Segmentation fault while adding a new node to a list

Question

i have a problem while searching a list and trying to add a new node. The Code looks as follows

struct sizelist{
    int currentsize, origsize;
    struct sizelist * next;
};
typedef struct sizelist item;

Here are sizes the content, items is the amount of nodes connected and next is the next node.

void firstfit(item tosort){
  int junksize = tosort.currentsize;
  int paired;
  item* current;
  for(int i=0;i<containeramount;i++){
    if(containers[i].currentsize - junksize >=0){
      paired = i;
      break;
    }
  }
  current = &containers[paired];
  while(current->next!=NULL){
    current = current->next;
  }
  containers[paired].currentsize = containers[paired].currentsize - junksize;
  current->next = &tosort;
 }

containers is an array of item.

This seems to work now. But now i have a problem with my output:

void writeout(){
  item* current;
  for(int i=0;i<containeramount;i++){
    current = &containers[i];
    for(int j=0;; j++){
      printf("%d ",current->currentsize);
      if(current->next!=NULL){
        current = current->next;
      }
      else{
        break;
      }
    }
    printf("\n");
  }
}

Now you also have all to understand the program. I give it for example 3 containers of size 10 each and things to sort of size 6,8,1,5. It looks like firstfit makes it's job, but the writeout method not. The proper output here should be:

10 6 1

10 8

10 5

Here the output for origsize is:

10 3

10 3

10 3

and for currentsize it is:

3 134515941

2 134515941

5 134515941

Answer 1

It looks like the latest revision of the code is much improved, but tosort is passed into firstfit(item tosort) by value. That means within the function firstfit(item tosort), tosort is a temporary variable that is destroyed at the end of the function. (This was in the earlier version of the program too, but we looked at other problems first.)

Now that the function is doing its work on the actual contents of containers[paired] rather than on a temporary copy of something, the final next pointer in the list is being set (as desired), but it points to the temporary object tosort. When the function ends, tosort goes out of scope. Presumably, something else gets written to the same block of virtual memory by the time you try to print this out.

This will work better if the function is changed to firstfit(item* tosort), that is, pass a pointer instead of a copy of the struct. This will behave a little bit more like you would expect a call to a function to behave in Java.

---

Note: The remarks below refer to revision 2 of the question. The code in the question has since been modified so that it follows these recommendations.

---

I'm finding so many apparent errors in the code it's hard to keep track of all of them, but I suspect that the segmentation fault is here:

    current = containers[paired];
    for(int i=0;i<containers[paired].items;i++){
        current = *current.next;
    }

One of the errors in the code is that you declare item current;. That means current is always a temporary data structure and is never actually "in" containers[paired]. When you do current.next = &tosort; the only thing that is changed is a field of this temporary data structure, which goes out of scope on the next line and is destroyed. So in effect that line does nothing at all. It most decidedly does not insert any data in containers[paired].

On the other hand, containers[paired].items++; does increment the counter in containers[paired]. So now containers[paired].items is greater than the number of items actually in the linked list. This means that when you come into this function some other time and execute the loop above with the same containers[paired], you will execute current = *current.next; too many times; you end up trying to access the next node of the last node in the list, and then you segfault.

The standard way to implement a simple linked list in C is to set the next pointer to 0 (or NULL if it's defined as 0) whenever there is no actual "next" thing in the list; the last thing in the list always has next equal to 0. In order to find the last thing in the list, you don't count the number of times to follow the next pointer; you simply follow the next pointer until you reach the node whose next pointer is 0, and then you stop.

I highly recommend getting rid of items. You can always find out how many items are in the container by following the list to the end and counting the number of nodes you encounter. Sure, this takes longer than just reading the value of items, but it will give you the correct answer and it will not cause a segmentation fault. Get your program to work without error, and then you can think about making it faster if you need to (for example by putting items back in your struct and making it actually have the correct value).