|
Packit |
d394d9 |
/* Copyright (C) 1995 Bjoern Beutel. */
|
|
Packit |
d394d9 |
|
|
Packit |
d394d9 |
/* Description. =============================================================*/
|
|
Packit |
d394d9 |
|
|
Packit |
d394d9 |
/* This module implements a static trie structure. */
|
|
Packit |
d394d9 |
|
|
Packit |
d394d9 |
/* Types. ===================================================================*/
|
|
Packit |
d394d9 |
|
|
Packit |
d394d9 |
typedef struct /* A "trie_entry_t" associates KEY with CONTENT. */
|
|
Packit |
d394d9 |
{
|
|
Packit |
d394d9 |
string_t key; /* The key of a trie entry is considered case insensitive. */
|
|
Packit |
d394d9 |
int_t content;
|
|
Packit |
d394d9 |
} trie_entry_t;
|
|
Packit |
d394d9 |
|
|
Packit |
d394d9 |
/* Functions. ===============================================================*/
|
|
Packit |
d394d9 |
|
|
Packit |
d394d9 |
/* A trie is a vector of ints. When constructed, it is returned as a pool
|
|
Packit |
d394d9 |
* together with the index of the root node. */
|
|
Packit |
d394d9 |
|
|
Packit |
d394d9 |
extern void new_trie( int_t n,
|
|
Packit |
d394d9 |
trie_entry_t *entries,
|
|
Packit |
d394d9 |
pool_t *trie_pool,
|
|
Packit |
d394d9 |
int_t *root_node_index );
|
|
Packit |
d394d9 |
/* Take N ENTRIES and build a trie of them.
|
|
Packit |
d394d9 |
* Return the trie in *TRIE_POOL
|
|
Packit |
d394d9 |
* and the index of its root node in *ROOT_NODE_INDEX.
|
|
Packit |
d394d9 |
* The keys in *ENTRIES must be non-empty, unique, and sorted. */
|
|
Packit |
d394d9 |
|
|
Packit |
d394d9 |
extern bool_t lookup_trie( int_t *trie,
|
|
Packit |
d394d9 |
int_t *node_index,
|
|
Packit |
d394d9 |
string_t *input,
|
|
Packit |
d394d9 |
int_t *content );
|
|
Packit |
d394d9 |
/* Test if a prefix of *INPUT matches the node at *NODE_INDEX in TRIE.
|
|
Packit |
d394d9 |
* If it does, return TRUE (else return FALSE) and:
|
|
Packit |
d394d9 |
* *CONTENT contains the associated content,
|
|
Packit |
d394d9 |
* *NODE contains the subnode for the matched input, and
|
|
Packit |
d394d9 |
* *INPUT points to the first char behind the prefix. */
|
|
Packit |
d394d9 |
|
|
Packit |
d394d9 |
/* End of file. =============================================================*/
|