include/am-hashmap.h
author David Anderson <dvander@alliedmods.net>
Thu Aug 29 23:51:30 2013 -0700 (2013-08-29)
changeset 16 c513ef40773e
parent 14 4ae6d413d3be
permissions -rw-r--r--
Sync from sourcemod.
     1 // vim: set sts=8 ts=2 sw=2 tw=99 et:
     2 //
     3 // Copyright (C) 2013, David Anderson and AlliedModders LLC
     4 // All rights reserved.
     5 // 
     6 // Redistribution and use in source and binary forms, with or without
     7 // modification, are permitted provided that the following conditions are met:
     8 // 
     9 //  * Redistributions of source code must retain the above copyright notice, this
    10 //  list of conditions and the following disclaimer.
    11 //  * Redistributions in binary form must reproduce the above copyright notice,
    12 //  this list of conditions and the following disclaimer in the documentation
    13 //  and/or other materials provided with the distribution.
    14 //  * Neither the name of AlliedModders LLC nor the names of its contributors
    15 //  may be used to endorse or promote products derived from this software
    16 //  without specific prior written permission.
    17 //
    18 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
    19 // AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
    20 // IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
    21 // ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
    22 // LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
    23 // CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
    24 // SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
    25 // INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
    26 // CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
    27 // ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
    28 // POSSIBILITY OF SUCH DAMAGE.
    29 
    30 #ifndef _include_amtl_hashmap_h_
    31 #define _include_amtl_hashmap_h_
    32 
    33 #include <am-hashtable.h>
    34 
    35 namespace ke {
    36 
    37 // Template parameters:
    38 //
    39 // K - Key type.
    40 // V - Value type.
    41 // HashPolicy - A struct with a hash and comparator function for each lookup type:
    42 //     static uint32_t hash(const Type &value);
    43 //     static bool matches(const Type &value, const K &key);
    44 //
    45 // All types that match a given key, must compute the same hash.
    46 //
    47 // Note that like HashTable, a HashMap is not usable until init() has been called.
    48 template <typename K,
    49           typename V,
    50           typename HashPolicy,
    51           typename AllocPolicy = SystemAllocatorPolicy>
    52 class HashMap : public AllocPolicy
    53 {
    54  private:
    55   struct Entry
    56   {
    57     K key;
    58     V value;
    59 
    60     Entry()
    61     {
    62     }
    63     Entry(Moveable<Entry> other)
    64       : key(Moveable<K>(other->key)),
    65         value(Moveable<V>(other->value))
    66     {
    67     }
    68 
    69     Entry(const K &aKey, const V &aValue)
    70      : key(aKey),
    71        value(aValue)
    72     { }
    73     Entry(const K &aKey, Moveable<V> aValue)
    74      : key(aKey),
    75        value(aValue)
    76     { }
    77     Entry(Moveable<K> aKey, const V &aValue)
    78      : key(aKey),
    79        value(aValue)
    80     { }
    81     Entry(Moveable<K> aKey, Moveable<V> aValue)
    82      : key(aKey),
    83        value(aValue)
    84     { }
    85   };
    86 
    87   struct Policy
    88   {
    89     typedef Entry Payload;
    90 
    91     template <typename Lookup>
    92     static uint32_t hash(const Lookup &key) {
    93       return HashPolicy::hash(key);
    94     }
    95 
    96     template <typename Lookup>
    97     static bool matches(const Lookup &key, const Payload &payload) {
    98       return HashPolicy::matches(key, payload.key);
    99     }
   100   };
   101 
   102   typedef HashTable<Policy, AllocPolicy> Internal;
   103 
   104  public:
   105   HashMap(AllocPolicy ap = AllocPolicy())
   106     : table_(ap)
   107   {
   108   }
   109 
   110   // capacity must be a power of two.
   111   bool init(size_t capacity = 16) {
   112     return table_.init(capacity);
   113   }
   114 
   115   typedef typename Internal::Result Result;
   116   typedef typename Internal::Insert Insert;
   117   typedef typename Internal::iterator iterator;
   118 
   119   template <typename Lookup>
   120   Result find(const Lookup &key) {
   121     return table_.find(key);
   122   }
   123 
   124   template <typename Lookup>
   125   Insert findForAdd(const Lookup &key) {
   126     return table_.findForAdd(key);
   127   }
   128 
   129   template <typename Lookup>
   130   void removeIfExists(const Lookup &key) {
   131     return table_.remove(key);
   132   }
   133 
   134   void remove(Result &r) {
   135     table_.remove(r);
   136   }
   137 
   138   // The map must not have been mutated in between findForAdd() and add().
   139   // The Insert object is still valid after add() returns, however.
   140   bool add(Insert &i, const K &key, const V &value) {
   141     return table_.add(i, Entry(key, value));
   142   }
   143   bool add(Insert &i, Moveable<K> key, const V &value) {
   144     return table_.add(i, Entry(key, value));
   145   }
   146   bool add(Insert &i, const K &key, Moveable<V> value) {
   147     return table_.add(i, Entry(key, value));
   148   }
   149   bool add(Insert &i, Moveable<K> key, Moveable<V> value) {
   150     return table_.add(i, Entry(key, value));
   151   }
   152   bool add(Insert &i, Moveable<K> key) {
   153     return table_.add(i, Entry(key, V()));
   154   }
   155 
   156   // This can be used to avoid compiler constructed temporaries, since AMTL
   157   // does not yet support move semantics. If you use this, the key and value
   158   // must be set after.
   159   bool add(Insert &i) {
   160     return table_.add(i);
   161   }
   162 
   163   iterator iter() {
   164     return iterator(&table_);
   165   }
   166 
   167   void clear() {
   168     table_.clear();
   169   }
   170 
   171   size_t elements() const {
   172     return table_.elements();
   173   }
   174 
   175   size_t estimateMemoryUse() const {
   176     return table_.estimateMemoryUse();
   177   }
   178 
   179  private:
   180   Internal table_;
   181 };
   182 
   183 template <typename T>
   184 struct PointerPolicy
   185 {
   186   static inline uint32_t hash(T *p) {
   187     return HashPointer(p);
   188   }
   189   static inline bool matches(T *p1, T *p2) {
   190     return p1 == p2;
   191   }
   192 };
   193 
   194 }
   195 
   196 #endif // _include_amtl_hashmap_h_