home *** CD-ROM | disk | FTP | other *** search
/ No Fragments Archive 12: Textmags & Docs / nf_archive_12.iso / MAGS / SOURCES / ATARI_SRC.ZIP / atari source / DSHJ2 / MALLOC.C < prev    next >
Encoding:
C/C++ Source or Header  |  2001-02-10  |  7.7 KB  |  313 lines
  1. /*
  2.  * General-purpose memory allocator, on the MWC arena model, with
  3.  * this added feature:
  4.  *
  5.  * All blocks are coalesced when they're freed.  If this results in
  6.  * an arena with only one block, and that free, it's returned to the
  7.  * OS.
  8.  *
  9.  * The functions here have the same names and bindings as the MWC
  10.  * memory manager, which is the same as the UNIX names and bindings.
  11.  */
  12.  
  13. /* need osbind.h for Malloc call.  MWC might not call it this */
  14. #include <osbind.h>
  15.  
  16. #define NULL ((char *)0)
  17.  
  18. #ifdef DEBUGON
  19. #define DEBUG(c) Cconout(c)
  20. #else
  21. #define DEBUG(c) /*nothing*/
  22. #endif
  23.  
  24. /*
  25.  * block header: every memory block has one.
  26.  * The size field is negative (i.e. -size) if the block is allocated.
  27.  * Zero-length blocks are free; they hold space which might get coalesced
  28.  * usefully later on.
  29.  */
  30.  
  31. struct block {
  32.     struct block *b_next;    /* NULL for last guy */
  33.     long b_size;        /* negative for allocated blocks */
  34. };
  35.  
  36. /*
  37.  * arena header: every arena has one.  Each arena is always completely
  38.  * filled with blocks; the first starts right after this header.
  39.  */
  40.  
  41. struct arena {
  42.     struct arena *a_next;
  43. };
  44.  
  45. /*
  46.  * Arena linked-list pointer, and block size.  The block size is initialized
  47.  * to Malloc(-1L)/10 when you start up, because somebody said that 10
  48.  * Malloc blocks per process was a reasonable maximum.  This is hopelessly
  49.  * unbalanced: 50K on a 520ST and 400K on a Mega 4, so it's tempered by
  50.  * the constant MAXARENA (I chose 100K, same as a 1040).
  51.  */
  52.  
  53. static struct arena *a_first = NULL;
  54. long minarena;
  55. #define MAXARENA (100L*1024L)
  56.  
  57. char *lmalloc(size)
  58. register long size;
  59. {
  60.     register struct arena *a;
  61.     register struct block *b;
  62.     register long temp;
  63.  
  64.     DEBUG('A');
  65.     /* make sure size is even; fail if it's negative zero */
  66.     if (size <= 0) return 0;
  67.     size = (size+1) & ~1;
  68.  
  69.     for (a = a_first; a; a = a->a_next) {
  70.     for (b = (struct block *)(a+1); b; b = b->b_next) {
  71.         /* if free & big enough, use it */
  72.         if (b->b_size >= size) {
  73.         goto done;
  74.         }
  75.     }
  76.     }
  77.  
  78.     /* no block available: get a new arena */
  79.  
  80.     if (!minarena) {
  81.     minarena = Malloc(-1L) / 10;
  82.     if (minarena > MAXARENA) minarena = MAXARENA;
  83.     }
  84.  
  85.     if (size < minarena) {
  86.     DEBUG('m');
  87.     temp = minarena;
  88.     }
  89.     else {
  90.     DEBUG('s');
  91.     temp = size;
  92.     }
  93.  
  94.     a = Malloc(temp + sizeof(struct arena) + sizeof(struct block));
  95.  
  96.     /* if Malloc failed return failure */
  97.     if (a == 0) {
  98.         DEBUG('x');
  99.         return 0;
  100.     }
  101.  
  102.     a->a_next = a_first;
  103.     a_first = a;
  104.     b = (struct block *)(a+1);
  105.     b->b_next = 0;
  106.     b->b_size = temp;
  107.  
  108. done:
  109.     cut(b,b->b_size,size);
  110.     return (char *)(b+1);
  111. }
  112.  
  113. /*
  114.  * cut: given a block, b, its size, osize, and the first-half size, fsize,
  115.  * split the block (if possible) so it's an allocated block fsize bytes 
  116.  * long, and the rest of the original block becomes a new, free block
  117.  * which is osize-fsize-sizeof(struct block) bytes long.
  118.  *
  119.  * Used on initially-free blocks by lmalloc, and initially-allocated
  120.  * blocks by lrealloc.
  121.  */
  122.  
  123. static cut(b,osize,fsize)
  124. register struct block *b;
  125. register long osize;
  126. register long fsize;
  127. {
  128.     register long temp;
  129.     register struct block *nb;
  130.     
  131.     /* set temp to size of remainder */
  132.     temp = osize - fsize - sizeof(struct block);
  133.  
  134.     if (temp < 0) {
  135.     /* original block too small to cut */
  136.     b->b_size = -osize;
  137.     return;
  138.     }
  139.     /* else block is big enough to cut */
  140.     DEBUG((temp == 0 ? 7 : 'c'));
  141.     nb = ((char *)(b+1)) + fsize;
  142.     nb->b_size = temp;
  143.     nb->b_next = b->b_next;
  144.     b->b_size = -fsize;                /* negative: allocated */
  145.     b->b_next = nb;
  146. };
  147.  
  148. int free(fb)
  149. struct block *fb;
  150. {
  151.     struct arena *a, **p;
  152.     register struct block *b, *pb, *hold;
  153.     register long temp;
  154.  
  155.     DEBUG('F');
  156.     /* set fb (and b) to header start; negate size */
  157.     b = --fb;
  158.     if ((b->b_size *= -1) < 0) {
  159.     /* it was positive to begin with; this isn't an allocated block! */
  160.     b->b_size *= -1;
  161.     return -1;
  162.     }
  163.  
  164.     /* hold gets addr of first block in this area; later, if the block    */
  165.     /* we free & coalesce starts at that addr, then it's the first    */
  166.     /* block in that arena.  If it's also the LAST block, arena's empty    */
  167.     /* and it gets freed.  p is used here, too: it points to the place    */
  168.     /* to stuff a->a_next in order to unlink a from the arena list.    */
  169.  
  170.     for (a = *(p = &a_first); a; a = *(p = &a->a_next)) {
  171.     for (pb = NULL, hold = b = (struct block *)(a+1); 
  172.          b; 
  173.          pb = b, b = b->b_next) {
  174.  
  175.         if (b == fb) {
  176.         /* Found it!  Coalesce backwards if any prev & it's free */
  177.         if (pb != NULL && pb->b_size >= 0) {
  178.             DEBUG('b');
  179.             pb->b_size += sizeof(struct block) + b->b_size;
  180.             pb->b_next = b->b_next;
  181.             b = pb;
  182.         }
  183.         /* coalesce forwards if any next & it's free */
  184.         if (b->b_next && (temp = b->b_next->b_size) >= 0) {
  185.             DEBUG('f');
  186.             b->b_size += temp + sizeof(struct block);
  187.             b->b_next = b->b_next->b_next;
  188.         }
  189.         if ((b == hold) && (b->b_next == 0)) {
  190.             /* this arena now contains one free block: Mfree it! */
  191.             DEBUG('!');
  192.             *p = a->a_next;
  193.             Mfree(a);
  194.         }
  195.         return 0;    /* success! */
  196.         }
  197.     }
  198.     }
  199.  
  200.     /* didn't find this block in any arena! */
  201.     return -1;
  202. }
  203.  
  204. char *malloc(size)
  205. int size;
  206. {
  207.     return (lmalloc((unsigned long)size));
  208. }
  209.  
  210. char *lcalloc(count,size)
  211. long count;
  212. register long size;
  213. {
  214.     register char *buf;
  215.     register int *ptr;
  216.  
  217.     size *= count;
  218.     ptr = buf = lmalloc(size);
  219.     if (!buf) return 0;
  220.  
  221.     /* clear the last odd byte if any */
  222.     if (size & 1) *(buf+size-1) = 0;
  223.  
  224.     /* clear complete words & return */
  225.     size >>= 1;
  226.     do {
  227.     *ptr++ = 0;
  228.     } while (--size);
  229.  
  230.     return buf;
  231. }
  232.  
  233. char *calloc(count,size)
  234. int count, size;
  235. {
  236.     return lcalloc((unsigned long)count,(unsigned long)size);
  237. }
  238.  
  239. /*
  240.  * realloc isn't quite as good as it could be: it doesn't check for a
  241.  * free block BEFORE the block in question, which you could grow into
  242.  * if it's big enough.  The logical place to check this is after coalescing
  243.  * the block in question with the following block, if any.  However,
  244.  * it would add overhead in looking through all the arenas for the
  245.  * predecessor to this block.
  246.  *
  247.  * For that matter, it would help to coalesce previous, current, and next
  248.  * block and copy the useful stuff down, because this would merge the previous
  249.  * and next blocks if they're both free.  But not this time.
  250.  */
  251.  
  252. char *lrealloc(ptr,size)
  253. struct block *ptr;
  254. register long size;
  255. {
  256.     register long osize, nextsize, savsize;
  257.     register struct block *b;
  258.     register int *p1, *p2;
  259.     char *newblk;
  260.     
  261.     DEBUG('R');
  262.     if (size <= 0) return 0;
  263.  
  264.     size = (size+1) & ~1;
  265.  
  266.     b = ptr - 1;
  267.  
  268.     /* remember the size of the original block */
  269.     savsize = osize = -b->b_size;
  270.     
  271.     /* coalesce next block onto this one if there is one and it's free */
  272.  
  273.     if (b->b_next && ((nextsize = b->b_next->b_size) >= 0)) {
  274.     /* tack the next (free) block onto this one */
  275.     DEBUG('-');
  276.     osize += sizeof(struct block) + nextsize;
  277.     b->b_size = -osize;
  278.     b->b_next = b->b_next->b_next;
  279.     }
  280.  
  281.     /* take care of shrinking, and growing in place */
  282.  
  283.     if (osize >= size) {
  284.     DEBUG('<');
  285.     cut(b,osize,size);
  286.     return (char *)(b+1);
  287.     }
  288.  
  289.     /* growing the block and not room to do it in place */
  290.  
  291.     if ((newblk = p1 = lmalloc(size)) == 0) {
  292.     DEBUG('>');
  293.     return 0;
  294.     }
  295.  
  296.     /* copy the original block into the new block */
  297.     p2 = ptr;
  298.     savsize >>= 1;
  299.     do {
  300.     *p1++ = *p2++;
  301.     } while (--savsize);
  302.     free(ptr);
  303.     DEBUG('r');
  304.     return newblk;
  305. }
  306.  
  307. char *realloc(ptr,size)
  308. char *ptr;
  309. int size;
  310. {
  311.     return lrealloc(ptr,(unsigned long)size);
  312. }
  313.