Generic Singly Linked List in C

Question

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 <stdbool.h>
#include <stddef.h>

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 <stdlib.h>
#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->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->compare = func ? func : default_compare;
    return l;
}

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

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

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

    if (l->tail->next) { 
        l->tail = l->tail->next; 
    }
}

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

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

    l->head = NULL;
    l->tail = NULL;
}

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

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

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

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

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

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

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

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

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

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

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

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

    if (ahead->next == l->tail) {
        l->tail = ahead;
    }
    struct slist_node *to_delete = ahead->next;
    ahead->next = ahead->next->next;
    free(to_delete);
}

Answer 1

• DRY

  In slist_insert the node creation code is duplicated. Do it once:

      slist_node * node = create_node(value);
      if (!node) { return; }
      if (slist_empty(l)) {
          l->tail = l->head = node;
          return;
      }
      l->tail->next = node;
      l->tail = node;
  

  There is still a bit of duplicated code (tail assignment), so totally DRY version should look like:

      slist_node * node = create_node(value);
      if (!node) { return; }
      if (slist_empty(l)) {
          l->head = node;
      } else {
          l->tail->next = node;
      }
      l->tail = node;
  

  Same applies to slist_remove.

• slist_insert should return a success/failure indication (e.g. invalid list, failure to create node).

• clear looks strange: it doesn't follow the naming convention, and is identical to slist_free. Why do you need it?

Answer 2

[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->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->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->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->next = NULL;           
        node->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->head; p!=NULL; p=p->next)
    if (list->compare(p->data, value))
        return p;
return NULL;

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