3 * ===============================================================
4 * CS:S DM, Copyright (C) 2004-2007 AlliedModders LLC.
5 * By David "BAILOPAN" Anderson
7 * ===============================================================
9 * This program is free software; you can redistribute it and/or modify
10 * it under the terms of the GNU General Public License as published by
11 * the Free Software Foundation; either version 2 of the License, or (at
12 * your option) any later version.
14 * This program is distributed in the hope that it will be useful, but
15 * WITHOUT ANY WARRANTY; without even the implied warranty of
16 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
17 * General Public License for more details.
19 * You should have received a copy of the GNU General Public License
20 * along with this program; see the file COPYING; if not, write to the
21 * Free Software Foundation, Inc., 51 Franklin St, Fifth Floor, Boston,
34 * Double Array Trie algorithm, based on:
35 * An Efficient Implementation of Trie Structures, by
36 * Jun-ichi Aoe and Katsushi Maromoto, and Takashi Sato
37 * from Software - Practice and Experience, Vol. 22(9), 695-721 (September 1992)
39 * A Trie is a simple data structure which stores strings as DFAs, with each
40 * transition state being a string entry. For example, observe the following strings:
42 * BAILOPAN, BAT, BACON, BACK
43 * These transition as the follow production rules:
54 * The standard implementation for this - using lists - gives a slow linear lookup, somewhere between
55 * O(N+M) or O(log n). A faster implementation is proposed in the paper above, which is based on compacting
56 * the transition states into two arrays. In the paper's implementation, two arrays are used, and thus it is
57 * called the "Double Array" algorithm. However, the CHECK array's size is maintained the same as BASE,
58 * so they can be combined into one structure. The array seems complex at first, but is very simple: it is a
59 * tree structure flattened out into a single vector. I am calling this implementation the Flat Array Trie.
61 * BASE[] is an array where each member is a node in the Trie. The node can either be UNUSED (empty), an ARC
62 * (containing an offset to the next set of ARCs), or a TERMINATOR (contains the rest of a string).
63 * Each node has an index which must be interpreted based on the node type. If the node is a TERMINATOR, then the
64 * index is an index into a string table, to find the rest of the string.
65 * If the node is an ARC, the index is another index into BASE. For each possible token that can follow the
66 * current token, the value of those tokens can be added to the index given in the ARC. Thus, given a current
67 * position and the next desired token, the current arc will jump to another arc which can contain either:
68 * 1) An invalid production (collision, no entry exists)
69 * 2) An empty production (no entry exists)
70 * 3) Another arc label (the string ends here or continues into more productions)
71 * 4) A TERMINATOR (the string ends here and contains an unused set of productions)
73 * So, given current offset N (starting at N=1), jumping to token C means the next offset will be:
75 * Thus, the next node will be at:
78 * This allows each ARC to specify the base offset for any of its ARC children, like a tree. Each node specifies
79 * its parent ARC -- so if an invalid offset is specified, the parent will not match, and thus no such derived
82 * This means that arrays can be laid out "sparsely," maximizing their usage. Note that N need not be related to
83 * the range of tokens (1-256). I.e., a base index does not have to be at 1, 256, 512, et cetera. This is because
84 * insertion comes with a small deal of complexity. To insert a new set of tokens T, the algorithm finds a new
85 * BASE index N such that BASE[N+T[i]] is unused for each T[i]. Thus, indirection is not necessarily linear;
86 * traversing a chain of ARC nodes can _and will_ jump around BASE.
88 * Of course, given this level of flexibility in the array organization, there are collisions. This is largely
89 * where insertions become slow, as the old chain must be relocated before the new one is used. Relocation means
90 * finding one or more new base indexes, and this means traversing BASE until an acceptable index is found, such
91 * that each offset is unused (see description in previous paragraph).
93 * However, it is not insertion time we are concerned about. The "trie" name comes from reTRIEval. We are only
94 * concerned with lookup and deletion. Both lookup and deletion are O(k), where k is relative to the length of the
95 * input string. Note that it is best case O(1) and worst case O(k). Deleting the entire trie is always O(1).
99 * Optimization ideas for the future:
100 * 1) Store a reference count for each arc, with the count of sub-children.
101 * This could let us break out of "children searches" for case 4 easily.
102 * 2) Use a 'free list' so we can easily search the trie for free points.
103 * This would drastically speed up x_check*
108 Node_Unused = 0, /* Node is not being used (sparse) */
109 Node_Arc, /* Node is part of an arc and does not terminate */
110 Node_Term, /* Node is a terminator */
116 * For Node_Arc, this index stores the 'base' offset to the next arc chain.
117 * I.e. to jump from this arc to character C, it will be at base[idx+C].
118 * For Node_Term, this is an index into the string table.
123 * This contains the prior arc that we must have come from.
124 * For example, if arc 63 has a base jump of index 12, and we want to see if
125 * there is a valid character C, the parent of 12+C must be 63.
129 void *value; /* Value associated with this node */
130 NodeType mode; /* Current usage type of the node */
131 bool valset; /* Whether or not a value is set */
136 TrieNode *base; /* Base array for the sparse tables */
137 char *stringtab; /* String table pointer */
138 unsigned int baseSize; /* Size of the base array, in members */
139 unsigned int stSize; /* Size of the string table, in bytes */
140 unsigned int tail; /* Current unused offset into the string table */
143 inline unsigned char charval(char c)
145 return (unsigned char)c;
148 bool sm_trie_grow(Trie *trie)
150 /* The current # of nodes in the tree is trie->baseSize + 1 */
151 unsigned int curSize = trie->baseSize;
152 unsigned int newSize = curSize * 2;
154 //:TODO: Make functions calling this return failure if this fails
155 trie->base = (TrieNode *)realloc(trie->base, (newSize + 1) * sizeof(TrieNode));
161 memset(&trie->base[curSize+1], 0, (newSize - curSize) * sizeof(TrieNode));
162 trie->baseSize = newSize;
167 unsigned int x_check(Trie *trie, char c, unsigned int start=1)
169 TrieNode *base = trie->base;
170 unsigned char _c = charval(c);
171 unsigned int to_check = trie->baseSize - _c;
172 for (unsigned int i=start; i<=to_check; i++)
174 if (base[i+_c].mode == Node_Unused)
182 return x_check(trie, c, to_check+1);
185 unsigned int x_check2(Trie *trie, char c1, char c2, unsigned int start=1)
187 TrieNode *base = trie->base;
188 unsigned char _c1 = charval(c1);
189 unsigned char _c2 = charval(c2);
190 unsigned int to_check = trie->baseSize - (_c1 > _c2 ? _c1 : _c2);
191 for (unsigned int i=start; i<=to_check; i++)
193 if (base[i+_c1].mode == Node_Unused
194 && base[i+_c2].mode == Node_Unused)
202 return x_check2(trie, c1, c2, to_check+1);
205 unsigned int x_check_multi(Trie *trie,
206 unsigned int offsets[],
208 unsigned int start=1)
210 TrieNode *base = trie->base;
212 unsigned int to_check = trie->baseSize;
213 unsigned int highest = 0;
215 for (unsigned int i=0; i<count; i++)
217 if (offsets[i] > highest)
219 highest = offsets[i];
225 for (unsigned int i=start; i<=to_check; i++)
228 for (unsigned int j=0; j<count; j++)
230 cur = &base[i+offsets[j]];
231 if (cur->mode != Node_Unused)
245 return x_check_multi(trie, offsets, count, to_check+1);
248 unsigned int x_addstring(Trie *trie, const char *ptr)
250 size_t len = strlen(ptr) + 1;
252 if (trie->tail + len >= trie->stSize)
254 while (trie->tail + len >= trie->stSize)
258 trie->stringtab = (char *)realloc(trie->stringtab, trie->stSize);
261 unsigned int tail = trie->tail;
262 strcpy(&trie->stringtab[tail], ptr);
268 Trie *sm_trie_create()
272 t->base = (TrieNode *)malloc(sizeof(TrieNode) * (256 + 1));
273 t->stringtab = (char *)malloc(sizeof(char) * 256);
282 void sm_trie_clear(Trie *trie)
286 memset(trie->base, 0, sizeof(TrieNode) * (trie->baseSize + 1));
287 memset(trie->stringtab, 0, sizeof(char) * trie->stSize);
289 /* Sentinel root node */
290 trie->base[1].idx = 1;
291 trie->base[1].mode = Node_Arc;
292 trie->base[1].parent = 1;
295 void sm_trie_destroy(Trie *trie)
298 free(trie->stringtab);
302 bool sm_trie_delete(Trie *trie, const char *key)
304 unsigned int lastidx = 1; /* the last node index */
305 unsigned int curidx; /* current node index */
306 const char *keyptr = key; /* input stream at current token */
307 TrieNode *node = NULL; /* current node being processed */
308 TrieNode *base = trie->base;
315 /* Start traversing at the root node */
318 /* Find where the next character is, then advance */
319 curidx = base[lastidx].idx;
320 node = &base[curidx];
321 curidx += charval(*keyptr);
322 node = &base[curidx];
325 /* Check if this slot is supposed to be empty or is a collision */
326 if ((curidx > trie->baseSize) || node->mode == Node_Unused || node->parent != lastidx)
329 } else if (node->mode == Node_Term) {
330 char *term = &trie->stringtab[node->idx];
331 if (strcmp(keyptr, term) == 0)
337 } while (*keyptr != '\0');
339 assert(node != NULL);
346 node->valset = false;
352 bool sm_trie_retrieve(Trie *trie, const char *key, void **value)
354 unsigned int lastidx = 1; /* the last node index */
355 unsigned int curidx; /* current node index */
356 const char *keyptr = key; /* input stream at current token */
357 TrieNode *node = NULL; /* current node being processed */
358 TrieNode *base = trie->base;
365 /* Start traversing at the root node */
368 /* Find where the next character is, then advance */
369 curidx = base[lastidx].idx;
370 node = &base[curidx];
371 curidx += charval(*keyptr);
372 node = &base[curidx];
375 /* Check if this slot is supposed to be empty or is a collision */
376 if ((curidx > trie->baseSize) || node->mode == Node_Unused || node->parent != lastidx)
379 } else if (node->mode == Node_Term) {
380 char *term = &trie->stringtab[node->idx];
381 if (strcmp(keyptr, term) == 0)
387 } while (*keyptr != '\0');
389 assert(node != NULL);
398 *value = node->value;
404 bool sm_trie_insert(Trie *trie, const char *key, void *value)
406 unsigned int lastidx = 1; /* the last node index */
407 unsigned int curidx; /* current node index */
408 const char *keyptr = key; /* input stream at current token */
409 TrieNode *node = NULL; /* current node being processed */
410 TrieNode *basenode = NULL; /* current base node being processed */
411 unsigned int q; /* temporary var for x_check results */
412 TrieNode *base = trie->base;
413 unsigned int curoffs; /* current offset */
415 /* Do not handle empty strings for simplicity */
421 /* Start traversing at the root node (1) */
424 /* Find where the next character is, then advance */
425 curidx = base[lastidx].idx;
426 basenode = &base[curidx];
427 curoffs = charval(*keyptr);
429 node = &base[curidx];
432 /* Check if this slot is supposed to be empty. If so, we need to handle CASES 1/2:
433 * Insertion without collisions
435 if ( (curidx > trie->baseSize) || (node->mode == Node_Unused) )
437 if (curidx > trie->baseSize)
439 if (!sm_trie_grow(trie))
443 node = &trie->base[curidx];
445 node->parent = lastidx;
448 node->mode = Node_Arc;
450 node->idx = x_addstring(trie, keyptr);
451 node->mode = Node_Term;
457 } else if (node->parent != lastidx) {
458 /* Collision! We have to split up the tree here. CASE 4:
459 * Insertion when a new word is inserted with a collision.
460 * NOTE: This is the hardest case to handle. All below examples are based on:
461 * BACHELOR, BADGE, inserting BABY.
462 * The problematic production here is A -> B, where B is already being used.
464 * This process has to rotate one half of the 'A' arc. We generate two lists:
465 * Outgoing Arcs - Anything leaving this 'A'
466 * Incoming Arcs - Anything going to this 'A'
467 * Whichever list is smaller will be moved. Note that this works because the intersection
468 * affects both arc chains, and moving one will make the slot available to either.
472 /* Find every node arcing from the last node.
473 * I.e. for BACHELOR, BADGE, BABY,
474 * The arcs leaving A will be C and D, but our current node is B -> *.
475 * Thus, we use the last index (A) to find the base for arcs leaving A.
477 unsigned int outgoing_base = base[lastidx].idx;
478 unsigned int outgoing_list[256];
479 unsigned int outgoing_count = 0; /* count the current index here */
480 cur = &base[outgoing_base] + 1;
481 unsigned int outgoing_limit = 255;
483 if (outgoing_base + outgoing_limit > trie->baseSize)
485 outgoing_limit = trie->baseSize - outgoing_base;
488 for (unsigned int i=1; i<=outgoing_limit; i++,cur++)
490 if (cur->mode == Node_Unused || cur->parent != lastidx)
494 outgoing_list[outgoing_count++] = i;
496 outgoing_list[outgoing_count++] = curidx - outgoing_base;
498 /* Now we need to find all the arcs leaving our parent...
499 * Note: the inconsistency is the base of our parent.
501 assert(base[node->parent].mode == Node_Arc);
502 unsigned int incoming_list[256];
503 unsigned int incoming_base = base[node->parent].idx;
504 unsigned int incoming_count = 0;
505 unsigned int incoming_limit = 255;
506 cur = &base[incoming_base] + 1;
508 if (incoming_base + incoming_limit > trie->baseSize)
510 incoming_limit = trie->baseSize - incoming_base;
513 assert(incoming_limit > 0 && incoming_limit <= 255);
515 for (unsigned int i=1; i<=255; i++,cur++)
517 if (cur->mode == Node_Arc || cur->mode == Node_Term)
519 if (cur->parent == node->parent)
521 incoming_list[incoming_count++] = i;
526 if (incoming_count < outgoing_count + 1)
528 unsigned int q = x_check_multi(trie, incoming_list, incoming_count);
531 node = &base[curidx];
533 /* If we're incoming, we need to modify our parent */
534 base[node->parent].idx = q;
536 /* For each node in the "to move" list,
537 * Relocate the node's info to the new position.
539 unsigned int idx, newidx, oldidx;
540 for (unsigned int i=0; i<incoming_count; i++)
542 idx = incoming_list[i];
544 oldidx = incoming_base + idx;
545 if (oldidx == lastidx)
547 /* Important! Make sure we're not invalidating our sacred lastidx */
550 base[newidx] = base[oldidx];
551 assert(base[base[newidx].parent].mode == Node_Arc);
552 memset(&base[oldidx], 0, sizeof(TrieNode));
553 /* If we are not a terminator, we have children we must take care of */
554 if (base[newidx].mode == Node_Arc)
556 TrieNode *check_base = &base[base[newidx].idx] + 1;
557 for (unsigned int j=1; j<=255; j++, check_base++)
559 if (check_base->parent == oldidx)
561 check_base->parent = newidx;
567 unsigned int q = x_check_multi(trie, outgoing_list, outgoing_count);
570 node = &base[curidx];
572 /* If we're outgoing, we need to modify our own base */
573 base[lastidx].idx = q;
575 /* Take the last index (curidx) out of the list. Technically we are not moving this,
576 * since it's already being used by something else.
580 /* For each node in the "to move" list,
581 * Relocate the node's info to the new position.
583 unsigned int idx, newidx, oldidx;
584 for (unsigned int i=0; i<outgoing_count; i++)
586 idx = outgoing_list[i];
588 oldidx = outgoing_base + idx;
589 if (oldidx == lastidx)
591 /* Important! Make sure we're not invalidating our sacred lastidx */
594 base[newidx] = base[oldidx];
595 assert(base[base[newidx].parent].mode == Node_Arc);
596 memset(&base[oldidx], 0, sizeof(TrieNode));
597 /* If we are not a terminator, we have children we must take care of */
598 if (base[newidx].mode == Node_Arc)
600 TrieNode *check_base = &base[base[newidx].idx] + 1;
601 for (unsigned int j=1; j<=255; j++, check_base++)
603 if (check_base->parent == oldidx)
605 check_base->parent = newidx;
611 /* Take the invisible node and use it as our new node */
612 node = &base[q + outgoing_list[outgoing_count]];
615 /* We're finally done! */
616 node->parent = lastidx;
619 node->mode = Node_Arc;
621 node->idx = x_addstring(trie, keyptr);
622 node->mode = Node_Term;
629 /* See what's in the next node - special case if terminator! */
630 if (node->mode == Node_Term)
632 /* If we're a terminator, we need to handle CASE 3:
633 * Insertion when a terminating collision occurs
635 char *term = &trie->stringtab[node->idx];
636 /* Do an initial browsing to make sure they're not the same string */
637 if (strcmp(keyptr, term) == 0)
645 /* Same string. We can't insert. */
648 /* For each matching character pair, we need to disband the terminator.
649 * This splits the similar prefix into a single arc path.
650 * First, save the old values so we can move them to a new node.
651 * Next, for each loop:
652 * Take the current (invalid) node, and point it to the next arc base.
653 * Set the current node to the node at the next arc.
655 void *oldvalue = node->value;
656 bool oldvalset = node->valset;
657 if (*term == *keyptr)
659 while (*term == *keyptr)
661 /* Find the next free slot in the check array.
662 * This is the "vector base" essentially
664 q = x_check(trie, *term);
666 node = &base[curidx];
667 /* Point the node to the next new base */
669 node->mode = Node_Arc;
670 node->valset = false;
671 /* Advance the input stream and local variables */
673 curidx = q + charval(*term);
674 node = &base[curidx];
675 /* Make sure the new current node has its parent set. */
676 node->parent = lastidx;
677 node->mode = Node_Arc; /* Just in case we run x_check again */
678 *term = '\0'; /* Unmark the string table here */
683 node->valset = false;
685 /* We're done inserting new pairs. If one of them is exhausted,
686 * we take special shortcuts.
688 if (*term == '\0') //EX: BADGERHOUSE added over B -> ADGER.
690 /* First backpatch the current node - it ends the newly split terminator.
691 * In the example, this would mean the node is the production from R -> ?
692 * This node ends the old BADGER, so we set it here.
694 node->valset = oldvalset;
695 node->value = oldvalue;
697 /* The terminator was split up, but pieces of keyptr remain.
698 * We need to generate a new production, in this example, R -> H,
699 * with H being a terminator to OUSE. Thus we get:
700 * B,A,D,G,E,R*,H*->OUSE (* = value set).
701 * NOTE: parent was last set at the end of the while loop.
703 /* Get the new base and apply re-basing */
704 q = x_check(trie, *keyptr);
706 node = &base[curidx];
709 node->mode = Node_Arc;
711 /* Finish the final node */
712 curidx = q + charval(*keyptr);
713 node = &trie->base[curidx];
715 /* Optimize - don't add to string table if there's nothing more to eat */
718 node->mode = Node_Arc;
720 node->idx = x_addstring(trie, keyptr);
721 node->mode = Node_Term;
723 node->parent = lastidx;
726 } else if (*keyptr == '\0') { //EX: BADGER added over B -> ADGERHOUSE
727 /* First backpatch the current node - it ends newly split input string.
728 * This is the exact opposite of the above procedure.
733 /* Get the new base and apply re-basing */
734 q = x_check(trie, *term);
736 node = &base[curidx];
739 node->mode = Node_Arc;
741 /* Finish the final node */
742 curidx = q + charval(*term);
743 node = &trie->base[curidx];
745 /* Optimize - don't add to string table if there's nothing more to eat */
748 node->mode = Node_Arc;
750 node->idx = (term - trie->stringtab); /* Already in the string table! */
751 node->mode = Node_Term;
753 node->parent = lastidx;
754 node->valset = oldvalset;
755 node->value = oldvalue;
757 /* Finally, we have to create two new nodes instead of just one. */
758 node->mode = Node_Arc;
760 /* Get the new base and apply re-basing */
761 q = x_check2(trie, *keyptr, *term);
763 node = &base[curidx];
768 /* Re-create the old terminated node */
769 curidx = q + charval(*term);
770 node = &trie->base[curidx];
772 node->valset = oldvalset;
773 node->value = oldvalue;
774 node->parent = lastidx;
777 node->mode = Node_Arc;
779 node->mode = Node_Term;
780 node->idx = (term - trie->stringtab); /* Already in the string table! */
783 /* Create the new keyed input node */
784 curidx = q + charval(*keyptr);
785 node = &trie->base[curidx];
789 node->parent = lastidx;
792 node->mode = Node_Arc;
794 node->mode = Node_Term;
795 node->idx = x_addstring(trie, keyptr);
802 assert(node->mode == Node_Arc);
806 } while (*keyptr != '\0');
810 /* If we've exhausted the string and we have a valid reached node,
811 * the production rule already existed. Make sure it's valid to set first.
814 /* We have to be an Arc. If the last result was anything else, we would have returned a new
815 * production earlier.
817 assert(node->mode == Node_Arc);
821 /* Insert is only possible if we have no production */