Happy New Year!
[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-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__