home *** CD-ROM | disk | FTP | other *** search
/ Power-Programmierung / CD2.mdf / c / library / mslang / vm / src / vmlist.c < prev    next >
Encoding:
C/C++ Source or Header  |  1993-12-15  |  5.8 KB  |  262 lines
  1. /***
  2. *vmlist.c - Free List Maintenance
  3. *
  4. *       Copyright (c) 1992, Microsoft Corporation.  All rights reserved.
  5. *
  6. *Purpose: Generic circular free list.
  7. *
  8. *******************************************************************************/
  9.  
  10. #include <version.h>
  11. #include <vmassert.h>
  12. #include <system.h>
  13. #include <error.h>
  14. #include <vm.h>
  15. #include <vmp.h>
  16. #include <vmlist.h>
  17.  
  18. #define max(A,B) ((A) > (B) ? (A) : (B))
  19.  
  20. #ifdef VMDEBUG
  21.  
  22. void PRIVATE __VmCheckFreeBlock( PFBD pfbdHead )
  23. {
  24.     PFBD pfbd1 = pfbdHead;
  25.     PFBD pfbd2;
  26.  
  27.     if (pfbd1 == pfbdNil)
  28.         return;
  29.  
  30.     pfbd2 = pfbd1->next;
  31.  
  32.     while (pfbd1 != pfbdNil)
  33.     {
  34.         Assert(pfbd1->cPage > 0);
  35.  
  36.         Assert(pfbd1->cbOffset % cbVmPage == 0);
  37.  
  38.         Assert(!pfbd2 ||
  39.             pfbd1->cbOffset+pfbd1->cPage*cbVmPage <= pfbd2->cbOffset);
  40.  
  41.         pfbd1 = pfbd2;
  42.         if (pfbd2 != pfbdNil)
  43.             pfbd2 = pfbd2->next;
  44.     }
  45. }
  46.  
  47. #endif /*VMDEBUG*/
  48.  
  49.  
  50. unsigned long PRIVATE __VmGetFreeMax(PFBD pfbdHead)
  51. {
  52.     PFBD pfbd = pfbdHead;
  53.     unsigned long cMax = 0L;
  54.  
  55.     while (pfbd != pfbdNil)
  56.     {
  57.         cMax = max(cMax, pfbd->cPage);
  58.         pfbd = pfbd->next;
  59.     }
  60.     return cMax;
  61. }
  62.  
  63.  
  64. // Keep "circular" linked list, start from the next block after last
  65. // allocation - avoid small unusable blocks at start of linear list
  66.  
  67. int PUBLIC __VmGetFreeBlock(
  68. PFBD *pfbdHead,
  69. PFBD *pfbdCurr,
  70. unsigned long *cMax,
  71. unsigned long cPage,
  72. unsigned long *cbOffset)
  73. {
  74.     PFBD pfbd1, pfbd2;
  75.  
  76.     VmTracePrintf(("VpGetFreeBlock: cPage=%08lX *cMax=%08lX.\n", cPage, *cMax));
  77.  
  78. #ifdef VMDEBUG
  79.     __VmCheckFreeBlock(*pfbdHead);
  80. #endif /*VMDEBUG*/
  81.  
  82.     if (*pfbdHead == pfbdNil)
  83.         return 0;
  84.  
  85.     // we start loking at the node after curr 
  86.     pfbd1 = *pfbdCurr;
  87.     pfbd2 = ((*pfbdCurr)->next != pfbdNil) ? (*pfbdCurr)->next : *pfbdHead;
  88.  
  89.     // in this while loop, pfbd2 always points to the node of interest, and
  90.     // pfbd1 trails to allow chain fixup. We start at the node after curr and 
  91.     // go circularly until we find a big enough space (first fit) or go full
  92.     // circle
  93.  
  94.     while (1)
  95.     {
  96.         // found a free block that is bigger than we need
  97.         if (cPage < pfbd2->cPage)
  98.         {
  99.             *cbOffset = pfbd2->cbOffset;
  100.             pfbd2->cPage -= cPage;
  101.             pfbd2->cbOffset += cPage * cbVmPage;
  102.             *pfbdCurr = pfbd2;
  103.             *cMax = __VmGetFreeMax(*pfbdHead);
  104.             return 1;
  105.         }
  106.         //      found a free block that is exactly the right size
  107.         if (cPage == pfbd2->cPage)
  108.         {
  109.             *cbOffset = pfbd2->cbOffset;
  110.             
  111.             if (pfbd2 == *pfbdHead) // remove head of list
  112.                 *pfbdHead = (*pfbdHead)->next;
  113.             else // remove from middle
  114.                 pfbd1->next = pfbd2->next;
  115.  
  116.             // adust current to node after current allocation
  117.             *pfbdCurr = (pfbd2->next != pfbdNil) ? pfbd2->next : *pfbdHead;
  118.             _VmFree(pfbd2);
  119.             *cMax = __VmGetFreeMax(*pfbdHead);
  120.             return 1;
  121.         }
  122.         // done the loop, no blocks big enough
  123.         if (pfbd2 == *pfbdCurr)
  124.             return 0;
  125.  
  126.         pfbd1 = pfbd2;
  127.         pfbd2 = (pfbd2->next != pfbdNil) ? pfbd2->next : *pfbdHead;
  128.     }
  129.     return 0;
  130. }
  131.  
  132.  
  133. // This routine adds a new free block descriptor to the linked list.
  134. // It uses two pointers to scan the list until the proper place is found.
  135. // New block is merged with old blocks when appropriate.
  136.  
  137. int PUBLIC __VmAddFreeBlock(
  138. PFBD *pfbdHead,
  139. PFBD *pfbdCurr,
  140. unsigned long *cMax,
  141. unsigned long cPage,
  142. unsigned long cbOffset )
  143. {
  144.     PFBD pfbd1, pfbd2;
  145.  
  146.     VmTracePrintf(("VpAddFreeBlock: cPage=%08lX cbOffset=%08lX.\n", cPage, cbOffset));
  147.  
  148. #ifdef VMDEBUG
  149.     __VmCheckFreeBlock(*pfbdHead);
  150. #endif /*VMDEBUG*/
  151.  
  152.     // empty list
  153.     if (*pfbdHead == pfbdNil)
  154.     {
  155.         if (!(*pfbdHead = *pfbdCurr = (PFBD)_VmMalloc(sizeof(FBD))))
  156.             return 0;
  157.         (*pfbdHead)->cPage = cPage;
  158.         *cMax = (*pfbdHead)->cPage;
  159.         (*pfbdHead)->cbOffset = cbOffset;
  160.         (*pfbdHead)->next = pfbdNil;
  161.         return 1;
  162.     }
  163.  
  164.     // new first item in list
  165.     if (cbOffset + cPage * cbVmPage < (*pfbdHead)->cbOffset)
  166.     {
  167.         if (!(pfbd1 = (PFBD)_VmMalloc(sizeof(FBD))))
  168.             return 0;
  169.         pfbd1->cPage = cPage;
  170.         *cMax = max(*cMax, pfbd1->cPage);
  171.         pfbd1->cbOffset = cbOffset;
  172.         pfbd1->next = *pfbdHead;
  173.         *pfbdHead = pfbd1;
  174.         return 1;
  175.     }
  176.  
  177.     // merge with first item in list
  178.     if (cbOffset + cPage * cbVmPage == (*pfbdHead)->cbOffset)
  179.     {
  180.         (*pfbdHead)->cbOffset = cbOffset;
  181.         (*pfbdHead)->cPage += cPage;
  182.         *cMax = max(*cMax, (*pfbdHead)->cPage);
  183.         return 1;
  184.     }
  185.  
  186.     // new block must go after first item in list
  187.     pfbd1 = *pfbdHead;
  188.     pfbd2 = (*pfbdHead)->next;
  189.  
  190.     while (1) {
  191.         // if we haven't found the proper place, keep moving
  192.         if (pfbd2 != pfbdNil && cbOffset > pfbd2->cbOffset)
  193.         {
  194.             pfbd1 = pfbd2;
  195.             pfbd2 = pfbd2->next;
  196.             continue;
  197.         }
  198.  
  199.         // place new node after pfbd1 in list, pfbd2 may be == pfbdNil
  200.  
  201.         // merge with previous block
  202.         if (pfbd1->cbOffset + pfbd1->cPage * cbVmPage == cbOffset)
  203.         {
  204.             pfbd1->cPage += cPage;
  205.             
  206.             // also merge with next block
  207.             if (cbOffset + cPage * cbVmPage == pfbd2->cbOffset)
  208.             {
  209.                 pfbd1->cPage += pfbd2->cPage;
  210.                 pfbd1->next = pfbd2->next;
  211.                 if (*pfbdCurr == pfbd2)
  212.                     *pfbdCurr = pfbd1;
  213.                 _VmFree(pfbd2);
  214.             }
  215.             *cMax = max(*cMax, pfbd1->cPage);
  216.             return 1;
  217.         }
  218.  
  219.         // merge with next block
  220.         if (cbOffset + cPage * cbVmPage == pfbd2->cbOffset)
  221.         {
  222.             pfbd2->cbOffset = cbOffset;
  223.             pfbd2->cPage += cPage;
  224.             *cMax = (pfbd2->cPage > *cMax) ? pfbd2->cPage : *cMax;
  225.             return 1;
  226.         }
  227.  
  228.         // make new node
  229.         if (!(pfbd1->next = (PFBD)_VmMalloc(sizeof(FBD))))
  230.             return 0;
  231.         pfbd1 = pfbd1->next;
  232.         pfbd1->cPage = cPage;
  233.         *cMax = (pfbd1->cPage > *cMax) ? pfbd1->cPage : *cMax;
  234.         pfbd1->cbOffset = cbOffset;
  235.         pfbd1->next = pfbd2;
  236.         return 1;
  237.     }
  238. }
  239.  
  240.  
  241. // Frees the linked list
  242.  
  243. void PUBLIC __VmFreeFreeBlock(PFBD *pfbdHead, PFBD *pfbdCurr, unsigned long *cMax)
  244. {
  245.     PFBD pfbd1, pfbd2;
  246.  
  247.     pfbd1 = *pfbdHead;
  248.  
  249.     while (pfbd1 != pfbdNil)
  250.     {
  251.         pfbd2 = pfbd1->next;
  252.         _VmFree(pfbd1);
  253.         pfbd1 = pfbd2;
  254.     }
  255.     *pfbdHead = pfbdNil;
  256.     *pfbdCurr = pfbdNil;
  257.     *cMax = 0;
  258. }
  259.  
  260.  
  261.  
  262.