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] 8module _collections 9class _tuplegetter "_tuplegetterobject *" "&tuplegetter_type" 10[clinic start generated code]*/ 11/*[clinic end generated code: output=da39a3ee5e6b4b0d input=a8ece4ccad7e30ac]*/ 12 13static 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 78typedef struct BLOCK { 79 struct BLOCK *leftlink; 80 PyObject *data[BLOCKLEN]; 81 struct BLOCK *rightlink; 82} block; 83 84typedef 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 97static 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 125static inline block * 126newblock(dequeobject *deque) { 127 block *b; 128 if (deque->numfreeblocks) { 129 deque->numfreeblocks--; 130 return deque->freeblocks[deque->numfreeblocks]; 131 } 132 b = PyMem_Malloc(sizeof(block)); 133 if (b != NULL) { 134 return b; 135 } 136 PyErr_NoMemory(); 137 return NULL; 138} 139 140static inline void 141freeblock(dequeobject *deque, block *b) 142{ 143 if (deque->numfreeblocks < MAXFREEBLOCKS) { 144 deque->freeblocks[deque->numfreeblocks] = b; 145 deque->numfreeblocks++; 146 } else { 147 PyMem_Free(b); 148 } 149} 150 151static PyObject * 152deque_new(PyTypeObject *type, PyObject *args, PyObject *kwds) 153{ 154 dequeobject *deque; 155 block *b; 156 157 /* create dequeobject structure */ 158 deque = (dequeobject *)type->tp_alloc(type, 0); 159 if (deque == NULL) 160 return NULL; 161 162 b = newblock(deque); 163 if (b == NULL) { 164 Py_DECREF(deque); 165 return NULL; 166 } 167 MARK_END(b->leftlink); 168 MARK_END(b->rightlink); 169 170 assert(BLOCKLEN >= 2); 171 Py_SET_SIZE(deque, 0); 172 deque->leftblock = b; 173 deque->rightblock = b; 174 deque->leftindex = CENTER + 1; 175 deque->rightindex = CENTER; 176 deque->state = 0; 177 deque->maxlen = -1; 178 deque->numfreeblocks = 0; 179 deque->weakreflist = NULL; 180 181 return (PyObject *)deque; 182} 183 184static PyObject * 185deque_pop(dequeobject *deque, PyObject *unused) 186{ 187 PyObject *item; 188 block *prevblock; 189 190 if (Py_SIZE(deque) == 0) { 191 PyErr_SetString(PyExc_IndexError, "pop from an empty deque"); 192 return NULL; 193 } 194 item = deque->rightblock->data[deque->rightindex]; 195 deque->rightindex--; 196 Py_SET_SIZE(deque, Py_SIZE(deque) - 1); 197 deque->state++; 198 199 if (deque->rightindex < 0) { 200 if (Py_SIZE(deque)) { 201 prevblock = deque->rightblock->leftlink; 202 assert(deque->leftblock != deque->rightblock); 203 freeblock(deque, deque->rightblock); 204 CHECK_NOT_END(prevblock); 205 MARK_END(prevblock->rightlink); 206 deque->rightblock = prevblock; 207 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 deque->leftindex = CENTER + 1; 213 deque->rightindex = CENTER; 214 } 215 } 216 return item; 217} 218 219PyDoc_STRVAR(pop_doc, "Remove and return the rightmost element."); 220 221static PyObject * 222deque_popleft(dequeobject *deque, PyObject *unused) 223{ 224 PyObject *item; 225 block *prevblock; 226 227 if (Py_SIZE(deque) == 0) { 228 PyErr_SetString(PyExc_IndexError, "pop from an empty deque"); 229 return NULL; 230 } 231 assert(deque->leftblock != NULL); 232 item = deque->leftblock->data[deque->leftindex]; 233 deque->leftindex++; 234 Py_SET_SIZE(deque, Py_SIZE(deque) - 1); 235 deque->state++; 236 237 if (deque->leftindex == BLOCKLEN) { 238 if (Py_SIZE(deque)) { 239 assert(deque->leftblock != deque->rightblock); 240 prevblock = deque->leftblock->rightlink; 241 freeblock(deque, deque->leftblock); 242 CHECK_NOT_END(prevblock); 243 MARK_END(prevblock->leftlink); 244 deque->leftblock = prevblock; 245 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 deque->leftindex = CENTER + 1; 251 deque->rightindex = CENTER; 252 } 253 } 254 return item; 255} 256 257PyDoc_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 273static inline int 274deque_append_internal(dequeobject *deque, PyObject *item, Py_ssize_t maxlen) 275{ 276 if (deque->rightindex == BLOCKLEN - 1) { 277 block *b = newblock(deque); 278 if (b == NULL) 279 return -1; 280 b->leftlink = deque->rightblock; 281 CHECK_END(deque->rightblock->rightlink); 282 deque->rightblock->rightlink = b; 283 deque->rightblock = b; 284 MARK_END(b->rightlink); 285 deque->rightindex = -1; 286 } 287 Py_SET_SIZE(deque, Py_SIZE(deque) + 1); 288 deque->rightindex++; 289 deque->rightblock->data[deque->rightindex] = item; 290 if (NEEDS_TRIM(deque, maxlen)) { 291 PyObject *olditem = deque_popleft(deque, NULL); 292 Py_DECREF(olditem); 293 } else { 294 deque->state++; 295 } 296 return 0; 297} 298 299static PyObject * 300deque_append(dequeobject *deque, PyObject *item) 301{ 302 Py_INCREF(item); 303 if (deque_append_internal(deque, item, deque->maxlen) < 0) 304 return NULL; 305 Py_RETURN_NONE; 306} 307 308PyDoc_STRVAR(append_doc, "Add an element to the right side of the deque."); 309 310static inline int 311deque_appendleft_internal(dequeobject *deque, PyObject *item, Py_ssize_t maxlen) 312{ 313 if (deque->leftindex == 0) { 314 block *b = newblock(deque); 315 if (b == NULL) 316 return -1; 317 b->rightlink = deque->leftblock; 318 CHECK_END(deque->leftblock->leftlink); 319 deque->leftblock->leftlink = b; 320 deque->leftblock = b; 321 MARK_END(b->leftlink); 322 deque->leftindex = BLOCKLEN; 323 } 324 Py_SET_SIZE(deque, Py_SIZE(deque) + 1); 325 deque->leftindex--; 326 deque->leftblock->data[deque->leftindex] = item; 327 if (NEEDS_TRIM(deque, deque->maxlen)) { 328 PyObject *olditem = deque_pop(deque, NULL); 329 Py_DECREF(olditem); 330 } else { 331 deque->state++; 332 } 333 return 0; 334} 335 336static PyObject * 337deque_appendleft(dequeobject *deque, PyObject *item) 338{ 339 Py_INCREF(item); 340 if (deque_appendleft_internal(deque, item, deque->maxlen) < 0) 341 return NULL; 342 Py_RETURN_NONE; 343} 344 345PyDoc_STRVAR(appendleft_doc, "Add an element to the left side of the deque."); 346 347static PyObject* 348finalize_iterator(PyObject *it) 349{ 350 if (PyErr_Occurred()) { 351 if (PyErr_ExceptionMatches(PyExc_StopIteration)) 352 PyErr_Clear(); 353 else { 354 Py_DECREF(it); 355 return NULL; 356 } 357 } 358 Py_DECREF(it); 359 Py_RETURN_NONE; 360} 361 362/* Run an iterator to exhaustion. Shortcut for 363 the extend/extendleft methods when maxlen == 0. */ 364static PyObject* 365consume_iterator(PyObject *it) 366{ 367 PyObject *(*iternext)(PyObject *); 368 PyObject *item; 369 370 iternext = *Py_TYPE(it)->tp_iternext; 371 while ((item = iternext(it)) != NULL) { 372 Py_DECREF(item); 373 } 374 return finalize_iterator(it); 375} 376 377static PyObject * 378deque_extend(dequeobject *deque, PyObject *iterable) 379{ 380 PyObject *it, *item; 381 PyObject *(*iternext)(PyObject *); 382 Py_ssize_t maxlen = deque->maxlen; 383 384 /* Handle case where id(deque) == id(iterable) */ 385 if ((PyObject *)deque == iterable) { 386 PyObject *result; 387 PyObject *s = PySequence_List(iterable); 388 if (s == NULL) 389 return NULL; 390 result = deque_extend(deque, s); 391 Py_DECREF(s); 392 return result; 393 } 394 395 it = PyObject_GetIter(iterable); 396 if (it == NULL) 397 return NULL; 398 399 if (maxlen == 0) 400 return consume_iterator(it); 401 402 /* Space saving heuristic. Start filling from the left */ 403 if (Py_SIZE(deque) == 0) { 404 assert(deque->leftblock == deque->rightblock); 405 assert(deque->leftindex == deque->rightindex+1); 406 deque->leftindex = 1; 407 deque->rightindex = 0; 408 } 409 410 iternext = *Py_TYPE(it)->tp_iternext; 411 while ((item = iternext(it)) != NULL) { 412 if (deque_append_internal(deque, item, maxlen) == -1) { 413 Py_DECREF(item); 414 Py_DECREF(it); 415 return NULL; 416 } 417 } 418 return finalize_iterator(it); 419} 420 421PyDoc_STRVAR(extend_doc, 422"Extend the right side of the deque with elements from the iterable"); 423 424static PyObject * 425deque_extendleft(dequeobject *deque, PyObject *iterable) 426{ 427 PyObject *it, *item; 428 PyObject *(*iternext)(PyObject *); 429 Py_ssize_t maxlen = deque->maxlen; 430 431 /* Handle case where id(deque) == id(iterable) */ 432 if ((PyObject *)deque == iterable) { 433 PyObject *result; 434 PyObject *s = PySequence_List(iterable); 435 if (s == NULL) 436 return NULL; 437 result = deque_extendleft(deque, s); 438 Py_DECREF(s); 439 return result; 440 } 441 442 it = PyObject_GetIter(iterable); 443 if (it == NULL) 444 return NULL; 445 446 if (maxlen == 0) 447 return consume_iterator(it); 448 449 /* Space saving heuristic. Start filling from the right */ 450 if (Py_SIZE(deque) == 0) { 451 assert(deque->leftblock == deque->rightblock); 452 assert(deque->leftindex == deque->rightindex+1); 453 deque->leftindex = BLOCKLEN - 1; 454 deque->rightindex = BLOCKLEN - 2; 455 } 456 457 iternext = *Py_TYPE(it)->tp_iternext; 458 while ((item = iternext(it)) != NULL) { 459 if (deque_appendleft_internal(deque, item, maxlen) == -1) { 460 Py_DECREF(item); 461 Py_DECREF(it); 462 return NULL; 463 } 464 } 465 return finalize_iterator(it); 466} 467 468PyDoc_STRVAR(extendleft_doc, 469"Extend the left side of the deque with elements from the iterable"); 470 471static PyObject * 472deque_inplace_concat(dequeobject *deque, PyObject *other) 473{ 474 PyObject *result; 475 476 result = deque_extend(deque, other); 477 if (result == NULL) 478 return result; 479 Py_INCREF(deque); 480 Py_DECREF(result); 481 return (PyObject *)deque; 482} 483 484static PyObject * 485deque_copy(PyObject *deque, PyObject *Py_UNUSED(ignored)) 486{ 487 PyObject *result; 488 dequeobject *old_deque = (dequeobject *)deque; 489 if (Py_IS_TYPE(deque, &deque_type)) { 490 dequeobject *new_deque; 491 PyObject *rv; 492 493 new_deque = (dequeobject *)deque_new(&deque_type, (PyObject *)NULL, (PyObject *)NULL); 494 if (new_deque == NULL) 495 return NULL; 496 new_deque->maxlen = old_deque->maxlen; 497 /* Fast path for the deque_repeat() common case where len(deque) == 1 */ 498 if (Py_SIZE(deque) == 1) { 499 PyObject *item = old_deque->leftblock->data[old_deque->leftindex]; 500 rv = deque_append(new_deque, item); 501 } else { 502 rv = deque_extend(new_deque, deque); 503 } 504 if (rv != NULL) { 505 Py_DECREF(rv); 506 return (PyObject *)new_deque; 507 } 508 Py_DECREF(new_deque); 509 return NULL; 510 } 511 if (old_deque->maxlen < 0) 512 result = PyObject_CallOneArg((PyObject *)(Py_TYPE(deque)), deque); 513 else 514 result = PyObject_CallFunction((PyObject *)(Py_TYPE(deque)), "Oi", 515 deque, old_deque->maxlen, NULL); 516 if (result != NULL && !PyObject_TypeCheck(result, &deque_type)) { 517 PyErr_Format(PyExc_TypeError, 518 "%.200s() must return a deque, not %.200s", 519 Py_TYPE(deque)->tp_name, Py_TYPE(result)->tp_name); 520 Py_DECREF(result); 521 return NULL; 522 } 523 return result; 524} 525 526PyDoc_STRVAR(copy_doc, "Return a shallow copy of a deque."); 527 528static PyObject * 529deque_concat(dequeobject *deque, PyObject *other) 530{ 531 PyObject *new_deque, *result; 532 int rv; 533 534 rv = PyObject_IsInstance(other, (PyObject *)&deque_type); 535 if (rv <= 0) { 536 if (rv == 0) { 537 PyErr_Format(PyExc_TypeError, 538 "can only concatenate deque (not \"%.200s\") to deque", 539 Py_TYPE(other)->tp_name); 540 } 541 return NULL; 542 } 543 544 new_deque = deque_copy((PyObject *)deque, NULL); 545 if (new_deque == NULL) 546 return NULL; 547 result = deque_extend((dequeobject *)new_deque, other); 548 if (result == NULL) { 549 Py_DECREF(new_deque); 550 return NULL; 551 } 552 Py_DECREF(result); 553 return new_deque; 554} 555 556static int 557deque_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 if (Py_SIZE(deque) == 0) 568 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 b = newblock(deque); 584 if (b == NULL) { 585 PyErr_Clear(); 586 goto alternate_method; 587 } 588 589 /* Remember the old size, leftblock, and leftindex */ 590 n = Py_SIZE(deque); 591 leftblock = deque->leftblock; 592 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 Py_SET_SIZE(deque, 0); 598 deque->leftblock = b; 599 deque->rightblock = b; 600 deque->leftindex = CENTER + 1; 601 deque->rightindex = CENTER; 602 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 m = (BLOCKLEN - leftindex > n) ? n : BLOCKLEN - leftindex; 608 itemptr = &leftblock->data[leftindex]; 609 limit = itemptr + m; 610 n -= m; 611 while (1) { 612 if (itemptr == limit) { 613 if (n == 0) 614 break; 615 CHECK_NOT_END(leftblock->rightlink); 616 prevblock = leftblock; 617 leftblock = leftblock->rightlink; 618 m = (n > BLOCKLEN) ? BLOCKLEN : n; 619 itemptr = leftblock->data; 620 limit = itemptr + m; 621 n -= m; 622 freeblock(deque, prevblock); 623 } 624 item = *(itemptr++); 625 Py_DECREF(item); 626 } 627 CHECK_END(leftblock->rightlink); 628 freeblock(deque, leftblock); 629 return 0; 630 631 alternate_method: 632 while (Py_SIZE(deque)) { 633 item = deque_pop(deque, NULL); 634 assert (item != NULL); 635 Py_DECREF(item); 636 } 637 return 0; 638} 639 640static PyObject * 641deque_clearmethod(dequeobject *deque, PyObject *Py_UNUSED(ignored)) 642{ 643 deque_clear(deque); 644 Py_RETURN_NONE; 645} 646 647PyDoc_STRVAR(clear_doc, "Remove all elements from the deque."); 648 649static PyObject * 650deque_inplace_repeat(dequeobject *deque, Py_ssize_t n) 651{ 652 Py_ssize_t i, m, size; 653 PyObject *seq; 654 PyObject *rv; 655 656 size = Py_SIZE(deque); 657 if (size == 0 || n == 1) { 658 Py_INCREF(deque); 659 return (PyObject *)deque; 660 } 661 662 if (n <= 0) { 663 deque_clear(deque); 664 Py_INCREF(deque); 665 return (PyObject *)deque; 666 } 667 668 if (size == 1) { 669 /* common case, repeating a single element */ 670 PyObject *item = deque->leftblock->data[deque->leftindex]; 671 672 if (deque->maxlen >= 0 && n > deque->maxlen) 673 n = deque->maxlen; 674 675 deque->state++; 676 for (i = 0 ; i < n-1 ; ) { 677 if (deque->rightindex == BLOCKLEN - 1) { 678 block *b = newblock(deque); 679 if (b == NULL) { 680 Py_SET_SIZE(deque, Py_SIZE(deque) + i); 681 return NULL; 682 } 683 b->leftlink = deque->rightblock; 684 CHECK_END(deque->rightblock->rightlink); 685 deque->rightblock->rightlink = b; 686 deque->rightblock = b; 687 MARK_END(b->rightlink); 688 deque->rightindex = -1; 689 } 690 m = n - 1 - i; 691 if (m > BLOCKLEN - 1 - deque->rightindex) 692 m = BLOCKLEN - 1 - deque->rightindex; 693 i += m; 694 while (m--) { 695 deque->rightindex++; 696 Py_INCREF(item); 697 deque->rightblock->data[deque->rightindex] = item; 698 } 699 } 700 Py_SET_SIZE(deque, Py_SIZE(deque) + i); 701 Py_INCREF(deque); 702 return (PyObject *)deque; 703 } 704 705 if ((size_t)size > PY_SSIZE_T_MAX / (size_t)n) { 706 return PyErr_NoMemory(); 707 } 708 709 seq = PySequence_List((PyObject *)deque); 710 if (seq == NULL) 711 return seq; 712 713 /* Reduce the number of repetitions when maxlen would be exceeded */ 714 if (deque->maxlen >= 0 && n * size > deque->maxlen) 715 n = (deque->maxlen + size - 1) / size; 716 717 for (i = 0 ; i < n-1 ; i++) { 718 rv = deque_extend(deque, seq); 719 if (rv == NULL) { 720 Py_DECREF(seq); 721 return NULL; 722 } 723 Py_DECREF(rv); 724 } 725 Py_INCREF(deque); 726 Py_DECREF(seq); 727 return (PyObject *)deque; 728} 729 730static PyObject * 731deque_repeat(dequeobject *deque, Py_ssize_t n) 732{ 733 dequeobject *new_deque; 734 PyObject *rv; 735 736 new_deque = (dequeobject *)deque_copy((PyObject *) deque, NULL); 737 if (new_deque == NULL) 738 return NULL; 739 rv = deque_inplace_repeat(new_deque, n); 740 Py_DECREF(new_deque); 741 return rv; 742} 743 744/* The rotate() method is part of the public API and is used internally 745as a primitive for other methods. 746 747Rotation by 1 or -1 is a common case, so any optimizations for high 748volume rotations should take care not to penalize the common case. 749 750Conceptually, a rotate by one is equivalent to a pop on one side and an 751append on the other. However, a pop/append pair is unnecessarily slow 752because it requires an incref/decref pair for an object located randomly 753in memory. It is better to just move the object pointer from one block 754to the next without changing the reference count. 755 756When moving batches of pointers, it is tempting to use memcpy() but that 757proved to be slower than a simple loop for a variety of reasons. 758Memcpy() cannot know in advance that we're copying pointers instead of 759bytes, that the source and destination are pointer aligned and 760non-overlapping, that moving just one pointer is a common case, that we 761never need to move more than BLOCKLEN pointers, and that at least one 762pointer is always moved. 763 764For high volume rotations, newblock() and freeblock() are never called 765more than once. Previously emptied blocks are immediately reused as a 766destination block. If a block is left-over at the end, it is freed. 767*/ 768 769static int 770_deque_rotate(dequeobject *deque, Py_ssize_t n) 771{ 772 block *b = NULL; 773 block *leftblock = deque->leftblock; 774 block *rightblock = deque->rightblock; 775 Py_ssize_t leftindex = deque->leftindex; 776 Py_ssize_t rightindex = deque->rightindex; 777 Py_ssize_t len=Py_SIZE(deque), halflen=len>>1; 778 int rv = -1; 779 780 if (len <= 1) 781 return 0; 782 if (n > halflen || n < -halflen) { 783 n %= len; 784 if (n > halflen) 785 n -= len; 786 else if (n < -halflen) 787 n += len; 788 } 789 assert(len > 1); 790 assert(-halflen <= n && n <= halflen); 791 792 deque->state++; 793 while (n > 0) { 794 if (leftindex == 0) { 795 if (b == NULL) { 796 b = newblock(deque); 797 if (b == NULL) 798 goto done; 799 } 800 b->rightlink = leftblock; 801 CHECK_END(leftblock->leftlink); 802 leftblock->leftlink = b; 803 leftblock = b; 804 MARK_END(b->leftlink); 805 leftindex = BLOCKLEN; 806 b = NULL; 807 } 808 assert(leftindex > 0); 809 { 810 PyObject **src, **dest; 811 Py_ssize_t m = n; 812 813 if (m > rightindex + 1) 814 m = rightindex + 1; 815 if (m > leftindex) 816 m = leftindex; 817 assert (m > 0 && m <= len); 818 rightindex -= m; 819 leftindex -= m; 820 src = &rightblock->data[rightindex + 1]; 821 dest = &leftblock->data[leftindex]; 822 n -= m; 823 do { 824 *(dest++) = *(src++); 825 } while (--m); 826 } 827 if (rightindex < 0) { 828 assert(leftblock != rightblock); 829 assert(b == NULL); 830 b = rightblock; 831 CHECK_NOT_END(rightblock->leftlink); 832 rightblock = rightblock->leftlink; 833 MARK_END(rightblock->rightlink); 834 rightindex = BLOCKLEN - 1; 835 } 836 } 837 while (n < 0) { 838 if (rightindex == BLOCKLEN - 1) { 839 if (b == NULL) { 840 b = newblock(deque); 841 if (b == NULL) 842 goto done; 843 } 844 b->leftlink = rightblock; 845 CHECK_END(rightblock->rightlink); 846 rightblock->rightlink = b; 847 rightblock = b; 848 MARK_END(b->rightlink); 849 rightindex = -1; 850 b = NULL; 851 } 852 assert (rightindex < BLOCKLEN - 1); 853 { 854 PyObject **src, **dest; 855 Py_ssize_t m = -n; 856 857 if (m > BLOCKLEN - leftindex) 858 m = BLOCKLEN - leftindex; 859 if (m > BLOCKLEN - 1 - rightindex) 860 m = BLOCKLEN - 1 - rightindex; 861 assert (m > 0 && m <= len); 862 src = &leftblock->data[leftindex]; 863 dest = &rightblock->data[rightindex + 1]; 864 leftindex += m; 865 rightindex += m; 866 n += m; 867 do { 868 *(dest++) = *(src++); 869 } while (--m); 870 } 871 if (leftindex == BLOCKLEN) { 872 assert(leftblock != rightblock); 873 assert(b == NULL); 874 b = leftblock; 875 CHECK_NOT_END(leftblock->rightlink); 876 leftblock = leftblock->rightlink; 877 MARK_END(leftblock->leftlink); 878 leftindex = 0; 879 } 880 } 881 rv = 0; 882done: 883 if (b != NULL) 884 freeblock(deque, b); 885 deque->leftblock = leftblock; 886 deque->rightblock = rightblock; 887 deque->leftindex = leftindex; 888 deque->rightindex = rightindex; 889 890 return rv; 891} 892 893static PyObject * 894deque_rotate(dequeobject *deque, PyObject *const *args, Py_ssize_t nargs) 895{ 896 Py_ssize_t n=1; 897 898 if (!_PyArg_CheckPositional("deque.rotate", nargs, 0, 1)) { 899 return NULL; 900 } 901 if (nargs) { 902 PyObject *index = _PyNumber_Index(args[0]); 903 if (index == NULL) { 904 return NULL; 905 } 906 n = PyLong_AsSsize_t(index); 907 Py_DECREF(index); 908 if (n == -1 && PyErr_Occurred()) { 909 return NULL; 910 } 911 } 912 913 if (!_deque_rotate(deque, n)) 914 Py_RETURN_NONE; 915 return NULL; 916} 917 918PyDoc_STRVAR(rotate_doc, 919"Rotate the deque n steps to the right (default n=1). If n is negative, rotates left."); 920 921static PyObject * 922deque_reverse(dequeobject *deque, PyObject *unused) 923{ 924 block *leftblock = deque->leftblock; 925 block *rightblock = deque->rightblock; 926 Py_ssize_t leftindex = deque->leftindex; 927 Py_ssize_t rightindex = deque->rightindex; 928 Py_ssize_t n = Py_SIZE(deque) >> 1; 929 PyObject *tmp; 930 931 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 tmp = leftblock->data[leftindex]; 939 leftblock->data[leftindex] = rightblock->data[rightindex]; 940 rightblock->data[rightindex] = tmp; 941 942 /* Advance left block/index pair */ 943 leftindex++; 944 if (leftindex == BLOCKLEN) { 945 leftblock = leftblock->rightlink; 946 leftindex = 0; 947 } 948 949 /* Step backwards with the right block/index pair */ 950 rightindex--; 951 if (rightindex < 0) { 952 rightblock = rightblock->leftlink; 953 rightindex = BLOCKLEN - 1; 954 } 955 } 956 Py_RETURN_NONE; 957} 958 959PyDoc_STRVAR(reverse_doc, 960"D.reverse() -- reverse *IN PLACE*"); 961 962static PyObject * 963deque_count(dequeobject *deque, PyObject *v) 964{ 965 block *b = deque->leftblock; 966 Py_ssize_t index = deque->leftindex; 967 Py_ssize_t n = Py_SIZE(deque); 968 Py_ssize_t count = 0; 969 size_t start_state = deque->state; 970 PyObject *item; 971 int cmp; 972 973 while (--n >= 0) { 974 CHECK_NOT_END(b); 975 item = b->data[index]; 976 Py_INCREF(item); 977 cmp = PyObject_RichCompareBool(item, v, Py_EQ); 978 Py_DECREF(item); 979 if (cmp < 0) 980 return NULL; 981 count += cmp; 982 983 if (start_state != deque->state) { 984 PyErr_SetString(PyExc_RuntimeError, 985 "deque mutated during iteration"); 986 return NULL; 987 } 988 989 /* Advance left block/index pair */ 990 index++; 991 if (index == BLOCKLEN) { 992 b = b->rightlink; 993 index = 0; 994 } 995 } 996 return PyLong_FromSsize_t(count); 997} 998 999PyDoc_STRVAR(count_doc, 1000"D.count(value) -- return number of occurrences of value"); 1001 1002static int 1003deque_contains(dequeobject *deque, PyObject *v) 1004{ 1005 block *b = deque->leftblock; 1006 Py_ssize_t index = deque->leftindex; 1007 Py_ssize_t n = Py_SIZE(deque); 1008 size_t start_state = deque->state; 1009 PyObject *item; 1010 int cmp; 1011 1012 while (--n >= 0) { 1013 CHECK_NOT_END(b); 1014 item = b->data[index]; 1015 Py_INCREF(item); 1016 cmp = PyObject_RichCompareBool(item, v, Py_EQ); 1017 Py_DECREF(item); 1018 if (cmp) { 1019 return cmp; 1020 } 1021 if (start_state != deque->state) { 1022 PyErr_SetString(PyExc_RuntimeError, 1023 "deque mutated during iteration"); 1024 return -1; 1025 } 1026 index++; 1027 if (index == BLOCKLEN) { 1028 b = b->rightlink; 1029 index = 0; 1030 } 1031 } 1032 return 0; 1033} 1034 1035static Py_ssize_t 1036deque_len(dequeobject *deque) 1037{ 1038 return Py_SIZE(deque); 1039} 1040 1041static PyObject * 1042deque_index(dequeobject *deque, PyObject *const *args, Py_ssize_t nargs) 1043{ 1044 Py_ssize_t i, n, start=0, stop=Py_SIZE(deque); 1045 PyObject *v, *item; 1046 block *b = deque->leftblock; 1047 Py_ssize_t index = deque->leftindex; 1048 size_t start_state = deque->state; 1049 int cmp; 1050 1051 if (!_PyArg_ParseStack(args, nargs, "O|O&O&:index", &v, 1052 _PyEval_SliceIndexNotNone, &start, 1053 _PyEval_SliceIndexNotNone, &stop)) { 1054 return NULL; 1055 } 1056 1057 if (start < 0) { 1058 start += Py_SIZE(deque); 1059 if (start < 0) 1060 start = 0; 1061 } 1062 if (stop < 0) { 1063 stop += Py_SIZE(deque); 1064 if (stop < 0) 1065 stop = 0; 1066 } 1067 if (stop > Py_SIZE(deque)) 1068 stop = Py_SIZE(deque); 1069 if (start > stop) 1070 start = stop; 1071 assert(0 <= start && start <= stop && stop <= Py_SIZE(deque)); 1072 1073 for (i=0 ; i < start - BLOCKLEN ; i += BLOCKLEN) { 1074 b = b->rightlink; 1075 } 1076 for ( ; i < start ; i++) { 1077 index++; 1078 if (index == BLOCKLEN) { 1079 b = b->rightlink; 1080 index = 0; 1081 } 1082 } 1083 1084 n = stop - i; 1085 while (--n >= 0) { 1086 CHECK_NOT_END(b); 1087 item = b->data[index]; 1088 cmp = PyObject_RichCompareBool(item, v, Py_EQ); 1089 if (cmp > 0) 1090 return PyLong_FromSsize_t(stop - n - 1); 1091 if (cmp < 0) 1092 return NULL; 1093 if (start_state != deque->state) { 1094 PyErr_SetString(PyExc_RuntimeError, 1095 "deque mutated during iteration"); 1096 return NULL; 1097 } 1098 index++; 1099 if (index == BLOCKLEN) { 1100 b = b->rightlink; 1101 index = 0; 1102 } 1103 } 1104 PyErr_Format(PyExc_ValueError, "%R is not in deque", v); 1105 return NULL; 1106} 1107 1108PyDoc_STRVAR(index_doc, 1109"D.index(value, [start, [stop]]) -- 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 1120static PyObject * 1121deque_insert(dequeobject *deque, PyObject *const *args, Py_ssize_t nargs) 1122{ 1123 Py_ssize_t index; 1124 Py_ssize_t n = Py_SIZE(deque); 1125 PyObject *value; 1126 PyObject *rv; 1127 1128 if (!_PyArg_ParseStack(args, nargs, "nO:insert", &index, &value)) { 1129 return NULL; 1130 } 1131 1132 if (deque->maxlen == Py_SIZE(deque)) { 1133 PyErr_SetString(PyExc_IndexError, "deque already at its maximum size"); 1134 return NULL; 1135 } 1136 if (index >= n) 1137 return deque_append(deque, value); 1138 if (index <= -n || index == 0) 1139 return deque_appendleft(deque, value); 1140 if (_deque_rotate(deque, -index)) 1141 return NULL; 1142 if (index < 0) 1143 rv = deque_append(deque, value); 1144 else 1145 rv = deque_appendleft(deque, value); 1146 if (rv == NULL) 1147 return NULL; 1148 Py_DECREF(rv); 1149 if (_deque_rotate(deque, index)) 1150 return NULL; 1151 Py_RETURN_NONE; 1152} 1153 1154PyDoc_STRVAR(insert_doc, 1155"D.insert(index, object) -- insert object before index"); 1156 1157PyDoc_STRVAR(remove_doc, 1158"D.remove(value) -- remove first occurrence of value."); 1159 1160static int 1161valid_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 return (size_t) i < (size_t) limit; 1166} 1167 1168static PyObject * 1169deque_item(dequeobject *deque, Py_ssize_t i) 1170{ 1171 block *b; 1172 PyObject *item; 1173 Py_ssize_t n, index=i; 1174 1175 if (!valid_index(i, Py_SIZE(deque))) { 1176 PyErr_SetString(PyExc_IndexError, "deque index out of range"); 1177 return NULL; 1178 } 1179 1180 if (i == 0) { 1181 i = deque->leftindex; 1182 b = deque->leftblock; 1183 } else if (i == Py_SIZE(deque) - 1) { 1184 i = deque->rightindex; 1185 b = deque->rightblock; 1186 } else { 1187 i += deque->leftindex; 1188 n = (Py_ssize_t)((size_t) i / BLOCKLEN); 1189 i = (Py_ssize_t)((size_t) i % BLOCKLEN); 1190 if (index < (Py_SIZE(deque) >> 1)) { 1191 b = deque->leftblock; 1192 while (--n >= 0) 1193 b = b->rightlink; 1194 } else { 1195 n = (Py_ssize_t)( 1196 ((size_t)(deque->leftindex + Py_SIZE(deque) - 1)) 1197 / BLOCKLEN - n); 1198 b = deque->rightblock; 1199 while (--n >= 0) 1200 b = b->leftlink; 1201 } 1202 } 1203 item = b->data[i]; 1204 Py_INCREF(item); 1205 return item; 1206} 1207 1208static int 1209deque_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 if (_deque_rotate(deque, -i)) 1216 return -1; 1217 item = deque_popleft(deque, NULL); 1218 rv = _deque_rotate(deque, i); 1219 assert (item != NULL); 1220 Py_DECREF(item); 1221 return rv; 1222} 1223 1224static PyObject * 1225deque_remove(dequeobject *deque, PyObject *value) 1226{ 1227 PyObject *item; 1228 block *b = deque->leftblock; 1229 Py_ssize_t i, n = Py_SIZE(deque), index = deque->leftindex; 1230 size_t start_state = deque->state; 1231 int cmp, rv; 1232 1233 for (i = 0 ; i < n; i++) { 1234 item = b->data[index]; 1235 Py_INCREF(item); 1236 cmp = PyObject_RichCompareBool(item, value, Py_EQ); 1237 Py_DECREF(item); 1238 if (cmp < 0) { 1239 return NULL; 1240 } 1241 if (start_state != deque->state) { 1242 PyErr_SetString(PyExc_IndexError, 1243 "deque mutated during iteration"); 1244 return NULL; 1245 } 1246 if (cmp > 0) { 1247 break; 1248 } 1249 index++; 1250 if (index == BLOCKLEN) { 1251 b = b->rightlink; 1252 index = 0; 1253 } 1254 } 1255 if (i == n) { 1256 PyErr_Format(PyExc_ValueError, "%R is not in deque", value); 1257 return NULL; 1258 } 1259 rv = deque_del_item(deque, i); 1260 if (rv == -1) { 1261 return NULL; 1262 } 1263 Py_RETURN_NONE; 1264} 1265 1266static int 1267deque_ass_item(dequeobject *deque, Py_ssize_t i, PyObject *v) 1268{ 1269 PyObject *old_value; 1270 block *b; 1271 Py_ssize_t n, len=Py_SIZE(deque), halflen=(len+1)>>1, index=i; 1272 1273 if (!valid_index(i, len)) { 1274 PyErr_SetString(PyExc_IndexError, "deque index out of range"); 1275 return -1; 1276 } 1277 if (v == NULL) 1278 return deque_del_item(deque, i); 1279 1280 i += deque->leftindex; 1281 n = (Py_ssize_t)((size_t) i / BLOCKLEN); 1282 i = (Py_ssize_t)((size_t) i % BLOCKLEN); 1283 if (index <= halflen) { 1284 b = deque->leftblock; 1285 while (--n >= 0) 1286 b = b->rightlink; 1287 } else { 1288 n = (Py_ssize_t)( 1289 ((size_t)(deque->leftindex + Py_SIZE(deque) - 1)) 1290 / BLOCKLEN - n); 1291 b = deque->rightblock; 1292 while (--n >= 0) 1293 b = b->leftlink; 1294 } 1295 Py_INCREF(v); 1296 old_value = b->data[i]; 1297 b->data[i] = v; 1298 Py_DECREF(old_value); 1299 return 0; 1300} 1301 1302static void 1303deque_dealloc(dequeobject *deque) 1304{ 1305 Py_ssize_t i; 1306 1307 PyObject_GC_UnTrack(deque); 1308 if (deque->weakreflist != NULL) 1309 PyObject_ClearWeakRefs((PyObject *) deque); 1310 if (deque->leftblock != NULL) { 1311 deque_clear(deque); 1312 assert(deque->leftblock != NULL); 1313 freeblock(deque, deque->leftblock); 1314 } 1315 deque->leftblock = NULL; 1316 deque->rightblock = NULL; 1317 for (i=0 ; i < deque->numfreeblocks ; i++) { 1318 PyMem_Free(deque->freeblocks[i]); 1319 } 1320 Py_TYPE(deque)->tp_free(deque); 1321} 1322 1323static int 1324deque_traverse(dequeobject *deque, visitproc visit, void *arg) 1325{ 1326 block *b; 1327 PyObject *item; 1328 Py_ssize_t index; 1329 Py_ssize_t indexlo = deque->leftindex; 1330 Py_ssize_t indexhigh; 1331 1332 for (b = deque->leftblock; b != deque->rightblock; b = b->rightlink) { 1333 for (index = indexlo; index < BLOCKLEN ; index++) { 1334 item = b->data[index]; 1335 Py_VISIT(item); 1336 } 1337 indexlo = 0; 1338 } 1339 indexhigh = deque->rightindex; 1340 for (index = indexlo; index <= indexhigh; index++) { 1341 item = b->data[index]; 1342 Py_VISIT(item); 1343 } 1344 return 0; 1345} 1346 1347static PyObject * 1348deque_reduce(dequeobject *deque, PyObject *Py_UNUSED(ignored)) 1349{ 1350 PyObject *state, *it; 1351 1352 state = _PyObject_GetState((PyObject *)deque); 1353 if (state == NULL) { 1354 return NULL; 1355 } 1356 1357 it = PyObject_GetIter((PyObject *)deque); 1358 if (it == NULL) { 1359 Py_DECREF(state); 1360 return NULL; 1361 } 1362 1363 if (deque->maxlen < 0) { 1364 return Py_BuildValue("O()NN", Py_TYPE(deque), state, it); 1365 } 1366 else { 1367 return Py_BuildValue("O(()n)NN", Py_TYPE(deque), deque->maxlen, state, it); 1368 } 1369} 1370 1371PyDoc_STRVAR(reduce_doc, "Return state information for pickling."); 1372 1373static PyObject * 1374deque_repr(PyObject *deque) 1375{ 1376 PyObject *aslist, *result; 1377 int i; 1378 1379 i = Py_ReprEnter(deque); 1380 if (i != 0) { 1381 if (i < 0) 1382 return NULL; 1383 return PyUnicode_FromString("[...]"); 1384 } 1385 1386 aslist = PySequence_List(deque); 1387 if (aslist == NULL) { 1388 Py_ReprLeave(deque); 1389 return NULL; 1390 } 1391 if (((dequeobject *)deque)->maxlen >= 0) 1392 result = PyUnicode_FromFormat("%s(%R, maxlen=%zd)", 1393 _PyType_Name(Py_TYPE(deque)), aslist, 1394 ((dequeobject *)deque)->maxlen); 1395 else 1396 result = PyUnicode_FromFormat("%s(%R)", 1397 _PyType_Name(Py_TYPE(deque)), aslist); 1398 Py_ReprLeave(deque); 1399 Py_DECREF(aslist); 1400 return result; 1401} 1402 1403static PyObject * 1404deque_richcompare(PyObject *v, PyObject *w, int op) 1405{ 1406 PyObject *it1=NULL, *it2=NULL, *x, *y; 1407 Py_ssize_t vs, ws; 1408 int b, cmp=-1; 1409 1410 if (!PyObject_TypeCheck(v, &deque_type) || 1411 !PyObject_TypeCheck(w, &deque_type)) { 1412 Py_RETURN_NOTIMPLEMENTED; 1413 } 1414 1415 /* Shortcuts */ 1416 vs = Py_SIZE((dequeobject *)v); 1417 ws = Py_SIZE((dequeobject *)w); 1418 if (op == Py_EQ) { 1419 if (v == w) 1420 Py_RETURN_TRUE; 1421 if (vs != ws) 1422 Py_RETURN_FALSE; 1423 } 1424 if (op == Py_NE) { 1425 if (v == w) 1426 Py_RETURN_FALSE; 1427 if (vs != ws) 1428 Py_RETURN_TRUE; 1429 } 1430 1431 /* Search for the first index where items are different */ 1432 it1 = PyObject_GetIter(v); 1433 if (it1 == NULL) 1434 goto done; 1435 it2 = PyObject_GetIter(w); 1436 if (it2 == NULL) 1437 goto done; 1438 for (;;) { 1439 x = PyIter_Next(it1); 1440 if (x == NULL && PyErr_Occurred()) 1441 goto done; 1442 y = PyIter_Next(it2); 1443 if (x == NULL || y == NULL) 1444 break; 1445 b = PyObject_RichCompareBool(x, y, Py_EQ); 1446 if (b == 0) { 1447 cmp = PyObject_RichCompareBool(x, y, op); 1448 Py_DECREF(x); 1449 Py_DECREF(y); 1450 goto done; 1451 } 1452 Py_DECREF(x); 1453 Py_DECREF(y); 1454 if (b < 0) 1455 goto done; 1456 } 1457 /* We reached the end of one deque or both */ 1458 Py_XDECREF(x); 1459 Py_XDECREF(y); 1460 if (PyErr_Occurred()) 1461 goto done; 1462 switch (op) { 1463 case Py_LT: cmp = y != NULL; break; /* if w was longer */ 1464 case Py_LE: cmp = x == NULL; break; /* if v was not longer */ 1465 case Py_EQ: cmp = x == y; break; /* if we reached the end of both */ 1466 case Py_NE: cmp = x != y; break; /* if one deque continues */ 1467 case Py_GT: cmp = x != NULL; break; /* if v was longer */ 1468 case Py_GE: cmp = y == NULL; break; /* if w was not longer */ 1469 } 1470 1471done: 1472 Py_XDECREF(it1); 1473 Py_XDECREF(it2); 1474 if (cmp == 1) 1475 Py_RETURN_TRUE; 1476 if (cmp == 0) 1477 Py_RETURN_FALSE; 1478 return NULL; 1479} 1480 1481static int 1482deque_init(dequeobject *deque, PyObject *args, PyObject *kwdargs) 1483{ 1484 PyObject *iterable = NULL; 1485 PyObject *maxlenobj = NULL; 1486 Py_ssize_t maxlen = -1; 1487 char *kwlist[] = {"iterable", "maxlen", 0}; 1488 1489 if (kwdargs == NULL && PyTuple_GET_SIZE(args) <= 2) { 1490 if (PyTuple_GET_SIZE(args) > 0) { 1491 iterable = PyTuple_GET_ITEM(args, 0); 1492 } 1493 if (PyTuple_GET_SIZE(args) > 1) { 1494 maxlenobj = PyTuple_GET_ITEM(args, 1); 1495 } 1496 } else { 1497 if (!PyArg_ParseTupleAndKeywords(args, kwdargs, "|OO:deque", kwlist, 1498 &iterable, &maxlenobj)) 1499 return -1; 1500 } 1501 if (maxlenobj != NULL && maxlenobj != Py_None) { 1502 maxlen = PyLong_AsSsize_t(maxlenobj); 1503 if (maxlen == -1 && PyErr_Occurred()) 1504 return -1; 1505 if (maxlen < 0) { 1506 PyErr_SetString(PyExc_ValueError, "maxlen must be non-negative"); 1507 return -1; 1508 } 1509 } 1510 deque->maxlen = maxlen; 1511 if (Py_SIZE(deque) > 0) 1512 deque_clear(deque); 1513 if (iterable != NULL) { 1514 PyObject *rv = deque_extend(deque, iterable); 1515 if (rv == NULL) 1516 return -1; 1517 Py_DECREF(rv); 1518 } 1519 return 0; 1520} 1521 1522static PyObject * 1523deque_sizeof(dequeobject *deque, void *unused) 1524{ 1525 Py_ssize_t res; 1526 Py_ssize_t blocks; 1527 1528 res = _PyObject_SIZE(Py_TYPE(deque)); 1529 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 res += blocks * sizeof(block); 1533 return PyLong_FromSsize_t(res); 1534} 1535 1536PyDoc_STRVAR(sizeof_doc, 1537"D.__sizeof__() -- size of D in memory, in bytes"); 1538 1539static PyObject * 1540deque_get_maxlen(dequeobject *deque, void *Py_UNUSED(ignored)) 1541{ 1542 if (deque->maxlen < 0) 1543 Py_RETURN_NONE; 1544 return PyLong_FromSsize_t(deque->maxlen); 1545} 1546 1547 1548/* deque object ********************************************************/ 1549 1550static 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 1556static 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 1569static PyObject *deque_iter(dequeobject *deque); 1570static PyObject *deque_reviter(dequeobject *deque, PyObject *Py_UNUSED(ignored)); 1571PyDoc_STRVAR(reversed_doc, 1572 "D.__reversed__() -- return a reverse iterator over the deque"); 1573 1574static 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 1616PyDoc_STRVAR(deque_doc, 1617"deque([iterable[, maxlen]]) --> deque object\n\ 1618\n\ 1619A list-like sequence optimized for data accesses near its endpoints."); 1620 1621static 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 1668typedef 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 1677static PyTypeObject dequeiter_type; 1678 1679static PyObject * 1680deque_iter(dequeobject *deque) 1681{ 1682 dequeiterobject *it; 1683 1684 it = PyObject_GC_New(dequeiterobject, &dequeiter_type); 1685 if (it == NULL) 1686 return NULL; 1687 it->b = deque->leftblock; 1688 it->index = deque->leftindex; 1689 Py_INCREF(deque); 1690 it->deque = deque; 1691 it->state = deque->state; 1692 it->counter = Py_SIZE(deque); 1693 PyObject_GC_Track(it); 1694 return (PyObject *)it; 1695} 1696 1697static int 1698dequeiter_traverse(dequeiterobject *dio, visitproc visit, void *arg) 1699{ 1700 Py_VISIT(dio->deque); 1701 return 0; 1702} 1703 1704static void 1705dequeiter_dealloc(dequeiterobject *dio) 1706{ 1707 /* bpo-31095: UnTrack is needed before calling any callbacks */ 1708 PyObject_GC_UnTrack(dio); 1709 Py_XDECREF(dio->deque); 1710 PyObject_GC_Del(dio); 1711} 1712 1713static PyObject * 1714dequeiter_next(dequeiterobject *it) 1715{ 1716 PyObject *item; 1717 1718 if (it->deque->state != it->state) { 1719 it->counter = 0; 1720 PyErr_SetString(PyExc_RuntimeError, 1721 "deque mutated during iteration"); 1722 return NULL; 1723 } 1724 if (it->counter == 0) 1725 return NULL; 1726 assert (!(it->b == it->deque->rightblock && 1727 it->index > it->deque->rightindex)); 1728 1729 item = it->b->data[it->index]; 1730 it->index++; 1731 it->counter--; 1732 if (it->index == BLOCKLEN && it->counter > 0) { 1733 CHECK_NOT_END(it->b->rightlink); 1734 it->b = it->b->rightlink; 1735 it->index = 0; 1736 } 1737 Py_INCREF(item); 1738 return item; 1739} 1740 1741static PyObject * 1742dequeiter_new(PyTypeObject *type, PyObject *args, PyObject *kwds) 1743{ 1744 Py_ssize_t i, index=0; 1745 PyObject *deque; 1746 dequeiterobject *it; 1747 if (!PyArg_ParseTuple(args, "O!|n", &deque_type, &deque, &index)) 1748 return NULL; 1749 assert(type == &dequeiter_type); 1750 1751 it = (dequeiterobject*)deque_iter((dequeobject *)deque); 1752 if (!it) 1753 return NULL; 1754 /* consume items from the queue */ 1755 for(i=0; i<index; i++) { 1756 PyObject *item = dequeiter_next(it); 1757 if (item) { 1758 Py_DECREF(item); 1759 } else { 1760 if (it->counter) { 1761 Py_DECREF(it); 1762 return NULL; 1763 } else 1764 break; 1765 } 1766 } 1767 return (PyObject*)it; 1768} 1769 1770static PyObject * 1771dequeiter_len(dequeiterobject *it, PyObject *Py_UNUSED(ignored)) 1772{ 1773 return PyLong_FromSsize_t(it->counter); 1774} 1775 1776PyDoc_STRVAR(length_hint_doc, "Private method returning an estimate of len(list(it))."); 1777 1778static PyObject * 1779dequeiter_reduce(dequeiterobject *it, PyObject *Py_UNUSED(ignored)) 1780{ 1781 return Py_BuildValue("O(On)", Py_TYPE(it), it->deque, Py_SIZE(it->deque) - it->counter); 1782} 1783 1784static 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 1790static 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 1835static PyTypeObject dequereviter_type; 1836 1837static PyObject * 1838deque_reviter(dequeobject *deque, PyObject *Py_UNUSED(ignored)) 1839{ 1840 dequeiterobject *it; 1841 1842 it = PyObject_GC_New(dequeiterobject, &dequereviter_type); 1843 if (it == NULL) 1844 return NULL; 1845 it->b = deque->rightblock; 1846 it->index = deque->rightindex; 1847 Py_INCREF(deque); 1848 it->deque = deque; 1849 it->state = deque->state; 1850 it->counter = Py_SIZE(deque); 1851 PyObject_GC_Track(it); 1852 return (PyObject *)it; 1853} 1854 1855static PyObject * 1856dequereviter_next(dequeiterobject *it) 1857{ 1858 PyObject *item; 1859 if (it->counter == 0) 1860 return NULL; 1861 1862 if (it->deque->state != it->state) { 1863 it->counter = 0; 1864 PyErr_SetString(PyExc_RuntimeError, 1865 "deque mutated during iteration"); 1866 return NULL; 1867 } 1868 assert (!(it->b == it->deque->leftblock && 1869 it->index < it->deque->leftindex)); 1870 1871 item = it->b->data[it->index]; 1872 it->index--; 1873 it->counter--; 1874 if (it->index < 0 && it->counter > 0) { 1875 CHECK_NOT_END(it->b->leftlink); 1876 it->b = it->b->leftlink; 1877 it->index = BLOCKLEN - 1; 1878 } 1879 Py_INCREF(item); 1880 return item; 1881} 1882 1883static PyObject * 1884dequereviter_new(PyTypeObject *type, PyObject *args, PyObject *kwds) 1885{ 1886 Py_ssize_t i, index=0; 1887 PyObject *deque; 1888 dequeiterobject *it; 1889 if (!PyArg_ParseTuple(args, "O!|n", &deque_type, &deque, &index)) 1890 return NULL; 1891 assert(type == &dequereviter_type); 1892 1893 it = (dequeiterobject*)deque_reviter((dequeobject *)deque, NULL); 1894 if (!it) 1895 return NULL; 1896 /* consume items from the queue */ 1897 for(i=0; i<index; i++) { 1898 PyObject *item = dequereviter_next(it); 1899 if (item) { 1900 Py_DECREF(item); 1901 } else { 1902 if (it->counter) { 1903 Py_DECREF(it); 1904 return NULL; 1905 } else 1906 break; 1907 } 1908 } 1909 return (PyObject*)it; 1910} 1911 1912static 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 1957typedef struct { 1958 PyDictObject dict; 1959 PyObject *default_factory; 1960} defdictobject; 1961 1962static PyTypeObject defdict_type; /* Forward */ 1963 1964PyDoc_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 1971static PyObject * 1972defdict_missing(defdictobject *dd, PyObject *key) 1973{ 1974 PyObject *factory = dd->default_factory; 1975 PyObject *value; 1976 if (factory == NULL || factory == Py_None) { 1977 /* XXX Call dict.__missing__(key) */ 1978 PyObject *tup; 1979 tup = PyTuple_Pack(1, key); 1980 if (!tup) return NULL; 1981 PyErr_SetObject(PyExc_KeyError, tup); 1982 Py_DECREF(tup); 1983 return NULL; 1984 } 1985 value = _PyObject_CallNoArgs(factory); 1986 if (value == NULL) 1987 return value; 1988 if (PyObject_SetItem((PyObject *)dd, key, value) < 0) { 1989 Py_DECREF(value); 1990 return NULL; 1991 } 1992 return value; 1993} 1994 1995static inline PyObject* 1996new_defdict(defdictobject *dd, PyObject *arg) 1997{ 1998 return PyObject_CallFunctionObjArgs((PyObject*)Py_TYPE(dd), 1999 dd->default_factory ? dd->default_factory : Py_None, arg, NULL); 2000} 2001 2002PyDoc_STRVAR(defdict_copy_doc, "D.copy() -> a shallow copy of D."); 2003 2004static PyObject * 2005defdict_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 return new_defdict(dd, (PyObject*)dd); 2012} 2013 2014static PyObject * 2015defdict_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 if (dd->default_factory == NULL || dd->default_factory == Py_None) 2045 args = PyTuple_New(0); 2046 else 2047 args = PyTuple_Pack(1, dd->default_factory); 2048 if (args == NULL) 2049 return NULL; 2050 items = PyObject_CallMethodNoArgs((PyObject *)dd, &_Py_ID(items)); 2051 if (items == NULL) { 2052 Py_DECREF(args); 2053 return NULL; 2054 } 2055 iter = PyObject_GetIter(items); 2056 if (iter == NULL) { 2057 Py_DECREF(items); 2058 Py_DECREF(args); 2059 return NULL; 2060 } 2061 result = PyTuple_Pack(5, Py_TYPE(dd), args, 2062 Py_None, Py_None, iter); 2063 Py_DECREF(iter); 2064 Py_DECREF(items); 2065 Py_DECREF(args); 2066 return result; 2067} 2068 2069static 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 2083static 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 2090static void 2091defdict_dealloc(defdictobject *dd) 2092{ 2093 /* bpo-31095: UnTrack is needed before calling any callbacks */ 2094 PyObject_GC_UnTrack(dd); 2095 Py_CLEAR(dd->default_factory); 2096 PyDict_Type.tp_dealloc((PyObject *)dd); 2097} 2098 2099static PyObject * 2100defdict_repr(defdictobject *dd) 2101{ 2102 PyObject *baserepr; 2103 PyObject *defrepr; 2104 PyObject *result; 2105 baserepr = PyDict_Type.tp_repr((PyObject *)dd); 2106 if (baserepr == NULL) 2107 return NULL; 2108 if (dd->default_factory == NULL) 2109 defrepr = PyUnicode_FromString("None"); 2110 else 2111 { 2112 int status = Py_ReprEnter(dd->default_factory); 2113 if (status != 0) { 2114 if (status < 0) { 2115 Py_DECREF(baserepr); 2116 return NULL; 2117 } 2118 defrepr = PyUnicode_FromString("..."); 2119 } 2120 else 2121 defrepr = PyObject_Repr(dd->default_factory); 2122 Py_ReprLeave(dd->default_factory); 2123 } 2124 if (defrepr == NULL) { 2125 Py_DECREF(baserepr); 2126 return NULL; 2127 } 2128 result = PyUnicode_FromFormat("%s(%U, %U)", 2129 _PyType_Name(Py_TYPE(dd)), 2130 defrepr, baserepr); 2131 Py_DECREF(defrepr); 2132 Py_DECREF(baserepr); 2133 return result; 2134} 2135 2136static PyObject* 2137defdict_or(PyObject* left, PyObject* right) 2138{ 2139 PyObject *self, *other; 2140 if (PyObject_TypeCheck(left, &defdict_type)) { 2141 self = left; 2142 other = right; 2143 } 2144 else { 2145 self = right; 2146 other = left; 2147 } 2148 if (!PyDict_Check(other)) { 2149 Py_RETURN_NOTIMPLEMENTED; 2150 } 2151 // Like copy(), this calls the object's class. 2152 // Override __or__/__ror__ for subclasses with different constructors. 2153 PyObject *new = new_defdict((defdictobject*)self, left); 2154 if (!new) { 2155 return NULL; 2156 } 2157 if (PyDict_Update(new, right)) { 2158 Py_DECREF(new); 2159 return NULL; 2160 } 2161 return new; 2162} 2163 2164static PyNumberMethods defdict_as_number = { 2165 .nb_or = defdict_or, 2166}; 2167 2168static int 2169defdict_traverse(PyObject *self, visitproc visit, void *arg) 2170{ 2171 Py_VISIT(((defdictobject *)self)->default_factory); 2172 return PyDict_Type.tp_traverse(self, visit, arg); 2173} 2174 2175static int 2176defdict_tp_clear(defdictobject *dd) 2177{ 2178 Py_CLEAR(dd->default_factory); 2179 return PyDict_Type.tp_clear((PyObject *)dd); 2180} 2181 2182static int 2183defdict_init(PyObject *self, PyObject *args, PyObject *kwds) 2184{ 2185 defdictobject *dd = (defdictobject *)self; 2186 PyObject *olddefault = dd->default_factory; 2187 PyObject *newdefault = NULL; 2188 PyObject *newargs; 2189 int result; 2190 if (args == NULL || !PyTuple_Check(args)) 2191 newargs = PyTuple_New(0); 2192 else { 2193 Py_ssize_t n = PyTuple_GET_SIZE(args); 2194 if (n > 0) { 2195 newdefault = PyTuple_GET_ITEM(args, 0); 2196 if (!PyCallable_Check(newdefault) && newdefault != Py_None) { 2197 PyErr_SetString(PyExc_TypeError, 2198 "first argument must be callable or None"); 2199 return -1; 2200 } 2201 } 2202 newargs = PySequence_GetSlice(args, 1, n); 2203 } 2204 if (newargs == NULL) 2205 return -1; 2206 Py_XINCREF(newdefault); 2207 dd->default_factory = newdefault; 2208 result = PyDict_Type.tp_init(self, newargs, kwds); 2209 Py_DECREF(newargs); 2210 Py_XDECREF(olddefault); 2211 return result; 2212} 2213 2214PyDoc_STRVAR(defdict_doc, 2215"defaultdict(default_factory=None, /, [...]) --> dict with default factory\n\ 2216\n\ 2217The default factory is called without arguments to produce\n\ 2218a new value when a key is not present, in __getitem__ only.\n\ 2219A defaultdict compares equal to a dict with the same items.\n\ 2220All remaining arguments are treated the same as if they were\n\ 2221passed to the dict constructor, including keyword arguments.\n\ 2222"); 2223 2224/* See comment in xxsubtype.c */ 2225#define DEFERRED_ADDRESS(ADDR) 0 2226 2227static 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 2280Count elements in the iterable, updating the mapping 2281[clinic start generated code]*/ 2282 2283static PyObject * 2284_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 PyObject *newval = NULL; 2290 PyObject *key = NULL; 2291 PyObject *bound_get = NULL; 2292 PyObject *mapping_get; 2293 PyObject *dict_get; 2294 PyObject *mapping_setitem; 2295 PyObject *dict_setitem; 2296 PyObject *one = _PyLong_GetOne(); // borrowed reference 2297 2298 it = PyObject_GetIter(iterable); 2299 if (it == NULL) 2300 return NULL; 2301 2302 /* Only take the fast path when get() and __setitem__() 2303 * have not been overridden. 2304 */ 2305 mapping_get = _PyType_Lookup(Py_TYPE(mapping), &_Py_ID(get)); 2306 dict_get = _PyType_Lookup(&PyDict_Type, &_Py_ID(get)); 2307 mapping_setitem = _PyType_Lookup(Py_TYPE(mapping), &_Py_ID(__setitem__)); 2308 dict_setitem = _PyType_Lookup(&PyDict_Type, &_Py_ID(__setitem__)); 2309 2310 if (mapping_get != NULL && mapping_get == dict_get && 2311 mapping_setitem != NULL && mapping_setitem == dict_setitem && 2312 PyDict_Check(mapping)) 2313 { 2314 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 key = PyIter_Next(it); 2328 if (key == NULL) 2329 break; 2330 2331 if (!PyUnicode_CheckExact(key) || 2332 (hash = _PyASCIIObject_CAST(key)->hash) == -1) 2333 { 2334 hash = PyObject_Hash(key); 2335 if (hash == -1) 2336 goto done; 2337 } 2338 2339 oldval = _PyDict_GetItem_KnownHash(mapping, key, hash); 2340 if (oldval == NULL) { 2341 if (PyErr_Occurred()) 2342 goto done; 2343 if (_PyDict_SetItem_KnownHash(mapping, key, one, hash) < 0) 2344 goto done; 2345 } else { 2346 newval = PyNumber_Add(oldval, one); 2347 if (newval == NULL) 2348 goto done; 2349 if (_PyDict_SetItem_KnownHash(mapping, key, newval, hash) < 0) 2350 goto done; 2351 Py_CLEAR(newval); 2352 } 2353 Py_DECREF(key); 2354 } 2355 } 2356 else { 2357 bound_get = PyObject_GetAttr(mapping, &_Py_ID(get)); 2358 if (bound_get == NULL) 2359 goto done; 2360 2361 PyObject *zero = _PyLong_GetZero(); // borrowed reference 2362 while (1) { 2363 key = PyIter_Next(it); 2364 if (key == NULL) 2365 break; 2366 oldval = PyObject_CallFunctionObjArgs(bound_get, key, zero, NULL); 2367 if (oldval == NULL) 2368 break; 2369 newval = PyNumber_Add(oldval, one); 2370 Py_DECREF(oldval); 2371 if (newval == NULL) 2372 break; 2373 if (PyObject_SetItem(mapping, key, newval) < 0) 2374 break; 2375 Py_CLEAR(newval); 2376 Py_DECREF(key); 2377 } 2378 } 2379 2380done: 2381 Py_DECREF(it); 2382 Py_XDECREF(key); 2383 Py_XDECREF(newval); 2384 Py_XDECREF(bound_get); 2385 if (PyErr_Occurred()) 2386 return NULL; 2387 Py_RETURN_NONE; 2388} 2389 2390/* Helper function for namedtuple() ************************************/ 2391 2392typedef 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 2407static PyObject * 2408tuplegetter_new_impl(PyTypeObject *type, Py_ssize_t index, PyObject *doc) 2409/*[clinic end generated code: output=014be444ad80263f input=87c576a5bdbc0bbb]*/ 2410{ 2411 _tuplegetterobject* self; 2412 self = (_tuplegetterobject *)type->tp_alloc(type, 0); 2413 if (self == NULL) { 2414 return NULL; 2415 } 2416 self->index = index; 2417 Py_INCREF(doc); 2418 self->doc = doc; 2419 return (PyObject *)self; 2420} 2421 2422static PyObject * 2423tuplegetter_descr_get(PyObject *self, PyObject *obj, PyObject *type) 2424{ 2425 Py_ssize_t index = ((_tuplegetterobject*)self)->index; 2426 PyObject *result; 2427 2428 if (obj == NULL) { 2429 Py_INCREF(self); 2430 return self; 2431 } 2432 if (!PyTuple_Check(obj)) { 2433 if (obj == Py_None) { 2434 Py_INCREF(self); 2435 return self; 2436 } 2437 PyErr_Format(PyExc_TypeError, 2438 "descriptor for index '%zd' for tuple subclasses " 2439 "doesn't apply to '%s' object", 2440 index, 2441 Py_TYPE(obj)->tp_name); 2442 return NULL; 2443 } 2444 2445 if (!valid_index(index, PyTuple_GET_SIZE(obj))) { 2446 PyErr_SetString(PyExc_IndexError, "tuple index out of range"); 2447 return NULL; 2448 } 2449 2450 result = PyTuple_GET_ITEM(obj, index); 2451 Py_INCREF(result); 2452 return result; 2453} 2454 2455static int 2456tuplegetter_descr_set(PyObject *self, PyObject *obj, PyObject *value) 2457{ 2458 if (value == NULL) { 2459 PyErr_SetString(PyExc_AttributeError, "can't delete attribute"); 2460 } else { 2461 PyErr_SetString(PyExc_AttributeError, "can't set attribute"); 2462 } 2463 return -1; 2464} 2465 2466static int 2467tuplegetter_traverse(PyObject *self, visitproc visit, void *arg) 2468{ 2469 _tuplegetterobject *tuplegetter = (_tuplegetterobject *)self; 2470 Py_VISIT(tuplegetter->doc); 2471 return 0; 2472} 2473 2474static int 2475tuplegetter_clear(PyObject *self) 2476{ 2477 _tuplegetterobject *tuplegetter = (_tuplegetterobject *)self; 2478 Py_CLEAR(tuplegetter->doc); 2479 return 0; 2480} 2481 2482static void 2483tuplegetter_dealloc(_tuplegetterobject *self) 2484{ 2485 PyObject_GC_UnTrack(self); 2486 tuplegetter_clear((PyObject*)self); 2487 Py_TYPE(self)->tp_free((PyObject*)self); 2488} 2489 2490static PyObject* 2491tuplegetter_reduce(_tuplegetterobject *self, PyObject *Py_UNUSED(ignored)) 2492{ 2493 return Py_BuildValue("(O(nO))", (PyObject*) Py_TYPE(self), self->index, self->doc); 2494} 2495 2496static PyObject* 2497tuplegetter_repr(_tuplegetterobject *self) 2498{ 2499 return PyUnicode_FromFormat("%s(%zd, %R)", 2500 _PyType_Name(Py_TYPE(self)), 2501 self->index, self->doc); 2502} 2503 2504 2505static PyMemberDef tuplegetter_members[] = { 2506 {"__doc__", T_OBJECT, offsetof(_tuplegetterobject, doc), 0}, 2507 {0} 2508}; 2509 2510static PyMethodDef tuplegetter_methods[] = { 2511 {"__reduce__", (PyCFunction)tuplegetter_reduce, METH_NOARGS, NULL}, 2512 {NULL}, 2513}; 2514 2515static 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 2561PyDoc_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 2567static struct PyMethodDef collections_methods[] = { 2568 _COLLECTIONS__COUNT_ELEMENTS_METHODDEF 2569 {NULL, NULL} /* sentinel */ 2570}; 2571 2572static int 2573collections_exec(PyObject *module) { 2574 PyTypeObject *typelist[] = { 2575 &deque_type, 2576 &defdict_type, 2577 &PyODict_Type, 2578 &dequeiter_type, 2579 &dequereviter_type, 2580 &tuplegetter_type 2581 }; 2582 2583 defdict_type.tp_base = &PyDict_Type; 2584 2585 for (size_t i = 0; i < Py_ARRAY_LENGTH(typelist); i++) { 2586 if (PyModule_AddType(module, typelist[i]) < 0) { 2587 return -1; 2588 } 2589 } 2590 2591 return 0; 2592} 2593 2594static struct PyModuleDef_Slot collections_slots[] = { 2595 {Py_mod_exec, collections_exec}, 2596 {0, NULL} 2597}; 2598 2599static 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 2611PyMODINIT_FUNC 2612PyInit__collections(void) 2613{ 2614 return PyModuleDef_Init(&_collectionsmodule); 2615} 2616