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