sm_trie.cpp
author David Anderson <dvander@alliedmods.net>
Tue Jun 26 00:03:54 2007 +0000 (2007-06-26)
changeset 13 3f35cdcf6955
parent 0 67dcd379a2d5
permissions -rw-r--r--
- fixed up plugin headers a tiny bit
- added the ol' join advertisement back in
- added bot quota plugin in
dvander@0
     1
/**
dvander@0
     2
 * vim: set ts=4 :
dvander@0
     3
 * ===============================================================
dvander@0
     4
 * CS:S DM, Copyright (C) 2004-2007 AlliedModders LLC. 
dvander@0
     5
 * By David "BAILOPAN" Anderson
dvander@0
     6
 * All rights reserved.
dvander@0
     7
 * ===============================================================
dvander@0
     8
 *
dvander@0
     9
 * This program is free software; you can redistribute it and/or modify
dvander@0
    10
 * it under the terms of the GNU General Public License as published by
dvander@0
    11
 * the Free Software Foundation; either version 2 of the License, or (at
dvander@0
    12
 * your option) any later version.
dvander@0
    13
 * 
dvander@0
    14
 * This program is distributed in the hope that it will be useful, but
dvander@0
    15
 * WITHOUT ANY WARRANTY; without even the implied warranty of
dvander@0
    16
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
dvander@0
    17
 * General Public License for more details.
dvander@0
    18
 * 
dvander@0
    19
 * You should have received a copy of the GNU General Public License
dvander@0
    20
 * along with this program; see the file COPYING; if not, write to the
dvander@0
    21
 * Free Software Foundation, Inc., 51 Franklin St, Fifth Floor, Boston,
dvander@0
    22
 * MA 02110-1301 USA
dvander@0
    23
 * 
dvander@0
    24
 * Version: $Id$
dvander@0
    25
 */
dvander@0
    26
dvander@0
    27
dvander@0
    28
#include <string.h>
dvander@0
    29
#include <stdlib.h>
dvander@0
    30
#include <assert.h>
dvander@0
    31
#include "sm_trie.h"
dvander@0
    32
dvander@0
    33
/**
dvander@0
    34
 * Double Array Trie algorithm, based on:
dvander@0
    35
 * An Efficient Implementation of Trie Structures, by
dvander@0
    36
 *  Jun-ichi Aoe and Katsushi Maromoto, and Takashi Sato
dvander@0
    37
 * from Software - Practice and Experience, Vol. 22(9), 695-721 (September 1992)
dvander@0
    38
 *
dvander@0
    39
 *  A Trie is a simple data structure which stores strings as DFAs, with each 
dvander@0
    40
 * transition state being a string entry.  For example, observe the following strings:
dvander@0
    41
 *
dvander@0
    42
 * BAILOPAN, BAT, BACON, BACK
dvander@0
    43
 *  These transition as the follow production rules:
dvander@0
    44
 *  B -> ...                  B
dvander@0
    45
 *       A -> ...             BA
dvander@0
    46
 *            I -> ...        BAI
dvander@0
    47
 *                 LOPAN      BAILOPAN
dvander@0
    48
 *            T -> ...        BAT
dvander@0
    49
 *            C ->            BAC
dvander@0
    50
 *                 O -> ...   BACO
dvander@0
    51
 *                      N     BACON
dvander@0
    52
 *                 K          BACK
dvander@0
    53
 *
dvander@0
    54
 *  The standard implementation for this - using lists - gives a slow linear lookup, somewhere between
dvander@0
    55
 * O(N+M) or O(log n).  A faster implementation is proposed in the paper above, which is based on compacting
dvander@0
    56
 * the transition states into two arrays.  In the paper's implementation, two arrays are used, and thus it is
dvander@0
    57
 * called the "Double Array" algorithm.  However, the CHECK array's size is maintained the same as BASE, 
dvander@0
    58
 * so they can be combined into one structure.  The array seems complex at first, but is very simple: it is a
dvander@0
    59
 * tree structure flattened out into a single vector.  I am calling this implementation the Flat Array Trie.
dvander@0
    60
 *
dvander@0
    61
 *  BASE[] is an array where each member is a node in the Trie.  The node can either be UNUSED (empty), an ARC
dvander@0
    62
 * (containing an offset to the next set of ARCs), or a TERMINATOR (contains the rest of a string).
dvander@0
    63
 * Each node has an index which must be interpreted based on the node type.  If the node is a TERMINATOR, then the
dvander@0
    64
 * index is an index into a string table, to find the rest of the string.  
dvander@0
    65
 *  If the node is an ARC, the index is another index into BASE.  For each possible token that can follow the
dvander@0
    66
 * current token, the value of those tokens can be added to the index given in the ARC.  Thus, given a current
dvander@0
    67
 * position and the next desired token, the current arc will jump to another arc which can contain either:
dvander@0
    68
 *   1) An invalid production (collision, no entry exists)
dvander@0
    69
 *   2) An empty production (no entry exists)
dvander@0
    70
 *   3) Another arc label (the string ends here or continues into more productions)
dvander@0
    71
 *   4) A TERMINATOR (the string ends here and contains an unused set of productions)
dvander@0
    72
 * 
dvander@0
    73
 *  So, given current offset N (starting at N=1), jumping to token C means the next offset will be:
dvander@0
    74
 *      offs = BASE[n] + C
dvander@0
    75
 *  Thus, the next node will be at:
dvander@0
    76
 *      BASE[BASE[n] + C]
dvander@0
    77
 * 
dvander@0
    78
 *  This allows each ARC to specify the base offset for any of its ARC children, like a tree.  Each node specifies
dvander@0
    79
 * its parent ARC -- so if an invalid offset is specified, the parent will not match, and thus no such derived 
dvander@0
    80
 * string exists.
dvander@0
    81
 *
dvander@0
    82
 *  This means that arrays can be laid out "sparsely," maximizing their usage.  Note that N need not be related to
dvander@0
    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
dvander@0
    84
 * insertion comes with a small deal of complexity.  To insert a new set of tokens T, the algorithm finds a new 
dvander@0
    85
 * BASE index N such that BASE[N+T[i]] is unused for each T[i].  Thus, indirection is not necessarily linear; 
dvander@0
    86
 * traversing a chain of ARC nodes can _and will_ jump around BASE.
dvander@0
    87
 *
dvander@0
    88
 *  Of course, given this level of flexibility in the array organization, there are collisions.  This is largely 
dvander@0
    89
 * where insertions become slow, as the old chain must be relocated before the new one is used.  Relocation means 
dvander@0
    90
 * finding one or more new base indexes, and this means traversing BASE until an acceptable index is found, such 
dvander@0
    91
 * that each offset is unused (see description in previous paragraph).
dvander@0
    92
 *
dvander@0
    93
 *  However, it is not insertion time we are concerned about.  The "trie" name comes from reTRIEval.  We are only
dvander@0
    94
 * concerned with lookup and deletion.  Both lookup and deletion are O(k), where k is relative to the length of the 
dvander@0
    95
 * input string.  Note that it is best case O(1) and worst case O(k).  Deleting the entire trie is always O(1).
dvander@0
    96
 */
dvander@0
    97
dvander@0
    98
/**
dvander@0
    99
 * Optimization ideas for the future:
dvander@0
   100
 * 1) Store a reference count for each arc, with the count of sub-children.
dvander@0
   101
 *    This could let us break out of "children searches" for case 4 easily.
dvander@0
   102
 * 2) Use a 'free list' so we can easily search the trie for free points.
dvander@0
   103
 *    This would drastically speed up x_check*
dvander@0
   104
 */
dvander@0
   105
dvander@0
   106
enum NodeType
dvander@0
   107
{
dvander@0
   108
	Node_Unused = 0,		/* Node is not being used (sparse) */
dvander@0
   109
	Node_Arc,				/* Node is part of an arc and does not terminate */
dvander@0
   110
	Node_Term,				/* Node is a terminator */
dvander@0
   111
};
dvander@0
   112
dvander@0
   113
struct TrieNode
dvander@0
   114
{
dvander@0
   115
	/**
dvander@0
   116
	 * For Node_Arc, this index stores the 'base' offset to the next arc chain.
dvander@0
   117
	 *   I.e. to jump from this arc to character C, it will be at base[idx+C].
dvander@0
   118
	 * For Node_Term, this is an index into the string table.
dvander@0
   119
	 */
dvander@0
   120
	unsigned int idx;
dvander@0
   121
dvander@0
   122
	/**
dvander@0
   123
	 * This contains the prior arc that we must have come from.
dvander@0
   124
	 * For example, if arc 63 has a base jump of index 12, and we want to see if
dvander@0
   125
	 * there is a valid character C, the parent of 12+C must be 63.
dvander@0
   126
	 */
dvander@0
   127
	unsigned int parent;
dvander@0
   128
dvander@0
   129
	void *value;			/* Value associated with this node */
dvander@0
   130
	NodeType mode;			/* Current usage type of the node */
dvander@0
   131
	bool valset;			/* Whether or not a value is set */
dvander@0
   132
};
dvander@0
   133
dvander@0
   134
struct Trie
dvander@0
   135
{
dvander@0
   136
	TrieNode *base;			/* Base array for the sparse tables */
dvander@0
   137
	char *stringtab;		/* String table pointer */
dvander@0
   138
	unsigned int baseSize;	/* Size of the base array, in members */
dvander@0
   139
	unsigned int stSize;	/* Size of the string table, in bytes */
dvander@0
   140
	unsigned int tail;		/* Current unused offset into the string table */
dvander@0
   141
};
dvander@0
   142
dvander@0
   143
inline unsigned char charval(char c)
dvander@0
   144
{
dvander@0
   145
	return (unsigned char)c;
dvander@0
   146
}
dvander@0
   147
dvander@0
   148
bool sm_trie_grow(Trie *trie)
dvander@0
   149
{
dvander@0
   150
	/* The current # of nodes in the tree is trie->baseSize + 1 */
dvander@0
   151
	unsigned int curSize = trie->baseSize;
dvander@0
   152
	unsigned int newSize = curSize * 2;
dvander@0
   153
dvander@0
   154
	//:TODO: Make functions calling this return failure if this fails 
dvander@0
   155
	trie->base = (TrieNode *)realloc(trie->base, (newSize + 1) * sizeof(TrieNode));
dvander@0
   156
	if (!trie->base)
dvander@0
   157
	{
dvander@0
   158
		return false;
dvander@0
   159
	}
dvander@0
   160
dvander@0
   161
	memset(&trie->base[curSize+1], 0, (newSize - curSize) * sizeof(TrieNode));
dvander@0
   162
	trie->baseSize = newSize;
dvander@0
   163
dvander@0
   164
	return true;
dvander@0
   165
}
dvander@0
   166
dvander@0
   167
unsigned int x_check(Trie *trie, char c, unsigned int start=1)
dvander@0
   168
{
dvander@0
   169
	TrieNode *base = trie->base;
dvander@0
   170
	unsigned char _c = charval(c);
dvander@0
   171
	unsigned int to_check = trie->baseSize - _c;
dvander@0
   172
	for (unsigned int i=start; i<=to_check; i++)
dvander@0
   173
	{
dvander@0
   174
		if (base[i+_c].mode == Node_Unused)
dvander@0
   175
		{
dvander@0
   176
			return i;
dvander@0
   177
		}
dvander@0
   178
	}
dvander@0
   179
dvander@0
   180
	sm_trie_grow(trie);
dvander@0
   181
dvander@0
   182
	return x_check(trie, c, to_check+1);
dvander@0
   183
}
dvander@0
   184
dvander@0
   185
unsigned int x_check2(Trie *trie, char c1, char c2, unsigned int start=1)
dvander@0
   186
{
dvander@0
   187
	TrieNode *base = trie->base;
dvander@0
   188
	unsigned char _c1 = charval(c1);
dvander@0
   189
	unsigned char _c2 = charval(c2);
dvander@0
   190
	unsigned int to_check = trie->baseSize - (_c1 > _c2 ? _c1 : _c2);
dvander@0
   191
	for (unsigned int i=start; i<=to_check; i++)
dvander@0
   192
	{
dvander@0
   193
		if (base[i+_c1].mode == Node_Unused
dvander@0
   194
			&& base[i+_c2].mode == Node_Unused)
dvander@0
   195
		{
dvander@0
   196
			return i;
dvander@0
   197
		}
dvander@0
   198
	}
dvander@0
   199
dvander@0
   200
	sm_trie_grow(trie);
dvander@0
   201
dvander@0
   202
	return x_check2(trie, c1, c2, to_check+1);
dvander@0
   203
}
dvander@0
   204
dvander@0
   205
unsigned int x_check_multi(Trie *trie, 
dvander@0
   206
							unsigned int offsets[], 
dvander@0
   207
							unsigned int count,
dvander@0
   208
							unsigned int start=1)
dvander@0
   209
{
dvander@0
   210
	TrieNode *base = trie->base;
dvander@0
   211
	TrieNode *cur;
dvander@0
   212
	unsigned int to_check = trie->baseSize;
dvander@0
   213
	unsigned int highest = 0;
dvander@0
   214
dvander@0
   215
	for (unsigned int i=0; i<count; i++)
dvander@0
   216
	{
dvander@0
   217
		if (offsets[i] > highest)
dvander@0
   218
		{
dvander@0
   219
			highest = offsets[i];
dvander@0
   220
		}
dvander@0
   221
	}
dvander@0
   222
dvander@0
   223
	to_check -= highest;
dvander@0
   224
dvander@0
   225
	for (unsigned int i=start; i<=to_check; i++)
dvander@0
   226
	{
dvander@0
   227
		bool okay = true;
dvander@0
   228
		for (unsigned int j=0; j<count; j++)
dvander@0
   229
		{
dvander@0
   230
			cur = &base[i+offsets[j]];
dvander@0
   231
			if (cur->mode != Node_Unused)
dvander@0
   232
			{
dvander@0
   233
				okay = false;
dvander@0
   234
				break;
dvander@0
   235
			}
dvander@0
   236
		}
dvander@0
   237
		if (okay)
dvander@0
   238
		{
dvander@0
   239
			return i;
dvander@0
   240
		}
dvander@0
   241
	}
dvander@0
   242
dvander@0
   243
	sm_trie_grow(trie);
dvander@0
   244
dvander@0
   245
	return x_check_multi(trie, offsets, count, to_check+1);
dvander@0
   246
}
dvander@0
   247
dvander@0
   248
unsigned int x_addstring(Trie *trie, const char *ptr)
dvander@0
   249
{
dvander@0
   250
	size_t len = strlen(ptr) + 1;
dvander@0
   251
dvander@0
   252
	if (trie->tail + len >= trie->stSize)
dvander@0
   253
	{		
dvander@0
   254
		while (trie->tail + len >= trie->stSize)
dvander@0
   255
		{
dvander@0
   256
			trie->stSize *= 2;
dvander@0
   257
		}
dvander@0
   258
		trie->stringtab = (char *)realloc(trie->stringtab, trie->stSize);
dvander@0
   259
	}
dvander@0
   260
dvander@0
   261
	unsigned int tail = trie->tail;
dvander@0
   262
	strcpy(&trie->stringtab[tail], ptr);
dvander@0
   263
	trie->tail += len;
dvander@0
   264
dvander@0
   265
	return tail;
dvander@0
   266
}
dvander@0
   267
dvander@0
   268
Trie *sm_trie_create()
dvander@0
   269
{
dvander@0
   270
	Trie *t = new Trie;
dvander@0
   271
dvander@0
   272
	t->base = (TrieNode *)malloc(sizeof(TrieNode) * (256 + 1));
dvander@0
   273
	t->stringtab = (char *)malloc(sizeof(char) * 256);
dvander@0
   274
	t->baseSize = 256;
dvander@0
   275
	t->stSize = 256;
dvander@0
   276
dvander@0
   277
	sm_trie_clear(t);
dvander@0
   278
dvander@0
   279
	return t;
dvander@0
   280
}
dvander@0
   281
dvander@0
   282
void sm_trie_clear(Trie *trie)
dvander@0
   283
{
dvander@0
   284
	trie->tail = 0;
dvander@0
   285
dvander@0
   286
	memset(trie->base, 0, sizeof(TrieNode) * (trie->baseSize + 1));
dvander@0
   287
	memset(trie->stringtab, 0, sizeof(char) * trie->stSize);
dvander@0
   288
dvander@0
   289
	/* Sentinel root node */
dvander@0
   290
	trie->base[1].idx = 1;
dvander@0
   291
	trie->base[1].mode = Node_Arc;
dvander@0
   292
	trie->base[1].parent = 1;
dvander@0
   293
}
dvander@0
   294
dvander@0
   295
void sm_trie_destroy(Trie *trie)
dvander@0
   296
{
dvander@0
   297
	free(trie->base);
dvander@0
   298
	free(trie->stringtab);
dvander@0
   299
	delete trie;
dvander@0
   300
}
dvander@0
   301
dvander@0
   302
bool sm_trie_delete(Trie *trie, const char *key)
dvander@0
   303
{
dvander@0
   304
	unsigned int lastidx = 1;		/* the last node index */
dvander@0
   305
	unsigned int curidx;			/* current node index */
dvander@0
   306
	const char *keyptr = key;		/* input stream at current token */
dvander@0
   307
	TrieNode *node = NULL;			/* current node being processed */
dvander@0
   308
	TrieNode *base = trie->base;
dvander@0
   309
dvander@0
   310
	if (!*key)
dvander@0
   311
	{
dvander@0
   312
		return false;
dvander@0
   313
	}
dvander@0
   314
dvander@0
   315
	/* Start traversing at the root node */
dvander@0
   316
	do
dvander@0
   317
	{
dvander@0
   318
		/* Find where the next character is, then advance */
dvander@0
   319
		curidx = base[lastidx].idx;
dvander@0
   320
		node = &base[curidx];
dvander@0
   321
		curidx += charval(*keyptr);
dvander@0
   322
		node = &base[curidx];
dvander@0
   323
		keyptr++;
dvander@0
   324
dvander@0
   325
		/* Check if this slot is supposed to be empty or is a collision */
dvander@0
   326
		if ((curidx > trie->baseSize) || node->mode == Node_Unused || node->parent != lastidx)
dvander@0
   327
		{
dvander@0
   328
			return false;
dvander@0
   329
		} else if (node->mode == Node_Term) {
dvander@0
   330
			char *term = &trie->stringtab[node->idx];
dvander@0
   331
			if (strcmp(keyptr, term) == 0)
dvander@0
   332
			{
dvander@0
   333
				break;
dvander@0
   334
			}
dvander@0
   335
		}
dvander@0
   336
		lastidx = curidx;
dvander@0
   337
	} while (*keyptr != '\0');
dvander@0
   338
dvander@0
   339
	assert(node != NULL);
dvander@0
   340
dvander@0
   341
	if (!node->valset)
dvander@0
   342
	{
dvander@0
   343
		return false;
dvander@0
   344
	}
dvander@0
   345
dvander@0
   346
	node->valset = false;
dvander@0
   347
	node->value = NULL;
dvander@0
   348
dvander@0
   349
	return true;
dvander@0
   350
}
dvander@0
   351
dvander@0
   352
bool sm_trie_retrieve(Trie *trie, const char *key, void **value)
dvander@0
   353
{
dvander@0
   354
	unsigned int lastidx = 1;		/* the last node index */
dvander@0
   355
	unsigned int curidx;			/* current node index */
dvander@0
   356
	const char *keyptr = key;		/* input stream at current token */
dvander@0
   357
	TrieNode *node = NULL;			/* current node being processed */
dvander@0
   358
	TrieNode *base = trie->base;
dvander@0
   359
dvander@0
   360
	if (!*key)
dvander@0
   361
	{
dvander@0
   362
		return false;
dvander@0
   363
	}
dvander@0
   364
dvander@0
   365
	/* Start traversing at the root node */
dvander@0
   366
	do
dvander@0
   367
	{
dvander@0
   368
		/* Find where the next character is, then advance */
dvander@0
   369
		curidx = base[lastidx].idx;
dvander@0
   370
		node = &base[curidx];
dvander@0
   371
		curidx += charval(*keyptr);
dvander@0
   372
		node = &base[curidx];
dvander@0
   373
		keyptr++;
dvander@0
   374
dvander@0
   375
		/* Check if this slot is supposed to be empty or is a collision */
dvander@0
   376
		if ((curidx > trie->baseSize) || node->mode == Node_Unused || node->parent != lastidx)
dvander@0
   377
		{
dvander@0
   378
			return false;
dvander@0
   379
		} else if (node->mode == Node_Term) {
dvander@0
   380
			char *term = &trie->stringtab[node->idx];
dvander@0
   381
			if (strcmp(keyptr, term) == 0)
dvander@0
   382
			{
dvander@0
   383
				break;
dvander@0
   384
			}
dvander@0
   385
		}
dvander@0
   386
		lastidx = curidx;
dvander@0
   387
	} while (*keyptr != '\0');
dvander@0
   388
dvander@0
   389
	assert(node != NULL);
dvander@0
   390
dvander@0
   391
	if (!node->valset)
dvander@0
   392
	{
dvander@0
   393
		return false;
dvander@0
   394
	}
dvander@0
   395
dvander@0
   396
	if (value)
dvander@0
   397
	{
dvander@0
   398
		*value = node->value;
dvander@0
   399
	}
dvander@0
   400
dvander@0
   401
	return true;
dvander@0
   402
}
dvander@0
   403
dvander@0
   404
bool sm_trie_insert(Trie *trie, const char *key, void *value)
dvander@0
   405
{
dvander@0
   406
	unsigned int lastidx = 1;		/* the last node index */
dvander@0
   407
	unsigned int curidx;			/* current node index */
dvander@0
   408
	const char *keyptr = key;		/* input stream at current token */
dvander@0
   409
	TrieNode *node = NULL;			/* current node being processed */
dvander@0
   410
	TrieNode *basenode = NULL;		/* current base node being processed */
dvander@0
   411
	unsigned int q;					/* temporary var for x_check results */
dvander@0
   412
	TrieNode *base = trie->base;
dvander@0
   413
	unsigned int curoffs;			/* current offset */
dvander@0
   414
dvander@0
   415
	/* Do not handle empty strings for simplicity */
dvander@0
   416
	if (!*key)
dvander@0
   417
	{
dvander@0
   418
		return false;
dvander@0
   419
	}
dvander@0
   420
dvander@0
   421
	/* Start traversing at the root node (1) */
dvander@0
   422
	do
dvander@0
   423
	{
dvander@0
   424
		/* Find where the next character is, then advance */
dvander@0
   425
		curidx = base[lastidx].idx;
dvander@0
   426
		basenode = &base[curidx];
dvander@0
   427
		curoffs = charval(*keyptr);
dvander@0
   428
		curidx += curoffs;
dvander@0
   429
		node = &base[curidx];
dvander@0
   430
		keyptr++;
dvander@0
   431
dvander@0
   432
		/* Check if this slot is supposed to be empty.  If so, we need to handle CASES 1/2:
dvander@0
   433
		 * Insertion without collisions
dvander@0
   434
		 */
dvander@0
   435
		if ( (curidx > trie->baseSize) || (node->mode == Node_Unused) )
dvander@0
   436
		{
dvander@0
   437
			if (curidx > trie->baseSize)
dvander@0
   438
			{
dvander@0
   439
				if (!sm_trie_grow(trie))
dvander@0
   440
				{
dvander@0
   441
					return false;
dvander@0
   442
				}
dvander@0
   443
				node = &trie->base[curidx];
dvander@0
   444
			}
dvander@0
   445
			node->parent = lastidx;
dvander@0
   446
			if (*keyptr == '\0')
dvander@0
   447
			{
dvander@0
   448
				node->mode = Node_Arc;
dvander@0
   449
			} else {
dvander@0
   450
				node->idx = x_addstring(trie, keyptr);
dvander@0
   451
				node->mode = Node_Term;
dvander@0
   452
			}
dvander@0
   453
			node->valset = true;
dvander@0
   454
			node->value = value;
dvander@0
   455
			
dvander@0
   456
			return true;
dvander@0
   457
		} else if (node->parent != lastidx) {
dvander@0
   458
			/* Collision! We have to split up the tree here.  CASE 4:
dvander@0
   459
			 * Insertion when a new word is inserted with a collision.
dvander@0
   460
			 * NOTE: This is the hardest case to handle.  All below examples are based on:
dvander@0
   461
			 * BACHELOR, BADGE, inserting BABY.
dvander@0
   462
			 * The problematic production here is A -> B, where B is already being used.
dvander@0
   463
			 *
dvander@0
   464
			 * This process has to rotate one half of the 'A' arc.  We generate two lists:
dvander@0
   465
			 *  Outgoing Arcs - Anything leaving this 'A'
dvander@0
   466
			 *  Incoming Arcs - Anything going to this 'A'
dvander@0
   467
			 * Whichever list is smaller will be moved.  Note that this works because the intersection
dvander@0
   468
			 * affects both arc chains, and moving one will make the slot available to either.
dvander@0
   469
			 */
dvander@0
   470
			TrieNode *cur;
dvander@0
   471
			
dvander@0
   472
			/* Find every node arcing from the last node.
dvander@0
   473
			 * I.e. for BACHELOR, BADGE, BABY,
dvander@0
   474
			 * The arcs leaving A will be C and D, but our current node is B -> *.
dvander@0
   475
			 * Thus, we use the last index (A) to find the base for arcs leaving A.
dvander@0
   476
			 */
dvander@0
   477
			unsigned int outgoing_base = base[lastidx].idx;
dvander@0
   478
			unsigned int outgoing_list[256];
dvander@0
   479
			unsigned int outgoing_count = 0;	/* count the current index here */
dvander@0
   480
			cur = &base[outgoing_base] + 1;
dvander@0
   481
			unsigned int outgoing_limit = 255;
dvander@0
   482
dvander@0
   483
			if (outgoing_base + outgoing_limit > trie->baseSize)
dvander@0
   484
			{
dvander@0
   485
				outgoing_limit = trie->baseSize - outgoing_base;
dvander@0
   486
			}
dvander@0
   487
dvander@0
   488
			for (unsigned int i=1; i<=outgoing_limit; i++,cur++)
dvander@0
   489
			{
dvander@0
   490
				if (cur->mode == Node_Unused || cur->parent != lastidx)
dvander@0
   491
				{
dvander@0
   492
					continue;
dvander@0
   493
				}
dvander@0
   494
				outgoing_list[outgoing_count++] = i;
dvander@0
   495
			}
dvander@0
   496
			outgoing_list[outgoing_count++] = curidx - outgoing_base;
dvander@0
   497
dvander@0
   498
			/* Now we need to find all the arcs leaving our parent...
dvander@0
   499
			 * Note: the inconsistency is the base of our parent.  
dvander@0
   500
			 */
dvander@0
   501
			assert(base[node->parent].mode == Node_Arc);
dvander@0
   502
			unsigned int incoming_list[256];
dvander@0
   503
			unsigned int incoming_base = base[node->parent].idx;
dvander@0
   504
			unsigned int incoming_count = 0;
dvander@0
   505
			unsigned int incoming_limit = 255;
dvander@0
   506
			cur = &base[incoming_base] + 1;
dvander@0
   507
dvander@0
   508
			if (incoming_base + incoming_limit > trie->baseSize)
dvander@0
   509
			{
dvander@0
   510
				incoming_limit = trie->baseSize - incoming_base;
dvander@0
   511
			}
dvander@0
   512
dvander@0
   513
			assert(incoming_limit > 0 && incoming_limit <= 255);
dvander@0
   514
dvander@0
   515
			for (unsigned int i=1; i<=255; i++,cur++)
dvander@0
   516
			{
dvander@0
   517
				if (cur->mode == Node_Arc || cur->mode == Node_Term)
dvander@0
   518
				{
dvander@0
   519
					if (cur->parent == node->parent)
dvander@0
   520
					{
dvander@0
   521
						incoming_list[incoming_count++] = i;
dvander@0
   522
					}
dvander@0
   523
				}
dvander@0
   524
			}
dvander@0
   525
dvander@0
   526
			if (incoming_count < outgoing_count + 1)
dvander@0
   527
			{
dvander@0
   528
				unsigned int q = x_check_multi(trie, incoming_list, incoming_count);
dvander@0
   529
dvander@0
   530
				base = trie->base;
dvander@0
   531
				node = &base[curidx];
dvander@0
   532
dvander@0
   533
				/* If we're incoming, we need to modify our parent */
dvander@0
   534
				base[node->parent].idx = q;
dvander@0
   535
dvander@0
   536
				/* For each node in the "to move" list,
dvander@0
   537
				 * Relocate the node's info to the new position.
dvander@0
   538
				 */
dvander@0
   539
				unsigned int idx, newidx, oldidx;
dvander@0
   540
				for (unsigned int i=0; i<incoming_count; i++)
dvander@0
   541
				{
dvander@0
   542
					idx = incoming_list[i];
dvander@0
   543
					newidx = q + idx;
dvander@0
   544
					oldidx = incoming_base + idx;
dvander@0
   545
					if (oldidx == lastidx)
dvander@0
   546
					{
dvander@0
   547
						/* Important! Make sure we're not invalidating our sacred lastidx */
dvander@0
   548
						lastidx = newidx;
dvander@0
   549
					}
dvander@0
   550
					base[newidx] = base[oldidx];
dvander@0
   551
					assert(base[base[newidx].parent].mode == Node_Arc);
dvander@0
   552
					memset(&base[oldidx], 0, sizeof(TrieNode));
dvander@0
   553
					/* If we are not a terminator, we have children we must take care of */
dvander@0
   554
					if (base[newidx].mode == Node_Arc)
dvander@0
   555
					{
dvander@0
   556
						TrieNode *check_base = &base[base[newidx].idx] + 1;
dvander@0
   557
						for (unsigned int j=1; j<=255; j++, check_base++)
dvander@0
   558
						{
dvander@0
   559
							if (check_base->parent == oldidx)
dvander@0
   560
							{
dvander@0
   561
								check_base->parent = newidx;
dvander@0
   562
							}
dvander@0
   563
						}
dvander@0
   564
					}
dvander@0
   565
				}
dvander@0
   566
			} else {
dvander@0
   567
				unsigned int q = x_check_multi(trie, outgoing_list, outgoing_count);
dvander@0
   568
dvander@0
   569
				base = trie->base;
dvander@0
   570
				node = &base[curidx];
dvander@0
   571
dvander@0
   572
				/* If we're outgoing, we need to modify our own base */
dvander@0
   573
				base[lastidx].idx = q;
dvander@0
   574
dvander@0
   575
				/* Take the last index (curidx) out of the list.  Technically we are not moving this,
dvander@0
   576
				 * since it's already being used by something else.  
dvander@0
   577
				 */
dvander@0
   578
				outgoing_count--;
dvander@0
   579
dvander@0
   580
				/* For each node in the "to move" list,
dvander@0
   581
				 * Relocate the node's info to the new position.
dvander@0
   582
				 */
dvander@0
   583
				unsigned int idx, newidx, oldidx;
dvander@0
   584
				for (unsigned int i=0; i<outgoing_count; i++)
dvander@0
   585
				{
dvander@0
   586
					idx = outgoing_list[i];
dvander@0
   587
					newidx = q + idx;
dvander@0
   588
					oldidx = outgoing_base + idx;
dvander@0
   589
					if (oldidx == lastidx)
dvander@0
   590
					{
dvander@0
   591
						/* Important! Make sure we're not invalidating our sacred lastidx */
dvander@0
   592
						lastidx = newidx;
dvander@0
   593
					}
dvander@0
   594
					base[newidx] = base[oldidx];
dvander@0
   595
					assert(base[base[newidx].parent].mode == Node_Arc);
dvander@0
   596
					memset(&base[oldidx], 0, sizeof(TrieNode));
dvander@0
   597
					/* If we are not a terminator, we have children we must take care of */
dvander@0
   598
					if (base[newidx].mode == Node_Arc)
dvander@0
   599
					{
dvander@0
   600
						TrieNode *check_base = &base[base[newidx].idx] + 1;
dvander@0
   601
						for (unsigned int j=1; j<=255; j++, check_base++)
dvander@0
   602
						{
dvander@0
   603
							if (check_base->parent == oldidx)
dvander@0
   604
							{
dvander@0
   605
								check_base->parent = newidx;
dvander@0
   606
							}
dvander@0
   607
						}
dvander@0
   608
					}
dvander@0
   609
				}
dvander@0
   610
dvander@0
   611
				/* Take the invisible node and use it as our new node */
dvander@0
   612
				node = &base[q + outgoing_list[outgoing_count]];
dvander@0
   613
			}
dvander@0
   614
dvander@0
   615
			/* We're finally done! */
dvander@0
   616
			node->parent = lastidx;
dvander@0
   617
			if (*keyptr == '\0')
dvander@0
   618
			{
dvander@0
   619
				node->mode = Node_Arc;
dvander@0
   620
			} else {
dvander@0
   621
				node->idx = x_addstring(trie, keyptr);
dvander@0
   622
				node->mode = Node_Term;
dvander@0
   623
			}
dvander@0
   624
			node->valset = true;
dvander@0
   625
			node->value = value;
dvander@0
   626
dvander@0
   627
			return true;
dvander@0
   628
		} else {
dvander@0
   629
			/* See what's in the next node - special case if terminator! */
dvander@0
   630
			if (node->mode == Node_Term)
dvander@0
   631
			{
dvander@0
   632
				/* If we're a terminator, we need to handle CASE 3:
dvander@0
   633
				 * Insertion when a terminating collision occurs
dvander@0
   634
				 */
dvander@0
   635
				char *term = &trie->stringtab[node->idx];
dvander@0
   636
				/* Do an initial browsing to make sure they're not the same string */
dvander@0
   637
				if (strcmp(keyptr, term) == 0)
dvander@0
   638
				{
dvander@0
   639
					if (!node->valset)
dvander@0
   640
					{
dvander@0
   641
						node->valset = true;
dvander@0
   642
						node->value = value;
dvander@0
   643
						return true;
dvander@0
   644
					}
dvander@0
   645
					/* Same string.  We can't insert. */
dvander@0
   646
					return false;
dvander@0
   647
				}
dvander@0
   648
				/* For each matching character pair, we need to disband the terminator.
dvander@0
   649
				 * This splits the similar prefix into a single arc path.
dvander@0
   650
				 * First, save the old values so we can move them to a new node.
dvander@0
   651
				 * Next, for each loop:
dvander@0
   652
				 *  Take the current (invalid) node, and point it to the next arc base.
dvander@0
   653
				 *  Set the current node to the node at the next arc.
dvander@0
   654
				 */
dvander@0
   655
				void *oldvalue = node->value;
dvander@0
   656
				bool oldvalset = node->valset;
dvander@0
   657
				if (*term == *keyptr)
dvander@0
   658
				{
dvander@0
   659
				while (*term == *keyptr)
dvander@0
   660
				{
dvander@0
   661
					/* Find the next free slot in the check array.
dvander@0
   662
					 * This is the "vector base" essentially
dvander@0
   663
					 */
dvander@0
   664
					q = x_check(trie, *term);
dvander@0
   665
						base = trie->base;
dvander@0
   666
						node = &base[curidx];
dvander@0
   667
					/* Point the node to the next new base */
dvander@0
   668
					node->idx = q;
dvander@0
   669
					node->mode = Node_Arc;
dvander@0
   670
					node->valset = false;
dvander@0
   671
					/* Advance the input stream and local variables */
dvander@0
   672
					lastidx = curidx;
dvander@0
   673
					curidx = q + charval(*term);
dvander@0
   674
					node = &base[curidx];
dvander@0
   675
					/* Make sure the new current node has its parent set. */
dvander@0
   676
					node->parent = lastidx;
dvander@0
   677
					node->mode = Node_Arc;	/* Just in case we run x_check again */
dvander@0
   678
					*term = '\0';	/* Unmark the string table here */
dvander@0
   679
					term++;
dvander@0
   680
					keyptr++;
dvander@0
   681
					}
dvander@0
   682
				} else {
dvander@0
   683
					node->valset = false;
dvander@0
   684
				}
dvander@0
   685
				/* We're done inserting new pairs.  If one of them is exhausted,
dvander@0
   686
				 * we take special shortcuts.
dvander@0
   687
				 */
dvander@0
   688
				if (*term == '\0')				//EX: BADGERHOUSE added over B -> ADGER.  
dvander@0
   689
				{
dvander@0
   690
					/* First backpatch the current node - it ends the newly split terminator.
dvander@0
   691
					 * In the example, this would mean the node is the production from R -> ?
dvander@0
   692
					 * This node ends the old BADGER, so we set it here.
dvander@0
   693
					 */
dvander@0
   694
					node->valset = oldvalset;
dvander@0
   695
					node->value = oldvalue;
dvander@0
   696
dvander@0
   697
					/* The terminator was split up, but pieces of keyptr remain.
dvander@0
   698
					 * We need to generate a new production, in this example, R -> H,
dvander@0
   699
					 * with H being a terminator to OUSE.  Thus we get:
dvander@0
   700
					 * B,A,D,G,E,R*,H*->OUSE (* = value set).
dvander@0
   701
					 * NOTE: parent was last set at the end of the while loop.
dvander@0
   702
					 */
dvander@0
   703
					/* Get the new base and apply re-basing */
dvander@0
   704
					q = x_check(trie, *keyptr);
dvander@0
   705
					base = trie->base;
dvander@0
   706
					node = &base[curidx];
dvander@0
   707
dvander@0
   708
					node->idx = q;
dvander@0
   709
					node->mode = Node_Arc;
dvander@0
   710
					lastidx = curidx;
dvander@0
   711
					/* Finish the final node */
dvander@0
   712
					curidx = q + charval(*keyptr);
dvander@0
   713
					node = &trie->base[curidx];
dvander@0
   714
					keyptr++;
dvander@0
   715
					/* Optimize - don't add to string table if there's nothing more to eat */
dvander@0
   716
					if (*keyptr == '\0')
dvander@0
   717
					{
dvander@0
   718
						node->mode = Node_Arc;
dvander@0
   719
					} else {
dvander@0
   720
						node->idx = x_addstring(trie, keyptr);
dvander@0
   721
						node->mode = Node_Term;
dvander@0
   722
					}
dvander@0
   723
					node->parent = lastidx;
dvander@0
   724
					node->valset = true;
dvander@0
   725
					node->value = value;
dvander@0
   726
				} else if (*keyptr == '\0') {	//EX: BADGER added over B -> ADGERHOUSE
dvander@0
   727
					/* First backpatch the current node - it ends newly split input string.
dvander@0
   728
					 * This is the exact opposite of the above procedure.
dvander@0
   729
					 */
dvander@0
   730
					node->valset = true;
dvander@0
   731
					node->value = value;
dvander@0
   732
dvander@0
   733
					/* Get the new base and apply re-basing */
dvander@0
   734
					q = x_check(trie, *term);
dvander@0
   735
					base = trie->base;
dvander@0
   736
					node = &base[curidx];
dvander@0
   737
dvander@0
   738
					node->idx = q;
dvander@0
   739
					node->mode = Node_Arc;
dvander@0
   740
					lastidx = curidx;
dvander@0
   741
					/* Finish the final node */
dvander@0
   742
					curidx = q + charval(*term);
dvander@0
   743
					node = &trie->base[curidx];
dvander@0
   744
					term++;
dvander@0
   745
					/* Optimize - don't add to string table if there's nothing more to eat */
dvander@0
   746
					if (*term == '\0')
dvander@0
   747
					{
dvander@0
   748
						node->mode = Node_Arc;
dvander@0
   749
					} else {
dvander@0
   750
						node->idx = (term - trie->stringtab); /* Already in the string table! */
dvander@0
   751
						node->mode = Node_Term;
dvander@0
   752
					}
dvander@0
   753
					node->parent = lastidx;
dvander@0
   754
					node->valset = oldvalset;
dvander@0
   755
					node->value = oldvalue;
dvander@0
   756
				} else {
dvander@0
   757
					/* Finally, we have to create two new nodes instead of just one. */
dvander@0
   758
					node->mode = Node_Arc;
dvander@0
   759
					
dvander@0
   760
					/* Get the new base and apply re-basing */
dvander@0
   761
					q = x_check2(trie, *keyptr, *term);
dvander@0
   762
					base = trie->base;
dvander@0
   763
					node = &base[curidx];
dvander@0
   764
dvander@0
   765
					node->idx = q;
dvander@0
   766
					lastidx = curidx;
dvander@0
   767
dvander@0
   768
					/* Re-create the old terminated node */
dvander@0
   769
					curidx = q + charval(*term);
dvander@0
   770
					node = &trie->base[curidx];
dvander@0
   771
					term++;
dvander@0
   772
					node->valset = oldvalset;
dvander@0
   773
					node->value = oldvalue;
dvander@0
   774
					node->parent = lastidx;
dvander@0
   775
					if (*term == '\0')
dvander@0
   776
					{
dvander@0
   777
						node->mode = Node_Arc;
dvander@0
   778
					} else {
dvander@0
   779
						node->mode = Node_Term;
dvander@0
   780
						node->idx = (term - trie->stringtab); /* Already in the string table! */
dvander@0
   781
					}
dvander@0
   782
dvander@0
   783
					/* Create the new keyed input node */
dvander@0
   784
					curidx = q + charval(*keyptr);
dvander@0
   785
					node = &trie->base[curidx];
dvander@0
   786
					keyptr++;
dvander@0
   787
					node->valset = true;
dvander@0
   788
					node->value = value;
dvander@0
   789
					node->parent = lastidx;
dvander@0
   790
					if (*keyptr == '\0')
dvander@0
   791
					{
dvander@0
   792
						node->mode = Node_Arc;
dvander@0
   793
					} else {
dvander@0
   794
						node->mode = Node_Term;
dvander@0
   795
						node->idx = x_addstring(trie, keyptr);
dvander@0
   796
					}
dvander@0
   797
				}
dvander@0
   798
dvander@0
   799
				/* Phew! */
dvander@0
   800
				return true;
dvander@0
   801
			} else {
dvander@0
   802
				assert(node->mode == Node_Arc);
dvander@0
   803
			}
dvander@0
   804
		}
dvander@0
   805
		lastidx = curidx;
dvander@0
   806
	} while (*keyptr != '\0');
dvander@0
   807
dvander@0
   808
	assert(node);
dvander@0
   809
dvander@0
   810
	/* If we've exhausted the string and we have a valid reached node,
dvander@0
   811
	 * the production rule already existed.  Make sure it's valid to set first.
dvander@0
   812
	 */
dvander@0
   813
dvander@0
   814
	/* We have to be an Arc.  If the last result was anything else, we would have returned a new 
dvander@0
   815
	 * production earlier.
dvander@0
   816
	 */
dvander@0
   817
	assert(node->mode == Node_Arc);
dvander@0
   818
dvander@0
   819
	if (!node->valset)
dvander@0
   820
	{
dvander@0
   821
		/* Insert is only possible if we have no production */
dvander@0
   822
		node->valset = true;
dvander@0
   823
		node->value = value;
dvander@0
   824
		return true;
dvander@0
   825
	}
dvander@0
   826
dvander@0
   827
	return false;
dvander@0
   828
}