1.1 --- a/public/amtl/am-hashmap.h	Sat Aug 24 23:56:39 2013 -0400
     1.2 +++ b/public/amtl/am-hashmap.h	Sun Aug 25 01:42:14 2013 -0700
     1.3 @@ -131,6 +131,10 @@
     1.4      return table_.add(i);
     1.5    }
     1.6  
     1.7 +  void clear() {
     1.8 +    table_.clear();
     1.9 +  }
    1.10 +
    1.11    size_t estimateMemoryUse() const {
    1.12      return table_.estimateMemoryUse();
    1.13    }

     2.1 --- a/public/amtl/am-hashtable.h	Sat Aug 24 23:56:39 2013 -0400
     2.2 +++ b/public/amtl/am-hashtable.h	Sun Aug 25 01:42:14 2013 -0700
     2.3 @@ -60,6 +60,10 @@
     2.4        destruct();
     2.5        hash_ = kRemovedHash;
     2.6      }
     2.7 +    void setFree() {
     2.8 +      destruct();
     2.9 +      hash_ = kFreeHash;
    2.10 +    }
    2.11      void initialize() {
    2.12        hash_ = kFreeHash;
    2.13      }
    2.14 @@ -432,6 +436,14 @@
    2.15      return true;
    2.16    }
    2.17  
    2.18 +  void clear() {
    2.19 +    for (size_t i = 0; i < capacity_; i++) {
    2.20 +      table_[i].setFree();
    2.21 +    }
    2.22 +    ndeleted_ = 0;
    2.23 +    nelements_ = 0;
    2.24 +  }
    2.25 +
    2.26    size_t estimateMemoryUse() const {
    2.27      return sizeof(Entry) * capacity_;
    2.28    }

     3.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     3.2 +++ b/public/sm_stringhashmap.h	Sun Aug 25 01:42:14 2013 -0700
     3.3 @@ -0,0 +1,178 @@
     3.4 +/**
     3.5 + * vim: set ts=4 sw=4 tw=99 noet :
     3.6 + * =============================================================================
     3.7 + * SourceMod
     3.8 + * Copyright (C) 2004-2008 AlliedModders LLC.  All rights reserved.
     3.9 + * =============================================================================
    3.10 + *
    3.11 + * This program is free software; you can redistribute it and/or modify it under
    3.12 + * the terms of the GNU General Public License, version 3.0, as published by the
    3.13 + * Free Software Foundation.
    3.14 + * 
    3.15 + * This program is distributed in the hope that it will be useful, but WITHOUT
    3.16 + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
    3.17 + * FOR A PARTICULAR PURPOSE.  See the GNU General Public License for more
    3.18 + * details.
    3.19 + *
    3.20 + * You should have received a copy of the GNU General Public License along with
    3.21 + * this program.  If not, see <http://www.gnu.org/licenses/>.
    3.22 + *
    3.23 + * As a special exception, AlliedModders LLC gives you permission to link the
    3.24 + * code of this program (as well as its derivative works) to "Half-Life 2," the
    3.25 + * "Source Engine," the "SourcePawn JIT," and any Game MODs that run on software
    3.26 + * by the Valve Corporation.  You must obey the GNU General Public License in
    3.27 + * all respects for all other code used.  Additionally, AlliedModders LLC grants
    3.28 + * this exception to all derivative works.  AlliedModders LLC defines further
    3.29 + * exceptions, found in LICENSE.txt (as of this writing, version JULY-31-2007),
    3.30 + * or <http://www.sourcemod.net/license.php>.
    3.31 + *
    3.32 + * Version: $Id$
    3.33 + */
    3.34 +
    3.35 +#ifndef _include_sourcemod_hashtable_h_
    3.36 +#define _include_sourcemod_hashtable_h_
    3.37 +
    3.38 +#include <am-allocator-policies.h>
    3.39 +#include <am-hashmap.h>
    3.40 +#include <am-string.h>
    3.41 +#include <string.h>
    3.42 +
    3.43 +namespace SourceMod
    3.44 +{
    3.45 +
    3.46 +using namespace ke;
    3.47 +
    3.48 +namespace detail
    3.49 +{
    3.50 +	class CharsAndLength
    3.51 +	{
    3.52 +	 public:
    3.53 +	  CharsAndLength(const char *str)
    3.54 +		: str_(str),
    3.55 +		  length_(0)
    3.56 +	  {
    3.57 +		  int c;
    3.58 +		  uint32_t hash = 0;
    3.59 +		  while ((c = *str++))
    3.60 +			  hash = c + (hash << 6) + (hash << 16) - hash;
    3.61 +		  hash_ = hash;
    3.62 +		  length_ = str - str_ - 1;
    3.63 +	  }
    3.64 +
    3.65 +	  uint32_t hash() const {
    3.66 +		  return hash_;
    3.67 +	  }
    3.68 +	  const char *chars() const {
    3.69 +		  return str_;
    3.70 +	  }
    3.71 +	  size_t length() const {
    3.72 +		  return length_;
    3.73 +	  }
    3.74 +
    3.75 +	 private:
    3.76 +	  const char *str_;
    3.77 +	  size_t length_;
    3.78 +	  uint32_t hash_;
    3.79 +	};
    3.80 +
    3.81 +	struct StringHashMapPolicy
    3.82 +	{
    3.83 +		static inline bool matches(const CharsAndLength &lookup, const AString &key) {
    3.84 +			return lookup.length() == key.length() &&
    3.85 +				   memcmp(lookup.chars(), key.chars(), key.length()) == 0;
    3.86 +		}
    3.87 +		static inline uint32_t hash(const CharsAndLength &key) {
    3.88 +			return key.hash();
    3.89 +		}
    3.90 +	};
    3.91 +}
    3.92 +
    3.93 +template <typename T>
    3.94 +class StringHashMap
    3.95 +{
    3.96 +	typedef detail::CharsAndLength CharsAndLength;
    3.97 +	typedef HashMap<AString, T, detail::StringHashMapPolicy> Internal;
    3.98 +
    3.99 +public:
   3.100 +	StringHashMap()
   3.101 +		: internal_(SystemAllocatorPolicy()),
   3.102 +		  memory_used_(0)
   3.103 +	{
   3.104 +		if (!internal_.init())
   3.105 +			internal_.reportOutOfMemory();
   3.106 +	}
   3.107 +
   3.108 +	// Some KTrie-like helper functions.
   3.109 +	bool retrieve(const char *aKey, T *aResult = NULL)
   3.110 +	{
   3.111 +		CharsAndLength key(aKey);
   3.112 +		typename Internal::Result r = internal_.find(key);
   3.113 +		if (!r.found())
   3.114 +			return false;
   3.115 +		if (aResult)
   3.116 +			*aResult = r->value;
   3.117 +		return true;
   3.118 +	}
   3.119 +
   3.120 +	bool contains(const char *aKey)
   3.121 +	{
   3.122 +		CharsAndLength key(aKey);
   3.123 +		typename Internal::Result r = internal_.find(key);
   3.124 +		return r.found();
   3.125 +	}
   3.126 +
   3.127 +	bool replace(const char *aKey, const T &value)
   3.128 +	{
   3.129 +		CharsAndLength key(aKey);
   3.130 +		typename Internal::Insert i = internal_.findForAdd(key);
   3.131 +		if (!i.found())
   3.132 +		{
   3.133 +			memory_used_ += key.length() + 1;
   3.134 +			return internal_.add(i, value);
   3.135 +		}
   3.136 +		i->value = value;
   3.137 +		return true;
   3.138 +	}
   3.139 +
   3.140 +	bool insert(const char *aKey, const T &value)
   3.141 +	{
   3.142 +		CharsAndLength key(aKey);
   3.143 +		typename Internal::Insert i = internal_.findForAdd(key);
   3.144 +		if (i.found())
   3.145 +			return false;
   3.146 +		if (!internal_.add(i))
   3.147 +			return false;
   3.148 +		memory_used_ += key.length() + 1;
   3.149 +		i->key = aKey;
   3.150 +		i->value = value;
   3.151 +		return true;
   3.152 +	}
   3.153 +
   3.154 +	bool remove(const char *aKey)
   3.155 +	{
   3.156 +		CharsAndLength key(aKey);
   3.157 +		typename Internal::Result r = internal_.find(key);
   3.158 +		if (!r.found())
   3.159 +			return false;
   3.160 +		memory_used_ -= key.length() + 1;
   3.161 +		internal_.remove(r);
   3.162 +		return true;
   3.163 +	}
   3.164 +
   3.165 +	void clear()
   3.166 +	{
   3.167 +		internal_.clear();
   3.168 +	}
   3.169 +
   3.170 +	size_t mem_usage() const {
   3.171 +		return internal_.estimateMemoryUse() + memory_used_;
   3.172 +	}
   3.173 +
   3.174 +private:
   3.175 +	Internal internal_;
   3.176 +	size_t memory_used_;
   3.177 +};
   3.178 +
   3.179 +}
   3.180 +
   3.181 +#endif // _include_sourcemod_hashtable_h_

     4.1 --- a/public/sm_trie_tpl.h	Sat Aug 24 23:56:39 2013 -0400
     4.2 +++ b/public/sm_trie_tpl.h	Sun Aug 25 01:42:14 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
     4.9   * Copyright (C) 2004-2008 AlliedModders LLC.  All rights reserved.
    4.10 @@ -45,11 +45,15 @@
    4.11  };
    4.12  
    4.13  /**
    4.14 - * @brief Trie class for storing key/value pairs, based on double array tries.
    4.15 - * @file sm_trie_tpl.h
    4.16 + * @brief DEPRECATED. This class scales extremely poorly; insertion scales
    4.17 + * quadratic (O(n^2)) with respect to the number of elements in the table.
    4.18 + * Only use this class if you have less than 200 elements or so. Otherwise,
    4.19 + * use StringHashMap in sm_hashtable.h which scales linearly and has comparable
    4.20 + * retrievable performance.
    4.21   *
    4.22 - * For full works cited and implementation overview, there is a big comment 
    4.23 - * block at the bottom of this file.
    4.24 + * See bug 5878 for more detail.
    4.25 + *
    4.26 + * @file sm_trie_tpl.h
    4.27   */
    4.28  
    4.29  template <typename K>