trie.h File Reference

A trie. More...

#include <stdbool.h>
#include <stddef.h>

Include dependency graph for trie.h:

Go to the source code of this file.

Classes
struct	tetengo_trie_trieElement_tag
	An element type. More...

Typedefs
typedef struct tetengo_trie_trieElement_tag	tetengo_trie_trieElement_t
	An element type.
typedef void(*	tetengo_trie_trie_addingObserver_t) (const char *serialized_key, void *p_context)
	An observer type called when a key is adding.
typedef void(*	tetengo_trie_trie_doneObserver_t) (void *p_context)
	An observer type called when the building is done.

Functions
void	tetengo_trie_trie_nullAddingObserver (const char *, void *)
	A null adding observer.
void	tetengo_trie_trie_nullDoneObserver (void *)
	A null done observer.
size_t	tetengo_trie_trie_defaultDoubleArrayDensityFactor (void)
	Returns the default double array density factor.
tetengo_trie_trie_t *	tetengo_trie_trie_create (const tetengo_trie_trieElement_t *p_elements, size_t element_count, size_t element_value_size, tetengo_trie_trie_addingObserver_t adding_observer, void *p_adding_observer_context, tetengo_trie_trie_doneObserver_t done_observer, void *p_done_observer_context, size_t double_array_density_factor)
	Creates a trie.
tetengo_trie_trie_t *	tetengo_trie_trie_createWithStorage (tetengo_trie_storage_t *p_storage)
	Creates a trie.
void	tetengo_trie_trie_destroy (const tetengo_trie_trie_t *p_trie)
	Destroys a trie.
bool	tetengo_trie_trie_empty (const tetengo_trie_trie_t *p_trie)
	Returns true when the trie is empty.
size_t	tetengo_trie_trie_size (const tetengo_trie_trie_t *p_trie)
	Returns the size of the trie.
bool	tetengo_trie_trie_contains (const tetengo_trie_trie_t *p_trie, const char *key)
	Returns true when the trie contains the given key.
const void *	tetengo_trie_trie_find (const tetengo_trie_trie_t *p_trie, const char *key)
	Finds the value object correspoinding the given key.
tetengo_trie_trieIterator_t *	tetengo_trie_trie_createIterator (const tetengo_trie_trie_t *p_trie)
	Creates an iterator.
void	tetengo_trie_trie_destroyIterator (const tetengo_trie_trieIterator_t *p_iterator)
	Destroys an iterator.
const tetengo_trie_trie_t *	tetengo_trie_trie_subtrie (const tetengo_trie_trie_t *p_trie, const char *key_prefix)
	Creates a subtrie.
const tetengo_trie_storage_t *	tetengo_trie_trie_getStorage (const tetengo_trie_trie_t *p_trie)
	Returns the pointer to the storage.

Detailed Description

A trie.

Copyright (C) 2019-2023 kaoru https://www.tetengo.org/

Typedef Documentation

tetengo_trie_trie_addingObserver_t

typedef void(* tetengo_trie_trie_addingObserver_t) (const char *serialized_key, void *p_context)

An observer type called when a key is adding.

Parameters

serialized_key	A serialized key.
p_context	A pointer to the context.

tetengo_trie_trie_doneObserver_t

typedef void(* tetengo_trie_trie_doneObserver_t) (void *p_context)

An observer type called when the building is done.

Parameters

p_context

A pointer to the context.

Function Documentation

tetengo_trie_trie_contains()

bool tetengo_trie_trie_contains	(	const tetengo_trie_trie_t *	p_trie,
		const char *	key
	)

Returns true when the trie contains the given key.

Parameters

p_trie	A pointer to a trie.
key	A key.

Return values

true	When the trie contains the given key.
false	Otherwise.

tetengo_trie_trie_create()

tetengo_trie_trie_t * tetengo_trie_trie_create	(	const tetengo_trie_trieElement_t *	p_elements,
		size_t	element_count,
		size_t	element_value_size,
		tetengo_trie_trie_addingObserver_t	adding_observer,
		void *	p_adding_observer_context,
		tetengo_trie_trie_doneObserver_t	done_observer,
		void *	p_done_observer_context,
		size_t	double_array_density_factor
	)

Creates a trie.

Parameters

p_elements	A pointer to the first element.
element_count	An element count.
element_value_size	An element value size.
adding_observer	An adding observer.
p_adding_observer_context	A pointer to the adding observer context.
done_observer	A done observer.
p_done_observer_context	A pointer to the done observer context.
double_array_density_factor	A double array density factor.

Returns

A pointer to a trie. Or NULL on error.

tetengo_trie_trie_createIterator()

tetengo_trie_trieIterator_t * tetengo_trie_trie_createIterator

(

const tetengo_trie_trie_t *

p_trie

)

Creates an iterator.

Parameters

p_trie

A pointer to a trie.

Returns

A pointer to an iterator. Or NULL on error.

tetengo_trie_trie_createWithStorage()

tetengo_trie_trie_t * tetengo_trie_trie_createWithStorage

(

tetengo_trie_storage_t *

p_storage

)

Creates a trie.

The ownership of the storage pointed by p_storage is transferred into the trie. There is no need to destroy the storage after calling this function.

Parameters

p_storage

A pointer to a storage.

Returns

A pointer to a trie. Or NULL on error or when p_storage does not own a storage but just refferes one.

tetengo_trie_trie_defaultDoubleArrayDensityFactor()

size_t tetengo_trie_trie_defaultDoubleArrayDensityFactor

(

void

)

Returns the default double array density factor.

Returns

The default double array density factor.

tetengo_trie_trie_destroy()

void tetengo_trie_trie_destroy

(

const tetengo_trie_trie_t *

p_trie

)

Destroys a trie.

Parameters

p_trie

A pointer to a trie.

tetengo_trie_trie_destroyIterator()

void tetengo_trie_trie_destroyIterator

(

const tetengo_trie_trieIterator_t *

p_iterator

)

Destroys an iterator.

Parameters

p_iterator

A pointer to an iterator.

tetengo_trie_trie_empty()

bool tetengo_trie_trie_empty

(

const tetengo_trie_trie_t *

p_trie

)

Returns true when the trie is empty.

Parameters

p_trie

A pointer to a trie.

Return values

true	When the trie is empty.
false	Otherwise.

tetengo_trie_trie_find()

const void * tetengo_trie_trie_find	(	const tetengo_trie_trie_t *	p_trie,
		const char *	key
	)

Finds the value object correspoinding the given key.

Parameters

p_trie	A pointer to a trie.
key	A key.

Returns

A pointer to the value object. Or NULL on error or when the trie does not have the given key.

tetengo_trie_trie_getStorage()

const tetengo_trie_storage_t * tetengo_trie_trie_getStorage

(

const tetengo_trie_trie_t *

p_trie

)

Returns the pointer to the storage.

Parameters

p_trie

A pointer to a trie.

Returns

The pointer to the storage. Or NULL on error.

tetengo_trie_trie_size()

size_t tetengo_trie_trie_size

(

const tetengo_trie_trie_t *

p_trie

)

Returns the size of the trie.

Parameters

p_trie

A pointer to a trie.

Returns

The size. Or (size_t)-1 on error.

tetengo_trie_trie_subtrie()

const tetengo_trie_trie_t * tetengo_trie_trie_subtrie	(	const tetengo_trie_trie_t *	p_trie,
		const char *	key_prefix
	)

Creates a subtrie.

Parameters

p_trie	A pointer to a trie.
key_prefix	A key prefix.

Returns

A pointer to a subtrie. Or NULL on error or when the trie does not have the given key prefix.