🚀 go-pugleaf

Hi,

We're currently using gcc-2.2.2 for project development on
a sparc 1+ architecture (sunOS 4.1.1).
We have serious doubts there is some bug in the gcc -O2 optimizer: we have a
program that behaves differently on compilation with and without the -O2 option.

Unfortunately the complete program as a whole is too big (and complicated) to
send you and isolating the bug in a small running program is also hard to do.
However, we have a pretty good idea of the location of the bug (we know small
code changes that fix the bug).

Below there is a cpp-file storing part of the program containing the bug.

The cpp-file was generated by the command
	gcc -pedantic -fpcc-struct-return -I/home/kiwi6/LOCO/NLOCO.NEW/Include -I.
	-I- -I/usr/openwin/share/include -I/usr/openwin/share/include/X11
	-I/usr/openwin/share/include/Xol -DOPT -E hash.c > hash.cpp

The bugged object file was generated by the command

	gcc -pedantic -fpcc-struct-return  -O2
	-I/home/kiwi6/LOCO/NLOCO.NEW/Include -I. -I-
	-I/usr/openwin/share/include -I/usr/openwin/share/include/X11
	-I/usr/openwin/share/include/Xol  -DOPT  -c hash.c -o hash.o

The problem arises in the cpp-code at lines 480-484: 
With the call to the 'vAvoidGCCbug' function (which doesn't do anything since
its body is completely empty) included, everything is ok, both with and without
-O2 option in the compilation. If we remove the 'vAvoidGCCbug' call at line 482, 
the compilation without -O2 is still ok. However, with the -O2 compilation,
the presence of the 
	((*(pbucket1)).hdr.iUsg)  = 35;
statement at line 482 changes the contents of the record the pointer 'pbucket2'
points to (which is not the case without -O2).
Although both 'pbucket1' and 'pbucket2' are pointers to records of
the same type, they do not point to the same memory area. Since 'pbucket2' has
been used as an argument in the 'memcpy' function at line 480, we suspect the -O2
optimizer to perform a bad register movement optimization in the assignment at
line 482. This can (in our opinion) explain why the bug disappears in case of
the addition of the 
	vAvoidGCCbug(ixB,ixB,ixB);
statement at line 481.

Can you check whether the (sparc 1+ , sunOS 4.1.1) assembler code of the lines
480 - 485 is bug-free in case of a -O2 compilation (and line 481 eliminated)?

Many thanks,

Luc Van Beirendonck
University of Antwerp (Belgium)
vbeiren@kiwi.uia.ac.be

___________________________________________________________________________



 
 
extern void *memccpy();
extern void *memchr();
extern void *memcpy();
extern void *memset();
extern int memcmp();
 
 
 
extern	struct	_iobuf {
	int	_cnt;
	unsigned char *_ptr;
	unsigned char *_base;
	int	_bufsiz;
	short	_flag;
	char	_file;		 
} _iob[];
extern struct _iobuf 	*fopen();
extern struct _iobuf 	*fdopen();
extern struct _iobuf 	*freopen();
extern struct _iobuf 	*popen();
extern struct _iobuf 	*tmpfile();
extern long	ftell();
extern char	*fgets();
extern char	*gets();
extern char	*sprintf();
extern char	*ctermid();
extern char	*cuserid();
extern char	*tempnam();
extern char	*tmpnam();
 
 
 
 
typedef	int		sigset_t;	 
typedef	unsigned int	speed_t;	 
typedef	unsigned long	tcflag_t;	 
typedef	unsigned char	cc_t;		 
typedef	int		pid_t;		 
typedef	unsigned short	mode_t;		 
typedef	short		nlink_t;	 
typedef	long		clock_t;	 
typedef	long		time_t;		 
typedef	int		size_t;		 
typedef int		ptrdiff_t;	 
typedef	unsigned short	wchar_t;	 
extern unsigned int _mb_cur_max;
 
extern void	abort( );
extern int	abs( );
extern double	atof( );
extern int	atoi( );
extern long int	atol( );
extern char *	bsearch( 
);
extern void *	calloc( );
extern void	exit( );
extern void	free( );
extern char *	getenv( );
extern void *	malloc( );
extern int	qsort( 
);
extern int	rand( );
extern void *	realloc( );
extern int	srand( );
extern int    mbtowc( );
extern int    wctomb( );
extern size_t mbstowcs( );
extern size_t wcstombs( );
 
typedef	unsigned	IX;
typedef	unsigned	SZ;
typedef	unsigned	T;
typedef	unsigned	JUNK;
typedef	int		I;
typedef	short		S;
typedef	unsigned short	US;
typedef	void		V;
typedef	char		C;
typedef	unsigned char	UC;
typedef	int		B;
typedef	B		*PB;
typedef	C		*PC;
typedef	UC		*PUC;
typedef	V		*PV;
typedef	I		*PI;
typedef	IX		*PIX;
typedef	SZ		*PSZ;
typedef	I		(*FI)();
typedef	B		(*FB)();
typedef	V		(*FV)();
typedef IX		(*FX)();
 
 
 
 
 
 
 
 
 
 
 
 
 
 
typedef	unsigned char	u_char;
typedef	unsigned short	u_short;
typedef	unsigned int	u_int;
typedef	unsigned long	u_long;
typedef	unsigned short	ushort;		 
typedef	unsigned int	uint;		 
typedef	struct  _physadr_t { int r[1]; } *physadr_t;
typedef	struct label_t {
	int	val[2];
} label_t;
typedef	struct	_quad_t { long val[2]; } quad_t;
typedef	long	daddr_t;
typedef	char *	caddr_t;
typedef	unsigned long	ino_t;
typedef	short	dev_t;
typedef	long	off_t;
typedef	unsigned short	uid_t;
typedef	unsigned short	gid_t;
typedef	long	key_t;
typedef	char *	addr_t;
 
typedef	long	fd_mask;
typedef	struct fd_set {
	fd_mask	fds_bits[(((256 )+(( (sizeof (fd_mask) * 8		)	)-1))/( (sizeof (fd_mask) * 8		)	)) ];
} fd_set;
extern void	_exit( );
extern int	access( );
extern unsigned	alarm( );
extern int	chdir( );
extern int	chmod( );
extern int	chown( );
extern int	close( );
extern char	*ctermid( );
extern char	*cuserid( );
extern int	dup( );
extern int	dup2( );
extern int	execl( );
extern int	execle( );
extern int	execlp( );
extern int	execv( );
extern int	execve( );
extern int	execvp( );
extern pid_t	fork( );
extern long	fpathconf( );
extern char	*getcwd( );
extern gid_t	getegid( );
extern uid_t	geteuid( );
extern gid_t	getgid( );
extern int	getgroups( );
extern char	*getlogin( );
extern pid_t	getpgrp( );
extern pid_t	getpid( );
extern pid_t	getppid( );
extern uid_t	getuid( );
extern int	isatty( );
extern int	link( );
extern off_t	lseek( );
extern long	pathconf( );
extern int	pause( );
extern int	pipe( );
extern int	read( );
extern int	rmdir( );
extern int	setgid( );
extern int	setpgid( );
extern pid_t	setsid( );
extern int	setuid( );
extern unsigned	sleep( );
extern long	sysconf( );
extern pid_t	tcgetpgrp( );
extern int	tcsetpgrp( );
extern char	*ttyname( );
extern int	unlink( );
extern int	write( );
typedef struct
	{
	SZ	size;
	IX	bot;	 
	IX	root;	 
	SZ	tos;
	B	bIsVar;	 
	B	bIsHep;	 
	I	data[1];
	}	SEG,*PSEG;
 
extern	PSEG	psegNew(PC pcFn,I sz,I szF);
 
extern	V	vSegClose(PSEG pseg);
extern	V	vSegZap(PSEG pseg);
extern	IX	ixSegAlloc(PSEG pseg,SZ sz);
extern	V	vSegFree(PSEG pseg,IX ix,SZ sz);
 
 
 
extern	I	iSegFreeAtmSz(PSEG pseg,IX ix);
extern	V	vSegPrintf(struct _iobuf  *pfile,PSEG pstk,FV fv,B bCheck);
extern	SZ	szSegFree(PSEG pseg);
extern	V	vSegCheck(PC pc,I i,B full,PSEG pseg);
extern	V	vSegFreePrint(struct _iobuf  *pfile,PSEG pseg,IX ix);
extern	V	vSegVrePrint(struct _iobuf  *pfile,PSEG pseg);
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
				  
 
extern PSEG SEGS[	8 ];
 
 
 
 
 
 
 
 
 
 
 
extern	IX	ixAtmDrf(IX ix);
 
extern	SZ	szAtm(PSEG pseg,IX ix);
 
extern	PC	pcAtmIx(IX ix);
extern	V	vAtmPrintf(struct _iobuf  *pfile,PSEG pseg,IX ix);
 
extern	PC	pcAtm(IX ix);
extern	PC	pcAtms(IX ix);
extern	V	vAtmPuts(PC buf,IX ix,I style);
extern	V	vAtmPutf(struct _iobuf  *pfile,IX ix,I style);
 
extern	IX	ixAtmKpy(	IX  mseg,PSEG pseg,IX from);
extern	IX	ixAtmCpy(	IX  mseg,IX from);
extern	IX	ixAtmCby(	IX  mseg,IX from);
extern	V	vAtmCb0();
 
extern	I	iAtmCmp(IX atm1,IX atm2);
extern	B	bAtmBnd(IX atm);
 
extern	V	vAtmZap(IX from);
extern	V	vAtmSap(IX from);
 
extern IX ixAtmResize(	IX  mseg,IX from,I newSzInC);
 
extern	V	vAtmInit();
 
extern	I	iAtmCheck;
extern	B	bAtmCheck(PSEG pseg,IX ix);
extern	B	bAtmPtrCheck(IX ix);
extern	V	vAtmCheckAll(PC pc,I i);
 
 
extern	FV	fvMemCpy[];
extern	FV	fvMemZap[];
extern	FV	fvMemPut[];
 
extern	V	vMemInstall(I iFun,FV fxCpy,FV fvZap,FV fvPut);
 
typedef	IX	(*PFIXIX)(IX ix);
typedef	B	(*PFBIXIX)(IX ix1,IX ix2);
typedef	struct
	{
	IX	ixKey;
	IX	ixData;
	} ELEMENT, *PELEMENT, **HELEMENT;
typedef	struct
	{
	int	iUsg;
	IX	ixOverflow;
	} BUCKET_HDR;
typedef	struct
	{
	BUCKET_HDR	hdr;
	ELEMENT		elements[1 ];
	} BUCKET, *PBUCKET, **HBUCKET;
typedef	struct
	{
	IX	ixN;
	int	iBN;
	int	iBSz;
	PFIXIX	pfixScramble;
	PFBIXIX	pfbCompare;
	IX	ixTreshold;
	int	iLevel;
	} PRIMARY_HDR;
typedef	struct
	{
	PRIMARY_HDR	hdr;
	BUCKET		buckets[1 ];
	} PRIMARY, *PPRIMARY, **HPRIMARY;
 
typedef	struct
	{
	IX	ixN;
	int	iBN;
	int	iBSz;
	PFIXIX	pfixScramble;
	PFBIXIX	pfbCompare;
	IX	ixTop;
	IX	ixFree;
	} OVERFLOW_HDR;
typedef	struct
	{
	OVERFLOW_HDR	hdr;
	BUCKET		buckets[1 ];
	} OVERFL, *POVERFL, **HOVERFL;
 
 
 
 
 
extern	void	vHashNew(	IX  mseg,IX *pixP,IX *pixO,
			int iNrOfBuckets,int iBucketSize,
			PFIXIX pfixScramble,PFBIXIX pfbCompare);
extern	void	vHashZap(IX ixP,IX ixO);
 
extern	B	bHashPut(IX *pixP,IX *pixO,IX ixKey,IX ixData);
extern	B	bHashRemove(IX ixP,IX ixO,IX ixKey);
extern	B	bHashGet(IX ixP,IX ixO,IX *pixKey,IX *pixData);
extern	B	bHashReplace(IX ixP,IX ixO,IX ixKey,IX ixData);
 
extern	void	vHashDump(struct _iobuf  *pfile,IX ixP,IX ixO);
void
vHashNew(	IX  mseg,IX *pixP,IX *pixO,
	int iNrOfBuckets,int iBucketSize,
	PFIXIX pfixScramble,PFBIXIX pfbCompare)
{
 ;
 ;
{
 
int	iSz;
PC	pc;
IX	ix;
PBUCKET	pbucket;
iSz = sizeof(PRIMARY_HDR)+iNrOfBuckets*(iBucketSize*sizeof(ELEMENT)+sizeof(BUCKET_HDR));
{ { *pixP = 	(ixSegAlloc(	(SEGS[(((SZ)	((mseg)&	000700000000 ) )>>	24 ) ]) ,			(((iSz)+sizeof(IX)-1)/sizeof(IX))  +2)) ; { 	(	(SEGS[(((SZ)	((mseg)&	000700000000 ) )>>	24 ) ]) )->data[*pixP] 	= ((	020000000000 |((	003000000000 |(iSz)) )) ) ; 	(	(SEGS[(((SZ)	((mseg)&	000700000000 ) )>>	24 ) ]) )->data[*pixP+1] 	=      19 ; if ((PC)0!=(PC)0) memcpy((PC)&((	(SEGS[(((SZ)	((mseg)&	000700000000 ) )>>	24 ) ]) )->data[(*pixP)+2 +(0)] ),(PC)0,(I)iSz);	} ; }  *pixP = ((	003000000000 |(((mseg)|(*pixP)) )) ) ; } ;
pc = ((PC)&(	(SEGS[(((SZ)	((*pixP)&	000700000000 ) )>>	24 ) ]) ->data[	(	((*pixP)&	000077777777 ) ) +2 ])) ;
	((*((PPRIMARY)pc)).hdr.ixN)  = (IX)iNrOfBuckets;
	((*((PPRIMARY)pc)).hdr.iBN)  = iBucketSize;
	((*((PPRIMARY)pc)).hdr.iBSz)  = sizeof(BUCKET_HDR)+iBucketSize*sizeof(ELEMENT);
((*((PPRIMARY)pc)).hdr.pfixScramble)  = pfixScramble;
	((*((PPRIMARY)pc)).hdr.pfbCompare)  = pfbCompare;
	((*((PPRIMARY)pc)).hdr.ixTreshold)  = 0;
	((*((PPRIMARY)pc)).hdr.iLevel)  = iNrOfBuckets;
for (ix=0;ix<iNrOfBuckets;ix++)
	{
	pbucket = 	((PBUCKET)(((PC)((*((PPRIMARY)pc)).buckets))+(ix)*	((*((PPRIMARY)pc)).hdr.iBSz) )) ;
		((*(pbucket)).hdr.iUsg)  = 0;
	((*(pbucket)).hdr.ixOverflow)  = ((IX)(-1)) ;
	}
}
{
 
int	iSz;
IX	ixN;
PC	pc;
ixN = iNrOfBuckets>=10?iNrOfBuckets/10:1;
iSz = sizeof(OVERFLOW_HDR)+ixN*(iBucketSize*sizeof(ELEMENT)+sizeof(BUCKET_HDR));
{ { *pixO = 	(ixSegAlloc(	(SEGS[(((SZ)	((mseg)&	000700000000 ) )>>	24 ) ]) ,			(((iSz)+sizeof(IX)-1)/sizeof(IX))  +2)) ; { 	(	(SEGS[(((SZ)	((mseg)&	000700000000 ) )>>	24 ) ]) )->data[*pixO] 	= ((	020000000000 |((	003000000000 |(iSz)) )) ) ; 	(	(SEGS[(((SZ)	((mseg)&	000700000000 ) )>>	24 ) ]) )->data[*pixO+1] 	=      20 ; if ((PC)0!=(PC)0) memcpy((PC)&((	(SEGS[(((SZ)	((mseg)&	000700000000 ) )>>	24 ) ]) )->data[(*pixO)+2 +(0)] ),(PC)0,(I)iSz);	} ; }  *pixO = ((	003000000000 |(((mseg)|(*pixO)) )) ) ; } ;
pc = ((PC)&(	(SEGS[(((SZ)	((*pixO)&	000700000000 ) )>>	24 ) ]) ->data[	(	((*pixO)&	000077777777 ) ) +2 ])) ;
	((*((POVERFL)pc)).hdr.ixN)  = ixN;
	((*((POVERFL)pc)).hdr.iBN)  = iBucketSize;
	((*((POVERFL)pc)).hdr.iBSz)  = sizeof(BUCKET_HDR)+iBucketSize*sizeof(ELEMENT);
((*((POVERFL)pc)).hdr.pfixScramble)  = pfixScramble;
	((*((POVERFL)pc)).hdr.pfbCompare)  = pfbCompare;
	((*((POVERFL)pc)).hdr.ixTop)  = 0;
	((*((POVERFL)pc)).hdr.ixFree)  = ((IX)(-1)) ;
}
vHashHeaderDump((&_iob[1]) ,*pixP,*pixO);
}
void
vHashZap(IX ixP,IX ixO)
{
vAtmZap(ixP);
vAtmZap(ixO);
}
static
IX
ixOBNew(IX *pixO)
{
PC	pc;
IX	ixB;
pc = ((PC)&(	(SEGS[(((SZ)	((*pixO)&	000700000000 ) )>>	24 ) ]) ->data[	(	((*pixO)&	000077777777 ) ) +2 ])) ;
if ((ixB=	((*((POVERFL)pc)).hdr.ixFree) )==((IX)(-1)) )
	{
	 
	if (	((*((POVERFL)pc)).hdr.ixTop) >=	((*((POVERFL)pc)).hdr.ixN) )
		{
		 
		if (	((*((POVERFL)pc)).hdr.ixN) <10)
				((*((POVERFL)pc)).hdr.ixN) ++;
		else
				((*((POVERFL)pc)).hdr.ixN)  = 11*	((*((POVERFL)pc)).hdr.ixN) /10;
		*pixO = ixAtmResize(	((*pixO)&	000700000000 ) ,*pixO,
			sizeof(OVERFLOW_HDR)+	((*((POVERFL)pc)).hdr.ixN) *	((*((POVERFL)pc)).hdr.iBSz) );
		pc = ((PC)&(	(SEGS[(((SZ)	((*pixO)&	000700000000 ) )>>	24 ) ]) ->data[	(	((*pixO)&	000077777777 ) ) +2 ])) ;
		}
	return 	((*((POVERFL)pc)).hdr.ixTop) ++;
	}
 
	((*((POVERFL)pc)).hdr.ixFree)  = ((*(	((PBUCKET)(((PC)((*((POVERFL)pc)).buckets))+(	((*((POVERFL)pc)).hdr.ixFree) )*	((*((PPRIMARY)pc)).hdr.iBSz) )) )).hdr.ixOverflow) ;
return ixB;
}
static
void
vOBZap(IX ixO,IX ix)
{
PC	pc;
pc = ((PC)&(	(SEGS[(((SZ)	((ixO)&	000700000000 ) )>>	24 ) ]) ->data[	(	((ixO)&	000077777777 ) ) +2 ])) ;
((*(	((PBUCKET)(((PC)((*((POVERFL)pc)).buckets))+(ix)*	((*((PPRIMARY)pc)).hdr.iBSz) )) )).hdr.ixOverflow)  = 	((*((POVERFL)pc)).hdr.ixFree) ;
	((*((POVERFL)pc)).hdr.ixFree)  = ix;
}
static
IX
ixPBNew(IX *pixP)
{
PC	pc;
IX	ixB;
pc = ((PC)&(	(SEGS[(((SZ)	((*pixP)&	000700000000 ) )>>	24 ) ]) ->data[	(	((*pixP)&	000077777777 ) ) +2 ])) ;
if (	((*((PPRIMARY)pc)).hdr.iLevel) +	((*((PPRIMARY)pc)).hdr.ixTreshold) >=	((*((PPRIMARY)pc)).hdr.ixN) )
	{
	 
	if (	((*((PPRIMARY)pc)).hdr.ixN) <10)
			((*((POVERFL)pc)).hdr.ixN) ++;
	else
			((*((PPRIMARY)pc)).hdr.ixN)  = 11*	((*((PPRIMARY)pc)).hdr.ixN) /10;
	*pixP = ixAtmResize(	((*pixP)&	000700000000 ) ,*pixP,
		sizeof(PRIMARY_HDR)+	((*((PPRIMARY)pc)).hdr.ixN) *	((*((PPRIMARY)pc)).hdr.iBSz) );
	pc = ((PC)&(	(SEGS[(((SZ)	((*pixP)&	000700000000 ) )>>	24 ) ]) ->data[	(	((*pixP)&	000077777777 ) ) +2 ])) ;
	}
return 	((*((PPRIMARY)pc)).hdr.iLevel) +	((*((PPRIMARY)pc)).hdr.ixTreshold) ;
}
static
void
vAvoidGCCbug(IX ixA, IX ixB, IX ixC)
{
}
static	int	iHashSplitLevel=0;
static
void
vHashSplit(IX *pixP,IX *pixO)
{
PC	pcP,pcO;
PBUCKET	pbucket1,pbucket2,pbucket;
IX	ix,ixB;
int	i;
if (iHashSplitLevel)
	return;
iHashSplitLevel++;
 ;
 ;
 
pcP = ((PC)&(	(SEGS[(((SZ)	((*pixP)&	000700000000 ) )>>	24 ) ]) ->data[	(	((*pixP)&	000077777777 ) ) +2 ])) ;
pbucket1 = 	((PBUCKET)(((PC)((*((PPRIMARY)pcP)).buckets))+(	((*((PPRIMARY)pcP)).hdr.ixTreshold) )*	((*((PPRIMARY)pcP)).hdr.iBSz) )) ;
ixB = ixOBNew(pixO);
pcO = ((PC)&(	(SEGS[(((SZ)	((*pixO)&	000700000000 ) )>>	24 ) ]) ->data[	(	((*pixO)&	000077777777 ) ) +2 ])) ;
pbucket2 = 	((PBUCKET)(((PC)((*((POVERFL)pcO)).buckets))+(ixB)*	((*((PPRIMARY)pcO)).hdr.iBSz) )) ;

memcpy((PC)pbucket2,(PC)pbucket1,((*((PPRIMARY)pcP)).hdr.iBSz) );
vAvoidGCCbug(ixB,ixB,ixB);
((*(pbucket1)).hdr.iUsg)  = 35;
((*(pbucket1)).hdr.ixOverflow)  = ((IX)(-1)) ;
ix = ixPBNew(pixP);

pcP = ((PC)&(	(SEGS[(((SZ)	((*pixP)&	000700000000 ) )>>	24 ) ]) ->data[	(	((*pixP)&	000077777777 ) ) +2 ])) ;
pbucket = 	((PBUCKET)(((PC)((*((PPRIMARY)pcP)).buckets))+(ix)*	((*((PPRIMARY)pcP)).hdr.iBSz) )) ;
	((*(pbucket)).hdr.iUsg)  = 0;
((*(pbucket)).hdr.ixOverflow)  = ((IX)(-1)) ;
fprintf((&_iob[1]) ,"vHashSplit: (%x,%x)\n",pixP,pixO);
fprintf((&_iob[1]) ,"\tsplitting bucket nr %d\n",	((*((PPRIMARY)pcP)).hdr.ixTreshold) );
fprintf((&_iob[1]) ,"\tcopying to scratch overflow bucket nr %d\n",ixB);
fprintf((&_iob[1]) ,"\tnew primary bucket = %d\n",ix);
fprintf((&_iob[1]) ,"\tbucket usage = %d\n",	((*(pbucket1)).hdr.iUsg) );
fprintf((&_iob[1]) ,"\tbucket overflow = %d\n",((*(pbucket1)).hdr.ixOverflow) );
fprintf((&_iob[1]) ,"\tscratch bucket usage = %d\n",	((*(pbucket2)).hdr.iUsg) );
fprintf((&_iob[1]) ,"\tscratch bucket overflow = %d\n",((*(pbucket2)).hdr.ixOverflow) );
 
if (++	((*((PPRIMARY)pcP)).hdr.ixTreshold) >=(IX)	((*((PPRIMARY)pcP)).hdr.iLevel) )
	{
		((*((PPRIMARY)pcP)).hdr.iLevel)  *= 2;
		((*((PPRIMARY)pcP)).hdr.ixTreshold)  = 0;
	fprintf((&_iob[1]) ,"\tlast bucket for current level (%d) has been split\n",
			((*((PPRIMARY)pcP)).hdr.iLevel) /2);
	fprintf((&_iob[1]) ,"\tdubble level\n");
	}
 
while (ixB!=((IX)(-1)) )
	{
	for (i=0;i<	((*(pbucket2)).hdr.iUsg) ;i++)
		{
		bHashPut(pixP,pixO,((*(pbucket2)).elements[i].ixKey) ,((*(pbucket2)).elements[i].ixData) );
		 
		pcO = ((PC)&(	(SEGS[(((SZ)	((*pixO)&	000700000000 ) )>>	24 ) ]) ->data[	(	((*pixO)&	000077777777 ) ) +2 ])) ;
		pbucket2 = 	((PBUCKET)(((PC)((*((POVERFL)pcO)).buckets))+(ixB)*	((*((PPRIMARY)pcO)).hdr.iBSz) )) ;
		}
	ix = ixB;
	ixB = ((*(pbucket2)).hdr.ixOverflow) ;
	pbucket2 = 	((PBUCKET)(((PC)((*((POVERFL)pcO)).buckets))+(ixB)*	((*((PPRIMARY)pcO)).hdr.iBSz) )) ;
	vOBZap(*pixO,ix);
	}
iHashSplitLevel--;
fprintf((&_iob[1]) ,"\tvHashSplit finishes\n");
}
B
bHashPut(IX *pixP,IX *pixO,IX ixKey,IX ixData)
{
PC	pc;
IX	ixB;
PBUCKET	pbucket;
B	bSplit = 0;
 ;
 ;
pc = ((PC)&(	(SEGS[(((SZ)	((*pixP)&	000700000000 ) )>>	24 ) ]) ->data[	(	((*pixP)&	000077777777 ) ) +2 ])) ;
{	IX	ix;	ix = ((*((PPRIMARY)pc)).hdr.pfixScramble) (ixKey);	if ((ixB=ix%	((*((PPRIMARY)pc)).hdr.iLevel) )<	((*((PPRIMARY)pc)).hdr.ixTreshold) )	ixB = ix%(2*	((*((PPRIMARY)pc)).hdr.iLevel) );	} ;
pbucket = 	((PBUCKET)(((PC)((*((PPRIMARY)pc)).buckets))+(ixB)*	((*((PPRIMARY)pc)).hdr.iBSz) )) ;
fprintf((&_iob[1]) ,"bHashPut: (%x,%x)\n\tkey = ",pixP,pixO);
vAtmPutf((&_iob[1]) ,ixKey,0) ;
fprintf((&_iob[1]) ,"\n\tdata = ");
vAtmPutf((&_iob[1]) ,ixData,0) ;
fprintf((&_iob[1]) ,"\n\tbucket nr = %d\n",ixB);
if (	((*(pbucket)).hdr.iUsg) >=	((*((PPRIMARY)pc)).hdr.iBN) )
	{
	 
	bSplit = 1;
	pc = ((PC)&(	(SEGS[(((SZ)	((*pixO)&	000700000000 ) )>>	24 ) ]) ->data[	(	((*pixO)&	000077777777 ) ) +2 ])) ;
	do
		{
		ixB = ((*(pbucket)).hdr.ixOverflow) ;
		if (ixB==((IX)(-1)) )
			{
			 
			ixB = ((*(pbucket)).hdr.ixOverflow)  = ixOBNew(pixO);
			pc = ((PC)&(	(SEGS[(((SZ)	((*pixO)&	000700000000 ) )>>	24 ) ]) ->data[	(	((*pixO)&	000077777777 ) ) +2 ])) ;
			pbucket = 	((PBUCKET)(((PC)((*((POVERFL)pc)).buckets))+(ixB)*	((*((PPRIMARY)pc)).hdr.iBSz) )) ;
				((*(pbucket)).hdr.iUsg)  = 0;
			((*(pbucket)).hdr.ixOverflow)  = ((IX)(-1)) ;
			break;
			}
		pbucket = 	((PBUCKET)(((PC)((*((POVERFL)pc)).buckets))+(ixB)*	((*((PPRIMARY)pc)).hdr.iBSz) )) ;
		}
	while (	((*(pbucket)).hdr.iUsg) >=	((*((POVERFL)pc)).hdr.iBN) );
	}
 
((*(pbucket)).elements[	((*(pbucket)).hdr.iUsg) ].ixKey)  = ixKey;
((*(pbucket)).elements[	((*(pbucket)).hdr.iUsg) ].ixData)  = ixData;
	((*(pbucket)).hdr.iUsg) ++;
if (bSplit)
	vHashSplit(pixP,pixO);
return 1;
}
static
B
bHashGetLocation(IX ixP,IX ixO,IX ixKey,B *pbPrimary,HBUCKET hbucket,int *piPos)
{
PC	pcP,pcO;
IX	ixB;
PBUCKET	pbucket;
B	bFirst;
int	i;
 ;
 ;
pcP = ((PC)&(	(SEGS[(((SZ)	((ixP)&	000700000000 ) )>>	24 ) ]) ->data[	(	((ixP)&	000077777777 ) ) +2 ])) ;
pcO = ((PC)&(	(SEGS[(((SZ)	((ixO)&	000700000000 ) )>>	24 ) ]) ->data[	(	((ixO)&	000077777777 ) ) +2 ])) ;
{	IX	ix;	ix = ((*((PPRIMARY)pcP)).hdr.pfixScramble) (ixKey);	if ((ixB=ix%	((*((PPRIMARY)pcP)).hdr.iLevel) )<	((*((PPRIMARY)pcP)).hdr.ixTreshold) )	ixB = ix%(2*	((*((PPRIMARY)pcP)).hdr.iLevel) );	} ;
fprintf((&_iob[1]) ,"\nbHashGetLocation: \n\tkey = ");
vAtmPutf((&_iob[1]) ,ixKey,0) ;
fprintf((&_iob[1]) ,"\n\tkey hashes to location %d\n",ixB);
 ;
 
pbucket = 	((PBUCKET)(((PC)((*((PPRIMARY)pcP)).buckets))+(ixB)*	((*((PPRIMARY)pcP)).hdr.iBSz) )) ;
bFirst = 1;
while (ixB!=((IX)(-1)) )
	{
	fprintf((&_iob[1]) ,"\n\tscanning bucket %d\n",ixB);
	fprintf((&_iob[1]) ,"\tfirst free entry = %d\n\tOverflow = %d\n",
			((*(pbucket)).hdr.iUsg) ,((*(pbucket)).hdr.ixOverflow) );
	for (i=0;i<	((*(pbucket)).hdr.iUsg) ;i++)
		{
		if (!	((*((PPRIMARY)pcP)).hdr.pfbCompare) (ixKey,((*(pbucket)).elements[i].ixKey) ))
			{
			fprintf((&_iob[1]) ,"\t%d: compare with ",i);
			vAtmPutf((&_iob[1]) ,((*(pbucket)).elements[i].ixKey) ,0) ;
			fprintf((&_iob[1]) ," succeeded\n");
			*hbucket = pbucket;
			*piPos = i;
			*pbPrimary = bFirst;
			return 1;
			}
		else
			{
			fprintf((&_iob[1]) ,"\t%d: compare with ",i);
			vAtmPutf((&_iob[1]) ,((*(pbucket)).elements[i].ixKey) ,0) ;
			fprintf((&_iob[1]) ," failed\n");
			}
		}
	ixB = ((*(pbucket)).hdr.ixOverflow) ;
	pbucket = 	((PBUCKET)(((PC)((*((POVERFL)pcO)).buckets))+(ixB)*	((*((PPRIMARY)pcO)).hdr.iBSz) )) ;
	bFirst = 0;
	}
return 0;
}
int
bHashRemove(IX ixP,IX ixO,IX ixKey)
 
{
B	bPrimary;
PBUCKET	pbucket;
int	iPos,iPos2;
PC	pcP,pcO;
fprintf((&_iob[1]) ,"bHashRemove: \n\tkey = ");
vAtmPutf((&_iob[1]) ,ixKey,0) ;
if (!bHashGetLocation(ixP,ixO,ixKey,&bPrimary,&pbucket,&iPos))
	{
	fprintf((&_iob[1]) ,"\n\tno bucket found!!!\n");
	return 0;
	}
fprintf((&_iob[1]) ,"\n\tbucket nr = %d\n",iPos);
pcP = ((PC)&(	(SEGS[(((SZ)	((ixP)&	000700000000 ) )>>	24 ) ]) ->data[	(	((ixP)&	000077777777 ) ) +2 ])) ;
pcO = ((PC)&(	(SEGS[(((SZ)	((ixO)&	000700000000 ) )>>	24 ) ]) ->data[	(	((ixO)&	000077777777 ) ) +2 ])) ;
if (iPos!=(iPos2=--	((*(pbucket)).hdr.iUsg) ))
	{
	((*(pbucket)).elements[iPos].ixKey)  = ((*(pbucket)).elements[iPos2].ixKey) ;
	((*(pbucket)).elements[iPos].ixData)  = ((*(pbucket)).elements[iPos2].ixData) ;
	}
return 1;
}
B
bHashGet(IX ixP,IX ixO,IX *pixKey,IX *pixData)
 
{
PBUCKET	pbucket;
int	iPos;
B	bPrimary;
fprintf((&_iob[1]) ,"bHashGet:\n\tkey = ");
vAtmPutf((&_iob[1]) ,*pixKey,0) ;
if (bHashGetLocation(ixP,ixO,*pixKey,&bPrimary,&pbucket,&iPos))
	{
	*pixKey = ((*(pbucket)).elements[iPos].ixKey) ;
	*pixData = ((*(pbucket)).elements[iPos].ixData) ;
	fprintf((&_iob[1]) ,"\n\tdata = ");
	vAtmPutf((&_iob[1]) ,*pixData,0) ;
	fprintf((&_iob[1]) ,"\n\tbucket nr = %d\n",iPos);
	return 1;
	}
fprintf((&_iob[1]) ,"\n\tkey not found!!!\n");
return 0;
}
B
bHashReplace(IX ixP,IX ixO,IX ixKey,IX ixData)
 
{
PBUCKET	pbucket;
int	iPos;
B	bPrimary;
fprintf((&_iob[1]) ,"bHashReplace:\n\tkey = ");
vAtmPutf((&_iob[1]) ,ixKey,0) ;
fprintf((&_iob[1]) ,"\n\tdata = ");
vAtmPutf((&_iob[1]) ,ixData,0) ;
if (bHashGetLocation(ixP,ixO,ixKey,&bPrimary,&pbucket,&iPos))
	{
	((*(pbucket)).elements[iPos].ixData)  = ixData;
	fprintf((&_iob[1]) ,"\n\tbucket nr = %d\n",iPos);
	return 1;
	}
fprintf((&_iob[1]) ,"\n\tkey not found!!!\n");
return 0;
}
static
void
vHashPrintBucket(struct _iobuf  *pfile,PBUCKET pbucket)
{
int	iPos;
for (iPos=0;iPos<	((*(pbucket)).hdr.iUsg) ;iPos++)
	{
	fprintf(pfile,"%d: %s - %s\n",
	   iPos,pcAtms(((*(pbucket)).elements[iPos].ixKey) ),pcAtms(((*(pbucket)).elements[iPos].ixData) ));
	}
}
void
vHashDump(struct _iobuf  *pfile,IX ixP,IX ixO)
{
IX	ixB,ixB2;
PBUCKET	pbucket;
B	bFirst;
int	iPos;
PC	pcP,pcO;
 ;
 ;
pcP = ((PC)&(	(SEGS[(((SZ)	((ixP)&	000700000000 ) )>>	24 ) ]) ->data[	(	((ixP)&	000077777777 ) ) +2 ])) ;
pcO = ((PC)&(	(SEGS[(((SZ)	((ixO)&	000700000000 ) )>>	24 ) ]) ->data[	(	((ixO)&	000077777777 ) ) +2 ])) ;
 
fprintf(pfile,"HASH-TABLE %x,%x:\n",ixP,ixO);
fprintf(pfile,"\tbucketsize=%d\n",	((*((PPRIMARY)pcP)).hdr.iBN) );
fprintf(pfile,"\tprimary: size=%d+%d=%d\n",	((*((PPRIMARY)pcP)).hdr.iLevel) +	((*((PPRIMARY)pcP)).hdr.ixTreshold) ,
		((*((PPRIMARY)pcP)).hdr.ixN) -(	((*((PPRIMARY)pcP)).hdr.iLevel) +	((*((PPRIMARY)pcP)).hdr.ixTreshold) ),	((*((PPRIMARY)pcP)).hdr.ixN) );
fprintf(pfile,"\toverflow: size=%d+%d=%d\n",	((*((POVERFL)pcO)).hdr.ixTop) ,
		((*((POVERFL)pcO)).hdr.ixN) -	((*((POVERFL)pcO)).hdr.ixTop) ,	((*((POVERFL)pcO)).hdr.ixN) );
fprintf(pfile,"\ttreshold=%d\tlevel=%d\n",	((*((PPRIMARY)pcP)).hdr.ixTreshold) ,	((*((PPRIMARY)pcP)).hdr.iLevel) );
 
for (ixB=0;ixB<(IX)	((*((PPRIMARY)pcP)).hdr.iLevel) +	((*((PPRIMARY)pcP)).hdr.ixTreshold) ;ixB++)
	{
	ixB2 = ixB;
	pbucket = 	((PBUCKET)(((PC)((*((PPRIMARY)pcP)).buckets))+(ixB2)*	((*((PPRIMARY)pcP)).hdr.iBSz) )) ;
	bFirst = 1;
	 
	while (ixB2!=((IX)(-1)) )
		{
		fprintf(pfile,"%s %d, (%d/%d) -> %d:\n",
			bFirst?"primary":"overflow",ixB2,	((*(pbucket)).hdr.iUsg) ,
				((*((PPRIMARY)pcP)).hdr.iBN) ,((*(pbucket)).hdr.ixOverflow) );
		bFirst = 0;
		 
		vHashPrintBucket(pfile,pbucket);
		ixB2 = ((*(pbucket)).hdr.ixOverflow) ;
		pbucket = 	((PBUCKET)(((PC)((*((POVERFL)pcO)).buckets))+(ixB2)*	((*((PPRIMARY)pcO)).hdr.iBSz) )) ;
		}
	}
}
static
void
vHashHeaderDump(struct _iobuf  *pfile,IX ixP,IX ixO)
{
IX	ixB,ixB2;
PBUCKET	pbucket;
B	bFirst;
int	iPos;
PC	pcP,pcO;
 ;
 ;
pcP = ((PC)&(	(SEGS[(((SZ)	((ixP)&	000700000000 ) )>>	24 ) ]) ->data[	(	((ixP)&	000077777777 ) ) +2 ])) ;
pcO = ((PC)&(	(SEGS[(((SZ)	((ixO)&	000700000000 ) )>>	24 ) ]) ->data[	(	((ixO)&	000077777777 ) ) +2 ])) ;
 
fprintf(pfile,"HASH-TABLE %x,%x:\n",ixP,ixO);
fprintf(pfile,"\tbucketsize=%d elements\n",	((*((PPRIMARY)pcP)).hdr.iBN) );
fprintf(pfile,"\tprimary:\n\t\tnrOfBuckets = %d\n\t\tnr of bucket elems = %d\n",
		((*((PPRIMARY)pcP)).hdr.ixN) ,	((*((PPRIMARY)pcP)).hdr.iBN) );
fprintf(pfile,"\t\tnext bucket to split = %d\n\t\tlevel = %d\n",
		((*((PPRIMARY)pcP)).hdr.ixTreshold) ,	((*((PPRIMARY)pcP)).hdr.iLevel) );
fprintf(pfile,"\toverflow:\n\t\tnrOfBuckets = %d\n\t\tnr of bucket elems = %d\n",
		((*((POVERFL)pcO)).hdr.ixN) ,	((*((POVERFL)pcO)).hdr.iBN) );
fprintf(pfile,"\t\tfirst never used bucket = %d\n\t\tfirst free bucket = %d\n",
		((*((POVERFL)pcO)).hdr.ixTop) ,	((*((POVERFL)pcO)).hdr.ixFree) );
}