2 Copyright (C) 2001-2006, William Joseph.
5 This file is part of GtkRadiant.
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.
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.
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
22 #if !defined(INCLUDED_CONTAINER_HASHTABLE_H)
23 #define INCLUDED_CONTAINER_HASHTABLE_H
28 #include "debugging/debugging.h"
31 namespace HashTableDetail
33 inline std::size_t next_power_of_two(std::size_t size)
35 std::size_t result = 1;
49 inline void list_initialise(BucketNodeBase& self)
51 self.next = self.prev = &self;
54 inline void list_swap(BucketNodeBase& self, BucketNodeBase& other)
56 BucketNodeBase tmp(self);
57 if(other.next == &other)
59 list_initialise(self);
64 self.next->prev = self.prev->next = &self;
68 list_initialise(other);
73 other.next->prev = other.prev->next = &other;
77 inline void node_link(BucketNodeBase* node, BucketNodeBase* next)
80 node->prev = next->prev;
82 node->prev->next = node;
84 inline void node_unlink(BucketNodeBase* node)
86 node->prev->next = node->next;
87 node->next->prev = node->prev;
90 template<typename Key, typename Value>
96 KeyValue(const Key& key_, const Value& value_)
97 : key(key_), value(value_)
102 template<typename Key, typename Value, typename Hash>
103 struct BucketNode : public BucketNodeBase
106 KeyValue<Key, Value> m_value;
108 BucketNode(Hash hash, const Key& key, const Value& value)
109 : m_hash(hash), m_value(key, value)
112 BucketNode* getNext() const
114 return static_cast<BucketNode*>(next);
116 BucketNode* getPrev() const
118 return static_cast<BucketNode*>(prev);
122 template<typename Key, typename Value, typename Hash>
125 typedef BucketNode<Key, Value, Hash> Node;
130 m_node = m_node->getNext();
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;
141 BucketIterator(Node* node) : m_node(node)
150 bool operator==(const BucketIterator& other) const
152 return m_node == other.m_node;
154 bool operator!=(const BucketIterator& other) const
156 return !operator==(other);
158 BucketIterator& operator++()
163 BucketIterator operator++(int)
165 BucketIterator tmp = *this;
169 value_type& operator*() const
171 return m_node->m_value;
173 value_type* operator->() const
175 return &(operator*());
181 /// A hash-table container which maps keys to values.
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.
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.
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
198 typedef typename Hasher::hash_type hash_type;
199 typedef HashTableDetail::KeyValue<Key, Value> KeyValue;
200 typedef HashTableDetail::BucketNode<Key, Value, hash_type> BucketNode;
202 inline BucketNode* node_create(hash_type hash, const Key& key, const Value& value)
204 return new BucketNode(hash, key, value);
206 inline void node_destroy(BucketNode* node)
211 typedef BucketNode* Bucket;
213 static Bucket* buckets_new(std::size_t count)
215 Bucket* buckets = new Bucket[count];
216 std::uninitialized_fill(buckets, buckets + count, Bucket(0));
219 static void buckets_delete(Bucket* buckets)
224 std::size_t m_bucketCount;
227 HashTableDetail::BucketNodeBase m_list;
229 BucketNode* getFirst()
231 return static_cast<BucketNode*>(m_list.next);
233 BucketNode* getLast()
235 return static_cast<BucketNode*>(&m_list);
240 typedef KeyValue value_type;
241 typedef HashTableDetail::BucketIterator<Key, Value, hash_type> iterator;
247 list_initialise(m_list);
249 hash_type hashKey(const Key& key)
251 return Hasher::operator()(key);
254 std::size_t getBucketId(hash_type hash) const
256 return hash & (m_bucketCount - 1);
258 Bucket& getBucket(hash_type hash)
260 return m_buckets[getBucketId(hash)];
262 BucketNode* bucket_find(Bucket bucket, hash_type hash, const Key& key)
264 std::size_t bucketId = getBucketId(hash);
265 for(iterator i(bucket); i != end(); ++i)
267 hash_type nodeHash = i.node()->m_hash;
269 if(getBucketId(nodeHash) != bucketId)
274 if(nodeHash == hash && KeyEqual::operator()((*i).key, key))
281 BucketNode* bucket_insert(Bucket& bucket, BucketNode* node)
283 // link node into list
284 node_link(node, bucket_next(bucket));
288 BucketNode* bucket_next(Bucket& bucket)
290 Bucket* end = m_buckets + m_bucketCount;
291 for(Bucket* i = &bucket; i != end; ++i)
301 void buckets_resize(std::size_t count)
303 BucketNode* first = getFirst();
304 BucketNode* last = getLast();
306 buckets_delete(m_buckets);
308 m_bucketCount = count;
310 m_buckets = buckets_new(m_bucketCount);
313 for(BucketNode* i = first; i != last;)
315 BucketNode* node = i;
317 bucket_insert(getBucket((*node).m_hash), node);
320 void size_increment()
322 if(m_size == m_bucketCount)
324 buckets_resize(m_bucketCount == 0 ? 8 : m_bucketCount << 1);
328 void size_decrement()
333 HashTable(const HashTable& other);
334 HashTable& operator=(const HashTable& other);
336 HashTable() : m_bucketCount(0), m_buckets(0), m_size(0)
340 HashTable(std::size_t bucketCount) : m_bucketCount(HashTableDetail::next_power_of_two(bucketCount)), m_buckets(buckets_new(m_bucketCount)), m_size(0)
346 for(BucketNode* i = getFirst(); i != getLast();)
348 BucketNode* node = i;
352 buckets_delete(m_buckets);
357 return iterator(getFirst());
361 return iterator(getLast());
368 std::size_t size() const
373 /// \brief Returns an iterator pointing to the value associated with \p key if it is contained by the hash-table, else \c end().
374 iterator find(const Key& key)
376 hash_type hash = hashKey(key);
377 if(m_bucketCount != 0)
379 Bucket bucket = getBucket(hash);
382 BucketNode* node = bucket_find(bucket, hash, key);
385 return iterator(node);
392 /// \brief Adds \p value to the hash-table associated with \p key if it does not exist.
393 iterator insert(const Key& key, const Value& value)
395 hash_type hash = hashKey(key);
396 if(m_bucketCount != 0)
398 Bucket& bucket = getBucket(hash);
401 BucketNode* node = bucket_find(bucket, hash, key);
404 return iterator(node);
410 return iterator(bucket_insert(getBucket(hash), node_create(hash, key, value)));
413 /// \brief Removes the value pointed to by \p i from the hash-table.
415 /// \p i must be a deferenceable iterator into the hash-table.
416 void erase(iterator i)
418 Bucket& bucket = getBucket(i.node()->m_hash);
419 BucketNode* node = i.node();
421 // if this was the last node in the bucket
424 bucket = (node->getNext() == getLast() || &getBucket(node->getNext()->m_hash) != &bucket) ? 0 : node->getNext();
428 ASSERT_MESSAGE(node != 0, "tried to erase a non-existent key/value");
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)
437 hash_type hash = hashKey(key);
438 if(m_bucketCount != 0)
440 Bucket& bucket = getBucket(hash);
443 BucketNode* node = bucket_find(bucket, hash, key);
446 return node->m_value.value;
451 return bucket_insert(getBucket(hash), node_create(hash, key, Value()))->m_value.value;
453 /// \brief Removes the value associated with \p key from the hash-table.
454 void erase(const Key& key)
458 /// \brief Swaps the contents of the hash-table with \p other.
459 void swap(HashTable& other)
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);
466 /// \brief Removes all values from the hash-table.