home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 5 Edit / 05-Edit.zip / NOTEPAD2.ZIP / MMEM.C < prev    next >
C/C++ Source or Header  |  1989-02-08  |  11KB  |  398 lines
  1. /*
  2.  * mmem.c -- Primitive memory management
  3.  *
  4.  * Created by Microsoft Corporation, 1989
  5.  */
  6.  
  7. #include <os2.h>
  8. #include <opendlg.h>
  9. #include "mtypes.h"
  10. #include "mfuncs.h"
  11.  
  12. /***********************************************************************
  13. * Internal forward declarations
  14. ***********************************************************************/
  15.  
  16. private USHORT SizeToIndex(LONG l);
  17. private LONG IndexToSize(USHORT i);
  18. private VOID FreelistInsert(PED ped, PFREEBLOCK pfb);
  19. private VOID FreelistDelete(PED ped, PFREEBLOCK pfb);
  20. private PFREEBLOCK SplitBlock(PED ped, PFREEBLOCK pfb, USHORT usSize);
  21. private VOID AttemptCoalesce(PED ped, PFREEBLOCK pfb);
  22. private SEL AllocSeg(PED ped, LONG segsize);
  23. private BOOL GrowSegs(PED ped);
  24. private BOOL FindMoreMem(PED ped);
  25.  
  26. /***********************************************************************
  27. *  These functions map freeblock size indices to and from actual sizes.
  28. ***********************************************************************/
  29.  
  30. /* private function
  31.  *
  32.  * USHORT SizeToIndex(LONG l)
  33.  *
  34.  * returns log2(i)-5 for 32<=i<=64K
  35.  *  if i<32, uses 32; if i>64K returns 12 (an error value)
  36.  * To wit:
  37.  *  0..32    => 0
  38.  *  33..64   => 1
  39.  *  65..128  => 2
  40.  *  129..256 => 3
  41.  *  257..512 => 4
  42.  * .....
  43.  *  32K+1..64K => 11
  44.  *  >64K       => 12
  45.  */
  46.  
  47. private USHORT SizeToIndex(LONG l)
  48. {
  49.         static LONG a[12] = {1<<5, 1<<6, 1<<7, 1<<8, 1<<9, 1<<10, 1<<11,
  50.                            1<<12, 1<<13, 1<<14, 1<<15, 1<<16};
  51.         USHORT i;
  52.  
  53.         for (i=0; ((i<12) && (a[i]<l)); i++)
  54.                 /* nothing */ ;
  55.  
  56.         return(i);
  57. }
  58.  
  59. /* private function
  60.  *
  61.  * LONG IndexToSize(USHORT i)
  62.  *
  63.  * Converts a block size index (as defined in SizeToIndex above) back to
  64.  * its corresponding size.
  65.  */
  66.  
  67. private LONG IndexToSize(USHORT i)
  68. {
  69.         return(1<<(i+5));
  70. }
  71.  
  72. /***********************************************************************
  73. * Free List manipulation
  74. *
  75. * These functions maintain the list of free blocks
  76. ***********************************************************************/
  77.  
  78. /* private function
  79.  *
  80.  * VOID FreelistInsert(PED ped, PFREEBLOCK pfb)
  81.  *
  82.  * given a pointer to a free block, inserts that free block onto the
  83.  * free list.  Assumes tag already handled.
  84.  */
  85.  
  86. private VOID FreelistInsert(PED ped, PFREEBLOCK pfb)
  87. {
  88.         pfb->prev = NULL;
  89.         pfb->next = ped->pfbHead;
  90.         if (ped->pfbHead == NULL) {
  91.                 ped->pfbTail = pfb;
  92.         } else {
  93.                 ped->pfbHead->prev = pfb;
  94.         }
  95.         ped->pfbHead = pfb;
  96. }
  97.  
  98. /* private function
  99.  *
  100.  * VOID FreelistDelete(PED ped, PFREEBLOCK pfb)
  101.  *
  102.  * given a pointer to a free block, deletes that free block from the
  103.  * free list.  Assumes tag handled elsewhere.
  104.  */
  105.  
  106. private VOID FreelistDelete(PED ped, PFREEBLOCK pfb)
  107. {
  108.     if (pfb->prev == NULL) {
  109.         ped->pfbHead = pfb->next;
  110.     } else {
  111.         pfb->prev->next = pfb->next;
  112.     }
  113.     if (pfb->next == NULL) {
  114.         ped->pfbTail = pfb->prev;
  115.     } else {
  116.         pfb->next->prev = pfb->prev;
  117.     }
  118. }
  119.  
  120. /* private function
  121.  *
  122.  * VOID SplitBlock(PED ped, PFREEBLOCK pfb, USHORT usSize)
  123.  *
  124.  * given a pointer to a free block and a request size, splits the
  125.  * block in half until usSize <= size of block < 2*usSize
  126.  * As a side effect, generates lots of new freeblocks; these are put
  127.  * on the freelist so that afterwards, the smallest new freeblock
  128.  * is pointed to by the head, the second smallest new freeblock is
  129.  * second in the list, &c.
  130.  */
  131.  
  132. private PFREEBLOCK SplitBlock(PED ped, PFREEBLOCK pfb, USHORT usSize)
  133. {
  134.         USHORT usTag;
  135.         PFREEBLOCK pfbBuddy;
  136.  
  137.         // find the size of the block we should create
  138.         usTag = SizeToIndex((LONG)usSize);
  139.  
  140.         // halve the current block until we're small enough
  141.         while ((USHORT)(pfb->tag & PFB_TAGSIZE) > usTag) {
  142.                 pfb->tag--;                          // halve freeblock size
  143.                 pfbBuddy = (PFREEBLOCK)((PBYTE)pfb+freeblock_size(pfb));
  144.                 *pfbBuddy = *pfb;   // make its buddy
  145.                 FreelistInsert(ped, pfbBuddy);
  146.         }
  147.  
  148.         return(pfb);
  149.  
  150. }
  151.  
  152. /* private function
  153.  *
  154.  * VOID AttemptCoalesce(PED ped, PFREEBLOCK pfb)
  155.  *
  156.  * given a pointer to a free block, coalesces the freeblock with its
  157.  * buddy if it is also free.  If so, recurses to try to continue coalescing.
  158.  */
  159.  
  160. private VOID AttemptCoalesce(PED ped, PFREEBLOCK pfb)
  161. {
  162.     PFREEBLOCK pfbBuddy;
  163.     ULONG ulSegSize;
  164.  
  165.     // find address of buddy block
  166.     pfbBuddy = (PFREEBLOCK)((LONG)pfb ^ freeblock_size(pfb));
  167.  
  168.     // stop when have coalesced all the way up the tree
  169.     if (pfbBuddy > pfb) {
  170.         DosSizeSeg(SELECTOROF(pfb),(PULONG)&ulSegSize);
  171.         if (((ULONG)(OFFSETOF(pfb)) + 2L*freeblock_size(pfb)) > ulSegSize) {
  172.             WinAlarm(HWND_DESKTOP, WA_NOTE);
  173.             return;
  174.         }
  175.     }
  176.  
  177.     // Do coalesce
  178.     if (pfbBuddy->tag == pfb->tag) {
  179.         if (pfbBuddy < pfb) {
  180.             (pfbBuddy->tag)++;
  181.             FreelistDelete(ped, pfb);
  182.             AttemptCoalesce(ped, pfbBuddy);
  183.         } else {
  184.             (pfb->tag)++;
  185.             FreelistDelete(ped, pfbBuddy);
  186.             AttemptCoalesce(ped, pfb);
  187.         }
  188.     }
  189. }
  190.  
  191. /***********************************************************************
  192. *  Allocate/Free blocks
  193. *
  194. * These functions allocate chunks of memory at user request and release
  195. * them later.
  196. ***********************************************************************/
  197.  
  198. /* Public function
  199.  *
  200.  * PVOID AllocStore(PED ped, USHORT size)
  201.  *
  202.  * given a request for a certain size block of memory, allocate it
  203.  * out of the free list
  204.  *
  205.  * Returns:  a pointer to the allocated memory, or NULL if can't be
  206.  *     allocated.
  207.  *
  208.  * Note that at objects of size at most 32K-1 can be allocated since that is
  209.  * the largest available block after a segment is initialised
  210.  */
  211.  
  212. public PVOID AllocStore(PED ped, USHORT size)
  213. {
  214.     PFREEBLOCK pfb;
  215.     PVOID pv;
  216.  
  217.     // find first block large enough to hold request
  218.     pfb = ped->pfbHead;
  219.     while ((pfb != NULL) && (freeblock_size(pfb) < (LONG)size+sizeof(BYTE))) {
  220.         pfb = pfb->next;
  221.     }
  222.  
  223.  
  224.     // if no such block could be found...
  225.     if (pfb == NULL) {
  226.         if (!(FindMoreMem(ped))) {  // try to get more memory...
  227.             return NULL;
  228.         } else {
  229.             return (AllocStore(ped, size));   // ...and try again
  230.         }
  231.     } else {
  232.         // allocate out of the found block
  233.         pfb = SplitBlock(ped, pfb, size+sizeof(BYTE));
  234.         FreelistDelete(ped, pfb);
  235.         pfb->tag |= PFB_TAGRESERVED;
  236.  
  237.         pv = ((PBYTE)pfb+sizeof(BYTE));
  238.         LFillStruct((PCH)pv,size,(BYTE)0xff);
  239.  
  240.         return(pv);
  241.     }
  242. }
  243.  
  244. /* public function
  245.  *
  246.  * VOID FreeStore(PED ped, PVOID p)
  247.  *
  248.  * Given a pointer previously returned by AllocStore, or internally
  249.  * synthesised so that it points one byte past a block tag, frees
  250.  * the block; it is an error to later refer to the contents at the
  251.  * pointer and behaviour is undefined.
  252.  * Marks the block as unreserved and attempts to coalesce with a "buddy"
  253.  * block (if any)
  254.  */
  255.  
  256. public VOID FreeStore(PED ped, PVOID p)
  257. {
  258.     PFREEBLOCK pfb;
  259.  
  260.     pfb = (PFREEBLOCK)((PBYTE)p - 1);
  261.     pfb->tag &= ~PFB_TAGRESERVED;
  262.     FreelistInsert(ped, pfb);
  263.     AttemptCoalesce(ped, pfb);
  264. }
  265.  
  266. /***********************************************************************
  267. * Segment manipulation
  268. *
  269. * These functions get space from the OS (in the form of segments).
  270. ***********************************************************************/
  271.  
  272. /* Private function
  273.  *
  274.  * SEL AllocSeg(PED ped, LONG segsize)
  275.  *
  276.  * Allocate a segment from the OS and initialise it; make the segment of a
  277.  * given size (must be SEG8K, SEG16K, SEG32K, or SEG64K).
  278.  *
  279.  * Return:  selector of segment (0 => error)
  280.  */
  281.  
  282. private SEL AllocSeg(PED ped, LONG segsize)
  283. {
  284.     SEL sel;
  285.     PSEGHDR psh;
  286.     PFREEBLOCK pfb;
  287.  
  288. // get segment from the OS memory pool
  289.  
  290.     if (DosAllocSeg((USHORT)segsize, (PSEL)&sel, (USHORT)0))
  291.         return((SEL)0);
  292.  
  293. // turn the segment into all free space and insert on freelist
  294.  
  295.     pfb = (PFREEBLOCK)SEGHDROF(sel);
  296.     pfb->tag = PFB_TAGSIZE & SizeToIndex(segsize);
  297.     FreelistInsert(ped,pfb);
  298.  
  299. // create a segment header for this segment
  300.  
  301.     psh = (PSEGHDR)AllocStore(ped, sizeof(SEGHDR));
  302.     psh->this = sel;
  303.     psh->size = segsize;
  304.     psh->prev = NULL;
  305.     psh->next = ped->selHead;
  306.     if (ped->selHead == NULL) {
  307.         ped->selTail = psh;
  308.     } else {
  309.         ped->selHead->prev = psh;
  310.     }
  311.     ped->selHead = psh;
  312.  
  313.     return(sel);
  314. }
  315.  
  316. /* Private function
  317.  *
  318.  * BOOL GrowSegs(PED ped)
  319.  *
  320.  * Attempts to reallocate the first segment on the segment list to provide
  321.  * more memory.  Obviously, the segment must double in size at each
  322.  * reallocation.  If the reallocate fails, or if the segment is already
  323.  * 64K long, the function returns FALSE; otherwise the function returns
  324.  * TRUE to indicate success.
  325.  */
  326.  
  327. private BOOL GrowSegs(PED ped)
  328. {
  329.     PFREEBLOCK pfb;
  330.     PSEGHDR psh;
  331.  
  332.     psh = ped->selHead;
  333.     if (psh == NULL)                // if no segments...
  334.         return(FALSE);
  335.  
  336.     if (psh->size == SEG64K)        // if it can't grow further...
  337.         return(FALSE);
  338.  
  339.     // try to reallocate
  340.  
  341.     if (DosReallocSeg((USHORT)(psh->size*2),psh->this))
  342.         return(FALSE);
  343.  
  344.     // synthesize a block header and free the block
  345.     // (will coalesce blocks as needed)
  346.  
  347.     pfb = (PFREEBLOCK)(((PBYTE)SEGHDROF(psh->this))+psh->size);
  348.     pfb->tag = PFB_TAGRESERVED | (PFB_TAGSIZE & SizeToIndex(psh->size));
  349.     FreeStore(ped, (((PBYTE)pfb)+1));
  350.     psh->size *= 2;
  351.  
  352.     return(TRUE);
  353. }
  354.  
  355. /* private function
  356.  *
  357.  * BOOL FindMoreMem(PED ped)
  358.  *
  359.  * Generally looks around to try to get some more memory.  First tries to
  360.  * do a reallocation; if that fails, gets a new segment.  If that
  361.  * fails too then function gives up.
  362.  */
  363.  
  364. private BOOL FindMoreMem(PED ped)
  365. {
  366.     if (GrowSegs(ped))
  367.             return TRUE;
  368.     if (AllocSeg(ped,STORE_INITSIZE) != 0)
  369.             return TRUE;
  370.     return FALSE;
  371. }
  372.  
  373. /***********************************************************************
  374. * Initialisation
  375. *
  376. * These functions should only be called at startup.  They initialise
  377. * the memory manager.
  378. ***********************************************************************/
  379.  
  380. /* public function
  381.  *
  382.  * BOOL InitStore(PED ped)
  383.  *
  384.  * Initialise storage management
  385.  *
  386.  * Return:  TRUE => initialised okay
  387.  *          FALSE =>  problem initialising
  388.  */
  389.  
  390. public BOOL InitStore(PED ped)
  391. {
  392.     ped->pfbHead = NULL;
  393.     ped->pfbTail = NULL;
  394.     ped->selHead = ped->selTail = NULL;
  395.     if (0 == AllocSeg(ped, STORE_INITSIZE))
  396.             return FALSE;
  397. }
  398.