Thread: Segfault on a linked list insert operation

  1. #1
    Registered User
    Join Date
    Mar 2011
    Posts
    4

    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!
    Last edited by anstmich; 03-25-2011 at 07:48 AM.

  2. #2
    Banned
    Join Date
    Aug 2010
    Location
    Ontario Canada
    Posts
    9,547
    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.

  3. #3
    Registered User
    Join Date
    Mar 2011
    Posts
    4
    Quote Originally Posted by CommonTater View Post
    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!

  4. #4
    Banned
    Join Date
    Aug 2010
    Location
    Ontario Canada
    Posts
    9,547
    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.

  5. #5
    Registered User
    Join Date
    Mar 2011
    Posts
    4
    Hmm, putting it in parentheses results in the same error =S

  6. #6
    Registered User
    Join Date
    May 2010
    Location
    Naypyidaw
    Posts
    1,314
    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?

  7. #7
    Registered User
    Join Date
    Mar 2011
    Posts
    4
    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.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Circularly-Doubly Linked List implementation
    By BlackOps in forum C Programming
    Replies: 4
    Last Post: 07-19-2009, 04:45 AM
  2. circular doubly linked list help
    By gunnerz in forum C++ Programming
    Replies: 5
    Last Post: 04-28-2007, 08:38 PM
  3. singly linked circular list
    By DarkDot in forum C++ Programming
    Replies: 0
    Last Post: 04-24-2007, 08:55 PM
  4. Replies: 6
    Last Post: 03-02-2005, 02:45 AM
  5. singly linked list
    By clarinetster in forum C Programming
    Replies: 2
    Last Post: 08-26-2001, 10:21 PM