Initial population of CoreRT Runtime files.

1 files changed, 408 insertions, 0 deletions

diff --git a/src/Native/Runtime/slist.inl b/src/Native/Runtime/slist.inl
new file mode 100644
index 000000000..9255af955
--- /dev/null
+++ b/src/Native/Runtime/slist.inl
@@ -0,0 +1,408 @@
+//
+// Copyright (c) Microsoft Corporation.  All rights reserved.
+// Licensed under the MIT license. See LICENSE file in the project root for full license information.
+//
+MSVC_SAVE_WARNING_STATE()
+MSVC_DISABLE_WARNING(4127)  // conditional expression is constant --
+                            // while (true) loops and compile time template constants cause this.
+
+
+//-------------------------------------------------------------------------------------------------
+namespace rh { namespace std
+{
+    // Specialize rh::std::find for SList iterators so that it will use _Traits::Equals.
+    template<class _Tx, class _Traits, class _Ty>
+    inline
+    typename SList<_Tx, _Traits>::Iterator find(
+        typename SList<_Tx, _Traits>::Iterator _First,
+        typename SList<_Tx, _Traits>::Iterator _Last,
+        const _Ty& _Val)
+    {   // find first matching _Val
+        for (; _First != _Last; ++_First)
+            if (_Traits::Equals(*_First, _Val))
+                break;
+        return (_First);
+    }
+} // namespace std
+} // namespace rh
+
+//-------------------------------------------------------------------------------------------------
+inline
+void DoNothingFailFastPolicy::FailFast()
+{
+    // Intentionally a no-op.
+}
+
+//-------------------------------------------------------------------------------------------------
+template <typename T, typename FailFastPolicy>
+inline
+typename DefaultSListTraits<T, FailFastPolicy>::PTR_PTR_T DefaultSListTraits<T, FailFastPolicy>::GetNextPtr(
+    PTR_T pT)
+{
+    ASSERT(pT != NULL);
+    return dac_cast<PTR_PTR_T>(dac_cast<TADDR>(pT) + offsetof(T, m_pNext));
+}
+
+//-------------------------------------------------------------------------------------------------
+template <typename T, typename FailFastPolicy>
+inline
+bool DefaultSListTraits<T, FailFastPolicy>::Equals(
+    PTR_T pA,
+    PTR_T pB)
+{   // Default is pointer comparison
+    return pA == pB;
+}
+
+//-------------------------------------------------------------------------------------------------
+template <typename T, typename Traits>
+inline
+SList<T, Traits>::SList()
+    : m_pHead(NULL)
+{
+}
+
+//-------------------------------------------------------------------------------------------------
+template <typename T, typename Traits>
+inline
+bool SList<T, Traits>::IsEmpty()
+{
+    return Begin() == End();
+}
+
+//-------------------------------------------------------------------------------------------------
+template <typename T, typename Traits>
+inline
+typename SList<T, Traits>::PTR_T SList<T, Traits>::GetHead()
+{
+    return m_pHead;
+}
+
+//-------------------------------------------------------------------------------------------------
+template <typename T, typename Traits>
+inline
+void SList<T, Traits>::PushHead(
+    PTR_T pItem)
+{
+    NO_DAC();
+    Begin().Insert(pItem);
+}
+
+//-------------------------------------------------------------------------------------------------
+template <typename T, typename Traits>
+inline
+void SList<T, Traits>::PushHeadInterlocked(
+    PTR_T pItem)
+{
+    NO_DAC();
+    ASSERT(pItem != NULL);
+    ASSERT(IS_ALIGNED(&m_pHead, sizeof(void*)));
+
+    while (true)
+    {
+        *GetNextPtr(pItem) = *reinterpret_cast<T * volatile *>(&m_pHead);
+        if (PalInterlockedCompareExchangePointer(
+                reinterpret_cast<void * volatile *>(&m_pHead),
+                reinterpret_cast<void *>(pItem),
+                reinterpret_cast<void *>(*GetNextPtr(pItem))) == reinterpret_cast<void *>(*GetNextPtr(pItem)))
+        {
+            break;
+        }
+    }
+}
+
+//-------------------------------------------------------------------------------------------------
+template <typename T, typename Traits>
+inline
+typename SList<T, Traits>::PTR_T SList<T, Traits>::PopHead()
+{
+    NO_DAC();
+    PTR_T pRet = *Begin();
+    Begin().Remove();
+    return pRet;
+}
+
+#ifdef FEATURE_VSD
+//-------------------------------------------------------------------------------------------------
+// This API is currently used only by VSD and it has a race condition. Possibly not worth fixing since it's
+// hard and we may be getting rid of VSD entirely.
+template <typename T, typename Traits>
+inline
+typename SList<T, Traits>::PTR_T SList<T, Traits>::PopHeadInterlocked()
+{
+    NO_DAC();
+    ASSERT(IS_ALIGNED(&m_pHead, sizeof(void*)));
+
+    T* pRetItem = NULL;
+    while (true)
+    {
+        // The read of m_pHead->m_pNext must be volatile to ensure the compiler reads
+        // the value only once.
+        pRetItem = *reinterpret_cast<T * volatile *>(&m_pHead);
+
+        // It is impossible for
+        // pRetItem->m_pNext to be modified until the link is successfully removed from
+        // the list. If another thread beats us to the remove, then the interlocked operation
+        // will fail (since the value of m_pHead->m_pNext will have been updated by that thread's
+        // interlocked compare exchange), and we'll update pRetItem with the new value and
+        // try again, failing if there are no elements in the list.
+
+        // The above logic has a flaw: we don't guard against the head element being popped, another element
+        // pushed and then the original element being re-pushed in between our initial read of the head
+        // element's next pointer and the interlocked compare exchange operation. Such a sequence would drop
+        // an element on the floor. The OS SLIST implementation uses a much more complex list head to avoid
+        // this problem and imposes double-pointer alignment requirements on both the list head and entries as
+        // a result.
+
+        if (pRetItem == NULL ||
+            PalInterlockedCompareExchangePointer(
+                reinterpret_cast<void * volatile *>(&m_pHead),
+                reinterpret_cast<void *>(*GetNextPtr(pRetItem)),
+                reinterpret_cast<void *>(pRetItem)) == reinterpret_cast<void *>(pRetItem))
+        {
+            break;
+        }
+    }
+    return pRetItem;
+}
+#endif // FEATURE_VSD
+
+//-------------------------------------------------------------------------------------------------
+template <typename T, typename Traits>
+inline
+SList<T, Traits>::Iterator::Iterator(
+    Iterator const &it)
+    : m_ppCur(it.m_ppCur)
+#ifdef _DEBUG
+      , m_fIsValid(it.m_fIsValid)
+#endif
+{
+}
+
+//-------------------------------------------------------------------------------------------------
+template <typename T, typename Traits>
+inline
+SList<T, Traits>::Iterator::Iterator(
+    PTR_PTR_T ppItem)
+    : m_ppCur(ppItem)
+#ifdef _DEBUG
+      , m_fIsValid(true)
+#endif
+{
+}
+
+//-------------------------------------------------------------------------------------------------
+template <typename T, typename Traits>
+inline
+typename SList<T, Traits>::Iterator& SList<T, Traits>::Iterator::operator=(
+    Iterator const &it)
+{
+    m_ppCur = it.m_ppCur;
+#ifdef _DEBUG
+    m_fIsValid = it.m_fIsValid;
+#endif
+    return *this;
+}
+
+//-------------------------------------------------------------------------------------------------
+template <typename T, typename Traits>
+inline
+typename SList<T, Traits>::PTR_T SList<T, Traits>::Iterator::operator->()
+{
+    _Validate(e_HasValue);
+    return _Value();
+}
+
+//-------------------------------------------------------------------------------------------------
+template <typename T, typename Traits>
+inline
+typename SList<T, Traits>::PTR_T SList<T, Traits>::Iterator::operator*()
+{
+    _Validate(e_HasValue);
+    return _Value();
+}
+
+//-------------------------------------------------------------------------------------------------
+template <typename T, typename Traits>
+inline
+typename SList<T, Traits>::Iterator & SList<T, Traits>::Iterator::operator++()
+{
+    _Validate(e_HasValue); // Having a value means we're not at the end.
+    m_ppCur = Traits::GetNextPtr(_Value());
+    return *this;
+}
+
+//-------------------------------------------------------------------------------------------------
+template <typename T, typename Traits>
+inline
+typename SList<T, Traits>::Iterator SList<T, Traits>::Iterator::operator++(
+    int)
+{
+    _Validate(e_HasValue); // Having a value means we're not at the end.
+    PTR_PTR_T ppRet = m_ppCur;
+    ++(*this);
+    return Iterator(ppRet);
+}
+
+//-------------------------------------------------------------------------------------------------
+template <typename T, typename Traits>
+inline
+bool SList<T, Traits>::Iterator::operator==(
+    Iterator const &rhs)
+{
+    _Validate(e_CanCompare);
+    rhs._Validate(e_CanCompare);
+    return Traits::Equals(_Value(), rhs._Value());
+}
+
+//-------------------------------------------------------------------------------------------------
+template <typename T, typename Traits>
+inline
+bool SList<T, Traits>::Iterator::operator==(
+    PTR_T pT)
+{
+    _Validate(e_CanCompare);
+    return Traits::Equals(_Value(), pT);
+}
+
+//-------------------------------------------------------------------------------------------------
+template <typename T, typename Traits>
+inline
+bool SList<T, Traits>::Iterator::operator!=(
+    Iterator const &rhs)
+{
+    return !operator==(rhs);
+}
+
+//-------------------------------------------------------------------------------------------------
+template <typename T, typename Traits>
+inline /*static*/
+typename SList<T, Traits>::Iterator SList<T, Traits>::Iterator::End()
+{
+    return Iterator(NULL);
+}
+
+//-------------------------------------------------------------------------------------------------
+template <typename T, typename Traits>
+inline
+typename SList<T, Traits>::Iterator SList<T, Traits>::Iterator::Insert(
+    PTR_T pItem)
+{
+    NO_DAC();
+    _Validate(e_CanInsert);
+    *Traits::GetNextPtr(pItem) = *m_ppCur;
+    *m_ppCur = pItem;
+    Iterator itRet(m_ppCur);
+    ++(*this);
+    return itRet;
+}
+
+//-------------------------------------------------------------------------------------------------
+template <typename T, typename Traits>
+inline
+typename SList<T, Traits>::Iterator SList<T, Traits>::Iterator::Remove()
+{
+    NO_DAC();
+    _Validate(e_HasValue);
+    *m_ppCur = *Traits::GetNextPtr(*m_ppCur);
+    PTR_PTR_T ppRet = m_ppCur;
+    // Set it to End, so that subsequent misuse of this iterator will
+    // result in an AV rather than possible memory corruption.
+    *this = End();
+    return Iterator(ppRet);
+}
+
+//-------------------------------------------------------------------------------------------------
+template <typename T, typename Traits>
+inline
+typename SList<T, Traits>::PTR_T SList<T, Traits>::Iterator::_Value() const
+{
+    ASSERT(m_fIsValid);
+    return dac_cast<PTR_T>(m_ppCur == NULL ? NULL : *m_ppCur);
+}
+
+//-------------------------------------------------------------------------------------------------
+template <typename T, typename Traits>
+inline
+void SList<T, Traits>::Iterator::_Validate(e_ValidateOperation op) const
+{
+    ASSERT(m_fIsValid);
+    ASSERT(op == e_CanCompare || op == e_CanInsert || op == e_HasValue);
+
+    if ((op != e_CanCompare && m_ppCur == NULL) ||
+        (op == e_HasValue && *m_ppCur == NULL))
+    {
+        // NOTE: Default of DoNothingFailFastPolicy is a no-op, and so this function will be
+        // eliminated in retail builds. This is ok, as the subsequent operation will cause
+        // an AV, which will itself trigger a FailFast. Provide a different policy to get
+        // different behavior.
+        ASSERT_MSG(false, "Invalid SList::Iterator use.");
+        Traits::FailFast();
+#ifdef _DEBUG
+        m_fIsValid = false;
+#endif
+    }
+}
+
+//-------------------------------------------------------------------------------------------------
+template <typename T, typename Traits>
+inline
+typename SList<T, Traits>::Iterator SList<T, Traits>::Begin()
+{
+    typedef SList<T, Traits> T_THIS;
+    return Iterator(dac_cast<PTR_PTR_T>(
+        dac_cast<TADDR>(this) + offsetof(T_THIS, m_pHead)));
+}
+
+//-------------------------------------------------------------------------------------------------
+template <typename T, typename Traits>
+inline
+typename SList<T, Traits>::Iterator SList<T, Traits>::End()
+{
+    return Iterator::End();
+}
+
+//-------------------------------------------------------------------------------------------------
+template <typename T, typename Traits>
+inline
+typename SList<T, Traits>::Iterator SList<T, Traits>::FindFirst(PTR_T pItem)
+{
+    return rh::std::find(Begin(), End(), pItem);
+}
+
+//-------------------------------------------------------------------------------------------------
+template <typename T, typename Traits>
+inline
+bool SList<T, Traits>::RemoveFirst(PTR_T pItem)
+{
+    NO_DAC();
+    Iterator it = FindFirst(pItem);
+    if (it != End())
+    {
+        it.Remove();
+        return true;
+    }
+    else
+    {
+        return false;
+    }
+}
+
+//-------------------------------------------------------------------------------------------------
+template <typename T, typename Traits>
+inline
+typename SList<T, Traits>::Iterator SList<T, Traits>::Insert(Iterator & it, PTR_T pItem)
+{
+    return it.Insert(pItem);
+}
+
+//-------------------------------------------------------------------------------------------------
+template <typename T, typename Traits>
+inline
+typename SList<T, Traits>::Iterator SList<T, Traits>::Remove(Iterator & it)
+{
+    return it.Remove();
+}
+
+
+MSVC_RESTORE_WARNING_STATE()
+