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