* 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
* idle blocks are coalesced during space search
/* all these defines must be powers of 2 */
#define WORD sizeof(struct store)
#define testbusy(p) ((int)(p)&BUSY)
#define setbusy(p) (struct store *)((int)(p)+BUSY)
#define clearbusy(p) (struct store *)((int)(p)&~BUSY)
#define ASSERT(p) if(!(p))botch("p");else
struct store
{ struct store
*ptr
; };
struct store allocs
[] = { /*initial arena*/
struct store
*allocp
= &allocs
[1]; /*search ptr*/
struct store
*alloct
= &allocs
[1]; /*arena top*/
struct store
*allocx
= 0; /*for benefit of realloc*/
static temp
; /*coroutines assume no auto*/
printf("malloc(%d) ",nbytes
);
nw
= (nbytes
+2*WORD
-1)/WORD
;
ASSERT(allocp
>allocs
&& allocp
<=alloct
);
while(!testbusy((q
=p
->ptr
)->ptr
)) {
else if(q
!=alloct
|| p
!=allocs
) {
temp
= (nw
+BLOCK
/WORD
)&~(BLOCK
/WORD
-1);
q
= sbrk(temp
*WORD
); /*SYSDEP*/
alloct
->ptr
= setbusy(alloct
->ptr
);
alloct
= q
->ptr
= q
+temp
-1;
alloct
->ptr
= setbusy(allocs
);
p
->ptr
= setbusy(allocp
);
* freeing strategy tuned for LIFO allocation
ASSERT(p
>clearbusy(allocs
[1].ptr
)&&p
<=alloct
);
ASSERT(testbusy(p
->ptr
));
p
->ptr
= clearbusy(p
->ptr
);
ASSERT(p
->ptr
> allocp
&& p
->ptr
<= alloct
);
char *calloc(nbytes
,count
)
c
=(char *)malloc(nbytes
*count
);
register struct store
*p
;
register struct store
*q
;
nw
= (nbytes
+WORD
-1)/WORD
;
(q
+(q
+nw
-p
))->ptr
= allocx
;