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()
43 #ifndef _SHERLOCK_UCW_TRIE_H
44 #define _SHERLOCK_UCW_TRIE_H
46 #include "lib/eltpool.h"
47 #include "lib/hashfunc.h"
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
60 #error Undefined mandatory macro TRIE_PREFIX
62 #define P(x) TRIE_PREFIX(x)
64 #ifndef TRIE_NODE_TYPE
65 #error Undefined mandatory macro TRIE_NODE_TYPE
67 typedef TRIE_NODE_TYPE P(node_t);
70 #define TRIE_NODE_KEY(node) ((char *)&(node))
74 #define TRIE_NODE_LEN(node) (str_len(TRIE_NODE_KEY(node)))
78 #define TRIE_LEN_TYPE u32
80 typedef TRIE_LEN_TYPE P(len_t);
82 #ifndef TRIE_ELTPOOL_SIZE
83 #define TRIE_ELTPOOL_SIZE 1024
86 #ifndef TRIE_HASH_THRESHOLD
87 #define TRIE_HASH_THRESHOLD (6 - sizeof(P(len_t)))
90 #ifndef TRIE_BUCKET_RANK
91 #define TRIE_BUCKET_RANK (2U + sizeof(void *) > 4)
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 };
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 *));
103 #define TRIE_DBG(x...) msg(L_DEBUG, "TRIE: " x)
105 #define TRIE_DBG(x...) do{}while(0)
108 /*** Solve dependencies ***/
110 #if !defined(TRIE_WANT_DO_FIND) && (defined(TRIE_WANT_FIND) || defined(TRIE_WANT_FIND_BUF))
111 #define TRIE_WANT_DO_FIND
114 #if !defined(TRIE_WANT_DO_LOOKUP) && (defined(TRIE_WANT_ADD) || defined(TRIE_WANT_REPLACE))
115 #define TRIE_WANT_DO_LOOKUP
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
122 #if !defined(TRIE_WANT_DO_LOOKUP)
123 #error You must request at least one method for inserting nodes
126 /*** Data structures ***/
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
135 u16 flags; // TRIE_FLAG_x
137 byte trans[TRIE_HASH_THRESHOLD]; // transition characters (!TRIE_FLAG_HASH)
139 byte hash_rank; // logarithmic hash size (TRIE_FLAG_HASH)
140 byte hash_deleted; // number of deleted items
143 P(len_t) len; // sum of all ancestor edges with their trasition
144 // characters plus the length of the current edge
146 P(node_t) *node; // inserted data (TRIE_FLAG_NODE)
147 struct P(edge) *leaf; // reference to a descendant with data (!TRIE_FLAG_NODE)
149 struct P(edge) *son[0]; // array of sons (!TRIE_FLAG_HASH)
150 // or hash table (TRIE_FLAG_HASH)
155 #define TA struct P(trie) *trie
160 static struct P(trie) P(trie);
168 /*** Memory management ***/
173 TRIE_DBG("Initializing");
174 bzero(&T, sizeof(T));
175 for (uns i = 0; i < ARRAY_SIZE(T.epool); i++)
177 uns size = sizeof(struct P(edge)) + i * sizeof(void *);
178 T.epool[i] = ep_new(size, MAX(TRIE_ELTPOOL_SIZE / size, 1));
180 for (uns i = 0; i < ARRAY_SIZE(T.hpool); i++)
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));
187 #ifdef TRIE_WANT_CLEANUP
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]);
199 static struct P(edge) *
200 P(edge_alloc)(TAC uns flags)
202 struct P(edge) *edge;
203 if (flags & TRIE_FLAG_HASH)
205 uns rank = 0, deg = flags & TRIE_FLAG_DEG;
206 while ((TRIE_BUCKET_MASK << rank) < deg * 2) // 25-50% density
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);
215 edge = ep_alloc(T.epool[flags & TRIE_FLAG_DEG]);
217 TRIE_DBG("Allocated edge %p, flags=0x%x", edge, flags);
222 P(edge_free)(TAC struct P(edge) *edge)
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);
228 ep_free(T.epool[edge->flags & TRIE_FLAG_DEG], edge);
231 /*** Manipulation with strings ***/
234 P(str_get)(P(node_t) *node)
236 return TRIE_NODE_KEY((*node));
240 P(str_len)(P(node_t) *node)
242 return TRIE_NODE_LEN((*node));
246 P(str_char)(byte *ptr, uns len UNUSED, uns pos)
251 return ptr[len - pos - 1];
256 P(str_prefix)(byte *ptr, uns len UNUSED, uns prefix UNUSED)
261 return ptr + len - prefix;
266 P(str_suffix)(byte *ptr, uns len UNUSED, uns suffix UNUSED)
269 return ptr + len - suffix;
276 P(common_prefix)(byte *ptr1, uns len1, byte *ptr2, uns len2)
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))
290 return hash_u32(c) >> 16;
293 static inline struct P(edge) **
294 P(hash_find)(struct P(edge) *edge, uns c)
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)
301 else if (((byte *)&edge->son[i & ~TRIE_BUCKET_MASK])[i & TRIE_BUCKET_MASK] == c)
302 return &edge->son[i];
305 static inline struct P(edge) **
306 P(hash_insert)(struct P(edge) *edge, uns c)
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)
312 edge->hash_deleted -= (uintptr_t)edge->son[i];
314 ((byte *)&edge->son[i & ~TRIE_BUCKET_MASK])[i & TRIE_BUCKET_MASK] = c;
315 return &edge->son[i];
319 #ifdef TRIE_WANT_DO_DELETE
321 P(hash_delete)(struct P(edge) *edge, uns c)
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)
328 edge->hash_deleted++;
329 edge->son[i] = (void *)1;
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]; \
342 #define TRIE_HASH_END_FOR }while(0);}}while(0)
345 P(hash_realloc)(TAC struct P(edge) **ref)
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;
354 P(edge_free)(TTC old);
357 /*** Finding/inserting/deleting sons ***/
359 static struct P(edge) **
360 P(son_find)(struct P(edge) *edge, uns c)
362 if (edge->flags & TRIE_FLAG_HASH)
363 return P(hash_find)(edge, c);
365 for (uns i = edge->flags & TRIE_FLAG_DEG; i--; )
366 if (edge->trans[i] == c)
367 return &edge->son[i];
371 static struct P(edge) **
372 P(son_insert)(TAC struct P(edge) **ref, uns c)
374 struct P(edge) *old = *ref, *edge;
375 uns deg = old->flags & TRIE_FLAG_DEG;
376 if (old->flags & TRIE_FLAG_HASH)
379 if ((deg + 1 + old->hash_deleted) * 4 > (TRIE_BUCKET_MASK << old->hash_rank) * 3) // >75% density
381 P(hash_realloc)(TTC ref);
389 if (deg < TRIE_HASH_THRESHOLD)
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);
399 return &edge->son[deg];
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);
413 return P(hash_insert)(edge, c);
416 #ifdef TRIE_WANT_DO_DELETE
418 P(son_delete)(TAC struct P(edge) **ref, uns c)
420 struct P(edge) *old = *ref, *edge;
421 uns deg = old->flags & TRIE_FLAG_DEG;
423 if (old->flags & TRIE_FLAG_HASH)
425 P(hash_delete)(old, c);
428 if (deg <= TRIE_HASH_THRESHOLD / 2)
430 TRIE_DBG("Reducing hash table to array");
431 edge = P(edge_alloc)(TTC old->flags & ~TRIE_FLAG_HASH);
433 TRIE_HASH_FOR_ALL(old, trans, son)
434 edge->trans[k] = trans;
440 else if (deg * 6 >= (TRIE_BUCKET_MASK << old->hash_rank)) // >= 16%
444 P(hash_realloc)(TTC ref);
451 TRIE_DBG("Reducing array");
452 edge = P(edge_alloc)(TTC old->flags - 1);
454 for (uns i = 0; i < deg; i++)
455 if (old->trans[i] != c)
457 edge->trans[j] = old->trans[i];
458 edge->son[j] = old->son[i];
461 ASSERT(j == deg - 1);
463 edge->node = old->node;
464 edge->len = old->len;
465 P(edge_free)(TTC old);
470 #ifdef TRIE_WANT_DO_DELETE
471 static struct P(edge) *
472 P(son_any)(struct P(edge) *edge)
474 ASSERT(edge->flags & TRIE_FLAG_DEG);
475 if (!(edge->flags & TRIE_FLAG_HASH))
478 for (uns i = 0; ; i++)
479 if ((i & TRIE_BUCKET_MASK) && (uintptr_t)edge->son[i] > 1)
484 /*** Find/insert/delete ***/
486 #ifdef TRIE_WANT_DO_FIND
487 static struct P(edge) *
488 P(do_find)(TAC byte *ptr, uns len)
490 TRIE_DBG("do_find('%.*s')", len, ptr);
491 struct P(edge) **ref = &T.root, *edge;
494 if (!(edge = *ref) || edge->len > len)
496 else if (edge->len == len)
497 return ((edge->flags & TRIE_FLAG_NODE) && !memcmp(ptr, P(str_get)(edge->node), len)) ? edge : NULL;
499 while (ref = P(son_find)(edge, P(str_char)(ptr, len, edge->len)));
504 static struct P(edge) *
505 P(do_lookup)(TAC byte *ptr, uns len)
507 TRIE_DBG("do_lookup('%.*s')", len, ptr);
508 struct P(edge) **ref, *edge, *leaf, *newleaf;
509 uns prefix, elen, trans, pos;
512 if (!(edge = T.root))
514 TRIE_DBG("Creating first edge");
515 edge = T.root = P(edge_alloc)(TTC TRIE_FLAG_NODE);
522 while (edge->len < len && (ref = P(son_find)(edge, P(str_char)(ptr, len, edge->len))))
524 if (!(edge->flags & TRIE_FLAG_NODE))
526 ASSERT(edge->flags & TRIE_FLAG_NODE);
527 eptr = P(str_get)(edge->node);
529 prefix = P(common_prefix)(ptr, len, eptr, elen);
530 if (prefix == len && prefix == elen)
532 TRIE_DBG("The longest common prefix is '%.*s'", prefix, P(str_prefix)(ptr, len, prefix));
536 TRIE_DBG("Creating a new leaf");
537 newleaf = P(edge_alloc)(TTC TRIE_FLAG_NODE);
538 newleaf->node = NULL;
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);
555 edge = P(edge_alloc)(TTC 1 | TRIE_FLAG_NODE);
558 edge->trans[0] = trans;
564 edge = P(edge_alloc)(TTC 2);
567 edge->trans[0] = trans;
569 edge->trans[1] = P(str_char)(ptr, len, prefix);
571 return edge->son[1] = newleaf;
576 TRIE_DBG("Adding the node to an already existing edge");
577 edge->flags |= TRIE_FLAG_NODE;
581 if (!(edge->flags & TRIE_FLAG_NODE) && newleaf)
582 edge->leaf = newleaf;
583 trans = P(str_char)(ptr, len, pos);
585 ref = P(son_find)(edge, trans);
587 ref = P(son_insert)(TTC ref, trans);
590 return *ref = newleaf;
593 #ifdef TRIE_WANT_DO_DELETE
595 P(do_delete)(TAC byte *ptr, uns len)
597 TRIE_DBG("do_delete('%.*s')", len, ptr);
598 struct P(edge) **ref = &T.root, **pref = NULL, *edge, *parent, *leaf, *pold = NULL;
601 if (!(edge = *ref) || edge->len > len)
603 else if (edge->len == len)
604 if ((edge->flags & TRIE_FLAG_NODE) && !memcmp(ptr, P(str_get)(edge->node), len))
609 if (!(ref = P(son_find)(edge, P(str_char)(ptr, len, edge->len))))
613 P(node_t) *node = edge->node;
614 uns deg = edge->flags & TRIE_FLAG_DEG;
620 TRIE_DBG("Deleting last edge");
622 P(edge_free)(TTC edge);
627 TRIE_DBG("Deleting a leaf");
629 P(son_delete)(TTC pref, P(str_char)(ptr, len, pold->len));
631 if ((parent->flags & (TRIE_FLAG_DEG | TRIE_FLAG_NODE)) <= 1)
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);
638 else if (parent->flags & TRIE_FLAG_NODE)
641 leaf = P(son_any)(parent);
643 P(edge_free)(TTC edge);
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);
654 TRIE_DBG("Deleting node, but leaving edge");
655 leaf = P(son_any)(edge);
656 if (!(leaf->flags & TRIE_FLAG_NODE))
659 edge->flags &= ~TRIE_FLAG_NODE;
662 TRIE_DBG("Updating leaf pointers");
663 if (!(leaf->flags & TRIE_FLAG_NODE))
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)
673 #ifdef TRIE_WANT_FIND
674 static inline P(node_t) *
675 P(find)(TAC char *str)
677 struct P(edge) *edge = P(do_find)(TTC str, str_len(str));
678 return edge ? edge->node : NULL;
682 #ifdef TRIE_WANT_FIND_BUF
683 static inline P(node_t) *
684 P(find_buf)(TAC byte *ptr, uns len)
686 struct P(edge) *edge = P(do_find)(TTC ptr, len);
687 return edge ? edge->node : NULL;
693 P(add)(TAC P(node_t) *node)
695 struct P(edge) *edge = P(do_lookup)(TTC P(str_get)(node), P(str_len)(node));
701 #ifdef TRIE_WANT_REPLACE
702 static inline P(node_t) *
703 P(replace)(TAC P(node_t) *node)
705 struct P(edge) *edge = P(do_lookup)(TTC P(str_get)(node), P(str_len)(node));
706 P(node_t) *over = edge->node;
712 #ifdef TRIE_WANT_DELETE
713 static inline P(node_t) *
714 P(delete)(TAC char *str)
716 return P(do_delete)(TTC str, str_len(str));
720 #ifdef TRIE_WANT_DELETE_BUF
721 static inline P(node_t) *
722 P(delete_buf)(TAC byte *ptr, uns len)
724 return P(do_delete)(TTC ptr, len);
728 #ifdef TRIE_WANT_REMOVE
730 P(remove)(TAC P(node_t) *node)
732 if (unlikely(P(do_delete)(TTC P(str_get)(node), P(str_len)(node)) != node))
737 /*** Traversing prefixes and subtrees ***/
741 // for all matched edges until the first >=xlen (including)
742 #define TRIE_FOR_PREFIX_EDGES(px, xtrie, xptr, xlen, xedge) \
745 byte *_ptr = (xptr); \
747 struct px##trie *_trie = (xtrie); \
748 struct px##edge *xedge, **_ref; \
749 if (!(xedge = _trie->root)) \
751 while (xedge->len < _len && (_ref = px##son_find(xedge, px##str_char(_ptr, _len, xedge->len)))) \
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) \
759 #define TRIE_END_PREFIX_EDGES \
764 // for entire subtree starting in the xstart edge
765 #define TRIE_FOR_SUBTREE_EDGES(px, xstart, xedge) \
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) \
774 if (xedge->flags & TRIE_FLAG_DEG) \
776 if (_sptr == _send) \
778 uns stack_size = _sptr - _sbuf; \
779 _sptr = alloca(sizeof(*_sptr) * (stack_size * 2)); \
780 memcpy(_sptr, _sbuf, sizeof(*_sptr) * stack_size); \
782 _send = _sptr + stack_size * 2; \
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); \
792 if (_sptr == _sbuf) \
797 _next = (--_sptr)->edge; \
798 uns pos = --(_sptr->pos); \
799 uns flags = _next->flags; \
800 _next = _next->son[pos]; \
803 if (!(flags & TRIE_FLAG_HASH) || \
804 ((pos & ((1U << px##bucket_rank) - 1)) && \
805 (uintptr_t)_next > 1)) \
808 #define TRIE_END_SUBTREE_EDGES \
813 #define TRIE_FOR_SUBTREE(px, xstart, xnode) \
814 TRIE_FOR_SUBTREE_EDGES(px, xstart, _edge) \
815 if (_edge->flags & TRIE_FLAG_NODE) \
817 px##node_t *xnode = _edge->node;
818 #define TRIE_END_SUBTREE \
820 TRIE_END_SUBTREE_EDGES;
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
825 #define TRIE_FOR_ALL(px, xtrie, xnode) TRIE_FOR_SUBTREE(px, (xtrie)->root, xnode)
826 #define TRIE_END_ALL TRIE_END_SUBTREE
830 /*** Check consistency ***/
832 #ifdef TRIE_WANT_AUDIT
838 TRIE_FOR_ALL_EDGES(TRIE_PREFIX(), &T, edge)
841 uns deg = edge->flags & TRIE_FLAG_DEG;
843 struct P(edge) * leaf = (edge->flags & TRIE_FLAG_NODE) ? edge : edge->leaf;
846 ASSERT(leaf->flags & TRIE_FLAG_NODE);
847 ASSERT(leaf->len > edge->len);
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)
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)
862 else if (edge->son[i])
864 ASSERT(edge->son[i]->len > edge->len);
867 ASSERT(count == deg);
868 ASSERT(deleted == edge->hash_deleted);
872 ASSERT(deg <= TRIE_HASH_THRESHOLD);
873 for (uns i = 0; i < deg; i++)
874 ASSERT(edge->son[i]->len > edge->len);
879 TRIE_DBG("Found %u edges", count);
886 #ifdef TRIE_WANT_STATS
895 P(stats)(TAC struct P(stats) *stats)
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->total_size + sizeof(T);
908 struct P(stats) stats;
909 P(stats)(TTC &stats);
910 return stats.total_size;
915 /*** Clean up local macros ***/
925 #undef TRIE_NODE_TYPE
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
938 #undef TRIE_HASH_FOR_ALL
939 #undef TRIE_HASH_END_FOR
941 #undef TRIE_WANT_CLEANUP
943 #undef TRIE_WANT_DO_FIND
944 #undef TRIE_WANT_DO_LOOKUP
945 #undef TRIE_WANT_DO_DELETE
947 #undef TRIE_WANT_FIND
948 #undef TRIE_WANT_FIND_BUF
950 #undef TRIE_WANT_ADD_OVER
951 #undef TRIE_WANT_DELETE
952 #undef TRIE_WANT_DELETE_BUF
953 #undef TRIE_WANT_REMOVE
955 #undef TRIE_WANT_AUDIT