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
29 #include "debugging/debugging.h"
32 namespace HashTableDetail
34 inline std::size_t next_power_of_two( std::size_t size ){
35 std::size_t result = 1;
36 while ( result < size )
49 inline void list_initialise( BucketNodeBase& self ){
50 self.next = self.prev = &self;
53 inline void list_swap( BucketNodeBase& self, BucketNodeBase& other ){
54 BucketNodeBase tmp( self );
55 if ( other.next == &other ) {
56 list_initialise( self );
61 self.next->prev = self.prev->next = &self;
63 if ( tmp.next == &self ) {
64 list_initialise( other );
69 other.next->prev = other.prev->next = &other;
73 inline void node_link( BucketNodeBase* node, BucketNodeBase* next ){
75 node->prev = next->prev;
77 node->prev->next = node;
79 inline void node_unlink( BucketNodeBase* node ){
80 node->prev->next = node->next;
81 node->next->prev = node->prev;
84 template<typename Key, typename Value>
90 KeyValue( const Key& key_, const Value& value_ )
91 : key( key_ ), value( value_ ){
95 template<typename Key, typename Value, typename Hash>
96 struct BucketNode : public BucketNodeBase
99 KeyValue<Key, Value> m_value;
101 BucketNode( Hash hash, const Key& key, const Value& value )
102 : m_hash( hash ), m_value( key, value ){
104 BucketNode* getNext() const {
105 return static_cast<BucketNode*>( next );
107 BucketNode* getPrev() const {
108 return static_cast<BucketNode*>( prev );
112 template<typename Key, typename Value, typename Hash>
115 typedef BucketNode<Key, Value, Hash> Node;
119 m_node = m_node->getNext();
123 typedef std::forward_iterator_tag iterator_category;
124 typedef std::ptrdiff_t difference_type;
125 typedef difference_type distance_type;
126 typedef KeyValue<Key, Value> value_type;
127 typedef value_type* pointer;
128 typedef value_type& reference;
130 BucketIterator( Node* node ) : m_node( node ){
137 bool operator==( const BucketIterator& other ) const {
138 return m_node == other.m_node;
140 bool operator!=( const BucketIterator& other ) const {
141 return !operator==( other );
143 BucketIterator& operator++(){
147 BucketIterator operator++( int ){
148 BucketIterator tmp = *this;
152 value_type& operator*() const {
153 return m_node->m_value;
155 value_type* operator->() const {
156 return &( operator*() );
162 /// A hash-table container which maps keys to values.
164 /// - Inserting or removing elements does not invalidate iterators.
165 /// - Inserting or retrieving an element for a given key takes O(1) time on average.
166 /// - Elements are stored in no particular order.
168 /// \param Key Uniquely identifies a value. Must provide a copy-constructor.
169 /// \param Value The value to be stored . Must provide a default-constructor and a copy-constructor.
170 /// \param Hasher Must provide 'std::size_t operator()(const Key&) const' which always returns the same result if the same argument is given.
171 /// \param KeyEqual Must provide 'bool operator==(const Key&, const Key&) const' which returns true only if both arguments are equal.
173 /// \dontinclude container/hashtable.cpp
174 /// \skipline HashTable example
175 /// \until end example
176 template<typename Key, typename Value, typename Hasher, typename KeyEqual = std::equal_to<Key> >
177 class HashTable : private KeyEqual, private Hasher
179 typedef typename Hasher::hash_type hash_type;
180 typedef HashTableDetail::KeyValue<Key, Value> KeyValue;
181 typedef HashTableDetail::BucketNode<Key, Value, hash_type> BucketNode;
183 inline BucketNode* node_create( hash_type hash, const Key& key, const Value& value ){
184 return new BucketNode( hash, key, value );
186 inline void node_destroy( BucketNode* node ){
190 typedef BucketNode* Bucket;
192 static Bucket* buckets_new( std::size_t count ){
193 Bucket* buckets = new Bucket[count];
194 std::uninitialized_fill( buckets, buckets + count, Bucket( 0 ) );
197 static void buckets_delete( Bucket* buckets ){
201 std::size_t m_bucketCount;
204 HashTableDetail::BucketNodeBase m_list;
206 BucketNode* getFirst(){
207 return static_cast<BucketNode*>( m_list.next );
209 BucketNode* getLast(){
210 return static_cast<BucketNode*>( &m_list );
215 typedef KeyValue value_type;
216 typedef HashTableDetail::BucketIterator<Key, Value, hash_type> iterator;
221 list_initialise( m_list );
223 hash_type hashKey( const Key& key ){
224 return Hasher::operator()( key );
227 std::size_t getBucketId( hash_type hash ) const {
228 return hash & ( m_bucketCount - 1 );
230 Bucket& getBucket( hash_type hash ){
231 return m_buckets[getBucketId( hash )];
233 BucketNode* bucket_find( Bucket bucket, hash_type hash, const Key& key ){
234 std::size_t bucketId = getBucketId( hash );
235 for ( iterator i( bucket ); i != end(); ++i )
237 hash_type nodeHash = i.node()->m_hash;
239 if ( getBucketId( nodeHash ) != bucketId ) {
243 if ( nodeHash == hash && KeyEqual::operator()( ( *i ).key, key ) ) {
249 BucketNode* bucket_insert( Bucket& bucket, BucketNode* node ){
250 // link node into list
251 node_link( node, bucket_next( bucket ) );
255 BucketNode* bucket_next( Bucket& bucket ){
256 Bucket* end = m_buckets + m_bucketCount;
257 for ( Bucket* i = &bucket; i != end; ++i )
266 void buckets_resize( std::size_t count ){
267 BucketNode* first = getFirst();
268 BucketNode* last = getLast();
270 buckets_delete( m_buckets );
272 m_bucketCount = count;
274 m_buckets = buckets_new( m_bucketCount );
277 for ( BucketNode* i = first; i != last; )
279 BucketNode* node = i;
281 bucket_insert( getBucket( ( *node ).m_hash ), node );
284 void size_increment(){
285 if ( m_size == m_bucketCount ) {
286 buckets_resize( m_bucketCount == 0 ? 8 : m_bucketCount << 1 );
290 void size_decrement(){
294 HashTable( const HashTable& other );
295 HashTable& operator=( const HashTable& other );
297 HashTable() : m_bucketCount( 0 ), m_buckets( 0 ), m_size( 0 ){
300 HashTable( std::size_t bucketCount ) : m_bucketCount( HashTableDetail::next_power_of_two( bucketCount ) ), m_buckets( buckets_new( m_bucketCount ) ), m_size( 0 ){
304 for ( BucketNode* i = getFirst(); i != getLast(); )
306 BucketNode* node = i;
308 node_destroy( node );
310 buckets_delete( m_buckets );
314 return iterator( getFirst() );
317 return iterator( getLast() );
323 std::size_t size() const {
327 /// \brief Returns an iterator pointing to the value associated with \p key if it is contained by the hash-table, else \c end().
328 iterator find( const Key& key ){
329 hash_type hash = hashKey( key );
330 if ( m_bucketCount != 0 ) {
331 Bucket bucket = getBucket( hash );
333 BucketNode* node = bucket_find( bucket, hash, key );
335 return iterator( node );
342 /// \brief Adds \p value to the hash-table associated with \p key if it does not exist.
343 iterator insert( const Key& key, const Value& value ){
344 hash_type hash = hashKey( key );
345 if ( m_bucketCount != 0 ) {
346 Bucket& bucket = getBucket( hash );
348 BucketNode* node = bucket_find( bucket, hash, key );
350 return iterator( node );
356 return iterator( bucket_insert( getBucket( hash ), node_create( hash, key, value ) ) );
359 /// \brief Removes the value pointed to by \p i from the hash-table.
361 /// \p i must be a deferenceable iterator into the hash-table.
362 void erase( iterator i ){
363 Bucket& bucket = getBucket( i.node()->m_hash );
364 BucketNode* node = i.node();
366 // if this was the last node in the bucket
367 if ( bucket == node ) {
368 bucket = ( node->getNext() == getLast() || &getBucket( node->getNext()->m_hash ) != &bucket ) ? 0 : node->getNext();
372 ASSERT_MESSAGE( node != 0, "tried to erase a non-existent key/value" );
373 node_destroy( node );
378 /// \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.
379 Value& operator[]( const Key& key ){
380 hash_type hash = hashKey( key );
381 if ( m_bucketCount != 0 ) {
382 Bucket& bucket = getBucket( hash );
384 BucketNode* node = bucket_find( bucket, hash, key );
386 return node->m_value.value;
391 return bucket_insert( getBucket( hash ), node_create( hash, key, Value() ) )->m_value.value;
393 /// \brief Removes the value associated with \p key from the hash-table.
394 void erase( const Key& key ){
395 erase( find( key ) );
397 /// \brief Swaps the contents of the hash-table with \p other.
398 void swap( HashTable& other ){
399 std::swap( m_buckets, other.m_buckets );
400 std::swap( m_bucketCount, other.m_bucketCount );
401 std::swap( m_size, other.m_size );
402 HashTableDetail::list_swap( m_list, other.m_list );
404 /// \brief Removes all values from the hash-table.