1.1 --- a/core/sm_trie.cpp Wed Aug 29 02:43:07 2007 +0000
1.2 +++ b/core/sm_trie.cpp Wed Aug 29 05:20:48 2007 +0000
1.3 @@ -30,788 +30,58 @@
1.4 */
1.5
1.6 #include <string.h>
1.7 -#include <stdlib.h>
1.8 #include <assert.h>
1.9 #include "sm_trie.h"
1.10 -
1.11 -/**
1.12 - * Double Array Trie algorithm, based on:
1.13 - * An Efficient Implementation of Trie Structures, by
1.14 - * Jun-ichi Aoe and Katsushi Maromoto, and Takashi Sato
1.15 - * from Software - Practice and Experience, Vol. 22(9), 695-721 (September 1992)
1.16 - *
1.17 - * A Trie is a simple data structure which stores strings as DFAs, with each
1.18 - * transition state being a string entry. For example, observe the following strings:
1.19 - *
1.20 - * BAILOPAN, BAT, BACON, BACK
1.21 - * These transition as the follow production rules:
1.22 - * B -> ... B
1.23 - * A -> ... BA
1.24 - * I -> ... BAI
1.25 - * LOPAN BAILOPAN
1.26 - * T -> ... BAT
1.27 - * C -> BAC
1.28 - * O -> ... BACO
1.29 - * N BACON
1.30 - * K BACK
1.31 - *
1.32 - * The standard implementation for this - using lists - gives a slow linear lookup, somewhere between
1.33 - * O(N+M) or O(log n). A faster implementation is proposed in the paper above, which is based on compacting
1.34 - * the transition states into two arrays. In the paper's implementation, two arrays are used, and thus it is
1.35 - * called the "Double Array" algorithm. However, the CHECK array's size is maintained the same as BASE,
1.36 - * so they can be combined into one structure. The array seems complex at first, but is very simple: it is a
1.37 - * tree structure flattened out into a single vector. I am calling this implementation the Flat Array Trie.
1.38 - *
1.39 - * BASE[] is an array where each member is a node in the Trie. The node can either be UNUSED (empty), an ARC
1.40 - * (containing an offset to the next set of ARCs), or a TERMINATOR (contains the rest of a string).
1.41 - * Each node has an index which must be interpreted based on the node type. If the node is a TERMINATOR, then the
1.42 - * index is an index into a string table, to find the rest of the string.
1.43 - * If the node is an ARC, the index is another index into BASE. For each possible token that can follow the
1.44 - * current token, the value of those tokens can be added to the index given in the ARC. Thus, given a current
1.45 - * position and the next desired token, the current arc will jump to another arc which can contain either:
1.46 - * 1) An invalid production (collision, no entry exists)
1.47 - * 2) An empty production (no entry exists)
1.48 - * 3) Another arc label (the string ends here or continues into more productions)
1.49 - * 4) A TERMINATOR (the string ends here and contains an unused set of productions)
1.50 - *
1.51 - * So, given current offset N (starting at N=1), jumping to token C means the next offset will be:
1.52 - * offs = BASE[n] + C
1.53 - * Thus, the next node will be at:
1.54 - * BASE[BASE[n] + C]
1.55 - *
1.56 - * This allows each ARC to specify the base offset for any of its ARC children, like a tree. Each node specifies
1.57 - * its parent ARC -- so if an invalid offset is specified, the parent will not match, and thus no such derived
1.58 - * string exists.
1.59 - *
1.60 - * This means that arrays can be laid out "sparsely," maximizing their usage. Note that N need not be related to
1.61 - * 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
1.62 - * insertion comes with a small deal of complexity. To insert a new set of tokens T, the algorithm finds a new
1.63 - * BASE index N such that BASE[N+T[i]] is unused for each T[i]. Thus, indirection is not necessarily linear;
1.64 - * traversing a chain of ARC nodes can _and will_ jump around BASE.
1.65 - *
1.66 - * Of course, given this level of flexibility in the array organization, there are collisions. This is largely
1.67 - * where insertions become slow, as the old chain must be relocated before the new one is used. Relocation means
1.68 - * finding one or more new base indexes, and this means traversing BASE until an acceptable index is found, such
1.69 - * that each offset is unused (see description in previous paragraph).
1.70 - *
1.71 - * However, it is not insertion time we are concerned about. The "trie" name comes from reTRIEval. We are only
1.72 - * concerned with lookup and deletion. Both lookup and deletion are O(k), where k is relative to the length of the
1.73 - * input string. Note that it is best case O(1) and worst case O(k). Deleting the entire trie is always O(1).
1.74 - */
1.75 -
1.76 -/**
1.77 - * Optimization ideas for the future:
1.78 - * 1) Store a reference count for each arc, with the count of sub-children.
1.79 - * This could let us break out of "children searches" for case 4 easily.
1.80 - * 2) Use a 'free list' so we can easily search the trie for free points.
1.81 - * This would drastically speed up x_check*
1.82 - */
1.83 -
1.84 -struct TrieNode
1.85 -{
1.86 - /**
1.87 - * For Node_Arc, this index stores the 'base' offset to the next arc chain.
1.88 - * I.e. to jump from this arc to character C, it will be at base[idx+C].
1.89 - * For Node_Term, this is an index into the string table.
1.90 - */
1.91 - unsigned int idx;
1.92 -
1.93 - /**
1.94 - * This contains the prior arc that we must have come from.
1.95 - * For example, if arc 63 has a base jump of index 12, and we want to see if
1.96 - * there is a valid character C, the parent of 12+C must be 63.
1.97 - */
1.98 - unsigned int parent;
1.99 -
1.100 - void *value; /* Value associated with this node */
1.101 - NodeType mode; /* Current usage type of the node */
1.102 - bool valset; /* Whether or not a value is set */
1.103 -};
1.104 +#include "sm_trie_tpl.h"
1.105
1.106 struct Trie
1.107 {
1.108 - TrieNode *base; /* Base array for the sparse tables */
1.109 - char *stringtab; /* String table pointer */
1.110 - unsigned int baseSize; /* Size of the base array, in members */
1.111 - unsigned int stSize; /* Size of the string table, in bytes */
1.112 - unsigned int tail; /* Current unused offset into the string table */
1.113 + KTrie<void *> k;
1.114 };
1.115
1.116 -inline unsigned char charval(char c)
1.117 -{
1.118 - return (unsigned char)c;
1.119 -}
1.120 -
1.121 -bool sm_trie_grow(Trie *trie)
1.122 -{
1.123 - /* The current # of nodes in the tree is trie->baseSize + 1 */
1.124 - unsigned int curSize = trie->baseSize;
1.125 - unsigned int newSize = curSize * 2;
1.126 -
1.127 - //:TODO: Make functions calling this return failure if this fails
1.128 - trie->base = (TrieNode *)realloc(trie->base, (newSize + 1) * sizeof(TrieNode));
1.129 - if (!trie->base)
1.130 - {
1.131 - return false;
1.132 - }
1.133 -
1.134 - memset(&trie->base[curSize+1], 0, (newSize - curSize) * sizeof(TrieNode));
1.135 - trie->baseSize = newSize;
1.136 -
1.137 - return true;
1.138 -}
1.139 -
1.140 -unsigned int x_check(Trie *trie, char c, unsigned int start=1)
1.141 -{
1.142 - TrieNode *base = trie->base;
1.143 - unsigned char _c = charval(c);
1.144 - unsigned int to_check = trie->baseSize - _c;
1.145 - for (unsigned int i=start; i<=to_check; i++)
1.146 - {
1.147 - if (base[i+_c].mode == Node_Unused)
1.148 - {
1.149 - return i;
1.150 - }
1.151 - }
1.152 -
1.153 - sm_trie_grow(trie);
1.154 -
1.155 - return x_check(trie, c, to_check+1);
1.156 -}
1.157 -
1.158 -unsigned int x_check2(Trie *trie, char c1, char c2, unsigned int start=1)
1.159 -{
1.160 - TrieNode *base = trie->base;
1.161 - unsigned char _c1 = charval(c1);
1.162 - unsigned char _c2 = charval(c2);
1.163 - unsigned int to_check = trie->baseSize - (_c1 > _c2 ? _c1 : _c2);
1.164 - for (unsigned int i=start; i<=to_check; i++)
1.165 - {
1.166 - if (base[i+_c1].mode == Node_Unused
1.167 - && base[i+_c2].mode == Node_Unused)
1.168 - {
1.169 - return i;
1.170 - }
1.171 - }
1.172 -
1.173 - sm_trie_grow(trie);
1.174 -
1.175 - return x_check2(trie, c1, c2, to_check+1);
1.176 -}
1.177 -
1.178 -unsigned int x_check_multi(Trie *trie,
1.179 - unsigned int offsets[],
1.180 - unsigned int count,
1.181 - unsigned int start=1)
1.182 -{
1.183 - TrieNode *base = trie->base;
1.184 - TrieNode *cur;
1.185 - unsigned int to_check = trie->baseSize;
1.186 - unsigned int highest = 0;
1.187 -
1.188 - for (unsigned int i=0; i<count; i++)
1.189 - {
1.190 - if (offsets[i] > highest)
1.191 - {
1.192 - highest = offsets[i];
1.193 - }
1.194 - }
1.195 -
1.196 - to_check -= highest;
1.197 -
1.198 - for (unsigned int i=start; i<=to_check; i++)
1.199 - {
1.200 - bool okay = true;
1.201 - for (unsigned int j=0; j<count; j++)
1.202 - {
1.203 - cur = &base[i+offsets[j]];
1.204 - if (cur->mode != Node_Unused)
1.205 - {
1.206 - okay = false;
1.207 - break;
1.208 - }
1.209 - }
1.210 - if (okay)
1.211 - {
1.212 - return i;
1.213 - }
1.214 - }
1.215 -
1.216 - sm_trie_grow(trie);
1.217 -
1.218 - return x_check_multi(trie, offsets, count, to_check+1);
1.219 -}
1.220 -
1.221 -unsigned int x_addstring(Trie *trie, const char *ptr)
1.222 -{
1.223 - size_t len = strlen(ptr) + 1;
1.224 -
1.225 - if (trie->tail + len >= trie->stSize)
1.226 - {
1.227 - while (trie->tail + len >= trie->stSize)
1.228 - {
1.229 - trie->stSize *= 2;
1.230 - }
1.231 - trie->stringtab = (char *)realloc(trie->stringtab, trie->stSize);
1.232 - }
1.233 -
1.234 - unsigned int tail = trie->tail;
1.235 - strcpy(&trie->stringtab[tail], ptr);
1.236 - trie->tail += len;
1.237 -
1.238 - return tail;
1.239 -}
1.240 -
1.241 Trie *sm_trie_create()
1.242 {
1.243 - Trie *t = new Trie;
1.244 -
1.245 - t->base = (TrieNode *)malloc(sizeof(TrieNode) * (256 + 1));
1.246 - t->stringtab = (char *)malloc(sizeof(char) * 256);
1.247 - t->baseSize = 256;
1.248 - t->stSize = 256;
1.249 -
1.250 - sm_trie_clear(t);
1.251 -
1.252 - return t;
1.253 -}
1.254 -
1.255 -void sm_trie_clear(Trie *trie)
1.256 -{
1.257 - trie->tail = 0;
1.258 -
1.259 - memset(trie->base, 0, sizeof(TrieNode) * (trie->baseSize + 1));
1.260 - memset(trie->stringtab, 0, sizeof(char) * trie->stSize);
1.261 -
1.262 - /* Sentinel root node */
1.263 - trie->base[1].idx = 1;
1.264 - trie->base[1].mode = Node_Arc;
1.265 - trie->base[1].parent = 1;
1.266 + return new Trie;
1.267 }
1.268
1.269 void sm_trie_destroy(Trie *trie)
1.270 {
1.271 - free(trie->base);
1.272 - free(trie->stringtab);
1.273 delete trie;
1.274 }
1.275
1.276 -TrieNode *sm_trie_internal_retrieve(Trie *trie, const char *key)
1.277 +bool sm_trie_insert(Trie *trie, const char *key, void *value)
1.278 {
1.279 - unsigned int lastidx = 1; /* the last node index */
1.280 - unsigned int curidx; /* current node index */
1.281 - const char *keyptr = key; /* input stream at current token */
1.282 - TrieNode *node = NULL; /* current node being processed */
1.283 - TrieNode *base = trie->base;
1.284 -
1.285 - if (!*key)
1.286 - {
1.287 - return NULL;
1.288 - }
1.289 -
1.290 - /* Start traversing at the root node */
1.291 - do
1.292 - {
1.293 - /* Find where the next character is, then advance */
1.294 - curidx = base[lastidx].idx;
1.295 - node = &base[curidx];
1.296 - curidx += charval(*keyptr);
1.297 - node = &base[curidx];
1.298 - keyptr++;
1.299 -
1.300 - /* Check if this slot is supposed to be empty or is a collision */
1.301 - if ((curidx > trie->baseSize) || node->mode == Node_Unused || node->parent != lastidx)
1.302 - {
1.303 - return NULL;
1.304 - } else if (node->mode == Node_Term) {
1.305 - char *term = &trie->stringtab[node->idx];
1.306 - if (strcmp(keyptr, term) == 0)
1.307 - {
1.308 - break;
1.309 - }
1.310 - }
1.311 - lastidx = curidx;
1.312 - } while (*keyptr != '\0');
1.313 -
1.314 - return node;
1.315 + return trie->k.insert(key, value);
1.316 }
1.317
1.318 -bool sm_trie_delete(Trie *trie, const char *key)
1.319 +bool sm_trie_replace(Trie *trie, const char *key, void *value)
1.320 {
1.321 - TrieNode *node = sm_trie_internal_retrieve(trie, key);
1.322 - if (!node || !node->valset)
1.323 - {
1.324 - return false;
1.325 - }
1.326 -
1.327 - node->value = NULL;
1.328 - node->valset = false;
1.329 -
1.330 - return true;
1.331 + return trie->k.replace(key, value);
1.332 }
1.333
1.334 bool sm_trie_retrieve(Trie *trie, const char *key, void **value)
1.335 {
1.336 - TrieNode *node = sm_trie_internal_retrieve(trie, key);
1.337 - if (!node || !node->valset)
1.338 + void **pValue = trie->k.retrieve(key);
1.339 +
1.340 + if (!pValue)
1.341 {
1.342 return false;
1.343 }
1.344
1.345 if (value)
1.346 {
1.347 - *value = node->value;
1.348 + *value = *pValue;
1.349 }
1.350
1.351 return true;
1.352 }
1.353
1.354 -bool sm_trie_insert(Trie *trie, const char *key, void *value)
1.355 +bool sm_trie_delete(Trie *trie, const char *key)
1.356 {
1.357 - unsigned int lastidx = 1; /* the last node index */
1.358 - unsigned int curidx; /* current node index */
1.359 - const char *keyptr = key; /* input stream at current token */
1.360 - TrieNode *node = NULL; /* current node being processed */
1.361 - TrieNode *basenode = NULL; /* current base node being processed */
1.362 - unsigned int q; /* temporary var for x_check results */
1.363 - TrieNode *base = trie->base;
1.364 - unsigned int curoffs; /* current offset */
1.365 -
1.366 - /* Do not handle empty strings for simplicity */
1.367 - if (!*key)
1.368 - {
1.369 - return false;
1.370 - }
1.371 -
1.372 - /* Start traversing at the root node (1) */
1.373 - do
1.374 - {
1.375 - /* Find where the next character is, then advance */
1.376 - curidx = base[lastidx].idx;
1.377 - basenode = &base[curidx];
1.378 - curoffs = charval(*keyptr);
1.379 - curidx += curoffs;
1.380 - node = &base[curidx];
1.381 - keyptr++;
1.382 -
1.383 - /* Check if this slot is supposed to be empty. If so, we need to handle CASES 1/2:
1.384 - * Insertion without collisions
1.385 - */
1.386 - if ( (curidx > trie->baseSize) || (node->mode == Node_Unused) )
1.387 - {
1.388 - if (curidx > trie->baseSize)
1.389 - {
1.390 - if (!sm_trie_grow(trie))
1.391 - {
1.392 - return false;
1.393 - }
1.394 - node = &trie->base[curidx];
1.395 - }
1.396 - node->parent = lastidx;
1.397 - if (*keyptr == '\0')
1.398 - {
1.399 - node->mode = Node_Arc;
1.400 - } else {
1.401 - node->idx = x_addstring(trie, keyptr);
1.402 - node->mode = Node_Term;
1.403 - }
1.404 - node->valset = true;
1.405 - node->value = value;
1.406 -
1.407 - return true;
1.408 - } else if (node->parent != lastidx) {
1.409 - /* Collision! We have to split up the tree here. CASE 4:
1.410 - * Insertion when a new word is inserted with a collision.
1.411 - * NOTE: This is the hardest case to handle. All below examples are based on:
1.412 - * BACHELOR, BADGE, inserting BABY.
1.413 - * The problematic production here is A -> B, where B is already being used.
1.414 - *
1.415 - * This process has to rotate one half of the 'A' arc. We generate two lists:
1.416 - * Outgoing Arcs - Anything leaving this 'A'
1.417 - * Incoming Arcs - Anything going to this 'A'
1.418 - * Whichever list is smaller will be moved. Note that this works because the intersection
1.419 - * affects both arc chains, and moving one will make the slot available to either.
1.420 - */
1.421 - TrieNode *cur;
1.422 -
1.423 - /* Find every node arcing from the last node.
1.424 - * I.e. for BACHELOR, BADGE, BABY,
1.425 - * The arcs leaving A will be C and D, but our current node is B -> *.
1.426 - * Thus, we use the last index (A) to find the base for arcs leaving A.
1.427 - */
1.428 - unsigned int outgoing_base = base[lastidx].idx;
1.429 - unsigned int outgoing_list[256];
1.430 - unsigned int outgoing_count = 0; /* count the current index here */
1.431 - cur = &base[outgoing_base] + 1;
1.432 - unsigned int outgoing_limit = 255;
1.433 -
1.434 - if (outgoing_base + outgoing_limit > trie->baseSize)
1.435 - {
1.436 - outgoing_limit = trie->baseSize - outgoing_base;
1.437 - }
1.438 -
1.439 - for (unsigned int i=1; i<=outgoing_limit; i++,cur++)
1.440 - {
1.441 - if (cur->mode == Node_Unused || cur->parent != lastidx)
1.442 - {
1.443 - continue;
1.444 - }
1.445 - outgoing_list[outgoing_count++] = i;
1.446 - }
1.447 - outgoing_list[outgoing_count++] = curidx - outgoing_base;
1.448 -
1.449 - /* Now we need to find all the arcs leaving our parent...
1.450 - * Note: the inconsistency is the base of our parent.
1.451 - */
1.452 - assert(base[node->parent].mode == Node_Arc);
1.453 - unsigned int incoming_list[256];
1.454 - unsigned int incoming_base = base[node->parent].idx;
1.455 - unsigned int incoming_count = 0;
1.456 - unsigned int incoming_limit = 255;
1.457 - cur = &base[incoming_base] + 1;
1.458 -
1.459 - if (incoming_base + incoming_limit > trie->baseSize)
1.460 - {
1.461 - incoming_limit = trie->baseSize - incoming_base;
1.462 - }
1.463 -
1.464 - assert(incoming_limit > 0 && incoming_limit <= 255);
1.465 -
1.466 - for (unsigned int i=1; i<=incoming_limit; i++,cur++)
1.467 - {
1.468 - if (cur->mode == Node_Arc || cur->mode == Node_Term)
1.469 - {
1.470 - if (cur->parent == node->parent)
1.471 - {
1.472 - incoming_list[incoming_count++] = i;
1.473 - }
1.474 - }
1.475 - }
1.476 -
1.477 - if (incoming_count < outgoing_count + 1)
1.478 - {
1.479 - unsigned int q = x_check_multi(trie, incoming_list, incoming_count);
1.480 -
1.481 - base = trie->base;
1.482 - node = &base[curidx];
1.483 -
1.484 - /* If we're incoming, we need to modify our parent */
1.485 - base[node->parent].idx = q;
1.486 -
1.487 - /* For each node in the "to move" list,
1.488 - * Relocate the node's info to the new position.
1.489 - */
1.490 - unsigned int idx, newidx, oldidx;
1.491 - for (unsigned int i=0; i<incoming_count; i++)
1.492 - {
1.493 - idx = incoming_list[i];
1.494 - newidx = q + idx;
1.495 - oldidx = incoming_base + idx;
1.496 - if (oldidx == lastidx)
1.497 - {
1.498 - /* Important! Make sure we're not invalidating our sacred lastidx */
1.499 - lastidx = newidx;
1.500 - }
1.501 - base[newidx] = base[oldidx];
1.502 - assert(base[base[newidx].parent].mode == Node_Arc);
1.503 - memset(&base[oldidx], 0, sizeof(TrieNode));
1.504 - /* If we are not a terminator, we have children we must take care of */
1.505 - if (base[newidx].mode == Node_Arc)
1.506 - {
1.507 - TrieNode *check_base = &base[base[newidx].idx] + 1;
1.508 - outgoing_limit = (base + trie->baseSize + 1) - check_base;
1.509 - if (outgoing_limit > 255)
1.510 - {
1.511 - outgoing_limit = 255;
1.512 - }
1.513 - for (unsigned int j=1; j<=outgoing_limit; j++, check_base++)
1.514 - {
1.515 - if (check_base->parent == oldidx)
1.516 - {
1.517 - check_base->parent = newidx;
1.518 - }
1.519 - }
1.520 - }
1.521 - }
1.522 - } else {
1.523 - unsigned int q = x_check_multi(trie, outgoing_list, outgoing_count);
1.524 -
1.525 - base = trie->base;
1.526 - node = &base[curidx];
1.527 -
1.528 - /* If we're outgoing, we need to modify our own base */
1.529 - base[lastidx].idx = q;
1.530 -
1.531 - /* Take the last index (curidx) out of the list. Technically we are not moving this,
1.532 - * since it's already being used by something else.
1.533 - */
1.534 - outgoing_count--;
1.535 -
1.536 - /* For each node in the "to move" list,
1.537 - * Relocate the node's info to the new position.
1.538 - */
1.539 - unsigned int idx, newidx, oldidx;
1.540 - for (unsigned int i=0; i<outgoing_count; i++)
1.541 - {
1.542 - idx = outgoing_list[i];
1.543 - newidx = q + idx;
1.544 - oldidx = outgoing_base + idx;
1.545 - if (oldidx == lastidx)
1.546 - {
1.547 - /* Important! Make sure we're not invalidating our sacred lastidx */
1.548 - lastidx = newidx;
1.549 - }
1.550 - base[newidx] = base[oldidx];
1.551 - assert(base[base[newidx].parent].mode == Node_Arc);
1.552 - memset(&base[oldidx], 0, sizeof(TrieNode));
1.553 - /* If we are not a terminator, we have children we must take care of */
1.554 - if (base[newidx].mode == Node_Arc)
1.555 - {
1.556 - TrieNode *check_base = &base[base[newidx].idx] + 1;
1.557 - outgoing_limit = (base + trie->baseSize + 1) - check_base;
1.558 - if (outgoing_limit > 255)
1.559 - {
1.560 - outgoing_limit = 255;
1.561 - }
1.562 - for (unsigned int j=1; j<=outgoing_limit; j++, check_base++)
1.563 - {
1.564 - if (check_base->parent == oldidx)
1.565 - {
1.566 - check_base->parent = newidx;
1.567 - }
1.568 - }
1.569 - }
1.570 - }
1.571 -
1.572 - /* Take the invisible node and use it as our new node */
1.573 - node = &base[q + outgoing_list[outgoing_count]];
1.574 - }
1.575 -
1.576 - /* We're finally done! */
1.577 - node->parent = lastidx;
1.578 - if (*keyptr == '\0')
1.579 - {
1.580 - node->mode = Node_Arc;
1.581 - } else {
1.582 - node->idx = x_addstring(trie, keyptr);
1.583 - node->mode = Node_Term;
1.584 - }
1.585 - node->valset = true;
1.586 - node->value = value;
1.587 -
1.588 - return true;
1.589 - } else {
1.590 - /* See what's in the next node - special case if terminator! */
1.591 - if (node->mode == Node_Term)
1.592 - {
1.593 - /* If we're a terminator, we need to handle CASE 3:
1.594 - * Insertion when a terminating collision occurs
1.595 - */
1.596 - char *term = &trie->stringtab[node->idx];
1.597 - /* Do an initial browsing to make sure they're not the same string */
1.598 - if (strcmp(keyptr, term) == 0)
1.599 - {
1.600 - if (!node->valset)
1.601 - {
1.602 - node->valset = true;
1.603 - node->value = value;
1.604 - return true;
1.605 - }
1.606 - /* Same string. We can't insert. */
1.607 - return false;
1.608 - }
1.609 - /* For each matching character pair, we need to disband the terminator.
1.610 - * This splits the similar prefix into a single arc path.
1.611 - * First, save the old values so we can move them to a new node.
1.612 - * Next, for each loop:
1.613 - * Take the current (invalid) node, and point it to the next arc base.
1.614 - * Set the current node to the node at the next arc.
1.615 - */
1.616 - void *oldvalue = node->value;
1.617 - bool oldvalset = node->valset;
1.618 - if (*term == *keyptr)
1.619 - {
1.620 - while (*term == *keyptr)
1.621 - {
1.622 - /* Find the next free slot in the check array.
1.623 - * This is the "vector base" essentially
1.624 - */
1.625 - q = x_check(trie, *term);
1.626 - base = trie->base;
1.627 - node = &base[curidx];
1.628 - /* Point the node to the next new base */
1.629 - node->idx = q;
1.630 - node->mode = Node_Arc;
1.631 - node->valset = false;
1.632 - /* Advance the input stream and local variables */
1.633 - lastidx = curidx;
1.634 - curidx = q + charval(*term);
1.635 - node = &base[curidx];
1.636 - /* Make sure the new current node has its parent set. */
1.637 - node->parent = lastidx;
1.638 - node->mode = Node_Arc; /* Just in case we run x_check again */
1.639 - *term = '\0'; /* Unmark the string table here */
1.640 - term++;
1.641 - keyptr++;
1.642 - }
1.643 - } else {
1.644 - node->valset = false;
1.645 - }
1.646 - /* We're done inserting new pairs. If one of them is exhausted,
1.647 - * we take special shortcuts.
1.648 - */
1.649 - if (*term == '\0') //EX: BADGERHOUSE added over B -> ADGER.
1.650 - {
1.651 - /* First backpatch the current node - it ends the newly split terminator.
1.652 - * In the example, this would mean the node is the production from R -> ?
1.653 - * This node ends the old BADGER, so we set it here.
1.654 - */
1.655 - node->valset = oldvalset;
1.656 - node->value = oldvalue;
1.657 -
1.658 - /* The terminator was split up, but pieces of keyptr remain.
1.659 - * We need to generate a new production, in this example, R -> H,
1.660 - * with H being a terminator to OUSE. Thus we get:
1.661 - * B,A,D,G,E,R*,H*->OUSE (* = value set).
1.662 - * NOTE: parent was last set at the end of the while loop.
1.663 - */
1.664 - /* Get the new base and apply re-basing */
1.665 - q = x_check(trie, *keyptr);
1.666 - base = trie->base;
1.667 - node = &base[curidx];
1.668 -
1.669 - node->idx = q;
1.670 - node->mode = Node_Arc;
1.671 - lastidx = curidx;
1.672 - /* Finish the final node */
1.673 - curidx = q + charval(*keyptr);
1.674 - node = &trie->base[curidx];
1.675 - keyptr++;
1.676 - /* Optimize - don't add to string table if there's nothing more to eat */
1.677 - if (*keyptr == '\0')
1.678 - {
1.679 - node->mode = Node_Arc;
1.680 - } else {
1.681 - node->idx = x_addstring(trie, keyptr);
1.682 - node->mode = Node_Term;
1.683 - }
1.684 - node->parent = lastidx;
1.685 - node->valset = true;
1.686 - node->value = value;
1.687 - } else if (*keyptr == '\0') { //EX: BADGER added over B -> ADGERHOUSE
1.688 - /* First backpatch the current node - it ends newly split input string.
1.689 - * This is the exact opposite of the above procedure.
1.690 - */
1.691 - node->valset = true;
1.692 - node->value = value;
1.693 -
1.694 - /* Get the new base and apply re-basing */
1.695 - q = x_check(trie, *term);
1.696 - base = trie->base;
1.697 - node = &base[curidx];
1.698 -
1.699 - node->idx = q;
1.700 - node->mode = Node_Arc;
1.701 - lastidx = curidx;
1.702 - /* Finish the final node */
1.703 - curidx = q + charval(*term);
1.704 - node = &trie->base[curidx];
1.705 - term++;
1.706 - /* Optimize - don't add to string table if there's nothing more to eat */
1.707 - if (*term == '\0')
1.708 - {
1.709 - node->mode = Node_Arc;
1.710 - } else {
1.711 - node->idx = (term - trie->stringtab); /* Already in the string table! */
1.712 - node->mode = Node_Term;
1.713 - }
1.714 - node->parent = lastidx;
1.715 - node->valset = oldvalset;
1.716 - node->value = oldvalue;
1.717 - } else {
1.718 - /* Finally, we have to create two new nodes instead of just one. */
1.719 - node->mode = Node_Arc;
1.720 -
1.721 - /* Get the new base and apply re-basing */
1.722 - q = x_check2(trie, *keyptr, *term);
1.723 - base = trie->base;
1.724 - node = &base[curidx];
1.725 -
1.726 - node->idx = q;
1.727 - lastidx = curidx;
1.728 -
1.729 - /* Re-create the old terminated node */
1.730 - curidx = q + charval(*term);
1.731 - node = &trie->base[curidx];
1.732 - term++;
1.733 - node->valset = oldvalset;
1.734 - node->value = oldvalue;
1.735 - node->parent = lastidx;
1.736 - if (*term == '\0')
1.737 - {
1.738 - node->mode = Node_Arc;
1.739 - } else {
1.740 - node->mode = Node_Term;
1.741 - node->idx = (term - trie->stringtab); /* Already in the string table! */
1.742 - }
1.743 -
1.744 - /* Create the new keyed input node */
1.745 - curidx = q + charval(*keyptr);
1.746 - node = &trie->base[curidx];
1.747 - keyptr++;
1.748 - node->valset = true;
1.749 - node->value = value;
1.750 - node->parent = lastidx;
1.751 - if (*keyptr == '\0')
1.752 - {
1.753 - node->mode = Node_Arc;
1.754 - } else {
1.755 - node->mode = Node_Term;
1.756 - node->idx = x_addstring(trie, keyptr);
1.757 - }
1.758 - }
1.759 -
1.760 - /* Phew! */
1.761 - return true;
1.762 - } else {
1.763 - assert(node->mode == Node_Arc);
1.764 - }
1.765 - }
1.766 - lastidx = curidx;
1.767 - } while (*keyptr != '\0');
1.768 -
1.769 - assert(node);
1.770 -
1.771 - /* If we've exhausted the string and we have a valid reached node,
1.772 - * the production rule already existed. Make sure it's valid to set first.
1.773 - */
1.774 -
1.775 - /* We have to be an Arc. If the last result was anything else, we would have returned a new
1.776 - * production earlier.
1.777 - */
1.778 - assert(node->mode == Node_Arc);
1.779 -
1.780 - if (!node->valset)
1.781 - {
1.782 - /* Insert is only possible if we have no production */
1.783 - node->valset = true;
1.784 - node->value = value;
1.785 - return true;
1.786 - }
1.787 -
1.788 - return false;
1.789 + return trie->k.remove(key);
1.790 }
1.791
1.792 -bool sm_trie_replace(Trie *trie, const char *key, void *value)
1.793 +void sm_trie_clear(Trie *trie)
1.794 {
1.795 - TrieNode *node = sm_trie_internal_retrieve(trie, key);
1.796 - if (!node)
1.797 - {
1.798 - return sm_trie_insert(trie, key, value);
1.799 - }
1.800 -
1.801 - node->value = value;
1.802 - node->valset = true;
1.803 -
1.804 - return true;
1.805 + trie->k.clear();
1.806 }
