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