Return to dballoc.c CVS log

Up to [Research Unix] / researchv10dc / libI77 / notused

Annotation of researchv10dc/libI77/notused/dballoc.c, revision 1.1

1.1     ! root        1: /*     @(#)dballoc.c   1.2     */
        !             2: #define debug YES
        !             3: #ifndef debug
        !             4: #define ASSERT(p)
        !             5: #endif
        !             6: #ifdef debug
        !             7: #define ASSERT(p) if(!(p))botch("p");else
        !             8: botch(s)
        !             9: char *s;
        !            10: {
        !            11:        printf("assertion botched: %s\n",s);
        !            12:        abort();
        !            13: }
        !            14: #endif
        !            15: /*     C storage allocator
        !            16:  *     circular first-fit strategy
        !            17:  *     works with noncontiguous, but monotonically linked, arena
        !            18:  *     each block is preceded by a ptr to the (pointer of) 
        !            19:  *     the next following block
        !            20:  *     blocks are exact number of words long; BUSY
        !            21:  *     bit in ptr is 1 for busy, 0 for idle
        !            22:  *     gaps in arena are merely noted as busy blocks
        !            23:  *     last block of arena (pointed to by alloct) is empty and
        !            24:  *     has a pointer to first
        !            25:  *     idle blocks are coalesced during space search
        !            26: */
        !            27: /*     all these defines must be powers of 2 */
        !            28: #define WORD sizeof(struct store)
        !            29: #define BLOCK 1024
        !            30: #define BUSY 1
        !            31: #define NULL 0
        !            32: #define testbusy(p) ((int)(p)&BUSY)
        !            33: #define setbusy(p) (struct store *)((int)(p)+BUSY)
        !            34: #define clearbusy(p) (struct store *)((int)(p)&~BUSY)
        !            35: 
        !            36: struct store { struct store *ptr; };
        !            37: 
        !            38: struct store allocs[] = {      /*initial arena*/
        !            39:        setbusy(&allocs[1].ptr),
        !            40:        setbusy(&allocs[0].ptr)
        !            41: };
        !            42: struct store *allocp = &allocs[1];     /*search ptr*/
        !            43: struct store *alloct = &allocs[1];     /*arena top*/
        !            44: struct store *allocx = 0;              /*for benefit of realloc*/
        !            45: struct store *sbrk();
        !            46: 
        !            47: struct store *
        !            48: malloc(nbytes)
        !            49: unsigned nbytes;
        !            50: {
        !            51:        struct store *p, *q;
        !            52:        register nw;
        !            53:        static temp;    /*coroutines assume no auto*/
        !            54: 
        !            55: #ifdef verbose
        !            56:        printf("malloc(%d) ",nbytes);
        !            57: #endif
        !            58:        nw = (nbytes+2*WORD-1)/WORD;
        !            59:        ASSERT(allocp>allocs && allocp<=alloct);
        !            60:        for(p=allocp; ; ) {
        !            61:                for(temp=0; ; ) {
        !            62:                        if(!testbusy(p->ptr)) {
        !            63:                                while(!testbusy((q=p->ptr)->ptr)) {
        !            64:                                        ASSERT(q>p&&q<alloct);
        !            65:                                        p->ptr = q->ptr;
        !            66:                                }
        !            67:                                if(q>=p+nw && p+nw>=p)
        !            68:                                        goto found;
        !            69:                        }
        !            70:                        q = p;
        !            71:                        p = clearbusy(p->ptr);
        !            72:                        if(p>q)
        !            73:                                ASSERT(p<=alloct);
        !            74:                        else if(q!=alloct || p!=allocs) {
        !            75:                                write(2,"corrupt arena\n",14);
        !            76: #ifdef debug
        !            77:                                abort();
        !            78: #endif
        !            79:                                exit(0175);
        !            80:                        } else if(++temp>1)
        !            81:                                break;
        !            82:                }
        !            83:                temp = (nw+BLOCK/WORD)&~(BLOCK/WORD-1);
        !            84:                q = sbrk(temp*WORD); /*SYSDEP*/
        !            85:                if((int)q == -1)
        !            86:                        return(NULL);
        !            87:                ASSERT(q>alloct);
        !            88:                alloct->ptr = q;
        !            89:                if(q!=alloct+1)
        !            90:                        alloct->ptr = setbusy(alloct->ptr);
        !            91:                alloct = q->ptr = q+temp-1;
        !            92:                alloct->ptr = setbusy(allocs);
        !            93:        }
        !            94: found:
        !            95:        allocp = p + nw;
        !            96:        ASSERT(allocp<=alloct);
        !            97:        if(q>allocp) {
        !            98:                allocx = allocp->ptr;
        !            99:                allocp->ptr = p->ptr;
        !           100:        }
        !           101:        p->ptr = setbusy(allocp);
        !           102: #ifdef verbose
        !           103:        printf("= %o\n",p+1);
        !           104: #endif
        !           105:        return(p+1);
        !           106: }
        !           107: /*     freeing strategy tuned for LIFO allocation
        !           108: */
        !           109: free(p)
        !           110:  struct store *p;
        !           111: {
        !           112:        struct store *savep=p;
        !           113: #ifdef verbose
        !           114:        printf("free(%o)\n",p);
        !           115: #endif
        !           116:        ASSERT(p>clearbusy(allocs[1].ptr)&&p<=alloct);
        !           117:        allocp = --p;
        !           118:        ASSERT(testbusy(p->ptr));
        !           119:        p->ptr = clearbusy(p->ptr);
        !           120:        ASSERT(p->ptr > allocp && p->ptr <= alloct);
        !           121: }
        !           122: char *calloc(nbytes,count)
        !           123: {      char *c;
        !           124:        c=(char *)malloc(nbytes*count);
        !           125:        return(c);
        !           126: }
        !           127: /*
        !           128: ahist(s) char *s;
        !           129: {      char **ap;
        !           130:        printf("%s allocp %o alloct %o\n",s,allocp,alloct);
        !           131:        for(ap= allocs;ap<alloct;ap= *ap&~BUSY)
        !           132:                if(*ap&BUSY) printf("%o ",ap);
        !           133:        printf("\n");
        !           134: }
        !           135: */
        !           136: struct store *
        !           137: realloc(p, nbytes)
        !           138: register struct store *p;
        !           139: unsigned nbytes;
        !           140: {
        !           141:        register struct store *q;
        !           142:        struct store *s, *t;
        !           143:        register unsigned nw;
        !           144:        unsigned onw;
        !           145: 
        !           146:        onw = p[-1].ptr - p;
        !           147:        q = malloc(nbytes);
        !           148:        if(q==NULL || q==p)
        !           149:                return(q);
        !           150:        s = p;
        !           151:        t = q;
        !           152:        nw = (nbytes+WORD-1)/WORD;
        !           153:        if(nw<onw)
        !           154:                onw = nw;
        !           155:        while(onw--!=0)
        !           156:                (t++)->ptr = (s++)->ptr;
        !           157:        if(q<p && q+nw>=p)
        !           158:                (q+(q+nw-p))->ptr = allocx;
        !           159:        return(q);
        !           160: }

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