Category : Recently Uploaded Files
Archive   : OXCC1430.ZIP
Filename : CMALLOC.C

/* 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
* [email protected]
* [email protected]
* 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 */