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