/* Copyright (c) 1979 Regents of the University of California */
static char sccsid
[] = "@(#)malloc.c 4.1 10/10/80";
* Patched up version of malloc to do an integrity check
* on each allocation or free.
#define ASSERT(p,t) if(!(p))return(t(TRASHED));else
* 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
* 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 WORD sizeof(union store)
#define BLOCK 1024 /* a multiple of WORD*/
#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
;
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*/
register union store
*p
, *q
;
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]);
nw
= (nbytes
+WORD
+WORD
-1)/WORD
;
ASSERT(allocp
>=allocs
&& allocp
<=alloct
,(char *));
ASSERT(allock(),(char *));
while(!testbusy((q
=p
->ptr
)->ptr
)) {
ASSERT(q
>p
&&q
<alloct
,(char *));
ASSERT(p
<=alloct
,(char *));
else if(q
!=alloct
|| p
!=allocs
) {
ASSERT(q
==alloct
&&p
==allocs
,(char *));
temp
= ((nw
+BLOCK
/WORD
)/(BLOCK
/WORD
))*(BLOCK
/WORD
);
q
= (union store
*)sbrk(0);
q
= (union store
*)sbrk(temp
*WORD
);
ASSERT(q
>alloct
,(char *));
alloct
->ptr
= setbusy(alloct
->ptr
);
alloct
= q
->ptr
= q
+temp
-1;
alloct
->ptr
= setbusy(allocs
);
ASSERT(allocp
<=alloct
,(char *));
p
->ptr
= setbusy(allocp
);
* freeing strategy tuned for LIFO allocation
register union store
*p
= (union store
*)ap
;
ASSERT(p
>clearbusy(allocs
[1].ptr
)&&p
<=alloct
,(long));
ASSERT(testbusy(p
->ptr
),(long));
p
->ptr
= clearbusy(p
->ptr
);
ASSERT(p
->ptr
> allocp
&& p
->ptr
<= alloct
,(long));
for(p
= &allocs
[0]; clearbusy(p
->ptr
) > p
; p
=clearbusy(p
->ptr
)) {
ASSERT(p
==alloct
,(long));