[Python-checkins] bpo-25246: Optimize deque.remove() (GH-23898)
rhettinger
webhook-mailer at python.org
Wed Dec 23 14:45:20 EST 2020
https://github.com/python/cpython/commit/6b1ac809b9718a369aea67b99077cdd682be2238
commit: 6b1ac809b9718a369aea67b99077cdd682be2238
branch: master
author: Raymond Hettinger <rhettinger at users.noreply.github.com>
committer: rhettinger <rhettinger at users.noreply.github.com>
date: 2020-12-23T11:45:06-08:00
summary:
bpo-25246: Optimize deque.remove() (GH-23898)
files:
A Misc/NEWS.d/next/Library/2020-12-22-13-16-43.bpo-25246.GhhCTl.rst
M Modules/_collectionsmodule.c
diff --git a/Misc/NEWS.d/next/Library/2020-12-22-13-16-43.bpo-25246.GhhCTl.rst b/Misc/NEWS.d/next/Library/2020-12-22-13-16-43.bpo-25246.GhhCTl.rst
new file mode 100644
index 0000000000000..258bb12ff8beb
--- /dev/null
+++ b/Misc/NEWS.d/next/Library/2020-12-22-13-16-43.bpo-25246.GhhCTl.rst
@@ -0,0 +1 @@
+Optimized :meth:`collections.deque.remove`.
diff --git a/Modules/_collectionsmodule.c b/Modules/_collectionsmodule.c
index 157875067635a..90bafb0ea86d9 100644
--- a/Modules/_collectionsmodule.c
+++ b/Modules/_collectionsmodule.c
@@ -1128,38 +1128,6 @@ deque_insert(dequeobject *deque, PyObject *const *args, Py_ssize_t nargs)
PyDoc_STRVAR(insert_doc,
"D.insert(index, object) -- insert object before index");
-static PyObject *
-deque_remove(dequeobject *deque, PyObject *value)
-{
- Py_ssize_t i, n=Py_SIZE(deque);
-
- for (i=0 ; i<n ; i++) {
- PyObject *item = deque->leftblock->data[deque->leftindex];
- int cmp = PyObject_RichCompareBool(item, value, Py_EQ);
-
- if (Py_SIZE(deque) != n) {
- PyErr_SetString(PyExc_IndexError,
- "deque mutated during remove().");
- return NULL;
- }
- if (cmp > 0) {
- PyObject *tgt = deque_popleft(deque, NULL);
- assert (tgt != NULL);
- if (_deque_rotate(deque, i))
- return NULL;
- Py_DECREF(tgt);
- Py_RETURN_NONE;
- }
- else if (cmp < 0) {
- _deque_rotate(deque, i);
- return NULL;
- }
- _deque_rotate(deque, -1);
- }
- PyErr_SetString(PyExc_ValueError, "deque.remove(x): x not in deque");
- return NULL;
-}
-
PyDoc_STRVAR(remove_doc,
"D.remove(value) -- remove first occurrence of value.");
@@ -1227,6 +1195,48 @@ deque_del_item(dequeobject *deque, Py_ssize_t i)
return rv;
}
+static PyObject *
+deque_remove(dequeobject *deque, PyObject *value)
+{
+ PyObject *item;
+ block *b = deque->leftblock;
+ Py_ssize_t i, n = Py_SIZE(deque), index = deque->leftindex;
+ size_t start_state = deque->state;
+ int cmp, rv;
+
+ for (i = 0 ; i < n; i++) {
+ item = b->data[index];
+ Py_INCREF(item);
+ cmp = PyObject_RichCompareBool(item, value, Py_EQ);
+ Py_DECREF(item);
+ if (cmp < 0) {
+ return NULL;
+ }
+ if (start_state != deque->state) {
+ PyErr_SetString(PyExc_IndexError,
+ "deque mutated during iteration");
+ return NULL;
+ }
+ if (cmp > 0) {
+ break;
+ }
+ index++;
+ if (index == BLOCKLEN) {
+ b = b->rightlink;
+ index = 0;
+ }
+ }
+ if (i == n) {
+ PyErr_Format(PyExc_ValueError, "%R is not in deque", value);
+ return NULL;
+ }
+ rv = deque_del_item(deque, i);
+ if (rv == -1) {
+ return NULL;
+ }
+ Py_RETURN_NONE;
+}
+
static int
deque_ass_item(dequeobject *deque, Py_ssize_t i, PyObject *v)
{
More information about the Python-checkins
mailing list