[Scummvm-cvs-logs] SF.net SVN: scummvm: [24079] scummvm/trunk/common/hashmap.h
fingolfin at users.sourceforge.net
fingolfin at users.sourceforge.net
Mon Oct 2 22:13:52 CEST 2006
Revision: 24079
http://svn.sourceforge.net/scummvm/?rev=24079&view=rev
Author: fingolfin
Date: 2006-10-02 13:13:48 -0700 (Mon, 02 Oct 2006)
Log Message:
-----------
Remove BaseNodeType (it is not used anymore, we can readd it, should we ever have need for it again)
Modified Paths:
--------------
scummvm/trunk/common/hashmap.h
Modified: scummvm/trunk/common/hashmap.h
===================================================================
--- scummvm/trunk/common/hashmap.h 2006-10-02 19:17:30 UTC (rev 24078)
+++ scummvm/trunk/common/hashmap.h 2006-10-02 20:13:48 UTC (rev 24079)
@@ -58,16 +58,6 @@
namespace Common {
-// data structure used by HashMap internally to keep
-// track of what's mapped to what.
-template <class Key, class Val>
-struct BaseNode {
- Key _key;
- Val _value;
- BaseNode() {}
- BaseNode(const Key &key) : _key(key) {}
-};
-
// The table sizes ideally are primes. We use a helper function to find
// suitable table sizes.
uint nextTableSize(uint x);
@@ -91,14 +81,22 @@
* triggered instead. Hence if you are not sure whether a key is contained in
* the map, use contains() first to check for its presence.
*/
-template <class Key, class Val, class HashFunc = Hash<Key>, class EqualFunc = EqualTo<Key>, class BaseNodeType = BaseNode<Key, Val> >
+template <class Key, class Val, class HashFunc = Hash<Key>, class EqualFunc = EqualTo<Key> >
class HashMap {
private:
#if defined (_WIN32_WCE) || defined (_MSC_VER) || defined (__SYMBIAN32__) || defined (PALMOS_MODE) || defined (__MINT__)
//FIXME evc4, msvc6,msvc7 & GCC 2.9x doesn't like it as private member
public:
#endif
- BaseNodeType **_arr; // hashtable of size arrsize.
+
+ struct Node {
+ Key _key;
+ Val _value;
+ Node() {}
+ Node(const Key &key) : _key(key) {}
+ };
+
+ Node **_arr; // hashtable of size arrsize.
uint _arrsize, _nele;
HashFunc _hash;
@@ -113,16 +111,16 @@
public:
class const_iterator {
- typedef const HashMap<Key, Val, HashFunc, EqualFunc, BaseNodeType> * hashmap_t;
- friend class HashMap<Key, Val, HashFunc, EqualFunc, BaseNodeType>;
+ typedef const HashMap<Key, Val, HashFunc, EqualFunc> * hashmap_t;
+ friend class HashMap<Key, Val, HashFunc, EqualFunc>;
protected:
hashmap_t _hashmap;
uint _idx;
const_iterator(uint idx, hashmap_t hashmap) : _idx(idx), _hashmap(hashmap) {}
- const BaseNodeType *deref() const {
+ const Node *deref() const {
assert(_hashmap != 0);
- BaseNodeType *node = _hashmap->_arr[_idx];
+ Node *node = _hashmap->_arr[_idx];
assert(node != 0);
return node;
}
@@ -130,8 +128,8 @@
public:
const_iterator() : _idx(0), _hashmap(0) {}
- const BaseNodeType &operator *() const { return *deref(); }
- const BaseNodeType *operator->() const { return deref(); }
+ const Node &operator *() const { return *deref(); }
+ const Node *operator->() const { return deref(); }
bool operator ==(const const_iterator &iter) const { return _idx == iter._idx && _hashmap == iter._hashmap; }
bool operator !=(const const_iterator &iter) const { return !(*this == iter); }
const_iterator operator ++() {
@@ -190,12 +188,12 @@
//-------------------------------------------------------
// HashMap functions
-template <class Key, class Val, class HashFunc, class EqualFunc, class BaseNodeType>
-HashMap<Key, Val, HashFunc, EqualFunc, BaseNodeType>::HashMap() {
+template <class Key, class Val, class HashFunc, class EqualFunc>
+HashMap<Key, Val, HashFunc, EqualFunc>::HashMap() {
_arrsize = nextTableSize(0);
- _arr = new BaseNodeType *[_arrsize];
+ _arr = new Node *[_arrsize];
assert(_arr != NULL);
- memset(_arr, 0, _arrsize * sizeof(BaseNodeType *));
+ memset(_arr, 0, _arrsize * sizeof(Node *));
_nele = 0;
@@ -205,8 +203,8 @@
#endif
}
-template <class Key, class Val, class HashFunc, class EqualFunc, class BaseNodeType>
-HashMap<Key, Val, HashFunc, EqualFunc, BaseNodeType>::~HashMap() {
+template <class Key, class Val, class HashFunc, class EqualFunc>
+HashMap<Key, Val, HashFunc, EqualFunc>::~HashMap() {
uint ctr;
for (ctr = 0; ctr < _arrsize; ctr++)
@@ -216,8 +214,8 @@
delete[] _arr;
}
-template <class Key, class Val, class HashFunc, class EqualFunc, class BaseNodeType>
-void HashMap<Key, Val, HashFunc, EqualFunc, BaseNodeType>::clear(bool shrinkArray) {
+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) {
delete _arr[ctr];
@@ -229,18 +227,18 @@
delete[] _arr;
_arrsize = nextTableSize(0);
- _arr = new BaseNodeType *[_arrsize];
+ _arr = new Node *[_arrsize];
assert(_arr != NULL);
- memset(_arr, 0, _arrsize * sizeof(BaseNodeType *));
+ memset(_arr, 0, _arrsize * sizeof(Node *));
}
_nele = 0;
}
-template <class Key, class Val, class HashFunc, class EqualFunc, class BaseNodeType>
-void HashMap<Key, Val, HashFunc, EqualFunc, BaseNodeType>::expand_array(uint newsize) {
+template <class Key, class Val, class HashFunc, class EqualFunc>
+void HashMap<Key, Val, HashFunc, EqualFunc>::expand_array(uint newsize) {
assert(newsize > _arrsize);
- BaseNodeType **old_arr;
+ Node **old_arr;
uint old_arrsize, old_nele, ctr, dex;
old_nele = _nele;
@@ -249,9 +247,9 @@
// allocate a new array
_arrsize = newsize;
- _arr = new BaseNodeType *[_arrsize];
+ _arr = new Node *[_arrsize];
assert(_arr != NULL);
- memset(_arr, 0, _arrsize * sizeof(BaseNodeType *));
+ memset(_arr, 0, _arrsize * sizeof(Node *));
_nele = 0;
@@ -281,8 +279,8 @@
return;
}
-template <class Key, class Val, class HashFunc, class EqualFunc, class BaseNodeType>
-int HashMap<Key, Val, HashFunc, EqualFunc, BaseNodeType>::lookup(const Key &key) const {
+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;
while (_arr[ctr] != NULL && !_equal(_arr[ctr]->_key, key)) {
@@ -303,18 +301,18 @@
return ctr;
}
-template <class Key, class Val, class HashFunc, class EqualFunc, class BaseNodeType>
-bool HashMap<Key, Val, HashFunc, EqualFunc, BaseNodeType>::contains(const Key &key) const {
+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);
}
-template <class Key, class Val, class HashFunc, class EqualFunc, class BaseNodeType>
-Val &HashMap<Key, Val, HashFunc, EqualFunc, BaseNodeType>::operator [](const Key &key) {
+template <class Key, class Val, class HashFunc, class EqualFunc>
+Val &HashMap<Key, Val, HashFunc, EqualFunc>::operator [](const Key &key) {
uint ctr = lookup(key);
if (_arr[ctr] == NULL) {
- _arr[ctr] = new BaseNodeType(key);
+ _arr[ctr] = new Node(key);
_nele++;
// Keep the load factor below 75%.
@@ -327,20 +325,20 @@
return _arr[ctr]->_value;
}
-template <class Key, class Val, class HashFunc, class EqualFunc, class BaseNodeType>
-const Val &HashMap<Key, Val, HashFunc, EqualFunc, BaseNodeType>::operator [](const Key &key) const {
+template <class Key, class Val, class HashFunc, class EqualFunc>
+const Val &HashMap<Key, Val, HashFunc, EqualFunc>::operator [](const Key &key) const {
return queryVal(key);
}
-template <class Key, class Val, class HashFunc, class EqualFunc, class BaseNodeType>
-const Val &HashMap<Key, Val, HashFunc, EqualFunc, BaseNodeType>::queryVal(const Key &key) const {
+template <class Key, class Val, class HashFunc, class EqualFunc>
+const Val &HashMap<Key, Val, HashFunc, EqualFunc>::queryVal(const Key &key) const {
uint ctr = lookup(key);
assert(_arr[ctr] != NULL);
return _arr[ctr]->_value;
}
-template <class Key, class Val, class HashFunc, class EqualFunc, class BaseNodeType>
-size_t HashMap<Key, Val, HashFunc, EqualFunc, BaseNodeType>::erase(const Key &key) {
+template <class Key, class Val, class HashFunc, class EqualFunc>
+size_t 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)
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