2 * UCW Library -- Byte-based trie
4 * (c) 2008 Pavel Charvat <pchar@ucw.cz>
6 * This software may be freely distributed and used according to the terms
7 * of the GNU Lesser General Public License.
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.
15 * You need to specify:
17 * [*] TRIE_PREFIX(x) macro to add a name prefix (used on all global names
18 * defined by the trie generator).
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.
27 * TRIE_WANT_CLEANUP cleanup()
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)
37 * TRIE_WANT_AUDIT audit()
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.
46 #ifndef _SHERLOCK_UCW_TRIE_H
47 #define _SHERLOCK_UCW_TRIE_H
49 #include <ucw/eltpool.h>
50 #include <ucw/hashfunc.h>
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
63 #error Undefined mandatory macro TRIE_PREFIX
65 #define P(x) TRIE_PREFIX(x)
67 #ifndef TRIE_NODE_TYPE
68 #error Undefined mandatory macro TRIE_NODE_TYPE
70 typedef TRIE_NODE_TYPE P(node_t);
73 #define TRIE_NODE_KEY(node) ((char *)&(node))
77 #define TRIE_NODE_LEN(node) (str_len(TRIE_NODE_KEY(node)))
81 #define TRIE_LEN_TYPE u32
83 typedef TRIE_LEN_TYPE P(len_t);
85 #ifndef TRIE_ELTPOOL_SIZE
86 #define TRIE_ELTPOOL_SIZE 1024
89 #ifndef TRIE_HASH_THRESHOLD
90 #define TRIE_HASH_THRESHOLD (6 - sizeof(P(len_t)))
93 #ifndef TRIE_BUCKET_RANK
94 #define TRIE_BUCKET_RANK (2U + (sizeof(void *) > 4))
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 };
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 *));
106 #define TRIE_DBG(x...) msg(L_DEBUG, "TRIE: " x)
108 #define TRIE_DBG(x...) do{}while(0)
111 /*** Solve dependencies ***/
113 #if !defined(TRIE_WANT_DO_FIND) && (defined(TRIE_WANT_FIND) || defined(TRIE_WANT_FIND_BUF))
114 #define TRIE_WANT_DO_FIND
117 #if !defined(TRIE_WANT_DO_LOOKUP) && (defined(TRIE_WANT_ADD) || defined(TRIE_WANT_REPLACE))
118 #define TRIE_WANT_DO_LOOKUP
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
125 #if !defined(TRIE_WANT_DO_LOOKUP)
126 #error You must request at least one method for inserting nodes
129 /*** Data structures ***/
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
138 u16 flags; // TRIE_FLAG_x
140 byte trans[TRIE_HASH_THRESHOLD]; // transition characters (!TRIE_FLAG_HASH)
142 byte hash_rank; // logarithmic hash size (TRIE_FLAG_HASH)
143 byte hash_deleted; // number of deleted items
146 P(len_t) len; // sum of all ancestor edges with their trasition
147 // characters plus the length of the current edge
149 P(node_t) *node; // inserted data (TRIE_FLAG_NODE)
150 struct P(edge) *leaf; // reference to a descendant with data (!TRIE_FLAG_NODE)
152 struct P(edge) *son[0]; // array of sons (!TRIE_FLAG_HASH)
153 // or hash table (TRIE_FLAG_HASH)
158 #define TA struct P(trie) *trie
163 static struct P(trie) P(trie);
171 /*** Memory management ***/
176 TRIE_DBG("Initializing");
177 bzero(&T, sizeof(T));
178 for (uns i = 0; i < ARRAY_SIZE(T.epool); i++)
180 uns size = sizeof(struct P(edge)) + i * sizeof(void *);
181 T.epool[i] = ep_new(size, MAX(TRIE_ELTPOOL_SIZE / size, 1));
183 for (uns i = 0; i < ARRAY_SIZE(T.hpool); i++)
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));
190 #ifdef TRIE_WANT_CLEANUP
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]);
202 static struct P(edge) *
203 P(edge_alloc)(TAC uns flags)
205 struct P(edge) *edge;
206 if (flags & TRIE_FLAG_HASH)
208 uns rank = 0, deg = flags & TRIE_FLAG_DEG;
209 while ((TRIE_BUCKET_MASK << rank) < deg * 2) // 25-50% density
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);
218 edge = ep_alloc(T.epool[flags & TRIE_FLAG_DEG]);
220 TRIE_DBG("Allocated edge %p, flags=0x%x", edge, flags);
225 P(edge_free)(TAC struct P(edge) *edge)
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);
231 ep_free(T.epool[edge->flags & TRIE_FLAG_DEG], edge);
234 /*** Manipulation with strings ***/
237 P(str_get)(P(node_t) *node)
239 return TRIE_NODE_KEY((*node));
243 P(str_len)(P(node_t) *node)
245 return TRIE_NODE_LEN((*node));
249 P(str_char)(byte *ptr, uns len UNUSED, uns pos)
254 return ptr[len - pos - 1];
259 P(str_prefix)(byte *ptr, uns len UNUSED, uns prefix UNUSED)
264 return ptr + len - prefix;
269 P(str_suffix)(byte *ptr, uns len UNUSED, uns suffix UNUSED)
272 return ptr + len - suffix;
279 P(common_prefix)(byte *ptr1, uns len1, byte *ptr2, uns len2)
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))
293 return hash_u32(c) >> 16;
296 static inline struct P(edge) **
297 P(hash_find)(struct P(edge) *edge, uns c)
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)
304 else if (((byte *)&edge->son[i & ~TRIE_BUCKET_MASK])[i & TRIE_BUCKET_MASK] == c)
305 return &edge->son[i];
308 static inline struct P(edge) **
309 P(hash_insert)(struct P(edge) *edge, uns c)
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)
315 edge->hash_deleted -= (uintptr_t)edge->son[i];
317 ((byte *)&edge->son[i & ~TRIE_BUCKET_MASK])[i & TRIE_BUCKET_MASK] = c;
318 return &edge->son[i];
322 #ifdef TRIE_WANT_DO_DELETE
324 P(hash_delete)(struct P(edge) *edge, uns c)
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)
331 edge->hash_deleted++;
332 edge->son[i] = (void *)1;
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]; \
345 #define TRIE_HASH_END_FOR }while(0);}}while(0)
348 P(hash_realloc)(TAC struct P(edge) **ref)
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;
357 P(edge_free)(TTC old);
360 /*** Finding/inserting/deleting sons ***/
362 static struct P(edge) **
363 P(son_find)(struct P(edge) *edge, uns c)
365 if (edge->flags & TRIE_FLAG_HASH)
366 return P(hash_find)(edge, c);
368 for (uns i = edge->flags & TRIE_FLAG_DEG; i--; )
369 if (edge->trans[i] == c)
370 return &edge->son[i];
374 static struct P(edge) **
375 P(son_insert)(TAC struct P(edge) **ref, uns c)
377 struct P(edge) *old = *ref, *edge;
378 uns deg = old->flags & TRIE_FLAG_DEG;
379 if (old->flags & TRIE_FLAG_HASH)
382 if ((deg + 1 + old->hash_deleted) * 4 > (TRIE_BUCKET_MASK << old->hash_rank) * 3) // >75% density
384 P(hash_realloc)(TTC ref);
392 if (deg < TRIE_HASH_THRESHOLD)
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);
402 return &edge->son[deg];
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);
416 return P(hash_insert)(edge, c);
419 #ifdef TRIE_WANT_DO_DELETE
421 P(son_delete)(TAC struct P(edge) **ref, uns c)
423 struct P(edge) *old = *ref, *edge;
424 uns deg = old->flags & TRIE_FLAG_DEG;
426 if (old->flags & TRIE_FLAG_HASH)
428 P(hash_delete)(old, c);
431 if (deg <= TRIE_HASH_THRESHOLD / 2)
433 TRIE_DBG("Reducing hash table to array");
434 edge = P(edge_alloc)(TTC old->flags & ~TRIE_FLAG_HASH);
436 TRIE_HASH_FOR_ALL(old, trans, son)
437 edge->trans[k] = trans;
443 else if (deg * 6 >= (TRIE_BUCKET_MASK << old->hash_rank)) // >= 16%
447 P(hash_realloc)(TTC ref);
454 TRIE_DBG("Reducing array");
455 edge = P(edge_alloc)(TTC old->flags - 1);
457 for (uns i = 0; i < deg; i++)
458 if (old->trans[i] != c)
460 edge->trans[j] = old->trans[i];
461 edge->son[j] = old->son[i];
464 ASSERT(j == deg - 1);
466 edge->node = old->node;
467 edge->len = old->len;
468 P(edge_free)(TTC old);
473 #ifdef TRIE_WANT_DO_DELETE
474 static struct P(edge) *
475 P(son_any)(struct P(edge) *edge)
477 ASSERT(edge->flags & TRIE_FLAG_DEG);
478 if (!(edge->flags & TRIE_FLAG_HASH))
481 for (uns i = 0; ; i++)
482 if ((i & TRIE_BUCKET_MASK) && (uintptr_t)edge->son[i] > 1)
487 /*** Find/insert/delete ***/
489 #ifdef TRIE_WANT_DO_FIND
490 static struct P(edge) *
491 P(do_find)(TAC byte *ptr, uns len)
493 TRIE_DBG("do_find('%.*s')", len, ptr);
494 struct P(edge) **ref = &T.root, *edge;
497 if (!(edge = *ref) || edge->len > len)
499 else if (edge->len == len)
500 return ((edge->flags & TRIE_FLAG_NODE) && !memcmp(ptr, P(str_get)(edge->node), len)) ? edge : NULL;
502 while (ref = P(son_find)(edge, P(str_char)(ptr, len, edge->len)));
507 static struct P(edge) *
508 P(do_lookup)(TAC byte *ptr, uns len)
510 TRIE_DBG("do_lookup('%.*s')", len, ptr);
511 struct P(edge) **ref, *edge, *leaf, *newleaf;
512 uns prefix, elen, trans, pos;
515 if (!(edge = T.root))
517 TRIE_DBG("Creating first edge");
518 edge = T.root = P(edge_alloc)(TTC TRIE_FLAG_NODE);
525 while (edge->len < len && (ref = P(son_find)(edge, P(str_char)(ptr, len, edge->len))))
527 if (!(edge->flags & TRIE_FLAG_NODE))
529 ASSERT(edge->flags & TRIE_FLAG_NODE);
530 eptr = P(str_get)(edge->node);
532 prefix = P(common_prefix)(ptr, len, eptr, elen);
533 if (prefix == len && prefix == elen)
535 TRIE_DBG("The longest common prefix is '%.*s'", prefix, P(str_prefix)(ptr, len, prefix));
539 TRIE_DBG("Creating a new leaf");
540 newleaf = P(edge_alloc)(TTC TRIE_FLAG_NODE);
541 newleaf->node = NULL;
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);
558 edge = P(edge_alloc)(TTC 1 | TRIE_FLAG_NODE);
561 edge->trans[0] = trans;
567 edge = P(edge_alloc)(TTC 2);
570 edge->trans[0] = trans;
572 edge->trans[1] = P(str_char)(ptr, len, prefix);
574 return edge->son[1] = newleaf;
579 TRIE_DBG("Adding the node to an already existing edge");
580 edge->flags |= TRIE_FLAG_NODE;
584 if (!(edge->flags & TRIE_FLAG_NODE) && newleaf)
585 edge->leaf = newleaf;
586 trans = P(str_char)(ptr, len, pos);
588 ref = P(son_find)(edge, trans);
590 ref = P(son_insert)(TTC ref, trans);
593 return *ref = newleaf;
596 #ifdef TRIE_WANT_DO_DELETE
598 P(do_delete)(TAC byte *ptr, uns len)
600 TRIE_DBG("do_delete('%.*s')", len, ptr);
601 struct P(edge) **ref = &T.root, **pref = NULL, *edge, *parent, *leaf, *pold = NULL;
604 if (!(edge = *ref) || edge->len > len)
606 else if (edge->len == len)
607 if ((edge->flags & TRIE_FLAG_NODE) && !memcmp(ptr, P(str_get)(edge->node), len))
612 if (!(ref = P(son_find)(edge, P(str_char)(ptr, len, edge->len))))
616 P(node_t) *node = edge->node;
617 uns deg = edge->flags & TRIE_FLAG_DEG;
623 TRIE_DBG("Deleting last edge");
625 P(edge_free)(TTC edge);
630 TRIE_DBG("Deleting a leaf");
632 P(son_delete)(TTC pref, P(str_char)(ptr, len, pold->len));
634 if ((parent->flags & (TRIE_FLAG_DEG | TRIE_FLAG_NODE)) <= 1)
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);
641 else if (parent->flags & TRIE_FLAG_NODE)
644 leaf = P(son_any)(parent);
646 P(edge_free)(TTC edge);
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);
657 TRIE_DBG("Deleting node, but leaving edge");
658 leaf = P(son_any)(edge);
659 if (!(leaf->flags & TRIE_FLAG_NODE))
662 edge->flags &= ~TRIE_FLAG_NODE;
665 TRIE_DBG("Updating leaf pointers");
666 if (!(leaf->flags & TRIE_FLAG_NODE))
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)
676 #ifdef TRIE_WANT_FIND
677 static inline P(node_t) *
678 P(find)(TAC char *str)
680 struct P(edge) *edge = P(do_find)(TTC str, str_len(str));
681 return edge ? edge->node : NULL;
685 #ifdef TRIE_WANT_FIND_BUF
686 static inline P(node_t) *
687 P(find_buf)(TAC byte *ptr, uns len)
689 struct P(edge) *edge = P(do_find)(TTC ptr, len);
690 return edge ? edge->node : NULL;
696 P(add)(TAC P(node_t) *node)
698 struct P(edge) *edge = P(do_lookup)(TTC P(str_get)(node), P(str_len)(node));
704 #ifdef TRIE_WANT_REPLACE
705 static inline P(node_t) *
706 P(replace)(TAC P(node_t) *node)
708 struct P(edge) *edge = P(do_lookup)(TTC P(str_get)(node), P(str_len)(node));
709 P(node_t) *over = edge->node;
715 #ifdef TRIE_WANT_DELETE
716 static inline P(node_t) *
717 P(delete)(TAC char *str)
719 return P(do_delete)(TTC str, str_len(str));
723 #ifdef TRIE_WANT_DELETE_BUF
724 static inline P(node_t) *
725 P(delete_buf)(TAC byte *ptr, uns len)
727 return P(do_delete)(TTC ptr, len);
731 #ifdef TRIE_WANT_REMOVE
733 P(remove)(TAC P(node_t) *node)
735 if (unlikely(P(do_delete)(TTC P(str_get)(node), P(str_len)(node)) != node))
740 /*** Traversing prefixes and subtrees ***/
744 // for all matched edges until the first >=xlen (including)
745 #define TRIE_FOR_PREFIX_EDGES(px, xtrie, xptr, xlen, xedge) \
748 byte *_ptr = (xptr); \
750 struct px##trie *_trie = (xtrie); \
751 struct px##edge *xedge, **_ref; \
752 if (!(xedge = _trie->root)) \
754 while (xedge->len < _len && (_ref = px##son_find(xedge, px##str_char(_ptr, _len, xedge->len)))) \
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) \
762 #define TRIE_END_PREFIX_EDGES \
767 // for entire subtree starting in the xstart edge
768 #define TRIE_FOR_SUBTREE_EDGES(px, xstart, xedge) \
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) \
777 if (xedge->flags & TRIE_FLAG_DEG) \
779 if (_sptr == _send) \
781 uns stack_size = _sptr - _sbuf; \
782 _sptr = alloca(sizeof(*_sptr) * (stack_size * 2)); \
783 memcpy(_sptr, _sbuf, sizeof(*_sptr) * stack_size); \
785 _send = _sptr + stack_size * 2; \
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); \
795 if (_sptr == _sbuf) \
800 _next = (--_sptr)->edge; \
801 uns pos = --(_sptr->pos); \
802 uns flags = _next->flags; \
803 _next = _next->son[pos]; \
806 if (!(flags & TRIE_FLAG_HASH) || \
807 ((pos & ((1U << px##bucket_rank) - 1)) && \
808 (uintptr_t)_next > 1)) \
811 #define TRIE_END_SUBTREE_EDGES \
816 #define TRIE_FOR_SUBTREE(px, xstart, xnode) \
817 TRIE_FOR_SUBTREE_EDGES(px, xstart, _edge) \
818 if (_edge->flags & TRIE_FLAG_NODE) \
820 px##node_t *xnode = _edge->node;
821 #define TRIE_END_SUBTREE \
823 TRIE_END_SUBTREE_EDGES;
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
828 #define TRIE_FOR_ALL(px, xtrie, xnode) TRIE_FOR_SUBTREE(px, (xtrie)->root, xnode)
829 #define TRIE_END_ALL TRIE_END_SUBTREE
833 /*** Check consistency ***/
835 #ifdef TRIE_WANT_AUDIT
841 TRIE_FOR_ALL_EDGES(TRIE_PREFIX(), &T, edge)
844 uns deg = edge->flags & TRIE_FLAG_DEG;
846 struct P(edge) * leaf = (edge->flags & TRIE_FLAG_NODE) ? edge : edge->leaf;
849 ASSERT(leaf->flags & TRIE_FLAG_NODE);
850 ASSERT(leaf->len > edge->len);
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)
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)
865 else if (edge->son[i])
867 ASSERT(edge->son[i]->len > edge->len);
870 ASSERT(count == deg);
871 ASSERT(deleted == edge->hash_deleted);
875 ASSERT(deg <= TRIE_HASH_THRESHOLD);
876 for (uns i = 0; i < deg; i++)
877 ASSERT(edge->son[i]->len > edge->len);
882 TRIE_DBG("Found %u edges", count);
889 #ifdef TRIE_WANT_STATS
898 P(stats)(TAC struct P(stats) *stats)
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);
911 struct P(stats) stats;
912 P(stats)(TTC &stats);
913 return stats.total_size;
918 /*** Clean up local macros ***/
928 #undef TRIE_NODE_TYPE
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
941 #undef TRIE_HASH_FOR_ALL
942 #undef TRIE_HASH_END_FOR
944 #undef TRIE_WANT_CLEANUP
946 #undef TRIE_WANT_DO_FIND
947 #undef TRIE_WANT_DO_LOOKUP
948 #undef TRIE_WANT_DO_DELETE
950 #undef TRIE_WANT_FIND
951 #undef TRIE_WANT_FIND_BUF
953 #undef TRIE_WANT_ADD_OVER
954 #undef TRIE_WANT_DELETE
955 #undef TRIE_WANT_DELETE_BUF
956 #undef TRIE_WANT_REMOVE
958 #undef TRIE_WANT_AUDIT