Return to alloc.c CVS log

Up to [Research Unix] / researchv9 / jerq / src / lib / j

Annotation of researchv9/jerq/src/lib/j/alloc.c, revision 1.1

1.1     ! root        1: #ifdef alloc
        !             2: #undef alloc
        !             3: #undef free
        !             4: #endif
        !             5: #ifdef debug
        !             6: #define ASSERT(p) if(!(p))botch("p");else
        !             7: botch(s)
        !             8: char *s;
        !             9: {
        !            10:        printf("assertion botched: %s\n",s);
        !            11:        abort();
        !            12: }
        !            13: #else
        !            14: #define ASSERT(p)
        !            15: #endif
        !            16: 
        !            17: /*     C storage allocator
        !            18:  *     first-fit strategy
        !            19:  *     works with noncontiguous, but monotonically linked, arena
        !            20:  *     each block is preceded by a ptr to the (pointer of) 
        !            21:  *     the next following block
        !            22:  *     blocks are exact number of words long 
        !            23:  *     aligned to the data type requirements of ALIGN
        !            24:  *     pointers to blocks must have BUSY bit 0
        !            25:  *     bit in ptr is 1 for busy, 0 for idle
        !            26:  *     gaps in arena are merely noted as busy blocks
        !            27:  *     last block of arena is empty and
        !            28:  *     has a pointer to first
        !            29:  *     idle blocks are coalesced during space search
        !            30:  *
        !            31:  *     a different implementation may need to redefine
        !            32:  *     ALIGN, NALIGN, BUSY, INT
        !            33:  *     where INT is integer type to which a pointer can be cast
        !            34: */
        !            35: #define INT long
        !            36: #define ALIGN int
        !            37: #define NALIGN 1
        !            38: #define WORD sizeof(union store)
        !            39: #define BUSY 1
        !            40: #define NULL 0
        !            41: #define testbusy(p) ((INT)(p)&BUSY)
        !            42: #define setbusy(p) (union store *)((INT)(p)|BUSY)
        !            43: #define clearbusy(p) (union store *)((INT)(p)&~BUSY)
        !            44: 
        !            45: union store {
        !            46:        struct {
        !            47:                union store *Uptr;
        !            48:                char * Uproc;   /* pointer to process of allocating guy */
        !            49:        } u;
        !            50:        union store *ptr;
        !            51:        ALIGN dummy[NALIGN];
        !            52:        int calloc;     /*calloc clears an array of integers*/
        !            53: };
        !            54: #define        proc    u.Uproc
        !            55: 
        !            56: char *allocstartp;     /* &end, but passed in because this is in ROM */
        !            57: char *allocendp;       /* should adjust according to load */
        !            58: #define        START   allocstartp
        !            59: #define        FIRSTWORD ((union store *)(START))
        !            60: #define        LASTWORD ((union store *)(allocendp-4))
        !            61: static union store *allocb;    /*arena base*/
        !            62: #ifdef REALLOC
        !            63: static union store *allocx;    /*for benefit of realloc*/
        !            64: #endif
        !            65: 
        !            66: allocinit(s, e)
        !            67:        int *s, *e;
        !            68: {
        !            69:        allocstartp=(char *)s;
        !            70:        allocendp=(char *)e;
        !            71:        FIRSTWORD->ptr = LASTWORD;
        !            72:        LASTWORD->ptr = (union store *)(START+1);
        !            73:        allocb = (union store *)START;
        !            74: }
        !            75: 
        !            76: char *
        !            77: realalloc(nbytes, whichproc)
        !            78:        unsigned nbytes;
        !            79:        char *whichproc;
        !            80: {
        !            81:        register union store *p, *q;
        !            82:        register nw;
        !            83:        register union store *allocp;
        !            84:        static int temp;
        !            85: 
        !            86:        nw = (nbytes+WORD+WORD-1)/WORD;
        !            87:        ASSERT(allock(allocb));
        !            88:        for(; ; ) {     /* done at most twice */
        !            89:                p = allocb;
        !            90:                allocp = allocb;
        !            91:                for(temp=0; ; ) {
        !            92:                        if(!testbusy(p->ptr)) {
        !            93:                                while(!testbusy((q=p->ptr)->ptr)) {
        !            94:                                        ASSERT(q>p);
        !            95:                                        p->ptr = q->ptr;
        !            96:                                        allocp = p;
        !            97:                                }
        !            98:                                if(q>=p+nw && p+nw>=p)
        !            99:                                        goto found;
        !           100:                        }
        !           101:                        q = p;
        !           102:                        p = clearbusy(p->ptr);
        !           103:                        if(p <= q) {
        !           104:                                ASSERT(p==allocb);
        !           105:                                if(p != allocb)
        !           106:                                        return(NULL);
        !           107:                                if(++temp > 1)
        !           108:                                        break;
        !           109:                        }
        !           110:                }
        !           111:                return NULL;    /* get more space, someday */
        !           112:        }
        !           113: found:
        !           114:        allocp = p + nw;
        !           115:        if(q>allocp) {
        !           116: #ifdef REALLOC
        !           117:                allocx = allocp->ptr;
        !           118: #endif
        !           119:                allocp->ptr = p->ptr;
        !           120:        }
        !           121:        p->ptr = setbusy(allocp);
        !           122:        /* clear the storage, for jerqs only */
        !           123:        for(q=p+1; q<p+nw; q++){
        !           124:                q->ptr=0;
        !           125:                q->proc=0;      /* cough */
        !           126:        }
        !           127:        p->proc = whichproc;
        !           128:        return((char *)(p+1));
        !           129: }
        !           130: 
        !           131: char *
        !           132: alloc(nbytes)
        !           133:        unsigned nbytes;
        !           134: {
        !           135:        return realalloc(nbytes, (char *)0);
        !           136: }
        !           137: 
        !           138: /*     freeing strategy tuned for LIFO allocation
        !           139: */
        !           140: free(ap)
        !           141: char *ap;
        !           142: {
        !           143:        register union store *p = (union store *)ap-1;
        !           144: 
        !           145:        ASSERT(allock(p));
        !           146:        ASSERT(testbusy(p->ptr));
        !           147:        p->ptr = clearbusy(p->ptr);
        !           148:        p->proc = 0;
        !           149:        ASSERT(p->ptr > p);
        !           150: }
        !           151: 
        !           152: /*     free all storage associated with the named process
        !           153: */
        !           154: freeall(whichproc)
        !           155:        register char *whichproc;
        !           156: {
        !           157:        register union store *p, *r;
        !           158: 
        !           159:        if ((p=allocb)->proc == whichproc)      /* first block on chain */
        !           160:                free((char *)(p+1));
        !           161:        for(p=allocb; (r=clearbusy(p->ptr)) > p; p=r)   /* rest of chain... */
        !           162:                if((r->proc == whichproc) && (r != LASTWORD))
        !           163:                        free((char *)(r+1));            /* ...except LASTWORD */
        !           164:        gcfreeall(whichproc);
        !           165: }
        !           166: 
        !           167: #ifdef REALLOC
        !           168: /*     realloc(p, nbytes) reallocates a block obtained from alloc()
        !           169:  *     and freed since last call of alloc()
        !           170:  *     to have new size nbytes, and old content
        !           171:  *     returns new location, or 0 on failure
        !           172: */
        !           173: 
        !           174: char *
        !           175: realloc(pp, nbytes)
        !           176: char *pp;
        !           177: unsigned nbytes;
        !           178: {
        !           179:        register union store *q;
        !           180:        register union store *p = (union store *)pp;
        !           181:        union store *s, *t;
        !           182:        register unsigned nw;
        !           183:        unsigned onw;
        !           184: 
        !           185:        ASSERT(allock(p-1));
        !           186:        if(testbusy(p[-1].ptr))
        !           187:                free((char *)p);
        !           188:        onw = p[-1].ptr - p;
        !           189:        q = (union store *)alloc(nbytes);
        !           190:        if(q==NULL || q==p)
        !           191:                return((char *)q);
        !           192:        ASSERT(q<p||q>p[-1].ptr);
        !           193:        s = p;
        !           194:        t = q;
        !           195:        nw = (nbytes+WORD-1)/WORD;
        !           196:        if(nw<onw)
        !           197:                onw = nw;
        !           198:        while(onw--!=0)
        !           199:                *t++ = *s++;
        !           200:        ASSERT(clearbusy(q[-1].ptr)-q==nw);
        !           201:        if(q<p && q+nw>=p)
        !           202:                (q+(q+nw-p))->ptr = allocx;
        !           203:        ASSERT(allock(q-1));
        !           204:        return((char *)q);
        !           205: }
        !           206: #endif
        !           207: 
        !           208: #ifdef debug
        !           209: allock(q)
        !           210: union store *q;
        !           211: {
        !           212: #ifdef longdebug
        !           213:        register union store *p, *r;
        !           214:        int x;
        !           215:        x = 0;
        !           216:        p = allocb;
        !           217:        if(((union store *)START)->ptr==0)
        !           218:                return(1);
        !           219:        for( ; (r=clearbusy(p->ptr)) > p; p=r) {
        !           220:                if(p==q)
        !           221:                        x++;
        !           222:        }
        !           223:        return(r==allocb&(x==1|p==q));
        !           224: #else
        !           225:        return(q>=allocb);
        !           226: #endif
        !           227: }
        !           228: abort(){
        !           229:        printf("abort\n");
        !           230:        for(;;);
        !           231: }
        !           232: #endif

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