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