git.ozlabs.org Git - ccan/blob - 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 }