libs/container/hashtable.h

   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 {
  33 inline std::size_t next_power_of_two( std::size_t size ){
  34         std::size_t result = 1;
  35         while ( result < size )
  36         {
  37                 result <<= 1;
  38         }
  39         return result;
  40 }
  41
  42 struct BucketNodeBase
  43 {
  44         BucketNodeBase* next;
  45         BucketNodeBase* prev;
  46 };
  47
  48 inline void list_initialise( BucketNodeBase& self ){
  49         self.next = self.prev = &self;
  50 }
  51
  52 inline void list_swap( BucketNodeBase& self, BucketNodeBase& other ){
  53         BucketNodeBase tmp( self );
  54         if ( other.next == &other ) {
  55                 list_initialise( self );
  56         }
  57         else
  58         {
  59                 self = other;
  60                 self.next->prev = self.prev->next = &self;
  61         }
  62         if ( tmp.next == &self ) {
  63                 list_initialise( other );
  64         }
  65         else
  66         {
  67                 other = tmp;
  68                 other.next->prev = other.prev->next = &other;
  69         }
  70 }
  71
  72 inline void node_link( BucketNodeBase* node, BucketNodeBase* next ){
  73         node->next = next;
  74         node->prev = next->prev;
  75         next->prev = node;
  76         node->prev->next = node;
  77 }
  78 inline void node_unlink( BucketNodeBase* node ){
  79         node->prev->next = node->next;
  80         node->next->prev = node->prev;
  81 }
  82
  83 template<typename Key, typename Value>
  84 struct KeyValue
  85 {
  86         const Key key;
  87         Value value;
  88
  89         KeyValue( const Key& key_, const Value& value_ )
  90                 : key( key_ ), value( value_ ){
  91         }
  92 };
  93
  94 template<typename Key, typename Value, typename Hash>
  95 struct BucketNode : public BucketNodeBase
  96 {
  97         Hash m_hash;
  98         KeyValue<Key, Value> m_value;
  99
 100         BucketNode( Hash hash, const Key& key, const Value& value )
 101                 : m_hash( hash ), m_value( key, value ){
 102         }
 103         BucketNode* getNext() const {
 104                 return static_cast<BucketNode*>( next );
 105         }
 106         BucketNode* getPrev() const {
 107                 return static_cast<BucketNode*>( prev );
 108         }
 109 };
 110
 111 template<typename Key, typename Value, typename Hash>
 112 class BucketIterator
 113 {
 114 typedef BucketNode<Key, Value, Hash> Node;
 115 Node* m_node;
 116
 117 void increment(){
 118         m_node = m_node->getNext();
 119 }
 120
 121 public:
 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;
 128
 129 BucketIterator( Node* node ) : m_node( node ){
 130 }
 131
 132 Node* node(){
 133         return m_node;
 134 }
 135
 136 bool operator==( const BucketIterator& other ) const {
 137         return m_node == other.m_node;
 138 }
 139 bool operator!=( const BucketIterator& other ) const {
 140         return !operator==( other );
 141 }
 142 BucketIterator& operator++(){
 143         increment();
 144         return *this;
 145 }
 146 BucketIterator operator++( int ){
 147         BucketIterator tmp = *this;
 148         increment();
 149         return tmp;
 150 }
 151 value_type& operator*() const {
 152         return m_node->m_value;
 153 }
 154 value_type* operator->() const {
 155         return &( operator*() );
 156 }
 157 };
 158 }
 159
 160
 161 /// A hash-table container which maps keys to values.
 162 ///
 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.
 166 ///
 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.
 171 ///
 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
 177 {
 178 typedef typename Hasher::hash_type hash_type;
 179 typedef HashTableDetail::KeyValue<Key, Value> KeyValue;
 180 typedef HashTableDetail::BucketNode<Key, Value, hash_type> BucketNode;
 181
 182 inline BucketNode* node_create( hash_type hash, const Key& key, const Value& value ){
 183         return new BucketNode( hash, key, value );
 184 }
 185 inline void node_destroy( BucketNode* node ){
 186         delete node;
 187 }
 188
 189 typedef BucketNode* Bucket;
 190
 191 static Bucket* buckets_new( std::size_t count ){
 192         Bucket* buckets = new Bucket[count];
 193         std::uninitialized_fill( buckets, buckets + count, Bucket( 0 ) );
 194         return buckets;
 195 }
 196 static void buckets_delete( Bucket* buckets ){
 197         delete[] buckets;
 198 }
 199
 200 std::size_t m_bucketCount;
 201 Bucket* m_buckets;
 202 std::size_t m_size;
 203 HashTableDetail::BucketNodeBase m_list;
 204
 205 BucketNode* getFirst(){
 206         return static_cast<BucketNode*>( m_list.next );
 207 }
 208 BucketNode* getLast(){
 209         return static_cast<BucketNode*>( &m_list );
 210 }
 211
 212 public:
 213
 214 typedef KeyValue value_type;
 215 typedef HashTableDetail::BucketIterator<Key, Value, hash_type> iterator;
 216
 217 private:
 218
 219 void initialise(){
 220         list_initialise( m_list );
 221 }
 222 hash_type hashKey( const Key& key ){
 223         return Hasher::operator()( key );
 224 }
 225
 226 std::size_t getBucketId( hash_type hash ) const {
 227         return hash & ( m_bucketCount - 1 );
 228 }
 229 Bucket& getBucket( hash_type hash ){
 230         return m_buckets[getBucketId( hash )];
 231 }
 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 )
 235         {
 236                 hash_type nodeHash = i.node()->m_hash;
 237
 238                 if ( getBucketId( nodeHash ) != bucketId ) {
 239                         return 0;
 240                 }
 241
 242                 if ( nodeHash == hash && KeyEqual::operator()( ( *i ).key, key ) ) {
 243                         return i.node();
 244                 }
 245         }
 246         return 0;
 247 }
 248 BucketNode* bucket_insert( Bucket& bucket, BucketNode* node ){
 249         // link node into list
 250         node_link( node, bucket_next( bucket ) );
 251         bucket = node;
 252         return node;
 253 }
 254 BucketNode* bucket_next( Bucket& bucket ){
 255         Bucket* end = m_buckets + m_bucketCount;
 256         for ( Bucket* i = &bucket; i != end; ++i )
 257         {
 258                 if ( *i != 0 ) {
 259                         return *i;
 260                 }
 261         }
 262         return getLast();
 263 }
 264
 265 void buckets_resize( std::size_t count ){
 266         BucketNode* first = getFirst();
 267         BucketNode* last = getLast();
 268
 269         buckets_delete( m_buckets );
 270
 271         m_bucketCount = count;
 272
 273         m_buckets = buckets_new( m_bucketCount );
 274         initialise();
 275
 276         for ( BucketNode* i = first; i != last; )
 277         {
 278                 BucketNode* node = i;
 279                 i = i->getNext();
 280                 bucket_insert( getBucket( ( *node ).m_hash ), node );
 281         }
 282 }
 283 void size_increment(){
 284         if ( m_size == m_bucketCount ) {
 285                 buckets_resize( m_bucketCount == 0 ? 8 : m_bucketCount << 1 );
 286         }
 287         ++m_size;
 288 }
 289 void size_decrement(){
 290         --m_size;
 291 }
 292
 293 HashTable( const HashTable& other );
 294 HashTable& operator=( const HashTable& other );
 295 public:
 296 HashTable() : m_bucketCount( 0 ), m_buckets( 0 ), m_size( 0 ){
 297         initialise();
 298 }
 299 HashTable( std::size_t bucketCount ) : m_bucketCount( HashTableDetail::next_power_of_two( bucketCount ) ), m_buckets( buckets_new( m_bucketCount ) ), m_size( 0 ){
 300         initialise();
 301 }
 302 ~HashTable(){
 303         for ( BucketNode* i = getFirst(); i != getLast(); )
 304         {
 305                 BucketNode* node = i;
 306                 i = i->getNext();
 307                 node_destroy( node );
 308         }
 309         buckets_delete( m_buckets );
 310 }
 311
 312 iterator begin(){
 313         return iterator( getFirst() );
 314 }
 315 iterator end(){
 316         return iterator( getLast() );
 317 }
 318
 319 bool empty() const {
 320         return m_size == 0;
 321 }
 322 std::size_t size() const {
 323         return m_size;
 324 }
 325
 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 );
 331                 if ( bucket != 0 ) {
 332                         BucketNode* node = bucket_find( bucket, hash, key );
 333                         if ( node != 0 ) {
 334                                 return iterator( node );
 335                         }
 336                 }
 337         }
 338
 339         return end();
 340 }
 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 );
 346                 if ( bucket != 0 ) {
 347                         BucketNode* node = bucket_find( bucket, hash, key );
 348                         if ( node != 0 ) {
 349                                 return iterator( node );
 350                         }
 351                 }
 352         }
 353
 354         size_increment();
 355         return iterator( bucket_insert( getBucket( hash ), node_create( hash, key, value ) ) );
 356 }
 357
 358 /// \brief Removes the value pointed to by \p i from the hash-table.
 359 ///
 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();
 364
 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();
 368         }
 369
 370         node_unlink( node );
 371         ASSERT_MESSAGE( node != 0, "tried to erase a non-existent key/value" );
 372         node_destroy( node );
 373
 374         size_decrement();
 375 }
 376
 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 );
 382                 if ( bucket != 0 ) {
 383                         BucketNode* node = bucket_find( bucket, hash, key );
 384                         if ( node != 0 ) {
 385                                 return node->m_value.value;
 386                         }
 387                 }
 388         }
 389         size_increment();
 390         return bucket_insert( getBucket( hash ), node_create( hash, key, Value() ) )->m_value.value;
 391 }
 392 /// \brief Removes the value associated with \p key from the hash-table.
 393 void erase( const Key& key ){
 394         erase( find( key ) );
 395 }
 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 );
 402 }
 403 /// \brief Removes all values from the hash-table.
 404 void clear(){
 405         HashTable tmp;
 406         tmp.swap( *this );
 407 }
 408 };
 409
 410 #endif