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