Jump to content

  • Log In with Google      Sign In   
  • Create Account


Custom sorted list class crashes


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
9 replies to this topic

#1 TheComet   Members   -  Reputation: 1156

Like
0Likes
Like

Posted 11 January 2014 - 10:30 AM

For an excersize, I write a class to contain elements. They are sorted using std::lower_bound before being inserted. Inserting duplicate items will silently fail.

 

I have this very strange bug that's causing stack frame corruption and I don't know why. I conclude it's this class because if I replace the container with std::vector instead of with my custom class, it works fine.

 

Can someone go over this code and see if they see anything wrong with it?

 

SortedList.hpp

// ----------------------------------------------------------------------------
// GOLSortedList.hpp
// ----------------------------------------------------------------------------

// ----------------------------------------------------------------------------
// include files

#include <iostream>

namespace GOL {

template <class T>
class SortedList
{
public:

    typedef T* iterator;
    typedef const T* const_iterator;

    /*!
     * @brief Default constructor
     */
    SortedList();

    /*!
     * @brief Constructs a sorted list with a specified pre-allocated chunk of memory
     * @param preallocate The amount of memory in sizeof(T) to allocate
     */
    SortedList( std::size_t preallocate );

    /*!
     * @brief Copy constructor
     */
    SortedList( const SortedList<T>& that );

    /*!
     * @brief Default destructor
     */
    ~SortedList();

    /*!
     * @brief Inserts an item into the sorted list
     * Will perform a binary search of all existing items in the list to
     * determine where to insert
     * @param item The item to insert
     */
    void insert( const T& item );

    /*!
     * @brief Erases an item from the list, shifting all data above it down
     * No memory re-allocation occurs during this process
     * @exception If the specified index in the list is out of bounds, an
     * exception is thrown.
     * @param index Index of the item to erase
     */
    void erase( std::size_t index );

    /*!
     * @brief Erases an item from the list, shifting all data above it down
     * No memory re-allocation occurs during this process
     * @param it The item to erase
     */
    void erase( iterator it );

    /*!
     * @brief Searches the list for the specified item
     * The complexity of the search is O(log(n)) (successive approximation).
     * If the item wasn't found, an iterator pointing at @a end() is returned.
     * @param item The item to look for
     * @return An iterator pointing to the item if it exists
     */
    iterator find( const T& item );

    /*!
     * @brief Clears the content of the list without de-allocating any memory
     */
    void clear();

    /*!
     * @brief Resizes the list and forces re-allocation of memory
     * @param size The size to re-allocate
     */
    void resize( std::size_t size );

    /*!
     * @brief Returns a pointer to the beginning of the data in the list
     * @return An iterator to the beginning of the data
     */
    iterator begin();

    /*!
     * @brief Returns a const pointer to the beginning of the data in the list
     * @return A const iterator to the beginning of the data
     */
    const_iterator begin() const;

    /*!
     * @brief Returns a pointer to the end of the data in the list
     * @return An iterator to the end of the data
     */
    iterator end();

    /*!
     * @brief Returns a const pointer to the end of the data in the list
     * @return A const iterator to the end of the data
     */
    const_iterator end() const;

    /*!
     * @brief Returns the size of the list (how many items are currently inserted)
     * @return The size of the list
     */
    std::size_t size();

    /*!
     * @brief Returns the amount of memory the list has allocated
     * @return The allocated size of the list
     */
    std::size_t allocatedSize();

    /*!
     * @brief Returns a reference to the specified item in the list
     * @exception If the specified index in the list is out of bounds, an
     * exception is thrown.
     * @param index The index of the item
     * @return A reference to the specified item
     */
    T& at( std::size_t index );

    /*!
     * @brief Returns a reference to the specified item in the list
     * @exception If the specified position in the list is out of bounds, an
     * exception is thrown.
     * @param index The index of the item
     * @return A reference to the specified item
     */
    const T& at( std::size_t index ) const;

    /*!
     * @brief Overload assignment operator
     */
    const SortedList<T>& operator=( const SortedList<T>& that );

    /*!
     * @brief Overload subscript operator
     * @note If _DEBUG is defined, this function calls @a at. If _DEBUG is not
     * defined, this function returns the data directly without bounds checking
     */
    T& operator[]( std::size_t index );

    /*!
     * @brief Overload const subscript operator
     * @note If _DEBUG is defined, this function calls @a at. If _DEBUG is not
     * defined, this function returns the data directly without bounds checking
     */
    const T& operator[]( std::size_t index ) const;

private:

    T*              m_Data;
    std::size_t     m_UsedSize;
    std::size_t     m_AllocatedSize;
};

} // namespace GOL

SortedList.cpp

// ----------------------------------------------------------------------------
// GOLSortedList.hxx
// ----------------------------------------------------------------------------

// ----------------------------------------------------------------------------
// include files

#include <GOLSortedList.hpp>

#include <Exception.hpp>
#include <sstream>
#include <algorithm>

namespace GOL {

// ----------------------------------------------------------------------------
template <class T>
SortedList<T>::SortedList() :
    m_Data(0),
    m_UsedSize(0),
    m_AllocatedSize(0)
{
}

// ----------------------------------------------------------------------------
template <class T>
SortedList<T>::SortedList( std::size_t preallocate ) :
    m_Data(0),
    m_UsedSize(0),
    m_AllocatedSize(0)
{
    m_Data = new T[preallocate];
    for( std::size_t n = 0; n != preallocate; ++n )
        m_Data[n] = T();
    m_UsedSize = preallocate;
    m_AllocatedSize = preallocate;
}

// ----------------------------------------------------------------------------
template <class T>
SortedList<T>::SortedList( const SortedList<T>& that ) :
    m_Data(0),
    m_UsedSize(0),
    m_AllocatedSize(0)
{
    *this = that;
}

// ----------------------------------------------------------------------------
template <class T>
SortedList<T>::~SortedList()
{
    if( m_Data )
        delete[] m_Data;
}

// ----------------------------------------------------------------------------
template <class T>
void SortedList<T>::insert( const T& item )
{

    // get insert position
    std::size_t insertPos = std::lower_bound( m_Data, m_Data+m_UsedSize, item ) - m_Data;
    if( insertPos != m_UsedSize )
        if( m_Data[insertPos] == item )
            return;

    // re-allocate if necessary
    if( m_UsedSize == m_AllocatedSize )
    {
        T* temp = new T[m_UsedSize+1];
        for( std::size_t n = 0; n != insertPos; ++n )
            temp[n] = m_Data[n];
        for( std::size_t n = insertPos; n != m_UsedSize; ++n )
            temp[n+1] = m_Data[n];
        if( m_Data )
            delete[] m_Data;
        m_Data = temp;
        m_Data[insertPos] = item;
        ++m_AllocatedSize;
        ++m_UsedSize;

    // insert item without re-allocating
    }else
    {
        ++m_UsedSize;
        for( std::size_t n = m_UsedSize; n > insertPos; --n )
            m_Data[n] = m_Data[n-1];
        m_Data[insertPos] = item;
    }
}

// ----------------------------------------------------------------------------
template <class T>
void SortedList<T>::erase( std::size_t pos )
{
    if( pos >= m_UsedSize )
    {
        std::stringstream ss; ss << "[SortedList::erase] Error: Index out of bounds: " << pos << ", actual list size: " << m_UsedSize;
        throw Exception( ss.str() );
    }

    // shift top part of list down, overwriting value to erase
    for( std::size_t n = pos+1; n != m_UsedSize; ++n )
        m_Data[n-1] = m_Data[n];
    if( m_UsedSize > 0 )
        --m_UsedSize;
}

// ----------------------------------------------------------------------------
template <class T>
void SortedList<T>::erase( SortedList<T>::iterator it )
{
    // shift top part of list down, overwriting value to erase
    for( iterator n = it+1; n != this->end(); ++n )
        *(n-1) = *n;
    if( m_UsedSize > 0 )
        --m_UsedSize;
}

// ----------------------------------------------------------------------------
template <class T>
typename SortedList<T>::iterator SortedList<T>::find( const T& item )
{
    iterator foundPos = std::lower_bound( m_Data, m_Data+m_UsedSize, item );
    if( foundPos == m_Data+m_UsedSize )
        return foundPos;
    if( *foundPos != item )
        foundPos = m_Data+m_UsedSize;
    return foundPos;
}

// ----------------------------------------------------------------------------
template <class T>
void SortedList<T>::clear()
{
    m_UsedSize = 0;
}

// ----------------------------------------------------------------------------
template <class T>
void SortedList<T>::resize( std::size_t size )
{
    T* temp = new T[size];
    if( m_UsedSize > size )
        m_UsedSize = size;
    for( std::size_t n = 0; n != m_UsedSize; ++n )
        temp[n] = m_Data[n];
    for( std::size_t n = m_UsedSize; n < size; ++n )
        temp[n] = T();
    if( m_Data )
        delete[] m_Data;
    m_Data = temp;
    m_AllocatedSize = size;
    m_UsedSize = size;
}

// ----------------------------------------------------------------------------
template <class T>
typename SortedList<T>::iterator SortedList<T>::begin()
{
    return m_Data;
}

// ----------------------------------------------------------------------------
template <class T>
typename SortedList<T>::const_iterator SortedList<T>::begin() const
{
    return m_Data;
}

// ----------------------------------------------------------------------------
template <class T>
typename SortedList<T>::iterator SortedList<T>::end()
{
    return (m_Data+m_UsedSize);
}

// ----------------------------------------------------------------------------
template <class T>
typename SortedList<T>::const_iterator SortedList<T>::end() const
{
    return (m_Data+m_UsedSize);
}

// ----------------------------------------------------------------------------
template <class T>
std::size_t SortedList<T>::size()
{
    return m_UsedSize;
}

// ----------------------------------------------------------------------------
template <class T>
std::size_t SortedList<T>::allocatedSize()
{
    return m_AllocatedSize;
}

// ----------------------------------------------------------------------------
template <class T>
T& SortedList<T>::at( std::size_t index )
{
    if( index >= m_UsedSize )
    {
        std::stringstream ss; ss << "[SortedList::operator[]] Error: Index out of bounds: " << index << ", actual list size: " << m_UsedSize;
        throw Exception( ss.str() );
    }
    return m_Data[index];
}

// ----------------------------------------------------------------------------
template <class T>
const T& SortedList<T>::at( std::size_t index ) const
{
    if( index >= m_UsedSize )
    {
        std::stringstream ss; ss << "[SortedList::operator[]] Error: Index out of bounds: " << index << ", actual list size: " << m_UsedSize;
        throw Exception( ss.str() );
    }
    return m_Data[index];
}

// ----------------------------------------------------------------------------
template <class T>
const SortedList<T>& SortedList<T>::operator=( const SortedList<T>& that )
{
    if( this == &that )
        return *this;

    // don't re-allocate if size of "this" is equal or greater than "that"
    // just copy data across
    if( m_AllocatedSize >= that.m_AllocatedSize )
    {
        for( std::size_t n = 0; n != that.m_UsedSize; ++n )
            m_Data[n] = that.m_Data[n];

    // re-allocate and copy data across
    }else
    {
        T* temp = new T[that.m_UsedSize];
        for( std::size_t n = 0; n != that.m_UsedSize; ++n )
            temp[n] = that.m_Data[n];
        if( m_Data )
            delete[] m_Data;
        m_Data = temp;
        m_AllocatedSize = that.m_UsedSize;
    }
    m_UsedSize = that.m_UsedSize;

    return *this;
}

// ----------------------------------------------------------------------------
template <class T>
T& SortedList<T>::operator[]( std::size_t index )
{
#ifdef _DEBUG
    return this->at(index);
#else
    return m_Data[index];
#endif
}

// ----------------------------------------------------------------------------
template <class T>
const T& SortedList<T>::operator[]( std::size_t index ) const
{
#ifdef _DEBUG
    return this->at(index);
#else
    return m_Data[index];
#endif
}

} // namespace GOL


YOUR_OPINION >/dev/null


Sponsor:

#2 Brother Bob   Moderators   -  Reputation: 7427

Like
0Likes
Like

Posted 11 January 2014 - 10:45 AM

Provide a test case that fails so we know where to start looking.



#3 TheComet   Members   -  Reputation: 1156

Like
0Likes
Like

Posted 11 January 2014 - 11:43 AM

I'm trying, believe me, but it's kind of at random.

 

At this point, I recommend cloning it from the repository and seeing for yourself until I have some code to go with.

 

dependencies: googletest

tools: premake

The following will reproduce the crash:

$ git clone https://www.github.com/TheComet93/game-of-life.git
$ cd game-of-life
$ git checkout topic
$ premake gmake
$ cd build
$ make gol Tests
$ ./../bin/debug/Tests

Thank you very much for your time.

 

EDIT: If you're on windows, use "premake MinGW" instead of premake "gmake". The rest would be identical, if you're using CYGWin.


Edited by TheComet, 11 January 2014 - 11:44 AM.

YOUR_OPINION >/dev/null


#4 L. Spiro   Crossbones+   -  Reputation: 9852

Like
2Likes
Like

Posted 11 January 2014 - 01:48 PM

The fact that you use new and delete instead of placement new and manual destruction is something of a worry to me.

 

You aren’t manually enforcing that an object’s destructor is called exactly the same times as its constructor.

 

Without going over the code in excruciating detail, it may end up coincidentally that you do have a proper pairing of constructors and destructors and this may not be a problem (though it certainly is a performance issue), but there are 3 test cases you can create to test this.

 

 

Make a loop that runs for 10 minutes or so and inserts, erases—whatever else you want to test—random:

#1: PoD types such as integers.

#2: Basic classes that keep track of the number of times they are constructed and destructed.

#3: Complex classes that perform allocations and deletions as they are created and destroyed, as well as a memory fill on the allocated data and on a local array.

 

If it crashes on #1 then your implementation is simply flawed, but not necessarily by a pairing of constructors and destructors.  You can print the last operation performed (insert, erase, whatever) to see which method to study.  In fact you can add debug prints right now and run your application as it is and see what was the last thing to be called before death.

 

#2 allows you to verify the pairing of constructors and destructors.  If this does not work, don’t bother with #3.  Rewrite the whole thing using placement new and manual destructors.  Actually, why bother testing?  Just do it.

 

If #3 fails it is because #2 failed.  Objects are not being constructed and destructed consistently and they themselves are causing the stack corruption as a result.  Again, placement new and manual destruction, and enforce consistency.

 

 

L. Spiro


It is amazing how often people try to be unique, and yet they are always trying to make others be like them. - L. Spiro 2011
I spent most of my life learning the courage it takes to go out and get what I want. Now that I have it, I am not sure exactly what it is that I want. - L. Spiro 2013
I went to my local Subway once to find some guy yelling at the staff. When someone finally came to take my order and asked, “May I help you?”, I replied, “Yeah, I’ll have one asshole to go.”
L. Spiro Engine: http://lspiroengine.com
L. Spiro Engine Forums: http://lspiroengine.com/forums

#5 TheComet   Members   -  Reputation: 1156

Like
0Likes
Like

Posted 13 January 2014 - 06:01 AM

I tried what you said, but I still can't accurately reproduce the problem.

 

I have a few questions regarding placement new. Could someone answer questions #1 through #3 in this code?

#include <new>
#include <iostream>

class Foo
{
public:
    Foo() { std::cout << "constructed [" << this << "]" << std::endl; }
    ~Foo() { std::cout << "destructed [" << this << "]" << std::endl; }
};

template <class T>
void destroy( void* buf, T* obj, std::size_t size )
{
    for( std::size_t n = 0; n != size; ++n )
        (obj+n)->~T();
}

int main()
{
    void* buf = ::operator new (sizeof(Foo)*2); // #1 Does this allocate memory to
                                                      // fit 2 instantiations of the class Foo
                                                      // and is this correct?

    Foo* a = new(buf) Foo[2];
    destroy( buf, a, 2 );

    a = new(buf) Foo[3]; // #2 what happens now? The buffer is only size 2.
    destroy( buf, a, 3 );

    delete buf; // #3 Is this correct and safe?
                // deleting void* is undefined, isn't it?

    return 0;
}

Edited by TheComet, 13 January 2014 - 06:02 AM.

YOUR_OPINION >/dev/null


#6 Brother Bob   Moderators   -  Reputation: 7427

Like
1Likes
Like

Posted 13 January 2014 - 06:21 AM

I tried what you said, but I still can't accurately reproduce the problem.
 
I have a few questions regarding placement new. Could someone answer questions #1 through #3 in this code?

int main()
{
    void* buf = ::operator new (sizeof(Foo)*2); // #1 Does this allocate memory to
                                                      // fit 2 instantiations of the class Foo
                                                      // and is this correct?

    Foo* a = new(buf) Foo[2];
    destroy( buf, a, 2 );

 
Don't use array placement new, you should use scalar placement new on each element by itself. In short, the array placement new, like normal array new, needs additional space for internal book-keeping information. You can easily check that this is happening by comparing the values of buf and a, and since you don't allocate space for this book-kepping, you are constructing objects outside the allocated space.
 
Instead, use a for-loop and call scalar placement new on the objects manually. The extra information you need to allocate is implementation defined and there's no standard way to get this information.
 

    a = new(buf) Foo[3]; // #2 what happens now? The buffer is only size 2.
    destroy( buf, a, 3 );

Placement new:ing more elements than allocated memory is just like stomping past any other array; undefined.

 

    delete buf; // #3 Is this correct and safe?
                // deleting void* is undefined, isn't it?

    return 0;
}

Calling delete on a buffer that wasn't allocated with new is undefined. You allocated the memory with ::operator new(), so you have to release it with ::operator delete(). Don't confuse the new operator with ::operator new; the former is an operator that does two things; allocates memory and constructs objects, while the latter is the actual function that the new operator calls to allocate the memory.



#7 TheComet   Members   -  Reputation: 1156

Like
0Likes
Like

Posted 13 January 2014 - 09:46 AM

Thanks for the reply! This is some cool stuff I didn't know about until now. :)


YOUR_OPINION >/dev/null


#8 TheComet   Members   -  Reputation: 1156

Like
0Likes
Like

Posted 14 January 2014 - 03:38 AM


Don't use array placement new, you should use scalar placement new on each element by itself.

This doesn't seem to work for me. See the following code:

#include <iostream>
#include <new>

class Foo
{
public:
    Foo() { std::cout << "constructed " << this << std::endl; }
    ~Foo() { std::cout << "destructed " << this << std::endl; }
};

template <class T>
void destroy( T* obj )
{
    obj->~T();
}

int main()
{

    Foo* buf = (Foo*) ::operator new(sizeof(Foo)*2);

    Foo* a = new (buf) Foo();
    Foo* b = new (buf) Foo();

    destroy(a);
    destroy(b);

    ::operator delete( buf );

    return 0;

}

This is the output I gayt:

constructed 0x382fd8
constructed 0x382fd8
destructed 0x382fd8
destructed 0x382fd8

Process returned 0 (0x0) 

It's allocating the second object at the first address of the first object.

 

Do I need to do my own book keeping? I.e.

Foo* a = new (buf+0) Foo();
Foo* b = new (buf+1) Foo();

Edited by TheComet, 14 January 2014 - 03:53 AM.

YOUR_OPINION >/dev/null


#9 BitMaster   Crossbones+   -  Reputation: 3056

Like
0Likes
Like

Posted 14 January 2014 - 03:41 AM

Instead of
Foo* a = new (buf) Foo();
Foo* b = new (buf) Foo();
you obviously need to do
Foo* a = new (buf    ) Foo();
Foo* b = new (buf + 1) Foo();


#10 TheComet   Members   -  Reputation: 1156

Like
0Likes
Like

Posted 14 January 2014 - 04:03 AM

Ah, obvious. dry.png Thanks!


YOUR_OPINION >/dev/null





Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS