Small implementation of a singly-linked list in C89

Question

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

Answer 1

• 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.

Answer 2

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.