Line data Source code
1 : /*
2 : * Copyright (c) 2010, Andrea Mazzoleni. All rights reserved.
3 : *
4 : * Redistribution and use in source and binary forms, with or without
5 : * modification, are permitted provided that the following conditions
6 : * are met:
7 : *
8 : * 1. Redistributions of source code must retain the above copyright
9 : * notice, this list of conditions and the following disclaimer.
10 : *
11 : * 2. Redistributions in binary form must reproduce the above copyright
12 : * notice, this list of conditions and the following disclaimer in the
13 : * documentation and/or other materials provided with the distribution.
14 : *
15 : * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
16 : * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
17 : * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
18 : * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
19 : * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
20 : * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
21 : * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
22 : * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
23 : * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
24 : * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
25 : * POSSIBILITY OF SUCH DAMAGE.
26 : */
27 :
28 : #include "tommytrie.h"
29 : #include "tommylist.h"
30 :
31 : #include <assert.h> /* for assert */
32 :
33 : /******************************************************************************/
34 : /* trie */
35 :
36 : /**
37 : * Mask for the inner branches.
38 : */
39 : #define TOMMY_TRIE_TREE_MASK (TOMMY_TRIE_TREE_MAX - 1)
40 :
41 : /**
42 : * Shift for the first level of branches.
43 : */
44 : #define TOMMY_TRIE_BUCKET_SHIFT (TOMMY_TRIE_BIT - TOMMY_TRIE_BUCKET_BIT)
45 :
46 : /**
47 : * Max number of levels.
48 : */
49 : #define TOMMY_TRIE_LEVEL_MAX ((TOMMY_TRIE_BIT - TOMMY_TRIE_BUCKET_BIT) / TOMMY_TRIE_TREE_BIT)
50 :
51 : /**
52 : * Hashtrie tree.
53 : * A tree contains TOMMY_TRIE_TREE_MAX ordered pointers to <null/node/tree>.
54 : *
55 : * Each tree level uses exactly TOMMY_TRIE_TREE_BIT bits from the key.
56 : */
57 : struct tommy_trie_tree_struct {
58 : tommy_trie_node* map[TOMMY_TRIE_TREE_MAX];
59 : };
60 : typedef struct tommy_trie_tree_struct tommy_trie_tree;
61 :
62 : /**
63 : * Kinds of an trie node.
64 : */
65 : #define TOMMY_TRIE_TYPE_NODE 0 /**< The node is of type ::tommy_trie_node. */
66 : #define TOMMY_TRIE_TYPE_TREE 1 /**< The node is of type ::tommy_trie_tree. */
67 :
68 : /**
69 : * Get and set pointer of trie nodes.
70 : *
71 : * The pointer type is stored in the lower bit.
72 : */
73 : #define trie_get_type(ptr) (((tommy_uintptr_t)(ptr)) & 1)
74 : #define trie_get_tree(ptr) ((tommy_trie_tree*)(((tommy_uintptr_t)(ptr)) - TOMMY_TRIE_TYPE_TREE))
75 : #define trie_set_tree(ptr) (void*)(((tommy_uintptr_t)(ptr)) + TOMMY_TRIE_TYPE_TREE)
76 :
77 1 : void tommy_trie_init(tommy_trie* trie, tommy_allocator* alloc)
78 : {
79 : tommy_uint_t i;
80 :
81 33 : for (i = 0; i < TOMMY_TRIE_BUCKET_MAX; ++i)
82 32 : trie->bucket[i] = 0;
83 :
84 1 : trie->count = 0;
85 1 : trie->node_count = 0;
86 :
87 1 : trie->alloc = alloc;
88 1 : }
89 :
90 42857154 : static void trie_bucket_insert(tommy_trie* trie, tommy_uint_t shift, tommy_trie_node** let_ptr, tommy_trie_node* insert, tommy_key_t key)
91 : {
92 : tommy_trie_tree* tree;
93 : tommy_trie_node* node;
94 : void* ptr;
95 : tommy_uint_t i;
96 : tommy_uint_t j;
97 :
98 : recurse:
99 42857154 : ptr = *let_ptr;
100 :
101 : /* if null, just insert the node */
102 42857154 : if (!ptr) {
103 : /* setup the node as a list */
104 3500000 : tommy_list_insert_first(let_ptr, insert);
105 3500000 : return;
106 : }
107 :
108 39357154 : if (trie_get_type(ptr) == TOMMY_TRIE_TYPE_TREE) {
109 : /* repeat the process one level down */
110 38857152 : let_ptr = &trie_get_tree(ptr)->map[(key >> shift) & TOMMY_TRIE_TREE_MASK];
111 38857152 : shift -= TOMMY_TRIE_TREE_BIT;
112 38857152 : goto recurse;
113 : }
114 :
115 500002 : node = tommy_cast(tommy_trie_node*, ptr);
116 :
117 : /* if it's the same key, insert in the list */
118 500002 : if (node->index == key) {
119 2 : tommy_list_insert_tail_not_empty(node, insert);
120 2 : return;
121 : }
122 :
123 : expand:
124 : /* convert to a tree */
125 571434 : tree = tommy_cast(tommy_trie_tree*, tommy_allocator_alloc(trie->alloc));
126 571434 : ++trie->node_count;
127 571434 : *let_ptr = tommy_cast(tommy_trie_node*, trie_set_tree(tree));
128 :
129 : /* initialize it */
130 5142906 : for (i = 0; i < TOMMY_TRIE_TREE_MAX; ++i)
131 4571472 : tree->map[i] = 0;
132 :
133 : /* get the position of the two elements */
134 571434 : i = (node->index >> shift) & TOMMY_TRIE_TREE_MASK;
135 571434 : j = (key >> shift) & TOMMY_TRIE_TREE_MASK;
136 :
137 : /* if they don't collide */
138 571434 : if (i != j) {
139 : /* insert the already existing element */
140 500000 : tree->map[i] = node;
141 :
142 : /* insert the new node */
143 500000 : tommy_list_insert_first(&tree->map[j], insert);
144 500000 : return;
145 : }
146 :
147 : /* expand one more level */
148 71434 : let_ptr = &tree->map[i];
149 71434 : shift -= TOMMY_TRIE_TREE_BIT;
150 71434 : goto expand;
151 : }
152 :
153 4000002 : void tommy_trie_insert(tommy_trie* trie, tommy_trie_node* node, void* data, tommy_key_t key)
154 : {
155 : tommy_trie_node** let_ptr;
156 :
157 : /* ensure that the element is not too big */
158 4000002 : assert(key >> TOMMY_TRIE_BUCKET_SHIFT < TOMMY_TRIE_BUCKET_MAX);
159 :
160 4000002 : node->data = data;
161 4000002 : node->index = key;
162 :
163 4000002 : let_ptr = &trie->bucket[key >> TOMMY_TRIE_BUCKET_SHIFT];
164 :
165 4000002 : trie_bucket_insert(trie, TOMMY_TRIE_BUCKET_SHIFT, let_ptr, node, key);
166 :
167 4000002 : ++trie->count;
168 4000002 : }
169 :
170 6000003 : static tommy_trie_node* trie_bucket_remove_existing(tommy_trie* trie, tommy_uint_t shift, tommy_trie_node** let_ptr, tommy_trie_node* remove, tommy_key_t key)
171 : {
172 : tommy_trie_node* node;
173 : tommy_trie_tree* tree;
174 : void* ptr;
175 : tommy_trie_node** let_back[TOMMY_TRIE_LEVEL_MAX + 1];
176 : tommy_uint_t level;
177 : tommy_uint_t i;
178 : tommy_uint_t count;
179 : tommy_uint_t last;
180 :
181 6000003 : level = 0;
182 : recurse:
183 53596017 : ptr = *let_ptr;
184 :
185 53596017 : if (!ptr)
186 2000000 : return 0;
187 :
188 51596017 : if (trie_get_type(ptr) == TOMMY_TRIE_TYPE_TREE) {
189 47596014 : tree = trie_get_tree(ptr);
190 :
191 : /* save the path */
192 47596014 : let_back[level++] = let_ptr;
193 :
194 : /* go down one level */
195 47596014 : let_ptr = &tree->map[(key >> shift) & TOMMY_TRIE_TREE_MASK];
196 47596014 : shift -= TOMMY_TRIE_TREE_BIT;
197 :
198 47596014 : goto recurse;
199 : }
200 :
201 4000003 : node = tommy_cast(tommy_trie_node*, ptr);
202 :
203 : /* if the node to remove is not specified */
204 4000003 : if (!remove) {
205 : /* remove the first */
206 2000001 : remove = node;
207 :
208 : /* check if it's really the element to remove */
209 2000001 : if (remove->index != key)
210 1 : return 0;
211 : }
212 :
213 4000002 : tommy_list_remove_existing(let_ptr, remove);
214 :
215 : /* if the list is not empty, try to reduce */
216 4000002 : if (*let_ptr || !level)
217 3 : return remove;
218 :
219 : reduce:
220 : /* go one level up */
221 4571432 : let_ptr = let_back[--level];
222 :
223 4571432 : tree = trie_get_tree(*let_ptr);
224 :
225 : /* check if there is only one child node */
226 4571432 : count = 0;
227 4571432 : last = 0;
228 26642856 : for (i = 0; i < TOMMY_TRIE_TREE_MAX; ++i) {
229 26071422 : if (tree->map[i]) {
230 : /* if we have a sub tree, we cannot reduce */
231 8071472 : if (trie_get_type(tree->map[i]) != TOMMY_TRIE_TYPE_NODE)
232 999957 : return remove;
233 : /* if more than one node, we cannot reduce */
234 7071515 : if (++count > 1)
235 3000041 : return remove;
236 4071474 : last = i;
237 : }
238 : }
239 :
240 : /* here count is never 0, as we cannot have a tree with only one sub node */
241 571434 : assert(count == 1);
242 :
243 571434 : *let_ptr = tree->map[last];
244 :
245 571434 : tommy_allocator_free(trie->alloc, tree);
246 571434 : --trie->node_count;
247 :
248 : /* repeat until more level */
249 571434 : if (level)
250 571433 : goto reduce;
251 :
252 1 : return remove;
253 : }
254 :
255 4000001 : void* tommy_trie_remove(tommy_trie* trie, tommy_key_t key)
256 : {
257 : tommy_trie_node* ret;
258 : tommy_trie_node** let_ptr;
259 :
260 : /* ensure that the element is not too big */
261 4000001 : assert(key >> TOMMY_TRIE_BUCKET_SHIFT < TOMMY_TRIE_BUCKET_MAX);
262 :
263 4000001 : let_ptr = &trie->bucket[key >> TOMMY_TRIE_BUCKET_SHIFT];
264 :
265 4000001 : ret = trie_bucket_remove_existing(trie, TOMMY_TRIE_BUCKET_SHIFT, let_ptr, 0, key);
266 :
267 4000001 : if (!ret)
268 2000001 : return 0;
269 :
270 2000000 : --trie->count;
271 :
272 2000000 : return ret->data;
273 : }
274 :
275 2000002 : void* tommy_trie_remove_existing(tommy_trie* trie, tommy_trie_node* node)
276 : {
277 : tommy_trie_node* ret;
278 2000002 : tommy_key_t key = node->index;
279 : tommy_trie_node** let_ptr;
280 :
281 : /* ensure that the element is not too big */
282 2000002 : assert(key >> TOMMY_TRIE_BUCKET_SHIFT < TOMMY_TRIE_BUCKET_MAX);
283 :
284 2000002 : let_ptr = &trie->bucket[key >> TOMMY_TRIE_BUCKET_SHIFT];
285 :
286 2000002 : ret = trie_bucket_remove_existing(trie, TOMMY_TRIE_BUCKET_SHIFT, let_ptr, node, key);
287 :
288 : /* the element removed must match the one passed */
289 2000002 : assert(ret == node);
290 :
291 2000002 : --trie->count;
292 :
293 2000002 : return ret->data;
294 : }
295 :
296 4000001 : tommy_trie_node* tommy_trie_bucket(tommy_trie* trie, tommy_key_t key)
297 : {
298 : tommy_trie_node* node;
299 : void* ptr;
300 : tommy_uint_t type;
301 : tommy_uint_t shift;
302 :
303 : /* ensure that the element is not too big */
304 4000001 : assert(key >> TOMMY_TRIE_BUCKET_SHIFT < TOMMY_TRIE_BUCKET_MAX);
305 :
306 4000001 : ptr = trie->bucket[key >> TOMMY_TRIE_BUCKET_SHIFT];
307 :
308 4000001 : shift = TOMMY_TRIE_BUCKET_SHIFT;
309 :
310 : recurse:
311 32167429 : if (!ptr)
312 2000000 : return 0;
313 :
314 30167429 : type = trie_get_type(ptr);
315 :
316 30167429 : switch (type) {
317 : case TOMMY_TRIE_TYPE_NODE :
318 2000001 : node = tommy_cast(tommy_trie_node*, ptr);
319 2000001 : if (node->index != key)
320 1 : return 0;
321 2000000 : return node;
322 : default :
323 : case TOMMY_TRIE_TYPE_TREE :
324 28167428 : ptr = trie_get_tree(ptr)->map[(key >> shift) & TOMMY_TRIE_TREE_MASK];
325 28167428 : shift -= TOMMY_TRIE_TREE_BIT;
326 28167428 : goto recurse;
327 : }
328 : }
329 :
330 1 : tommy_size_t tommy_trie_memory_usage(tommy_trie* trie)
331 : {
332 2 : return tommy_trie_count(trie) * (tommy_size_t)sizeof(tommy_trie_node)
333 1 : + trie->node_count * (tommy_size_t)TOMMY_TRIE_BLOCK_SIZE;
334 : }
335 :
|
