sm_trie.cpp
changeset 0 67dcd379a2d5
     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 +}