Mercurial > cpython-lru_cache-weakref

annotate Modules/_collectionsmodule.c @ 64166:d0e9febfa00a 3.1

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