3 * Replacement for map<> using hash tables. */
6 * GiNaC Copyright (C) 1999-2005 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., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
23 #ifndef __GINAC_HASH_MAP_H__
24 #define __GINAC_HASH_MAP_H__
36 * "Hashmap Light" - buckets only contain one value, quadratic probing,
42 // List of prime numbers shamelessly stolen from GCC STL
43 enum { num_primes = 29 };
45 static const unsigned long prime_list[num_primes] =
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
55 inline unsigned long next_prime(unsigned long n)
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;
63 } // namespace internal
66 // Define default arguments
67 template <typename T, template <class> class A = std::allocator>
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.
74 * Differences to map<>:
75 * - no lower_bound()/upper_bound()
76 * - no reverse iterators, no rbegin()/rend()
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>
85 static const unsigned min_num_buckets = 31; // must be prime
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;
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
105 typedef std::pair<bucket_state, value_type> Bucket;
108 // More standard types
109 typedef A<Bucket> allocator_type;
112 // More private types
113 typedef std::vector<Bucket, allocator_type> Table;
115 typedef typename Table::iterator table_iterator;
116 typedef typename Table::const_iterator table_const_iterator;
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> {
123 friend class exhashmap;
126 exhashmap_iterator() {}
127 exhashmap_iterator(TableIterator t, TableIterator te)
128 : it(t), table_end(te) {}
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_()) {}
135 typename exhashmap_iterator::reference operator*() const
140 typename exhashmap_iterator::pointer operator->() const
142 return &(it->second);
145 exhashmap_iterator &operator++()
151 exhashmap_iterator operator++(int)
153 exhashmap_iterator tmp = *this;
158 template <typename P, typename R, class TI>
159 bool operator==(const exhashmap_iterator<P, R, TI> &other) const
161 return it == other.get_it_();
164 template <typename P, typename R, class TI>
165 bool operator!=(const exhashmap_iterator<P, R, TI> &other) const
167 return it != other.get_it_();
170 // Private access function
171 TableIterator get_it_() const { return it; }
172 TableIterator get_table_end_() const { return table_end; }
175 TableIterator it; ///< Pointer to current bucket
176 TableIterator table_end; ///< Pointer to one-past-last bucket
183 // Skip empty and erased buckets
184 while (it != table_end && it->first != USED)
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;
192 // More standard types
193 typedef typename Table::size_type size_type;
194 typedef typename Table::difference_type difference_type;
196 class value_compare : public std::binary_function<value_type, value_type, bool>, private key_compare {
197 friend class exhashmap;
199 bool operator()(const value_type &lhs, const value_type &rhs) const
201 return key_compare::operator()(lhs.first, rhs.first);
204 bool operator()(const key_type &lhs, const value_type &rhs) const
206 return key_compare::operator()(lhs, rhs.first);
209 bool operator()(const value_type &lhs, const key_type &rhs) const
211 return key_compare::operator()(lhs.first, rhs);
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
221 /** Return index of key in hash table. */
222 static size_type hash_index(const key_type &x, size_type nbuckets)
224 return x.gethash() % nbuckets;
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);
231 /** Return pointer to bucket corresponding to key (or first empty bucket). */
232 table_iterator find_bucket(const key_type &x)
234 return find_bucket(x, hashtab.begin(), num_buckets);
237 /** Return pointer to bucket corresponding to key (or first empty bucket). */
238 table_const_iterator find_bucket(const key_type &x) const
240 return find_bucket(x, hashtab.begin(), num_buckets);
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)
246 return find_bucket_for_insertion(x, hashtab.begin(), num_buckets);
249 /** Return number of entries above which the table will grow. */
250 size_type hwm() const
252 // Try to keep at least 25% of the buckets free
253 return num_buckets - (num_buckets >> 2);
259 // 23.3.1.1 Construct/copy/destroy
261 : num_entries(0), num_buckets(min_num_buckets), hashtab(num_buckets, std::make_pair(EMPTY, std::make_pair(0, mapped_type()))) {}
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()))) {}
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())))
273 exhashmap &operator=(const exhashmap &other)
275 exhashmap(other).swap(*this);
282 // Find first used bucket
283 table_iterator bucket = hashtab.begin();
284 while (bucket != hashtab.end() && bucket->first != USED)
286 return iterator(bucket, hashtab.end());
289 const_iterator begin() const
291 // Find first used bucket
292 table_const_iterator bucket = hashtab.begin();
293 while (bucket != hashtab.end() && bucket->first != USED)
295 return const_iterator(bucket, hashtab.end());
300 return iterator(hashtab.end(), hashtab.end());
303 const_iterator end() const
305 return const_iterator(hashtab.end(), hashtab.end());
311 return num_entries == 0;
314 size_type size() const
319 size_type max_size() const
321 return hashtab.max_size();
324 size_type bucket_count() const
329 // 23.3.1.2 Element access
330 T &operator[](const key_type &x)
332 return insert(value_type(x, mapped_type())).first->second;
336 std::pair<iterator, bool> insert(const value_type &x);
338 iterator insert(iterator pos, const value_type &x)
340 return insert(x).first;
343 template <class InputIterator>
344 void insert(InputIterator first, InputIterator last)
346 for (; first != last; ++first)
350 void erase(iterator position)
352 table_iterator bucket = position.get_it_();
353 bucket->first = ERASED;
354 bucket->second.first = 0;
358 size_type erase(const key_type &x);
360 void swap(exhashmap &other)
362 hashtab.swap(other.hashtab);
363 std::swap(num_buckets, other.num_buckets);
364 std::swap(num_entries, other.num_entries);
370 key_compare key_comp() const
372 return key_compare();
375 value_compare value_comp() const
377 return value_compare();
380 // 23.3.1.3 Map operations
381 iterator find(const key_type &x);
382 const_iterator find(const key_type &x) const;
384 size_type count(const key_type &x) const
386 return find(x) == end() ? 0 : 1;
389 std::pair<iterator, iterator> equal_range(const key_type &x)
391 iterator i = find(x);
393 return std::make_pair(i, i);
396 return std::make_pair(i, j);
400 std::pair<const_iterator, const_iterator> equal_range(const key_type &x) const
402 const_iterator i = find(x);
404 return std::make_pair(i, i);
406 const_iterator j = ++i;
407 return std::make_pair(i, j);
411 friend bool operator==(const exhashmap &lhs, const exhashmap &rhs)
413 if (lhs.num_entries != rhs.num_entries || lhs.num_buckets != rhs.num_buckets)
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())
423 if (itl->second != itr->second)
429 friend bool operator!=(const exhashmap &lhs, const exhashmap &rhs)
431 return !(lhs == rhs);
437 std::clog << "num_entries = " << num_entries << std::endl;
438 std::clog << "num_buckets = " << num_buckets << std::endl;
440 for (table_const_iterator it = hashtab.begin(); it != hashtab.end(); ++it, ++t) {
441 std::clog << " bucket " << t << ": ";
442 std::clog << (it->first == EMPTY ? "free" : (it->first == USED ? "used" : "erased")) << ", " << it->second.first << " -> " << it->second.second << std::endl;
448 /** Return pointer to bucket corresponding to key (or first empty bucket). */
449 template <typename T, template <class> class A>
450 inline typename exhashmap<T, A>::table_iterator exhashmap<T, A>::find_bucket(const key_type &x, table_iterator tab, size_type nbuckets)
453 size_type h = hash_index(x, nbuckets);
455 table_iterator it = tab + h;
456 while (it->first != EMPTY && !(it->first == USED && key_equal()(it->second.first, x))) {
457 h = (h + d) % nbuckets;
464 /** Return pointer to bucket corresponding to key (or first empty bucket). */
465 template <typename T, template <class> class A>
466 inline typename exhashmap<T, A>::table_const_iterator exhashmap<T, A>::find_bucket(const key_type &x, table_const_iterator tab, size_type nbuckets)
469 size_type h = hash_index(x, nbuckets);
471 table_const_iterator it = tab + h;
472 while (it->first != EMPTY && !(it->first == USED && key_equal()(it->second.first, x))) {
473 h = (h + d) % nbuckets;
480 /** Return pointer to bucket corresponding to key (or first empty or erased bucket). */
481 template <typename T, template <class> class A>
482 inline typename exhashmap<T, A>::table_iterator exhashmap<T, A>::find_bucket_for_insertion(const key_type &x, table_iterator tab, size_type nbuckets)
485 size_type h = hash_index(x, nbuckets);
487 table_iterator it = tab + h;
488 while (it->first != EMPTY && !key_equal()(it->second.first, x)) {
489 h = (h + d) % nbuckets;
496 /** Grow hash table */
497 template <typename T, template <class> class A>
498 void exhashmap<T, A>::grow()
500 // Allocate new empty hash table
501 size_type new_num_buckets = internal::next_prime(num_buckets + 1);
503 new_hashtab.resize(new_num_buckets);
504 for (table_iterator it = new_hashtab.begin(); it != new_hashtab.end(); ++it)
507 // Re-insert all elements into new table
508 for (table_const_iterator it = hashtab.begin(); it != hashtab.end(); ++it) {
509 if (it->first == USED) {
510 table_iterator bucket = find_bucket(it->second.first, new_hashtab.begin(), new_num_buckets);
515 // Swap with the old table
516 hashtab.swap(new_hashtab);
517 num_buckets = new_num_buckets;
520 template <typename T, template <class> class A>
521 std::pair<typename exhashmap<T, A>::iterator, bool> exhashmap<T, A>::insert(const value_type &x)
523 table_iterator bucket = find_bucket_for_insertion(x.first);
524 if (bucket->first == USED) {
525 // Value already in map
526 return std::make_pair(iterator(bucket, hashtab.end()), false);
529 bucket->first = USED;
532 if (num_entries >= hwm()) {
534 bucket = find_bucket(x.first);
536 return std::make_pair(iterator(bucket, hashtab.end()), true);
540 template <typename T, template <class> class A>
541 typename exhashmap<T, A>::size_type exhashmap<T, A>::erase(const key_type &x)
543 iterator i = find(x);
551 template <typename T, template <class> class A>
552 typename exhashmap<T, A>::iterator exhashmap<T, A>::find(const key_type &x)
554 table_iterator bucket = find_bucket(x);
555 if (bucket->first == USED)
556 return iterator(bucket, hashtab.end());
561 template <typename T, template <class> class A>
562 typename exhashmap<T, A>::const_iterator exhashmap<T, A>::find(const key_type &x) const
564 table_const_iterator bucket = find_bucket(x);
565 if (bucket->first == USED)
566 return const_iterator(bucket, hashtab.end());
571 template <typename T, template <class> class A>
572 void exhashmap<T, A>::clear()
574 for (table_iterator i = hashtab.begin(); i != hashtab.end(); ++i) {
577 i->second.second = mapped_type();
585 // Specializations of Standard Library algorithms
588 /** Specialization of std::swap() for exhashmap. */
589 template <typename T, template <class> class A>
590 inline void swap(GiNaC::exhashmap<T, A> &lhs, GiNaC::exhashmap<T, A> &rhs)
597 #endif // ndef __GINAC_HASH_MAP_H__