Committed patch #1929274 "HashMap: Iterator rework".

svn-id: r31356

1 files changed, 19 insertions, 81 deletions

diff --git a/common/hashmap.h b/common/hashmap.h
index 3f028d69ed..fb1de38fd1 100644
--- a/common/hashmap.h
+++ b/common/hashmap.h
@@ -150,106 +150,44 @@ public:
 	int lookupAndCreateIfMissing(const Key &key);
 	void expand_array(uint newsize);
 
-	class Iterator;
-	class ConstIterator;
-	friend class Iterator;
-	friend class ConstIterator;
+	template<class T> friend class IteratorImpl;
 
 	/**
 	 * Simple HashMap iterator implementation.
 	 */
-	class Iterator {
-	protected:
-		typedef const HashMap hashmap_t;
+	template<class NodeType>
+	class IteratorImpl {
 		friend class HashMap;
-
-		// Allow ConstIterator to read member vars, so that Iterators can be converted to ConstIterator
-		friend class HashMap::ConstIterator;
-
-		uint _idx;
-		hashmap_t *_hashmap;
-
-	protected:
-		Iterator(uint idx, hashmap_t *hashmap) : _idx(idx), _hashmap(hashmap) {}
-
-		Node *deref() const {
-			assert(_hashmap != 0);
-			assert(_idx < _hashmap->_arrsize);
-			Node *node = _hashmap->_arr[_idx];
-			assert(node != 0);
-			return node;
-		}
-
-	public:
-		Iterator() : _idx(0), _hashmap(0) {}
-
-		Node &operator *() const { return *deref(); }
-		Node *operator->() const { return deref(); }
-
-		bool operator ==(const Iterator &iter) const { return _idx == iter._idx && _hashmap == iter._hashmap; }
-		bool operator !=(const Iterator &iter) const { return !(*this == iter); }
-
-		Iterator &operator ++() {
-			assert(_hashmap);
-			do {
-				_idx++;
-			} while (_idx < _hashmap->_arrsize && _hashmap->_arr[_idx] == 0);
-			if (_idx >= _hashmap->_arrsize)
-				_idx = (uint)-1;
-
-			return *this;
-		}
-
-		Iterator operator ++(int) {
-			Iterator old = *this;
-			operator ++();
-			return old;
-		}
-	};
-
-	/**
-	 * Simple HashMap const iterator implementation.
-	 * This is almost completely identical to the normal iterator class, only
-	 * with some const keywords added here and there, plus a conversion
-	 * operator which makes it possible to transparently convert iterators to
-	 * const iterators.
-	 * It is sadly not really possible to reduce this code duplication using
-	 * template, unless one is willing to accept various warnings on certain
-	 * compilers. Note that many (most? all?) implementations of the standard
-	 * C++ library use a similar approach for their implementations.
-	 */
-	class ConstIterator {
+		template<class T> friend class IteratorImpl;
 	protected:
 		typedef const HashMap hashmap_t;
-		friend class HashMap;
 
 		uint _idx;
 		hashmap_t *_hashmap;
 
 	protected:
-		ConstIterator(uint idx, hashmap_t *hashmap) : _idx(idx), _hashmap(hashmap) {}
+		IteratorImpl(uint idx, hashmap_t *hashmap) : _idx(idx), _hashmap(hashmap) {}
 
-		const Node *deref() const {
+		NodeType *deref() const {
 			assert(_hashmap != 0);
 			assert(_idx < _hashmap->_arrsize);
-			const Node *node = _hashmap->_arr[_idx];
+			Node *node = _hashmap->_arr[_idx];
 			assert(node != 0);
 			return node;
 		}
 
 	public:
-		ConstIterator() : _idx(0), _hashmap(0) {}
-
-		// Converting a non-const iterator to a const one is allowed
-		ConstIterator(const Iterator &iter) : _idx(iter._idx), _hashmap(iter._hashmap) {}
+		IteratorImpl() : _idx(0), _hashmap(0) {}
+		template<class T>
+		IteratorImpl(const IteratorImpl<T> &c) : _idx(c._idx), _hashmap(c._hashmap) {}
 
-		const Node &operator *() const { return *deref(); }
-		const Node *operator->() const { return deref(); }
+		NodeType &operator *() const { return *deref(); }
+		NodeType *operator->() const { return deref(); }
 
-		bool operator ==(const ConstIterator &iter) const { return _idx == iter._idx && _hashmap == iter._hashmap; }
-		bool operator !=(const ConstIterator &iter) const { return !(*this == iter); }
+		bool operator ==(const IteratorImpl &iter) const { return _idx == iter._idx && _hashmap == iter._hashmap; }
+		bool operator !=(const IteratorImpl &iter) const { return !(*this == iter); }
 
-		ConstIterator &operator ++() {
+		IteratorImpl &operator ++() {
 			assert(_hashmap);
 			do {
 				_idx++;
@@ -260,16 +198,16 @@ public:
 			return *this;
 		}
 
-		ConstIterator operator ++(int) {
-			ConstIterator old = *this;
+		IteratorImpl operator ++(int) {
+			IteratorImpl old = *this;
 			operator ++();
 			return old;
 		}
 	};
 
 public:
-	typedef Iterator iterator;
-	typedef ConstIterator const_iterator;
+	typedef IteratorImpl<Node> iterator;
+	typedef IteratorImpl<const Node> const_iterator;
 
 	HashMap();
 	HashMap(const HM_t& map);