summaryrefslogtreecommitdiff
path: root/Build/source/texk/lcdf-typetools/lcdf-typetools-src/include/lcdf/hashmap.hh
diff options
context:
space:
mode:
Diffstat (limited to 'Build/source/texk/lcdf-typetools/lcdf-typetools-src/include/lcdf/hashmap.hh')
-rw-r--r--Build/source/texk/lcdf-typetools/lcdf-typetools-src/include/lcdf/hashmap.hh210
1 files changed, 0 insertions, 210 deletions
diff --git a/Build/source/texk/lcdf-typetools/lcdf-typetools-src/include/lcdf/hashmap.hh b/Build/source/texk/lcdf-typetools/lcdf-typetools-src/include/lcdf/hashmap.hh
deleted file mode 100644
index 3d4179e5b5f..00000000000
--- a/Build/source/texk/lcdf-typetools/lcdf-typetools-src/include/lcdf/hashmap.hh
+++ /dev/null
@@ -1,210 +0,0 @@
-#ifndef LCDF_HASHMAP_HH
-#define LCDF_HASHMAP_HH
-#include <assert.h>
-#include <lcdf/hashcode.hh>
-
-// 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
-// hashcode_t hashcode(const K &)
-// If hashcode(k1) != hashcode(k2), then k1 != k2.
-// Actually any unsigned integer type may be used.
-//
-// 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; }
- const V &default_value() const { return _default_value; }
- 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 &, const V &);
- inline 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);
- hashcode_t 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 V &
-HashMap<K, V>::find_force(const K &key)
-{
- return find_force(key, _default_value);
-}
-
-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;
-}
-
-#include <lcdf/hashmap.cc> // necessary to support GCC 3.3
-#endif