#ifndef PtexHashMap_h
#define PtexHashMap_h
template<typename KeyType, typename DataType, typename HashFn>
class PtexHashMap
{
struct Entry;
public:
typedef KeyType key_type;
typedef DataType data_type;
typedef HashFn hash_fn;
struct value_type {
key_type first;
data_type second;
value_type() : first(), second() {}
value_type(const KeyType& first, const DataType& second)
: first(first), second(second) {}
};
class iterator {
public:
iterator() : e(0), h(0), b(0) {}
iterator(const iterator& iter) : e(iter.e), h(iter.h), b(iter.b) {}
value_type operator*() const {
if (e) return value_type((*e)->key, (*e)->val);
return value_type();
}
value_type* operator->() const {
static value_type v;
v = operator*();
return &v;
}
iterator& operator=(const iterator& iter) {
e = iter.e; h = iter.h; b = iter.b; return *this;
}
bool operator==(const iterator& iter) const { return iter.e == e; }
bool operator!=(const iterator& iter) const { return iter.e != e; }
iterator& operator++(int);
private:
friend class PtexHashMap;
Entry** e;
const PtexHashMap* h;
int b;
};
iterator begin() const
{
iterator iter;
iter.h = this;
for (iter.b = 0; iter.b < _numBuckets; iter.b++) {
iter.e = &_buckets[iter.b];
if (*iter.e) return iter;
}
iter.e = 0;
return iter;
}
iterator end() const
{
iterator iter;
iter.h = this; iter.b = 0; iter.e = 0;
return iter;
}
PtexHashMap() : _numEntries(0), _numBuckets(0), _bucketMask(0), _buckets(0) {}
~PtexHashMap() { clear(); }
DataType& operator[](const KeyType& key);
iterator find(const KeyType& key) const;
bool erase(const KeyType& key);
iterator erase(iterator iter);
void clear();
int size() const { return _numEntries; }
private:
PtexHashMap(const PtexHashMap&);
bool operator=(const PtexHashMap&);
friend class iterator;
struct Entry {
Entry() : val() {}
Entry* next;
KeyType key;
DataType val;
};
Entry** locate(const KeyType& key) const
{
if (!_buckets) return 0;
for (Entry** e = &_buckets[hash(key) & _bucketMask]; *e; e = &(*e)->next)
if ((*e)->key == key)
return e;
return 0;
}
void grow();
int _numEntries;
int _numBuckets;
int _bucketMask;
Entry** _buckets;
HashFn hash;
};
template<class KeyType, class DataType, class HashFn>
typename PtexHashMap<KeyType, DataType, HashFn>::iterator&
PtexHashMap<KeyType, DataType, HashFn>::iterator::operator++(int)
{
if (e) {
e = &(*e)->next;
if (!*e) {
for (b++; b < h->_numBuckets; b++) {
e = &h->_buckets[b];
if (*e) return *this;
}
e = 0;
}
}
return *this;
}
template<class KeyType, class DataType, class HashFn>
typename PtexHashMap<KeyType, DataType, HashFn>::iterator
PtexHashMap<KeyType, DataType, HashFn>::find(const KeyType& key) const
{
iterator iter;
Entry** e = locate(key);
if (e) {
iter.h = this;
iter.e = e;
iter.b = hash(key) & _bucketMask;
} else iter = end();
return iter;
}
template<class KeyType, class DataType, class HashFn>
DataType& PtexHashMap<KeyType, DataType, HashFn>::operator[](const KeyType& key)
{
Entry** e = locate(key);
if (e) return (*e)->val;
_numEntries++;
if (_numEntries*2 >= _numBuckets) grow();
void* ebuf = malloc(sizeof(Entry));
Entry* ne = new(ebuf) Entry;
Entry** slot = &_buckets[hash(key) & _bucketMask];
ne->next = *slot; *slot = ne;
ne->key = key;
return ne->val;
}
template<class KeyType, class DataType, class HashFn>
void PtexHashMap<KeyType, DataType, HashFn>::grow()
{
if (!_buckets) {
_numBuckets = 16;
_bucketMask = _numBuckets - 1;
_buckets = (Entry**) calloc(_numBuckets, sizeof(Entry*));
} else {
int newsize = _numBuckets * 2;
_bucketMask = newsize - 1;
Entry** newbuckets = (Entry**) calloc(newsize, sizeof(Entry*));
for (int i = 0; i < _numBuckets; i++) {
for (Entry* e = _buckets[i]; e;) {
Entry* next = e->next;
Entry** slot = &newbuckets[hash(e->key) & _bucketMask];
e->next = *slot; *slot = e;
e = next;
}
}
free(_buckets);
_buckets = newbuckets;
_numBuckets = newsize;
}
}
template<class KeyType, class DataType, class HashFn>
bool PtexHashMap<KeyType, DataType, HashFn>::erase(const KeyType& key)
{
iterator iter = find(key);
if (iter == end()) return 0;
erase(iter);
return 1;
}
template<class KeyType, class DataType, class HashFn>
typename PtexHashMap<KeyType, DataType, HashFn>::iterator
PtexHashMap<KeyType, DataType, HashFn>::erase(iterator iter)
{
Entry** eptr = iter.e;
if (!eptr) return iter;
Entry* e = *eptr;
Entry* next = e->next;
if (!next) iter++;
*eptr = next;
e->~Entry();
free(e);
_numEntries--;
return iter;
}
template<class KeyType, class DataType, class HashFn>
void PtexHashMap<KeyType, DataType, HashFn>::clear()
{
for (iterator i = begin(); i != end(); i = erase(i));
free(_buckets);
_buckets = 0;
_numEntries = 0;
_numBuckets = 0;
}
#endif