Trie - osvaldoandrade/ova-lib GitHub Wiki

Trie

Read this page when the query is over prefixes of byte strings and not only over exact keys.

Constructor and Core API

The constructor is:

trie *create_trie(void);

The public API is:

Function	Meaning
`insert`	inserts or updates one word-value pair
`search`	returns the stored value for an exact word or `NULL`
`starts_with`	returns whether at least one stored word shares the prefix
`get_words_with_prefix`	returns an allocated list of matching words
`delete`	removes one stored word and returns whether removal happened
`count_words`	returns total stored word count
`count_prefixes`	returns the number of stored words under a prefix
`free`	frees trie storage

Storage Model

The current implementation is byte-oriented with an alphabet size of 256.

That means the trie works on raw byte strings, not only on letters.

Insert and Search Semantics

t->insert(t, ...) creates missing nodes on the path and stores the value pointer at the terminal node.

If the word already exists, insertion overwrites the stored value pointer.

t->search(t, ...) returns the stored value pointer for an exact match.

Prefix Operations

starts_with answers whether the prefix exists at all.

count_prefixes answers how many stored words share that prefix.

get_words_with_prefix returns a fresh list container of fresh char * copies of the matching words. The words are collected in byte-order traversal, which gives lexicographic order for plain ASCII text.

The shipped tests verify the order car, cart, cat for the prefix ca.

Delete Semantics

delete removes one exact word and prunes unused nodes on the way back up.

Deleting a shorter word does not remove longer words that share the same prefix. The shipped tests verify that deleting car leaves cart intact.

`NULL` Value Caveat

If you intentionally store NULL as the value for a word, search cannot distinguish between:

the word being absent

the word being present with a stored NULL value

That ambiguity is part of the current contract.

Ownership and Cleanup

The trie owns its nodes only. It does not own the stored value pointers.

The list returned by get_words_with_prefix belongs to the caller. Each string inside that list also belongs to the caller and must be freed before the list container is freed.

Destroy the trie with t->free(t).