[Python-checkins] python/dist/src/Objects listobject.c,2.125,2.126

[tim_one@users.sourceforge.net]

Update of /cvsroot/python/python/dist/src/Objects
In directory usw-pr-cvs1:/tmp/cvs-serv31227/python/Objects

Modified Files:
	listobject.c 
Log Message:
binarysort() cleanup:  Documented the key invariants, explained why they
imply this is a stable sort, and added some asserts.


Index: listobject.c
===================================================================
RCS file: /cvsroot/python/python/dist/src/Objects/listobject.c,v
retrieving revision 2.125
retrieving revision 2.126
diff -C2 -d -r2.125 -r2.126
*** listobject.c	19 Jul 2002 04:04:16 -0000	2.125
--- listobject.c	19 Jul 2002 06:12:32 -0000	2.126
***************
*** 872,875 ****
--- 872,881 ----
  		r = start;
  		pivot = *r;
+ 		/* Invariants:
+ 		 * pivot >= all in [lo, l).
+ 		 * pivot  < all in [r, start).
+ 		 * The second is vacuously true at the start.
+ 		 */
+ 		assert(l < r);
  		do {
  			p = l + ((r - l) >> 1);
***************
*** 877,883 ****
  				r = p;
  			else
! 				l = p + 1;
  		} while (l < r);
! 		/* Pivot should go at l -- slide over to make room.
  		   Caution: using memmove is much slower under MSVC 5;
  		   we're not usually moving many slots. */
--- 883,894 ----
  				r = p;
  			else
! 				l = p+1;
  		} while (l < r);
! 		assert(l == r);
! 		/* The invariants still hold, so pivot >= all in [lo, l) and
! 		   pivot < all in [l, start), so pivot belongs at l.  Note
! 		   that if there are elements equal to pivot, l points to the
! 		   first slot after them -- that's why this sort is stable.
! 		   Slide over to make room.
  		   Caution: using memmove is much slower under MSVC 5;
  		   we're not usually moving many slots. */