[frontierkernel-commits] Frontier/Common/source langhash.c,1.4.2.22,1.4.2.23

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

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

Modified Files:
      Tag: New_Tables_Experiment-branch
	langhash.c 
Log Message:
A disturbing discovery, the sort order is only maintained strictly if the table is sorted by name. If the sort order is set to anything else, we can't use a binary search to locate existing items or appropriate slots for insertion.

Index: langhash.c
===================================================================
RCS file: /cvsroot/frontierkernel/Frontier/Common/source/langhash.c,v
retrieving revision 1.4.2.22
retrieving revision 1.4.2.23
diff -C2 -d -r1.4.2.22 -r1.4.2.23
*** langhash.c	7 Dec 2004 11:17:22 -0000	1.4.2.22
--- langhash.c	15 Dec 2004 20:25:50 -0000	1.4.2.23
***************
*** 1603,1614 ****
  
  static boolean hashsortedinsert (hdlhashnode hnode) {
  
  	#ifdef fltablesortorderisarray
  	
! 	if ((**currenthashtable).sortedlist == nil)
  		return (true);
- 		
- 	return (listsortedinsert ((**currenthashtable).sortedlist, (Handle) hnode, hashgetcomparefunc (currenthashtable)));
  	
  	#else
  
--- 1603,1639 ----
  
  static boolean hashsortedinsert (hdlhashnode hnode) {
+ 	
+ 	/*
+ 	2004-12-15 aradke: a disturbing discovery, the sort order is only maintained strictly
+ 	if the table is sorted by name. if the sort order is set to anything else, we can't
+ 	use a binary search to locate existing items or appropriate slots for insertion.
+ 	emulate previous behaviour when the sort order isn't by name.
+ 	*/
  
  	#ifdef fltablesortorderisarray
  	
! 	hdllist hlist = (**currenthashtable).sortedlist;
! 	hashcomparefunc comparefunc;
! 	long k, kmax;
! 	hdlhashnode nomad;
! 	
! 	if (hlist == nil)
  		return (true);
  	
+ 	if ((**currenthashtable).sortorder == sortbyname)
+ 		return (listsortedinsert (hlist, (Handle) hnode, hashgetcomparefunc (currenthashtable)));
+ 	
+ 	comparefunc = hashgetcomparefunc (currenthashtable);
+ 	
+ 	for (k = 0, kmax = listcount (hlist); k < kmax; k++) {
+ 		
+ 		nomad = (hdlhashnode) listget (hlist, k);
+ 
+ 		if ((*comparefunc) (&hnode, &nomad) < 0)			
+ 			return (listinsert (hlist, k, (Handle) hnode));
+ 		} /*for*/
+ 
+ 	return (listappend (hlist, (Handle) hnode));
+ 
  	#else
  
***************
*** 1671,1680 ****
  static void hashsorteddelete (hdlhashnode hnodedelete) {
  	
  	#ifdef fltablesortorderisarray
  	
! 	if ((**currenthashtable).sortedlist == nil)
  		return;
  	
! 	(void) listsorteddelete ((**currenthashtable).sortedlist, (Handle) hnodedelete, hashgetcomparefunc (currenthashtable));
  	
  	#else
--- 1696,1721 ----
  static void hashsorteddelete (hdlhashnode hnodedelete) {
  	
+ 	/*
+ 	2004-12-15 aradke: see hashsortedinsert
+ 	*/
+ 
  	#ifdef fltablesortorderisarray
  	
! 	hdllist hlist = (**currenthashtable).sortedlist;
! 	long ix;
! 	
! 	if (hlist == nil)
  		return;
  	
! 	if ((**currenthashtable).sortorder == sortbyname) {
! 	
! 		(void) listsorteddelete (hlist, (Handle) hnodedelete, hashgetcomparefunc (currenthashtable));
! 		
! 		return;
! 		}
! 	
! 	if (listlinearsearch (hlist, (Handle) hnodedelete, &ix))
! 
! 		listdelete (hlist, ix);
  	
  	#else
***************
*** 2876,2883 ****
  	2004-11-20 aradke: if a single node is affected, we rely on the caller
  	to determine the index of the node before changing its hash key or value.
  	*/
  	
  	register hdlhashtable ht = htable;
! 
  	if (hresort == nil)
  		return (hashquicksort (ht));
--- 2917,2930 ----
  	2004-11-20 aradke: if a single node is affected, we rely on the caller
  	to determine the index of the node before changing its hash key or value.
+ 
+ 	2004-12-15 aradke: see hashsortedinsert
  	*/
  	
  	register hdlhashtable ht = htable;
! 	#ifdef fltablesortorderisarray
! 		hdllist hlist;
! 		hashcomparefunc comparefunc;
! 	#endif
! 	
  	if (hresort == nil)
  		return (hashquicksort (ht));
***************
*** 2886,2894 ****
  	
  	#ifdef fltablesortorderisarray
  	
! 		assert ((**ht).sortedlist != nil);
  
! 		listresort ((**ht).sortedlist, ix, hashgetcomparefunc (ht));
  		
  	#else
  
--- 2933,2966 ----
  	
  	#ifdef fltablesortorderisarray
+ 		
+ 		hlist = (**ht).sortedlist;
+ 		
+ 		comparefunc = hashgetcomparefunc (currenthashtable);
  	
! 		assert (hlist != nil);
! 		
! 		if ((**ht).sortorder = sortbyname) {
  
! 			listresort (hlist, ix, comparefunc);
! 			}
! 		else {
  		
+ 			hdlhashnode nomad;
+ 			long k, kmax;
+ 			
+ 			for (k = 0, kmax = listcount (hlist); k < kmax; k++) {
+ 				
+ 				nomad = (hdlhashnode) listget (hlist, k);
+ 
+ 				if ((*comparefunc) (&hresort, &nomad) < 0)
+ 					break;
+ 				} /*for*/
+ 			
+ 			if (ix < k) /*adjust for source being to the left of the destination*/
+ 				k--;
+ 
+ 			listmove (hlist, ix, k);
+ 			}
+ 			
  	#else
  
***************
*** 4405,4426 ****
  	is in the list, so we can use the binary search successfully. however, just
  	to be sure we try a linearsearch if the binary search fails.
  	*/
  	
  #ifdef fltablesortorderisarray
  	
  	boolean flfound;
  	
! 	assert ((**htable).sortedlist != nil);
  
! 	pushhashtable (htable); /*for hashcompare*/
! 	
! 	flfound = listbinarysearchexact ((**htable).sortedlist, (Handle) hnode, index, hashgetcomparefunc (htable));
! 	
! 	pophashtable ();
  	
! 	if (flfound)
! 		return (true);
  		
! 	return (listlinearsearch ((**htable).sortedlist, (Handle) hnode, index));
  
  #else
--- 4477,4503 ----
  	is in the list, so we can use the binary search successfully. however, just
  	to be sure we try a linearsearch if the binary search fails.
+ 
+ 	2004-12-15 aradke: see hashsortedinsert, binary search only works with sort by name.
  	*/
  	
  #ifdef fltablesortorderisarray
  	
+ 	hdllist hlist = (**htable).sortedlist;
  	boolean flfound;
  	
! 	assert (hlist != nil);
  
! 	if ((**htable).sortorder == sortbyname) {
  	
! 		pushhashtable (htable); /*for hashcompare*/
  		
! 		flfound = listbinarysearchexact (hlist, (Handle) hnode, index, hashgetcomparefunc (htable));
! 		
! 		pophashtable ();
! 		}	
! 	else
! 		flfound = listlinearsearch (hlist, (Handle) hnode, index);
! 	
! 	return (flfound);
  
  #else