1 #include "Python.h"
2 #include "structmember.h"
3
4 /* collections module implementation of a deque() datatype
5 Written and maintained by Raymond D. Hettinger <python@rcn.com>
6 */
7
8 /* The block length may be set to any number over 1. Larger numbers
9 * reduce the number of calls to the memory allocator, give faster
10 * indexing and rotation, and reduce the link::data overhead ratio.
11 *
12 * Ideally, the block length will be set to two less than some
13 * multiple of the cache-line length (so that the full block
14 * including the leftlink and rightlink will fit neatly into
15 * cache lines).
16 */
17
18 #define BLOCKLEN 62
19 #define CENTER ((BLOCKLEN - 1) / 2)
20
21 /* A `dequeobject` is composed of a doubly-linked list of `block` nodes.
22 * This list is not circular (the leftmost block has leftlink==NULL,
23 * and the rightmost block has rightlink==NULL). A deque d's first
24 * element is at d.leftblock[leftindex] and its last element is at
25 * d.rightblock[rightindex]; note that, unlike as for Python slice
26 * indices, these indices are inclusive on both ends. By being inclusive
27 * on both ends, algorithms for left and right operations become
28 * symmetrical which simplifies the design.
29 *
30 * The list of blocks is never empty, so d.leftblock and d.rightblock
31 * are never equal to NULL.
32 *
33 * The indices, d.leftindex and d.rightindex are always in the range
34 * 0 <= index < BLOCKLEN.
35 * Their exact relationship is:
36 * (d.leftindex + d.len - 1) % BLOCKLEN == d.rightindex.
37 *
38 * Empty deques have d.len == 0; d.leftblock==d.rightblock;
39 * d.leftindex == CENTER+1; and d.rightindex == CENTER.
40 * Checking for d.len == 0 is the intended way to see whether d is empty.
41 *
42 * Whenever d.leftblock == d.rightblock,
43 * d.leftindex + d.len - 1 == d.rightindex.
44 *
45 * However, when d.leftblock != d.rightblock, d.leftindex and d.rightindex
46 * become indices into distinct blocks and either may be larger than the
47 * other.
48 */
49
50 typedef struct BLOCK {
51 PyObject *data[BLOCKLEN];
52 struct BLOCK *rightlink;
53 struct BLOCK *leftlink;
54 } block;
55
56 #define MAXFREEBLOCKS 10
57 static Py_ssize_t numfreeblocks = 0;
58 static block *freeblocks[MAXFREEBLOCKS];
59
60 static block *
newblock(block * leftlink,block * rightlink,Py_ssize_t len)61 newblock(block *leftlink, block *rightlink, Py_ssize_t len) {
62 block *b;
63 /* To prevent len from overflowing PY_SSIZE_T_MAX on 32-bit machines, we
64 * refuse to allocate new blocks if the current len is nearing overflow. */
65 if (len >= PY_SSIZE_T_MAX - 2*BLOCKLEN) {
66 PyErr_SetString(PyExc_OverflowError,
67 "cannot add more blocks to the deque");
68 return NULL;
69 }
70 if (numfreeblocks) {
71 numfreeblocks -= 1;
72 b = freeblocks[numfreeblocks];
73 } else {
74 b = PyMem_Malloc(sizeof(block));
75 if (b == NULL) {
76 PyErr_NoMemory();
77 return NULL;
78 }
79 }
80 b->leftlink = leftlink;
81 b->rightlink = rightlink;
82 return b;
83 }
84
85 static void
freeblock(block * b)86 freeblock(block *b)
87 {
88 if (numfreeblocks < MAXFREEBLOCKS) {
89 freeblocks[numfreeblocks] = b;
90 numfreeblocks++;
91 } else {
92 PyMem_Free(b);
93 }
94 }
95
96 typedef struct {
97 PyObject_HEAD
98 block *leftblock;
99 block *rightblock;
100 Py_ssize_t leftindex; /* in range(BLOCKLEN) */
101 Py_ssize_t rightindex; /* in range(BLOCKLEN) */
102 Py_ssize_t len;
103 long state; /* incremented whenever the indices move */
104 Py_ssize_t maxlen;
105 PyObject *weakreflist; /* List of weak references */
106 } dequeobject;
107
108 /* The deque's size limit is d.maxlen. The limit can be zero or positive.
109 * If there is no limit, then d.maxlen == -1.
110 *
111 * After an item is added to a deque, we check to see if the size has grown past
112 * the limit. If it has, we get the size back down to the limit by popping an
113 * item off of the opposite end. The methods that can trigger this are append(),
114 * appendleft(), extend(), and extendleft().
115 */
116
117 #define TRIM(d, popfunction) \
118 if (d->maxlen != -1 && d->len > d->maxlen) { \
119 PyObject *rv = popfunction(d, NULL); \
120 assert(rv != NULL && d->len <= d->maxlen); \
121 Py_DECREF(rv); \
122 }
123
124 static PyTypeObject deque_type;
125
126 static PyObject *
deque_new(PyTypeObject * type,PyObject * args,PyObject * kwds)127 deque_new(PyTypeObject *type, PyObject *args, PyObject *kwds)
128 {
129 dequeobject *deque;
130 block *b;
131
132 /* create dequeobject structure */
133 deque = (dequeobject *)type->tp_alloc(type, 0);
134 if (deque == NULL)
135 return NULL;
136
137 b = newblock(NULL, NULL, 0);
138 if (b == NULL) {
139 Py_DECREF(deque);
140 return NULL;
141 }
142
143 assert(BLOCKLEN >= 2);
144 deque->leftblock = b;
145 deque->rightblock = b;
146 deque->leftindex = CENTER + 1;
147 deque->rightindex = CENTER;
148 deque->len = 0;
149 deque->state = 0;
150 deque->weakreflist = NULL;
151 deque->maxlen = -1;
152
153 return (PyObject *)deque;
154 }
155
156 static PyObject *
deque_pop(dequeobject * deque,PyObject * unused)157 deque_pop(dequeobject *deque, PyObject *unused)
158 {
159 PyObject *item;
160 block *prevblock;
161
162 if (deque->len == 0) {
163 PyErr_SetString(PyExc_IndexError, "pop from an empty deque");
164 return NULL;
165 }
166 item = deque->rightblock->data[deque->rightindex];
167 deque->rightindex--;
168 deque->len--;
169 deque->state++;
170
171 if (deque->rightindex == -1) {
172 if (deque->len == 0) {
173 assert(deque->leftblock == deque->rightblock);
174 assert(deque->leftindex == deque->rightindex+1);
175 /* re-center instead of freeing a block */
176 deque->leftindex = CENTER + 1;
177 deque->rightindex = CENTER;
178 } else {
179 prevblock = deque->rightblock->leftlink;
180 assert(deque->leftblock != deque->rightblock);
181 freeblock(deque->rightblock);
182 prevblock->rightlink = NULL;
183 deque->rightblock = prevblock;
184 deque->rightindex = BLOCKLEN - 1;
185 }
186 }
187 return item;
188 }
189
190 PyDoc_STRVAR(pop_doc, "Remove and return the rightmost element.");
191
192 static PyObject *
deque_popleft(dequeobject * deque,PyObject * unused)193 deque_popleft(dequeobject *deque, PyObject *unused)
194 {
195 PyObject *item;
196 block *prevblock;
197
198 if (deque->len == 0) {
199 PyErr_SetString(PyExc_IndexError, "pop from an empty deque");
200 return NULL;
201 }
202 assert(deque->leftblock != NULL);
203 item = deque->leftblock->data[deque->leftindex];
204 deque->leftindex++;
205 deque->len--;
206 deque->state++;
207
208 if (deque->leftindex == BLOCKLEN) {
209 if (deque->len == 0) {
210 assert(deque->leftblock == deque->rightblock);
211 assert(deque->leftindex == deque->rightindex+1);
212 /* re-center instead of freeing a block */
213 deque->leftindex = CENTER + 1;
214 deque->rightindex = CENTER;
215 } else {
216 assert(deque->leftblock != deque->rightblock);
217 prevblock = deque->leftblock->rightlink;
218 freeblock(deque->leftblock);
219 assert(prevblock != NULL);
220 prevblock->leftlink = NULL;
221 deque->leftblock = prevblock;
222 deque->leftindex = 0;
223 }
224 }
225 return item;
226 }
227
228 PyDoc_STRVAR(popleft_doc, "Remove and return the leftmost element.");
229
230 static PyObject *
deque_append(dequeobject * deque,PyObject * item)231 deque_append(dequeobject *deque, PyObject *item)
232 {
233 deque->state++;
234 if (deque->rightindex == BLOCKLEN-1) {
235 block *b = newblock(deque->rightblock, NULL, deque->len);
236 if (b == NULL)
237 return NULL;
238 assert(deque->rightblock->rightlink == NULL);
239 deque->rightblock->rightlink = b;
240 deque->rightblock = b;
241 deque->rightindex = -1;
242 }
243 Py_INCREF(item);
244 deque->len++;
245 deque->rightindex++;
246 deque->rightblock->data[deque->rightindex] = item;
247 TRIM(deque, deque_popleft);
248 Py_RETURN_NONE;
249 }
250
251 PyDoc_STRVAR(append_doc, "Add an element to the right side of the deque.");
252
253 static PyObject *
deque_appendleft(dequeobject * deque,PyObject * item)254 deque_appendleft(dequeobject *deque, PyObject *item)
255 {
256 deque->state++;
257 if (deque->leftindex == 0) {
258 block *b = newblock(NULL, deque->leftblock, deque->len);
259 if (b == NULL)
260 return NULL;
261 assert(deque->leftblock->leftlink == NULL);
262 deque->leftblock->leftlink = b;
263 deque->leftblock = b;
264 deque->leftindex = BLOCKLEN;
265 }
266 Py_INCREF(item);
267 deque->len++;
268 deque->leftindex--;
269 deque->leftblock->data[deque->leftindex] = item;
270 TRIM(deque, deque_pop);
271 Py_RETURN_NONE;
272 }
273
274 PyDoc_STRVAR(appendleft_doc, "Add an element to the left side of the deque.");
275
276
277 /* Run an iterator to exhaustion. Shortcut for
278 the extend/extendleft methods when maxlen == 0. */
279 static PyObject*
consume_iterator(PyObject * it)280 consume_iterator(PyObject *it)
281 {
282 PyObject *item;
283
284 while ((item = PyIter_Next(it)) != NULL) {
285 Py_DECREF(item);
286 }
287 Py_DECREF(it);
288 if (PyErr_Occurred())
289 return NULL;
290 Py_RETURN_NONE;
291 }
292
293 static PyObject *
deque_extend(dequeobject * deque,PyObject * iterable)294 deque_extend(dequeobject *deque, PyObject *iterable)
295 {
296 PyObject *it, *item;
297
298 /* Handle case where id(deque) == id(iterable) */
299 if ((PyObject *)deque == iterable) {
300 PyObject *result;
301 PyObject *s = PySequence_List(iterable);
302 if (s == NULL)
303 return NULL;
304 result = deque_extend(deque, s);
305 Py_DECREF(s);
306 return result;
307 }
308
309 it = PyObject_GetIter(iterable);
310 if (it == NULL)
311 return NULL;
312
313 if (deque->maxlen == 0)
314 return consume_iterator(it);
315
316 while ((item = PyIter_Next(it)) != NULL) {
317 deque->state++;
318 if (deque->rightindex == BLOCKLEN-1) {
319 block *b = newblock(deque->rightblock, NULL,
320 deque->len);
321 if (b == NULL) {
322 Py_DECREF(item);
323 Py_DECREF(it);
324 return NULL;
325 }
326 assert(deque->rightblock->rightlink == NULL);
327 deque->rightblock->rightlink = b;
328 deque->rightblock = b;
329 deque->rightindex = -1;
330 }
331 deque->len++;
332 deque->rightindex++;
333 deque->rightblock->data[deque->rightindex] = item;
334 TRIM(deque, deque_popleft);
335 }
336 Py_DECREF(it);
337 if (PyErr_Occurred())
338 return NULL;
339 Py_RETURN_NONE;
340 }
341
342 PyDoc_STRVAR(extend_doc,
343 "Extend the right side of the deque with elements from the iterable");
344
345 static PyObject *
deque_extendleft(dequeobject * deque,PyObject * iterable)346 deque_extendleft(dequeobject *deque, PyObject *iterable)
347 {
348 PyObject *it, *item;
349
350 /* Handle case where id(deque) == id(iterable) */
351 if ((PyObject *)deque == iterable) {
352 PyObject *result;
353 PyObject *s = PySequence_List(iterable);
354 if (s == NULL)
355 return NULL;
356 result = deque_extendleft(deque, s);
357 Py_DECREF(s);
358 return result;
359 }
360
361 it = PyObject_GetIter(iterable);
362 if (it == NULL)
363 return NULL;
364
365 if (deque->maxlen == 0)
366 return consume_iterator(it);
367
368 while ((item = PyIter_Next(it)) != NULL) {
369 deque->state++;
370 if (deque->leftindex == 0) {
371 block *b = newblock(NULL, deque->leftblock,
372 deque->len);
373 if (b == NULL) {
374 Py_DECREF(item);
375 Py_DECREF(it);
376 return NULL;
377 }
378 assert(deque->leftblock->leftlink == NULL);
379 deque->leftblock->leftlink = b;
380 deque->leftblock = b;
381 deque->leftindex = BLOCKLEN;
382 }
383 deque->len++;
384 deque->leftindex--;
385 deque->leftblock->data[deque->leftindex] = item;
386 TRIM(deque, deque_pop);
387 }
388 Py_DECREF(it);
389 if (PyErr_Occurred())
390 return NULL;
391 Py_RETURN_NONE;
392 }
393
394 PyDoc_STRVAR(extendleft_doc,
395 "Extend the left side of the deque with elements from the iterable");
396
397 static PyObject *
deque_inplace_concat(dequeobject * deque,PyObject * other)398 deque_inplace_concat(dequeobject *deque, PyObject *other)
399 {
400 PyObject *result;
401
402 result = deque_extend(deque, other);
403 if (result == NULL)
404 return result;
405 Py_DECREF(result);
406 Py_INCREF(deque);
407 return (PyObject *)deque;
408 }
409
410 static int
_deque_rotate(dequeobject * deque,Py_ssize_t n)411 _deque_rotate(dequeobject *deque, Py_ssize_t n)
412 {
413 Py_ssize_t m, len=deque->len, halflen=len>>1;
414
415 if (len <= 1)
416 return 0;
417 if (n > halflen || n < -halflen) {
418 n %= len;
419 if (n > halflen)
420 n -= len;
421 else if (n < -halflen)
422 n += len;
423 }
424 assert(len > 1);
425 assert(-halflen <= n && n <= halflen);
426
427 deque->state++;
428 while (n > 0) {
429 if (deque->leftindex == 0) {
430 block *b = newblock(NULL, deque->leftblock, len);
431 if (b == NULL)
432 return -1;
433 assert(deque->leftblock->leftlink == NULL);
434 deque->leftblock->leftlink = b;
435 deque->leftblock = b;
436 deque->leftindex = BLOCKLEN;
437 }
438 assert(deque->leftindex > 0);
439
440 m = n;
441 if (m > deque->rightindex + 1)
442 m = deque->rightindex + 1;
443 if (m > deque->leftindex)
444 m = deque->leftindex;
445 assert (m > 0 && m <= len);
446 memcpy(&deque->leftblock->data[deque->leftindex - m],
447 &deque->rightblock->data[deque->rightindex + 1 - m],
448 m * sizeof(PyObject *));
449 deque->rightindex -= m;
450 deque->leftindex -= m;
451 n -= m;
452
453 if (deque->rightindex == -1) {
454 block *prevblock = deque->rightblock->leftlink;
455 assert(deque->rightblock != NULL);
456 assert(deque->leftblock != deque->rightblock);
457 freeblock(deque->rightblock);
458 prevblock->rightlink = NULL;
459 deque->rightblock = prevblock;
460 deque->rightindex = BLOCKLEN - 1;
461 }
462 }
463 while (n < 0) {
464 if (deque->rightindex == BLOCKLEN - 1) {
465 block *b = newblock(deque->rightblock, NULL, len);
466 if (b == NULL)
467 return -1;
468 assert(deque->rightblock->rightlink == NULL);
469 deque->rightblock->rightlink = b;
470 deque->rightblock = b;
471 deque->rightindex = -1;
472 }
473 assert (deque->rightindex < BLOCKLEN - 1);
474
475 m = -n;
476 if (m > BLOCKLEN - deque->leftindex)
477 m = BLOCKLEN - deque->leftindex;
478 if (m > BLOCKLEN - 1 - deque->rightindex)
479 m = BLOCKLEN - 1 - deque->rightindex;
480 assert (m > 0 && m <= len);
481 memcpy(&deque->rightblock->data[deque->rightindex + 1],
482 &deque->leftblock->data[deque->leftindex],
483 m * sizeof(PyObject *));
484 deque->leftindex += m;
485 deque->rightindex += m;
486 n += m;
487
488 if (deque->leftindex == BLOCKLEN) {
489 block *nextblock = deque->leftblock->rightlink;
490 assert(deque->leftblock != deque->rightblock);
491 freeblock(deque->leftblock);
492 assert(nextblock != NULL);
493 nextblock->leftlink = NULL;
494 deque->leftblock = nextblock;
495 deque->leftindex = 0;
496 }
497 }
498 return 0;
499 }
500
501 static PyObject *
deque_rotate(dequeobject * deque,PyObject * args)502 deque_rotate(dequeobject *deque, PyObject *args)
503 {
504 Py_ssize_t n=1;
505
506 if (!PyArg_ParseTuple(args, "|n:rotate", &n))
507 return NULL;
508 if (_deque_rotate(deque, n) == 0)
509 Py_RETURN_NONE;
510 return NULL;
511 }
512
513 PyDoc_STRVAR(rotate_doc,
514 "Rotate the deque n steps to the right (default n=1). If n is negative, rotates left.");
515
516 static PyObject *
deque_reverse(dequeobject * deque,PyObject * unused)517 deque_reverse(dequeobject *deque, PyObject *unused)
518 {
519 block *leftblock = deque->leftblock;
520 block *rightblock = deque->rightblock;
521 Py_ssize_t leftindex = deque->leftindex;
522 Py_ssize_t rightindex = deque->rightindex;
523 Py_ssize_t n = (deque->len)/2;
524 Py_ssize_t i;
525 PyObject *tmp;
526
527 for (i=0 ; i<n ; i++) {
528 /* Validate that pointers haven't met in the middle */
529 assert(leftblock != rightblock || leftindex < rightindex);
530
531 /* Swap */
532 tmp = leftblock->data[leftindex];
533 leftblock->data[leftindex] = rightblock->data[rightindex];
534 rightblock->data[rightindex] = tmp;
535
536 /* Advance left block/index pair */
537 leftindex++;
538 if (leftindex == BLOCKLEN) {
539 if (leftblock->rightlink == NULL)
540 break;
541 leftblock = leftblock->rightlink;
542 leftindex = 0;
543 }
544
545 /* Step backwards with the right block/index pair */
546 rightindex--;
547 if (rightindex == -1) {
548 if (rightblock->leftlink == NULL)
549 break;
550 rightblock = rightblock->leftlink;
551 rightindex = BLOCKLEN - 1;
552 }
553 }
554 Py_RETURN_NONE;
555 }
556
557 PyDoc_STRVAR(reverse_doc,
558 "D.reverse() -- reverse *IN PLACE*");
559
560 static PyObject *
deque_count(dequeobject * deque,PyObject * v)561 deque_count(dequeobject *deque, PyObject *v)
562 {
563 block *leftblock = deque->leftblock;
564 Py_ssize_t leftindex = deque->leftindex;
565 Py_ssize_t n = deque->len;
566 Py_ssize_t i;
567 Py_ssize_t count = 0;
568 PyObject *item;
569 long start_state = deque->state;
570 int cmp;
571
572 for (i=0 ; i<n ; i++) {
573 item = leftblock->data[leftindex];
574 cmp = PyObject_RichCompareBool(item, v, Py_EQ);
575 if (cmp > 0)
576 count++;
577 else if (cmp < 0)
578 return NULL;
579
580 if (start_state != deque->state) {
581 PyErr_SetString(PyExc_RuntimeError,
582 "deque mutated during iteration");
583 return NULL;
584 }
585
586 /* Advance left block/index pair */
587 leftindex++;
588 if (leftindex == BLOCKLEN) {
589 if (leftblock->rightlink == NULL) /* can occur when i==n-1 */
590 break;
591 leftblock = leftblock->rightlink;
592 leftindex = 0;
593 }
594 }
595 return PyInt_FromSsize_t(count);
596 }
597
598 PyDoc_STRVAR(count_doc,
599 "D.count(value) -> integer -- return number of occurrences of value");
600
601 static Py_ssize_t
deque_len(dequeobject * deque)602 deque_len(dequeobject *deque)
603 {
604 return deque->len;
605 }
606
607 static PyObject *
deque_remove(dequeobject * deque,PyObject * value)608 deque_remove(dequeobject *deque, PyObject *value)
609 {
610 Py_ssize_t i, n=deque->len;
611
612 for (i=0 ; i<n ; i++) {
613 PyObject *item = deque->leftblock->data[deque->leftindex];
614 int cmp = PyObject_RichCompareBool(item, value, Py_EQ);
615
616 if (deque->len != n) {
617 PyErr_SetString(PyExc_IndexError,
618 "deque mutated during remove().");
619 return NULL;
620 }
621 if (cmp > 0) {
622 PyObject *tgt = deque_popleft(deque, NULL);
623 assert (tgt != NULL);
624 if (_deque_rotate(deque, i))
625 return NULL;
626 Py_DECREF(tgt);
627 Py_RETURN_NONE;
628 }
629 else if (cmp < 0) {
630 _deque_rotate(deque, i);
631 return NULL;
632 }
633 _deque_rotate(deque, -1);
634 }
635 PyErr_SetString(PyExc_ValueError, "deque.remove(x): x not in deque");
636 return NULL;
637 }
638
639 PyDoc_STRVAR(remove_doc,
640 "D.remove(value) -- remove first occurrence of value.");
641
642 static int
deque_clear(dequeobject * deque)643 deque_clear(dequeobject *deque)
644 {
645 block *b;
646 block *prevblock;
647 block *leftblock;
648 Py_ssize_t leftindex;
649 Py_ssize_t n;
650 PyObject *item;
651
652 if (deque->len == 0)
653 return 0;
654
655 /* During the process of clearing a deque, decrefs can cause the
656 deque to mutate. To avoid fatal confusion, we have to make the
657 deque empty before clearing the blocks and never refer to
658 anything via deque->ref while clearing. (This is the same
659 technique used for clearing lists, sets, and dicts.)
660
661 Making the deque empty requires allocating a new empty block. In
662 the unlikely event that memory is full, we fall back to an
663 alternate method that doesn't require a new block. Repeating
664 pops in a while-loop is slower, possibly re-entrant (and a clever
665 adversary could cause it to never terminate).
666 */
667
668 b = newblock(NULL, NULL, 0);
669 if (b == NULL) {
670 PyErr_Clear();
671 goto alternate_method;
672 }
673
674 /* Remember the old size, leftblock, and leftindex */
675 leftblock = deque->leftblock;
676 leftindex = deque->leftindex;
677 n = deque->len;
678
679 /* Set the deque to be empty using the newly allocated block */
680 deque->len = 0;
681 deque->leftblock = b;
682 deque->rightblock = b;
683 deque->leftindex = CENTER + 1;
684 deque->rightindex = CENTER;
685 deque->state++;
686
687 /* Now the old size, leftblock, and leftindex are disconnected from
688 the empty deque and we can use them to decref the pointers.
689 */
690 while (n--) {
691 item = leftblock->data[leftindex];
692 Py_DECREF(item);
693 leftindex++;
694 if (leftindex == BLOCKLEN && n) {
695 assert(leftblock->rightlink != NULL);
696 prevblock = leftblock;
697 leftblock = leftblock->rightlink;
698 leftindex = 0;
699 freeblock(prevblock);
700 }
701 }
702 assert(leftblock->rightlink == NULL);
703 freeblock(leftblock);
704 return 0;
705
706 alternate_method:
707 while (deque->len) {
708 item = deque_pop(deque, NULL);
709 assert (item != NULL);
710 Py_DECREF(item);
711 }
712 return 0;
713 }
714
715 static PyObject *
deque_item(dequeobject * deque,Py_ssize_t i)716 deque_item(dequeobject *deque, Py_ssize_t i)
717 {
718 block *b;
719 PyObject *item;
720 Py_ssize_t n, index=i;
721
722 if (i < 0 || i >= deque->len) {
723 PyErr_SetString(PyExc_IndexError,
724 "deque index out of range");
725 return NULL;
726 }
727
728 if (i == 0) {
729 i = deque->leftindex;
730 b = deque->leftblock;
731 } else if (i == deque->len - 1) {
732 i = deque->rightindex;
733 b = deque->rightblock;
734 } else {
735 i += deque->leftindex;
736 n = i / BLOCKLEN;
737 i %= BLOCKLEN;
738 if (index < (deque->len >> 1)) {
739 b = deque->leftblock;
740 while (n--)
741 b = b->rightlink;
742 } else {
743 n = (deque->leftindex + deque->len - 1) / BLOCKLEN - n;
744 b = deque->rightblock;
745 while (n--)
746 b = b->leftlink;
747 }
748 }
749 item = b->data[i];
750 Py_INCREF(item);
751 return item;
752 }
753
754 /* delitem() implemented in terms of rotate for simplicity and reasonable
755 performance near the end points. If for some reason this method becomes
756 popular, it is not hard to re-implement this using direct data movement
757 (similar to code in list slice assignment) and achieve a two or threefold
758 performance boost.
759 */
760
761 static int
deque_del_item(dequeobject * deque,Py_ssize_t i)762 deque_del_item(dequeobject *deque, Py_ssize_t i)
763 {
764 PyObject *item;
765 int rv;
766
767 assert (i >= 0 && i < deque->len);
768 if (_deque_rotate(deque, -i))
769 return -1;
770 item = deque_popleft(deque, NULL);
771 rv = _deque_rotate(deque, i);
772 assert (item != NULL);
773 Py_DECREF(item);
774 return rv;
775 }
776
777 static int
deque_ass_item(dequeobject * deque,Py_ssize_t i,PyObject * v)778 deque_ass_item(dequeobject *deque, Py_ssize_t i, PyObject *v)
779 {
780 PyObject *old_value;
781 block *b;
782 Py_ssize_t n, len=deque->len, halflen=(len+1)>>1, index=i;
783
784 if (i < 0 || i >= len) {
785 PyErr_SetString(PyExc_IndexError,
786 "deque index out of range");
787 return -1;
788 }
789 if (v == NULL)
790 return deque_del_item(deque, i);
791
792 i += deque->leftindex;
793 n = i / BLOCKLEN;
794 i %= BLOCKLEN;
795 if (index <= halflen) {
796 b = deque->leftblock;
797 while (n--)
798 b = b->rightlink;
799 } else {
800 n = (deque->leftindex + len - 1) / BLOCKLEN - n;
801 b = deque->rightblock;
802 while (n--)
803 b = b->leftlink;
804 }
805 Py_INCREF(v);
806 old_value = b->data[i];
807 b->data[i] = v;
808 Py_DECREF(old_value);
809 return 0;
810 }
811
812 static PyObject *
deque_clearmethod(dequeobject * deque)813 deque_clearmethod(dequeobject *deque)
814 {
815 deque_clear(deque);
816 Py_RETURN_NONE;
817 }
818
819 PyDoc_STRVAR(clear_doc, "Remove all elements from the deque.");
820
821 static void
deque_dealloc(dequeobject * deque)822 deque_dealloc(dequeobject *deque)
823 {
824 PyObject_GC_UnTrack(deque);
825 if (deque->weakreflist != NULL)
826 PyObject_ClearWeakRefs((PyObject *) deque);
827 if (deque->leftblock != NULL) {
828 deque_clear(deque);
829 assert(deque->leftblock != NULL);
830 freeblock(deque->leftblock);
831 }
832 deque->leftblock = NULL;
833 deque->rightblock = NULL;
834 Py_TYPE(deque)->tp_free(deque);
835 }
836
837 static int
deque_traverse(dequeobject * deque,visitproc visit,void * arg)838 deque_traverse(dequeobject *deque, visitproc visit, void *arg)
839 {
840 block *b;
841 PyObject *item;
842 Py_ssize_t index;
843 Py_ssize_t indexlo = deque->leftindex;
844
845 for (b = deque->leftblock; b != NULL; b = b->rightlink) {
846 const Py_ssize_t indexhi = b == deque->rightblock ?
847 deque->rightindex :
848 BLOCKLEN - 1;
849
850 for (index = indexlo; index <= indexhi; ++index) {
851 item = b->data[index];
852 Py_VISIT(item);
853 }
854 indexlo = 0;
855 }
856 return 0;
857 }
858
859 static PyObject *
deque_copy(PyObject * deque)860 deque_copy(PyObject *deque)
861 {
862 PyObject *result;
863 if (((dequeobject *)deque)->maxlen == -1)
864 result = PyObject_CallFunction((PyObject *)(Py_TYPE(deque)), "O", deque, NULL);
865 else
866 result = PyObject_CallFunction((PyObject *)(Py_TYPE(deque)), "Oi",
867 deque, ((dequeobject *)deque)->maxlen, NULL);
868 if (result != NULL && !PyObject_TypeCheck(result, &deque_type)) {
869 PyErr_Format(PyExc_TypeError,
870 "%.200s() must return a deque, not %.200s",
871 Py_TYPE(deque)->tp_name, Py_TYPE(result)->tp_name);
872 Py_DECREF(result);
873 return NULL;
874 }
875 return result;
876 }
877
878 PyDoc_STRVAR(copy_doc, "Return a shallow copy of a deque.");
879
880 static PyObject *
deque_reduce(dequeobject * deque)881 deque_reduce(dequeobject *deque)
882 {
883 PyObject *dict, *result, *aslist;
884
885 dict = PyObject_GetAttrString((PyObject *)deque, "__dict__");
886 if (dict == NULL)
887 PyErr_Clear();
888 aslist = PySequence_List((PyObject *)deque);
889 if (aslist == NULL) {
890 Py_XDECREF(dict);
891 return NULL;
892 }
893 if (dict == NULL) {
894 if (deque->maxlen == -1)
895 result = Py_BuildValue("O(O)", Py_TYPE(deque), aslist);
896 else
897 result = Py_BuildValue("O(On)", Py_TYPE(deque), aslist, deque->maxlen);
898 } else {
899 if (deque->maxlen == -1)
900 result = Py_BuildValue("O(OO)O", Py_TYPE(deque), aslist, Py_None, dict);
901 else
902 result = Py_BuildValue("O(On)O", Py_TYPE(deque), aslist, deque->maxlen, dict);
903 }
904 Py_XDECREF(dict);
905 Py_DECREF(aslist);
906 return result;
907 }
908
909 PyDoc_STRVAR(reduce_doc, "Return state information for pickling.");
910
911 static PyObject *
deque_repr(PyObject * deque)912 deque_repr(PyObject *deque)
913 {
914 PyObject *aslist, *result, *fmt;
915 int i;
916
917 i = Py_ReprEnter(deque);
918 if (i != 0) {
919 if (i < 0)
920 return NULL;
921 return PyString_FromString("[...]");
922 }
923
924 aslist = PySequence_List(deque);
925 if (aslist == NULL) {
926 Py_ReprLeave(deque);
927 return NULL;
928 }
929 if (((dequeobject *)deque)->maxlen != -1)
930 fmt = PyString_FromFormat("deque(%%r, maxlen=%zd)",
931 ((dequeobject *)deque)->maxlen);
932 else
933 fmt = PyString_FromString("deque(%r)");
934 if (fmt == NULL) {
935 Py_DECREF(aslist);
936 Py_ReprLeave(deque);
937 return NULL;
938 }
939 result = PyString_Format(fmt, aslist);
940 Py_DECREF(fmt);
941 Py_DECREF(aslist);
942 Py_ReprLeave(deque);
943 return result;
944 }
945
946 static int
deque_tp_print(PyObject * deque,FILE * fp,int flags)947 deque_tp_print(PyObject *deque, FILE *fp, int flags)
948 {
949 PyObject *it, *item;
950 char *emit = ""; /* No separator emitted on first pass */
951 char *separator = ", ";
952 int i;
953
954 i = Py_ReprEnter(deque);
955 if (i != 0) {
956 if (i < 0)
957 return i;
958 Py_BEGIN_ALLOW_THREADS
959 fputs("[...]", fp);
960 Py_END_ALLOW_THREADS
961 return 0;
962 }
963
964 it = PyObject_GetIter(deque);
965 if (it == NULL)
966 return -1;
967
968 Py_BEGIN_ALLOW_THREADS
969 fputs("deque([", fp);
970 Py_END_ALLOW_THREADS
971 while ((item = PyIter_Next(it)) != NULL) {
972 Py_BEGIN_ALLOW_THREADS
973 fputs(emit, fp);
974 Py_END_ALLOW_THREADS
975 emit = separator;
976 if (PyObject_Print(item, fp, 0) != 0) {
977 Py_DECREF(item);
978 Py_DECREF(it);
979 Py_ReprLeave(deque);
980 return -1;
981 }
982 Py_DECREF(item);
983 }
984 Py_ReprLeave(deque);
985 Py_DECREF(it);
986 if (PyErr_Occurred())
987 return -1;
988
989 Py_BEGIN_ALLOW_THREADS
990 if (((dequeobject *)deque)->maxlen == -1)
991 fputs("])", fp);
992 else
993 fprintf(fp, "], maxlen=%" PY_FORMAT_SIZE_T "d)", ((dequeobject *)deque)->maxlen);
994 Py_END_ALLOW_THREADS
995 return 0;
996 }
997
998 static PyObject *
deque_richcompare(PyObject * v,PyObject * w,int op)999 deque_richcompare(PyObject *v, PyObject *w, int op)
1000 {
1001 PyObject *it1=NULL, *it2=NULL, *x, *y;
1002 Py_ssize_t vs, ws;
1003 int b, cmp=-1;
1004
1005 if (!PyObject_TypeCheck(v, &deque_type) ||
1006 !PyObject_TypeCheck(w, &deque_type)) {
1007 Py_INCREF(Py_NotImplemented);
1008 return Py_NotImplemented;
1009 }
1010
1011 /* Shortcuts */
1012 vs = ((dequeobject *)v)->len;
1013 ws = ((dequeobject *)w)->len;
1014 if (op == Py_EQ) {
1015 if (v == w)
1016 Py_RETURN_TRUE;
1017 if (vs != ws)
1018 Py_RETURN_FALSE;
1019 }
1020 if (op == Py_NE) {
1021 if (v == w)
1022 Py_RETURN_FALSE;
1023 if (vs != ws)
1024 Py_RETURN_TRUE;
1025 }
1026
1027 /* Search for the first index where items are different */
1028 it1 = PyObject_GetIter(v);
1029 if (it1 == NULL)
1030 goto done;
1031 it2 = PyObject_GetIter(w);
1032 if (it2 == NULL)
1033 goto done;
1034 for (;;) {
1035 x = PyIter_Next(it1);
1036 if (x == NULL && PyErr_Occurred())
1037 goto done;
1038 y = PyIter_Next(it2);
1039 if (x == NULL || y == NULL)
1040 break;
1041 b = PyObject_RichCompareBool(x, y, Py_EQ);
1042 if (b == 0) {
1043 cmp = PyObject_RichCompareBool(x, y, op);
1044 Py_DECREF(x);
1045 Py_DECREF(y);
1046 goto done;
1047 }
1048 Py_DECREF(x);
1049 Py_DECREF(y);
1050 if (b == -1)
1051 goto done;
1052 }
1053 /* We reached the end of one deque or both */
1054 Py_XDECREF(x);
1055 Py_XDECREF(y);
1056 if (PyErr_Occurred())
1057 goto done;
1058 switch (op) {
1059 case Py_LT: cmp = y != NULL; break; /* if w was longer */
1060 case Py_LE: cmp = x == NULL; break; /* if v was not longer */
1061 case Py_EQ: cmp = x == y; break; /* if we reached the end of both */
1062 case Py_NE: cmp = x != y; break; /* if one deque continues */
1063 case Py_GT: cmp = x != NULL; break; /* if v was longer */
1064 case Py_GE: cmp = y == NULL; break; /* if w was not longer */
1065 }
1066
1067 done:
1068 Py_XDECREF(it1);
1069 Py_XDECREF(it2);
1070 if (cmp == 1)
1071 Py_RETURN_TRUE;
1072 if (cmp == 0)
1073 Py_RETURN_FALSE;
1074 return NULL;
1075 }
1076
1077 static int
deque_init(dequeobject * deque,PyObject * args,PyObject * kwdargs)1078 deque_init(dequeobject *deque, PyObject *args, PyObject *kwdargs)
1079 {
1080 PyObject *iterable = NULL;
1081 PyObject *maxlenobj = NULL;
1082 Py_ssize_t maxlen = -1;
1083 char *kwlist[] = {"iterable", "maxlen", 0};
1084
1085 if (!PyArg_ParseTupleAndKeywords(args, kwdargs, "|OO:deque", kwlist, &iterable, &maxlenobj))
1086 return -1;
1087 if (maxlenobj != NULL && maxlenobj != Py_None) {
1088 maxlen = PyInt_AsSsize_t(maxlenobj);
1089 if (maxlen == -1 && PyErr_Occurred())
1090 return -1;
1091 if (maxlen < 0) {
1092 PyErr_SetString(PyExc_ValueError, "maxlen must be non-negative");
1093 return -1;
1094 }
1095 }
1096 deque->maxlen = maxlen;
1097 if (deque->len > 0)
1098 deque_clear(deque);
1099 if (iterable != NULL) {
1100 PyObject *rv = deque_extend(deque, iterable);
1101 if (rv == NULL)
1102 return -1;
1103 Py_DECREF(rv);
1104 }
1105 return 0;
1106 }
1107
1108 static PyObject *
deque_sizeof(dequeobject * deque,void * unused)1109 deque_sizeof(dequeobject *deque, void *unused)
1110 {
1111 Py_ssize_t res;
1112 Py_ssize_t blocks;
1113
1114 res = _PyObject_SIZE(Py_TYPE(deque));
1115 blocks = (deque->leftindex + deque->len + BLOCKLEN - 1) / BLOCKLEN;
1116 assert(deque->leftindex + deque->len - 1 ==
1117 (blocks - 1) * BLOCKLEN + deque->rightindex);
1118 res += blocks * sizeof(block);
1119 return PyLong_FromSsize_t(res);
1120 }
1121
1122 PyDoc_STRVAR(sizeof_doc,
1123 "D.__sizeof__() -- size of D in memory, in bytes");
1124
1125 static PyObject *
deque_get_maxlen(dequeobject * deque)1126 deque_get_maxlen(dequeobject *deque)
1127 {
1128 if (deque->maxlen == -1)
1129 Py_RETURN_NONE;
1130 return PyInt_FromSsize_t(deque->maxlen);
1131 }
1132
1133 static PyGetSetDef deque_getset[] = {
1134 {"maxlen", (getter)deque_get_maxlen, (setter)NULL,
1135 "maximum size of a deque or None if unbounded"},
1136 {0}
1137 };
1138
1139 static PySequenceMethods deque_as_sequence = {
1140 (lenfunc)deque_len, /* sq_length */
1141 0, /* sq_concat */
1142 0, /* sq_repeat */
1143 (ssizeargfunc)deque_item, /* sq_item */
1144 0, /* sq_slice */
1145 (ssizeobjargproc)deque_ass_item, /* sq_ass_item */
1146 0, /* sq_ass_slice */
1147 0, /* sq_contains */
1148 (binaryfunc)deque_inplace_concat, /* sq_inplace_concat */
1149 0, /* sq_inplace_repeat */
1150
1151 };
1152
1153 /* deque object ********************************************************/
1154
1155 static PyObject *deque_iter(dequeobject *deque);
1156 static PyObject *deque_reviter(dequeobject *deque);
1157 PyDoc_STRVAR(reversed_doc,
1158 "D.__reversed__() -- return a reverse iterator over the deque");
1159
1160 static PyMethodDef deque_methods[] = {
1161 {"append", (PyCFunction)deque_append,
1162 METH_O, append_doc},
1163 {"appendleft", (PyCFunction)deque_appendleft,
1164 METH_O, appendleft_doc},
1165 {"clear", (PyCFunction)deque_clearmethod,
1166 METH_NOARGS, clear_doc},
1167 {"__copy__", (PyCFunction)deque_copy,
1168 METH_NOARGS, copy_doc},
1169 {"count", (PyCFunction)deque_count,
1170 METH_O, count_doc},
1171 {"extend", (PyCFunction)deque_extend,
1172 METH_O, extend_doc},
1173 {"extendleft", (PyCFunction)deque_extendleft,
1174 METH_O, extendleft_doc},
1175 {"pop", (PyCFunction)deque_pop,
1176 METH_NOARGS, pop_doc},
1177 {"popleft", (PyCFunction)deque_popleft,
1178 METH_NOARGS, popleft_doc},
1179 {"__reduce__", (PyCFunction)deque_reduce,
1180 METH_NOARGS, reduce_doc},
1181 {"remove", (PyCFunction)deque_remove,
1182 METH_O, remove_doc},
1183 {"__reversed__", (PyCFunction)deque_reviter,
1184 METH_NOARGS, reversed_doc},
1185 {"reverse", (PyCFunction)deque_reverse,
1186 METH_NOARGS, reverse_doc},
1187 {"rotate", (PyCFunction)deque_rotate,
1188 METH_VARARGS, rotate_doc},
1189 {"__sizeof__", (PyCFunction)deque_sizeof,
1190 METH_NOARGS, sizeof_doc},
1191 {NULL, NULL} /* sentinel */
1192 };
1193
1194 PyDoc_STRVAR(deque_doc,
1195 "deque([iterable[, maxlen]]) --> deque object\n\
1196 \n\
1197 Build an ordered collection with optimized access from its endpoints.");
1198
1199 static PyTypeObject deque_type = {
1200 PyVarObject_HEAD_INIT(NULL, 0)
1201 "collections.deque", /* tp_name */
1202 sizeof(dequeobject), /* tp_basicsize */
1203 0, /* tp_itemsize */
1204 /* methods */
1205 (destructor)deque_dealloc, /* tp_dealloc */
1206 deque_tp_print, /* tp_print */
1207 0, /* tp_getattr */
1208 0, /* tp_setattr */
1209 0, /* tp_compare */
1210 deque_repr, /* tp_repr */
1211 0, /* tp_as_number */
1212 &deque_as_sequence, /* tp_as_sequence */
1213 0, /* tp_as_mapping */
1214 (hashfunc)PyObject_HashNotImplemented, /* tp_hash */
1215 0, /* tp_call */
1216 0, /* tp_str */
1217 PyObject_GenericGetAttr, /* tp_getattro */
1218 0, /* tp_setattro */
1219 0, /* tp_as_buffer */
1220 Py_TPFLAGS_DEFAULT | Py_TPFLAGS_BASETYPE | Py_TPFLAGS_HAVE_GC |
1221 Py_TPFLAGS_HAVE_WEAKREFS, /* tp_flags */
1222 deque_doc, /* tp_doc */
1223 (traverseproc)deque_traverse, /* tp_traverse */
1224 (inquiry)deque_clear, /* tp_clear */
1225 (richcmpfunc)deque_richcompare, /* tp_richcompare */
1226 offsetof(dequeobject, weakreflist), /* tp_weaklistoffset*/
1227 (getiterfunc)deque_iter, /* tp_iter */
1228 0, /* tp_iternext */
1229 deque_methods, /* tp_methods */
1230 0, /* tp_members */
1231 deque_getset, /* tp_getset */
1232 0, /* tp_base */
1233 0, /* tp_dict */
1234 0, /* tp_descr_get */
1235 0, /* tp_descr_set */
1236 0, /* tp_dictoffset */
1237 (initproc)deque_init, /* tp_init */
1238 PyType_GenericAlloc, /* tp_alloc */
1239 deque_new, /* tp_new */
1240 PyObject_GC_Del, /* tp_free */
1241 };
1242
1243 /*********************** Deque Iterator **************************/
1244
1245 typedef struct {
1246 PyObject_HEAD
1247 Py_ssize_t index;
1248 block *b;
1249 dequeobject *deque;
1250 long state; /* state when the iterator is created */
1251 Py_ssize_t counter; /* number of items remaining for iteration */
1252 } dequeiterobject;
1253
1254 static PyTypeObject dequeiter_type;
1255
1256 static PyObject *
deque_iter(dequeobject * deque)1257 deque_iter(dequeobject *deque)
1258 {
1259 dequeiterobject *it;
1260
1261 it = PyObject_GC_New(dequeiterobject, &dequeiter_type);
1262 if (it == NULL)
1263 return NULL;
1264 it->b = deque->leftblock;
1265 it->index = deque->leftindex;
1266 Py_INCREF(deque);
1267 it->deque = deque;
1268 it->state = deque->state;
1269 it->counter = deque->len;
1270 PyObject_GC_Track(it);
1271 return (PyObject *)it;
1272 }
1273
1274 static int
dequeiter_traverse(dequeiterobject * dio,visitproc visit,void * arg)1275 dequeiter_traverse(dequeiterobject *dio, visitproc visit, void *arg)
1276 {
1277 Py_VISIT(dio->deque);
1278 return 0;
1279 }
1280
1281 static void
dequeiter_dealloc(dequeiterobject * dio)1282 dequeiter_dealloc(dequeiterobject *dio)
1283 {
1284 /* bpo-31095: UnTrack is needed before calling any callbacks */
1285 PyObject_GC_UnTrack(dio);
1286 Py_XDECREF(dio->deque);
1287 PyObject_GC_Del(dio);
1288 }
1289
1290 static PyObject *
dequeiter_next(dequeiterobject * it)1291 dequeiter_next(dequeiterobject *it)
1292 {
1293 PyObject *item;
1294
1295 if (it->deque->state != it->state) {
1296 it->counter = 0;
1297 PyErr_SetString(PyExc_RuntimeError,
1298 "deque mutated during iteration");
1299 return NULL;
1300 }
1301 if (it->counter == 0)
1302 return NULL;
1303 assert (!(it->b == it->deque->rightblock &&
1304 it->index > it->deque->rightindex));
1305
1306 item = it->b->data[it->index];
1307 it->index++;
1308 it->counter--;
1309 if (it->index == BLOCKLEN && it->counter > 0) {
1310 assert (it->b->rightlink != NULL);
1311 it->b = it->b->rightlink;
1312 it->index = 0;
1313 }
1314 Py_INCREF(item);
1315 return item;
1316 }
1317
1318 static PyObject *
dequeiter_len(dequeiterobject * it)1319 dequeiter_len(dequeiterobject *it)
1320 {
1321 return PyInt_FromLong(it->counter);
1322 }
1323
1324 PyDoc_STRVAR(length_hint_doc, "Private method returning an estimate of len(list(it)).");
1325
1326 static PyMethodDef dequeiter_methods[] = {
1327 {"__length_hint__", (PyCFunction)dequeiter_len, METH_NOARGS, length_hint_doc},
1328 {NULL, NULL} /* sentinel */
1329 };
1330
1331 static PyTypeObject dequeiter_type = {
1332 PyVarObject_HEAD_INIT(NULL, 0)
1333 "deque_iterator", /* tp_name */
1334 sizeof(dequeiterobject), /* tp_basicsize */
1335 0, /* tp_itemsize */
1336 /* methods */
1337 (destructor)dequeiter_dealloc, /* tp_dealloc */
1338 0, /* tp_print */
1339 0, /* tp_getattr */
1340 0, /* tp_setattr */
1341 0, /* tp_compare */
1342 0, /* tp_repr */
1343 0, /* tp_as_number */
1344 0, /* tp_as_sequence */
1345 0, /* tp_as_mapping */
1346 0, /* tp_hash */
1347 0, /* tp_call */
1348 0, /* tp_str */
1349 PyObject_GenericGetAttr, /* tp_getattro */
1350 0, /* tp_setattro */
1351 0, /* tp_as_buffer */
1352 Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC,/* tp_flags */
1353 0, /* tp_doc */
1354 (traverseproc)dequeiter_traverse, /* tp_traverse */
1355 0, /* tp_clear */
1356 0, /* tp_richcompare */
1357 0, /* tp_weaklistoffset */
1358 PyObject_SelfIter, /* tp_iter */
1359 (iternextfunc)dequeiter_next, /* tp_iternext */
1360 dequeiter_methods, /* tp_methods */
1361 0,
1362 };
1363
1364 /*********************** Deque Reverse Iterator **************************/
1365
1366 static PyTypeObject dequereviter_type;
1367
1368 static PyObject *
deque_reviter(dequeobject * deque)1369 deque_reviter(dequeobject *deque)
1370 {
1371 dequeiterobject *it;
1372
1373 it = PyObject_GC_New(dequeiterobject, &dequereviter_type);
1374 if (it == NULL)
1375 return NULL;
1376 it->b = deque->rightblock;
1377 it->index = deque->rightindex;
1378 Py_INCREF(deque);
1379 it->deque = deque;
1380 it->state = deque->state;
1381 it->counter = deque->len;
1382 PyObject_GC_Track(it);
1383 return (PyObject *)it;
1384 }
1385
1386 static PyObject *
dequereviter_next(dequeiterobject * it)1387 dequereviter_next(dequeiterobject *it)
1388 {
1389 PyObject *item;
1390 if (it->counter == 0)
1391 return NULL;
1392
1393 if (it->deque->state != it->state) {
1394 it->counter = 0;
1395 PyErr_SetString(PyExc_RuntimeError,
1396 "deque mutated during iteration");
1397 return NULL;
1398 }
1399 assert (!(it->b == it->deque->leftblock &&
1400 it->index < it->deque->leftindex));
1401
1402 item = it->b->data[it->index];
1403 it->index--;
1404 it->counter--;
1405 if (it->index == -1 && it->counter > 0) {
1406 assert (it->b->leftlink != NULL);
1407 it->b = it->b->leftlink;
1408 it->index = BLOCKLEN - 1;
1409 }
1410 Py_INCREF(item);
1411 return item;
1412 }
1413
1414 static PyTypeObject dequereviter_type = {
1415 PyVarObject_HEAD_INIT(NULL, 0)
1416 "deque_reverse_iterator", /* tp_name */
1417 sizeof(dequeiterobject), /* tp_basicsize */
1418 0, /* tp_itemsize */
1419 /* methods */
1420 (destructor)dequeiter_dealloc, /* tp_dealloc */
1421 0, /* tp_print */
1422 0, /* tp_getattr */
1423 0, /* tp_setattr */
1424 0, /* tp_compare */
1425 0, /* tp_repr */
1426 0, /* tp_as_number */
1427 0, /* tp_as_sequence */
1428 0, /* tp_as_mapping */
1429 0, /* tp_hash */
1430 0, /* tp_call */
1431 0, /* tp_str */
1432 PyObject_GenericGetAttr, /* tp_getattro */
1433 0, /* tp_setattro */
1434 0, /* tp_as_buffer */
1435 Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC,/* tp_flags */
1436 0, /* tp_doc */
1437 (traverseproc)dequeiter_traverse, /* tp_traverse */
1438 0, /* tp_clear */
1439 0, /* tp_richcompare */
1440 0, /* tp_weaklistoffset */
1441 PyObject_SelfIter, /* tp_iter */
1442 (iternextfunc)dequereviter_next, /* tp_iternext */
1443 dequeiter_methods, /* tp_methods */
1444 0,
1445 };
1446
1447 /* defaultdict type *********************************************************/
1448
1449 typedef struct {
1450 PyDictObject dict;
1451 PyObject *default_factory;
1452 } defdictobject;
1453
1454 static PyTypeObject defdict_type; /* Forward */
1455
1456 PyDoc_STRVAR(defdict_missing_doc,
1457 "__missing__(key) # Called by __getitem__ for missing key; pseudo-code:\n\
1458 if self.default_factory is None: raise KeyError((key,))\n\
1459 self[key] = value = self.default_factory()\n\
1460 return value\n\
1461 ");
1462
1463 static PyObject *
defdict_missing(defdictobject * dd,PyObject * key)1464 defdict_missing(defdictobject *dd, PyObject *key)
1465 {
1466 PyObject *factory = dd->default_factory;
1467 PyObject *value;
1468 if (factory == NULL || factory == Py_None) {
1469 /* XXX Call dict.__missing__(key) */
1470 PyObject *tup;
1471 tup = PyTuple_Pack(1, key);
1472 if (!tup) return NULL;
1473 PyErr_SetObject(PyExc_KeyError, tup);
1474 Py_DECREF(tup);
1475 return NULL;
1476 }
1477 value = PyEval_CallObject(factory, NULL);
1478 if (value == NULL)
1479 return value;
1480 if (PyObject_SetItem((PyObject *)dd, key, value) < 0) {
1481 Py_DECREF(value);
1482 return NULL;
1483 }
1484 return value;
1485 }
1486
1487 PyDoc_STRVAR(defdict_copy_doc, "D.copy() -> a shallow copy of D.");
1488
1489 static PyObject *
defdict_copy(defdictobject * dd)1490 defdict_copy(defdictobject *dd)
1491 {
1492 /* This calls the object's class. That only works for subclasses
1493 whose class constructor has the same signature. Subclasses that
1494 define a different constructor signature must override copy().
1495 */
1496
1497 if (dd->default_factory == NULL)
1498 return PyObject_CallFunctionObjArgs((PyObject*)Py_TYPE(dd), Py_None, dd, NULL);
1499 return PyObject_CallFunctionObjArgs((PyObject*)Py_TYPE(dd),
1500 dd->default_factory, dd, NULL);
1501 }
1502
1503 static PyObject *
defdict_reduce(defdictobject * dd)1504 defdict_reduce(defdictobject *dd)
1505 {
1506 /* __reduce__ must return a 5-tuple as follows:
1507
1508 - factory function
1509 - tuple of args for the factory function
1510 - additional state (here None)
1511 - sequence iterator (here None)
1512 - dictionary iterator (yielding successive (key, value) pairs
1513
1514 This API is used by pickle.py and copy.py.
1515
1516 For this to be useful with pickle.py, the default_factory
1517 must be picklable; e.g., None, a built-in, or a global
1518 function in a module or package.
1519
1520 Both shallow and deep copying are supported, but for deep
1521 copying, the default_factory must be deep-copyable; e.g. None,
1522 or a built-in (functions are not copyable at this time).
1523
1524 This only works for subclasses as long as their constructor
1525 signature is compatible; the first argument must be the
1526 optional default_factory, defaulting to None.
1527 */
1528 PyObject *args;
1529 PyObject *items;
1530 PyObject *result;
1531 if (dd->default_factory == NULL || dd->default_factory == Py_None)
1532 args = PyTuple_New(0);
1533 else
1534 args = PyTuple_Pack(1, dd->default_factory);
1535 if (args == NULL)
1536 return NULL;
1537 items = PyObject_CallMethod((PyObject *)dd, "iteritems", "()");
1538 if (items == NULL) {
1539 Py_DECREF(args);
1540 return NULL;
1541 }
1542 result = PyTuple_Pack(5, Py_TYPE(dd), args,
1543 Py_None, Py_None, items);
1544 Py_DECREF(items);
1545 Py_DECREF(args);
1546 return result;
1547 }
1548
1549 static PyMethodDef defdict_methods[] = {
1550 {"__missing__", (PyCFunction)defdict_missing, METH_O,
1551 defdict_missing_doc},
1552 {"copy", (PyCFunction)defdict_copy, METH_NOARGS,
1553 defdict_copy_doc},
1554 {"__copy__", (PyCFunction)defdict_copy, METH_NOARGS,
1555 defdict_copy_doc},
1556 {"__reduce__", (PyCFunction)defdict_reduce, METH_NOARGS,
1557 reduce_doc},
1558 {NULL}
1559 };
1560
1561 static PyMemberDef defdict_members[] = {
1562 {"default_factory", T_OBJECT,
1563 offsetof(defdictobject, default_factory), 0,
1564 PyDoc_STR("Factory for default value called by __missing__().")},
1565 {NULL}
1566 };
1567
1568 static void
defdict_dealloc(defdictobject * dd)1569 defdict_dealloc(defdictobject *dd)
1570 {
1571 /* bpo-31095: UnTrack is needed before calling any callbacks */
1572 PyObject_GC_UnTrack(dd);
1573 Py_CLEAR(dd->default_factory);
1574 PyDict_Type.tp_dealloc((PyObject *)dd);
1575 }
1576
1577 static int
defdict_print(defdictobject * dd,FILE * fp,int flags)1578 defdict_print(defdictobject *dd, FILE *fp, int flags)
1579 {
1580 int sts;
1581 Py_BEGIN_ALLOW_THREADS
1582 fprintf(fp, "defaultdict(");
1583 Py_END_ALLOW_THREADS
1584 if (dd->default_factory == NULL) {
1585 Py_BEGIN_ALLOW_THREADS
1586 fprintf(fp, "None");
1587 Py_END_ALLOW_THREADS
1588 } else {
1589 PyObject_Print(dd->default_factory, fp, 0);
1590 }
1591 Py_BEGIN_ALLOW_THREADS
1592 fprintf(fp, ", ");
1593 Py_END_ALLOW_THREADS
1594 sts = PyDict_Type.tp_print((PyObject *)dd, fp, 0);
1595 Py_BEGIN_ALLOW_THREADS
1596 fprintf(fp, ")");
1597 Py_END_ALLOW_THREADS
1598 return sts;
1599 }
1600
1601 static PyObject *
defdict_repr(defdictobject * dd)1602 defdict_repr(defdictobject *dd)
1603 {
1604 PyObject *defrepr;
1605 PyObject *baserepr;
1606 PyObject *result;
1607 baserepr = PyDict_Type.tp_repr((PyObject *)dd);
1608 if (baserepr == NULL)
1609 return NULL;
1610 if (dd->default_factory == NULL)
1611 defrepr = PyString_FromString("None");
1612 else
1613 {
1614 int status = Py_ReprEnter(dd->default_factory);
1615 if (status != 0) {
1616 if (status < 0) {
1617 Py_DECREF(baserepr);
1618 return NULL;
1619 }
1620 defrepr = PyString_FromString("...");
1621 }
1622 else
1623 defrepr = PyObject_Repr(dd->default_factory);
1624 Py_ReprLeave(dd->default_factory);
1625 }
1626 if (defrepr == NULL) {
1627 Py_DECREF(baserepr);
1628 return NULL;
1629 }
1630 result = PyString_FromFormat("defaultdict(%s, %s)",
1631 PyString_AS_STRING(defrepr),
1632 PyString_AS_STRING(baserepr));
1633 Py_DECREF(defrepr);
1634 Py_DECREF(baserepr);
1635 return result;
1636 }
1637
1638 static int
defdict_traverse(PyObject * self,visitproc visit,void * arg)1639 defdict_traverse(PyObject *self, visitproc visit, void *arg)
1640 {
1641 Py_VISIT(((defdictobject *)self)->default_factory);
1642 return PyDict_Type.tp_traverse(self, visit, arg);
1643 }
1644
1645 static int
defdict_tp_clear(defdictobject * dd)1646 defdict_tp_clear(defdictobject *dd)
1647 {
1648 Py_CLEAR(dd->default_factory);
1649 return PyDict_Type.tp_clear((PyObject *)dd);
1650 }
1651
1652 static int
defdict_init(PyObject * self,PyObject * args,PyObject * kwds)1653 defdict_init(PyObject *self, PyObject *args, PyObject *kwds)
1654 {
1655 defdictobject *dd = (defdictobject *)self;
1656 PyObject *olddefault = dd->default_factory;
1657 PyObject *newdefault = NULL;
1658 PyObject *newargs;
1659 int result;
1660 if (args == NULL || !PyTuple_Check(args))
1661 newargs = PyTuple_New(0);
1662 else {
1663 Py_ssize_t n = PyTuple_GET_SIZE(args);
1664 if (n > 0) {
1665 newdefault = PyTuple_GET_ITEM(args, 0);
1666 if (!PyCallable_Check(newdefault) && newdefault != Py_None) {
1667 PyErr_SetString(PyExc_TypeError,
1668 "first argument must be callable or None");
1669 return -1;
1670 }
1671 }
1672 newargs = PySequence_GetSlice(args, 1, n);
1673 }
1674 if (newargs == NULL)
1675 return -1;
1676 Py_XINCREF(newdefault);
1677 dd->default_factory = newdefault;
1678 result = PyDict_Type.tp_init(self, newargs, kwds);
1679 Py_DECREF(newargs);
1680 Py_XDECREF(olddefault);
1681 return result;
1682 }
1683
1684 PyDoc_STRVAR(defdict_doc,
1685 "defaultdict(default_factory[, ...]) --> dict with default factory\n\
1686 \n\
1687 The default factory is called without arguments to produce\n\
1688 a new value when a key is not present, in __getitem__ only.\n\
1689 A defaultdict compares equal to a dict with the same items.\n\
1690 All remaining arguments are treated the same as if they were\n\
1691 passed to the dict constructor, including keyword arguments.\n\
1692 ");
1693
1694 /* See comment in xxsubtype.c */
1695 #define DEFERRED_ADDRESS(ADDR) 0
1696
1697 static PyTypeObject defdict_type = {
1698 PyVarObject_HEAD_INIT(DEFERRED_ADDRESS(&PyType_Type), 0)
1699 "collections.defaultdict", /* tp_name */
1700 sizeof(defdictobject), /* tp_basicsize */
1701 0, /* tp_itemsize */
1702 /* methods */
1703 (destructor)defdict_dealloc, /* tp_dealloc */
1704 (printfunc)defdict_print, /* tp_print */
1705 0, /* tp_getattr */
1706 0, /* tp_setattr */
1707 0, /* tp_compare */
1708 (reprfunc)defdict_repr, /* tp_repr */
1709 0, /* tp_as_number */
1710 0, /* tp_as_sequence */
1711 0, /* tp_as_mapping */
1712 0, /* tp_hash */
1713 0, /* tp_call */
1714 0, /* tp_str */
1715 PyObject_GenericGetAttr, /* tp_getattro */
1716 0, /* tp_setattro */
1717 0, /* tp_as_buffer */
1718 Py_TPFLAGS_DEFAULT | Py_TPFLAGS_BASETYPE | Py_TPFLAGS_HAVE_GC |
1719 Py_TPFLAGS_HAVE_WEAKREFS, /* tp_flags */
1720 defdict_doc, /* tp_doc */
1721 defdict_traverse, /* tp_traverse */
1722 (inquiry)defdict_tp_clear, /* tp_clear */
1723 0, /* tp_richcompare */
1724 0, /* tp_weaklistoffset*/
1725 0, /* tp_iter */
1726 0, /* tp_iternext */
1727 defdict_methods, /* tp_methods */
1728 defdict_members, /* tp_members */
1729 0, /* tp_getset */
1730 DEFERRED_ADDRESS(&PyDict_Type), /* tp_base */
1731 0, /* tp_dict */
1732 0, /* tp_descr_get */
1733 0, /* tp_descr_set */
1734 0, /* tp_dictoffset */
1735 defdict_init, /* tp_init */
1736 PyType_GenericAlloc, /* tp_alloc */
1737 0, /* tp_new */
1738 PyObject_GC_Del, /* tp_free */
1739 };
1740
1741 /* module level code ********************************************************/
1742
1743 PyDoc_STRVAR(module_doc,
1744 "High performance data structures.\n\
1745 - deque: ordered collection accessible from endpoints only\n\
1746 - defaultdict: dict subclass with a default value factory\n\
1747 ");
1748
1749 PyMODINIT_FUNC
init_collections(void)1750 init_collections(void)
1751 {
1752 PyObject *m;
1753
1754 m = Py_InitModule3("_collections", NULL, module_doc);
1755 if (m == NULL)
1756 return;
1757
1758 if (PyType_Ready(&deque_type) < 0)
1759 return;
1760 Py_INCREF(&deque_type);
1761 PyModule_AddObject(m, "deque", (PyObject *)&deque_type);
1762
1763 defdict_type.tp_base = &PyDict_Type;
1764 if (PyType_Ready(&defdict_type) < 0)
1765 return;
1766 Py_INCREF(&defdict_type);
1767 PyModule_AddObject(m, "defaultdict", (PyObject *)&defdict_type);
1768
1769 if (PyType_Ready(&dequeiter_type) < 0)
1770 return;
1771
1772 if (PyType_Ready(&dequereviter_type) < 0)
1773 return;
1774
1775 return;
1776 }
1777