blob: 9f6c47f54a9eb74d5b41b9658e6efdbc25fcdbc5 [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 Hettingereb6b5542015-02-10 22:37:22 -060012 Copyright (c) 2004-2015 Python Software Foundation.
Raymond Hettinger756b3f32004-01-29 06:37:52 +000013 All rights reserved.
14*/
15
Raymond Hettinger77e8bf12004-10-01 15:25:53 +000016/* The block length may be set to any number over 1. Larger numbers
Raymond Hettinger20b0f872013-06-23 15:44:33 -070017 * reduce the number of calls to the memory allocator, give faster
Raymond Hettinger30c90742015-03-02 22:31:35 -080018 * indexing and rotation, and reduce the link to data overhead ratio.
Raymond Hettingerdaf57f22015-02-26 23:21:29 -080019 * Making the block length a power of two speeds-up the modulo
Raymond Hettinger30c90742015-03-02 22:31:35 -080020 * and division calculations in deque_item() and deque_ass_item().
Raymond Hettinger77e8bf12004-10-01 15:25:53 +000021 */
22
Raymond Hettingerdaf57f22015-02-26 23:21:29 -080023#define BLOCKLEN 64
Raymond Hettinger61f05fb2004-10-01 06:24:12 +000024#define CENTER ((BLOCKLEN - 1) / 2)
Raymond Hettinger756b3f32004-01-29 06:37:52 +000025
Raymond Hettinger551350a2015-03-24 00:19:53 -070026/* Data for deque objects is stored in a doubly-linked list of fixed
27 * length blocks. This assures that appends or pops never move any
28 * other data elements besides the one being appended or popped.
29 *
30 * Another advantage is that it completely avoids use of realloc(),
31 * resulting in more predictable performance.
32 *
33 * Textbook implementations of doubly-linked lists store one datum
34 * per link, but that gives them a 200% memory overhead (a prev and
35 * next link for each datum) and it costs one malloc() call per data
36 * element. By using fixed-length blocks, the link to data ratio is
37 * significantly improved and there are proportionally fewer calls
38 * to malloc() and free(). The data blocks of consecutive pointers
39 * also improve cache locality.
40 *
Raymond Hettinger61f05fb2004-10-01 06:24:12 +000041 * The list of blocks is never empty, so d.leftblock and d.rightblock
Raymond Hettinger82df9252013-07-07 01:43:42 -100042 * are never equal to NULL. The list is not circular.
43 *
44 * A deque d's first element is at d.leftblock[leftindex]
45 * and its last element is at d.rightblock[rightindex].
Raymond Hettinger61f05fb2004-10-01 06:24:12 +000046 *
Raymond Hettinger551350a2015-03-24 00:19:53 -070047 * Unlike Python slice indices, these indices are inclusive on both
48 * ends. This makes the algorithms for left and right operations
49 * more symmetrical and it simplifies the design.
Raymond Hettinger61f05fb2004-10-01 06:24:12 +000050 *
Raymond Hettinger551350a2015-03-24 00:19:53 -070051 * The indices, d.leftindex and d.rightindex are always in the range:
52 * 0 <= index < BLOCKLEN
53 *
54 * And their exact relationship is:
55 * (d.leftindex + d.len - 1) % BLOCKLEN == d.rightindex
Raymond Hettinger61f05fb2004-10-01 06:24:12 +000056 *
Raymond Hettinger8dbbae22015-03-24 21:01:50 -070057 * Whenever d.leftblock == d.rightblock, then:
Raymond Hettinger551350a2015-03-24 00:19:53 -070058 * d.leftindex + d.len - 1 == d.rightindex
Thomas Wouters0e3f5912006-08-11 14:57:12 +000059 *
Raymond Hettinger551350a2015-03-24 00:19:53 -070060 * However, when d.leftblock != d.rightblock, the d.leftindex and
61 * d.rightindex become indices into distinct blocks and either may
62 * be larger than the other.
63 *
64 * Empty deques have:
65 * d.len == 0
66 * d.leftblock == d.rightblock
67 * d.leftindex == CENTER + 1
68 * d.rightindex == CENTER
69 *
70 * Checking for d.len == 0 is the intended way to see whether d is empty.
Tim Petersd8768d32004-10-01 01:32:53 +000071 */
72
Raymond Hettinger756b3f32004-01-29 06:37:52 +000073typedef struct BLOCK {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +000074 struct BLOCK *leftlink;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +000075 PyObject *data[BLOCKLEN];
Raymond Hettinger20b0f872013-06-23 15:44:33 -070076 struct BLOCK *rightlink;
Raymond Hettinger756b3f32004-01-29 06:37:52 +000077} block;
78
Raymond Hettinger30c90742015-03-02 22:31:35 -080079typedef struct {
80 PyObject_VAR_HEAD
81 block *leftblock;
82 block *rightblock;
Raymond Hettinger551350a2015-03-24 00:19:53 -070083 Py_ssize_t leftindex; /* 0 <= leftindex < BLOCKLEN */
84 Py_ssize_t rightindex; /* 0 <= rightindex < BLOCKLEN */
Raymond Hettingerf9d9c792015-03-02 22:47:46 -080085 size_t state; /* incremented whenever the indices move */
Raymond Hettinger30c90742015-03-02 22:31:35 -080086 Py_ssize_t maxlen;
Raymond Hettinger0f6f9472015-03-21 01:42:10 -070087 PyObject *weakreflist;
Raymond Hettinger30c90742015-03-02 22:31:35 -080088} dequeobject;
89
90static PyTypeObject deque_type;
91
Raymond Hettinger82df9252013-07-07 01:43:42 -100092/* For debug builds, add error checking to track the endpoints
93 * in the chain of links. The goal is to make sure that link
94 * assignments only take place at endpoints so that links already
95 * in use do not get overwritten.
96 *
97 * CHECK_END should happen before each assignment to a block's link field.
98 * MARK_END should happen whenever a link field becomes a new endpoint.
99 * This happens when new blocks are added or whenever an existing
100 * block is freed leaving another existing block as the new endpoint.
101 */
102
Raymond Hettinger3223dd52013-07-26 23:14:22 -0700103#ifndef NDEBUG
Raymond Hettinger82df9252013-07-07 01:43:42 -1000104#define MARK_END(link) link = NULL;
105#define CHECK_END(link) assert(link == NULL);
106#define CHECK_NOT_END(link) assert(link != NULL);
107#else
108#define MARK_END(link)
109#define CHECK_END(link)
110#define CHECK_NOT_END(link)
111#endif
112
Raymond Hettinger41290a62015-03-31 08:12:23 -0700113/* To prevent len from overflowing PY_SSIZE_T_MAX, we refuse to
114 allocate new blocks if the current len is nearing overflow.
115*/
116
117#define MAX_DEQUE_LEN (PY_SSIZE_T_MAX - 3*BLOCKLEN)
118
Raymond Hettinger82df9252013-07-07 01:43:42 -1000119/* A simple freelisting scheme is used to minimize calls to the memory
Raymond Hettinger551350a2015-03-24 00:19:53 -0700120 allocator. It accommodates common use cases where new blocks are being
Raymond Hettinger82df9252013-07-07 01:43:42 -1000121 added at about the same rate as old blocks are being freed.
122 */
123
Guido van Rossum58da9312007-11-10 23:39:45 +0000124#define MAXFREEBLOCKS 10
Benjamin Petersond6313712008-07-31 16:23:04 +0000125static Py_ssize_t numfreeblocks = 0;
Guido van Rossum58da9312007-11-10 23:39:45 +0000126static block *freeblocks[MAXFREEBLOCKS];
127
Tim Peters6f853562004-10-01 01:04:50 +0000128static block *
Raymond Hettinger82df9252013-07-07 01:43:42 -1000129newblock(Py_ssize_t len) {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000130 block *b;
Raymond Hettinger41290a62015-03-31 08:12:23 -0700131 if (len >= MAX_DEQUE_LEN) {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000132 PyErr_SetString(PyExc_OverflowError,
133 "cannot add more blocks to the deque");
134 return NULL;
135 }
136 if (numfreeblocks) {
Raymond Hettinger59cf23a2013-02-07 00:57:19 -0500137 numfreeblocks--;
Raymond Hettinger82df9252013-07-07 01:43:42 -1000138 return freeblocks[numfreeblocks];
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000139 }
Raymond Hettinger82df9252013-07-07 01:43:42 -1000140 b = PyMem_Malloc(sizeof(block));
141 if (b != NULL) {
142 return b;
143 }
144 PyErr_NoMemory();
145 return NULL;
Raymond Hettinger756b3f32004-01-29 06:37:52 +0000146}
147
Martin v. Löwis59683e82008-06-13 07:50:45 +0000148static void
Guido van Rossum58da9312007-11-10 23:39:45 +0000149freeblock(block *b)
150{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000151 if (numfreeblocks < MAXFREEBLOCKS) {
152 freeblocks[numfreeblocks] = b;
153 numfreeblocks++;
154 } else {
155 PyMem_Free(b);
156 }
Guido van Rossum58da9312007-11-10 23:39:45 +0000157}
158
Raymond Hettingerda2850f2015-02-27 12:42:54 -0800159/* XXX Todo:
Raymond Hettinger54023152014-04-23 00:58:48 -0700160 If aligned memory allocations become available, make the
161 deque object 64 byte aligned so that all of the fields
162 can be retrieved or updated in a single cache line.
163*/
164
Raymond Hettinger756b3f32004-01-29 06:37:52 +0000165static PyObject *
166deque_new(PyTypeObject *type, PyObject *args, PyObject *kwds)
167{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000168 dequeobject *deque;
169 block *b;
Raymond Hettinger756b3f32004-01-29 06:37:52 +0000170
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000171 /* create dequeobject structure */
172 deque = (dequeobject *)type->tp_alloc(type, 0);
173 if (deque == NULL)
174 return NULL;
Tim Peters1065f752004-10-01 01:03:29 +0000175
Raymond Hettinger82df9252013-07-07 01:43:42 -1000176 b = newblock(0);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000177 if (b == NULL) {
178 Py_DECREF(deque);
179 return NULL;
180 }
Raymond Hettinger82df9252013-07-07 01:43:42 -1000181 MARK_END(b->leftlink);
182 MARK_END(b->rightlink);
Raymond Hettinger756b3f32004-01-29 06:37:52 +0000183
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000184 assert(BLOCKLEN >= 2);
Raymond Hettinger87e69122015-03-02 23:32:02 -0800185 Py_SIZE(deque) = 0;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000186 deque->leftblock = b;
187 deque->rightblock = b;
188 deque->leftindex = CENTER + 1;
189 deque->rightindex = CENTER;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000190 deque->state = 0;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000191 deque->maxlen = -1;
Raymond Hettinger87e69122015-03-02 23:32:02 -0800192 deque->weakreflist = NULL;
Raymond Hettinger756b3f32004-01-29 06:37:52 +0000193
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000194 return (PyObject *)deque;
Raymond Hettinger756b3f32004-01-29 06:37:52 +0000195}
196
197static PyObject *
Raymond Hettinger756b3f32004-01-29 06:37:52 +0000198deque_pop(dequeobject *deque, PyObject *unused)
199{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000200 PyObject *item;
201 block *prevblock;
Raymond Hettinger756b3f32004-01-29 06:37:52 +0000202
Raymond Hettingerdf715ba2013-07-06 13:01:13 -1000203 if (Py_SIZE(deque) == 0) {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000204 PyErr_SetString(PyExc_IndexError, "pop from an empty deque");
205 return NULL;
206 }
207 item = deque->rightblock->data[deque->rightindex];
208 deque->rightindex--;
Raymond Hettingerdf715ba2013-07-06 13:01:13 -1000209 Py_SIZE(deque)--;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000210 deque->state++;
Raymond Hettinger756b3f32004-01-29 06:37:52 +0000211
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000212 if (deque->rightindex == -1) {
Raymond Hettinger8dbbae22015-03-24 21:01:50 -0700213 if (Py_SIZE(deque)) {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000214 prevblock = deque->rightblock->leftlink;
215 assert(deque->leftblock != deque->rightblock);
216 freeblock(deque->rightblock);
Raymond Hettinger82df9252013-07-07 01:43:42 -1000217 CHECK_NOT_END(prevblock);
218 MARK_END(prevblock->rightlink);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000219 deque->rightblock = prevblock;
220 deque->rightindex = BLOCKLEN - 1;
Raymond Hettinger8dbbae22015-03-24 21:01:50 -0700221 } else {
222 assert(deque->leftblock == deque->rightblock);
223 assert(deque->leftindex == deque->rightindex+1);
224 /* re-center instead of freeing a block */
225 deque->leftindex = CENTER + 1;
226 deque->rightindex = CENTER;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000227 }
228 }
229 return item;
Raymond Hettinger756b3f32004-01-29 06:37:52 +0000230}
231
232PyDoc_STRVAR(pop_doc, "Remove and return the rightmost element.");
233
234static PyObject *
235deque_popleft(dequeobject *deque, PyObject *unused)
236{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000237 PyObject *item;
238 block *prevblock;
Raymond Hettinger756b3f32004-01-29 06:37:52 +0000239
Raymond Hettingerdf715ba2013-07-06 13:01:13 -1000240 if (Py_SIZE(deque) == 0) {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000241 PyErr_SetString(PyExc_IndexError, "pop from an empty deque");
242 return NULL;
243 }
244 assert(deque->leftblock != NULL);
245 item = deque->leftblock->data[deque->leftindex];
246 deque->leftindex++;
Raymond Hettingerdf715ba2013-07-06 13:01:13 -1000247 Py_SIZE(deque)--;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000248 deque->state++;
Raymond Hettinger756b3f32004-01-29 06:37:52 +0000249
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000250 if (deque->leftindex == BLOCKLEN) {
Raymond Hettinger8dbbae22015-03-24 21:01:50 -0700251 if (Py_SIZE(deque)) {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000252 assert(deque->leftblock != deque->rightblock);
253 prevblock = deque->leftblock->rightlink;
254 freeblock(deque->leftblock);
Raymond Hettinger82df9252013-07-07 01:43:42 -1000255 CHECK_NOT_END(prevblock);
256 MARK_END(prevblock->leftlink);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000257 deque->leftblock = prevblock;
258 deque->leftindex = 0;
Raymond Hettinger8dbbae22015-03-24 21:01:50 -0700259 } else {
260 assert(deque->leftblock == deque->rightblock);
261 assert(deque->leftindex == deque->rightindex+1);
262 /* re-center instead of freeing a block */
263 deque->leftindex = CENTER + 1;
264 deque->rightindex = CENTER;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000265 }
266 }
267 return item;
Raymond Hettinger756b3f32004-01-29 06:37:52 +0000268}
269
270PyDoc_STRVAR(popleft_doc, "Remove and return the leftmost element.");
271
Raymond Hettingerf30f5b92015-03-02 22:23:37 -0800272/* The deque's size limit is d.maxlen. The limit can be zero or positive.
273 * If there is no limit, then d.maxlen == -1.
274 *
275 * After an item is added to a deque, we check to see if the size has grown past
276 * the limit. If it has, we get the size back down to the limit by popping an
277 * item off of the opposite end. The methods that can trigger this are append(),
278 * appendleft(), extend(), and extendleft().
279 */
280
281static void
282deque_trim_right(dequeobject *deque)
283{
284 if (deque->maxlen != -1 && Py_SIZE(deque) > deque->maxlen) {
285 PyObject *rv = deque_pop(deque, NULL);
286 assert(rv != NULL);
287 assert(Py_SIZE(deque) <= deque->maxlen);
288 Py_DECREF(rv);
289 }
290}
291
292static void
293deque_trim_left(dequeobject *deque)
294{
295 if (deque->maxlen != -1 && Py_SIZE(deque) > deque->maxlen) {
296 PyObject *rv = deque_popleft(deque, NULL);
297 assert(rv != NULL);
298 assert(Py_SIZE(deque) <= deque->maxlen);
299 Py_DECREF(rv);
300 }
301}
302
Raymond Hettinger3ba85c22004-02-06 19:04:56 +0000303static PyObject *
Guido van Rossum8ce8a782007-11-01 19:42:39 +0000304deque_append(dequeobject *deque, PyObject *item)
305{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000306 deque->state++;
Raymond Hettinger8dbbae22015-03-24 21:01:50 -0700307 if (deque->rightindex == BLOCKLEN - 1) {
Raymond Hettinger82df9252013-07-07 01:43:42 -1000308 block *b = newblock(Py_SIZE(deque));
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000309 if (b == NULL)
310 return NULL;
Raymond Hettinger82df9252013-07-07 01:43:42 -1000311 b->leftlink = deque->rightblock;
312 CHECK_END(deque->rightblock->rightlink);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000313 deque->rightblock->rightlink = b;
314 deque->rightblock = b;
Raymond Hettinger82df9252013-07-07 01:43:42 -1000315 MARK_END(b->rightlink);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000316 deque->rightindex = -1;
317 }
318 Py_INCREF(item);
Raymond Hettingerdf715ba2013-07-06 13:01:13 -1000319 Py_SIZE(deque)++;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000320 deque->rightindex++;
321 deque->rightblock->data[deque->rightindex] = item;
Raymond Hettingerf30f5b92015-03-02 22:23:37 -0800322 deque_trim_left(deque);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000323 Py_RETURN_NONE;
Guido van Rossum8ce8a782007-11-01 19:42:39 +0000324}
325
326PyDoc_STRVAR(append_doc, "Add an element to the right side of the deque.");
327
328static PyObject *
329deque_appendleft(dequeobject *deque, PyObject *item)
330{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000331 deque->state++;
332 if (deque->leftindex == 0) {
Raymond Hettinger82df9252013-07-07 01:43:42 -1000333 block *b = newblock(Py_SIZE(deque));
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000334 if (b == NULL)
335 return NULL;
Raymond Hettinger82df9252013-07-07 01:43:42 -1000336 b->rightlink = deque->leftblock;
337 CHECK_END(deque->leftblock->leftlink);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000338 deque->leftblock->leftlink = b;
339 deque->leftblock = b;
Raymond Hettinger82df9252013-07-07 01:43:42 -1000340 MARK_END(b->leftlink);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000341 deque->leftindex = BLOCKLEN;
342 }
343 Py_INCREF(item);
Raymond Hettingerdf715ba2013-07-06 13:01:13 -1000344 Py_SIZE(deque)++;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000345 deque->leftindex--;
346 deque->leftblock->data[deque->leftindex] = item;
Raymond Hettingerf30f5b92015-03-02 22:23:37 -0800347 deque_trim_right(deque);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000348 Py_RETURN_NONE;
Guido van Rossum8ce8a782007-11-01 19:42:39 +0000349}
350
351PyDoc_STRVAR(appendleft_doc, "Add an element to the left side of the deque.");
352
Raymond Hettinger060c7f62009-03-10 09:36:07 +0000353
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000354/* Run an iterator to exhaustion. Shortcut for
Raymond Hettinger060c7f62009-03-10 09:36:07 +0000355 the extend/extendleft methods when maxlen == 0. */
356static PyObject*
357consume_iterator(PyObject *it)
358{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000359 PyObject *item;
Raymond Hettinger060c7f62009-03-10 09:36:07 +0000360
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000361 while ((item = PyIter_Next(it)) != NULL) {
362 Py_DECREF(item);
363 }
364 Py_DECREF(it);
365 if (PyErr_Occurred())
366 return NULL;
367 Py_RETURN_NONE;
Raymond Hettinger060c7f62009-03-10 09:36:07 +0000368}
369
Guido van Rossum8ce8a782007-11-01 19:42:39 +0000370static PyObject *
Raymond Hettinger3ba85c22004-02-06 19:04:56 +0000371deque_extend(dequeobject *deque, PyObject *iterable)
372{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000373 PyObject *it, *item;
Raymond Hettinger3ba85c22004-02-06 19:04:56 +0000374
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000375 /* Handle case where id(deque) == id(iterable) */
376 if ((PyObject *)deque == iterable) {
377 PyObject *result;
378 PyObject *s = PySequence_List(iterable);
379 if (s == NULL)
380 return NULL;
381 result = deque_extend(deque, s);
382 Py_DECREF(s);
383 return result;
384 }
Raymond Hettinger3f9afd82009-12-10 03:03:02 +0000385
Raymond Hettingerd9c116c2013-07-09 00:13:21 -0700386 /* Space saving heuristic. Start filling from the left */
387 if (Py_SIZE(deque) == 0) {
388 assert(deque->leftblock == deque->rightblock);
389 assert(deque->leftindex == deque->rightindex+1);
390 deque->leftindex = 1;
391 deque->rightindex = 0;
392 }
393
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000394 it = PyObject_GetIter(iterable);
395 if (it == NULL)
396 return NULL;
Raymond Hettinger3ba85c22004-02-06 19:04:56 +0000397
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000398 if (deque->maxlen == 0)
399 return consume_iterator(it);
Raymond Hettinger060c7f62009-03-10 09:36:07 +0000400
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000401 while ((item = PyIter_Next(it)) != NULL) {
402 deque->state++;
Raymond Hettinger8dbbae22015-03-24 21:01:50 -0700403 if (deque->rightindex == BLOCKLEN - 1) {
Raymond Hettinger82df9252013-07-07 01:43:42 -1000404 block *b = newblock(Py_SIZE(deque));
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000405 if (b == NULL) {
406 Py_DECREF(item);
407 Py_DECREF(it);
408 return NULL;
409 }
Raymond Hettinger82df9252013-07-07 01:43:42 -1000410 b->leftlink = deque->rightblock;
411 CHECK_END(deque->rightblock->rightlink);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000412 deque->rightblock->rightlink = b;
413 deque->rightblock = b;
Raymond Hettinger82df9252013-07-07 01:43:42 -1000414 MARK_END(b->rightlink);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000415 deque->rightindex = -1;
416 }
Raymond Hettingerdf715ba2013-07-06 13:01:13 -1000417 Py_SIZE(deque)++;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000418 deque->rightindex++;
419 deque->rightblock->data[deque->rightindex] = item;
Raymond Hettingerf30f5b92015-03-02 22:23:37 -0800420 deque_trim_left(deque);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000421 }
422 Py_DECREF(it);
423 if (PyErr_Occurred())
424 return NULL;
425 Py_RETURN_NONE;
Raymond Hettinger3ba85c22004-02-06 19:04:56 +0000426}
427
Tim Peters1065f752004-10-01 01:03:29 +0000428PyDoc_STRVAR(extend_doc,
Raymond Hettinger3ba85c22004-02-06 19:04:56 +0000429"Extend the right side of the deque with elements from the iterable");
430
431static PyObject *
432deque_extendleft(dequeobject *deque, PyObject *iterable)
433{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000434 PyObject *it, *item;
Raymond Hettinger3ba85c22004-02-06 19:04:56 +0000435
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000436 /* Handle case where id(deque) == id(iterable) */
437 if ((PyObject *)deque == iterable) {
438 PyObject *result;
439 PyObject *s = PySequence_List(iterable);
440 if (s == NULL)
441 return NULL;
442 result = deque_extendleft(deque, s);
443 Py_DECREF(s);
444 return result;
445 }
Raymond Hettinger3f9afd82009-12-10 03:03:02 +0000446
Raymond Hettingerd9c116c2013-07-09 00:13:21 -0700447 /* Space saving heuristic. Start filling from the right */
448 if (Py_SIZE(deque) == 0) {
449 assert(deque->leftblock == deque->rightblock);
450 assert(deque->leftindex == deque->rightindex+1);
451 deque->leftindex = BLOCKLEN - 1;
452 deque->rightindex = BLOCKLEN - 2;
453 }
454
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000455 it = PyObject_GetIter(iterable);
456 if (it == NULL)
457 return NULL;
Raymond Hettinger3ba85c22004-02-06 19:04:56 +0000458
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000459 if (deque->maxlen == 0)
460 return consume_iterator(it);
Raymond Hettinger060c7f62009-03-10 09:36:07 +0000461
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000462 while ((item = PyIter_Next(it)) != NULL) {
463 deque->state++;
464 if (deque->leftindex == 0) {
Raymond Hettinger82df9252013-07-07 01:43:42 -1000465 block *b = newblock(Py_SIZE(deque));
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000466 if (b == NULL) {
467 Py_DECREF(item);
468 Py_DECREF(it);
469 return NULL;
470 }
Raymond Hettinger82df9252013-07-07 01:43:42 -1000471 b->rightlink = deque->leftblock;
472 CHECK_END(deque->leftblock->leftlink);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000473 deque->leftblock->leftlink = b;
474 deque->leftblock = b;
Raymond Hettinger82df9252013-07-07 01:43:42 -1000475 MARK_END(b->leftlink);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000476 deque->leftindex = BLOCKLEN;
477 }
Raymond Hettingerdf715ba2013-07-06 13:01:13 -1000478 Py_SIZE(deque)++;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000479 deque->leftindex--;
480 deque->leftblock->data[deque->leftindex] = item;
Raymond Hettingerf30f5b92015-03-02 22:23:37 -0800481 deque_trim_right(deque);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000482 }
483 Py_DECREF(it);
484 if (PyErr_Occurred())
485 return NULL;
486 Py_RETURN_NONE;
Raymond Hettinger3ba85c22004-02-06 19:04:56 +0000487}
488
Tim Peters1065f752004-10-01 01:03:29 +0000489PyDoc_STRVAR(extendleft_doc,
Raymond Hettinger3ba85c22004-02-06 19:04:56 +0000490"Extend the left side of the deque with elements from the iterable");
491
Raymond Hettinger3f9afd82009-12-10 03:03:02 +0000492static PyObject *
493deque_inplace_concat(dequeobject *deque, PyObject *other)
494{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000495 PyObject *result;
Raymond Hettinger3f9afd82009-12-10 03:03:02 +0000496
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000497 result = deque_extend(deque, other);
498 if (result == NULL)
499 return result;
500 Py_DECREF(result);
501 Py_INCREF(deque);
502 return (PyObject *)deque;
Raymond Hettinger3f9afd82009-12-10 03:03:02 +0000503}
504
Raymond Hettinger41290a62015-03-31 08:12:23 -0700505static PyObject *deque_copy(PyObject *deque);
506
507static PyObject *
508deque_concat(dequeobject *deque, PyObject *other)
509{
510 PyObject *new_deque;
511 int rv;
512
513 rv = PyObject_IsInstance(other, (PyObject *)&deque_type);
514 if (rv <= 0) {
515 if (rv == 0) {
516 PyErr_Format(PyExc_TypeError,
517 "can only concatenate deque (not \"%.200s\") to deque",
518 other->ob_type->tp_name);
519 }
520 return NULL;
521 }
522
523 new_deque = deque_copy((PyObject *)deque);
524 if (new_deque == NULL)
525 return NULL;
526 return deque_inplace_concat((dequeobject *)new_deque, other);
527}
528
529static void deque_clear(dequeobject *deque);
530
531static PyObject *
532deque_repeat(dequeobject *deque, Py_ssize_t n)
533{
534 dequeobject *new_deque;
535 PyObject *result;
536
537 /* XXX add a special case for when maxlen is defined */
538 if (n < 0)
539 n = 0;
540 else if (n > 0 && Py_SIZE(deque) > MAX_DEQUE_LEN / n)
541 return PyErr_NoMemory();
542
543 new_deque = (dequeobject *)deque_new(&deque_type, (PyObject *)NULL, (PyObject *)NULL);
544 new_deque->maxlen = deque->maxlen;
545
546 for ( ; n ; n--) {
547 result = deque_extend(new_deque, (PyObject *)deque);
548 if (result == NULL) {
549 Py_DECREF(new_deque);
550 return NULL;
551 }
552 Py_DECREF(result);
553 }
554 return (PyObject *)new_deque;
555}
556
557static PyObject *
558deque_inplace_repeat(dequeobject *deque, Py_ssize_t n)
559{
560 Py_ssize_t i, size;
561 PyObject *seq;
562 PyObject *rv;
563
564 size = Py_SIZE(deque);
565 if (size == 0 || n == 1) {
566 Py_INCREF(deque);
567 return (PyObject *)deque;
568 }
569
570 if (n <= 0) {
571 deque_clear(deque);
572 Py_INCREF(deque);
573 return (PyObject *)deque;
574 }
575
576 if (size > MAX_DEQUE_LEN / n) {
577 return PyErr_NoMemory();
578 }
579
580 if (size == 1) {
581 /* common case, repeating a single element */
582 PyObject *item = deque->leftblock->data[deque->leftindex];
583
584 if (deque->maxlen != -1 && n > deque->maxlen)
585 n = deque->maxlen;
586
587 for (i = 0 ; i < n-1 ; i++) {
588 rv = deque_append(deque, item);
589 if (rv == NULL)
590 return NULL;
591 Py_DECREF(rv);
592 }
593 Py_INCREF(deque);
594 return (PyObject *)deque;
595 }
596
597 seq = PySequence_List((PyObject *)deque);
598 if (seq == NULL)
599 return seq;
600
601 for (i = 0 ; i < n-1 ; i++) {
602 rv = deque_extend(deque, seq);
603 if (rv == NULL) {
604 Py_DECREF(seq);
605 return NULL;
606 }
607 Py_DECREF(rv);
608 }
609 Py_INCREF(deque);
610 Py_DECREF(seq);
611 return (PyObject *)deque;
612}
613
Raymond Hettinger54023152014-04-23 00:58:48 -0700614/* The rotate() method is part of the public API and is used internally
615as a primitive for other methods.
616
617Rotation by 1 or -1 is a common case, so any optimizations for high
618volume rotations should take care not to penalize the common case.
619
620Conceptually, a rotate by one is equivalent to a pop on one side and an
621append on the other. However, a pop/append pair is unnecessarily slow
622because it requires a incref/decref pair for an object located randomly
623in memory. It is better to just move the object pointer from one block
624to the next without changing the reference count.
625
626When moving batches of pointers, it is tempting to use memcpy() but that
627proved to be slower than a simple loop for a variety of reasons.
628Memcpy() cannot know in advance that we're copying pointers instead of
629bytes, that the source and destination are pointer aligned and
630non-overlapping, that moving just one pointer is a common case, that we
631never need to move more than BLOCKLEN pointers, and that at least one
632pointer is always moved.
633
634For high volume rotations, newblock() and freeblock() are never called
635more than once. Previously emptied blocks are immediately reused as a
636destination block. If a block is left-over at the end, it is freed.
637*/
638
Raymond Hettingerdcb9d942004-10-09 16:02:18 +0000639static int
Martin v. Löwis18e16552006-02-15 17:27:45 +0000640_deque_rotate(dequeobject *deque, Py_ssize_t n)
Raymond Hettinger5c5eb862004-02-07 21:13:00 +0000641{
Raymond Hettinger3959af92013-07-13 02:34:08 -0700642 block *b = NULL;
Raymond Hettinger20b0f872013-06-23 15:44:33 -0700643 block *leftblock = deque->leftblock;
644 block *rightblock = deque->rightblock;
645 Py_ssize_t leftindex = deque->leftindex;
646 Py_ssize_t rightindex = deque->rightindex;
Raymond Hettingerdf715ba2013-07-06 13:01:13 -1000647 Py_ssize_t len=Py_SIZE(deque), halflen=len>>1;
Raymond Hettinger3959af92013-07-13 02:34:08 -0700648 int rv = -1;
Raymond Hettinger5c5eb862004-02-07 21:13:00 +0000649
Raymond Hettinger464d89b2013-01-11 22:29:50 -0800650 if (len <= 1)
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000651 return 0;
652 if (n > halflen || n < -halflen) {
653 n %= len;
654 if (n > halflen)
655 n -= len;
656 else if (n < -halflen)
657 n += len;
658 }
Raymond Hettinger1f0044c2013-02-05 01:30:46 -0500659 assert(len > 1);
Raymond Hettingera4409c12013-02-04 00:08:12 -0500660 assert(-halflen <= n && n <= halflen);
Raymond Hettinger231ee4d2013-02-02 11:24:43 -0800661
Raymond Hettinger464d89b2013-01-11 22:29:50 -0800662 deque->state++;
Raymond Hettinger1f0044c2013-02-05 01:30:46 -0500663 while (n > 0) {
Raymond Hettinger20b0f872013-06-23 15:44:33 -0700664 if (leftindex == 0) {
Raymond Hettinger20b0f872013-06-23 15:44:33 -0700665 if (b == NULL) {
Raymond Hettinger3959af92013-07-13 02:34:08 -0700666 b = newblock(len);
667 if (b == NULL)
668 goto done;
Raymond Hettinger20b0f872013-06-23 15:44:33 -0700669 }
Raymond Hettinger82df9252013-07-07 01:43:42 -1000670 b->rightlink = leftblock;
671 CHECK_END(leftblock->leftlink);
Raymond Hettinger20b0f872013-06-23 15:44:33 -0700672 leftblock->leftlink = b;
673 leftblock = b;
Raymond Hettinger82df9252013-07-07 01:43:42 -1000674 MARK_END(b->leftlink);
Raymond Hettinger20b0f872013-06-23 15:44:33 -0700675 leftindex = BLOCKLEN;
Raymond Hettinger3959af92013-07-13 02:34:08 -0700676 b = NULL;
Raymond Hettinger464d89b2013-01-11 22:29:50 -0800677 }
Raymond Hettinger20b0f872013-06-23 15:44:33 -0700678 assert(leftindex > 0);
Raymond Hettinger20b0f872013-06-23 15:44:33 -0700679 {
680 PyObject **src, **dest;
681 Py_ssize_t m = n;
Raymond Hettinger21777ac2013-02-02 09:56:08 -0800682
Raymond Hettinger20b0f872013-06-23 15:44:33 -0700683 if (m > rightindex + 1)
684 m = rightindex + 1;
685 if (m > leftindex)
686 m = leftindex;
687 assert (m > 0 && m <= len);
Raymond Hettinger20b0f872013-06-23 15:44:33 -0700688 rightindex -= m;
689 leftindex -= m;
Raymond Hettinger0e259f12015-02-01 22:53:41 -0800690 src = &rightblock->data[rightindex + 1];
691 dest = &leftblock->data[leftindex];
Raymond Hettinger20b0f872013-06-23 15:44:33 -0700692 n -= m;
Raymond Hettinger840533b2013-07-13 17:03:58 -0700693 do {
Raymond Hettinger0e259f12015-02-01 22:53:41 -0800694 *(dest++) = *(src++);
Raymond Hettinger840533b2013-07-13 17:03:58 -0700695 } while (--m);
Raymond Hettinger20b0f872013-06-23 15:44:33 -0700696 }
Raymond Hettinger20b0f872013-06-23 15:44:33 -0700697 if (rightindex == -1) {
Raymond Hettinger20b0f872013-06-23 15:44:33 -0700698 assert(leftblock != rightblock);
Raymond Hettinger840533b2013-07-13 17:03:58 -0700699 assert(b == NULL);
Raymond Hettinger3959af92013-07-13 02:34:08 -0700700 b = rightblock;
Raymond Hettingerb97cc492013-07-21 01:51:07 -0700701 CHECK_NOT_END(rightblock->leftlink);
702 rightblock = rightblock->leftlink;
703 MARK_END(rightblock->rightlink);
Raymond Hettinger20b0f872013-06-23 15:44:33 -0700704 rightindex = BLOCKLEN - 1;
Raymond Hettinger464d89b2013-01-11 22:29:50 -0800705 }
Raymond Hettinger21777ac2013-02-02 09:56:08 -0800706 }
Raymond Hettinger1f0044c2013-02-05 01:30:46 -0500707 while (n < 0) {
Raymond Hettinger20b0f872013-06-23 15:44:33 -0700708 if (rightindex == BLOCKLEN - 1) {
Raymond Hettinger20b0f872013-06-23 15:44:33 -0700709 if (b == NULL) {
Raymond Hettinger3959af92013-07-13 02:34:08 -0700710 b = newblock(len);
711 if (b == NULL)
712 goto done;
Raymond Hettinger20b0f872013-06-23 15:44:33 -0700713 }
Raymond Hettinger82df9252013-07-07 01:43:42 -1000714 b->leftlink = rightblock;
715 CHECK_END(rightblock->rightlink);
Raymond Hettinger20b0f872013-06-23 15:44:33 -0700716 rightblock->rightlink = b;
717 rightblock = b;
Raymond Hettinger82df9252013-07-07 01:43:42 -1000718 MARK_END(b->rightlink);
Raymond Hettinger20b0f872013-06-23 15:44:33 -0700719 rightindex = -1;
Raymond Hettinger3959af92013-07-13 02:34:08 -0700720 b = NULL;
Raymond Hettinger464d89b2013-01-11 22:29:50 -0800721 }
Raymond Hettinger20b0f872013-06-23 15:44:33 -0700722 assert (rightindex < BLOCKLEN - 1);
Raymond Hettinger20b0f872013-06-23 15:44:33 -0700723 {
724 PyObject **src, **dest;
725 Py_ssize_t m = -n;
Raymond Hettinger21777ac2013-02-02 09:56:08 -0800726
Raymond Hettinger20b0f872013-06-23 15:44:33 -0700727 if (m > BLOCKLEN - leftindex)
728 m = BLOCKLEN - leftindex;
729 if (m > BLOCKLEN - 1 - rightindex)
730 m = BLOCKLEN - 1 - rightindex;
731 assert (m > 0 && m <= len);
732 src = &leftblock->data[leftindex];
733 dest = &rightblock->data[rightindex + 1];
734 leftindex += m;
735 rightindex += m;
736 n += m;
Raymond Hettinger840533b2013-07-13 17:03:58 -0700737 do {
Raymond Hettinger20b0f872013-06-23 15:44:33 -0700738 *(dest++) = *(src++);
Raymond Hettinger840533b2013-07-13 17:03:58 -0700739 } while (--m);
Raymond Hettinger20b0f872013-06-23 15:44:33 -0700740 }
Raymond Hettinger20b0f872013-06-23 15:44:33 -0700741 if (leftindex == BLOCKLEN) {
Raymond Hettinger20b0f872013-06-23 15:44:33 -0700742 assert(leftblock != rightblock);
Raymond Hettinger840533b2013-07-13 17:03:58 -0700743 assert(b == NULL);
Raymond Hettinger3959af92013-07-13 02:34:08 -0700744 b = leftblock;
Raymond Hettingerb97cc492013-07-21 01:51:07 -0700745 CHECK_NOT_END(leftblock->rightlink);
746 leftblock = leftblock->rightlink;
747 MARK_END(leftblock->leftlink);
Raymond Hettinger20b0f872013-06-23 15:44:33 -0700748 leftindex = 0;
Raymond Hettinger21777ac2013-02-02 09:56:08 -0800749 }
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000750 }
Raymond Hettinger3959af92013-07-13 02:34:08 -0700751 rv = 0;
Raymond Hettinger20b0f872013-06-23 15:44:33 -0700752done:
Raymond Hettinger3959af92013-07-13 02:34:08 -0700753 if (b != NULL)
754 freeblock(b);
Raymond Hettinger20b0f872013-06-23 15:44:33 -0700755 deque->leftblock = leftblock;
756 deque->rightblock = rightblock;
757 deque->leftindex = leftindex;
758 deque->rightindex = rightindex;
759
760 return rv;
Raymond Hettingerdcb9d942004-10-09 16:02:18 +0000761}
762
763static PyObject *
764deque_rotate(dequeobject *deque, PyObject *args)
765{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000766 Py_ssize_t n=1;
Raymond Hettingerdcb9d942004-10-09 16:02:18 +0000767
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000768 if (!PyArg_ParseTuple(args, "|n:rotate", &n))
769 return NULL;
Raymond Hettinger6921c132015-03-21 02:03:40 -0700770 if (!_deque_rotate(deque, n))
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000771 Py_RETURN_NONE;
772 return NULL;
Raymond Hettinger5c5eb862004-02-07 21:13:00 +0000773}
774
Tim Peters1065f752004-10-01 01:03:29 +0000775PyDoc_STRVAR(rotate_doc,
Raymond Hettingeree33b272004-02-08 04:05:26 +0000776"Rotate the deque n steps to the right (default n=1). If n is negative, rotates left.");
Raymond Hettinger5c5eb862004-02-07 21:13:00 +0000777
Raymond Hettingere5fdedb2009-12-10 00:47:21 +0000778static PyObject *
779deque_reverse(dequeobject *deque, PyObject *unused)
780{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000781 block *leftblock = deque->leftblock;
782 block *rightblock = deque->rightblock;
783 Py_ssize_t leftindex = deque->leftindex;
784 Py_ssize_t rightindex = deque->rightindex;
Raymond Hettinger8dbbae22015-03-24 21:01:50 -0700785 Py_ssize_t n = Py_SIZE(deque) / 2;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000786 Py_ssize_t i;
787 PyObject *tmp;
Raymond Hettingere5fdedb2009-12-10 00:47:21 +0000788
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000789 for (i=0 ; i<n ; i++) {
790 /* Validate that pointers haven't met in the middle */
791 assert(leftblock != rightblock || leftindex < rightindex);
Raymond Hettinger82df9252013-07-07 01:43:42 -1000792 CHECK_NOT_END(leftblock);
793 CHECK_NOT_END(rightblock);
Raymond Hettingere5fdedb2009-12-10 00:47:21 +0000794
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000795 /* Swap */
796 tmp = leftblock->data[leftindex];
797 leftblock->data[leftindex] = rightblock->data[rightindex];
798 rightblock->data[rightindex] = tmp;
Raymond Hettingere5fdedb2009-12-10 00:47:21 +0000799
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000800 /* Advance left block/index pair */
801 leftindex++;
802 if (leftindex == BLOCKLEN) {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000803 leftblock = leftblock->rightlink;
804 leftindex = 0;
805 }
Raymond Hettingere5fdedb2009-12-10 00:47:21 +0000806
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000807 /* Step backwards with the right block/index pair */
808 rightindex--;
809 if (rightindex == -1) {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000810 rightblock = rightblock->leftlink;
811 rightindex = BLOCKLEN - 1;
812 }
813 }
814 Py_RETURN_NONE;
Raymond Hettingere5fdedb2009-12-10 00:47:21 +0000815}
816
817PyDoc_STRVAR(reverse_doc,
818"D.reverse() -- reverse *IN PLACE*");
819
Raymond Hettinger44459de2010-04-03 23:20:46 +0000820static PyObject *
821deque_count(dequeobject *deque, PyObject *v)
822{
Raymond Hettingerf3a67b72013-07-06 17:49:06 -1000823 block *b = deque->leftblock;
824 Py_ssize_t index = deque->leftindex;
Raymond Hettingerdf715ba2013-07-06 13:01:13 -1000825 Py_ssize_t n = Py_SIZE(deque);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000826 Py_ssize_t i;
827 Py_ssize_t count = 0;
Raymond Hettingerf9d9c792015-03-02 22:47:46 -0800828 size_t start_state = deque->state;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000829 PyObject *item;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000830 int cmp;
Raymond Hettinger44459de2010-04-03 23:20:46 +0000831
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000832 for (i=0 ; i<n ; i++) {
Raymond Hettinger82df9252013-07-07 01:43:42 -1000833 CHECK_NOT_END(b);
Raymond Hettingerf3a67b72013-07-06 17:49:06 -1000834 item = b->data[index];
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000835 cmp = PyObject_RichCompareBool(item, v, Py_EQ);
836 if (cmp > 0)
837 count++;
838 else if (cmp < 0)
839 return NULL;
Raymond Hettinger44459de2010-04-03 23:20:46 +0000840
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000841 if (start_state != deque->state) {
842 PyErr_SetString(PyExc_RuntimeError,
843 "deque mutated during iteration");
844 return NULL;
845 }
Raymond Hettinger44459de2010-04-03 23:20:46 +0000846
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000847 /* Advance left block/index pair */
Raymond Hettingerf3a67b72013-07-06 17:49:06 -1000848 index++;
849 if (index == BLOCKLEN) {
850 b = b->rightlink;
851 index = 0;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000852 }
853 }
854 return PyLong_FromSsize_t(count);
Raymond Hettinger44459de2010-04-03 23:20:46 +0000855}
856
857PyDoc_STRVAR(count_doc,
858"D.count(value) -> integer -- return number of occurrences of value");
859
Raymond Hettinger39dadf72015-03-20 16:38:56 -0700860static int
861deque_contains(dequeobject *deque, PyObject *v)
862{
863 block *b = deque->leftblock;
864 Py_ssize_t index = deque->leftindex;
865 Py_ssize_t n = Py_SIZE(deque);
866 Py_ssize_t i;
867 size_t start_state = deque->state;
868 PyObject *item;
869 int cmp;
870
871 for (i=0 ; i<n ; i++) {
872 CHECK_NOT_END(b);
873 item = b->data[index];
874 cmp = PyObject_RichCompareBool(item, v, Py_EQ);
875 if (cmp) {
876 return cmp;
877 }
878 if (start_state != deque->state) {
879 PyErr_SetString(PyExc_RuntimeError,
880 "deque mutated during iteration");
881 return -1;
882 }
883 index++;
884 if (index == BLOCKLEN) {
885 b = b->rightlink;
886 index = 0;
887 }
888 }
889 return 0;
890}
891
Martin v. Löwis18e16552006-02-15 17:27:45 +0000892static Py_ssize_t
Raymond Hettinger756b3f32004-01-29 06:37:52 +0000893deque_len(dequeobject *deque)
894{
Raymond Hettingerdf715ba2013-07-06 13:01:13 -1000895 return Py_SIZE(deque);
Raymond Hettinger756b3f32004-01-29 06:37:52 +0000896}
897
Raymond Hettinger4aec61e2005-03-18 21:20:23 +0000898static PyObject *
Raymond Hettinger32ea1652015-03-21 01:37:37 -0700899deque_index(dequeobject *deque, PyObject *args)
900{
901 Py_ssize_t i, start=0, stop=Py_SIZE(deque);
902 PyObject *v, *item;
903 block *b = deque->leftblock;
904 Py_ssize_t index = deque->leftindex;
905 size_t start_state = deque->state;
906
907 if (!PyArg_ParseTuple(args, "O|O&O&:index", &v,
908 _PyEval_SliceIndex, &start,
909 _PyEval_SliceIndex, &stop))
910 return NULL;
911 if (start < 0) {
912 start += Py_SIZE(deque);
913 if (start < 0)
914 start = 0;
915 }
916 if (stop < 0) {
917 stop += Py_SIZE(deque);
918 if (stop < 0)
919 stop = 0;
920 }
921
922 for (i=0 ; i<stop ; i++) {
923 if (i >= start) {
924 int cmp;
925 CHECK_NOT_END(b);
926 item = b->data[index];
927 cmp = PyObject_RichCompareBool(item, v, Py_EQ);
928 if (cmp > 0)
929 return PyLong_FromSsize_t(i);
930 else if (cmp < 0)
931 return NULL;
932 if (start_state != deque->state) {
933 PyErr_SetString(PyExc_RuntimeError,
934 "deque mutated during iteration");
935 return NULL;
936 }
937 }
938 index++;
939 if (index == BLOCKLEN) {
940 b = b->rightlink;
941 index = 0;
942 }
943 }
944 PyErr_Format(PyExc_ValueError, "%R is not in deque", v);
945 return NULL;
946}
947
948PyDoc_STRVAR(index_doc,
949"D.index(value, [start, [stop]]) -> integer -- return first index of value.\n"
950"Raises ValueError if the value is not present.");
951
Raymond Hettinger551350a2015-03-24 00:19:53 -0700952/* insert(), remove(), and delitem() are implemented in terms of
953 rotate() for simplicity and reasonable performance near the end
954 points. If for some reason these methods become popular, it is not
955 hard to re-implement this using direct data movement (similar to
956 the code used in list slice assignments) and achieve a performance
Raymond Hettingerfef9c1b2015-03-24 21:12:57 -0700957 boost (by moving each pointer only once instead of twice).
Raymond Hettinger551350a2015-03-24 00:19:53 -0700958*/
959
Raymond Hettinger32ea1652015-03-21 01:37:37 -0700960static PyObject *
961deque_insert(dequeobject *deque, PyObject *args)
962{
963 Py_ssize_t index;
964 Py_ssize_t n = Py_SIZE(deque);
965 PyObject *value;
966 PyObject *rv;
967
968 if (!PyArg_ParseTuple(args, "nO:insert", &index, &value))
969 return NULL;
970 if (index >= n)
971 return deque_append(deque, value);
972 if (index <= -n || index == 0)
973 return deque_appendleft(deque, value);
974 if (_deque_rotate(deque, -index))
975 return NULL;
976 if (index < 0)
977 rv = deque_append(deque, value);
978 else
979 rv = deque_appendleft(deque, value);
980 if (rv == NULL)
981 return NULL;
982 Py_DECREF(rv);
983 if (_deque_rotate(deque, index))
984 return NULL;
985 Py_RETURN_NONE;
986}
987
988PyDoc_STRVAR(insert_doc,
989"D.insert(index, object) -- insert object before index");
990
991static PyObject *
Raymond Hettinger4aec61e2005-03-18 21:20:23 +0000992deque_remove(dequeobject *deque, PyObject *value)
993{
Raymond Hettingerdf715ba2013-07-06 13:01:13 -1000994 Py_ssize_t i, n=Py_SIZE(deque);
Raymond Hettinger4aec61e2005-03-18 21:20:23 +0000995
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000996 for (i=0 ; i<n ; i++) {
997 PyObject *item = deque->leftblock->data[deque->leftindex];
998 int cmp = PyObject_RichCompareBool(item, value, Py_EQ);
Raymond Hettingerd73202c2005-03-19 00:00:51 +0000999
Raymond Hettingerdf715ba2013-07-06 13:01:13 -10001000 if (Py_SIZE(deque) != n) {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001001 PyErr_SetString(PyExc_IndexError,
1002 "deque mutated during remove().");
1003 return NULL;
1004 }
1005 if (cmp > 0) {
1006 PyObject *tgt = deque_popleft(deque, NULL);
1007 assert (tgt != NULL);
Raymond Hettinger6921c132015-03-21 02:03:40 -07001008 if (_deque_rotate(deque, i))
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001009 return NULL;
Raymond Hettingerac13ad62015-03-21 01:53:16 -07001010 Py_DECREF(tgt);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001011 Py_RETURN_NONE;
1012 }
1013 else if (cmp < 0) {
1014 _deque_rotate(deque, i);
1015 return NULL;
1016 }
1017 _deque_rotate(deque, -1);
1018 }
1019 PyErr_SetString(PyExc_ValueError, "deque.remove(x): x not in deque");
1020 return NULL;
Raymond Hettinger4aec61e2005-03-18 21:20:23 +00001021}
1022
1023PyDoc_STRVAR(remove_doc,
1024"D.remove(value) -- remove first occurrence of value.");
1025
Benjamin Peterson0e5c48a2013-01-12 21:22:18 -05001026static void
Raymond Hettinger756b3f32004-01-29 06:37:52 +00001027deque_clear(dequeobject *deque)
1028{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001029 PyObject *item;
Raymond Hettinger756b3f32004-01-29 06:37:52 +00001030
Raymond Hettingerdf715ba2013-07-06 13:01:13 -10001031 while (Py_SIZE(deque)) {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001032 item = deque_pop(deque, NULL);
1033 assert (item != NULL);
1034 Py_DECREF(item);
1035 }
Raymond Hettinger87e69122015-03-02 23:32:02 -08001036 assert(deque->leftblock == deque->rightblock);
1037 assert(deque->leftindex - 1 == deque->rightindex);
1038 assert(Py_SIZE(deque) == 0);
Raymond Hettinger756b3f32004-01-29 06:37:52 +00001039}
1040
Raymond Hettinger3c186ba2015-03-02 21:45:02 -08001041static int
1042valid_index(Py_ssize_t i, Py_ssize_t limit)
1043{
1044 /* The cast to size_t let us use just a single comparison
1045 to check whether i is in the range: 0 <= i < limit */
1046 return (size_t) i < (size_t) limit;
1047}
1048
Raymond Hettinger756b3f32004-01-29 06:37:52 +00001049static PyObject *
Benjamin Petersond6313712008-07-31 16:23:04 +00001050deque_item(dequeobject *deque, Py_ssize_t i)
Raymond Hettinger0a4977c2004-03-01 23:16:22 +00001051{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001052 block *b;
1053 PyObject *item;
1054 Py_ssize_t n, index=i;
Raymond Hettinger0a4977c2004-03-01 23:16:22 +00001055
Raymond Hettinger3c186ba2015-03-02 21:45:02 -08001056 if (!valid_index(i, Py_SIZE(deque))) {
1057 PyErr_SetString(PyExc_IndexError, "deque index out of range");
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001058 return NULL;
1059 }
Raymond Hettinger0a4977c2004-03-01 23:16:22 +00001060
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001061 if (i == 0) {
1062 i = deque->leftindex;
1063 b = deque->leftblock;
Raymond Hettingerdf715ba2013-07-06 13:01:13 -10001064 } else if (i == Py_SIZE(deque) - 1) {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001065 i = deque->rightindex;
1066 b = deque->rightblock;
1067 } else {
1068 i += deque->leftindex;
Raymond Hettingerc2083082015-02-28 23:29:16 -08001069 n = (Py_ssize_t)((size_t) i / BLOCKLEN);
1070 i = (Py_ssize_t)((size_t) i % BLOCKLEN);
Raymond Hettingerdf715ba2013-07-06 13:01:13 -10001071 if (index < (Py_SIZE(deque) >> 1)) {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001072 b = deque->leftblock;
1073 while (n--)
1074 b = b->rightlink;
1075 } else {
Raymond Hettinger63d1ff22015-02-28 07:41:30 -08001076 n = (Py_ssize_t)(
Raymond Hettingerc2083082015-02-28 23:29:16 -08001077 ((size_t)(deque->leftindex + Py_SIZE(deque) - 1))
Raymond Hettinger63d1ff22015-02-28 07:41:30 -08001078 / BLOCKLEN - n);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001079 b = deque->rightblock;
1080 while (n--)
1081 b = b->leftlink;
1082 }
1083 }
1084 item = b->data[i];
1085 Py_INCREF(item);
1086 return item;
Raymond Hettinger0a4977c2004-03-01 23:16:22 +00001087}
1088
1089static int
Martin v. Löwis18e16552006-02-15 17:27:45 +00001090deque_del_item(dequeobject *deque, Py_ssize_t i)
Raymond Hettinger0e371f22004-05-12 20:55:56 +00001091{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001092 PyObject *item;
Raymond Hettingerac13ad62015-03-21 01:53:16 -07001093 int rv;
Raymond Hettinger0e371f22004-05-12 20:55:56 +00001094
Raymond Hettingerdf715ba2013-07-06 13:01:13 -10001095 assert (i >= 0 && i < Py_SIZE(deque));
Raymond Hettinger6921c132015-03-21 02:03:40 -07001096 if (_deque_rotate(deque, -i))
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001097 return -1;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001098 item = deque_popleft(deque, NULL);
Raymond Hettingerac13ad62015-03-21 01:53:16 -07001099 rv = _deque_rotate(deque, i);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001100 assert (item != NULL);
1101 Py_DECREF(item);
Raymond Hettingerac13ad62015-03-21 01:53:16 -07001102 return rv;
Raymond Hettinger0e371f22004-05-12 20:55:56 +00001103}
1104
1105static int
Martin v. Löwis18e16552006-02-15 17:27:45 +00001106deque_ass_item(dequeobject *deque, Py_ssize_t i, PyObject *v)
Raymond Hettinger0a4977c2004-03-01 23:16:22 +00001107{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001108 PyObject *old_value;
1109 block *b;
Raymond Hettingerdf715ba2013-07-06 13:01:13 -10001110 Py_ssize_t n, len=Py_SIZE(deque), halflen=(len+1)>>1, index=i;
Raymond Hettinger0a4977c2004-03-01 23:16:22 +00001111
Raymond Hettinger3c186ba2015-03-02 21:45:02 -08001112 if (!valid_index(i, len)) {
1113 PyErr_SetString(PyExc_IndexError, "deque index out of range");
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001114 return -1;
1115 }
1116 if (v == NULL)
1117 return deque_del_item(deque, i);
Raymond Hettinger0e371f22004-05-12 20:55:56 +00001118
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001119 i += deque->leftindex;
Raymond Hettingerc2083082015-02-28 23:29:16 -08001120 n = (Py_ssize_t)((size_t) i / BLOCKLEN);
1121 i = (Py_ssize_t)((size_t) i % BLOCKLEN);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001122 if (index <= halflen) {
1123 b = deque->leftblock;
1124 while (n--)
1125 b = b->rightlink;
1126 } else {
Raymond Hettingera473b9d2015-02-28 17:49:47 -08001127 n = (Py_ssize_t)(
Raymond Hettingerc2083082015-02-28 23:29:16 -08001128 ((size_t)(deque->leftindex + Py_SIZE(deque) - 1))
Raymond Hettingera473b9d2015-02-28 17:49:47 -08001129 / BLOCKLEN - n);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001130 b = deque->rightblock;
1131 while (n--)
1132 b = b->leftlink;
1133 }
1134 Py_INCREF(v);
1135 old_value = b->data[i];
1136 b->data[i] = v;
1137 Py_DECREF(old_value);
1138 return 0;
Raymond Hettinger0a4977c2004-03-01 23:16:22 +00001139}
1140
1141static PyObject *
Raymond Hettinger756b3f32004-01-29 06:37:52 +00001142deque_clearmethod(dequeobject *deque)
1143{
Benjamin Peterson0e5c48a2013-01-12 21:22:18 -05001144 deque_clear(deque);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001145 Py_RETURN_NONE;
Raymond Hettinger756b3f32004-01-29 06:37:52 +00001146}
1147
1148PyDoc_STRVAR(clear_doc, "Remove all elements from the deque.");
1149
1150static void
1151deque_dealloc(dequeobject *deque)
1152{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001153 PyObject_GC_UnTrack(deque);
1154 if (deque->weakreflist != NULL)
1155 PyObject_ClearWeakRefs((PyObject *) deque);
1156 if (deque->leftblock != NULL) {
1157 deque_clear(deque);
1158 assert(deque->leftblock != NULL);
1159 freeblock(deque->leftblock);
1160 }
1161 deque->leftblock = NULL;
1162 deque->rightblock = NULL;
1163 Py_TYPE(deque)->tp_free(deque);
Raymond Hettinger756b3f32004-01-29 06:37:52 +00001164}
1165
1166static int
Raymond Hettinger0a4977c2004-03-01 23:16:22 +00001167deque_traverse(dequeobject *deque, visitproc visit, void *arg)
Raymond Hettinger756b3f32004-01-29 06:37:52 +00001168{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001169 block *b;
1170 PyObject *item;
1171 Py_ssize_t index;
1172 Py_ssize_t indexlo = deque->leftindex;
Raymond Hettinger756b3f32004-01-29 06:37:52 +00001173
Raymond Hettinger5bfa8672013-07-06 11:58:09 -10001174 for (b = deque->leftblock; b != deque->rightblock; b = b->rightlink) {
1175 for (index = indexlo; index < BLOCKLEN ; index++) {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001176 item = b->data[index];
1177 Py_VISIT(item);
1178 }
1179 indexlo = 0;
1180 }
Raymond Hettinger5bfa8672013-07-06 11:58:09 -10001181 for (index = indexlo; index <= deque->rightindex; index++) {
1182 item = b->data[index];
1183 Py_VISIT(item);
1184 }
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001185 return 0;
Raymond Hettinger756b3f32004-01-29 06:37:52 +00001186}
1187
Raymond Hettinger756b3f32004-01-29 06:37:52 +00001188static PyObject *
1189deque_copy(PyObject *deque)
1190{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001191 if (((dequeobject *)deque)->maxlen == -1)
1192 return PyObject_CallFunction((PyObject *)(Py_TYPE(deque)), "O", deque, NULL);
1193 else
1194 return PyObject_CallFunction((PyObject *)(Py_TYPE(deque)), "Oi",
1195 deque, ((dequeobject *)deque)->maxlen, NULL);
Raymond Hettinger756b3f32004-01-29 06:37:52 +00001196}
1197
1198PyDoc_STRVAR(copy_doc, "Return a shallow copy of a deque.");
1199
1200static PyObject *
1201deque_reduce(dequeobject *deque)
1202{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001203 PyObject *dict, *result, *aslist;
Martin v. Löwisbd928fe2011-10-14 10:20:37 +02001204 _Py_IDENTIFIER(__dict__);
Raymond Hettinger756b3f32004-01-29 06:37:52 +00001205
Martin v. Löwis1ee1b6f2011-10-10 18:11:30 +02001206 dict = _PyObject_GetAttrId((PyObject *)deque, &PyId___dict__);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001207 if (dict == NULL)
1208 PyErr_Clear();
1209 aslist = PySequence_List((PyObject *)deque);
1210 if (aslist == NULL) {
1211 Py_XDECREF(dict);
1212 return NULL;
1213 }
1214 if (dict == NULL) {
1215 if (deque->maxlen == -1)
1216 result = Py_BuildValue("O(O)", Py_TYPE(deque), aslist);
1217 else
1218 result = Py_BuildValue("O(On)", Py_TYPE(deque), aslist, deque->maxlen);
1219 } else {
1220 if (deque->maxlen == -1)
1221 result = Py_BuildValue("O(OO)O", Py_TYPE(deque), aslist, Py_None, dict);
1222 else
1223 result = Py_BuildValue("O(On)O", Py_TYPE(deque), aslist, deque->maxlen, dict);
1224 }
1225 Py_XDECREF(dict);
1226 Py_DECREF(aslist);
1227 return result;
Raymond Hettinger756b3f32004-01-29 06:37:52 +00001228}
1229
1230PyDoc_STRVAR(reduce_doc, "Return state information for pickling.");
1231
1232static PyObject *
1233deque_repr(PyObject *deque)
1234{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001235 PyObject *aslist, *result;
1236 int i;
Raymond Hettinger756b3f32004-01-29 06:37:52 +00001237
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001238 i = Py_ReprEnter(deque);
1239 if (i != 0) {
1240 if (i < 0)
1241 return NULL;
1242 return PyUnicode_FromString("[...]");
1243 }
Raymond Hettinger756b3f32004-01-29 06:37:52 +00001244
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001245 aslist = PySequence_List(deque);
1246 if (aslist == NULL) {
1247 Py_ReprLeave(deque);
1248 return NULL;
1249 }
1250 if (((dequeobject *)deque)->maxlen != -1)
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001251 result = PyUnicode_FromFormat("deque(%R, maxlen=%zd)",
1252 aslist, ((dequeobject *)deque)->maxlen);
1253 else
1254 result = PyUnicode_FromFormat("deque(%R)", aslist);
1255 Py_DECREF(aslist);
1256 Py_ReprLeave(deque);
1257 return result;
Raymond Hettinger756b3f32004-01-29 06:37:52 +00001258}
1259
Raymond Hettinger738ec902004-02-29 02:15:56 +00001260static PyObject *
1261deque_richcompare(PyObject *v, PyObject *w, int op)
1262{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001263 PyObject *it1=NULL, *it2=NULL, *x, *y;
1264 Py_ssize_t vs, ws;
1265 int b, cmp=-1;
Raymond Hettinger738ec902004-02-29 02:15:56 +00001266
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001267 if (!PyObject_TypeCheck(v, &deque_type) ||
1268 !PyObject_TypeCheck(w, &deque_type)) {
Brian Curtindfc80e32011-08-10 20:28:54 -05001269 Py_RETURN_NOTIMPLEMENTED;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001270 }
Raymond Hettinger738ec902004-02-29 02:15:56 +00001271
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001272 /* Shortcuts */
Raymond Hettingerdf715ba2013-07-06 13:01:13 -10001273 vs = Py_SIZE((dequeobject *)v);
1274 ws = Py_SIZE((dequeobject *)w);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001275 if (op == Py_EQ) {
1276 if (v == w)
1277 Py_RETURN_TRUE;
1278 if (vs != ws)
1279 Py_RETURN_FALSE;
1280 }
1281 if (op == Py_NE) {
1282 if (v == w)
1283 Py_RETURN_FALSE;
1284 if (vs != ws)
1285 Py_RETURN_TRUE;
1286 }
Raymond Hettinger738ec902004-02-29 02:15:56 +00001287
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001288 /* Search for the first index where items are different */
1289 it1 = PyObject_GetIter(v);
1290 if (it1 == NULL)
1291 goto done;
1292 it2 = PyObject_GetIter(w);
1293 if (it2 == NULL)
1294 goto done;
1295 for (;;) {
1296 x = PyIter_Next(it1);
1297 if (x == NULL && PyErr_Occurred())
1298 goto done;
1299 y = PyIter_Next(it2);
1300 if (x == NULL || y == NULL)
1301 break;
1302 b = PyObject_RichCompareBool(x, y, Py_EQ);
1303 if (b == 0) {
1304 cmp = PyObject_RichCompareBool(x, y, op);
1305 Py_DECREF(x);
1306 Py_DECREF(y);
1307 goto done;
1308 }
1309 Py_DECREF(x);
1310 Py_DECREF(y);
1311 if (b == -1)
1312 goto done;
1313 }
1314 /* We reached the end of one deque or both */
1315 Py_XDECREF(x);
1316 Py_XDECREF(y);
1317 if (PyErr_Occurred())
1318 goto done;
1319 switch (op) {
1320 case Py_LT: cmp = y != NULL; break; /* if w was longer */
1321 case Py_LE: cmp = x == NULL; break; /* if v was not longer */
1322 case Py_EQ: cmp = x == y; break; /* if we reached the end of both */
1323 case Py_NE: cmp = x != y; break; /* if one deque continues */
1324 case Py_GT: cmp = x != NULL; break; /* if v was longer */
1325 case Py_GE: cmp = y == NULL; break; /* if w was not longer */
1326 }
Tim Peters1065f752004-10-01 01:03:29 +00001327
Raymond Hettinger738ec902004-02-29 02:15:56 +00001328done:
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001329 Py_XDECREF(it1);
1330 Py_XDECREF(it2);
1331 if (cmp == 1)
1332 Py_RETURN_TRUE;
1333 if (cmp == 0)
1334 Py_RETURN_FALSE;
1335 return NULL;
Raymond Hettinger738ec902004-02-29 02:15:56 +00001336}
1337
Raymond Hettinger756b3f32004-01-29 06:37:52 +00001338static int
Guido van Rossum8ce8a782007-11-01 19:42:39 +00001339deque_init(dequeobject *deque, PyObject *args, PyObject *kwdargs)
Raymond Hettinger756b3f32004-01-29 06:37:52 +00001340{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001341 PyObject *iterable = NULL;
1342 PyObject *maxlenobj = NULL;
1343 Py_ssize_t maxlen = -1;
1344 char *kwlist[] = {"iterable", "maxlen", 0};
Raymond Hettinger756b3f32004-01-29 06:37:52 +00001345
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001346 if (!PyArg_ParseTupleAndKeywords(args, kwdargs, "|OO:deque", kwlist, &iterable, &maxlenobj))
1347 return -1;
1348 if (maxlenobj != NULL && maxlenobj != Py_None) {
1349 maxlen = PyLong_AsSsize_t(maxlenobj);
1350 if (maxlen == -1 && PyErr_Occurred())
1351 return -1;
1352 if (maxlen < 0) {
1353 PyErr_SetString(PyExc_ValueError, "maxlen must be non-negative");
1354 return -1;
1355 }
1356 }
1357 deque->maxlen = maxlen;
1358 deque_clear(deque);
1359 if (iterable != NULL) {
1360 PyObject *rv = deque_extend(deque, iterable);
1361 if (rv == NULL)
1362 return -1;
1363 Py_DECREF(rv);
1364 }
1365 return 0;
Raymond Hettinger756b3f32004-01-29 06:37:52 +00001366}
1367
Raymond Hettinger5bb0f0e2009-03-10 12:56:32 +00001368static PyObject *
Jesus Cea16e2fca2012-08-03 14:49:42 +02001369deque_sizeof(dequeobject *deque, void *unused)
1370{
1371 Py_ssize_t res;
1372 Py_ssize_t blocks;
1373
1374 res = sizeof(dequeobject);
Raymond Hettingerdf715ba2013-07-06 13:01:13 -10001375 blocks = (deque->leftindex + Py_SIZE(deque) + BLOCKLEN - 1) / BLOCKLEN;
1376 assert(deque->leftindex + Py_SIZE(deque) - 1 ==
Jesus Cea16e2fca2012-08-03 14:49:42 +02001377 (blocks - 1) * BLOCKLEN + deque->rightindex);
1378 res += blocks * sizeof(block);
1379 return PyLong_FromSsize_t(res);
1380}
1381
1382PyDoc_STRVAR(sizeof_doc,
1383"D.__sizeof__() -- size of D in memory, in bytes");
1384
Raymond Hettinger0f1451c2015-03-23 23:23:55 -07001385static int
1386deque_bool(dequeobject *deque)
1387{
1388 return Py_SIZE(deque) != 0;
1389}
1390
Jesus Cea16e2fca2012-08-03 14:49:42 +02001391static PyObject *
Raymond Hettinger5bb0f0e2009-03-10 12:56:32 +00001392deque_get_maxlen(dequeobject *deque)
1393{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001394 if (deque->maxlen == -1)
1395 Py_RETURN_NONE;
1396 return PyLong_FromSsize_t(deque->maxlen);
Raymond Hettinger5bb0f0e2009-03-10 12:56:32 +00001397}
1398
Raymond Hettinger41290a62015-03-31 08:12:23 -07001399
1400/* deque object ********************************************************/
1401
Raymond Hettinger5bb0f0e2009-03-10 12:56:32 +00001402static PyGetSetDef deque_getset[] = {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001403 {"maxlen", (getter)deque_get_maxlen, (setter)NULL,
1404 "maximum size of a deque or None if unbounded"},
1405 {0}
Raymond Hettinger5bb0f0e2009-03-10 12:56:32 +00001406};
1407
Raymond Hettinger756b3f32004-01-29 06:37:52 +00001408static PySequenceMethods deque_as_sequence = {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001409 (lenfunc)deque_len, /* sq_length */
Raymond Hettinger41290a62015-03-31 08:12:23 -07001410 (binaryfunc)deque_concat, /* sq_concat */
1411 (ssizeargfunc)deque_repeat, /* sq_repeat */
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001412 (ssizeargfunc)deque_item, /* sq_item */
1413 0, /* sq_slice */
Raymond Hettinger87e69122015-03-02 23:32:02 -08001414 (ssizeobjargproc)deque_ass_item, /* sq_ass_item */
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001415 0, /* sq_ass_slice */
Raymond Hettinger39dadf72015-03-20 16:38:56 -07001416 (objobjproc)deque_contains, /* sq_contains */
Raymond Hettinger87e69122015-03-02 23:32:02 -08001417 (binaryfunc)deque_inplace_concat, /* sq_inplace_concat */
Raymond Hettinger41290a62015-03-31 08:12:23 -07001418 (ssizeargfunc)deque_inplace_repeat, /* sq_inplace_repeat */
Raymond Hettinger756b3f32004-01-29 06:37:52 +00001419};
1420
Raymond Hettinger0f1451c2015-03-23 23:23:55 -07001421static PyNumberMethods deque_as_number = {
1422 0, /* nb_add */
1423 0, /* nb_subtract */
1424 0, /* nb_multiply */
1425 0, /* nb_remainder */
1426 0, /* nb_divmod */
1427 0, /* nb_power */
1428 0, /* nb_negative */
1429 0, /* nb_positive */
1430 0, /* nb_absolute */
1431 (inquiry)deque_bool, /* nb_bool */
1432 0, /* nb_invert */
Raymond Hettinger0f1451c2015-03-23 23:23:55 -07001433 };
1434
Raymond Hettinger756b3f32004-01-29 06:37:52 +00001435static PyObject *deque_iter(dequeobject *deque);
Raymond Hettinger1e5809f2004-03-18 11:04:57 +00001436static PyObject *deque_reviter(dequeobject *deque);
Tim Peters1065f752004-10-01 01:03:29 +00001437PyDoc_STRVAR(reversed_doc,
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001438 "D.__reversed__() -- return a reverse iterator over the deque");
Raymond Hettinger756b3f32004-01-29 06:37:52 +00001439
1440static PyMethodDef deque_methods[] = {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001441 {"append", (PyCFunction)deque_append,
1442 METH_O, append_doc},
1443 {"appendleft", (PyCFunction)deque_appendleft,
1444 METH_O, appendleft_doc},
1445 {"clear", (PyCFunction)deque_clearmethod,
1446 METH_NOARGS, clear_doc},
1447 {"__copy__", (PyCFunction)deque_copy,
1448 METH_NOARGS, copy_doc},
Raymond Hettinger32ea1652015-03-21 01:37:37 -07001449 {"copy", (PyCFunction)deque_copy,
1450 METH_NOARGS, copy_doc},
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001451 {"count", (PyCFunction)deque_count,
Raymond Hettinger0f6f9472015-03-21 01:42:10 -07001452 METH_O, count_doc},
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001453 {"extend", (PyCFunction)deque_extend,
1454 METH_O, extend_doc},
1455 {"extendleft", (PyCFunction)deque_extendleft,
1456 METH_O, extendleft_doc},
Raymond Hettinger32ea1652015-03-21 01:37:37 -07001457 {"index", (PyCFunction)deque_index,
1458 METH_VARARGS, index_doc},
1459 {"insert", (PyCFunction)deque_insert,
1460 METH_VARARGS, insert_doc},
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001461 {"pop", (PyCFunction)deque_pop,
1462 METH_NOARGS, pop_doc},
1463 {"popleft", (PyCFunction)deque_popleft,
1464 METH_NOARGS, popleft_doc},
Raymond Hettinger0f6f9472015-03-21 01:42:10 -07001465 {"__reduce__", (PyCFunction)deque_reduce,
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001466 METH_NOARGS, reduce_doc},
1467 {"remove", (PyCFunction)deque_remove,
1468 METH_O, remove_doc},
1469 {"__reversed__", (PyCFunction)deque_reviter,
1470 METH_NOARGS, reversed_doc},
1471 {"reverse", (PyCFunction)deque_reverse,
1472 METH_NOARGS, reverse_doc},
1473 {"rotate", (PyCFunction)deque_rotate,
Jesus Cea16e2fca2012-08-03 14:49:42 +02001474 METH_VARARGS, rotate_doc},
1475 {"__sizeof__", (PyCFunction)deque_sizeof,
1476 METH_NOARGS, sizeof_doc},
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001477 {NULL, NULL} /* sentinel */
Raymond Hettinger756b3f32004-01-29 06:37:52 +00001478};
1479
1480PyDoc_STRVAR(deque_doc,
Andrew Svetlov6a5c7c32012-10-31 11:50:40 +02001481"deque([iterable[, maxlen]]) --> deque object\n\
Raymond Hettinger756b3f32004-01-29 06:37:52 +00001482\n\
Raymond Hettinger41290a62015-03-31 08:12:23 -07001483A list-like sequence optimized for data accesses near its endpoints.");
Raymond Hettinger756b3f32004-01-29 06:37:52 +00001484
Neal Norwitz87f10132004-02-29 15:40:53 +00001485static PyTypeObject deque_type = {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001486 PyVarObject_HEAD_INIT(NULL, 0)
1487 "collections.deque", /* tp_name */
1488 sizeof(dequeobject), /* tp_basicsize */
1489 0, /* tp_itemsize */
1490 /* methods */
1491 (destructor)deque_dealloc, /* tp_dealloc */
1492 0, /* tp_print */
1493 0, /* tp_getattr */
1494 0, /* tp_setattr */
1495 0, /* tp_reserved */
1496 deque_repr, /* tp_repr */
Raymond Hettinger0f1451c2015-03-23 23:23:55 -07001497 &deque_as_number, /* tp_as_number */
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001498 &deque_as_sequence, /* tp_as_sequence */
1499 0, /* tp_as_mapping */
Georg Brandlf038b322010-10-18 07:35:09 +00001500 PyObject_HashNotImplemented, /* tp_hash */
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001501 0, /* tp_call */
1502 0, /* tp_str */
1503 PyObject_GenericGetAttr, /* tp_getattro */
1504 0, /* tp_setattro */
1505 0, /* tp_as_buffer */
1506 Py_TPFLAGS_DEFAULT | Py_TPFLAGS_BASETYPE | Py_TPFLAGS_HAVE_GC,
Georg Brandlf038b322010-10-18 07:35:09 +00001507 /* tp_flags */
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001508 deque_doc, /* tp_doc */
1509 (traverseproc)deque_traverse, /* tp_traverse */
1510 (inquiry)deque_clear, /* tp_clear */
1511 (richcmpfunc)deque_richcompare, /* tp_richcompare */
Georg Brandlf038b322010-10-18 07:35:09 +00001512 offsetof(dequeobject, weakreflist), /* tp_weaklistoffset*/
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001513 (getiterfunc)deque_iter, /* tp_iter */
1514 0, /* tp_iternext */
1515 deque_methods, /* tp_methods */
1516 0, /* tp_members */
Georg Brandlf038b322010-10-18 07:35:09 +00001517 deque_getset, /* tp_getset */
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001518 0, /* tp_base */
1519 0, /* tp_dict */
1520 0, /* tp_descr_get */
1521 0, /* tp_descr_set */
1522 0, /* tp_dictoffset */
1523 (initproc)deque_init, /* tp_init */
1524 PyType_GenericAlloc, /* tp_alloc */
1525 deque_new, /* tp_new */
1526 PyObject_GC_Del, /* tp_free */
Raymond Hettinger756b3f32004-01-29 06:37:52 +00001527};
1528
1529/*********************** Deque Iterator **************************/
1530
1531typedef struct {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001532 PyObject_HEAD
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001533 block *b;
Raymond Hettinger87e69122015-03-02 23:32:02 -08001534 Py_ssize_t index;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001535 dequeobject *deque;
Raymond Hettingerf9d9c792015-03-02 22:47:46 -08001536 size_t state; /* state when the iterator is created */
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001537 Py_ssize_t counter; /* number of items remaining for iteration */
Raymond Hettinger756b3f32004-01-29 06:37:52 +00001538} dequeiterobject;
1539
Martin v. Löwis59683e82008-06-13 07:50:45 +00001540static PyTypeObject dequeiter_type;
Raymond Hettinger756b3f32004-01-29 06:37:52 +00001541
1542static PyObject *
1543deque_iter(dequeobject *deque)
1544{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001545 dequeiterobject *it;
Raymond Hettinger756b3f32004-01-29 06:37:52 +00001546
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001547 it = PyObject_GC_New(dequeiterobject, &dequeiter_type);
1548 if (it == NULL)
1549 return NULL;
1550 it->b = deque->leftblock;
1551 it->index = deque->leftindex;
1552 Py_INCREF(deque);
1553 it->deque = deque;
1554 it->state = deque->state;
Raymond Hettingerdf715ba2013-07-06 13:01:13 -10001555 it->counter = Py_SIZE(deque);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001556 PyObject_GC_Track(it);
1557 return (PyObject *)it;
Raymond Hettinger756b3f32004-01-29 06:37:52 +00001558}
1559
Antoine Pitrou7ddda782009-01-01 15:35:33 +00001560static int
1561dequeiter_traverse(dequeiterobject *dio, visitproc visit, void *arg)
1562{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001563 Py_VISIT(dio->deque);
1564 return 0;
Antoine Pitrou7ddda782009-01-01 15:35:33 +00001565}
1566
Raymond Hettinger756b3f32004-01-29 06:37:52 +00001567static void
1568dequeiter_dealloc(dequeiterobject *dio)
1569{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001570 Py_XDECREF(dio->deque);
1571 PyObject_GC_Del(dio);
Raymond Hettinger756b3f32004-01-29 06:37:52 +00001572}
1573
1574static PyObject *
1575dequeiter_next(dequeiterobject *it)
1576{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001577 PyObject *item;
Raymond Hettingerd1b3d882004-10-02 00:43:13 +00001578
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001579 if (it->deque->state != it->state) {
1580 it->counter = 0;
1581 PyErr_SetString(PyExc_RuntimeError,
1582 "deque mutated during iteration");
1583 return NULL;
1584 }
1585 if (it->counter == 0)
1586 return NULL;
1587 assert (!(it->b == it->deque->rightblock &&
1588 it->index > it->deque->rightindex));
Raymond Hettinger756b3f32004-01-29 06:37:52 +00001589
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001590 item = it->b->data[it->index];
1591 it->index++;
1592 it->counter--;
1593 if (it->index == BLOCKLEN && it->counter > 0) {
Raymond Hettinger82df9252013-07-07 01:43:42 -10001594 CHECK_NOT_END(it->b->rightlink);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001595 it->b = it->b->rightlink;
1596 it->index = 0;
1597 }
1598 Py_INCREF(item);
1599 return item;
Raymond Hettinger756b3f32004-01-29 06:37:52 +00001600}
1601
Raymond Hettinger6b27cda2005-09-24 21:23:05 +00001602static PyObject *
Kristján Valur Jónsson31668b82012-04-03 10:49:41 +00001603dequeiter_new(PyTypeObject *type, PyObject *args, PyObject *kwds)
1604{
1605 Py_ssize_t i, index=0;
1606 PyObject *deque;
1607 dequeiterobject *it;
1608 if (!PyArg_ParseTuple(args, "O!|n", &deque_type, &deque, &index))
1609 return NULL;
1610 assert(type == &dequeiter_type);
1611
1612 it = (dequeiterobject*)deque_iter((dequeobject *)deque);
1613 if (!it)
1614 return NULL;
1615 /* consume items from the queue */
1616 for(i=0; i<index; i++) {
1617 PyObject *item = dequeiter_next(it);
1618 if (item) {
1619 Py_DECREF(item);
1620 } else {
1621 if (it->counter) {
1622 Py_DECREF(it);
1623 return NULL;
1624 } else
1625 break;
1626 }
1627 }
1628 return (PyObject*)it;
1629}
1630
1631static PyObject *
Raymond Hettinger1e5809f2004-03-18 11:04:57 +00001632dequeiter_len(dequeiterobject *it)
1633{
Antoine Pitrou554f3342010-08-17 18:30:06 +00001634 return PyLong_FromSsize_t(it->counter);
Raymond Hettinger1e5809f2004-03-18 11:04:57 +00001635}
1636
Armin Rigof5b3e362006-02-11 21:32:43 +00001637PyDoc_STRVAR(length_hint_doc, "Private method returning an estimate of len(list(it)).");
Raymond Hettinger6b27cda2005-09-24 21:23:05 +00001638
Kristján Valur Jónsson31668b82012-04-03 10:49:41 +00001639static PyObject *
1640dequeiter_reduce(dequeiterobject *it)
1641{
Raymond Hettingerdf715ba2013-07-06 13:01:13 -10001642 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 +00001643}
1644
Raymond Hettinger6b27cda2005-09-24 21:23:05 +00001645static PyMethodDef dequeiter_methods[] = {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001646 {"__length_hint__", (PyCFunction)dequeiter_len, METH_NOARGS, length_hint_doc},
Kristján Valur Jónsson31668b82012-04-03 10:49:41 +00001647 {"__reduce__", (PyCFunction)dequeiter_reduce, METH_NOARGS, reduce_doc},
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001648 {NULL, NULL} /* sentinel */
Raymond Hettinger1e5809f2004-03-18 11:04:57 +00001649};
1650
Martin v. Löwis59683e82008-06-13 07:50:45 +00001651static PyTypeObject dequeiter_type = {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001652 PyVarObject_HEAD_INIT(NULL, 0)
Raymond Hettinger87e69122015-03-02 23:32:02 -08001653 "_collections._deque_iterator", /* tp_name */
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001654 sizeof(dequeiterobject), /* tp_basicsize */
1655 0, /* tp_itemsize */
1656 /* methods */
1657 (destructor)dequeiter_dealloc, /* tp_dealloc */
1658 0, /* tp_print */
1659 0, /* tp_getattr */
1660 0, /* tp_setattr */
1661 0, /* tp_reserved */
1662 0, /* tp_repr */
1663 0, /* tp_as_number */
1664 0, /* tp_as_sequence */
1665 0, /* tp_as_mapping */
1666 0, /* tp_hash */
1667 0, /* tp_call */
1668 0, /* tp_str */
1669 PyObject_GenericGetAttr, /* tp_getattro */
1670 0, /* tp_setattro */
1671 0, /* tp_as_buffer */
Raymond Hettinger87e69122015-03-02 23:32:02 -08001672 Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC, /* tp_flags */
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001673 0, /* tp_doc */
1674 (traverseproc)dequeiter_traverse, /* tp_traverse */
1675 0, /* tp_clear */
1676 0, /* tp_richcompare */
1677 0, /* tp_weaklistoffset */
1678 PyObject_SelfIter, /* tp_iter */
1679 (iternextfunc)dequeiter_next, /* tp_iternext */
1680 dequeiter_methods, /* tp_methods */
Kristján Valur Jónsson31668b82012-04-03 10:49:41 +00001681 0, /* tp_members */
1682 0, /* tp_getset */
1683 0, /* tp_base */
1684 0, /* tp_dict */
1685 0, /* tp_descr_get */
1686 0, /* tp_descr_set */
1687 0, /* tp_dictoffset */
1688 0, /* tp_init */
1689 0, /* tp_alloc */
1690 dequeiter_new, /* tp_new */
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001691 0,
Raymond Hettinger756b3f32004-01-29 06:37:52 +00001692};
1693
Raymond Hettinger1e5809f2004-03-18 11:04:57 +00001694/*********************** Deque Reverse Iterator **************************/
1695
Martin v. Löwis59683e82008-06-13 07:50:45 +00001696static PyTypeObject dequereviter_type;
Raymond Hettinger1e5809f2004-03-18 11:04:57 +00001697
1698static PyObject *
1699deque_reviter(dequeobject *deque)
1700{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001701 dequeiterobject *it;
Raymond Hettinger1e5809f2004-03-18 11:04:57 +00001702
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001703 it = PyObject_GC_New(dequeiterobject, &dequereviter_type);
1704 if (it == NULL)
1705 return NULL;
1706 it->b = deque->rightblock;
1707 it->index = deque->rightindex;
1708 Py_INCREF(deque);
1709 it->deque = deque;
1710 it->state = deque->state;
Raymond Hettingerdf715ba2013-07-06 13:01:13 -10001711 it->counter = Py_SIZE(deque);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001712 PyObject_GC_Track(it);
1713 return (PyObject *)it;
Raymond Hettinger1e5809f2004-03-18 11:04:57 +00001714}
1715
1716static PyObject *
1717dequereviter_next(dequeiterobject *it)
1718{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001719 PyObject *item;
1720 if (it->counter == 0)
1721 return NULL;
Raymond Hettinger1e5809f2004-03-18 11:04:57 +00001722
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001723 if (it->deque->state != it->state) {
1724 it->counter = 0;
1725 PyErr_SetString(PyExc_RuntimeError,
1726 "deque mutated during iteration");
1727 return NULL;
1728 }
1729 assert (!(it->b == it->deque->leftblock &&
1730 it->index < it->deque->leftindex));
Raymond Hettinger1e5809f2004-03-18 11:04:57 +00001731
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001732 item = it->b->data[it->index];
1733 it->index--;
1734 it->counter--;
1735 if (it->index == -1 && it->counter > 0) {
Raymond Hettinger82df9252013-07-07 01:43:42 -10001736 CHECK_NOT_END(it->b->leftlink);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001737 it->b = it->b->leftlink;
1738 it->index = BLOCKLEN - 1;
1739 }
1740 Py_INCREF(item);
1741 return item;
Raymond Hettinger1e5809f2004-03-18 11:04:57 +00001742}
1743
Kristján Valur Jónsson31668b82012-04-03 10:49:41 +00001744static PyObject *
1745dequereviter_new(PyTypeObject *type, PyObject *args, PyObject *kwds)
1746{
1747 Py_ssize_t i, index=0;
1748 PyObject *deque;
1749 dequeiterobject *it;
1750 if (!PyArg_ParseTuple(args, "O!|n", &deque_type, &deque, &index))
1751 return NULL;
1752 assert(type == &dequereviter_type);
1753
1754 it = (dequeiterobject*)deque_reviter((dequeobject *)deque);
1755 if (!it)
1756 return NULL;
1757 /* consume items from the queue */
1758 for(i=0; i<index; i++) {
1759 PyObject *item = dequereviter_next(it);
1760 if (item) {
1761 Py_DECREF(item);
1762 } else {
1763 if (it->counter) {
1764 Py_DECREF(it);
1765 return NULL;
1766 } else
1767 break;
1768 }
1769 }
1770 return (PyObject*)it;
1771}
1772
Martin v. Löwis59683e82008-06-13 07:50:45 +00001773static PyTypeObject dequereviter_type = {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001774 PyVarObject_HEAD_INIT(NULL, 0)
Raymond Hettinger87e69122015-03-02 23:32:02 -08001775 "_collections._deque_reverse_iterator", /* tp_name */
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001776 sizeof(dequeiterobject), /* tp_basicsize */
1777 0, /* tp_itemsize */
1778 /* methods */
1779 (destructor)dequeiter_dealloc, /* tp_dealloc */
1780 0, /* tp_print */
1781 0, /* tp_getattr */
1782 0, /* tp_setattr */
1783 0, /* tp_reserved */
1784 0, /* tp_repr */
1785 0, /* tp_as_number */
1786 0, /* tp_as_sequence */
1787 0, /* tp_as_mapping */
1788 0, /* tp_hash */
1789 0, /* tp_call */
1790 0, /* tp_str */
1791 PyObject_GenericGetAttr, /* tp_getattro */
1792 0, /* tp_setattro */
1793 0, /* tp_as_buffer */
Raymond Hettinger87e69122015-03-02 23:32:02 -08001794 Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC, /* tp_flags */
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001795 0, /* tp_doc */
1796 (traverseproc)dequeiter_traverse, /* tp_traverse */
1797 0, /* tp_clear */
1798 0, /* tp_richcompare */
1799 0, /* tp_weaklistoffset */
1800 PyObject_SelfIter, /* tp_iter */
1801 (iternextfunc)dequereviter_next, /* tp_iternext */
1802 dequeiter_methods, /* tp_methods */
Kristján Valur Jónsson31668b82012-04-03 10:49:41 +00001803 0, /* tp_members */
1804 0, /* tp_getset */
1805 0, /* tp_base */
1806 0, /* tp_dict */
1807 0, /* tp_descr_get */
1808 0, /* tp_descr_set */
1809 0, /* tp_dictoffset */
1810 0, /* tp_init */
1811 0, /* tp_alloc */
1812 dequereviter_new, /* tp_new */
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001813 0,
Raymond Hettinger1e5809f2004-03-18 11:04:57 +00001814};
1815
Guido van Rossum1968ad32006-02-25 22:38:04 +00001816/* defaultdict type *********************************************************/
1817
1818typedef struct {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001819 PyDictObject dict;
1820 PyObject *default_factory;
Guido van Rossum1968ad32006-02-25 22:38:04 +00001821} defdictobject;
1822
1823static PyTypeObject defdict_type; /* Forward */
1824
1825PyDoc_STRVAR(defdict_missing_doc,
1826"__missing__(key) # Called by __getitem__ for missing key; pseudo-code:\n\
Guido van Rossumd8faa362007-04-27 19:54:29 +00001827 if self.default_factory is None: raise KeyError((key,))\n\
Guido van Rossum1968ad32006-02-25 22:38:04 +00001828 self[key] = value = self.default_factory()\n\
1829 return value\n\
1830");
1831
1832static PyObject *
1833defdict_missing(defdictobject *dd, PyObject *key)
1834{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001835 PyObject *factory = dd->default_factory;
1836 PyObject *value;
1837 if (factory == NULL || factory == Py_None) {
1838 /* XXX Call dict.__missing__(key) */
1839 PyObject *tup;
1840 tup = PyTuple_Pack(1, key);
1841 if (!tup) return NULL;
1842 PyErr_SetObject(PyExc_KeyError, tup);
1843 Py_DECREF(tup);
1844 return NULL;
1845 }
1846 value = PyEval_CallObject(factory, NULL);
1847 if (value == NULL)
1848 return value;
1849 if (PyObject_SetItem((PyObject *)dd, key, value) < 0) {
1850 Py_DECREF(value);
1851 return NULL;
1852 }
1853 return value;
Guido van Rossum1968ad32006-02-25 22:38:04 +00001854}
1855
1856PyDoc_STRVAR(defdict_copy_doc, "D.copy() -> a shallow copy of D.");
1857
1858static PyObject *
1859defdict_copy(defdictobject *dd)
1860{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001861 /* This calls the object's class. That only works for subclasses
1862 whose class constructor has the same signature. Subclasses that
1863 define a different constructor signature must override copy().
1864 */
Raymond Hettinger54628fa2009-08-04 19:16:39 +00001865
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001866 if (dd->default_factory == NULL)
1867 return PyObject_CallFunctionObjArgs((PyObject*)Py_TYPE(dd), Py_None, dd, NULL);
1868 return PyObject_CallFunctionObjArgs((PyObject*)Py_TYPE(dd),
1869 dd->default_factory, dd, NULL);
Guido van Rossum1968ad32006-02-25 22:38:04 +00001870}
1871
1872static PyObject *
1873defdict_reduce(defdictobject *dd)
1874{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001875 /* __reduce__ must return a 5-tuple as follows:
Guido van Rossum1968ad32006-02-25 22:38:04 +00001876
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001877 - factory function
1878 - tuple of args for the factory function
1879 - additional state (here None)
1880 - sequence iterator (here None)
1881 - dictionary iterator (yielding successive (key, value) pairs
Guido van Rossum1968ad32006-02-25 22:38:04 +00001882
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001883 This API is used by pickle.py and copy.py.
Guido van Rossum1968ad32006-02-25 22:38:04 +00001884
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001885 For this to be useful with pickle.py, the default_factory
1886 must be picklable; e.g., None, a built-in, or a global
1887 function in a module or package.
Guido van Rossum1968ad32006-02-25 22:38:04 +00001888
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001889 Both shallow and deep copying are supported, but for deep
1890 copying, the default_factory must be deep-copyable; e.g. None,
1891 or a built-in (functions are not copyable at this time).
Guido van Rossum1968ad32006-02-25 22:38:04 +00001892
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001893 This only works for subclasses as long as their constructor
1894 signature is compatible; the first argument must be the
1895 optional default_factory, defaulting to None.
1896 */
1897 PyObject *args;
1898 PyObject *items;
1899 PyObject *iter;
1900 PyObject *result;
Martin v. Löwisbd928fe2011-10-14 10:20:37 +02001901 _Py_IDENTIFIER(items);
Martin v. Löwisafe55bb2011-10-09 10:38:36 +02001902
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001903 if (dd->default_factory == NULL || dd->default_factory == Py_None)
1904 args = PyTuple_New(0);
1905 else
1906 args = PyTuple_Pack(1, dd->default_factory);
1907 if (args == NULL)
1908 return NULL;
Martin v. Löwisafe55bb2011-10-09 10:38:36 +02001909 items = _PyObject_CallMethodId((PyObject *)dd, &PyId_items, "()");
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001910 if (items == NULL) {
1911 Py_DECREF(args);
1912 return NULL;
1913 }
1914 iter = PyObject_GetIter(items);
1915 if (iter == NULL) {
1916 Py_DECREF(items);
1917 Py_DECREF(args);
1918 return NULL;
1919 }
1920 result = PyTuple_Pack(5, Py_TYPE(dd), args,
1921 Py_None, Py_None, iter);
1922 Py_DECREF(iter);
1923 Py_DECREF(items);
1924 Py_DECREF(args);
1925 return result;
Guido van Rossum1968ad32006-02-25 22:38:04 +00001926}
1927
1928static PyMethodDef defdict_methods[] = {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001929 {"__missing__", (PyCFunction)defdict_missing, METH_O,
1930 defdict_missing_doc},
1931 {"copy", (PyCFunction)defdict_copy, METH_NOARGS,
1932 defdict_copy_doc},
1933 {"__copy__", (PyCFunction)defdict_copy, METH_NOARGS,
1934 defdict_copy_doc},
1935 {"__reduce__", (PyCFunction)defdict_reduce, METH_NOARGS,
1936 reduce_doc},
1937 {NULL}
Guido van Rossum1968ad32006-02-25 22:38:04 +00001938};
1939
1940static PyMemberDef defdict_members[] = {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001941 {"default_factory", T_OBJECT,
1942 offsetof(defdictobject, default_factory), 0,
1943 PyDoc_STR("Factory for default value called by __missing__().")},
1944 {NULL}
Guido van Rossum1968ad32006-02-25 22:38:04 +00001945};
1946
1947static void
1948defdict_dealloc(defdictobject *dd)
1949{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001950 Py_CLEAR(dd->default_factory);
1951 PyDict_Type.tp_dealloc((PyObject *)dd);
Guido van Rossum1968ad32006-02-25 22:38:04 +00001952}
1953
Guido van Rossum1968ad32006-02-25 22:38:04 +00001954static PyObject *
1955defdict_repr(defdictobject *dd)
1956{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001957 PyObject *baserepr;
1958 PyObject *defrepr;
1959 PyObject *result;
1960 baserepr = PyDict_Type.tp_repr((PyObject *)dd);
1961 if (baserepr == NULL)
1962 return NULL;
1963 if (dd->default_factory == NULL)
1964 defrepr = PyUnicode_FromString("None");
1965 else
1966 {
1967 int status = Py_ReprEnter(dd->default_factory);
1968 if (status != 0) {
Antoine Pitrouf5f1fe02012-02-15 02:42:46 +01001969 if (status < 0) {
1970 Py_DECREF(baserepr);
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001971 return NULL;
Antoine Pitrouf5f1fe02012-02-15 02:42:46 +01001972 }
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001973 defrepr = PyUnicode_FromString("...");
1974 }
1975 else
1976 defrepr = PyObject_Repr(dd->default_factory);
1977 Py_ReprLeave(dd->default_factory);
1978 }
1979 if (defrepr == NULL) {
1980 Py_DECREF(baserepr);
1981 return NULL;
1982 }
1983 result = PyUnicode_FromFormat("defaultdict(%U, %U)",
1984 defrepr, baserepr);
1985 Py_DECREF(defrepr);
1986 Py_DECREF(baserepr);
1987 return result;
Guido van Rossum1968ad32006-02-25 22:38:04 +00001988}
1989
1990static int
1991defdict_traverse(PyObject *self, visitproc visit, void *arg)
1992{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001993 Py_VISIT(((defdictobject *)self)->default_factory);
1994 return PyDict_Type.tp_traverse(self, visit, arg);
Guido van Rossum1968ad32006-02-25 22:38:04 +00001995}
1996
1997static int
1998defdict_tp_clear(defdictobject *dd)
1999{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002000 Py_CLEAR(dd->default_factory);
2001 return PyDict_Type.tp_clear((PyObject *)dd);
Guido van Rossum1968ad32006-02-25 22:38:04 +00002002}
2003
2004static int
2005defdict_init(PyObject *self, PyObject *args, PyObject *kwds)
2006{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002007 defdictobject *dd = (defdictobject *)self;
2008 PyObject *olddefault = dd->default_factory;
2009 PyObject *newdefault = NULL;
2010 PyObject *newargs;
2011 int result;
2012 if (args == NULL || !PyTuple_Check(args))
2013 newargs = PyTuple_New(0);
2014 else {
2015 Py_ssize_t n = PyTuple_GET_SIZE(args);
2016 if (n > 0) {
2017 newdefault = PyTuple_GET_ITEM(args, 0);
2018 if (!PyCallable_Check(newdefault) && newdefault != Py_None) {
2019 PyErr_SetString(PyExc_TypeError,
2020 "first argument must be callable");
2021 return -1;
2022 }
2023 }
2024 newargs = PySequence_GetSlice(args, 1, n);
2025 }
2026 if (newargs == NULL)
2027 return -1;
2028 Py_XINCREF(newdefault);
2029 dd->default_factory = newdefault;
2030 result = PyDict_Type.tp_init(self, newargs, kwds);
2031 Py_DECREF(newargs);
2032 Py_XDECREF(olddefault);
2033 return result;
Guido van Rossum1968ad32006-02-25 22:38:04 +00002034}
2035
2036PyDoc_STRVAR(defdict_doc,
Benjamin Peterson9cb33b72014-01-13 23:56:05 -05002037"defaultdict(default_factory[, ...]) --> dict with default factory\n\
Guido van Rossum1968ad32006-02-25 22:38:04 +00002038\n\
2039The default factory is called without arguments to produce\n\
2040a new value when a key is not present, in __getitem__ only.\n\
2041A defaultdict compares equal to a dict with the same items.\n\
Benjamin Peterson9cb33b72014-01-13 23:56:05 -05002042All remaining arguments are treated the same as if they were\n\
2043passed to the dict constructor, including keyword arguments.\n\
Guido van Rossum1968ad32006-02-25 22:38:04 +00002044");
2045
Thomas Wouters49fd7fa2006-04-21 10:40:58 +00002046/* See comment in xxsubtype.c */
2047#define DEFERRED_ADDRESS(ADDR) 0
2048
Guido van Rossum1968ad32006-02-25 22:38:04 +00002049static PyTypeObject defdict_type = {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002050 PyVarObject_HEAD_INIT(DEFERRED_ADDRESS(&PyType_Type), 0)
2051 "collections.defaultdict", /* tp_name */
2052 sizeof(defdictobject), /* tp_basicsize */
2053 0, /* tp_itemsize */
2054 /* methods */
2055 (destructor)defdict_dealloc, /* tp_dealloc */
2056 0, /* tp_print */
2057 0, /* tp_getattr */
2058 0, /* tp_setattr */
2059 0, /* tp_reserved */
2060 (reprfunc)defdict_repr, /* tp_repr */
2061 0, /* tp_as_number */
2062 0, /* tp_as_sequence */
2063 0, /* tp_as_mapping */
2064 0, /* tp_hash */
2065 0, /* tp_call */
2066 0, /* tp_str */
2067 PyObject_GenericGetAttr, /* tp_getattro */
2068 0, /* tp_setattro */
2069 0, /* tp_as_buffer */
2070 Py_TPFLAGS_DEFAULT | Py_TPFLAGS_BASETYPE | Py_TPFLAGS_HAVE_GC,
2071 /* tp_flags */
2072 defdict_doc, /* tp_doc */
2073 defdict_traverse, /* tp_traverse */
2074 (inquiry)defdict_tp_clear, /* tp_clear */
2075 0, /* tp_richcompare */
2076 0, /* tp_weaklistoffset*/
2077 0, /* tp_iter */
2078 0, /* tp_iternext */
2079 defdict_methods, /* tp_methods */
2080 defdict_members, /* tp_members */
2081 0, /* tp_getset */
2082 DEFERRED_ADDRESS(&PyDict_Type), /* tp_base */
2083 0, /* tp_dict */
2084 0, /* tp_descr_get */
2085 0, /* tp_descr_set */
2086 0, /* tp_dictoffset */
2087 defdict_init, /* tp_init */
2088 PyType_GenericAlloc, /* tp_alloc */
2089 0, /* tp_new */
2090 PyObject_GC_Del, /* tp_free */
Guido van Rossum1968ad32006-02-25 22:38:04 +00002091};
2092
Raymond Hettinger96f34102010-12-15 16:30:37 +00002093/* helper function for Counter *********************************************/
2094
2095PyDoc_STRVAR(_count_elements_doc,
2096"_count_elements(mapping, iterable) -> None\n\
2097\n\
2098Count elements in the iterable, updating the mappping");
2099
2100static PyObject *
2101_count_elements(PyObject *self, PyObject *args)
2102{
Raymond Hettingercb1d96f2013-10-04 16:51:02 -07002103 _Py_IDENTIFIER(get);
Raymond Hettinger2ff21902013-10-01 00:55:43 -07002104 _Py_IDENTIFIER(__setitem__);
Raymond Hettinger96f34102010-12-15 16:30:37 +00002105 PyObject *it, *iterable, *mapping, *oldval;
2106 PyObject *newval = NULL;
2107 PyObject *key = NULL;
Raymond Hettinger224c87d2013-10-01 21:36:09 -07002108 PyObject *zero = NULL;
Raymond Hettinger96f34102010-12-15 16:30:37 +00002109 PyObject *one = NULL;
Raymond Hettingercb1d96f2013-10-04 16:51:02 -07002110 PyObject *bound_get = NULL;
2111 PyObject *mapping_get;
2112 PyObject *dict_get;
Raymond Hettinger2ff21902013-10-01 00:55:43 -07002113 PyObject *mapping_setitem;
Raymond Hettinger2ff21902013-10-01 00:55:43 -07002114 PyObject *dict_setitem;
Raymond Hettinger96f34102010-12-15 16:30:37 +00002115
2116 if (!PyArg_UnpackTuple(args, "_count_elements", 2, 2, &mapping, &iterable))
2117 return NULL;
2118
Raymond Hettinger96f34102010-12-15 16:30:37 +00002119 it = PyObject_GetIter(iterable);
2120 if (it == NULL)
2121 return NULL;
Raymond Hettinger426e0522011-01-03 02:12:02 +00002122
Raymond Hettinger96f34102010-12-15 16:30:37 +00002123 one = PyLong_FromLong(1);
Raymond Hettinger224c87d2013-10-01 21:36:09 -07002124 if (one == NULL)
2125 goto done;
Raymond Hettinger426e0522011-01-03 02:12:02 +00002126
Raymond Hettingercb1d96f2013-10-04 16:51:02 -07002127 /* Only take the fast path when get() and __setitem__()
2128 * have not been overridden.
2129 */
2130 mapping_get = _PyType_LookupId(Py_TYPE(mapping), &PyId_get);
2131 dict_get = _PyType_LookupId(&PyDict_Type, &PyId_get);
Raymond Hettinger2ff21902013-10-01 00:55:43 -07002132 mapping_setitem = _PyType_LookupId(Py_TYPE(mapping), &PyId___setitem__);
2133 dict_setitem = _PyType_LookupId(&PyDict_Type, &PyId___setitem__);
2134
Raymond Hettingercb1d96f2013-10-04 16:51:02 -07002135 if (mapping_get != NULL && mapping_get == dict_get &&
2136 mapping_setitem != NULL && mapping_setitem == dict_setitem) {
Raymond Hettinger426e0522011-01-03 02:12:02 +00002137 while (1) {
Raymond Hettinger507d9972014-05-18 21:32:40 +01002138 /* Fast path advantages:
2139 1. Eliminate double hashing
2140 (by re-using the same hash for both the get and set)
2141 2. Avoid argument overhead of PyObject_CallFunctionObjArgs
2142 (argument tuple creation and parsing)
2143 3. Avoid indirection through a bound method object
2144 (creates another argument tuple)
2145 4. Avoid initial increment from zero
2146 (reuse an existing one-object instead)
2147 */
Raymond Hettinger4b0b1ac2014-05-03 16:41:19 -07002148 Py_hash_t hash;
2149
Raymond Hettinger426e0522011-01-03 02:12:02 +00002150 key = PyIter_Next(it);
Victor Stinnera154b5c2011-04-20 23:23:52 +02002151 if (key == NULL)
2152 break;
Raymond Hettinger4b0b1ac2014-05-03 16:41:19 -07002153
2154 if (!PyUnicode_CheckExact(key) ||
2155 (hash = ((PyASCIIObject *) key)->hash) == -1)
2156 {
2157 hash = PyObject_Hash(key);
Raymond Hettingerda2850f2015-02-27 12:42:54 -08002158 if (hash == -1)
Raymond Hettinger4b0b1ac2014-05-03 16:41:19 -07002159 goto done;
2160 }
2161
2162 oldval = _PyDict_GetItem_KnownHash(mapping, key, hash);
Raymond Hettinger426e0522011-01-03 02:12:02 +00002163 if (oldval == NULL) {
Raymond Hettinger4b0b1ac2014-05-03 16:41:19 -07002164 if (_PyDict_SetItem_KnownHash(mapping, key, one, hash) == -1)
Raymond Hettinger507d9972014-05-18 21:32:40 +01002165 goto done;
Raymond Hettinger426e0522011-01-03 02:12:02 +00002166 } else {
2167 newval = PyNumber_Add(oldval, one);
2168 if (newval == NULL)
Raymond Hettinger507d9972014-05-18 21:32:40 +01002169 goto done;
Raymond Hettinger4b0b1ac2014-05-03 16:41:19 -07002170 if (_PyDict_SetItem_KnownHash(mapping, key, newval, hash) == -1)
Raymond Hettinger507d9972014-05-18 21:32:40 +01002171 goto done;
Raymond Hettinger426e0522011-01-03 02:12:02 +00002172 Py_CLEAR(newval);
2173 }
2174 Py_DECREF(key);
Raymond Hettinger96f34102010-12-15 16:30:37 +00002175 }
Raymond Hettinger426e0522011-01-03 02:12:02 +00002176 } else {
Victor Stinnere7f516c2013-11-06 23:52:55 +01002177 bound_get = _PyObject_GetAttrId(mapping, &PyId_get);
Raymond Hettingercb1d96f2013-10-04 16:51:02 -07002178 if (bound_get == NULL)
Raymond Hettinger224c87d2013-10-01 21:36:09 -07002179 goto done;
2180
2181 zero = PyLong_FromLong(0);
2182 if (zero == NULL)
2183 goto done;
2184
Raymond Hettinger426e0522011-01-03 02:12:02 +00002185 while (1) {
2186 key = PyIter_Next(it);
Victor Stinnera154b5c2011-04-20 23:23:52 +02002187 if (key == NULL)
2188 break;
Raymond Hettingercb1d96f2013-10-04 16:51:02 -07002189 oldval = PyObject_CallFunctionObjArgs(bound_get, key, zero, NULL);
Raymond Hettinger224c87d2013-10-01 21:36:09 -07002190 if (oldval == NULL)
2191 break;
2192 newval = PyNumber_Add(oldval, one);
2193 Py_DECREF(oldval);
2194 if (newval == NULL)
2195 break;
Raymond Hettinger426e0522011-01-03 02:12:02 +00002196 if (PyObject_SetItem(mapping, key, newval) == -1)
Raymond Hettinger96f34102010-12-15 16:30:37 +00002197 break;
2198 Py_CLEAR(newval);
Raymond Hettinger426e0522011-01-03 02:12:02 +00002199 Py_DECREF(key);
Raymond Hettinger96f34102010-12-15 16:30:37 +00002200 }
Raymond Hettinger96f34102010-12-15 16:30:37 +00002201 }
Raymond Hettinger426e0522011-01-03 02:12:02 +00002202
Raymond Hettinger224c87d2013-10-01 21:36:09 -07002203done:
Raymond Hettinger96f34102010-12-15 16:30:37 +00002204 Py_DECREF(it);
2205 Py_XDECREF(key);
2206 Py_XDECREF(newval);
Raymond Hettingercb1d96f2013-10-04 16:51:02 -07002207 Py_XDECREF(bound_get);
Raymond Hettinger224c87d2013-10-01 21:36:09 -07002208 Py_XDECREF(zero);
2209 Py_XDECREF(one);
Raymond Hettinger96f34102010-12-15 16:30:37 +00002210 if (PyErr_Occurred())
2211 return NULL;
2212 Py_RETURN_NONE;
2213}
2214
Raymond Hettinger756b3f32004-01-29 06:37:52 +00002215/* module level code ********************************************************/
2216
2217PyDoc_STRVAR(module_doc,
Guido van Rossum1968ad32006-02-25 22:38:04 +00002218"High performance data structures.\n\
2219- deque: ordered collection accessible from endpoints only\n\
2220- defaultdict: dict subclass with a default value factory\n\
Raymond Hettinger756b3f32004-01-29 06:37:52 +00002221");
2222
Raymond Hettinger96f34102010-12-15 16:30:37 +00002223static struct PyMethodDef module_functions[] = {
2224 {"_count_elements", _count_elements, METH_VARARGS, _count_elements_doc},
2225 {NULL, NULL} /* sentinel */
2226};
Martin v. Löwis1a214512008-06-11 05:26:20 +00002227
2228static struct PyModuleDef _collectionsmodule = {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002229 PyModuleDef_HEAD_INIT,
2230 "_collections",
2231 module_doc,
2232 -1,
Raymond Hettinger96f34102010-12-15 16:30:37 +00002233 module_functions,
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002234 NULL,
2235 NULL,
2236 NULL,
2237 NULL
Martin v. Löwis1a214512008-06-11 05:26:20 +00002238};
2239
Raymond Hettinger756b3f32004-01-29 06:37:52 +00002240PyMODINIT_FUNC
Martin v. Löwis1a214512008-06-11 05:26:20 +00002241PyInit__collections(void)
Raymond Hettinger756b3f32004-01-29 06:37:52 +00002242{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002243 PyObject *m;
Raymond Hettinger756b3f32004-01-29 06:37:52 +00002244
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002245 m = PyModule_Create(&_collectionsmodule);
2246 if (m == NULL)
2247 return NULL;
Raymond Hettinger756b3f32004-01-29 06:37:52 +00002248
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002249 if (PyType_Ready(&deque_type) < 0)
2250 return NULL;
2251 Py_INCREF(&deque_type);
2252 PyModule_AddObject(m, "deque", (PyObject *)&deque_type);
Raymond Hettinger756b3f32004-01-29 06:37:52 +00002253
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002254 defdict_type.tp_base = &PyDict_Type;
2255 if (PyType_Ready(&defdict_type) < 0)
2256 return NULL;
2257 Py_INCREF(&defdict_type);
2258 PyModule_AddObject(m, "defaultdict", (PyObject *)&defdict_type);
Guido van Rossum1968ad32006-02-25 22:38:04 +00002259
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002260 if (PyType_Ready(&dequeiter_type) < 0)
2261 return NULL;
Kristján Valur Jónsson31668b82012-04-03 10:49:41 +00002262 Py_INCREF(&dequeiter_type);
2263 PyModule_AddObject(m, "_deque_iterator", (PyObject *)&dequeiter_type);
Raymond Hettinger756b3f32004-01-29 06:37:52 +00002264
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002265 if (PyType_Ready(&dequereviter_type) < 0)
2266 return NULL;
Kristján Valur Jónsson31668b82012-04-03 10:49:41 +00002267 Py_INCREF(&dequereviter_type);
2268 PyModule_AddObject(m, "_deque_reverse_iterator", (PyObject *)&dequereviter_type);
Raymond Hettinger1e5809f2004-03-18 11:04:57 +00002269
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00002270 return m;
Raymond Hettinger756b3f32004-01-29 06:37:52 +00002271}