trie.h
Go to the documentation of this file.
00001 /***********************************************************************/
00016 #include <limits.h> //CHAR_BIT
00017 
00018 #include "types.h"
00019 #include "config.h"
00020 
00021 //index_t and NODEBITS is tweakable
00022 typedef u8 index_t;
00023 #define NODEBITS CONFIG_TRIE_BITS_PER_NODE
00024 
00025 //These are untweakable
00026 #define INDEXBITS (CHAR_BIT*sizeof(index_t))
00027 #define OUTDEGREE (1<<NODEBITS)
00028 #define NODBITSMASK (OUTDEGREE-1)
00029 
00030 struct trienode{
00031         struct trienode *child[OUTDEGREE];
00032 };
00033 
00034 /*
00035  * Not storing the leaf pointer, we do not support efficient dereferencing.
00036  * The leaf pointer should instead be returned by functions manipulating this.
00037  */
00038 struct trie_iterator{
00039         struct trienode *comefrom[INDEXBITS/NODEBITS - 1]; //nodes above leaf
00040         index_t index;
00041 };
00042 
00043 typedef void (*callback_f)(void*, index_t);
00044 
00045 void trie_init(struct trienode *);
00046 void trie_destroy(struct trienode *, callback_f);
00047 void* trie_lookup(struct trienode *, index_t);
00048 void* trie_iterator_begin(struct trie_iterator*, struct trienode*, index_t);
00049 void* trie_iterate(struct trie_iterator *);
00050 void** trie_push(struct trienode *, index_t);
00051 void* trie_pop(struct trienode *, index_t);
 All Classes Files Functions Enumerations Enumerator Defines