home *** CD-ROM | disk | FTP | other *** search
/ Australian Personal Computer 2002 November / CD 1 / APC0211D1.ISO / workshop / prog / files / ActivePerl-5.6.1.633-MSWin32.msi / _74c24dd322d3595f007b04d41dca5bdf < prev    next >
Encoding:
Text File  |  2002-05-28  |  52.3 KB  |  1,890 lines
  1. /* vmem.h
  2.  *
  3.  * (c) 1999 Microsoft Corporation. All rights reserved. 
  4.  * Portions (c) 1999 ActiveState Tool Corp, http://www.ActiveState.com/
  5.  *
  6.  *    You may distribute under the terms of either the GNU General Public
  7.  *    License or the Artistic License, as specified in the README file.
  8.  *
  9.  * Options:
  10.  *
  11.  * Defining _USE_MSVCRT_MEM_ALLOC will cause all memory allocations
  12.  * to be forwarded to MSVCRT.DLL. Defining _USE_LINKED_LIST as well will
  13.  * track all allocations in a doubly linked list, so that the host can
  14.  * free all memory allocated when it goes away.
  15.  * If _USE_MSVCRT_MEM_ALLOC is not defined then Knuth's boundary tag algorithm
  16.  * is used; defining _USE_BUDDY_BLOCKS will use Knuth's algorithm R
  17.  * (Buddy system reservation)
  18.  * Defining _USE_EXERCISE_19 uses buddy block system and returns large 
  19.  * free memory blocks to the OS
  20.  *
  21.  */
  22.  
  23. #ifndef ___VMEM_H_INC___
  24. #define ___VMEM_H_INC___
  25.  
  26. // #define _USE_MSVCRT_MEM_ALLOC
  27.  
  28. // #define _USE_EXERCISE_19
  29. // #define _USE_BUDDY_BLOCKS
  30.  
  31. // #define _DEBUG_MEM
  32. #ifdef _DEBUG_MEM
  33. #define ASSERT(f) if(!(f)) DebugBreak();
  34.  
  35. inline void MEMODS(char *str)
  36. {
  37.     OutputDebugString(str);
  38.     OutputDebugString("\n");
  39. }
  40.  
  41. inline void MEMODSlx(char *str, long x)
  42. {
  43.     char szBuffer[512];    
  44.     sprintf(szBuffer, "%s %lx\n", str, x);
  45.     OutputDebugString(szBuffer);
  46. }
  47.  
  48. #define WALKHEAP() WalkHeap(0)
  49. #define WALKHEAPTRACE() WalkHeap(1)
  50.  
  51. #else
  52.  
  53. #define ASSERT(f)
  54. #define MEMODS(x)
  55. #define MEMODSlx(x, y)
  56. #define WALKHEAP()
  57. #define WALKHEAPTRACE()
  58.  
  59. #endif
  60.  
  61. #ifdef _USE_MSVCRT_MEM_ALLOC
  62.  
  63. #ifndef _USE_LINKED_LIST
  64. // #define _USE_LINKED_LIST
  65. #endif
  66.  
  67. /* 
  68.  * Pass all memory requests throught to msvcrt.dll 
  69.  * optionaly track by using a doubly linked header
  70.  */
  71.  
  72. typedef void (*LPFREE)(void *block);
  73. typedef void* (*LPMALLOC)(size_t size);
  74. typedef void* (*LPREALLOC)(void *block, size_t size);
  75. #ifdef _USE_LINKED_LIST
  76. typedef struct _MemoryBlockHeader* PMEMORY_BLOCK_HEADER;
  77. typedef struct _MemoryBlockHeader {
  78.     PMEMORY_BLOCK_HEADER    pNext;
  79.     PMEMORY_BLOCK_HEADER    pPrev;
  80. } MEMORY_BLOCK_HEADER, *PMEMORY_BLOCK_HEADER;
  81. #endif
  82.  
  83. class VMem
  84. {
  85. public:
  86.     VMem();
  87.     ~VMem();
  88.     virtual void* Malloc(size_t size);
  89.     virtual void* Realloc(void* pMem, size_t size);
  90.     virtual void Free(void* pMem);
  91.     virtual void GetLock(void);
  92.     virtual void FreeLock(void);
  93.     virtual int IsLocked(void);
  94.     virtual long Release(void);
  95.     virtual long AddRef(void);
  96.  
  97.     inline BOOL CreateOk(void)
  98.     {
  99.     return TRUE;
  100.     };
  101.  
  102. protected:
  103. #ifdef _USE_LINKED_LIST
  104.     void LinkBlock(PMEMORY_BLOCK_HEADER ptr)
  105.     {
  106.     PMEMORY_BLOCK_HEADER next = m_Dummy.pNext;
  107.     m_Dummy.pNext = ptr;
  108.     ptr->pPrev = &m_Dummy;
  109.     ptr->pNext = next;
  110.     next->pPrev = ptr;
  111.     }
  112.     void UnlinkBlock(PMEMORY_BLOCK_HEADER ptr)
  113.     {
  114.     PMEMORY_BLOCK_HEADER next = ptr->pNext;
  115.     PMEMORY_BLOCK_HEADER prev = ptr->pPrev;
  116.     prev->pNext = next;
  117.     next->pPrev = prev;
  118.     }
  119.  
  120.     MEMORY_BLOCK_HEADER    m_Dummy;
  121. #endif
  122.  
  123.     long        m_lRefCount;    // number of current users
  124.     CRITICAL_SECTION    m_cs;        // access lock
  125.     HINSTANCE        m_hLib;
  126.     LPFREE        m_pfree;
  127.     LPMALLOC        m_pmalloc;
  128.     LPREALLOC        m_prealloc;
  129. };
  130.  
  131. VMem::VMem()
  132. {
  133.     m_lRefCount = 1;
  134.     InitializeCriticalSection(&m_cs);
  135. #ifdef _USE_LINKED_LIST
  136.     m_Dummy.pNext = m_Dummy.pPrev =  &m_Dummy;
  137. #endif
  138.     m_hLib = LoadLibrary("msvcrt.dll");
  139.     if (m_hLib) {
  140.     m_pfree = (LPFREE)GetProcAddress(m_hLib, "free");
  141.     m_pmalloc = (LPMALLOC)GetProcAddress(m_hLib, "malloc");
  142.     m_prealloc = (LPREALLOC)GetProcAddress(m_hLib, "realloc");
  143.     }
  144. }
  145.  
  146. VMem::~VMem(void)
  147. {
  148. #ifdef _USE_LINKED_LIST
  149.     while (m_Dummy.pNext != &m_Dummy) {
  150.     Free(m_Dummy.pNext+1);
  151.     }
  152. #endif
  153.     if (m_hLib)
  154.     FreeLibrary(m_hLib);
  155.     DeleteCriticalSection(&m_cs);
  156. }
  157.  
  158. void* VMem::Malloc(size_t size)
  159. {
  160. #ifdef _USE_LINKED_LIST
  161.     PMEMORY_BLOCK_HEADER ptr = (PMEMORY_BLOCK_HEADER)m_pmalloc(size+sizeof(MEMORY_BLOCK_HEADER));
  162.     LinkBlock(ptr);
  163.     return (ptr+1);
  164. #else
  165.     return m_pmalloc(size);
  166. #endif
  167. }
  168.  
  169. void* VMem::Realloc(void* pMem, size_t size)
  170. {
  171. #ifdef _USE_LINKED_LIST
  172.     if (!pMem)
  173.     return Malloc(size);
  174.  
  175.     if (!size) {
  176.     Free(pMem);
  177.     return NULL;
  178.     }
  179.  
  180.     PMEMORY_BLOCK_HEADER ptr = (PMEMORY_BLOCK_HEADER)(((char*)pMem)-sizeof(MEMORY_BLOCK_HEADER));
  181.     UnlinkBlock(ptr);
  182.     ptr = (PMEMORY_BLOCK_HEADER)m_prealloc(ptr, size+sizeof(MEMORY_BLOCK_HEADER));
  183.     LinkBlock(ptr);
  184.  
  185.     return (ptr+1);
  186. #else
  187.     return m_prealloc(pMem, size);
  188. #endif
  189. }
  190.  
  191. void VMem::Free(void* pMem)
  192. {
  193. #ifdef _USE_LINKED_LIST
  194.     if (pMem) {
  195.     PMEMORY_BLOCK_HEADER ptr = (PMEMORY_BLOCK_HEADER)(((char*)pMem)-sizeof(MEMORY_BLOCK_HEADER));
  196.     UnlinkBlock(ptr);
  197.     m_pfree(ptr);
  198.     }
  199. #else
  200.     m_pfree(pMem);
  201. #endif
  202. }
  203.  
  204. #else    /* _USE_MSVCRT_MEM_ALLOC */
  205.  
  206. /*
  207.  * Knuth's boundary tag algorithm Vol #1, Page 440.
  208.  *
  209.  * Each block in the heap has tag words before and after it,
  210.  *  TAG
  211.  *  block
  212.  *  TAG
  213.  * The size is stored in these tags as a long word, and includes the 8 bytes
  214.  * of overhead that the boundary tags consume.  Blocks are allocated on long
  215.  * word boundaries, so the size is always multiples of long words.  When the
  216.  * block is allocated, bit 0, (the tag bit), of the size is set to 1.  When 
  217.  * a block is freed, it is merged with adjacent free blocks, and the tag bit
  218.  * is set to 0.
  219.  *
  220.  * A linked list is used to manage the free list. The first two long words of
  221.  * the block contain double links.  These links are only valid when the block
  222.  * is freed, therefore space needs to be reserved for them.  Thus, the minimum
  223.  * block size (not counting the tags) is 8 bytes.
  224.  *
  225.  * Since memory allocation may occur on a single threaded, explict locks are not
  226.  * provided.
  227.  * 
  228.  */
  229.  
  230. #ifdef _USE_EXERCISE_19
  231. /*----------------------------------------------------------------------
  232.  * Variation from above that incorporates the buddy block system and
  233.  * the ideas from exercise 19.
  234.  *
  235.  * Since the allocations are always multiples of ULONG words, the lower 2
  236.  * bits of the tag can be used to indicate the status of this block and
  237.  * the previous block. Therefore the tag is only needed at the begining 
  238.  * of a block. The size is stored as a ULONG, and DOES NOT include the 4 
  239.  * bytes of overhead that the tag consumes.
  240.  *
  241.  * When the block is allocated, tag bit 0 (TAGBIT_FREE) of the size is set
  242.  * to 0. Tag bit 1 (TAGBIT_PREVFREE) if set indicates that the previous 
  243.  * block is free. When a block is freed, it is merged with adjacent free
  244.  * blocks.
  245.  *
  246.  * On the free list, the first two ULONG words of the block contain links.
  247.  * In addition, there is a pointer at the end of the block, which points
  248.  * to the begining of the block. These links are only valid when the block
  249.  * is free, therefore space needs to be reserved for them. Thus, the minimum
  250.  * block size is 12 bytes (not counting the tag).
  251.  *
  252.  * Blocks larger than nBuddyBlockSize have one free list with a roving 
  253.  * pointer. Blocks smaller than nBuddyBlockSize have an array of free lists.
  254.  * Each of these lists link free blocks of the same size.
  255.  */
  256.  
  257.  
  258. #define    ROUND_UP(x,p2)    (((x)+((p2)-1))&(~((p2)-1)))
  259. #define    ROUND_DOWN(x,p2) ((x)&(~((p2)-1)))
  260.  
  261. const int maxHeaps = 32;
  262.  
  263. /*
  264.  * The use of structures yields less macros and type casting
  265.  */
  266.  
  267. typedef struct _Heap* PHEAP;
  268. typedef struct _Heap
  269. {
  270.     ULONG    commitSize;        /* committed size in this heap */
  271.     ULONG    reserveSize;        /* total reserved size */
  272.     ULONG    memBlockCount;        /* number of memory blocks in memBlocks */
  273.     BYTE*    memBlocks[maxHeaps];    /* all non-contiguous heap areas */
  274.     PHEAP    pNextHeap;        /* next heap if this is full */
  275. } HEAP;
  276.  
  277. typedef struct _BlockTag* PBLOCKTAG;
  278. typedef    struct _BlockTag
  279. {
  280.     ULONG    blockSize;    /* bit 0 this block. bit 1 prev block, if set then free */
  281.     PBLOCKTAG    pNextFree;    /* only exist in free blocks */
  282.     PBLOCKTAG    pPrevFree;
  283. } BLOCKTAG;
  284. /* free blocks are terminated with 'PBLOCKTAG' pointing back to their BLOCKTAG structure */
  285.  
  286. typedef struct _BuddyLinks* PBUDDYLINK;
  287. typedef struct _BuddyLinks
  288. {
  289.     PBLOCKTAG pNextFree;
  290.     PBLOCKTAG pPrevFree;
  291. } BUDDYLINK;
  292.  
  293. /*
  294.  * Note the BUDDYLINK is the same as the BLOCKTAG without the blockSize
  295.  * This assumption is made in the code to conserve space
  296.  */
  297.  
  298. const ULONG lAllocSize = 0x020000;    /* each new block is at least this size */
  299. const ULONG lFreeSize = lAllocSize*2;    /* when this much memory is free return it to OS */
  300. const ULONG minBlockSize = sizeof(BLOCKTAG);
  301. const ULONG blockOverhead = sizeof(PBLOCKTAG);
  302. const ULONG blockAlign = sizeof(ULONG);
  303. const ULONG minAllocSize = minBlockSize+blockOverhead;
  304. const ULONG initialReserveSize = 0x800000;
  305. const ULONG nBuddyBlockSize = 4096;
  306. const ULONG nBuddyTableSize = (nBuddyBlockSize * (sizeof(BUDDYLINK) / blockAlign));
  307.  
  308. #define    MEM2TAG(ptr)    ((PBLOCKTAG)(((BYTE*)(ptr))-sizeof(ULONG)))
  309. #define    TAG2MEM(pBlock)    ((void*)(((BYTE*)(pBlock))+sizeof(ULONG)))
  310.  
  311. #define    TAGBIT_FREE    1    /* this block is free */
  312. #define    TAGBIT_PREVFREE    2    /* previous block is free */
  313. #define    TAGBIT_MASK    3    /* mask for flags in the blocksize */
  314.  
  315. #define    SIZE(pBlock)        (((pBlock)->blockSize)&(~TAGBIT_MASK))
  316. #define    AVAILSIZE(pBlock)    ((((pBlock)->blockSize)&(~TAGBIT_MASK))+sizeof(ULONG))
  317. #define    ISFREE(pBlock)        (((pBlock)->blockSize)&TAGBIT_FREE)
  318. #define    ISPREVFREE(pBlock)    (((pBlock)->blockSize)&TAGBIT_PREVFREE)
  319. #define    NEXT(pBlock)        ((PBLOCKTAG)((BYTE*)TAG2MEM(pBlock)+SIZE(pBlock)))
  320.  
  321. inline void SetBlockBackPtr(PBLOCKTAG pBlock, ULONG size)
  322. {
  323.     *(PBLOCKTAG*)(((BYTE*)pBlock) + size) = pBlock;
  324. }
  325.  
  326. inline PBLOCKTAG PreviousBlock(PBLOCKTAG pBlock)
  327. {
  328.     return *(PBLOCKTAG*)(((BYTE*)(pBlock)) - blockOverhead);
  329. }
  330.  
  331. inline PBLOCKTAG FirstHeapBlock(PHEAP pHeap)
  332. {
  333.     return ((PBLOCKTAG)(((BYTE*)pHeap) + sizeof(HEAP)));
  334. }
  335. inline PBLOCKTAG LastHeapBlock(PHEAP pHeap)
  336. {
  337.     return ((PBLOCKTAG)(((BYTE*)pHeap)+pHeap->commitSize - sizeof(ULONG)));
  338. }
  339.  
  340. inline AddToFreeList(PBLOCKTAG pFreeList, PBLOCKTAG pBlock)
  341. {
  342.     pBlock->pNextFree = pFreeList->pNextFree;
  343.     pBlock->pPrevFree = pFreeList;
  344.     pBlock->pNextFree->pPrevFree = pFreeList->pNextFree = pBlock;
  345. }
  346.  
  347. inline UnlinkBlock(PBLOCKTAG pBlock)
  348. {
  349.     pBlock->pNextFree->pPrevFree = pBlock->pPrevFree;
  350.     pBlock->pPrevFree->pNextFree = pBlock->pNextFree;
  351. }
  352.  
  353. class VMem
  354. {
  355. public:
  356.     VMem();
  357.     ~VMem();
  358.     virtual void* Malloc(size_t size);
  359.     virtual void* Realloc(void* pMem, size_t size);
  360.     virtual void Free(void* pMem);
  361.     virtual void GetLock(void);
  362.     virtual void FreeLock(void);
  363.     virtual int IsLocked(void);
  364.     virtual long Release(void);
  365.     virtual long AddRef(void);
  366.  
  367.     inline BOOL CreateOk(void) { return TRUE; };
  368.  
  369. protected:
  370.     int Getmem(ULONG size);
  371.     void* Expand(void* pBlock, ULONG size);
  372.     BOOL ResizeHeap(PHEAP pHeap, ULONG newSize);
  373.     inline PBLOCKTAG GetFreeListLink(int index)
  374.     {
  375.     ASSERT(!(index&TAGBIT_MASK));
  376.     return ((PBLOCKTAG) (((BYTE*)m_pBuddyLinks)
  377.         + ((index) * (sizeof(BUDDYLINK)/blockAlign))
  378.             - (sizeof(ULONG) + sizeof(BUDDYLINK))));
  379.     }
  380.     inline void CheckRoverAndUnlinkBlock(PBLOCKTAG pBlock)
  381.     {
  382.         if (m_pRover == pBlock)
  383.             m_pRover = m_pRover->pNextFree;
  384.         UnlinkBlock(pBlock);
  385.     }
  386.     inline void MarkBlockInUse(PBLOCKTAG pBlock)
  387.     {
  388.     pBlock->blockSize &= ~TAGBIT_FREE;
  389.     NEXT(pBlock)->blockSize &= ~TAGBIT_PREVFREE;
  390.     }
  391.  
  392.     /*
  393.      * pointer to an array of doublely linked list of headers 
  394.      * for blocks < nBuddyBlockSize
  395.      */
  396.     PBUDDYLINK        m_pBuddyLinks;
  397.  
  398.     /* free list for non buddy blocks */
  399.     BLOCKTAG        m_freeList;
  400.     PBLOCKTAG        m_pRover;
  401.     PHEAP        m_pHeaps;
  402.     DWORD        m_dwPageSize;
  403.  
  404.     long        m_lRefCount;    // number of current users
  405.     CRITICAL_SECTION    m_cs;        // access lock
  406.  
  407. // #define _VERIFY_FREES
  408. #ifdef _VERIFY_FREES
  409.     bool VerifyPtr(void* ptr);
  410. #endif
  411. #ifdef _DEBUG_MEM
  412.     void WalkHeap(int complete);
  413.     void MemoryUsageMessage(char* str, long x, long y, int c);
  414.     FILE*        m_pLog;
  415. #endif
  416. };
  417.  
  418. VMem::VMem()
  419. {
  420.     SYSTEM_INFO si;
  421.  
  422.     GetSystemInfo(&si);
  423.     m_dwPageSize = si.dwPageSize;
  424.     m_pHeaps = NULL;
  425.     m_pBuddyLinks = NULL;
  426.     m_freeList.blockSize = TAGBIT_FREE;
  427.     m_freeList.pNextFree = &m_freeList;
  428.     m_freeList.pPrevFree = &m_freeList;
  429.     m_pRover = &m_freeList;
  430.  
  431.     m_lRefCount = 1;
  432.  
  433.     InitializeCriticalSection(&m_cs);
  434. #ifdef _DEBUG_MEM
  435.     m_pLog = 0;
  436. #endif
  437. }
  438.  
  439. VMem::~VMem()
  440. {
  441.     PHEAP pHeap, pNextHeap;
  442.     int index;
  443.  
  444.     WALKHEAPTRACE();
  445.  
  446.     for (pHeap = m_pHeaps; pHeap; pHeap = pNextHeap) {
  447.     pNextHeap = pHeap->pNextHeap;
  448.         for (index = --pHeap->memBlockCount; index >= 0; --index) {
  449.             ULONG size = pHeap->commitSize - (pHeap->memBlocks[index] - (BYTE*)pHeap);
  450.             void* ptr = pHeap->memBlocks[index];
  451.  
  452.             pHeap->commitSize = pHeap->reserveSize = pHeap->memBlocks[index] - (BYTE*)pHeap;
  453.  
  454.             VirtualFree(ptr, size, MEM_DECOMMIT);
  455.             VirtualFree(ptr, 0, MEM_RELEASE);
  456.         }
  457.     }
  458. }
  459.  
  460. void* VMem::Malloc(size_t size)
  461. {
  462.     ULONG allocSize;
  463.     PBLOCKTAG pFreeBlock;
  464.     int loops = 2;
  465.  
  466.     WALKHEAP();
  467.  
  468.     if (!size)
  469.         return NULL;
  470.  
  471.     if (!m_pBuddyLinks)
  472.         Getmem(nBuddyTableSize + sizeof(HEAP) + minBlockSize);
  473.  
  474.     /*
  475.      * If the size <= nBuddyBlockSize, first check if a free block
  476.      * of that size exists. If not then take the m_pRover. If there are no free
  477.      * blocks > nBuddyBlockSize, scan forward in the buddy list until we find 
  478.      * a free block. If all that fails, get more memory from the OS
  479.      */
  480.     allocSize = (size < minBlockSize) ? minBlockSize : ROUND_UP(size, blockAlign);
  481.     while(loops--) {
  482.     if (allocSize < nBuddyBlockSize) {
  483.         pFreeBlock = GetFreeListLink(allocSize);
  484.         if (pFreeBlock->pNextFree != pFreeBlock) {
  485.         pFreeBlock = pFreeBlock->pNextFree;
  486.         MarkBlockInUse(pFreeBlock);
  487.         UnlinkBlock(pFreeBlock);
  488.  
  489.         return TAG2MEM(pFreeBlock);
  490.         }
  491.  
  492.         /* if m_pRover not empty then must fit */
  493.         pFreeBlock = m_pRover;
  494.         if (pFreeBlock == &m_freeList)
  495.         pFreeBlock = pFreeBlock->pNextFree;
  496.  
  497.         /* if oversize list is empty, find next larger slot */
  498.         if (pFreeBlock == &m_freeList) {
  499.         /*
  500.          * scan the buddy list for an entry.
  501.          * the end of list marker has ->pNextFree == NULL.
  502.          */
  503.         for (pFreeBlock = GetFreeListLink(allocSize + blockAlign); 
  504.             pFreeBlock->pNextFree == pFreeBlock;
  505.                 pFreeBlock = (PBLOCKTAG)(((BYTE*)pFreeBlock)+sizeof(BUDDYLINK)))
  506.             ;
  507.  
  508.         pFreeBlock = (pFreeBlock->pNextFree) ? pFreeBlock->pNextFree : &m_freeList;
  509.         }
  510.     }
  511.     else {
  512.         ULONG saveSize = (pFreeBlock = m_pRover)->blockSize;
  513.         if (saveSize < allocSize) {
  514.         m_pRover->blockSize = 0xFFFFFFFF; /* mark this to complete the search */
  515.         for (pFreeBlock = pFreeBlock->pNextFree; 
  516.             pFreeBlock->blockSize < allocSize;
  517.                 pFreeBlock = pFreeBlock->pNextFree)
  518.             ;
  519.  
  520.         m_pRover->blockSize = saveSize;
  521.         if (m_pRover == pFreeBlock)
  522.             pFreeBlock = &m_freeList; /* say not found */
  523.         }
  524.     }
  525.  
  526.     if (pFreeBlock != &m_freeList) {
  527.         ULONG freeSize = SIZE(pFreeBlock);
  528.         if (freeSize - allocSize < minAllocSize) {
  529.         MarkBlockInUse(pFreeBlock);
  530.         CheckRoverAndUnlinkBlock(pFreeBlock);
  531.         }
  532.         else {
  533.         /* split the block */
  534.         PBLOCKTAG pNextBlock;
  535.         ULONG rem;
  536.  
  537.         pFreeBlock->blockSize = allocSize;
  538.  
  539.         pNextBlock = NEXT(pFreeBlock);
  540.         rem = freeSize - allocSize - sizeof(ULONG);
  541.         pNextBlock->blockSize = rem | TAGBIT_FREE;
  542.  
  543.         SetBlockBackPtr(pNextBlock, rem);
  544.         if (rem < nBuddyBlockSize) {
  545.             AddToFreeList(GetFreeListLink(rem), pNextBlock);
  546.             CheckRoverAndUnlinkBlock(pFreeBlock);
  547.         }
  548.         else {
  549.             pFreeBlock->pPrevFree->pNextFree = pNextBlock;
  550.             pNextBlock->pPrevFree = pFreeBlock->pPrevFree;
  551.             pFreeBlock->pNextFree->pPrevFree = pNextBlock;
  552.             pNextBlock->pNextFree = pFreeBlock->pNextFree;
  553.             m_pRover = pNextBlock;
  554.         }
  555.         }
  556.  
  557.         return TAG2MEM(pFreeBlock);
  558.     }
  559.     else {
  560.         /*
  561.          * We've gone through this list once already without finding anything, 
  562.          * allocate some new memory from the heap and try again.
  563.          */
  564.         Getmem(size + sizeof(HEAP));
  565.     }
  566.     }
  567.  
  568.     return NULL;
  569. }
  570.  
  571. void* VMem::Realloc(void* ptr, size_t size)
  572. {
  573.     WALKHEAP();
  574.  
  575.     /* if size is zero, free the block. */
  576.     if (!size) {
  577.         Free(ptr);
  578.         return NULL;
  579.     }
  580.  
  581.     /* if pointer is NULL, do a Malloc(). */
  582.     if (!ptr)
  583.         return Malloc(size);
  584.  
  585.     /*
  586.      * Grow or shrink the block in place.
  587.      * if the block grows then the next block will be used if free
  588.      */
  589.     if (!Expand(ptr, size)) {
  590.         void* newPtr;
  591.         if ((newPtr = Malloc(size)) != NULL) {
  592.         ULONG moveSize = SIZE(MEM2TAG(ptr));
  593.         if (moveSize > size)
  594.         moveSize = size;
  595.             memmove(newPtr, ptr, moveSize);
  596.             Free(ptr);
  597.         }
  598.         return newPtr;
  599.     }
  600.     return ptr;
  601. }
  602.  
  603. void VMem::Free(void* ptr)
  604. {
  605.     PBLOCKTAG pBlock, pNextBlock;
  606.     ULONG size;
  607.  
  608.     /* Ignore null pointer. */
  609.     if (!ptr)
  610.         return;
  611.  
  612. #ifdef _VERIFY_FREES
  613.     if (!VerifyPtr(ptr))
  614.     return;
  615. #endif
  616.  
  617.     WALKHEAP();
  618.  
  619.     pBlock = MEM2TAG(ptr);
  620.     /* if previous block is free, add this block to it. */
  621.     if (ISPREVFREE(pBlock)) {
  622.         PBLOCKTAG pPrevBlock = PreviousBlock(pBlock);
  623.         pPrevBlock->blockSize += AVAILSIZE(pBlock);
  624.         pBlock = pPrevBlock;
  625.         CheckRoverAndUnlinkBlock(pBlock);
  626.     }
  627.     else {
  628.         /* cannot merge previous, mark this block free */
  629.         pBlock->blockSize |= TAGBIT_FREE;
  630.     }
  631.  
  632.     /* if the next physical block is free, merge it with this block. */
  633.     if (ISFREE(pNextBlock = NEXT(pBlock))) {
  634.         pBlock->blockSize += AVAILSIZE(pNextBlock);
  635.         CheckRoverAndUnlinkBlock(pNextBlock);
  636.     }
  637.  
  638.     pNextBlock = NEXT(pBlock);
  639.     pNextBlock->blockSize |= TAGBIT_PREVFREE;
  640.  
  641.     /* reinsert block to free list */
  642.     size = SIZE(pBlock);
  643.     AddToFreeList((size < nBuddyBlockSize) ? GetFreeListLink(size) : m_pRover->pNextFree, pBlock);
  644.     SetBlockBackPtr(pBlock, size);
  645.  
  646.     /* Can this heap shrink */
  647.     if (pNextBlock->blockSize == TAGBIT_PREVFREE && pBlock->blockSize-minBlockSize >= lFreeSize) {
  648.     PHEAP pHeap;
  649.     ULONG diffSize = ROUND_DOWN(pBlock->blockSize-minBlockSize, lFreeSize);
  650.     for (pHeap = m_pHeaps; pHeap; pHeap = pHeap->pNextHeap) {
  651.         if (LastHeapBlock(pHeap) == pNextBlock) {
  652.         /* this heap can shrink */
  653.         ULONG newSize = pHeap->commitSize - diffSize;
  654.         ResizeHeap(pHeap, newSize);
  655.         while ((BYTE*)pHeap + newSize <= pHeap->memBlocks[pHeap->memBlockCount - 1]) {
  656.             /* give block back to OS */
  657.             size = pHeap->commitSize - (pHeap->memBlocks[--pHeap->memBlockCount] - (BYTE*)pHeap);
  658.             VirtualFree(pHeap->memBlocks[pHeap->memBlockCount], size, MEM_DECOMMIT);
  659.             VirtualFree(pHeap->memBlocks[pHeap->memBlockCount], 0, MEM_RELEASE);
  660.             pHeap->commitSize = pHeap->reserveSize = pHeap->memBlocks[pHeap->memBlockCount] - (BYTE*)pHeap;
  661.         }
  662.  
  663.         VirtualFree(pHeap->memBlocks[pHeap->memBlockCount - 1] + newSize, pHeap->commitSize - newSize, MEM_DECOMMIT);
  664.         pHeap->commitSize = newSize;
  665.         break;
  666.         }
  667.     }
  668.     }
  669. }
  670.  
  671. BOOL VMem::ResizeHeap(PHEAP pHeap, ULONG newSize)
  672. {
  673.     ULONG diffSize;
  674.     PBLOCKTAG pBlock;
  675.  
  676.     newSize = ROUND_DOWN(newSize, m_dwPageSize);
  677.     pBlock = LastHeapBlock(pHeap);
  678.     if (newSize < pHeap->commitSize) {
  679.         if (!ISPREVFREE(pBlock))
  680.             return FALSE;
  681.  
  682.     pBlock = PreviousBlock(pBlock);
  683.         diffSize = pHeap->commitSize - newSize;
  684.  
  685.         if (SIZE(pBlock) - minBlockSize < diffSize)
  686.             return FALSE;
  687.  
  688.         pBlock->blockSize -= diffSize;
  689.         SetBlockBackPtr(pBlock, SIZE(pBlock));
  690.         NEXT(pBlock)->blockSize = TAGBIT_PREVFREE;
  691.  
  692.         if (SIZE(pBlock) < nBuddyBlockSize) {
  693.         /* reinsert block to correct free list */
  694.             UnlinkBlock(pBlock);
  695.             AddToFreeList(GetFreeListLink(SIZE(pBlock)), pBlock);
  696.         }
  697.     }
  698.     else {
  699.         diffSize = newSize - pHeap->commitSize;
  700.         pBlock->blockSize += diffSize - sizeof(ULONG);
  701.         NEXT(pBlock)->blockSize = 0;
  702.         Free(TAG2MEM(pBlock));
  703.         pHeap->commitSize += diffSize;
  704.     }
  705.     return TRUE;
  706. }
  707.  
  708.  
  709. BOOL VMem::Getmem(ULONG minSize)
  710. {
  711.     PBLOCKTAG pBlock;
  712.     PHEAP pHeap;
  713.     void* pMem;
  714.     ULONG tableSize, innerSize;
  715.     ULONG commitSize, virtualSize, allocMinSize = ROUND_UP(minSize, m_dwPageSize);
  716.  
  717.     /* find a heap that has some reserved memory available */
  718.     for (pHeap = m_pHeaps; pHeap; pHeap = pHeap->pNextHeap) {
  719.         if (pHeap->reserveSize - pHeap->commitSize > allocMinSize) {
  720.             ULONG newSize = pHeap->reserveSize;
  721.         commitSize = pHeap->commitSize + ROUND_UP(allocMinSize, lAllocSize);
  722.             if (newSize > commitSize)
  723.         newSize = commitSize;
  724.             if (VirtualAlloc((BYTE*)pHeap + pHeap->commitSize, newSize - pHeap->commitSize, MEM_COMMIT, PAGE_READWRITE)) {
  725.                 return ResizeHeap(pHeap, newSize);
  726.             }
  727.             /* otherwise, try to commit m_dwPageSize */
  728.             else if(VirtualAlloc((BYTE*)pHeap + pHeap->commitSize, m_dwPageSize, MEM_COMMIT, PAGE_READWRITE)) {
  729.                 return ResizeHeap(pHeap, pHeap->commitSize+m_dwPageSize);
  730.             }
  731.             /* Out of memory!!! */
  732.             else
  733.         return FALSE;
  734.         }
  735.     }
  736.  
  737.     /* allocate more memory */
  738.     virtualSize = (allocMinSize < initialReserveSize)
  739.     ? initialReserveSize
  740.         : ROUND_UP(allocMinSize, initialReserveSize);
  741.  
  742.     pMem = VirtualAlloc(NULL, virtualSize, MEM_RESERVE, PAGE_NOACCESS);
  743.     if (!pMem)
  744.         return FALSE;
  745.  
  746.     commitSize = ROUND_UP(allocMinSize + m_dwPageSize, lAllocSize);
  747.     for (pHeap = m_pHeaps; pHeap; pHeap = pHeap->pNextHeap) {
  748.         if ((BYTE*)pHeap + pHeap->reserveSize == pMem && pHeap->memBlockCount < maxHeaps) {
  749.             ULONG rem = pHeap->reserveSize - pHeap->commitSize;
  750.             if (rem) {
  751.                 if (!VirtualAlloc((BYTE*)pHeap + pHeap->commitSize, rem, MEM_COMMIT, PAGE_READWRITE))
  752.                     return FALSE;
  753.  
  754.                 ResizeHeap(pHeap, pHeap->reserveSize);
  755.             }
  756.  
  757.             if (!VirtualAlloc(pMem, commitSize - rem, MEM_COMMIT, PAGE_READWRITE))
  758.                 return FALSE;
  759.         else {
  760.                 pHeap->memBlocks[pHeap->memBlockCount++] = (BYTE*)pMem;
  761.                 pHeap->reserveSize += virtualSize;
  762.                 return ResizeHeap(pHeap, pHeap->commitSize + commitSize - rem);
  763.             }
  764.         }
  765.     }
  766.  
  767.     if (!VirtualAlloc(pMem, commitSize, MEM_COMMIT, PAGE_READWRITE)) {
  768.         VirtualFree(pMem, 0, MEM_RELEASE);
  769.         return FALSE;
  770.     }
  771.  
  772.     pHeap = (PHEAP)pMem;
  773.  
  774.     /* Create the header for the heap */
  775.     pHeap->memBlockCount = 1;
  776.     pHeap->memBlocks[0] = (BYTE*)pMem;
  777.     pHeap->commitSize = commitSize;
  778.     pHeap->reserveSize = virtualSize;
  779.  
  780.     /* Link it in */
  781.     pHeap->pNextHeap = m_pHeaps;
  782.     m_pHeaps = pHeap;
  783.  
  784.     /* The first dummy block */
  785.     pBlock = FirstHeapBlock(pHeap);
  786.     pBlock->blockSize = 0;
  787.     pBlock = NEXT(pBlock);
  788.  
  789.     tableSize = 0;
  790.     /* Allocate the buddy blocks */
  791.     if (!m_pBuddyLinks) {
  792.     int index;
  793.     PBLOCKTAG pTerm;
  794.  
  795.         tableSize = ROUND_UP(nBuddyTableSize, blockAlign);
  796.         m_pBuddyLinks = (PBUDDYLINK)TAG2MEM(pBlock);
  797.         pBlock->blockSize = tableSize;
  798.         pBlock = NEXT(pBlock);
  799.  
  800.     for (index = minBlockSize; index < nBuddyBlockSize; index += blockAlign) {
  801.         PBLOCKTAG p = GetFreeListLink(index);
  802.         p->pNextFree = p->pPrevFree = p;
  803.     }
  804.     pTerm = GetFreeListLink(nBuddyBlockSize);
  805.     pTerm->pNextFree = pTerm->pPrevFree = NULL;
  806.  
  807.         tableSize += sizeof(ULONG);
  808.     }
  809.  
  810.     /* Inner free block size is
  811.      *    commitSize - sizeof(HEAP) - (tableSize if just created)
  812.      *    - (2 dummy zero-length blocks + free block header) 
  813.      */                  
  814.     innerSize = commitSize - sizeof(HEAP) - tableSize - (3 * sizeof(ULONG));
  815.     pBlock->blockSize = innerSize | TAGBIT_FREE; /* previous block is NOT free */
  816.  
  817.     /* The last dummy block */
  818.     NEXT(pBlock)->blockSize = TAGBIT_PREVFREE; /* previous block is free */
  819.  
  820.     AddToFreeList((innerSize < nBuddyBlockSize) ?  GetFreeListLink(innerSize) : m_pRover, pBlock);
  821.     SetBlockBackPtr(pBlock, innerSize);
  822.     return TRUE;
  823. }
  824.  
  825. void* VMem::Expand(void* ptr, ULONG size)
  826. {
  827.     PBLOCKTAG pBlock, pNextBlock;
  828.     ULONG allocSize, availSize;
  829.  
  830.     pBlock = MEM2TAG(ptr);
  831.     availSize = SIZE(pBlock);
  832.     allocSize = (size < minBlockSize) ? minBlockSize : ROUND_UP(size, blockAlign);
  833.     if (availSize == allocSize)
  834.     return ptr;
  835.  
  836.     pNextBlock = NEXT(pBlock);
  837.     if (ISFREE(pNextBlock))
  838.         availSize += AVAILSIZE(pNextBlock);
  839.  
  840.     if (availSize >= allocSize) {
  841.         PBLOCKTAG oldPrevFree = NULL;
  842.         /* Can grow/shrink in place. If the next block is free merge it */
  843.         if (ISFREE(pNextBlock)) {
  844.             if (SIZE(pNextBlock) >= nBuddyBlockSize)
  845.                 oldPrevFree = pNextBlock->pPrevFree;
  846.  
  847.             CheckRoverAndUnlinkBlock(pNextBlock);
  848.             NEXT(pNextBlock)->blockSize &= ~TAGBIT_PREVFREE;
  849.             pBlock->blockSize = availSize | (pBlock->blockSize & TAGBIT_PREVFREE);
  850.         }
  851.  
  852.     /* if the block is being shrunk, convert the remainder of the block into a new free block. */
  853.         if (availSize - allocSize >= minAllocSize) {
  854.             /* shrink back to requested size */
  855.             ULONG rem = availSize - allocSize - sizeof(ULONG);
  856.             pBlock->blockSize = allocSize | (pBlock->blockSize & TAGBIT_PREVFREE);
  857.             pNextBlock = NEXT(pBlock);
  858.             pNextBlock->blockSize = rem | TAGBIT_FREE;
  859.             NEXT(pNextBlock)->blockSize |= TAGBIT_PREVFREE;
  860.  
  861.             /* reinsert block to free list */
  862.             AddToFreeList((rem < nBuddyBlockSize)
  863.             ? GetFreeListLink(rem)
  864.             : (oldPrevFree ? oldPrevFree : m_pRover->pNextFree), pNextBlock);
  865.             SetBlockBackPtr(pNextBlock, rem);
  866.         }
  867.  
  868.     return ptr;
  869.     }
  870.     return NULL;
  871. }
  872.  
  873. #ifdef _VERIFY_FREES
  874. bool VMem::VerifyPtr(void* ptr)
  875. {
  876.     PHEAP pHeap;
  877.  
  878.     for (pHeap = m_pHeaps; pHeap; pHeap = pHeap->pNextHeap) {
  879.     char* pLow = (char*)pHeap;
  880.     char* pHigh = pLow + pHeap->commitSize;
  881.     char* pTest = (char*)ptr;
  882.     if (pLow < pTest && pTest < pHigh)
  883.         return true;
  884.     }
  885. //    DebugBreak();
  886.     return false;
  887. }
  888. #endif
  889.  
  890. #else  /* _USE_EXERCISE_19 */
  891.  
  892. const long lAllocStart = 0x00020000; /* start at 128K */
  893. const long minBlockSize = sizeof(void*)*2;
  894. const long sizeofTag = sizeof(long);
  895. const long blockOverhead = sizeofTag*2;
  896. const long minAllocSize = minBlockSize+blockOverhead;
  897. #ifdef _USE_BUDDY_BLOCKS
  898. const long lSmallBlockSize = 1024;
  899. const size_t nListEntries = ((lSmallBlockSize-minAllocSize)/sizeof(long));
  900.  
  901. inline size_t CalcEntry(size_t size)
  902. {
  903.     ASSERT((size&(sizeof(long)-1)) == 0);
  904.     return ((size - minAllocSize) / sizeof(long));
  905. }
  906. #endif
  907.  
  908. typedef BYTE* PBLOCK;    /* pointer to a memory block */
  909.  
  910. /*
  911.  * Macros for accessing hidden fields in a memory block:
  912.  *
  913.  * SIZE        size of this block (tag bit 0 is 1 if block is allocated)
  914.  * PSIZE    size of previous physical block
  915.  */
  916.  
  917. #define SIZE(block)    (*(ULONG*)(((PBLOCK)(block))-sizeofTag))
  918. #define PSIZE(block)    (*(ULONG*)(((PBLOCK)(block))-(blockOverhead)))
  919. inline void SetTags(PBLOCK block, long size)
  920. {
  921.     SIZE(block) = size;
  922.     PSIZE(block+(size&~1)) = size;
  923. }
  924.  
  925. /*
  926.  * Free list pointers
  927.  * PREV    pointer to previous block
  928.  * NEXT    pointer to next block
  929.  */
  930.  
  931. #define PREV(block)    (*(PBLOCK*)(block))
  932. #define NEXT(block)    (*(PBLOCK*)((block)+sizeof(PBLOCK)))
  933. inline void SetLink(PBLOCK block, PBLOCK prev, PBLOCK next)
  934. {
  935.     PREV(block) = prev;
  936.     NEXT(block) = next;
  937. }
  938. inline void Unlink(PBLOCK p)
  939. {
  940.     PBLOCK next = NEXT(p);
  941.     PBLOCK prev = PREV(p);
  942.     NEXT(prev) = next;
  943.     PREV(next) = prev;
  944. }
  945. #ifndef _USE_BUDDY_BLOCKS
  946. inline void AddToFreeList(PBLOCK block, PBLOCK pInList)
  947. {
  948.     PBLOCK next = NEXT(pInList);
  949.     NEXT(pInList) = block;
  950.     SetLink(block, pInList, next);
  951.     PREV(next) = block;
  952. }
  953. #endif
  954.  
  955. /* Macro for rounding up to the next sizeof(long) */
  956. #define ROUND_UP(n)    (((ULONG)(n)+sizeof(long)-1)&~(sizeof(long)-1))
  957. #define ROUND_UP64K(n)    (((ULONG)(n)+0x10000-1)&~(0x10000-1))
  958. #define ROUND_DOWN(n)    ((ULONG)(n)&~(sizeof(long)-1))
  959.  
  960. /*
  961.  * HeapRec - a list of all non-contiguous heap areas
  962.  *
  963.  * Each record in this array contains information about a non-contiguous heap area.
  964.  */
  965.  
  966. const int maxHeaps = 32; /* 64 was overkill */
  967. const long lAllocMax   = 0x80000000; /* max size of allocation */
  968.  
  969. #ifdef _USE_BUDDY_BLOCKS
  970. typedef struct _FreeListEntry
  971. {
  972.     BYTE    Dummy[minAllocSize];    // dummy free block
  973. } FREE_LIST_ENTRY, *PFREE_LIST_ENTRY;
  974. #endif
  975.  
  976. #ifndef _USE_BUDDY_BLOCKS
  977. #define USE_BIGBLOCK_ALLOC
  978. #endif
  979. /*
  980.  * performance tuning
  981.  * Use VirtualAlloc() for blocks bigger than nMaxHeapAllocSize since
  982.  * Windows 95/98/Me have heap managers that are designed for memory 
  983.  * blocks smaller than four megabytes.
  984.  */
  985.  
  986. #ifdef USE_BIGBLOCK_ALLOC
  987. const int nMaxHeapAllocSize = (1024*512);  /* don't allocate anything larger than this from the heap */
  988. #endif
  989.  
  990. typedef struct _HeapRec
  991. {
  992.     PBLOCK    base;    /* base of heap area */
  993.     ULONG    len;    /* size of heap area */
  994. #ifdef USE_BIGBLOCK_ALLOC
  995.     BOOL    bBigBlock;  /* was allocate using VirtualAlloc */
  996. #endif
  997. } HeapRec;
  998.  
  999. class VMem
  1000. {
  1001. public:
  1002.     VMem();
  1003.     ~VMem();
  1004.     virtual void* Malloc(size_t size);
  1005.     virtual void* Realloc(void* pMem, size_t size);
  1006.     virtual void Free(void* pMem);
  1007.     virtual void GetLock(void);
  1008.     virtual void FreeLock(void);
  1009.     virtual int IsLocked(void);
  1010.     virtual long Release(void);
  1011.     virtual long AddRef(void);
  1012.  
  1013.     inline BOOL CreateOk(void)
  1014.     {
  1015. #ifdef _USE_BUDDY_BLOCKS
  1016.     return TRUE;
  1017. #else
  1018.     return m_hHeap != NULL;
  1019. #endif
  1020.     };
  1021.  
  1022.     void ReInit(void);
  1023.  
  1024. protected:
  1025.     void Init(void);
  1026.     int Getmem(size_t size);
  1027.  
  1028.     int HeapAdd(void* ptr, size_t size
  1029. #ifdef USE_BIGBLOCK_ALLOC
  1030.     , BOOL bBigBlock
  1031. #endif
  1032.     );
  1033.  
  1034.     void* Expand(void* block, size_t size);
  1035.  
  1036. #ifdef _USE_BUDDY_BLOCKS
  1037.     inline PBLOCK GetFreeListLink(int index)
  1038.     {
  1039.     if (index >= nListEntries)
  1040.         index = nListEntries-1;
  1041.     return &m_FreeList[index].Dummy[sizeofTag];
  1042.     }
  1043.     inline PBLOCK GetOverSizeFreeList(void)
  1044.     {
  1045.     return &m_FreeList[nListEntries-1].Dummy[sizeofTag];
  1046.     }
  1047.     inline PBLOCK GetEOLFreeList(void)
  1048.     {
  1049.     return &m_FreeList[nListEntries].Dummy[sizeofTag];
  1050.     }
  1051.  
  1052.     void AddToFreeList(PBLOCK block, size_t size)
  1053.     {
  1054.     PBLOCK pFreeList = GetFreeListLink(CalcEntry(size));
  1055.     PBLOCK next = NEXT(pFreeList);
  1056.     NEXT(pFreeList) = block;
  1057.     SetLink(block, pFreeList, next);
  1058.     PREV(next) = block;
  1059.     }
  1060. #endif
  1061.     inline size_t CalcAllocSize(size_t size)
  1062.     {
  1063.     /*
  1064.      * Adjust the real size of the block to be a multiple of sizeof(long), and add
  1065.      * the overhead for the boundary tags.  Disallow negative or zero sizes.
  1066.      */
  1067.     return (size < minBlockSize) ? minAllocSize : (size_t)ROUND_UP(size) + blockOverhead;
  1068.     }
  1069.  
  1070. #ifdef _USE_BUDDY_BLOCKS
  1071.     FREE_LIST_ENTRY    m_FreeList[nListEntries+1];    // free list with dummy end of list entry as well
  1072. #else
  1073.     HANDLE        m_hHeap;            // memory heap for this script
  1074.     char        m_FreeDummy[minAllocSize];  // dummy free block
  1075.     PBLOCK        m_pFreeList;            // pointer to first block on free list
  1076. #endif
  1077.     PBLOCK        m_pRover;            // roving pointer into the free list
  1078.     HeapRec        m_heaps[maxHeaps];        // list of all non-contiguous heap areas 
  1079.     int            m_nHeaps;            // no. of heaps in m_heaps 
  1080.     long        m_lAllocSize;            // current alloc size
  1081.     long        m_lRefCount;            // number of current users
  1082.     CRITICAL_SECTION    m_cs;                // access lock
  1083.  
  1084. #ifdef _DEBUG_MEM
  1085.     void WalkHeap(int complete);
  1086.     void MemoryUsageMessage(char *str, long x, long y, int c);
  1087.     FILE*        m_pLog;
  1088. #endif
  1089. };
  1090.  
  1091. VMem::VMem()
  1092. {
  1093.     m_lRefCount = 1;
  1094. #ifndef _USE_BUDDY_BLOCKS
  1095.     BOOL bRet = (NULL != (m_hHeap = HeapCreate(HEAP_NO_SERIALIZE,
  1096.                 lAllocStart,    /* initial size of heap */
  1097.                 0)));        /* no upper limit on size of heap */
  1098.     ASSERT(bRet);
  1099. #endif
  1100.  
  1101.     InitializeCriticalSection(&m_cs);
  1102. #ifdef _DEBUG_MEM
  1103.     m_pLog = 0;
  1104. #endif
  1105.  
  1106.     Init();
  1107. }
  1108.  
  1109. VMem::~VMem(void)
  1110. {
  1111. #ifndef _USE_BUDDY_BLOCKS
  1112.     ASSERT(HeapValidate(m_hHeap, HEAP_NO_SERIALIZE, NULL));
  1113. #endif
  1114.     WALKHEAPTRACE();
  1115.  
  1116.     DeleteCriticalSection(&m_cs);
  1117. #ifdef _USE_BUDDY_BLOCKS
  1118.     for(int index = 0; index < m_nHeaps; ++index) {
  1119.     VirtualFree(m_heaps[index].base, 0, MEM_RELEASE);
  1120.     }
  1121. #else /* !_USE_BUDDY_BLOCKS */
  1122. #ifdef USE_BIGBLOCK_ALLOC
  1123.     for(int index = 0; index < m_nHeaps; ++index) {
  1124.     if (m_heaps[index].bBigBlock) {
  1125.         VirtualFree(m_heaps[index].base, 0, MEM_RELEASE);
  1126.     }
  1127.     }
  1128. #endif
  1129.     BOOL bRet = HeapDestroy(m_hHeap);
  1130.     ASSERT(bRet);
  1131. #endif /* _USE_BUDDY_BLOCKS */
  1132. }
  1133.  
  1134. void VMem::ReInit(void)
  1135. {
  1136.     for(int index = 0; index < m_nHeaps; ++index) {
  1137. #ifdef _USE_BUDDY_BLOCKS
  1138.     VirtualFree(m_heaps[index].base, 0, MEM_RELEASE);
  1139. #else
  1140. #ifdef USE_BIGBLOCK_ALLOC
  1141.     if (m_heaps[index].bBigBlock) {
  1142.         VirtualFree(m_heaps[index].base, 0, MEM_RELEASE);
  1143.     }
  1144.     else
  1145. #endif
  1146.         HeapFree(m_hHeap, HEAP_NO_SERIALIZE, m_heaps[index].base);
  1147. #endif /* _USE_BUDDY_BLOCKS */
  1148.     }
  1149.  
  1150.     Init();
  1151. }
  1152.  
  1153. void VMem::Init(void)
  1154. {
  1155. #ifdef _USE_BUDDY_BLOCKS
  1156.     PBLOCK pFreeList;
  1157.     /*
  1158.      * Initialize the free list by placing a dummy zero-length block on it.
  1159.      * Set the end of list marker.
  1160.      * Set the number of non-contiguous heaps to zero.
  1161.      * Set the next allocation size.
  1162.      */
  1163.     for (int index = 0; index < nListEntries; ++index) {
  1164.     pFreeList = GetFreeListLink(index);
  1165.     SIZE(pFreeList) = PSIZE(pFreeList+minAllocSize) = 0;
  1166.     PREV(pFreeList) = NEXT(pFreeList) = pFreeList;
  1167.     }
  1168.     pFreeList = GetEOLFreeList();
  1169.     SIZE(pFreeList) = PSIZE(pFreeList+minAllocSize) = 0;
  1170.     PREV(pFreeList) = NEXT(pFreeList) = NULL;
  1171.     m_pRover = GetOverSizeFreeList();
  1172. #else
  1173.     /*
  1174.      * Initialize the free list by placing a dummy zero-length block on it.
  1175.      * Set the number of non-contiguous heaps to zero.
  1176.      */
  1177.     m_pFreeList = m_pRover = (PBLOCK)(&m_FreeDummy[sizeofTag]);
  1178.     PSIZE(m_pFreeList+minAllocSize) = SIZE(m_pFreeList) = 0;
  1179.     PREV(m_pFreeList) = NEXT(m_pFreeList) = m_pFreeList;
  1180. #endif
  1181.  
  1182.     m_nHeaps = 0;
  1183.     m_lAllocSize = lAllocStart;
  1184. }
  1185.  
  1186. void* VMem::Malloc(size_t size)
  1187. {
  1188.     WALKHEAP();
  1189.  
  1190.     PBLOCK ptr;
  1191.     size_t lsize, rem;
  1192.     /*
  1193.      * Disallow negative or zero sizes.
  1194.      */
  1195.     size_t realsize = CalcAllocSize(size);
  1196.     if((int)realsize < minAllocSize || size == 0)
  1197.     return NULL;
  1198.  
  1199. #ifdef _USE_BUDDY_BLOCKS
  1200.     /*
  1201.      * Check the free list of small blocks if this is free use it
  1202.      * Otherwise check the rover if it has no blocks then
  1203.      * Scan the free list entries use the first free block
  1204.      * split the block if needed, stop at end of list marker
  1205.      */
  1206.     {
  1207.     int index = CalcEntry(realsize);
  1208.     if (index < nListEntries-1) {
  1209.         ptr = GetFreeListLink(index);
  1210.         lsize = SIZE(ptr);
  1211.         if (lsize >= realsize) {
  1212.         rem = lsize - realsize;
  1213.         if(rem < minAllocSize) {
  1214.             /* Unlink the block from the free list. */
  1215.             Unlink(ptr);
  1216.         }
  1217.         else {
  1218.             /*
  1219.              * split the block
  1220.              * The remainder is big enough to split off into a new block.
  1221.              * Use the end of the block, resize the beginning of the block
  1222.              * no need to change the free list.
  1223.              */
  1224.             SetTags(ptr, rem);
  1225.             ptr += SIZE(ptr);
  1226.             lsize = realsize;
  1227.         }
  1228.         SetTags(ptr, lsize | 1);
  1229.         return ptr;
  1230.         }
  1231.         ptr = m_pRover;
  1232.         lsize = SIZE(ptr);
  1233.         if (lsize >= realsize) {
  1234.         rem = lsize - realsize;
  1235.         if(rem < minAllocSize) {
  1236.             /* Unlink the block from the free list. */
  1237.             Unlink(ptr);
  1238.         }
  1239.         else {
  1240.             /*
  1241.              * split the block
  1242.              * The remainder is big enough to split off into a new block.
  1243.              * Use the end of the block, resize the beginning of the block
  1244.              * no need to change the free list.
  1245.              */
  1246.             SetTags(ptr, rem);
  1247.             ptr += SIZE(ptr);
  1248.             lsize = realsize;
  1249.         }
  1250.         SetTags(ptr, lsize | 1);
  1251.         return ptr;
  1252.         }
  1253.         ptr = GetFreeListLink(index+1);
  1254.         while (NEXT(ptr)) {
  1255.         lsize = SIZE(ptr);
  1256.         if (lsize >= realsize) {
  1257.             size_t rem = lsize - realsize;
  1258.             if(rem < minAllocSize) {
  1259.             /* Unlink the block from the free list. */
  1260.             Unlink(ptr);
  1261.             }
  1262.             else {
  1263.             /*
  1264.              * split the block
  1265.              * The remainder is big enough to split off into a new block.
  1266.              * Use the end of the block, resize the beginning of the block
  1267.              * no need to change the free list.
  1268.              */
  1269.             SetTags(ptr, rem);
  1270.             ptr += SIZE(ptr);
  1271.             lsize = realsize;
  1272.             }
  1273.             SetTags(ptr, lsize | 1);
  1274.             return ptr;
  1275.         }
  1276.         ptr += sizeof(FREE_LIST_ENTRY);
  1277.         }
  1278.     }
  1279.     }
  1280. #endif
  1281.  
  1282.     /*
  1283.      * Start searching the free list at the rover.  If we arrive back at rover without
  1284.      * finding anything, allocate some memory from the heap and try again.
  1285.      */
  1286.     ptr = m_pRover;    /* start searching at rover */
  1287.     int loops = 2;    /* allow two times through the loop  */
  1288.     for(;;) {
  1289.     lsize = SIZE(ptr);
  1290.     ASSERT((lsize&1)==0);
  1291.     /* is block big enough? */
  1292.     if(lsize >= realsize) {    
  1293.         /* if the remainder is too small, don't bother splitting the block. */
  1294.         rem = lsize - realsize;
  1295.         if(rem < minAllocSize) {
  1296.         if(m_pRover == ptr)
  1297.             m_pRover = NEXT(ptr);
  1298.  
  1299.         /* Unlink the block from the free list. */
  1300.         Unlink(ptr);
  1301.         }
  1302.         else {
  1303.         /*
  1304.          * split the block
  1305.          * The remainder is big enough to split off into a new block.
  1306.          * Use the end of the block, resize the beginning of the block
  1307.          * no need to change the free list.
  1308.          */
  1309.         SetTags(ptr, rem);
  1310.         ptr += SIZE(ptr);
  1311.         lsize = realsize;
  1312.         }
  1313.         /* Set the boundary tags to mark it as allocated. */
  1314.         SetTags(ptr, lsize | 1);
  1315.         return ((void *)ptr);
  1316.     }
  1317.  
  1318.     /*
  1319.      * This block was unsuitable.  If we've gone through this list once already without
  1320.      * finding anything, allocate some new memory from the heap and try again.
  1321.      */
  1322.     ptr = NEXT(ptr);
  1323.     if(ptr == m_pRover) {
  1324.         if(!(loops-- && Getmem(realsize))) {
  1325.         return NULL;
  1326.         }
  1327.         ptr = m_pRover;
  1328.     }
  1329.     }
  1330. }
  1331.  
  1332. void* VMem::Realloc(void* block, size_t size)
  1333. {
  1334.     WALKHEAP();
  1335.  
  1336.     /* if size is zero, free the block. */
  1337.     if(size == 0) {
  1338.     Free(block);
  1339.     return (NULL);
  1340.     }
  1341.  
  1342.     /* if block pointer is NULL, do a Malloc(). */
  1343.     if(block == NULL)
  1344.     return Malloc(size);
  1345.  
  1346.     /*
  1347.      * Grow or shrink the block in place.
  1348.      * if the block grows then the next block will be used if free
  1349.      */
  1350.     if(Expand(block, size) != NULL)
  1351.     return block;
  1352.  
  1353.     size_t realsize = CalcAllocSize(size);
  1354.     if((int)realsize < minAllocSize)
  1355.     return NULL;
  1356.  
  1357.     /*
  1358.      * see if the previous block is free, and is it big enough to cover the new size
  1359.      * if merged with the current block.
  1360.      */
  1361.     PBLOCK ptr = (PBLOCK)block;
  1362.     size_t cursize = SIZE(ptr) & ~1;
  1363.     size_t psize = PSIZE(ptr);
  1364.     if((psize&1) == 0 && (psize + cursize) >= realsize) {
  1365.     PBLOCK prev = ptr - psize;
  1366.     if(m_pRover == prev)
  1367.         m_pRover = NEXT(prev);
  1368.  
  1369.     /* Unlink the next block from the free list. */
  1370.     Unlink(prev);
  1371.  
  1372.     /* Copy contents of old block to new location, make it the current block. */
  1373.     memmove(prev, ptr, cursize);
  1374.     cursize += psize;    /* combine sizes */
  1375.     ptr = prev;
  1376.  
  1377.     size_t rem = cursize - realsize;
  1378.     if(rem >= minAllocSize) {
  1379.         /*
  1380.          * The remainder is big enough to be a new block.  Set boundary
  1381.          * tags for the resized block and the new block.
  1382.          */
  1383.         prev = ptr + realsize;
  1384.         /*
  1385.          * add the new block to the free list.
  1386.          * next block cannot be free
  1387.          */
  1388.         SetTags(prev, rem);
  1389. #ifdef _USE_BUDDY_BLOCKS
  1390.         AddToFreeList(prev, rem);
  1391. #else
  1392.         AddToFreeList(prev, m_pFreeList);
  1393. #endif
  1394.         cursize = realsize;
  1395.         }
  1396.     /* Set the boundary tags to mark it as allocated. */
  1397.     SetTags(ptr, cursize | 1);
  1398.         return ((void *)ptr);
  1399.     }
  1400.  
  1401.     /* Allocate a new block, copy the old to the new, and free the old. */
  1402.     if((ptr = (PBLOCK)Malloc(size)) != NULL) {
  1403.     memmove(ptr, block, cursize-blockOverhead);
  1404.     Free(block);
  1405.     }
  1406.     return ((void *)ptr);
  1407. }
  1408.  
  1409. void VMem::Free(void* p)
  1410. {
  1411.     WALKHEAP();
  1412.  
  1413.     /* Ignore null pointer. */
  1414.     if(p == NULL)
  1415.     return;
  1416.  
  1417.     PBLOCK ptr = (PBLOCK)p;
  1418.  
  1419.     /* Check for attempt to free a block that's already free. */
  1420.     size_t size = SIZE(ptr);
  1421.     if((size&1) == 0) {
  1422.     MEMODSlx("Attempt to free previously freed block", (long)p);
  1423.     return;
  1424.     }
  1425.     size &= ~1;    /* remove allocated tag */
  1426.  
  1427.     /* if previous block is free, add this block to it. */
  1428. #ifndef _USE_BUDDY_BLOCKS
  1429.     int linked = FALSE;
  1430. #endif
  1431.     size_t psize = PSIZE(ptr);
  1432.     if((psize&1) == 0) {
  1433.     ptr -= psize;    /* point to previous block */
  1434.     size += psize;    /* merge the sizes of the two blocks */
  1435. #ifdef _USE_BUDDY_BLOCKS
  1436.     Unlink(ptr);
  1437. #else
  1438.     linked = TRUE;    /* it's already on the free list */
  1439. #endif
  1440.     }
  1441.  
  1442.     /* if the next physical block is free, merge it with this block. */
  1443.     PBLOCK next = ptr + size;    /* point to next physical block */
  1444.     size_t nsize = SIZE(next);
  1445.     if((nsize&1) == 0) {
  1446.     /* block is free move rover if needed */
  1447.     if(m_pRover == next)
  1448.         m_pRover = NEXT(next);
  1449.  
  1450.     /* unlink the next block from the free list. */
  1451.     Unlink(next);
  1452.  
  1453.     /* merge the sizes of this block and the next block. */
  1454.     size += nsize;
  1455.     }
  1456.  
  1457.     /* Set the boundary tags for the block; */
  1458.     SetTags(ptr, size);
  1459.  
  1460.     /* Link the block to the head of the free list. */
  1461. #ifdef _USE_BUDDY_BLOCKS
  1462.     AddToFreeList(ptr, size);
  1463. #else
  1464.     if(!linked) {
  1465.     AddToFreeList(ptr, m_pFreeList);
  1466.     }
  1467. #endif
  1468. }
  1469.  
  1470. int VMem::Getmem(size_t requestSize)
  1471. {   /* returns -1 is successful 0 if not */
  1472. #ifdef USE_BIGBLOCK_ALLOC
  1473.     BOOL bBigBlock;
  1474. #endif
  1475.     void *ptr;
  1476.  
  1477.     /* Round up size to next multiple of 64K. */
  1478.     size_t size = (size_t)ROUND_UP64K(requestSize);
  1479.  
  1480.     /*
  1481.      * if the size requested is smaller than our current allocation size
  1482.      * adjust up
  1483.      */
  1484.     if(size < (unsigned long)m_lAllocSize)
  1485.     size = m_lAllocSize;
  1486.  
  1487.     /* Update the size to allocate on the next request */
  1488.     if(m_lAllocSize != lAllocMax)
  1489.     m_lAllocSize <<= 2;
  1490.  
  1491. #ifndef _USE_BUDDY_BLOCKS
  1492.     if(m_nHeaps != 0
  1493. #ifdef USE_BIGBLOCK_ALLOC
  1494.     && !m_heaps[m_nHeaps-1].bBigBlock
  1495. #endif
  1496.             ) {
  1497.     /* Expand the last allocated heap */
  1498.     ptr = HeapReAlloc(m_hHeap, HEAP_REALLOC_IN_PLACE_ONLY|HEAP_NO_SERIALIZE,
  1499.         m_heaps[m_nHeaps-1].base,
  1500.         m_heaps[m_nHeaps-1].len + size);
  1501.     if(ptr != 0) {
  1502.         HeapAdd(((char*)ptr) + m_heaps[m_nHeaps-1].len, size
  1503. #ifdef USE_BIGBLOCK_ALLOC
  1504.         , FALSE
  1505. #endif
  1506.         );
  1507.         return -1;
  1508.     }
  1509.     }
  1510. #endif /* _USE_BUDDY_BLOCKS */
  1511.  
  1512.     /*
  1513.      * if we didn't expand a block to cover the requested size
  1514.      * allocate a new Heap
  1515.      * the size of this block must include the additional dummy tags at either end
  1516.      * the above ROUND_UP64K may not have added any memory to include this.
  1517.      */
  1518.     if(size == requestSize)
  1519.     size = (size_t)ROUND_UP64K(requestSize+(blockOverhead));
  1520.  
  1521. Restart:
  1522. #ifdef _USE_BUDDY_BLOCKS
  1523.     ptr = VirtualAlloc(NULL, size, MEM_COMMIT, PAGE_READWRITE);
  1524. #else
  1525. #ifdef USE_BIGBLOCK_ALLOC
  1526.     bBigBlock = FALSE;
  1527.     if (size >= nMaxHeapAllocSize) {
  1528.     bBigBlock = TRUE;
  1529.     ptr = VirtualAlloc(NULL, size, MEM_COMMIT, PAGE_READWRITE);
  1530.     }
  1531.     else
  1532. #endif
  1533.     ptr = HeapAlloc(m_hHeap, HEAP_NO_SERIALIZE, size);
  1534. #endif /* _USE_BUDDY_BLOCKS */
  1535.  
  1536.     if (!ptr) {
  1537.     /* try to allocate a smaller chunk */
  1538.     size >>= 1;
  1539.     if(size > requestSize)
  1540.         goto Restart;
  1541.     }
  1542.  
  1543.     if(ptr == 0) {
  1544.     MEMODSlx("HeapAlloc failed on size!!!", size);
  1545.     return 0;
  1546.     }
  1547.  
  1548. #ifdef _USE_BUDDY_BLOCKS
  1549.     if (HeapAdd(ptr, size)) {
  1550.     VirtualFree(ptr, 0, MEM_RELEASE);
  1551.     return 0;
  1552.     }
  1553. #else
  1554. #ifdef USE_BIGBLOCK_ALLOC
  1555.     if (HeapAdd(ptr, size, bBigBlock)) {
  1556.     if (bBigBlock) {
  1557.         VirtualFree(ptr, 0, MEM_RELEASE);
  1558.     }
  1559.     }
  1560. #else
  1561.     HeapAdd(ptr, size);
  1562. #endif
  1563. #endif /* _USE_BUDDY_BLOCKS */
  1564.     return -1;
  1565. }
  1566.  
  1567. int VMem::HeapAdd(void* p, size_t size
  1568. #ifdef USE_BIGBLOCK_ALLOC
  1569.     , BOOL bBigBlock
  1570. #endif
  1571.     )
  1572. {   /* if the block can be succesfully added to the heap, returns 0; otherwise -1. */
  1573.     int index;
  1574.  
  1575.     /* Check size, then round size down to next long word boundary. */
  1576.     if(size < minAllocSize)
  1577.     return -1;
  1578.  
  1579.     size = (size_t)ROUND_DOWN(size);
  1580.     PBLOCK ptr = (PBLOCK)p;
  1581.  
  1582. #ifdef USE_BIGBLOCK_ALLOC
  1583.     if (!bBigBlock) {
  1584. #endif
  1585.     /*
  1586.      * Search for another heap area that's contiguous with the bottom of this new area.
  1587.      * (It should be extremely unusual to find one that's contiguous with the top).
  1588.      */
  1589.     for(index = 0; index < m_nHeaps; ++index) {
  1590.         if(ptr == m_heaps[index].base + (int)m_heaps[index].len) {
  1591.         /*
  1592.          * The new block is contiguous with a previously allocated heap area.  Add its
  1593.          * length to that of the previous heap.  Merge it with the the dummy end-of-heap
  1594.          * area marker of the previous heap.
  1595.          */
  1596.         m_heaps[index].len += size;
  1597.         break;
  1598.         }
  1599.     }
  1600. #ifdef USE_BIGBLOCK_ALLOC
  1601.     }
  1602.     else {
  1603.     index = m_nHeaps;
  1604.     }
  1605. #endif
  1606.  
  1607.     if(index == m_nHeaps) {
  1608.     /* The new block is not contiguous, or is BigBlock.  Add it to the heap list. */
  1609.     if(m_nHeaps == maxHeaps) {
  1610.         return -1;    /* too many non-contiguous heaps */
  1611.     }
  1612.     m_heaps[m_nHeaps].base = ptr;
  1613.     m_heaps[m_nHeaps].len = size;
  1614. #ifdef USE_BIGBLOCK_ALLOC
  1615.     m_heaps[m_nHeaps].bBigBlock = bBigBlock;
  1616. #endif
  1617.     m_nHeaps++;
  1618.  
  1619.     /*
  1620.      * Reserve the first LONG in the block for the ending boundary tag of a dummy
  1621.      * block at the start of the heap area.
  1622.      */
  1623.     size -= blockOverhead;
  1624.     ptr += blockOverhead;
  1625.     PSIZE(ptr) = 1;    /* mark the dummy previous block as allocated */
  1626.     }
  1627.  
  1628.     /*
  1629.      * Convert the heap to one large block.  Set up its boundary tags, and those of
  1630.      * marker block after it.  The marker block before the heap will already have
  1631.      * been set up if this heap is not contiguous with the end of another heap.
  1632.      */
  1633.     SetTags(ptr, size | 1);
  1634.     PBLOCK next = ptr + size;    /* point to dummy end block */
  1635.     SIZE(next) = 1;    /* mark the dummy end block as allocated */
  1636.  
  1637.     /*
  1638.      * Link the block to the start of the free list by calling free().
  1639.      * This will merge the block with any adjacent free blocks.
  1640.      */
  1641.     Free(ptr);
  1642.     return 0;
  1643. }
  1644.  
  1645. void* VMem::Expand(void* block, size_t size)
  1646. {
  1647.     /*
  1648.      * Disallow negative or zero sizes.
  1649.      */
  1650.     size_t realsize = CalcAllocSize(size);
  1651.     if((int)realsize < minAllocSize || size == 0)
  1652.     return NULL;
  1653.  
  1654.     PBLOCK ptr = (PBLOCK)block; 
  1655.  
  1656.     /* if the current size is the same as requested, do nothing. */
  1657.     size_t cursize = SIZE(ptr) & ~1;
  1658.     if(cursize == realsize) {
  1659.     return block;
  1660.     }
  1661.  
  1662.     /* if the block is being shrunk, convert the remainder of the block into a new free block. */
  1663.     if(realsize <= cursize) {
  1664.     size_t nextsize = cursize - realsize;    /* size of new remainder block */
  1665.     if(nextsize >= minAllocSize) {
  1666.         /*
  1667.          * Split the block
  1668.          * Set boundary tags for the resized block and the new block.
  1669.          */
  1670.         SetTags(ptr, realsize | 1);
  1671.         ptr += realsize;
  1672.  
  1673.         /*
  1674.          * add the new block to the free list.
  1675.          * call Free to merge this block with next block if free
  1676.          */
  1677.         SetTags(ptr, nextsize | 1);
  1678.         Free(ptr);
  1679.     }
  1680.  
  1681.     return block;
  1682.     }
  1683.  
  1684.     PBLOCK next = ptr + cursize;
  1685.     size_t nextsize = SIZE(next);
  1686.  
  1687.     /* Check the next block for consistency.*/
  1688.     if((nextsize&1) == 0 && (nextsize + cursize) >= realsize) {
  1689.     /*
  1690.      * The next block is free and big enough.  Add the part that's needed
  1691.      * to our block, and split the remainder off into a new block.
  1692.      */
  1693.     if(m_pRover == next)
  1694.         m_pRover = NEXT(next);
  1695.  
  1696.     /* Unlink the next block from the free list. */
  1697.     Unlink(next);
  1698.     cursize += nextsize;    /* combine sizes */
  1699.  
  1700.     size_t rem = cursize - realsize;    /* size of remainder */
  1701.     if(rem >= minAllocSize) {
  1702.         /*
  1703.          * The remainder is big enough to be a new block.
  1704.          * Set boundary tags for the resized block and the new block.
  1705.          */
  1706.         next = ptr + realsize;
  1707.         /*
  1708.          * add the new block to the free list.
  1709.          * next block cannot be free
  1710.          */
  1711.         SetTags(next, rem);
  1712. #ifdef _USE_BUDDY_BLOCKS
  1713.         AddToFreeList(next, rem);
  1714. #else
  1715.         AddToFreeList(next, m_pFreeList);
  1716. #endif
  1717.         cursize = realsize;
  1718.         }
  1719.     /* Set the boundary tags to mark it as allocated. */
  1720.     SetTags(ptr, cursize | 1);
  1721.     return ((void *)ptr);
  1722.     }
  1723.     return NULL;
  1724. }
  1725.  
  1726. #endif /* _USE_EXERCISE_19 */
  1727.  
  1728. #ifdef _DEBUG_MEM
  1729. #define LOG_FILENAME ".\\MemLog.txt"
  1730.  
  1731. void VMem::MemoryUsageMessage(char* str, long x, long y, int c)
  1732. {
  1733.     char szBuffer[512];
  1734.     if(str) {
  1735.     if(!m_pLog)
  1736.         m_pLog = fopen(LOG_FILENAME, "w");
  1737.     sprintf(szBuffer, str, x, y, c);
  1738.     fputs(szBuffer, m_pLog);
  1739.     }
  1740.     else {
  1741.     if(m_pLog) {
  1742.         fflush(m_pLog);
  1743.         fclose(m_pLog);
  1744.         m_pLog = 0;
  1745.     }
  1746.     }
  1747. }
  1748.  
  1749. #ifdef _USE_EXERCISE_19
  1750. void VMem::WalkHeap(int complete)
  1751. {
  1752.     if(complete && m_pHeaps) {
  1753.     PHEAP pHeap;
  1754.  
  1755.     MemoryUsageMessage(NULL, 0, 0, 0);
  1756.  
  1757.     /* Walk all the heaps - verify structures */
  1758.     for (pHeap = m_pHeaps; pHeap; pHeap = pHeap->pNextHeap) {
  1759.         MemoryUsageMessage("Heaps at %08x. has %d blocks\n", (long)pHeap, pHeap->memBlockCount, 0);
  1760.         
  1761.         ASSERT(pHeap->commitSize <= pHeap->reserveSize);
  1762.         PBLOCKTAG pBlock = FirstHeapBlock(pHeap);
  1763.         PBLOCKTAG lastBlock = LastHeapBlock(pHeap);
  1764.         
  1765.         MemoryUsageMessage("First memory block %08x: Last memory block %08x\n", (long)pBlock, (long)lastBlock, 0);
  1766.         
  1767.         ASSERT(!SIZE(pBlock));
  1768.         ASSERT(!SIZE(lastBlock));
  1769.         while (pBlock != lastBlock) {
  1770.         if (ISFREE(pBlock)) {
  1771.             PBLOCKTAG pFreeBlock, pStart;
  1772.             ASSERT(ISPREVFREE(NEXT(pBlock)));
  1773.             ULONG cursize = SIZE(pBlock);
  1774.             pStart = (cursize < nBuddyBlockSize) ? GetFreeListLink(cursize) : m_pRover;
  1775.             for (pFreeBlock = pStart->pNextFree; pFreeBlock != pStart; pFreeBlock = pFreeBlock->pNextFree) {
  1776.             if (pFreeBlock == pBlock)
  1777.                 break;
  1778.             }
  1779.             if (pFreeBlock != pBlock)
  1780.             MemoryUsageMessage("Memory Block %08x: Size %08x free but not in free list\n", (long)pBlock, cursize, 0);
  1781.         }
  1782.         pBlock = NEXT(pBlock);
  1783.         }
  1784.     }
  1785.     MemoryUsageMessage(NULL, 0, 0, 0);
  1786.     }
  1787. }
  1788.  
  1789. #else  /* _USE_EXERCISE_19 */
  1790.  
  1791. void VMem::WalkHeap(int complete)
  1792. {
  1793.     if(complete) {
  1794.     MemoryUsageMessage(NULL, 0, 0, 0);
  1795.     size_t total = 0;
  1796.     for(int i = 0; i < m_nHeaps; ++i) {
  1797.         total += m_heaps[i].len;
  1798.     }
  1799.     MemoryUsageMessage("VMem heaps used %d. Total memory %08x\n", m_nHeaps, total, 0);
  1800.  
  1801.     /* Walk all the heaps - verify structures */
  1802.     for(int index = 0; index < m_nHeaps; ++index) {
  1803.         PBLOCK ptr = m_heaps[index].base;
  1804.         size_t size = m_heaps[index].len;
  1805. #ifndef _USE_BUDDY_BLOCKS
  1806. #ifdef USE_BIGBLOCK_ALLOC
  1807.         if (!m_heaps[m_nHeaps].bBigBlock)
  1808. #endif
  1809.         ASSERT(HeapValidate(m_hHeap, HEAP_NO_SERIALIZE, ptr));
  1810. #endif
  1811.  
  1812.         /* set over reserved header block */
  1813.         size -= blockOverhead;
  1814.         ptr += blockOverhead;
  1815.         PBLOCK pLast = ptr + size;
  1816.         ASSERT(PSIZE(ptr) == 1); /* dummy previous block is allocated */
  1817.         ASSERT(SIZE(pLast) == 1); /* dummy next block is allocated */
  1818.         while(ptr < pLast) {
  1819.         ASSERT(ptr > m_heaps[index].base);
  1820.         size_t cursize = SIZE(ptr) & ~1;
  1821.         ASSERT((PSIZE(ptr+cursize) & ~1) == cursize);
  1822.         MemoryUsageMessage("Memory Block %08x: Size %08x %c\n", (long)ptr, cursize, (SIZE(ptr)&1) ? 'x' : ' ');
  1823.         if(!(SIZE(ptr)&1)) {
  1824.             /* this block is on the free list */
  1825.             PBLOCK tmp = NEXT(ptr);
  1826.             while(tmp != ptr) {
  1827.             ASSERT((SIZE(tmp)&1)==0);
  1828.             if(tmp == m_pFreeList)
  1829.                 break;
  1830.             ASSERT(NEXT(tmp));
  1831.             tmp = NEXT(tmp);
  1832.             }
  1833.             if(tmp == ptr) {
  1834.             MemoryUsageMessage("Memory Block %08x: Size %08x free but not in free list\n", (long)ptr, cursize, 0);
  1835.             }
  1836.         }
  1837.         ptr += cursize;
  1838.         }
  1839.     }
  1840.     MemoryUsageMessage(NULL, 0, 0, 0);
  1841.     }
  1842. }
  1843. #endif  /* _USE_EXERCISE_19 */
  1844. #endif    /* _DEBUG_MEM */
  1845.  
  1846. #endif    /* _USE_MSVCRT_MEM_ALLOC */
  1847.  
  1848. void VMem::GetLock(void)
  1849. {
  1850.     EnterCriticalSection(&m_cs);
  1851. }
  1852.  
  1853. void VMem::FreeLock(void)
  1854. {
  1855.     LeaveCriticalSection(&m_cs);
  1856. }
  1857.  
  1858. int VMem::IsLocked(void)
  1859. {
  1860. #if 0
  1861.     /* XXX TryEnterCriticalSection() is not available in some versions
  1862.      * of Windows 95.  Since this code is not used anywhere yet, we 
  1863.      * skirt the issue for now. */
  1864.     BOOL bAccessed = TryEnterCriticalSection(&m_cs);
  1865.     if(bAccessed) {
  1866.     LeaveCriticalSection(&m_cs);
  1867.     }
  1868.     return !bAccessed;
  1869. #else
  1870.     ASSERT(0);    /* alarm bells for when somebody calls this */
  1871.     return 0;
  1872. #endif
  1873. }
  1874.  
  1875. long VMem::Release(void)
  1876. {
  1877.     long lCount = InterlockedDecrement(&m_lRefCount);
  1878.     if(!lCount)
  1879.     delete this;
  1880.     return lCount;
  1881. }
  1882.  
  1883. long VMem::AddRef(void)
  1884. {
  1885.     long lCount = InterlockedIncrement(&m_lRefCount);
  1886.     return lCount;
  1887. }
  1888.  
  1889. #endif    /* ___VMEM_H_INC___ */
  1890.