4.3BSD - /usr/src/new/jove/malloc.c

   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

Defined functions

Defined variables

Defined union's

Defined macros