Python-2.7.3/Modules/_collectionsmodule.c

Location Tool Test ID Function Issue
/builddir/build/BUILD/Python-2.7.3/Modules/_collectionsmodule.c:707:9 gcc unused-but-set-variable deque_clearmethod variable 'rv' set but not used
/builddir/build/BUILD/Python-2.7.3/Modules/_collectionsmodule.c:709:5 clang-analyzer Value stored to 'rv' is never read
   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@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;
variable 'rv' set but not used
(emitted by gcc)
708 709 rv = deque_clear(deque);
Value stored to 'rv' is never read
(emitted by clang-analyzer)

TODO: a detailed trace is available in the data model (not yet rendered in this report)

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 Py_DECREF(baserepr); 1480 return NULL; 1481 } 1482 defrepr = PyString_FromString("..."); 1483 } 1484 else 1485 defrepr = PyObject_Repr(dd->default_factory); 1486 Py_ReprLeave(dd->default_factory); 1487 } 1488 if (defrepr == NULL) { 1489 Py_DECREF(baserepr); 1490 return NULL; 1491 } 1492 result = PyString_FromFormat("defaultdict(%s, %s)", 1493 PyString_AS_STRING(defrepr), 1494 PyString_AS_STRING(baserepr)); 1495 Py_DECREF(defrepr); 1496 Py_DECREF(baserepr); 1497 return result; 1498 } 1499 1500 static int 1501 defdict_traverse(PyObject *self, visitproc visit, void *arg) 1502 { 1503 Py_VISIT(((defdictobject *)self)->default_factory); 1504 return PyDict_Type.tp_traverse(self, visit, arg); 1505 } 1506 1507 static int 1508 defdict_tp_clear(defdictobject *dd) 1509 { 1510 Py_CLEAR(dd->default_factory); 1511 return PyDict_Type.tp_clear((PyObject *)dd); 1512 } 1513 1514 static int 1515 defdict_init(PyObject *self, PyObject *args, PyObject *kwds) 1516 { 1517 defdictobject *dd = (defdictobject *)self; 1518 PyObject *olddefault = dd->default_factory; 1519 PyObject *newdefault = NULL; 1520 PyObject *newargs; 1521 int result; 1522 if (args == NULL || !PyTuple_Check(args)) 1523 newargs = PyTuple_New(0); 1524 else { 1525 Py_ssize_t n = PyTuple_GET_SIZE(args); 1526 if (n > 0) { 1527 newdefault = PyTuple_GET_ITEM(args, 0); 1528 if (!PyCallable_Check(newdefault) && newdefault != Py_None) { 1529 PyErr_SetString(PyExc_TypeError, 1530 "first argument must be callable"); 1531 return -1; 1532 } 1533 } 1534 newargs = PySequence_GetSlice(args, 1, n); 1535 } 1536 if (newargs == NULL) 1537 return -1; 1538 Py_XINCREF(newdefault); 1539 dd->default_factory = newdefault; 1540 result = PyDict_Type.tp_init(self, newargs, kwds); 1541 Py_DECREF(newargs); 1542 Py_XDECREF(olddefault); 1543 return result; 1544 } 1545 1546 PyDoc_STRVAR(defdict_doc, 1547 "defaultdict(default_factory) --> dict with default factory\n\ 1548 \n\ 1549 The default factory is called without arguments to produce\n\ 1550 a new value when a key is not present, in __getitem__ only.\n\ 1551 A defaultdict compares equal to a dict with the same items.\n\ 1552 "); 1553 1554 /* See comment in xxsubtype.c */ 1555 #define DEFERRED_ADDRESS(ADDR) 0 1556 1557 static PyTypeObject defdict_type = { 1558 PyVarObject_HEAD_INIT(DEFERRED_ADDRESS(&PyType_Type), 0) 1559 "collections.defaultdict", /* tp_name */ 1560 sizeof(defdictobject), /* tp_basicsize */ 1561 0, /* tp_itemsize */ 1562 /* methods */ 1563 (destructor)defdict_dealloc, /* tp_dealloc */ 1564 (printfunc)defdict_print, /* tp_print */ 1565 0, /* tp_getattr */ 1566 0, /* tp_setattr */ 1567 0, /* tp_compare */ 1568 (reprfunc)defdict_repr, /* tp_repr */ 1569 0, /* tp_as_number */ 1570 0, /* tp_as_sequence */ 1571 0, /* tp_as_mapping */ 1572 0, /* tp_hash */ 1573 0, /* tp_call */ 1574 0, /* tp_str */ 1575 PyObject_GenericGetAttr, /* tp_getattro */ 1576 0, /* tp_setattro */ 1577 0, /* tp_as_buffer */ 1578 Py_TPFLAGS_DEFAULT | Py_TPFLAGS_BASETYPE | Py_TPFLAGS_HAVE_GC | 1579 Py_TPFLAGS_HAVE_WEAKREFS, /* tp_flags */ 1580 defdict_doc, /* tp_doc */ 1581 defdict_traverse, /* tp_traverse */ 1582 (inquiry)defdict_tp_clear, /* tp_clear */ 1583 0, /* tp_richcompare */ 1584 0, /* tp_weaklistoffset*/ 1585 0, /* tp_iter */ 1586 0, /* tp_iternext */ 1587 defdict_methods, /* tp_methods */ 1588 defdict_members, /* tp_members */ 1589 0, /* tp_getset */ 1590 DEFERRED_ADDRESS(&PyDict_Type), /* tp_base */ 1591 0, /* tp_dict */ 1592 0, /* tp_descr_get */ 1593 0, /* tp_descr_set */ 1594 0, /* tp_dictoffset */ 1595 defdict_init, /* tp_init */ 1596 PyType_GenericAlloc, /* tp_alloc */ 1597 0, /* tp_new */ 1598 PyObject_GC_Del, /* tp_free */ 1599 }; 1600 1601 /* module level code ********************************************************/ 1602 1603 PyDoc_STRVAR(module_doc, 1604 "High performance data structures.\n\ 1605 - deque: ordered collection accessible from endpoints only\n\ 1606 - defaultdict: dict subclass with a default value factory\n\ 1607 "); 1608 1609 PyMODINIT_FUNC 1610 init_collections(void) 1611 { 1612 PyObject *m; 1613 1614 m = Py_InitModule3("_collections", NULL, module_doc); 1615 if (m == NULL) 1616 return; 1617 1618 if (PyType_Ready(&deque_type) < 0) 1619 return; 1620 Py_INCREF(&deque_type); 1621 PyModule_AddObject(m, "deque", (PyObject *)&deque_type); 1622 1623 defdict_type.tp_base = &PyDict_Type; 1624 if (PyType_Ready(&defdict_type) < 0) 1625 return; 1626 Py_INCREF(&defdict_type); 1627 PyModule_AddObject(m, "defaultdict", (PyObject *)&defdict_type); 1628 1629 if (PyType_Ready(&dequeiter_type) < 0) 1630 return; 1631 1632 if (PyType_Ready(&dequereviter_type) < 0) 1633 return; 1634 1635 return; 1636 }