Initial commit to populate CoreCLR repo

[tfs-changeset: 1407945]

1 files changed, 311 insertions, 0 deletions

diff --git a/src/utilcode/arraylist.cpp b/src/utilcode/arraylist.cpp
new file mode 100644
index 0000000000..801ab98f54
--- /dev/null
+++ b/src/utilcode/arraylist.cpp
@@ -0,0 +1,311 @@
+//
+// Copyright (c) Microsoft. All rights reserved.
+// Licensed under the MIT license. See LICENSE file in the project root for full license information.
+//
+
+#include "stdafx.h"
+
+#include "arraylist.h"
+#include "utilcode.h"
+#include "ex.h"
+
+//
+// ArrayList is a simple class which is used to contain a growable
+// list of pointers, stored in chunks.  Modification is by appending
+// only currently.  Access is by index (efficient if the number of
+// elements stays small) and iteration (efficient in all cases).
+//
+// An important property of an ArrayList is that the list remains
+// coherent while it is being modified (appended to). This means that readers
+// never need to lock when accessing it. (Locking is necessary among multiple
+// writers, however.)
+//
+
+void ArrayListBase::Clear()
+{
+    CONTRACTL
+    {
+        NOTHROW;
+        FORBID_FAULT;
+    }
+    CONTRACTL_END
+
+    ArrayListBlock *block = m_firstBlock.m_next;
+    while (block != NULL)
+    {
+        ArrayListBlock *next = block->m_next;
+        delete [] block;
+        block = next;
+    }
+    m_firstBlock.m_next = 0;
+    m_count = 0;
+}
+
+PTR_VOID * ArrayListBase::GetPtr(DWORD index) const
+{
+    STATIC_CONTRACT_NOTHROW;
+    STATIC_CONTRACT_FORBID_FAULT;
+    STATIC_CONTRACT_SO_TOLERANT;
+    STATIC_CONTRACT_CANNOT_TAKE_LOCK;
+    SUPPORTS_DAC;
+
+    _ASSERTE(index < m_count);
+
+    ArrayListBlock *b = (ArrayListBlock*)&m_firstBlock;
+    while (index >= b->m_blockSize)
+    {
+        PREFIX_ASSUME(b->m_next != NULL);
+        index -= b->m_blockSize;
+        b = b->m_next;
+    }
+
+    return b->m_array + index;
+}
+
+#ifndef DACCESS_COMPILE
+
+HRESULT ArrayListBase::Append(void *element)
+{
+    CONTRACTL
+    {
+        NOTHROW;
+        INJECT_FAULT(return E_OUTOFMEMORY;);
+    }
+    CONTRACTL_END
+
+    ArrayListBlock *b = (ArrayListBlock*)&m_firstBlock;
+    DWORD           count = m_count;
+
+    while (count >= b->m_blockSize)
+    {
+        count -= b->m_blockSize;
+
+        if (b->m_next == NULL)
+        {
+            _ASSERTE(count == 0);
+
+            DWORD nextSize = b->m_blockSize * 2;
+
+            ArrayListBlock *bNew = (ArrayListBlock *)
+              new (nothrow) BYTE [sizeof(ArrayListBlock) + nextSize * sizeof(void*)];
+
+            if (bNew == NULL)
+                return E_OUTOFMEMORY;
+
+            bNew->m_next = NULL;
+            bNew->m_blockSize = nextSize;
+
+            b->m_next = bNew;
+        }
+
+        b = b->m_next;
+    }
+
+    b->m_array[count] = element;
+
+    m_count++;
+
+    return S_OK;
+}
+
+#endif // #ifndef DACCESS_COMPILE
+
+DWORD ArrayListBase::FindElement(DWORD start, PTR_VOID element) const
+{
+    CONTRACTL
+    {
+        NOTHROW;
+        FORBID_FAULT;
+    }
+    CONTRACTL_END
+
+    DWORD index = start;
+
+    _ASSERTE(index <= m_count);
+
+    ArrayListBlock *b = (ArrayListBlock*)&m_firstBlock;
+
+    //
+    // Skip to the block containing start.
+    // index should be the index of start in the block.
+    //
+
+    while (b != NULL && index >= b->m_blockSize)
+    {
+        index -= b->m_blockSize;
+        b = b->m_next;
+    }
+
+    //
+    // Adjust start to be the index of the start of the block
+    //
+
+    start -= index;
+
+    //
+    // Compute max number of entries from the start of the block
+    //
+
+    DWORD max = m_count - start;
+
+    while (b != NULL)
+    {
+        //
+        // Compute end of search in this block - either end of the block
+        // or end of the array
+        //
+
+        DWORD blockMax;
+        if (max < b->m_blockSize)
+            blockMax = max;
+        else
+            blockMax = b->m_blockSize;
+
+        //
+        // Scan for element, until the end.
+        //
+
+        while (index < blockMax)
+        {
+            if (b->m_array[index] == element)
+                return start + index;
+            index++;
+        }
+
+        //
+        // Otherwise, increment block start index, decrement max count,
+        // reset index, and go to the next block (if any)
+        //
+
+        start += b->m_blockSize;
+        max -= b->m_blockSize;
+        index = 0;
+        b = b->m_next;
+    }
+
+    return (DWORD) NOT_FOUND;
+}
+
+BOOL ArrayListBase::Iterator::Next()
+{
+    LIMITED_METHOD_DAC_CONTRACT;
+
+    ++m_index;
+
+    if (m_index >= m_remaining)
+        return FALSE;
+
+    if (m_index >= m_block->m_blockSize)
+    {
+        m_remaining -= m_block->m_blockSize;
+        m_index -= m_block->m_blockSize;
+        m_total += m_block->m_blockSize;
+        m_block = m_block->m_next;
+    }
+
+    return TRUE;
+}
+
+#ifdef DACCESS_COMPILE
+
+void
+ArrayListBase::EnumMemoryRegions(CLRDataEnumMemoryFlags flags)
+{
+    SUPPORTS_DAC;
+
+    // Assume that 'this' is enumerated, either explicitly
+    // or because this class is embedded in another.
+
+    PTR_ArrayListBlock block = m_firstBlock.m_next;
+    while (block.IsValid())
+    {
+        block.EnumMem();
+        block = block->m_next;
+    }
+}
+
+#endif // #ifdef DACCESS_COMPILE
+
+
+void StructArrayListBase::Destruct (FreeProc *pfnFree)
+{
+    WRAPPER_NO_CONTRACT;
+    
+    StructArrayListEntryBase *pList = m_pChunkListHead;
+    while (pList)
+    {
+        StructArrayListEntryBase *pTrash = pList;
+        pList = pList->pNext;
+        pfnFree(this, pTrash);
+    }
+}
+
+// Copied from jit.h
+inline
+size_t              roundUp(size_t size, size_t mult = sizeof(size_t))
+{
+    assert(mult && ((mult & (mult-1)) == 0));   // power of two test
+
+    return  (size + (mult - 1)) & ~(mult - 1);
+}
+
+void StructArrayListBase::CreateNewChunk (SIZE_T InitialChunkLength, SIZE_T ChunkLengthGrowthFactor, SIZE_T cbElement, AllocProc *pfnAlloc, SIZE_T alignment)
+{
+    CONTRACTL {
+        THROWS;
+        PRECONDITION(!m_pChunkListHead || m_nItemsInLastChunk == m_nLastChunkCapacity);
+    } CONTRACTL_END;
+
+    SIZE_T nChunkCapacity;
+    if (!m_pChunkListHead)
+        nChunkCapacity = InitialChunkLength;
+    else
+        nChunkCapacity = m_nLastChunkCapacity * ChunkLengthGrowthFactor;
+    
+    S_SIZE_T cbBaseSize = S_SIZE_T(roundUp(sizeof(StructArrayListEntryBase), alignment));
+    S_SIZE_T cbChunk = cbBaseSize + 
+        S_SIZE_T(cbElement) * S_SIZE_T(nChunkCapacity);
+    _ASSERTE(!cbChunk.IsOverflow());
+    if(cbChunk.IsOverflow())
+    {
+        ThrowWin32(ERROR_ARITHMETIC_OVERFLOW);
+    }
+
+    StructArrayListEntryBase *pNewChunk = (StructArrayListEntryBase*)pfnAlloc(this, cbChunk.Value());
+
+    if (m_pChunkListTail)
+    {
+        _ASSERTE(m_pChunkListHead);
+        m_pChunkListTail->pNext = pNewChunk;
+    }
+    else
+    {
+        _ASSERTE(!m_pChunkListHead);
+        m_pChunkListHead = pNewChunk;
+    }
+    
+    pNewChunk->pNext = NULL;
+    m_pChunkListTail = pNewChunk;
+
+    m_nItemsInLastChunk = 0;
+    m_nLastChunkCapacity = nChunkCapacity;
+}
+
+
+void StructArrayListBase::ArrayIteratorBase::SetCurrentChunk (StructArrayListEntryBase *pChunk, SIZE_T nChunkCapacity)
+{
+    LIMITED_METHOD_CONTRACT;
+
+    m_pCurrentChunk = pChunk;
+
+    if (pChunk)
+    {
+        if (pChunk == m_pArrayList->m_pChunkListTail)
+            m_nItemsInCurrentChunk = m_pArrayList->m_nItemsInLastChunk;
+        else
+            m_nItemsInCurrentChunk = nChunkCapacity;
+
+        m_nCurrentChunkCapacity = nChunkCapacity;
+    }
+}
+