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

fingolfin at users.sourceforge.net fingolfin at users.sourceforge.net
Tue Mar 28 02:55:00 CEST 2006


Revision: 21474
Author:   fingolfin
Date:     2006-03-28 02:54:02 -0800 (Tue, 28 Mar 2006)
ViewCVS:  http://svn.sourceforge.net/scummvm/?rev=21474&view=rev

Log Message:
-----------
Increase the load factor for our hashmaps from 50% to 75%, to be slightly nicer regarding memory consumption

Modified Paths:
--------------
    scummvm/trunk/common/hashmap.h
Modified: scummvm/trunk/common/hashmap.h
===================================================================
--- scummvm/trunk/common/hashmap.h	2006-03-28 10:05:25 UTC (rev 21473)
+++ scummvm/trunk/common/hashmap.h	2006-03-28 10:54:02 UTC (rev 21474)
@@ -110,7 +110,7 @@
 #endif
 
 	int lookup(const Key &key) const;
-	void expand_array(void);
+	void expand_array(uint newsize);
 
 public:
 
@@ -233,13 +233,10 @@
 
 template <class Key, class Val>
 HashMap<Key, Val>::HashMap() {
-	uint ctr;
-
 	_arrsize = nextTableSize(0);
 	_arr = new aa_ref_t *[_arrsize];
 	assert(_arr != NULL);
-	for (ctr = 0; ctr < _arrsize; ctr++)
-		_arr[ctr] = NULL;
+	memset(_arr, 0, _arrsize * sizeof(aa_ref_t *));
 
 	_nele = 0;
 	
@@ -275,15 +272,15 @@
 		_arrsize = nextTableSize(0);
 		_arr = new aa_ref_t *[_arrsize];
 		assert(_arr != NULL);
-		for (uint ctr = 0; ctr < _arrsize; ctr++)
-			_arr[ctr] = NULL;
+		memset(_arr, 0, _arrsize * sizeof(aa_ref_t *));
 	}
 
 	_nele = 0;
 }
 
 template <class Key, class Val>
-void HashMap<Key, Val>::expand_array(void) {
+void HashMap<Key, Val>::expand_array(uint newsize) {
+	assert(newsize > _arrsize);
 	aa_ref_t **old_arr;
 	uint old_arrsize, old_nele, ctr, dex;
 
@@ -292,14 +289,11 @@
 	old_arrsize = _arrsize;
 
 	// allocate a new array 
-	_arrsize = nextTableSize(old_arrsize);
+	_arrsize = newsize;
 	_arr = new aa_ref_t *[_arrsize];
-
 	assert(_arr != NULL);
+	memset(_arr, 0, _arrsize * sizeof(aa_ref_t *));
 
-	for (ctr = 0; ctr < _arrsize; ctr++)
-		_arr[ctr] = NULL;
-
 	_nele = 0;
 
 	// rehash all the old elements
@@ -319,6 +313,7 @@
 		_nele++;
 	}
 
+	// Perform a sanity check: Old number of elements should match the new one!
 	assert(_nele == old_nele);
 
 	delete[] old_arr;
@@ -334,9 +329,9 @@
 		_arr[ctr] = new aa_ref_t(key);
 		_nele++;
 
-		// Only fill array to fifty percent
-		if (_nele > _arrsize / 2) {
-			expand_array();
+		// Keep the load factor below 75%.
+		if (_nele > _arrsize * 65 / 100) {
+			expand_array(nextTableSize(_arrsize));
 			ctr = lookup(key);
 		}
 	}


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