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?

• Bizkit: I actually noticed there was a memory leak in my slist_free function. I call clear to clear the list but I never free the memory I allocated from slist_init. The clear function not following the naming convention is an oversight that I'll fixed. It's meant to be called by client code to clear the list.

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.