[frontierkernel-commits] Frontier/Common/source arraylist.c,1.1.2.7,1.1.2.8

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

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

Modified Files:
      Tag: New_Tables_Experiment-branch
	arraylist.c 
Log Message:
In listresort, fixed a bug where the function didn't do anything if the caller asked for the first item to be resorted. Added more debugging code for the sorting functions.

Index: arraylist.c
===================================================================
RCS file: /cvsroot/frontierkernel/Frontier/Common/source/Attic/arraylist.c,v
retrieving revision 1.1.2.7
retrieving revision 1.1.2.8
diff -C2 -d -r1.1.2.7 -r1.1.2.8
*** arraylist.c	20 Nov 2004 23:24:44 -0000	1.1.2.7
--- arraylist.c	4 Dec 2004 22:20:43 -0000	1.1.2.8
***************
*** 32,35 ****
--- 32,37 ----
  
  
+ //#define fldebugsorting	1	/*2004-12-04 aradke: for enabling additional checks on sorting functions*/
+ 
  /*
  	Implementation of a simple list type based on an array.
***************
*** 487,491 ****
  	assert (hlist != nil);
  	
! 	return (ex < (**hlist).ctitems);
  	} /*listvalidindex*/
  	
--- 489,493 ----
  	assert (hlist != nil);
  	
! 	return ((0 <= ex) && (ex < (**hlist).ctitems));
  	} /*listvalidindex*/
  	
***************
*** 499,503 ****
  	assert (hlist != nil);
  
! 	assert (ex < (**hlist).ctitems);
  
  	return ((**hlist).item[LIST_EXTERNAL_TO_INTERNAL_INDEX (hlist, ex)]);
--- 501,505 ----
  	assert (hlist != nil);
  
! 	assert (listvalidindex (hlist, ex));
  
  	return ((**hlist).item[LIST_EXTERNAL_TO_INTERNAL_INDEX (hlist, ex)]);
***************
*** 513,517 ****
  	assert (hlist != nil);
  
! 	assert (ex < (**hlist).ctitems);
  
  	(**hlist).item[LIST_EXTERNAL_TO_INTERNAL_INDEX (hlist, ex)] = hdata;
--- 515,519 ----
  	assert (hlist != nil);
  
! 	assert (listvalidindex (hlist, ex));
  
  	(**hlist).item[LIST_EXTERNAL_TO_INTERNAL_INDEX (hlist, ex)] = hdata;
***************
*** 740,743 ****
--- 742,747 ----
  	/*
  	insert handle at position ex, moving current item ex out of the way to the right
+ 	
+ 	2004-12-04 aradke: to clarify, the new item will be at position ex when we're done.
  	*/
  	
***************
*** 816,819 ****
--- 820,828 ----
  	deleting it from the list, and re-inserting it at ixdest, except we
  	move as few other handles around as possible.
+ 	
+ 	2004-12-04 aradke: clarification and bug fix, before we start moving stuff
+ 	around, the item is at position exsrc. when we are done moving, the item
+ 	ends up at position exdest, whether exsrc is to the left or to the right
+ 	of exdest. if exsrc is equal to exdest, there's nothing to do.
  	*/
  	
***************
*** 846,865 ****
  		if (exsrc < exdest) {
  			
  			rotateright (hlist, LIST_EXTERNAL_TO_INTERNAL_INDEX (hlist, 0), exsrc);
  
! 			rotateright (hlist, LIST_EXTERNAL_TO_INTERNAL_INDEX (hlist, exdest), (**hlist).ctitems - exdest);
! 
! 			if ((**hlist).ix_offset == (**hlist).ix_mask) /*first rotate moved first item to right*/
  				(**hlist).ix_offset = 0; /*wrap around*/
  			else
  				(**hlist).ix_offset++;
  			}
  		else {
  			
! 			rotateleft (hlist, LIST_EXTERNAL_TO_INTERNAL_INDEX (hlist, 0), exdest + 1);
! 
! 			rotateleft (hlist, LIST_EXTERNAL_TO_INTERNAL_INDEX (hlist, exsrc + 1), (**hlist).ctitems - exdest - 1);
  		
! 			if ((**hlist).ix_offset == 0) /*first rotate moved first item to left*/
  				(**hlist).ix_offset = (**hlist).ix_mask; /*wrap around*/
  			else
--- 855,878 ----
  		if (exsrc < exdest) {
  			
+ 			/*close gap at exsrc first*/
  			rotateright (hlist, LIST_EXTERNAL_TO_INTERNAL_INDEX (hlist, 0), exsrc);
  
! 			if ((**hlist).ix_offset == (**hlist).ix_mask) /*rotatation moved first item to right, adjust offset*/
  				(**hlist).ix_offset = 0; /*wrap around*/
  			else
  				(**hlist).ix_offset++;
+ 			
+ 			/*open new gap at exdest*/
+ 			rotateright (hlist, LIST_EXTERNAL_TO_INTERNAL_INDEX (hlist, exdest), ((**hlist).ctitems - 1) - exdest);
  			}
  		else {
  			
! 			/*close gap at exsrc first*/
! 			rotateleft (hlist, LIST_EXTERNAL_TO_INTERNAL_INDEX (hlist, exsrc + 1), ((**hlist).ctitems - 1) - exsrc);
! 			
! 			/*open new gap at exdest*/
! 			rotateleft (hlist, LIST_EXTERNAL_TO_INTERNAL_INDEX (hlist, 0), exdest);
  		
! 			if ((**hlist).ix_offset == 0) /*rotatation moved first item to left, adjust offset*/
  				(**hlist).ix_offset = (**hlist).ix_mask; /*wrap around*/
  			else
***************
*** 867,871 ****
  			}
  		}
! 		
  	listset (hlist, exdest, hdata);
  	} /*listmove*/
--- 880,884 ----
  			}
  		}
! 
  	listset (hlist, exdest, hdata);
  	} /*listmove*/
***************
*** 934,937 ****
--- 947,994 ----
  
  
+ #ifdef fldebugsorting
+ 
+ static boolean listcheckpartialsortorder (hdllist hlist, long ixmin, long ixmax, int (*comparefunc)(const void *, const void *)) {
+ 	
+ 	/*
+ 	determine whether the given part of the list is sorted according to the given comparefunc
+ 	
+ 	the caller is responsible for locking hlist if comparefunc requires it
+ 	*/
+ 	
+ 	long k = ixmin;
+ 	long kmax = ixmax;
+ 	Handle h1, h2;
+ 	
+ 	while (k < kmax) {
+ 		
+ 		h1 = listget (hlist, k);
+ 		
+ 		++k;
+ 		
+ 		h2 = listget (hlist, k);
+ 
+ 		if ((*comparefunc) (&h1, &h2) > 0)
+ 			return (false);
+ 		} /*for*/
+ 	
+ 	return (true);
+ 	} /*listcheckpartialsortorder*/
+ 
+ 
+ static boolean listchecksortorder (hdllist hlist, int (*comparefunc)(const void *, const void *)) {
+ 	
+ 	/*
+ 	determine whether the list is sorted according to the given comparefunc
+ 	
+ 	the caller is responsible for locking hlist if comparefunc requires it
+ 	*/
+ 	
+ 	return (listcheckpartialsortorder (hlist, 0, listcount (hlist) - 1, comparefunc));
+ 	} /*listchecksortorder*/
+ 
+ #endif
+ 
+ 
  static boolean runbinarysearch (hdllist hlist, Handle hdata,
  		long ixmin, long ixmax,
***************
*** 962,965 ****
--- 1019,1026 ----
  	assert (ixmax < (**hlist).ix_offset + (**hlist).ctitems);
  	
+ 	#ifdef fldebugsorting
+ 		assert (listcheckpartialsortorder (hlist, ixmin, ixmax, comparefunc));
+ 	#endif
+ 	
  	while (ixmin <= ixmax) {
  	
***************
*** 1226,1238 ****
  	into the proper slot. Assume that the rest of the list is still
  	sorted properly.
  	*/
  	
! 	long exdest, ixdest;
  	int resleft = 0;
  	int resright = 0;
  	
  	assert (hlist != nil);
  	
! 	assert (exsrc < (**hlist).ctitems);
  	
  	if ((**hlist).ctitems < 2)
--- 1287,1303 ----
  	into the proper slot. Assume that the rest of the list is still
  	sorted properly.
+ 	
+ 	2004-12-04 aradke: fixed a bug where the first item in the list
+ 	would never get resorted. [reported by Jeff Imig]
  	*/
  	
! 	long exdest;
  	int resleft = 0;
  	int resright = 0;
+ 	Handle hdata;
  	
  	assert (hlist != nil);
  	
! 	assert (listvalidindex (hlist, exsrc));
  	
  	if ((**hlist).ctitems < 2)
***************
*** 1240,1282 ****
  	
  	lockhandle ((Handle) hlist);
! 	
  	if (exsrc > 0) { /*compare with left neighbour*/
  		
! 		resleft = (*comparefunc) (&((**hlist).item[LIST_EXTERNAL_TO_INTERNAL_INDEX (hlist, exsrc - 1)]),
! 									&((**hlist).item[LIST_EXTERNAL_TO_INTERNAL_INDEX (hlist, exsrc)]));
  		}
! 	
  	if ((resleft < 0) && (exsrc < (**hlist).ctitems - 1)) { /*compare with right neighbour*/
  		
! 		resright = (*comparefunc) (&((**hlist).item[LIST_EXTERNAL_TO_INTERNAL_INDEX (hlist, exsrc)]),
! 									&((**hlist).item[LIST_EXTERNAL_TO_INTERNAL_INDEX (hlist, exsrc + 1)]));
  		}
  	
- 	ixdest = (**hlist).ix_offset + exsrc; /*default value*/
- 	
  	if (resleft > 0) { /*left neighbour is greater, search partition on left*/
! 	
! 		runbinarysearch (hlist, (**hlist).item[LIST_EXTERNAL_TO_INTERNAL_INDEX (hlist, exsrc)],
! 							(**hlist).ix_offset,
! 							(**hlist).ix_offset + exsrc - 1,
  							&ixdest, comparefunc);
  		}
  	else if (resright > 0) { /*right neighbour is less, search partition on right*/
  	
! 		runbinarysearch (hlist, (**hlist).item[LIST_EXTERNAL_TO_INTERNAL_INDEX (hlist, exsrc)],
! 							(**hlist).ix_offset + exsrc + 1,
! 							(**hlist).ix_offset + (**hlist).ctitems - 1,
  							&ixdest, comparefunc);
  		}
! 	
! 	exdest = ixdest - (**hlist).ix_offset;
! 	
! 	assert (((resleft > 0) && (exdest < exsrc))
! 				|| ((resright > 0) && (exdest > exsrc))
! 				|| ((resleft <= 0) && (resright <= 0) && (exdest == exsrc)));
! 	
! 	listmove (hlist, exsrc, exdest);
  	
  	unlockhandle ((Handle) hlist);
  	} /*listresort*/
- 
--- 1305,1358 ----
  	
  	lockhandle ((Handle) hlist);
! 		
! 	hdata = (**hlist).item[LIST_EXTERNAL_TO_INTERNAL_INDEX (hlist, exsrc)];
! 
  	if (exsrc > 0) { /*compare with left neighbour*/
  		
! 		resleft = (*comparefunc) (&((**hlist).item[LIST_EXTERNAL_TO_INTERNAL_INDEX (hlist, exsrc - 1)]), &hdata);
  		}
! 	else
! 		resleft = -1; /*2004-12-04 aradke: make sure we compare with right neighbour if its the first item*/
! 		
  	if ((resleft < 0) && (exsrc < (**hlist).ctitems - 1)) { /*compare with right neighbour*/
  		
! 		resright = (*comparefunc) (&hdata, &((**hlist).item[LIST_EXTERNAL_TO_INTERNAL_INDEX (hlist, exsrc + 1)]));
  		}
  	
  	if (resleft > 0) { /*left neighbour is greater, search partition on left*/
! 		
! 		long ixdest;
! 		
! 		runbinarysearch (hlist, hdata,
! 							(**hlist).ix_offset, (**hlist).ix_offset + exsrc - 1,
  							&ixdest, comparefunc);
+ 
+ 		exdest = ixdest - (**hlist).ix_offset;
+ 		
+ 		assert (exdest < exsrc);
+ 
+ 		listmove (hlist, exsrc, exdest);
  		}
  	else if (resright > 0) { /*right neighbour is less, search partition on right*/
+ 		
+ 		long ixdest;
  	
! 		runbinarysearch (hlist, hdata,
! 							(**hlist).ix_offset + exsrc + 1, (**hlist).ix_offset + (**hlist).ctitems - 1,
  							&ixdest, comparefunc);
+ 
+ 		exdest = ixdest - (**hlist).ix_offset;
+ 		
+ 		assert (exsrc + 1 < exdest);
+ 		
+ 		exdest--; /*adjust for exsrc being to the left of exdest*/
+ 
+ 		listmove (hlist, exsrc, exdest);
  		}
! 
! 	#ifdef fldebugsorting
! 		assert (listchecksortorder (hlist, comparefunc));
! 	#endif
  	
  	unlockhandle ((Handle) hlist);
  	} /*listresort*/