BSD 4 release

[unix-history] / usr / src / cmd / csh / alloc.c

static  char *sccsid = "@(#)alloc.c 4.1 10/9/80";

#include "sh.local.h"
#ifdef debug
#define ASSERT(p) if(!(p))botch("p");else
botch(s)
char *s;
{
       printf("assertion botched: %s\n",s);
       abort();
}
#else
#define ASSERT(p)
#endif

/*      avoid break bug */
#ifdef pdp11
#define GRANULE 64
#else
#define GRANULE 0
#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 
*      aligned to the data type requirements of ALIGN
*      pointers to blocks must have BUSY bit 0
*      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
*
*      a different implementation may need to redefine
*      ALIGN, NALIGN, BLOCK, BUSY, INT
*      where INT is integer type to which a pointer can be cast
*/
#define INT int
#define ALIGN int
#define NALIGN 1
#define WORD sizeof(union store)
#define BLOCK 1024      /* a multiple of WORD*/
#define BUSY 1
#define NULL 0
#define testbusy(p) ((INT)(p)&BUSY)
#define setbusy(p) (union store *)((INT)(p)|BUSY)
#define clearbusy(p) (union store *)((INT)(p)&~BUSY)

union store { union store *ptr;
             ALIGN dummy[NALIGN];
             int calloc;       /*calloc clears an array of integers*/
};

static  union store allocs[2];  /*initial arena*/
static  union store *allocp;    /*search ptr*/
static  union store *alloct;    /*arena top*/
static  union store *allocx;    /*for benefit of realloc*/
char    *sbrk();

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

       if(allocs[0].ptr==0) {  /*first time*/
               allocs[0].ptr = setbusy(&allocs[1]);
               allocs[1].ptr = setbusy(&allocs[0]);
               alloct = &allocs[1];
               allocp = &allocs[0];
       }
       nw = (nbytes+WORD+WORD-1)/WORD;
       ASSERT(allocp>=allocs && allocp<=alloct);
       ASSERT(allock());
       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) {
                               ASSERT(q==alloct&&p==allocs);
                               return(NULL);
                       } else if(++temp>1)
                               break;
               }
               temp = ((nw+BLOCK/WORD)/(BLOCK/WORD))*(BLOCK/WORD);
               q = (union store *)sbrk(0);
               if(q+temp+GRANULE < q) {
                       return(NULL);
               }
               q = (union store *)sbrk(temp*WORD);
               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);
       return((char *)(p+1));
}

/*      freeing strategy tuned for LIFO allocation
*/
free(ap)
register char *ap;
{
       register union store *p = (union store *)ap;

       ASSERT(p>clearbusy(allocs[1].ptr)&&p<=alloct);
       ASSERT(allock());
       allocp = --p;
/*      ASSERT(testbusy(p->ptr)); */
       p->ptr = clearbusy(p->ptr);
       ASSERT(p->ptr > allocp && p->ptr <= alloct);
}

/*      realloc(p, nbytes) reallocates a block obtained from malloc()
*      and freed since last call of malloc()
*      to have new size nbytes, and old content
*      returns new location, or 0 on failure
*/

char *
realloc(p, nbytes)
register union store *p;
unsigned nbytes;
{
       register union store *q;
       union store *s, *t;
       register unsigned nw;
       unsigned onw;

       if(testbusy(p[-1].ptr))
               free((char *)p);
       onw = p[-1].ptr - p;
       q = (union store *)malloc(nbytes);
       if(q==NULL || q==p)
               return((char *)q);
       s = p;
       t = q;
       nw = (nbytes+WORD-1)/WORD;
       if(nw<onw)
               onw = nw;
       while(onw--!=0)
#ifdef  V6
               copy(t++, s++, sizeof (*t));
#else
               *t++ = *s++;
#endif
       if(q<p && q+nw>=p)
               (q+(q+nw-p))->ptr = allocx;
       return((char *)q);
}

#ifdef debug
allock()
{
#ifdef longdebug
       register union store *p;
       int x;
       x = 0;
       for(p= &allocs[0]; clearbusy(p->ptr) > p; p=clearbusy(p->ptr)) {
               if(p==allocp)
                       x++;
       }
       ASSERT(p==alloct);
       return(x==1|p==allocp);
#else
       return(1);
#endif
}
#endif

#ifdef debug
showall(v)
       char **v;
{
       register union store *p, *q;
       int used = 0, free = 0, i;

       for (p = clearbusy(allocs[1].ptr); p != alloct; p = q) {
               q = clearbusy(p->ptr);
               if (v[1])
               printf("%6o %5d %s\n", p,
                   ((unsigned) q - (unsigned) p),
                   testbusy(p->ptr) ? "BUSY" : "FREE");
               i = ((unsigned) q - (unsigned) p);
               if (testbusy(p->ptr)) used += i; else free += i;
       }
       printf("%d used, %d free, %l end\n", used, free, clearbusy(alloct));
}
#endif