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 but take more
12 * memory. Ideally, BLOCKLEN should be set with an eye to the
13 * length of a cache line.
17 #define CENTER ((BLOCKLEN - 1) / 2)
19 /* A `dequeobject` is composed of a doubly-linked list of `block` nodes.
20 * This list is not circular (the leftmost block has leftlink==NULL,
21 * and the rightmost block has rightlink==NULL). A deque d's first
22 * element is at d.leftblock[leftindex] and its last element is at
23 * d.rightblock[rightindex]; note that, unlike as for Python slice
24 * indices, these indices are inclusive on both ends. By being inclusive
25 * on both ends, algorithms for left and right operations become
26 * symmetrical which simplifies the design.
28 * The list of blocks is never empty, so d.leftblock and d.rightblock
29 * are never equal to NULL.
31 * The indices, d.leftindex and d.rightindex are always in the range
32 * 0 <= index < BLOCKLEN.
33 * Their exact relationship is:
34 * (d.leftindex + d.len - 1) % BLOCKLEN == d.rightindex.
36 * Empty deques have d.len == 0; d.leftblock==d.rightblock;
37 * d.leftindex == CENTER+1; and d.rightindex == CENTER.
38 * Checking for d.len == 0 is the intended way to see whether d is empty.
40 * Whenever d.leftblock == d.rightblock,
41 * d.leftindex + d.len - 1 == d.rightindex.
43 * However, when d.leftblock != d.rightblock, d.leftindex and d.rightindex
44 * become indices into distinct blocks and either may be larger than the
48 typedef struct BLOCK
{
49 struct BLOCK
*leftlink
;
50 struct BLOCK
*rightlink
;
51 PyObject
*data
[BLOCKLEN
];
54 #define MAXFREEBLOCKS 10
55 static int numfreeblocks
= 0;
56 static block
*freeblocks
[MAXFREEBLOCKS
];
59 newblock(block
*leftlink
, block
*rightlink
, int len
) {
61 /* To prevent len from overflowing INT_MAX on 64-bit machines, we
62 * refuse to allocate new blocks if the current len is dangerously
63 * close. There is some extra margin to prevent spurious arithmetic
64 * overflows at various places. The following check ensures that
65 * the blocks allocated to the deque, in the worst case, can only
66 * have INT_MAX-2 entries in total.
68 if (len
>= INT_MAX
- 2*BLOCKLEN
) {
69 PyErr_SetString(PyExc_OverflowError
,
70 "cannot add more blocks to the deque");
75 b
= freeblocks
[numfreeblocks
];
77 b
= PyMem_Malloc(sizeof(block
));
83 b
->leftlink
= leftlink
;
84 b
->rightlink
= rightlink
;
91 if (numfreeblocks
< MAXFREEBLOCKS
) {
92 freeblocks
[numfreeblocks
] = b
;
103 int leftindex
; /* in range(BLOCKLEN) */
104 int rightindex
; /* in range(BLOCKLEN) */
107 long state
; /* incremented whenever the indices move */
108 PyObject
*weakreflist
; /* List of weak references */
111 /* The deque's size limit is d.maxlen. The limit can be zero or positive.
112 * If there is no limit, then d.maxlen == -1.
114 * After an item is added to a deque, we check to see if the size has grown past
115 * the limit. If it has, we get the size back down to the limit by popping an
116 * item off of the opposite end. The methods that can trigger this are append(),
117 * appendleft(), extend(), and extendleft().
120 #define TRIM(d, popfunction) \
121 if (d->maxlen != -1 && d->len > d->maxlen) { \
122 PyObject *rv = popfunction(d, NULL); \
123 assert(rv != NULL && d->len <= d->maxlen); \
127 static PyTypeObject deque_type
;
130 deque_new(PyTypeObject
*type
, PyObject
*args
, PyObject
*kwds
)
135 /* create dequeobject structure */
136 deque
= (dequeobject
*)type
->tp_alloc(type
, 0);
140 b
= newblock(NULL
, NULL
, 0);
146 assert(BLOCKLEN
>= 2);
147 deque
->leftblock
= b
;
148 deque
->rightblock
= b
;
149 deque
->leftindex
= CENTER
+ 1;
150 deque
->rightindex
= CENTER
;
153 deque
->weakreflist
= NULL
;
156 return (PyObject
*)deque
;
160 deque_pop(dequeobject
*deque
, PyObject
*unused
)
165 if (deque
->len
== 0) {
166 PyErr_SetString(PyExc_IndexError
, "pop from an empty deque");
169 item
= deque
->rightblock
->data
[deque
->rightindex
];
174 if (deque
->rightindex
== -1) {
175 if (deque
->len
== 0) {
176 assert(deque
->leftblock
== deque
->rightblock
);
177 assert(deque
->leftindex
== deque
->rightindex
+1);
178 /* re-center instead of freeing a block */
179 deque
->leftindex
= CENTER
+ 1;
180 deque
->rightindex
= CENTER
;
182 prevblock
= deque
->rightblock
->leftlink
;
183 assert(deque
->leftblock
!= deque
->rightblock
);
184 freeblock(deque
->rightblock
);
185 prevblock
->rightlink
= NULL
;
186 deque
->rightblock
= prevblock
;
187 deque
->rightindex
= BLOCKLEN
- 1;
193 PyDoc_STRVAR(pop_doc
, "Remove and return the rightmost element.");
196 deque_popleft(dequeobject
*deque
, PyObject
*unused
)
201 if (deque
->len
== 0) {
202 PyErr_SetString(PyExc_IndexError
, "pop from an empty deque");
205 assert(deque
->leftblock
!= NULL
);
206 item
= deque
->leftblock
->data
[deque
->leftindex
];
211 if (deque
->leftindex
== BLOCKLEN
) {
212 if (deque
->len
== 0) {
213 assert(deque
->leftblock
== deque
->rightblock
);
214 assert(deque
->leftindex
== deque
->rightindex
+1);
215 /* re-center instead of freeing a block */
216 deque
->leftindex
= CENTER
+ 1;
217 deque
->rightindex
= CENTER
;
219 assert(deque
->leftblock
!= deque
->rightblock
);
220 prevblock
= deque
->leftblock
->rightlink
;
221 freeblock(deque
->leftblock
);
222 assert(prevblock
!= NULL
);
223 prevblock
->leftlink
= NULL
;
224 deque
->leftblock
= prevblock
;
225 deque
->leftindex
= 0;
231 PyDoc_STRVAR(popleft_doc
, "Remove and return the leftmost element.");
234 deque_append(dequeobject
*deque
, PyObject
*item
)
237 if (deque
->rightindex
== BLOCKLEN
-1) {
238 block
*b
= newblock(deque
->rightblock
, NULL
, deque
->len
);
241 assert(deque
->rightblock
->rightlink
== NULL
);
242 deque
->rightblock
->rightlink
= b
;
243 deque
->rightblock
= b
;
244 deque
->rightindex
= -1;
249 deque
->rightblock
->data
[deque
->rightindex
] = item
;
250 TRIM(deque
, deque_popleft
);
254 PyDoc_STRVAR(append_doc
, "Add an element to the right side of the deque.");
257 deque_appendleft(dequeobject
*deque
, PyObject
*item
)
260 if (deque
->leftindex
== 0) {
261 block
*b
= newblock(NULL
, deque
->leftblock
, deque
->len
);
264 assert(deque
->leftblock
->leftlink
== NULL
);
265 deque
->leftblock
->leftlink
= b
;
266 deque
->leftblock
= b
;
267 deque
->leftindex
= BLOCKLEN
;
272 deque
->leftblock
->data
[deque
->leftindex
] = item
;
273 TRIM(deque
, deque_pop
);
277 PyDoc_STRVAR(appendleft_doc
, "Add an element to the left side of the deque.");
280 deque_extend(dequeobject
*deque
, PyObject
*iterable
)
284 it
= PyObject_GetIter(iterable
);
288 while ((item
= PyIter_Next(it
)) != NULL
) {
290 if (deque
->rightindex
== BLOCKLEN
-1) {
291 block
*b
= newblock(deque
->rightblock
, NULL
,
298 assert(deque
->rightblock
->rightlink
== NULL
);
299 deque
->rightblock
->rightlink
= b
;
300 deque
->rightblock
= b
;
301 deque
->rightindex
= -1;
305 deque
->rightblock
->data
[deque
->rightindex
] = item
;
306 TRIM(deque
, deque_popleft
);
309 if (PyErr_Occurred())
314 PyDoc_STRVAR(extend_doc
,
315 "Extend the right side of the deque with elements from the iterable");
318 deque_extendleft(dequeobject
*deque
, PyObject
*iterable
)
322 it
= PyObject_GetIter(iterable
);
326 while ((item
= PyIter_Next(it
)) != NULL
) {
328 if (deque
->leftindex
== 0) {
329 block
*b
= newblock(NULL
, deque
->leftblock
,
336 assert(deque
->leftblock
->leftlink
== NULL
);
337 deque
->leftblock
->leftlink
= b
;
338 deque
->leftblock
= b
;
339 deque
->leftindex
= BLOCKLEN
;
343 deque
->leftblock
->data
[deque
->leftindex
] = item
;
344 TRIM(deque
, deque_pop
);
347 if (PyErr_Occurred())
352 PyDoc_STRVAR(extendleft_doc
,
353 "Extend the left side of the deque with elements from the iterable");
356 _deque_rotate(dequeobject
*deque
, Py_ssize_t n
)
358 int i
, len
=deque
->len
, halflen
=(len
+1)>>1;
363 if (n
> halflen
|| n
< -halflen
) {
367 else if (n
< -halflen
)
371 for (i
=0 ; i
<n
; i
++) {
372 item
= deque_pop(deque
, NULL
);
373 assert (item
!= NULL
);
374 rv
= deque_appendleft(deque
, item
);
380 for (i
=0 ; i
>n
; i
--) {
381 item
= deque_popleft(deque
, NULL
);
382 assert (item
!= NULL
);
383 rv
= deque_append(deque
, item
);
393 deque_rotate(dequeobject
*deque
, PyObject
*args
)
397 if (!PyArg_ParseTuple(args
, "|i:rotate", &n
))
399 if (_deque_rotate(deque
, n
) == 0)
404 PyDoc_STRVAR(rotate_doc
,
405 "Rotate the deque n steps to the right (default n=1). If n is negative, rotates left.");
408 deque_len(dequeobject
*deque
)
414 deque_remove(dequeobject
*deque
, PyObject
*value
)
416 Py_ssize_t i
, n
=deque
->len
;
418 for (i
=0 ; i
<n
; i
++) {
419 PyObject
*item
= deque
->leftblock
->data
[deque
->leftindex
];
420 int cmp
= PyObject_RichCompareBool(item
, value
, Py_EQ
);
422 if (deque
->len
!= n
) {
423 PyErr_SetString(PyExc_IndexError
,
424 "deque mutated during remove().");
428 PyObject
*tgt
= deque_popleft(deque
, NULL
);
429 assert (tgt
!= NULL
);
431 if (_deque_rotate(deque
, i
) == -1)
436 _deque_rotate(deque
, i
);
439 _deque_rotate(deque
, -1);
441 PyErr_SetString(PyExc_ValueError
, "deque.remove(x): x not in deque");
445 PyDoc_STRVAR(remove_doc
,
446 "D.remove(value) -- remove first occurrence of value.");
449 deque_clear(dequeobject
*deque
)
454 item
= deque_pop(deque
, NULL
);
455 assert (item
!= NULL
);
458 assert(deque
->leftblock
== deque
->rightblock
&&
459 deque
->leftindex
- 1 == deque
->rightindex
&&
465 deque_item(dequeobject
*deque
, int i
)
471 if (i
< 0 || i
>= deque
->len
) {
472 PyErr_SetString(PyExc_IndexError
,
473 "deque index out of range");
478 i
= deque
->leftindex
;
479 b
= deque
->leftblock
;
480 } else if (i
== deque
->len
- 1) {
481 i
= deque
->rightindex
;
482 b
= deque
->rightblock
;
484 i
+= deque
->leftindex
;
487 if (index
< (deque
->len
>> 1)) {
488 b
= deque
->leftblock
;
492 n
= (deque
->leftindex
+ deque
->len
- 1) / BLOCKLEN
- n
;
493 b
= deque
->rightblock
;
503 /* delitem() implemented in terms of rotate for simplicity and reasonable
504 performance near the end points. If for some reason this method becomes
505 popular, it is not hard to re-implement this using direct data movement
506 (similar to code in list slice assignment) and achieve a two or threefold
511 deque_del_item(dequeobject
*deque
, Py_ssize_t i
)
515 assert (i
>= 0 && i
< deque
->len
);
516 if (_deque_rotate(deque
, -i
) == -1)
519 item
= deque_popleft(deque
, NULL
);
520 assert (item
!= NULL
);
523 return _deque_rotate(deque
, i
);
527 deque_ass_item(dequeobject
*deque
, Py_ssize_t i
, PyObject
*v
)
531 Py_ssize_t n
, len
=deque
->len
, halflen
=(len
+1)>>1, index
=i
;
533 if (i
< 0 || i
>= len
) {
534 PyErr_SetString(PyExc_IndexError
,
535 "deque index out of range");
539 return deque_del_item(deque
, i
);
541 i
+= deque
->leftindex
;
544 if (index
<= halflen
) {
545 b
= deque
->leftblock
;
549 n
= (deque
->leftindex
+ len
- 1) / BLOCKLEN
- n
;
550 b
= deque
->rightblock
;
555 old_value
= b
->data
[i
];
557 Py_DECREF(old_value
);
562 deque_clearmethod(dequeobject
*deque
)
566 rv
= deque_clear(deque
);
571 PyDoc_STRVAR(clear_doc
, "Remove all elements from the deque.");
574 deque_dealloc(dequeobject
*deque
)
576 PyObject_GC_UnTrack(deque
);
577 if (deque
->weakreflist
!= NULL
)
578 PyObject_ClearWeakRefs((PyObject
*) deque
);
579 if (deque
->leftblock
!= NULL
) {
581 assert(deque
->leftblock
!= NULL
);
582 freeblock(deque
->leftblock
);
584 deque
->leftblock
= NULL
;
585 deque
->rightblock
= NULL
;
586 Py_TYPE(deque
)->tp_free(deque
);
590 deque_traverse(dequeobject
*deque
, visitproc visit
, void *arg
)
595 int indexlo
= deque
->leftindex
;
597 for (b
= deque
->leftblock
; b
!= NULL
; b
= b
->rightlink
) {
598 const int indexhi
= b
== deque
->rightblock
?
602 for (index
= indexlo
; index
<= indexhi
; ++index
) {
603 item
= b
->data
[index
];
612 deque_nohash(PyObject
*self
)
614 PyErr_SetString(PyExc_TypeError
, "deque objects are unhashable");
619 deque_copy(PyObject
*deque
)
621 if (((dequeobject
*)deque
)->maxlen
== -1)
622 return PyObject_CallFunction((PyObject
*)(Py_TYPE(deque
)), "O", deque
, NULL
);
624 return PyObject_CallFunction((PyObject
*)(Py_TYPE(deque
)), "Oi",
625 deque
, ((dequeobject
*)deque
)->maxlen
, NULL
);
628 PyDoc_STRVAR(copy_doc
, "Return a shallow copy of a deque.");
631 deque_reduce(dequeobject
*deque
)
633 PyObject
*dict
, *result
, *aslist
;
635 dict
= PyObject_GetAttrString((PyObject
*)deque
, "__dict__");
638 aslist
= PySequence_List((PyObject
*)deque
);
639 if (aslist
== NULL
) {
644 if (deque
->maxlen
== -1)
645 result
= Py_BuildValue("O(O)", Py_TYPE(deque
), aslist
);
647 result
= Py_BuildValue("O(Oi)", Py_TYPE(deque
), aslist
, deque
->maxlen
);
649 if (deque
->maxlen
== -1)
650 result
= Py_BuildValue("O(OO)O", Py_TYPE(deque
), aslist
, Py_None
, dict
);
652 result
= Py_BuildValue("O(Oi)O", Py_TYPE(deque
), aslist
, deque
->maxlen
, dict
);
659 PyDoc_STRVAR(reduce_doc
, "Return state information for pickling.");
662 deque_repr(PyObject
*deque
)
664 PyObject
*aslist
, *result
, *fmt
;
667 i
= Py_ReprEnter(deque
);
671 return PyString_FromString("[...]");
674 aslist
= PySequence_List(deque
);
675 if (aslist
== NULL
) {
679 if (((dequeobject
*)deque
)->maxlen
!= -1)
680 fmt
= PyString_FromFormat("deque(%%r, maxlen=%i)",
681 ((dequeobject
*)deque
)->maxlen
);
683 fmt
= PyString_FromString("deque(%r)");
689 result
= PyString_Format(fmt
, aslist
);
697 deque_tp_print(PyObject
*deque
, FILE *fp
, int flags
)
700 char *emit
= ""; /* No separator emitted on first pass */
701 char *separator
= ", ";
704 i
= Py_ReprEnter(deque
);
708 Py_BEGIN_ALLOW_THREADS
714 it
= PyObject_GetIter(deque
);
718 Py_BEGIN_ALLOW_THREADS
719 fputs("deque([", fp
);
721 while ((item
= PyIter_Next(it
)) != NULL
) {
722 Py_BEGIN_ALLOW_THREADS
726 if (PyObject_Print(item
, fp
, 0) != 0) {
736 if (PyErr_Occurred())
739 Py_BEGIN_ALLOW_THREADS
740 if (((dequeobject
*)deque
)->maxlen
== -1)
743 fprintf(fp
, "], maxlen=%d)", ((dequeobject
*)deque
)->maxlen
);
749 deque_richcompare(PyObject
*v
, PyObject
*w
, int op
)
751 PyObject
*it1
=NULL
, *it2
=NULL
, *x
, *y
;
752 int b
, vs
, ws
, cmp
=-1;
754 if (!PyObject_TypeCheck(v
, &deque_type
) ||
755 !PyObject_TypeCheck(w
, &deque_type
)) {
756 Py_INCREF(Py_NotImplemented
);
757 return Py_NotImplemented
;
761 vs
= ((dequeobject
*)v
)->len
;
762 ws
= ((dequeobject
*)w
)->len
;
776 /* Search for the first index where items are different */
777 it1
= PyObject_GetIter(v
);
780 it2
= PyObject_GetIter(w
);
784 x
= PyIter_Next(it1
);
785 if (x
== NULL
&& PyErr_Occurred())
787 y
= PyIter_Next(it2
);
788 if (x
== NULL
|| y
== NULL
)
790 b
= PyObject_RichCompareBool(x
, y
, Py_EQ
);
792 cmp
= PyObject_RichCompareBool(x
, y
, op
);
802 /* We reached the end of one deque or both */
805 if (PyErr_Occurred())
808 case Py_LT
: cmp
= y
!= NULL
; break; /* if w was longer */
809 case Py_LE
: cmp
= x
== NULL
; break; /* if v was not longer */
810 case Py_EQ
: cmp
= x
== y
; break; /* if we reached the end of both */
811 case Py_NE
: cmp
= x
!= y
; break; /* if one deque continues */
812 case Py_GT
: cmp
= x
!= NULL
; break; /* if v was longer */
813 case Py_GE
: cmp
= y
== NULL
; break; /* if w was not longer */
827 deque_init(dequeobject
*deque
, PyObject
*args
, PyObject
*kwdargs
)
829 PyObject
*iterable
= NULL
;
830 PyObject
*maxlenobj
= NULL
;
832 char *kwlist
[] = {"iterable", "maxlen", 0};
834 if (!PyArg_ParseTupleAndKeywords(args
, kwdargs
, "|OO:deque", kwlist
, &iterable
, &maxlenobj
))
836 if (maxlenobj
!= NULL
&& maxlenobj
!= Py_None
) {
837 maxlen
= PyInt_AsLong(maxlenobj
);
838 if (maxlen
== -1 && PyErr_Occurred())
841 PyErr_SetString(PyExc_ValueError
, "maxlen must be non-negative");
845 deque
->maxlen
= maxlen
;
847 if (iterable
!= NULL
) {
848 PyObject
*rv
= deque_extend(deque
, iterable
);
856 static PySequenceMethods deque_as_sequence
= {
857 (lenfunc
)deque_len
, /* sq_length */
860 (ssizeargfunc
)deque_item
, /* sq_item */
862 (ssizeobjargproc
)deque_ass_item
, /* sq_ass_item */
865 /* deque object ********************************************************/
867 static PyObject
*deque_iter(dequeobject
*deque
);
868 static PyObject
*deque_reviter(dequeobject
*deque
);
869 PyDoc_STRVAR(reversed_doc
,
870 "D.__reversed__() -- return a reverse iterator over the deque");
872 static PyMethodDef deque_methods
[] = {
873 {"append", (PyCFunction
)deque_append
,
875 {"appendleft", (PyCFunction
)deque_appendleft
,
876 METH_O
, appendleft_doc
},
877 {"clear", (PyCFunction
)deque_clearmethod
,
878 METH_NOARGS
, clear_doc
},
879 {"__copy__", (PyCFunction
)deque_copy
,
880 METH_NOARGS
, copy_doc
},
881 {"extend", (PyCFunction
)deque_extend
,
883 {"extendleft", (PyCFunction
)deque_extendleft
,
884 METH_O
, extendleft_doc
},
885 {"pop", (PyCFunction
)deque_pop
,
886 METH_NOARGS
, pop_doc
},
887 {"popleft", (PyCFunction
)deque_popleft
,
888 METH_NOARGS
, popleft_doc
},
889 {"__reduce__", (PyCFunction
)deque_reduce
,
890 METH_NOARGS
, reduce_doc
},
891 {"remove", (PyCFunction
)deque_remove
,
893 {"__reversed__", (PyCFunction
)deque_reviter
,
894 METH_NOARGS
, reversed_doc
},
895 {"rotate", (PyCFunction
)deque_rotate
,
896 METH_VARARGS
, rotate_doc
},
897 {NULL
, NULL
} /* sentinel */
900 PyDoc_STRVAR(deque_doc
,
901 "deque(iterable[, maxlen]) --> deque object\n\
903 Build an ordered collection accessible from endpoints only.");
905 static PyTypeObject deque_type
= {
906 PyVarObject_HEAD_INIT(NULL
, 0)
907 "collections.deque", /* tp_name */
908 sizeof(dequeobject
), /* tp_basicsize */
911 (destructor
)deque_dealloc
, /* tp_dealloc */
912 deque_tp_print
, /* tp_print */
916 deque_repr
, /* tp_repr */
917 0, /* tp_as_number */
918 &deque_as_sequence
, /* tp_as_sequence */
919 0, /* tp_as_mapping */
920 deque_nohash
, /* tp_hash */
923 PyObject_GenericGetAttr
, /* tp_getattro */
925 0, /* tp_as_buffer */
926 Py_TPFLAGS_DEFAULT
| Py_TPFLAGS_BASETYPE
| Py_TPFLAGS_HAVE_GC
|
927 Py_TPFLAGS_HAVE_WEAKREFS
, /* tp_flags */
928 deque_doc
, /* tp_doc */
929 (traverseproc
)deque_traverse
, /* tp_traverse */
930 (inquiry
)deque_clear
, /* tp_clear */
931 (richcmpfunc
)deque_richcompare
, /* tp_richcompare */
932 offsetof(dequeobject
, weakreflist
), /* tp_weaklistoffset*/
933 (getiterfunc
)deque_iter
, /* tp_iter */
935 deque_methods
, /* tp_methods */
940 0, /* tp_descr_get */
941 0, /* tp_descr_set */
942 0, /* tp_dictoffset */
943 (initproc
)deque_init
, /* tp_init */
944 PyType_GenericAlloc
, /* tp_alloc */
945 deque_new
, /* tp_new */
946 PyObject_GC_Del
, /* tp_free */
949 /*********************** Deque Iterator **************************/
956 long state
; /* state when the iterator is created */
957 int counter
; /* number of items remaining for iteration */
960 PyTypeObject dequeiter_type
;
963 deque_iter(dequeobject
*deque
)
967 it
= PyObject_New(dequeiterobject
, &dequeiter_type
);
970 it
->b
= deque
->leftblock
;
971 it
->index
= deque
->leftindex
;
974 it
->state
= deque
->state
;
975 it
->counter
= deque
->len
;
976 return (PyObject
*)it
;
980 dequeiter_dealloc(dequeiterobject
*dio
)
982 Py_XDECREF(dio
->deque
);
983 Py_TYPE(dio
)->tp_free(dio
);
987 dequeiter_next(dequeiterobject
*it
)
991 if (it
->deque
->state
!= it
->state
) {
993 PyErr_SetString(PyExc_RuntimeError
,
994 "deque mutated during iteration");
997 if (it
->counter
== 0)
999 assert (!(it
->b
== it
->deque
->rightblock
&&
1000 it
->index
> it
->deque
->rightindex
));
1002 item
= it
->b
->data
[it
->index
];
1005 if (it
->index
== BLOCKLEN
&& it
->counter
> 0) {
1006 assert (it
->b
->rightlink
!= NULL
);
1007 it
->b
= it
->b
->rightlink
;
1015 dequeiter_len(dequeiterobject
*it
)
1017 return PyInt_FromLong(it
->counter
);
1020 PyDoc_STRVAR(length_hint_doc
, "Private method returning an estimate of len(list(it)).");
1022 static PyMethodDef dequeiter_methods
[] = {
1023 {"__length_hint__", (PyCFunction
)dequeiter_len
, METH_NOARGS
, length_hint_doc
},
1024 {NULL
, NULL
} /* sentinel */
1027 PyTypeObject dequeiter_type
= {
1028 PyVarObject_HEAD_INIT(NULL
, 0)
1029 "deque_iterator", /* tp_name */
1030 sizeof(dequeiterobject
), /* tp_basicsize */
1031 0, /* tp_itemsize */
1033 (destructor
)dequeiter_dealloc
, /* tp_dealloc */
1039 0, /* tp_as_number */
1040 0, /* tp_as_sequence */
1041 0, /* tp_as_mapping */
1045 PyObject_GenericGetAttr
, /* tp_getattro */
1046 0, /* tp_setattro */
1047 0, /* tp_as_buffer */
1048 Py_TPFLAGS_DEFAULT
, /* tp_flags */
1050 0, /* tp_traverse */
1052 0, /* tp_richcompare */
1053 0, /* tp_weaklistoffset */
1054 PyObject_SelfIter
, /* tp_iter */
1055 (iternextfunc
)dequeiter_next
, /* tp_iternext */
1056 dequeiter_methods
, /* tp_methods */
1060 /*********************** Deque Reverse Iterator **************************/
1062 PyTypeObject dequereviter_type
;
1065 deque_reviter(dequeobject
*deque
)
1067 dequeiterobject
*it
;
1069 it
= PyObject_New(dequeiterobject
, &dequereviter_type
);
1072 it
->b
= deque
->rightblock
;
1073 it
->index
= deque
->rightindex
;
1076 it
->state
= deque
->state
;
1077 it
->counter
= deque
->len
;
1078 return (PyObject
*)it
;
1082 dequereviter_next(dequeiterobject
*it
)
1085 if (it
->counter
== 0)
1088 if (it
->deque
->state
!= it
->state
) {
1090 PyErr_SetString(PyExc_RuntimeError
,
1091 "deque mutated during iteration");
1094 assert (!(it
->b
== it
->deque
->leftblock
&&
1095 it
->index
< it
->deque
->leftindex
));
1097 item
= it
->b
->data
[it
->index
];
1100 if (it
->index
== -1 && it
->counter
> 0) {
1101 assert (it
->b
->leftlink
!= NULL
);
1102 it
->b
= it
->b
->leftlink
;
1103 it
->index
= BLOCKLEN
- 1;
1109 PyTypeObject dequereviter_type
= {
1110 PyVarObject_HEAD_INIT(NULL
, 0)
1111 "deque_reverse_iterator", /* tp_name */
1112 sizeof(dequeiterobject
), /* tp_basicsize */
1113 0, /* tp_itemsize */
1115 (destructor
)dequeiter_dealloc
, /* tp_dealloc */
1121 0, /* tp_as_number */
1122 0, /* tp_as_sequence */
1123 0, /* tp_as_mapping */
1127 PyObject_GenericGetAttr
, /* tp_getattro */
1128 0, /* tp_setattro */
1129 0, /* tp_as_buffer */
1130 Py_TPFLAGS_DEFAULT
, /* tp_flags */
1132 0, /* tp_traverse */
1134 0, /* tp_richcompare */
1135 0, /* tp_weaklistoffset */
1136 PyObject_SelfIter
, /* tp_iter */
1137 (iternextfunc
)dequereviter_next
, /* tp_iternext */
1138 dequeiter_methods
, /* tp_methods */
1142 /* defaultdict type *********************************************************/
1146 PyObject
*default_factory
;
1149 static PyTypeObject defdict_type
; /* Forward */
1151 PyDoc_STRVAR(defdict_missing_doc
,
1152 "__missing__(key) # Called by __getitem__ for missing key; pseudo-code:\n\
1153 if self.default_factory is None: raise KeyError((key,))\n\
1154 self[key] = value = self.default_factory()\n\
1159 defdict_missing(defdictobject
*dd
, PyObject
*key
)
1161 PyObject
*factory
= dd
->default_factory
;
1163 if (factory
== NULL
|| factory
== Py_None
) {
1164 /* XXX Call dict.__missing__(key) */
1166 tup
= PyTuple_Pack(1, key
);
1167 if (!tup
) return NULL
;
1168 PyErr_SetObject(PyExc_KeyError
, tup
);
1172 value
= PyEval_CallObject(factory
, NULL
);
1175 if (PyObject_SetItem((PyObject
*)dd
, key
, value
) < 0) {
1182 PyDoc_STRVAR(defdict_copy_doc
, "D.copy() -> a shallow copy of D.");
1185 defdict_copy(defdictobject
*dd
)
1187 /* This calls the object's class. That only works for subclasses
1188 whose class constructor has the same signature. Subclasses that
1189 define a different constructor signature must override copy().
1191 return PyObject_CallFunctionObjArgs((PyObject
*)Py_TYPE(dd
),
1192 dd
->default_factory
, dd
, NULL
);
1196 defdict_reduce(defdictobject
*dd
)
1198 /* __reduce__ must return a 5-tuple as follows:
1201 - tuple of args for the factory function
1202 - additional state (here None)
1203 - sequence iterator (here None)
1204 - dictionary iterator (yielding successive (key, value) pairs
1206 This API is used by pickle.py and copy.py.
1208 For this to be useful with pickle.py, the default_factory
1209 must be picklable; e.g., None, a built-in, or a global
1210 function in a module or package.
1212 Both shallow and deep copying are supported, but for deep
1213 copying, the default_factory must be deep-copyable; e.g. None,
1214 or a built-in (functions are not copyable at this time).
1216 This only works for subclasses as long as their constructor
1217 signature is compatible; the first argument must be the
1218 optional default_factory, defaulting to None.
1223 if (dd
->default_factory
== NULL
|| dd
->default_factory
== Py_None
)
1224 args
= PyTuple_New(0);
1226 args
= PyTuple_Pack(1, dd
->default_factory
);
1229 items
= PyObject_CallMethod((PyObject
*)dd
, "iteritems", "()");
1230 if (items
== NULL
) {
1234 result
= PyTuple_Pack(5, Py_TYPE(dd
), args
,
1235 Py_None
, Py_None
, items
);
1241 static PyMethodDef defdict_methods
[] = {
1242 {"__missing__", (PyCFunction
)defdict_missing
, METH_O
,
1243 defdict_missing_doc
},
1244 {"copy", (PyCFunction
)defdict_copy
, METH_NOARGS
,
1246 {"__copy__", (PyCFunction
)defdict_copy
, METH_NOARGS
,
1248 {"__reduce__", (PyCFunction
)defdict_reduce
, METH_NOARGS
,
1253 static PyMemberDef defdict_members
[] = {
1254 {"default_factory", T_OBJECT
,
1255 offsetof(defdictobject
, default_factory
), 0,
1256 PyDoc_STR("Factory for default value called by __missing__().")},
1261 defdict_dealloc(defdictobject
*dd
)
1263 Py_CLEAR(dd
->default_factory
);
1264 PyDict_Type
.tp_dealloc((PyObject
*)dd
);
1268 defdict_print(defdictobject
*dd
, FILE *fp
, int flags
)
1271 Py_BEGIN_ALLOW_THREADS
1272 fprintf(fp
, "defaultdict(");
1273 Py_END_ALLOW_THREADS
1274 if (dd
->default_factory
== NULL
) {
1275 Py_BEGIN_ALLOW_THREADS
1276 fprintf(fp
, "None");
1277 Py_END_ALLOW_THREADS
1279 PyObject_Print(dd
->default_factory
, fp
, 0);
1281 Py_BEGIN_ALLOW_THREADS
1283 Py_END_ALLOW_THREADS
1284 sts
= PyDict_Type
.tp_print((PyObject
*)dd
, fp
, 0);
1285 Py_BEGIN_ALLOW_THREADS
1287 Py_END_ALLOW_THREADS
1292 defdict_repr(defdictobject
*dd
)
1297 baserepr
= PyDict_Type
.tp_repr((PyObject
*)dd
);
1298 if (baserepr
== NULL
)
1300 if (dd
->default_factory
== NULL
)
1301 defrepr
= PyString_FromString("None");
1304 int status
= Py_ReprEnter(dd
->default_factory
);
1308 defrepr
= PyString_FromString("...");
1311 defrepr
= PyObject_Repr(dd
->default_factory
);
1312 Py_ReprLeave(dd
->default_factory
);
1314 if (defrepr
== NULL
) {
1315 Py_DECREF(baserepr
);
1318 result
= PyString_FromFormat("defaultdict(%s, %s)",
1319 PyString_AS_STRING(defrepr
),
1320 PyString_AS_STRING(baserepr
));
1322 Py_DECREF(baserepr
);
1327 defdict_traverse(PyObject
*self
, visitproc visit
, void *arg
)
1329 Py_VISIT(((defdictobject
*)self
)->default_factory
);
1330 return PyDict_Type
.tp_traverse(self
, visit
, arg
);
1334 defdict_tp_clear(defdictobject
*dd
)
1336 Py_CLEAR(dd
->default_factory
);
1337 return PyDict_Type
.tp_clear((PyObject
*)dd
);
1341 defdict_init(PyObject
*self
, PyObject
*args
, PyObject
*kwds
)
1343 defdictobject
*dd
= (defdictobject
*)self
;
1344 PyObject
*olddefault
= dd
->default_factory
;
1345 PyObject
*newdefault
= NULL
;
1348 if (args
== NULL
|| !PyTuple_Check(args
))
1349 newargs
= PyTuple_New(0);
1351 Py_ssize_t n
= PyTuple_GET_SIZE(args
);
1353 newdefault
= PyTuple_GET_ITEM(args
, 0);
1354 if (!PyCallable_Check(newdefault
)) {
1355 PyErr_SetString(PyExc_TypeError
,
1356 "first argument must be callable");
1360 newargs
= PySequence_GetSlice(args
, 1, n
);
1362 if (newargs
== NULL
)
1364 Py_XINCREF(newdefault
);
1365 dd
->default_factory
= newdefault
;
1366 result
= PyDict_Type
.tp_init(self
, newargs
, kwds
);
1368 Py_XDECREF(olddefault
);
1372 PyDoc_STRVAR(defdict_doc
,
1373 "defaultdict(default_factory) --> dict with default factory\n\
1375 The default factory is called without arguments to produce\n\
1376 a new value when a key is not present, in __getitem__ only.\n\
1377 A defaultdict compares equal to a dict with the same items.\n\
1380 /* See comment in xxsubtype.c */
1381 #define DEFERRED_ADDRESS(ADDR) 0
1383 static PyTypeObject defdict_type
= {
1384 PyVarObject_HEAD_INIT(DEFERRED_ADDRESS(&PyType_Type
), 0)
1385 "collections.defaultdict", /* tp_name */
1386 sizeof(defdictobject
), /* tp_basicsize */
1387 0, /* tp_itemsize */
1389 (destructor
)defdict_dealloc
, /* tp_dealloc */
1390 (printfunc
)defdict_print
, /* tp_print */
1394 (reprfunc
)defdict_repr
, /* tp_repr */
1395 0, /* tp_as_number */
1396 0, /* tp_as_sequence */
1397 0, /* tp_as_mapping */
1401 PyObject_GenericGetAttr
, /* tp_getattro */
1402 0, /* tp_setattro */
1403 0, /* tp_as_buffer */
1404 Py_TPFLAGS_DEFAULT
| Py_TPFLAGS_BASETYPE
| Py_TPFLAGS_HAVE_GC
|
1405 Py_TPFLAGS_HAVE_WEAKREFS
, /* tp_flags */
1406 defdict_doc
, /* tp_doc */
1407 defdict_traverse
, /* tp_traverse */
1408 (inquiry
)defdict_tp_clear
, /* tp_clear */
1409 0, /* tp_richcompare */
1410 0, /* tp_weaklistoffset*/
1412 0, /* tp_iternext */
1413 defdict_methods
, /* tp_methods */
1414 defdict_members
, /* tp_members */
1416 DEFERRED_ADDRESS(&PyDict_Type
), /* tp_base */
1418 0, /* tp_descr_get */
1419 0, /* tp_descr_set */
1420 0, /* tp_dictoffset */
1421 defdict_init
, /* tp_init */
1422 PyType_GenericAlloc
, /* tp_alloc */
1424 PyObject_GC_Del
, /* tp_free */
1427 /* module level code ********************************************************/
1429 PyDoc_STRVAR(module_doc
,
1430 "High performance data structures.\n\
1431 - deque: ordered collection accessible from endpoints only\n\
1432 - defaultdict: dict subclass with a default value factory\n\
1436 init_collections(void)
1440 m
= Py_InitModule3("_collections", NULL
, module_doc
);
1444 if (PyType_Ready(&deque_type
) < 0)
1446 Py_INCREF(&deque_type
);
1447 PyModule_AddObject(m
, "deque", (PyObject
*)&deque_type
);
1449 defdict_type
.tp_base
= &PyDict_Type
;
1450 if (PyType_Ready(&defdict_type
) < 0)
1452 Py_INCREF(&defdict_type
);
1453 PyModule_AddObject(m
, "defaultdict", (PyObject
*)&defdict_type
);
1455 if (PyType_Ready(&dequeiter_type
) < 0)
1458 if (PyType_Ready(&dequereviter_type
) < 0)