From 51010bd038119dc98356b442c8f30b8e486aa5c2 Mon Sep 17 00:00:00 2001 From: Max Horn Date: Mon, 2 Oct 2006 20:13:48 +0000 Subject: Remove BaseNodeType (it is not used anymore, we can readd it, should we ever have need for it again) svn-id: r24079 --- common/hashmap.h | 90 +++++++++++++++++++++++++++----------------------------- 1 file changed, 44 insertions(+), 46 deletions(-) (limited to 'common/hashmap.h') diff --git a/common/hashmap.h b/common/hashmap.h index 87ed1b1173..825f46ab37 100644 --- a/common/hashmap.h +++ b/common/hashmap.h @@ -58,16 +58,6 @@ namespace Common { -// data structure used by HashMap internally to keep -// track of what's mapped to what. -template -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 @@ uint nextTableSize(uint x); * 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 EqualFunc = EqualTo, class BaseNodeType = BaseNode > +template , class EqualFunc = EqualTo > 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: public: class const_iterator { - typedef const HashMap * hashmap_t; - friend class HashMap; + typedef const HashMap * hashmap_t; + friend class HashMap; 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: 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 @@ public: //------------------------------------------------------- // HashMap functions -template -HashMap::HashMap() { +template +HashMap::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 @@ HashMap::HashMap() { #endif } -template -HashMap::~HashMap() { +template +HashMap::~HashMap() { uint ctr; for (ctr = 0; ctr < _arrsize; ctr++) @@ -216,8 +214,8 @@ HashMap::~HashMap() { delete[] _arr; } -template -void HashMap::clear(bool shrinkArray) { +template +void HashMap::clear(bool shrinkArray) { for (uint ctr = 0; ctr < _arrsize; ctr++) { if (_arr[ctr] != NULL) { delete _arr[ctr]; @@ -229,18 +227,18 @@ void HashMap::clear(bool shrinkArra 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 -void HashMap::expand_array(uint newsize) { +template +void HashMap::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 @@ void HashMap::expand_array(uint new // 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 @@ void HashMap::expand_array(uint new return; } -template -int HashMap::lookup(const Key &key) const { +template +int HashMap::lookup(const Key &key) const { uint ctr = _hash(key) % _arrsize; while (_arr[ctr] != NULL && !_equal(_arr[ctr]->_key, key)) { @@ -303,18 +301,18 @@ int HashMap::lookup(const Key &key) return ctr; } -template -bool HashMap::contains(const Key &key) const { +template +bool HashMap::contains(const Key &key) const { uint ctr = lookup(key); return (_arr[ctr] != NULL); } -template -Val &HashMap::operator [](const Key &key) { +template +Val &HashMap::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 @@ Val &HashMap::operator [](const Key return _arr[ctr]->_value; } -template -const Val &HashMap::operator [](const Key &key) const { +template +const Val &HashMap::operator [](const Key &key) const { return queryVal(key); } -template -const Val &HashMap::queryVal(const Key &key) const { +template +const Val &HashMap::queryVal(const Key &key) const { uint ctr = lookup(key); assert(_arr[ctr] != NULL); return _arr[ctr]->_value; } -template -size_t HashMap::erase(const Key &key) { +template +size_t HashMap::erase(const Key &key) { // This is based on code in the Wikipedia article on Hash tables. uint i = lookup(key); if (_arr[i] == NULL) -- cgit v1.2.3