Return to alloc.c CVS log

Up to [CSRG BSD Unix] / 42BSD / bin / csh

Annotation of 42BSD/bin/csh/alloc.c, revision 1.1

1.1     ! root        1: static char *sccsid = "@(#)alloc.c 4.2 2/9/83";
        !             2: 
        !             3: #include "sh.local.h"
        !             4: #ifdef debug
        !             5: #define ASSERT(p) if(!(p))botch("p");else
        !             6: botch(s)
        !             7: char *s;
        !             8: {
        !             9:        printf("assertion botched: %s\n",s);
        !            10:        abort();
        !            11: }
        !            12: #else
        !            13: #define ASSERT(p)
        !            14: #endif
        !            15: 
        !            16: /*     avoid break bug */
        !            17: #ifdef pdp11
        !            18: #define GRANULE 64
        !            19: #else
        !            20: #define GRANULE 0
        !            21: #endif
        !            22: /*     C storage allocator
        !            23:  *     circular first-fit strategy
        !            24:  *     works with noncontiguous, but monotonically linked, arena
        !            25:  *     each block is preceded by a ptr to the (pointer of) 
        !            26:  *     the next following block
        !            27:  *     blocks are exact number of words long 
        !            28:  *     aligned to the data type requirements of ALIGN
        !            29:  *     pointers to blocks must have BUSY bit 0
        !            30:  *     bit in ptr is 1 for busy, 0 for idle
        !            31:  *     gaps in arena are merely noted as busy blocks
        !            32:  *     last block of arena (pointed to by alloct) is empty and
        !            33:  *     has a pointer to first
        !            34:  *     idle blocks are coalesced during space search
        !            35:  *
        !            36:  *     a different implementation may need to redefine
        !            37:  *     ALIGN, NALIGN, BLOCK, BUSY, INT
        !            38:  *     where INT is integer type to which a pointer can be cast
        !            39: */
        !            40: #define INT int
        !            41: #define ALIGN int
        !            42: #define NALIGN 1
        !            43: #define WORD sizeof(union store)
        !            44: #define BLOCK 1024     /* a multiple of WORD*/
        !            45: #define BUSY 1
        !            46: #define NULL 0
        !            47: #define testbusy(p) ((INT)(p)&BUSY)
        !            48: #define setbusy(p) (union store *)((INT)(p)|BUSY)
        !            49: #define clearbusy(p) (union store *)((INT)(p)&~BUSY)
        !            50: 
        !            51: union store { union store *ptr;
        !            52:              ALIGN dummy[NALIGN];
        !            53:              int calloc;       /*calloc clears an array of integers*/
        !            54: };
        !            55: 
        !            56: static union store allocs[2];  /*initial arena*/
        !            57: static union store *allocp;    /*search ptr*/
        !            58: static union store *alloct;    /*arena top*/
        !            59: static union store *allocx;    /*for benefit of realloc*/
        !            60: char   *sbrk();
        !            61: 
        !            62: char *
        !            63: malloc(nbytes)
        !            64: unsigned nbytes;
        !            65: {
        !            66:        register union store *p, *q;
        !            67:        register nw;
        !            68:        static temp;    /*coroutines assume no auto*/
        !            69: 
        !            70:        if(allocs[0].ptr==0) {  /*first time*/
        !            71:                allocs[0].ptr = setbusy(&allocs[1]);
        !            72:                allocs[1].ptr = setbusy(&allocs[0]);
        !            73:                alloct = &allocs[1];
        !            74:                allocp = &allocs[0];
        !            75:        }
        !            76:        nw = (nbytes+WORD+WORD-1)/WORD;
        !            77:        ASSERT(allocp>=allocs && allocp<=alloct);
        !            78:        ASSERT(allock());
        !            79:        for(p=allocp; ; ) {
        !            80:                for(temp=0; ; ) {
        !            81:                        if(!testbusy(p->ptr)) {
        !            82:                                while(!testbusy((q=p->ptr)->ptr)) {
        !            83:                                        ASSERT(q>p&&q<alloct);
        !            84:                                        p->ptr = q->ptr;
        !            85:                                }
        !            86:                                if(q>=p+nw && p+nw>=p)
        !            87:                                        goto found;
        !            88:                        }
        !            89:                        q = p;
        !            90:                        p = clearbusy(p->ptr);
        !            91:                        if(p>q)
        !            92:                                ASSERT(p<=alloct);
        !            93:                        else if(q!=alloct || p!=allocs) {
        !            94:                                ASSERT(q==alloct&&p==allocs);
        !            95:                                return(NULL);
        !            96:                        } else if(++temp>1)
        !            97:                                break;
        !            98:                }
        !            99:                temp = ((nw+BLOCK/WORD)/(BLOCK/WORD))*(BLOCK/WORD);
        !           100:                q = (union store *)sbrk(0);
        !           101:                if(q+temp+GRANULE < q) {
        !           102:                        return(NULL);
        !           103:                }
        !           104:                q = (union store *)sbrk(temp*WORD);
        !           105:                if((INT)q == -1) {
        !           106:                        return(NULL);
        !           107:                }
        !           108:                ASSERT(q>alloct);
        !           109:                alloct->ptr = q;
        !           110:                if(q!=alloct+1)
        !           111:                        alloct->ptr = setbusy(alloct->ptr);
        !           112:                alloct = q->ptr = q+temp-1;
        !           113:                alloct->ptr = setbusy(allocs);
        !           114:        }
        !           115: found:
        !           116:        allocp = p + nw;
        !           117:        ASSERT(allocp<=alloct);
        !           118:        if(q>allocp) {
        !           119:                allocx = allocp->ptr;
        !           120:                allocp->ptr = p->ptr;
        !           121:        }
        !           122:        p->ptr = setbusy(allocp);
        !           123:        return((char *)(p+1));
        !           124: }
        !           125: 
        !           126: /*     freeing strategy tuned for LIFO allocation
        !           127: */
        !           128: free(ap)
        !           129: register char *ap;
        !           130: {
        !           131:        register union store *p = (union store *)ap;
        !           132: 
        !           133:        ASSERT(p>clearbusy(allocs[1].ptr)&&p<=alloct);
        !           134:        ASSERT(allock());
        !           135:        allocp = --p;
        !           136: /*     ASSERT(testbusy(p->ptr)); */
        !           137:        p->ptr = clearbusy(p->ptr);
        !           138:        ASSERT(p->ptr > allocp && p->ptr <= alloct);
        !           139: }
        !           140: 
        !           141: /*     realloc(p, nbytes) reallocates a block obtained from malloc()
        !           142:  *     and freed since last call of malloc()
        !           143:  *     to have new size nbytes, and old content
        !           144:  *     returns new location, or 0 on failure
        !           145: */
        !           146: 
        !           147: char *
        !           148: realloc(p, nbytes)
        !           149: register union store *p;
        !           150: unsigned nbytes;
        !           151: {
        !           152:        register union store *q;
        !           153:        union store *s, *t;
        !           154:        register unsigned nw;
        !           155:        unsigned onw;
        !           156: 
        !           157:        if(testbusy(p[-1].ptr))
        !           158:                free((char *)p);
        !           159:        onw = p[-1].ptr - p;
        !           160:        q = (union store *)malloc(nbytes);
        !           161:        if(q==NULL || q==p)
        !           162:                return((char *)q);
        !           163:        s = p;
        !           164:        t = q;
        !           165:        nw = (nbytes+WORD-1)/WORD;
        !           166:        if(nw<onw)
        !           167:                onw = nw;
        !           168:        while(onw--!=0)
        !           169: #ifdef V6
        !           170:                copy(t++, s++, sizeof (*t));
        !           171: #else
        !           172:                *t++ = *s++;
        !           173: #endif
        !           174:        if(q<p && q+nw>=p)
        !           175:                (q+(q+nw-p))->ptr = allocx;
        !           176:        return((char *)q);
        !           177: }
        !           178: 
        !           179: #ifdef debug
        !           180: allock()
        !           181: {
        !           182: #ifdef longdebug
        !           183:        register union store *p;
        !           184:        int x;
        !           185:        x = 0;
        !           186:        for(p= &allocs[0]; clearbusy(p->ptr) > p; p=clearbusy(p->ptr)) {
        !           187:                if(p==allocp)
        !           188:                        x++;
        !           189:        }
        !           190:        ASSERT(p==alloct);
        !           191:        return(x==1|p==allocp);
        !           192: #else
        !           193:        return(1);
        !           194: #endif
        !           195: }
        !           196: #endif
        !           197: 
        !           198: #ifdef debug
        !           199: showall(v)
        !           200:        char **v;
        !           201: {
        !           202:        register union store *p, *q;
        !           203:        int used = 0, free = 0, i;
        !           204: 
        !           205:        for (p = clearbusy(allocs[1].ptr); p != alloct; p = q) {
        !           206:                q = clearbusy(p->ptr);
        !           207:                if (v[1])
        !           208:                printf("%6o %5d %s\n", p,
        !           209:                    ((unsigned) q - (unsigned) p),
        !           210:                    testbusy(p->ptr) ? "BUSY" : "FREE");
        !           211:                i = ((unsigned) q - (unsigned) p);
        !           212:                if (testbusy(p->ptr)) used += i; else free += i;
        !           213:        }
        !           214:        printf("%d used, %d free, %ld end\n", used, free, clearbusy(alloct));
        !           215: }
        !           216: #endif

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