Dynamic array

[miteshpandey]

Following is implementation of a dynamic array. This is a production sample code from Microsoft but open source. I have shown relevant functions for my question.

template< typename TYPE >
HRESULT CGrowableArray<TYPE>::Add( const TYPE& value )
{
    HRESULT hr;
    if( FAILED( hr = SetSizeInternal( m_nSize + 1 ) ) )
        return hr;

    // Construct the new element
    ::new (&m_pData[m_nSize]) TYPE;

    // Assign
    m_pData[m_nSize] = value;
    ++m_nSize;

    return S_OK;
}

template< typename TYPE >
HRESULT CGrowableArray<TYPE>::Remove( int nIndex )
{
    if( nIndex < 0 || 
        nIndex >= m_nSize )
    {
        assert( false );
        return E_INVALIDARG;
    }

    // Destruct the element to be removed
    m_pData[nIndex].~TYPE();

    // Compact the array and decrease the size
    MoveMemory( &m_pData[nIndex], &m_pData[nIndex+1], sizeof(TYPE) * (m_nSize - (nIndex+1)) );
    --m_nSize;

    return S_OK;
}

template< typename TYPE >
HRESULT CGrowableArray<TYPE>::SetSize( int nNewMaxSize )
{
    int nOldSize = m_nSize;

    if( nOldSize > nNewMaxSize )
    {
        // Removing elements. Call dtor.

        for( int i = nNewMaxSize; i < nOldSize; ++i )
            m_pData[i].~TYPE();
    }

    // Adjust buffer.  Note that there's no need to check for error
    // since if it happens, nOldSize == nNewMaxSize will be true.)
    HRESULT hr = SetSizeInternal( nNewMaxSize );

    if( nOldSize < nNewMaxSize )
    {
        // Adding elements. Call ctor.

        for( int i = nOldSize; i < nNewMaxSize; ++i )
            ::new (&m_pData[i]) TYPE;
    }

    return hr;
}

template< typename TYPE >
HRESULT CGrowableArray<TYPE>::SetSizeInternal( int nNewMaxSize )
{

    if( nNewMaxSize < 0 )
    {
        assert( false );
        return E_INVALIDARG;
    }

    if( nNewMaxSize == 0 )
    {
        // Shrink to 0 size & cleanup
        if( m_pData )
        {
            free( m_pData );
            m_pData = NULL;
        }

        m_nMaxSize = 0;
        m_nSize = 0;
    }
    else if( m_pData == NULL || nNewMaxSize > m_nMaxSize )
    {
        // Grow array
        int nGrowBy = ( m_nMaxSize == 0 ) ? 16 : m_nMaxSize;
        nNewMaxSize = max( nNewMaxSize, m_nMaxSize + nGrowBy );

       TYPE* pDataNew = (TYPE*) realloc( m_pData, nNewMaxSize * sizeof(TYPE) );
        if( pDataNew == NULL )
            return E_OUTOFMEMORY;

        m_pData = pDataNew;
        m_nMaxSize = nNewMaxSize;
    }

    return S_OK;
}

void    RemoveAll() { SetSize(0); }

My question.

The Remove function doesn't free memory but calls MoveMemory.

But the RemoveAll function calls SetSize(0) which in turn calls SetSizeInternal with 0 and this function frees memory with a call to free(...).

Shouldn't Remove free memory for a single object that is removed? Does calling MoveMemory is enough and not calling free for the removed object?

I know the difference between using new/delete Vs Malloc/Alloc/free.

[SuperKoko]

Aghhhh
This code seems to not assume that the type is POD, since it calls (some) destructors and use new with placement!

But it is completely buggy!
And has undefined behaviour!
MoveMemory can only be used with POD types!
realloc too!

I know the difference between using new/delete Vs Malloc/Alloc/free.

These programmers don'tt !

[SuperKoko]

You seem also to have been confused by this thing.

The Remove function doesn't free memory but calls MoveMemory.

It leads to undefined behaviour with non-POD types...
Now, assuming that the guy use a proper function (std::copy) instead of MoveMemory.

He doesn't need to call free in Remove, because this array has two sizes (m_nSize and m_nMaxSize).
It is similar to std::vector sizes and capacities.

m_nMaxSize is not modified by Remove, but m_nSize is.

But the RemoveAll function calls SetSize(0) which in turn calls SetSizeInternal with 0 and this function frees memory with a call to free(...).

Yes, here the behaviour is correct.

SetSize has correct behaviour as long as the new size is smaller than the old m_nMaxSize, otherwise it has undefined behaviour (especially, realloc may move the memory).

[miteshpandey]

Thank you Super Koko

Originally posted by Super KoKo He doesn't need to call free in Remove, because this array has two sizes (m_nSize and m_nMaxSize).
It is similar to std::vector sizes and capacities.

That was the answer I was looking for

This code was taken from a sample program that came with DirectX 9.0c SDK. Microsoft encourages you to follow this sample's framework in your DirectX projects. So I find it hard to believe that it is buggy. So please help me to convince myself that it is buggy.

Both realloc and MoveMemory deal with pointers. Does it matter that the pointer referes to POD and non-POD types?

If I understand you, as also stated by MSDN that realloc function might not return the pointer that it was supplied with (meaning that the location would be different) but this is handled by the above code. It updates the m_pData member by the value returned by the realloc.

What do you think?

[SuperKoko]

Both realloc and MoveMemory deal with pointers. Does it matter that the pointer referes to POD and non-POD types?

It matters!
Because it does a binary copy of the non-POD type!
And, binary copying non-POD types makes undefined behaviour!

Since it is a move operation, it is less obvious than with binary copies that let the original object intact:
But here are examples of what can be wrong:

I am almost sure it will be buggy if an object with virtual inheritance is used.

Similarly, if an object contains a pointer to one of its member, the pointer will not point to the correct location, after the move operation:

struct A
{
int x;
int* p;
A():p(&x) {}
A(const A& other):x(other.x),p(&x) {}
~A() {}
A& operator=(const A& other)
{
x=other.x;
return *this;
}
};

[exterminator]

...but it work on the MS platform because they know that it will work. The same is the issue with CArray... their implementation is so not portable and gives wrong porgramming habit to people willing to write portable code. They use the C-allocation routines and mem* set of functions which only are supposed to work with POD types.. and as by the standards would lead to undefined behaviour with POD types.. but they will work on MS platform because may be that is what their intention is...

This is a piece of non-portable code from CArray:

//copy new data from old
memcpy(pNewData, m_pData, m_nSize * sizeof(TYPE));

MFC is well-known for its non-portable library.. Use standards containers or containers that use standard approach to implementation. That is the safest, portable and good way of doing things. Use std::vector instead of CGrowableArray/CArray. But if you are really coding MS-specific applications... no need to worry. Have a look at this thread about CArray:

How to create an int with 2 numbers and store it in a vector? Won't work...

Regards.

[SuperKoko]

but they will work on MS platform because may be that is what their intention is...

But, it does NOT work!
Seriously, you should try with a class containing a pointer to one of its member (or virtual deriving from another class).
Results should be funny!

[SuperKoko]

Here is the code with a few corrections (not tested);

template< typename TYPE >
HRESULT CGrowableArray<TYPE>::Add( const TYPE& value )
{
    HRESULT hr;
    if( FAILED( hr = SetSizeInternal( m_nSize + 1 ) ) )
        return hr;

    // Construct the new element
    ::new (&m_pData[m_nSize]) TYPE(value); // strongly exception safe!
   
    ++m_nSize;

    return S_OK;
}

template< typename TYPE >
HRESULT CGrowableArray<TYPE>::Remove( int nIndex )
{
    if( nIndex < 0 || 
        nIndex >= m_nSize )
    {
        assert( false );
        return E_INVALIDARG;
    }

    
    // Compact the array and decrease the size
    std::copy(m_pData+1, m_pData + m_nSize, m_pData);
    
    m_pData[m_nSize].~TYPE();
    --m_nSize;

    return S_OK; // met basic exception safety requirements (Consistency)!
}

template< typename TYPE >
HRESULT CGrowableArray<TYPE>::SetSize( int nNewSize ) // hey -- it is the new size, not the new max size!
{
    int nOldSize = m_nSize;

    if( nOldSize > nNewSize )
    {
        // Removing elements. Call dtor.

        for( int i = nNewSize; i < nOldSize; ++i )
            m_pData[i].~TYPE();
        m_nSize=nNewSize; // don't forget to assign m_nSize!
    }

    // Adjust buffer.  Note that there's no need to check for error
    // since if it happens, nOldSize == nNewSize will be true.)
    SetSizeInternal( nNewSize );

    if( nOldSize < nNewSize )
    {
        // Adding elements. Call ctor.

        for( int i = nOldSize; i < nNewSize; ++i )
            {::new (&m_pData[i]) TYPE;++m_nSize;} // m_nSize must be incremented
    }

    return hr;
} // basically exception safe (Consistency)
template< typename TYPE >
HRESULT CGrowableArray<TYPE>::SetSizeInternal( int nNewMaxSize )
{ // atomic, Consistency

    if( nNewMaxSize < 0 )
    {
        assert( false );
        return E_INVALIDARG;
    }

    if( nNewMaxSize == 0 )
    {
        // Shrink to 0 size & cleanup
        if( m_pData )
        {
            free( m_pData );
            m_pData = NULL;
        }

        m_nMaxSize = 0;
        m_nSize = 0;
    }
    else if( m_pData == NULL || nNewMaxSize > m_nMaxSize )
    {
        // Grow array
        int nGrowBy = ( m_nMaxSize == 0 ) ? 16 : m_nMaxSize;
        nNewMaxSize = max( nNewMaxSize, m_nMaxSize + nGrowBy );
       
        TYPE* pNewData=(TYPE*)malloc(nNewMaxSize*sizeof(TYPE));
        if (NULL==pNewData) return E_OUTOFMEMORY;
        int i;
        try
        {
        for(i=0;i<m_nSize;++i)
            ::new (pNewData+i) TYPE(m_pData[i]);
        }
        catch(...)
        {
        while(--i >= 0) pNewData[i].~TYPE();
        throw;
        }
        for(i=0;i<m_nSize;++i) pData[i].~TYPE();

        free(m_pData);
        m_pData = pNewData;
        m_nMaxSize = nNewMaxSize;
    }

    return S_OK;
}

I detected another bug:
Even with POD types, it is buggy!
The SetSize function didn't set the m_nSize data member!

[miteshpandey]

Thank you all.

It seems that Microsoft didn't want this array to be used in general.

[SuperKoko]

It seems that Microsoft didn't want this array to be used in general.

I understand that one could want to write an array for POD types.
It allows to use realloc.
But, he should not make an hybrid class!
He should not call destructors and constructors!

In addition, this class has still a bug : SetSize doesn't change m_nSize.

What is really wrong with that class, is the fact that many people will think that it work with non-POD types, and it'll work with many non-POD types, but sometimes it will crash... And these bugs will be very very hard to understand for the poor programmer.

And with a lot of non-POD types, it will crash seldomly, so there will be bugs in released products!