1// tMap.h 
2// 
3// A map class (dictionary) that keeps track of keys and associated values, both of which may be any type. The 
4// requirements are: The key type must be copyable, comparable, and convertable to a uint32. The value type must be 
5// copyable. tMap is implemented as a hash-table with lists to resolve collisions and has expected O(1) running 
6// time for insertions and value retrievals. The hash table automatically grows when a threshold percentage of the hash 
7// table is used (defaulting to 60%). Keys are unique -- the last value assigned to a key is the one stored in the tMap. 
8// 
9// You may iterate through a tMap to retrieve all keys and values. Range-based for loops are supported. Note that this 
10// is slightly less efficient than iterating through a tList though, as empty nodes in the hash table are visited. 
11// 
12// Copyright (c) 2020 Tristan Grimmer. 
13// Permission to use, copy, modify, and/or distribute this software for any purpose with or without fee is hereby 
14// granted, provided that the above copyright notice and this permission notice appear in all copies. 
15// 
16// THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE INCLUDING ALL 
17// IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY SPECIAL, DIRECT, 
18// INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN 
19// AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR 
20// PERFORMANCE OF THIS SOFTWARE. 
21 
22#pragma once 
23#include "Foundation/tAssert.h" 
24#include "Foundation/tPlatform.h" 
25#include "Foundation/tFundamentals.h" 
26#include "Foundation/tList.h" 
27 
28 
29template<typename K, typename V> class tMap 
30{ 
31public: 
32 // Set therekey percent > 1.0f to prevent all rekeying / resizing. 
33 tMap(int initialLog2Size = 8, float rekeyPercent = 0.6f); 
34 ~tMap(); 
35 
36 // These are fast with expected O(1) running time. 
37 V& GetInsert(const K&); 
38 V& operator[](const K&); 
39 bool Remove(const K&); 
40 int GetNumItems() const { return NumItems; } 
41 
42 // These are mostly for debugging or checking performance of the hash table. 
43 int GetHashTableSize() const { return HashTableSize; } 
44 int GetHashTableEntryCount() const { return HashTableEntryCount; } 
45 int GetHashTableCollisions() const { return NumItems - HashTableEntryCount; } 
46 float GetHashTablePercent() const { return float(HashTableEntryCount)/float(HashTableSize); } 
47 
48private: 
49 struct Pair 
50 { 
51 Pair(const Pair& pair) : Key(pair.Key), Value(pair.Value) { } 
52 Pair(const K& key) : Key(key), Value() { } 
53 K Key; V Value; 
54 }; 
55 struct HashTableItem 
56 { 
57 tItList<Pair> Pairs; 
58 }; 
59 void Rekey(int newSize); 
60 int NumItems; 
61 int HashTableSize; 
62 int HashTableEntryCount; 
63 HashTableItem* HashTable; 
64 float RekeyPercent; 
65 
66public: 
67 // If needed you can use this iterator to query every key and/or value in the tMap. Note that the keys and values 
68 // are stored unordered. Further, since not all hash table entries will have valid data, it is slightly less 
69 // efficient to iterate through a tMap vs interating through, for example, a tItList, since empties must be skipped. 
70 class Iter 
71 { 
72 public: 
73 Iter() : Map(nullptr), TableIndex(-1), PairIter() { } 
74 Iter(const Iter& src) : Map(src.Map), TableIndex(src.TableIndex), PairIter(src.PairIter) { } 
75 
76 bool IsValid() const { return PairIter.IsValid(); } 
77 void Clear() { Map = nullptr; TableIndex = -1; PairIter.Clear(); } 
78 void Next(); 
79 V& Value() const { return PairIter->Value; } 
80 K& Key() const { return PairIter->Key; } 
81 
82 Iter& operator*() { return *this; } 
83 Iter* operator->() const { return this; } 
84 operator bool() const { return PairIter.IsValid(); } 
85 Iter& operator=(const Iter& i) { if (this != &i) { Map = i.Map; TableIndex = i.TableIndex; PairIter = i.PairIter; } return *this; } 
86 
87 // Use ++iter instead of iter++ when possible. Since the hash table is unordered, there's no point in offering 
88 // both forward and backwards iteration. Therefore there's only First, Next, operator++ etc. 
89 const Iter operator++(int) { Iter curr(*this); Next(); return curr; } 
90 const Iter operator++() { Next(); return *this; } 
91 const Iter operator+(int offset) const { Iter i = *this; while (offset--) i.Next(); return i; } 
92 Iter& operator+=(int offset) { tAssert(offset >= 0); while (offset--) Next(); return *this; } 
93 bool operator==(const Iter& i) const { return (Map == i.Map) && (TableIndex == i.TableIndex) && (PairIter == i.PairIter); } 
94 bool operator!=(const Iter& i) const { return (Map != i.Map) || (TableIndex != i.TableIndex) || (PairIter != i.PairIter); } 
95 
96 private: 
97 friend class tMap; 
98 Iter(const tMap<K,V>* map, int tableIndex, typename tItList<Pair>::Iter iter) : Map(map), TableIndex(tableIndex), PairIter(iter) { } 
99 const tMap<K,V>* Map; 
100 int TableIndex; 
101 typename tItList<Pair>::Iter PairIter; 
102 }; 
103 
104public: 
105 Iter First() const; 
106 Iter begin() const /* For range-based iteration supported by C++11. */ { return First(); } 
107 Iter end() const /* For range-based iteration supported by C++11. */ { return Iter(this, -1, typename tItList<Pair>::Iter()); } 
108}; 
109 
110 
111// Implementation below this line. 
112 
113 
114template<typename K, typename V> inline tMap<K,V>::tMap(int initialLog2Size, float rekeyPercent) 
115{ 
116 NumItems = 0; 
117 
118 tAssert(initialLog2Size >= 0); 
119 HashTableSize = 1 << initialLog2Size; 
120 
121 tAssert(rekeyPercent >= 0.0f); 
122 RekeyPercent = rekeyPercent; 
123 
124 HashTableEntryCount = 0; 
125 HashTable = new HashTableItem[HashTableSize]; 
126} 
127 
128 
129template<typename K, typename V> inline tMap<K,V>::~tMap() 
130{ 
131 delete[] HashTable; 
132} 
133 
134 
135template<typename K, typename V> inline V& tMap<K,V>::GetInsert(const K& key) 
136{ 
137 // Do we need to grow the hash table? 
138 if (GetHashTablePercent() >= RekeyPercent) 
139 Rekey(2*HashTableSize); 
140 
141 uint32 hash = uint32(key); 
142 int hashBits = tMath::tLog2(HashTableSize); 
143 hash = hash & (0xFFFFFFFF >> (32-hashBits)); 
144 tAssert(hash < HashTableSize); 
145 
146 HashTableItem& item = HashTable[hash]; 
147 for (Pair& pair : item.Pairs) 
148 { 
149 if (pair.Key == key) 
150 return pair.Value; 
151 } 
152 
153 if (item.Pairs.IsEmpty()) 
154 HashTableEntryCount++; 
155 NumItems++; 
156 return item.Pairs.Append(new Pair(key))->Value; 
157} 
158 
159 
160template<typename K, typename V> inline V& tMap<K,V>::operator[](const K& key) 
161{ 
162 return GetInsert(key); 
163} 
164 
165 
166template<typename K, typename V> inline bool tMap<K,V>::Remove(const K& key) 
167{ 
168 uint32 hash = uint32(key); 
169 int hashBits = tMath::tLog2(HashTableSize); 
170 hash = hash & (0xFFFFFFFF >> (32-hashBits)); 
171 tAssert(hash < HashTableSize); 
172 
173 HashTableItem& item = HashTable[hash]; 
174 
175 for (auto iter = item.Pairs.First(); iter; iter++) 
176 { 
177 if (iter->Key == key) 
178 { 
179 delete item.Pairs.Remove(iter); 
180 if (item.Pairs.IsEmpty()) 
181 HashTableEntryCount--; 
182 NumItems--; 
183 return true; 
184 } 
185 } 
186 
187 return false; 
188} 
189 
190 
191template<typename K, typename V> inline void tMap<K,V>::Rekey(int newSize) 
192{ 
193 tAssert((newSize > HashTableSize) && tMath::tIsPower2(newSize)); 
194 HashTableItem* newTable = new HashTableItem[newSize]; 
195 
196 // Loop throught existing keys and rekey them into the new table 
197 for (int i = 0; i < HashTableSize; i++) 
198 { 
199 for (Pair& pair : HashTable[i].Pairs) 
200 { 
201 uint32 hashNew = uint32(pair.Key); 
202 int hashBitsNew = tMath::tLog2(newSize); 
203 hashNew = hashNew & (0xFFFFFFFF >> (32-hashBitsNew)); 
204 
205 tAssert(hashNew < newSize); 
206 newTable[hashNew].Pairs.Append(new Pair(pair)); 
207 } 
208 HashTable[i].Pairs.Clear(); 
209 } 
210 
211 HashTableSize = newSize; 
212 delete[] HashTable; 
213 HashTable = newTable; 
214} 
215 
216 
217template<typename K, typename V> inline void tMap<K,V>::Iter::Next() 
218{ 
219 // If we can just advance the PairIter, we're done. 
220 PairIter++; 
221 if (PairIter.IsValid()) 
222 return; 
223 
224 // Try next hash table entries until we either find a non-empty one or reach the end of the table. 
225 while (++TableIndex < Map->HashTableSize) 
226 { 
227 HashTableItem& item = Map->HashTable[TableIndex]; 
228 if (!item.Pairs.IsEmpty()) 
229 { 
230 PairIter = item.Pairs.First(); 
231 return; 
232 } 
233 }; 
234 
235 // It is vital to have 'this' be the same as end() here, as ranged-based for loops must return false when 
236 // comparing the last Next() with end() using != operator. This is why must set the index to -1. To make 
237 // sure it matches end(). 
238 TableIndex = -1; 
239 PairIter = typename tItList<Pair>::Iter();  
240} 
241 
242 
243template<typename K, typename V> inline typename tMap<K,V>::Iter tMap<K,V>::First() const 
244{ 
245 for (int tableIndex = 0; tableIndex < HashTableSize; tableIndex++) 
246 { 
247 HashTableItem& item = HashTable[tableIndex]; 
248 if (!item.Pairs.IsEmpty()) 
249 return Iter(this, tableIndex, item.Pairs.First()); 
250 } 
251 return Iter(this, -1, typename tItList<Pair>::Iter()); 
252} 
253