CascadeNewArray.h

Go to the documentation of this file.

//
// CascadeNewArray.h - header file for class CascadeNewArray
//
// Copyright (c) 2002, Roku, LLC.  All rights reserved.
//

#ifndef _ROKU_INCLUDE_CASCADE_UTIL_CASCADENEWARRAY_H
#define _ROKU_INCLUDE_CASCADE_UTIL_CASCADENEWARRAY_H

#include <cascade/CascadeObject.h>

// template class CascadeNewArray<TYPE>
//
// good general purpose true array for fast random access of elements
// (for sorting/searching).
// provides automatic expansion of array elements -
// it's expensive when expansion happens - new array memory allocation,
// old element memcpy with each new array element getting its constructor
// invoked.  Inserting or removing elements in the middle of the array
// is also costly as it involves a shift of memory.  Use a CascadeListArray for
// an array with good insert/remove performance.
#undef CASSERT  /* temporary */
#define CASSERT(x) do {} while (false) /* temporary */

#if defined(new)
#error "new cannot be #defined when including this file"
#endif

// class CascadeNewArray placement new helper implementation
namespace CascadePrivate { class ArrayPlacementHelper { }; }
inline void * operator new(MemoryWord nSize, void * pMem, CascadePrivate::ArrayPlacementHelper *)
{
    return pMem;
}

// class CascadeNewArray quicksort helper
namespace CascadePrivate { void CascadeNewArray_QuickSortHelper(void * base, u32 num, int width, void * pFunc); }

// class CascadeNewArray
template <class TYPE>
class CascadeNewArray : public CascadeObject
{
public:
    CascadeNewArray(u32 nInitialMemSize = kDefaultInitialMemSize);
    CascadeNewArray(const CascadeNewArray & that);
    virtual ~CascadeNewArray();
public:
    CascadeNewArray & operator = (const CascadeNewArray & that);
public:
    void   SetAt(u32 nIndex, const TYPE & data);
    TYPE & GetAt(u32 nIndex) const;
    TYPE & operator[](u32 nIndex) const;
    void InsertAt(u32 nIndex, const TYPE & data);
    void RemoveAt(u32 nIndex);
    void Append(const TYPE & pData);
    u32  GetSize() const;
    void SetSize(u32 nSize);
    bool IsEmpty() const;

    typedef int (CompareFunction)(const TYPE * pElement1, const TYPE * pElement2);
        // CompareFunctions are used for QuickSort.  See QuickSort.

    void QuickSort(CompareFunction * pCompareFunction);
        // QuickSort performs a quicksort on the array, given a compare function
        // WARNING: QuickSort will only work if it can memmove the elements of the
        // array around without regard to their type (i.e. it uses memmove on the sizeof an
        // element, not a copy constructor or = operator).  As a result, QuickSort is good for sorting
        // arrays of pointers, not so good at sorting structures or classes unless they
        // can be memmoved.

protected:
    enum { kDefaultInitialMemSize = 8 };

protected:
    TYPE * m_pData;
    u32 m_nSize;
    u32 m_nMemSize;

protected:
    inline static void PlacementNewConstruct(TYPE * pObjects, u32 nNumObjects)
    {
        u8 * pBytes = (u8 *)pObjects;
            u32 nBytes = nNumObjects * sizeof(TYPE);
        while (nBytes--) *pBytes++ = 0;
            for (; nNumObjects--; pObjects++) ::new((void *)pObjects, (CascadePrivate::ArrayPlacementHelper *)NULL) TYPE;
    }
    inline static void ManualDestruct(TYPE * pObjects, u32 nNumObjects)
    {
        for (; nNumObjects--; pObjects++) pObjects->~TYPE();
    }
    inline static void arraymemmove(void * pDest, const void * pSource, u32 nCount)
    {
        if ((u32)pDest > (u32)pSource)
        {
            // moving up, start at end of pSource, move to end of pDest
            u8 * pDEST = (u8 *)pDest + nCount - 1;
            u8 * pSOURCE = (u8 *)pSource + nCount - 1;
            for (; nCount--;) *pDEST-- = *pSOURCE--;
        }
        else
        {
            // moving down, start at beginning of pSource and pDest
            u8 * pDEST = (u8 *)pDest;
            u8 * pSOURCE = (u8 *)pSource;
            for (; nCount--;) *pDEST++ = *pSOURCE++;
        }
    }
    inline static void arraymemcpy(void * pDest, const void * pSource, u32 nCount)
    {
        u8 * pDEST = (u8 *)pDest;
        u8 * pSOURCE = (u8 *)pSource;
        for (; nCount--;) *pDEST++ = *pSOURCE++;
    }
};

// template class CascadeNewArray<TYPE> implementation
template <class TYPE>
CascadeNewArray<TYPE>::CascadeNewArray(u32 nInitialMemSize)
{
        m_nSize = m_nMemSize = 0;
        m_pData = NULL;
    SetSize(nInitialMemSize);
    SetSize(0);
}

template <class TYPE>
CascadeNewArray<TYPE>::CascadeNewArray(const CascadeNewArray<TYPE> & that)
{
        m_nSize = m_nMemSize = 0;
        m_pData = NULL;
        
        u32 nThatSize = that.GetSize();
        if (0 == nThatSize)
        {
        SetSize(that.m_nMemSize);
        SetSize(0);
        }
        else
        {
           SetSize(nThatSize);
           for (u32 i = 0; i < nThatSize; i++) m_pData[i] = that.m_pData[i];
        }
}

template <class TYPE>
CascadeNewArray<TYPE>::~CascadeNewArray()
{
        if (m_pData)
        {
        ManualDestruct(m_pData, m_nMemSize);
                delete [] (u8 *)m_pData;
        }
}

template <class TYPE>
CascadeNewArray<TYPE> &
CascadeNewArray<TYPE>::operator = (const CascadeNewArray<TYPE> & that)
{
    SetSize(that.m_nSize);
    for (u32 i = 0; i < that.m_nSize; i++) m_pData[i] = that.m_pData[i];
    return *this;
}

template <class TYPE>
inline void
CascadeNewArray<TYPE>::SetAt(u32 nIndex, const TYPE & data)
{
        CASSERT(nIndex < m_nSize);
    m_pData[nIndex] = data;
}

template <class TYPE>
inline TYPE &
CascadeNewArray<TYPE>::GetAt(u32 nIndex) const
{
        CASSERT(nIndex < m_nSize);
    return m_pData[nIndex];
}

template <class TYPE>
void
CascadeNewArray<TYPE>::InsertAt(u32 nIndex, const TYPE & data)
{
    if (nIndex >= m_nSize)
    {
        // inserting after the end of the array, make room
        SetSize(nIndex + 1);
    }
    else
    {
        // inserting into the middle, make room and shift up
        SetSize(m_nSize + 1);
                // destruct the top slot that SetSize constructed since we're gonna memmove into it
        ManualDestruct(&m_pData[m_nSize-1], 1);
        // memmove everything up one
        //memmove(&m_pData[nIndex+1], &m_pData[nIndex], ((m_nSize-1) - nIndex) * sizeof(TYPE));
        arraymemmove(&m_pData[nIndex+1], &m_pData[nIndex], ((m_nSize-1) - nIndex) * sizeof(TYPE));
                // re-construct the slot we're inserting into before copying into it
        PlacementNewConstruct(&m_pData[nIndex], 1);
    }
    
        CASSERT(nIndex < m_nSize);
    m_pData[nIndex] = data;
}

template <class TYPE>
void
CascadeNewArray<TYPE>::RemoveAt(u32 nIndex)
{       
        CASSERT(nIndex < m_nSize);

    // destruct what we're removing
    ManualDestruct(&m_pData[nIndex], 1);

    // shift elements down if required
        //if (nIndex < (m_nSize - 1)) memmove(&m_pData[nIndex], &m_pData[nIndex + 1], (m_nSize - (nIndex + 1)) * sizeof(TYPE));
        if (nIndex < (m_nSize - 1)) arraymemmove(&m_pData[nIndex], &m_pData[nIndex + 1], (m_nSize - (nIndex + 1)) * sizeof(TYPE));
        // re-construct the slot we just exposed
    PlacementNewConstruct(&m_pData[m_nSize - 1], 1);

    // decrement the size of the array
    m_nSize--;
}

template <class TYPE>
inline void
CascadeNewArray<TYPE>::Append(const TYPE & data)
{
    InsertAt(m_nSize, data);
}

template <class TYPE>
inline u32
CascadeNewArray<TYPE>::GetSize() const
{
        return m_nSize;
}

template <class TYPE>
void
CascadeNewArray<TYPE>::SetSize(u32 nSize)
{
        if (nSize > m_nMemSize)
        {
        u32 nNewMemSize;
        if (m_nMemSize)
        {
            u32 nDouble = 2 * m_nMemSize;
            nNewMemSize = nDouble * ((nSize / nDouble) + 1);
        }
        else nNewMemSize = nSize;

        // just alloc the nSize normalized up to the nearest grow size
                u32 nBytesToAlloc = sizeof(TYPE) * nNewMemSize;
                TYPE * pNewData = (TYPE *) new u8[nBytesToAlloc];

        // memcpy the old memory into the new
        //if (m_nMemSize) memcpy(pNewData, m_pData, m_nMemSize * sizeof(TYPE));
        if (m_nMemSize) arraymemcpy(pNewData, m_pData, m_nMemSize * sizeof(TYPE));

        // construct the new entries (m_nSize to nNewMemSize -1).
        PlacementNewConstruct(&pNewData[m_nSize], nNewMemSize - m_nSize);

        // free the old data, and remember the new data
                if (m_pData) delete [] (u8 *)m_pData;
                m_pData = pNewData;
                m_nMemSize = nNewMemSize;
        }

    m_nSize = nSize;
}

template <class TYPE>
inline bool
CascadeNewArray<TYPE>::IsEmpty() const
{
        return (m_nSize == 0);
}

template <class TYPE>
inline TYPE &
CascadeNewArray<TYPE>::operator[](u32 nIndex) const
{
        CASSERT(nIndex < m_nSize);
    return m_pData[nIndex];
}

template <class TYPE>
void
CascadeNewArray<TYPE>::QuickSort(CompareFunction * pCompareFunction)
{
    CascadePrivate::CascadeNewArray_QuickSortHelper((void *)m_pData, m_nSize, sizeof(TYPE), (void *)pCompareFunction);
}

#endif // #ifndef _ROKU_INCLUDE_CASCADE_UTIL_CASCADENEWARRAY_H

//  LOG
//  07-Feb-04   dwoodward       created
//  19-Feb-04   dwoodward       streamlined
//  29-Mar-04   dwoodward   disabled ManualDestruct on VDK
//  14-Apr-04   dwoodward   added copy constructor and = operator
//  01-Dec-04   dsletten    construct exposed slot in RemoveAt()
//  12-May-05   dwoodward   added QuickSort
//  07-Jun-05   dsletten    remove VDK workaround

---