From baa789e0c9109bcb1e717ce4a9953709e7345e55 Mon Sep 17 00:00:00 2001 From: Yong He Date: Fri, 28 Aug 2020 14:56:53 -0700 Subject: Add OrderedDictionary to core. (#1523) --- source/core/slang-dictionary.h | 360 +++++++++++++++++++++++++++++++++++++++++ 1 file changed, 360 insertions(+) (limited to 'source/core/slang-dictionary.h') diff --git a/source/core/slang-dictionary.h b/source/core/slang-dictionary.h index 10c5a9b7d..2bd58f1c6 100644 --- a/source/core/slang-dictionary.h +++ b/source/core/slang-dictionary.h @@ -2,6 +2,7 @@ #define SLANG_CORE_DICTIONARY_H #include "slang-list.h" +#include "slang-linked-list.h" #include "slang-common.h" #include "slang-uint-set.h" #include "slang-exception.h" @@ -623,6 +624,365 @@ namespace Slang template class HashSet : public HashSetBase> {}; + + template + class OrderedDictionary + { + friend class Iterator; + friend class ItemProxy; + + private: + inline int GetProbeOffset(int /*probeIdx*/) const + { + // quadratic probing + return 1; + } + + private: + int bucketSizeMinusOne; + int _count; + UIntSet marks; + + LinkedList> kvPairs; + LinkedNode>** 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 inline int GetHashPos(T& key) const + { + const unsigned int hash = (unsigned int)getHashCode(key); + return ((unsigned int)(hash * 2654435761)) % bucketSizeMinusOne; + } + template 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&& 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; + if (newSize == 0) + { + newSize = 16; + } + OrderedDictionary newDict; + newDict.bucketSizeMinusOne = newSize - 1; + newDict.hashMap = new LinkedNode>*[newSize]; + newDict.marks.resizeAndClear(newSize * 2); + if (hashMap) + { + for (auto& kvPair : *this) + { + newDict.Add(_Move(kvPair)); + } + } + *this = _Move(newDict); + } + } + + bool AddIfNotExists(KeyValuePair&& 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&& kvPair) + { + if (!AddIfNotExists(_Move(kvPair))) + throw KeyExistsException("The key already exists in Dictionary."); + } + TValue& Set(KeyValuePair&& 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>::Iterator Iterator; + + typename LinkedList>::Iterator begin() const + { + return kvPairs.begin(); + } + typename LinkedList>::Iterator end() const + { + return kvPairs.end(); + } + + public: + void Add(const TKey& key, const TValue& value) + { + Add(KeyValuePair(key, value)); + } + void Add(TKey&& key, TValue&& value) + { + Add(KeyValuePair(_Move(key), _Move(value))); + } + bool AddIfNotExists(const TKey& key, const TValue& value) + { + return AddIfNotExists(KeyValuePair(key, value)); + } + bool AddIfNotExists(TKey&& key, TValue&& value) + { + return AddIfNotExists(KeyValuePair(_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 bool ContainsKey(const T& key) const + { + if (bucketSizeMinusOne == -1) + return false; + auto pos = FindPosition(key); + return pos.ObjectPosition != -1; + } + template 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 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 OrderedDictionary* dict; + TKey key; + + public: + ItemProxy(const TKey& _key, const OrderedDictionary* _dict) + { + this->dict = _dict; + this->key = _key; + } + ItemProxy(TKey&& _key, const OrderedDictionary* _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 ((OrderedDictionary*)dict) + ->Set(KeyValuePair(_Move(key), val)); + } + TValue& operator=(TValue&& val) + { + return ((OrderedDictionary*)dict) + ->Set(KeyValuePair(_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& First() const { return kvPairs.First(); } + KeyValuePair& Last() const { return kvPairs.Last(); } + + private: + template + void Init(const KeyValuePair& kvPair, Args... args) + { + Add(kvPair); + Init(args...); + } + + public: + OrderedDictionary() + { + bucketSizeMinusOne = -1; + _count = 0; + hashMap = 0; + } + template OrderedDictionary(Arg arg, Args... args) + { + Init(arg, args...); + } + OrderedDictionary(const OrderedDictionary& other) + : bucketSizeMinusOne(-1) + , _count(0) + , hashMap(0) + { + *this = other; + } + OrderedDictionary(OrderedDictionary&& other) + : bucketSizeMinusOne(-1) + , _count(0) + , hashMap(0) + { + *this = (_Move(other)); + } + OrderedDictionary& + operator=(const OrderedDictionary& other) + { + if (this == &other) + return *this; + Clear(); + for (auto& item : other) + Add(item.Key, item.Value); + return *this; + } + OrderedDictionary& + operator=(OrderedDictionary&& other) + { + if (this == &other) + return *this; + Free(); + bucketSizeMinusOne = other.bucketSizeMinusOne; + _count = other._count; + hashMap = other.hashMap; + marks = _Move(other.marks); + other.hashMap = 0; + other._count = 0; + other.bucketSizeMinusOne = -1; + kvPairs = _Move(other.kvPairs); + return *this; + } + ~OrderedDictionary() { Free(); } + }; + + template class OrderedHashSet : public HashSetBase> + {}; } #endif -- cgit v1.2.3