aboutsummaryrefslogtreecommitdiff
path: root/common/hashmap.h
diff options
context:
space:
mode:
Diffstat (limited to 'common/hashmap.h')
-rw-r--r--common/hashmap.h272
1 files changed, 139 insertions, 133 deletions
diff --git a/common/hashmap.h b/common/hashmap.h
index 69f367de97..81f5ee84b4 100644
--- a/common/hashmap.h
+++ b/common/hashmap.h
@@ -24,32 +24,8 @@
*/
// The hash map (associative array) implementation in this file is
-// based on code by Andrew Y. Ng, 1996:
-
-/*
- * Copyright (c) 1998-2003 Massachusetts Institute of Technology.
- * This code was developed as part of the Haystack research project
- * (http://haystack.lcs.mit.edu/). Permission is hereby granted,
- * free of charge, to any person obtaining a copy of this software
- * and associated documentation files (the "Software"), to deal in
- * the Software without restriction, including without limitation
- * the rights to use, copy, modify, merge, publish, distribute,
- * sublicense, and/or sell copies of the Software, and to permit
- * persons to whom the Software is furnished to do so, subject to
- * the following conditions:
- *
- * The above copyright notice and this permission notice shall be
- * included in all copies or substantial portions of the Software.
- *
- * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
- * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
- * OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
- * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
- * HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
- * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
- * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
- * OTHER DEALINGS IN THE SOFTWARE.
- */
+// based on the PyDict implementation of CPython. The erase() method
+// is based on example code in the Wikipedia article on Hash tables.
#ifndef COMMON_HASHMAP_H
#define COMMON_HASHMAP_H
@@ -74,11 +50,6 @@
namespace Common {
-// The table sizes ideally are primes. We use a helper function to find
-// suitable table sizes.
-uint nextTableSize(uint x);
-
-
// Enable the following #define if you want to check how many collisions the
// code produces (many collisions indicate either a bad hash function, or a
// hash table that is too small).
@@ -113,9 +84,24 @@ public:
Node(const Key &key) : _key(key), _value() {}
};
+ enum {
+ HASHMAP_PERTURB_SHIFT = 5,
+ HASHMAP_MIN_CAPACITY = 16,
+
+ // The quotient of the next two constants controls how much the
+ // internal storage of the hashmap may fill up before being
+ // increased automatically.
+ // Note: the quotient of these two must be between and different
+ // from 0 and 1.
+ HASHMAP_LOADFACTOR_NUMERATOR = 2,
+ HASHMAP_LOADFACTOR_DENOMINATOR = 3,
+
+ HASHMAP_MEMORYPOOL_SIZE = HASHMAP_MIN_CAPACITY * HASHMAP_LOADFACTOR_NUMERATOR / HASHMAP_LOADFACTOR_DENOMINATOR
+ };
+
#ifdef USE_HASHMAP_MEMORY_POOL
- MemoryPool _nodePool;
+ FixedSizeMemoryPool<sizeof(Node), HASHMAP_MEMORYPOOL_SIZE> _nodePool;
Node *allocNode(const Key &key) {
void* mem = _nodePool.malloc();
@@ -136,8 +122,9 @@ public:
}
#endif
- Node **_arr; // hashtable of size arrsize.
- uint _arrsize, _nele;
+ 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;
HashFunc _hash;
EqualFunc _equal;
@@ -152,7 +139,7 @@ public:
void assign(const HM_t &map);
int lookup(const Key &key) const;
int lookupAndCreateIfMissing(const Key &key);
- void expand_array(uint newsize);
+ void expandStorage(uint newCapacity);
template<class T> friend class IteratorImpl;
@@ -174,8 +161,8 @@ public:
NodeType *deref() const {
assert(_hashmap != 0);
- assert(_idx < _hashmap->_arrsize);
- Node *node = _hashmap->_arr[_idx];
+ assert(_idx <= _hashmap->_mask);
+ Node *node = _hashmap->_storage[_idx];
assert(node != 0);
return node;
}
@@ -195,8 +182,8 @@ public:
assert(_hashmap);
do {
_idx++;
- } while (_idx < _hashmap->_arrsize && _hashmap->_arr[_idx] == 0);
- if (_idx >= _hashmap->_arrsize)
+ } while (_idx <= _hashmap->_mask && _hashmap->_storage[_idx] == 0);
+ if (_idx > _hashmap->_mask)
_idx = (uint)-1;
return *this;
@@ -223,7 +210,7 @@ public:
// Remove the previous content and ...
clear();
- delete[] _arr;
+ delete[] _storage;
// ... copy the new stuff.
assign(map);
return *this;
@@ -242,12 +229,12 @@ public:
void erase(const Key &key);
- uint size() const { return _nele; }
+ uint size() const { return _size; }
iterator begin() {
// Find and return the _key non-empty entry
- for (uint ctr = 0; ctr < _arrsize; ++ctr) {
- if (_arr[ctr])
+ for (uint ctr = 0; ctr <= _mask; ++ctr) {
+ if (_storage[ctr])
return iterator(ctr, this);
}
return end();
@@ -258,8 +245,8 @@ public:
const_iterator begin() const {
// Find and return the first non-empty entry
- for (uint ctr = 0; ctr < _arrsize; ++ctr) {
- if (_arr[ctr])
+ for (uint ctr = 0; ctr <= _mask; ++ctr) {
+ if (_storage[ctr])
return const_iterator(ctr, this);
}
return end();
@@ -270,14 +257,14 @@ public:
iterator find(const Key &key) {
uint ctr = lookup(key);
- if (_arr[ctr])
+ if (_storage[ctr])
return iterator(ctr, this);
return end();
}
const_iterator find(const Key &key) const {
uint ctr = lookup(key);
- if (_arr[ctr])
+ if (_storage[ctr])
return const_iterator(ctr, this);
return end();
}
@@ -285,7 +272,7 @@ public:
// TODO: insert() method?
bool empty() const {
- return (_nele == 0);
+ return (_size == 0);
}
};
@@ -297,16 +284,13 @@ public:
*/
template<class Key, class Val, class HashFunc, class EqualFunc>
HashMap<Key, Val, HashFunc, EqualFunc>::HashMap() :
-#ifdef USE_HASHMAP_MEMORY_POOL
- _nodePool(sizeof(Node)),
-#endif
_defaultVal() {
- _arrsize = nextTableSize(0);
- _arr = new Node *[_arrsize];
- assert(_arr != NULL);
- memset(_arr, 0, _arrsize * sizeof(Node *));
+ _mask = HASHMAP_MIN_CAPACITY - 1;
+ _storage = new Node *[HASHMAP_MIN_CAPACITY];
+ assert(_storage != NULL);
+ memset(_storage, 0, HASHMAP_MIN_CAPACITY * sizeof(Node *));
- _nele = 0;
+ _size = 0;
#ifdef DEBUG_HASH_COLLISIONS
_collisions = 0;
@@ -321,9 +305,6 @@ HashMap<Key, Val, HashFunc, EqualFunc>::HashMap() :
*/
template<class Key, class Val, class HashFunc, class EqualFunc>
HashMap<Key, Val, HashFunc, EqualFunc>::HashMap(const HM_t &map) :
-#ifdef USE_HASHMAP_MEMORY_POOL
- _nodePool(sizeof(Node)),
-#endif
_defaultVal() {
assign(map);
}
@@ -333,11 +314,15 @@ 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 < _arrsize; ++ctr)
- if (_arr[ctr] != NULL)
- freeNode(_arr[ctr]);
+ for (uint ctr = 0; ctr <= _mask; ++ctr)
+ if (_storage[ctr] != NULL)
+ freeNode(_storage[ctr]);
- delete[] _arr;
+ delete[] _storage;
+#ifdef DEBUG_HASH_COLLISIONS
+ extern void updateHashCollisionStats(int, int, int, int);
+ updateHashCollisionStats(_collisions, _lookups, _mask+1, _size);
+#endif
}
/**
@@ -349,95 +334,102 @@ HashMap<Key, Val, HashFunc, EqualFunc>::~HashMap() {
*/
template<class Key, class Val, class HashFunc, class EqualFunc>
void HashMap<Key, Val, HashFunc, EqualFunc>::assign(const HM_t &map) {
- _arrsize = map._arrsize;
- _arr = new Node *[_arrsize];
- assert(_arr != NULL);
- memset(_arr, 0, _arrsize * sizeof(Node *));
+ _mask = map._mask;
+ _storage = new Node *[_mask+1];
+ assert(_storage != NULL);
+ memset(_storage, 0, (_mask+1) * sizeof(Node *));
// Simply clone the map given to us, one by one.
- _nele = 0;
- for (uint ctr = 0; ctr < _arrsize; ++ctr) {
- if (map._arr[ctr] != NULL) {
- _arr[ctr] = allocNode(map._arr[ctr]->_key);
- _arr[ctr]->_value = map._arr[ctr]->_value;
- _nele++;
+ _size = 0;
+ for (uint ctr = 0; ctr <= _mask; ++ctr) {
+ if (map._storage[ctr] != NULL) {
+ _storage[ctr] = allocNode(map._storage[ctr]->_key);
+ _storage[ctr]->_value = map._storage[ctr]->_value;
+ _size++;
}
}
// Perform a sanity check (to help track down hashmap corruption)
- assert(_nele == map._nele);
+ assert(_size == map._size);
}
template<class Key, class Val, class HashFunc, class EqualFunc>
void HashMap<Key, Val, HashFunc, EqualFunc>::clear(bool shrinkArray) {
- for (uint ctr = 0; ctr < _arrsize; ++ctr) {
- if (_arr[ctr] != NULL) {
- freeNode(_arr[ctr]);
- _arr[ctr] = NULL;
+ for (uint ctr = 0; ctr <= _mask; ++ctr) {
+ if (_storage[ctr] != NULL) {
+ freeNode(_storage[ctr]);
+ _storage[ctr] = NULL;
}
}
- if (shrinkArray && _arrsize > nextTableSize(0)) {
- delete[] _arr;
+#ifdef USE_HASHMAP_MEMORY_POOL
+ _nodePool.freeUnusedPages();
+#endif
+
+ if (shrinkArray && _mask >= HASHMAP_MIN_CAPACITY) {
+ delete[] _storage;
- _arrsize = nextTableSize(0);
- _arr = new Node *[_arrsize];
- assert(_arr != NULL);
- memset(_arr, 0, _arrsize * sizeof(Node *));
+ _mask = HASHMAP_MIN_CAPACITY;
+ _storage = new Node *[HASHMAP_MIN_CAPACITY];
+ assert(_storage != NULL);
+ memset(_storage, 0, HASHMAP_MIN_CAPACITY * sizeof(Node *));
}
- _nele = 0;
+ _size = 0;
}
template<class Key, class Val, class HashFunc, class EqualFunc>
-void HashMap<Key, Val, HashFunc, EqualFunc>::expand_array(uint newsize) {
- assert(newsize > _arrsize);
- uint ctr, dex;
+void HashMap<Key, Val, HashFunc, EqualFunc>::expandStorage(uint newCapacity) {
+ assert(newCapacity > _mask+1);
- const uint old_nele = _nele;
- const uint old_arrsize = _arrsize;
- Node **old_arr = _arr;
+ const uint old_size = _size;
+ const uint old_mask = _mask;
+ Node **old_storage = _storage;
// allocate a new array
- _nele = 0;
- _arrsize = newsize;
- _arr = new Node *[_arrsize];
- assert(_arr != NULL);
- memset(_arr, 0, _arrsize * sizeof(Node *));
+ _size = 0;
+ _mask = newCapacity - 1;
+ _storage = new Node *[newCapacity];
+ assert(_storage != NULL);
+ memset(_storage, 0, newCapacity * sizeof(Node *));
// rehash all the old elements
- for (ctr = 0; ctr < old_arrsize; ++ctr) {
- if (old_arr[ctr] == NULL)
+ for (uint ctr = 0; ctr <= old_mask; ++ctr) {
+ if (old_storage[ctr] == NULL)
continue;
// Insert the element from the old table into the new table.
// 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().
- dex = _hash(old_arr[ctr]->_key) % _arrsize;
- while (_arr[dex] != NULL) {
- dex = (dex + 1) % _arrsize;
+ const uint hash = _hash(old_storage[ctr]->_key);
+ uint idx = hash & _mask;
+ for (uint perturb = hash; _storage[idx] != NULL; perturb >>= HASHMAP_PERTURB_SHIFT) {
+ idx = (5 * idx + perturb + 1) & _mask;
}
- _arr[dex] = old_arr[ctr];
- _nele++;
+ _storage[idx] = old_storage[ctr];
+ _size++;
}
// 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);
+ assert(_size == old_size);
- delete[] old_arr;
+ delete[] old_storage;
return;
}
template<class Key, class Val, class HashFunc, class EqualFunc>
int HashMap<Key, Val, HashFunc, EqualFunc>::lookup(const Key &key) const {
- uint ctr = _hash(key) % _arrsize;
+ const uint hash = _hash(key);
+ uint ctr = hash & _mask;
+ for (uint perturb = hash; ; perturb >>= HASHMAP_PERTURB_SHIFT) {
+ if (_storage[ctr] == NULL || _equal(_storage[ctr]->_key, key))
+ break;
- while (_arr[ctr] != NULL && !_equal(_arr[ctr]->_key, key)) {
- ctr = (ctr + 1) % _arrsize;
+ ctr = (5 * ctr + perturb + 1) & _mask;
#ifdef DEBUG_HASH_COLLISIONS
_collisions++;
@@ -448,7 +440,7 @@ int HashMap<Key, Val, HashFunc, EqualFunc>::lookup(const Key &key) const {
_lookups++;
fprintf(stderr, "collisions %d, lookups %d, ratio %f in HashMap %p; size %d num elements %d\n",
_collisions, _lookups, ((double) _collisions / (double)_lookups),
- (const void *)this, _arrsize, _nele);
+ (const void *)this, _mask+1, _size);
#endif
return ctr;
@@ -458,13 +450,15 @@ template<class Key, class Val, class HashFunc, class EqualFunc>
int HashMap<Key, Val, HashFunc, EqualFunc>::lookupAndCreateIfMissing(const Key &key) {
uint ctr = lookup(key);
- if (_arr[ctr] == NULL) {
- _arr[ctr] = allocNode(key);
- _nele++;
+ if (_storage[ctr] == NULL) {
+ _storage[ctr] = allocNode(key);
+ _size++;
- // Keep the load factor below 75%.
- if (_nele > _arrsize * 75 / 100) {
- expand_array(nextTableSize(_arrsize));
+ // Keep the load factor below a certain threshold.
+ uint capacity = _mask + 1;
+ if (_size * HASHMAP_LOADFACTOR_DENOMINATOR > capacity * HASHMAP_LOADFACTOR_NUMERATOR) {
+ capacity = capacity < 500 ? (capacity * 4) : (capacity * 2);
+ expandStorage(capacity);
ctr = lookup(key);
}
}
@@ -476,7 +470,7 @@ int 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);
- return (_arr[ctr] != NULL);
+ return (_storage[ctr] != NULL);
}
template<class Key, class Val, class HashFunc, class EqualFunc>
@@ -492,15 +486,15 @@ 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);
- assert(_arr[ctr] != NULL);
- return _arr[ctr]->_value;
+ assert(_storage[ctr] != NULL);
+ return _storage[ctr]->_value;
}
template<class Key, class Val, class HashFunc, class EqualFunc>
const Val &HashMap<Key, Val, HashFunc, EqualFunc>::getVal(const Key &key) const {
uint ctr = lookup(key);
- if (_arr[ctr] != NULL)
- return _arr[ctr]->_value;
+ if (_storage[ctr] != NULL)
+ return _storage[ctr]->_value;
else
return _defaultVal;
}
@@ -508,38 +502,50 @@ 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);
- assert(_arr[ctr] != NULL);
- _arr[ctr]->_value = val;
+ assert(_storage[ctr] != NULL);
+ _storage[ctr]->_value = val;
}
template<class Key, class Val, class HashFunc, class EqualFunc>
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)
+
+ const uint hash = _hash(key);
+ uint i = hash & _mask;
+ uint perturb;
+
+ for (perturb = hash; ; perturb >>= HASHMAP_PERTURB_SHIFT) {
+ if (_storage[i] == NULL || _equal(_storage[i]->_key, key))
+ break;
+
+ i = (5 * i + perturb + 1) & _mask;
+ }
+
+ if (_storage[i] == NULL)
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;
- freeNode(_arr[i]);
- _arr[i] = NULL;
- while (true) {
+ freeNode(_storage[i]);
+ _storage[i] = NULL;
+ for (perturb = hash; ; perturb >>= HASHMAP_PERTURB_SHIFT) {
// Look at the next table slot
- j = (j + 1) % _arrsize;
+ j = (5 * j + perturb + 1) & _mask;
// If the next slot is empty, we are done
- if (_arr[j] == NULL)
+ if (_storage[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;
+ uint k = _hash(_storage[j]->_key) & _mask;
if ((j > i && (k <= i || k > j)) ||
(j < i && (k <= i && k > j)) ) {
- _arr[i] = _arr[j];
+ _storage[i] = _storage[j];
i = j;
}
}
- _arr[i] = NULL;
- _nele--;
+ _storage[i] = NULL;
+ _size--;
return;
}
generated by cgit v1.2.3 (git 2.25.1) at 2024-09-12 20:14:28 +0000