Data structures in C

I've always wished that the C standard library included support for common data structures (Binary Trees, Linked Lists, etc). It's unfortunate that it doesn't, but most Unix systems include a sys/queue.h which originated in BSD. This post will walk you though using it, since macros and generics programming in C can get a little confusing.

For this example I will be using TAILQs since they let you insert and remove elements at the beginning or end of the list/queue in O(1) time, however sys/queue.h also provides LIST (doubly linked list), SLIST (singly linked list), STAILQ (singly linked tail queue) - and others on some platforms.

sys/queue.h

Most if not all modern Unix systems will include a sys/queue.h of some sort. However, I suggest that you download a copy from a recent version of FreeBSD and include it in your project. The FreeBSD version is well documented and includes "SAFE" looping constructs that allow you to remove elements form the list/queue while looping over it.

simple_queue_example.c

This is a simple example of using TAILQ without any extra typedefs and all of the code in main().

// gcc simple_queue_example.c -o simple_queue_example

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "queue.h" // queue taken from FreeBSD 10

// The data type for the node
struct node
{
    char c;
    // This macro does the magic to point to other nodes
    TAILQ_ENTRY(node) nodes;
};

int main (int arc, char * argv [])
{
    // This macro creates the data type for the head of the queue
    // for nodes of type 'struct node'
    TAILQ_HEAD(head_s, node) head;
    // Initialize the head before use
    TAILQ_INIT(&head);
    char string[] = "Hello World\n";

    //
    // put some nodes in the queue
    //

    struct node * e = NULL;
    int c = 0;
    for (c = 0; c < strlen(string); ++c)
    {
        e = malloc(sizeof(struct node));
        if (e == NULL)
        {
            fprintf(stderr, "malloc failed");
            exit(EXIT_FAILURE);
        }
        e->c = string[c];
        // Actually insert the node e into the queue at the end
        TAILQ_INSERT_TAIL(&head, e, nodes);
        e = NULL;
    }

    // print the queue
    TAILQ_FOREACH(e, &head, nodes)
    {
        printf("%c", e->c);
    }

    // free the elements from the queue
    while (!TAILQ_EMPTY(&head))
    {
        e = TAILQ_FIRST(&head);
        TAILQ_REMOVE(&head, e, nodes);
        free(e);
        e = NULL;
    }

    return EXIT_SUCCESS;
}

queue_example.c

Here is a more complicated example with the typedefs and separate functions that you would expect to see in production code.

// gcc queue_example.c -o queue_example

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "queue.h" // queue taken from FreeBSD 10

// Note the standard typedef of struct node to node_t for convenient use but
// the TAILQ_ENTRY macro uses the struct name.
typedef struct node
{
    char c;
    TAILQ_ENTRY(node) nodes;
} node_t;
// This typedef creates a head_t that makes it easy for us to pass pointers to
// head_t without the compiler complaining.
typedef TAILQ_HEAD(head_s, node) head_t;

// Takes a string and puts in in the queue on character at a time.
static void _fill_queue(head_t * head, const char * string)
{
    int c = 0;
    for (c = 0; c < strlen(string); ++c)
    {
        struct node * e = malloc(sizeof(struct node));
        if (e == NULL)
        {
            fprintf(stderr, "malloc failed");
            exit(EXIT_FAILURE);
        }
        e->c = string[c];
        TAILQ_INSERT_TAIL(head, e, nodes);
        e = NULL;
    }
}

// Removes all of the elements from the queue before free()ing them.
static void _free_queue(head_t * head)
{
    struct node * e = NULL;
    while (!TAILQ_EMPTY(head))
    {
        e = TAILQ_FIRST(head);
        TAILQ_REMOVE(head, e, nodes);
        free(e);
        e = NULL;
    }
}

// Prints the queue by traversing the queue forwards.
static void _print_queue(head_t * head)
{
    struct node * e = NULL;
    TAILQ_FOREACH(e, head, nodes)
    {
        printf("%c", e->c);
    }
}

// Prints the queue while traversing the queue backwards.
static void _print_queue_backwards(head_t * head)
{
    struct node * e = NULL;
    TAILQ_FOREACH_REVERSE(e, head, head_s, nodes)
    {
        printf("%c", e->c);
    }
}

// Safely removes the vowels from the queue
static void _remove_vowels(head_t * head)
{
    struct node * e = NULL;
    struct node * next = NULL;
    TAILQ_FOREACH_SAFE(e, head, nodes, next)
    {
        if (e->c == 'a' || e->c == 'A' || e->c == 'e' || e->c == 'E' ||
            e->c == 'i' || e->c == 'I' || e->c == 'o' || e->c == 'O' ||
            e->c == 'u' || e->c == 'U')
        {
            TAILQ_REMOVE(head, e, nodes);
            free(e);
            e = NULL;
        }
    }
}

int main (int arc, char * argv [])
{
    // declare the head
    head_t head;
    TAILQ_INIT(&head); // initialize the head

    // fill the queue with "Hello World\n"
    _fill_queue(&head, "Hello World!\n");

    printf("Forwards: ");
    _print_queue(&head); // prints "Hello World!\n"
    printf("Backwards: ");
    _print_queue_backwards(&head); // prints "\n!dlroW olleH"

    // remove the vowels from the queue
    _remove_vowels(&head);
    printf("\nForwards, vowels removed: ");
    _print_queue(&head); // prints "Hll Wrld!\n"

    // free the queue
    _free_queue(&head);
    _print_queue(&head); // prints ""

    return EXIT_SUCCESS;
}

Link to code repository

All of the code listed here is checked into github if you want to grab it that way.