2 * Copyright (c) 2004 Anders Magnusson (ragge@ludd.luth.se).
3 * Copyright (c) 2009 Joseph Adams (joeyadams3.14159@gmail.com).
6 * Redistribution and use in source and binary forms, with or without
7 * modification, are permitted provided that the following conditions
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
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.
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 */
32 #include "stringmap.h"
37 #define assert(...) do {} while(0)
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
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);
59 void *stringmap_lookup_real(struct stringmap *t, const char *key, int enterf, const size_t T_size) {
61 struct stringmap_node *w, *new, *last;
62 int len, cix, bit, fbit, svbit, ix, bitno;
63 const char *k, *m, *sm;
69 t->bp = block_pool_new(t->bp);
71 t->root = T_new(t->bp, key, T_size);
77 /* Count full string length */
78 for (k = key, len = 0; *k; k++, len++)
86 bitno = len * CHECKBITS;
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);
103 /* Check for correct string and return */
104 for (cix = 0; *m && *k && *m == *k; m++, k++, cix += CHECKBITS)
106 if (*m == 0 && *k == 0) {
107 //if (!enterf && sp->value == NULL)
113 return NULL; /* no string found and do not enter */
116 while ((ix & 1) == 0)
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);
125 if (t->count++ == 1) {
126 new->lr[!bit] = t->root;
127 new->bitno |= (bit ? LEFT_IS_LEAF : RIGHT_IS_LEAF);
129 return (struct T *)new->lr[bit];
136 bitno = BITNO(w->bitno);
137 assert(bitno != cix);
140 svbit = P_BIT(key, bitno);
143 if (fbit & (svbit ? RIGHT_IS_LEAF : LEFT_IS_LEAF))
151 last->lr[svbit] = new;
152 last->bitno &= ~(svbit ? RIGHT_IS_LEAF : LEFT_IS_LEAF);
155 new->bitno |= (bit ? LEFT_IS_LEAF : RIGHT_IS_LEAF);
156 return (struct T *)new->lr[bit];