/* ======================== START OF CODE =========================== */
#if PRINT_RAWDATA == 1
static char
hexbyte(unsigned int c)
{
char x = c & 0xf;

	return x + ((x>9) ? 55 : 48);
}
static void
print_rawdata(void *rawdata, long size)
{
unsigned long vaddr = 0;
unsigned char *d = rawdata;
int i,j;
char addr[9];
char hex1[24];
char hex2[24];
char side1[9];
char side2[9];

	addr[8] = 0;
	hex1[23] = 0;
	hex2[23] = 0;
	side1[8] = 0;
	side2[8] = 0;
	while(size > 0)
	{
	unsigned long qaddr = vaddr;
		memset(addr, '0', 8);
		memset(hex1, ' ', 23);
		memset(hex2, ' ', 23);
		memset(side1, ' ', 8);
		memset(side2, ' ', 8);
		i = 7;
		while(qaddr)
		{
			addr[i--] = hexbyte(qaddr);
			qaddr >>= 4;
		}
		for(i=0,j=0; i < 8; ++i)
		{
			if(--size >= 0)
			{
			unsigned int c = *d++;
				if(isprint(c))
					side1[i] = c;
				else
					side1[i] = '.';
				hex1[j++] = hexbyte(c>>4);
				hex1[j++] = hexbyte(c);
					++j;
			}
			else break;
		}
		for(i=0,j=0; i < 8; ++i)
		{
			if(--size >= 0)
			{
			unsigned int c = *d++;
				if(isprint(c))
					side2[i] = c;					
				else
					side2[i] = '.';
				hex2[j++] = hexbyte(c>>4);
				hex2[j++] = hexbyte(c);
				++j;
			}
			else break;
		}
		VPRINTF("%s  %s%s%s  %s%s%s\n",addr,hex1," | ",hex2,side1,"|",side2);
		vaddr += 16;
	}
}
#endif

/*
 * Returns a really good 31-bit random number.
 */
static long
lrandom()
{
long i;
	
	*fptr += *rptr;
	i = (*fptr >> 1) & 0x7fffffffUL;
	if(++fptr > &randtbl[31])
	{
		fptr = &randtbl[1];
		++rptr;
	}
	else
	{
		if(++rptr > &randtbl[31])  
			rptr = &randtbl[1];
	}
	return( i );
}
#if !USING_FRAMEWORK
static void *
do_sbrk(unsigned amount)
{
void *address;

	address = sbrk(amount);	/* OR WHATEVER TO ACCESS THE OPERATING SYSTEM */
	if(address == (void*)-1)
	{
		PERROR(pName "\nsystem out of memory, requested %u bytes\n", amount);
	}
	return address;
}
#endif

static struct _catlocs *
new_catloc(void)
{
struct _catlocs *p;
	if((p=freecatlocs))
	{
		freecatlocs = p->fptr;
		return p;
	}
	if(binsize < sizeof(struct _catlocs))
	{
		binbase = THEWELL(4096);
		binsize = 4096;
	}
	binsize -= sizeof(struct _catlocs);
	p = (void*)binbase;
	binbase += sizeof(struct _catlocs);
	return p;
}
static void
free_catloc(struct _catlocs *p)
{
	p->fptr = freecatlocs;
	freecatlocs = p;
}
static void *
new_chunk(struct _bins *bp, int size, int type)
{
char *p;
 	if(bp->chunksize[type] < size)
	{
		if(bp->bincat == 0) {
			bp->chunkbase[type] = THEWELL(chunksizes[type]);
			bp->chunksize[type] = chunksizes[type];
		}
		else {
		struct _catlocs *cl;
			bp->chunkbase[type] = Cmalloc(0,chunksizes[type]-zbp.guarded);
			bp->chunksize[type] = chunksizes[type]-zbp.guarded;
			cl = new_catloc();
			cl->addr = bp->chunkbase[type];
			cl->fptr = bp->catlocs;
			bp->catlocs = cl;
		}
	}
	bp->chunksize[type] -= size;
	p = bp->chunkbase[type];
	bp->chunkbase[type] += size;
	return p;
}
static void *
new_Mnode(struct _bins *bp, int levels, int type)
{
int size;
NodePM p;

	if((p=bp->freenodes[type][levels]))
	{
		bp->freenodes[type][levels] = p->fptr[0];
		p->value = 0;
		return p;
	}
 	size = sizeof(struct _nodeM) + levels * sizeof(void*);
	p = new_chunk(bp, size, type);
	p->levels = levels;
	p->value = 0;
	return p;	
}
static void
free_Mnode(struct _bins *bp, NodePM p, int type)
{
	p->fptr[0] = bp->freenodes[type][p->levels];
	bp->freenodes[type][p->levels] = p;
}
static struct _addr *
new_addr(struct _bins *bp)
{
struct _addr *p;
	if((p=bp->freeaddrlocs))
	{
		bp->freeaddrlocs = p->fptr;
		return p;
	}
	return new_chunk(bp, sizeof(struct _addr), FREEH);
}
static void
free_addr(struct _bins *bp, struct _addr *p)
{
	p->fptr = bp->freeaddrlocs;
	bp->freeaddrlocs = p;
}
static struct _bins *
new_bins(void)
{
struct _bins *p;
	if((p=freebinlocs))
	{
		freebinlocs = p->fptr;
		return p;
	}
 	if(binsize < sizeof(struct _bins))
	{
		binbase = THEWELL(4096);
		binsize = 4096;
	}
	binsize -= sizeof(struct _bins);
	p = (struct _bins*)binbase;
	binbase += sizeof(struct _bins);
	return p;
}
static void
free_bins(struct _bins *p)
{
	p->fptr = freebinlocs;
	freebinlocs = p;
}
static int
getMlevel (struct _bins *p, int binlevel)
{
int level = -1;
int bits = 0;

    while(bits == 0)
    {
		if (p->nbits == 0)
		{
		    p->bits = lrandom();
			p->nbits = 15;
		}
		bits = p->bits & 3;
		p->bits >>= 2;
		p->nbits--;

		if(++level > binlevel)
			break;
    }
    return (level > MAL_MAXLEVEL) ? MAL_MAXLEVEL : level;
}

static void
init_bins(struct _bins *bp, int category)
{
int i;
int binnum = category % 1009;

	bzero(bp, sizeof(struct _bins));
	bp->bincat = category;
	bp->minloc = 0xffffffff;
	bp->fptr = hmap[binnum];
	hmap[binnum] = bp;
	bp->SIZEHheader = new_Mnode(bp, MAL_MAXLEVEL+1, SIZEH);
	bp->FREEHheader = new_Mnode(bp, MAL_MAXLEVEL+1, FREEH);
	bp->USEDHheader = new_Mnode(bp, MAL_MAXLEVEL+1, USEDH);

	for(i = 0; i <= MAL_MAXLEVEL; ++i)
	{
		bp->SIZEHheader->fptr[i] = _NILLL;
		bp->FREEHheader->fptr[i] = _NILLL;
		bp->USEDHheader->fptr[i] = _NILLL;
	}
}

static struct _bins*
getcat(int category)
{
struct _bins *hbp;

	hbp = hmap[category % 1009];
	while(hbp)
	{
		if(hbp->bincat == category)
			return hbp;
		hbp = hbp->fptr;
	}
	return 0;
}
static struct _bins *
initcat(int category)
{
struct _bins *bp;

	if(category == 0)
	{
		bp = &zbp;
		if(zbp.SIZEHheader == 0)
			init_bins(bp, category);
		return bp;
	}
	/* do this to set zbp.guarded properly on startup */
	if(zbp.SIZEHheader == 0)
		initcat(0);

	if((bp = new_bins()))
	{
		init_bins(bp, category);
		return bp;
	}
	return 0;
}
static void *
getspace(struct _bins *bp, unsigned size, unsigned *remainder)
{
unsigned desired;
void *address;
  
	desired = ((size+ALLOCSIZE-1)/ALLOCSIZE)*ALLOCSIZE;
	if(bp->bincat == 0)
	{
		address = THEWELL(desired);
		*remainder = desired - size;
	}
	else
	{
	struct _catlocs *cl;

		if((desired-size) > zbp.guarded)
			desired -= zbp.guarded;
		
		address = Cmalloc(0, desired);
		*remainder = desired - size;

		/* save the gross allocations for the category */
		cl = new_catloc();
		cl->addr = address;
		cl->fptr = bp->catlocs;
		bp->catlocs = cl;
	}
	/* maintain address range info */
	if((unsigned)address < bp->minloc)
		bp->minloc = (unsigned)address;
	if(((unsigned)address + desired) > bp->maxloc)
		bp->maxloc = (unsigned)address + desired;
 	if(bp->minloc < minloc)
 		minloc = bp->minloc;
 	if(bp->maxloc > maxloc)
 		maxloc = bp->maxloc;
	return address;
}
static void
addto_sizelist(struct _bins *bp, AddrP ap)
{
SKIPVARS;

	/* INSERT IN SIZE LIST */
	FINDKEY(SIZEH, ap->size)

	if(node->key == ap->size)
	{/* size node exists */
		ap->fptr = (AddrP)node->value;
		ap->bptr = (AddrP)&node->value;
		if(ap->fptr) ap->fptr->bptr = ap;
		node->value = (unsigned)ap;
	}
	else
	{/* create new size node */
		SETLEVEL(SIZEH)
		node = new_Mnode(bp, level, SIZEH);
		node->key = ap->size;
		node->value = (unsigned)ap;
		ap->fptr = 0;
		ap->bptr = (AddrP)&node->value;
		INSERT()
	}
}
static void
addto_freelist(struct _bins *bp, void *addr, unsigned size)
{
SKIPVARS;
AddrP ap,sp;
unsigned dsize[2];

	/* GET NEW ADDR STRUCT */
	ap = new_addr(bp);
	ap->size = size;

	dsize[1] = dsize[0] = 0; /* sizenode deletion markers */

	/* CHECK FREE LIST */
	FINDKEY(FREEH, (unsigned)addr)

	/* CHECK FOR MERGE OR INSERT */
	if(prev->value && prev->key+((AddrP)prev->value)->size == (unsigned)addr)
	{/* merge with previous block */
		ap->size += ((AddrP)prev->value)->size;

		if(prev->key + ap->size == node->key)
		{/* merge with previous and next block */
			sp = (AddrP) node->value;;
			ap->size += sp->size;

			/* delete size struct for next block */
			UNLINK(sp, 0)

			/* delete next block */
			DELETENODE(FREEH);
		}
		/* delete size struct for prev block */
		sp = (AddrP)prev->value;
		UNLINK(sp, 1)

		/* set new address struct */
		prev->value = (unsigned)ap;
		ap->maddr = prev;
	}
	else if(node->value && (char*)addr + size == (void*)node->key)
	{/* merge with next block */
		sp = (AddrP) node->value;;
		node->key = (unsigned)addr;
		ap->size += sp->size;

		/* unlink size struct for next block */
		UNLINK(sp,0)

		/* set new address struct */
		node->value = (unsigned)ap;
		ap->maddr = node;
	}
	else
	{/* insert in free list */

		SETLEVEL(FREEH)
		node = new_Mnode(bp, level, FREEH);
		node->key = (unsigned)addr;
		node->value = (unsigned)ap;
		ap->maddr = node;
		INSERT()
	}
	addto_sizelist(bp, ap);

	/* Remove sizenodes eliminated by merge */
	if(dsize[0])
	{
		FINDKEY(SIZEH, dsize[0])
		if(node->value == 0)
		  DELETENODE(SIZEH)
	}
	if(dsize[1])
	{
		FINDKEY(SIZEH, dsize[1])
		if(node->value == 0)
		  DELETENODE(SIZEH)
	}
}

LOCAL void* 
Cmemalign(int category, unsigned alignment, unsigned req)
{
SKIPVARS;
NodePM fnode;
unsigned remainder;
unsigned *address;
struct _bins *bp;
unsigned mask, size;


	if(!(bp = getcat(category)))
	  if(!(bp = initcat(category)))
		return 0;
HEAPCHECK
	if(req == 0)
		req = ALIGNMENTM;
	else
		req += ROUNDINGM(req);
	size = req += bp->guarded;

	if(alignment)
	{
		alignment += ROUNDINGM(alignment);
		if(alignment > ALIGNMENTM)
		{
			mask = alignment -1;
			size = req + alignment + bp->guarded;
		}
		else
		{
			alignment = 0;
		}
	}

	/* check sizelist for candidate */
	FINDKEY(SIZEH, size)
	fnode = node;
trynext:
	if(node->key != 0xffffffff)
	{/* found an appropriately sized block */
	AddrP sp = (AddrP)node->value;

		if(!sp && node == fnode)
		{
		NodePM q;
			q = node->fptr[0];
			DELETENODE(SIZEH)
			node = q;
			goto trynext;
		}
		if(!sp)
		{/* no available space at this size */
			node = node->fptr[0];
			goto trynext;
		}

		/* extract some space from this block */
		remainder = node->key - size;
		address = (void*)sp->maddr->key;
		sp->maddr->key += size;
		DETACH(sp);

		if(node->value == 0)
		{/* no more blocks of this size, delete sizenode */
			if(node != fnode)
			  FINDKEY(SIZEH, size)
			DELETENODE(SIZEH)
		}

		if(remainder == 0)
		{/* no remaining space,the node in freelist is exhausted, delete it */
			FINDKEY(FREEH, sp->maddr->key)
			DELETENODE(FREEH)
			free_addr(bp, sp);
		}
		else
		{/* space remains in block, move it to new size loc */
			sp->size = remainder;
			addto_sizelist(bp, sp);
		}
	}
	else
	{
		address = getspace(bp, size, &remainder);
		if(remainder)
		  addto_freelist(bp, ((char*)address)+size, remainder);
	}
	if(alignment)
	{
	unsigned diff;
		if((diff = (unsigned)address & mask))
		{/* move address forward */
		char *naddress;
		unsigned lose;
			lose = alignment - diff;
			naddress = (char*)address + lose;
			addto_freelist(bp, address, lose);
			address = (unsigned*)naddress;
		}
	}
	if(bp->guarded)
	{
	  *address = FRNTGUARD;
	  *((unsigned*)(((char*)address)+req-ALIGNMENTM)) = BACKGUARD;

	}

	FINDKEY(USEDH, (unsigned)address)

	if(node->key == (unsigned)address) {
	  PERROR(pName ":ERROR:allocC:%d: bookkeeping nodes are corrupted at:0x%x\n",
	  	category, address);
	}
	SETLEVEL(USEDH)
	node = new_Mnode(bp, level, USEDH);
	node->key = (unsigned)address;
	node->value = req;
	INSERT()	

	return address+bp->addrbump;
}
LOCAL void*
Ccalloc(int category, unsigned cnt, unsigned elem_size)
{
unsigned size = cnt * elem_size;
void* buf;;

  if((buf = Cmalloc(category, size)))
	  bzero(buf, size);
  return buf;
};
LOCAL void
Cfree(int category, void* addr)
{
unsigned cursize;
unsigned *address;
struct _bins *bp;
SKIPVARS;
	if(addr)
	{
		if(!(bp = getcat(category))) {
			PERROR(pName ":ERROR:Cfree:%d: non-existant category at:0x%x\n",category,addr);
		}
HEAPCHECK
		address = (void*) ((unsigned*)addr - bp->addrbump);
		FINDKEY(USEDH, (unsigned)address)
		if(node->key != (unsigned)address) {
		  PERROR(pName ":ERROR:Cfree:%d: bogus address=0x%x\n", category, addr);
		}
		cursize = node->value;
		CHECKGUARDS(Cfree)
		DELETENODE(USEDH)

		addto_freelist(bp, address, cursize);
	}
	else PERROR(pName ":ERROR:Cfree:%d: null pointer\n", category);
}
LOCAL void* 
Crealloc(int category, void* addr, unsigned newsize)
{
SKIPVARS;
unsigned cursize;
unsigned *address;
struct _bins *bp;
NodePM onode;

	if(addr == 0) 
		return Cmalloc(category, newsize);
	else
	{
		if(!(bp = getcat(category))) {
		   PERROR(pName ":ERROR:reallocC:%d: non-existant category at:%x\n",category,addr);
		}
HEAPCHECK 
		if(newsi