Double Linked List Implementation Review

Question

I've written a double-linked list library for another program I'm working on. I want to be particular about this library because I will be using it in another library, which will be used the program I'm currently working on.

I'm including the header file, source file, and a test main file (and its output). As far as I can tell, everything works fine. But I can run additional testing, if there's a reason to do so.

Any sort of feedback would be great. I don't mind criticism.

The source file is large-ish, so I can remove the main and test results if nobody thinks that it's necessary.

#ifndef LIST_H
#define LIST_H

/*
 * list.h
 *
 * A simple library for using double linked lists
 *
 * Written by Taylor Holberton
 * During June 2013
 */

typedef enum {
    list_null,
    list_single,
    list_front,
    list_back,
    list_middle
} list_nodetype;

struct list_node {
    void    * data,
            * next,
            * last;
};

/* Notes:
 *
 * 'after' and 'before' {
 *
 *      The words after and before indicate which way
 *      the list is shifting after list size modification
 *
 *      ie: (1) - (2) - (3)
 *
 *      putafter(2)   = (1) - (2) - (n) - (3)
 *
 *      putbefore (2) = (1) - (n) - (2) - (3)
 * }
 *
 * 'backwards' and 'forwards' {
 *
 *      The words 'backwards' and 'forwards' refer
 *      to the order of traversal the function will take.
 *      'Backwards' doesn't include the current node in the
 *      traversal and 'forwards' does.
 * }
 */

struct list_node * list_createnode (unsigned int size);

void list_setnode (struct list_node *, void * data, unsigned int size);

struct list_node * list_get (struct list_node *, int offset);
struct list_node * list_getfront (struct list_node *);
struct list_node * list_getback (struct list_node *);

struct list_node * list_putbefore (struct list_node *, unsigned int size);
struct list_node * list_putafter  (struct list_node *, unsigned int size);

struct list_node * list_splitbefore (struct list_node *);
struct list_node * list_splitafter  (struct list_node *);

struct list_node * list_freeforwards (struct list_node *);
void list_freebackwards  (struct list_node *);

void list_free (struct list_node *);
void list_remove (struct list_node *);

unsigned int list_size (struct list_node *);
unsigned int list_countbackwards (struct list_node *);
unsigned int list_countforwards (struct list_node *);

// returns the node at which the traversal stopped (may be null)
struct list_node * list_traverse (struct list_node *, int (*callback)(void *));
struct list_node * list_traversebackwards (struct list_node *, int (*callback)(void *));
struct list_node * list_traverseforwards (struct list_node *, int (*callback)(void *));

struct list_node * list_pop (struct list_node *);
struct list_node * list_popback  (struct list_node *);
struct list_node * list_popfront (struct list_node *);
struct list_node * list_pushback  (struct list_node *, unsigned int size);
struct list_node * list_pushfront (struct list_node *, unsigned int size);

list_nodetype list_getnodetype (struct list_node * node);

#endif

Source file:

#include <stdlib.h>
#include <string.h>
#include "list.h"

struct list_node * list_createnode (unsigned int size){

    size += sizeof (struct list_node);
    struct list_node * newnode = calloc (1, size);

    if (size) newnode->data = newnode + sizeof (struct list_node);

    return newnode;
}

void list_setnode (struct list_node * node, void * data, unsigned int size){
    if (node && node->data)
            memcpy (node->data, data, size);
}

struct list_node * list_get (struct list_node * node, int offset){

    switch (list_getnodetype (node)){

    case list_null:
            return 0;

    case list_back:
            if (offset > 0) return 0;
            break;

    case list_front:
            if (offset < 0) return 0;
            break;
    }

    if (offset > 0)
            while (node && offset){
                    node = node->next;
                    offset--;
            }

    if (offset < 0)
            while (node && offset){
                    node = node->last;
                    offset++;
            }

    return node;
}

struct list_node * list_getfront (struct list_node * node){
    if (node) while (node->last) node = node->last;
    return node;
}

struct list_node * list_getback (struct list_node * node){
    if (node) while (node->next) node = node->next;
    return node;
}

struct list_node * list_putbefore (struct list_node * node, unsigned int size){

    struct list_node * newnode = 0,
                     * last = 0;

    switch (list_getnodetype (node)){

    case list_null:
            break;

    default:
            if (newnode = list_createnode (size)){
                    last = node->last;

                    newnode->next = node;
                    newnode->last = node->last;

                    node->last = newnode;
                    if (last) last->next = newnode;
            }

            break;
    }

    return newnode;
}

struct list_node * list_putafter (struct list_node * node, unsigned int size){

    struct list_node * newnode = 0,
                     * next = 0;

    switch (list_getnodetype (node)){

    case list_null:
            break;

    default:
            if (newnode = list_createnode (size)){
                    next = node->next;

                    newnode->last = node;
                    newnode->next = next;

                    if (next) next->last = newnode;
                    node->next = newnode;
            }

            break;
    }

    return newnode;
}

struct list_node * list_splitbefore (struct list_node * node){

    struct list_node * last = 0;

    switch (list_getnodetype (node)){

    case list_middle:
    case list_back:

            last = node->last;
            last->next = 0;
            node->last = 0;

            last = list_getfront (last);

            break;

    }

    return last;
}

struct list_node * list_splitafter (struct list_node * node){

    struct list_node * next = 0;

    switch (list_getnodetype (node)){

    case list_middle:
    case list_front:

            next = node->next;
            next->last = 0;
            node->next = 0;
    }

    return next;
}

struct list_node * list_freeforwards (struct list_node * node){

    struct list_node * temp = 0,
                     * last = 0;

    switch (list_getnodetype (node)){

    case list_middle:
    case list_back:

            last = node->last;

    }

    while (node){
            temp = node->next;
            free (node);
            node = temp;
    }

    return last;
}

void list_freebackwards (struct list_node * node){

    struct list_node * temp = 0;

    switch (list_getnodetype (node)){

    case list_middle:
    case list_back:

            node = node->last;

            while (node){
                    temp = node->last;
                    free (node);
                    node = temp;
            }

            break;
    }
}

void list_free (struct list_node * node){

    switch (list_getnodetype (node)){

    case list_null:
            return;

    case list_front:

            list_freeforwards (node);
            break;

    case list_middle:

            list_freebackwards (node); // the order of this
            list_freeforwards (node);  // is important
            break;

    case list_back:

            list_freebackwards (node);
            free (node);
            break;

    case list_single:
            free (node);
            break;
    }
}

void list_remove (struct list_node * node){
    node = list_pop (node);
    if (node) free (node);
}

unsigned int list_size (struct list_node * node){

    unsigned int count = 0;

    switch (list_getnodetype (node)){

    case list_null:
            return 0;
    case list_single:
            return 1;

    default:
            count = list_countforwards (node)
            +       list_countbackwards (node);
            break;
    }

    return count;
}

unsigned int list_countbackwards (struct list_node * node){

    unsigned int count = 0;

    switch (list_getnodetype (node)){

    case list_null:
    case list_front:
            break;
    case list_single:
            return 1;

    default:
            while (node = node->last)
                    count++;

            break;
    }

    return count;
}

unsigned int list_countforwards (struct list_node * node){

    unsigned int count = 0;

    switch (list_getnodetype (node)){

    case list_null:
    case list_back:
            break;
    case list_single:
            return 1;

    default:

            while (node){
                    count++;
                    node = node->next;
            }

            break;

    }

    return count;
}

struct list_node * list_traverse (struct list_node * node, int (*callback)(void * data)){

    if (!callback || !node) return node;

    node = list_getfront (node);

    while (node){
            if (callback (node->data)) break;
            node = node->next;
    }

    return node;
}

struct list_node * list_traverseforwards (struct list_node * node, int (*callback)(void * data)){

    if (!callback) return node;

    switch (list_getnodetype (node)){

    case list_null:
            break;

    default:
            while (node){
                    if (callback (node->data)) break;
                    node = node->next;
            }
    }

    return node;
}

struct list_node * list_traversebackwards (struct list_node * node, int (*callback)(void * data)){

    if (!callback) return node;

    switch (list_getnodetype (node)){

    case list_null:
            break;

    default:
            node = node->last;

            while (node){
                    if (callback (node->data)) break;
                    node = node->last;
            }

            break;
    }

    return node;
}

struct list_node * list_pop (struct list_node * node){

    struct list_node * next = 0,
                     * last = 0;

    if (!node) return;

    next = node->next;
    last = node->last;

    if (next) next->last = last;
    if (last) last->next = next;

    node->next = 0;
    node->last = 0;

    return node;
}

struct list_node * list_popback (struct list_node * node){
    return list_pop (list_getback (node));
}

struct list_node * list_popfront (struct list_node * node){
    return list_pop (list_getfront (node));
}

struct list_node * list_pushback (struct list_node * node, unsigned int size){
    return list_putafter (list_getback (node), size); // already error-checked
}

struct list_node * list_pushfront (struct list_node * node, unsigned int size){
    return list_putbefore (list_getfront (node), size);
}

list_nodetype list_getnodetype (struct list_node * node){

    list_nodetype type;

    if (!node) type = list_null;
    else if ( node->next && !node->last) type = list_front;
    else if ( node->last && !node->next) type = list_back;
    else if (!node->last && !node->next) type = list_single;
    else type = list_middle;

    return type;
}

Example implementation:

#include <stdio.h>
#include <string.h>
#include "list.h"

#define strpsize(value) value, sizeof (value)
#define nodesize 5

int callback (void * data){
    if (data) printf ("found data\n");
    else printf ("found empty node\n");
    return 0;
}

int callback2 (void * data){
    if (data) printf ("found data traversing backwards!\n");
    else printf ("found empty data traversing backwards!\n");
    return 0;
}

int callback3 (void * data){
    if (data) printf ("found data traversing forwards\n");
    else printf ("found empty data traversing forwards!\n");
    return 0;
}

int callback4 (void * data){
    if (!data){
            printf ("found empty slot. stopping loop now.\n");
            return -1;
    }

    return 0;
}

int callback5 (void * data){
    char * str = data;
    if (data && str[0]){
            printf ("found: %s\n", str);
            return -1;
    } else printf ("null\n");

    return 0;
}

int main (){

    struct list_node * head = list_createnode (nodesize),
                     * middle = 0,
                     * tail = 0,
                     * error = 0;

    list_pushback (head, nodesize);
    list_pushback (head, 0);

    if (!head){
            printf ("head is null\n");
            list_free (head);
            return -1;
    }

    middle = list_get (head, 1);

    if (!middle){
            printf ("middle node is null\n");
            list_free (head);
            return -1;
    }

    middle = list_putafter (middle, nodesize);
    list_putbefore (middle, nodesize);

    list_pushfront (middle, nodesize);

    head = list_getfront (middle);

    printf ("size of list is %d\n", list_size (head));
    printf ("size after head is %d\n", list_countforwards (head));

    tail = list_getback (middle);

    printf ("size before tail is %d\n", list_countbackwards (tail));
    printf ("size after middle is %d\n", list_countforwards (middle));
    printf ("size before middle is %d\n", list_countbackwards (middle));

    list_traverse (head, callback);
    list_traversebackwards (head, callback2);
    list_traverseforwards (head, callback3);

    list_traverse (head, callback4);

    middle = list_putafter (middle, sizeof ("node message"));

    list_setnode (middle, strpsize ("node message"));

    error = list_traverse (head, callback5);

    printf ("removing text node..\n");
    list_remove (error);

    printf ("checking again..\n");
    list_traverse (head, callback5);

    printf ("freeing memory\n");
    list_free (head);

    printf ("exiting\n");
    return 0;
}

Results:

size of list is 6
size after head is 6
size before tail is 5
size after middle is 2
size before middle is 4
found data
found data
found data
found data
found data
found data
found data traversing forwards
found data traversing forwards
found data traversing forwards
found data traversing forwards
found data traversing forwards
found data traversing forwards
null
null
null
null
null
found: node message
removing text node..
checking again..
null
null
null
null
null
null
freeing memory
exiting

Running this with valgrind the output is a little different and I get a lot of invalid reads (still working on that), but no memory leaks. I'm not asking anyone to figure that out, though - just a general review.

Additional notes:

The library was written so that any node within the list can be used for operations. This is advantageous when it comes to successive calls to similar areas within the list.

For example:

Instead of calling list_pushback (head, size) multiple times, like this:

 list_pushback (head, size);
 list_pushback (head, size);
 list_pushback (head, size);

The calls could be made like this:

 tail = list_pushback (head, size);
 tail = list_pushback (tail, size);
 tail = list_pushback (tail, size);

Which completely eliminates the need for traversal within the function - which greatly improves the speed in loops. This might help review the code, just so you know what I was "going for".

Answer 1

I'll post some more comments later, but to start with, you should let the compiler guide you. If you compile this with -Wall (gcc or clang) you will get many warnings and one error.

• Some warnings are caused by expressions such as

  if (newnode = list_createnode (size)){ ...
  

  which should hve an extra set of brackets to show that you intended the assignment:

  if ((newnode = list_createnode (size))){ ...
  

  Some coding standards will object to this too and prefer to see:

  if ((newnode = list_createnode (size)) != NULL){ ...
  

• Another source of warnings comes from your switch statements that do not include a case for each possibility

• Warnings also come from your test callbacks that should be 'static'.

• The error is in list_pop where you return without supplying a value

EDIT

---

Ok here's some further comments.

In the header file I'd probably define the enum constants as upper-case (although I actually think they are unnecessary, as is the function that returns them and the switches that depend upon them). The list_node would more normally be expressed as:

struct list_node {
    void *data;
    struct list_node *next;
    struct list_node *prev;
};
typedef struct list_node list_node;

I'm surprised that list_node doesn't hold the data size, as each of your nodes can differ in size. I'd re-name last to prev (previous) as it is not ambiguous ('last' could mean the last in the list). Note that it is common to typedef the struct so that you don't have to type 'struct' everywhere:

Well done for putting a meaningful explanation of terms in a comment.

I see no const parameters - I'm sure some of those functions don't modify their input list.

---

Some general comments on the implementation.

I have never seen a list implementation that doesn't expect the user to keep a pointer to the head of the list. Your list functions work with a pointer to anywhere in the list, which is interesting. But is there a need for this behaviour? Why does your application need this?

It is normal in C to start functions with the { in column 0. Although to be honest, nobody else seems bothered about this.

Sizes are often represented using size_t rather than unsigned int (although it comes to much the same thing). If unsigned int is used instead, there is no need to include a system header to get size_t. But most of the time that is not a concern and (although I am cautious in using unsigned types) I would use size_t.

Use of braces even when strictly unnecessary is considered best practice. One-liners are generally not used much:

if (node && node->data) {
        memcpy(node->data, data, size);
}

Define only one variable per line and don't use commas to continue to another line.

You are using switch statements where a simple if-then-else would be better. For example in list_putbefore

switch (list_getnodetype (node)){

case list_null:
     break;

default:
     ...

is better stated as:

if (list_getnodetype(node) != list_null) {...}

Define variables where they are needed rather than at the start of the function. This makes their use clearer by reducing their scope.

Your list_getnodetype is unnecessary.

---

In list_createnode and list_setnode:

The if (size) is redundant. You know that sizeof (struct list_node) is non-zero... unless you wanted to test the original size passed as a parameter, which is no longer available.

Also, there is no check for calloc failure.

Separating create and set functions might be reasonable, but I'd expect to see the set function checking that the size is ok (which requires the node to have a size field). Or, perhaps better, you could combine create/set so that the data is passed and copied when the node is allocated.

---

In list_get:

Much too complicated. Why not use the obvious:

while (offset && node) {
    if (offset < 0) {
        node = node->last;
        ++offset;
    }
    else {
        node = node->next;
        --offset;
    }
}
return node;

Also node could be const (true in many functions and not mentioned again)

---

list_getfront and list_getback should be written out normally, not compressed vertically. Also consider a for-loop.

if (node) {
    for (; node->last; node = node->last) {
        /* nothing */
    }
}
return node;

---

In list_putbefore and list_putafter, you don't need to call list_getnodetype to tell that the list is empty. Also it would be reasonable to expect these functions to add the first element to the list instead of failing if the list is empty.

---

In list_splitbefore and list_splitafter you don't need to call list_getnodetype - you can just inspect node and node->last/next

if (node && node->last) {
    struct list_node *last = node->last;
    last->next = 0;
    node->last = 0;
    return list_getfront (last);
}
return NULL;

---

Your list_free* functions seem redundant. I'd expect a list_free to free everything from the given node forwards. If a caller really wants to free a list using a pointer to somewhere other than the beginning of the list, she can do:

list_free(list_getfront(list));

Similarly if the caller wants to free a list backwards from a pointer to somewhere other than the beginning of the list, she can do:

list_free(list_splitbefore(list));

Similarly, your counting and traversal functions have some redundancy.