/* vmem.h
 *
 * (c) 1999 Microsoft Corporation. All rights reserved. 
 * Portions (c) 1999 ActiveState Tool Corp, http://www.ActiveState.com/
 *
 *    You may distribute under the terms of either the GNU General Public
 *    License or the Artistic License, as specified in the README file.
 *
 * Options:
 *
 * Defining _USE_MSVCRT_MEM_ALLOC will cause all memory allocations
 * to be forwarded to MSVCRT.DLL. Defining _USE_LINKED_LIST as well will
 * track all allocations in a doubly linked list, so that the host can
 * free all memory allocated when it goes away.
 * If _USE_MSVCRT_MEM_ALLOC is not defined then Knuth's boundary tag algorithm
 * is used; defining _USE_BUDDY_BLOCKS will use Knuth's algorithm R
 * (Buddy system reservation)
 * Defining _USE_EXERCISE_19 uses buddy block system and returns large 
 * free memory blocks to the OS
 *
 */

#ifndef ___VMEM_H_INC___
#define ___VMEM_H_INC___

// #define _USE_MSVCRT_MEM_ALLOC

// #define _USE_EXERCISE_19
// #define _USE_BUDDY_BLOCKS

// #define _DEBUG_MEM
#ifdef _DEBUG_MEM
#define ASSERT(f) if(!(f)) DebugBreak();

inline void MEMODS(char *str)
{
    OutputDebugString(str);
    OutputDebugString("\n");
}

inline void MEMODSlx(char *str, long x)
{
    char szBuffer[512];	
    sprintf(szBuffer, "%s %lx\n", str, x);
    OutputDebugString(szBuffer);
}

#define WALKHEAP() WalkHeap(0)
#define WALKHEAPTRACE() WalkHeap(1)

#else

#define ASSERT(f)
#define MEMODS(x)
#define MEMODSlx(x, y)
#define WALKHEAP()
#define WALKHEAPTRACE()

#endif

#ifdef _USE_MSVCRT_MEM_ALLOC

#ifndef _USE_LINKED_LIST
// #define _USE_LINKED_LIST
#endif

/* 
 * Pass all memory requests throught to msvcrt.dll 
 * optionaly track by using a doubly linked header
 */

typedef void (*LPFREE)(void *block);
typedef void* (*LPMALLOC)(size_t size);
typedef void* (*LPREALLOC)(void *block, size_t size);
#ifdef _USE_LINKED_LIST
typedef struct _MemoryBlockHeader* PMEMORY_BLOCK_HEADER;
typedef struct _MemoryBlockHeader {
    PMEMORY_BLOCK_HEADER    pNext;
    PMEMORY_BLOCK_HEADER    pPrev;
} MEMORY_BLOCK_HEADER, *PMEMORY_BLOCK_HEADER;
#endif

class VMem
{
public:
    VMem();
    ~VMem();
    virtual void* Malloc(size_t size);
    virtual void* Realloc(void* pMem, size_t size);
    virtual void Free(void* pMem);
    virtual void GetLock(void);
    virtual void FreeLock(void);
    virtual int IsLocked(void);
    virtual long Release(void);
    virtual long AddRef(void);

    inline BOOL CreateOk(void)
    {
	return TRUE;
    };

protected:
#ifdef _USE_LINKED_LIST
    void LinkBlock(PMEMORY_BLOCK_HEADER ptr)
    {
	PMEMORY_BLOCK_HEADER next = m_Dummy.pNext;
	m_Dummy.pNext = ptr;
	ptr->pPrev = &m_Dummy;
	ptr->pNext = next;
	next->pPrev = ptr;
    }
    void UnlinkBlock(PMEMORY_BLOCK_HEADER ptr)
    {
	PMEMORY_BLOCK_HEADER next = ptr->pNext;
	PMEMORY_BLOCK_HEADER prev = ptr->pPrev;
	prev->pNext = next;
	next->pPrev = prev;
    }

    MEMORY_BLOCK_HEADER	m_Dummy;
#endif

    long		m_lRefCount;	// number of current users
    CRITICAL_SECTION	m_cs;		// access lock
    HINSTANCE		m_hLib;
    LPFREE		m_pfree;
    LPMALLOC		m_pmalloc;
    LPREALLOC		m_prealloc;
};

VMem::VMem()
{
    m_lRefCount = 1;
    InitializeCriticalSection(&m_cs);
#ifdef _USE_LINKED_LIST
    m_Dummy.pNext = m_Dummy.pPrev =  &m_Dummy;
#endif
    m_hLib = LoadLibrary("msvcrt.dll");
    if (m_hLib) {
	m_pfree = (LPFREE)GetProcAddress(m_hLib, "free");
	m_pmalloc = (LPMALLOC)GetProcAddress(m_hLib, "malloc");
	m_prealloc = (LPREALLOC)GetProcAddress(m_hLib, "realloc");
    }
}

VMem::~VMem(void)
{
#ifdef _USE_LINKED_LIST
    while (m_Dummy.pNext != &m_Dummy) {
	Free(m_Dummy.pNext+1);
    }
#endif
    if (m_hLib)
	FreeLibrary(m_hLib);
    DeleteCriticalSection(&m_cs);
}

void* VMem::Malloc(size_t size)
{
#ifdef _USE_LINKED_LIST
    PMEMORY_BLOCK_HEADER ptr = (PMEMORY_BLOCK_HEADER)m_pmalloc(size+sizeof(MEMORY_BLOCK_HEADER));
    LinkBlock(ptr);
    return (ptr+1);
#else
    return m_pmalloc(size);
#endif
}

void* VMem::Realloc(void* pMem, size_t size)
{
#ifdef _USE_LINKED_LIST
    if (!pMem)
	return Malloc(size);

    if (!size) {
	Free(pMem);
	return NULL;
    }

    PMEMORY_BLOCK_HEADER ptr = (PMEMORY_BLOCK_HEADER)(((char*)pMem)-sizeof(MEMORY_BLOCK_HEADER));
    UnlinkBlock(ptr);
    ptr = (PMEMORY_BLOCK_HEADER)m_prealloc(ptr, size+sizeof(MEMORY_BLOCK_HEADER));
    LinkBlock(ptr);

    return (ptr+1);
#else
    return m_prealloc(pMem, size);
#endif
}

void VMem::Free(void* pMem)
{
#ifdef _USE_LINKED_LIST
    if (pMem) {
	PMEMORY_BLOCK_HEADER ptr = (PMEMORY_BLOCK_HEADER)(((char*)pMem)-sizeof(MEMORY_BLOCK_HEADER));
	UnlinkBlock(ptr);
	m_pfree(ptr);
    }
#else
    m_pfree(pMem);
#endif
}

#else	/* _USE_MSVCRT_MEM_ALLOC */

/*
 * Knuth's boundary tag algorithm Vol #1, Page 440.
 *
 * Each block in the heap has tag words before and after it,
 *  TAG
 *  block
 *  TAG
 * The size is stored in these tags as a long word, and includes the 8 bytes
 * of overhead that the boundary tags consume.  Blocks are allocated on long
 * word boundaries, so the size is always multiples of long words.  When the
 * block is allocated, bit 0, (the tag bit), of the size is set to 1.  When 
 * a block is freed, it is merged with adjacent free blocks, and the tag bit
 * is set to 0.
 *
 * A linked list is used to manage the free list. The first two long words of
 * the block contain double links.  These links are only valid when the block
 * is freed, therefore space needs to be reserved for them.  Thus, the minimum
 * block size (not counting the tags) is 8 bytes.
 *
 * Since memory allocation may occur on a single threaded, explict locks are not
 * provided.
 * 
 */

#ifdef _USE_EXERCISE_19
/*----------------------------------------------------------------------
 * Variation from above that incorporates the buddy block system and
 * the ideas from exercise 19.
 *
 * Since the allocations are always multiples of ULONG words, the lower 2
 * bits of the tag can be used to indicate the status of this block and
 * the previous block. Therefore the tag is only needed at the begining 
 * of a block. The size is stored as a ULONG, and DOES NOT include the 4 
 * bytes of overhead that the tag consumes.
 *
 * When the block is allocated, tag bit 0 (TAGBIT_FREE) of the size is set
 * to 0. Tag bit 1 (TAGBIT_PREVFREE) if set indicates that the previous 
 * block is free. When a block is freed, it is merged with adjacent free
 * blocks.
 *
 * On the free list, the first two ULONG words of the block contain links.
 * In addition, there is a pointer at the end of the block, which points
 * to the begining of the block. These links are only valid when the block
 * is free, therefore space needs to be reserved for them. Thus, the minimum
 * block size is 12 bytes (not counting the tag).
 *
 * Blocks larger than nBuddyBlockSize have one free list with a roving 
 * pointer. Blocks smaller than nBuddyBlockSize have an array of free lists.
 * Each of these lists link free blocks of the same size.
 */


#define	ROUND_UP(x,p2)	(((x)+((p2)-1))&(~((p2)-1)))
#define	ROUND_DOWN(x,p2) ((x)&(~((p2)-1)))

const int maxHeaps = 32;

/*
 * The use of structures yields less macros and type casting
 */

typedef struct _Heap* PHEAP;
typedef struct _Heap
{
    ULONG	commitSize;		/* committed size in this heap */
    ULONG	reserveSize;		/* total reserved size */
    ULONG	memBlockCount;		/* number of memory blocks in memBlocks */
    BYTE*	memBlocks[maxHeaps];	/* all non-contiguous heap areas */
    PHEAP	pNextHeap;		/* next heap if this is full */
} HEAP;

typedef struct _BlockTag* PBLOCKTAG;
typedef	struct _BlockTag
{
    ULONG	blockSize;	/* bit 0 this block. bit 1 prev block, if set then free */
    PBLOCKTAG	pNextFree;	/* only exist in free blocks */
    PBLOCKTAG	pPrevFree;
} BLOCKTAG;
/* free blocks are terminated with 'PBLOCKTAG' pointing back to their BLOCKTAG structure */

typedef struct _BuddyLinks* PBUDDYLINK;
typedef struct _BuddyLinks
{
    PBLOCKTAG pNextFree;
    PBLOCKTAG pPrevFree;
} BUDDYLINK;

/*
 * Note the BUDDYLINK is the same as the BLOCKTAG without the blockSize
 * This assumption is made in the code to conserve space
 */

const ULONG lAllocSize = 0x020000;	/* each new block is at least this size */
const ULONG lFreeSize = lAllocSize*2;	/* when this much memory is free return it to OS */
const ULONG minBlockSize = sizeof(BLOCKTAG);
const ULONG blockOverhead = sizeof(PBLOCKTAG);
const ULONG blockAlign = sizeof(ULONG);
const ULONG minAllocSize = minBlockSize+blockOverhead;
const ULONG initialReserveSize = 0x800000;
const ULONG nBuddyBlockSize = 4096;
const ULONG nBuddyTableSize = (nBuddyBlockSize * (sizeof(BUDDYLINK) / blockAlign));

#define	MEM2TAG(ptr)	((PBLOCKTAG)(((BYTE*)(ptr))-sizeof(ULONG)))
#define	TAG2MEM(pBlock)	((void*)(((BYTE*)(pBlock))+sizeof(ULONG)))

#define	TAGBIT_FREE	1	/* this block is free */
#define	TAGBIT_PREVFREE	2	/* previous block is free */
#define	TAGBIT_MASK	3	/* mask for flags in the blocksize */

#define	SIZE(pBlock)		(((pBlock)->blockSize)&(~TAGBIT_MASK))
#define	AVAILSIZE(pBlock)	((((pBlock)->blockSize)&(~TAGBIT_MASK))+sizeof(ULONG))
#define	ISFREE(pBlock)		(((pBlock)->blockSize)&TAGBIT_FREE)
#define	ISPREVFREE(pBlock)	(((pBlock)->blockSize)&TAGBIT_PREVFREE)
#define	NEXT(pBlock)		((PBLOCKTAG)((BYTE*)TAG2MEM(pBlock)+SIZE(pBlock)))

inline void SetBlockBackPtr(PBLOCKTAG pBlock, ULONG size)
{
    *(PBLOCKTAG*)(((BYTE*)pBlock) + size) = pBlock;
}

inline PBLOCKTAG PreviousBlock(PBLOCKTAG pBlock)
{
    return *(PBLOCKTAG*)(((BYTE*)(pBlock)) - blockOverhead);
}

inline PBLOCKTAG FirstHeapBlock(PHEAP pHeap)
{
    return ((PBLOCKTAG)(((BYTE*)pHeap) + sizeof(HEAP)));
}
inline PBLOCKTAG LastHeapBlock(PHEAP pHeap)
{
    return ((PBLOCKTAG)(((BYTE*)pHeap)+pHeap->commitSize - sizeof(ULONG)));
}

inline AddToFreeList(PBLOCKTAG pFreeList, PBLOCKTAG pBlock)
{
    pBlock->pNextFree = pFreeList->pNextFree;
    pBlock->pPrevFree = pFreeList;
    pBlock->pNextFree->pPrevFree = pFreeList->pNextFree = pBlock;
}

inline UnlinkBlock(PBLOCKTAG pBlock)
{
    pBlock->pNextFree->pPrevFree = pBlock->pPrevFree;
    pBlock->pPrevFree->pNextFree = pBlock->pNextFree;
}

class VMem
{
public:
    VMem();
    ~VMem();
    virtual void* Malloc(size_t size);
    virtual void* Realloc(void* pMem, size_t size);
    virtual void Free(void* pMem);
    virtual void GetLock(void);
    virtual void FreeLock(void);
    virtual int IsLocked(void);
    virtual long Release(void);
    virtual long AddRef(void);

    inline BOOL CreateOk(void) { return TRUE; };

protected:
    int Getmem(ULONG size);
    void* Expand(void* pBlock, ULONG size);
    BOOL ResizeHeap(PHEAP pHeap, ULONG newSize);
    inline PBLOCKTAG GetFreeListLink(int index)
    {
	ASSERT(!(index&TAGBIT_MASK));
	return ((PBLOCKTAG) (((BYTE*)m_pBuddyLinks)
		+ ((index) * (sizeof(BUDDYLINK)/blockAlign))
		    - (sizeof(ULONG) + sizeof(BUDDYLINK))));
    }
    inline void CheckRoverAndUnlinkBlock(PBLOCKTAG pBlock)
    {
        if (m_pRover == pBlock)
            m_pRover = m_pRover->pNextFree;
        UnlinkBlock(pBlock);
    }
    inline void MarkBlockInUse(PBLOCKTAG pBlock)
    {
	pBlock->blockSize &= ~TAGBIT_FREE;
	NEXT(pBlock)->blockSize &= ~TAGBIT_PREVFREE;
    }

    /*
     * pointer to an array of doublely linked list of headers 
     * for blocks < nBuddyBlockSize
     */
    PBUDDYLINK		m_pBuddyLinks;

    /* free list for non buddy blocks */
    BLOCKTAG		m_freeList;
    PBLOCKTAG		m_pRover;
    PHEAP		m_pHeaps;
    DWORD		m_dwPageSize;

    long		m_lRefCount;	// number of current users
    CRITICAL_SECTION	m_cs;		// access lock

// #define _VERIFY_FREES
#ifdef _VERIFY_FREES
    bool VerifyPtr(void* ptr);
#endif
#ifdef _DEBUG_MEM
    void WalkHeap(int complete);
    void MemoryUsageMessage(char* str, long x, long y, int c);
    FILE*		m_pLog;
#endif
};

VMem::VMem()
{
    SYSTEM_INFO si;

    GetSystemInfo(&si);
    m_dwPageSize = si.dwPageSize;
    m_pHeaps = NULL;
    m_pBuddyLinks = NULL;
    m_freeList.blockSize = TAGBIT_FREE;
    m_freeList.pNextFree = &m_freeList;
    m_freeList.pPrevFree = &m_freeList;
    m_pRover = &m_freeList;

    m_lRefCount = 1;

    InitializeCriticalSection(&m_cs);
#ifdef _DEBUG_MEM
    m_pLog = 0;
#endif
}

VMem::~VMem()
{
    PHEAP pHeap, pNextHeap;
    int index;

    WALKHEAPTRACE();

    for (pHeap = m_pHeaps; pHeap; pHeap = pNextHeap) {
	pNextHeap = pHeap->pNextHeap;
        for (index = --pHeap->memBlockCount; index >= 0; --index) {
            ULONG size = pHeap->commitSize - (pHeap->memBlocks[index] - (BYTE*)pHeap);
            void* ptr = pHeap->memBlocks[index];

            pHeap->commitSize = pHeap->reserveSize = pHeap->memBlocks[index] - (BYTE*)pHeap;

            VirtualFree(ptr, size, MEM_DECOMMIT);
            VirtualFree(ptr, 0, MEM_RELEASE);
        }
    }
}

void* VMem::Malloc(size_t size)
{
    ULONG allocSize;
    PBLOCKTAG pFreeBlock;
    int loops = 2;

    WALKHEAP();

    if (!size)
        return NULL;

    if (!m_pBuddyLinks)
        Getmem(nBuddyTableSize + sizeof(HEAP) + minBlockSize);

    /*
     * If the size <= nBuddyBlockSize, first check if a free block
     * of that size exists. If not then take the m_pRover. If there are no free
     * blocks > nBuddyBlockSize, scan forward in the buddy list until we find 
     * a free block. If all that fails, get more memory from the OS
     */
    allocSize = (size < minBlockSize) ? minBlockSize : ROUND_UP(size, blockAlign);
    while(loops--) {
	if (allocSize < nBuddyBlockSize) {
	    pFreeBlock = GetFreeListLink(allocSize);
	    if (pFreeBlock->pNextFree != pFreeBlock) {
		pFreeBlock = pFreeBlock->pNextFree;
		MarkBlockInUse(pFreeBlock);
		UnlinkBlock(pFreeBlock);

		return TAG2MEM(pFreeBlock);
	    }

	    /* if m_pRover not empty then must fit */
	    pFreeBlock = m_pRover;
	    if (pFreeBlock == &m_freeList)
		pFreeBlock = pFreeBlock->pNextFree;

	    /* if oversize list is empty, find next larger slot */
	    if (pFreeBlock == &m_freeList) {
		/*
		 * scan the buddy list for an entry.
		 * the end of list marker has ->pNextFree == NULL.
		 */
		for (pFreeBlock = GetFreeListLink(allocSize + blockAlign); 
			pFreeBlock->pNextFree == pFreeBlock;
			    pFreeBlock = (PBLOCKTAG)(((BYTE*)pFreeBlock)+sizeof(BUDDYLINK)))
		    ;

		pFreeBlock = (pFreeBlock->pNextFree) ? pFreeBlock->pNextFree : &m_freeList;
	    }
	}
	else {
	    ULONG saveSize = (pFreeBlock = m_pRover)->blockSize;
	    if (saveSize < allocSize) {
		m_pRover->blockSize = 0xFFFFFFFF; /* mark this to complete the search */
		for (pFreeBlock = pFreeBlock->pNextFree; 
			pFreeBlock->blockSize < allocSize;
			    pFreeBlock = pFreeBlock->pNextFree)
		    ;

		m_pRover->blockSize = saveSize;
		if (m_pRover == pFreeBlock)
		    pFreeBlock = &m_freeList; /* say not found */
	    }
	}

	if (pFreeBlock != &m_freeList) {
	    ULONG freeSize = SIZE(pFreeBlock);
	    if (freeSize - allocSize < minAllocSize) {
		MarkBlockInUse(pFreeBlock);
		CheckRoverAndUnlinkBlock(pFreeBlock);
	    }
	    else {
		/* split the block */
		PBLOCKTAG pNextBlock;
		ULONG rem;

		pFreeBlock->blockSize = allocSize;

		pNextBlock = NEXT(pFreeBlock);
		rem = freeSize - allocSize - sizeof(ULONG);
		pNextBlock->blockSize = rem | TAGBIT_FREE;

		SetBlockBackPtr(pNextBlock, rem);
		if (rem < nBuddyBlockSize) {
		    AddToFreeList(GetFreeListLink(rem), pNextBlock);
		    CheckRoverAndUnlinkBlock(pFreeBlock);
		}
		else {
		    pFreeBlock->pPrevFree->pNextFree = pNextBlock;
		    pNextBlock->pPrevFree = pFreeBlock->pPrevFree;
		    pFreeBlock->pNextFree->pPrevFree = pNextBlock;
		    pNextBlock->pNextFree = pFreeBlock->pNextFree;
		    m_pRover = pNextBlock;
		}
	    }

	    return TAG2MEM(pFreeBlock);
	}
	else {
	    /*
	     * We've gone through this list once already without finding anything, 
	     * allocate some new memory from the heap and try again.
	     */
	    Getmem(size + sizeof(HEAP));
	}
    }

    return NULL;
}

void* VMem::Realloc(void* ptr, size_t size)
{
    WALKHEAP();

    /* if size is zero, free the block. */
    if (!size) {
        Free(ptr);
        return NULL;
    }

    /* if pointer is NULL, do a Malloc(). */
    if (!ptr)
        return Malloc(size);

    /*
     * Grow or shrink the block in place.
     * if the block grows then the next block will be used if free
     */
    if (!Expand(ptr, size)) {
        void* newPtr;
        if ((newPtr = Malloc(size)) != NULL) {
	    ULONG moveSize = SIZE(MEM2TAG(ptr));
	    if (moveSize > size)
		moveSize = size;
            memmove(newPtr, ptr, moveSize);
            Free(ptr);
        }
        return newPtr;
    }
    return ptr;
}

void VMem::Free(void* ptr)
{
    PBLOCKTAG pBlock, pNextBlock;
    ULONG size;

    /* Ignore null pointer. */
    if (!ptr)
        return;

#ifdef _VERIFY_FREES
    if (!VerifyPtr(ptr))
	return;
#endif

    WALKHEAP();

    pBlock = MEM2TAG(ptr);
    /* if previous block is free, add this block to it. */
    if (ISPREVFREE(pBlock)) {
        PBLOCKTAG pPrevBlock = PreviousBlock(pBlock);
        pPrevBlock->blockSize += AVAILSIZE(pBlock);
        pBlock = pPrevBlock;
        CheckRoverAndUnlinkBlock(pBlock);
    }
    else {
        /* cannot merge previous, mark this block free */
        pBlock->blockSize |= TAGBIT_FREE;
    }

    /* if the next physical block is free, merge it with this block. */
    if (ISFREE(pNextBlock = NEXT(pBlock))) {
        pBlock->blockSize += AVAILSIZE(pNextBlock);
        CheckRoverAndUnlinkBlock(pNextBlock);
    }

    pNextBlock = NEXT(pBlock);
    pNextBlock->blockSize |= TAGBIT_PREVFREE;

    /* reinsert block to free list */
    size = SIZE(pBlock);
    AddToFreeList((size < nBuddyBlockSize) ? GetFreeListLink(size) : m_pRover->pNextFree, pBlock);
    SetBlockBackPtr(pBlock, size);

    /* Can this heap shrink */
    if (pNextBlock->blockSize == TAGBIT_PREVFREE && pBlock->blockSize-minBlockSize >= lFreeSize) {
	PHEAP pHeap;
	ULONG diffSize = ROUND_DOWN(pBlock->blockSize-minBlockSize, lFreeSize);
	for (pHeap = m_pHeaps; pHeap; pHeap = pHeap->pNextHeap) {
	    if (LastHeapBlock(pHeap) == pNextBlock) {
		/* this heap can shrink */
		ULONG newSize = pHeap->commitSize - diffSize;
		ResizeHeap(pHeap, newSize);
		while ((BYTE*)pHeap + newSize <= pHeap->memBlocks[pHeap->memBlockCount - 1]) {
		    /* give block back to OS */
		    size = pHeap->commitSize - (pHeap->memBlocks[--pHeap->memBlockCount] - (BYTE*)pHeap);
		    VirtualFree(pHeap->memBlocks[pHeap->memBlockCount], size, MEM_DECOMMIT);
		    VirtualFree(pHeap->memBlocks[pHeap->memBlockCount], 0, MEM_RELEASE);
		    pHeap->commitSize = pHeap->reserveSize = pHeap->memBlocks[pHeap->memBlockCount] - (BYTE*)pHeap;
		}

		VirtualFree(pHeap->memBlocks[pHeap->memBlockCount - 1] + newSize, pHeap->commitSize - newSize, MEM_DECOMMIT);
		pHeap->commitSize = newSize;
		break;
	    }
	}
    }
}

BOOL VMem::ResizeHeap(PHEAP pHeap, ULONG newSize)
{
    ULONG diffSize;
    PBLOCKTAG pBlock;

    newSize = ROUND_DOWN(newSize, m_dwPageSize);
    pBlock = LastHeapBlock(pHeap);
    if (newSize < pHeap->commitSize) {
        if (!ISPREVFREE(pBlock))
            return FALSE;

	pBlock = PreviousBlock(pBlock);
        diffSize = pHeap->commitSize - newSize;

        if (SIZE(pBlock) - minBlockSize < diffSize)
            return FALSE;

        pBlock->blockSize -= diffSize;
        SetBlockBackPtr(pBlock, SIZE(pBlock));
        NEXT(pBlock)->blockSize = TAGBIT_PREVFREE;

        if (SIZE(pBlock) < nBuddyBlockSize) {
	    /* reinsert block to correct free list */
            UnlinkBlock(pBlock);
            AddToFreeList(GetFreeListLink(SIZE(pBlock)), pBlock);
        }
    }
    else {
        diffSize = newSize - pHeap->commitSize;
        pBlock->blockSize += diffSize - sizeof(ULONG);
        NEXT(pBlock)->blockSize = 0;
        Free(TAG2MEM(pBlock));
        pHeap->commitSize += diffSize;
    }
    return TRUE;
}


BOOL VMem::Getmem(ULONG minSize)
{
    PBLOCKTAG pBlock;
    PHEAP pHeap;
    void* pMem;
    ULONG tableSize, innerSize;
    ULONG commitSize, virtualSize, allocMinSize = ROUND_UP(minSize, m_dwPageSize);

    /* find a heap that has some reserved memory available */
    for (pHeap = m_pHeaps; pHeap; pHeap = pHeap->pNextHeap) {
        if (pHeap->reserveSize - pHeap->commitSize > allocMinSize) {
            ULONG newSize = pHeap->reserveSize;
	    commitSize = pHeap->commitSize + ROUND_UP(allocMinSize, lAllocSize);
            if (newSize > commitSize)
		newSize = commitSize;
            if (VirtualAlloc((BYTE*)pHeap + pHeap->commitSize, newSize - pHeap->commitSize, MEM_COMMIT, PAGE_READWRITE)) {
                return ResizeHeap(pHeap, newSize);
            }
            /* otherwise, try to commit m_dwPageSize */
            else if(VirtualAlloc((BYTE*)pHeap + pHeap->commitSize, m_dwPageSize, MEM_COMMIT, PAGE_READWRITE)) {
                return ResizeHeap(pHeap, pHeap->commitSize+m_dwPageSize);
            }
            /* Out of memory!!! */
            else
		return FALSE;
        }
    }

    /* allocate more memory */
    virtualSize = (allocMinSize < initialReserveSize)
	? initialReserveSize
	    : ROUND_UP(allocMinSize, initialReserveSize);

    pMem = VirtualAlloc(NULL, virtualSize, MEM_RESERVE, PAGE_NOACCESS);
    if (!pMem)
        return FALSE;

    commitSize = ROUND_UP(allocMinSize + m_dwPageSize, lAllocSize);
    for (pHeap = m_pHeaps; pHeap; pHeap = pHeap->pNextHeap) {
        if ((BYTE*)pHeap + pHeap->reserveSize == pMem && pHeap->memBlockCount < maxHeaps) {
            ULONG rem = pHeap->reserveSize - pHeap->commitSize;
            if (rem) {
                if (!VirtualAlloc((BYTE*)pHeap + pHeap->commitSize, rem, MEM_COMMIT, PAGE_READWRITE))
                    return FALSE;

                ResizeHeap(pHeap, pHeap->reserveSize);
            }

            if (!VirtualAlloc(pMem, commitSize - rem, MEM_COMMIT, PAGE_READWRITE))
                return FALSE;
	    else {
                pHeap->memBlocks[pHeap->memBlockCount++] = (BYTE*)pMem;
                pHeap->reserveSize += virtualSize;
                return ResizeHeap(pHeap, pHeap->commitSize + commitSize - rem);
            }
        }
    }

    if (!VirtualAlloc(pMem, commitSize, MEM_COMMIT, PAGE_READWRITE)) {
        VirtualFree(pMem, 0, MEM_RELEASE);
        return FALSE;
    }

    pHeap = (PHEAP)pMem;

    /* Create the header for the heap */
    pHeap->memBlockCount = 1;
    pHeap->memBlocks[0] = (BYTE*)pMem;
    pHeap->commitSize = commitSize;
    pHeap->reserveSize = virtualSize;

    /* Link it in */
    pHeap->pNextHeap = m_pHeaps;
    m_pHeaps = pHeap;

    /* The first dummy block */
    pBlock = FirstHeapBlock(pHeap);
    pBlock->blockSize = 0;
    pBlock = NEXT(pBlock);

    tableSize = 0;
    /* Allocate the buddy blocks */
    if (!m_pBuddyLinks) {
	int index;
	PBLOCKTAG pTerm;

        tableSize = ROUND_UP(nBuddyTableSize, blockAlign);
        m_pBuddyLinks = (PBUDDYLINK)TAG2MEM(pBlock);
        pBlock->blockSize = tableSize;
        pBlock = NEXT(pBlock);

	for (index = minBlockSize; index < nBuddyBlockSize; index += blockAlign) {
	    PBLOCKTAG p = GetFreeListLink(index);
	    p->pNextFree = p->pPrevFree = p;
	}
	pTerm = GetFreeListLink(nBuddyBlockSize);
	pTerm->pNextFree = pTerm->pPrevFree = NULL;

        tableSize += sizeof(ULONG);
    }

    /* Inner free block size is
     *	commitSize - sizeof(HEAP) - (tableSize if just created)
     *    - (2 dummy zero-length blocks + free block header) 
     */                  
    innerSize = commitSize - sizeof(HEAP) - tableSize - (3 * sizeof(ULONG));
    pBlock->blockSize = innerSize | TAGBIT_FREE; /* previous block is NOT free */

    /* The last dummy block */
    NEXT(pBlock)->blockSize = TAGBIT_PREVFREE; /* previous block is free */

    AddToFreeList((innerSize < nBuddyBlockSize) ?  GetFreeListLink(innerSize) : m_pRover, pBlock);
    SetBlockBackPtr(pBlock, innerSize);
    return TRUE;
}

void* VMem::Expand(void* ptr, ULONG size)
{
    PBLOCKTAG pBlock, pNextBlock;
    ULONG allocSize, availSize;

    pBlock = MEM2TAG(ptr);
    availSize = SIZE(pBlock);
    allocSize = (size < minBlockSize) ? minBlockSize : ROUND_UP(size, blockAlign);
    if (availSize == allocSize)
	return ptr;

    pNextBlock = NEXT(pBlock);
    if (ISFREE(pNextBlock))
        availSize += AVAILSIZE(pNextBlock);

    if (availSize >= allocSize) {
        PBLOCKTAG oldPrevFree = NULL;
        /* Can grow/shrink in place. If the next block is free merge it */
        if (ISFREE(pNextBlock)) {
            if (SIZE(pNextBlock) >= nBuddyBlockSize)
                oldPrevFree = pNextBlock->pPrevFree;

            CheckRoverAndUnlinkBlock(pNextBlock);
            NEXT(pNextBlock)->blockSize &= ~TAGBIT_PREVFREE;
            pBlock->blockSize = availSize | (pBlock->blockSize & TAGBIT_PREVFREE);
        }

	/* if the block is being shrunk, convert the remainder of the block into a new free block. */
        if (availSize - allocSize >= minAllocSize) {
            /* shrink back to requested size */
            ULONG rem = availSize - allocSize - sizeof(ULONG);
            pBlock->blockSize = allocSize | (pBlock->blockSize & TAGBIT_PREVFREE);
            pNextBlock = NEXT(pBlock);
            pNextBlock->blockSize = rem | TAGBIT_FREE;
            NEXT(pNextBlock)->blockSize |= TAGBIT_PREVFREE;

            /* reinsert block to free list */
            AddToFreeList((rem < nBuddyBlockSize)
		    ? GetFreeListLink(rem)
		    : (oldPrevFree ? oldPrevFree : m_pRover->pNextFree), pNextBlock);
            SetBlockBackPtr(pNextBlock, rem);
        }

	return ptr;
    }
    return NULL;
}

#ifdef _VERIFY_FREES
bool VMem::VerifyPtr(void* ptr)
{
    PHEAP pHeap;

    for (pHeap = m_pHeaps; pHeap; pHeap = pHeap->pNextHeap) {
	char* pLow = (char*)pHeap;
	char* pHigh = pLow + pHeap->commitSize;
	char* pTest = (char*)ptr;
	if (pLow < pTest && pTest < pHigh)
	    return true;
    }
//    DebugBreak();
    return false;
}
#endif

#else  /* _USE_EXERCISE_19 */

const long lAllocStart = 0x00020000; /* start at 128K */
const long minBlockSize = sizeof(void*)*2;
const long sizeofTag = sizeof(long);
const long blockOverhead = sizeofTag*2;
const long minAllocSize = minBlockSize+blockOverhead;
#ifdef _USE_BUDDY_BLOCKS
const long lSmallBlockSize = 1024;
const size_t nListEntries = ((lSmallBlockSize-minAllocSize)/sizeof(long));

inline size_t CalcEntry(size_t size)
{
    ASSERT((size&(sizeof(long)-1)) == 0);
    return ((size - minAllocSize) / sizeof(long));
}
#endif

typedef BYTE* PBLOCK;	/* pointer to a memory block */

/*
 * Macros for accessing hidden fields in a memory block:
 *
 * SIZE	    size of this block (tag bit 0 is 1 if block is allocated)
 * PSIZE    size of previous physical block
 */

#define SIZE(block)	(*(ULONG*)(((PBLOCK)(block))-sizeofTag))
#define PSIZE(block)	(*(ULONG*)(((PBLOCK)(block))-(blockOverhead)))
inline void SetTags(PBLOCK block, long size)
{
    SIZE(block) = size;
    PSIZE(block+(size&~1)) = size;
}

/*
 * Free list pointers
 * PREV	pointer to previous block
 * NEXT	pointer to next block
 */

#define PREV(block)	(*(PBLOCK*)(block))
#define NEXT(block)	(*(PBLOCK*)((block)+sizeof(PBLOCK)))
inline void SetLink(PBLOCK block, PBLOCK prev, PBLOCK next)
{
    PREV(block) = prev;
    NEXT(block) = next;
}
inline void Unlink(PBLOCK p)
{
    PBLOCK next = NEXT(p);
    PBLOCK prev = PREV(p);
    NEXT(prev) = next;
    PREV(next) = prev;
}
#ifndef _USE_BUDDY_BLOCKS
inline void AddToFreeList(PBLOCK block, PBLOCK pInList)
{
    PBLOCK next = NEXT(pInList);
    NEXT(pInList) = block;
    SetLink(block, pInList, next);
    PREV(next) = block;
}
#endif

/* Macro for rounding up to the next sizeof(long) */
#define ROUND_UP(n)	(((ULONG)(n)+sizeof(long)-1)&~(sizeof(long)-1))
#define ROUND_UP64K(n)	(((ULONG)(n)+0x10000-1)&~(0x10000-1))
#define ROUND_DOWN(n)	((ULONG)(n)&~(sizeof(long)-1))

/*
 * HeapRec - a list of all non-contiguous heap areas
 *
 * Each record in this array contains information about a non-contiguous heap area.
 */

const int maxHeaps = 32; /* 64 was overkill */
const long lAllocMax   = 0x80000000; /* max size of allocation */

#ifdef _USE_BUDDY_BLOCKS
typedef struct _FreeListEntry
{
    BYTE    Dummy[minAllocSize];	// dummy free block
} FREE_LIST_ENTRY, *PFREE_LIST_ENTRY;
#endif

#ifndef _USE_BUDDY_BLOCKS
#define USE_BIGBLOCK_ALLOC
#endif
/*
 * performance tuning
 * Use VirtualAlloc() for blocks bigger than nMaxHeapAllocSize since
 * Windows 95/98/Me have heap managers that are designed for memory 
 * blocks smaller than four megabytes.
 */

#ifdef USE_BIGBLOCK_ALLOC
const int nMaxHeapAllocSize = (1024*512);  /* don't allocate anything larger than this from the heap */
#endif

typedef struct _HeapRec
{
    PBLOCK	base;	/* base of heap area */
    ULONG	len;	/* size of heap area */
#ifdef USE_BIGBLOCK_ALLOC
    BOOL	bBigBlock;  /* was allocate using VirtualAlloc */
#endif
} HeapRec;

class VMem
{
public:
    VMem();
    ~VMem();
    virtual void* Malloc(size_t size);
    virtual void* Realloc(void* pMem, size_t size);
    virtual void Free(void* pMem);
    virtual void GetLock(void);
    virtual void FreeLock(void);
    virtual int IsLocked(void);
    virtual long Release(void);
    virtual long AddRef(void);

    inline BOOL CreateOk(void)
    {
#ifdef _USE_BUDDY_BLOCKS
	return TRUE;
#else
	return m_hHeap != NULL;
#endif
    };

    void ReInit(void);

protected:
    void Init(void);
    int Getmem(size_t size);

    int HeapAdd(void* ptr, size_t size
#ifdef USE_BIGBLOCK_ALLOC
	, BOOL bBigBlock
#endif
    );

    void* Expand(void* block, size_t size);

#ifdef _USE_BUDDY_BLOCKS
    inline PBLOCK GetFreeListLink(int index)
    {
	if (index >= nListEntries)
	    index = nListEntries-1;
	return &m_FreeList[index].Dummy[sizeofTag];
    }
    inline PBLOCK GetOverSizeFreeList(void)
    {
	return &m_FreeList[nListEntries-1].Dummy[sizeofTag];
    }
    inline PBLOCK GetEOLFreeList(void)
    {
	return &m_FreeList[nListEntries].Dummy[sizeofTag];
    }

    void AddToFreeList(PBLOCK block, size_t size)
    {
	PBLOCK pFreeList = GetFreeListLink(CalcEntry(size));
	PBLOCK next = NEXT(pFreeList);
	NEXT(pFreeList) = block;
	SetLink(block, pFreeList, next);
	PREV(next) = block;
    }
#endif
    inline size_t CalcAllocSize(size_t size)
    {
	/*
	 * Adjust the real size of the block to be a multiple of sizeof(long), and add
	 * the overhead for the boundary tags.  Disallow negative or zero sizes.
	 */
	return (size < minBlockSize) ? minAllocSize : (size_t)ROUND_UP(size) + blockOverhead;
    }

#ifdef _USE_BUDDY_BLOCKS
    FREE_LIST_ENTRY	m_FreeList[nListEntries+1];	// free list with dummy end of list entry as well
#else
    HANDLE		m_hHeap;		    // memory heap for this script
    char		m_FreeDummy[minAllocSize];  // dummy free block
    PBLOCK		m_pFreeList;		    // pointer to first block on free list
#endif
    PBLOCK		m_pRover;		    // roving pointer into the free list
    HeapRec		m_heaps[maxHeaps];	    // list of all non-contiguous heap areas 
    int			m_nHeaps;		    // no. of heaps in m_heaps 
    long		m_lAllocSize;		    // current alloc size
    long		m_lRefCount;		    // number of current users
    CRITICAL_SECTION	m_cs;			    // access lock

#ifdef _DEBUG_MEM
    void WalkHeap(int complete);
    void MemoryUsageMessage(char *str, long x, long y, int c);
    FILE*		m_pLog;
#endif
};

VMem::VMem()
{
    m_lRefCount = 1;
#ifndef _USE_BUDDY_BLOCKS
    BOOL bRet = (NULL != (m_hHeap = HeapCreate(HEAP_NO_SERIALIZE,
				lAllocStart,	/* initial size of heap */
				0)));		/* no upper limit on size of heap */
    ASSERT(bRet);
#endif

    InitializeCriticalSection(&m_cs);
#ifdef _DEBUG_MEM
    m_pLog = 0;
#endif

    Init();
}

VMem::~VMem(void)
{
#ifndef _USE_BUDDY_BLOCKS
    ASSERT(HeapValidate(m_hHeap, HEAP_NO_SERIALIZE, NULL));
#endif
    WALKHEAPTRACE();

    DeleteCriticalSection(&m_cs);
#ifdef _USE_BUDDY_BLOCKS
    for(int index = 0; index < m_nHeaps; ++index) {
	VirtualFree(m_heaps[index].base, 0, MEM_RELEASE);
    }
#else /* !_USE_BUDDY_BLOCKS */
#ifdef USE_BIGBLOCK_ALLOC
    for(int index = 0; index < m_nHeaps; ++index) {
	if (m_heaps[index].bBigBlock) {
	    VirtualFree(m_heaps[index].base, 0, MEM_RELEASE);
	}
    }
#endif
    BOOL bRet = HeapDestroy(m_hHeap);
    ASSERT(bRet);
#endif /* _USE_BUDDY_BLOCKS */
}

void VMem::ReInit(void)
{
    for(int index = 0; index < m_nHeaps; ++index) {
#ifdef _USE_BUDDY_BLOCKS
	VirtualFree(m_heaps[index].base, 0, MEM_RELEASE);
#else
#ifdef USE_BIGBLOCK_ALLOC
	if (m_heaps[index].bBigBlock) {
	    VirtualFree(m_heaps[index].base, 0, MEM_RELEASE);
	}
	else
#endif
	    HeapFree(m_hHeap, HEAP_NO_SERIALIZE, m_heaps[index].base);
#endif /* _USE_BUDDY_BLOCKS */
    }

    Init();
}

void VMem::Init(void)
{
#ifdef _USE_BUDDY_BLOCKS
    PBLOCK pFreeList;
    /*
     * Initialize the free list by placing a dummy zero-length block on it.
     * Set the end of list marker.
     * Set the number of non-contiguous heaps to zero.
     * Set the next allocation size.
     */
    for (int index = 0; index < nListEntries; ++index) {
	pFreeList = GetFreeListLink(index);
	SIZE(pFreeList) = PSIZE(pFreeList+minAllocSize) = 0;
	PREV(pFreeList) = NEXT(pFreeList) = pFreeList;
    }
    pFreeList = GetEOLFreeList();
    SIZE(pFreeList) = PSIZE(pFreeList+minAllocSize) = 0;
    PREV(pFreeList) = NEXT(pFreeList) = NULL;
    m_pRover = GetOverSizeFreeList();
#else
    /*
     * Initialize the free list by placing a dummy zero-length block on it.
     * Set the number of non-contiguous heaps to zero.
     */
    m_pFreeList = m_pRover = (PBLOCK)(&m_FreeDummy[sizeofTag]);
    PSIZE(m_pFreeList+minAllocSize) = SIZE(m_pFreeList) = 0;
    PREV(m_pFreeList) = NEXT(m_pFreeList) = m_pFreeList;
#endif

    m_nHeaps = 0;
    m_lAllocSize = lAllocStart;
}

void* VMem::Malloc(size_t size)
{
    WALKHEAP();

    PBLOCK ptr;
    size_t lsize, rem;
    /*
     * Disallow negative or zero sizes.
     */
    size_t realsize = CalcAllocSize(size);
    if((int)realsize < minAllocSize || size == 0)
	return NULL;

#ifdef _USE_BUDDY_BLOCKS
    /*
     * Check the free list of small blocks if this is free use it
     * Otherwise check the rover if it has no blocks then
     * Scan the free list entries use the first free block
     * split the block if needed, stop at end of list marker
     */
    {
	int index = CalcEntry(realsize);
	if (index < nListEntries-1) {
	    ptr = GetFreeListLink(index);
	    lsize = SIZE(ptr);
	    if (lsize >= realsize) {
		rem = lsize - realsize;
		if(rem < minAllocSize) {
		    /* Unlink the block from the free list. */
		    Unlink(ptr);
		}
		else {
		    /*
		     * split the block
		     * The remainder is big enough to split off into a new block.
		     * Use the end of the block, resize the beginning of the block
		     * no need to change the free list.
		     */
		    SetTags(ptr, rem);
		    ptr += SIZE(ptr);
		    lsize = realsize;
		}
		SetTags(ptr, lsize | 1);
		return ptr;
	    }
	    ptr = m_pRover;
	    lsize = SIZE(ptr);
	    if (lsize >= realsize) {
		rem = lsize - realsize;
		if(rem < minAllocSize) {
		    /* Unlink the block from the free list. */
		    Unlink(ptr);
		}
		else {
		    /*
		     * split the block
		     * The remainder is big enough to split off into a new block.
		     * Use the end of the block, resize the beginning of the block
		     * no need to change the free list.
		     */
		    SetTags(ptr, rem);
		    ptr += SIZE(ptr);
		    lsize = realsize;
		}
		SetTags(ptr, lsize | 1);
		return ptr;
	    }
	    ptr = GetFreeListLink(index+1);
	    while (NEXT(ptr)) {
		lsize = SIZE(ptr);
		if (lsize >= realsize) {
		    size_t rem = lsize - realsize;
		    if(rem < minAllocSize) {
			/* Unlink the block from the free list. */
			Unlink(ptr);
		    }
		    else {
			/*
			 * split the block
			 * The remainder is big enough to split off into a new block.
			 * Use the end of the block, resize the beginning of the block
			 * no need to change the free list.
			 */
			SetTags(ptr, rem);
			ptr += SIZE(ptr);
			lsize = realsize;
		    }
		    SetTags(ptr, lsize | 1);
		    return ptr;
		}
		ptr += sizeof(FREE_LIST_ENTRY);
	    }
	}
    }
#endif

    /*
     * Start searching the free list at the rover.  If we arrive back at rover without
     * finding anything, allocate some memory from the heap and try again.
     */
    ptr = m_pRover;	/* start searching at rover */
    int loops = 2;	/* allow two times through the loop  */
    for(;;) {
	lsize = SIZE(ptr);
	ASSERT((lsize&1)==0);
	/* is block big enough? */
	if(lsize >= realsize) {	
	    /* if the remainder is too small, don't bother splitting the block. */
	    rem = lsize - realsize;
	    if(rem < minAllocSize) {
		if(m_pRover == ptr)
		    m_pRover = NEXT(ptr);

		/* Unlink the block from the free list. */
		Unlink(ptr);
	    }
	    else {
		/*
		 * split the block
		 * The remainder is big enough to split off into a new block.
		 * Use the end of the block, resize the beginning of the block
		 * no need to change the free list.
		 */
		SetTags(ptr, rem);
		ptr += SIZE(ptr);
		lsize = realsize;
	    }
	    /* Set the boundary tags to mark it as allocated. */
	    SetTags(ptr, lsize | 1);
	    return ((void *)ptr);
	}

	/*
	 * This block was unsuitable.  If we've gone through this list once already without
	 * finding anything, allocate some new memory from the heap and try again.
	 */
	ptr = NEXT(ptr);
	if(ptr == m_pRover) {
	    if(!(loops-- && Getmem(realsize))) {
		return NULL;
	    }
	    ptr = m_pRover;
	}
    }
}

void* VMem::Realloc(void* block, size_t size)
{
    WALKHEAP();

    /* if size is zero, free the block. */
    if(size == 0) {
	Free(block);
	return (NULL);
    }

    /* if block pointer is NULL, do a Malloc(). */
    if(block == NULL)
	return Malloc(size);

    /*
     * Grow or shrink the block in place.
     * if the block grows then the next block will be used if free
     */
    if(Expand(block, size) != NULL)
	return block;

    size_t realsize = CalcAllocSize(size);
    if((int)realsize < minAllocSize)
	return NULL;

    /*
     * see if the previous block is free, and is it big enough to cover the new size
     * if merged with the current block.
     */
    PBLOCK ptr = (PBLOCK)block;
    size_t cursize = SIZE(ptr) & ~1;
    size_t psize = PSIZE(ptr);
    if((psize&1) == 0 && (psize + cursize) >= realsize) {
	PBLOCK prev = ptr - psize;
	if(m_pRover == prev)
	    m_pRover = NEXT(prev);

	/* Unlink the next block from the free list. */
	Unlink(prev);

	/* Copy contents of old block to new location, make it the current block. */
	memmove(prev, ptr, cursize);
	cursize += psize;	/* combine sizes */
	ptr = prev;

	size_t rem = cursize - realsize;
	if(rem >= minAllocSize) {
	    /*
	     * The remainder is big enough to be a new block.  Set boundary
	     * tags for the resized block and the new block.
	     */
	    prev = ptr + realsize;
	    /*
	     * add the new block to the free list.
	     * next block cannot be free
	     */
	    SetTags(prev, rem);
#ifdef _USE_BUDDY_BLOCKS
	    AddToFreeList(prev, rem);
#else
	    AddToFreeList(prev, m_pFreeList);
#endif
	    cursize = realsize;
        }
	/* Set the boundary tags to mark it as allocated. */
	SetTags(ptr, cursize | 1);
        return ((void *)ptr);
    }

    /* Allocate a new block, copy the old to the new, and free the old. */
    if((ptr = (PBLOCK)Malloc(size)) != NULL) {
	memmove(ptr, block, cursize-blockOverhead);
	Free(block);
    }
    return ((void *)ptr);
}

void VMem::Free(void* p)
{
    WALKHEAP();

    /* Ignore null pointer. */
    if(p == NULL)
	return;

    PBLOCK ptr = (PBLOCK)p;

    /* Check for attempt to free a block that's already free. */
    size_t size = SIZE(ptr);
    if((size&1) == 0) {
	MEMODSlx("Attempt to free previously freed block", (long)p);
	return;
    }
    size &= ~1;	/* remove allocated tag */

    /* if previous block is free, add this block to it. */
#ifndef _USE_BUDDY_BLOCKS
    int linked = FALSE;
#endif
    size_t psize = PSIZE(ptr);
    if((psize&1) == 0) {
	ptr -= psize;	/* point to previous block */
	size += psize;	/* merge the sizes of the two blocks */
#ifdef _USE_BUDDY_BLOCKS
	Unlink(ptr);
#else
	linked = TRUE;	/* it's already on the free list */
#endif
    }

    /* if the next physical block is free, merge it with this block. */
    PBLOCK next = ptr + size;	/* point to next physical block */
    size_t nsize = SIZE(next);
    if((nsize&1) == 0) {
	/* block is free move rover if needed */
	if(m_pRover == next)
	    m_pRover = NEXT(next);

	/* unlink the next block from the free list. */
	Unlink(next);

	/* merge the sizes of this block and the next block. */
	size += nsize;
    }

    /* Set the boundary tags for the block; */
    SetTags(ptr, size);

    /* Link the block to the head of the free list. */
#ifdef _USE_BUDDY_BLOCKS
	AddToFreeList(ptr, size);
#else
    if(!linked) {
	AddToFreeList(ptr, m_pFreeList);
    }
#endif
}

int VMem::Getmem(size_t requestSize)
{   /* returns -1 is successful 0 if not */
#ifdef USE_BIGBLOCK_ALLOC
    BOOL bBigBlock;
#endif
    void *ptr;

    /* Round up size to next multiple of 64K. */
    size_t size = (size_t)ROUND_UP64K(requestSize);

    /*
     * if the size requested is smaller than our current allocation size
     * adjust up
     */
    if(size < (unsigned long)m_lAllocSize)
	size = m_lAllocSize;

    /* Update the size to allocate on the next request */
    if(m_lAllocSize != lAllocMax)
	m_lAllocSize <<= 2;

#ifndef _USE_BUDDY_BLOCKS
    if(m_nHeaps != 0
#ifdef USE_BIGBLOCK_ALLOC
	&& !m_heaps[m_nHeaps-1].bBigBlock
#endif
		    ) {
	/* Expand the last allocated heap */
	ptr = HeapReAlloc(m_hHeap, HEAP_REALLOC_IN_PLACE_ONLY|HEAP_NO_SERIALIZE,
		m_heaps[m_nHeaps-1].base,
		m_heaps[m_nHeaps-1].len + size);
	if(ptr != 0) {
	    HeapAdd(((char*)ptr) + m_heaps[m_nHeaps-1].len, size
#ifdef USE_BIGBLOCK_ALLOC
		, FALSE
#endif
		);
	    return -1;
	}
    }
#endif /* _USE_BUDDY_BLOCKS */

    /*
     * if we didn't expand a block to cover the requested size
     * allocate a new Heap
     * the size of this block must include the additional dummy tags at either end
     * the above ROUND_UP64K may not have added any memory to include this.
     */
    if(size == requestSize)
	size = (size_t)ROUND_UP64K(requestSize+(blockOverhead));

Restart:
#ifdef _USE_BUDDY_BLOCKS
    ptr = VirtualAlloc(NULL, size, MEM_COMMIT, PAGE_READWRITE);
#else
#ifdef USE_BIGBLOCK_ALLOC
    bBigBlock = FALSE;
    if (size >= nMaxHeapAllocSize) {
	bBigBlock = TRUE;
	ptr = VirtualAlloc(NULL, size, MEM_COMMIT, PAGE_READWRITE);
    }
    else
#endif
    ptr = HeapAlloc(m_hHeap, HEAP_NO_SERIALIZE, size);
#endif /* _USE_BUDDY_BLOCKS */

    if (!ptr) {
	/* try to allocate a smaller chunk */
	size >>= 1;
	if(size > requestSize)
	    goto Restart;
    }

    if(ptr == 0) {
	MEMODSlx("HeapAlloc failed on size!!!", size);
	return 0;
    }

#ifdef _USE_BUDDY_BLOCKS
    if (HeapAdd(ptr, size)) {
	VirtualFree(ptr, 0, MEM_RELEASE);
	return 0;
    }
#else
#ifdef USE_BIGBLOCK_ALLOC
    if (HeapAdd(ptr, size, bBigBlock)) {
	if (bBigBlock) {
	    VirtualFree(ptr, 0, MEM_RELEASE);
	}
    }
#else
    HeapAdd(ptr, size);
#endif
#endif /* _USE_BUDDY_BLOCKS */
    return -1;
}

int VMem::HeapAdd(void* p, size_t size
#ifdef USE_BIGBLOCK_ALLOC
    , BOOL bBigBlock
#endif
    )
{   /* if the block can be succesfully added to the heap, returns 0; otherwise -1. */
    int index;

    /* Check size, then round size down to next long word boundary. */
    if(size < minAllocSize)
	return -1;

    size = (size_t)ROUND_DOWN(size);
    PBLOCK ptr = (PBLOCK)p;

#ifdef USE_BIGBLOCK_ALLOC
    if (!bBigBlock) {
#endif
	/*
	 * Search for another heap area that's contiguous with the bottom of this new area.
	 * (It should be extremely unusual to find one that's contiguous with the top).
	 */
	for(index = 0; index < m_nHeaps; ++index) {
	    if(ptr == m_heaps[index].base + (int)m_heaps[index].len) {
		/*
		 * The new block is contiguous with a previously allocated heap area.  Add its
		 * length to that of the previous heap.  Merge it with the the dummy end-of-heap
		 * area marker of the previous heap.
		 */
		m_heaps[index].len += size;
		break;
	    }
	}
#ifdef USE_BIGBLOCK_ALLOC
    }
    else {
	index = m_nHeaps;
    }
#endif

    if(index == m_nHeaps) {
	/* The new block is not contiguous, or is BigBlock.  Add it to the heap list. */
	if(m_nHeaps == maxHeaps) {
	    return -1;	/* too many non-contiguous heaps */
	}
	m_heaps[m_nHeaps].base = ptr;
	m_heaps[m_nHeaps].len = size;
#ifdef USE_BIGBLOCK_ALLOC
	m_heaps[m_nHeaps].bBigBlock = bBigBlock;
#endif
	m_nHeaps++;

	/*
	 * Reserve the first LONG in the block for the ending boundary tag of a dummy
	 * block at the start of the heap area.
	 */
	size -= blockOverhead;
	ptr += blockOverhead;
	PSIZE(ptr) = 1;	/* mark the dummy previous block as allocated */
    }

    /*
     * Convert the heap to one large block.  Set up its boundary tags, and those of
     * marker block after it.  The marker block before the heap will already have
     * been set up if this heap is not contiguous with the end of another heap.
     */
    SetTags(ptr, size | 1);
    PBLOCK next = ptr + size;	/* point to dummy end block */
    SIZE(next) = 1;	/* mark the dummy end block as allocated */

    /*
     * Link the block to the start of the free list by calling free().
     * This will merge the block with any adjacent free blocks.
     */
    Free(ptr);
    return 0;
}

void* VMem::Expand(void* block, size_t size)
{
    /*
     * Disallow negative or zero sizes.
     */
    size_t realsize = CalcAllocSize(size);
    if((int)realsize < minAllocSize || size == 0)
	return NULL;

    PBLOCK ptr = (PBLOCK)block; 

    /* if the current size is the same as requested, do nothing. */
    size_t cursize = SIZE(ptr) & ~1;
    if(cursize == realsize) {
	return block;
    }

    /* if the block is being shrunk, convert the remainder of the block into a new free block. */
    if(realsize <= cursize) {
	size_t nextsize = cursize - realsize;	/* size of new remainder block */
	if(nextsize >= minAllocSize) {
	    /*
	     * Split the block
	     * Set boundary tags for the resized block and the new block.
	     */
	    SetTags(ptr, realsize | 1);
	    ptr += realsize;

	    /*
	     * add the new block to the free list.
	     * call Free to merge this block with next block if free
	     */
	    SetTags(ptr, nextsize | 1);
	    Free(ptr);
	}

	return block;
    }

    PBLOCK next = ptr + cursize;
    size_t nextsize = SIZE(next);

    /* Check the next block for consistency.*/
    if((nextsize&1) == 0 && (nextsize + cursize) >= realsize) {
	/*
	 * The next block is free and big enough.  Add the part that's needed
	 * to our block, and split the remainder off into a new block.
	 */
	if(m_pRover == next)
	    m_pRover = NEXT(next);

	/* Unlink the next block from the free list. */
	Unlink(next);
	cursize += nextsize;	/* combine sizes */

	size_t rem = cursize - realsize;	/* size of remainder */
	if(rem >= minAllocSize) {
	    /*
	     * The remainder is big enough to be a new block.
	     * Set boundary tags for the resized block and the new block.
	     */
	    next = ptr + realsize;
	    /*
	     * add the new block to the free list.
	     * next block cannot be free
	     */
	    SetTags(next, rem);
#ifdef _USE_BUDDY_BLOCKS
	    AddToFreeList(next, rem);
#else
	    AddToFreeList(next, m_pFreeList);
#endif
	    cursize = realsize;
        }
	/* Set the boundary tags to mark it as allocated. */
	SetTags(ptr, cursize | 1);
	return ((void *)ptr);
    }
    return NULL;
}

#endif /* _USE_EXERCISE_19 */

#ifdef _DEBUG_MEM
#define LOG_FILENAME ".\\MemLog.txt"

void VMem::MemoryUsageMessage(char* str, long x, long y, int c)
{
    char szBuffer[512];
    if(str) {
	if(!m_pLog)
	    m_pLog = fopen(LOG_FILENAME, "w");
	sprintf(szBuffer, str, x, y, c);
	fputs(szBuffer, m_pLog);
    }
    else {
	if(m_pLog) {
	    fflush(m_pLog);
	    fclose(m_pLog);
	    m_pLog = 0;
	}
    }
}

#ifdef _USE_EXERCISE_19
void VMem::WalkHeap(int complete)
{
    if(complete && m_pHeaps) {
	PHEAP pHeap;

	MemoryUsageMessage(NULL, 0, 0, 0);

	/* Walk all the heaps - verify structures */
	for (pHeap = m_pHeaps; pHeap; pHeap = pHeap->pNextHeap) {
	    MemoryUsageMessage("Heaps at %08x. has %d blocks\n", (long)pHeap, pHeap->memBlockCount, 0);
	    
	    ASSERT(pHeap->commitSize <= pHeap->reserveSize);
	    PBLOCKTAG pBlock = FirstHeapBlock(pHeap);
	    PBLOCKTAG lastBlock = LastHeapBlock(pHeap);
	    
	    MemoryUsageMessage("First memory block %08x: Last memory block %08x\n", (long)pBlock, (long)lastBlock, 0);
	    
	    ASSERT(!SIZE(pBlock));
	    ASSERT(!SIZE(lastBlock));
	    while (pBlock != lastBlock) {
		if (ISFREE(pBlock)) {
		    PBLOCKTAG pFreeBlock, pStart;
		    ASSERT(ISPREVFREE(NEXT(pBlock)));
		    ULONG cursize = SIZE(pBlock);
		    pStart = (cursize < nBuddyBlockSize) ? GetFreeListLink(cursize) : m_pRover;
		    for (pFreeBlock = pStart->pNextFree; pFreeBlock != pStart; pFreeBlock = pFreeBlock->pNextFree) {
			if (pFreeBlock == pBlock)
			    break;
		    }
		    if (pFreeBlock != pBlock)
			MemoryUsageMessage("Memory Block %08x: Size %08x free but not in free list\n", (long)pBlock, cursize, 0);
		}
		pBlock = NEXT(pBlock);
	    }
	}
	MemoryUsageMessage(NULL, 0, 0, 0);
    }
}

#else  /* _USE_EXERCISE_19 */

void VMem::WalkHeap(int complete)
{
    if(complete) {
	MemoryUsageMessage(NULL, 0, 0, 0);
	size_t total = 0;
	for(int i = 0; i < m_nHeaps; ++i) {
	    total += m_heaps[i].len;
	}
	MemoryUsageMessage("VMem heaps used %d. Total memory %08x\n", m_nHeaps, total, 0);

	/* Walk all the heaps - verify structures */
	for(int index = 0; index < m_nHeaps; ++index) {
	    PBLOCK ptr = m_heaps[index].base;
	    size_t size = m_heaps[index].len;
#ifndef _USE_BUDDY_BLOCKS
#ifdef USE_BIGBLOCK_ALLOC
	    if (!m_heaps[m_nHeaps].bBigBlock)
#endif
		ASSERT(HeapValidate(m_hHeap, HEAP_NO_SERIALIZE, ptr));
#endif

	    /* set over reserved header block */
	    size -= blockOverhead;
	    ptr += blockOverhead;
	    PBLOCK pLast = ptr + size;
	    ASSERT(PSIZE(ptr) == 1); /* dummy previous block is allocated */
	    ASSERT(SIZE(pLast) == 1); /* dummy next block is allocated */
	    while(ptr < pLast) {
		ASSERT(ptr > m_heaps[index].base);
		size_t cursize = SIZE(ptr) & ~1;
		ASSERT((PSIZE(ptr+cursize) & ~1) == cursize);
		MemoryUsageMessage("Memory Block %08x: Size %08x %c\n", (long)ptr, cursize, (SIZE(ptr)&1) ? 'x' : ' ');
		if(!(SIZE(ptr)&1)) {
		    /* this block is on the free list */
		    PBLOCK tmp = NEXT(ptr);
		    while(tmp != ptr) {
			ASSERT((SIZE(tmp)&1)==0);
			if(tmp == m_pFreeList)
			    break;
			ASSERT(NEXT(tmp));
			tmp = NEXT(tmp);
		    }
		    if(tmp == ptr) {
			MemoryUsageMessage("Memory Block %08x: Size %08x free but not in free list\n", (long)ptr, cursize, 0);
		    }
		}
		ptr += cursize;
	    }
	}
	MemoryUsageMessage(NULL, 0, 0, 0);
    }
}
#endif  /* _USE_EXERCISE_19 */
#endif	/* _DEBUG_MEM */

#endif	/* _USE_MSVCRT_MEM_ALLOC */

void VMem::GetLock(void)
{
    EnterCriticalSection(&m_cs);
}

void VMem::FreeLock(void)
{
    LeaveCriticalSection(&m_cs);
}

int VMem::IsLocked(void)
{
#if 0
    /* XXX TryEnterCriticalSection() is not available in some versions
     * of Windows 95.  Since this code is not used anywhere yet, we 
     * skirt the issue for now. */
    BOOL bAccessed = TryEnterCriticalSection(&m_cs);
    if(bAccessed) {
	LeaveCriticalSection(&m_cs);
    }
    return !bAccessed;
#else
    ASSERT(0);	/* alarm bells for when somebody calls this */
    return 0;
#endif
}

long VMem::Release(void)
{
    long lCount = InterlockedDecrement(&m_lRefCount);
    if(!lCount)
	delete this;
    return lCount;
}

long VMem::AddRef(void)
{
    long lCount = InterlockedIncrement(&m_lRefCount);
    return lCount;
}

#endif	/* ___VMEM_H_INC___ */
