2.11BSD#431 - /usr/src/new/jove/malloc.c

   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 */

Defined functions

Defined variables

Defined union's

Defined macros