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