Merge.
[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 "stringmap.h"
33
34 #if 0
35 #include <assert.h>
36 #else
37 #define assert(...) do {} while(0)
38 #endif
39
40 #define BITNO(x)                ((x) & ~(LEFT_IS_LEAF|RIGHT_IS_LEAF))
41 #define LEFT_IS_LEAF            0x80000000
42 #define RIGHT_IS_LEAF           0x40000000
43 #define IS_LEFT_LEAF(x)         (((x) & LEFT_IS_LEAF) != 0)
44 #define IS_RIGHT_LEAF(x)        (((x) & RIGHT_IS_LEAF) != 0)
45 #define P_BIT(key, bit)         (key[bit >> 3] >> (bit & 7)) & 1
46 #define CHECKBITS               8
47
48 struct T {
49         char *str;
50 };
51
52 static void *T_new(struct block_pool *bp, const char *key, size_t T_size) {
53         struct T *leaf = block_pool_alloc(bp, T_size);
54         memset(leaf, 0, T_size);
55         leaf->str = block_pool_strdup(bp, key);
56         return leaf;
57 }
58
59 void *stringmap_lookup_real(struct stringmap *t, const char *key, int enterf, const size_t T_size) {
60         struct T *sp;
61         struct stringmap_node *w, *new, *last;
62         int len, cix, bit, fbit, svbit, ix, bitno;
63         const char *k, *m, *sm;
64         
65         if (!t->root) {
66                 if (!enterf)
67                         return NULL;
68                 
69                 t->bp = block_pool_new(t->bp);
70                 
71                 t->root = T_new(t->bp, key, T_size);
72                 t->count = 1;
73                 
74                 return t->root;
75         }
76
77         /* Count full string length */
78         for (k = key, len = 0; *k; k++, len++)
79                 ;
80         
81         if (t->count == 1) {
82                 w = t->root;
83                 svbit = 0;
84         } else {
85                 w = t->root;
86                 bitno = len * CHECKBITS;
87                 for (;;) {
88                         bit = BITNO(w->bitno);
89                         fbit = bit > bitno ? 0 : P_BIT(key, bit);
90                         svbit = fbit ? IS_RIGHT_LEAF(w->bitno) :
91                             IS_LEFT_LEAF(w->bitno);
92                         w = w->lr[fbit];
93                         if (svbit)
94                                 break;
95                 }
96         }
97
98         sp = (struct T *)w;
99
100         sm = m = sp->str;
101         k = key;
102
103         /* Check for correct string and return */
104         for (cix = 0; *m && *k && *m == *k; m++, k++, cix += CHECKBITS)
105                 ;
106         if (*m == 0 && *k == 0) {
107                 //if (!enterf && sp->value == NULL)
108                 //      return NULL;
109                 return sp;
110         }
111
112         if (!enterf)
113                 return NULL; /* no string found and do not enter */
114
115         ix = *m ^ *k;
116         while ((ix & 1) == 0)
117                 ix >>= 1, cix++;
118
119         /* Create new node */
120         new = block_pool_alloc(t->bp, sizeof *new);
121         bit = P_BIT(key, cix);
122         new->bitno = cix | (bit ? RIGHT_IS_LEAF : LEFT_IS_LEAF);
123         new->lr[bit] = T_new(t->bp, key, T_size);
124
125         if (t->count++ == 1) {
126                 new->lr[!bit] = t->root;
127                 new->bitno |= (bit ? LEFT_IS_LEAF : RIGHT_IS_LEAF);
128                 t->root = new;
129                 return (struct T *)new->lr[bit];
130         }
131
132         w = t->root;
133         last = NULL;
134         for (;;) {
135                 fbit = w->bitno;
136                 bitno = BITNO(w->bitno);
137                 assert(bitno != cix);
138                 if (bitno > cix)
139                         break;
140                 svbit = P_BIT(key, bitno);
141                 last = w;
142                 w = w->lr[svbit];
143                 if (fbit & (svbit ? RIGHT_IS_LEAF : LEFT_IS_LEAF))
144                         break;
145         }
146
147         new->lr[!bit] = w;
148         if (last == NULL) {
149                 t->root = new;
150         } else {
151                 last->lr[svbit] = new;
152                 last->bitno &= ~(svbit ? RIGHT_IS_LEAF : LEFT_IS_LEAF);
153         }
154         if (bitno < cix)
155                 new->bitno |= (bit ? LEFT_IS_LEAF : RIGHT_IS_LEAF);
156         return (struct T *)new->lr[bit];
157 }