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 "tommytrieinp.h"
29 :
30 : #include <assert.h> /* for assert */
31 :
32 : /******************************************************************************/
33 : /* trie_inplace */
34 :
35 : /**
36 : * Mask for the inner branches.
37 : */
38 : #define TOMMY_TRIE_INPLACE_TREE_MASK (TOMMY_TRIE_INPLACE_TREE_MAX - 1)
39 :
40 : /**
41 : * Shift for the first level of branches.
42 : */
43 : #define TOMMY_TRIE_INPLACE_BUCKET_SHIFT (TOMMY_TRIE_INPLACE_BIT - TOMMY_TRIE_INPLACE_BUCKET_BIT)
44 :
45 : /**
46 : * Create a new list with a single element.
47 : */
48 4000000 : tommy_inline tommy_trie_inplace_node* tommy_trie_inplace_list_insert_first(tommy_trie_inplace_node* node)
49 : {
50 : /* one element "circular" prev list */
51 4000000 : node->prev = node;
52 :
53 : /* one element "0 terminated" next list */
54 4000000 : node->next = 0;
55 :
56 4000000 : return node;
57 : }
58 :
59 : /**
60 : * Add an element to an existing list.
61 : * \note The element is inserted at the end of the list.
62 : */
63 2 : tommy_inline void tommy_trie_inplace_list_insert_tail_not_empty(tommy_trie_inplace_node* head, tommy_trie_inplace_node* node)
64 : {
65 : /* insert in the list in the last position */
66 :
67 : /* insert in the "circular" prev list */
68 2 : node->prev = head->prev;
69 2 : head->prev = node;
70 :
71 : /* insert in the "0 terminated" next list */
72 2 : node->next = 0;
73 2 : node->prev->next = node;
74 2 : }
75 :
76 : /**
77 : * Remove an element from the list.
78 : */
79 4000002 : tommy_inline void tommy_trie_inplace_list_remove(tommy_trie_inplace_node** let_ptr, tommy_trie_inplace_node* node)
80 : {
81 4000002 : tommy_trie_inplace_node* head = *let_ptr;
82 :
83 : /* remove from the "circular" prev list */
84 4000002 : if (node->next)
85 2 : node->next->prev = node->prev;
86 : else
87 4000000 : head->prev = node->prev; /* the last */
88 :
89 : /* remove from the "0 terminated" next list */
90 4000002 : if (head == node)
91 4000001 : *let_ptr = node->next; /* the new first */
92 : else
93 1 : node->prev->next = node->next;
94 4000002 : }
95 :
96 1 : void tommy_trie_inplace_init(tommy_trie_inplace* trie_inplace)
97 : {
98 : tommy_uint_t i;
99 :
100 65 : for (i = 0; i < TOMMY_TRIE_INPLACE_BUCKET_MAX; ++i)
101 64 : trie_inplace->bucket[i] = 0;
102 :
103 1 : trie_inplace->count = 0;
104 1 : }
105 :
106 4000002 : static void trie_inplace_bucket_insert(tommy_uint_t shift, tommy_trie_inplace_node** let_ptr, tommy_trie_inplace_node* insert, tommy_key_t key)
107 : {
108 : tommy_trie_inplace_node* node;
109 :
110 4000002 : node = *let_ptr;
111 62226086 : while (node && node->key != key) {
112 54226082 : let_ptr = &node->map[(key >> shift) & TOMMY_TRIE_INPLACE_TREE_MASK];
113 54226082 : node = *let_ptr;
114 54226082 : shift -= TOMMY_TRIE_INPLACE_TREE_BIT;
115 : }
116 :
117 : /* if null, just insert the node */
118 4000002 : if (!node) {
119 : /* setup the node as a list */
120 4000000 : *let_ptr = tommy_trie_inplace_list_insert_first(insert);
121 : } else {
122 : /* if it's the same key, insert in the list */
123 2 : tommy_trie_inplace_list_insert_tail_not_empty(node, insert);
124 : }
125 4000002 : }
126 :
127 4000002 : void tommy_trie_inplace_insert(tommy_trie_inplace* trie_inplace, tommy_trie_inplace_node* node, void* data, tommy_key_t key)
128 : {
129 : tommy_trie_inplace_node** let_ptr;
130 : tommy_uint_t i;
131 :
132 : /* ensure that the element is not too big */
133 4000002 : assert(key >> TOMMY_TRIE_INPLACE_BUCKET_SHIFT < TOMMY_TRIE_INPLACE_BUCKET_MAX);
134 :
135 4000002 : node->data = data;
136 4000002 : node->key = key;
137 : /* clear the child pointers */
138 20000010 : for (i = 0; i < TOMMY_TRIE_INPLACE_TREE_MAX; ++i)
139 16000008 : node->map[i] = 0;
140 :
141 4000002 : let_ptr = &trie_inplace->bucket[key >> TOMMY_TRIE_INPLACE_BUCKET_SHIFT];
142 :
143 4000002 : trie_inplace_bucket_insert(TOMMY_TRIE_INPLACE_BUCKET_SHIFT, let_ptr, node, key);
144 :
145 4000002 : ++trie_inplace->count;
146 4000002 : }
147 :
148 6000002 : static tommy_trie_inplace_node* trie_inplace_bucket_remove(tommy_uint_t shift, tommy_trie_inplace_node** let_ptr, tommy_trie_inplace_node* remove, tommy_key_t key)
149 : {
150 : tommy_trie_inplace_node* node;
151 : int i;
152 : tommy_trie_inplace_node** leaf_let_ptr;
153 : tommy_trie_inplace_node* leaf;
154 :
155 6000002 : node = *let_ptr;
156 73636434 : while (node && node->key != key) {
157 61636430 : let_ptr = &node->map[(key >> shift) & TOMMY_TRIE_INPLACE_TREE_MASK];
158 61636430 : node = *let_ptr;
159 61636430 : shift -= TOMMY_TRIE_INPLACE_TREE_BIT;
160 : }
161 :
162 6000002 : if (!node)
163 2000000 : return 0;
164 :
165 : /* if the node to remove is not specified */
166 4000002 : if (!remove)
167 2000000 : remove = node; /* remove the first */
168 :
169 4000002 : tommy_trie_inplace_list_remove(let_ptr, remove);
170 :
171 : /* if not change in the node, nothing more to do */
172 4000002 : if (*let_ptr == node)
173 1 : return remove;
174 :
175 : /* if we have a substitute */
176 4000001 : if (*let_ptr != 0) {
177 : /* copy the child pointers to the new one */
178 1 : node = *let_ptr;
179 5 : for (i = 0; i < TOMMY_TRIE_INPLACE_TREE_MAX; ++i)
180 4 : node->map[i] = remove->map[i];
181 :
182 1 : return remove;
183 : }
184 :
185 : /* find a leaf */
186 4000000 : leaf_let_ptr = 0;
187 4000000 : leaf = remove;
188 :
189 : /* search backward, statistically we have more zeros than ones */
190 4000000 : i = TOMMY_TRIE_INPLACE_TREE_MAX - 1;
191 26120471 : while (i >= 0) {
192 18120471 : if (leaf->map[i]) {
193 1742548 : leaf_let_ptr = &leaf->map[i];
194 1742548 : leaf = *leaf_let_ptr;
195 1742548 : i = TOMMY_TRIE_INPLACE_TREE_MAX - 1;
196 1742548 : continue;
197 : }
198 16377923 : --i;
199 : }
200 :
201 : /* if it's itself a leaf */
202 4000000 : if (!leaf_let_ptr)
203 2698033 : return remove;
204 :
205 : /* remove the leaf */
206 1301967 : *leaf_let_ptr = 0;
207 :
208 : /* copy the child pointers */
209 6509835 : for (i = 0; i < TOMMY_TRIE_INPLACE_TREE_MAX; ++i)
210 5207868 : leaf->map[i] = remove->map[i];
211 :
212 : /* put it in place */
213 1301967 : *let_ptr = leaf;
214 :
215 1301967 : return remove;
216 : }
217 :
218 4000000 : void* tommy_trie_inplace_remove(tommy_trie_inplace* trie_inplace, tommy_key_t key)
219 : {
220 : tommy_trie_inplace_node* ret;
221 : tommy_trie_inplace_node** let_ptr;
222 :
223 : /* ensure that the element is not too big */
224 4000000 : assert(key >> TOMMY_TRIE_INPLACE_BUCKET_SHIFT < TOMMY_TRIE_INPLACE_BUCKET_MAX);
225 :
226 4000000 : let_ptr = &trie_inplace->bucket[key >> TOMMY_TRIE_INPLACE_BUCKET_SHIFT];
227 :
228 4000000 : ret = trie_inplace_bucket_remove(TOMMY_TRIE_INPLACE_BUCKET_SHIFT, let_ptr, 0, key);
229 :
230 4000000 : if (!ret)
231 2000000 : return 0;
232 :
233 2000000 : --trie_inplace->count;
234 :
235 2000000 : return ret->data;
236 : }
237 :
238 2000002 : void* tommy_trie_inplace_remove_existing(tommy_trie_inplace* trie_inplace, tommy_trie_inplace_node* node)
239 : {
240 : tommy_trie_inplace_node* ret;
241 2000002 : tommy_key_t key = node->key;
242 : tommy_trie_inplace_node** let_ptr;
243 :
244 : /* ensure that the element is not too big */
245 2000002 : assert(key >> TOMMY_TRIE_INPLACE_BUCKET_SHIFT < TOMMY_TRIE_INPLACE_BUCKET_MAX);
246 :
247 2000002 : let_ptr = &trie_inplace->bucket[key >> TOMMY_TRIE_INPLACE_BUCKET_SHIFT];
248 :
249 2000002 : ret = trie_inplace_bucket_remove(TOMMY_TRIE_INPLACE_BUCKET_SHIFT, let_ptr, node, key);
250 :
251 : /* the element removed must match the one passed */
252 2000002 : assert(ret == node);
253 :
254 2000002 : --trie_inplace->count;
255 :
256 2000002 : return ret->data;
257 : }
258 :
259 4000000 : tommy_trie_inplace_node* tommy_trie_inplace_bucket(tommy_trie_inplace* trie_inplace, tommy_key_t key)
260 : {
261 : tommy_trie_inplace_node* node;
262 : tommy_uint_t shift;
263 :
264 : /* ensure that the element is not too big */
265 4000000 : assert(key >> TOMMY_TRIE_INPLACE_BUCKET_SHIFT < TOMMY_TRIE_INPLACE_BUCKET_MAX);
266 :
267 4000000 : node = trie_inplace->bucket[key >> TOMMY_TRIE_INPLACE_BUCKET_SHIFT];
268 4000000 : shift = TOMMY_TRIE_INPLACE_BUCKET_SHIFT;
269 :
270 44265902 : while (node && node->key != key) {
271 36265902 : node = node->map[(key >> shift) & TOMMY_TRIE_INPLACE_TREE_MASK];
272 36265902 : shift -= TOMMY_TRIE_INPLACE_TREE_BIT;
273 : }
274 :
275 4000000 : return node;
276 : }
277 :
278 1 : tommy_size_t tommy_trie_inplace_memory_usage(tommy_trie_inplace* trie_inplace)
279 : {
280 1 : return tommy_trie_inplace_count(trie_inplace) * (tommy_size_t)sizeof(tommy_trie_inplace_node);
281 : }
282 :
|
