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
];
55 newblock(block
*leftlink
, block
*rightlink
, int len
) {
57 /* To prevent len from overflowing INT_MAX on 64-bit machines, we
58 * refuse to allocate new blocks if the current len is dangerously
59 * close. There is some extra margin to prevent spurious arithmetic
60 * overflows at various places. The following check ensures that
61 * the blocks allocated to the deque, in the worst case, can only
62 * have INT_MAX-2 entries in total.
64 if (len
>= INT_MAX
- 2*BLOCKLEN
) {
65 PyErr_SetString(PyExc_OverflowError
,
66 "cannot add more blocks to the deque");
69 b
= PyMem_Malloc(sizeof(block
));
74 b
->leftlink
= leftlink
;
75 b
->rightlink
= rightlink
;
83 int leftindex
; /* in range(BLOCKLEN) */
84 int rightindex
; /* in range(BLOCKLEN) */
86 long state
; /* incremented whenever the indices move */
87 PyObject
*weakreflist
; /* List of weak references */
90 static PyTypeObject deque_type
;
93 deque_new(PyTypeObject
*type
, PyObject
*args
, PyObject
*kwds
)
98 if (!_PyArg_NoKeywords("deque()", kwds
))
101 /* create dequeobject structure */
102 deque
= (dequeobject
*)type
->tp_alloc(type
, 0);
106 b
= newblock(NULL
, NULL
, 0);
112 assert(BLOCKLEN
>= 2);
113 deque
->leftblock
= b
;
114 deque
->rightblock
= b
;
115 deque
->leftindex
= CENTER
+ 1;
116 deque
->rightindex
= CENTER
;
119 deque
->weakreflist
= NULL
;
121 return (PyObject
*)deque
;
125 deque_append(dequeobject
*deque
, PyObject
*item
)
128 if (deque
->rightindex
== BLOCKLEN
-1) {
129 block
*b
= newblock(deque
->rightblock
, NULL
, deque
->len
);
132 assert(deque
->rightblock
->rightlink
== NULL
);
133 deque
->rightblock
->rightlink
= b
;
134 deque
->rightblock
= b
;
135 deque
->rightindex
= -1;
140 deque
->rightblock
->data
[deque
->rightindex
] = item
;
144 PyDoc_STRVAR(append_doc
, "Add an element to the right side of the deque.");
147 deque_appendleft(dequeobject
*deque
, PyObject
*item
)
150 if (deque
->leftindex
== 0) {
151 block
*b
= newblock(NULL
, deque
->leftblock
, deque
->len
);
154 assert(deque
->leftblock
->leftlink
== NULL
);
155 deque
->leftblock
->leftlink
= b
;
156 deque
->leftblock
= b
;
157 deque
->leftindex
= BLOCKLEN
;
162 deque
->leftblock
->data
[deque
->leftindex
] = item
;
166 PyDoc_STRVAR(appendleft_doc
, "Add an element to the left side of the deque.");
169 deque_pop(dequeobject
*deque
, PyObject
*unused
)
174 if (deque
->len
== 0) {
175 PyErr_SetString(PyExc_IndexError
, "pop from an empty deque");
178 item
= deque
->rightblock
->data
[deque
->rightindex
];
183 if (deque
->rightindex
== -1) {
184 if (deque
->len
== 0) {
185 assert(deque
->leftblock
== deque
->rightblock
);
186 assert(deque
->leftindex
== deque
->rightindex
+1);
187 /* re-center instead of freeing a block */
188 deque
->leftindex
= CENTER
+ 1;
189 deque
->rightindex
= CENTER
;
191 prevblock
= deque
->rightblock
->leftlink
;
192 assert(deque
->leftblock
!= deque
->rightblock
);
193 PyMem_Free(deque
->rightblock
);
194 prevblock
->rightlink
= NULL
;
195 deque
->rightblock
= prevblock
;
196 deque
->rightindex
= BLOCKLEN
- 1;
202 PyDoc_STRVAR(pop_doc
, "Remove and return the rightmost element.");
205 deque_popleft(dequeobject
*deque
, PyObject
*unused
)
210 if (deque
->len
== 0) {
211 PyErr_SetString(PyExc_IndexError
, "pop from an empty deque");
214 item
= deque
->leftblock
->data
[deque
->leftindex
];
219 if (deque
->leftindex
== BLOCKLEN
) {
220 if (deque
->len
== 0) {
221 assert(deque
->leftblock
== deque
->rightblock
);
222 assert(deque
->leftindex
== deque
->rightindex
+1);
223 /* re-center instead of freeing a block */
224 deque
->leftindex
= CENTER
+ 1;
225 deque
->rightindex
= CENTER
;
227 assert(deque
->leftblock
!= deque
->rightblock
);
228 prevblock
= deque
->leftblock
->rightlink
;
229 assert(deque
->leftblock
!= NULL
);
230 PyMem_Free(deque
->leftblock
);
231 assert(prevblock
!= NULL
);
232 prevblock
->leftlink
= NULL
;
233 deque
->leftblock
= prevblock
;
234 deque
->leftindex
= 0;
240 PyDoc_STRVAR(popleft_doc
, "Remove and return the leftmost element.");
243 deque_extend(dequeobject
*deque
, PyObject
*iterable
)
247 it
= PyObject_GetIter(iterable
);
251 while ((item
= PyIter_Next(it
)) != NULL
) {
253 if (deque
->rightindex
== BLOCKLEN
-1) {
254 block
*b
= newblock(deque
->rightblock
, NULL
,
261 assert(deque
->rightblock
->rightlink
== NULL
);
262 deque
->rightblock
->rightlink
= b
;
263 deque
->rightblock
= b
;
264 deque
->rightindex
= -1;
268 deque
->rightblock
->data
[deque
->rightindex
] = item
;
271 if (PyErr_Occurred())
276 PyDoc_STRVAR(extend_doc
,
277 "Extend the right side of the deque with elements from the iterable");
280 deque_extendleft(dequeobject
*deque
, PyObject
*iterable
)
284 it
= PyObject_GetIter(iterable
);
288 while ((item
= PyIter_Next(it
)) != NULL
) {
290 if (deque
->leftindex
== 0) {
291 block
*b
= newblock(NULL
, deque
->leftblock
,
298 assert(deque
->leftblock
->leftlink
== NULL
);
299 deque
->leftblock
->leftlink
= b
;
300 deque
->leftblock
= b
;
301 deque
->leftindex
= BLOCKLEN
;
305 deque
->leftblock
->data
[deque
->leftindex
] = item
;
308 if (PyErr_Occurred())
313 PyDoc_STRVAR(extendleft_doc
,
314 "Extend the left side of the deque with elements from the iterable");
317 _deque_rotate(dequeobject
*deque
, int n
)
319 int i
, len
=deque
->len
, halflen
=(len
+1)>>1;
324 if (n
> halflen
|| n
< -halflen
) {
328 else if (n
< -halflen
)
332 for (i
=0 ; i
<n
; i
++) {
333 item
= deque_pop(deque
, NULL
);
334 assert (item
!= NULL
);
335 rv
= deque_appendleft(deque
, item
);
341 for (i
=0 ; i
>n
; i
--) {
342 item
= deque_popleft(deque
, NULL
);
343 assert (item
!= NULL
);
344 rv
= deque_append(deque
, item
);
354 deque_rotate(dequeobject
*deque
, PyObject
*args
)
358 if (!PyArg_ParseTuple(args
, "|i:rotate", &n
))
360 if (_deque_rotate(deque
, n
) == 0)
365 PyDoc_STRVAR(rotate_doc
,
366 "Rotate the deque n steps to the right (default n=1). If n is negative, rotates left.");
369 deque_len(dequeobject
*deque
)
375 deque_remove(dequeobject
*deque
, PyObject
*value
)
379 for (i
=0 ; i
<n
; i
++) {
380 PyObject
*item
= deque
->leftblock
->data
[deque
->leftindex
];
381 int cmp
= PyObject_RichCompareBool(item
, value
, Py_EQ
);
383 if (deque
->len
!= n
) {
384 PyErr_SetString(PyExc_IndexError
,
385 "deque mutated during remove().");
389 PyObject
*tgt
= deque_popleft(deque
, NULL
);
390 assert (tgt
!= NULL
);
392 if (_deque_rotate(deque
, i
) == -1)
397 _deque_rotate(deque
, i
);
400 _deque_rotate(deque
, -1);
402 PyErr_SetString(PyExc_ValueError
, "deque.remove(x): x not in deque");
406 PyDoc_STRVAR(remove_doc
,
407 "D.remove(value) -- remove first occurrence of value.");
410 deque_clear(dequeobject
*deque
)
415 item
= deque_pop(deque
, NULL
);
416 assert (item
!= NULL
);
419 assert(deque
->leftblock
== deque
->rightblock
&&
420 deque
->leftindex
- 1 == deque
->rightindex
&&
426 deque_item(dequeobject
*deque
, int i
)
432 if (i
< 0 || i
>= deque
->len
) {
433 PyErr_SetString(PyExc_IndexError
,
434 "deque index out of range");
439 i
= deque
->leftindex
;
440 b
= deque
->leftblock
;
441 } else if (i
== deque
->len
- 1) {
442 i
= deque
->rightindex
;
443 b
= deque
->rightblock
;
445 i
+= deque
->leftindex
;
448 if (index
< (deque
->len
>> 1)) {
449 b
= deque
->leftblock
;
453 n
= (deque
->leftindex
+ deque
->len
- 1) / BLOCKLEN
- n
;
454 b
= deque
->rightblock
;
464 /* delitem() implemented in terms of rotate for simplicity and reasonable
465 performance near the end points. If for some reason this method becomes
466 popular, it is not hard to re-implement this using direct data movement
467 (similar to code in list slice assignment) and achieve a two or threefold
472 deque_del_item(dequeobject
*deque
, int i
)
476 assert (i
>= 0 && i
< deque
->len
);
477 if (_deque_rotate(deque
, -i
) == -1)
480 item
= deque_popleft(deque
, NULL
);
481 assert (item
!= NULL
);
484 return _deque_rotate(deque
, i
);
488 deque_ass_item(dequeobject
*deque
, int i
, PyObject
*v
)
492 int n
, len
=deque
->len
, halflen
=(len
+1)>>1, index
=i
;
494 if (i
< 0 || i
>= len
) {
495 PyErr_SetString(PyExc_IndexError
,
496 "deque index out of range");
500 return deque_del_item(deque
, i
);
502 i
+= deque
->leftindex
;
505 if (index
<= halflen
) {
506 b
= deque
->leftblock
;
510 n
= (deque
->leftindex
+ len
- 1) / BLOCKLEN
- n
;
511 b
= deque
->rightblock
;
516 old_value
= b
->data
[i
];
518 Py_DECREF(old_value
);
523 deque_clearmethod(dequeobject
*deque
)
527 rv
= deque_clear(deque
);
532 PyDoc_STRVAR(clear_doc
, "Remove all elements from the deque.");
535 deque_dealloc(dequeobject
*deque
)
537 PyObject_GC_UnTrack(deque
);
538 if (deque
->weakreflist
!= NULL
)
539 PyObject_ClearWeakRefs((PyObject
*) deque
);
540 if (deque
->leftblock
!= NULL
) {
542 assert(deque
->leftblock
!= NULL
);
543 PyMem_Free(deque
->leftblock
);
545 deque
->leftblock
= NULL
;
546 deque
->rightblock
= NULL
;
547 deque
->ob_type
->tp_free(deque
);
551 deque_traverse(dequeobject
*deque
, visitproc visit
, void *arg
)
556 int indexlo
= deque
->leftindex
;
558 for (b
= deque
->leftblock
; b
!= NULL
; b
= b
->rightlink
) {
559 const int indexhi
= b
== deque
->rightblock
?
563 for (index
= indexlo
; index
<= indexhi
; ++index
) {
564 item
= b
->data
[index
];
573 deque_nohash(PyObject
*self
)
575 PyErr_SetString(PyExc_TypeError
, "deque objects are unhashable");
580 deque_copy(PyObject
*deque
)
582 return PyObject_CallFunctionObjArgs((PyObject
*)(deque
->ob_type
),
586 PyDoc_STRVAR(copy_doc
, "Return a shallow copy of a deque.");
589 deque_reduce(dequeobject
*deque
)
591 PyObject
*dict
, *result
, *it
;
593 dict
= PyObject_GetAttrString((PyObject
*)deque
, "__dict__");
599 it
= PyObject_GetIter((PyObject
*)deque
);
604 result
= Py_BuildValue("O()ON", deque
->ob_type
, dict
, it
);
609 PyDoc_STRVAR(reduce_doc
, "Return state information for pickling.");
612 deque_repr(PyObject
*deque
)
614 PyObject
*aslist
, *result
, *fmt
;
617 i
= Py_ReprEnter(deque
);
621 return PyString_FromString("[...]");
624 aslist
= PySequence_List(deque
);
625 if (aslist
== NULL
) {
630 fmt
= PyString_FromString("deque(%r)");
636 result
= PyString_Format(fmt
, aslist
);
644 deque_tp_print(PyObject
*deque
, FILE *fp
, int flags
)
647 char *emit
= ""; /* No separator emitted on first pass */
648 char *separator
= ", ";
651 i
= Py_ReprEnter(deque
);
659 it
= PyObject_GetIter(deque
);
663 fputs("deque([", fp
);
664 while ((item
= PyIter_Next(it
)) != NULL
) {
667 if (PyObject_Print(item
, fp
, 0) != 0) {
677 if (PyErr_Occurred())
684 deque_richcompare(PyObject
*v
, PyObject
*w
, int op
)
686 PyObject
*it1
=NULL
, *it2
=NULL
, *x
, *y
;
687 int b
, vs
, ws
, cmp
=-1;
689 if (!PyObject_TypeCheck(v
, &deque_type
) ||
690 !PyObject_TypeCheck(w
, &deque_type
)) {
691 Py_INCREF(Py_NotImplemented
);
692 return Py_NotImplemented
;
696 vs
= ((dequeobject
*)v
)->len
;
697 ws
= ((dequeobject
*)w
)->len
;
711 /* Search for the first index where items are different */
712 it1
= PyObject_GetIter(v
);
715 it2
= PyObject_GetIter(w
);
719 x
= PyIter_Next(it1
);
720 if (x
== NULL
&& PyErr_Occurred())
722 y
= PyIter_Next(it2
);
723 if (x
== NULL
|| y
== NULL
)
725 b
= PyObject_RichCompareBool(x
, y
, Py_EQ
);
727 cmp
= PyObject_RichCompareBool(x
, y
, op
);
737 /* We reached the end of one deque or both */
740 if (PyErr_Occurred())
743 case Py_LT
: cmp
= y
!= NULL
; break; /* if w was longer */
744 case Py_LE
: cmp
= x
== NULL
; break; /* if v was not longer */
745 case Py_EQ
: cmp
= x
== y
; break; /* if we reached the end of both */
746 case Py_NE
: cmp
= x
!= y
; break; /* if one deque continues */
747 case Py_GT
: cmp
= x
!= NULL
; break; /* if v was longer */
748 case Py_GE
: cmp
= y
== NULL
; break; /* if w was not longer */
762 deque_init(dequeobject
*deque
, PyObject
*args
, PyObject
*kwds
)
764 PyObject
*iterable
= NULL
;
766 if (!PyArg_UnpackTuple(args
, "deque", 0, 1, &iterable
))
769 if (iterable
!= NULL
) {
770 PyObject
*rv
= deque_extend(deque
, iterable
);
778 static PySequenceMethods deque_as_sequence
= {
779 (inquiry
)deque_len
, /* sq_length */
782 (intargfunc
)deque_item
, /* sq_item */
784 (intobjargproc
)deque_ass_item
, /* sq_ass_item */
787 /* deque object ********************************************************/
789 static PyObject
*deque_iter(dequeobject
*deque
);
790 static PyObject
*deque_reviter(dequeobject
*deque
);
791 PyDoc_STRVAR(reversed_doc
,
792 "D.__reversed__() -- return a reverse iterator over the deque");
794 static PyMethodDef deque_methods
[] = {
795 {"append", (PyCFunction
)deque_append
,
797 {"appendleft", (PyCFunction
)deque_appendleft
,
798 METH_O
, appendleft_doc
},
799 {"clear", (PyCFunction
)deque_clearmethod
,
800 METH_NOARGS
, clear_doc
},
801 {"__copy__", (PyCFunction
)deque_copy
,
802 METH_NOARGS
, copy_doc
},
803 {"extend", (PyCFunction
)deque_extend
,
805 {"extendleft", (PyCFunction
)deque_extendleft
,
806 METH_O
, extendleft_doc
},
807 {"pop", (PyCFunction
)deque_pop
,
808 METH_NOARGS
, pop_doc
},
809 {"popleft", (PyCFunction
)deque_popleft
,
810 METH_NOARGS
, popleft_doc
},
811 {"__reduce__", (PyCFunction
)deque_reduce
,
812 METH_NOARGS
, reduce_doc
},
813 {"remove", (PyCFunction
)deque_remove
,
815 {"__reversed__", (PyCFunction
)deque_reviter
,
816 METH_NOARGS
, reversed_doc
},
817 {"rotate", (PyCFunction
)deque_rotate
,
818 METH_VARARGS
, rotate_doc
},
819 {NULL
, NULL
} /* sentinel */
822 PyDoc_STRVAR(deque_doc
,
823 "deque(iterable) --> deque object\n\
825 Build an ordered collection accessible from endpoints only.");
827 static PyTypeObject deque_type
= {
828 PyObject_HEAD_INIT(NULL
)
830 "collections.deque", /* tp_name */
831 sizeof(dequeobject
), /* tp_basicsize */
834 (destructor
)deque_dealloc
, /* tp_dealloc */
835 (printfunc
)deque_tp_print
, /* tp_print */
839 (reprfunc
)deque_repr
, /* tp_repr */
840 0, /* tp_as_number */
841 &deque_as_sequence
, /* tp_as_sequence */
842 0, /* tp_as_mapping */
843 deque_nohash
, /* tp_hash */
846 PyObject_GenericGetAttr
, /* tp_getattro */
848 0, /* tp_as_buffer */
849 Py_TPFLAGS_DEFAULT
| Py_TPFLAGS_BASETYPE
| Py_TPFLAGS_HAVE_GC
|
850 Py_TPFLAGS_HAVE_WEAKREFS
, /* tp_flags */
851 deque_doc
, /* tp_doc */
852 (traverseproc
)deque_traverse
, /* tp_traverse */
853 (inquiry
)deque_clear
, /* tp_clear */
854 (richcmpfunc
)deque_richcompare
, /* tp_richcompare */
855 offsetof(dequeobject
, weakreflist
), /* tp_weaklistoffset*/
856 (getiterfunc
)deque_iter
, /* tp_iter */
858 deque_methods
, /* tp_methods */
863 0, /* tp_descr_get */
864 0, /* tp_descr_set */
865 0, /* tp_dictoffset */
866 (initproc
)deque_init
, /* tp_init */
867 PyType_GenericAlloc
, /* tp_alloc */
868 deque_new
, /* tp_new */
869 PyObject_GC_Del
, /* tp_free */
872 /*********************** Deque Iterator **************************/
879 long state
; /* state when the iterator is created */
880 int counter
; /* number of items remaining for iteration */
883 PyTypeObject dequeiter_type
;
886 deque_iter(dequeobject
*deque
)
890 it
= PyObject_New(dequeiterobject
, &dequeiter_type
);
893 it
->b
= deque
->leftblock
;
894 it
->index
= deque
->leftindex
;
897 it
->state
= deque
->state
;
898 it
->counter
= deque
->len
;
899 return (PyObject
*)it
;
903 dequeiter_dealloc(dequeiterobject
*dio
)
905 Py_XDECREF(dio
->deque
);
906 dio
->ob_type
->tp_free(dio
);
910 dequeiter_next(dequeiterobject
*it
)
914 if (it
->counter
== 0)
917 if (it
->deque
->state
!= it
->state
) {
919 PyErr_SetString(PyExc_RuntimeError
,
920 "deque mutated during iteration");
923 assert (!(it
->b
== it
->deque
->rightblock
&&
924 it
->index
> it
->deque
->rightindex
));
926 item
= it
->b
->data
[it
->index
];
929 if (it
->index
== BLOCKLEN
&& it
->counter
> 0) {
930 assert (it
->b
->rightlink
!= NULL
);
931 it
->b
= it
->b
->rightlink
;
939 dequeiter_len(dequeiterobject
*it
)
941 return PyInt_FromLong(it
->counter
);
944 PyDoc_STRVAR(length_cue_doc
, "Private method returning an estimate of len(list(it)).");
946 static PyMethodDef dequeiter_methods
[] = {
947 {"_length_cue", (PyCFunction
)dequeiter_len
, METH_NOARGS
, length_cue_doc
},
948 {NULL
, NULL
} /* sentinel */
951 PyTypeObject dequeiter_type
= {
952 PyObject_HEAD_INIT(NULL
)
954 "deque_iterator", /* tp_name */
955 sizeof(dequeiterobject
), /* tp_basicsize */
958 (destructor
)dequeiter_dealloc
, /* tp_dealloc */
964 0, /* tp_as_number */
965 0, /* tp_as_sequence */
966 0, /* tp_as_mapping */
970 PyObject_GenericGetAttr
, /* tp_getattro */
972 0, /* tp_as_buffer */
973 Py_TPFLAGS_DEFAULT
, /* tp_flags */
977 0, /* tp_richcompare */
978 0, /* tp_weaklistoffset */
979 PyObject_SelfIter
, /* tp_iter */
980 (iternextfunc
)dequeiter_next
, /* tp_iternext */
981 dequeiter_methods
, /* tp_methods */
985 /*********************** Deque Reverse Iterator **************************/
987 PyTypeObject dequereviter_type
;
990 deque_reviter(dequeobject
*deque
)
994 it
= PyObject_New(dequeiterobject
, &dequereviter_type
);
997 it
->b
= deque
->rightblock
;
998 it
->index
= deque
->rightindex
;
1001 it
->state
= deque
->state
;
1002 it
->counter
= deque
->len
;
1003 return (PyObject
*)it
;
1007 dequereviter_next(dequeiterobject
*it
)
1010 if (it
->counter
== 0)
1013 if (it
->deque
->state
!= it
->state
) {
1015 PyErr_SetString(PyExc_RuntimeError
,
1016 "deque mutated during iteration");
1019 assert (!(it
->b
== it
->deque
->leftblock
&&
1020 it
->index
< it
->deque
->leftindex
));
1022 item
= it
->b
->data
[it
->index
];
1025 if (it
->index
== -1 && it
->counter
> 0) {
1026 assert (it
->b
->leftlink
!= NULL
);
1027 it
->b
= it
->b
->leftlink
;
1028 it
->index
= BLOCKLEN
- 1;
1034 PyTypeObject dequereviter_type
= {
1035 PyObject_HEAD_INIT(NULL
)
1037 "deque_reverse_iterator", /* tp_name */
1038 sizeof(dequeiterobject
), /* tp_basicsize */
1039 0, /* tp_itemsize */
1041 (destructor
)dequeiter_dealloc
, /* tp_dealloc */
1047 0, /* tp_as_number */
1048 0, /* tp_as_sequence */
1049 0, /* tp_as_mapping */
1053 PyObject_GenericGetAttr
, /* tp_getattro */
1054 0, /* tp_setattro */
1055 0, /* tp_as_buffer */
1056 Py_TPFLAGS_DEFAULT
, /* tp_flags */
1058 0, /* tp_traverse */
1060 0, /* tp_richcompare */
1061 0, /* tp_weaklistoffset */
1062 PyObject_SelfIter
, /* tp_iter */
1063 (iternextfunc
)dequereviter_next
, /* tp_iternext */
1064 dequeiter_methods
, /* tp_methods */
1068 /* module level code ********************************************************/
1070 PyDoc_STRVAR(module_doc
,
1071 "High performance data structures\n\
1075 initcollections(void)
1079 m
= Py_InitModule3("collections", NULL
, module_doc
);
1083 if (PyType_Ready(&deque_type
) < 0)
1085 Py_INCREF(&deque_type
);
1086 PyModule_AddObject(m
, "deque", (PyObject
*)&deque_type
);
1088 if (PyType_Ready(&dequeiter_type
) < 0)
1091 if (PyType_Ready(&dequereviter_type
) < 0)