diff options
Diffstat (limited to 'Build/source/utils/lcdf-typetools/include/lcdf/hashmap.hh')
-rw-r--r-- | Build/source/utils/lcdf-typetools/include/lcdf/hashmap.hh | 223 |
1 files changed, 223 insertions, 0 deletions
diff --git a/Build/source/utils/lcdf-typetools/include/lcdf/hashmap.hh b/Build/source/utils/lcdf-typetools/include/lcdf/hashmap.hh new file mode 100644 index 00000000000..c1f1339b976 --- /dev/null +++ b/Build/source/utils/lcdf-typetools/include/lcdf/hashmap.hh @@ -0,0 +1,223 @@ +#ifndef LCDF_HASHMAP_HH +#define LCDF_HASHMAP_HH +#include <assert.h> + +// K AND V REQUIREMENTS: +// +// K::K() +// K::operator bool() const +// Must have (bool)(K()) == false +// and no k with (bool)k == false is stored. +// K & K::operator=(const K &) +// k1 == k2 +// unsigned hashcode(const K &) +// If hashcode(k1) != hashcode(k2), then k1 != k2. +// +// V::V() +// V & V::operator=(const V &) + +template <class K, class V> class _HashMap_const_iterator; +template <class K, class V> class _HashMap_iterator; + +template <class K, class V> +class HashMap { public: + + HashMap(); + explicit HashMap(const V &); + HashMap(const HashMap<K, V> &); + ~HashMap() { delete[] _e; } + + int size() const { return _n; } + bool empty() const { return _n == 0; } + int capacity() const { return _capacity; } + void set_default_value(const V &v) { _default_value = v; } + + typedef _HashMap_const_iterator<K, V> const_iterator; + typedef _HashMap_iterator<K, V> iterator; + + inline const_iterator begin() const; + inline iterator begin(); + inline const_iterator end() const; + inline iterator end(); + + inline const V &find(const K &) const; + inline V *findp(const K &) const; + inline const V &operator[](const K &k) const; + V &find_force(const K &); + + bool insert(const K &, const V &); + void clear(); + + HashMap<K, V> &operator=(const HashMap<K, V> &); + void swap(HashMap<K, V> &); + + void resize(int size) { increase(size); } + + struct Pair { + K key; + V value; + Pair() : key(), value() { } + }; + + private: + + int _capacity; + int _grow_limit; + int _n; + Pair *_e; + V _default_value; + + void increase(int); + inline void check_capacity(); + inline int bucket(const K &) const; + + friend class _HashMap_const_iterator<K, V>; + friend class _HashMap_iterator<K, V>; + +}; + +template <class K, class V> +class _HashMap_const_iterator { public: + typedef _HashMap_const_iterator const_iterator; + typedef typename HashMap<K, V>::Pair Pair; + + operator bool() const { return _pos < _hm->_capacity; } + bool operator!() const { return _pos >= _hm->_capacity; } + + void operator++(int); + void operator++() { (*this)++; } + + const K &key() const { return _hm->_e[_pos].key; } + const V &value() const { return _hm->_e[_pos].value; } + const Pair &pair() const { return _hm->_e[_pos]; } + + inline bool operator==(const const_iterator &) const; + inline bool operator!=(const const_iterator &) const; + + private: + const HashMap<K, V> *_hm; + int _pos; + _HashMap_const_iterator(const HashMap<K, V> *, int); + friend class HashMap<K, V>; + friend class _HashMap_iterator<K, V>; +}; + +template <class K, class V> +class _HashMap_iterator : public _HashMap_const_iterator<K, V> { public: + typedef _HashMap_iterator iterator; + + V &value() const { return this->_hm->_e[this->_pos].value; } + + private: + _HashMap_iterator(const HashMap<K, V> *hm, int pos) : _HashMap_const_iterator<K, V>(hm, pos) { } + friend class HashMap<K, V>; +}; + + +template <class K, class V> +inline int +HashMap<K, V>::bucket(const K &key) const +{ + assert(key); + unsigned hc = hashcode(key); + int i = hc & (_capacity - 1); + int j = ((hc >> 6) & (_capacity - 1)) | 1; + + while (_e[i].key && !(_e[i].key == key)) + i = (i + j) & (_capacity - 1); + + return i; +} + +template <class K, class V> +inline const V & +HashMap<K, V>::find(const K &key) const +{ + int i = bucket(key); + const V *v = (_e[i].key ? &_e[i].value : &_default_value); + return *v; +} + +template <class K, class V> +inline const V & +HashMap<K, V>::operator[](const K &key) const +{ + return find(key); +} + +template <class K, class V> +inline V * +HashMap<K, V>::findp(const K &key) const +{ + int i = bucket(key); + return _e[i].key ? &_e[i].value : 0; +} + +template <class K, class V> +inline _HashMap_const_iterator<K, V> +HashMap<K, V>::begin() const +{ + return const_iterator(this, 0); +} + +template <class K, class V> +inline _HashMap_const_iterator<K, V> +HashMap<K, V>::end() const +{ + return const_iterator(this, _capacity); +} + +template <class K, class V> +inline _HashMap_iterator<K, V> +HashMap<K, V>::begin() +{ + return iterator(this, 0); +} + +template <class K, class V> +inline _HashMap_iterator<K, V> +HashMap<K, V>::end() +{ + return iterator(this, _capacity); +} + +template <class K, class V> +inline bool +_HashMap_const_iterator<K, V>::operator==(const const_iterator &i) const +{ + return _hm == i._hm && _pos == i._pos; +} + +template <class K, class V> +inline bool +_HashMap_const_iterator<K, V>::operator!=(const const_iterator &i) const +{ + return _hm != i._hm || _pos != i._pos; +} + +inline unsigned +hashcode(int i) +{ + return static_cast<unsigned>(i); +} + +inline unsigned +hashcode(unsigned u) +{ + return u; +} + +inline unsigned +hashcode(long l) +{ + return static_cast<unsigned>(l); +} + +inline unsigned +hashcode(unsigned long ul) +{ + return static_cast<unsigned long>(ul); +} + +#include <lcdf/hashmap.cc> // necessary to support GCC 3.3 +#endif |