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