summaryrefslogtreecommitdiffstats
path: root/source/core/dictionary.h
diff options
context:
space:
mode:
Diffstat (limited to 'source/core/dictionary.h')
-rw-r--r--source/core/dictionary.h406
1 files changed, 0 insertions, 406 deletions
diff --git a/source/core/dictionary.h b/source/core/dictionary.h
index c052685fd..408835454 100644
--- a/source/core/dictionary.h
+++ b/source/core/dictionary.h
@@ -487,398 +487,6 @@ namespace Slang
}
};
- template<typename TKey, typename TValue>
- class EnumerableDictionary
- {
- friend class Iterator;
- friend class ItemProxy;
- private:
- inline int GetProbeOffset(int /*probeIdx*/) const
- {
- // quadratic probing
- return 1;
- }
- private:
- int bucketSizeMinusOne, shiftBits;
- int _count;
- IntSet marks;
-
- // debug op
- struct Op
- {
- TKey key;
- int opType;
- Op()
- {}
- Op(const TKey & key, int t)
- {
- this->key = key;
- opType = t;
- }
- };
- LinkedList<KeyValuePair<TKey, TValue>> kvPairs;
- LinkedNode<KeyValuePair<TKey, TValue>>** hashMap;
- void Free()
- {
- if (hashMap)
- delete[] hashMap;
- hashMap = 0;
- kvPairs.Clear();
- }
- inline bool IsDeleted(int pos) const
- {
- return marks.Contains((pos << 1) + 1);
- }
- inline bool IsEmpty(int pos) const
- {
- return !marks.Contains((pos << 1));
- }
- inline void SetDeleted(int pos, bool val)
- {
- if (val)
- marks.Add((pos << 1) + 1);
- else
- marks.Remove((pos << 1) + 1);
- }
- inline void SetEmpty(int pos, bool val)
- {
- if (val)
- marks.Remove((pos << 1));
- else
- marks.Add((pos << 1));
- }
- struct FindPositionResult
- {
- int ObjectPosition;
- int InsertionPosition;
- FindPositionResult()
- {
- ObjectPosition = -1;
- InsertionPosition = -1;
- }
- FindPositionResult(int objPos, int insertPos)
- {
- ObjectPosition = objPos;
- InsertionPosition = insertPos;
- }
-
- };
- template<typename T>
- inline int GetHashPos(T & key) const
- {
- return ((unsigned int)(GetHashCode(key) * 2654435761)) >> shiftBits;
- }
- template<typename T>
- FindPositionResult FindPosition(const T & key) const
- {
- int hashPos = GetHashPos((T&)key);
- int insertPos = -1;
- int numProbes = 0;
- while (numProbes <= bucketSizeMinusOne)
- {
- if (IsEmpty(hashPos))
- {
- if (insertPos == -1)
- return FindPositionResult(-1, hashPos);
- else
- return FindPositionResult(-1, insertPos);
- }
- else if (IsDeleted(hashPos))
- {
- if (insertPos == -1)
- insertPos = hashPos;
- }
- else if (hashMap[hashPos]->Value.Key == key)
- {
- return FindPositionResult(hashPos, -1);
- }
- numProbes++;
- hashPos = (hashPos + GetProbeOffset(numProbes)) & bucketSizeMinusOne;
- }
- if (insertPos != -1)
- return FindPositionResult(-1, insertPos);
- throw InvalidOperationException("Hash map is full. This indicates an error in Key::Equal or Key::GetHashCode.");
- }
- TValue & _Insert(KeyValuePair<TKey, TValue> && kvPair, int pos)
- {
- auto node = kvPairs.AddLast();
- node->Value = _Move(kvPair);
- hashMap[pos] = node;
- SetEmpty(pos, false);
- SetDeleted(pos, false);
- return node->Value.Value;
- }
- void Rehash()
- {
- if (bucketSizeMinusOne == -1 || _count / (float)bucketSizeMinusOne >= MaxLoadFactor)
- {
- int newSize = (bucketSizeMinusOne + 1) * 2;
- int newShiftBits = shiftBits - 1;
- if (newSize == 0)
- {
- newSize = 16;
- newShiftBits = 28;
- }
- EnumerableDictionary<TKey, TValue> newDict;
- newDict.shiftBits = newShiftBits;
- newDict.bucketSizeMinusOne = newSize - 1;
- newDict.hashMap = new LinkedNode<KeyValuePair<TKey, TValue>>*[newSize];
- newDict.marks.SetMax(newSize * 2);
- if (hashMap)
- {
- for (auto & kvPair : *this)
- {
- newDict.Add(_Move(kvPair));
- }
- }
- *this = _Move(newDict);
- }
- }
-
- bool AddIfNotExists(KeyValuePair<TKey, TValue> && kvPair)
- {
- Rehash();
- auto pos = FindPosition(kvPair.Key);
- if (pos.ObjectPosition != -1)
- return false;
- else if (pos.InsertionPosition != -1)
- {
- _count++;
- _Insert(_Move(kvPair), pos.InsertionPosition);
- return true;
- }
- else
- throw InvalidOperationException("Inconsistent find result returned. This is a bug in Dictionary implementation.");
- }
- void Add(KeyValuePair<TKey, TValue> && kvPair)
- {
- if (!AddIfNotExists(_Move(kvPair)))
- throw KeyExistsException("The key already exists in Dictionary.");
- }
- TValue & Set(KeyValuePair<TKey, TValue> && kvPair)
- {
- Rehash();
- auto pos = FindPosition(kvPair.Key);
- if (pos.ObjectPosition != -1)
- {
- hashMap[pos.ObjectPosition]->Delete();
- return _Insert(_Move(kvPair), pos.ObjectPosition);
- }
- else if (pos.InsertionPosition != -1)
- {
- _count++;
- return _Insert(_Move(kvPair), pos.InsertionPosition);
- }
- else
- throw InvalidOperationException("Inconsistent find result returned. This is a bug in Dictionary implementation.");
- }
- public:
- typedef typename LinkedList<KeyValuePair<TKey, TValue>>::Iterator Iterator;
-
- typename LinkedList<KeyValuePair<TKey, TValue>>::Iterator begin() const
- {
- return kvPairs.begin();
- }
- typename LinkedList<KeyValuePair<TKey, TValue>>::Iterator end() const
- {
- return kvPairs.end();
- }
- public:
- void Add(const TKey & key, const TValue & value)
- {
- Add(KeyValuePair<TKey, TValue>(key, value));
- }
- void Add(TKey && key, TValue && value)
- {
- Add(KeyValuePair<TKey, TValue>(_Move(key), _Move(value)));
- }
- bool AddIfNotExists(const TKey & key, const TValue & value)
- {
- return AddIfNotExists(KeyValuePair<TKey, TValue>(key, value));
- }
- bool AddIfNotExists(TKey && key, TValue && value)
- {
- return AddIfNotExists(KeyValuePair<TKey, TValue>(_Move(key), _Move(value)));
- }
- void Remove(const TKey & key)
- {
- if (_count > 0)
- {
- auto pos = FindPosition(key);
- if (pos.ObjectPosition != -1)
- {
- kvPairs.Delete(hashMap[pos.ObjectPosition]);
- hashMap[pos.ObjectPosition] = 0;
- SetDeleted(pos.ObjectPosition, true);
- _count--;
- }
- }
- }
- void Clear()
- {
- _count = 0;
- kvPairs.Clear();
- marks.Clear();
- }
- template<typename T>
- bool ContainsKey(const T & key) const
- {
- if (bucketSizeMinusOne == -1)
- return false;
- auto pos = FindPosition(key);
- return pos.ObjectPosition != -1;
- }
- template<typename T>
- TValue * TryGetValue(const T & key) const
- {
- if (bucketSizeMinusOne == -1)
- return nullptr;
- auto pos = FindPosition(key);
- if (pos.ObjectPosition != -1)
- {
- return &(hashMap[pos.ObjectPosition]->Value.Value);
- }
- return nullptr;
- }
- template<typename T>
- bool TryGetValue(const T & key, TValue & value) const
- {
- if (bucketSizeMinusOne == -1)
- return false;
- auto pos = FindPosition(key);
- if (pos.ObjectPosition != -1)
- {
- value = hashMap[pos.ObjectPosition]->Value.Value;
- return true;
- }
- return false;
- }
- class ItemProxy
- {
- private:
- const EnumerableDictionary<TKey, TValue> * dict;
- TKey key;
- public:
- ItemProxy(const TKey & _key, const EnumerableDictionary<TKey, TValue> * _dict)
- {
- this->dict = _dict;
- this->key = _key;
- }
- ItemProxy(TKey && _key, const EnumerableDictionary<TKey, TValue> * _dict)
- {
- this->dict = _dict;
- this->key = _Move(_key);
- }
- TValue & GetValue() const
- {
- auto pos = dict->FindPosition(key);
- if (pos.ObjectPosition != -1)
- {
- return dict->hashMap[pos.ObjectPosition]->Value.Value;
- }
- else
- {
- throw KeyNotFoundException("The key does not exists in dictionary.");
- }
- }
- inline TValue & operator()() const
- {
- return GetValue();
- }
- operator TValue&() const
- {
- return GetValue();
- }
- TValue & operator = (const TValue & val)
- {
- return ((EnumerableDictionary<TKey, TValue>*)dict)->Set(KeyValuePair<TKey, TValue>(_Move(key), val));
- }
- TValue & operator = (TValue && val)
- {
- return ((EnumerableDictionary<TKey, TValue>*)dict)->Set(KeyValuePair<TKey, TValue>(_Move(key), _Move(val)));
- }
- };
- ItemProxy operator [](const TKey & key) const
- {
- return ItemProxy(key, this);
- }
- ItemProxy operator [](TKey && key) const
- {
- return ItemProxy(_Move(key), this);
- }
- int Count() const
- {
- return _count;
- }
- KeyValuePair<TKey, TValue> & First() const
- {
- return kvPairs.First();
- }
- KeyValuePair<TKey, TValue> & Last() const
- {
- return kvPairs.Last();
- }
- private:
- template<typename... Args>
- void Init(const KeyValuePair<TKey, TValue> & kvPair, Args... args)
- {
- Add(kvPair);
- Init(args...);
- }
- public:
- EnumerableDictionary()
- {
- bucketSizeMinusOne = -1;
- shiftBits = 32;
- _count = 0;
- hashMap = 0;
- }
- template<typename Arg, typename... Args>
- EnumerableDictionary(Arg arg, Args... args)
- {
- Init(arg, args...);
- }
- EnumerableDictionary(const EnumerableDictionary<TKey, TValue> & other)
- : bucketSizeMinusOne(-1), _count(0), hashMap(0)
- {
- *this = other;
- }
- EnumerableDictionary(EnumerableDictionary<TKey, TValue> && other)
- : bucketSizeMinusOne(-1), _count(0), hashMap(0)
- {
- *this = (_Move(other));
- }
- EnumerableDictionary<TKey, TValue> & operator = (const EnumerableDictionary<TKey, TValue> & other)
- {
- if (this == &other)
- return *this;
- Clear();
- for (auto & item : other)
- Add(item.Key, item.Value);
- return *this;
- }
- EnumerableDictionary<TKey, TValue> & operator = (EnumerableDictionary<TKey, TValue> && other)
- {
- if (this == &other)
- return *this;
- Free();
- bucketSizeMinusOne = other.bucketSizeMinusOne;
- _count = other._count;
- hashMap = other.hashMap;
- shiftBits = other.shiftBits;
- marks = _Move(other.marks);
- other.hashMap = 0;
- other._count = 0;
- other.bucketSizeMinusOne = -1;
- kvPairs = _Move(other.kvPairs);
- return *this;
- }
- ~EnumerableDictionary()
- {
- Free();
- }
- };
-
class _DummyClass
{};
@@ -996,20 +604,6 @@ namespace Slang
template <typename T>
class HashSet : public HashSetBase<T, Dictionary<T, _DummyClass>>
{};
-
- template <typename T>
- class EnumerableHashSet : public HashSetBase<T, EnumerableDictionary<T, _DummyClass>>
- {
- public:
- T & First() const
- {
- return this->dict.First().Key;
- }
- T & Last() const
- {
- return this->dict.Last().Key;
- }
- };
}
#endif
generated by cgit v1.2.3 (git 2.39.1) at 2026-06-01 22:37:00 +0000