1.1 --- a/core/logic/sm_memtable.h	Thu Aug 29 11:11:41 2013 -0400
     1.2 +++ b/core/logic/sm_memtable.h	Thu Aug 29 10:09:02 2013 -0700
     1.3 @@ -1,5 +1,5 @@
     1.4  /**
     1.5 - * vim: set ts=4 :
     1.6 + * vim: set ts=4 sw=4 tw=99 noet :
     1.7   * =============================================================================
     1.8   * SourceMod
     1.9   * Copyright (C) 2004-2008 AlliedModders LLC.  All rights reserved.
    1.10 @@ -120,13 +120,20 @@
    1.11  	 */
    1.12  	int AddString(const char *string)
    1.13  	{
    1.14 -		size_t len = strlen(string) + 1;
    1.15 +		return AddString(string, strlen(string));
    1.16 +	}
    1.17 +
    1.18 +	/** 
    1.19 +	 * Adds a string to the string table and returns its index.
    1.20 +	 */
    1.21 +	int AddString(const char *string, size_t length)
    1.22 +	{
    1.23 +		size_t len = length + 1;
    1.24  		int idx;
    1.25  		char *addr;
    1.26  
    1.27  		idx = m_table.CreateMem(len, (void **)&addr);
    1.28 -		strcpy(addr, string);
    1.29 -
    1.30 +		memcpy(addr, string, length + 1);
    1.31  		return idx;
    1.32  	}
    1.33  
    1.34 @@ -139,7 +146,7 @@
    1.35  	}
    1.36  
    1.37  	/**
    1.38 -	 * Scraps the string table.  For caching purposes, the memory
    1.39 +	 * Scraps the string table. For caching purposes, the memory
    1.40  	 * is not freed, however subsequent calls to AddString() will 
    1.41  	 * begin at the first index again.
    1.42  	 */

     2.1 --- a/core/logic/smn_adt_trie.cpp	Thu Aug 29 11:11:41 2013 -0400
     2.2 +++ b/core/logic/smn_adt_trie.cpp	Thu Aug 29 10:09:02 2013 -0700
     2.3 @@ -1,5 +1,5 @@
     2.4  /**
     2.5 - * vim: set ts=4 :
     2.6 + * vim: set ts=4 sw=4 tw=99 noet :
     2.7   * =============================================================================
     2.8   * SourceMod
     2.9   * Copyright (C) 2004-2008 AlliedModders LLC.  All rights reserved.
    2.10 @@ -31,49 +31,157 @@
    2.11  
    2.12  #include <stdlib.h>
    2.13  #include "common_logic.h"
    2.14 -#include <sm_trie_tpl.h>
    2.15 +#include <am-moveable.h>
    2.16 +#include <am-refcounting.h>
    2.17 +#include <sm_stringhashmap.h>
    2.18 +#include "sm_memtable.h"
    2.19  
    2.20  HandleType_t htCellTrie;
    2.21 +HandleType_t htSnapshot;
    2.22  
    2.23 -enum TrieNodeType
    2.24 +enum EntryType
    2.25  {
    2.26 -	TrieNode_Cell,
    2.27 -	TrieNode_CellArray,
    2.28 -	TrieNode_String,
    2.29 +	EntryType_Cell,
    2.30 +	EntryType_CellArray,
    2.31 +	EntryType_String,
    2.32  };
    2.33  
    2.34 -struct SmartTrieNode
    2.35 +class Entry
    2.36  {
    2.37 -	SmartTrieNode()
    2.38 +	struct ArrayInfo
    2.39  	{
    2.40 -		ptr = NULL;
    2.41 -		type = TrieNode_Cell;
    2.42 +		size_t length;
    2.43 +		size_t maxbytes;
    2.44 +
    2.45 +		void *base() {
    2.46 +			return this + 1;
    2.47 +		}
    2.48 +	};
    2.49 +
    2.50 +public:
    2.51 +	Entry()
    2.52 +		: control_(0)
    2.53 +	{
    2.54  	}
    2.55 -	SmartTrieNode(const SmartTrieNode &obj)
    2.56 +	Entry(ke::Moveable<Entry> other)
    2.57 +	{
    2.58 +		control_ = other->control_;
    2.59 +		data_ = other->data_;
    2.60 +		other->control_ = 0;
    2.61 +	}
    2.62 +
    2.63 +	~Entry()
    2.64  	{
    2.65 -		type = obj.type;
    2.66 -		ptr = obj.ptr;
    2.67 -		data = obj.data;
    2.68 -		data_len = obj.data_len;
    2.69 +		free(raw());
    2.70 +	}
    2.71 +
    2.72 +	void setCell(cell_t value) {
    2.73 +		setType(EntryType_Cell);
    2.74 +		data_ = value;
    2.75 +	}
    2.76 +	void setArray(cell_t *cells, size_t length) {
    2.77 +		ArrayInfo *array = ensureArray(length * sizeof(cell_t));
    2.78 +		array->length = length;
    2.79 +		memcpy(array->base(), cells, length * sizeof(cell_t));
    2.80 +		setTypeAndPointer(EntryType_CellArray, array);
    2.81 +	}
    2.82 +	void setString(const char *str) {
    2.83 +		size_t length = strlen(str);
    2.84 +		ArrayInfo *array = ensureArray(length + 1);
    2.85 +		array->length = length;
    2.86 +		strcpy((char *)array->base(), str);
    2.87 +		setTypeAndPointer(EntryType_String, array);
    2.88 +	}
    2.89 +
    2.90 +	size_t arrayLength() const {
    2.91 +		assert(isArray());
    2.92 +		return raw()->length;
    2.93 +	}
    2.94 +	cell_t *array() const {
    2.95 +		assert(isArray());
    2.96 +		return reinterpret_cast<cell_t *>(raw()->base());
    2.97 +	}
    2.98 +	char *chars() const {
    2.99 +		assert(isString());
   2.100 +		return reinterpret_cast<char *>(raw()->base());
   2.101 +	}
   2.102 +	cell_t cell() const {
   2.103 +		assert(isCell());
   2.104 +		return data_;
   2.105 +	}
   2.106 +
   2.107 +	bool isCell() const {
   2.108 +		return type() == EntryType_Cell;
   2.109 +	}
   2.110 +	bool isArray() const {
   2.111 +		return type() == EntryType_CellArray;
   2.112  	}
   2.113 -	SmartTrieNode & operator =(const SmartTrieNode &src)
   2.114 -	{
   2.115 -		type = src.type;
   2.116 -		ptr = src.ptr;
   2.117 -		data = src.data;
   2.118 -		data_len = src.data_len;
   2.119 -		return *this;
   2.120 +	bool isString() const {
   2.121 +		return type() == EntryType_String;
   2.122 +	}
   2.123 +
   2.124 +private:
   2.125 +	Entry(const Entry &other) KE_DELETE;
   2.126 +
   2.127 +	ArrayInfo *ensureArray(size_t bytes) {
   2.128 +		ArrayInfo *array = raw();
   2.129 +		if (array && array->maxbytes >= bytes)
   2.130 +			return array;
   2.131 +		array = (ArrayInfo *)realloc(array, bytes + sizeof(ArrayInfo));
   2.132 +		if (!array)
   2.133 +		{
   2.134 +			fprintf(stderr, "Out of memory!\n");
   2.135 +			abort();
   2.136 +		}
   2.137 +		array->maxbytes = bytes;
   2.138 +		return array;
   2.139  	}
   2.140 -	TrieNodeType type;
   2.141 -	cell_t *ptr;
   2.142 -	cell_t data;
   2.143 -	cell_t data_len;
   2.144 +
   2.145 +	// Pointer and type are overlaid, so we have some accessors.
   2.146 +	ArrayInfo *raw() const {
   2.147 +		return reinterpret_cast<ArrayInfo *>(control_ & ~uintptr_t(0x3));
   2.148 +	}
   2.149 +	void setType(EntryType aType) {
   2.150 +		control_ = uintptr_t(raw()) | uintptr_t(aType);
   2.151 +		assert(type() == aType);
   2.152 +	}
   2.153 +	void setTypeAndPointer(EntryType aType, ArrayInfo *ptr) {
   2.154 +		// malloc() should guarantee 8-byte alignment at worst
   2.155 +		assert((uintptr_t(ptr) & 0x3) == 0);
   2.156 +		control_ = uintptr_t(ptr) | uintptr_t(aType);
   2.157 +		assert(type() == aType);
   2.158 +	}
   2.159 +	EntryType type() const {
   2.160 +		return (EntryType)(control_ & 0x3);
   2.161 +	}
   2.162 +
   2.163 +private:
   2.164 +	// Contains the bits for the type, and an array pointer, if one is set.
   2.165 +	uintptr_t control_;
   2.166 +
   2.167 +	// Contains data for cell-only entries.
   2.168 +	cell_t data_;
   2.169  };
   2.170  
   2.171 -struct CellTrie
   2.172 +struct CellTrie : public ke::Refcounted<CellTrie>
   2.173 +{
   2.174 +	StringHashMap<Entry> map;
   2.175 +};
   2.176 +
   2.177 +struct TrieSnapshot
   2.178  {
   2.179 -	KTrie<SmartTrieNode> trie;
   2.180 -	cell_t mem_usage;
   2.181 +	TrieSnapshot()
   2.182 +		: strings(128)
   2.183 +	{ }
   2.184 +
   2.185 +	size_t mem_usage()
   2.186 +	{
   2.187 +		return length * sizeof(int) + strings.GetMemTable()->GetMemUsage();
   2.188 +	}
   2.189 +
   2.190 +	size_t length;
   2.191 +	ke::AutoArray<int> keys;
   2.192 +	BaseStringTable strings;
   2.193  };
   2.194  
   2.195  class TrieHelpers : 
   2.196 @@ -84,28 +192,35 @@
   2.197  	void OnSourceModAllInitialized()
   2.198  	{
   2.199  		htCellTrie = handlesys->CreateType("Trie", this, 0, NULL, NULL, g_pCoreIdent, NULL);
   2.200 +		htSnapshot = handlesys->CreateType("TrieSnapshot", this, 0, NULL, NULL, g_pCoreIdent, NULL);
   2.201  	}
   2.202  	void OnSourceModShutdown()
   2.203  	{
   2.204 +		handlesys->RemoveType(htSnapshot, g_pCoreIdent);
   2.205  		handlesys->RemoveType(htCellTrie, g_pCoreIdent);
   2.206  	}
   2.207  public: //IHandleTypeDispatch
   2.208 -	static void DestroySmartTrieNode(SmartTrieNode *pNode)
   2.209 -	{
   2.210 -		free(pNode->ptr);
   2.211 -	}
   2.212  	void OnHandleDestroy(HandleType_t type, void *object)
   2.213  	{
   2.214 -		CellTrie *pTrie = (CellTrie *)object;
   2.215 -
   2.216 -		pTrie->trie.run_destructor(DestroySmartTrieNode);
   2.217 -
   2.218 -		delete pTrie;
   2.219 +		if (type == htCellTrie)
   2.220 +		{
   2.221 +			CellTrie *pTrie = (CellTrie *)object;
   2.222 +			pTrie->Release();
   2.223 +		} else {
   2.224 +			TrieSnapshot *snapshot = (TrieSnapshot *)object;
   2.225 +			delete snapshot;
   2.226 +		}
   2.227  	}
   2.228  	bool GetHandleApproxSize(HandleType_t type, void *object, unsigned int *pSize)
   2.229  	{
   2.230 -		CellTrie *pArray = (CellTrie *)object;
   2.231 -		*pSize = sizeof(CellTrie) + pArray->mem_usage + pArray->trie.mem_usage();
   2.232 +		if (type == htCellTrie)
   2.233 +		{
   2.234 +			CellTrie *pArray = (CellTrie *)object;
   2.235 +			*pSize = sizeof(CellTrie) + pArray->map.mem_usage();
   2.236 +		} else {
   2.237 +			TrieSnapshot *snapshot = (TrieSnapshot *)object;
   2.238 +			*pSize = sizeof(TrieSnapshot) + snapshot->mem_usage();
   2.239 +		}
   2.240  		return true;
   2.241  	}
   2.242  } s_CellTrieHelpers;
   2.243 @@ -115,8 +230,6 @@
   2.244  	CellTrie *pTrie = new CellTrie;
   2.245  	Handle_t hndl;
   2.246  
   2.247 -	pTrie->mem_usage = 0;
   2.248 -
   2.249  	if ((hndl = handlesys->CreateHandle(htCellTrie, pTrie, pContext->GetIdentity(), g_pCoreIdent, NULL))
   2.250  		== BAD_HANDLE)
   2.251  	{
   2.252 @@ -127,67 +240,13 @@
   2.253  	return hndl;
   2.254  }
   2.255  
   2.256 -static void UpdateNodeCells(CellTrie *pTrie, SmartTrieNode *pData, const cell_t *cells, cell_t num_cells)
   2.257 -{
   2.258 -	if (num_cells == 1)
   2.259 -	{
   2.260 -		pData->data = *cells;
   2.261 -		pData->type = TrieNode_Cell;
   2.262 -	}
   2.263 -	else
   2.264 -	{
   2.265 -		pData->type = TrieNode_CellArray;
   2.266 -		if (pData->ptr == NULL)
   2.267 -		{
   2.268 -			pData->ptr = (cell_t *)malloc(num_cells * sizeof(cell_t));
   2.269 -			pData->data_len = num_cells;
   2.270 -			pTrie->mem_usage += (pData->data_len * sizeof(cell_t));
   2.271 -		}
   2.272 -		else if (pData->data_len < num_cells)
   2.273 -		{
   2.274 -			pData->ptr = (cell_t *)realloc(pData->ptr, num_cells * sizeof(cell_t));
   2.275 -			pTrie->mem_usage += (num_cells - pData->data_len) * sizeof(cell_t);
   2.276 -			pData->data_len = num_cells;
   2.277 -		}
   2.278 -		if (num_cells != 0)
   2.279 -		{
   2.280 -			memcpy(pData->ptr, cells, sizeof(cell_t) * num_cells);
   2.281 -		}
   2.282 -		pData->data = num_cells;
   2.283 -	}
   2.284 -}
   2.285 -
   2.286 -static void UpdateNodeString(CellTrie *pTrie, SmartTrieNode *pData, const char *str)
   2.287 -{
   2.288 -	size_t len = strlen(str);
   2.289 -	cell_t num_cells = (len + sizeof(cell_t)) / sizeof(cell_t);
   2.290 -
   2.291 -	if (pData->ptr == NULL)
   2.292 -	{
   2.293 -		pData->ptr = (cell_t *)malloc(num_cells * sizeof(cell_t));
   2.294 -		pData->data_len = num_cells;
   2.295 -		pTrie->mem_usage += (pData->data_len * sizeof(cell_t));
   2.296 -	}
   2.297 -	else if (pData->data_len < num_cells)
   2.298 -	{
   2.299 -		pData->ptr = (cell_t *)realloc(pData->ptr, num_cells * sizeof(cell_t));
   2.300 -		pTrie->mem_usage += (num_cells - pData->data_len) * sizeof(cell_t);
   2.301 -		pData->data_len = num_cells;
   2.302 -	}
   2.303 -
   2.304 -	strcpy((char *)pData->ptr, str);
   2.305 -	pData->data = len;
   2.306 -	pData->type = TrieNode_String;
   2.307 -}
   2.308 -
   2.309  static cell_t SetTrieValue(IPluginContext *pContext, const cell_t *params)
   2.310  {
   2.311 -	Handle_t hndl;
   2.312  	CellTrie *pTrie;
   2.313  	HandleError err;
   2.314  	HandleSecurity sec = HandleSecurity(pContext->GetIdentity(), g_pCoreIdent);
   2.315  
   2.316 -	hndl = params[1];
   2.317 +	Handle_t hndl = params[1];
   2.318  
   2.319  	if ((err = handlesys->ReadHandle(hndl, htCellTrie, &sec, (void **)&pTrie))
   2.320  		!= HandleError_None)
   2.321 @@ -198,32 +257,29 @@
   2.322  	char *key;
   2.323  	pContext->LocalToString(params[2], &key);
   2.324  
   2.325 -	SmartTrieNode *pNode;
   2.326 -	if ((pNode = pTrie->trie.retrieve(key)) == NULL)
   2.327 +	StringHashMap<Entry>::Insert i = pTrie->map.findForAdd(key);
   2.328 +	if (!i.found())
   2.329  	{
   2.330 -		SmartTrieNode node;
   2.331 -		UpdateNodeCells(pTrie, &node, &params[3], 1);
   2.332 -		return pTrie->trie.insert(key, node) ? 1 : 0;
   2.333 +		if (!pTrie->map.add(i, key))
   2.334 +			return 0;
   2.335 +		i->value.setCell(params[3]);
   2.336 +		return 1;
   2.337  	}
   2.338  
   2.339  	if (!params[4])
   2.340 -	{
   2.341  		return 0;
   2.342 -	}
   2.343  
   2.344 -	UpdateNodeCells(pTrie, pNode, &params[3], 1);
   2.345 -
   2.346 +	i->value.setCell(params[3]);
   2.347  	return 1;
   2.348  }
   2.349  
   2.350  static cell_t SetTrieArray(IPluginContext *pContext, const cell_t *params)
   2.351  {
   2.352 -	Handle_t hndl;
   2.353  	CellTrie *pTrie;
   2.354  	HandleError err;
   2.355  	HandleSecurity sec = HandleSecurity(pContext->GetIdentity(), g_pCoreIdent);
   2.356  
   2.357 -	hndl = params[1];
   2.358 +	Handle_t hndl = params[1];
   2.359  
   2.360  	if ((err = handlesys->ReadHandle(hndl, htCellTrie, &sec, (void **)&pTrie))
   2.361  		!= HandleError_None)
   2.362 @@ -241,37 +297,30 @@
   2.363  	pContext->LocalToString(params[2], &key);
   2.364  	pContext->LocalToPhysAddr(params[3], &array);
   2.365  
   2.366 -	SmartTrieNode *pNode;
   2.367 -	if ((pNode = pTrie->trie.retrieve(key)) == NULL)
   2.368 +	StringHashMap<Entry>::Insert i = pTrie->map.findForAdd(key);
   2.369 +	if (!i.found())
   2.370  	{
   2.371 -		SmartTrieNode node;
   2.372 -		UpdateNodeCells(pTrie, &node, array, params[4]);
   2.373 -		if (!pTrie->trie.insert(key, node))
   2.374 -		{
   2.375 -			free(node.ptr);
   2.376 +		if (!pTrie->map.add(i, key))
   2.377  			return 0;
   2.378 -		}
   2.379 +		i->key = key;
   2.380 +		i->value.setArray(array, params[4]);
   2.381  		return 1;
   2.382  	}
   2.383  
   2.384  	if (!params[4])
   2.385 -	{
   2.386  		return 0;
   2.387 -	}
   2.388  
   2.389 -	UpdateNodeCells(pTrie, pNode, array, params[4]);
   2.390 -
   2.391 +	i->value.setArray(array, params[4]);
   2.392  	return 1;
   2.393  }
   2.394  
   2.395  static cell_t SetTrieString(IPluginContext *pContext, const cell_t *params)
   2.396  {
   2.397 -	Handle_t hndl;
   2.398  	CellTrie *pTrie;
   2.399  	HandleError err;
   2.400  	HandleSecurity sec = HandleSecurity(pContext->GetIdentity(), g_pCoreIdent);
   2.401  
   2.402 -	hndl = params[1];
   2.403 +	Handle_t hndl = params[1];
   2.404  
   2.405  	if ((err = handlesys->ReadHandle(hndl, htCellTrie, &sec, (void **)&pTrie))
   2.406  		!= HandleError_None)
   2.407 @@ -283,37 +332,29 @@
   2.408  	pContext->LocalToString(params[2], &key);
   2.409  	pContext->LocalToString(params[3], &val);
   2.410  
   2.411 -	SmartTrieNode *pNode;
   2.412 -	if ((pNode = pTrie->trie.retrieve(key)) == NULL)
   2.413 +	StringHashMap<Entry>::Insert i = pTrie->map.findForAdd(key);
   2.414 +	if (!i.found())
   2.415  	{
   2.416 -		SmartTrieNode node;
   2.417 -		UpdateNodeString(pTrie, &node, val);
   2.418 -		if (!pTrie->trie.insert(key, node))
   2.419 -		{
   2.420 -			free(node.ptr);
   2.421 +		if (!pTrie->map.add(i, key))
   2.422  			return 0;
   2.423 -		}
   2.424 +		i->value.setString(val);
   2.425  		return 1;
   2.426  	}
   2.427  
   2.428  	if (!params[4])
   2.429 -	{
   2.430  		return 0;
   2.431 -	}
   2.432  
   2.433 -	UpdateNodeString(pTrie, pNode, val);
   2.434 -
   2.435 +	i->value.setString(val);
   2.436  	return 1;
   2.437  }
   2.438  
   2.439  static cell_t RemoveFromTrie(IPluginContext *pContext, const cell_t *params)
   2.440  {
   2.441 -	Handle_t hndl;
   2.442  	CellTrie *pTrie;
   2.443  	HandleError err;
   2.444  	HandleSecurity sec = HandleSecurity(pContext->GetIdentity(), g_pCoreIdent);
   2.445  
   2.446 -	hndl = params[1];
   2.447 +	Handle_t hndl = params[1];
   2.448  
   2.449  	if ((err = handlesys->ReadHandle(hndl, htCellTrie, &sec, (void **)&pTrie))
   2.450  		!= HandleError_None)
   2.451 @@ -324,16 +365,12 @@
   2.452  	char *key;
   2.453  	pContext->LocalToString(params[2], &key);
   2.454  
   2.455 -	SmartTrieNode *pNode;
   2.456 -	if ((pNode = pTrie->trie.retrieve(key)) == NULL)
   2.457 -	{
   2.458 +	StringHashMap<Entry>::Result r = pTrie->map.find(key);
   2.459 +	if (!r.found())
   2.460  		return 0;
   2.461 -	}
   2.462  
   2.463 -	free(pNode->ptr);
   2.464 -	pNode->ptr = NULL;
   2.465 -
   2.466 -	return pTrie->trie.remove(key) ? 1 : 0;
   2.467 +	pTrie->map.remove(r);
   2.468 +	return 1;
   2.469  }
   2.470  
   2.471  static cell_t ClearTrie(IPluginContext *pContext, const cell_t *params)
   2.472 @@ -351,9 +388,7 @@
   2.473  		return pContext->ThrowNativeError("Invalid Handle %x (error %d)", hndl, err);
   2.474  	}
   2.475  
   2.476 -	pTrie->trie.run_destructor(TrieHelpers::DestroySmartTrieNode);
   2.477 -	pTrie->trie.clear();
   2.478 -
   2.479 +	pTrie->map.clear();
   2.480  	return 1;
   2.481  }
   2.482  
   2.483 @@ -377,15 +412,22 @@
   2.484  	pContext->LocalToString(params[2], &key);
   2.485  	pContext->LocalToPhysAddr(params[3], &pValue);
   2.486  
   2.487 -	SmartTrieNode *pNode;
   2.488 -	if ((pNode = pTrie->trie.retrieve(key)) == NULL)
   2.489 +	StringHashMap<Entry>::Result r = pTrie->map.find(key);
   2.490 +	if (!r.found())
   2.491 +		return 0;
   2.492 +
   2.493 +	if (r->value.isCell())
   2.494  	{
   2.495 -		return 0;
   2.496 +		*pValue = r->value.cell();
   2.497 +		return 1;
   2.498  	}
   2.499  
   2.500 -	if (pNode->type == TrieNode_Cell)
   2.501 +	// Maintain compatibility with an old bug. If an array was set with one
   2.502 +	// cell, it was stored internally as a single cell. We now store as an
   2.503 +	// actual array, but we make GetTrieValue() still work for this case.
   2.504 +	if (r->value.isArray() && r->value.arrayLength() == 1)
   2.505  	{
   2.506 -		*pValue = pNode->data;
   2.507 +		*pValue = r->value.array()[0];
   2.508  		return 1;
   2.509  	}
   2.510  	
   2.511 @@ -418,34 +460,29 @@
   2.512  	pContext->LocalToPhysAddr(params[3], &pValue);
   2.513  	pContext->LocalToPhysAddr(params[5], &pSize);
   2.514  
   2.515 -	SmartTrieNode *pNode;
   2.516 -	if ((pNode = pTrie->trie.retrieve(key)) == NULL
   2.517 -		|| pNode->type != TrieNode_CellArray)
   2.518 -	{
   2.519 +
   2.520 +	StringHashMap<Entry>::Result r = pTrie->map.find(key);
   2.521 +	if (!r.found() || !r->value.isArray())
   2.522  		return 0;
   2.523 -	}
   2.524  
   2.525 -	if (pNode->ptr == NULL)
   2.526 +	if (!r->value.array())
   2.527  	{
   2.528  		*pSize = 0;
   2.529  		return 1;
   2.530  	}
   2.531  
   2.532 -	if (pNode->data > params[4])
   2.533 -	{
   2.534 +	if (!params[4])
   2.535 +		return 1;
   2.536 +
   2.537 +	size_t length = r->value.arrayLength();
   2.538 +	cell_t *base = r->value.array();
   2.539 +
   2.540 +	if (length > size_t(params[4]))
   2.541  		*pSize = params[4];
   2.542 -	}
   2.543 -	else if (params[4] != 0)
   2.544 -	{
   2.545 -		*pSize = pNode->data;
   2.546 -	}
   2.547  	else
   2.548 -	{
   2.549 -		return 1;
   2.550 -	}
   2.551 +		*pSize = length;
   2.552  
   2.553 -	memcpy(pValue, pNode->ptr, sizeof(cell_t) * pSize[0]);
   2.554 -
   2.555 +	memcpy(pValue, base, sizeof(cell_t) * pSize[0]);
   2.556  	return 1;
   2.557  }
   2.558  
   2.559 @@ -474,25 +511,14 @@
   2.560  	pContext->LocalToString(params[2], &key);
   2.561  	pContext->LocalToPhysAddr(params[5], &pSize);
   2.562  
   2.563 -	SmartTrieNode *pNode;
   2.564 -	if ((pNode = pTrie->trie.retrieve(key)) == NULL
   2.565 -		|| pNode->type != TrieNode_String)
   2.566 -	{
   2.567 +	StringHashMap<Entry>::Result r = pTrie->map.find(key);
   2.568 +	if (!r.found() || !r->value.isString())
   2.569  		return 0;
   2.570 -	}
   2.571 -
   2.572 -	if (pNode->ptr == NULL)
   2.573 -	{
   2.574 -		*pSize = 0;
   2.575 -		pContext->StringToLocal(params[3], params[4], "");
   2.576 -		return 1;
   2.577 -	}
   2.578  
   2.579  	size_t written;
   2.580 -	pContext->StringToLocalUTF8(params[3], params[4], (char *)pNode->ptr, &written);
   2.581 +	pContext->StringToLocalUTF8(params[3], params[4], r->value.chars(), &written);
   2.582  
   2.583  	*pSize = (cell_t)written;
   2.584 -
   2.585  	return 1;
   2.586  }
   2.587  
   2.588 @@ -511,7 +537,101 @@
   2.589  		return pContext->ThrowNativeError("Invalid Handle %x (error %d)", hndl, err);
   2.590  	}
   2.591  
   2.592 -	return pTrie->trie.size();
   2.593 +	return pTrie->map.elements();
   2.594 +}
   2.595 +
   2.596 +static cell_t CreateTrieSnapshot(IPluginContext *pContext, const cell_t *params)
   2.597 +{
   2.598 +	HandleError err;
   2.599 +	HandleSecurity sec = HandleSecurity(pContext->GetIdentity(), g_pCoreIdent);
   2.600 +
   2.601 +	Handle_t hndl = params[1];
   2.602 +
   2.603 +	CellTrie *pTrie;
   2.604 +	if ((err = handlesys->ReadHandle(hndl, htCellTrie, &sec, (void **)&pTrie))
   2.605 +		!= HandleError_None)
   2.606 +	{
   2.607 +		return pContext->ThrowNativeError("Invalid Handle %x (error %d)", hndl, err);
   2.608 +	}
   2.609 +
   2.610 +	TrieSnapshot *snapshot = new TrieSnapshot;
   2.611 +	snapshot->length = pTrie->map.elements();
   2.612 +	snapshot->keys = new int[snapshot->length];
   2.613 +	size_t i = 0;
   2.614 +	for (StringHashMap<Entry>::iterator iter = pTrie->map.iter(); !iter.empty(); iter.next(), i++)
   2.615 +		snapshot->keys[i] = snapshot->strings.AddString(iter->key.chars(), iter->key.length());
   2.616 +	assert(i == snapshot->length);
   2.617 +
   2.618 +	if ((hndl = handlesys->CreateHandle(htSnapshot, snapshot, pContext->GetIdentity(), g_pCoreIdent, NULL))
   2.619 +		== BAD_HANDLE)
   2.620 +	{
   2.621 +		delete snapshot;
   2.622 +		return BAD_HANDLE;
   2.623 +	}
   2.624 +
   2.625 +	return hndl;
   2.626 +}
   2.627 +
   2.628 +static cell_t TrieSnapshotLength(IPluginContext *pContext, const cell_t *params)
   2.629 +{
   2.630 +	HandleError err;
   2.631 +	HandleSecurity sec = HandleSecurity(pContext->GetIdentity(), g_pCoreIdent);
   2.632 +
   2.633 +	Handle_t hndl = params[1];
   2.634 +
   2.635 +	TrieSnapshot *snapshot;
   2.636 +	if ((err = handlesys->ReadHandle(hndl, htSnapshot, &sec, (void **)&snapshot))
   2.637 +		!= HandleError_None)
   2.638 +	{
   2.639 +		return pContext->ThrowNativeError("Invalid Handle %x (error %d)", hndl, err);
   2.640 +	}
   2.641 +
   2.642 +	return snapshot->length;
   2.643 +}
   2.644 +
   2.645 +static cell_t TrieSnapshotKeyBufferSize(IPluginContext *pContext, const cell_t *params)
   2.646 +{
   2.647 +	HandleError err;
   2.648 +	HandleSecurity sec = HandleSecurity(pContext->GetIdentity(), g_pCoreIdent);
   2.649 +
   2.650 +	Handle_t hndl = params[1];
   2.651 +
   2.652 +	TrieSnapshot *snapshot;
   2.653 +	if ((err = handlesys->ReadHandle(hndl, htSnapshot, &sec, (void **)&snapshot))
   2.654 +		!= HandleError_None)
   2.655 +	{
   2.656 +		return pContext->ThrowNativeError("Invalid Handle %x (error %d)", hndl, err);
   2.657 +	}
   2.658 +
   2.659 +	unsigned index = params[2];
   2.660 +	if (index >= snapshot->length)
   2.661 +		return pContext->ThrowNativeError("Invalid index %d", index);
   2.662 +
   2.663 +	return strlen(snapshot->strings.GetString(snapshot->keys[index])) + 1;
   2.664 +}
   2.665 +
   2.666 +static cell_t GetTrieSnapshotKey(IPluginContext *pContext, const cell_t *params)
   2.667 +{
   2.668 +	HandleError err;
   2.669 +	HandleSecurity sec = HandleSecurity(pContext->GetIdentity(), g_pCoreIdent);
   2.670 +
   2.671 +	Handle_t hndl = params[1];
   2.672 +
   2.673 +	TrieSnapshot *snapshot;
   2.674 +	if ((err = handlesys->ReadHandle(hndl, htSnapshot, &sec, (void **)&snapshot))
   2.675 +		!= HandleError_None)
   2.676 +	{
   2.677 +		return pContext->ThrowNativeError("Invalid Handle %x (error %d)", hndl, err);
   2.678 +	}
   2.679 +
   2.680 +	unsigned index = params[2];
   2.681 +	if (index >= snapshot->length)
   2.682 +		return pContext->ThrowNativeError("Invalid index %d", index);
   2.683 +
   2.684 +	size_t written;
   2.685 +	const char *str = snapshot->strings.GetString(snapshot->keys[index]);
   2.686 +	pContext->StringToLocalUTF8(params[3], params[4], str, &written);
   2.687 +	return written;
   2.688  }
   2.689  
   2.690  REGISTER_NATIVES(trieNatives)
   2.691 @@ -526,5 +646,9 @@
   2.692  	{"SetTrieString",			SetTrieString},
   2.693  	{"SetTrieValue",			SetTrieValue},
   2.694  	{"GetTrieSize",				GetTrieSize},
   2.695 +	{"CreateTrieSnapshot",		CreateTrieSnapshot},
   2.696 +	{"TrieSnapshotLength",		TrieSnapshotLength},
   2.697 +	{"TrieSnapshotKeyBufferSize", TrieSnapshotKeyBufferSize},
   2.698 +	{"GetTrieSnapshotKey",		GetTrieSnapshotKey},
   2.699  	{NULL,						NULL},
   2.700  };

     3.1 --- a/core/sm_memtable.h	Thu Aug 29 11:11:41 2013 -0400
     3.2 +++ b/core/sm_memtable.h	Thu Aug 29 10:09:02 2013 -0700
     3.3 @@ -1,5 +1,5 @@
     3.4  /**
     3.5 - * vim: set ts=4 :
     3.6 + * vim: set ts=4 sw=4 tw=99 noet :
     3.7   * =============================================================================
     3.8   * SourceMod
     3.9   * Copyright (C) 2004-2008 AlliedModders LLC.  All rights reserved.
    3.10 @@ -120,13 +120,20 @@
    3.11  	 */
    3.12  	int AddString(const char *string)
    3.13  	{
    3.14 -		size_t len = strlen(string) + 1;
    3.15 +		return AddString(string, strlen(string));
    3.16 +	}
    3.17 +
    3.18 +	/** 
    3.19 +	 * Adds a string to the string table and returns its index.
    3.20 +	 */
    3.21 +	int AddString(const char *string, size_t length)
    3.22 +	{
    3.23 +		size_t len = length + 1;
    3.24  		int idx;
    3.25  		char *addr;
    3.26  
    3.27  		idx = m_table.CreateMem(len, (void **)&addr);
    3.28 -		strcpy(addr, string);
    3.29 -
    3.30 +		memcpy(addr, string, length + 1);
    3.31  		return idx;
    3.32  	}
    3.33  
    3.34 @@ -139,7 +146,7 @@
    3.35  	}
    3.36  
    3.37  	/**
    3.38 -	 * Scraps the string table.  For caching purposes, the memory
    3.39 +	 * Scraps the string table. For caching purposes, the memory
    3.40  	 * is not freed, however subsequent calls to AddString() will 
    3.41  	 * begin at the first index again.
    3.42  	 */

     4.1 --- a/plugins/include/adt_trie.inc	Thu Aug 29 11:11:41 2013 -0400
     4.2 +++ b/plugins/include/adt_trie.inc	Thu Aug 29 10:09:02 2013 -0700
     4.3 @@ -1,5 +1,5 @@
     4.4  /**
     4.5 - * vim: set ts=4 :
     4.6 + * vim: set ts=4 sw=4 tw=99 noet :
     4.7   * =============================================================================
     4.8   * SourceMod (C)2004-2008 AlliedModders LLC.  All rights reserved.
     4.9   * =============================================================================
    4.10 @@ -36,35 +36,37 @@
    4.11  #define _adt_trie_included
    4.12  
    4.13  /**
    4.14 - * Creates a Trie structure.  A trie is a data storage object that maps any value to a 
    4.15 - * string of text.  It features very fast lookup and deletion, but grows very slow for 
    4.16 - * insertion once tens of thousands of items are added.
    4.17 + * Creates a hash map. A hash map is a container that can map strings (called
    4.18 + * "keys") to arbitrary values (cells, arrays, or strings). Keys in a hash map
    4.19 + * are unique. That is, there is at most one entry in the map for a given key.
    4.20   *
    4.21 - * Keys in Tries are unique.  That is, each key may only have one value.  Unlike arrays, 
    4.22 - * Tries cannot be iterated right now.  Since the contents are known to be unique, to 
    4.23 - * work around this, you can use ADT Arrays to store a list of keys known to be in a 
    4.24 - * Trie.
    4.25 + * Insertion, deletion, and lookup in a hash map are all considered to be fast
    4.26 + * operations, amortized to O(1), or constant time.
    4.27   *
    4.28 - * @return 			New Trie Handle, which must be freed via CloseHandle().
    4.29 + * The word "Trie" in this API is historical. As of SourceMod 1.6, tries have
    4.30 + * been internally replaced with hash tables, which have O(1) insertion time
    4.31 + * instead of O(n).
    4.32 + *
    4.33 + * @return 			New Map Handle, which must be freed via CloseHandle().
    4.34   */
    4.35  native Handle:CreateTrie();
    4.36  
    4.37  /**
    4.38 - * Sets a value in a Trie, either inserting a new entry or replacing an old one.
    4.39 + * Sets a value in a hash map, either inserting a new entry or replacing an old one.
    4.40   *
    4.41 - * @param trie		Trie Handle.
    4.42 + * @param map		Map Handle.
    4.43   * @param key		Key string.
    4.44   * @param value		Value to store at this key.
    4.45   * @param replace	If false, operation will fail if the key is already set.
    4.46   * @return			True on success, false on failure.
    4.47   * @error			Invalid Handle.
    4.48   */
    4.49 -native bool:SetTrieValue(Handle:trie, const String:key[], any:value, bool:replace=true);
    4.50 +native bool:SetTrieValue(Handle:map, const String:key[], any:value, bool:replace=true);
    4.51  
    4.52  /**
    4.53 - * Sets an array value in a Trie, either inserting a new entry or replacing an old one.
    4.54 + * Sets an array value in a Map, either inserting a new entry or replacing an old one.
    4.55   *
    4.56 - * @param trie		Trie Handle.
    4.57 + * @param map		Map Handle.
    4.58   * @param key		Key string.
    4.59   * @param array		Array to store.
    4.60   * @param num_items	Number of items in the array.
    4.61 @@ -72,36 +74,36 @@
    4.62   * @return			True on success, false on failure.
    4.63   * @error			Invalid Handle.
    4.64   */
    4.65 -native bool:SetTrieArray(Handle:trie, const String:key[], const any:array[], num_items, bool:replace=true);
    4.66 +native bool:SetTrieArray(Handle:map, const String:key[], const any:array[], num_items, bool:replace=true);
    4.67  
    4.68  /**
    4.69 - * Sets a string value in a Trie, either inserting a new entry or replacing an old one.
    4.70 + * Sets a string value in a Map, either inserting a new entry or replacing an old one.
    4.71   *
    4.72 - * @param trie		Trie Handle.
    4.73 + * @param map		Map Handle.
    4.74   * @param key		Key string.
    4.75   * @param value		String to store.
    4.76   * @param replace	If false, operation will fail if the key is already set.
    4.77   * @return			True on success, false on failure.
    4.78   * @error			Invalid Handle.
    4.79   */
    4.80 -native bool:SetTrieString(Handle:trie, const String:key[], const String:value[], bool:replace=true);
    4.81 +native bool:SetTrieString(Handle:map, const String:key[], const String:value[], bool:replace=true);
    4.82  
    4.83  /**
    4.84 - * Retrieves a value in a Trie.
    4.85 + * Retrieves a value in a Map.
    4.86   *
    4.87 - * @param trie		Trie Handle.
    4.88 + * @param map		Map Handle.
    4.89   * @param key		Key string.
    4.90   * @param value		Variable to store value.
    4.91   * @return			True on success.  False if the key is not set, or the key is set 
    4.92   *					as an array or string (not a value).
    4.93   * @error			Invalid Handle.
    4.94   */
    4.95 -native bool:GetTrieValue(Handle:trie, const String:key[], &any:value);
    4.96 +native bool:GetTrieValue(Handle:map, const String:key[], &any:value);
    4.97  
    4.98  /**
    4.99 - * Retrieves an array in a Trie.
   4.100 + * Retrieves an array in a Map.
   4.101   *
   4.102 - * @param trie		Trie Handle.
   4.103 + * @param map		Map Handle.
   4.104   * @param key		Key string.
   4.105   * @param array		Buffer to store array.
   4.106   * @param max_size	Maximum size of array buffer.
   4.107 @@ -110,12 +112,12 @@
   4.108   *					as a value or string (not an array).
   4.109   * @error			Invalid Handle.
   4.110   */
   4.111 -native bool:GetTrieArray(Handle:trie, const String:key[], any:array[], max_size, &size=0);
   4.112 +native bool:GetTrieArray(Handle:map, const String:key[], any:array[], max_size, &size=0);
   4.113  
   4.114  /**
   4.115 - * Retrieves a string in a Trie.
   4.116 + * Retrieves a string in a Map.
   4.117   *
   4.118 - * @param trie		Trie Handle.
   4.119 + * @param map		Map Handle.
   4.120   * @param key		Key string.
   4.121   * @param value		Buffer to store value.
   4.122   * @param max_size	Maximum size of string buffer.
   4.123 @@ -124,34 +126,75 @@
   4.124   *					as a value or array (not a string).
   4.125   * @error			Invalid Handle.
   4.126   */
   4.127 -native bool:GetTrieString(Handle:trie, const String:key[], String:value[], max_size, &size=0);
   4.128 +native bool:GetTrieString(Handle:map, const String:key[], String:value[], max_size, &size=0);
   4.129  
   4.130  /**
   4.131 - * Removes a key entry from a Trie.
   4.132 + * Removes a key entry from a Map.
   4.133   *
   4.134 - * @param trie		Trie Handle.
   4.135 + * @param map		Map Handle.
   4.136   * @param key		Key string.
   4.137   * @return			True on success, false if the value was never set.
   4.138   * @error			Invalid Handle.
   4.139   */
   4.140 -native RemoveFromTrie(Handle:trie, const String:key[]);
   4.141 +native RemoveFromTrie(Handle:map, const String:key[]);
   4.142  
   4.143  /**
   4.144 - * Clears all entries from a Trie.
   4.145 + * Clears all entries from a Map.
   4.146   *
   4.147 - * @param trie		Trie Handle.
   4.148 + * @param map		Map Handle.
   4.149   * @error			Invalid Handle.
   4.150   */
   4.151 -native ClearTrie(Handle:trie);
   4.152 +native ClearTrie(Handle:map);
   4.153  
   4.154  /**
   4.155 - * Retrieves the number of elements in a trie.
   4.156 + * Retrieves the number of elements in a map.
   4.157   *
   4.158 - * Note that trie items are not enumerable/iteratable.  If you need to 
   4.159 - * retrieve the elements in a trie, store its keys in an ADT Array. 
   4.160 - *
   4.161 - * @param trie		Trie Handle.
   4.162 + * @param map		Map Handle.
   4.163   * @return			Number of elements in the trie.
   4.164   * @error			Invalid Handle.
   4.165   */
   4.166 -native GetTrieSize(Handle:trie);
   4.167 +native GetTrieSize(Handle:map);
   4.168 +
   4.169 +/**
   4.170 + * Creates a snapshot of all keys in the map. If the map is changed after this
   4.171 + * call, the changes are not reflected in the snapshot. Keys are not sorted.
   4.172 + *
   4.173 + * @param map       Map Handle.
   4.174 + * @return			New Map Snapshot Handle, which must be closed via CloseHandle().
   4.175 + * @error			Invalid Handle.
   4.176 + */
   4.177 +native Handle:CreateTrieSnapshot(Handle:map);
   4.178 +
   4.179 +/**
   4.180 + * Returns the number of keys in a map snapshot. Note that this may be
   4.181 + * different from the size of the map, since the map can change after the
   4.182 + * snapshot of its keys was taken.
   4.183 + *
   4.184 + * @param snapshot	Map snapshot.
   4.185 + * @return			Number of keys.
   4.186 + * @error			Invalid Handle.
   4.187 + */
   4.188 +native TrieSnapshotLength(Handle:snapshot);
   4.189 +
   4.190 +/**
   4.191 + * Returns the buffer size required to store a given key. That is, it returns
   4.192 + * the length of the key plus one.
   4.193 + *
   4.194 + * @param snapshot	Map snapshot.
   4.195 + * @param index		Key index (starting from 0).
   4.196 + * @return 			Buffer size required to store the key string.
   4.197 + * @error			Invalid Handle or index out of range.
   4.198 + */
   4.199 +native TrieSnapshotKeyBufferSize(Handle:snapshot, index);
   4.200 +
   4.201 +/**
   4.202 + * Retrieves the key string of a given key in a map snapshot.
   4.203 + *
   4.204 + * @param snapshot	Map snapshot.
   4.205 + * @param index		Key index (starting from 0).
   4.206 + * @param buffer	String buffer.
   4.207 + * @param maxlength	Maximum buffer length.
   4.208 + * @return			Number of bytes written to the buffer.
   4.209 + * @error			Invalid Handle or index out of range.
   4.210 + */
   4.211 +native GetTrieSnapshotKey(Handle:snapshot, index, String:buffer[], maxlength);

     5.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     5.2 +++ b/plugins/testsuite/tries.sp	Thu Aug 29 10:09:02 2013 -0700
     5.3 @@ -0,0 +1,162 @@
     5.4 +// vim: set sts=2 ts=8 sw=2 tw=99 et ft=c :
     5.5 +#include <sourcemod>
     5.6 +
     5.7 +public Plugin:myinfo = 
     5.8 +{
     5.9 +  name        = "Trie test",
    5.10 +  author      = "AlliedModders LLC",
    5.11 +  description = "Trie tests",
    5.12 +  version     = "1.0.0.0",
    5.13 +  url         = "http://www.sourcemod.net/"
    5.14 +};
    5.15 +
    5.16 +public OnPluginStart()
    5.17 +{
    5.18 +  RegServerCmd("test_tries", RunTests);
    5.19 +}
    5.20 +
    5.21 +public Action:RunTests(argc)
    5.22 +{
    5.23 +  new Handle:trie = CreateTrie();
    5.24 +
    5.25 +  for (new i = 0; i < 64; i++) {
    5.26 +    new String:buffer[24];
    5.27 +    Format(buffer, sizeof(buffer), "%d", i);
    5.28 +
    5.29 +    if (!SetTrieValue(trie, buffer, i))
    5.30 +      ThrowError("set trie to %d failed", i);
    5.31 +
    5.32 +    new value;
    5.33 +    if (!GetTrieValue(trie, buffer, value))
    5.34 +      ThrowError("get trie %d", i);
    5.35 +    if (value != i)
    5.36 +      ThrowError("get trie %d == %d", i, i);
    5.37 +  }
    5.38 +
    5.39 +  // Setting 17 without replace should fail.
    5.40 +  new value;
    5.41 +  if (SetTrieValue(trie, "17", 999, false))
    5.42 +    ThrowError("set trie 17 should fail");
    5.43 +  if (!GetTrieValue(trie, "17", value) || value != 17)
    5.44 +    ThrowError("value at 17 not correct");
    5.45 +  if (!SetTrieValue(trie, "17", 999))
    5.46 +    ThrowError("set trie 17 = 999 should succeed");
    5.47 +  if (!GetTrieValue(trie, "17", value) || value != 999)
    5.48 +    ThrowError("value at 17 not correct");
    5.49 +
    5.50 +  // Check size is 64.
    5.51 +  if (GetTrieSize(trie) != 64)
    5.52 +    ThrowError("trie size not 64");
    5.53 +
    5.54 +  // Check "cat" is not found.
    5.55 +  new array[64];
    5.56 +  new String:string[64];
    5.57 +  if (GetTrieValue(trie, "cat", value) ||
    5.58 +      GetTrieArray(trie, "cat", array, sizeof(array)) ||
    5.59 +      GetTrieString(trie, "cat", string, sizeof(string)))
    5.60 +  {
    5.61 +    ThrowError("trie should not have a cat");
    5.62 +  }
    5.63 +
    5.64 +  // Check that "17" is not a string or array.
    5.65 +  if (GetTrieArray(trie, "17", array, sizeof(array)) ||
    5.66 +      GetTrieString(trie, "17", string, sizeof(string)))
    5.67 +  {
    5.68 +    ThrowError("entry 17 should not be an array or string");
    5.69 +  }
    5.70 +
    5.71 +  // Strings.
    5.72 +  if (!SetTrieString(trie, "17", "hellokitty"))
    5.73 +    ThrowError("17 should be string");
    5.74 +  if (!GetTrieString(trie, "17", string, sizeof(string)) ||
    5.75 +      strcmp(string, "hellokitty") != 0)
    5.76 +  {
    5.77 +    ThrowError("17 should be hellokitty");
    5.78 +  }
    5.79 +  if (GetTrieValue(trie, "17", value) ||
    5.80 +      GetTrieArray(trie, "17", array, sizeof(array)))
    5.81 +  {
    5.82 +    ThrowError("entry 17 should not be an array or string");
    5.83 +  }
    5.84 +
    5.85 +  // Arrays.
    5.86 +  new data[5] = { 93, 1, 2, 3, 4 };
    5.87 +  if (!SetTrieArray(trie, "17", data, 5))
    5.88 +    ThrowError("17 should be string");
    5.89 +  if (!GetTrieArray(trie, "17", array, sizeof(array)))
    5.90 +    ThrowError("17 should be hellokitty");
    5.91 +  for (new i = 0; i < 5; i++) {
    5.92 +    if (data[i] != array[i])
    5.93 +      ThrowError("17 slot %d should be %d, got %d", i, data[i], array[i]);
    5.94 +  }
    5.95 +  if (GetTrieValue(trie, "17", value) ||
    5.96 +      GetTrieString(trie, "17", string, sizeof(string)))
    5.97 +  {
    5.98 +    ThrowError("entry 17 should not be an array or string");
    5.99 +  }
   5.100 +
   5.101 +  if (!SetTrieArray(trie, "17", data, 1))
   5.102 +    ThrowError("couldn't set 17 to 1-entry array");
   5.103 +  // Check that we fixed an old bug where 1-entry arrays where cells
   5.104 +  if (!GetTrieArray(trie, "17", array, sizeof(array), value))
   5.105 +    ThrowError("couldn't fetch 1-entry array");
   5.106 +  if (value != 1)
   5.107 +    ThrowError("array size mismatch (%d, expected %d)", value, 1);
   5.108 +  // Check that we maintained backward compatibility.
   5.109 +  if (!GetTrieValue(trie, "17", value))
   5.110 +    ThrowError("backwards compatibility failed");
   5.111 +  if (value != data[0])
   5.112 +    ThrowError("wrong value (%d, expected %d)", value, data[0]);
   5.113 +
   5.114 +  // Remove "17".
   5.115 +  if (!RemoveFromTrie(trie, "17"))
   5.116 +    ThrowError("17 should have been removed");
   5.117 +  if (RemoveFromTrie(trie, "17"))
   5.118 +    ThrowError("17 should not exist");
   5.119 +  if (GetTrieValue(trie, "17", value) ||
   5.120 +      GetTrieArray(trie, "17", array, sizeof(array)) ||
   5.121 +      GetTrieString(trie, "17", string, sizeof(string)))
   5.122 +  {
   5.123 +    ThrowError("trie should not have a 17");
   5.124 +  }
   5.125 +
   5.126 +  ClearTrie(trie);
   5.127 +
   5.128 +  if (GetTrieSize(trie))
   5.129 +    ThrowError("size should be 0");
   5.130 +
   5.131 +  SetTrieString(trie, "adventure", "time!");
   5.132 +  SetTrieString(trie, "butterflies", "bees");
   5.133 +  SetTrieString(trie, "egg", "egg");
   5.134 +
   5.135 +  new Handle:keys = CreateTrieSnapshot(trie);
   5.136 +  {
   5.137 +    if (TrieSnapshotLength(keys) != 3)
   5.138 +      ThrowError("trie snapshot length should be 3");
   5.139 +
   5.140 +    new bool:found[3];
   5.141 +    for (new i = 0; i < TrieSnapshotLength(keys); i++) {
   5.142 +      new size = TrieSnapshotKeyBufferSize(keys, i);
   5.143 +      new String:buffer[size];
   5.144 +      GetTrieSnapshotKey(keys, i, buffer, size);
   5.145 +
   5.146 +      if (strcmp(buffer, "adventure") == 0)
   5.147 +        found[0] = true;
   5.148 +      else if (strcmp(buffer, "butterflies") == 0)
   5.149 +        found[1] = true;
   5.150 +      else if (strcmp(buffer, "egg") == 0)
   5.151 +        found[2] = true;
   5.152 +      else
   5.153 +        ThrowError("unexpected key: %s", buffer);
   5.154 +    }
   5.155 +
   5.156 +    if (!found[0] || !found[1] || !found[2])
   5.157 +      ThrowError("did not find all keys");
   5.158 +  }
   5.159 +  CloseHandle(keys);
   5.160 +
   5.161 +  PrintToServer("All tests passed!");
   5.162 +  CloseHandle(trie);
   5.163 +  return Plugin_Handled;
   5.164 +}
   5.165 +

     6.1 --- a/public/amtl/am-hashmap.h	Thu Aug 29 11:11:41 2013 -0400
     6.2 +++ b/public/amtl/am-hashmap.h	Thu Aug 29 10:09:02 2013 -0700
     6.3 @@ -60,12 +60,28 @@
     6.4      Entry()
     6.5      {
     6.6      }
     6.7 +    Entry(Moveable<Entry> other)
     6.8 +      : key(Moveable<K>(other->key)),
     6.9 +        value(Moveable<V>(other->value))
    6.10 +    {
    6.11 +    }
    6.12  
    6.13      Entry(const K &aKey, const V &aValue)
    6.14       : key(aKey),
    6.15         value(aValue)
    6.16 -    {
    6.17 -    }
    6.18 +    { }
    6.19 +    Entry(const K &aKey, Moveable<V> aValue)
    6.20 +     : key(aKey),
    6.21 +       value(aValue)
    6.22 +    { }
    6.23 +    Entry(Moveable<K> aKey, const V &aValue)
    6.24 +     : key(aKey),
    6.25 +       value(aValue)
    6.26 +    { }
    6.27 +    Entry(Moveable<K> aKey, Moveable<V> aValue)
    6.28 +     : key(aKey),
    6.29 +       value(aValue)
    6.30 +    { }
    6.31    };
    6.32  
    6.33    struct Policy
    6.34 @@ -124,6 +140,18 @@
    6.35    bool add(Insert &i, const K &key, const V &value) {
    6.36      return table_.add(i, Entry(key, value));
    6.37    }
    6.38 +  bool add(Insert &i, Moveable<K> key, const V &value) {
    6.39 +    return table_.add(i, Entry(key, value));
    6.40 +  }
    6.41 +  bool add(Insert &i, const K &key, Moveable<V> value) {
    6.42 +    return table_.add(i, Entry(key, value));
    6.43 +  }
    6.44 +  bool add(Insert &i, Moveable<K> key, Moveable<V> value) {
    6.45 +    return table_.add(i, Entry(key, value));
    6.46 +  }
    6.47 +  bool add(Insert &i, Moveable<K> key) {
    6.48 +    return table_.add(i, Entry(key, V()));
    6.49 +  }
    6.50  
    6.51    // This can be used to avoid compiler constructed temporaries, since AMTL
    6.52    // does not yet support move semantics. If you use this, the key and value
    6.53 @@ -140,6 +168,10 @@
    6.54      table_.clear();
    6.55    }
    6.56  
    6.57 +  size_t elements() const {
    6.58 +    return table_.elements();
    6.59 +  }
    6.60 +
    6.61    size_t estimateMemoryUse() const {
    6.62      return table_.estimateMemoryUse();
    6.63    }

     7.1 --- a/public/amtl/am-hashtable.h	Thu Aug 29 11:11:41 2013 -0400
     7.2 +++ b/public/amtl/am-hashtable.h	Thu Aug 29 10:09:02 2013 -0700
     7.3 @@ -35,6 +35,7 @@
     7.4  #include <stdlib.h>
     7.5  #include "am-allocator-policies.h"
     7.6  #include "am-utility.h"
     7.7 +#include "am-moveable.h"
     7.8  
     7.9  namespace ke {
    7.10  
    7.11 @@ -50,8 +51,16 @@
    7.12      static const uint32_t kRemovedHash = 1;
    7.13    
    7.14     public:
    7.15 -    void setHash(uint32_t hash, const T &t) {
    7.16 +    void setHash(uint32_t hash) {
    7.17        hash_ = hash;
    7.18 +    }
    7.19 +    void construct() {
    7.20 +      new (&t_) T();
    7.21 +    }
    7.22 +    void construct(const T &t) {
    7.23 +      new (&t_) T(t);
    7.24 +    }
    7.25 +    void construct(Moveable<T> t) {
    7.26        new (&t_) T(t);
    7.27      }
    7.28      uint32_t hash() const {
    7.29 @@ -257,7 +266,8 @@
    7.30        Entry &oldEntry = oldTable[i];
    7.31        if (oldEntry.isLive()) {
    7.32          Insert p = insertUnique(oldEntry.hash());
    7.33 -        p.entry().setHash(p.hash(), oldEntry.payload());
    7.34 +        p.entry().setHash(p.hash());
    7.35 +        p.entry().construct(Moveable<Payload>(oldEntry.payload()));
    7.36        }
    7.37        oldEntry.destruct();
    7.38      }
    7.39 @@ -290,8 +300,8 @@
    7.40        if (e->free())
    7.41          break;
    7.42        if (e->isLive() &&
    7.43 -        e->sameHash(hash) &&
    7.44 -        HashPolicy::matches(key, e->payload()))
    7.45 +          e->sameHash(hash) &&
    7.46 +          HashPolicy::matches(key, e->payload()))
    7.47        {
    7.48          return Result(e);
    7.49        }
    7.50 @@ -318,7 +328,7 @@
    7.51      return Insert(e, hash);
    7.52    }
    7.53  
    7.54 -  bool internalAdd(Insert &i, const Payload &payload) {
    7.55 +  bool internalAdd(Insert &i) {
    7.56      assert(!i.found());
    7.57  
    7.58      // If the entry is deleted, just re-use the slot.
    7.59 @@ -345,8 +355,8 @@
    7.60          i = insertUnique(i.hash());
    7.61      }
    7.62  
    7.63 -    i.entry().setHash(i.hash(), payload);
    7.64      nelements_++;
    7.65 +    i.entry().setHash(i.hash());
    7.66      return true;
    7.67    }
    7.68  
    7.69 @@ -423,10 +433,22 @@
    7.70    // The table must not have been mutated in between findForAdd() and add().
    7.71    // The Insert object is still valid after add() returns, however.
    7.72    bool add(Insert &i, const Payload &payload) {
    7.73 -    return internalAdd(i, payload);
    7.74 +    if (!internalAdd(i))
    7.75 +      return false;
    7.76 +    i.entry().construct(payload);
    7.77 +    return true;
    7.78 +  }
    7.79 +  bool add(Insert &i, Moveable<Payload> payload) {
    7.80 +    if (!internalAdd(i))
    7.81 +      return false;
    7.82 +    i.entry().construct(payload);
    7.83 +    return true;
    7.84    }
    7.85    bool add(Insert &i) {
    7.86 -    return internalAdd(i, Payload());
    7.87 +    if (!internalAdd(i))
    7.88 +      return false;
    7.89 +    i.entry().construct();
    7.90 +    return true;
    7.91    }
    7.92  
    7.93    bool checkDensity() {
    7.94 @@ -445,6 +467,10 @@
    7.95      nelements_ = 0;
    7.96    }
    7.97  
    7.98 +  size_t elements() const {
    7.99 +    return nelements_;
   7.100 +  }
   7.101 +
   7.102    size_t estimateMemoryUse() const {
   7.103      return sizeof(Entry) * capacity_;
   7.104    }

     8.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     8.2 +++ b/public/amtl/am-moveable.h	Thu Aug 29 10:09:02 2013 -0700
     8.3 @@ -0,0 +1,66 @@
     8.4 +// vim: set sts=8 ts=2 sw=2 tw=99 et:
     8.5 +//
     8.6 +// Copyright (C) 2013, David Anderson and AlliedModders LLC
     8.7 +// All rights reserved.
     8.8 +// 
     8.9 +// Redistribution and use in source and binary forms, with or without
    8.10 +// modification, are permitted provided that the following conditions are met:
    8.11 +// 
    8.12 +//  * Redistributions of source code must retain the above copyright notice, this
    8.13 +//    list of conditions and the following disclaimer.
    8.14 +//  * Redistributions in binary form must reproduce the above copyright notice,
    8.15 +//    this list of conditions and the following disclaimer in the documentation
    8.16 +//    and/or other materials provided with the distribution.
    8.17 +//  * Neither the name of AlliedModders LLC nor the names of its contributors
    8.18 +//    may be used to endorse or promote products derived from this software
    8.19 +//    without specific prior written permission.
    8.20 +//
    8.21 +// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
    8.22 +// AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
    8.23 +// IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
    8.24 +// ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
    8.25 +// LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
    8.26 +// CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
    8.27 +// SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
    8.28 +// INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
    8.29 +// CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
    8.30 +// ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
    8.31 +// POSSIBILITY OF SUCH DAMAGE.
    8.32 +
    8.33 +#ifndef _include_amtl_moveable_h_
    8.34 +#define _include_amtl_moveable_h_
    8.35 +
    8.36 +namespace ke {
    8.37 +
    8.38 +// This is a feature in C++11, but since AM projects do not have access to
    8.39 +// C++11 yet, we provide templates to implement move semantics. A class can
    8.40 +// provide a constructor for (ke::Moveable<T> t) which containers will try
    8.41 +// to use.
    8.42 +//
    8.43 +// When implementing a constructor that takes a Moveable, the object being
    8.44 +// moved should be left in a state that is safe, since its destructor will
    8.45 +// be called even though it has been moved.
    8.46 +
    8.47 +template <typename T>
    8.48 +struct Moveable
    8.49 +{
    8.50 + public:
    8.51 +  explicit Moveable(T &t)
    8.52 +   : t_(t)
    8.53 +  {
    8.54 +  }
    8.55 +
    8.56 +  T *operator ->() {
    8.57 +    return &t_;
    8.58 +  }
    8.59 +  operator T &() {
    8.60 +    return t_;
    8.61 +  }
    8.62 +
    8.63 + private:
    8.64 +  T &t_;
    8.65 +};
    8.66 +
    8.67 +} // namespace ke
    8.68 +
    8.69 +#endif // _include_amtl_moveable_h_

     9.1 --- a/public/amtl/am-string.h	Thu Aug 29 11:11:41 2013 -0400
     9.2 +++ b/public/amtl/am-string.h	Thu Aug 29 10:09:02 2013 -0700
     9.3 @@ -33,6 +33,7 @@
     9.4  #include <stdlib.h>
     9.5  #include <string.h>
     9.6  #include <am-utility.h>
     9.7 +#include <am-moveable.h>
     9.8  
     9.9  namespace ke {
    9.10  
    9.11 @@ -54,6 +55,12 @@
    9.12      if (other.length_)
    9.13        set(other.chars_, other.length_);
    9.14    }
    9.15 +  AString(Moveable<AString> other)
    9.16 +    : chars_(other->chars_.take()),
    9.17 +      length_(other->length_)
    9.18 +  {
    9.19 +    other->length_ = 0;
    9.20 +  }
    9.21  
    9.22    AString &operator =(const char *str) {
    9.23      if (str && str[0]) {

    10.1 --- a/public/amtl/am-vector.h	Thu Aug 29 11:11:41 2013 -0400
    10.2 +++ b/public/amtl/am-vector.h	Thu Aug 29 10:09:02 2013 -0700
    10.3 @@ -34,6 +34,7 @@
    10.4  #include <stdlib.h>
    10.5  #include <am-allocator-policies.h>
    10.6  #include <am-utility.h>
    10.7 +#include <am-moveable.h>
    10.8  
    10.9  namespace ke {
   10.10  
   10.11 @@ -163,7 +164,7 @@
   10.12      if (newdata == NULL)
   10.13        return false;
   10.14      for (size_t i = 0; i < nitems_; i++) {
   10.15 -      new (&newdata[i]) T(data_[i]);
   10.16 +      new (&newdata[i]) T(Moveable<T>(data_[i]));
   10.17        data_[i].~T();
   10.18      }
   10.19      this->free(data_);

    11.1 --- a/public/sm_stringhashmap.h	Thu Aug 29 11:11:41 2013 -0400
    11.2 +++ b/public/sm_stringhashmap.h	Thu Aug 29 10:09:02 2013 -0700
    11.3 @@ -47,6 +47,7 @@
    11.4  #include <am-allocator-policies.h>
    11.5  #include <am-hashmap.h>
    11.6  #include <am-string.h>
    11.7 +#include <am-moveable.h>
    11.8  #include <string.h>
    11.9  
   11.10  namespace SourceMod
   11.11 @@ -113,6 +114,7 @@
   11.12  	}
   11.13  
   11.14  	typedef typename Internal::Result Result;
   11.15 +	typedef typename Internal::Insert Insert;
   11.16  	typedef typename Internal::iterator iterator;
   11.17  
   11.18  	// Some KTrie-like helper functions.
   11.19 @@ -143,7 +145,7 @@
   11.20  	bool replace(const char *aKey, const T &value)
   11.21  	{
   11.22  		CharsAndLength key(aKey);
   11.23 -		typename Internal::Insert i = internal_.findForAdd(key);
   11.24 +		Insert i = internal_.findForAdd(key);
   11.25  		if (!i.found())
   11.26  		{
   11.27  			memory_used_ += key.length() + 1;
   11.28 @@ -158,7 +160,7 @@
   11.29  	bool insert(const char *aKey, const T &value)
   11.30  	{
   11.31  		CharsAndLength key(aKey);
   11.32 -		typename Internal::Insert i = internal_.findForAdd(key);
   11.33 +		Insert i = internal_.findForAdd(key);
   11.34  		if (i.found())
   11.35  			return false;
   11.36  		if (!internal_.add(i))
   11.37 @@ -190,14 +192,45 @@
   11.38  		internal_.clear();
   11.39  	}
   11.40  
   11.41 -	iterator iter() {
   11.42 +	iterator iter()
   11.43 +	{
   11.44  		return internal_.iter();
   11.45  	}
   11.46  
   11.47 -	size_t mem_usage() const {
   11.48 +	size_t mem_usage() const
   11.49 +	{
   11.50  		return internal_.estimateMemoryUse() + memory_used_;
   11.51  	}
   11.52  
   11.53 +	size_t elements() const
   11.54 +	{
   11.55 +		return internal_.elements();
   11.56 +	}
   11.57 +
   11.58 +
   11.59 +	Insert findForAdd(const char *aKey)
   11.60 +	{
   11.61 +		CharsAndLength key(aKey);
   11.62 +		return internal_.findForAdd(key);
   11.63 +	}
   11.64 +
   11.65 +	// Note that |i->key| must be set after calling this, and the key must
   11.66 +	// be the same as used with findForAdd(). It is best to avoid these two
   11.67 +	// functions as the combined variants above are safer.
   11.68 +	bool add(Insert &i)
   11.69 +	{
   11.70 +		return internal_.add(i);
   11.71 +	}
   11.72 +
   11.73 +	// Only value needs to be set after.
   11.74 +	bool add(Insert &i, const char *aKey)
   11.75 +	{
   11.76 +		if (!internal_.add(i))
   11.77 +			return false;
   11.78 +		i->key = aKey;
   11.79 +		return true;
   11.80 +	}
   11.81 +
   11.82  private:
   11.83  	Internal internal_;
   11.84  	size_t memory_used_;