1.1 --- a/core/msvc8/sourcemod_mm.vcproj Wed Aug 29 02:37:25 2007 +0000
1.2 +++ b/core/msvc8/sourcemod_mm.vcproj Wed Aug 29 02:37:59 2007 +0000
1.3 @@ -535,6 +535,10 @@
1.4 >
1.5 </File>
1.6 <File
1.7 + RelativePath="..\sm_trie_tpl.h"
1.8 + >
1.9 + </File>
1.10 + <File
1.11 RelativePath="..\sm_version.h"
1.12 >
1.13 </File>
2.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
2.2 +++ b/core/sm_trie_tpl.h Wed Aug 29 02:37:59 2007 +0000
2.3 @@ -0,0 +1,773 @@
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 "sm_trie.h"
2.39 +
2.40 +/**
2.41 + * See sm_trie.h for the main implementation, this is a quick templatized version.
2.42 + */
2.43 +
2.44 +template <typename K>
2.45 +class KTrie
2.46 +{
2.47 +private:
2.48 + class KTrieNode
2.49 + {
2.50 + friend class KTrie;
2.51 + private:
2.52 + unsigned int idx;
2.53 + unsigned int parent;
2.54 + K value; /* Value associated with this node */
2.55 + NodeType mode; /* Current usage type of the node */
2.56 + bool valset; /* Whether or not a value is set */
2.57 + };
2.58 +public:
2.59 + KTrie()
2.60 + {
2.61 + m_base = (KTrieNode *)malloc(sizeof(KTrieNode) * (256 + 1));
2.62 + m_stringtab = (char *)malloc(sizeof(char) * 256);
2.63 + m_baseSize = 256;
2.64 + m_stSize = 256;
2.65 +
2.66 + internal_clear();
2.67 + }
2.68 + ~KTrie()
2.69 + {
2.70 + run_destructors();
2.71 + free(m_base);
2.72 + free(m_stringtab);
2.73 + }
2.74 +public:
2.75 + void clear()
2.76 + {
2.77 + run_destructors();
2.78 + internal_clear();
2.79 + }
2.80 + bool remove(const char *key)
2.81 + {
2.82 + KTrieNode *node = internal_retrieve(key);
2.83 + if (!node || !node->valset)
2.84 + {
2.85 + return false;
2.86 + }
2.87 +
2.88 + node->value.~K();
2.89 + node->valset = false;
2.90 +
2.91 + return true;
2.92 + }
2.93 + K * retrieve(const char *key)
2.94 + {
2.95 + KTrieNode *node = internal_retrieve(key);
2.96 + if (!node || !node->valset)
2.97 + {
2.98 + return NULL;
2.99 + }
2.100 + return &node->value;
2.101 + }
2.102 + bool replace(const char *key, const K & obj)
2.103 + {
2.104 + KTrieNode *prev_node = internal_retrieve(key);
2.105 + if (!prev_node)
2.106 + {
2.107 + return insert(key, obj);
2.108 + }
2.109 +
2.110 + if (prev_node->valset)
2.111 + {
2.112 + prev_node->value.~K();
2.113 + }
2.114 +
2.115 + new (&prev_node->value) K(obj);
2.116 +
2.117 + return true;
2.118 + }
2.119 + bool insert(const char *key, const K & obj)
2.120 + {
2.121 + unsigned int lastidx = 1; /* the last node index */
2.122 + unsigned int curidx; /* current node index */
2.123 + const char *keyptr = key; /* input stream at current token */
2.124 + KTrieNode *node = NULL; /* current node being processed */
2.125 + KTrieNode *basenode = NULL; /* current base node being processed */
2.126 + unsigned int q; /* temporary var for x_check results */
2.127 + unsigned int curoffs; /* current offset */
2.128 +
2.129 + /* Do not handle empty strings for simplicity */
2.130 + if (!*key)
2.131 + {
2.132 + return false;
2.133 + }
2.134 +
2.135 + /* Start traversing at the root node (1) */
2.136 + do
2.137 + {
2.138 + /* Find where the next character is, then advance */
2.139 + curidx = m_base[lastidx].idx;
2.140 + basenode = &m_base[curidx];
2.141 + curoffs = charval(*keyptr);
2.142 + curidx += curoffs;
2.143 + node = &m_base[curidx];
2.144 + keyptr++;
2.145 +
2.146 + /* Check if this slot is supposed to be empty. If so, we need to handle CASES 1/2:
2.147 + * Insertion without collisions
2.148 + */
2.149 + if ( (curidx > m_baseSize) || (node->mode == Node_Unused) )
2.150 + {
2.151 + if (curidx > m_baseSize)
2.152 + {
2.153 + if (!grow())
2.154 + {
2.155 + return false;
2.156 + }
2.157 + node = &m_base[curidx];
2.158 + }
2.159 + node->parent = lastidx;
2.160 + if (*keyptr == '\0')
2.161 + {
2.162 + node->mode = Node_Arc;
2.163 + } else {
2.164 + node->idx = x_addstring(keyptr);
2.165 + node->mode = Node_Term;
2.166 + }
2.167 + node->valset = true;
2.168 + new (&node->value) K(obj);
2.169 +
2.170 + return true;
2.171 + } else if (node->parent != lastidx) {
2.172 + /* Collision! We have to split up the tree here. CASE 4:
2.173 + * Insertion when a new word is inserted with a collision.
2.174 + * NOTE: This is the hardest case to handle. All below examples are based on:
2.175 + * BACHELOR, BADGE, inserting BABY.
2.176 + * The problematic production here is A -> B, where B is already being used.
2.177 + *
2.178 + * This process has to rotate one half of the 'A' arc. We generate two lists:
2.179 + * Outgoing Arcs - Anything leaving this 'A'
2.180 + * Incoming Arcs - Anything going to this 'A'
2.181 + * Whichever list is smaller will be moved. Note that this works because the intersection
2.182 + * affects both arc chains, and moving one will make the slot available to either.
2.183 + */
2.184 + KTrieNode *cur;
2.185 +
2.186 + /* Find every node arcing from the last node.
2.187 + * I.e. for BACHELOR, BADGE, BABY,
2.188 + * The arcs leaving A will be C and D, but our current node is B -> *.
2.189 + * Thus, we use the last index (A) to find the base for arcs leaving A.
2.190 + */
2.191 + unsigned int outgoing_base = m_base[lastidx].idx;
2.192 + unsigned int outgoing_list[256];
2.193 + unsigned int outgoing_count = 0; /* count the current index here */
2.194 + cur = &m_base[outgoing_base] + 1;
2.195 + unsigned int outgoing_limit = 255;
2.196 +
2.197 + if (outgoing_base + outgoing_limit > m_baseSize)
2.198 + {
2.199 + outgoing_limit = m_baseSize - outgoing_base;
2.200 + }
2.201 +
2.202 + for (unsigned int i=1; i<=outgoing_limit; i++,cur++)
2.203 + {
2.204 + if (cur->mode == Node_Unused || cur->parent != lastidx)
2.205 + {
2.206 + continue;
2.207 + }
2.208 + outgoing_list[outgoing_count++] = i;
2.209 + }
2.210 + outgoing_list[outgoing_count++] = curidx - outgoing_base;
2.211 +
2.212 + /* Now we need to find all the arcs leaving our parent...
2.213 + * Note: the inconsistency is the base of our parent.
2.214 + */
2.215 + assert(m_base[node->parent].mode == Node_Arc);
2.216 + unsigned int incoming_list[256];
2.217 + unsigned int incoming_base = m_base[node->parent].idx;
2.218 + unsigned int incoming_count = 0;
2.219 + unsigned int incoming_limit = 255;
2.220 + cur = &m_base[incoming_base] + 1;
2.221 +
2.222 + if (incoming_base + incoming_limit > m_baseSize)
2.223 + {
2.224 + incoming_limit = m_baseSize - incoming_base;
2.225 + }
2.226 +
2.227 + assert(incoming_limit > 0 && incoming_limit <= 255);
2.228 +
2.229 + for (unsigned int i=1; i<=incoming_limit; i++,cur++)
2.230 + {
2.231 + if (cur->mode == Node_Arc || cur->mode == Node_Term)
2.232 + {
2.233 + if (cur->parent == node->parent)
2.234 + {
2.235 + incoming_list[incoming_count++] = i;
2.236 + }
2.237 + }
2.238 + }
2.239 +
2.240 + if (incoming_count < outgoing_count + 1)
2.241 + {
2.242 + unsigned int q = x_check_multi(incoming_list, incoming_count);
2.243 +
2.244 + node = &m_base[curidx];
2.245 +
2.246 + /* If we're incoming, we need to modify our parent */
2.247 + m_base[node->parent].idx = q;
2.248 +
2.249 + /* For each node in the "to move" list,
2.250 + * Relocate the node's info to the new position.
2.251 + */
2.252 + unsigned int idx, newidx, oldidx;
2.253 + for (unsigned int i=0; i<incoming_count; i++)
2.254 + {
2.255 + idx = incoming_list[i];
2.256 + newidx = q + idx;
2.257 + oldidx = incoming_base + idx;
2.258 + if (oldidx == lastidx)
2.259 + {
2.260 + /* Important! Make sure we're not invalidating our sacred lastidx */
2.261 + lastidx = newidx;
2.262 + }
2.263 + /* Fully copy the node */
2.264 + memcpy(&m_base[newidx], &m_base[oldidx], sizeof(KTrieNode));
2.265 + if (m_base[oldidx].valset)
2.266 + {
2.267 + new (&m_base[newidx].value) K(m_base[oldidx].value);
2.268 + m_base[oldidx].value.~K();
2.269 + }
2.270 + assert(m_base[m_base[newidx].parent].mode == Node_Arc);
2.271 + /* Erase old data */
2.272 + memset(&m_base[oldidx], 0, sizeof(KTrieNode));
2.273 + /* If we are not a terminator, we have children we must take care of */
2.274 + if (m_base[newidx].mode == Node_Arc)
2.275 + {
2.276 + KTrieNode *check_base = &m_base[m_base[newidx].idx] + 1;
2.277 + outgoing_limit = (m_base + m_baseSize + 1) - check_base;
2.278 + if (outgoing_limit > 255)
2.279 + {
2.280 + outgoing_limit = 255;
2.281 + }
2.282 + for (unsigned int j=1; j<=outgoing_limit; j++, check_base++)
2.283 + {
2.284 + if (check_base->parent == oldidx)
2.285 + {
2.286 + check_base->parent = newidx;
2.287 + }
2.288 + }
2.289 + }
2.290 + }
2.291 + } else {
2.292 + unsigned int q = x_check_multi(outgoing_list, outgoing_count);
2.293 +
2.294 + node = &m_base[curidx];
2.295 +
2.296 + /* If we're outgoing, we need to modify our own base */
2.297 + m_base[lastidx].idx = q;
2.298 +
2.299 + /* Take the last index (curidx) out of the list. Technically we are not moving this,
2.300 + * since it's already being used by something else.
2.301 + */
2.302 + outgoing_count--;
2.303 +
2.304 + /* For each node in the "to move" list,
2.305 + * Relocate the node's info to the new position.
2.306 + */
2.307 + unsigned int idx, newidx, oldidx;
2.308 + for (unsigned int i=0; i<outgoing_count; i++)
2.309 + {
2.310 + idx = outgoing_list[i];
2.311 + newidx = q + idx;
2.312 + oldidx = outgoing_base + idx;
2.313 + if (oldidx == lastidx)
2.314 + {
2.315 + /* Important! Make sure we're not invalidating our sacred lastidx */
2.316 + lastidx = newidx;
2.317 + }
2.318 + /* Fully copy the node */
2.319 + memcpy(&m_base[newidx], &m_base[oldidx], sizeof(KTrieNode));
2.320 + if (m_base[oldidx].valset)
2.321 + {
2.322 + new (&m_base[newidx].value) K(m_base[oldidx].value);
2.323 + m_base[oldidx].value.~K();
2.324 + }
2.325 + assert(m_base[m_base[newidx].parent].mode == Node_Arc);
2.326 + /* Erase old data */
2.327 + memset(&m_base[oldidx], 0, sizeof(KTrieNode));
2.328 + /* If we are not a terminator, we have children we must take care of */
2.329 + if (m_base[newidx].mode == Node_Arc)
2.330 + {
2.331 + KTrieNode *check_base = &m_base[m_base[newidx].idx] + 1;
2.332 + outgoing_limit = (m_base + m_baseSize + 1) - check_base;
2.333 + if (outgoing_limit > 255)
2.334 + {
2.335 + outgoing_limit = 255;
2.336 + }
2.337 + for (unsigned int j=1; j<=outgoing_limit; j++, check_base++)
2.338 + {
2.339 + if (check_base->parent == oldidx)
2.340 + {
2.341 + check_base->parent = newidx;
2.342 + }
2.343 + }
2.344 + }
2.345 + }
2.346 +
2.347 + /* Take the invisible node and use it as our new node */
2.348 + node = &m_base[q + outgoing_list[outgoing_count]];
2.349 + }
2.350 +
2.351 + /* We're finally done! */
2.352 + node->parent = lastidx;
2.353 + if (*keyptr == '\0')
2.354 + {
2.355 + node->mode = Node_Arc;
2.356 + } else {
2.357 + node->idx = x_addstring(keyptr);
2.358 + node->mode = Node_Term;
2.359 + }
2.360 + node->valset = true;
2.361 + new (&node->value) K(obj);
2.362 +
2.363 + return true;
2.364 + } else {
2.365 + /* See what's in the next node - special case if terminator! */
2.366 + if (node->mode == Node_Term)
2.367 + {
2.368 + /* If we're a terminator, we need to handle CASE 3:
2.369 + * Insertion when a terminating collision occurs
2.370 + */
2.371 + char *term = &m_stringtab[node->idx];
2.372 + /* Do an initial browsing to make sure they're not the same string */
2.373 + if (strcmp(keyptr, term) == 0)
2.374 + {
2.375 + if (!node->valset)
2.376 + {
2.377 + node->valset = true;
2.378 + new (&node->value) K(obj);
2.379 + return true;
2.380 + }
2.381 + /* Same string. We can't insert. */
2.382 + return false;
2.383 + }
2.384 + /* For each matching character pair, we need to disband the terminator.
2.385 + * This splits the similar prefix into a single arc path.
2.386 + * First, save the old values so we can move them to a new node.
2.387 + * Next, for each loop:
2.388 + * Take the current (invalid) node, and point it to the next arc base.
2.389 + * Set the current node to the node at the next arc.
2.390 + */
2.391 + K oldvalue;
2.392 + bool oldvalset = node->valset;
2.393 + if (oldvalset)
2.394 + {
2.395 + oldvalue = node->value;
2.396 + }
2.397 + if (*term == *keyptr)
2.398 + {
2.399 + while (*term == *keyptr)
2.400 + {
2.401 + /* Find the next free slot in the check array.
2.402 + * This is the "vector base" essentially
2.403 + */
2.404 + q = x_check(*term);
2.405 + node = &m_base[curidx];
2.406 + /* Point the node to the next new base */
2.407 + node->idx = q;
2.408 + node->mode = Node_Arc;
2.409 + if (node->valset == true)
2.410 + {
2.411 + node->value.~K();
2.412 + node->valset = false;
2.413 + }
2.414 + /* Advance the input stream and local variables */
2.415 + lastidx = curidx;
2.416 + curidx = q + charval(*term);
2.417 + node = &m_base[curidx];
2.418 + /* Make sure the new current node has its parent set. */
2.419 + node->parent = lastidx;
2.420 + node->mode = Node_Arc; /* Just in case we run x_check again */
2.421 + *term = '\0'; /* Unmark the string table here */
2.422 + term++;
2.423 + keyptr++;
2.424 + }
2.425 + } else if (node->valset) {
2.426 + node->valset = false;
2.427 + node->value.~K();
2.428 + }
2.429 + /* We're done inserting new pairs. If one of them is exhausted,
2.430 + * we take special shortcuts.
2.431 + */
2.432 + if (*term == '\0') //EX: BADGERHOUSE added over B -> ADGER.
2.433 + {
2.434 + /* First backpatch the current node - it ends the newly split terminator.
2.435 + * In the example, this would mean the node is the production from R -> ?
2.436 + * This node ends the old BADGER, so we set it here.
2.437 + */
2.438 + node->valset = oldvalset;
2.439 + if (node->valset)
2.440 + {
2.441 + new (&node->value) K(oldvalue);
2.442 + }
2.443 +
2.444 + /* The terminator was split up, but pieces of keyptr remain.
2.445 + * We need to generate a new production, in this example, R -> H,
2.446 + * with H being a terminator to OUSE. Thus we get:
2.447 + * B,A,D,G,E,R*,H*->OUSE (* = value set).
2.448 + * NOTE: parent was last set at the end of the while loop.
2.449 + */
2.450 + /* Get the new base and apply re-basing */
2.451 + q = x_check(*keyptr);
2.452 + node = &m_base[curidx];
2.453 +
2.454 + node->idx = q;
2.455 + node->mode = Node_Arc;
2.456 + lastidx = curidx;
2.457 + /* Finish the final node */
2.458 + curidx = q + charval(*keyptr);
2.459 + node = &m_base[curidx];
2.460 + keyptr++;
2.461 + /* Optimize - don't add to string table if there's nothing more to eat */
2.462 + if (*keyptr == '\0')
2.463 + {
2.464 + node->mode = Node_Arc;
2.465 + } else {
2.466 + node->idx = x_addstring(keyptr);
2.467 + node->mode = Node_Term;
2.468 + }
2.469 + node->parent = lastidx;
2.470 + node->valset = true;
2.471 + new (&node->value) K(obj);
2.472 + } else if (*keyptr == '\0') { //EX: BADGER added over B -> ADGERHOUSE
2.473 + /* First backpatch the current node - it ends newly split input string.
2.474 + * This is the exact opposite of the above procedure.
2.475 + */
2.476 + node->valset = true;
2.477 + new (&node->value) K(obj);
2.478 +
2.479 + /* Get the new base and apply re-basing */
2.480 + q = x_check(*term);
2.481 + node = &m_base[curidx];
2.482 +
2.483 + node->idx = q;
2.484 + node->mode = Node_Arc;
2.485 + lastidx = curidx;
2.486 + /* Finish the final node */
2.487 + curidx = q + charval(*term);
2.488 + node = &m_base[curidx];
2.489 + term++;
2.490 + /* Optimize - don't add to string table if there's nothing more to eat */
2.491 + if (*term == '\0')
2.492 + {
2.493 + node->mode = Node_Arc;
2.494 + } else {
2.495 + node->idx = (term - m_stringtab); /* Already in the string table! */
2.496 + node->mode = Node_Term;
2.497 + }
2.498 + node->parent = lastidx;
2.499 + node->valset = oldvalset;
2.500 + if (node->valset)
2.501 + {
2.502 + new (&node->value) K(oldvalue);
2.503 + }
2.504 + } else {
2.505 + /* Finally, we have to create two new nodes instead of just one. */
2.506 + node->mode = Node_Arc;
2.507 +
2.508 + /* Get the new base and apply re-basing */
2.509 + q = x_check2(*keyptr, *term);
2.510 + node = &m_base[curidx];
2.511 +
2.512 + node->idx = q;
2.513 + lastidx = curidx;
2.514 +
2.515 + /* Re-create the old terminated node */
2.516 + curidx = q + charval(*term);
2.517 + node = &m_base[curidx];
2.518 + term++;
2.519 + node->valset = oldvalset;
2.520 + if (node->valset)
2.521 + {
2.522 + new (&node->value) K(oldvalue);
2.523 + }
2.524 + node->parent = lastidx;
2.525 + if (*term == '\0')
2.526 + {
2.527 + node->mode = Node_Arc;
2.528 + } else {
2.529 + node->mode = Node_Term;
2.530 + node->idx = (term - m_stringtab); /* Already in the string table! */
2.531 + }
2.532 +
2.533 + /* Create the new keyed input node */
2.534 + curidx = q + charval(*keyptr);
2.535 + node = &m_base[curidx];
2.536 + keyptr++;
2.537 + node->valset = true;
2.538 + new (&node->value) K(obj);
2.539 + node->parent = lastidx;
2.540 + if (*keyptr == '\0')
2.541 + {
2.542 + node->mode = Node_Arc;
2.543 + } else {
2.544 + node->mode = Node_Term;
2.545 + node->idx = x_addstring(keyptr);
2.546 + }
2.547 + }
2.548 +
2.549 + /* Phew! */
2.550 + return true;
2.551 + } else {
2.552 + assert(node->mode == Node_Arc);
2.553 + }
2.554 + }
2.555 + lastidx = curidx;
2.556 + } while (*keyptr != '\0');
2.557 +
2.558 + assert(node);
2.559 +
2.560 + /* If we've exhausted the string and we have a valid reached node,
2.561 + * the production rule already existed. Make sure it's valid to set first.
2.562 + */
2.563 +
2.564 + /* We have to be an Arc. If the last result was anything else, we would have returned a new
2.565 + * production earlier.
2.566 + */
2.567 + assert(node->mode == Node_Arc);
2.568 +
2.569 + if (!node->valset)
2.570 + {
2.571 + node->valset = true;
2.572 + new (&node->value) K(obj);
2.573 + return true;
2.574 + }
2.575 +
2.576 + return false;
2.577 + }
2.578 +private:
2.579 + KTrieNode *internal_retrieve(const char *key)
2.580 + {
2.581 + unsigned int lastidx = 1; /* the last node index */
2.582 + unsigned int curidx; /* current node index */
2.583 + const char *keyptr = key; /* input stream at current token */
2.584 + KTrieNode *node = NULL; /* current node being processed */
2.585 +
2.586 + if (!*key)
2.587 + {
2.588 + return NULL;
2.589 + }
2.590 +
2.591 + /* Start traversing at the root node */
2.592 + do
2.593 + {
2.594 + /* Find where the next character is, then advance */
2.595 + curidx = m_base[lastidx].idx;
2.596 + node = &m_base[curidx];
2.597 + curidx += charval(*keyptr);
2.598 + node = &m_base[curidx];
2.599 + keyptr++;
2.600 +
2.601 + /* Check if this slot is supposed to be empty or is a collision */
2.602 + if ((curidx > m_baseSize) || node->mode == Node_Unused || node->parent != lastidx)
2.603 + {
2.604 + return NULL;
2.605 + } else if (node->mode == Node_Term) {
2.606 + char *term = &m_stringtab[node->idx];
2.607 + if (strcmp(keyptr, term) == 0)
2.608 + {
2.609 + break;
2.610 + }
2.611 + }
2.612 + lastidx = curidx;
2.613 + } while (*keyptr != '\0');
2.614 +
2.615 + return node;
2.616 + }
2.617 + bool grow()
2.618 + {
2.619 + /* The current # of nodes in the tree is trie->baseSize + 1 */
2.620 + unsigned int cur_size = m_baseSize;
2.621 + unsigned int new_size = cur_size * 2;
2.622 +
2.623 + KTrieNode *new_base = (KTrieNode *)malloc((new_size + 1) * sizeof(KTrieNode));
2.624 + if (!new_base)
2.625 + {
2.626 + return false;
2.627 + }
2.628 +
2.629 + memcpy(new_base, m_base, sizeof(KTrieNode *) * (m_baseSize + 1));
2.630 + memset(&new_base[cur_size + 1], 0, (new_size - cur_size) * sizeof(KTrieNode));
2.631 +
2.632 + for (size_t i = 0; i <= m_baseSize; i++)
2.633 + {
2.634 + if (m_base[i].valset)
2.635 + {
2.636 + /* Placement construct+copy the object, then placement destroy the old. */
2.637 + new (&new_base[i].value) K(m_base[i].value);
2.638 + m_base[i].value.~K();
2.639 + }
2.640 + }
2.641 +
2.642 + free(m_base);
2.643 + m_base = new_base;
2.644 + m_baseSize = new_size;
2.645 +
2.646 + return true;
2.647 + }
2.648 + inline unsigned char charval(char c)
2.649 + {
2.650 + return (unsigned char)c;
2.651 + }
2.652 + void internal_clear()
2.653 + {
2.654 + m_tail = 0;
2.655 +
2.656 + memset(m_base, 0, sizeof(KTrieNode) * (m_baseSize + 1));
2.657 + memset(m_stringtab, 0, sizeof(char) * m_stSize);
2.658 +
2.659 + /* Sentinel root node */
2.660 + m_base[1].idx = 1;
2.661 + m_base[1].mode = Node_Arc;
2.662 + m_base[1].parent = 1;
2.663 + }
2.664 + void run_destructors()
2.665 + {
2.666 + for (size_t i = 0; i <= m_baseSize; i++)
2.667 + {
2.668 + if (m_base[i].valset)
2.669 + {
2.670 + m_base[i].value.~K();
2.671 + }
2.672 + }
2.673 + }
2.674 + unsigned int x_addstring(const char *ptr)
2.675 + {
2.676 + size_t len = strlen(ptr) + 1;
2.677 +
2.678 + if (m_tail + len >= m_stSize)
2.679 + {
2.680 + while (m_tail + len >= m_stSize)
2.681 + {
2.682 + m_stSize *= 2;
2.683 + }
2.684 + m_stringtab = (char *)realloc(m_stringtab,m_stSize);
2.685 + }
2.686 +
2.687 + unsigned int tail = m_tail;
2.688 + strcpy(&m_stringtab[tail], ptr);
2.689 + m_tail += len;
2.690 +
2.691 + return tail;
2.692 + }
2.693 + unsigned int x_check(char c, unsigned int start=1)
2.694 + {
2.695 + unsigned char _c = charval(c);
2.696 + unsigned int to_check = m_baseSize - _c;
2.697 + for (unsigned int i=start; i<=to_check; i++)
2.698 + {
2.699 + if (m_base[i+_c].mode == Node_Unused)
2.700 + {
2.701 + return i;
2.702 + }
2.703 + }
2.704 +
2.705 + grow();
2.706 +
2.707 + return x_check(c, to_check+1);
2.708 + }
2.709 + unsigned int x_check2(char c1, char c2, unsigned int start=1)
2.710 + {
2.711 + unsigned char _c1 = charval(c1);
2.712 + unsigned char _c2 = charval(c2);
2.713 + unsigned int to_check = m_baseSize - (_c1 > _c2 ? _c1 : _c2);
2.714 + for (unsigned int i=start; i<=to_check; i++)
2.715 + {
2.716 + if (m_base[i+_c1].mode == Node_Unused
2.717 + && m_base[i+_c2].mode == Node_Unused)
2.718 + {
2.719 + return i;
2.720 + }
2.721 + }
2.722 +
2.723 + grow();
2.724 +
2.725 + return x_check2(c1, c2, to_check+1);
2.726 + }
2.727 + unsigned int x_check_multi(
2.728 + unsigned int offsets[],
2.729 + unsigned int count,
2.730 + unsigned int start=1)
2.731 + {
2.732 + KTrieNode *cur;
2.733 + unsigned int to_check = m_baseSize;
2.734 + unsigned int highest = 0;
2.735 +
2.736 + for (unsigned int i=0; i<count; i++)
2.737 + {
2.738 + if (offsets[i] > highest)
2.739 + {
2.740 + highest = offsets[i];
2.741 + }
2.742 + }
2.743 +
2.744 + to_check -= highest;
2.745 +
2.746 + for (unsigned int i=start; i<=to_check; i++)
2.747 + {
2.748 + bool okay = true;
2.749 + for (unsigned int j=0; j<count; j++)
2.750 + {
2.751 + cur = &m_base[i+offsets[j]];
2.752 + if (cur->mode != Node_Unused)
2.753 + {
2.754 + okay = false;
2.755 + break;
2.756 + }
2.757 + }
2.758 + if (okay)
2.759 + {
2.760 + return i;
2.761 + }
2.762 + }
2.763 +
2.764 + grow();
2.765 +
2.766 + return x_check_multi(offsets, count, to_check+1);
2.767 + }
2.768 +private:
2.769 + KTrieNode *m_base; /* Base array for the sparse tables */
2.770 + char *m_stringtab; /* String table pointer */
2.771 + unsigned int m_baseSize; /* Size of the base array, in members */
2.772 + unsigned int m_stSize; /* Size of the string table, in bytes */
2.773 + unsigned int m_tail; /* Current unused offset into the string table */
2.774 +};
2.775 +
2.776 +#endif //_INCLUDE_SOURCEMOD_TEMPLATED_TRIE_H_
