Branch data Line data Source code
1 : : #include "Python.h"
2 : : #include "pycore_call.h" // _PyObject_CallNoArgs()
3 : : #include "pycore_long.h" // _PyLong_GetZero()
4 : : #include "structmember.h" // PyMemberDef
5 : : #include <stddef.h>
6 : :
7 : : /*[clinic input]
8 : : module _collections
9 : : class _tuplegetter "_tuplegetterobject *" "&tuplegetter_type"
10 : : [clinic start generated code]*/
11 : : /*[clinic end generated code: output=da39a3ee5e6b4b0d input=a8ece4ccad7e30ac]*/
12 : :
13 : : static PyTypeObject tuplegetter_type;
14 : : #include "clinic/_collectionsmodule.c.h"
15 : :
16 : : /* collections module implementation of a deque() datatype
17 : : Written and maintained by Raymond D. Hettinger <python@rcn.com>
18 : : */
19 : :
20 : : /* The block length may be set to any number over 1. Larger numbers
21 : : * reduce the number of calls to the memory allocator, give faster
22 : : * indexing and rotation, and reduce the link to data overhead ratio.
23 : : * Making the block length a power of two speeds-up the modulo
24 : : * and division calculations in deque_item() and deque_ass_item().
25 : : */
26 : :
27 : : #define BLOCKLEN 64
28 : : #define CENTER ((BLOCKLEN - 1) / 2)
29 : : #define MAXFREEBLOCKS 16
30 : :
31 : : /* Data for deque objects is stored in a doubly-linked list of fixed
32 : : * length blocks. This assures that appends or pops never move any
33 : : * other data elements besides the one being appended or popped.
34 : : *
35 : : * Another advantage is that it completely avoids use of realloc(),
36 : : * resulting in more predictable performance.
37 : : *
38 : : * Textbook implementations of doubly-linked lists store one datum
39 : : * per link, but that gives them a 200% memory overhead (a prev and
40 : : * next link for each datum) and it costs one malloc() call per data
41 : : * element. By using fixed-length blocks, the link to data ratio is
42 : : * significantly improved and there are proportionally fewer calls
43 : : * to malloc() and free(). The data blocks of consecutive pointers
44 : : * also improve cache locality.
45 : : *
46 : : * The list of blocks is never empty, so d.leftblock and d.rightblock
47 : : * are never equal to NULL. The list is not circular.
48 : : *
49 : : * A deque d's first element is at d.leftblock[leftindex]
50 : : * and its last element is at d.rightblock[rightindex].
51 : : *
52 : : * Unlike Python slice indices, these indices are inclusive on both
53 : : * ends. This makes the algorithms for left and right operations
54 : : * more symmetrical and it simplifies the design.
55 : : *
56 : : * The indices, d.leftindex and d.rightindex are always in the range:
57 : : * 0 <= index < BLOCKLEN
58 : : *
59 : : * And their exact relationship is:
60 : : * (d.leftindex + d.len - 1) % BLOCKLEN == d.rightindex
61 : : *
62 : : * Whenever d.leftblock == d.rightblock, then:
63 : : * d.leftindex + d.len - 1 == d.rightindex
64 : : *
65 : : * However, when d.leftblock != d.rightblock, the d.leftindex and
66 : : * d.rightindex become indices into distinct blocks and either may
67 : : * be larger than the other.
68 : : *
69 : : * Empty deques have:
70 : : * d.len == 0
71 : : * d.leftblock == d.rightblock
72 : : * d.leftindex == CENTER + 1
73 : : * d.rightindex == CENTER
74 : : *
75 : : * Checking for d.len == 0 is the intended way to see whether d is empty.
76 : : */
77 : :
78 : : typedef struct BLOCK {
79 : : struct BLOCK *leftlink;
80 : : PyObject *data[BLOCKLEN];
81 : : struct BLOCK *rightlink;
82 : : } block;
83 : :
84 : : typedef struct {
85 : : PyObject_VAR_HEAD
86 : : block *leftblock;
87 : : block *rightblock;
88 : : Py_ssize_t leftindex; /* 0 <= leftindex < BLOCKLEN */
89 : : Py_ssize_t rightindex; /* 0 <= rightindex < BLOCKLEN */
90 : : size_t state; /* incremented whenever the indices move */
91 : : Py_ssize_t maxlen; /* maxlen is -1 for unbounded deques */
92 : : Py_ssize_t numfreeblocks;
93 : : block *freeblocks[MAXFREEBLOCKS];
94 : : PyObject *weakreflist;
95 : : } dequeobject;
96 : :
97 : : static PyTypeObject deque_type;
98 : :
99 : : /* For debug builds, add error checking to track the endpoints
100 : : * in the chain of links. The goal is to make sure that link
101 : : * assignments only take place at endpoints so that links already
102 : : * in use do not get overwritten.
103 : : *
104 : : * CHECK_END should happen before each assignment to a block's link field.
105 : : * MARK_END should happen whenever a link field becomes a new endpoint.
106 : : * This happens when new blocks are added or whenever an existing
107 : : * block is freed leaving another existing block as the new endpoint.
108 : : */
109 : :
110 : : #ifndef NDEBUG
111 : : #define MARK_END(link) link = NULL;
112 : : #define CHECK_END(link) assert(link == NULL);
113 : : #define CHECK_NOT_END(link) assert(link != NULL);
114 : : #else
115 : : #define MARK_END(link)
116 : : #define CHECK_END(link)
117 : : #define CHECK_NOT_END(link)
118 : : #endif
119 : :
120 : : /* A simple freelisting scheme is used to minimize calls to the memory
121 : : allocator. It accommodates common use cases where new blocks are being
122 : : added at about the same rate as old blocks are being freed.
123 : : */
124 : :
125 : : static inline block *
126 : 78693 : newblock(dequeobject *deque) {
127 : : block *b;
128 [ + + ]: 78693 : if (deque->numfreeblocks) {
129 : 15076 : deque->numfreeblocks--;
130 : 15076 : return deque->freeblocks[deque->numfreeblocks];
131 : : }
132 : 63617 : b = PyMem_Malloc(sizeof(block));
133 [ + - ]: 63617 : if (b != NULL) {
134 : 63617 : return b;
135 : : }
136 : : PyErr_NoMemory();
137 : 0 : return NULL;
138 : : }
139 : :
140 : : static inline void
141 : 78503 : freeblock(dequeobject *deque, block *b)
142 : : {
143 [ + + ]: 78503 : if (deque->numfreeblocks < MAXFREEBLOCKS) {
144 : 69861 : deque->freeblocks[deque->numfreeblocks] = b;
145 : 69861 : deque->numfreeblocks++;
146 : : } else {
147 : 8642 : PyMem_Free(b);
148 : : }
149 : 78503 : }
150 : :
151 : : static PyObject *
152 : 50449 : deque_new(PyTypeObject *type, PyObject *args, PyObject *kwds)
153 : : {
154 : : dequeobject *deque;
155 : : block *b;
156 : :
157 : : /* create dequeobject structure */
158 : 50449 : deque = (dequeobject *)type->tp_alloc(type, 0);
159 [ - + ]: 50449 : if (deque == NULL)
160 : 0 : return NULL;
161 : :
162 : 50449 : b = newblock(deque);
163 [ - + ]: 50449 : if (b == NULL) {
164 : 0 : Py_DECREF(deque);
165 : 0 : return NULL;
166 : : }
167 : : MARK_END(b->leftlink);
168 : : MARK_END(b->rightlink);
169 : :
170 : : assert(BLOCKLEN >= 2);
171 : 50449 : Py_SET_SIZE(deque, 0);
172 : 50449 : deque->leftblock = b;
173 : 50449 : deque->rightblock = b;
174 : 50449 : deque->leftindex = CENTER + 1;
175 : 50449 : deque->rightindex = CENTER;
176 : 50449 : deque->state = 0;
177 : 50449 : deque->maxlen = -1;
178 : 50449 : deque->numfreeblocks = 0;
179 : 50449 : deque->weakreflist = NULL;
180 : :
181 : 50449 : return (PyObject *)deque;
182 : : }
183 : :
184 : : static PyObject *
185 : 734753 : deque_pop(dequeobject *deque, PyObject *unused)
186 : : {
187 : : PyObject *item;
188 : : block *prevblock;
189 : :
190 [ + + ]: 734753 : if (Py_SIZE(deque) == 0) {
191 : 3 : PyErr_SetString(PyExc_IndexError, "pop from an empty deque");
192 : 3 : return NULL;
193 : : }
194 : 734750 : item = deque->rightblock->data[deque->rightindex];
195 : 734750 : deque->rightindex--;
196 : 734750 : Py_SET_SIZE(deque, Py_SIZE(deque) - 1);
197 : 734750 : deque->state++;
198 : :
199 [ + + ]: 734750 : if (deque->rightindex < 0) {
200 [ + + ]: 12875 : if (Py_SIZE(deque)) {
201 : 9733 : prevblock = deque->rightblock->leftlink;
202 : : assert(deque->leftblock != deque->rightblock);
203 : 9733 : freeblock(deque, deque->rightblock);
204 : : CHECK_NOT_END(prevblock);
205 : : MARK_END(prevblock->rightlink);
206 : 9733 : deque->rightblock = prevblock;
207 : 9733 : deque->rightindex = BLOCKLEN - 1;
208 : : } else {
209 : : assert(deque->leftblock == deque->rightblock);
210 : : assert(deque->leftindex == deque->rightindex+1);
211 : : /* re-center instead of freeing a block */
212 : 3142 : deque->leftindex = CENTER + 1;
213 : 3142 : deque->rightindex = CENTER;
214 : : }
215 : : }
216 : 734750 : return item;
217 : : }
218 : :
219 : : PyDoc_STRVAR(pop_doc, "Remove and return the rightmost element.");
220 : :
221 : : static PyObject *
222 : 1005079 : deque_popleft(dequeobject *deque, PyObject *unused)
223 : : {
224 : : PyObject *item;
225 : : block *prevblock;
226 : :
227 [ + + ]: 1005079 : if (Py_SIZE(deque) == 0) {
228 : 810 : PyErr_SetString(PyExc_IndexError, "pop from an empty deque");
229 : 810 : return NULL;
230 : : }
231 : : assert(deque->leftblock != NULL);
232 : 1004269 : item = deque->leftblock->data[deque->leftindex];
233 : 1004269 : deque->leftindex++;
234 : 1004269 : Py_SET_SIZE(deque, Py_SIZE(deque) - 1);
235 : 1004269 : deque->state++;
236 : :
237 [ + + ]: 1004269 : if (deque->leftindex == BLOCKLEN) {
238 [ + + ]: 16394 : if (Py_SIZE(deque)) {
239 : : assert(deque->leftblock != deque->rightblock);
240 : 12305 : prevblock = deque->leftblock->rightlink;
241 : 12305 : freeblock(deque, deque->leftblock);
242 : : CHECK_NOT_END(prevblock);
243 : : MARK_END(prevblock->leftlink);
244 : 12305 : deque->leftblock = prevblock;
245 : 12305 : deque->leftindex = 0;
246 : : } else {
247 : : assert(deque->leftblock == deque->rightblock);
248 : : assert(deque->leftindex == deque->rightindex+1);
249 : : /* re-center instead of freeing a block */
250 : 4089 : deque->leftindex = CENTER + 1;
251 : 4089 : deque->rightindex = CENTER;
252 : : }
253 : : }
254 : 1004269 : return item;
255 : : }
256 : :
257 : : PyDoc_STRVAR(popleft_doc, "Remove and return the leftmost element.");
258 : :
259 : : /* The deque's size limit is d.maxlen. The limit can be zero or positive.
260 : : * If there is no limit, then d.maxlen == -1.
261 : : *
262 : : * After an item is added to a deque, we check to see if the size has
263 : : * grown past the limit. If it has, we get the size back down to the limit
264 : : * by popping an item off of the opposite end. The methods that can
265 : : * trigger this are append(), appendleft(), extend(), and extendleft().
266 : : *
267 : : * The macro to check whether a deque needs to be trimmed uses a single
268 : : * unsigned test that returns true whenever 0 <= maxlen < Py_SIZE(deque).
269 : : */
270 : :
271 : : #define NEEDS_TRIM(deque, maxlen) ((size_t)(maxlen) < (size_t)(Py_SIZE(deque)))
272 : :
273 : : static inline int
274 : 1224411 : deque_append_internal(dequeobject *deque, PyObject *item, Py_ssize_t maxlen)
275 : : {
276 [ + + ]: 1224411 : if (deque->rightindex == BLOCKLEN - 1) {
277 : 15259 : block *b = newblock(deque);
278 [ - + ]: 15259 : if (b == NULL)
279 : 0 : return -1;
280 : 15259 : b->leftlink = deque->rightblock;
281 : : CHECK_END(deque->rightblock->rightlink);
282 : 15259 : deque->rightblock->rightlink = b;
283 : 15259 : deque->rightblock = b;
284 : : MARK_END(b->rightlink);
285 : 15259 : deque->rightindex = -1;
286 : : }
287 : 1224411 : Py_SET_SIZE(deque, Py_SIZE(deque) + 1);
288 : 1224411 : deque->rightindex++;
289 : 1224411 : deque->rightblock->data[deque->rightindex] = item;
290 [ + + ]: 1224411 : if (NEEDS_TRIM(deque, maxlen)) {
291 : 23327 : PyObject *olditem = deque_popleft(deque, NULL);
292 : 23327 : Py_DECREF(olditem);
293 : : } else {
294 : 1201084 : deque->state++;
295 : : }
296 : 1224411 : return 0;
297 : : }
298 : :
299 : : static PyObject *
300 : 970849 : deque_append(dequeobject *deque, PyObject *item)
301 : : {
302 : 970849 : Py_INCREF(item);
303 [ - + ]: 970849 : if (deque_append_internal(deque, item, deque->maxlen) < 0)
304 : 0 : return NULL;
305 : 970849 : Py_RETURN_NONE;
306 : : }
307 : :
308 : : PyDoc_STRVAR(append_doc, "Add an element to the right side of the deque.");
309 : :
310 : : static inline int
311 : 703832 : deque_appendleft_internal(dequeobject *deque, PyObject *item, Py_ssize_t maxlen)
312 : : {
313 [ + + ]: 703832 : if (deque->leftindex == 0) {
314 : 9392 : block *b = newblock(deque);
315 [ - + ]: 9392 : if (b == NULL)
316 : 0 : return -1;
317 : 9392 : b->rightlink = deque->leftblock;
318 : : CHECK_END(deque->leftblock->leftlink);
319 : 9392 : deque->leftblock->leftlink = b;
320 : 9392 : deque->leftblock = b;
321 : : MARK_END(b->leftlink);
322 : 9392 : deque->leftindex = BLOCKLEN;
323 : : }
324 : 703832 : Py_SET_SIZE(deque, Py_SIZE(deque) + 1);
325 : 703832 : deque->leftindex--;
326 : 703832 : deque->leftblock->data[deque->leftindex] = item;
327 [ + + ]: 703832 : if (NEEDS_TRIM(deque, deque->maxlen)) {
328 : 3 : PyObject *olditem = deque_pop(deque, NULL);
329 : 3 : Py_DECREF(olditem);
330 : : } else {
331 : 703829 : deque->state++;
332 : : }
333 : 703832 : return 0;
334 : : }
335 : :
336 : : static PyObject *
337 : 702820 : deque_appendleft(dequeobject *deque, PyObject *item)
338 : : {
339 : 702820 : Py_INCREF(item);
340 [ - + ]: 702820 : if (deque_appendleft_internal(deque, item, deque->maxlen) < 0)
341 : 0 : return NULL;
342 : 702820 : Py_RETURN_NONE;
343 : : }
344 : :
345 : : PyDoc_STRVAR(appendleft_doc, "Add an element to the left side of the deque.");
346 : :
347 : : static PyObject*
348 : 12016 : finalize_iterator(PyObject *it)
349 : : {
350 [ + + ]: 12016 : if (PyErr_Occurred()) {
351 [ + + ]: 31 : if (PyErr_ExceptionMatches(PyExc_StopIteration))
352 : 20 : PyErr_Clear();
353 : : else {
354 : 11 : Py_DECREF(it);
355 : 11 : return NULL;
356 : : }
357 : : }
358 : 12005 : Py_DECREF(it);
359 : 12005 : Py_RETURN_NONE;
360 : : }
361 : :
362 : : /* Run an iterator to exhaustion. Shortcut for
363 : : the extend/extendleft methods when maxlen == 0. */
364 : : static PyObject*
365 : 14 : consume_iterator(PyObject *it)
366 : : {
367 : : PyObject *(*iternext)(PyObject *);
368 : : PyObject *item;
369 : :
370 : 14 : iternext = *Py_TYPE(it)->tp_iternext;
371 [ + + ]: 327 : while ((item = iternext(it)) != NULL) {
372 : 313 : Py_DECREF(item);
373 : : }
374 : 14 : return finalize_iterator(it);
375 : : }
376 : :
377 : : static PyObject *
378 : 12033 : deque_extend(dequeobject *deque, PyObject *iterable)
379 : : {
380 : : PyObject *it, *item;
381 : : PyObject *(*iternext)(PyObject *);
382 : 12033 : Py_ssize_t maxlen = deque->maxlen;
383 : :
384 : : /* Handle case where id(deque) == id(iterable) */
385 [ + + ]: 12033 : if ((PyObject *)deque == iterable) {
386 : : PyObject *result;
387 : 2 : PyObject *s = PySequence_List(iterable);
388 [ - + ]: 2 : if (s == NULL)
389 : 0 : return NULL;
390 : 2 : result = deque_extend(deque, s);
391 : 2 : Py_DECREF(s);
392 : 2 : return result;
393 : : }
394 : :
395 : 12031 : it = PyObject_GetIter(iterable);
396 [ + + ]: 12031 : if (it == NULL)
397 : 22 : return NULL;
398 : :
399 [ + + ]: 12009 : if (maxlen == 0)
400 : 13 : return consume_iterator(it);
401 : :
402 : : /* Space saving heuristic. Start filling from the left */
403 [ + + ]: 11996 : if (Py_SIZE(deque) == 0) {
404 : : assert(deque->leftblock == deque->rightblock);
405 : : assert(deque->leftindex == deque->rightindex+1);
406 : 9410 : deque->leftindex = 1;
407 : 9410 : deque->rightindex = 0;
408 : : }
409 : :
410 : 11996 : iternext = *Py_TYPE(it)->tp_iternext;
411 [ + + ]: 265558 : while ((item = iternext(it)) != NULL) {
412 [ - + ]: 253562 : if (deque_append_internal(deque, item, maxlen) == -1) {
413 : 0 : Py_DECREF(item);
414 : 0 : Py_DECREF(it);
415 : 0 : return NULL;
416 : : }
417 : : }
418 : 11996 : return finalize_iterator(it);
419 : : }
420 : :
421 : : PyDoc_STRVAR(extend_doc,
422 : : "Extend the right side of the deque with elements from the iterable");
423 : :
424 : : static PyObject *
425 : 9 : deque_extendleft(dequeobject *deque, PyObject *iterable)
426 : : {
427 : : PyObject *it, *item;
428 : : PyObject *(*iternext)(PyObject *);
429 : 9 : Py_ssize_t maxlen = deque->maxlen;
430 : :
431 : : /* Handle case where id(deque) == id(iterable) */
432 [ + + ]: 9 : if ((PyObject *)deque == iterable) {
433 : : PyObject *result;
434 : 1 : PyObject *s = PySequence_List(iterable);
435 [ - + ]: 1 : if (s == NULL)
436 : 0 : return NULL;
437 : 1 : result = deque_extendleft(deque, s);
438 : 1 : Py_DECREF(s);
439 : 1 : return result;
440 : : }
441 : :
442 : 8 : it = PyObject_GetIter(iterable);
443 [ + + ]: 8 : if (it == NULL)
444 : 1 : return NULL;
445 : :
446 [ + + ]: 7 : if (maxlen == 0)
447 : 1 : return consume_iterator(it);
448 : :
449 : : /* Space saving heuristic. Start filling from the right */
450 [ + + ]: 6 : if (Py_SIZE(deque) == 0) {
451 : : assert(deque->leftblock == deque->rightblock);
452 : : assert(deque->leftindex == deque->rightindex+1);
453 : 2 : deque->leftindex = BLOCKLEN - 1;
454 : 2 : deque->rightindex = BLOCKLEN - 2;
455 : : }
456 : :
457 : 6 : iternext = *Py_TYPE(it)->tp_iternext;
458 [ + + ]: 1018 : while ((item = iternext(it)) != NULL) {
459 [ - + ]: 1012 : if (deque_appendleft_internal(deque, item, maxlen) == -1) {
460 : 0 : Py_DECREF(item);
461 : 0 : Py_DECREF(it);
462 : 0 : return NULL;
463 : : }
464 : : }
465 : 6 : return finalize_iterator(it);
466 : : }
467 : :
468 : : PyDoc_STRVAR(extendleft_doc,
469 : : "Extend the left side of the deque with elements from the iterable");
470 : :
471 : : static PyObject *
472 : 6 : deque_inplace_concat(dequeobject *deque, PyObject *other)
473 : : {
474 : : PyObject *result;
475 : :
476 : 6 : result = deque_extend(deque, other);
477 [ - + ]: 6 : if (result == NULL)
478 : 0 : return result;
479 : 6 : Py_INCREF(deque);
480 : 6 : Py_DECREF(result);
481 : 6 : return (PyObject *)deque;
482 : : }
483 : :
484 : : static PyObject *
485 : 136 : deque_copy(PyObject *deque, PyObject *Py_UNUSED(ignored))
486 : : {
487 : : PyObject *result;
488 : 136 : dequeobject *old_deque = (dequeobject *)deque;
489 [ + + ]: 136 : if (Py_IS_TYPE(deque, &deque_type)) {
490 : : dequeobject *new_deque;
491 : : PyObject *rv;
492 : :
493 : 128 : new_deque = (dequeobject *)deque_new(&deque_type, (PyObject *)NULL, (PyObject *)NULL);
494 [ - + ]: 128 : if (new_deque == NULL)
495 : 0 : return NULL;
496 : 128 : new_deque->maxlen = old_deque->maxlen;
497 : : /* Fast path for the deque_repeat() common case where len(deque) == 1 */
498 [ + + ]: 128 : if (Py_SIZE(deque) == 1) {
499 : 23 : PyObject *item = old_deque->leftblock->data[old_deque->leftindex];
500 : 23 : rv = deque_append(new_deque, item);
501 : : } else {
502 : 105 : rv = deque_extend(new_deque, deque);
503 : : }
504 [ + - ]: 128 : if (rv != NULL) {
505 : 128 : Py_DECREF(rv);
506 : 128 : return (PyObject *)new_deque;
507 : : }
508 : 0 : Py_DECREF(new_deque);
509 : 0 : return NULL;
510 : : }
511 [ + + ]: 8 : if (old_deque->maxlen < 0)
512 : 6 : result = PyObject_CallOneArg((PyObject *)(Py_TYPE(deque)), deque);
513 : : else
514 : 2 : result = PyObject_CallFunction((PyObject *)(Py_TYPE(deque)), "Oi",
515 : : deque, old_deque->maxlen, NULL);
516 [ + - + + ]: 8 : if (result != NULL && !PyObject_TypeCheck(result, &deque_type)) {
517 : 2 : PyErr_Format(PyExc_TypeError,
518 : : "%.200s() must return a deque, not %.200s",
519 : 2 : Py_TYPE(deque)->tp_name, Py_TYPE(result)->tp_name);
520 : 2 : Py_DECREF(result);
521 : 2 : return NULL;
522 : : }
523 : 6 : return result;
524 : : }
525 : :
526 : : PyDoc_STRVAR(copy_doc, "Return a shallow copy of a deque.");
527 : :
528 : : static PyObject *
529 : 23 : deque_concat(dequeobject *deque, PyObject *other)
530 : : {
531 : : PyObject *new_deque, *result;
532 : : int rv;
533 : :
534 : 23 : rv = PyObject_IsInstance(other, (PyObject *)&deque_type);
535 [ + + ]: 23 : if (rv <= 0) {
536 [ + - ]: 1 : if (rv == 0) {
537 : 1 : PyErr_Format(PyExc_TypeError,
538 : : "can only concatenate deque (not \"%.200s\") to deque",
539 : 1 : Py_TYPE(other)->tp_name);
540 : : }
541 : 1 : return NULL;
542 : : }
543 : :
544 : 22 : new_deque = deque_copy((PyObject *)deque, NULL);
545 [ + + ]: 22 : if (new_deque == NULL)
546 : 1 : return NULL;
547 : 21 : result = deque_extend((dequeobject *)new_deque, other);
548 [ - + ]: 21 : if (result == NULL) {
549 : 0 : Py_DECREF(new_deque);
550 : 0 : return NULL;
551 : : }
552 : 21 : Py_DECREF(result);
553 : 21 : return new_deque;
554 : : }
555 : :
556 : : static int
557 : 53947 : deque_clear(dequeobject *deque)
558 : : {
559 : : block *b;
560 : : block *prevblock;
561 : : block *leftblock;
562 : : Py_ssize_t leftindex;
563 : : Py_ssize_t n, m;
564 : : PyObject *item;
565 : : PyObject **itemptr, **limit;
566 : :
567 [ + + ]: 53947 : if (Py_SIZE(deque) == 0)
568 : 52351 : return 0;
569 : :
570 : : /* During the process of clearing a deque, decrefs can cause the
571 : : deque to mutate. To avoid fatal confusion, we have to make the
572 : : deque empty before clearing the blocks and never refer to
573 : : anything via deque->ref while clearing. (This is the same
574 : : technique used for clearing lists, sets, and dicts.)
575 : :
576 : : Making the deque empty requires allocating a new empty block. In
577 : : the unlikely event that memory is full, we fall back to an
578 : : alternate method that doesn't require a new block. Repeating
579 : : pops in a while-loop is slower, possibly re-entrant (and a clever
580 : : adversary could cause it to never terminate).
581 : : */
582 : :
583 : 1596 : b = newblock(deque);
584 [ - + ]: 1596 : if (b == NULL) {
585 : 0 : PyErr_Clear();
586 : 0 : goto alternate_method;
587 : : }
588 : :
589 : : /* Remember the old size, leftblock, and leftindex */
590 : 1596 : n = Py_SIZE(deque);
591 : 1596 : leftblock = deque->leftblock;
592 : 1596 : leftindex = deque->leftindex;
593 : :
594 : : /* Set the deque to be empty using the newly allocated block */
595 : : MARK_END(b->leftlink);
596 : : MARK_END(b->rightlink);
597 : 1596 : Py_SET_SIZE(deque, 0);
598 : 1596 : deque->leftblock = b;
599 : 1596 : deque->rightblock = b;
600 : 1596 : deque->leftindex = CENTER + 1;
601 : 1596 : deque->rightindex = CENTER;
602 : 1596 : deque->state++;
603 : :
604 : : /* Now the old size, leftblock, and leftindex are disconnected from
605 : : the empty deque and we can use them to decref the pointers.
606 : : */
607 : 1596 : m = (BLOCKLEN - leftindex > n) ? n : BLOCKLEN - leftindex;
608 : 1596 : itemptr = &leftblock->data[leftindex];
609 : 1596 : limit = itemptr + m;
610 : 1596 : n -= m;
611 : : while (1) {
612 [ + + ]: 193840 : if (itemptr == limit) {
613 [ + + ]: 4260 : if (n == 0)
614 : 1596 : break;
615 : : CHECK_NOT_END(leftblock->rightlink);
616 : 2664 : prevblock = leftblock;
617 : 2664 : leftblock = leftblock->rightlink;
618 : 2664 : m = (n > BLOCKLEN) ? BLOCKLEN : n;
619 : 2664 : itemptr = leftblock->data;
620 : 2664 : limit = itemptr + m;
621 : 2664 : n -= m;
622 : 2664 : freeblock(deque, prevblock);
623 : : }
624 : 192244 : item = *(itemptr++);
625 : 192244 : Py_DECREF(item);
626 : : }
627 : : CHECK_END(leftblock->rightlink);
628 : 1596 : freeblock(deque, leftblock);
629 : 1596 : return 0;
630 : :
631 : 0 : alternate_method:
632 [ # # ]: 0 : while (Py_SIZE(deque)) {
633 : 0 : item = deque_pop(deque, NULL);
634 : : assert (item != NULL);
635 : 0 : Py_DECREF(item);
636 : : }
637 : 0 : return 0;
638 : : }
639 : :
640 : : static PyObject *
641 : 3592 : deque_clearmethod(dequeobject *deque, PyObject *Py_UNUSED(ignored))
642 : : {
643 : 3592 : deque_clear(deque);
644 : 3592 : Py_RETURN_NONE;
645 : : }
646 : :
647 : : PyDoc_STRVAR(clear_doc, "Remove all elements from the deque.");
648 : :
649 : : static PyObject *
650 : 115 : deque_inplace_repeat(dequeobject *deque, Py_ssize_t n)
651 : : {
652 : : Py_ssize_t i, m, size;
653 : : PyObject *seq;
654 : : PyObject *rv;
655 : :
656 : 115 : size = Py_SIZE(deque);
657 [ + + + + ]: 115 : if (size == 0 || n == 1) {
658 : 36 : Py_INCREF(deque);
659 : 36 : return (PyObject *)deque;
660 : : }
661 : :
662 [ + + ]: 79 : if (n <= 0) {
663 : 38 : deque_clear(deque);
664 : 38 : Py_INCREF(deque);
665 : 38 : return (PyObject *)deque;
666 : : }
667 : :
668 [ + + ]: 41 : if (size == 1) {
669 : : /* common case, repeating a single element */
670 : 12 : PyObject *item = deque->leftblock->data[deque->leftindex];
671 : :
672 [ + + + + ]: 12 : if (deque->maxlen >= 0 && n > deque->maxlen)
673 : 2 : n = deque->maxlen;
674 : :
675 : 12 : deque->state++;
676 [ + + ]: 67 : for (i = 0 ; i < n-1 ; ) {
677 [ + + ]: 55 : if (deque->rightindex == BLOCKLEN - 1) {
678 : 43 : block *b = newblock(deque);
679 [ - + ]: 43 : if (b == NULL) {
680 : 0 : Py_SET_SIZE(deque, Py_SIZE(deque) + i);
681 : 0 : return NULL;
682 : : }
683 : 43 : b->leftlink = deque->rightblock;
684 : : CHECK_END(deque->rightblock->rightlink);
685 : 43 : deque->rightblock->rightlink = b;
686 : 43 : deque->rightblock = b;
687 : : MARK_END(b->rightlink);
688 : 43 : deque->rightindex = -1;
689 : : }
690 : 55 : m = n - 1 - i;
691 [ + + ]: 55 : if (m > BLOCKLEN - 1 - deque->rightindex)
692 : 43 : m = BLOCKLEN - 1 - deque->rightindex;
693 : 55 : i += m;
694 [ + + ]: 3075 : while (m--) {
695 : 3020 : deque->rightindex++;
696 : 3020 : Py_INCREF(item);
697 : 3020 : deque->rightblock->data[deque->rightindex] = item;
698 : : }
699 : : }
700 : 12 : Py_SET_SIZE(deque, Py_SIZE(deque) + i);
701 : 12 : Py_INCREF(deque);
702 : 12 : return (PyObject *)deque;
703 : : }
704 : :
705 [ - + ]: 29 : if ((size_t)size > PY_SSIZE_T_MAX / (size_t)n) {
706 : : return PyErr_NoMemory();
707 : : }
708 : :
709 : 29 : seq = PySequence_List((PyObject *)deque);
710 [ - + ]: 29 : if (seq == NULL)
711 : 0 : return seq;
712 : :
713 : : /* Reduce the number of repetitions when maxlen would be exceeded */
714 [ + + + + ]: 29 : if (deque->maxlen >= 0 && n * size > deque->maxlen)
715 : 6 : n = (deque->maxlen + size - 1) / size;
716 : :
717 [ + + ]: 1412 : for (i = 0 ; i < n-1 ; i++) {
718 : 1383 : rv = deque_extend(deque, seq);
719 [ - + ]: 1383 : if (rv == NULL) {
720 : 0 : Py_DECREF(seq);
721 : 0 : return NULL;
722 : : }
723 : 1383 : Py_DECREF(rv);
724 : : }
725 : 29 : Py_INCREF(deque);
726 : 29 : Py_DECREF(seq);
727 : 29 : return (PyObject *)deque;
728 : : }
729 : :
730 : : static PyObject *
731 : 73 : deque_repeat(dequeobject *deque, Py_ssize_t n)
732 : : {
733 : : dequeobject *new_deque;
734 : : PyObject *rv;
735 : :
736 : 73 : new_deque = (dequeobject *)deque_copy((PyObject *) deque, NULL);
737 [ + + ]: 73 : if (new_deque == NULL)
738 : 1 : return NULL;
739 : 72 : rv = deque_inplace_repeat(new_deque, n);
740 : 72 : Py_DECREF(new_deque);
741 : 72 : return rv;
742 : : }
743 : :
744 : : /* The rotate() method is part of the public API and is used internally
745 : : as a primitive for other methods.
746 : :
747 : : Rotation by 1 or -1 is a common case, so any optimizations for high
748 : : volume rotations should take care not to penalize the common case.
749 : :
750 : : Conceptually, a rotate by one is equivalent to a pop on one side and an
751 : : append on the other. However, a pop/append pair is unnecessarily slow
752 : : because it requires an incref/decref pair for an object located randomly
753 : : in memory. It is better to just move the object pointer from one block
754 : : to the next without changing the reference count.
755 : :
756 : : When moving batches of pointers, it is tempting to use memcpy() but that
757 : : proved to be slower than a simple loop for a variety of reasons.
758 : : Memcpy() cannot know in advance that we're copying pointers instead of
759 : : bytes, that the source and destination are pointer aligned and
760 : : non-overlapping, that moving just one pointer is a common case, that we
761 : : never need to move more than BLOCKLEN pointers, and that at least one
762 : : pointer is always moved.
763 : :
764 : : For high volume rotations, newblock() and freeblock() are never called
765 : : more than once. Previously emptied blocks are immediately reused as a
766 : : destination block. If a block is left-over at the end, it is freed.
767 : : */
768 : :
769 : : static int
770 : 188181 : _deque_rotate(dequeobject *deque, Py_ssize_t n)
771 : : {
772 : 188181 : block *b = NULL;
773 : 188181 : block *leftblock = deque->leftblock;
774 : 188181 : block *rightblock = deque->rightblock;
775 : 188181 : Py_ssize_t leftindex = deque->leftindex;
776 : 188181 : Py_ssize_t rightindex = deque->rightindex;
777 : 188181 : Py_ssize_t len=Py_SIZE(deque), halflen=len>>1;
778 : 188181 : int rv = -1;
779 : :
780 [ + + ]: 188181 : if (len <= 1)
781 : 53812 : return 0;
782 [ + + + + ]: 134369 : if (n > halflen || n < -halflen) {
783 : 584 : n %= len;
784 [ + + ]: 584 : if (n > halflen)
785 : 267 : n -= len;
786 [ + + ]: 317 : else if (n < -halflen)
787 : 275 : n += len;
788 : : }
789 : : assert(len > 1);
790 : : assert(-halflen <= n && n <= halflen);
791 : :
792 : 134369 : deque->state++;
793 [ + + ]: 236136 : while (n > 0) {
794 [ + + ]: 101767 : if (leftindex == 0) {
795 [ + + ]: 2075 : if (b == NULL) {
796 : 1763 : b = newblock(deque);
797 [ - + ]: 1763 : if (b == NULL)
798 : 0 : goto done;
799 : : }
800 : 2075 : b->rightlink = leftblock;
801 : : CHECK_END(leftblock->leftlink);
802 : 2075 : leftblock->leftlink = b;
803 : 2075 : leftblock = b;
804 : : MARK_END(b->leftlink);
805 : 2075 : leftindex = BLOCKLEN;
806 : 2075 : b = NULL;
807 : : }
808 : : assert(leftindex > 0);
809 : : {
810 : : PyObject **src, **dest;
811 : 101767 : Py_ssize_t m = n;
812 : :
813 [ + + ]: 101767 : if (m > rightindex + 1)
814 : 780 : m = rightindex + 1;
815 [ + + ]: 101767 : if (m > leftindex)
816 : 488 : m = leftindex;
817 : : assert (m > 0 && m <= len);
818 : 101767 : rightindex -= m;
819 : 101767 : leftindex -= m;
820 : 101767 : src = &rightblock->data[rightindex + 1];
821 : 101767 : dest = &leftblock->data[leftindex];
822 : 101767 : n -= m;
823 : : do {
824 : 131841 : *(dest++) = *(src++);
825 [ + + ]: 131841 : } while (--m);
826 : : }
827 [ + + ]: 101767 : if (rightindex < 0) {
828 : : assert(leftblock != rightblock);
829 : : assert(b == NULL);
830 : 2071 : b = rightblock;
831 : : CHECK_NOT_END(rightblock->leftlink);
832 : 2071 : rightblock = rightblock->leftlink;
833 : : MARK_END(rightblock->rightlink);
834 : 2071 : rightindex = BLOCKLEN - 1;
835 : : }
836 : : }
837 [ + + ]: 136029 : while (n < 0) {
838 [ + + ]: 1660 : if (rightindex == BLOCKLEN - 1) {
839 [ + + ]: 499 : if (b == NULL) {
840 : 191 : b = newblock(deque);
841 [ - + ]: 191 : if (b == NULL)
842 : 0 : goto done;
843 : : }
844 : 499 : b->leftlink = rightblock;
845 : : CHECK_END(rightblock->rightlink);
846 : 499 : rightblock->rightlink = b;
847 : 499 : rightblock = b;
848 : : MARK_END(b->rightlink);
849 : 499 : rightindex = -1;
850 : 499 : b = NULL;
851 : : }
852 : : assert (rightindex < BLOCKLEN - 1);
853 : : {
854 : : PyObject **src, **dest;
855 : 1660 : Py_ssize_t m = -n;
856 : :
857 [ + + ]: 1660 : if (m > BLOCKLEN - leftindex)
858 : 791 : m = BLOCKLEN - leftindex;
859 [ + + ]: 1660 : if (m > BLOCKLEN - 1 - rightindex)
860 : 483 : m = BLOCKLEN - 1 - rightindex;
861 : : assert (m > 0 && m <= len);
862 : 1660 : src = &leftblock->data[leftindex];
863 : 1660 : dest = &rightblock->data[rightindex + 1];
864 : 1660 : leftindex += m;
865 : 1660 : rightindex += m;
866 : 1660 : n += m;
867 : : do {
868 : 31669 : *(dest++) = *(src++);
869 [ + + ]: 31669 : } while (--m);
870 : : }
871 [ + + ]: 1660 : if (leftindex == BLOCKLEN) {
872 : : assert(leftblock != rightblock);
873 : : assert(b == NULL);
874 : 495 : b = leftblock;
875 : : CHECK_NOT_END(leftblock->rightlink);
876 : 495 : leftblock = leftblock->rightlink;
877 : : MARK_END(leftblock->leftlink);
878 : 495 : leftindex = 0;
879 : : }
880 : : }
881 : 134369 : rv = 0;
882 : 134369 : done:
883 [ + + ]: 134369 : if (b != NULL)
884 : 1946 : freeblock(deque, b);
885 : 134369 : deque->leftblock = leftblock;
886 : 134369 : deque->rightblock = rightblock;
887 : 134369 : deque->leftindex = leftindex;
888 : 134369 : deque->rightindex = rightindex;
889 : :
890 : 134369 : return rv;
891 : : }
892 : :
893 : : static PyObject *
894 : 100445 : deque_rotate(dequeobject *deque, PyObject *const *args, Py_ssize_t nargs)
895 : : {
896 : 100445 : Py_ssize_t n=1;
897 : :
898 [ + - + + : 100445 : if (!_PyArg_CheckPositional("deque.rotate", nargs, 0, 1)) {
+ - ]
899 : 1 : return NULL;
900 : : }
901 [ + + ]: 100444 : if (nargs) {
902 : 325 : PyObject *index = _PyNumber_Index(args[0]);
903 [ + + ]: 325 : if (index == NULL) {
904 : 1 : return NULL;
905 : : }
906 : 324 : n = PyLong_AsSsize_t(index);
907 : 324 : Py_DECREF(index);
908 [ + + - + ]: 324 : if (n == -1 && PyErr_Occurred()) {
909 : 0 : return NULL;
910 : : }
911 : : }
912 : :
913 [ + - ]: 100443 : if (!_deque_rotate(deque, n))
914 : 100443 : Py_RETURN_NONE;
915 : 0 : return NULL;
916 : : }
917 : :
918 : : PyDoc_STRVAR(rotate_doc,
919 : : "Rotate the deque n steps to the right (default n=1). If n is negative, rotates left.");
920 : :
921 : : static PyObject *
922 : 1000 : deque_reverse(dequeobject *deque, PyObject *unused)
923 : : {
924 : 1000 : block *leftblock = deque->leftblock;
925 : 1000 : block *rightblock = deque->rightblock;
926 : 1000 : Py_ssize_t leftindex = deque->leftindex;
927 : 1000 : Py_ssize_t rightindex = deque->rightindex;
928 : 1000 : Py_ssize_t n = Py_SIZE(deque) >> 1;
929 : : PyObject *tmp;
930 : :
931 [ + + ]: 125500 : while (--n >= 0) {
932 : : /* Validate that pointers haven't met in the middle */
933 : : assert(leftblock != rightblock || leftindex < rightindex);
934 : : CHECK_NOT_END(leftblock);
935 : : CHECK_NOT_END(rightblock);
936 : :
937 : : /* Swap */
938 : 124500 : tmp = leftblock->data[leftindex];
939 : 124500 : leftblock->data[leftindex] = rightblock->data[rightindex];
940 : 124500 : rightblock->data[rightindex] = tmp;
941 : :
942 : : /* Advance left block/index pair */
943 : 124500 : leftindex++;
944 [ + + ]: 124500 : if (leftindex == BLOCKLEN) {
945 : 1476 : leftblock = leftblock->rightlink;
946 : 1476 : leftindex = 0;
947 : : }
948 : :
949 : : /* Step backwards with the right block/index pair */
950 : 124500 : rightindex--;
951 [ + + ]: 124500 : if (rightindex < 0) {
952 : 1946 : rightblock = rightblock->leftlink;
953 : 1946 : rightindex = BLOCKLEN - 1;
954 : : }
955 : : }
956 : 1000 : Py_RETURN_NONE;
957 : : }
958 : :
959 : : PyDoc_STRVAR(reverse_doc,
960 : : "D.reverse() -- reverse *IN PLACE*");
961 : :
962 : : static PyObject *
963 : 93 : deque_count(dequeobject *deque, PyObject *v)
964 : : {
965 : 93 : block *b = deque->leftblock;
966 : 93 : Py_ssize_t index = deque->leftindex;
967 : 93 : Py_ssize_t n = Py_SIZE(deque);
968 : 93 : Py_ssize_t count = 0;
969 : 93 : size_t start_state = deque->state;
970 : : PyObject *item;
971 : : int cmp;
972 : :
973 [ + + ]: 130544 : while (--n >= 0) {
974 : : CHECK_NOT_END(b);
975 : 130456 : item = b->data[index];
976 : 130456 : Py_INCREF(item);
977 : 130456 : cmp = PyObject_RichCompareBool(item, v, Py_EQ);
978 : 130456 : Py_DECREF(item);
979 [ + + ]: 130456 : if (cmp < 0)
980 : 3 : return NULL;
981 : 130453 : count += cmp;
982 : :
983 [ + + ]: 130453 : if (start_state != deque->state) {
984 : 2 : PyErr_SetString(PyExc_RuntimeError,
985 : : "deque mutated during iteration");
986 : 2 : return NULL;
987 : : }
988 : :
989 : : /* Advance left block/index pair */
990 : 130451 : index++;
991 [ + + ]: 130451 : if (index == BLOCKLEN) {
992 : 2028 : b = b->rightlink;
993 : 2028 : index = 0;
994 : : }
995 : : }
996 : 88 : return PyLong_FromSsize_t(count);
997 : : }
998 : :
999 : : PyDoc_STRVAR(count_doc,
1000 : : "D.count(value) -> integer -- return number of occurrences of value");
1001 : :
1002 : : static int
1003 : 1226 : deque_contains(dequeobject *deque, PyObject *v)
1004 : : {
1005 : 1226 : block *b = deque->leftblock;
1006 : 1226 : Py_ssize_t index = deque->leftindex;
1007 : 1226 : Py_ssize_t n = Py_SIZE(deque);
1008 : 1226 : size_t start_state = deque->state;
1009 : : PyObject *item;
1010 : : int cmp;
1011 : :
1012 [ + + ]: 206609 : while (--n >= 0) {
1013 : : CHECK_NOT_END(b);
1014 : 206102 : item = b->data[index];
1015 : 206102 : Py_INCREF(item);
1016 : 206102 : cmp = PyObject_RichCompareBool(item, v, Py_EQ);
1017 : 206102 : Py_DECREF(item);
1018 [ + + ]: 206102 : if (cmp) {
1019 : 717 : return cmp;
1020 : : }
1021 [ + + ]: 205385 : if (start_state != deque->state) {
1022 : 2 : PyErr_SetString(PyExc_RuntimeError,
1023 : : "deque mutated during iteration");
1024 : 2 : return -1;
1025 : : }
1026 : 205383 : index++;
1027 [ + + ]: 205383 : if (index == BLOCKLEN) {
1028 : 3108 : b = b->rightlink;
1029 : 3108 : index = 0;
1030 : : }
1031 : : }
1032 : 507 : return 0;
1033 : : }
1034 : :
1035 : : static Py_ssize_t
1036 : 473925 : deque_len(dequeobject *deque)
1037 : : {
1038 : 473925 : return Py_SIZE(deque);
1039 : : }
1040 : :
1041 : : static PyObject *
1042 : 67655 : deque_index(dequeobject *deque, PyObject *const *args, Py_ssize_t nargs)
1043 : : {
1044 : 67655 : Py_ssize_t i, n, start=0, stop=Py_SIZE(deque);
1045 : : PyObject *v, *item;
1046 : 67655 : block *b = deque->leftblock;
1047 : 67655 : Py_ssize_t index = deque->leftindex;
1048 : 67655 : size_t start_state = deque->state;
1049 : : int cmp;
1050 : :
1051 [ + + ]: 67655 : if (!_PyArg_ParseStack(args, nargs, "O|O&O&:index", &v,
1052 : : _PyEval_SliceIndexNotNone, &start,
1053 : : _PyEval_SliceIndexNotNone, &stop)) {
1054 : 1 : return NULL;
1055 : : }
1056 : :
1057 [ + + ]: 67654 : if (start < 0) {
1058 : 33626 : start += Py_SIZE(deque);
1059 [ + + ]: 33626 : if (start < 0)
1060 : 18863 : start = 0;
1061 : : }
1062 [ + + ]: 67654 : if (stop < 0) {
1063 : 33624 : stop += Py_SIZE(deque);
1064 [ + + ]: 33624 : if (stop < 0)
1065 : 18863 : stop = 0;
1066 : : }
1067 [ + + ]: 67654 : if (stop > Py_SIZE(deque))
1068 : 18042 : stop = Py_SIZE(deque);
1069 [ + + ]: 67654 : if (start > stop)
1070 : 32571 : start = stop;
1071 : : assert(0 <= start && start <= stop && stop <= Py_SIZE(deque));
1072 : :
1073 [ + + ]: 68654 : for (i=0 ; i < start - BLOCKLEN ; i += BLOCKLEN) {
1074 : 1000 : b = b->rightlink;
1075 : : }
1076 [ + + ]: 381058 : for ( ; i < start ; i++) {
1077 : 313404 : index++;
1078 [ + + ]: 313404 : if (index == BLOCKLEN) {
1079 : 94 : b = b->rightlink;
1080 : 94 : index = 0;
1081 : : }
1082 : : }
1083 : :
1084 : 67654 : n = stop - i;
1085 [ + + ]: 223683 : while (--n >= 0) {
1086 : : CHECK_NOT_END(b);
1087 : 175767 : item = b->data[index];
1088 : 175767 : cmp = PyObject_RichCompareBool(item, v, Py_EQ);
1089 [ + + ]: 175767 : if (cmp > 0)
1090 : 19727 : return PyLong_FromSsize_t(stop - n - 1);
1091 [ + + ]: 156040 : if (cmp < 0)
1092 : 6 : return NULL;
1093 [ + + ]: 156034 : if (start_state != deque->state) {
1094 : 5 : PyErr_SetString(PyExc_RuntimeError,
1095 : : "deque mutated during iteration");
1096 : 5 : return NULL;
1097 : : }
1098 : 156029 : index++;
1099 [ + + ]: 156029 : if (index == BLOCKLEN) {
1100 : 562 : b = b->rightlink;
1101 : 562 : index = 0;
1102 : : }
1103 : : }
1104 : 47916 : PyErr_Format(PyExc_ValueError, "%R is not in deque", v);
1105 : 47916 : return NULL;
1106 : : }
1107 : :
1108 : : PyDoc_STRVAR(index_doc,
1109 : : "D.index(value, [start, [stop]]) -> integer -- return first index of value.\n"
1110 : : "Raises ValueError if the value is not present.");
1111 : :
1112 : : /* insert(), remove(), and delitem() are implemented in terms of
1113 : : rotate() for simplicity and reasonable performance near the end
1114 : : points. If for some reason these methods become popular, it is not
1115 : : hard to re-implement this using direct data movement (similar to
1116 : : the code used in list slice assignments) and achieve a performance
1117 : : boost (by moving each pointer only once instead of twice).
1118 : : */
1119 : :
1120 : : static PyObject *
1121 : 65 : deque_insert(dequeobject *deque, PyObject *const *args, Py_ssize_t nargs)
1122 : : {
1123 : : Py_ssize_t index;
1124 : 65 : Py_ssize_t n = Py_SIZE(deque);
1125 : : PyObject *value;
1126 : : PyObject *rv;
1127 : :
1128 [ - + ]: 65 : if (!_PyArg_ParseStack(args, nargs, "nO:insert", &index, &value)) {
1129 : 0 : return NULL;
1130 : : }
1131 : :
1132 [ + + ]: 65 : if (deque->maxlen == Py_SIZE(deque)) {
1133 : 1 : PyErr_SetString(PyExc_IndexError, "deque already at its maximum size");
1134 : 1 : return NULL;
1135 : : }
1136 [ + + ]: 64 : if (index >= n)
1137 : 14 : return deque_append(deque, value);
1138 [ + + + + ]: 50 : if (index <= -n || index == 0)
1139 : 18 : return deque_appendleft(deque, value);
1140 [ - + ]: 32 : if (_deque_rotate(deque, -index))
1141 : 0 : return NULL;
1142 [ + + ]: 32 : if (index < 0)
1143 : 16 : rv = deque_append(deque, value);
1144 : : else
1145 : 16 : rv = deque_appendleft(deque, value);
1146 [ - + ]: 32 : if (rv == NULL)
1147 : 0 : return NULL;
1148 : 32 : Py_DECREF(rv);
1149 [ - + ]: 32 : if (_deque_rotate(deque, index))
1150 : 0 : return NULL;
1151 : 32 : Py_RETURN_NONE;
1152 : : }
1153 : :
1154 : : PyDoc_STRVAR(insert_doc,
1155 : : "D.insert(index, object) -- insert object before index");
1156 : :
1157 : : PyDoc_STRVAR(remove_doc,
1158 : : "D.remove(value) -- remove first occurrence of value.");
1159 : :
1160 : : static int
1161 : 1356858 : valid_index(Py_ssize_t i, Py_ssize_t limit)
1162 : : {
1163 : : /* The cast to size_t lets us use just a single comparison
1164 : : to check whether i is in the range: 0 <= i < limit */
1165 : 1356858 : return (size_t) i < (size_t) limit;
1166 : : }
1167 : :
1168 : : static PyObject *
1169 : 106588 : deque_item(dequeobject *deque, Py_ssize_t i)
1170 : : {
1171 : : block *b;
1172 : : PyObject *item;
1173 : 106588 : Py_ssize_t n, index=i;
1174 : :
1175 [ + + ]: 106588 : if (!valid_index(i, Py_SIZE(deque))) {
1176 : 3 : PyErr_SetString(PyExc_IndexError, "deque index out of range");
1177 : 3 : return NULL;
1178 : : }
1179 : :
1180 [ + + ]: 106585 : if (i == 0) {
1181 : 42306 : i = deque->leftindex;
1182 : 42306 : b = deque->leftblock;
1183 [ + + ]: 64279 : } else if (i == Py_SIZE(deque) - 1) {
1184 : 443 : i = deque->rightindex;
1185 : 443 : b = deque->rightblock;
1186 : : } else {
1187 : 63836 : i += deque->leftindex;
1188 : 63836 : n = (Py_ssize_t)((size_t) i / BLOCKLEN);
1189 : 63836 : i = (Py_ssize_t)((size_t) i % BLOCKLEN);
1190 [ + + ]: 63836 : if (index < (Py_SIZE(deque) >> 1)) {
1191 : 31770 : b = deque->leftblock;
1192 [ + + ]: 51400 : while (--n >= 0)
1193 : 19630 : b = b->rightlink;
1194 : : } else {
1195 : 32066 : n = (Py_ssize_t)(
1196 : 32066 : ((size_t)(deque->leftindex + Py_SIZE(deque) - 1))
1197 : 32066 : / BLOCKLEN - n);
1198 : 32066 : b = deque->rightblock;
1199 [ + + ]: 51725 : while (--n >= 0)
1200 : 19659 : b = b->leftlink;
1201 : : }
1202 : : }
1203 : 106585 : item = b->data[i];
1204 : 106585 : Py_INCREF(item);
1205 : 106585 : return item;
1206 : : }
1207 : :
1208 : : static int
1209 : 43837 : deque_del_item(dequeobject *deque, Py_ssize_t i)
1210 : : {
1211 : : PyObject *item;
1212 : : int rv;
1213 : :
1214 : : assert (i >= 0 && i < Py_SIZE(deque));
1215 [ - + ]: 43837 : if (_deque_rotate(deque, -i))
1216 : 0 : return -1;
1217 : 43837 : item = deque_popleft(deque, NULL);
1218 : 43837 : rv = _deque_rotate(deque, i);
1219 : : assert (item != NULL);
1220 : 43837 : Py_DECREF(item);
1221 : 43837 : return rv;
1222 : : }
1223 : :
1224 : : static PyObject *
1225 : 40315 : deque_remove(dequeobject *deque, PyObject *value)
1226 : : {
1227 : : PyObject *item;
1228 : 40315 : block *b = deque->leftblock;
1229 : 40315 : Py_ssize_t i, n = Py_SIZE(deque), index = deque->leftindex;
1230 : 40315 : size_t start_state = deque->state;
1231 : : int cmp, rv;
1232 : :
1233 [ + + ]: 40351 : for (i = 0 ; i < n; i++) {
1234 : 40342 : item = b->data[index];
1235 : 40342 : Py_INCREF(item);
1236 : 40342 : cmp = PyObject_RichCompareBool(item, value, Py_EQ);
1237 : 40342 : Py_DECREF(item);
1238 [ + + ]: 40342 : if (cmp < 0) {
1239 : 1 : return NULL;
1240 : : }
1241 [ + + ]: 40341 : if (start_state != deque->state) {
1242 : 2 : PyErr_SetString(PyExc_IndexError,
1243 : : "deque mutated during iteration");
1244 : 2 : return NULL;
1245 : : }
1246 [ + + ]: 40339 : if (cmp > 0) {
1247 : 40303 : break;
1248 : : }
1249 : 36 : index++;
1250 [ - + ]: 36 : if (index == BLOCKLEN) {
1251 : 0 : b = b->rightlink;
1252 : 0 : index = 0;
1253 : : }
1254 : : }
1255 [ + + ]: 40312 : if (i == n) {
1256 : 9 : PyErr_Format(PyExc_ValueError, "%R is not in deque", value);
1257 : 9 : return NULL;
1258 : : }
1259 : 40303 : rv = deque_del_item(deque, i);
1260 [ - + ]: 40303 : if (rv == -1) {
1261 : 0 : return NULL;
1262 : : }
1263 : 40303 : Py_RETURN_NONE;
1264 : : }
1265 : :
1266 : : static int
1267 : 8548 : deque_ass_item(dequeobject *deque, Py_ssize_t i, PyObject *v)
1268 : : {
1269 : : PyObject *old_value;
1270 : : block *b;
1271 : 8548 : Py_ssize_t n, len=Py_SIZE(deque), halflen=(len+1)>>1, index=i;
1272 : :
1273 [ + + ]: 8548 : if (!valid_index(i, len)) {
1274 : 2 : PyErr_SetString(PyExc_IndexError, "deque index out of range");
1275 : 2 : return -1;
1276 : : }
1277 [ + + ]: 8546 : if (v == NULL)
1278 : 3534 : return deque_del_item(deque, i);
1279 : :
1280 : 5012 : i += deque->leftindex;
1281 : 5012 : n = (Py_ssize_t)((size_t) i / BLOCKLEN);
1282 : 5012 : i = (Py_ssize_t)((size_t) i % BLOCKLEN);
1283 [ + + ]: 5012 : if (index <= halflen) {
1284 : 2537 : b = deque->leftblock;
1285 [ + + ]: 3491 : while (--n >= 0)
1286 : 954 : b = b->rightlink;
1287 : : } else {
1288 : 2475 : n = (Py_ssize_t)(
1289 : 2475 : ((size_t)(deque->leftindex + Py_SIZE(deque) - 1))
1290 : 2475 : / BLOCKLEN - n);
1291 : 2475 : b = deque->rightblock;
1292 [ + + ]: 5375 : while (--n >= 0)
1293 : 2900 : b = b->leftlink;
1294 : : }
1295 : 5012 : Py_INCREF(v);
1296 : 5012 : old_value = b->data[i];
1297 : 5012 : b->data[i] = v;
1298 : 5012 : Py_DECREF(old_value);
1299 : 5012 : return 0;
1300 : : }
1301 : :
1302 : : static void
1303 : 50259 : deque_dealloc(dequeobject *deque)
1304 : : {
1305 : : Py_ssize_t i;
1306 : :
1307 : 50259 : PyObject_GC_UnTrack(deque);
1308 [ + + ]: 50259 : if (deque->weakreflist != NULL)
1309 : 1 : PyObject_ClearWeakRefs((PyObject *) deque);
1310 [ + - ]: 50259 : if (deque->leftblock != NULL) {
1311 : 50259 : deque_clear(deque);
1312 : : assert(deque->leftblock != NULL);
1313 : 50259 : freeblock(deque, deque->leftblock);
1314 : : }
1315 : 50259 : deque->leftblock = NULL;
1316 : 50259 : deque->rightblock = NULL;
1317 [ + + ]: 105044 : for (i=0 ; i < deque->numfreeblocks ; i++) {
1318 : 54785 : PyMem_Free(deque->freeblocks[i]);
1319 : : }
1320 : 50259 : Py_TYPE(deque)->tp_free(deque);
1321 : 50259 : }
1322 : :
1323 : : static int
1324 : 202095 : deque_traverse(dequeobject *deque, visitproc visit, void *arg)
1325 : : {
1326 : : block *b;
1327 : : PyObject *item;
1328 : : Py_ssize_t index;
1329 : 202095 : Py_ssize_t indexlo = deque->leftindex;
1330 : : Py_ssize_t indexhigh;
1331 : :
1332 [ + + ]: 202445 : for (b = deque->leftblock; b != deque->rightblock; b = b->rightlink) {
1333 [ + + ]: 17162 : for (index = indexlo; index < BLOCKLEN ; index++) {
1334 : 16812 : item = b->data[index];
1335 [ + - - + ]: 16812 : Py_VISIT(item);
1336 : : }
1337 : 350 : indexlo = 0;
1338 : : }
1339 : 202095 : indexhigh = deque->rightindex;
1340 [ + + ]: 212012 : for (index = indexlo; index <= indexhigh; index++) {
1341 : 9917 : item = b->data[index];
1342 [ + - - + ]: 9917 : Py_VISIT(item);
1343 : : }
1344 : 202095 : return 0;
1345 : : }
1346 : :
1347 : : static PyObject *
1348 : 115 : deque_reduce(dequeobject *deque, PyObject *Py_UNUSED(ignored))
1349 : : {
1350 : : PyObject *state, *it;
1351 : :
1352 : 115 : state = _PyObject_GetState((PyObject *)deque);
1353 [ - + ]: 115 : if (state == NULL) {
1354 : 0 : return NULL;
1355 : : }
1356 : :
1357 : 115 : it = PyObject_GetIter((PyObject *)deque);
1358 [ + + ]: 115 : if (it == NULL) {
1359 : 12 : Py_DECREF(state);
1360 : 12 : return NULL;
1361 : : }
1362 : :
1363 [ + + ]: 103 : if (deque->maxlen < 0) {
1364 : 67 : return Py_BuildValue("O()NN", Py_TYPE(deque), state, it);
1365 : : }
1366 : : else {
1367 : 36 : return Py_BuildValue("O(()n)NN", Py_TYPE(deque), deque->maxlen, state, it);
1368 : : }
1369 : : }
1370 : :
1371 : : PyDoc_STRVAR(reduce_doc, "Return state information for pickling.");
1372 : :
1373 : : static PyObject *
1374 : 34 : deque_repr(PyObject *deque)
1375 : : {
1376 : : PyObject *aslist, *result;
1377 : : int i;
1378 : :
1379 : 34 : i = Py_ReprEnter(deque);
1380 [ + + ]: 34 : if (i != 0) {
1381 [ - + ]: 2 : if (i < 0)
1382 : 0 : return NULL;
1383 : 2 : return PyUnicode_FromString("[...]");
1384 : : }
1385 : :
1386 : 32 : aslist = PySequence_List(deque);
1387 [ - + ]: 32 : if (aslist == NULL) {
1388 : 0 : Py_ReprLeave(deque);
1389 : 0 : return NULL;
1390 : : }
1391 [ + + ]: 32 : if (((dequeobject *)deque)->maxlen >= 0)
1392 : 11 : result = PyUnicode_FromFormat("%s(%R, maxlen=%zd)",
1393 : : _PyType_Name(Py_TYPE(deque)), aslist,
1394 : : ((dequeobject *)deque)->maxlen);
1395 : : else
1396 : 21 : result = PyUnicode_FromFormat("%s(%R)",
1397 : : _PyType_Name(Py_TYPE(deque)), aslist);
1398 : 32 : Py_ReprLeave(deque);
1399 : 32 : Py_DECREF(aslist);
1400 : 32 : return result;
1401 : : }
1402 : :
1403 : : static PyObject *
1404 : 286 : deque_richcompare(PyObject *v, PyObject *w, int op)
1405 : : {
1406 : 286 : PyObject *it1=NULL, *it2=NULL, *x, *y;
1407 : : Py_ssize_t vs, ws;
1408 : 286 : int b, cmp=-1;
1409 : :
1410 [ + - + + ]: 572 : if (!PyObject_TypeCheck(v, &deque_type) ||
1411 : 286 : !PyObject_TypeCheck(w, &deque_type)) {
1412 : 2 : Py_RETURN_NOTIMPLEMENTED;
1413 : : }
1414 : :
1415 : : /* Shortcuts */
1416 : 284 : vs = Py_SIZE((dequeobject *)v);
1417 : 284 : ws = Py_SIZE((dequeobject *)w);
1418 [ + + ]: 284 : if (op == Py_EQ) {
1419 [ + + ]: 240 : if (v == w)
1420 : 2 : Py_RETURN_TRUE;
1421 [ + + ]: 238 : if (vs != ws)
1422 : 10 : Py_RETURN_FALSE;
1423 : : }
1424 [ + + ]: 272 : if (op == Py_NE) {
1425 [ + + ]: 12 : if (v == w)
1426 : 1 : Py_RETURN_FALSE;
1427 [ + + ]: 11 : if (vs != ws)
1428 : 10 : Py_RETURN_TRUE;
1429 : : }
1430 : :
1431 : : /* Search for the first index where items are different */
1432 : 261 : it1 = PyObject_GetIter(v);
1433 [ - + ]: 261 : if (it1 == NULL)
1434 : 0 : goto done;
1435 : 261 : it2 = PyObject_GetIter(w);
1436 [ + - ]: 261 : if (it2 == NULL)
1437 : 0 : goto done;
1438 : : for (;;) {
1439 : 17034 : x = PyIter_Next(it1);
1440 [ + + - + ]: 17034 : if (x == NULL && PyErr_Occurred())
1441 : 0 : goto done;
1442 : 17034 : y = PyIter_Next(it2);
1443 [ + + + - ]: 17034 : if (x == NULL || y == NULL)
1444 : : break;
1445 : 16773 : b = PyObject_RichCompareBool(x, y, Py_EQ);
1446 [ - + ]: 16773 : if (b == 0) {
1447 : 0 : cmp = PyObject_RichCompareBool(x, y, op);
1448 : 0 : Py_DECREF(x);
1449 : 0 : Py_DECREF(y);
1450 : 0 : goto done;
1451 : : }
1452 : 16773 : Py_DECREF(x);
1453 : 16773 : Py_DECREF(y);
1454 [ - + ]: 16773 : if (b < 0)
1455 : 0 : goto done;
1456 : : }
1457 : : /* We reached the end of one deque or both */
1458 : 261 : Py_XDECREF(x);
1459 : 261 : Py_XDECREF(y);
1460 [ - + ]: 261 : if (PyErr_Occurred())
1461 : 0 : goto done;
1462 [ + + + + : 261 : switch (op) {
+ + - ]
1463 : 8 : case Py_LT: cmp = y != NULL; break; /* if w was longer */
1464 : 8 : case Py_LE: cmp = x == NULL; break; /* if v was not longer */
1465 : 228 : case Py_EQ: cmp = x == y; break; /* if we reached the end of both */
1466 : 1 : case Py_NE: cmp = x != y; break; /* if one deque continues */
1467 : 8 : case Py_GT: cmp = x != NULL; break; /* if v was longer */
1468 : 8 : case Py_GE: cmp = y == NULL; break; /* if w was not longer */
1469 : : }
1470 : :
1471 : 261 : done:
1472 : 261 : Py_XDECREF(it1);
1473 : 261 : Py_XDECREF(it2);
1474 [ + + ]: 261 : if (cmp == 1)
1475 : 244 : Py_RETURN_TRUE;
1476 [ + - ]: 17 : if (cmp == 0)
1477 : 17 : Py_RETURN_FALSE;
1478 : 0 : return NULL;
1479 : : }
1480 : :
1481 : : static int
1482 : 50323 : deque_init(dequeobject *deque, PyObject *args, PyObject *kwdargs)
1483 : : {
1484 : 50323 : PyObject *iterable = NULL;
1485 : 50323 : PyObject *maxlenobj = NULL;
1486 : 50323 : Py_ssize_t maxlen = -1;
1487 : 50323 : char *kwlist[] = {"iterable", "maxlen", 0};
1488 : :
1489 [ + + + - ]: 50323 : if (kwdargs == NULL && PyTuple_GET_SIZE(args) <= 2) {
1490 [ + + ]: 48929 : if (PyTuple_GET_SIZE(args) > 0) {
1491 : 1277 : iterable = PyTuple_GET_ITEM(args, 0);
1492 : : }
1493 [ + + ]: 48929 : if (PyTuple_GET_SIZE(args) > 1) {
1494 : 103 : maxlenobj = PyTuple_GET_ITEM(args, 1);
1495 : : }
1496 : : } else {
1497 [ + + ]: 1394 : if (!PyArg_ParseTupleAndKeywords(args, kwdargs, "|OO:deque", kwlist,
1498 : : &iterable, &maxlenobj))
1499 : 2 : return -1;
1500 : : }
1501 [ + + + + ]: 50321 : if (maxlenobj != NULL && maxlenobj != Py_None) {
1502 : 1460 : maxlen = PyLong_AsSsize_t(maxlenobj);
1503 [ + + - + ]: 1460 : if (maxlen == -1 && PyErr_Occurred())
1504 : 0 : return -1;
1505 [ + + ]: 1460 : if (maxlen < 0) {
1506 : 2 : PyErr_SetString(PyExc_ValueError, "maxlen must be non-negative");
1507 : 2 : return -1;
1508 : : }
1509 : : }
1510 : 50319 : deque->maxlen = maxlen;
1511 [ + + ]: 50319 : if (Py_SIZE(deque) > 0)
1512 : 2 : deque_clear(deque);
1513 [ + + ]: 50319 : if (iterable != NULL) {
1514 : 2659 : PyObject *rv = deque_extend(deque, iterable);
1515 [ + + ]: 2659 : if (rv == NULL)
1516 : 31 : return -1;
1517 : 2628 : Py_DECREF(rv);
1518 : : }
1519 : 50288 : return 0;
1520 : : }
1521 : :
1522 : : static PyObject *
1523 : 5 : deque_sizeof(dequeobject *deque, void *unused)
1524 : : {
1525 : : Py_ssize_t res;
1526 : : Py_ssize_t blocks;
1527 : :
1528 : 5 : res = _PyObject_SIZE(Py_TYPE(deque));
1529 : 5 : blocks = (size_t)(deque->leftindex + Py_SIZE(deque) + BLOCKLEN - 1) / BLOCKLEN;
1530 : : assert(deque->leftindex + Py_SIZE(deque) - 1 ==
1531 : : (blocks - 1) * BLOCKLEN + deque->rightindex);
1532 : 5 : res += blocks * sizeof(block);
1533 : 5 : return PyLong_FromSsize_t(res);
1534 : : }
1535 : :
1536 : : PyDoc_STRVAR(sizeof_doc,
1537 : : "D.__sizeof__() -- size of D in memory, in bytes");
1538 : :
1539 : : static PyObject *
1540 : 197 : deque_get_maxlen(dequeobject *deque, void *Py_UNUSED(ignored))
1541 : : {
1542 [ + + ]: 197 : if (deque->maxlen < 0)
1543 : 72 : Py_RETURN_NONE;
1544 : 125 : return PyLong_FromSsize_t(deque->maxlen);
1545 : : }
1546 : :
1547 : :
1548 : : /* deque object ********************************************************/
1549 : :
1550 : : static PyGetSetDef deque_getset[] = {
1551 : : {"maxlen", (getter)deque_get_maxlen, (setter)NULL,
1552 : : "maximum size of a deque or None if unbounded"},
1553 : : {0}
1554 : : };
1555 : :
1556 : : static PySequenceMethods deque_as_sequence = {
1557 : : (lenfunc)deque_len, /* sq_length */
1558 : : (binaryfunc)deque_concat, /* sq_concat */
1559 : : (ssizeargfunc)deque_repeat, /* sq_repeat */
1560 : : (ssizeargfunc)deque_item, /* sq_item */
1561 : : 0, /* sq_slice */
1562 : : (ssizeobjargproc)deque_ass_item, /* sq_ass_item */
1563 : : 0, /* sq_ass_slice */
1564 : : (objobjproc)deque_contains, /* sq_contains */
1565 : : (binaryfunc)deque_inplace_concat, /* sq_inplace_concat */
1566 : : (ssizeargfunc)deque_inplace_repeat, /* sq_inplace_repeat */
1567 : : };
1568 : :
1569 : : static PyObject *deque_iter(dequeobject *deque);
1570 : : static PyObject *deque_reviter(dequeobject *deque, PyObject *Py_UNUSED(ignored));
1571 : : PyDoc_STRVAR(reversed_doc,
1572 : : "D.__reversed__() -- return a reverse iterator over the deque");
1573 : :
1574 : : static PyMethodDef deque_methods[] = {
1575 : : {"append", (PyCFunction)deque_append,
1576 : : METH_O, append_doc},
1577 : : {"appendleft", (PyCFunction)deque_appendleft,
1578 : : METH_O, appendleft_doc},
1579 : : {"clear", (PyCFunction)deque_clearmethod,
1580 : : METH_NOARGS, clear_doc},
1581 : : {"__copy__", deque_copy,
1582 : : METH_NOARGS, copy_doc},
1583 : : {"copy", deque_copy,
1584 : : METH_NOARGS, copy_doc},
1585 : : {"count", (PyCFunction)deque_count,
1586 : : METH_O, count_doc},
1587 : : {"extend", (PyCFunction)deque_extend,
1588 : : METH_O, extend_doc},
1589 : : {"extendleft", (PyCFunction)deque_extendleft,
1590 : : METH_O, extendleft_doc},
1591 : : {"index", _PyCFunction_CAST(deque_index),
1592 : : METH_FASTCALL, index_doc},
1593 : : {"insert", _PyCFunction_CAST(deque_insert),
1594 : : METH_FASTCALL, insert_doc},
1595 : : {"pop", (PyCFunction)deque_pop,
1596 : : METH_NOARGS, pop_doc},
1597 : : {"popleft", (PyCFunction)deque_popleft,
1598 : : METH_NOARGS, popleft_doc},
1599 : : {"__reduce__", (PyCFunction)deque_reduce,
1600 : : METH_NOARGS, reduce_doc},
1601 : : {"remove", (PyCFunction)deque_remove,
1602 : : METH_O, remove_doc},
1603 : : {"__reversed__", (PyCFunction)deque_reviter,
1604 : : METH_NOARGS, reversed_doc},
1605 : : {"reverse", (PyCFunction)deque_reverse,
1606 : : METH_NOARGS, reverse_doc},
1607 : : {"rotate", _PyCFunction_CAST(deque_rotate),
1608 : : METH_FASTCALL, rotate_doc},
1609 : : {"__sizeof__", (PyCFunction)deque_sizeof,
1610 : : METH_NOARGS, sizeof_doc},
1611 : : {"__class_getitem__", Py_GenericAlias,
1612 : : METH_O|METH_CLASS, PyDoc_STR("See PEP 585")},
1613 : : {NULL, NULL} /* sentinel */
1614 : : };
1615 : :
1616 : : PyDoc_STRVAR(deque_doc,
1617 : : "deque([iterable[, maxlen]]) --> deque object\n\
1618 : : \n\
1619 : : A list-like sequence optimized for data accesses near its endpoints.");
1620 : :
1621 : : static PyTypeObject deque_type = {
1622 : : PyVarObject_HEAD_INIT(NULL, 0)
1623 : : "collections.deque", /* tp_name */
1624 : : sizeof(dequeobject), /* tp_basicsize */
1625 : : 0, /* tp_itemsize */
1626 : : /* methods */
1627 : : (destructor)deque_dealloc, /* tp_dealloc */
1628 : : 0, /* tp_vectorcall_offset */
1629 : : 0, /* tp_getattr */
1630 : : 0, /* tp_setattr */
1631 : : 0, /* tp_as_async */
1632 : : deque_repr, /* tp_repr */
1633 : : 0, /* tp_as_number */
1634 : : &deque_as_sequence, /* tp_as_sequence */
1635 : : 0, /* tp_as_mapping */
1636 : : PyObject_HashNotImplemented, /* tp_hash */
1637 : : 0, /* tp_call */
1638 : : 0, /* tp_str */
1639 : : PyObject_GenericGetAttr, /* tp_getattro */
1640 : : 0, /* tp_setattro */
1641 : : 0, /* tp_as_buffer */
1642 : : Py_TPFLAGS_DEFAULT | Py_TPFLAGS_BASETYPE |
1643 : : Py_TPFLAGS_HAVE_GC | Py_TPFLAGS_SEQUENCE,
1644 : : /* tp_flags */
1645 : : deque_doc, /* tp_doc */
1646 : : (traverseproc)deque_traverse, /* tp_traverse */
1647 : : (inquiry)deque_clear, /* tp_clear */
1648 : : (richcmpfunc)deque_richcompare, /* tp_richcompare */
1649 : : offsetof(dequeobject, weakreflist), /* tp_weaklistoffset*/
1650 : : (getiterfunc)deque_iter, /* tp_iter */
1651 : : 0, /* tp_iternext */
1652 : : deque_methods, /* tp_methods */
1653 : : 0, /* tp_members */
1654 : : deque_getset, /* tp_getset */
1655 : : 0, /* tp_base */
1656 : : 0, /* tp_dict */
1657 : : 0, /* tp_descr_get */
1658 : : 0, /* tp_descr_set */
1659 : : 0, /* tp_dictoffset */
1660 : : (initproc)deque_init, /* tp_init */
1661 : : PyType_GenericAlloc, /* tp_alloc */
1662 : : deque_new, /* tp_new */
1663 : : PyObject_GC_Del, /* tp_free */
1664 : : };
1665 : :
1666 : : /*********************** Deque Iterator **************************/
1667 : :
1668 : : typedef struct {
1669 : : PyObject_HEAD
1670 : : block *b;
1671 : : Py_ssize_t index;
1672 : : dequeobject *deque;
1673 : : size_t state; /* state when the iterator is created */
1674 : : Py_ssize_t counter; /* number of items remaining for iteration */
1675 : : } dequeiterobject;
1676 : :
1677 : : static PyTypeObject dequeiter_type;
1678 : :
1679 : : static PyObject *
1680 : 2885 : deque_iter(dequeobject *deque)
1681 : : {
1682 : : dequeiterobject *it;
1683 : :
1684 : 2885 : it = PyObject_GC_New(dequeiterobject, &dequeiter_type);
1685 [ - + ]: 2885 : if (it == NULL)
1686 : 0 : return NULL;
1687 : 2885 : it->b = deque->leftblock;
1688 : 2885 : it->index = deque->leftindex;
1689 : 2885 : Py_INCREF(deque);
1690 : 2885 : it->deque = deque;
1691 : 2885 : it->state = deque->state;
1692 : 2885 : it->counter = Py_SIZE(deque);
1693 : 2885 : PyObject_GC_Track(it);
1694 : 2885 : return (PyObject *)it;
1695 : : }
1696 : :
1697 : : static int
1698 : 6 : dequeiter_traverse(dequeiterobject *dio, visitproc visit, void *arg)
1699 : : {
1700 [ + - - + ]: 6 : Py_VISIT(dio->deque);
1701 : 6 : return 0;
1702 : : }
1703 : :
1704 : : static void
1705 : 2895 : dequeiter_dealloc(dequeiterobject *dio)
1706 : : {
1707 : : /* bpo-31095: UnTrack is needed before calling any callbacks */
1708 : 2895 : PyObject_GC_UnTrack(dio);
1709 : 2895 : Py_XDECREF(dio->deque);
1710 : 2895 : PyObject_GC_Del(dio);
1711 : 2895 : }
1712 : :
1713 : : static PyObject *
1714 : 317861 : dequeiter_next(dequeiterobject *it)
1715 : : {
1716 : : PyObject *item;
1717 : :
1718 [ + + ]: 317861 : if (it->deque->state != it->state) {
1719 : 3 : it->counter = 0;
1720 : 3 : PyErr_SetString(PyExc_RuntimeError,
1721 : : "deque mutated during iteration");
1722 : 3 : return NULL;
1723 : : }
1724 [ + + ]: 317858 : if (it->counter == 0)
1725 : 2794 : return NULL;
1726 : : assert (!(it->b == it->deque->rightblock &&
1727 : : it->index > it->deque->rightindex));
1728 : :
1729 : 315064 : item = it->b->data[it->index];
1730 : 315064 : it->index++;
1731 : 315064 : it->counter--;
1732 [ + + + + ]: 315064 : if (it->index == BLOCKLEN && it->counter > 0) {
1733 : : CHECK_NOT_END(it->b->rightlink);
1734 : 4353 : it->b = it->b->rightlink;
1735 : 4353 : it->index = 0;
1736 : : }
1737 : 315064 : Py_INCREF(item);
1738 : 315064 : return item;
1739 : : }
1740 : :
1741 : : static PyObject *
1742 : 24 : dequeiter_new(PyTypeObject *type, PyObject *args, PyObject *kwds)
1743 : : {
1744 : 24 : Py_ssize_t i, index=0;
1745 : : PyObject *deque;
1746 : : dequeiterobject *it;
1747 [ - + ]: 24 : if (!PyArg_ParseTuple(args, "O!|n", &deque_type, &deque, &index))
1748 : 0 : return NULL;
1749 : : assert(type == &dequeiter_type);
1750 : :
1751 : 24 : it = (dequeiterobject*)deque_iter((dequeobject *)deque);
1752 [ - + ]: 24 : if (!it)
1753 : 0 : return NULL;
1754 : : /* consume items from the queue */
1755 [ + + ]: 2430 : for(i=0; i<index; i++) {
1756 : 2406 : PyObject *item = dequeiter_next(it);
1757 [ + - ]: 2406 : if (item) {
1758 : 2406 : Py_DECREF(item);
1759 : : } else {
1760 [ # # ]: 0 : if (it->counter) {
1761 : 0 : Py_DECREF(it);
1762 : 0 : return NULL;
1763 : : } else
1764 : 0 : break;
1765 : : }
1766 : : }
1767 : 24 : return (PyObject*)it;
1768 : : }
1769 : :
1770 : : static PyObject *
1771 : 61 : dequeiter_len(dequeiterobject *it, PyObject *Py_UNUSED(ignored))
1772 : : {
1773 : 61 : return PyLong_FromSsize_t(it->counter);
1774 : : }
1775 : :
1776 : : PyDoc_STRVAR(length_hint_doc, "Private method returning an estimate of len(list(it)).");
1777 : :
1778 : : static PyObject *
1779 : 24 : dequeiter_reduce(dequeiterobject *it, PyObject *Py_UNUSED(ignored))
1780 : : {
1781 : 24 : return Py_BuildValue("O(On)", Py_TYPE(it), it->deque, Py_SIZE(it->deque) - it->counter);
1782 : : }
1783 : :
1784 : : static PyMethodDef dequeiter_methods[] = {
1785 : : {"__length_hint__", (PyCFunction)dequeiter_len, METH_NOARGS, length_hint_doc},
1786 : : {"__reduce__", (PyCFunction)dequeiter_reduce, METH_NOARGS, reduce_doc},
1787 : : {NULL, NULL} /* sentinel */
1788 : : };
1789 : :
1790 : : static PyTypeObject dequeiter_type = {
1791 : : PyVarObject_HEAD_INIT(NULL, 0)
1792 : : "_collections._deque_iterator", /* tp_name */
1793 : : sizeof(dequeiterobject), /* tp_basicsize */
1794 : : 0, /* tp_itemsize */
1795 : : /* methods */
1796 : : (destructor)dequeiter_dealloc, /* tp_dealloc */
1797 : : 0, /* tp_vectorcall_offset */
1798 : : 0, /* tp_getattr */
1799 : : 0, /* tp_setattr */
1800 : : 0, /* tp_as_async */
1801 : : 0, /* tp_repr */
1802 : : 0, /* tp_as_number */
1803 : : 0, /* tp_as_sequence */
1804 : : 0, /* tp_as_mapping */
1805 : : 0, /* tp_hash */
1806 : : 0, /* tp_call */
1807 : : 0, /* tp_str */
1808 : : PyObject_GenericGetAttr, /* tp_getattro */
1809 : : 0, /* tp_setattro */
1810 : : 0, /* tp_as_buffer */
1811 : : Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC, /* tp_flags */
1812 : : 0, /* tp_doc */
1813 : : (traverseproc)dequeiter_traverse, /* tp_traverse */
1814 : : 0, /* tp_clear */
1815 : : 0, /* tp_richcompare */
1816 : : 0, /* tp_weaklistoffset */
1817 : : PyObject_SelfIter, /* tp_iter */
1818 : : (iternextfunc)dequeiter_next, /* tp_iternext */
1819 : : dequeiter_methods, /* tp_methods */
1820 : : 0, /* tp_members */
1821 : : 0, /* tp_getset */
1822 : : 0, /* tp_base */
1823 : : 0, /* tp_dict */
1824 : : 0, /* tp_descr_get */
1825 : : 0, /* tp_descr_set */
1826 : : 0, /* tp_dictoffset */
1827 : : 0, /* tp_init */
1828 : : 0, /* tp_alloc */
1829 : : dequeiter_new, /* tp_new */
1830 : : 0,
1831 : : };
1832 : :
1833 : : /*********************** Deque Reverse Iterator **************************/
1834 : :
1835 : : static PyTypeObject dequereviter_type;
1836 : :
1837 : : static PyObject *
1838 : 10 : deque_reviter(dequeobject *deque, PyObject *Py_UNUSED(ignored))
1839 : : {
1840 : : dequeiterobject *it;
1841 : :
1842 : 10 : it = PyObject_GC_New(dequeiterobject, &dequereviter_type);
1843 [ - + ]: 10 : if (it == NULL)
1844 : 0 : return NULL;
1845 : 10 : it->b = deque->rightblock;
1846 : 10 : it->index = deque->rightindex;
1847 : 10 : Py_INCREF(deque);
1848 : 10 : it->deque = deque;
1849 : 10 : it->state = deque->state;
1850 : 10 : it->counter = Py_SIZE(deque);
1851 : 10 : PyObject_GC_Track(it);
1852 : 10 : return (PyObject *)it;
1853 : : }
1854 : :
1855 : : static PyObject *
1856 : 4036 : dequereviter_next(dequeiterobject *it)
1857 : : {
1858 : : PyObject *item;
1859 [ + + ]: 4036 : if (it->counter == 0)
1860 : 7 : return NULL;
1861 : :
1862 [ + + ]: 4029 : if (it->deque->state != it->state) {
1863 : 1 : it->counter = 0;
1864 : 1 : PyErr_SetString(PyExc_RuntimeError,
1865 : : "deque mutated during iteration");
1866 : 1 : return NULL;
1867 : : }
1868 : : assert (!(it->b == it->deque->leftblock &&
1869 : : it->index < it->deque->leftindex));
1870 : :
1871 : 4028 : item = it->b->data[it->index];
1872 : 4028 : it->index--;
1873 : 4028 : it->counter--;
1874 [ + + + - ]: 4028 : if (it->index < 0 && it->counter > 0) {
1875 : : CHECK_NOT_END(it->b->leftlink);
1876 : 62 : it->b = it->b->leftlink;
1877 : 62 : it->index = BLOCKLEN - 1;
1878 : : }
1879 : 4028 : Py_INCREF(item);
1880 : 4028 : return item;
1881 : : }
1882 : :
1883 : : static PyObject *
1884 : 2 : dequereviter_new(PyTypeObject *type, PyObject *args, PyObject *kwds)
1885 : : {
1886 : 2 : Py_ssize_t i, index=0;
1887 : : PyObject *deque;
1888 : : dequeiterobject *it;
1889 [ - + ]: 2 : if (!PyArg_ParseTuple(args, "O!|n", &deque_type, &deque, &index))
1890 : 0 : return NULL;
1891 : : assert(type == &dequereviter_type);
1892 : :
1893 : 2 : it = (dequeiterobject*)deque_reviter((dequeobject *)deque, NULL);
1894 [ - + ]: 2 : if (!it)
1895 : 0 : return NULL;
1896 : : /* consume items from the queue */
1897 [ - + ]: 2 : for(i=0; i<index; i++) {
1898 : 0 : PyObject *item = dequereviter_next(it);
1899 [ # # ]: 0 : if (item) {
1900 : 0 : Py_DECREF(item);
1901 : : } else {
1902 [ # # ]: 0 : if (it->counter) {
1903 : 0 : Py_DECREF(it);
1904 : 0 : return NULL;
1905 : : } else
1906 : 0 : break;
1907 : : }
1908 : : }
1909 : 2 : return (PyObject*)it;
1910 : : }
1911 : :
1912 : : static PyTypeObject dequereviter_type = {
1913 : : PyVarObject_HEAD_INIT(NULL, 0)
1914 : : "_collections._deque_reverse_iterator", /* tp_name */
1915 : : sizeof(dequeiterobject), /* tp_basicsize */
1916 : : 0, /* tp_itemsize */
1917 : : /* methods */
1918 : : (destructor)dequeiter_dealloc, /* tp_dealloc */
1919 : : 0, /* tp_vectorcall_offset */
1920 : : 0, /* tp_getattr */
1921 : : 0, /* tp_setattr */
1922 : : 0, /* tp_as_async */
1923 : : 0, /* tp_repr */
1924 : : 0, /* tp_as_number */
1925 : : 0, /* tp_as_sequence */
1926 : : 0, /* tp_as_mapping */
1927 : : 0, /* tp_hash */
1928 : : 0, /* tp_call */
1929 : : 0, /* tp_str */
1930 : : PyObject_GenericGetAttr, /* tp_getattro */
1931 : : 0, /* tp_setattro */
1932 : : 0, /* tp_as_buffer */
1933 : : Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC, /* tp_flags */
1934 : : 0, /* tp_doc */
1935 : : (traverseproc)dequeiter_traverse, /* tp_traverse */
1936 : : 0, /* tp_clear */
1937 : : 0, /* tp_richcompare */
1938 : : 0, /* tp_weaklistoffset */
1939 : : PyObject_SelfIter, /* tp_iter */
1940 : : (iternextfunc)dequereviter_next, /* tp_iternext */
1941 : : dequeiter_methods, /* tp_methods */
1942 : : 0, /* tp_members */
1943 : : 0, /* tp_getset */
1944 : : 0, /* tp_base */
1945 : : 0, /* tp_dict */
1946 : : 0, /* tp_descr_get */
1947 : : 0, /* tp_descr_set */
1948 : : 0, /* tp_dictoffset */
1949 : : 0, /* tp_init */
1950 : : 0, /* tp_alloc */
1951 : : dequereviter_new, /* tp_new */
1952 : : 0,
1953 : : };
1954 : :
1955 : : /* defaultdict type *********************************************************/
1956 : :
1957 : : typedef struct {
1958 : : PyDictObject dict;
1959 : : PyObject *default_factory;
1960 : : } defdictobject;
1961 : :
1962 : : static PyTypeObject defdict_type; /* Forward */
1963 : :
1964 : : PyDoc_STRVAR(defdict_missing_doc,
1965 : : "__missing__(key) # Called by __getitem__ for missing key; pseudo-code:\n\
1966 : : if self.default_factory is None: raise KeyError((key,))\n\
1967 : : self[key] = value = self.default_factory()\n\
1968 : : return value\n\
1969 : : ");
1970 : :
1971 : : static PyObject *
1972 : 164077 : defdict_missing(defdictobject *dd, PyObject *key)
1973 : : {
1974 : 164077 : PyObject *factory = dd->default_factory;
1975 : : PyObject *value;
1976 [ + + + + ]: 164077 : if (factory == NULL || factory == Py_None) {
1977 : : /* XXX Call dict.__missing__(key) */
1978 : : PyObject *tup;
1979 : 3 : tup = PyTuple_Pack(1, key);
1980 [ - + ]: 3 : if (!tup) return NULL;
1981 : 3 : PyErr_SetObject(PyExc_KeyError, tup);
1982 : 3 : Py_DECREF(tup);
1983 : 3 : return NULL;
1984 : : }
1985 : 164074 : value = _PyObject_CallNoArgs(factory);
1986 [ - + ]: 164074 : if (value == NULL)
1987 : 0 : return value;
1988 [ - + ]: 164074 : if (PyObject_SetItem((PyObject *)dd, key, value) < 0) {
1989 : 0 : Py_DECREF(value);
1990 : 0 : return NULL;
1991 : : }
1992 : 164074 : return value;
1993 : : }
1994 : :
1995 : : static inline PyObject*
1996 : 10 : new_defdict(defdictobject *dd, PyObject *arg)
1997 : : {
1998 : 10 : return PyObject_CallFunctionObjArgs((PyObject*)Py_TYPE(dd),
1999 [ + + ]: 10 : dd->default_factory ? dd->default_factory : Py_None, arg, NULL);
2000 : : }
2001 : :
2002 : : PyDoc_STRVAR(defdict_copy_doc, "D.copy() -> a shallow copy of D.");
2003 : :
2004 : : static PyObject *
2005 : 6 : defdict_copy(defdictobject *dd, PyObject *Py_UNUSED(ignored))
2006 : : {
2007 : : /* This calls the object's class. That only works for subclasses
2008 : : whose class constructor has the same signature. Subclasses that
2009 : : define a different constructor signature must override copy().
2010 : : */
2011 : 6 : return new_defdict(dd, (PyObject*)dd);
2012 : : }
2013 : :
2014 : : static PyObject *
2015 : 26 : defdict_reduce(defdictobject *dd, PyObject *Py_UNUSED(ignored))
2016 : : {
2017 : : /* __reduce__ must return a 5-tuple as follows:
2018 : :
2019 : : - factory function
2020 : : - tuple of args for the factory function
2021 : : - additional state (here None)
2022 : : - sequence iterator (here None)
2023 : : - dictionary iterator (yielding successive (key, value) pairs
2024 : :
2025 : : This API is used by pickle.py and copy.py.
2026 : :
2027 : : For this to be useful with pickle.py, the default_factory
2028 : : must be picklable; e.g., None, a built-in, or a global
2029 : : function in a module or package.
2030 : :
2031 : : Both shallow and deep copying are supported, but for deep
2032 : : copying, the default_factory must be deep-copyable; e.g. None,
2033 : : or a built-in (functions are not copyable at this time).
2034 : :
2035 : : This only works for subclasses as long as their constructor
2036 : : signature is compatible; the first argument must be the
2037 : : optional default_factory, defaulting to None.
2038 : : */
2039 : : PyObject *args;
2040 : : PyObject *items;
2041 : : PyObject *iter;
2042 : : PyObject *result;
2043 : :
2044 [ + + - + ]: 26 : if (dd->default_factory == NULL || dd->default_factory == Py_None)
2045 : 18 : args = PyTuple_New(0);
2046 : : else
2047 : 8 : args = PyTuple_Pack(1, dd->default_factory);
2048 [ - + ]: 26 : if (args == NULL)
2049 : 0 : return NULL;
2050 : 26 : items = PyObject_CallMethodNoArgs((PyObject *)dd, &_Py_ID(items));
2051 [ - + ]: 26 : if (items == NULL) {
2052 : 0 : Py_DECREF(args);
2053 : 0 : return NULL;
2054 : : }
2055 : 26 : iter = PyObject_GetIter(items);
2056 [ - + ]: 26 : if (iter == NULL) {
2057 : 0 : Py_DECREF(items);
2058 : 0 : Py_DECREF(args);
2059 : 0 : return NULL;
2060 : : }
2061 : 26 : result = PyTuple_Pack(5, Py_TYPE(dd), args,
2062 : : Py_None, Py_None, iter);
2063 : 26 : Py_DECREF(iter);
2064 : 26 : Py_DECREF(items);
2065 : 26 : Py_DECREF(args);
2066 : 26 : return result;
2067 : : }
2068 : :
2069 : : static PyMethodDef defdict_methods[] = {
2070 : : {"__missing__", (PyCFunction)defdict_missing, METH_O,
2071 : : defdict_missing_doc},
2072 : : {"copy", (PyCFunction)defdict_copy, METH_NOARGS,
2073 : : defdict_copy_doc},
2074 : : {"__copy__", (PyCFunction)defdict_copy, METH_NOARGS,
2075 : : defdict_copy_doc},
2076 : : {"__reduce__", (PyCFunction)defdict_reduce, METH_NOARGS,
2077 : : reduce_doc},
2078 : : {"__class_getitem__", Py_GenericAlias, METH_O|METH_CLASS,
2079 : : PyDoc_STR("See PEP 585")},
2080 : : {NULL}
2081 : : };
2082 : :
2083 : : static PyMemberDef defdict_members[] = {
2084 : : {"default_factory", T_OBJECT,
2085 : : offsetof(defdictobject, default_factory), 0,
2086 : : PyDoc_STR("Factory for default value called by __missing__().")},
2087 : : {NULL}
2088 : : };
2089 : :
2090 : : static void
2091 : 17295 : defdict_dealloc(defdictobject *dd)
2092 : : {
2093 : : /* bpo-31095: UnTrack is needed before calling any callbacks */
2094 : 17295 : PyObject_GC_UnTrack(dd);
2095 [ + + ]: 17295 : Py_CLEAR(dd->default_factory);
2096 : 17295 : PyDict_Type.tp_dealloc((PyObject *)dd);
2097 : 17295 : }
2098 : :
2099 : : static PyObject *
2100 : 16 : defdict_repr(defdictobject *dd)
2101 : : {
2102 : : PyObject *baserepr;
2103 : : PyObject *defrepr;
2104 : : PyObject *result;
2105 : 16 : baserepr = PyDict_Type.tp_repr((PyObject *)dd);
2106 [ - + ]: 16 : if (baserepr == NULL)
2107 : 0 : return NULL;
2108 [ + + ]: 16 : if (dd->default_factory == NULL)
2109 : 3 : defrepr = PyUnicode_FromString("None");
2110 : : else
2111 : : {
2112 : 13 : int status = Py_ReprEnter(dd->default_factory);
2113 [ + + ]: 13 : if (status != 0) {
2114 [ - + ]: 1 : if (status < 0) {
2115 : 0 : Py_DECREF(baserepr);
2116 : 0 : return NULL;
2117 : : }
2118 : 1 : defrepr = PyUnicode_FromString("...");
2119 : : }
2120 : : else
2121 : 12 : defrepr = PyObject_Repr(dd->default_factory);
2122 : 13 : Py_ReprLeave(dd->default_factory);
2123 : : }
2124 [ - + ]: 16 : if (defrepr == NULL) {
2125 : 0 : Py_DECREF(baserepr);
2126 : 0 : return NULL;
2127 : : }
2128 : 16 : result = PyUnicode_FromFormat("%s(%U, %U)",
2129 : : _PyType_Name(Py_TYPE(dd)),
2130 : : defrepr, baserepr);
2131 : 16 : Py_DECREF(defrepr);
2132 : 16 : Py_DECREF(baserepr);
2133 : 16 : return result;
2134 : : }
2135 : :
2136 : : static PyObject*
2137 : 6 : defdict_or(PyObject* left, PyObject* right)
2138 : : {
2139 : : PyObject *self, *other;
2140 [ + + ]: 6 : if (PyObject_TypeCheck(left, &defdict_type)) {
2141 : 4 : self = left;
2142 : 4 : other = right;
2143 : : }
2144 : : else {
2145 : 2 : self = right;
2146 : 2 : other = left;
2147 : : }
2148 [ + + ]: 6 : if (!PyDict_Check(other)) {
2149 : 2 : Py_RETURN_NOTIMPLEMENTED;
2150 : : }
2151 : : // Like copy(), this calls the object's class.
2152 : : // Override __or__/__ror__ for subclasses with different constructors.
2153 : 4 : PyObject *new = new_defdict((defdictobject*)self, left);
2154 [ - + ]: 4 : if (!new) {
2155 : 0 : return NULL;
2156 : : }
2157 [ - + ]: 4 : if (PyDict_Update(new, right)) {
2158 : 0 : Py_DECREF(new);
2159 : 0 : return NULL;
2160 : : }
2161 : 4 : return new;
2162 : : }
2163 : :
2164 : : static PyNumberMethods defdict_as_number = {
2165 : : .nb_or = defdict_or,
2166 : : };
2167 : :
2168 : : static int
2169 : 58514 : defdict_traverse(PyObject *self, visitproc visit, void *arg)
2170 : : {
2171 [ + + - + ]: 58514 : Py_VISIT(((defdictobject *)self)->default_factory);
2172 : 58514 : return PyDict_Type.tp_traverse(self, visit, arg);
2173 : : }
2174 : :
2175 : : static int
2176 : 204 : defdict_tp_clear(defdictobject *dd)
2177 : : {
2178 [ + + ]: 204 : Py_CLEAR(dd->default_factory);
2179 : 204 : return PyDict_Type.tp_clear((PyObject *)dd);
2180 : : }
2181 : :
2182 : : static int
2183 : 17294 : defdict_init(PyObject *self, PyObject *args, PyObject *kwds)
2184 : : {
2185 : 17294 : defdictobject *dd = (defdictobject *)self;
2186 : 17294 : PyObject *olddefault = dd->default_factory;
2187 : 17294 : PyObject *newdefault = NULL;
2188 : : PyObject *newargs;
2189 : : int result;
2190 [ + - - + ]: 17294 : if (args == NULL || !PyTuple_Check(args))
2191 : 0 : newargs = PyTuple_New(0);
2192 : : else {
2193 : 17294 : Py_ssize_t n = PyTuple_GET_SIZE(args);
2194 [ + + ]: 17294 : if (n > 0) {
2195 : 17255 : newdefault = PyTuple_GET_ITEM(args, 0);
2196 [ + + + + ]: 17255 : if (!PyCallable_Check(newdefault) && newdefault != Py_None) {
2197 : 2 : PyErr_SetString(PyExc_TypeError,
2198 : : "first argument must be callable or None");
2199 : 2 : return -1;
2200 : : }
2201 : : }
2202 : 17292 : newargs = PySequence_GetSlice(args, 1, n);
2203 : : }
2204 [ - + ]: 17292 : if (newargs == NULL)
2205 : 0 : return -1;
2206 : 17292 : Py_XINCREF(newdefault);
2207 : 17292 : dd->default_factory = newdefault;
2208 : 17292 : result = PyDict_Type.tp_init(self, newargs, kwds);
2209 : 17292 : Py_DECREF(newargs);
2210 : 17292 : Py_XDECREF(olddefault);
2211 : 17292 : return result;
2212 : : }
2213 : :
2214 : : PyDoc_STRVAR(defdict_doc,
2215 : : "defaultdict(default_factory=None, /, [...]) --> dict with default factory\n\
2216 : : \n\
2217 : : The default factory is called without arguments to produce\n\
2218 : : a new value when a key is not present, in __getitem__ only.\n\
2219 : : A defaultdict compares equal to a dict with the same items.\n\
2220 : : All remaining arguments are treated the same as if they were\n\
2221 : : passed to the dict constructor, including keyword arguments.\n\
2222 : : ");
2223 : :
2224 : : /* See comment in xxsubtype.c */
2225 : : #define DEFERRED_ADDRESS(ADDR) 0
2226 : :
2227 : : static PyTypeObject defdict_type = {
2228 : : PyVarObject_HEAD_INIT(DEFERRED_ADDRESS(&PyType_Type), 0)
2229 : : "collections.defaultdict", /* tp_name */
2230 : : sizeof(defdictobject), /* tp_basicsize */
2231 : : 0, /* tp_itemsize */
2232 : : /* methods */
2233 : : (destructor)defdict_dealloc, /* tp_dealloc */
2234 : : 0, /* tp_vectorcall_offset */
2235 : : 0, /* tp_getattr */
2236 : : 0, /* tp_setattr */
2237 : : 0, /* tp_as_async */
2238 : : (reprfunc)defdict_repr, /* tp_repr */
2239 : : &defdict_as_number, /* tp_as_number */
2240 : : 0, /* tp_as_sequence */
2241 : : 0, /* tp_as_mapping */
2242 : : 0, /* tp_hash */
2243 : : 0, /* tp_call */
2244 : : 0, /* tp_str */
2245 : : PyObject_GenericGetAttr, /* tp_getattro */
2246 : : 0, /* tp_setattro */
2247 : : 0, /* tp_as_buffer */
2248 : : Py_TPFLAGS_DEFAULT | Py_TPFLAGS_BASETYPE | Py_TPFLAGS_HAVE_GC,
2249 : : /* tp_flags */
2250 : : defdict_doc, /* tp_doc */
2251 : : defdict_traverse, /* tp_traverse */
2252 : : (inquiry)defdict_tp_clear, /* tp_clear */
2253 : : 0, /* tp_richcompare */
2254 : : 0, /* tp_weaklistoffset*/
2255 : : 0, /* tp_iter */
2256 : : 0, /* tp_iternext */
2257 : : defdict_methods, /* tp_methods */
2258 : : defdict_members, /* tp_members */
2259 : : 0, /* tp_getset */
2260 : : DEFERRED_ADDRESS(&PyDict_Type), /* tp_base */
2261 : : 0, /* tp_dict */
2262 : : 0, /* tp_descr_get */
2263 : : 0, /* tp_descr_set */
2264 : : 0, /* tp_dictoffset */
2265 : : defdict_init, /* tp_init */
2266 : : PyType_GenericAlloc, /* tp_alloc */
2267 : : 0, /* tp_new */
2268 : : PyObject_GC_Del, /* tp_free */
2269 : : };
2270 : :
2271 : : /* helper function for Counter *********************************************/
2272 : :
2273 : : /*[clinic input]
2274 : : _collections._count_elements
2275 : :
2276 : : mapping: object
2277 : : iterable: object
2278 : : /
2279 : :
2280 : : Count elements in the iterable, updating the mapping
2281 : : [clinic start generated code]*/
2282 : :
2283 : : static PyObject *
2284 : 2026 : _collections__count_elements_impl(PyObject *module, PyObject *mapping,
2285 : : PyObject *iterable)
2286 : : /*[clinic end generated code: output=7e0c1789636b3d8f input=e79fad04534a0b45]*/
2287 : : {
2288 : : PyObject *it, *oldval;
2289 : 2026 : PyObject *newval = NULL;
2290 : 2026 : PyObject *key = NULL;
2291 : 2026 : PyObject *bound_get = NULL;
2292 : : PyObject *mapping_get;
2293 : : PyObject *dict_get;
2294 : : PyObject *mapping_setitem;
2295 : : PyObject *dict_setitem;
2296 : 2026 : PyObject *one = _PyLong_GetOne(); // borrowed reference
2297 : :
2298 : 2026 : it = PyObject_GetIter(iterable);
2299 [ + + ]: 2026 : if (it == NULL)
2300 : 2 : return NULL;
2301 : :
2302 : : /* Only take the fast path when get() and __setitem__()
2303 : : * have not been overridden.
2304 : : */
2305 : 2024 : mapping_get = _PyType_Lookup(Py_TYPE(mapping), &_Py_ID(get));
2306 : 2024 : dict_get = _PyType_Lookup(&PyDict_Type, &_Py_ID(get));
2307 : 2024 : mapping_setitem = _PyType_Lookup(Py_TYPE(mapping), &_Py_ID(__setitem__));
2308 : 2024 : dict_setitem = _PyType_Lookup(&PyDict_Type, &_Py_ID(__setitem__));
2309 : :
2310 [ + - + + : 2024 : if (mapping_get != NULL && mapping_get == dict_get &&
+ - ]
2311 [ + + + - ]: 4044 : mapping_setitem != NULL && mapping_setitem == dict_setitem &&
2312 : 2021 : PyDict_Check(mapping))
2313 : : {
2314 : 220580 : while (1) {
2315 : : /* Fast path advantages:
2316 : : 1. Eliminate double hashing
2317 : : (by re-using the same hash for both the get and set)
2318 : : 2. Avoid argument overhead of PyObject_CallFunctionObjArgs
2319 : : (argument tuple creation and parsing)
2320 : : 3. Avoid indirection through a bound method object
2321 : : (creates another argument tuple)
2322 : : 4. Avoid initial increment from zero
2323 : : (reuse an existing one-object instead)
2324 : : */
2325 : : Py_hash_t hash;
2326 : :
2327 : 222601 : key = PyIter_Next(it);
2328 [ + + ]: 222601 : if (key == NULL)
2329 : 2011 : break;
2330 : :
2331 [ + + ]: 220590 : if (!PyUnicode_CheckExact(key) ||
2332 [ + + ]: 16248 : (hash = _PyASCIIObject_CAST(key)->hash) == -1)
2333 : : {
2334 : 205281 : hash = PyObject_Hash(key);
2335 [ + + ]: 205281 : if (hash == -1)
2336 : 10 : goto done;
2337 : : }
2338 : :
2339 : 220580 : oldval = _PyDict_GetItem_KnownHash(mapping, key, hash);
2340 [ + + ]: 220580 : if (oldval == NULL) {
2341 [ - + ]: 13864 : if (PyErr_Occurred())
2342 : 0 : goto done;
2343 [ - + ]: 13864 : if (_PyDict_SetItem_KnownHash(mapping, key, one, hash) < 0)
2344 : 0 : goto done;
2345 : : } else {
2346 : 206716 : newval = PyNumber_Add(oldval, one);
2347 [ - + ]: 206716 : if (newval == NULL)
2348 : 0 : goto done;
2349 [ - + ]: 206716 : if (_PyDict_SetItem_KnownHash(mapping, key, newval, hash) < 0)
2350 : 0 : goto done;
2351 [ + - ]: 206716 : Py_CLEAR(newval);
2352 : : }
2353 : 220580 : Py_DECREF(key);
2354 : : }
2355 : : }
2356 : : else {
2357 : 3 : bound_get = PyObject_GetAttr(mapping, &_Py_ID(get));
2358 [ - + ]: 3 : if (bound_get == NULL)
2359 : 0 : goto done;
2360 : :
2361 : 3 : PyObject *zero = _PyLong_GetZero(); // borrowed reference
2362 : : while (1) {
2363 : 36 : key = PyIter_Next(it);
2364 [ + + ]: 36 : if (key == NULL)
2365 : 3 : break;
2366 : 33 : oldval = PyObject_CallFunctionObjArgs(bound_get, key, zero, NULL);
2367 [ - + ]: 33 : if (oldval == NULL)
2368 : 0 : break;
2369 : 33 : newval = PyNumber_Add(oldval, one);
2370 : 33 : Py_DECREF(oldval);
2371 [ - + ]: 33 : if (newval == NULL)
2372 : 0 : break;
2373 [ - + ]: 33 : if (PyObject_SetItem(mapping, key, newval) < 0)
2374 : 0 : break;
2375 [ + - ]: 33 : Py_CLEAR(newval);
2376 : 33 : Py_DECREF(key);
2377 : : }
2378 : : }
2379 : :
2380 : 2024 : done:
2381 : 2024 : Py_DECREF(it);
2382 : 2024 : Py_XDECREF(key);
2383 : 2024 : Py_XDECREF(newval);
2384 : 2024 : Py_XDECREF(bound_get);
2385 [ + + ]: 2024 : if (PyErr_Occurred())
2386 : 10 : return NULL;
2387 : 2014 : Py_RETURN_NONE;
2388 : : }
2389 : :
2390 : : /* Helper function for namedtuple() ************************************/
2391 : :
2392 : : typedef struct {
2393 : : PyObject_HEAD
2394 : : Py_ssize_t index;
2395 : : PyObject* doc;
2396 : : } _tuplegetterobject;
2397 : :
2398 : : /*[clinic input]
2399 : : @classmethod
2400 : : _tuplegetter.__new__ as tuplegetter_new
2401 : :
2402 : : index: Py_ssize_t
2403 : : doc: object
2404 : : /
2405 : : [clinic start generated code]*/
2406 : :
2407 : : static PyObject *
2408 : 131676 : tuplegetter_new_impl(PyTypeObject *type, Py_ssize_t index, PyObject *doc)
2409 : : /*[clinic end generated code: output=014be444ad80263f input=87c576a5bdbc0bbb]*/
2410 : : {
2411 : : _tuplegetterobject* self;
2412 : 131676 : self = (_tuplegetterobject *)type->tp_alloc(type, 0);
2413 [ - + ]: 131676 : if (self == NULL) {
2414 : 0 : return NULL;
2415 : : }
2416 : 131676 : self->index = index;
2417 : 131676 : Py_INCREF(doc);
2418 : 131676 : self->doc = doc;
2419 : 131676 : return (PyObject *)self;
2420 : : }
2421 : :
2422 : : static PyObject *
2423 : 1274223 : tuplegetter_descr_get(PyObject *self, PyObject *obj, PyObject *type)
2424 : : {
2425 : 1274223 : Py_ssize_t index = ((_tuplegetterobject*)self)->index;
2426 : : PyObject *result;
2427 : :
2428 [ + + ]: 1274223 : if (obj == NULL) {
2429 : 32501 : Py_INCREF(self);
2430 : 32501 : return self;
2431 : : }
2432 [ - + ]: 1241722 : if (!PyTuple_Check(obj)) {
2433 [ # # ]: 0 : if (obj == Py_None) {
2434 : 0 : Py_INCREF(self);
2435 : 0 : return self;
2436 : : }
2437 : 0 : PyErr_Format(PyExc_TypeError,
2438 : : "descriptor for index '%zd' for tuple subclasses "
2439 : : "doesn't apply to '%s' object",
2440 : : index,
2441 : 0 : Py_TYPE(obj)->tp_name);
2442 : 0 : return NULL;
2443 : : }
2444 : :
2445 [ - + ]: 1241722 : if (!valid_index(index, PyTuple_GET_SIZE(obj))) {
2446 : 0 : PyErr_SetString(PyExc_IndexError, "tuple index out of range");
2447 : 0 : return NULL;
2448 : : }
2449 : :
2450 : 1241722 : result = PyTuple_GET_ITEM(obj, index);
2451 : 1241722 : Py_INCREF(result);
2452 : 1241722 : return result;
2453 : : }
2454 : :
2455 : : static int
2456 : 4 : tuplegetter_descr_set(PyObject *self, PyObject *obj, PyObject *value)
2457 : : {
2458 [ + + ]: 4 : if (value == NULL) {
2459 : 2 : PyErr_SetString(PyExc_AttributeError, "can't delete attribute");
2460 : : } else {
2461 : 2 : PyErr_SetString(PyExc_AttributeError, "can't set attribute");
2462 : : }
2463 : 4 : return -1;
2464 : : }
2465 : :
2466 : : static int
2467 : 3987341 : tuplegetter_traverse(PyObject *self, visitproc visit, void *arg)
2468 : : {
2469 : 3987341 : _tuplegetterobject *tuplegetter = (_tuplegetterobject *)self;
2470 [ + - - + ]: 3987341 : Py_VISIT(tuplegetter->doc);
2471 : 3987341 : return 0;
2472 : : }
2473 : :
2474 : : static int
2475 : 131840 : tuplegetter_clear(PyObject *self)
2476 : : {
2477 : 131840 : _tuplegetterobject *tuplegetter = (_tuplegetterobject *)self;
2478 [ + + ]: 131840 : Py_CLEAR(tuplegetter->doc);
2479 : 131840 : return 0;
2480 : : }
2481 : :
2482 : : static void
2483 : 131259 : tuplegetter_dealloc(_tuplegetterobject *self)
2484 : : {
2485 : 131259 : PyObject_GC_UnTrack(self);
2486 : 131259 : tuplegetter_clear((PyObject*)self);
2487 : 131259 : Py_TYPE(self)->tp_free((PyObject*)self);
2488 : 131259 : }
2489 : :
2490 : : static PyObject*
2491 : 12 : tuplegetter_reduce(_tuplegetterobject *self, PyObject *Py_UNUSED(ignored))
2492 : : {
2493 : 12 : return Py_BuildValue("(O(nO))", (PyObject*) Py_TYPE(self), self->index, self->doc);
2494 : : }
2495 : :
2496 : : static PyObject*
2497 : 4 : tuplegetter_repr(_tuplegetterobject *self)
2498 : : {
2499 : 4 : return PyUnicode_FromFormat("%s(%zd, %R)",
2500 : : _PyType_Name(Py_TYPE(self)),
2501 : : self->index, self->doc);
2502 : : }
2503 : :
2504 : :
2505 : : static PyMemberDef tuplegetter_members[] = {
2506 : : {"__doc__", T_OBJECT, offsetof(_tuplegetterobject, doc), 0},
2507 : : {0}
2508 : : };
2509 : :
2510 : : static PyMethodDef tuplegetter_methods[] = {
2511 : : {"__reduce__", (PyCFunction)tuplegetter_reduce, METH_NOARGS, NULL},
2512 : : {NULL},
2513 : : };
2514 : :
2515 : : static PyTypeObject tuplegetter_type = {
2516 : : PyVarObject_HEAD_INIT(NULL, 0)
2517 : : "_collections._tuplegetter", /* tp_name */
2518 : : sizeof(_tuplegetterobject), /* tp_basicsize */
2519 : : 0, /* tp_itemsize */
2520 : : /* methods */
2521 : : (destructor)tuplegetter_dealloc, /* tp_dealloc */
2522 : : 0, /* tp_vectorcall_offset */
2523 : : 0, /* tp_getattr */
2524 : : 0, /* tp_setattr */
2525 : : 0, /* tp_as_async */
2526 : : (reprfunc)tuplegetter_repr, /* tp_repr */
2527 : : 0, /* tp_as_number */
2528 : : 0, /* tp_as_sequence */
2529 : : 0, /* tp_as_mapping */
2530 : : 0, /* tp_hash */
2531 : : 0, /* tp_call */
2532 : : 0, /* tp_str */
2533 : : 0, /* tp_getattro */
2534 : : 0, /* tp_setattro */
2535 : : 0, /* tp_as_buffer */
2536 : : Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC, /* tp_flags */
2537 : : 0, /* tp_doc */
2538 : : (traverseproc)tuplegetter_traverse, /* tp_traverse */
2539 : : (inquiry)tuplegetter_clear, /* tp_clear */
2540 : : 0, /* tp_richcompare */
2541 : : 0, /* tp_weaklistoffset */
2542 : : 0, /* tp_iter */
2543 : : 0, /* tp_iternext */
2544 : : tuplegetter_methods, /* tp_methods */
2545 : : tuplegetter_members, /* tp_members */
2546 : : 0, /* tp_getset */
2547 : : 0, /* tp_base */
2548 : : 0, /* tp_dict */
2549 : : tuplegetter_descr_get, /* tp_descr_get */
2550 : : tuplegetter_descr_set, /* tp_descr_set */
2551 : : 0, /* tp_dictoffset */
2552 : : 0, /* tp_init */
2553 : : 0, /* tp_alloc */
2554 : : tuplegetter_new, /* tp_new */
2555 : : 0,
2556 : : };
2557 : :
2558 : :
2559 : : /* module level code ********************************************************/
2560 : :
2561 : : PyDoc_STRVAR(collections_doc,
2562 : : "High performance data structures.\n\
2563 : : - deque: ordered collection accessible from endpoints only\n\
2564 : : - defaultdict: dict subclass with a default value factory\n\
2565 : : ");
2566 : :
2567 : : static struct PyMethodDef collections_methods[] = {
2568 : : _COLLECTIONS__COUNT_ELEMENTS_METHODDEF
2569 : : {NULL, NULL} /* sentinel */
2570 : : };
2571 : :
2572 : : static int
2573 : 1983 : collections_exec(PyObject *module) {
2574 : 1983 : PyTypeObject *typelist[] = {
2575 : : &deque_type,
2576 : : &defdict_type,
2577 : : &PyODict_Type,
2578 : : &dequeiter_type,
2579 : : &dequereviter_type,
2580 : : &tuplegetter_type
2581 : : };
2582 : :
2583 : 1983 : defdict_type.tp_base = &PyDict_Type;
2584 : :
2585 [ + + ]: 13881 : for (size_t i = 0; i < Py_ARRAY_LENGTH(typelist); i++) {
2586 [ - + ]: 11898 : if (PyModule_AddType(module, typelist[i]) < 0) {
2587 : 0 : return -1;
2588 : : }
2589 : : }
2590 : :
2591 : 1983 : return 0;
2592 : : }
2593 : :
2594 : : static struct PyModuleDef_Slot collections_slots[] = {
2595 : : {Py_mod_exec, collections_exec},
2596 : : {0, NULL}
2597 : : };
2598 : :
2599 : : static struct PyModuleDef _collectionsmodule = {
2600 : : PyModuleDef_HEAD_INIT,
2601 : : "_collections",
2602 : : collections_doc,
2603 : : 0,
2604 : : collections_methods,
2605 : : collections_slots,
2606 : : NULL,
2607 : : NULL,
2608 : : NULL
2609 : : };
2610 : :
2611 : : PyMODINIT_FUNC
2612 : 1983 : PyInit__collections(void)
2613 : : {
2614 : 1983 : return PyModuleDef_Init(&_collectionsmodule);
2615 : : }
|
