Tommy is designed to fulfill the need for generic data structures for the C language, providing at the same time high performance and a clean and easy-to-use interface.
Extensive and automated tests with the runtime checker valgrind and the static analyzer clang are done to ensure the correctness of the library.
The test has a code coverage of 100%, measured with lcov.
Tommy is not thread-safe. You have always to provide thread safety using locks before calling any Tommy functions.
Tommy doesn't provide iterators for elements stored in a container. To iterate on elements you must insert them also into a tommy_list, and use the list as an iterator. See the Multi-Indexing: Searching Objects in Multiple Ways example for more details.
Tommy doesn't provide an error reporting mechanism for a malloc() failure. You have to provide it by redefining malloc() if you expect it to fail.
Finding the right balance between efficiency and ease of use required some compromises. Most of them are on memory efficiency, and were done to avoid crippling the interface.
The following is a list of such decisions.
All the Tommy containers support the insertion of multiple elements with the same key, adding in each node a list of equal elements.
They are the equivalent of the C++ associative containers multimap<unsigned,void*> and unordered_multimap<unsigned,void*> that allow duplicates of the same key.
A more memory-conservative approach is to not allow duplicated elements, removing the need for this list.
The tommy_node::data field is present to allow search and remove functions to return directly a pointer to the element stored in the container.
A more memory-conservative approach is to require the user to compute the element pointer from the embedded node with a fixed displacement. For an example, see the Linux Kernel declaration of container_of().
The list used for collisions is double-linked to allow insertion of elements at the end of the list to keep the insertion order of equal elements.
A more memory-conservative approach is to use a single-linked list, inserting elements only at the start of the list, losing the original insertion order.
The 0-terminated format of tommy_node::next is present to provide a forward iterator terminating in 0. This allows the user to write a simple iteration loop over the list of elements in the same bucket.
A more efficient approach is to use a circular list, because operating on nodes in a circular list doesn't require managing the special terminating case when adding or removing elements.