Hashing.h

Go to the documentation of this file.

 
#pragma once
 
#include <ogdf/basic/basic.h>
#include <ogdf/basic/memory.h>
 
#include <cmath>
#include <cstddef>
#include <limits>
#include <string>
 
namespace ogdf {
 
 
class OGDF_EXPORT HashElementBase {
    friend class HashingBase;
 
    HashElementBase* m_next; 
    size_t m_hashValue; 
 
public:
    explicit HashElementBase(size_t hashValue) : m_next(nullptr), m_hashValue(hashValue) { }
 
    HashElementBase* next() const { return m_next; }
 
    size_t hashValue() const { return m_hashValue; }
 
    OGDF_NEW_DELETE
};
 
class OGDF_EXPORT HashingBase {
protected:
    int m_tableSize; 
    int m_hashMask; 
    int m_minTableSize; 
    int m_tableSizeLow; 
    int m_tableSizeHigh; 
    int m_count; 
    HashElementBase** m_table; 
 
public:
    explicit HashingBase(int minTableSize);
 
    HashingBase(const HashingBase& H);
 
    virtual ~HashingBase();
 
    void resize(int newTableSize);
 
    void insert(HashElementBase* pElement);
 
    void del(HashElementBase* pElement);
 
    void clear();
 
    HashingBase& operator=(const HashingBase& H);
 
    int size() const { return m_count; }
 
    int empty() const { return m_count == 0; }
 
    HashElementBase* firstListElement(size_t hashValue) const {
        return *(m_table + (hashValue & m_hashMask));
    }
 
    HashElementBase* firstElement(HashElementBase*** pList) const;
 
    HashElementBase* nextElement(HashElementBase*** pList, HashElementBase* pElement) const;
 
protected:
    void destroyAll();
 
    virtual void destroy(HashElementBase* pElement) = 0;
 
    virtual HashElementBase* copy(HashElementBase* pElement) const = 0;
 
private:
    void init(int tableSize);
 
    void copyAll(const HashingBase& H);
};
 
template<class K, class I>
class HashElement : public HashElementBase {
    K m_key; 
    I m_info; 
 
public:
    HashElement(size_t hashValue, const K& key, const I& info)
        : HashElementBase(hashValue), m_key(key), m_info(info) { }
 
    HashElement<K, I>* next() const { return (HashElement<K, I>*)HashElementBase::next(); }
 
    const K& key() const { return m_key; }
 
    const I& info() const { return m_info; }
 
    I& info() { return m_info; }
 
    OGDF_NEW_DELETE
};
 
 
template<class K, class I, class H>
class HashConstIterator;
 
template<class K>
class DefHashFunc {
public:
    size_t hash(const K& key) const { return size_t(key); }
};
 
template<>
class DefHashFunc<void*> {
public:
    size_t hash(const void*& key) const { return size_t(key && 0xffffffff); }
};
 
template<>
class DefHashFunc<double> {
public:
    size_t hash(const double& key) const {
        int dummy;
        return (size_t)((double)std::numeric_limits<size_t>::max() * frexp(key, &dummy));
    }
};
 
template<>
class DefHashFunc<string> {
public:
    size_t hash(const string& key) const;
};
 
 
template<class K, class I, class H = DefHashFunc<K>>
class Hashing : private HashingBase {
    friend class HashConstIterator<K, I, H>;
    H m_hashFunc; 
 
public:
    using const_iterator = HashConstIterator<K, I, H>;
 
    explicit Hashing(int minTableSize = 256, const H& hashFunc = H())
        : HashingBase(minTableSize), m_hashFunc(hashFunc) { }
 
    Hashing(const Hashing<K, I, H>& h) = default;
 
    ~Hashing() { HashingBase::destroyAll(); }
 
    int size() const { return HashingBase::size(); }
 
    bool empty() const { return HashingBase::size() == 0; }
 
    bool member(const K& key) const { return lookup(key) != nullptr; }
 
    HashConstIterator<K, I, H> begin() const;
 
    HashElement<K, I>* lookup(const K& key) const {
        HashElement<K, I>* pElement = (HashElement<K, I>*)firstListElement(m_hashFunc.hash(key));
        for (; pElement; pElement = pElement->next()) {
            if (pElement->key() == key) {
                return pElement;
            }
        }
 
        return nullptr;
    }
 
    Hashing<K, I, H>& operator=(const Hashing<K, I, H>& hashing) = default;
 
    HashElement<K, I>* insert(const K& key, const I& info) {
        HashElement<K, I>* pElement = lookup(key);
 
        if (pElement) {
            pElement->info() = info;
        } else {
            HashingBase::insert(pElement = new HashElement<K, I>(m_hashFunc.hash(key), key, info));
        }
 
        return pElement;
    }
 
    HashElement<K, I>* insertByNeed(const K& key, const I& info) {
        HashElement<K, I>* pElement = lookup(key);
 
        if (!pElement) {
            HashingBase::insert(pElement = new HashElement<K, I>(m_hashFunc.hash(key), key, info));
        }
 
        return pElement;
    }
 
    HashElement<K, I>* fastInsert(const K& key, const I& info) {
        HashElement<K, I>* pElement = new HashElement<K, I>(m_hashFunc.hash(key), key, info);
        HashingBase::insert(pElement);
        return pElement;
    }
 
    void del(const K& key) {
        HashElement<K, I>* pElement = lookup(key);
        if (pElement) {
            HashingBase::del(pElement);
            delete pElement;
        }
    }
 
    void clear() { HashingBase::clear(); }
 
protected:
    HashElement<K, I>* firstElement(HashElement<K, I>*** pList) const {
        return (HashElement<K, I>*)(HashingBase::firstElement((HashElementBase***)pList));
    }
 
    HashElement<K, I>* nextElement(HashElement<K, I>*** pList, HashElement<K, I>* pElement) const {
        return (HashElement<K, I>*)(HashingBase::nextElement((HashElementBase***)pList, pElement));
    }
 
private:
    virtual void destroy(HashElementBase* pElement) override {
        delete (HashElement<K, I>*)(pElement);
    }
 
    virtual HashElementBase* copy(HashElementBase* pElement) const override {
        HashElement<K, I>* pX = (HashElement<K, I>*)(pElement);
        return new HashElement<K, I>(pX->hashValue(), pX->key(), pX->info());
    }
};
 
template<class K, class I, class H = DefHashFunc<K>>
class HashConstIterator {
    HashElement<K, I>* m_pElement; 
    HashElement<K, I>** m_pList; 
    const Hashing<K, I, H>* m_pHashing; 
 
public:
    HashConstIterator() : m_pElement(nullptr), m_pList(nullptr), m_pHashing(nullptr) { }
 
    HashConstIterator(HashElement<K, I>* pElement, HashElement<K, I>** pList,
            const Hashing<K, I, H>* pHashing)
        : m_pElement(pElement), m_pList(pList), m_pHashing(pHashing) { }
 
    HashConstIterator(const HashConstIterator<K, I, H>& it)
        : m_pElement(it.m_pElement), m_pList(it.m_pList), m_pHashing(it.m_pHashing) { }
 
    HashConstIterator& operator=(const HashConstIterator<K, I, H>& it) {
        m_pElement = it.m_pElement;
        m_pList = it.m_pList;
        m_pHashing = it.m_pHashing;
        return *this;
    }
 
    bool valid() const { return m_pElement != nullptr; }
 
    const K& key() const { return m_pElement->key(); }
 
    const I& info() const { return m_pElement->info(); }
 
    friend bool operator==(const HashConstIterator<K, I, H>& it1,
            const HashConstIterator<K, I, H>& it2) {
        return it1.m_pElement == it2.m_pElement;
    }
 
    friend bool operator!=(const HashConstIterator<K, I, H>& it1,
            const HashConstIterator<K, I, H>& it2) {
        return it1.m_pElement != it2.m_pElement;
    }
 
    HashConstIterator<K, I, H>& operator++() {
        m_pElement = m_pHashing->nextElement(&m_pList, m_pElement);
        return *this;
    }
};
 
template<class K, class I, class H>
inline HashConstIterator<K, I, H> Hashing<K, I, H>::begin() const {
    HashElement<K, I>*pElement, **pList;
    pElement = firstElement(&pList);
    return HashConstIterator<K, I, H>(pElement, pList, this);
}
 
}