00001 00002 /* 00003 ** Copyright (C) 2005 Russell Leighton 00004 ** 00005 ** This program is free software; you can redistribute it and/or modify 00006 ** it under the terms of the GNU General Public License as published by 00007 ** the Free Software Foundation; either version 2 of the License, or 00008 ** (at your option) any later version. 00009 ** 00010 ** This program is distributed in the hope that it will be useful, 00011 ** but WITHOUT ANY WARRANTY; without even the implied warranty of 00012 ** MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 00013 ** GNU General Public License for more details. 00014 ** 00015 ** You should have received a copy of the GNU General Public License 00016 ** along with this program; if not, write to the Free Software 00017 ** Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. 00018 */ 00019 00020 00021 #ifndef __AW_TRIE__ 00022 #define __AW_TRIE__ 00023 00024 #include "sys.h" 00025 #include "errors.h" 00026 #include "util.h" 00027 00039 /* ------------------------- trie.c */ 00040 00041 typedef struct { 00042 00043 u_int32_t 00044 modmask; /* masking 'i' with this is equiv of: (i % nelements-in-table) */ 00045 00046 struct aw_trie_node_struct 00047 **table; /* array of aw_trie_node_struct *, size == modmask+1 */ 00048 00049 } oht_t; /* octet hash table (always power of 2 and <= 256 in size */ 00050 00051 00052 /* used to lookup objects */ 00053 typedef struct aw_trie_node_struct 00054 { 00055 u_int32_t 00056 octet; 00057 00058 const byte_t 00059 *path; /* pointer to UN-expanded path */ 00060 00061 union { 00062 00063 oht_t 00064 *children; /* pointer to table of children */ 00065 00066 void 00067 *bin; /* pointer to user structure */ 00068 00069 } bucket; 00070 00071 } aw_trie_node_t; 00072 00073 typedef struct aw_trie_struct { 00074 00075 /* total objects stored */ 00076 u_int32_t 00077 nentries; 00078 00079 oht_t 00080 *roots; 00081 00082 } aw_trie_t; 00083 00084 00085 /* exported functions from trie.c */ 00086 00092 aw_trie_t *aw_trie_make(void); 00093 00100 int32_t aw_trie_insert(const byte_t *s, void *value_ptr, aw_trie_t *trie); 00101 00107 void *aw_trie_delete(const byte_t *s, aw_trie_t *trie); 00108 00109 00114 void *aw_trie_fetch(const byte_t *s, const aw_trie_t *trie); 00115 00116 00122 int32_t aw_trie_uincr(const byte_t *s, u_int32_t uincr, aw_trie_t *trie); 00123 00128 void aw_trie_destroy(aw_trie_t *trie); 00129 00134 void aw_trie_clear(aw_trie_t *trie); 00135 00141 void aw_trie_thin(aw_trie_t *trie, void *user_ptr, u_int32_t (*eval)(void *user_ptr, void *value_ptr) ); 00142 00143 #endif