ginac/hash_map.h

   1 /** @file hash_map.h
   2  *
   3  *  Replacement for map<> using hash tables. */
   4
   5 /*
   6  *  GiNaC Copyright (C) 1999-2003 Johannes Gutenberg University Mainz, Germany
   7  *
   8  *  This program is free software; you can redistribute it and/or modify
   9  *  it under the terms of the GNU General Public License as published by
  10  *  the Free Software Foundation; either version 2 of the License, or
  11  *  (at your option) any later version.
  12  *
  13  *  This program is distributed in the hope that it will be useful,
  14  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  15  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  16  *  GNU General Public License for more details.
  17  *
  18  *  You should have received a copy of the GNU General Public License
  19  *  along with this program; if not, write to the Free Software
  20  *  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
  21  */
  22
  23 #ifndef __GINAC_HASH_MAP_H__
  24 #define __GINAC_HASH_MAP_H__
  25
  26 #include <list>
  27 #include <iterator>
  28 #include <algorithm>
  29 #include <functional>
  30 #include <utility>
  31
  32
  33 namespace GiNaC {
  34
  35 /*
  36  *  "Hashmap Light" - buckets only contain one value, quadratic probing,
  37  *  grows automatically
  38  */
  39
  40 namespace internal {
  41
  42 // List of prime numbers shamelessly stolen from GCC STL
  43 enum { num_primes = 29 };
  44
  45 static const unsigned long prime_list[num_primes] =
  46 {
  47         31ul,        53ul,         97ul,         193ul,       389ul,
  48         769ul,       1543ul,       3079ul,       6151ul,      12289ul,
  49         24593ul,     49157ul,      98317ul,      196613ul,    393241ul,
  50         786433ul,    1572869ul,    3145739ul,    6291469ul,   12582917ul,
  51         25165843ul,  50331653ul,   100663319ul,  201326611ul, 402653189ul,
  52         805306457ul, 1610612741ul, 3221225473ul, 4294967291ul
  53 };
  54
  55 inline unsigned long next_prime(unsigned long n)
  56 {
  57         const unsigned long *first = prime_list;
  58         const unsigned long *last = prime_list + num_primes;
  59         const unsigned long *pos = std::lower_bound(first, last, n);
  60         return pos == last ? *(last - 1) : *pos;
  61 }
  62
  63 } // namespace internal
  64
  65
  66 // Define default arguments
  67 template <typename T, template <class> class A = std::allocator>
  68 class exhashmap;
  69
  70
  71 /** Pair Associative Container with 'ex' objects as keys, that is implemented
  72  *  with a hash table and can be used as a replacement for map<> in many cases.
  73  *
  74  *  Differences to map<>:
  75  *   - no lower_bound()/upper_bound()
  76  *   - no "insert with a hint" insert(iterator, key_type)
  77  *   - no reverse iterators, no rbegin()/rend()
  78  *   - no operator<()
  79  *   - comparison functor is hardcoded to ex_is_less
  80  *   - bucket_count() returns the number of buckets allocated in the hash table
  81  *   - insert() and erase() invalidate all iterators
  82  *   - average complexity of find() is constant time, worst case is O(n) */
  83 template <typename T, template <class> class A>
  84 class exhashmap {
  85 public:
  86         static const unsigned min_num_buckets = 31; // must be prime
  87
  88         // Standard types
  89         typedef ex key_type;
  90         typedef T mapped_type;
  91         typedef std::pair<key_type, T> value_type;
  92         typedef ex_is_less key_compare;
  93         typedef ex_is_equal key_equal;
  94         typedef value_type & reference;
  95         typedef const value_type & const_reference;
  96         typedef value_type * pointer;
  97         typedef const value_type * const_pointer;
  98
  99 protected:
 100         // Private types
 101         enum bucket_state {
 102                 EMPTY,  ///< bucket empty (never used)
 103                 USED,   ///< bucket in use
 104                 ERASED  ///< bucket empty (element deleted), but may be part of a search chain
 105         };
 106         typedef std::pair<bucket_state, value_type> Bucket;
 107
 108 public:
 109         // More standard types
 110         typedef A<Bucket> allocator_type;
 111
 112 protected:
 113         // More private types
 114         typedef std::vector<Bucket, allocator_type> Table;
 115
 116         typedef typename Table::iterator table_iterator;
 117         typedef typename Table::const_iterator table_const_iterator;
 118
 119 public:
 120         // Iterators
 121         template <typename Pointer, typename Reference, class TableIterator>
 122         class exhashmap_iterator : public std::iterator<std::forward_iterator_tag, value_type, typename Table::difference_type, Pointer, Reference> {
 123         protected:
 124                 friend class exhashmap;
 125
 126         public:
 127                 exhashmap_iterator() {}
 128                 exhashmap_iterator(TableIterator t, TableIterator te)
 129                  : it(t), table_end(te) {}
 130
 131                 // Allow iterator to const_iterator conversion
 132                 template <typename P, typename R, class TI>
 133                 exhashmap_iterator(const exhashmap_iterator<P, R, TI> &other)
 134                  : it(other.get_it_()), table_end(other.get_table_end_()) {}
 135
 136                 typename exhashmap_iterator::reference operator*() const
 137                 {
 138                         return it->second;
 139                 }
 140
 141                 typename exhashmap_iterator::pointer operator->() const
 142                 {
 143                         return &(it->second);
 144                 }
 145
 146                 exhashmap_iterator &operator++()
 147                 {
 148                         increment();
 149                         return *this;
 150                 }
 151
 152                 exhashmap_iterator operator++(int)
 153                 {
 154                         exhashmap_iterator tmp = *this;
 155                         increment();
 156                         return tmp;
 157                 }
 158
 159                 template <typename P, typename R, class TI>
 160                 bool operator==(const exhashmap_iterator<P, R, TI> &other) const
 161                 {
 162                         return it == other.get_it_();
 163                 }
 164
 165                 template <typename P, typename R, class TI>
 166                 bool operator!=(const exhashmap_iterator<P, R, TI> &other) const
 167                 {
 168                         return it != other.get_it_();
 169                 }
 170
 171                 // Private access function
 172                 TableIterator get_it_() const { return it; }
 173                 TableIterator get_table_end_() const { return table_end; }
 174
 175         protected:
 176                 TableIterator it;        ///< Pointer to current bucket
 177                 TableIterator table_end; ///< Pointer to one-past-last bucket
 178
 179                 void increment()
 180                 {
 181                         if (it != table_end)
 182                                 ++it;
 183
 184                         // Skip empty and erased buckets
 185                         while (it != table_end && it->first != USED)
 186                                 ++it;
 187                 }
 188         };
 189
 190         typedef exhashmap_iterator<value_type*, value_type&, table_iterator> iterator;
 191         typedef exhashmap_iterator<const value_type*, const value_type&, table_const_iterator> const_iterator;
 192
 193         // More standard types
 194         typedef typename Table::size_type size_type;
 195         typedef typename Table::difference_type difference_type;
 196
 197         class value_compare : public std::binary_function<value_type, value_type, bool>, private key_compare {
 198                 friend class exhashmap;
 199         public:
 200                 bool operator()(const value_type &lhs, const value_type &rhs) const
 201                 {
 202                         return key_compare::operator()(lhs.first, rhs.first);
 203                 }
 204
 205                 bool operator()(const key_type &lhs, const value_type &rhs) const
 206                 {
 207                         return key_compare::operator()(lhs, rhs.first);
 208                 }
 209
 210                 bool operator()(const value_type &lhs, const key_type &rhs) const
 211                 {
 212                         return key_compare::operator()(lhs.first, rhs);
 213                 }
 214         };
 215
 216 protected:
 217         // Private data
 218         size_type num_entries; ///< Number of values stored in container (cached for faster operation of size())
 219         size_type num_buckets; ///< Number of buckets (= hashtab.size())
 220         Table hashtab;         ///< Vector of buckets, each bucket is kept sorted
 221
 222         /** Return index of key in hash table. */
 223         static size_type hash_index(const key_type &x, size_type nbuckets)
 224         {
 225                 return x.gethash() % nbuckets;
 226         }
 227
 228         static table_iterator find_bucket(const key_type &x, table_iterator tab, size_type nbuckets);
 229         static table_const_iterator find_bucket(const key_type &x, table_const_iterator tab, size_type nbuckets);
 230         static table_iterator find_bucket_for_insertion(const key_type &x, table_iterator tab, size_type nbuckets);
 231
 232         /** Return pointer to bucket corresponding to key (or first empty bucket). */
 233         table_iterator find_bucket(const key_type &x)
 234         {
 235                 return find_bucket(x, hashtab.begin(), num_buckets);
 236         }
 237
 238         /** Return pointer to bucket corresponding to key (or first empty bucket). */
 239         table_const_iterator find_bucket(const key_type &x) const
 240         {
 241                 return find_bucket(x, hashtab.begin(), num_buckets);
 242         }
 243
 244         /** Return pointer to bucket corresponding to key (or first empty or erased bucket). */
 245         table_iterator find_bucket_for_insertion(const key_type &x)
 246         {
 247                 return find_bucket_for_insertion(x, hashtab.begin(), num_buckets);
 248         }
 249
 250         /** Return number of entries above which the table will grow. */
 251         size_type hwm() const
 252         {
 253                 // Try to keep at least 25% of the buckets free
 254                 return num_buckets - (num_buckets >> 2);
 255         }
 256
 257         void grow();
 258
 259 public:
 260         // 23.3.1.1 Construct/copy/destroy
 261         exhashmap()
 262          : num_entries(0), num_buckets(min_num_buckets), hashtab(num_buckets, std::make_pair(EMPTY, std::make_pair(0, mapped_type()))) {}
 263
 264         explicit exhashmap(size_type nbuckets)
 265          : num_entries(0), num_buckets(internal::next_prime(nbuckets)), hashtab(num_buckets, std::make_pair(EMPTY, std::make_pair(0, mapped_type()))) {}
 266
 267         template <class InputIterator>
 268         exhashmap(InputIterator first, InputIterator last)
 269          : num_entries(0), num_buckets(min_num_buckets), hashtab(num_buckets, std::make_pair(EMPTY, std::make_pair(0, mapped_type())))
 270         {
 271                 insert(first, last);
 272         }
 273
 274         exhashmap &operator=(const exhashmap &other)
 275         {
 276                 exhashmap(other).swap(*this);
 277                 return *this;
 278         }
 279
 280         // Iterators
 281         iterator begin()
 282         {
 283                 // Find first used bucket
 284                 table_iterator bucket = hashtab.begin();
 285                 while (bucket != hashtab.end() && bucket->first != USED)
 286                         ++bucket;
 287                 return iterator(bucket, hashtab.end());
 288         }
 289
 290         const_iterator begin() const
 291         {
 292                 // Find first used bucket
 293                 table_const_iterator bucket = hashtab.begin();
 294                 while (bucket != hashtab.end() && bucket->first != USED)
 295                         ++bucket;
 296                 return const_iterator(bucket, hashtab.end());
 297         }
 298
 299         iterator end()
 300         {
 301                 return iterator(hashtab.end(), hashtab.end());
 302         }
 303
 304         const_iterator end() const
 305         {
 306                 return const_iterator(hashtab.end(), hashtab.end());
 307         }
 308
 309         // Capacity
 310         bool empty() const
 311         {
 312                 return num_entries == 0;
 313         }
 314
 315         size_type size() const
 316         {
 317                 return num_entries;
 318         }
 319
 320         size_type max_size() const
 321         {
 322                 return hashtab.max_size();
 323         }
 324
 325         size_type bucket_count() const
 326         {
 327                 return num_buckets;
 328         }
 329
 330         // 23.3.1.2 Element access
 331         T &operator[](const key_type &x)
 332         {
 333                 return insert(value_type(x, mapped_type())).first->second;
 334         }
 335
 336         // Modifiers
 337         std::pair<iterator, bool> insert(const value_type &x);
 338
 339         template <class InputIterator>
 340         void insert(InputIterator first, InputIterator last)
 341         {
 342                 for (; first != last; ++first)
 343                         insert(*first);
 344         }
 345
 346         void erase(iterator position)
 347         {
 348                 table_iterator bucket = position.get_it_();
 349                 bucket->first = ERASED;
 350                 bucket->second.first = 0;
 351                 --num_entries;
 352         }
 353
 354         size_type erase(const key_type &x);
 355
 356         void swap(exhashmap &other)
 357         {
 358                 hashtab.swap(other.hashtab);
 359                 std::swap(num_buckets, other.num_buckets);
 360                 std::swap(num_entries, other.num_entries);
 361         }
 362
 363         void clear();
 364
 365         // Observers
 366         key_compare key_comp() const
 367         {
 368                 return key_compare();
 369         }
 370
 371         value_compare value_comp() const
 372         {
 373                 return value_compare();
 374         }
 375
 376         // 23.3.1.3 Map operations
 377         iterator find(const key_type &x);
 378         const_iterator find(const key_type &x) const;
 379
 380         size_type count(const key_type &x) const
 381         {
 382                 return find(x) == end() ? 0 : 1;
 383         }
 384
 385         std::pair<iterator, iterator> equal_range(const key_type &x)
 386         {
 387                 iterator i = find(x);
 388                 if (i == end())
 389                         return std::make_pair(i, i);
 390                 else {
 391                         iterator j = ++i;
 392                         return std::make_pair(i, j);
 393                 }
 394         }
 395
 396         std::pair<const_iterator, const_iterator> equal_range(const key_type &x) const
 397         {
 398                 const_iterator i = find(x);
 399                 if (i == end())
 400                         return std::make_pair(i, i);
 401                 else {
 402                         const_iterator j = ++i;
 403                         return std::make_pair(i, j);
 404                 }
 405         }
 406
 407         friend bool operator==(const exhashmap &lhs, const exhashmap &rhs)
 408         {
 409                 if (lhs.num_entries != rhs.num_entries || lhs.num_buckets != rhs.num_buckets)
 410                         return false;
 411
 412                 // We can't compare the tables directly as the elements may be
 413                 // in different order due to the collision handling. We therefore
 414                 // look up each value from the lhs map in the rhs map separately.
 415                 for (const_iterator itl = lhs.begin(); itl != lhs.end(); ++itl) {
 416                         const_iterator itr = rhs.find(itl->first);
 417                         if (itr == rhs.end())
 418                                 return false;
 419                         if (itl->second != itr->second)
 420                                 return false;
 421                 }
 422                 return true;
 423         }
 424
 425         friend bool operator!=(const exhashmap &lhs, const exhashmap &rhs)
 426         {
 427                 return !(lhs == rhs);
 428         }
 429
 430         void dump() const
 431         {
 432                 std::clog << "num_entries = " << num_entries << std::endl;
 433                 std::clog << "num_buckets = " << num_buckets << std::endl;
 434                 size_type t = 0;
 435                 for (table_const_iterator it = hashtab.begin(); it != hashtab.end(); ++it, ++t) {
 436                         std::clog << " bucket " << t << ": ";
 437                         std::clog << (it->first == EMPTY ? "free" : (it->first == USED ? "used" : "erased")) << ", " << it->second.first << " -> " << it->second.second << std::endl;
 438                 }
 439         }
 440 };
 441
 442 /** Return pointer to bucket corresponding to key (or first empty bucket). */
 443 template <typename T, template <class> class A>
 444 inline typename exhashmap<T, A>::table_iterator exhashmap<T, A>::find_bucket(const key_type &x, table_iterator tab, size_type nbuckets)
 445 {
 446         // Quadratic probing
 447         size_type h = hash_index(x, nbuckets);
 448         size_type d = 1;
 449         table_iterator it = tab + h;
 450         while (it->first != EMPTY && !(it->first == USED && key_equal()(it->second.first, x))) {
 451                 h = (h + d) % nbuckets;
 452                 d += 2;
 453                 it = tab + h;
 454         }
 455         return it;
 456 }
 457
 458 /** Return pointer to bucket corresponding to key (or first empty bucket). */
 459 template <typename T, template <class> class A>
 460 inline typename exhashmap<T, A>::table_const_iterator exhashmap<T, A>::find_bucket(const key_type &x, table_const_iterator tab, size_type nbuckets)
 461 {
 462         // Quadratic probing
 463         size_type h = hash_index(x, nbuckets);
 464         size_type d = 1;
 465         table_const_iterator it = tab + h;
 466         while (it->first != EMPTY && !(it->first == USED && key_equal()(it->second.first, x))) {
 467                 h = (h + d) % nbuckets;
 468                 d += 2;
 469                 it = tab + h;
 470         }
 471         return it;
 472 }
 473
 474 /** Return pointer to bucket corresponding to key (or first empty or erased bucket). */
 475 template <typename T, template <class> class A>
 476 inline typename exhashmap<T, A>::table_iterator exhashmap<T, A>::find_bucket_for_insertion(const key_type &x, table_iterator tab, size_type nbuckets)
 477 {
 478         // Quadratic probing
 479         size_type h = hash_index(x, nbuckets);
 480         size_type d = 1;
 481         table_iterator it = tab + h;
 482         while (it->first != EMPTY && !key_equal()(it->second.first, x)) {
 483                 h = (h + d) % nbuckets;
 484                 d += 2;
 485                 it = tab + h;
 486         }
 487         return it;
 488 }
 489
 490 /** Grow hash table */
 491 template <typename T, template <class> class A>
 492 void exhashmap<T, A>::grow()
 493 {
 494         // Allocate new empty hash table
 495         size_type new_num_buckets = internal::next_prime(num_buckets + 1);
 496         Table new_hashtab;
 497         new_hashtab.resize(new_num_buckets);
 498         for (table_iterator it = new_hashtab.begin(); it != new_hashtab.end(); ++it)
 499                 it->first = EMPTY;
 500
 501         // Re-insert all elements into new table
 502         for (table_const_iterator it = hashtab.begin(); it != hashtab.end(); ++it) {
 503                 if (it->first == USED) {
 504                         table_iterator bucket = find_bucket(it->second.first, new_hashtab.begin(), new_num_buckets);
 505                         *bucket = *it;
 506                 }
 507         }
 508
 509         // Swap with the old table
 510         hashtab.swap(new_hashtab);
 511         num_buckets = new_num_buckets;
 512 }
 513
 514 template <typename T, template <class> class A>
 515 std::pair<typename exhashmap<T, A>::iterator, bool> exhashmap<T, A>::insert(const value_type &x)
 516 {
 517         table_iterator bucket = find_bucket_for_insertion(x.first);
 518         if (bucket->first == USED) {
 519                 // Value already in map
 520                 return std::make_pair(iterator(bucket, hashtab.end()), false);
 521         } else {
 522                 // Insert new value
 523                 bucket->first = USED;
 524                 bucket->second = x;
 525                 ++num_entries;
 526                 if (num_entries >= hwm()) {
 527                         grow();
 528                         bucket = find_bucket(x.first);
 529                 }
 530                 return std::make_pair(iterator(bucket, hashtab.end()), true);
 531         }
 532 }
 533
 534 template <typename T, template <class> class A>
 535 typename exhashmap<T, A>::size_type exhashmap<T, A>::erase(const key_type &x)
 536 {
 537         iterator i = find(x);
 538         if (i != end()) {
 539                 erase(i);
 540                 return 1;
 541         } else
 542                 return 0;
 543 }
 544
 545 template <typename T, template <class> class A>
 546 typename exhashmap<T, A>::iterator exhashmap<T, A>::find(const key_type &x)
 547 {
 548         table_iterator bucket = find_bucket(x);
 549         if (bucket->first == USED)
 550                 return iterator(bucket, hashtab.end());
 551         else
 552                 return end();
 553 }
 554
 555 template <typename T, template <class> class A>
 556 typename exhashmap<T, A>::const_iterator exhashmap<T, A>::find(const key_type &x) const
 557 {
 558         table_const_iterator bucket = find_bucket(x);
 559         if (bucket->first == USED)
 560                 return const_iterator(bucket, hashtab.end());
 561         else
 562                 return end();
 563 }
 564
 565 template <typename T, template <class> class A>
 566 void exhashmap<T, A>::clear()
 567 {
 568         for (table_iterator i = hashtab.begin(); i != hashtab.end(); ++i) {
 569                 i->first = EMPTY;
 570                 i->second.first = 0;
 571                 i->second.second = mapped_type();
 572         }
 573         num_entries = 0;
 574 }
 575
 576 } // namespace GiNaC
 577
 578
 579 // Specializations of Standard Library algorithms
 580 namespace std {
 581
 582 /** Specialization of std::swap() for exhashmap. */
 583 template <typename T, template <class> class A>
 584 inline void swap(GiNaC::exhashmap<T, A> &lhs, GiNaC::exhashmap<T, A> &rhs)
 585 {
 586         lhs.swap(rhs);
 587 }
 588
 589 } // namespace std
 590
 591 #endif // ndef __GINAC_HASH_MAP_H__