Return to alloc.c CVS log

Up to [MW Coherent from dump] / coherent / a / usr / bob / korn

Annotation of coherent/a/usr/bob/korn/alloc.c, revision 1.1

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

This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.