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