dvander@370: /**
ds@653: * vim: set ts=4 :
ds@1330: * =============================================================================
dvander@1231: * SourceMod
dvander@1231: * Copyright (C) 2004-2007 AlliedModders LLC. All rights reserved.
ds@1330: * =============================================================================
dvander@370: *
ds@1330: * This program is free software; you can redistribute it and/or modify it under
ds@1330: * the terms of the GNU General Public License, version 3.0, as published by the
ds@1330: * Free Software Foundation.
dvander@1231: *
ds@1330: * This program is distributed in the hope that it will be useful, but WITHOUT
ds@1330: * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
ds@1330: * FOR A PARTICULAR PURPOSE. See the GNU General Public License for more
ds@1330: * details.
dvander@1231: *
ds@1330: * You should have received a copy of the GNU General Public License along with
ds@1330: * this program. If not, see .
dvander@1231: *
ds@1330: * As a special exception, AlliedModders LLC gives you permission to link the
ds@1330: * code of this program (as well as its derivative works) to "Half-Life 2," the
ds@1330: * "Source Engine," the "SourcePawn JIT," and any Game MODs that run on software
ds@1330: * by the Valve Corporation. You must obey the GNU General Public License in
ds@1330: * all respects for all other code used. Additionally, AlliedModders LLC grants
ds@1330: * this exception to all derivative works. AlliedModders LLC defines further
ds@1330: * exceptions, found in LICENSE.txt (as of this writing, version JULY-31-2007),
ds@1330: * or .
dvander@370: *
dvander@370: * Version: $Id$
dvander@370: */
dvander@370:
dvander@189: #include
dvander@189: #include
dvander@189: #include
dvander@189: #include "sm_trie.h"
dvander@189:
dvander@189: /**
dvander@189: * Double Array Trie algorithm, based on:
dvander@189: * An Efficient Implementation of Trie Structures, by
dvander@189: * Jun-ichi Aoe and Katsushi Maromoto, and Takashi Sato
ds@729: * from Software - Practice and Experience, Vol. 22(9), 695-721 (September 1992)
dvander@189: *
dvander@189: * A Trie is a simple data structure which stores strings as DFAs, with each
dvander@189: * transition state being a string entry. For example, observe the following strings:
dvander@189: *
dvander@189: * BAILOPAN, BAT, BACON, BACK
dvander@189: * These transition as the follow production rules:
dvander@189: * B -> ... B
dvander@189: * A -> ... BA
dvander@189: * I -> ... BAI
dvander@189: * LOPAN BAILOPAN
dvander@189: * T -> ... BAT
dvander@189: * C -> BAC
dvander@189: * O -> ... BACO
dvander@189: * N BACON
dvander@189: * K BACK
dvander@189: *
dvander@189: * The standard implementation for this - using lists - gives a slow linear lookup, somewhere between
dvander@189: * O(N+M) or O(log n). A faster implementation is proposed in the paper above, which is based on compacting
dvander@189: * the transition states into two arrays. In the paper's implementation, two arrays are used, and thus it is
dvander@189: * called the "Double Array" algorithm. However, the CHECK array's size is maintained the same as BASE,
dvander@189: * so they can be combined into one structure. The array seems complex at first, but is very simple: it is a
dvander@189: * tree structure flattened out into a single vector. I am calling this implementation the Flat Array Trie.
dvander@189: *
dvander@189: * BASE[] is an array where each member is a node in the Trie. The node can either be UNUSED (empty), an ARC
dvander@189: * (containing an offset to the next set of ARCs), or a TERMINATOR (contains the rest of a string).
ds@729: * Each node has an index which must be interpreted based on the node type. If the node is a TERMINATOR, then the
dvander@189: * index is an index into a string table, to find the rest of the string.
dvander@189: * If the node is an ARC, the index is another index into BASE. For each possible token that can follow the
dvander@189: * current token, the value of those tokens can be added to the index given in the ARC. Thus, given a current
dvander@189: * position and the next desired token, the current arc will jump to another arc which can contain either:
dvander@189: * 1) An invalid production (collision, no entry exists)
dvander@189: * 2) An empty production (no entry exists)
dvander@189: * 3) Another arc label (the string ends here or continues into more productions)
dvander@189: * 4) A TERMINATOR (the string ends here and contains an unused set of productions)
dvander@189: *
dvander@189: * So, given current offset N (starting at N=1), jumping to token C means the next offset will be:
dvander@189: * offs = BASE[n] + C
dvander@189: * Thus, the next node will be at:
dvander@189: * BASE[BASE[n] + C]
dvander@189: *
dvander@189: * This allows each ARC to specify the base offset for any of its ARC children, like a tree. Each node specifies
dvander@189: * its parent ARC -- so if an invalid offset is specified, the parent will not match, and thus no such derived
dvander@189: * string exists.
dvander@189: *
dvander@189: * This means that arrays can be laid out "sparsely," maximizing their usage. Note that N need not be related to
dvander@189: * 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@189: * insertion comes with a small deal of complexity. To insert a new set of tokens T, the algorithm finds a new
dvander@189: * BASE index N such that BASE[N+T[i]] is unused for each T[i]. Thus, indirection is not necessarily linear;
dvander@189: * traversing a chain of ARC nodes can _and will_ jump around BASE.
dvander@189: *
dvander@189: * Of course, given this level of flexibility in the array organization, there are collisions. This is largely
dvander@189: * where insertions become slow, as the old chain must be relocated before the new one is used. Relocation means
dvander@189: * finding one or more new base indexes, and this means traversing BASE until an acceptable index is found, such
dvander@189: * that each offset is unused (see description in previous paragraph).
dvander@189: *
dvander@189: * However, it is not insertion time we are concerned about. The "trie" name comes from reTRIEval. We are only
dvander@189: * concerned with lookup and deletion. Both lookup and deletion are O(k), where k is relative to the length of the
dvander@189: * input string. Note that it is best case O(1) and worst case O(k). Deleting the entire trie is always O(1).
dvander@189: */
dvander@189:
dvander@189: /**
dvander@189: * Optimization ideas for the future:
dvander@189: * 1) Store a reference count for each arc, with the count of sub-children.
dvander@189: * This could let us break out of "children searches" for case 4 easily.
dvander@189: * 2) Use a 'free list' so we can easily search the trie for free points.
dvander@189: * This would drastically speed up x_check*
dvander@189: */
dvander@189:
dvander@189: enum NodeType
dvander@189: {
dvander@189: Node_Unused = 0, /* Node is not being used (sparse) */
dvander@189: Node_Arc, /* Node is part of an arc and does not terminate */
dvander@189: Node_Term, /* Node is a terminator */
dvander@189: };
dvander@189:
dvander@189: struct TrieNode
dvander@189: {
dvander@189: /**
dvander@189: * For Node_Arc, this index stores the 'base' offset to the next arc chain.
dvander@189: * I.e. to jump from this arc to character C, it will be at base[idx+C].
dvander@189: * For Node_Term, this is an index into the string table.
dvander@189: */
dvander@189: unsigned int idx;
dvander@189:
dvander@189: /**
dvander@189: * This contains the prior arc that we must have come from.
dvander@189: * For example, if arc 63 has a base jump of index 12, and we want to see if
dvander@189: * there is a valid character C, the parent of 12+C must be 63.
dvander@189: */
dvander@189: unsigned int parent;
dvander@189:
dvander@189: void *value; /* Value associated with this node */
dvander@189: NodeType mode; /* Current usage type of the node */
dvander@189: bool valset; /* Whether or not a value is set */
dvander@189: };
dvander@189:
dvander@189: struct Trie
dvander@189: {
dvander@189: TrieNode *base; /* Base array for the sparse tables */
dvander@189: char *stringtab; /* String table pointer */
dvander@189: unsigned int baseSize; /* Size of the base array, in members */
dvander@189: unsigned int stSize; /* Size of the string table, in bytes */
dvander@189: unsigned int tail; /* Current unused offset into the string table */
dvander@189: };
dvander@189:
dvander@189: inline unsigned char charval(char c)
dvander@189: {
dvander@190: return (unsigned char)c;
dvander@189: }
dvander@189:
dvander@193: bool sm_trie_grow(Trie *trie)
dvander@193: {
dvander@193: /* The current # of nodes in the tree is trie->baseSize + 1 */
dvander@193: unsigned int curSize = trie->baseSize;
dvander@193: unsigned int newSize = curSize * 2;
dvander@193:
dvander@193: //:TODO: Make functions calling this return failure if this fails
dvander@193: trie->base = (TrieNode *)realloc(trie->base, (newSize + 1) * sizeof(TrieNode));
dvander@193: if (!trie->base)
dvander@193: {
dvander@193: return false;
dvander@193: }
dvander@193:
dvander@193: memset(&trie->base[curSize+1], 0, (newSize - curSize) * sizeof(TrieNode));
dvander@193: trie->baseSize = newSize;
dvander@193:
dvander@193: return true;
dvander@193: }
dvander@193:
dvander@193: unsigned int x_check(Trie *trie, char c, unsigned int start=1)
dvander@189: {
dvander@189: TrieNode *base = trie->base;
dvander@189: unsigned char _c = charval(c);
dvander@189: unsigned int to_check = trie->baseSize - _c;
dvander@193: for (unsigned int i=start; i<=to_check; i++)
dvander@189: {
dvander@189: if (base[i+_c].mode == Node_Unused)
dvander@189: {
dvander@189: return i;
dvander@189: }
dvander@189: }
dvander@189:
dvander@193: sm_trie_grow(trie);
dvander@189:
dvander@193: return x_check(trie, c, to_check+1);
dvander@189: }
dvander@189:
dvander@193: unsigned int x_check2(Trie *trie, char c1, char c2, unsigned int start=1)
dvander@189: {
dvander@189: TrieNode *base = trie->base;
dvander@189: unsigned char _c1 = charval(c1);
dvander@189: unsigned char _c2 = charval(c2);
dvander@189: unsigned int to_check = trie->baseSize - (_c1 > _c2 ? _c1 : _c2);
dvander@193: for (unsigned int i=start; i<=to_check; i++)
dvander@189: {
dvander@189: if (base[i+_c1].mode == Node_Unused
dvander@189: && base[i+_c2].mode == Node_Unused)
dvander@189: {
dvander@189: return i;
dvander@189: }
dvander@189: }
dvander@189:
dvander@193: sm_trie_grow(trie);
dvander@189:
dvander@193: return x_check2(trie, c1, c2, to_check+1);
dvander@189: }
dvander@189:
dvander@189: unsigned int x_check_multi(Trie *trie,
dvander@189: unsigned int offsets[],
dvander@193: unsigned int count,
dvander@193: unsigned int start=1)
dvander@189: {
dvander@189: TrieNode *base = trie->base;
dvander@189: TrieNode *cur;
dvander@189: unsigned int to_check = trie->baseSize;
dvander@193: unsigned int highest = 0;
dvander@193:
dvander@193: for (unsigned int i=0; i highest)
dvander@193: {
dvander@193: highest = offsets[i];
dvander@193: }
dvander@193: }
dvander@193:
dvander@193: to_check -= highest;
dvander@193:
dvander@193: for (unsigned int i=start; i<=to_check; i++)
dvander@189: {
dvander@189: bool okay = true;
dvander@189: for (unsigned int j=0; jmode != Node_Unused)
dvander@189: {
dvander@189: okay = false;
dvander@189: break;
dvander@189: }
dvander@189: }
dvander@189: if (okay)
dvander@189: {
dvander@189: return i;
dvander@189: }
dvander@189: }
dvander@189:
dvander@193: sm_trie_grow(trie);
dvander@189:
dvander@193: return x_check_multi(trie, offsets, count, to_check+1);
dvander@189: }
dvander@189:
dvander@189: unsigned int x_addstring(Trie *trie, const char *ptr)
dvander@189: {
dvander@189: size_t len = strlen(ptr) + 1;
dvander@189:
dvander@193: if (trie->tail + len >= trie->stSize)
dvander@189: {
dvander@189: while (trie->tail + len >= trie->stSize)
dvander@189: {
dvander@189: trie->stSize *= 2;
dvander@189: }
dvander@189: trie->stringtab = (char *)realloc(trie->stringtab, trie->stSize);
dvander@189: }
dvander@189:
dvander@189: unsigned int tail = trie->tail;
dvander@189: strcpy(&trie->stringtab[tail], ptr);
dvander@189: trie->tail += len;
dvander@189:
dvander@189: return tail;
dvander@189: }
dvander@189:
dvander@189: Trie *sm_trie_create()
dvander@189: {
dvander@189: Trie *t = new Trie;
dvander@189:
dvander@193: t->base = (TrieNode *)malloc(sizeof(TrieNode) * (256 + 1));
dvander@189: t->stringtab = (char *)malloc(sizeof(char) * 256);
dvander@189: t->baseSize = 256;
dvander@189: t->stSize = 256;
dvander@335:
dvander@335: sm_trie_clear(t);
dvander@335:
dvander@335: return t;
dvander@335: }
dvander@189:
dvander@335: void sm_trie_clear(Trie *trie)
dvander@335: {
dvander@335: trie->tail = 0;
dvander@335:
dvander@335: memset(trie->base, 0, sizeof(TrieNode) * (trie->baseSize + 1));
dvander@335: memset(trie->stringtab, 0, sizeof(char) * trie->stSize);
dvander@189:
dvander@189: /* Sentinel root node */
dvander@335: trie->base[1].idx = 1;
dvander@335: trie->base[1].mode = Node_Arc;
dvander@335: trie->base[1].parent = 1;
dvander@189: }
dvander@189:
dvander@189: void sm_trie_destroy(Trie *trie)
dvander@189: {
dvander@189: free(trie->base);
dvander@189: free(trie->stringtab);
dvander@195: delete trie;
dvander@189: }
dvander@189:
dvander@211: bool sm_trie_delete(Trie *trie, const char *key)
dvander@211: {
dvander@211: unsigned int lastidx = 1; /* the last node index */
dvander@211: unsigned int curidx; /* current node index */
dvander@211: const char *keyptr = key; /* input stream at current token */
dvander@211: TrieNode *node = NULL; /* current node being processed */
dvander@211: TrieNode *base = trie->base;
dvander@211:
dvander@211: if (!*key)
dvander@211: {
dvander@211: return false;
dvander@211: }
dvander@211:
dvander@211: /* Start traversing at the root node */
dvander@211: do
dvander@211: {
dvander@211: /* Find where the next character is, then advance */
dvander@211: curidx = base[lastidx].idx;
dvander@211: node = &base[curidx];
dvander@211: curidx += charval(*keyptr);
dvander@211: node = &base[curidx];
dvander@211: keyptr++;
dvander@211:
dvander@211: /* Check if this slot is supposed to be empty or is a collision */
dvander@211: if ((curidx > trie->baseSize) || node->mode == Node_Unused || node->parent != lastidx)
dvander@211: {
dvander@211: return false;
dvander@211: } else if (node->mode == Node_Term) {
dvander@211: char *term = &trie->stringtab[node->idx];
dvander@211: if (strcmp(keyptr, term) == 0)
dvander@211: {
dvander@211: break;
dvander@211: }
dvander@211: }
dvander@211: lastidx = curidx;
dvander@211: } while (*keyptr != '\0');
dvander@211:
dvander@211: assert(node != NULL);
dvander@211:
dvander@211: if (!node->valset)
dvander@211: {
dvander@211: return false;
dvander@211: }
dvander@211:
dvander@211: node->valset = false;
dvander@211: node->value = NULL;
dvander@211:
dvander@211: return true;
dvander@211: }
dvander@211:
dvander@189: bool sm_trie_retrieve(Trie *trie, const char *key, void **value)
dvander@189: {
dvander@189: unsigned int lastidx = 1; /* the last node index */
dvander@189: unsigned int curidx; /* current node index */
dvander@189: const char *keyptr = key; /* input stream at current token */
dvander@189: TrieNode *node = NULL; /* current node being processed */
dvander@189: TrieNode *base = trie->base;
dvander@189:
dvander@189: if (!*key)
dvander@189: {
dvander@189: return false;
dvander@189: }
dvander@189:
dvander@189: /* Start traversing at the root node */
dvander@189: do
dvander@189: {
dvander@189: /* Find where the next character is, then advance */
dvander@189: curidx = base[lastidx].idx;
dvander@189: node = &base[curidx];
dvander@189: curidx += charval(*keyptr);
dvander@189: node = &base[curidx];
dvander@189: keyptr++;
dvander@189:
dvander@189: /* Check if this slot is supposed to be empty or is a collision */
dvander@194: if ((curidx > trie->baseSize) || node->mode == Node_Unused || node->parent != lastidx)
dvander@189: {
dvander@189: return false;
dvander@189: } else if (node->mode == Node_Term) {
dvander@189: char *term = &trie->stringtab[node->idx];
dvander@189: if (strcmp(keyptr, term) == 0)
dvander@189: {
dvander@189: break;
dvander@189: }
dvander@189: }
dvander@189: lastidx = curidx;
dvander@189: } while (*keyptr != '\0');
dvander@189:
dvander@189: assert(node != NULL);
dvander@189:
dvander@189: if (!node->valset)
dvander@189: {
dvander@189: return false;
dvander@189: }
dvander@189:
dvander@189: if (value)
dvander@189: {
dvander@189: *value = node->value;
dvander@189: }
dvander@189:
dvander@189: return true;
dvander@189: }
dvander@189:
dvander@1057: bool sm_trie_add(Trie *trie, const char *key, void *value, bool replace_allowed)
dvander@189: {
dvander@189: unsigned int lastidx = 1; /* the last node index */
dvander@189: unsigned int curidx; /* current node index */
dvander@189: const char *keyptr = key; /* input stream at current token */
dvander@189: TrieNode *node = NULL; /* current node being processed */
dvander@189: TrieNode *basenode = NULL; /* current base node being processed */
dvander@189: unsigned int q; /* temporary var for x_check results */
dvander@189: TrieNode *base = trie->base;
dvander@189: unsigned int curoffs; /* current offset */
dvander@189:
dvander@189: /* Do not handle empty strings for simplicity */
dvander@189: if (!*key)
dvander@189: {
dvander@189: return false;
dvander@189: }
dvander@189:
dvander@189: /* Start traversing at the root node (1) */
dvander@189: do
dvander@189: {
dvander@189: /* Find where the next character is, then advance */
dvander@189: curidx = base[lastidx].idx;
dvander@189: basenode = &base[curidx];
dvander@189: curoffs = charval(*keyptr);
dvander@189: curidx += curoffs;
dvander@189: node = &base[curidx];
dvander@189: keyptr++;
dvander@189:
dvander@189: /* Check if this slot is supposed to be empty. If so, we need to handle CASES 1/2:
dvander@189: * Insertion without collisions
dvander@189: */
dvander@194: if ( (curidx > trie->baseSize) || (node->mode == Node_Unused) )
dvander@189: {
dvander@194: if (curidx > trie->baseSize)
dvander@194: {
dvander@194: if (!sm_trie_grow(trie))
dvander@194: {
dvander@194: return false;
dvander@194: }
dvander@194: node = &trie->base[curidx];
dvander@194: }
dvander@189: node->parent = lastidx;
dvander@194: if (*keyptr == '\0')
dvander@194: {
dvander@194: node->mode = Node_Arc;
dvander@194: } else {
dvander@194: node->idx = x_addstring(trie, keyptr);
dvander@194: node->mode = Node_Term;
dvander@194: }
dvander@189: node->valset = true;
dvander@189: node->value = value;
dvander@189:
dvander@189: return true;
dvander@189: } else if (node->parent != lastidx) {
dvander@189: /* Collision! We have to split up the tree here. CASE 4:
dvander@189: * Insertion when a new word is inserted with a collision.
dvander@189: * NOTE: This is the hardest case to handle. All below examples are based on:
dvander@189: * BACHELOR, BADGE, inserting BABY.
dvander@189: * The problematic production here is A -> B, where B is already being used.
dvander@189: *
dvander@189: * This process has to rotate one half of the 'A' arc. We generate two lists:
dvander@189: * Outgoing Arcs - Anything leaving this 'A'
dvander@189: * Incoming Arcs - Anything going to this 'A'
dvander@189: * Whichever list is smaller will be moved. Note that this works because the intersection
dvander@189: * affects both arc chains, and moving one will make the slot available to either.
dvander@189: */
dvander@189: TrieNode *cur;
dvander@189:
dvander@189: /* Find every node arcing from the last node.
dvander@189: * I.e. for BACHELOR, BADGE, BABY,
dvander@189: * The arcs leaving A will be C and D, but our current node is B -> *.
dvander@189: * Thus, we use the last index (A) to find the base for arcs leaving A.
dvander@189: */
dvander@189: unsigned int outgoing_base = base[lastidx].idx;
dvander@189: unsigned int outgoing_list[256];
dvander@189: unsigned int outgoing_count = 0; /* count the current index here */
dvander@189: cur = &base[outgoing_base] + 1;
dvander@194: unsigned int outgoing_limit = 255;
dvander@194:
dvander@194: if (outgoing_base + outgoing_limit > trie->baseSize)
dvander@194: {
dvander@194: outgoing_limit = trie->baseSize - outgoing_base;
dvander@194: }
dvander@194:
dvander@194: for (unsigned int i=1; i<=outgoing_limit; i++,cur++)
dvander@189: {
dvander@189: if (cur->mode == Node_Unused || cur->parent != lastidx)
dvander@189: {
dvander@189: continue;
dvander@189: }
dvander@189: outgoing_list[outgoing_count++] = i;
dvander@189: }
dvander@189: outgoing_list[outgoing_count++] = curidx - outgoing_base;
dvander@189:
dvander@189: /* Now we need to find all the arcs leaving our parent...
dvander@189: * Note: the inconsistency is the base of our parent.
dvander@189: */
dvander@193: assert(base[node->parent].mode == Node_Arc);
dvander@189: unsigned int incoming_list[256];
dvander@189: unsigned int incoming_base = base[node->parent].idx;
dvander@189: unsigned int incoming_count = 0;
dvander@194: unsigned int incoming_limit = 255;
dvander@189: cur = &base[incoming_base] + 1;
dvander@194:
dvander@194: if (incoming_base + incoming_limit > trie->baseSize)
dvander@194: {
dvander@195: incoming_limit = trie->baseSize - incoming_base;
dvander@194: }
dvander@194:
dvander@195: assert(incoming_limit > 0 && incoming_limit <= 255);
dvander@195:
ds@1088: for (unsigned int i=1; i<=incoming_limit; i++,cur++)
dvander@189: {
dvander@189: if (cur->mode == Node_Arc || cur->mode == Node_Term)
dvander@189: {
dvander@189: if (cur->parent == node->parent)
dvander@189: {
dvander@189: incoming_list[incoming_count++] = i;
dvander@189: }
dvander@189: }
dvander@189: }
dvander@189:
dvander@189: if (incoming_count < outgoing_count + 1)
dvander@189: {
dvander@189: unsigned int q = x_check_multi(trie, incoming_list, incoming_count);
dvander@189:
dvander@193: base = trie->base;
dvander@193: node = &base[curidx];
dvander@193:
dvander@189: /* If we're incoming, we need to modify our parent */
dvander@193: base[node->parent].idx = q;
dvander@189:
dvander@189: /* For each node in the "to move" list,
dvander@189: * Relocate the node's info to the new position.
dvander@189: */
dvander@189: unsigned int idx, newidx, oldidx;
dvander@189: for (unsigned int i=0; ibaseSize + 1) - check_base;
dvander@1362: if (outgoing_limit > 255)
dvander@1362: {
dvander@1362: outgoing_limit = 255;
dvander@1362: }
dvander@1362: for (unsigned int j=1; j<=outgoing_limit; j++, check_base++)
dvander@189: {
dvander@189: if (check_base->parent == oldidx)
dvander@189: {
dvander@189: check_base->parent = newidx;
dvander@189: }
dvander@189: }
dvander@189: }
dvander@189: }
dvander@189: } else {
dvander@189: unsigned int q = x_check_multi(trie, outgoing_list, outgoing_count);
dvander@189:
dvander@193: base = trie->base;
dvander@193: node = &base[curidx];
dvander@193:
dvander@189: /* If we're outgoing, we need to modify our own base */
dvander@189: base[lastidx].idx = q;
dvander@189:
dvander@189: /* Take the last index (curidx) out of the list. Technically we are not moving this,
dvander@189: * since it's already being used by something else.
dvander@189: */
dvander@189: outgoing_count--;
dvander@189:
dvander@189: /* For each node in the "to move" list,
dvander@189: * Relocate the node's info to the new position.
dvander@189: */
dvander@189: unsigned int idx, newidx, oldidx;
dvander@189: for (unsigned int i=0; ibaseSize + 1) - check_base;
dvander@1362: if (outgoing_limit > 255)
dvander@1362: {
dvander@1362: outgoing_limit = 255;
dvander@1362: }
dvander@1362: for (unsigned int j=1; j<=outgoing_limit; j++, check_base++)
dvander@189: {
dvander@189: if (check_base->parent == oldidx)
dvander@189: {
dvander@189: check_base->parent = newidx;
dvander@189: }
dvander@189: }
dvander@189: }
dvander@189: }
dvander@189:
dvander@189: /* Take the invisible node and use it as our new node */
dvander@189: node = &base[q + outgoing_list[outgoing_count]];
dvander@189: }
dvander@189:
dvander@189: /* We're finally done! */
dvander@189: node->parent = lastidx;
dvander@189: if (*keyptr == '\0')
dvander@189: {
dvander@189: node->mode = Node_Arc;
dvander@189: } else {
dvander@189: node->idx = x_addstring(trie, keyptr);
dvander@189: node->mode = Node_Term;
dvander@189: }
dvander@189: node->valset = true;
dvander@189: node->value = value;
dvander@189:
dvander@189: return true;
dvander@189: } else {
dvander@189: /* See what's in the next node - special case if terminator! */
dvander@189: if (node->mode == Node_Term)
dvander@189: {
dvander@189: /* If we're a terminator, we need to handle CASE 3:
dvander@189: * Insertion when a terminating collision occurs
dvander@189: */
dvander@189: char *term = &trie->stringtab[node->idx];
dvander@189: /* Do an initial browsing to make sure they're not the same string */
dvander@189: if (strcmp(keyptr, term) == 0)
dvander@189: {
dvander@1060: if (!node->valset || replace_allowed)
faluco@216: {
faluco@216: node->valset = true;
faluco@216: node->value = value;
faluco@216: return true;
faluco@216: }
dvander@189: /* Same string. We can't insert. */
dvander@189: return false;
dvander@189: }
dvander@189: /* For each matching character pair, we need to disband the terminator.
dvander@189: * This splits the similar prefix into a single arc path.
dvander@189: * First, save the old values so we can move them to a new node.
dvander@189: * Next, for each loop:
dvander@189: * Take the current (invalid) node, and point it to the next arc base.
dvander@189: * Set the current node to the node at the next arc.
dvander@189: */
dvander@189: void *oldvalue = node->value;
dvander@189: bool oldvalset = node->valset;
dvander@193: if (*term == *keyptr)
dvander@193: {
dvander@189: while (*term == *keyptr)
dvander@189: {
dvander@189: /* Find the next free slot in the check array.
dvander@189: * This is the "vector base" essentially
dvander@189: */
dvander@189: q = x_check(trie, *term);
dvander@193: base = trie->base;
dvander@193: node = &base[curidx];
dvander@189: /* Point the node to the next new base */
dvander@189: node->idx = q;
dvander@189: node->mode = Node_Arc;
dvander@189: node->valset = false;
dvander@189: /* Advance the input stream and local variables */
dvander@189: lastidx = curidx;
dvander@189: curidx = q + charval(*term);
dvander@189: node = &base[curidx];
dvander@189: /* Make sure the new current node has its parent set. */
dvander@189: node->parent = lastidx;
dvander@189: node->mode = Node_Arc; /* Just in case we run x_check again */
dvander@189: *term = '\0'; /* Unmark the string table here */
dvander@189: term++;
dvander@189: keyptr++;
dvander@193: }
dvander@193: } else {
dvander@193: node->valset = false;
dvander@189: }
dvander@189: /* We're done inserting new pairs. If one of them is exhausted,
dvander@189: * we take special shortcuts.
dvander@189: */
dvander@189: if (*term == '\0') //EX: BADGERHOUSE added over B -> ADGER.
dvander@189: {
dvander@189: /* First backpatch the current node - it ends the newly split terminator.
dvander@189: * In the example, this would mean the node is the production from R -> ?
dvander@189: * This node ends the old BADGER, so we set it here.
dvander@189: */
dvander@189: node->valset = oldvalset;
dvander@189: node->value = oldvalue;
dvander@189:
dvander@189: /* The terminator was split up, but pieces of keyptr remain.
dvander@189: * We need to generate a new production, in this example, R -> H,
dvander@189: * with H being a terminator to OUSE. Thus we get:
dvander@189: * B,A,D,G,E,R*,H*->OUSE (* = value set).
dvander@189: * NOTE: parent was last set at the end of the while loop.
dvander@189: */
dvander@193: /* Get the new base and apply re-basing */
dvander@189: q = x_check(trie, *keyptr);
dvander@193: base = trie->base;
dvander@193: node = &base[curidx];
dvander@193:
dvander@189: node->idx = q;
dvander@189: node->mode = Node_Arc;
dvander@189: lastidx = curidx;
dvander@189: /* Finish the final node */
dvander@189: curidx = q + charval(*keyptr);
dvander@189: node = &trie->base[curidx];
dvander@189: keyptr++;
dvander@189: /* Optimize - don't add to string table if there's nothing more to eat */
dvander@189: if (*keyptr == '\0')
dvander@189: {
dvander@189: node->mode = Node_Arc;
dvander@189: } else {
dvander@189: node->idx = x_addstring(trie, keyptr);
dvander@189: node->mode = Node_Term;
dvander@189: }
dvander@189: node->parent = lastidx;
dvander@189: node->valset = true;
dvander@189: node->value = value;
dvander@189: } else if (*keyptr == '\0') { //EX: BADGER added over B -> ADGERHOUSE
dvander@189: /* First backpatch the current node - it ends newly split input string.
dvander@189: * This is the exact opposite of the above procedure.
dvander@189: */
dvander@189: node->valset = true;
dvander@189: node->value = value;
dvander@189:
dvander@193: /* Get the new base and apply re-basing */
dvander@189: q = x_check(trie, *term);
dvander@193: base = trie->base;
dvander@193: node = &base[curidx];
dvander@193:
dvander@189: node->idx = q;
dvander@189: node->mode = Node_Arc;
dvander@189: lastidx = curidx;
dvander@189: /* Finish the final node */
dvander@189: curidx = q + charval(*term);
dvander@189: node = &trie->base[curidx];
dvander@189: term++;
dvander@189: /* Optimize - don't add to string table if there's nothing more to eat */
dvander@189: if (*term == '\0')
dvander@189: {
dvander@189: node->mode = Node_Arc;
dvander@189: } else {
dvander@189: node->idx = (term - trie->stringtab); /* Already in the string table! */
dvander@189: node->mode = Node_Term;
dvander@189: }
dvander@189: node->parent = lastidx;
dvander@189: node->valset = oldvalset;
dvander@189: node->value = oldvalue;
dvander@189: } else {
dvander@189: /* Finally, we have to create two new nodes instead of just one. */
dvander@189: node->mode = Node_Arc;
dvander@189:
dvander@193: /* Get the new base and apply re-basing */
dvander@189: q = x_check2(trie, *keyptr, *term);
dvander@193: base = trie->base;
dvander@193: node = &base[curidx];
dvander@193:
dvander@189: node->idx = q;
dvander@189: lastidx = curidx;
dvander@189:
dvander@189: /* Re-create the old terminated node */
dvander@189: curidx = q + charval(*term);
dvander@189: node = &trie->base[curidx];
dvander@189: term++;
dvander@189: node->valset = oldvalset;
dvander@189: node->value = oldvalue;
dvander@189: node->parent = lastidx;
dvander@189: if (*term == '\0')
dvander@189: {
dvander@189: node->mode = Node_Arc;
dvander@189: } else {
dvander@189: node->mode = Node_Term;
dvander@189: node->idx = (term - trie->stringtab); /* Already in the string table! */
dvander@189: }
dvander@189:
dvander@189: /* Create the new keyed input node */
dvander@189: curidx = q + charval(*keyptr);
dvander@189: node = &trie->base[curidx];
dvander@189: keyptr++;
dvander@189: node->valset = true;
dvander@189: node->value = value;
dvander@189: node->parent = lastidx;
dvander@189: if (*keyptr == '\0')
dvander@189: {
dvander@189: node->mode = Node_Arc;
dvander@189: } else {
dvander@189: node->mode = Node_Term;
dvander@189: node->idx = x_addstring(trie, keyptr);
dvander@189: }
dvander@189: }
dvander@189:
dvander@189: /* Phew! */
dvander@189: return true;
dvander@195: } else {
dvander@195: assert(node->mode == Node_Arc);
dvander@189: }
dvander@189: }
dvander@189: lastidx = curidx;
dvander@189: } while (*keyptr != '\0');
dvander@189:
dvander@189: assert(node);
dvander@189:
dvander@189: /* If we've exhausted the string and we have a valid reached node,
dvander@189: * the production rule already existed. Make sure it's valid to set first.
dvander@189: */
dvander@189:
dvander@189: /* We have to be an Arc. If the last result was anything else, we would have returned a new
dvander@189: * production earlier.
dvander@189: */
dvander@189: assert(node->mode == Node_Arc);
dvander@189:
dvander@1057: if (!node->valset || replace_allowed)
dvander@189: {
dvander@189: /* Insert is only possible if we have no production */
dvander@189: node->valset = true;
dvander@189: node->value = value;
dvander@189: return true;
dvander@189: }
dvander@189:
dvander@189: return false;
dvander@189: }
dvander@1057:
dvander@1057: bool sm_trie_insert(Trie *trie, const char *key, void *value)
dvander@1057: {
dvander@1057: return sm_trie_add(trie, key, value, false);
dvander@1057: }
dvander@1057:
dvander@1057: bool sm_trie_replace(Trie *trie, const char *key, void *value)
dvander@1057: {
dvander@1057: return sm_trie_add(trie, key, value, true);
dvander@1057: }