Lines Matching defs:deque
4 /* collections module implementation of a deque() datatype
23 * and the rightmost block has rightlink==NULL). A deque d's first
67 "cannot add more blocks to the deque");
108 /* The deque's size limit is d.maxlen. The limit can be zero or positive.
111 * After an item is added to a deque, we check to see if the size has grown past
129 dequeobject *deque;
133 deque = (dequeobject *)type->tp_alloc(type, 0);
134 if (deque == NULL)
139 Py_DECREF(deque);
144 deque->leftblock = b;
145 deque->rightblock = b;
146 deque->leftindex = CENTER + 1;
147 deque->rightindex = CENTER;
148 deque->len = 0;
149 deque->state = 0;
150 deque->weakreflist = NULL;
151 deque->maxlen = -1;
153 return (PyObject *)deque;
157 deque_pop(dequeobject *deque, PyObject *unused)
162 if (deque->len == 0) {
163 PyErr_SetString(PyExc_IndexError, "pop from an empty deque");
166 item = deque->rightblock->data[deque->rightindex];
167 deque->rightindex--;
168 deque->len--;
169 deque->state++;
171 if (deque->rightindex == -1) {
172 if (deque->len == 0) {
173 assert(deque->leftblock == deque->rightblock);
174 assert(deque->leftindex == deque->rightindex+1);
176 deque->leftindex = CENTER + 1;
177 deque->rightindex = CENTER;
179 prevblock = deque->rightblock->leftlink;
180 assert(deque->leftblock != deque->rightblock);
181 freeblock(deque->rightblock);
183 deque->rightblock = prevblock;
184 deque->rightindex = BLOCKLEN - 1;
193 deque_popleft(dequeobject *deque, PyObject *unused)
198 if (deque->len == 0) {
199 PyErr_SetString(PyExc_IndexError, "pop from an empty deque");
202 assert(deque->leftblock != NULL);
203 item = deque->leftblock->data[deque->leftindex];
204 deque->leftindex++;
205 deque->len--;
206 deque->state++;
208 if (deque->leftindex == BLOCKLEN) {
209 if (deque->len == 0) {
210 assert(deque->leftblock == deque->rightblock);
211 assert(deque->leftindex == deque->rightindex+1);
213 deque->leftindex = CENTER + 1;
214 deque->rightindex = CENTER;
216 assert(deque->leftblock != deque->rightblock);
217 prevblock = deque->leftblock->rightlink;
218 freeblock(deque->leftblock);
221 deque->leftblock = prevblock;
222 deque->leftindex = 0;
231 deque_append(dequeobject *deque, PyObject *item)
233 deque->state++;
234 if (deque->rightindex == BLOCKLEN-1) {
235 block *b = newblock(deque->rightblock, NULL, deque->len);
238 assert(deque->rightblock->rightlink == NULL);
239 deque->rightblock->rightlink = b;
240 deque->rightblock = b;
241 deque->rightindex = -1;
244 deque->len++;
245 deque->rightindex++;
246 deque->rightblock->data[deque->rightindex] = item;
247 TRIM(deque, deque_popleft);
251 PyDoc_STRVAR(append_doc, "Add an element to the right side of the deque.");
254 deque_appendleft(dequeobject *deque, PyObject *item)
256 deque->state++;
257 if (deque->leftindex == 0) {
258 block *b = newblock(NULL, deque->leftblock, deque->len);
261 assert(deque->leftblock->leftlink == NULL);
262 deque->leftblock->leftlink = b;
263 deque->leftblock = b;
264 deque->leftindex = BLOCKLEN;
267 deque->len++;
268 deque->leftindex--;
269 deque->leftblock->data[deque->leftindex] = item;
270 TRIM(deque, deque_pop);
274 PyDoc_STRVAR(appendleft_doc, "Add an element to the left side of the deque.");
294 deque_extend(dequeobject *deque, PyObject *iterable)
298 /* Handle case where id(deque) == id(iterable) */
299 if ((PyObject *)deque == iterable) {
304 result = deque_extend(deque, s);
313 if (deque->maxlen == 0)
317 deque->state++;
318 if (deque->rightindex == BLOCKLEN-1) {
319 block *b = newblock(deque->rightblock, NULL,
320 deque->len);
326 assert(deque->rightblock->rightlink == NULL);
327 deque->rightblock->rightlink = b;
328 deque->rightblock = b;
329 deque->rightindex = -1;
331 deque->len++;
332 deque->rightindex++;
333 deque->rightblock->data[deque->rightindex] = item;
334 TRIM(deque, deque_popleft);
343 "Extend the right side of the deque with elements from the iterable");
346 deque_extendleft(dequeobject *deque, PyObject *iterable)
350 /* Handle case where id(deque) == id(iterable) */
351 if ((PyObject *)deque == iterable) {
356 result = deque_extendleft(deque, s);
365 if (deque->maxlen == 0)
369 deque->state++;
370 if (deque->leftindex == 0) {
371 block *b = newblock(NULL, deque->leftblock,
372 deque->len);
378 assert(deque->leftblock->leftlink == NULL);
379 deque->leftblock->leftlink = b;
380 deque->leftblock = b;
381 deque->leftindex = BLOCKLEN;
383 deque->len++;
384 deque->leftindex--;
385 deque->leftblock->data[deque->leftindex] = item;
386 TRIM(deque, deque_pop);
395 "Extend the left side of the deque with elements from the iterable");
398 deque_inplace_concat(dequeobject *deque, PyObject *other)
402 result = deque_extend(deque, other);
406 Py_INCREF(deque);
407 return (PyObject *)deque;
411 _deque_rotate(dequeobject *deque, Py_ssize_t n)
413 Py_ssize_t m, len=deque->len, halflen=len>>1;
427 deque->state++;
429 if (deque->leftindex == 0) {
430 block *b = newblock(NULL, deque->leftblock, len);
433 assert(deque->leftblock->leftlink == NULL);
434 deque->leftblock->leftlink = b;
435 deque->leftblock = b;
436 deque->leftindex = BLOCKLEN;
438 assert(deque->leftindex > 0);
441 if (m > deque->rightindex + 1)
442 m = deque->rightindex + 1;
443 if (m > deque->leftindex)
444 m = deque->leftindex;
446 memcpy(&deque->leftblock->data[deque->leftindex - m],
447 &deque->rightblock->data[deque->rightindex + 1 - m],
449 deque->rightindex -= m;
450 deque->leftindex -= m;
453 if (deque->rightindex == -1) {
454 block *prevblock = deque->rightblock->leftlink;
455 assert(deque->rightblock != NULL);
456 assert(deque->leftblock != deque->rightblock);
457 freeblock(deque->rightblock);
459 deque->rightblock = prevblock;
460 deque->rightindex = BLOCKLEN - 1;
464 if (deque->rightindex == BLOCKLEN - 1) {
465 block *b = newblock(deque->rightblock, NULL, len);
468 assert(deque->rightblock->rightlink == NULL);
469 deque->rightblock->rightlink = b;
470 deque->rightblock = b;
471 deque->rightindex = -1;
473 assert (deque->rightindex < BLOCKLEN - 1);
476 if (m > BLOCKLEN - deque->leftindex)
477 m = BLOCKLEN - deque->leftindex;
478 if (m > BLOCKLEN - 1 - deque->rightindex)
479 m = BLOCKLEN - 1 - deque->rightindex;
481 memcpy(&deque->rightblock->data[deque->rightindex + 1],
482 &deque->leftblock->data[deque->leftindex],
484 deque->leftindex += m;
485 deque->rightindex += m;
488 if (deque->leftindex == BLOCKLEN) {
489 block *nextblock = deque->leftblock->rightlink;
490 assert(deque->leftblock != deque->rightblock);
491 freeblock(deque->leftblock);
494 deque->leftblock = nextblock;
495 deque->leftindex = 0;
502 deque_rotate(dequeobject *deque, PyObject *args)
508 if (_deque_rotate(deque, n) == 0)
514 "Rotate the deque n steps to the right (default n=1). If n is negative, rotates left.");
517 deque_reverse(dequeobject *deque, PyObject *unused)
519 block *leftblock = deque->leftblock;
520 block *rightblock = deque->rightblock;
521 Py_ssize_t leftindex = deque->leftindex;
522 Py_ssize_t rightindex = deque->rightindex;
523 Py_ssize_t n = (deque->len)/2;
561 deque_count(dequeobject *deque, PyObject *v)
563 block *leftblock = deque->leftblock;
564 Py_ssize_t leftindex = deque->leftindex;
565 Py_ssize_t n = deque->len;
569 long start_state = deque->state;
580 if (start_state != deque->state) {
582 "deque mutated during iteration");
602 deque_len(dequeobject *deque)
604 return deque->len;
608 deque_remove(dequeobject *deque, PyObject *value)
610 Py_ssize_t i, n=deque->len;
613 PyObject *item = deque->leftblock->data[deque->leftindex];
616 if (deque->len != n) {
618 "deque mutated during remove().");
622 PyObject *tgt = deque_popleft(deque, NULL);
624 if (_deque_rotate(deque, i))
630 _deque_rotate(deque, i);
633 _deque_rotate(deque, -1);
635 PyErr_SetString(PyExc_ValueError, "deque.remove(x): x not in deque");
643 deque_clear(dequeobject *deque)
652 if (deque->len == 0)
655 /* During the process of clearing a deque, decrefs can cause the
656 deque to mutate. To avoid fatal confusion, we have to make the
657 deque empty before clearing the blocks and never refer to
658 anything via deque->ref while clearing. (This is the same
661 Making the deque empty requires allocating a new empty block. In
675 leftblock = deque->leftblock;
676 leftindex = deque->leftindex;
677 n = deque->len;
679 /* Set the deque to be empty using the newly allocated block */
680 deque->len = 0;
681 deque->leftblock = b;
682 deque->rightblock = b;
683 deque->leftindex = CENTER + 1;
684 deque->rightindex = CENTER;
685 deque->state++;
688 the empty deque and we can use them to decref the pointers.
707 while (deque->len) {
708 item = deque_pop(deque, NULL);
715 deque_item(dequeobject *deque, Py_ssize_t i)
721 if (i < 0 || i >= deque->len) {
723 "deque index out of range");
728 i = deque->leftindex;
729 b = deque->leftblock;
730 } else if (i == deque->len - 1) {
731 i = deque->rightindex;
732 b = deque->rightblock;
734 i += deque->leftindex;
737 if (index < (deque->len >> 1)) {
738 b = deque->leftblock;
742 n = (deque->leftindex + deque->len - 1) / BLOCKLEN - n;
743 b = deque->rightblock;
761 deque_del_item(dequeobject *deque, Py_ssize_t i)
766 assert (i >= 0 && i < deque->len);
767 if (_deque_rotate(deque, -i))
769 item = deque_popleft(deque, NULL);
770 rv = _deque_rotate(deque, i);
777 deque_ass_item(dequeobject *deque, Py_ssize_t i, PyObject *v)
781 Py_ssize_t n, len=deque->len, halflen=(len+1)>>1, index=i;
785 "deque index out of range");
789 return deque_del_item(deque, i);
791 i += deque->leftindex;
795 b = deque->leftblock;
799 n = (deque->leftindex + len - 1) / BLOCKLEN - n;
800 b = deque->rightblock;
812 deque_clearmethod(dequeobject *deque)
814 deque_clear(deque);
818 PyDoc_STRVAR(clear_doc, "Remove all elements from the deque.");
821 deque_dealloc(dequeobject *deque)
823 PyObject_GC_UnTrack(deque);
824 if (deque->weakreflist != NULL)
825 PyObject_ClearWeakRefs((PyObject *) deque);
826 if (deque->leftblock != NULL) {
827 deque_clear(deque);
828 assert(deque->leftblock != NULL);
829 freeblock(deque->leftblock);
831 deque->leftblock = NULL;
832 deque->rightblock = NULL;
833 Py_TYPE(deque)->tp_free(deque);
837 deque_traverse(dequeobject *deque, visitproc visit, void *arg)
842 Py_ssize_t indexlo = deque->leftindex;
844 for (b = deque->leftblock; b != NULL; b = b->rightlink) {
845 const Py_ssize_t indexhi = b == deque->rightblock ?
846 deque->rightindex :
859 deque_copy(PyObject *deque)
861 if (((dequeobject *)deque)->maxlen == -1)
862 return PyObject_CallFunction((PyObject *)(Py_TYPE(deque)), "O", deque, NULL);
864 return PyObject_CallFunction((PyObject *)(Py_TYPE(deque)), "Oi",
865 deque, ((dequeobject *)deque)->maxlen, NULL);
868 PyDoc_STRVAR(copy_doc, "Return a shallow copy of a deque.");
871 deque_reduce(dequeobject *deque)
875 dict = PyObject_GetAttrString((PyObject *)deque, "__dict__");
878 aslist = PySequence_List((PyObject *)deque);
884 if (deque->maxlen == -1)
885 result = Py_BuildValue("O(O)", Py_TYPE(deque), aslist);
887 result = Py_BuildValue("O(On)", Py_TYPE(deque), aslist, deque->maxlen);
889 if (deque->maxlen == -1)
890 result = Py_BuildValue("O(OO)O", Py_TYPE(deque), aslist, Py_None, dict);
892 result = Py_BuildValue("O(On)O", Py_TYPE(deque), aslist, deque->maxlen, dict);
902 deque_repr(PyObject *deque)
907 i = Py_ReprEnter(deque);
914 aslist = PySequence_List(deque);
916 Py_ReprLeave(deque);
919 if (((dequeobject *)deque)->maxlen != -1)
920 fmt = PyString_FromFormat("deque(%%r, maxlen=%zd)",
921 ((dequeobject *)deque)->maxlen);
923 fmt = PyString_FromString("deque(%r)");
926 Py_ReprLeave(deque);
932 Py_ReprLeave(deque);
937 deque_tp_print(PyObject *deque, FILE *fp, int flags)
944 i = Py_ReprEnter(deque);
954 it = PyObject_GetIter(deque);
959 fputs("deque([", fp);
969 Py_ReprLeave(deque);
974 Py_ReprLeave(deque);
980 if (((dequeobject *)deque)->maxlen == -1)
983 fprintf(fp, "], maxlen=%" PY_FORMAT_SIZE_T "d)", ((dequeobject *)deque)->maxlen);
1043 /* We reached the end of one deque or both */
1052 case Py_NE: cmp = x != y; break; /* if one deque continues */
1068 deque_init(dequeobject *deque, PyObject *args, PyObject *kwdargs)
1075 if (!PyArg_ParseTupleAndKeywords(args, kwdargs, "|OO:deque", kwlist, &iterable, &maxlenobj))
1086 deque->maxlen = maxlen;
1087 if (deque->len > 0)
1088 deque_clear(deque);
1090 PyObject *rv = deque_extend(deque, iterable);
1099 deque_sizeof(dequeobject *deque, void *unused)
1104 res = _PyObject_SIZE(Py_TYPE(deque));
1105 blocks = (deque->leftindex + deque->len + BLOCKLEN - 1) / BLOCKLEN;
1106 assert(deque->leftindex + deque->len - 1 ==
1107 (blocks - 1) * BLOCKLEN + deque->rightindex);
1116 deque_get_maxlen(dequeobject *deque)
1118 if (deque->maxlen == -1)
1120 return PyInt_FromSsize_t(deque->maxlen);
1125 "maximum size of a deque or None if unbounded"},
1143 /* deque object ********************************************************/
1145 static PyObject *deque_iter(dequeobject *deque);
1146 static PyObject *deque_reviter(dequeobject *deque);
1148 "D.__reversed__() -- return a reverse iterator over the deque");
1185 "deque([iterable[, maxlen]]) --> deque object\n\
1191 "collections.deque", /* tp_name */
1233 /*********************** Deque Iterator **************************/
1239 dequeobject *deque;
1247 deque_iter(dequeobject *deque)
1254 it->b = deque->leftblock;
1255 it->index = deque->leftindex;
1256 Py_INCREF(deque);
1257 it->deque = deque;
1258 it->state = deque->state;
1259 it->counter = deque->len;
1267 Py_VISIT(dio->deque);
1274 Py_XDECREF(dio->deque);
1283 if (it->deque->state != it->state) {
1286 "deque mutated during iteration");
1291 assert (!(it->b == it->deque->rightblock &&
1292 it->index > it->deque->rightindex));
1352 /*********************** Deque Reverse Iterator **************************/
1357 deque_reviter(dequeobject *deque)
1364 it->b = deque->rightblock;
1365 it->index = deque->rightindex;
1366 Py_INCREF(deque);
1367 it->deque = deque;
1368 it->state = deque->state;
1369 it->counter = deque->len;
1381 if (it->deque->state != it->state) {
1384 "deque mutated during iteration");
1387 assert (!(it->b == it->deque->leftblock &&
1388 it->index < it->deque->leftindex));
1731 - deque: ordered collection accessible from endpoints only\n\
1747 PyModule_AddObject(m, "deque", (PyObject *)&deque_type);
