Tommy is a C library of array, hashtables and tries data structures, designed for high performance and providing an easy to use interface.
It's faster than all the similar libraries like rbtree, judy, googlebtree, stxbtree, khash, uthash, nedtrie, judyarray, concurrencykit and others. Only googledensehash is a real competitor for Tommy.
The data structures provided are:
The most interesting are tommy_array, tommy_hashdyn, tommy_hashlin, tommy_trie and tommy_trie_inplace.
The official site of TommyDS is http://www.tommyds.it/,
All the Tommy containers are used to store pointers to generic objects, associated to an integer value, that could be a key or a hash value.
They are semantically equivalent at the C++ multimap<unsigned,void*> and unordered_multimap<unsigned,void*>.
An object, to be inserted in a container, should contain a node of type tommy_node. Inside this node is present a pointer to the object itself in the tommy_node::data field, the key used to identify the object in the tommy_node::key field, and other fields used by the containers.
This is a typical object declaration:
To insert an object in a container, you have to provide the address of the embedded node, the address of the object and the value of the key.
To search an object you have to provide the key and call the search function.
To access all the objects with the same keys you have to iterate over the bucket assigned at the specified key.
To remove an object you have to provide the key and call the remove function.
Dealing with hashtables, instead of the key, you have to provide the hash value of the object, and a compare function able to differentiate objects with the same hash value. To compute the hash value, you can use the generic tommy_hash_u32() function, or the specialized integer hash function tommy_inthash_u32().
Tommy is fast and easy to use.
Tommy is portable to all platforms and operating systems.
Tommy containers support multiple elements with the same key.
Tommy containers keep the original insertion order of elements with equal keys.
Tommy is released with the 2-clause BSD license.
See the Tommy Design page for more details and limitations.
Here you can see some timings comparing with other notable implementations. The Hit graph shows the time required for searching random objects with a key. The Change graph shows the time required for searching, removing and reinsert random objects with a different key value.
Times are expressed in nanoseconds for each element, and lower is better.
To have some reference numbers, you can check Latency numbers every programmer should know.
A complete analysis is available in the Tommy Benchmarks page.