Implementation of a trie data structure. More...

#include <stdbool.h>
#include <stdlib.h>
#include <stdarg.h>
#include "sb-mem.h"

typedef struct _sb_trie_t	sb_trie_t

typedef void(*	sb_trie_foreach_func_t) (const char key, void data, void *user_data)

sb_trie_t *	sb_trie_new (sb_free_func_t free_func)

void	sb_trie_free (sb_trie_t *trie)

void	sb_trie_insert (sb_trie_t trie, const char key, void *data)

void *	sb_trie_lookup (sb_trie_t trie, const char key)

size_t	sb_trie_size (sb_trie_t *trie)

void	sb_trie_foreach (sb_trie_t trie, sb_trie_foreach_func_t func, void user_data)

Detailed Description

Implementation of a trie data structure.

This trie implementation is mostly designed to be used as a replacement for a hash table, where the keys are always strings (arrays of char elements).

Typedef Documentation

typedef void(* sb_trie_foreach_func_t) (const char *key, void *data, void *user_data)

Trie foreach callback function type.

Parameters

key	The key string for current trie element.
data	The data stored for the key.
user_data	Pointer to arbitrary user data that was passed to sb_trie_foreach.

typedef struct _sb_trie_t sb_trie_t

Trie opaque structure.

Function Documentation

void sb_trie_foreach	(	sb_trie_t *	trie,
		sb_trie_foreach_func_t	func,
		void *	user_data
	)

Function that calls a given function for each element of a trie.

Parameters

trie	The trie.
func	The function that should be called for each element.
user_data	Pointer to arbitrary user data to be passed to `func`.

Examples:: hello_trie.c.

void sb_trie_free ( sb_trie_t * trie )

Function that frees the memory allocated for a trie, and for its elements (using the free function provided when creating the trie).

Parameters

trie The trie.

Examples:: hello_trie.c.

void sb_trie_insert	(	sb_trie_t *	trie,
		const char *	key,
		void *	data
	)

Function that inserts an element on the trie. If the key already exists, its current element is free'd (using the free function provided when creating the trie) and replaced with new one.

Parameters

trie	The trie.
key	The key string.
data	The data to be stored for the key. Users should not free it explicitly if the tree was initialized with a valid free function.

Examples:: hello_trie.c.

void* sb_trie_lookup	(	sb_trie_t *	trie,
		const char *	key
	)

Function that searches the trie for a given key, and return its data.

Parameters

trie	The trie.
key	The key string to be looked for.

Returns: The date stored for the given key, if found, otherwise NULL.

Examples:: hello_trie.c.

sb_trie_t* sb_trie_new ( sb_free_func_t free_func )

Function that creates a new trie.

Parameters

free_func The sb_free_func_t to be used to free the memory allocated for the elements automatically when needed. If NULL, the trie won't touch the elements when free'ing itself.

Returns: A new trie.

Examples:: hello_trie.c.

size_t sb_trie_size ( sb_trie_t * trie )

Function that returns the size of a given trie.

Parameters

trie The trie.

Returns: The size of the given trie.

Examples:: hello_trie.c.