cpython: b75160d24b7b (original) (raw)

Mercurial > cpython

changeset 95333:b75160d24b7b

Issue 23793: Add deque support for __add__(), __mul__(), and __imul__().

Raymond Hettinger python@rcn.com
date	Tue, 31 Mar 2015 08:12:23 -0700
parents	c59d81b802f8
children	d9374864d4a9
files	Doc/library/collections.rst Lib/test/test_deque.py Misc/NEWS Modules/_collectionsmodule.c
diffstat	4 files changed, 204 insertions(+), 10 deletions(-)[+] [-] Doc/library/collections.rst 3 Lib/test/test_deque.py 77 Misc/NEWS 1 Modules/_collectionsmodule.c 133

line wrap: on

line diff

--- a/Doc/library/collections.rst +++ b/Doc/library/collections.rst @@ -526,6 +526,9 @@ the :keyword:in operator, and subscrip 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::

--- a/Lib/test/test_deque.py +++ b/Lib/test/test_deque.py @@ -192,6 +192,26 @@ class TestBasic(unittest.TestCase): d.extend(d) self.assertEqual(list(d), list('abcdabcd'))

def test_add(self):
```
   d = deque()[](#l2.8)
```
```
   e = deque('abc')[](#l2.9)
```
```
   f = deque('def')[](#l2.10)
```

   self.assertEqual(d + d, deque())[](#l2.11)

   self.assertEqual(e + f, deque('abcdef'))[](#l2.12)

   self.assertEqual(e + e, deque('abcabc'))[](#l2.13)

   self.assertEqual(e + d, deque('abc'))[](#l2.14)

   self.assertEqual(d + e, deque('abc'))[](#l2.15)

   self.assertIsNot(d + d, deque())[](#l2.16)

   self.assertIsNot(e + d, deque('abc'))[](#l2.17)

   self.assertIsNot(d + e, deque('abc'))[](#l2.18)

   g = deque('abcdef', maxlen=4)[](#l2.20)

```
   h = deque('gh')[](#l2.21)
```

   self.assertEqual(g + h, deque('efgh'))[](#l2.22)

   with self.assertRaises(TypeError):[](#l2.24)

```
       deque('abc') + 'def'[](#l2.25)
```

+ def test_iadd(self): d = deque('a') d += 'bcd' @@ -279,6 +299,63 @@ class TestBasic(unittest.TestCase): s.insert(i, 'Z') self.assertEqual(list(d), s)

def test_imul(self):

   for n in (-10, -1, 0, 1, 2, 10, 1000):[](#l2.35)

```
       d = deque()[](#l2.36)
```
```
       d *= n[](#l2.37)
```

       self.assertEqual(d, deque())[](#l2.38)

       self.assertIsNone(d.maxlen)[](#l2.39)

   for n in (-10, -1, 0, 1, 2, 10, 1000):[](#l2.41)

```
       d = deque('a')[](#l2.42)
```
```
       d *= n[](#l2.43)
```

       self.assertEqual(d, deque('a' * n))[](#l2.44)

       self.assertIsNone(d.maxlen)[](#l2.45)

   for n in (-10, -1, 0, 1, 2, 10, 499, 500, 501, 1000):[](#l2.47)

```
       d = deque('a', 500)[](#l2.48)
```
```
       d *= n[](#l2.49)
```

       self.assertEqual(d, deque('a' * min(n, 500)))[](#l2.50)

       self.assertEqual(d.maxlen, 500)[](#l2.51)

   for n in (-10, -1, 0, 1, 2, 10, 1000):[](#l2.53)

```
       d = deque('abcdef')[](#l2.54)
```
```
       d *= n[](#l2.55)
```

       self.assertEqual(d, deque('abcdef' * n))[](#l2.56)

       self.assertIsNone(d.maxlen)[](#l2.57)

   for n in (-10, -1, 0, 1, 2, 10, 499, 500, 501, 1000):[](#l2.59)

       d = deque('abcdef', 500)[](#l2.60)

```
       d *= n[](#l2.61)
```

       self.assertEqual(d, deque(('abcdef' * n)[-500:]))[](#l2.62)

       self.assertEqual(d.maxlen, 500)[](#l2.63)

def test_mul(self):
```
   d = deque('abc')[](#l2.66)
```

   self.assertEqual(d * -5, deque())[](#l2.67)

   self.assertEqual(d * 0, deque())[](#l2.68)

   self.assertEqual(d * 1, deque('abc'))[](#l2.69)

   self.assertEqual(d * 2, deque('abcabc'))[](#l2.70)

   self.assertEqual(d * 3, deque('abcabcabc'))[](#l2.71)

```
   self.assertIsNot(d * 1, d)[](#l2.72)
```

   self.assertEqual(deque() * 0, deque())[](#l2.74)

   self.assertEqual(deque() * 1, deque())[](#l2.75)

   self.assertEqual(deque() * 5, deque())[](#l2.76)

   self.assertEqual(-5 * d, deque())[](#l2.78)

   self.assertEqual(0 * d, deque())[](#l2.79)

   self.assertEqual(1 * d, deque('abc'))[](#l2.80)

   self.assertEqual(2 * d, deque('abcabc'))[](#l2.81)

   self.assertEqual(3 * d, deque('abcabcabc'))[](#l2.82)

```
   d = deque('abc', maxlen=5)[](#l2.84)
```

   self.assertEqual(d * -5, deque())[](#l2.85)

   self.assertEqual(d * 0, deque())[](#l2.86)

   self.assertEqual(d * 1, deque('abc'))[](#l2.87)

   self.assertEqual(d * 2, deque('bcabc'))[](#l2.88)

   self.assertEqual(d * 30, deque('bcabc'))[](#l2.89)

+ def test_setitem(self): n = 200 d = deque(range(n))

--- a/Misc/NEWS +++ b/Misc/NEWS @@ -152,6 +152,7 @@ Library

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

--- a/Modules/_collectionsmodule.c +++ b/Modules/_collectionsmodule.c @@ -110,6 +110,12 @@ static PyTypeObject deque_type; #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 - 3BLOCKLEN) + / 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 *freeblocks[MAXFREEBLOCKS]; 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. */[](#l4.21)

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 @@ deque_inplace_concat(dequeobject *deque, 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) {[](#l4.41)
```

       PyErr_Format(PyExc_TypeError,[](#l4.42)

                    "can only concatenate deque (not \"%.200s\") to deque",[](#l4.43)

                    other->ob_type->tp_name);[](#l4.44)

```
   }[](#l4.45)
```
```
   return NULL;[](#l4.46)
```
}

new_deque = deque_copy((PyObject *)deque);
if (new_deque == NULL)
```
   return NULL;[](#l4.51)
```
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;[](#l4.65)
```
else if (n > 0 && Py_SIZE(deque) > MAX_DEQUE_LEN / n)
```
   return PyErr_NoMemory();[](#l4.67)
```

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);[](#l4.73)

```
   if (result == NULL) {[](#l4.74)
```
```
       Py_DECREF(new_deque);[](#l4.75)
```
```
       return NULL;[](#l4.76)
```
```
   }[](#l4.77)
```
```
   Py_DECREF(result);[](#l4.78)
```
}
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);[](#l4.92)
```
```
   return (PyObject *)deque;[](#l4.93)
```
}

if (n <= 0) {
```
   deque_clear(deque);[](#l4.97)
```
```
   Py_INCREF(deque);[](#l4.98)
```
```
   return (PyObject *)deque;[](#l4.99)
```
}

if (size > MAX_DEQUE_LEN / n) {
```
   return PyErr_NoMemory();[](#l4.103)
```
}

if (size == 1) {

   /* common case, repeating a single element */[](#l4.107)

   PyObject *item = deque->leftblock->data[deque->leftindex];[](#l4.108)

   if (deque->maxlen != -1 && n > deque->maxlen)[](#l4.110)

```
       n = deque->maxlen;[](#l4.111)
```

   for (i = 0 ; i < n-1 ; i++) {[](#l4.113)

       rv = deque_append(deque, item);[](#l4.114)

```
       if (rv == NULL)[](#l4.115)
```
```
           return NULL;[](#l4.116)
```
```
       Py_DECREF(rv);[](#l4.117)
```
```
   }[](#l4.118)
```
```
   Py_INCREF(deque);[](#l4.119)
```
```
   return (PyObject *)deque;[](#l4.120)
```
}

seq = PySequence_List((PyObject *)deque);
if (seq == NULL)
```
   return seq;[](#l4.125)
```

for (i = 0 ; i < n-1 ; i++) {

   rv = deque_extend(deque, seq);[](#l4.128)

```
   if (rv == NULL) {[](#l4.129)
```
```
       Py_DECREF(seq);[](#l4.130)
```
```
       return NULL;[](#l4.131)
```
```
   }[](#l4.132)
```
```
   Py_DECREF(rv);[](#l4.133)
```
}
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 @@ deque_get_maxlen(dequeobject deque) 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 PyGetSetDef deque_getset[] = { 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 @@ static PyNumberMethods deque_as_number = 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 @@ static PyMethodDef deque_methods[] = { PyDoc_STRVAR(deque_doc, "deque([iterable[, maxlen]]) --> deque object\n[](#l4.184) \n[](#l4.185) -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)