diff options
| author | jsmall-nvidia <jsmall@nvidia.com> | 2023-04-25 10:43:29 -0400 |
|---|---|---|
| committer | GitHub <noreply@github.com> | 2023-04-25 10:43:29 -0400 |
| commit | 7b7c095b37e85ca3a8f55eff1c3d9643d467b8e0 (patch) | |
| tree | 9c71955dbc956b0058b19818ca127c8132cda512 /source/core/slang-dictionary.h | |
| parent | 284cee1f246c072f190c87c8fb60c1d2181e458f (diff) | |
Dictionary using lowerCamel (#2835)
* #include an absolute path didn't work - because paths were taken to always be relative.
* WIP lowerCamel Dictionary.
* WIP more lowerCamel fixes for Dictionary.
* Add/Remove/Clear
* GetValue/Contains
* Fix tabs in dictionary.
Count -> getCount
* Fix fields with caps.
* Key -> key
Value -> value
Use m_ for members where appropriate.
Use lowerCamel in linked list.
* Some small fixes/improvements to Dictionary.
* Kick CI.
Diffstat (limited to 'source/core/slang-dictionary.h')
| -rw-r--r-- | source/core/slang-dictionary.h | 1501 |
1 files changed, 747 insertions, 754 deletions
diff --git a/source/core/slang-dictionary.h b/source/core/slang-dictionary.h index 0839a649c..0350a99d2 100644 --- a/source/core/slang-dictionary.h +++ b/source/core/slang-dictionary.h @@ -11,678 +11,670 @@ namespace Slang { - template<typename TKey, typename TValue> - class KeyValuePair - { - public: - TKey Key; - TValue Value; - KeyValuePair() - {} - KeyValuePair(const TKey & key, const TValue & value) - { - Key = key; - Value = value; - } - KeyValuePair(TKey && key, TValue && value) - { - Key = _Move(key); - Value = _Move(value); - } - KeyValuePair(TKey && key, const TValue & value) - { - Key = _Move(key); - Value = value; - } - KeyValuePair(const KeyValuePair<TKey, TValue> & _that) - { - Key = _that.Key; - Value = _that.Value; - } - KeyValuePair(KeyValuePair<TKey, TValue> && _that) - { - operator=(_Move(_that)); - } - KeyValuePair & operator=(KeyValuePair<TKey, TValue> && that) - { - Key = _Move(that.Key); - Value = _Move(that.Value); - return *this; - } - KeyValuePair & operator=(const KeyValuePair<TKey, TValue> & that) - { - Key = that.Key; - Value = that.Value; - return *this; - } - HashCode getHashCode() - { + template<typename TKey, typename TValue> + class KeyValuePair + { + public: + TKey key; + TValue value; + KeyValuePair() + {} + KeyValuePair(const TKey& inKey, const TValue& inValue) + { + key = inKey; + value = inValue; + } + KeyValuePair(TKey&& inKey, TValue&& inValue) + { + key = _Move(inKey); + value = _Move(inValue); + } + KeyValuePair(TKey&& inKey, const TValue& inValue) + { + key = _Move(inKey); + value = inValue; + } + KeyValuePair(const KeyValuePair<TKey, TValue>& that) + { + key = that.key; + value = that.value; + } + KeyValuePair(KeyValuePair<TKey, TValue>&& that) + { + operator=(_Move(that)); + } + KeyValuePair& operator=(KeyValuePair<TKey, TValue>&& that) + { + key = _Move(that.key); + value = _Move(that.value); + return *this; + } + KeyValuePair& operator=(const KeyValuePair<TKey, TValue>& that) + { + key = that.key; + value = that.value; + return *this; + } + HashCode getHashCode() + { return combineHash( - Slang::getHashCode(Key), - Slang::getHashCode(Value)); - } + Slang::getHashCode(key), + Slang::getHashCode(value)); + } bool operator==(const KeyValuePair<TKey, TValue>& that) const { - return (Key == that.Key) && (Value == that.Value); + return (key == that.key) && (value == that.value); } - }; + }; - template<typename TKey, typename TValue> - inline KeyValuePair<TKey, TValue> KVPair(const TKey & k, const TValue & v) - { - return KeyValuePair<TKey, TValue>(k, v); - } + template<typename TKey, typename TValue> + inline KeyValuePair<TKey, TValue> KVPair(const TKey& k, const TValue& v) + { + return KeyValuePair<TKey, TValue>(k, v); + } - const float MaxLoadFactor = 0.7f; + const float kMaxLoadFactor = 0.7f; - template<typename TKey, typename TValue> - class Dictionary - { - friend class Iterator; - friend class ItemProxy; + template<typename TKey, typename TValue> + class Dictionary + { + friend class Iterator; + friend class ItemProxy; public: typedef TValue ValueType; typedef TKey KeyType; - typedef Dictionary ThisType; - private: - inline int GetProbeOffset(int /*probeId*/) const - { - // linear probing - return 1; - } - private: - int bucketSizeMinusOne; - int _count; - UIntSet marks; - KeyValuePair<TKey, TValue>* hashMap; - void Free() - { - if (hashMap) - delete[] hashMap; - hashMap = 0; - } - 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; - } + typedef Dictionary ThisType; + private: + inline int getProbeOffset(int /*probeId*/) const + { + // linear probing + return 1; + } + private: + int m_bucketCountMinusOne; + int m_count; + UIntSet m_marks; + KeyValuePair<TKey, TValue>* m_hashMap; + void deallocateAll() + { + if (m_hashMap) + delete[] m_hashMap; + m_hashMap = nullptr; + } + inline bool isDeleted(int pos) const + { + return m_marks.contains((pos << 1) + 1); + } + inline bool isEmpty(int pos) const + { + return !m_marks.contains((pos << 1)); + } + inline void setDeleted(int pos, bool val) + { + if (val) + m_marks.add((pos << 1) + 1); + else + m_marks.remove((pos << 1) + 1); + } + inline void setEmpty(int pos, bool val) + { + if (val) + m_marks.remove((pos << 1)); + else + m_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 KeyType> - inline int GetHashPos(KeyType& key) const + inline int getHashPos(KeyType& key) const { - SLANG_ASSERT(bucketSizeMinusOne > 0); + SLANG_ASSERT(m_bucketCountMinusOne > 0); const unsigned int hash = (unsigned int)getHashCode(key); - return (hash * 2654435761u) % (unsigned int)(bucketSizeMinusOne); - } + return (hash * 2654435761u) % (unsigned int)(m_bucketCountMinusOne); + } template<typename KeyType> - FindPositionResult FindPosition(const KeyType& key) const - { - int hashPos = GetHashPos(const_cast<KeyType&>(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].Key == key) - { - return FindPositionResult(hashPos, -1); - } - numProbes++; - hashPos = (hashPos + GetProbeOffset(numProbes)) & bucketSizeMinusOne; - } - if (insertPos != -1) - return FindPositionResult(-1, insertPos); - SLANG_ASSERT_FAILURE("Hash map is full. This indicates an error in Key::Equal or Key::getHashCode."); - } - TValue & _Insert(KeyValuePair<TKey, TValue>&& kvPair, int pos) - { - hashMap[pos] = _Move(kvPair); - SetEmpty(pos, false); - SetDeleted(pos, false); - return hashMap[pos].Value; - } - void Rehash() - { - if (bucketSizeMinusOne == -1 || _count >= int(MaxLoadFactor * bucketSizeMinusOne)) - { - int newSize = (bucketSizeMinusOne + 1) * 2; - if (newSize == 0) - { - newSize = 16; - } - Dictionary<TKey, TValue> newDict; - newDict.bucketSizeMinusOne = newSize - 1; - newDict.hashMap = new KeyValuePair<TKey, TValue>[newSize]; - newDict.marks.resizeAndClear(newSize * 2); - if (hashMap) - { - for (auto & kvPair : *this) - { - newDict.Add(_Move(kvPair)); - } - } - *this = _Move(newDict); - } - } + FindPositionResult findPosition(const KeyType& key) const + { + int hashPos = getHashPos(const_cast<KeyType&>(key)); + int insertPos = -1; + int numProbes = 0; + while (numProbes <= m_bucketCountMinusOne) + { + 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 (m_hashMap[hashPos].key == key) + { + return FindPositionResult(hashPos, -1); + } + numProbes++; + hashPos = (hashPos + getProbeOffset(numProbes)) & m_bucketCountMinusOne; + } + if (insertPos != -1) + return FindPositionResult(-1, insertPos); + SLANG_ASSERT_FAILURE("Hash map is full. This indicates an error in Key::Equal or Key::getHashCode."); + } + TValue& _insert(KeyValuePair<TKey, TValue>&& kvPair, int pos) + { + m_hashMap[pos] = _Move(kvPair); + setEmpty(pos, false); + setDeleted(pos, false); + return m_hashMap[pos].value; + } + void maybeRehash() + { + if (m_bucketCountMinusOne == -1 || m_count >= int(kMaxLoadFactor * m_bucketCountMinusOne)) + { + int newSize = (m_bucketCountMinusOne + 1) * 2; + if (newSize == 0) + { + newSize = 16; + } + Dictionary<TKey, TValue> newDict; + newDict.m_bucketCountMinusOne = newSize - 1; + newDict.m_hashMap = new KeyValuePair<TKey, TValue>[newSize]; + newDict.m_marks.resizeAndClear(newSize * 2); + if (m_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 - SLANG_ASSERT_FAILURE("Inconsistent find result returned. This is a bug in Dictionary implementation."); - } - void Add(KeyValuePair<TKey, TValue>&& kvPair) - { - if (!AddIfNotExists(_Move(kvPair))) + bool addIfNotExists(KeyValuePair<TKey, TValue>&& kvPair) + { + maybeRehash(); + auto pos = findPosition(kvPair.key); + if (pos.objectPosition != -1) + return false; + else if (pos.insertionPosition != -1) + { + m_count++; + _insert(_Move(kvPair), pos.insertionPosition); + return true; + } + else + SLANG_ASSERT_FAILURE("Inconsistent find result returned. This is a bug in Dictionary implementation."); + } + void add(KeyValuePair<TKey, TValue>&& kvPair) + { + if (!addIfNotExists(_Move(kvPair))) SLANG_ASSERT_FAILURE("The key already exists in Dictionary."); - } - TValue& Set(KeyValuePair<TKey, TValue>&& kvPair) - { - Rehash(); - auto pos = FindPosition(kvPair.Key); - if (pos.ObjectPosition != -1) - return _Insert(_Move(kvPair), pos.ObjectPosition); - else if (pos.InsertionPosition != -1) - { - _count++; - return _Insert(_Move(kvPair), pos.InsertionPosition); - } - else + } + TValue& set(KeyValuePair<TKey, TValue>&& kvPair) + { + maybeRehash(); + auto pos = findPosition(kvPair.key); + if (pos.objectPosition != -1) + return _insert(_Move(kvPair), pos.objectPosition); + else if (pos.insertionPosition != -1) + { + m_count++; + return _insert(_Move(kvPair), pos.insertionPosition); + } + else SLANG_ASSERT_FAILURE("Inconsistent find result returned. This is a bug in Dictionary implementation."); - } - public: - class Iterator - { - private: - const Dictionary<TKey, TValue> * dict; - int pos; - public: - KeyValuePair<TKey, TValue> & operator *() const - { - return dict->hashMap[pos]; - } - KeyValuePair<TKey, TValue> * operator ->() const - { - return dict->hashMap + pos; - } - Iterator & operator ++() - { - if (pos > dict->bucketSizeMinusOne) - return *this; - pos++; - while (pos <= dict->bucketSizeMinusOne && (dict->IsDeleted(pos) || dict->IsEmpty(pos))) - { - pos++; - } - return *this; - } - Iterator operator ++(int) - { - Iterator rs = *this; - operator++(); - return rs; - } - bool operator != (const Iterator & _that) const - { - return pos != _that.pos || dict != _that.dict; - } - bool operator == (const Iterator & _that) const - { - return pos == _that.pos && dict == _that.dict; - } - Iterator(const Dictionary<TKey, TValue> * _dict, int _pos) - { - this->dict = _dict; - this->pos = _pos; - } - Iterator() - { - this->dict = 0; - this->pos = 0; - } - }; - - Iterator begin() const - { - int pos = 0; - while (pos < bucketSizeMinusOne + 1) - { - if (IsEmpty(pos) || IsDeleted(pos)) - pos++; - else - break; - } - return Iterator(this, pos); - } - Iterator end() const - { - return Iterator(this, bucketSizeMinusOne + 1); - } - 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) - return; - auto pos = FindPosition(key); - if (pos.ObjectPosition != -1) - { - SetDeleted(pos.ObjectPosition, true); - _count--; - } - } - void Clear() - { - _count = 0; + } + public: + class Iterator + { + private: + const Dictionary<TKey, TValue>* dict; + int pos; + public: + KeyValuePair<TKey, TValue>& operator*() const + { + return dict->m_hashMap[pos]; + } + KeyValuePair<TKey, TValue>* operator->() const + { + return dict->m_hashMap + pos; + } + Iterator& operator++() + { + if (pos > dict->m_bucketCountMinusOne) + return *this; + pos++; + while (pos <= dict->m_bucketCountMinusOne && (dict->isDeleted(pos) || dict->isEmpty(pos))) + { + pos++; + } + return *this; + } + Iterator operator++(int) + { + Iterator rs = *this; + operator++(); + return rs; + } + bool operator!=(const Iterator& that) const + { + return pos != that.pos || dict != that.dict; + } + bool operator==(const Iterator& that) const + { + return pos == that.pos && dict == that.dict; + } + Iterator(const Dictionary<TKey, TValue>* inDict, int inPos) + { + this->dict = inDict; + this->pos = inPos; + } + Iterator() + { + this->dict = nullptr; + this->pos = 0; + } + }; - marks.clear(); - } + Iterator begin() const + { + int pos = 0; + while (pos < m_bucketCountMinusOne + 1) + { + if (isEmpty(pos) || isDeleted(pos)) + pos++; + else + break; + } + return Iterator(this, pos); + } + Iterator end() const + { + return Iterator(this, m_bucketCountMinusOne + 1); + } + 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 (m_count == 0) + return; + auto pos = findPosition(key); + if (pos.objectPosition != -1) + { + setDeleted(pos.objectPosition, true); + m_count--; + } + } + void clear() + { + m_count = 0; + m_marks.clear(); + } - TValue* TryGetValueOrAdd(const TKey& key, const TValue& value) + TValue* tryGetValueOrAdd(const TKey& key, const TValue& value) { - Rehash(); - auto pos = FindPosition(key); - if (pos.ObjectPosition != -1) + maybeRehash(); + auto pos = findPosition(key); + if (pos.objectPosition != -1) { - return &hashMap[pos.ObjectPosition].Value; + return &m_hashMap[pos.objectPosition].value; } - else if (pos.InsertionPosition != -1) + else if (pos.insertionPosition != -1) { // Make pair KeyValuePair<TKey, TValue> kvPair(_Move(key), _Move(value)); - _count++; - _Insert(_Move(kvPair), pos.InsertionPosition); + m_count++; + _insert(_Move(kvPair), pos.insertionPosition); return nullptr; } else SLANG_ASSERT_FAILURE("Inconsistent find result returned. This is a bug in Dictionary implementation."); } - /// This differs from TryGetValueOrAdd, in that it always returns the Value held in the Dictionary. + /// This differs from tryGetValueOrAdd, in that it always returns the Value held in the Dictionary. /// If there isn't already an entry for 'key', a value is added with defaultValue. - TValue& GetOrAddValue(const TKey& key, const TValue& defaultValue) + TValue& getOrAddValue(const TKey& key, const TValue& defaultValue) { - Rehash(); - auto pos = FindPosition(key); - if (pos.ObjectPosition != -1) + maybeRehash(); + auto pos = findPosition(key); + if (pos.objectPosition != -1) { - return hashMap[pos.ObjectPosition].Value; + return m_hashMap[pos.objectPosition].value; } - else if (pos.InsertionPosition != -1) + else if (pos.insertionPosition != -1) { // Make pair KeyValuePair<TKey, TValue> kvPair(_Move(key), _Move(defaultValue)); - _count++; - return _Insert(_Move(kvPair), pos.InsertionPosition); + m_count++; + return _insert(_Move(kvPair), pos.insertionPosition); } else SLANG_ASSERT_FAILURE("Inconsistent find result returned. This is a bug in Dictionary implementation."); } - void Set(const TKey& key, const TValue& value) - { - if (auto ptr = TryGetValueOrAdd(key, value)) - { - *ptr = value; - } - } + void set(const TKey& key, const TValue& value) + { + if (auto ptr = tryGetValueOrAdd(key, value)) + { + *ptr = value; + } + } template<typename KeyType> - bool ContainsKey(const KeyType& key) const - { - if (bucketSizeMinusOne == -1) - return false; - auto pos = FindPosition(key); - return pos.ObjectPosition != -1; - } + bool containsKey(const KeyType& key) const + { + if (m_bucketCountMinusOne == -1) + return false; + auto pos = findPosition(key); + return pos.objectPosition != -1; + } template<typename KeyType> - bool TryGetValue(const KeyType& key, TValue& value) const - { - if (bucketSizeMinusOne == -1) - return false; - auto pos = FindPosition(key); - if (pos.ObjectPosition != -1) - { - value = hashMap[pos.ObjectPosition].Value; - return true; - } - return false; - } + bool tryGetValue(const KeyType& key, TValue& value) const + { + if (m_bucketCountMinusOne == -1) + return false; + auto pos = findPosition(key); + if (pos.objectPosition != -1) + { + value = m_hashMap[pos.objectPosition].value; + return true; + } + return false; + } template<typename KeyType> - TValue* TryGetValue(const KeyType& key) const - { - if (bucketSizeMinusOne == -1) - return nullptr; - auto pos = FindPosition(key); - if (pos.ObjectPosition != -1) - { - return &hashMap[pos.ObjectPosition].Value; - } - return nullptr; - } + TValue* tryGetValue(const KeyType& key) const + { + if (m_bucketCountMinusOne == -1) + return nullptr; + auto pos = findPosition(key); + if (pos.objectPosition != -1) + { + return &m_hashMap[pos.objectPosition].value; + } + return nullptr; + } - class ItemProxy - { - private: - const Dictionary<TKey, TValue> * dict; - TKey key; - public: - ItemProxy(const TKey& _key, const Dictionary<TKey, TValue>* _dict) - { - this->dict = _dict; - this->key = _key; - } - ItemProxy(TKey&& _key, const Dictionary<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; - } - else + class ItemProxy + { + private: + const Dictionary<TKey, TValue>* dict; + TKey key; + public: + ItemProxy(const TKey& _key, const Dictionary<TKey, TValue>* _dict) + { + this->dict = _dict; + this->key = _key; + } + ItemProxy(TKey&& _key, const Dictionary<TKey, TValue>* _dict) + { + this->dict = _dict; + this->key = _Move(_key); + } + TValue& getValue() const + { + auto pos = dict->findPosition(key); + if (pos.objectPosition != -1) + { + return dict->m_hashMap[pos.objectPosition].value; + } + else SLANG_ASSERT_FAILURE("The key does not exist in dictionary."); - } - inline TValue & operator()() const - { - return GetValue(); - } - operator TValue&() const - { - return GetValue(); - } - TValue & operator = (const TValue & val) const - { - return ((Dictionary<TKey, TValue>*)dict)->Set(KeyValuePair<TKey, TValue>(_Move(key), val)); - } - TValue & operator = (TValue && val) const - { - return ((Dictionary<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; - } + } + inline TValue& operator()() const + { + return getValue(); + } + operator TValue&() const + { + return getValue(); + } + TValue& operator=(const TValue& val) const + { + return ((Dictionary<TKey, TValue>*)dict)->set(KeyValuePair<TKey, TValue>(_Move(key), val)); + } + TValue& operator=(TValue&& val) const + { + return ((Dictionary<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 getCount() const + { + return m_count; + } - /// Swap this with rhs - void swapWith(ThisType& rhs); + /// Swap this with rhs + void swapWith(ThisType& rhs); - private: - template<typename... Args> - void Init(const KeyValuePair<TKey, TValue> & kvPair, Args... args) - { - Add(kvPair); - Init(args...); - } - public: - Dictionary() - { - bucketSizeMinusOne = -1; - _count = 0; - hashMap = nullptr; - } - template<typename Arg, typename... Args> - Dictionary(Arg arg, Args... args) - { - Init(arg, args...); - } - Dictionary(const Dictionary<TKey, TValue>& other) - : bucketSizeMinusOne(-1), _count(0), hashMap(nullptr) - { - *this = other; - } - Dictionary(Dictionary<TKey, TValue>&& other) - : bucketSizeMinusOne(-1), _count(0), hashMap(nullptr) - { - *this = (_Move(other)); - } - Dictionary<TKey, TValue>& operator = (const Dictionary<TKey, TValue>& other) - { - if (this == &other) - return *this; - Free(); - bucketSizeMinusOne = other.bucketSizeMinusOne; - _count = other._count; - hashMap = new KeyValuePair<TKey, TValue>[other.bucketSizeMinusOne + 1]; - marks = other.marks; - for (int i = 0; i <= bucketSizeMinusOne; i++) - hashMap[i] = other.hashMap[i]; - return *this; - } - Dictionary<TKey, TValue> & operator = (Dictionary<TKey, TValue>&& 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; - return *this; - } - ~Dictionary() - { - Free(); - } - }; + private: + template<typename... Args> + void init(const KeyValuePair<TKey, TValue>& kvPair, Args... args) + { + add(kvPair); + init(args...); + } + public: + Dictionary() + { + m_bucketCountMinusOne = -1; + m_count = 0; + m_hashMap = nullptr; + } + template<typename Arg, typename... Args> + Dictionary(Arg arg, Args... args) + { + init(arg, args...); + } + Dictionary(const Dictionary<TKey, TValue>& other) + : m_bucketCountMinusOne(-1), m_count(0), m_hashMap(nullptr) + { + *this = other; + } + Dictionary(Dictionary<TKey, TValue>&& other) + : m_bucketCountMinusOne(-1), m_count(0), m_hashMap(nullptr) + { + *this = (_Move(other)); + } + Dictionary<TKey, TValue>& operator=(const Dictionary<TKey, TValue>& other) + { + if (this == &other) + return *this; + deallocateAll(); + m_bucketCountMinusOne = other.m_bucketCountMinusOne; + m_count = other.m_count; + m_hashMap = new KeyValuePair<TKey, TValue>[other.m_bucketCountMinusOne + 1]; + m_marks = other.m_marks; + for (int i = 0; i <= m_bucketCountMinusOne; i++) + m_hashMap[i] = other.m_hashMap[i]; + return *this; + } + Dictionary<TKey, TValue>& operator=(Dictionary<TKey, TValue>&& other) + { + if (this == &other) + return *this; + deallocateAll(); + m_bucketCountMinusOne = other.m_bucketCountMinusOne; + m_count = other.m_count; + m_hashMap = other.m_hashMap; + m_marks = _Move(other.m_marks); + other.m_hashMap = nullptr; + other.m_count = 0; + other.m_bucketCountMinusOne = -1; + return *this; + } + ~Dictionary() + { + deallocateAll(); + } + }; - // --------------------------------------------------------- - template<typename TKey, typename TValue> - void Dictionary<TKey, TValue>::swapWith(ThisType& rhs) - { - Swap(bucketSizeMinusOne, rhs.bucketSizeMinusOne); - Swap(_count, rhs._count); - marks.swapWith(rhs.marks); - Swap(hashMap, rhs.hashMap); - } + // --------------------------------------------------------- + template<typename TKey, typename TValue> + void Dictionary<TKey, TValue>::swapWith(ThisType& rhs) + { + Swap(m_bucketCountMinusOne, rhs.m_bucketCountMinusOne); + Swap(m_count, rhs.m_count); + m_marks.swapWith(rhs.m_marks); + Swap(m_hashMap, rhs.m_hashMap); + } - class _DummyClass - {}; + /* We may want to rename this, as strictly speaking _Caps names are reserved */ + class _DummyClass + {}; - template<typename T, typename DictionaryType> - class HashSetBase - { - protected: - DictionaryType dict; - private: - template<typename... Args> - void Init(const T & v, Args... args) - { - Add(v); - Init(args...); - } - public: - HashSetBase() - {} - template<typename Arg, typename... Args> - HashSetBase(Arg arg, Args... args) - { - Init(arg, args...); - } - HashSetBase(const HashSetBase & set) - { - operator=(set); - } - HashSetBase(HashSetBase && set) - { - operator=(_Move(set)); - } - HashSetBase & operator = (const HashSetBase & set) - { - dict = set.dict; - return *this; - } - HashSetBase & operator = (HashSetBase && set) - { - dict = _Move(set.dict); - return *this; - } - public: - class Iterator - { - private: - typename DictionaryType::Iterator iter; - public: - Iterator() = default; - T & operator *() const - { - return (*iter).Key; - } - T * operator ->() const - { - return &(*iter).Key; - } - Iterator & operator ++() - { - ++iter; - return *this; - } - Iterator operator ++(int) - { - Iterator rs = *this; - operator++(); - return rs; - } - bool operator != (const Iterator & _that) const - { - return iter != _that.iter; - } - bool operator == (const Iterator & _that) const - { - return iter == _that.iter; - } - Iterator(const typename DictionaryType::Iterator & _iter) - { - this->iter = _iter; - } - }; - Iterator begin() const - { - return Iterator(dict.begin()); - } - Iterator end() const - { - return Iterator(dict.end()); - } - public: - int Count() const - { - return dict.Count(); - } - void Clear() - { - dict.Clear(); - } - bool Add(const T& obj) - { - return dict.AddIfNotExists(obj, _DummyClass()); - } - bool Add(T && obj) - { - return dict.AddIfNotExists(_Move(obj), _DummyClass()); - } + template<typename T, typename DictionaryType> + class HashSetBase + { + protected: + DictionaryType dict; + private: + template<typename... Args> + void init(const T& v, Args... args) + { + add(v); + init(args...); + } + public: + HashSetBase() + {} + template<typename Arg, typename... Args> + HashSetBase(Arg arg, Args... args) + { + init(arg, args...); + } + HashSetBase(const HashSetBase& set) + { + operator=(set); + } + HashSetBase(HashSetBase&& set) + { + operator=(_Move(set)); + } + HashSetBase& operator=(const HashSetBase& set) + { + dict = set.dict; + return *this; + } + HashSetBase& operator=(HashSetBase&& set) + { + dict = _Move(set.dict); + return *this; + } + public: + class Iterator + { + private: + typename DictionaryType::Iterator iter; + public: + Iterator() = default; + T& operator*() const + { + return (*iter).key; + } + T* operator->() const + { + return &(*iter).key; + } + Iterator& operator++() + { + ++iter; + return *this; + } + Iterator operator++(int) + { + Iterator rs = *this; + operator++(); + return rs; + } + bool operator!=(const Iterator& that) const + { + return iter != that.iter; + } + bool operator==(const Iterator& that) const + { + return iter == that.iter; + } + Iterator(const typename DictionaryType::Iterator& _iter) + { + this->iter = _iter; + } + }; + Iterator begin() const + { + return Iterator(dict.begin()); + } + Iterator end() const + { + return Iterator(dict.end()); + } + public: + int getCount() const + { + return dict.getCount(); + } + void clear() + { + dict.clear(); + } bool add(const T& obj) { - return dict.AddIfNotExists(obj, _DummyClass()); + return dict.addIfNotExists(obj, _DummyClass()); } bool add(T&& obj) { - return dict.AddIfNotExists(_Move(obj), _DummyClass()); - } - void Remove(const T & obj) - { - dict.Remove(obj); - } - bool Contains(const T & obj) const - { - return dict.ContainsKey(obj); - } - }; - template <typename T> - class HashSet : public HashSetBase<T, Dictionary<T, _DummyClass>> - {}; + return dict.addIfNotExists(_Move(obj), _DummyClass()); + } + void remove(const T& obj) + { + dict.remove(obj); + } + bool contains(const T& obj) const + { + return dict.containsKey(obj); + } + }; + template <typename T> + class HashSet : public HashSetBase<T, Dictionary<T, _DummyClass>> + {}; template <typename TKey, typename TValue> class OrderedDictionary @@ -691,158 +683,158 @@ namespace Slang friend class ItemProxy; private: - inline int GetProbeOffset(int /*probeIdx*/) const + inline int getProbeOffset(int /*probeIdx*/) const { // quadratic probing return 1; } private: - int bucketSizeMinusOne; - int _count; - UIntSet marks; + int m_bucketCountMinusOne; + int m_count; + UIntSet m_marks; - LinkedList<KeyValuePair<TKey, TValue>> kvPairs; - LinkedNode<KeyValuePair<TKey, TValue>>** hashMap; - void Free() + LinkedList<KeyValuePair<TKey, TValue>> m_kvPairs; + LinkedNode<KeyValuePair<TKey, TValue>>** m_hashMap; + void deallocateAll() { - if (hashMap) - delete[] hashMap; - hashMap = 0; - kvPairs.Clear(); + if (m_hashMap) + delete[] m_hashMap; + m_hashMap = nullptr; + m_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) + inline bool isDeleted(int pos) const { return m_marks.contains((pos << 1) + 1); } + inline bool isEmpty(int pos) const { return !m_marks.contains((pos << 1)); } + inline void setDeleted(int pos, bool val) { if (val) - marks.add((pos << 1) + 1); + m_marks.add((pos << 1) + 1); else - marks.remove((pos << 1) + 1); + m_marks.remove((pos << 1) + 1); } - inline void SetEmpty(int pos, bool val) + inline void setEmpty(int pos, bool val) { if (val) - marks.remove((pos << 1)); + m_marks.remove((pos << 1)); else - marks.add((pos << 1)); + m_marks.add((pos << 1)); } struct FindPositionResult { - int ObjectPosition; - int InsertionPosition; + int objectPosition; + int insertionPosition; FindPositionResult() { - ObjectPosition = -1; - InsertionPosition = -1; + objectPosition = -1; + insertionPosition = -1; } FindPositionResult(int objPos, int insertPos) { - ObjectPosition = objPos; - InsertionPosition = insertPos; + objectPosition = objPos; + insertionPosition = insertPos; } }; - template <typename T> inline int GetHashPos(T& key) const + template <typename T> inline int getHashPos(T& key) const { const unsigned int hash = (unsigned int)getHashCode(key); - return ((unsigned int)(hash * 2654435761)) % bucketSizeMinusOne; + return ((unsigned int)(hash * 2654435761)) % m_bucketCountMinusOne; } - template <typename T> FindPositionResult FindPosition(const T& key) const + template <typename T> FindPositionResult findPosition(const T& key) const { - int hashPos = GetHashPos((T&)key); + int hashPos = getHashPos((T&)key); int insertPos = -1; int numProbes = 0; - while (numProbes <= bucketSizeMinusOne) + while (numProbes <= m_bucketCountMinusOne) { - if (IsEmpty(hashPos)) + if (isEmpty(hashPos)) { if (insertPos == -1) return FindPositionResult(-1, hashPos); else return FindPositionResult(-1, insertPos); } - else if (IsDeleted(hashPos)) + else if (isDeleted(hashPos)) { if (insertPos == -1) insertPos = hashPos; } - else if (hashMap[hashPos]->Value.Key == key) + else if (m_hashMap[hashPos]->value.key == key) { return FindPositionResult(hashPos, -1); } numProbes++; - hashPos = (hashPos + GetProbeOffset(numProbes)) & bucketSizeMinusOne; + hashPos = (hashPos + getProbeOffset(numProbes)) & m_bucketCountMinusOne; } if (insertPos != -1) return FindPositionResult(-1, insertPos); SLANG_ASSERT_FAILURE("Hash map is full. This indicates an error in Key::Equal or Key::GetHashCode."); } - TValue& _Insert(KeyValuePair<TKey, TValue>&& kvPair, int pos) + 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; + auto node = m_kvPairs.addLast(); + node->value = _Move(kvPair); + m_hashMap[pos] = node; + setEmpty(pos, false); + setDeleted(pos, false); + return node->value.value; } - void Rehash() + void maybeRehash() { - if (bucketSizeMinusOne == -1 || _count / (float)bucketSizeMinusOne >= MaxLoadFactor) + if (m_bucketCountMinusOne == -1 || m_count / (float)m_bucketCountMinusOne >= kMaxLoadFactor) { - int newSize = (bucketSizeMinusOne + 1) * 2; + int newSize = (m_bucketCountMinusOne + 1) * 2; if (newSize == 0) { newSize = 16; } OrderedDictionary<TKey, TValue> newDict; - newDict.bucketSizeMinusOne = newSize - 1; - newDict.hashMap = new LinkedNode<KeyValuePair<TKey, TValue>>*[newSize]; - newDict.marks.resizeAndClear(newSize * 2); - if (hashMap) + newDict.m_bucketCountMinusOne = newSize - 1; + newDict.m_hashMap = new LinkedNode<KeyValuePair<TKey, TValue>>*[newSize]; + newDict.m_marks.resizeAndClear(newSize * 2); + if (m_hashMap) { for (auto& kvPair : *this) { - newDict.Add(_Move(kvPair)); + newDict.add(_Move(kvPair)); } } *this = _Move(newDict); } } - bool AddIfNotExists(KeyValuePair<TKey, TValue>&& kvPair) + bool addIfNotExists(KeyValuePair<TKey, TValue>&& kvPair) { - Rehash(); - auto pos = FindPosition(kvPair.Key); - if (pos.ObjectPosition != -1) + maybeRehash(); + auto pos = findPosition(kvPair.key); + if (pos.objectPosition != -1) return false; - else if (pos.InsertionPosition != -1) + else if (pos.insertionPosition != -1) { - _count++; - _Insert(_Move(kvPair), pos.InsertionPosition); + m_count++; + _insert(_Move(kvPair), pos.insertionPosition); return true; } else SLANG_ASSERT_FAILURE("Inconsistent find result returned. This is a bug in Dictionary implementation."); } - void Add(KeyValuePair<TKey, TValue>&& kvPair) + void add(KeyValuePair<TKey, TValue>&& kvPair) { - if (!AddIfNotExists(_Move(kvPair))) + if (!addIfNotExists(_Move(kvPair))) SLANG_ASSERT_FAILURE("The key already exists in Dictionary."); } - TValue& Set(KeyValuePair<TKey, TValue>&& kvPair) + TValue& set(KeyValuePair<TKey, TValue>&& kvPair) { - Rehash(); - auto pos = FindPosition(kvPair.Key); - if (pos.ObjectPosition != -1) + maybeRehash(); + auto pos = findPosition(kvPair.key); + if (pos.objectPosition != -1) { - hashMap[pos.ObjectPosition]->Delete(); - return _Insert(_Move(kvPair), pos.ObjectPosition); + m_hashMap[pos.objectPosition]->removeAndDelete(); + return _insert(_Move(kvPair), pos.objectPosition); } - else if (pos.InsertionPosition != -1) + else if (pos.insertionPosition != -1) { - _count++; - return _Insert(_Move(kvPair), pos.InsertionPosition); + m_count++; + return _insert(_Move(kvPair), pos.insertionPosition); } else SLANG_ASSERT_FAILURE("Inconsistent find result returned. This is a bug in Dictionary implementation."); @@ -853,76 +845,76 @@ namespace Slang typename LinkedList<KeyValuePair<TKey, TValue>>::Iterator begin() const { - return kvPairs.begin(); + return m_kvPairs.begin(); } typename LinkedList<KeyValuePair<TKey, TValue>>::Iterator end() const { - return kvPairs.end(); + return m_kvPairs.end(); } public: - void Add(const TKey& key, const TValue& value) + void add(const TKey& key, const TValue& value) { - Add(KeyValuePair<TKey, TValue>(key, value)); + add(KeyValuePair<TKey, TValue>(key, value)); } - void Add(TKey&& key, TValue&& value) + void add(TKey&& key, TValue&& value) { - Add(KeyValuePair<TKey, TValue>(_Move(key), _Move(value))); + add(KeyValuePair<TKey, TValue>(_Move(key), _Move(value))); } - bool AddIfNotExists(const TKey& key, const TValue& value) + bool addIfNotExists(const TKey& key, const TValue& value) { - return AddIfNotExists(KeyValuePair<TKey, TValue>(key, value)); + return addIfNotExists(KeyValuePair<TKey, TValue>(key, value)); } - bool AddIfNotExists(TKey&& key, TValue&& value) + bool addIfNotExists(TKey&& key, TValue&& value) { - return AddIfNotExists(KeyValuePair<TKey, TValue>(_Move(key), _Move(value))); + return addIfNotExists(KeyValuePair<TKey, TValue>(_Move(key), _Move(value))); } - void Remove(const TKey& key) + void remove(const TKey& key) { - if (_count > 0) + if (m_count > 0) { - auto pos = FindPosition(key); - if (pos.ObjectPosition != -1) + auto pos = findPosition(key); + if (pos.objectPosition != -1) { - kvPairs.Delete(hashMap[pos.ObjectPosition]); - hashMap[pos.ObjectPosition] = 0; - SetDeleted(pos.ObjectPosition, true); - _count--; + m_kvPairs.removeAndDelete(m_hashMap[pos.objectPosition]); + m_hashMap[pos.objectPosition] = 0; + setDeleted(pos.objectPosition, true); + m_count--; } } } - void Clear() + void clear() { - _count = 0; - kvPairs.Clear(); - marks.clear(); + m_count = 0; + m_kvPairs.clear(); + m_marks.clear(); } - template <typename T> bool ContainsKey(const T& key) const + template <typename T> bool containsKey(const T& key) const { - if (bucketSizeMinusOne == -1) + if (m_bucketCountMinusOne == -1) return false; - auto pos = FindPosition(key); - return pos.ObjectPosition != -1; + auto pos = findPosition(key); + return pos.objectPosition != -1; } - template <typename T> TValue* TryGetValue(const T& key) const + template <typename T> TValue* tryGetValue(const T& key) const { - if (bucketSizeMinusOne == -1) + if (m_bucketCountMinusOne == -1) return nullptr; - auto pos = FindPosition(key); - if (pos.ObjectPosition != -1) + auto pos = findPosition(key); + if (pos.objectPosition != -1) { - return &(hashMap[pos.ObjectPosition]->Value.Value); + return &(m_hashMap[pos.objectPosition]->value.value); } return nullptr; } - template <typename T> bool TryGetValue(const T& key, TValue& value) const + template <typename T> bool tryGetValue(const T& key, TValue& value) const { - if (bucketSizeMinusOne == -1) + if (m_bucketCountMinusOne == -1) return false; - auto pos = FindPosition(key); - if (pos.ObjectPosition != -1) + auto pos = findPosition(key); + if (pos.objectPosition != -1) { - value = hashMap[pos.ObjectPosition]->Value.Value; + value = m_hashMap[pos.objectPosition]->value.value; return true; } return false; @@ -944,67 +936,68 @@ namespace Slang this->dict = _dict; this->key = _Move(_key); } - TValue& GetValue() const + TValue& getValue() const { - auto pos = dict->FindPosition(key); - if (pos.ObjectPosition != -1) + auto pos = dict->findPosition(key); + if (pos.objectPosition != -1) { - return dict->hashMap[pos.ObjectPosition]->Value.Value; + return dict->m_hashMap[pos.objectPosition]->value.value; } else { SLANG_ASSERT_FAILURE("The key does not exists in dictionary."); } } - inline TValue& operator()() const { return GetValue(); } - operator TValue&() const { return GetValue(); } + inline TValue& operator()() const { return getValue(); } + operator TValue&() const { return getValue(); } TValue& operator=(const TValue& val) { return ((OrderedDictionary<TKey, TValue>*)dict) - ->Set(KeyValuePair<TKey, TValue>(_Move(key), val)); + ->set(KeyValuePair<TKey, TValue>(_Move(key), val)); } TValue& operator=(TValue&& val) { return ((OrderedDictionary<TKey, TValue>*)dict) - ->Set(KeyValuePair<TKey, TValue>(_Move(key), _Move(val))); + ->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(); } + + int getCount() const { return m_count; } + KeyValuePair<TKey, TValue>& getFirst() const { return m_kvPairs.getFirst(); } + KeyValuePair<TKey, TValue>& getLast() const { return m_kvPairs.getLast(); } private: template <typename... Args> - void Init(const KeyValuePair<TKey, TValue>& kvPair, Args... args) + void init(const KeyValuePair<TKey, TValue>& kvPair, Args... args) { - Add(kvPair); - Init(args...); + add(kvPair); + init(args...); } public: OrderedDictionary() { - bucketSizeMinusOne = -1; - _count = 0; - hashMap = 0; + m_bucketCountMinusOne = -1; + m_count = 0; + m_hashMap = 0; } template <typename Arg, typename... Args> OrderedDictionary(Arg arg, Args... args) { - Init(arg, args...); + init(arg, args...); } OrderedDictionary(const OrderedDictionary<TKey, TValue>& other) - : bucketSizeMinusOne(-1) - , _count(0) - , hashMap(0) + : m_bucketCountMinusOne(-1) + , m_count(0) + , m_hashMap(0) { *this = other; } OrderedDictionary(OrderedDictionary<TKey, TValue>&& other) - : bucketSizeMinusOne(-1) - , _count(0) - , hashMap(0) + : m_bucketCountMinusOne(-1) + , m_count(0) + , m_hashMap(0) { *this = (_Move(other)); } @@ -1013,9 +1006,9 @@ namespace Slang { if (this == &other) return *this; - Clear(); + clear(); for (auto& item : other) - Add(item.Key, item.Value); + add(item.key, item.value); return *this; } OrderedDictionary<TKey, TValue>& @@ -1023,18 +1016,18 @@ namespace Slang { 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); + deallocateAll(); + m_bucketCountMinusOne = other.m_bucketCountMinusOne; + m_count = other.m_count; + m_hashMap = other.m_hashMap; + m_marks = _Move(other.m_marks); + other.m_hashMap = 0; + other.m_count = 0; + other.m_bucketCountMinusOne = -1; + m_kvPairs = _Move(other.m_kvPairs); return *this; } - ~OrderedDictionary() { Free(); } + ~OrderedDictionary() { deallocateAll(); } }; template <typename T> class OrderedHashSet : public HashSetBase<T, OrderedDictionary<T, _DummyClass>> @@ -1042,11 +1035,11 @@ namespace Slang public: T& getLast() { - return this->dict.Last().Key; + return this->dict.getLast().key; } void removeLast() { - this->Remove(getLast()); + this->remove(getLast()); } }; } |
