From fe3af74fb8c8af4c8ab008c4788a7755b602db08 Mon Sep 17 00:00:00 2001 From: Richard Kreckel Date: Sun, 22 Sep 2019 13:19:00 +0200 Subject: [PATCH] Remove exhashmap class. Class exhashmap was a workaround for missing std::hash_map in the original C++98 standard. It was put in GiNaC because map was deemed too slow. Since C++11 there is std::unorderd_map, which is hash-based. To be able to use it, add specializations of std::hash and std:equal_to. --- check/CMakeLists.txt | 2 - check/Makefile.am | 8 - check/exam_hashmap.cpp | 293 --------------------- check/time_hashmap.cpp | 117 --------- doc/tutorial/ginac.texi | 41 +-- ginac/ex.h | 20 ++ ginac/hash_map.h | 570 +--------------------------------------- 7 files changed, 28 insertions(+), 1023 deletions(-) delete mode 100644 check/exam_hashmap.cpp delete mode 100644 check/time_hashmap.cpp diff --git a/check/CMakeLists.txt b/check/CMakeLists.txt index 58f9736b..c229a818 100644 --- a/check/CMakeLists.txt +++ b/check/CMakeLists.txt @@ -29,7 +29,6 @@ set(ginac_tests exam_clifford exam_archive exam_structure - exam_hashmap exam_misc exam_mod_gcd exam_cra @@ -44,7 +43,6 @@ set(ginac_timings time_gammaseries time_vandermonde time_toeplitz - time_hashmap time_lw_A time_lw_B time_lw_C diff --git a/check/Makefile.am b/check/Makefile.am index 0f7e035e..e8adab07 100644 --- a/check/Makefile.am +++ b/check/Makefile.am @@ -26,7 +26,6 @@ EXAMS = exam_paranoia \ exam_clifford \ exam_archive \ exam_structure \ - exam_hashmap \ exam_misc \ exam_mod_gcd \ check_mul_info \ @@ -41,7 +40,6 @@ TIMES = time_dennyfliegner \ time_gammaseries \ time_vandermonde \ time_toeplitz \ - time_hashmap \ time_lw_A \ time_lw_B \ time_lw_C \ @@ -146,9 +144,6 @@ exam_archive_LDADD = ../ginac/libginac.la exam_structure_SOURCES = exam_structure.cpp exam_structure_LDADD = ../ginac/libginac.la -exam_hashmap_SOURCES = exam_hashmap.cpp -exam_hashmap_LDADD = ../ginac/libginac.la - exam_misc_SOURCES = exam_misc.cpp exam_misc_LDADD = ../ginac/libginac.la @@ -176,9 +171,6 @@ time_vandermonde_LDADD = ../ginac/libginac.la time_toeplitz_SOURCES = time_toeplitz.cpp \ randomize_serials.cpp timer.cpp timer.h time_toeplitz_LDADD = ../ginac/libginac.la -time_hashmap_SOURCES = time_hashmap.cpp \ - randomize_serials.cpp timer.cpp timer.h -time_hashmap_LDADD = ../ginac/libginac.la time_lw_A_SOURCES = time_lw_A.cpp \ randomize_serials.cpp timer.cpp timer.h diff --git a/check/exam_hashmap.cpp b/check/exam_hashmap.cpp deleted file mode 100644 index ad8c1b2e..00000000 --- a/check/exam_hashmap.cpp +++ /dev/null @@ -1,293 +0,0 @@ -/** @file exam_hashmap.cpp - * - * Regression tests for the exhashmap<> container. */ - -/* - * GiNaC Copyright (C) 1999-2019 Johannes Gutenberg University Mainz, Germany - * - * This program is free software; you can redistribute it and/or modify - * it under the terms of the GNU General Public License as published by - * the Free Software Foundation; either version 2 of the License, or - * (at your option) any later version. - * - * This program is distributed in the hope that it will be useful, - * but WITHOUT ANY WARRANTY; without even the implied warranty of - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - * GNU General Public License for more details. - * - * You should have received a copy of the GNU General Public License - * along with this program; if not, write to the Free Software - * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA - */ - -#include "ginac.h" -using namespace GiNaC; - -#include -using namespace std; - -unsigned exam_hashmap() -{ - unsigned result = 0; - unsigned N = 100; - - cout << "examining hash maps" << flush; - - // Create empty container - exhashmap M1; - if (M1.size() != 0) { - clog << "Newly constructed container has size() != 0" << endl; - ++result; - } - if (!M1.empty()) { - clog << "Newly constructed container is not empty" << endl; - ++result; - } - - cout << '.' << flush; - - // Insert elements - for (unsigned i = 0; i < N; ++i) - M1.insert(make_pair(i, i)); - - if (M1.size() != N) { - clog << "After " << N << " insertions, size() returns " << M1.size() << " instead of " << N << endl; - ++result; - } - - for (unsigned i = 0; i < N; ++i) { - if (M1[i] != i) { - clog << "Lookup of key " << i << " in M1 didn't return correct value" << endl; - ++result; - break; - } - } - - if (M1.size() != N) { - clog << "After " << N << " lookups, size() returns " << M1.size() << " instead of " << N << endl; - ++result; - } - - cout << '.' << flush; - - // Test constructor from two iterators and operator== - exhashmap M2(M1.begin(), M1.end()); - if (M2.size() != M1.size()) { - clog << "Constructor from two iterators: size of destination container (" << M2.size() << ") not equal to size of source (" << M1.size() << ")" << endl; - ++result; - } - - for (unsigned i = 0; i < N; ++i) { - if (M2[i] != i) { - clog << "Lookup of key " << i << " in M2 didn't return correct value" << endl; - ++result; - break; - } - } - - if (M2 != M1) { - clog << "Copied container not equal to source" << endl; - ++result; - } - - cout << '.' << flush; - - // Test assignment operator - exhashmap M3; - M3 = M1; - if (M3.size() != N) { - clog << "Assignment operator: size of assigned container not equal to size of original" << endl; - ++result; - } - - for (unsigned i = 0; i < N; ++i) { - if (M3[i] != i) { - clog << "Lookup of key " << i << " in M3 didn't return correct value" << endl; - ++result; - break; - } - } - - cout << '.' << flush; - - // Test insert(it, it) - exhashmap M4; - M4.insert(M1.begin(), M1.end()); - - if (M4.size() != M1.size()) { - clog << "insert(it, it): size of destination container not equal to size of source" << endl; - ++result; - } - - for (unsigned i = 0; i < N; ++i) { - if (M4[i] != i) { - clog << "Lookup of key " << i << " in M4 didn't return correct value" << endl; - ++result; - break; - } - } - - cout << '.' << flush; - - // Test insert()/find() - symbol x("x"), y("y"); - exhashmap M5; - M5.insert(make_pair(x-2, 1)); - M5.insert(make_pair(sin(x+y), 2)); - M5.insert(make_pair(Pi, 3)); - M5.insert(make_pair(0, 4)); - M5.insert(make_pair(4*pow(x, y), 5)); - if (M5.size() != 5) { - clog << "After 5 insertions, size() returns " << M5.size() << " instead of 5" << endl; - ++result; - } - - exhashmap::const_iterator cit = M5.find(sin(x+y)); - if (cit == M5.end()) { - clog << "Lookup of sin(x+y) didn't find anything" << endl; - ++result; - } - if (!cit->first.is_equal(sin(x+y))) { - clog << "Lookup of sin(x+y) returned an incorrect iterator" << endl; - ++result; - } - if (cit->second != 2) { - clog << "Lookup of sin(x+y) returned wrong value" << endl; - ++result; - } - - cout << '.' << flush; - - // Test re-inserting insert() - pair::iterator, bool> pit = M5.insert(make_pair(sin(x+y), 42)); - if (pit.second) { - clog << "Reinsertion of sin(x+y) inserted a new value" << endl; - ++result; - } - if (!pit.first->first.is_equal(sin(x+y))) { - clog << "Reinsertion of sin(x+y) returned an incorrect iterator" << endl; - ++result; - } - if (pit.first->second != 2) { - clog << "Reinsertion of sin(x+y) changed the value" << endl; - ++result; - } - - cout << '.' << flush; - - // Test operator[] - unsigned v = M5[sin(x+y)]; - if (M5.size() != 5) { - clog << "operator[] with an existing key changed the container size" << endl; - ++result; - } - if (v != 2) { - clog << "operator[] with an existing key returned the wrong value" << endl; - ++result; - } - - v = M5[y+1]; - if (M5.size() != 6) { - clog << "operator[] with a new key didn't insert a new value" << endl; - ++result; - } - if (v != 0) { - clog << "operator[] with a new key returned the wrong value" << endl; - ++result; - } - - cout << '.' << flush; - - // Test erase() - exhashmap::iterator it = M5.find(y+1); - if (it == M5.end()) { - clog << "Key y+1 wasn't found" << endl; - ++result; - } - if (!it->first.is_equal(y+1)) { - clog << "find() returned an incorrect iterator" << endl; - ++result; - } - if (it->second != 0) { - clog << "find() returned an incorrect value" << endl; - ++result; - } - - M5.erase(it); - if (M5.size() != 5) { - clog << "erase(it) didn't reduce the size of the container" << endl; - ++result; - } - - it = M5.find(y+1); - if (it != M5.end()) { - clog << "Key was still found after erase()" << endl; - ++result; - } - - exhashmap::size_type n = M5.erase(Pi); - if (n != 1) { - clog << "erase(Pi) returned " << n << " instead of 1" << endl; - ++result; - } - if (M5.size() != 4) { - clog << "erase(Pi) didn't reduce the size of the container" << endl; - ++result; - } - - n = M5.erase(42); - if (n != 0) { - clog << "erase(42) returned " << n << " instead of 0" << endl; - ++result; - } - if (M5.size() != 4) { - clog << "erase(42) reduced the size of the container" << endl; - ++result; - } - - cout << '.' << flush; - - // Test swap() - exhashmap M6; - M6.swap(M1); - if (M6.size() != N) { - clog << "After swap, size() returns " << M6.size() << " instead of " << N << endl; - ++result; - } - if (M1.size() != 0) { - clog << "After swap with empty container, size() returns " << M1.size() << " instead of 0" << endl; - ++result; - } - - cout << '.' << flush; - - // Test clear() - M2.clear(); - if (M2.size() != 0) { - clog << "Size of cleared container is " << M5.size() << " instead of 0" << endl; - ++result; - } - - cout << '.' << flush; - - // Test count() - n = M5.count(Pi); - if (n != 0) { - clog << "count(Pi) returns " << n << " instead of 0" << endl; - ++result; - } - - n = M5.count(4*pow(x, y)); - if (n != 1) { - clog << "count(4*x^y) returns " << n << " instead of 1" << endl; - ++result; - } - cout << '.' << flush; - - return result; -} - -int main(int argc, char** argv) -{ - return exam_hashmap(); -} diff --git a/check/time_hashmap.cpp b/check/time_hashmap.cpp deleted file mode 100644 index 7657a477..00000000 --- a/check/time_hashmap.cpp +++ /dev/null @@ -1,117 +0,0 @@ -/** @file time_hashmap.cpp - * - * Timings for exhashmap<> operations. */ - -/* - * GiNaC Copyright (C) 1999-2019 Johannes Gutenberg University Mainz, Germany - * - * This program is free software; you can redistribute it and/or modify - * it under the terms of the GNU General Public License as published by - * the Free Software Foundation; either version 2 of the License, or - * (at your option) any later version. - * - * This program is distributed in the hope that it will be useful, - * but WITHOUT ANY WARRANTY; without even the implied warranty of - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - * GNU General Public License for more details. - * - * You should have received a copy of the GNU General Public License - * along with this program; if not, write to the Free Software - * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA - */ - -#include "ginac.h" -#include "timer.h" -using namespace GiNaC; - -#include -#include -using namespace std; - -template -static void run_timing(unsigned size, double &time_insert, double &time_find, double &time_erase) -{ - vector S; - T M; - timer t; - - S.reserve(size); - for (unsigned i=0; i sizes(s, s+sizeof(s)/sizeof(*s)); - - vector times_insert, times_find, times_erase; - - for (vector::const_iterator i = sizes.begin(); i != sizes.end(); ++i) { - double time_insert, time_find, time_erase; - - run_timing>(*i, time_insert, time_find, time_erase); - -// If you like, you can compare it with this: -// run_timing>(*i, time_insert, time_find, time_erase); - - times_insert.push_back(time_insert); - times_find.push_back(time_find); - times_erase.push_back(time_erase); - cout << '.' << flush; - } - - // print the report: - cout << endl << " size:\t"; - copy(sizes.begin(), sizes.end(), ostream_iterator(cout, "\t")); - cout << endl << " insert/s:\t"; - copy(times_insert.begin(), times_insert.end(), ostream_iterator(cout, "\t")); - cout << endl << " find/s:\t"; - copy(times_find.begin(), times_find.end(), ostream_iterator(cout, "\t")); - cout << endl << " erase/s:\t"; - copy(times_erase.begin(), times_erase.end(), ostream_iterator(cout, "\t")); - cout << endl; - - return result; -} - -extern void randomify_symbol_serials(); - -int main(int argc, char** argv) -{ - randomify_symbol_serials(); - cout << setprecision(2) << showpoint; - return time_hashmap(); -} diff --git a/doc/tutorial/ginac.texi b/doc/tutorial/ginac.texi index a3459585..b348b89b 100644 --- a/doc/tutorial/ginac.texi +++ b/doc/tutorial/ginac.texi @@ -717,7 +717,6 @@ meta-class for storing all mathematical objects. * Matrices:: Matrices. * Indexed objects:: Handling indexed quantities. * Non-commutative objects:: Algebras with non-commutative products. -* Hash maps:: A faster alternative to std::map<>. @end menu @@ -2987,7 +2986,7 @@ one form for @samp{F} and explicitly multiply it with a matrix representation of the metric tensor. -@node Non-commutative objects, Hash maps, Indexed objects, Basic concepts +@node Non-commutative objects, Methods and functions, Indexed objects, Basic concepts @c node-name, next, previous, up @section Non-commutative objects @@ -3771,43 +3770,7 @@ example: @end example -@node Hash maps, Methods and functions, Non-commutative objects, Basic concepts -@c node-name, next, previous, up -@section Hash Maps -@cindex hash maps -@cindex @code{exhashmap} (class) - -For your convenience, GiNaC offers the container template @code{exhashmap} -that can be used as a drop-in replacement for the STL -@code{std::map}, using hash tables to provide faster, -typically constant-time, element look-up than @code{map<>}. - -@code{exhashmap<>} supports all @code{map<>} members and operations, with the -following differences: - -@itemize @bullet -@item -no @code{lower_bound()} and @code{upper_bound()} methods -@item -no reverse iterators, no @code{rbegin()}/@code{rend()} -@item -no @code{operator<(exhashmap, exhashmap)} -@item -the comparison function object @code{key_compare} is hardcoded to -@code{ex_is_less} -@item -the constructor @code{exhashmap(size_t n)} allows specifying the minimum -initial hash table size (the actual table size after construction may be -larger than the specified value) -@item -the method @code{size_t bucket_count()} returns the current size of the hash -table -@item -@code{insert()} and @code{erase()} operations invalidate all iterators -@end itemize - - -@node Methods and functions, Information about expressions, Hash maps, Top +@node Methods and functions, Information about expressions, Non-commutative objects, Top @c node-name, next, previous, up @chapter Methods and functions @cindex polynomial diff --git a/ginac/ex.h b/ginac/ex.h index 606cd9d8..dd3cfe05 100644 --- a/ginac/ex.h +++ b/ginac/ex.h @@ -962,6 +962,26 @@ inline void swap(GiNaC::ex &a, GiNaC::ex &b) a.swap(b); } +/** Specialization of std::hash() for ex objects. */ +template<> +struct hash +{ + std::size_t operator()(const GiNaC::ex & e) const noexcept + { + return e.gethash(); + } +}; + +/** Specialization of std::equal_to() for ex objects. */ +template<> +struct equal_to +{ + bool operator()(const GiNaC::ex &e1, const GiNaC::ex &e2) const noexcept + { + return e1.is_equal(e2); + } +}; + } // namespace std #endif // ndef GINAC_EX_H diff --git a/ginac/hash_map.h b/ginac/hash_map.h index fb37d862..032489f9 100644 --- a/ginac/hash_map.h +++ b/ginac/hash_map.h @@ -23,574 +23,16 @@ #ifndef GINAC_HASH_MAP_H #define GINAC_HASH_MAP_H -#include -#include -#include -#include -#include +#include namespace GiNaC { -/* - * "Hashmap Light" - buckets only contain one value, quadratic probing, - * grows automatically - */ - -namespace internal { - -// List of prime numbers shamelessly stolen from GCC STL -enum { num_primes = 29 }; - -static const unsigned long prime_list[num_primes] = -{ - 31ul, 53ul, 97ul, 193ul, 389ul, - 769ul, 1543ul, 3079ul, 6151ul, 12289ul, - 24593ul, 49157ul, 98317ul, 196613ul, 393241ul, - 786433ul, 1572869ul, 3145739ul, 6291469ul, 12582917ul, - 25165843ul, 50331653ul, 100663319ul, 201326611ul, 402653189ul, - 805306457ul, 1610612741ul, 3221225473ul, 4294967291ul -}; - -inline unsigned long next_prime(unsigned long n) -{ - const unsigned long *first = prime_list; - const unsigned long *last = prime_list + num_primes; - const unsigned long *pos = std::lower_bound(first, last, n); - return pos == last ? *(last - 1) : *pos; -} - -} // namespace internal - - -// Define default arguments -template class A = std::allocator> -class exhashmap; - - -/** Pair Associative Container with 'ex' objects as keys, that is implemented - * with a hash table and can be used as a replacement for map<> in many cases. - * - * Differences to map<>: - * - no lower_bound()/upper_bound() - * - no reverse iterators, no rbegin()/rend() - * - no operator<() - * - comparison functor is hardcoded to ex_is_less - * - bucket_count() returns the number of buckets allocated in the hash table - * - insert() and erase() invalidate all iterators - * - average complexity of find() is constant time, worst case is O(n) */ -template class A> -class exhashmap { -public: - static const unsigned min_num_buckets = 31; // must be prime - - // Standard types - typedef ex key_type; - typedef T mapped_type; - typedef std::pair value_type; - typedef ex_is_less key_compare; - typedef ex_is_equal key_equal; - typedef value_type & reference; - typedef const value_type & const_reference; - typedef value_type * pointer; - typedef const value_type * const_pointer; - -protected: - // Private types - enum bucket_state { - EMPTY, ///< bucket empty (never used) - USED, ///< bucket in use - ERASED ///< bucket empty (element deleted), but may be part of a search chain - }; - typedef std::pair Bucket; - -public: - // More standard types - typedef A allocator_type; - -protected: - // More private types - typedef std::vector Table; - - typedef typename Table::iterator table_iterator; - typedef typename Table::const_iterator table_const_iterator; - -public: - // Iterators - template - class exhashmap_iterator : public std::iterator { - protected: - friend class exhashmap; - - public: - exhashmap_iterator() {} - exhashmap_iterator(TableIterator t, TableIterator te) - : it(t), table_end(te) {} - - // Allow iterator to const_iterator conversion - template - exhashmap_iterator(const exhashmap_iterator &other) - : it(other.get_it_()), table_end(other.get_table_end_()) {} - - typename exhashmap_iterator::reference operator*() const - { - return it->second; - } - - typename exhashmap_iterator::pointer operator->() const - { - return &(it->second); - } - - exhashmap_iterator &operator++() - { - increment(); - return *this; - } - - exhashmap_iterator operator++(int) - { - exhashmap_iterator tmp = *this; - increment(); - return tmp; - } - - template - bool operator==(const exhashmap_iterator &other) const - { - return it == other.get_it_(); - } - - template - bool operator!=(const exhashmap_iterator &other) const - { - return it != other.get_it_(); - } - - // Private access function - TableIterator get_it_() const { return it; } - TableIterator get_table_end_() const { return table_end; } - - protected: - TableIterator it; ///< Pointer to current bucket - TableIterator table_end; ///< Pointer to one-past-last bucket - - void increment() - { - if (it != table_end) - ++it; - - // Skip empty and erased buckets - while (it != table_end && it->first != USED) - ++it; - } - }; - - typedef exhashmap_iterator iterator; - typedef exhashmap_iterator const_iterator; - - // More standard types - typedef typename Table::size_type size_type; - typedef typename Table::difference_type difference_type; - - class value_compare : private key_compare { - friend class exhashmap; - public: - bool operator()(const value_type &lhs, const value_type &rhs) const - { - return key_compare::operator()(lhs.first, rhs.first); - } - - bool operator()(const key_type &lhs, const value_type &rhs) const - { - return key_compare::operator()(lhs, rhs.first); - } - - bool operator()(const value_type &lhs, const key_type &rhs) const - { - return key_compare::operator()(lhs.first, rhs); - } - }; - -protected: - // Private data - size_type num_entries; ///< Number of values stored in container (cached for faster operation of size()) - size_type num_buckets; ///< Number of buckets (= hashtab.size()) - Table hashtab; ///< Vector of buckets, each bucket is kept sorted - - /** Return index of key in hash table. */ - static size_type hash_index(const key_type &x, size_type nbuckets) - { - return x.gethash() % nbuckets; - } - - static table_iterator find_bucket(const key_type &x, table_iterator tab, size_type nbuckets); - static table_const_iterator find_bucket(const key_type &x, table_const_iterator tab, size_type nbuckets); - static table_iterator find_bucket_for_insertion(const key_type &x, table_iterator tab, size_type nbuckets); - - /** Return pointer to bucket corresponding to key (or first empty bucket). */ - table_iterator find_bucket(const key_type &x) - { - return find_bucket(x, hashtab.begin(), num_buckets); - } - - /** Return pointer to bucket corresponding to key (or first empty bucket). */ - table_const_iterator find_bucket(const key_type &x) const - { - return find_bucket(x, hashtab.begin(), num_buckets); - } - - /** Return pointer to bucket corresponding to key (or first empty or erased bucket). */ - table_iterator find_bucket_for_insertion(const key_type &x) - { - return find_bucket_for_insertion(x, hashtab.begin(), num_buckets); - } - - /** Return number of entries above which the table will grow. */ - size_type hwm() const - { - // Try to keep at least 25% of the buckets free - return num_buckets - (num_buckets >> 2); - } - - void grow(); - -public: - // 23.3.1.1 Construct/copy/destroy - exhashmap() - : num_entries(0), num_buckets(min_num_buckets), hashtab(num_buckets, std::make_pair(EMPTY, std::make_pair(0, mapped_type()))) {} - - explicit exhashmap(size_type nbuckets) - : num_entries(0), num_buckets(internal::next_prime(nbuckets)), hashtab(num_buckets, std::make_pair(EMPTY, std::make_pair(0, mapped_type()))) {} - - template - exhashmap(InputIterator first, InputIterator last) - : num_entries(0), num_buckets(min_num_buckets), hashtab(num_buckets, std::make_pair(EMPTY, std::make_pair(0, mapped_type()))) - { - insert(first, last); - } - - exhashmap &operator=(const exhashmap &other) - { - exhashmap(other).swap(*this); - return *this; - } - - // Iterators - iterator begin() - { - // Find first used bucket - table_iterator bucket = hashtab.begin(); - while (bucket != hashtab.end() && bucket->first != USED) - ++bucket; - return iterator(bucket, hashtab.end()); - } - - const_iterator begin() const - { - // Find first used bucket - table_const_iterator bucket = hashtab.begin(); - while (bucket != hashtab.end() && bucket->first != USED) - ++bucket; - return const_iterator(bucket, hashtab.end()); - } - - iterator end() - { - return iterator(hashtab.end(), hashtab.end()); - } - - const_iterator end() const - { - return const_iterator(hashtab.end(), hashtab.end()); - } - - // Capacity - bool empty() const - { - return num_entries == 0; - } - - size_type size() const - { - return num_entries; - } - - size_type max_size() const - { - return hashtab.max_size(); - } - - size_type bucket_count() const - { - return num_buckets; - } - - // 23.3.1.2 Element access - T &operator[](const key_type &x) - { - return insert(value_type(x, mapped_type())).first->second; - } - - // Modifiers - std::pair insert(const value_type &x); - - iterator insert(iterator pos, const value_type &x) - { - return insert(x).first; - } - - template - void insert(InputIterator first, InputIterator last) - { - for (; first != last; ++first) - insert(*first); - } - - void erase(iterator position) - { - table_iterator bucket = position.get_it_(); - bucket->first = ERASED; - bucket->second.first = 0; - --num_entries; - } - - size_type erase(const key_type &x); - - void swap(exhashmap &other) - { - hashtab.swap(other.hashtab); - std::swap(num_buckets, other.num_buckets); - std::swap(num_entries, other.num_entries); - } - - void clear(); - - // Observers - key_compare key_comp() const - { - return key_compare(); - } - - value_compare value_comp() const - { - return value_compare(); - } - - // 23.3.1.3 Map operations - iterator find(const key_type &x); - const_iterator find(const key_type &x) const; - - size_type count(const key_type &x) const - { - return find(x) == end() ? 0 : 1; - } - - std::pair equal_range(const key_type &x) - { - iterator i = find(x); - if (i == end()) - return std::make_pair(i, i); - else { - iterator j = ++i; - return std::make_pair(i, j); - } - } - - std::pair equal_range(const key_type &x) const - { - const_iterator i = find(x); - if (i == end()) - return std::make_pair(i, i); - else { - const_iterator j = ++i; - return std::make_pair(i, j); - } - } - - friend bool operator==(const exhashmap &lhs, const exhashmap &rhs) - { - if (lhs.num_entries != rhs.num_entries || lhs.num_buckets != rhs.num_buckets) - return false; - - // We can't compare the tables directly as the elements may be - // in different order due to the collision handling. We therefore - // look up each value from the lhs map in the rhs map separately. - for (const_iterator itl = lhs.begin(); itl != lhs.end(); ++itl) { - const_iterator itr = rhs.find(itl->first); - if (itr == rhs.end()) - return false; - if (itl->second != itr->second) - return false; - } - return true; - } - - friend bool operator!=(const exhashmap &lhs, const exhashmap &rhs) - { - return !(lhs == rhs); - } - -#if 0 - void dump() const - { - std::clog << "num_entries = " << num_entries << std::endl; - std::clog << "num_buckets = " << num_buckets << std::endl; - size_type t = 0; - for (table_const_iterator it = hashtab.begin(); it != hashtab.end(); ++it, ++t) { - std::clog << " bucket " << t << ": "; - std::clog << (it->first == EMPTY ? "free" : (it->first == USED ? "used" : "erased")) << ", " << it->second.first << " -> " << it->second.second << std::endl; - } - } -#endif -}; - -/** Return pointer to bucket corresponding to key (or first empty bucket). */ -template class A> -inline typename exhashmap::table_iterator exhashmap::find_bucket(const key_type &x, table_iterator tab, size_type nbuckets) -{ - // Quadratic probing - size_type h = hash_index(x, nbuckets); - size_type d = 1; - table_iterator it = tab + h; - while (it->first != EMPTY && !(it->first == USED && key_equal()(it->second.first, x))) { - h = (h + d) % nbuckets; - d += 2; - it = tab + h; - } - return it; -} - -/** Return pointer to bucket corresponding to key (or first empty bucket). */ -template class A> -inline typename exhashmap::table_const_iterator exhashmap::find_bucket(const key_type &x, table_const_iterator tab, size_type nbuckets) -{ - // Quadratic probing - size_type h = hash_index(x, nbuckets); - size_type d = 1; - table_const_iterator it = tab + h; - while (it->first != EMPTY && !(it->first == USED && key_equal()(it->second.first, x))) { - h = (h + d) % nbuckets; - d += 2; - it = tab + h; - } - return it; -} - -/** Return pointer to bucket corresponding to key (or first empty or erased bucket). */ -template class A> -inline typename exhashmap::table_iterator exhashmap::find_bucket_for_insertion(const key_type &x, table_iterator tab, size_type nbuckets) -{ - // Quadratic probing - size_type h = hash_index(x, nbuckets); - size_type d = 1; - table_iterator it = tab + h; - while (it->first != EMPTY && !key_equal()(it->second.first, x)) { - h = (h + d) % nbuckets; - d += 2; - it = tab + h; - } - return it; -} - -/** Grow hash table */ -template class A> -void exhashmap::grow() -{ - // Allocate new empty hash table - size_type new_num_buckets = internal::next_prime(num_buckets + 1); - Table new_hashtab; - new_hashtab.resize(new_num_buckets); - for (table_iterator it = new_hashtab.begin(); it != new_hashtab.end(); ++it) - it->first = EMPTY; - - // Re-insert all elements into new table - for (table_const_iterator it = hashtab.begin(); it != hashtab.end(); ++it) { - if (it->first == USED) { - table_iterator bucket = find_bucket(it->second.first, new_hashtab.begin(), new_num_buckets); - *bucket = *it; - } - } - - // Swap with the old table - hashtab.swap(new_hashtab); - num_buckets = new_num_buckets; -} - -template class A> -std::pair::iterator, bool> exhashmap::insert(const value_type &x) -{ - table_iterator bucket = find_bucket_for_insertion(x.first); - if (bucket->first == USED) { - // Value already in map - return std::make_pair(iterator(bucket, hashtab.end()), false); - } else { - // Insert new value - bucket->first = USED; - bucket->second = x; - ++num_entries; - if (num_entries >= hwm()) { - grow(); - bucket = find_bucket(x.first); - } - return std::make_pair(iterator(bucket, hashtab.end()), true); - } -} - -template class A> -typename exhashmap::size_type exhashmap::erase(const key_type &x) -{ - iterator i = find(x); - if (i != end()) { - erase(i); - return 1; - } else - return 0; -} - -template class A> -typename exhashmap::iterator exhashmap::find(const key_type &x) -{ - table_iterator bucket = find_bucket(x); - if (bucket->first == USED) - return iterator(bucket, hashtab.end()); - else - return end(); -} - -template class A> -typename exhashmap::const_iterator exhashmap::find(const key_type &x) const -{ - table_const_iterator bucket = find_bucket(x); - if (bucket->first == USED) - return const_iterator(bucket, hashtab.end()); - else - return end(); -} - -template class A> -void exhashmap::clear() -{ - for (table_iterator i = hashtab.begin(); i != hashtab.end(); ++i) { - i->first = EMPTY; - i->second.first = 0; - i->second.second = mapped_type(); - } - num_entries = 0; -} +template , + class KeyEqual = std::equal_to, + class Allocator = std::allocator>> +using exhashmap = std::unordered_map; } // namespace GiNaC - -// Specializations of Standard Library algorithms -namespace std { - -/** Specialization of std::swap() for exhashmap. */ -template class A> -inline void swap(GiNaC::exhashmap &lhs, GiNaC::exhashmap &rhs) -{ - lhs.swap(rhs); -} - -} // namespace std - #endif // ndef GINAC_HASH_MAP_H -- 2.44.0