Thread: 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.

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

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.

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 ^_^.