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__, __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__, __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__, __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__, __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