Return to malloc.c CVS log

Up to [CSRG BSD Unix] / 43BSDTahoe / new / jove

Annotation of 43BSDTahoe/new/jove/malloc.c, revision 1.1

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

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