And templates for all ! Template containers (lists, sets and maps) for C language (why not ?).
(c) 2017 Laurent Farhi (lrspam at sfr.fr).
Dreaming of templates for C, such as
LIST (int) * mylist = LIST_CREATE (int);
LIST_APPEND (mylist, 2);
LIST_APPEND (mylist, 1);
LIST_SORT (mylist);?
Make your dream come true, read on !
This project is about turning theoretical ideas of Randy Gaul on his excellent blog into operational template containers.
Templates are about generating code at compile time. Languages such as C++ offer a powerful framework for template programming and usage.
Nevertheless, templates do not require runtime polymorphism, and can be implemented in C language. As such, Randy Gaul has demonstrated in 2012 [1] that the C macro preprocessor permits to implement a template mechanism in C.
The idea here is to exploit this feature to create template collections such as lists, sets and maps.
The solution is a combination of several techniques:
- macros to generate collection for any type and structure
- virtual tables to implement static polymorphism
- binary tree structure and operations
- function overloading on number of arguments (but not type though)
Let me know if you encounter any bug, or have any comment or suggestion.
Prior to any usage of template collections, header files should be included in source files :
#include "defops.h"#include "list_impl.h",#include "set_impl.h"or#include "map_impl.h"whether lists, sets or maps will be used.
Once header files are included, the template have to be instanciated for each type to be used in collections.
Templates are declared in global scope by:
DECLARE_LIST (type);
DECLARE_SET (type);
DECLARE_MAP (key_type, value_type);
For each type, some helpers have to be defined to allow declaration of copy constructors, destructors and inequality operator <.
This is done in global scope by:
DEFINE_OPERATORS (type);
Templates are defined in global scope by:
DEFINE_LIST (type);
DEFINE_SET (type);
DEFINE_MAP (key_type, value_type);
If collections are intended to be used in a library,
- the library header file should include files defining the interface of template :
#include "list.h",#include "set.h"or#include "map.h"whether lists, sets or maps will be used. - Declarations of templates should appear in the library header file.
- Definitions of operators and templates should appear in library source file.
Three common types of containers are provided: lists, sets and maps.
This container represents a strongly typed list of objects that can be accessed by index.
The type of a list is LIST(T), where T denotes the type contained in the list.
This type is noted as L below.
Elements are place-holders of values of type T. Thoses elements allow to navigate through the container.
The type of the elements of a list is LNODE(T).
This type is noted as N below.
Dereferences the value of the element n. The returned value should not be freed by the caller.
Modifies the value hold be the element n with the value v.. A copy of v is assigned to the element.
Returns a pointer to the next element in the list or LIST_END(L). Complexity: O(log N)
Returns a pointer to the previous elemnt in the list or LIST_END(L). Complexity: O(log N)
Description: Desallocate all elements in the list and desallocate the list. The destructor of type T is called for each element of the list. The list must not be used afterwards.
Description: Inserts an element containing the value v before the element n where n is an element of the list l or LIST_END(l). The new element is inserted at the end of the list if n is equal to LIST_END(l).
Errors: EINVAL if n is not LIST_END(l) and is not an element of the list l. ENOMEM in case of memory allocation error.
Description: Inserts an element containing the value v at the end of the list. Behaves as well as LIST_INSERT(l, LIST_END(l), v)
Description: Removes the element n from the list l. The value hold by the eleemnt is destroyed. n should not be dereferenced afterwards.
Description: Desallocate all elements in the list. The destructor of type T is called for each element of the list. The list can still be used afterwards.
Arguments param and until are optional. Default values are respectively l and EXIT_FAILURE.
Description: Applies a function callback to every element of the list sequentially, from beginning to end, until callback returns until. callback is called with element as the first argument. param is oassed as the second argument to each call of callback.
Arguments param, until, begin and end are optional. Default values are respectively l, EXIT_FAILURE, LIST_BEGIN(l) and LIST_END(l).
Description: Applies a function callback to every element of the list sequentially, from begin (included) to end (excluded), until callback returns until. Elements are passed sequentially as the first argument of callback. param is oassed as the second argument to each call of callback.
Arguments op and begin are optionnal. Default values are respectively the default less than operator and LIST_BEGIN(l).
Description: Finds the first element n in list l after element begin (included) which holds a value equal to v, that is for which op(value of n, v) and op(v, value of n) return 0.
- return 0 if the two values are equal, 1 otherwise ;
- return 1 if
ais strictly less thanb, 0 otherwise.
Return value: The first element n in list l after element begin (included) which holds a value equal to v, that is for which op(value of n, v) and op(v, value of n) return 0, or LIST_END(l) if no occurrence were found.
Errors: EINVAL if herefrom does not belong to the list from or if hereto is not LIST_END(to) and is not an element of the list to.
Description: Reverses the order of the elements of the list l. If begin and end are specified, only the elements between begin (included) and end (excluded) are reversed.
Description: Rotates all the elements of the list one position to the left (LIST_ROTATE_LEFT) or to the right (LIST_ROTATE_RIGHT).
Description: Sorts the elements of the list in ascending order with respect to the less than operator lt.
Note: lt(T a, T b) should return 1 if a is strictly less than b, 0 otherwise. If lt is not specified, the standard less than operator is used.
Description: Removes all but one adjacent matching elements (which values are equal with respect to op) from list l. Only the first occurrence is kept in the list.
- return 0 if the two values are equal, 1 otherwise ;
- return 1 if
ais strictly less thanb, 0 otherwise.
If op is not specified, the standard less than operator is used.
typedef char *T;
DECLARE_LIST (T);
DEFINE_OPERATORS (T);
DEFINE_LIST (T);
int main (void)
{
LIST (T) * mylist = LIST_CREATE (T);
LIST_APPEND (mylist, "A");
LIST_INSERT (mylist, LIST_LAST (mylist), "aaa");
LIST_INSERT (mylist, LIST_BEGIN (mylist), "bbbb");
LIST_INSERT (mylist, 1), "f");
LIST_SORT (mylist);
LIST_REVERSE (mylist);
LNODE_ASSIGN (LIST_BEGIN (mylist), "zzzz");
LIST_DESTROY (mylist);
}Look at a complete example.
This container represents a collection of objects that is maintained in sorted order.
The type of a set is SET(K), where K denotes the type contained in the set.
This type is noted as S below.
Sets can either contain unique elements or not, depending on the third parameters passed at creation (SET_CREATE).
Elements are place-holders of values of type K. Thoses elements allow to navigate through the container.
The type of the elements of a set is SNODE(K)
This type is noted as N below.
Dereferences the value of the element n. The returned value should not be freed by the caller.
Returns a pointer to the next element in the list or SET_END(L). Complexity: O(log N)
Returns a pointer to the previous elemnt in the list or SET_END(L). Complexity: O(log N)
Parameters between square bracket are optional.
Description: Desallocates all elements in the set and desallocates the set. The destructor of type K is called for each element of the set. The set must not be used afterwards.
Note: No insertion is performed if an element with the same value is already in the set, and unicity is required.
Description: Removes the element n from the set s. The value hold by the eleemnt is destroyed. n should not be dereferenced afterwards.
Description: Desallocates all elements in the set. The destructor of type K is called for each element of the set. The set can still be used afterwards.
Arguments param and until are optional. Default values are respectively s and EXIT_FAILURE.
Description: Applies a function callback to every element of the set sequentially, from beginning to end, until callback returns until. callback is called with element as the first argument. param is passed as the second argument to each call of callback.
Arguments param, until, begin and end are optional. Default values are respectively s, EXIT_FAILURE, SET_BEGIN(s) and SET_END(s).
Description: Applies a function callback to every element of the set sequentially, from begin (included) to end (excluded), until callback returns until. callback is called with element as the first argument of callback. param is passed as the second argument to each call of callback.
The second argument is optional.
typedef char *T;
DECLARE_SET (T);
DEFINE_OPERATORS (T);
DEFINE_SET (T);
int main (void)
{
SET (T) * myset = SET_CREATE (T);
SET_INSERT (myset, "b");
SET_INSERT (myset, "c");
SET_INSERT (myset, "a");
SET_DESTROY (myset);
}Look at a complete example.
This container represents a collection of pairs of keys and values that is maintained in sorted order of keys.
The type of a map is MAP(K, T), where K denotes the key type contained in the map, and T the value type assiciated to the keys.
This type is noted as M below.
Maps can either contain unique elements or not, depending on the third parameters passed at creation (MAP_CREATE).
Elements are place-holders of pairs (key, value) of type (K, T). Thoses elements allow to navigate through the container.
The type of the elements of a map is BNODE(K, T)
This type is noted as N below.
Dereferences the key of the element n. The returned value should not be freed by the caller.
Dereferences the value of the element n. The returned value should not be freed by the caller.
Modifies the value hold be the element n with the value v.. A copy of v is assigned to the element.
Returns a pointer to the next element in the list or MAP_END(L). Complexity: O(log N)
Returns a pointer to the previous elemnt in the list or MAP_END(L). Complexity: O(log N)
Parameters between square bracket are optional.
Description: Creates a new map of pairs (K, T). This map must be destroyed by MAP_DESTROY after usage.
Description: Desallocates all elements in the map and desallocates the map. The destructor of types K and T are called for each element of the map
Note: No insertion is performed if an element with the same key is already in the map, and unicity is required.
Description: Modifies the value associated with the key k in the map : the associated value is set to the value v.
Note: An element is inserted if no element with the same key is already in the map, or if unicity is not required.
Description: Removes the element n from the map m. The pair hold by the element is destroyed. n should not be dereferenced afterwards.
Description: Desallocates all elements in the map. The destructors of types K and T are called for each element of the map. The map can still be used afterwards.
Arguments param and until are optional. Default values are respectively m and EXIT_FAILURE.
Description: Applies a function callback to every element of the map sequentially, from beginning to end, until callback returns until. callback is called with element as the first argument. param is passed as the second argument to each call of callback.
Arguments param, until, begin and end are optional. Default values are respectively m, EXIT_FAILURE, MAP_BEGIN(m) and MAP_END(m).
Description: Applies a function callback to every element of the map sequentially, from begin (included) to end (excluded), until callback returns until. callback is called with element as the first argument of callback. param is passed as the second argument to each call of callback.
The second argument is optional.
The second argument is optional.
Note: If no operator is specified for the map m, the operator attached to type T is used, or the default less than operator for type T.
typedef struct
{
int l, w, h;
} Dimensions;
DEFINE_OPERATORS (pchar);
DEFINE_OPERATORS (Dimensions);
DECLARE_MAP (pchar, Dimensions);
DEFINE_MAP (pchar, Dimensions);
static int
print_car (BNODE (pchar, Dimensions) * car, void *arg)
{
(void) arg;
printf ("%s (%d, %d, %d)\n", *BNODE_KEY (car), BNODE_VALUE (car)->l, BNODE_VALUE (car)->w, BNODE_VALUE (car)->h);
return EXIT_SUCCESS;
}
int
main (void)
{
MAP (pchar, Dimensions) * cars = MAP_CREATE (pchar, Dimensions);
Dimensions rt = {.l = 3595,.w = 1647,.h = 1557 };
Dimensions cc1 = {.l = 3466,.w = 1615,.h = 1460 };
Dimensions p108 = {.l = 3475,.w = 1615,.h = 1460 };
MAP_INSERT (cars, "Renault Twingo", cc1); // Inserts and sets value
MAP_SET_VALUE (cars, "Renault Twingo", rt); // Does not insert but sets value
MAP_SET_VALUE (cars, "Citroën C1", cc1); // Inserts and sets value
MAP_INSERT (cars, "Citroën C1", rt); // Does neither insert nor modify value
MAP_SET_VALUE (cars, "Peugeot 108", cc1); // Inserts and sets value
MAP_SET_VALUE (cars, "Peugeot 108", p108); // Does not insert but sets value
MAP (pchar, Dimensions) * fiat = MAP_CREATE (pchar, Dimensions);
Dimensions mini3 = {.l = 3821,.w = 1727,.h = 1415 };
MAP_SET_VALUE (fiat, "Mini Cooper", mini3);
Dimensions f500 = {.l = 3546,.w = 1627,.h = 1488 };
MAP_SET_VALUE (fiat, "Fiat 500", f500);
MAP_MOVE (cars, fiat, MAP_KEY (fiat, "Fiat 500"));
MAP_REMOVE (fiat, MAP_KEY (fiat, "Mini Cooper"));
printf ("%lu elements in fiat\n", MAP_SIZE (fiat));
MAP_DESTROY (fiat);
MAP_TRAVERSE (cars, print_car);
// Find keys in the set
char *alicia[2] = { "Fiat 500", "Mini Cooper" };
for (size_t i = 0; i < sizeof (alicia) / sizeof (*alicia); i++)
if (MAP_FIND_KEY (cars, alicia[i]))
printf ("%s is in cars.\n", alicia[i]);
else
printf ("%s is NOT in cars.\n", alicia[i]);
Dimensions d = {.l = 3546,.w = 1627,.h = 1488 };
BNODE (pchar, Dimensions) * c = MAP_FIND_VALUE (cars, d);
if (c)
printf ("%s\n", *BNODE_KEY (c));
c = MAP_INDEX (cars, 1);
if (c)
printf ("%s\n", *BNODE_KEY (c));
c = MAP_LAST (cars);
if (c)
printf ("%s\n", *BNODE_KEY (c));
MAP_DESTROY (cars);
}Look at a complete example.
Collections can manage their own memory for the data held into the elements.
For basic standard types, the default copy constructor is the = operator.
For strings (char *), the default constructor is defined as strdup and the default destructor is defined as free.
For user defined types T, optional operators can be assigned to types contained into collections using:
SET_COPY_CONSTRUCTOR(T, constructor)whereconstructoris a pointer to function with typeT (*constructor) (T v)SET_DESTRUCTOR(T, destructor)wheredestructoris a pointer to function with typevoid (*destructor) (T v)
Theses operators can be reset to their default value by passing 0 to SET_DESTRUCTOR and SET_COPY_CONSTRUCTOR.
GET_DESTRUCTOR(T) and GET_COPY_CONSTRUCTOR(T) allow to return pointers to previously defined destructor and copy constructor for type T.
For convenience, COPY_CONSTRUCTOR_TYPE(T) and DESTRUCTOR_TYPE(T) are the predefined types for pointer functions to copy constructor and destructor for type T. For instance, one can thus write
COPY_CONSTRUCTOR_TYPE(T) cptor = GET_COPY_CONSTRUCTOR(T);Sets, maps as well as LIST_SORT require a strict weak ordering.
Sets, maps as well as LIST_FIND and LIST_UNIQUE require equality operator.
For basic standard types, the standard operator < is defined and used by default.
For strings (char *), a default operator is defined from strcoll.
For other types, a default less than operator is defind as a bytewise comparator (something similar to memcmp).
User defined operators can optionally replace default operators using:
SET_LESS_THAN_OPERATOR(T, operator)whereoperatoris a pointer to function with typeT (*operator) (T arg1, T arg2). This function should return 1 ifarg1<arg2, 0 otherwise.
GET_LESS_THAN_OPERATOR(T) returns the pointer to the less than operator previously defined for type T.
For convenience, LESS_THAN_OPERATOR_TYPE(T) is the predefined type for pointer function to less than operator for type T.
For sets and maps, less than operators can also be optionally specified when the collection is created (see SET_CREATE and MAP_CREATE). If not, the less than operator tied to type T will be used (either the user defined or defualt one).
For lists, a less than operator can also be specified as the optional second argument of LIST_SORT and LIST_UNIQUE. If not, the less than operator tied to type T will be used (either the user defined or defualt one).
Equality is required for key or data matching (using finctions ...FIND...) and unicity (during insertion or for LIST_UNIQUE).
Two values arg1 and arg2 are considered to be equal when neither arg1 < arg2, nor arg1 > arg2.
Internal data in lists, sets and maps are organized into self-balancing binary trees. This allows to reduce algorithmic complexity to O(log N) for most operations.
The self-balacing strategy is relaxed:
- it is applied at insertion, in order to keep the branch into which the element is inserted not longer than the sibling breanch.
- it is not applied when an element is removed. The branch where the element is removed can get shorter than its sibling branch.
This strategy garanties than the tree depth is always lower or equal to (log Nmax)/(log 2), where Nmax is the larger size of the collections.
The complexity in worst case is compared in the following table.
| List | Set | Map | |
|---|---|---|---|
| Insert | O(log N) | O(log N) | O(log N) |
| Remove | O(1) | O(1) | O(1) |
| Move | O(log N) | O(log N) | O(log N) |
| Index | O(log N) | O(log N) | O(log N) |
| Go to Previous | O(log N) | O(log N) | O(log N) |
| Go to Next | O(log N) | O(log N) | O(log N) |
| Go to begining | O(1) | O(1) | O(1) |
| Go to end | O(1) | O(1) | O(1) |
| Go to index | O(log N) | O(log N) | O(log N) |
| Search key | - | O(log N) | O(log N) |
| Search value | O(N) | - | O(N) |
| Traverse | O(N) | O(N) | O(N) |
| For_each | O(N log N) | O(N log N) | O(N log N) |
| Clear or destroy | O(N) | O(N) | O(N) |
Template declarations can not apply directly on compound types such as char *, unsigned long or struct foo.
User defined types should be used to create template collections on such compound types.
typedef unsigned long ulong;
typedef struct foo foo;
typedef char * pchar;
Evaluated variables should not be used for the first parameter of template functions.
Since mecro are extensively used, this would otherwise have unintended side effects [2] (at least as long as GNU C language extensions __auto and Statements and Declarations in Expressions are not part of the standard C language.)
Avoid
LNODE_ASSIGN(LIST_BEGIN(list), 55);
Prefer
LNODE(int) b = LIST_BEGIN(list);
LNODE_ASSIGN(b, 55);
Look at examples in directory examples.
gol.c is a naïve, slow and conventional implementation (neither pattern recognition nor time compression,
as in hashlife algorithm) of the Conway's Game Of Life using lists, sets and maps.
Lists, sets and maps functionnalities have been thoroughly tested as well as self-balancing algorithm.
valgrind has been used to check the execution of thoses tests is memory leajs free.
Look at full tests in directory test.
[1] Randy Gaul's Game Programming Blog - Generic Programming in C (http://www.randygaul.net/2012/08/10/generic-programming-in-c/)
[2] The C Preprocessor - Duplication of Side Effects (https://gcc.gnu.org/onlinedocs/cpp/Duplication-of-Side-Effects.html#Duplication-of-Side-Effects)