2 #include "structmember.h"
4 /* collections module implementation of a deque() datatype
5 Written and maintained by Raymond D. Hettinger <python@rcn.com>
6 Copyright (c) 2004 Python Software Foundation.
10 /* The block length may be set to any number over 1. Larger numbers
11 * reduce the number of calls to the memory allocator, give faster
12 * indexing and rotation, and reduce the link::data overhead ratio.
14 * Ideally, the block length will be set to two less than some
15 * multiple of the cache-line length (so that the full block
16 * including the leftlink and rightlink will fit neatly into
21 #define CENTER ((BLOCKLEN - 1) / 2)
23 /* A `dequeobject` is composed of a doubly-linked list of `block` nodes.
24 * This list is not circular (the leftmost block has leftlink==NULL,
25 * and the rightmost block has rightlink==NULL). A deque d's first
26 * element is at d.leftblock[leftindex] and its last element is at
27 * d.rightblock[rightindex]; note that, unlike as for Python slice
28 * indices, these indices are inclusive on both ends. By being inclusive
29 * on both ends, algorithms for left and right operations become
30 * symmetrical which simplifies the design.
32 * The list of blocks is never empty, so d.leftblock and d.rightblock
33 * are never equal to NULL.
35 * The indices, d.leftindex and d.rightindex are always in the range
36 * 0 <= index < BLOCKLEN.
37 * Their exact relationship is:
38 * (d.leftindex + d.len - 1) % BLOCKLEN == d.rightindex.
40 * Empty deques have d.len == 0; d.leftblock==d.rightblock;
41 * d.leftindex == CENTER+1; and d.rightindex == CENTER.
42 * Checking for d.len == 0 is the intended way to see whether d is empty.
44 * Whenever d.leftblock == d.rightblock,
45 * d.leftindex + d.len - 1 == d.rightindex.
47 * However, when d.leftblock != d.rightblock, d.leftindex and d.rightindex
48 * become indices into distinct blocks and either may be larger than the
52 typedef struct BLOCK
{
53 PyObject
*data
[BLOCKLEN
];
54 struct BLOCK
*rightlink
;
55 struct BLOCK
*leftlink
;
58 #define MAXFREEBLOCKS 10
59 static Py_ssize_t numfreeblocks
= 0;
60 static block
*freeblocks
[MAXFREEBLOCKS
];
63 newblock(block
*leftlink
, block
*rightlink
, Py_ssize_t len
) {
65 /* To prevent len from overflowing PY_SSIZE_T_MAX on 32-bit machines, we
66 * refuse to allocate new blocks if the current len is nearing overflow. */
67 if (len
>= PY_SSIZE_T_MAX
- 2*BLOCKLEN
) {
68 PyErr_SetString(PyExc_OverflowError
,
69 "cannot add more blocks to the deque");
74 b
= freeblocks
[numfreeblocks
];
76 b
= PyMem_Malloc(sizeof(block
));
82 b
->leftlink
= leftlink
;
83 b
->rightlink
= rightlink
;
90 if (numfreeblocks
< MAXFREEBLOCKS
) {
91 freeblocks
[numfreeblocks
] = b
;
102 Py_ssize_t leftindex
; /* in range(BLOCKLEN) */
103 Py_ssize_t rightindex
; /* in range(BLOCKLEN) */
105 long state
; /* incremented whenever the indices move */
107 PyObject
*weakreflist
; /* List of weak references */
110 /* The deque's size limit is d.maxlen. The limit can be zero or positive.
111 * If there is no limit, then d.maxlen == -1.
113 * After an item is added to a deque, we check to see if the size has grown past
114 * the limit. If it has, we get the size back down to the limit by popping an
115 * item off of the opposite end. The methods that can trigger this are append(),
116 * appendleft(), extend(), and extendleft().
119 #define TRIM(d, popfunction) \
120 if (d->maxlen != -1 && d->len > d->maxlen) { \
121 PyObject *rv = popfunction(d, NULL); \
122 assert(rv != NULL && d->len <= d->maxlen); \
126 static PyTypeObject deque_type
;
129 deque_new(PyTypeObject
*type
, PyObject
*args
, PyObject
*kwds
)
134 /* create dequeobject structure */
135 deque
= (dequeobject
*)type
->tp_alloc(type
, 0);
139 b
= newblock(NULL
, NULL
, 0);
145 assert(BLOCKLEN
>= 2);
146 deque
->leftblock
= b
;
147 deque
->rightblock
= b
;
148 deque
->leftindex
= CENTER
+ 1;
149 deque
->rightindex
= CENTER
;
152 deque
->weakreflist
= NULL
;
155 return (PyObject
*)deque
;
159 deque_pop(dequeobject
*deque
, PyObject
*unused
)
164 if (deque
->len
== 0) {
165 PyErr_SetString(PyExc_IndexError
, "pop from an empty deque");
168 item
= deque
->rightblock
->data
[deque
->rightindex
];
173 if (deque
->rightindex
== -1) {
174 if (deque
->len
== 0) {
175 assert(deque
->leftblock
== deque
->rightblock
);
176 assert(deque
->leftindex
== deque
->rightindex
+1);
177 /* re-center instead of freeing a block */
178 deque
->leftindex
= CENTER
+ 1;
179 deque
->rightindex
= CENTER
;
181 prevblock
= deque
->rightblock
->leftlink
;
182 assert(deque
->leftblock
!= deque
->rightblock
);
183 freeblock(deque
->rightblock
);
184 prevblock
->rightlink
= NULL
;
185 deque
->rightblock
= prevblock
;
186 deque
->rightindex
= BLOCKLEN
- 1;
192 PyDoc_STRVAR(pop_doc
, "Remove and return the rightmost element.");
195 deque_popleft(dequeobject
*deque
, PyObject
*unused
)
200 if (deque
->len
== 0) {
201 PyErr_SetString(PyExc_IndexError
, "pop from an empty deque");
204 assert(deque
->leftblock
!= NULL
);
205 item
= deque
->leftblock
->data
[deque
->leftindex
];
210 if (deque
->leftindex
== BLOCKLEN
) {
211 if (deque
->len
== 0) {
212 assert(deque
->leftblock
== deque
->rightblock
);
213 assert(deque
->leftindex
== deque
->rightindex
+1);
214 /* re-center instead of freeing a block */
215 deque
->leftindex
= CENTER
+ 1;
216 deque
->rightindex
= CENTER
;
218 assert(deque
->leftblock
!= deque
->rightblock
);
219 prevblock
= deque
->leftblock
->rightlink
;
220 freeblock(deque
->leftblock
);
221 assert(prevblock
!= NULL
);
222 prevblock
->leftlink
= NULL
;
223 deque
->leftblock
= prevblock
;
224 deque
->leftindex
= 0;
230 PyDoc_STRVAR(popleft_doc
, "Remove and return the leftmost element.");
233 deque_append(dequeobject
*deque
, PyObject
*item
)
236 if (deque
->rightindex
== BLOCKLEN
-1) {
237 block
*b
= newblock(deque
->rightblock
, NULL
, deque
->len
);
240 assert(deque
->rightblock
->rightlink
== NULL
);
241 deque
->rightblock
->rightlink
= b
;
242 deque
->rightblock
= b
;
243 deque
->rightindex
= -1;
248 deque
->rightblock
->data
[deque
->rightindex
] = item
;
249 TRIM(deque
, deque_popleft
);
253 PyDoc_STRVAR(append_doc
, "Add an element to the right side of the deque.");
256 deque_appendleft(dequeobject
*deque
, PyObject
*item
)
259 if (deque
->leftindex
== 0) {
260 block
*b
= newblock(NULL
, deque
->leftblock
, deque
->len
);
263 assert(deque
->leftblock
->leftlink
== NULL
);
264 deque
->leftblock
->leftlink
= b
;
265 deque
->leftblock
= b
;
266 deque
->leftindex
= BLOCKLEN
;
271 deque
->leftblock
->data
[deque
->leftindex
] = item
;
272 TRIM(deque
, deque_pop
);
276 PyDoc_STRVAR(appendleft_doc
, "Add an element to the left side of the deque.");
279 /* Run an iterator to exhaustion. Shortcut for
280 the extend/extendleft methods when maxlen == 0. */
282 consume_iterator(PyObject
*it
)
286 while ((item
= PyIter_Next(it
)) != NULL
) {
290 if (PyErr_Occurred())
296 deque_extend(dequeobject
*deque
, PyObject
*iterable
)
300 /* Handle case where id(deque) == id(iterable) */
301 if ((PyObject
*)deque
== iterable
) {
303 PyObject
*s
= PySequence_List(iterable
);
306 result
= deque_extend(deque
, s
);
311 it
= PyObject_GetIter(iterable
);
315 if (deque
->maxlen
== 0)
316 return consume_iterator(it
);
318 while ((item
= PyIter_Next(it
)) != NULL
) {
320 if (deque
->rightindex
== BLOCKLEN
-1) {
321 block
*b
= newblock(deque
->rightblock
, NULL
,
328 assert(deque
->rightblock
->rightlink
== NULL
);
329 deque
->rightblock
->rightlink
= b
;
330 deque
->rightblock
= b
;
331 deque
->rightindex
= -1;
335 deque
->rightblock
->data
[deque
->rightindex
] = item
;
336 TRIM(deque
, deque_popleft
);
339 if (PyErr_Occurred())
344 PyDoc_STRVAR(extend_doc
,
345 "Extend the right side of the deque with elements from the iterable");
348 deque_extendleft(dequeobject
*deque
, PyObject
*iterable
)
352 /* Handle case where id(deque) == id(iterable) */
353 if ((PyObject
*)deque
== iterable
) {
355 PyObject
*s
= PySequence_List(iterable
);
358 result
= deque_extendleft(deque
, s
);
363 it
= PyObject_GetIter(iterable
);
367 if (deque
->maxlen
== 0)
368 return consume_iterator(it
);
370 while ((item
= PyIter_Next(it
)) != NULL
) {
372 if (deque
->leftindex
== 0) {
373 block
*b
= newblock(NULL
, deque
->leftblock
,
380 assert(deque
->leftblock
->leftlink
== NULL
);
381 deque
->leftblock
->leftlink
= b
;
382 deque
->leftblock
= b
;
383 deque
->leftindex
= BLOCKLEN
;
387 deque
->leftblock
->data
[deque
->leftindex
] = item
;
388 TRIM(deque
, deque_pop
);
391 if (PyErr_Occurred())
396 PyDoc_STRVAR(extendleft_doc
,
397 "Extend the left side of the deque with elements from the iterable");
400 deque_inplace_concat(dequeobject
*deque
, PyObject
*other
)
404 result
= deque_extend(deque
, other
);
409 return (PyObject
*)deque
;
413 _deque_rotate(dequeobject
*deque
, Py_ssize_t n
)
415 Py_ssize_t m
, len
=deque
->len
, halflen
=len
>>1;
419 if (n
> halflen
|| n
< -halflen
) {
423 else if (n
< -halflen
)
427 assert(-halflen
<= n
&& n
<= halflen
);
431 if (deque
->leftindex
== 0) {
432 block
*b
= newblock(NULL
, deque
->leftblock
, len
);
435 assert(deque
->leftblock
->leftlink
== NULL
);
436 deque
->leftblock
->leftlink
= b
;
437 deque
->leftblock
= b
;
438 deque
->leftindex
= BLOCKLEN
;
440 assert(deque
->leftindex
> 0);
443 if (m
> deque
->rightindex
+ 1)
444 m
= deque
->rightindex
+ 1;
445 if (m
> deque
->leftindex
)
446 m
= deque
->leftindex
;
447 assert (m
> 0 && m
<= len
);
448 memcpy(&deque
->leftblock
->data
[deque
->leftindex
- m
],
449 &deque
->rightblock
->data
[deque
->rightindex
+ 1 - m
],
450 m
* sizeof(PyObject
*));
451 deque
->rightindex
-= m
;
452 deque
->leftindex
-= m
;
455 if (deque
->rightindex
== -1) {
456 block
*prevblock
= deque
->rightblock
->leftlink
;
457 assert(deque
->rightblock
!= NULL
);
458 assert(deque
->leftblock
!= deque
->rightblock
);
459 freeblock(deque
->rightblock
);
460 prevblock
->rightlink
= NULL
;
461 deque
->rightblock
= prevblock
;
462 deque
->rightindex
= BLOCKLEN
- 1;
466 if (deque
->rightindex
== BLOCKLEN
- 1) {
467 block
*b
= newblock(deque
->rightblock
, NULL
, len
);
470 assert(deque
->rightblock
->rightlink
== NULL
);
471 deque
->rightblock
->rightlink
= b
;
472 deque
->rightblock
= b
;
473 deque
->rightindex
= -1;
475 assert (deque
->rightindex
< BLOCKLEN
- 1);
478 if (m
> BLOCKLEN
- deque
->leftindex
)
479 m
= BLOCKLEN
- deque
->leftindex
;
480 if (m
> BLOCKLEN
- 1 - deque
->rightindex
)
481 m
= BLOCKLEN
- 1 - deque
->rightindex
;
482 assert (m
> 0 && m
<= len
);
483 memcpy(&deque
->rightblock
->data
[deque
->rightindex
+ 1],
484 &deque
->leftblock
->data
[deque
->leftindex
],
485 m
* sizeof(PyObject
*));
486 deque
->leftindex
+= m
;
487 deque
->rightindex
+= m
;
490 if (deque
->leftindex
== BLOCKLEN
) {
491 block
*nextblock
= deque
->leftblock
->rightlink
;
492 assert(deque
->leftblock
!= deque
->rightblock
);
493 freeblock(deque
->leftblock
);
494 assert(nextblock
!= NULL
);
495 nextblock
->leftlink
= NULL
;
496 deque
->leftblock
= nextblock
;
497 deque
->leftindex
= 0;
504 deque_rotate(dequeobject
*deque
, PyObject
*args
)
508 if (!PyArg_ParseTuple(args
, "|n:rotate", &n
))
510 if (_deque_rotate(deque
, n
) == 0)
515 PyDoc_STRVAR(rotate_doc
,
516 "Rotate the deque n steps to the right (default n=1). If n is negative, rotates left.");
519 deque_reverse(dequeobject
*deque
, PyObject
*unused
)
521 block
*leftblock
= deque
->leftblock
;
522 block
*rightblock
= deque
->rightblock
;
523 Py_ssize_t leftindex
= deque
->leftindex
;
524 Py_ssize_t rightindex
= deque
->rightindex
;
525 Py_ssize_t n
= (deque
->len
)/2;
529 for (i
=0 ; i
<n
; i
++) {
530 /* Validate that pointers haven't met in the middle */
531 assert(leftblock
!= rightblock
|| leftindex
< rightindex
);
534 tmp
= leftblock
->data
[leftindex
];
535 leftblock
->data
[leftindex
] = rightblock
->data
[rightindex
];
536 rightblock
->data
[rightindex
] = tmp
;
538 /* Advance left block/index pair */
540 if (leftindex
== BLOCKLEN
) {
541 if (leftblock
->rightlink
== NULL
)
543 leftblock
= leftblock
->rightlink
;
547 /* Step backwards with the right block/index pair */
549 if (rightindex
== -1) {
550 if (rightblock
->leftlink
== NULL
)
552 rightblock
= rightblock
->leftlink
;
553 rightindex
= BLOCKLEN
- 1;
559 PyDoc_STRVAR(reverse_doc
,
560 "D.reverse() -- reverse *IN PLACE*");
563 deque_count(dequeobject
*deque
, PyObject
*v
)
565 block
*leftblock
= deque
->leftblock
;
566 Py_ssize_t leftindex
= deque
->leftindex
;
567 Py_ssize_t n
= deque
->len
;
569 Py_ssize_t count
= 0;
571 long start_state
= deque
->state
;
574 for (i
=0 ; i
<n
; i
++) {
575 item
= leftblock
->data
[leftindex
];
576 cmp
= PyObject_RichCompareBool(item
, v
, Py_EQ
);
582 if (start_state
!= deque
->state
) {
583 PyErr_SetString(PyExc_RuntimeError
,
584 "deque mutated during iteration");
588 /* Advance left block/index pair */
590 if (leftindex
== BLOCKLEN
) {
591 if (leftblock
->rightlink
== NULL
) /* can occur when i==n-1 */
593 leftblock
= leftblock
->rightlink
;
597 return PyInt_FromSsize_t(count
);
600 PyDoc_STRVAR(count_doc
,
601 "D.count(value) -> integer -- return number of occurrences of value");
604 deque_len(dequeobject
*deque
)
610 deque_remove(dequeobject
*deque
, PyObject
*value
)
612 Py_ssize_t i
, n
=deque
->len
;
614 for (i
=0 ; i
<n
; i
++) {
615 PyObject
*item
= deque
->leftblock
->data
[deque
->leftindex
];
616 int cmp
= PyObject_RichCompareBool(item
, value
, Py_EQ
);
618 if (deque
->len
!= n
) {
619 PyErr_SetString(PyExc_IndexError
,
620 "deque mutated during remove().");
624 PyObject
*tgt
= deque_popleft(deque
, NULL
);
625 assert (tgt
!= NULL
);
626 if (_deque_rotate(deque
, i
))
632 _deque_rotate(deque
, i
);
635 _deque_rotate(deque
, -1);
637 PyErr_SetString(PyExc_ValueError
, "deque.remove(x): x not in deque");
641 PyDoc_STRVAR(remove_doc
,
642 "D.remove(value) -- remove first occurrence of value.");
645 deque_clear(dequeobject
*deque
)
650 item
= deque_pop(deque
, NULL
);
651 assert (item
!= NULL
);
654 assert(deque
->leftblock
== deque
->rightblock
&&
655 deque
->leftindex
- 1 == deque
->rightindex
&&
660 deque_item(dequeobject
*deque
, Py_ssize_t i
)
664 Py_ssize_t n
, index
=i
;
666 if (i
< 0 || i
>= deque
->len
) {
667 PyErr_SetString(PyExc_IndexError
,
668 "deque index out of range");
673 i
= deque
->leftindex
;
674 b
= deque
->leftblock
;
675 } else if (i
== deque
->len
- 1) {
676 i
= deque
->rightindex
;
677 b
= deque
->rightblock
;
679 i
+= deque
->leftindex
;
682 if (index
< (deque
->len
>> 1)) {
683 b
= deque
->leftblock
;
687 n
= (deque
->leftindex
+ deque
->len
- 1) / BLOCKLEN
- n
;
688 b
= deque
->rightblock
;
698 /* delitem() implemented in terms of rotate for simplicity and reasonable
699 performance near the end points. If for some reason this method becomes
700 popular, it is not hard to re-implement this using direct data movement
701 (similar to code in list slice assignment) and achieve a two or threefold
706 deque_del_item(dequeobject
*deque
, Py_ssize_t i
)
711 assert (i
>= 0 && i
< deque
->len
);
712 if (_deque_rotate(deque
, -i
))
714 item
= deque_popleft(deque
, NULL
);
715 rv
= _deque_rotate(deque
, i
);
716 assert (item
!= NULL
);
722 deque_ass_item(dequeobject
*deque
, Py_ssize_t i
, PyObject
*v
)
726 Py_ssize_t n
, len
=deque
->len
, halflen
=(len
+1)>>1, index
=i
;
728 if (i
< 0 || i
>= len
) {
729 PyErr_SetString(PyExc_IndexError
,
730 "deque index out of range");
734 return deque_del_item(deque
, i
);
736 i
+= deque
->leftindex
;
739 if (index
<= halflen
) {
740 b
= deque
->leftblock
;
744 n
= (deque
->leftindex
+ len
- 1) / BLOCKLEN
- n
;
745 b
= deque
->rightblock
;
750 old_value
= b
->data
[i
];
752 Py_DECREF(old_value
);
757 deque_clearmethod(dequeobject
*deque
)
763 PyDoc_STRVAR(clear_doc
, "Remove all elements from the deque.");
766 deque_dealloc(dequeobject
*deque
)
768 PyObject_GC_UnTrack(deque
);
769 if (deque
->weakreflist
!= NULL
)
770 PyObject_ClearWeakRefs((PyObject
*) deque
);
771 if (deque
->leftblock
!= NULL
) {
773 assert(deque
->leftblock
!= NULL
);
774 freeblock(deque
->leftblock
);
776 deque
->leftblock
= NULL
;
777 deque
->rightblock
= NULL
;
778 Py_TYPE(deque
)->tp_free(deque
);
782 deque_traverse(dequeobject
*deque
, visitproc visit
, void *arg
)
787 Py_ssize_t indexlo
= deque
->leftindex
;
789 for (b
= deque
->leftblock
; b
!= NULL
; b
= b
->rightlink
) {
790 const Py_ssize_t indexhi
= b
== deque
->rightblock
?
794 for (index
= indexlo
; index
<= indexhi
; ++index
) {
795 item
= b
->data
[index
];
804 deque_copy(PyObject
*deque
)
806 if (((dequeobject
*)deque
)->maxlen
== -1)
807 return PyObject_CallFunction((PyObject
*)(Py_TYPE(deque
)), "O", deque
, NULL
);
809 return PyObject_CallFunction((PyObject
*)(Py_TYPE(deque
)), "Oi",
810 deque
, ((dequeobject
*)deque
)->maxlen
, NULL
);
813 PyDoc_STRVAR(copy_doc
, "Return a shallow copy of a deque.");
816 deque_reduce(dequeobject
*deque
)
818 PyObject
*dict
, *result
, *aslist
;
820 dict
= PyObject_GetAttrString((PyObject
*)deque
, "__dict__");
823 aslist
= PySequence_List((PyObject
*)deque
);
824 if (aslist
== NULL
) {
829 if (deque
->maxlen
== -1)
830 result
= Py_BuildValue("O(O)", Py_TYPE(deque
), aslist
);
832 result
= Py_BuildValue("O(On)", Py_TYPE(deque
), aslist
, deque
->maxlen
);
834 if (deque
->maxlen
== -1)
835 result
= Py_BuildValue("O(OO)O", Py_TYPE(deque
), aslist
, Py_None
, dict
);
837 result
= Py_BuildValue("O(On)O", Py_TYPE(deque
), aslist
, deque
->maxlen
, dict
);
844 PyDoc_STRVAR(reduce_doc
, "Return state information for pickling.");
847 deque_repr(PyObject
*deque
)
849 PyObject
*aslist
, *result
, *fmt
;
852 i
= Py_ReprEnter(deque
);
856 return PyString_FromString("[...]");
859 aslist
= PySequence_List(deque
);
860 if (aslist
== NULL
) {
864 if (((dequeobject
*)deque
)->maxlen
!= -1)
865 fmt
= PyString_FromFormat("deque(%%r, maxlen=%zd)",
866 ((dequeobject
*)deque
)->maxlen
);
868 fmt
= PyString_FromString("deque(%r)");
874 result
= PyString_Format(fmt
, aslist
);
882 deque_tp_print(PyObject
*deque
, FILE *fp
, int flags
)
885 char *emit
= ""; /* No separator emitted on first pass */
886 char *separator
= ", ";
889 i
= Py_ReprEnter(deque
);
893 Py_BEGIN_ALLOW_THREADS
899 it
= PyObject_GetIter(deque
);
903 Py_BEGIN_ALLOW_THREADS
904 fputs("deque([", fp
);
906 while ((item
= PyIter_Next(it
)) != NULL
) {
907 Py_BEGIN_ALLOW_THREADS
911 if (PyObject_Print(item
, fp
, 0) != 0) {
921 if (PyErr_Occurred())
924 Py_BEGIN_ALLOW_THREADS
925 if (((dequeobject
*)deque
)->maxlen
== -1)
928 fprintf(fp
, "], maxlen=%" PY_FORMAT_SIZE_T
"d)", ((dequeobject
*)deque
)->maxlen
);
934 deque_richcompare(PyObject
*v
, PyObject
*w
, int op
)
936 PyObject
*it1
=NULL
, *it2
=NULL
, *x
, *y
;
940 if (!PyObject_TypeCheck(v
, &deque_type
) ||
941 !PyObject_TypeCheck(w
, &deque_type
)) {
942 Py_INCREF(Py_NotImplemented
);
943 return Py_NotImplemented
;
947 vs
= ((dequeobject
*)v
)->len
;
948 ws
= ((dequeobject
*)w
)->len
;
962 /* Search for the first index where items are different */
963 it1
= PyObject_GetIter(v
);
966 it2
= PyObject_GetIter(w
);
970 x
= PyIter_Next(it1
);
971 if (x
== NULL
&& PyErr_Occurred())
973 y
= PyIter_Next(it2
);
974 if (x
== NULL
|| y
== NULL
)
976 b
= PyObject_RichCompareBool(x
, y
, Py_EQ
);
978 cmp
= PyObject_RichCompareBool(x
, y
, op
);
988 /* We reached the end of one deque or both */
991 if (PyErr_Occurred())
994 case Py_LT
: cmp
= y
!= NULL
; break; /* if w was longer */
995 case Py_LE
: cmp
= x
== NULL
; break; /* if v was not longer */
996 case Py_EQ
: cmp
= x
== y
; break; /* if we reached the end of both */
997 case Py_NE
: cmp
= x
!= y
; break; /* if one deque continues */
998 case Py_GT
: cmp
= x
!= NULL
; break; /* if v was longer */
999 case Py_GE
: cmp
= y
== NULL
; break; /* if w was not longer */
1013 deque_init(dequeobject
*deque
, PyObject
*args
, PyObject
*kwdargs
)
1015 PyObject
*iterable
= NULL
;
1016 PyObject
*maxlenobj
= NULL
;
1017 Py_ssize_t maxlen
= -1;
1018 char *kwlist
[] = {"iterable", "maxlen", 0};
1020 if (!PyArg_ParseTupleAndKeywords(args
, kwdargs
, "|OO:deque", kwlist
, &iterable
, &maxlenobj
))
1022 if (maxlenobj
!= NULL
&& maxlenobj
!= Py_None
) {
1023 maxlen
= PyInt_AsSsize_t(maxlenobj
);
1024 if (maxlen
== -1 && PyErr_Occurred())
1027 PyErr_SetString(PyExc_ValueError
, "maxlen must be non-negative");
1031 deque
->maxlen
= maxlen
;
1033 if (iterable
!= NULL
) {
1034 PyObject
*rv
= deque_extend(deque
, iterable
);
1043 deque_sizeof(dequeobject
*deque
, void *unused
)
1048 res
= sizeof(dequeobject
);
1049 blocks
= (deque
->leftindex
+ deque
->len
+ BLOCKLEN
- 1) / BLOCKLEN
;
1050 assert(deque
->leftindex
+ deque
->len
- 1 ==
1051 (blocks
- 1) * BLOCKLEN
+ deque
->rightindex
);
1052 res
+= blocks
* sizeof(block
);
1053 return PyLong_FromSsize_t(res
);
1056 PyDoc_STRVAR(sizeof_doc
,
1057 "D.__sizeof__() -- size of D in memory, in bytes");
1060 deque_get_maxlen(dequeobject
*deque
)
1062 if (deque
->maxlen
== -1)
1064 return PyInt_FromSsize_t(deque
->maxlen
);
1067 static PyGetSetDef deque_getset
[] = {
1068 {"maxlen", (getter
)deque_get_maxlen
, (setter
)NULL
,
1069 "maximum size of a deque or None if unbounded"},
1073 static PySequenceMethods deque_as_sequence
= {
1074 (lenfunc
)deque_len
, /* sq_length */
1077 (ssizeargfunc
)deque_item
, /* sq_item */
1079 (ssizeobjargproc
)deque_ass_item
, /* sq_ass_item */
1080 0, /* sq_ass_slice */
1081 0, /* sq_contains */
1082 (binaryfunc
)deque_inplace_concat
, /* sq_inplace_concat */
1083 0, /* sq_inplace_repeat */
1087 /* deque object ********************************************************/
1089 static PyObject
*deque_iter(dequeobject
*deque
);
1090 static PyObject
*deque_reviter(dequeobject
*deque
);
1091 PyDoc_STRVAR(reversed_doc
,
1092 "D.__reversed__() -- return a reverse iterator over the deque");
1094 static PyMethodDef deque_methods
[] = {
1095 {"append", (PyCFunction
)deque_append
,
1096 METH_O
, append_doc
},
1097 {"appendleft", (PyCFunction
)deque_appendleft
,
1098 METH_O
, appendleft_doc
},
1099 {"clear", (PyCFunction
)deque_clearmethod
,
1100 METH_NOARGS
, clear_doc
},
1101 {"__copy__", (PyCFunction
)deque_copy
,
1102 METH_NOARGS
, copy_doc
},
1103 {"count", (PyCFunction
)deque_count
,
1105 {"extend", (PyCFunction
)deque_extend
,
1106 METH_O
, extend_doc
},
1107 {"extendleft", (PyCFunction
)deque_extendleft
,
1108 METH_O
, extendleft_doc
},
1109 {"pop", (PyCFunction
)deque_pop
,
1110 METH_NOARGS
, pop_doc
},
1111 {"popleft", (PyCFunction
)deque_popleft
,
1112 METH_NOARGS
, popleft_doc
},
1113 {"__reduce__", (PyCFunction
)deque_reduce
,
1114 METH_NOARGS
, reduce_doc
},
1115 {"remove", (PyCFunction
)deque_remove
,
1116 METH_O
, remove_doc
},
1117 {"__reversed__", (PyCFunction
)deque_reviter
,
1118 METH_NOARGS
, reversed_doc
},
1119 {"reverse", (PyCFunction
)deque_reverse
,
1120 METH_NOARGS
, reverse_doc
},
1121 {"rotate", (PyCFunction
)deque_rotate
,
1122 METH_VARARGS
, rotate_doc
},
1123 {"__sizeof__", (PyCFunction
)deque_sizeof
,
1124 METH_NOARGS
, sizeof_doc
},
1125 {NULL
, NULL
} /* sentinel */
1128 PyDoc_STRVAR(deque_doc
,
1129 "deque([iterable[, maxlen]]) --> deque object\n\
1131 Build an ordered collection with optimized access from its endpoints.");
1133 static PyTypeObject deque_type
= {
1134 PyVarObject_HEAD_INIT(NULL
, 0)
1135 "collections.deque", /* tp_name */
1136 sizeof(dequeobject
), /* tp_basicsize */
1137 0, /* tp_itemsize */
1139 (destructor
)deque_dealloc
, /* tp_dealloc */
1140 deque_tp_print
, /* tp_print */
1144 deque_repr
, /* tp_repr */
1145 0, /* tp_as_number */
1146 &deque_as_sequence
, /* tp_as_sequence */
1147 0, /* tp_as_mapping */
1148 (hashfunc
)PyObject_HashNotImplemented
, /* tp_hash */
1151 PyObject_GenericGetAttr
, /* tp_getattro */
1152 0, /* tp_setattro */
1153 0, /* tp_as_buffer */
1154 Py_TPFLAGS_DEFAULT
| Py_TPFLAGS_BASETYPE
| Py_TPFLAGS_HAVE_GC
|
1155 Py_TPFLAGS_HAVE_WEAKREFS
, /* tp_flags */
1156 deque_doc
, /* tp_doc */
1157 (traverseproc
)deque_traverse
, /* tp_traverse */
1158 (inquiry
)deque_clear
, /* tp_clear */
1159 (richcmpfunc
)deque_richcompare
, /* tp_richcompare */
1160 offsetof(dequeobject
, weakreflist
), /* tp_weaklistoffset*/
1161 (getiterfunc
)deque_iter
, /* tp_iter */
1162 0, /* tp_iternext */
1163 deque_methods
, /* tp_methods */
1165 deque_getset
, /* tp_getset */
1168 0, /* tp_descr_get */
1169 0, /* tp_descr_set */
1170 0, /* tp_dictoffset */
1171 (initproc
)deque_init
, /* tp_init */
1172 PyType_GenericAlloc
, /* tp_alloc */
1173 deque_new
, /* tp_new */
1174 PyObject_GC_Del
, /* tp_free */
1177 /*********************** Deque Iterator **************************/
1184 long state
; /* state when the iterator is created */
1185 Py_ssize_t counter
; /* number of items remaining for iteration */
1188 static PyTypeObject dequeiter_type
;
1191 deque_iter(dequeobject
*deque
)
1193 dequeiterobject
*it
;
1195 it
= PyObject_GC_New(dequeiterobject
, &dequeiter_type
);
1198 it
->b
= deque
->leftblock
;
1199 it
->index
= deque
->leftindex
;
1202 it
->state
= deque
->state
;
1203 it
->counter
= deque
->len
;
1204 PyObject_GC_Track(it
);
1205 return (PyObject
*)it
;
1209 dequeiter_traverse(dequeiterobject
*dio
, visitproc visit
, void *arg
)
1211 Py_VISIT(dio
->deque
);
1216 dequeiter_dealloc(dequeiterobject
*dio
)
1218 Py_XDECREF(dio
->deque
);
1219 PyObject_GC_Del(dio
);
1223 dequeiter_next(dequeiterobject
*it
)
1227 if (it
->deque
->state
!= it
->state
) {
1229 PyErr_SetString(PyExc_RuntimeError
,
1230 "deque mutated during iteration");
1233 if (it
->counter
== 0)
1235 assert (!(it
->b
== it
->deque
->rightblock
&&
1236 it
->index
> it
->deque
->rightindex
));
1238 item
= it
->b
->data
[it
->index
];
1241 if (it
->index
== BLOCKLEN
&& it
->counter
> 0) {
1242 assert (it
->b
->rightlink
!= NULL
);
1243 it
->b
= it
->b
->rightlink
;
1251 dequeiter_len(dequeiterobject
*it
)
1253 return PyInt_FromLong(it
->counter
);
1256 PyDoc_STRVAR(length_hint_doc
, "Private method returning an estimate of len(list(it)).");
1258 static PyMethodDef dequeiter_methods
[] = {
1259 {"__length_hint__", (PyCFunction
)dequeiter_len
, METH_NOARGS
, length_hint_doc
},
1260 {NULL
, NULL
} /* sentinel */
1263 static PyTypeObject dequeiter_type
= {
1264 PyVarObject_HEAD_INIT(NULL
, 0)
1265 "deque_iterator", /* tp_name */
1266 sizeof(dequeiterobject
), /* tp_basicsize */
1267 0, /* tp_itemsize */
1269 (destructor
)dequeiter_dealloc
, /* tp_dealloc */
1275 0, /* tp_as_number */
1276 0, /* tp_as_sequence */
1277 0, /* tp_as_mapping */
1281 PyObject_GenericGetAttr
, /* tp_getattro */
1282 0, /* tp_setattro */
1283 0, /* tp_as_buffer */
1284 Py_TPFLAGS_DEFAULT
| Py_TPFLAGS_HAVE_GC
,/* tp_flags */
1286 (traverseproc
)dequeiter_traverse
, /* tp_traverse */
1288 0, /* tp_richcompare */
1289 0, /* tp_weaklistoffset */
1290 PyObject_SelfIter
, /* tp_iter */
1291 (iternextfunc
)dequeiter_next
, /* tp_iternext */
1292 dequeiter_methods
, /* tp_methods */
1296 /*********************** Deque Reverse Iterator **************************/
1298 static PyTypeObject dequereviter_type
;
1301 deque_reviter(dequeobject
*deque
)
1303 dequeiterobject
*it
;
1305 it
= PyObject_GC_New(dequeiterobject
, &dequereviter_type
);
1308 it
->b
= deque
->rightblock
;
1309 it
->index
= deque
->rightindex
;
1312 it
->state
= deque
->state
;
1313 it
->counter
= deque
->len
;
1314 PyObject_GC_Track(it
);
1315 return (PyObject
*)it
;
1319 dequereviter_next(dequeiterobject
*it
)
1322 if (it
->counter
== 0)
1325 if (it
->deque
->state
!= it
->state
) {
1327 PyErr_SetString(PyExc_RuntimeError
,
1328 "deque mutated during iteration");
1331 assert (!(it
->b
== it
->deque
->leftblock
&&
1332 it
->index
< it
->deque
->leftindex
));
1334 item
= it
->b
->data
[it
->index
];
1337 if (it
->index
== -1 && it
->counter
> 0) {
1338 assert (it
->b
->leftlink
!= NULL
);
1339 it
->b
= it
->b
->leftlink
;
1340 it
->index
= BLOCKLEN
- 1;
1346 static PyTypeObject dequereviter_type
= {
1347 PyVarObject_HEAD_INIT(NULL
, 0)
1348 "deque_reverse_iterator", /* tp_name */
1349 sizeof(dequeiterobject
), /* tp_basicsize */
1350 0, /* tp_itemsize */
1352 (destructor
)dequeiter_dealloc
, /* tp_dealloc */
1358 0, /* tp_as_number */
1359 0, /* tp_as_sequence */
1360 0, /* tp_as_mapping */
1364 PyObject_GenericGetAttr
, /* tp_getattro */
1365 0, /* tp_setattro */
1366 0, /* tp_as_buffer */
1367 Py_TPFLAGS_DEFAULT
| Py_TPFLAGS_HAVE_GC
,/* tp_flags */
1369 (traverseproc
)dequeiter_traverse
, /* tp_traverse */
1371 0, /* tp_richcompare */
1372 0, /* tp_weaklistoffset */
1373 PyObject_SelfIter
, /* tp_iter */
1374 (iternextfunc
)dequereviter_next
, /* tp_iternext */
1375 dequeiter_methods
, /* tp_methods */
1379 /* defaultdict type *********************************************************/
1383 PyObject
*default_factory
;
1386 static PyTypeObject defdict_type
; /* Forward */
1388 PyDoc_STRVAR(defdict_missing_doc
,
1389 "__missing__(key) # Called by __getitem__ for missing key; pseudo-code:\n\
1390 if self.default_factory is None: raise KeyError((key,))\n\
1391 self[key] = value = self.default_factory()\n\
1396 defdict_missing(defdictobject
*dd
, PyObject
*key
)
1398 PyObject
*factory
= dd
->default_factory
;
1400 if (factory
== NULL
|| factory
== Py_None
) {
1401 /* XXX Call dict.__missing__(key) */
1403 tup
= PyTuple_Pack(1, key
);
1404 if (!tup
) return NULL
;
1405 PyErr_SetObject(PyExc_KeyError
, tup
);
1409 value
= PyEval_CallObject(factory
, NULL
);
1412 if (PyObject_SetItem((PyObject
*)dd
, key
, value
) < 0) {
1419 PyDoc_STRVAR(defdict_copy_doc
, "D.copy() -> a shallow copy of D.");
1422 defdict_copy(defdictobject
*dd
)
1424 /* This calls the object's class. That only works for subclasses
1425 whose class constructor has the same signature. Subclasses that
1426 define a different constructor signature must override copy().
1429 if (dd
->default_factory
== NULL
)
1430 return PyObject_CallFunctionObjArgs((PyObject
*)Py_TYPE(dd
), Py_None
, dd
, NULL
);
1431 return PyObject_CallFunctionObjArgs((PyObject
*)Py_TYPE(dd
),
1432 dd
->default_factory
, dd
, NULL
);
1436 defdict_reduce(defdictobject
*dd
)
1438 /* __reduce__ must return a 5-tuple as follows:
1441 - tuple of args for the factory function
1442 - additional state (here None)
1443 - sequence iterator (here None)
1444 - dictionary iterator (yielding successive (key, value) pairs
1446 This API is used by pickle.py and copy.py.
1448 For this to be useful with pickle.py, the default_factory
1449 must be picklable; e.g., None, a built-in, or a global
1450 function in a module or package.
1452 Both shallow and deep copying are supported, but for deep
1453 copying, the default_factory must be deep-copyable; e.g. None,
1454 or a built-in (functions are not copyable at this time).
1456 This only works for subclasses as long as their constructor
1457 signature is compatible; the first argument must be the
1458 optional default_factory, defaulting to None.
1463 if (dd
->default_factory
== NULL
|| dd
->default_factory
== Py_None
)
1464 args
= PyTuple_New(0);
1466 args
= PyTuple_Pack(1, dd
->default_factory
);
1469 items
= PyObject_CallMethod((PyObject
*)dd
, "iteritems", "()");
1470 if (items
== NULL
) {
1474 result
= PyTuple_Pack(5, Py_TYPE(dd
), args
,
1475 Py_None
, Py_None
, items
);
1481 static PyMethodDef defdict_methods
[] = {
1482 {"__missing__", (PyCFunction
)defdict_missing
, METH_O
,
1483 defdict_missing_doc
},
1484 {"copy", (PyCFunction
)defdict_copy
, METH_NOARGS
,
1486 {"__copy__", (PyCFunction
)defdict_copy
, METH_NOARGS
,
1488 {"__reduce__", (PyCFunction
)defdict_reduce
, METH_NOARGS
,
1493 static PyMemberDef defdict_members
[] = {
1494 {"default_factory", T_OBJECT
,
1495 offsetof(defdictobject
, default_factory
), 0,
1496 PyDoc_STR("Factory for default value called by __missing__().")},
1501 defdict_dealloc(defdictobject
*dd
)
1503 Py_CLEAR(dd
->default_factory
);
1504 PyDict_Type
.tp_dealloc((PyObject
*)dd
);
1508 defdict_print(defdictobject
*dd
, FILE *fp
, int flags
)
1511 Py_BEGIN_ALLOW_THREADS
1512 fprintf(fp
, "defaultdict(");
1513 Py_END_ALLOW_THREADS
1514 if (dd
->default_factory
== NULL
) {
1515 Py_BEGIN_ALLOW_THREADS
1516 fprintf(fp
, "None");
1517 Py_END_ALLOW_THREADS
1519 PyObject_Print(dd
->default_factory
, fp
, 0);
1521 Py_BEGIN_ALLOW_THREADS
1523 Py_END_ALLOW_THREADS
1524 sts
= PyDict_Type
.tp_print((PyObject
*)dd
, fp
, 0);
1525 Py_BEGIN_ALLOW_THREADS
1527 Py_END_ALLOW_THREADS
1532 defdict_repr(defdictobject
*dd
)
1537 baserepr
= PyDict_Type
.tp_repr((PyObject
*)dd
);
1538 if (baserepr
== NULL
)
1540 if (dd
->default_factory
== NULL
)
1541 defrepr
= PyString_FromString("None");
1544 int status
= Py_ReprEnter(dd
->default_factory
);
1547 Py_DECREF(baserepr
);
1550 defrepr
= PyString_FromString("...");
1553 defrepr
= PyObject_Repr(dd
->default_factory
);
1554 Py_ReprLeave(dd
->default_factory
);
1556 if (defrepr
== NULL
) {
1557 Py_DECREF(baserepr
);
1560 result
= PyString_FromFormat("defaultdict(%s, %s)",
1561 PyString_AS_STRING(defrepr
),
1562 PyString_AS_STRING(baserepr
));
1564 Py_DECREF(baserepr
);
1569 defdict_traverse(PyObject
*self
, visitproc visit
, void *arg
)
1571 Py_VISIT(((defdictobject
*)self
)->default_factory
);
1572 return PyDict_Type
.tp_traverse(self
, visit
, arg
);
1576 defdict_tp_clear(defdictobject
*dd
)
1578 Py_CLEAR(dd
->default_factory
);
1579 return PyDict_Type
.tp_clear((PyObject
*)dd
);
1583 defdict_init(PyObject
*self
, PyObject
*args
, PyObject
*kwds
)
1585 defdictobject
*dd
= (defdictobject
*)self
;
1586 PyObject
*olddefault
= dd
->default_factory
;
1587 PyObject
*newdefault
= NULL
;
1590 if (args
== NULL
|| !PyTuple_Check(args
))
1591 newargs
= PyTuple_New(0);
1593 Py_ssize_t n
= PyTuple_GET_SIZE(args
);
1595 newdefault
= PyTuple_GET_ITEM(args
, 0);
1596 if (!PyCallable_Check(newdefault
) && newdefault
!= Py_None
) {
1597 PyErr_SetString(PyExc_TypeError
,
1598 "first argument must be callable");
1602 newargs
= PySequence_GetSlice(args
, 1, n
);
1604 if (newargs
== NULL
)
1606 Py_XINCREF(newdefault
);
1607 dd
->default_factory
= newdefault
;
1608 result
= PyDict_Type
.tp_init(self
, newargs
, kwds
);
1610 Py_XDECREF(olddefault
);
1614 PyDoc_STRVAR(defdict_doc
,
1615 "defaultdict(default_factory[, ...]) --> dict with default factory\n\
1617 The default factory is called without arguments to produce\n\
1618 a new value when a key is not present, in __getitem__ only.\n\
1619 A defaultdict compares equal to a dict with the same items.\n\
1620 All remaining arguments are treated the same as if they were\n\
1621 passed to the dict constructor, including keyword arguments.\n\
1624 /* See comment in xxsubtype.c */
1625 #define DEFERRED_ADDRESS(ADDR) 0
1627 static PyTypeObject defdict_type
= {
1628 PyVarObject_HEAD_INIT(DEFERRED_ADDRESS(&PyType_Type
), 0)
1629 "collections.defaultdict", /* tp_name */
1630 sizeof(defdictobject
), /* tp_basicsize */
1631 0, /* tp_itemsize */
1633 (destructor
)defdict_dealloc
, /* tp_dealloc */
1634 (printfunc
)defdict_print
, /* tp_print */
1638 (reprfunc
)defdict_repr
, /* tp_repr */
1639 0, /* tp_as_number */
1640 0, /* tp_as_sequence */
1641 0, /* tp_as_mapping */
1645 PyObject_GenericGetAttr
, /* tp_getattro */
1646 0, /* tp_setattro */
1647 0, /* tp_as_buffer */
1648 Py_TPFLAGS_DEFAULT
| Py_TPFLAGS_BASETYPE
| Py_TPFLAGS_HAVE_GC
|
1649 Py_TPFLAGS_HAVE_WEAKREFS
, /* tp_flags */
1650 defdict_doc
, /* tp_doc */
1651 defdict_traverse
, /* tp_traverse */
1652 (inquiry
)defdict_tp_clear
, /* tp_clear */
1653 0, /* tp_richcompare */
1654 0, /* tp_weaklistoffset*/
1656 0, /* tp_iternext */
1657 defdict_methods
, /* tp_methods */
1658 defdict_members
, /* tp_members */
1660 DEFERRED_ADDRESS(&PyDict_Type
), /* tp_base */
1662 0, /* tp_descr_get */
1663 0, /* tp_descr_set */
1664 0, /* tp_dictoffset */
1665 defdict_init
, /* tp_init */
1666 PyType_GenericAlloc
, /* tp_alloc */
1668 PyObject_GC_Del
, /* tp_free */
1671 /* module level code ********************************************************/
1673 PyDoc_STRVAR(module_doc
,
1674 "High performance data structures.\n\
1675 - deque: ordered collection accessible from endpoints only\n\
1676 - defaultdict: dict subclass with a default value factory\n\
1680 init_collections(void)
1684 m
= Py_InitModule3("_collections", NULL
, module_doc
);
1688 if (PyType_Ready(&deque_type
) < 0)
1690 Py_INCREF(&deque_type
);
1691 PyModule_AddObject(m
, "deque", (PyObject
*)&deque_type
);
1693 defdict_type
.tp_base
= &PyDict_Type
;
1694 if (PyType_Ready(&defdict_type
) < 0)
1696 Py_INCREF(&defdict_type
);
1697 PyModule_AddObject(m
, "defaultdict", (PyObject
*)&defdict_type
);
1699 if (PyType_Ready(&dequeiter_type
) < 0)
1702 if (PyType_Ready(&dequereviter_type
) < 0)