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 <unordered_map>
  26
  27 template<typename Key, typename Value, typename Hasher, typename KeyEqual = std::equal_to<Key> >
  28         using HashTable = std::unordered_map<Key, Value, Hasher, KeyEqual>;
  29
  30 #if 0
  31 #include <cstddef>
  32 #include <algorithm>
  33 #include <functional>
  34 #include <memory>
  35 #include "debugging/debugging.h"
  36
  37 namespace HashTableDetail
  38 {
  39 inline std::size_t next_power_of_two( std::size_t size ){
  40         std::size_t result = 1;
  41         while ( result < size )
  42         {
  43                 result <<= 1;
  44         }
  45         return result;
  46 }
  47
  48 struct BucketNodeBase
  49 {
  50         BucketNodeBase* next;
  51         BucketNodeBase* prev;
  52 };
  53
  54 inline void list_initialise( BucketNodeBase& self ){
  55         self.next = self.prev = &self;
  56 }
  57
  58 inline void list_swap( BucketNodeBase& self, BucketNodeBase& other ){
  59         BucketNodeBase tmp( self );
  60         if ( other.next == &other ) {
  61                 list_initialise( self );
  62         }
  63         else
  64         {
  65                 self = other;
  66                 self.next->prev = self.prev->next = &self;
  67         }
  68         if ( tmp.next == &self ) {
  69                 list_initialise( other );
  70         }
  71         else
  72         {
  73                 other = tmp;
  74                 other.next->prev = other.prev->next = &other;
  75         }
  76 }
  77
  78 inline void node_link( BucketNodeBase* node, BucketNodeBase* next ){
  79         node->next = next;
  80         node->prev = next->prev;
  81         next->prev = node;
  82         node->prev->next = node;
  83 }
  84 inline void node_unlink( BucketNodeBase* node ){
  85         node->prev->next = node->next;
  86         node->next->prev = node->prev;
  87 }
  88
  89 template<typename Key, typename Value>
  90 struct KeyValue
  91 {
  92         const Key key;
  93         Value value;
  94
  95         KeyValue( const Key& key_, const Value& value_ )
  96                 : key( key_ ), value( value_ ){
  97         }
  98 };
  99
 100 template<typename Key, typename Value, typename Hash>
 101 struct BucketNode : public BucketNodeBase
 102 {
 103         Hash m_hash;
 104         KeyValue<Key, Value> m_value;
 105
 106         BucketNode( Hash hash, const Key& key, const Value& value )
 107                 : m_hash( hash ), m_value( key, value ){
 108         }
 109         BucketNode* getNext() const {
 110                 return static_cast<BucketNode*>( next );
 111         }
 112         BucketNode* getPrev() const {
 113                 return static_cast<BucketNode*>( prev );
 114         }
 115 };
 116
 117 template<typename Key, typename Value, typename Hash>
 118 class BucketIterator
 119 {
 120 typedef BucketNode<Key, Value, Hash> Node;
 121 Node* m_node;
 122
 123 void increment(){
 124         m_node = m_node->getNext();
 125 }
 126
 127 public:
 128 typedef std::forward_iterator_tag iterator_category;
 129 typedef std::ptrdiff_t difference_type;
 130 typedef difference_type distance_type;
 131 typedef KeyValue<Key, Value> value_type;
 132 typedef value_type* pointer;
 133 typedef value_type& reference;
 134
 135 BucketIterator( Node* node ) : m_node( node ){
 136 }
 137
 138 Node* node(){
 139         return m_node;
 140 }
 141
 142 bool operator==( const BucketIterator& other ) const {
 143         return m_node == other.m_node;
 144 }
 145 bool operator!=( const BucketIterator& other ) const {
 146         return !operator==( other );
 147 }
 148 BucketIterator& operator++(){
 149         increment();
 150         return *this;
 151 }
 152 BucketIterator operator++( int ){
 153         BucketIterator tmp = *this;
 154         increment();
 155         return tmp;
 156 }
 157 value_type& operator*() const {
 158         return m_node->m_value;
 159 }
 160 value_type* operator->() const {
 161         return &( operator*() );
 162 }
 163 };
 164 }
 165
 166
 167 /// A hash-table container which maps keys to values.
 168 ///
 169 /// - Inserting or removing elements does not invalidate iterators.
 170 /// - Inserting or retrieving an element for a given key takes O(1) time on average.
 171 /// - Elements are stored in no particular order.
 172 ///
 173 /// \param Key Uniquely identifies a value. Must provide a copy-constructor.
 174 /// \param Value The value to be stored . Must provide a default-constructor and a copy-constructor.
 175 /// \param Hasher Must provide 'std::size_t operator()(const Key&) const' which always returns the same result if the same argument is given.
 176 /// \param KeyEqual Must provide 'bool operator==(const Key&, const Key&) const' which returns true only if both arguments are equal.
 177 ///
 178 /// \dontinclude container/hashtable.cpp
 179 /// \skipline HashTable example
 180 /// \until end example
 181 template<typename Key, typename Value, typename Hasher, typename KeyEqual = std::equal_to<Key> >
 182 class HashTable : private KeyEqual, private Hasher
 183 {
 184 typedef typename Hasher::hash_type hash_type;
 185 typedef HashTableDetail::KeyValue<Key, Value> KeyValue;
 186 typedef HashTableDetail::BucketNode<Key, Value, hash_type> BucketNode;
 187
 188 inline BucketNode* node_create( hash_type hash, const Key& key, const Value& value ){
 189         return new BucketNode( hash, key, value );
 190 }
 191 inline void node_destroy( BucketNode* node ){
 192         delete node;
 193 }
 194
 195 typedef BucketNode* Bucket;
 196
 197 static Bucket* buckets_new( std::size_t count ){
 198         Bucket* buckets = new Bucket[count];
 199         std::uninitialized_fill( buckets, buckets + count, Bucket( 0 ) );
 200         return buckets;
 201 }
 202 static void buckets_delete( Bucket* buckets ){
 203         delete[] buckets;
 204 }
 205
 206 std::size_t m_bucketCount;
 207 Bucket* m_buckets;
 208 std::size_t m_size;
 209 HashTableDetail::BucketNodeBase m_list;
 210
 211 BucketNode* getFirst(){
 212         return static_cast<BucketNode*>( m_list.next );
 213 }
 214 BucketNode* getLast(){
 215         return static_cast<BucketNode*>( &m_list );
 216 }
 217
 218 public:
 219
 220 typedef KeyValue value_type;
 221 typedef HashTableDetail::BucketIterator<Key, Value, hash_type> iterator;
 222
 223 private:
 224
 225 void initialise(){
 226         list_initialise( m_list );
 227 }
 228 hash_type hashKey( const Key& key ){
 229         return Hasher::operator()( key );
 230 }
 231
 232 std::size_t getBucketId( hash_type hash ) const {
 233         return hash & ( m_bucketCount - 1 );
 234 }
 235 Bucket& getBucket( hash_type hash ){
 236         return m_buckets[getBucketId( hash )];
 237 }
 238 BucketNode* bucket_find( Bucket bucket, hash_type hash, const Key& key ){
 239         std::size_t bucketId = getBucketId( hash );
 240         for ( iterator i( bucket ); i != end(); ++i )
 241         {
 242                 hash_type nodeHash = i.node()->m_hash;
 243
 244                 if ( getBucketId( nodeHash ) != bucketId ) {
 245                         return 0;
 246                 }
 247
 248                 if ( nodeHash == hash && KeyEqual::operator()( ( *i ).first, key ) ) {
 249                         return i.node();
 250                 }
 251         }
 252         return 0;
 253 }
 254 BucketNode* bucket_insert( Bucket& bucket, BucketNode* node ){
 255         // link node into list
 256         node_link( node, bucket_next( bucket ) );
 257         bucket = node;
 258         return node;
 259 }
 260 BucketNode* bucket_next( Bucket& bucket ){
 261         Bucket* end = m_buckets + m_bucketCount;
 262         for ( Bucket* i = &bucket; i != end; ++i )
 263         {
 264                 if ( *i != 0 ) {
 265                         return *i;
 266                 }
 267         }
 268         return getLast();
 269 }
 270
 271 void buckets_resize( std::size_t count ){
 272         BucketNode* first = getFirst();
 273         BucketNode* last = getLast();
 274
 275         buckets_delete( m_buckets );
 276
 277         m_bucketCount = count;
 278
 279         m_buckets = buckets_new( m_bucketCount );
 280         initialise();
 281
 282         for ( BucketNode* i = first; i != last; )
 283         {
 284                 BucketNode* node = i;
 285                 i = i->getNext();
 286                 bucket_insert( getBucket( ( *node ).m_hash ), node );
 287         }
 288 }
 289 void size_increment(){
 290         if ( m_size == m_bucketCount ) {
 291                 buckets_resize( m_bucketCount == 0 ? 8 : m_bucketCount << 1 );
 292         }
 293         ++m_size;
 294 }
 295 void size_decrement(){
 296         --m_size;
 297 }
 298
 299 HashTable( const HashTable& other );
 300 HashTable& operator=( const HashTable& other );
 301 public:
 302 HashTable() : m_bucketCount( 0 ), m_buckets( 0 ), m_size( 0 ){
 303         initialise();
 304 }
 305 HashTable( std::size_t bucketCount ) : m_bucketCount( HashTableDetail::next_power_of_two( bucketCount ) ), m_buckets( buckets_new( m_bucketCount ) ), m_size( 0 ){
 306         initialise();
 307 }
 308 ~HashTable(){
 309         for ( BucketNode* i = getFirst(); i != getLast(); )
 310         {
 311                 BucketNode* node = i;
 312                 i = i->getNext();
 313                 node_destroy( node );
 314         }
 315         buckets_delete( m_buckets );
 316 }
 317
 318 iterator begin(){
 319         return iterator( getFirst() );
 320 }
 321 iterator end(){
 322         return iterator( getLast() );
 323 }
 324
 325 bool empty() const {
 326         return m_size == 0;
 327 }
 328 std::size_t size() const {
 329         return m_size;
 330 }
 331
 332 /// \brief Returns an iterator pointing to the value associated with \p key if it is contained by the hash-table, else \c end().
 333 iterator find( const Key& key ){
 334         hash_type hash = hashKey( key );
 335         if ( m_bucketCount != 0 ) {
 336                 Bucket bucket = getBucket( hash );
 337                 if ( bucket != 0 ) {
 338                         BucketNode* node = bucket_find( bucket, hash, key );
 339                         if ( node != 0 ) {
 340                                 return iterator( node );
 341                         }
 342                 }
 343         }
 344
 345         return end();
 346 }
 347 /// \brief Adds \p value to the hash-table associated with \p key if it does not exist.
 348 iterator insert( const Key& key, const Value& value ){
 349         hash_type hash = hashKey( key );
 350         if ( m_bucketCount != 0 ) {
 351                 Bucket& bucket = getBucket( hash );
 352                 if ( bucket != 0 ) {
 353                         BucketNode* node = bucket_find( bucket, hash, key );
 354                         if ( node != 0 ) {
 355                                 return iterator( node );
 356                         }
 357                 }
 358         }
 359
 360         size_increment();
 361         return iterator( bucket_insert( getBucket( hash ), node_create( hash, key, value ) ) );
 362 }
 363
 364 /// \brief Removes the value pointed to by \p i from the hash-table.
 365 ///
 366 /// \p i must be a deferenceable iterator into the hash-table.
 367 void erase( iterator i ){
 368         Bucket& bucket = getBucket( i.node()->m_hash );
 369         BucketNode* node = i.node();
 370
 371         // if this was the last node in the bucket
 372         if ( bucket == node ) {
 373                 bucket = ( node->getNext() == getLast() || &getBucket( node->getNext()->m_hash ) != &bucket ) ? 0 : node->getNext();
 374         }
 375
 376         node_unlink( node );
 377         ASSERT_MESSAGE( node != 0, "tried to erase a non-existent key/value" );
 378         node_destroy( node );
 379
 380         size_decrement();
 381 }
 382
 383 /// \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.
 384 Value& operator[]( const Key& key ){
 385         hash_type hash = hashKey( key );
 386         if ( m_bucketCount != 0 ) {
 387                 Bucket& bucket = getBucket( hash );
 388                 if ( bucket != 0 ) {
 389                         BucketNode* node = bucket_find( bucket, hash, key );
 390                         if ( node != 0 ) {
 391                                 return node->m_value.value;
 392                         }
 393                 }
 394         }
 395         size_increment();
 396         return bucket_insert( getBucket( hash ), node_create( hash, key, Value() ) )->m_value.value;
 397 }
 398 /// \brief Removes the value associated with \p key from the hash-table.
 399 void erase( const Key& key ){
 400         erase( find( key ) );
 401 }
 402 /// \brief Swaps the contents of the hash-table with \p other.
 403 void swap( HashTable& other ){
 404         std::swap( m_buckets, other.m_buckets );
 405         std::swap( m_bucketCount, other.m_bucketCount );
 406         std::swap( m_size, other.m_size );
 407         HashTableDetail::list_swap( m_list, other.m_list );
 408 }
 409 /// \brief Removes all values from the hash-table.
 410 void clear(){
 411         HashTable tmp;
 412         tmp.swap( *this );
 413 }
 414 };
 415
 416 #endif
 417
 418 #endif