home  /   who am i  /   my work  /   soap box

c container library


The latest version of the c container library (libcontainer) can be downloaded below.  Building and installation instructions can be found in the source's README file.

Description Version Last change Download
Source v1.01 October 14, 2013 Tarball / Zip / GitHub


1. Overview

The C container library (libcontainer) implements generic containers without the preprocessor hacks commonly seen in such attempts.  This was accomplished by using the lesser-known container_of macro.  It is easiest to demonstrate the benefits of such an approach through an example snippet.

struct my_element
    int my_element_data;

    /* Placement of container-specific node data can be easily modified for locality
       optimization */
    struct container__slist_node slist_node;

    /* A single element can be linked into multiple containers */
    struct container__hash_node hash_node;

InsertElement (...)
    struct my_element* el;

    /* Allocate elements using any mechanism desired */
    el = malloc(sizeof(struct my_element));

    el->my_element_data = 42;

    /* Perform locking only during the insertion, allowing potentially costly allocations and
       initializations to occur outside the lock */

    Container_AddSListHead(&el->slist_node, &my_slist);


    /* Easily allow external libraries to operate on the container */
    ExternalLibUpdate(&el->hash_node, &my_hash);

Implementations for singly linked list, queues, circular linked lists, hash maps, binary search trees, balances, and stack tracking are available.  Documentation for each of these containers can be found below.

2. Documentation

Documentation for each container can be found in the related header file.  Simple example programs can also be found for each container type.

2.1. Singly linked list

Name slist
Description A linked list implementation where each node contains only a next pointer and elements may only be inserted at the head.  Elements may only be removed from the head
Header & Documentation container/slist.h
Example ex_slist.c

2.2. Queue

Name queue
Description A singly linked list that allows for insertion at both the head and tail.  Elements may only be removed from the head
Header & Documentation container/queue.h
Example ex_queue.c

2.3. Circular Linked List

Name clist
Description A double linked list that allows for insertion and removal at any point within the list
Header & Documentation container/clist.h
Example ex_clist.c

2.4. Hash Map

Name hash
Description A hash map implementation that allows for storage and subsequent lookups of elements by a specified key
Header & Documentation container/hash.h
Example ex_hash.c

2.5. Binary Search Tree

Name bst
Description A basic binary search tree implementation that allows for storage and lookups of elements by a specified key
Header & Documentation container/bst.h
Example ex_bst.c

2.6. Balance

Name bal
Description Implements a balance, which allows for automatic arrangement of elements into buckets such that the elements are split evenly between them
Header & Documentation container/bal.h
Example ex_bal.c

2.7. Stack

Name stack
Description Implements basic stack tracking functionality
Header & Documentation container/stack.h
Example ex_stack.c

2.8. Container Utilities

Name utils
Description Implements various utilities used by the container library.  Specifically, a container_of implementation is defined here
Header & Documentation container/utils.h

3. Licensing

The C container library is licensed under the simplified BSD license:

Copyright 2012, Andrew Gottemoller
All rights reserved.

Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following conditions are met:

Redistributions of source code must retain the above copyright notice, this list of conditions and the following disclaimer.

Redistributions in binary form must reproduce the above copyright notice, this list of conditions and the following disclaimer in the documentation and/or other materials provided with the distribution.

Neither the name of Andrew Gottemoller nor the names of its contributors may be used to endorse or promote products derived from this software without specific prior written permission.

4. Alternative Licensing

A special license for the C container library is available if you are unable to meet the conditions of the license described above.  For more information, please contact me.