X-Git-Url: https://www.ginac.de/ginac.git//ginac.git?p=ginac.git;a=blobdiff_plain;f=ginac%2Fhash_map.h;h=5e9895ae387dd9861cbe34905cc123b7c5f32fa2;hp=3673f69050868586e0acfe0212ad8eab0c277f25;hb=e5eeee53d814cedc12cd725e76b0eb87859cdd77;hpb=b38e42e8ed1d985129d88dd53792e643796fc4d8

diff --git a/ginac/hash_map.h b/ginac/hash_map.h
index 3673f690..5e9895ae 100644
--- a/ginac/hash_map.h
+++ b/ginac/hash_map.h
@@ -3,7 +3,7 @@
  *  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
@@ -17,19 +17,18 @@
  *
  *  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 {
 
 /*
@@ -73,7 +72,6 @@ class exhashmap;
  *
  *  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
@@ -83,7 +81,7 @@ class exhashmap;
 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;
@@ -215,9 +213,9 @@ public:
 
 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)
@@ -254,35 +252,20 @@ protected:
 		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);
 	}
 
@@ -351,6 +334,11 @@ public:
 	// 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)
 	{
@@ -442,6 +430,7 @@ public:
 		return !(lhs == rhs);
 	}
 
+#if 0
 	void dump() const
 	{
 		std::clog << "num_entries = " << num_entries << std::endl;
@@ -452,6 +441,7 @@ public:
 			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). */
@@ -583,7 +573,7 @@ void exhashmap<T, A>::clear()
 	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;
 }
@@ -603,4 +593,4 @@ inline void swap(GiNaC::exhashmap<T, A> &lhs, GiNaC::exhashmap<T, A> &rhs)
 
 } // namespace std
 
-#endif // ndef __GINAC_HASH_MAP_H__
+#endif // ndef GINAC_HASH_MAP_H