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