home *** CD-ROM | disk | FTP | other *** search
/ RISC DISC 1 / RISC_DISC_1.iso / pd_share / code / desklib / Libraries / Mem / c / Mem < prev    next >
Encoding:
Text File  |  1994-05-29  |  11.9 KB  |  373 lines
  1. /*
  2.     ####             #    #     # #
  3.     #   #            #    #       #          The FreeWare C library for 
  4.     #   #  ##   ###  #  # #     # ###             RISC OS machines
  5.     #   # #  # #     # #  #     # #  #   ___________________________________
  6.     #   # ####  ###  ##   #     # #  #                                      
  7.     #   # #        # # #  #     # #  #    Please refer to the accompanying
  8.     ####   ### ####  #  # ##### # ###    documentation for conditions of use
  9.     ________________________________________________________________________
  10.  
  11.     File:    Mem.c
  12.     Author:  Copyright © 1993, 1994 Jason Williams
  13.     Version: 1.01 (30 May 1994)
  14.     Purpose: Dynamic memory management
  15.  
  16.  *  Details for use of Mem are in Mem.h
  17.  *  Ideas that may be added to Mem.c in future are in Docs.ModuleNote.Mem
  18.  *
  19.  *  NOTE that some functions and variables are Mem__xxxx: These are NOT
  20.  *  intended for external use outside Mem_ Functions, and are only externs
  21.  *  so that Mem does not need to be linked with as one huge chunk.
  22.  *
  23.  *  Details of how this code works:
  24.  *  Mem memory chunks are held in a 'heap' of memory above the area grabbed
  25.  *  by the SharedCLibrary for mallocs and stackspace, extending up to the
  26.  *  end of the WimpSlot, which is adjusted up & down as necessary.
  27.  *
  28.  *  The Mem heap is simple, and is *exactly* filled by a contiguous set of
  29.  *  chunks. This is laid out as follows:
  30.  *
  31.  *    [H] [H|--data--:P] ... [H|-----data-----:P] [H]
  32.  *
  33.  *  Where H is a chunk header containing
  34.  *    + the size of the previous chunk, including H and P
  35.  *       (for moving backwards through the chain of chunks)
  36.  *
  37.  *    + the size of this chunk, including H and P
  38.  *       (for moving forwards through the chain of chunks)
  39.  *
  40.  *    + the size of the user data held in this chunk
  41.  *      Note that userdatasize + H + P does not necessarily  == chunksize
  42.  *
  43.  *    + the anchor of this chunk
  44.  *       (a pointer to the user's pointer to the chunk)
  45.  *       This is used for 2 things: To update the user's anchor when the chunk
  46.  *       is moved, and also to check that all accesses are legal.
  47.  *
  48.  *  P is padding to word-align the block. Note that the padding may be
  49.  *  anywhere between 0 and 20 bytes in size - normally it will be 0..3 to
  50.  *  get word alignment, but if a block is allocated into a free space which
  51.  *  is not big enough for that block plus a new free block, we'll swallow
  52.  *  the whole freespace into the newly allocated block to ensure the continued
  53.  *  viability of the heap. Note also that during some operations, chunks
  54.  *  may temporarily exist with P fields of any size at all.
  55.  */
  56.  
  57. #include <stdlib.h>
  58. #include <string.h>
  59.  
  60. #include "kernel.h"
  61.  
  62. #define __dl_mem_c
  63. #include "MemDefs.h"
  64.  
  65. #include "DeskLib:WimpSWIs.h"
  66.  
  67.  
  68. /* --- External interface - global variables ------------------------------- */
  69. int mem_autocompact = mem_FASTCOMPACT;     /* Enable/disable auto-compaction */
  70.  
  71.  
  72. /* --- Internal data ------------------------------------------------------- */
  73. mem_header *mem__lastchunk = NULL;
  74. int mem__heap         = -1;      /* Base address of heap (malloc high water) */
  75. int mem__heapsize     = -1;      /* Size of the heap                         */
  76. BOOL mem__iscompact   = TRUE;    /* The heap does not need compacting        */
  77.  
  78.  
  79. /* --- Internal Function definitions --------------------------------------- */
  80.  
  81. extern int Mem__HeapSize(int heapsize)
  82. /*  Reads/Writes the heap size value
  83.  *  pass in heapsize == -1 to just read the current value
  84.  */
  85. {
  86.   int nextslot = -1;
  87.   int freepool = -1;
  88.   int slot     = heapsize;
  89.  
  90.   if (mem__heap == -1)                        /* Remember initial slot size  */
  91.   {
  92.     Wimp_SlotSize(&mem__heap, &nextslot, &freepool);
  93.     mem__heap = WORDALIGN(mem__heap);
  94.  
  95.     mem__heap += 0x8000;    /* Add application base address to get heap base */
  96.   }
  97.  
  98.   if (slot >= 0) slot += mem__heap;           /* Work out new wimp slot size */
  99.   Wimp_SlotSize(&slot, &nextslot, &freepool);
  100.  
  101.   return(slot - mem__heap);                   /* Return new heap size        */
  102. }
  103.  
  104.  
  105.  
  106. extern void Mem__ReduceSlot(void)
  107. /*  Attempts to shrink the heap by returning all free memory in the lastchunk
  108.  *  back to the Wimp.
  109.  */
  110. {
  111.   if (mem__lastchunk->realsize > sizeof(mem_header) + 16)
  112.   {
  113.     mem__heapsize = Mem__HeapSize((int) mem__lastchunk +
  114.                                    sizeof(mem_header) + 16 - mem__heap);
  115.     mem__lastchunk->realsize = mem__heap + mem__heapsize - (int) mem__lastchunk;
  116.   }
  117. }
  118.  
  119.  
  120.  
  121. extern mem_header *Mem__NextChunk(mem_header *chunk)
  122. /*  Returns a pointer to the next chunk in the heap. Note that if
  123.  *  'chunk' is the last chunk in the heap, it will return 'chunk'.
  124.  */
  125. {
  126.   if (chunk == mem__lastchunk)
  127.     return(chunk);
  128.  
  129.   return((mem_header *) ((int) chunk + chunk->realsize));
  130. }
  131.  
  132.  
  133. extern mem_header *Mem__PrevChunk(mem_header *chunk)
  134. /*  Returns a pointer to the previous chunk in the heap. Note that if
  135.  *  'chunk' is the first chunk in the heap, it will return 'chunk'.
  136.  */
  137. {
  138.   return((mem_header *) ((int) chunk - chunk->prevrealsize));
  139. }
  140.  
  141.  
  142. extern BOOL Mem__FindChunk(mem_anchor *anchor, mem_header **chunk)
  143. /*  Checks that the header is OK by comparing the handle to the
  144.  *  (supposedly identical) handle stored in the chunk header.
  145.  *  Returns the pointer to the chunk header, and TRUE if it is OK.
  146.  */
  147. {
  148.   if (*anchor == NULL) return(FALSE);
  149.  
  150.   *chunk = (mem_header *) (((int) *anchor) - sizeof(mem_header));
  151.   return((*chunk)->handle == anchor);
  152. }
  153.  
  154.  
  155.  
  156. static void Mem__Amalgamate(mem_header **chunk)
  157. /*  Tries to merge this free chunk with the previous chunk, if it's free.
  158.  */
  159. {
  160.   mem_header *this, *prev, *next;
  161.  
  162.   this = *chunk;
  163.   if (!ISFREE(this) || (int) this <= mem__heap) return;
  164.  
  165.   prev = Mem__PrevChunk(this);
  166.   if (prev != this && ISFREE(prev))                /* Amalgamate free chunks */
  167.   {
  168.     prev->realsize += this->realsize;              /* Extend prev chunk      */
  169.     *chunk = prev;                                 /* Return new free chunk  */
  170.  
  171.     if (this == mem__lastchunk)                    /* Update lastchunk ptr   */
  172.       mem__lastchunk = prev;
  173.     else
  174.     {                                              /* Fix backward 'link'    */
  175.       next = Mem__NextChunk(prev);
  176.       next->prevrealsize = prev->realsize;
  177.     }
  178.   }
  179. }
  180.  
  181.  
  182. extern void Mem__SplitOffFreeChunk(mem_header *chunk)
  183. /*  Checks if it is possible to split off enough memory from the end of this
  184.  *  chunk to create a new free chunk - if there is, it does the split.
  185.  */
  186. {
  187.   if (ISFREE(chunk)) return;
  188.  
  189.   mem__iscompact = FALSE;            /* Compaction is probably necessary now */
  190.   if (chunk->realsize - chunk->datasize >= sizeof(mem_header) + 16)
  191.   {
  192.     mem_header *free;
  193.     int         chunksize = chunk->realsize;
  194.  
  195.     /*  There is enough wastage at the end of the chunk to create a new free
  196.      *  chunk of 16 or more bytes dataspace at the end of it
  197.      */
  198.  
  199.     free = (mem_header *) WORDALIGN( ((int) chunk) +
  200.                                       sizeof(mem_header) + chunk->datasize);
  201.     
  202.     chunk->realsize    = (int) free - (int) chunk;
  203.     free->realsize     = (((int) chunk) + chunksize) - (int) free;
  204.     free->prevrealsize = chunk->realsize;
  205.     free->datasize     = 0;
  206.     free->handle       = NULL;
  207.  
  208.     if (mem__lastchunk == chunk)
  209.       mem__lastchunk = free;
  210.     else
  211.     {
  212.       chunk = Mem__NextChunk(free);
  213.       chunk->prevrealsize = free->realsize;
  214.  
  215.       Mem__Amalgamate(&chunk);         /* Ensure not 2 free chunks in a row */
  216.     }
  217.   }
  218.  
  219.   if (mem_autocompact == mem_FULLCOMPACT)
  220.     Mem_Compact();
  221. }
  222.  
  223.  
  224.  
  225. /* --- External Function definitions --------------------------------------- */
  226.  
  227. extern BOOL Mem_Alloc(mem_anchor *anchor, int numbytes)
  228. /*  Allocates 'numbytes' of memory, placing a pointer to this data in
  229.  *  the given anchor. The memory returned always starts at a word-aligned
  230.  *  address, though need not be an integral number of words long.
  231.  *
  232.  *  Note that this implementation provides a 'best fit' strategy, that is
  233.  *  it searches for the free chunk of the *closest* size to that needed
  234.  *  which can be slow if there are a lot of free chunks. However, this
  235.  *  is still pretty quick, especially if you call Mem_Compact reasonably
  236.  *  often to ensure the heap is kept compact.
  237.  *
  238.  *  Alternative strategies that you might prefer to implement for yourself
  239.  *  are:
  240.  *    + First fit: Find the first large enough free space
  241.  *                 Faster than best fit, but generally less effective.
  242.  *
  243.  *    + Grab:      Just alloc at the end of the heap, and rely on (compacts
  244.  *                 helping to keep) enough free memory in the Wimp Pool
  245.  *                 to always be able to satisfy memory requests.
  246.  *                 (This is very fast, and minimises the code in this function)
  247.  *                 [RECOMPILE with FASTALLOC defined for this scheme]
  248.  */
  249. {
  250.   mem_header *chunk, *bestfit = NULL;
  251.  
  252.   *anchor  = NULL;
  253.   if (numbytes <= 0) return(FALSE);
  254.   
  255.   numbytes += sizeof(mem_header);
  256.  
  257. #ifndef FASTALLOC
  258.   /*
  259.    *  Find the best fit free-chunk in the heap. (i.e. search for the smallest
  260.    *  chunk which is >= numbytes)
  261.    */
  262.   chunk = (mem_header *) mem__heap;
  263.  
  264.   while (chunk != mem__lastchunk)
  265.   {
  266.     if (ISFREE(chunk) && chunk->realsize >= numbytes)
  267.     {
  268.       if (bestfit == NULL || bestfit->realsize > chunk->realsize)
  269.       {
  270.         bestfit = chunk;
  271.  
  272.         if (bestfit->realsize == numbytes)        /* Don't bother continuing */
  273.           break;
  274.       }
  275.     }
  276.     chunk = Mem__NextChunk(chunk);
  277.   }
  278.  
  279.   if (bestfit == NULL)      /* No large enough chunks - must extend the heap */
  280. #endif
  281.  
  282.   {
  283.     int needed = numbytes;
  284.  
  285.     if (ISFREE(mem__lastchunk))
  286.       needed -= mem__lastchunk->realsize;
  287.  
  288.     if (needed > 0)
  289.       mem__heapsize = Mem__HeapSize(mem__heapsize + needed + 16);
  290.       
  291.     mem__lastchunk->realsize = mem__heap + mem__heapsize - (int) mem__lastchunk;
  292.  
  293.     Mem__SplitOffFreeChunk(mem__lastchunk);
  294.     if (mem__lastchunk->realsize >= numbytes)
  295.       bestfit = mem__lastchunk;
  296.   }
  297.  
  298.   if (bestfit == NULL)                      /* Unable to allocate the memory */
  299.     return(FALSE);
  300.  
  301.   *anchor = (void *) ((int) bestfit + sizeof(mem_header));
  302.   bestfit->handle = anchor;
  303.   bestfit->datasize = numbytes - sizeof(mem_header);
  304.  
  305.   Mem__SplitOffFreeChunk(bestfit);         /* Return any free space for use */
  306.  
  307.   return(TRUE);
  308. }
  309.  
  310.  
  311. extern void Mem_Free(mem_anchor *anchor)
  312. {
  313.   mem_header *chunk;
  314.  
  315.   if (Mem__FindChunk(anchor, &chunk))
  316.   {
  317.     chunk->datasize = 0;                           /* Mark this chunk free   */
  318.     *anchor         = NULL;                        /* Kill the user's anchor */
  319.  
  320.     Mem__Amalgamate(&chunk);
  321.     if (chunk != mem__lastchunk)
  322.     {
  323.       chunk = Mem__NextChunk(chunk);
  324.       Mem__Amalgamate(&chunk);
  325.     }
  326.   }
  327.  
  328.   if (mem_autocompact == mem_FULLCOMPACT)
  329.     Mem_Compact();
  330.   Mem__ReduceSlot();
  331. }
  332.  
  333.  
  334. #pragma no_check_stack
  335. extern int Mem_DontBudge(int n, void **a)
  336. /*  Function to register with _kernel_register_slotextend to refuse to allow
  337.  *  SharedCLib to allocate more memory. (identical to Flex's flex_dontbudge)
  338.  *  Don't call this function - pass to _k*_r*_slotextend instead. Note that
  339.  *  Mem_Initialise does this for you automatically anyway, so unless you have
  340.  *  a Mem_Budge function, you shouldn't have to worry about this at all.
  341.  */
  342. {
  343.   return(0);                                    /* number of bytes allocated */
  344. }
  345. #pragma check_stack
  346.  
  347.  
  348. extern BOOL Mem_Initialise(void)
  349. /*  Initialises the Mem memory manager
  350.  *  Returns FALSE if it fails - if this occurs, Mem will not operate and
  351.  *  you should not try calling any Mem FNs. Basically you're stuffed.
  352.  *  (Generally you should report the "Insufficient memory or not within
  353.  *   *desktop world" error message and exit)
  354.  */
  355. {
  356.   _kernel_register_slotextend(Mem_DontBudge);
  357.  
  358.   if (mem__heap == -1)    /* This will be > 0 if we have already initialised */
  359.   {
  360.     mem__heapsize  = Mem__HeapSize(sizeof(mem_header) + 16);
  361.     if (mem__heapsize < sizeof(mem_header))
  362.       return(FALSE);
  363.       
  364.     mem__lastchunk = (mem_header *) mem__heap;
  365.     mem__lastchunk->realsize     = mem__heapsize;
  366.     mem__lastchunk->datasize     = 0;
  367.     mem__lastchunk->prevrealsize = 0;
  368.     mem__lastchunk->handle       = NULL;
  369.   }
  370.  
  371.   return(TRUE);
  372. }
  373.