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 void
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;
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;
705
706 alternate_method:
707 while (deque->len) {
708 item = deque_pop(deque, NULL);
709 assert (item != NULL);
710 Py_DECREF(item);
711 }
712 }
713
714 static PyObject *
deque_item(dequeobject * deque,Py_ssize_t i)715 deque_item(dequeobject *deque, Py_ssize_t i)
716 {
717 block *b;
718 PyObject *item;
719 Py_ssize_t n, index=i;
720
721 if (i < 0 || i >= deque->len) {
722 PyErr_SetString(PyExc_IndexError,
723 "deque index out of range");
724 return NULL;
725 }
726
727 if (i == 0) {
728 i = deque->leftindex;
729 b = deque->leftblock;
730 } else if (i == deque->len - 1) {
731 i = deque->rightindex;
732 b = deque->rightblock;
733 } else {
734 i += deque->leftindex;
735 n = i / BLOCKLEN;
736 i %= BLOCKLEN;
737 if (index < (deque->len >> 1)) {
738 b = deque->leftblock;
739 while (n--)
740 b = b->rightlink;
741 } else {
742 n = (deque->leftindex + deque->len - 1) / BLOCKLEN - n;
743 b = deque->rightblock;
744 while (n--)
745 b = b->leftlink;
746 }
747 }
748 item = b->data[i];
749 Py_INCREF(item);
750 return item;
751 }
752
753 /* delitem() implemented in terms of rotate for simplicity and reasonable
754 performance near the end points. If for some reason this method becomes
755 popular, it is not hard to re-implement this using direct data movement
756 (similar to code in list slice assignment) and achieve a two or threefold
757 performance boost.
758 */
759
760 static int
deque_del_item(dequeobject * deque,Py_ssize_t i)761 deque_del_item(dequeobject *deque, Py_ssize_t i)
762 {
763 PyObject *item;
764 int rv;
765
766 assert (i >= 0 && i < deque->len);
767 if (_deque_rotate(deque, -i))
768 return -1;
769 item = deque_popleft(deque, NULL);
770 rv = _deque_rotate(deque, i);
771 assert (item != NULL);
772 Py_DECREF(item);
773 return rv;
774 }
775
776 static int
deque_ass_item(dequeobject * deque,Py_ssize_t i,PyObject * v)777 deque_ass_item(dequeobject *deque, Py_ssize_t i, PyObject *v)
778 {
779 PyObject *old_value;
780 block *b;
781 Py_ssize_t n, len=deque->len, halflen=(len+1)>>1, index=i;
782
783 if (i < 0 || i >= len) {
784 PyErr_SetString(PyExc_IndexError,
785 "deque index out of range");
786 return -1;
787 }
788 if (v == NULL)
789 return deque_del_item(deque, i);
790
791 i += deque->leftindex;
792 n = i / BLOCKLEN;
793 i %= BLOCKLEN;
794 if (index <= halflen) {
795 b = deque->leftblock;
796 while (n--)
797 b = b->rightlink;
798 } else {
799 n = (deque->leftindex + len - 1) / BLOCKLEN - n;
800 b = deque->rightblock;
801 while (n--)
802 b = b->leftlink;
803 }
804 Py_INCREF(v);
805 old_value = b->data[i];
806 b->data[i] = v;
807 Py_DECREF(old_value);
808 return 0;
809 }
810
811 static PyObject *
deque_clearmethod(dequeobject * deque)812 deque_clearmethod(dequeobject *deque)
813 {
814 deque_clear(deque);
815 Py_RETURN_NONE;
816 }
817
818 PyDoc_STRVAR(clear_doc, "Remove all elements from the deque.");
819
820 static void
deque_dealloc(dequeobject * deque)821 deque_dealloc(dequeobject *deque)
822 {
823 PyObject_GC_UnTrack(deque);
824 if (deque->weakreflist != NULL)
825 PyObject_ClearWeakRefs((PyObject *) deque);
826 if (deque->leftblock != NULL) {
827 deque_clear(deque);
828 assert(deque->leftblock != NULL);
829 freeblock(deque->leftblock);
830 }
831 deque->leftblock = NULL;
832 deque->rightblock = NULL;
833 Py_TYPE(deque)->tp_free(deque);
834 }
835
836 static int
deque_traverse(dequeobject * deque,visitproc visit,void * arg)837 deque_traverse(dequeobject *deque, visitproc visit, void *arg)
838 {
839 block *b;
840 PyObject *item;
841 Py_ssize_t index;
842 Py_ssize_t indexlo = deque->leftindex;
843
844 for (b = deque->leftblock; b != NULL; b = b->rightlink) {
845 const Py_ssize_t indexhi = b == deque->rightblock ?
846 deque->rightindex :
847 BLOCKLEN - 1;
848
849 for (index = indexlo; index <= indexhi; ++index) {
850 item = b->data[index];
851 Py_VISIT(item);
852 }
853 indexlo = 0;
854 }
855 return 0;
856 }
857
858 static PyObject *
deque_copy(PyObject * deque)859 deque_copy(PyObject *deque)
860 {
861 if (((dequeobject *)deque)->maxlen == -1)
862 return PyObject_CallFunction((PyObject *)(Py_TYPE(deque)), "O", deque, NULL);
863 else
864 return PyObject_CallFunction((PyObject *)(Py_TYPE(deque)), "Oi",
865 deque, ((dequeobject *)deque)->maxlen, NULL);
866 }
867
868 PyDoc_STRVAR(copy_doc, "Return a shallow copy of a deque.");
869
870 static PyObject *
deque_reduce(dequeobject * deque)871 deque_reduce(dequeobject *deque)
872 {
873 PyObject *dict, *result, *aslist;
874
875 dict = PyObject_GetAttrString((PyObject *)deque, "__dict__");
876 if (dict == NULL)
877 PyErr_Clear();
878 aslist = PySequence_List((PyObject *)deque);
879 if (aslist == NULL) {
880 Py_XDECREF(dict);
881 return NULL;
882 }
883 if (dict == NULL) {
884 if (deque->maxlen == -1)
885 result = Py_BuildValue("O(O)", Py_TYPE(deque), aslist);
886 else
887 result = Py_BuildValue("O(On)", Py_TYPE(deque), aslist, deque->maxlen);
888 } else {
889 if (deque->maxlen == -1)
890 result = Py_BuildValue("O(OO)O", Py_TYPE(deque), aslist, Py_None, dict);
891 else
892 result = Py_BuildValue("O(On)O", Py_TYPE(deque), aslist, deque->maxlen, dict);
893 }
894 Py_XDECREF(dict);
895 Py_DECREF(aslist);
896 return result;
897 }
898
899 PyDoc_STRVAR(reduce_doc, "Return state information for pickling.");
900
901 static PyObject *
deque_repr(PyObject * deque)902 deque_repr(PyObject *deque)
903 {
904 PyObject *aslist, *result, *fmt;
905 int i;
906
907 i = Py_ReprEnter(deque);
908 if (i != 0) {
909 if (i < 0)
910 return NULL;
911 return PyString_FromString("[...]");
912 }
913
914 aslist = PySequence_List(deque);
915 if (aslist == NULL) {
916 Py_ReprLeave(deque);
917 return NULL;
918 }
919 if (((dequeobject *)deque)->maxlen != -1)
920 fmt = PyString_FromFormat("deque(%%r, maxlen=%zd)",
921 ((dequeobject *)deque)->maxlen);
922 else
923 fmt = PyString_FromString("deque(%r)");
924 if (fmt == NULL) {
925 Py_DECREF(aslist);
926 Py_ReprLeave(deque);
927 return NULL;
928 }
929 result = PyString_Format(fmt, aslist);
930 Py_DECREF(fmt);
931 Py_DECREF(aslist);
932 Py_ReprLeave(deque);
933 return result;
934 }
935
936 static int
deque_tp_print(PyObject * deque,FILE * fp,int flags)937 deque_tp_print(PyObject *deque, FILE *fp, int flags)
938 {
939 PyObject *it, *item;
940 char *emit = ""; /* No separator emitted on first pass */
941 char *separator = ", ";
942 int i;
943
944 i = Py_ReprEnter(deque);
945 if (i != 0) {
946 if (i < 0)
947 return i;
948 Py_BEGIN_ALLOW_THREADS
949 fputs("[...]", fp);
950 Py_END_ALLOW_THREADS
951 return 0;
952 }
953
954 it = PyObject_GetIter(deque);
955 if (it == NULL)
956 return -1;
957
958 Py_BEGIN_ALLOW_THREADS
959 fputs("deque([", fp);
960 Py_END_ALLOW_THREADS
961 while ((item = PyIter_Next(it)) != NULL) {
962 Py_BEGIN_ALLOW_THREADS
963 fputs(emit, fp);
964 Py_END_ALLOW_THREADS
965 emit = separator;
966 if (PyObject_Print(item, fp, 0) != 0) {
967 Py_DECREF(item);
968 Py_DECREF(it);
969 Py_ReprLeave(deque);
970 return -1;
971 }
972 Py_DECREF(item);
973 }
974 Py_ReprLeave(deque);
975 Py_DECREF(it);
976 if (PyErr_Occurred())
977 return -1;
978
979 Py_BEGIN_ALLOW_THREADS
980 if (((dequeobject *)deque)->maxlen == -1)
981 fputs("])", fp);
982 else
983 fprintf(fp, "], maxlen=%" PY_FORMAT_SIZE_T "d)", ((dequeobject *)deque)->maxlen);
984 Py_END_ALLOW_THREADS
985 return 0;
986 }
987
988 static PyObject *
deque_richcompare(PyObject * v,PyObject * w,int op)989 deque_richcompare(PyObject *v, PyObject *w, int op)
990 {
991 PyObject *it1=NULL, *it2=NULL, *x, *y;
992 Py_ssize_t vs, ws;
993 int b, cmp=-1;
994
995 if (!PyObject_TypeCheck(v, &deque_type) ||
996 !PyObject_TypeCheck(w, &deque_type)) {
997 Py_INCREF(Py_NotImplemented);
998 return Py_NotImplemented;
999 }
1000
1001 /* Shortcuts */
1002 vs = ((dequeobject *)v)->len;
1003 ws = ((dequeobject *)w)->len;
1004 if (op == Py_EQ) {
1005 if (v == w)
1006 Py_RETURN_TRUE;
1007 if (vs != ws)
1008 Py_RETURN_FALSE;
1009 }
1010 if (op == Py_NE) {
1011 if (v == w)
1012 Py_RETURN_FALSE;
1013 if (vs != ws)
1014 Py_RETURN_TRUE;
1015 }
1016
1017 /* Search for the first index where items are different */
1018 it1 = PyObject_GetIter(v);
1019 if (it1 == NULL)
1020 goto done;
1021 it2 = PyObject_GetIter(w);
1022 if (it2 == NULL)
1023 goto done;
1024 for (;;) {
1025 x = PyIter_Next(it1);
1026 if (x == NULL && PyErr_Occurred())
1027 goto done;
1028 y = PyIter_Next(it2);
1029 if (x == NULL || y == NULL)
1030 break;
1031 b = PyObject_RichCompareBool(x, y, Py_EQ);
1032 if (b == 0) {
1033 cmp = PyObject_RichCompareBool(x, y, op);
1034 Py_DECREF(x);
1035 Py_DECREF(y);
1036 goto done;
1037 }
1038 Py_DECREF(x);
1039 Py_DECREF(y);
1040 if (b == -1)
1041 goto done;
1042 }
1043 /* We reached the end of one deque or both */
1044 Py_XDECREF(x);
1045 Py_XDECREF(y);
1046 if (PyErr_Occurred())
1047 goto done;
1048 switch (op) {
1049 case Py_LT: cmp = y != NULL; break; /* if w was longer */
1050 case Py_LE: cmp = x == NULL; break; /* if v was not longer */
1051 case Py_EQ: cmp = x == y; break; /* if we reached the end of both */
1052 case Py_NE: cmp = x != y; break; /* if one deque continues */
1053 case Py_GT: cmp = x != NULL; break; /* if v was longer */
1054 case Py_GE: cmp = y == NULL; break; /* if w was not longer */
1055 }
1056
1057 done:
1058 Py_XDECREF(it1);
1059 Py_XDECREF(it2);
1060 if (cmp == 1)
1061 Py_RETURN_TRUE;
1062 if (cmp == 0)
1063 Py_RETURN_FALSE;
1064 return NULL;
1065 }
1066
1067 static int
deque_init(dequeobject * deque,PyObject * args,PyObject * kwdargs)1068 deque_init(dequeobject *deque, PyObject *args, PyObject *kwdargs)
1069 {
1070 PyObject *iterable = NULL;
1071 PyObject *maxlenobj = NULL;
1072 Py_ssize_t maxlen = -1;
1073 char *kwlist[] = {"iterable", "maxlen", 0};
1074
1075 if (!PyArg_ParseTupleAndKeywords(args, kwdargs, "|OO:deque", kwlist, &iterable, &maxlenobj))
1076 return -1;
1077 if (maxlenobj != NULL && maxlenobj != Py_None) {
1078 maxlen = PyInt_AsSsize_t(maxlenobj);
1079 if (maxlen == -1 && PyErr_Occurred())
1080 return -1;
1081 if (maxlen < 0) {
1082 PyErr_SetString(PyExc_ValueError, "maxlen must be non-negative");
1083 return -1;
1084 }
1085 }
1086 deque->maxlen = maxlen;
1087 if (deque->len > 0)
1088 deque_clear(deque);
1089 if (iterable != NULL) {
1090 PyObject *rv = deque_extend(deque, iterable);
1091 if (rv == NULL)
1092 return -1;
1093 Py_DECREF(rv);
1094 }
1095 return 0;
1096 }
1097
1098 static PyObject *
deque_sizeof(dequeobject * deque,void * unused)1099 deque_sizeof(dequeobject *deque, void *unused)
1100 {
1101 Py_ssize_t res;
1102 Py_ssize_t blocks;
1103
1104 res = _PyObject_SIZE(Py_TYPE(deque));
1105 blocks = (deque->leftindex + deque->len + BLOCKLEN - 1) / BLOCKLEN;
1106 assert(deque->leftindex + deque->len - 1 ==
1107 (blocks - 1) * BLOCKLEN + deque->rightindex);
1108 res += blocks * sizeof(block);
1109 return PyLong_FromSsize_t(res);
1110 }
1111
1112 PyDoc_STRVAR(sizeof_doc,
1113 "D.__sizeof__() -- size of D in memory, in bytes");
1114
1115 static PyObject *
deque_get_maxlen(dequeobject * deque)1116 deque_get_maxlen(dequeobject *deque)
1117 {
1118 if (deque->maxlen == -1)
1119 Py_RETURN_NONE;
1120 return PyInt_FromSsize_t(deque->maxlen);
1121 }
1122
1123 static PyGetSetDef deque_getset[] = {
1124 {"maxlen", (getter)deque_get_maxlen, (setter)NULL,
1125 "maximum size of a deque or None if unbounded"},
1126 {0}
1127 };
1128
1129 static PySequenceMethods deque_as_sequence = {
1130 (lenfunc)deque_len, /* sq_length */
1131 0, /* sq_concat */
1132 0, /* sq_repeat */
1133 (ssizeargfunc)deque_item, /* sq_item */
1134 0, /* sq_slice */
1135 (ssizeobjargproc)deque_ass_item, /* sq_ass_item */
1136 0, /* sq_ass_slice */
1137 0, /* sq_contains */
1138 (binaryfunc)deque_inplace_concat, /* sq_inplace_concat */
1139 0, /* sq_inplace_repeat */
1140
1141 };
1142
1143 /* deque object ********************************************************/
1144
1145 static PyObject *deque_iter(dequeobject *deque);
1146 static PyObject *deque_reviter(dequeobject *deque);
1147 PyDoc_STRVAR(reversed_doc,
1148 "D.__reversed__() -- return a reverse iterator over the deque");
1149
1150 static PyMethodDef deque_methods[] = {
1151 {"append", (PyCFunction)deque_append,
1152 METH_O, append_doc},
1153 {"appendleft", (PyCFunction)deque_appendleft,
1154 METH_O, appendleft_doc},
1155 {"clear", (PyCFunction)deque_clearmethod,
1156 METH_NOARGS, clear_doc},
1157 {"__copy__", (PyCFunction)deque_copy,
1158 METH_NOARGS, copy_doc},
1159 {"count", (PyCFunction)deque_count,
1160 METH_O, count_doc},
1161 {"extend", (PyCFunction)deque_extend,
1162 METH_O, extend_doc},
1163 {"extendleft", (PyCFunction)deque_extendleft,
1164 METH_O, extendleft_doc},
1165 {"pop", (PyCFunction)deque_pop,
1166 METH_NOARGS, pop_doc},
1167 {"popleft", (PyCFunction)deque_popleft,
1168 METH_NOARGS, popleft_doc},
1169 {"__reduce__", (PyCFunction)deque_reduce,
1170 METH_NOARGS, reduce_doc},
1171 {"remove", (PyCFunction)deque_remove,
1172 METH_O, remove_doc},
1173 {"__reversed__", (PyCFunction)deque_reviter,
1174 METH_NOARGS, reversed_doc},
1175 {"reverse", (PyCFunction)deque_reverse,
1176 METH_NOARGS, reverse_doc},
1177 {"rotate", (PyCFunction)deque_rotate,
1178 METH_VARARGS, rotate_doc},
1179 {"__sizeof__", (PyCFunction)deque_sizeof,
1180 METH_NOARGS, sizeof_doc},
1181 {NULL, NULL} /* sentinel */
1182 };
1183
1184 PyDoc_STRVAR(deque_doc,
1185 "deque([iterable[, maxlen]]) --> deque object\n\
1186 \n\
1187 Build an ordered collection with optimized access from its endpoints.");
1188
1189 static PyTypeObject deque_type = {
1190 PyVarObject_HEAD_INIT(NULL, 0)
1191 "collections.deque", /* tp_name */
1192 sizeof(dequeobject), /* tp_basicsize */
1193 0, /* tp_itemsize */
1194 /* methods */
1195 (destructor)deque_dealloc, /* tp_dealloc */
1196 deque_tp_print, /* tp_print */
1197 0, /* tp_getattr */
1198 0, /* tp_setattr */
1199 0, /* tp_compare */
1200 deque_repr, /* tp_repr */
1201 0, /* tp_as_number */
1202 &deque_as_sequence, /* tp_as_sequence */
1203 0, /* tp_as_mapping */
1204 (hashfunc)PyObject_HashNotImplemented, /* tp_hash */
1205 0, /* tp_call */
1206 0, /* tp_str */
1207 PyObject_GenericGetAttr, /* tp_getattro */
1208 0, /* tp_setattro */
1209 0, /* tp_as_buffer */
1210 Py_TPFLAGS_DEFAULT | Py_TPFLAGS_BASETYPE | Py_TPFLAGS_HAVE_GC |
1211 Py_TPFLAGS_HAVE_WEAKREFS, /* tp_flags */
1212 deque_doc, /* tp_doc */
1213 (traverseproc)deque_traverse, /* tp_traverse */
1214 (inquiry)deque_clear, /* tp_clear */
1215 (richcmpfunc)deque_richcompare, /* tp_richcompare */
1216 offsetof(dequeobject, weakreflist), /* tp_weaklistoffset*/
1217 (getiterfunc)deque_iter, /* tp_iter */
1218 0, /* tp_iternext */
1219 deque_methods, /* tp_methods */
1220 0, /* tp_members */
1221 deque_getset, /* tp_getset */
1222 0, /* tp_base */
1223 0, /* tp_dict */
1224 0, /* tp_descr_get */
1225 0, /* tp_descr_set */
1226 0, /* tp_dictoffset */
1227 (initproc)deque_init, /* tp_init */
1228 PyType_GenericAlloc, /* tp_alloc */
1229 deque_new, /* tp_new */
1230 PyObject_GC_Del, /* tp_free */
1231 };
1232
1233 /*********************** Deque Iterator **************************/
1234
1235 typedef struct {
1236 PyObject_HEAD
1237 Py_ssize_t index;
1238 block *b;
1239 dequeobject *deque;
1240 long state; /* state when the iterator is created */
1241 Py_ssize_t counter; /* number of items remaining for iteration */
1242 } dequeiterobject;
1243
1244 static PyTypeObject dequeiter_type;
1245
1246 static PyObject *
deque_iter(dequeobject * deque)1247 deque_iter(dequeobject *deque)
1248 {
1249 dequeiterobject *it;
1250
1251 it = PyObject_GC_New(dequeiterobject, &dequeiter_type);
1252 if (it == NULL)
1253 return NULL;
1254 it->b = deque->leftblock;
1255 it->index = deque->leftindex;
1256 Py_INCREF(deque);
1257 it->deque = deque;
1258 it->state = deque->state;
1259 it->counter = deque->len;
1260 PyObject_GC_Track(it);
1261 return (PyObject *)it;
1262 }
1263
1264 static int
dequeiter_traverse(dequeiterobject * dio,visitproc visit,void * arg)1265 dequeiter_traverse(dequeiterobject *dio, visitproc visit, void *arg)
1266 {
1267 Py_VISIT(dio->deque);
1268 return 0;
1269 }
1270
1271 static void
dequeiter_dealloc(dequeiterobject * dio)1272 dequeiter_dealloc(dequeiterobject *dio)
1273 {
1274 Py_XDECREF(dio->deque);
1275 PyObject_GC_Del(dio);
1276 }
1277
1278 static PyObject *
dequeiter_next(dequeiterobject * it)1279 dequeiter_next(dequeiterobject *it)
1280 {
1281 PyObject *item;
1282
1283 if (it->deque->state != it->state) {
1284 it->counter = 0;
1285 PyErr_SetString(PyExc_RuntimeError,
1286 "deque mutated during iteration");
1287 return NULL;
1288 }
1289 if (it->counter == 0)
1290 return NULL;
1291 assert (!(it->b == it->deque->rightblock &&
1292 it->index > it->deque->rightindex));
1293
1294 item = it->b->data[it->index];
1295 it->index++;
1296 it->counter--;
1297 if (it->index == BLOCKLEN && it->counter > 0) {
1298 assert (it->b->rightlink != NULL);
1299 it->b = it->b->rightlink;
1300 it->index = 0;
1301 }
1302 Py_INCREF(item);
1303 return item;
1304 }
1305
1306 static PyObject *
dequeiter_len(dequeiterobject * it)1307 dequeiter_len(dequeiterobject *it)
1308 {
1309 return PyInt_FromLong(it->counter);
1310 }
1311
1312 PyDoc_STRVAR(length_hint_doc, "Private method returning an estimate of len(list(it)).");
1313
1314 static PyMethodDef dequeiter_methods[] = {
1315 {"__length_hint__", (PyCFunction)dequeiter_len, METH_NOARGS, length_hint_doc},
1316 {NULL, NULL} /* sentinel */
1317 };
1318
1319 static PyTypeObject dequeiter_type = {
1320 PyVarObject_HEAD_INIT(NULL, 0)
1321 "deque_iterator", /* tp_name */
1322 sizeof(dequeiterobject), /* tp_basicsize */
1323 0, /* tp_itemsize */
1324 /* methods */
1325 (destructor)dequeiter_dealloc, /* tp_dealloc */
1326 0, /* tp_print */
1327 0, /* tp_getattr */
1328 0, /* tp_setattr */
1329 0, /* tp_compare */
1330 0, /* tp_repr */
1331 0, /* tp_as_number */
1332 0, /* tp_as_sequence */
1333 0, /* tp_as_mapping */
1334 0, /* tp_hash */
1335 0, /* tp_call */
1336 0, /* tp_str */
1337 PyObject_GenericGetAttr, /* tp_getattro */
1338 0, /* tp_setattro */
1339 0, /* tp_as_buffer */
1340 Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC,/* tp_flags */
1341 0, /* tp_doc */
1342 (traverseproc)dequeiter_traverse, /* tp_traverse */
1343 0, /* tp_clear */
1344 0, /* tp_richcompare */
1345 0, /* tp_weaklistoffset */
1346 PyObject_SelfIter, /* tp_iter */
1347 (iternextfunc)dequeiter_next, /* tp_iternext */
1348 dequeiter_methods, /* tp_methods */
1349 0,
1350 };
1351
1352 /*********************** Deque Reverse Iterator **************************/
1353
1354 static PyTypeObject dequereviter_type;
1355
1356 static PyObject *
deque_reviter(dequeobject * deque)1357 deque_reviter(dequeobject *deque)
1358 {
1359 dequeiterobject *it;
1360
1361 it = PyObject_GC_New(dequeiterobject, &dequereviter_type);
1362 if (it == NULL)
1363 return NULL;
1364 it->b = deque->rightblock;
1365 it->index = deque->rightindex;
1366 Py_INCREF(deque);
1367 it->deque = deque;
1368 it->state = deque->state;
1369 it->counter = deque->len;
1370 PyObject_GC_Track(it);
1371 return (PyObject *)it;
1372 }
1373
1374 static PyObject *
dequereviter_next(dequeiterobject * it)1375 dequereviter_next(dequeiterobject *it)
1376 {
1377 PyObject *item;
1378 if (it->counter == 0)
1379 return NULL;
1380
1381 if (it->deque->state != it->state) {
1382 it->counter = 0;
1383 PyErr_SetString(PyExc_RuntimeError,
1384 "deque mutated during iteration");
1385 return NULL;
1386 }
1387 assert (!(it->b == it->deque->leftblock &&
1388 it->index < it->deque->leftindex));
1389
1390 item = it->b->data[it->index];
1391 it->index--;
1392 it->counter--;
1393 if (it->index == -1 && it->counter > 0) {
1394 assert (it->b->leftlink != NULL);
1395 it->b = it->b->leftlink;
1396 it->index = BLOCKLEN - 1;
1397 }
1398 Py_INCREF(item);
1399 return item;
1400 }
1401
1402 static PyTypeObject dequereviter_type = {
1403 PyVarObject_HEAD_INIT(NULL, 0)
1404 "deque_reverse_iterator", /* tp_name */
1405 sizeof(dequeiterobject), /* tp_basicsize */
1406 0, /* tp_itemsize */
1407 /* methods */
1408 (destructor)dequeiter_dealloc, /* tp_dealloc */
1409 0, /* tp_print */
1410 0, /* tp_getattr */
1411 0, /* tp_setattr */
1412 0, /* tp_compare */
1413 0, /* tp_repr */
1414 0, /* tp_as_number */
1415 0, /* tp_as_sequence */
1416 0, /* tp_as_mapping */
1417 0, /* tp_hash */
1418 0, /* tp_call */
1419 0, /* tp_str */
1420 PyObject_GenericGetAttr, /* tp_getattro */
1421 0, /* tp_setattro */
1422 0, /* tp_as_buffer */
1423 Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC,/* tp_flags */
1424 0, /* tp_doc */
1425 (traverseproc)dequeiter_traverse, /* tp_traverse */
1426 0, /* tp_clear */
1427 0, /* tp_richcompare */
1428 0, /* tp_weaklistoffset */
1429 PyObject_SelfIter, /* tp_iter */
1430 (iternextfunc)dequereviter_next, /* tp_iternext */
1431 dequeiter_methods, /* tp_methods */
1432 0,
1433 };
1434
1435 /* defaultdict type *********************************************************/
1436
1437 typedef struct {
1438 PyDictObject dict;
1439 PyObject *default_factory;
1440 } defdictobject;
1441
1442 static PyTypeObject defdict_type; /* Forward */
1443
1444 PyDoc_STRVAR(defdict_missing_doc,
1445 "__missing__(key) # Called by __getitem__ for missing key; pseudo-code:\n\
1446 if self.default_factory is None: raise KeyError((key,))\n\
1447 self[key] = value = self.default_factory()\n\
1448 return value\n\
1449 ");
1450
1451 static PyObject *
defdict_missing(defdictobject * dd,PyObject * key)1452 defdict_missing(defdictobject *dd, PyObject *key)
1453 {
1454 PyObject *factory = dd->default_factory;
1455 PyObject *value;
1456 if (factory == NULL || factory == Py_None) {
1457 /* XXX Call dict.__missing__(key) */
1458 PyObject *tup;
1459 tup = PyTuple_Pack(1, key);
1460 if (!tup) return NULL;
1461 PyErr_SetObject(PyExc_KeyError, tup);
1462 Py_DECREF(tup);
1463 return NULL;
1464 }
1465 value = PyEval_CallObject(factory, NULL);
1466 if (value == NULL)
1467 return value;
1468 if (PyObject_SetItem((PyObject *)dd, key, value) < 0) {
1469 Py_DECREF(value);
1470 return NULL;
1471 }
1472 return value;
1473 }
1474
1475 PyDoc_STRVAR(defdict_copy_doc, "D.copy() -> a shallow copy of D.");
1476
1477 static PyObject *
defdict_copy(defdictobject * dd)1478 defdict_copy(defdictobject *dd)
1479 {
1480 /* This calls the object's class. That only works for subclasses
1481 whose class constructor has the same signature. Subclasses that
1482 define a different constructor signature must override copy().
1483 */
1484
1485 if (dd->default_factory == NULL)
1486 return PyObject_CallFunctionObjArgs((PyObject*)Py_TYPE(dd), Py_None, dd, NULL);
1487 return PyObject_CallFunctionObjArgs((PyObject*)Py_TYPE(dd),
1488 dd->default_factory, dd, NULL);
1489 }
1490
1491 static PyObject *
defdict_reduce(defdictobject * dd)1492 defdict_reduce(defdictobject *dd)
1493 {
1494 /* __reduce__ must return a 5-tuple as follows:
1495
1496 - factory function
1497 - tuple of args for the factory function
1498 - additional state (here None)
1499 - sequence iterator (here None)
1500 - dictionary iterator (yielding successive (key, value) pairs
1501
1502 This API is used by pickle.py and copy.py.
1503
1504 For this to be useful with pickle.py, the default_factory
1505 must be picklable; e.g., None, a built-in, or a global
1506 function in a module or package.
1507
1508 Both shallow and deep copying are supported, but for deep
1509 copying, the default_factory must be deep-copyable; e.g. None,
1510 or a built-in (functions are not copyable at this time).
1511
1512 This only works for subclasses as long as their constructor
1513 signature is compatible; the first argument must be the
1514 optional default_factory, defaulting to None.
1515 */
1516 PyObject *args;
1517 PyObject *items;
1518 PyObject *result;
1519 if (dd->default_factory == NULL || dd->default_factory == Py_None)
1520 args = PyTuple_New(0);
1521 else
1522 args = PyTuple_Pack(1, dd->default_factory);
1523 if (args == NULL)
1524 return NULL;
1525 items = PyObject_CallMethod((PyObject *)dd, "iteritems", "()");
1526 if (items == NULL) {
1527 Py_DECREF(args);
1528 return NULL;
1529 }
1530 result = PyTuple_Pack(5, Py_TYPE(dd), args,
1531 Py_None, Py_None, items);
1532 Py_DECREF(items);
1533 Py_DECREF(args);
1534 return result;
1535 }
1536
1537 static PyMethodDef defdict_methods[] = {
1538 {"__missing__", (PyCFunction)defdict_missing, METH_O,
1539 defdict_missing_doc},
1540 {"copy", (PyCFunction)defdict_copy, METH_NOARGS,
1541 defdict_copy_doc},
1542 {"__copy__", (PyCFunction)defdict_copy, METH_NOARGS,
1543 defdict_copy_doc},
1544 {"__reduce__", (PyCFunction)defdict_reduce, METH_NOARGS,
1545 reduce_doc},
1546 {NULL}
1547 };
1548
1549 static PyMemberDef defdict_members[] = {
1550 {"default_factory", T_OBJECT,
1551 offsetof(defdictobject, default_factory), 0,
1552 PyDoc_STR("Factory for default value called by __missing__().")},
1553 {NULL}
1554 };
1555
1556 static void
defdict_dealloc(defdictobject * dd)1557 defdict_dealloc(defdictobject *dd)
1558 {
1559 Py_CLEAR(dd->default_factory);
1560 PyDict_Type.tp_dealloc((PyObject *)dd);
1561 }
1562
1563 static int
defdict_print(defdictobject * dd,FILE * fp,int flags)1564 defdict_print(defdictobject *dd, FILE *fp, int flags)
1565 {
1566 int sts;
1567 Py_BEGIN_ALLOW_THREADS
1568 fprintf(fp, "defaultdict(");
1569 Py_END_ALLOW_THREADS
1570 if (dd->default_factory == NULL) {
1571 Py_BEGIN_ALLOW_THREADS
1572 fprintf(fp, "None");
1573 Py_END_ALLOW_THREADS
1574 } else {
1575 PyObject_Print(dd->default_factory, fp, 0);
1576 }
1577 Py_BEGIN_ALLOW_THREADS
1578 fprintf(fp, ", ");
1579 Py_END_ALLOW_THREADS
1580 sts = PyDict_Type.tp_print((PyObject *)dd, fp, 0);
1581 Py_BEGIN_ALLOW_THREADS
1582 fprintf(fp, ")");
1583 Py_END_ALLOW_THREADS
1584 return sts;
1585 }
1586
1587 static PyObject *
defdict_repr(defdictobject * dd)1588 defdict_repr(defdictobject *dd)
1589 {
1590 PyObject *defrepr;
1591 PyObject *baserepr;
1592 PyObject *result;
1593 baserepr = PyDict_Type.tp_repr((PyObject *)dd);
1594 if (baserepr == NULL)
1595 return NULL;
1596 if (dd->default_factory == NULL)
1597 defrepr = PyString_FromString("None");
1598 else
1599 {
1600 int status = Py_ReprEnter(dd->default_factory);
1601 if (status != 0) {
1602 if (status < 0) {
1603 Py_DECREF(baserepr);
1604 return NULL;
1605 }
1606 defrepr = PyString_FromString("...");
1607 }
1608 else
1609 defrepr = PyObject_Repr(dd->default_factory);
1610 Py_ReprLeave(dd->default_factory);
1611 }
1612 if (defrepr == NULL) {
1613 Py_DECREF(baserepr);
1614 return NULL;
1615 }
1616 result = PyString_FromFormat("defaultdict(%s, %s)",
1617 PyString_AS_STRING(defrepr),
1618 PyString_AS_STRING(baserepr));
1619 Py_DECREF(defrepr);
1620 Py_DECREF(baserepr);
1621 return result;
1622 }
1623
1624 static int
defdict_traverse(PyObject * self,visitproc visit,void * arg)1625 defdict_traverse(PyObject *self, visitproc visit, void *arg)
1626 {
1627 Py_VISIT(((defdictobject *)self)->default_factory);
1628 return PyDict_Type.tp_traverse(self, visit, arg);
1629 }
1630
1631 static int
defdict_tp_clear(defdictobject * dd)1632 defdict_tp_clear(defdictobject *dd)
1633 {
1634 Py_CLEAR(dd->default_factory);
1635 return PyDict_Type.tp_clear((PyObject *)dd);
1636 }
1637
1638 static int
defdict_init(PyObject * self,PyObject * args,PyObject * kwds)1639 defdict_init(PyObject *self, PyObject *args, PyObject *kwds)
1640 {
1641 defdictobject *dd = (defdictobject *)self;
1642 PyObject *olddefault = dd->default_factory;
1643 PyObject *newdefault = NULL;
1644 PyObject *newargs;
1645 int result;
1646 if (args == NULL || !PyTuple_Check(args))
1647 newargs = PyTuple_New(0);
1648 else {
1649 Py_ssize_t n = PyTuple_GET_SIZE(args);
1650 if (n > 0) {
1651 newdefault = PyTuple_GET_ITEM(args, 0);
1652 if (!PyCallable_Check(newdefault) && newdefault != Py_None) {
1653 PyErr_SetString(PyExc_TypeError,
1654 "first argument must be callable or None");
1655 return -1;
1656 }
1657 }
1658 newargs = PySequence_GetSlice(args, 1, n);
1659 }
1660 if (newargs == NULL)
1661 return -1;
1662 Py_XINCREF(newdefault);
1663 dd->default_factory = newdefault;
1664 result = PyDict_Type.tp_init(self, newargs, kwds);
1665 Py_DECREF(newargs);
1666 Py_XDECREF(olddefault);
1667 return result;
1668 }
1669
1670 PyDoc_STRVAR(defdict_doc,
1671 "defaultdict(default_factory[, ...]) --> dict with default factory\n\
1672 \n\
1673 The default factory is called without arguments to produce\n\
1674 a new value when a key is not present, in __getitem__ only.\n\
1675 A defaultdict compares equal to a dict with the same items.\n\
1676 All remaining arguments are treated the same as if they were\n\
1677 passed to the dict constructor, including keyword arguments.\n\
1678 ");
1679
1680 /* See comment in xxsubtype.c */
1681 #define DEFERRED_ADDRESS(ADDR) 0
1682
1683 static PyTypeObject defdict_type = {
1684 PyVarObject_HEAD_INIT(DEFERRED_ADDRESS(&PyType_Type), 0)
1685 "collections.defaultdict", /* tp_name */
1686 sizeof(defdictobject), /* tp_basicsize */
1687 0, /* tp_itemsize */
1688 /* methods */
1689 (destructor)defdict_dealloc, /* tp_dealloc */
1690 (printfunc)defdict_print, /* tp_print */
1691 0, /* tp_getattr */
1692 0, /* tp_setattr */
1693 0, /* tp_compare */
1694 (reprfunc)defdict_repr, /* tp_repr */
1695 0, /* tp_as_number */
1696 0, /* tp_as_sequence */
1697 0, /* tp_as_mapping */
1698 0, /* tp_hash */
1699 0, /* tp_call */
1700 0, /* tp_str */
1701 PyObject_GenericGetAttr, /* tp_getattro */
1702 0, /* tp_setattro */
1703 0, /* tp_as_buffer */
1704 Py_TPFLAGS_DEFAULT | Py_TPFLAGS_BASETYPE | Py_TPFLAGS_HAVE_GC |
1705 Py_TPFLAGS_HAVE_WEAKREFS, /* tp_flags */
1706 defdict_doc, /* tp_doc */
1707 defdict_traverse, /* tp_traverse */
1708 (inquiry)defdict_tp_clear, /* tp_clear */
1709 0, /* tp_richcompare */
1710 0, /* tp_weaklistoffset*/
1711 0, /* tp_iter */
1712 0, /* tp_iternext */
1713 defdict_methods, /* tp_methods */
1714 defdict_members, /* tp_members */
1715 0, /* tp_getset */
1716 DEFERRED_ADDRESS(&PyDict_Type), /* tp_base */
1717 0, /* tp_dict */
1718 0, /* tp_descr_get */
1719 0, /* tp_descr_set */
1720 0, /* tp_dictoffset */
1721 defdict_init, /* tp_init */
1722 PyType_GenericAlloc, /* tp_alloc */
1723 0, /* tp_new */
1724 PyObject_GC_Del, /* tp_free */
1725 };
1726
1727 /* module level code ********************************************************/
1728
1729 PyDoc_STRVAR(module_doc,
1730 "High performance data structures.\n\
1731 - deque: ordered collection accessible from endpoints only\n\
1732 - defaultdict: dict subclass with a default value factory\n\
1733 ");
1734
1735 PyMODINIT_FUNC
init_collections(void)1736 init_collections(void)
1737 {
1738 PyObject *m;
1739
1740 m = Py_InitModule3("_collections", NULL, module_doc);
1741 if (m == NULL)
1742 return;
1743
1744 if (PyType_Ready(&deque_type) < 0)
1745 return;
1746 Py_INCREF(&deque_type);
1747 PyModule_AddObject(m, "deque", (PyObject *)&deque_type);
1748
1749 defdict_type.tp_base = &PyDict_Type;
1750 if (PyType_Ready(&defdict_type) < 0)
1751 return;
1752 Py_INCREF(&defdict_type);
1753 PyModule_AddObject(m, "defaultdict", (PyObject *)&defdict_type);
1754
1755 if (PyType_Ready(&dequeiter_type) < 0)
1756 return;
1757
1758 if (PyType_Ready(&dequereviter_type) < 0)
1759 return;
1760
1761 return;
1762 }
1763