#define ASSERT(p) if(!(p))botch("p");else
printf("assertion botched: %s\n",s
);
* 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) ((int)(p)+BUSY)
#define clearbusy(p) ((int)(p)&~BUSY)
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
; /*for benefit of realloc*/
register struct store
*p
, *q
;
static temp
; /*coroutines assume no auto*/
nw
= (nbytes
+2*WORD
-1)/WORD
;
ASSERT(allocp
>allocs
&& allocp
<=alloct
);
while(!testbusy((q
=p
->ptr
)->ptr
)) {
else if(q
!=alloct
|| p
!=allocs
) {
write(2,"corrupt arena\n",14);
temp
= (nw
+BLOCK
/WORD
)&~(BLOCK
/WORD
-1);
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
register struct store
*p
;
ASSERT(p
>clearbusy(allocs
[1].ptr
)&&p
<=alloct
);
ASSERT(testbusy(p
->ptr
));
p
->ptr
= clearbusy(p
->ptr
);
ASSERT(p
->ptr
> allocp
&& p
->ptr
<= alloct
);
struct { unsigned tag
:4, vtype
:4;};
register struct store
*p
, *q
;
ASSERT(allocp
>allocs
&& allocp
<=alloct
);
printf("busy 0%o, tag %d, type %d, length %d\n",
clearbusy(p
->ptr
) - (int) p
- 2 );
else if(q
!=alloct
|| p
!=allocs
)
write(2,"corrupt arena\n",14);