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 3 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, see <http://www.gnu.org/licenses/>.
 *
 */
 
// 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
 
// 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
 
#define USE_HASHMAP_MEMORY_POOL
 
 
#include "common/func.h"
 
#include "common/str.h"
 
#ifdef DEBUG_HASH_COLLISIONS
#include "common/debug.h"
#endif
 
#ifdef USE_HASHMAP_MEMORY_POOL
#include "common/memorypool.h"
#endif
 
namespace Common {
 
// The Intel C++ Compiler has difficulties with nested templates.
#if defined(__INTEL_COMPILER)
template<class T> class IteratorImpl;
#endif
 
 
template<class Key, class Val, class HashFunc = Hash<Key>, class EqualFunc = EqualTo<Key> >
class HashMap {
public:
    typedef uint size_type;
 
    struct Node {
        Val _value;
        const Key _key;
        explicit Node(const Key &key) : _key(key), _value() {}
        Node() : _key(), _value() {}
    };
 
private:
 
    typedef HashMap<Key, Val, HashFunc, EqualFunc> HM_t;
 
    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,
 
#ifdef REDUCE_MEMORY_USAGE
        HASHMAP_MEMORYPOOL_SIZE = 0
#else
        HASHMAP_MEMORYPOOL_SIZE = HASHMAP_MIN_CAPACITY * HASHMAP_LOADFACTOR_NUMERATOR / HASHMAP_LOADFACTOR_DENOMINATOR
#endif
    };
 
#ifdef USE_HASHMAP_MEMORY_POOL
    ObjectPool<Node, HASHMAP_MEMORYPOOL_SIZE> _nodePool;
#endif
 
    Val _defaultVal;
 
    Node **_storage;    
    size_type _mask;        
    size_type _size;
    size_type _deleted; 
 
    HashFunc _hash;
    EqualFunc _equal;
 
    #define HASHMAP_DUMMY_NODE  ((Node *)1)
 
#ifdef DEBUG_HASH_COLLISIONS
    mutable int _collisions, _lookups, _dummyHits;
#endif
 
    Node *allocNode(const Key &key) {
#ifdef USE_HASHMAP_MEMORY_POOL
        return new (_nodePool) Node(key);
#else
        return new Node(key);
#endif
    }
 
    void freeNode(Node *node) {
        if (node && node != HASHMAP_DUMMY_NODE)
#ifdef USE_HASHMAP_MEMORY_POOL
            _nodePool.deleteChunk(node);
#else
            delete node;
#endif
    }
 
    void assign(const HM_t &map);
    size_type lookup(const Key &key) const;
    size_type lookupAndCreateIfMissing(const Key &key);
    void expandStorage(size_type newCapacity);
 
    template<class T> friend class IteratorImpl;
 
    template<class NodeType>
    class IteratorImpl {
        friend class HashMap;
#if defined(__INTEL_COMPILER)
        template<class T> friend class Common::IteratorImpl;
#else
        template<class T> friend class IteratorImpl;
#endif
    protected:
        typedef const HashMap hashmap_t;
 
        size_type _idx;
        hashmap_t *_hashmap;
 
    protected:
        IteratorImpl(size_type idx, hashmap_t *hashmap) : _idx(idx), _hashmap(hashmap) {}
 
        NodeType *deref() const {
            assert(_hashmap != nullptr);
            assert(_idx <= _hashmap->_mask);
            Node *node = _hashmap->_storage[_idx];
            assert(node != nullptr);
            assert(node != HASHMAP_DUMMY_NODE);
            return node;
        }
 
    public:
        IteratorImpl() : _idx(0), _hashmap(nullptr) {}
        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] == nullptr || _hashmap->_storage[_idx] == HASHMAP_DUMMY_NODE));
            if (_idx > _hashmap->_mask)
                _idx = (size_type)-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 &getOrCreateVal(const Key &key);
    Val &getVal(const Key &key);
    const Val &getVal(const Key &key) const;
    const Val &getValOrDefault(const Key &key) const;
    const Val &getValOrDefault(const Key &key, const Val &defaultVal) const;
    bool tryGetVal(const Key &key, Val &out) const;
    void setVal(const Key &key, const Val &val);
 
    void clear(bool shrinkArray = 0);
 
    void erase(iterator entry);
    void erase(const Key &key);
 
    size_type size() const { return _size; }
 
    iterator    begin() {
        // Find and return the first non-empty entry
        for (size_type ctr = 0; ctr <= _mask; ++ctr) {
            if (_storage[ctr] && _storage[ctr] != HASHMAP_DUMMY_NODE)
                return iterator(ctr, this);
        }
        return end();
    }
    iterator    end() {
        return iterator((size_type)-1, this);
    }
 
    const_iterator  begin() const {
        // Find and return the first non-empty entry
        for (size_type ctr = 0; ctr <= _mask; ++ctr) {
            if (_storage[ctr] && _storage[ctr] != HASHMAP_DUMMY_NODE)
                return const_iterator(ctr, this);
        }
        return end();
    }
    const_iterator  end() const {
        return const_iterator((size_type)-1, this);
    }
 
    iterator    find(const Key &key) {
        size_type ctr = lookup(key);
        if (_storage[ctr])
            return iterator(ctr, this);
        return end();
    }
 
    const_iterator  find(const Key &key) const {
        size_type ctr = lookup(key);
        if (_storage[ctr])
            return const_iterator(ctr, this);
        return end();
    }
 
    // TODO: insert() method?
    bool empty() const {
        return (_size == 0);
    }
};
 
template <class Key>
void NORETURN_PRE unknownKeyError(Key k) NORETURN_POST {
    error("Unknown key");
}
 
template<>
void NORETURN_PRE unknownKeyError(::Common::String key) NORETURN_POST;
template<>
void NORETURN_PRE unknownKeyError(signed char key) NORETURN_POST;
template<>
void NORETURN_PRE unknownKeyError(unsigned char key) NORETURN_POST;
template<>
void NORETURN_PRE unknownKeyError(short signed key) NORETURN_POST;
template<>
void NORETURN_PRE unknownKeyError(short unsigned key) NORETURN_POST;
template<>
void NORETURN_PRE unknownKeyError(long signed key) NORETURN_POST;
template<>
void NORETURN_PRE unknownKeyError(long unsigned key) NORETURN_POST;
template<>
void NORETURN_PRE unknownKeyError(signed int key) NORETURN_POST;
template<>
void NORETURN_PRE unknownKeyError(unsigned int key) NORETURN_POST;
template<>
void NORETURN_PRE unknownKeyError(long long signed key) NORETURN_POST;
template<>
void NORETURN_PRE unknownKeyError(long long unsigned key) NORETURN_POST;
template<>
void NORETURN_PRE unknownKeyError(void *key) NORETURN_POST;
template<>
void NORETURN_PRE unknownKeyError(const char *key) NORETURN_POST;
 
//-------------------------------------------------------
// HashMap functions
 
template<class Key, class Val, class HashFunc, class EqualFunc>
HashMap<Key, Val, HashFunc, EqualFunc>::HashMap() : _defaultVal() {
    _mask = HASHMAP_MIN_CAPACITY - 1;
    _storage = new Node *[HASHMAP_MIN_CAPACITY];
    assert(_storage != nullptr);
    memset(_storage, 0, HASHMAP_MIN_CAPACITY * sizeof(Node *));
 
    _size = 0;
    _deleted = 0;
 
#ifdef DEBUG_HASH_COLLISIONS
    _collisions = 0;
    _lookups = 0;
    _dummyHits = 0;
#endif
}
 
template<class Key, class Val, class HashFunc, class EqualFunc>
HashMap<Key, Val, HashFunc, EqualFunc>::HashMap(const HM_t &map) :
    _defaultVal() {
#ifdef DEBUG_HASH_COLLISIONS
    _collisions = 0;
    _lookups = 0;
    _dummyHits = 0;
#endif
    assign(map);
}
 
template<class Key, class Val, class HashFunc, class EqualFunc>
HashMap<Key, Val, HashFunc, EqualFunc>::~HashMap() {
    for (size_type 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
}
 
template<class Key, class Val, class HashFunc, class EqualFunc>
void HashMap<Key, Val, HashFunc, EqualFunc>::assign(const HM_t &map) {
    _mask = map._mask;
    _storage = new Node *[_mask + 1];
    assert(_storage != nullptr);
    memset(_storage, 0, (_mask + 1) * sizeof(Node *));
 
    // Simply clone the map given to us, one by one.
    _size = 0;
    _deleted = 0;
    for (size_type ctr = 0; ctr <= _mask; ++ctr) {
        if (map._storage[ctr] == HASHMAP_DUMMY_NODE) {
            _storage[ctr] = HASHMAP_DUMMY_NODE;
            _deleted++;
        } else if (map._storage[ctr] != nullptr) {
            _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 (size_type ctr = 0; ctr <= _mask; ++ctr) {
        freeNode(_storage[ctr]);
        _storage[ctr] = nullptr;
    }
 
#ifdef USE_HASHMAP_MEMORY_POOL
    _nodePool.freeUnusedPages();
#endif
 
    if (shrinkArray && _mask >= HASHMAP_MIN_CAPACITY) {
        delete[] _storage;
 
        _mask = HASHMAP_MIN_CAPACITY - 1;
        _storage = new Node *[HASHMAP_MIN_CAPACITY];
        assert(_storage != nullptr);
        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(size_type newCapacity) {
    assert(newCapacity > _mask + 1);
 
#ifndef RELEASE_BUILD
    const size_type old_size = _size;
#endif
    const size_type old_mask = _mask;
    Node **old_storage = _storage;
 
    // allocate a new array
    _size = 0;
    _deleted = 0;
    _mask = newCapacity - 1;
    _storage = new Node *[newCapacity];
    assert(_storage != nullptr);
    memset(_storage, 0, newCapacity * sizeof(Node *));
 
    // rehash all the old elements
    for (size_type ctr = 0; ctr <= old_mask; ++ctr) {
        if (old_storage[ctr] == nullptr || old_storage[ctr] == HASHMAP_DUMMY_NODE)
            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 size_type hash = _hash(old_storage[ctr]->_key);
        size_type idx = hash & _mask;
        for (size_type perturb = hash; _storage[idx] != nullptr && _storage[idx] != HASHMAP_DUMMY_NODE; perturb >>= HASHMAP_PERTURB_SHIFT) {
            idx = (5 * idx + perturb + 1) & _mask;
        }
 
        _storage[idx] = old_storage[ctr];
        _size++;
    }
 
#ifndef RELEASE_BUILD
    // 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);
#endif
 
    delete[] old_storage;
 
    return;
}
 
template<class Key, class Val, class HashFunc, class EqualFunc>
typename HashMap<Key, Val, HashFunc, EqualFunc>::size_type HashMap<Key, Val, HashFunc, EqualFunc>::lookup(const Key &key) const {
    const size_type hash = _hash(key);
    size_type ctr = hash & _mask;
    for (size_type perturb = hash; ; perturb >>= HASHMAP_PERTURB_SHIFT) {
        if (_storage[ctr] == nullptr)
            break;
        if (_storage[ctr] == HASHMAP_DUMMY_NODE) {
#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++;
    debug("collisions %d, dummies hit %d, lookups %d, ratio %f in HashMap %p; size %d num elements %d",
        _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>
typename HashMap<Key, Val, HashFunc, EqualFunc>::size_type HashMap<Key, Val, HashFunc, EqualFunc>::lookupAndCreateIfMissing(const Key &key) {
    const size_type hash = _hash(key);
    size_type ctr = hash & _mask;
    const size_type NONE_FOUND = _mask + 1;
    size_type first_free = NONE_FOUND;
    bool found = false;
    for (size_type perturb = hash; ; perturb >>= HASHMAP_PERTURB_SHIFT) {
        if (_storage[ctr] == nullptr)
            break;
        if (_storage[ctr] == HASHMAP_DUMMY_NODE) {
#ifdef DEBUG_HASH_COLLISIONS
            _dummyHits++;
#endif
            if (first_free == NONE_FOUND)
                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++;
    debug("collisions %d, dummies hit %d, lookups %d, ratio %f in HashMap %p; size %d num elements %d",
        _collisions, _dummyHits, _lookups, ((double) _collisions / (double)_lookups),
        (const void *)this, _mask + 1, _size);
#endif
 
    if (!found && first_free != NONE_FOUND)
        ctr = first_free;
 
    if (!found) {
        if (_storage[ctr])
            _deleted--;
        _storage[ctr] = allocNode(key);
        assert(_storage[ctr] != nullptr);
        _size++;
 
        // Keep the load factor below a certain threshold.
        // Deleted nodes are also counted
        size_type 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] != nullptr);
        }
    }
 
    return ctr;
}
 
template<class Key, class Val, class HashFunc, class EqualFunc>
bool HashMap<Key, Val, HashFunc, EqualFunc>::contains(const Key &key) const {
    size_type ctr = lookup(key);
    return (_storage[ctr] != nullptr);
}
 
template<class Key, class Val, class HashFunc, class EqualFunc>
Val &HashMap<Key, Val, HashFunc, EqualFunc>::operator[](const Key &key) {
    return getOrCreateVal(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>::getOrCreateVal(const Key &key) {
    size_type ctr = lookupAndCreateIfMissing(key);
    assert(_storage[ctr] != nullptr);
    return _storage[ctr]->_value;
}
 
template<class Key, class Val, class HashFunc, class EqualFunc>
Val &HashMap<Key, Val, HashFunc, EqualFunc>::getVal(const Key &key) {
    size_type ctr = lookup(key);
    if (_storage[ctr] != nullptr)
        return _storage[ctr]->_value;
    else
        // In the past getVal() and operator[] used to return the default value for this case.
        // Clarifying the intent by using getValOrDefault() when we query a key that may not be
        // present is a good idea, but we have a lot of legacy code that may need to be updated.
        // So for now only returns an error in non-release builds. Once we are confident all the
        // code has been updated to use the correct function we can remove the RELEASE_BUILD
        // special case.
#ifdef RELEASE_BUILD
        return _defaultVal;
#else
        unknownKeyError(key);
#endif
}
 
template<class Key, class Val, class HashFunc, class EqualFunc>
const Val &HashMap<Key, Val, HashFunc, EqualFunc>::getVal(const Key &key) const {
    size_type ctr = lookup(key);
    if (_storage[ctr] != nullptr)
        return _storage[ctr]->_value;
    else
        // See comment in non-const getVal() above.
#ifdef RELEASE_BUILD
        return _defaultVal;
#else
        unknownKeyError(key);
#endif
}
 
template<class Key, class Val, class HashFunc, class EqualFunc>
const Val &HashMap<Key, Val, HashFunc, EqualFunc>::getValOrDefault(const Key &key) const {
    return getValOrDefault(key, _defaultVal);
}
 
template<class Key, class Val, class HashFunc, class EqualFunc>
const Val &HashMap<Key, Val, HashFunc, EqualFunc>::getValOrDefault(const Key &key, const Val &defaultVal) const {
    size_type ctr = lookup(key);
    if (_storage[ctr] != nullptr)
        return _storage[ctr]->_value;
    else
        return defaultVal;
}
 
template<class Key, class Val, class HashFunc, class EqualFunc>
bool HashMap<Key, Val, HashFunc, EqualFunc>::tryGetVal(const Key &key, Val &out) const {
    size_type ctr = lookup(key);
    if (_storage[ctr] != nullptr) {
        out = _storage[ctr]->_value;
        return true;
    } else {
        return false;
    }
}
 
template<class Key, class Val, class HashFunc, class EqualFunc>
void HashMap<Key, Val, HashFunc, EqualFunc>::setVal(const Key &key, const Val &val) {
    size_type ctr = lookupAndCreateIfMissing(key);
    assert(_storage[ctr] != nullptr);
    _storage[ctr]->_value = val;
}
 
template<class Key, class Val, class HashFunc, class EqualFunc>
void HashMap<Key, Val, HashFunc, EqualFunc>::erase(iterator entry) {
    // Check whether we have a valid iterator
    assert(entry._hashmap == this);
    const size_type ctr = entry._idx;
    assert(ctr <= _mask);
    Node * const node = _storage[ctr];
    assert(node != NULL);
    assert(node != HASHMAP_DUMMY_NODE);
 
    // If we remove a key, we replace it with a dummy node.
    freeNode(node);
    _storage[ctr] = HASHMAP_DUMMY_NODE;
    _size--;
    _deleted++;
}
 
template<class Key, class Val, class HashFunc, class EqualFunc>
void HashMap<Key, Val, HashFunc, EqualFunc>::erase(const Key &key) {
 
    size_type ctr = lookup(key);
    if (_storage[ctr] == nullptr)
        return;
 
    // If we remove a key, we replace it with a dummy node.
    freeNode(_storage[ctr]);
    _storage[ctr] = HASHMAP_DUMMY_NODE;
    _size--;
    _deleted++;
    return;
}
 
#undef HASHMAP_DUMMY_NODE
 
} // End of namespace Common
 
#endif