trie.h File Reference

Trie data structure implementation for efficient string storage and retrieval. More...

#include "arena.h"
#include <stdbool.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

Include dependency graph for trie.h:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Classes
struct	suggestions_collector_t

Typedefs
typedef struct _trie	trie_t

Functions
trie_t *	trie_create (void)
void	trie_destroy (trie_t *trie)
bool	trie_insert (trie_t *trie, const char *word)
bool	trie_search (const trie_t *trie, const char *word)
bool	trie_starts_with (const trie_t *trie, const char *prefix)
bool	trie_delete (trie_t *trie, const char *word)
uint32_t	trie_get_frequency (const trie_t *trie, const char *word)
size_t	trie_get_word_count (const trie_t *trie)
bool	trie_is_empty (const trie_t *trie)
const char **	trie_autocomplete (const trie_t *trie, const char *prefix, size_t max_suggestions, size_t *out_count, Arena *arena)

Detailed Description

Trie data structure implementation for efficient string storage and retrieval.

Definition in file trie.h.

Typedef Documentation

trie_t

typedef struct _trie trie_t

Root structure for the Trie data structure.

Definition at line 15 of file trie.h.

Function Documentation

trie_autocomplete()

const char ** trie_autocomplete	(	const trie_t *	trie,
		const char *	prefix,
		size_t	max_suggestions,
		size_t *	out_count,
		Arena *	arena
	)

Autocomplete function that returns all words with a given prefix. Stores the result array and suggestion strings in the provided Arena.

Parameters

trie	The Trie structure.
prefix	The prefix to search for (null-terminated).
max_suggestions	Maximum number of suggestions to return.
out_count	Output parameter for number of suggestions found.
arena	The Arena allocator to use for the results.

Returns

Array of suggestion strings (allocated in arena), or NULL on error/not found.

Note

The returned array and strings are owned by the Arena and freed when arena_destroy is called.

Definition at line 235 of file trie.c.

References trie_autocomplete().

Referenced by trie_autocomplete().

Here is the call graph for this function:

Here is the caller graph for this function:

trie_create()

trie_t * trie_create

(

void

)

Creates a new Trie data structure.

Returns

Pointer to new Trie on success, NULL on allocation failure.

Note

Caller must free using trie_destroy().

Definition at line 117 of file trie.c.

References trie_create().

Referenced by trie_create().

Here is the call graph for this function:

Here is the caller graph for this function:

trie_delete()

bool trie_delete	(	trie_t *	trie,
		const char *	word
	)

Deletes a word from the Trie.

Parameters

trie	The Trie structure.
word	The word to delete (null-terminated).

Returns

true if word was deleted, false if word doesn't exist.

Note

This only marks the word as deleted; nodes are not freed to maintain O(1) deletion.

Definition at line 176 of file trie.c.

References trie_delete().

Referenced by trie_delete().

Here is the call graph for this function:

Here is the caller graph for this function:

trie_destroy()

void trie_destroy

(

trie_t *

trie

)

Destroys a Trie and frees all associated memory.

Parameters

trie	Trie to destroy (can be NULL).

Definition at line 129 of file trie.c.

References trie_destroy().

Referenced by trie_destroy().

Here is the call graph for this function:

Here is the caller graph for this function:

trie_get_frequency()

uint32_t trie_get_frequency	(	const trie_t *	trie,
		const char *	word
	)

Gets the frequency count for a word.

Parameters

trie	The Trie structure.
word	The word to query (null-terminated).

Returns

Frequency count, or 0 if word doesn't exist.

Definition at line 193 of file trie.c.

References trie_get_frequency().

Referenced by trie_get_frequency().

Here is the call graph for this function:

Here is the caller graph for this function:

trie_get_word_count()

size_t trie_get_word_count

(

const trie_t *

trie

)

Gets the total number of unique words in the Trie.

Parameters

trie	The Trie structure.

Returns

Number of unique words, or 0 if trie is NULL.

Definition at line 205 of file trie.c.

References trie_get_word_count().

Referenced by trie_get_word_count().

Here is the call graph for this function:

Here is the caller graph for this function:

trie_insert()

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

Inserts a word into the Trie.

Parameters

trie	The Trie structure.
word	The word to insert (null-terminated).

Returns

true on success, false on failure (invalid input or allocation error).

Definition at line 135 of file trie.c.

References trie_insert().

Referenced by trie_insert().

Here is the call graph for this function:

Here is the caller graph for this function:

trie_is_empty()

bool trie_is_empty

(

const trie_t *

trie

)

Checks if the Trie is empty.

Parameters

trie	The Trie structure.

Returns

true if empty or NULL, false otherwise.

Definition at line 206 of file trie.c.

References trie_is_empty().

Referenced by trie_is_empty().

Here is the call graph for this function:

Here is the caller graph for this function:

trie_search()

bool trie_search	(	const trie_t *	trie,
		const char *	word
	)

Searches for an exact word in the Trie.

Parameters

trie	The Trie structure.
word	The word to search for (null-terminated).

Returns

true if word exists in Trie, false otherwise.

Definition at line 152 of file trie.c.

References trie_search().

Referenced by trie_search().

Here is the call graph for this function:

Here is the caller graph for this function:

trie_starts_with()

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

Checks if any word in the Trie starts with the given prefix.

Parameters

trie	The Trie structure.
prefix	The prefix to search for (null-terminated).

Returns

true if prefix exists, false otherwise.

Definition at line 164 of file trie.c.

References trie_starts_with().

Referenced by trie_starts_with().

Here is the call graph for this function:

Here is the caller graph for this function: