Tommy Documentation

Introduction

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:

• 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 the 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 http://www.tommyds.it/,

Use

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:

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

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.

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

To search 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 keys 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 object allocated 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 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.