Thread: Help understanding linked list behavior

  1. #1
    Registered User
    Join Date
    Jun 2009
    Posts
    486

    Help understanding linked list behavior

    Hi all,

    I have the following two structs which form linked lists:

    Code:
    struct Cusumlevel
    {
        double current;
        uint64_t length;
        struct Cusumlevel *next;
    };
    typedef struct Cusumlevel cusumlevel;
    Code:
    struct Edge
    {
        uint64_t location;
        int64_t type;
        struct Edge *next;
    };
    typedef struct Edge edge;
    This linked list is a member of another struct,

    Code:
    struct Event
    {
        [...other variables...]
        struct Edge *first_edge;
        struct Cusumlevel *first_level;
        struct Event *next;
        struct Event *prev;
    };
    typedef struct Event event;
    I have a function that allocates memory for and populated cusumlevel structs:

    Code:
    cusumlevel *add_cusum_level(cusumlevel *lastlevel, double current, uint64_t length)
    {
        cusumlevel *temp;
        if (lastlevel)
        {
            if ((lastlevel->next=malloc(sizeof(cusumlevel)))==NULL)
            {
                printf("Cannot allocate level node\n");
                abort();
            }
            lastlevel->next->current = current;
            lastlevel->next->length = length;
            lastlevel->next->next = NULL;
            temp = lastlevel->next;
        }
        else
        {
            if ((lastlevel=malloc(sizeof(cusumlevel)))==NULL)
            {
                printf("Cannot allocate level head node\n");
                abort();
            }
            lastlevel->current = current;
            lastlevel->length = length;
            lastlevel->next = NULL;
            temp = lastlevel;
        }
        return temp;
    }
    and I have a function that gets the data to do it with:

    Code:
    void average_cusum_levels(event *current, uint64_t subevent_minpoints, double cusum_minstep)
    {
        edge *first_edge = current->first_edge;
        edge *current_edge = first_edge;
        cusumlevel *first_level = current->first_level;
        cusumlevel *current_level = first_level;
    
        [...initialize variables...]
    
        while (current_edge)
        {
    
            [...get values for current and length...]
    
            current_level = add_cusum_level(current_level, average, current_edge->location - anchor);
    
            [...clean up for next iteration...]
    
        }
        current_level = first_level;
        while (current_level)
        {
            printf("%g\t%"PRIu64"\n",current_level->current, current_level->length);
            current_level = current_level->next;
        }
    }

    My problem is that the printf at the end does not print anything, as though the linked list were never allocated. I'm sure I'm just mixing up pointers somewhere, but it's a case of having stared at the problem so long I am obviously just making the same mistake every time. I have verified that during the loop over the edge linked list, current_level contains the correct data. It just isn't getting reset to the head of the list before I print, or the list is not getting assembled properly.

    Can someone help me spot the error? Let me know if additional information is needed, I tried to pare it down to the basics.
    Last edited by KBriggs; 07-06-2015 at 11:06 AM. Reason: fixed code formatting
    C is fun

  2. #2
    Tweaking master Aslaville's Avatar
    Join Date
    Sep 2012
    Location
    Rogueport
    Posts
    528
    Can someone help me spot the error?
    Are your format specifiers correct to start with ? - (too lazy to check )

  3. #3
    Registered User
    Join Date
    Jun 2009
    Posts
    486
    Yes, the format specifiers are correct: PRIu64 is a macro for printing uint64_t types. This code compiles without error or warnings with -Wall and -Wextra flags enabled so I think it would complain otherwise, and the same format specifiers can be used inside the edge loop to verify that the data is correctly added by the add_cusum_level() function.

    For example:

    Code:
    printf("%g\t%"PRIu64"\n",current_level->current, current_level->length);
    just below the call to add_cusum_level() will cause the correct data to be printed.

    somehow the linked list seems to be getting disconnected somewhere, it's as if I am losing the proper reference to the start of the list, or something.

    EDIT: I should add: current->first_level == NULL prior to the first call to add_cusum_level()
    Last edited by KBriggs; 07-06-2015 at 11:02 AM.
    C is fun

  4. #4
    Registered User
    Join Date
    Jun 2011
    Posts
    4,509
    It would be easier if we had a simplified example we could compile and test, but at a glance, I'd suspect that your head pointer of type "cusumlevel" is not being allocated as you expect.

    You pass "lastlevel" to your "add_cusum_level()" function, and if it's NULL, try to allocate memory to use it as a head ... but that's only a local copy of the pointer. It's like passing an int to a function, changing its value, and the value remains unchanged in the caller.

    If you wanted to update what "lastlevel" points to (when using it as a head), you'd want to pass the address of the "lastlevel" pointer (i.e. a pointer to a pointer).

    I don't know if that's the source of your problem, but probably worth looking into regardless.

  5. #5
    Registered User
    Join Date
    Jun 2015
    Posts
    1,643
    add_cusum_level has a bug in the first branch of the if. Ultimately it adds the node as the second node in the list and returns a pointer to it (cutting off the head).
    You can simplify your code by creating a separate function to allocate a new node.
    Code:
    cusumlevel *new_cusum_level(double current, uint64_t length) {
        cusumlevel *x = malloc(sizeof *x);
        if (!cusumlevel) {
            fprintf(stderr, "Cannot allocate level node\n");
            abort();
        }
        x->current = current;
        x->length = length;
        x->next = NULL;
        return x;
    }
    
    cusumlevel *add_cusum_level(cusumlevel *lastlevel, double current, uint64_t length) {
        cusumlevel *x = new_cusum_level(current, length);
        if (last_level)
            x->next = last_level;
        return x;
    }

  6. #6
    Registered User
    Join Date
    Jun 2009
    Posts
    486
    I don't think I understand - the first branch of the if happens if there is already a node in existence, and it adds a new one and returns a pointer to the new one. The head node should be stored back in the caller in first_level, so it should never be lost. Is this incorrect? I am modifying pointers, rather than values, so it should be reflected in the caller. Or does malloc not necessarily retain the memory address? (EDIT: now that I type this, I am fairly sure you are correct. Stay tuned while I implement and test).

    @Matticus: I use similar logic elsewhere in the code and it works OK, but that doesn't necessarily mean anything. I will try the suggestions above and if I can't get it running I will put together an MWE for you guys.
    Last edited by KBriggs; 07-06-2015 at 12:52 PM.
    C is fun

  7. #7
    Registered User
    Join Date
    Jun 2015
    Posts
    1,643
    If you mean to add the new node to the very front of the list then that is not at all what's happening. You don't pass lastlevel back but instead pass temp which has been set to lastlevel->next.

    Try my replacement code.

  8. #8
    Registered User
    Join Date
    Jun 2009
    Posts
    486
    You were correct. Malloc in the head node case was causing the reference to the actual head node to be lost. Thanks!

    My error was assuming that if I declare a pointer and then malloc it, that malloc would allocate memory wherever the pointer pointed initially. In hindsight, this is obviously silly ^_^.
    Last edited by KBriggs; 07-06-2015 at 01:09 PM.
    C is fun

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Linked List - Still not understanding!
    By stach in forum C Programming
    Replies: 4
    Last Post: 08-12-2013, 08:08 AM
  2. help understanding linked list
    By progmateur in forum C Programming
    Replies: 4
    Last Post: 03-19-2013, 02:02 PM
  3. Doubly Linked List - Understanding...
    By hi-0ctane in forum C Programming
    Replies: 3
    Last Post: 05-31-2009, 05:27 PM
  4. understanding linked list
    By sara.stanley in forum C Programming
    Replies: 5
    Last Post: 04-14-2006, 04:32 PM
  5. Replies: 2
    Last Post: 11-28-2003, 11:50 AM