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

• Reinderien: Sigh. Stuff like l0__create makes me sad. This is macro-heavy, and thus fairly unmaintainable. What's your justification for all of the macros? You know you can define entire functions in C in a header file, right? Just ensure that they're declared static, and then you can write sane code.
• AShelly: Macros are the only way to make type-safe generics in C. A function needs to accept a specific type. Which would require either casts to void, or macro wrappers to define type-specific versions. I think this is safer and easier to use

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.

• AShelly: I take your point about naming and separation of concerns. Isn't next a fairly standard name for the next element in a list? However, I'm not happy with "MACROS BAD" as a criticism. With the exception of create, which I'm happy to separate into allocate and initialize components, what is unmaintainable or nightmarish about these macros, which are broken down into simple sequences of steps?
• janos: For "next" to make sense, it needs a reference point: "next" from what? I don't know what that means in the context of a list. What's wrong with macros? Lot's of things, as widely known, I don't understand why you ask... stackoverflow.com/a/14041847/641955
• AShelly: Honestly, every example in the accepted answer there is terrible. Yes, you can write terrible macros with unintended side effects. I have done my best to avoid doing that, and to write ones that are hard to abuse. I know I need to fix create. Are there other actual use cases that will break my code?
• janos: @AShelly I rephrased my remark about macros. Some people consider them a nightmare to maintain, myself included. You are not one of those people, and that's fine. Do note that I acknowledged the necessity in your use case, so I cannot recommend to remove completely, I only recommend to make it as minimal as possible. If you don't agree that by doing so your code will become more maintainable, that's fine as well. It's up to you which recommendations you find useful and actually put to use and which you don't. If you think my answer contains bad recommendation, then I suggest to downvote it.