https://hg.python.org/cpython/rev/b75160d24b7b changeset: 95333:b75160d24b7b user: Raymond Hettinger <python@rcn.com> date: Tue Mar 31 08:12:23 2015 -0700 summary: Issue 23793: Add deque support for __add__(), __mul__(), and __imul__(). files: Doc/library/collections.rst | 3 + Lib/test/test_deque.py | 77 +++++++++++++ Misc/NEWS | 1 + Modules/_collectionsmodule.c | 133 +++++++++++++++++++++- 4 files changed, 204 insertions(+), 10 deletions(-) diff --git a/Doc/library/collections.rst b/Doc/library/collections.rst --- a/Doc/library/collections.rst +++ b/Doc/library/collections.rst @@ -526,6 +526,9 @@ access is O(1) at both ends but slows to O(n) in the middle. For fast random access, use lists instead. +Starting in version 3.5, deques support ``__add__()``, ``__mul__()``, +and ``__imul__()``. + Example: .. doctest:: diff --git a/Lib/test/test_deque.py b/Lib/test/test_deque.py --- a/Lib/test/test_deque.py +++ b/Lib/test/test_deque.py @@ -192,6 +192,26 @@ d.extend(d) self.assertEqual(list(d), list('abcdabcd')) + def test_add(self): + d = deque() + e = deque('abc') + f = deque('def') + self.assertEqual(d + d, deque()) + self.assertEqual(e + f, deque('abcdef')) + self.assertEqual(e + e, deque('abcabc')) + self.assertEqual(e + d, deque('abc')) + self.assertEqual(d + e, deque('abc')) + self.assertIsNot(d + d, deque()) + self.assertIsNot(e + d, deque('abc')) + self.assertIsNot(d + e, deque('abc')) + + g = deque('abcdef', maxlen=4) + h = deque('gh') + self.assertEqual(g + h, deque('efgh')) + + with self.assertRaises(TypeError): + deque('abc') + 'def' + def test_iadd(self): d = deque('a') d += 'bcd' @@ -279,6 +299,63 @@ s.insert(i, 'Z') self.assertEqual(list(d), s) + def test_imul(self): + for n in (-10, -1, 0, 1, 2, 10, 1000): + d = deque() + d *= n + self.assertEqual(d, deque()) + self.assertIsNone(d.maxlen) + + for n in (-10, -1, 0, 1, 2, 10, 1000): + d = deque('a') + d *= n + self.assertEqual(d, deque('a' * n)) + self.assertIsNone(d.maxlen) + + for n in (-10, -1, 0, 1, 2, 10, 499, 500, 501, 1000): + d = deque('a', 500) + d *= n + self.assertEqual(d, deque('a' * min(n, 500))) + self.assertEqual(d.maxlen, 500) + + for n in (-10, -1, 0, 1, 2, 10, 1000): + d = deque('abcdef') + d *= n + self.assertEqual(d, deque('abcdef' * n)) + self.assertIsNone(d.maxlen) + + for n in (-10, -1, 0, 1, 2, 10, 499, 500, 501, 1000): + d = deque('abcdef', 500) + d *= n + self.assertEqual(d, deque(('abcdef' * n)[-500:])) + self.assertEqual(d.maxlen, 500) + + def test_mul(self): + d = deque('abc') + self.assertEqual(d * -5, deque()) + self.assertEqual(d * 0, deque()) + self.assertEqual(d * 1, deque('abc')) + self.assertEqual(d * 2, deque('abcabc')) + self.assertEqual(d * 3, deque('abcabcabc')) + self.assertIsNot(d * 1, d) + + self.assertEqual(deque() * 0, deque()) + self.assertEqual(deque() * 1, deque()) + self.assertEqual(deque() * 5, deque()) + + self.assertEqual(-5 * d, deque()) + self.assertEqual(0 * d, deque()) + self.assertEqual(1 * d, deque('abc')) + self.assertEqual(2 * d, deque('abcabc')) + self.assertEqual(3 * d, deque('abcabcabc')) + + d = deque('abc', maxlen=5) + self.assertEqual(d * -5, deque()) + self.assertEqual(d * 0, deque()) + self.assertEqual(d * 1, deque('abc')) + self.assertEqual(d * 2, deque('bcabc')) + self.assertEqual(d * 30, deque('bcabc')) + def test_setitem(self): n = 200 d = deque(range(n)) diff --git a/Misc/NEWS b/Misc/NEWS --- a/Misc/NEWS +++ b/Misc/NEWS @@ -152,6 +152,7 @@ - Issue #23704: collections.deque() objects now support methods for index(), insert(), and copy(). This allows deques to be registered as a MutableSequence and it improves their substitutablity for lists. + Deques now also support __add__, __mul__, and __imul__(). - Issue #23715: :func:`signal.sigwaitinfo` and :func:`signal.sigtimedwait` are now retried when interrupted by a signal not in the *sigset* parameter, if diff --git a/Modules/_collectionsmodule.c b/Modules/_collectionsmodule.c --- a/Modules/_collectionsmodule.c +++ b/Modules/_collectionsmodule.c @@ -110,6 +110,12 @@ #define CHECK_NOT_END(link) #endif +/* To prevent len from overflowing PY_SSIZE_T_MAX, we refuse to + allocate new blocks if the current len is nearing overflow. +*/ + +#define MAX_DEQUE_LEN (PY_SSIZE_T_MAX - 3*BLOCKLEN) + /* A simple freelisting scheme is used to minimize calls to the memory allocator. It accommodates common use cases where new blocks are being added at about the same rate as old blocks are being freed. @@ -122,9 +128,7 @@ static block * newblock(Py_ssize_t len) { block *b; - /* To prevent len from overflowing PY_SSIZE_T_MAX, we refuse to - * allocate new blocks if the current len is nearing overflow. */ - if (len >= PY_SSIZE_T_MAX - 2*BLOCKLEN) { + if (len >= MAX_DEQUE_LEN) { PyErr_SetString(PyExc_OverflowError, "cannot add more blocks to the deque"); return NULL; @@ -498,6 +502,115 @@ return (PyObject *)deque; } +static PyObject *deque_copy(PyObject *deque); + +static PyObject * +deque_concat(dequeobject *deque, PyObject *other) +{ + PyObject *new_deque; + int rv; + + rv = PyObject_IsInstance(other, (PyObject *)&deque_type); + if (rv <= 0) { + if (rv == 0) { + PyErr_Format(PyExc_TypeError, + "can only concatenate deque (not \"%.200s\") to deque", + other->ob_type->tp_name); + } + return NULL; + } + + new_deque = deque_copy((PyObject *)deque); + if (new_deque == NULL) + return NULL; + return deque_inplace_concat((dequeobject *)new_deque, other); +} + +static void deque_clear(dequeobject *deque); + +static PyObject * +deque_repeat(dequeobject *deque, Py_ssize_t n) +{ + dequeobject *new_deque; + PyObject *result; + + /* XXX add a special case for when maxlen is defined */ + if (n < 0) + n = 0; + else if (n > 0 && Py_SIZE(deque) > MAX_DEQUE_LEN / n) + return PyErr_NoMemory(); + + new_deque = (dequeobject *)deque_new(&deque_type, (PyObject *)NULL, (PyObject *)NULL); + new_deque->maxlen = deque->maxlen; + + for ( ; n ; n--) { + result = deque_extend(new_deque, (PyObject *)deque); + if (result == NULL) { + Py_DECREF(new_deque); + return NULL; + } + Py_DECREF(result); + } + return (PyObject *)new_deque; +} + +static PyObject * +deque_inplace_repeat(dequeobject *deque, Py_ssize_t n) +{ + Py_ssize_t i, size; + PyObject *seq; + PyObject *rv; + + size = Py_SIZE(deque); + if (size == 0 || n == 1) { + Py_INCREF(deque); + return (PyObject *)deque; + } + + if (n <= 0) { + deque_clear(deque); + Py_INCREF(deque); + return (PyObject *)deque; + } + + if (size > MAX_DEQUE_LEN / n) { + return PyErr_NoMemory(); + } + + if (size == 1) { + /* common case, repeating a single element */ + PyObject *item = deque->leftblock->data[deque->leftindex]; + + if (deque->maxlen != -1 && n > deque->maxlen) + n = deque->maxlen; + + for (i = 0 ; i < n-1 ; i++) { + rv = deque_append(deque, item); + if (rv == NULL) + return NULL; + Py_DECREF(rv); + } + Py_INCREF(deque); + return (PyObject *)deque; + } + + seq = PySequence_List((PyObject *)deque); + if (seq == NULL) + return seq; + + for (i = 0 ; i < n-1 ; i++) { + rv = deque_extend(deque, seq); + if (rv == NULL) { + Py_DECREF(seq); + return NULL; + } + Py_DECREF(rv); + } + Py_INCREF(deque); + Py_DECREF(seq); + return (PyObject *)deque; +} + /* The rotate() method is part of the public API and is used internally as a primitive for other methods. @@ -1283,6 +1396,9 @@ return PyLong_FromSsize_t(deque->maxlen); } + +/* deque object ********************************************************/ + static PyGetSetDef deque_getset[] = { {"maxlen", (getter)deque_get_maxlen, (setter)NULL, "maximum size of a deque or None if unbounded"}, @@ -1291,15 +1407,15 @@ static PySequenceMethods deque_as_sequence = { (lenfunc)deque_len, /* sq_length */ - 0, /* sq_concat */ - 0, /* sq_repeat */ + (binaryfunc)deque_concat, /* sq_concat */ + (ssizeargfunc)deque_repeat, /* sq_repeat */ (ssizeargfunc)deque_item, /* sq_item */ 0, /* sq_slice */ (ssizeobjargproc)deque_ass_item, /* sq_ass_item */ 0, /* sq_ass_slice */ (objobjproc)deque_contains, /* sq_contains */ (binaryfunc)deque_inplace_concat, /* sq_inplace_concat */ - 0, /* sq_inplace_repeat */ + (ssizeargfunc)deque_inplace_repeat, /* sq_inplace_repeat */ }; static PyNumberMethods deque_as_number = { @@ -1316,9 +1432,6 @@ 0, /* nb_invert */ }; - -/* deque object ********************************************************/ - static PyObject *deque_iter(dequeobject *deque); static PyObject *deque_reviter(dequeobject *deque); PyDoc_STRVAR(reversed_doc, @@ -1367,7 +1480,7 @@ PyDoc_STRVAR(deque_doc, "deque([iterable[, maxlen]]) --> deque object\n\ \n\ -Build an ordered collection with optimized access from its endpoints."); +A list-like sequence optimized for data accesses near its endpoints."); static PyTypeObject deque_type = { PyVarObject_HEAD_INIT(NULL, 0) -- Repository URL: https://hg.python.org/cpython