Inplace trie. More...

Data Structures
struct	tommy_trie_inplace_node_struct
	Trie node. More...

struct	tommy_trie_inplace_struct
	Trie container type. More...

Macros
#define	TOMMY_TRIE_INPLACE_TREE_MAX 4
	Number of branches on each node. More...

Typedefs
typedef struct tommy_trie_inplace_node_struct	tommy_trie_inplace_node
	Trie node. More...

typedef struct tommy_trie_inplace_struct	tommy_trie_inplace
	Trie container type. More...

Functions
void	tommy_trie_inplace_init (tommy_trie_inplace *trie_inplace)
	Initializes the trie. More...

void	tommy_trie_inplace_insert (tommy_trie_inplace trie_inplace, tommy_trie_inplace_node node, void *data, tommy_key_t key)
	Inserts an element in the trie. More...

void *	tommy_trie_inplace_remove (tommy_trie_inplace *trie_inplace, tommy_key_t key)
	Searches and removes the first element with the specified key. More...

tommy_trie_inplace_node *	tommy_trie_inplace_bucket (tommy_trie_inplace *trie_inplace, tommy_key_t key)
	Gets the bucket of the specified key. More...

void *	tommy_trie_inplace_search (tommy_trie_inplace *trie_inplace, tommy_key_t key)
	Searches an element in the trie. More...

void *	tommy_trie_inplace_remove_existing (tommy_trie_inplace trie_inplace, tommy_trie_inplace_node node)
	Removes an element from the trie. More...

tommy_count_t	tommy_trie_inplace_count (tommy_trie_inplace *trie_inplace)
	Gets the number of elements. More...

tommy_size_t	tommy_trie_inplace_memory_usage (tommy_trie_inplace *trie_inplace)
	Gets the size of allocated memory. More...

Detailed Description

Inplace trie.

This trie is a inplace implementation not needing any external allocation.

Elements are not stored in order, like tommy_trie, because some elements should be used to represent the inner nodes in the trie.

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

Compared to tommy_trie you should use a lower number of branches to limit the unused memory occupation of the leaf nodes. This imply a lower speed, but without the need of an external allocator.

To initialize the trie you have to call tommy_trie_inplace_init().

tommy_trie_inplace trie_inplace;
tommy_trie_inplace_init(&trie_inplace);

To insert elements in the trie you have to call tommy_trie_inplace_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_inplace_insert(&trie_inplace, &obj->node, obj, obj->value); // inserts the object

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

int value_to_find = 1;
struct object* obj = tommy_trie_inplace_search(&trie_inplace, 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_inplace_bucket() and follow the tommy_node::next pointer until NULL.

int value_to_find = 1;
tommy_node* i = tommy_trie_inplace_bucket(&trie_inplace, 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_inplace_remove() providing the key to search and remove.

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

To destroy the trie you have only to remove all the elements, as the trie is completely inplace and it doesn't allocate memory.

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 Tommy Multi Indexing example for more detail.

Macro Definition Documentation

#define TOMMY_TRIE_INPLACE_TREE_MAX 4

Number of branches on each node.

It must be a power of 2. Suggested values are 2, 4 and 8. Any node, including leafs, contains a pointer to each branch.

Typedef Documentation

typedef struct tommy_trie_inplace_node_struct tommy_trie_inplace_node

Trie node.

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

typedef struct tommy_trie_inplace_struct tommy_trie_inplace

Trie container type.

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

Function Documentation

void tommy_trie_inplace_init ( tommy_trie_inplace * trie_inplace )

Initializes the trie.

The tries is completely inplace, and it doesn't need to be deinitialized.

void tommy_trie_inplace_insert	(	tommy_trie_inplace *	trie_inplace,
		tommy_trie_inplace_node *	node,
		void *	data,
		tommy_key_t	key
	)

Inserts an element in the trie.

void* tommy_trie_inplace_remove	(	tommy_trie_inplace *	trie_inplace,
		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_inplace_bucket() and tommy_trie_inplace_remove_existing() separately.

Parameters

key	Key of the element to find and remove.

Returns: The removed element, or 0 if not found.

tommy_trie_inplace_node* tommy_trie_inplace_bucket	(	tommy_trie_inplace *	trie_inplace,
		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.

void* tommy_trie_inplace_search	(	tommy_trie_inplace *	trie_inplace,
		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.

void* tommy_trie_inplace_remove_existing	(	tommy_trie_inplace *	trie_inplace,
		tommy_trie_inplace_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_count_t tommy_trie_inplace_count ( tommy_trie_inplace * trie_inplace )

Gets the number of elements.

tommy_size_t tommy_trie_inplace_memory_usage ( tommy_trie_inplace * trie_inplace )

Gets the size of allocated memory.

It includes the size of the ::tommy_inplace_node of the stored elements.

Data Structures

Macros

Typedefs

Functions

Detailed Description

Macro Definition Documentation

Typedef Documentation

Function Documentation