oxccl.c

OXCC is a multipass, interpreting C compiler with several language extensions. It generates an Archi

		}
HEAPCHECK 
		if(newsize == 0)
			newsize = ALIGNMENTM;
		else
			newsize += ROUNDINGM(newsize);
		newsize += bp->guarded;

		address = (void*)(((char*)addr)-(bp->guarded/2));
		FINDKEY(USEDH, (unsigned)address)
		if(node->key != (unsigned)address) {
		  PERROR(pName ":ERROR:reallocC:%d: bogus address=0x%x\n", category, addr);
		}
		cursize = node->value;
		node->value = newsize;
		onode = node;

		CHECKGUARDS(reallocC)

		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(FREEH, (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(FREEH)
					}
					else
					{/* shift the remainder in the sizelist */
						addto_sizelist(bp, sp);
					}
					/* SUCCESS */
					if(bp->guarded)
					{
						*((unsigned*)(((char*)address)+newsize-ALIGNMENTM))
							= BACKGUARD;
					}
					return addr;
				}
			}
			/* HERE WE COULD CHECK OTHER SOURCES OF SPACE */

			/* can't extend block, malloc some new space */
			if((taddr = Cmalloc(category,newsize-bp->guarded)))
			{
				memmove(taddr,addr,cursize-bp->guarded);
				onode->value = cursize;
				Cfree(category, addr);
			}
			/* SUCCESS */
			return taddr;
		}
		else
		{/* shrink block */
			if(bp->guarded)
			{
				*((unsigned*)(((char*)address)+newsize-ALIGNMENTM))
					= BACKGUARD;
			}
			addto_freelist(bp, ((char*)address)+newsize, cursize-newsize); 
			return addr;
		}
  	}
}
LOCAL 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;
		}
	}
}
LOCAL 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;
}
LOCAL int
Cusedrange(int category, unsigned *min, unsigned *max)
{
struct _bins *bp;
NodePM node;
int level;

	if((bp = getcat(category)))
	{
		node = bp->USEDHheader;
		*min = node->fptr[0]->key;
		for(level = bp->USEDHlevel; level >= 0; level--)
		  while(node->fptr[level]->key < 0xffffffff)
			node = node->fptr[level];
		*max = node->key;
		return 1;
	}
	return 0;
}
LOCAL void
Ctotrange(unsigned *min, unsigned *max)
{
	*min = minloc;
	*max = maxloc;
}
LOCAL void
Cguard(int category)
{
struct _bins *bp;

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

	if(!bp->guarded)
	{
		bp->guarded = 2*ALIGNMENTM;
		bp->addrbump = 1;
	}
}
LOCAL void*
Cheapcheck(int category, void *start)
{
struct _bins *bp;
NodePM node,prev;
unsigned *p1,*p2;

	if((bp = getcat(category)))
	{
		if(bp->guarded)
		{
			prev = 0;
			node = bp->USEDHheader;
			while(		(node = node->fptr[0]) != (NodePM)0xffffffff
					&&	node->key != 0xffffffffUL)
			{
				if((void*)node->key > start)
				{
					p1 = (unsigned*)node->key;
					if(*p1 != FRNTGUARD)
					{
						if(prev)
							return (char*)prev->key+ALIGNMENTM;
						else
							return (void*)1;
					}
					p2 = (unsigned*)(((char*)p1)+node->value-ALIGNMENTM);
					if(*p2 != BACKGUARD)
						return (char*)node->key+ALIGNMENTM;
				}
				prev = node;
			}
		}
	}
	return 0;
}
LOCAL void* 
Cmalloc(int category, unsigned size)
{
	return Cmemalign(category, 0, size);
}

LOCAL void* 
Cvalloc(int category, unsigned bytes)
{
  return Cmemalign (category, PAGESIZE, bytes);
}
LOCAL unsigned
Cmallocsize(int category, void* addr)
{
struct _bins *bp;
SKIPVARS;

	if(addr && (bp = getcat(category)))
	{
	unsigned address = (unsigned)((unsigned*)addr - bp->addrbump);
		FINDKEY(USEDH, address)
		if(node->key == address)
			return node->value - bp->guarded;
	}
	return 0;
}

LOCAL int
Cnewcat()
{
static unsigned int cat = BASE_CATEGORY;
	return ++cat;
}


/* ====================== END MULTI-HEAP MALLOC ============================ */

/* ====================== SYMBOL TABLE HANDLERS ============================ */

typedef struct _key
{
	unsigned long k[2];
	unsigned long hv;
} KEY, *KEYP;

typedef struct _nodeS
{/* 40 bytes -- adjust size to suit application */
	unsigned long value[4];	/* 16 bytes */
	unsigned long key[2];	/* 8 bytes */
	struct _nodeS *fptr[4];	/* 16 bytes */
} NodeS, *NodePS;

typedef struct _pbuf
{/* symbol table object */
	int	nbins;			/* number of bins in dictionary */
	int lastbin;		/* for seq access */
	NodePS lastptr;		/* ditto */
	int category;		/* heap number */
	char *chunkbase;	/* node allocation base */
	int chunksize;		/* number of bytes available in current chunk */
	NodePS freelist;	/* list of freed nodes for allocation */
	int level;			/* sorted level */
	int bits;			/* sorted bits */
	int bitcnt;			/* sorted bitcnt */
	NodePS header;		/* sorted header */
	NodePS bins[0];		/* bins if hashed dictionary */
} *PbufP;

#define SYM_MAXLEVEL 12
#define TBL ((PbufP)tbl)
#define KEYEQ(a,b) ((a)[0] == (b)[0] && (a)[1] == (b)[1])
#define KEYLT(a,b) (((a)[1] < (b)[1]) || ((a)[1] == (b)[1] && (a)[0] < (b)[0]))
#define MIN(a,b) (((a) < (b)) ? (a) : (b))

static struct _nodeS _nnil = {{0,0,0,0},{0xffffffff,0xffffffff},{0,0,0,0}};
static struct _nodeS *_NNIL = &_nnil;

static int
getSlevel (PbufP tbl)
{
int level = -1;
int bits = 0;

    while (bits == 0)
    {
		if (tbl->bitcnt == 0)
		{
		    tbl->bits = lrandom();
		    tbl->bitcnt = 15;
		}

		bits = tbl->bits & 3;
		tbl->bits >>= 2;
		tbl->bitcnt--;

		if(++level > tbl->level)
			break;
    }
    return (level > SYM_MAXLEVEL) ? SYM_MAXLEVEL : level;

}

static void
hash(void *key, KEY *cat)
{
	cat->k[0] = ((unsigned long*)key)[0];
	cat->k[1] = ((unsigned long*)key)[1];
	cat->hv = ((cat->k[0] ^ cat->k[1]) * 1103515245UL) + 12345;
}
static void
sym_hash(unsigned long *key, char *symb)
{
int len = strlen(symb);
int i;
	for(i = 0; i < len; ++i)
	  ((unsigned char *)key)[i & 7] ^= symb[i];
	key[0] = ((key[0] ^ key[1]) * 1103515245UL) + 12345;
	key[1] = len;
}
static void *
new_Snode(PbufP tbl, int levels)
{
NodePS p;
int size;
	if(levels <= 3)
	{
		if(tbl->freelist)
		{
			p = tbl->freelist;
			tbl->freelist = p->fptr[0];
			p->fptr[0] = 0;
			return p;
		}
	}
	size = sizeof(struct _nodeS) + ((levels-3) * sizeof(void*));
	if(tbl->chunksize < size)
	{
		tbl->chunkbase = Ccalloc(tbl->category, 1, 4080);
		tbl->chunksize = 4080;
	} 
	tbl->chunksize -= size;
	p = (NodePS)tbl->chunkbase;
	tbl->chunkbase += size;
	return p;
}
static void
free_Snode(PbufP tbl, NodePS node)
{
	bzero(node, sizeof(struct _nodeS));
	node->fptr[0] = tbl->freelist;
	tbl->freelist = node;
}

static void*
NewSymTable(int category, int nbins)
{
PbufP tbl;

	tbl = Ccalloc(category, 1, nbins*sizeof(NodePS) + sizeof(struct _pbuf));
	if(nbins == 0)
	{/* sorted dictionary */
	int i;
		tbl->header = new_Snode(tbl, SYM_MAXLEVEL+1);
		for(i = 0; i <= SYM_MAXLEVEL; ++i)
			tbl->header->fptr[i] = _NNIL;
	}
	tbl->nbins = nbins;
	tbl->category = category;
	return tbl;
}
static int
SymFind(void *tbl, void *key, void *result)
{
NodePS node;

	if(tbl && key)
	{
	  if(TBL->nbins)
	  {/* hashed dictionary */
	  KEY cat;

		hash(key, &cat);
		if((node = TBL->bins[cat.hv % TBL->nbins]))
		{
			do {
				if(		node->key[0] == cat.k[0]
					&&	node->key[1] == cat.k[1])
				{
					if(result)
					  *((NodePS *)result) = node;
					TBL->lastbin = cat.hv % TBL->nbins;
					TBL->lastptr = node;
					return 1;
				}
			 } while((node = node->fptr[0]));
		}
		return 0;
	  }
	  else
	  {/* sorted dictionary */
	  int level;

	    node = TBL->header;
	    for(level = TBL->level; level >= 0; level--)
		{
		  while( KEYLT(node->fptr[level]->key, ((unsigned long*)key)) )
		    node = node->fptr[level];
		}
	    node = node->fptr[0];

		TBL->lastptr = node;
		if(result)
			*((NodePS *)result) = node;
		return (KEYEQ(node->key, ((unsigned long*)key))) ? 1 : 0;
	  }
	}
	return -1;
}
static int
SymFindRange(void *tbl, void *key, void *result)
{/* assumes 4 byte key and value (the value can be bigger) */
NodePS node;

	if(tbl && key)
	{
	  if(TBL->nbins)
	  {/* hashed dictionary */
		return 0;
	  }
	  else
	  {/* sorted dictionary */
	  NodePS prev;
	  int level;

	    node = TBL->header;
	    for(level = TBL->level; level >= 0; level--)
		{
		  while ( node->fptr[level]->key[0] < ((unsigned long*)key)[0] )
		    node = node->fptr[level];
		}
		prev = node;
	    node = node->fptr[0];

		if( node->key[0] == ((unsigned long*)key)[0] )
		{
			TBL->lastptr = node;
			if(result)
				*((NodePS *)result) = node;
			return 1;
		}		
		if( ((unsigned long*)key)[0] < prev->key[0]+prev->value[0] )
		{
			TBL->lastptr = prev;
			if(result)
				*((NodePS *)result) = prev;
			return 1;
		}
		return 0;
	  }
	}
	return -1;
}
static void*
SymInsert(void *tbl, void *key, void *value, int datsiz)
{
NodePS node;

	if(tbl && key)
	{
	  if(TBL->nbins)
	  {/* hashed dictionary */
	  KEY cat;
	  NodePS *binp;
		hash(key, &cat);
		node = new_Snode(tbl, 0);
		TBL->lastbin = cat.hv % TBL->nbins;
		TBL->lastptr = node;
		binp = &TBL->bins[TBL->lastbin];
		if(value && datsiz)
		  memcpy(node, value, MIN(datsiz,16));
		node->key[0] = cat.k[0];
		node->key[1] = cat.k[1];
		node->fptr[0] = *binp;
		*binp = node;
		return node;
	  }
	  else
	  {/* sorted dictionary */
	  int level;
	  NodePS update[SYM_MAXLEVEL+1];

	    node = TBL->header;
	    for (level = TBL->level; level >= 0; level--)
	    {
		  while ( KEYLT(node->fptr[level]->key,((unsigned long*)key)) )
		    node = node->fptr[level];
		  update[level] = node;
		}

	    level = getSlevel(tbl);

	    while(TBL->level < level)
			update[++TBL->level] = TBL->header;

	    node = new_Snode(tbl, level);

		if(value && datsiz)
		  memcpy(node, value, MIN(datsiz,16));
		node->key[0] = ((unsigned long*)key)[0];
		node->key[1] = ((unsigned long*)key)[1];

	    while(level >= 0)
	    {
			node->fptr[level] = update[level]->fptr[level];
			update[level]->fptr[level] = node;
			level--;
    	}
		TBL->lastptr = node;
		return node;
	 }
	}
	return 0;
}
static int
StringFind(void *tbl, char *string, void *result)
{
unsigned long key[2];
struct {
	char *symname;
} *valp;

	key[0] = 0;
	key[1] = 0;
	sym_hash(key, string);

	if(SymFind(tbl, key, &valp) == 1)
	{
	unsigned long *key1;
		do {
			if(!strcmp(string, valp->symname))
			{
				if(result)
					*((void **)result) = valp;
				return 1;
			}
			/* Check duplicates */
			if(!SymNext(tbl))
				break;
			SymKey(tbl, &key1);
			SymValue(tbl, &valp);
		} while(KEYEQ(key, key1));
	}
	return 0;
}
static int
StringInsert(void *tbl, char *string, void *result)
{
unsigned long key[2];
struct {
	char *symname;
} *valp;

	key[0] = 0;
	key[1] = 0;
	sym_hash(key, string);
	if(SymFind(tbl, key, &valp) == 1)
	{/* hash keys match */
	unsigned long *key1;
		do {
			if(!strcmp(string, valp->symname))
			{
				if(result)
					*((void **)result) = valp;
				return 1;
			}
			/* Check duplicates */
			if(!SymNext(tbl))
				break;
			SymKey(tbl, &key1);
			SymValue(tbl, &valp);
		} while(KEYEQ(key, key1));
	}
	/* NOMATCH */
	valp = SymInsert(tbl, key, &string, 4);
	if(result)
		*((void**)result) = valp;
	return 0;
}
static void
SymDelete(void *tbl, void *key)
{
NodePS node;

	if(tbl && key)
	{