tommytrie.h File Reference

Trie optimized for cache utilization. More...

Go to the source code of this file.

Data Structures
struct	tommy_trie_struct
	Trie container type. More...

Macros
#define	TOMMY_TRIE_BIT   32
	Number of bits of the elements to store in the trie. More...
#define	TOMMY_TRIE_TREE_MAX   (64 / sizeof(void*))
	Number of branches on each inner node. More...
#define	TOMMY_TRIE_BLOCK_SIZE   (TOMMY_TRIE_TREE_MAX * sizeof(void*))
	Trie block size. More...

Typedefs
typedef tommy_node	tommy_trie_node
	Trie node. More...
typedef struct tommy_trie_struct	tommy_trie
	Trie container type. More...

Functions
TOMMY_API void	tommy_trie_init (tommy_trie *trie, tommy_allocator *alloc)
	Initializes the trie. More...
TOMMY_API void	tommy_trie_insert (tommy_trie *trie, tommy_trie_node *node, void *data, tommy_key_t key)
	Inserts an element in the trie. More...
TOMMY_API void *	tommy_trie_remove (tommy_trie *trie, tommy_key_t key)
	Searches and removes the first element with the specified key. More...
TOMMY_API tommy_trie_node *	tommy_trie_bucket (tommy_trie *trie, tommy_key_t key)
	Gets the bucket of the specified key. More...
void *	tommy_trie_search (tommy_trie *trie, tommy_key_t key)
	Searches an element in the trie. More...
TOMMY_API void *	tommy_trie_remove_existing (tommy_trie *trie, tommy_trie_node *node)
	Removes an element from the trie. More...
tommy_size_t	tommy_trie_count (tommy_trie *trie)
	Gets the number of elements. More...
TOMMY_API tommy_size_t	tommy_trie_memory_usage (tommy_trie *trie)
	Gets the size of allocated memory. More...

Detailed Description

Trie optimized for cache utilization.

This trie is a standard implementation that stores elements in the order defined by the key.

It needs an external allocator for the inner nodes in the trie.

You can control the number of branches of each node using the TOMMY_TRIE_TREE_MAX define. More branches imply more speed, but a bigger memory occupation.

Compared to tommy_trie_inplace you have to provide a tommy_allocator allocator. Note that the C malloc() is too slow to fulfill this role.

To initialize the trie you have to call tommy_allocator_init() to initialize the allocator, and tommy_trie_init() for the trie.

tommy_allocator alloc;
tommy_trie trie;
 
tommy_allocator_init(&alloc, TOMMY_TRIE_BLOCK_SIZE, TOMMY_TRIE_BLOCK_SIZE);
 
tommy_trie_init(&trie, &alloc);

To insert elements in the trie you have to call tommy_trie_insert() for each element. In the insertion call you have to specify the address of the node, the address of the object, and the key value to use. The address of the object is used to initialize the tommy_node::data field of the node, and the key to initialize the tommy_node::key field.

struct object {
    int value;
    // other fields
    tommy_node node;
};
 
struct object* obj = malloc(sizeof(struct object)); // creates the object
 
obj->value = ...; // initializes the object
 
tommy_trie_insert(&trie, &obj->node, obj, obj->value); // inserts the object

To find an element in the trie you have to call tommy_trie_search() providing the key to search.

int value_to_find = 1;
struct object* obj = tommy_trie_search(&trie, value_to_find);
if (!obj) {
    // not found
} else {
    // found
}

To iterate over all the elements in the trie with the same key, you have to use tommy_trie_bucket() and follow the tommy_node::next pointer until NULL.

int value_to_find = 1;
tommy_node* i = tommy_trie_bucket(&trie, value_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 element from the trie you have to call tommy_trie_remove() providing the key to search and remove.

struct object* obj = tommy_trie_remove(&trie, value_to_remove);
if (obj) {
    free(obj); // frees the object allocated memory
}

To destroy the trie you have to remove all the elements, and deinitialize the allocator using tommy_allocator_done().

tommy_allocator_done(&alloc);

Note that you cannot iterate over all the elements in the trie using the trie itself. You have to insert all the elements also in a tommy_list, and use the list to iterate. See the Multi-Indexing: Searching Objects in Multiple Ways example for more detail.

Macro Definition Documentation

TOMMY_TRIE_BIT

#define TOMMY_TRIE_BIT   32

Number of bits of the elements to store in the trie.

If you need to store integers bigger than 32 bits you can increase this value.

Keeping this value small improves the performance of the trie.

TOMMY_TRIE_TREE_MAX

#define TOMMY_TRIE_TREE_MAX   (64 / sizeof(void*))

Number of branches on each inner node.

It must be a power of 2. Suggested values are 8, 16 and 32. Any inner node, excluding leafs, contains a pointer to each branch.

The default size is chosen to exactly fit a typical cache line of 64 bytes.

TOMMY_TRIE_BLOCK_SIZE

#define TOMMY_TRIE_BLOCK_SIZE   (TOMMY_TRIE_TREE_MAX * sizeof(void*))

Trie block size.

You must use this value to initialize the allocator.

Typedef Documentation

tommy_trie_node

typedef tommy_node tommy_trie_node

Trie node.

This is the node that you have to include inside your objects.

tommy_trie

typedef struct tommy_trie_struct tommy_trie

Trie container type.

Note

Don't use internal fields directly, but access the container only using functions.

Function Documentation

tommy_trie_init()

TOMMY_API void tommy_trie_init	(	tommy_trie *	trie,
		tommy_allocator *	alloc
	)

Initializes the trie.

You have to provide an allocator initialized with both the size and align with TOMMY_TRIE_BLOCK_SIZE. You can share this allocator with other tries.

The trie is completely allocated through the allocator, and it doesn't need to be deinitialized.

Parameters

alloc

Allocator initialized with both the size and align with TOMMY_TRIE_BLOCK_SIZE.

tommy_trie_insert()

TOMMY_API void tommy_trie_insert	(	tommy_trie *	trie,
		tommy_trie_node *	node,
		void *	data,
		tommy_key_t	key
	)

Inserts an element in the trie.

You have to provide the pointer of the node embedded into the object, the pointer to the object and the key to use.

Parameters

node	Pointer to the node embedded into the object to insert.
data	Pointer to the object to insert.
key	Key to use to insert the object.

tommy_trie_remove()

TOMMY_API void * tommy_trie_remove	(	tommy_trie *	trie,
		tommy_key_t	key
	)

Searches and removes the first element with the specified key.

If the element is not found, 0 is returned. If more equal elements are present, the first one is removed. This operation is faster than calling tommy_trie_bucket() and tommy_trie_remove_existing() separately.

Parameters

key	Key of the element to find and remove.

Returns

The removed element, or 0 if not found.

tommy_trie_bucket()

TOMMY_API tommy_trie_node * tommy_trie_bucket	(	tommy_trie *	trie,
		tommy_key_t	key
	)

Gets the bucket of the specified key.

The bucket is guaranteed to contain ALL and ONLY the elements with the specified key. You can access elements in the bucket following the ::next pointer until 0.

Parameters

key	Key of the element to find.

Returns

The head of the bucket, or 0 if empty.

tommy_trie_search()

void * tommy_trie_search	(	tommy_trie *	trie,
		tommy_key_t	key
	)

Searches an element in the trie.

You have to provide the key of the element you want to find. If more elements with the same key are present, the first one is returned.

Parameters

key	Key of the element to find.

Returns

The first element found, or 0 if none.

tommy_trie_remove_existing()

TOMMY_API void * tommy_trie_remove_existing	(	tommy_trie *	trie,
		tommy_trie_node *	node
	)

Removes an element from the trie.

You must already have the address of the element to remove.

Returns

The tommy_node::data field of the node removed.

tommy_trie_count()

tommy_size_t tommy_trie_count

(

tommy_trie *

trie

)

Gets the number of elements.

tommy_trie_memory_usage()

TOMMY_API tommy_size_t tommy_trie_memory_usage

(

tommy_trie *

trie

)

Gets the size of allocated memory.

It includes the size of the tommy_trie_node of the stored elements.