2
\$\begingroup\$

I'm very new to C and have extensive experience with C# and very little with C++, but basically none with C.

I wrote a small program that declares a singly-linked list struct, a few methods operating on the list, and then uses it from the main method. Even though I've read about it a lot, this is only my second/third program I've written in C, so please beware.

#include <assert.h>
#include <inttypes.h>
#include <stddef.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct linked_list_node linked_list_node; // forward declare linked_list_node and add it to the struct/global namespaces

struct linked_list_node
{
    linked_list_node* next;
    int32_t item;
};

typedef struct
{
    linked_list_node* head;
    size_t size;
} linked_list;

void init_list(linked_list* list) { /* Nothing to do here */ }

void add_last(linked_list* list, int32_t item)
{
    assert(list != NULL);

    if (list->head == NULL)
    {
        // No elements in the list yet.
        list->head = malloc(sizeof(linked_list_node));
        list->head->next = NULL;
        list->head->item = item;
    }
    else
    {
        // At least 1 element in the list.
        assert(list->size > 0);

        // Walk the list until we find the last node.
        linked_list_node* node = list->head;
        while (node->next != NULL)
        {
            node = node->next;
        }

        // Allocate a new last node
        linked_list_node* next = malloc(sizeof(linked_list_node)); // note: no typecast from void* here
        node->next = next;
        next->next = NULL; // need to explicitly do this since malloc's memory is uninitialized
        next->item = item;
    }

    list->size++;
}

typedef void action(int32_t);

void foreach_list(linked_list* list, action* act)
{
    assert(list != NULL && act != NULL);

    linked_list_node* node;
    for (node = list->head;
        node != NULL;
        node = node->next)
    {
        act(node->item);
    }
}

// Cleans up all of the memory used up by the list's
// nodes. DOES NOT FREE THE LIST ITSELF.
void cleanup_list(linked_list* list)
{
    assert(list != NULL);

    list->size = 0;

    // Walk the list, freeing nodes as we go.
    linked_list_node* node, *next;
    for (node = list->head;
        node != NULL;
        node = next)
    {
        next = node->next;
        free(node);
    }
}

void print_int32(int32_t to_print)
{
    printf("Found %"PRIi32"!\n", to_print); // format specifier for int32_t
}

int main(void)
{
    linked_list list;
    memset(&list, 0, sizeof(list));
    init_list(&list);

    add_last(&list, 3);
    add_last(&list, 4);
    add_last(&list, 5);

    foreach_list(&list, print_int32);
    printf("Size: %"PRIu64"\n", (uint64_t)list.size); // do not use %zu since this is targeting C89

    cleanup_list(&list);
    return 0;
}

I compiled this under MinGW with C89.

Here is the type of feedback I'm looking for:

  • Did I introduce and potential sources of UB? For example, is there a flaw in my logic where a NULL pointer can be dereferenced and go undetected by asserts?

  • Is my memory management logic correct? Did I accidentally malloc something that never got cleared, or did I free anything twice in cleanup_list? Is there a way to make all of the logic less error-prone?

  • Did I rely on any features specific to GCC to get this to work? For example, will this program also work with other compilers under C89?

  • Any way I could clean up the code and make it more neat/concise? (I am aware that I should probably have put the list definition/methods into separate header/source files than main.)

\$\endgroup\$
3
\$\begingroup\$
  • init_list

    should really initialize the list. Otherwise you are forcing the caller to make an non-obvious memset.

    void init_list(linked_list * list) {
        list->head = 0;
        list->size = 0;
    }
    

    is much more clean.

  • add_last

    is not a particularly good name. Traditionally this operation is called append or push_back.

    The function can be streamlined. First, assert your invariant fully (that is either head == 0 and size == 0 or head != 0 and size > 0) and immediately.

    Second, once the invariant is deemed correct, allocate the node (you need to do it anyway). It is a good idea to delegate node allocation to a function.

    Finally, find the tail (it is also a good candidate to factor out into a function), and attach the node. For example,

    void append (linked_list * list, int32_t item)
    {
        assert(list_is_good(list));
        linked_list_node * node = create_list_node(item);
        linked_list_node * tail = find_list_tail(list);
        if (tail == NULL) {
            list->head = node;
        } else {
            tail->next = node;
        }
        list->size += 1;
    }
    
  • malloc may fail

    Test the results of malloc. There is not much you can do once it fails, but it is good form anyway.

\$\endgroup\$
2
\$\begingroup\$

Did I introduce and potential sources of UB?

A1. Lack of check that malloc() worked.

list->head = malloc(sizeof(linked_list_node));
if (list->head == NULL) We_Are_Outta_Here();
list->head->next = ... // Potential UB.

Is my memory management logic correct?

B1. Rather than have init_list() initialize the head pointer, the calling code does a memset() to clear the list. It makes more sense and is more understandable to have init_list() do that clearing.

linked_list list;
// Move memset / initialization to `init_list()`
// memset(&list, 0, sizeof(list));
init_list(&list);

B2. Although cleanup_list() is OK, consider adding a scrub. By zeroing free'd resources, code that inadvertently accesses free'd data tends to fail quicker. Sooner bad code fails, easier it is to ID and fix.

memset(node, 0, sizeof *node); // add to enhance debugging.
free(node);

Did I accidentally malloc something .. Is there a way to make all of the logic less error-prone?

C1. free(NULL) is OK code and like-wise allowing cleanup_list() to free again a link list is good. Just clear the head node to an initial state. Detail: cleanup_list() should be able to be followed by a another init_list().

memset(list, 0, sizeof *list); // add to cleanup_list()

C2. Allocate to the size of the reference type. Less error prone. No need to code the matching type.

// list->head = malloc(sizeof(linked_list_node))
list->head = malloc(sizeof *(list->head))

C3. foreach_list() lacks a method for the called action to abort the loop. Further, make more useful to also pass a state variable into act()

{
    // Allow `act()` to quit early 
    if(act(state, node->item)) return 1;
}

Did I rely on any features specific to GCC to get this to work? For example will this program also work with other compilers under C89?

D1. printf("Size: %"PRIu64"\n", (uint64_t)list.size); // do not use %zu since this is targeting C89 is odd. Both uint64_t and "%zu" are C99 features and uint64_t is an optional type even in C99,C11. The simple and portable alternative to print types lacking a known matching specifier is to cast to a wide supported type.

printf("Size: %lu\n", (unsigned long) list.size);
// or if desperate for a wide type
printf("Size: %.0f\n", 1.0 * list.size);

D2. int32_t is an optional type in C99,C11. It does not exist in C89. Consider long.

D3. #include <inttypes.h> is not C89.

Any way I could clean up the code and make it more neat/concise?

E1. Segment into .h and .c files.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.