#ifndef PtexDict_h
#define PtexDict_h
template<class T>
class PtexDict
{
class Entry;
public:
class iterator;
class const_iterator;
friend class iterator;
friend class const_iterator;
typedef const char* key_type;
typedef T mapped_type;
struct value_type {
public:
value_type():
first(0), second() {}
value_type(key_type
f,
const T&
s):
first(f), second(s) {}
T second;
};
public:
PtexDict() : _numEntries(0), _numBuckets(0), _bucketMask(0), _buckets(0) {}
virtual ~PtexDict() { clear(); }
T& operator[](const char* key);
iterator begin()
{
iterator iter;
iter._d = 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;
}
inline iterator
end() {
return iterator( 0,
this, 0 ); }
const_iterator begin() const
{
const_iterator iter;
iter._d = 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;
}
inline const_iterator
end()
const {
return const_iterator( 0,
this, 0 ); }
iterator find(const char* key);
const_iterator find(const char* key) const;
bool erase(const char* key);
iterator erase(iterator iter);
void clear();
int size()
const {
return _numEntries; }
private:
struct Entry {
public:
Entry() : _next(0), _hashval(0), _keylen(0),
_val(_key,T()), _pad(0) {}
private:
Entry(const Entry&);
Entry& operator=(const Entry&);
public:
Entry* _next;
int _hashval;
int _keylen;
value_type _val;
union {
int _pad;
char _key[1];
};
};
PtexDict(const PtexDict&);
PtexDict& operator=(const PtexDict&);
int hash(const char* key, int& keylen) const
{
int hashval = 0;
const char* cp = key;
while ((c = *cp++)) hashval = hashval * 33 +
c;
return hashval;
}
Entry** locate(const char* key, int& keylen, int& hashval) const
{
hashval = hash(key, keylen);
if (!_buckets) return 0;
for (Entry** e = &_buckets[hashval & _bucketMask]; *e; e=&(*e)->_next)
if ((*e)->_hashval == hashval && (*e)->_keylen == keylen &&
streq(key, (*e)->_key, keylen))
return e;
return 0;
}
static inline bool streq(
const char* s1,
const char* s2,
int len)
{
if (((intptr_t)s1 & 3) == 0) {
int len4 = len >> 2;
while (len4--) {
if (*(int*)s1 != *(int*)s2) return 0;
s1 += 4; s2 += 4;
}
len &= 3;
}
while (len--) if (*s1++ != *s2++) return 0;
return 1;
}
void grow();
private:
int _numEntries;
int _numBuckets;
int _bucketMask;
Entry** _buckets;
};
template<class T>
class PtexDict<T>::iterator {
public:
iterator() : _d(0), _e(0), _b(0) {}
iterator(const iterator& iter) :
_d(iter._d), _e(iter._e), _b(iter._b) {}
inline iterator& operator=(const iterator& iter)
{ _e = iter._e; _d = iter._d; _b = iter._b; return *this; }
inline value_type&
operator*()
const {
return getValue(); }
inline value_type* operator->() const { return &getValue(); }
inline operator bool() { return _e != 0; }
inline bool operator==(
const iterator& iter)
const
{ return iter._e == _e; }
inline bool operator!=(
const iterator& iter)
const
{ return iter._e != _e; }
inline bool operator==(
const const_iterator& iter)
const
{ return iter._e == _e; }
inline bool operator!=(
const const_iterator& iter)
const
{ return iter._e != _e; }
iterator& operator++(int);
private:
iterator( Entry** e,
const PtexDict* d,
int b): _d(d), _e(e), _b(b) {}
inline value_type& getValue() const{
if (_e) return (*_e)->_val;
else return _defaultVal;
}
friend class PtexDict;
friend class const_iterator;
const PtexDict* _d;
Entry** _e;
int _b;
static value_type _defaultVal;
};
template<class T> typename PtexDict<T>::value_type PtexDict<T>::iterator::_defaultVal;
template<class T>
class PtexDict<T>::const_iterator {
public:
const_iterator() : _d(0), _e(0), _b(0) {}
const_iterator(const const_iterator& iter) :
_d(iter._d), _e(iter._e), _b(iter._b) {}
const_iterator(const iterator& iter) :
_d(iter._d), _e(iter._e), _b(iter._b) {}
inline const_iterator& operator=(const const_iterator& iter)
{ _e = iter._e; _d = iter._d; _b = iter._b; return *this; }
inline const_iterator& operator=(iterator& iter)
{ _e = iter._e; _d = iter._d; _b = iter._b; return *this; }
inline const value_type&
operator*()
const {
return getValue(); }
inline const value_type* operator->() const { return &getValue(); }
inline operator bool() { return _e != 0; }
inline bool operator==(
const iterator& iter)
const
{ return iter._e == _e; }
inline bool operator!=(
const iterator& iter)
const
{ return iter._e != _e; }
inline bool operator==(
const const_iterator& iter)
const
{ return iter._e == _e; }
inline bool operator!=(
const const_iterator& iter)
const
{ return iter._e != _e; }
const_iterator& operator++(int);
private:
const_iterator( Entry** e,
const PtexDict* d,
int b): _d(d),_e(e),_b(b) {}
inline const value_type& getValue() const{
if (_e) return (*_e)->_val;
else return _defaultVal;
}
friend class PtexDict;
friend class iterator;
const PtexDict* _d;
Entry** _e;
int _b;
static value_type _defaultVal;
};
template<class T> typename PtexDict<T>::value_type PtexDict<T>::const_iterator::_defaultVal;
template<class T>
typename PtexDict<T>::iterator& PtexDict<T>::iterator::operator++(int)
{
if (_e) {
_e = &(*_e)->_next;
if (!*_e) {
for (_b++; _b < _d->_numBuckets; _b++) {
_e = &_d->_buckets[_b];
if (*_e) return *this;
}
_e = 0;
}
}
return *this;
}
template<class T>
typename PtexDict<T>::const_iterator& PtexDict<T>::const_iterator::operator++(int)
{
if (_e) {
_e = &(*_e)->_next;
if (!*_e) {
for (_b++; _b < _d->_numBuckets; _b++) {
_e = &_d->_buckets[_b];
if (*_e) return *this;
}
_e = 0;
}
}
return *this;
}
template<class T>
typename PtexDict<T>::iterator PtexDict<T>::find(const char* key)
{
int keylen, hashval;
Entry** e = locate(key, keylen, hashval);
if (e) return iterator( e, this, hashval & _bucketMask );
}
template<class T>
typename PtexDict<T>::const_iterator PtexDict<T>::find(const char* key) const
{
int keylen, hashval;
Entry** e = locate(key, keylen, hashval);
if (e) return const_iterator( e, this, hashval & _bucketMask );
}
template<class T>
T& PtexDict<T>::operator[](const char* key)
{
int keylen, hashval;
Entry** e = locate(key, keylen, hashval);
if (e) return (*e)->_val.second;
_numEntries++;
if (_numEntries*2 >= _numBuckets) grow();
void* ebuf = malloc( sizeof(Entry) + (keylen) * sizeof(char) );
Entry* ne = new(ebuf) Entry;
Entry** slot = &_buckets[hashval & _bucketMask];
ne->_next = *slot; *slot = ne;
ne->_hashval = hashval;
ne->_keylen = keylen;
memcpy(ne->_key, key, keylen);
ne->_key[keylen] = '\0';
return ne->_val.second;
}
template<class T>
void PtexDict<T>::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[e->_hashval & _bucketMask];
e->_next = *slot; *slot = e;
e = _next;
}
}
free(_buckets);
_buckets = newbuckets;
_numBuckets = newsize;
}
}
template<class T>
bool PtexDict<T>::erase(const char* key)
{
iterator iter = find(key);
if (!iter) return false;
erase(iter);
return true;
}
template<class T>
typename PtexDict<T>::iterator PtexDict<T>::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 T>
void PtexDict<T>::clear()
{
for (iterator i=begin(); i !=
end(); i = erase(i));
free(_buckets);
_buckets = 0;
_numEntries = 0;
_numBuckets = 0;
}
#endif //PtexDict_h