F:/My Projects/LSEngine/Modules/LSMemLib/Src/Allocators/LSAStdAllocatorHeap.h

#ifndef __LSA_STDALLOCATORHEAP_H__
#define __LSA_STDALLOCATORHEAP_H__

#include "../OSHeap/LSAOsHeap.h"
#if defined( LSA_USE_FLOAT_OPTIMIZATIONS )
#include <cmath>
#endif  // #ifdef LSA_USE_FLOAT_OPTIMIZATIONS


namespace lsa {

        class CStdAllocatorHeap {
                // Only the CStdAllocator class can create this object.
                friend class                                                                    CStdAllocator;

        public :
                // == Functions.
                LSVOID * LSE_CALL                                                               Alloc( LSA_SIZE _sSize, LSUINT32 _ui32Align = LSA_MIN_ALIGN                                             LSA_DEBUGPARMSDECL );

                LSBOOL LSE_CALL                                                                 Free( LSVOID * _pvAddr );

                LSBOOL LSE_CALL                                                                 IsEmpty( LSBOOL _bReport ) const;

                LSVOID LSE_CALL                                                                 Trash();

                LSA_SIZE LSE_CALL                                                               PrintAllocations( LSUINT32 _ui32Count = 0UL, LSUINT32 _ui32End = 0xFFFFFFFFUL ) const;

                LSE_INLINE LSA_SIZE LSE_CALL                                    GetHeapSize() const;

                static LSUINT32 LSE_CALL                                                GetAllocationCounter();


        protected :
                // == Various constructors.
                LSE_INLINE LSE_CALL                                                             CStdAllocatorHeap();

        protected :
                // == Types.
#pragma pack( push, 1 )
                typedef struct LSA_FREEHEADER {
                        LSA_FREEHEADER *                                                        pfhNextFree;

                        LSA_FREEHEADER *                                                        pfhPrevFree;

                        LSA_FREEHEADER *                                                        pfhNextInHash;

                        LSA_SIZE                                                                        sActualSize;
                } * LPLSA_FREEHEADER, * const LPCLSA_FREEHEADER;
#pragma pack( pop )

#pragma pack( push, 1 )
                typedef struct LSA_ALLOCATIONHEADER {
                        LPLSA_FREEHEADER                                                        pfhPrevFree;
                        
                        LSA_ALLOCATIONHEADER *                                          pahNext;
                        
                        LSA_ALLOCATIONHEADER *                                          pahNextInHash;
                        
                        LSUINT32                                                                        ui32Size                : 31;
                        
                        LSUINT32                                                                        ui32Alignment   : 1;

                        // Debug information, if any.
#ifdef LSA_DEBUG

                        LSUINT32                                                                        ui32Line;
                        
                        const LSCHAR *                                                          pcFile;
                        
                        LSUINT32                                                                        ui32Number;
#endif  // #ifdef LSA_DEBUG
                } * LPLSA_ALLOCATIONHEADER, * const LPCLSA_ALLOCATIONHEADER;
#pragma pack( pop )


        protected :
                // == Functions.
                LSE_INLINE LSVOID LSE_CALL                                              Set( LSVOID * _pvHeap, LSA_SIZE _sSizeOfHeap );

                LSVOID * LSE_CALL                                                               ReAlloc( LPLSA_ALLOCATIONHEADER &_lpahHeader, LSVOID * _pvAddr, LSA_SIZE _sSize LSA_DEBUGPARMSDECL );

                // Given the address of a block, get the address returned to the user.
                LSE_INLINE static LSVOID * LSE_CALL                             GetStartAddress( const LPLSA_ALLOCATIONHEADER _lpahHeader );

                // Get the actual size of a block given the requested size, alignment, and start address.
                LSE_INLINE static LSA_SIZE LSE_CALL                             GetActualSizeOfBlock( LSVOID * _pvAddr, LSA_SIZE _sSize, LSUINT32 _ui32Align );

                // Get the size of an allocated block.
                LSE_INLINE static LSA_SIZE LSE_CALL                             GetSize( const LPLSA_ALLOCATIONHEADER _lpahHeader );

                // Given an address returned to the user, generate a hash key.
                LSE_INLINE LSUINT32 LSE_CALL                                    GetHashKey( LSVOID * _pvAddr ) const;

                // Given a size, generate a hash key.
                LSE_INLINE static LSUINT32 LSE_CALL                             GetHashKey( LSA_SIZE _sSize );

                // Round up to the nearest alignment.
                LSE_INLINE static LSA_SIZE LSE_CALL                             RoundUp( LSA_SIZE _sSize );

                // Create a size key for allocation blocks.
                LSE_INLINE static LSUINT32 LSE_CALL                             CreateSizeKey( LSA_SIZE _sSize );

                // Get the alignment in decimal form given an alignment key.
                LSE_INLINE static LSUINT32 LSE_CALL                             GetAlignment( LSUINT32 _ui32Key );

                // Get the allocation block previous to the given block, or NULL if there is none.
                LPLSA_ALLOCATIONHEADER LSE_CALL                                 GetPrevAlloc( LPLSA_ALLOCATIONHEADER _pahFrom ) const;

                // Add an allocation.  Does not remove free blocks or cut anything.  Assumes the address at _pvAddr
                //      is ready to go.
                LSVOID * LSE_CALL                                                               AddAllocInternal( LPLSA_FREEHEADER _lpfhPrevFree,
                        LPLSA_ALLOCATIONHEADER _lpahNextAllocated,
                        LSVOID * _pvAddr, LSA_SIZE _sSize, LSUINT32 _ui32Align
                        LSA_DEBUGPARMSDECL );

                // Add an allocation at the given address.  The given address is assumed to be the header of a free
                //      block which must be adjusted or removed to make room for the allocation block.  Performs all
                //      necessary operations for adding the allocation block.
                LSVOID * LSE_CALL                                                               AddAlloc( LPLSA_ALLOCATIONHEADER _lpahNextAllocated,
                        LSVOID * _pvAddr, LSA_SIZE _sSize, LSUINT32 _ui32Align
                        LSA_DEBUGPARMSDECL );

                // Remove an allocation.  Does all merging and fixing, leaving in a stable state.
                LSVOID LSE_CALL                                                                 RemAlloc( LPLSA_ALLOCATIONHEADER _lpahAllocated );

                // Add a free-store block without merging or fixing-up.
                LSVOID LSE_CALL                                                                 AddFreeBlockInternal( LPLSA_FREEHEADER _lpfhAfterMe, LPLSA_FREEHEADER _lpfhBeforeMe,
                        LSVOID * _pvAddr, LSA_SIZE _sSize );

                // Remove a free-store block.  Does not chop, merge, or fix-up.
                LSVOID LSE_CALL                                                                 RemFreeBlockInternal( LPLSA_FREEHEADER _lpfhRemoveMe );

                // Add a free-store block.  Performs merging and fixing.
                LSVOID LSE_CALL                                                                 AddFreeBlock( LPLSA_FREEHEADER _lpfhAfterMe, LPLSA_FREEHEADER _lpfhBeforeMe,
                        LSVOID * _pvAddr, LSA_SIZE _sSize );

                // Merge connected free-store blocks.
                LSBOOL LSE_CALL                                                                 MergeFreeStoreBlocks( LPLSA_FREEHEADER _lpfhFirst );

                // Get the head of the allocation list.
                LSE_INLINE LPLSA_ALLOCATIONHEADER LSE_CALL              GetAllocationHead() const;

                // Get the next allocated block after a free block or NULL if there are none.
                LSE_INLINE LPLSA_ALLOCATIONHEADER LSE_CALL              GetNextAllocatedBlock( LPLSA_FREEHEADER _lpAfterMe ) const;

                // Get the next free block after the given allocated block, or NULL for none.
                LSE_INLINE LPLSA_FREEHEADER LSE_CALL                    GetNextFreeBlock( LPLSA_ALLOCATIONHEADER _lpahAfterMe );

                // Fix up the free pointers on allocated blocks following a free block.
                LSE_INLINE LSVOID LSE_CALL                                              FixUpAllocationFreeBlockPointers( LPLSA_FREEHEADER _lpfhAfterMe );

                // In a linked-list of allocated blocks, replace each elementís previous free pointer with the one given
                //      if it matches the provided original free-block pointer.  Stops scanning at the first block that does
                //      not match the given key.
                LSE_INLINE LSVOID LSE_CALL                                              ReplaceAllocationFreeBlockPointers( LPLSA_ALLOCATIONHEADER _lpahStart, LPLSA_FREEHEADER _lpfhReplaceMe, LPLSA_FREEHEADER _lpfhWithMe );

                // Find a free-store block large enough for a given allocation size and alignment.
                LPLSA_FREEHEADER LSE_CALL                                               FindFreeStoreBlock( LSA_SIZE _sSize, LSUINT32 _ui32Align );

                // Find an allocated block given its address.
                LSE_INLINE LPLSA_ALLOCATIONHEADER LSE_CALL              FindAllocationBlock( LSVOID * _pvAddr );

                // Additional debug functions.
#ifdef LSA_DEBUG
                // Print free blocks.
                LSVOID LSE_CALL                                                                 PrintFreeBlocks() const;

                // Verify free blocks.
                LSVOID LSE_CALL                                                                 VerifyFreeBlocks() const;

                // Verify allocated blocks.
                LSVOID LSE_CALL                                                                 VerifyAllocatedBlocks() const;

                static LSVOID LSE_CALL                                                  PrintAllocation( const LPLSA_ALLOCATIONHEADER _lpahHeader );
#endif  // #ifdef LSA_DEBUG

                // == Members.
                LSVOID *                                                                                m_pvHeap;
                
                LSA_SIZE                                                                                m_sSize;

                CStdAllocatorHeap *                                                             m_psahNext;

                LPLSA_ALLOCATIONHEADER                                                  m_lpahAllocatedBlocks[LSA_BUCKETS];

                LPLSA_FREEHEADER                                                                m_lpfhFreeBlocks[LSA_BUCKETS];

                LPLSA_FREEHEADER                                                                m_lpfhFreeHead;

                LSUINT16                                                                                m_usLowestFreeBlockInHashTable;

#ifdef LSA_USE_FLOAT_OPTIMIZATIONS

                LSDOUBLE                                                                                m_dInvSize;
#endif  // #ifdef LSA_USE_FLOAT_OPTIMIZATIONS

#ifdef LSA_DEBUG

                static LSUINT32                                                                 m_ui32AllocCount;
#endif  // #ifdef LSA_DEBUG

#ifdef LSA_USE_FLOAT_OPTIMIZATIONS

                static LSBOOL                                                                   m_bMadeTable;

                static LSDOUBLE                                                                 m_dSinTable[0x10000];
#endif  // #ifdef LSA_USE_FLOAT_OPTIMIZATIONS
        };


        // * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
        // DEFINITIONS
        // * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
        // == Various constructors.
        LSE_INLINE LSE_CALL CStdAllocatorHeap::CStdAllocatorHeap() :
#ifdef LSA_USE_FLOAT_OPTIMIZATIONS
                m_dInvSize( 0.0 ),
#endif  // #ifdef LSA_USE_FLOAT_OPTIMIZATIONS
                m_sSize( 0 ),
                m_pvHeap( NULL ),
                //m_lpahAllocatedHead( NULL ),
                m_lpfhFreeHead( NULL ),
                m_psahNext( NULL ),
                m_usLowestFreeBlockInHashTable( LSA_BUCKETS - 1 ) {
                for ( LSUINT32 I = 0; I < LSA_BUCKETS; ++I ) {
                        m_lpahAllocatedBlocks[I] = NULL;
                        m_lpfhFreeBlocks[I] = NULL;
                }
#ifdef LSA_USE_FLOAT_OPTIMIZATIONS
                if ( !m_bMadeTable ) {
                        for ( LSINT32 I = 0x10000; --I >= 0; ) {
                                m_dSinTable[I] = ::sin( (2.0 * 3.1415926535897932384626433832795 / 0x10000) * I );
                        }
                        m_bMadeTable = true;
                }
#endif  // #ifdef LSA_USE_FLOAT_OPTIMIZATIONS
        }

        // == Functions.
        LSE_INLINE LSA_SIZE LSE_CALL CStdAllocatorHeap::GetHeapSize() const {
                return m_sSize;
        }

        LSE_INLINE LSVOID LSE_CALL CStdAllocatorHeap::Set( LSVOID * _pvHeap, LSA_SIZE _sSizeOfHeap ) {
                m_pvHeap = _pvHeap;
                m_sSize = _sSizeOfHeap;
#ifdef LSA_USE_FLOAT_OPTIMIZATIONS
                m_dInvSize = 1.0 / m_sSize;
#endif  // #ifdef LSA_USE_FLOAT_OPTIMIZATIONS
                //m_lpahAllocatedHead = NULL;
                m_lpfhFreeHead = NULL;
                m_psahNext = NULL;
                for ( LSUINT32 I = 0; I < LSA_BUCKETS; ++I ) {
                        m_lpahAllocatedBlocks[I] = NULL;
                        m_lpfhFreeBlocks[I] = NULL;
                }

                m_usLowestFreeBlockInHashTable = LSA_BUCKETS - 1;

                // Add the whole block to the free store.
                AddFreeBlock( NULL, NULL, m_pvHeap, m_sSize );
        }

        // Given the address of a block, get the address returned to the user.
        LSE_INLINE LSVOID * CStdAllocatorHeap::GetStartAddress( const LPLSA_ALLOCATIONHEADER _lpahHeader ) {
                LSA_SIZE sStart = reinterpret_cast<LSA_SIZE>(_lpahHeader);

                // Skip the header.
                sStart += sizeof( LSA_ALLOCATIONHEADER );
                // From here, round up based on the alignment.
                LSUINT32 ui32Align = LSA_MIN_ALIGN + LSA_MIN_ALIGN * _lpahHeader->ui32Alignment;
                return reinterpret_cast<LSVOID *>(LSE_ROUND_UP( sStart, ui32Align ));
        }

        // Get the actual size of a block given the requested size, alignment, and start address.
        LSE_INLINE LSA_SIZE LSE_CALL CStdAllocatorHeap::GetActualSizeOfBlock( LSVOID * _pvAddr, LSA_SIZE _sSize, LSUINT32 _ui32Align ) {
                LSA_SIZE sStart = reinterpret_cast<LSA_SIZE>(_pvAddr);
                LSA_SIZE sOriginal = sStart;
                // Skip the header.
                sStart += sizeof( LSA_ALLOCATIONHEADER );
                // From here, round up based on the alignment.
                LSUINT32 ui32Align = LSA_MIN_ALIGN + LSA_MIN_ALIGN * _ui32Align;

                sStart = LSE_ROUND_UP( sStart, ui32Align );

                // Now add the requested allocation length.
                sStart += _sSize;

                sStart = LSE_ROUND_UP( sStart, LSA_MIN_ALIGN );

                return sStart - sOriginal;
        }

        // Get the size of an allocated block.
        LSE_INLINE LSA_SIZE CStdAllocatorHeap::GetSize( const LPLSA_ALLOCATIONHEADER _lpahHeader ) {
                return _lpahHeader->ui32Size * LSA_MIN_ALIGN;
        }

        // Given an address returned to the user, generate a hash key.
        LSE_INLINE LSUINT32 CStdAllocatorHeap::GetHashKey( LSVOID * _pvAddr ) const {
                LSA_SUPERSIZE sStart = reinterpret_cast<LSA_SIZE>(_pvAddr);
                LSA_SUPERSIZE sBase = reinterpret_cast<LSA_SIZE>(m_pvHeap);
                sStart -= sBase;
#ifdef LSA_USE_FLOAT_OPTIMIZATIONS
                LSDOUBLE dFrac = sStart * m_dInvSize;
                dFrac *= static_cast<LSDOUBLE>(1.5707963267948966192313216916398);
                return static_cast<LSUINT32>(m_dSinTable[static_cast<LSUINT16>(1.0/(3.1415926535897932384626433832795*2.0)*0x10000*dFrac)] * (LSA_BUCKETS - 1));
#else   // #ifdef LSA_USE_FLOAT_OPTIMIZATIONS
                sStart = sStart * LSA_BUCKETS / m_sSize;
                return static_cast<LSUINT32>(sStart);
#endif  // #ifdef LSA_USE_FLOAT_OPTIMIZATIONS
        }

        // Given a size, generate a hash key.
        LSE_INLINE LSUINT32 CStdAllocatorHeap::GetHashKey( LSA_SIZE _sSize ) {
                _sSize >>= 12;
                if ( _sSize < LSA_BUCKETS ) { return static_cast<LSUINT32>(_sSize); }
                return LSA_BUCKETS - 1;
        }

        // Round up to the nearest alignment.
        LSE_INLINE LSA_SIZE LSE_CALL CStdAllocatorHeap::RoundUp( LSA_SIZE _sSize ) {
                LSA_SIZE sThis = _sSize >> LSA_MIN_ALIGN_BITS;
                if ( (_sSize & (LSA_MIN_ALIGN - 1)) ) {
                        return (sThis + 1) << LSA_MIN_ALIGN_BITS;
                }
                return sThis << LSA_MIN_ALIGN_BITS;
        }

        // Create a size key for allocation blocks.
        LSE_INLINE LSUINT32 LSE_CALL CStdAllocatorHeap::CreateSizeKey( LSA_SIZE _sSize ) {
                LSA_SIZE sThis = _sSize >> LSA_MIN_ALIGN_BITS;
                if ( (_sSize & (LSA_MIN_ALIGN - 1)) ) {
                        return static_cast<LSUINT32>(sThis + 1);
                }
                return static_cast<LSUINT32>(sThis);
                //return static_cast<LSUINT32>(RoundUp( _sSize ) >> LSA_MIN_ALIGN_BITS);
        }

        // Get the alignment in decimal form given an alignment key.
        LSE_INLINE LSUINT32 LSE_CALL CStdAllocatorHeap::GetAlignment( LSUINT32 _ui32Key ) {
                return LSA_MIN_ALIGN + LSA_MIN_ALIGN * _ui32Key;
        }

        // Get the head of the allocation list.
        LSE_INLINE CStdAllocatorHeap::LPLSA_ALLOCATIONHEADER LSE_CALL CStdAllocatorHeap::GetAllocationHead() const {
                if ( m_lpfhFreeHead == m_pvHeap ) {
                        return GetNextAllocatedBlock( m_lpfhFreeHead );
                }
                return static_cast<LPLSA_ALLOCATIONHEADER>(m_pvHeap);
        }

        // Get the next allocated block after a free block or NULL if there are none.
        LSE_INLINE CStdAllocatorHeap::LPLSA_ALLOCATIONHEADER LSE_CALL CStdAllocatorHeap::GetNextAllocatedBlock( LPLSA_FREEHEADER _lpAfterMe ) const {
                LSA_SIZE sStart = reinterpret_cast<LSA_SIZE>(_lpAfterMe);
                sStart += _lpAfterMe->sActualSize;
                LSA_SIZE sOurEnd = reinterpret_cast<LSA_SIZE>(m_pvHeap);

                // If it points to the end of the block or beyond there is nothing there.
                if ( sStart >= (sOurEnd + m_sSize) ) {
                        return NULL;
                }
                return reinterpret_cast<LPLSA_ALLOCATIONHEADER>(sStart);
        }

        // Get the next free block after the given allocated block, or NULL for none.
        LSE_INLINE CStdAllocatorHeap::LPLSA_FREEHEADER LSE_CALL CStdAllocatorHeap::GetNextFreeBlock( LPLSA_ALLOCATIONHEADER _lpahAfterMe ) {
                // Go to the free block before this allocation.
                LPLSA_FREEHEADER lpfhThis = _lpahAfterMe->pfhPrevFree;
                if ( !lpfhThis ) {
                        return m_lpfhFreeHead;
                }
                // Return the next free block after that.
                return lpfhThis->pfhNextFree;
        }

        // Fix up the free pointers on allocated blocks following a free block.
        LSE_INLINE LSVOID LSE_CALL CStdAllocatorHeap::FixUpAllocationFreeBlockPointers( LPLSA_FREEHEADER _lpfhAfterMe ) {
                //LSA_SIZE sIamAt = reinterpret_cast<LSA_SIZE>(_lpfhAfterMe);
                LSA_SIZE sEnd = reinterpret_cast<LSA_SIZE>(_lpfhAfterMe->pfhNextFree);
                if ( !sEnd ) {
                        sEnd = static_cast<LSA_SIZE>(-1);
                }

                /*for ( LSUINT32 I = 0; I < LSA_BUCKETS; ++I ) {
                        for ( LPLSA_ALLOCATIONHEADER lpahThis = m_lpahAllocatedBlocks[I]; lpahThis; lpahThis = lpahThis->pahNextInHash ) {
                                LSA_SIZE sThis = reinterpret_cast<LSA_SIZE>(lpahThis);
                                if ( sThis > sIamAt && sThis < sEnd ) {
                                        lpahThis->pfhPrevFree = _lpfhAfterMe;
                                }
                        }
                }*/


                LPLSA_ALLOCATIONHEADER lpahStart;
                for ( lpahStart = GetNextAllocatedBlock( _lpfhAfterMe );
                        lpahStart;
                        lpahStart = lpahStart->pahNext ) {
                        LSA_SIZE sItPointsTo = reinterpret_cast<LSA_SIZE>(lpahStart->pfhPrevFree);
                        // If it points below us, we are the new closest.
                        // Make it point at us.
                        if ( sItPointsTo < sEnd ) {
                                lpahStart->pfhPrevFree = _lpfhAfterMe;
                        }
                        else {
                                break;
                        }
                }
        }

        // In a linked-list of allocated blocks, replace each elementís previous free pointer with the one given
        //      if it matches the provided original free-block pointer.  Stops scanning at the first block that does
        //      not match the given key.
        LSE_INLINE LSVOID LSE_CALL CStdAllocatorHeap::ReplaceAllocationFreeBlockPointers( LPLSA_ALLOCATIONHEADER _lpahStart, LPLSA_FREEHEADER _lpfhReplaceMe, LPLSA_FREEHEADER _lpfhWithMe ) {
                for ( ; _lpahStart; _lpahStart = _lpahStart->pahNext ) {
                        if ( _lpahStart->pfhPrevFree != _lpfhReplaceMe ) { return; }
                        _lpahStart->pfhPrevFree = _lpfhWithMe;
                }
        }

        // Find an allocated block given its address.
        LSE_INLINE CStdAllocatorHeap::LPLSA_ALLOCATIONHEADER LSE_CALL CStdAllocatorHeap::FindAllocationBlock( LSVOID * _pvAddr ) {
                LSUINT32 ui32Key = GetHashKey( _pvAddr );
                // For every allocation in the hash table.
                for ( LPLSA_ALLOCATIONHEADER lpahThis = m_lpahAllocatedBlocks[ui32Key]; lpahThis; lpahThis = lpahThis->pahNextInHash ) {
                        if ( GetStartAddress( lpahThis ) == _pvAddr ) {
                                return lpahThis;
                        }
                }
                return NULL;
        }


}       // namespace lsa

#endif  // __LSA_STDALLOCATORHEAP_H__