1.1 --- a/core/sm_trie.cpp Wed Aug 29 05:20:48 2007 +0000
1.2 +++ b/core/sm_trie.cpp Wed Aug 29 05:22:47 2007 +0000
1.3 @@ -31,8 +31,8 @@
1.4
1.5 #include <string.h>
1.6 #include <assert.h>
1.7 +#include <sm_trie_tpl.h>
1.8 #include "sm_trie.h"
1.9 -#include "sm_trie_tpl.h"
1.10
1.11 struct Trie
1.12 {
2.1 --- a/core/sm_trie_tpl.h Wed Aug 29 05:20:48 2007 +0000
2.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
2.3 @@ -1,898 +0,0 @@
2.4 -/**
2.5 - * vim: set ts=4 :
2.6 - * =============================================================================
2.7 - * SourceMod
2.8 - * Copyright (C) 2004-2007 AlliedModders LLC. All rights reserved.
2.9 - * =============================================================================
2.10 - *
2.11 - * This program is free software; you can redistribute it and/or modify it under
2.12 - * the terms of the GNU General Public License, version 3.0, as published by the
2.13 - * Free Software Foundation.
2.14 - *
2.15 - * This program is distributed in the hope that it will be useful, but WITHOUT
2.16 - * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
2.17 - * FOR A PARTICULAR PURPOSE. See the GNU General Public License for more
2.18 - * details.
2.19 - *
2.20 - * You should have received a copy of the GNU General Public License along with
2.21 - * this program. If not, see <http://www.gnu.org/licenses/>.
2.22 - *
2.23 - * As a special exception, AlliedModders LLC gives you permission to link the
2.24 - * code of this program (as well as its derivative works) to "Half-Life 2," the
2.25 - * "Source Engine," the "SourcePawn JIT," and any Game MODs that run on software
2.26 - * by the Valve Corporation. You must obey the GNU General Public License in
2.27 - * all respects for all other code used. Additionally, AlliedModders LLC grants
2.28 - * this exception to all derivative works. AlliedModders LLC defines further
2.29 - * exceptions, found in LICENSE.txt (as of this writing, version JULY-31-2007),
2.30 - * or <http://www.sourcemod.net/license.php>.
2.31 - *
2.32 - * Version: $Id$
2.33 - */
2.34 -
2.35 -#ifndef _INCLUDE_SOURCEMOD_TEMPLATED_TRIE_H_
2.36 -#define _INCLUDE_SOURCEMOD_TEMPLATED_TRIE_H_
2.37 -
2.38 -#include <new>
2.39 -#include <string.h>
2.40 -#include <malloc.h>
2.41 -#include <assert.h>
2.42 -
2.43 -enum NodeType
2.44 -{
2.45 - Node_Unused = 0, /* Node is not being used (sparse) */
2.46 - Node_Arc, /* Node is part of an arc and does not terminate */
2.47 - Node_Term, /* Node is a terminator */
2.48 -};
2.49 -
2.50 -/**
2.51 - * @brief Trie algorithm based on "Double Array Trie" algorith.
2.52 - * @file sm_trie_tpl.h
2.53 - *
2.54 - * For full works cited and implementation overview, there is a big comment
2.55 - * block at the bottom of this file.
2.56 - */
2.57 -
2.58 -template <typename K>
2.59 -class KTrie
2.60 -{
2.61 - class KTrieNode;
2.62 -public:
2.63 - /**
2.64 - * @brief Clears all set objects in the trie.
2.65 - */
2.66 - void clear()
2.67 - {
2.68 - run_destructors();
2.69 - internal_clear();
2.70 - }
2.71 -
2.72 - /**
2.73 - * @brief Removes a key from the trie.
2.74 - *
2.75 - * @param key Key to remove.
2.76 - * @return True on success, false if key was never set.
2.77 - */
2.78 - bool remove(const char *key)
2.79 - {
2.80 - KTrieNode *node = internal_retrieve(key);
2.81 - if (!node || !node->valset)
2.82 - {
2.83 - return false;
2.84 - }
2.85 -
2.86 - node->value.~K();
2.87 - node->valset = false;
2.88 -
2.89 - return true;
2.90 - }
2.91 -
2.92 - /**
2.93 - * @brief Retrieves a pointer to the object stored at a given key.
2.94 - *
2.95 - * @param key Key to retrieve.
2.96 - * @return Pointer to object, or NULL if key was not found or not set.
2.97 - */
2.98 - K * retrieve(const char *key)
2.99 - {
2.100 - KTrieNode *node = internal_retrieve(key);
2.101 - if (!node || !node->valset)
2.102 - {
2.103 - return NULL;
2.104 - }
2.105 - return &node->value;
2.106 - }
2.107 -
2.108 - /**
2.109 - * @brief Inserts or updates the object stored at a key.
2.110 - *
2.111 - * @param key Key to update or insert.
2.112 - * @param obj Object to store at the key.
2.113 - * @return True on success, false on failure.
2.114 - */
2.115 - bool replace(const char *key, const K & obj)
2.116 - {
2.117 - KTrieNode *prev_node = internal_retrieve(key);
2.118 - if (!prev_node)
2.119 - {
2.120 - return insert(key, obj);
2.121 - }
2.122 -
2.123 - if (prev_node->valset)
2.124 - {
2.125 - prev_node->value.~K();
2.126 - }
2.127 -
2.128 - new (&prev_node->value) K(obj);
2.129 -
2.130 - return true;
2.131 - }
2.132 -
2.133 - /**
2.134 - * @brief Inserts an object at a key.
2.135 - *
2.136 - * @param key Key to insert at.
2.137 - * @param obj Object to store at the key.
2.138 - * @return True on success, false if the key is already set or
2.139 - * insertion otherwise failed.
2.140 - */
2.141 - bool insert(const char *key, const K & obj)
2.142 - {
2.143 - unsigned int lastidx = 1; /* the last node index */
2.144 - unsigned int curidx; /* current node index */
2.145 - const char *keyptr = key; /* input stream at current token */
2.146 - KTrieNode *node = NULL; /* current node being processed */
2.147 - KTrieNode *basenode = NULL; /* current base node being processed */
2.148 - unsigned int q; /* temporary var for x_check results */
2.149 - unsigned int curoffs; /* current offset */
2.150 -
2.151 - /* Do not handle empty strings for simplicity */
2.152 - if (!*key)
2.153 - {
2.154 - return false;
2.155 - }
2.156 -
2.157 - /* Start traversing at the root node (1) */
2.158 - do
2.159 - {
2.160 - /* Find where the next character is, then advance */
2.161 - curidx = m_base[lastidx].idx;
2.162 - basenode = &m_base[curidx];
2.163 - curoffs = charval(*keyptr);
2.164 - curidx += curoffs;
2.165 - node = &m_base[curidx];
2.166 - keyptr++;
2.167 -
2.168 - /* Check if this slot is supposed to be empty. If so, we need to handle CASES 1/2:
2.169 - * Insertion without collisions
2.170 - */
2.171 - if ( (curidx > m_baseSize) || (node->mode == Node_Unused) )
2.172 - {
2.173 - if (curidx > m_baseSize)
2.174 - {
2.175 - if (!grow())
2.176 - {
2.177 - return false;
2.178 - }
2.179 - node = &m_base[curidx];
2.180 - }
2.181 - node->parent = lastidx;
2.182 - if (*keyptr == '\0')
2.183 - {
2.184 - node->mode = Node_Arc;
2.185 - } else {
2.186 - node->idx = x_addstring(keyptr);
2.187 - node->mode = Node_Term;
2.188 - }
2.189 - node->valset = true;
2.190 - new (&node->value) K(obj);
2.191 -
2.192 - return true;
2.193 - } else if (node->parent != lastidx) {
2.194 - /* Collision! We have to split up the tree here. CASE 4:
2.195 - * Insertion when a new word is inserted with a collision.
2.196 - * NOTE: This is the hardest case to handle. All below examples are based on:
2.197 - * BACHELOR, BADGE, inserting BABY.
2.198 - * The problematic production here is A -> B, where B is already being used.
2.199 - *
2.200 - * This process has to rotate one half of the 'A' arc. We generate two lists:
2.201 - * Outgoing Arcs - Anything leaving this 'A'
2.202 - * Incoming Arcs - Anything going to this 'A'
2.203 - * Whichever list is smaller will be moved. Note that this works because the intersection
2.204 - * affects both arc chains, and moving one will make the slot available to either.
2.205 - */
2.206 - KTrieNode *cur;
2.207 -
2.208 - /* Find every node arcing from the last node.
2.209 - * I.e. for BACHELOR, BADGE, BABY,
2.210 - * The arcs leaving A will be C and D, but our current node is B -> *.
2.211 - * Thus, we use the last index (A) to find the base for arcs leaving A.
2.212 - */
2.213 - unsigned int outgoing_base = m_base[lastidx].idx;
2.214 - unsigned int outgoing_list[256];
2.215 - unsigned int outgoing_count = 0; /* count the current index here */
2.216 - cur = &m_base[outgoing_base] + 1;
2.217 - unsigned int outgoing_limit = 255;
2.218 -
2.219 - if (outgoing_base + outgoing_limit > m_baseSize)
2.220 - {
2.221 - outgoing_limit = m_baseSize - outgoing_base;
2.222 - }
2.223 -
2.224 - for (unsigned int i=1; i<=outgoing_limit; i++,cur++)
2.225 - {
2.226 - if (cur->mode == Node_Unused || cur->parent != lastidx)
2.227 - {
2.228 - continue;
2.229 - }
2.230 - outgoing_list[outgoing_count++] = i;
2.231 - }
2.232 - outgoing_list[outgoing_count++] = curidx - outgoing_base;
2.233 -
2.234 - /* Now we need to find all the arcs leaving our parent...
2.235 - * Note: the inconsistency is the base of our parent.
2.236 - */
2.237 - assert(m_base[node->parent].mode == Node_Arc);
2.238 - unsigned int incoming_list[256];
2.239 - unsigned int incoming_base = m_base[node->parent].idx;
2.240 - unsigned int incoming_count = 0;
2.241 - unsigned int incoming_limit = 255;
2.242 - cur = &m_base[incoming_base] + 1;
2.243 -
2.244 - if (incoming_base + incoming_limit > m_baseSize)
2.245 - {
2.246 - incoming_limit = m_baseSize - incoming_base;
2.247 - }
2.248 -
2.249 - assert(incoming_limit > 0 && incoming_limit <= 255);
2.250 -
2.251 - for (unsigned int i=1; i<=incoming_limit; i++,cur++)
2.252 - {
2.253 - if (cur->mode == Node_Arc || cur->mode == Node_Term)
2.254 - {
2.255 - if (cur->parent == node->parent)
2.256 - {
2.257 - incoming_list[incoming_count++] = i;
2.258 - }
2.259 - }
2.260 - }
2.261 -
2.262 - if (incoming_count < outgoing_count + 1)
2.263 - {
2.264 - unsigned int q = x_check_multi(incoming_list, incoming_count);
2.265 -
2.266 - node = &m_base[curidx];
2.267 -
2.268 - /* If we're incoming, we need to modify our parent */
2.269 - m_base[node->parent].idx = q;
2.270 -
2.271 - /* For each node in the "to move" list,
2.272 - * Relocate the node's info to the new position.
2.273 - */
2.274 - unsigned int idx, newidx, oldidx;
2.275 - for (unsigned int i=0; i<incoming_count; i++)
2.276 - {
2.277 - idx = incoming_list[i];
2.278 - newidx = q + idx;
2.279 - oldidx = incoming_base + idx;
2.280 - if (oldidx == lastidx)
2.281 - {
2.282 - /* Important! Make sure we're not invalidating our sacred lastidx */
2.283 - lastidx = newidx;
2.284 - }
2.285 - /* Fully copy the node */
2.286 - memcpy(&m_base[newidx], &m_base[oldidx], sizeof(KTrieNode));
2.287 - if (m_base[oldidx].valset)
2.288 - {
2.289 - new (&m_base[newidx].value) K(m_base[oldidx].value);
2.290 - m_base[oldidx].value.~K();
2.291 - }
2.292 - assert(m_base[m_base[newidx].parent].mode == Node_Arc);
2.293 - /* Erase old data */
2.294 - memset(&m_base[oldidx], 0, sizeof(KTrieNode));
2.295 - /* If we are not a terminator, we have children we must take care of */
2.296 - if (m_base[newidx].mode == Node_Arc)
2.297 - {
2.298 - KTrieNode *check_base = &m_base[m_base[newidx].idx] + 1;
2.299 - outgoing_limit = (m_base + m_baseSize + 1) - check_base;
2.300 - if (outgoing_limit > 255)
2.301 - {
2.302 - outgoing_limit = 255;
2.303 - }
2.304 - for (unsigned int j=1; j<=outgoing_limit; j++, check_base++)
2.305 - {
2.306 - if (check_base->parent == oldidx)
2.307 - {
2.308 - check_base->parent = newidx;
2.309 - }
2.310 - }
2.311 - }
2.312 - }
2.313 - } else {
2.314 - unsigned int q = x_check_multi(outgoing_list, outgoing_count);
2.315 -
2.316 - node = &m_base[curidx];
2.317 -
2.318 - /* If we're outgoing, we need to modify our own base */
2.319 - m_base[lastidx].idx = q;
2.320 -
2.321 - /* Take the last index (curidx) out of the list. Technically we are not moving this,
2.322 - * since it's already being used by something else.
2.323 - */
2.324 - outgoing_count--;
2.325 -
2.326 - /* For each node in the "to move" list,
2.327 - * Relocate the node's info to the new position.
2.328 - */
2.329 - unsigned int idx, newidx, oldidx;
2.330 - for (unsigned int i=0; i<outgoing_count; i++)
2.331 - {
2.332 - idx = outgoing_list[i];
2.333 - newidx = q + idx;
2.334 - oldidx = outgoing_base + idx;
2.335 - if (oldidx == lastidx)
2.336 - {
2.337 - /* Important! Make sure we're not invalidating our sacred lastidx */
2.338 - lastidx = newidx;
2.339 - }
2.340 - /* Fully copy the node */
2.341 - memcpy(&m_base[newidx], &m_base[oldidx], sizeof(KTrieNode));
2.342 - if (m_base[oldidx].valset)
2.343 - {
2.344 - new (&m_base[newidx].value) K(m_base[oldidx].value);
2.345 - m_base[oldidx].value.~K();
2.346 - }
2.347 - assert(m_base[m_base[newidx].parent].mode == Node_Arc);
2.348 - /* Erase old data */
2.349 - memset(&m_base[oldidx], 0, sizeof(KTrieNode));
2.350 - /* If we are not a terminator, we have children we must take care of */
2.351 - if (m_base[newidx].mode == Node_Arc)
2.352 - {
2.353 - KTrieNode *check_base = &m_base[m_base[newidx].idx] + 1;
2.354 - outgoing_limit = (m_base + m_baseSize + 1) - check_base;
2.355 - if (outgoing_limit > 255)
2.356 - {
2.357 - outgoing_limit = 255;
2.358 - }
2.359 - for (unsigned int j=1; j<=outgoing_limit; j++, check_base++)
2.360 - {
2.361 - if (check_base->parent == oldidx)
2.362 - {
2.363 - check_base->parent = newidx;
2.364 - }
2.365 - }
2.366 - }
2.367 - }
2.368 -
2.369 - /* Take the invisible node and use it as our new node */
2.370 - node = &m_base[q + outgoing_list[outgoing_count]];
2.371 - }
2.372 -
2.373 - /* We're finally done! */
2.374 - node->parent = lastidx;
2.375 - if (*keyptr == '\0')
2.376 - {
2.377 - node->mode = Node_Arc;
2.378 - } else {
2.379 - node->idx = x_addstring(keyptr);
2.380 - node->mode = Node_Term;
2.381 - }
2.382 - node->valset = true;
2.383 - new (&node->value) K(obj);
2.384 -
2.385 - return true;
2.386 - } else {
2.387 - /* See what's in the next node - special case if terminator! */
2.388 - if (node->mode == Node_Term)
2.389 - {
2.390 - /* If we're a terminator, we need to handle CASE 3:
2.391 - * Insertion when a terminating collision occurs
2.392 - */
2.393 - char *term = &m_stringtab[node->idx];
2.394 - /* Do an initial browsing to make sure they're not the same string */
2.395 - if (strcmp(keyptr, term) == 0)
2.396 - {
2.397 - if (!node->valset)
2.398 - {
2.399 - node->valset = true;
2.400 - new (&node->value) K(obj);
2.401 - return true;
2.402 - }
2.403 - /* Same string. We can't insert. */
2.404 - return false;
2.405 - }
2.406 - /* For each matching character pair, we need to disband the terminator.
2.407 - * This splits the similar prefix into a single arc path.
2.408 - * First, save the old values so we can move them to a new node.
2.409 - * Next, for each loop:
2.410 - * Take the current (invalid) node, and point it to the next arc base.
2.411 - * Set the current node to the node at the next arc.
2.412 - */
2.413 - K oldvalue;
2.414 - bool oldvalset = node->valset;
2.415 - if (oldvalset)
2.416 - {
2.417 - oldvalue = node->value;
2.418 - }
2.419 - if (*term == *keyptr)
2.420 - {
2.421 - while (*term == *keyptr)
2.422 - {
2.423 - /* Find the next free slot in the check array.
2.424 - * This is the "vector base" essentially
2.425 - */
2.426 - q = x_check(*term);
2.427 - node = &m_base[curidx];
2.428 - /* Point the node to the next new base */
2.429 - node->idx = q;
2.430 - node->mode = Node_Arc;
2.431 - if (node->valset == true)
2.432 - {
2.433 - node->value.~K();
2.434 - node->valset = false;
2.435 - }
2.436 - /* Advance the input stream and local variables */
2.437 - lastidx = curidx;
2.438 - curidx = q + charval(*term);
2.439 - node = &m_base[curidx];
2.440 - /* Make sure the new current node has its parent set. */
2.441 - node->parent = lastidx;
2.442 - node->mode = Node_Arc; /* Just in case we run x_check again */
2.443 - *term = '\0'; /* Unmark the string table here */
2.444 - term++;
2.445 - keyptr++;
2.446 - }
2.447 - } else if (node->valset) {
2.448 - node->valset = false;
2.449 - node->value.~K();
2.450 - }
2.451 - /* We're done inserting new pairs. If one of them is exhausted,
2.452 - * we take special shortcuts.
2.453 - */
2.454 - if (*term == '\0') //EX: BADGERHOUSE added over B -> ADGER.
2.455 - {
2.456 - /* First backpatch the current node - it ends the newly split terminator.
2.457 - * In the example, this would mean the node is the production from R -> ?
2.458 - * This node ends the old BADGER, so we set it here.
2.459 - */
2.460 - node->valset = oldvalset;
2.461 - if (node->valset)
2.462 - {
2.463 - new (&node->value) K(oldvalue);
2.464 - }
2.465 -
2.466 - /* The terminator was split up, but pieces of keyptr remain.
2.467 - * We need to generate a new production, in this example, R -> H,
2.468 - * with H being a terminator to OUSE. Thus we get:
2.469 - * B,A,D,G,E,R*,H*->OUSE (* = value set).
2.470 - * NOTE: parent was last set at the end of the while loop.
2.471 - */
2.472 - /* Get the new base and apply re-basing */
2.473 - q = x_check(*keyptr);
2.474 - node = &m_base[curidx];
2.475 -
2.476 - node->idx = q;
2.477 - node->mode = Node_Arc;
2.478 - lastidx = curidx;
2.479 - /* Finish the final node */
2.480 - curidx = q + charval(*keyptr);
2.481 - node = &m_base[curidx];
2.482 - keyptr++;
2.483 - /* Optimize - don't add to string table if there's nothing more to eat */
2.484 - if (*keyptr == '\0')
2.485 - {
2.486 - node->mode = Node_Arc;
2.487 - } else {
2.488 - node->idx = x_addstring(keyptr);
2.489 - node->mode = Node_Term;
2.490 - }
2.491 - node->parent = lastidx;
2.492 - node->valset = true;
2.493 - new (&node->value) K(obj);
2.494 - } else if (*keyptr == '\0') { //EX: BADGER added over B -> ADGERHOUSE
2.495 - /* First backpatch the current node - it ends newly split input string.
2.496 - * This is the exact opposite of the above procedure.
2.497 - */
2.498 - node->valset = true;
2.499 - new (&node->value) K(obj);
2.500 -
2.501 - /* Get the new base and apply re-basing */
2.502 - q = x_check(*term);
2.503 - node = &m_base[curidx];
2.504 -
2.505 - node->idx = q;
2.506 - node->mode = Node_Arc;
2.507 - lastidx = curidx;
2.508 - /* Finish the final node */
2.509 - curidx = q + charval(*term);
2.510 - node = &m_base[curidx];
2.511 - term++;
2.512 - /* Optimize - don't add to string table if there's nothing more to eat */
2.513 - if (*term == '\0')
2.514 - {
2.515 - node->mode = Node_Arc;
2.516 - } else {
2.517 - node->idx = (term - m_stringtab); /* Already in the string table! */
2.518 - node->mode = Node_Term;
2.519 - }
2.520 - node->parent = lastidx;
2.521 - node->valset = oldvalset;
2.522 - if (node->valset)
2.523 - {
2.524 - new (&node->value) K(oldvalue);
2.525 - }
2.526 - } else {
2.527 - /* Finally, we have to create two new nodes instead of just one. */
2.528 - node->mode = Node_Arc;
2.529 -
2.530 - /* Get the new base and apply re-basing */
2.531 - q = x_check2(*keyptr, *term);
2.532 - node = &m_base[curidx];
2.533 -
2.534 - node->idx = q;
2.535 - lastidx = curidx;
2.536 -
2.537 - /* Re-create the old terminated node */
2.538 - curidx = q + charval(*term);
2.539 - node = &m_base[curidx];
2.540 - term++;
2.541 - node->valset = oldvalset;
2.542 - if (node->valset)
2.543 - {
2.544 - new (&node->value) K(oldvalue);
2.545 - }
2.546 - node->parent = lastidx;
2.547 - if (*term == '\0')
2.548 - {
2.549 - node->mode = Node_Arc;
2.550 - } else {
2.551 - node->mode = Node_Term;
2.552 - node->idx = (term - m_stringtab); /* Already in the string table! */
2.553 - }
2.554 -
2.555 - /* Create the new keyed input node */
2.556 - curidx = q + charval(*keyptr);
2.557 - node = &m_base[curidx];
2.558 - keyptr++;
2.559 - node->valset = true;
2.560 - new (&node->value) K(obj);
2.561 - node->parent = lastidx;
2.562 - if (*keyptr == '\0')
2.563 - {
2.564 - node->mode = Node_Arc;
2.565 - } else {
2.566 - node->mode = Node_Term;
2.567 - node->idx = x_addstring(keyptr);
2.568 - }
2.569 - }
2.570 -
2.571 - /* Phew! */
2.572 - return true;
2.573 - } else {
2.574 - assert(node->mode == Node_Arc);
2.575 - }
2.576 - }
2.577 - lastidx = curidx;
2.578 - } while (*keyptr != '\0');
2.579 -
2.580 - assert(node);
2.581 -
2.582 - /* If we've exhausted the string and we have a valid reached node,
2.583 - * the production rule already existed. Make sure it's valid to set first.
2.584 - */
2.585 -
2.586 - /* We have to be an Arc. If the last result was anything else, we would have returned a new
2.587 - * production earlier.
2.588 - */
2.589 - assert(node->mode == Node_Arc);
2.590 -
2.591 - if (!node->valset)
2.592 - {
2.593 - node->valset = true;
2.594 - new (&node->value) K(obj);
2.595 - return true;
2.596 - }
2.597 -
2.598 - return false;
2.599 - }
2.600 -public:
2.601 - KTrie()
2.602 - {
2.603 - m_base = (KTrieNode *)malloc(sizeof(KTrieNode) * (256 + 1));
2.604 - m_stringtab = (char *)malloc(sizeof(char) * 256);
2.605 - m_baseSize = 256;
2.606 - m_stSize = 256;
2.607 -
2.608 - internal_clear();
2.609 - }
2.610 - ~KTrie()
2.611 - {
2.612 - run_destructors();
2.613 - free(m_base);
2.614 - free(m_stringtab);
2.615 - }
2.616 -private:
2.617 - class KTrieNode
2.618 - {
2.619 - friend class KTrie;
2.620 - private:
2.621 - /**
2.622 - * For Node_Arc, this index stores the 'base' offset to the next arc chain.
2.623 - * I.e. to jump from this arc to character C, it will be at base[idx+C].
2.624 - * For Node_Term, this is an index into the string table.
2.625 - */
2.626 - unsigned int idx;
2.627 -
2.628 - /**
2.629 - * This contains the prior arc that we must have come from.
2.630 - * For example, if arc 63 has a base jump of index 12, and we want to see if
2.631 - * there is a valid character C, the parent of 12+C must be 63.
2.632 - */
2.633 - unsigned int parent;
2.634 - K value; /* Value associated with this node */
2.635 - NodeType mode; /* Current usage type of the node */
2.636 - bool valset; /* Whether or not a value is set */
2.637 - };
2.638 -private:
2.639 - KTrieNode *internal_retrieve(const char *key)
2.640 - {
2.641 - unsigned int lastidx = 1; /* the last node index */
2.642 - unsigned int curidx; /* current node index */
2.643 - const char *keyptr = key; /* input stream at current token */
2.644 - KTrieNode *node = NULL; /* current node being processed */
2.645 -
2.646 - if (!*key)
2.647 - {
2.648 - return NULL;
2.649 - }
2.650 -
2.651 - /* Start traversing at the root node */
2.652 - do
2.653 - {
2.654 - /* Find where the next character is, then advance */
2.655 - curidx = m_base[lastidx].idx;
2.656 - node = &m_base[curidx];
2.657 - curidx += charval(*keyptr);
2.658 - node = &m_base[curidx];
2.659 - keyptr++;
2.660 -
2.661 - /* Check if this slot is supposed to be empty or is a collision */
2.662 - if ((curidx > m_baseSize) || node->mode == Node_Unused || node->parent != lastidx)
2.663 - {
2.664 - return NULL;
2.665 - } else if (node->mode == Node_Term) {
2.666 - char *term = &m_stringtab[node->idx];
2.667 - if (strcmp(keyptr, term) == 0)
2.668 - {
2.669 - break;
2.670 - }
2.671 - }
2.672 - lastidx = curidx;
2.673 - } while (*keyptr != '\0');
2.674 -
2.675 - return node;
2.676 - }
2.677 - bool grow()
2.678 - {
2.679 - /* The current # of nodes in the tree is trie->baseSize + 1 */
2.680 - unsigned int cur_size = m_baseSize;
2.681 - unsigned int new_size = cur_size * 2;
2.682 -
2.683 - KTrieNode *new_base = (KTrieNode *)malloc((new_size + 1) * sizeof(KTrieNode));
2.684 - if (!new_base)
2.685 - {
2.686 - return false;
2.687 - }
2.688 -
2.689 - memcpy(new_base, m_base, sizeof(KTrieNode) * (m_baseSize + 1));
2.690 - memset(&new_base[cur_size + 1], 0, (new_size - cur_size) * sizeof(KTrieNode));
2.691 -
2.692 - for (size_t i = 0; i <= m_baseSize; i++)
2.693 - {
2.694 - if (m_base[i].valset)
2.695 - {
2.696 - /* Placement construct+copy the object, then placement destroy the old. */
2.697 - new (&new_base[i].value) K(m_base[i].value);
2.698 - m_base[i].value.~K();
2.699 - }
2.700 - }
2.701 -
2.702 - free(m_base);
2.703 - m_base = new_base;
2.704 - m_baseSize = new_size;
2.705 -
2.706 - return true;
2.707 - }
2.708 - inline unsigned char charval(char c)
2.709 - {
2.710 - return (unsigned char)c;
2.711 - }
2.712 - void internal_clear()
2.713 - {
2.714 - m_tail = 0;
2.715 -
2.716 - memset(m_base, 0, sizeof(KTrieNode) * (m_baseSize + 1));
2.717 - memset(m_stringtab, 0, sizeof(char) * m_stSize);
2.718 -
2.719 - /* Sentinel root node */
2.720 - m_base[1].idx = 1;
2.721 - m_base[1].mode = Node_Arc;
2.722 - m_base[1].parent = 1;
2.723 - }
2.724 - void run_destructors()
2.725 - {
2.726 - for (size_t i = 0; i <= m_baseSize; i++)
2.727 - {
2.728 - if (m_base[i].valset)
2.729 - {
2.730 - m_base[i].value.~K();
2.731 - }
2.732 - }
2.733 - }
2.734 - unsigned int x_addstring(const char *ptr)
2.735 - {
2.736 - size_t len = strlen(ptr) + 1;
2.737 -
2.738 - if (m_tail + len >= m_stSize)
2.739 - {
2.740 - while (m_tail + len >= m_stSize)
2.741 - {
2.742 - m_stSize *= 2;
2.743 - }
2.744 - m_stringtab = (char *)realloc(m_stringtab,m_stSize);
2.745 - }
2.746 -
2.747 - unsigned int tail = m_tail;
2.748 - strcpy(&m_stringtab[tail], ptr);
2.749 - m_tail += len;
2.750 -
2.751 - return tail;
2.752 - }
2.753 - unsigned int x_check(char c, unsigned int start=1)
2.754 - {
2.755 - unsigned char _c = charval(c);
2.756 - unsigned int to_check = m_baseSize - _c;
2.757 - for (unsigned int i=start; i<=to_check; i++)
2.758 - {
2.759 - if (m_base[i+_c].mode == Node_Unused)
2.760 - {
2.761 - return i;
2.762 - }
2.763 - }
2.764 -
2.765 - grow();
2.766 -
2.767 - return x_check(c, to_check+1);
2.768 - }
2.769 - unsigned int x_check2(char c1, char c2, unsigned int start=1)
2.770 - {
2.771 - unsigned char _c1 = charval(c1);
2.772 - unsigned char _c2 = charval(c2);
2.773 - unsigned int to_check = m_baseSize - (_c1 > _c2 ? _c1 : _c2);
2.774 - for (unsigned int i=start; i<=to_check; i++)
2.775 - {
2.776 - if (m_base[i+_c1].mode == Node_Unused
2.777 - && m_base[i+_c2].mode == Node_Unused)
2.778 - {
2.779 - return i;
2.780 - }
2.781 - }
2.782 -
2.783 - grow();
2.784 -
2.785 - return x_check2(c1, c2, to_check+1);
2.786 - }
2.787 - unsigned int x_check_multi(
2.788 - unsigned int offsets[],
2.789 - unsigned int count,
2.790 - unsigned int start=1)
2.791 - {
2.792 - KTrieNode *cur;
2.793 - unsigned int to_check = m_baseSize;
2.794 - unsigned int highest = 0;
2.795 -
2.796 - for (unsigned int i=0; i<count; i++)
2.797 - {
2.798 - if (offsets[i] > highest)
2.799 - {
2.800 - highest = offsets[i];
2.801 - }
2.802 - }
2.803 -
2.804 - to_check -= highest;
2.805 -
2.806 - for (unsigned int i=start; i<=to_check; i++)
2.807 - {
2.808 - bool okay = true;
2.809 - for (unsigned int j=0; j<count; j++)
2.810 - {
2.811 - cur = &m_base[i+offsets[j]];
2.812 - if (cur->mode != Node_Unused)
2.813 - {
2.814 - okay = false;
2.815 - break;
2.816 - }
2.817 - }
2.818 - if (okay)
2.819 - {
2.820 - return i;
2.821 - }
2.822 - }
2.823 -
2.824 - grow();
2.825 -
2.826 - return x_check_multi(offsets, count, to_check+1);
2.827 - }
2.828 -private:
2.829 - KTrieNode *m_base; /* Base array for the sparse tables */
2.830 - char *m_stringtab; /* String table pointer */
2.831 - unsigned int m_baseSize; /* Size of the base array, in members */
2.832 - unsigned int m_stSize; /* Size of the string table, in bytes */
2.833 - unsigned int m_tail; /* Current unused offset into the string table */
2.834 -};
2.835 -
2.836 -/**
2.837 - * Double Array Trie algorithm, based on:
2.838 - * An Efficient Implementation of Trie Structures, by
2.839 - * Jun-ichi Aoe and Katsushi Maromoto, and Takashi Sato
2.840 - * from Software - Practice and Experience, Vol. 22(9), 695-721 (September 1992)
2.841 - *
2.842 - * A Trie is a simple data structure which stores strings as DFAs, with each
2.843 - * transition state being a string entry. For example, observe the following strings:
2.844 - *
2.845 - * BAILOPAN, BAT, BACON, BACK
2.846 - * These transition as the follow production rules:
2.847 - * B -> ... B
2.848 - * A -> ... BA
2.849 - * I -> ... BAI
2.850 - * LOPAN BAILOPAN
2.851 - * T -> ... BAT
2.852 - * C -> BAC
2.853 - * O -> ... BACO
2.854 - * N BACON
2.855 - * K BACK
2.856 - *
2.857 - * The standard implementation for this - using lists - gives a slow linear lookup, somewhere between
2.858 - * O(N+M) or O(log n). A faster implementation is proposed in the paper above, which is based on compacting
2.859 - * the transition states into two arrays. In the paper's implementation, two arrays are used, and thus it is
2.860 - * called the "Double Array" algorithm. However, the CHECK array's size is maintained the same as BASE,
2.861 - * so they can be combined into one structure. The array seems complex at first, but is very simple: it is a
2.862 - * tree structure flattened out into a single vector. I am calling this implementation the Flat Array Trie.
2.863 - *
2.864 - * BASE[] is an array where each member is a node in the Trie. The node can either be UNUSED (empty), an ARC
2.865 - * (containing an offset to the next set of ARCs), or a TERMINATOR (contains the rest of a string).
2.866 - * Each node has an index which must be interpreted based on the node type. If the node is a TERMINATOR, then the
2.867 - * index is an index into a string table, to find the rest of the string.
2.868 - * If the node is an ARC, the index is another index into BASE. For each possible token that can follow the
2.869 - * current token, the value of those tokens can be added to the index given in the ARC. Thus, given a current
2.870 - * position and the next desired token, the current arc will jump to another arc which can contain either:
2.871 - * 1) An invalid production (collision, no entry exists)
2.872 - * 2) An empty production (no entry exists)
2.873 - * 3) Another arc label (the string ends here or continues into more productions)
2.874 - * 4) A TERMINATOR (the string ends here and contains an unused set of productions)
2.875 - *
2.876 - * So, given current offset N (starting at N=1), jumping to token C means the next offset will be:
2.877 - * offs = BASE[n] + C
2.878 - * Thus, the next node will be at:
2.879 - * BASE[BASE[n] + C]
2.880 - *
2.881 - * This allows each ARC to specify the base offset for any of its ARC children, like a tree. Each node specifies
2.882 - * its parent ARC -- so if an invalid offset is specified, the parent will not match, and thus no such derived
2.883 - * string exists.
2.884 - *
2.885 - * This means that arrays can be laid out "sparsely," maximizing their usage. Note that N need not be related to
2.886 - * 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
2.887 - * insertion comes with a small deal of complexity. To insert a new set of tokens T, the algorithm finds a new
2.888 - * BASE index N such that BASE[N+T[i]] is unused for each T[i]. Thus, indirection is not necessarily linear;
2.889 - * traversing a chain of ARC nodes can _and will_ jump around BASE.
2.890 - *
2.891 - * Of course, given this level of flexibility in the array organization, there are collisions. This is largely
2.892 - * where insertions become slow, as the old chain must be relocated before the new one is used. Relocation means
2.893 - * finding one or more new base indexes, and this means traversing BASE until an acceptable index is found, such
2.894 - * that each offset is unused (see description in previous paragraph).
2.895 - *
2.896 - * However, it is not insertion time we are concerned about. The "trie" name comes from reTRIEval. We are only
2.897 - * concerned with lookup and deletion. Both lookup and deletion are O(k), where k is relative to the length of the
2.898 - * input string. Note that it is best case O(1) and worst case O(k). Deleting the entire trie is always O(1).
2.899 - */
2.900 -
2.901 -#endif //_INCLUDE_SOURCEMOD_TEMPLATED_TRIE_H_
3.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
3.2 +++ b/public/sm_trie_tpl.h Wed Aug 29 05:22:47 2007 +0000
3.3 @@ -0,0 +1,898 @@
3.4 +/**
3.5 + * vim: set ts=4 :
3.6 + * =============================================================================
3.7 + * SourceMod
3.8 + * Copyright (C) 2004-2007 AlliedModders LLC. All rights reserved.
3.9 + * =============================================================================
3.10 + *
3.11 + * This program is free software; you can redistribute it and/or modify it under
3.12 + * the terms of the GNU General Public License, version 3.0, as published by the
3.13 + * Free Software Foundation.
3.14 + *
3.15 + * This program is distributed in the hope that it will be useful, but WITHOUT
3.16 + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
3.17 + * FOR A PARTICULAR PURPOSE. See the GNU General Public License for more
3.18 + * details.
3.19 + *
3.20 + * You should have received a copy of the GNU General Public License along with
3.21 + * this program. If not, see <http://www.gnu.org/licenses/>.
3.22 + *
3.23 + * As a special exception, AlliedModders LLC gives you permission to link the
3.24 + * code of this program (as well as its derivative works) to "Half-Life 2," the
3.25 + * "Source Engine," the "SourcePawn JIT," and any Game MODs that run on software
3.26 + * by the Valve Corporation. You must obey the GNU General Public License in
3.27 + * all respects for all other code used. Additionally, AlliedModders LLC grants
3.28 + * this exception to all derivative works. AlliedModders LLC defines further
3.29 + * exceptions, found in LICENSE.txt (as of this writing, version JULY-31-2007),
3.30 + * or <http://www.sourcemod.net/license.php>.
3.31 + *
3.32 + * Version: $Id$
3.33 + */
3.34 +
3.35 +#ifndef _INCLUDE_SOURCEMOD_TEMPLATED_TRIE_H_
3.36 +#define _INCLUDE_SOURCEMOD_TEMPLATED_TRIE_H_
3.37 +
3.38 +#include <new>
3.39 +#include <string.h>
3.40 +#include <malloc.h>
3.41 +#include <assert.h>
3.42 +
3.43 +enum NodeType
3.44 +{
3.45 + Node_Unused = 0, /* Node is not being used (sparse) */
3.46 + Node_Arc, /* Node is part of an arc and does not terminate */
3.47 + Node_Term, /* Node is a terminator */
3.48 +};
3.49 +
3.50 +/**
3.51 + * @brief Trie algorithm based on "Double Array Trie" algorith.
3.52 + * @file sm_trie_tpl.h
3.53 + *
3.54 + * For full works cited and implementation overview, there is a big comment
3.55 + * block at the bottom of this file.
3.56 + */
3.57 +
3.58 +template <typename K>
3.59 +class KTrie
3.60 +{
3.61 + class KTrieNode;
3.62 +public:
3.63 + /**
3.64 + * @brief Clears all set objects in the trie.
3.65 + */
3.66 + void clear()
3.67 + {
3.68 + run_destructors();
3.69 + internal_clear();
3.70 + }
3.71 +
3.72 + /**
3.73 + * @brief Removes a key from the trie.
3.74 + *
3.75 + * @param key Key to remove.
3.76 + * @return True on success, false if key was never set.
3.77 + */
3.78 + bool remove(const char *key)
3.79 + {
3.80 + KTrieNode *node = internal_retrieve(key);
3.81 + if (!node || !node->valset)
3.82 + {
3.83 + return false;
3.84 + }
3.85 +
3.86 + node->value.~K();
3.87 + node->valset = false;
3.88 +
3.89 + return true;
3.90 + }
3.91 +
3.92 + /**
3.93 + * @brief Retrieves a pointer to the object stored at a given key.
3.94 + *
3.95 + * @param key Key to retrieve.
3.96 + * @return Pointer to object, or NULL if key was not found or not set.
3.97 + */
3.98 + K * retrieve(const char *key)
3.99 + {
3.100 + KTrieNode *node = internal_retrieve(key);
3.101 + if (!node || !node->valset)
3.102 + {
3.103 + return NULL;
3.104 + }
3.105 + return &node->value;
3.106 + }
3.107 +
3.108 + /**
3.109 + * @brief Inserts or updates the object stored at a key.
3.110 + *
3.111 + * @param key Key to update or insert.
3.112 + * @param obj Object to store at the key.
3.113 + * @return True on success, false on failure.
3.114 + */
3.115 + bool replace(const char *key, const K & obj)
3.116 + {
3.117 + KTrieNode *prev_node = internal_retrieve(key);
3.118 + if (!prev_node)
3.119 + {
3.120 + return insert(key, obj);
3.121 + }
3.122 +
3.123 + if (prev_node->valset)
3.124 + {
3.125 + prev_node->value.~K();
3.126 + }
3.127 +
3.128 + new (&prev_node->value) K(obj);
3.129 +
3.130 + return true;
3.131 + }
3.132 +
3.133 + /**
3.134 + * @brief Inserts an object at a key.
3.135 + *
3.136 + * @param key Key to insert at.
3.137 + * @param obj Object to store at the key.
3.138 + * @return True on success, false if the key is already set or
3.139 + * insertion otherwise failed.
3.140 + */
3.141 + bool insert(const char *key, const K & obj)
3.142 + {
3.143 + unsigned int lastidx = 1; /* the last node index */
3.144 + unsigned int curidx; /* current node index */
3.145 + const char *keyptr = key; /* input stream at current token */
3.146 + KTrieNode *node = NULL; /* current node being processed */
3.147 + KTrieNode *basenode = NULL; /* current base node being processed */
3.148 + unsigned int q; /* temporary var for x_check results */
3.149 + unsigned int curoffs; /* current offset */
3.150 +
3.151 + /* Do not handle empty strings for simplicity */
3.152 + if (!*key)
3.153 + {
3.154 + return false;
3.155 + }
3.156 +
3.157 + /* Start traversing at the root node (1) */
3.158 + do
3.159 + {
3.160 + /* Find where the next character is, then advance */
3.161 + curidx = m_base[lastidx].idx;
3.162 + basenode = &m_base[curidx];
3.163 + curoffs = charval(*keyptr);
3.164 + curidx += curoffs;
3.165 + node = &m_base[curidx];
3.166 + keyptr++;
3.167 +
3.168 + /* Check if this slot is supposed to be empty. If so, we need to handle CASES 1/2:
3.169 + * Insertion without collisions
3.170 + */
3.171 + if ( (curidx > m_baseSize) || (node->mode == Node_Unused) )
3.172 + {
3.173 + if (curidx > m_baseSize)
3.174 + {
3.175 + if (!grow())
3.176 + {
3.177 + return false;
3.178 + }
3.179 + node = &m_base[curidx];
3.180 + }
3.181 + node->parent = lastidx;
3.182 + if (*keyptr == '\0')
3.183 + {
3.184 + node->mode = Node_Arc;
3.185 + } else {
3.186 + node->idx = x_addstring(keyptr);
3.187 + node->mode = Node_Term;
3.188 + }
3.189 + node->valset = true;
3.190 + new (&node->value) K(obj);
3.191 +
3.192 + return true;
3.193 + } else if (node->parent != lastidx) {
3.194 + /* Collision! We have to split up the tree here. CASE 4:
3.195 + * Insertion when a new word is inserted with a collision.
3.196 + * NOTE: This is the hardest case to handle. All below examples are based on:
3.197 + * BACHELOR, BADGE, inserting BABY.
3.198 + * The problematic production here is A -> B, where B is already being used.
3.199 + *
3.200 + * This process has to rotate one half of the 'A' arc. We generate two lists:
3.201 + * Outgoing Arcs - Anything leaving this 'A'
3.202 + * Incoming Arcs - Anything going to this 'A'
3.203 + * Whichever list is smaller will be moved. Note that this works because the intersection
3.204 + * affects both arc chains, and moving one will make the slot available to either.
3.205 + */
3.206 + KTrieNode *cur;
3.207 +
3.208 + /* Find every node arcing from the last node.
3.209 + * I.e. for BACHELOR, BADGE, BABY,
3.210 + * The arcs leaving A will be C and D, but our current node is B -> *.
3.211 + * Thus, we use the last index (A) to find the base for arcs leaving A.
3.212 + */
3.213 + unsigned int outgoing_base = m_base[lastidx].idx;
3.214 + unsigned int outgoing_list[256];
3.215 + unsigned int outgoing_count = 0; /* count the current index here */
3.216 + cur = &m_base[outgoing_base] + 1;
3.217 + unsigned int outgoing_limit = 255;
3.218 +
3.219 + if (outgoing_base + outgoing_limit > m_baseSize)
3.220 + {
3.221 + outgoing_limit = m_baseSize - outgoing_base;
3.222 + }
3.223 +
3.224 + for (unsigned int i=1; i<=outgoing_limit; i++,cur++)
3.225 + {
3.226 + if (cur->mode == Node_Unused || cur->parent != lastidx)
3.227 + {
3.228 + continue;
3.229 + }
3.230 + outgoing_list[outgoing_count++] = i;
3.231 + }
3.232 + outgoing_list[outgoing_count++] = curidx - outgoing_base;
3.233 +
3.234 + /* Now we need to find all the arcs leaving our parent...
3.235 + * Note: the inconsistency is the base of our parent.
3.236 + */
3.237 + assert(m_base[node->parent].mode == Node_Arc);
3.238 + unsigned int incoming_list[256];
3.239 + unsigned int incoming_base = m_base[node->parent].idx;
3.240 + unsigned int incoming_count = 0;
3.241 + unsigned int incoming_limit = 255;
3.242 + cur = &m_base[incoming_base] + 1;
3.243 +
3.244 + if (incoming_base + incoming_limit > m_baseSize)
3.245 + {
3.246 + incoming_limit = m_baseSize - incoming_base;
3.247 + }
3.248 +
3.249 + assert(incoming_limit > 0 && incoming_limit <= 255);
3.250 +
3.251 + for (unsigned int i=1; i<=incoming_limit; i++,cur++)
3.252 + {
3.253 + if (cur->mode == Node_Arc || cur->mode == Node_Term)
3.254 + {
3.255 + if (cur->parent == node->parent)
3.256 + {
3.257 + incoming_list[incoming_count++] = i;
3.258 + }
3.259 + }
3.260 + }
3.261 +
3.262 + if (incoming_count < outgoing_count + 1)
3.263 + {
3.264 + unsigned int q = x_check_multi(incoming_list, incoming_count);
3.265 +
3.266 + node = &m_base[curidx];
3.267 +
3.268 + /* If we're incoming, we need to modify our parent */
3.269 + m_base[node->parent].idx = q;
3.270 +
3.271 + /* For each node in the "to move" list,
3.272 + * Relocate the node's info to the new position.
3.273 + */
3.274 + unsigned int idx, newidx, oldidx;
3.275 + for (unsigned int i=0; i<incoming_count; i++)
3.276 + {
3.277 + idx = incoming_list[i];
3.278 + newidx = q + idx;
3.279 + oldidx = incoming_base + idx;
3.280 + if (oldidx == lastidx)
3.281 + {
3.282 + /* Important! Make sure we're not invalidating our sacred lastidx */
3.283 + lastidx = newidx;
3.284 + }
3.285 + /* Fully copy the node */
3.286 + memcpy(&m_base[newidx], &m_base[oldidx], sizeof(KTrieNode));
3.287 + if (m_base[oldidx].valset)
3.288 + {
3.289 + new (&m_base[newidx].value) K(m_base[oldidx].value);
3.290 + m_base[oldidx].value.~K();
3.291 + }
3.292 + assert(m_base[m_base[newidx].parent].mode == Node_Arc);
3.293 + /* Erase old data */
3.294 + memset(&m_base[oldidx], 0, sizeof(KTrieNode));
3.295 + /* If we are not a terminator, we have children we must take care of */
3.296 + if (m_base[newidx].mode == Node_Arc)
3.297 + {
3.298 + KTrieNode *check_base = &m_base[m_base[newidx].idx] + 1;
3.299 + outgoing_limit = (m_base + m_baseSize + 1) - check_base;
3.300 + if (outgoing_limit > 255)
3.301 + {
3.302 + outgoing_limit = 255;
3.303 + }
3.304 + for (unsigned int j=1; j<=outgoing_limit; j++, check_base++)
3.305 + {
3.306 + if (check_base->parent == oldidx)
3.307 + {
3.308 + check_base->parent = newidx;
3.309 + }
3.310 + }
3.311 + }
3.312 + }
3.313 + } else {
3.314 + unsigned int q = x_check_multi(outgoing_list, outgoing_count);
3.315 +
3.316 + node = &m_base[curidx];
3.317 +
3.318 + /* If we're outgoing, we need to modify our own base */
3.319 + m_base[lastidx].idx = q;
3.320 +
3.321 + /* Take the last index (curidx) out of the list. Technically we are not moving this,
3.322 + * since it's already being used by something else.
3.323 + */
3.324 + outgoing_count--;
3.325 +
3.326 + /* For each node in the "to move" list,
3.327 + * Relocate the node's info to the new position.
3.328 + */
3.329 + unsigned int idx, newidx, oldidx;
3.330 + for (unsigned int i=0; i<outgoing_count; i++)
3.331 + {
3.332 + idx = outgoing_list[i];
3.333 + newidx = q + idx;
3.334 + oldidx = outgoing_base + idx;
3.335 + if (oldidx == lastidx)
3.336 + {
3.337 + /* Important! Make sure we're not invalidating our sacred lastidx */
3.338 + lastidx = newidx;
3.339 + }
3.340 + /* Fully copy the node */
3.341 + memcpy(&m_base[newidx], &m_base[oldidx], sizeof(KTrieNode));
3.342 + if (m_base[oldidx].valset)
3.343 + {
3.344 + new (&m_base[newidx].value) K(m_base[oldidx].value);
3.345 + m_base[oldidx].value.~K();
3.346 + }
3.347 + assert(m_base[m_base[newidx].parent].mode == Node_Arc);
3.348 + /* Erase old data */
3.349 + memset(&m_base[oldidx], 0, sizeof(KTrieNode));
3.350 + /* If we are not a terminator, we have children we must take care of */
3.351 + if (m_base[newidx].mode == Node_Arc)
3.352 + {
3.353 + KTrieNode *check_base = &m_base[m_base[newidx].idx] + 1;
3.354 + outgoing_limit = (m_base + m_baseSize + 1) - check_base;
3.355 + if (outgoing_limit > 255)
3.356 + {
3.357 + outgoing_limit = 255;
3.358 + }
3.359 + for (unsigned int j=1; j<=outgoing_limit; j++, check_base++)
3.360 + {
3.361 + if (check_base->parent == oldidx)
3.362 + {
3.363 + check_base->parent = newidx;
3.364 + }
3.365 + }
3.366 + }
3.367 + }
3.368 +
3.369 + /* Take the invisible node and use it as our new node */
3.370 + node = &m_base[q + outgoing_list[outgoing_count]];
3.371 + }
3.372 +
3.373 + /* We're finally done! */
3.374 + node->parent = lastidx;
3.375 + if (*keyptr == '\0')
3.376 + {
3.377 + node->mode = Node_Arc;
3.378 + } else {
3.379 + node->idx = x_addstring(keyptr);
3.380 + node->mode = Node_Term;
3.381 + }
3.382 + node->valset = true;
3.383 + new (&node->value) K(obj);
3.384 +
3.385 + return true;
3.386 + } else {
3.387 + /* See what's in the next node - special case if terminator! */
3.388 + if (node->mode == Node_Term)
3.389 + {
3.390 + /* If we're a terminator, we need to handle CASE 3:
3.391 + * Insertion when a terminating collision occurs
3.392 + */
3.393 + char *term = &m_stringtab[node->idx];
3.394 + /* Do an initial browsing to make sure they're not the same string */
3.395 + if (strcmp(keyptr, term) == 0)
3.396 + {
3.397 + if (!node->valset)
3.398 + {
3.399 + node->valset = true;
3.400 + new (&node->value) K(obj);
3.401 + return true;
3.402 + }
3.403 + /* Same string. We can't insert. */
3.404 + return false;
3.405 + }
3.406 + /* For each matching character pair, we need to disband the terminator.
3.407 + * This splits the similar prefix into a single arc path.
3.408 + * First, save the old values so we can move them to a new node.
3.409 + * Next, for each loop:
3.410 + * Take the current (invalid) node, and point it to the next arc base.
3.411 + * Set the current node to the node at the next arc.
3.412 + */
3.413 + K oldvalue;
3.414 + bool oldvalset = node->valset;
3.415 + if (oldvalset)
3.416 + {
3.417 + oldvalue = node->value;
3.418 + }
3.419 + if (*term == *keyptr)
3.420 + {
3.421 + while (*term == *keyptr)
3.422 + {
3.423 + /* Find the next free slot in the check array.
3.424 + * This is the "vector base" essentially
3.425 + */
3.426 + q = x_check(*term);
3.427 + node = &m_base[curidx];
3.428 + /* Point the node to the next new base */
3.429 + node->idx = q;
3.430 + node->mode = Node_Arc;
3.431 + if (node->valset == true)
3.432 + {
3.433 + node->value.~K();
3.434 + node->valset = false;
3.435 + }
3.436 + /* Advance the input stream and local variables */
3.437 + lastidx = curidx;
3.438 + curidx = q + charval(*term);
3.439 + node = &m_base[curidx];
3.440 + /* Make sure the new current node has its parent set. */
3.441 + node->parent = lastidx;
3.442 + node->mode = Node_Arc; /* Just in case we run x_check again */
3.443 + *term = '\0'; /* Unmark the string table here */
3.444 + term++;
3.445 + keyptr++;
3.446 + }
3.447 + } else if (node->valset) {
3.448 + node->valset = false;
3.449 + node->value.~K();
3.450 + }
3.451 + /* We're done inserting new pairs. If one of them is exhausted,
3.452 + * we take special shortcuts.
3.453 + */
3.454 + if (*term == '\0') //EX: BADGERHOUSE added over B -> ADGER.
3.455 + {
3.456 + /* First backpatch the current node - it ends the newly split terminator.
3.457 + * In the example, this would mean the node is the production from R -> ?
3.458 + * This node ends the old BADGER, so we set it here.
3.459 + */
3.460 + node->valset = oldvalset;
3.461 + if (node->valset)
3.462 + {
3.463 + new (&node->value) K(oldvalue);
3.464 + }
3.465 +
3.466 + /* The terminator was split up, but pieces of keyptr remain.
3.467 + * We need to generate a new production, in this example, R -> H,
3.468 + * with H being a terminator to OUSE. Thus we get:
3.469 + * B,A,D,G,E,R*,H*->OUSE (* = value set).
3.470 + * NOTE: parent was last set at the end of the while loop.
3.471 + */
3.472 + /* Get the new base and apply re-basing */
3.473 + q = x_check(*keyptr);
3.474 + node = &m_base[curidx];
3.475 +
3.476 + node->idx = q;
3.477 + node->mode = Node_Arc;
3.478 + lastidx = curidx;
3.479 + /* Finish the final node */
3.480 + curidx = q + charval(*keyptr);
3.481 + node = &m_base[curidx];
3.482 + keyptr++;
3.483 + /* Optimize - don't add to string table if there's nothing more to eat */
3.484 + if (*keyptr == '\0')
3.485 + {
3.486 + node->mode = Node_Arc;
3.487 + } else {
3.488 + node->idx = x_addstring(keyptr);
3.489 + node->mode = Node_Term;
3.490 + }
3.491 + node->parent = lastidx;
3.492 + node->valset = true;
3.493 + new (&node->value) K(obj);
3.494 + } else if (*keyptr == '\0') { //EX: BADGER added over B -> ADGERHOUSE
3.495 + /* First backpatch the current node - it ends newly split input string.
3.496 + * This is the exact opposite of the above procedure.
3.497 + */
3.498 + node->valset = true;
3.499 + new (&node->value) K(obj);
3.500 +
3.501 + /* Get the new base and apply re-basing */
3.502 + q = x_check(*term);
3.503 + node = &m_base[curidx];
3.504 +
3.505 + node->idx = q;
3.506 + node->mode = Node_Arc;
3.507 + lastidx = curidx;
3.508 + /* Finish the final node */
3.509 + curidx = q + charval(*term);
3.510 + node = &m_base[curidx];
3.511 + term++;
3.512 + /* Optimize - don't add to string table if there's nothing more to eat */
3.513 + if (*term == '\0')
3.514 + {
3.515 + node->mode = Node_Arc;
3.516 + } else {
3.517 + node->idx = (term - m_stringtab); /* Already in the string table! */
3.518 + node->mode = Node_Term;
3.519 + }
3.520 + node->parent = lastidx;
3.521 + node->valset = oldvalset;
3.522 + if (node->valset)
3.523 + {
3.524 + new (&node->value) K(oldvalue);
3.525 + }
3.526 + } else {
3.527 + /* Finally, we have to create two new nodes instead of just one. */
3.528 + node->mode = Node_Arc;
3.529 +
3.530 + /* Get the new base and apply re-basing */
3.531 + q = x_check2(*keyptr, *term);
3.532 + node = &m_base[curidx];
3.533 +
3.534 + node->idx = q;
3.535 + lastidx = curidx;
3.536 +
3.537 + /* Re-create the old terminated node */
3.538 + curidx = q + charval(*term);
3.539 + node = &m_base[curidx];
3.540 + term++;
3.541 + node->valset = oldvalset;
3.542 + if (node->valset)
3.543 + {
3.544 + new (&node->value) K(oldvalue);
3.545 + }
3.546 + node->parent = lastidx;
3.547 + if (*term == '\0')
3.548 + {
3.549 + node->mode = Node_Arc;
3.550 + } else {
3.551 + node->mode = Node_Term;
3.552 + node->idx = (term - m_stringtab); /* Already in the string table! */
3.553 + }
3.554 +
3.555 + /* Create the new keyed input node */
3.556 + curidx = q + charval(*keyptr);
3.557 + node = &m_base[curidx];
3.558 + keyptr++;
3.559 + node->valset = true;
3.560 + new (&node->value) K(obj);
3.561 + node->parent = lastidx;
3.562 + if (*keyptr == '\0')
3.563 + {
3.564 + node->mode = Node_Arc;
3.565 + } else {
3.566 + node->mode = Node_Term;
3.567 + node->idx = x_addstring(keyptr);
3.568 + }
3.569 + }
3.570 +
3.571 + /* Phew! */
3.572 + return true;
3.573 + } else {
3.574 + assert(node->mode == Node_Arc);
3.575 + }
3.576 + }
3.577 + lastidx = curidx;
3.578 + } while (*keyptr != '\0');
3.579 +
3.580 + assert(node);
3.581 +
3.582 + /* If we've exhausted the string and we have a valid reached node,
3.583 + * the production rule already existed. Make sure it's valid to set first.
3.584 + */
3.585 +
3.586 + /* We have to be an Arc. If the last result was anything else, we would have returned a new
3.587 + * production earlier.
3.588 + */
3.589 + assert(node->mode == Node_Arc);
3.590 +
3.591 + if (!node->valset)
3.592 + {
3.593 + node->valset = true;
3.594 + new (&node->value) K(obj);
3.595 + return true;
3.596 + }
3.597 +
3.598 + return false;
3.599 + }
3.600 +public:
3.601 + KTrie()
3.602 + {
3.603 + m_base = (KTrieNode *)malloc(sizeof(KTrieNode) * (256 + 1));
3.604 + m_stringtab = (char *)malloc(sizeof(char) * 256);
3.605 + m_baseSize = 256;
3.606 + m_stSize = 256;
3.607 +
3.608 + internal_clear();
3.609 + }
3.610 + ~KTrie()
3.611 + {
3.612 + run_destructors();
3.613 + free(m_base);
3.614 + free(m_stringtab);
3.615 + }
3.616 +private:
3.617 + class KTrieNode
3.618 + {
3.619 + friend class KTrie;
3.620 + private:
3.621 + /**
3.622 + * For Node_Arc, this index stores the 'base' offset to the next arc chain.
3.623 + * I.e. to jump from this arc to character C, it will be at base[idx+C].
3.624 + * For Node_Term, this is an index into the string table.
3.625 + */
3.626 + unsigned int idx;
3.627 +
3.628 + /**
3.629 + * This contains the prior arc that we must have come from.
3.630 + * For example, if arc 63 has a base jump of index 12, and we want to see if
3.631 + * there is a valid character C, the parent of 12+C must be 63.
3.632 + */
3.633 + unsigned int parent;
3.634 + K value; /* Value associated with this node */
3.635 + NodeType mode; /* Current usage type of the node */
3.636 + bool valset; /* Whether or not a value is set */
3.637 + };
3.638 +private:
3.639 + KTrieNode *internal_retrieve(const char *key)
3.640 + {
3.641 + unsigned int lastidx = 1; /* the last node index */
3.642 + unsigned int curidx; /* current node index */
3.643 + const char *keyptr = key; /* input stream at current token */
3.644 + KTrieNode *node = NULL; /* current node being processed */
3.645 +
3.646 + if (!*key)
3.647 + {
3.648 + return NULL;
3.649 + }
3.650 +
3.651 + /* Start traversing at the root node */
3.652 + do
3.653 + {
3.654 + /* Find where the next character is, then advance */
3.655 + curidx = m_base[lastidx].idx;
3.656 + node = &m_base[curidx];
3.657 + curidx += charval(*keyptr);
3.658 + node = &m_base[curidx];
3.659 + keyptr++;
3.660 +
3.661 + /* Check if this slot is supposed to be empty or is a collision */
3.662 + if ((curidx > m_baseSize) || node->mode == Node_Unused || node->parent != lastidx)
3.663 + {
3.664 + return NULL;
3.665 + } else if (node->mode == Node_Term) {
3.666 + char *term = &m_stringtab[node->idx];
3.667 + if (strcmp(keyptr, term) == 0)
3.668 + {
3.669 + break;
3.670 + }
3.671 + }
3.672 + lastidx = curidx;
3.673 + } while (*keyptr != '\0');
3.674 +
3.675 + return node;
3.676 + }
3.677 + bool grow()
3.678 + {
3.679 + /* The current # of nodes in the tree is trie->baseSize + 1 */
3.680 + unsigned int cur_size = m_baseSize;
3.681 + unsigned int new_size = cur_size * 2;
3.682 +
3.683 + KTrieNode *new_base = (KTrieNode *)malloc((new_size + 1) * sizeof(KTrieNode));
3.684 + if (!new_base)
3.685 + {
3.686 + return false;
3.687 + }
3.688 +
3.689 + memcpy(new_base, m_base, sizeof(KTrieNode) * (m_baseSize + 1));
3.690 + memset(&new_base[cur_size + 1], 0, (new_size - cur_size) * sizeof(KTrieNode));
3.691 +
3.692 + for (size_t i = 0; i <= m_baseSize; i++)
3.693 + {
3.694 + if (m_base[i].valset)
3.695 + {
3.696 + /* Placement construct+copy the object, then placement destroy the old. */
3.697 + new (&new_base[i].value) K(m_base[i].value);
3.698 + m_base[i].value.~K();
3.699 + }
3.700 + }
3.701 +
3.702 + free(m_base);
3.703 + m_base = new_base;
3.704 + m_baseSize = new_size;
3.705 +
3.706 + return true;
3.707 + }
3.708 + inline unsigned char charval(char c)
3.709 + {
3.710 + return (unsigned char)c;
3.711 + }
3.712 + void internal_clear()
3.713 + {
3.714 + m_tail = 0;
3.715 +
3.716 + memset(m_base, 0, sizeof(KTrieNode) * (m_baseSize + 1));
3.717 + memset(m_stringtab, 0, sizeof(char) * m_stSize);
3.718 +
3.719 + /* Sentinel root node */
3.720 + m_base[1].idx = 1;
3.721 + m_base[1].mode = Node_Arc;
3.722 + m_base[1].parent = 1;
3.723 + }
3.724 + void run_destructors()
3.725 + {
3.726 + for (size_t i = 0; i <= m_baseSize; i++)
3.727 + {
3.728 + if (m_base[i].valset)
3.729 + {
3.730 + m_base[i].value.~K();
3.731 + }
3.732 + }
3.733 + }
3.734 + unsigned int x_addstring(const char *ptr)
3.735 + {
3.736 + size_t len = strlen(ptr) + 1;
3.737 +
3.738 + if (m_tail + len >= m_stSize)
3.739 + {
3.740 + while (m_tail + len >= m_stSize)
3.741 + {
3.742 + m_stSize *= 2;
3.743 + }
3.744 + m_stringtab = (char *)realloc(m_stringtab,m_stSize);
3.745 + }
3.746 +
3.747 + unsigned int tail = m_tail;
3.748 + strcpy(&m_stringtab[tail], ptr);
3.749 + m_tail += len;
3.750 +
3.751 + return tail;
3.752 + }
3.753 + unsigned int x_check(char c, unsigned int start=1)
3.754 + {
3.755 + unsigned char _c = charval(c);
3.756 + unsigned int to_check = m_baseSize - _c;
3.757 + for (unsigned int i=start; i<=to_check; i++)
3.758 + {
3.759 + if (m_base[i+_c].mode == Node_Unused)
3.760 + {
3.761 + return i;
3.762 + }
3.763 + }
3.764 +
3.765 + grow();
3.766 +
3.767 + return x_check(c, to_check+1);
3.768 + }
3.769 + unsigned int x_check2(char c1, char c2, unsigned int start=1)
3.770 + {
3.771 + unsigned char _c1 = charval(c1);
3.772 + unsigned char _c2 = charval(c2);
3.773 + unsigned int to_check = m_baseSize - (_c1 > _c2 ? _c1 : _c2);
3.774 + for (unsigned int i=start; i<=to_check; i++)
3.775 + {
3.776 + if (m_base[i+_c1].mode == Node_Unused
3.777 + && m_base[i+_c2].mode == Node_Unused)
3.778 + {
3.779 + return i;
3.780 + }
3.781 + }
3.782 +
3.783 + grow();
3.784 +
3.785 + return x_check2(c1, c2, to_check+1);
3.786 + }
3.787 + unsigned int x_check_multi(
3.788 + unsigned int offsets[],
3.789 + unsigned int count,
3.790 + unsigned int start=1)
3.791 + {
3.792 + KTrieNode *cur;
3.793 + unsigned int to_check = m_baseSize;
3.794 + unsigned int highest = 0;
3.795 +
3.796 + for (unsigned int i=0; i<count; i++)
3.797 + {
3.798 + if (offsets[i] > highest)
3.799 + {
3.800 + highest = offsets[i];
3.801 + }
3.802 + }
3.803 +
3.804 + to_check -= highest;
3.805 +
3.806 + for (unsigned int i=start; i<=to_check; i++)
3.807 + {
3.808 + bool okay = true;
3.809 + for (unsigned int j=0; j<count; j++)
3.810 + {
3.811 + cur = &m_base[i+offsets[j]];
3.812 + if (cur->mode != Node_Unused)
3.813 + {
3.814 + okay = false;
3.815 + break;
3.816 + }
3.817 + }
3.818 + if (okay)
3.819 + {
3.820 + return i;
3.821 + }
3.822 + }
3.823 +
3.824 + grow();
3.825 +
3.826 + return x_check_multi(offsets, count, to_check+1);
3.827 + }
3.828 +private:
3.829 + KTrieNode *m_base; /* Base array for the sparse tables */
3.830 + char *m_stringtab; /* String table pointer */
3.831 + unsigned int m_baseSize; /* Size of the base array, in members */
3.832 + unsigned int m_stSize; /* Size of the string table, in bytes */
3.833 + unsigned int m_tail; /* Current unused offset into the string table */
3.834 +};
3.835 +
3.836 +/**
3.837 + * Double Array Trie algorithm, based on:
3.838 + * An Efficient Implementation of Trie Structures, by
3.839 + * Jun-ichi Aoe and Katsushi Maromoto, and Takashi Sato
3.840 + * from Software - Practice and Experience, Vol. 22(9), 695-721 (September 1992)
3.841 + *
3.842 + * A Trie is a simple data structure which stores strings as DFAs, with each
3.843 + * transition state being a string entry. For example, observe the following strings:
3.844 + *
3.845 + * BAILOPAN, BAT, BACON, BACK
3.846 + * These transition as the follow production rules:
3.847 + * B -> ... B
3.848 + * A -> ... BA
3.849 + * I -> ... BAI
3.850 + * LOPAN BAILOPAN
3.851 + * T -> ... BAT
3.852 + * C -> BAC
3.853 + * O -> ... BACO
3.854 + * N BACON
3.855 + * K BACK
3.856 + *
3.857 + * The standard implementation for this - using lists - gives a slow linear lookup, somewhere between
3.858 + * O(N+M) or O(log n). A faster implementation is proposed in the paper above, which is based on compacting
3.859 + * the transition states into two arrays. In the paper's implementation, two arrays are used, and thus it is
3.860 + * called the "Double Array" algorithm. However, the CHECK array's size is maintained the same as BASE,
3.861 + * so they can be combined into one structure. The array seems complex at first, but is very simple: it is a
3.862 + * tree structure flattened out into a single vector. I am calling this implementation the Flat Array Trie.
3.863 + *
3.864 + * BASE[] is an array where each member is a node in the Trie. The node can either be UNUSED (empty), an ARC
3.865 + * (containing an offset to the next set of ARCs), or a TERMINATOR (contains the rest of a string).
3.866 + * Each node has an index which must be interpreted based on the node type. If the node is a TERMINATOR, then the
3.867 + * index is an index into a string table, to find the rest of the string.
3.868 + * If the node is an ARC, the index is another index into BASE. For each possible token that can follow the
3.869 + * current token, the value of those tokens can be added to the index given in the ARC. Thus, given a current
3.870 + * position and the next desired token, the current arc will jump to another arc which can contain either:
3.871 + * 1) An invalid production (collision, no entry exists)
3.872 + * 2) An empty production (no entry exists)
3.873 + * 3) Another arc label (the string ends here or continues into more productions)
3.874 + * 4) A TERMINATOR (the string ends here and contains an unused set of productions)
3.875 + *
3.876 + * So, given current offset N (starting at N=1), jumping to token C means the next offset will be:
3.877 + * offs = BASE[n] + C
3.878 + * Thus, the next node will be at:
3.879 + * BASE[BASE[n] + C]
3.880 + *
3.881 + * This allows each ARC to specify the base offset for any of its ARC children, like a tree. Each node specifies
3.882 + * its parent ARC -- so if an invalid offset is specified, the parent will not match, and thus no such derived
3.883 + * string exists.
3.884 + *
3.885 + * This means that arrays can be laid out "sparsely," maximizing their usage. Note that N need not be related to
3.886 + * 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
3.887 + * insertion comes with a small deal of complexity. To insert a new set of tokens T, the algorithm finds a new
3.888 + * BASE index N such that BASE[N+T[i]] is unused for each T[i]. Thus, indirection is not necessarily linear;
3.889 + * traversing a chain of ARC nodes can _and will_ jump around BASE.
3.890 + *
3.891 + * Of course, given this level of flexibility in the array organization, there are collisions. This is largely
3.892 + * where insertions become slow, as the old chain must be relocated before the new one is used. Relocation means
3.893 + * finding one or more new base indexes, and this means traversing BASE until an acceptable index is found, such
3.894 + * that each offset is unused (see description in previous paragraph).
3.895 + *
3.896 + * However, it is not insertion time we are concerned about. The "trie" name comes from reTRIEval. We are only
3.897 + * concerned with lookup and deletion. Both lookup and deletion are O(k), where k is relative to the length of the
3.898 + * input string. Note that it is best case O(1) and worst case O(k). Deleting the entire trie is always O(1).
3.899 + */
3.900 +
3.901 +#endif //_INCLUDE_SOURCEMOD_TEMPLATED_TRIE_H_
