From 2cdb6435d6f7c6f1bd2ae935bc6e11d6aa79f4a2 Mon Sep 17 00:00:00 2001
From: Raymond Hettinger <python@rcn.com>
Date: Sat, 12 Jan 2013 00:05:00 -0800
Subject: [PATCH] Issue #16398: Optimize deque.rotate()

---
 Misc/NEWS                    |  3 ++
 Modules/_collectionsmodule.c | 72 +++++++++++++++++++++++++++++-------
 2 files changed, 61 insertions(+), 14 deletions(-)

diff --git a/Misc/NEWS b/Misc/NEWS
index 94cc8ac19f..43cfc64f71 100644
--- a/Misc/NEWS
+++ b/Misc/NEWS
@@ -189,6 +189,9 @@ Library
 - Issue #13899: \A, \Z, and \B now correctly match the A, Z, and B literals
   when used inside character classes (e.g. '[\A]').  Patch by Matthew Barnett.
 
+- Issue #16398: Optimize deque.rotate() so that it only moves pointers
+  and doesn't touch the underlying data with increfs and decrefs.
+
 - Issue #15109: Fix regression in sqlite3's iterdump method where it would
   die with an encoding error if the database contained string values
   containing non-ASCII.  (Regression was introduced by fix for 9750).
diff --git a/Modules/_collectionsmodule.c b/Modules/_collectionsmodule.c
index 242abf2afd..106768a642 100644
--- a/Modules/_collectionsmodule.c
+++ b/Modules/_collectionsmodule.c
@@ -414,9 +414,10 @@ static int
 _deque_rotate(dequeobject *deque, Py_ssize_t n)
 {
     Py_ssize_t i, len=deque->len, halflen=(len+1)>>1;
-    PyObject *item, *rv;
+    PyObject *item;
+    block *prevblock, *leftblock, *rightblock;
 
-    if (len == 0)
+    if (len <= 1)
         return 0;
     if (n > halflen || n < -halflen) {
         n %= len;
@@ -426,23 +427,66 @@ _deque_rotate(dequeobject *deque, Py_ssize_t n)
             n += len;
     }
 
+    assert(deque->len > 1);
+    deque->state++;
+    leftblock = deque->leftblock;
+    rightblock = deque->rightblock;
     for (i=0 ; i<n ; i++) {
-        item = deque_pop(deque, NULL);
+        item = rightblock->data[deque->rightindex];
         assert (item != NULL);
-        rv = deque_appendleft(deque, item);
-        Py_DECREF(item);
-        if (rv == NULL)
-            return -1;
-        Py_DECREF(rv);
+        deque->rightindex--;
+        if (deque->rightindex == -1) {
+            assert(rightblock != NULL);
+            prevblock = rightblock->leftlink;
+            assert(leftblock != rightblock);
+            freeblock(rightblock);
+            prevblock->rightlink = NULL;
+            deque->rightblock = 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);
+                return -1;
+            }
+            assert(leftblock->leftlink == NULL);
+            leftblock->leftlink = b;
+            deque->leftblock = leftblock = b;
+            deque->leftindex = BLOCKLEN;
+        }
+        deque->leftindex--;
+        leftblock->data[deque->leftindex] = item;
     }
     for (i=0 ; i>n ; i--) {
-        item = deque_popleft(deque, NULL);
+        assert(leftblock != NULL);
+        item = leftblock->data[deque->leftindex];
         assert (item != NULL);
-        rv = deque_append(deque, item);
-        Py_DECREF(item);
-        if (rv == NULL)
-            return -1;
-        Py_DECREF(rv);
+        deque->leftindex++;
+        if (deque->leftindex == BLOCKLEN) {
+            assert(leftblock != rightblock);
+            prevblock = leftblock->rightlink;
+            freeblock(leftblock);
+            assert(prevblock != NULL);
+            prevblock->leftlink = NULL;
+            deque->leftblock = 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.50.0