1 /* 2 Copyright (C) 2001-2006, William Joseph. 3 All Rights Reserved. 4 5 This file is part of GtkRadiant. 6 7 GtkRadiant is free software; you can redistribute it and/or modify 8 it under the terms of the GNU General Public License as published by 9 the Free Software Foundation; either version 2 of the License, or 10 (at your option) any later version. 11 12 GtkRadiant is distributed in the hope that it will be useful, 13 but WITHOUT ANY WARRANTY; without even the implied warranty of 14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 15 GNU General Public License for more details. 16 17 You should have received a copy of the GNU General Public License 18 along with GtkRadiant; if not, write to the Free Software 19 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA 20 */ 21 22 #if !defined(INCLUDED_CONTAINER_HASHTABLE_H) 23 #define INCLUDED_CONTAINER_HASHTABLE_H 24 25 #include <cstddef> 26 #include <algorithm> 27 #include <functional> 28 #include "debugging/debugging.h" 29 30 31 namespace HashTableDetail 32 { next_power_of_two(std::size_t size)33 inline std::size_t next_power_of_two(std::size_t size) 34 { 35 std::size_t result = 1; 36 while(result < size) 37 { 38 result <<= 1; 39 } 40 return result; 41 } 42 43 struct BucketNodeBase 44 { 45 BucketNodeBase* next; 46 BucketNodeBase* prev; 47 }; 48 list_initialise(BucketNodeBase & self)49 inline void list_initialise(BucketNodeBase& self) 50 { 51 self.next = self.prev = &self; 52 } 53 list_swap(BucketNodeBase & self,BucketNodeBase & other)54 inline void list_swap(BucketNodeBase& self, BucketNodeBase& other) 55 { 56 BucketNodeBase tmp(self); 57 if(other.next == &other) 58 { 59 list_initialise(self); 60 } 61 else 62 { 63 self = other; 64 self.next->prev = self.prev->next = &self; 65 } 66 if(tmp.next == &self) 67 { 68 list_initialise(other); 69 } 70 else 71 { 72 other = tmp; 73 other.next->prev = other.prev->next = &other; 74 } 75 } 76 node_link(BucketNodeBase * node,BucketNodeBase * next)77 inline void node_link(BucketNodeBase* node, BucketNodeBase* next) 78 { 79 node->next = next; 80 node->prev = next->prev; 81 next->prev = node; 82 node->prev->next = node; 83 } node_unlink(BucketNodeBase * node)84 inline void node_unlink(BucketNodeBase* node) 85 { 86 node->prev->next = node->next; 87 node->next->prev = node->prev; 88 } 89 90 template<typename Key, typename Value> 91 struct KeyValue 92 { 93 const Key key; 94 Value value; 95 KeyValueKeyValue96 KeyValue(const Key& key_, const Value& value_) 97 : key(key_), value(value_) 98 { 99 } 100 }; 101 102 template<typename Key, typename Value, typename Hash> 103 struct BucketNode : public BucketNodeBase 104 { 105 Hash m_hash; 106 KeyValue<Key, Value> m_value; 107 BucketNodeBucketNode108 BucketNode(Hash hash, const Key& key, const Value& value) 109 : m_hash(hash), m_value(key, value) 110 { 111 } getNextBucketNode112 BucketNode* getNext() 113 { 114 return static_cast<BucketNode*>(next); 115 } getPrevBucketNode116 BucketNode* getPrev() 117 { 118 return static_cast<BucketNode*>(prev); 119 } 120 }; 121 122 template<typename Key, typename Value, typename Hash> 123 class BucketIterator 124 { 125 typedef BucketNode<Key, Value, Hash> Node; 126 Node* m_node; 127 increment()128 void increment() 129 { 130 m_node = m_node->getNext(); 131 } 132 133 public: 134 typedef std::forward_iterator_tag iterator_category; 135 typedef std::ptrdiff_t difference_type; 136 typedef difference_type distance_type; 137 typedef KeyValue<Key, Value> value_type; 138 typedef value_type* pointer; 139 typedef value_type& reference; 140 BucketIterator(Node * node)141 BucketIterator(Node* node) : m_node(node) 142 { 143 } 144 node()145 Node* node() 146 { 147 return m_node; 148 } 149 150 bool operator==(const BucketIterator& other) const 151 { 152 return m_node == other.m_node; 153 } 154 bool operator!=(const BucketIterator& other) const 155 { 156 return !operator==(other); 157 } 158 BucketIterator& operator++() 159 { 160 increment(); 161 return *this; 162 } 163 BucketIterator operator++(int) 164 { 165 BucketIterator tmp = *this; 166 increment(); 167 return tmp; 168 } 169 value_type& operator*() 170 { 171 return m_node->m_value; 172 } 173 value_type* operator->() 174 { 175 return &(operator*()); 176 } 177 }; 178 } 179 180 181 /// A hash-table container which maps keys to values. 182 /// 183 /// - Inserting or removing elements does not invalidate iterators. 184 /// - Inserting or retrieving an element for a given key takes O(1) time on average. 185 /// - Elements are stored in no particular order. 186 /// 187 /// \param Key Uniquely identifies a value. Must provide a copy-constructor. 188 /// \param Value The value to be stored . Must provide a default-constructor and a copy-constructor. 189 /// \param Hasher Must provide 'std::size_t operator()(const Key&) const' which always returns the same result if the same argument is given. 190 /// \param KeyEqual Must provide 'bool operator==(const Key&, const Key&) const' which returns true only if both arguments are equal. 191 /// 192 /// \dontinclude container/hashtable.cpp 193 /// \skipline HashTable example 194 /// \until end example 195 template<typename Key, typename Value, typename Hasher, typename KeyEqual = std::equal_to<Key> > 196 class HashTable : private KeyEqual, private Hasher 197 { 198 typedef typename Hasher::hash_type hash_type; 199 typedef HashTableDetail::KeyValue<Key, Value> KeyValue; 200 typedef HashTableDetail::BucketNode<Key, Value, hash_type> BucketNode; 201 node_create(hash_type hash,const Key & key,const Value & value)202 inline BucketNode* node_create(hash_type hash, const Key& key, const Value& value) 203 { 204 return new BucketNode(hash, key, value); 205 } node_destroy(BucketNode * node)206 inline void node_destroy(BucketNode* node) 207 { 208 delete node; 209 } 210 211 typedef BucketNode* Bucket; 212 buckets_new(std::size_t count)213 static Bucket* buckets_new(std::size_t count) 214 { 215 Bucket* buckets = new Bucket[count]; 216 std::uninitialized_fill(buckets, buckets + count, Bucket(0)); 217 return buckets; 218 } buckets_delete(Bucket * buckets)219 static void buckets_delete(Bucket* buckets) 220 { 221 delete[] buckets; 222 } 223 224 std::size_t m_bucketCount; 225 Bucket* m_buckets; 226 std::size_t m_size; 227 HashTableDetail::BucketNodeBase m_list; 228 getFirst()229 BucketNode* getFirst() 230 { 231 return static_cast<BucketNode*>(m_list.next); 232 } getLast()233 BucketNode* getLast() 234 { 235 return static_cast<BucketNode*>(&m_list); 236 } 237 238 public: 239 240 typedef KeyValue value_type; 241 typedef HashTableDetail::BucketIterator<Key, Value, hash_type> iterator; 242 243 private: 244 initialise()245 void initialise() 246 { 247 list_initialise(m_list); 248 } hashKey(const Key & key)249 hash_type hashKey(const Key& key) 250 { 251 return Hasher::operator()(key); 252 } 253 getBucketId(hash_type hash)254 std::size_t getBucketId(hash_type hash) const 255 { 256 return hash & (m_bucketCount - 1); 257 } getBucket(hash_type hash)258 Bucket& getBucket(hash_type hash) 259 { 260 return m_buckets[getBucketId(hash)]; 261 } bucket_find(Bucket bucket,hash_type hash,const Key & key)262 BucketNode* bucket_find(Bucket bucket, hash_type hash, const Key& key) 263 { 264 std::size_t bucketId = getBucketId(hash); 265 for(iterator i(bucket); i != end(); ++i) 266 { 267 hash_type nodeHash = i.node()->m_hash; 268 269 if(getBucketId(nodeHash) != bucketId) 270 { 271 return 0; 272 } 273 274 if(nodeHash == hash && KeyEqual::operator()((*i).key, key)) 275 { 276 return i.node(); 277 } 278 } 279 return 0; 280 } bucket_insert(Bucket & bucket,BucketNode * node)281 BucketNode* bucket_insert(Bucket& bucket, BucketNode* node) 282 { 283 // link node into list 284 node_link(node, bucket_next(bucket)); 285 bucket = node; 286 return node; 287 } bucket_next(Bucket & bucket)288 BucketNode* bucket_next(Bucket& bucket) 289 { 290 Bucket* end = m_buckets + m_bucketCount; 291 for(Bucket* i = &bucket; i != end; ++i) 292 { 293 if(*i != 0) 294 { 295 return *i; 296 } 297 } 298 return getLast(); 299 } 300 buckets_resize(std::size_t count)301 void buckets_resize(std::size_t count) 302 { 303 BucketNode* first = getFirst(); 304 BucketNode* last = getLast(); 305 306 buckets_delete(m_buckets); 307 308 m_bucketCount = count; 309 310 m_buckets = buckets_new(m_bucketCount); 311 initialise(); 312 313 for(BucketNode* i = first; i != last;) 314 { 315 BucketNode* node = i; 316 i = i->getNext(); 317 bucket_insert(getBucket((*node).m_hash), node); 318 } 319 } size_increment()320 void size_increment() 321 { 322 if(m_size == m_bucketCount) 323 { 324 buckets_resize(m_bucketCount == 0 ? 8 : m_bucketCount << 1); 325 } 326 ++m_size; 327 } size_decrement()328 void size_decrement() 329 { 330 --m_size; 331 } 332 333 HashTable(const HashTable& other); 334 HashTable& operator=(const HashTable& other); 335 public: HashTable()336 HashTable() : m_bucketCount(0), m_buckets(0), m_size(0) 337 { 338 initialise(); 339 } HashTable(std::size_t bucketCount)340 HashTable(std::size_t bucketCount) : m_bucketCount(HashTableDetail::next_power_of_two(bucketCount)), m_buckets(buckets_new(m_bucketCount)), m_size(0) 341 { 342 initialise(); 343 } ~HashTable()344 ~HashTable() 345 { 346 for(BucketNode* i = getFirst(); i != getLast();) 347 { 348 BucketNode* node = i; 349 i = i->getNext(); 350 node_destroy(node); 351 } 352 buckets_delete(m_buckets); 353 } 354 begin()355 iterator begin() 356 { 357 return iterator(getFirst()); 358 } end()359 iterator end() 360 { 361 return iterator(getLast()); 362 } 363 empty()364 bool empty() const 365 { 366 return m_size == 0; 367 } size()368 std::size_t size() const 369 { 370 return m_size; 371 } 372 373 /// \brief Returns an iterator pointing to the value associated with \p key if it is contained by the hash-table, else \c end(). find(const Key & key)374 iterator find(const Key& key) 375 { 376 hash_type hash = hashKey(key); 377 if(m_bucketCount != 0) 378 { 379 Bucket bucket = getBucket(hash); 380 if(bucket != 0) 381 { 382 BucketNode* node = bucket_find(bucket, hash, key); 383 if(node != 0) 384 { 385 return iterator(node); 386 } 387 } 388 } 389 390 return end(); 391 } 392 /// \brief Adds \p value to the hash-table associated with \p key if it does not exist. insert(const Key & key,const Value & value)393 iterator insert(const Key& key, const Value& value) 394 { 395 hash_type hash = hashKey(key); 396 if(m_bucketCount != 0) 397 { 398 Bucket& bucket = getBucket(hash); 399 if(bucket != 0) 400 { 401 BucketNode* node = bucket_find(bucket, hash, key); 402 if(node != 0) 403 { 404 return iterator(node); 405 } 406 } 407 } 408 409 size_increment(); 410 return iterator(bucket_insert(getBucket(hash), node_create(hash, key, value))); 411 } 412 413 /// \brief Removes the value pointed to by \p i from the hash-table. 414 /// 415 /// \p i must be a deferenceable iterator into the hash-table. erase(iterator i)416 void erase(iterator i) 417 { 418 Bucket& bucket = getBucket(i.node()->m_hash); 419 BucketNode* node = i.node(); 420 421 // if this was the last node in the bucket 422 if(bucket == node) 423 { 424 bucket = (node->getNext() == getLast() || &getBucket(node->getNext()->m_hash) != &bucket) ? 0 : node->getNext(); 425 } 426 427 node_unlink(node); 428 ASSERT_MESSAGE(node != 0, "tried to erase a non-existent key/value"); 429 node_destroy(node); 430 431 size_decrement(); 432 } 433 434 /// \brief Returns the value identified by \p key if it is contained by the hash-table, else inserts and returns a new default-constructed value associated with \p key. 435 Value& operator[](const Key& key) 436 { 437 hash_type hash = hashKey(key); 438 if(m_bucketCount != 0) 439 { 440 Bucket& bucket = getBucket(hash); 441 if(bucket != 0) 442 { 443 BucketNode* node = bucket_find(bucket, hash, key); 444 if(node != 0) 445 { 446 return node->m_value.value; 447 } 448 } 449 } 450 size_increment(); 451 return bucket_insert(getBucket(hash), node_create(hash, key, Value()))->m_value.value; 452 } 453 /// \brief Removes the value associated with \p key from the hash-table. erase(const Key & key)454 void erase(const Key& key) 455 { 456 erase(find(key)); 457 } 458 /// \brief Swaps the contents of the hash-table with \p other. swap(HashTable & other)459 void swap(HashTable& other) 460 { 461 std::swap(m_buckets, other.m_buckets); 462 std::swap(m_bucketCount, other.m_bucketCount); 463 std::swap(m_size, other.m_size); 464 HashTableDetail::list_swap(m_list, other.m_list); 465 } 466 /// \brief Removes all values from the hash-table. clear()467 void clear() 468 { 469 HashTable tmp; 470 tmp.swap(*this); 471 } 472 }; 473 474 #endif 475