blob: fbf07a87a562cfd68cd801076bbe4a2775c66647 [file] [log] [blame]
Raymond Hettinger756b3f32004-01-29 06:37:52 +00001#include "Python.h"
Raymond Hettinger691d8052004-05-30 07:26:47 +00002#include "structmember.h"
Raymond Hettinger756b3f32004-01-29 06:37:52 +00003
Raymond Hettingerc2083082015-02-28 23:29:16 -08004#ifdef STDC_HEADERS
5#include <stddef.h>
6#else
7#include <sys/types.h> /* For size_t */
8#endif
9
Raymond Hettinger756b3f32004-01-29 06:37:52 +000010/* collections module implementation of a deque() datatype
11 Written and maintained by Raymond D. Hettinger <python@rcn.com>
Raymond Hettinger756b3f32004-01-29 06:37:52 +000012*/
13
Raymond Hettinger77e8bf12004-10-01 15:25:53 +000014/* The block length may be set to any number over 1. Larger numbers
Raymond Hettinger20b0f872013-06-23 15:44:33 -070015 * reduce the number of calls to the memory allocator, give faster
Raymond Hettinger30c90742015-03-02 22:31:35 -080016 * indexing and rotation, and reduce the link to data overhead ratio.
Raymond Hettingerdaf57f22015-02-26 23:21:29 -080017 * Making the block length a power of two speeds-up the modulo
Raymond Hettinger30c90742015-03-02 22:31:35 -080018 * and division calculations in deque_item() and deque_ass_item().
Raymond Hettinger77e8bf12004-10-01 15:25:53 +000019 */
20
Raymond Hettingerdaf57f22015-02-26 23:21:29 -080021#define BLOCKLEN 64
Raymond Hettinger61f05fb2004-10-01 06:24:12 +000022#define CENTER ((BLOCKLEN - 1) / 2)
Raymond Hettinger756b3f32004-01-29 06:37:52 +000023
Raymond Hettinger551350a2015-03-24 00:19:53 -070024/* Data for deque objects is stored in a doubly-linked list of fixed
25 * length blocks. This assures that appends or pops never move any
26 * other data elements besides the one being appended or popped.
27 *
28 * Another advantage is that it completely avoids use of realloc(),
29 * resulting in more predictable performance.
30 *
31 * Textbook implementations of doubly-linked lists store one datum
32 * per link, but that gives them a 200% memory overhead (a prev and
33 * next link for each datum) and it costs one malloc() call per data
34 * element. By using fixed-length blocks, the link to data ratio is
35 * significantly improved and there are proportionally fewer calls
36 * to malloc() and free(). The data blocks of consecutive pointers
37 * also improve cache locality.
38 *
Raymond Hettinger61f05fb2004-10-01 06:24:12 +000039 * The list of blocks is never empty, so d.leftblock and d.rightblock
Raymond Hettinger82df9252013-07-07 01:43:42 -100040 * are never equal to NULL. The list is not circular.
41 *
42 * A deque d's first element is at d.leftblock[leftindex]
43 * and its last element is at d.rightblock[rightindex].
Raymond Hettinger61f05fb2004-10-01 06:24:12 +000044 *
Raymond Hettinger551350a2015-03-24 00:19:53 -070045 * Unlike Python slice indices, these indices are inclusive on both
46 * ends. This makes the algorithms for left and right operations
47 * more symmetrical and it simplifies the design.
Raymond Hettinger61f05fb2004-10-01 06:24:12 +000048 *
Raymond Hettinger551350a2015-03-24 00:19:53 -070049 * The indices, d.leftindex and d.rightindex are always in the range:
50 * 0 <= index < BLOCKLEN
51 *
52 * And their exact relationship is:
53 * (d.leftindex + d.len - 1) % BLOCKLEN == d.rightindex
Raymond Hettinger61f05fb2004-10-01 06:24:12 +000054 *
Raymond Hettinger8dbbae22015-03-24 21:01:50 -070055 * Whenever d.leftblock == d.rightblock, then:
Raymond Hettinger551350a2015-03-24 00:19:53 -070056 * d.leftindex + d.len - 1 == d.rightindex
Thomas Wouters0e3f5912006-08-11 14:57:12 +000057 *
Raymond Hettinger551350a2015-03-24 00:19:53 -070058 * However, when d.leftblock != d.rightblock, the d.leftindex and
59 * d.rightindex become indices into distinct blocks and either may
60 * be larger than the other.
61 *
62 * Empty deques have:
63 * d.len == 0
64 * d.leftblock == d.rightblock
65 * d.leftindex == CENTER + 1
66 * d.rightindex == CENTER
67 *
68 * Checking for d.len == 0 is the intended way to see whether d is empty.
Tim Petersd8768d32004-10-01 01:32:53 +000069 */
70
Raymond Hettinger756b3f32004-01-29 06:37:52 +000071typedef struct BLOCK {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +000072 struct BLOCK *leftlink;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +000073 PyObject *data[BLOCKLEN];
Raymond Hettinger20b0f872013-06-23 15:44:33 -070074 struct BLOCK *rightlink;
Raymond Hettinger756b3f32004-01-29 06:37:52 +000075} block;
76
Raymond Hettinger30c90742015-03-02 22:31:35 -080077typedef struct {
78 PyObject_VAR_HEAD
79 block *leftblock;
80 block *rightblock;
Raymond Hettinger551350a2015-03-24 00:19:53 -070081 Py_ssize_t leftindex; /* 0 <= leftindex < BLOCKLEN */
82 Py_ssize_t rightindex; /* 0 <= rightindex < BLOCKLEN */
Raymond Hettingerf9d9c792015-03-02 22:47:46 -080083 size_t state; /* incremented whenever the indices move */
Raymond Hettinger30c90742015-03-02 22:31:35 -080084 Py_ssize_t maxlen;
Raymond Hettinger0f6f9472015-03-21 01:42:10 -070085 PyObject *weakreflist;
Raymond Hettinger30c90742015-03-02 22:31:35 -080086} dequeobject;
87
88static PyTypeObject deque_type;
89
Raymond Hettinger82df9252013-07-07 01:43:42 -100090/* For debug builds, add error checking to track the endpoints
91 * in the chain of links. The goal is to make sure that link
92 * assignments only take place at endpoints so that links already
93 * in use do not get overwritten.
94 *
95 * CHECK_END should happen before each assignment to a block's link field.
96 * MARK_END should happen whenever a link field becomes a new endpoint.
97 * This happens when new blocks are added or whenever an existing
98 * block is freed leaving another existing block as the new endpoint.
99 */
100
Raymond Hettinger3223dd52013-07-26 23:14:22 -0700101#ifndef NDEBUG
Raymond Hettinger82df9252013-07-07 01:43:42 -1000102#define MARK_END(link) link = NULL;
103#define CHECK_END(link) assert(link == NULL);
104#define CHECK_NOT_END(link) assert(link != NULL);
105#else
106#define MARK_END(link)
107#define CHECK_END(link)
108#define CHECK_NOT_END(link)
109#endif
110
111/* A simple freelisting scheme is used to minimize calls to the memory
Raymond Hettinger551350a2015-03-24 00:19:53 -0700112 allocator. It accommodates common use cases where new blocks are being
Raymond Hettinger82df9252013-07-07 01:43:42 -1000113 added at about the same rate as old blocks are being freed.
114 */
115
Raymond Hettingerf2b02ce2015-09-26 17:47:02 -0700116#define MAXFREEBLOCKS 16
Benjamin Petersond6313712008-07-31 16:23:04 +0000117static Py_ssize_t numfreeblocks = 0;
Guido van Rossum58da9312007-11-10 23:39:45 +0000118static block *freeblocks[MAXFREEBLOCKS];
119
Tim Peters6f853562004-10-01 01:04:50 +0000120static block *
Raymond Hettingerdb41fd42015-10-22 22:48:16 -0700121newblock(void) {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000122 block *b;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000123 if (numfreeblocks) {
Raymond Hettinger59cf23a2013-02-07 00:57:19 -0500124 numfreeblocks--;
Raymond Hettinger82df9252013-07-07 01:43:42 -1000125 return freeblocks[numfreeblocks];
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000126 }
Raymond Hettinger82df9252013-07-07 01:43:42 -1000127 b = PyMem_Malloc(sizeof(block));
128 if (b != NULL) {
129 return b;
130 }
131 PyErr_NoMemory();
132 return NULL;
Raymond Hettinger756b3f32004-01-29 06:37:52 +0000133}
134
Martin v. Löwis59683e82008-06-13 07:50:45 +0000135static void
Guido van Rossum58da9312007-11-10 23:39:45 +0000136freeblock(block *b)
137{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000138 if (numfreeblocks < MAXFREEBLOCKS) {
139 freeblocks[numfreeblocks] = b;
140 numfreeblocks++;
141 } else {
142 PyMem_Free(b);
143 }
Guido van Rossum58da9312007-11-10 23:39:45 +0000144}
145
Raymond Hettinger756b3f32004-01-29 06:37:52 +0000146static PyObject *
147deque_new(PyTypeObject *type, PyObject *args, PyObject *kwds)
148{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000149 dequeobject *deque;
150 block *b;
Raymond Hettinger756b3f32004-01-29 06:37:52 +0000151
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000152 /* create dequeobject structure */
153 deque = (dequeobject *)type->tp_alloc(type, 0);
154 if (deque == NULL)
155 return NULL;
Tim Peters1065f752004-10-01 01:03:29 +0000156
Raymond Hettingerdb41fd42015-10-22 22:48:16 -0700157 b = newblock();
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000158 if (b == NULL) {
159 Py_DECREF(deque);
160 return NULL;
161 }
Raymond Hettinger82df9252013-07-07 01:43:42 -1000162 MARK_END(b->leftlink);
163 MARK_END(b->rightlink);
Raymond Hettinger756b3f32004-01-29 06:37:52 +0000164
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000165 assert(BLOCKLEN >= 2);
Raymond Hettinger87e69122015-03-02 23:32:02 -0800166 Py_SIZE(deque) = 0;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000167 deque->leftblock = b;
168 deque->rightblock = b;
169 deque->leftindex = CENTER + 1;
170 deque->rightindex = CENTER;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000171 deque->state = 0;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000172 deque->maxlen = -1;
Raymond Hettinger87e69122015-03-02 23:32:02 -0800173 deque->weakreflist = NULL;
Raymond Hettinger756b3f32004-01-29 06:37:52 +0000174
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000175 return (PyObject *)deque;
Raymond Hettinger756b3f32004-01-29 06:37:52 +0000176}
177
178static PyObject *
Raymond Hettinger756b3f32004-01-29 06:37:52 +0000179deque_pop(dequeobject *deque, PyObject *unused)
180{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000181 PyObject *item;
182 block *prevblock;
Raymond Hettinger756b3f32004-01-29 06:37:52 +0000183
Raymond Hettingerdf715ba2013-07-06 13:01:13 -1000184 if (Py_SIZE(deque) == 0) {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000185 PyErr_SetString(PyExc_IndexError, "pop from an empty deque");
186 return NULL;
187 }
188 item = deque->rightblock->data[deque->rightindex];
189 deque->rightindex--;
Raymond Hettingerdf715ba2013-07-06 13:01:13 -1000190 Py_SIZE(deque)--;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000191 deque->state++;
Raymond Hettinger756b3f32004-01-29 06:37:52 +0000192
Raymond Hettingerd3d2b2c2015-09-21 23:41:56 -0700193 if (deque->rightindex < 0) {
Raymond Hettinger8dbbae22015-03-24 21:01:50 -0700194 if (Py_SIZE(deque)) {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000195 prevblock = deque->rightblock->leftlink;
196 assert(deque->leftblock != deque->rightblock);
197 freeblock(deque->rightblock);
Raymond Hettinger82df9252013-07-07 01:43:42 -1000198 CHECK_NOT_END(prevblock);
199 MARK_END(prevblock->rightlink);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000200 deque->rightblock = prevblock;
201 deque->rightindex = BLOCKLEN - 1;
Raymond Hettinger8dbbae22015-03-24 21:01:50 -0700202 } else {
203 assert(deque->leftblock == deque->rightblock);
204 assert(deque->leftindex == deque->rightindex+1);
205 /* re-center instead of freeing a block */
206 deque->leftindex = CENTER + 1;
207 deque->rightindex = CENTER;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000208 }
209 }
210 return item;
Raymond Hettinger756b3f32004-01-29 06:37:52 +0000211}
212
213PyDoc_STRVAR(pop_doc, "Remove and return the rightmost element.");
214
215static PyObject *
216deque_popleft(dequeobject *deque, PyObject *unused)
217{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000218 PyObject *item;
219 block *prevblock;
Raymond Hettinger756b3f32004-01-29 06:37:52 +0000220
Raymond Hettingerdf715ba2013-07-06 13:01:13 -1000221 if (Py_SIZE(deque) == 0) {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000222 PyErr_SetString(PyExc_IndexError, "pop from an empty deque");
223 return NULL;
224 }
225 assert(deque->leftblock != NULL);
226 item = deque->leftblock->data[deque->leftindex];
227 deque->leftindex++;
Raymond Hettingerdf715ba2013-07-06 13:01:13 -1000228 Py_SIZE(deque)--;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000229 deque->state++;
Raymond Hettinger756b3f32004-01-29 06:37:52 +0000230
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000231 if (deque->leftindex == BLOCKLEN) {
Raymond Hettinger8dbbae22015-03-24 21:01:50 -0700232 if (Py_SIZE(deque)) {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000233 assert(deque->leftblock != deque->rightblock);
234 prevblock = deque->leftblock->rightlink;
235 freeblock(deque->leftblock);
Raymond Hettinger82df9252013-07-07 01:43:42 -1000236 CHECK_NOT_END(prevblock);
237 MARK_END(prevblock->leftlink);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000238 deque->leftblock = prevblock;
239 deque->leftindex = 0;
Raymond Hettinger8dbbae22015-03-24 21:01:50 -0700240 } else {
241 assert(deque->leftblock == deque->rightblock);
242 assert(deque->leftindex == deque->rightindex+1);
243 /* re-center instead of freeing a block */
244 deque->leftindex = CENTER + 1;
245 deque->rightindex = CENTER;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000246 }
247 }
248 return item;
Raymond Hettinger756b3f32004-01-29 06:37:52 +0000249}
250
251PyDoc_STRVAR(popleft_doc, "Remove and return the leftmost element.");
252
Raymond Hettingerf30f5b92015-03-02 22:23:37 -0800253/* The deque's size limit is d.maxlen. The limit can be zero or positive.
254 * If there is no limit, then d.maxlen == -1.
255 *
Raymond Hettingera4b13d02015-10-15 08:05:31 -0700256 * After an item is added to a deque, we check to see if the size has
257 * grown past the limit. If it has, we get the size back down to the limit
258 * by popping an item off of the opposite end. The methods that can
259 * trigger this are append(), appendleft(), extend(), and extendleft().
Raymond Hettingerd96db092015-10-11 22:34:48 -0700260 *
261 * The macro to check whether a deque needs to be trimmed uses a single
262 * unsigned test that returns true whenever 0 <= maxlen < Py_SIZE(deque).
Raymond Hettingerf30f5b92015-03-02 22:23:37 -0800263 */
264
Raymond Hettingerd96db092015-10-11 22:34:48 -0700265#define NEEDS_TRIM(deque, maxlen) ((size_t)(maxlen) < (size_t)(Py_SIZE(deque)))
Raymond Hettingerf30f5b92015-03-02 22:23:37 -0800266
Raymond Hettinger3ba85c22004-02-06 19:04:56 +0000267static PyObject *
Guido van Rossum8ce8a782007-11-01 19:42:39 +0000268deque_append(dequeobject *deque, PyObject *item)
269{
Raymond Hettinger8dbbae22015-03-24 21:01:50 -0700270 if (deque->rightindex == BLOCKLEN - 1) {
Raymond Hettingerdb41fd42015-10-22 22:48:16 -0700271 block *b = newblock();
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000272 if (b == NULL)
273 return NULL;
Raymond Hettinger82df9252013-07-07 01:43:42 -1000274 b->leftlink = deque->rightblock;
275 CHECK_END(deque->rightblock->rightlink);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000276 deque->rightblock->rightlink = b;
277 deque->rightblock = b;
Raymond Hettinger82df9252013-07-07 01:43:42 -1000278 MARK_END(b->rightlink);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000279 deque->rightindex = -1;
280 }
Raymond Hettingerdf715ba2013-07-06 13:01:13 -1000281 Py_SIZE(deque)++;
Raymond Hettinger7c0b70f2015-09-26 21:11:05 -0700282 Py_INCREF(item);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000283 deque->rightindex++;
284 deque->rightblock->data[deque->rightindex] = item;
Raymond Hettingerd96db092015-10-11 22:34:48 -0700285 if (NEEDS_TRIM(deque, deque->maxlen)) {
Raymond Hettinger1286d142015-10-14 23:16:57 -0700286 PyObject *olditem = deque_popleft(deque, NULL);
287 Py_DECREF(olditem);
Raymond Hettinger0f43bb12015-10-20 00:03:33 -0700288 } else {
289 deque->state++;
Raymond Hettingerd96db092015-10-11 22:34:48 -0700290 }
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000291 Py_RETURN_NONE;
Guido van Rossum8ce8a782007-11-01 19:42:39 +0000292}
293
294PyDoc_STRVAR(append_doc, "Add an element to the right side of the deque.");
295
296static PyObject *
297deque_appendleft(dequeobject *deque, PyObject *item)
298{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000299 if (deque->leftindex == 0) {
Raymond Hettingerdb41fd42015-10-22 22:48:16 -0700300 block *b = newblock();
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000301 if (b == NULL)
302 return NULL;
Raymond Hettinger82df9252013-07-07 01:43:42 -1000303 b->rightlink = deque->leftblock;
304 CHECK_END(deque->leftblock->leftlink);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000305 deque->leftblock->leftlink = b;
306 deque->leftblock = b;
Raymond Hettinger82df9252013-07-07 01:43:42 -1000307 MARK_END(b->leftlink);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000308 deque->leftindex = BLOCKLEN;
309 }
Raymond Hettingerdf715ba2013-07-06 13:01:13 -1000310 Py_SIZE(deque)++;
Raymond Hettinger7c0b70f2015-09-26 21:11:05 -0700311 Py_INCREF(item);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000312 deque->leftindex--;
313 deque->leftblock->data[deque->leftindex] = item;
Raymond Hettingerd96db092015-10-11 22:34:48 -0700314 if (NEEDS_TRIM(deque, deque->maxlen)) {
Raymond Hettinger1286d142015-10-14 23:16:57 -0700315 PyObject *olditem = deque_pop(deque, NULL);
316 Py_DECREF(olditem);
Raymond Hettinger0f43bb12015-10-20 00:03:33 -0700317 } else {
318 deque->state++;
Raymond Hettingerd96db092015-10-11 22:34:48 -0700319 }
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000320 Py_RETURN_NONE;
Guido van Rossum8ce8a782007-11-01 19:42:39 +0000321}
322
323PyDoc_STRVAR(appendleft_doc, "Add an element to the left side of the deque.");
324
Raymond Hettingerfd265f42015-10-02 23:17:33 -0700325static PyObject*
326finalize_iterator(PyObject *it)
327{
328 if (PyErr_Occurred()) {
329 if (PyErr_ExceptionMatches(PyExc_StopIteration))
330 PyErr_Clear();
331 else {
332 Py_DECREF(it);
333 return NULL;
334 }
335 }
336 Py_DECREF(it);
337 Py_RETURN_NONE;
338}
Raymond Hettinger060c7f62009-03-10 09:36:07 +0000339
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000340/* Run an iterator to exhaustion. Shortcut for
Raymond Hettinger060c7f62009-03-10 09:36:07 +0000341 the extend/extendleft methods when maxlen == 0. */
342static PyObject*
343consume_iterator(PyObject *it)
344{
Raymond Hettingerfd265f42015-10-02 23:17:33 -0700345 PyObject *(*iternext)(PyObject *);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000346 PyObject *item;
Raymond Hettinger060c7f62009-03-10 09:36:07 +0000347
Raymond Hettingerfd265f42015-10-02 23:17:33 -0700348 iternext = *Py_TYPE(it)->tp_iternext;
349 while ((item = iternext(it)) != NULL) {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000350 Py_DECREF(item);
351 }
Raymond Hettingerfd265f42015-10-02 23:17:33 -0700352 return finalize_iterator(it);
Raymond Hettinger060c7f62009-03-10 09:36:07 +0000353}
354
Guido van Rossum8ce8a782007-11-01 19:42:39 +0000355static PyObject *
Raymond Hettinger3ba85c22004-02-06 19:04:56 +0000356deque_extend(dequeobject *deque, PyObject *iterable)
357{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000358 PyObject *it, *item;
Raymond Hettinger7a845522015-09-26 01:30:51 -0700359 PyObject *(*iternext)(PyObject *);
Raymond Hettinger6b1e1132015-10-11 09:43:50 -0700360 Py_ssize_t maxlen = deque->maxlen;
Raymond Hettinger3ba85c22004-02-06 19:04:56 +0000361
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000362 /* Handle case where id(deque) == id(iterable) */
363 if ((PyObject *)deque == iterable) {
364 PyObject *result;
365 PyObject *s = PySequence_List(iterable);
366 if (s == NULL)
367 return NULL;
368 result = deque_extend(deque, s);
369 Py_DECREF(s);
370 return result;
371 }
Raymond Hettinger3f9afd82009-12-10 03:03:02 +0000372
Raymond Hettingerd9c116c2013-07-09 00:13:21 -0700373 /* Space saving heuristic. Start filling from the left */
374 if (Py_SIZE(deque) == 0) {
375 assert(deque->leftblock == deque->rightblock);
376 assert(deque->leftindex == deque->rightindex+1);
377 deque->leftindex = 1;
378 deque->rightindex = 0;
379 }
380
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000381 it = PyObject_GetIter(iterable);
382 if (it == NULL)
383 return NULL;
Raymond Hettinger3ba85c22004-02-06 19:04:56 +0000384
Raymond Hettinger965362e2015-10-11 22:52:54 -0700385 if (maxlen == 0)
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000386 return consume_iterator(it);
Raymond Hettinger060c7f62009-03-10 09:36:07 +0000387
Raymond Hettinger7a845522015-09-26 01:30:51 -0700388 iternext = *Py_TYPE(it)->tp_iternext;
389 while ((item = iternext(it)) != NULL) {
Raymond Hettinger8dbbae22015-03-24 21:01:50 -0700390 if (deque->rightindex == BLOCKLEN - 1) {
Raymond Hettingerdb41fd42015-10-22 22:48:16 -0700391 block *b = newblock();
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000392 if (b == NULL) {
393 Py_DECREF(item);
394 Py_DECREF(it);
395 return NULL;
396 }
Raymond Hettinger82df9252013-07-07 01:43:42 -1000397 b->leftlink = deque->rightblock;
398 CHECK_END(deque->rightblock->rightlink);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000399 deque->rightblock->rightlink = b;
400 deque->rightblock = b;
Raymond Hettinger82df9252013-07-07 01:43:42 -1000401 MARK_END(b->rightlink);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000402 deque->rightindex = -1;
403 }
Raymond Hettingerdf715ba2013-07-06 13:01:13 -1000404 Py_SIZE(deque)++;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000405 deque->rightindex++;
406 deque->rightblock->data[deque->rightindex] = item;
Raymond Hettingerd96db092015-10-11 22:34:48 -0700407 if (NEEDS_TRIM(deque, maxlen)) {
Raymond Hettinger1286d142015-10-14 23:16:57 -0700408 PyObject *olditem = deque_popleft(deque, NULL);
409 Py_DECREF(olditem);
Raymond Hettinger0f43bb12015-10-20 00:03:33 -0700410 } else {
411 deque->state++;
Raymond Hettinger6b1e1132015-10-11 09:43:50 -0700412 }
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000413 }
Raymond Hettingerfd265f42015-10-02 23:17:33 -0700414 return finalize_iterator(it);
Raymond Hettinger3ba85c22004-02-06 19:04:56 +0000415}
416
Tim Peters1065f752004-10-01 01:03:29 +0000417PyDoc_STRVAR(extend_doc,
Raymond Hettinger3ba85c22004-02-06 19:04:56 +0000418"Extend the right side of the deque with elements from the iterable");
419
420static PyObject *
421deque_extendleft(dequeobject *deque, PyObject *iterable)
422{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000423 PyObject *it, *item;
Raymond Hettinger7a845522015-09-26 01:30:51 -0700424 PyObject *(*iternext)(PyObject *);
Raymond Hettinger6b1e1132015-10-11 09:43:50 -0700425 Py_ssize_t maxlen = deque->maxlen;
Raymond Hettinger3ba85c22004-02-06 19:04:56 +0000426
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000427 /* Handle case where id(deque) == id(iterable) */
428 if ((PyObject *)deque == iterable) {
429 PyObject *result;
430 PyObject *s = PySequence_List(iterable);
431 if (s == NULL)
432 return NULL;
433 result = deque_extendleft(deque, s);
434 Py_DECREF(s);
435 return result;
436 }
Raymond Hettinger3f9afd82009-12-10 03:03:02 +0000437
Raymond Hettingerd9c116c2013-07-09 00:13:21 -0700438 /* Space saving heuristic. Start filling from the right */
439 if (Py_SIZE(deque) == 0) {
440 assert(deque->leftblock == deque->rightblock);
441 assert(deque->leftindex == deque->rightindex+1);
442 deque->leftindex = BLOCKLEN - 1;
443 deque->rightindex = BLOCKLEN - 2;
444 }
445
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000446 it = PyObject_GetIter(iterable);
447 if (it == NULL)
448 return NULL;
Raymond Hettinger3ba85c22004-02-06 19:04:56 +0000449
Raymond Hettinger965362e2015-10-11 22:52:54 -0700450 if (maxlen == 0)
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000451 return consume_iterator(it);
Raymond Hettinger060c7f62009-03-10 09:36:07 +0000452
Raymond Hettinger7a845522015-09-26 01:30:51 -0700453 iternext = *Py_TYPE(it)->tp_iternext;
454 while ((item = iternext(it)) != NULL) {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000455 if (deque->leftindex == 0) {
Raymond Hettingerdb41fd42015-10-22 22:48:16 -0700456 block *b = newblock();
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000457 if (b == NULL) {
458 Py_DECREF(item);
459 Py_DECREF(it);
460 return NULL;
461 }
Raymond Hettinger82df9252013-07-07 01:43:42 -1000462 b->rightlink = deque->leftblock;
463 CHECK_END(deque->leftblock->leftlink);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000464 deque->leftblock->leftlink = b;
465 deque->leftblock = b;
Raymond Hettinger82df9252013-07-07 01:43:42 -1000466 MARK_END(b->leftlink);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000467 deque->leftindex = BLOCKLEN;
468 }
Raymond Hettingerdf715ba2013-07-06 13:01:13 -1000469 Py_SIZE(deque)++;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000470 deque->leftindex--;
471 deque->leftblock->data[deque->leftindex] = item;
Raymond Hettingerd96db092015-10-11 22:34:48 -0700472 if (NEEDS_TRIM(deque, maxlen)) {
Raymond Hettinger1286d142015-10-14 23:16:57 -0700473 PyObject *olditem = deque_pop(deque, NULL);
474 Py_DECREF(olditem);
Raymond Hettinger0f43bb12015-10-20 00:03:33 -0700475 } else {
476 deque->state++;
Raymond Hettinger6b1e1132015-10-11 09:43:50 -0700477 }
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000478 }
Raymond Hettingerfd265f42015-10-02 23:17:33 -0700479 return finalize_iterator(it);
Raymond Hettinger3ba85c22004-02-06 19:04:56 +0000480}
481
Tim Peters1065f752004-10-01 01:03:29 +0000482PyDoc_STRVAR(extendleft_doc,
Raymond Hettinger3ba85c22004-02-06 19:04:56 +0000483"Extend the left side of the deque with elements from the iterable");
484
Raymond Hettinger3f9afd82009-12-10 03:03:02 +0000485static PyObject *
486deque_inplace_concat(dequeobject *deque, PyObject *other)
487{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000488 PyObject *result;
Raymond Hettinger3f9afd82009-12-10 03:03:02 +0000489
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000490 result = deque_extend(deque, other);
491 if (result == NULL)
492 return result;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000493 Py_INCREF(deque);
Raymond Hettinger2b2b7532015-09-05 17:05:52 -0700494 Py_DECREF(result);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000495 return (PyObject *)deque;
Raymond Hettinger3f9afd82009-12-10 03:03:02 +0000496}
497
Raymond Hettinger8299e9b2015-09-26 21:31:23 -0700498static PyObject *
499deque_copy(PyObject *deque)
500{
501 dequeobject *old_deque = (dequeobject *)deque;
502 if (Py_TYPE(deque) == &deque_type) {
503 dequeobject *new_deque;
504 PyObject *rv;
505
506 new_deque = (dequeobject *)deque_new(&deque_type, (PyObject *)NULL, (PyObject *)NULL);
507 if (new_deque == NULL)
508 return NULL;
509 new_deque->maxlen = old_deque->maxlen;
510 /* Fast path for the deque_repeat() common case where len(deque) == 1 */
Raymond Hettinger0443ac22015-10-05 22:52:37 -0400511 if (Py_SIZE(deque) == 1) {
Raymond Hettinger8299e9b2015-09-26 21:31:23 -0700512 PyObject *item = old_deque->leftblock->data[old_deque->leftindex];
513 rv = deque_append(new_deque, item);
514 } else {
515 rv = deque_extend(new_deque, deque);
516 }
517 if (rv != NULL) {
518 Py_DECREF(rv);
519 return (PyObject *)new_deque;
520 }
521 Py_DECREF(new_deque);
522 return NULL;
523 }
524 if (old_deque->maxlen < 0)
525 return PyObject_CallFunction((PyObject *)(Py_TYPE(deque)), "O", deque, NULL);
526 else
527 return PyObject_CallFunction((PyObject *)(Py_TYPE(deque)), "Oi",
528 deque, old_deque->maxlen, NULL);
529}
530
531PyDoc_STRVAR(copy_doc, "Return a shallow copy of a deque.");
Raymond Hettinger41290a62015-03-31 08:12:23 -0700532
533static PyObject *
534deque_concat(dequeobject *deque, PyObject *other)
535{
Benjamin Peterson1a629212015-04-04 10:52:36 -0400536 PyObject *new_deque, *result;
Raymond Hettinger41290a62015-03-31 08:12:23 -0700537 int rv;
538
539 rv = PyObject_IsInstance(other, (PyObject *)&deque_type);
540 if (rv <= 0) {
541 if (rv == 0) {
542 PyErr_Format(PyExc_TypeError,
543 "can only concatenate deque (not \"%.200s\") to deque",
544 other->ob_type->tp_name);
545 }
546 return NULL;
547 }
548
549 new_deque = deque_copy((PyObject *)deque);
550 if (new_deque == NULL)
551 return NULL;
Benjamin Peterson1a629212015-04-04 10:52:36 -0400552 result = deque_extend((dequeobject *)new_deque, other);
553 if (result == NULL) {
554 Py_DECREF(new_deque);
555 return NULL;
556 }
557 Py_DECREF(result);
558 return new_deque;
Raymond Hettinger41290a62015-03-31 08:12:23 -0700559}
560
Raymond Hettinger8299e9b2015-09-26 21:31:23 -0700561static void
562deque_clear(dequeobject *deque)
563{
564 block *b;
565 block *prevblock;
566 block *leftblock;
567 Py_ssize_t leftindex;
568 Py_ssize_t n;
569 PyObject *item;
570
Raymond Hettinger38031142015-09-29 22:45:05 -0700571 if (Py_SIZE(deque) == 0)
572 return;
573
Raymond Hettinger8299e9b2015-09-26 21:31:23 -0700574 /* During the process of clearing a deque, decrefs can cause the
575 deque to mutate. To avoid fatal confusion, we have to make the
576 deque empty before clearing the blocks and never refer to
577 anything via deque->ref while clearing. (This is the same
578 technique used for clearing lists, sets, and dicts.)
579
580 Making the deque empty requires allocating a new empty block. In
581 the unlikely event that memory is full, we fall back to an
582 alternate method that doesn't require a new block. Repeating
583 pops in a while-loop is slower, possibly re-entrant (and a clever
584 adversary could cause it to never terminate).
585 */
586
Raymond Hettingerdb41fd42015-10-22 22:48:16 -0700587 b = newblock();
Raymond Hettinger8299e9b2015-09-26 21:31:23 -0700588 if (b == NULL) {
589 PyErr_Clear();
590 goto alternate_method;
591 }
592
593 /* Remember the old size, leftblock, and leftindex */
594 leftblock = deque->leftblock;
595 leftindex = deque->leftindex;
596 n = Py_SIZE(deque);
597
598 /* Set the deque to be empty using the newly allocated block */
599 MARK_END(b->leftlink);
600 MARK_END(b->rightlink);
601 Py_SIZE(deque) = 0;
602 deque->leftblock = b;
603 deque->rightblock = b;
604 deque->leftindex = CENTER + 1;
605 deque->rightindex = CENTER;
606 deque->state++;
607
608 /* Now the old size, leftblock, and leftindex are disconnected from
609 the empty deque and we can use them to decref the pointers.
610 */
611 while (n--) {
612 item = leftblock->data[leftindex];
613 Py_DECREF(item);
614 leftindex++;
615 if (leftindex == BLOCKLEN && n) {
616 CHECK_NOT_END(leftblock->rightlink);
617 prevblock = leftblock;
618 leftblock = leftblock->rightlink;
619 leftindex = 0;
620 freeblock(prevblock);
621 }
622 }
623 CHECK_END(leftblock->rightlink);
624 freeblock(leftblock);
625 return;
626
627 alternate_method:
628 while (Py_SIZE(deque)) {
629 item = deque_pop(deque, NULL);
630 assert (item != NULL);
631 Py_DECREF(item);
632 }
633}
634
635static PyObject *
636deque_clearmethod(dequeobject *deque)
637{
638 deque_clear(deque);
639 Py_RETURN_NONE;
640}
641
642PyDoc_STRVAR(clear_doc, "Remove all elements from the deque.");
Raymond Hettinger41290a62015-03-31 08:12:23 -0700643
644static PyObject *
Raymond Hettinger41290a62015-03-31 08:12:23 -0700645deque_inplace_repeat(dequeobject *deque, Py_ssize_t n)
646{
Raymond Hettingerc22eee62015-09-26 02:14:50 -0700647 Py_ssize_t i, m, size;
Raymond Hettinger41290a62015-03-31 08:12:23 -0700648 PyObject *seq;
649 PyObject *rv;
650
651 size = Py_SIZE(deque);
652 if (size == 0 || n == 1) {
653 Py_INCREF(deque);
654 return (PyObject *)deque;
655 }
656
657 if (n <= 0) {
658 deque_clear(deque);
659 Py_INCREF(deque);
660 return (PyObject *)deque;
661 }
662
Raymond Hettinger41290a62015-03-31 08:12:23 -0700663 if (size == 1) {
664 /* common case, repeating a single element */
665 PyObject *item = deque->leftblock->data[deque->leftindex];
666
Raymond Hettingera7f630092015-10-10 23:56:02 -0400667 if (deque->maxlen >= 0 && n > deque->maxlen)
Raymond Hettinger41290a62015-03-31 08:12:23 -0700668 n = deque->maxlen;
669
Raymond Hettinger67c78b52015-09-12 11:00:20 -0400670 deque->state++;
Raymond Hettingerad262252015-09-14 01:03:04 -0400671 for (i = 0 ; i < n-1 ; ) {
Raymond Hettinger67c78b52015-09-12 11:00:20 -0400672 if (deque->rightindex == BLOCKLEN - 1) {
Raymond Hettingerdb41fd42015-10-22 22:48:16 -0700673 block *b = newblock();
Raymond Hettinger67c78b52015-09-12 11:00:20 -0400674 if (b == NULL) {
675 Py_SIZE(deque) += i;
676 return NULL;
677 }
678 b->leftlink = deque->rightblock;
679 CHECK_END(deque->rightblock->rightlink);
680 deque->rightblock->rightlink = b;
681 deque->rightblock = b;
682 MARK_END(b->rightlink);
683 deque->rightindex = -1;
684 }
Raymond Hettingerc22eee62015-09-26 02:14:50 -0700685 m = n - 1 - i;
686 if (m > BLOCKLEN - 1 - deque->rightindex)
687 m = BLOCKLEN - 1 - deque->rightindex;
688 i += m;
689 while (m--) {
Raymond Hettingerad262252015-09-14 01:03:04 -0400690 deque->rightindex++;
691 Py_INCREF(item);
692 deque->rightblock->data[deque->rightindex] = item;
693 }
Raymond Hettinger41290a62015-03-31 08:12:23 -0700694 }
Raymond Hettinger67c78b52015-09-12 11:00:20 -0400695 Py_SIZE(deque) += i;
Raymond Hettinger41290a62015-03-31 08:12:23 -0700696 Py_INCREF(deque);
697 return (PyObject *)deque;
698 }
699
Raymond Hettinger20151f52015-10-16 22:47:29 -0700700 if ((size_t)size > PY_SSIZE_T_MAX / (size_t)n) {
Raymond Hettingerf5d72f32015-09-09 22:39:44 -0400701 return PyErr_NoMemory();
702 }
703
Raymond Hettinger41290a62015-03-31 08:12:23 -0700704 seq = PySequence_List((PyObject *)deque);
705 if (seq == NULL)
706 return seq;
707
708 for (i = 0 ; i < n-1 ; i++) {
709 rv = deque_extend(deque, seq);
710 if (rv == NULL) {
711 Py_DECREF(seq);
712 return NULL;
713 }
714 Py_DECREF(rv);
715 }
716 Py_INCREF(deque);
717 Py_DECREF(seq);
718 return (PyObject *)deque;
719}
720
Raymond Hettingerf5d72f32015-09-09 22:39:44 -0400721static PyObject *
722deque_repeat(dequeobject *deque, Py_ssize_t n)
723{
724 dequeobject *new_deque;
Raymond Hettinger95e2cc52015-09-13 02:41:18 -0400725 PyObject *rv;
Raymond Hettingerf5d72f32015-09-09 22:39:44 -0400726
727 new_deque = (dequeobject *)deque_copy((PyObject *) deque);
728 if (new_deque == NULL)
729 return NULL;
Raymond Hettinger95e2cc52015-09-13 02:41:18 -0400730 rv = deque_inplace_repeat(new_deque, n);
731 Py_DECREF(new_deque);
732 return rv;
Raymond Hettingerf5d72f32015-09-09 22:39:44 -0400733}
734
Raymond Hettinger54023152014-04-23 00:58:48 -0700735/* The rotate() method is part of the public API and is used internally
736as a primitive for other methods.
737
738Rotation by 1 or -1 is a common case, so any optimizations for high
739volume rotations should take care not to penalize the common case.
740
741Conceptually, a rotate by one is equivalent to a pop on one side and an
742append on the other. However, a pop/append pair is unnecessarily slow
Martin Panterd2ad5712015-11-02 04:20:33 +0000743because it requires an incref/decref pair for an object located randomly
Raymond Hettinger54023152014-04-23 00:58:48 -0700744in memory. It is better to just move the object pointer from one block
745to the next without changing the reference count.
746
747When moving batches of pointers, it is tempting to use memcpy() but that
748proved to be slower than a simple loop for a variety of reasons.
749Memcpy() cannot know in advance that we're copying pointers instead of
750bytes, that the source and destination are pointer aligned and
751non-overlapping, that moving just one pointer is a common case, that we
752never need to move more than BLOCKLEN pointers, and that at least one
753pointer is always moved.
754
755For high volume rotations, newblock() and freeblock() are never called
756more than once. Previously emptied blocks are immediately reused as a
757destination block. If a block is left-over at the end, it is freed.
758*/
759
Raymond Hettingerdcb9d942004-10-09 16:02:18 +0000760static int
Martin v. Löwis18e16552006-02-15 17:27:45 +0000761_deque_rotate(dequeobject *deque, Py_ssize_t n)
Raymond Hettinger5c5eb862004-02-07 21:13:00 +0000762{
Raymond Hettinger3959af92013-07-13 02:34:08 -0700763 block *b = NULL;
Raymond Hettinger20b0f872013-06-23 15:44:33 -0700764 block *leftblock = deque->leftblock;
765 block *rightblock = deque->rightblock;
766 Py_ssize_t leftindex = deque->leftindex;
767 Py_ssize_t rightindex = deque->rightindex;
Raymond Hettingerdf715ba2013-07-06 13:01:13 -1000768 Py_ssize_t len=Py_SIZE(deque), halflen=len>>1;
Raymond Hettinger3959af92013-07-13 02:34:08 -0700769 int rv = -1;
Raymond Hettinger5c5eb862004-02-07 21:13:00 +0000770
Raymond Hettinger464d89b2013-01-11 22:29:50 -0800771 if (len <= 1)
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000772 return 0;
773 if (n > halflen || n < -halflen) {
774 n %= len;
775 if (n > halflen)
776 n -= len;
777 else if (n < -halflen)
778 n += len;
779 }
Raymond Hettinger1f0044c2013-02-05 01:30:46 -0500780 assert(len > 1);
Raymond Hettingera4409c12013-02-04 00:08:12 -0500781 assert(-halflen <= n && n <= halflen);
Raymond Hettinger231ee4d2013-02-02 11:24:43 -0800782
Raymond Hettinger464d89b2013-01-11 22:29:50 -0800783 deque->state++;
Raymond Hettinger1f0044c2013-02-05 01:30:46 -0500784 while (n > 0) {
Raymond Hettinger20b0f872013-06-23 15:44:33 -0700785 if (leftindex == 0) {
Raymond Hettinger20b0f872013-06-23 15:44:33 -0700786 if (b == NULL) {
Raymond Hettingerdb41fd42015-10-22 22:48:16 -0700787 b = newblock();
Raymond Hettinger3959af92013-07-13 02:34:08 -0700788 if (b == NULL)
789 goto done;
Raymond Hettinger20b0f872013-06-23 15:44:33 -0700790 }
Raymond Hettinger82df9252013-07-07 01:43:42 -1000791 b->rightlink = leftblock;
792 CHECK_END(leftblock->leftlink);
Raymond Hettinger20b0f872013-06-23 15:44:33 -0700793 leftblock->leftlink = b;
794 leftblock = b;
Raymond Hettinger82df9252013-07-07 01:43:42 -1000795 MARK_END(b->leftlink);
Raymond Hettinger20b0f872013-06-23 15:44:33 -0700796 leftindex = BLOCKLEN;
Raymond Hettinger3959af92013-07-13 02:34:08 -0700797 b = NULL;
Raymond Hettinger464d89b2013-01-11 22:29:50 -0800798 }
Raymond Hettinger20b0f872013-06-23 15:44:33 -0700799 assert(leftindex > 0);
Raymond Hettinger20b0f872013-06-23 15:44:33 -0700800 {
801 PyObject **src, **dest;
802 Py_ssize_t m = n;
Raymond Hettinger21777ac2013-02-02 09:56:08 -0800803
Raymond Hettinger20b0f872013-06-23 15:44:33 -0700804 if (m > rightindex + 1)
805 m = rightindex + 1;
806 if (m > leftindex)
807 m = leftindex;
808 assert (m > 0 && m <= len);
Raymond Hettinger20b0f872013-06-23 15:44:33 -0700809 rightindex -= m;
810 leftindex -= m;
Raymond Hettinger0e259f12015-02-01 22:53:41 -0800811 src = &rightblock->data[rightindex + 1];
812 dest = &leftblock->data[leftindex];
Raymond Hettinger20b0f872013-06-23 15:44:33 -0700813 n -= m;
Raymond Hettinger840533b2013-07-13 17:03:58 -0700814 do {
Raymond Hettinger0e259f12015-02-01 22:53:41 -0800815 *(dest++) = *(src++);
Raymond Hettinger840533b2013-07-13 17:03:58 -0700816 } while (--m);
Raymond Hettinger20b0f872013-06-23 15:44:33 -0700817 }
Raymond Hettingerd3d2b2c2015-09-21 23:41:56 -0700818 if (rightindex < 0) {
Raymond Hettinger20b0f872013-06-23 15:44:33 -0700819 assert(leftblock != rightblock);
Raymond Hettinger840533b2013-07-13 17:03:58 -0700820 assert(b == NULL);
Raymond Hettinger3959af92013-07-13 02:34:08 -0700821 b = rightblock;
Raymond Hettingerb97cc492013-07-21 01:51:07 -0700822 CHECK_NOT_END(rightblock->leftlink);
823 rightblock = rightblock->leftlink;
824 MARK_END(rightblock->rightlink);
Raymond Hettinger20b0f872013-06-23 15:44:33 -0700825 rightindex = BLOCKLEN - 1;
Raymond Hettinger464d89b2013-01-11 22:29:50 -0800826 }
Raymond Hettinger21777ac2013-02-02 09:56:08 -0800827 }
Raymond Hettinger1f0044c2013-02-05 01:30:46 -0500828 while (n < 0) {
Raymond Hettinger20b0f872013-06-23 15:44:33 -0700829 if (rightindex == BLOCKLEN - 1) {
Raymond Hettinger20b0f872013-06-23 15:44:33 -0700830 if (b == NULL) {
Raymond Hettingerdb41fd42015-10-22 22:48:16 -0700831 b = newblock();
Raymond Hettinger3959af92013-07-13 02:34:08 -0700832 if (b == NULL)
833 goto done;
Raymond Hettinger20b0f872013-06-23 15:44:33 -0700834 }
Raymond Hettinger82df9252013-07-07 01:43:42 -1000835 b->leftlink = rightblock;
836 CHECK_END(rightblock->rightlink);
Raymond Hettinger20b0f872013-06-23 15:44:33 -0700837 rightblock->rightlink = b;
838 rightblock = b;
Raymond Hettinger82df9252013-07-07 01:43:42 -1000839 MARK_END(b->rightlink);
Raymond Hettinger20b0f872013-06-23 15:44:33 -0700840 rightindex = -1;
Raymond Hettinger3959af92013-07-13 02:34:08 -0700841 b = NULL;
Raymond Hettinger464d89b2013-01-11 22:29:50 -0800842 }
Raymond Hettinger20b0f872013-06-23 15:44:33 -0700843 assert (rightindex < BLOCKLEN - 1);
Raymond Hettinger20b0f872013-06-23 15:44:33 -0700844 {
845 PyObject **src, **dest;
846 Py_ssize_t m = -n;
Raymond Hettinger21777ac2013-02-02 09:56:08 -0800847
Raymond Hettinger20b0f872013-06-23 15:44:33 -0700848 if (m > BLOCKLEN - leftindex)
849 m = BLOCKLEN - leftindex;
850 if (m > BLOCKLEN - 1 - rightindex)
851 m = BLOCKLEN - 1 - rightindex;
852 assert (m > 0 && m <= len);
853 src = &leftblock->data[leftindex];
854 dest = &rightblock->data[rightindex + 1];
855 leftindex += m;
856 rightindex += m;
857 n += m;
Raymond Hettinger840533b2013-07-13 17:03:58 -0700858 do {
Raymond Hettinger20b0f872013-06-23 15:44:33 -0700859 *(dest++) = *(src++);
Raymond Hettinger840533b2013-07-13 17:03:58 -0700860 } while (--m);
Raymond Hettinger20b0f872013-06-23 15:44:33 -0700861 }
Raymond Hettinger20b0f872013-06-23 15:44:33 -0700862 if (leftindex == BLOCKLEN) {
Raymond Hettinger20b0f872013-06-23 15:44:33 -0700863 assert(leftblock != rightblock);
Raymond Hettinger840533b2013-07-13 17:03:58 -0700864 assert(b == NULL);
Raymond Hettinger3959af92013-07-13 02:34:08 -0700865 b = leftblock;
Raymond Hettingerb97cc492013-07-21 01:51:07 -0700866 CHECK_NOT_END(leftblock->rightlink);
867 leftblock = leftblock->rightlink;
868 MARK_END(leftblock->leftlink);
Raymond Hettinger20b0f872013-06-23 15:44:33 -0700869 leftindex = 0;
Raymond Hettinger21777ac2013-02-02 09:56:08 -0800870 }
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000871 }
Raymond Hettinger3959af92013-07-13 02:34:08 -0700872 rv = 0;
Raymond Hettinger20b0f872013-06-23 15:44:33 -0700873done:
Raymond Hettinger3959af92013-07-13 02:34:08 -0700874 if (b != NULL)
875 freeblock(b);
Raymond Hettinger20b0f872013-06-23 15:44:33 -0700876 deque->leftblock = leftblock;
877 deque->rightblock = rightblock;
878 deque->leftindex = leftindex;
879 deque->rightindex = rightindex;
880
881 return rv;
Raymond Hettingerdcb9d942004-10-09 16:02:18 +0000882}
883
884static PyObject *
885deque_rotate(dequeobject *deque, PyObject *args)
886{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000887 Py_ssize_t n=1;
Raymond Hettingerdcb9d942004-10-09 16:02:18 +0000888
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000889 if (!PyArg_ParseTuple(args, "|n:rotate", &n))
890 return NULL;
Raymond Hettinger6921c132015-03-21 02:03:40 -0700891 if (!_deque_rotate(deque, n))
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000892 Py_RETURN_NONE;
893 return NULL;
Raymond Hettinger5c5eb862004-02-07 21:13:00 +0000894}
895
Tim Peters1065f752004-10-01 01:03:29 +0000896PyDoc_STRVAR(rotate_doc,
Raymond Hettingeree33b272004-02-08 04:05:26 +0000897"Rotate the deque n steps to the right (default n=1). If n is negative, rotates left.");
Raymond Hettinger5c5eb862004-02-07 21:13:00 +0000898
Raymond Hettingere5fdedb2009-12-10 00:47:21 +0000899static PyObject *
900deque_reverse(dequeobject *deque, PyObject *unused)
901{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000902 block *leftblock = deque->leftblock;
903 block *rightblock = deque->rightblock;
904 Py_ssize_t leftindex = deque->leftindex;
905 Py_ssize_t rightindex = deque->rightindex;
Raymond Hettingercfe5b6c2015-07-20 00:25:50 -0400906 Py_ssize_t n = Py_SIZE(deque) >> 1;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000907 PyObject *tmp;
Raymond Hettingere5fdedb2009-12-10 00:47:21 +0000908
Raymond Hettinger7a237232015-09-22 01:20:36 -0700909 while (n-- > 0) {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000910 /* Validate that pointers haven't met in the middle */
911 assert(leftblock != rightblock || leftindex < rightindex);
Raymond Hettinger82df9252013-07-07 01:43:42 -1000912 CHECK_NOT_END(leftblock);
913 CHECK_NOT_END(rightblock);
Raymond Hettingere5fdedb2009-12-10 00:47:21 +0000914
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000915 /* Swap */
916 tmp = leftblock->data[leftindex];
917 leftblock->data[leftindex] = rightblock->data[rightindex];
918 rightblock->data[rightindex] = tmp;
Raymond Hettingere5fdedb2009-12-10 00:47:21 +0000919
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000920 /* Advance left block/index pair */
921 leftindex++;
922 if (leftindex == BLOCKLEN) {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000923 leftblock = leftblock->rightlink;
924 leftindex = 0;
925 }
Raymond Hettingere5fdedb2009-12-10 00:47:21 +0000926
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000927 /* Step backwards with the right block/index pair */
928 rightindex--;
Raymond Hettingerd3d2b2c2015-09-21 23:41:56 -0700929 if (rightindex < 0) {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000930 rightblock = rightblock->leftlink;
931 rightindex = BLOCKLEN - 1;
932 }
933 }
934 Py_RETURN_NONE;
Raymond Hettingere5fdedb2009-12-10 00:47:21 +0000935}
936
937PyDoc_STRVAR(reverse_doc,
938"D.reverse() -- reverse *IN PLACE*");
939
Raymond Hettinger44459de2010-04-03 23:20:46 +0000940static PyObject *
941deque_count(dequeobject *deque, PyObject *v)
942{
Raymond Hettingerf3a67b72013-07-06 17:49:06 -1000943 block *b = deque->leftblock;
944 Py_ssize_t index = deque->leftindex;
Raymond Hettingerdf715ba2013-07-06 13:01:13 -1000945 Py_ssize_t n = Py_SIZE(deque);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000946 Py_ssize_t count = 0;
Raymond Hettingerf9d9c792015-03-02 22:47:46 -0800947 size_t start_state = deque->state;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000948 PyObject *item;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000949 int cmp;
Raymond Hettinger44459de2010-04-03 23:20:46 +0000950
Raymond Hettinger3a1a8d02015-09-23 02:42:02 -0700951 while (n--) {
Raymond Hettinger82df9252013-07-07 01:43:42 -1000952 CHECK_NOT_END(b);
Raymond Hettingerf3a67b72013-07-06 17:49:06 -1000953 item = b->data[index];
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000954 cmp = PyObject_RichCompareBool(item, v, Py_EQ);
Raymond Hettinger2b0d6462015-09-23 19:15:44 -0700955 if (cmp < 0)
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000956 return NULL;
Raymond Hettinger2b0d6462015-09-23 19:15:44 -0700957 count += cmp;
Raymond Hettinger44459de2010-04-03 23:20:46 +0000958
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000959 if (start_state != deque->state) {
960 PyErr_SetString(PyExc_RuntimeError,
961 "deque mutated during iteration");
962 return NULL;
963 }
Raymond Hettinger44459de2010-04-03 23:20:46 +0000964
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000965 /* Advance left block/index pair */
Raymond Hettingerf3a67b72013-07-06 17:49:06 -1000966 index++;
967 if (index == BLOCKLEN) {
968 b = b->rightlink;
969 index = 0;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000970 }
971 }
972 return PyLong_FromSsize_t(count);
Raymond Hettinger44459de2010-04-03 23:20:46 +0000973}
974
975PyDoc_STRVAR(count_doc,
976"D.count(value) -> integer -- return number of occurrences of value");
977
Raymond Hettinger39dadf72015-03-20 16:38:56 -0700978static int
979deque_contains(dequeobject *deque, PyObject *v)
980{
981 block *b = deque->leftblock;
982 Py_ssize_t index = deque->leftindex;
983 Py_ssize_t n = Py_SIZE(deque);
Raymond Hettinger39dadf72015-03-20 16:38:56 -0700984 size_t start_state = deque->state;
985 PyObject *item;
986 int cmp;
987
Raymond Hettinger3a1a8d02015-09-23 02:42:02 -0700988 while (n--) {
Raymond Hettinger39dadf72015-03-20 16:38:56 -0700989 CHECK_NOT_END(b);
990 item = b->data[index];
991 cmp = PyObject_RichCompareBool(item, v, Py_EQ);
992 if (cmp) {
993 return cmp;
994 }
995 if (start_state != deque->state) {
996 PyErr_SetString(PyExc_RuntimeError,
997 "deque mutated during iteration");
998 return -1;
999 }
1000 index++;
1001 if (index == BLOCKLEN) {
1002 b = b->rightlink;
1003 index = 0;
1004 }
1005 }
1006 return 0;
1007}
1008
Martin v. Löwis18e16552006-02-15 17:27:45 +00001009static Py_ssize_t
Raymond Hettinger756b3f32004-01-29 06:37:52 +00001010deque_len(dequeobject *deque)
1011{
Raymond Hettingerdf715ba2013-07-06 13:01:13 -10001012 return Py_SIZE(deque);
Raymond Hettinger756b3f32004-01-29 06:37:52 +00001013}
1014
Raymond Hettinger4aec61e2005-03-18 21:20:23 +00001015static PyObject *
Raymond Hettinger32ea1652015-03-21 01:37:37 -07001016deque_index(dequeobject *deque, PyObject *args)
1017{
Raymond Hettinger67b97b82015-11-01 23:57:37 -05001018 Py_ssize_t i, n, start=0, stop=Py_SIZE(deque);
Raymond Hettinger32ea1652015-03-21 01:37:37 -07001019 PyObject *v, *item;
1020 block *b = deque->leftblock;
1021 Py_ssize_t index = deque->leftindex;
1022 size_t start_state = deque->state;
Raymond Hettinger67b97b82015-11-01 23:57:37 -05001023 int cmp;
Raymond Hettinger32ea1652015-03-21 01:37:37 -07001024
1025 if (!PyArg_ParseTuple(args, "O|O&O&:index", &v,
1026 _PyEval_SliceIndex, &start,
1027 _PyEval_SliceIndex, &stop))
1028 return NULL;
1029 if (start < 0) {
1030 start += Py_SIZE(deque);
1031 if (start < 0)
1032 start = 0;
1033 }
1034 if (stop < 0) {
1035 stop += Py_SIZE(deque);
1036 if (stop < 0)
1037 stop = 0;
1038 }
Raymond Hettinger87674ec2015-08-26 08:08:38 -07001039 if (stop > Py_SIZE(deque))
1040 stop = Py_SIZE(deque);
Raymond Hettinger67b97b82015-11-01 23:57:37 -05001041 if (start > stop)
1042 start = stop;
1043 assert(0 <= start && start <= stop && stop <= Py_SIZE(deque));
Raymond Hettinger32ea1652015-03-21 01:37:37 -07001044
Raymond Hettinger67b97b82015-11-01 23:57:37 -05001045 /* XXX Replace this loop with faster code from deque_item() */
1046 for (i=0 ; i<start ; i++) {
1047 index++;
1048 if (index == BLOCKLEN) {
1049 b = b->rightlink;
1050 index = 0;
1051 }
1052 }
1053
Raymond Hettinger4a91d212015-11-03 22:00:26 -05001054 n = stop - i + 1;
1055 while (--n) {
Raymond Hettinger67b97b82015-11-01 23:57:37 -05001056 CHECK_NOT_END(b);
1057 item = b->data[index];
1058 cmp = PyObject_RichCompareBool(item, v, Py_EQ);
1059 if (cmp > 0)
Raymond Hettinger4a91d212015-11-03 22:00:26 -05001060 return PyLong_FromSsize_t(stop - n);
Raymond Hettingerdf8f5b52015-11-02 07:27:40 -05001061 if (cmp < 0)
Raymond Hettinger67b97b82015-11-01 23:57:37 -05001062 return NULL;
1063 if (start_state != deque->state) {
1064 PyErr_SetString(PyExc_RuntimeError,
1065 "deque mutated during iteration");
1066 return NULL;
Raymond Hettinger32ea1652015-03-21 01:37:37 -07001067 }
1068 index++;
1069 if (index == BLOCKLEN) {
1070 b = b->rightlink;
1071 index = 0;
1072 }
1073 }
1074 PyErr_Format(PyExc_ValueError, "%R is not in deque", v);
1075 return NULL;
1076}
1077
1078PyDoc_STRVAR(index_doc,
1079"D.index(value, [start, [stop]]) -> integer -- return first index of value.\n"
1080"Raises ValueError if the value is not present.");
1081
Raymond Hettinger551350a2015-03-24 00:19:53 -07001082/* insert(), remove(), and delitem() are implemented in terms of
1083 rotate() for simplicity and reasonable performance near the end
1084 points. If for some reason these methods become popular, it is not
1085 hard to re-implement this using direct data movement (similar to
1086 the code used in list slice assignments) and achieve a performance
Raymond Hettingerfef9c1b2015-03-24 21:12:57 -07001087 boost (by moving each pointer only once instead of twice).
Raymond Hettinger551350a2015-03-24 00:19:53 -07001088*/
1089
Raymond Hettinger32ea1652015-03-21 01:37:37 -07001090static PyObject *
1091deque_insert(dequeobject *deque, PyObject *args)
1092{
1093 Py_ssize_t index;
1094 Py_ssize_t n = Py_SIZE(deque);
1095 PyObject *value;
1096 PyObject *rv;
1097
1098 if (!PyArg_ParseTuple(args, "nO:insert", &index, &value))
1099 return NULL;
1100 if (index >= n)
1101 return deque_append(deque, value);
1102 if (index <= -n || index == 0)
1103 return deque_appendleft(deque, value);
1104 if (_deque_rotate(deque, -index))
1105 return NULL;
1106 if (index < 0)
1107 rv = deque_append(deque, value);
1108 else
1109 rv = deque_appendleft(deque, value);
1110 if (rv == NULL)
1111 return NULL;
1112 Py_DECREF(rv);
1113 if (_deque_rotate(deque, index))
1114 return NULL;
1115 Py_RETURN_NONE;
1116}
1117
1118PyDoc_STRVAR(insert_doc,
1119"D.insert(index, object) -- insert object before index");
1120
1121static PyObject *
Raymond Hettinger4aec61e2005-03-18 21:20:23 +00001122deque_remove(dequeobject *deque, PyObject *value)
1123{
Raymond Hettingerdf715ba2013-07-06 13:01:13 -10001124 Py_ssize_t i, n=Py_SIZE(deque);
Raymond Hettinger4aec61e2005-03-18 21:20:23 +00001125
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001126 for (i=0 ; i<n ; i++) {
1127 PyObject *item = deque->leftblock->data[deque->leftindex];
1128 int cmp = PyObject_RichCompareBool(item, value, Py_EQ);
Raymond Hettingerd73202c2005-03-19 00:00:51 +00001129
Raymond Hettingerdf715ba2013-07-06 13:01:13 -10001130 if (Py_SIZE(deque) != n) {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001131 PyErr_SetString(PyExc_IndexError,
1132 "deque mutated during remove().");
1133 return NULL;
1134 }
1135 if (cmp > 0) {
1136 PyObject *tgt = deque_popleft(deque, NULL);
1137 assert (tgt != NULL);
Raymond Hettinger6921c132015-03-21 02:03:40 -07001138 if (_deque_rotate(deque, i))
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001139 return NULL;
Raymond Hettingerac13ad62015-03-21 01:53:16 -07001140 Py_DECREF(tgt);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001141 Py_RETURN_NONE;
1142 }
1143 else if (cmp < 0) {
1144 _deque_rotate(deque, i);
1145 return NULL;
1146 }
1147 _deque_rotate(deque, -1);
1148 }
1149 PyErr_SetString(PyExc_ValueError, "deque.remove(x): x not in deque");
1150 return NULL;
Raymond Hettinger4aec61e2005-03-18 21:20:23 +00001151}
1152
1153PyDoc_STRVAR(remove_doc,
1154"D.remove(value) -- remove first occurrence of value.");
1155
Raymond Hettinger3c186ba2015-03-02 21:45:02 -08001156static int
1157valid_index(Py_ssize_t i, Py_ssize_t limit)
1158{
Raymond Hettinger12f896c2015-07-31 12:03:20 -07001159 /* The cast to size_t lets us use just a single comparison
Raymond Hettinger3c186ba2015-03-02 21:45:02 -08001160 to check whether i is in the range: 0 <= i < limit */
1161 return (size_t) i < (size_t) limit;
1162}
1163
Raymond Hettinger756b3f32004-01-29 06:37:52 +00001164static PyObject *
Benjamin Petersond6313712008-07-31 16:23:04 +00001165deque_item(dequeobject *deque, Py_ssize_t i)
Raymond Hettinger0a4977c2004-03-01 23:16:22 +00001166{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001167 block *b;
1168 PyObject *item;
1169 Py_ssize_t n, index=i;
Raymond Hettinger0a4977c2004-03-01 23:16:22 +00001170
Raymond Hettinger3c186ba2015-03-02 21:45:02 -08001171 if (!valid_index(i, Py_SIZE(deque))) {
1172 PyErr_SetString(PyExc_IndexError, "deque index out of range");
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001173 return NULL;
1174 }
Raymond Hettinger0a4977c2004-03-01 23:16:22 +00001175
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001176 if (i == 0) {
1177 i = deque->leftindex;
1178 b = deque->leftblock;
Raymond Hettingerdf715ba2013-07-06 13:01:13 -10001179 } else if (i == Py_SIZE(deque) - 1) {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001180 i = deque->rightindex;
1181 b = deque->rightblock;
1182 } else {
1183 i += deque->leftindex;
Raymond Hettingerc2083082015-02-28 23:29:16 -08001184 n = (Py_ssize_t)((size_t) i / BLOCKLEN);
1185 i = (Py_ssize_t)((size_t) i % BLOCKLEN);
Raymond Hettingerdf715ba2013-07-06 13:01:13 -10001186 if (index < (Py_SIZE(deque) >> 1)) {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001187 b = deque->leftblock;
1188 while (n--)
1189 b = b->rightlink;
1190 } else {
Raymond Hettinger63d1ff22015-02-28 07:41:30 -08001191 n = (Py_ssize_t)(
Raymond Hettingerc2083082015-02-28 23:29:16 -08001192 ((size_t)(deque->leftindex + Py_SIZE(deque) - 1))
Raymond Hettinger63d1ff22015-02-28 07:41:30 -08001193 / BLOCKLEN - n);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001194 b = deque->rightblock;
1195 while (n--)
1196 b = b->leftlink;
1197 }
1198 }
1199 item = b->data[i];
1200 Py_INCREF(item);
1201 return item;
Raymond Hettinger0a4977c2004-03-01 23:16:22 +00001202}
1203
1204static int
Martin v. Löwis18e16552006-02-15 17:27:45 +00001205deque_del_item(dequeobject *deque, Py_ssize_t i)
Raymond Hettinger0e371f22004-05-12 20:55:56 +00001206{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001207 PyObject *item;
Raymond Hettingerac13ad62015-03-21 01:53:16 -07001208 int rv;
Raymond Hettinger0e371f22004-05-12 20:55:56 +00001209
Raymond Hettingerdf715ba2013-07-06 13:01:13 -10001210 assert (i >= 0 && i < Py_SIZE(deque));
Raymond Hettinger6921c132015-03-21 02:03:40 -07001211 if (_deque_rotate(deque, -i))
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001212 return -1;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001213 item = deque_popleft(deque, NULL);
Raymond Hettingerac13ad62015-03-21 01:53:16 -07001214 rv = _deque_rotate(deque, i);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001215 assert (item != NULL);
1216 Py_DECREF(item);
Raymond Hettingerac13ad62015-03-21 01:53:16 -07001217 return rv;
Raymond Hettinger0e371f22004-05-12 20:55:56 +00001218}
1219
1220static int
Martin v. Löwis18e16552006-02-15 17:27:45 +00001221deque_ass_item(dequeobject *deque, Py_ssize_t i, PyObject *v)
Raymond Hettinger0a4977c2004-03-01 23:16:22 +00001222{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001223 block *b;
Raymond Hettingerdf715ba2013-07-06 13:01:13 -10001224 Py_ssize_t n, len=Py_SIZE(deque), halflen=(len+1)>>1, index=i;
Raymond Hettinger0a4977c2004-03-01 23:16:22 +00001225
Raymond Hettinger3c186ba2015-03-02 21:45:02 -08001226 if (!valid_index(i, len)) {
1227 PyErr_SetString(PyExc_IndexError, "deque index out of range");
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001228 return -1;
1229 }
1230 if (v == NULL)
1231 return deque_del_item(deque, i);
Raymond Hettinger0e371f22004-05-12 20:55:56 +00001232
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001233 i += deque->leftindex;
Raymond Hettingerc2083082015-02-28 23:29:16 -08001234 n = (Py_ssize_t)((size_t) i / BLOCKLEN);
1235 i = (Py_ssize_t)((size_t) i % BLOCKLEN);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001236 if (index <= halflen) {
1237 b = deque->leftblock;
1238 while (n--)
1239 b = b->rightlink;
1240 } else {
Raymond Hettingera473b9d2015-02-28 17:49:47 -08001241 n = (Py_ssize_t)(
Raymond Hettingerc2083082015-02-28 23:29:16 -08001242 ((size_t)(deque->leftindex + Py_SIZE(deque) - 1))
Raymond Hettingera473b9d2015-02-28 17:49:47 -08001243 / BLOCKLEN - n);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001244 b = deque->rightblock;
1245 while (n--)
1246 b = b->leftlink;
1247 }
1248 Py_INCREF(v);
Serhiy Storchaka1ed017a2015-12-27 15:51:32 +02001249 Py_SETREF(b->data[i], v);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001250 return 0;
Raymond Hettinger0a4977c2004-03-01 23:16:22 +00001251}
1252
Raymond Hettinger756b3f32004-01-29 06:37:52 +00001253static void
1254deque_dealloc(dequeobject *deque)
1255{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001256 PyObject_GC_UnTrack(deque);
1257 if (deque->weakreflist != NULL)
1258 PyObject_ClearWeakRefs((PyObject *) deque);
1259 if (deque->leftblock != NULL) {
1260 deque_clear(deque);
1261 assert(deque->leftblock != NULL);
1262 freeblock(deque->leftblock);
1263 }
1264 deque->leftblock = NULL;
1265 deque->rightblock = NULL;
1266 Py_TYPE(deque)->tp_free(deque);
Raymond Hettinger756b3f32004-01-29 06:37:52 +00001267}
1268
1269static int
Raymond Hettinger0a4977c2004-03-01 23:16:22 +00001270deque_traverse(dequeobject *deque, visitproc visit, void *arg)
Raymond Hettinger756b3f32004-01-29 06:37:52 +00001271{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001272 block *b;
1273 PyObject *item;
1274 Py_ssize_t index;
1275 Py_ssize_t indexlo = deque->leftindex;
Raymond Hettinger1286d142015-10-14 23:16:57 -07001276 Py_ssize_t indexhigh;
Raymond Hettinger756b3f32004-01-29 06:37:52 +00001277
Raymond Hettinger5bfa8672013-07-06 11:58:09 -10001278 for (b = deque->leftblock; b != deque->rightblock; b = b->rightlink) {
1279 for (index = indexlo; index < BLOCKLEN ; index++) {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001280 item = b->data[index];
1281 Py_VISIT(item);
1282 }
1283 indexlo = 0;
1284 }
Raymond Hettinger1286d142015-10-14 23:16:57 -07001285 indexhigh = deque->rightindex;
1286 for (index = indexlo; index <= indexhigh; index++) {
Raymond Hettinger5bfa8672013-07-06 11:58:09 -10001287 item = b->data[index];
1288 Py_VISIT(item);
1289 }
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001290 return 0;
Raymond Hettinger756b3f32004-01-29 06:37:52 +00001291}
1292
Raymond Hettinger756b3f32004-01-29 06:37:52 +00001293static PyObject *
Raymond Hettinger756b3f32004-01-29 06:37:52 +00001294deque_reduce(dequeobject *deque)
1295{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001296 PyObject *dict, *result, *aslist;
Martin v. Löwisbd928fe2011-10-14 10:20:37 +02001297 _Py_IDENTIFIER(__dict__);
Raymond Hettinger756b3f32004-01-29 06:37:52 +00001298
Martin v. Löwis1ee1b6f2011-10-10 18:11:30 +02001299 dict = _PyObject_GetAttrId((PyObject *)deque, &PyId___dict__);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001300 if (dict == NULL)
1301 PyErr_Clear();
1302 aslist = PySequence_List((PyObject *)deque);
1303 if (aslist == NULL) {
1304 Py_XDECREF(dict);
1305 return NULL;
1306 }
1307 if (dict == NULL) {
Raymond Hettingerd3d2b2c2015-09-21 23:41:56 -07001308 if (deque->maxlen < 0)
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001309 result = Py_BuildValue("O(O)", Py_TYPE(deque), aslist);
1310 else
1311 result = Py_BuildValue("O(On)", Py_TYPE(deque), aslist, deque->maxlen);
1312 } else {
Raymond Hettingerd3d2b2c2015-09-21 23:41:56 -07001313 if (deque->maxlen < 0)
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001314 result = Py_BuildValue("O(OO)O", Py_TYPE(deque), aslist, Py_None, dict);
1315 else
1316 result = Py_BuildValue("O(On)O", Py_TYPE(deque), aslist, deque->maxlen, dict);
1317 }
1318 Py_XDECREF(dict);
1319 Py_DECREF(aslist);
1320 return result;
Raymond Hettinger756b3f32004-01-29 06:37:52 +00001321}
1322
1323PyDoc_STRVAR(reduce_doc, "Return state information for pickling.");
1324
1325static PyObject *
1326deque_repr(PyObject *deque)
1327{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001328 PyObject *aslist, *result;
1329 int i;
Raymond Hettinger756b3f32004-01-29 06:37:52 +00001330
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001331 i = Py_ReprEnter(deque);
1332 if (i != 0) {
1333 if (i < 0)
1334 return NULL;
1335 return PyUnicode_FromString("[...]");
1336 }
Raymond Hettinger756b3f32004-01-29 06:37:52 +00001337
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001338 aslist = PySequence_List(deque);
1339 if (aslist == NULL) {
1340 Py_ReprLeave(deque);
1341 return NULL;
1342 }
Raymond Hettingera7f630092015-10-10 23:56:02 -04001343 if (((dequeobject *)deque)->maxlen >= 0)
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001344 result = PyUnicode_FromFormat("deque(%R, maxlen=%zd)",
1345 aslist, ((dequeobject *)deque)->maxlen);
1346 else
1347 result = PyUnicode_FromFormat("deque(%R)", aslist);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001348 Py_ReprLeave(deque);
Raymond Hettinger2b2b7532015-09-05 17:05:52 -07001349 Py_DECREF(aslist);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001350 return result;
Raymond Hettinger756b3f32004-01-29 06:37:52 +00001351}
1352
Raymond Hettinger738ec902004-02-29 02:15:56 +00001353static PyObject *
1354deque_richcompare(PyObject *v, PyObject *w, int op)
1355{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001356 PyObject *it1=NULL, *it2=NULL, *x, *y;
1357 Py_ssize_t vs, ws;
1358 int b, cmp=-1;
Raymond Hettinger738ec902004-02-29 02:15:56 +00001359
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001360 if (!PyObject_TypeCheck(v, &deque_type) ||
1361 !PyObject_TypeCheck(w, &deque_type)) {
Brian Curtindfc80e32011-08-10 20:28:54 -05001362 Py_RETURN_NOTIMPLEMENTED;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001363 }
Raymond Hettinger738ec902004-02-29 02:15:56 +00001364
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001365 /* Shortcuts */
Raymond Hettingerdf715ba2013-07-06 13:01:13 -10001366 vs = Py_SIZE((dequeobject *)v);
1367 ws = Py_SIZE((dequeobject *)w);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001368 if (op == Py_EQ) {
1369 if (v == w)
1370 Py_RETURN_TRUE;
1371 if (vs != ws)
1372 Py_RETURN_FALSE;
1373 }
1374 if (op == Py_NE) {
1375 if (v == w)
1376 Py_RETURN_FALSE;
1377 if (vs != ws)
1378 Py_RETURN_TRUE;
1379 }
Raymond Hettinger738ec902004-02-29 02:15:56 +00001380
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001381 /* Search for the first index where items are different */
1382 it1 = PyObject_GetIter(v);
1383 if (it1 == NULL)
1384 goto done;
1385 it2 = PyObject_GetIter(w);
1386 if (it2 == NULL)
1387 goto done;
1388 for (;;) {
1389 x = PyIter_Next(it1);
1390 if (x == NULL && PyErr_Occurred())
1391 goto done;
1392 y = PyIter_Next(it2);
1393 if (x == NULL || y == NULL)
1394 break;
1395 b = PyObject_RichCompareBool(x, y, Py_EQ);
1396 if (b == 0) {
1397 cmp = PyObject_RichCompareBool(x, y, op);
1398 Py_DECREF(x);
1399 Py_DECREF(y);
1400 goto done;
1401 }
1402 Py_DECREF(x);
1403 Py_DECREF(y);
Raymond Hettingerd3d2b2c2015-09-21 23:41:56 -07001404 if (b < 0)
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001405 goto done;
1406 }
1407 /* We reached the end of one deque or both */
1408 Py_XDECREF(x);
1409 Py_XDECREF(y);
1410 if (PyErr_Occurred())
1411 goto done;
1412 switch (op) {
1413 case Py_LT: cmp = y != NULL; break; /* if w was longer */
1414 case Py_LE: cmp = x == NULL; break; /* if v was not longer */
1415 case Py_EQ: cmp = x == y; break; /* if we reached the end of both */
1416 case Py_NE: cmp = x != y; break; /* if one deque continues */
1417 case Py_GT: cmp = x != NULL; break; /* if v was longer */
1418 case Py_GE: cmp = y == NULL; break; /* if w was not longer */
1419 }
Tim Peters1065f752004-10-01 01:03:29 +00001420
Raymond Hettinger738ec902004-02-29 02:15:56 +00001421done:
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001422 Py_XDECREF(it1);
1423 Py_XDECREF(it2);
1424 if (cmp == 1)
1425 Py_RETURN_TRUE;
1426 if (cmp == 0)
1427 Py_RETURN_FALSE;
1428 return NULL;
Raymond Hettinger738ec902004-02-29 02:15:56 +00001429}
1430
Raymond Hettinger756b3f32004-01-29 06:37:52 +00001431static int
Guido van Rossum8ce8a782007-11-01 19:42:39 +00001432deque_init(dequeobject *deque, PyObject *args, PyObject *kwdargs)
Raymond Hettinger756b3f32004-01-29 06:37:52 +00001433{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001434 PyObject *iterable = NULL;
1435 PyObject *maxlenobj = NULL;
1436 Py_ssize_t maxlen = -1;
1437 char *kwlist[] = {"iterable", "maxlen", 0};
Raymond Hettinger756b3f32004-01-29 06:37:52 +00001438
Raymond Hettinger0d309402015-09-30 23:15:02 -07001439 if (kwdargs == NULL) {
1440 if (!PyArg_UnpackTuple(args, "deque()", 0, 2, &iterable, &maxlenobj))
1441 return -1;
1442 } else {
1443 if (!PyArg_ParseTupleAndKeywords(args, kwdargs, "|OO:deque", kwlist,
1444 &iterable, &maxlenobj))
1445 return -1;
1446 }
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001447 if (maxlenobj != NULL && maxlenobj != Py_None) {
1448 maxlen = PyLong_AsSsize_t(maxlenobj);
1449 if (maxlen == -1 && PyErr_Occurred())
1450 return -1;
1451 if (maxlen < 0) {
1452 PyErr_SetString(PyExc_ValueError, "maxlen must be non-negative");
1453 return -1;
1454 }
1455 }
1456 deque->maxlen = maxlen;
Raymond Hettinger0d309402015-09-30 23:15:02 -07001457 if (Py_SIZE(deque) > 0)
1458 deque_clear(deque);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001459 if (iterable != NULL) {
1460 PyObject *rv = deque_extend(deque, iterable);
1461 if (rv == NULL)
1462 return -1;
1463 Py_DECREF(rv);
1464 }
1465 return 0;
Raymond Hettinger756b3f32004-01-29 06:37:52 +00001466}
1467
Raymond Hettinger5bb0f0e2009-03-10 12:56:32 +00001468static PyObject *
Jesus Cea16e2fca2012-08-03 14:49:42 +02001469deque_sizeof(dequeobject *deque, void *unused)
1470{
1471 Py_ssize_t res;
1472 Py_ssize_t blocks;
1473
Serhiy Storchaka5c4064e2015-12-19 20:05:25 +02001474 res = _PyObject_SIZE(Py_TYPE(deque));
Raymond Hettingerbc003412015-10-14 23:33:23 -07001475 blocks = (size_t)(deque->leftindex + Py_SIZE(deque) + BLOCKLEN - 1) / BLOCKLEN;
Raymond Hettingerdf715ba2013-07-06 13:01:13 -10001476 assert(deque->leftindex + Py_SIZE(deque) - 1 ==
Jesus Cea16e2fca2012-08-03 14:49:42 +02001477 (blocks - 1) * BLOCKLEN + deque->rightindex);
1478 res += blocks * sizeof(block);
1479 return PyLong_FromSsize_t(res);
1480}
1481
1482PyDoc_STRVAR(sizeof_doc,
1483"D.__sizeof__() -- size of D in memory, in bytes");
1484
Raymond Hettinger0f1451c2015-03-23 23:23:55 -07001485static int
1486deque_bool(dequeobject *deque)
1487{
1488 return Py_SIZE(deque) != 0;
1489}
1490
Jesus Cea16e2fca2012-08-03 14:49:42 +02001491static PyObject *
Raymond Hettinger5bb0f0e2009-03-10 12:56:32 +00001492deque_get_maxlen(dequeobject *deque)
1493{
Raymond Hettingerd3d2b2c2015-09-21 23:41:56 -07001494 if (deque->maxlen < 0)
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001495 Py_RETURN_NONE;
1496 return PyLong_FromSsize_t(deque->maxlen);
Raymond Hettinger5bb0f0e2009-03-10 12:56:32 +00001497}
1498
Raymond Hettinger41290a62015-03-31 08:12:23 -07001499
1500/* deque object ********************************************************/
1501
Raymond Hettinger5bb0f0e2009-03-10 12:56:32 +00001502static PyGetSetDef deque_getset[] = {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001503 {"maxlen", (getter)deque_get_maxlen, (setter)NULL,
1504 "maximum size of a deque or None if unbounded"},
1505 {0}
Raymond Hettinger5bb0f0e2009-03-10 12:56:32 +00001506};
1507
Raymond Hettinger756b3f32004-01-29 06:37:52 +00001508static PySequenceMethods deque_as_sequence = {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001509 (lenfunc)deque_len, /* sq_length */
Raymond Hettinger41290a62015-03-31 08:12:23 -07001510 (binaryfunc)deque_concat, /* sq_concat */
1511 (ssizeargfunc)deque_repeat, /* sq_repeat */
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001512 (ssizeargfunc)deque_item, /* sq_item */
1513 0, /* sq_slice */
Raymond Hettinger87e69122015-03-02 23:32:02 -08001514 (ssizeobjargproc)deque_ass_item, /* sq_ass_item */
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001515 0, /* sq_ass_slice */
Raymond Hettinger39dadf72015-03-20 16:38:56 -07001516 (objobjproc)deque_contains, /* sq_contains */
Raymond Hettinger87e69122015-03-02 23:32:02 -08001517 (binaryfunc)deque_inplace_concat, /* sq_inplace_concat */
Raymond Hettinger41290a62015-03-31 08:12:23 -07001518 (ssizeargfunc)deque_inplace_repeat, /* sq_inplace_repeat */
Raymond Hettinger756b3f32004-01-29 06:37:52 +00001519};
1520
Raymond Hettinger0f1451c2015-03-23 23:23:55 -07001521static PyNumberMethods deque_as_number = {
1522 0, /* nb_add */
1523 0, /* nb_subtract */
1524 0, /* nb_multiply */
1525 0, /* nb_remainder */
1526 0, /* nb_divmod */
1527 0, /* nb_power */
1528 0, /* nb_negative */
1529 0, /* nb_positive */
1530 0, /* nb_absolute */
1531 (inquiry)deque_bool, /* nb_bool */
1532 0, /* nb_invert */
Raymond Hettinger0f1451c2015-03-23 23:23:55 -07001533 };
1534
Raymond Hettinger756b3f32004-01-29 06:37:52 +00001535static PyObject *deque_iter(dequeobject *deque);
Raymond Hettinger1e5809f2004-03-18 11:04:57 +00001536static PyObject *deque_reviter(dequeobject *deque);
Tim Peters1065f752004-10-01 01:03:29 +00001537PyDoc_STRVAR(reversed_doc,
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001538 "D.__reversed__() -- return a reverse iterator over the deque");
Raymond Hettinger756b3f32004-01-29 06:37:52 +00001539
1540static PyMethodDef deque_methods[] = {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001541 {"append", (PyCFunction)deque_append,
1542 METH_O, append_doc},
1543 {"appendleft", (PyCFunction)deque_appendleft,
1544 METH_O, appendleft_doc},
1545 {"clear", (PyCFunction)deque_clearmethod,
1546 METH_NOARGS, clear_doc},
1547 {"__copy__", (PyCFunction)deque_copy,
1548 METH_NOARGS, copy_doc},
Raymond Hettinger32ea1652015-03-21 01:37:37 -07001549 {"copy", (PyCFunction)deque_copy,
1550 METH_NOARGS, copy_doc},
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001551 {"count", (PyCFunction)deque_count,
Raymond Hettinger0f6f9472015-03-21 01:42:10 -07001552 METH_O, count_doc},
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001553 {"extend", (PyCFunction)deque_extend,
1554 METH_O, extend_doc},
1555 {"extendleft", (PyCFunction)deque_extendleft,
1556 METH_O, extendleft_doc},
Raymond Hettinger32ea1652015-03-21 01:37:37 -07001557 {"index", (PyCFunction)deque_index,
1558 METH_VARARGS, index_doc},
1559 {"insert", (PyCFunction)deque_insert,
1560 METH_VARARGS, insert_doc},
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001561 {"pop", (PyCFunction)deque_pop,
1562 METH_NOARGS, pop_doc},
1563 {"popleft", (PyCFunction)deque_popleft,
1564 METH_NOARGS, popleft_doc},
Raymond Hettinger0f6f9472015-03-21 01:42:10 -07001565 {"__reduce__", (PyCFunction)deque_reduce,
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001566 METH_NOARGS, reduce_doc},
1567 {"remove", (PyCFunction)deque_remove,
1568 METH_O, remove_doc},
1569 {"__reversed__", (PyCFunction)deque_reviter,
1570 METH_NOARGS, reversed_doc},
1571 {"reverse", (PyCFunction)deque_reverse,
1572 METH_NOARGS, reverse_doc},
1573 {"rotate", (PyCFunction)deque_rotate,
Jesus Cea16e2fca2012-08-03 14:49:42 +02001574 METH_VARARGS, rotate_doc},
1575 {"__sizeof__", (PyCFunction)deque_sizeof,
1576 METH_NOARGS, sizeof_doc},
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001577 {NULL, NULL} /* sentinel */
Raymond Hettinger756b3f32004-01-29 06:37:52 +00001578};
1579
1580PyDoc_STRVAR(deque_doc,
Andrew Svetlov6a5c7c32012-10-31 11:50:40 +02001581"deque([iterable[, maxlen]]) --> deque object\n\
Raymond Hettinger756b3f32004-01-29 06:37:52 +00001582\n\
Raymond Hettinger41290a62015-03-31 08:12:23 -07001583A list-like sequence optimized for data accesses near its endpoints.");
Raymond Hettinger756b3f32004-01-29 06:37:52 +00001584
Neal Norwitz87f10132004-02-29 15:40:53 +00001585static PyTypeObject deque_type = {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001586 PyVarObject_HEAD_INIT(NULL, 0)
1587 "collections.deque", /* tp_name */
1588 sizeof(dequeobject), /* tp_basicsize */
1589 0, /* tp_itemsize */
1590 /* methods */
1591 (destructor)deque_dealloc, /* tp_dealloc */
1592 0, /* tp_print */
1593 0, /* tp_getattr */
1594 0, /* tp_setattr */
1595 0, /* tp_reserved */
1596 deque_repr, /* tp_repr */
Raymond Hettinger0f1451c2015-03-23 23:23:55 -07001597 &deque_as_number, /* tp_as_number */
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001598 &deque_as_sequence, /* tp_as_sequence */
1599 0, /* tp_as_mapping */
Georg Brandlf038b322010-10-18 07:35:09 +00001600 PyObject_HashNotImplemented, /* tp_hash */
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001601 0, /* tp_call */
1602 0, /* tp_str */
1603 PyObject_GenericGetAttr, /* tp_getattro */
1604 0, /* tp_setattro */
1605 0, /* tp_as_buffer */
1606 Py_TPFLAGS_DEFAULT | Py_TPFLAGS_BASETYPE | Py_TPFLAGS_HAVE_GC,
Georg Brandlf038b322010-10-18 07:35:09 +00001607 /* tp_flags */
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001608 deque_doc, /* tp_doc */
1609 (traverseproc)deque_traverse, /* tp_traverse */
1610 (inquiry)deque_clear, /* tp_clear */
1611 (richcmpfunc)deque_richcompare, /* tp_richcompare */
Georg Brandlf038b322010-10-18 07:35:09 +00001612 offsetof(dequeobject, weakreflist), /* tp_weaklistoffset*/
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001613 (getiterfunc)deque_iter, /* tp_iter */
1614 0, /* tp_iternext */
1615 deque_methods, /* tp_methods */
1616 0, /* tp_members */
Georg Brandlf038b322010-10-18 07:35:09 +00001617 deque_getset, /* tp_getset */
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001618 0, /* tp_base */
1619 0, /* tp_dict */
1620 0, /* tp_descr_get */
1621 0, /* tp_descr_set */
1622 0, /* tp_dictoffset */
1623 (initproc)deque_init, /* tp_init */
1624 PyType_GenericAlloc, /* tp_alloc */
1625 deque_new, /* tp_new */
1626 PyObject_GC_Del, /* tp_free */
Raymond Hettinger756b3f32004-01-29 06:37:52 +00001627};
1628
1629/*********************** Deque Iterator **************************/
1630
1631typedef struct {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001632 PyObject_HEAD
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001633 block *b;
Raymond Hettinger87e69122015-03-02 23:32:02 -08001634 Py_ssize_t index;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001635 dequeobject *deque;
Raymond Hettingerf9d9c792015-03-02 22:47:46 -08001636 size_t state; /* state when the iterator is created */
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001637 Py_ssize_t counter; /* number of items remaining for iteration */
Raymond Hettinger756b3f32004-01-29 06:37:52 +00001638} dequeiterobject;
1639
Martin v. Löwis59683e82008-06-13 07:50:45 +00001640static PyTypeObject dequeiter_type;
Raymond Hettinger756b3f32004-01-29 06:37:52 +00001641
1642static PyObject *
1643deque_iter(dequeobject *deque)
1644{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001645 dequeiterobject *it;
Raymond Hettinger756b3f32004-01-29 06:37:52 +00001646
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001647 it = PyObject_GC_New(dequeiterobject, &dequeiter_type);
1648 if (it == NULL)
1649 return NULL;
1650 it->b = deque->leftblock;
1651 it->index = deque->leftindex;
1652 Py_INCREF(deque);
1653 it->deque = deque;
1654 it->state = deque->state;
Raymond Hettingerdf715ba2013-07-06 13:01:13 -10001655 it->counter = Py_SIZE(deque);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001656 PyObject_GC_Track(it);
1657 return (PyObject *)it;
Raymond Hettinger756b3f32004-01-29 06:37:52 +00001658}
1659
Antoine Pitrou7ddda782009-01-01 15:35:33 +00001660static int
1661dequeiter_traverse(dequeiterobject *dio, visitproc visit, void *arg)
1662{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001663 Py_VISIT(dio->deque);
1664 return 0;
Antoine Pitrou7ddda782009-01-01 15:35:33 +00001665}
1666
Raymond Hettinger756b3f32004-01-29 06:37:52 +00001667static void
1668dequeiter_dealloc(dequeiterobject *dio)
1669{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001670 Py_XDECREF(dio->deque);
1671 PyObject_GC_Del(dio);
Raymond Hettinger756b3f32004-01-29 06:37:52 +00001672}
1673
1674static PyObject *
1675dequeiter_next(dequeiterobject *it)
1676{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001677 PyObject *item;
Raymond Hettingerd1b3d882004-10-02 00:43:13 +00001678
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001679 if (it->deque->state != it->state) {
1680 it->counter = 0;
1681 PyErr_SetString(PyExc_RuntimeError,
1682 "deque mutated during iteration");
1683 return NULL;
1684 }
1685 if (it->counter == 0)
1686 return NULL;
1687 assert (!(it->b == it->deque->rightblock &&
1688 it->index > it->deque->rightindex));
Raymond Hettinger756b3f32004-01-29 06:37:52 +00001689
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001690 item = it->b->data[it->index];
1691 it->index++;
1692 it->counter--;
1693 if (it->index == BLOCKLEN && it->counter > 0) {
Raymond Hettinger82df9252013-07-07 01:43:42 -10001694 CHECK_NOT_END(it->b->rightlink);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001695 it->b = it->b->rightlink;
1696 it->index = 0;
1697 }
1698 Py_INCREF(item);
1699 return item;
Raymond Hettinger756b3f32004-01-29 06:37:52 +00001700}
1701
Raymond Hettinger6b27cda2005-09-24 21:23:05 +00001702static PyObject *
Kristján Valur Jónsson31668b82012-04-03 10:49:41 +00001703dequeiter_new(PyTypeObject *type, PyObject *args, PyObject *kwds)
1704{
1705 Py_ssize_t i, index=0;
1706 PyObject *deque;
1707 dequeiterobject *it;
1708 if (!PyArg_ParseTuple(args, "O!|n", &deque_type, &deque, &index))
1709 return NULL;
1710 assert(type == &dequeiter_type);
1711
1712 it = (dequeiterobject*)deque_iter((dequeobject *)deque);
1713 if (!it)
1714 return NULL;
1715 /* consume items from the queue */
1716 for(i=0; i<index; i++) {
1717 PyObject *item = dequeiter_next(it);
1718 if (item) {
1719 Py_DECREF(item);
1720 } else {
1721 if (it->counter) {
1722 Py_DECREF(it);
1723 return NULL;
1724 } else
1725 break;
1726 }
1727 }
1728 return (PyObject*)it;
1729}
1730
1731static PyObject *
Raymond Hettinger1e5809f2004-03-18 11:04:57 +00001732dequeiter_len(dequeiterobject *it)
1733{
Antoine Pitrou554f3342010-08-17 18:30:06 +00001734 return PyLong_FromSsize_t(it->counter);
Raymond Hettinger1e5809f2004-03-18 11:04:57 +00001735}
1736
Armin Rigof5b3e362006-02-11 21:32:43 +00001737PyDoc_STRVAR(length_hint_doc, "Private method returning an estimate of len(list(it)).");
Raymond Hettinger6b27cda2005-09-24 21:23:05 +00001738
Kristján Valur Jónsson31668b82012-04-03 10:49:41 +00001739static PyObject *
1740dequeiter_reduce(dequeiterobject *it)
1741{
Raymond Hettingerdf715ba2013-07-06 13:01:13 -10001742 return Py_BuildValue("O(On)", Py_TYPE(it), it->deque, Py_SIZE(it->deque) - it->counter);
Kristján Valur Jónsson31668b82012-04-03 10:49:41 +00001743}
1744
Raymond Hettinger6b27cda2005-09-24 21:23:05 +00001745static PyMethodDef dequeiter_methods[] = {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001746 {"__length_hint__", (PyCFunction)dequeiter_len, METH_NOARGS, length_hint_doc},
Kristján Valur Jónsson31668b82012-04-03 10:49:41 +00001747 {"__reduce__", (PyCFunction)dequeiter_reduce, METH_NOARGS, reduce_doc},
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001748 {NULL, NULL} /* sentinel */
Raymond Hettinger1e5809f2004-03-18 11:04:57 +00001749};
1750
Martin v. Löwis59683e82008-06-13 07:50:45 +00001751static PyTypeObject dequeiter_type = {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001752 PyVarObject_HEAD_INIT(NULL, 0)
Raymond Hettinger87e69122015-03-02 23:32:02 -08001753 "_collections._deque_iterator", /* tp_name */
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001754 sizeof(dequeiterobject), /* tp_basicsize */
1755 0, /* tp_itemsize */
1756 /* methods */
1757 (destructor)dequeiter_dealloc, /* tp_dealloc */
1758 0, /* tp_print */
1759 0, /* tp_getattr */
1760 0, /* tp_setattr */
1761 0, /* tp_reserved */
1762 0, /* tp_repr */
1763 0, /* tp_as_number */
1764 0, /* tp_as_sequence */
1765 0, /* tp_as_mapping */
1766 0, /* tp_hash */
1767 0, /* tp_call */
1768 0, /* tp_str */
1769 PyObject_GenericGetAttr, /* tp_getattro */
1770 0, /* tp_setattro */
1771 0, /* tp_as_buffer */
Raymond Hettinger87e69122015-03-02 23:32:02 -08001772 Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC, /* tp_flags */
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001773 0, /* tp_doc */
1774 (traverseproc)dequeiter_traverse, /* tp_traverse */
1775 0, /* tp_clear */
1776 0, /* tp_richcompare */
1777 0, /* tp_weaklistoffset */
1778 PyObject_SelfIter, /* tp_iter */
1779 (iternextfunc)dequeiter_next, /* tp_iternext */
1780 dequeiter_methods, /* tp_methods */
Kristján Valur Jónsson31668b82012-04-03 10:49:41 +00001781 0, /* tp_members */
1782 0, /* tp_getset */
1783 0, /* tp_base */
1784 0, /* tp_dict */
1785 0, /* tp_descr_get */
1786 0, /* tp_descr_set */
1787 0, /* tp_dictoffset */
1788 0, /* tp_init */
1789 0, /* tp_alloc */
1790 dequeiter_new, /* tp_new */
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001791 0,
Raymond Hettinger756b3f32004-01-29 06:37:52 +00001792};
1793
Raymond Hettinger1e5809f2004-03-18 11:04:57 +00001794/*********************** Deque Reverse Iterator **************************/
1795
Martin v. Löwis59683e82008-06-13 07:50:45 +00001796static PyTypeObject dequereviter_type;
Raymond Hettinger1e5809f2004-03-18 11:04:57 +00001797
1798static PyObject *
1799deque_reviter(dequeobject *deque)
1800{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001801 dequeiterobject *it;
Raymond Hettinger1e5809f2004-03-18 11:04:57 +00001802
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001803 it = PyObject_GC_New(dequeiterobject, &dequereviter_type);
1804 if (it == NULL)
1805 return NULL;
1806 it->b = deque->rightblock;
1807 it->index = deque->rightindex;
1808 Py_INCREF(deque);
1809 it->deque = deque;
1810 it->state = deque->state;
Raymond Hettingerdf715ba2013-07-06 13:01:13 -10001811 it->counter = Py_SIZE(deque);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001812 PyObject_GC_Track(it);
1813 return (PyObject *)it;
Raymond Hettinger1e5809f2004-03-18 11:04:57 +00001814}
1815
1816static PyObject *
1817dequereviter_next(dequeiterobject *it)
1818{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001819 PyObject *item;
1820 if (it->counter == 0)
1821 return NULL;
Raymond Hettinger1e5809f2004-03-18 11:04:57 +00001822
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001823 if (it->deque->state != it->state) {
1824 it->counter = 0;
1825 PyErr_SetString(PyExc_RuntimeError,
1826 "deque mutated during iteration");
1827 return NULL;
1828 }
1829 assert (!(it->b == it->deque->leftblock &&
1830 it->index < it->deque->leftindex));
Raymond Hettinger1e5809f2004-03-18 11:04:57 +00001831
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001832 item = it->b->data[it->index];
1833 it->index--;
1834 it->counter--;
Raymond Hettingerd3d2b2c2015-09-21 23:41:56 -07001835 if (it->index < 0 && it->counter > 0) {
Raymond Hettinger82df9252013-07-07 01:43:42 -10001836 CHECK_NOT_END(it->b->leftlink);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001837 it->b = it->b->leftlink;
1838 it->index = BLOCKLEN - 1;
1839 }
1840 Py_INCREF(item);
1841 return item;
Raymond Hettinger1e5809f2004-03-18 11:04:57 +00001842}
1843
Kristján Valur Jónsson31668b82012-04-03 10:49:41 +00001844static PyObject *
1845dequereviter_new(PyTypeObject *type, PyObject *args, PyObject *kwds)
1846{
1847 Py_ssize_t i, index=0;
1848 PyObject *deque;
1849 dequeiterobject *it;
1850 if (!PyArg_ParseTuple(args, "O!|n", &deque_type, &deque, &index))
1851 return NULL;
1852 assert(type == &dequereviter_type);
1853
1854 it = (dequeiterobject*)deque_reviter((dequeobject *)deque);
1855 if (!it)
1856 return NULL;
1857 /* consume items from the queue */
1858 for(i=0; i<index; i++) {
1859 PyObject *item = dequereviter_next(it);
1860 if (item) {
1861 Py_DECREF(item);
1862 } else {
1863 if (it->counter) {
1864 Py_DECREF(it);
1865 return NULL;
1866 } else
1867 break;
1868 }
1869 }
1870 return (PyObject*)it;
1871}
1872
Martin v. Löwis59683e82008-06-13 07:50:45 +00001873static PyTypeObject dequereviter_type = {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001874 PyVarObject_HEAD_INIT(NULL, 0)
Raymond Hettinger87e69122015-03-02 23:32:02 -08001875 "_collections._deque_reverse_iterator", /* tp_name */
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001876 sizeof(dequeiterobject), /* tp_basicsize */
1877 0, /* tp_itemsize */
1878 /* methods */
1879 (destructor)dequeiter_dealloc, /* tp_dealloc */
1880 0, /* tp_print */
1881 0, /* tp_getattr */
1882 0, /* tp_setattr */
1883 0, /* tp_reserved */
1884 0, /* tp_repr */
1885 0, /* tp_as_number */
1886 0, /* tp_as_sequence */
1887 0, /* tp_as_mapping */
1888 0, /* tp_hash */
1889 0, /* tp_call */
1890 0, /* tp_str */
1891 PyObject_GenericGetAttr, /* tp_getattro */
1892 0, /* tp_setattro */
1893 0, /* tp_as_buffer */
Raymond Hettinger87e69122015-03-02 23:32:02 -08001894 Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC, /* tp_flags */
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001895 0, /* tp_doc */
1896 (traverseproc)dequeiter_traverse, /* tp_traverse */
1897 0, /* tp_clear */
1898 0, /* tp_richcompare */
1899 0, /* tp_weaklistoffset */
1900 PyObject_SelfIter, /* tp_iter */
1901 (iternextfunc)dequereviter_next, /* tp_iternext */
1902 dequeiter_methods, /* tp_methods */
Kristján Valur Jónsson31668b82012-04-03 10:49:41 +00001903 0, /* tp_members */
1904 0, /* tp_getset */
1905 0, /* tp_base */
1906 0, /* tp_dict */
1907 0, /* tp_descr_get */
1908 0, /* tp_descr_set */
1909 0, /* tp_dictoffset */
1910 0, /* tp_init */
1911 0, /* tp_alloc */
1912 dequereviter_new, /* tp_new */
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001913 0,
Raymond Hettinger1e5809f2004-03-18 11:04:57 +00001914};
1915
Guido van Rossum1968ad32006-02-25 22:38:04 +00001916/* defaultdict type *********************************************************/
1917
1918typedef struct {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001919 PyDictObject dict;
1920 PyObject *default_factory;
Guido van Rossum1968ad32006-02-25 22:38:04 +00001921} defdictobject;
1922
1923static PyTypeObject defdict_type; /* Forward */
1924
1925PyDoc_STRVAR(defdict_missing_doc,
1926"__missing__(key) # Called by __getitem__ for missing key; pseudo-code:\n\
Guido van Rossumd8faa362007-04-27 19:54:29 +00001927 if self.default_factory is None: raise KeyError((key,))\n\
Guido van Rossum1968ad32006-02-25 22:38:04 +00001928 self[key] = value = self.default_factory()\n\
1929 return value\n\
1930");
1931
1932static PyObject *
1933defdict_missing(defdictobject *dd, PyObject *key)
1934{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001935 PyObject *factory = dd->default_factory;
1936 PyObject *value;
1937 if (factory == NULL || factory == Py_None) {
1938 /* XXX Call dict.__missing__(key) */
1939 PyObject *tup;
1940 tup = PyTuple_Pack(1, key);
1941 if (!tup) return NULL;
1942 PyErr_SetObject(PyExc_KeyError, tup);
1943 Py_DECREF(tup);
1944 return NULL;
1945 }
1946 value = PyEval_CallObject(factory, NULL);
1947 if (value == NULL)
1948 return value;
1949 if (PyObject_SetItem((PyObject *)dd, key, value) < 0) {
1950 Py_DECREF(value);
1951 return NULL;
1952 }
1953 return value;
Guido van Rossum1968ad32006-02-25 22:38:04 +00001954}
1955
1956PyDoc_STRVAR(defdict_copy_doc, "D.copy() -> a shallow copy of D.");
1957
1958static PyObject *
1959defdict_copy(defdictobject *dd)
1960{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001961 /* This calls the object's class. That only works for subclasses
1962 whose class constructor has the same signature. Subclasses that
1963 define a different constructor signature must override copy().
1964 */
Raymond Hettinger54628fa2009-08-04 19:16:39 +00001965
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001966 if (dd->default_factory == NULL)
1967 return PyObject_CallFunctionObjArgs((PyObject*)Py_TYPE(dd), Py_None, dd, NULL);
1968 return PyObject_CallFunctionObjArgs((PyObject*)Py_TYPE(dd),
1969 dd->default_factory, dd, NULL);
Guido van Rossum1968ad32006-02-25 22:38:04 +00001970}
1971
1972static PyObject *
1973defdict_reduce(defdictobject *dd)
1974{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001975 /* __reduce__ must return a 5-tuple as follows:
Guido van Rossum1968ad32006-02-25 22:38:04 +00001976
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001977 - factory function
1978 - tuple of args for the factory function
1979 - additional state (here None)
1980 - sequence iterator (here None)
1981 - dictionary iterator (yielding successive (key, value) pairs
Guido van Rossum1968ad32006-02-25 22:38:04 +00001982
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001983 This API is used by pickle.py and copy.py.
Guido van Rossum1968ad32006-02-25 22:38:04 +00001984
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001985 For this to be useful with pickle.py, the default_factory
1986 must be picklable; e.g., None, a built-in, or a global
1987 function in a module or package.
Guido van Rossum1968ad32006-02-25 22:38:04 +00001988
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001989 Both shallow and deep copying are supported, but for deep
1990 copying, the default_factory must be deep-copyable; e.g. None,
1991 or a built-in (functions are not copyable at this time).
Guido van Rossum1968ad32006-02-25 22:38:04 +00001992
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001993 This only works for subclasses as long as their constructor
1994 signature is compatible; the first argument must be the
1995 optional default_factory, defaulting to None.
1996 */
1997 PyObject *args;
1998 PyObject *items;
1999 PyObject *iter;
2000 PyObject *result;
Martin v. Löwisbd928fe2011-10-14 10:20:37 +02002001 _Py_IDENTIFIER(items);
Martin v. Löwisafe55bb2011-10-09 10:38:36 +02002002
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002003 if (dd->default_factory == NULL || dd->default_factory == Py_None)
2004 args = PyTuple_New(0);
2005 else
2006 args = PyTuple_Pack(1, dd->default_factory);
2007 if (args == NULL)
2008 return NULL;
Martin v. Löwisafe55bb2011-10-09 10:38:36 +02002009 items = _PyObject_CallMethodId((PyObject *)dd, &PyId_items, "()");
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002010 if (items == NULL) {
2011 Py_DECREF(args);
2012 return NULL;
2013 }
2014 iter = PyObject_GetIter(items);
2015 if (iter == NULL) {
2016 Py_DECREF(items);
2017 Py_DECREF(args);
2018 return NULL;
2019 }
2020 result = PyTuple_Pack(5, Py_TYPE(dd), args,
2021 Py_None, Py_None, iter);
2022 Py_DECREF(iter);
2023 Py_DECREF(items);
2024 Py_DECREF(args);
2025 return result;
Guido van Rossum1968ad32006-02-25 22:38:04 +00002026}
2027
2028static PyMethodDef defdict_methods[] = {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002029 {"__missing__", (PyCFunction)defdict_missing, METH_O,
2030 defdict_missing_doc},
2031 {"copy", (PyCFunction)defdict_copy, METH_NOARGS,
2032 defdict_copy_doc},
2033 {"__copy__", (PyCFunction)defdict_copy, METH_NOARGS,
2034 defdict_copy_doc},
2035 {"__reduce__", (PyCFunction)defdict_reduce, METH_NOARGS,
2036 reduce_doc},
2037 {NULL}
Guido van Rossum1968ad32006-02-25 22:38:04 +00002038};
2039
2040static PyMemberDef defdict_members[] = {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002041 {"default_factory", T_OBJECT,
2042 offsetof(defdictobject, default_factory), 0,
2043 PyDoc_STR("Factory for default value called by __missing__().")},
2044 {NULL}
Guido van Rossum1968ad32006-02-25 22:38:04 +00002045};
2046
2047static void
2048defdict_dealloc(defdictobject *dd)
2049{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002050 Py_CLEAR(dd->default_factory);
2051 PyDict_Type.tp_dealloc((PyObject *)dd);
Guido van Rossum1968ad32006-02-25 22:38:04 +00002052}
2053
Guido van Rossum1968ad32006-02-25 22:38:04 +00002054static PyObject *
2055defdict_repr(defdictobject *dd)
2056{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002057 PyObject *baserepr;
2058 PyObject *defrepr;
2059 PyObject *result;
2060 baserepr = PyDict_Type.tp_repr((PyObject *)dd);
2061 if (baserepr == NULL)
2062 return NULL;
2063 if (dd->default_factory == NULL)
2064 defrepr = PyUnicode_FromString("None");
2065 else
2066 {
2067 int status = Py_ReprEnter(dd->default_factory);
2068 if (status != 0) {
Antoine Pitrouf5f1fe02012-02-15 02:42:46 +01002069 if (status < 0) {
2070 Py_DECREF(baserepr);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002071 return NULL;
Antoine Pitrouf5f1fe02012-02-15 02:42:46 +01002072 }
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002073 defrepr = PyUnicode_FromString("...");
2074 }
2075 else
2076 defrepr = PyObject_Repr(dd->default_factory);
2077 Py_ReprLeave(dd->default_factory);
2078 }
2079 if (defrepr == NULL) {
2080 Py_DECREF(baserepr);
2081 return NULL;
2082 }
2083 result = PyUnicode_FromFormat("defaultdict(%U, %U)",
2084 defrepr, baserepr);
2085 Py_DECREF(defrepr);
2086 Py_DECREF(baserepr);
2087 return result;
Guido van Rossum1968ad32006-02-25 22:38:04 +00002088}
2089
2090static int
2091defdict_traverse(PyObject *self, visitproc visit, void *arg)
2092{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002093 Py_VISIT(((defdictobject *)self)->default_factory);
2094 return PyDict_Type.tp_traverse(self, visit, arg);
Guido van Rossum1968ad32006-02-25 22:38:04 +00002095}
2096
2097static int
2098defdict_tp_clear(defdictobject *dd)
2099{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002100 Py_CLEAR(dd->default_factory);
2101 return PyDict_Type.tp_clear((PyObject *)dd);
Guido van Rossum1968ad32006-02-25 22:38:04 +00002102}
2103
2104static int
2105defdict_init(PyObject *self, PyObject *args, PyObject *kwds)
2106{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002107 defdictobject *dd = (defdictobject *)self;
2108 PyObject *olddefault = dd->default_factory;
2109 PyObject *newdefault = NULL;
2110 PyObject *newargs;
2111 int result;
2112 if (args == NULL || !PyTuple_Check(args))
2113 newargs = PyTuple_New(0);
2114 else {
2115 Py_ssize_t n = PyTuple_GET_SIZE(args);
2116 if (n > 0) {
2117 newdefault = PyTuple_GET_ITEM(args, 0);
2118 if (!PyCallable_Check(newdefault) && newdefault != Py_None) {
2119 PyErr_SetString(PyExc_TypeError,
Raymond Hettinger239aba72015-07-20 03:09:22 -04002120 "first argument must be callable or None");
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002121 return -1;
2122 }
2123 }
2124 newargs = PySequence_GetSlice(args, 1, n);
2125 }
2126 if (newargs == NULL)
2127 return -1;
2128 Py_XINCREF(newdefault);
2129 dd->default_factory = newdefault;
2130 result = PyDict_Type.tp_init(self, newargs, kwds);
2131 Py_DECREF(newargs);
2132 Py_XDECREF(olddefault);
2133 return result;
Guido van Rossum1968ad32006-02-25 22:38:04 +00002134}
2135
2136PyDoc_STRVAR(defdict_doc,
Benjamin Peterson9cb33b72014-01-13 23:56:05 -05002137"defaultdict(default_factory[, ...]) --> dict with default factory\n\
Guido van Rossum1968ad32006-02-25 22:38:04 +00002138\n\
2139The default factory is called without arguments to produce\n\
2140a new value when a key is not present, in __getitem__ only.\n\
2141A defaultdict compares equal to a dict with the same items.\n\
Benjamin Peterson9cb33b72014-01-13 23:56:05 -05002142All remaining arguments are treated the same as if they were\n\
2143passed to the dict constructor, including keyword arguments.\n\
Guido van Rossum1968ad32006-02-25 22:38:04 +00002144");
2145
Thomas Wouters49fd7fa2006-04-21 10:40:58 +00002146/* See comment in xxsubtype.c */
2147#define DEFERRED_ADDRESS(ADDR) 0
2148
Guido van Rossum1968ad32006-02-25 22:38:04 +00002149static PyTypeObject defdict_type = {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002150 PyVarObject_HEAD_INIT(DEFERRED_ADDRESS(&PyType_Type), 0)
2151 "collections.defaultdict", /* tp_name */
2152 sizeof(defdictobject), /* tp_basicsize */
2153 0, /* tp_itemsize */
2154 /* methods */
2155 (destructor)defdict_dealloc, /* tp_dealloc */
2156 0, /* tp_print */
2157 0, /* tp_getattr */
2158 0, /* tp_setattr */
2159 0, /* tp_reserved */
2160 (reprfunc)defdict_repr, /* tp_repr */
2161 0, /* tp_as_number */
2162 0, /* tp_as_sequence */
2163 0, /* tp_as_mapping */
2164 0, /* tp_hash */
2165 0, /* tp_call */
2166 0, /* tp_str */
2167 PyObject_GenericGetAttr, /* tp_getattro */
2168 0, /* tp_setattro */
2169 0, /* tp_as_buffer */
2170 Py_TPFLAGS_DEFAULT | Py_TPFLAGS_BASETYPE | Py_TPFLAGS_HAVE_GC,
2171 /* tp_flags */
2172 defdict_doc, /* tp_doc */
2173 defdict_traverse, /* tp_traverse */
2174 (inquiry)defdict_tp_clear, /* tp_clear */
2175 0, /* tp_richcompare */
2176 0, /* tp_weaklistoffset*/
2177 0, /* tp_iter */
2178 0, /* tp_iternext */
2179 defdict_methods, /* tp_methods */
2180 defdict_members, /* tp_members */
2181 0, /* tp_getset */
2182 DEFERRED_ADDRESS(&PyDict_Type), /* tp_base */
2183 0, /* tp_dict */
2184 0, /* tp_descr_get */
2185 0, /* tp_descr_set */
2186 0, /* tp_dictoffset */
2187 defdict_init, /* tp_init */
2188 PyType_GenericAlloc, /* tp_alloc */
2189 0, /* tp_new */
2190 PyObject_GC_Del, /* tp_free */
Guido van Rossum1968ad32006-02-25 22:38:04 +00002191};
2192
Raymond Hettinger96f34102010-12-15 16:30:37 +00002193/* helper function for Counter *********************************************/
2194
2195PyDoc_STRVAR(_count_elements_doc,
2196"_count_elements(mapping, iterable) -> None\n\
2197\n\
2198Count elements in the iterable, updating the mappping");
2199
2200static PyObject *
2201_count_elements(PyObject *self, PyObject *args)
2202{
Raymond Hettingercb1d96f2013-10-04 16:51:02 -07002203 _Py_IDENTIFIER(get);
Raymond Hettinger2ff21902013-10-01 00:55:43 -07002204 _Py_IDENTIFIER(__setitem__);
Raymond Hettinger96f34102010-12-15 16:30:37 +00002205 PyObject *it, *iterable, *mapping, *oldval;
2206 PyObject *newval = NULL;
2207 PyObject *key = NULL;
Raymond Hettinger224c87d2013-10-01 21:36:09 -07002208 PyObject *zero = NULL;
Raymond Hettinger96f34102010-12-15 16:30:37 +00002209 PyObject *one = NULL;
Raymond Hettingercb1d96f2013-10-04 16:51:02 -07002210 PyObject *bound_get = NULL;
2211 PyObject *mapping_get;
2212 PyObject *dict_get;
Raymond Hettinger2ff21902013-10-01 00:55:43 -07002213 PyObject *mapping_setitem;
Raymond Hettinger2ff21902013-10-01 00:55:43 -07002214 PyObject *dict_setitem;
Raymond Hettinger96f34102010-12-15 16:30:37 +00002215
2216 if (!PyArg_UnpackTuple(args, "_count_elements", 2, 2, &mapping, &iterable))
2217 return NULL;
2218
Raymond Hettinger96f34102010-12-15 16:30:37 +00002219 it = PyObject_GetIter(iterable);
2220 if (it == NULL)
2221 return NULL;
Raymond Hettinger426e0522011-01-03 02:12:02 +00002222
Raymond Hettinger96f34102010-12-15 16:30:37 +00002223 one = PyLong_FromLong(1);
Raymond Hettinger224c87d2013-10-01 21:36:09 -07002224 if (one == NULL)
2225 goto done;
Raymond Hettinger426e0522011-01-03 02:12:02 +00002226
Raymond Hettingercb1d96f2013-10-04 16:51:02 -07002227 /* Only take the fast path when get() and __setitem__()
2228 * have not been overridden.
2229 */
2230 mapping_get = _PyType_LookupId(Py_TYPE(mapping), &PyId_get);
2231 dict_get = _PyType_LookupId(&PyDict_Type, &PyId_get);
Raymond Hettinger2ff21902013-10-01 00:55:43 -07002232 mapping_setitem = _PyType_LookupId(Py_TYPE(mapping), &PyId___setitem__);
2233 dict_setitem = _PyType_LookupId(&PyDict_Type, &PyId___setitem__);
2234
Raymond Hettingercb1d96f2013-10-04 16:51:02 -07002235 if (mapping_get != NULL && mapping_get == dict_get &&
2236 mapping_setitem != NULL && mapping_setitem == dict_setitem) {
Raymond Hettinger426e0522011-01-03 02:12:02 +00002237 while (1) {
Raymond Hettinger507d9972014-05-18 21:32:40 +01002238 /* Fast path advantages:
2239 1. Eliminate double hashing
2240 (by re-using the same hash for both the get and set)
2241 2. Avoid argument overhead of PyObject_CallFunctionObjArgs
2242 (argument tuple creation and parsing)
2243 3. Avoid indirection through a bound method object
2244 (creates another argument tuple)
2245 4. Avoid initial increment from zero
2246 (reuse an existing one-object instead)
2247 */
Raymond Hettinger4b0b1ac2014-05-03 16:41:19 -07002248 Py_hash_t hash;
2249
Raymond Hettinger426e0522011-01-03 02:12:02 +00002250 key = PyIter_Next(it);
Victor Stinnera154b5c2011-04-20 23:23:52 +02002251 if (key == NULL)
2252 break;
Raymond Hettinger4b0b1ac2014-05-03 16:41:19 -07002253
2254 if (!PyUnicode_CheckExact(key) ||
2255 (hash = ((PyASCIIObject *) key)->hash) == -1)
2256 {
2257 hash = PyObject_Hash(key);
Raymond Hettingerda2850f2015-02-27 12:42:54 -08002258 if (hash == -1)
Raymond Hettinger4b0b1ac2014-05-03 16:41:19 -07002259 goto done;
2260 }
2261
2262 oldval = _PyDict_GetItem_KnownHash(mapping, key, hash);
Raymond Hettinger426e0522011-01-03 02:12:02 +00002263 if (oldval == NULL) {
Raymond Hettinger28c995d2015-08-14 02:07:41 -07002264 if (_PyDict_SetItem_KnownHash(mapping, key, one, hash) < 0)
Raymond Hettinger507d9972014-05-18 21:32:40 +01002265 goto done;
Raymond Hettinger426e0522011-01-03 02:12:02 +00002266 } else {
2267 newval = PyNumber_Add(oldval, one);
2268 if (newval == NULL)
Raymond Hettinger507d9972014-05-18 21:32:40 +01002269 goto done;
Raymond Hettinger28c995d2015-08-14 02:07:41 -07002270 if (_PyDict_SetItem_KnownHash(mapping, key, newval, hash) < 0)
Raymond Hettinger507d9972014-05-18 21:32:40 +01002271 goto done;
Raymond Hettinger426e0522011-01-03 02:12:02 +00002272 Py_CLEAR(newval);
2273 }
2274 Py_DECREF(key);
Raymond Hettinger96f34102010-12-15 16:30:37 +00002275 }
Raymond Hettinger426e0522011-01-03 02:12:02 +00002276 } else {
Victor Stinnere7f516c2013-11-06 23:52:55 +01002277 bound_get = _PyObject_GetAttrId(mapping, &PyId_get);
Raymond Hettingercb1d96f2013-10-04 16:51:02 -07002278 if (bound_get == NULL)
Raymond Hettinger224c87d2013-10-01 21:36:09 -07002279 goto done;
2280
2281 zero = PyLong_FromLong(0);
2282 if (zero == NULL)
2283 goto done;
2284
Raymond Hettinger426e0522011-01-03 02:12:02 +00002285 while (1) {
2286 key = PyIter_Next(it);
Victor Stinnera154b5c2011-04-20 23:23:52 +02002287 if (key == NULL)
2288 break;
Raymond Hettingercb1d96f2013-10-04 16:51:02 -07002289 oldval = PyObject_CallFunctionObjArgs(bound_get, key, zero, NULL);
Raymond Hettinger224c87d2013-10-01 21:36:09 -07002290 if (oldval == NULL)
2291 break;
2292 newval = PyNumber_Add(oldval, one);
2293 Py_DECREF(oldval);
2294 if (newval == NULL)
2295 break;
Raymond Hettinger28c995d2015-08-14 02:07:41 -07002296 if (PyObject_SetItem(mapping, key, newval) < 0)
Raymond Hettinger96f34102010-12-15 16:30:37 +00002297 break;
2298 Py_CLEAR(newval);
Raymond Hettinger426e0522011-01-03 02:12:02 +00002299 Py_DECREF(key);
Raymond Hettinger96f34102010-12-15 16:30:37 +00002300 }
Raymond Hettinger96f34102010-12-15 16:30:37 +00002301 }
Raymond Hettinger426e0522011-01-03 02:12:02 +00002302
Raymond Hettinger224c87d2013-10-01 21:36:09 -07002303done:
Raymond Hettinger96f34102010-12-15 16:30:37 +00002304 Py_DECREF(it);
2305 Py_XDECREF(key);
2306 Py_XDECREF(newval);
Raymond Hettingercb1d96f2013-10-04 16:51:02 -07002307 Py_XDECREF(bound_get);
Raymond Hettinger224c87d2013-10-01 21:36:09 -07002308 Py_XDECREF(zero);
2309 Py_XDECREF(one);
Raymond Hettinger96f34102010-12-15 16:30:37 +00002310 if (PyErr_Occurred())
2311 return NULL;
2312 Py_RETURN_NONE;
2313}
2314
Raymond Hettinger756b3f32004-01-29 06:37:52 +00002315/* module level code ********************************************************/
2316
2317PyDoc_STRVAR(module_doc,
Guido van Rossum1968ad32006-02-25 22:38:04 +00002318"High performance data structures.\n\
2319- deque: ordered collection accessible from endpoints only\n\
2320- defaultdict: dict subclass with a default value factory\n\
Raymond Hettinger756b3f32004-01-29 06:37:52 +00002321");
2322
Raymond Hettinger96f34102010-12-15 16:30:37 +00002323static struct PyMethodDef module_functions[] = {
2324 {"_count_elements", _count_elements, METH_VARARGS, _count_elements_doc},
2325 {NULL, NULL} /* sentinel */
2326};
Martin v. Löwis1a214512008-06-11 05:26:20 +00002327
2328static struct PyModuleDef _collectionsmodule = {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002329 PyModuleDef_HEAD_INIT,
2330 "_collections",
2331 module_doc,
2332 -1,
Raymond Hettinger96f34102010-12-15 16:30:37 +00002333 module_functions,
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002334 NULL,
2335 NULL,
2336 NULL,
2337 NULL
Martin v. Löwis1a214512008-06-11 05:26:20 +00002338};
2339
Raymond Hettinger756b3f32004-01-29 06:37:52 +00002340PyMODINIT_FUNC
Martin v. Löwis1a214512008-06-11 05:26:20 +00002341PyInit__collections(void)
Raymond Hettinger756b3f32004-01-29 06:37:52 +00002342{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002343 PyObject *m;
Raymond Hettinger756b3f32004-01-29 06:37:52 +00002344
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002345 m = PyModule_Create(&_collectionsmodule);
2346 if (m == NULL)
2347 return NULL;
Raymond Hettinger756b3f32004-01-29 06:37:52 +00002348
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002349 if (PyType_Ready(&deque_type) < 0)
2350 return NULL;
2351 Py_INCREF(&deque_type);
2352 PyModule_AddObject(m, "deque", (PyObject *)&deque_type);
Raymond Hettinger756b3f32004-01-29 06:37:52 +00002353
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002354 defdict_type.tp_base = &PyDict_Type;
2355 if (PyType_Ready(&defdict_type) < 0)
2356 return NULL;
2357 Py_INCREF(&defdict_type);
2358 PyModule_AddObject(m, "defaultdict", (PyObject *)&defdict_type);
Guido van Rossum1968ad32006-02-25 22:38:04 +00002359
Eric Snow47db7172015-05-29 22:21:39 -06002360 Py_INCREF(&PyODict_Type);
2361 PyModule_AddObject(m, "OrderedDict", (PyObject *)&PyODict_Type);
2362
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002363 if (PyType_Ready(&dequeiter_type) < 0)
2364 return NULL;
Kristján Valur Jónsson31668b82012-04-03 10:49:41 +00002365 Py_INCREF(&dequeiter_type);
2366 PyModule_AddObject(m, "_deque_iterator", (PyObject *)&dequeiter_type);
Raymond Hettinger756b3f32004-01-29 06:37:52 +00002367
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002368 if (PyType_Ready(&dequereviter_type) < 0)
2369 return NULL;
Kristján Valur Jónsson31668b82012-04-03 10:49:41 +00002370 Py_INCREF(&dequereviter_type);
2371 PyModule_AddObject(m, "_deque_reverse_iterator", (PyObject *)&dequereviter_type);
Raymond Hettinger1e5809f2004-03-18 11:04:57 +00002372
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002373 return m;
Raymond Hettinger756b3f32004-01-29 06:37:52 +00002374}