diff options
-rw-r--r-- | Lib/test/test_deque.py | 20 | ||||
-rw-r--r-- | Modules/_collectionsmodule.c | 34 |
2 files changed, 53 insertions, 1 deletions
diff --git a/Lib/test/test_deque.py b/Lib/test/test_deque.py index 0eebbff..7d69448 100644 --- a/Lib/test/test_deque.py +++ b/Lib/test/test_deque.py @@ -164,6 +164,26 @@ class TestBasic(unittest.TestCase): self.assertEqual(x > y, list(x) > list(y), (x,y)) self.assertEqual(x >= y, list(x) >= list(y), (x,y)) + def test_contains(self): + n = 200 + + d = deque(range(n)) + for i in range(n): + self.assertTrue(i in d) + self.assertTrue((n+1) not in d) + + # Test detection of mutation during iteration + d = deque(range(n)) + d[n//2] = MutateCmp(d, False) + with self.assertRaises(RuntimeError): + n in d + + # Test detection of comparison exceptions + d = deque(range(n)) + d[n//2] = BadCmp() + with self.assertRaises(RuntimeError): + n in d + def test_extend(self): d = deque('a') self.assertRaises(TypeError, d.extend, 1) diff --git a/Modules/_collectionsmodule.c b/Modules/_collectionsmodule.c index d4794be..26a0c8f 100644 --- a/Modules/_collectionsmodule.c +++ b/Modules/_collectionsmodule.c @@ -724,6 +724,38 @@ deque_count(dequeobject *deque, PyObject *v) PyDoc_STRVAR(count_doc, "D.count(value) -> integer -- return number of occurrences of value"); +static int +deque_contains(dequeobject *deque, PyObject *v) +{ + block *b = deque->leftblock; + Py_ssize_t index = deque->leftindex; + Py_ssize_t n = Py_SIZE(deque); + Py_ssize_t i; + size_t start_state = deque->state; + PyObject *item; + int cmp; + + for (i=0 ; i<n ; i++) { + CHECK_NOT_END(b); + item = b->data[index]; + cmp = PyObject_RichCompareBool(item, v, Py_EQ); + if (cmp) { + return cmp; + } + if (start_state != deque->state) { + PyErr_SetString(PyExc_RuntimeError, + "deque mutated during iteration"); + return -1; + } + index++; + if (index == BLOCKLEN) { + b = b->rightlink; + index = 0; + } + } + return 0; +} + static Py_ssize_t deque_len(dequeobject *deque) { @@ -1154,7 +1186,7 @@ static PySequenceMethods deque_as_sequence = { 0, /* sq_slice */ (ssizeobjargproc)deque_ass_item, /* sq_ass_item */ 0, /* sq_ass_slice */ - 0, /* sq_contains */ + (objobjproc)deque_contains, /* sq_contains */ (binaryfunc)deque_inplace_concat, /* sq_inplace_concat */ 0, /* sq_inplace_repeat */ |