Segfault on a linked list insert operation

Hi all,

I am implementing my own double-linked list (I know there are existing libraries that accomplish the task better, however the list will eventually need to be specialized in a number of ways) and I am getting a Segmentation fault when attempting to insert an item at the end of the list.

The gdb output and backtrace:

Code:

---

]Program received signal SIGSEGV, Segmentation fault.
0x00000000004021b1 in insertBefore (existing=0x7fffffffe600, newNode=0x604330) at src/Cerveau_List.c:49
49                        existing->prev->next = newNode;
(gdb) bt
#0  0x00000000004021b1 in insertBefore (existing=0x7fffffffe600, newNode=0x604330) at src/Cerveau_List.c:49
#1  0x0000000000401285 in main (argc=1, argv=0x7fffffffe608) at src/Cerveau.c:99
(gdb)

---

and valgrind output:

Code:

---

==27391== Process terminating with default action of signal 11 (SIGSEGV)
==27391==  Access not within mapped region at address 0x8
==27391==    at 0x4021B1: insertBefore (Cerveau_List.c:49)
==27391==    by 0x401284: main (Cerveau.c:99)
==27391==  If you believe this happened as a result of a stack
==27391==  overflow in your program's main thread (unlikely but
==27391==  possible), you can try to increase the size of the
==27391==  main thread stack using the --main-stacksize= flag.
==27391==  The main thread stack size used in this run was 8388608.

---

And the code...
Cerveau_List.h

Code:

---

#include "Cerveau_Data.h"

#ifndef __Cerveau_Data_h__
#define __Cerveau_Data_h__

#define NULL 0

typedef struct CNode {
       
        /// Each node houses a Cerveau_Data struct, the fundamental unit of information in Cerveau
        Cerveau_Data* datum;
       
        /// Pointer to the next node in the list
        struct CNode* next;
       
        /// Pointer to the previous node in the list
        struct CNode* prev;
       
        /// Numerical index in case vectorization is needed
        int index;
       
} Cerveau_Node;

void insertAfter(Cerveau_Node* existing, Cerveau_Node* newNode);
void insertBefore(Cerveau_Node* existing, Cerveau_Node* newNode);


#endif

---

Cerveau_List.c

Code:

---

#include "Cerveau_List.h"

/**
 * Insert a node after an existing node.
 *
 * @param existing An existing node
 * @param newNode The new node to be inserted.
 */
void insertAfter(Cerveau_Node* existing, Cerveau_Node* newNode)
{
        if(newNode == NULL) {
                return;
        }
        // make newNode the first node of a list
        else if(existing == NULL) {
                newNode->next = newNode;
                newNode->prev = newNode;
        }
        // insert the new node
        else {
       
                newNode->next = existing->next;
                existing->next->prev = newNode;
                newNode->prev = existing;
                existing->next = newNode;
        }
}

/**
 * Insert a node before an existing node
 *
 * @param existing An existing node in the list
 * @param newNode The new Node to be inserted
 */
void insertBefore(Cerveau_Node* existing, Cerveau_Node* newNode)
{
        if(newNode == NULL) {
                return;
        }
        // make newNode the first node of a list
        else if(existing == NULL) {
                newNode->next = newNode;
                newNode->prev = newNode;
        }
        // insert the new node
        else {
       
                newNode->next = existing;
                existing->prev->next = newNode;
                newNode->prev = existing->prev;
                existing->prev = newNode;
        }
}

---

According to the debugger output, the problem occurs on the line

Code:

---

existing->prev->next = newNode;

---

however I have been staring at this for a while and cant seem to figure out why this is producing a problem. I am assuming the problem is stemming from a poor understanding of a certain aspect of pointers/memory management, so I would really appreciate any help on the topic.

Thanks!

Where do you allocate memory for your nodes?

Code:

---

newnode = malloc(sizeof(node));

---

also from your struct definition existing->prev->next is not a part of the struct.

Quote:

---

Originally Posted by CommonTater

Where do you allocate memory for your nodes?

Code:

---

newnode = malloc(sizeof(node));

---

also from your struct definition existing->prev->next is not a part of the struct.

---

I allocate memory in my main function with the line:

Code:

---

newNode = malloc(sizeof(Cerveau_Node));

---

What do you mean that it is not part of the struct? "existing->prev" is a pointer to a struct and so wouldnt "existing->prev->next" provide access to the pointer of the struct resulting from "existing->prev"? Or is this a misunderstanding? Thanks!

It may be a misunderstanding... on my part... perhaps one of the others can clarify... but it certianly does appear that your compiler isn't grasping your intent at that point... maybe (existing->prev)->next ?



I went to the allocation question because that's the most usual cause of "seg fault" problems as you described.

Hmm, putting it in parentheses results in the same error =S

Code:

---

existing->prev->next = newNode;

---

Simple. possibility existing->prev is NULL. duh~
After all just think the logic. for one element list, what would be prev pointing to? NULL nope?

Ahhhh! That is it. I had explicitly tried to catch this problem by setting the next and previous nodes of the first noded added to that first node itself (thus making the very first node added linked with itself).

My code for creating and adding the nodes:

Code:

---


if(head == NULL) {
        head = malloc(sizeof(Cerveau_Node));
        head->datum = data;
        current = head;
        head->next = head;
        head->prev = head;
}
else{
        newNode = malloc(sizeof(Cerveau_Node));
        newNode->datum = data;
       
        // add the new node to the list
        insertBefore(head, newNode);
        current = newNode;

}

---

The problem however, was a simple one -- I assumed that

Code:

---

Cerveau_Node* head;

---

would default to NULL, but it wasnt (silly me), so the "if(head == NULL)" condition was always false. Initializing head to NULL fixed everything.

Thanks a lot!! I feel like an idiot now.