DS_List.h

Go to the documentation of this file.

#ifndef __LIST_H
#define __LIST_H 

#include "RakAssert.h"
#include <string.h> // memmove
#include "Export.h"
#include "RakMemoryOverride.h"

static const unsigned int MAX_UNSIGNED_LONG = 4294967295U;

namespace DataStructures
{
    template <class list_type>
    class RAK_DLL_EXPORT List
    {   
    public:
        List();

        // Destructor
        ~List();
        
        List( const List& original_copy );
        
        List& operator= ( const List& original_copy );
        
        list_type& operator[] ( const unsigned int position ) const;

        list_type& Get ( const unsigned int position ) const;

        void Push(const list_type &input, const char *file, unsigned int line );

        list_type& Pop(void);
        
        void Insert( const list_type &input, const unsigned int position, const char *file, unsigned int line );
        
        void Insert( const list_type &input, const char *file, unsigned int line );
        
        void Replace( const list_type &input, const list_type filler, const unsigned int position, const char *file, unsigned int line );
        
        void Replace( const list_type &input );
        
        void RemoveAtIndex( const unsigned int position );

        void RemoveAtIndexFast( const unsigned int position );
        
        void RemoveFromEnd(const unsigned num=1);
        
        unsigned int GetIndexOf( const list_type &input ) const;
        
        unsigned int Size( void ) const;
        
        void Clear( bool doNotDeallocateSmallBlocks, const char *file, unsigned int line );
        
        void Preallocate( unsigned countNeeded, const char *file, unsigned int line );

        void Compress( const char *file, unsigned int line );
        
    private:
        list_type* listArray;
        
        unsigned int list_size;
        
        unsigned int allocation_size;
    };
    template <class list_type>
        List<list_type>::List()
    {
        allocation_size = 0;
        listArray = 0;
        list_size = 0;
    }

    template <class list_type>
        List<list_type>::~List()
    {
        if (allocation_size>0)
            RakNet::OP_DELETE_ARRAY(listArray, _FILE_AND_LINE_);
    }


    template <class list_type>
        List<list_type>::List( const List& original_copy )
    {
        // Allocate memory for copy

        if ( original_copy.list_size == 0 )
        {
            list_size = 0;
            allocation_size = 0;
        }
        else
        {
            listArray = RakNet::OP_NEW_ARRAY<list_type >( original_copy.list_size , _FILE_AND_LINE_ );

            for ( unsigned int counter = 0; counter < original_copy.list_size; ++counter )
                listArray[ counter ] = original_copy.listArray[ counter ];

            // Don't call constructors, assignment operators, etc.
            //memcpy(listArray, original_copy.listArray, original_copy.list_size*sizeof(list_type));

            list_size = allocation_size = original_copy.list_size;
        }
    }

    template <class list_type>
        List<list_type>& List<list_type>::operator= ( const List& original_copy )
    {
        if ( ( &original_copy ) != this )
        {
            Clear( false, _FILE_AND_LINE_ );

            // Allocate memory for copy

            if ( original_copy.list_size == 0 )
            {
                list_size = 0;
                allocation_size = 0;
            }

            else
            {
                listArray = RakNet::OP_NEW_ARRAY<list_type >( original_copy.list_size , _FILE_AND_LINE_ );

                for ( unsigned int counter = 0; counter < original_copy.list_size; ++counter )
                    listArray[ counter ] = original_copy.listArray[ counter ];
                // Don't call constructors, assignment operators, etc.
                //memcpy(listArray, original_copy.listArray, original_copy.list_size*sizeof(list_type));

                list_size = allocation_size = original_copy.list_size;
            }
        }

        return *this;
    }


        template <class list_type>
            inline list_type& List<list_type>::operator[] ( const unsigned int position ) const
        {
        #ifdef _DEBUG
            if (position>=list_size)
            {
                RakAssert ( position < list_size );
            }
        #endif
            return listArray[ position ];
        }

        // Just here for debugging
        template <class list_type>
        inline list_type& List<list_type>::Get ( const unsigned int position ) const
        {
            return listArray[ position ];
        }

        template <class list_type>
        void List<list_type>::Push(const list_type &input, const char *file, unsigned int line)
        {
            Insert(input, file, line);
        }

        template <class list_type>
        inline list_type& List<list_type>::Pop(void)
        {
#ifdef _DEBUG
            RakAssert(list_size>0);
#endif
            --list_size;
            return listArray[list_size];
        }

    template <class list_type>
    void List<list_type>::Insert( const list_type &input, const unsigned int position, const char *file, unsigned int line )
    {
#ifdef _DEBUG
        if (position>list_size)
        {
            RakAssert( position <= list_size );
        }
#endif

        // Reallocate list if necessary
        if ( list_size == allocation_size )
        {
            // allocate twice the currently allocated memory
            list_type * new_array;

            if ( allocation_size == 0 )
                allocation_size = 16;
            else
                allocation_size *= 2;

            new_array = RakNet::OP_NEW_ARRAY<list_type >( allocation_size , file, line );

            // copy old array over
            for ( unsigned int counter = 0; counter < list_size; ++counter )
                new_array[ counter ] = listArray[ counter ];

            // Don't call constructors, assignment operators, etc.
            //memcpy(new_array, listArray, list_size*sizeof(list_type));

            // set old array to point to the newly allocated and twice as large array
            RakNet::OP_DELETE_ARRAY(listArray, file, line);

            listArray = new_array;
        }

        // Move the elements in the list to make room
        for ( unsigned int counter = list_size; counter != position; counter-- )
            listArray[ counter ] = listArray[ counter - 1 ];

        // Don't call constructors, assignment operators, etc.
        //memmove(listArray+position+1, listArray+position, (list_size-position)*sizeof(list_type));

        // Insert the new item at the correct spot
        listArray[ position ] = input;

        ++list_size;

    }


    template <class list_type>
    void List<list_type>::Insert( const list_type &input, const char *file, unsigned int line )
    {
        // Reallocate list if necessary

        if ( list_size == allocation_size )
        {
            // allocate twice the currently allocated memory
            list_type * new_array;

            if ( allocation_size == 0 )
                allocation_size = 16;
            else
                allocation_size *= 2;

            new_array = RakNet::OP_NEW_ARRAY<list_type >( allocation_size , file, line );

            if (listArray)
            {
                // copy old array over
                    for ( unsigned int counter = 0; counter < list_size; ++counter )
                        new_array[ counter ] = listArray[ counter ];

                // Don't call constructors, assignment operators, etc.
                //memcpy(new_array, listArray, list_size*sizeof(list_type));

                // set old array to point to the newly allocated and twice as large array
                RakNet::OP_DELETE_ARRAY(listArray, file, line);
            }
            
            listArray = new_array;
        }

        // Insert the new item at the correct spot
        listArray[ list_size ] = input;

        ++list_size;
    }

    template <class list_type>
        inline void List<list_type>::Replace( const list_type &input, const list_type filler, const unsigned int position, const char *file, unsigned int line )
    {
        if ( ( list_size > 0 ) && ( position < list_size ) )
        {
            // Direct replacement
            listArray[ position ] = input;
        }
        else
        {
            if ( position >= allocation_size )
            {
                // Reallocate the list to size position and fill in blanks with filler
                list_type * new_array;
                allocation_size = position + 1;

                new_array = RakNet::OP_NEW_ARRAY<list_type >( allocation_size , file, line );

                // copy old array over

                for ( unsigned int counter = 0; counter < list_size; ++counter )
                    new_array[ counter ] = listArray[ counter ];

                // Don't call constructors, assignment operators, etc.
                //memcpy(new_array, listArray, list_size*sizeof(list_type));

                // set old array to point to the newly allocated array
                RakNet::OP_DELETE_ARRAY(listArray, file, line);

                listArray = new_array;
            }

            // Fill in holes with filler
            while ( list_size < position )
                listArray[ list_size++ ] = filler;

            // Fill in the last element with the new item
            listArray[ list_size++ ] = input;

#ifdef _DEBUG

            RakAssert( list_size == position + 1 );

#endif

        }
    }

    template <class list_type>
        inline void List<list_type>::Replace( const list_type &input )
    {
        if ( list_size > 0 )
            listArray[ list_size - 1 ] = input;
    }

    template <class list_type>
        void List<list_type>::RemoveAtIndex( const unsigned int position )
    {
#ifdef _DEBUG
        if (position >= list_size)
        {
            RakAssert( position < list_size );
            return;
        }
#endif

        if ( position < list_size )
        {
            // Compress the array
            for ( unsigned int counter = position; counter < list_size - 1 ; ++counter )
            listArray[ counter ] = listArray[ counter + 1 ];
            // Don't call constructors, assignment operators, etc.
            // memmove(listArray+position, listArray+position+1, (list_size-1-position) * sizeof(list_type));

            RemoveFromEnd();
        }
    }

    template <class list_type>
        void List<list_type>::RemoveAtIndexFast( const unsigned int position )
        {
#ifdef _DEBUG
            if (position >= list_size)
            {
                RakAssert( position < list_size );
                return;
            }
#endif
            --list_size;
            listArray[position]=listArray[list_size];
        }

    template <class list_type>
        inline void List<list_type>::RemoveFromEnd( const unsigned num )
    {
        // Delete the last elements on the list.  No compression needed
#ifdef _DEBUG
        RakAssert(list_size>=num);
#endif
        list_size-=num;
    }

    template <class list_type>
        unsigned int List<list_type>::GetIndexOf( const list_type &input ) const
    {
        for ( unsigned int i = 0; i < list_size; ++i )
            if ( listArray[ i ] == input )
                return i;

        return MAX_UNSIGNED_LONG;
    }

    template <class list_type>
        inline unsigned int List<list_type>::Size( void ) const
    {
        return list_size;
    }

    template <class list_type>
    void List<list_type>::Clear( bool doNotDeallocateSmallBlocks, const char *file, unsigned int line )
    {
        if ( allocation_size == 0 )
            return;

        if (allocation_size>512 || doNotDeallocateSmallBlocks==false)
        {
            RakNet::OP_DELETE_ARRAY(listArray, file, line);
            allocation_size = 0;
            listArray = 0;
        }
        list_size = 0;
    }

    template <class list_type>
    void List<list_type>::Compress( const char *file, unsigned int line )
    {
        list_type * new_array;

        if ( allocation_size == 0 )
            return ;

        new_array = RakNet::OP_NEW_ARRAY<list_type >( allocation_size , file, line );

        // copy old array over
        for ( unsigned int counter = 0; counter < list_size; ++counter )
            new_array[ counter ] = listArray[ counter ];

        // Don't call constructors, assignment operators, etc.
        //memcpy(new_array, listArray, list_size*sizeof(list_type));

        // set old array to point to the newly allocated array
        RakNet::OP_DELETE_ARRAY(listArray, file, line);

        listArray = new_array;
    }

    template <class list_type>
    void List<list_type>::Preallocate( unsigned countNeeded, const char *file, unsigned int line )
    {
        unsigned amountToAllocate = allocation_size;
        if (allocation_size==0)
            amountToAllocate=16;
        while (amountToAllocate < countNeeded)
            amountToAllocate<<=1;

        if ( allocation_size < amountToAllocate)
        {
            // allocate twice the currently allocated memory
            list_type * new_array;

            allocation_size=amountToAllocate;

            new_array = RakNet::OP_NEW_ARRAY< list_type >( allocation_size , file, line );

            if (listArray)
            {
                // copy old array over
                for ( unsigned int counter = 0; counter < list_size; ++counter )
                    new_array[ counter ] = listArray[ counter ];

                // Don't call constructors, assignment operators, etc.
                //memcpy(new_array, listArray, list_size*sizeof(list_type));

                // set old array to point to the newly allocated and twice as large array
                RakNet::OP_DELETE_ARRAY(listArray, file, line);
            }

            listArray = new_array;
        }
    }
    
} // End namespace

#endif