Circular double linked list implementation

gistfile1.c

#include <stdio.h>
#include <stdlib.h>
#include <memory.h>
#include <string.h>
#include <assert.h>

// node structure
typedef struct list_t {
    char *value;
    struct list_t *next;
    struct list_t *prev;
} list_t;

static void failed_allocation(void) {
    fprintf(stderr, "Out of memory.\n");
    abort();
}


// initialize a linked list header pointer. Just sets it to NULL.
void list_init(list_t** listpp)
{
    if (listpp)
        *listpp = NULL;
}

// return the value-field of a valid list node.
// otherwise return NULL if node is NULL.
const char *list_node_value(list_t *node)
{
    return (node ? node->value : NULL);
}

// return the next pointer (which may be a self-reference)
//  of a valid list_t pointer.
list_t *list_next(list_t *node)
{
    return (node ? node->next : NULL);
}

// return the previous pointer (which may be a self-reference)
//  of a valid list_t pointer.
list_t *list_previous(list_t *node)
{
    return (node ? node->prev : NULL);
}


// return the same pointer we were passed.
list_t *list_first(list_t *headp)
{
    return headp;
}

// return the previous pointer (which may be a self-reference)
//  of the given list-head pointer.
list_t *list_last(list_t *headp)
{
    return list_previous(headp);
}

// insert a new item at the end of the list, which means it
//  becomes the item previous to the head pointer. this handles
//  the case of an initially empty list, which creates the first
//  node that is self-referencing.
list_t *list_append(list_t **headpp, const char* value)
{
    if (!headpp) // error. must pass the address of a list_t ptr.
        return NULL;

    // allocate a new node.
    list_t* p = malloc(sizeof(*p));
    if (p == NULL)
        failed_allocation();

    // setup duplicate value
    p->value = (value) ? strdup(value) : NULL;

    // insert the node into the list. note that this
    //  works even when the head pointer is an initial
    //  self-referencing node.
    if (*headpp)
    {
        (*headpp)->prev->next = p;
        p->prev = (*headpp)->prev;
        p->next  = (*headpp);
        (*headpp)->prev = p;
    }
    else
    {   // no prior list. we're it. self-reference
        *headpp = p;
        p->next = p->prev = p;
    }
    return p;
}


// insert a new value into the list, returns a pointer to the
//  node allocated to hold the value. this will ALWAYS update
//  the given head pointer, since the new node is being prepended
//  to the list and by-definition becomes the new head.
list_t *list_prepend(list_t **headpp, const char* value)
{
    list_append(headpp, value);
    if (!(headpp && *headpp))
        return NULL;
    *headpp = (*headpp)->prev;
    return *headpp;
}


// insert a new node previous to the given valid node pointer.
// returns a pointer to the inserted node, or NULL on error.
list_t *list_insert_before(list_t* node, const char* value)
{
    // node *must* be a valid list_t pointer.
    if (!node)
        return NULL;
    list_prepend(&node, value);
    return node;
}


// insert a new node after the given valid node pointer.
// returns a pointer to the inserted node, or NULL on error.
list_t *list_insert_after(list_t* node, const char* value)
{
    // node *must* be a valid list_t pointer.
    if (!node)
        return NULL;
    node = node->next;
    list_prepend(&node, value);
    return node;
}


// delete a node referenced by the node pointer parameter.
//  this *can* be the root pointer, which means the root
//  must be set to the next item in the list before return.
int list_remove(list_t** headpp, list_t* node)
{
    // no list, empty list, or no node all return immediately.
    if (!(headpp && *headpp && node))
        return 1;

    // validate the node is in *this* list. it may seem odd, but
    //  we cannot just free it if the node may be in a *different*
    //  list, as it could be the other list's head-ptr.
    if (*headpp != node)
    {
        list_t *p = (*headpp)->next;
        while (p != node && p != *headpp)
            p = p->next;
        if (p == *headpp)
            return 1;
    }

    // isolate the node pointer by connecting surrounding links.
    node->next->prev = node->prev;
    node->prev->next = node->next;

    // move the head pointer if it is the same node
    if (*headpp ==  node)
        *headpp = (node != node->next) ? node->next : NULL;

    // finally we can delete the node.
    free(node->value);
    free(node);
    return 0;
}


// release the entire list. the list pointer will be reset to
//  NULL when this is finished.
void list_free(list_t **headpp)
{
    if (!(headpp && *headpp))
        return;
    while (*headpp)
        list_remove(headpp, *headpp);
}


// enumerate the list starting at the given node.
void list_foreach(list_t *listp, void (*function)(const char*))
{
    if (listp)
    {
        list_t *cur = listp;
        do {
            function(cur->value);
            cur = cur->next;
        } while (cur != listp);
    }
    printf("\n");
}

// printer callback
void print_str(const char* value)
{
    printf("%s\n", value);
}

// main entrypoint
int main(int argc, char *argv[])
{
    list_t *listp;
    list_init(&listp);

    // insert some new entries
    list_t* hello =   list_append(&listp, "Hello, Bedrock!!");
    assert(NULL != hello);
    assert(listp == hello);

    // insert Fred prior to hello. does not change the list head.
    list_t* fred = list_insert_before(hello, "Fred Flintstone");
    assert(NULL != fred);
    assert(listp == hello);
    // Hello, Bedrock!!
    // Fred Flintstone
    list_foreach(listp, print_str);

    // insert Wilma priot to Fred. does not change the list head.
    list_t* wilma = list_insert_before(fred, "Wilma Flintstone");
    assert(NULL != wilma);
    assert(list_next(wilma) == fred);
    assert(list_previous(wilma) == hello);
    // Hello, Bedrock!!
    // Wilma Flintstone
    // Fred Flintstone
    list_foreach(listp, print_str);

    list_t* barney =  list_prepend(&listp, "Barney Rubble");
    list_t* dino =    list_insert_after(wilma, "Dino");
    assert(barney != NULL);
    assert(dino != NULL);
    assert(listp == barney);
    assert(list_previous(barney) == fred);
    assert(list_next(barney) == hello);
    // Barney Rubble
    // Hello, Bedrock!!
    // Wilma Flintstone
    // Dino
    // Fred Flintstone
    list_foreach(listp, print_str);

    // remove everyone, one at a time.
    list_remove(&listp, fred);   // will not relocate the list head.
    // Barney Rubble
    // Hello, Bedrock!!
    // Wilma Flintstone
    // Dino
    list_foreach(listp, print_str);

    list_remove(&listp, hello);  // will not relocate the list head.
    // Barney Rubble
    // Wilma Flintstone
    // Dino
    list_foreach(listp, print_str);

    list_remove(&listp, barney); // will relocate the list head.
    // Wilma Flintstone
    // Dino
    list_foreach(listp, print_str);
    assert(listp == wilma);
    assert(list_next(wilma) == dino);
    assert(list_previous(listp) == dino);

    list_remove(&listp, wilma);  // will relocate the list head.
    // Dino
    list_foreach(listp, print_str);

    list_remove(&listp, dino);   // will relocate the list head;

    // generate a raft entries (a million of them)/
    char number[32];
    int i=0;
    for (;i<1000000; i++)
    {
        sprintf(number, "%d", i);
        list_append(&listp, number);
    }

    // now test freeing the entire list.
    list_free(&listp);

    return 0;
}