Research V7 development

[unix-history] / usr / src / libI77 / dballoc.c

#define debug YES
#ifndef debug
#define ASSERT(p)
#endif
#ifdef debug
#define ASSERT(p) if(!(p))botch("p");else
botch(s)
char *s;
{
       printf("assertion botched: %s\n",s);
       abort();
}
#endif
/*      C storage allocator
*      circular first-fit strategy
*      works with noncontiguous, but monotonically linked, arena
*      each block is preceded by a ptr to the (pointer of) 
*      the next following block
*      blocks are exact number of words long; BUSY
*      bit in ptr is 1 for busy, 0 for idle
*      gaps in arena are merely noted as busy blocks
*      last block of arena (pointed to by alloct) is empty and
*      has a pointer to first
*      idle blocks are coalesced during space search
*/
/*      all these defines must be powers of 2 */
#define WORD sizeof(struct store)
#define BLOCK 1024
#define BUSY 1
#define NULL 0
#define testbusy(p) ((int)(p)&BUSY)
#define setbusy(p) (struct store *)((int)(p)+BUSY)
#define clearbusy(p) (struct store *)((int)(p)&~BUSY)

struct store { struct store *ptr; };

struct store allocs[] = {       /*initial arena*/
       setbusy(&allocs[1].ptr),
       setbusy(&allocs[0].ptr)
};
struct store *allocp = &allocs[1];      /*search ptr*/
struct store *alloct = &allocs[1];      /*arena top*/
struct store *allocx = 0;               /*for benefit of realloc*/
struct store *sbrk();

struct store *
malloc(nbytes)
unsigned nbytes;
{
       struct store *p, *q;
       register nw;
       static temp;    /*coroutines assume no auto*/

#ifdef verbose
       printf("malloc(%d) ",nbytes);
#endif
       nw = (nbytes+2*WORD-1)/WORD;
       ASSERT(allocp>allocs && allocp<=alloct);
       for(p=allocp; ; ) {
               for(temp=0; ; ) {
                       if(!testbusy(p->ptr)) {
                               while(!testbusy((q=p->ptr)->ptr)) {
                                       ASSERT(q>p&&q<alloct);
                                       p->ptr = q->ptr;
                               }
                               if(q>=p+nw && p+nw>=p)
                                       goto found;
                       }
                       q = p;
                       p = clearbusy(p->ptr);
                       if(p>q)
                               ASSERT(p<=alloct);
                       else if(q!=alloct || p!=allocs) {
                               write(2,"corrupt arena\n",14);
#ifdef debug
                               abort();
#endif
                               exit(0175);
                       } else if(++temp>1)
                               break;
               }
               temp = (nw+BLOCK/WORD)&~(BLOCK/WORD-1);
               q = sbrk(temp*WORD); /*SYSDEP*/
               if((int)q == -1)
                       return(NULL);
               ASSERT(q>alloct);
               alloct->ptr = q;
               if(q!=alloct+1)
                       alloct->ptr = setbusy(alloct->ptr);
               alloct = q->ptr = q+temp-1;
               alloct->ptr = setbusy(allocs);
       }
found:
       allocp = p + nw;
       ASSERT(allocp<=alloct);
       if(q>allocp) {
               allocx = allocp->ptr;
               allocp->ptr = p->ptr;
       }
       p->ptr = setbusy(allocp);
#ifdef verbose
       printf("= %o\n",p+1);
#endif
       return(p+1);
}
/*      freeing strategy tuned for LIFO allocation
*/
free(p)
struct store *p;
{
       struct store *savep=p;
#ifdef verbose
       printf("free(%o)\n",p);
#endif
       ASSERT(p>clearbusy(allocs[1].ptr)&&p<=alloct);
       allocp = --p;
       ASSERT(testbusy(p->ptr));
       p->ptr = clearbusy(p->ptr);
       ASSERT(p->ptr > allocp && p->ptr <= alloct);
}
char *calloc(nbytes,count)
{       char *c;
       c=(char *)malloc(nbytes*count);
       return(c);
}
/*
ahist(s) char *s;
{       char **ap;
       printf("%s allocp %o alloct %o\n",s,allocp,alloct);
       for(ap= allocs;ap<alloct;ap= *ap&~BUSY)
               if(*ap&BUSY) printf("%o ",ap);
       printf("\n");
}
*/
struct store *
realloc(p, nbytes)
register struct store *p;
unsigned nbytes;
{
       register struct store *q;
       struct store *s, *t;
       register unsigned nw;
       unsigned onw;

       onw = p[-1].ptr - p;
       q = malloc(nbytes);
       if(q==NULL || q==p)
               return(q);
       s = p;
       t = q;
       nw = (nbytes+WORD-1)/WORD;
       if(nw<onw)
               onw = nw;
       while(onw--!=0)
               (t++)->ptr = (s++)->ptr;
       if(q<p && q+nw>=p)
               (q+(q+nw-p))->ptr = allocx;
       return(q);
}