Tommy

Introduction

Tommy is a C library of array, hashtable and trie data structures, designed for high performance and providing an easy-to-use interface.

It's faster than all the similar libraries like rbtree, nedtrie, khash, uthash, judy, judyarray, googledensehash, googlebtree, stxbtree, tesseract, libdynamic, concurrencykit and others.

The data structures provided are:

• tommy_list - A double linked list.
• tommy_array, tommy_arrayof - A linear array. It doesn't fragment the heap.
• tommy_arrayblk, tommy_arrayblkof - A blocked linear array. It doesn't fragment the heap and it minimizes space occupation.
• tommy_hashtable - A fixed-size chained hashtable.
• tommy_hashdyn - A dynamic chained hashtable.
• tommy_hashlin - A linear chained hashtable. It doesn't have the problem of the delay when resizing and it doesn't fragment the heap.
• tommy_trie - A trie optimized for cache utilization.
• tommy_trie_inplace - A trie completely inplace.
• tommy_tree - A tree to keep elements in order.

The most interesting are tommy_array, tommy_hashdyn, tommy_hashlin, tommy_trie and tommy_trie_inplace.

The official site of TommyDS is https://www.tommyds.it/.

Use

All the Tommy containers are used to store pointers to generic objects, associated with an integer value, that could be a key or a hash value.

They are semantically equivalent to the C++ multimap<unsigned,void*> and unordered_multimap<unsigned,void*>.

An object, to be inserted into 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:

struct object {
    // other fields
    tommy_node node;
};

To insert an object into a container, you have to provide the address of the embedded node, the address of the object and the value of the key.

int key_to_insert = 1;
struct object* obj = malloc(sizeof(struct object));
...
tommy_trie_insert(..., &obj->node, obj, key_to_insert);

To search for an object you have to provide the key and call the search function.

int key_to_find = 1;
struct object* obj = tommy_trie_search(..., key_to_find);
if (obj) {
    // found
}

To access all the objects with the same key, you have to iterate over the bucket assigned at the specified key.

int key_to_find = 1;
tommy_trie_node* i = tommy_trie_bucket(..., key_to_find);
 
while (i) {
    struct object* obj = i->data; // gets the object pointer
 
    printf("%d\n", obj->value); // process the object
 
    i = i->next; // goes to the next element
}

To remove an object you have to provide the key and call the remove function.

int key_to_remove = 1;
struct object* obj = tommy_trie_remove(..., key_to_remove);
if (obj) {
    // found
    free(obj); // frees the allocated object memory
}

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().

Features

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.

Performance

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 reinserting 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.