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.

Quote:

---

Can someone help me spot the error?

---

Are your format specifiers correct to start with ? - (too lazy to check :) )

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

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.

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;
}

---

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.

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.

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