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