[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