ginac/hash_map.h

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