sm_trie.cpp
author David Anderson <dvander@alliedmods.net>
Mon Jun 25 23:30:11 2007 +0000 (2007-06-25)
changeset 8 fdcccf33a7cf
parent 0 67dcd379a2d5
permissions -rw-r--r--
fixed translation file not being loaded
     1 /**
     2  * vim: set ts=4 :
     3  * ===============================================================
     4  * CS:S DM, Copyright (C) 2004-2007 AlliedModders LLC. 
     5  * By David "BAILOPAN" Anderson
     6  * All rights reserved.
     7  * ===============================================================
     8  *
     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.
    13  * 
    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.
    18  * 
    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,
    22  * MA 02110-1301 USA
    23  * 
    24  * Version: $Id$
    25  */
    26 
    27 
    28 #include <string.h>
    29 #include <stdlib.h>
    30 #include <assert.h>
    31 #include "sm_trie.h"
    32 
    33 /**
    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)
    38  *
    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:
    41  *
    42  * BAILOPAN, BAT, BACON, BACK
    43  *  These transition as the follow production rules:
    44  *  B -> ...                  B
    45  *       A -> ...             BA
    46  *            I -> ...        BAI
    47  *                 LOPAN      BAILOPAN
    48  *            T -> ...        BAT
    49  *            C ->            BAC
    50  *                 O -> ...   BACO
    51  *                      N     BACON
    52  *                 K          BACK
    53  *
    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.
    60  *
    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)
    72  * 
    73  *  So, given current offset N (starting at N=1), jumping to token C means the next offset will be:
    74  *      offs = BASE[n] + C
    75  *  Thus, the next node will be at:
    76  *      BASE[BASE[n] + C]
    77  * 
    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 
    80  * string exists.
    81  *
    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.
    87  *
    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).
    92  *
    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).
    96  */
    97 
    98 /**
    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*
   104  */
   105 
   106 enum NodeType
   107 {
   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 */
   111 };
   112 
   113 struct TrieNode
   114 {
   115 	/**
   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.
   119 	 */
   120 	unsigned int idx;
   121 
   122 	/**
   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.
   126 	 */
   127 	unsigned int parent;
   128 
   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 */
   132 };
   133 
   134 struct Trie
   135 {
   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 */
   141 };
   142 
   143 inline unsigned char charval(char c)
   144 {
   145 	return (unsigned char)c;
   146 }
   147 
   148 bool sm_trie_grow(Trie *trie)
   149 {
   150 	/* The current # of nodes in the tree is trie->baseSize + 1 */
   151 	unsigned int curSize = trie->baseSize;
   152 	unsigned int newSize = curSize * 2;
   153 
   154 	//:TODO: Make functions calling this return failure if this fails 
   155 	trie->base = (TrieNode *)realloc(trie->base, (newSize + 1) * sizeof(TrieNode));
   156 	if (!trie->base)
   157 	{
   158 		return false;
   159 	}
   160 
   161 	memset(&trie->base[curSize+1], 0, (newSize - curSize) * sizeof(TrieNode));
   162 	trie->baseSize = newSize;
   163 
   164 	return true;
   165 }
   166 
   167 unsigned int x_check(Trie *trie, char c, unsigned int start=1)
   168 {
   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++)
   173 	{
   174 		if (base[i+_c].mode == Node_Unused)
   175 		{
   176 			return i;
   177 		}
   178 	}
   179 
   180 	sm_trie_grow(trie);
   181 
   182 	return x_check(trie, c, to_check+1);
   183 }
   184 
   185 unsigned int x_check2(Trie *trie, char c1, char c2, unsigned int start=1)
   186 {
   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++)
   192 	{
   193 		if (base[i+_c1].mode == Node_Unused
   194 			&& base[i+_c2].mode == Node_Unused)
   195 		{
   196 			return i;
   197 		}
   198 	}
   199 
   200 	sm_trie_grow(trie);
   201 
   202 	return x_check2(trie, c1, c2, to_check+1);
   203 }
   204 
   205 unsigned int x_check_multi(Trie *trie, 
   206 							unsigned int offsets[], 
   207 							unsigned int count,
   208 							unsigned int start=1)
   209 {
   210 	TrieNode *base = trie->base;
   211 	TrieNode *cur;
   212 	unsigned int to_check = trie->baseSize;
   213 	unsigned int highest = 0;
   214 
   215 	for (unsigned int i=0; i<count; i++)
   216 	{
   217 		if (offsets[i] > highest)
   218 		{
   219 			highest = offsets[i];
   220 		}
   221 	}
   222 
   223 	to_check -= highest;
   224 
   225 	for (unsigned int i=start; i<=to_check; i++)
   226 	{
   227 		bool okay = true;
   228 		for (unsigned int j=0; j<count; j++)
   229 		{
   230 			cur = &base[i+offsets[j]];
   231 			if (cur->mode != Node_Unused)
   232 			{
   233 				okay = false;
   234 				break;
   235 			}
   236 		}
   237 		if (okay)
   238 		{
   239 			return i;
   240 		}
   241 	}
   242 
   243 	sm_trie_grow(trie);
   244 
   245 	return x_check_multi(trie, offsets, count, to_check+1);
   246 }
   247 
   248 unsigned int x_addstring(Trie *trie, const char *ptr)
   249 {
   250 	size_t len = strlen(ptr) + 1;
   251 
   252 	if (trie->tail + len >= trie->stSize)
   253 	{		
   254 		while (trie->tail + len >= trie->stSize)
   255 		{
   256 			trie->stSize *= 2;
   257 		}
   258 		trie->stringtab = (char *)realloc(trie->stringtab, trie->stSize);
   259 	}
   260 
   261 	unsigned int tail = trie->tail;
   262 	strcpy(&trie->stringtab[tail], ptr);
   263 	trie->tail += len;
   264 
   265 	return tail;
   266 }
   267 
   268 Trie *sm_trie_create()
   269 {
   270 	Trie *t = new Trie;
   271 
   272 	t->base = (TrieNode *)malloc(sizeof(TrieNode) * (256 + 1));
   273 	t->stringtab = (char *)malloc(sizeof(char) * 256);
   274 	t->baseSize = 256;
   275 	t->stSize = 256;
   276 
   277 	sm_trie_clear(t);
   278 
   279 	return t;
   280 }
   281 
   282 void sm_trie_clear(Trie *trie)
   283 {
   284 	trie->tail = 0;
   285 
   286 	memset(trie->base, 0, sizeof(TrieNode) * (trie->baseSize + 1));
   287 	memset(trie->stringtab, 0, sizeof(char) * trie->stSize);
   288 
   289 	/* Sentinel root node */
   290 	trie->base[1].idx = 1;
   291 	trie->base[1].mode = Node_Arc;
   292 	trie->base[1].parent = 1;
   293 }
   294 
   295 void sm_trie_destroy(Trie *trie)
   296 {
   297 	free(trie->base);
   298 	free(trie->stringtab);
   299 	delete trie;
   300 }
   301 
   302 bool sm_trie_delete(Trie *trie, const char *key)
   303 {
   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;
   309 
   310 	if (!*key)
   311 	{
   312 		return false;
   313 	}
   314 
   315 	/* Start traversing at the root node */
   316 	do
   317 	{
   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];
   323 		keyptr++;
   324 
   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)
   327 		{
   328 			return false;
   329 		} else if (node->mode == Node_Term) {
   330 			char *term = &trie->stringtab[node->idx];
   331 			if (strcmp(keyptr, term) == 0)
   332 			{
   333 				break;
   334 			}
   335 		}
   336 		lastidx = curidx;
   337 	} while (*keyptr != '\0');
   338 
   339 	assert(node != NULL);
   340 
   341 	if (!node->valset)
   342 	{
   343 		return false;
   344 	}
   345 
   346 	node->valset = false;
   347 	node->value = NULL;
   348 
   349 	return true;
   350 }
   351 
   352 bool sm_trie_retrieve(Trie *trie, const char *key, void **value)
   353 {
   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;
   359 
   360 	if (!*key)
   361 	{
   362 		return false;
   363 	}
   364 
   365 	/* Start traversing at the root node */
   366 	do
   367 	{
   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];
   373 		keyptr++;
   374 
   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)
   377 		{
   378 			return false;
   379 		} else if (node->mode == Node_Term) {
   380 			char *term = &trie->stringtab[node->idx];
   381 			if (strcmp(keyptr, term) == 0)
   382 			{
   383 				break;
   384 			}
   385 		}
   386 		lastidx = curidx;
   387 	} while (*keyptr != '\0');
   388 
   389 	assert(node != NULL);
   390 
   391 	if (!node->valset)
   392 	{
   393 		return false;
   394 	}
   395 
   396 	if (value)
   397 	{
   398 		*value = node->value;
   399 	}
   400 
   401 	return true;
   402 }
   403 
   404 bool sm_trie_insert(Trie *trie, const char *key, void *value)
   405 {
   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 */
   414 
   415 	/* Do not handle empty strings for simplicity */
   416 	if (!*key)
   417 	{
   418 		return false;
   419 	}
   420 
   421 	/* Start traversing at the root node (1) */
   422 	do
   423 	{
   424 		/* Find where the next character is, then advance */
   425 		curidx = base[lastidx].idx;
   426 		basenode = &base[curidx];
   427 		curoffs = charval(*keyptr);
   428 		curidx += curoffs;
   429 		node = &base[curidx];
   430 		keyptr++;
   431 
   432 		/* Check if this slot is supposed to be empty.  If so, we need to handle CASES 1/2:
   433 		 * Insertion without collisions
   434 		 */
   435 		if ( (curidx > trie->baseSize) || (node->mode == Node_Unused) )
   436 		{
   437 			if (curidx > trie->baseSize)
   438 			{
   439 				if (!sm_trie_grow(trie))
   440 				{
   441 					return false;
   442 				}
   443 				node = &trie->base[curidx];
   444 			}
   445 			node->parent = lastidx;
   446 			if (*keyptr == '\0')
   447 			{
   448 				node->mode = Node_Arc;
   449 			} else {
   450 				node->idx = x_addstring(trie, keyptr);
   451 				node->mode = Node_Term;
   452 			}
   453 			node->valset = true;
   454 			node->value = value;
   455 			
   456 			return true;
   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.
   463 			 *
   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.
   469 			 */
   470 			TrieNode *cur;
   471 			
   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.
   476 			 */
   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;
   482 
   483 			if (outgoing_base + outgoing_limit > trie->baseSize)
   484 			{
   485 				outgoing_limit = trie->baseSize - outgoing_base;
   486 			}
   487 
   488 			for (unsigned int i=1; i<=outgoing_limit; i++,cur++)
   489 			{
   490 				if (cur->mode == Node_Unused || cur->parent != lastidx)
   491 				{
   492 					continue;
   493 				}
   494 				outgoing_list[outgoing_count++] = i;
   495 			}
   496 			outgoing_list[outgoing_count++] = curidx - outgoing_base;
   497 
   498 			/* Now we need to find all the arcs leaving our parent...
   499 			 * Note: the inconsistency is the base of our parent.  
   500 			 */
   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;
   507 
   508 			if (incoming_base + incoming_limit > trie->baseSize)
   509 			{
   510 				incoming_limit = trie->baseSize - incoming_base;
   511 			}
   512 
   513 			assert(incoming_limit > 0 && incoming_limit <= 255);
   514 
   515 			for (unsigned int i=1; i<=255; i++,cur++)
   516 			{
   517 				if (cur->mode == Node_Arc || cur->mode == Node_Term)
   518 				{
   519 					if (cur->parent == node->parent)
   520 					{
   521 						incoming_list[incoming_count++] = i;
   522 					}
   523 				}
   524 			}
   525 
   526 			if (incoming_count < outgoing_count + 1)
   527 			{
   528 				unsigned int q = x_check_multi(trie, incoming_list, incoming_count);
   529 
   530 				base = trie->base;
   531 				node = &base[curidx];
   532 
   533 				/* If we're incoming, we need to modify our parent */
   534 				base[node->parent].idx = q;
   535 
   536 				/* For each node in the "to move" list,
   537 				 * Relocate the node's info to the new position.
   538 				 */
   539 				unsigned int idx, newidx, oldidx;
   540 				for (unsigned int i=0; i<incoming_count; i++)
   541 				{
   542 					idx = incoming_list[i];
   543 					newidx = q + idx;
   544 					oldidx = incoming_base + idx;
   545 					if (oldidx == lastidx)
   546 					{
   547 						/* Important! Make sure we're not invalidating our sacred lastidx */
   548 						lastidx = newidx;
   549 					}
   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)
   555 					{
   556 						TrieNode *check_base = &base[base[newidx].idx] + 1;
   557 						for (unsigned int j=1; j<=255; j++, check_base++)
   558 						{
   559 							if (check_base->parent == oldidx)
   560 							{
   561 								check_base->parent = newidx;
   562 							}
   563 						}
   564 					}
   565 				}
   566 			} else {
   567 				unsigned int q = x_check_multi(trie, outgoing_list, outgoing_count);
   568 
   569 				base = trie->base;
   570 				node = &base[curidx];
   571 
   572 				/* If we're outgoing, we need to modify our own base */
   573 				base[lastidx].idx = q;
   574 
   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.  
   577 				 */
   578 				outgoing_count--;
   579 
   580 				/* For each node in the "to move" list,
   581 				 * Relocate the node's info to the new position.
   582 				 */
   583 				unsigned int idx, newidx, oldidx;
   584 				for (unsigned int i=0; i<outgoing_count; i++)
   585 				{
   586 					idx = outgoing_list[i];
   587 					newidx = q + idx;
   588 					oldidx = outgoing_base + idx;
   589 					if (oldidx == lastidx)
   590 					{
   591 						/* Important! Make sure we're not invalidating our sacred lastidx */
   592 						lastidx = newidx;
   593 					}
   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)
   599 					{
   600 						TrieNode *check_base = &base[base[newidx].idx] + 1;
   601 						for (unsigned int j=1; j<=255; j++, check_base++)
   602 						{
   603 							if (check_base->parent == oldidx)
   604 							{
   605 								check_base->parent = newidx;
   606 							}
   607 						}
   608 					}
   609 				}
   610 
   611 				/* Take the invisible node and use it as our new node */
   612 				node = &base[q + outgoing_list[outgoing_count]];
   613 			}
   614 
   615 			/* We're finally done! */
   616 			node->parent = lastidx;
   617 			if (*keyptr == '\0')
   618 			{
   619 				node->mode = Node_Arc;
   620 			} else {
   621 				node->idx = x_addstring(trie, keyptr);
   622 				node->mode = Node_Term;
   623 			}
   624 			node->valset = true;
   625 			node->value = value;
   626 
   627 			return true;
   628 		} else {
   629 			/* See what's in the next node - special case if terminator! */
   630 			if (node->mode == Node_Term)
   631 			{
   632 				/* If we're a terminator, we need to handle CASE 3:
   633 				 * Insertion when a terminating collision occurs
   634 				 */
   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)
   638 				{
   639 					if (!node->valset)
   640 					{
   641 						node->valset = true;
   642 						node->value = value;
   643 						return true;
   644 					}
   645 					/* Same string.  We can't insert. */
   646 					return false;
   647 				}
   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.
   654 				 */
   655 				void *oldvalue = node->value;
   656 				bool oldvalset = node->valset;
   657 				if (*term == *keyptr)
   658 				{
   659 				while (*term == *keyptr)
   660 				{
   661 					/* Find the next free slot in the check array.
   662 					 * This is the "vector base" essentially
   663 					 */
   664 					q = x_check(trie, *term);
   665 						base = trie->base;
   666 						node = &base[curidx];
   667 					/* Point the node to the next new base */
   668 					node->idx = q;
   669 					node->mode = Node_Arc;
   670 					node->valset = false;
   671 					/* Advance the input stream and local variables */
   672 					lastidx = curidx;
   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 */
   679 					term++;
   680 					keyptr++;
   681 					}
   682 				} else {
   683 					node->valset = false;
   684 				}
   685 				/* We're done inserting new pairs.  If one of them is exhausted,
   686 				 * we take special shortcuts.
   687 				 */
   688 				if (*term == '\0')				//EX: BADGERHOUSE added over B -> ADGER.  
   689 				{
   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.
   693 					 */
   694 					node->valset = oldvalset;
   695 					node->value = oldvalue;
   696 
   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.
   702 					 */
   703 					/* Get the new base and apply re-basing */
   704 					q = x_check(trie, *keyptr);
   705 					base = trie->base;
   706 					node = &base[curidx];
   707 
   708 					node->idx = q;
   709 					node->mode = Node_Arc;
   710 					lastidx = curidx;
   711 					/* Finish the final node */
   712 					curidx = q + charval(*keyptr);
   713 					node = &trie->base[curidx];
   714 					keyptr++;
   715 					/* Optimize - don't add to string table if there's nothing more to eat */
   716 					if (*keyptr == '\0')
   717 					{
   718 						node->mode = Node_Arc;
   719 					} else {
   720 						node->idx = x_addstring(trie, keyptr);
   721 						node->mode = Node_Term;
   722 					}
   723 					node->parent = lastidx;
   724 					node->valset = true;
   725 					node->value = value;
   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.
   729 					 */
   730 					node->valset = true;
   731 					node->value = value;
   732 
   733 					/* Get the new base and apply re-basing */
   734 					q = x_check(trie, *term);
   735 					base = trie->base;
   736 					node = &base[curidx];
   737 
   738 					node->idx = q;
   739 					node->mode = Node_Arc;
   740 					lastidx = curidx;
   741 					/* Finish the final node */
   742 					curidx = q + charval(*term);
   743 					node = &trie->base[curidx];
   744 					term++;
   745 					/* Optimize - don't add to string table if there's nothing more to eat */
   746 					if (*term == '\0')
   747 					{
   748 						node->mode = Node_Arc;
   749 					} else {
   750 						node->idx = (term - trie->stringtab); /* Already in the string table! */
   751 						node->mode = Node_Term;
   752 					}
   753 					node->parent = lastidx;
   754 					node->valset = oldvalset;
   755 					node->value = oldvalue;
   756 				} else {
   757 					/* Finally, we have to create two new nodes instead of just one. */
   758 					node->mode = Node_Arc;
   759 					
   760 					/* Get the new base and apply re-basing */
   761 					q = x_check2(trie, *keyptr, *term);
   762 					base = trie->base;
   763 					node = &base[curidx];
   764 
   765 					node->idx = q;
   766 					lastidx = curidx;
   767 
   768 					/* Re-create the old terminated node */
   769 					curidx = q + charval(*term);
   770 					node = &trie->base[curidx];
   771 					term++;
   772 					node->valset = oldvalset;
   773 					node->value = oldvalue;
   774 					node->parent = lastidx;
   775 					if (*term == '\0')
   776 					{
   777 						node->mode = Node_Arc;
   778 					} else {
   779 						node->mode = Node_Term;
   780 						node->idx = (term - trie->stringtab); /* Already in the string table! */
   781 					}
   782 
   783 					/* Create the new keyed input node */
   784 					curidx = q + charval(*keyptr);
   785 					node = &trie->base[curidx];
   786 					keyptr++;
   787 					node->valset = true;
   788 					node->value = value;
   789 					node->parent = lastidx;
   790 					if (*keyptr == '\0')
   791 					{
   792 						node->mode = Node_Arc;
   793 					} else {
   794 						node->mode = Node_Term;
   795 						node->idx = x_addstring(trie, keyptr);
   796 					}
   797 				}
   798 
   799 				/* Phew! */
   800 				return true;
   801 			} else {
   802 				assert(node->mode == Node_Arc);
   803 			}
   804 		}
   805 		lastidx = curidx;
   806 	} while (*keyptr != '\0');
   807 
   808 	assert(node);
   809 
   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.
   812 	 */
   813 
   814 	/* We have to be an Arc.  If the last result was anything else, we would have returned a new 
   815 	 * production earlier.
   816 	 */
   817 	assert(node->mode == Node_Arc);
   818 
   819 	if (!node->valset)
   820 	{
   821 		/* Insert is only possible if we have no production */
   822 		node->valset = true;
   823 		node->value = value;
   824 		return true;
   825 	}
   826 
   827 	return false;
   828 }