[Python-checkins] r88191 - in python/branches/py3k: Lib/test/test_deque.py Misc/NEWS Modules/_collectionsmodule.c

[raymond.hettinger]

Author: raymond.hettinger
Date: Tue Jan 25 22:32:39 2011
New Revision: 88191

Log:
Issue #11004:  Repair edge case in deque.count().
(Reviewed by Georg Brandl.)

Also made similar changes to deque.reverse() though this wasn't
strictly necessary (the edge case cannot occur with two pointers
moving to meet in the middle).  Making the change in reverse()
was more a matter of future-proofing.



Modified:
   python/branches/py3k/Lib/test/test_deque.py
   python/branches/py3k/Misc/NEWS
   python/branches/py3k/Modules/_collectionsmodule.c

Modified: python/branches/py3k/Lib/test/test_deque.py
==============================================================================
--- python/branches/py3k/Lib/test/test_deque.py	(original)
+++ python/branches/py3k/Lib/test/test_deque.py	Tue Jan 25 22:32:39 2011
@@ -138,6 +138,15 @@
         m.d = d
         self.assertRaises(RuntimeError, d.count, 3)
 
+        # test issue11004
+        # block advance failed after rotation aligned elements on right side of block
+        d = deque([None]*16)
+        for i in range(len(d)):
+            d.rotate(-1)
+        d.rotate(1)
+        self.assertEqual(d.count(1), 0)
+        self.assertEqual(d.count(None), 16)
+
     def test_comparisons(self):
         d = deque('xabc'); d.popleft()
         for e in [d, deque('abc'), deque('ab'), deque(), list(d)]:

Modified: python/branches/py3k/Misc/NEWS
==============================================================================
--- python/branches/py3k/Misc/NEWS	(original)
+++ python/branches/py3k/Misc/NEWS	Tue Jan 25 22:32:39 2011
@@ -16,6 +16,8 @@
 Library
 -------
 
+- Issue #11004: Repaired edge case in deque.count().
+
 - Issue #10974: IDLE no longer crashes if its recent files list includes files
   with non-ASCII characters in their path names.
 

Modified: python/branches/py3k/Modules/_collectionsmodule.c
==============================================================================
--- python/branches/py3k/Modules/_collectionsmodule.c	(original)
+++ python/branches/py3k/Modules/_collectionsmodule.c	Tue Jan 25 22:32:39 2011
@@ -485,7 +485,8 @@
         /* Advance left block/index pair */
         leftindex++;
         if (leftindex == BLOCKLEN) {
-            assert (leftblock->rightlink != NULL);
+            if (leftblock->rightlink == NULL)
+                break;
             leftblock = leftblock->rightlink;
             leftindex = 0;
         }
@@ -493,7 +494,8 @@
         /* Step backwards with the right block/index pair */
         rightindex--;
         if (rightindex == -1) {
-            assert (rightblock->leftlink != NULL);
+            if (rightblock->leftlink == NULL)
+                break;
             rightblock = rightblock->leftlink;
             rightindex = BLOCKLEN - 1;
         }
@@ -509,7 +511,7 @@
 {
     block *leftblock = deque->leftblock;
     Py_ssize_t leftindex = deque->leftindex;
-    Py_ssize_t n = (deque->len);
+    Py_ssize_t n = deque->len;
     Py_ssize_t i;
     Py_ssize_t count = 0;
     PyObject *item;
@@ -533,7 +535,8 @@
         /* Advance left block/index pair */
         leftindex++;
         if (leftindex == BLOCKLEN) {
-            assert (leftblock->rightlink != NULL);
+            if (leftblock->rightlink == NULL)  /* can occur when i==n-1 */
+                break;
             leftblock = leftblock->rightlink;
             leftindex = 0;
         }