Sync from sourcemod.
1 // vim: set sts=8 ts=2 sw=2 tw=99 et:
3 // Copyright (C) 2013, David Anderson and AlliedModders LLC
4 // All rights reserved.
6 // Redistribution and use in source and binary forms, with or without
7 // modification, are permitted provided that the following conditions are met:
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.
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.
30 #ifndef _include_amtl_hashmap_h_
31 #define _include_amtl_hashmap_h_
33 #include <am-hashtable.h>
37 // Template parameters:
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);
45 // All types that match a given key, must compute the same hash.
47 // Note that like HashTable, a HashMap is not usable until init() has been called.
51 typename AllocPolicy = SystemAllocatorPolicy>
52 class HashMap : public AllocPolicy
63 Entry(Moveable<Entry> other)
64 : key(Moveable<K>(other->key)),
65 value(Moveable<V>(other->value))
69 Entry(const K &aKey, const V &aValue)
73 Entry(const K &aKey, Moveable<V> aValue)
77 Entry(Moveable<K> aKey, const V &aValue)
81 Entry(Moveable<K> aKey, Moveable<V> aValue)
89 typedef Entry Payload;
91 template <typename Lookup>
92 static uint32_t hash(const Lookup &key) {
93 return HashPolicy::hash(key);
96 template <typename Lookup>
97 static bool matches(const Lookup &key, const Payload &payload) {
98 return HashPolicy::matches(key, payload.key);
102 typedef HashTable<Policy, AllocPolicy> Internal;
105 HashMap(AllocPolicy ap = AllocPolicy())
110 // capacity must be a power of two.
111 bool init(size_t capacity = 16) {
112 return table_.init(capacity);
115 typedef typename Internal::Result Result;
116 typedef typename Internal::Insert Insert;
117 typedef typename Internal::iterator iterator;
119 template <typename Lookup>
120 Result find(const Lookup &key) {
121 return table_.find(key);
124 template <typename Lookup>
125 Insert findForAdd(const Lookup &key) {
126 return table_.findForAdd(key);
129 template <typename Lookup>
130 void removeIfExists(const Lookup &key) {
131 return table_.remove(key);
134 void remove(Result &r) {
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));
143 bool add(Insert &i, Moveable<K> key, const V &value) {
144 return table_.add(i, Entry(key, value));
146 bool add(Insert &i, const K &key, Moveable<V> value) {
147 return table_.add(i, Entry(key, value));
149 bool add(Insert &i, Moveable<K> key, Moveable<V> value) {
150 return table_.add(i, Entry(key, value));
152 bool add(Insert &i, Moveable<K> key) {
153 return table_.add(i, Entry(key, V()));
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);
164 return iterator(&table_);
171 size_t elements() const {
172 return table_.elements();
175 size_t estimateMemoryUse() const {
176 return table_.estimateMemoryUse();
183 template <typename T>
186 static inline uint32_t hash(T *p) {
187 return HashPointer(p);
189 static inline bool matches(T *p1, T *p2) {
196 #endif // _include_amtl_hashmap_h_