home *** CD-ROM | disk | FTP | other *** search
/ GEMini Atari / GEMini_Atari_CD-ROM_Walnut_Creek_December_1993.iso / files / program / bdtmaloc.txt < prev   
Text File  |  1988-09-22  |  10KB  |  392 lines
  1. From david%bdt%hoptoad%lll-crg%ames.uucp@mailrus.cc.umich.edu Thu Sep 22 01:15:09 1988
  2. Received: from mailrus.cc.umich.edu by polymnia.math.lsa.umich.edu (5.59/umix-1.1)
  3.     id AA08618; Thu, 22 Sep 88 01:15:00 EDT
  4. Received: from ames.arc.nasa.gov by mailrus.cc.umich.edu (5.59/1.0)
  5.     id AA15150; Thu, 22 Sep 88 01:17:30 EDT
  6. From: david%bdt%hoptoad%lll-crg%ames.uucp@mailrus.cc.umich.edu
  7. Received: Wed, 21 Sep 88 22:16:15 PDT by ames.arc.nasa.gov (5.59/1.2)
  8. Received: by lll-crg.llnl.gov (5.54/1.14)
  9.     id AA16660; Wed, 21 Sep 88 22:05:15 PDT
  10. Received: from bdt.UUCP by hop.toad.com id AA13716; Wed, 21 Sep 88 18:02:34 PDT
  11. Message-Id: <8809220102.AA13716@hop.toad.com>
  12. To: dyer%math.lsa.umich.edu%mailrus%ames%lll-crg%hoptoad.uucp@mailrus.cc.umich.edu
  13. Date: Wed, 21 Sep 88 9:10:22 PDT
  14. Subject: Re: Memory Allocator - who wants it?
  15. In-Reply-To: Message from "math.lsa.umich.edu!dyer" of Sep 17, 88 at 11:16 pm
  16. X-Mailer: Elm [version 1.5]
  17. Status: R
  18.  
  19. OK.  Here's the malloc I use with Alcyon C.
  20.  
  21. I am not doing a lot of new Atari ST product development, btu we are
  22. continuing to market and support all of our products, including new
  23. improvements and enhancements.   We will probably begin a new ST
  24. marketing effort this month.   Our Retail Software is becoming
  25. popular in the Mega ST configuration, I guess for price considerations.
  26.  
  27.     - David Beckemeyer
  28.  
  29. ------- CUT HERE ------
  30.  
  31. /************************************************************************/
  32. /*                                    */
  33. /*    (c) Copyright 1986                        */
  34. /*    David Beckemeyer                        */
  35. /*    All Rights Reserved                         */
  36. /*                                    */
  37. /*    memory.c - memory allocation module                */
  38. /*                                    */
  39. /*    This is an implementation of the Unix standard C runtime    */
  40. /*    library routines malloc(), free(), and realloc().        */
  41. /*                                    */
  42. /*    The routines manage "heaps" allocated from the system.        */
  43. /*    Each heap is carved up into some number of user memory        */
  44. /*    blocks, as requested by malloc() and realloc() calls.        */
  45. /*                                    */
  46. /*    As blocks are returned with free() calls, they are merged    */
  47. /*    with any neighboring blocks that are free. Un-mergable        */
  48. /*    blocks are stored on a doubly linked list.            */
  49. /*                                    */
  50. /*    As heaps become full, new ones are created. The list of        */
  51. /*    heaps is a singly linked list.  Heaps are returned to the    */
  52. /*    system during garbage collection, which occurs whenever        */
  53. /*    the current set of heaps cannot fill a memory request.        */
  54. /*                                    */
  55. /*    This scheme avoids GEMDOS memory management problems        */
  56. /*    and minimizes fragmentation.                    */
  57. /*                                    */
  58. /*    MINSEG below defines the minimum segment size allocated.    */
  59. /*    Whenever the remaining portion of a block is smaller than    */
  60. /*    this value, the entire block is returned to the caller.        */
  61. /*                                    */
  62. /*    HEAPSIZE is the smallest system allocation we will ever        */
  63. /*    make.  This value can be adjusted to your application.        */
  64. /*    If it is small, more GEMDOS Malloc calls will have to         */
  65. /*    be performed.  If it is large compared to the amount of        */
  66. /*    memory actually aquired at runtime, there will be wasted    */
  67. /*    memory.  Since too many GEMDOS Malloc calls may produce        */
  68. /*    a crash, it is wise to make HEAPSIZE at least 8K bytes.        */
  69. /*                                    */
  70. /************************************************************************/
  71.  
  72. #include <stdio.h>
  73. #include <osbind.h>
  74.  
  75.  
  76. /* memory manager definitions */
  77. #define MAGIC 0x55aa        /* magic number used for validation */
  78. #define HEAPSIZE 16384L        /* minimum size of each heap */
  79. #define MINSEG 256L        /* minimum size of allocated memory chunk */
  80.  
  81. /* the structure controlling the object known as heap */
  82. #define HEAP struct _heap
  83.  
  84. /* Memory Control Block */
  85. #define MCB struct _mcb
  86. struct _mcb {
  87.     MCB *fore;        /* forward link */
  88.     MCB *aft;        /* backward link */
  89.     MCB *neighbor;        /* nearest lower address neighbor */
  90.     long size;        /* size of this chunk including MCB */
  91.     HEAP *heap;        /* 0L if free, else owner of this chunk */    
  92.     int magic;        /* magic number for validation */
  93. };
  94.  
  95. /* and here is the heap control block */
  96. struct _heap {
  97.     HEAP *link;        /* pointer to next heap (0 if end) */
  98.     MCB *freelist;        /* pointer to first free block or 0 */
  99.     MCB *limit;        /* address of the end of this heap */
  100. };
  101.  
  102. /* List of allocated heaps aquired from GEMDOS.
  103.  * Start off with no heaps allocated (NULL terminated linked list).
  104.  */
  105. static HEAP heaplist = { (HEAP *)0 };
  106.  
  107.     
  108. /* get another heap from GEMDOS */
  109.  
  110. static HEAP *alloc_heap(x)
  111. long x;
  112. {
  113.     MCB *m;
  114.     HEAP *heap;
  115.  
  116.     /* locate end of the heaplist (a tail pointer might help here) */
  117.     for (heap = &heaplist; heap->link; heap = heap->link)
  118.         ;
  119.  
  120.     /* adjust the request for the minmum required overhead */
  121.     x = (x + sizeof(HEAP) + sizeof(MCB) + 1) & ~1L;
  122.  
  123.     /* grab a chunk from GEMDOS */
  124.     if ((heap->link = (HEAP *)Malloc(x)) == 0)
  125.         return((HEAP *)0);
  126.  
  127.     /* add the heap to the heaplist */
  128.     heap = heap->link;
  129.     heap->link = (HEAP *)0;
  130.  
  131.     /* first chunk is just after header */
  132.     m = (MCB *)(heap + 1);
  133.  
  134.     /* set up size and mark it as a free chunk */
  135.     m->size = x - sizeof(HEAP);
  136.     m->heap = 0L;
  137.  
  138.     /* this is the last (only) chunk on the linked list */
  139.     m->fore = (MCB *)0;
  140.     m->aft = (MCB *)(&heap->freelist);
  141.  
  142.     /* there is no lower addressed neighbor to this chunk */
  143.     m->neighbor = (MCB *)0;
  144.  
  145.     /* mark the heap limit and place chunk on freelist */
  146.     heap->limit = (MCB *)((char *)heap + x); 
  147.     heap->freelist = m;
  148.     return(heap);
  149. }
  150.  
  151.  
  152. /* split a segment into two chunks */
  153.  
  154. static split_seg(mcb, x)
  155. MCB *mcb;
  156. long x;
  157. {
  158.     MCB *m;
  159.     HEAP *heap;
  160.  
  161.     /* check for ownership here */
  162.     if (mcb == 0 || (heap = mcb->heap) == 0 || mcb->magic != MAGIC) {
  163.         return(-40);
  164.     }
  165.  
  166.     /* make a new chunk inside this one */
  167.     m = (MCB *)((char *)mcb + x);
  168.     m->size = mcb->size - x;
  169.     m->neighbor = mcb;
  170.     m->heap = mcb->heap;
  171.     m->magic = MAGIC;
  172.     /* shrink the old chunk */
  173.     mcb->size = x;
  174.     /* establish the forward neighbor's relationship to us */
  175.     mcb = m;
  176.     if ((m = (MCB *)((char *)mcb + mcb->size)) < heap->limit)
  177.         m->neighbor = mcb;
  178.     free(++mcb);
  179.     return(0);
  180. }
  181.  
  182.  
  183.  
  184. /* allocate a chunk out of a heap */
  185.  
  186. static MCB *alloc_seg(x, heap)
  187. long x;
  188. HEAP *heap;
  189. {
  190.     MCB *mcb;
  191.  
  192.     /* use first fit algorithm to find chunk to use */
  193.     for (mcb = heap->freelist; mcb; mcb = mcb->fore)
  194.         if (mcb->size >= x + sizeof(MCB))
  195.             break;
  196.     if (mcb) {
  197.         /* remove it from the freelist */
  198.         unfree(mcb);
  199.         /* set up owner */
  200.         mcb->heap = heap;
  201.         mcb->magic = MAGIC;
  202.         /* if it's bigger than we need and splitable, split it */
  203.         if (mcb->size - x > MINSEG)
  204.             split_seg(mcb, x + sizeof(MCB));
  205.         /* return start of data area to caller */
  206.         mcb++;
  207.     }
  208.     return(mcb);
  209. }
  210.  
  211.  
  212.  
  213. /* remove (unlink) a chunk from the freelist */
  214.  
  215. static unfree(mcb)
  216. MCB *mcb;
  217. {
  218.     if ((mcb->aft->fore = mcb->fore) != 0)
  219.         mcb->fore->aft = mcb->aft;
  220. }
  221.  
  222.  
  223.  
  224. /* GEMDOS garbage collection, return TRUE if anything changes */
  225.  
  226. static collect()
  227. {
  228.     HEAP *heap, *h;
  229.     MCB *mcb;
  230.     int flag;
  231.     
  232.     for (flag = 0, heap = &heaplist; (h = heap->link) != 0; ) {
  233.         if ((mcb = h->freelist) != 0 &&
  234.          !mcb->neighbor && ((char *)mcb + mcb->size) == h->limit) {
  235.             heap->link = h->link;
  236.             Mfree(h);
  237.             flag++;
  238.         }
  239.         else
  240.             heap = h;
  241.     }
  242.     return(flag);
  243. }
  244.  
  245. /****************************************************
  246.  *
  247.  *    Unix standard C runtime library routines
  248.  *    malloc(), free(), and realloc() follow.
  249.  *
  250.  *    The three calls work as described in K & R.
  251.  *
  252.  *    This implementation uses a first fit algorithm
  253.  *    and does occasional garbage collection to
  254.  *    minimize system memory fragmentation.
  255.  *
  256.  *****************************************************
  257.  
  258. /****************/
  259. /*        */
  260. /*    malloc    */
  261. /*        */
  262. /****************/
  263.  
  264. char *malloc(n)
  265. int n;
  266. {
  267.     register HEAP *heap;
  268.     register long x;
  269.     char *p;
  270.  
  271.     /* malloc is supposed to accept all 16 bits so fix it up here */
  272.     if (n < 0)
  273.         x = 65537L + (long)n & ~1L;
  274.     else
  275.         x = (long)(n + 1) & ~1L;
  276.  
  277.     /* first check all current heaps */
  278.     for (heap = heaplist.link; heap; heap = heap->link)
  279.         if ((p = alloc_seg(x, heap)) != 0)
  280.             return(p);
  281.  
  282.     /* not enough room on heaps, try garbage collection */
  283.     collect();
  284.  
  285.     /* now allocate a new heap */
  286.     if ((heap = alloc_heap(max(x, HEAPSIZE))) != 0)
  287.         if ((p = alloc_seg(x, heap)) != 0)
  288.             return(p);
  289.  
  290.     /* couldn't get a chunk big enough */
  291.     return((char *)0);
  292. }
  293.  
  294.  
  295. /****************/
  296. /*        */
  297. /*     free    */
  298. /*        */
  299. /****************/
  300.  
  301. free(mcb)
  302. MCB *mcb;
  303. {
  304.     MCB *m;
  305.     HEAP *heap;
  306.  
  307.     /* address header */
  308.     mcb--;
  309.  
  310.     /* check for ownership here */
  311.     if (mcb == 0 || (heap = mcb->heap) == 0 || mcb->magic != MAGIC) {
  312.         return(-40);
  313.     }
  314.         
  315.     /* connect to chunks behind this one */
  316.     while (mcb->neighbor) {
  317.         if (mcb->neighbor->heap)
  318.             break;
  319.         mcb->neighbor->size += mcb->size;
  320.         mcb = mcb->neighbor;
  321.         unfree(mcb);
  322.     }
  323.  
  324.     /* now connect to chunks after this one */
  325.     while ((m = (MCB *)((char *)mcb + mcb->size)) < heap->limit) {
  326.         m->neighbor = mcb;
  327.         if (m->heap)
  328.             break;
  329.         mcb->size += m->size;
  330.         unfree(m);
  331.     }
  332.     /* place the resultant chunk on the free list */
  333.     for (m = (MCB *)(&heap->freelist); m->fore; m = m->fore)
  334.         ;
  335.     m->fore = mcb;
  336.     mcb->fore = (MCB *)0;
  337.     mcb->aft = m;
  338.     mcb->heap = 0L;
  339.     return(0);
  340. }
  341.  
  342.  
  343.  
  344. /****************/
  345. /*        */
  346. /*   realloc    */
  347. /*        */
  348. /****************/
  349.  
  350. char *realloc(mcb, n)
  351. MCB *mcb;
  352. int n;
  353. {
  354.     long x;
  355.     char *t, *s, *p;
  356.  
  357.     /* address header */
  358.     --mcb;
  359.  
  360.     /* check for ownership here */
  361.     if (mcb == 0 || mcb->magic != MAGIC) {
  362.         return((char *)0);
  363.     }
  364.  
  365.     /* malloc is supposed to accept all 16 bits so fix it up here */
  366.     if (n < 0)
  367.         x = (65537L + (long)n + sizeof(MCB)) & ~1L;
  368.     else
  369.         x = (long)(n + 1 + sizeof(MCB)) & ~1L;
  370.  
  371.     /* if less than current size, just shrink it */
  372.     if (mcb->size > x) {
  373.         split_seg(mcb, x);
  374.         return((char *)(++mcb));
  375.     }
  376.  
  377.     /* it's bigger - allocate new block, copy data, and free old one */
  378.     if ((p = malloc(n)) != 0) {
  379.         x = mcb->size - sizeof(MCB);
  380.         s = ++mcb;
  381.         t = p;
  382.         while (x--)
  383.             *t++ = *s++;
  384.         free(mcb);
  385.         return(p);
  386.     }
  387.     return((char *)0);
  388. }
  389.  
  390.  
  391.  
  392.