|
Shinya Kitaoka |
810553 |
#pragma once
|
|
Toshihiro Shimizu |
890ddd |
|
|
Toshihiro Shimizu |
890ddd |
#ifndef TCG_HASH_H
|
|
Toshihiro Shimizu |
890ddd |
#define TCG_HASH_H
|
|
Toshihiro Shimizu |
890ddd |
|
|
Toshihiro Shimizu |
890ddd |
// tcg includes
|
|
Toshihiro Shimizu |
890ddd |
#include "list.h"
|
|
Toshihiro Shimizu |
890ddd |
|
|
Toshihiro Shimizu |
890ddd |
namespace tcg
|
|
Toshihiro Shimizu |
890ddd |
{
|
|
Toshihiro Shimizu |
890ddd |
|
|
Toshihiro Shimizu |
890ddd |
//============================================================================================
|
|
Toshihiro Shimizu |
890ddd |
|
|
Toshihiro Shimizu |
890ddd |
/*!
|
|
Toshihiro Shimizu |
890ddd |
The hash class implements a hash map using tcg lists
|
|
Toshihiro Shimizu |
890ddd |
*/
|
|
Toshihiro Shimizu |
890ddd |
|
|
Toshihiro Shimizu |
890ddd |
template <typename &)="" (*)(const="" hash_functor="size_t" k="" k,="" t,="" typename=""></typename>
|
|
Toshihiro Shimizu |
890ddd |
class hash
|
|
Toshihiro Shimizu |
890ddd |
{
|
|
Toshihiro Shimizu |
890ddd |
public:
|
|
Toshihiro Shimizu |
890ddd |
typedef K key_type;
|
|
Toshihiro Shimizu |
890ddd |
typedef T value_type;
|
|
Toshihiro Shimizu |
890ddd |
typedef Hash_functor hash_type;
|
|
Toshihiro Shimizu |
890ddd |
|
|
Toshihiro Shimizu |
890ddd |
struct BucketNode {
|
|
Toshihiro Shimizu |
890ddd |
K m_key;
|
|
Toshihiro Shimizu |
890ddd |
T m_val;
|
|
Toshihiro Shimizu |
890ddd |
size_t m_next;
|
|
Toshihiro Shimizu |
890ddd |
size_t m_prev;
|
|
Toshihiro Shimizu |
890ddd |
|
|
Toshihiro Shimizu |
890ddd |
BucketNode(const K &key, const T &val) : m_key(key), m_val(val), m_next(-1), m_prev(-1) {}
|
|
Toshihiro Shimizu |
890ddd |
BucketNode(const std::pair<k, t=""> &pair) : m_key(pair.first), m_val(pair.second), m_next(-1), m_prev(-1) {}</k,>
|
|
Toshihiro Shimizu |
890ddd |
~BucketNode() {}
|
|
Toshihiro Shimizu |
890ddd |
};
|
|
Toshihiro Shimizu |
890ddd |
|
|
Toshihiro Shimizu |
890ddd |
typedef typename tcg::list<bucketnode>::size_t size_t;</bucketnode>
|
|
Toshihiro Shimizu |
890ddd |
|
|
Toshihiro Shimizu |
890ddd |
typedef typename tcg::list<bucketnode>::iterator iterator;</bucketnode>
|
|
Toshihiro Shimizu |
890ddd |
typedef typename tcg::list<bucketnode>::const_iterator const_iterator;</bucketnode>
|
|
Toshihiro Shimizu |
890ddd |
|
|
Toshihiro Shimizu |
890ddd |
private:
|
|
Toshihiro Shimizu |
890ddd |
std::vector<size_t> m_bucketsIdx;</size_t>
|
|
Toshihiro Shimizu |
890ddd |
tcg::list<bucketnode> m_items;</bucketnode>
|
|
Toshihiro Shimizu |
890ddd |
Hash_functor m_hash;
|
|
Toshihiro Shimizu |
890ddd |
|
|
Toshihiro Shimizu |
890ddd |
private:
|
|
Toshihiro Shimizu |
890ddd |
bool createItem(const K &key, const T &val)
|
|
Toshihiro Shimizu |
890ddd |
{
|
|
Toshihiro Shimizu |
890ddd |
m_items.push_back(BucketNode(key, val));
|
|
Toshihiro Shimizu |
890ddd |
|
|
Toshihiro Shimizu |
890ddd |
size_t itemsCount = m_items.size(), bucketsCount = m_bucketsIdx.size();
|
|
Toshihiro Shimizu |
890ddd |
if (itemsCount > bucketsCount) {
|
|
Toshihiro Shimizu |
890ddd |
do
|
|
Toshihiro Shimizu |
890ddd |
bucketsCount = 2 * bucketsCount + 1; // Please, note that 2n here would be moronic
|
|
Toshihiro Shimizu |
890ddd |
while (itemsCount > bucketsCount);
|
|
Toshihiro Shimizu |
890ddd |
|
|
Toshihiro Shimizu |
890ddd |
rehash(bucketsCount);
|
|
Toshihiro Shimizu |
890ddd |
return true;
|
|
Toshihiro Shimizu |
890ddd |
}
|
|
Toshihiro Shimizu |
890ddd |
return false;
|
|
Toshihiro Shimizu |
890ddd |
}
|
|
Toshihiro Shimizu |
890ddd |
|
|
Toshihiro Shimizu |
890ddd |
size_t touchKey(const K &key, const T &val = T())
|
|
Toshihiro Shimizu |
890ddd |
{
|
|
Toshihiro Shimizu |
890ddd |
size_t hashValue = m_hash(key) % m_bucketsIdx.size();
|
|
Toshihiro Shimizu |
890ddd |
size_t bucketIdx = m_bucketsIdx[hashValue];
|
|
Toshihiro Shimizu |
890ddd |
size_t oldIdx = _neg;
|
|
Toshihiro Shimizu |
890ddd |
|
|
Toshihiro Shimizu |
890ddd |
if (bucketIdx == _neg) {
|
|
Toshihiro Shimizu |
890ddd |
//A new bucket is created
|
|
Toshihiro Shimizu |
890ddd |
bool rehashed = createItem(key, val);
|
|
Toshihiro Shimizu |
890ddd |
bucketIdx = m_items.last().m_idx;
|
|
Toshihiro Shimizu |
890ddd |
|
|
Toshihiro Shimizu |
890ddd |
if (!rehashed)
|
|
Toshihiro Shimizu |
890ddd |
//Need to manually update the stored bucket index
|
|
Toshihiro Shimizu |
890ddd |
m_bucketsIdx[hashValue] = bucketIdx;
|
|
Toshihiro Shimizu |
890ddd |
|
|
Toshihiro Shimizu |
890ddd |
return bucketIdx;
|
|
Toshihiro Shimizu |
890ddd |
} else {
|
|
Toshihiro Shimizu |
890ddd |
//Bucket exists - search key in it
|
|
Toshihiro Shimizu |
890ddd |
for (;
|
|
Toshihiro Shimizu |
890ddd |
bucketIdx != _neg && m_items[bucketIdx].m_key != key;
|
|
Toshihiro Shimizu |
890ddd |
oldIdx = bucketIdx, bucketIdx = m_items[bucketIdx].m_next)
|
|
Toshihiro Shimizu |
890ddd |
;
|
|
Toshihiro Shimizu |
890ddd |
}
|
|
Toshihiro Shimizu |
890ddd |
|
|
Toshihiro Shimizu |
890ddd |
if (bucketIdx == _neg) {
|
|
Toshihiro Shimizu |
890ddd |
//Key was not found - create an item and insert it
|
|
Toshihiro Shimizu |
890ddd |
bool rehashed = createItem(key, val);
|
|
Toshihiro Shimizu |
890ddd |
bucketIdx = m_items.last().m_idx;
|
|
Toshihiro Shimizu |
890ddd |
|
|
Toshihiro Shimizu |
890ddd |
if (!rehashed && oldIdx != _neg) {
|
|
Toshihiro Shimizu |
890ddd |
//Need to relink manually
|
|
Toshihiro Shimizu |
890ddd |
m_items[oldIdx].m_next = bucketIdx;
|
|
Toshihiro Shimizu |
890ddd |
m_items[bucketIdx].m_prev = oldIdx;
|
|
Toshihiro Shimizu |
890ddd |
}
|
|
Toshihiro Shimizu |
890ddd |
}
|
|
Toshihiro Shimizu |
890ddd |
|
|
Toshihiro Shimizu |
890ddd |
return bucketIdx;
|
|
Toshihiro Shimizu |
890ddd |
}
|
|
Toshihiro Shimizu |
890ddd |
|
|
Toshihiro Shimizu |
890ddd |
public:
|
|
Toshihiro Shimizu |
890ddd |
// NOTE: The defaulted 89 is a *good* initial buckets size when expanding by the (2n+1) rule.
|
|
Toshihiro Shimizu |
890ddd |
// See http://www.concentric.net/~ttwang/tech/hashsize.htm for details
|
|
Toshihiro Shimizu |
890ddd |
|
|
Toshihiro Shimizu |
890ddd |
hash(const Hash_functor &func = Hash_functor(), size_t bucketsCount = 89)
|
|
Toshihiro Shimizu |
890ddd |
: m_bucketsIdx(bucketsCount, _neg), m_hash(func) {}
|
|
Toshihiro Shimizu |
890ddd |
|
|
Toshihiro Shimizu |
890ddd |
template <typename forit=""></typename>
|
|
Toshihiro Shimizu |
890ddd |
hash(ForIt begin, ForIt end, const Hash_functor &func = Hash_functor(), size_t bucketsCount = 89)
|
|
Toshihiro Shimizu |
890ddd |
: m_items(begin, end), m_hash(func)
|
|
Toshihiro Shimizu |
890ddd |
{
|
|
Toshihiro Shimizu |
890ddd |
for (size_t nCount = m_items.nodesCount(); bucketsCount < nCount;
|
|
Toshihiro Shimizu |
890ddd |
bucketsCount = 2 * bucketsCount + 1)
|
|
Toshihiro Shimizu |
890ddd |
;
|
|
Toshihiro Shimizu |
890ddd |
rehash(bucketsCount);
|
|
Toshihiro Shimizu |
890ddd |
}
|
|
Toshihiro Shimizu |
890ddd |
|
|
Toshihiro Shimizu |
890ddd |
//! Constructs from a range of (index, value) item pairs
|
|
Toshihiro Shimizu |
890ddd |
template <typename bidit=""></typename>
|
|
Toshihiro Shimizu |
890ddd |
hash(BidIt begin, BidIt end, size_t nodesCount, const Hash_functor &func = Hash_functor(), size_t bucketsCount = 89)
|
|
Toshihiro Shimizu |
890ddd |
: m_items(begin, end, nodesCount), m_hash(func)
|
|
Toshihiro Shimizu |
890ddd |
{
|
|
Toshihiro Shimizu |
890ddd |
for (size_t nCount = m_items.nodesCount(); bucketsCount < nCount;
|
|
Toshihiro Shimizu |
890ddd |
bucketsCount = 2 * bucketsCount + 1)
|
|
Toshihiro Shimizu |
890ddd |
;
|
|
Toshihiro Shimizu |
890ddd |
rehash(bucketsCount);
|
|
Toshihiro Shimizu |
890ddd |
}
|
|
Toshihiro Shimizu |
890ddd |
|
|
Toshihiro Shimizu |
890ddd |
//--------------------------------------------------------------------------
|
|
Toshihiro Shimizu |
890ddd |
|
|
Toshihiro Shimizu |
890ddd |
void rehash(size_t newSize)
|
|
Toshihiro Shimizu |
890ddd |
{
|
|
Toshihiro Shimizu |
890ddd |
m_bucketsIdx.clear();
|
|
Toshihiro Shimizu |
890ddd |
m_bucketsIdx.resize(newSize, _neg);
|
|
Toshihiro Shimizu |
890ddd |
|
|
Toshihiro Shimizu |
890ddd |
size_t bucketIdx;
|
|
Toshihiro Shimizu |
890ddd |
|
|
Toshihiro Shimizu |
890ddd |
iterator it, iEnd = end();
|
|
Toshihiro Shimizu |
890ddd |
for (it = begin(); it != iEnd; ++it) {
|
|
Toshihiro Shimizu |
890ddd |
bucketIdx = m_hash(it->m_key) % newSize;
|
|
Toshihiro Shimizu |
890ddd |
size_t &idx = m_bucketsIdx[bucketIdx];
|
|
Toshihiro Shimizu |
890ddd |
|
|
Toshihiro Shimizu |
890ddd |
it->m_next = idx;
|
|
Toshihiro Shimizu |
890ddd |
it->m_prev = _neg;
|
|
Toshihiro Shimizu |
890ddd |
|
|
Toshihiro Shimizu |
890ddd |
if (idx != _neg)
|
|
Toshihiro Shimizu |
890ddd |
m_items[idx].m_prev = it.m_idx;
|
|
Toshihiro Shimizu |
890ddd |
idx = it.m_idx;
|
|
Toshihiro Shimizu |
890ddd |
}
|
|
Toshihiro Shimizu |
890ddd |
}
|
|
Toshihiro Shimizu |
890ddd |
|
|
Toshihiro Shimizu |
890ddd |
//--------------------------------------------------------------------------
|
|
Toshihiro Shimizu |
890ddd |
|
|
Toshihiro Shimizu |
890ddd |
size_t size() const { return m_items.size(); }
|
|
Toshihiro Shimizu |
890ddd |
bool empty() { return size() == 0; }
|
|
Toshihiro Shimizu |
890ddd |
|
|
Toshihiro Shimizu |
890ddd |
void clear()
|
|
Toshihiro Shimizu |
890ddd |
{
|
|
Toshihiro Shimizu |
890ddd |
m_items.clear();
|
|
Toshihiro Shimizu |
890ddd |
m_bucketsIdx.clear();
|
|
Toshihiro Shimizu |
890ddd |
m_bucketsIdx.resize(1, _neg);
|
|
Toshihiro Shimizu |
890ddd |
}
|
|
Toshihiro Shimizu |
890ddd |
|
|
Toshihiro Shimizu |
890ddd |
//--------------------------------------------------------------------------
|
|
Toshihiro Shimizu |
890ddd |
|
|
Toshihiro Shimizu |
890ddd |
iterator begin() { return m_items.begin(); }
|
|
Toshihiro Shimizu |
890ddd |
iterator last() { return m_items.last(); }
|
|
Toshihiro Shimizu |
890ddd |
iterator end() { return m_items.end(); }
|
|
Toshihiro Shimizu |
890ddd |
|
|
Toshihiro Shimizu |
890ddd |
//--------------------------------------------------------------------------
|
|
Toshihiro Shimizu |
890ddd |
|
|
Toshihiro Shimizu |
890ddd |
const_iterator begin() const { return m_items.begin(); }
|
|
Toshihiro Shimizu |
890ddd |
const_iterator last() const { return m_items.last(); }
|
|
Toshihiro Shimizu |
890ddd |
const_iterator end() const { return m_items.end(); }
|
|
Toshihiro Shimizu |
890ddd |
|
|
Toshihiro Shimizu |
890ddd |
//--------------------------------------------------------------------------
|
|
Toshihiro Shimizu |
890ddd |
|
|
Toshihiro Shimizu |
890ddd |
iterator find(const K &key)
|
|
Toshihiro Shimizu |
890ddd |
{
|
|
Toshihiro Shimizu |
890ddd |
size_t hashValue = m_hash(key) % m_bucketsIdx.size();
|
|
Toshihiro Shimizu |
890ddd |
size_t bucketIdx = m_bucketsIdx[hashValue];
|
|
Toshihiro Shimizu |
890ddd |
|
|
Toshihiro Shimizu |
890ddd |
if (bucketIdx == _neg)
|
|
Toshihiro Shimizu |
890ddd |
return end();
|
|
Toshihiro Shimizu |
890ddd |
|
|
Toshihiro Shimizu |
890ddd |
for (;
|
|
Toshihiro Shimizu |
890ddd |
bucketIdx != _neg && m_items[bucketIdx].m_key != key;
|
|
Toshihiro Shimizu |
890ddd |
bucketIdx = m_items[bucketIdx].m_next)
|
|
Toshihiro Shimizu |
890ddd |
;
|
|
Toshihiro Shimizu |
890ddd |
|
|
Toshihiro Shimizu |
890ddd |
return bucketIdx == _neg ? end() : iterator(&m_items, bucketIdx);
|
|
Toshihiro Shimizu |
890ddd |
}
|
|
Toshihiro Shimizu |
890ddd |
|
|
Toshihiro Shimizu |
890ddd |
const_iterator find(const K &key) const
|
|
Toshihiro Shimizu |
890ddd |
{
|
|
Toshihiro Shimizu |
890ddd |
return const_iterator(&m_items, const_cast<hash *="">(this)->find(key).m_idx);</hash>
|
|
Toshihiro Shimizu |
890ddd |
}
|
|
Toshihiro Shimizu |
890ddd |
|
|
Toshihiro Shimizu |
890ddd |
//--------------------------------------------------------------------------
|
|
Toshihiro Shimizu |
890ddd |
|
|
Toshihiro Shimizu |
890ddd |
iterator insert(const K &key, const T &val)
|
|
Toshihiro Shimizu |
890ddd |
{
|
|
Toshihiro Shimizu |
890ddd |
size_t idx = touchKey(key);
|
|
Toshihiro Shimizu |
890ddd |
m_items[idx].m_val = val;
|
|
Toshihiro Shimizu |
890ddd |
return iterator(&m_items, idx);
|
|
Toshihiro Shimizu |
890ddd |
}
|
|
Toshihiro Shimizu |
890ddd |
|
|
Toshihiro Shimizu |
890ddd |
//--------------------------------------------------------------------------
|
|
Toshihiro Shimizu |
890ddd |
|
|
Toshihiro Shimizu |
890ddd |
//!\warning Assignment of the kind hash_map[i1] = hash_map[i2] are DANGEROUS! The
|
|
Toshihiro Shimizu |
890ddd |
//!reference returned on the right may be INVALIDATED if the first key is inserted!
|
|
Toshihiro Shimizu |
890ddd |
T &operator[](const K &key)
|
|
Toshihiro Shimizu |
890ddd |
{
|
|
Toshihiro Shimizu |
890ddd |
return m_items[touchKey(key)].m_val;
|
|
Toshihiro Shimizu |
890ddd |
}
|
|
Toshihiro Shimizu |
890ddd |
|
|
Toshihiro Shimizu |
890ddd |
//--------------------------------------------------------------------------
|
|
Toshihiro Shimizu |
890ddd |
|
|
Toshihiro Shimizu |
890ddd |
//!\warning The same remark of operator[] applies here!
|
|
Toshihiro Shimizu |
890ddd |
T &touch(const K &key, const T &val)
|
|
Toshihiro Shimizu |
890ddd |
{
|
|
Toshihiro Shimizu |
890ddd |
return m_items[touchKey(key, val)].m_val;
|
|
Toshihiro Shimizu |
890ddd |
}
|
|
Toshihiro Shimizu |
890ddd |
|
|
Toshihiro Shimizu |
890ddd |
//--------------------------------------------------------------------------
|
|
Toshihiro Shimizu |
890ddd |
|
|
Toshihiro Shimizu |
890ddd |
iterator insert(const std::pair<k, t=""> &pair)</k,>
|
|
Toshihiro Shimizu |
890ddd |
{
|
|
Toshihiro Shimizu |
890ddd |
return insert(pair.first, pair.second);
|
|
Toshihiro Shimizu |
890ddd |
}
|
|
Toshihiro Shimizu |
890ddd |
|
|
Toshihiro Shimizu |
890ddd |
//--------------------------------------------------------------------------
|
|
Toshihiro Shimizu |
890ddd |
|
|
Toshihiro Shimizu |
890ddd |
void erase(iterator it)
|
|
Toshihiro Shimizu |
890ddd |
{
|
|
Toshihiro Shimizu |
890ddd |
BucketNode &node = *it;
|
|
Toshihiro Shimizu |
890ddd |
if (node.m_next != _neg)
|
|
Toshihiro Shimizu |
890ddd |
m_items[node.m_next].m_prev = node.m_prev;
|
|
Toshihiro Shimizu |
890ddd |
if (node.m_prev != _neg)
|
|
Toshihiro Shimizu |
890ddd |
m_items[node.m_prev].m_next = node.m_next;
|
|
Toshihiro Shimizu |
890ddd |
else
|
|
Toshihiro Shimizu |
890ddd |
m_bucketsIdx[m_hash(node.m_key) % m_bucketsIdx.size()] = _neg;
|
|
Toshihiro Shimizu |
890ddd |
|
|
Toshihiro Shimizu |
890ddd |
m_items.erase(it);
|
|
Toshihiro Shimizu |
890ddd |
}
|
|
Toshihiro Shimizu |
890ddd |
|
|
Toshihiro Shimizu |
890ddd |
//--------------------------------------------------------------------------
|
|
Toshihiro Shimizu |
890ddd |
|
|
Toshihiro Shimizu |
890ddd |
void erase(const K &key)
|
|
Toshihiro Shimizu |
890ddd |
{
|
|
Toshihiro Shimizu |
890ddd |
iterator it = find(key);
|
|
Toshihiro Shimizu |
890ddd |
if (it != end())
|
|
Toshihiro Shimizu |
890ddd |
erase(it);
|
|
Toshihiro Shimizu |
890ddd |
}
|
|
Toshihiro Shimizu |
890ddd |
|
|
Toshihiro Shimizu |
890ddd |
//--------------------------------------------------------------------------
|
|
Toshihiro Shimizu |
890ddd |
|
|
Toshihiro Shimizu |
890ddd |
friend void swap(hash &a, hash &b)
|
|
Toshihiro Shimizu |
890ddd |
{
|
|
Toshihiro Shimizu |
890ddd |
using std::swap;
|
|
Toshihiro Shimizu |
890ddd |
|
|
Toshihiro Shimizu |
890ddd |
a.m_bucketsIdx.swap(b.m_bucketsIdx);
|
|
Toshihiro Shimizu |
890ddd |
swap(a.m_items, b.m_items);
|
|
Toshihiro Shimizu |
890ddd |
swap(a.m_hash, b.m_hash);
|
|
Toshihiro Shimizu |
890ddd |
}
|
|
Toshihiro Shimizu |
890ddd |
|
|
Toshihiro Shimizu |
890ddd |
//--------------------------------------------------------------------------
|
|
Toshihiro Shimizu |
890ddd |
|
|
Toshihiro Shimizu |
890ddd |
const tcg::list<bucketnode> &items() const { return m_items; }</bucketnode>
|
|
Toshihiro Shimizu |
890ddd |
|
|
Toshihiro Shimizu |
890ddd |
//--------------------------------------------------------------------------
|
|
Toshihiro Shimizu |
890ddd |
|
|
Toshihiro Shimizu |
890ddd |
const std::vector<size_t> &buckets() const { return m_bucketsIdx; }</size_t>
|
|
Toshihiro Shimizu |
890ddd |
|
|
Toshihiro Shimizu |
890ddd |
//--------------------------------------------------------------------------
|
|
Toshihiro Shimizu |
890ddd |
|
|
Toshihiro Shimizu |
890ddd |
const Hash_functor &hashFunctor() const { return m_hash; }
|
|
Toshihiro Shimizu |
890ddd |
|
|
Toshihiro Shimizu |
890ddd |
//!Remember to rehash() if the hash functor changes
|
|
Toshihiro Shimizu |
890ddd |
Hash_functor &hashFunctor() { return m_hash; }
|
|
Toshihiro Shimizu |
890ddd |
};
|
|
Toshihiro Shimizu |
890ddd |
|
|
Toshihiro Shimizu |
890ddd |
} //namespace tcg
|
|
Toshihiro Shimizu |
890ddd |
|
|
Toshihiro Shimizu |
890ddd |
#endif // TCG_HASH_H
|