* Replacement for map<> using hash tables. */
/*
- * GiNaC Copyright (C) 1999-2003 Johannes Gutenberg University Mainz, Germany
+ * GiNaC Copyright (C) 1999-2011 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
*
* 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., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
*/
-#ifndef __GINAC_HASH_MAP_H__
-#define __GINAC_HASH_MAP_H__
+#ifndef GINAC_HASH_MAP_H
+#define GINAC_HASH_MAP_H
-#include <list>
-#include <iterator>
#include <algorithm>
#include <functional>
+#include <iterator>
+#include <list>
#include <utility>
-
namespace GiNaC {
/*
*
* Differences to map<>:
* - no lower_bound()/upper_bound()
- * - no "insert with a hint" insert(iterator, key_type)
* - no reverse iterators, no rbegin()/rend()
* - no operator<()
* - comparison functor is hardcoded to ex_is_less
template <typename T, template <class> class A>
class exhashmap {
public:
- static const unsigned min_num_buckets = 5; // must be prime
+ static const unsigned min_num_buckets = 31; // must be prime
// Standard types
typedef ex key_type;
protected:
// Private data
- Table hashtab; ///< Vector of buckets, each bucket is kept sorted
- size_type num_buckets; ///< Number of buckets (= hashtab.size())
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 num_buckets - (num_buckets >> 2);
}
- /** Empty all buckets in the table. */
- void empty_all_buckets()
- {
- for (table_iterator i = hashtab.begin(); i != hashtab.end(); ++i)
- i->first = EMPTY;
- }
-
void grow();
public:
// 23.3.1.1 Construct/copy/destroy
- exhashmap() : num_buckets(min_num_buckets), num_entries(0)
- {
- hashtab.resize(num_buckets);
- empty_all_buckets();
- }
+ 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.resize(num_buckets);
- empty_all_buckets();
- }
+ 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 <class InputIterator>
- exhashmap(InputIterator first, InputIterator last) : num_buckets(min_num_buckets), num_entries(0)
+ 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())))
{
- hashtab.resize(num_buckets);
- empty_all_buckets();
insert(first, last);
}
// Modifiers
std::pair<iterator, bool> insert(const value_type &x);
+ iterator insert(iterator pos, const value_type &x)
+ {
+ return insert(x).first;
+ }
+
template <class InputIterator>
void insert(InputIterator first, InputIterator last)
{
return !(lhs == rhs);
}
+#if 0
void dump() const
{
std::clog << "num_entries = " << num_entries << std::endl;
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). */
for (table_iterator i = hashtab.begin(); i != hashtab.end(); ++i) {
i->first = EMPTY;
i->second.first = 0;
- i->second.second = T();
+ i->second.second = mapped_type();
}
num_entries = 0;
}
} // namespace std
-#endif // ndef __GINAC_HASH_MAP_H__
+#endif // ndef GINAC_HASH_MAP_H