CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 10 of 10

Thread: Dynamic array

  1. #1
    Join Date
    Apr 2003
    Location
    kathmandu, nepal
    Posts
    1,570

    Dynamic array

    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.
    Code:
    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;
    }
    Code:
    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;
    }
    Code:
    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;
    }
    Code:
    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;
    }
    Code:
    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.
    Last edited by miteshpandey; April 1st, 2006 at 09:35 AM.
    If there is no love sun won't shine

  2. #2
    Join Date
    Feb 2005
    Location
    Normandy in France
    Posts
    4,590

    Re: Dynamic array

    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 !
    "inherit to be reused by code that uses the base class, not to reuse base class code", Sutter and Alexandrescu, C++ Coding Standards.
    Club of lovers of the C++ typecasts cute syntax: Only recorded member.

    Out of memory happens! Handle it properly!
    Say no to g_new()!

  3. #3
    Join Date
    Feb 2005
    Location
    Normandy in France
    Posts
    4,590

    Re: Dynamic array

    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).
    Last edited by SuperKoko; April 1st, 2006 at 09:51 AM.
    "inherit to be reused by code that uses the base class, not to reuse base class code", Sutter and Alexandrescu, C++ Coding Standards.
    Club of lovers of the C++ typecasts cute syntax: Only recorded member.

    Out of memory happens! Handle it properly!
    Say no to g_new()!

  4. #4
    Join Date
    Apr 2003
    Location
    kathmandu, nepal
    Posts
    1,570

    Re: Dynamic array

    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?
    If there is no love sun won't shine

  5. #5
    Join Date
    Feb 2005
    Location
    Normandy in France
    Posts
    4,590

    Re: Dynamic array

    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:
    Code:
    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;
    }
    };

  6. #6
    Join Date
    Feb 2005
    Location
    "The Capital"
    Posts
    5,306

    Re: Dynamic array

    ...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:
    Code:
    //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.
    Last edited by exterminator; April 1st, 2006 at 10:21 AM.

  7. #7
    Join Date
    Feb 2005
    Location
    Normandy in France
    Posts
    4,590

    Re: Dynamic array

    Quote Originally Posted by exterminator
    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!
    "inherit to be reused by code that uses the base class, not to reuse base class code", Sutter and Alexandrescu, C++ Coding Standards.
    Club of lovers of the C++ typecasts cute syntax: Only recorded member.

    Out of memory happens! Handle it properly!
    Say no to g_new()!

  8. #8
    Join Date
    Feb 2005
    Location
    Normandy in France
    Posts
    4,590

    Re: Dynamic array

    Here is the code with a few corrections (not tested);
    Code:
    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!

  9. #9
    Join Date
    Apr 2003
    Location
    kathmandu, nepal
    Posts
    1,570

    Re: Dynamic array

    Thank you all.

    It seems that Microsoft didn't want this array to be used in general.
    If there is no love sun won't shine

  10. #10
    Join Date
    Feb 2005
    Location
    Normandy in France
    Posts
    4,590

    Re: Dynamic array

    Quote Originally Posted by miteshpandey
    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!
    Last edited by SuperKoko; April 1st, 2006 at 11:41 AM.
    "inherit to be reused by code that uses the base class, not to reuse base class code", Sutter and Alexandrescu, C++ Coding Standards.
    Club of lovers of the C++ typecasts cute syntax: Only recorded member.

    Out of memory happens! Handle it properly!
    Say no to g_new()!

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  


Windows Mobile Development Center


Click Here to Expand Forum to Full Width




On-Demand Webinars (sponsored)