/* CMALLOC ===================== MULTI HEAP MALLOC ========================== 
 * 
 *  Copyright (c) 1995
 *  Norman D. Culver dba Oxbow Software
 *  1323 S.E. 17th Street #662
 *  Ft. Lauderdale, FL 33316
 *  (305) 527-1663 Voice
 *  (305) 760-7584 Fax
 *  (305) 760-4679 Data
 *  ndc@fhd486.harvard.edu
 *  norman.culver@channel1.com
 *  All rights reserved.
 *
 * Redistribution and use in source and binary forms are permitted
 * provided that: (1) source distributions retain this entire copyright
 * notice and comment, and (2) distributions including binaries display
 * the following acknowledgement:  ``This product includes software
 * developed by Norman D. Culver dba Oxbow Software''
 * in the documentation or other materials provided with the distribution
 * and in all advertising materials mentioning features or use of this
 * software.
 * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR
 * IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED
 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.

	
	This implementation of malloc has some unique features.

	  1. Multiple heaps (categories) are very convenient because
	     the programmer can free an entire category of allocations
	     instead of ensuring that each malloc is paired with a free.
	  2. It is implemented with skip lists.
	  3. Nevertheless it competes favorably with BSD (buddy block) mallocs 
	  	 for speed and total space consumed.
	  4. If 'USEDLIST' is defined == 1, then allocated memory is never
	     touched. In a demand paging situation this method is ENORMOUSLY
	     faster than conventional mallocs which store bookkeeping info
	     in the allocated area and thus can/will cause thrashing when
	     space is allocated or freed.
	  5. With some minor modifications this implementation would make
	     a respectable disk allocator.
	  6. Individual categories can be set to 'guarded' mode in which
	     case guard words are stored at the front and back of each
	     allocation, the guard words are tested when the space is
	     freed or reallocated. If 'USEDLIST' == 1, then the function
	     Ccatcheck(int category, void *startaddr) will walk the heap
	     forward from 'startaddr' and return a bad address or 0.
*/
	
extern void *sbrk(unsigned);
extern void bzero(void*,unsigned);
extern void memmove(void*,void*,unsigned);
extern int printf(const char *fmt, ...);
extern int vprintf();
extern void abort(void);
extern void exit(int);

static void *do_sbrk(unsigned amount);
static void print_freenodes(int);

/* User API */
static void *Cmalloc(int category, unsigned amount);
static void *Ccalloc(int category, unsigned nelems, unsigned elemsize);
static void *Crealloc(int category, void* buf, unsigned newsize);
static void Cfree(int category, void* buf);
static void Cfreecat(int category);
static int Cmemrange(int category, unsigned* minp, unsigned* maxp);
static int Cusedrange(int category, unsigned* minp, unsigned* maxp);
static void Ctotrange(unsigned* minp,unsigned* maxp);
static int Cnewcat(void);
static void *Ccatcheck(int category, void *start);
static void Cguard(int category);
/* END: User API */

#define DEBUG 0
#define DEBUG_STATISTICS 0
#define DEBUG_USEDNODES 0
#define DEBUG_SPARES 0

#define USEDLIST 1	/* adds 13 bytes of nodespace per allocation */
#define ALIGNMENT (sizeof(int))
#define MAXLEVEL (15)
#define ROUNDING(a) ((ALIGNMENT-((a)&(ALIGNMENT-1)))&(ALIGNMENT-1))
#define ALLOCSIZE (4096)
#define GUARDWORD (0xa7b3a7b3)
#define THEWELL do_sbrk
#define PRINTF printf
#define VPRINTF vprintf
#define PERROR prerror

#if USEDLIST
#define NUMTYPES 3
#define SIZE 0
#define FREE 1
#define USED 2
#else
#define NUMTYPES 2
#define SIZE 0
#define FREE 1
#endif

#define SKIPVARS NodeP update[MAXLEVEL+1];NodeP node,prev;int level

#define DELETENODE(TYPE) \
{for(level=0;level<=bp->TYPE##level; level++)\
{if(update[level]->fptr[level] == node)\
update[level]->fptr[level] = node->fptr[level];else break;}\
while(bp->TYPE##level>0 && bp->TYPE##header->fptr[bp->TYPE##level]==_NIL)\
bp->TYPE##level--;free_node(bp,node,TYPE);}

#define INSERT() \
{while(level >= 0){\
node->fptr[level] = update[level]->fptr[level];\
update[level]->fptr[level] = node;level--;}}

#define SETLEVEL(TYPE) \
{level = getlevel(bp, bp->TYPE##level);\
while(bp->TYPE##level < level)update[++bp->TYPE##level]=bp->TYPE##header;}

#define FINDKEY(TYPE, KEYVAL)\
{node = bp->TYPE##header;\
for(level = bp->TYPE##level; level >= 0; level--){\
while(node->fptr[level]->key < KEYVAL)\
node = node->fptr[level];\
update[level] = node;}prev=node;node=node->fptr[0];}

#define DETACH(SN)\
{SN->bptr->fptr=SN->fptr;if(SN->fptr)SN->fptr->bptr=SN->bptr;}

#define UNLINK(SN, N)\
{if(!sp->fptr&&sp->bptr->bptr<=(AddrP)(MAXLEVEL+1))dsize[N]=sp->size;\
DETACH(SN);free_addr(bp,SN);}

#if USEDLIST
#define CHECKGUARDS(MSG)\
{if(bp->guarded){\
unsigned *p2;\
p2 = (void*)((char*)address+cursize-ALIGNMENT);\
if(*address != (unsigned)GUARDWORD)\
PERROR(#MSG ": heap(%d) corrupted at 0x%x\n", bp->bincat, addr);\
if(*p2 != ~((unsigned)GUARDWORD))\
PERROR(#MSG ": heap(%d) corrupted by 0x%x\n", bp->bincat, addr);}}
#else
#define CHECKGUARDS(MSG)\
{if(bp->guarded){\
unsigned *p2;\
address = (void*)((char*)address-ALIGNMENT);\
p2 = (void*)((char*)address+cursize-ALIGNMENT);\
if(*address != (unsigned)GUARDWORD)\
PERROR(#MSG ": heap(%d) corrupted at 0x%x\n", bp->bincat, addr);\
if(*p2 != ~((unsigned)GUARDWORD))\
PERROR(#MSG ": heap(%d) corrupted by 0x%x\n", bp->bincat, addr);}}
#endif

struct _catlocs {
	void *addr;
	struct _catlocs *fptr;
};

typedef struct _node
{
	unsigned key;
	unsigned value;
	unsigned levels;	/* must always be after value */
	struct _node *fptr[1];
} Node, *NodeP;

typedef struct _addr
{
	struct _addr *fptr;
	struct _addr *bptr;
	NodeP maddr;
	unsigned size;
} *AddrP;

struct _bins {
	unsigned bits;
	unsigned nbits;
	NodeP SIZEheader;
	int SIZElevel;
	NodeP FREEheader;
	int FREElevel; 
#if USEDLIST
	NodeP USEDheader;
	int USEDlevel;
#endif
	unsigned bincat;
	unsigned maxloc;
	unsigned minloc;
	struct _catlocs *catlocs;
	struct _bins *fptr;
	NodeP freenodes[NUMTYPES][MAXLEVEL+2];
	struct _addr *freeaddrlocs;
	char *chunkbase[NUMTYPES];
	int chunksize[NUMTYPES];
	int guarded;
	int addrbump;
	int overhead;
} zbp;

static struct _bins *hmap[1009];
static struct _node _nil = {0xffffffff,0,0,0};
static struct _node *_NIL = &_nil;
static unsigned maxloc;
static unsigned minloc;
static struct _bins *freebinlocs;
struct _catlocs *freecatlocs;
static char *binbase;
static int binsize;
static int chunksizes[] = {ALLOCSIZE,3*ALLOCSIZE,2*ALLOCSIZE};

#if DEBUG_STATISTICS
static unsigned histnodes[MAXLEVEL+1];
static unsigned nodetypes[NUMTYPES];
#endif

#include "lrandom.c"

static void
prerror(char *fmt, ...)
{
	VPRINTF(fmt, (char *)(((int *)(&fmt))+1));
	exit(0);
}
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.overhead);
			bp->chunksize[type] = chunksizes[type]-zbp.overhead;
			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_node(struct _bins *bp, int levels, int type)
{
int size;
NodeP p;

#if DEBUG_STATISTICS
	nodetypes[type]++;
#endif
	if((p=bp->freenodes[type][levels]))
	{
#if DEBUG_STATISTICS
		histnodes[levels]--;
#endif
		bp->freenodes[type][levels] = p->fptr[0];
		p->value = 0;
		return p;
	}
 	size = sizeof(struct _node) + levels * sizeof(void*);
	p = new_chunk(bp, size, type);
	p->levels = levels;
	p->value = 0;
	return p;
}
static void
free_node(struct _bins *bp, NodeP p, int type)
{
	p->fptr[0] = bp->freenodes[type][p->levels];
	bp->freenodes[type][p->levels] = p;
#if DEBUG_STATISTICS
	nodetypes[type]--;
	histnodes[p->levels]++;
#endif
}
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), FREE);
}
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
getlevel (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 > MAXLEVEL) ? MAXLEVEL : level;
}

static void
init_bins(struct _bins *bp, unsigned 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->SIZEheader = new_node(bp, MAXLEVEL+1, SIZE);
	bp->FREEheader = new_node(bp, MAXLEVEL+1, FREE);
#if USEDLIST
	bp->USEDheader = new_node(bp, MAXLEVEL+1, USED);
#else
	bp->addrbump = 1;
	bp->overhead = ALIGNMENT;
#endif
	for(i = 0; i <= MAXLEVEL; ++i)
	{
		bp->SIZEheader->fptr[i] = _NIL;
		bp->FREEheader->fptr[i] = _NIL;
#if USEDLIST
		bp->USEDheader->fptr[i] = _NIL;
#endif
	}
}

static struct _bins*
getcat(unsigned 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(unsigned category)
{
struct _bins *bp;

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

	if((bp = new_bins()))
	{
		init_bins(bp, category);
		return bp;
	}
	return 0;
}
static void *
do_sbrk(unsigned amount)
{
void *address;

	address = sbrk(amount);
	if(address == (void*)-1)
	{
		PERROR("cmalloc: system out of memory\n");
	}
	return address;
}
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.overhead)
			desired -= zbp.overhead;
		
		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(SIZE, 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(SIZE)
		node = new_node(bp, level, SIZE);
		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(FREE, (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(FREE);
		}
		/* 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(FREE)
		node = new_node(bp, level, FREE);
		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(SIZE, dsize[0])
		if(node->value == 0)
		  DELETENODE(SIZE)
	}
	if(dsize[1])
	{
		FINDKEY(SIZE, dsize[1])
		if(node->value == 0)
		  DELETENODE(SIZE)
	}
}
static void* 
Cmalloc(int category, unsigned size)
{
SKIPVARS;
NodeP fnode;
unsigned remainder;
unsigned *address;
struct _bins *bp;

	if(!(bp = getcat(category)))
	  if(!(bp = initcat(category)))
		  return 0;

	if(size == 0)
		size = ALIGNMENT;
	else
		size += ROUNDING(size);
	size += bp->guarded;

#if USEDLIST == 0
	size += ALIGNMENT;
#endif

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

		if(!sp && node == fnode)
		{
		NodeP q;
			q = node->fptr[0];
			DELETENODE(SIZE)
			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(SIZE, size)
			DELETENODE(SIZE)
		}

		if(remainder == 0)
		{/* no remaining space,the node in freelist is exhausted, delete it */
			FINDKEY(FREE, sp->maddr->key)
			DELETENODE(FREE)
			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(bp->guarded)
	{
	  *address = (unsigned)GUARDWORD;
	  *((unsigned*)(((char*)address)+size-ALIGNMENT)) = ~((unsigned)GUARDWORD);
#if USEDLIST == 0
	  ++address;
#endif
	}
#if USEDLIST
	FINDKEY(USED, (unsigned)address)
	if(node->key == (unsigned)address) {
	  PERROR("Cmalloc: bookkeeping nodes are corrupted at:0x%x\n", address);
	}
	SETLEVEL(USED)
	node = new_node(bp, level, USED);
	node->key = (unsigned)address;
	node->value = size;
	INSERT()	
#else
	*address = size | (ALIGNMENT-1);
#endif
	return address+bp->addrbump;
}
static 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;
};
static void
Cfree(int category, void* addr)
{
unsigned cursize;
unsigned *address;
struct _bins *bp;

#if USEDLIST
SKIPVARS;
#endif

	if(addr)
	{
		if(!(bp = getcat(category)))
			PERROR("Cfree: non-existant category:%d at:0x%x\n",category,addr);

#if USEDLIST
		address = (void*)(((char*)addr)-(bp->guarded/2));
		FINDKEY(USED, (unsigned)address)
		if(node->key != (unsigned)address)
		  PERROR("Cfree: bogus address=0x%x\n", addr);

		cursize = node->value;
		CHECKGUARDS(Cfree)
		DELETENODE(USED)
#else
		address = (void*)(((char*)addr)-ALIGNMENT);
		if((unsigned)address & (ALIGNMENT-1))
		  PERROR("Cfree: bogus address=0x%x\n", addr);

		cursize = *address;
		if((cursize & (ALIGNMENT-1)) != (ALIGNMENT-1))
		  PERROR("Cfree: heap(%d) corrupted at 0x%x\n", bp->bincat, addr);

		cursize &= ~(ALIGNMENT-1);
		*address = cursize;
		CHECKGUARDS(Cfree)
#endif
		addto_freelist(bp, address, cursize);
	}
	else PERROR("Cfree: null pointer in category %d\n", category);
}
static void* 
Crealloc(int category, void* addr, unsigned newsize)
{
SKIPVARS;
unsigned cursize;
unsigned *address;
unsigned *sizptr;
struct _bins *bp;

#if USEDLIST
NodeP onode;
#endif

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

		if(newsize == 0)
			newsize = ALIGNMENT;
		else
			newsize += ROUNDING(newsize);
		newsize += bp->guarded;

#if USEDLIST
		address = (void*)(((char*)addr)-(bp->guarded/2));
		FINDKEY(USED, (unsigned)address)
		if(node->key != (unsigned)address)
		  PERROR("Crealloc: bogus address=0x%x\n", addr);

		cursize = node->value;
		node->value = newsize;
		onode = node;
#else
		newsize += ALIGNMENT;
		if((unsigned)addr & (ALIGNMENT-1))
		  PERROR("Crealloc: bogus address=0x%x\n", addr);

		address = (void*)(((char*)addr)-ALIGNMENT);
		cursize = *address;
		if((cursize & (ALIGNMENT-1)) != (ALIGNMENT-1))
		  PERROR("Crealloc: heap(%d) corrupted at 0x%x\n",
		  	bp->bincat, addr);

		cursize &= ~(ALIGNMENT-1);
		sizptr = address;
#endif
		CHECKGUARDS(Crealloc)

		if(newsize == cursize)
			return addr;
		if(newsize > cursize)
		{/* check if block can be extended */
		void *taddr = ((char*)address) + cursize;
		unsigned extendsize = newsize-cursize;

			/* check freelist for an available block at the right address */
			FINDKEY(FREE, (unsigned)taddr)
			if(node->key == (unsigned)taddr)
			{
			AddrP sp = (AddrP)node->value;
				if(sp->size >= extendsize)
				{/* BLOCK CAN BE EXTENDED INTERNALLY */
					node->key += extendsize;
					sp->size -= extendsize;
					DETACH(sp)
					if(sp->size == 0)
					{/* the extension block is used up, delete this node */
						free_addr(bp, sp);
						DELETENODE(FREE)
					}
					else
					{/* shift the remainder in the sizelist */
						addto_sizelist(bp, sp);
					}
					/* SUCCESS */
					if(bp->guarded)
					{
						*((unsigned*)(((char*)address)+newsize-ALIGNMENT))
							= ~((unsigned)GUARDWORD);
					}
#if USEDLIST == 0
					*sizptr = newsize | (ALIGNMENT-1);
#endif
					return addr;
				}
			}
			/* HERE WE COULD CHECK OTHER SOURCES OF SPACE */

			/* can't extend block, malloc some new space */
			if((taddr = Cmalloc(category,newsize-bp->overhead)))
			{
				memmove(taddr,addr,cursize-bp->overhead);
#if USEDLIST
				onode->value = cursize;
#endif
				Cfree(category, addr);
			}
			/* SUCCESS */
			return taddr;
		}
		else
		{/* shrink block */
			if(bp->guarded)
			{
				*((unsigned*)(((char*)address)+newsize-ALIGNMENT))
					= ~((unsigned)GUARDWORD);
			}
			addto_freelist(bp, ((char*)address)+newsize, cursize-newsize); 

#if USEDLIST == 0
			*sizptr = newsize | (ALIGNMENT-1);
#endif
			return addr;
		}
  	}
}
static void
Cfreecat(int category)
{
struct _bins *bp;

	if(category == 0)
		return;

	if((bp = getcat(category)))
	{
	struct _catlocs *cl = bp->catlocs;
	struct _bins *hbp;
	struct _bins *prev;

		while(cl)
		{/* Space allocated to the category is moved to category 0 */
		void *ql = cl->fptr;

			Cfree(0, cl->addr);
			free_catloc(cl);
			cl = ql;
		}
		/* space for the _bins struct is placed on a free list */
		hbp = hmap[category % 1009];
		prev = 0;
		while(hbp)
		{
			if(hbp->bincat == category)
			{
				if(prev == 0)
					hmap[category % 1009] = hbp->fptr;
				else
					prev->fptr = hbp->fptr;
				free_bins(hbp);
				return;
			}
			prev = hbp;
			hbp = hbp->fptr;
		}
	}
}
static int
Cmemrange(int category, unsigned *min, unsigned *max)
{
struct _bins *bp;

	if((bp = getcat(category)))
	{
		*min = bp->minloc;
		*max = bp->maxloc;
		return 1;
	}
	return 0;
}
static int
Cusedrange(int category, unsigned *min, unsigned *max)
{
#if USEDLIST
struct _bins *bp;
NodeP node;
int level;

	if((bp = getcat(category)))
	{
		node = bp->USEDheader;
		*min = node->fptr[0]->key;
		for(level = bp->USEDlevel; level >= 0; level--)
		  while(node->fptr[level]->key < 0xffffffff)
			node = node->fptr[level];
		*max = node->key;
		return 1;
	}
#endif
	return 0;
}
static void
Ctotrange(unsigned *min, unsigned *max)
{
	*min = minloc;
	*max = maxloc;
}
static int
Cnewcat(void)
{
static int cat;
	return ++cat;
}
static void
Cguard(int category)
{
struct _bins *bp;

	if(!(bp = getcat(category)))
	  if(!(bp = initcat(category)))
		  return;

	if(!bp->guarded)
	{
		bp->guarded = 2*ALIGNMENT;
		bp->addrbump = 1;
		bp->overhead += 2*ALIGNMENT;
	}
}
static void*
Ccatcheck(int category, void *start)
{
#if USEDLIST
struct _bins *bp;
NodeP node,prev;
unsigned *p1,*p2;
	if((bp = getcat(category)))
	{
		if(bp->guarded)
		{
			prev = 0;
			node = bp->USEDheader;
			while((node = node->fptr[0]) != (NodeP)0xffffffff)
			{
				if((void*)node->key > start)
				{
					p1 = (unsigned*)node->key;
					p2 = (void*)((char*)p1+node->value+ALIGNMENT);
					if(*p1 != (unsigned)GUARDWORD)
					{
						if(prev)
							return (char*)prev->key+ALIGNMENT;
						else
							return (void*)1;
					}
					if(*p2 != ~((unsigned)GUARDWORD))
						return (char*)node->key+ALIGNMENT;
				}
				prev = node;
			}
		}
	}
#endif
	return 0;
}
#if DEBUG
long clock();
long start, end, diff;
void *malloc();
void *realloc();
void free();
#define CLOCKS_PER_SECOND 1000000L
#define ITERATIONS 0x10000
#define MAXALLOC 0x1ff

#define PRINT_TIME(string)\
diff = end - start;\
diff /= CLOCKS_PER_SECOND/10;\
if(diff == 0) diff = 1;\
printf(string " = %ld\n", (i*10) / diff);print_freenodes(1);

static void
print_freenodes(int category)
{
int i;
NodeP node;
AddrP ap;
struct _bins *bp = getcat(category);

#if DEBUG_STATISTICS
	printf("SIZENODES=%d\n", nodetypes[0]);
	node = bp->SIZEheader;
	while((node = node->fptr[0]))
	{
		printf("Size:%d\n", node->key);
		ap = (void*)node->value;
		while(ap)
		{
			printf("	%x	size=%d\n", ap->maddr->key, ap->size);
			ap = ap->fptr;
		}
	}
	printf("FREENODES=%d\n", nodetypes[1]);
	node = bp->FREEheader;
	while((node = node->fptr[0]))
	{
	int size;
		if((ap = (void*)node->value))
			size = ap->size;
		else size=-1;

		printf("Addr:%x	size=%d=0x%x End:%x\n",
			node->key, size, size, node->key+size);
	}
#if DEBUG_USEDNODES
	printf("USEDNODES=%d\n", nodetypes[2]);
	node = bp->USEDheader;
	while((node = node->fptr[0]))
	{
		printf("Addr:0x%x	Size:%d\n", node->key, node->value);
	}
#endif
#if DEBUG_SPARES
	printf("SPARES\n");
	for(i = 0; i <= MAXLEVEL; ++i)
		printf("%d	%d\n", i, histnodes[i]);
#endif
#endif
}
int
main(int argc, char **argv)
{
int i;
void *buf;
void *addrs[ITERATIONS];
unsigned random[ITERATIONS];
int cm = 0;

  if(argc > 1)
	cm =1;

  for(i = 0; i < ITERATIONS; ++i)
  {
	random[i] = lrandom();
	addrs[i] = 0;
  }
  if(cm)
  {

	start = clock();
	for(i = 0; i < ITERATIONS; ++i)
		addrs[i] = Cmalloc(1,random[i] & MAXALLOC);
	end = clock();
	PRINT_TIME("CMALLOC PER SEC")

	start = clock();
	/* Free the addresses in random order */
	for(i = 0; i < ITERATIONS; ++i)
	{
	int j = random[i] & (ITERATIONS-1);
		if(addrs[j])
		{
			Cfree(1,addrs[j]);
			addrs[j] = 0;
		}
	}
	/* Clean up any missed elements */
	for(i = 0; i < ITERATIONS; ++i)
	{
		if(addrs[i])
			Cfree(1,addrs[i]);
	}
	end = clock();
	PRINT_TIME("CFREE PER SEC")

	start = clock();
	for(i = 0; i < ITERATIONS; ++i)
	{
	int j = random[i] & (ITERATIONS-1);
		addrs[i] = Cmalloc(1,j & MAXALLOC);
		if(j < i && addrs[j])
		{
			Cfree(1,addrs[j]);
			addrs[j] = 0;
		}
	}
	end = clock();
	PRINT_TIME("C_COMBO PER SEC");

	/* Cleanup */
	for(i = 0; i < ITERATIONS; ++i)
		if(addrs[i]) Cfree(1,addrs[i]);

	start = clock();
	for(i = 0; i < ITERATIONS/2; ++i)
	{
	int j = random[i] & ((ITERATIONS/2)-1);

		addrs[i] = Cmalloc(1,random[i] & MAXALLOC);
		*((unsigned*)addrs[i]) = random[i];

		if(j < i && addrs[j])
		{
			if(*((unsigned*)addrs[j]) != random[j])
			  printf("Cmalloc: fail i=%d j=%d addr=0x%x des=%x got=%x size=%d\n",
				i, j, addrs[j], random[j], *((unsigned*)addrs[j]), 
				random[j] & MAXALLOC);

			addrs[j] = Crealloc(1,addrs[j], random[i] & MAXALLOC);
			if(*((unsigned*)addrs[j]) != random[j])
			  printf("Crealloc: fail i=%d j=%d addr=0x%x des=%x got=%x nsize=%d\n",
				i, j, addrs[j], random[j], *((unsigned*)addrs[j]), 
				random[i] & MAXALLOC);
		}
	}
	end = clock();
	PRINT_TIME("C_REALLOC PER SEC")

	Cfreecat(1);
  } else {

	start = clock();
	for(i = 0; i < ITERATIONS; ++i)
		addrs[i] = malloc(random[i] & MAXALLOC);
	end = clock();
	PRINT_TIME("MALLOC PER SEC")

	start = clock();
	for(i = 0; i < ITERATIONS; ++i)
	{
	int j = random[i] & (ITERATIONS-1);
		if(addrs[j])
		{
			free(addrs[j]);
			addrs[j] = 0;
		}
	}
	/* Clean up any missed elements */
	for(i = 0; i < ITERATIONS; ++i)
	{
		if(addrs[i])
			free(addrs[i]);
	}
	end = clock();
	PRINT_TIME("FREE PER SEC")

	start = clock();
	for(i = 0; i < ITERATIONS; ++i)
	{
	int j = random[i] & (ITERATIONS-1);
		addrs[i] = malloc(j & MAXALLOC);
		if(j < i && addrs[j])
		{
			free(addrs[j]);
			addrs[j] = 0;
		}
	}
	end = clock();
	PRINT_TIME("COMBO PER SEC");

	/* Cleanup */
	for(i = 0; i < ITERATIONS; ++i)
		if(addrs[i]) free(addrs[i]);

	start = clock();
	for(i = 0; i < ITERATIONS/2; ++i)
	{
	int j = random[i] & ((ITERATIONS/2)-1);

		addrs[i] = malloc((random[i] & MAXALLOC)+4);
		*((unsigned*)addrs[i]) = random[i];

		if(j < i && addrs[j])
		{
			if(*((unsigned*)addrs[j]) != random[j])
			  printf("malloc: fail i=%d j=%d addr=0x%x des=%x got=%x size=%d\n",
				i, j, addrs[j], random[j], *((unsigned*)addrs[j]), 
				(random[j] & MAXALLOC)+4);

			addrs[j] = realloc(addrs[j], (random[i] & MAXALLOC)+4);
			if(*((unsigned*)addrs[j]) != random[j])
			  printf("realloc: fail i=%d j=%d addr=0x%x des=%x got=%x size=%d\n",
				i, j, addrs[j], random[j], *((unsigned*)addrs[j]), 
				(random[i] & MAXALLOC)+4);
		}
	}
	end = clock();
	PRINT_TIME("REALLOC PER SEC")
  }
}
#endif /* DEBUG */
