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