00001 #include <limits.h>
00002
00003 #include "types.h"
00004 #include "config.h"
00005
00006
00007 typedef u8 index_t;
00008 #define NODEBITS CONFIG_TRIE_BITS_PER_NODE
00009
00010
00011 #define INDEXBITS (CHAR_BIT*sizeof(index_t))
00012 #define OUTDEGREE (1<<NODEBITS)
00013 #define NODBITSMASK (OUTDEGREE-1)
00014
00015 struct trienode{
00016 struct trienode *child[OUTDEGREE];
00017 };
00018
00019
00020
00021
00022
00023 struct trie_iterator{
00024 struct trienode *comefrom[INDEXBITS/NODEBITS - 1];
00025 index_t index;
00026 };
00027
00028 typedef void (*callback_f)(void*, index_t);
00029
00030 void trie_init(struct trienode *);
00031 void trie_destroy(struct trienode *, callback_f);
00032 void* trie_lookup(struct trienode *, index_t);
00033 void* trie_iterator_begin(struct trie_iterator*, struct trienode*, index_t);
00034 void* trie_iterate(struct trie_iterator *);
00035 void** trie_push(struct trienode *, index_t);
00036 void* trie_pop(struct trienode *, index_t);