[frontierkernel-commits] Frontier/Common/source langhash.c,1.4.2.2,1.4.2.3

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

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

Modified Files:
      Tag: New_Tables_Experiment-branch
	langhash.c 
Log Message:
When inserting a node into a hash table and the number of nodes is larger than the number of hash buckets, grow the size of the bucket array by a factor of two.

Index: langhash.c
===================================================================
RCS file: /cvsroot/frontierkernel/Frontier/Common/source/langhash.c,v
retrieving revision 1.4.2.2
retrieving revision 1.4.2.3
diff -C2 -d -r1.4.2.2 -r1.4.2.3
*** langhash.c	11 Nov 2004 13:12:39 -0000	1.4.2.2
--- langhash.c	11 Nov 2004 14:52:59 -0000	1.4.2.3
***************
*** 458,461 ****
--- 458,463 ----
  		#ifdef flv10tables
  		
+ 		/*** FIXME: shrink buckets array to ctinitiallogsize while it's still empty? ***/
+ 		
  		clearhandle ((Handle) hbuckets);
  		
***************
*** 497,500 ****
--- 499,569 ----
  	return (true);
  	} /*newhashtable*/
+ 
+ 
+ #ifdef flv10tables
+ 
+ static unsigned long ctresizedhashtables = 0;
+ 
+ static boolean resizehashtable (hdlhashtable htable, unsigned long newlogsize) {
+ 	
+ 	/*
+ 	2004-11-11 aradke: adjust the size of the hash bucket array of the table.
+ 	allocate a new handle for the array, walk the old array, and re-bucket
+ 	all nodes. Finally, dispose of the old array.
+ 	
+ 	the array can be grown or shrinked. return false only if we run out of memory.
+ 	*/
+ 	
+ 	hdlhashbucketarray hnewbuckets, holdbuckets;
+ 	unsigned long ctoldbuckets, oldlogsize;
+ 	unsigned long ctnewbuckets;
+ 	register unsigned long ix, ixnew, newmask;
+ 	register hdlhashnode nomad, nextnomad;
+ 	
+ 	if (newlogsize < ctinitiallogsize)	
+ 		newlogsize = ctinitiallogsize;
+ 	
+ 	if (newlogsize == oldlogsize)
+ 		return (true);
+ 	
+ 	ctresizedhashtables++;
+ 	
+ 	ctnewbuckets = (1 << newlogsize);
+ 	newmask = ctnewbuckets - 1;
+ 	
+ 	if (!newclearhandle (ctnewbuckets * sizeof(hdlhashnode), (Handle *) &hnewbuckets))
+ 		return (false);
+ 	
+ 	holdbuckets = (**htable).hbuckets;
+ 	oldlogsize = (**htable).logsize;
+ 	ctoldbuckets = 1 << oldlogsize;
+ 	
+ 	assert (gethandlesize ((Handle) holdbuckets) == ctoldbuckets * sizeof(hdlhashnode));
+ 	
+ 	for (ix = 0; ix < ctoldbuckets; ix++) {
+ 		
+ 		for (nomad = (*holdbuckets) [ix]; nomad != nil; nomad = nextnomad) {
+ 			
+ 			ixnew = (**nomad).hashval & newmask;
+ 			
+ 			nextnomad = (**nomad).hashlink;
+ 			
+ 			(**nomad).hashlink = (*hnewbuckets) [ixnew];
+ 			
+ 			(*hnewbuckets) [ixnew] = nomad;
+ 			} /*for*/
+ 
+ 		} /*for*/
+ 	
+ 	disposehandle ((Handle) holdbuckets);
+ 	
+ 	(**htable).hbuckets = hnewbuckets;
+ 	(**htable).logsize = newlogsize;
+ 	(**htable).bucketmask = newmask;
+ 	
+ 	return (true);	
+ 	} /*resizehashtable*/
+ 
+ #endif /*flv10tables*/
  	
  	
***************
*** 1199,1202 ****
--- 1268,1274 ----
  
  #ifdef flv10tables
+ 	
+ 	if ((**htable).ctnodes > (1 << (**htable).logsize)) /*getting full*/
+ 		(void) resizehashtable (htable, (**htable).logsize + 1); /*ignore return value, our callers don't check for it*/
  
  	assert ((**hn).hashval == hashfunction ((**hn).hashkey));