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 must always provide thread safety using locks before calling any Tommy functions.
Tommy does not provide a uniform iterator interface across all containers. While individual containers provide callback-based traversal (foreach) and explicit bidirectional iteration using dedicated node functions (head(), tail(), next(), and prev() in lists, trees, tries, and hashtables, or index-based access in arrays), each container uses its own API rather than a unified iterator abstraction. Furthermore, associative containers iterate in their internal or sorted order rather than global insertion order. To iterate over elements with an explicit loop while preserving global insertion order, you can insert elements also into a tommy_list and use the list as an iterator. See the Multi-Indexing: Searching Elements in Multiple Ways example for more details.
Tommy assumes memory allocation is infallible and does not provide an error reporting mechanism for allocation failures. See Infallible memory allocation for the rationale, advantages, and trade-offs of this decision.
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.
Tommy assumes that dynamic memory allocation never fails. Container operations do not check for allocation failures and do not return error codes on out-of-memory conditions.
Handling allocation failures across every container operation would introduce branching overhead and require complex rollback logic when dynamic resizing fails halfway through. On modern 64-bit operating systems with virtual memory overcommit (such as Linux) and swap, memory exhaustion is either handled by the kernel OOM killer or results in system thrashing, making userspace null checks ineffective.
In environments where allocation failures must be intercepted (such as embedded systems or monitored services), Tommy allows redefining tommy_malloc(), tommy_calloc(), tommy_realloc(), and tommy_free() with custom wrappers that can log diagnostics and abort or perform an unwinding non-local exit.
All the Tommy associative containers (hashtables, tries and trees) 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.
Each node explicitly stores a pointer to the enclosing element (tommy_node::data, tommy_trie_inplace_node::data, and tommy_tree_node::data) to allow search, traversal, and removal functions to access or return directly a pointer to the element stored in the container.
A more memory-conservative alternative is to require the user to compute the element pointer from the embedded node with a fixed displacement, as done in the Linux Kernel declaration of container_of().
Tommy deliberately trades one pointer of storage (sizeof(void*)) per node to obtain significant advantages in usability, safety, and API cleanliness:
In associative containers, the list used for collisions is doubly-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 singly-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 a list or over elements in the same collision 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.