[frontierkernel-commits] Frontier/Common/source tableops.c,1.3,1.3.2.1 langexternal.c,1.3,1.3.2.1 la

SourceForge Headquarters 1320 Columbia Street Suite 310 San Diego, CA 92101 +1 (858) 422-6466

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

Modified Files:
      Tag: New_Tables_Experiment-branch
	tableops.c langexternal.c langhash.c langvalue.c 
	tablevalidate.c 
Log Message:
First step towards an overhaul of the hashtable type: Switched to a hash function with a wider spread. Prepare for allocating and resizing the hash bucket array dynamically by caching the hash function result in each hash node and moving the hash bucket array out of the hash node handle and into its own handle. All significant changes ifdef'd for flv10tables, to be defined in frontierdefs.h.

Index: tablevalidate.c
===================================================================
RCS file: /cvsroot/frontierkernel/Frontier/Common/source/tablevalidate.c,v
retrieving revision 1.3
retrieving revision 1.3.2.1
diff -C2 -d -r1.3 -r1.3.2.1
*** tablevalidate.c	31 Oct 2004 20:41:10 -0000	1.3
--- tablevalidate.c	10 Nov 2004 16:19:07 -0000	1.3.2.1
***************
*** 96,102 ****
  		}

! 	for (i = 0; i < ctbuckets; i++) {

! 		x = (**ht).hashbucket [i];

  		while (x != nil) { /*chain through the hash list*/
--- 96,102 ----
  		}

! 	for (i = 0; i < gethashbucketcount (ht); i++) {

! 		x = nthhashbucket (ht, i);

  		while (x != nil) { /*chain through the hash list*/
***************
*** 116,120 ****
  				return (false);
  				}
! 			
  			if (hashfunction (bs) != i) {

--- 116,137 ----
  				return (false);
  				}
! 
! #ifdef flv10tables
! 			if (hashfunction (bs) != (**x).hashval) {
! 				
! 				if (flalert)
! 					shellinternalerror (idbadbucketliststring, "\x1b" "bad hashval in hash node");
! 				
! 				return (false);
! 				}
! 
! 			if (((**x).hashval % (**ht).ctbuckets) != i) {
! 				
! 				if (flalert)
! 					shellinternalerror (idbadbucketliststring, "\x1b" "bad hashval in bucket list");
! 				
! 				return (false);
! 				}
! #else			
  			if (hashfunction (bs) != i) {

***************
*** 124,127 ****
--- 141,145 ----
  				return (false);
  				}
+ #endif

  			if (!gettablevariable ((**x).val, &hvariable, &errcode))

Index: langvalue.c
===================================================================
RCS file: /cvsroot/frontierkernel/Frontier/Common/source/langvalue.c,v
retrieving revision 1.5
retrieving revision 1.5.2.1
diff -C2 -d -r1.5 -r1.5.2.1
*** langvalue.c	31 Oct 2004 21:43:38 -0000	1.5
--- langvalue.c	10 Nov 2004 16:19:06 -0000	1.5.2.1
***************
*** 7609,7615 ****
  	register hdlexternalvariable hv;

! 	for (i = 0; i < ctbuckets; i++) {

! 		x = (**ht).hashbucket [i];

  		while (x != nil) { /*chain through the hash list*/
--- 7609,7615 ----
  	register hdlexternalvariable hv;

! 	for (i = 0; i < gethashbucketcount (ht); i++) {

! 		x = nthhashbucket (ht, i);

  		while (x != nil) { /*chain through the hash list*/

Index: langexternal.c
===================================================================
RCS file: /cvsroot/frontierkernel/Frontier/Common/source/langexternal.c,v
retrieving revision 1.3
retrieving revision 1.3.2.1
diff -C2 -d -r1.3 -r1.3.2.1
*** langexternal.c	31 Oct 2004 21:43:38 -0000	1.3
--- langexternal.c	10 Nov 2004 16:19:05 -0000	1.3.2.1
***************
*** 1516,1522 ****
  		return (true);

! 	for (i = 0; i < ctbuckets; i++) {

! 		x = (**ht).hashbucket [i];

  		bucketCount = 0;
--- 1516,1522 ----
  		return (true);

! 	for (i = 0; i < gethashbucketcount (ht); i++) {

! 		x = nthhashbucket (ht, i);

  		bucketCount = 0;

Index: tableops.c
===================================================================
RCS file: /cvsroot/frontierkernel/Frontier/Common/source/tableops.c,v
retrieving revision 1.3
retrieving revision 1.3.2.1
diff -C2 -d -r1.3 -r1.3.2.1
*** tableops.c	31 Oct 2004 20:41:10 -0000	1.3
--- tableops.c	10 Nov 2004 16:19:05 -0000	1.3.2.1
***************
*** 429,435 ****
  	register hdlexternalvariable hv = nil;

! 	for (i = 0; i < ctbuckets; i++) {

! 		x = (**ht).hashbucket [i];

  		while (x != nil) { /*chain through the hash list*/
--- 429,435 ----
  	register hdlexternalvariable hv = nil;

! 	for (i = 0; i < gethashbucketcount (ht); i++) {

! 		x = nthhashbucket (ht, i);

  		while (x != nil) { /*chain through the hash list*/
***************
*** 715,721 ****
  		}

! 	for (i = 0; i < ctbuckets; i++) {

! 		x = (**ht).hashbucket [i];

  		while (x != nil) { /*chain through the hash list*/
--- 715,721 ----
  		}

! 	for (i = 0; i < gethashbucketcount (ht); i++) {

! 		x = nthhashbucket (ht, i);

  		while (x != nil) { /*chain through the hash list*/

Index: langhash.c
===================================================================
RCS file: /cvsroot/frontierkernel/Frontier/Common/source/langhash.c,v
retrieving revision 1.4
retrieving revision 1.4.2.1
diff -C2 -d -r1.4 -r1.4.2.1
*** langhash.c	1 Nov 2004 11:50:17 -0000	1.4
--- langhash.c	10 Nov 2004 16:19:05 -0000	1.4.2.1
***************
*** 411,414 ****
--- 411,420 ----
  	*/

+ 	#ifdef flv10tables
+ 	
+ 	hdlhashbucketarray hbuckets;
+ 	
+ 	#endif
+ 	
  	if (hmagictable != nil) {

***************
*** 431,434 ****
--- 437,450 ----
  		short ct;

+ 		#ifdef flv10tables
+ 		
+ 		unsigned long ctbuckets = (**ht).ctbuckets;
+ 		
+ 		hbuckets = (**ht).hbuckets;
+ 		
+ 		assert (gethandlesize ((Handle) hbuckets) / sizeof (hdlhashnode) == ctbuckets);
+ 
+ 		#endif
+ 		
  		hfirstfreetable = (**hfirstfreetable).prevhashtable;

***************
*** 439,442 ****
--- 455,468 ----
  		(**ht).cttmpstack = ct;

+ 		#ifdef flv10tables
+ 		
+ 		clearhandle ((Handle) hbuckets);
+ 		
+ 		(**ht).hbuckets = hbuckets;
+ 		
+ 		(**ht).ctbuckets = ctbuckets;
+ 		
+ 		#endif
+ 		
  		*htable = ht;

***************
*** 448,452 ****
--- 474,491 ----

  	(***htable).timecreated = timenow ();
+ 
+ 	#ifdef flv10tables
+ 	
+ 	if (!newclearhandle (ctinitialbuckets * sizeof (hdlhashnode), (Handle *) &hbuckets)) {
+ 		disposehandle (*(Handle *) htable);
+ 		return (false);
+ 		}

+ 	(***htable).hbuckets = hbuckets;
+ 	
+ 	(***htable).ctbuckets = ctinitialbuckets;
+ 	
+ 	#endif
+ 
  	return (true);
  	} /*newhashtable*/
***************
*** 892,900 ****
  	(**ht).hfirstsort = nil;	/*disconnect now so table is valid during disposal*/

! 	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) {
--- 931,939 ----
  	(**ht).hfirstsort = nil;	/*disconnect now so table is valid during disposal*/

! 	for (i = 0; i < gethashbucketcount (ht); i++) {

! 		nomad = nthhashbucket (ht, i);

! 		nthhashbucket (ht, i) = nil; /*disconnect list so table is valid during disposal*/

  		while (nomad != nil) {
***************
*** 1016,1045 ****

! short hashfunction (const bigstring bs) {
! 	
! 	/*
! 		3.0.4b8 dmb: need to make locals unsigned to protect against ctype's int's
! 	*/

! //	register unsigned short c;
! 	register unsigned short len;
! //	register ptrstring p = (ptrstring) bs;
! 	register unsigned short val;

! 	len = stringlength (bs);
! 	
! 	if (len == 0)
! 		return (0);
! 	
! //	c = p [1];
! 	
! 	val = getlower(getstringcharacter(bs,0));
! 	
! //	c = p [len];
! 	
! 	val += getlower(getstringcharacter(bs,len-1));
! 	
! 	return (val % ctbuckets);
! 	} /*hashfunction*/

--- 1055,1119 ----

! #ifdef flv10tables

! 	unsigned long hashfunction (const bigstring bs) {
! 		
! 		/*
! 		2004-11-10 aradke: New hash function with wider spread, inspired by K&R "Programming in C".
! 		
! 		We loop from the end to the beginning of the string so that the multiplication
! 		will magnify the difference between two strings that differ only in the last
! 		position, e.g. consecutively numbered items.
! 		
! 		The return value is unsigned long because we expect to switch to a variable number
! 		of buckets on a per-table basis soon. When we get there, we will switch to returning
! 		hashval un-mod-ed, so it can be saved with the hashkey in the node and be re-used
! 		for when we need to re-bucket all items.
! 		*/

! 		register unsigned long hashval = 0;
! 		register ptrstring pend;
! 		register ptrstring p;
! 		
! 		pend = (ptrstring) bs;
! 		
! 		p = pend + stringlength (bs);
! 		
! 		while (p > pend)
! 			hashval = 31 * hashval + (unsigned long) getlower (*p--);
! 
! 		return (hashval);
! 		} /*hashfunction*/
! 
! #else
! 
! 	short hashfunction (const bigstring bs) {
! 		
! 		/*
! 			3.0.4b8 dmb: need to make locals unsigned to protect against ctype's int's
! 		*/
! 
! 	//	register unsigned short c;
! 		register unsigned short len;
! 	//	register ptrstring p = (ptrstring) bs;
! 		register unsigned short val;
! 
! 		len = stringlength (bs);
! 		
! 		if (len == 0)
! 			return (0);
! 		
! 	//	c = p [1];
! 		
! 		val = getlower(getstringcharacter(bs,0));
! 		
! 	//	c = p [len];
! 		
! 		val += getlower(getstringcharacter(bs,len-1));
! 		
! 		return (val % ctbuckets);
! 		} /*hashfunction*/
! 
! #endif /*flv10tables*/

***************
*** 1135,1144 ****
  	register short ixbucket;
  	register hdlhashnode hnext;

  	ixbucket = hashfunction ((**hn).hashkey);

! 	hnext = (**ht).hashbucket [ixbucket];

! 	(**ht).hashbucket [ixbucket] = hnode; /*link new guy at head of list*/

  	(**hn).hashlink = hnext;
--- 1209,1228 ----
  	register short ixbucket;
  	register hdlhashnode hnext;
+ 
+ #ifdef flv10tables
+ 
+ 	assert ((**hn).hashval == hashfunction ((**hn).hashkey));

+ 	ixbucket = (**hn).hashval % (**ht).ctbuckets;
+ 
+ #else	
+ 
  	ixbucket = hashfunction ((**hn).hashkey);
+ 
+ #endif

! 	hnext = nthhashbucket (ht, ixbucket);

! 	nthhashbucket (ht, ixbucket) = hnode; /*link new guy at head of list*/

  	(**hn).hashlink = hnext;
***************
*** 1188,1194 ****
  	register hdlhashnode nomad, prev;

! 	for (i = 0; i < ctbuckets; i++) {

! 		nomad = (**htable).hashbucket [i];

  		prev = nil;
--- 1272,1278 ----
  	register hdlhashnode nomad, prev;

! 	for (i = 0; i < gethashbucketcount (htable); i++) {

! 		nomad = nthhashbucket (htable, i);

  		prev = nil;
***************
*** 1210,1214 ****

  	if (prev == nil) 
! 		(**htable).hashbucket [i] = (**nomad).hashlink;
  	else
  		(**prev).hashlink = (**nomad).hashlink;
--- 1294,1298 ----

  	if (prev == nil) 
! 		nthhashbucket (htable, i) = (**nomad).hashlink;
  	else
  		(**prev).hashlink = (**nomad).hashlink;
***************
*** 1225,1230 ****
  	hashunlinknode (htable, hnode);

! 	copystring (bs, (**hnode).hashkey);

  	hashlinknode (htable, hnode);

--- 1309,1318 ----
  	hashunlinknode (htable, hnode);

! #ifdef flv10tables
! 	(**hnode).hashval = hashfunction (bs); /*keep in sync with hashkey*/
! #endif

+ 	copystring (bs, (**hnode).hashkey);
+ 
  	hashlinknode (htable, hnode);

***************
*** 1242,1245 ****
--- 1330,1337 ----
  		return (false);

+ #ifdef flv10tables
+ 	(***hnode).hashval = hashfunction (bskey);
+ #endif
+ 	
  	copystring (bskey, (***hnode).hashkey);

***************
*** 1381,1385 ****
--- 1473,1481 ----
  	*/

+ #ifdef flv10tables
+ 	ixbucket = hashfunction (bs) % (**currenthashtable).ctbuckets;
+ #else
  	ixbucket = hashfunction (bs);
+ #endif

  	//assert (currenthashtable != nil);
***************
*** 1387,1391 ****
  	//assert (validhandle ((Handle) currenthashtable));

! 	nomad = (**currenthashtable).hashbucket [ixbucket];

  	nomadprev = nil;
--- 1483,1487 ----
  	//assert (validhandle ((Handle) currenthashtable));

! 	nomad = nthhashbucket (currenthashtable, ixbucket);

  	nomadprev = nil;
***************
*** 1427,1432 ****
  	langsymbolunlinking (currenthashtable, hn);

! 	if (hprev == nil) 
! 		(**currenthashtable).hashbucket [hashfunction (bs)] = (**hn).hashlink;
  	else 
  		(**hprev).hashlink = (**hn).hashlink;
--- 1523,1540 ----
  	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;
***************
*** 1474,1479 ****
  	langsymbolunlinking (currenthashtable, hn);

! 	if (hprev == nil) 
! 		(**currenthashtable).hashbucket [hashfunction (bs)] = (**hn).hashlink;
  	else 
  		(**hprev).hashlink = (**hn).hashlink;
--- 1582,1599 ----
  	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;
***************
*** 1981,1987 ****
  	register short i;

! 	for (i = 0; i < ctbuckets; i++) {

! 		x = (**htable).hashbucket [i];

  		while (x != nil) {
--- 2101,2107 ----
  	register short i;

! 	for (i = 0; i < gethashbucketcount (htable); i++) {

! 		x = nthhashbucket (htable, i);

  		while (x != nil) {
***************
*** 2129,2135 ****
  	register short i;

! 	for (i = 0; i < ctbuckets; i++) {

! 		nomad = (**htable).hashbucket [i];

  		while (nomad != nil) {
--- 2249,2255 ----
  	register short i;

! 	for (i = 0; i < gethashbucketcount (htable); i++) {

! 		nomad = nthhashbucket (htable, i);

  		while (nomad != nil) {

[frontierkernel-commits] Frontier/Common/source tableops.c,1.3,1.3.2.1 langexternal.c,1.3,1.3.2.1 la

[frontierkernel-commits] Frontier/Common/source tableops.c,1.3,1.3.2.1 langexternal.c,1.3,1.3.2.1 langhash.c,1.4,1.4.2.1 langvalue.c,1.5,1.5.2.1 tablevalidate.c,1.3,1.3.2.1