[Scummvm-cvs-logs] SF.net SVN: scummvm: [25967] scummvm/trunk/common/hashmap.h

fingolfin at users.sourceforge.net fingolfin at users.sourceforge.net
Sun Mar 4 10:58:05 CET 2007


Revision: 25967
          http://scummvm.svn.sourceforge.net/scummvm/?rev=25967&view=rev
Author:   fingolfin
Date:     2007-03-04 01:58:04 -0800 (Sun, 04 Mar 2007)

Log Message:
-----------
Some HashMap cleanup:
* Removed the odd return value of method erase()
* Stopped erase() from leaking (oops!)
* Added a (paranoia) consistency check to assign()

Modified Paths:
--------------
    scummvm/trunk/common/hashmap.h

Modified: scummvm/trunk/common/hashmap.h
===================================================================
--- scummvm/trunk/common/hashmap.h	2007-03-04 09:41:58 UTC (rev 25966)
+++ scummvm/trunk/common/hashmap.h	2007-03-04 09:58:04 UTC (rev 25967)
@@ -174,7 +174,7 @@
 
 	void clear(bool shrinkArray = 0);
 
-	size_t erase(const Key &key);
+	void erase(const Key &key);
 
 	uint size() const { return _nele; }
 
@@ -264,11 +264,15 @@
 	memset(_arr, 0, _arrsize * sizeof(Node *));
 
 	// Simply clone the map given to us, one by one.
-	_nele = map._nele;
-	for (uint ctr = 0; ctr < _arrsize; ++ctr)
+	_nele = 0;
+	for (uint ctr = 0; ctr < _arrsize; ++ctr) {
 		if (map._arr[ctr] != NULL) {
 			_arr[ctr] = new Node(*map._arr[ctr]);
+			_nele++;
 		}
+	}
+	// Perform a sanity check (to help track down hashmap corruption)
+	assert(_nele == map._nele);
 }
 
 
@@ -296,21 +300,19 @@
 template <class Key, class Val, class HashFunc, class EqualFunc>
 void HashMap<Key, Val, HashFunc, EqualFunc>::expand_array(uint newsize) {
 	assert(newsize > _arrsize);
-	Node **old_arr;
-	uint old_arrsize, old_nele, ctr, dex;
+	uint ctr, dex;
 
-	old_nele = _nele;
-	old_arr = _arr;
-	old_arrsize = _arrsize;
+	const uint old_nele = _nele;
+	const uint old_arrsize = _arrsize;
+	Node **old_arr = _arr;
 
 	// allocate a new array 
+	_nele = 0;
 	_arrsize = newsize;
 	_arr = new Node *[_arrsize];
 	assert(_arr != NULL);
 	memset(_arr, 0, _arrsize * sizeof(Node *));
 
-	_nele = 0;
-
 	// rehash all the old elements
 	for (ctr = 0; ctr < old_arrsize; ++ctr) {
 		if (old_arr[ctr] == NULL)
@@ -330,6 +332,7 @@
 	}
 
 	// Perform a sanity check: Old number of elements should match the new one!
+	// This check will fail if some previous operation corrupted this hashmap.
 	assert(_nele == old_nele);
 
 	delete[] old_arr;
@@ -418,25 +421,33 @@
 }
 
 template <class Key, class Val, class HashFunc, class EqualFunc>
-size_t HashMap<Key, Val, HashFunc, EqualFunc>::erase(const Key &key) {
+void HashMap<Key, Val, HashFunc, EqualFunc>::erase(const Key &key) {
 	// This is based on code in the Wikipedia article on Hash tables.
 	uint i = lookup(key);
 	if (_arr[i] == NULL)
-		return 0; // key wasn't present, so no work has to be done
+		return; // key wasn't present, so no work has to be done
+	// If we remove a key, we must check all subsequent keys and possibly
+	// reinsert them.
 	uint j = i;
 	while (true) {
+		// Look at the next table slot
 		j = (j + 1) % _arrsize;
+		// If the next slot is empty, we are done
 		if (_arr[j] == NULL)
 			break;
+		// Compute the slot where the content of the next slot should normally be,
+		// assuming an empty table, and check whether we have to move it.
 		uint k = _hash(_arr[j]->_key) % _arrsize;
 		if ((j > i && (k <= i || k > j)) ||
 		    (j < i && (k <= i && k > j)) ) {
+		    delete _arr[i];
 			_arr[i] = _arr[j];
 			i = j;
 		}
 	}
+    delete _arr[i];
 	_arr[i] = NULL;
-	return 1;
+	return;
 }
 
 }	// End of namespace Common


This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.




More information about the Scummvm-git-logs mailing list