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 <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 }