Add OrderedDictionary to core. (#1523)

5 files changed, 672 insertions, 2 deletions

diff --git a/source/core/core.vcxproj b/source/core/core.vcxproj
index 9676bb989..521adc790 100644
--- a/source/core/core.vcxproj
+++ b/source/core/core.vcxproj
@@ -185,6 +185,7 @@
     <ClInclude Include="slang-hash.h" />
     <ClInclude Include="slang-hex-dump-util.h" />
     <ClInclude Include="slang-io.h" />
+    <ClInclude Include="slang-linked-list.h" />
     <ClInclude Include="slang-list.h" />
     <ClInclude Include="slang-math.h" />
     <ClInclude Include="slang-memory-arena.h" />
@@ -253,4 +254,4 @@
   <Import Project="$(VCTargetsPath)\Microsoft.Cpp.targets" />
   <ImportGroup Label="ExtensionTargets">
   </ImportGroup>
-</Project>
\ No newline at end of file
+</Project> 
\ No newline at end of file
diff --git a/source/core/core.vcxproj.filters b/source/core/core.vcxproj.filters
index 4331745ba..7514fa1c9 100644
--- a/source/core/core.vcxproj.filters
+++ b/source/core/core.vcxproj.filters
@@ -54,6 +54,9 @@
     <ClInclude Include="slang-io.h">
       <Filter>Header Files</Filter>
     </ClInclude>
+    <ClInclude Include="slang-linked-list.h">
+      <Filter>Header Files</Filter>
+    </ClInclude>
     <ClInclude Include="slang-list.h">
       <Filter>Header Files</Filter>
     </ClInclude>
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 <typename T>
 	class HashSet : public HashSetBase<T, Dictionary<T, _DummyClass>>
 	{};
+
+    template <typename TKey, typename TValue>
+    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<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
+        {
+            const unsigned int hash = (unsigned int)getHashCode(key);
+            return ((unsigned int)(hash * 2654435761)) % bucketSizeMinusOne;
+        }
+        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;
+                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)
+                {
+                    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 OrderedDictionary<TKey, TValue>* dict;
+            TKey key;
+
+        public:
+            ItemProxy(const TKey& _key, const OrderedDictionary<TKey, TValue>* _dict)
+            {
+                this->dict = _dict;
+                this->key = _key;
+            }
+            ItemProxy(TKey&& _key, const OrderedDictionary<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 ((OrderedDictionary<TKey, TValue>*)dict)
+                    ->Set(KeyValuePair<TKey, TValue>(_Move(key), val));
+            }
+            TValue& operator=(TValue&& val)
+            {
+                return ((OrderedDictionary<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:
+        OrderedDictionary()
+        {
+            bucketSizeMinusOne = -1;
+            _count = 0;
+            hashMap = 0;
+        }
+        template <typename Arg, typename... Args> OrderedDictionary(Arg arg, Args... args)
+        {
+            Init(arg, args...);
+        }
+        OrderedDictionary(const OrderedDictionary<TKey, TValue>& other)
+            : bucketSizeMinusOne(-1)
+            , _count(0)
+            , hashMap(0)
+        {
+            *this = other;
+        }
+        OrderedDictionary(OrderedDictionary<TKey, TValue>&& other)
+            : bucketSizeMinusOne(-1)
+            , _count(0)
+            , hashMap(0)
+        {
+            *this = (_Move(other));
+        }
+        OrderedDictionary<TKey, TValue>&
+        operator=(const OrderedDictionary<TKey, TValue>& other)
+        {
+            if (this == &other)
+                return *this;
+            Clear();
+            for (auto& item : other)
+                Add(item.Key, item.Value);
+            return *this;
+        }
+        OrderedDictionary<TKey, TValue>&
+        operator=(OrderedDictionary<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;
+            kvPairs = _Move(other.kvPairs);
+            return *this;
+        }
+        ~OrderedDictionary() { Free(); }
+    };
+
+    template <typename T> class OrderedHashSet : public HashSetBase<T, OrderedDictionary<T, _DummyClass>>
+    {};
 }
 
 #endif
diff --git a/source/core/slang-linked-list.h b/source/core/slang-linked-list.h
new file mode 100644
index 000000000..7c9987397
--- /dev/null
+++ b/source/core/slang-linked-list.h
@@ -0,0 +1,306 @@
+#ifndef SLANG_CORE_LINKED_LIST_H
+#define SLANG_CORE_LINKED_LIST_H
+
+#include "../../slang.h"
+
+#include "slang-allocator.h"
+
+namespace Slang
+{
+template <typename T>
+class LinkedList;
+
+template <typename T>
+class LinkedNode
+{
+    template <typename T1> friend class LinkedList;
+
+private:
+    LinkedNode<T>* prev = nullptr;
+    LinkedNode<T>* next = nullptr;
+    LinkedList<T>* list;
+
+public:
+    T Value;
+    LinkedNode(LinkedList<T>* lnk)
+        : list(lnk)
+    {
+    };
+    LinkedNode<T>* GetPrevious() { return prev; };
+    LinkedNode<T>* GetNext() { return next; };
+    LinkedNode<T>* InsertAfter(const T& nData)
+    {
+        LinkedNode<T>* n = new LinkedNode<T>(list);
+        n->Value = nData;
+        n->prev = this;
+        n->next = this->next;
+        LinkedNode<T>* npp = n->next;
+        if (npp)
+        {
+            npp->prev = n;
+        }
+        next = n;
+        if (!n->next)
+            list->tail = n;
+        list->count++;
+        return n;
+    };
+    LinkedNode<T>* InsertBefore(const T& nData)
+    {
+        LinkedNode<T>* n = new LinkedNode<T>(list);
+        n->Value = nData;
+        n->prev = prev;
+        n->next = this;
+        prev = n;
+        LinkedNode<T>* npp = n->prev;
+        if (npp)
+            npp->next = n;
+        if (!n->prev)
+            list->head = n;
+        list->count++;
+        return n;
+    };
+    void Delete()
+    {
+        if (prev)
+            prev->next = next;
+        if (next)
+            next->prev = prev;
+        list->count--;
+        if (list->head == this)
+        {
+            list->head = next;
+        }
+        if (list->tail == this)
+        {
+            list->tail = prev;
+        }
+        delete this;
+    }
+};
+
+template <typename T> class LinkedList
+{
+    template <typename T1> friend class LinkedNode;
+
+private:
+    LinkedNode<T>*head, *tail;
+    int count;
+
+public:
+    class Iterator
+    {
+    public:
+        LinkedNode<T>*Current, *Next;
+        void SetCurrent(LinkedNode<T>* cur)
+        {
+            Current = cur;
+            if (Current)
+                Next = Current->GetNext();
+            else
+                Next = 0;
+        }
+        Iterator() { Current = Next = 0; }
+        Iterator(LinkedNode<T>* cur) { SetCurrent(cur); }
+        T& operator*() const { return Current->Value; }
+        Iterator& operator++()
+        {
+            SetCurrent(Next);
+            return *this;
+        }
+        Iterator operator++(int)
+        {
+            Iterator rs = *this;
+            SetCurrent(Next);
+            return rs;
+        }
+        bool operator!=(const Iterator& iter) const { return Current != iter.Current; }
+        bool operator==(const Iterator& iter) const { return Current == iter.Current; }
+    };
+    Iterator begin() const { return Iterator(head); }
+    Iterator end() const { return Iterator(0); }
+
+public:
+    LinkedList()
+        : head(0)
+        , tail(0)
+        , count(0)
+    {}
+    ~LinkedList() { Clear(); }
+    LinkedList(const LinkedList<T>& link)
+        : head(0)
+        , tail(0)
+        , count(0)
+    {
+        this->operator=(link);
+    }
+    LinkedList(LinkedList<T>&& link)
+        : head(0)
+        , tail(0)
+        , count(0)
+    {
+        this->operator=(_Move(link));
+    }
+    LinkedList<T>& operator=(LinkedList<T>&& link)
+    {
+        if (head != 0)
+            Clear();
+        head = link.head;
+        tail = link.tail;
+        count = link.count;
+        link.head = 0;
+        link.tail = 0;
+        link.count = 0;
+        for (auto node = head; node; node = node->GetNext())
+            node->list = this;
+        return *this;
+    }
+    LinkedList<T>& operator=(const LinkedList<T>& link)
+    {
+        if (head != 0)
+            Clear();
+        auto p = link.head;
+        while (p)
+        {
+            AddLast(p->Value);
+            p = p->GetNext();
+        }
+        return *this;
+    }
+    template <typename IteratorFunc> void ForEach(const IteratorFunc& f)
+    {
+        auto p = head;
+        while (p)
+        {
+            f(p->Value);
+            p = p->GetNext();
+        }
+    }
+    LinkedNode<T>* GetNode(int x)
+    {
+        LinkedNode<T>* pCur = head;
+        for (int i = 0; i < x; i++)
+        {
+            if (pCur)
+                pCur = pCur->next;
+            else
+                SLANG_UNEXPECTED("Index out of range");
+        }
+        return pCur;
+    };
+    LinkedNode<T>* Find(const T& fData)
+    {
+        for (LinkedNode<T>* pCur = head; pCur; pCur = pCur->next)
+        {
+            if (pCur->Value == fData)
+                return pCur;
+        }
+        return 0;
+    };
+    LinkedNode<T>* FirstNode() const { return head; };
+    T& First() const
+    {
+        if (!head)
+            SLANG_UNEXPECTED("LinkedList: index out of range.");
+        return head->Value;
+    }
+    T& Last() const
+    {
+        if (!tail)
+            SLANG_UNEXPECTED("LinkedList: index out of range.");
+        return tail->Value;
+    }
+    LinkedNode<T>* LastNode() const { return tail; };
+    LinkedNode<T>* AddLast(const T& nData)
+    {
+        LinkedNode<T>* n = new LinkedNode<T>(this);
+        n->Value = nData;
+        n->prev = tail;
+        if (tail)
+            tail->next = n;
+        n->next = 0;
+        tail = n;
+        if (!head)
+            head = n;
+        count++;
+        return n;
+    };
+    // Insert a blank node
+    LinkedNode<T>* AddLast()
+    {
+        LinkedNode<T>* n = new LinkedNode<T>(this);
+        n->prev = tail;
+        if (tail)
+            tail->next = n;
+        n->next = 0;
+        tail = n;
+        if (!head)
+            head = n;
+        count++;
+        return n;
+    };
+    LinkedNode<T>* AddFirst(const T& nData)
+    {
+        LinkedNode<T>* n = new LinkedNode<T>(this);
+        n->Value = nData;
+        n->prev = 0;
+        n->next = head;
+        if (head)
+            head->prev = n;
+        head = n;
+        if (!tail)
+            tail = n;
+        count++;
+        return n;
+    };
+    void Delete(LinkedNode<T>* n, int Count = 1)
+    {
+        LinkedNode<T>*n1, *n2 = 0, *tn;
+        n1 = n->prev;
+        tn = n;
+        int numDeleted = 0;
+        for (int i = 0; i < Count; i++)
+        {
+            n2 = tn->next;
+            delete tn;
+            tn = n2;
+            numDeleted++;
+            if (tn == 0)
+                break;
+        }
+        if (n1)
+            n1->next = n2;
+        else
+            head = n2;
+        if (n2)
+            n2->prev = n1;
+        else
+            tail = n1;
+        count -= numDeleted;
+    }
+    void Clear()
+    {
+        for (LinkedNode<T>* n = head; n;)
+        {
+            LinkedNode<T>* tmp = n->next;
+            delete n;
+            n = tmp;
+        }
+        head = 0;
+        tail = 0;
+        count = 0;
+    }
+    List<T> ToList() const
+    {
+        List<T> rs;
+        rs.Reserve(count);
+        for (auto& item : *this)
+        {
+            rs.Add(item);
+        }
+        return rs;
+    }
+    int Count() { return count; }
+};
+} // namespace Slang
+#endif
diff --git a/source/slang/slang.vcxproj b/source/slang/slang.vcxproj
index 563014c5b..dcbc3865e 100644
--- a/source/slang/slang.vcxproj
+++ b/source/slang/slang.vcxproj
@@ -417,4 +417,4 @@
   <Import Project="$(VCTargetsPath)\Microsoft.Cpp.targets" />
   <ImportGroup Label="ExtensionTargets">
   </ImportGroup>
-</Project> 
\ No newline at end of file
+</Project>
\ No newline at end of file