[frontierkernel-commits] Frontier/Common/source langhash.c,1.4.2.1,1.4.2.2 tablevalidate.c,1.3.2.1,1.3.2.2

[Andre R. <and...@us...>]

Update of /cvsroot/frontierkernel/Frontier/Common/source
In directory sc8-pr-cvs1.sourceforge.net:/tmp/cvs-serv1178/source

Modified Files:
      Tag: New_Tables_Experiment-branch
	langhash.c tablevalidate.c 
Log Message:
Further preparations for moving to dynamic allocation of hash bucket arrays: The size of a hash bucket array is now always a power of two. Computing an index into the bucket array is just a matter of masking the hash value rather than taking the rest of the division by a prime number. Hash tables now also keep track of the number of nodes they contain, so we will eventually be able to determine when to grow the hash bucket array.

Index: tablevalidate.c
===================================================================
RCS file: /cvsroot/frontierkernel/Frontier/Common/source/tablevalidate.c,v
retrieving revision 1.3.2.1
retrieving revision 1.3.2.2
diff -C2 -d -r1.3.2.1 -r1.3.2.2
*** tablevalidate.c	10 Nov 2004 16:19:07 -0000	1.3.2.1
--- tablevalidate.c	11 Nov 2004 13:12:40 -0000	1.3.2.2
***************
*** 126,130 ****
  				}
  
! 			if (((**x).hashval % (**ht).ctbuckets) != i) {
  				
  				if (flalert)
--- 126,130 ----
  				}
  
! 			if (hashtobucketindex (ht, (**x).hashval) != i) {
  				
  				if (flalert)

Index: langhash.c
===================================================================
RCS file: /cvsroot/frontierkernel/Frontier/Common/source/langhash.c,v
retrieving revision 1.4.2.1
retrieving revision 1.4.2.2
diff -C2 -d -r1.4.2.1 -r1.4.2.2
*** langhash.c	10 Nov 2004 16:19:05 -0000	1.4.2.1
--- langhash.c	11 Nov 2004 13:12:39 -0000	1.4.2.2
***************
*** 414,417 ****
--- 414,418 ----
  	
  	hdlhashbucketarray hbuckets;
+ 	unsigned long logsize;
  	
  	#endif
***************
*** 437,452 ****
  		short ct;
  		
! 		#ifdef flv10tables
  		
! 		unsigned long ctbuckets = (**ht).ctbuckets;
  		
  		hbuckets = (**ht).hbuckets;
  		
! 		assert (gethandlesize ((Handle) hbuckets) / sizeof (hdlhashnode) == ctbuckets);
  
  		#endif
  		
- 		hfirstfreetable = (**hfirstfreetable).prevhashtable;
- 		
  		ct = (**ht).cttmpstack;
  		
--- 438,453 ----
  		short ct;
  		
! 		hfirstfreetable = (**ht).prevhashtable; /*unlink*/
  		
! 		#ifdef flv10tables
  		
  		hbuckets = (**ht).hbuckets;
  		
! 		logsize = (**ht).logsize;
! 		
! 		assert (gethandlesize ((Handle) hbuckets) / sizeof (hdlhashnode) == (1 << logsize));
  
  		#endif
  		
  		ct = (**ht).cttmpstack;
  		
***************
*** 461,465 ****
  		(**ht).hbuckets = hbuckets;
  		
! 		(**ht).ctbuckets = ctbuckets;
  		
  		#endif
--- 462,468 ----
  		(**ht).hbuckets = hbuckets;
  		
! 		(**ht).logsize = logsize;
! 		
! 		(**ht).bucketmask = (1 << logsize) - 1;
  		
  		#endif
***************
*** 477,481 ****
  	#ifdef flv10tables
  	
! 	if (!newclearhandle (ctinitialbuckets * sizeof (hdlhashnode), (Handle *) &hbuckets)) {
  		disposehandle (*(Handle *) htable);
  		return (false);
--- 480,486 ----
  	#ifdef flv10tables
  	
! 	logsize = ctinitiallogsize;
! 	
! 	if (!newclearhandle ((1 << logsize) * sizeof (hdlhashnode), (Handle *) &hbuckets)) {
  		disposehandle (*(Handle *) htable);
  		return (false);
***************
*** 484,488 ****
  	(***htable).hbuckets = hbuckets;
  	
! 	(***htable).ctbuckets = ctinitialbuckets;
  	
  	#endif
--- 489,495 ----
  	(***htable).hbuckets = hbuckets;
  	
! 	(***htable).logsize = logsize;
! 	
! 	(***htable).bucketmask = (1 << logsize) - 1;
  	
  	#endif
***************
*** 923,927 ****
  	register hdlhashnode nomad, nextnomad;
  	register short i;
! 	short ctdisposed = 0;
  	bigstring bs;
  	
--- 930,934 ----
  	register hdlhashnode nomad, nextnomad;
  	register short i;
! 	unsigned long ctdisposed = 0;
  	bigstring bs;
  	
***************
*** 959,962 ****
--- 966,973 ----
  	
  	dirtyhashtable (ht);
+ 	
+ #ifdef flv10tables
+ 	(**ht).ctnodes -= ctdisposed;
+ #endif	
  
  	return (ctdisposed); 
***************
*** 1015,1041 ****
  	
  	smashhashtable (ht, fldisk, false);
- 	/*
- 	for (i = 0; i < ctbuckets; i++) {
- 		
- 		nomad = (**ht).hashbucket [i];
- 		
- 		(**ht).hashbucket [i] = nil; /%disconnect list so table is valid during disposal%/
- 		
- 		while (nomad != nil) {
- 			
- 			/%
- 			boolean fldisposevalue;
- 			
- 			fldisposevalue = (!(**ht).fllocaltable) || ((**nomad).val.valuetype != codevaluetype);
- 			%/
- 			
- 			nextnomad = (**nomad).hashlink;
- 			
- 			disposehashnode (nomad, true /%fldisposevalue%/, fldisk);
- 			
- 			nomad = nextnomad;
- 			}
- 		}
- 	*/
  	
  #ifdef fltracklocaladdresses
--- 1026,1029 ----
***************
*** 1214,1218 ****
  	assert ((**hn).hashval == hashfunction ((**hn).hashkey));
  	
! 	ixbucket = (**hn).hashval % (**ht).ctbuckets;
  
  #else	
--- 1202,1206 ----
  	assert ((**hn).hashval == hashfunction ((**hn).hashkey));
  	
! 	ixbucket = hashtobucketindex (ht, (**hn).hashval);
  
  #else	
***************
*** 1228,1231 ****
--- 1216,1225 ----
  	(**hn).hashlink = hnext;
  	
+ #ifdef flv10tables
+ 
+ 	(**htable).ctnodes++;
+ 	
+ #endif
+ 
  	return (true);
  	} /*hashlinknode*/
***************
*** 1297,1300 ****
--- 1291,1300 ----
  	else
  		(**prev).hashlink = (**nomad).hashlink;
+ 
+ #ifdef flv10tables
+ 
+ 	(**htable).ctnodes--;
+ 	
+ #endif
  	
  	return (true);
***************
*** 1474,1478 ****
  	
  #ifdef flv10tables
! 	ixbucket = hashfunction (bs) % (**currenthashtable).ctbuckets;
  #else
  	ixbucket = hashfunction (bs);
--- 1474,1478 ----
  	
  #ifdef flv10tables
! 	ixbucket = hashtobucketindex (currenthashtable, hashfunction (bs));
  #else
  	ixbucket = hashfunction (bs);
***************
*** 1507,1512 ****
  
  
! boolean hashunlink (const bigstring bs, hdlhashnode *hnode) {
  	
  	hdlhashnode hprev;
  	register hdlhashnode hn;
--- 1507,1520 ----
  
  
! static boolean hashdeletenode (const bigstring bs, hdlhashnode *hnode) {
! 	
! 	/*
! 	2004-11-11 aradke: hashunlink and hashdelete had a lot of common code,
! 	so we created this static function for them.
  	
+ 	The caller is responsible for setting the tables dirty flag, invoking
+ 	the appropriate callbacks, and disposing of or re-using the node.
+ 	*/
+ 
  	hdlhashnode hprev;
  	register hdlhashnode hn;
***************
*** 1529,1533 ****
  		assert ((**hn).hashval == hashfunction (bs));
  
! 		nthhashbucket (currenthashtable, (**hn).hashval % (**currenthashtable).ctbuckets) = (**hn).hashlink;
  
  #else
--- 1537,1541 ----
  		assert ((**hn).hashval == hashfunction (bs));
  
! 		nthhashbucket (currenthashtable, hashtobucketindex (currenthashtable, (**hn).hashval)) = (**hn).hashlink;
  
  #else
***************
*** 1540,1545 ****
--- 1548,1571 ----
  		(**hprev).hashlink = (**hn).hashlink;
  	
+ #ifdef flv10tables
+ 	(**currenthashtable).ctnodes--;
+ #endif
+ 	
  	hashsorteddelete (hn);
+ 
+ 	return (true);
+ 	} /*hashdeletenode*/
  	
+ 
+ boolean hashunlink (const bigstring bs, hdlhashnode *hnode) {
+ 		
+ 	/*
+ 	2004-11-11 aradke: this is similar enough to hashdelete to warrant
+ 	moving the shared code into a separate static function, hashdeletenode.
+ 	*/
+ 
+ 	if (!hashdeletenode (bs, hnode))
+ 		return (false);
+ 
  	dirtyhashtable (currenthashtable);
  	
***************
*** 1549,1603 ****
  	} /*hashunlink*/
  
- /*
- boolean hashdeletenode (hdlhashnode *hnode) {
- 	
- 	hdlhashnode hprev;
- 	register hdlhashnode hn;
- 	
- 	hashunlinknode (currenthashtable, hnode);
- 	
- 	hashsorteddelete (hnode);
- 	
- 	dirtyhashtable (currenthashtable);
- 	
- 	return (true);
- 	} /%hashdeletenode%/
- */
- 
  
  boolean hashdelete (const bigstring bs, boolean fldisposevalue, boolean fldisk) {
  	
! 	hdlhashnode hnode, hprev;
! 	register hdlhashnode hn;
  	
! 	if (!hashlocate (bs, &hnode, &hprev)) {
  	
! 		langparamerror (cantdeleteerror, bs);
! 		
  		return (false);
- 		}
- 	
- 	hn = hnode; /*copy into register*/
- 	
- 	langsymbolunlinking (currenthashtable, hn);
- 	
- 	if (hprev == nil) {
- 	
- #ifdef flv10tables
- 
- 		assert ((**hn).hashval == hashfunction (bs));
- 
- 		nthhashbucket (currenthashtable, (**hn).hashval % (**currenthashtable).ctbuckets) = (**hn).hashlink;
- 
- #else
- 
- 		nthhashbucket (currenthashtable, hashfunction (bs)) = (**hn).hashlink;
- 
- #endif
- 		}
- 	else 
- 		(**hprev).hashlink = (**hn).hashlink;
- 	
- 	hashsorteddelete (hn);
  	
  	disposehashnode (currenthashtable, hn, fldisposevalue, fldisk);
--- 1575,1590 ----
  	} /*hashunlink*/
  
  
  boolean hashdelete (const bigstring bs, boolean fldisposevalue, boolean fldisk) {
  	
! 	/*
! 	2004-11-11 aradke: this is similar enough to hashunlink to warrant
! 	moving the shared code into a separate static function, hashdeletenode.
! 	*/
  	
! 	hdlhashnode hn;
  	
! 	if (!hashdeletenode (bs, &hn))
  		return (false);
  	
  	disposehashnode (currenthashtable, hn, fldisposevalue, fldisk);
***************
*** 3557,3560 ****
--- 3544,3553 ----
  		
  	*ctitems = ct;
+ 
+ #ifdef flv10tables
+ 
+ 	assert (ct == (**htable).ctnodes);
+ 	
+ #endif
  	
  	return (true);