Logo Search packages:      
Sourcecode: scummvm version File versions  Download package

hashmap.h

/* ScummVM - Graphic Adventure Engine
 *
 * ScummVM is the legal property of its developers, whose names
 * are too numerous to list here. Please refer to the COPYRIGHT
 * file distributed with this source distribution.
 *
 * This program is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public License
 * as published by the Free Software Foundation; either version 2
 * of the License, or (at your option) any later version.

 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.

 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
 *
 * $URL: https://scummvm.svn.sourceforge.net/svnroot/scummvm/scummvm/tags/release-1-0-0/common/hashmap.h $
 * $Id: hashmap.h 44257 2009-09-22 12:33:20Z wjpalenstijn $
 *
 */

// The hash map (associative array) implementation in this file is
// based on the PyDict implementation of CPython.

#ifndef COMMON_HASHMAP_H
#define COMMON_HASHMAP_H

#include "common/func.h"
#include "common/str.h"
#include "common/util.h"

#define USE_HASHMAP_MEMORY_POOL
#ifdef USE_HASHMAP_MEMORY_POOL
#include "common/memorypool.h"
#endif

namespace Common {
/**
  * The sgi IRIX MIPSpro Compiler has difficulties with nested templates. 
  * This and the other __sgi conditionals below work around these problems.
  */
#ifdef __sgi
template<class T> class IteratorImpl;
#endif

// 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).
//#define DEBUG_HASH_COLLISIONS


/**
 * HashMap<Key,Val> maps objects of type Key to objects of type Val.
 * For each used Key type, we need an "uint hashit(Key,uint)" function
 * that computes a hash for the given Key object and returns it as an
 * an integer from 0 to hashsize-1, and also an "equality functor".
 * that returns true if if its two arguments are to be considered
 * equal. Also, we assume that "=" works on Val objects for assignment.
 *
 * If aa is an HashMap<Key,Val>, then space is allocated each time aa[key] is
 * referenced, for a new key. If the object is const, then an assertion is
 * 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> >
00070 class HashMap {
private:
#if defined (PALMOS_MODE)
public:
#endif

      typedef HashMap<Key, Val, HashFunc, EqualFunc> HM_t;

      struct Node {
            const Key _key;
            Val _value;
            explicit Node(const Key &key) : _key(key), _value() {}
            Node() : _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
      };


      ObjectPool<Node, HASHMAP_MEMORYPOOL_SIZE> _nodePool;

      Node *allocNode(const Key &key) {
            return new (_nodePool) Node(key);
      }

      void freeNode(Node *node) {
            if (node && node != &_dummyNode)
                  _nodePool.deleteChunk(node);
      }

      Node **_storage;  // hashtable of size arrsize.
00113       uint _mask;       /**< Capacity of the HashMap minus one; must be a power of two of minus one */
      uint _size;
00115       uint _deleted; ///< Number of deleted elements (_dummyNodes)

      HashFunc _hash;
      EqualFunc _equal;

      // Default value, returned by the const getVal.
      const Val _defaultVal;

      // Dummy node, used as marker for erased objects.
      Node _dummyNode;

#ifdef DEBUG_HASH_COLLISIONS
      mutable int _collisions, _lookups, _dummyHits;
#endif

      void assign(const HM_t &map);
      int lookup(const Key &key) const;
      int lookupAndCreateIfMissing(const Key &key);
      void expandStorage(uint newCapacity);

#ifndef __sgi
      template<class T> friend class IteratorImpl;
#endif

      /**
       * Simple HashMap iterator implementation.
       */
      template<class NodeType>
00143       class IteratorImpl {
            friend class HashMap;
#ifdef __sgi
            template<class T> friend class Common::IteratorImpl;
#else
            template<class T> friend class IteratorImpl;
#endif
      protected:
            typedef const HashMap hashmap_t;

            uint _idx;
            hashmap_t *_hashmap;

      protected:
            IteratorImpl(uint idx, hashmap_t *hashmap) : _idx(idx), _hashmap(hashmap) {}

            NodeType *deref() const {
                  assert(_hashmap != 0);
                  assert(_idx <= _hashmap->_mask);
                  Node *node = _hashmap->_storage[_idx];
                  assert(node != 0);
                  assert(node != &_hashmap->_dummyNode);
                  return node;
            }

      public:
            IteratorImpl() : _idx(0), _hashmap(0) {}
            template<class T>
            IteratorImpl(const IteratorImpl<T> &c) : _idx(c._idx), _hashmap(c._hashmap) {}

            NodeType &operator*() const { return *deref(); }
            NodeType *operator->() const { return deref(); }

            bool operator==(const IteratorImpl &iter) const { return _idx == iter._idx && _hashmap == iter._hashmap; }
            bool operator!=(const IteratorImpl &iter) const { return !(*this == iter); }

            IteratorImpl &operator++() {
                  assert(_hashmap);
                  do {
                        _idx++;
                  } while (_idx <= _hashmap->_mask && (_hashmap->_storage[_idx] == 0 || _hashmap->_storage[_idx] == &_hashmap->_dummyNode));
                  if (_idx > _hashmap->_mask)
                        _idx = (uint)-1;

                  return *this;
            }

            IteratorImpl operator++(int) {
                  IteratorImpl old = *this;
                  operator ++();
                  return old;
            }
      };

public:
      typedef IteratorImpl<Node> iterator;
      typedef IteratorImpl<const Node> const_iterator;

      HashMap();
      HashMap(const HM_t &map);
      ~HashMap();

      HM_t &operator=(const HM_t &map) {
            if (this == &map)
                  return *this;

            // Remove the previous content and ...
            clear();
            delete[] _storage;
            // ... copy the new stuff.
            assign(map);
            return *this;
      }

      bool contains(const Key &key) const;

      Val &operator[](const Key &key);
      const Val &operator[](const Key &key) const;

      Val &getVal(const Key &key);
      const Val &getVal(const Key &key) const;
      void setVal(const Key &key, const Val &val);

      void clear(bool shrinkArray = 0);

      void erase(const Key &key);

      uint size() const { return _size; }

      iterator    begin() {
            // Find and return the first non-empty entry
            for (uint ctr = 0; ctr <= _mask; ++ctr) {
                  if (_storage[ctr] && _storage[ctr] != &_dummyNode)
                        return iterator(ctr, this);
            }
            return end();
      }
      iterator    end() {
            return iterator((uint)-1, this);
      }

      const_iterator    begin() const {
            // Find and return the first non-empty entry
            for (uint ctr = 0; ctr <= _mask; ++ctr) {
                  if (_storage[ctr] && _storage[ctr] != &_dummyNode)
                        return const_iterator(ctr, this);
            }
            return end();
      }
      const_iterator    end() const {
            return const_iterator((uint)-1, this);
      }

      iterator    find(const Key &key) {
            uint ctr = lookup(key);
            if (_storage[ctr])
                  return iterator(ctr, this);
            return end();
      }

      const_iterator    find(const Key &key) const {
            uint ctr = lookup(key);
            if (_storage[ctr])
                  return const_iterator(ctr, this);
            return end();
      }

      // TODO: insert() method?

      bool empty() const {
            return (_size == 0);
      }
};

//-------------------------------------------------------
// HashMap functions

/**
 * Base constructor, creates an empty hashmap.
 */
template<class Key, class Val, class HashFunc, class EqualFunc>
00284 HashMap<Key, Val, HashFunc, EqualFunc>::HashMap()
//
// We have to skip _defaultVal() on PS2 to avoid gcc 3.2.2 ICE
//
#ifdef __PLAYSTATION2__
      {
#else
      : _defaultVal(), _dummyNode() {
#endif
      _mask = HASHMAP_MIN_CAPACITY - 1;
      _storage = new Node *[HASHMAP_MIN_CAPACITY];
      assert(_storage != NULL);
      memset(_storage, 0, HASHMAP_MIN_CAPACITY * sizeof(Node *));

      _size = 0;
      _deleted = 0;

#ifdef DEBUG_HASH_COLLISIONS
      _collisions = 0;
      _lookups = 0;
      _dummyHits = 0;
#endif
}

/**
 * Copy constructor, creates a full copy of the given hashmap.
 * We must provide a custom copy constructor as we use pointers
 * to heap buffers for the internal storage.
 */
template<class Key, class Val, class HashFunc, class EqualFunc>
00314 HashMap<Key, Val, HashFunc, EqualFunc>::HashMap(const HM_t &map) :
      _defaultVal(), _dummyNode() {
#ifdef DEBUG_HASH_COLLISIONS
      _collisions = 0;
      _lookups = 0;
      _dummyHits = 0;
#endif
      assign(map);
}

/**
 * Destructor, frees all used memory.
 */
template<class Key, class Val, class HashFunc, class EqualFunc>
00328 HashMap<Key, Val, HashFunc, EqualFunc>::~HashMap() {
      for (uint ctr = 0; ctr <= _mask; ++ctr)
        freeNode(_storage[ctr]);

      delete[] _storage;
#ifdef DEBUG_HASH_COLLISIONS
      extern void updateHashCollisionStats(int, int, int, int, int);
      updateHashCollisionStats(_collisions, _dummyHits, _lookups, _mask+1, _size);
#endif
}

/**
 * Internal method for assigning the content of another HashMap
 * to this one.
 *
 * @note We do *not* deallocate the previous storage here -- the caller is
 *       responsible for doing that!
 */
template<class Key, class Val, class HashFunc, class EqualFunc>
00347 void HashMap<Key, Val, HashFunc, EqualFunc>::assign(const HM_t &map) {
      _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.
      _size = 0;
      _deleted = 0;
      for (uint ctr = 0; ctr <= _mask; ++ctr) {
            if (map._storage[ctr] == &map._dummyNode) {
                  _storage[ctr] = &_dummyNode;
                  _deleted++;
            } else 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(_size == map._size);
      assert(_deleted == map._deleted);
}


template<class Key, class Val, class HashFunc, class EqualFunc>
void HashMap<Key, Val, HashFunc, EqualFunc>::clear(bool shrinkArray) {
      for (uint ctr = 0; ctr <= _mask; ++ctr) {
            freeNode(_storage[ctr]);
            _storage[ctr] = NULL;
      }

#ifdef USE_HASHMAP_MEMORY_POOL
      _nodePool.freeUnusedPages();
#endif

      if (shrinkArray && _mask >= HASHMAP_MIN_CAPACITY) {
            delete[] _storage;

            _mask = HASHMAP_MIN_CAPACITY;
            _storage = new Node *[HASHMAP_MIN_CAPACITY];
            assert(_storage != NULL);
            memset(_storage, 0, HASHMAP_MIN_CAPACITY * sizeof(Node *));
      }

      _size = 0;
      _deleted = 0;
}

template<class Key, class Val, class HashFunc, class EqualFunc>
void HashMap<Key, Val, HashFunc, EqualFunc>::expandStorage(uint newCapacity) {
      assert(newCapacity > _mask+1);

#ifndef NDEBUG
      const uint old_size = _size;
#endif
      const uint old_mask = _mask;
      Node **old_storage = _storage;

      // allocate a new array
      _size = 0;
      _deleted = 0;
      _mask = newCapacity - 1;
      _storage = new Node *[newCapacity];
      assert(_storage != NULL);
      memset(_storage, 0, newCapacity * sizeof(Node *));

      // rehash all the old elements
      for (uint ctr = 0; ctr <= old_mask; ++ctr) {
            if (old_storage[ctr] == NULL || old_storage[ctr] == &_dummyNode)
                  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().
            const uint hash = _hash(old_storage[ctr]->_key);
            uint idx = hash & _mask;
            for (uint perturb = hash; _storage[idx] != NULL && _storage[idx] != &_dummyNode; perturb >>= HASHMAP_PERTURB_SHIFT) {
                  idx = (5 * idx + perturb + 1) & _mask;
            }

            _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(_size == old_size);

      delete[] old_storage;

      return;
}

template<class Key, class Val, class HashFunc, class EqualFunc>
int HashMap<Key, Val, HashFunc, EqualFunc>::lookup(const Key &key) const {
      const uint hash = _hash(key);
      uint ctr = hash & _mask;
      for (uint perturb = hash; ; perturb >>= HASHMAP_PERTURB_SHIFT) {
            if (_storage[ctr] == NULL)
                  break;
            if (_storage[ctr] == &_dummyNode) {
#ifdef DEBUG_HASH_COLLISIONS
                  _dummyHits++;
#endif
            } else if (_equal(_storage[ctr]->_key, key))
                  break;

            ctr = (5 * ctr + perturb + 1) & _mask;

#ifdef DEBUG_HASH_COLLISIONS
            _collisions++;
#endif
      }

#ifdef DEBUG_HASH_COLLISIONS
      _lookups++;
      fprintf(stderr, "collisions %d, dummies hit %d, lookups %d, ratio %f in HashMap %p; size %d num elements %d\n",
            _collisions, _dummyHits, _lookups, ((double) _collisions / (double)_lookups),
            (const void *)this, _mask+1, _size);
#endif

      return ctr;
}

template<class Key, class Val, class HashFunc, class EqualFunc>
int HashMap<Key, Val, HashFunc, EqualFunc>::lookupAndCreateIfMissing(const Key &key) {
      const uint hash = _hash(key);
      uint ctr = hash & _mask;
      const uint NONE_FOUND = _mask + 1;
      uint first_free = NONE_FOUND;
      bool found = false;
      for (uint perturb = hash; ; perturb >>= HASHMAP_PERTURB_SHIFT) {
            if (_storage[ctr] == NULL)
                  break;
            if (_storage[ctr] == &_dummyNode) {
#ifdef DEBUG_HASH_COLLISIONS
                  _dummyHits++;
#endif
                  if (first_free != _mask + 1)
                        first_free = ctr;
            } else if (_equal(_storage[ctr]->_key, key)) {
                  found = true;
                  break;
            }

            ctr = (5 * ctr + perturb + 1) & _mask;

#ifdef DEBUG_HASH_COLLISIONS
            _collisions++;
#endif
      }

#ifdef DEBUG_HASH_COLLISIONS
      _lookups++;
      fprintf(stderr, "collisions %d, dummies hit %d, lookups %d, ratio %f in HashMap %p; size %d num elements %d\n",
            _collisions, _dummyHits, _lookups, ((double) _collisions / (double)_lookups),
            (const void *)this, _mask+1, _size);
#endif

      if (!found && first_free != _mask + 1)
            ctr = first_free;

      if (!found) {
            if (_storage[ctr])
                  _deleted--;
            _storage[ctr] = allocNode(key);
            assert(_storage[ctr] != NULL);
            _size++;

            // Keep the load factor below a certain threshold.
            // Deleted nodes are also counted
            uint capacity = _mask + 1;
            if ((_size + _deleted) * HASHMAP_LOADFACTOR_DENOMINATOR >
                    capacity * HASHMAP_LOADFACTOR_NUMERATOR) {
                  capacity = capacity < 500 ? (capacity * 4) : (capacity * 2);
                  expandStorage(capacity);
                  ctr = lookup(key);
                  assert(_storage[ctr] != NULL);
            }
      }

      return ctr;
}


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 (_storage[ctr] != NULL);
}

template<class Key, class Val, class HashFunc, class EqualFunc>
Val &HashMap<Key, Val, HashFunc, EqualFunc>::operator[](const Key &key) {
      return getVal(key);
}

template<class Key, class Val, class HashFunc, class EqualFunc>
const Val &HashMap<Key, Val, HashFunc, EqualFunc>::operator[](const Key &key) const {
      return getVal(key);
}

template<class Key, class Val, class HashFunc, class EqualFunc>
Val &HashMap<Key, Val, HashFunc, EqualFunc>::getVal(const Key &key) {
      uint ctr = lookupAndCreateIfMissing(key);
      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 (_storage[ctr] != NULL)
            return _storage[ctr]->_value;
      else
            return _defaultVal;
}

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(_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) {

      uint ctr = lookup(key);
      if (_storage[ctr] == NULL)
            return;

      // If we remove a key, we replace it with a dummy node.
      freeNode(_storage[ctr]);
      _storage[ctr] = &_dummyNode;
      _size--;
      _deleted++;
      return;
}

}     // End of namespace Common

#endif

Generated by  Doxygen 1.6.0   Back to index