invalid write size of 1 in C

Question

I trying to write a queue(String Version) program in C by using linked lists.

Here is the structure:

struct strqueue;
typedef struct strqueue *StrQueue;

struct node {
  char *item;
  struct node *next;
};

struct strqueue {
  struct node *front;//first element
  struct node *back;//last element in the list
  int length;
};

I creates a new StrQueue first

StrQueue create_StrQueue(void) {
  StrQueue q = malloc(sizeof (struct strqueue));
  q->front = NULL;
  q->back = NULL;
  q->length = 0;
  return q;
}

makes a copy of str and places it at the end of the queue

void push(StrQueue sq, const char *str) {
  struct node *new = malloc(sizeof(struct node));
  new->item = NULL;
  strcpy(new->item,str);//invalid write size of 1 ?
  new->next = NULL;
  if (sq->length == 0) {
  sq->front = new;
  sq->back = new;
} else {
  sq->back->next = new;
  sq->back = new;
}
sq->length++;
}

frees the node at the front of the sq and returns the string that was first in the queue

char *pop(StrQueue sq) {
 if (sq->length == 0) {
 return NULL;
}
 struct node *i = sq->front;
 char *new = sq->front->item;
 sq->front = i->next;
 sq->length --;
 free(sq->front);
 return new;
}

I got invalid write size of 1 at strcpy(new->item,str); I dont understand why I got this error. Can anyone tell me why and tell me how should I fix it? Thanks in advance.

Answer 1

Okay, first things first, in the answer below I am NOT fixing your doubly linked list concepts, I am just showing you how you should fix the code above within the scope of your question. You may want to look into how doubly linked lists are done.

In:

void push(StrQueue sq, const char *str) {
  struct node *new = malloc(sizeof(struct node));
  new->item = NULL;

The next statement is wrong:

  strcpy(new->item,str);

There are two ways you can solve it:

1. Make sure that *str is a valid pointer outside of the list management context while the list is being used.

2. Let the list manage the string allocation (and possibly deallocation).

   1. is the quick and dirty method, it's easier to debug later but larger codebase makes it cumbersome.
   2. cleaner looking code, but requires initial setup discipline, you should create object (string) management routines in addition to list management routines. can be cumbersome in its own right.

CASE 1: const char *str is guaranteed to be valid for life of StrQueue (this is what you are looking for really)

It should be:

new->item = str;

Here we assume str was a dynamic string allocated elsewhere

Now, in pop when you pop off the string you are okay. because the pointer you are returning is still valid (you are guaranteeing it elsewhere)

CASE 2: const char *str is not guaranteed to be valid for life of StrQueue

Then use:

new->item = strdup(str);

Now, in pop when you pop off the string you can either

1. de-allocate the strdup and not return anything, (not quite the same things as you did)
2. pass a container pointer to pop where contents of item are copied (clean)
3. return the popped off pointer, but you must deallocate it separately when you are done with it (ugly)

Which would make your pop function one of the following:

Case 2.1:

 void pop(StrQueue sq) {

    if (sq->length == 0) {
       return NULL;
    }
    struct node *node = sq->front;
    sq->front = node->next;
    sq->length--;
    free(node->item);
    free(node);
}

Case 2.2:

 char *pop(StrQueue sq, char *here) {

    if (sq->length == 0) {
       return NULL;
    }
    struct node *node = sq->front;
    sq->front = node->next;
    sq->length--;
    strcpy(here, node->item);
    free(node->item);
    free(node);
}

Case 2.3:

 char *pop(StrQueue sq) {

    char *dangling_item = NULL;
    if (sq->length == 0) {
       return NULL;
    }
    struct node *node = sq->front;
    sq->front = node->next;
    sq->length--;
    dangling_item = node->item;
    free(node);
    return dangling_item;
}

Answer 2

I got invalid write size of 1 at strcpy(new->item,str); I dont understand why I got this error. Can anyone tell me why and tell me how should I fix it?

Why:

This code:

new->item = NULL;
strcpy(new->item,str);//invalid write size of 1 ?

You're not suppose to pass a null pointer to the first argument, it should be a pointer to allocated memory. The reason why you're getting this error message, I can imagine, is because the implementation of strcpy probably looks like this:

for (int i = 0; str2[i]; i++) str1[i] = str2[i];

And in the first iteration of the for loop, it writes to address 0 (a read-only section of memory) - this gives you the invalid write of size 1. I'm not sure, however, why you are only getting a size of 1, though (I would imagine it would be the entire size of the string). This could be because either a) str is only of size 1 or b) because the signal, SIGSEGV stops the program.

How to fix:

Allocate space for new->item before calling strcpy, like this:

new->item = malloc (strlen (str) + 1); // + 1 for null-terminating character

But you could probably include some error checking, like this:

int len = strlen (str) + 1;
if (len){
    new->item = malloc (len);
    if (!new->item){
        return;
    }
}