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

2002年7月18日 23:12:35 -0700

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. */