2.9BSD - /usr/src/lib/libI77/dballoc.c

   1: /*
   2: char id_dballoc[] = "@(#)dballoc.c	1.1";
   3:  *
   4:  *	C storage allocator
   5:  *	circular first-fit strategy
   6:  *	works with noncontiguous, but monotonically linked, arena
   7:  *	each block is preceded by a ptr to the (pointer of)
   8:  *	the next following block
   9:  *	blocks are exact number of words long; BUSY
  10:  *	bit in ptr is 1 for busy, 0 for idle
  11:  *	gaps in arena are merely noted as busy blocks
  12:  *	last block of arena (pointed to by alloct) is empty and
  13:  *	has a pointer to first
  14:  *	idle blocks are coalesced during space search
  15: */
  16: 
  17: #include    <stdio.h>
  18: #include    "f_errno.h"
  19: 
  20: /*	all these defines must be powers of 2 */
  21: #define WORD sizeof(struct store)
  22: #define BLOCK 1024
  23: #define BUSY 1
  24: #define NULL 0
  25: #define testbusy(p) ((int)(p)&BUSY)
  26: #define setbusy(p) (struct store *)((int)(p)+BUSY)
  27: #define clearbusy(p) (struct store *)((int)(p)&~BUSY)
  28: 
  29: /*
  30: #define debug YES
  31: */
  32: 
  33: #ifndef debug
  34: #define ASSERT(p)
  35: #endif
  36: 
  37: #ifdef debug
  38: #define ASSERT(p) if(!(p))botch("p");else
  39: 
  40: botch(s) char *s;
  41: {
  42:     fatal(F_ERSYS,s);
  43: }
  44: #endif
  45: 
  46: struct store { struct store *ptr; };
  47: 
  48: struct store allocs[] = {   /*initial arena*/
  49:     setbusy(&allocs[1].ptr),
  50:     setbusy(&allocs[0].ptr)
  51: };
  52: struct store *allocp = &allocs[1];  /*search ptr*/
  53: struct store *alloct = &allocs[1];  /*arena top*/
  54: struct store *allocx = 0;       /*for benefit of realloc*/
  55: struct store *sbrk();
  56: 
  57: struct store *
  58: malloc(nbytes)
  59: unsigned nbytes;
  60: {
  61:     struct store *p, *q;
  62:     register nw;
  63:     static temp;    /*coroutines assume no auto*/
  64: 
  65: #ifdef verbose
  66:     printf("malloc(%d) ",nbytes);
  67: #endif
  68:     nw = (nbytes+2*WORD-1)/WORD;
  69:     ASSERT(allocp>allocs && allocp<=alloct);
  70:     for(p=allocp; ; ) {
  71:         for(temp=0; ; ) {
  72:             if(!testbusy(p->ptr)) {
  73:                 while(!testbusy((q=p->ptr)->ptr)) {
  74:                     ASSERT(q>p&&q<alloct);
  75:                     p->ptr = q->ptr;
  76:                 }
  77:                 if(q>=p+nw && p+nw>=p)
  78:                     goto found;
  79:             }
  80:             q = p;
  81:             p = clearbusy(p->ptr);
  82:             if(p>q)
  83:                 ASSERT(p<=alloct);
  84:             else if(q!=alloct || p!=allocs) {
  85:                 fatal(F_ERSYS,"dballoc");
  86:             } else if(++temp>1)
  87:                 break;
  88:         }
  89:         temp = (nw+BLOCK/WORD)&~(BLOCK/WORD-1);
  90:         q = sbrk(temp*WORD); /*SYSDEP*/
  91:         if((int)q == -1)
  92:             return(NULL);
  93:         ASSERT(q>alloct);
  94:         alloct->ptr = q;
  95:         if(q!=alloct+1)
  96:             alloct->ptr = setbusy(alloct->ptr);
  97:         alloct = q->ptr = q+temp-1;
  98:         alloct->ptr = setbusy(allocs);
  99:     }
 100: found:
 101:     allocp = p + nw;
 102:     ASSERT(allocp<=alloct);
 103:     if(q>allocp) {
 104:         allocx = allocp->ptr;
 105:         allocp->ptr = p->ptr;
 106:     }
 107:     p->ptr = setbusy(allocp);
 108: #ifdef verbose
 109:     printf("= %o\n",p+1);
 110: #endif
 111:     return(p+1);
 112: }
 113: 
 114: /*
 115:  *	freeing strategy tuned for LIFO allocation
 116:  */
 117: free(p)
 118: struct store *p;
 119: {
 120:     struct store *savep=p;
 121: #ifdef verbose
 122:     printf("free(%o)\n",p);
 123: #endif
 124:     ASSERT(p>clearbusy(allocs[1].ptr)&&p<=alloct);
 125:     allocp = --p;
 126:     ASSERT(testbusy(p->ptr));
 127:     p->ptr = clearbusy(p->ptr);
 128:     ASSERT(p->ptr > allocp && p->ptr <= alloct);
 129: }
 130: 
 131: char *calloc(nbytes,count)
 132: {   char *c;
 133:     c=(char *)malloc(nbytes*count);
 134:     return(c);
 135: }
 136: 
 137: struct store *
 138: realloc(p, nbytes)
 139: register struct store *p;
 140: unsigned nbytes;
 141: {
 142:     register struct store *q;
 143:     struct store *s, *t;
 144:     register unsigned nw;
 145:     unsigned onw;
 146: 
 147:     onw = p[-1].ptr - p;
 148:     q = malloc(nbytes);
 149:     if(q==NULL || q==p)
 150:         return(q);
 151:     s = p;
 152:     t = q;
 153:     nw = (nbytes+WORD-1)/WORD;
 154:     if(nw<onw)
 155:         onw = nw;
 156:     while(onw--!=0)
 157:         (t++)->ptr = (s++)->ptr;
 158:     if(q<p && q+nw>=p)
 159:         (q+(q+nw-p))->ptr = allocx;
 160:     return(q);
 161: }

Defined functions

Defined variables

Defined struct's

Defined macros