Home - sourcemod-central - file revision - core/smn_adt_trie.cpp@e6e2f440376d Mercurial
summary | shortlog | changelog | graph | tags | branches | files | changeset | file | latest | revisions | annotate | diff | raw | help
core/smn_adt_trie.cpp
author David Anderson <dvander@alliedmods.net>
Mon Dec 10 22:20:53 2007 +0000 (2007-12-10)
changeset 1783 e6e2f440376d
parent 1779 68c6036834d4
child 1829 97cd42e800e8
permissions -rw-r--r--
- fixed amb1237 part 1 - maplists.cfg missing could cause ReadMapList() to fail
- fixed amb1237 part 2 - nextmap could fail in certain cases with mapchooser present 
     1 /**
     2  * vim: set ts=4 :
     3  * =============================================================================
     4  * SourceMod
     5  * Copyright (C) 2004-2007 AlliedModders LLC.  All rights reserved.
     6  * =============================================================================
     7  *
     8  * This program is free software; you can redistribute it and/or modify it under
     9  * the terms of the GNU General Public License, version 3.0, as published by the
    10  * Free Software Foundation.
    11  * 
    12  * This program is distributed in the hope that it will be useful, but WITHOUT
    13  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
    14  * FOR A PARTICULAR PURPOSE.  See the GNU General Public License for more
    15  * details.
    16  *
    17  * You should have received a copy of the GNU General Public License along with
    18  * this program.  If not, see <http://www.gnu.org/licenses/>.
    19  *
    20  * As a special exception, AlliedModders LLC gives you permission to link the
    21  * code of this program (as well as its derivative works) to "Half-Life 2," the
    22  * "Source Engine," the "SourcePawn JIT," and any Game MODs that run on software
    23  * by the Valve Corporation.  You must obey the GNU General Public License in
    24  * all respects for all other code used.  Additionally, AlliedModders LLC grants
    25  * this exception to all derivative works.  AlliedModders LLC defines further
    26  * exceptions, found in LICENSE.txt (as of this writing, version JULY-31-2007),
    27  * or <http://www.sourcemod.net/license.php>.
    28  *
    29  * Version: $Id$
    30  */
    31 
    32 #include <malloc.h>
    33 #include "sm_globals.h"
    34 #include "sm_stringutil.h"
    35 #include "HandleSys.h"
    36 #include "sm_trie_tpl.h"
    37 
    38 HandleType_t htCellTrie;
    39 
    40 enum TrieNodeType
    41 {
    42 	TrieNode_Cell,
    43 	TrieNode_CellArray,
    44 	TrieNode_String,
    45 };
    46 
    47 struct SmartTrieNode
    48 {
    49 	SmartTrieNode()
    50 	{
    51 		ptr = NULL;
    52 		type = TrieNode_Cell;
    53 	}
    54 	SmartTrieNode(const SmartTrieNode &obj)
    55 	{
    56 		type = obj.type;
    57 		ptr = obj.ptr;
    58 		data = obj.data;
    59 		data_len = obj.data_len;
    60 	}
    61 	SmartTrieNode & operator =(const SmartTrieNode &src)
    62 	{
    63 		type = src.type;
    64 		ptr = src.ptr;
    65 		data = src.data;
    66 		data_len = src.data_len;
    67 		return *this;
    68 	}
    69 	TrieNodeType type;
    70 	cell_t *ptr;
    71 	cell_t data;
    72 	cell_t data_len;
    73 };
    74 
    75 struct CellTrie
    76 {
    77 	KTrie<SmartTrieNode> trie;
    78 	cell_t mem_usage;
    79 };
    80 
    81 class TrieHelpers : 
    82 	public SMGlobalClass,
    83 	public IHandleTypeDispatch
    84 {
    85 public: //SMGlobalClass
    86 	void OnSourceModAllInitialized()
    87 	{
    88 		htCellTrie = g_HandleSys.CreateType("Trie", this, 0, NULL, NULL, g_pCoreIdent, NULL);
    89 	}
    90 	void OnSourceModShutdown()
    91 	{
    92 		g_HandleSys.RemoveType(htCellTrie, g_pCoreIdent);
    93 	}
    94 public: //IHandleTypeDispatch
    95 	static void DestroySmartTrieNode(SmartTrieNode *pNode)
    96 	{
    97 		free(pNode->ptr);
    98 	}
    99 	void OnHandleDestroy(HandleType_t type, void *object)
   100 	{
   101 		CellTrie *pTrie = (CellTrie *)object;
   102 
   103 		pTrie->trie.run_destructor(DestroySmartTrieNode);
   104 
   105 		delete pTrie;
   106 	}
   107 	bool GetHandleApproxSize(HandleType_t type, void *object, unsigned int *pSize)
   108 	{
   109 		CellTrie *pArray = (CellTrie *)object;
   110 		*pSize = sizeof(CellTrie) + pArray->mem_usage + pArray->trie.mem_usage();
   111 		return true;
   112 	}
   113 } s_CellTrieHelpers;
   114 
   115 static cell_t CreateTrie(IPluginContext *pContext, const cell_t *params)
   116 {
   117 	CellTrie *pTrie = new CellTrie;
   118 	Handle_t hndl;
   119 
   120 	pTrie->mem_usage = 0;
   121 
   122 	if ((hndl = g_HandleSys.CreateHandle(htCellTrie, pTrie, pContext->GetIdentity(), g_pCoreIdent, NULL))
   123 		== BAD_HANDLE)
   124 	{
   125 		delete pTrie;
   126 		return BAD_HANDLE;
   127 	}
   128 
   129 	return hndl;
   130 }
   131 
   132 static void UpdateNodeCells(CellTrie *pTrie, SmartTrieNode *pData, const cell_t *cells, cell_t num_cells)
   133 {
   134 	if (num_cells == 1)
   135 	{
   136 		pData->data = *cells;
   137 		pData->type = TrieNode_Cell;
   138 	}
   139 	else
   140 	{
   141 		pData->type = TrieNode_CellArray;
   142 		if (pData->ptr == NULL)
   143 		{
   144 			pData->ptr = (cell_t *)malloc(num_cells * sizeof(cell_t));
   145 			pData->data_len = num_cells;
   146 			pTrie->mem_usage += (pData->data_len * sizeof(cell_t));
   147 		}
   148 		else if (pData->data_len < num_cells)
   149 		{
   150 			pData->ptr = (cell_t *)realloc(pData->ptr, num_cells * sizeof(cell_t));
   151 			pTrie->mem_usage += (num_cells - pData->data_len) * sizeof(cell_t);
   152 			pData->data_len = num_cells;
   153 		}
   154 		if (num_cells != 0)
   155 		{
   156 			memcpy(pData->ptr, cells, sizeof(cell_t) * num_cells);
   157 		}
   158 		pData->data = num_cells;
   159 	}
   160 }
   161 
   162 static void UpdateNodeString(CellTrie *pTrie, SmartTrieNode *pData, const char *str)
   163 {
   164 	size_t len = strlen(str);
   165 	cell_t num_cells = (len + sizeof(cell_t)) / sizeof(cell_t);
   166 
   167 	if (pData->ptr == NULL)
   168 	{
   169 		pData->ptr = (cell_t *)malloc(num_cells * sizeof(cell_t));
   170 		pData->data_len = num_cells;
   171 		pTrie->mem_usage += (pData->data_len * sizeof(cell_t));
   172 	}
   173 	else if (pData->data_len < num_cells)
   174 	{
   175 		pData->ptr = (cell_t *)realloc(pData->ptr, num_cells * sizeof(cell_t));
   176 		pTrie->mem_usage += (num_cells - pData->data_len) * sizeof(cell_t);
   177 		pData->data_len = num_cells;
   178 	}
   179 
   180 	strcpy((char *)pData->ptr, str);
   181 	pData->data = len;
   182 	pData->type = TrieNode_String;
   183 }
   184 
   185 static cell_t SetTrieValue(IPluginContext *pContext, const cell_t *params)
   186 {
   187 	Handle_t hndl;
   188 	CellTrie *pTrie;
   189 	HandleError err;
   190 	HandleSecurity sec = HandleSecurity(pContext->GetIdentity(), g_pCoreIdent);
   191 
   192 	hndl = params[1];
   193 
   194 	if ((err = g_HandleSys.ReadHandle(hndl, htCellTrie, &sec, (void **)&pTrie))
   195 		!= HandleError_None)
   196 	{
   197 		return pContext->ThrowNativeError("Invalid Handle %x (error %d)", hndl, err);
   198 	}
   199 
   200 	char *key;
   201 	pContext->LocalToString(params[2], &key);
   202 
   203 	SmartTrieNode *pNode;
   204 	if ((pNode = pTrie->trie.retrieve(key)) == NULL)
   205 	{
   206 		SmartTrieNode node;
   207 		UpdateNodeCells(pTrie, &node, &params[3], 1);
   208 		return pTrie->trie.insert(key, node) ? 1 : 0;
   209 	}
   210 
   211 	if (!params[4])
   212 	{
   213 		return 0;
   214 	}
   215 
   216 	UpdateNodeCells(pTrie, pNode, &params[3], 1);
   217 
   218 	return 1;
   219 }
   220 
   221 static cell_t SetTrieArray(IPluginContext *pContext, const cell_t *params)
   222 {
   223 	Handle_t hndl;
   224 	CellTrie *pTrie;
   225 	HandleError err;
   226 	HandleSecurity sec = HandleSecurity(pContext->GetIdentity(), g_pCoreIdent);
   227 
   228 	hndl = params[1];
   229 
   230 	if ((err = g_HandleSys.ReadHandle(hndl, htCellTrie, &sec, (void **)&pTrie))
   231 		!= HandleError_None)
   232 	{
   233 		return pContext->ThrowNativeError("Invalid Handle %x (error %d)", hndl, err);
   234 	}
   235 
   236 	if (params[4] < 0)
   237 	{
   238 		return pContext->ThrowNativeError("Invalid array size: %d", params[4]);
   239 	}
   240 
   241 	char *key;
   242 	cell_t *array;
   243 	pContext->LocalToString(params[2], &key);
   244 	pContext->LocalToPhysAddr(params[3], &array);
   245 
   246 	SmartTrieNode *pNode;
   247 	if ((pNode = pTrie->trie.retrieve(key)) == NULL)
   248 	{
   249 		SmartTrieNode node;
   250 		UpdateNodeCells(pTrie, &node, array, params[4]);
   251 		if (!pTrie->trie.insert(key, node))
   252 		{
   253 			free(node.ptr);
   254 			return 0;
   255 		}
   256 		return 1;
   257 	}
   258 
   259 	if (!params[4])
   260 	{
   261 		return 0;
   262 	}
   263 
   264 	UpdateNodeCells(pTrie, pNode, array, params[4]);
   265 
   266 	return 1;
   267 }
   268 
   269 static cell_t SetTrieString(IPluginContext *pContext, const cell_t *params)
   270 {
   271 	Handle_t hndl;
   272 	CellTrie *pTrie;
   273 	HandleError err;
   274 	HandleSecurity sec = HandleSecurity(pContext->GetIdentity(), g_pCoreIdent);
   275 
   276 	hndl = params[1];
   277 
   278 	if ((err = g_HandleSys.ReadHandle(hndl, htCellTrie, &sec, (void **)&pTrie))
   279 		!= HandleError_None)
   280 	{
   281 		return pContext->ThrowNativeError("Invalid Handle %x (error %d)", hndl, err);
   282 	}
   283 
   284 	char *key, *val;
   285 	pContext->LocalToString(params[2], &key);
   286 	pContext->LocalToString(params[3], &val);
   287 
   288 	SmartTrieNode *pNode;
   289 	if ((pNode = pTrie->trie.retrieve(key)) == NULL)
   290 	{
   291 		SmartTrieNode node;
   292 		UpdateNodeString(pTrie, &node, val);
   293 		if (!pTrie->trie.insert(key, node))
   294 		{
   295 			free(node.ptr);
   296 			return 0;
   297 		}
   298 		return 1;
   299 	}
   300 
   301 	if (!params[4])
   302 	{
   303 		return 0;
   304 	}
   305 
   306 	UpdateNodeString(pTrie, pNode, val);
   307 
   308 	return 1;
   309 }
   310 
   311 static cell_t RemoveFromTrie(IPluginContext *pContext, const cell_t *params)
   312 {
   313 	Handle_t hndl;
   314 	CellTrie *pTrie;
   315 	HandleError err;
   316 	HandleSecurity sec = HandleSecurity(pContext->GetIdentity(), g_pCoreIdent);
   317 
   318 	hndl = params[1];
   319 
   320 	if ((err = g_HandleSys.ReadHandle(hndl, htCellTrie, &sec, (void **)&pTrie))
   321 		!= HandleError_None)
   322 	{
   323 		return pContext->ThrowNativeError("Invalid Handle %x (error %d)", hndl, err);
   324 	}
   325 
   326 	char *key;
   327 	pContext->LocalToString(params[2], &key);
   328 
   329 	SmartTrieNode *pNode;
   330 	if ((pNode = pTrie->trie.retrieve(key)) == NULL)
   331 	{
   332 		return 0;
   333 	}
   334 
   335 	free(pNode->ptr);
   336 	pNode->ptr = NULL;
   337 
   338 	return pTrie->trie.remove(key) ? 1 : 0;
   339 }
   340 
   341 static cell_t ClearTrie(IPluginContext *pContext, const cell_t *params)
   342 {
   343 	Handle_t hndl;
   344 	CellTrie *pTrie;
   345 	HandleError err;
   346 	HandleSecurity sec = HandleSecurity(pContext->GetIdentity(), g_pCoreIdent);
   347 
   348 	hndl = params[1];
   349 
   350 	if ((err = g_HandleSys.ReadHandle(hndl, htCellTrie, &sec, (void **)&pTrie))
   351 		!= HandleError_None)
   352 	{
   353 		return pContext->ThrowNativeError("Invalid Handle %x (error %d)", hndl, err);
   354 	}
   355 
   356 	pTrie->trie.run_destructor(TrieHelpers::DestroySmartTrieNode);
   357 	pTrie->trie.clear();
   358 
   359 	return 1;
   360 }
   361 
   362 static cell_t GetTrieValue(IPluginContext *pContext, const cell_t *params)
   363 {
   364 	Handle_t hndl;
   365 	CellTrie *pTrie;
   366 	HandleError err;
   367 	HandleSecurity sec = HandleSecurity(pContext->GetIdentity(), g_pCoreIdent);
   368 
   369 	hndl = params[1];
   370 
   371 	if ((err = g_HandleSys.ReadHandle(hndl, htCellTrie, &sec, (void **)&pTrie))
   372 		!= HandleError_None)
   373 	{
   374 		return pContext->ThrowNativeError("Invalid Handle %x (error %d)", hndl, err);
   375 	}
   376 
   377 	char *key;
   378 	cell_t *pValue;
   379 	pContext->LocalToString(params[2], &key);
   380 	pContext->LocalToPhysAddr(params[3], &pValue);
   381 
   382 	SmartTrieNode *pNode;
   383 	if ((pNode = pTrie->trie.retrieve(key)) == NULL)
   384 	{
   385 		return 0;
   386 	}
   387 
   388 	if (pNode->type == TrieNode_Cell)
   389 	{
   390 		*pValue = pNode->data;
   391 		return 1;
   392 	}
   393 	
   394 	return 0;
   395 }
   396 
   397 static cell_t GetTrieArray(IPluginContext *pContext, const cell_t *params)
   398 {
   399 	Handle_t hndl;
   400 	CellTrie *pTrie;
   401 	HandleError err;
   402 	HandleSecurity sec = HandleSecurity(pContext->GetIdentity(), g_pCoreIdent);
   403 
   404 	hndl = params[1];
   405 
   406 	if ((err = g_HandleSys.ReadHandle(hndl, htCellTrie, &sec, (void **)&pTrie))
   407 		!= HandleError_None)
   408 	{
   409 		return pContext->ThrowNativeError("Invalid Handle %x (error %d)", hndl, err);
   410 	}
   411 
   412 	if (params[4] < 0)
   413 	{
   414 		return pContext->ThrowNativeError("Invalid array size: %d", params[4]);
   415 	}
   416 
   417 	char *key;
   418 	cell_t *pValue, *pSize;
   419 	pContext->LocalToString(params[2], &key);
   420 	pContext->LocalToPhysAddr(params[3], &pValue);
   421 	pContext->LocalToPhysAddr(params[5], &pSize);
   422 
   423 	SmartTrieNode *pNode;
   424 	if ((pNode = pTrie->trie.retrieve(key)) == NULL
   425 		|| pNode->type != TrieNode_CellArray)
   426 	{
   427 		return 0;
   428 	}
   429 
   430 	if (pNode->ptr == NULL)
   431 	{
   432 		*pSize = 0;
   433 		return 1;
   434 	}
   435 
   436 	if (pNode->data > params[4])
   437 	{
   438 		*pSize = params[4];
   439 	}
   440 	else if (params[4] != 0)
   441 	{
   442 		*pSize = pNode->data;
   443 	}
   444 	else
   445 	{
   446 		return 1;
   447 	}
   448 
   449 	memcpy(pValue, pNode->ptr, sizeof(cell_t) * pSize[0]);
   450 
   451 	return 1;
   452 }
   453 
   454 static cell_t GetTrieString(IPluginContext *pContext, const cell_t *params)
   455 {
   456 	Handle_t hndl;
   457 	CellTrie *pTrie;
   458 	HandleError err;
   459 	HandleSecurity sec = HandleSecurity(pContext->GetIdentity(), g_pCoreIdent);
   460 
   461 	hndl = params[1];
   462 
   463 	if ((err = g_HandleSys.ReadHandle(hndl, htCellTrie, &sec, (void **)&pTrie))
   464 		!= HandleError_None)
   465 	{
   466 		return pContext->ThrowNativeError("Invalid Handle %x (error %d)", hndl, err);
   467 	}
   468 
   469 	if (params[4] < 0)
   470 	{
   471 		return pContext->ThrowNativeError("Invalid buffer size: %d", params[4]);
   472 	}
   473 
   474 	char *key;
   475 	cell_t *pSize;
   476 	pContext->LocalToString(params[2], &key);
   477 	pContext->LocalToPhysAddr(params[5], &pSize);
   478 
   479 	SmartTrieNode *pNode;
   480 	if ((pNode = pTrie->trie.retrieve(key)) == NULL
   481 		|| pNode->type != TrieNode_String)
   482 	{
   483 		return 0;
   484 	}
   485 
   486 	if (pNode->ptr == NULL)
   487 	{
   488 		*pSize = 0;
   489 		pContext->StringToLocal(params[3], params[4], "");
   490 		return 1;
   491 	}
   492 
   493 	size_t written;
   494 	pContext->StringToLocalUTF8(params[3], params[4], (char *)pNode->ptr, &written);
   495 
   496 	*pSize = (cell_t)written;
   497 
   498 	return 1;
   499 }
   500 
   501 REGISTER_NATIVES(trieNatives)
   502 {
   503 	{"ClearTrie",				ClearTrie},
   504 	{"CreateTrie",				CreateTrie},
   505 	{"GetTrieArray",			GetTrieArray},
   506 	{"GetTrieString",			GetTrieString},
   507 	{"GetTrieValue",			GetTrieValue},
   508 	{"RemoveFromTrie",			RemoveFromTrie},
   509 	{"SetTrieArray",			SetTrieArray},
   510 	{"SetTrieString",			SetTrieString},
   511 	{"SetTrieValue",			SetTrieValue},
   512 	{NULL,						NULL},
   513 };
sourcemod-central
Feed