home *** CD-ROM | disk | FTP | other *** search
/ The World of Computer Software / World_Of_Computer_Software-02-385-Vol-1of3.iso / k / ksh48.zip / sh / alloc.c next >
C/C++ Source or Header  |  1992-05-03  |  5KB  |  248 lines
  1. /*
  2.  * area-based allocation built on malloc/free
  3.  */
  4.  
  5. #ifndef lint
  6. static char *RCSid = "$Id: alloc.c,v 1.2 1992/04/25 08:33:28 sjg Exp $";
  7. #endif
  8.  
  9. #include "stdh.h"
  10. #include <setjmp.h>
  11. #include <sys/types.h>
  12. #include "sh.h"
  13.  
  14. #define    ICELLS    100        /* number of Cells in small Block */
  15.  
  16. typedef union Cell Cell;
  17. typedef struct Block Block;
  18.  
  19. /*
  20.  * The Cells in a Block are organized as a set of objects.
  21.  * Each object (pointed to by dp) begins with a size in (dp-1)->size,
  22.  * followed with "size" data Cells.  Free objects are
  23.  * linked together via dp->next.
  24.  */
  25.  
  26. union Cell {
  27.     size_t    size;
  28.     union Cell   *next;
  29.     struct {int _;} junk;    /* alignment */
  30. };
  31.  
  32. struct Block {
  33.     struct Block  *next;        /* list of Blocks in Area */
  34.     union Cell   *free;        /* object free list */
  35.     union Cell   *last;        /* &b.cell[size] */
  36.     union Cell    cell [1];    /* [size] Cells for allocation */
  37. };
  38.  
  39. Block aempty = {&aempty, aempty.cell, aempty.cell};
  40.  
  41. /* create empty Area */
  42. Area *
  43. ainit(ap)
  44.     register Area *ap;
  45. {
  46.     ap->free = &aempty;
  47.     return ap;
  48. }
  49.  
  50. /* free all object in Area */
  51. void
  52. afreeall(ap)
  53.     register Area *ap;
  54. {
  55.     register Block *bp;
  56.     register Block *tmp;
  57.  
  58.     bp = ap->free;
  59.     if (bp != NULL && bp != &aempty) {
  60.         do {
  61.             tmp = bp->next;
  62.             free((void*)bp);
  63.             bp = tmp;
  64.         } while (bp != ap->free);
  65.         ap->free = &aempty;
  66.     }
  67. }
  68.  
  69. /* allocate object from Area */
  70. void *
  71. alloc(size, ap)
  72.     size_t size;
  73.     register Area *ap;
  74. {
  75.     int cells, split;
  76.     register Block *bp;
  77.     register Cell *dp, *fp, *fpp;
  78.  
  79.     if (size <= 0) {
  80.         aerror(ap, "allocate bad size");
  81.         return NULL;
  82.     }
  83.     cells = (unsigned)(size - 1) / sizeof(Cell) + 1;
  84.  
  85.     /* find Cell large enough */
  86.     for (bp = ap->free; ; bp = bp->next) {
  87.         for (fpp = NULL, fp = bp->free;
  88.              fp != bp->last; fpp = fp, fp = fpp->next)
  89.             if ((fp-1)->size >= cells)
  90.                 goto Found;
  91.  
  92.         /* wrapped around Block list, create new Block */
  93.         if (bp->next == ap->free) {
  94.             bp = (Block*) malloc(offsetof(Block, cell[ICELLS + cells]));
  95.             if (bp == NULL) {
  96.                 aerror(ap, "cannot allocate");
  97.                 return NULL;
  98.             }
  99.             if (ap->free == &aempty)
  100.                 bp->next = bp;
  101.             else {
  102.                 bp->next = ap->free->next;
  103.                 ap->free->next = bp;
  104.             }
  105.             bp->last = bp->cell + ICELLS + cells;
  106.             fp = bp->free = bp->cell + 1; /* initial free list */
  107.             (fp-1)->size = ICELLS + cells - 1;
  108.             fp->next = bp->last;
  109.             fpp = NULL;
  110.             break;
  111.         }
  112.     }
  113.   Found:
  114.     ap->free = bp;
  115.     dp = fp;        /* allocated object */
  116.     split = (dp-1)->size - cells;
  117.     if (split < 0)
  118.         aerror(ap, "allocated object too small");
  119.     if (--split <= 0) {    /* allocate all */
  120.         fp = fp->next;
  121.     } else {        /* allocate head, free tail */
  122.         (fp-1)->size = cells;
  123.         fp += cells + 1;
  124.         (fp-1)->size = split;
  125.         fp->next = dp->next;
  126.     }
  127.     if (fpp == NULL)
  128.         bp->free = fp;
  129.     else
  130.         fpp->next = fp;
  131.     return (void*) dp;
  132. }
  133.  
  134. /* change size of object -- like realloc */
  135. void *
  136. aresize(ptr, size, ap)
  137.     register void *ptr;
  138.     size_t size;
  139.     Area *ap;
  140. {
  141.     int cells;
  142.     register Cell *dp = (Cell*) ptr;
  143.  
  144.     if (size <= 0) {
  145.         aerror(ap, "allocate bad size");
  146.         return NULL;
  147.     }
  148.     cells = (unsigned)(size - 1) / sizeof(Cell) + 1;
  149.  
  150.     if (dp == NULL || (dp-1)->size < cells) { /* enlarge object */
  151.         register Cell *np;
  152.         register int i;
  153.         void *optr = ptr;
  154.  
  155.         ptr = alloc(size, ap);
  156.         np = (Cell*) ptr;
  157.         if (dp != NULL)
  158.             for (i = (dp-1)->size; i--; )
  159.                 *np++ = *dp++;
  160.         afree(optr, ap);
  161.     } else {        /* shrink object */
  162.         int split;
  163.  
  164.         split = (dp-1)->size - cells;
  165.         if (--split <= 0) /* cannot split */
  166.             ;
  167.         else {        /* shrink head, free tail */
  168.             (dp-1)->size = cells;
  169.             dp += cells + 1;
  170.             (dp-1)->size = split;
  171.             afree((void*)dp, ap);
  172.         }
  173.     }
  174.     return (void*) ptr;
  175. }
  176.  
  177. void
  178. afree(ptr, ap)
  179.     void *ptr;
  180.     register Area *ap;
  181. {
  182.     register Block *bp;
  183.     register Cell *fp, *fpp;
  184.     register Cell *dp = (Cell*)ptr;
  185.  
  186.     /* find Block containing Cell */
  187.     for (bp = ap->free; ; bp = bp->next) {
  188.         if (bp->cell <= dp && dp < bp->last)
  189.             break;
  190.         if (bp->next == ap->free) {
  191.             aerror(ap, "freeing with invalid area");
  192.             return;
  193.         }
  194.     }
  195.  
  196.     /* find position in free list */
  197.     for (fpp = NULL, fp = bp->free; fp < dp; fpp = fp, fp = fpp->next)
  198.         ;
  199.  
  200.     if (fp == dp) {
  201.         aerror(ap, "freeing free object");
  202.         return;
  203.     }
  204.  
  205.     /* join object with next */
  206.     if (dp + (dp-1)->size == fp-1) { /* adjacent */
  207.         (dp-1)->size += (fp-1)->size + 1;
  208.         dp->next = fp->next;
  209.     } else            /* non-adjacent */
  210.         dp->next = fp;
  211.  
  212.     /* join previous with object */
  213.     if (fpp == NULL)
  214.         bp->free = dp;
  215.     else if (fpp + (fpp-1)->size == dp-1) { /* adjacent */
  216.         (fpp-1)->size += (dp-1)->size + 1;
  217.         fpp->next = dp->next;
  218.     } else            /* non-adjacent */
  219.         fpp->next = dp;
  220. }
  221.  
  222.  
  223. #if TEST_ALLOC
  224.  
  225. Area a;
  226.  
  227. main(int argc, char **argv) {
  228.     int i;
  229.     char *p [9];
  230.  
  231.     ainit(&a);
  232.     for (i = 0; i < 9; i++) {
  233.         p[i] = alloc(124, &a);
  234.         printf("alloc: %x\n", p[i]);
  235.     }
  236.     for (i = 1; i < argc; i++)
  237.         afree(p[atoi(argv[i])], &a);
  238.     afreeall(&a);
  239.     return 0;
  240. }
  241.  
  242. void aerror(Area *ap, const char *msg) {
  243.     abort();
  244. }
  245.  
  246. #endif
  247.  
  248.