tdb2: copy tdb1's changed expansion logic.
[ccan] / ccan / stringmap / stringmap.c
1 /*
2  * Copyright (c) 2004 Anders Magnusson (ragge@ludd.luth.se).
3  * Copyright (c) 2009 Joseph Adams (joeyadams3.14159@gmail.com).
4  * All rights reserved.
5  *
6  * Redistribution and use in source and binary forms, with or without
7  * modification, are permitted provided that the following conditions
8  * are met:
9  * 1. Redistributions of source code must retain the above copyright
10  *    notice, this list of conditions and the following disclaimer.
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  * 3. The name of the author may not be used to endorse or promote products
15  *    derived from this software without specific prior written permission
16  *
17  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
18  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
19  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
20  * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
21  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
22  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
23  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
24  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
26  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27  */
28
29 /* This is a heavily modified version of the Patricia tree implementation
30    in PCC at http://pcc.zentus.com/cgi-bin/cvsweb.cgi/cc/cpp/cpp.c?rev=1.96 */
31
32 #include <ccan/stringmap/stringmap.h>
33
34 //#define CONSISTENCY_CHECK
35
36 #if 0
37 #include <assert.h>
38 #else
39 #define assert(...) do {} while(0)
40 #endif
41
42 #define PEEK_BIT(key, bit)              ((key[bit >> 3] >> (~bit & 7)) & 1)
43
44 struct stringmap_node {
45         uint32_t left_is_leaf:1, right_is_leaf:1, bitno:30;
46         struct stringmap_node *lr[2];
47 };
48
49 struct T {
50         char *str;
51         size_t len;
52 };
53
54 static inline struct T *leaf(struct stringmap_node *n, int lr) {
55         assert(lr ? n->right_is_leaf : n->left_is_leaf);
56         return (struct T*)n->lr[lr];
57 }
58
59 /* Normal nodes diverge because there was a 0 or 1 difference. If left_ends(n),
60    then the node diverges because one string ends and the rest don't. */
61 static inline int left_ends(struct stringmap_node *n) {
62         return (n->left_is_leaf && (leaf(n,0)->len << 3)==n->bitno);
63 }
64
65 static void *T_new(struct block_pool *bp, const char *key, size_t len, size_t T_size) {
66         struct T *leaf = block_pool_alloc(bp, T_size);
67         memset(leaf, 0, T_size);
68         
69         leaf->str = block_pool_alloc_align(bp, len+1, 1);
70         memcpy(leaf->str, key, len);
71         leaf->str[len] = 0;
72         leaf->len = len;
73         
74         return leaf;
75 }
76
77 //used for diagnostics
78 static int consistency_check(struct stringmap *t);
79 static void emit_dot(struct stringmap *t);
80 static void emit_subtree(struct stringmap_node *n, int is_leaf);
81
82 void *stringmap_lookup_real(struct stringmap *t, const char *key, size_t len, int enterf, size_t T_size) {
83         struct T *sp;
84         struct stringmap_node *w, *new, *last;
85         uint32_t cix, bit, svbit, ix, bitno, end_bit;
86         const char *k, *m;
87         
88         (void) consistency_check;
89         (void) emit_dot;
90         #ifdef STRINGMAP_EMIT_DOT
91         emit_dot(t);
92         #endif
93         #ifdef CONSISTENCY_CHECK
94         consistency_check(t);
95         #endif
96         
97         /* If key length wasn't supplied, calculate it. */
98         if (len == (size_t)-1)
99                 len = strlen(key);
100         end_bit = len << 3;
101         
102         /* If tree is empty, create the first node. */
103         if (!t->root) {
104                 if (!enterf)
105                         return NULL;
106                 
107                 t->bp = block_pool_new(t->bp);
108                 
109                 t->root = T_new(t->bp, key, len, T_size);
110                 t->count = 1;
111                 
112                 return t->root;
113         }
114         
115         /* Follow the tree down to what might be the target key. */
116         if (t->count == 1) {
117                 w = t->root;
118                 svbit = 0;
119         } else {
120                 w = t->root;
121                 for (;;) {
122                         if (!left_ends(w)) //0 or 1
123                                 bit = w->bitno < end_bit ? PEEK_BIT(key, w->bitno) : 0;
124                         else //ends or doesn't end
125                                 bit = (w->bitno != end_bit);
126                         svbit = bit ? w->right_is_leaf : w->left_is_leaf;
127                         w = w->lr[bit];
128                         if (svbit)
129                                 break;
130                 }
131         }
132         
133         /* See if the strings match.  If not, set cix to the first bit offset
134            where there's a difference, and bit to the side on which to put
135                 this leaf. */
136         sp = (struct T *)w;
137         m = sp->str;
138         k = key;
139         for (cix = 0; ; m++, k++, cix++) {
140                 if (cix>=sp->len || cix>=len) { //we reached the end of one or both strings
141                         if (cix==sp->len && cix==len) { //strings match
142                                 //if (!enterf && sp->value == NULL)
143                                 //      return NULL;
144                                 return sp;
145                         }
146                         cix <<= 3;
147                         
148                         //put the shorter key to the left
149                         bit = len > sp->len;
150                         
151                         break;
152                 }
153                 if (*m != *k) { //the strings have a differing character
154                         cix <<= 3;
155                         
156                         //advance cix to the first differing bit
157                         ix = *m ^ *k;
158                         while ((ix & 128) == 0)
159                                 ix <<= 1, cix++;
160                         
161                         //choose left/right based on the differing bit
162                         bit = PEEK_BIT(key, cix);
163                         
164                         break;
165                 }
166         }
167         
168         if (!enterf)
169                 return NULL; /* no string found and do not enter */
170
171         /* Create new node */
172         new = block_pool_alloc(t->bp, sizeof *new);
173         
174         new->right_is_leaf = bit;
175         new->left_is_leaf = !bit;
176         new->bitno = cix;
177         
178         new->lr[bit] = T_new(t->bp, key, len, T_size);
179
180         if (t->count++ == 1) {
181                 new->lr[!bit] = t->root;
182                 new->right_is_leaf = 1;
183                 new->left_is_leaf = 1;
184                 t->root = new;
185                 return (struct T *)new->lr[bit];
186         }
187
188         w = t->root;
189         last = NULL;
190         for (;;) {
191                 bitno = w->bitno;
192                 if (bitno > cix)
193                         break;
194                 
195                 if (!left_ends(w)) { //0 or 1
196                         if (bitno == cix)
197                                 break;
198                         svbit = PEEK_BIT(key, bitno);
199                         
200                 } else { //ends or doesn't end
201                         //because left is an end, we cannot split it, so we must turn right
202                         svbit = 1;
203                 }
204                 
205                 last = w;
206                 w = w->lr[svbit];
207                 if (svbit ? last->right_is_leaf : last->left_is_leaf) {
208                         //w is a leaf, so mark it accordingly in its parent structure
209                         if (!bit)
210                                 new->right_is_leaf = 1;
211                         else
212                                 new->left_is_leaf = 1;
213                         
214                         break;
215                 }
216         }
217
218         new->lr[!bit] = w;
219         if (last == NULL) {
220                 t->root = new;
221         } else {
222                 last->lr[svbit] = new;
223                 if (svbit)
224                         last->right_is_leaf = 0;
225                 else
226                         last->left_is_leaf = 0;
227         }
228         
229         return (struct T *)new->lr[bit];
230 }
231
232 static int consistency_check_subtree(struct stringmap_node *n) {
233         uint32_t bitno = n->bitno;
234         int success = 1;
235         
236         //make sure bitnos ascend (must ascend unless left ends)
237         if (!n->left_is_leaf && bitno >= n->lr[0]->bitno) {
238                 printf("Left leaf has bitno >= than parent\n");
239                 success = 0;
240         }
241         if (!n->right_is_leaf && bitno >= n->lr[1]->bitno) {
242                 if (left_ends(n) && bitno == n->lr[1]->bitno) {
243                         //fine, there's a shelf here
244                 } else {
245                         printf("Right leaf has bitno >= than parent\n");
246                         success = 0;
247                 }
248         }
249         
250         //make sure eponymous bits are set properly
251         if (n->left_is_leaf) {
252                 struct T *lf = leaf(n, 0);
253                 size_t len = lf->len << 3;
254                 if (len == n->bitno) {
255                         //this is a shelf
256                 } else if (len <= n->bitno) {
257                         printf("Left leaf is too short\n");
258                         success = 0;
259                 } else if (PEEK_BIT(lf->str, n->bitno) == 1) {
260                         printf("Left leaf has incorrect bit\n");
261                         success = 0;
262                 }
263         }
264         if (n->right_is_leaf) {
265                 struct T *lf = leaf(n, 1);
266                 size_t len = lf->len << 3;
267                 if (len <= n->bitno) {
268                         printf("Right leaf is too short\n");
269                         success = 0;
270                 } else if (PEEK_BIT(lf->str, n->bitno) == 0 && !left_ends(n)) {
271                         printf("Right leaf has incorrect bit\n");
272                         success = 0;
273                 }
274         }
275         
276         if (!success) {
277                 //emit_subtree(n, 0);
278                 abort();
279         }
280         
281         //recursively check
282         return (!n->left_is_leaf ? consistency_check_subtree(n->lr[0]) : 1) &&
283               (!n->right_is_leaf ? consistency_check_subtree(n->lr[1]) : 1);
284 }
285
286 static int consistency_check(struct stringmap *t) {
287         if (t->count < 2)
288                 return 1;
289         return consistency_check_subtree(t->root);
290 }
291
292 //The following can be used to create Graphviz "dot" files to visualize the tree
293
294 static void leaf_to_dot(void *lp, FILE *f) {
295         struct T *leaf = lp;
296         size_t bit_count = leaf->len << 3;
297         size_t i;
298         
299         fputs("\"", f);
300         #if 1
301         for (i=0; i<bit_count; i++) {
302                 putc(PEEK_BIT(leaf->str, i) ? '1' : '0', f);
303                 if (((i+1) & 7) == 0)
304                         fputs("\\n", f); //add newlines between bytes
305         }
306         putc(' ', f);
307         #endif
308         fprintf(f, "(%s)\"\n", leaf->str);
309 }
310
311 static void node_to_dot(struct stringmap_node *n, FILE *f, size_t level) {
312         //don't draw ridiculously huge trees
313         if (level > 4)
314                 return;
315         
316         fprintf(f, "%zu [label=\"[%zu] %u\"]\n", (size_t)n, level, n->bitno);
317         
318         if (n->left_is_leaf) {
319                 fprintf(f, "%zu -> ", (size_t)n);
320                 leaf_to_dot(n->lr[0], f);
321         } else {
322                 fprintf(f, "%zu -> %zu \n", (size_t)n, (size_t)n->lr[0]);
323                 node_to_dot(n->lr[0], f, level+1);
324         }
325         
326         if (n->right_is_leaf) {
327                 fprintf(f, "%zu -> ", (size_t)n);
328                 leaf_to_dot(n->lr[1], f);
329         } else {
330                 fprintf(f, "%zu -> %zu \n", (size_t)n, (size_t)n->lr[1]);
331                 node_to_dot(n->lr[1], f, level+1);
332         }
333 }
334
335 static void stringmap_subtree_to_dot(struct stringmap_node *n, int is_leaf, const char *filename_out) {
336         FILE *f = fopen(filename_out, "w");
337         
338         fputs("digraph G {\n", f);
339         
340         if (is_leaf)
341                 leaf_to_dot(n, f);
342         else
343                 node_to_dot(n, f, 0);
344         
345         fputs("}\n", f);
346         fclose(f);
347 }
348
349 static size_t dot_file_number = 0;
350
351 static void emit_subtree(struct stringmap_node *n, int is_leaf) {
352         char buf[64];
353         sprintf(buf, "dot/%04zu.dot", dot_file_number++);
354         stringmap_subtree_to_dot(n, is_leaf, buf);
355 }
356
357 static void emit_dot(struct stringmap *t) {
358         if (t->count)
359                 emit_subtree(t->root, t->count==1);
360 }