ginac/hash_map.h

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