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