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