Generic Singly Linked List in C I decided to learn generic programming in C (and take a break from templates in C++) by implementing my first simple data structure in C: the singly linked list.

What I'm looking to gain out of reviews is:


Clarity/quality
Algorithmic correctness
Code style for C
Structure and design
Any bugs or issues you can find


I'm planning to use this as a basis for implementing a hash-map in C that uses chaining. 

slist.h

#ifndef C_SLIST_H
#define C_SLIST_H

#include &lt;stdbool.h&gt;
#include &lt;stddef.h&gt;

struct slist_node;
struct slist;

typedef bool (*func_cmp)(const void *a, const void *b);

struct slist *slist_init(func_cmp cmp);

void slist_insert(struct slist *, void *);

void slist_free(struct slist *);

bool slist_empty(const struct slist *);

void *slist_value(const struct slist_node *);

struct slist_node *slist_find(const struct slist *, void *);

void clear(struct slist *);

size_t slist_size(const struct slist *);

void slist_remove(struct slist *, void *);
#endif


slist.c

#include &lt;stdlib.h&gt;
#include "slist.h"

struct slist_node {
    struct slist_node *next;
    void *data;
};

struct slist {
    struct slist_node *head, *tail;
    func_cmp compare;
};

static struct slist_node *create_node(void *value)
{
    struct slist_node *node = calloc(1, sizeof(*node));
    if (!node) { return NULL; }
    node-&gt;data = value;
    return node;
}

static bool default_compare(const void *a, const void *b)
{
    return a == b;
}

struct slist *slist_init(func_cmp func)
{
    struct slist *l = calloc(1, sizeof(struct slist));
    l-&gt;compare = func ? func : default_compare;
    return l;
}

void slist_insert(struct slist *l, void *value)
{
    if (!l) { return; }

    if (slist_empty(l)) {
        l-&gt;head = create_node(value);
        if (!l-&gt;head) { return; }
        l-&gt;tail = l-&gt;head;
        return;
    }

    l-&gt;tail-&gt;next = create_node(value);
    if (!l-&gt;tail-&gt;next) { return; }

    if (l-&gt;tail-&gt;next) { 
        l-&gt;tail = l-&gt;tail-&gt;next; 
    }
}

void clear(struct slist *l)
{
    if (!l) { return; }

    struct slist_node *copy = l-&gt;head;
    while (copy) {
        struct slist_node *after = copy-&gt;next;
        free(copy);
        copy = after;
    }

    l-&gt;head = NULL;
    l-&gt;tail = NULL;
}

void slist_free(struct slist *l)
{
    clear(l);
}

bool slist_empty(const struct slist *l)
{
    return l ? l-&gt;head == NULL : true;
}

void *slist_value(const struct slist_node *n)
{
    return n ? n-&gt;data : NULL;
}

size_t slist_size(const struct slist *l)
{
    if (!l || slist_empty(l)) { return 0; }

    const struct slist_node *copy = l-&gt;head;
    size_t size = 0;
    while (copy) {
        ++size;
        copy = copy-&gt;next;
    }
    return size;
}

static struct slist_node *slist_find_ahead(const struct slist *l, void *value)
{    
    struct slist_node *copy = l-&gt;head;
    while (copy) {
        if ((l-&gt;compare)(copy-&gt;next-&gt;data, value)) {
            return copy;
        } else {
            copy = copy-&gt;next;
        }
    }
    return NULL;
}

struct slist_node *slist_find(const struct slist *l, void *value)
{
    if (!l || slist_empty(l)) { return NULL; }

    if ((l-&gt;compare)(l-&gt;head-&gt;data, value)) { return l-&gt;head; }

    const struct slist_node *found = slist_find_ahead(l, value);
    return found ? found-&gt;next : NULL;
}

void slist_remove(struct slist *l, void *value)
{
    if (!l || slist_empty(l)) { return; }

    if (l-&gt;head-&gt;data == value) {
        struct slist_node *copy = l-&gt;head;
        if (l-&gt;tail == l-&gt;head) {
            l-&gt;tail = copy-&gt;next;
        }
        l-&gt;head = copy-&gt;next;
        free(copy);
        return;
    }

    struct slist_node *ahead = slist_find_ahead(l, value);
    if (!ahead) { return; }

    if (ahead-&gt;next == l-&gt;tail) {
        l-&gt;tail = ahead;
    }
    struct slist_node *to_delete = ahead-&gt;next;
    ahead-&gt;next = ahead-&gt;next-&gt;next;
    free(to_delete);
}
[can't finish now--work in progress]

In create_node:

static struct slist_node *create_node(void *value)
{
    struct slist_node *node = calloc(1, sizeof(*node));
    if (!node) { return NULL; }
    node-&gt;data = value;
    return node;
}


...I see a few things I don't like. Personally, I'd prefer an explicit comparison to NULL rather than !node. I'd also rather avoid doubled-up return statements, so I'd probably write the code more like this:

static struct slist_node *create_node(void *value)
{
    struct slist_node *node = calloc(1, sizeof(*node));
    if (node != NULL)
        node-&gt;data = value;
    return node;
}


I'm also a bit less than enthused about using calloc here. You're assuming that the zero-bytes used to initialize the memory will turn into null pointers when the right number of them are treated as a pointer. That's pretty common, but not actually required. It also means that node-&gt;data gets initialized to zero bytes, only to be immediately overwritten with some other value. As a rule, I'd prefer to explicitly set the pointers:

static struct slist_node *create_node(void *value)
{
    struct slist_node *node = malloc(sizeof(*node));
    if (node != NULL) {
        node-&gt;next = NULL;           
        node-&gt;data = value;
    }
    return node;
}


I'd at least consider keeping track of the current list size in the slist structure. When you insert a node, increment it. When you remove a node, decrement it. This lets you get the size for essentially zero cost with extremely minimal overhead.

I'd write slist_find_ahead using a for loop, something like:

struct slist_node *p;
for (p=list-&gt;head; p!=NULL; p=p-&gt;next)
    if (list-&gt;compare(p-&gt;data, value))
        return p;
return NULL;


As it is, slist_find_ahead will attempt to dereference copy-&gt;next-&gt;data, even when copy-&gt;next == NULL.