Lines Matching refs:deque
16 /* collections module implementation of a deque() datatype
31 /* Data for deque objects is stored in a doubly-linked list of fixed
49 * A deque d's first element is at d.leftblock[leftindex]
126 newblock(dequeobject *deque) {
128 if (deque->numfreeblocks) {
129 deque->numfreeblocks--;
130 return deque->freeblocks[deque->numfreeblocks];
141 freeblock(dequeobject *deque, block *b)
143 if (deque->numfreeblocks < MAXFREEBLOCKS) {
144 deque->freeblocks[deque->numfreeblocks] = b;
145 deque->numfreeblocks++;
154 dequeobject *deque;
158 deque = (dequeobject *)type->tp_alloc(type, 0);
159 if (deque == NULL)
162 b = newblock(deque);
164 Py_DECREF(deque);
171 Py_SET_SIZE(deque, 0);
172 deque->leftblock = b;
173 deque->rightblock = b;
174 deque->leftindex = CENTER + 1;
175 deque->rightindex = CENTER;
176 deque->state = 0;
177 deque->maxlen = -1;
178 deque->numfreeblocks = 0;
179 deque->weakreflist = NULL;
181 return (PyObject *)deque;
185 deque_pop(dequeobject *deque, PyObject *unused)
190 if (Py_SIZE(deque) == 0) {
191 PyErr_SetString(PyExc_IndexError, "pop from an empty deque");
194 item = deque->rightblock->data[deque->rightindex];
195 deque->rightindex--;
196 Py_SET_SIZE(deque, Py_SIZE(deque) - 1);
197 deque->state++;
199 if (deque->rightindex < 0) {
200 if (Py_SIZE(deque)) {
201 prevblock = deque->rightblock->leftlink;
202 assert(deque->leftblock != deque->rightblock);
203 freeblock(deque, deque->rightblock);
206 deque->rightblock = prevblock;
207 deque->rightindex = BLOCKLEN - 1;
209 assert(deque->leftblock == deque->rightblock);
210 assert(deque->leftindex == deque->rightindex+1);
212 deque->leftindex = CENTER + 1;
213 deque->rightindex = CENTER;
222 deque_popleft(dequeobject *deque, PyObject *unused)
227 if (Py_SIZE(deque) == 0) {
228 PyErr_SetString(PyExc_IndexError, "pop from an empty deque");
231 assert(deque->leftblock != NULL);
232 item = deque->leftblock->data[deque->leftindex];
233 deque->leftindex++;
234 Py_SET_SIZE(deque, Py_SIZE(deque) - 1);
235 deque->state++;
237 if (deque->leftindex == BLOCKLEN) {
238 if (Py_SIZE(deque)) {
239 assert(deque->leftblock != deque->rightblock);
240 prevblock = deque->leftblock->rightlink;
241 freeblock(deque, deque->leftblock);
244 deque->leftblock = prevblock;
245 deque->leftindex = 0;
247 assert(deque->leftblock == deque->rightblock);
248 assert(deque->leftindex == deque->rightindex+1);
250 deque->leftindex = CENTER + 1;
251 deque->rightindex = CENTER;
259 /* The deque's size limit is d.maxlen. The limit can be zero or positive.
262 * After an item is added to a deque, we check to see if the size has
267 * The macro to check whether a deque needs to be trimmed uses a single
268 * unsigned test that returns true whenever 0 <= maxlen < Py_SIZE(deque).
271 #define NEEDS_TRIM(deque, maxlen) ((size_t)(maxlen) < (size_t)(Py_SIZE(deque)))
274 deque_append_internal(dequeobject *deque, PyObject *item, Py_ssize_t maxlen)
276 if (deque->rightindex == BLOCKLEN - 1) {
277 block *b = newblock(deque);
280 b->leftlink = deque->rightblock;
281 CHECK_END(deque->rightblock->rightlink);
282 deque->rightblock->rightlink = b;
283 deque->rightblock = b;
285 deque->rightindex = -1;
287 Py_SET_SIZE(deque, Py_SIZE(deque) + 1);
288 deque->rightindex++;
289 deque->rightblock->data[deque->rightindex] = item;
290 if (NEEDS_TRIM(deque, maxlen)) {
291 PyObject *olditem = deque_popleft(deque, NULL);
294 deque->state++;
300 deque_append(dequeobject *deque, PyObject *item)
303 if (deque_append_internal(deque, item, deque->maxlen) < 0)
308 PyDoc_STRVAR(append_doc, "Add an element to the right side of the deque.");
311 deque_appendleft_internal(dequeobject *deque, PyObject *item, Py_ssize_t maxlen)
313 if (deque->leftindex == 0) {
314 block *b = newblock(deque);
317 b->rightlink = deque->leftblock;
318 CHECK_END(deque->leftblock->leftlink);
319 deque->leftblock->leftlink = b;
320 deque->leftblock = b;
322 deque->leftindex = BLOCKLEN;
324 Py_SET_SIZE(deque, Py_SIZE(deque) + 1);
325 deque->leftindex--;
326 deque->leftblock->data[deque->leftindex] = item;
327 if (NEEDS_TRIM(deque, deque->maxlen)) {
328 PyObject *olditem = deque_pop(deque, NULL);
331 deque->state++;
337 deque_appendleft(dequeobject *deque, PyObject *item)
340 if (deque_appendleft_internal(deque, item, deque->maxlen) < 0)
345 PyDoc_STRVAR(appendleft_doc, "Add an element to the left side of the deque.");
378 deque_extend(dequeobject *deque, PyObject *iterable)
382 Py_ssize_t maxlen = deque->maxlen;
384 /* Handle case where id(deque) == id(iterable) */
385 if ((PyObject *)deque == iterable) {
390 result = deque_extend(deque, s);
403 if (Py_SIZE(deque) == 0) {
404 assert(deque->leftblock == deque->rightblock);
405 assert(deque->leftindex == deque->rightindex+1);
406 deque->leftindex = 1;
407 deque->rightindex = 0;
412 if (deque_append_internal(deque, item, maxlen) == -1) {
422 "Extend the right side of the deque with elements from the iterable");
425 deque_extendleft(dequeobject *deque, PyObject *iterable)
429 Py_ssize_t maxlen = deque->maxlen;
431 /* Handle case where id(deque) == id(iterable) */
432 if ((PyObject *)deque == iterable) {
437 result = deque_extendleft(deque, s);
450 if (Py_SIZE(deque) == 0) {
451 assert(deque->leftblock == deque->rightblock);
452 assert(deque->leftindex == deque->rightindex+1);
453 deque->leftindex = BLOCKLEN - 1;
454 deque->rightindex = BLOCKLEN - 2;
459 if (deque_appendleft_internal(deque, item, maxlen) == -1) {
469 "Extend the left side of the deque with elements from the iterable");
472 deque_inplace_concat(dequeobject *deque, PyObject *other)
476 result = deque_extend(deque, other);
479 Py_INCREF(deque);
481 return (PyObject *)deque;
485 deque_copy(PyObject *deque, PyObject *Py_UNUSED(ignored))
488 dequeobject *old_deque = (dequeobject *)deque;
489 if (Py_IS_TYPE(deque, &deque_type)) {
497 /* Fast path for the deque_repeat() common case where len(deque) == 1 */
498 if (Py_SIZE(deque) == 1) {
502 rv = deque_extend(new_deque, deque);
512 result = PyObject_CallOneArg((PyObject *)(Py_TYPE(deque)), deque);
514 result = PyObject_CallFunction((PyObject *)(Py_TYPE(deque)), "Oi",
515 deque, old_deque->maxlen, NULL);
518 "%.200s() must return a deque, not %.200s",
519 Py_TYPE(deque)->tp_name, Py_TYPE(result)->tp_name);
526 PyDoc_STRVAR(copy_doc, "Return a shallow copy of a deque.");
529 deque_concat(dequeobject *deque, PyObject *other)
538 "can only concatenate deque (not \"%.200s\") to deque",
544 new_deque = deque_copy((PyObject *)deque, NULL);
557 deque_clear(dequeobject *deque)
567 if (Py_SIZE(deque) == 0)
570 /* During the process of clearing a deque, decrefs can cause the
571 deque to mutate. To avoid fatal confusion, we have to make the
572 deque empty before clearing the blocks and never refer to
573 anything via deque->ref while clearing. (This is the same
576 Making the deque empty requires allocating a new empty block. In
583 b = newblock(deque);
590 n = Py_SIZE(deque);
591 leftblock = deque->leftblock;
592 leftindex = deque->leftindex;
594 /* Set the deque to be empty using the newly allocated block */
597 Py_SET_SIZE(deque, 0);
598 deque->leftblock = b;
599 deque->rightblock = b;
600 deque->leftindex = CENTER + 1;
601 deque->rightindex = CENTER;
602 deque->state++;
605 the empty deque and we can use them to decref the pointers.
622 freeblock(deque, prevblock);
628 freeblock(deque, leftblock);
632 while (Py_SIZE(deque)) {
633 item = deque_pop(deque, NULL);
641 deque_clearmethod(dequeobject *deque, PyObject *Py_UNUSED(ignored))
643 deque_clear(deque);
647 PyDoc_STRVAR(clear_doc, "Remove all elements from the deque.");
650 deque_inplace_repeat(dequeobject *deque, Py_ssize_t n)
656 size = Py_SIZE(deque);
658 Py_INCREF(deque);
659 return (PyObject *)deque;
663 deque_clear(deque);
664 Py_INCREF(deque);
665 return (PyObject *)deque;
670 PyObject *item = deque->leftblock->data[deque->leftindex];
672 if (deque->maxlen >= 0 && n > deque->maxlen)
673 n = deque->maxlen;
675 deque->state++;
677 if (deque->rightindex == BLOCKLEN - 1) {
678 block *b = newblock(deque);
680 Py_SET_SIZE(deque, Py_SIZE(deque) + i);
683 b->leftlink = deque->rightblock;
684 CHECK_END(deque->rightblock->rightlink);
685 deque->rightblock->rightlink = b;
686 deque->rightblock = b;
688 deque->rightindex = -1;
691 if (m > BLOCKLEN - 1 - deque->rightindex)
692 m = BLOCKLEN - 1 - deque->rightindex;
695 deque->rightindex++;
697 deque->rightblock->data[deque->rightindex] = item;
700 Py_SET_SIZE(deque, Py_SIZE(deque) + i);
701 Py_INCREF(deque);
702 return (PyObject *)deque;
709 seq = PySequence_List((PyObject *)deque);
714 if (deque->maxlen >= 0 && n * size > deque->maxlen)
715 n = (deque->maxlen + size - 1) / size;
718 rv = deque_extend(deque, seq);
725 Py_INCREF(deque);
727 return (PyObject *)deque;
731 deque_repeat(dequeobject *deque, Py_ssize_t n)
736 new_deque = (dequeobject *)deque_copy((PyObject *) deque, NULL);
770 _deque_rotate(dequeobject *deque, Py_ssize_t n)
773 block *leftblock = deque->leftblock;
774 block *rightblock = deque->rightblock;
775 Py_ssize_t leftindex = deque->leftindex;
776 Py_ssize_t rightindex = deque->rightindex;
777 Py_ssize_t len=Py_SIZE(deque), halflen=len>>1;
792 deque->state++;
796 b = newblock(deque);
840 b = newblock(deque);
884 freeblock(deque, b);
885 deque->leftblock = leftblock;
886 deque->rightblock = rightblock;
887 deque->leftindex = leftindex;
888 deque->rightindex = rightindex;
894 deque_rotate(dequeobject *deque, PyObject *const *args, Py_ssize_t nargs)
898 if (!_PyArg_CheckPositional("deque.rotate", nargs, 0, 1)) {
913 if (!_deque_rotate(deque, n))
919 "Rotate the deque n steps to the right (default n=1). If n is negative, rotates left.");
922 deque_reverse(dequeobject *deque, PyObject *unused)
924 block *leftblock = deque->leftblock;
925 block *rightblock = deque->rightblock;
926 Py_ssize_t leftindex = deque->leftindex;
927 Py_ssize_t rightindex = deque->rightindex;
928 Py_ssize_t n = Py_SIZE(deque) >> 1;
963 deque_count(dequeobject *deque, PyObject *v)
965 block *b = deque->leftblock;
966 Py_ssize_t index = deque->leftindex;
967 Py_ssize_t n = Py_SIZE(deque);
969 size_t start_state = deque->state;
983 if (start_state != deque->state) {
985 "deque mutated during iteration");
1003 deque_contains(dequeobject *deque, PyObject *v)
1005 block *b = deque->leftblock;
1006 Py_ssize_t index = deque->leftindex;
1007 Py_ssize_t n = Py_SIZE(deque);
1008 size_t start_state = deque->state;
1021 if (start_state != deque->state) {
1023 "deque mutated during iteration");
1036 deque_len(dequeobject *deque)
1038 return Py_SIZE(deque);
1042 deque_index(dequeobject *deque, PyObject *const *args, Py_ssize_t nargs)
1044 Py_ssize_t i, n, start=0, stop=Py_SIZE(deque);
1046 block *b = deque->leftblock;
1047 Py_ssize_t index = deque->leftindex;
1048 size_t start_state = deque->state;
1058 start += Py_SIZE(deque);
1063 stop += Py_SIZE(deque);
1067 if (stop > Py_SIZE(deque))
1068 stop = Py_SIZE(deque);
1071 assert(0 <= start && start <= stop && stop <= Py_SIZE(deque));
1093 if (start_state != deque->state) {
1095 "deque mutated during iteration");
1104 PyErr_Format(PyExc_ValueError, "%R is not in deque", v);
1121 deque_insert(dequeobject *deque, PyObject *const *args, Py_ssize_t nargs)
1124 Py_ssize_t n = Py_SIZE(deque);
1132 if (deque->maxlen == Py_SIZE(deque)) {
1133 PyErr_SetString(PyExc_IndexError, "deque already at its maximum size");
1137 return deque_append(deque, value);
1139 return deque_appendleft(deque, value);
1140 if (_deque_rotate(deque, -index))
1143 rv = deque_append(deque, value);
1145 rv = deque_appendleft(deque, value);
1149 if (_deque_rotate(deque, index))
1169 deque_item(dequeobject *deque, Py_ssize_t i)
1175 if (!valid_index(i, Py_SIZE(deque))) {
1176 PyErr_SetString(PyExc_IndexError, "deque index out of range");
1181 i = deque->leftindex;
1182 b = deque->leftblock;
1183 } else if (i == Py_SIZE(deque) - 1) {
1184 i = deque->rightindex;
1185 b = deque->rightblock;
1187 i += deque->leftindex;
1190 if (index < (Py_SIZE(deque) >> 1)) {
1191 b = deque->leftblock;
1196 ((size_t)(deque->leftindex + Py_SIZE(deque) - 1))
1198 b = deque->rightblock;
1209 deque_del_item(dequeobject *deque, Py_ssize_t i)
1214 assert (i >= 0 && i < Py_SIZE(deque));
1215 if (_deque_rotate(deque, -i))
1217 item = deque_popleft(deque, NULL);
1218 rv = _deque_rotate(deque, i);
1225 deque_remove(dequeobject *deque, PyObject *value)
1228 block *b = deque->leftblock;
1229 Py_ssize_t i, n = Py_SIZE(deque), index = deque->leftindex;
1230 size_t start_state = deque->state;
1241 if (start_state != deque->state) {
1243 "deque mutated during iteration");
1256 PyErr_Format(PyExc_ValueError, "%R is not in deque", value);
1259 rv = deque_del_item(deque, i);
1267 deque_ass_item(dequeobject *deque, Py_ssize_t i, PyObject *v)
1271 Py_ssize_t n, len=Py_SIZE(deque), halflen=(len+1)>>1, index=i;
1274 PyErr_SetString(PyExc_IndexError, "deque index out of range");
1278 return deque_del_item(deque, i);
1280 i += deque->leftindex;
1284 b = deque->leftblock;
1289 ((size_t)(deque->leftindex + Py_SIZE(deque) - 1))
1291 b = deque->rightblock;
1303 deque_dealloc(dequeobject *deque)
1307 PyObject_GC_UnTrack(deque);
1308 if (deque->weakreflist != NULL)
1309 PyObject_ClearWeakRefs((PyObject *) deque);
1310 if (deque->leftblock != NULL) {
1311 deque_clear(deque);
1312 assert(deque->leftblock != NULL);
1313 freeblock(deque, deque->leftblock);
1315 deque->leftblock = NULL;
1316 deque->rightblock = NULL;
1317 for (i=0 ; i < deque->numfreeblocks ; i++) {
1318 PyMem_Free(deque->freeblocks[i]);
1320 Py_TYPE(deque)->tp_free(deque);
1324 deque_traverse(dequeobject *deque, visitproc visit, void *arg)
1329 Py_ssize_t indexlo = deque->leftindex;
1332 for (b = deque->leftblock; b != deque->rightblock; b = b->rightlink) {
1339 indexhigh = deque->rightindex;
1348 deque_reduce(dequeobject *deque, PyObject *Py_UNUSED(ignored))
1352 state = _PyObject_GetState((PyObject *)deque);
1357 it = PyObject_GetIter((PyObject *)deque);
1363 if (deque->maxlen < 0) {
1364 return Py_BuildValue("O()NN", Py_TYPE(deque), state, it);
1367 return Py_BuildValue("O(()n)NN", Py_TYPE(deque), deque->maxlen, state, it);
1374 deque_repr(PyObject *deque)
1379 i = Py_ReprEnter(deque);
1386 aslist = PySequence_List(deque);
1388 Py_ReprLeave(deque);
1391 if (((dequeobject *)deque)->maxlen >= 0)
1393 _PyType_Name(Py_TYPE(deque)), aslist,
1394 ((dequeobject *)deque)->maxlen);
1397 _PyType_Name(Py_TYPE(deque)), aslist);
1398 Py_ReprLeave(deque);
1457 /* We reached the end of one deque or both */
1466 case Py_NE: cmp = x != y; break; /* if one deque continues */
1482 deque_init(dequeobject *deque, PyObject *args, PyObject *kwdargs)
1497 if (!PyArg_ParseTupleAndKeywords(args, kwdargs, "|OO:deque", kwlist,
1510 deque->maxlen = maxlen;
1511 if (Py_SIZE(deque) > 0)
1512 deque_clear(deque);
1514 PyObject *rv = deque_extend(deque, iterable);
1523 deque_sizeof(dequeobject *deque, void *unused)
1528 res = _PyObject_SIZE(Py_TYPE(deque));
1529 blocks = (size_t)(deque->leftindex + Py_SIZE(deque) + BLOCKLEN - 1) / BLOCKLEN;
1530 assert(deque->leftindex + Py_SIZE(deque) - 1 ==
1531 (blocks - 1) * BLOCKLEN + deque->rightindex);
1540 deque_get_maxlen(dequeobject *deque, void *Py_UNUSED(ignored))
1542 if (deque->maxlen < 0)
1544 return PyLong_FromSsize_t(deque->maxlen);
1548 /* deque object ********************************************************/
1552 "maximum size of a deque or None if unbounded"},
1569 static PyObject *deque_iter(dequeobject *deque);
1570 static PyObject *deque_reviter(dequeobject *deque, PyObject *Py_UNUSED(ignored));
1572 "D.__reversed__() -- return a reverse iterator over the deque");
1617 "deque([iterable[, maxlen]]) --> deque object\n\
1623 "collections.deque", /* tp_name */
1672 dequeobject *deque;
1680 deque_iter(dequeobject *deque)
1687 it->b = deque->leftblock;
1688 it->index = deque->leftindex;
1689 Py_INCREF(deque);
1690 it->deque = deque;
1691 it->state = deque->state;
1692 it->counter = Py_SIZE(deque);
1700 Py_VISIT(dio->deque);
1709 Py_XDECREF(dio->deque);
1718 if (it->deque->state != it->state) {
1721 "deque mutated during iteration");
1726 assert (!(it->b == it->deque->rightblock &&
1727 it->index > it->deque->rightindex));
1745 PyObject *deque;
1747 if (!PyArg_ParseTuple(args, "O!|n", &deque_type, &deque, &index))
1751 it = (dequeiterobject*)deque_iter((dequeobject *)deque);
1781 return Py_BuildValue("O(On)", Py_TYPE(it), it->deque, Py_SIZE(it->deque) - it->counter);
1838 deque_reviter(dequeobject *deque, PyObject *Py_UNUSED(ignored))
1845 it->b = deque->rightblock;
1846 it->index = deque->rightindex;
1847 Py_INCREF(deque);
1848 it->deque = deque;
1849 it->state = deque->state;
1850 it->counter = Py_SIZE(deque);
1862 if (it->deque->state != it->state) {
1865 "deque mutated during iteration");
1868 assert (!(it->b == it->deque->leftblock &&
1869 it->index < it->deque->leftindex));
1887 PyObject *deque;
1889 if (!PyArg_ParseTuple(args, "O!|n", &deque_type, &deque, &index))
1893 it = (dequeiterobject*)deque_reviter((dequeobject *)deque, NULL);
2563 - deque: ordered collection accessible from endpoints only\n\