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 Py_INCREF(item);
970 cmp = PyObject_RichCompareBool(item, v, Py_EQ);
971 Py_DECREF(item);
972 if (cmp < 0)
973 return NULL;
974 count += cmp;
975
976 if (start_state != deque->state) {
977 PyErr_SetString(PyExc_RuntimeError,
978 "deque mutated during iteration");
979 return NULL;
980 }
981
982 /* Advance left block/index pair */
983 index++;
984 if (index == BLOCKLEN) {
985 b = b->rightlink;
986 index = 0;
987 }
988 }
989 return PyLong_FromSsize_t(count);
990 }
991
992 PyDoc_STRVAR(count_doc,
993 "D.count(value) -> integer -- return number of occurrences of value");
994
995 static int
deque_contains(dequeobject * deque,PyObject * v)996 deque_contains(dequeobject *deque, PyObject *v)
997 {
998 block *b = deque->leftblock;
999 Py_ssize_t index = deque->leftindex;
1000 Py_ssize_t n = Py_SIZE(deque);
1001 size_t start_state = deque->state;
1002 PyObject *item;
1003 int cmp;
1004
1005 while (--n >= 0) {
1006 CHECK_NOT_END(b);
1007 item = b->data[index];
1008 Py_INCREF(item);
1009 cmp = PyObject_RichCompareBool(item, v, Py_EQ);
1010 Py_DECREF(item);
1011 if (cmp) {
1012 return cmp;
1013 }
1014 if (start_state != deque->state) {
1015 PyErr_SetString(PyExc_RuntimeError,
1016 "deque mutated during iteration");
1017 return -1;
1018 }
1019 index++;
1020 if (index == BLOCKLEN) {
1021 b = b->rightlink;
1022 index = 0;
1023 }
1024 }
1025 return 0;
1026 }
1027
1028 static Py_ssize_t
deque_len(dequeobject * deque)1029 deque_len(dequeobject *deque)
1030 {
1031 return Py_SIZE(deque);
1032 }
1033
1034 static PyObject *
deque_index(dequeobject * deque,PyObject * const * args,Py_ssize_t nargs)1035 deque_index(dequeobject *deque, PyObject *const *args, Py_ssize_t nargs)
1036 {
1037 Py_ssize_t i, n, start=0, stop=Py_SIZE(deque);
1038 PyObject *v, *item;
1039 block *b = deque->leftblock;
1040 Py_ssize_t index = deque->leftindex;
1041 size_t start_state = deque->state;
1042 int cmp;
1043
1044 if (!_PyArg_ParseStack(args, nargs, "O|O&O&:index", &v,
1045 _PyEval_SliceIndexNotNone, &start,
1046 _PyEval_SliceIndexNotNone, &stop)) {
1047 return NULL;
1048 }
1049
1050 if (start < 0) {
1051 start += Py_SIZE(deque);
1052 if (start < 0)
1053 start = 0;
1054 }
1055 if (stop < 0) {
1056 stop += Py_SIZE(deque);
1057 if (stop < 0)
1058 stop = 0;
1059 }
1060 if (stop > Py_SIZE(deque))
1061 stop = Py_SIZE(deque);
1062 if (start > stop)
1063 start = stop;
1064 assert(0 <= start && start <= stop && stop <= Py_SIZE(deque));
1065
1066 for (i=0 ; i < start - BLOCKLEN ; i += BLOCKLEN) {
1067 b = b->rightlink;
1068 }
1069 for ( ; i < start ; i++) {
1070 index++;
1071 if (index == BLOCKLEN) {
1072 b = b->rightlink;
1073 index = 0;
1074 }
1075 }
1076
1077 n = stop - i;
1078 while (--n >= 0) {
1079 CHECK_NOT_END(b);
1080 item = b->data[index];
1081 cmp = PyObject_RichCompareBool(item, v, Py_EQ);
1082 if (cmp > 0)
1083 return PyLong_FromSsize_t(stop - n - 1);
1084 if (cmp < 0)
1085 return NULL;
1086 if (start_state != deque->state) {
1087 PyErr_SetString(PyExc_RuntimeError,
1088 "deque mutated during iteration");
1089 return NULL;
1090 }
1091 index++;
1092 if (index == BLOCKLEN) {
1093 b = b->rightlink;
1094 index = 0;
1095 }
1096 }
1097 PyErr_Format(PyExc_ValueError, "%R is not in deque", v);
1098 return NULL;
1099 }
1100
1101 PyDoc_STRVAR(index_doc,
1102 "D.index(value, [start, [stop]]) -> integer -- return first index of value.\n"
1103 "Raises ValueError if the value is not present.");
1104
1105 /* insert(), remove(), and delitem() are implemented in terms of
1106 rotate() for simplicity and reasonable performance near the end
1107 points. If for some reason these methods become popular, it is not
1108 hard to re-implement this using direct data movement (similar to
1109 the code used in list slice assignments) and achieve a performance
1110 boost (by moving each pointer only once instead of twice).
1111 */
1112
1113 static PyObject *
deque_insert(dequeobject * deque,PyObject * const * args,Py_ssize_t nargs)1114 deque_insert(dequeobject *deque, PyObject *const *args, Py_ssize_t nargs)
1115 {
1116 Py_ssize_t index;
1117 Py_ssize_t n = Py_SIZE(deque);
1118 PyObject *value;
1119 PyObject *rv;
1120
1121 if (!_PyArg_ParseStack(args, nargs, "nO:insert", &index, &value)) {
1122 return NULL;
1123 }
1124
1125 if (deque->maxlen == Py_SIZE(deque)) {
1126 PyErr_SetString(PyExc_IndexError, "deque already at its maximum size");
1127 return NULL;
1128 }
1129 if (index >= n)
1130 return deque_append(deque, value);
1131 if (index <= -n || index == 0)
1132 return deque_appendleft(deque, value);
1133 if (_deque_rotate(deque, -index))
1134 return NULL;
1135 if (index < 0)
1136 rv = deque_append(deque, value);
1137 else
1138 rv = deque_appendleft(deque, value);
1139 if (rv == NULL)
1140 return NULL;
1141 Py_DECREF(rv);
1142 if (_deque_rotate(deque, index))
1143 return NULL;
1144 Py_RETURN_NONE;
1145 }
1146
1147 PyDoc_STRVAR(insert_doc,
1148 "D.insert(index, object) -- insert object before index");
1149
1150 static PyObject *
deque_remove(dequeobject * deque,PyObject * value)1151 deque_remove(dequeobject *deque, PyObject *value)
1152 {
1153 Py_ssize_t i, n=Py_SIZE(deque);
1154
1155 for (i=0 ; i<n ; i++) {
1156 PyObject *item = deque->leftblock->data[deque->leftindex];
1157 int cmp = PyObject_RichCompareBool(item, value, Py_EQ);
1158
1159 if (Py_SIZE(deque) != n) {
1160 PyErr_SetString(PyExc_IndexError,
1161 "deque mutated during remove().");
1162 return NULL;
1163 }
1164 if (cmp > 0) {
1165 PyObject *tgt = deque_popleft(deque, NULL);
1166 assert (tgt != NULL);
1167 if (_deque_rotate(deque, i))
1168 return NULL;
1169 Py_DECREF(tgt);
1170 Py_RETURN_NONE;
1171 }
1172 else if (cmp < 0) {
1173 _deque_rotate(deque, i);
1174 return NULL;
1175 }
1176 _deque_rotate(deque, -1);
1177 }
1178 PyErr_SetString(PyExc_ValueError, "deque.remove(x): x not in deque");
1179 return NULL;
1180 }
1181
1182 PyDoc_STRVAR(remove_doc,
1183 "D.remove(value) -- remove first occurrence of value.");
1184
1185 static int
valid_index(Py_ssize_t i,Py_ssize_t limit)1186 valid_index(Py_ssize_t i, Py_ssize_t limit)
1187 {
1188 /* The cast to size_t lets us use just a single comparison
1189 to check whether i is in the range: 0 <= i < limit */
1190 return (size_t) i < (size_t) limit;
1191 }
1192
1193 static PyObject *
deque_item(dequeobject * deque,Py_ssize_t i)1194 deque_item(dequeobject *deque, Py_ssize_t i)
1195 {
1196 block *b;
1197 PyObject *item;
1198 Py_ssize_t n, index=i;
1199
1200 if (!valid_index(i, Py_SIZE(deque))) {
1201 PyErr_SetString(PyExc_IndexError, "deque index out of range");
1202 return NULL;
1203 }
1204
1205 if (i == 0) {
1206 i = deque->leftindex;
1207 b = deque->leftblock;
1208 } else if (i == Py_SIZE(deque) - 1) {
1209 i = deque->rightindex;
1210 b = deque->rightblock;
1211 } else {
1212 i += deque->leftindex;
1213 n = (Py_ssize_t)((size_t) i / BLOCKLEN);
1214 i = (Py_ssize_t)((size_t) i % BLOCKLEN);
1215 if (index < (Py_SIZE(deque) >> 1)) {
1216 b = deque->leftblock;
1217 while (--n >= 0)
1218 b = b->rightlink;
1219 } else {
1220 n = (Py_ssize_t)(
1221 ((size_t)(deque->leftindex + Py_SIZE(deque) - 1))
1222 / BLOCKLEN - n);
1223 b = deque->rightblock;
1224 while (--n >= 0)
1225 b = b->leftlink;
1226 }
1227 }
1228 item = b->data[i];
1229 Py_INCREF(item);
1230 return item;
1231 }
1232
1233 static int
deque_del_item(dequeobject * deque,Py_ssize_t i)1234 deque_del_item(dequeobject *deque, Py_ssize_t i)
1235 {
1236 PyObject *item;
1237 int rv;
1238
1239 assert (i >= 0 && i < Py_SIZE(deque));
1240 if (_deque_rotate(deque, -i))
1241 return -1;
1242 item = deque_popleft(deque, NULL);
1243 rv = _deque_rotate(deque, i);
1244 assert (item != NULL);
1245 Py_DECREF(item);
1246 return rv;
1247 }
1248
1249 static int
deque_ass_item(dequeobject * deque,Py_ssize_t i,PyObject * v)1250 deque_ass_item(dequeobject *deque, Py_ssize_t i, PyObject *v)
1251 {
1252 PyObject *old_value;
1253 block *b;
1254 Py_ssize_t n, len=Py_SIZE(deque), halflen=(len+1)>>1, index=i;
1255
1256 if (!valid_index(i, len)) {
1257 PyErr_SetString(PyExc_IndexError, "deque index out of range");
1258 return -1;
1259 }
1260 if (v == NULL)
1261 return deque_del_item(deque, i);
1262
1263 i += deque->leftindex;
1264 n = (Py_ssize_t)((size_t) i / BLOCKLEN);
1265 i = (Py_ssize_t)((size_t) i % BLOCKLEN);
1266 if (index <= halflen) {
1267 b = deque->leftblock;
1268 while (--n >= 0)
1269 b = b->rightlink;
1270 } else {
1271 n = (Py_ssize_t)(
1272 ((size_t)(deque->leftindex + Py_SIZE(deque) - 1))
1273 / BLOCKLEN - n);
1274 b = deque->rightblock;
1275 while (--n >= 0)
1276 b = b->leftlink;
1277 }
1278 Py_INCREF(v);
1279 old_value = b->data[i];
1280 b->data[i] = v;
1281 Py_DECREF(old_value);
1282 return 0;
1283 }
1284
1285 static void
deque_dealloc(dequeobject * deque)1286 deque_dealloc(dequeobject *deque)
1287 {
1288 PyObject_GC_UnTrack(deque);
1289 if (deque->weakreflist != NULL)
1290 PyObject_ClearWeakRefs((PyObject *) deque);
1291 if (deque->leftblock != NULL) {
1292 deque_clear(deque);
1293 assert(deque->leftblock != NULL);
1294 freeblock(deque->leftblock);
1295 }
1296 deque->leftblock = NULL;
1297 deque->rightblock = NULL;
1298 Py_TYPE(deque)->tp_free(deque);
1299 }
1300
1301 static int
deque_traverse(dequeobject * deque,visitproc visit,void * arg)1302 deque_traverse(dequeobject *deque, visitproc visit, void *arg)
1303 {
1304 block *b;
1305 PyObject *item;
1306 Py_ssize_t index;
1307 Py_ssize_t indexlo = deque->leftindex;
1308 Py_ssize_t indexhigh;
1309
1310 for (b = deque->leftblock; b != deque->rightblock; b = b->rightlink) {
1311 for (index = indexlo; index < BLOCKLEN ; index++) {
1312 item = b->data[index];
1313 Py_VISIT(item);
1314 }
1315 indexlo = 0;
1316 }
1317 indexhigh = deque->rightindex;
1318 for (index = indexlo; index <= indexhigh; index++) {
1319 item = b->data[index];
1320 Py_VISIT(item);
1321 }
1322 return 0;
1323 }
1324
1325 static PyObject *
deque_reduce(dequeobject * deque,PyObject * Py_UNUSED (ignored))1326 deque_reduce(dequeobject *deque, PyObject *Py_UNUSED(ignored))
1327 {
1328 PyObject *dict, *it;
1329 _Py_IDENTIFIER(__dict__);
1330
1331 if (_PyObject_LookupAttrId((PyObject *)deque, &PyId___dict__, &dict) < 0) {
1332 return NULL;
1333 }
1334 if (dict == NULL) {
1335 dict = Py_None;
1336 Py_INCREF(dict);
1337 }
1338
1339 it = PyObject_GetIter((PyObject *)deque);
1340 if (it == NULL) {
1341 Py_DECREF(dict);
1342 return NULL;
1343 }
1344
1345 if (deque->maxlen < 0) {
1346 return Py_BuildValue("O()NN", Py_TYPE(deque), dict, it);
1347 }
1348 else {
1349 return Py_BuildValue("O(()n)NN", Py_TYPE(deque), deque->maxlen, dict, it);
1350 }
1351 }
1352
1353 PyDoc_STRVAR(reduce_doc, "Return state information for pickling.");
1354
1355 static PyObject *
deque_repr(PyObject * deque)1356 deque_repr(PyObject *deque)
1357 {
1358 PyObject *aslist, *result;
1359 int i;
1360
1361 i = Py_ReprEnter(deque);
1362 if (i != 0) {
1363 if (i < 0)
1364 return NULL;
1365 return PyUnicode_FromString("[...]");
1366 }
1367
1368 aslist = PySequence_List(deque);
1369 if (aslist == NULL) {
1370 Py_ReprLeave(deque);
1371 return NULL;
1372 }
1373 if (((dequeobject *)deque)->maxlen >= 0)
1374 result = PyUnicode_FromFormat("%s(%R, maxlen=%zd)",
1375 _PyType_Name(Py_TYPE(deque)), aslist,
1376 ((dequeobject *)deque)->maxlen);
1377 else
1378 result = PyUnicode_FromFormat("%s(%R)",
1379 _PyType_Name(Py_TYPE(deque)), aslist);
1380 Py_ReprLeave(deque);
1381 Py_DECREF(aslist);
1382 return result;
1383 }
1384
1385 static PyObject *
deque_richcompare(PyObject * v,PyObject * w,int op)1386 deque_richcompare(PyObject *v, PyObject *w, int op)
1387 {
1388 PyObject *it1=NULL, *it2=NULL, *x, *y;
1389 Py_ssize_t vs, ws;
1390 int b, cmp=-1;
1391
1392 if (!PyObject_TypeCheck(v, &deque_type) ||
1393 !PyObject_TypeCheck(w, &deque_type)) {
1394 Py_RETURN_NOTIMPLEMENTED;
1395 }
1396
1397 /* Shortcuts */
1398 vs = Py_SIZE((dequeobject *)v);
1399 ws = Py_SIZE((dequeobject *)w);
1400 if (op == Py_EQ) {
1401 if (v == w)
1402 Py_RETURN_TRUE;
1403 if (vs != ws)
1404 Py_RETURN_FALSE;
1405 }
1406 if (op == Py_NE) {
1407 if (v == w)
1408 Py_RETURN_FALSE;
1409 if (vs != ws)
1410 Py_RETURN_TRUE;
1411 }
1412
1413 /* Search for the first index where items are different */
1414 it1 = PyObject_GetIter(v);
1415 if (it1 == NULL)
1416 goto done;
1417 it2 = PyObject_GetIter(w);
1418 if (it2 == NULL)
1419 goto done;
1420 for (;;) {
1421 x = PyIter_Next(it1);
1422 if (x == NULL && PyErr_Occurred())
1423 goto done;
1424 y = PyIter_Next(it2);
1425 if (x == NULL || y == NULL)
1426 break;
1427 b = PyObject_RichCompareBool(x, y, Py_EQ);
1428 if (b == 0) {
1429 cmp = PyObject_RichCompareBool(x, y, op);
1430 Py_DECREF(x);
1431 Py_DECREF(y);
1432 goto done;
1433 }
1434 Py_DECREF(x);
1435 Py_DECREF(y);
1436 if (b < 0)
1437 goto done;
1438 }
1439 /* We reached the end of one deque or both */
1440 Py_XDECREF(x);
1441 Py_XDECREF(y);
1442 if (PyErr_Occurred())
1443 goto done;
1444 switch (op) {
1445 case Py_LT: cmp = y != NULL; break; /* if w was longer */
1446 case Py_LE: cmp = x == NULL; break; /* if v was not longer */
1447 case Py_EQ: cmp = x == y; break; /* if we reached the end of both */
1448 case Py_NE: cmp = x != y; break; /* if one deque continues */
1449 case Py_GT: cmp = x != NULL; break; /* if v was longer */
1450 case Py_GE: cmp = y == NULL; break; /* if w was not longer */
1451 }
1452
1453 done:
1454 Py_XDECREF(it1);
1455 Py_XDECREF(it2);
1456 if (cmp == 1)
1457 Py_RETURN_TRUE;
1458 if (cmp == 0)
1459 Py_RETURN_FALSE;
1460 return NULL;
1461 }
1462
1463 static int
deque_init(dequeobject * deque,PyObject * args,PyObject * kwdargs)1464 deque_init(dequeobject *deque, PyObject *args, PyObject *kwdargs)
1465 {
1466 PyObject *iterable = NULL;
1467 PyObject *maxlenobj = NULL;
1468 Py_ssize_t maxlen = -1;
1469 char *kwlist[] = {"iterable", "maxlen", 0};
1470
1471 if (kwdargs == NULL && PyTuple_GET_SIZE(args) <= 2) {
1472 if (PyTuple_GET_SIZE(args) > 0) {
1473 iterable = PyTuple_GET_ITEM(args, 0);
1474 }
1475 if (PyTuple_GET_SIZE(args) > 1) {
1476 maxlenobj = PyTuple_GET_ITEM(args, 1);
1477 }
1478 } else {
1479 if (!PyArg_ParseTupleAndKeywords(args, kwdargs, "|OO:deque", kwlist,
1480 &iterable, &maxlenobj))
1481 return -1;
1482 }
1483 if (maxlenobj != NULL && maxlenobj != Py_None) {
1484 maxlen = PyLong_AsSsize_t(maxlenobj);
1485 if (maxlen == -1 && PyErr_Occurred())
1486 return -1;
1487 if (maxlen < 0) {
1488 PyErr_SetString(PyExc_ValueError, "maxlen must be non-negative");
1489 return -1;
1490 }
1491 }
1492 deque->maxlen = maxlen;
1493 if (Py_SIZE(deque) > 0)
1494 deque_clear(deque);
1495 if (iterable != NULL) {
1496 PyObject *rv = deque_extend(deque, iterable);
1497 if (rv == NULL)
1498 return -1;
1499 Py_DECREF(rv);
1500 }
1501 return 0;
1502 }
1503
1504 static PyObject *
deque_sizeof(dequeobject * deque,void * unused)1505 deque_sizeof(dequeobject *deque, void *unused)
1506 {
1507 Py_ssize_t res;
1508 Py_ssize_t blocks;
1509
1510 res = _PyObject_SIZE(Py_TYPE(deque));
1511 blocks = (size_t)(deque->leftindex + Py_SIZE(deque) + BLOCKLEN - 1) / BLOCKLEN;
1512 assert(deque->leftindex + Py_SIZE(deque) - 1 ==
1513 (blocks - 1) * BLOCKLEN + deque->rightindex);
1514 res += blocks * sizeof(block);
1515 return PyLong_FromSsize_t(res);
1516 }
1517
1518 PyDoc_STRVAR(sizeof_doc,
1519 "D.__sizeof__() -- size of D in memory, in bytes");
1520
1521 static int
deque_bool(dequeobject * deque)1522 deque_bool(dequeobject *deque)
1523 {
1524 return Py_SIZE(deque) != 0;
1525 }
1526
1527 static PyObject *
deque_get_maxlen(dequeobject * deque,void * Py_UNUSED (ignored))1528 deque_get_maxlen(dequeobject *deque, void *Py_UNUSED(ignored))
1529 {
1530 if (deque->maxlen < 0)
1531 Py_RETURN_NONE;
1532 return PyLong_FromSsize_t(deque->maxlen);
1533 }
1534
1535
1536 /* deque object ********************************************************/
1537
1538 static PyGetSetDef deque_getset[] = {
1539 {"maxlen", (getter)deque_get_maxlen, (setter)NULL,
1540 "maximum size of a deque or None if unbounded"},
1541 {0}
1542 };
1543
1544 static PySequenceMethods deque_as_sequence = {
1545 (lenfunc)deque_len, /* sq_length */
1546 (binaryfunc)deque_concat, /* sq_concat */
1547 (ssizeargfunc)deque_repeat, /* sq_repeat */
1548 (ssizeargfunc)deque_item, /* sq_item */
1549 0, /* sq_slice */
1550 (ssizeobjargproc)deque_ass_item, /* sq_ass_item */
1551 0, /* sq_ass_slice */
1552 (objobjproc)deque_contains, /* sq_contains */
1553 (binaryfunc)deque_inplace_concat, /* sq_inplace_concat */
1554 (ssizeargfunc)deque_inplace_repeat, /* sq_inplace_repeat */
1555 };
1556
1557 static PyNumberMethods deque_as_number = {
1558 0, /* nb_add */
1559 0, /* nb_subtract */
1560 0, /* nb_multiply */
1561 0, /* nb_remainder */
1562 0, /* nb_divmod */
1563 0, /* nb_power */
1564 0, /* nb_negative */
1565 0, /* nb_positive */
1566 0, /* nb_absolute */
1567 (inquiry)deque_bool, /* nb_bool */
1568 0, /* nb_invert */
1569 };
1570
1571 static PyObject *deque_iter(dequeobject *deque);
1572 static PyObject *deque_reviter(dequeobject *deque, PyObject *Py_UNUSED(ignored));
1573 PyDoc_STRVAR(reversed_doc,
1574 "D.__reversed__() -- return a reverse iterator over the deque");
1575
1576 static PyMethodDef deque_methods[] = {
1577 {"append", (PyCFunction)deque_append,
1578 METH_O, append_doc},
1579 {"appendleft", (PyCFunction)deque_appendleft,
1580 METH_O, appendleft_doc},
1581 {"clear", (PyCFunction)deque_clearmethod,
1582 METH_NOARGS, clear_doc},
1583 {"__copy__", deque_copy,
1584 METH_NOARGS, copy_doc},
1585 {"copy", deque_copy,
1586 METH_NOARGS, copy_doc},
1587 {"count", (PyCFunction)deque_count,
1588 METH_O, count_doc},
1589 {"extend", (PyCFunction)deque_extend,
1590 METH_O, extend_doc},
1591 {"extendleft", (PyCFunction)deque_extendleft,
1592 METH_O, extendleft_doc},
1593 {"index", (PyCFunction)(void(*)(void))deque_index,
1594 METH_FASTCALL, index_doc},
1595 {"insert", (PyCFunction)(void(*)(void))deque_insert,
1596 METH_FASTCALL, insert_doc},
1597 {"pop", (PyCFunction)deque_pop,
1598 METH_NOARGS, pop_doc},
1599 {"popleft", (PyCFunction)deque_popleft,
1600 METH_NOARGS, popleft_doc},
1601 {"__reduce__", (PyCFunction)deque_reduce,
1602 METH_NOARGS, reduce_doc},
1603 {"remove", (PyCFunction)deque_remove,
1604 METH_O, remove_doc},
1605 {"__reversed__", (PyCFunction)deque_reviter,
1606 METH_NOARGS, reversed_doc},
1607 {"reverse", (PyCFunction)deque_reverse,
1608 METH_NOARGS, reverse_doc},
1609 {"rotate", (PyCFunction)(void(*)(void))deque_rotate,
1610 METH_FASTCALL, rotate_doc},
1611 {"__sizeof__", (PyCFunction)deque_sizeof,
1612 METH_NOARGS, sizeof_doc},
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 &deque_as_number, /* 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 | Py_TPFLAGS_HAVE_GC,
1643 /* tp_flags */
1644 deque_doc, /* tp_doc */
1645 (traverseproc)deque_traverse, /* tp_traverse */
1646 (inquiry)deque_clear, /* tp_clear */
1647 (richcmpfunc)deque_richcompare, /* tp_richcompare */
1648 offsetof(dequeobject, weakreflist), /* tp_weaklistoffset*/
1649 (getiterfunc)deque_iter, /* tp_iter */
1650 0, /* tp_iternext */
1651 deque_methods, /* tp_methods */
1652 0, /* tp_members */
1653 deque_getset, /* tp_getset */
1654 0, /* tp_base */
1655 0, /* tp_dict */
1656 0, /* tp_descr_get */
1657 0, /* tp_descr_set */
1658 0, /* tp_dictoffset */
1659 (initproc)deque_init, /* tp_init */
1660 PyType_GenericAlloc, /* tp_alloc */
1661 deque_new, /* tp_new */
1662 PyObject_GC_Del, /* tp_free */
1663 };
1664
1665 /*********************** Deque Iterator **************************/
1666
1667 typedef struct {
1668 PyObject_HEAD
1669 block *b;
1670 Py_ssize_t index;
1671 dequeobject *deque;
1672 size_t state; /* state when the iterator is created */
1673 Py_ssize_t counter; /* number of items remaining for iteration */
1674 } dequeiterobject;
1675
1676 static PyTypeObject dequeiter_type;
1677
1678 static PyObject *
deque_iter(dequeobject * deque)1679 deque_iter(dequeobject *deque)
1680 {
1681 dequeiterobject *it;
1682
1683 it = PyObject_GC_New(dequeiterobject, &dequeiter_type);
1684 if (it == NULL)
1685 return NULL;
1686 it->b = deque->leftblock;
1687 it->index = deque->leftindex;
1688 Py_INCREF(deque);
1689 it->deque = deque;
1690 it->state = deque->state;
1691 it->counter = Py_SIZE(deque);
1692 PyObject_GC_Track(it);
1693 return (PyObject *)it;
1694 }
1695
1696 static int
dequeiter_traverse(dequeiterobject * dio,visitproc visit,void * arg)1697 dequeiter_traverse(dequeiterobject *dio, visitproc visit, void *arg)
1698 {
1699 Py_VISIT(dio->deque);
1700 return 0;
1701 }
1702
1703 static void
dequeiter_dealloc(dequeiterobject * dio)1704 dequeiter_dealloc(dequeiterobject *dio)
1705 {
1706 /* bpo-31095: UnTrack is needed before calling any callbacks */
1707 PyObject_GC_UnTrack(dio);
1708 Py_XDECREF(dio->deque);
1709 PyObject_GC_Del(dio);
1710 }
1711
1712 static PyObject *
dequeiter_next(dequeiterobject * it)1713 dequeiter_next(dequeiterobject *it)
1714 {
1715 PyObject *item;
1716
1717 if (it->deque->state != it->state) {
1718 it->counter = 0;
1719 PyErr_SetString(PyExc_RuntimeError,
1720 "deque mutated during iteration");
1721 return NULL;
1722 }
1723 if (it->counter == 0)
1724 return NULL;
1725 assert (!(it->b == it->deque->rightblock &&
1726 it->index > it->deque->rightindex));
1727
1728 item = it->b->data[it->index];
1729 it->index++;
1730 it->counter--;
1731 if (it->index == BLOCKLEN && it->counter > 0) {
1732 CHECK_NOT_END(it->b->rightlink);
1733 it->b = it->b->rightlink;
1734 it->index = 0;
1735 }
1736 Py_INCREF(item);
1737 return item;
1738 }
1739
1740 static PyObject *
dequeiter_new(PyTypeObject * type,PyObject * args,PyObject * kwds)1741 dequeiter_new(PyTypeObject *type, PyObject *args, PyObject *kwds)
1742 {
1743 Py_ssize_t i, index=0;
1744 PyObject *deque;
1745 dequeiterobject *it;
1746 if (!PyArg_ParseTuple(args, "O!|n", &deque_type, &deque, &index))
1747 return NULL;
1748 assert(type == &dequeiter_type);
1749
1750 it = (dequeiterobject*)deque_iter((dequeobject *)deque);
1751 if (!it)
1752 return NULL;
1753 /* consume items from the queue */
1754 for(i=0; i<index; i++) {
1755 PyObject *item = dequeiter_next(it);
1756 if (item) {
1757 Py_DECREF(item);
1758 } else {
1759 if (it->counter) {
1760 Py_DECREF(it);
1761 return NULL;
1762 } else
1763 break;
1764 }
1765 }
1766 return (PyObject*)it;
1767 }
1768
1769 static PyObject *
dequeiter_len(dequeiterobject * it,PyObject * Py_UNUSED (ignored))1770 dequeiter_len(dequeiterobject *it, PyObject *Py_UNUSED(ignored))
1771 {
1772 return PyLong_FromSsize_t(it->counter);
1773 }
1774
1775 PyDoc_STRVAR(length_hint_doc, "Private method returning an estimate of len(list(it)).");
1776
1777 static PyObject *
dequeiter_reduce(dequeiterobject * it,PyObject * Py_UNUSED (ignored))1778 dequeiter_reduce(dequeiterobject *it, PyObject *Py_UNUSED(ignored))
1779 {
1780 return Py_BuildValue("O(On)", Py_TYPE(it), it->deque, Py_SIZE(it->deque) - it->counter);
1781 }
1782
1783 static PyMethodDef dequeiter_methods[] = {
1784 {"__length_hint__", (PyCFunction)dequeiter_len, METH_NOARGS, length_hint_doc},
1785 {"__reduce__", (PyCFunction)dequeiter_reduce, METH_NOARGS, reduce_doc},
1786 {NULL, NULL} /* sentinel */
1787 };
1788
1789 static PyTypeObject dequeiter_type = {
1790 PyVarObject_HEAD_INIT(NULL, 0)
1791 "_collections._deque_iterator", /* tp_name */
1792 sizeof(dequeiterobject), /* tp_basicsize */
1793 0, /* tp_itemsize */
1794 /* methods */
1795 (destructor)dequeiter_dealloc, /* tp_dealloc */
1796 0, /* tp_vectorcall_offset */
1797 0, /* tp_getattr */
1798 0, /* tp_setattr */
1799 0, /* tp_as_async */
1800 0, /* tp_repr */
1801 0, /* tp_as_number */
1802 0, /* tp_as_sequence */
1803 0, /* tp_as_mapping */
1804 0, /* tp_hash */
1805 0, /* tp_call */
1806 0, /* tp_str */
1807 PyObject_GenericGetAttr, /* tp_getattro */
1808 0, /* tp_setattro */
1809 0, /* tp_as_buffer */
1810 Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC, /* tp_flags */
1811 0, /* tp_doc */
1812 (traverseproc)dequeiter_traverse, /* tp_traverse */
1813 0, /* tp_clear */
1814 0, /* tp_richcompare */
1815 0, /* tp_weaklistoffset */
1816 PyObject_SelfIter, /* tp_iter */
1817 (iternextfunc)dequeiter_next, /* tp_iternext */
1818 dequeiter_methods, /* tp_methods */
1819 0, /* tp_members */
1820 0, /* tp_getset */
1821 0, /* tp_base */
1822 0, /* tp_dict */
1823 0, /* tp_descr_get */
1824 0, /* tp_descr_set */
1825 0, /* tp_dictoffset */
1826 0, /* tp_init */
1827 0, /* tp_alloc */
1828 dequeiter_new, /* tp_new */
1829 0,
1830 };
1831
1832 /*********************** Deque Reverse Iterator **************************/
1833
1834 static PyTypeObject dequereviter_type;
1835
1836 static PyObject *
deque_reviter(dequeobject * deque,PyObject * Py_UNUSED (ignored))1837 deque_reviter(dequeobject *deque, PyObject *Py_UNUSED(ignored))
1838 {
1839 dequeiterobject *it;
1840
1841 it = PyObject_GC_New(dequeiterobject, &dequereviter_type);
1842 if (it == NULL)
1843 return NULL;
1844 it->b = deque->rightblock;
1845 it->index = deque->rightindex;
1846 Py_INCREF(deque);
1847 it->deque = deque;
1848 it->state = deque->state;
1849 it->counter = Py_SIZE(deque);
1850 PyObject_GC_Track(it);
1851 return (PyObject *)it;
1852 }
1853
1854 static PyObject *
dequereviter_next(dequeiterobject * it)1855 dequereviter_next(dequeiterobject *it)
1856 {
1857 PyObject *item;
1858 if (it->counter == 0)
1859 return NULL;
1860
1861 if (it->deque->state != it->state) {
1862 it->counter = 0;
1863 PyErr_SetString(PyExc_RuntimeError,
1864 "deque mutated during iteration");
1865 return NULL;
1866 }
1867 assert (!(it->b == it->deque->leftblock &&
1868 it->index < it->deque->leftindex));
1869
1870 item = it->b->data[it->index];
1871 it->index--;
1872 it->counter--;
1873 if (it->index < 0 && it->counter > 0) {
1874 CHECK_NOT_END(it->b->leftlink);
1875 it->b = it->b->leftlink;
1876 it->index = BLOCKLEN - 1;
1877 }
1878 Py_INCREF(item);
1879 return item;
1880 }
1881
1882 static PyObject *
dequereviter_new(PyTypeObject * type,PyObject * args,PyObject * kwds)1883 dequereviter_new(PyTypeObject *type, PyObject *args, PyObject *kwds)
1884 {
1885 Py_ssize_t i, index=0;
1886 PyObject *deque;
1887 dequeiterobject *it;
1888 if (!PyArg_ParseTuple(args, "O!|n", &deque_type, &deque, &index))
1889 return NULL;
1890 assert(type == &dequereviter_type);
1891
1892 it = (dequeiterobject*)deque_reviter((dequeobject *)deque, NULL);
1893 if (!it)
1894 return NULL;
1895 /* consume items from the queue */
1896 for(i=0; i<index; i++) {
1897 PyObject *item = dequereviter_next(it);
1898 if (item) {
1899 Py_DECREF(item);
1900 } else {
1901 if (it->counter) {
1902 Py_DECREF(it);
1903 return NULL;
1904 } else
1905 break;
1906 }
1907 }
1908 return (PyObject*)it;
1909 }
1910
1911 static PyTypeObject dequereviter_type = {
1912 PyVarObject_HEAD_INIT(NULL, 0)
1913 "_collections._deque_reverse_iterator", /* tp_name */
1914 sizeof(dequeiterobject), /* tp_basicsize */
1915 0, /* tp_itemsize */
1916 /* methods */
1917 (destructor)dequeiter_dealloc, /* tp_dealloc */
1918 0, /* tp_vectorcall_offset */
1919 0, /* tp_getattr */
1920 0, /* tp_setattr */
1921 0, /* tp_as_async */
1922 0, /* tp_repr */
1923 0, /* tp_as_number */
1924 0, /* tp_as_sequence */
1925 0, /* tp_as_mapping */
1926 0, /* tp_hash */
1927 0, /* tp_call */
1928 0, /* tp_str */
1929 PyObject_GenericGetAttr, /* tp_getattro */
1930 0, /* tp_setattro */
1931 0, /* tp_as_buffer */
1932 Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC, /* tp_flags */
1933 0, /* tp_doc */
1934 (traverseproc)dequeiter_traverse, /* tp_traverse */
1935 0, /* tp_clear */
1936 0, /* tp_richcompare */
1937 0, /* tp_weaklistoffset */
1938 PyObject_SelfIter, /* tp_iter */
1939 (iternextfunc)dequereviter_next, /* tp_iternext */
1940 dequeiter_methods, /* tp_methods */
1941 0, /* tp_members */
1942 0, /* tp_getset */
1943 0, /* tp_base */
1944 0, /* tp_dict */
1945 0, /* tp_descr_get */
1946 0, /* tp_descr_set */
1947 0, /* tp_dictoffset */
1948 0, /* tp_init */
1949 0, /* tp_alloc */
1950 dequereviter_new, /* tp_new */
1951 0,
1952 };
1953
1954 /* defaultdict type *********************************************************/
1955
1956 typedef struct {
1957 PyDictObject dict;
1958 PyObject *default_factory;
1959 } defdictobject;
1960
1961 static PyTypeObject defdict_type; /* Forward */
1962
1963 PyDoc_STRVAR(defdict_missing_doc,
1964 "__missing__(key) # Called by __getitem__ for missing key; pseudo-code:\n\
1965 if self.default_factory is None: raise KeyError((key,))\n\
1966 self[key] = value = self.default_factory()\n\
1967 return value\n\
1968 ");
1969
1970 static PyObject *
defdict_missing(defdictobject * dd,PyObject * key)1971 defdict_missing(defdictobject *dd, PyObject *key)
1972 {
1973 PyObject *factory = dd->default_factory;
1974 PyObject *value;
1975 if (factory == NULL || factory == Py_None) {
1976 /* XXX Call dict.__missing__(key) */
1977 PyObject *tup;
1978 tup = PyTuple_Pack(1, key);
1979 if (!tup) return NULL;
1980 PyErr_SetObject(PyExc_KeyError, tup);
1981 Py_DECREF(tup);
1982 return NULL;
1983 }
1984 value = PyEval_CallObject(factory, NULL);
1985 if (value == NULL)
1986 return value;
1987 if (PyObject_SetItem((PyObject *)dd, key, value) < 0) {
1988 Py_DECREF(value);
1989 return NULL;
1990 }
1991 return value;
1992 }
1993
1994 PyDoc_STRVAR(defdict_copy_doc, "D.copy() -> a shallow copy of D.");
1995
1996 static PyObject *
defdict_copy(defdictobject * dd,PyObject * Py_UNUSED (ignored))1997 defdict_copy(defdictobject *dd, PyObject *Py_UNUSED(ignored))
1998 {
1999 /* This calls the object's class. That only works for subclasses
2000 whose class constructor has the same signature. Subclasses that
2001 define a different constructor signature must override copy().
2002 */
2003
2004 if (dd->default_factory == NULL)
2005 return PyObject_CallFunctionObjArgs((PyObject*)Py_TYPE(dd), Py_None, dd, NULL);
2006 return PyObject_CallFunctionObjArgs((PyObject*)Py_TYPE(dd),
2007 dd->default_factory, dd, NULL);
2008 }
2009
2010 static PyObject *
defdict_reduce(defdictobject * dd,PyObject * Py_UNUSED (ignored))2011 defdict_reduce(defdictobject *dd, PyObject *Py_UNUSED(ignored))
2012 {
2013 /* __reduce__ must return a 5-tuple as follows:
2014
2015 - factory function
2016 - tuple of args for the factory function
2017 - additional state (here None)
2018 - sequence iterator (here None)
2019 - dictionary iterator (yielding successive (key, value) pairs
2020
2021 This API is used by pickle.py and copy.py.
2022
2023 For this to be useful with pickle.py, the default_factory
2024 must be picklable; e.g., None, a built-in, or a global
2025 function in a module or package.
2026
2027 Both shallow and deep copying are supported, but for deep
2028 copying, the default_factory must be deep-copyable; e.g. None,
2029 or a built-in (functions are not copyable at this time).
2030
2031 This only works for subclasses as long as their constructor
2032 signature is compatible; the first argument must be the
2033 optional default_factory, defaulting to None.
2034 */
2035 PyObject *args;
2036 PyObject *items;
2037 PyObject *iter;
2038 PyObject *result;
2039 _Py_IDENTIFIER(items);
2040
2041 if (dd->default_factory == NULL || dd->default_factory == Py_None)
2042 args = PyTuple_New(0);
2043 else
2044 args = PyTuple_Pack(1, dd->default_factory);
2045 if (args == NULL)
2046 return NULL;
2047 items = _PyObject_CallMethodId((PyObject *)dd, &PyId_items, NULL);
2048 if (items == NULL) {
2049 Py_DECREF(args);
2050 return NULL;
2051 }
2052 iter = PyObject_GetIter(items);
2053 if (iter == NULL) {
2054 Py_DECREF(items);
2055 Py_DECREF(args);
2056 return NULL;
2057 }
2058 result = PyTuple_Pack(5, Py_TYPE(dd), args,
2059 Py_None, Py_None, iter);
2060 Py_DECREF(iter);
2061 Py_DECREF(items);
2062 Py_DECREF(args);
2063 return result;
2064 }
2065
2066 static PyMethodDef defdict_methods[] = {
2067 {"__missing__", (PyCFunction)defdict_missing, METH_O,
2068 defdict_missing_doc},
2069 {"copy", (PyCFunction)defdict_copy, METH_NOARGS,
2070 defdict_copy_doc},
2071 {"__copy__", (PyCFunction)defdict_copy, METH_NOARGS,
2072 defdict_copy_doc},
2073 {"__reduce__", (PyCFunction)defdict_reduce, METH_NOARGS,
2074 reduce_doc},
2075 {NULL}
2076 };
2077
2078 static PyMemberDef defdict_members[] = {
2079 {"default_factory", T_OBJECT,
2080 offsetof(defdictobject, default_factory), 0,
2081 PyDoc_STR("Factory for default value called by __missing__().")},
2082 {NULL}
2083 };
2084
2085 static void
defdict_dealloc(defdictobject * dd)2086 defdict_dealloc(defdictobject *dd)
2087 {
2088 /* bpo-31095: UnTrack is needed before calling any callbacks */
2089 PyObject_GC_UnTrack(dd);
2090 Py_CLEAR(dd->default_factory);
2091 PyDict_Type.tp_dealloc((PyObject *)dd);
2092 }
2093
2094 static PyObject *
defdict_repr(defdictobject * dd)2095 defdict_repr(defdictobject *dd)
2096 {
2097 PyObject *baserepr;
2098 PyObject *defrepr;
2099 PyObject *result;
2100 baserepr = PyDict_Type.tp_repr((PyObject *)dd);
2101 if (baserepr == NULL)
2102 return NULL;
2103 if (dd->default_factory == NULL)
2104 defrepr = PyUnicode_FromString("None");
2105 else
2106 {
2107 int status = Py_ReprEnter(dd->default_factory);
2108 if (status != 0) {
2109 if (status < 0) {
2110 Py_DECREF(baserepr);
2111 return NULL;
2112 }
2113 defrepr = PyUnicode_FromString("...");
2114 }
2115 else
2116 defrepr = PyObject_Repr(dd->default_factory);
2117 Py_ReprLeave(dd->default_factory);
2118 }
2119 if (defrepr == NULL) {
2120 Py_DECREF(baserepr);
2121 return NULL;
2122 }
2123 result = PyUnicode_FromFormat("%s(%U, %U)",
2124 _PyType_Name(Py_TYPE(dd)),
2125 defrepr, baserepr);
2126 Py_DECREF(defrepr);
2127 Py_DECREF(baserepr);
2128 return result;
2129 }
2130
2131 static int
defdict_traverse(PyObject * self,visitproc visit,void * arg)2132 defdict_traverse(PyObject *self, visitproc visit, void *arg)
2133 {
2134 Py_VISIT(((defdictobject *)self)->default_factory);
2135 return PyDict_Type.tp_traverse(self, visit, arg);
2136 }
2137
2138 static int
defdict_tp_clear(defdictobject * dd)2139 defdict_tp_clear(defdictobject *dd)
2140 {
2141 Py_CLEAR(dd->default_factory);
2142 return PyDict_Type.tp_clear((PyObject *)dd);
2143 }
2144
2145 static int
defdict_init(PyObject * self,PyObject * args,PyObject * kwds)2146 defdict_init(PyObject *self, PyObject *args, PyObject *kwds)
2147 {
2148 defdictobject *dd = (defdictobject *)self;
2149 PyObject *olddefault = dd->default_factory;
2150 PyObject *newdefault = NULL;
2151 PyObject *newargs;
2152 int result;
2153 if (args == NULL || !PyTuple_Check(args))
2154 newargs = PyTuple_New(0);
2155 else {
2156 Py_ssize_t n = PyTuple_GET_SIZE(args);
2157 if (n > 0) {
2158 newdefault = PyTuple_GET_ITEM(args, 0);
2159 if (!PyCallable_Check(newdefault) && newdefault != Py_None) {
2160 PyErr_SetString(PyExc_TypeError,
2161 "first argument must be callable or None");
2162 return -1;
2163 }
2164 }
2165 newargs = PySequence_GetSlice(args, 1, n);
2166 }
2167 if (newargs == NULL)
2168 return -1;
2169 Py_XINCREF(newdefault);
2170 dd->default_factory = newdefault;
2171 result = PyDict_Type.tp_init(self, newargs, kwds);
2172 Py_DECREF(newargs);
2173 Py_XDECREF(olddefault);
2174 return result;
2175 }
2176
2177 PyDoc_STRVAR(defdict_doc,
2178 "defaultdict(default_factory[, ...]) --> dict with default factory\n\
2179 \n\
2180 The default factory is called without arguments to produce\n\
2181 a new value when a key is not present, in __getitem__ only.\n\
2182 A defaultdict compares equal to a dict with the same items.\n\
2183 All remaining arguments are treated the same as if they were\n\
2184 passed to the dict constructor, including keyword arguments.\n\
2185 ");
2186
2187 /* See comment in xxsubtype.c */
2188 #define DEFERRED_ADDRESS(ADDR) 0
2189
2190 static PyTypeObject defdict_type = {
2191 PyVarObject_HEAD_INIT(DEFERRED_ADDRESS(&PyType_Type), 0)
2192 "collections.defaultdict", /* tp_name */
2193 sizeof(defdictobject), /* tp_basicsize */
2194 0, /* tp_itemsize */
2195 /* methods */
2196 (destructor)defdict_dealloc, /* tp_dealloc */
2197 0, /* tp_vectorcall_offset */
2198 0, /* tp_getattr */
2199 0, /* tp_setattr */
2200 0, /* tp_as_async */
2201 (reprfunc)defdict_repr, /* tp_repr */
2202 0, /* tp_as_number */
2203 0, /* tp_as_sequence */
2204 0, /* tp_as_mapping */
2205 0, /* tp_hash */
2206 0, /* tp_call */
2207 0, /* tp_str */
2208 PyObject_GenericGetAttr, /* tp_getattro */
2209 0, /* tp_setattro */
2210 0, /* tp_as_buffer */
2211 Py_TPFLAGS_DEFAULT | Py_TPFLAGS_BASETYPE | Py_TPFLAGS_HAVE_GC,
2212 /* tp_flags */
2213 defdict_doc, /* tp_doc */
2214 defdict_traverse, /* tp_traverse */
2215 (inquiry)defdict_tp_clear, /* tp_clear */
2216 0, /* tp_richcompare */
2217 0, /* tp_weaklistoffset*/
2218 0, /* tp_iter */
2219 0, /* tp_iternext */
2220 defdict_methods, /* tp_methods */
2221 defdict_members, /* tp_members */
2222 0, /* tp_getset */
2223 DEFERRED_ADDRESS(&PyDict_Type), /* tp_base */
2224 0, /* tp_dict */
2225 0, /* tp_descr_get */
2226 0, /* tp_descr_set */
2227 0, /* tp_dictoffset */
2228 defdict_init, /* tp_init */
2229 PyType_GenericAlloc, /* tp_alloc */
2230 0, /* tp_new */
2231 PyObject_GC_Del, /* tp_free */
2232 };
2233
2234 /* helper function for Counter *********************************************/
2235
2236 /*[clinic input]
2237 _collections._count_elements
2238
2239 mapping: object
2240 iterable: object
2241 /
2242
2243 Count elements in the iterable, updating the mapping
2244 [clinic start generated code]*/
2245
2246 static PyObject *
_collections__count_elements_impl(PyObject * module,PyObject * mapping,PyObject * iterable)2247 _collections__count_elements_impl(PyObject *module, PyObject *mapping,
2248 PyObject *iterable)
2249 /*[clinic end generated code: output=7e0c1789636b3d8f input=e79fad04534a0b45]*/
2250 {
2251 _Py_IDENTIFIER(get);
2252 _Py_IDENTIFIER(__setitem__);
2253 PyObject *it, *oldval;
2254 PyObject *newval = NULL;
2255 PyObject *key = NULL;
2256 PyObject *bound_get = NULL;
2257 PyObject *mapping_get;
2258 PyObject *dict_get;
2259 PyObject *mapping_setitem;
2260 PyObject *dict_setitem;
2261
2262 it = PyObject_GetIter(iterable);
2263 if (it == NULL)
2264 return NULL;
2265
2266 /* Only take the fast path when get() and __setitem__()
2267 * have not been overridden.
2268 */
2269 mapping_get = _PyType_LookupId(Py_TYPE(mapping), &PyId_get);
2270 dict_get = _PyType_LookupId(&PyDict_Type, &PyId_get);
2271 mapping_setitem = _PyType_LookupId(Py_TYPE(mapping), &PyId___setitem__);
2272 dict_setitem = _PyType_LookupId(&PyDict_Type, &PyId___setitem__);
2273
2274 if (mapping_get != NULL && mapping_get == dict_get &&
2275 mapping_setitem != NULL && mapping_setitem == dict_setitem &&
2276 PyDict_Check(mapping))
2277 {
2278 while (1) {
2279 /* Fast path advantages:
2280 1. Eliminate double hashing
2281 (by re-using the same hash for both the get and set)
2282 2. Avoid argument overhead of PyObject_CallFunctionObjArgs
2283 (argument tuple creation and parsing)
2284 3. Avoid indirection through a bound method object
2285 (creates another argument tuple)
2286 4. Avoid initial increment from zero
2287 (reuse an existing one-object instead)
2288 */
2289 Py_hash_t hash;
2290
2291 key = PyIter_Next(it);
2292 if (key == NULL)
2293 break;
2294
2295 if (!PyUnicode_CheckExact(key) ||
2296 (hash = ((PyASCIIObject *) key)->hash) == -1)
2297 {
2298 hash = PyObject_Hash(key);
2299 if (hash == -1)
2300 goto done;
2301 }
2302
2303 oldval = _PyDict_GetItem_KnownHash(mapping, key, hash);
2304 if (oldval == NULL) {
2305 if (PyErr_Occurred())
2306 goto done;
2307 if (_PyDict_SetItem_KnownHash(mapping, key, _PyLong_One, hash) < 0)
2308 goto done;
2309 } else {
2310 newval = PyNumber_Add(oldval, _PyLong_One);
2311 if (newval == NULL)
2312 goto done;
2313 if (_PyDict_SetItem_KnownHash(mapping, key, newval, hash) < 0)
2314 goto done;
2315 Py_CLEAR(newval);
2316 }
2317 Py_DECREF(key);
2318 }
2319 } else {
2320 bound_get = _PyObject_GetAttrId(mapping, &PyId_get);
2321 if (bound_get == NULL)
2322 goto done;
2323
2324 while (1) {
2325 key = PyIter_Next(it);
2326 if (key == NULL)
2327 break;
2328 oldval = PyObject_CallFunctionObjArgs(bound_get, key, _PyLong_Zero, NULL);
2329 if (oldval == NULL)
2330 break;
2331 newval = PyNumber_Add(oldval, _PyLong_One);
2332 Py_DECREF(oldval);
2333 if (newval == NULL)
2334 break;
2335 if (PyObject_SetItem(mapping, key, newval) < 0)
2336 break;
2337 Py_CLEAR(newval);
2338 Py_DECREF(key);
2339 }
2340 }
2341
2342 done:
2343 Py_DECREF(it);
2344 Py_XDECREF(key);
2345 Py_XDECREF(newval);
2346 Py_XDECREF(bound_get);
2347 if (PyErr_Occurred())
2348 return NULL;
2349 Py_RETURN_NONE;
2350 }
2351
2352 /* Helper function for namedtuple() ************************************/
2353
2354 typedef struct {
2355 PyObject_HEAD
2356 Py_ssize_t index;
2357 PyObject* doc;
2358 } _tuplegetterobject;
2359
2360 /*[clinic input]
2361 @classmethod
2362 _tuplegetter.__new__ as tuplegetter_new
2363
2364 index: Py_ssize_t
2365 doc: object
2366 /
2367 [clinic start generated code]*/
2368
2369 static PyObject *
tuplegetter_new_impl(PyTypeObject * type,Py_ssize_t index,PyObject * doc)2370 tuplegetter_new_impl(PyTypeObject *type, Py_ssize_t index, PyObject *doc)
2371 /*[clinic end generated code: output=014be444ad80263f input=87c576a5bdbc0bbb]*/
2372 {
2373 _tuplegetterobject* self;
2374 self = (_tuplegetterobject *)type->tp_alloc(type, 0);
2375 if (self == NULL) {
2376 return NULL;
2377 }
2378 self->index = index;
2379 Py_INCREF(doc);
2380 self->doc = doc;
2381 return (PyObject *)self;
2382 }
2383
2384 static PyObject *
tuplegetter_descr_get(PyObject * self,PyObject * obj,PyObject * type)2385 tuplegetter_descr_get(PyObject *self, PyObject *obj, PyObject *type)
2386 {
2387 Py_ssize_t index = ((_tuplegetterobject*)self)->index;
2388 PyObject *result;
2389
2390 if (obj == NULL) {
2391 Py_INCREF(self);
2392 return self;
2393 }
2394 if (!PyTuple_Check(obj)) {
2395 if (obj == Py_None) {
2396 Py_INCREF(self);
2397 return self;
2398 }
2399 PyErr_Format(PyExc_TypeError,
2400 "descriptor for index '%zd' for tuple subclasses "
2401 "doesn't apply to '%s' object",
2402 index,
2403 obj->ob_type->tp_name);
2404 return NULL;
2405 }
2406
2407 if (!valid_index(index, PyTuple_GET_SIZE(obj))) {
2408 PyErr_SetString(PyExc_IndexError, "tuple index out of range");
2409 return NULL;
2410 }
2411
2412 result = PyTuple_GET_ITEM(obj, index);
2413 Py_INCREF(result);
2414 return result;
2415 }
2416
2417 static int
tuplegetter_descr_set(PyObject * self,PyObject * obj,PyObject * value)2418 tuplegetter_descr_set(PyObject *self, PyObject *obj, PyObject *value)
2419 {
2420 if (value == NULL) {
2421 PyErr_SetString(PyExc_AttributeError, "can't delete attribute");
2422 } else {
2423 PyErr_SetString(PyExc_AttributeError, "can't set attribute");
2424 }
2425 return -1;
2426 }
2427
2428 static int
tuplegetter_traverse(PyObject * self,visitproc visit,void * arg)2429 tuplegetter_traverse(PyObject *self, visitproc visit, void *arg)
2430 {
2431 _tuplegetterobject *tuplegetter = (_tuplegetterobject *)self;
2432 Py_VISIT(tuplegetter->doc);
2433 return 0;
2434 }
2435
2436 static int
tuplegetter_clear(PyObject * self)2437 tuplegetter_clear(PyObject *self)
2438 {
2439 _tuplegetterobject *tuplegetter = (_tuplegetterobject *)self;
2440 Py_CLEAR(tuplegetter->doc);
2441 return 0;
2442 }
2443
2444 static void
tuplegetter_dealloc(_tuplegetterobject * self)2445 tuplegetter_dealloc(_tuplegetterobject *self)
2446 {
2447 PyObject_GC_UnTrack(self);
2448 tuplegetter_clear((PyObject*)self);
2449 Py_TYPE(self)->tp_free((PyObject*)self);
2450 }
2451
2452 static PyObject*
tuplegetter_reduce(_tuplegetterobject * self,PyObject * Py_UNUSED (ignored))2453 tuplegetter_reduce(_tuplegetterobject *self, PyObject *Py_UNUSED(ignored))
2454 {
2455 return Py_BuildValue("(O(nO))", (PyObject*) Py_TYPE(self), self->index, self->doc);
2456 }
2457
2458
2459 static PyMemberDef tuplegetter_members[] = {
2460 {"__doc__", T_OBJECT, offsetof(_tuplegetterobject, doc), 0},
2461 {0}
2462 };
2463
2464 static PyMethodDef tuplegetter_methods[] = {
2465 {"__reduce__", (PyCFunction)tuplegetter_reduce, METH_NOARGS, NULL},
2466 {NULL},
2467 };
2468
2469 static PyTypeObject tuplegetter_type = {
2470 PyVarObject_HEAD_INIT(NULL, 0)
2471 "_collections._tuplegetter", /* tp_name */
2472 sizeof(_tuplegetterobject), /* tp_basicsize */
2473 0, /* tp_itemsize */
2474 /* methods */
2475 (destructor)tuplegetter_dealloc, /* tp_dealloc */
2476 0, /* tp_vectorcall_offset */
2477 0, /* tp_getattr */
2478 0, /* tp_setattr */
2479 0, /* tp_as_async */
2480 0, /* tp_repr */
2481 0, /* tp_as_number */
2482 0, /* tp_as_sequence */
2483 0, /* tp_as_mapping */
2484 0, /* tp_hash */
2485 0, /* tp_call */
2486 0, /* tp_str */
2487 0, /* tp_getattro */
2488 0, /* tp_setattro */
2489 0, /* tp_as_buffer */
2490 Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC, /* tp_flags */
2491 0, /* tp_doc */
2492 (traverseproc)tuplegetter_traverse, /* tp_traverse */
2493 (inquiry)tuplegetter_clear, /* tp_clear */
2494 0, /* tp_richcompare */
2495 0, /* tp_weaklistoffset */
2496 0, /* tp_iter */
2497 0, /* tp_iternext */
2498 tuplegetter_methods, /* tp_methods */
2499 tuplegetter_members, /* tp_members */
2500 0, /* tp_getset */
2501 0, /* tp_base */
2502 0, /* tp_dict */
2503 tuplegetter_descr_get, /* tp_descr_get */
2504 tuplegetter_descr_set, /* tp_descr_set */
2505 0, /* tp_dictoffset */
2506 0, /* tp_init */
2507 0, /* tp_alloc */
2508 tuplegetter_new, /* tp_new */
2509 0,
2510 };
2511
2512
2513 /* module level code ********************************************************/
2514
2515 PyDoc_STRVAR(module_doc,
2516 "High performance data structures.\n\
2517 - deque: ordered collection accessible from endpoints only\n\
2518 - defaultdict: dict subclass with a default value factory\n\
2519 ");
2520
2521 static struct PyMethodDef module_functions[] = {
2522 _COLLECTIONS__COUNT_ELEMENTS_METHODDEF
2523 {NULL, NULL} /* sentinel */
2524 };
2525
2526 static struct PyModuleDef _collectionsmodule = {
2527 PyModuleDef_HEAD_INIT,
2528 "_collections",
2529 module_doc,
2530 -1,
2531 module_functions,
2532 NULL,
2533 NULL,
2534 NULL,
2535 NULL
2536 };
2537
2538 PyMODINIT_FUNC
PyInit__collections(void)2539 PyInit__collections(void)
2540 {
2541 PyObject *m;
2542
2543 m = PyModule_Create(&_collectionsmodule);
2544 if (m == NULL)
2545 return NULL;
2546
2547 if (PyType_Ready(&deque_type) < 0)
2548 return NULL;
2549 Py_INCREF(&deque_type);
2550 PyModule_AddObject(m, "deque", (PyObject *)&deque_type);
2551
2552 defdict_type.tp_base = &PyDict_Type;
2553 if (PyType_Ready(&defdict_type) < 0)
2554 return NULL;
2555 Py_INCREF(&defdict_type);
2556 PyModule_AddObject(m, "defaultdict", (PyObject *)&defdict_type);
2557
2558 Py_INCREF(&PyODict_Type);
2559 PyModule_AddObject(m, "OrderedDict", (PyObject *)&PyODict_Type);
2560
2561 if (PyType_Ready(&dequeiter_type) < 0)
2562 return NULL;
2563 Py_INCREF(&dequeiter_type);
2564 PyModule_AddObject(m, "_deque_iterator", (PyObject *)&dequeiter_type);
2565
2566 if (PyType_Ready(&dequereviter_type) < 0)
2567 return NULL;
2568 Py_INCREF(&dequereviter_type);
2569 PyModule_AddObject(m, "_deque_reverse_iterator", (PyObject *)&dequereviter_type);
2570
2571 if (PyType_Ready(&tuplegetter_type) < 0)
2572 return NULL;
2573 Py_INCREF(&tuplegetter_type);
2574 PyModule_AddObject(m, "_tuplegetter", (PyObject *)&tuplegetter_type);
2575
2576 return m;
2577 }
2578