Tommy is designed to fulfill the need of 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 over the implicit order defined by the data structures. To iterate on elements you must insert them also into a tommy_list, and use the list as iterator. See the Tommy Multi Indexing example for more details. Note that this is a real limitation only for tommy_trie, as it's the only data structure defining an useable order.
Tommy doesn't provide an error reporting mechanism for a malloc() failure. You have to provide it redefining malloc() if you expect it to fail.
Tommy assumes to never have more than 2^32-1 elements in a container.
Finding the right balance between efficency and easy to use required some comprimises. Most of them are on memory efficency, and were done to avoid to cripple 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 at 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 of 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 requires to manage the special terminating case when adding or removing elements.