ucw/trie.h

   1 /*
   2  *      UCW Library -- Byte-based trie
   3  *
   4  *      (c) 2008 Pavel Charvat <pchar@ucw.cz>
   5  *
   6  *      This software may be freely distributed and used according to the terms
   7  *      of the GNU Lesser General Public License.
   8  */
   9
  10 /*
  11  *      This is not a normal header file, it's a generator of tries.
  12  *      Each time you include it with parameters set in the corresponding
  13  *      preprocessor macros, it generates a trie with the parameters given.
  14  *
  15  *      You need to specify:
  16  *
  17  *      [*] TRIE_PREFIX(x)              macro to add a name prefix (used on all global names
  18  *                                      defined by the trie generator).
  19  *
  20  *      [*] TRIE_NODE_TYPE              data type where a node dwells (usually a struct).
  21  *          TRIE_NODE_KEY(node)         macro to return the pointer to the key (default=&x)
  22  *          TRIE_NODE_LEN(node)         macro to return the length of the key (default=str_len(TRIE_NODE_KEY(node)))
  23  *          TRIE_LEN_TYPE               integer type large enough to hold length of any inserted string (default=u32).
  24  *          TRIE_REV                    work with reversed strings.
  25  *          TRIE_DYNAMIC
  26  *
  27  *          TRIE_WANT_CLEANUP           cleanup()
  28  *
  29  *          TRIE_WANT_FIND              node *find(char *str)
  30  *          TRIE_WANT_FIND_BUF          node *find_buf(byte *ptr, uint len)
  31  *          TRIE_WANT_ADD               add(*node)
  32  *          TRIE_WANT_REPLACE           node *replace(*node)
  33  *          TRIE_WANT_DELETE            delete(char *str)
  34  *          TRIE_WANT_DELETE_BUF        delete_buf(byte *ptr, uint len)
  35  *          TRIE_WANT_REMOVE            remove(*node)
  36  *
  37  *          TRIE_WANT_AUDIT             audit()
  38  *          TRIE_WANT_STATS
  39  *
  40  *      Be warned that the implementation uses alloca() in several macros,
  41  *      so if you use automatic variable-length arrays in the same function,
  42  *      all the hell may be unleashed.
  43  */
  44
  45 /*** Define once ***/
  46
  47 #ifndef _SHERLOCK_UCW_TRIE_H
  48 #define _SHERLOCK_UCW_TRIE_H
  49
  50 #include <ucw/eltpool.h>
  51 #include <ucw/hashfunc.h>
  52
  53 #include <string.h>
  54
  55 #define TRIE_FLAG_DEG           0x01ff  // mask for edge degree (0-256)
  56 #define TRIE_FLAG_HASH          0x0200  // sons are stored in a hash table
  57 #define TRIE_FLAG_NODE          0x0400  // edge contains inserted data
  58
  59 #endif
  60
  61 /*** Defaults ***/
  62
  63 #ifndef TRIE_PREFIX
  64 #error Undefined mandatory macro TRIE_PREFIX
  65 #endif
  66 #define P(x) TRIE_PREFIX(x)
  67
  68 #ifndef TRIE_NODE_TYPE
  69 #error Undefined mandatory macro TRIE_NODE_TYPE
  70 #endif
  71 typedef TRIE_NODE_TYPE P(node_t);
  72
  73 #ifndef TRIE_NODE_KEY
  74 #define TRIE_NODE_KEY(node) ((char *)&(node))
  75 #endif
  76
  77 #ifndef TRIE_NODE_LEN
  78 #define TRIE_NODE_LEN(node) (str_len(TRIE_NODE_KEY(node)))
  79 #endif
  80
  81 #ifndef TRIE_LEN_TYPE
  82 #define TRIE_LEN_TYPE u32
  83 #endif
  84 typedef TRIE_LEN_TYPE P(len_t);
  85
  86 #ifndef TRIE_ELTPOOL_SIZE
  87 #define TRIE_ELTPOOL_SIZE 1024
  88 #endif
  89
  90 #ifndef TRIE_HASH_THRESHOLD
  91 #define TRIE_HASH_THRESHOLD (6 - sizeof(P(len_t)))
  92 #endif
  93
  94 #ifndef TRIE_BUCKET_RANK
  95 #define TRIE_BUCKET_RANK (2U + (sizeof(void *) > 4))
  96 #endif
  97 #define TRIE_BUCKET_SIZE (1U << TRIE_BUCKET_RANK)
  98 #define TRIE_BUCKET_MASK (TRIE_BUCKET_SIZE - 1)
  99 enum { P(bucket_rank) = TRIE_BUCKET_RANK };
 100
 101 #define TRIE_COMPILE_ASSERT(x, y) typedef char TRIE_PREFIX(x##_compile_assert)[!!(y)-1]
 102 TRIE_COMPILE_ASSERT(len_type, sizeof(P(len_t)) <= sizeof(uint));
 103 TRIE_COMPILE_ASSERT(hash_threshold, TRIE_HASH_THRESHOLD >= 2);
 104 TRIE_COMPILE_ASSERT(bucket_size, TRIE_BUCKET_RANK >= 1 && TRIE_BUCKET_MASK < sizeof(void *));
 105
 106 #ifdef TRIE_TRACE
 107 #define TRIE_DBG(x...) msg(L_DEBUG, "TRIE: " x)
 108 #else
 109 #define TRIE_DBG(x...) do{}while(0)
 110 #endif
 111
 112 /*** Solve dependencies ***/
 113
 114 #if !defined(TRIE_WANT_DO_FIND) && (defined(TRIE_WANT_FIND) || defined(TRIE_WANT_FIND_BUF))
 115 #define TRIE_WANT_DO_FIND
 116 #endif
 117
 118 #if !defined(TRIE_WANT_DO_LOOKUP) && (defined(TRIE_WANT_ADD) || defined(TRIE_WANT_REPLACE))
 119 #define TRIE_WANT_DO_LOOKUP
 120 #endif
 121
 122 #if !defined(TRIE_WANT_DO_DELETE) && (defined(TRIE_WANT_DELETE) || defined(TRIE_WANT_DELETE_BUF) || defined(TRIE_WANT_REMOVE))
 123 #define TRIE_WANT_DO_DELETE
 124 #endif
 125
 126 #if !defined(TRIE_WANT_DO_LOOKUP)
 127 #error You must request at least one method for inserting nodes
 128 #endif
 129
 130 /*** Data structures ***/
 131
 132 struct P(trie) {
 133   struct P(edge) *root;                         // root edge or NULL
 134   struct eltpool *epool[TRIE_HASH_THRESHOLD + 1]; // eltpools for edges with array of sons
 135   struct eltpool *hpool[9];                     // eltpools for edges with hash table
 136 };
 137
 138 struct P(edge) {
 139   u16 flags;                                    // TRIE_FLAG_x
 140   union {
 141     byte trans[TRIE_HASH_THRESHOLD];            // transition characters (!TRIE_FLAG_HASH)
 142     struct {
 143       byte hash_rank;                           // logarithmic hash size (TRIE_FLAG_HASH)
 144       byte hash_deleted;                        // number of deleted items
 145     };
 146   };
 147   P(len_t) len;                                 // sum of all ancestor edges with their trasition
 148                                                 //   characters plus the length of the current edge
 149   union {
 150     P(node_t) *node;                            // inserted data (TRIE_FLAG_NODE)
 151     struct P(edge) *leaf;                       // reference to a descendant with data (!TRIE_FLAG_NODE)
 152   };
 153   struct P(edge) *son[0];                       // array of sons (!TRIE_FLAG_HASH)
 154                                                 //   or hash table (TRIE_FLAG_HASH)
 155 };
 156
 157 #ifdef TRIE_DYNAMIC
 158 #define T (*trie)
 159 #define TA struct P(trie) *trie
 160 #define TAC TA,
 161 #define TT trie
 162 #define TTC trie,
 163 #else
 164 static struct P(trie) P(trie);
 165 #define T P(trie)
 166 #define TA void
 167 #define TAC
 168 #define TT
 169 #define TTC
 170 #endif
 171
 172 /*** Memory management ***/
 173
 174 static void
 175 P(init)(TA)
 176 {
 177   TRIE_DBG("Initializing");
 178   bzero(&T, sizeof(T));
 179   for (uint i = 0; i < ARRAY_SIZE(T.epool); i++)
 180     {
 181       uint size = sizeof(struct P(edge)) + i * sizeof(void *);
 182       T.epool[i] = ep_new(size, MAX(TRIE_ELTPOOL_SIZE / size, 1));
 183     }
 184   for (uint i = 0; i < ARRAY_SIZE(T.hpool); i++)
 185     {
 186       uint size = sizeof(struct P(edge)) + ((sizeof(void *) << TRIE_BUCKET_RANK) << i);
 187       T.hpool[i] = ep_new(size, MAX(TRIE_ELTPOOL_SIZE / size, 1));
 188     }
 189 }
 190
 191 #ifdef TRIE_WANT_CLEANUP
 192 static void
 193 P(cleanup)(TA)
 194 {
 195   TRIE_DBG("Cleaning up");
 196   for (uint i = 0; i < ARRAY_SIZE(T.epool); i++)
 197     ep_delete(T.epool[i]);
 198   for (uint i = 0; i < ARRAY_SIZE(T.hpool); i++)
 199     ep_delete(T.hpool[i]);
 200 }
 201 #endif
 202
 203 static struct P(edge) *
 204 P(edge_alloc)(TAC uint flags)
 205 {
 206   struct P(edge) *edge;
 207   if (flags & TRIE_FLAG_HASH)
 208     {
 209       uint rank = 0, deg = flags & TRIE_FLAG_DEG;
 210       while ((TRIE_BUCKET_MASK << rank) < deg * 2) // 25-50% density
 211         rank++;
 212       ASSERT(rank < ARRAY_SIZE(T.hpool));
 213       edge = ep_alloc(T.hpool[rank]);
 214       edge->hash_rank = rank;
 215       edge->hash_deleted = 0;
 216       bzero(edge->son, (sizeof(void *) << TRIE_BUCKET_RANK) << rank);
 217     }
 218   else
 219     edge = ep_alloc(T.epool[flags & TRIE_FLAG_DEG]);
 220   edge->flags = flags;
 221   TRIE_DBG("Allocated edge %p, flags=0x%x", edge, flags);
 222   return edge;
 223 }
 224
 225 static void
 226 P(edge_free)(TAC struct P(edge) *edge)
 227 {
 228   TRIE_DBG("Freeing edge %p, flags=0x%x", edge, edge->flags);
 229   if (edge->flags & TRIE_FLAG_HASH)
 230     ep_free(T.hpool[edge->hash_rank], edge);
 231   else
 232     ep_free(T.epool[edge->flags & TRIE_FLAG_DEG], edge);
 233 }
 234
 235 /*** Manipulation with strings ***/
 236
 237 static inline byte *
 238 P(str_get)(P(node_t) *node)
 239 {
 240   return TRIE_NODE_KEY((*node));
 241 }
 242
 243 static inline uint
 244 P(str_len)(P(node_t) *node)
 245 {
 246   return TRIE_NODE_LEN((*node));
 247 }
 248
 249 static inline uint
 250 P(str_char)(byte *ptr, uint len UNUSED, uint pos)
 251 {
 252 #ifndef TRIE_REV
 253   return ptr[pos];
 254 #else
 255   return ptr[len - pos - 1];
 256 #endif
 257 }
 258
 259 static inline byte *
 260 P(str_prefix)(byte *ptr, uint len UNUSED, uint prefix UNUSED)
 261 {
 262 #ifndef TRIE_REV
 263   return ptr;
 264 #else
 265   return ptr + len - prefix;
 266 #endif
 267 }
 268
 269 static inline byte *
 270 P(str_suffix)(byte *ptr, uint len UNUSED, uint suffix UNUSED)
 271 {
 272 #ifndef TRIE_REV
 273   return ptr + len - suffix;
 274 #else
 275   return ptr;
 276 #endif
 277 }
 278
 279 static inline uint
 280 P(common_prefix)(byte *ptr1, uint len1, byte *ptr2, uint len2)
 281 {
 282   uint l = MIN(len1, len2), i;
 283   for (i = 0; i < l; i++)
 284     if (P(str_char)(ptr1, len1, i) != P(str_char)(ptr2, len2, i))
 285       break;
 286   return i;
 287 }
 288
 289 /*** Sons ***/
 290
 291 static inline uint
 292 P(hash_func)(uint c)
 293 {
 294   return hash_u32(c) >> 16;
 295 }
 296
 297 static inline struct P(edge) **
 298 P(hash_find)(struct P(edge) *edge, uint c)
 299 {
 300   uint mask = (TRIE_BUCKET_SIZE << edge->hash_rank) - 1;
 301   for (uint i = P(hash_func)(c); ; i++)
 302     if (((i &= mask) & TRIE_BUCKET_MASK) && (uintptr_t)edge->son[i] != 1)
 303       if (!edge->son[i])
 304         return NULL;
 305       else if (((byte *)&edge->son[i & ~TRIE_BUCKET_MASK])[i & TRIE_BUCKET_MASK] == c)
 306         return &edge->son[i];
 307 }
 308
 309 static inline struct P(edge) **
 310 P(hash_insert)(struct P(edge) *edge, uint c)
 311 {
 312   uint mask = (TRIE_BUCKET_SIZE << edge->hash_rank) - 1;
 313   for (uint i = P(hash_func)(c); ; i++)
 314     if (((i &= mask) & TRIE_BUCKET_MASK) && (uintptr_t)edge->son[i] <= 1)
 315       {
 316         edge->hash_deleted -= (uintptr_t)edge->son[i];
 317         edge->son[i] = NULL;
 318         ((byte *)&edge->son[i & ~TRIE_BUCKET_MASK])[i & TRIE_BUCKET_MASK] = c;
 319         return &edge->son[i];
 320       }
 321 }
 322
 323 #ifdef TRIE_WANT_DO_DELETE
 324 static inline void
 325 P(hash_delete)(struct P(edge) *edge, uint c)
 326 {
 327   uint mask = (TRIE_BUCKET_SIZE << edge->hash_rank) - 1;
 328   for (uint i = P(hash_func)(c); ; i++)
 329     if (((i &= mask) & TRIE_BUCKET_MASK) && (uintptr_t)edge->son[i] > 1 &&
 330       ((byte *)&edge->son[i & ~TRIE_BUCKET_MASK])[i & TRIE_BUCKET_MASK] == c)
 331       {
 332         edge->hash_deleted++;
 333         edge->son[i] = (void *)1;
 334         return;
 335       }
 336 }
 337 #endif
 338
 339 #define TRIE_HASH_FOR_ALL(xedge, xtrans, xson) do { \
 340   struct P(edge) *_edge = (xedge); \
 341   for (uint _i = (TRIE_BUCKET_SIZE << _edge->hash_rank); _i--; ) \
 342     if ((_i & TRIE_BUCKET_MASK) && (uintptr_t)_edge->son[_i] > 1) { \
 343       UNUSED uint xtrans = ((byte *)&_edge->son[_i & ~TRIE_BUCKET_MASK])[_i & TRIE_BUCKET_MASK]; \
 344       UNUSED struct P(edge) *xson = _edge->son[_i]; \
 345       do {
 346 #define TRIE_HASH_END_FOR }while(0);}}while(0)
 347
 348 static void
 349 P(hash_realloc)(TAC struct P(edge) **ref)
 350 {
 351   struct P(edge) *old = *ref, *edge = *ref = P(edge_alloc)(TTC old->flags);
 352   TRIE_DBG("Reallocating hash table");
 353   edge->node = old->node;
 354   edge->len = old->len;
 355   TRIE_HASH_FOR_ALL(old, trans, son)
 356     *P(hash_insert)(edge, trans) = son;
 357   TRIE_HASH_END_FOR;
 358   P(edge_free)(TTC old);
 359 }
 360
 361 /*** Finding/inserting/deleting sons ***/
 362
 363 static struct P(edge) **
 364 P(son_find)(struct P(edge) *edge, uint c)
 365 {
 366   if (edge->flags & TRIE_FLAG_HASH)
 367     return P(hash_find)(edge, c);
 368   else
 369     for (uint i = edge->flags & TRIE_FLAG_DEG; i--; )
 370       if (edge->trans[i] == c)
 371         return &edge->son[i];
 372   return NULL;
 373 }
 374
 375 static struct P(edge) **
 376 P(son_insert)(TAC struct P(edge) **ref, uint c)
 377 {
 378   struct P(edge) *old = *ref, *edge;
 379   uint deg = old->flags & TRIE_FLAG_DEG;
 380   if (old->flags & TRIE_FLAG_HASH)
 381     {
 382       old->flags++;
 383       if ((deg + 1 + old->hash_deleted) * 4 > (TRIE_BUCKET_MASK << old->hash_rank) * 3) // >75% density
 384         {
 385           P(hash_realloc)(TTC ref);
 386           edge = *ref;
 387         }
 388       else
 389         edge = old;
 390     }
 391   else
 392     {
 393       if (deg < TRIE_HASH_THRESHOLD)
 394         {
 395           TRIE_DBG("Growing array");
 396           edge = P(edge_alloc)(TTC old->flags + 1);
 397           memcpy((byte *)edge + sizeof(edge->flags), (byte *)old + sizeof(edge->flags),
 398             sizeof(*old) - sizeof(edge->flags) + deg * sizeof(*old->son));
 399           edge->trans[deg] = c;
 400           edge->son[deg] = NULL;
 401           P(edge_free)(TTC old);
 402           *ref = edge;
 403           return &edge->son[deg];
 404         }
 405       else
 406         {
 407           TRIE_DBG("Growing array to hash table");
 408           edge = P(edge_alloc)(TTC (old->flags + 1) | TRIE_FLAG_HASH);
 409           edge->node = old->node;
 410           edge->len = old->len;
 411           for (uint i = 0; i < deg; i++)
 412             *P(hash_insert)(edge, old->trans[i]) = old->son[i];
 413           P(edge_free)(TTC old);
 414         }
 415     }
 416   *ref = edge;
 417   return P(hash_insert)(edge, c);
 418 }
 419
 420 #ifdef TRIE_WANT_DO_DELETE
 421 static void
 422 P(son_delete)(TAC struct P(edge) **ref, uint c)
 423 {
 424   struct P(edge) *old = *ref, *edge;
 425   uint deg = old->flags & TRIE_FLAG_DEG;
 426   ASSERT(deg);
 427   if (old->flags & TRIE_FLAG_HASH)
 428     {
 429       P(hash_delete)(old, c);
 430       old->flags--;
 431       deg--;
 432       if (deg <= TRIE_HASH_THRESHOLD / 2)
 433         {
 434           TRIE_DBG("Reducing hash table to array");
 435           edge = P(edge_alloc)(TTC old->flags & ~TRIE_FLAG_HASH);
 436           uint k = 0;
 437           TRIE_HASH_FOR_ALL(old, trans, son)
 438             edge->trans[k] = trans;
 439             edge->son[k] = son;
 440             k++;
 441           TRIE_HASH_END_FOR;
 442           ASSERT(k == deg);
 443         }
 444       else if (deg * 6 >= (TRIE_BUCKET_MASK << old->hash_rank)) // >= 16%
 445         return;
 446       else
 447         {
 448           P(hash_realloc)(TTC ref);
 449           edge = *ref;
 450           return;
 451         }
 452     }
 453   else
 454     {
 455       TRIE_DBG("Reducing array");
 456       edge = P(edge_alloc)(TTC old->flags - 1);
 457       uint j = 0;
 458       for (uint i = 0; i < deg; i++)
 459         if (old->trans[i] != c)
 460           {
 461             edge->trans[j] = old->trans[i];
 462             edge->son[j] = old->son[i];
 463             j++;
 464           }
 465       ASSERT(j == deg - 1);
 466     }
 467   edge->node = old->node;
 468   edge->len = old->len;
 469   P(edge_free)(TTC old);
 470   *ref = edge;
 471 }
 472 #endif
 473
 474 #ifdef TRIE_WANT_DO_DELETE
 475 static struct P(edge) *
 476 P(son_any)(struct P(edge) *edge)
 477 {
 478   ASSERT(edge->flags & TRIE_FLAG_DEG);
 479   if (!(edge->flags & TRIE_FLAG_HASH))
 480     return edge->son[0];
 481   else
 482     for (uint i = 0; ; i++)
 483       if ((i & TRIE_BUCKET_MASK) && (uintptr_t)edge->son[i] > 1)
 484         return edge->son[i];
 485 }
 486 #endif
 487
 488 /*** Find/insert/delete ***/
 489
 490 #ifdef TRIE_WANT_DO_FIND
 491 static struct P(edge) *
 492 P(do_find)(TAC byte *ptr, uint len)
 493 {
 494   TRIE_DBG("do_find('%.*s')", len, ptr);
 495   struct P(edge) **ref = &T.root, *edge;
 496   do
 497     {
 498       if (!(edge = *ref) || edge->len > len)
 499         return NULL;
 500       else if (edge->len == len)
 501         return ((edge->flags & TRIE_FLAG_NODE) && !memcmp(ptr, P(str_get)(edge->node), len)) ? edge : NULL;
 502     }
 503   while (ref = P(son_find)(edge, P(str_char)(ptr, len, edge->len)));
 504   return NULL;
 505 }
 506 #endif
 507
 508 static struct P(edge) *
 509 P(do_lookup)(TAC byte *ptr, uint len)
 510 {
 511   TRIE_DBG("do_lookup('%.*s')", len, ptr);
 512   struct P(edge) **ref, *edge, *leaf, *newleaf;
 513   uint prefix, elen, trans, pos;
 514   byte *eptr;
 515
 516   if (!(edge = T.root))
 517     {
 518       TRIE_DBG("Creating first edge");
 519       edge = T.root = P(edge_alloc)(TTC TRIE_FLAG_NODE);
 520       edge->node = NULL;
 521       edge->len = len;
 522       return edge;
 523     }
 524   else
 525     {
 526       while (edge->len < len && (ref = P(son_find)(edge, P(str_char)(ptr, len, edge->len))))
 527         edge = *ref;
 528       if (!(edge->flags & TRIE_FLAG_NODE))
 529         edge = edge->leaf;
 530       ASSERT(edge->flags & TRIE_FLAG_NODE);
 531       eptr = P(str_get)(edge->node);
 532       elen = edge->len;
 533       prefix = P(common_prefix)(ptr, len, eptr, elen);
 534       if (prefix == len && prefix == elen)
 535         return edge;
 536       TRIE_DBG("The longest common prefix is '%.*s'", prefix, P(str_prefix)(ptr, len, prefix));
 537
 538       if (prefix < len)
 539         {
 540           TRIE_DBG("Creating a new leaf");
 541           newleaf = P(edge_alloc)(TTC TRIE_FLAG_NODE);
 542           newleaf->node = NULL;
 543           newleaf->len = len;
 544         }
 545       else
 546         newleaf = NULL;
 547
 548       ref = &T.root;
 549       while (edge = *ref)
 550         {
 551           pos = edge->len;
 552           if (prefix < pos)
 553             {
 554               leaf = (edge->flags & TRIE_FLAG_NODE) ? edge : edge->leaf;
 555               TRIE_DBG("Splitting edge '%.*s'", leaf->len, P(str_get)(leaf->node));
 556               trans = P(str_char)(P(str_get)(leaf->node), leaf->len, prefix);
 557               if (len == prefix)
 558                 {
 559                   edge = P(edge_alloc)(TTC 1 | TRIE_FLAG_NODE);
 560                   edge->len = prefix;
 561                   edge->node = NULL;
 562                   edge->trans[0] = trans;
 563                   edge->son[0] = *ref;
 564                   return *ref = edge;
 565                 }
 566               else
 567                 {
 568                   edge = P(edge_alloc)(TTC 2);
 569                   edge->len = prefix;
 570                   edge->leaf = leaf;
 571                   edge->trans[0] = trans;
 572                   edge->son[0] = *ref;
 573                   edge->trans[1] = P(str_char)(ptr, len, prefix);
 574                   *ref = edge;
 575                   return edge->son[1] = newleaf;
 576                 }
 577             }
 578           if (pos == len)
 579             {
 580               TRIE_DBG("Adding the node to an already existing edge");
 581               edge->flags |= TRIE_FLAG_NODE;
 582               edge->node = NULL;
 583               return edge;
 584             }
 585           if (!(edge->flags & TRIE_FLAG_NODE) && newleaf)
 586             edge->leaf = newleaf;
 587           trans = P(str_char)(ptr, len, pos);
 588           if (pos < prefix)
 589             ref = P(son_find)(edge, trans);
 590           else
 591             ref = P(son_insert)(TTC ref, trans);
 592         }
 593     }
 594   return *ref = newleaf;
 595 }
 596
 597 #ifdef TRIE_WANT_DO_DELETE
 598 static P(node_t) *
 599 P(do_delete)(TAC byte *ptr, uint len)
 600 {
 601   TRIE_DBG("do_delete('%.*s')", len, ptr);
 602   struct P(edge) **ref = &T.root, **pref = NULL, *edge, *parent, *leaf, *pold = NULL;
 603   while (1)
 604     {
 605       if (!(edge = *ref) || edge->len > len)
 606         return NULL;
 607       else if (edge->len == len)
 608         if ((edge->flags & TRIE_FLAG_NODE) && !memcmp(ptr, P(str_get)(edge->node), len))
 609           break;
 610         else
 611           return NULL;
 612       pref = ref;
 613       if (!(ref = P(son_find)(edge, P(str_char)(ptr, len, edge->len))))
 614         return NULL;
 615     }
 616
 617   P(node_t) *node = edge->node;
 618   uint deg = edge->flags & TRIE_FLAG_DEG;
 619
 620   if (!deg)
 621     {
 622       if (!pref)
 623         {
 624           TRIE_DBG("Deleting last edge");
 625           T.root = NULL;
 626           P(edge_free)(TTC edge);
 627           return node;
 628         }
 629       else
 630         {
 631           TRIE_DBG("Deleting a leaf");
 632           pold = *pref;
 633           P(son_delete)(TTC pref, P(str_char)(ptr, len, pold->len));
 634           parent = *pref;
 635           if ((parent->flags & (TRIE_FLAG_DEG | TRIE_FLAG_NODE)) <= 1)
 636             {
 637               ASSERT((parent->flags & (TRIE_FLAG_DEG | TRIE_FLAG_HASH)) == 1);
 638               TRIE_DBG("... and its parent");
 639               leaf = *pref = parent->son[0];
 640               P(edge_free)(TTC parent);
 641             }
 642           else if (parent->flags & TRIE_FLAG_NODE)
 643             leaf = parent;
 644           else
 645             leaf = P(son_any)(parent);
 646         }
 647       P(edge_free)(TTC edge);
 648     }
 649   else if (deg == 1)
 650     {
 651       TRIE_DBG("Deleting internal edge");
 652       ASSERT(!(edge->flags & TRIE_FLAG_HASH));
 653       leaf = *ref = edge->son[0];
 654       P(edge_free)(TTC edge);
 655     }
 656   else
 657     {
 658       TRIE_DBG("Deleting node, but leaving edge");
 659       leaf = P(son_any)(edge);
 660       if (!(leaf->flags & TRIE_FLAG_NODE))
 661         leaf = leaf->leaf;
 662       edge->leaf = leaf;
 663       edge->flags &= ~TRIE_FLAG_NODE;
 664     }
 665
 666   TRIE_DBG("Updating leaf pointers");
 667   if (!(leaf->flags & TRIE_FLAG_NODE))
 668     leaf = leaf->leaf;
 669   ASSERT(leaf->flags & TRIE_FLAG_NODE);
 670   for (ref = &T.root; ref && (*ref)->len < len; ref = P(son_find)(*ref, P(str_char)(ptr, len, (*ref)->len)))
 671     if ((*ref)->leaf == edge || (*ref)->leaf == pold)
 672       (*ref)->leaf = leaf;
 673   return node;
 674 }
 675 #endif
 676
 677 #ifdef TRIE_WANT_FIND
 678 static inline P(node_t) *
 679 P(find)(TAC char *str)
 680 {
 681   struct P(edge) *edge = P(do_find)(TTC str, str_len(str));
 682   return edge ? edge->node : NULL;
 683 }
 684 #endif
 685
 686 #ifdef TRIE_WANT_FIND_BUF
 687 static inline P(node_t) *
 688 P(find_buf)(TAC byte *ptr, uint len)
 689 {
 690   struct P(edge) *edge = P(do_find)(TTC ptr, len);
 691   return edge ? edge->node : NULL;
 692 }
 693 #endif
 694
 695 #ifdef TRIE_WANT_ADD
 696 static inline void
 697 P(add)(TAC P(node_t) *node)
 698 {
 699   struct P(edge) *edge = P(do_lookup)(TTC P(str_get)(node), P(str_len)(node));
 700   ASSERT(!edge->node);
 701   edge->node = node;
 702 }
 703 #endif
 704
 705 #ifdef TRIE_WANT_REPLACE
 706 static inline P(node_t) *
 707 P(replace)(TAC P(node_t) *node)
 708 {
 709   struct P(edge) *edge = P(do_lookup)(TTC P(str_get)(node), P(str_len)(node));
 710   P(node_t) *over = edge->node;
 711   edge->node = node;
 712   return over;
 713 }
 714 #endif
 715
 716 #ifdef TRIE_WANT_DELETE
 717 static inline P(node_t) *
 718 P(delete)(TAC char *str)
 719 {
 720   return P(do_delete)(TTC str, str_len(str));
 721 }
 722 #endif
 723
 724 #ifdef TRIE_WANT_DELETE_BUF
 725 static inline P(node_t) *
 726 P(delete_buf)(TAC byte *ptr, uint len)
 727 {
 728   return P(do_delete)(TTC ptr, len);
 729 }
 730 #endif
 731
 732 #ifdef TRIE_WANT_REMOVE
 733 static inline void
 734 P(remove)(TAC P(node_t) *node)
 735 {
 736   if (unlikely(P(do_delete)(TTC P(str_get)(node), P(str_len)(node)) != node))
 737     ASSERT(0);
 738 }
 739 #endif
 740
 741 /*** Traversing prefixes and subtrees ***/
 742
 743 #ifndef TRIE_FOR_ALL
 744
 745 // for all matched edges until the first >=xlen (including)
 746 #define TRIE_FOR_PREFIX_EDGES(px, xtrie, xptr, xlen, xedge)             \
 747   do                                                                    \
 748     {                                                                   \
 749       byte *_ptr = (xptr);                                              \
 750       uint _len = (xlen);                                               \
 751       struct px##trie *_trie = (xtrie);                                 \
 752       struct px##edge *xedge, **_ref;                                   \
 753       if (!(xedge = _trie->root))                                       \
 754         break;                                                          \
 755       while (xedge->len < _len && (_ref = px##son_find(xedge, px##str_char(_ptr, _len, xedge->len))))           \
 756         xedge = *_ref;                                                  \
 757       if (!(xedge->flags & TRIE_FLAG_NODE))                             \
 758         xedge = xedge->leaf;                                            \
 759       uint _prefix = px##common_prefix(_ptr, _len, px##str_get(xedge->node), xedge->len);                       \
 760       for (_ref = &_trie->root; _ref && ((xedge = *_ref)->len <= _prefix || _prefix == _len);                   \
 761         _ref = (xedge->len < _prefix) ? px##son_find(xedge, px##str_char(_ptr, _len, xedge->len)) : NULL)       \
 762         {
 763 #define TRIE_END_PREFIX_EDGES                                           \
 764         }                                                               \
 765     }                                                                   \
 766   while (0)
 767
 768 // for entire subtree starting in the xstart edge
 769 #define TRIE_FOR_SUBTREE_EDGES(px, xstart, xedge)                       \
 770   do                                                                    \
 771     {                                                                   \
 772       struct { struct px##edge *edge; uint pos; }                       \
 773         *_sbuf = alloca(sizeof(*_sbuf) * 16),                           \
 774         *_sptr = _sbuf, *_send = _sbuf + 16;                            \
 775       struct px##edge *_next = (xstart), *xedge;                        \
 776       while (xedge = _next)                                             \
 777         {                                                               \
 778           if (xedge->flags & TRIE_FLAG_DEG)                             \
 779             {                                                           \
 780               if (_sptr == _send)                                       \
 781                 {                                                       \
 782                   uint stack_size = _sptr - _sbuf;                      \
 783                   _sptr = alloca(sizeof(*_sptr) * (stack_size * 2));    \
 784                   memcpy(_sptr, _sbuf, sizeof(*_sptr) * stack_size);    \
 785                   _sbuf = _sptr;                                        \
 786                   _send = _sptr + stack_size * 2;                       \
 787                 }                                                       \
 788               _sptr->edge = xedge;                                      \
 789               _sptr->pos = (xedge->flags & TRIE_FLAG_HASH) ?            \
 790                 (1U << px##bucket_rank) << xedge->hash_rank :           \
 791                 (xedge->flags & TRIE_FLAG_DEG);                         \
 792               _sptr++;                                                  \
 793             }                                                           \
 794           while (1)                                                     \
 795             {                                                           \
 796               if (_sptr == _sbuf)                                       \
 797                 {                                                       \
 798                   _next = NULL;                                         \
 799                   break;                                                \
 800                 }                                                       \
 801               _next = (--_sptr)->edge;                                  \
 802               uint pos = --(_sptr->pos);                                \
 803               uint flags = _next->flags;                                \
 804               _next = _next->son[pos];                                  \
 805               if (pos)                                                  \
 806                 _sptr++;                                                \
 807               if (!(flags & TRIE_FLAG_HASH) ||                          \
 808                 ((pos & ((1U << px##bucket_rank) - 1)) &&               \
 809                  (uintptr_t)_next > 1))                                 \
 810                 break;                                                  \
 811             }
 812 #define TRIE_END_SUBTREE_EDGES                                          \
 813         }                                                               \
 814     }                                                                   \
 815   while (0)
 816
 817 #define TRIE_FOR_SUBTREE(px, xstart, xnode)                             \
 818   TRIE_FOR_SUBTREE_EDGES(px, xstart, _edge)                             \
 819     if (_edge->flags & TRIE_FLAG_NODE)                                  \
 820       {                                                                 \
 821         px##node_t *xnode = _edge->node;
 822 #define TRIE_END_SUBTREE                                                \
 823       }                                                                 \
 824   TRIE_END_SUBTREE_EDGES;
 825
 826 #define TRIE_FOR_ALL_EDGES(px, xtrie, xedge) TRIE_FOR_SUBTREE_EDGES(px, (xtrie)->root, xedge)
 827 #define TRIE_END_ALL_EDGES TRIE_END_SUBTREE_EDGES
 828
 829 #define TRIE_FOR_ALL(px, xtrie, xnode) TRIE_FOR_SUBTREE(px, (xtrie)->root, xnode)
 830 #define TRIE_END_ALL TRIE_END_SUBTREE
 831
 832 #endif
 833
 834 /*** Check consistency ***/
 835
 836 #ifdef TRIE_WANT_AUDIT
 837
 838 static void
 839 P(audit)(TA)
 840 {
 841   uint count = 0;
 842   TRIE_FOR_ALL_EDGES(TRIE_PREFIX(), &T, edge)
 843     {
 844       ASSERT(edge);
 845       uint deg = edge->flags & TRIE_FLAG_DEG;
 846       ASSERT(edge->node);
 847       struct P(edge) * leaf = (edge->flags & TRIE_FLAG_NODE) ? edge : edge->leaf;
 848       if (leaf != edge)
 849         {
 850           ASSERT(leaf->flags & TRIE_FLAG_NODE);
 851           ASSERT(leaf->len > edge->len);
 852           ASSERT(leaf->node);
 853         }
 854       TRIE_DBG("Checking edge %p, %s=%p, flags=0x%x, key='%.*s'",
 855           edge, (edge->flags & TRIE_FLAG_NODE) ? "node" : "leaf", edge->node, edge->flags,
 856           edge->len, P(str_prefix)(P(str_get)(leaf->node), leaf->len, edge->len));
 857       ASSERT(deg >= 2 || (edge->flags & TRIE_FLAG_NODE));
 858       if (edge->flags & TRIE_FLAG_HASH)
 859         {
 860           ASSERT(deg > 1 && deg <= 256);
 861           uint count = 0, deleted = 0;
 862           for (uint i = TRIE_BUCKET_SIZE << edge->hash_rank; i--; )
 863             if (i & TRIE_BUCKET_MASK)
 864               if ((uintptr_t)edge->son[i] == 1)
 865                 deleted++;
 866               else if (edge->son[i])
 867                 {
 868                   ASSERT(edge->son[i]->len > edge->len);
 869                   count++;
 870                 }
 871           ASSERT(count == deg);
 872           ASSERT(deleted == edge->hash_deleted);
 873         }
 874       else
 875         {
 876           ASSERT(deg <= TRIE_HASH_THRESHOLD);
 877           for (uint i = 0; i < deg; i++)
 878             ASSERT(edge->son[i]->len > edge->len);
 879         }
 880       count++;
 881     }
 882   TRIE_END_ALL_EDGES;
 883   TRIE_DBG("Found %u edges", count);
 884 }
 885
 886 #endif
 887
 888 /*** Statistics ***/
 889
 890 #ifdef TRIE_WANT_STATS
 891
 892 struct P(stats) {
 893   u64 total_size;
 894   u64 small_size;
 895   u64 hash_size;
 896 };
 897
 898 static void
 899 P(stats)(TAC struct P(stats) *stats)
 900 {
 901   bzero(stats, sizeof(*stats));
 902   for (uint i = 0; i < ARRAY_SIZE(T.epool); i++)
 903     stats->small_size += ep_total_size(T.epool[i]);
 904   for (uint i = 0; i < ARRAY_SIZE(T.hpool); i++)
 905     stats->hash_size += ep_total_size(T.hpool[i]);
 906   stats->total_size = stats->small_size + stats->hash_size + sizeof(T);
 907 }
 908
 909 static inline u64
 910 P(total_size)(TA)
 911 {
 912   struct P(stats) stats;
 913   P(stats)(TTC &stats);
 914   return stats.total_size;
 915 }
 916
 917 #endif
 918
 919 /*** Clean up local macros ***/
 920
 921 #undef P
 922 #undef T
 923 #undef TA
 924 #undef TAC
 925 #undef TT
 926 #undef TTC
 927
 928 #undef TRIE_PREFIX
 929 #undef TRIE_NODE_TYPE
 930 #undef TRIE_NODE_KEY
 931 #undef TRIE_NODE_LEN
 932 #undef TRIE_LEN_TYPE
 933 #undef TRIE_REV
 934 #undef TRIE_DYNAMIC
 935 #undef TRIE_ELTPOOL_SIZE
 936 #undef TRIE_HASH_THRESHOLD
 937 #undef TRIE_BUCKET_RANK
 938 #undef TRIE_BUCKET_SIZE
 939 #undef TRIE_BUCKET_MASK
 940 #undef TRIE_TRACE
 941 #undef TRIE_DBG
 942 #undef TRIE_HASH_FOR_ALL
 943 #undef TRIE_HASH_END_FOR
 944
 945 #undef TRIE_WANT_CLEANUP
 946
 947 #undef TRIE_WANT_DO_FIND
 948 #undef TRIE_WANT_DO_LOOKUP
 949 #undef TRIE_WANT_DO_DELETE
 950
 951 #undef TRIE_WANT_FIND
 952 #undef TRIE_WANT_FIND_BUF
 953 #undef TRIE_WANT_ADD
 954 #undef TRIE_WANT_ADD_OVER
 955 #undef TRIE_WANT_DELETE
 956 #undef TRIE_WANT_DELETE_BUF
 957 #undef TRIE_WANT_REMOVE
 958
 959 #undef TRIE_WANT_AUDIT