839b8238f8402c78ded1c0c4dea3bce19e278d0a
[ginac.git] / 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         /** Empty all buckets in the table. */
258         void empty_all_buckets()
259         {
260                 for (table_iterator i = hashtab.begin(); i != hashtab.end(); ++i)
261                         i->first = EMPTY;
262         }
263
264         void grow();
265
266 public:
267         // 23.3.1.1 Construct/copy/destroy
268         exhashmap()
269          : num_entries(0), num_buckets(min_num_buckets), hashtab(num_buckets, std::make_pair(EMPTY, std::make_pair(0, mapped_type()))) {}
270
271         explicit exhashmap(size_type nbuckets)
272          : num_entries(0), num_buckets(internal::next_prime(nbuckets)), hashtab(num_buckets, std::make_pair(EMPTY, std::make_pair(0, mapped_type()))) {}
273
274         template <class InputIterator>
275         exhashmap(InputIterator first, InputIterator last)
276          : num_entries(0), num_buckets(min_num_buckets), hashtab(num_buckets, std::make_pair(EMPTY, std::make_pair(0, mapped_type())))
277         {
278                 insert(first, last);
279         }
280
281         exhashmap &operator=(const exhashmap &other)
282         {
283                 exhashmap(other).swap(*this);
284                 return *this;
285         }
286
287         // Iterators
288         iterator begin()
289         {
290                 // Find first used bucket
291                 table_iterator bucket = hashtab.begin();
292                 while (bucket != hashtab.end() && bucket->first != USED)
293                         ++bucket;
294                 return iterator(bucket, hashtab.end());
295         }
296
297         const_iterator begin() const
298         {
299                 // Find first used bucket
300                 table_const_iterator bucket = hashtab.begin();
301                 while (bucket != hashtab.end() && bucket->first != USED)
302                         ++bucket;
303                 return const_iterator(bucket, hashtab.end());
304         }
305
306         iterator end()
307         {
308                 return iterator(hashtab.end(), hashtab.end());
309         }
310
311         const_iterator end() const
312         {
313                 return const_iterator(hashtab.end(), hashtab.end());
314         }
315
316         // Capacity
317         bool empty() const
318         {
319                 return num_entries == 0;
320         }
321
322         size_type size() const
323         {
324                 return num_entries;
325         }
326
327         size_type max_size() const
328         {
329                 return hashtab.max_size();
330         }
331
332         size_type bucket_count() const
333         {
334                 return num_buckets;
335         }
336
337         // 23.3.1.2 Element access
338         T &operator[](const key_type &x)
339         {
340                 return insert(value_type(x, mapped_type())).first->second;
341         }
342
343         // Modifiers
344         std::pair<iterator, bool> insert(const value_type &x);
345
346         template <class InputIterator>
347         void insert(InputIterator first, InputIterator last)
348         {
349                 for (; first != last; ++first)
350                         insert(*first);
351         }
352
353         void erase(iterator position)
354         {
355                 table_iterator bucket = position.get_it_();
356                 bucket->first = ERASED;
357                 bucket->second.first = 0;
358                 --num_entries;
359         }
360
361         size_type erase(const key_type &x);
362
363         void swap(exhashmap &other)
364         {
365                 hashtab.swap(other.hashtab);
366                 std::swap(num_buckets, other.num_buckets);
367                 std::swap(num_entries, other.num_entries);
368         }
369
370         void clear();
371
372         // Observers
373         key_compare key_comp() const
374         {
375                 return key_compare();
376         }
377
378         value_compare value_comp() const
379         {
380                 return value_compare();
381         }
382
383         // 23.3.1.3 Map operations
384         iterator find(const key_type &x);
385         const_iterator find(const key_type &x) const;
386
387         size_type count(const key_type &x) const
388         {
389                 return find(x) == end() ? 0 : 1;
390         }
391
392         std::pair<iterator, iterator> equal_range(const key_type &x)
393         {
394                 iterator i = find(x);
395                 if (i == end())
396                         return std::make_pair(i, i);
397                 else {
398                         iterator j = ++i;
399                         return std::make_pair(i, j);
400                 }
401         }
402
403         std::pair<const_iterator, const_iterator> equal_range(const key_type &x) const
404         {
405                 const_iterator i = find(x);
406                 if (i == end())
407                         return std::make_pair(i, i);
408                 else {
409                         const_iterator j = ++i;
410                         return std::make_pair(i, j);
411                 }
412         }
413
414         friend bool operator==(const exhashmap &lhs, const exhashmap &rhs)
415         {
416                 if (lhs.num_entries != rhs.num_entries || lhs.num_buckets != rhs.num_buckets)
417                         return false;
418
419                 // We can't compare the tables directly as the elements may be
420                 // in different order due to the collision handling. We therefore
421                 // look up each value from the lhs map in the rhs map separately.
422                 for (const_iterator itl = lhs.begin(); itl != lhs.end(); ++itl) {
423                         const_iterator itr = rhs.find(itl->first);
424                         if (itr == rhs.end())
425                                 return false;
426                         if (itl->second != itr->second)
427                                 return false;
428                 }
429                 return true;
430         }
431
432         friend bool operator!=(const exhashmap &lhs, const exhashmap &rhs)
433         {
434                 return !(lhs == rhs);
435         }
436
437         void dump() const
438         {
439                 std::clog << "num_entries = " << num_entries << std::endl;
440                 std::clog << "num_buckets = " << num_buckets << std::endl;
441                 size_type t = 0;
442                 for (table_const_iterator it = hashtab.begin(); it != hashtab.end(); ++it, ++t) {
443                         std::clog << " bucket " << t << ": ";
444                         std::clog << (it->first == EMPTY ? "free" : (it->first == USED ? "used" : "erased")) << ", " << it->second.first << " -> " << it->second.second << std::endl;
445                 }
446         }
447 };
448
449 /** Return pointer to bucket corresponding to key (or first empty bucket). */
450 template <typename T, template <class> class A>
451 inline typename exhashmap<T, A>::table_iterator exhashmap<T, A>::find_bucket(const key_type &x, table_iterator tab, size_type nbuckets)
452 {
453         // Quadratic probing
454         size_type h = hash_index(x, nbuckets);
455         size_type d = 1;
456         table_iterator it = tab + h;
457         while (it->first != EMPTY && !(it->first == USED && key_equal()(it->second.first, x))) {
458                 h = (h + d) % nbuckets;
459                 d += 2;
460                 it = tab + h;
461         }
462         return it;
463 }
464
465 /** Return pointer to bucket corresponding to key (or first empty bucket). */
466 template <typename T, template <class> class A>
467 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 {
469         // Quadratic probing
470         size_type h = hash_index(x, nbuckets);
471         size_type d = 1;
472         table_const_iterator it = tab + h;
473         while (it->first != EMPTY && !(it->first == USED && key_equal()(it->second.first, x))) {
474                 h = (h + d) % nbuckets;
475                 d += 2;
476                 it = tab + h;
477         }
478         return it;
479 }
480
481 /** Return pointer to bucket corresponding to key (or first empty or erased bucket). */
482 template <typename T, template <class> class A>
483 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 {
485         // Quadratic probing
486         size_type h = hash_index(x, nbuckets);
487         size_type d = 1;
488         table_iterator it = tab + h;
489         while (it->first != EMPTY && !key_equal()(it->second.first, x)) {
490                 h = (h + d) % nbuckets;
491                 d += 2;
492                 it = tab + h;
493         }
494         return it;
495 }
496
497 /** Grow hash table */
498 template <typename T, template <class> class A>
499 void exhashmap<T, A>::grow()
500 {
501         // Allocate new empty hash table
502         size_type new_num_buckets = internal::next_prime(num_buckets + 1);
503         Table new_hashtab;
504         new_hashtab.resize(new_num_buckets);
505         for (table_iterator it = new_hashtab.begin(); it != new_hashtab.end(); ++it)
506                 it->first = EMPTY;
507
508         // Re-insert all elements into new table
509         for (table_const_iterator it = hashtab.begin(); it != hashtab.end(); ++it) {
510                 if (it->first == USED) {
511                         table_iterator bucket = find_bucket(it->second.first, new_hashtab.begin(), new_num_buckets);
512                         *bucket = *it;
513                 }
514         }
515
516         // Swap with the old table
517         hashtab.swap(new_hashtab);
518         num_buckets = new_num_buckets;
519 }
520
521 template <typename T, template <class> class A>
522 std::pair<typename exhashmap<T, A>::iterator, bool> exhashmap<T, A>::insert(const value_type &x)
523 {
524         table_iterator bucket = find_bucket_for_insertion(x.first);
525         if (bucket->first == USED) {
526                 // Value already in map
527                 return std::make_pair(iterator(bucket, hashtab.end()), false);
528         } else {
529                 // Insert new value
530                 bucket->first = USED;
531                 bucket->second = x;
532                 ++num_entries;
533                 if (num_entries >= hwm()) {
534                         grow();
535                         bucket = find_bucket(x.first);
536                 }
537                 return std::make_pair(iterator(bucket, hashtab.end()), true);
538         }
539 }
540
541 template <typename T, template <class> class A>
542 typename exhashmap<T, A>::size_type exhashmap<T, A>::erase(const key_type &x)
543 {
544         iterator i = find(x);
545         if (i != end()) {
546                 erase(i);
547                 return 1;
548         } else
549                 return 0;
550 }
551
552 template <typename T, template <class> class A>
553 typename exhashmap<T, A>::iterator exhashmap<T, A>::find(const key_type &x)
554 {
555         table_iterator bucket = find_bucket(x);
556         if (bucket->first == USED)
557                 return iterator(bucket, hashtab.end());
558         else
559                 return end();
560 }
561
562 template <typename T, template <class> class A>
563 typename exhashmap<T, A>::const_iterator exhashmap<T, A>::find(const key_type &x) const
564 {
565         table_const_iterator bucket = find_bucket(x);
566         if (bucket->first == USED)
567                 return const_iterator(bucket, hashtab.end());
568         else
569                 return end();
570 }
571
572 template <typename T, template <class> class A>
573 void exhashmap<T, A>::clear()
574 {
575         for (table_iterator i = hashtab.begin(); i != hashtab.end(); ++i) {
576                 i->first = EMPTY;
577                 i->second.first = 0;
578                 i->second.second = mapped_type();
579         }
580         num_entries = 0;
581 }
582
583 } // namespace GiNaC
584
585
586 // Specializations of Standard Library algorithms
587 namespace std {
588
589 /** Specialization of std::swap() for exhashmap. */
590 template <typename T, template <class> class A>
591 inline void swap(GiNaC::exhashmap<T, A> &lhs, GiNaC::exhashmap<T, A> &rhs)
592 {
593         lhs.swap(rhs);
594 }
595
596 } // namespace std
597
598 #endif // ndef __GINAC_HASH_MAP_H__