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