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