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