Generic Containers¶

Included Implementations¶

The following types are supported:-

int
double
char *
void *

The following containers are implemented for all the supported types:-

list
vector
map
queue
stack

Note that for maps the supported types are provided for values but char * is the only supported key type.

This set of implementations should cover most scenarios. Using void * you could cast to any complex type rather than generating a type safe collection. If you require map keys other than char * you will need to generate.

The generated function names follow the type. For char * assume ‘str’ and for void * assume ‘ptr’, EG:-

#include "list-str.h"
#include "queue-ptr.h"

LIST_STR names = list_str_create(mem);
QUEUE_PTR process_q = queue_ptr_create(mem);

Container Interface¶

The interfaces for each generic container type share many common functions. Although not all containers support every function, there is a common subset.

Different container implementations will have different characteristics. Some operations that are fast in one implementation may be extremely slow in another. You should choose the most appropriate container for the specific needs of your program feature. A full discussion of this is beyond the scope of this manual, so if you have any doubts you should research the relative merits of lists, vectors and maps.

Supported operations:-

Construction - create, from_array.
Access - get, set (by key or index).
Management - append, insert, remove, replace.
Iteration - first, next.
Searching - find.
Filtering - where.
Informational - count.
Conversion - to_array.

Construction¶

There are two methods of construction. As a new container or a conversion from an existing array. Both require a memory scope to use for memory allocation.

void *mem = sm_create(1024);

/* New container */
CONTAINER c = container_create(mem);

/* Conversion from array */
T item[] = { x, y, z };
CONTAINER c = container_from_array(mem, item, ARRAYLEN(item));

Access¶

To access a contained element at an index use:-

TYPE element = container_get(c, index);
container_set(c, index, element);

Note that for list and vectors the index is an int and for maps the index is a key of the key type, which may or may not be an int.

Management¶

To add and remove elements use:-

container_add(c, index, element);
container_append(c, element);
container_remove(c, index, element);
container_clear(c);

For vectors and list the index is the insertion point (before) or removal point. For maps the index is the key and the function will return zero (FALSE) if the element exists on add or does not exist on removal. Use container_get() to modify an existing element.

The container_clear() function removes all elements but is available for lists and vectors only.

Note that append() is not available for maps, as it is meaningless.

Iteration¶

To iterate a container use:-

TYPE element = container_first(c, x); /* Returns x if at end */
TYPE element = container_next(c, x);  /* Returns x if at end */

/* Example loop */
for(TYPE element = container_first(c, NULL);
                element; element = container_next(c, NULL))
{
    /* Do something with element */
}

/* Or, if you prefer... */
TYPE element = container_first(c, NULL);
while(element != NULL)
{
    /* Do something with element */

    element = container_next(c, NULL);
}

These are extremely common patterns and worth memorizing. It is also common to use NULL as the sentinel for end of set. However, if NULL happens to be a valid value for your set you can choose a different value. If you want to iterate you must reserve an unused value to indicate end of set.

You may iterate a map but the order will be random.

Searching¶

To find an element using a compare function:

/* Returns defval if not found */
TYPE element = container_find(c, defval, cmp_name);

Note the generic compare functions have the correct signature, and floating point types carry the usual caveat regarding approximation of near identical values.

Filtering¶

To filter a container use the where method:

/* Returns zero if not found */
CONTAINER new_container = container_where(c, cmp, arg);

A new container is returned with only the elements that returned TRUE when compared with arg.

Note the generic compare functions have the correct signature, and doubles carry the usual caveat regarding approximation of near identical values.

Information¶

To find the number of elements in a container:

size_t count = container_count(c);

Some containers, such as lists may actually count the items, so take care using.

Conversion¶

To extract a container to a simple array use the to_array method:

/* Returns zero if not found */
T *array = container_to_array(c, not_found);

An array is returned with a terminating element, the value of which is the value of the second parameter passed in. Usually this is NULL or 0, but can be any value you wish. You can query the container using count to determine the number of elements there will be in the array.

Note the array is allocated using the container memory scope, and will be freed when that is freed.