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 dequeobject *old_deque = (dequeobject *)deque;
518 if (Py_TYPE(deque) == &deque_type) {
519 dequeobject *new_deque;
520 PyObject *rv;
521
522 new_deque = (dequeobject *)deque_new(&deque_type, (PyObject *)NULL, (PyObject *)NULL);
523 if (new_deque == NULL)
524 return NULL;
525 new_deque->maxlen = old_deque->maxlen;
526 /* Fast path for the deque_repeat() common case where len(deque) == 1 */
527 if (Py_SIZE(deque) == 1) {
528 PyObject *item = old_deque->leftblock->data[old_deque->leftindex];
529 rv = deque_append(new_deque, item);
530 } else {
531 rv = deque_extend(new_deque, deque);
532 }
533 if (rv != NULL) {
534 Py_DECREF(rv);
535 return (PyObject *)new_deque;
536 }
537 Py_DECREF(new_deque);
538 return NULL;
539 }
540 if (old_deque->maxlen < 0)
541 return PyObject_CallFunction((PyObject *)(Py_TYPE(deque)), "O", deque, NULL);
542 else
543 return PyObject_CallFunction((PyObject *)(Py_TYPE(deque)), "Oi",
544 deque, old_deque->maxlen, NULL);
545 }
546
547 PyDoc_STRVAR(copy_doc, "Return a shallow copy of a deque.");
548
549 static PyObject *
deque_concat(dequeobject * deque,PyObject * other)550 deque_concat(dequeobject *deque, PyObject *other)
551 {
552 PyObject *new_deque, *result;
553 int rv;
554
555 rv = PyObject_IsInstance(other, (PyObject *)&deque_type);
556 if (rv <= 0) {
557 if (rv == 0) {
558 PyErr_Format(PyExc_TypeError,
559 "can only concatenate deque (not \"%.200s\") to deque",
560 other->ob_type->tp_name);
561 }
562 return NULL;
563 }
564
565 new_deque = deque_copy((PyObject *)deque);
566 if (new_deque == NULL)
567 return NULL;
568 result = deque_extend((dequeobject *)new_deque, other);
569 if (result == NULL) {
570 Py_DECREF(new_deque);
571 return NULL;
572 }
573 Py_DECREF(result);
574 return new_deque;
575 }
576
577 static void
deque_clear(dequeobject * deque)578 deque_clear(dequeobject *deque)
579 {
580 block *b;
581 block *prevblock;
582 block *leftblock;
583 Py_ssize_t leftindex;
584 Py_ssize_t n, m;
585 PyObject *item;
586 PyObject **itemptr, **limit;
587
588 if (Py_SIZE(deque) == 0)
589 return;
590
591 /* During the process of clearing a deque, decrefs can cause the
592 deque to mutate. To avoid fatal confusion, we have to make the
593 deque empty before clearing the blocks and never refer to
594 anything via deque->ref while clearing. (This is the same
595 technique used for clearing lists, sets, and dicts.)
596
597 Making the deque empty requires allocating a new empty block. In
598 the unlikely event that memory is full, we fall back to an
599 alternate method that doesn't require a new block. Repeating
600 pops in a while-loop is slower, possibly re-entrant (and a clever
601 adversary could cause it to never terminate).
602 */
603
604 b = newblock();
605 if (b == NULL) {
606 PyErr_Clear();
607 goto alternate_method;
608 }
609
610 /* Remember the old size, leftblock, and leftindex */
611 n = Py_SIZE(deque);
612 leftblock = deque->leftblock;
613 leftindex = deque->leftindex;
614
615 /* Set the deque to be empty using the newly allocated block */
616 MARK_END(b->leftlink);
617 MARK_END(b->rightlink);
618 Py_SIZE(deque) = 0;
619 deque->leftblock = b;
620 deque->rightblock = b;
621 deque->leftindex = CENTER + 1;
622 deque->rightindex = CENTER;
623 deque->state++;
624
625 /* Now the old size, leftblock, and leftindex are disconnected from
626 the empty deque and we can use them to decref the pointers.
627 */
628 m = (BLOCKLEN - leftindex > n) ? n : BLOCKLEN - leftindex;
629 itemptr = &leftblock->data[leftindex];
630 limit = itemptr + m;
631 n -= m;
632 while (1) {
633 if (itemptr == limit) {
634 if (n == 0)
635 break;
636 CHECK_NOT_END(leftblock->rightlink);
637 prevblock = leftblock;
638 leftblock = leftblock->rightlink;
639 m = (n > BLOCKLEN) ? BLOCKLEN : n;
640 itemptr = leftblock->data;
641 limit = itemptr + m;
642 n -= m;
643 freeblock(prevblock);
644 }
645 item = *(itemptr++);
646 Py_DECREF(item);
647 }
648 CHECK_END(leftblock->rightlink);
649 freeblock(leftblock);
650 return;
651
652 alternate_method:
653 while (Py_SIZE(deque)) {
654 item = deque_pop(deque, NULL);
655 assert (item != NULL);
656 Py_DECREF(item);
657 }
658 }
659
660 static PyObject *
deque_clearmethod(dequeobject * deque)661 deque_clearmethod(dequeobject *deque)
662 {
663 deque_clear(deque);
664 Py_RETURN_NONE;
665 }
666
667 PyDoc_STRVAR(clear_doc, "Remove all elements from the deque.");
668
669 static PyObject *
deque_inplace_repeat(dequeobject * deque,Py_ssize_t n)670 deque_inplace_repeat(dequeobject *deque, Py_ssize_t n)
671 {
672 Py_ssize_t i, m, size;
673 PyObject *seq;
674 PyObject *rv;
675
676 size = Py_SIZE(deque);
677 if (size == 0 || n == 1) {
678 Py_INCREF(deque);
679 return (PyObject *)deque;
680 }
681
682 if (n <= 0) {
683 deque_clear(deque);
684 Py_INCREF(deque);
685 return (PyObject *)deque;
686 }
687
688 if (size == 1) {
689 /* common case, repeating a single element */
690 PyObject *item = deque->leftblock->data[deque->leftindex];
691
692 if (deque->maxlen >= 0 && n > deque->maxlen)
693 n = deque->maxlen;
694
695 deque->state++;
696 for (i = 0 ; i < n-1 ; ) {
697 if (deque->rightindex == BLOCKLEN - 1) {
698 block *b = newblock();
699 if (b == NULL) {
700 Py_SIZE(deque) += i;
701 return NULL;
702 }
703 b->leftlink = deque->rightblock;
704 CHECK_END(deque->rightblock->rightlink);
705 deque->rightblock->rightlink = b;
706 deque->rightblock = b;
707 MARK_END(b->rightlink);
708 deque->rightindex = -1;
709 }
710 m = n - 1 - i;
711 if (m > BLOCKLEN - 1 - deque->rightindex)
712 m = BLOCKLEN - 1 - deque->rightindex;
713 i += m;
714 while (m--) {
715 deque->rightindex++;
716 Py_INCREF(item);
717 deque->rightblock->data[deque->rightindex] = item;
718 }
719 }
720 Py_SIZE(deque) += i;
721 Py_INCREF(deque);
722 return (PyObject *)deque;
723 }
724
725 if ((size_t)size > PY_SSIZE_T_MAX / (size_t)n) {
726 return PyErr_NoMemory();
727 }
728
729 seq = PySequence_List((PyObject *)deque);
730 if (seq == NULL)
731 return seq;
732
733 for (i = 0 ; i < n-1 ; i++) {
734 rv = deque_extend(deque, seq);
735 if (rv == NULL) {
736 Py_DECREF(seq);
737 return NULL;
738 }
739 Py_DECREF(rv);
740 }
741 Py_INCREF(deque);
742 Py_DECREF(seq);
743 return (PyObject *)deque;
744 }
745
746 static PyObject *
deque_repeat(dequeobject * deque,Py_ssize_t n)747 deque_repeat(dequeobject *deque, Py_ssize_t n)
748 {
749 dequeobject *new_deque;
750 PyObject *rv;
751
752 new_deque = (dequeobject *)deque_copy((PyObject *) deque);
753 if (new_deque == NULL)
754 return NULL;
755 rv = deque_inplace_repeat(new_deque, n);
756 Py_DECREF(new_deque);
757 return rv;
758 }
759
760 /* The rotate() method is part of the public API and is used internally
761 as a primitive for other methods.
762
763 Rotation by 1 or -1 is a common case, so any optimizations for high
764 volume rotations should take care not to penalize the common case.
765
766 Conceptually, a rotate by one is equivalent to a pop on one side and an
767 append on the other. However, a pop/append pair is unnecessarily slow
768 because it requires an incref/decref pair for an object located randomly
769 in memory. It is better to just move the object pointer from one block
770 to the next without changing the reference count.
771
772 When moving batches of pointers, it is tempting to use memcpy() but that
773 proved to be slower than a simple loop for a variety of reasons.
774 Memcpy() cannot know in advance that we're copying pointers instead of
775 bytes, that the source and destination are pointer aligned and
776 non-overlapping, that moving just one pointer is a common case, that we
777 never need to move more than BLOCKLEN pointers, and that at least one
778 pointer is always moved.
779
780 For high volume rotations, newblock() and freeblock() are never called
781 more than once. Previously emptied blocks are immediately reused as a
782 destination block. If a block is left-over at the end, it is freed.
783 */
784
785 static int
_deque_rotate(dequeobject * deque,Py_ssize_t n)786 _deque_rotate(dequeobject *deque, Py_ssize_t n)
787 {
788 block *b = NULL;
789 block *leftblock = deque->leftblock;
790 block *rightblock = deque->rightblock;
791 Py_ssize_t leftindex = deque->leftindex;
792 Py_ssize_t rightindex = deque->rightindex;
793 Py_ssize_t len=Py_SIZE(deque), halflen=len>>1;
794 int rv = -1;
795
796 if (len <= 1)
797 return 0;
798 if (n > halflen || n < -halflen) {
799 n %= len;
800 if (n > halflen)
801 n -= len;
802 else if (n < -halflen)
803 n += len;
804 }
805 assert(len > 1);
806 assert(-halflen <= n && n <= halflen);
807
808 deque->state++;
809 while (n > 0) {
810 if (leftindex == 0) {
811 if (b == NULL) {
812 b = newblock();
813 if (b == NULL)
814 goto done;
815 }
816 b->rightlink = leftblock;
817 CHECK_END(leftblock->leftlink);
818 leftblock->leftlink = b;
819 leftblock = b;
820 MARK_END(b->leftlink);
821 leftindex = BLOCKLEN;
822 b = NULL;
823 }
824 assert(leftindex > 0);
825 {
826 PyObject **src, **dest;
827 Py_ssize_t m = n;
828
829 if (m > rightindex + 1)
830 m = rightindex + 1;
831 if (m > leftindex)
832 m = leftindex;
833 assert (m > 0 && m <= len);
834 rightindex -= m;
835 leftindex -= m;
836 src = &rightblock->data[rightindex + 1];
837 dest = &leftblock->data[leftindex];
838 n -= m;
839 do {
840 *(dest++) = *(src++);
841 } while (--m);
842 }
843 if (rightindex < 0) {
844 assert(leftblock != rightblock);
845 assert(b == NULL);
846 b = rightblock;
847 CHECK_NOT_END(rightblock->leftlink);
848 rightblock = rightblock->leftlink;
849 MARK_END(rightblock->rightlink);
850 rightindex = BLOCKLEN - 1;
851 }
852 }
853 while (n < 0) {
854 if (rightindex == BLOCKLEN - 1) {
855 if (b == NULL) {
856 b = newblock();
857 if (b == NULL)
858 goto done;
859 }
860 b->leftlink = rightblock;
861 CHECK_END(rightblock->rightlink);
862 rightblock->rightlink = b;
863 rightblock = b;
864 MARK_END(b->rightlink);
865 rightindex = -1;
866 b = NULL;
867 }
868 assert (rightindex < BLOCKLEN - 1);
869 {
870 PyObject **src, **dest;
871 Py_ssize_t m = -n;
872
873 if (m > BLOCKLEN - leftindex)
874 m = BLOCKLEN - leftindex;
875 if (m > BLOCKLEN - 1 - rightindex)
876 m = BLOCKLEN - 1 - rightindex;
877 assert (m > 0 && m <= len);
878 src = &leftblock->data[leftindex];
879 dest = &rightblock->data[rightindex + 1];
880 leftindex += m;
881 rightindex += m;
882 n += m;
883 do {
884 *(dest++) = *(src++);
885 } while (--m);
886 }
887 if (leftindex == BLOCKLEN) {
888 assert(leftblock != rightblock);
889 assert(b == NULL);
890 b = leftblock;
891 CHECK_NOT_END(leftblock->rightlink);
892 leftblock = leftblock->rightlink;
893 MARK_END(leftblock->leftlink);
894 leftindex = 0;
895 }
896 }
897 rv = 0;
898 done:
899 if (b != NULL)
900 freeblock(b);
901 deque->leftblock = leftblock;
902 deque->rightblock = rightblock;
903 deque->leftindex = leftindex;
904 deque->rightindex = rightindex;
905
906 return rv;
907 }
908
909 static PyObject *
deque_rotate(dequeobject * deque,PyObject * args)910 deque_rotate(dequeobject *deque, PyObject *args)
911 {
912 Py_ssize_t n=1;
913
914 if (!PyArg_ParseTuple(args, "|n:rotate", &n))
915 return NULL;
916 if (!_deque_rotate(deque, n))
917 Py_RETURN_NONE;
918 return NULL;
919 }
920
921 PyDoc_STRVAR(rotate_doc,
922 "Rotate the deque n steps to the right (default n=1). If n is negative, rotates left.");
923
924 static PyObject *
deque_reverse(dequeobject * deque,PyObject * unused)925 deque_reverse(dequeobject *deque, PyObject *unused)
926 {
927 block *leftblock = deque->leftblock;
928 block *rightblock = deque->rightblock;
929 Py_ssize_t leftindex = deque->leftindex;
930 Py_ssize_t rightindex = deque->rightindex;
931 Py_ssize_t n = Py_SIZE(deque) >> 1;
932 PyObject *tmp;
933
934 n++;
935 while (--n) {
936 /* Validate that pointers haven't met in the middle */
937 assert(leftblock != rightblock || leftindex < rightindex);
938 CHECK_NOT_END(leftblock);
939 CHECK_NOT_END(rightblock);
940
941 /* Swap */
942 tmp = leftblock->data[leftindex];
943 leftblock->data[leftindex] = rightblock->data[rightindex];
944 rightblock->data[rightindex] = tmp;
945
946 /* Advance left block/index pair */
947 leftindex++;
948 if (leftindex == BLOCKLEN) {
949 leftblock = leftblock->rightlink;
950 leftindex = 0;
951 }
952
953 /* Step backwards with the right block/index pair */
954 rightindex--;
955 if (rightindex < 0) {
956 rightblock = rightblock->leftlink;
957 rightindex = BLOCKLEN - 1;
958 }
959 }
960 Py_RETURN_NONE;
961 }
962
963 PyDoc_STRVAR(reverse_doc,
964 "D.reverse() -- reverse *IN PLACE*");
965
966 static PyObject *
deque_count(dequeobject * deque,PyObject * v)967 deque_count(dequeobject *deque, PyObject *v)
968 {
969 block *b = deque->leftblock;
970 Py_ssize_t index = deque->leftindex;
971 Py_ssize_t n = Py_SIZE(deque);
972 Py_ssize_t count = 0;
973 size_t start_state = deque->state;
974 PyObject *item;
975 int cmp;
976
977 n++;
978 while (--n) {
979 CHECK_NOT_END(b);
980 item = b->data[index];
981 cmp = PyObject_RichCompareBool(item, v, Py_EQ);
982 if (cmp < 0)
983 return NULL;
984 count += cmp;
985
986 if (start_state != deque->state) {
987 PyErr_SetString(PyExc_RuntimeError,
988 "deque mutated during iteration");
989 return NULL;
990 }
991
992 /* Advance left block/index pair */
993 index++;
994 if (index == BLOCKLEN) {
995 b = b->rightlink;
996 index = 0;
997 }
998 }
999 return PyLong_FromSsize_t(count);
1000 }
1001
1002 PyDoc_STRVAR(count_doc,
1003 "D.count(value) -> integer -- return number of occurrences of value");
1004
1005 static int
deque_contains(dequeobject * deque,PyObject * v)1006 deque_contains(dequeobject *deque, PyObject *v)
1007 {
1008 block *b = deque->leftblock;
1009 Py_ssize_t index = deque->leftindex;
1010 Py_ssize_t n = Py_SIZE(deque);
1011 size_t start_state = deque->state;
1012 PyObject *item;
1013 int cmp;
1014
1015 n++;
1016 while (--n) {
1017 CHECK_NOT_END(b);
1018 item = b->data[index];
1019 cmp = PyObject_RichCompareBool(item, v, Py_EQ);
1020 if (cmp) {
1021 return cmp;
1022 }
1023 if (start_state != deque->state) {
1024 PyErr_SetString(PyExc_RuntimeError,
1025 "deque mutated during iteration");
1026 return -1;
1027 }
1028 index++;
1029 if (index == BLOCKLEN) {
1030 b = b->rightlink;
1031 index = 0;
1032 }
1033 }
1034 return 0;
1035 }
1036
1037 static Py_ssize_t
deque_len(dequeobject * deque)1038 deque_len(dequeobject *deque)
1039 {
1040 return Py_SIZE(deque);
1041 }
1042
1043 static PyObject *
deque_index(dequeobject * deque,PyObject * args)1044 deque_index(dequeobject *deque, PyObject *args)
1045 {
1046 Py_ssize_t i, n, start=0, stop=Py_SIZE(deque);
1047 PyObject *v, *item;
1048 block *b = deque->leftblock;
1049 Py_ssize_t index = deque->leftindex;
1050 size_t start_state = deque->state;
1051 int cmp;
1052
1053 if (!PyArg_ParseTuple(args, "O|O&O&:index", &v,
1054 _PyEval_SliceIndex, &start,
1055 _PyEval_SliceIndex, &stop))
1056 return NULL;
1057 if (start < 0) {
1058 start += Py_SIZE(deque);
1059 if (start < 0)
1060 start = 0;
1061 }
1062 if (stop < 0) {
1063 stop += Py_SIZE(deque);
1064 if (stop < 0)
1065 stop = 0;
1066 }
1067 if (stop > Py_SIZE(deque))
1068 stop = Py_SIZE(deque);
1069 if (start > stop)
1070 start = stop;
1071 assert(0 <= start && start <= stop && stop <= Py_SIZE(deque));
1072
1073 /* XXX Replace this loop with faster code from deque_item() */
1074 for (i=0 ; i<start ; i++) {
1075 index++;
1076 if (index == BLOCKLEN) {
1077 b = b->rightlink;
1078 index = 0;
1079 }
1080 }
1081
1082 n = stop - i + 1;
1083 while (--n) {
1084 CHECK_NOT_END(b);
1085 item = b->data[index];
1086 cmp = PyObject_RichCompareBool(item, v, Py_EQ);
1087 if (cmp > 0)
1088 return PyLong_FromSsize_t(stop - n);
1089 if (cmp < 0)
1090 return NULL;
1091 if (start_state != deque->state) {
1092 PyErr_SetString(PyExc_RuntimeError,
1093 "deque mutated during iteration");
1094 return NULL;
1095 }
1096 index++;
1097 if (index == BLOCKLEN) {
1098 b = b->rightlink;
1099 index = 0;
1100 }
1101 }
1102 PyErr_Format(PyExc_ValueError, "%R is not in deque", v);
1103 return NULL;
1104 }
1105
1106 PyDoc_STRVAR(index_doc,
1107 "D.index(value, [start, [stop]]) -> integer -- return first index of value.\n"
1108 "Raises ValueError if the value is not present.");
1109
1110 /* insert(), remove(), and delitem() are implemented in terms of
1111 rotate() for simplicity and reasonable performance near the end
1112 points. If for some reason these methods become popular, it is not
1113 hard to re-implement this using direct data movement (similar to
1114 the code used in list slice assignments) and achieve a performance
1115 boost (by moving each pointer only once instead of twice).
1116 */
1117
1118 static PyObject *
deque_insert(dequeobject * deque,PyObject * args)1119 deque_insert(dequeobject *deque, PyObject *args)
1120 {
1121 Py_ssize_t index;
1122 Py_ssize_t n = Py_SIZE(deque);
1123 PyObject *value;
1124 PyObject *rv;
1125
1126 if (!PyArg_ParseTuple(args, "nO:insert", &index, &value))
1127 return NULL;
1128 if (deque->maxlen == Py_SIZE(deque)) {
1129 PyErr_SetString(PyExc_IndexError, "deque already at its maximum size");
1130 return NULL;
1131 }
1132 if (index >= n)
1133 return deque_append(deque, value);
1134 if (index <= -n || index == 0)
1135 return deque_appendleft(deque, value);
1136 if (_deque_rotate(deque, -index))
1137 return NULL;
1138 if (index < 0)
1139 rv = deque_append(deque, value);
1140 else
1141 rv = deque_appendleft(deque, value);
1142 if (rv == NULL)
1143 return NULL;
1144 Py_DECREF(rv);
1145 if (_deque_rotate(deque, index))
1146 return NULL;
1147 Py_RETURN_NONE;
1148 }
1149
1150 PyDoc_STRVAR(insert_doc,
1151 "D.insert(index, object) -- insert object before index");
1152
1153 static PyObject *
deque_remove(dequeobject * deque,PyObject * value)1154 deque_remove(dequeobject *deque, PyObject *value)
1155 {
1156 Py_ssize_t i, n=Py_SIZE(deque);
1157
1158 for (i=0 ; i<n ; i++) {
1159 PyObject *item = deque->leftblock->data[deque->leftindex];
1160 int cmp = PyObject_RichCompareBool(item, value, Py_EQ);
1161
1162 if (Py_SIZE(deque) != n) {
1163 PyErr_SetString(PyExc_IndexError,
1164 "deque mutated during remove().");
1165 return NULL;
1166 }
1167 if (cmp > 0) {
1168 PyObject *tgt = deque_popleft(deque, NULL);
1169 assert (tgt != NULL);
1170 if (_deque_rotate(deque, i))
1171 return NULL;
1172 Py_DECREF(tgt);
1173 Py_RETURN_NONE;
1174 }
1175 else if (cmp < 0) {
1176 _deque_rotate(deque, i);
1177 return NULL;
1178 }
1179 _deque_rotate(deque, -1);
1180 }
1181 PyErr_SetString(PyExc_ValueError, "deque.remove(x): x not in deque");
1182 return NULL;
1183 }
1184
1185 PyDoc_STRVAR(remove_doc,
1186 "D.remove(value) -- remove first occurrence of value.");
1187
1188 static int
valid_index(Py_ssize_t i,Py_ssize_t limit)1189 valid_index(Py_ssize_t i, Py_ssize_t limit)
1190 {
1191 /* The cast to size_t lets us use just a single comparison
1192 to check whether i is in the range: 0 <= i < limit */
1193 return (size_t) i < (size_t) limit;
1194 }
1195
1196 static PyObject *
deque_item(dequeobject * deque,Py_ssize_t i)1197 deque_item(dequeobject *deque, Py_ssize_t i)
1198 {
1199 block *b;
1200 PyObject *item;
1201 Py_ssize_t n, index=i;
1202
1203 if (!valid_index(i, Py_SIZE(deque))) {
1204 PyErr_SetString(PyExc_IndexError, "deque index out of range");
1205 return NULL;
1206 }
1207
1208 if (i == 0) {
1209 i = deque->leftindex;
1210 b = deque->leftblock;
1211 } else if (i == Py_SIZE(deque) - 1) {
1212 i = deque->rightindex;
1213 b = deque->rightblock;
1214 } else {
1215 i += deque->leftindex;
1216 n = (Py_ssize_t)((size_t) i / BLOCKLEN);
1217 i = (Py_ssize_t)((size_t) i % BLOCKLEN);
1218 if (index < (Py_SIZE(deque) >> 1)) {
1219 b = deque->leftblock;
1220 n++;
1221 while (--n)
1222 b = b->rightlink;
1223 } else {
1224 n = (Py_ssize_t)(
1225 ((size_t)(deque->leftindex + Py_SIZE(deque) - 1))
1226 / BLOCKLEN - n);
1227 b = deque->rightblock;
1228 n++;
1229 while (--n)
1230 b = b->leftlink;
1231 }
1232 }
1233 item = b->data[i];
1234 Py_INCREF(item);
1235 return item;
1236 }
1237
1238 static int
deque_del_item(dequeobject * deque,Py_ssize_t i)1239 deque_del_item(dequeobject *deque, Py_ssize_t i)
1240 {
1241 PyObject *item;
1242 int rv;
1243
1244 assert (i >= 0 && i < Py_SIZE(deque));
1245 if (_deque_rotate(deque, -i))
1246 return -1;
1247 item = deque_popleft(deque, NULL);
1248 rv = _deque_rotate(deque, i);
1249 assert (item != NULL);
1250 Py_DECREF(item);
1251 return rv;
1252 }
1253
1254 static int
deque_ass_item(dequeobject * deque,Py_ssize_t i,PyObject * v)1255 deque_ass_item(dequeobject *deque, Py_ssize_t i, PyObject *v)
1256 {
1257 PyObject *old_value;
1258 block *b;
1259 Py_ssize_t n, len=Py_SIZE(deque), halflen=(len+1)>>1, index=i;
1260
1261 if (!valid_index(i, len)) {
1262 PyErr_SetString(PyExc_IndexError, "deque index out of range");
1263 return -1;
1264 }
1265 if (v == NULL)
1266 return deque_del_item(deque, i);
1267
1268 i += deque->leftindex;
1269 n = (Py_ssize_t)((size_t) i / BLOCKLEN);
1270 i = (Py_ssize_t)((size_t) i % BLOCKLEN);
1271 if (index <= halflen) {
1272 b = deque->leftblock;
1273 n++;
1274 while (--n)
1275 b = b->rightlink;
1276 } else {
1277 n = (Py_ssize_t)(
1278 ((size_t)(deque->leftindex + Py_SIZE(deque) - 1))
1279 / BLOCKLEN - n);
1280 b = deque->rightblock;
1281 n++;
1282 while (--n)
1283 b = b->leftlink;
1284 }
1285 Py_INCREF(v);
1286 old_value = b->data[i];
1287 b->data[i] = v;
1288 Py_DECREF(old_value);
1289 return 0;
1290 }
1291
1292 static void
deque_dealloc(dequeobject * deque)1293 deque_dealloc(dequeobject *deque)
1294 {
1295 PyObject_GC_UnTrack(deque);
1296 if (deque->weakreflist != NULL)
1297 PyObject_ClearWeakRefs((PyObject *) deque);
1298 if (deque->leftblock != NULL) {
1299 deque_clear(deque);
1300 assert(deque->leftblock != NULL);
1301 freeblock(deque->leftblock);
1302 }
1303 deque->leftblock = NULL;
1304 deque->rightblock = NULL;
1305 Py_TYPE(deque)->tp_free(deque);
1306 }
1307
1308 static int
deque_traverse(dequeobject * deque,visitproc visit,void * arg)1309 deque_traverse(dequeobject *deque, visitproc visit, void *arg)
1310 {
1311 block *b;
1312 PyObject *item;
1313 Py_ssize_t index;
1314 Py_ssize_t indexlo = deque->leftindex;
1315 Py_ssize_t indexhigh;
1316
1317 for (b = deque->leftblock; b != deque->rightblock; b = b->rightlink) {
1318 for (index = indexlo; index < BLOCKLEN ; index++) {
1319 item = b->data[index];
1320 Py_VISIT(item);
1321 }
1322 indexlo = 0;
1323 }
1324 indexhigh = deque->rightindex;
1325 for (index = indexlo; index <= indexhigh; index++) {
1326 item = b->data[index];
1327 Py_VISIT(item);
1328 }
1329 return 0;
1330 }
1331
1332 static PyObject *
deque_reduce(dequeobject * deque)1333 deque_reduce(dequeobject *deque)
1334 {
1335 PyObject *dict, *it;
1336 _Py_IDENTIFIER(__dict__);
1337
1338 dict = _PyObject_GetAttrId((PyObject *)deque, &PyId___dict__);
1339 if (dict == NULL) {
1340 if (!PyErr_ExceptionMatches(PyExc_AttributeError)) {
1341 return NULL;
1342 }
1343 PyErr_Clear();
1344 dict = Py_None;
1345 Py_INCREF(dict);
1346 }
1347
1348 it = PyObject_GetIter((PyObject *)deque);
1349 if (it == NULL) {
1350 Py_DECREF(dict);
1351 return NULL;
1352 }
1353
1354 if (deque->maxlen < 0) {
1355 return Py_BuildValue("O()NN", Py_TYPE(deque), dict, it);
1356 }
1357 else {
1358 return Py_BuildValue("O(()n)NN", Py_TYPE(deque), deque->maxlen, dict, it);
1359 }
1360 }
1361
1362 PyDoc_STRVAR(reduce_doc, "Return state information for pickling.");
1363
1364 static PyObject *
deque_repr(PyObject * deque)1365 deque_repr(PyObject *deque)
1366 {
1367 PyObject *aslist, *result;
1368 int i;
1369
1370 i = Py_ReprEnter(deque);
1371 if (i != 0) {
1372 if (i < 0)
1373 return NULL;
1374 return PyUnicode_FromString("[...]");
1375 }
1376
1377 aslist = PySequence_List(deque);
1378 if (aslist == NULL) {
1379 Py_ReprLeave(deque);
1380 return NULL;
1381 }
1382 if (((dequeobject *)deque)->maxlen >= 0)
1383 result = PyUnicode_FromFormat("deque(%R, maxlen=%zd)",
1384 aslist, ((dequeobject *)deque)->maxlen);
1385 else
1386 result = PyUnicode_FromFormat("deque(%R)", aslist);
1387 Py_ReprLeave(deque);
1388 Py_DECREF(aslist);
1389 return result;
1390 }
1391
1392 static PyObject *
deque_richcompare(PyObject * v,PyObject * w,int op)1393 deque_richcompare(PyObject *v, PyObject *w, int op)
1394 {
1395 PyObject *it1=NULL, *it2=NULL, *x, *y;
1396 Py_ssize_t vs, ws;
1397 int b, cmp=-1;
1398
1399 if (!PyObject_TypeCheck(v, &deque_type) ||
1400 !PyObject_TypeCheck(w, &deque_type)) {
1401 Py_RETURN_NOTIMPLEMENTED;
1402 }
1403
1404 /* Shortcuts */
1405 vs = Py_SIZE((dequeobject *)v);
1406 ws = Py_SIZE((dequeobject *)w);
1407 if (op == Py_EQ) {
1408 if (v == w)
1409 Py_RETURN_TRUE;
1410 if (vs != ws)
1411 Py_RETURN_FALSE;
1412 }
1413 if (op == Py_NE) {
1414 if (v == w)
1415 Py_RETURN_FALSE;
1416 if (vs != ws)
1417 Py_RETURN_TRUE;
1418 }
1419
1420 /* Search for the first index where items are different */
1421 it1 = PyObject_GetIter(v);
1422 if (it1 == NULL)
1423 goto done;
1424 it2 = PyObject_GetIter(w);
1425 if (it2 == NULL)
1426 goto done;
1427 for (;;) {
1428 x = PyIter_Next(it1);
1429 if (x == NULL && PyErr_Occurred())
1430 goto done;
1431 y = PyIter_Next(it2);
1432 if (x == NULL || y == NULL)
1433 break;
1434 b = PyObject_RichCompareBool(x, y, Py_EQ);
1435 if (b == 0) {
1436 cmp = PyObject_RichCompareBool(x, y, op);
1437 Py_DECREF(x);
1438 Py_DECREF(y);
1439 goto done;
1440 }
1441 Py_DECREF(x);
1442 Py_DECREF(y);
1443 if (b < 0)
1444 goto done;
1445 }
1446 /* We reached the end of one deque or both */
1447 Py_XDECREF(x);
1448 Py_XDECREF(y);
1449 if (PyErr_Occurred())
1450 goto done;
1451 switch (op) {
1452 case Py_LT: cmp = y != NULL; break; /* if w was longer */
1453 case Py_LE: cmp = x == NULL; break; /* if v was not longer */
1454 case Py_EQ: cmp = x == y; break; /* if we reached the end of both */
1455 case Py_NE: cmp = x != y; break; /* if one deque continues */
1456 case Py_GT: cmp = x != NULL; break; /* if v was longer */
1457 case Py_GE: cmp = y == NULL; break; /* if w was not longer */
1458 }
1459
1460 done:
1461 Py_XDECREF(it1);
1462 Py_XDECREF(it2);
1463 if (cmp == 1)
1464 Py_RETURN_TRUE;
1465 if (cmp == 0)
1466 Py_RETURN_FALSE;
1467 return NULL;
1468 }
1469
1470 static int
deque_init(dequeobject * deque,PyObject * args,PyObject * kwdargs)1471 deque_init(dequeobject *deque, PyObject *args, PyObject *kwdargs)
1472 {
1473 PyObject *iterable = NULL;
1474 PyObject *maxlenobj = NULL;
1475 Py_ssize_t maxlen = -1;
1476 char *kwlist[] = {"iterable", "maxlen", 0};
1477
1478 if (kwdargs == NULL) {
1479 if (!PyArg_UnpackTuple(args, "deque()", 0, 2, &iterable, &maxlenobj))
1480 return -1;
1481 } else {
1482 if (!PyArg_ParseTupleAndKeywords(args, kwdargs, "|OO:deque", kwlist,
1483 &iterable, &maxlenobj))
1484 return -1;
1485 }
1486 if (maxlenobj != NULL && maxlenobj != Py_None) {
1487 maxlen = PyLong_AsSsize_t(maxlenobj);
1488 if (maxlen == -1 && PyErr_Occurred())
1489 return -1;
1490 if (maxlen < 0) {
1491 PyErr_SetString(PyExc_ValueError, "maxlen must be non-negative");
1492 return -1;
1493 }
1494 }
1495 deque->maxlen = maxlen;
1496 if (Py_SIZE(deque) > 0)
1497 deque_clear(deque);
1498 if (iterable != NULL) {
1499 PyObject *rv = deque_extend(deque, iterable);
1500 if (rv == NULL)
1501 return -1;
1502 Py_DECREF(rv);
1503 }
1504 return 0;
1505 }
1506
1507 static PyObject *
deque_sizeof(dequeobject * deque,void * unused)1508 deque_sizeof(dequeobject *deque, void *unused)
1509 {
1510 Py_ssize_t res;
1511 Py_ssize_t blocks;
1512
1513 res = _PyObject_SIZE(Py_TYPE(deque));
1514 blocks = (size_t)(deque->leftindex + Py_SIZE(deque) + BLOCKLEN - 1) / BLOCKLEN;
1515 assert(deque->leftindex + Py_SIZE(deque) - 1 ==
1516 (blocks - 1) * BLOCKLEN + deque->rightindex);
1517 res += blocks * sizeof(block);
1518 return PyLong_FromSsize_t(res);
1519 }
1520
1521 PyDoc_STRVAR(sizeof_doc,
1522 "D.__sizeof__() -- size of D in memory, in bytes");
1523
1524 static int
deque_bool(dequeobject * deque)1525 deque_bool(dequeobject *deque)
1526 {
1527 return Py_SIZE(deque) != 0;
1528 }
1529
1530 static PyObject *
deque_get_maxlen(dequeobject * deque)1531 deque_get_maxlen(dequeobject *deque)
1532 {
1533 if (deque->maxlen < 0)
1534 Py_RETURN_NONE;
1535 return PyLong_FromSsize_t(deque->maxlen);
1536 }
1537
1538
1539 /* deque object ********************************************************/
1540
1541 static PyGetSetDef deque_getset[] = {
1542 {"maxlen", (getter)deque_get_maxlen, (setter)NULL,
1543 "maximum size of a deque or None if unbounded"},
1544 {0}
1545 };
1546
1547 static PySequenceMethods deque_as_sequence = {
1548 (lenfunc)deque_len, /* sq_length */
1549 (binaryfunc)deque_concat, /* sq_concat */
1550 (ssizeargfunc)deque_repeat, /* sq_repeat */
1551 (ssizeargfunc)deque_item, /* sq_item */
1552 0, /* sq_slice */
1553 (ssizeobjargproc)deque_ass_item, /* sq_ass_item */
1554 0, /* sq_ass_slice */
1555 (objobjproc)deque_contains, /* sq_contains */
1556 (binaryfunc)deque_inplace_concat, /* sq_inplace_concat */
1557 (ssizeargfunc)deque_inplace_repeat, /* sq_inplace_repeat */
1558 };
1559
1560 static PyNumberMethods deque_as_number = {
1561 0, /* nb_add */
1562 0, /* nb_subtract */
1563 0, /* nb_multiply */
1564 0, /* nb_remainder */
1565 0, /* nb_divmod */
1566 0, /* nb_power */
1567 0, /* nb_negative */
1568 0, /* nb_positive */
1569 0, /* nb_absolute */
1570 (inquiry)deque_bool, /* nb_bool */
1571 0, /* nb_invert */
1572 };
1573
1574 static PyObject *deque_iter(dequeobject *deque);
1575 static PyObject *deque_reviter(dequeobject *deque);
1576 PyDoc_STRVAR(reversed_doc,
1577 "D.__reversed__() -- return a reverse iterator over the deque");
1578
1579 static PyMethodDef deque_methods[] = {
1580 {"append", (PyCFunction)deque_append,
1581 METH_O, append_doc},
1582 {"appendleft", (PyCFunction)deque_appendleft,
1583 METH_O, appendleft_doc},
1584 {"clear", (PyCFunction)deque_clearmethod,
1585 METH_NOARGS, clear_doc},
1586 {"__copy__", (PyCFunction)deque_copy,
1587 METH_NOARGS, copy_doc},
1588 {"copy", (PyCFunction)deque_copy,
1589 METH_NOARGS, copy_doc},
1590 {"count", (PyCFunction)deque_count,
1591 METH_O, count_doc},
1592 {"extend", (PyCFunction)deque_extend,
1593 METH_O, extend_doc},
1594 {"extendleft", (PyCFunction)deque_extendleft,
1595 METH_O, extendleft_doc},
1596 {"index", (PyCFunction)deque_index,
1597 METH_VARARGS, index_doc},
1598 {"insert", (PyCFunction)deque_insert,
1599 METH_VARARGS, insert_doc},
1600 {"pop", (PyCFunction)deque_pop,
1601 METH_NOARGS, pop_doc},
1602 {"popleft", (PyCFunction)deque_popleft,
1603 METH_NOARGS, popleft_doc},
1604 {"__reduce__", (PyCFunction)deque_reduce,
1605 METH_NOARGS, reduce_doc},
1606 {"remove", (PyCFunction)deque_remove,
1607 METH_O, remove_doc},
1608 {"__reversed__", (PyCFunction)deque_reviter,
1609 METH_NOARGS, reversed_doc},
1610 {"reverse", (PyCFunction)deque_reverse,
1611 METH_NOARGS, reverse_doc},
1612 {"rotate", (PyCFunction)deque_rotate,
1613 METH_VARARGS, rotate_doc},
1614 {"__sizeof__", (PyCFunction)deque_sizeof,
1615 METH_NOARGS, sizeof_doc},
1616 {NULL, NULL} /* sentinel */
1617 };
1618
1619 PyDoc_STRVAR(deque_doc,
1620 "deque([iterable[, maxlen]]) --> deque object\n\
1621 \n\
1622 A list-like sequence optimized for data accesses near its endpoints.");
1623
1624 static PyTypeObject deque_type = {
1625 PyVarObject_HEAD_INIT(NULL, 0)
1626 "collections.deque", /* tp_name */
1627 sizeof(dequeobject), /* tp_basicsize */
1628 0, /* tp_itemsize */
1629 /* methods */
1630 (destructor)deque_dealloc, /* tp_dealloc */
1631 0, /* tp_print */
1632 0, /* tp_getattr */
1633 0, /* tp_setattr */
1634 0, /* tp_reserved */
1635 deque_repr, /* tp_repr */
1636 &deque_as_number, /* tp_as_number */
1637 &deque_as_sequence, /* tp_as_sequence */
1638 0, /* tp_as_mapping */
1639 PyObject_HashNotImplemented, /* tp_hash */
1640 0, /* tp_call */
1641 0, /* tp_str */
1642 PyObject_GenericGetAttr, /* tp_getattro */
1643 0, /* tp_setattro */
1644 0, /* tp_as_buffer */
1645 Py_TPFLAGS_DEFAULT | Py_TPFLAGS_BASETYPE | Py_TPFLAGS_HAVE_GC,
1646 /* tp_flags */
1647 deque_doc, /* tp_doc */
1648 (traverseproc)deque_traverse, /* tp_traverse */
1649 (inquiry)deque_clear, /* tp_clear */
1650 (richcmpfunc)deque_richcompare, /* tp_richcompare */
1651 offsetof(dequeobject, weakreflist), /* tp_weaklistoffset*/
1652 (getiterfunc)deque_iter, /* tp_iter */
1653 0, /* tp_iternext */
1654 deque_methods, /* tp_methods */
1655 0, /* tp_members */
1656 deque_getset, /* tp_getset */
1657 0, /* tp_base */
1658 0, /* tp_dict */
1659 0, /* tp_descr_get */
1660 0, /* tp_descr_set */
1661 0, /* tp_dictoffset */
1662 (initproc)deque_init, /* tp_init */
1663 PyType_GenericAlloc, /* tp_alloc */
1664 deque_new, /* tp_new */
1665 PyObject_GC_Del, /* tp_free */
1666 };
1667
1668 /*********************** Deque Iterator **************************/
1669
1670 typedef struct {
1671 PyObject_HEAD
1672 block *b;
1673 Py_ssize_t index;
1674 dequeobject *deque;
1675 size_t state; /* state when the iterator is created */
1676 Py_ssize_t counter; /* number of items remaining for iteration */
1677 } dequeiterobject;
1678
1679 static PyTypeObject dequeiter_type;
1680
1681 static PyObject *
deque_iter(dequeobject * deque)1682 deque_iter(dequeobject *deque)
1683 {
1684 dequeiterobject *it;
1685
1686 it = PyObject_GC_New(dequeiterobject, &dequeiter_type);
1687 if (it == NULL)
1688 return NULL;
1689 it->b = deque->leftblock;
1690 it->index = deque->leftindex;
1691 Py_INCREF(deque);
1692 it->deque = deque;
1693 it->state = deque->state;
1694 it->counter = Py_SIZE(deque);
1695 PyObject_GC_Track(it);
1696 return (PyObject *)it;
1697 }
1698
1699 static int
dequeiter_traverse(dequeiterobject * dio,visitproc visit,void * arg)1700 dequeiter_traverse(dequeiterobject *dio, visitproc visit, void *arg)
1701 {
1702 Py_VISIT(dio->deque);
1703 return 0;
1704 }
1705
1706 static void
dequeiter_dealloc(dequeiterobject * dio)1707 dequeiter_dealloc(dequeiterobject *dio)
1708 {
1709 Py_XDECREF(dio->deque);
1710 PyObject_GC_Del(dio);
1711 }
1712
1713 static PyObject *
dequeiter_next(dequeiterobject * it)1714 dequeiter_next(dequeiterobject *it)
1715 {
1716 PyObject *item;
1717
1718 if (it->deque->state != it->state) {
1719 it->counter = 0;
1720 PyErr_SetString(PyExc_RuntimeError,
1721 "deque mutated during iteration");
1722 return NULL;
1723 }
1724 if (it->counter == 0)
1725 return NULL;
1726 assert (!(it->b == it->deque->rightblock &&
1727 it->index > it->deque->rightindex));
1728
1729 item = it->b->data[it->index];
1730 it->index++;
1731 it->counter--;
1732 if (it->index == BLOCKLEN && it->counter > 0) {
1733 CHECK_NOT_END(it->b->rightlink);
1734 it->b = it->b->rightlink;
1735 it->index = 0;
1736 }
1737 Py_INCREF(item);
1738 return item;
1739 }
1740
1741 static PyObject *
dequeiter_new(PyTypeObject * type,PyObject * args,PyObject * kwds)1742 dequeiter_new(PyTypeObject *type, PyObject *args, PyObject *kwds)
1743 {
1744 Py_ssize_t i, index=0;
1745 PyObject *deque;
1746 dequeiterobject *it;
1747 if (!PyArg_ParseTuple(args, "O!|n", &deque_type, &deque, &index))
1748 return NULL;
1749 assert(type == &dequeiter_type);
1750
1751 it = (dequeiterobject*)deque_iter((dequeobject *)deque);
1752 if (!it)
1753 return NULL;
1754 /* consume items from the queue */
1755 for(i=0; i<index; i++) {
1756 PyObject *item = dequeiter_next(it);
1757 if (item) {
1758 Py_DECREF(item);
1759 } else {
1760 if (it->counter) {
1761 Py_DECREF(it);
1762 return NULL;
1763 } else
1764 break;
1765 }
1766 }
1767 return (PyObject*)it;
1768 }
1769
1770 static PyObject *
dequeiter_len(dequeiterobject * it)1771 dequeiter_len(dequeiterobject *it)
1772 {
1773 return PyLong_FromSsize_t(it->counter);
1774 }
1775
1776 PyDoc_STRVAR(length_hint_doc, "Private method returning an estimate of len(list(it)).");
1777
1778 static PyObject *
dequeiter_reduce(dequeiterobject * it)1779 dequeiter_reduce(dequeiterobject *it)
1780 {
1781 return Py_BuildValue("O(On)", Py_TYPE(it), it->deque, Py_SIZE(it->deque) - it->counter);
1782 }
1783
1784 static PyMethodDef dequeiter_methods[] = {
1785 {"__length_hint__", (PyCFunction)dequeiter_len, METH_NOARGS, length_hint_doc},
1786 {"__reduce__", (PyCFunction)dequeiter_reduce, METH_NOARGS, reduce_doc},
1787 {NULL, NULL} /* sentinel */
1788 };
1789
1790 static PyTypeObject dequeiter_type = {
1791 PyVarObject_HEAD_INIT(NULL, 0)
1792 "_collections._deque_iterator", /* tp_name */
1793 sizeof(dequeiterobject), /* tp_basicsize */
1794 0, /* tp_itemsize */
1795 /* methods */
1796 (destructor)dequeiter_dealloc, /* tp_dealloc */
1797 0, /* tp_print */
1798 0, /* tp_getattr */
1799 0, /* tp_setattr */
1800 0, /* tp_reserved */
1801 0, /* tp_repr */
1802 0, /* tp_as_number */
1803 0, /* tp_as_sequence */
1804 0, /* tp_as_mapping */
1805 0, /* tp_hash */
1806 0, /* tp_call */
1807 0, /* tp_str */
1808 PyObject_GenericGetAttr, /* tp_getattro */
1809 0, /* tp_setattro */
1810 0, /* tp_as_buffer */
1811 Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC, /* tp_flags */
1812 0, /* tp_doc */
1813 (traverseproc)dequeiter_traverse, /* tp_traverse */
1814 0, /* tp_clear */
1815 0, /* tp_richcompare */
1816 0, /* tp_weaklistoffset */
1817 PyObject_SelfIter, /* tp_iter */
1818 (iternextfunc)dequeiter_next, /* tp_iternext */
1819 dequeiter_methods, /* tp_methods */
1820 0, /* tp_members */
1821 0, /* tp_getset */
1822 0, /* tp_base */
1823 0, /* tp_dict */
1824 0, /* tp_descr_get */
1825 0, /* tp_descr_set */
1826 0, /* tp_dictoffset */
1827 0, /* tp_init */
1828 0, /* tp_alloc */
1829 dequeiter_new, /* tp_new */
1830 0,
1831 };
1832
1833 /*********************** Deque Reverse Iterator **************************/
1834
1835 static PyTypeObject dequereviter_type;
1836
1837 static PyObject *
deque_reviter(dequeobject * deque)1838 deque_reviter(dequeobject *deque)
1839 {
1840 dequeiterobject *it;
1841
1842 it = PyObject_GC_New(dequeiterobject, &dequereviter_type);
1843 if (it == NULL)
1844 return NULL;
1845 it->b = deque->rightblock;
1846 it->index = deque->rightindex;
1847 Py_INCREF(deque);
1848 it->deque = deque;
1849 it->state = deque->state;
1850 it->counter = Py_SIZE(deque);
1851 PyObject_GC_Track(it);
1852 return (PyObject *)it;
1853 }
1854
1855 static PyObject *
dequereviter_next(dequeiterobject * it)1856 dequereviter_next(dequeiterobject *it)
1857 {
1858 PyObject *item;
1859 if (it->counter == 0)
1860 return NULL;
1861
1862 if (it->deque->state != it->state) {
1863 it->counter = 0;
1864 PyErr_SetString(PyExc_RuntimeError,
1865 "deque mutated during iteration");
1866 return NULL;
1867 }
1868 assert (!(it->b == it->deque->leftblock &&
1869 it->index < it->deque->leftindex));
1870
1871 item = it->b->data[it->index];
1872 it->index--;
1873 it->counter--;
1874 if (it->index < 0 && it->counter > 0) {
1875 CHECK_NOT_END(it->b->leftlink);
1876 it->b = it->b->leftlink;
1877 it->index = BLOCKLEN - 1;
1878 }
1879 Py_INCREF(item);
1880 return item;
1881 }
1882
1883 static PyObject *
dequereviter_new(PyTypeObject * type,PyObject * args,PyObject * kwds)1884 dequereviter_new(PyTypeObject *type, PyObject *args, PyObject *kwds)
1885 {
1886 Py_ssize_t i, index=0;
1887 PyObject *deque;
1888 dequeiterobject *it;
1889 if (!PyArg_ParseTuple(args, "O!|n", &deque_type, &deque, &index))
1890 return NULL;
1891 assert(type == &dequereviter_type);
1892
1893 it = (dequeiterobject*)deque_reviter((dequeobject *)deque);
1894 if (!it)
1895 return NULL;
1896 /* consume items from the queue */
1897 for(i=0; i<index; i++) {
1898 PyObject *item = dequereviter_next(it);
1899 if (item) {
1900 Py_DECREF(item);
1901 } else {
1902 if (it->counter) {
1903 Py_DECREF(it);
1904 return NULL;
1905 } else
1906 break;
1907 }
1908 }
1909 return (PyObject*)it;
1910 }
1911
1912 static PyTypeObject dequereviter_type = {
1913 PyVarObject_HEAD_INIT(NULL, 0)
1914 "_collections._deque_reverse_iterator", /* tp_name */
1915 sizeof(dequeiterobject), /* tp_basicsize */
1916 0, /* tp_itemsize */
1917 /* methods */
1918 (destructor)dequeiter_dealloc, /* tp_dealloc */
1919 0, /* tp_print */
1920 0, /* tp_getattr */
1921 0, /* tp_setattr */
1922 0, /* tp_reserved */
1923 0, /* tp_repr */
1924 0, /* tp_as_number */
1925 0, /* tp_as_sequence */
1926 0, /* tp_as_mapping */
1927 0, /* tp_hash */
1928 0, /* tp_call */
1929 0, /* tp_str */
1930 PyObject_GenericGetAttr, /* tp_getattro */
1931 0, /* tp_setattro */
1932 0, /* tp_as_buffer */
1933 Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC, /* tp_flags */
1934 0, /* tp_doc */
1935 (traverseproc)dequeiter_traverse, /* tp_traverse */
1936 0, /* tp_clear */
1937 0, /* tp_richcompare */
1938 0, /* tp_weaklistoffset */
1939 PyObject_SelfIter, /* tp_iter */
1940 (iternextfunc)dequereviter_next, /* tp_iternext */
1941 dequeiter_methods, /* tp_methods */
1942 0, /* tp_members */
1943 0, /* tp_getset */
1944 0, /* tp_base */
1945 0, /* tp_dict */
1946 0, /* tp_descr_get */
1947 0, /* tp_descr_set */
1948 0, /* tp_dictoffset */
1949 0, /* tp_init */
1950 0, /* tp_alloc */
1951 dequereviter_new, /* tp_new */
1952 0,
1953 };
1954
1955 /* defaultdict type *********************************************************/
1956
1957 typedef struct {
1958 PyDictObject dict;
1959 PyObject *default_factory;
1960 } defdictobject;
1961
1962 static PyTypeObject defdict_type; /* Forward */
1963
1964 PyDoc_STRVAR(defdict_missing_doc,
1965 "__missing__(key) # Called by __getitem__ for missing key; pseudo-code:\n\
1966 if self.default_factory is None: raise KeyError((key,))\n\
1967 self[key] = value = self.default_factory()\n\
1968 return value\n\
1969 ");
1970
1971 static PyObject *
defdict_missing(defdictobject * dd,PyObject * key)1972 defdict_missing(defdictobject *dd, PyObject *key)
1973 {
1974 PyObject *factory = dd->default_factory;
1975 PyObject *value;
1976 if (factory == NULL || factory == Py_None) {
1977 /* XXX Call dict.__missing__(key) */
1978 PyObject *tup;
1979 tup = PyTuple_Pack(1, key);
1980 if (!tup) return NULL;
1981 PyErr_SetObject(PyExc_KeyError, tup);
1982 Py_DECREF(tup);
1983 return NULL;
1984 }
1985 value = PyEval_CallObject(factory, NULL);
1986 if (value == NULL)
1987 return value;
1988 if (PyObject_SetItem((PyObject *)dd, key, value) < 0) {
1989 Py_DECREF(value);
1990 return NULL;
1991 }
1992 return value;
1993 }
1994
1995 PyDoc_STRVAR(defdict_copy_doc, "D.copy() -> a shallow copy of D.");
1996
1997 static PyObject *
defdict_copy(defdictobject * dd)1998 defdict_copy(defdictobject *dd)
1999 {
2000 /* This calls the object's class. That only works for subclasses
2001 whose class constructor has the same signature. Subclasses that
2002 define a different constructor signature must override copy().
2003 */
2004
2005 if (dd->default_factory == NULL)
2006 return PyObject_CallFunctionObjArgs((PyObject*)Py_TYPE(dd), Py_None, dd, NULL);
2007 return PyObject_CallFunctionObjArgs((PyObject*)Py_TYPE(dd),
2008 dd->default_factory, dd, NULL);
2009 }
2010
2011 static PyObject *
defdict_reduce(defdictobject * dd)2012 defdict_reduce(defdictobject *dd)
2013 {
2014 /* __reduce__ must return a 5-tuple as follows:
2015
2016 - factory function
2017 - tuple of args for the factory function
2018 - additional state (here None)
2019 - sequence iterator (here None)
2020 - dictionary iterator (yielding successive (key, value) pairs
2021
2022 This API is used by pickle.py and copy.py.
2023
2024 For this to be useful with pickle.py, the default_factory
2025 must be picklable; e.g., None, a built-in, or a global
2026 function in a module or package.
2027
2028 Both shallow and deep copying are supported, but for deep
2029 copying, the default_factory must be deep-copyable; e.g. None,
2030 or a built-in (functions are not copyable at this time).
2031
2032 This only works for subclasses as long as their constructor
2033 signature is compatible; the first argument must be the
2034 optional default_factory, defaulting to None.
2035 */
2036 PyObject *args;
2037 PyObject *items;
2038 PyObject *iter;
2039 PyObject *result;
2040 _Py_IDENTIFIER(items);
2041
2042 if (dd->default_factory == NULL || dd->default_factory == Py_None)
2043 args = PyTuple_New(0);
2044 else
2045 args = PyTuple_Pack(1, dd->default_factory);
2046 if (args == NULL)
2047 return NULL;
2048 items = _PyObject_CallMethodId((PyObject *)dd, &PyId_items, NULL);
2049 if (items == NULL) {
2050 Py_DECREF(args);
2051 return NULL;
2052 }
2053 iter = PyObject_GetIter(items);
2054 if (iter == NULL) {
2055 Py_DECREF(items);
2056 Py_DECREF(args);
2057 return NULL;
2058 }
2059 result = PyTuple_Pack(5, Py_TYPE(dd), args,
2060 Py_None, Py_None, iter);
2061 Py_DECREF(iter);
2062 Py_DECREF(items);
2063 Py_DECREF(args);
2064 return result;
2065 }
2066
2067 static PyMethodDef defdict_methods[] = {
2068 {"__missing__", (PyCFunction)defdict_missing, METH_O,
2069 defdict_missing_doc},
2070 {"copy", (PyCFunction)defdict_copy, METH_NOARGS,
2071 defdict_copy_doc},
2072 {"__copy__", (PyCFunction)defdict_copy, METH_NOARGS,
2073 defdict_copy_doc},
2074 {"__reduce__", (PyCFunction)defdict_reduce, METH_NOARGS,
2075 reduce_doc},
2076 {NULL}
2077 };
2078
2079 static PyMemberDef defdict_members[] = {
2080 {"default_factory", T_OBJECT,
2081 offsetof(defdictobject, default_factory), 0,
2082 PyDoc_STR("Factory for default value called by __missing__().")},
2083 {NULL}
2084 };
2085
2086 static void
defdict_dealloc(defdictobject * dd)2087 defdict_dealloc(defdictobject *dd)
2088 {
2089 Py_CLEAR(dd->default_factory);
2090 PyDict_Type.tp_dealloc((PyObject *)dd);
2091 }
2092
2093 static PyObject *
defdict_repr(defdictobject * dd)2094 defdict_repr(defdictobject *dd)
2095 {
2096 PyObject *baserepr;
2097 PyObject *defrepr;
2098 PyObject *result;
2099 baserepr = PyDict_Type.tp_repr((PyObject *)dd);
2100 if (baserepr == NULL)
2101 return NULL;
2102 if (dd->default_factory == NULL)
2103 defrepr = PyUnicode_FromString("None");
2104 else
2105 {
2106 int status = Py_ReprEnter(dd->default_factory);
2107 if (status != 0) {
2108 if (status < 0) {
2109 Py_DECREF(baserepr);
2110 return NULL;
2111 }
2112 defrepr = PyUnicode_FromString("...");
2113 }
2114 else
2115 defrepr = PyObject_Repr(dd->default_factory);
2116 Py_ReprLeave(dd->default_factory);
2117 }
2118 if (defrepr == NULL) {
2119 Py_DECREF(baserepr);
2120 return NULL;
2121 }
2122 result = PyUnicode_FromFormat("defaultdict(%U, %U)",
2123 defrepr, baserepr);
2124 Py_DECREF(defrepr);
2125 Py_DECREF(baserepr);
2126 return result;
2127 }
2128
2129 static int
defdict_traverse(PyObject * self,visitproc visit,void * arg)2130 defdict_traverse(PyObject *self, visitproc visit, void *arg)
2131 {
2132 Py_VISIT(((defdictobject *)self)->default_factory);
2133 return PyDict_Type.tp_traverse(self, visit, arg);
2134 }
2135
2136 static int
defdict_tp_clear(defdictobject * dd)2137 defdict_tp_clear(defdictobject *dd)
2138 {
2139 Py_CLEAR(dd->default_factory);
2140 return PyDict_Type.tp_clear((PyObject *)dd);
2141 }
2142
2143 static int
defdict_init(PyObject * self,PyObject * args,PyObject * kwds)2144 defdict_init(PyObject *self, PyObject *args, PyObject *kwds)
2145 {
2146 defdictobject *dd = (defdictobject *)self;
2147 PyObject *olddefault = dd->default_factory;
2148 PyObject *newdefault = NULL;
2149 PyObject *newargs;
2150 int result;
2151 if (args == NULL || !PyTuple_Check(args))
2152 newargs = PyTuple_New(0);
2153 else {
2154 Py_ssize_t n = PyTuple_GET_SIZE(args);
2155 if (n > 0) {
2156 newdefault = PyTuple_GET_ITEM(args, 0);
2157 if (!PyCallable_Check(newdefault) && newdefault != Py_None) {
2158 PyErr_SetString(PyExc_TypeError,
2159 "first argument must be callable or None");
2160 return -1;
2161 }
2162 }
2163 newargs = PySequence_GetSlice(args, 1, n);
2164 }
2165 if (newargs == NULL)
2166 return -1;
2167 Py_XINCREF(newdefault);
2168 dd->default_factory = newdefault;
2169 result = PyDict_Type.tp_init(self, newargs, kwds);
2170 Py_DECREF(newargs);
2171 Py_XDECREF(olddefault);
2172 return result;
2173 }
2174
2175 PyDoc_STRVAR(defdict_doc,
2176 "defaultdict(default_factory[, ...]) --> dict with default factory\n\
2177 \n\
2178 The default factory is called without arguments to produce\n\
2179 a new value when a key is not present, in __getitem__ only.\n\
2180 A defaultdict compares equal to a dict with the same items.\n\
2181 All remaining arguments are treated the same as if they were\n\
2182 passed to the dict constructor, including keyword arguments.\n\
2183 ");
2184
2185 /* See comment in xxsubtype.c */
2186 #define DEFERRED_ADDRESS(ADDR) 0
2187
2188 static PyTypeObject defdict_type = {
2189 PyVarObject_HEAD_INIT(DEFERRED_ADDRESS(&PyType_Type), 0)
2190 "collections.defaultdict", /* tp_name */
2191 sizeof(defdictobject), /* tp_basicsize */
2192 0, /* tp_itemsize */
2193 /* methods */
2194 (destructor)defdict_dealloc, /* tp_dealloc */
2195 0, /* tp_print */
2196 0, /* tp_getattr */
2197 0, /* tp_setattr */
2198 0, /* tp_reserved */
2199 (reprfunc)defdict_repr, /* tp_repr */
2200 0, /* tp_as_number */
2201 0, /* tp_as_sequence */
2202 0, /* tp_as_mapping */
2203 0, /* tp_hash */
2204 0, /* tp_call */
2205 0, /* tp_str */
2206 PyObject_GenericGetAttr, /* tp_getattro */
2207 0, /* tp_setattro */
2208 0, /* tp_as_buffer */
2209 Py_TPFLAGS_DEFAULT | Py_TPFLAGS_BASETYPE | Py_TPFLAGS_HAVE_GC,
2210 /* tp_flags */
2211 defdict_doc, /* tp_doc */
2212 defdict_traverse, /* tp_traverse */
2213 (inquiry)defdict_tp_clear, /* tp_clear */
2214 0, /* tp_richcompare */
2215 0, /* tp_weaklistoffset*/
2216 0, /* tp_iter */
2217 0, /* tp_iternext */
2218 defdict_methods, /* tp_methods */
2219 defdict_members, /* tp_members */
2220 0, /* tp_getset */
2221 DEFERRED_ADDRESS(&PyDict_Type), /* tp_base */
2222 0, /* tp_dict */
2223 0, /* tp_descr_get */
2224 0, /* tp_descr_set */
2225 0, /* tp_dictoffset */
2226 defdict_init, /* tp_init */
2227 PyType_GenericAlloc, /* tp_alloc */
2228 0, /* tp_new */
2229 PyObject_GC_Del, /* tp_free */
2230 };
2231
2232 /* helper function for Counter *********************************************/
2233
2234 PyDoc_STRVAR(_count_elements_doc,
2235 "_count_elements(mapping, iterable) -> None\n\
2236 \n\
2237 Count elements in the iterable, updating the mapping");
2238
2239 static PyObject *
_count_elements(PyObject * self,PyObject * args)2240 _count_elements(PyObject *self, PyObject *args)
2241 {
2242 _Py_IDENTIFIER(get);
2243 _Py_IDENTIFIER(__setitem__);
2244 PyObject *it, *iterable, *mapping, *oldval;
2245 PyObject *newval = NULL;
2246 PyObject *key = NULL;
2247 PyObject *zero = NULL;
2248 PyObject *one = NULL;
2249 PyObject *bound_get = NULL;
2250 PyObject *mapping_get;
2251 PyObject *dict_get;
2252 PyObject *mapping_setitem;
2253 PyObject *dict_setitem;
2254
2255 if (!PyArg_UnpackTuple(args, "_count_elements", 2, 2, &mapping, &iterable))
2256 return NULL;
2257
2258 it = PyObject_GetIter(iterable);
2259 if (it == NULL)
2260 return NULL;
2261
2262 one = PyLong_FromLong(1);
2263 if (one == NULL)
2264 goto done;
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 while (1) {
2277 /* Fast path advantages:
2278 1. Eliminate double hashing
2279 (by re-using the same hash for both the get and set)
2280 2. Avoid argument overhead of PyObject_CallFunctionObjArgs
2281 (argument tuple creation and parsing)
2282 3. Avoid indirection through a bound method object
2283 (creates another argument tuple)
2284 4. Avoid initial increment from zero
2285 (reuse an existing one-object instead)
2286 */
2287 Py_hash_t hash;
2288
2289 key = PyIter_Next(it);
2290 if (key == NULL)
2291 break;
2292
2293 if (!PyUnicode_CheckExact(key) ||
2294 (hash = ((PyASCIIObject *) key)->hash) == -1)
2295 {
2296 hash = PyObject_Hash(key);
2297 if (hash == -1)
2298 goto done;
2299 }
2300
2301 oldval = _PyDict_GetItem_KnownHash(mapping, key, hash);
2302 if (oldval == NULL) {
2303 if (PyErr_Occurred())
2304 goto done;
2305 if (_PyDict_SetItem_KnownHash(mapping, key, one, hash) < 0)
2306 goto done;
2307 } else {
2308 newval = PyNumber_Add(oldval, one);
2309 if (newval == NULL)
2310 goto done;
2311 if (_PyDict_SetItem_KnownHash(mapping, key, newval, hash) < 0)
2312 goto done;
2313 Py_CLEAR(newval);
2314 }
2315 Py_DECREF(key);
2316 }
2317 } else {
2318 bound_get = _PyObject_GetAttrId(mapping, &PyId_get);
2319 if (bound_get == NULL)
2320 goto done;
2321
2322 zero = PyLong_FromLong(0);
2323 if (zero == NULL)
2324 goto done;
2325
2326 while (1) {
2327 key = PyIter_Next(it);
2328 if (key == NULL)
2329 break;
2330 oldval = PyObject_CallFunctionObjArgs(bound_get, key, zero, NULL);
2331 if (oldval == NULL)
2332 break;
2333 newval = PyNumber_Add(oldval, one);
2334 Py_DECREF(oldval);
2335 if (newval == NULL)
2336 break;
2337 if (PyObject_SetItem(mapping, key, newval) < 0)
2338 break;
2339 Py_CLEAR(newval);
2340 Py_DECREF(key);
2341 }
2342 }
2343
2344 done:
2345 Py_DECREF(it);
2346 Py_XDECREF(key);
2347 Py_XDECREF(newval);
2348 Py_XDECREF(bound_get);
2349 Py_XDECREF(zero);
2350 Py_XDECREF(one);
2351 if (PyErr_Occurred())
2352 return NULL;
2353 Py_RETURN_NONE;
2354 }
2355
2356 /* module level code ********************************************************/
2357
2358 PyDoc_STRVAR(module_doc,
2359 "High performance data structures.\n\
2360 - deque: ordered collection accessible from endpoints only\n\
2361 - defaultdict: dict subclass with a default value factory\n\
2362 ");
2363
2364 static struct PyMethodDef module_functions[] = {
2365 {"_count_elements", _count_elements, METH_VARARGS, _count_elements_doc},
2366 {NULL, NULL} /* sentinel */
2367 };
2368
2369 static struct PyModuleDef _collectionsmodule = {
2370 PyModuleDef_HEAD_INIT,
2371 "_collections",
2372 module_doc,
2373 -1,
2374 module_functions,
2375 NULL,
2376 NULL,
2377 NULL,
2378 NULL
2379 };
2380
2381 PyMODINIT_FUNC
PyInit__collections(void)2382 PyInit__collections(void)
2383 {
2384 PyObject *m;
2385
2386 m = PyModule_Create(&_collectionsmodule);
2387 if (m == NULL)
2388 return NULL;
2389
2390 if (PyType_Ready(&deque_type) < 0)
2391 return NULL;
2392 Py_INCREF(&deque_type);
2393 PyModule_AddObject(m, "deque", (PyObject *)&deque_type);
2394
2395 defdict_type.tp_base = &PyDict_Type;
2396 if (PyType_Ready(&defdict_type) < 0)
2397 return NULL;
2398 Py_INCREF(&defdict_type);
2399 PyModule_AddObject(m, "defaultdict", (PyObject *)&defdict_type);
2400
2401 Py_INCREF(&PyODict_Type);
2402 PyModule_AddObject(m, "OrderedDict", (PyObject *)&PyODict_Type);
2403
2404 if (PyType_Ready(&dequeiter_type) < 0)
2405 return NULL;
2406 Py_INCREF(&dequeiter_type);
2407 PyModule_AddObject(m, "_deque_iterator", (PyObject *)&dequeiter_type);
2408
2409 if (PyType_Ready(&dequereviter_type) < 0)
2410 return NULL;
2411 Py_INCREF(&dequereviter_type);
2412 PyModule_AddObject(m, "_deque_reverse_iterator", (PyObject *)&dequereviter_type);
2413
2414 return m;
2415 }
2416