3 * Replacement for map<> using hash tables. */
6 * GiNaC Copyright (C) 1999-2015 Johannes Gutenberg University Mainz, Germany
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.
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.
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
23 #ifndef GINAC_HASH_MAP_H
24 #define GINAC_HASH_MAP_H
35 * "Hashmap Light" - buckets only contain one value, quadratic probing,
41 // List of prime numbers shamelessly stolen from GCC STL
42 enum { num_primes = 29 };
44 static const unsigned long prime_list[num_primes] =
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
54 inline unsigned long next_prime(unsigned long n)
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;
62 } // namespace internal
65 // Define default arguments
66 template <typename T, template <class> class A = std::allocator>
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.
73 * Differences to map<>:
74 * - no lower_bound()/upper_bound()
75 * - no reverse iterators, no rbegin()/rend()
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>
84 static const unsigned min_num_buckets = 31; // must be prime
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;
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
104 typedef std::pair<bucket_state, value_type> Bucket;
107 // More standard types
108 typedef A<Bucket> allocator_type;
111 // More private types
112 typedef std::vector<Bucket, allocator_type> Table;
114 typedef typename Table::iterator table_iterator;
115 typedef typename Table::const_iterator table_const_iterator;
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> {
122 friend class exhashmap;
125 exhashmap_iterator() {}
126 exhashmap_iterator(TableIterator t, TableIterator te)
127 : it(t), table_end(te) {}
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_()) {}
134 typename exhashmap_iterator::reference operator*() const
139 typename exhashmap_iterator::pointer operator->() const
141 return &(it->second);
144 exhashmap_iterator &operator++()
150 exhashmap_iterator operator++(int)
152 exhashmap_iterator tmp = *this;
157 template <typename P, typename R, class TI>
158 bool operator==(const exhashmap_iterator<P, R, TI> &other) const
160 return it == other.get_it_();
163 template <typename P, typename R, class TI>
164 bool operator!=(const exhashmap_iterator<P, R, TI> &other) const
166 return it != other.get_it_();
169 // Private access function
170 TableIterator get_it_() const { return it; }
171 TableIterator get_table_end_() const { return table_end; }
174 TableIterator it; ///< Pointer to current bucket
175 TableIterator table_end; ///< Pointer to one-past-last bucket
182 // Skip empty and erased buckets
183 while (it != table_end && it->first != USED)
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;
191 // More standard types
192 typedef typename Table::size_type size_type;
193 typedef typename Table::difference_type difference_type;
195 class value_compare : public std::binary_function<value_type, value_type, bool>, private key_compare {
196 friend class exhashmap;
198 bool operator()(const value_type &lhs, const value_type &rhs) const
200 return key_compare::operator()(lhs.first, rhs.first);
203 bool operator()(const key_type &lhs, const value_type &rhs) const
205 return key_compare::operator()(lhs, rhs.first);
208 bool operator()(const value_type &lhs, const key_type &rhs) const
210 return key_compare::operator()(lhs.first, rhs);
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
220 /** Return index of key in hash table. */
221 static size_type hash_index(const key_type &x, size_type nbuckets)
223 return x.gethash() % nbuckets;
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);
230 /** Return pointer to bucket corresponding to key (or first empty bucket). */
231 table_iterator find_bucket(const key_type &x)
233 return find_bucket(x, hashtab.begin(), num_buckets);
236 /** Return pointer to bucket corresponding to key (or first empty bucket). */
237 table_const_iterator find_bucket(const key_type &x) const
239 return find_bucket(x, hashtab.begin(), num_buckets);
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)
245 return find_bucket_for_insertion(x, hashtab.begin(), num_buckets);
248 /** Return number of entries above which the table will grow. */
249 size_type hwm() const
251 // Try to keep at least 25% of the buckets free
252 return num_buckets - (num_buckets >> 2);
258 // 23.3.1.1 Construct/copy/destroy
260 : num_entries(0), num_buckets(min_num_buckets), hashtab(num_buckets, std::make_pair(EMPTY, std::make_pair(0, mapped_type()))) {}
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()))) {}
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())))
272 exhashmap &operator=(const exhashmap &other)
274 exhashmap(other).swap(*this);
281 // Find first used bucket
282 table_iterator bucket = hashtab.begin();
283 while (bucket != hashtab.end() && bucket->first != USED)
285 return iterator(bucket, hashtab.end());
288 const_iterator begin() const
290 // Find first used bucket
291 table_const_iterator bucket = hashtab.begin();
292 while (bucket != hashtab.end() && bucket->first != USED)
294 return const_iterator(bucket, hashtab.end());
299 return iterator(hashtab.end(), hashtab.end());
302 const_iterator end() const
304 return const_iterator(hashtab.end(), hashtab.end());
310 return num_entries == 0;
313 size_type size() const
318 size_type max_size() const
320 return hashtab.max_size();
323 size_type bucket_count() const
328 // 23.3.1.2 Element access
329 T &operator[](const key_type &x)
331 return insert(value_type(x, mapped_type())).first->second;
335 std::pair<iterator, bool> insert(const value_type &x);
337 iterator insert(iterator pos, const value_type &x)
339 return insert(x).first;
342 template <class InputIterator>
343 void insert(InputIterator first, InputIterator last)
345 for (; first != last; ++first)
349 void erase(iterator position)
351 table_iterator bucket = position.get_it_();
352 bucket->first = ERASED;
353 bucket->second.first = 0;
357 size_type erase(const key_type &x);
359 void swap(exhashmap &other)
361 hashtab.swap(other.hashtab);
362 std::swap(num_buckets, other.num_buckets);
363 std::swap(num_entries, other.num_entries);
369 key_compare key_comp() const
371 return key_compare();
374 value_compare value_comp() const
376 return value_compare();
379 // 23.3.1.3 Map operations
380 iterator find(const key_type &x);
381 const_iterator find(const key_type &x) const;
383 size_type count(const key_type &x) const
385 return find(x) == end() ? 0 : 1;
388 std::pair<iterator, iterator> equal_range(const key_type &x)
390 iterator i = find(x);
392 return std::make_pair(i, i);
395 return std::make_pair(i, j);
399 std::pair<const_iterator, const_iterator> equal_range(const key_type &x) const
401 const_iterator i = find(x);
403 return std::make_pair(i, i);
405 const_iterator j = ++i;
406 return std::make_pair(i, j);
410 friend bool operator==(const exhashmap &lhs, const exhashmap &rhs)
412 if (lhs.num_entries != rhs.num_entries || lhs.num_buckets != rhs.num_buckets)
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())
422 if (itl->second != itr->second)
428 friend bool operator!=(const exhashmap &lhs, const exhashmap &rhs)
430 return !(lhs == rhs);
436 std::clog << "num_entries = " << num_entries << std::endl;
437 std::clog << "num_buckets = " << num_buckets << std::endl;
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;
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)
452 size_type h = hash_index(x, nbuckets);
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;
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)
468 size_type h = hash_index(x, nbuckets);
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;
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)
484 size_type h = hash_index(x, nbuckets);
486 table_iterator it = tab + h;
487 while (it->first != EMPTY && !key_equal()(it->second.first, x)) {
488 h = (h + d) % nbuckets;
495 /** Grow hash table */
496 template <typename T, template <class> class A>
497 void exhashmap<T, A>::grow()
499 // Allocate new empty hash table
500 size_type new_num_buckets = internal::next_prime(num_buckets + 1);
502 new_hashtab.resize(new_num_buckets);
503 for (table_iterator it = new_hashtab.begin(); it != new_hashtab.end(); ++it)
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);
514 // Swap with the old table
515 hashtab.swap(new_hashtab);
516 num_buckets = new_num_buckets;
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)
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);
528 bucket->first = USED;
531 if (num_entries >= hwm()) {
533 bucket = find_bucket(x.first);
535 return std::make_pair(iterator(bucket, hashtab.end()), true);
539 template <typename T, template <class> class A>
540 typename exhashmap<T, A>::size_type exhashmap<T, A>::erase(const key_type &x)
542 iterator i = find(x);
550 template <typename T, template <class> class A>
551 typename exhashmap<T, A>::iterator exhashmap<T, A>::find(const key_type &x)
553 table_iterator bucket = find_bucket(x);
554 if (bucket->first == USED)
555 return iterator(bucket, hashtab.end());
560 template <typename T, template <class> class A>
561 typename exhashmap<T, A>::const_iterator exhashmap<T, A>::find(const key_type &x) const
563 table_const_iterator bucket = find_bucket(x);
564 if (bucket->first == USED)
565 return const_iterator(bucket, hashtab.end());
570 template <typename T, template <class> class A>
571 void exhashmap<T, A>::clear()
573 for (table_iterator i = hashtab.begin(); i != hashtab.end(); ++i) {
576 i->second.second = mapped_type();
584 // Specializations of Standard Library algorithms
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)
596 #endif // ndef GINAC_HASH_MAP_H