/*
 * Memory handling
 *
 * Copyright (c) 1998 Criterion Software Ltd.
 */

/**
 * \ingroup rwfreelist
 * \page rwfreelistoverview RwFreeList Overview
 *
 * This object provides a platform-neutral memory allocation API.
 *
 * A free list can be used to allocate memory for
 * lists of identical datatypes.
 * As the list is filled, the free list mechanism can be set to automatically
 * allocate more memory in developer-defined chunks.
 * Getting the most out of this system can require some fine-tuning work,
 * but the result should be an optimal trade-off between
 * memory usage and speed.
 */

/**
 * \ingroup rwmem
 * \page rwmemoverview RwMem Overview
 *
 * A set of utility functions intended to ease cross-platform compatibility of
 * RenderWare Graphics data structures.
 *
 * These functions include conversions from RenderWare Graphics' intrinsic
 * types - RwInt32, RwInt16, RwReal, etc. - into platform-neutral forms.
 *
 */

#if (!defined(RWKEEPFREELISTS))
#define RWKEEPFREELISTS
#endif /* (!defined(RWKEEPFREELISTS)) */

/****************************************************************************
 Includes
 */

#include <stdlib.h>
#include <string.h>

#include "batypes.h"
#include "balibtyp.h"
#include "badebug.h"
#include "rwstring.h" /* for unicode support */
#include "bamemory.h"

#if (!defined(DOXYGEN))
static const char   rcsid[] __RWUNUSED__ =
    "@@(#)$Id: bamemory.c,v 1.121 2001/07/10 11:54:53 johns Exp $";
#endif /* (!defined(DOXYGEN)) */

/****************************************************************************
 Local Types
 */

/****************************************************************************
 Local (Static) Prototypes
 */

/****************************************************************************
 Local Defines
 */

#if (defined(_WINDOWS))
#define  __RWCDECL                   __cdecl
#endif /* (defined(_WINDOWS)) */

#if (!defined(__RWCDECL))
#define  __RWCDECL             /* No op */
#endif /* (!defined(__RWCDECL)) */

/****************************************************************************
 Globals (across program)
 */

/****************************************************************************
 Local (static) Globals
 */

static RwLinkList   llGAllFreeLists;

#ifndef calloc

/* Make our own fake version of calloc for systems that don't have it */
static void *
FakeCalloc(size_t numObj, size_t sizeObj)
{
    size_t              totalSize = numObj * sizeObj;
    void               *newMem;

    RWFUNCTION(RWSTRING("FakeCalloc"));

    /* Allocate it */
    newMem = malloc(totalSize);

    /* Clear it if allocated */
    if (newMem)
    {
        memset(newMem, 0, totalSize);
    }

    /* Return the memory if allocated */
    RWRETURN(newMem);
}
#endif /* calloc */

/****************************************************************************
 FreeListBlockValidate

 On entry   : Free list
            : Thing to free
 On exit    : TRUE if ok to free
 */

#if (defined(RWDEBUG))
static  RwBool
FreeListBlockValidate(RwFreeList * freelist, void *pBlock)
{
    void              **ppPos;
    RwFreeBlock        *fbpCur;

    RWFUNCTION(RWSTRING("FreeListBlockValidate"));
    RWASSERT(freelist);
    RWASSERT(pBlock);

    /* Check if the address is alredy on the stack */
    ppPos = freelist->freeListStack;

    while (ppPos <= freelist->freeListStackTop)
    {
        if ((*ppPos) == pBlock)
        {
            RWERROR((E_RW_FREELISTFREED));
            RWRETURN(FALSE);
        }

        /* next */
        ppPos++;
    }

    /* Check if the address is possible */
    fbpCur = freelist->firstBlock;
    while (fbpCur)
    {
        RwUInt8            *cpFirst, *cpLast;

        /* Get address of first aligned block */
        cpFirst =
            ((RwUInt8 *) (fbpCur + 1)) + freelist->alignmentMinusOne;
        cpFirst =
            (RwUInt8 *) ((RwUInt32) cpFirst &
                         (~freelist->alignmentMinusOne));

        /* And address after last */
        cpLast =
            cpFirst + (freelist->entriesPerBlock * freelist->entrySize);

        if ((pBlock >= (void *) cpFirst) && (pBlock < (void *) cpLast))
        {
            RwInt32             nPos;

            /* Apparently its in this block */
            nPos = (RwInt32) ((RwUInt8 *) pBlock - (RwUInt8 *) cpFirst);

            if (nPos % freelist->entrySize)
            {
                /* Its not on a valid boundary */
                RWERROR((E_RW_FREELISTINVMEMBOUND));
                RWRETURN(FALSE);
            }

            RWRETURN(TRUE);
        }

        /* next */
        fbpCur = fbpCur->nextBlock;
    }

    /* So its not a valid address */
    RWERROR((E_RW_FREELISTINVADDRESS));
    RWRETURN(FALSE);
}

#endif /* defined(RWDEBUG) */

/****************************************************************************
 FreeListPurgeSort

 On entry   : Ptr 1
            : Ptr 2
 On exit    : Ptr 1<Ptr2 -1
            : Ptr 1>Ptr2 1
 */

static int          __RWCDECL
FreeListPurgeSort(const void *pA, const void *pB)
{
    const void        **ppPtrA = (const void **) pA;
    const void        **ppPtrB = (const void **) pB;

    RWFUNCTION(RWSTRING("FreeListPurgeSort"));
    RWRETURN(((int) (*ppPtrA)) - ((int) (*ppPtrB)));
}

static void
SortBlocks(RwFreeList * freelist)
{
    /* Sort the blocks of memory */
    RwBool              bFlip;

    RWFUNCTION(RWSTRING("SortBlocks"));

    do
    {
        RwFreeBlock       **fbppPrev = &freelist->firstBlock;
        RwFreeBlock        *fbpCur = freelist->firstBlock;
        RwFreeBlock        *nextBlock;

        bFlip = FALSE;

        while ((nextBlock = fbpCur->nextBlock))
        {
            if (nextBlock < fbpCur)
            {
                bFlip = TRUE;

                /* Flip around the blocks */
                (*fbppPrev) = nextBlock;
                fbpCur->nextBlock = nextBlock->nextBlock;
                nextBlock->nextBlock = fbpCur;

                /* Onto next block */

                /* Cur is now the next block cos of the flip */
                fbppPrev = &(nextBlock->nextBlock);
            }
            else
            {
                /* Onto the next block */

                fbppPrev = &(fbpCur->nextBlock);
                fbpCur = nextBlock;
            }
        }
    }
    while (bFlip);

    RWRETURNVOID();
}

static              RwInt32
FreeContiguous(RwFreeList * freelist)
{
    /* Now we'll try to find blocks that we can throw away.
     * If we find pointers in the freelist that point at the start
     * and end of a block, and these are separated by entriesperblock,
     * then the block is not in use and can be freed.  Blowing the
     * block away is easy, but then we have to move all the remaining
     * freelist entries up to fill the space we have left behind.
     */
    RwInt32             memoryFreed = 0;
    RwFreeBlock        *prevBlock = (RwFreeBlock *) NULL;
    RwFreeBlock        *currBlock;
    void              **currAddr;
    RwBool              advance;

#if (defined(PURGEVERBOSE))
    RwUInt32            totalBlocks, count;
    RwUInt32            addr[100];
#endif /* (defined(PURGEVERBOSE)) */

    RWFUNCTION(RWSTRING("FreeContiguous"));

    RWASSERT(freelist);

    currBlock = freelist->firstBlock;
    currAddr = freelist->freeListStack;

#if (defined(PURGEVERBOSE))
    count = 0;
    totalBlocks = 0;
    while (currBlock)
    {
        addr[totalBlocks++] = (RwUInt32) currBlock;
        currBlock = currBlock->nextBlock;
    }
#endif /* (defined(PURGEVERBOSE)) */

    currBlock = freelist->firstBlock;
    while (currBlock)
    {
        /* what we are doing here is going to the end of the block,
         * and then backing up to the beginning.  This makes sure
         * that we compute alignment correctly.  The code here was
         * stolen from the code used to populate the stack with
         * block pointers.  This has been tested with align=128.
         */
        const RwInt32       blockSize = freelist->blockSize;
        const RwInt32       entrySize = freelist->entrySize;
        const RwInt32       alignmentMinusOne = freelist->alignmentMinusOne;
        const RwInt32       entriesPerBlock = freelist->entriesPerBlock;
        RwBool              candidate = FALSE;
        RwUInt8            *blockFirstAddr = (RwUInt8 *) NULL;
        const RwInt32       offset = blockSize - entrySize;
        RwUInt8            *blockLastAddr = &((RwUInt8 *) currBlock)[offset];

        /* Align last pBlock */
        blockLastAddr = (RwUInt8 *)
            ((RwUInt32) blockLastAddr & (~alignmentMinusOne));

        blockFirstAddr =
            blockLastAddr - (entriesPerBlock - 1) * entrySize;

        /* search through the freelist looking for a
         * pointer to the first block address
         */

        advance = TRUE;

        while ((currAddr <= freelist->freeListStackTop))
        {
            candidate = ( ((RwUInt8 *)*currAddr) >= blockFirstAddr);
            if (candidate)
                break;

            currAddr++;
        }

        /* either we ran out of options , or we found a pointer */
        if (!candidate)
        {
            /* nothing else to do */
            currBlock = (RwFreeBlock *) NULL;
        }
        else if (*currAddr == blockFirstAddr)
        {
            /* we found a pointer to the start of the block */

            /* compute a pointer to the last object in the block */
            const RwInt32       lastSlot = entriesPerBlock - 1;
            const RwInt32       offset = lastSlot * (entrySize);
            void               *blockLastAddr =
                (void *) &(((RwUInt8 *) blockFirstAddr)[offset]);

            if (&(currAddr[lastSlot]) <= freelist->freeListStackTop)
            {
                if (currAddr[lastSlot] == blockLastAddr)
                {
                    /* we can blow away this block */
                    void              **ppCopy;

#if (defined(PURGEVERBOSE))
                    RwInt32             i;

                    ++count;
                    RWMESSAGE(("Block to blow away: (%p) %d/%d\n",
                               freelist, count, totalBlocks));
                    for (i = 0; i < totalBlocks; i++)
                    {
                        RWMESSAGE(("%p->", addr[i]));
                    }
                    if (prevBlock == NULL)
                    {
                        RWMESSAGE(("*prev = NULL\n"));
                    }
                    else
                    {
                        RWMESSAGE(("*prev = %p\n", prevBlock));
                    }
#endif /* (defined(PURGEVERBOSE)) */

                    {

                        RwFreeBlock        *post = currBlock->nextBlock;

                        RwFree(currBlock);

                        if (prevBlock == NULL)
                        {
                            /* update head */
                            freelist->firstBlock = post;
                        }
                        else
                        {
                            prevBlock->nextBlock = post;
                        }
                        currBlock = post;
                        advance = FALSE;

#if (defined(PURGEVERBOSE))
                        totalBlocks--;
                        post = freelist->firstBlock;
                        for (i = 0; i < totalBlocks; i++)
                        {
                            RWMESSAGE(("%p->", post));

                            post = post->nextBlock;
                        }
                        RWMESSAGE(("deleted %p\n", currBlock));
#endif /* (defined(PURGEVERBOSE)) */

                    }

                    /* We managed to free up some more memory */
                    memoryFreed += blockSize;

                    /* Remove the pointers from the free list */
                    ppCopy = currAddr;
                    while (&ppCopy[entriesPerBlock] <=
                           freelist->freeListStackTop)
                    {
                        *ppCopy++ = ppCopy[entriesPerBlock];
                    }

                    /* We now have this many elements on the stack */
                    freelist->freeListStackTop -= entriesPerBlock;

                    /* And the possibility of having less element free
                     * at maximum */
                    freelist->entriesAllocated -= entriesPerBlock;
                }
            }
        }

        if ((currBlock) && (advance))
        {
            prevBlock = currBlock;
            currBlock = currBlock->nextBlock;
        }
#if (defined(PURGEVERBOSE))
        count++;
#endif /* (defined(PURGEVERBOSE)) */
    }
    RWRETURN(memoryFreed);
}

/**
 * \ingroup rwos
 * \ref RwOsGetMemoryInterface is used to retrieve the memory functions
 * used by RenderWare. By default the standard ANSI functions are used. The
 * application may install an alternative interface providing that it is ANSI
 * compliant.
 *
 * If an application wishes to completely overload the memory interface then
 * this can be achieved via the \ref RwEngineInit API function which guarantees
 * that the overload takes place before any memory allocation. The memory
 * function pointers should not be manipulated directly.
 *
 * Note that since RenderWare allocates and frees memory in an asynchronous
 * fashion it is not possible to install a completely different memory handler
 * once the library has been initialized. It is, however, possible to install
 * a daisy chained handler that gathers statistics before calling the default.
 *
 * See the section RenderWare Data Types for details of the memory interface.
 *
 * \return Returns pointer to a \ref RwMemoryFunctions value containing pointers to
 * memory access functions. The elements of this structure may be modified
 * directly to install an alternative memory interface.
 *
 * \see RwEngineInit
 * \see RwOsGetFileInterface
 *
 */
RwMemoryFunctions *
RwOsGetMemoryInterface(void)
{
    RWAPIFUNCTION(RWSTRING("RwOsGetMemoryInterface"));

    RWRETURN(&RWSRCGLOBAL(memoryFuncs));
}

/* !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

   Free Lists

   !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! */

/**
 * \ingroup rwfreelist
 * \ref RwFreeListDestroy is used to release the block (or blocks) of
 * memory used by the specified free list.
 *
 * \param freelist  Pointer to the free list.
 *
 * \return Returns TRUE if successful or FALSE if there is an error.
 *
 * \see RwFreeListAlloc
 * \see RwFreeListCreate
 * \see RwFreeListFree
 * \see RwFreeListPurge
 * \see RwFreeListForAllUsed
 * \see RwFreeListPurgeAllFreeLists
 *
 */
RwBool
RwFreeListDestroy(RwFreeList * freelist)
{
    RwFreeBlock        *fbpCur;

    RWAPIFUNCTION(RWSTRING("RwFreeListDestroy"));
    RWASSERT(freelist);

    if (freelist->freeListStack)
    {
        RwFree(freelist->freeListStack);
    }

    /* Free all of the blocks */
    fbpCur = freelist->firstBlock;

    while (fbpCur)
    {
        RwFreeBlock        *nextBlock;

        nextBlock = fbpCur->nextBlock;
        RwFree(fbpCur);
        fbpCur = nextBlock;
    }

    /* Remove the free list from the list of all freelists */
    rwLinkListRemoveLLLink(&freelist->lFreeList);

    /* Done */
    RwFree(freelist);
    RWRETURN(TRUE);
}

static RwFreeList *
FreeListCreate(RwInt32 entrySize, RwInt32 blockEntries, RwInt32 alignment)
{
    RwFreeList         *freelist;

    RWFUNCTION(RWSTRING("FreeListCreate"));
    RWASSERT(entrySize);
    RWASSERT(blockEntries);
    RWASSERT(!(alignment & (alignment - 1))); /* Assert power of 2 */

    freelist = (RwFreeList *) RwMalloc(sizeof(RwFreeList));
    if (freelist)
    {

        /* Deal with don't care case (align to 1 byte :-) */
        alignment = (alignment > 1) ? alignment : 1;

        /* Enforce alignment of packed elements */
        freelist->alignmentMinusOne = alignment - 1;
        entrySize += freelist->alignmentMinusOne;
        entrySize &= (~freelist->alignmentMinusOne);

        /* Set characteristics of the free list */
        freelist->entrySize = entrySize;
        freelist->entriesPerBlock = blockEntries;

        /* The block size */
        freelist->blockSize =
            (entrySize * blockEntries) + sizeof(RwFreeBlock);

        /* Allow enough space for alignment of first element */
        freelist->blockSize += freelist->alignmentMinusOne;

        /* Say that the stack is empty */
        freelist->freeListStack = (void **) RwMalloc(sizeof(void *));

        if (freelist->freeListStack)
        {

            freelist->freeListStackTop = freelist->freeListStack - 1;
            freelist->entriesAllocated = 0;
            freelist->firstBlock = (RwFreeBlock *) NULL;

            /* Add the freelist the link list of all free lists */
            rwLinkListAddLLLink(&llGAllFreeLists, &freelist->lFreeList);
        }
        else
        {
            RWERROR((E_RW_NOMEM, sizeof(void *)));
            RwFree(freelist);
            freelist = ((RwFreeList *) NULL);
        }
    }
    else
    {
        RWERROR((E_RW_NOMEM, sizeof(RwFreeList)));
        freelist = ((RwFreeList *) NULL);
    }

    /* Done */
    RWRETURN(freelist);
}

#if (defined(RWDEBUG) && !defined(DOXYGEN))

RwFreeList *
_rwFreeListCreate(RwInt32 entrySize,
                  RwInt32 entriesPerBlock,
                  RwInt32 alignment,
                  const RwChar * fileCreate,
                  RwUInt32 lineCreate)
{
    RwFreeList         *freelist;

    RWFUNCTION(RWSTRING("_rwFreeListCreate"));
    RWASSERT(entrySize);
    RWASSERT(entriesPerBlock);
    RWASSERT(!(alignment & (alignment - 1))); /* Assert power of 2 */

    freelist = FreeListCreate(entrySize, entriesPerBlock, alignment);

    /* If successful, record creation point for posterity/debugging
     */
    if (freelist)
    {
        freelist->fileCreate = fileCreate;
        freelist->lineCreate = lineCreate;
    }
    RWRETURN(freelist);
}

#else /* (defined(RWDEBUG) && !defined(DOXYGEN)) */
/**
 * \ingroup rwfreelist
 * \ref RwFreeListCreate is used to create a new free list that will
 * contain the specified number of entries, each of the specified size (in
 * bytes), in a single block of memory. Initially, the free list is empty and
 * no memory is allocated for any entries. Only when one of the entries is
 * requested from a call to \ref RwFreeListAlloc is the whole block allocated.
 *
 * \param entrySize  A RwInt32 value equal to
 *                   the size of each entry (in bytes).
 * \param blockEntries  A RwInt32 value equal to
 *                      the number of entries.
 * \param alignment  A RwInt32 value equal to
 *                   the desired byte alignment of entries.
 *                   The alignment must be a power of two.
 *                  Zero indicates don't care.
 *
 * \return Returns pointer to the new free list if successful
 *         or NULL if there is an error.
 *
 * \see RwFreeListAlloc
 * \see RwFreeListFree
 * \see RwFreeListPurge
 * \see RwFreeListForAllUsed
 * \see RwFreeListDestroy
 * \see RwFreeListPurgeAllFreeLists
 */
RwFreeList *
RwFreeListCreate(RwInt32 entrySize, RwInt32 blockEntries,  RwInt32 alignment)
{
    RwFreeList         *freelist;

    RWAPIFUNCTION(RWSTRING("RwFreeListCreate"));
    RWASSERT(entrySize);
    RWASSERT(blockEntries);
    RWASSERT(!(alignment & (alignment - 1))); /* Assert power of 2 */

    freelist = FreeListCreate(entrySize, blockEntries, alignment);

    RWRETURN(freelist);
}
#endif /* (defined(RWDEBUG) && !defined(DOXYGEN)) */

RwFreeList *
_rwFreeListFreeReal(RwFreeList * freelist, void *pBlock)
{
    RWFUNCTION(RWSTRING("_rwFreeListFreeReal"));
    RWASSERT(freelist);
    RWASSERT(pBlock);

#if (defined(RWDEBUG))
    /* Do we need to do extra checking? */
    if (RWSRCGLOBAL(freeListExtraDebug))
    {
        RwBool              validBlockFreed;

        validBlockFreed = FreeListBlockValidate(freelist, pBlock);

        RWASSERT(validBlockFreed);

        if (!validBlockFreed)
        {
            /* Can't free something that isn't in the list */
            RWRETURN((RwFreeList *)NULL);
        }
    }

    /* Mark as unused */
    memset(pBlock, rwFREELISTDEADLANDFILL, freelist->entrySize);
#endif /* defined(RWDEBUG) */

    /* Free the chunk of memory */
    (*(++(freelist->freeListStackTop))) = pBlock;

    RWRETURN(freelist);
}

void *
_rwFreeListAllocReal(RwFreeList * freelist)
{
    void               *pBlock;

    RWFUNCTION(RWSTRING("_rwFreeListAllocReal"));
    RWASSERT(freelist);

    if (freelist->freeListStackTop < freelist->freeListStack)
    {
        RwFreeBlock        *fbpBlock;
        void              **freeListStack;
        RwUInt32            bytes;

        /* Create a block */
        fbpBlock = (RwFreeBlock *) RwMalloc(freelist->blockSize);

        if (!fbpBlock)
        {
            RWERROR((E_RW_NOMEM, (freelist->blockSize)));
            RWRETURN(NULL);
        }

        /* Create the stack */

        bytes = ( sizeof(void *) *
                  (freelist->entriesAllocated + freelist->entriesPerBlock) );

        freeListStack = (void **) RwMalloc(bytes);

        if (!freeListStack)
        {
            RWERROR((E_RW_NOMEM, (bytes)));

            RwFree(fbpBlock);
            RWRETURN(NULL);
        }

        RwFree(freelist->freeListStack);

        freelist->freeListStack = freeListStack;

        /* We now have this many entries stored */
        freelist->entriesAllocated += freelist->entriesPerBlock;

        /* Add the pBlock to the list */
        fbpBlock->nextBlock = freelist->firstBlock;
        freelist->firstBlock = fbpBlock;

        /* Add the new pBlock entries */
        {
            const RwInt32       offset = (freelist->blockSize -
                                          freelist->entrySize);
            RwUInt8            *cpData = (((RwUInt8 *) (fbpBlock)) + offset);
            RwInt32             nI;

            /* Align last pBlock */
            cpData = ((RwUInt8 *) ((RwUInt32) cpData &
                                   (~freelist->alignmentMinusOne)));

            /* Then work backwards adding to the freelist stack */
            nI = freelist->entriesPerBlock;

            RWASSERT(0 < nI);

            while (nI--)
            {
                (*freeListStack) = (void *) cpData;
                freeListStack++;
                cpData -= freelist->entrySize;
            }
        }

        freelist->freeListStackTop = (freelist->freeListStack) +
            (freelist->entriesPerBlock - 1);
    }

    /* Do the alloc */
    pBlock = *(freelist->freeListStackTop--);

    /* Assert desired alignment has occured */
    RWASSERT(((RwUInt32) pBlock & freelist->alignmentMinusOne) == 0);

#if (defined(RWDEBUG))
    /* Do we need to do extra checking? */
    if (RWSRCGLOBAL(freeListExtraDebug))
    {
        RwBool              validPBlockFreed;

        validPBlockFreed = FreeListBlockValidate(freelist, pBlock);

        RWASSERT(validPBlockFreed);
    }

    /* Mark as new */
    memset(pBlock, rwFREELISTCLEANLANDFILL, freelist->entrySize);
#endif /* defined(RWDEBUG) */

    /* Return the pBlock */
    RWRETURN(pBlock);
}

/**
 * \ingroup rwfreelist
 * \ref RwFreeListPurge is used to the release the memory for any blocks
 * in the specified free list that wholly contain unused entries.  It returns
 * the amount of memory (in bytes) recovered.
 *
 * \param freelist  Pointer to free list.
 *
 * \return Returns amount of memory freed, or -1 if there is an error.
 *
 * \see RwFreeListAlloc
 * \see RwFreeListCreate
 * \see RwFreeListFree
 * \see RwFreeListForAllUsed
 * \see RwFreeListDestroy
 * \see RwFreeListPurgeAllFreeLists
 *
 */
RwInt32
RwFreeListPurge(RwFreeList * freelist)
{
    RwInt32             memoryFreed = 0;

    RWAPIFUNCTION(RWSTRING("RwFreeListPurge"));
    RWASSERT(freelist);

    if (freelist->freeListStackTop >= freelist->freeListStack)
    {
        const RwInt32       nFreeEntries =
            (((RwInt32)
              (((RwUInt8 *) (freelist->freeListStackTop)) -
               ((RwUInt8 *) (freelist->freeListStack)))) /
             sizeof(void *)) + 1;

        /* Sort all of the pointers */
        qsort(freelist->freeListStack, nFreeEntries, sizeof(void *),

              FreeListPurgeSort);

        /* Sort the blocks of memory */
        SortBlocks(freelist);

        /* Release runs of free entries filling a block */
        memoryFreed = FreeContiguous(freelist);
    }
    RWRETURN(memoryFreed);
}

static RwInt32
PurgeAllFreeLists(void)
{
    RwInt32             memoryFreed = 0;
    RwLLLink           *cur, *end;

    RWFUNCTION(RWSTRING("PurgeAllFreeLists"));

    cur = rwLinkListGetFirstLLLink(&llGAllFreeLists);
    end = rwLinkListGetTerminator(&llGAllFreeLists);
    while (cur != end)
    {
        /* Purge this list */
        RwFreeList * const  freeList = ( rwLLLinkGetData(cur, 
                                                         RwFreeList, 
                                                         lFreeList) );
        const RwInt32       thisMemoryFreed = RwFreeListPurge(freeList);

        if (0 < thisMemoryFreed)
        {
            memoryFreed += thisMemoryFreed;
        }

        /* Get next */
        cur = rwLLLinkGetNext(cur);
    }

    RWRETURN(memoryFreed);
}

/**
 * \ingroup rwfreelist
 * \ref RwFreeListPurgeAllFreeLists is used to purge all free lists in
 * the system.  It returns the amount of memory freed as a result.
 *
 * \return Returns amount of memory freed if successful, or -1 if there is an
 * error.
 *
 * \see RwFreeListAlloc
 * \see RwFreeListCreate
 * \see RwFreeListFree
 * \see RwFreeListPurge
 * \see RwFreeListDestroy
 * \see RwFreeListForAllUsed
 *
 */
RwInt32
RwFreeListPurgeAllFreeLists(void)
{
    RwInt32             passFreed;
    RwInt32             totalFreed = 0;

    RWAPIFUNCTION(RWSTRING("RwFreeListPurgeAllFreeLists"));

#if (defined(RWDEBUG))
    {
        RwInt32             passes = 0;

        do
        { 
#endif /* (defined(RWDEBUG)) */
            passFreed = PurgeAllFreeLists();
            totalFreed += passFreed;
#if (defined(RWDEBUG))
            passes++;
        }   while (0 < passFreed);

        RWASSERT(2 >= passes) ;
    }
#endif /* (defined(RWDEBUG)) */
    
    RWRETURN(totalFreed);
}

/**
 * \ingroup rwfreelist
 * \ref RwFreeListForAllUsed is used to apply the given callback
 * function to all used entries in the specified free list. The format of
 * the callback function is:
 * \verbatim
        void (*RwFreeListCallBack)(void *mem, void *data);
   \endverbatim
 * where data is a user-defined data pointer to pass to the callback function.
 *
 * \param freelist  Pointer to free list.
 * \param fpCallBack  Pointer to the callback to apply to call with each used block.
 * \param pData  Pointer to user-supplied data to pass to callback function.
 *
 * \return Returns pointer to the free list if successful or NULL
 * if there is an error.
 *
 * \see RwFreeListAlloc
 * \see RwFreeListCreate
 * \see RwFreeListFree
 * \see RwFreeListPurge
 * \see RwFreeListDestroy
 * \see RwFreeListPurgeAllFreeLists
 *
 */
RwFreeList *
RwFreeListForAllUsed(RwFreeList * freelist,
                     RwFreeListCallBack fpCallBack, void *pData)
{
    RwUInt8            *cpCur;
    RwFreeBlock        *fbpCur = freelist->firstBlock;

    RWAPIFUNCTION(RWSTRING("RwFreeListForAllUsed"));
    RWASSERT(freelist);
    RWASSERT(fpCallBack);

    while (fbpCur)
    {
        RwInt32             nI;

        cpCur = (RwUInt8 *) (fbpCur + 1);

        nI = freelist->entriesPerBlock;

        while (nI--)
        {
            void              **ppPos;

            /* Check if the address is already on the stack */
            ppPos = freelist->freeListStack;
            while (ppPos <= freelist->freeListStackTop)
            {
                if ((*ppPos) == (void *) cpCur)
                {
                    break;
                }

                /* next */
                ppPos++;
            }

            /* Is this used then? */
            if (!(ppPos <= freelist->freeListStackTop))
            {
                fpCallBack((void *) cpCur, pData);
            }

            /* Onto the next entry */
            cpCur += freelist->entrySize;
        }

        /* next */
        fbpCur = fbpCur->nextBlock;
    }

    RWRETURN(freelist);
}

#if (defined(DOXYGEN))

/**
 * \ingroup rwfreelist
 * \ref RwFreeListFree is used to mark the specified entry contained
 * in the given free list as unused.
 * Note that this function can be coerced to call RwFree through the
 * second argument to \ref RwEngineInit.
 * This function is actually implemented
 * as a macro that expands to either _rwFreeListAllocReal or RwFree.
 *
 * \param freelist  Pointer to freelist.
 * \param pBlock  Pointer to used entry.
 *
 * \return Returns pointer to the free list if successful or NULL
 * if there is an error.
 *
 * \see RwFreeListAlloc
 * \see RwFreeListCreate
 * \see RwFreeListPurge
 * \see RwFreeListForAllUsed
 * \see RwFreeListDestroy
 * \see RwFreeListPurgeAllFreeLists
 *
 */
RwFreeList *
RwFreeListFree(RwFreeList * freelist, void *pBlock)
{
    RWAPIFUNCTION(RWSTRING("RwFreeListFree"));

    RWRETURN(NULL);
}

/**
 * \ingroup rwfreelist
 * \ref RwFreeListAlloc is used to retrieve an unused entry from the
 * specified free list. If, prior to this function call, the free list is
 * empty, the whole free list block is allocated memory. If there are no
 * more unused entries left, new entries are retrieved from another
 * allocated block.
 * Note that this function can be coerced to call \ref RwMalloc through the
 * second argument to \ref RwEngineInit.
 * This is actually implemented
 * as a macro that expands to either _rwFreeListAllocReal or \ref RwMalloc.
 *
 * \param freelist  Pointer to the free list.
 *
 * \return Returns pointer to an unused entry if successful or NULL
 * is there is an error.
 *
 * \see RwFreeListCreate
 * \see RwFreeListFree
 * \see RwFreeListPurge
 * \see RwFreeListForAllUsed
 * \see RwFreeListDestroy
 * \see RwFreeListPurgeAllFreeLists
 *
 */
void *
RwFreeListAlloc(RwFreeList * freelist)
{
    RWAPIFUNCTION(RWSTRING("RwFreeListAlloc"));

    RWRETURN(NULL);
}

#endif /* (defined(DOXYGEN)) */

/* !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

   Open/close

   !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! */

/****************************************************************************
 _rwMemoryClose

 On entry   :
 On exit    :
 */

void
_rwMemoryClose(void)
{
    RWFUNCTION(RWSTRING("_rwMemoryClose"));

    RWRETURNVOID();
}

/****************************************************************************
 _rwMemoryOpen

 On entry   : Optional pointer to replacement memory functions
 On exit    : TRUE on success
 */

RwBool
_rwMemoryOpen(RwMemoryFunctions * memFuncs)
{
    RWFUNCTION(RWSTRING("_rwMemoryOpen"));

    rwLinkListInitialize(&llGAllFreeLists);

#if (defined(RWDEBUG))
    RWSRCGLOBAL(freeListExtraDebug) = FALSE;
#endif /* defined(RWDEBUG) */

    if (memFuncs)
    {
        /* Install user specified memory system */
        RWSRCGLOBAL(memoryFuncs) = *memFuncs;
    }
    else
    {
        /* Install an ANSI memory system */
        RWSRCGLOBAL(memoryFuncs).rwmalloc = malloc;
        RWSRCGLOBAL(memoryFuncs).rwfree = free;
        RWSRCGLOBAL(memoryFuncs).rwrealloc = realloc;
#if (defined(calloc))
        RWSRCGLOBAL(memoryFuncs).rwcalloc = calloc;
#else /* (defined(calloc)) */
        RWSRCGLOBAL(memoryFuncs).rwcalloc = FakeCalloc;
#endif /* (defined(calloc)) */
    }

    RWRETURN(TRUE);
}

#if (0 && defined(RWREDUNDANT))

static RwInt32
FreeContiguousOld(RwFreeList * freelist)
{
    /* Find out if a run of free entries fills a block */
    RwInt32             memoryFreed = 0;
    void              **curFreeEl;
    RwFreeBlock        *curBlock;
    RwFreeBlock       **prevBlockPointer;
    void               *blockFirstEl;
    void               *blockLastEl;
    RwInt32             distanceAcrossBlock =
        freelist->entrySize * (freelist->entriesPerBlock - 1);

    RWFUNCTION(RWSTRING("FreeContiguousOld"));

    curFreeEl = freelist->freeListStack;
    curBlock = freelist->firstBlock;
    prevBlockPointer = &freelist->firstBlock;

    while (curBlock && (curFreeEl +
                        freelist->entriesPerBlock <=
                        freelist->freeListStackTop))
    {
        /* Figure out the 1st and last elements of the current block */
        blockFirstEl = (void *) (curBlock + 1);
        blockLastEl =
            (void *) ((RwUInt8 *) blockFirstEl + distanceAcrossBlock);

        if (curFreeEl[0] < blockFirstEl)
        {
            /* Scan along the free el list */
            while ((curFreeEl[0] < blockFirstEl) &&
                   (curFreeEl + freelist->entriesPerBlock
                    <= freelist->freeListStackTop))
            {
                curFreeEl++;
            }
        }
        else if (curFreeEl[0] > blockFirstEl)
        {
            /* Scan along the block list */
            while ((curFreeEl[0] > blockFirstEl) && curBlock)
            {
                prevBlockPointer = &curBlock->nextBlock;
                curBlock = curBlock->nextBlock;
                blockFirstEl = (void *) (curBlock + 1);
                blockLastEl = (void *) ((RwUInt8 *) blockFirstEl +
                                        distanceAcrossBlock);
            }
        }
        else if ((curFreeEl[0] == blockFirstEl) &&
                 (curFreeEl[freelist->entriesPerBlock - 1]
                  == blockLastEl))
        {
            /* This block can be freed */
            void              **ppCopy;

            /* Delete the block */
            (*prevBlockPointer) = curBlock->nextBlock;
            RwFree(curBlock);
            curBlock = (*prevBlockPointer);

            /* We managed to free up some more memory */
            memoryFreed += freelist->blockSize;

            /* Remove the pointers from the free list */
            ppCopy = curFreeEl;
            while (ppCopy + freelist->entriesPerBlock <=
                   freelist->freeListStackTop)
            {
                ppCopy[0] = ppCopy[freelist->entriesPerBlock];
                ppCopy++;
            }

            /* We now have this many elements on the stack */
            freelist->freeListStackTop -= freelist->entriesPerBlock;

            /* And the possibility of having less element free at maximum */
            freelist->entriesAllocated -= freelist->entriesPerBlock;
        }
        else
        {
            /* Bump along to the next block */
            prevBlockPointer = &curBlock->nextBlock;
            curBlock = curBlock->nextBlock;
            blockFirstEl = (void *) (curBlock + 1);
            blockLastEl = (void *) ((RwUInt8 *)
                                    blockFirstEl + distanceAcrossBlock);
        }
    }

    RWRETURN(memoryFreed);
}

#endif /* (0 && defined(RWREDUNDANT)) */

