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