1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/core/smn_adt_trie.cpp Mon Dec 10 05:14:37 2007 +0000
1.3 @@ -0,0 +1,513 @@
1.4 +/**
1.5 + * vim: set ts=4 :
1.6 + * =============================================================================
1.7 + * SourceMod
1.8 + * Copyright (C) 2004-2007 AlliedModders LLC. All rights reserved.
1.9 + * =============================================================================
1.10 + *
1.11 + * This program is free software; you can redistribute it and/or modify it under
1.12 + * the terms of the GNU General Public License, version 3.0, as published by the
1.13 + * Free Software Foundation.
1.14 + *
1.15 + * This program is distributed in the hope that it will be useful, but WITHOUT
1.16 + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
1.17 + * FOR A PARTICULAR PURPOSE. See the GNU General Public License for more
1.18 + * details.
1.19 + *
1.20 + * You should have received a copy of the GNU General Public License along with
1.21 + * this program. If not, see <http://www.gnu.org/licenses/>.
1.22 + *
1.23 + * As a special exception, AlliedModders LLC gives you permission to link the
1.24 + * code of this program (as well as its derivative works) to "Half-Life 2," the
1.25 + * "Source Engine," the "SourcePawn JIT," and any Game MODs that run on software
1.26 + * by the Valve Corporation. You must obey the GNU General Public License in
1.27 + * all respects for all other code used. Additionally, AlliedModders LLC grants
1.28 + * this exception to all derivative works. AlliedModders LLC defines further
1.29 + * exceptions, found in LICENSE.txt (as of this writing, version JULY-31-2007),
1.30 + * or <http://www.sourcemod.net/license.php>.
1.31 + *
1.32 + * Version: $Id$
1.33 + */
1.34 +
1.35 +#include <malloc.h>
1.36 +#include "sm_globals.h"
1.37 +#include "sm_stringutil.h"
1.38 +#include "HandleSys.h"
1.39 +#include "sm_trie_tpl.h"
1.40 +
1.41 +HandleType_t htCellTrie;
1.42 +
1.43 +enum TrieNodeType
1.44 +{
1.45 + TrieNode_Cell,
1.46 + TrieNode_CellArray,
1.47 + TrieNode_String,
1.48 +};
1.49 +
1.50 +struct SmartTrieNode
1.51 +{
1.52 + SmartTrieNode()
1.53 + {
1.54 + ptr = NULL;
1.55 + type = TrieNode_Cell;
1.56 + }
1.57 + SmartTrieNode(const SmartTrieNode &obj)
1.58 + {
1.59 + type = obj.type;
1.60 + ptr = obj.ptr;
1.61 + data = obj.data;
1.62 + data_len = obj.data_len;
1.63 + }
1.64 + SmartTrieNode & operator =(const SmartTrieNode &src)
1.65 + {
1.66 + type = src.type;
1.67 + ptr = src.ptr;
1.68 + data = src.data;
1.69 + data_len = src.data_len;
1.70 + return *this;
1.71 + }
1.72 + TrieNodeType type;
1.73 + cell_t *ptr;
1.74 + cell_t data;
1.75 + cell_t data_len;
1.76 +};
1.77 +
1.78 +struct CellTrie
1.79 +{
1.80 + KTrie<SmartTrieNode> trie;
1.81 + cell_t mem_usage;
1.82 +};
1.83 +
1.84 +class TrieHelpers :
1.85 + public SMGlobalClass,
1.86 + public IHandleTypeDispatch
1.87 +{
1.88 +public: //SMGlobalClass
1.89 + void OnSourceModAllInitialized()
1.90 + {
1.91 + htCellTrie = g_HandleSys.CreateType("Trie", this, 0, NULL, NULL, g_pCoreIdent, NULL);
1.92 + }
1.93 + void OnSourceModShutdown()
1.94 + {
1.95 + g_HandleSys.RemoveType(htCellTrie, g_pCoreIdent);
1.96 + }
1.97 +public: //IHandleTypeDispatch
1.98 + static void DestroySmartTrieNode(SmartTrieNode *pNode)
1.99 + {
1.100 + free(pNode->ptr);
1.101 + }
1.102 + void OnHandleDestroy(HandleType_t type, void *object)
1.103 + {
1.104 + CellTrie *pTrie = (CellTrie *)object;
1.105 +
1.106 + pTrie->trie.run_destructor(DestroySmartTrieNode);
1.107 +
1.108 + delete pTrie;
1.109 + }
1.110 + bool GetHandleApproxSize(HandleType_t type, void *object, unsigned int *pSize)
1.111 + {
1.112 + CellTrie *pArray = (CellTrie *)object;
1.113 + *pSize = sizeof(CellTrie) + pArray->mem_usage + pArray->trie.mem_usage();
1.114 + return true;
1.115 + }
1.116 +} s_CellTrieHelpers;
1.117 +
1.118 +static cell_t CreateTrie(IPluginContext *pContext, const cell_t *params)
1.119 +{
1.120 + CellTrie *pTrie = new CellTrie;
1.121 + Handle_t hndl;
1.122 +
1.123 + pTrie->mem_usage = 0;
1.124 +
1.125 + if ((hndl = g_HandleSys.CreateHandle(htCellTrie, pTrie, pContext->GetIdentity(), g_pCoreIdent, NULL))
1.126 + == BAD_HANDLE)
1.127 + {
1.128 + delete pTrie;
1.129 + return BAD_HANDLE;
1.130 + }
1.131 +
1.132 + return hndl;
1.133 +}
1.134 +
1.135 +static void UpdateNodeCells(CellTrie *pTrie, SmartTrieNode *pData, const cell_t *cells, cell_t num_cells)
1.136 +{
1.137 + if (num_cells == 1)
1.138 + {
1.139 + pData->data = *cells;
1.140 + pData->type = TrieNode_Cell;
1.141 + }
1.142 + else
1.143 + {
1.144 + pData->type = TrieNode_CellArray;
1.145 + if (pData->ptr == NULL)
1.146 + {
1.147 + pData->ptr = (cell_t *)malloc(num_cells * sizeof(cell_t));
1.148 + pData->data_len = num_cells;
1.149 + pTrie->mem_usage += (pData->data_len * sizeof(cell_t));
1.150 + }
1.151 + else if (pData->data_len < num_cells)
1.152 + {
1.153 + pData->ptr = (cell_t *)realloc(pData->ptr, num_cells * sizeof(cell_t));
1.154 + pTrie->mem_usage += (num_cells - pData->data_len) * sizeof(cell_t);
1.155 + pData->data_len = num_cells;
1.156 + }
1.157 + if (num_cells != 0)
1.158 + {
1.159 + memcpy(pData->ptr, cells, sizeof(cell_t) * num_cells);
1.160 + }
1.161 + pData->data = num_cells;
1.162 + }
1.163 +}
1.164 +
1.165 +static void UpdateNodeString(CellTrie *pTrie, SmartTrieNode *pData, const char *str)
1.166 +{
1.167 + size_t len = strlen(str);
1.168 + cell_t num_cells = (len + sizeof(cell_t)) / sizeof(cell_t);
1.169 +
1.170 + if (pData->ptr == NULL)
1.171 + {
1.172 + pData->ptr = (cell_t *)malloc(num_cells * sizeof(cell_t));
1.173 + pData->data_len = num_cells;
1.174 + pTrie->mem_usage += (pData->data_len * sizeof(cell_t));
1.175 + }
1.176 + else if (pData->data_len < num_cells)
1.177 + {
1.178 + pData->ptr = (cell_t *)realloc(pData->ptr, num_cells * sizeof(cell_t));
1.179 + pTrie->mem_usage += (num_cells - pData->data_len) * sizeof(cell_t);
1.180 + pData->data_len = num_cells;
1.181 + }
1.182 +
1.183 + strcpy((char *)pData->ptr, str);
1.184 + pData->data = len;
1.185 + pData->type = TrieNode_String;
1.186 +}
1.187 +
1.188 +static cell_t SetTrieValue(IPluginContext *pContext, const cell_t *params)
1.189 +{
1.190 + Handle_t hndl;
1.191 + CellTrie *pTrie;
1.192 + HandleError err;
1.193 + HandleSecurity sec = HandleSecurity(pContext->GetIdentity(), g_pCoreIdent);
1.194 +
1.195 + hndl = params[1];
1.196 +
1.197 + if ((err = g_HandleSys.ReadHandle(hndl, htCellTrie, &sec, (void **)&pTrie))
1.198 + != HandleError_None)
1.199 + {
1.200 + return pContext->ThrowNativeError("Invalid Handle %x (error %d)", hndl, err);
1.201 + }
1.202 +
1.203 + char *key;
1.204 + pContext->LocalToString(params[2], &key);
1.205 +
1.206 + SmartTrieNode *pNode;
1.207 + if ((pNode = pTrie->trie.retrieve(key)) == NULL)
1.208 + {
1.209 + SmartTrieNode node;
1.210 + UpdateNodeCells(pTrie, &node, ¶ms[3], 1);
1.211 + return pTrie->trie.insert(key, node) ? 1 : 0;
1.212 + }
1.213 +
1.214 + if (!params[4])
1.215 + {
1.216 + return 0;
1.217 + }
1.218 +
1.219 + UpdateNodeCells(pTrie, pNode, ¶ms[3], 1);
1.220 +
1.221 + return 1;
1.222 +}
1.223 +
1.224 +static cell_t SetTrieArray(IPluginContext *pContext, const cell_t *params)
1.225 +{
1.226 + Handle_t hndl;
1.227 + CellTrie *pTrie;
1.228 + HandleError err;
1.229 + HandleSecurity sec = HandleSecurity(pContext->GetIdentity(), g_pCoreIdent);
1.230 +
1.231 + hndl = params[1];
1.232 +
1.233 + if ((err = g_HandleSys.ReadHandle(hndl, htCellTrie, &sec, (void **)&pTrie))
1.234 + != HandleError_None)
1.235 + {
1.236 + return pContext->ThrowNativeError("Invalid Handle %x (error %d)", hndl, err);
1.237 + }
1.238 +
1.239 + if (params[4] < 0)
1.240 + {
1.241 + return pContext->ThrowNativeError("Invalid array size: %d", params[4]);
1.242 + }
1.243 +
1.244 + char *key;
1.245 + cell_t *array;
1.246 + pContext->LocalToString(params[2], &key);
1.247 + pContext->LocalToPhysAddr(params[3], &array);
1.248 +
1.249 + SmartTrieNode *pNode;
1.250 + if ((pNode = pTrie->trie.retrieve(key)) == NULL)
1.251 + {
1.252 + SmartTrieNode node;
1.253 + UpdateNodeCells(pTrie, &node, array, params[4]);
1.254 + if (!pTrie->trie.insert(key, node))
1.255 + {
1.256 + free(node.ptr);
1.257 + return 0;
1.258 + }
1.259 + return 1;
1.260 + }
1.261 +
1.262 + if (!params[4])
1.263 + {
1.264 + return 0;
1.265 + }
1.266 +
1.267 + UpdateNodeCells(pTrie, pNode, array, params[4]);
1.268 +
1.269 + return 1;
1.270 +}
1.271 +
1.272 +static cell_t SetTrieString(IPluginContext *pContext, const cell_t *params)
1.273 +{
1.274 + Handle_t hndl;
1.275 + CellTrie *pTrie;
1.276 + HandleError err;
1.277 + HandleSecurity sec = HandleSecurity(pContext->GetIdentity(), g_pCoreIdent);
1.278 +
1.279 + hndl = params[1];
1.280 +
1.281 + if ((err = g_HandleSys.ReadHandle(hndl, htCellTrie, &sec, (void **)&pTrie))
1.282 + != HandleError_None)
1.283 + {
1.284 + return pContext->ThrowNativeError("Invalid Handle %x (error %d)", hndl, err);
1.285 + }
1.286 +
1.287 + char *key, *val;
1.288 + pContext->LocalToString(params[2], &key);
1.289 + pContext->LocalToString(params[3], &val);
1.290 +
1.291 + SmartTrieNode *pNode;
1.292 + if ((pNode = pTrie->trie.retrieve(key)) == NULL)
1.293 + {
1.294 + SmartTrieNode node;
1.295 + UpdateNodeString(pTrie, &node, val);
1.296 + if (!pTrie->trie.insert(key, node))
1.297 + {
1.298 + free(node.ptr);
1.299 + return 0;
1.300 + }
1.301 + return 1;
1.302 + }
1.303 +
1.304 + if (!params[4])
1.305 + {
1.306 + return 0;
1.307 + }
1.308 +
1.309 + UpdateNodeString(pTrie, pNode, val);
1.310 +
1.311 + return 1;
1.312 +}
1.313 +
1.314 +static cell_t RemoveFromTrie(IPluginContext *pContext, const cell_t *params)
1.315 +{
1.316 + Handle_t hndl;
1.317 + CellTrie *pTrie;
1.318 + HandleError err;
1.319 + HandleSecurity sec = HandleSecurity(pContext->GetIdentity(), g_pCoreIdent);
1.320 +
1.321 + hndl = params[1];
1.322 +
1.323 + if ((err = g_HandleSys.ReadHandle(hndl, htCellTrie, &sec, (void **)&pTrie))
1.324 + != HandleError_None)
1.325 + {
1.326 + return pContext->ThrowNativeError("Invalid Handle %x (error %d)", hndl, err);
1.327 + }
1.328 +
1.329 + char *key;
1.330 + pContext->LocalToString(params[2], &key);
1.331 +
1.332 + SmartTrieNode *pNode;
1.333 + if ((pNode = pTrie->trie.retrieve(key)) == NULL)
1.334 + {
1.335 + return 0;
1.336 + }
1.337 +
1.338 + free(pNode->ptr);
1.339 + pNode->ptr = NULL;
1.340 +
1.341 + return pTrie->trie.remove(key) ? 1 : 0;
1.342 +}
1.343 +
1.344 +static cell_t ClearTrie(IPluginContext *pContext, const cell_t *params)
1.345 +{
1.346 + Handle_t hndl;
1.347 + CellTrie *pTrie;
1.348 + HandleError err;
1.349 + HandleSecurity sec = HandleSecurity(pContext->GetIdentity(), g_pCoreIdent);
1.350 +
1.351 + hndl = params[1];
1.352 +
1.353 + if ((err = g_HandleSys.ReadHandle(hndl, htCellTrie, &sec, (void **)&pTrie))
1.354 + != HandleError_None)
1.355 + {
1.356 + return pContext->ThrowNativeError("Invalid Handle %x (error %d)", hndl, err);
1.357 + }
1.358 +
1.359 + pTrie->trie.run_destructor(TrieHelpers::DestroySmartTrieNode);
1.360 + pTrie->trie.clear();
1.361 +
1.362 + return 1;
1.363 +}
1.364 +
1.365 +static cell_t GetTrieValue(IPluginContext *pContext, const cell_t *params)
1.366 +{
1.367 + Handle_t hndl;
1.368 + CellTrie *pTrie;
1.369 + HandleError err;
1.370 + HandleSecurity sec = HandleSecurity(pContext->GetIdentity(), g_pCoreIdent);
1.371 +
1.372 + hndl = params[1];
1.373 +
1.374 + if ((err = g_HandleSys.ReadHandle(hndl, htCellTrie, &sec, (void **)&pTrie))
1.375 + != HandleError_None)
1.376 + {
1.377 + return pContext->ThrowNativeError("Invalid Handle %x (error %d)", hndl, err);
1.378 + }
1.379 +
1.380 + char *key;
1.381 + cell_t *pValue;
1.382 + pContext->LocalToString(params[2], &key);
1.383 + pContext->LocalToPhysAddr(params[3], &pValue);
1.384 +
1.385 + SmartTrieNode *pNode;
1.386 + if ((pNode = pTrie->trie.retrieve(key)) == NULL)
1.387 + {
1.388 + return 0;
1.389 + }
1.390 +
1.391 + if (pNode->type == TrieNode_Cell)
1.392 + {
1.393 + *pValue = pNode->data;
1.394 + return 1;
1.395 + }
1.396 +
1.397 + return 0;
1.398 +}
1.399 +
1.400 +static cell_t GetTrieArray(IPluginContext *pContext, const cell_t *params)
1.401 +{
1.402 + Handle_t hndl;
1.403 + CellTrie *pTrie;
1.404 + HandleError err;
1.405 + HandleSecurity sec = HandleSecurity(pContext->GetIdentity(), g_pCoreIdent);
1.406 +
1.407 + hndl = params[1];
1.408 +
1.409 + if ((err = g_HandleSys.ReadHandle(hndl, htCellTrie, &sec, (void **)&pTrie))
1.410 + != HandleError_None)
1.411 + {
1.412 + return pContext->ThrowNativeError("Invalid Handle %x (error %d)", hndl, err);
1.413 + }
1.414 +
1.415 + if (params[4] < 0)
1.416 + {
1.417 + return pContext->ThrowNativeError("Invalid array size: %d", params[4]);
1.418 + }
1.419 +
1.420 + char *key;
1.421 + cell_t *pValue, *pSize;
1.422 + pContext->LocalToString(params[2], &key);
1.423 + pContext->LocalToPhysAddr(params[3], &pValue);
1.424 + pContext->LocalToPhysAddr(params[5], &pSize);
1.425 +
1.426 + SmartTrieNode *pNode;
1.427 + if ((pNode = pTrie->trie.retrieve(key)) == NULL
1.428 + || pNode->type != TrieNode_CellArray)
1.429 + {
1.430 + return 0;
1.431 + }
1.432 +
1.433 + if (pNode->ptr == NULL)
1.434 + {
1.435 + *pSize = 0;
1.436 + return 1;
1.437 + }
1.438 +
1.439 + if (pNode->data > params[4])
1.440 + {
1.441 + *pSize = params[4];
1.442 + }
1.443 + else if (params[4] != 0)
1.444 + {
1.445 + *pSize = pNode->data;
1.446 + }
1.447 + else
1.448 + {
1.449 + return 1;
1.450 + }
1.451 +
1.452 + memcpy(pValue, pNode->ptr, sizeof(cell_t) * pSize[0]);
1.453 +
1.454 + return 1;
1.455 +}
1.456 +
1.457 +static cell_t GetTrieString(IPluginContext *pContext, const cell_t *params)
1.458 +{
1.459 + Handle_t hndl;
1.460 + CellTrie *pTrie;
1.461 + HandleError err;
1.462 + HandleSecurity sec = HandleSecurity(pContext->GetIdentity(), g_pCoreIdent);
1.463 +
1.464 + hndl = params[1];
1.465 +
1.466 + if ((err = g_HandleSys.ReadHandle(hndl, htCellTrie, &sec, (void **)&pTrie))
1.467 + != HandleError_None)
1.468 + {
1.469 + return pContext->ThrowNativeError("Invalid Handle %x (error %d)", hndl, err);
1.470 + }
1.471 +
1.472 + if (params[4] < 0)
1.473 + {
1.474 + return pContext->ThrowNativeError("Invalid buffer size: %d", params[4]);
1.475 + }
1.476 +
1.477 + char *key;
1.478 + cell_t *pSize;
1.479 + pContext->LocalToString(params[2], &key);
1.480 + pContext->LocalToPhysAddr(params[5], &pSize);
1.481 +
1.482 + SmartTrieNode *pNode;
1.483 + if ((pNode = pTrie->trie.retrieve(key)) == NULL
1.484 + || pNode->type != TrieNode_String)
1.485 + {
1.486 + return 0;
1.487 + }
1.488 +
1.489 + if (pNode->ptr == NULL)
1.490 + {
1.491 + *pSize = 0;
1.492 + pContext->StringToLocal(params[3], params[4], "");
1.493 + return 1;
1.494 + }
1.495 +
1.496 + size_t written;
1.497 + pContext->StringToLocalUTF8(params[3], params[4], (char *)pNode->ptr, &written);
1.498 +
1.499 + *pSize = (cell_t)written;
1.500 +
1.501 + return 1;
1.502 +}
1.503 +
1.504 +REGISTER_NATIVES(trieNatives)
1.505 +{
1.506 + {"ClearTrie", ClearTrie},
1.507 + {"CreateTrie", CreateTrie},
1.508 + {"GetTrieArray", GetTrieArray},
1.509 + {"GetTrieString", GetTrieString},
1.510 + {"GetTrieValue", GetTrieValue},
1.511 + {"RemoveFromTrie", RemoveFromTrie},
1.512 + {"SetTrieArray", SetTrieArray},
1.513 + {"SetTrieString", SetTrieString},
1.514 + {"SetTrieValue", SetTrieValue},
1.515 + {NULL, NULL},
1.516 +};
