3
\$\begingroup\$

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);
}
\$\endgroup\$

2 Answers 2

1
\$\begingroup\$
  • 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?

\$\endgroup\$
1
  • \$\begingroup\$ 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. \$\endgroup\$
    – Bizkit
    Commented Jan 14, 2016 at 20:11
1
\$\begingroup\$

[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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.