DS_MemoryPool.h

Go to the documentation of this file.

#ifndef __MEMORY_POOL_H
#define __MEMORY_POOL_H

#ifndef __APPLE__
// Use stdlib and not malloc for compatibility
#include <stdlib.h>
#endif
#include "RakAssert.h"
#include "Export.h"

#include "RakMemoryOverride.h"

// DS_MEMORY_POOL_MAX_FREE_PAGES must be > 1
#define DS_MEMORY_POOL_MAX_FREE_PAGES 4

//#define _DISABLE_MEMORY_POOL

namespace DataStructures
{
    template <class MemoryBlockType>
    class RAK_DLL_EXPORT MemoryPool
    {
    public:
        struct Page;
        struct MemoryWithPage
        {
            MemoryBlockType userMemory;
            Page *parentPage;
        };
        struct Page
        {
            MemoryWithPage** availableStack;
            int availableStackSize;
            MemoryWithPage* block;
            Page *next, *prev;
        };

        MemoryPool();
        ~MemoryPool();
        void SetPageSize(int size); // Defaults to 16384 bytes
        MemoryBlockType *Allocate(const char *file, unsigned int line);
        void Release(MemoryBlockType *m, const char *file, unsigned int line);
        void Clear(const char *file, unsigned int line);

        int GetAvailablePagesSize(void) const {return availablePagesSize;}
        int GetUnavailablePagesSize(void) const {return unavailablePagesSize;}
        int GetMemoryPoolPageSize(void) const {return memoryPoolPageSize;}
    protected:
        int BlocksPerPage(void) const;
        void AllocateFirst(void);
        bool InitPage(Page *page, Page *prev, const char *file, unsigned int line);

        // availablePages contains pages which have room to give the user new blocks.  We return these blocks from the head of the list
        // unavailablePages are pages which are totally full, and from which we do not return new blocks.
        // Pages move from the head of unavailablePages to the tail of availablePages, and from the head of availablePages to the tail of unavailablePages
        Page *availablePages, *unavailablePages;
        int availablePagesSize, unavailablePagesSize;
        int memoryPoolPageSize;
    };

    template<class MemoryBlockType>
    MemoryPool<MemoryBlockType>::MemoryPool()
    {
#ifndef _DISABLE_MEMORY_POOL
        //AllocateFirst();
        availablePagesSize=0;
        unavailablePagesSize=0;
        memoryPoolPageSize=16384;
#endif
    }
    template<class MemoryBlockType>
    MemoryPool<MemoryBlockType>::~MemoryPool()
    {
#ifndef _DISABLE_MEMORY_POOL
        Clear(_FILE_AND_LINE_);
#endif
    }

    template<class MemoryBlockType>
    void MemoryPool<MemoryBlockType>::SetPageSize(int size)
    {
        memoryPoolPageSize=size;
    }

    template<class MemoryBlockType>
    MemoryBlockType* MemoryPool<MemoryBlockType>::Allocate(const char *file, unsigned int line)
    {
#ifdef _DISABLE_MEMORY_POOL
        return (MemoryBlockType*) rakMalloc_Ex(sizeof(MemoryBlockType), file, line);
#else

        if (availablePagesSize>0)
        {
            MemoryBlockType *retVal;
            Page *curPage;
            curPage=availablePages;
            retVal = (MemoryBlockType*) curPage->availableStack[--(curPage->availableStackSize)];
            if (curPage->availableStackSize==0)
            {
                --availablePagesSize;
                availablePages=curPage->next;
                RakAssert(availablePagesSize==0 || availablePages->availableStackSize>0);
                curPage->next->prev=curPage->prev;
                curPage->prev->next=curPage->next;

                if (unavailablePagesSize++==0)
                {
                    unavailablePages=curPage;
                    curPage->next=curPage;
                    curPage->prev=curPage;  
                }
                else
                {
                    curPage->next=unavailablePages;
                    curPage->prev=unavailablePages->prev;
                    unavailablePages->prev->next=curPage;
                    unavailablePages->prev=curPage;
                }           
            }

            RakAssert(availablePagesSize==0 || availablePages->availableStackSize>0);
            return retVal;
        }

        availablePages = (Page *) rakMalloc_Ex(sizeof(Page), file, line);
        if (availablePages==0)
            return 0;
        availablePagesSize=1;
        if (InitPage(availablePages, availablePages, file, line)==false)
            return 0;
        // If this assert hits, we couldn't allocate even 1 block per page. Increase the page size
        RakAssert(availablePages->availableStackSize>1);

        return (MemoryBlockType *) availablePages->availableStack[--availablePages->availableStackSize];
#endif
    }
    template<class MemoryBlockType>
    void MemoryPool<MemoryBlockType>::Release(MemoryBlockType *m, const char *file, unsigned int line)
    {
#ifdef _DISABLE_MEMORY_POOL
        rakFree_Ex(m, file, line);
        return;
#else
        // Find the page this block is in and return it.
        Page *curPage;
        MemoryWithPage *memoryWithPage = (MemoryWithPage*)m;
        curPage=memoryWithPage->parentPage;

        if (curPage->availableStackSize==0)
        {
            // The page is in the unavailable list so move it to the available list
            curPage->availableStack[curPage->availableStackSize++]=memoryWithPage;
            unavailablePagesSize--;

            // As this page is no longer totally empty, move it to the end of available pages
            curPage->next->prev=curPage->prev;
            curPage->prev->next=curPage->next;
            
            if (unavailablePagesSize>0 && curPage==unavailablePages)
                unavailablePages=unavailablePages->next;
            
            if (availablePagesSize++==0)
            {
                availablePages=curPage;
                curPage->next=curPage;
                curPage->prev=curPage;
            }
            else
            {
                curPage->next=availablePages;
                curPage->prev=availablePages->prev;
                availablePages->prev->next=curPage;
                availablePages->prev=curPage;   
            }
        }
        else
        {
            curPage->availableStack[curPage->availableStackSize++]=memoryWithPage;

            if (curPage->availableStackSize==BlocksPerPage() &&
                availablePagesSize>=DS_MEMORY_POOL_MAX_FREE_PAGES)
            {
                // After a certain point, just deallocate empty pages rather than keep them around
                if (curPage==availablePages)
                {
                    availablePages=curPage->next;
                    RakAssert(availablePages->availableStackSize>0);
                }
                curPage->prev->next=curPage->next;
                curPage->next->prev=curPage->prev;
                availablePagesSize--;
                rakFree_Ex(curPage->availableStack, file, line );
                rakFree_Ex(curPage->block, file, line );
                rakFree_Ex(curPage, file, line );
            }
        }
#endif
    }
    template<class MemoryBlockType>
    void MemoryPool<MemoryBlockType>::Clear(const char *file, unsigned int line)
    {
#ifdef _DISABLE_MEMORY_POOL
        return;
#else
        Page *cur, *freed;

        if (availablePagesSize>0)
        {
            cur = availablePages;
#ifdef _MSC_VER
#pragma warning(disable:4127)   // conditional expression is constant
#endif
            while (true) 
            // do
            {
                rakFree_Ex(cur->availableStack, file, line );
                rakFree_Ex(cur->block, file, line );
                freed=cur;
                cur=cur->next;
                if (cur==availablePages)
                {
                    rakFree_Ex(freed, file, line );
                    break;
                }
                rakFree_Ex(freed, file, line );
            }// while(cur!=availablePages);
        }
        
        if (unavailablePagesSize>0)
        {
            cur = unavailablePages;
            while (1)
            //do 
            {
                rakFree_Ex(cur->availableStack, file, line );
                rakFree_Ex(cur->block, file, line );
                freed=cur;
                cur=cur->next;
                if (cur==unavailablePages)
                {
                    rakFree_Ex(freed, file, line );
                    break;
                }
                rakFree_Ex(freed, file, line );
            } // while(cur!=unavailablePages);
        }

        availablePagesSize=0;
        unavailablePagesSize=0;
#endif
    }
    template<class MemoryBlockType>
    int MemoryPool<MemoryBlockType>::BlocksPerPage(void) const
    {
        return memoryPoolPageSize / sizeof(MemoryWithPage);
    }
    template<class MemoryBlockType>
    bool MemoryPool<MemoryBlockType>::InitPage(Page *page, Page *prev, const char *file, unsigned int line)
    {
        int i=0;
        const int bpp = BlocksPerPage();
        page->block=(MemoryWithPage*) rakMalloc_Ex(memoryPoolPageSize, file, line);
        if (page->block==0)
            return false;
        page->availableStack=(MemoryWithPage**)rakMalloc_Ex(sizeof(MemoryWithPage*)*bpp, file, line);
        if (page->availableStack==0)
        {
            rakFree_Ex(page->block, file, line );
            return false;
        }
        MemoryWithPage *curBlock = page->block;
        MemoryWithPage **curStack = page->availableStack;
        while (i < bpp)
        {
            curBlock->parentPage=page;
            curStack[i]=curBlock++;
            i++;
        }
        page->availableStackSize=bpp;
        page->next=availablePages;
        page->prev=prev;
        return true;
    }
}

#endif