1#include "Python.h"
2#include "pycore_long.h" // _PyLong_GetZero()
3#include "structmember.h" // PyMemberDef
4
5#ifdef STDC_HEADERS
6#include <stddef.h>
7#else
8#include <sys/types.h> // size_t
9#endif
10
11/*[clinic input]
12module _collections
13class _tuplegetter "_tuplegetterobject *" "&tuplegetter_type"
14[clinic start generated code]*/
15/*[clinic end generated code: output=da39a3ee5e6b4b0d input=a8ece4ccad7e30ac]*/
16
17static PyTypeObject tuplegetter_type;
18#include "clinic/_collectionsmodule.c.h"
19
20/* collections module implementation of a deque() datatype
21 Written and maintained by Raymond D. Hettinger <[email protected]>
22*/
23
24/* The block length may be set to any number over 1. Larger numbers
25 * reduce the number of calls to the memory allocator, give faster
26 * indexing and rotation, and reduce the link to data overhead ratio.
27 * Making the block length a power of two speeds-up the modulo
28 * and division calculations in deque_item() and deque_ass_item().
29 */
30
31#define BLOCKLEN 64
32#define CENTER ((BLOCKLEN - 1) / 2)
33
34/* Data for deque objects is stored in a doubly-linked list of fixed
35 * length blocks. This assures that appends or pops never move any
36 * other data elements besides the one being appended or popped.
37 *
38 * Another advantage is that it completely avoids use of realloc(),
39 * resulting in more predictable performance.
40 *
41 * Textbook implementations of doubly-linked lists store one datum
42 * per link, but that gives them a 200% memory overhead (a prev and
43 * next link for each datum) and it costs one malloc() call per data
44 * element. By using fixed-length blocks, the link to data ratio is
45 * significantly improved and there are proportionally fewer calls
46 * to malloc() and free(). The data blocks of consecutive pointers
47 * also improve cache locality.
48 *
49 * The list of blocks is never empty, so d.leftblock and d.rightblock
50 * are never equal to NULL. The list is not circular.
51 *
52 * A deque d's first element is at d.leftblock[leftindex]
53 * and its last element is at d.rightblock[rightindex].
54 *
55 * Unlike Python slice indices, these indices are inclusive on both
56 * ends. This makes the algorithms for left and right operations
57 * more symmetrical and it simplifies the design.
58 *
59 * The indices, d.leftindex and d.rightindex are always in the range:
60 * 0 <= index < BLOCKLEN
61 *
62 * And their exact relationship is:
63 * (d.leftindex + d.len - 1) % BLOCKLEN == d.rightindex
64 *
65 * Whenever d.leftblock == d.rightblock, then:
66 * d.leftindex + d.len - 1 == d.rightindex
67 *
68 * However, when d.leftblock != d.rightblock, the d.leftindex and
69 * d.rightindex become indices into distinct blocks and either may
70 * be larger than the other.
71 *
72 * Empty deques have:
73 * d.len == 0
74 * d.leftblock == d.rightblock
75 * d.leftindex == CENTER + 1
76 * d.rightindex == CENTER
77 *
78 * Checking for d.len == 0 is the intended way to see whether d is empty.
79 */
80
81typedef struct BLOCK {
82 struct BLOCK *leftlink;
83 PyObject *data[BLOCKLEN];
84 struct BLOCK *rightlink;
85} block;
86
87typedef struct {
88 PyObject_VAR_HEAD
89 block *leftblock;
90 block *rightblock;
91 Py_ssize_t leftindex; /* 0 <= leftindex < BLOCKLEN */
92 Py_ssize_t rightindex; /* 0 <= rightindex < BLOCKLEN */
93 size_t state; /* incremented whenever the indices move */
94 Py_ssize_t maxlen; /* maxlen is -1 for unbounded deques */
95 PyObject *weakreflist;
96} dequeobject;
97
98static PyTypeObject deque_type;
99
100/* For debug builds, add error checking to track the endpoints
101 * in the chain of links. The goal is to make sure that link
102 * assignments only take place at endpoints so that links already
103 * in use do not get overwritten.
104 *
105 * CHECK_END should happen before each assignment to a block's link field.
106 * MARK_END should happen whenever a link field becomes a new endpoint.
107 * This happens when new blocks are added or whenever an existing
108 * block is freed leaving another existing block as the new endpoint.
109 */
110
111#ifndef NDEBUG
112#define MARK_END(link) link = NULL;
113#define CHECK_END(link) assert(link == NULL);
114#define CHECK_NOT_END(link) assert(link != NULL);
115#else
116#define MARK_END(link)
117#define CHECK_END(link)
118#define CHECK_NOT_END(link)
119#endif
120
121/* A simple freelisting scheme is used to minimize calls to the memory
122 allocator. It accommodates common use cases where new blocks are being
123 added at about the same rate as old blocks are being freed.
124 */
125
126#define MAXFREEBLOCKS 16
127static Py_ssize_t numfreeblocks = 0;
128static block *freeblocks[MAXFREEBLOCKS];
129
130static block *
131newblock(void) {
132 block *b;
133 if (numfreeblocks) {
134 numfreeblocks--;
135 return freeblocks[numfreeblocks];
136 }
137 b = PyMem_Malloc(sizeof(block));
138 if (b != NULL) {
139 return b;
140 }
141 PyErr_NoMemory();
142 return NULL;
143}
144
145static void
146freeblock(block *b)
147{
148 if (numfreeblocks < MAXFREEBLOCKS) {
149 freeblocks[numfreeblocks] = b;
150 numfreeblocks++;
151 } else {
152 PyMem_Free(b);
153 }
154}
155
156static PyObject *
157deque_new(PyTypeObject *type, PyObject *args, PyObject *kwds)
158{
159 dequeobject *deque;
160 block *b;
161
162 /* create dequeobject structure */
163 deque = (dequeobject *)type->tp_alloc(type, 0);
164 if (deque == NULL)
165 return NULL;
166
167 b = newblock();
168 if (b == NULL) {
169 Py_DECREF(deque);
170 return NULL;
171 }
172 MARK_END(b->leftlink);
173 MARK_END(b->rightlink);
174
175 assert(BLOCKLEN >= 2);
176 Py_SET_SIZE(deque, 0);
177 deque->leftblock = b;
178 deque->rightblock = b;
179 deque->leftindex = CENTER + 1;
180 deque->rightindex = CENTER;
181 deque->state = 0;
182 deque->maxlen = -1;
183 deque->weakreflist = NULL;
184
185 return (PyObject *)deque;
186}
187
188static PyObject *
189deque_pop(dequeobject *deque, PyObject *unused)
190{
191 PyObject *item;
192 block *prevblock;
193
194 if (Py_SIZE(deque) == 0) {
195 PyErr_SetString(PyExc_IndexError, "pop from an empty deque");
196 return NULL;
197 }
198 item = deque->rightblock->data[deque->rightindex];
199 deque->rightindex--;
200 Py_SET_SIZE(deque, Py_SIZE(deque) - 1);
201 deque->state++;
202
203 if (deque->rightindex < 0) {
204 if (Py_SIZE(deque)) {
205 prevblock = deque->rightblock->leftlink;
206 assert(deque->leftblock != deque->rightblock);
207 freeblock(deque->rightblock);
208 CHECK_NOT_END(prevblock);
209 MARK_END(prevblock->rightlink);
210 deque->rightblock = prevblock;
211 deque->rightindex = BLOCKLEN - 1;
212 } else {
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;
218 }
219 }
220 return item;
221}
222
223PyDoc_STRVAR(pop_doc, "Remove and return the rightmost element.");
224
225static PyObject *
226deque_popleft(dequeobject *deque, PyObject *unused)
227{
228 PyObject *item;
229 block *prevblock;
230
231 if (Py_SIZE(deque) == 0) {
232 PyErr_SetString(PyExc_IndexError, "pop from an empty deque");
233 return NULL;
234 }
235 assert(deque->leftblock != NULL);
236 item = deque->leftblock->data[deque->leftindex];
237 deque->leftindex++;
238 Py_SET_SIZE(deque, Py_SIZE(deque) - 1);
239 deque->state++;
240
241 if (deque->leftindex == BLOCKLEN) {
242 if (Py_SIZE(deque)) {
243 assert(deque->leftblock != deque->rightblock);
244 prevblock = deque->leftblock->rightlink;
245 freeblock(deque->leftblock);
246 CHECK_NOT_END(prevblock);
247 MARK_END(prevblock->leftlink);
248 deque->leftblock = prevblock;
249 deque->leftindex = 0;
250 } else {
251 assert(deque->leftblock == deque->rightblock);
252 assert(deque->leftindex == deque->rightindex+1);
253 /* re-center instead of freeing a block */
254 deque->leftindex = CENTER + 1;
255 deque->rightindex = CENTER;
256 }
257 }
258 return item;
259}
260
261PyDoc_STRVAR(popleft_doc, "Remove and return the leftmost element.");
262
263/* The deque's size limit is d.maxlen. The limit can be zero or positive.
264 * If there is no limit, then d.maxlen == -1.
265 *
266 * After an item is added to a deque, we check to see if the size has
267 * grown past the limit. If it has, we get the size back down to the limit
268 * by popping an item off of the opposite end. The methods that can
269 * trigger this are append(), appendleft(), extend(), and extendleft().
270 *
271 * The macro to check whether a deque needs to be trimmed uses a single
272 * unsigned test that returns true whenever 0 <= maxlen < Py_SIZE(deque).
273 */
274
275#define NEEDS_TRIM(deque, maxlen) ((size_t)(maxlen) < (size_t)(Py_SIZE(deque)))
276
277static inline int
278deque_append_internal(dequeobject *deque, PyObject *item, Py_ssize_t maxlen)
279{
280 if (deque->rightindex == BLOCKLEN - 1) {
281 block *b = newblock();
282 if (b == NULL)
283 return -1;
284 b->leftlink = deque->rightblock;
285 CHECK_END(deque->rightblock->rightlink);
286 deque->rightblock->rightlink = b;
287 deque->rightblock = b;
288 MARK_END(b->rightlink);
289 deque->rightindex = -1;
290 }
291 Py_SET_SIZE(deque, Py_SIZE(deque) + 1);
292 deque->rightindex++;
293 deque->rightblock->data[deque->rightindex] = item;
294 if (NEEDS_TRIM(deque, maxlen)) {
295 PyObject *olditem = deque_popleft(deque, NULL);
296 Py_DECREF(olditem);
297 } else {
298 deque->state++;
299 }
300 return 0;
301}
302
303static PyObject *
304deque_append(dequeobject *deque, PyObject *item)
305{
306 Py_INCREF(item);
307 if (deque_append_internal(deque, item, deque->maxlen) < 0)
308 return NULL;
309 Py_RETURN_NONE;
310}
311
312PyDoc_STRVAR(append_doc, "Add an element to the right side of the deque.");
313
314static inline int
315deque_appendleft_internal(dequeobject *deque, PyObject *item, Py_ssize_t maxlen)
316{
317 if (deque->leftindex == 0) {
318 block *b = newblock();
319 if (b == NULL)
320 return -1;
321 b->rightlink = deque->leftblock;
322 CHECK_END(deque->leftblock->leftlink);
323 deque->leftblock->leftlink = b;
324 deque->leftblock = b;
325 MARK_END(b->leftlink);
326 deque->leftindex = BLOCKLEN;
327 }
328 Py_SET_SIZE(deque, Py_SIZE(deque) + 1);
329 deque->leftindex--;
330 deque->leftblock->data[deque->leftindex] = item;
331 if (NEEDS_TRIM(deque, deque->maxlen)) {
332 PyObject *olditem = deque_pop(deque, NULL);
333 Py_DECREF(olditem);
334 } else {
335 deque->state++;
336 }
337 return 0;
338}
339
340static PyObject *
341deque_appendleft(dequeobject *deque, PyObject *item)
342{
343 Py_INCREF(item);
344 if (deque_appendleft_internal(deque, item, deque->maxlen) < 0)
345 return NULL;
346 Py_RETURN_NONE;
347}
348
349PyDoc_STRVAR(appendleft_doc, "Add an element to the left side of the deque.");
350
351static PyObject*
352finalize_iterator(PyObject *it)
353{
354 if (PyErr_Occurred()) {
355 if (PyErr_ExceptionMatches(PyExc_StopIteration))
356 PyErr_Clear();
357 else {
358 Py_DECREF(it);
359 return NULL;
360 }
361 }
362 Py_DECREF(it);
363 Py_RETURN_NONE;
364}
365
366/* Run an iterator to exhaustion. Shortcut for
367 the extend/extendleft methods when maxlen == 0. */
368static PyObject*
369consume_iterator(PyObject *it)
370{
371 PyObject *(*iternext)(PyObject *);
372 PyObject *item;
373
374 iternext = *Py_TYPE(it)->tp_iternext;
375 while ((item = iternext(it)) != NULL) {
376 Py_DECREF(item);
377 }
378 return finalize_iterator(it);
379}
380
381static PyObject *
382deque_extend(dequeobject *deque, PyObject *iterable)
383{
384 PyObject *it, *item;
385 PyObject *(*iternext)(PyObject *);
386 Py_ssize_t maxlen = deque->maxlen;
387
388 /* Handle case where id(deque) == id(iterable) */
389 if ((PyObject *)deque == iterable) {
390 PyObject *result;
391 PyObject *s = PySequence_List(iterable);
392 if (s == NULL)
393 return NULL;
394 result = deque_extend(deque, s);
395 Py_DECREF(s);
396 return result;
397 }
398
399 it = PyObject_GetIter(iterable);
400 if (it == NULL)
401 return NULL;
402
403 if (maxlen == 0)
404 return consume_iterator(it);
405
406 /* Space saving heuristic. Start filling from the left */
407 if (Py_SIZE(deque) == 0) {
408 assert(deque->leftblock == deque->rightblock);
409 assert(deque->leftindex == deque->rightindex+1);
410 deque->leftindex = 1;
411 deque->rightindex = 0;
412 }
413
414 iternext = *Py_TYPE(it)->tp_iternext;
415 while ((item = iternext(it)) != NULL) {
416 if (deque_append_internal(deque, item, maxlen) == -1) {
417 Py_DECREF(item);
418 Py_DECREF(it);
419 return NULL;
420 }
421 }
422 return finalize_iterator(it);
423}
424
425PyDoc_STRVAR(extend_doc,
426"Extend the right side of the deque with elements from the iterable");
427
428static PyObject *
429deque_extendleft(dequeobject *deque, PyObject *iterable)
430{
431 PyObject *it, *item;
432 PyObject *(*iternext)(PyObject *);
433 Py_ssize_t maxlen = deque->maxlen;
434
435 /* Handle case where id(deque) == id(iterable) */
436 if ((PyObject *)deque == iterable) {
437 PyObject *result;
438 PyObject *s = PySequence_List(iterable);
439 if (s == NULL)
440 return NULL;
441 result = deque_extendleft(deque, s);
442 Py_DECREF(s);
443 return result;
444 }
445
446 it = PyObject_GetIter(iterable);
447 if (it == NULL)
448 return NULL;
449
450 if (maxlen == 0)
451 return consume_iterator(it);
452
453 /* Space saving heuristic. Start filling from the right */
454 if (Py_SIZE(deque) == 0) {
455 assert(deque->leftblock == deque->rightblock);
456 assert(deque->leftindex == deque->rightindex+1);
457 deque->leftindex = BLOCKLEN - 1;
458 deque->rightindex = BLOCKLEN - 2;
459 }
460
461 iternext = *Py_TYPE(it)->tp_iternext;
462 while ((item = iternext(it)) != NULL) {
463 if (deque_appendleft_internal(deque, item, maxlen) == -1) {
464 Py_DECREF(item);
465 Py_DECREF(it);
466 return NULL;
467 }
468 }
469 return finalize_iterator(it);
470}
471
472PyDoc_STRVAR(extendleft_doc,
473"Extend the left side of the deque with elements from the iterable");
474
475static PyObject *
476deque_inplace_concat(dequeobject *deque, PyObject *other)
477{
478 PyObject *result;
479
480 result = deque_extend(deque, other);
481 if (result == NULL)
482 return result;
483 Py_INCREF(deque);
484 Py_DECREF(result);
485 return (PyObject *)deque;
486}
487
488static PyObject *
489deque_copy(PyObject *deque, PyObject *Py_UNUSED(ignored))
490{
491 PyObject *result;
492 dequeobject *old_deque = (dequeobject *)deque;
493 if (Py_IS_TYPE(deque, &deque_type)) {
494 dequeobject *new_deque;
495 PyObject *rv;
496
497 new_deque = (dequeobject *)deque_new(&deque_type, (PyObject *)NULL, (PyObject *)NULL);
498 if (new_deque == NULL)
499 return NULL;
500 new_deque->maxlen = old_deque->maxlen;
501 /* Fast path for the deque_repeat() common case where len(deque) == 1 */
502 if (Py_SIZE(deque) == 1) {
503 PyObject *item = old_deque->leftblock->data[old_deque->leftindex];
504 rv = deque_append(new_deque, item);
505 } else {
506 rv = deque_extend(new_deque, deque);
507 }
508 if (rv != NULL) {
509 Py_DECREF(rv);
510 return (PyObject *)new_deque;
511 }
512 Py_DECREF(new_deque);
513 return NULL;
514 }
515 if (old_deque->maxlen < 0)
516 result = PyObject_CallOneArg((PyObject *)(Py_TYPE(deque)), deque);
517 else
518 result = PyObject_CallFunction((PyObject *)(Py_TYPE(deque)), "Oi",
519 deque, old_deque->maxlen, NULL);
520 if (result != NULL && !PyObject_TypeCheck(result, &deque_type)) {
521 PyErr_Format(PyExc_TypeError,
522 "%.200s() must return a deque, not %.200s",
523 Py_TYPE(deque)->tp_name, Py_TYPE(result)->tp_name);
524 Py_DECREF(result);
525 return NULL;
526 }
527 return result;
528}
529
530PyDoc_STRVAR(copy_doc, "Return a shallow copy of a deque.");
531
532static PyObject *
533deque_concat(dequeobject *deque, PyObject *other)
534{
535 PyObject *new_deque, *result;
536 int rv;
537
538 rv = PyObject_IsInstance(other, (PyObject *)&deque_type);
539 if (rv <= 0) {
540 if (rv == 0) {
541 PyErr_Format(PyExc_TypeError,
542 "can only concatenate deque (not \"%.200s\") to deque",
543 Py_TYPE(other)->tp_name);
544 }
545 return NULL;
546 }
547
548 new_deque = deque_copy((PyObject *)deque, NULL);
549 if (new_deque == NULL)
550 return NULL;
551 result = deque_extend((dequeobject *)new_deque, other);
552 if (result == NULL) {
553 Py_DECREF(new_deque);
554 return NULL;
555 }
556 Py_DECREF(result);
557 return new_deque;
558}
559
560static int
561deque_clear(dequeobject *deque)
562{
563 block *b;
564 block *prevblock;
565 block *leftblock;
566 Py_ssize_t leftindex;
567 Py_ssize_t n, m;
568 PyObject *item;
569 PyObject **itemptr, **limit;
570
571 if (Py_SIZE(deque) == 0)
572 return 0;
573
574 /* During the process of clearing a deque, decrefs can cause the
575 deque to mutate. To avoid fatal confusion, we have to make the
576 deque empty before clearing the blocks and never refer to
577 anything via deque->ref while clearing. (This is the same
578 technique used for clearing lists, sets, and dicts.)
579
580 Making the deque empty requires allocating a new empty block. In
581 the unlikely event that memory is full, we fall back to an
582 alternate method that doesn't require a new block. Repeating
583 pops in a while-loop is slower, possibly re-entrant (and a clever
584 adversary could cause it to never terminate).
585 */
586
587 b = newblock();
588 if (b == NULL) {
589 PyErr_Clear();
590 goto alternate_method;
591 }
592
593 /* Remember the old size, leftblock, and leftindex */
594 n = Py_SIZE(deque);
595 leftblock = deque->leftblock;
596 leftindex = deque->leftindex;
597
598 /* Set the deque to be empty using the newly allocated block */
599 MARK_END(b->leftlink);
600 MARK_END(b->rightlink);
601 Py_SET_SIZE(deque, 0);
602 deque->leftblock = b;
603 deque->rightblock = b;
604 deque->leftindex = CENTER + 1;
605 deque->rightindex = CENTER;
606 deque->state++;
607
608 /* Now the old size, leftblock, and leftindex are disconnected from
609 the empty deque and we can use them to decref the pointers.
610 */
611 m = (BLOCKLEN - leftindex > n) ? n : BLOCKLEN - leftindex;
612 itemptr = &leftblock->data[leftindex];
613 limit = itemptr + m;
614 n -= m;
615 while (1) {
616 if (itemptr == limit) {
617 if (n == 0)
618 break;
619 CHECK_NOT_END(leftblock->rightlink);
620 prevblock = leftblock;
621 leftblock = leftblock->rightlink;
622 m = (n > BLOCKLEN) ? BLOCKLEN : n;
623 itemptr = leftblock->data;
624 limit = itemptr + m;
625 n -= m;
626 freeblock(prevblock);
627 }
628 item = *(itemptr++);
629 Py_DECREF(item);
630 }
631 CHECK_END(leftblock->rightlink);
632 freeblock(leftblock);
633 return 0;
634
635 alternate_method:
636 while (Py_SIZE(deque)) {
637 item = deque_pop(deque, NULL);
638 assert (item != NULL);
639 Py_DECREF(item);
640 }
641 return 0;
642}
643
644static PyObject *
645deque_clearmethod(dequeobject *deque, PyObject *Py_UNUSED(ignored))
646{
647 deque_clear(deque);
648 Py_RETURN_NONE;
649}
650
651PyDoc_STRVAR(clear_doc, "Remove all elements from the deque.");
652
653static PyObject *
654deque_inplace_repeat(dequeobject *deque, Py_ssize_t n)
655{
656 Py_ssize_t i, m, size;
657 PyObject *seq;
658 PyObject *rv;
659
660 size = Py_SIZE(deque);
661 if (size == 0 || n == 1) {
662 Py_INCREF(deque);
663 return (PyObject *)deque;
664 }
665
666 if (n <= 0) {
667 deque_clear(deque);
668 Py_INCREF(deque);
669 return (PyObject *)deque;
670 }
671
672 if (size == 1) {
673 /* common case, repeating a single element */
674 PyObject *item = deque->leftblock->data[deque->leftindex];
675
676 if (deque->maxlen >= 0 && n > deque->maxlen)
677 n = deque->maxlen;
678
679 deque->state++;
680 for (i = 0 ; i < n-1 ; ) {
681 if (deque->rightindex == BLOCKLEN - 1) {
682 block *b = newblock();
683 if (b == NULL) {
684 Py_SET_SIZE(deque, Py_SIZE(deque) + i);
685 return NULL;
686 }
687 b->leftlink = deque->rightblock;
688 CHECK_END(deque->rightblock->rightlink);
689 deque->rightblock->rightlink = b;
690 deque->rightblock = b;
691 MARK_END(b->rightlink);
692 deque->rightindex = -1;
693 }
694 m = n - 1 - i;
695 if (m > BLOCKLEN - 1 - deque->rightindex)
696 m = BLOCKLEN - 1 - deque->rightindex;
697 i += m;
698 while (m--) {
699 deque->rightindex++;
700 Py_INCREF(item);
701 deque->rightblock->data[deque->rightindex] = item;
702 }
703 }
704 Py_SET_SIZE(deque, Py_SIZE(deque) + i);
705 Py_INCREF(deque);
706 return (PyObject *)deque;
707 }
708
709 if ((size_t)size > PY_SSIZE_T_MAX / (size_t)n) {
710 return PyErr_NoMemory();
711 }
712
713 seq = PySequence_List((PyObject *)deque);
714 if (seq == NULL)
715 return seq;
716
717 /* Reduce the number of repetitions when maxlen would be exceeded */
718 if (deque->maxlen >= 0 && n * size > deque->maxlen)
719 n = (deque->maxlen + size - 1) / size;
720
721 for (i = 0 ; i < n-1 ; i++) {
722 rv = deque_extend(deque, seq);
723 if (rv == NULL) {
724 Py_DECREF(seq);
725 return NULL;
726 }
727 Py_DECREF(rv);
728 }
729 Py_INCREF(deque);
730 Py_DECREF(seq);
731 return (PyObject *)deque;
732}
733
734static PyObject *
735deque_repeat(dequeobject *deque, Py_ssize_t n)
736{
737 dequeobject *new_deque;
738 PyObject *rv;
739
740 new_deque = (dequeobject *)deque_copy((PyObject *) deque, NULL);
741 if (new_deque == NULL)
742 return NULL;
743 rv = deque_inplace_repeat(new_deque, n);
744 Py_DECREF(new_deque);
745 return rv;
746}
747
748/* The rotate() method is part of the public API and is used internally
749as a primitive for other methods.
750
751Rotation by 1 or -1 is a common case, so any optimizations for high
752volume rotations should take care not to penalize the common case.
753
754Conceptually, a rotate by one is equivalent to a pop on one side and an
755append on the other. However, a pop/append pair is unnecessarily slow
756because it requires an incref/decref pair for an object located randomly
757in memory. It is better to just move the object pointer from one block
758to the next without changing the reference count.
759
760When moving batches of pointers, it is tempting to use memcpy() but that
761proved to be slower than a simple loop for a variety of reasons.
762Memcpy() cannot know in advance that we're copying pointers instead of
763bytes, that the source and destination are pointer aligned and
764non-overlapping, that moving just one pointer is a common case, that we
765never need to move more than BLOCKLEN pointers, and that at least one
766pointer is always moved.
767
768For high volume rotations, newblock() and freeblock() are never called
769more than once. Previously emptied blocks are immediately reused as a
770destination block. If a block is left-over at the end, it is freed.
771*/
772
773static int
774_deque_rotate(dequeobject *deque, Py_ssize_t n)
775{
776 block *b = NULL;
777 block *leftblock = deque->leftblock;
778 block *rightblock = deque->rightblock;
779 Py_ssize_t leftindex = deque->leftindex;
780 Py_ssize_t rightindex = deque->rightindex;
781 Py_ssize_t len=Py_SIZE(deque), halflen=len>>1;
782 int rv = -1;
783
784 if (len <= 1)
785 return 0;
786 if (n > halflen || n < -halflen) {
787 n %= len;
788 if (n > halflen)
789 n -= len;
790 else if (n < -halflen)
791 n += len;
792 }
793 assert(len > 1);
794 assert(-halflen <= n && n <= halflen);
795
796 deque->state++;
797 while (n > 0) {
798 if (leftindex == 0) {
799 if (b == NULL) {
800 b = newblock();
801 if (b == NULL)
802 goto done;
803 }
804 b->rightlink = leftblock;
805 CHECK_END(leftblock->leftlink);
806 leftblock->leftlink = b;
807 leftblock = b;
808 MARK_END(b->leftlink);
809 leftindex = BLOCKLEN;
810 b = NULL;
811 }
812 assert(leftindex > 0);
813 {
814 PyObject **src, **dest;
815 Py_ssize_t m = n;
816
817 if (m > rightindex + 1)
818 m = rightindex + 1;
819 if (m > leftindex)
820 m = leftindex;
821 assert (m > 0 && m <= len);
822 rightindex -= m;
823 leftindex -= m;
824 src = &rightblock->data[rightindex + 1];
825 dest = &leftblock->data[leftindex];
826 n -= m;
827 do {
828 *(dest++) = *(src++);
829 } while (--m);
830 }
831 if (rightindex < 0) {
832 assert(leftblock != rightblock);
833 assert(b == NULL);
834 b = rightblock;
835 CHECK_NOT_END(rightblock->leftlink);
836 rightblock = rightblock->leftlink;
837 MARK_END(rightblock->rightlink);
838 rightindex = BLOCKLEN - 1;
839 }
840 }
841 while (n < 0) {
842 if (rightindex == BLOCKLEN - 1) {
843 if (b == NULL) {
844 b = newblock();
845 if (b == NULL)
846 goto done;
847 }
848 b->leftlink = rightblock;
849 CHECK_END(rightblock->rightlink);
850 rightblock->rightlink = b;
851 rightblock = b;
852 MARK_END(b->rightlink);
853 rightindex = -1;
854 b = NULL;
855 }
856 assert (rightindex < BLOCKLEN - 1);
857 {
858 PyObject **src, **dest;
859 Py_ssize_t m = -n;
860
861 if (m > BLOCKLEN - leftindex)
862 m = BLOCKLEN - leftindex;
863 if (m > BLOCKLEN - 1 - rightindex)
864 m = BLOCKLEN - 1 - rightindex;
865 assert (m > 0 && m <= len);
866 src = &leftblock->data[leftindex];
867 dest = &rightblock->data[rightindex + 1];
868 leftindex += m;
869 rightindex += m;
870 n += m;
871 do {
872 *(dest++) = *(src++);
873 } while (--m);
874 }
875 if (leftindex == BLOCKLEN) {
876 assert(leftblock != rightblock);
877 assert(b == NULL);
878 b = leftblock;
879 CHECK_NOT_END(leftblock->rightlink);
880 leftblock = leftblock->rightlink;
881 MARK_END(leftblock->leftlink);
882 leftindex = 0;
883 }
884 }
885 rv = 0;
886done:
887 if (b != NULL)
888 freeblock(b);
889 deque->leftblock = leftblock;
890 deque->rightblock = rightblock;
891 deque->leftindex = leftindex;
892 deque->rightindex = rightindex;
893
894 return rv;
895}
896
897static PyObject *
898deque_rotate(dequeobject *deque, PyObject *const *args, Py_ssize_t nargs)
899{
900 Py_ssize_t n=1;
901
902 if (!_PyArg_CheckPositional("deque.rotate", nargs, 0, 1)) {
903 return NULL;
904 }
905 if (nargs) {
906 PyObject *index = _PyNumber_Index(args[0]);
907 if (index == NULL) {
908 return NULL;
909 }
910 n = PyLong_AsSsize_t(index);
911 Py_DECREF(index);
912 if (n == -1 && PyErr_Occurred()) {
913 return NULL;
914 }
915 }
916
917 if (!_deque_rotate(deque, n))
918 Py_RETURN_NONE;
919 return NULL;
920}
921
922PyDoc_STRVAR(rotate_doc,
923"Rotate the deque n steps to the right (default n=1). If n is negative, rotates left.");
924
925static PyObject *
926deque_reverse(dequeobject *deque, PyObject *unused)
927{
928 block *leftblock = deque->leftblock;
929 block *rightblock = deque->rightblock;
930 Py_ssize_t leftindex = deque->leftindex;
931 Py_ssize_t rightindex = deque->rightindex;
932 Py_ssize_t n = Py_SIZE(deque) >> 1;
933 PyObject *tmp;
934
935 while (--n >= 0) {
936 /* Validate that pointers haven't met in the middle */
937 assert(leftblock != rightblock || leftindex < rightindex);
938 CHECK_NOT_END(leftblock);
939 CHECK_NOT_END(rightblock);
940
941 /* Swap */
942 tmp = leftblock->data[leftindex];
943 leftblock->data[leftindex] = rightblock->data[rightindex];
944 rightblock->data[rightindex] = tmp;
945
946 /* Advance left block/index pair */
947 leftindex++;
948 if (leftindex == BLOCKLEN) {
949 leftblock = leftblock->rightlink;
950 leftindex = 0;
951 }
952
953 /* Step backwards with the right block/index pair */
954 rightindex--;
955 if (rightindex < 0) {
956 rightblock = rightblock->leftlink;
957 rightindex = BLOCKLEN - 1;
958 }
959 }
960 Py_RETURN_NONE;
961}
962
963PyDoc_STRVAR(reverse_doc,
964"D.reverse() -- reverse *IN PLACE*");
965
966static PyObject *
967deque_count(dequeobject *deque, PyObject *v)
968{
969 block *b = deque->leftblock;
970 Py_ssize_t index = deque->leftindex;
971 Py_ssize_t n = Py_SIZE(deque);
972 Py_ssize_t count = 0;
973 size_t start_state = deque->state;
974 PyObject *item;
975 int cmp;
976
977 while (--n >= 0) {
978 CHECK_NOT_END(b);
979 item = b->data[index];
980 Py_INCREF(item);
981 cmp = PyObject_RichCompareBool(item, v, Py_EQ);
982 Py_DECREF(item);
983 if (cmp < 0)
984 return NULL;
985 count += cmp;
986
987 if (start_state != deque->state) {
988 PyErr_SetString(PyExc_RuntimeError,
989 "deque mutated during iteration");
990 return NULL;
991 }
992
993 /* Advance left block/index pair */
994 index++;
995 if (index == BLOCKLEN) {
996 b = b->rightlink;
997 index = 0;
998 }
999 }
1000 return PyLong_FromSsize_t(count);
1001}
1002
1003PyDoc_STRVAR(count_doc,
1004"D.count(value) -> integer -- return number of occurrences of value");
1005
1006static int
1007deque_contains(dequeobject *deque, PyObject *v)
1008{
1009 block *b = deque->leftblock;
1010 Py_ssize_t index = deque->leftindex;
1011 Py_ssize_t n = Py_SIZE(deque);
1012 size_t start_state = deque->state;
1013 PyObject *item;
1014 int cmp;
1015
1016 while (--n >= 0) {
1017 CHECK_NOT_END(b);
1018 item = b->data[index];
1019 Py_INCREF(item);
1020 cmp = PyObject_RichCompareBool(item, v, Py_EQ);
1021 Py_DECREF(item);
1022 if (cmp) {
1023 return cmp;
1024 }
1025 if (start_state != deque->state) {
1026 PyErr_SetString(PyExc_RuntimeError,
1027 "deque mutated during iteration");
1028 return -1;
1029 }
1030 index++;
1031 if (index == BLOCKLEN) {
1032 b = b->rightlink;
1033 index = 0;
1034 }
1035 }
1036 return 0;
1037}
1038
1039static Py_ssize_t
1040deque_len(dequeobject *deque)
1041{
1042 return Py_SIZE(deque);
1043}
1044
1045static PyObject *
1046deque_index(dequeobject *deque, PyObject *const *args, Py_ssize_t nargs)
1047{
1048 Py_ssize_t i, n, start=0, stop=Py_SIZE(deque);
1049 PyObject *v, *item;
1050 block *b = deque->leftblock;
1051 Py_ssize_t index = deque->leftindex;
1052 size_t start_state = deque->state;
1053 int cmp;
1054
1055 if (!_PyArg_ParseStack(args, nargs, "O|O&O&:index", &v,
1056 _PyEval_SliceIndexNotNone, &start,
1057 _PyEval_SliceIndexNotNone, &stop)) {
1058 return NULL;
1059 }
1060
1061 if (start < 0) {
1062 start += Py_SIZE(deque);
1063 if (start < 0)
1064 start = 0;
1065 }
1066 if (stop < 0) {
1067 stop += Py_SIZE(deque);
1068 if (stop < 0)
1069 stop = 0;
1070 }
1071 if (stop > Py_SIZE(deque))
1072 stop = Py_SIZE(deque);
1073 if (start > stop)
1074 start = stop;
1075 assert(0 <= start && start <= stop && stop <= Py_SIZE(deque));
1076
1077 for (i=0 ; i < start - BLOCKLEN ; i += BLOCKLEN) {
1078 b = b->rightlink;
1079 }
1080 for ( ; i < start ; i++) {
1081 index++;
1082 if (index == BLOCKLEN) {
1083 b = b->rightlink;
1084 index = 0;
1085 }
1086 }
1087
1088 n = stop - i;
1089 while (--n >= 0) {
1090 CHECK_NOT_END(b);
1091 item = b->data[index];
1092 cmp = PyObject_RichCompareBool(item, v, Py_EQ);
1093 if (cmp > 0)
1094 return PyLong_FromSsize_t(stop - n - 1);
1095 if (cmp < 0)
1096 return NULL;
1097 if (start_state != deque->state) {
1098 PyErr_SetString(PyExc_RuntimeError,
1099 "deque mutated during iteration");
1100 return NULL;
1101 }
1102 index++;
1103 if (index == BLOCKLEN) {
1104 b = b->rightlink;
1105 index = 0;
1106 }
1107 }
1108 PyErr_Format(PyExc_ValueError, "%R is not in deque", v);
1109 return NULL;
1110}
1111
1112PyDoc_STRVAR(index_doc,
1113"D.index(value, [start, [stop]]) -> integer -- return first index of value.\n"
1114"Raises ValueError if the value is not present.");
1115
1116/* insert(), remove(), and delitem() are implemented in terms of
1117 rotate() for simplicity and reasonable performance near the end
1118 points. If for some reason these methods become popular, it is not
1119 hard to re-implement this using direct data movement (similar to
1120 the code used in list slice assignments) and achieve a performance
1121 boost (by moving each pointer only once instead of twice).
1122*/
1123
1124static PyObject *
1125deque_insert(dequeobject *deque, PyObject *const *args, Py_ssize_t nargs)
1126{
1127 Py_ssize_t index;
1128 Py_ssize_t n = Py_SIZE(deque);
1129 PyObject *value;
1130 PyObject *rv;
1131
1132 if (!_PyArg_ParseStack(args, nargs, "nO:insert", &index, &value)) {
1133 return NULL;
1134 }
1135
1136 if (deque->maxlen == Py_SIZE(deque)) {
1137 PyErr_SetString(PyExc_IndexError, "deque already at its maximum size");
1138 return NULL;
1139 }
1140 if (index >= n)
1141 return deque_append(deque, value);
1142 if (index <= -n || index == 0)
1143 return deque_appendleft(deque, value);
1144 if (_deque_rotate(deque, -index))
1145 return NULL;
1146 if (index < 0)
1147 rv = deque_append(deque, value);
1148 else
1149 rv = deque_appendleft(deque, value);
1150 if (rv == NULL)
1151 return NULL;
1152 Py_DECREF(rv);
1153 if (_deque_rotate(deque, index))
1154 return NULL;
1155 Py_RETURN_NONE;
1156}
1157
1158PyDoc_STRVAR(insert_doc,
1159"D.insert(index, object) -- insert object before index");
1160
1161PyDoc_STRVAR(remove_doc,
1162"D.remove(value) -- remove first occurrence of value.");
1163
1164static int
1165valid_index(Py_ssize_t i, Py_ssize_t limit)
1166{
1167 /* The cast to size_t lets us use just a single comparison
1168 to check whether i is in the range: 0 <= i < limit */
1169 return (size_t) i < (size_t) limit;
1170}
1171
1172static PyObject *
1173deque_item(dequeobject *deque, Py_ssize_t i)
1174{
1175 block *b;
1176 PyObject *item;
1177 Py_ssize_t n, index=i;
1178
1179 if (!valid_index(i, Py_SIZE(deque))) {
1180 PyErr_SetString(PyExc_IndexError, "deque index out of range");
1181 return NULL;
1182 }
1183
1184 if (i == 0) {
1185 i = deque->leftindex;
1186 b = deque->leftblock;
1187 } else if (i == Py_SIZE(deque) - 1) {
1188 i = deque->rightindex;
1189 b = deque->rightblock;
1190 } else {
1191 i += deque->leftindex;
1192 n = (Py_ssize_t)((size_t) i / BLOCKLEN);
1193 i = (Py_ssize_t)((size_t) i % BLOCKLEN);
1194 if (index < (Py_SIZE(deque) >> 1)) {
1195 b = deque->leftblock;
1196 while (--n >= 0)
1197 b = b->rightlink;
1198 } else {
1199 n = (Py_ssize_t)(
1200 ((size_t)(deque->leftindex + Py_SIZE(deque) - 1))
1201 / BLOCKLEN - n);
1202 b = deque->rightblock;
1203 while (--n >= 0)
1204 b = b->leftlink;
1205 }
1206 }
1207 item = b->data[i];
1208 Py_INCREF(item);
1209 return item;
1210}
1211
1212static int
1213deque_del_item(dequeobject *deque, Py_ssize_t i)
1214{
1215 PyObject *item;
1216 int rv;
1217
1218 assert (i >= 0 && i < Py_SIZE(deque));
1219 if (_deque_rotate(deque, -i))
1220 return -1;
1221 item = deque_popleft(deque, NULL);
1222 rv = _deque_rotate(deque, i);
1223 assert (item != NULL);
1224 Py_DECREF(item);
1225 return rv;
1226}
1227
1228static PyObject *
1229deque_remove(dequeobject *deque, PyObject *value)
1230{
1231 PyObject *item;
1232 block *b = deque->leftblock;
1233 Py_ssize_t i, n = Py_SIZE(deque), index = deque->leftindex;
1234 size_t start_state = deque->state;
1235 int cmp, rv;
1236
1237 for (i = 0 ; i < n; i++) {
1238 item = b->data[index];
1239 Py_INCREF(item);
1240 cmp = PyObject_RichCompareBool(item, value, Py_EQ);
1241 Py_DECREF(item);
1242 if (cmp < 0) {
1243 return NULL;
1244 }
1245 if (start_state != deque->state) {
1246 PyErr_SetString(PyExc_IndexError,
1247 "deque mutated during iteration");
1248 return NULL;
1249 }
1250 if (cmp > 0) {
1251 break;
1252 }
1253 index++;
1254 if (index == BLOCKLEN) {
1255 b = b->rightlink;
1256 index = 0;
1257 }
1258 }
1259 if (i == n) {
1260 PyErr_Format(PyExc_ValueError, "%R is not in deque", value);
1261 return NULL;
1262 }
1263 rv = deque_del_item(deque, i);
1264 if (rv == -1) {
1265 return NULL;
1266 }
1267 Py_RETURN_NONE;
1268}
1269
1270static int
1271deque_ass_item(dequeobject *deque, Py_ssize_t i, PyObject *v)
1272{
1273 PyObject *old_value;
1274 block *b;
1275 Py_ssize_t n, len=Py_SIZE(deque), halflen=(len+1)>>1, index=i;
1276
1277 if (!valid_index(i, len)) {
1278 PyErr_SetString(PyExc_IndexError, "deque index out of range");
1279 return -1;
1280 }
1281 if (v == NULL)
1282 return deque_del_item(deque, i);
1283
1284 i += deque->leftindex;
1285 n = (Py_ssize_t)((size_t) i / BLOCKLEN);
1286 i = (Py_ssize_t)((size_t) i % BLOCKLEN);
1287 if (index <= halflen) {
1288 b = deque->leftblock;
1289 while (--n >= 0)
1290 b = b->rightlink;
1291 } else {
1292 n = (Py_ssize_t)(
1293 ((size_t)(deque->leftindex + Py_SIZE(deque) - 1))
1294 / BLOCKLEN - n);
1295 b = deque->rightblock;
1296 while (--n >= 0)
1297 b = b->leftlink;
1298 }
1299 Py_INCREF(v);
1300 old_value = b->data[i];
1301 b->data[i] = v;
1302 Py_DECREF(old_value);
1303 return 0;
1304}
1305
1306static void
1307deque_dealloc(dequeobject *deque)
1308{
1309 PyObject_GC_UnTrack(deque);
1310 if (deque->weakreflist != NULL)
1311 PyObject_ClearWeakRefs((PyObject *) deque);
1312 if (deque->leftblock != NULL) {
1313 deque_clear(deque);
1314 assert(deque->leftblock != NULL);
1315 freeblock(deque->leftblock);
1316 }
1317 deque->leftblock = NULL;
1318 deque->rightblock = NULL;
1319 Py_TYPE(deque)->tp_free(deque);
1320}
1321
1322static int
1323deque_traverse(dequeobject *deque, visitproc visit, void *arg)
1324{
1325 block *b;
1326 PyObject *item;
1327 Py_ssize_t index;
1328 Py_ssize_t indexlo = deque->leftindex;
1329 Py_ssize_t indexhigh;
1330
1331 for (b = deque->leftblock; b != deque->rightblock; b = b->rightlink) {
1332 for (index = indexlo; index < BLOCKLEN ; index++) {
1333 item = b->data[index];
1334 Py_VISIT(item);
1335 }
1336 indexlo = 0;
1337 }
1338 indexhigh = deque->rightindex;
1339 for (index = indexlo; index <= indexhigh; index++) {
1340 item = b->data[index];
1341 Py_VISIT(item);
1342 }
1343 return 0;
1344}
1345
1346static PyObject *
1347deque_reduce(dequeobject *deque, PyObject *Py_UNUSED(ignored))
1348{
1349 PyObject *dict, *it;
1350 _Py_IDENTIFIER(__dict__);
1351
1352 if (_PyObject_LookupAttrId((PyObject *)deque, &PyId___dict__, &dict) < 0) {
1353 return NULL;
1354 }
1355 if (dict == NULL) {
1356 dict = Py_None;
1357 Py_INCREF(dict);
1358 }
1359
1360 it = PyObject_GetIter((PyObject *)deque);
1361 if (it == NULL) {
1362 Py_DECREF(dict);
1363 return NULL;
1364 }
1365
1366 if (deque->maxlen < 0) {
1367 return Py_BuildValue("O()NN", Py_TYPE(deque), dict, it);
1368 }
1369 else {
1370 return Py_BuildValue("O(()n)NN", Py_TYPE(deque), deque->maxlen, dict, it);
1371 }
1372}
1373
1374PyDoc_STRVAR(reduce_doc, "Return state information for pickling.");
1375
1376static PyObject *
1377deque_repr(PyObject *deque)
1378{
1379 PyObject *aslist, *result;
1380 int i;
1381
1382 i = Py_ReprEnter(deque);
1383 if (i != 0) {
1384 if (i < 0)
1385 return NULL;
1386 return PyUnicode_FromString("[...]");
1387 }
1388
1389 aslist = PySequence_List(deque);
1390 if (aslist == NULL) {
1391 Py_ReprLeave(deque);
1392 return NULL;
1393 }
1394 if (((dequeobject *)deque)->maxlen >= 0)
1395 result = PyUnicode_FromFormat("%s(%R, maxlen=%zd)",
1396 _PyType_Name(Py_TYPE(deque)), aslist,
1397 ((dequeobject *)deque)->maxlen);
1398 else
1399 result = PyUnicode_FromFormat("%s(%R)",
1400 _PyType_Name(Py_TYPE(deque)), aslist);
1401 Py_ReprLeave(deque);
1402 Py_DECREF(aslist);
1403 return result;
1404}
1405
1406static PyObject *
1407deque_richcompare(PyObject *v, PyObject *w, int op)
1408{
1409 PyObject *it1=NULL, *it2=NULL, *x, *y;
1410 Py_ssize_t vs, ws;
1411 int b, cmp=-1;
1412
1413 if (!PyObject_TypeCheck(v, &deque_type) ||
1414 !PyObject_TypeCheck(w, &deque_type)) {
1415 Py_RETURN_NOTIMPLEMENTED;
1416 }
1417
1418 /* Shortcuts */
1419 vs = Py_SIZE((dequeobject *)v);
1420 ws = Py_SIZE((dequeobject *)w);
1421 if (op == Py_EQ) {
1422 if (v == w)
1423 Py_RETURN_TRUE;
1424 if (vs != ws)
1425 Py_RETURN_FALSE;
1426 }
1427 if (op == Py_NE) {
1428 if (v == w)
1429 Py_RETURN_FALSE;
1430 if (vs != ws)
1431 Py_RETURN_TRUE;
1432 }
1433
1434 /* Search for the first index where items are different */
1435 it1 = PyObject_GetIter(v);
1436 if (it1 == NULL)
1437 goto done;
1438 it2 = PyObject_GetIter(w);
1439 if (it2 == NULL)
1440 goto done;
1441 for (;;) {
1442 x = PyIter_Next(it1);
1443 if (x == NULL && PyErr_Occurred())
1444 goto done;
1445 y = PyIter_Next(it2);
1446 if (x == NULL || y == NULL)
1447 break;
1448 b = PyObject_RichCompareBool(x, y, Py_EQ);
1449 if (b == 0) {
1450 cmp = PyObject_RichCompareBool(x, y, op);
1451 Py_DECREF(x);
1452 Py_DECREF(y);
1453 goto done;
1454 }
1455 Py_DECREF(x);
1456 Py_DECREF(y);
1457 if (b < 0)
1458 goto done;
1459 }
1460 /* We reached the end of one deque or both */
1461 Py_XDECREF(x);
1462 Py_XDECREF(y);
1463 if (PyErr_Occurred())
1464 goto done;
1465 switch (op) {
1466 case Py_LT: cmp = y != NULL; break; /* if w was longer */
1467 case Py_LE: cmp = x == NULL; break; /* if v was not longer */
1468 case Py_EQ: cmp = x == y; break; /* if we reached the end of both */
1469 case Py_NE: cmp = x != y; break; /* if one deque continues */
1470 case Py_GT: cmp = x != NULL; break; /* if v was longer */
1471 case Py_GE: cmp = y == NULL; break; /* if w was not longer */
1472 }
1473
1474done:
1475 Py_XDECREF(it1);
1476 Py_XDECREF(it2);
1477 if (cmp == 1)
1478 Py_RETURN_TRUE;
1479 if (cmp == 0)
1480 Py_RETURN_FALSE;
1481 return NULL;
1482}
1483
1484static int
1485deque_init(dequeobject *deque, PyObject *args, PyObject *kwdargs)
1486{
1487 PyObject *iterable = NULL;
1488 PyObject *maxlenobj = NULL;
1489 Py_ssize_t maxlen = -1;
1490 char *kwlist[] = {"iterable", "maxlen", 0};
1491
1492 if (kwdargs == NULL && PyTuple_GET_SIZE(args) <= 2) {
1493 if (PyTuple_GET_SIZE(args) > 0) {
1494 iterable = PyTuple_GET_ITEM(args, 0);
1495 }
1496 if (PyTuple_GET_SIZE(args) > 1) {
1497 maxlenobj = PyTuple_GET_ITEM(args, 1);
1498 }
1499 } else {
1500 if (!PyArg_ParseTupleAndKeywords(args, kwdargs, "|OO:deque", kwlist,
1501 &iterable, &maxlenobj))
1502 return -1;
1503 }
1504 if (maxlenobj != NULL && maxlenobj != Py_None) {
1505 maxlen = PyLong_AsSsize_t(maxlenobj);
1506 if (maxlen == -1 && PyErr_Occurred())
1507 return -1;
1508 if (maxlen < 0) {
1509 PyErr_SetString(PyExc_ValueError, "maxlen must be non-negative");
1510 return -1;
1511 }
1512 }
1513 deque->maxlen = maxlen;
1514 if (Py_SIZE(deque) > 0)
1515 deque_clear(deque);
1516 if (iterable != NULL) {
1517 PyObject *rv = deque_extend(deque, iterable);
1518 if (rv == NULL)
1519 return -1;
1520 Py_DECREF(rv);
1521 }
1522 return 0;
1523}
1524
1525static PyObject *
1526deque_sizeof(dequeobject *deque, void *unused)
1527{
1528 Py_ssize_t res;
1529 Py_ssize_t blocks;
1530
1531 res = _PyObject_SIZE(Py_TYPE(deque));
1532 blocks = (size_t)(deque->leftindex + Py_SIZE(deque) + BLOCKLEN - 1) / BLOCKLEN;
1533 assert(deque->leftindex + Py_SIZE(deque) - 1 ==
1534 (blocks - 1) * BLOCKLEN + deque->rightindex);
1535 res += blocks * sizeof(block);
1536 return PyLong_FromSsize_t(res);
1537}
1538
1539PyDoc_STRVAR(sizeof_doc,
1540"D.__sizeof__() -- size of D in memory, in bytes");
1541
1542static int
1543deque_bool(dequeobject *deque)
1544{
1545 return Py_SIZE(deque) != 0;
1546}
1547
1548static PyObject *
1549deque_get_maxlen(dequeobject *deque, void *Py_UNUSED(ignored))
1550{
1551 if (deque->maxlen < 0)
1552 Py_RETURN_NONE;
1553 return PyLong_FromSsize_t(deque->maxlen);
1554}
1555
1556
1557/* deque object ********************************************************/
1558
1559static PyGetSetDef deque_getset[] = {
1560 {"maxlen", (getter)deque_get_maxlen, (setter)NULL,
1561 "maximum size of a deque or None if unbounded"},
1562 {0}
1563};
1564
1565static PySequenceMethods deque_as_sequence = {
1566 (lenfunc)deque_len, /* sq_length */
1567 (binaryfunc)deque_concat, /* sq_concat */
1568 (ssizeargfunc)deque_repeat, /* sq_repeat */
1569 (ssizeargfunc)deque_item, /* sq_item */
1570 0, /* sq_slice */
1571 (ssizeobjargproc)deque_ass_item, /* sq_ass_item */
1572 0, /* sq_ass_slice */
1573 (objobjproc)deque_contains, /* sq_contains */
1574 (binaryfunc)deque_inplace_concat, /* sq_inplace_concat */
1575 (ssizeargfunc)deque_inplace_repeat, /* sq_inplace_repeat */
1576};
1577
1578static PyNumberMethods deque_as_number = {
1579 0, /* nb_add */
1580 0, /* nb_subtract */
1581 0, /* nb_multiply */
1582 0, /* nb_remainder */
1583 0, /* nb_divmod */
1584 0, /* nb_power */
1585 0, /* nb_negative */
1586 0, /* nb_positive */
1587 0, /* nb_absolute */
1588 (inquiry)deque_bool, /* nb_bool */
1589 0, /* nb_invert */
1590 };
1591
1592static PyObject *deque_iter(dequeobject *deque);
1593static PyObject *deque_reviter(dequeobject *deque, PyObject *Py_UNUSED(ignored));
1594PyDoc_STRVAR(reversed_doc,
1595 "D.__reversed__() -- return a reverse iterator over the deque");
1596
1597static PyMethodDef deque_methods[] = {
1598 {"append", (PyCFunction)deque_append,
1599 METH_O, append_doc},
1600 {"appendleft", (PyCFunction)deque_appendleft,
1601 METH_O, appendleft_doc},
1602 {"clear", (PyCFunction)deque_clearmethod,
1603 METH_NOARGS, clear_doc},
1604 {"__copy__", deque_copy,
1605 METH_NOARGS, copy_doc},
1606 {"copy", deque_copy,
1607 METH_NOARGS, copy_doc},
1608 {"count", (PyCFunction)deque_count,
1609 METH_O, count_doc},
1610 {"extend", (PyCFunction)deque_extend,
1611 METH_O, extend_doc},
1612 {"extendleft", (PyCFunction)deque_extendleft,
1613 METH_O, extendleft_doc},
1614 {"index", (PyCFunction)(void(*)(void))deque_index,
1615 METH_FASTCALL, index_doc},
1616 {"insert", (PyCFunction)(void(*)(void))deque_insert,
1617 METH_FASTCALL, insert_doc},
1618 {"pop", (PyCFunction)deque_pop,
1619 METH_NOARGS, pop_doc},
1620 {"popleft", (PyCFunction)deque_popleft,
1621 METH_NOARGS, popleft_doc},
1622 {"__reduce__", (PyCFunction)deque_reduce,
1623 METH_NOARGS, reduce_doc},
1624 {"remove", (PyCFunction)deque_remove,
1625 METH_O, remove_doc},
1626 {"__reversed__", (PyCFunction)deque_reviter,
1627 METH_NOARGS, reversed_doc},
1628 {"reverse", (PyCFunction)deque_reverse,
1629 METH_NOARGS, reverse_doc},
1630 {"rotate", (PyCFunction)(void(*)(void))deque_rotate,
1631 METH_FASTCALL, rotate_doc},
1632 {"__sizeof__", (PyCFunction)deque_sizeof,
1633 METH_NOARGS, sizeof_doc},
1634 {"__class_getitem__", (PyCFunction)Py_GenericAlias,
1635 METH_O|METH_CLASS, PyDoc_STR("See PEP 585")},
1636 {NULL, NULL} /* sentinel */
1637};
1638
1639PyDoc_STRVAR(deque_doc,
1640"deque([iterable[, maxlen]]) --> deque object\n\
1641\n\
1642A list-like sequence optimized for data accesses near its endpoints.");
1643
1644static PyTypeObject deque_type = {
1645 PyVarObject_HEAD_INIT(NULL, 0)
1646 "collections.deque", /* tp_name */
1647 sizeof(dequeobject), /* tp_basicsize */
1648 0, /* tp_itemsize */
1649 /* methods */
1650 (destructor)deque_dealloc, /* tp_dealloc */
1651 0, /* tp_vectorcall_offset */
1652 0, /* tp_getattr */
1653 0, /* tp_setattr */
1654 0, /* tp_as_async */
1655 deque_repr, /* tp_repr */
1656 &deque_as_number, /* tp_as_number */
1657 &deque_as_sequence, /* tp_as_sequence */
1658 0, /* tp_as_mapping */
1659 PyObject_HashNotImplemented, /* tp_hash */
1660 0, /* tp_call */
1661 0, /* tp_str */
1662 PyObject_GenericGetAttr, /* tp_getattro */
1663 0, /* tp_setattro */
1664 0, /* tp_as_buffer */
1665 Py_TPFLAGS_DEFAULT | Py_TPFLAGS_BASETYPE |
1666 Py_TPFLAGS_HAVE_GC | Py_TPFLAGS_SEQUENCE,
1667 /* tp_flags */
1668 deque_doc, /* tp_doc */
1669 (traverseproc)deque_traverse, /* tp_traverse */
1670 (inquiry)deque_clear, /* tp_clear */
1671 (richcmpfunc)deque_richcompare, /* tp_richcompare */
1672 offsetof(dequeobject, weakreflist), /* tp_weaklistoffset*/
1673 (getiterfunc)deque_iter, /* tp_iter */
1674 0, /* tp_iternext */
1675 deque_methods, /* tp_methods */
1676 0, /* tp_members */
1677 deque_getset, /* tp_getset */
1678 0, /* tp_base */
1679 0, /* tp_dict */
1680 0, /* tp_descr_get */
1681 0, /* tp_descr_set */
1682 0, /* tp_dictoffset */
1683 (initproc)deque_init, /* tp_init */
1684 PyType_GenericAlloc, /* tp_alloc */
1685 deque_new, /* tp_new */
1686 PyObject_GC_Del, /* tp_free */
1687};
1688
1689/*********************** Deque Iterator **************************/
1690
1691typedef struct {
1692 PyObject_HEAD
1693 block *b;
1694 Py_ssize_t index;
1695 dequeobject *deque;
1696 size_t state; /* state when the iterator is created */
1697 Py_ssize_t counter; /* number of items remaining for iteration */
1698} dequeiterobject;
1699
1700static PyTypeObject dequeiter_type;
1701
1702static PyObject *
1703deque_iter(dequeobject *deque)
1704{
1705 dequeiterobject *it;
1706
1707 it = PyObject_GC_New(dequeiterobject, &dequeiter_type);
1708 if (it == NULL)
1709 return NULL;
1710 it->b = deque->leftblock;
1711 it->index = deque->leftindex;
1712 Py_INCREF(deque);
1713 it->deque = deque;
1714 it->state = deque->state;
1715 it->counter = Py_SIZE(deque);
1716 PyObject_GC_Track(it);
1717 return (PyObject *)it;
1718}
1719
1720static int
1721dequeiter_traverse(dequeiterobject *dio, visitproc visit, void *arg)
1722{
1723 Py_VISIT(dio->deque);
1724 return 0;
1725}
1726
1727static void
1728dequeiter_dealloc(dequeiterobject *dio)
1729{
1730 /* bpo-31095: UnTrack is needed before calling any callbacks */
1731 PyObject_GC_UnTrack(dio);
1732 Py_XDECREF(dio->deque);
1733 PyObject_GC_Del(dio);
1734}
1735
1736static PyObject *
1737dequeiter_next(dequeiterobject *it)
1738{
1739 PyObject *item;
1740
1741 if (it->deque->state != it->state) {
1742 it->counter = 0;
1743 PyErr_SetString(PyExc_RuntimeError,
1744 "deque mutated during iteration");
1745 return NULL;
1746 }
1747 if (it->counter == 0)
1748 return NULL;
1749 assert (!(it->b == it->deque->rightblock &&
1750 it->index > it->deque->rightindex));
1751
1752 item = it->b->data[it->index];
1753 it->index++;
1754 it->counter--;
1755 if (it->index == BLOCKLEN && it->counter > 0) {
1756 CHECK_NOT_END(it->b->rightlink);
1757 it->b = it->b->rightlink;
1758 it->index = 0;
1759 }
1760 Py_INCREF(item);
1761 return item;
1762}
1763
1764static PyObject *
1765dequeiter_new(PyTypeObject *type, PyObject *args, PyObject *kwds)
1766{
1767 Py_ssize_t i, index=0;
1768 PyObject *deque;
1769 dequeiterobject *it;
1770 if (!PyArg_ParseTuple(args, "O!|n", &deque_type, &deque, &index))
1771 return NULL;
1772 assert(type == &dequeiter_type);
1773
1774 it = (dequeiterobject*)deque_iter((dequeobject *)deque);
1775 if (!it)
1776 return NULL;
1777 /* consume items from the queue */
1778 for(i=0; i<index; i++) {
1779 PyObject *item = dequeiter_next(it);
1780 if (item) {
1781 Py_DECREF(item);
1782 } else {
1783 if (it->counter) {
1784 Py_DECREF(it);
1785 return NULL;
1786 } else
1787 break;
1788 }
1789 }
1790 return (PyObject*)it;
1791}
1792
1793static PyObject *
1794dequeiter_len(dequeiterobject *it, PyObject *Py_UNUSED(ignored))
1795{
1796 return PyLong_FromSsize_t(it->counter);
1797}
1798
1799PyDoc_STRVAR(length_hint_doc, "Private method returning an estimate of len(list(it)).");
1800
1801static PyObject *
1802dequeiter_reduce(dequeiterobject *it, PyObject *Py_UNUSED(ignored))
1803{
1804 return Py_BuildValue("O(On)", Py_TYPE(it), it->deque, Py_SIZE(it->deque) - it->counter);
1805}
1806
1807static PyMethodDef dequeiter_methods[] = {
1808 {"__length_hint__", (PyCFunction)dequeiter_len, METH_NOARGS, length_hint_doc},
1809 {"__reduce__", (PyCFunction)dequeiter_reduce, METH_NOARGS, reduce_doc},
1810 {NULL, NULL} /* sentinel */
1811};
1812
1813static PyTypeObject dequeiter_type = {
1814 PyVarObject_HEAD_INIT(NULL, 0)
1815 "_collections._deque_iterator", /* tp_name */
1816 sizeof(dequeiterobject), /* tp_basicsize */
1817 0, /* tp_itemsize */
1818 /* methods */
1819 (destructor)dequeiter_dealloc, /* tp_dealloc */
1820 0, /* tp_vectorcall_offset */
1821 0, /* tp_getattr */
1822 0, /* tp_setattr */
1823 0, /* tp_as_async */
1824 0, /* tp_repr */
1825 0, /* tp_as_number */
1826 0, /* tp_as_sequence */
1827 0, /* tp_as_mapping */
1828 0, /* tp_hash */
1829 0, /* tp_call */
1830 0, /* tp_str */
1831 PyObject_GenericGetAttr, /* tp_getattro */
1832 0, /* tp_setattro */
1833 0, /* tp_as_buffer */
1834 Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC, /* tp_flags */
1835 0, /* tp_doc */
1836 (traverseproc)dequeiter_traverse, /* tp_traverse */
1837 0, /* tp_clear */
1838 0, /* tp_richcompare */
1839 0, /* tp_weaklistoffset */
1840 PyObject_SelfIter, /* tp_iter */
1841 (iternextfunc)dequeiter_next, /* tp_iternext */
1842 dequeiter_methods, /* tp_methods */
1843 0, /* tp_members */
1844 0, /* tp_getset */
1845 0, /* tp_base */
1846 0, /* tp_dict */
1847 0, /* tp_descr_get */
1848 0, /* tp_descr_set */
1849 0, /* tp_dictoffset */
1850 0, /* tp_init */
1851 0, /* tp_alloc */
1852 dequeiter_new, /* tp_new */
1853 0,
1854};
1855
1856/*********************** Deque Reverse Iterator **************************/
1857
1858static PyTypeObject dequereviter_type;
1859
1860static PyObject *
1861deque_reviter(dequeobject *deque, PyObject *Py_UNUSED(ignored))
1862{
1863 dequeiterobject *it;
1864
1865 it = PyObject_GC_New(dequeiterobject, &dequereviter_type);
1866 if (it == NULL)
1867 return NULL;
1868 it->b = deque->rightblock;
1869 it->index = deque->rightindex;
1870 Py_INCREF(deque);
1871 it->deque = deque;
1872 it->state = deque->state;
1873 it->counter = Py_SIZE(deque);
1874 PyObject_GC_Track(it);
1875 return (PyObject *)it;
1876}
1877
1878static PyObject *
1879dequereviter_next(dequeiterobject *it)
1880{
1881 PyObject *item;
1882 if (it->counter == 0)
1883 return NULL;
1884
1885 if (it->deque->state != it->state) {
1886 it->counter = 0;
1887 PyErr_SetString(PyExc_RuntimeError,
1888 "deque mutated during iteration");
1889 return NULL;
1890 }
1891 assert (!(it->b == it->deque->leftblock &&
1892 it->index < it->deque->leftindex));
1893
1894 item = it->b->data[it->index];
1895 it->index--;
1896 it->counter--;
1897 if (it->index < 0 && it->counter > 0) {
1898 CHECK_NOT_END(it->b->leftlink);
1899 it->b = it->b->leftlink;
1900 it->index = BLOCKLEN - 1;
1901 }
1902 Py_INCREF(item);
1903 return item;
1904}
1905
1906static PyObject *
1907dequereviter_new(PyTypeObject *type, PyObject *args, PyObject *kwds)
1908{
1909 Py_ssize_t i, index=0;
1910 PyObject *deque;
1911 dequeiterobject *it;
1912 if (!PyArg_ParseTuple(args, "O!|n", &deque_type, &deque, &index))
1913 return NULL;
1914 assert(type == &dequereviter_type);
1915
1916 it = (dequeiterobject*)deque_reviter((dequeobject *)deque, NULL);
1917 if (!it)
1918 return NULL;
1919 /* consume items from the queue */
1920 for(i=0; i<index; i++) {
1921 PyObject *item = dequereviter_next(it);
1922 if (item) {
1923 Py_DECREF(item);
1924 } else {
1925 if (it->counter) {
1926 Py_DECREF(it);
1927 return NULL;
1928 } else
1929 break;
1930 }
1931 }
1932 return (PyObject*)it;
1933}
1934
1935static PyTypeObject dequereviter_type = {
1936 PyVarObject_HEAD_INIT(NULL, 0)
1937 "_collections._deque_reverse_iterator", /* tp_name */
1938 sizeof(dequeiterobject), /* tp_basicsize */
1939 0, /* tp_itemsize */
1940 /* methods */
1941 (destructor)dequeiter_dealloc, /* tp_dealloc */
1942 0, /* tp_vectorcall_offset */
1943 0, /* tp_getattr */
1944 0, /* tp_setattr */
1945 0, /* tp_as_async */
1946 0, /* tp_repr */
1947 0, /* tp_as_number */
1948 0, /* tp_as_sequence */
1949 0, /* tp_as_mapping */
1950 0, /* tp_hash */
1951 0, /* tp_call */
1952 0, /* tp_str */
1953 PyObject_GenericGetAttr, /* tp_getattro */
1954 0, /* tp_setattro */
1955 0, /* tp_as_buffer */
1956 Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC, /* tp_flags */
1957 0, /* tp_doc */
1958 (traverseproc)dequeiter_traverse, /* tp_traverse */
1959 0, /* tp_clear */
1960 0, /* tp_richcompare */
1961 0, /* tp_weaklistoffset */
1962 PyObject_SelfIter, /* tp_iter */
1963 (iternextfunc)dequereviter_next, /* tp_iternext */
1964 dequeiter_methods, /* tp_methods */
1965 0, /* tp_members */
1966 0, /* tp_getset */
1967 0, /* tp_base */
1968 0, /* tp_dict */
1969 0, /* tp_descr_get */
1970 0, /* tp_descr_set */
1971 0, /* tp_dictoffset */
1972 0, /* tp_init */
1973 0, /* tp_alloc */
1974 dequereviter_new, /* tp_new */
1975 0,
1976};
1977
1978/* defaultdict type *********************************************************/
1979
1980typedef struct {
1981 PyDictObject dict;
1982 PyObject *default_factory;
1983} defdictobject;
1984
1985static PyTypeObject defdict_type; /* Forward */
1986
1987PyDoc_STRVAR(defdict_missing_doc,
1988"__missing__(key) # Called by __getitem__ for missing key; pseudo-code:\n\
1989 if self.default_factory is None: raise KeyError((key,))\n\
1990 self[key] = value = self.default_factory()\n\
1991 return value\n\
1992");
1993
1994static PyObject *
1995defdict_missing(defdictobject *dd, PyObject *key)
1996{
1997 PyObject *factory = dd->default_factory;
1998 PyObject *value;
1999 if (factory == NULL || factory == Py_None) {
2000 /* XXX Call dict.__missing__(key) */
2001 PyObject *tup;
2002 tup = PyTuple_Pack(1, key);
2003 if (!tup) return NULL;
2004 PyErr_SetObject(PyExc_KeyError, tup);
2005 Py_DECREF(tup);
2006 return NULL;
2007 }
2008 value = _PyObject_CallNoArg(factory);
2009 if (value == NULL)
2010 return value;
2011 if (PyObject_SetItem((PyObject *)dd, key, value) < 0) {
2012 Py_DECREF(value);
2013 return NULL;
2014 }
2015 return value;
2016}
2017
2018static inline PyObject*
2019new_defdict(defdictobject *dd, PyObject *arg)
2020{
2021 return PyObject_CallFunctionObjArgs((PyObject*)Py_TYPE(dd),
2022 dd->default_factory ? dd->default_factory : Py_None, arg, NULL);
2023}
2024
2025PyDoc_STRVAR(defdict_copy_doc, "D.copy() -> a shallow copy of D.");
2026
2027static PyObject *
2028defdict_copy(defdictobject *dd, PyObject *Py_UNUSED(ignored))
2029{
2030 /* This calls the object's class. That only works for subclasses
2031 whose class constructor has the same signature. Subclasses that
2032 define a different constructor signature must override copy().
2033 */
2034 return new_defdict(dd, (PyObject*)dd);
2035}
2036
2037static PyObject *
2038defdict_reduce(defdictobject *dd, PyObject *Py_UNUSED(ignored))
2039{
2040 /* __reduce__ must return a 5-tuple as follows:
2041
2042 - factory function
2043 - tuple of args for the factory function
2044 - additional state (here None)
2045 - sequence iterator (here None)
2046 - dictionary iterator (yielding successive (key, value) pairs
2047
2048 This API is used by pickle.py and copy.py.
2049
2050 For this to be useful with pickle.py, the default_factory
2051 must be picklable; e.g., None, a built-in, or a global
2052 function in a module or package.
2053
2054 Both shallow and deep copying are supported, but for deep
2055 copying, the default_factory must be deep-copyable; e.g. None,
2056 or a built-in (functions are not copyable at this time).
2057
2058 This only works for subclasses as long as their constructor
2059 signature is compatible; the first argument must be the
2060 optional default_factory, defaulting to None.
2061 */
2062 PyObject *args;
2063 PyObject *items;
2064 PyObject *iter;
2065 PyObject *result;
2066 _Py_IDENTIFIER(items);
2067
2068 if (dd->default_factory == NULL || dd->default_factory == Py_None)
2069 args = PyTuple_New(0);
2070 else
2071 args = PyTuple_Pack(1, dd->default_factory);
2072 if (args == NULL)
2073 return NULL;
2074 items = _PyObject_CallMethodIdNoArgs((PyObject *)dd, &PyId_items);
2075 if (items == NULL) {
2076 Py_DECREF(args);
2077 return NULL;
2078 }
2079 iter = PyObject_GetIter(items);
2080 if (iter == NULL) {
2081 Py_DECREF(items);
2082 Py_DECREF(args);
2083 return NULL;
2084 }
2085 result = PyTuple_Pack(5, Py_TYPE(dd), args,
2086 Py_None, Py_None, iter);
2087 Py_DECREF(iter);
2088 Py_DECREF(items);
2089 Py_DECREF(args);
2090 return result;
2091}
2092
2093static PyMethodDef defdict_methods[] = {
2094 {"__missing__", (PyCFunction)defdict_missing, METH_O,
2095 defdict_missing_doc},
2096 {"copy", (PyCFunction)defdict_copy, METH_NOARGS,
2097 defdict_copy_doc},
2098 {"__copy__", (PyCFunction)defdict_copy, METH_NOARGS,
2099 defdict_copy_doc},
2100 {"__reduce__", (PyCFunction)defdict_reduce, METH_NOARGS,
2101 reduce_doc},
2102 {"__class_getitem__", (PyCFunction)Py_GenericAlias, METH_O|METH_CLASS,
2103 PyDoc_STR("See PEP 585")},
2104 {NULL}
2105};
2106
2107static PyMemberDef defdict_members[] = {
2108 {"default_factory", T_OBJECT,
2109 offsetof(defdictobject, default_factory), 0,
2110 PyDoc_STR("Factory for default value called by __missing__().")},
2111 {NULL}
2112};
2113
2114static void
2115defdict_dealloc(defdictobject *dd)
2116{
2117 /* bpo-31095: UnTrack is needed before calling any callbacks */
2118 PyObject_GC_UnTrack(dd);
2119 Py_CLEAR(dd->default_factory);
2120 PyDict_Type.tp_dealloc((PyObject *)dd);
2121}
2122
2123static PyObject *
2124defdict_repr(defdictobject *dd)
2125{
2126 PyObject *baserepr;
2127 PyObject *defrepr;
2128 PyObject *result;
2129 baserepr = PyDict_Type.tp_repr((PyObject *)dd);
2130 if (baserepr == NULL)
2131 return NULL;
2132 if (dd->default_factory == NULL)
2133 defrepr = PyUnicode_FromString("None");
2134 else
2135 {
2136 int status = Py_ReprEnter(dd->default_factory);
2137 if (status != 0) {
2138 if (status < 0) {
2139 Py_DECREF(baserepr);
2140 return NULL;
2141 }
2142 defrepr = PyUnicode_FromString("...");
2143 }
2144 else
2145 defrepr = PyObject_Repr(dd->default_factory);
2146 Py_ReprLeave(dd->default_factory);
2147 }
2148 if (defrepr == NULL) {
2149 Py_DECREF(baserepr);
2150 return NULL;
2151 }
2152 result = PyUnicode_FromFormat("%s(%U, %U)",
2153 _PyType_Name(Py_TYPE(dd)),
2154 defrepr, baserepr);
2155 Py_DECREF(defrepr);
2156 Py_DECREF(baserepr);
2157 return result;
2158}
2159
2160static PyObject*
2161defdict_or(PyObject* left, PyObject* right)
2162{
2163 PyObject *self, *other;
2164 if (PyObject_TypeCheck(left, &defdict_type)) {
2165 self = left;
2166 other = right;
2167 }
2168 else {
2169 self = right;
2170 other = left;
2171 }
2172 if (!PyDict_Check(other)) {
2173 Py_RETURN_NOTIMPLEMENTED;
2174 }
2175 // Like copy(), this calls the object's class.
2176 // Override __or__/__ror__ for subclasses with different constructors.
2177 PyObject *new = new_defdict((defdictobject*)self, left);
2178 if (!new) {
2179 return NULL;
2180 }
2181 if (PyDict_Update(new, right)) {
2182 Py_DECREF(new);
2183 return NULL;
2184 }
2185 return new;
2186}
2187
2188static PyNumberMethods defdict_as_number = {
2189 .nb_or = defdict_or,
2190};
2191
2192static int
2193defdict_traverse(PyObject *self, visitproc visit, void *arg)
2194{
2195 Py_VISIT(((defdictobject *)self)->default_factory);
2196 return PyDict_Type.tp_traverse(self, visit, arg);
2197}
2198
2199static int
2200defdict_tp_clear(defdictobject *dd)
2201{
2202 Py_CLEAR(dd->default_factory);
2203 return PyDict_Type.tp_clear((PyObject *)dd);
2204}
2205
2206static int
2207defdict_init(PyObject *self, PyObject *args, PyObject *kwds)
2208{
2209 defdictobject *dd = (defdictobject *)self;
2210 PyObject *olddefault = dd->default_factory;
2211 PyObject *newdefault = NULL;
2212 PyObject *newargs;
2213 int result;
2214 if (args == NULL || !PyTuple_Check(args))
2215 newargs = PyTuple_New(0);
2216 else {
2217 Py_ssize_t n = PyTuple_GET_SIZE(args);
2218 if (n > 0) {
2219 newdefault = PyTuple_GET_ITEM(args, 0);
2220 if (!PyCallable_Check(newdefault) && newdefault != Py_None) {
2221 PyErr_SetString(PyExc_TypeError,
2222 "first argument must be callable or None");
2223 return -1;
2224 }
2225 }
2226 newargs = PySequence_GetSlice(args, 1, n);
2227 }
2228 if (newargs == NULL)
2229 return -1;
2230 Py_XINCREF(newdefault);
2231 dd->default_factory = newdefault;
2232 result = PyDict_Type.tp_init(self, newargs, kwds);
2233 Py_DECREF(newargs);
2234 Py_XDECREF(olddefault);
2235 return result;
2236}
2237
2238PyDoc_STRVAR(defdict_doc,
2239"defaultdict(default_factory=None, /, [...]) --> dict with default factory\n\
2240\n\
2241The default factory is called without arguments to produce\n\
2242a new value when a key is not present, in __getitem__ only.\n\
2243A defaultdict compares equal to a dict with the same items.\n\
2244All remaining arguments are treated the same as if they were\n\
2245passed to the dict constructor, including keyword arguments.\n\
2246");
2247
2248/* See comment in xxsubtype.c */
2249#define DEFERRED_ADDRESS(ADDR) 0
2250
2251static PyTypeObject defdict_type = {
2252 PyVarObject_HEAD_INIT(DEFERRED_ADDRESS(&PyType_Type), 0)
2253 "collections.defaultdict", /* tp_name */
2254 sizeof(defdictobject), /* tp_basicsize */
2255 0, /* tp_itemsize */
2256 /* methods */
2257 (destructor)defdict_dealloc, /* tp_dealloc */
2258 0, /* tp_vectorcall_offset */
2259 0, /* tp_getattr */
2260 0, /* tp_setattr */
2261 0, /* tp_as_async */
2262 (reprfunc)defdict_repr, /* tp_repr */
2263 &defdict_as_number, /* tp_as_number */
2264 0, /* tp_as_sequence */
2265 0, /* tp_as_mapping */
2266 0, /* tp_hash */
2267 0, /* tp_call */
2268 0, /* tp_str */
2269 PyObject_GenericGetAttr, /* tp_getattro */
2270 0, /* tp_setattro */
2271 0, /* tp_as_buffer */
2272 Py_TPFLAGS_DEFAULT | Py_TPFLAGS_BASETYPE | Py_TPFLAGS_HAVE_GC,
2273 /* tp_flags */
2274 defdict_doc, /* tp_doc */
2275 defdict_traverse, /* tp_traverse */
2276 (inquiry)defdict_tp_clear, /* tp_clear */
2277 0, /* tp_richcompare */
2278 0, /* tp_weaklistoffset*/
2279 0, /* tp_iter */
2280 0, /* tp_iternext */
2281 defdict_methods, /* tp_methods */
2282 defdict_members, /* tp_members */
2283 0, /* tp_getset */
2284 DEFERRED_ADDRESS(&PyDict_Type), /* tp_base */
2285 0, /* tp_dict */
2286 0, /* tp_descr_get */
2287 0, /* tp_descr_set */
2288 0, /* tp_dictoffset */
2289 defdict_init, /* tp_init */
2290 PyType_GenericAlloc, /* tp_alloc */
2291 0, /* tp_new */
2292 PyObject_GC_Del, /* tp_free */
2293};
2294
2295/* helper function for Counter *********************************************/
2296
2297/*[clinic input]
2298_collections._count_elements
2299
2300 mapping: object
2301 iterable: object
2302 /
2303
2304Count elements in the iterable, updating the mapping
2305[clinic start generated code]*/
2306
2307static PyObject *
2308_collections__count_elements_impl(PyObject *module, PyObject *mapping,
2309 PyObject *iterable)
2310/*[clinic end generated code: output=7e0c1789636b3d8f input=e79fad04534a0b45]*/
2311{
2312 _Py_IDENTIFIER(get);
2313 _Py_IDENTIFIER(__setitem__);
2314 PyObject *it, *oldval;
2315 PyObject *newval = NULL;
2316 PyObject *key = NULL;
2317 PyObject *bound_get = NULL;
2318 PyObject *mapping_get;
2319 PyObject *dict_get;
2320 PyObject *mapping_setitem;
2321 PyObject *dict_setitem;
2322 PyObject *one = _PyLong_GetOne(); // borrowed reference
2323
2324 it = PyObject_GetIter(iterable);
2325 if (it == NULL)
2326 return NULL;
2327
2328 /* Only take the fast path when get() and __setitem__()
2329 * have not been overridden.
2330 */
2331 mapping_get = _PyType_LookupId(Py_TYPE(mapping), &PyId_get);
2332 dict_get = _PyType_LookupId(&PyDict_Type, &PyId_get);
2333 mapping_setitem = _PyType_LookupId(Py_TYPE(mapping), &PyId___setitem__);
2334 dict_setitem = _PyType_LookupId(&PyDict_Type, &PyId___setitem__);
2335
2336 if (mapping_get != NULL && mapping_get == dict_get &&
2337 mapping_setitem != NULL && mapping_setitem == dict_setitem &&
2338 PyDict_Check(mapping))
2339 {
2340 while (1) {
2341 /* Fast path advantages:
2342 1. Eliminate double hashing
2343 (by re-using the same hash for both the get and set)
2344 2. Avoid argument overhead of PyObject_CallFunctionObjArgs
2345 (argument tuple creation and parsing)
2346 3. Avoid indirection through a bound method object
2347 (creates another argument tuple)
2348 4. Avoid initial increment from zero
2349 (reuse an existing one-object instead)
2350 */
2351 Py_hash_t hash;
2352
2353 key = PyIter_Next(it);
2354 if (key == NULL)
2355 break;
2356
2357 if (!PyUnicode_CheckExact(key) ||
2358 (hash = ((PyASCIIObject *) key)->hash) == -1)
2359 {
2360 hash = PyObject_Hash(key);
2361 if (hash == -1)
2362 goto done;
2363 }
2364
2365 oldval = _PyDict_GetItem_KnownHash(mapping, key, hash);
2366 if (oldval == NULL) {
2367 if (PyErr_Occurred())
2368 goto done;
2369 if (_PyDict_SetItem_KnownHash(mapping, key, one, hash) < 0)
2370 goto done;
2371 } else {
2372 newval = PyNumber_Add(oldval, one);
2373 if (newval == NULL)
2374 goto done;
2375 if (_PyDict_SetItem_KnownHash(mapping, key, newval, hash) < 0)
2376 goto done;
2377 Py_CLEAR(newval);
2378 }
2379 Py_DECREF(key);
2380 }
2381 }
2382 else {
2383 bound_get = _PyObject_GetAttrId(mapping, &PyId_get);
2384 if (bound_get == NULL)
2385 goto done;
2386
2387 PyObject *zero = _PyLong_GetZero(); // borrowed reference
2388 while (1) {
2389 key = PyIter_Next(it);
2390 if (key == NULL)
2391 break;
2392 oldval = PyObject_CallFunctionObjArgs(bound_get, key, zero, NULL);
2393 if (oldval == NULL)
2394 break;
2395 newval = PyNumber_Add(oldval, one);
2396 Py_DECREF(oldval);
2397 if (newval == NULL)
2398 break;
2399 if (PyObject_SetItem(mapping, key, newval) < 0)
2400 break;
2401 Py_CLEAR(newval);
2402 Py_DECREF(key);
2403 }
2404 }
2405
2406done:
2407 Py_DECREF(it);
2408 Py_XDECREF(key);
2409 Py_XDECREF(newval);
2410 Py_XDECREF(bound_get);
2411 if (PyErr_Occurred())
2412 return NULL;
2413 Py_RETURN_NONE;
2414}
2415
2416/* Helper function for namedtuple() ************************************/
2417
2418typedef struct {
2419 PyObject_HEAD
2420 Py_ssize_t index;
2421 PyObject* doc;
2422} _tuplegetterobject;
2423
2424/*[clinic input]
2425@classmethod
2426_tuplegetter.__new__ as tuplegetter_new
2427
2428 index: Py_ssize_t
2429 doc: object
2430 /
2431[clinic start generated code]*/
2432
2433static PyObject *
2434tuplegetter_new_impl(PyTypeObject *type, Py_ssize_t index, PyObject *doc)
2435/*[clinic end generated code: output=014be444ad80263f input=87c576a5bdbc0bbb]*/
2436{
2437 _tuplegetterobject* self;
2438 self = (_tuplegetterobject *)type->tp_alloc(type, 0);
2439 if (self == NULL) {
2440 return NULL;
2441 }
2442 self->index = index;
2443 Py_INCREF(doc);
2444 self->doc = doc;
2445 return (PyObject *)self;
2446}
2447
2448static PyObject *
2449tuplegetter_descr_get(PyObject *self, PyObject *obj, PyObject *type)
2450{
2451 Py_ssize_t index = ((_tuplegetterobject*)self)->index;
2452 PyObject *result;
2453
2454 if (obj == NULL) {
2455 Py_INCREF(self);
2456 return self;
2457 }
2458 if (!PyTuple_Check(obj)) {
2459 if (obj == Py_None) {
2460 Py_INCREF(self);
2461 return self;
2462 }
2463 PyErr_Format(PyExc_TypeError,
2464 "descriptor for index '%zd' for tuple subclasses "
2465 "doesn't apply to '%s' object",
2466 index,
2467 Py_TYPE(obj)->tp_name);
2468 return NULL;
2469 }
2470
2471 if (!valid_index(index, PyTuple_GET_SIZE(obj))) {
2472 PyErr_SetString(PyExc_IndexError, "tuple index out of range");
2473 return NULL;
2474 }
2475
2476 result = PyTuple_GET_ITEM(obj, index);
2477 Py_INCREF(result);
2478 return result;
2479}
2480
2481static int
2482tuplegetter_descr_set(PyObject *self, PyObject *obj, PyObject *value)
2483{
2484 if (value == NULL) {
2485 PyErr_SetString(PyExc_AttributeError, "can't delete attribute");
2486 } else {
2487 PyErr_SetString(PyExc_AttributeError, "can't set attribute");
2488 }
2489 return -1;
2490}
2491
2492static int
2493tuplegetter_traverse(PyObject *self, visitproc visit, void *arg)
2494{
2495 _tuplegetterobject *tuplegetter = (_tuplegetterobject *)self;
2496 Py_VISIT(tuplegetter->doc);
2497 return 0;
2498}
2499
2500static int
2501tuplegetter_clear(PyObject *self)
2502{
2503 _tuplegetterobject *tuplegetter = (_tuplegetterobject *)self;
2504 Py_CLEAR(tuplegetter->doc);
2505 return 0;
2506}
2507
2508static void
2509tuplegetter_dealloc(_tuplegetterobject *self)
2510{
2511 PyObject_GC_UnTrack(self);
2512 tuplegetter_clear((PyObject*)self);
2513 Py_TYPE(self)->tp_free((PyObject*)self);
2514}
2515
2516static PyObject*
2517tuplegetter_reduce(_tuplegetterobject *self, PyObject *Py_UNUSED(ignored))
2518{
2519 return Py_BuildValue("(O(nO))", (PyObject*) Py_TYPE(self), self->index, self->doc);
2520}
2521
2522static PyObject*
2523tuplegetter_repr(_tuplegetterobject *self)
2524{
2525 return PyUnicode_FromFormat("%s(%zd, %R)",
2526 _PyType_Name(Py_TYPE(self)),
2527 self->index, self->doc);
2528}
2529
2530
2531static PyMemberDef tuplegetter_members[] = {
2532 {"__doc__", T_OBJECT, offsetof(_tuplegetterobject, doc), 0},
2533 {0}
2534};
2535
2536static PyMethodDef tuplegetter_methods[] = {
2537 {"__reduce__", (PyCFunction)tuplegetter_reduce, METH_NOARGS, NULL},
2538 {NULL},
2539};
2540
2541static PyTypeObject tuplegetter_type = {
2542 PyVarObject_HEAD_INIT(NULL, 0)
2543 "_collections._tuplegetter", /* tp_name */
2544 sizeof(_tuplegetterobject), /* tp_basicsize */
2545 0, /* tp_itemsize */
2546 /* methods */
2547 (destructor)tuplegetter_dealloc, /* tp_dealloc */
2548 0, /* tp_vectorcall_offset */
2549 0, /* tp_getattr */
2550 0, /* tp_setattr */
2551 0, /* tp_as_async */
2552 (reprfunc)tuplegetter_repr, /* tp_repr */
2553 0, /* tp_as_number */
2554 0, /* tp_as_sequence */
2555 0, /* tp_as_mapping */
2556 0, /* tp_hash */
2557 0, /* tp_call */
2558 0, /* tp_str */
2559 0, /* tp_getattro */
2560 0, /* tp_setattro */
2561 0, /* tp_as_buffer */
2562 Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC, /* tp_flags */
2563 0, /* tp_doc */
2564 (traverseproc)tuplegetter_traverse, /* tp_traverse */
2565 (inquiry)tuplegetter_clear, /* tp_clear */
2566 0, /* tp_richcompare */
2567 0, /* tp_weaklistoffset */
2568 0, /* tp_iter */
2569 0, /* tp_iternext */
2570 tuplegetter_methods, /* tp_methods */
2571 tuplegetter_members, /* tp_members */
2572 0, /* tp_getset */
2573 0, /* tp_base */
2574 0, /* tp_dict */
2575 tuplegetter_descr_get, /* tp_descr_get */
2576 tuplegetter_descr_set, /* tp_descr_set */
2577 0, /* tp_dictoffset */
2578 0, /* tp_init */
2579 0, /* tp_alloc */
2580 tuplegetter_new, /* tp_new */
2581 0,
2582};
2583
2584
2585/* module level code ********************************************************/
2586
2587PyDoc_STRVAR(collections_doc,
2588"High performance data structures.\n\
2589- deque: ordered collection accessible from endpoints only\n\
2590- defaultdict: dict subclass with a default value factory\n\
2591");
2592
2593static struct PyMethodDef collections_methods[] = {
2594 _COLLECTIONS__COUNT_ELEMENTS_METHODDEF
2595 {NULL, NULL} /* sentinel */
2596};
2597
2598static int
2599collections_exec(PyObject *module) {
2600 PyTypeObject *typelist[] = {
2601 &deque_type,
2602 &defdict_type,
2603 &PyODict_Type,
2604 &dequeiter_type,
2605 &dequereviter_type,
2606 &tuplegetter_type
2607 };
2608
2609 defdict_type.tp_base = &PyDict_Type;
2610
2611 for (size_t i = 0; i < Py_ARRAY_LENGTH(typelist); i++) {
2612 if (PyModule_AddType(module, typelist[i]) < 0) {
2613 return -1;
2614 }
2615 }
2616
2617 return 0;
2618}
2619
2620static struct PyModuleDef_Slot collections_slots[] = {
2621 {Py_mod_exec, collections_exec},
2622 {0, NULL}
2623};
2624
2625static struct PyModuleDef _collectionsmodule = {
2626 PyModuleDef_HEAD_INIT,
2627 "_collections",
2628 collections_doc,
2629 0,
2630 collections_methods,
2631 collections_slots,
2632 NULL,
2633 NULL,
2634 NULL
2635};
2636
2637PyMODINIT_FUNC
2638PyInit__collections(void)
2639{
2640 return PyModuleDef_Init(&_collectionsmodule);
2641}
2642