From 21777acd684e9d74ad8847413ff2df0e418b07bd Mon Sep 17 00:00:00 2001
From: Raymond Hettinger <python@rcn.com>
Date: Sat, 2 Feb 2013 09:56:08 -0800
Subject: [PATCH] Issue 16398: Use memcpy() in deque.rotate().

---
 Modules/_collectionsmodule.c | 110 +++++++++++++++++++----------------
 1 file changed, 60 insertions(+), 50 deletions(-)

diff --git a/Modules/_collectionsmodule.c b/Modules/_collectionsmodule.c
index 45b4f74bf9..e0c6f0c954 100644
--- a/Modules/_collectionsmodule.c
+++ b/Modules/_collectionsmodule.c
@@ -413,9 +413,8 @@ deque_inplace_concat(dequeobject *deque, PyObject *other)
 static int
 _deque_rotate(dequeobject *deque, Py_ssize_t n)
 {
-    Py_ssize_t i, len=deque->len, halflen=(len+1)>>1;
-    PyObject *item;
-    block *prevblock, *leftblock, *rightblock;
+    Py_ssize_t i, m, len=deque->len, halflen=(len+1)>>1;
+    block *prevblock;
 
     if (len <= 1)
         return 0;
@@ -429,64 +428,75 @@ _deque_rotate(dequeobject *deque, Py_ssize_t n)
 
     assert(deque->len > 1);
     deque->state++;
-    leftblock = deque->leftblock;
-    rightblock = deque->rightblock;
-    for (i=0 ; i<n ; i++) {
-        item = rightblock->data[deque->rightindex];
-        assert (item != NULL);
-        deque->rightindex--;
+    for (i=0 ; i<n ; ) {
+        if (deque->leftindex == 0) {
+            block *b = newblock(NULL, deque->leftblock, deque->len);
+            if (b == NULL)
+                return -1;
+            assert(deque->leftblock->leftlink == NULL);
+            deque->leftblock->leftlink = b;
+            deque->leftblock = b;
+            deque->leftindex = BLOCKLEN;
+        }
+        assert(deque->leftindex > 0);
+
+        m = n - i;
+        if (m > deque->rightindex + 1)
+            m = deque->rightindex + 1;
+        if (m > deque->leftindex)
+            m = deque->leftindex;
+        assert (m > 0);
+        memcpy(&deque->leftblock->data[deque->leftindex - m],
+               &deque->rightblock->data[deque->rightindex - m + 1],
+               m * sizeof(PyObject *));
+        deque->rightindex -= m;
+        deque->leftindex -= m;
+        i += m;
+
         if (deque->rightindex == -1) {
-            assert(rightblock != NULL);
-            prevblock = rightblock->leftlink;
-            assert(leftblock != rightblock);
-            freeblock(rightblock);
+            assert(deque->rightblock != NULL);
+            prevblock = deque->rightblock->leftlink;
+            assert(deque->leftblock != deque->rightblock);
+            freeblock(deque->rightblock);
             prevblock->rightlink = NULL;
-            deque->rightblock = rightblock = prevblock;
+            deque->rightblock = prevblock;
             deque->rightindex = BLOCKLEN - 1;
         }
-        if (deque->leftindex == 0) {
-            block *b = newblock(NULL, leftblock, deque->len);
-            if (b == NULL) {
-                deque->len--;
-                Py_DECREF(item);
+    }
+    for (i=0 ; i>n ; ) {
+        if (deque->rightindex == BLOCKLEN - 1) {
+            block *b = newblock(deque->rightblock, NULL, deque->len);
+            if (b == NULL)
                 return -1;
-            }
-            assert(leftblock->leftlink == NULL);
-            leftblock->leftlink = b;
-            deque->leftblock = leftblock = b;
-            deque->leftindex = BLOCKLEN;
+            assert(deque->rightblock->rightlink == NULL);
+            deque->rightblock->rightlink = b;
+            deque->rightblock = b;
+            deque->rightindex = -1;
         }
-        deque->leftindex--;
-        leftblock->data[deque->leftindex] = item;
-    }
-    for (i=0 ; i>n ; i--) {
-        assert(leftblock != NULL);
-        item = leftblock->data[deque->leftindex];
-        assert (item != NULL);
-        deque->leftindex++;
+        assert (deque->rightindex < BLOCKLEN - 1);
+
+        m = i - n;
+        if (m > BLOCKLEN - deque->leftindex)
+            m = BLOCKLEN - deque->leftindex;
+        if (m > BLOCKLEN - 1 - deque->rightindex)
+            m = BLOCKLEN - 1 - deque->rightindex;
+        assert (m > 0);
+        memcpy(&deque->rightblock->data[deque->rightindex + 1],
+               &deque->leftblock->data[deque->leftindex],
+               m * sizeof(PyObject *));
+        deque->leftindex += m;
+        deque->rightindex += m;
+        i -= m;
+
         if (deque->leftindex == BLOCKLEN) {
-            assert(leftblock != rightblock);
-            prevblock = leftblock->rightlink;
-            freeblock(leftblock);
+            assert(deque->leftblock != deque->rightblock);
+            prevblock = deque->leftblock->rightlink;
+            freeblock(deque->leftblock);
             assert(prevblock != NULL);
             prevblock->leftlink = NULL;
-            deque->leftblock = leftblock = prevblock;
+            deque->leftblock = prevblock;
             deque->leftindex = 0;
         }
-        if (deque->rightindex == BLOCKLEN-1) {
-            block *b = newblock(rightblock, NULL, deque->len);
-            if (b == NULL) {
-                deque->len--;
-                Py_DECREF(item);
-                return -1;
-            }
-            assert(rightblock->rightlink == NULL);
-            rightblock->rightlink = b;
-            deque->rightblock = rightblock = b;
-            deque->rightindex = -1;
-        }
-        deque->rightindex++;
-        rightblock->data[deque->rightindex] = item;
     }
     return 0;
 }
-- 
2.40.0