include/data_structures/tries/trie.h File Reference

#include <stdint.h>
#include <stdbool.h>

Go to the source code of this file.

Data Structures
struct	CKTrie
struct	CKTrieNode

Functions
void	ck_trie_clear (CKTrie *trie)
CKTrie *	ck_trie_create (size_t max_nodes)
int32_t	ck_trie_find_longest (const CKTrie *trie, const char *text, size_t text_len, size_t start_pos, size_t *match_len)
void	ck_trie_free (CKTrie *trie)
bool	ck_trie_has_prefix (const CKTrie *trie, const char *text, size_t text_len, size_t pos)
int	ck_trie_insert (CKTrie *trie, const char *token, int32_t token_id, bool is_special, int32_t priority)
size_t	ck_trie_node_count (const CKTrie *trie)

Function Documentation

ck_trie_clear()

void ck_trie_clear

(

CKTrie *

trie

)

Definition at line 80 of file trie.c.

                                 {
    if (!trie) return;
 
    /* Free all nodes except root */
    CKTrieNode **queue = (CKTrieNode **)malloc(trie->node_count * sizeof(CKTrieNode *));
    if (!queue) return;
 
    size_t head = 0, tail = 0;
    queue[tail++] = trie->root;
 
    while (head < tail) {
        CKTrieNode *node = queue[head++];
        for (int i = 0; i < 256; i++) {
            if (node->children[i]) {
                queue[tail++] = node->children[i];
            }
        }
        /* Clear children pointers but don't free root */
        if (node != trie->root) {
            free(node);
        } else {
            memset(node->children, 0, sizeof(node->children));
            node->token_id = -1;
        }
    }
 
    free(queue);
    trie->node_count = 1;
}

References CKTrieNode::children, CKTrie::node_count, CKTrie::root, and CKTrieNode::token_id.

Referenced by ck_tokenizer_reset().

ck_trie_create()

CKTrie* ck_trie_create

(

size_t

max_nodes

)

Definition at line 29 of file trie.c.

                                         {
    CKTrie *trie = (CKTrie *)malloc(sizeof(CKTrie));
    if (!trie) {
        return NULL;
    }
 
    if (max_nodes == 0) {
        max_nodes = DEFAULT_MAX_NODES;
    }
 
    trie->root = create_node();
    if (!trie->root) {
        free(trie);
        return NULL;
    }
 
    trie->max_nodes = max_nodes;
    trie->node_count = 1; /* Root node */
 
    return trie;
}

References create_node(), DEFAULT_MAX_NODES, CKTrie::max_nodes, CKTrie::node_count, and CKTrie::root.

Referenced by ck_tokenizer_create().

ck_trie_find_longest()

int32_t ck_trie_find_longest	(	const CKTrie *	trie,
		const char *	text,
		size_t	text_len,
		size_t	start_pos,
		size_t *	match_len
	)

Definition at line 142 of file trie.c.

                                                                   {
    if (!trie || !text || start_pos >= text_len || !match_len) {
        *match_len = 0;
        return -1;
    }
 
    CKTrieNode *node = trie->root;
    CKTrieNode *last_token_node = NULL;
    size_t last_token_len = 0;
    size_t pos = start_pos;
 
    /* Traverse as long as we have matching children */
    while (pos < text_len && node) {
        unsigned char c = (unsigned char)text[pos];
 
        if (!node->children[c]) {
            break;
        }
 
        node = node->children[c];
        pos++;
 
        /* Record if this is a valid token end */
        if (node->token_id >= 0) {
            last_token_node = node;
            last_token_len = pos - start_pos;
        }
    }
 
    *match_len = last_token_len;
 
    if (last_token_node) {
        return last_token_node->token_id;
    }
 
    return -1;
}

References CKTrieNode::children, CKTrie::root, text, text_len, and CKTrieNode::token_id.

Referenced by find_longest_match_trie().

ck_trie_free()

void ck_trie_free

(

CKTrie *

trie

)

Definition at line 51 of file trie.c.

                                {
    if (!trie) return;
 
    /* Free all nodes using BFS */
    CKTrieNode **queue = (CKTrieNode **)malloc(trie->node_count * sizeof(CKTrieNode *));
    if (!queue) {
        /* Fallback to simple free */
        free(trie->root);
        free(trie);
        return;
    }
 
    size_t head = 0, tail = 0;
    queue[tail++] = trie->root;
 
    while (head < tail) {
        CKTrieNode *node = queue[head++];
        for (int i = 0; i < 256; i++) {
            if (node->children[i]) {
                queue[tail++] = node->children[i];
            }
        }
        free(node);
    }
 
    free(queue);
    free(trie);
}

References CKTrieNode::children, CKTrie::node_count, and CKTrie::root.

Referenced by ck_tokenizer_free().

ck_trie_has_prefix()

bool ck_trie_has_prefix	(	const CKTrie *	trie,
		const char *	text,
		size_t	text_len,
		size_t	pos
	)

Definition at line 181 of file trie.c.

                                                                                           {
    if (!trie || !text || pos >= text_len) return false;
 
    CKTrieNode *node = trie->root;
 
    while (pos < text_len && node) {
        unsigned char c = (unsigned char)text[pos];
        node = node->children[c];
        pos++;
    }
 
    return node != NULL;
}

References CKTrieNode::children, CKTrie::root, text, and text_len.

ck_trie_insert()

int ck_trie_insert	(	CKTrie *	trie,
		const char *	token,
		int32_t	token_id,
		bool	is_special,
		int32_t	priority
	)

Definition at line 110 of file trie.c.

                                                                                                         {
    if (!trie || !token) return -1;
 
    CKTrieNode *node = trie->root;
    const unsigned char *p = (const unsigned char *)token;
 
    while (*p) {
        unsigned char c = *p++;
 
        if (!node->children[c]) {
            if (trie->node_count >= trie->max_nodes) {
                return -1; /* Out of nodes */
            }
 
            CKTrieNode *new_node = create_node();
            if (!new_node) return -1;
 
            node->children[c] = new_node;
            trie->node_count++;
        }
 
        node = node->children[c];
    }
 
    /* Mark end of token */
    node->token_id = token_id;
    node->is_special = is_special;
    node->priority = priority;
 
    return 0;
}

References CKTrieNode::children, create_node(), CKTrieNode::is_special, CKTrie::max_nodes, CKTrie::node_count, CKTrieNode::priority, priority, CKTrie::root, token, and CKTrieNode::token_id.

Referenced by ck_tokenizer_add_special_token(), and ck_tokenizer_add_token().

ck_trie_node_count()

size_t ck_trie_node_count

(

const CKTrie *

trie

)

Definition at line 195 of file trie.c.

                                              {
    return trie ? trie->node_count : 0;
}

References CKTrie::node_count.