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 ){
34 std::size_t result = 1;
35 while ( result < size )
48 inline void list_initialise( BucketNodeBase& self ){
49 self.next = self.prev = &self;
52 inline void list_swap( BucketNodeBase& self, BucketNodeBase& other ){
53 BucketNodeBase tmp( self );
54 if ( other.next == &other ) {
55 list_initialise( self );
60 self.next->prev = self.prev->next = &self;
62 if ( tmp.next == &self ) {
63 list_initialise( other );
68 other.next->prev = other.prev->next = &other;
72 inline void node_link( BucketNodeBase* node, BucketNodeBase* next ){
74 node->prev = next->prev;
76 node->prev->next = node;
78 inline void node_unlink( BucketNodeBase* node ){
79 node->prev->next = node->next;
80 node->next->prev = node->prev;
83 template<typename Key, typename Value>
89 KeyValue( const Key& key_, const Value& value_ )
90 : key( key_ ), value( value_ ){
94 template<typename Key, typename Value, typename Hash>
95 struct BucketNode : public BucketNodeBase
98 KeyValue<Key, Value> m_value;
100 BucketNode( Hash hash, const Key& key, const Value& value )
101 : m_hash( hash ), m_value( key, value ){
103 BucketNode* getNext() const {
104 return static_cast<BucketNode*>( next );
106 BucketNode* getPrev() const {
107 return static_cast<BucketNode*>( prev );
111 template<typename Key, typename Value, typename Hash>
114 typedef BucketNode<Key, Value, Hash> Node;
118 m_node = m_node->getNext();
122 typedef std::forward_iterator_tag iterator_category;
123 typedef std::ptrdiff_t difference_type;
124 typedef difference_type distance_type;
125 typedef KeyValue<Key, Value> value_type;
126 typedef value_type* pointer;
127 typedef value_type& reference;
129 BucketIterator( Node* node ) : m_node( node ){
136 bool operator==( const BucketIterator& other ) const {
137 return m_node == other.m_node;
139 bool operator!=( const BucketIterator& other ) const {
140 return !operator==( other );
142 BucketIterator& operator++(){
146 BucketIterator operator++( int ){
147 BucketIterator tmp = *this;
151 value_type& operator*() const {
152 return m_node->m_value;
154 value_type* operator->() const {
155 return &( operator*() );
161 /// A hash-table container which maps keys to values.
163 /// - Inserting or removing elements does not invalidate iterators.
164 /// - Inserting or retrieving an element for a given key takes O(1) time on average.
165 /// - Elements are stored in no particular order.
167 /// \param Key Uniquely identifies a value. Must provide a copy-constructor.
168 /// \param Value The value to be stored . Must provide a default-constructor and a copy-constructor.
169 /// \param Hasher Must provide 'std::size_t operator()(const Key&) const' which always returns the same result if the same argument is given.
170 /// \param KeyEqual Must provide 'bool operator==(const Key&, const Key&) const' which returns true only if both arguments are equal.
172 /// \dontinclude container/hashtable.cpp
173 /// \skipline HashTable example
174 /// \until end example
175 template<typename Key, typename Value, typename Hasher, typename KeyEqual = std::equal_to<Key> >
176 class HashTable : private KeyEqual, private Hasher
178 typedef typename Hasher::hash_type hash_type;
179 typedef HashTableDetail::KeyValue<Key, Value> KeyValue;
180 typedef HashTableDetail::BucketNode<Key, Value, hash_type> BucketNode;
182 inline BucketNode* node_create( hash_type hash, const Key& key, const Value& value ){
183 return new BucketNode( hash, key, value );
185 inline void node_destroy( BucketNode* node ){
189 typedef BucketNode* Bucket;
191 static Bucket* buckets_new( std::size_t count ){
192 Bucket* buckets = new Bucket[count];
193 std::uninitialized_fill( buckets, buckets + count, Bucket( 0 ) );
196 static void buckets_delete( Bucket* buckets ){
200 std::size_t m_bucketCount;
203 HashTableDetail::BucketNodeBase m_list;
205 BucketNode* getFirst(){
206 return static_cast<BucketNode*>( m_list.next );
208 BucketNode* getLast(){
209 return static_cast<BucketNode*>( &m_list );
214 typedef KeyValue value_type;
215 typedef HashTableDetail::BucketIterator<Key, Value, hash_type> iterator;
220 list_initialise( m_list );
222 hash_type hashKey( const Key& key ){
223 return Hasher::operator()( key );
226 std::size_t getBucketId( hash_type hash ) const {
227 return hash & ( m_bucketCount - 1 );
229 Bucket& getBucket( hash_type hash ){
230 return m_buckets[getBucketId( hash )];
232 BucketNode* bucket_find( Bucket bucket, hash_type hash, const Key& key ){
233 std::size_t bucketId = getBucketId( hash );
234 for ( iterator i( bucket ); i != end(); ++i )
236 hash_type nodeHash = i.node()->m_hash;
238 if ( getBucketId( nodeHash ) != bucketId ) {
242 if ( nodeHash == hash && KeyEqual::operator()( ( *i ).key, key ) ) {
248 BucketNode* bucket_insert( Bucket& bucket, BucketNode* node ){
249 // link node into list
250 node_link( node, bucket_next( bucket ) );
254 BucketNode* bucket_next( Bucket& bucket ){
255 Bucket* end = m_buckets + m_bucketCount;
256 for ( Bucket* i = &bucket; i != end; ++i )
265 void buckets_resize( std::size_t count ){
266 BucketNode* first = getFirst();
267 BucketNode* last = getLast();
269 buckets_delete( m_buckets );
271 m_bucketCount = count;
273 m_buckets = buckets_new( m_bucketCount );
276 for ( BucketNode* i = first; i != last; )
278 BucketNode* node = i;
280 bucket_insert( getBucket( ( *node ).m_hash ), node );
283 void size_increment(){
284 if ( m_size == m_bucketCount ) {
285 buckets_resize( m_bucketCount == 0 ? 8 : m_bucketCount << 1 );
289 void size_decrement(){
293 HashTable( const HashTable& other );
294 HashTable& operator=( const HashTable& other );
296 HashTable() : m_bucketCount( 0 ), m_buckets( 0 ), m_size( 0 ){
299 HashTable( std::size_t bucketCount ) : m_bucketCount( HashTableDetail::next_power_of_two( bucketCount ) ), m_buckets( buckets_new( m_bucketCount ) ), m_size( 0 ){
303 for ( BucketNode* i = getFirst(); i != getLast(); )
305 BucketNode* node = i;
307 node_destroy( node );
309 buckets_delete( m_buckets );
313 return iterator( getFirst() );
316 return iterator( getLast() );
322 std::size_t size() const {
326 /// \brief Returns an iterator pointing to the value associated with \p key if it is contained by the hash-table, else \c end().
327 iterator find( const Key& key ){
328 hash_type hash = hashKey( key );
329 if ( m_bucketCount != 0 ) {
330 Bucket bucket = getBucket( hash );
332 BucketNode* node = bucket_find( bucket, hash, key );
334 return iterator( node );
341 /// \brief Adds \p value to the hash-table associated with \p key if it does not exist.
342 iterator insert( const Key& key, const Value& value ){
343 hash_type hash = hashKey( key );
344 if ( m_bucketCount != 0 ) {
345 Bucket& bucket = getBucket( hash );
347 BucketNode* node = bucket_find( bucket, hash, key );
349 return iterator( node );
355 return iterator( bucket_insert( getBucket( hash ), node_create( hash, key, value ) ) );
358 /// \brief Removes the value pointed to by \p i from the hash-table.
360 /// \p i must be a deferenceable iterator into the hash-table.
361 void erase( iterator i ){
362 Bucket& bucket = getBucket( i.node()->m_hash );
363 BucketNode* node = i.node();
365 // if this was the last node in the bucket
366 if ( bucket == node ) {
367 bucket = ( node->getNext() == getLast() || &getBucket( node->getNext()->m_hash ) != &bucket ) ? 0 : node->getNext();
371 ASSERT_MESSAGE( node != 0, "tried to erase a non-existent key/value" );
372 node_destroy( node );
377 /// \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.
378 Value& operator[]( const Key& key ){
379 hash_type hash = hashKey( key );
380 if ( m_bucketCount != 0 ) {
381 Bucket& bucket = getBucket( hash );
383 BucketNode* node = bucket_find( bucket, hash, key );
385 return node->m_value.value;
390 return bucket_insert( getBucket( hash ), node_create( hash, key, Value() ) )->m_value.value;
392 /// \brief Removes the value associated with \p key from the hash-table.
393 void erase( const Key& key ){
394 erase( find( key ) );
396 /// \brief Swaps the contents of the hash-table with \p other.
397 void swap( HashTable& other ){
398 std::swap( m_buckets, other.m_buckets );
399 std::swap( m_bucketCount, other.m_bucketCount );
400 std::swap( m_size, other.m_size );
401 HashTableDetail::list_swap( m_list, other.m_list );
403 /// \brief Removes all values from the hash-table.