Thread: linked list sorting function causes segfault

  1. #1
    Registered User
    Join Date
    Apr 2019
    Posts
    662

    linked list sorting function causes segfault

    i have the following function
    Code:
    #include <stdio.h>
    #include <stdlib.h>
    
    typedef struct Node
    {
        int age;
        struct Node *next;
    }Node;
    
    typedef struct LinkedList
    {
        struct Node *head;
        struct Node *tail;
    }LinkedList;
    
    enum Flag {FALSE = 0, TRUE = 1};
    
    void initalize_list(LinkedList *list);
    struct Node *create_head(void);
    struct Node *get_memory(void);
    int get_age(void);
    void print_list(const LinkedList list);
    void delete_list(LinkedList *list);
    void append_to_list(LinkedList *list);
    void prepend_to_list(LinkedList *list);
    void delete_node(LinkedList *list);
    int find_node(int age, Node **current, Node **previous);
    void remove_node(Node *current, Node *previous, LinkedList **list);
    void insert_node_in_middle(int index, LinkedList *list);
    void insert_node(int index, LinkedList **list, Node **tmp_node);
    void sort_list(LinkedList *list);
    
    int main()
    {
        //declare my list
        LinkedList list;
    
        //list.head = create_head();
        initalize_list(&list);
        append_to_list(&list);
        //append_to_list(&list);
        //prepend_to_list(&list);
        prepend_to_list(&list);
        print_list(list);
        delete_node(&list);
        print_list(list);
        append_to_list(&list);
        prepend_to_list(&list);
        print_list(list);
        insert_node_in_middle(2, &list);
        print_list(list);
        printf("\nsorting list\n");
        sort_list(&list);
        print_list(list);
        delete_node(&list);
        print_list(list);
        delete_list(&list);
    
        return 0;
    }
    
    void initalize_list(LinkedList *list)
    {
        list->head = NULL;
        list->tail = NULL;
    
        list->head = create_head();
        list->head->next = NULL;
        list->tail = list->head;
    
        list->head->age = get_age();
    }
    
    struct Node *create_head(void)
    {
        Node *head_tmp;
    
        head_tmp = get_memory();
        if (!head_tmp)
        {
            fprintf(stderr, "error allocating memory\n");
            exit(EXIT_FAILURE);// if it cant allocate memory for the head node at startup somthing really wrong so bug out
        }
    
        return head_tmp;
    }
    
    struct Node *get_memory(void)
    {
        return malloc(sizeof(Node));
    }
    
    int get_age(void)
    {
        int age;
    
        printf("PLease enter an age: ");
        scanf(" %d", &age);
    
        return age;
    }
    
    void print_list(const LinkedList list)
    {
        int count = 1;
        Node *tmp = list.head;
    
        while (tmp)
        {
            printf("person%d's age is %d\n", count, tmp->age);
            count++;
            tmp = tmp->next;
        }
    }
    
    void delete_list(LinkedList *list)
    {
        int count = 1;
        Node *tmp;
    
        printf("freeing memory.....\n");
        while (list->head)
        {
            tmp = list->head->next;
            printf("freeing element %d\n", count);
            free(list->head);
            list->head = tmp;
            count++;
        }
        printf("memory freed\n");
    }
    
    void append_to_list(LinkedList *list)
    {
        Node *tmp_node = NULL;
    
        tmp_node = get_memory();
    
        if(!tmp_node)
        {
            fprintf(stderr, "Unable to get memory for node to append\n");
            return;
        }
    
        tmp_node->age = get_age();
        list->tail->next = tmp_node; //set the tail's next pointer to point at the new node
        list->tail = tmp_node; //set tail to the new node;
    
        // if its the second node in the list list->head->next will be NULL so set the next pointer to point at tmp_node as well
        if (!list->head->next)
        {
            list->head->next = tmp_node;
        }
    }
    
    void prepend_to_list(LinkedList *list)
    {
        Node *tmp_node = NULL;
    
        tmp_node = get_memory();
    
        if(!tmp_node)
        {
            fprintf(stderr, "Unable to get memory for node to prepend\n");
            return;
        }
    
        tmp_node->age = get_age();
        tmp_node->next = list->head; //set tmp_node's next pointer to point at the current head pointer
        list->head = tmp_node; //set head to point to the new head/node
    }
    void insert_node_in_middle(int index, LinkedList *list)
    {
        Node *tmp_node = NULL;
    
        tmp_node = get_memory();
    
        if(!tmp_node)
        {
            fprintf(stderr, "Unable to get memory for node to prepend\n");
            return;
        }
        insert_node(index, &list, &tmp_node);
    }
    
    void insert_node(int index, LinkedList **list, Node **tmp_node)
    {
        int count = 0;
        Node *current_node = (*list)->head, *previous_node = NULL;
    
        while (current_node)
        {
            if (count == index)
            {
                break;
            }
            previous_node = current_node;
            current_node = current_node->next;
            count++;
        }
    
        if (!current_node)
        {
            append_to_list(*list);
            return;
        }
    
        (*tmp_node)->age = get_age();
        (*tmp_node)->next = previous_node->next;
        previous_node->next = (*tmp_node);
    }
    
    void delete_node(LinkedList *list)
    {
        int age;
        Node *current = list->head, *previous = NULL;
    
        printf("Please enter the age you wish to delete: ");
        scanf(" %d", &age);
    
        if (find_node(age, &current, &previous))
        {
            remove_node(current, previous, &list);
            free(current);
            printf("node deleted\n");
        }
        else
        {
            printf("Invalid age as no node found!\n");
        }
    }
    
    int find_node(int age, Node **current, Node **previous)
    {
        while (*current)
        {
            if ((*current)->age == age)
            {
                return TRUE;
            }
            *previous = *current;
            *current = (*current)->next;
        }
    
        return FALSE;
    }
    
    void remove_node(Node *current, Node *previous, LinkedList **list)
    {
        if (!previous) // current is pointing at the head
        {
            (*list)->head = current->next;
            current->next = NULL;
            printf("freeing head node\n");
        }
        else if(!current->next) // current is pointing at the tail (the last node)
        {
            (*list)->tail = previous;
            (*list)->tail->next = NULL;
            printf("freeing tail node\n");
        }
        else //its somewhere in the middle of the list
        {
            previous->next = current->next;
            current->next = NULL;
            printf("freeing middle node\n");
        }
    }
    
    void sort_list(LinkedList *list)
    {
        int index = 0;
        Node *current_loop_node = list->head, *current_node = NULL, *previous_node;
        Node *current_youngest_node, *previous_youngest_node, *tmp_node = NULL;
    
        while (current_loop_node)
        {
            current_node = current_loop_node;
            previous_node = NULL;
            current_youngest_node->age = current_loop_node->age;
    
            while (current_node)
            {
                if (current_youngest_node->age > current_node->age)
                {
                    current_youngest_node = current_node;
                    previous_youngest_node = previous_node;
                    tmp_node = current_node;
                }
                previous_node = current_node;
                current_node = current_node->next;
            }
    
            remove_node(current_youngest_node, previous_youngest_node, &list);
            insert_node(index, &list, &tmp_node);
            current_loop_node = current_loop_node->next;
            index++;
        }
    }
    and i thought everything was going swimmingly i was thinking i was mastering this
    But no i get a segfault on line 280 on the first itteration of the while loop on line 276

    last task i could think of as well
    coop

  2. #2
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    37,523
    > Node *current_youngest_node, *previous_youngest_node, *tmp_node = NULL;
    Not initialised here.

    > current_youngest_node->age = current_loop_node->age;
    Dereferenced here, blows up.

    > remove_node(current_youngest_node, previous_youngest_node, &list);
    > insert_node(index, &list, &tmp_node);
    > current_loop_node = current_loop_node->next;
    You need to be careful here.
    You remove an arbitrary node and place it at the head of the list.
    But current_loop_node was the head of the list - at least on the first iteration.

    TBH, the simplest approach is to do the 'sort' on the removal (as you're doing at the moment), and then just append the nodes to a new list altogether.
    Then return the new list when the old list is empty.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  3. #3
    Registered User
    Join Date
    Apr 2019
    Posts
    662
    ok now i am really confused i hard coded an age into current_youngest_node on line 280 and i still got a segfault. however unless i am being really dense here i have declared current_youngest_node the same way i have declared tmp_node and used tmp_node->age = get age 10 times with no issue

  4. #4
    Registered User
    Join Date
    Apr 2019
    Posts
    662
    sorry i was typing and trying things when you responded. i have tried setting current_youngest_node to null at deceleration but it still causes a segfault.

    why an arbitrary node it should be the one with the youngest age. then on the second iteration of the outer while loop as current_node is set to current_loop_node it doesn't pick up the youngest ages it goes for the second youngest and so on. least that is my intention have i not coded that?

    coop

  5. #5
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    37,523
    So initialise all your pointers to NULL.
    Then put a breakpoint on line 280.
    Then figure out why the pointer is still NULL.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  6. #6
    Registered User
    Join Date
    Apr 2019
    Posts
    662
    is it because the wind is blowing from the east where as half an hour ago it was blowing from the north east cos far as i can see that is the only difference between line 280 and 145 160 and 168
    Last edited by cooper1200; 05-26-2019 at 02:47 PM.

  7. #7
    Registered User
    Join Date
    Apr 2019
    Posts
    662
    of course its not till it executes line 280 does the value of current_youngest node change

  8. #8
    Registered User
    Join Date
    Apr 2019
    Posts
    662
    ok i can be thick at times the difference between lines 280 and the others is the otherrs were from malloc'ed memory. everywhere else tmp_node or its derivative is set from list->head soon as i set current_youngest to list->head i got through.

    there are still some bugs i need to work though is there a way of saying on error go to .... so i can send it to my delete list function and at least try to free some of the memory

  9. #9
    Registered User
    Join Date
    Feb 2019
    Posts
    550
    Quote Originally Posted by cooper1200 View Post
    is it because the wind is blowing from the east where as half an hour ago it was blowing from the north east cos far as i can see that is the only difference between line 280 and 145 160 and 168
    Nothing really matters. Anyone can see.
    Any way the wind blows...

  10. #10
    Registered User
    Join Date
    Apr 2019
    Posts
    662
    Quote Originally Posted by flp1969 View Post
    Nothing really matters. Anyone can see.
    Any way the wind blows...
    now that is funny lol

  11. #11
    Registered User
    Join Date
    Apr 2019
    Posts
    662
    seriously though does mint/umbuntu recover malloc'ed memory automatically in case of a program crash

  12. #12
    Registered User
    Join Date
    Feb 2019
    Posts
    550
    Quote Originally Posted by cooper1200 View Post
    seriously though does mint/umbuntu recover malloc'ed memory automatically in case of a program crash
    yep, it does

  13. #13
    Registered User
    Join Date
    Apr 2019
    Posts
    662
    next source of confusion is im trying to correct my insert node function. if i type (*list)-> auto complete comes up with head and tail. however if i do = (*list)->auto complete comes up with next not head and tail. im assuming its because im doing something wrong just have no clue what

  14. #14
    TEIAM - problem solved
    Join Date
    Apr 2012
    Location
    Melbourne Australia
    Posts
    1,859
    Salem has the problem.

    Imagine that you are the computer - You have the number "age" and you have been told to store it in the place that "current_youngest_node->age" points to. Imagine the shock horror to find that current_youngest_node->age doesn't have a valid address - Where would you put it?


    The answer is it use your get_memory function so that the computer has somewhere to put the value
    Fact - Beethoven wrote his first symphony in C

  15. #15
    Registered User
    Join Date
    Apr 2019
    Posts
    662
    i got the program to run with out any segfaults but got odd results so i decided to impliment salams idea of building a new list so please excuse the commented out bits
    Code:
    void sort_list(LinkedList *list, LinkedList *sorted_list)
    {
        int index = 0;
        Node *current_loop_node = list->head, *current_node = NULL, *previous_node;
        Node *current_youngest_node = list->head, *tmp_node = NULL,*previous_youngest_node = NULL;
    
        while (current_loop_node)
        {
            current_node = current_loop_node;
            previous_node = NULL;
            current_youngest_node->age = current_loop_node->age;
    
            while (current_node)
            {
                if (current_youngest_node->age > current_node->age)
                {
                    current_youngest_node = current_node;
                    previous_youngest_node = previous_node;
                    tmp_node = current_node;
                }
                previous_node = current_node;
                current_node = current_node->next;
            }
    
            printf("current youngest = %d\n", current_youngest_node->age);
            //remove_node(current_youngest_node, previous_youngest_node, &list);
            //insert_node(index, &list, &tmp_node);
            if (!sorted_list->head)
            {
                sorted_list->head = tmp_node;
                sorted_list->head->next = NULL;
                sorted_list->tail = sorted_list->head;
            }
            else if (!sorted_list->head->next)
            {
                sorted_list->head->next = tmp_node;
                tmp_node->next = NULL;
                sorted_list->tail = tmp_node;
            }
            else
            {
                sorted_list->tail->next = tmp_node;
                tmp_node->next = NULL;
            }
            current_loop_node = current_loop_node->next;
            index++;
        }
    }
    if i enter 11 22 33 and remove 33 then enter 44 55 and 66 the it only finds 11 55 and 55 again and the sorted list only has one entry in it (55) and strangely the original list (unaltered) now only has three entries in it 66 55 and 55 again

    i have no idea how i am causing this
    coop

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Segfault on a linked list insert operation
    By anstmich in forum C Programming
    Replies: 6
    Last Post: 03-25-2011, 09:20 AM
  2. Segfault with Linked List Program
    By kbrandt in forum C Programming
    Replies: 1
    Last Post: 06-23-2009, 07:13 AM
  3. Need help with linked list sorting function
    By Jaggid1x in forum C Programming
    Replies: 6
    Last Post: 06-02-2009, 02:14 AM
  4. segfault from linked list function
    By kataya in forum C Programming
    Replies: 7
    Last Post: 04-16-2008, 04:30 AM
  5. Segfault when trying to free a double linked list
    By Rpog in forum C Programming
    Replies: 1
    Last Post: 04-19-2005, 07:37 AM

Tags for this Thread