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

and for currentsize it is:

3 134515941

2 134515941

5 134515941

Welcome to Stackoverflow! Do you have stable way to reproduce the problem? What is the initial values to do it? Have you tried to use debugger? — Ilya
– Ilya, Commented Jul 31, 2015 at 12:35
paired might be uninitialised if none of the containers fit. Initialise it with an illegal index, say -1 and enforce that it has a legal index later. — M Oehm
– M Oehm, Commented Jul 31, 2015 at 12:37
When you say current = containers[paires], you copy the contents. If you have a linked list, you want pointers to existing items, not copies. Likewise, the line current = *current.next look wrong. It should be current = current->next and current should be a pointer to an item. — M Oehm
– M Oehm, Commented Jul 31, 2015 at 12:41
Are you sure it's a good idea to keep a count of the number of nodes connected in the node? AFAICT, it means if you insert a node at the end, you have to walk back and increment every nodecount in the list, which is probably bug-prone and inefficient. — user3185968
– user3185968, Commented Jul 31, 2015 at 12:43

Community · Accepted Answer · 2017-05-23 12:21:43Z

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).

Thank you, I can programm in java, but i don't understand that POINTER style. I have edited my first post now because i have another problem, that i do not understand anymore.

Collectives™ on Stack Overflow

Segmentation fault while adding a new node to a list

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related