123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212 |
- /*
- * (c) copyright 1983 by the Vrije Universiteit, Amsterdam, The Netherlands.
- *
- * This product is part of the Amsterdam Compiler Kit.
- *
- * Permission to use, sell, duplicate or disclose this software must be
- * obtained in writing. Requests for such permissions may be sent to
- *
- * Dr. Andrew S. Tanenbaum
- * Wiskundig Seminarium
- * Vrije Universiteit
- * Postbox 7161
- * 1007 MC Amsterdam
- * The Netherlands
- *
- */
- #include "ack.h"
- #ifdef DEBUG
- #define ASSERT(p) if(!(p))botch("p");else
- botch(s)
- char *s;
- {
- printf("malloc/free botched: %s\n",s);
- abort();
- }
- #else
- #define ASSERT(p)
- #endif
- #ifndef NORCSID
- static char rcs_id[] = "$Header$" ;
- #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)
- *t++ = *s++;
- if(q<p && q+nw>=p)
- (q+(q+nw-p))->ptr = allocx;
- return((char *)q);
- }
- #ifdef DEBUG
- allock()
- {
- #ifdef DEBUG
- 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
|