Return to malloc.c CVS log

Up to [CSRG BSD Unix] / 43BSD / contrib / jove

Annotation of 43BSD/contrib/jove/malloc.c, revision 1.1

1.1     ! root        1: /*************************************************************************
        !             2:  * This program is copyright (C) 1985, 1986 by Jonathan Payne.  It is    *
        !             3:  * provided to you without charge for use only on a licensed Unix        *
        !             4:  * system.  You may copy JOVE provided that this notice is included with *
        !             5:  * the copy.  You may not sell copies of this program or versions        *
        !             6:  * modified for use on microcomputer systems, unless the copies are      *
        !             7:  * included with a Unix system distribution and the source is provided.  *
        !             8:  *************************************************************************/
        !             9: 
        !            10: #include "tune.h"
        !            11: 
        !            12: #ifdef MY_MALLOC
        !            13: 
        !            14: /*     avoid break bug */
        !            15: #ifdef pdp11
        !            16: #      define GRANULE 64
        !            17: #else
        !            18: #      define GRANULE 0
        !            19: #endif
        !            20: 
        !            21: /*     C storage allocator
        !            22:  *     circular first-fit strategy
        !            23:  *     works with noncontiguous, but monotonically linked, arena
        !            24:  *     each block is preceded by a ptr to the (pointer of) 
        !            25:  *     the next following block
        !            26:  *     blocks are exact number of words long 
        !            27:  *     aligned to the data type requirements of ALIGN
        !            28:  *     pointers to blocks must have BUSY bit 0
        !            29:  *     bit in ptr is 1 for busy, 0 for idle
        !            30:  *     gaps in arena are merely noted as busy blocks
        !            31:  *     last block of arena (pointed to by alloct) is empty and
        !            32:  *     has a pointer to first
        !            33:  *     idle blocks are coalesced during space search
        !            34:  *
        !            35:  *     a different implementation may need to redefine
        !            36:  *     ALIGN, NALIGN, BLOCK, BUSY, INT
        !            37:  *     where INT is integer type to which a pointer can be cast
        !            38:  */
        !            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 {
        !            52:        union store     *ptr;
        !            53:        ALIGN   dummy[NALIGN];
        !            54:        int     calloc;         /*calloc clears an array of integers*/
        !            55: };
        !            56: 
        !            57: static union store     allocs[2],      /*initial arena*/
        !            58:                        *allocp,        /*search ptr*/
        !            59:                        *alloct,        /*arena top*/
        !            60:                        *allocx;        /*for benefit of realloc*/
        !            61: 
        !            62: char   *sbrk();
        !            63: 
        !            64: char *
        !            65: malloc(nbytes)
        !            66: unsigned int   nbytes;
        !            67: {
        !            68:        register union store    *p,
        !            69:                                *q;
        !            70:        register int    nw;
        !            71:        static int      temp;   /* coroutines assume no auto */
        !            72: 
        !            73:        if (allocs[0].ptr == 0) {       /* first time */
        !            74:                allocs[0].ptr = setbusy(&allocs[1]);
        !            75:                allocs[1].ptr = setbusy(&allocs[0]);
        !            76:                alloct = &allocs[1];
        !            77:                allocp = &allocs[0];
        !            78:        }
        !            79:        nw = (nbytes + WORD + WORD - 1) / WORD;
        !            80:        for (p = allocp; ; ) {
        !            81:                for (temp = 0; ; ) {
        !            82:                        if (!testbusy(p->ptr)) {
        !            83:                                while (!testbusy((q = p->ptr)->ptr))
        !            84:                                        p->ptr = q->ptr;
        !            85:                                if(q >= p + nw && p + nw >= p)
        !            86:                                        goto found;
        !            87:                        }
        !            88:                        q = p;
        !            89:                        p = clearbusy(p->ptr);
        !            90:                        if (p > q)
        !            91:                                ;
        !            92:                        else if (q != alloct || p != allocs)
        !            93:                                return NULL;
        !            94:                        else if (++temp > 1)
        !            95:                                break;
        !            96:                }
        !            97:                temp = ((nw + BLOCK/WORD) / (BLOCK/WORD)) * (BLOCK/WORD);
        !            98:                q = (union store *) sbrk(0);
        !            99:                if (q + temp + GRANULE < q)
        !           100:                        return NULL;
        !           101:                q = (union store *) sbrk(temp * WORD);
        !           102:                if ((INT) q == -1)
        !           103:                        return NULL;
        !           104:                alloct->ptr = q;
        !           105:                if (q != alloct+1)
        !           106:                        alloct->ptr = setbusy(alloct->ptr);
        !           107:                alloct = q->ptr = q + temp - 1;
        !           108:                alloct->ptr = setbusy(allocs);
        !           109:        }
        !           110: found:
        !           111:        allocp = p + nw;
        !           112:        if (q > allocp) {
        !           113:                allocx = allocp->ptr;
        !           114:                allocp->ptr = p->ptr;
        !           115:        }
        !           116:        p->ptr = setbusy(allocp);
        !           117:        return (char *) (p + 1);
        !           118: }
        !           119: 
        !           120: /* freeing strategy tuned for LIFO allocation */
        !           121: 
        !           122: free(ap)
        !           123: register char  *ap;
        !           124: {
        !           125:        register union store    *p = (union store *) ap;
        !           126: 
        !           127:        allocp = --p;
        !           128:        p->ptr = clearbusy(p->ptr);
        !           129: }
        !           130: 
        !           131: /*     realloc(p, nbytes) reallocates a block obtained from malloc()
        !           132:  *     and freed since last call of malloc()
        !           133:  *     to have new size nbytes, and old content
        !           134:  *     returns new location, or 0 on failure
        !           135: */
        !           136: 
        !           137: char *
        !           138: realloc(obj, nbytes)
        !           139: char   *obj;
        !           140: unsigned int   nbytes;
        !           141: {
        !           142:        register union store    *q,
        !           143:                                *p = (union store *) obj;
        !           144:        union store     *s,
        !           145:                        *t;
        !           146:        register unsigned int   nw;
        !           147:        unsigned int    onw;
        !           148: 
        !           149:        if (testbusy(p[-1].ptr))
        !           150:                free((char *) p);
        !           151:        onw = p[-1].ptr - p;
        !           152:        q = (union store *) malloc(nbytes);
        !           153:        if(q == NULL || q == p)
        !           154:                return((char *) q);
        !           155:        s = p;
        !           156:        t = q;
        !           157:        nw = (nbytes + WORD - 1)/WORD;
        !           158:        if (nw < onw)
        !           159:                onw = nw;
        !           160:        while (onw-- != 0)
        !           161:                *t++ = *s++;
        !           162:        if(q < p && q + nw >= p)
        !           163:                (q + (q+nw-p))->ptr = allocx;
        !           164:        return (char *) q;
        !           165: }
        !           166: 
        !           167: #endif MY_MALLOC

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