blob: 2391c0d38158107169a75bf4074ea4a598c92a83 [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
4/* collections module implementation of a deque() datatype
5 Written and maintained by Raymond D. Hettinger <python@rcn.com>
6 Copyright (c) 2004 Python Software Foundation.
7 All rights reserved.
8*/
9
Raymond Hettinger77e8bf12004-10-01 15:25:53 +000010/* The block length may be set to any number over 1. Larger numbers
11 * reduce the number of calls to the memory allocator but take more
12 * memory. Ideally, BLOCKLEN should be set with an eye to the
Thomas Wouters0e3f5912006-08-11 14:57:12 +000013 * length of a cache line.
Raymond Hettinger77e8bf12004-10-01 15:25:53 +000014 */
15
Raymond Hettinger7d112df2004-11-02 02:11:35 +000016#define BLOCKLEN 62
Raymond Hettinger61f05fb2004-10-01 06:24:12 +000017#define CENTER ((BLOCKLEN - 1) / 2)
Raymond Hettinger756b3f32004-01-29 06:37:52 +000018
Tim Petersd8768d32004-10-01 01:32:53 +000019/* A `dequeobject` is composed of a doubly-linked list of `block` nodes.
20 * This list is not circular (the leftmost block has leftlink==NULL,
21 * and the rightmost block has rightlink==NULL). A deque d's first
22 * element is at d.leftblock[leftindex] and its last element is at
23 * d.rightblock[rightindex]; note that, unlike as for Python slice
Raymond Hettinger61f05fb2004-10-01 06:24:12 +000024 * indices, these indices are inclusive on both ends. By being inclusive
Thomas Wouters0e3f5912006-08-11 14:57:12 +000025 * on both ends, algorithms for left and right operations become
Raymond Hettinger61f05fb2004-10-01 06:24:12 +000026 * symmetrical which simplifies the design.
Thomas Wouters0e3f5912006-08-11 14:57:12 +000027 *
Raymond Hettinger61f05fb2004-10-01 06:24:12 +000028 * The list of blocks is never empty, so d.leftblock and d.rightblock
29 * are never equal to NULL.
30 *
31 * The indices, d.leftindex and d.rightindex are always in the range
32 * 0 <= index < BLOCKLEN.
Raymond Hettinger4ca4c7c2004-10-01 15:14:39 +000033 * Their exact relationship is:
34 * (d.leftindex + d.len - 1) % BLOCKLEN == d.rightindex.
Raymond Hettinger61f05fb2004-10-01 06:24:12 +000035 *
36 * Empty deques have d.len == 0; d.leftblock==d.rightblock;
37 * d.leftindex == CENTER+1; and d.rightindex == CENTER.
38 * Checking for d.len == 0 is the intended way to see whether d is empty.
39 *
Thomas Wouters0e3f5912006-08-11 14:57:12 +000040 * Whenever d.leftblock == d.rightblock,
Raymond Hettinger4ca4c7c2004-10-01 15:14:39 +000041 * d.leftindex + d.len - 1 == d.rightindex.
Thomas Wouters0e3f5912006-08-11 14:57:12 +000042 *
Raymond Hettinger4ca4c7c2004-10-01 15:14:39 +000043 * However, when d.leftblock != d.rightblock, d.leftindex and d.rightindex
Thomas Wouters0e3f5912006-08-11 14:57:12 +000044 * become indices into distinct blocks and either may be larger than the
Raymond Hettinger4ca4c7c2004-10-01 15:14:39 +000045 * other.
Tim Petersd8768d32004-10-01 01:32:53 +000046 */
47
Raymond Hettinger756b3f32004-01-29 06:37:52 +000048typedef struct BLOCK {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +000049 struct BLOCK *leftlink;
50 struct BLOCK *rightlink;
51 PyObject *data[BLOCKLEN];
Raymond Hettinger756b3f32004-01-29 06:37:52 +000052} block;
53
Guido van Rossum58da9312007-11-10 23:39:45 +000054#define MAXFREEBLOCKS 10
Benjamin Petersond6313712008-07-31 16:23:04 +000055static Py_ssize_t numfreeblocks = 0;
Guido van Rossum58da9312007-11-10 23:39:45 +000056static block *freeblocks[MAXFREEBLOCKS];
57
Tim Peters6f853562004-10-01 01:04:50 +000058static block *
Benjamin Petersond6313712008-07-31 16:23:04 +000059newblock(block *leftlink, block *rightlink, Py_ssize_t len) {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +000060 block *b;
61 /* To prevent len from overflowing PY_SSIZE_T_MAX on 64-bit machines, we
62 * refuse to allocate new blocks if the current len is dangerously
63 * close. There is some extra margin to prevent spurious arithmetic
64 * overflows at various places. The following check ensures that
65 * the blocks allocated to the deque, in the worst case, can only
66 * have PY_SSIZE_T_MAX-2 entries in total.
67 */
68 if (len >= PY_SSIZE_T_MAX - 2*BLOCKLEN) {
69 PyErr_SetString(PyExc_OverflowError,
70 "cannot add more blocks to the deque");
71 return NULL;
72 }
73 if (numfreeblocks) {
74 numfreeblocks -= 1;
75 b = freeblocks[numfreeblocks];
76 } else {
77 b = PyMem_Malloc(sizeof(block));
78 if (b == NULL) {
79 PyErr_NoMemory();
80 return NULL;
81 }
82 }
83 b->leftlink = leftlink;
84 b->rightlink = rightlink;
85 return b;
Raymond Hettinger756b3f32004-01-29 06:37:52 +000086}
87
Martin v. Löwis59683e82008-06-13 07:50:45 +000088static void
Guido van Rossum58da9312007-11-10 23:39:45 +000089freeblock(block *b)
90{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +000091 if (numfreeblocks < MAXFREEBLOCKS) {
92 freeblocks[numfreeblocks] = b;
93 numfreeblocks++;
94 } else {
95 PyMem_Free(b);
96 }
Guido van Rossum58da9312007-11-10 23:39:45 +000097}
98
Raymond Hettinger756b3f32004-01-29 06:37:52 +000099typedef struct {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000100 PyObject_HEAD
101 block *leftblock;
102 block *rightblock;
103 Py_ssize_t leftindex; /* in range(BLOCKLEN) */
104 Py_ssize_t rightindex; /* in range(BLOCKLEN) */
105 Py_ssize_t len;
106 Py_ssize_t maxlen;
107 long state; /* incremented whenever the indices move */
108 PyObject *weakreflist; /* List of weak references */
Raymond Hettinger756b3f32004-01-29 06:37:52 +0000109} dequeobject;
110
Guido van Rossum8ce8a782007-11-01 19:42:39 +0000111/* The deque's size limit is d.maxlen. The limit can be zero or positive.
112 * If there is no limit, then d.maxlen == -1.
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000113 *
Guido van Rossum8ce8a782007-11-01 19:42:39 +0000114 * After an item is added to a deque, we check to see if the size has grown past
115 * the limit. If it has, we get the size back down to the limit by popping an
116 * item off of the opposite end. The methods that can trigger this are append(),
117 * appendleft(), extend(), and extendleft().
118 */
119
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000120#define TRIM(d, popfunction) \
121 if (d->maxlen != -1 && d->len > d->maxlen) { \
122 PyObject *rv = popfunction(d, NULL); \
123 assert(rv != NULL && d->len <= d->maxlen); \
124 Py_DECREF(rv); \
Guido van Rossum8ce8a782007-11-01 19:42:39 +0000125 }
126
Neal Norwitz87f10132004-02-29 15:40:53 +0000127static PyTypeObject deque_type;
Raymond Hettinger738ec902004-02-29 02:15:56 +0000128
Raymond Hettinger756b3f32004-01-29 06:37:52 +0000129static PyObject *
130deque_new(PyTypeObject *type, PyObject *args, PyObject *kwds)
131{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000132 dequeobject *deque;
133 block *b;
Raymond Hettinger756b3f32004-01-29 06:37:52 +0000134
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000135 /* create dequeobject structure */
136 deque = (dequeobject *)type->tp_alloc(type, 0);
137 if (deque == NULL)
138 return NULL;
Tim Peters1065f752004-10-01 01:03:29 +0000139
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000140 b = newblock(NULL, NULL, 0);
141 if (b == NULL) {
142 Py_DECREF(deque);
143 return NULL;
144 }
Raymond Hettinger756b3f32004-01-29 06:37:52 +0000145
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000146 assert(BLOCKLEN >= 2);
147 deque->leftblock = b;
148 deque->rightblock = b;
149 deque->leftindex = CENTER + 1;
150 deque->rightindex = CENTER;
151 deque->len = 0;
152 deque->state = 0;
153 deque->weakreflist = NULL;
154 deque->maxlen = -1;
Raymond Hettinger756b3f32004-01-29 06:37:52 +0000155
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000156 return (PyObject *)deque;
Raymond Hettinger756b3f32004-01-29 06:37:52 +0000157}
158
159static PyObject *
Raymond Hettinger756b3f32004-01-29 06:37:52 +0000160deque_pop(dequeobject *deque, PyObject *unused)
161{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000162 PyObject *item;
163 block *prevblock;
Raymond Hettinger756b3f32004-01-29 06:37:52 +0000164
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000165 if (deque->len == 0) {
166 PyErr_SetString(PyExc_IndexError, "pop from an empty deque");
167 return NULL;
168 }
169 item = deque->rightblock->data[deque->rightindex];
170 deque->rightindex--;
171 deque->len--;
172 deque->state++;
Raymond Hettinger756b3f32004-01-29 06:37:52 +0000173
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000174 if (deque->rightindex == -1) {
175 if (deque->len == 0) {
176 assert(deque->leftblock == deque->rightblock);
177 assert(deque->leftindex == deque->rightindex+1);
178 /* re-center instead of freeing a block */
179 deque->leftindex = CENTER + 1;
180 deque->rightindex = CENTER;
181 } else {
182 prevblock = deque->rightblock->leftlink;
183 assert(deque->leftblock != deque->rightblock);
184 freeblock(deque->rightblock);
185 prevblock->rightlink = NULL;
186 deque->rightblock = prevblock;
187 deque->rightindex = BLOCKLEN - 1;
188 }
189 }
190 return item;
Raymond Hettinger756b3f32004-01-29 06:37:52 +0000191}
192
193PyDoc_STRVAR(pop_doc, "Remove and return the rightmost element.");
194
195static PyObject *
196deque_popleft(dequeobject *deque, PyObject *unused)
197{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000198 PyObject *item;
199 block *prevblock;
Raymond Hettinger756b3f32004-01-29 06:37:52 +0000200
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000201 if (deque->len == 0) {
202 PyErr_SetString(PyExc_IndexError, "pop from an empty deque");
203 return NULL;
204 }
205 assert(deque->leftblock != NULL);
206 item = deque->leftblock->data[deque->leftindex];
207 deque->leftindex++;
208 deque->len--;
209 deque->state++;
Raymond Hettinger756b3f32004-01-29 06:37:52 +0000210
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000211 if (deque->leftindex == BLOCKLEN) {
212 if (deque->len == 0) {
213 assert(deque->leftblock == deque->rightblock);
214 assert(deque->leftindex == deque->rightindex+1);
215 /* re-center instead of freeing a block */
216 deque->leftindex = CENTER + 1;
217 deque->rightindex = CENTER;
218 } else {
219 assert(deque->leftblock != deque->rightblock);
220 prevblock = deque->leftblock->rightlink;
221 freeblock(deque->leftblock);
222 assert(prevblock != NULL);
223 prevblock->leftlink = NULL;
224 deque->leftblock = prevblock;
225 deque->leftindex = 0;
226 }
227 }
228 return item;
Raymond Hettinger756b3f32004-01-29 06:37:52 +0000229}
230
231PyDoc_STRVAR(popleft_doc, "Remove and return the leftmost element.");
232
Raymond Hettinger3ba85c22004-02-06 19:04:56 +0000233static PyObject *
Guido van Rossum8ce8a782007-11-01 19:42:39 +0000234deque_append(dequeobject *deque, PyObject *item)
235{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000236 deque->state++;
237 if (deque->rightindex == BLOCKLEN-1) {
238 block *b = newblock(deque->rightblock, NULL, deque->len);
239 if (b == NULL)
240 return NULL;
241 assert(deque->rightblock->rightlink == NULL);
242 deque->rightblock->rightlink = b;
243 deque->rightblock = b;
244 deque->rightindex = -1;
245 }
246 Py_INCREF(item);
247 deque->len++;
248 deque->rightindex++;
249 deque->rightblock->data[deque->rightindex] = item;
250 TRIM(deque, deque_popleft);
251 Py_RETURN_NONE;
Guido van Rossum8ce8a782007-11-01 19:42:39 +0000252}
253
254PyDoc_STRVAR(append_doc, "Add an element to the right side of the deque.");
255
256static PyObject *
257deque_appendleft(dequeobject *deque, PyObject *item)
258{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000259 deque->state++;
260 if (deque->leftindex == 0) {
261 block *b = newblock(NULL, deque->leftblock, deque->len);
262 if (b == NULL)
263 return NULL;
264 assert(deque->leftblock->leftlink == NULL);
265 deque->leftblock->leftlink = b;
266 deque->leftblock = b;
267 deque->leftindex = BLOCKLEN;
268 }
269 Py_INCREF(item);
270 deque->len++;
271 deque->leftindex--;
272 deque->leftblock->data[deque->leftindex] = item;
273 TRIM(deque, deque_pop);
274 Py_RETURN_NONE;
Guido van Rossum8ce8a782007-11-01 19:42:39 +0000275}
276
277PyDoc_STRVAR(appendleft_doc, "Add an element to the left side of the deque.");
278
Raymond Hettinger060c7f62009-03-10 09:36:07 +0000279
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000280/* Run an iterator to exhaustion. Shortcut for
Raymond Hettinger060c7f62009-03-10 09:36:07 +0000281 the extend/extendleft methods when maxlen == 0. */
282static PyObject*
283consume_iterator(PyObject *it)
284{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000285 PyObject *item;
Raymond Hettinger060c7f62009-03-10 09:36:07 +0000286
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000287 while ((item = PyIter_Next(it)) != NULL) {
288 Py_DECREF(item);
289 }
290 Py_DECREF(it);
291 if (PyErr_Occurred())
292 return NULL;
293 Py_RETURN_NONE;
Raymond Hettinger060c7f62009-03-10 09:36:07 +0000294}
295
Guido van Rossum8ce8a782007-11-01 19:42:39 +0000296static PyObject *
Raymond Hettinger3ba85c22004-02-06 19:04:56 +0000297deque_extend(dequeobject *deque, PyObject *iterable)
298{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000299 PyObject *it, *item;
Raymond Hettinger3ba85c22004-02-06 19:04:56 +0000300
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000301 /* Handle case where id(deque) == id(iterable) */
302 if ((PyObject *)deque == iterable) {
303 PyObject *result;
304 PyObject *s = PySequence_List(iterable);
305 if (s == NULL)
306 return NULL;
307 result = deque_extend(deque, s);
308 Py_DECREF(s);
309 return result;
310 }
Raymond Hettinger3f9afd82009-12-10 03:03:02 +0000311
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000312 it = PyObject_GetIter(iterable);
313 if (it == NULL)
314 return NULL;
Raymond Hettinger3ba85c22004-02-06 19:04:56 +0000315
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000316 if (deque->maxlen == 0)
317 return consume_iterator(it);
Raymond Hettinger060c7f62009-03-10 09:36:07 +0000318
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000319 while ((item = PyIter_Next(it)) != NULL) {
320 deque->state++;
321 if (deque->rightindex == BLOCKLEN-1) {
322 block *b = newblock(deque->rightblock, NULL,
323 deque->len);
324 if (b == NULL) {
325 Py_DECREF(item);
326 Py_DECREF(it);
327 return NULL;
328 }
329 assert(deque->rightblock->rightlink == NULL);
330 deque->rightblock->rightlink = b;
331 deque->rightblock = b;
332 deque->rightindex = -1;
333 }
334 deque->len++;
335 deque->rightindex++;
336 deque->rightblock->data[deque->rightindex] = item;
337 TRIM(deque, deque_popleft);
338 }
339 Py_DECREF(it);
340 if (PyErr_Occurred())
341 return NULL;
342 Py_RETURN_NONE;
Raymond Hettinger3ba85c22004-02-06 19:04:56 +0000343}
344
Tim Peters1065f752004-10-01 01:03:29 +0000345PyDoc_STRVAR(extend_doc,
Raymond Hettinger3ba85c22004-02-06 19:04:56 +0000346"Extend the right side of the deque with elements from the iterable");
347
348static PyObject *
349deque_extendleft(dequeobject *deque, PyObject *iterable)
350{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000351 PyObject *it, *item;
Raymond Hettinger3ba85c22004-02-06 19:04:56 +0000352
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000353 /* Handle case where id(deque) == id(iterable) */
354 if ((PyObject *)deque == iterable) {
355 PyObject *result;
356 PyObject *s = PySequence_List(iterable);
357 if (s == NULL)
358 return NULL;
359 result = deque_extendleft(deque, s);
360 Py_DECREF(s);
361 return result;
362 }
Raymond Hettinger3f9afd82009-12-10 03:03:02 +0000363
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000364 it = PyObject_GetIter(iterable);
365 if (it == NULL)
366 return NULL;
Raymond Hettinger3ba85c22004-02-06 19:04:56 +0000367
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000368 if (deque->maxlen == 0)
369 return consume_iterator(it);
Raymond Hettinger060c7f62009-03-10 09:36:07 +0000370
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000371 while ((item = PyIter_Next(it)) != NULL) {
372 deque->state++;
373 if (deque->leftindex == 0) {
374 block *b = newblock(NULL, deque->leftblock,
375 deque->len);
376 if (b == NULL) {
377 Py_DECREF(item);
378 Py_DECREF(it);
379 return NULL;
380 }
381 assert(deque->leftblock->leftlink == NULL);
382 deque->leftblock->leftlink = b;
383 deque->leftblock = b;
384 deque->leftindex = BLOCKLEN;
385 }
386 deque->len++;
387 deque->leftindex--;
388 deque->leftblock->data[deque->leftindex] = item;
389 TRIM(deque, deque_pop);
390 }
391 Py_DECREF(it);
392 if (PyErr_Occurred())
393 return NULL;
394 Py_RETURN_NONE;
Raymond Hettinger3ba85c22004-02-06 19:04:56 +0000395}
396
Tim Peters1065f752004-10-01 01:03:29 +0000397PyDoc_STRVAR(extendleft_doc,
Raymond Hettinger3ba85c22004-02-06 19:04:56 +0000398"Extend the left side of the deque with elements from the iterable");
399
Raymond Hettinger3f9afd82009-12-10 03:03:02 +0000400static PyObject *
401deque_inplace_concat(dequeobject *deque, PyObject *other)
402{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000403 PyObject *result;
Raymond Hettinger3f9afd82009-12-10 03:03:02 +0000404
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000405 result = deque_extend(deque, other);
406 if (result == NULL)
407 return result;
408 Py_DECREF(result);
409 Py_INCREF(deque);
410 return (PyObject *)deque;
Raymond Hettinger3f9afd82009-12-10 03:03:02 +0000411}
412
Raymond Hettingerdcb9d942004-10-09 16:02:18 +0000413static int
Martin v. Löwis18e16552006-02-15 17:27:45 +0000414_deque_rotate(dequeobject *deque, Py_ssize_t n)
Raymond Hettinger5c5eb862004-02-07 21:13:00 +0000415{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000416 Py_ssize_t i, len=deque->len, halflen=(len+1)>>1;
417 PyObject *item, *rv;
Raymond Hettinger5c5eb862004-02-07 21:13:00 +0000418
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000419 if (len == 0)
420 return 0;
421 if (n > halflen || n < -halflen) {
422 n %= len;
423 if (n > halflen)
424 n -= len;
425 else if (n < -halflen)
426 n += len;
427 }
Raymond Hettinger5c5eb862004-02-07 21:13:00 +0000428
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000429 for (i=0 ; i<n ; i++) {
430 item = deque_pop(deque, NULL);
431 assert (item != NULL);
432 rv = deque_appendleft(deque, item);
433 Py_DECREF(item);
434 if (rv == NULL)
435 return -1;
436 Py_DECREF(rv);
437 }
438 for (i=0 ; i>n ; i--) {
439 item = deque_popleft(deque, NULL);
440 assert (item != NULL);
441 rv = deque_append(deque, item);
442 Py_DECREF(item);
443 if (rv == NULL)
444 return -1;
445 Py_DECREF(rv);
446 }
447 return 0;
Raymond Hettingerdcb9d942004-10-09 16:02:18 +0000448}
449
450static PyObject *
451deque_rotate(dequeobject *deque, PyObject *args)
452{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000453 Py_ssize_t n=1;
Raymond Hettingerdcb9d942004-10-09 16:02:18 +0000454
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000455 if (!PyArg_ParseTuple(args, "|n:rotate", &n))
456 return NULL;
457 if (_deque_rotate(deque, n) == 0)
458 Py_RETURN_NONE;
459 return NULL;
Raymond Hettinger5c5eb862004-02-07 21:13:00 +0000460}
461
Tim Peters1065f752004-10-01 01:03:29 +0000462PyDoc_STRVAR(rotate_doc,
Raymond Hettingeree33b272004-02-08 04:05:26 +0000463"Rotate the deque n steps to the right (default n=1). If n is negative, rotates left.");
Raymond Hettinger5c5eb862004-02-07 21:13:00 +0000464
Raymond Hettingere5fdedb2009-12-10 00:47:21 +0000465static PyObject *
466deque_reverse(dequeobject *deque, PyObject *unused)
467{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000468 block *leftblock = deque->leftblock;
469 block *rightblock = deque->rightblock;
470 Py_ssize_t leftindex = deque->leftindex;
471 Py_ssize_t rightindex = deque->rightindex;
472 Py_ssize_t n = (deque->len)/2;
473 Py_ssize_t i;
474 PyObject *tmp;
Raymond Hettingere5fdedb2009-12-10 00:47:21 +0000475
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000476 for (i=0 ; i<n ; i++) {
477 /* Validate that pointers haven't met in the middle */
478 assert(leftblock != rightblock || leftindex < rightindex);
Raymond Hettingere5fdedb2009-12-10 00:47:21 +0000479
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000480 /* Swap */
481 tmp = leftblock->data[leftindex];
482 leftblock->data[leftindex] = rightblock->data[rightindex];
483 rightblock->data[rightindex] = tmp;
Raymond Hettingere5fdedb2009-12-10 00:47:21 +0000484
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000485 /* Advance left block/index pair */
486 leftindex++;
487 if (leftindex == BLOCKLEN) {
Raymond Hettinger512d2cc2011-01-25 21:32:39 +0000488 if (leftblock->rightlink == NULL)
489 break;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000490 leftblock = leftblock->rightlink;
491 leftindex = 0;
492 }
Raymond Hettingere5fdedb2009-12-10 00:47:21 +0000493
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000494 /* Step backwards with the right block/index pair */
495 rightindex--;
496 if (rightindex == -1) {
Raymond Hettinger512d2cc2011-01-25 21:32:39 +0000497 if (rightblock->leftlink == NULL)
498 break;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000499 rightblock = rightblock->leftlink;
500 rightindex = BLOCKLEN - 1;
501 }
502 }
503 Py_RETURN_NONE;
Raymond Hettingere5fdedb2009-12-10 00:47:21 +0000504}
505
506PyDoc_STRVAR(reverse_doc,
507"D.reverse() -- reverse *IN PLACE*");
508
Raymond Hettinger44459de2010-04-03 23:20:46 +0000509static PyObject *
510deque_count(dequeobject *deque, PyObject *v)
511{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000512 block *leftblock = deque->leftblock;
513 Py_ssize_t leftindex = deque->leftindex;
Raymond Hettinger512d2cc2011-01-25 21:32:39 +0000514 Py_ssize_t n = deque->len;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000515 Py_ssize_t i;
516 Py_ssize_t count = 0;
517 PyObject *item;
518 long start_state = deque->state;
519 int cmp;
Raymond Hettinger44459de2010-04-03 23:20:46 +0000520
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000521 for (i=0 ; i<n ; i++) {
522 item = leftblock->data[leftindex];
523 cmp = PyObject_RichCompareBool(item, v, Py_EQ);
524 if (cmp > 0)
525 count++;
526 else if (cmp < 0)
527 return NULL;
Raymond Hettinger44459de2010-04-03 23:20:46 +0000528
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000529 if (start_state != deque->state) {
530 PyErr_SetString(PyExc_RuntimeError,
531 "deque mutated during iteration");
532 return NULL;
533 }
Raymond Hettinger44459de2010-04-03 23:20:46 +0000534
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000535 /* Advance left block/index pair */
536 leftindex++;
537 if (leftindex == BLOCKLEN) {
Raymond Hettinger512d2cc2011-01-25 21:32:39 +0000538 if (leftblock->rightlink == NULL) /* can occur when i==n-1 */
539 break;
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000540 leftblock = leftblock->rightlink;
541 leftindex = 0;
542 }
543 }
544 return PyLong_FromSsize_t(count);
Raymond Hettinger44459de2010-04-03 23:20:46 +0000545}
546
547PyDoc_STRVAR(count_doc,
548"D.count(value) -> integer -- return number of occurrences of value");
549
Martin v. Löwis18e16552006-02-15 17:27:45 +0000550static Py_ssize_t
Raymond Hettinger756b3f32004-01-29 06:37:52 +0000551deque_len(dequeobject *deque)
552{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000553 return deque->len;
Raymond Hettinger756b3f32004-01-29 06:37:52 +0000554}
555
Raymond Hettinger4aec61e2005-03-18 21:20:23 +0000556static PyObject *
557deque_remove(dequeobject *deque, PyObject *value)
558{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000559 Py_ssize_t i, n=deque->len;
Raymond Hettinger4aec61e2005-03-18 21:20:23 +0000560
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000561 for (i=0 ; i<n ; i++) {
562 PyObject *item = deque->leftblock->data[deque->leftindex];
563 int cmp = PyObject_RichCompareBool(item, value, Py_EQ);
Raymond Hettingerd73202c2005-03-19 00:00:51 +0000564
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000565 if (deque->len != n) {
566 PyErr_SetString(PyExc_IndexError,
567 "deque mutated during remove().");
568 return NULL;
569 }
570 if (cmp > 0) {
571 PyObject *tgt = deque_popleft(deque, NULL);
572 assert (tgt != NULL);
573 Py_DECREF(tgt);
574 if (_deque_rotate(deque, i) == -1)
575 return NULL;
576 Py_RETURN_NONE;
577 }
578 else if (cmp < 0) {
579 _deque_rotate(deque, i);
580 return NULL;
581 }
582 _deque_rotate(deque, -1);
583 }
584 PyErr_SetString(PyExc_ValueError, "deque.remove(x): x not in deque");
585 return NULL;
Raymond Hettinger4aec61e2005-03-18 21:20:23 +0000586}
587
588PyDoc_STRVAR(remove_doc,
589"D.remove(value) -- remove first occurrence of value.");
590
Raymond Hettinger756b3f32004-01-29 06:37:52 +0000591static int
592deque_clear(dequeobject *deque)
593{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000594 PyObject *item;
Raymond Hettinger756b3f32004-01-29 06:37:52 +0000595
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000596 while (deque->len) {
597 item = deque_pop(deque, NULL);
598 assert (item != NULL);
599 Py_DECREF(item);
600 }
601 assert(deque->leftblock == deque->rightblock &&
602 deque->leftindex - 1 == deque->rightindex &&
603 deque->len == 0);
604 return 0;
Raymond Hettinger756b3f32004-01-29 06:37:52 +0000605}
606
607static PyObject *
Benjamin Petersond6313712008-07-31 16:23:04 +0000608deque_item(dequeobject *deque, Py_ssize_t i)
Raymond Hettinger0a4977c2004-03-01 23:16:22 +0000609{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000610 block *b;
611 PyObject *item;
612 Py_ssize_t n, index=i;
Raymond Hettinger0a4977c2004-03-01 23:16:22 +0000613
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000614 if (i < 0 || i >= deque->len) {
615 PyErr_SetString(PyExc_IndexError,
616 "deque index out of range");
617 return NULL;
618 }
Raymond Hettinger0a4977c2004-03-01 23:16:22 +0000619
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000620 if (i == 0) {
621 i = deque->leftindex;
622 b = deque->leftblock;
623 } else if (i == deque->len - 1) {
624 i = deque->rightindex;
625 b = deque->rightblock;
626 } else {
627 i += deque->leftindex;
628 n = i / BLOCKLEN;
629 i %= BLOCKLEN;
630 if (index < (deque->len >> 1)) {
631 b = deque->leftblock;
632 while (n--)
633 b = b->rightlink;
634 } else {
635 n = (deque->leftindex + deque->len - 1) / BLOCKLEN - n;
636 b = deque->rightblock;
637 while (n--)
638 b = b->leftlink;
639 }
640 }
641 item = b->data[i];
642 Py_INCREF(item);
643 return item;
Raymond Hettinger0a4977c2004-03-01 23:16:22 +0000644}
645
Raymond Hettinger616f4f62004-06-26 04:42:06 +0000646/* delitem() implemented in terms of rotate for simplicity and reasonable
647 performance near the end points. If for some reason this method becomes
Tim Peters1065f752004-10-01 01:03:29 +0000648 popular, it is not hard to re-implement this using direct data movement
Raymond Hettinger616f4f62004-06-26 04:42:06 +0000649 (similar to code in list slice assignment) and achieve a two or threefold
650 performance boost.
651*/
652
Raymond Hettinger0a4977c2004-03-01 23:16:22 +0000653static int
Martin v. Löwis18e16552006-02-15 17:27:45 +0000654deque_del_item(dequeobject *deque, Py_ssize_t i)
Raymond Hettinger0e371f22004-05-12 20:55:56 +0000655{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000656 PyObject *item;
Raymond Hettinger0e371f22004-05-12 20:55:56 +0000657
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000658 assert (i >= 0 && i < deque->len);
659 if (_deque_rotate(deque, -i) == -1)
660 return -1;
Raymond Hettinger0e371f22004-05-12 20:55:56 +0000661
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000662 item = deque_popleft(deque, NULL);
663 assert (item != NULL);
664 Py_DECREF(item);
Raymond Hettinger0e371f22004-05-12 20:55:56 +0000665
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000666 return _deque_rotate(deque, i);
Raymond Hettinger0e371f22004-05-12 20:55:56 +0000667}
668
669static int
Martin v. Löwis18e16552006-02-15 17:27:45 +0000670deque_ass_item(dequeobject *deque, Py_ssize_t i, PyObject *v)
Raymond Hettinger0a4977c2004-03-01 23:16:22 +0000671{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000672 PyObject *old_value;
673 block *b;
674 Py_ssize_t n, len=deque->len, halflen=(len+1)>>1, index=i;
Raymond Hettinger0a4977c2004-03-01 23:16:22 +0000675
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000676 if (i < 0 || i >= len) {
677 PyErr_SetString(PyExc_IndexError,
678 "deque index out of range");
679 return -1;
680 }
681 if (v == NULL)
682 return deque_del_item(deque, i);
Raymond Hettinger0e371f22004-05-12 20:55:56 +0000683
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000684 i += deque->leftindex;
685 n = i / BLOCKLEN;
686 i %= BLOCKLEN;
687 if (index <= halflen) {
688 b = deque->leftblock;
689 while (n--)
690 b = b->rightlink;
691 } else {
692 n = (deque->leftindex + len - 1) / BLOCKLEN - n;
693 b = deque->rightblock;
694 while (n--)
695 b = b->leftlink;
696 }
697 Py_INCREF(v);
698 old_value = b->data[i];
699 b->data[i] = v;
700 Py_DECREF(old_value);
701 return 0;
Raymond Hettinger0a4977c2004-03-01 23:16:22 +0000702}
703
704static PyObject *
Raymond Hettinger756b3f32004-01-29 06:37:52 +0000705deque_clearmethod(dequeobject *deque)
706{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000707 int rv;
Raymond Hettingera435c532004-07-09 04:10:20 +0000708
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000709 rv = deque_clear(deque);
710 assert (rv != -1);
711 Py_RETURN_NONE;
Raymond Hettinger756b3f32004-01-29 06:37:52 +0000712}
713
714PyDoc_STRVAR(clear_doc, "Remove all elements from the deque.");
715
716static void
717deque_dealloc(dequeobject *deque)
718{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000719 PyObject_GC_UnTrack(deque);
720 if (deque->weakreflist != NULL)
721 PyObject_ClearWeakRefs((PyObject *) deque);
722 if (deque->leftblock != NULL) {
723 deque_clear(deque);
724 assert(deque->leftblock != NULL);
725 freeblock(deque->leftblock);
726 }
727 deque->leftblock = NULL;
728 deque->rightblock = NULL;
729 Py_TYPE(deque)->tp_free(deque);
Raymond Hettinger756b3f32004-01-29 06:37:52 +0000730}
731
732static int
Raymond Hettinger0a4977c2004-03-01 23:16:22 +0000733deque_traverse(dequeobject *deque, visitproc visit, void *arg)
Raymond Hettinger756b3f32004-01-29 06:37:52 +0000734{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000735 block *b;
736 PyObject *item;
737 Py_ssize_t index;
738 Py_ssize_t indexlo = deque->leftindex;
Raymond Hettinger756b3f32004-01-29 06:37:52 +0000739
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000740 for (b = deque->leftblock; b != NULL; b = b->rightlink) {
741 const Py_ssize_t indexhi = b == deque->rightblock ?
742 deque->rightindex :
743 BLOCKLEN - 1;
Tim Peters10c7e862004-10-01 02:01:04 +0000744
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000745 for (index = indexlo; index <= indexhi; ++index) {
746 item = b->data[index];
747 Py_VISIT(item);
748 }
749 indexlo = 0;
750 }
751 return 0;
Raymond Hettinger756b3f32004-01-29 06:37:52 +0000752}
753
Raymond Hettinger756b3f32004-01-29 06:37:52 +0000754static PyObject *
755deque_copy(PyObject *deque)
756{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000757 if (((dequeobject *)deque)->maxlen == -1)
758 return PyObject_CallFunction((PyObject *)(Py_TYPE(deque)), "O", deque, NULL);
759 else
760 return PyObject_CallFunction((PyObject *)(Py_TYPE(deque)), "Oi",
761 deque, ((dequeobject *)deque)->maxlen, NULL);
Raymond Hettinger756b3f32004-01-29 06:37:52 +0000762}
763
764PyDoc_STRVAR(copy_doc, "Return a shallow copy of a deque.");
765
766static PyObject *
767deque_reduce(dequeobject *deque)
768{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000769 PyObject *dict, *result, *aslist;
Raymond Hettinger756b3f32004-01-29 06:37:52 +0000770
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000771 dict = PyObject_GetAttrString((PyObject *)deque, "__dict__");
772 if (dict == NULL)
773 PyErr_Clear();
774 aslist = PySequence_List((PyObject *)deque);
775 if (aslist == NULL) {
776 Py_XDECREF(dict);
777 return NULL;
778 }
779 if (dict == NULL) {
780 if (deque->maxlen == -1)
781 result = Py_BuildValue("O(O)", Py_TYPE(deque), aslist);
782 else
783 result = Py_BuildValue("O(On)", Py_TYPE(deque), aslist, deque->maxlen);
784 } else {
785 if (deque->maxlen == -1)
786 result = Py_BuildValue("O(OO)O", Py_TYPE(deque), aslist, Py_None, dict);
787 else
788 result = Py_BuildValue("O(On)O", Py_TYPE(deque), aslist, deque->maxlen, dict);
789 }
790 Py_XDECREF(dict);
791 Py_DECREF(aslist);
792 return result;
Raymond Hettinger756b3f32004-01-29 06:37:52 +0000793}
794
795PyDoc_STRVAR(reduce_doc, "Return state information for pickling.");
796
797static PyObject *
798deque_repr(PyObject *deque)
799{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000800 PyObject *aslist, *result;
801 int i;
Raymond Hettinger756b3f32004-01-29 06:37:52 +0000802
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000803 i = Py_ReprEnter(deque);
804 if (i != 0) {
805 if (i < 0)
806 return NULL;
807 return PyUnicode_FromString("[...]");
808 }
Raymond Hettinger756b3f32004-01-29 06:37:52 +0000809
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000810 aslist = PySequence_List(deque);
811 if (aslist == NULL) {
812 Py_ReprLeave(deque);
813 return NULL;
814 }
815 if (((dequeobject *)deque)->maxlen != -1)
Benjamin Petersona786b022008-08-25 21:05:21 +0000816
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000817 result = PyUnicode_FromFormat("deque(%R, maxlen=%zd)",
818 aslist, ((dequeobject *)deque)->maxlen);
819 else
820 result = PyUnicode_FromFormat("deque(%R)", aslist);
821 Py_DECREF(aslist);
822 Py_ReprLeave(deque);
823 return result;
Raymond Hettinger756b3f32004-01-29 06:37:52 +0000824}
825
Raymond Hettinger738ec902004-02-29 02:15:56 +0000826static PyObject *
827deque_richcompare(PyObject *v, PyObject *w, int op)
828{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000829 PyObject *it1=NULL, *it2=NULL, *x, *y;
830 Py_ssize_t vs, ws;
831 int b, cmp=-1;
Raymond Hettinger738ec902004-02-29 02:15:56 +0000832
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000833 if (!PyObject_TypeCheck(v, &deque_type) ||
834 !PyObject_TypeCheck(w, &deque_type)) {
835 Py_INCREF(Py_NotImplemented);
836 return Py_NotImplemented;
837 }
Raymond Hettinger738ec902004-02-29 02:15:56 +0000838
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000839 /* Shortcuts */
840 vs = ((dequeobject *)v)->len;
841 ws = ((dequeobject *)w)->len;
842 if (op == Py_EQ) {
843 if (v == w)
844 Py_RETURN_TRUE;
845 if (vs != ws)
846 Py_RETURN_FALSE;
847 }
848 if (op == Py_NE) {
849 if (v == w)
850 Py_RETURN_FALSE;
851 if (vs != ws)
852 Py_RETURN_TRUE;
853 }
Raymond Hettinger738ec902004-02-29 02:15:56 +0000854
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000855 /* Search for the first index where items are different */
856 it1 = PyObject_GetIter(v);
857 if (it1 == NULL)
858 goto done;
859 it2 = PyObject_GetIter(w);
860 if (it2 == NULL)
861 goto done;
862 for (;;) {
863 x = PyIter_Next(it1);
864 if (x == NULL && PyErr_Occurred())
865 goto done;
866 y = PyIter_Next(it2);
867 if (x == NULL || y == NULL)
868 break;
869 b = PyObject_RichCompareBool(x, y, Py_EQ);
870 if (b == 0) {
871 cmp = PyObject_RichCompareBool(x, y, op);
872 Py_DECREF(x);
873 Py_DECREF(y);
874 goto done;
875 }
876 Py_DECREF(x);
877 Py_DECREF(y);
878 if (b == -1)
879 goto done;
880 }
881 /* We reached the end of one deque or both */
882 Py_XDECREF(x);
883 Py_XDECREF(y);
884 if (PyErr_Occurred())
885 goto done;
886 switch (op) {
887 case Py_LT: cmp = y != NULL; break; /* if w was longer */
888 case Py_LE: cmp = x == NULL; break; /* if v was not longer */
889 case Py_EQ: cmp = x == y; break; /* if we reached the end of both */
890 case Py_NE: cmp = x != y; break; /* if one deque continues */
891 case Py_GT: cmp = x != NULL; break; /* if v was longer */
892 case Py_GE: cmp = y == NULL; break; /* if w was not longer */
893 }
Tim Peters1065f752004-10-01 01:03:29 +0000894
Raymond Hettinger738ec902004-02-29 02:15:56 +0000895done:
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000896 Py_XDECREF(it1);
897 Py_XDECREF(it2);
898 if (cmp == 1)
899 Py_RETURN_TRUE;
900 if (cmp == 0)
901 Py_RETURN_FALSE;
902 return NULL;
Raymond Hettinger738ec902004-02-29 02:15:56 +0000903}
904
Raymond Hettinger756b3f32004-01-29 06:37:52 +0000905static int
Guido van Rossum8ce8a782007-11-01 19:42:39 +0000906deque_init(dequeobject *deque, PyObject *args, PyObject *kwdargs)
Raymond Hettinger756b3f32004-01-29 06:37:52 +0000907{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000908 PyObject *iterable = NULL;
909 PyObject *maxlenobj = NULL;
910 Py_ssize_t maxlen = -1;
911 char *kwlist[] = {"iterable", "maxlen", 0};
Raymond Hettinger756b3f32004-01-29 06:37:52 +0000912
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000913 if (!PyArg_ParseTupleAndKeywords(args, kwdargs, "|OO:deque", kwlist, &iterable, &maxlenobj))
914 return -1;
915 if (maxlenobj != NULL && maxlenobj != Py_None) {
916 maxlen = PyLong_AsSsize_t(maxlenobj);
917 if (maxlen == -1 && PyErr_Occurred())
918 return -1;
919 if (maxlen < 0) {
920 PyErr_SetString(PyExc_ValueError, "maxlen must be non-negative");
921 return -1;
922 }
923 }
924 deque->maxlen = maxlen;
925 deque_clear(deque);
926 if (iterable != NULL) {
927 PyObject *rv = deque_extend(deque, iterable);
928 if (rv == NULL)
929 return -1;
930 Py_DECREF(rv);
931 }
932 return 0;
Raymond Hettinger756b3f32004-01-29 06:37:52 +0000933}
934
Raymond Hettinger5bb0f0e2009-03-10 12:56:32 +0000935static PyObject *
936deque_get_maxlen(dequeobject *deque)
937{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000938 if (deque->maxlen == -1)
939 Py_RETURN_NONE;
940 return PyLong_FromSsize_t(deque->maxlen);
Raymond Hettinger5bb0f0e2009-03-10 12:56:32 +0000941}
942
943static PyGetSetDef deque_getset[] = {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000944 {"maxlen", (getter)deque_get_maxlen, (setter)NULL,
945 "maximum size of a deque or None if unbounded"},
946 {0}
Raymond Hettinger5bb0f0e2009-03-10 12:56:32 +0000947};
948
Raymond Hettinger756b3f32004-01-29 06:37:52 +0000949static PySequenceMethods deque_as_sequence = {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000950 (lenfunc)deque_len, /* sq_length */
951 0, /* sq_concat */
952 0, /* sq_repeat */
953 (ssizeargfunc)deque_item, /* sq_item */
954 0, /* sq_slice */
955 (ssizeobjargproc)deque_ass_item, /* sq_ass_item */
956 0, /* sq_ass_slice */
957 0, /* sq_contains */
958 (binaryfunc)deque_inplace_concat, /* sq_inplace_concat */
959 0, /* sq_inplace_repeat */
Raymond Hettinger3f9afd82009-12-10 03:03:02 +0000960
Raymond Hettinger756b3f32004-01-29 06:37:52 +0000961};
962
963/* deque object ********************************************************/
964
965static PyObject *deque_iter(dequeobject *deque);
Raymond Hettinger1e5809f2004-03-18 11:04:57 +0000966static PyObject *deque_reviter(dequeobject *deque);
Tim Peters1065f752004-10-01 01:03:29 +0000967PyDoc_STRVAR(reversed_doc,
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000968 "D.__reversed__() -- return a reverse iterator over the deque");
Raymond Hettinger756b3f32004-01-29 06:37:52 +0000969
970static PyMethodDef deque_methods[] = {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +0000971 {"append", (PyCFunction)deque_append,
972 METH_O, append_doc},
973 {"appendleft", (PyCFunction)deque_appendleft,
974 METH_O, appendleft_doc},
975 {"clear", (PyCFunction)deque_clearmethod,
976 METH_NOARGS, clear_doc},
977 {"__copy__", (PyCFunction)deque_copy,
978 METH_NOARGS, copy_doc},
979 {"count", (PyCFunction)deque_count,
980 METH_O, count_doc},
981 {"extend", (PyCFunction)deque_extend,
982 METH_O, extend_doc},
983 {"extendleft", (PyCFunction)deque_extendleft,
984 METH_O, extendleft_doc},
985 {"pop", (PyCFunction)deque_pop,
986 METH_NOARGS, pop_doc},
987 {"popleft", (PyCFunction)deque_popleft,
988 METH_NOARGS, popleft_doc},
989 {"__reduce__", (PyCFunction)deque_reduce,
990 METH_NOARGS, reduce_doc},
991 {"remove", (PyCFunction)deque_remove,
992 METH_O, remove_doc},
993 {"__reversed__", (PyCFunction)deque_reviter,
994 METH_NOARGS, reversed_doc},
995 {"reverse", (PyCFunction)deque_reverse,
996 METH_NOARGS, reverse_doc},
997 {"rotate", (PyCFunction)deque_rotate,
998 METH_VARARGS, rotate_doc},
999 {NULL, NULL} /* sentinel */
Raymond Hettinger756b3f32004-01-29 06:37:52 +00001000};
1001
1002PyDoc_STRVAR(deque_doc,
Guido van Rossum8ce8a782007-11-01 19:42:39 +00001003"deque(iterable[, maxlen]) --> deque object\n\
Raymond Hettinger756b3f32004-01-29 06:37:52 +00001004\n\
1005Build an ordered collection accessible from endpoints only.");
1006
Neal Norwitz87f10132004-02-29 15:40:53 +00001007static PyTypeObject deque_type = {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001008 PyVarObject_HEAD_INIT(NULL, 0)
1009 "collections.deque", /* tp_name */
1010 sizeof(dequeobject), /* tp_basicsize */
1011 0, /* tp_itemsize */
1012 /* methods */
1013 (destructor)deque_dealloc, /* tp_dealloc */
1014 0, /* tp_print */
1015 0, /* tp_getattr */
1016 0, /* tp_setattr */
1017 0, /* tp_reserved */
1018 deque_repr, /* tp_repr */
1019 0, /* tp_as_number */
1020 &deque_as_sequence, /* tp_as_sequence */
1021 0, /* tp_as_mapping */
Georg Brandlf038b322010-10-18 07:35:09 +00001022 PyObject_HashNotImplemented, /* tp_hash */
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001023 0, /* tp_call */
1024 0, /* tp_str */
1025 PyObject_GenericGetAttr, /* tp_getattro */
1026 0, /* tp_setattro */
1027 0, /* tp_as_buffer */
1028 Py_TPFLAGS_DEFAULT | Py_TPFLAGS_BASETYPE | Py_TPFLAGS_HAVE_GC,
Georg Brandlf038b322010-10-18 07:35:09 +00001029 /* tp_flags */
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001030 deque_doc, /* tp_doc */
1031 (traverseproc)deque_traverse, /* tp_traverse */
1032 (inquiry)deque_clear, /* tp_clear */
1033 (richcmpfunc)deque_richcompare, /* tp_richcompare */
Georg Brandlf038b322010-10-18 07:35:09 +00001034 offsetof(dequeobject, weakreflist), /* tp_weaklistoffset*/
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001035 (getiterfunc)deque_iter, /* tp_iter */
1036 0, /* tp_iternext */
1037 deque_methods, /* tp_methods */
1038 0, /* tp_members */
Georg Brandlf038b322010-10-18 07:35:09 +00001039 deque_getset, /* tp_getset */
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001040 0, /* tp_base */
1041 0, /* tp_dict */
1042 0, /* tp_descr_get */
1043 0, /* tp_descr_set */
1044 0, /* tp_dictoffset */
1045 (initproc)deque_init, /* tp_init */
1046 PyType_GenericAlloc, /* tp_alloc */
1047 deque_new, /* tp_new */
1048 PyObject_GC_Del, /* tp_free */
Raymond Hettinger756b3f32004-01-29 06:37:52 +00001049};
1050
1051/*********************** Deque Iterator **************************/
1052
1053typedef struct {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001054 PyObject_HEAD
1055 Py_ssize_t index;
1056 block *b;
1057 dequeobject *deque;
1058 long state; /* state when the iterator is created */
1059 Py_ssize_t counter; /* number of items remaining for iteration */
Raymond Hettinger756b3f32004-01-29 06:37:52 +00001060} dequeiterobject;
1061
Martin v. Löwis59683e82008-06-13 07:50:45 +00001062static PyTypeObject dequeiter_type;
Raymond Hettinger756b3f32004-01-29 06:37:52 +00001063
1064static PyObject *
1065deque_iter(dequeobject *deque)
1066{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001067 dequeiterobject *it;
Raymond Hettinger756b3f32004-01-29 06:37:52 +00001068
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001069 it = PyObject_GC_New(dequeiterobject, &dequeiter_type);
1070 if (it == NULL)
1071 return NULL;
1072 it->b = deque->leftblock;
1073 it->index = deque->leftindex;
1074 Py_INCREF(deque);
1075 it->deque = deque;
1076 it->state = deque->state;
1077 it->counter = deque->len;
1078 PyObject_GC_Track(it);
1079 return (PyObject *)it;
Raymond Hettinger756b3f32004-01-29 06:37:52 +00001080}
1081
Antoine Pitrou7ddda782009-01-01 15:35:33 +00001082static int
1083dequeiter_traverse(dequeiterobject *dio, visitproc visit, void *arg)
1084{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001085 Py_VISIT(dio->deque);
1086 return 0;
Antoine Pitrou7ddda782009-01-01 15:35:33 +00001087}
1088
Raymond Hettinger756b3f32004-01-29 06:37:52 +00001089static void
1090dequeiter_dealloc(dequeiterobject *dio)
1091{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001092 Py_XDECREF(dio->deque);
1093 PyObject_GC_Del(dio);
Raymond Hettinger756b3f32004-01-29 06:37:52 +00001094}
1095
1096static PyObject *
1097dequeiter_next(dequeiterobject *it)
1098{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001099 PyObject *item;
Raymond Hettingerd1b3d882004-10-02 00:43:13 +00001100
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001101 if (it->deque->state != it->state) {
1102 it->counter = 0;
1103 PyErr_SetString(PyExc_RuntimeError,
1104 "deque mutated during iteration");
1105 return NULL;
1106 }
1107 if (it->counter == 0)
1108 return NULL;
1109 assert (!(it->b == it->deque->rightblock &&
1110 it->index > it->deque->rightindex));
Raymond Hettinger756b3f32004-01-29 06:37:52 +00001111
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001112 item = it->b->data[it->index];
1113 it->index++;
1114 it->counter--;
1115 if (it->index == BLOCKLEN && it->counter > 0) {
1116 assert (it->b->rightlink != NULL);
1117 it->b = it->b->rightlink;
1118 it->index = 0;
1119 }
1120 Py_INCREF(item);
1121 return item;
Raymond Hettinger756b3f32004-01-29 06:37:52 +00001122}
1123
Raymond Hettinger6b27cda2005-09-24 21:23:05 +00001124static PyObject *
Raymond Hettinger1e5809f2004-03-18 11:04:57 +00001125dequeiter_len(dequeiterobject *it)
1126{
Antoine Pitrou554f3342010-08-17 18:30:06 +00001127 return PyLong_FromSsize_t(it->counter);
Raymond Hettinger1e5809f2004-03-18 11:04:57 +00001128}
1129
Armin Rigof5b3e362006-02-11 21:32:43 +00001130PyDoc_STRVAR(length_hint_doc, "Private method returning an estimate of len(list(it)).");
Raymond Hettinger6b27cda2005-09-24 21:23:05 +00001131
1132static PyMethodDef dequeiter_methods[] = {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001133 {"__length_hint__", (PyCFunction)dequeiter_len, METH_NOARGS, length_hint_doc},
1134 {NULL, NULL} /* sentinel */
Raymond Hettinger1e5809f2004-03-18 11:04:57 +00001135};
1136
Martin v. Löwis59683e82008-06-13 07:50:45 +00001137static PyTypeObject dequeiter_type = {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001138 PyVarObject_HEAD_INIT(NULL, 0)
1139 "deque_iterator", /* tp_name */
1140 sizeof(dequeiterobject), /* tp_basicsize */
1141 0, /* tp_itemsize */
1142 /* methods */
1143 (destructor)dequeiter_dealloc, /* tp_dealloc */
1144 0, /* tp_print */
1145 0, /* tp_getattr */
1146 0, /* tp_setattr */
1147 0, /* tp_reserved */
1148 0, /* tp_repr */
1149 0, /* tp_as_number */
1150 0, /* tp_as_sequence */
1151 0, /* tp_as_mapping */
1152 0, /* tp_hash */
1153 0, /* tp_call */
1154 0, /* tp_str */
1155 PyObject_GenericGetAttr, /* tp_getattro */
1156 0, /* tp_setattro */
1157 0, /* tp_as_buffer */
1158 Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC,/* tp_flags */
1159 0, /* tp_doc */
1160 (traverseproc)dequeiter_traverse, /* tp_traverse */
1161 0, /* tp_clear */
1162 0, /* tp_richcompare */
1163 0, /* tp_weaklistoffset */
1164 PyObject_SelfIter, /* tp_iter */
1165 (iternextfunc)dequeiter_next, /* tp_iternext */
1166 dequeiter_methods, /* tp_methods */
1167 0,
Raymond Hettinger756b3f32004-01-29 06:37:52 +00001168};
1169
Raymond Hettinger1e5809f2004-03-18 11:04:57 +00001170/*********************** Deque Reverse Iterator **************************/
1171
Martin v. Löwis59683e82008-06-13 07:50:45 +00001172static PyTypeObject dequereviter_type;
Raymond Hettinger1e5809f2004-03-18 11:04:57 +00001173
1174static PyObject *
1175deque_reviter(dequeobject *deque)
1176{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001177 dequeiterobject *it;
Raymond Hettinger1e5809f2004-03-18 11:04:57 +00001178
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001179 it = PyObject_GC_New(dequeiterobject, &dequereviter_type);
1180 if (it == NULL)
1181 return NULL;
1182 it->b = deque->rightblock;
1183 it->index = deque->rightindex;
1184 Py_INCREF(deque);
1185 it->deque = deque;
1186 it->state = deque->state;
1187 it->counter = deque->len;
1188 PyObject_GC_Track(it);
1189 return (PyObject *)it;
Raymond Hettinger1e5809f2004-03-18 11:04:57 +00001190}
1191
1192static PyObject *
1193dequereviter_next(dequeiterobject *it)
1194{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001195 PyObject *item;
1196 if (it->counter == 0)
1197 return NULL;
Raymond Hettinger1e5809f2004-03-18 11:04:57 +00001198
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001199 if (it->deque->state != it->state) {
1200 it->counter = 0;
1201 PyErr_SetString(PyExc_RuntimeError,
1202 "deque mutated during iteration");
1203 return NULL;
1204 }
1205 assert (!(it->b == it->deque->leftblock &&
1206 it->index < it->deque->leftindex));
Raymond Hettinger1e5809f2004-03-18 11:04:57 +00001207
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001208 item = it->b->data[it->index];
1209 it->index--;
1210 it->counter--;
1211 if (it->index == -1 && it->counter > 0) {
1212 assert (it->b->leftlink != NULL);
1213 it->b = it->b->leftlink;
1214 it->index = BLOCKLEN - 1;
1215 }
1216 Py_INCREF(item);
1217 return item;
Raymond Hettinger1e5809f2004-03-18 11:04:57 +00001218}
1219
Martin v. Löwis59683e82008-06-13 07:50:45 +00001220static PyTypeObject dequereviter_type = {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001221 PyVarObject_HEAD_INIT(NULL, 0)
1222 "deque_reverse_iterator", /* tp_name */
1223 sizeof(dequeiterobject), /* tp_basicsize */
1224 0, /* tp_itemsize */
1225 /* methods */
1226 (destructor)dequeiter_dealloc, /* tp_dealloc */
1227 0, /* tp_print */
1228 0, /* tp_getattr */
1229 0, /* tp_setattr */
1230 0, /* tp_reserved */
1231 0, /* tp_repr */
1232 0, /* tp_as_number */
1233 0, /* tp_as_sequence */
1234 0, /* tp_as_mapping */
1235 0, /* tp_hash */
1236 0, /* tp_call */
1237 0, /* tp_str */
1238 PyObject_GenericGetAttr, /* tp_getattro */
1239 0, /* tp_setattro */
1240 0, /* tp_as_buffer */
1241 Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC,/* tp_flags */
1242 0, /* tp_doc */
1243 (traverseproc)dequeiter_traverse, /* tp_traverse */
1244 0, /* tp_clear */
1245 0, /* tp_richcompare */
1246 0, /* tp_weaklistoffset */
1247 PyObject_SelfIter, /* tp_iter */
1248 (iternextfunc)dequereviter_next, /* tp_iternext */
1249 dequeiter_methods, /* tp_methods */
1250 0,
Raymond Hettinger1e5809f2004-03-18 11:04:57 +00001251};
1252
Guido van Rossum1968ad32006-02-25 22:38:04 +00001253/* defaultdict type *********************************************************/
1254
1255typedef struct {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001256 PyDictObject dict;
1257 PyObject *default_factory;
Guido van Rossum1968ad32006-02-25 22:38:04 +00001258} defdictobject;
1259
1260static PyTypeObject defdict_type; /* Forward */
1261
1262PyDoc_STRVAR(defdict_missing_doc,
1263"__missing__(key) # Called by __getitem__ for missing key; pseudo-code:\n\
Guido van Rossumd8faa362007-04-27 19:54:29 +00001264 if self.default_factory is None: raise KeyError((key,))\n\
Guido van Rossum1968ad32006-02-25 22:38:04 +00001265 self[key] = value = self.default_factory()\n\
1266 return value\n\
1267");
1268
1269static PyObject *
1270defdict_missing(defdictobject *dd, PyObject *key)
1271{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001272 PyObject *factory = dd->default_factory;
1273 PyObject *value;
1274 if (factory == NULL || factory == Py_None) {
1275 /* XXX Call dict.__missing__(key) */
1276 PyObject *tup;
1277 tup = PyTuple_Pack(1, key);
1278 if (!tup) return NULL;
1279 PyErr_SetObject(PyExc_KeyError, tup);
1280 Py_DECREF(tup);
1281 return NULL;
1282 }
1283 value = PyEval_CallObject(factory, NULL);
1284 if (value == NULL)
1285 return value;
1286 if (PyObject_SetItem((PyObject *)dd, key, value) < 0) {
1287 Py_DECREF(value);
1288 return NULL;
1289 }
1290 return value;
Guido van Rossum1968ad32006-02-25 22:38:04 +00001291}
1292
1293PyDoc_STRVAR(defdict_copy_doc, "D.copy() -> a shallow copy of D.");
1294
1295static PyObject *
1296defdict_copy(defdictobject *dd)
1297{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001298 /* This calls the object's class. That only works for subclasses
1299 whose class constructor has the same signature. Subclasses that
1300 define a different constructor signature must override copy().
1301 */
Raymond Hettinger54628fa2009-08-04 19:16:39 +00001302
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001303 if (dd->default_factory == NULL)
1304 return PyObject_CallFunctionObjArgs((PyObject*)Py_TYPE(dd), Py_None, dd, NULL);
1305 return PyObject_CallFunctionObjArgs((PyObject*)Py_TYPE(dd),
1306 dd->default_factory, dd, NULL);
Guido van Rossum1968ad32006-02-25 22:38:04 +00001307}
1308
1309static PyObject *
1310defdict_reduce(defdictobject *dd)
1311{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001312 /* __reduce__ must return a 5-tuple as follows:
Guido van Rossum1968ad32006-02-25 22:38:04 +00001313
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001314 - factory function
1315 - tuple of args for the factory function
1316 - additional state (here None)
1317 - sequence iterator (here None)
1318 - dictionary iterator (yielding successive (key, value) pairs
Guido van Rossum1968ad32006-02-25 22:38:04 +00001319
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001320 This API is used by pickle.py and copy.py.
Guido van Rossum1968ad32006-02-25 22:38:04 +00001321
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001322 For this to be useful with pickle.py, the default_factory
1323 must be picklable; e.g., None, a built-in, or a global
1324 function in a module or package.
Guido van Rossum1968ad32006-02-25 22:38:04 +00001325
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001326 Both shallow and deep copying are supported, but for deep
1327 copying, the default_factory must be deep-copyable; e.g. None,
1328 or a built-in (functions are not copyable at this time).
Guido van Rossum1968ad32006-02-25 22:38:04 +00001329
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001330 This only works for subclasses as long as their constructor
1331 signature is compatible; the first argument must be the
1332 optional default_factory, defaulting to None.
1333 */
1334 PyObject *args;
1335 PyObject *items;
1336 PyObject *iter;
1337 PyObject *result;
1338 if (dd->default_factory == NULL || dd->default_factory == Py_None)
1339 args = PyTuple_New(0);
1340 else
1341 args = PyTuple_Pack(1, dd->default_factory);
1342 if (args == NULL)
1343 return NULL;
1344 items = PyObject_CallMethod((PyObject *)dd, "items", "()");
1345 if (items == NULL) {
1346 Py_DECREF(args);
1347 return NULL;
1348 }
1349 iter = PyObject_GetIter(items);
1350 if (iter == NULL) {
1351 Py_DECREF(items);
1352 Py_DECREF(args);
1353 return NULL;
1354 }
1355 result = PyTuple_Pack(5, Py_TYPE(dd), args,
1356 Py_None, Py_None, iter);
1357 Py_DECREF(iter);
1358 Py_DECREF(items);
1359 Py_DECREF(args);
1360 return result;
Guido van Rossum1968ad32006-02-25 22:38:04 +00001361}
1362
1363static PyMethodDef defdict_methods[] = {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001364 {"__missing__", (PyCFunction)defdict_missing, METH_O,
1365 defdict_missing_doc},
1366 {"copy", (PyCFunction)defdict_copy, METH_NOARGS,
1367 defdict_copy_doc},
1368 {"__copy__", (PyCFunction)defdict_copy, METH_NOARGS,
1369 defdict_copy_doc},
1370 {"__reduce__", (PyCFunction)defdict_reduce, METH_NOARGS,
1371 reduce_doc},
1372 {NULL}
Guido van Rossum1968ad32006-02-25 22:38:04 +00001373};
1374
1375static PyMemberDef defdict_members[] = {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001376 {"default_factory", T_OBJECT,
1377 offsetof(defdictobject, default_factory), 0,
1378 PyDoc_STR("Factory for default value called by __missing__().")},
1379 {NULL}
Guido van Rossum1968ad32006-02-25 22:38:04 +00001380};
1381
1382static void
1383defdict_dealloc(defdictobject *dd)
1384{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001385 Py_CLEAR(dd->default_factory);
1386 PyDict_Type.tp_dealloc((PyObject *)dd);
Guido van Rossum1968ad32006-02-25 22:38:04 +00001387}
1388
Guido van Rossum1968ad32006-02-25 22:38:04 +00001389static PyObject *
1390defdict_repr(defdictobject *dd)
1391{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001392 PyObject *baserepr;
1393 PyObject *defrepr;
1394 PyObject *result;
1395 baserepr = PyDict_Type.tp_repr((PyObject *)dd);
1396 if (baserepr == NULL)
1397 return NULL;
1398 if (dd->default_factory == NULL)
1399 defrepr = PyUnicode_FromString("None");
1400 else
1401 {
1402 int status = Py_ReprEnter(dd->default_factory);
1403 if (status != 0) {
1404 if (status < 0)
1405 return NULL;
1406 defrepr = PyUnicode_FromString("...");
1407 }
1408 else
1409 defrepr = PyObject_Repr(dd->default_factory);
1410 Py_ReprLeave(dd->default_factory);
1411 }
1412 if (defrepr == NULL) {
1413 Py_DECREF(baserepr);
1414 return NULL;
1415 }
1416 result = PyUnicode_FromFormat("defaultdict(%U, %U)",
1417 defrepr, baserepr);
1418 Py_DECREF(defrepr);
1419 Py_DECREF(baserepr);
1420 return result;
Guido van Rossum1968ad32006-02-25 22:38:04 +00001421}
1422
1423static int
1424defdict_traverse(PyObject *self, visitproc visit, void *arg)
1425{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001426 Py_VISIT(((defdictobject *)self)->default_factory);
1427 return PyDict_Type.tp_traverse(self, visit, arg);
Guido van Rossum1968ad32006-02-25 22:38:04 +00001428}
1429
1430static int
1431defdict_tp_clear(defdictobject *dd)
1432{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001433 Py_CLEAR(dd->default_factory);
1434 return PyDict_Type.tp_clear((PyObject *)dd);
Guido van Rossum1968ad32006-02-25 22:38:04 +00001435}
1436
1437static int
1438defdict_init(PyObject *self, PyObject *args, PyObject *kwds)
1439{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001440 defdictobject *dd = (defdictobject *)self;
1441 PyObject *olddefault = dd->default_factory;
1442 PyObject *newdefault = NULL;
1443 PyObject *newargs;
1444 int result;
1445 if (args == NULL || !PyTuple_Check(args))
1446 newargs = PyTuple_New(0);
1447 else {
1448 Py_ssize_t n = PyTuple_GET_SIZE(args);
1449 if (n > 0) {
1450 newdefault = PyTuple_GET_ITEM(args, 0);
1451 if (!PyCallable_Check(newdefault) && newdefault != Py_None) {
1452 PyErr_SetString(PyExc_TypeError,
1453 "first argument must be callable");
1454 return -1;
1455 }
1456 }
1457 newargs = PySequence_GetSlice(args, 1, n);
1458 }
1459 if (newargs == NULL)
1460 return -1;
1461 Py_XINCREF(newdefault);
1462 dd->default_factory = newdefault;
1463 result = PyDict_Type.tp_init(self, newargs, kwds);
1464 Py_DECREF(newargs);
1465 Py_XDECREF(olddefault);
1466 return result;
Guido van Rossum1968ad32006-02-25 22:38:04 +00001467}
1468
1469PyDoc_STRVAR(defdict_doc,
1470"defaultdict(default_factory) --> dict with default factory\n\
1471\n\
1472The default factory is called without arguments to produce\n\
1473a new value when a key is not present, in __getitem__ only.\n\
1474A defaultdict compares equal to a dict with the same items.\n\
1475");
1476
Thomas Wouters49fd7fa2006-04-21 10:40:58 +00001477/* See comment in xxsubtype.c */
1478#define DEFERRED_ADDRESS(ADDR) 0
1479
Guido van Rossum1968ad32006-02-25 22:38:04 +00001480static PyTypeObject defdict_type = {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001481 PyVarObject_HEAD_INIT(DEFERRED_ADDRESS(&PyType_Type), 0)
1482 "collections.defaultdict", /* tp_name */
1483 sizeof(defdictobject), /* tp_basicsize */
1484 0, /* tp_itemsize */
1485 /* methods */
1486 (destructor)defdict_dealloc, /* tp_dealloc */
1487 0, /* tp_print */
1488 0, /* tp_getattr */
1489 0, /* tp_setattr */
1490 0, /* tp_reserved */
1491 (reprfunc)defdict_repr, /* tp_repr */
1492 0, /* tp_as_number */
1493 0, /* tp_as_sequence */
1494 0, /* tp_as_mapping */
1495 0, /* tp_hash */
1496 0, /* tp_call */
1497 0, /* tp_str */
1498 PyObject_GenericGetAttr, /* tp_getattro */
1499 0, /* tp_setattro */
1500 0, /* tp_as_buffer */
1501 Py_TPFLAGS_DEFAULT | Py_TPFLAGS_BASETYPE | Py_TPFLAGS_HAVE_GC,
1502 /* tp_flags */
1503 defdict_doc, /* tp_doc */
1504 defdict_traverse, /* tp_traverse */
1505 (inquiry)defdict_tp_clear, /* tp_clear */
1506 0, /* tp_richcompare */
1507 0, /* tp_weaklistoffset*/
1508 0, /* tp_iter */
1509 0, /* tp_iternext */
1510 defdict_methods, /* tp_methods */
1511 defdict_members, /* tp_members */
1512 0, /* tp_getset */
1513 DEFERRED_ADDRESS(&PyDict_Type), /* tp_base */
1514 0, /* tp_dict */
1515 0, /* tp_descr_get */
1516 0, /* tp_descr_set */
1517 0, /* tp_dictoffset */
1518 defdict_init, /* tp_init */
1519 PyType_GenericAlloc, /* tp_alloc */
1520 0, /* tp_new */
1521 PyObject_GC_Del, /* tp_free */
Guido van Rossum1968ad32006-02-25 22:38:04 +00001522};
1523
Raymond Hettinger96f34102010-12-15 16:30:37 +00001524/* helper function for Counter *********************************************/
1525
1526PyDoc_STRVAR(_count_elements_doc,
1527"_count_elements(mapping, iterable) -> None\n\
1528\n\
1529Count elements in the iterable, updating the mappping");
1530
1531static PyObject *
1532_count_elements(PyObject *self, PyObject *args)
1533{
1534 PyObject *it, *iterable, *mapping, *oldval;
1535 PyObject *newval = NULL;
1536 PyObject *key = NULL;
1537 PyObject *one = NULL;
1538
1539 if (!PyArg_UnpackTuple(args, "_count_elements", 2, 2, &mapping, &iterable))
1540 return NULL;
1541
Raymond Hettinger96f34102010-12-15 16:30:37 +00001542 it = PyObject_GetIter(iterable);
1543 if (it == NULL)
1544 return NULL;
Raymond Hettinger426e0522011-01-03 02:12:02 +00001545
Raymond Hettinger96f34102010-12-15 16:30:37 +00001546 one = PyLong_FromLong(1);
1547 if (one == NULL) {
1548 Py_DECREF(it);
1549 return NULL;
1550 }
Raymond Hettinger426e0522011-01-03 02:12:02 +00001551
1552 if (PyDict_CheckExact(mapping)) {
1553 while (1) {
1554 key = PyIter_Next(it);
1555 if (key == NULL) {
1556 if (PyErr_Occurred() && PyErr_ExceptionMatches(PyExc_StopIteration))
1557 PyErr_Clear();
1558 else
1559 break;
1560 }
1561 oldval = PyDict_GetItem(mapping, key);
1562 if (oldval == NULL) {
1563 if (PyDict_SetItem(mapping, key, one) == -1)
1564 break;
1565 } else {
1566 newval = PyNumber_Add(oldval, one);
1567 if (newval == NULL)
1568 break;
1569 if (PyDict_SetItem(mapping, key, newval) == -1)
1570 break;
1571 Py_CLEAR(newval);
1572 }
1573 Py_DECREF(key);
Raymond Hettinger96f34102010-12-15 16:30:37 +00001574 }
Raymond Hettinger426e0522011-01-03 02:12:02 +00001575 } else {
1576 while (1) {
1577 key = PyIter_Next(it);
1578 if (key == NULL) {
1579 if (PyErr_Occurred() && PyErr_ExceptionMatches(PyExc_StopIteration))
1580 PyErr_Clear();
1581 else
1582 break;
1583 }
1584 oldval = PyObject_GetItem(mapping, key);
1585 if (oldval == NULL) {
1586 if (!PyErr_Occurred() || !PyErr_ExceptionMatches(PyExc_KeyError))
1587 break;
1588 PyErr_Clear();
1589 Py_INCREF(one);
1590 newval = one;
1591 } else {
1592 newval = PyNumber_Add(oldval, one);
1593 Py_DECREF(oldval);
1594 if (newval == NULL)
1595 break;
1596 }
1597 if (PyObject_SetItem(mapping, key, newval) == -1)
Raymond Hettinger96f34102010-12-15 16:30:37 +00001598 break;
1599 Py_CLEAR(newval);
Raymond Hettinger426e0522011-01-03 02:12:02 +00001600 Py_DECREF(key);
Raymond Hettinger96f34102010-12-15 16:30:37 +00001601 }
Raymond Hettinger96f34102010-12-15 16:30:37 +00001602 }
Raymond Hettinger426e0522011-01-03 02:12:02 +00001603
Raymond Hettinger96f34102010-12-15 16:30:37 +00001604 Py_DECREF(it);
1605 Py_XDECREF(key);
1606 Py_XDECREF(newval);
1607 Py_DECREF(one);
1608 if (PyErr_Occurred())
1609 return NULL;
1610 Py_RETURN_NONE;
1611}
1612
Raymond Hettinger756b3f32004-01-29 06:37:52 +00001613/* module level code ********************************************************/
1614
1615PyDoc_STRVAR(module_doc,
Guido van Rossum1968ad32006-02-25 22:38:04 +00001616"High performance data structures.\n\
1617- deque: ordered collection accessible from endpoints only\n\
1618- defaultdict: dict subclass with a default value factory\n\
Raymond Hettinger756b3f32004-01-29 06:37:52 +00001619");
1620
Raymond Hettinger96f34102010-12-15 16:30:37 +00001621static struct PyMethodDef module_functions[] = {
1622 {"_count_elements", _count_elements, METH_VARARGS, _count_elements_doc},
1623 {NULL, NULL} /* sentinel */
1624};
Martin v. Löwis1a214512008-06-11 05:26:20 +00001625
1626static struct PyModuleDef _collectionsmodule = {
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001627 PyModuleDef_HEAD_INIT,
1628 "_collections",
1629 module_doc,
1630 -1,
Raymond Hettinger96f34102010-12-15 16:30:37 +00001631 module_functions,
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001632 NULL,
1633 NULL,
1634 NULL,
1635 NULL
Martin v. Löwis1a214512008-06-11 05:26:20 +00001636};
1637
Raymond Hettinger756b3f32004-01-29 06:37:52 +00001638PyMODINIT_FUNC
Martin v. Löwis1a214512008-06-11 05:26:20 +00001639PyInit__collections(void)
Raymond Hettinger756b3f32004-01-29 06:37:52 +00001640{
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001641 PyObject *m;
Raymond Hettinger756b3f32004-01-29 06:37:52 +00001642
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001643 m = PyModule_Create(&_collectionsmodule);
1644 if (m == NULL)
1645 return NULL;
Raymond Hettinger756b3f32004-01-29 06:37:52 +00001646
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001647 if (PyType_Ready(&deque_type) < 0)
1648 return NULL;
1649 Py_INCREF(&deque_type);
1650 PyModule_AddObject(m, "deque", (PyObject *)&deque_type);
Raymond Hettinger756b3f32004-01-29 06:37:52 +00001651
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001652 defdict_type.tp_base = &PyDict_Type;
1653 if (PyType_Ready(&defdict_type) < 0)
1654 return NULL;
1655 Py_INCREF(&defdict_type);
1656 PyModule_AddObject(m, "defaultdict", (PyObject *)&defdict_type);
Guido van Rossum1968ad32006-02-25 22:38:04 +00001657
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001658 if (PyType_Ready(&dequeiter_type) < 0)
1659 return NULL;
Raymond Hettinger756b3f32004-01-29 06:37:52 +00001660
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001661 if (PyType_Ready(&dequereviter_type) < 0)
1662 return NULL;
Raymond Hettinger1e5809f2004-03-18 11:04:57 +00001663
Antoine Pitrouf95a1b32010-05-09 15:52:27 +00001664 return m;
Raymond Hettinger756b3f32004-01-29 06:37:52 +00001665}