trie.h File Reference

Prefix tree (trie) over lowercase ASCII letters a-z. More...

#include <stdbool.h>

Go to the source code of this file.

Typedefs
typedef struct trie	trie_t

Functions
bool	trie_contains (const trie_t *t, const char *word)
trie_t *	trie_create (void)
void	trie_destroy (trie_t *t)
bool	trie_insert (trie_t *t, const char *word)
bool	trie_starts_with (const trie_t *t, const char *prefix)

Detailed Description

Prefix tree (trie) over lowercase ASCII letters a-z.

26-way fixed branching, one node per inserted prefix. Memory cost is proportional to the union of all prefixes — heavier than a hash set but supports starts_with (prefix queries) in O(prefix length).

Definition in file trie.h.

Typedef Documentation

trie_t

typedef struct trie trie_t

Definition at line 15 of file trie.h.

Function Documentation

trie_contains()

bool trie_contains	(	const trie_t *	t,
		const char *	word
	)

Definition at line 76 of file trie.c.

References trie_node::terminal, and walk().

trie_create()

trie_t * trie_create

(

void

)

Definition at line 29 of file trie.c.

References node_create(), and trie::root.

trie_destroy()

void trie_destroy

(

trie_t *

t

)

Definition at line 37 of file trie.c.

References node_destroy(), and trie::root.

trie_insert()

bool trie_insert	(	trie_t *	t,
		const char *	word
	)

Inserts a lowercase a-z word. Returns false on allocation failure or if the word contains a non-{a-z} character.

Definition at line 49 of file trie.c.

References trie_node::children, idx_of(), node_create(), trie::root, and trie_node::terminal.

trie_starts_with()

bool trie_starts_with	(	const trie_t *	t,
		const char *	prefix
	)

True if any inserted word begins with prefix.

Definition at line 81 of file trie.c.

References walk().