Generic Linked List (header-only and non-intrusive)

Question

Although I should know better, I wrote my own linked list implementation in C.

My goal was to make it a true generic collection, with no need to modify the structure being listed. I only implemented push, pop, peek, append, size, and next. This is sufficient for implementing stacks or queues.

I welcome feedback, suggestions for improvement, use cases that break it. I'd love an idea for a compiler-independent way of returning a value from l0_size().

#ifndef L0__H_
#define L0__H_
//# LIST0 - A Generic Linked-List Header-only Library for C 

#include <stdlib.h>  //for calloc/free

/* PRIVATE helpers, start with l0__ (double underscore). Here be dragons. */
#define l0__nexta(hd)  (void **)((hd)+1)   //address of next ptr
#define l0__nextv(hd) (*l0__nexta((hd)))   //value of next ptr
#define l0__create(hd, val) (((hd)=calloc(1,sizeof(*(hd))+sizeof((hd))))?*(hd)=(val):(val))
#define l0__gototail(hd) do {} while ((l0_next((hd)))&&((hd)=l0__nextv((hd))))

/* Public Interface */
#define l0_next(head) ((head) ? l0__nextv(head) : NULL)
#define l0_peek(head) (*(head))

#define l0_add(head, value) do {                  \
      if (!(head)) { l0__create((head), value); } \
      else { void *save__0l = (head);             \
         l0__gototail(head);                      \
         void **next__0l = l0__nexta(head);       \
         l0__create((head), value);               \
         *next__0l = (head);                      \
         (head) = save__0l;                       \
      } } while (0)

#define l0_push(head, value) do {               \
      void *rest__0l = (head);                  \
      l0__create((head), value);                \
      l0__nextv(head) = rest__0l;               \
   } while (0)

#define l0_pop(head) do {                       \
      void *dead__0l = (head);                  \
      (head) = l0_next(head);                   \
      free(dead__0l);                           \
   } while (0)

#define l0_isempty(head) ((head)==NULL)
#define l0_listof(type) type *

#if defined(___GNUC__) || defined(__clang__)
//return val version.  //needs "statement expression" support
#define l0_size(head) ({int len__0l=0; void* head__0l=(head);   \
         for (; (head); (head)=l0__nextv(head) ) { ++len__0l; } \
         (head)=head__0l; len__0l;})
#else
//getter version, pass &int;
#define l0_size(head, sz_out) do { void* head__0l=(head);                \
      for (*sz_out=0; (head); (head)=l0__nextv(head) ) { (*sz_out)+=1; } \
      (head)=head__0l;                                                   \
   } while (0)
#endif

#endif

Test program:

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

#include "l0.h"

int main(int argc, const char* argv[]) {

   typedef l0_listof(float) float_list;

   float_list listp = NULL;

   // Initial list is empty
   assert(l0_size(listp) == 0);
   assert(l0_isempty(listp));

   //add an element - it is there
   l0_add(listp, 1);
   assert(l0_size(listp) == 1);
   assert(!l0_isempty(listp));
   assert(l0_peek(listp) == 1.0);

   //add a second element - the list grows, the head does not change
   l0_add(listp, 2.1f);
   assert(l0_size(listp) == 2);
   assert(!l0_isempty(listp));
   assert(l0_peek(listp) == 1.0);

   //pop the head - the list shrinks, the head changes
   l0_pop(listp);
   assert(l0_size(listp) == 1);
   assert(!l0_isempty(listp));
   assert(l0_peek(listp) == 2.1f);

   //pop the head - the list is empty again
   l0_pop(listp);
   assert(l0_size(listp) == 0);
   assert(l0_isempty(listp));

   //pop an empty list, no change
   l0_pop(listp);
   assert(l0_size(listp) == 0);
   assert(l0_isempty(listp));

   //push onto a list - element is present
   l0_push(listp, 3.3f);
   assert(l0_size(listp) == 1);
   assert(!l0_isempty(listp));
   assert(l0_peek(listp) == 3.3f);

   //push again onto a list - list grows, new element is front
   l0_push(listp, 4.4f);
   assert(l0_size(listp) == 2);
   assert(!l0_isempty(listp));
   assert(l0_peek(listp) == 4.4f);

   //push again onto a list - list grows, new element is front
   l0_push(listp, 5.5f);
   assert(l0_size(listp) == 3);
   assert(!l0_isempty(listp));
   assert(l0_peek(listp) == 5.5);

   //walk the list
   float expected[] = {5.5f, 4.4f, 3.3f};
   int n=0;
   for (float_list i = listp; i!=NULL; i=l0_next(i))
   {
      printf("%f ",*i);
      assert(*i == expected[n++]);
   }
   printf("\n");

   //pop the head - the list shrinks, the head changes
   l0_pop(listp);
   assert(l0_size(listp) == 2);
   assert(!l0_isempty(listp));
   assert(l0_peek(listp) == 4.4f);

   //arbitrary things can be in lists
   typedef struct {
      int n;
      float f;
   } blob;
   #define BLOB(name, n) blob name = {n,n}
   #define BLOBEQ(a,b) (a.n==b.n && a.f == b.f)

   l0_listof(blob) sl;
   assert(l0_size(sl)==0);

   BLOB(one,1);
   BLOB(two,2);
   BLOB(three,3);

   // Initial list is empty
   assert(l0_size(sl) == 0);
   assert(l0_isempty(sl));

   //add an element - it is there
   l0_add(sl, one);
   assert(l0_size(sl) == 1);
   assert(!l0_isempty(sl));
   assert(BLOBEQ(l0_peek(sl), one));

   //push onto a list - list grows, new element is front
   l0_push(sl, two);
   assert(l0_size(sl) == 2);
   assert(!l0_isempty(sl));
   assert(BLOBEQ(l0_peek(sl), two));

   //add to end - the list grows, the head does not change
   l0_add(sl, three);
   assert(l0_size(sl) == 3);
   assert(!l0_isempty(sl));
   assert(BLOBEQ(l0_peek(sl), two));

   //pop the head - the list shrinks, the head changes
   l0_pop(sl);
   assert(l0_size(sl) == 2);
   assert(!l0_isempty(sl));
   assert(BLOBEQ(l0_peek(sl), one));

   //pop the head - the list shrinks, the head changes
   l0_pop(sl);
   assert(l0_size(sl) == 1);
   assert(!l0_isempty(sl));
   assert(BLOBEQ(l0_peek(sl), three));

   //pop the head - the list is empty again
   l0_pop(sl);
   assert(l0_size(sl) == 0);
   assert(l0_isempty(sl));

   printf(" PASS! \n");
}

Answer 1

API design

I only implemented push, pop, peek, append, size, and next. This is sufficient for implementing stacks or queues.

I find this API confusing:

• What's the difference between push and append?
• What is next?

I think it would be better to implement a list Abstract Data Type with methods that are perfectly clear and intuitive. If you also want to provide stacks and queues, you could provide specialized APIs for those, and implement them in terms of the lower list, which will be a hidden implementation detail, and you can save users from any confusion.

From a list I would expect methods insert, append, remove, size, isEmpty, first, last.

A stack could be implemented on top of that, with methods push, pop, isEmpty, which would internally use a list, without exposing other methods of the list that may confuse users. Same thing for a queue.

Implementation

The implementation of the list is entirely in macros. As a commenter pointed out, this is considered by some people a nightmare to maintain. You responded that "macros are the only way to make type-safe generics in C". Which is true, but I believe you can take a sort of hybrid approach, separating the essential generic code that can only be implemented with macros, and other parts that can be implemented in regular C.

In particular, the only part that needs to be generic is the value stored in list nodes. The operations on the nodes, the behavior of the list is independent from the payload in the nodes. Therefore, I believe you can implement the list operations in regular C, and limit the use of macros for the nodes.