Limitless Containers without dynamic memory allocation in C/C++.

Lists, FIFOs, dictionaries, maps, etc. are handy-dandy data structures when designing and implementing code. However, most container implementations either use dynamic memory allocation or have a fixed number of elements they can contain.

Because my day job is as an embedded developer, I typically do not get to use the heap (aka dynamic memory) after the application start-up logic has completed. So that leaves me with using containers that have fixed limits on the number of elements they can contain. The problem here is how to go about setting the limit. While the amount of RAM available in todays’ microcontrollers is constantly increasing, it is still limited, i.e. there are always trade-offs being made with respect RAM usage. Using an arbitrarily high limit that would never be exceeded at run time is not an option. That leaves setting the limit at something the fits within the RAM budget – but it also means that runtime checks are needed for when a container is out-of-memory. Sometimes this can be handled relatively painlessly, but not always. For example, when using a FIFO for an event queue and the FIFO memory is exhausted, the choices for handling the out-of-memory condition are:

Ignore the new event (or overwrite that last queued event, etc.) – basically lose a event.
Or, block/busy-wait until the normal course of event processing removes an event from the queue thus making room for the new event. Since event queues are typically used as a mechanism for asynchronous communication, blocking/busy-waiting is bad thing in this scenario.

What is needed are containers that have no arbitrary limit to the number of elements they can contain and does not require dynamic memory allocation.

Intrusive Containers

Intrusive containers are where the items being stored contained the necessary metadata/memory need to be an element of the container. Let’s take a step back and review how a non-intrusive (a.k.a. using dynamic memory) doubly linked list works.

A doubly linked list consists of elements where each elements contains next and previous pointers to other elements and a pointer to the item’s data. The next and previous pointers are metadata/memory required by the list to store an item in the list. Example:

struct Item { 
   int apple; 
   int orange; 
};  

struct Element { 
   Element* next; 
   Element* prev; 
   Item*    data; 
};

When the application wants to add an Item instance the list, it provides the list with a pointer/reference to the instance. The list then allocates memory for an Element, sets the .data field to point to the Item instance, and then inserts the Element instance into its linked-list structure. When the Element is removed from the list, the Element instance is freed.

A doubly linked list using intrusive listing would use the following structure for Item

struct Item { 
   Item* next; 
   Item* prev; 
   int   apple; 
   int   orange; 
};

When the application wants to add an Item instance the list, it provides the list with a pointer/reference to the instance. The list then inserts the Item instance into its linked-list structure. That’s it, no memory allocations or freeing required. It also means there is no limit to the number of Items that can be stored in the container, i.e. if the Item exists – it will fit in the container.

Fine Print

Intrusive containers meet my embedded requirements, but as always, there are trade-offs. Intrusive containers have the following constraints

Items have to be built from the ground up for being stored in a container. Yes, a data structure or class can be retrofitted after the fact. Typically, this is not a problem, but sometime its can be problematic. For example, when the Item in question is from a third party package.

A given Item can only be in one container at any given time. Once again this is usually not a problem, but not always. For example, in my Colony.Core C++ library its Data Model framework contains a sorted list of all model points using intrusive listing. If the application wants its own list of model points (e.g. all model points of interest to sub-system X), then a wrapper class must be created and instances of the wrapper class are stored in the second list.

It is up to the application to enforce the constraint of an item can only be in one container. If an item does get inserted into two containers at the same time – it corrupts both containers. However, corruption does not cause a crash – it causes the two containers to have their elements crossed-link. This condition can be very difficult to find/troubleshoot. The intrusive container implementation in the Colony.Core C++ library checks for this condition and throws a fatal error if it occurs, i.e. the offending code can be found be setting a break point in the fatal error handler and walking the stack trace.

Implementation

As hinted above, the Colony.Core C++ library has an implementation for intrusive containers. It supports the following containers. In addition, all of the containers are type-safe.

Singly linked ordered list
Doubly linked ordered list
Map (sorted list)
Dictionary (aka hash table)

To make a class an ‘listable’ Item, you simply have your class inherit from an Item class. There are several Item classes so that if all you need is a FIFO – your Items only inherit the metadata footprint for singly linked list vs the metadata required for a sorted list.

// MyClass1 can be stored in Cpl::Container::SList container
class MyClass1: public Cpl::Container::Item
{
…
};

// MyClass2 can be stored in Cpl::Container::Map container 
// (as well as Dictionary, DList, and SList containers).
class MyClass2: public Cpl::Container::MapItem
{
…
};

There is also C only implementation for singly and doubled linked ordered lists. This is a recent addition to the Colony.Core repository. But since I work on a lot of C only projects I wanted a C based reference implementation. Be warned: The C implementation is not as elegant as the C++ code and is not type-safe.

Patterns in the Machine