1.1 --- a/public/amtl/am-allocator-policies.h	Sat Aug 24 00:12:21 2013 -0400
     1.2 +++ b/public/amtl/am-allocator-policies.h	Fri Aug 23 22:29:44 2013 -0700
     1.3 @@ -38,7 +38,7 @@
     1.4  // The default system allocator policy will crash on out-of-memory.
     1.5  class SystemAllocatorPolicy
     1.6  {
     1.7 -  protected:
     1.8 +  public:
     1.9      void reportOutOfMemory() {
    1.10        fprintf(stderr, "OUT OF MEMORY\n");
    1.11        abort();

     2.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     2.2 +++ b/public/amtl/am-hashmap.h	Fri Aug 23 22:29:44 2013 -0700
     2.3 @@ -0,0 +1,133 @@
     2.4 +// vim: set sts=8 ts=2 sw=2 tw=99 et:
     2.5 +//
     2.6 +// Copyright (C) 2013, David Anderson and AlliedModders LLC
     2.7 +// All rights reserved.
     2.8 +// 
     2.9 +// Redistribution and use in source and binary forms, with or without
    2.10 +// modification, are permitted provided that the following conditions are met:
    2.11 +// 
    2.12 +//  * Redistributions of source code must retain the above copyright notice, this
    2.13 +//  list of conditions and the following disclaimer.
    2.14 +//  * Redistributions in binary form must reproduce the above copyright notice,
    2.15 +//  this list of conditions and the following disclaimer in the documentation
    2.16 +//  and/or other materials provided with the distribution.
    2.17 +//  * Neither the name of AlliedModders LLC nor the names of its contributors
    2.18 +//  may be used to endorse or promote products derived from this software
    2.19 +//  without specific prior written permission.
    2.20 +//
    2.21 +// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
    2.22 +// AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
    2.23 +// IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
    2.24 +// ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
    2.25 +// LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
    2.26 +// CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
    2.27 +// SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
    2.28 +// INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
    2.29 +// CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
    2.30 +// ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
    2.31 +// POSSIBILITY OF SUCH DAMAGE.
    2.32 +
    2.33 +#ifndef _include_amtl_hashmap_h_
    2.34 +#define _include_amtl_hashmap_h_
    2.35 +
    2.36 +#include <am-hashtable.h>
    2.37 +
    2.38 +namespace ke {
    2.39 +
    2.40 +// Template parameters:
    2.41 +//
    2.42 +// K - Key type.
    2.43 +// V - Value type.
    2.44 +// HashPolicy - A struct with a hash and comparator function for each lookup type:
    2.45 +//     static uint32_t hash(const Type &value);
    2.46 +//     static bool matches(const Type &value, const K &key);
    2.47 +//
    2.48 +// All types that match a given key, must compute the same hash.
    2.49 +//
    2.50 +// Note that like HashTable, a HashMap is not usable until init() has been called.
    2.51 +template <typename K,
    2.52 +          typename V,
    2.53 +          typename HashPolicy,
    2.54 +          typename AllocPolicy = SystemAllocatorPolicy>
    2.55 +class HashMap : public AllocPolicy
    2.56 +{
    2.57 + private:
    2.58 +  struct Entry
    2.59 +  {
    2.60 +    K key;
    2.61 +    V value;
    2.62 +
    2.63 +    Entry(const K &aKey, const V &aValue)
    2.64 +     : key(aKey),
    2.65 +       value(aValue)
    2.66 +    {
    2.67 +    }
    2.68 +  };
    2.69 +
    2.70 +  struct Policy
    2.71 +  {
    2.72 +    typedef Entry Payload;
    2.73 +
    2.74 +    template <typename Lookup>
    2.75 +    static uint32_t hash(const Lookup &key) {
    2.76 +      return HashPolicy::hash(key);
    2.77 +    }
    2.78 +
    2.79 +    template <typename Lookup>
    2.80 +    static bool matches(const Lookup &key, const Payload &payload) {
    2.81 +      return HashPolicy::matches(key, payload.key);
    2.82 +    }
    2.83 +  };
    2.84 +
    2.85 +  typedef HashTable<Policy, AllocPolicy> Internal;
    2.86 +
    2.87 + public:
    2.88 +  HashMap(AllocPolicy ap = AllocPolicy())
    2.89 +    : table_(ap)
    2.90 +  {
    2.91 +  }
    2.92 +
    2.93 +  // capacity must be a power of two.
    2.94 +  bool init(size_t capacity = 16) {
    2.95 +    return table_.init(capacity);
    2.96 +  }
    2.97 +
    2.98 +  typedef typename Internal::Result Result;
    2.99 +  typedef typename Internal::Insert Insert;
   2.100 +
   2.101 +  template <typename Lookup>
   2.102 +  Result find(const Lookup &key) {
   2.103 +    return table_.find(key);
   2.104 +  }
   2.105 +
   2.106 +  template <typename Lookup>
   2.107 +  Insert findForAdd(const Lookup &key) {
   2.108 +    return table_.findForAdd(key);
   2.109 +  }
   2.110 +
   2.111 +  template <typename Lookup>
   2.112 +  void removeIfExists(const Lookup &key) {
   2.113 +    return table_.remove(key);
   2.114 +  }
   2.115 +
   2.116 +  void remove(Result &r) {
   2.117 +    table_.remove(r);
   2.118 +  }
   2.119 +
   2.120 +  // The map must not have been mutated in between findForAdd() and add().
   2.121 +  // The Insert object is still valid after add() returns, however.
   2.122 +  bool add(Insert &i, const K &key, const V &value) {
   2.123 +    return table_.add(i, Entry(key, value));
   2.124 +  }
   2.125 +
   2.126 +  size_t estimateMemoryUse() const {
   2.127 +    return table_.estimateMemoryUse();
   2.128 +  }
   2.129 +
   2.130 + private:
   2.131 +  Internal table_;
   2.132 +};
   2.133 +
   2.134 +}
   2.135 +
   2.136 +#endif // _include_amtl_hashmap_h_

     3.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     3.2 +++ b/public/amtl/am-hashtable.h	Fri Aug 23 22:29:44 2013 -0700
     3.3 @@ -0,0 +1,586 @@
     3.4 +// vim: set sts=8 ts=2 sw=2 tw=99 et:
     3.5 +//
     3.6 +// Copyright (C) 2013, David Anderson and AlliedModders LLC
     3.7 +// All rights reserved.
     3.8 +// 
     3.9 +// Redistribution and use in source and binary forms, with or without
    3.10 +// modification, are permitted provided that the following conditions are met:
    3.11 +// 
    3.12 +//  * Redistributions of source code must retain the above copyright notice, this
    3.13 +//  list of conditions and the following disclaimer.
    3.14 +//  * Redistributions in binary form must reproduce the above copyright notice,
    3.15 +//  this list of conditions and the following disclaimer in the documentation
    3.16 +//  and/or other materials provided with the distribution.
    3.17 +//  * Neither the name of AlliedModders LLC nor the names of its contributors
    3.18 +//  may be used to endorse or promote products derived from this software
    3.19 +//  without specific prior written permission.
    3.20 +//
    3.21 +// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
    3.22 +// AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
    3.23 +// IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
    3.24 +// ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
    3.25 +// LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
    3.26 +// CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
    3.27 +// SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
    3.28 +// INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
    3.29 +// CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
    3.30 +// ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
    3.31 +// POSSIBILITY OF SUCH DAMAGE.
    3.32 +
    3.33 +#ifndef _INCLUDE_KEIMA_HASHTABLE_H_
    3.34 +#define _INCLUDE_KEIMA_HASHTABLE_H_
    3.35 +
    3.36 +#include <new>
    3.37 +#include <limits.h>
    3.38 +#include <stdlib.h>
    3.39 +#include "am-utility.h"
    3.40 +
    3.41 +namespace ke {
    3.42 +
    3.43 +namespace detail {
    3.44 +  template <typename T>
    3.45 +  class HashTableEntry
    3.46 +  {
    3.47 +    uint32_t hash_;
    3.48 +    T t_;
    3.49 +  
    3.50 +   public:
    3.51 +    static const uint32_t kFreeHash = 0;
    3.52 +    static const uint32_t kRemovedHash = 1;
    3.53 +  
    3.54 +   public:
    3.55 +    void setHash(uint32_t hash, const T &t) {
    3.56 +      hash_ = hash;
    3.57 +      new (&t_) T(t);
    3.58 +    }
    3.59 +    uint32_t hash() const {
    3.60 +      return hash_;
    3.61 +    }
    3.62 +    void setRemoved() {
    3.63 +      destruct();
    3.64 +      hash_ = kRemovedHash;
    3.65 +    }
    3.66 +    void initialize() {
    3.67 +      hash_ = kFreeHash;
    3.68 +    }
    3.69 +    void destruct() {
    3.70 +      if (isLive())
    3.71 +        t_.~T();
    3.72 +    }
    3.73 +    bool removed() const {
    3.74 +      return hash_ == kRemovedHash;
    3.75 +    }
    3.76 +    bool free() const {
    3.77 +      return hash_ == kFreeHash;
    3.78 +    }
    3.79 +    bool isLive() const {
    3.80 +      return hash_ > kRemovedHash;
    3.81 +    }
    3.82 +    T &payload() {
    3.83 +      assert(isLive());
    3.84 +      return t_;
    3.85 +    }
    3.86 +    bool sameHash(uint32_t hash) const {
    3.87 +      return hash_ == hash;
    3.88 +    }
    3.89 +  
    3.90 +   private:
    3.91 +    HashTableEntry(const HashTableEntry &other) KE_DELETE;
    3.92 +    HashTableEntry &operator =(const HashTableEntry &other) KE_DELETE;
    3.93 +  };
    3.94 +}
    3.95 +
    3.96 +// The HashPolicy for the table must have the following members:
    3.97 +//
    3.98 +//     Payload
    3.99 +//     static uint32_t hash(const LookupType &key);
   3.100 +//     static bool matches(const LookupType &key, const Payload &other);
   3.101 +//
   3.102 +// Payload must be a type, and LookupType is any type that lookups will be
   3.103 +// performed with (these functions can be overloaded). Example:
   3.104 +//
   3.105 +//     struct Policy {
   3.106 +//       typedef KeyValuePair Payload;
   3.107 +//       static uint32 hash(const Key &key) {
   3.108 +//         ...
   3.109 +//       }
   3.110 +//       static bool matches(const Key &key, const KeyValuePair &pair) {
   3.111 +//         ...
   3.112 +//       }
   3.113 +//     };
   3.114 +//
   3.115 +// Note that the table is not usable until init() has been called.
   3.116 +//
   3.117 +template <typename HashPolicy, typename AllocPolicy = SystemAllocatorPolicy>
   3.118 +class HashTable : public AllocPolicy
   3.119 +{
   3.120 +  friend class iterator;
   3.121 +
   3.122 +  typedef typename HashPolicy::Payload Payload;
   3.123 +  typedef detail::HashTableEntry<Payload> Entry;
   3.124 +
   3.125 + private:
   3.126 +  static const uint32_t kMinCapacity = 16;
   3.127 +  static const uint32_t kMaxCapacity = INT_MAX / sizeof(Entry);
   3.128 +
   3.129 +  template <typename Key>
   3.130 +  uint32_t computeHash(const Key &key) {
   3.131 +    // Multiply by golden ratio.
   3.132 +    uint32_t hash = HashPolicy::hash(key) * 0x9E3779B9;
   3.133 +    if (hash == Entry::kFreeHash || hash == Entry::kRemovedHash)
   3.134 +      hash += 2;
   3.135 +    return hash;
   3.136 +  }
   3.137 +
   3.138 +  Entry *createTable(uint32_t capacity) {
   3.139 +    assert(capacity <= kMaxCapacity);
   3.140 +
   3.141 +    Entry *table = (Entry *)this->malloc(capacity * sizeof(Entry));
   3.142 +    if (!table)
   3.143 +      return NULL;
   3.144 +
   3.145 +    for (size_t i = 0; i < capacity; i++)
   3.146 +      table[i].initialize();
   3.147 +
   3.148 +    return table;
   3.149 +  }
   3.150 +
   3.151 + public:
   3.152 +  class Result
   3.153 +  {
   3.154 +    friend class HashTable;
   3.155 +
   3.156 +    Entry *entry_;
   3.157 +
   3.158 +    Entry &entry() {
   3.159 +      return *entry_;
   3.160 +    }
   3.161 +
   3.162 +   public:
   3.163 +    Result(Entry *entry)
   3.164 +      : entry_(entry)
   3.165 +    { }
   3.166 +
   3.167 +    Payload * operator ->() {
   3.168 +      return &entry_->payload();
   3.169 +    }
   3.170 +    Payload & operator *() {
   3.171 +      return entry_->payload();
   3.172 +    }
   3.173 +
   3.174 +    bool found() const {
   3.175 +      return entry_->isLive();
   3.176 +    }
   3.177 +  };
   3.178 +
   3.179 +  class Insert : public Result
   3.180 +  {
   3.181 +    uint32_t hash_;
   3.182 +
   3.183 +   public:
   3.184 +    Insert(Entry *entry, uint32_t hash)
   3.185 +      : Result(entry),
   3.186 +      hash_(hash)
   3.187 +    {
   3.188 +    }
   3.189 +
   3.190 +    uint32_t hash() const {
   3.191 +      return hash_;
   3.192 +    }
   3.193 +  };
   3.194 +
   3.195 + private:
   3.196 +  class Probulator {
   3.197 +    uint32_t hash_;
   3.198 +    uint32_t capacity_;
   3.199 +
   3.200 +   public:
   3.201 +    Probulator(uint32_t hash, uint32_t capacity)
   3.202 +      : hash_(hash),
   3.203 +      capacity_(capacity)
   3.204 +    {
   3.205 +      assert(IsPowerOfTwo(capacity_)); 
   3.206 +    }
   3.207 +
   3.208 +    uint32_t entry() const {
   3.209 +      return hash_ & (capacity_ - 1);
   3.210 +    }
   3.211 +    uint32_t next() {
   3.212 +      hash_++;
   3.213 +      return entry();
   3.214 +    }
   3.215 +  };
   3.216 +
   3.217 +  bool underloaded() const {
   3.218 +    // Check if the table is underloaded: < 25% entries used.
   3.219 +    return (capacity_ > kMinCapacity) && (nelements_ + ndeleted_ < capacity_ / 4);
   3.220 +  }
   3.221 +  bool overloaded() const {
   3.222 +    // Grow if the table is overloaded: > 75% entries used.
   3.223 +    return (nelements_ + ndeleted_) > ((capacity_ / 2) + (capacity_ / 4));
   3.224 +  }
   3.225 +
   3.226 +  bool shrink() {
   3.227 +    if ((capacity_ >> 1) < minCapacity_)
   3.228 +      return true;
   3.229 +    return changeCapacity(capacity_ >> 1);
   3.230 +  }
   3.231 +  
   3.232 +  bool grow() {
   3.233 +    if (capacity_ >= kMaxCapacity) {
   3.234 +      this->reportAllocationOverflow();
   3.235 +      return false;
   3.236 +    }
   3.237 +    return changeCapacity(capacity_ << 1);
   3.238 +  }
   3.239 +
   3.240 +  bool changeCapacity(uint32_t newCapacity) {
   3.241 +    assert(newCapacity <= kMaxCapacity);
   3.242 +
   3.243 +    Entry *newTable = createTable(newCapacity);
   3.244 +    if (!newTable)
   3.245 +      return false;
   3.246 +
   3.247 +    Entry *oldTable = table_;
   3.248 +    uint32_t oldCapacity = capacity_;
   3.249 +
   3.250 +    table_ = newTable;
   3.251 +    capacity_ = newCapacity;
   3.252 +    ndeleted_ = 0;
   3.253 +
   3.254 +    for (uint32_t i = 0; i < oldCapacity; i++) {
   3.255 +      Entry &oldEntry = oldTable[i];
   3.256 +      if (oldEntry.isLive()) {
   3.257 +        Insert p = insertUnique(oldEntry.hash());
   3.258 +        p.entry().setHash(p.hash(), oldEntry.payload());
   3.259 +      }
   3.260 +      oldEntry.destruct();
   3.261 +    }
   3.262 +    this->free(oldTable);
   3.263 +
   3.264 +    return true;
   3.265 +  }
   3.266 +
   3.267 +  // For use when the key is known to be unique.
   3.268 +  Insert insertUnique(uint32_t hash) {
   3.269 +    Probulator probulator(hash, capacity_);
   3.270 +
   3.271 +    Entry *e = &table_[probulator.entry()];
   3.272 +    for (;;) {
   3.273 +      if (e->free() || e->removed())
   3.274 +        break;
   3.275 +      e = &table_[probulator.next()];
   3.276 +    }
   3.277 +
   3.278 +    return Insert(e, hash);
   3.279 +  }
   3.280 +
   3.281 +  template <typename Key>
   3.282 +  Result lookup(const Key &key) {
   3.283 +    uint32_t hash = computeHash(key);
   3.284 +    Probulator probulator(hash, capacity_);
   3.285 +
   3.286 +    Entry *e = &table_[probulator.entry()];
   3.287 +    for (;;) {
   3.288 +      if (e->free())
   3.289 +        break;
   3.290 +      if (e->isLive() &&
   3.291 +        e->sameHash(hash) &&
   3.292 +        HashPolicy::matches(key, e->payload()))
   3.293 +      {
   3.294 +        return Result(e);
   3.295 +      }
   3.296 +      e = &table_[probulator.next()];
   3.297 +    }
   3.298 +
   3.299 +    return Result(e);
   3.300 +  }
   3.301 +
   3.302 +  template <typename Key>
   3.303 +  Insert lookupForAdd(const Key &key) {
   3.304 +    uint32_t hash = computeHash(key);
   3.305 +    Probulator probulator(hash, capacity_);
   3.306 +
   3.307 +    Entry *e = &table_[probulator.entry()];
   3.308 +    for (;;) {
   3.309 +      if (!e->isLive())
   3.310 +        break;
   3.311 +      if (e->sameHash(hash) && HashPolicy::matches(key, e->payload()))
   3.312 +        break;
   3.313 +      e = &table_[probulator.next()];
   3.314 +    }
   3.315 +
   3.316 +    return Insert(e, hash);
   3.317 +  }
   3.318 +
   3.319 +  bool internalAdd(Insert &i, const Payload &payload) {
   3.320 +    assert(!i.found());
   3.321 +
   3.322 +    // If the entry is deleted, just re-use the slot.
   3.323 +    if (i.entry().removed()) {
   3.324 +      ndeleted_--;
   3.325 +    } else {
   3.326 +      // Otherwise, see if we're at max capacity.
   3.327 +      if (nelements_ == kMaxCapacity) {
   3.328 +        this->reportAllocationOverflow();
   3.329 +        return false;
   3.330 +      }
   3.331 +
   3.332 +      // Check if the table is over or underloaded. The table is always at
   3.333 +      // least 25% free, so this check is enough to guarantee one free slot.
   3.334 +      // (Without one free slot, insertion search could infinite loop.)
   3.335 +      uint32_t oldCapacity = capacity_;
   3.336 +      if (!checkDensity())
   3.337 +        return false;
   3.338 +
   3.339 +      // If the table changed size, we need to find a new insertion point.
   3.340 +      // Note that a removed entry is impossible: either we caught it above,
   3.341 +      // or we just resized and no entries are removed.
   3.342 +      if (capacity_ != oldCapacity)
   3.343 +        i = insertUnique(i.hash());
   3.344 +    }
   3.345 +
   3.346 +    i.entry().setHash(i.hash(), payload);
   3.347 +    nelements_++;
   3.348 +    return true;
   3.349 +  }
   3.350 +
   3.351 +  void removeEntry(Entry &e) {
   3.352 +    assert(e.isLive());
   3.353 +    e.setRemoved();
   3.354 +    ndeleted_++;
   3.355 +    nelements_--;
   3.356 +  }
   3.357 +
   3.358 + public:
   3.359 +  HashTable(AllocPolicy ap)
   3.360 +  : AllocPolicy(ap),
   3.361 +    capacity_(0),
   3.362 +    nelements_(0),
   3.363 +    ndeleted_(0),
   3.364 +    table_(NULL),
   3.365 +    minCapacity_(kMinCapacity)
   3.366 +  {
   3.367 +  }
   3.368 +
   3.369 +  ~HashTable()
   3.370 +  {
   3.371 +    for (uint32_t i = 0; i < capacity_; i++)
   3.372 +      table_[i].destruct();
   3.373 +    this->free(table_);
   3.374 +  }
   3.375 +
   3.376 +  bool init(uint32_t capacity = 0) {
   3.377 +    if (capacity < kMinCapacity) {
   3.378 +      capacity = kMinCapacity;
   3.379 +    } else if (capacity > kMaxCapacity) {
   3.380 +      this->reportAllocationOverflow();
   3.381 +      return false;
   3.382 +    }
   3.383 +
   3.384 +    minCapacity_ = capacity;
   3.385 +
   3.386 +    assert(IsPowerOfTwo(capacity));
   3.387 +    capacity_ = capacity;
   3.388 +
   3.389 +    table_ = createTable(capacity_);
   3.390 +    if (!table_)
   3.391 +      return false;
   3.392 +
   3.393 +    return true;
   3.394 +  }
   3.395 +
   3.396 +  // The Result object must not be used past mutating table operations.
   3.397 +  template <typename Key>
   3.398 +  Result find(const Key &key) {
   3.399 +    return lookup(key);
   3.400 +  }
   3.401 +
   3.402 +  // The Insert object must not be used past mutating table operations.
   3.403 +  template <typename Key>
   3.404 +  Insert findForAdd(const Key &key) {
   3.405 +    return lookupForAdd(key);
   3.406 +  }
   3.407 +
   3.408 +  template <typename Key>
   3.409 +  void removeIfExists(const Key &key) {
   3.410 +    Result r = find(key);
   3.411 +    if (!r.found())
   3.412 +      return;
   3.413 +    remove(r);
   3.414 +  }
   3.415 +
   3.416 +  void remove(Result &r) {
   3.417 +    assert(r.found());
   3.418 +    removeEntry(r.entry());
   3.419 +  }
   3.420 +
   3.421 +  // The table must not have been mutated in between findForAdd() and add().
   3.422 +  // The Insert object is still valid after add() returns, however.
   3.423 +  bool add(Insert &i, const Payload &payload) {
   3.424 +    return internalAdd(i, payload);
   3.425 +  }
   3.426 +
   3.427 +  bool checkDensity() {
   3.428 +    if (underloaded())
   3.429 +      return shrink(); 
   3.430 +    if (overloaded())
   3.431 +      return grow();
   3.432 +    return true;
   3.433 +  }
   3.434 +
   3.435 +  size_t estimateMemoryUse() const {
   3.436 +    return sizeof(Entry) * capacity_;
   3.437 +  }
   3.438 +
   3.439 + public:
   3.440 +  // It is illegal to mutate a HashTable during iteration.
   3.441 +  class iterator
   3.442 +  {
   3.443 +   public:
   3.444 +    iterator(HashTable *table)
   3.445 +      : table_(table),
   3.446 +      i_(table->table_),
   3.447 +      end_(table->table_ + table->capacity_)
   3.448 +    {
   3.449 +      while (i_ < end_ && !i_->isLive())
   3.450 +        i_++;
   3.451 +    }
   3.452 +
   3.453 +    bool empty() const {
   3.454 +      return i_ == end_;
   3.455 +    }
   3.456 +
   3.457 +    void erase() {
   3.458 +      assert(!empty());
   3.459 +      table_->removeEntry(*i_);
   3.460 +    }
   3.461 +
   3.462 +    const Payload &operator *() const {
   3.463 +      return i_->payload();
   3.464 +    }
   3.465 +
   3.466 +    void next() {
   3.467 +      do {
   3.468 +        i_++;
   3.469 +      } while (i_ < end_ && !i_->isLive());
   3.470 +    }
   3.471 +
   3.472 +   private:
   3.473 +    HashTable *table_;
   3.474 +    Entry *i_;
   3.475 +    Entry *end_;
   3.476 +  };
   3.477 +
   3.478 + private:
   3.479 +  HashTable(const HashTable &other) KE_DELETE;
   3.480 +  HashTable &operator =(const HashTable &other) KE_DELETE;
   3.481 +
   3.482 + private:
   3.483 +  uint32_t capacity_;
   3.484 +  uint32_t nelements_;
   3.485 +  uint32_t ndeleted_;
   3.486 +  Entry *table_;
   3.487 +  uint32_t minCapacity_;
   3.488 +};
   3.489 +
   3.490 +// Bob Jenkin's one-at-a-time hash function[1].
   3.491 +//
   3.492 +// [1] http://burtleburtle.net/bob/hash/doobs.html
   3.493 +class CharacterStreamHasher
   3.494 +{
   3.495 +  uint32_t hash;
   3.496 +
   3.497 + public:
   3.498 +  CharacterStreamHasher()
   3.499 +    : hash(0)
   3.500 +  { }
   3.501 +
   3.502 +  void add(char c) {
   3.503 +    hash += c;
   3.504 +    hash += (hash << 10);
   3.505 +    hash ^= (hash >> 6);
   3.506 +  }
   3.507 +
   3.508 +  void add(const char *s, size_t length) {
   3.509 +    for (size_t i = 0; i < length; i++)
   3.510 +      add(s[i]);
   3.511 +  }
   3.512 +
   3.513 +  uint32_t result() {
   3.514 +    hash += (hash << 3);
   3.515 +    hash ^= (hash >> 11);
   3.516 +    hash += (hash << 15);
   3.517 +    return hash;
   3.518 +  }
   3.519 +};
   3.520 +
   3.521 +static inline uint32_t
   3.522 +HashCharSequence(const char *s, size_t length)
   3.523 +{
   3.524 +  CharacterStreamHasher hasher;
   3.525 +  hasher.add(s, length);
   3.526 +  return hasher.result();
   3.527 +}
   3.528 +
   3.529 +static inline uint32_t
   3.530 +FastHashCharSequence(const char *s, size_t length)
   3.531 +{
   3.532 +  uint32_t hash = 0;
   3.533 +  for (size_t i = 0; i < length; i++)
   3.534 +    hash = s[i] + (hash << 6) + (hash << 16) - hash;
   3.535 +  return hash;
   3.536 +}
   3.537 +
   3.538 +// From http://burtleburtle.net/bob/hash/integer.html
   3.539 +static inline uint32_t
   3.540 +HashInt32(int32_t a)
   3.541 +{
   3.542 +  a = (a ^ 61) ^ (a >> 16);
   3.543 +  a = a + (a << 3);
   3.544 +  a = a ^ (a >> 4);
   3.545 +  a = a * 0x27d4eb2d;
   3.546 +  a = a ^ (a >> 15);
   3.547 +  return a;
   3.548 +}
   3.549 +
   3.550 +// From http://www.cris.com/~Ttwang/tech/inthash.htm
   3.551 +static inline uint32_t
   3.552 +HashInt64(int64_t key)
   3.553 +{
   3.554 +  key = (~key) + (key << 18); // key = (key << 18) - key - 1;
   3.555 +  key = key ^ (uint64(key) >> 31);
   3.556 +  key = key * 21; // key = (key + (key << 2)) + (key << 4);
   3.557 +  key = key ^ (uint64(key) >> 11);
   3.558 +  key = key + (key << 6);
   3.559 +  key = key ^ (uint64(key) >> 22);
   3.560 +  return uint32(key);
   3.561 +}
   3.562 +
   3.563 +template <size_t Size>
   3.564 +static inline uint32_t
   3.565 +HashInteger(uintptr_t value);
   3.566 +
   3.567 +template <>
   3.568 +inline uint32_t
   3.569 +HashInteger<4>(uintptr_t value)
   3.570 +{
   3.571 +  return HashInt32(value);
   3.572 +}
   3.573 +
   3.574 +template <>
   3.575 +inline uint32_t
   3.576 +HashInteger<8>(uintptr_t value)
   3.577 +{
   3.578 +  return HashInt64(value);
   3.579 +}
   3.580 +
   3.581 +static inline uint32_t
   3.582 +HashPointer(void *ptr)
   3.583 +{
   3.584 +  return HashInteger<sizeof(ptr)>(reinterpret_cast<uintptr_t>(ptr));
   3.585 +}
   3.586 +
   3.587 +} // namespace ke
   3.588 +
   3.589 +#endif // _INCLUDE_KEIMA_HASHTABLE_H_

     4.1 --- a/public/amtl/am-inline-list.h	Sat Aug 24 00:12:21 2013 -0400
     4.2 +++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
     4.3 @@ -1,142 +0,0 @@
     4.4 -// vim: set sts=8 ts=2 sw=2 tw=99 et:
     4.5 -//
     4.6 -// Copyright (C) 2013, David Anderson and AlliedModders LLC
     4.7 -// All rights reserved.
     4.8 -// 
     4.9 -// Redistribution and use in source and binary forms, with or without
    4.10 -// modification, are permitted provided that the following conditions are met:
    4.11 -// 
    4.12 -//  * Redistributions of source code must retain the above copyright notice, this
    4.13 -//    list of conditions and the following disclaimer.
    4.14 -//  * Redistributions in binary form must reproduce the above copyright notice,
    4.15 -//    this list of conditions and the following disclaimer in the documentation
    4.16 -//    and/or other materials provided with the distribution.
    4.17 -//  * Neither the name of AlliedModders LLC nor the names of its contributors
    4.18 -//    may be used to endorse or promote products derived from this software
    4.19 -//    without specific prior written permission.
    4.20 -//
    4.21 -// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
    4.22 -// AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
    4.23 -// IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
    4.24 -// ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
    4.25 -// LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
    4.26 -// CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
    4.27 -// SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
    4.28 -// INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
    4.29 -// CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
    4.30 -// ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
    4.31 -// POSSIBILITY OF SUCH DAMAGE.
    4.32 -
    4.33 -#ifndef _include_amtl_inline_list_h_
    4.34 -#define _include_amtl_inline_list_h_
    4.35 -
    4.36 -#include <stddef.h>
    4.37 -
    4.38 -namespace ke {
    4.39 -
    4.40 -template <typename T> class InlineList;
    4.41 -
    4.42 -template <typename T>
    4.43 -class InlineListNode
    4.44 -{
    4.45 -  friend class InlineList<T>;
    4.46 -
    4.47 -  public:
    4.48 -  InlineListNode()
    4.49 -    : next_(NULL),
    4.50 -    prev_(NULL)
    4.51 -  {
    4.52 -  }
    4.53 -
    4.54 -  InlineListNode(InlineListNode *next, InlineListNode *prev)
    4.55 -    : next_(next),
    4.56 -    prev_(prev)
    4.57 -  {
    4.58 -  }
    4.59 -
    4.60 -  protected:
    4.61 -  InlineListNode *next_;
    4.62 -  InlineListNode *prev_;
    4.63 -};
    4.64 -
    4.65 -template <typename T>
    4.66 -class InlineList
    4.67 -{
    4.68 -  typedef InlineListNode<T> Node;
    4.69 -
    4.70 -  Node head_;
    4.71 -
    4.72 - public:
    4.73 -  InlineList()
    4.74 -    : head_(&head_, &head_)
    4.75 -  {
    4.76 -  }
    4.77 -
    4.78 - public:
    4.79 -  class iterator
    4.80 -  {
    4.81 -    friend class InlineList;
    4.82 -    Node *iter_;
    4.83 -
    4.84 -   public:
    4.85 -    iterator(Node *iter)
    4.86 -      : iter_(iter)
    4.87 -    {
    4.88 -    }
    4.89 -
    4.90 -    iterator & operator ++() {
    4.91 -      iter_ = iter_->next;
    4.92 -      return *iter_;
    4.93 -    }
    4.94 -    iterator operator ++(int) {
    4.95 -      iterator old(*this);
    4.96 -      iter_ = iter_->next_;
    4.97 -      return old;
    4.98 -    }
    4.99 -    T * operator *() {
   4.100 -      return static_cast<T *>(iter_);
   4.101 -    }
   4.102 -    T * operator ->() {
   4.103 -      return static_cast<T *>(iter_);
   4.104 -    }
   4.105 -    bool operator !=(const iterator &where) const {
   4.106 -      return iter_ != where.iter_;
   4.107 -    }
   4.108 -    bool operator ==(const iterator &where) const {
   4.109 -      return iter_ == where.iter_;
   4.110 -    }
   4.111 -    iterator prev() const {
   4.112 -      iterator p(iter_->prev_);
   4.113 -      return p;
   4.114 -    }
   4.115 -    iterator next() const {
   4.116 -      iterator p(iter_->next_);
   4.117 -      return p;
   4.118 -    }
   4.119 -  };
   4.120 -
   4.121 -  iterator begin() {
   4.122 -    return iterator(head_.next_);
   4.123 -  }
   4.124 -
   4.125 -  iterator end() {
   4.126 -    return iterator(&head_);
   4.127 -  }
   4.128 -
   4.129 -  void erase(Node *t) {
   4.130 -    t->prev_->next_ = t->next_;
   4.131 -    t->next_->prev_ = t->prev_;
   4.132 -  }
   4.133 -
   4.134 -  void insert(Node *t) {
   4.135 -    t->prev_ = head_.prev_;
   4.136 -    t->next_ = &head_;
   4.137 -    head_.prev_->next_ = t;
   4.138 -    head_.prev_ = t;
   4.139 -  }
   4.140 -};
   4.141 -
   4.142 -}
   4.143 -
   4.144 -#endif // _include_amtl_inline_list_h_
   4.145 -

     5.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     5.2 +++ b/public/amtl/am-inlinelist.h	Fri Aug 23 22:29:44 2013 -0700
     5.3 @@ -0,0 +1,142 @@
     5.4 +// vim: set sts=8 ts=2 sw=2 tw=99 et:
     5.5 +//
     5.6 +// Copyright (C) 2013, David Anderson and AlliedModders LLC
     5.7 +// All rights reserved.
     5.8 +// 
     5.9 +// Redistribution and use in source and binary forms, with or without
    5.10 +// modification, are permitted provided that the following conditions are met:
    5.11 +// 
    5.12 +//  * Redistributions of source code must retain the above copyright notice, this
    5.13 +//    list of conditions and the following disclaimer.
    5.14 +//  * Redistributions in binary form must reproduce the above copyright notice,
    5.15 +//    this list of conditions and the following disclaimer in the documentation
    5.16 +//    and/or other materials provided with the distribution.
    5.17 +//  * Neither the name of AlliedModders LLC nor the names of its contributors
    5.18 +//    may be used to endorse or promote products derived from this software
    5.19 +//    without specific prior written permission.
    5.20 +//
    5.21 +// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
    5.22 +// AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
    5.23 +// IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
    5.24 +// ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
    5.25 +// LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
    5.26 +// CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
    5.27 +// SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
    5.28 +// INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
    5.29 +// CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
    5.30 +// ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
    5.31 +// POSSIBILITY OF SUCH DAMAGE.
    5.32 +
    5.33 +#ifndef _include_amtl_inline_list_h_
    5.34 +#define _include_amtl_inline_list_h_
    5.35 +
    5.36 +#include <stddef.h>
    5.37 +
    5.38 +namespace ke {
    5.39 +
    5.40 +template <typename T> class InlineList;
    5.41 +
    5.42 +template <typename T>
    5.43 +class InlineListNode
    5.44 +{
    5.45 +  friend class InlineList<T>;
    5.46 +
    5.47 +  public:
    5.48 +  InlineListNode()
    5.49 +    : next_(NULL),
    5.50 +    prev_(NULL)
    5.51 +  {
    5.52 +  }
    5.53 +
    5.54 +  InlineListNode(InlineListNode *next, InlineListNode *prev)
    5.55 +    : next_(next),
    5.56 +    prev_(prev)
    5.57 +  {
    5.58 +  }
    5.59 +
    5.60 +  protected:
    5.61 +  InlineListNode *next_;
    5.62 +  InlineListNode *prev_;
    5.63 +};
    5.64 +
    5.65 +template <typename T>
    5.66 +class InlineList
    5.67 +{
    5.68 +  typedef InlineListNode<T> Node;
    5.69 +
    5.70 +  Node head_;
    5.71 +
    5.72 + public:
    5.73 +  InlineList()
    5.74 +    : head_(&head_, &head_)
    5.75 +  {
    5.76 +  }
    5.77 +
    5.78 + public:
    5.79 +  class iterator
    5.80 +  {
    5.81 +    friend class InlineList;
    5.82 +    Node *iter_;
    5.83 +
    5.84 +   public:
    5.85 +    iterator(Node *iter)
    5.86 +      : iter_(iter)
    5.87 +    {
    5.88 +    }
    5.89 +
    5.90 +    iterator & operator ++() {
    5.91 +      iter_ = iter_->next;
    5.92 +      return *iter_;
    5.93 +    }
    5.94 +    iterator operator ++(int) {
    5.95 +      iterator old(*this);
    5.96 +      iter_ = iter_->next_;
    5.97 +      return old;
    5.98 +    }
    5.99 +    T * operator *() {
   5.100 +      return static_cast<T *>(iter_);
   5.101 +    }
   5.102 +    T * operator ->() {
   5.103 +      return static_cast<T *>(iter_);
   5.104 +    }
   5.105 +    bool operator !=(const iterator &where) const {
   5.106 +      return iter_ != where.iter_;
   5.107 +    }
   5.108 +    bool operator ==(const iterator &where) const {
   5.109 +      return iter_ == where.iter_;
   5.110 +    }
   5.111 +    iterator prev() const {
   5.112 +      iterator p(iter_->prev_);
   5.113 +      return p;
   5.114 +    }
   5.115 +    iterator next() const {
   5.116 +      iterator p(iter_->next_);
   5.117 +      return p;
   5.118 +    }
   5.119 +  };
   5.120 +
   5.121 +  iterator begin() {
   5.122 +    return iterator(head_.next_);
   5.123 +  }
   5.124 +
   5.125 +  iterator end() {
   5.126 +    return iterator(&head_);
   5.127 +  }
   5.128 +
   5.129 +  void erase(Node *t) {
   5.130 +    t->prev_->next_ = t->next_;
   5.131 +    t->next_->prev_ = t->prev_;
   5.132 +  }
   5.133 +
   5.134 +  void insert(Node *t) {
   5.135 +    t->prev_ = head_.prev_;
   5.136 +    t->next_ = &head_;
   5.137 +    head_.prev_->next_ = t;
   5.138 +    head_.prev_ = t;
   5.139 +  }
   5.140 +};
   5.141 +
   5.142 +}
   5.143 +
   5.144 +#endif // _include_amtl_inline_list_h_
   5.145 +

     6.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     6.2 +++ b/public/amtl/am-linkedlist.h	Fri Aug 23 22:29:44 2013 -0700
     6.3 @@ -0,0 +1,290 @@
     6.4 +// vim: set sts=8 ts=2 sw=2 tw=99 et:
     6.5 +//
     6.6 +// Copyright (C) 2013, David Anderson and AlliedModders LLC
     6.7 +// All rights reserved.
     6.8 +// 
     6.9 +// Redistribution and use in source and binary forms, with or without
    6.10 +// modification, are permitted provided that the following conditions are met:
    6.11 +// 
    6.12 +//  * Redistributions of source code must retain the above copyright notice, this
    6.13 +//    list of conditions and the following disclaimer.
    6.14 +//  * Redistributions in binary form must reproduce the above copyright notice,
    6.15 +//    this list of conditions and the following disclaimer in the documentation
    6.16 +//    and/or other materials provided with the distribution.
    6.17 +//  * Neither the name of AlliedModders LLC nor the names of its contributors
    6.18 +//    may be used to endorse or promote products derived from this software
    6.19 +//    without specific prior written permission.
    6.20 +//
    6.21 +// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
    6.22 +// AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
    6.23 +// IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
    6.24 +// ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
    6.25 +// LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
    6.26 +// CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
    6.27 +// SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
    6.28 +// INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
    6.29 +// CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
    6.30 +// ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
    6.31 +// POSSIBILITY OF SUCH DAMAGE.
    6.32 +
    6.33 +#ifndef _include_amtl_linkedlist_h_
    6.34 +#define _include_amtl_linkedlist_h_
    6.35 +
    6.36 +#include <new>
    6.37 +#include <stdlib.h>
    6.38 +#include <am-allocator-policies.h>
    6.39 +#include <am-utility.h>
    6.40 +
    6.41 +namespace ke {
    6.42 +
    6.43 +// LinkedList, analagous to std::list or SourceHook::List. Since it performs a
    6.44 +// malloc() and free() on every contained node, it should be avoided unless
    6.45 +// absolutely necessary, or for when allocation performance is not a factor. It
    6.46 +// is provided here to safely port old AlliedModders code to AMTL.
    6.47 +//
    6.48 +// In order to use a circular chain, LinkedList's allocation size includes
    6.49 +// exactly one T. If T is very large, LinkedList should be allocated on the
    6.50 +// heap, to avoid using the stack.
    6.51 +template <class T, class AllocPolicy = SystemAllocatorPolicy>
    6.52 +class LinkedList : public AllocPolicy
    6.53 +{
    6.54 + public:
    6.55 +  friend class iterator;
    6.56 +
    6.57 +  class Node
    6.58 +  {
    6.59 +   public:
    6.60 +    Node(const T &o)
    6.61 +     : obj(o)
    6.62 +    {
    6.63 +    }
    6.64 +
    6.65 +    T obj;
    6.66 +    Node *next;
    6.67 +    Node *prev;
    6.68 +  };
    6.69 +
    6.70 +public:
    6.71 +  LinkedList(AllocPolicy = AllocPolicy())
    6.72 +   : length_(0)
    6.73 +  {
    6.74 +  }
    6.75 +  ~LinkedList() {
    6.76 +    clear();
    6.77 +  }
    6.78 +
    6.79 +  bool append(const T &obj) {
    6.80 +    Node *node = allocNode(obj);
    6.81 +    if (!node)
    6.82 +      return false;
    6.83 +
    6.84 +    node->prev = head()->prev;
    6.85 +    node->next = head();
    6.86 +    head()->prev->next = node;
    6.87 +    head()->prev = node;
    6.88 +
    6.89 +    length_++;
    6.90 +  }
    6.91 +
    6.92 +  bool prepend(const T &obj) {
    6.93 +    return insert(begin(), obj);
    6.94 +  }
    6.95 +
    6.96 +  size_t size() const {
    6.97 +    return length_;
    6.98 +  }
    6.99 +
   6.100 +  void clear() {
   6.101 +    Node *node = head()->next;
   6.102 +    Node *temp;
   6.103 +    head()->next = head();
   6.104 +    head()->prev = head();
   6.105 +
   6.106 +    // Iterate through the nodes until we find the sentinel again.
   6.107 +    while (node != head()) {
   6.108 +      temp = node->next;
   6.109 +      freeNode(node);
   6.110 +      node = temp;
   6.111 +    }
   6.112 +    length_ = 0;
   6.113 +  }
   6.114 +
   6.115 +  bool empty() const {
   6.116 +    return (length_ == 0);
   6.117 +  }
   6.118 +
   6.119 +  T &front() {
   6.120 +    assert(!empty());
   6.121 +    return head()->next->obj;
   6.122 +  }
   6.123 +  T &back() {
   6.124 +    assert(!empty());
   6.125 +    return head()->prev->obj;
   6.126 +  }
   6.127 +
   6.128 + private:
   6.129 +  const Node *head() const {
   6.130 +    return sentinel_.address();
   6.131 +  }
   6.132 +  Node *head() {
   6.133 +    return sentinel_.address();
   6.134 +  }
   6.135 +
   6.136 +  Node *allocNode(const T &obj) {
   6.137 +    Node *node = (Node *)this->malloc(sizeof(Node));
   6.138 +    if (!node)
   6.139 +      return NULL;
   6.140 +    new (node) Node(obj);
   6.141 +    return node;
   6.142 +  }
   6.143 +
   6.144 +  void freeNode(Node *node) {
   6.145 +    node->obj.~T();
   6.146 +    this->free(node);
   6.147 +  }
   6.148 +
   6.149 + private:
   6.150 +  StorageBuffer<Node> sentinel_;
   6.151 +  size_t length_;
   6.152 +
   6.153 + public:
   6.154 +  class iterator
   6.155 +  {
   6.156 +    friend class LinkedList;
   6.157 +
   6.158 +   public:
   6.159 +    iterator()
   6.160 +     : this_(NULL)
   6.161 +    {
   6.162 +    }
   6.163 +    iterator(const LinkedList &src)
   6.164 +     : this_(src.head())
   6.165 +    {
   6.166 +    }
   6.167 +    iterator(Node *n)
   6.168 +     : this_(n)
   6.169 +    {
   6.170 +    }
   6.171 +    iterator(const iterator &where)
   6.172 +     : this_(where.this_)
   6.173 +    {
   6.174 +    }
   6.175 +
   6.176 +    iterator &operator --() {
   6.177 +      if (this_)
   6.178 +        this_ = this_->prev;
   6.179 +      return *this;
   6.180 +    }
   6.181 +    iterator operator --(int) {
   6.182 +      iterator old(*this);
   6.183 +      if (this_)
   6.184 +        this_ = this_->prev;
   6.185 +      return old;
   6.186 +    }  
   6.187 +    iterator &operator ++() {
   6.188 +      if (this_)
   6.189 +        this_ = this_->next;
   6.190 +      return *this;
   6.191 +    }
   6.192 +    iterator operator ++(int) {
   6.193 +      iterator old(*this);
   6.194 +      if (this_)
   6.195 +        this_ = this_->next;
   6.196 +      return old;
   6.197 +    }
   6.198 +    
   6.199 +    const T &operator * () const {
   6.200 +      return this_->obj;
   6.201 +    }
   6.202 +    T &operator * () {
   6.203 +      return this_->obj;
   6.204 +    }
   6.205 +    T *operator ->() {
   6.206 +      return &this_->obj;
   6.207 +    }
   6.208 +    const T *operator ->() const {
   6.209 +      return &(this_->obj);
   6.210 +    }
   6.211 +    
   6.212 +    bool operator !=(const iterator &where) const {
   6.213 +      return (this_ != where.this_);
   6.214 +    }
   6.215 +    bool operator ==(const iterator &where) const {
   6.216 +      return (this_ == where.this_);
   6.217 +    }
   6.218 +
   6.219 +    operator bool() {
   6.220 +      return !!this_;
   6.221 +    }
   6.222 +
   6.223 +   private:
   6.224 +    Node *this_;
   6.225 +  };
   6.226 +
   6.227 + public:
   6.228 +  iterator begin() const {
   6.229 +    return iterator(head()->next);
   6.230 +  }
   6.231 +  iterator end() const {
   6.232 +    return iterator(head());
   6.233 +  }
   6.234 +  iterator erase(iterator &where) {
   6.235 +    Node *pNode = where.this_;
   6.236 +    iterator iter(where);
   6.237 +    iter++;
   6.238 +
   6.239 +    pNode->prev->next = pNode->next;
   6.240 +    pNode->next->prev = pNode->prev;
   6.241 +
   6.242 +    freeNode(pNode);
   6.243 +    length_--;
   6.244 +
   6.245 +    return iter;
   6.246 +  }
   6.247 +  iterator insert(iterator where, const T &obj) {
   6.248 +    // Insert obj right before where
   6.249 +    Node *node = allocNode(obj);
   6.250 +    if (!node)
   6.251 +      return where;
   6.252 +
   6.253 +    Node *pWhereNode = where.this_;
   6.254 +    
   6.255 +    pWhereNode->prev->next = node;
   6.256 +    node->prev = pWhereNode->prev;
   6.257 +    pWhereNode->prev = node;
   6.258 +    node->next = pWhereNode;
   6.259 +
   6.260 +    length_++;
   6.261 +    return iterator(node);
   6.262 +  }
   6.263 +
   6.264 + public:
   6.265 +  void remove(const T &obj) {
   6.266 +    for (iterator b = begin(); b != end(); b++) {
   6.267 +      if (*b == obj) {
   6.268 +        erase(b);
   6.269 +        break;
   6.270 +      }
   6.271 +    }
   6.272 +  }
   6.273 +
   6.274 +  template <typename U>
   6.275 +  iterator find(const U &equ) const {
   6.276 +    for (iterator iter = begin(); iter != end(); iter++) {
   6.277 +      if (*iter == equ)
   6.278 +        return iter;
   6.279 +    }
   6.280 +    return end();
   6.281 +  }
   6.282 +
   6.283 +
   6.284 + private:
   6.285 +  // These are disallowed because they basically violate the failure handling
   6.286 +  // model for AllocPolicies and are also likely to have abysmal performance.
   6.287 +  LinkedList &operator =(const LinkedList<T> &other) KE_DELETE;
   6.288 +  LinkedList(const LinkedList<T> &other) KE_DELETE;
   6.289 +};
   6.290 +
   6.291 +} // namespace ke
   6.292 +
   6.293 +#endif //_INCLUDE_CSDM_LIST_H

     7.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     7.2 +++ b/public/amtl/am-string.h	Fri Aug 23 22:29:44 2013 -0700
     7.3 @@ -0,0 +1,101 @@
     7.4 +// vim: set sts=8 ts=2 sw=2 tw=99 et:
     7.5 +//
     7.6 +// Copyright (C) 2013, David Anderson and AlliedModders LLC
     7.7 +// All rights reserved.
     7.8 +// 
     7.9 +// Redistribution and use in source and binary forms, with or without
    7.10 +// modification, are permitted provided that the following conditions are met:
    7.11 +// 
    7.12 +//  * Redistributions of source code must retain the above copyright notice, this
    7.13 +//    list of conditions and the following disclaimer.
    7.14 +//  * Redistributions in binary form must reproduce the above copyright notice,
    7.15 +//    this list of conditions and the following disclaimer in the documentation
    7.16 +//    and/or other materials provided with the distribution.
    7.17 +//  * Neither the name of AlliedModders LLC nor the names of its contributors
    7.18 +//    may be used to endorse or promote products derived from this software
    7.19 +//    without specific prior written permission.
    7.20 +//
    7.21 +// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
    7.22 +// AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
    7.23 +// IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
    7.24 +// ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
    7.25 +// LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
    7.26 +// CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
    7.27 +// SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
    7.28 +// INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
    7.29 +// CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
    7.30 +// ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
    7.31 +// POSSIBILITY OF SUCH DAMAGE.
    7.32 +
    7.33 +#ifndef _include_amtl_string_h_
    7.34 +#define _include_amtl_string_h_
    7.35 +
    7.36 +#include <stdlib.h>
    7.37 +#include <string.h>
    7.38 +#include <am-utility.h>
    7.39 +
    7.40 +namespace ke {
    7.41 +
    7.42 +// ASCII string.
    7.43 +class AString
    7.44 +{
    7.45 + public:
    7.46 +  AString()
    7.47 +   : length_(0)
    7.48 +  {
    7.49 +  }
    7.50 +  explicit AString(const char *str) {
    7.51 +    set(str, strlen(str));
    7.52 +  }
    7.53 +  AString(const char *str, size_t length) {
    7.54 +    set(str, length);
    7.55 +  }
    7.56 +  AString(const AString &other) {
    7.57 +    set(other.chars_, other.length_);
    7.58 +  }
    7.59 +
    7.60 +  AString &operator =(const char *str) {
    7.61 +    set(str, strlen(str));
    7.62 +    return *this;
    7.63 +  }
    7.64 +  AString &operator =(const AString &other) {
    7.65 +    set(other.chars_, other.length_);
    7.66 +    return *this;
    7.67 +  }
    7.68 +
    7.69 +  bool operator ==(const AString &other) const {
    7.70 +    return other.length() == length() &&
    7.71 +           memcmp(other.chars(), chars(), length()) == 0;
    7.72 +  }
    7.73 +
    7.74 +  char operator [](size_t index) const {
    7.75 +    assert(index < length());
    7.76 +    return chars()[index];
    7.77 +  }
    7.78 +
    7.79 +  size_t length() const {
    7.80 +    return length_;
    7.81 +  }
    7.82 +
    7.83 +  const char *chars() const {
    7.84 +    if (!chars_)
    7.85 +      return "";
    7.86 +    return chars_;
    7.87 +  }
    7.88 +
    7.89 + private:
    7.90 +  void set(const char *str, size_t length) {
    7.91 +    chars_ = new char[length + 1];
    7.92 +    length_ = length;
    7.93 +    memcpy(chars_, str, length);
    7.94 +    chars_[length] = '\0';
    7.95 +  }
    7.96 +
    7.97 + private:
    7.98 +  AutoArray<char> chars_;
    7.99 +  size_t length_;
   7.100 +};
   7.101 +
   7.102 +}
   7.103 +
   7.104 +#endif // _include_amtl_string_h_

     8.1 --- a/public/amtl/am-thread-posix.h	Sat Aug 24 00:12:21 2013 -0400
     8.2 +++ b/public/amtl/am-thread-posix.h	Fri Aug 23 22:29:44 2013 -0700
     8.3 @@ -57,15 +57,15 @@
     8.4      pthread_mutex_destroy(&mutex_);
     8.5    }
     8.6  
     8.7 -  bool DoTryLock() {
     8.8 +  bool DoTryLock() KE_OVERRIDE {
     8.9      return pthread_mutex_trylock(&mutex_) == 0;
    8.10    }
    8.11  
    8.12 -  void DoLock() {
    8.13 +  void DoLock() KE_OVERRIDE {
    8.14      pthread_mutex_lock(&mutex_);
    8.15    }
    8.16  
    8.17 -  void DoUnlock() {
    8.18 +  void DoUnlock() KE_OVERRIDE {
    8.19      pthread_mutex_unlock(&mutex_);
    8.20    }
    8.21    
    8.22 @@ -92,13 +92,13 @@
    8.23      pthread_cond_destroy(&cv_);
    8.24    }
    8.25  
    8.26 -  bool DoTryLock() {
    8.27 +  bool DoTryLock() KE_OVERRIDE {
    8.28      return mutex_.DoTryLock();
    8.29    }
    8.30 -  void DoLock() {
    8.31 +  void DoLock() KE_OVERRIDE {
    8.32      mutex_.DoLock();
    8.33    }
    8.34 -  void DoUnlock() {
    8.35 +  void DoUnlock() KE_OVERRIDE {
    8.36      mutex_.DoUnlock();
    8.37    }
    8.38  

     9.1 --- a/public/amtl/am-thread-windows.h	Sat Aug 24 00:12:21 2013 -0400
     9.2 +++ b/public/amtl/am-thread-windows.h	Fri Aug 23 22:29:44 2013 -0700
     9.3 @@ -44,14 +44,14 @@
     9.4      DeleteCriticalSection(&cs_);
     9.5    }
     9.6  
     9.7 -  bool DoTryLock() {
     9.8 +  bool DoTryLock() KE_OVERRIDE {
     9.9      return !!TryEnterCriticalSection(&cs_);
    9.10    }
    9.11 -  void DoLock() {
    9.12 +  void DoLock() KE_OVERRIDE {
    9.13      EnterCriticalSection(&cs_);
    9.14    }
    9.15  
    9.16 -  void DoUnlock() {
    9.17 +  void DoUnlock() KE_OVERRIDE {
    9.18      LeaveCriticalSection(&cs_);
    9.19    }
    9.20  
    9.21 @@ -72,13 +72,13 @@
    9.22      CloseHandle(event_);
    9.23    }
    9.24  
    9.25 -  bool DoTryLock() {
    9.26 +  bool DoTryLock() KE_OVERRIDE {
    9.27      return cs_.DoTryLock();
    9.28    }
    9.29 -  void DoLock() {
    9.30 +  void DoLock() KE_OVERRIDE {
    9.31      cs_.DoLock();
    9.32    }
    9.33 -  void DoUnlock() {
    9.34 +  void DoUnlock() KE_OVERRIDE {
    9.35      cs_.DoUnlock();
    9.36    }
    9.37  

    10.1 --- a/public/amtl/am-utility.h	Sat Aug 24 00:12:21 2013 -0400
    10.2 +++ b/public/amtl/am-utility.h	Fri Aug 23 22:29:44 2013 -0700
    10.3 @@ -108,80 +108,49 @@
    10.4      }
    10.5  };
    10.6  
    10.7 -// Bob Jenkin's one-at-a-time hash function[1].
    10.8 -//
    10.9 -// [1] http://burtleburtle.net/bob/hash/doobs.html
   10.10 -class CharacterStreamHasher
   10.11 +// Wrapper that automatically deletes its contents. The pointer can be taken
   10.12 +// to avoid destruction.
   10.13 +template <typename T>
   10.14 +class AutoArray
   10.15  {
   10.16 -    uint32 hash;
   10.17 +    T *t_;
   10.18  
   10.19    public:
   10.20 -    CharacterStreamHasher()
   10.21 -      : hash(0)
   10.22 -    { }
   10.23 -
   10.24 -    void add(char c) {
   10.25 -        hash += c;
   10.26 -        hash += (hash << 10);
   10.27 -        hash ^= (hash >> 6);
   10.28 +    AutoArray()
   10.29 +      : t_(NULL)
   10.30 +    {
   10.31 +    }
   10.32 +    explicit AutoArray(T *t)
   10.33 +      : t_(t)
   10.34 +    {
   10.35 +    }
   10.36 +    ~AutoArray() {
   10.37 +        delete [] t_;
   10.38 +    }
   10.39 +    T *take() {
   10.40 +        return ReturnAndVoid(t_);
   10.41      }
   10.42 -
   10.43 -    void add(const char *s, size_t length) {
   10.44 -        for (size_t i = 0; i < length; i++)
   10.45 -            add(s[i]);
   10.46 +    T *operator *() const {
   10.47 +        return t_;
   10.48 +    }
   10.49 +    T &operator [](size_t index) {
   10.50 +      return t_[index];
   10.51 +    }
   10.52 +    const T &operator [](size_t index) const {
   10.53 +      return t_[index];
   10.54      }
   10.55 -
   10.56 -    uint32 result() {
   10.57 -        hash += (hash << 3);
   10.58 -        hash ^= (hash >> 11);
   10.59 -        hash += (hash << 15);
   10.60 -        return hash;
   10.61 +    operator T *() const {
   10.62 +        return t_;
   10.63 +    }
   10.64 +    void operator =(T *t) {
   10.65 +        delete [] t_;
   10.66 +        t_ = t;
   10.67 +    }
   10.68 +    bool operator !() const {
   10.69 +        return !t_;
   10.70      }
   10.71  };
   10.72  
   10.73 -static inline uint32
   10.74 -HashCharSequence(const char *s, size_t length)
   10.75 -{
   10.76 -    CharacterStreamHasher hasher;
   10.77 -    hasher.add(s, length);
   10.78 -    return hasher.result();
   10.79 -}
   10.80 -
   10.81 -// From http://burtleburtle.net/bob/hash/integer.html
   10.82 -static inline uint32
   10.83 -HashInt32(int32 a)
   10.84 -{
   10.85 -    a = (a ^ 61) ^ (a >> 16);
   10.86 -    a = a + (a << 3);
   10.87 -    a = a ^ (a >> 4);
   10.88 -    a = a * 0x27d4eb2d;
   10.89 -    a = a ^ (a >> 15);
   10.90 -    return a;
   10.91 -}
   10.92 -
   10.93 -// From http://www.cris.com/~Ttwang/tech/inthash.htm
   10.94 -static inline uint32
   10.95 -HashInt64(int64 key)
   10.96 -{
   10.97 -  key = (~key) + (key << 18); // key = (key << 18) - key - 1;
   10.98 -  key = key ^ (uint64(key) >> 31);
   10.99 -  key = key * 21; // key = (key + (key << 2)) + (key << 4);
  10.100 -  key = key ^ (uint64(key) >> 11);
  10.101 -  key = key + (key << 6);
  10.102 -  key = key ^ (uint64(key) >> 22);
  10.103 -  return uint32(key);
  10.104 -}
  10.105 -
  10.106 -static inline uint32
  10.107 -HashPointer(void *p)
  10.108 -{
  10.109 -#if defined(KE_32BIT)
  10.110 -    return HashInt32(reinterpret_cast<int32>(p));
  10.111 -#elif defined(KE_64BIT)
  10.112 -    return HashInt64(reinterpret_cast<int64>(p));
  10.113 -#endif
  10.114 -}
  10.115 -
  10.116  static inline size_t
  10.117  Log2(size_t number)
  10.118  {
  10.119 @@ -317,6 +286,36 @@
  10.120      return t1 > t2 ? t1 : t2;
  10.121  }
  10.122  
  10.123 +template <typename T>
  10.124 +class StorageBuffer
  10.125 +{
  10.126 + public:
  10.127 +  T *address() {
  10.128 +    return reinterpret_cast<T *>(buffer_);
  10.129 +  }
  10.130 +  const T *address() const {
  10.131 +    return reinterpret_cast<const T *>(buffer_);
  10.132 +  }
  10.133 +
  10.134 + private:
  10.135 +  union {
  10.136 +    char buffer_[sizeof(T)];
  10.137 +    uint64_t aligned_;
  10.138 +  };
  10.139 +};
  10.140 +
  10.141 +#if __cplusplus >= 201103L
  10.142 +# define KE_CXX11
  10.143 +#endif
  10.144 +
  10.145 +#if defined(KE_CXX11)
  10.146 +# define KE_DELETE delete
  10.147 +# define KE_OVERRIDE override
  10.148 +#else
  10.149 +# define KE_DELETE
  10.150 +# define KE_OVERRIDE
  10.151 +#endif
  10.152 +
  10.153  #if defined(_MSC_VER)
  10.154  # define KE_SIZET_FMT           "%Iu"
  10.155  #elif defined(__GNUC__)

    11.1 --- a/public/amtl/am-vector.h	Sat Aug 24 00:12:21 2013 -0400
    11.2 +++ b/public/amtl/am-vector.h	Fri Aug 23 22:29:44 2013 -0700
    11.3 @@ -48,8 +48,7 @@
    11.4    {
    11.5    }
    11.6  
    11.7 -  ~Vector()
    11.8 -  {
    11.9 +  ~Vector() {
   11.10      zap();
   11.11    }
   11.12  
   11.13 @@ -61,7 +60,7 @@
   11.14      other.reset();
   11.15    }
   11.16  
   11.17 -  bool append(const T& item) {
   11.18 +  bool append(const T &item) {
   11.19      if (!growIfNeeded(1))
   11.20        return false;
   11.21      new (&data_[nitems_]) T(item);
   11.22 @@ -125,6 +124,12 @@
   11.23    }
   11.24  
   11.25   private:
   11.26 +  // These are disallowed because they basically violate the failure handling
   11.27 +  // model for AllocPolicies and are also likely to have abysmal performance.
   11.28 +  Vector(const Vector<T> &other) KE_DELETE;
   11.29 +  Vector &operator =(const Vector<T> &other) KE_DELETE;
   11.30 +
   11.31 + private:
   11.32    void zap() {
   11.33      for (size_t i = 0; i < nitems_; i++)
   11.34        data_[i].~T();
   11.35 @@ -144,16 +149,17 @@
   11.36      }
   11.37      if (nitems_ + needed < maxsize_)
   11.38        return true;
   11.39 -    if (maxsize_ == 0)
   11.40 -      maxsize_ = 8;
   11.41 -    while (nitems_ + needed > maxsize_) {
   11.42 -      if (!IsUintPtrMultiplySafe(maxsize_, 2)) {
   11.43 +
   11.44 +    size_t new_maxsize = maxsize_ ? maxsize_ : 8;
   11.45 +    while (nitems_ + needed > new_maxsize) {
   11.46 +      if (!IsUintPtrMultiplySafe(new_maxsize, 2)) {
   11.47          this->reportAllocationOverflow();
   11.48          return false;
   11.49        }
   11.50 -      maxsize_ *= 2;
   11.51 +      new_maxsize *= 2;
   11.52      }
   11.53 -    T* newdata = (T*)this->malloc(sizeof(T) * maxsize_);
   11.54 +
   11.55 +    T* newdata = (T*)this->malloc(sizeof(T) * new_maxsize);
   11.56      if (newdata == NULL)
   11.57        return false;
   11.58      for (size_t i = 0; i < nitems_; i++) {
   11.59 @@ -161,7 +167,9 @@
   11.60        data_[i].~T();
   11.61      }
   11.62      this->free(data_);
   11.63 +
   11.64      data_ = newdata;
   11.65 +    maxsize_ = new_maxsize;
   11.66      return true;
   11.67    }
   11.68  

    12.1 --- a/sourcepawn/jit/BaseRuntime.h	Sat Aug 24 00:12:21 2013 -0400
    12.2 +++ b/sourcepawn/jit/BaseRuntime.h	Fri Aug 23 22:29:44 2013 -0700
    12.3 @@ -4,7 +4,7 @@
    12.4  
    12.5  #include <sp_vm_api.h>
    12.6  #include <am-vector.h>
    12.7 -#include <am-inline-list.h>
    12.8 +#include <am-inlinelist.h>
    12.9  #include "jit_shared.h"
   12.10  #include "sp_vm_function.h"
   12.11