COMMON: Add a size_type to HashMap.

1 files changed, 47 insertions, 44 deletions

diff --git a/common/hashmap.h b/common/hashmap.h
index 347ac1fd25..7cf54997e8 100644
--- a/common/hashmap.h
+++ b/common/hashmap.h
@@ -67,7 +67,7 @@ template<class T> class IteratorImpl;
 
 /**
  * HashMap<Key,Val> maps objects of type Key to objects of type Val.
- * For each used Key type, we need an "uint hashit(Key,uint)" function
+ * For each used Key type, we need an "size_type hashit(Key,size_type)" function
  * that computes a hash for the given Key object and returns it as an
  * an integer from 0 to hashsize-1, and also an "equality functor".
  * that returns true if if its two arguments are to be considered
@@ -80,6 +80,9 @@ template<class T> class IteratorImpl;
  */
 template<class Key, class Val, class HashFunc = Hash<Key>, class EqualFunc = EqualTo<Key> >
 class HashMap {
+public:
+	typedef uint size_type;
+
 private:
 
 	typedef HashMap<Key, Val, HashFunc, EqualFunc> HM_t;
@@ -111,9 +114,9 @@ private:
 #endif
 
 	Node **_storage;	///< hashtable of size arrsize.
-	uint _mask;		///< Capacity of the HashMap minus one; must be a power of two of minus one
-	uint _size;
-	uint _deleted; ///< Number of deleted elements (_dummyNodes)
+	size_type _mask;		///< Capacity of the HashMap minus one; must be a power of two of minus one
+	size_type _size;
+	size_type _deleted; ///< Number of deleted elements (_dummyNodes)
 
 	HashFunc _hash;
 	EqualFunc _equal;
@@ -146,9 +149,9 @@ private:
 	}
 
 	void assign(const HM_t &map);
-	uint lookup(const Key &key) const;
-	uint lookupAndCreateIfMissing(const Key &key);
-	void expandStorage(uint newCapacity);
+	size_type lookup(const Key &key) const;
+	size_type lookupAndCreateIfMissing(const Key &key);
+	void expandStorage(size_type newCapacity);
 
 #if !defined(__sgi) || defined(__GNUC__)
 	template<class T> friend class IteratorImpl;
@@ -168,11 +171,11 @@ private:
 	protected:
 		typedef const HashMap hashmap_t;
 
-		uint _idx;
+		size_type _idx;
 		hashmap_t *_hashmap;
 
 	protected:
-		IteratorImpl(uint idx, hashmap_t *hashmap) : _idx(idx), _hashmap(hashmap) {}
+		IteratorImpl(size_type idx, hashmap_t *hashmap) : _idx(idx), _hashmap(hashmap) {}
 
 		NodeType *deref() const {
 			assert(_hashmap != 0);
@@ -200,7 +203,7 @@ private:
 				_idx++;
 			} while (_idx <= _hashmap->_mask && (_hashmap->_storage[_idx] == 0 || _hashmap->_storage[_idx] == HASHMAP_DUMMY_NODE));
 			if (_idx > _hashmap->_mask)
-				_idx = (uint)-1;
+				_idx = (size_type)-1;
 
 			return *this;
 		}
@@ -247,41 +250,41 @@ public:
 	void erase(iterator entry);
 	void erase(const Key &key);
 
-	uint size() const { return _size; }
+	size_type size() const { return _size; }
 
 	iterator	begin() {
 		// Find and return the first non-empty entry
-		for (uint ctr = 0; ctr <= _mask; ++ctr) {
+		for (size_type ctr = 0; ctr <= _mask; ++ctr) {
 			if (_storage[ctr] && _storage[ctr] != HASHMAP_DUMMY_NODE)
 				return iterator(ctr, this);
 		}
 		return end();
 	}
 	iterator	end() {
-		return iterator((uint)-1, this);
+		return iterator((size_type)-1, this);
 	}
 
 	const_iterator	begin() const {
 		// Find and return the first non-empty entry
-		for (uint ctr = 0; ctr <= _mask; ++ctr) {
+		for (size_type ctr = 0; ctr <= _mask; ++ctr) {
 			if (_storage[ctr] && _storage[ctr] != HASHMAP_DUMMY_NODE)
 				return const_iterator(ctr, this);
 		}
 		return end();
 	}
 	const_iterator	end() const {
-		return const_iterator((uint)-1, this);
+		return const_iterator((size_type)-1, this);
 	}
 
 	iterator	find(const Key &key) {
-		uint ctr = lookup(key);
+		size_type ctr = lookup(key);
 		if (_storage[ctr])
 			return iterator(ctr, this);
 		return end();
 	}
 
 	const_iterator	find(const Key &key) const {
-		uint ctr = lookup(key);
+		size_type ctr = lookup(key);
 		if (_storage[ctr])
 			return const_iterator(ctr, this);
 		return end();
@@ -346,7 +349,7 @@ HashMap<Key, Val, HashFunc, EqualFunc>::HashMap(const HM_t &map) :
  */
 template<class Key, class Val, class HashFunc, class EqualFunc>
 HashMap<Key, Val, HashFunc, EqualFunc>::~HashMap() {
-	for (uint ctr = 0; ctr <= _mask; ++ctr)
+	for (size_type ctr = 0; ctr <= _mask; ++ctr)
 	  freeNode(_storage[ctr]);
 
 	delete[] _storage;
@@ -373,7 +376,7 @@ void HashMap<Key, Val, HashFunc, EqualFunc>::assign(const HM_t &map) {
 	// Simply clone the map given to us, one by one.
 	_size = 0;
 	_deleted = 0;
-	for (uint ctr = 0; ctr <= _mask; ++ctr) {
+	for (size_type ctr = 0; ctr <= _mask; ++ctr) {
 		if (map._storage[ctr] == HASHMAP_DUMMY_NODE) {
 			_storage[ctr] = HASHMAP_DUMMY_NODE;
 			_deleted++;
@@ -391,7 +394,7 @@ void HashMap<Key, Val, HashFunc, EqualFunc>::assign(const HM_t &map) {
 
 template<class Key, class Val, class HashFunc, class EqualFunc>
 void HashMap<Key, Val, HashFunc, EqualFunc>::clear(bool shrinkArray) {
-	for (uint ctr = 0; ctr <= _mask; ++ctr) {
+	for (size_type ctr = 0; ctr <= _mask; ++ctr) {
 		freeNode(_storage[ctr]);
 		_storage[ctr] = NULL;
 	}
@@ -414,13 +417,13 @@ void HashMap<Key, Val, HashFunc, EqualFunc>::clear(bool shrinkArray) {
 }
 
 template<class Key, class Val, class HashFunc, class EqualFunc>
-void HashMap<Key, Val, HashFunc, EqualFunc>::expandStorage(uint newCapacity) {
+void HashMap<Key, Val, HashFunc, EqualFunc>::expandStorage(size_type newCapacity) {
 	assert(newCapacity > _mask+1);
 
 #ifndef NDEBUG
-	const uint old_size = _size;
+	const size_type old_size = _size;
 #endif
-	const uint old_mask = _mask;
+	const size_type old_mask = _mask;
 	Node **old_storage = _storage;
 
 	// allocate a new array
@@ -432,7 +435,7 @@ void HashMap<Key, Val, HashFunc, EqualFunc>::expandStorage(uint newCapacity) {
 	memset(_storage, 0, newCapacity * sizeof(Node *));
 
 	// rehash all the old elements
-	for (uint ctr = 0; ctr <= old_mask; ++ctr) {
+	for (size_type ctr = 0; ctr <= old_mask; ++ctr) {
 		if (old_storage[ctr] == NULL || old_storage[ctr] == HASHMAP_DUMMY_NODE)
 			continue;
 
@@ -440,9 +443,9 @@ void HashMap<Key, Val, HashFunc, EqualFunc>::expandStorage(uint newCapacity) {
 		// Since we know that no key exists twice in the old table, we
 		// can do this slightly better than by calling lookup, since we
 		// don't have to call _equal().
-		const uint hash = _hash(old_storage[ctr]->_key);
-		uint idx = hash & _mask;
-		for (uint perturb = hash; _storage[idx] != NULL && _storage[idx] != HASHMAP_DUMMY_NODE; perturb >>= HASHMAP_PERTURB_SHIFT) {
+		const size_type hash = _hash(old_storage[ctr]->_key);
+		size_type idx = hash & _mask;
+		for (size_type perturb = hash; _storage[idx] != NULL && _storage[idx] != HASHMAP_DUMMY_NODE; perturb >>= HASHMAP_PERTURB_SHIFT) {
 			idx = (5 * idx + perturb + 1) & _mask;
 		}
 
@@ -460,10 +463,10 @@ void HashMap<Key, Val, HashFunc, EqualFunc>::expandStorage(uint newCapacity) {
 }
 
 template<class Key, class Val, class HashFunc, class EqualFunc>
-uint HashMap<Key, Val, HashFunc, EqualFunc>::lookup(const Key &key) const {
-	const uint hash = _hash(key);
-	uint ctr = hash & _mask;
-	for (uint perturb = hash; ; perturb >>= HASHMAP_PERTURB_SHIFT) {
+typename HashMap<Key, Val, HashFunc, EqualFunc>::size_type HashMap<Key, Val, HashFunc, EqualFunc>::lookup(const Key &key) const {
+	const size_type hash = _hash(key);
+	size_type ctr = hash & _mask;
+	for (size_type perturb = hash; ; perturb >>= HASHMAP_PERTURB_SHIFT) {
 		if (_storage[ctr] == NULL)
 			break;
 		if (_storage[ctr] == HASHMAP_DUMMY_NODE) {
@@ -491,13 +494,13 @@ uint HashMap<Key, Val, HashFunc, EqualFunc>::lookup(const Key &key) const {
 }
 
 template<class Key, class Val, class HashFunc, class EqualFunc>
-uint HashMap<Key, Val, HashFunc, EqualFunc>::lookupAndCreateIfMissing(const Key &key) {
-	const uint hash = _hash(key);
-	uint ctr = hash & _mask;
-	const uint NONE_FOUND = _mask + 1;
-	uint first_free = NONE_FOUND;
+typename HashMap<Key, Val, HashFunc, EqualFunc>::size_type HashMap<Key, Val, HashFunc, EqualFunc>::lookupAndCreateIfMissing(const Key &key) {
+	const size_type hash = _hash(key);
+	size_type ctr = hash & _mask;
+	const size_type NONE_FOUND = _mask + 1;
+	size_type first_free = NONE_FOUND;
 	bool found = false;
-	for (uint perturb = hash; ; perturb >>= HASHMAP_PERTURB_SHIFT) {
+	for (size_type perturb = hash; ; perturb >>= HASHMAP_PERTURB_SHIFT) {
 		if (_storage[ctr] == NULL)
 			break;
 		if (_storage[ctr] == HASHMAP_DUMMY_NODE) {
@@ -537,7 +540,7 @@ uint HashMap<Key, Val, HashFunc, EqualFunc>::lookupAndCreateIfMissing(const Key
 
 		// Keep the load factor below a certain threshold.
 		// Deleted nodes are also counted
-		uint capacity = _mask + 1;
+		size_type capacity = _mask + 1;
 		if ((_size + _deleted) * HASHMAP_LOADFACTOR_DENOMINATOR >
 		        capacity * HASHMAP_LOADFACTOR_NUMERATOR) {
 			capacity = capacity < 500 ? (capacity * 4) : (capacity * 2);
@@ -553,7 +556,7 @@ uint HashMap<Key, Val, HashFunc, EqualFunc>::lookupAndCreateIfMissing(const Key
 
 template<class Key, class Val, class HashFunc, class EqualFunc>
 bool HashMap<Key, Val, HashFunc, EqualFunc>::contains(const Key &key) const {
-	uint ctr = lookup(key);
+	size_type ctr = lookup(key);
 	return (_storage[ctr] != NULL);
 }
 
@@ -569,7 +572,7 @@ const Val &HashMap<Key, Val, HashFunc, EqualFunc>::operator[](const Key &key) co
 
 template<class Key, class Val, class HashFunc, class EqualFunc>
 Val &HashMap<Key, Val, HashFunc, EqualFunc>::getVal(const Key &key) {
-	uint ctr = lookupAndCreateIfMissing(key);
+	size_type ctr = lookupAndCreateIfMissing(key);
 	assert(_storage[ctr] != NULL);
 	return _storage[ctr]->_value;
 }
@@ -581,7 +584,7 @@ const Val &HashMap<Key, Val, HashFunc, EqualFunc>::getVal(const Key &key) const
 
 template<class Key, class Val, class HashFunc, class EqualFunc>
 const Val &HashMap<Key, Val, HashFunc, EqualFunc>::getVal(const Key &key, const Val &defaultVal) const {
-	uint ctr = lookup(key);
+	size_type ctr = lookup(key);
 	if (_storage[ctr] != NULL)
 		return _storage[ctr]->_value;
 	else
@@ -590,7 +593,7 @@ const Val &HashMap<Key, Val, HashFunc, EqualFunc>::getVal(const Key &key, const
 
 template<class Key, class Val, class HashFunc, class EqualFunc>
 void HashMap<Key, Val, HashFunc, EqualFunc>::setVal(const Key &key, const Val &val) {
-	uint ctr = lookupAndCreateIfMissing(key);
+	size_type ctr = lookupAndCreateIfMissing(key);
 	assert(_storage[ctr] != NULL);
 	_storage[ctr]->_value = val;
 }
@@ -599,7 +602,7 @@ template<class Key, class Val, class HashFunc, class EqualFunc>
 void HashMap<Key, Val, HashFunc, EqualFunc>::erase(iterator entry) {
 	// Check whether we have a valid iterator
 	assert(entry._hashmap == this);
-	const uint ctr = entry._idx;
+	const size_type ctr = entry._idx;
 	assert(ctr <= _mask);
 	Node * const node = _storage[ctr];
 	assert(node != NULL);
@@ -615,7 +618,7 @@ void HashMap<Key, Val, HashFunc, EqualFunc>::erase(iterator entry) {
 template<class Key, class Val, class HashFunc, class EqualFunc>
 void HashMap<Key, Val, HashFunc, EqualFunc>::erase(const Key &key) {
 
-	uint ctr = lookup(key);
+	size_type ctr = lookup(key);
 	if (_storage[ctr] == NULL)
 		return;