1 /* List object implementation */ 2 3 #include "Python.h" 4 5 #ifdef STDC_HEADERS 6 #include <stddef.h> 7 #else 8 #include <sys/types.h> /* For size_t */ 9 #endif 10 11 /* Ensure ob_item has room for at least newsize elements, and set 12 * ob_size to newsize. If newsize > ob_size on entry, the content 13 * of the new slots at exit is undefined heap trash; it's the caller's 14 * responsibility to overwrite them with sane values. 15 * The number of allocated elements may grow, shrink, or stay the same. 16 * Failure is impossible if newsize <= self.allocated on entry, although 17 * that partly relies on an assumption that the system realloc() never 18 * fails when passed a number of bytes <= the number of bytes last 19 * allocated (the C standard doesn't guarantee this, but it's hard to 20 * imagine a realloc implementation where it wouldn't be true). 21 * Note that self->ob_item may change, and even if newsize is less 22 * than ob_size on entry. 23 */ 24 static int 25 list_resize(PyListObject *self, Py_ssize_t newsize) 26 { 27 PyObject **items; 28 size_t new_allocated; 29 Py_ssize_t allocated = self->allocated; 30 31 /* Bypass realloc() when a previous overallocation is large enough 32 to accommodate the newsize. If the newsize falls lower than half 33 the allocated size, then proceed with the realloc() to shrink the list. 34 */ 35 if (allocated >= newsize && newsize >= (allocated >> 1)) { 36 assert(self->ob_item != NULL || newsize == 0); 37 Py_SIZE(self) = newsize; 38 return 0; 39 } 40 41 /* This over-allocates proportional to the list size, making room 42 * for additional growth. The over-allocation is mild, but is 43 * enough to give linear-time amortized behavior over a long 44 * sequence of appends() in the presence of a poorly-performing 45 * system realloc(). 46 * The growth pattern is: 0, 4, 8, 16, 25, 35, 46, 58, 72, 88, ... 47 */ 48 new_allocated = (newsize >> 3) + (newsize < 9 ? 3 : 6); 49 50 /* check for integer overflow */ 51 if (new_allocated > PY_SIZE_MAX - newsize) { 52 PyErr_NoMemory(); 53 return -1; 54 } else { 55 new_allocated += newsize; 56 } 57 58 if (newsize == 0) 59 new_allocated = 0; 60 items = self->ob_item; 61 if (new_allocated <= (PY_SIZE_MAX / sizeof(PyObject *))) 62 PyMem_RESIZE(items, PyObject *, new_allocated); 63 else 64 items = NULL; 65 if (items == NULL) { 66 PyErr_NoMemory(); 67 return -1; 68 } 69 self->ob_item = items; 70 Py_SIZE(self) = newsize; 71 self->allocated = new_allocated; 72 return 0; 73 } 74 75 /* Debug statistic to compare allocations with reuse through the free list */ 76 #undef SHOW_ALLOC_COUNT 77 #ifdef SHOW_ALLOC_COUNT 78 static size_t count_alloc = 0; 79 static size_t count_reuse = 0; 80 81 static void 82 show_alloc(void) 83 { 84 fprintf(stderr, "List allocations: %" PY_FORMAT_SIZE_T "d\n", 85 count_alloc); 86 fprintf(stderr, "List reuse through freelist: %" PY_FORMAT_SIZE_T 87 "d\n", count_reuse); 88 fprintf(stderr, "%.2f%% reuse rate\n\n", 89 (100.0*count_reuse/(count_alloc+count_reuse))); 90 } 91 #endif 92 93 /* Empty list reuse scheme to save calls to malloc and free */ 94 #ifndef PyList_MAXFREELIST 95 #define PyList_MAXFREELIST 80 96 #endif 97 static PyListObject *free_list[PyList_MAXFREELIST]; 98 static int numfree = 0; 99 100 void 101 PyList_Fini(void) 102 { 103 PyListObject *op; 104 105 while (numfree) { 106 op = free_list[--numfree]; 107 assert(PyList_CheckExact(op)); 108 PyObject_GC_Del(op); 109 } 110 } 111 112 PyObject * 113 PyList_New(Py_ssize_t size) 114 { 115 PyListObject *op; 116 size_t nbytes; 117 #ifdef SHOW_ALLOC_COUNT 118 static int initialized = 0; 119 if (!initialized) { 120 Py_AtExit(show_alloc); 121 initialized = 1; 122 } 123 #endif 124 125 if (size < 0) { 126 PyErr_BadInternalCall(); 127 return NULL; 128 } 129 /* Check for overflow without an actual overflow, 130 * which can cause compiler to optimise out */ 131 if ((size_t)size > PY_SIZE_MAX / sizeof(PyObject *)) 132 return PyErr_NoMemory(); 133 nbytes = size * sizeof(PyObject *); 134 if (numfree) { 135 numfree--; 136 op = free_list[numfree]; 137 _Py_NewReference((PyObject *)op); 138 #ifdef SHOW_ALLOC_COUNT 139 count_reuse++; 140 #endif 141 } else { 142 op = PyObject_GC_New(PyListObject, &PyList_Type); 143 if (op == NULL) 144 return NULL; 145 #ifdef SHOW_ALLOC_COUNT 146 count_alloc++; 147 #endif 148 } 149 if (size <= 0) 150 op->ob_item = NULL; 151 else { 152 op->ob_item = (PyObject **) PyMem_MALLOC(nbytes); 153 if (op->ob_item == NULL) { 154 Py_DECREF(op); 155 return PyErr_NoMemory(); 156 } 157 memset(op->ob_item, 0, nbytes); 158 } 159 Py_SIZE(op) = size; 160 op->allocated = size; 161 _PyObject_GC_TRACK(op); 162 return (PyObject *) op; 163 } 164 165 Py_ssize_t 166 PyList_Size(PyObject *op) 167 { 168 if (!PyList_Check(op)) { 169 PyErr_BadInternalCall(); 170 return -1; 171 } 172 else 173 return Py_SIZE(op); 174 } 175 176 static PyObject *indexerr = NULL; 177 178 PyObject * 179 PyList_GetItem(PyObject *op, Py_ssize_t i) 180 { 181 if (!PyList_Check(op)) { 182 PyErr_BadInternalCall(); 183 return NULL; 184 } 185 if (i < 0 || i >= Py_SIZE(op)) { 186 if (indexerr == NULL) { 187 indexerr = PyString_FromString( 188 "list index out of range"); 189 if (indexerr == NULL) 190 return NULL; 191 } 192 PyErr_SetObject(PyExc_IndexError, indexerr); 193 return NULL; 194 } 195 return ((PyListObject *)op) -> ob_item[i]; 196 } 197 198 int 199 PyList_SetItem(register PyObject *op, register Py_ssize_t i, 200 register PyObject *newitem) 201 { 202 register PyObject *olditem; 203 register PyObject **p; 204 if (!PyList_Check(op)) { 205 Py_XDECREF(newitem); 206 PyErr_BadInternalCall(); 207 return -1; 208 } 209 if (i < 0 || i >= Py_SIZE(op)) { 210 Py_XDECREF(newitem); 211 PyErr_SetString(PyExc_IndexError, 212 "list assignment index out of range"); 213 return -1; 214 } 215 p = ((PyListObject *)op) -> ob_item + i; 216 olditem = *p; 217 *p = newitem; 218 Py_XDECREF(olditem); 219 return 0; 220 } 221 222 static int 223 ins1(PyListObject *self, Py_ssize_t where, PyObject *v) 224 { 225 Py_ssize_t i, n = Py_SIZE(self); 226 PyObject **items; 227 if (v == NULL) { 228 PyErr_BadInternalCall(); 229 return -1; 230 } 231 if (n == PY_SSIZE_T_MAX) { 232 PyErr_SetString(PyExc_OverflowError, 233 "cannot add more objects to list"); 234 return -1; 235 } 236 237 if (list_resize(self, n+1) == -1) 238 return -1; 239 240 if (where < 0) { 241 where += n; 242 if (where < 0) 243 where = 0; 244 } 245 if (where > n) 246 where = n; 247 items = self->ob_item; 248 for (i = n; --i >= where; ) 249 items[i+1] = items[i]; 250 Py_INCREF(v); 251 items[where] = v; 252 return 0; 253 } 254 255 int 256 PyList_Insert(PyObject *op, Py_ssize_t where, PyObject *newitem) 257 { 258 if (!PyList_Check(op)) { 259 PyErr_BadInternalCall(); 260 return -1; 261 } 262 return ins1((PyListObject *)op, where, newitem); 263 } 264 265 static int 266 app1(PyListObject *self, PyObject *v) 267 { 268 Py_ssize_t n = PyList_GET_SIZE(self); 269 270 assert (v != NULL); 271 if (n == PY_SSIZE_T_MAX) { 272 PyErr_SetString(PyExc_OverflowError, 273 "cannot add more objects to list"); 274 return -1; 275 } 276 277 if (list_resize(self, n+1) == -1) 278 return -1; 279 280 Py_INCREF(v); 281 PyList_SET_ITEM(self, n, v); 282 return 0; 283 } 284 285 int 286 PyList_Append(PyObject *op, PyObject *newitem) 287 { 288 if (PyList_Check(op) && (newitem != NULL)) 289 return app1((PyListObject *)op, newitem); 290 PyErr_BadInternalCall(); 291 return -1; 292 } 293 294 /* Methods */ 295 296 static void 297 list_dealloc(PyListObject *op) 298 { 299 Py_ssize_t i; 300 PyObject_GC_UnTrack(op); 301 Py_TRASHCAN_SAFE_BEGIN(op) 302 if (op->ob_item != NULL) { 303 /* Do it backwards, for Christian Tismer. 304 There's a simple test case where somehow this reduces 305 thrashing when a *very* large list is created and 306 immediately deleted. */ 307 i = Py_SIZE(op); 308 while (--i >= 0) { 309 Py_XDECREF(op->ob_item[i]); 310 } 311 PyMem_FREE(op->ob_item); 312 } 313 if (numfree < PyList_MAXFREELIST && PyList_CheckExact(op)) 314 free_list[numfree++] = op; 315 else 316 Py_TYPE(op)->tp_free((PyObject *)op); 317 Py_TRASHCAN_SAFE_END(op) 318 } 319 320 static int 321 list_print(PyListObject *op, FILE *fp, int flags) 322 { 323 int rc; 324 Py_ssize_t i; 325 PyObject *item; 326 327 rc = Py_ReprEnter((PyObject*)op); 328 if (rc != 0) { 329 if (rc < 0) 330 return rc; 331 Py_BEGIN_ALLOW_THREADS 332 fprintf(fp, "[...]"); 333 Py_END_ALLOW_THREADS 334 return 0; 335 } 336 Py_BEGIN_ALLOW_THREADS 337 fprintf(fp, "["); 338 Py_END_ALLOW_THREADS 339 for (i = 0; i < Py_SIZE(op); i++) { 340 item = op->ob_item[i]; 341 Py_INCREF(item); 342 if (i > 0) { 343 Py_BEGIN_ALLOW_THREADS 344 fprintf(fp, ", "); 345 Py_END_ALLOW_THREADS 346 } 347 if (PyObject_Print(item, fp, 0) != 0) { 348 Py_DECREF(item); 349 Py_ReprLeave((PyObject *)op); 350 return -1; 351 } 352 Py_DECREF(item); 353 } 354 Py_BEGIN_ALLOW_THREADS 355 fprintf(fp, "]"); 356 Py_END_ALLOW_THREADS 357 Py_ReprLeave((PyObject *)op); 358 return 0; 359 } 360 361 static PyObject * 362 list_repr(PyListObject *v) 363 { 364 Py_ssize_t i; 365 PyObject *s, *temp; 366 PyObject *pieces = NULL, *result = NULL; 367 368 i = Py_ReprEnter((PyObject*)v); 369 if (i != 0) { 370 return i > 0 ? PyString_FromString("[...]") : NULL; 371 } 372 373 if (Py_SIZE(v) == 0) { 374 result = PyString_FromString("[]"); 375 goto Done; 376 } 377 378 pieces = PyList_New(0); 379 if (pieces == NULL) 380 goto Done; 381 382 /* Do repr() on each element. Note that this may mutate the list, 383 so must refetch the list size on each iteration. */ 384 for (i = 0; i < Py_SIZE(v); ++i) { 385 int status; 386 if (Py_EnterRecursiveCall(" while getting the repr of a list")) 387 goto Done; 388 s = PyObject_Repr(v->ob_item[i]); 389 Py_LeaveRecursiveCall(); 390 if (s == NULL) 391 goto Done; 392 status = PyList_Append(pieces, s); 393 Py_DECREF(s); /* append created a new ref */ 394 if (status < 0) 395 goto Done; 396 } 397 398 /* Add "[]" decorations to the first and last items. */ 399 assert(PyList_GET_SIZE(pieces) > 0); 400 s = PyString_FromString("["); 401 if (s == NULL) 402 goto Done; 403 temp = PyList_GET_ITEM(pieces, 0); 404 PyString_ConcatAndDel(&s, temp); 405 PyList_SET_ITEM(pieces, 0, s); 406 if (s == NULL) 407 goto Done; 408 409 s = PyString_FromString("]"); 410 if (s == NULL) 411 goto Done; 412 temp = PyList_GET_ITEM(pieces, PyList_GET_SIZE(pieces) - 1); 413 PyString_ConcatAndDel(&temp, s); 414 PyList_SET_ITEM(pieces, PyList_GET_SIZE(pieces) - 1, temp); 415 if (temp == NULL) 416 goto Done; 417 418 /* Paste them all together with ", " between. */ 419 s = PyString_FromString(", "); 420 if (s == NULL) 421 goto Done; 422 result = _PyString_Join(s, pieces); 423 Py_DECREF(s); 424 425 Done: 426 Py_XDECREF(pieces); 427 Py_ReprLeave((PyObject *)v); 428 return result; 429 } 430 431 static Py_ssize_t 432 list_length(PyListObject *a) 433 { 434 return Py_SIZE(a); 435 } 436 437 static int 438 list_contains(PyListObject *a, PyObject *el) 439 { 440 Py_ssize_t i; 441 int cmp; 442 443 for (i = 0, cmp = 0 ; cmp == 0 && i < Py_SIZE(a); ++i) 444 cmp = PyObject_RichCompareBool(el, PyList_GET_ITEM(a, i), 445 Py_EQ); 446 return cmp; 447 } 448 449 static PyObject * 450 list_item(PyListObject *a, Py_ssize_t i) 451 { 452 if (i < 0 || i >= Py_SIZE(a)) { 453 if (indexerr == NULL) { 454 indexerr = PyString_FromString( 455 "list index out of range"); 456 if (indexerr == NULL) 457 return NULL; 458 } 459 PyErr_SetObject(PyExc_IndexError, indexerr); 460 return NULL; 461 } 462 Py_INCREF(a->ob_item[i]); 463 return a->ob_item[i]; 464 } 465 466 static PyObject * 467 list_slice(PyListObject *a, Py_ssize_t ilow, Py_ssize_t ihigh) 468 { 469 PyListObject *np; 470 PyObject **src, **dest; 471 Py_ssize_t i, len; 472 if (ilow < 0) 473 ilow = 0; 474 else if (ilow > Py_SIZE(a)) 475 ilow = Py_SIZE(a); 476 if (ihigh < ilow) 477 ihigh = ilow; 478 else if (ihigh > Py_SIZE(a)) 479 ihigh = Py_SIZE(a); 480 len = ihigh - ilow; 481 np = (PyListObject *) PyList_New(len); 482 if (np == NULL) 483 return NULL; 484 485 src = a->ob_item + ilow; 486 dest = np->ob_item; 487 for (i = 0; i < len; i++) { 488 PyObject *v = src[i]; 489 Py_INCREF(v); 490 dest[i] = v; 491 } 492 return (PyObject *)np; 493 } 494 495 PyObject * 496 PyList_GetSlice(PyObject *a, Py_ssize_t ilow, Py_ssize_t ihigh) 497 { 498 if (!PyList_Check(a)) { 499 PyErr_BadInternalCall(); 500 return NULL; 501 } 502 return list_slice((PyListObject *)a, ilow, ihigh); 503 } 504 505 static PyObject * 506 list_concat(PyListObject *a, PyObject *bb) 507 { 508 Py_ssize_t size; 509 Py_ssize_t i; 510 PyObject **src, **dest; 511 PyListObject *np; 512 if (!PyList_Check(bb)) { 513 PyErr_Format(PyExc_TypeError, 514 "can only concatenate list (not \"%.200s\") to list", 515 bb->ob_type->tp_name); 516 return NULL; 517 } 518 #define b ((PyListObject *)bb) 519 size = Py_SIZE(a) + Py_SIZE(b); 520 if (size < 0) 521 return PyErr_NoMemory(); 522 np = (PyListObject *) PyList_New(size); 523 if (np == NULL) { 524 return NULL; 525 } 526 src = a->ob_item; 527 dest = np->ob_item; 528 for (i = 0; i < Py_SIZE(a); i++) { 529 PyObject *v = src[i]; 530 Py_INCREF(v); 531 dest[i] = v; 532 } 533 src = b->ob_item; 534 dest = np->ob_item + Py_SIZE(a); 535 for (i = 0; i < Py_SIZE(b); i++) { 536 PyObject *v = src[i]; 537 Py_INCREF(v); 538 dest[i] = v; 539 } 540 return (PyObject *)np; 541 #undef b 542 } 543 544 static PyObject * 545 list_repeat(PyListObject *a, Py_ssize_t n) 546 { 547 Py_ssize_t i, j; 548 Py_ssize_t size; 549 PyListObject *np; 550 PyObject **p, **items; 551 PyObject *elem; 552 if (n < 0) 553 n = 0; 554 if (n > 0 && Py_SIZE(a) > PY_SSIZE_T_MAX / n) 555 return PyErr_NoMemory(); 556 size = Py_SIZE(a) * n; 557 if (size == 0) 558 return PyList_New(0); 559 np = (PyListObject *) PyList_New(size); 560 if (np == NULL) 561 return NULL; 562 563 items = np->ob_item; 564 if (Py_SIZE(a) == 1) { 565 elem = a->ob_item[0]; 566 for (i = 0; i < n; i++) { 567 items[i] = elem; 568 Py_INCREF(elem); 569 } 570 return (PyObject *) np; 571 } 572 p = np->ob_item; 573 items = a->ob_item; 574 for (i = 0; i < n; i++) { 575 for (j = 0; j < Py_SIZE(a); j++) { 576 *p = items[j]; 577 Py_INCREF(*p); 578 p++; 579 } 580 } 581 return (PyObject *) np; 582 } 583 584 static int 585 list_clear(PyListObject *a) 586 { 587 Py_ssize_t i; 588 PyObject **item = a->ob_item; 589 if (item != NULL) { 590 /* Because XDECREF can recursively invoke operations on 591 this list, we make it empty first. */ 592 i = Py_SIZE(a); 593 Py_SIZE(a) = 0; 594 a->ob_item = NULL; 595 a->allocated = 0; 596 while (--i >= 0) { 597 Py_XDECREF(item[i]); 598 } 599 PyMem_FREE(item); 600 } 601 /* Never fails; the return value can be ignored. 602 Note that there is no guarantee that the list is actually empty 603 at this point, because XDECREF may have populated it again! */ 604 return 0; 605 } 606 607 /* a[ilow:ihigh] = v if v != NULL. 608 * del a[ilow:ihigh] if v == NULL. 609 * 610 * Special speed gimmick: when v is NULL and ihigh - ilow <= 8, it's 611 * guaranteed the call cannot fail. 612 */ 613 static int 614 list_ass_slice(PyListObject *a, Py_ssize_t ilow, Py_ssize_t ihigh, PyObject *v) 615 { 616 /* Because [X]DECREF can recursively invoke list operations on 617 this list, we must postpone all [X]DECREF activity until 618 after the list is back in its canonical shape. Therefore 619 we must allocate an additional array, 'recycle', into which 620 we temporarily copy the items that are deleted from the 621 list. :-( */ 622 PyObject *recycle_on_stack[8]; 623 PyObject **recycle = recycle_on_stack; /* will allocate more if needed */ 624 PyObject **item; 625 PyObject **vitem = NULL; 626 PyObject *v_as_SF = NULL; /* PySequence_Fast(v) */ 627 Py_ssize_t n; /* # of elements in replacement list */ 628 Py_ssize_t norig; /* # of elements in list getting replaced */ 629 Py_ssize_t d; /* Change in size */ 630 Py_ssize_t k; 631 size_t s; 632 int result = -1; /* guilty until proved innocent */ 633 #define b ((PyListObject *)v) 634 if (v == NULL) 635 n = 0; 636 else { 637 if (a == b) { 638 /* Special case "a[i:j] = a" -- copy b first */ 639 v = list_slice(b, 0, Py_SIZE(b)); 640 if (v == NULL) 641 return result; 642 result = list_ass_slice(a, ilow, ihigh, v); 643 Py_DECREF(v); 644 return result; 645 } 646 v_as_SF = PySequence_Fast(v, "can only assign an iterable"); 647 if(v_as_SF == NULL) 648 goto Error; 649 n = PySequence_Fast_GET_SIZE(v_as_SF); 650 vitem = PySequence_Fast_ITEMS(v_as_SF); 651 } 652 if (ilow < 0) 653 ilow = 0; 654 else if (ilow > Py_SIZE(a)) 655 ilow = Py_SIZE(a); 656 657 if (ihigh < ilow) 658 ihigh = ilow; 659 else if (ihigh > Py_SIZE(a)) 660 ihigh = Py_SIZE(a); 661 662 norig = ihigh - ilow; 663 assert(norig >= 0); 664 d = n - norig; 665 if (Py_SIZE(a) + d == 0) { 666 Py_XDECREF(v_as_SF); 667 return list_clear(a); 668 } 669 item = a->ob_item; 670 /* recycle the items that we are about to remove */ 671 s = norig * sizeof(PyObject *); 672 /* If norig == 0, item might be NULL, in which case we may not memcpy from it. */ 673 if (s) { 674 if (s > sizeof(recycle_on_stack)) { 675 recycle = (PyObject **)PyMem_MALLOC(s); 676 if (recycle == NULL) { 677 PyErr_NoMemory(); 678 goto Error; 679 } 680 } 681 memcpy(recycle, &item[ilow], s); 682 } 683 684 if (d < 0) { /* Delete -d items */ 685 memmove(&item[ihigh+d], &item[ihigh], 686 (Py_SIZE(a) - ihigh)*sizeof(PyObject *)); 687 list_resize(a, Py_SIZE(a) + d); 688 item = a->ob_item; 689 } 690 else if (d > 0) { /* Insert d items */ 691 k = Py_SIZE(a); 692 if (list_resize(a, k+d) < 0) 693 goto Error; 694 item = a->ob_item; 695 memmove(&item[ihigh+d], &item[ihigh], 696 (k - ihigh)*sizeof(PyObject *)); 697 } 698 for (k = 0; k < n; k++, ilow++) { 699 PyObject *w = vitem[k]; 700 Py_XINCREF(w); 701 item[ilow] = w; 702 } 703 for (k = norig - 1; k >= 0; --k) 704 Py_XDECREF(recycle[k]); 705 result = 0; 706 Error: 707 if (recycle != recycle_on_stack) 708 PyMem_FREE(recycle); 709 Py_XDECREF(v_as_SF); 710 return result; 711 #undef b 712 } 713 714 int 715 PyList_SetSlice(PyObject *a, Py_ssize_t ilow, Py_ssize_t ihigh, PyObject *v) 716 { 717 if (!PyList_Check(a)) { 718 PyErr_BadInternalCall(); 719 return -1; 720 } 721 return list_ass_slice((PyListObject *)a, ilow, ihigh, v); 722 } 723 724 static PyObject * 725 list_inplace_repeat(PyListObject *self, Py_ssize_t n) 726 { 727 PyObject **items; 728 Py_ssize_t size, i, j, p; 729 730 731 size = PyList_GET_SIZE(self); 732 if (size == 0 || n == 1) { 733 Py_INCREF(self); 734 return (PyObject *)self; 735 } 736 737 if (n < 1) { 738 (void)list_clear(self); 739 Py_INCREF(self); 740 return (PyObject *)self; 741 } 742 743 if (size > PY_SSIZE_T_MAX / n) { 744 return PyErr_NoMemory(); 745 } 746 747 if (list_resize(self, size*n) == -1) 748 return NULL; 749 750 p = size; 751 items = self->ob_item; 752 for (i = 1; i < n; i++) { /* Start counting at 1, not 0 */ 753 for (j = 0; j < size; j++) { 754 PyObject *o = items[j]; 755 Py_INCREF(o); 756 items[p++] = o; 757 } 758 } 759 Py_INCREF(self); 760 return (PyObject *)self; 761 } 762 763 static int 764 list_ass_item(PyListObject *a, Py_ssize_t i, PyObject *v) 765 { 766 PyObject *old_value; 767 if (i < 0 || i >= Py_SIZE(a)) { 768 PyErr_SetString(PyExc_IndexError, 769 "list assignment index out of range"); 770 return -1; 771 } 772 if (v == NULL) 773 return list_ass_slice(a, i, i+1, v); 774 Py_INCREF(v); 775 old_value = a->ob_item[i]; 776 a->ob_item[i] = v; 777 Py_DECREF(old_value); 778 return 0; 779 } 780 781 static PyObject * 782 listinsert(PyListObject *self, PyObject *args) 783 { 784 Py_ssize_t i; 785 PyObject *v; 786 if (!PyArg_ParseTuple(args, "nO:insert", &i, &v)) 787 return NULL; 788 if (ins1(self, i, v) == 0) 789 Py_RETURN_NONE; 790 return NULL; 791 } 792 793 static PyObject * 794 listappend(PyListObject *self, PyObject *v) 795 { 796 if (app1(self, v) == 0) 797 Py_RETURN_NONE; 798 return NULL; 799 } 800 801 static PyObject * 802 listextend(PyListObject *self, PyObject *b) 803 { 804 PyObject *it; /* iter(v) */ 805 Py_ssize_t m; /* size of self */ 806 Py_ssize_t n; /* guess for size of b */ 807 Py_ssize_t mn; /* m + n */ 808 Py_ssize_t i; 809 PyObject *(*iternext)(PyObject *); 810 811 /* Special cases: 812 1) lists and tuples which can use PySequence_Fast ops 813 2) extending self to self requires making a copy first 814 */ 815 if (PyList_CheckExact(b) || PyTuple_CheckExact(b) || (PyObject *)self == b) { 816 PyObject **src, **dest; 817 b = PySequence_Fast(b, "argument must be iterable"); 818 if (!b) 819 return NULL; 820 n = PySequence_Fast_GET_SIZE(b); 821 if (n == 0) { 822 /* short circuit when b is empty */ 823 Py_DECREF(b); 824 Py_RETURN_NONE; 825 } 826 m = Py_SIZE(self); 827 if (list_resize(self, m + n) == -1) { 828 Py_DECREF(b); 829 return NULL; 830 } 831 /* note that we may still have self == b here for the 832 * situation a.extend(a), but the following code works 833 * in that case too. Just make sure to resize self 834 * before calling PySequence_Fast_ITEMS. 835 */ 836 /* populate the end of self with b's items */ 837 src = PySequence_Fast_ITEMS(b); 838 dest = self->ob_item + m; 839 for (i = 0; i < n; i++) { 840 PyObject *o = src[i]; 841 Py_INCREF(o); 842 dest[i] = o; 843 } 844 Py_DECREF(b); 845 Py_RETURN_NONE; 846 } 847 848 it = PyObject_GetIter(b); 849 if (it == NULL) 850 return NULL; 851 iternext = *it->ob_type->tp_iternext; 852 853 /* Guess a result list size. */ 854 n = _PyObject_LengthHint(b, 8); 855 if (n == -1) { 856 Py_DECREF(it); 857 return NULL; 858 } 859 m = Py_SIZE(self); 860 mn = m + n; 861 if (mn >= m) { 862 /* Make room. */ 863 if (list_resize(self, mn) == -1) 864 goto error; 865 /* Make the list sane again. */ 866 Py_SIZE(self) = m; 867 } 868 /* Else m + n overflowed; on the chance that n lied, and there really 869 * is enough room, ignore it. If n was telling the truth, we'll 870 * eventually run out of memory during the loop. 871 */ 872 873 /* Run iterator to exhaustion. */ 874 for (;;) { 875 PyObject *item = iternext(it); 876 if (item == NULL) { 877 if (PyErr_Occurred()) { 878 if (PyErr_ExceptionMatches(PyExc_StopIteration)) 879 PyErr_Clear(); 880 else 881 goto error; 882 } 883 break; 884 } 885 if (Py_SIZE(self) < self->allocated) { 886 /* steals ref */ 887 PyList_SET_ITEM(self, Py_SIZE(self), item); 888 ++Py_SIZE(self); 889 } 890 else { 891 int status = app1(self, item); 892 Py_DECREF(item); /* append creates a new ref */ 893 if (status < 0) 894 goto error; 895 } 896 } 897 898 /* Cut back result list if initial guess was too large. */ 899 if (Py_SIZE(self) < self->allocated) 900 list_resize(self, Py_SIZE(self)); /* shrinking can't fail */ 901 902 Py_DECREF(it); 903 Py_RETURN_NONE; 904 905 error: 906 Py_DECREF(it); 907 return NULL; 908 } 909 910 PyObject * 911 _PyList_Extend(PyListObject *self, PyObject *b) 912 { 913 return listextend(self, b); 914 } 915 916 static PyObject * 917 list_inplace_concat(PyListObject *self, PyObject *other) 918 { 919 PyObject *result; 920 921 result = listextend(self, other); 922 if (result == NULL) 923 return result; 924 Py_DECREF(result); 925 Py_INCREF(self); 926 return (PyObject *)self; 927 } 928 929 static PyObject * 930 listpop(PyListObject *self, PyObject *args) 931 { 932 Py_ssize_t i = -1; 933 PyObject *v; 934 int status; 935 936 if (!PyArg_ParseTuple(args, "|n:pop", &i)) 937 return NULL; 938 939 if (Py_SIZE(self) == 0) { 940 /* Special-case most common failure cause */ 941 PyErr_SetString(PyExc_IndexError, "pop from empty list"); 942 return NULL; 943 } 944 if (i < 0) 945 i += Py_SIZE(self); 946 if (i < 0 || i >= Py_SIZE(self)) { 947 PyErr_SetString(PyExc_IndexError, "pop index out of range"); 948 return NULL; 949 } 950 v = self->ob_item[i]; 951 if (i == Py_SIZE(self) - 1) { 952 status = list_resize(self, Py_SIZE(self) - 1); 953 assert(status >= 0); 954 return v; /* and v now owns the reference the list had */ 955 } 956 Py_INCREF(v); 957 status = list_ass_slice(self, i, i+1, (PyObject *)NULL); 958 assert(status >= 0); 959 /* Use status, so that in a release build compilers don't 960 * complain about the unused name. 961 */ 962 (void) status; 963 964 return v; 965 } 966 967 /* Reverse a slice of a list in place, from lo up to (exclusive) hi. */ 968 static void 969 reverse_slice(PyObject **lo, PyObject **hi) 970 { 971 assert(lo && hi); 972 973 --hi; 974 while (lo < hi) { 975 PyObject *t = *lo; 976 *lo = *hi; 977 *hi = t; 978 ++lo; 979 --hi; 980 } 981 } 982 983 /* Lots of code for an adaptive, stable, natural mergesort. There are many 984 * pieces to this algorithm; read listsort.txt for overviews and details. 985 */ 986 987 /* Comparison function. Takes care of calling a user-supplied 988 * comparison function (any callable Python object), which must not be 989 * NULL (use the ISLT macro if you don't know, or call PyObject_RichCompareBool 990 * with Py_LT if you know it's NULL). 991 * Returns -1 on error, 1 if x < y, 0 if x >= y. 992 */ 993 static int 994 islt(PyObject *x, PyObject *y, PyObject *compare) 995 { 996 PyObject *res; 997 PyObject *args; 998 Py_ssize_t i; 999 1000 assert(compare != NULL); 1001 /* Call the user's comparison function and translate the 3-way 1002 * result into true or false (or error). 1003 */ 1004 args = PyTuple_New(2); 1005 if (args == NULL) 1006 return -1; 1007 Py_INCREF(x); 1008 Py_INCREF(y); 1009 PyTuple_SET_ITEM(args, 0, x); 1010 PyTuple_SET_ITEM(args, 1, y); 1011 res = PyObject_Call(compare, args, NULL); 1012 Py_DECREF(args); 1013 if (res == NULL) 1014 return -1; 1015 if (!PyInt_Check(res)) { 1016 PyErr_Format(PyExc_TypeError, 1017 "comparison function must return int, not %.200s", 1018 res->ob_type->tp_name); 1019 Py_DECREF(res); 1020 return -1; 1021 } 1022 i = PyInt_AsLong(res); 1023 Py_DECREF(res); 1024 return i < 0; 1025 } 1026 1027 /* If COMPARE is NULL, calls PyObject_RichCompareBool with Py_LT, else calls 1028 * islt. This avoids a layer of function call in the usual case, and 1029 * sorting does many comparisons. 1030 * Returns -1 on error, 1 if x < y, 0 if x >= y. 1031 */ 1032 #define ISLT(X, Y, COMPARE) ((COMPARE) == NULL ? \ 1033 PyObject_RichCompareBool(X, Y, Py_LT) : \ 1034 islt(X, Y, COMPARE)) 1035 1036 /* Compare X to Y via "<". Goto "fail" if the comparison raises an 1037 error. Else "k" is set to true iff X<Y, and an "if (k)" block is 1038 started. It makes more sense in context <wink>. X and Y are PyObject*s. 1039 */ 1040 #define IFLT(X, Y) if ((k = ISLT(X, Y, compare)) < 0) goto fail; \ 1041 if (k) 1042 1043 /* binarysort is the best method for sorting small arrays: it does 1044 few compares, but can do data movement quadratic in the number of 1045 elements. 1046 [lo, hi) is a contiguous slice of a list, and is sorted via 1047 binary insertion. This sort is stable. 1048 On entry, must have lo <= start <= hi, and that [lo, start) is already 1049 sorted (pass start == lo if you don't know!). 1050 If islt() complains return -1, else 0. 1051 Even in case of error, the output slice will be some permutation of 1052 the input (nothing is lost or duplicated). 1053 */ 1054 static int 1055 binarysort(PyObject **lo, PyObject **hi, PyObject **start, PyObject *compare) 1056 /* compare -- comparison function object, or NULL for default */ 1057 { 1058 register Py_ssize_t k; 1059 register PyObject **l, **p, **r; 1060 register PyObject *pivot; 1061 1062 assert(lo <= start && start <= hi); 1063 /* assert [lo, start) is sorted */ 1064 if (lo == start) 1065 ++start; 1066 for (; start < hi; ++start) { 1067 /* set l to where *start belongs */ 1068 l = lo; 1069 r = start; 1070 pivot = *r; 1071 /* Invariants: 1072 * pivot >= all in [lo, l). 1073 * pivot < all in [r, start). 1074 * The second is vacuously true at the start. 1075 */ 1076 assert(l < r); 1077 do { 1078 p = l + ((r - l) >> 1); 1079 IFLT(pivot, *p) 1080 r = p; 1081 else 1082 l = p+1; 1083 } while (l < r); 1084 assert(l == r); 1085 /* The invariants still hold, so pivot >= all in [lo, l) and 1086 pivot < all in [l, start), so pivot belongs at l. Note 1087 that if there are elements equal to pivot, l points to the 1088 first slot after them -- that's why this sort is stable. 1089 Slide over to make room. 1090 Caution: using memmove is much slower under MSVC 5; 1091 we're not usually moving many slots. */ 1092 for (p = start; p > l; --p) 1093 *p = *(p-1); 1094 *l = pivot; 1095 } 1096 return 0; 1097 1098 fail: 1099 return -1; 1100 } 1101 1102 /* 1103 Return the length of the run beginning at lo, in the slice [lo, hi). lo < hi 1104 is required on entry. "A run" is the longest ascending sequence, with 1105 1106 lo[0] <= lo[1] <= lo[2] <= ... 1107 1108 or the longest descending sequence, with 1109 1110 lo[0] > lo[1] > lo[2] > ... 1111 1112 Boolean *descending is set to 0 in the former case, or to 1 in the latter. 1113 For its intended use in a stable mergesort, the strictness of the defn of 1114 "descending" is needed so that the caller can safely reverse a descending 1115 sequence without violating stability (strict > ensures there are no equal 1116 elements to get out of order). 1117 1118 Returns -1 in case of error. 1119 */ 1120 static Py_ssize_t 1121 count_run(PyObject **lo, PyObject **hi, PyObject *compare, int *descending) 1122 { 1123 Py_ssize_t k; 1124 Py_ssize_t n; 1125 1126 assert(lo < hi); 1127 *descending = 0; 1128 ++lo; 1129 if (lo == hi) 1130 return 1; 1131 1132 n = 2; 1133 IFLT(*lo, *(lo-1)) { 1134 *descending = 1; 1135 for (lo = lo+1; lo < hi; ++lo, ++n) { 1136 IFLT(*lo, *(lo-1)) 1137 ; 1138 else 1139 break; 1140 } 1141 } 1142 else { 1143 for (lo = lo+1; lo < hi; ++lo, ++n) { 1144 IFLT(*lo, *(lo-1)) 1145 break; 1146 } 1147 } 1148 1149 return n; 1150 fail: 1151 return -1; 1152 } 1153 1154 /* 1155 Locate the proper position of key in a sorted vector; if the vector contains 1156 an element equal to key, return the position immediately to the left of 1157 the leftmost equal element. [gallop_right() does the same except returns 1158 the position to the right of the rightmost equal element (if any).] 1159 1160 "a" is a sorted vector with n elements, starting at a[0]. n must be > 0. 1161 1162 "hint" is an index at which to begin the search, 0 <= hint < n. The closer 1163 hint is to the final result, the faster this runs. 1164 1165 The return value is the int k in 0..n such that 1166 1167 a[k-1] < key <= a[k] 1168 1169 pretending that *(a-1) is minus infinity and a[n] is plus infinity. IOW, 1170 key belongs at index k; or, IOW, the first k elements of a should precede 1171 key, and the last n-k should follow key. 1172 1173 Returns -1 on error. See listsort.txt for info on the method. 1174 */ 1175 static Py_ssize_t 1176 gallop_left(PyObject *key, PyObject **a, Py_ssize_t n, Py_ssize_t hint, PyObject *compare) 1177 { 1178 Py_ssize_t ofs; 1179 Py_ssize_t lastofs; 1180 Py_ssize_t k; 1181 1182 assert(key && a && n > 0 && hint >= 0 && hint < n); 1183 1184 a += hint; 1185 lastofs = 0; 1186 ofs = 1; 1187 IFLT(*a, key) { 1188 /* a[hint] < key -- gallop right, until 1189 * a[hint + lastofs] < key <= a[hint + ofs] 1190 */ 1191 const Py_ssize_t maxofs = n - hint; /* &a[n-1] is highest */ 1192 while (ofs < maxofs) { 1193 IFLT(a[ofs], key) { 1194 lastofs = ofs; 1195 ofs = (ofs << 1) + 1; 1196 if (ofs <= 0) /* int overflow */ 1197 ofs = maxofs; 1198 } 1199 else /* key <= a[hint + ofs] */ 1200 break; 1201 } 1202 if (ofs > maxofs) 1203 ofs = maxofs; 1204 /* Translate back to offsets relative to &a[0]. */ 1205 lastofs += hint; 1206 ofs += hint; 1207 } 1208 else { 1209 /* key <= a[hint] -- gallop left, until 1210 * a[hint - ofs] < key <= a[hint - lastofs] 1211 */ 1212 const Py_ssize_t maxofs = hint + 1; /* &a[0] is lowest */ 1213 while (ofs < maxofs) { 1214 IFLT(*(a-ofs), key) 1215 break; 1216 /* key <= a[hint - ofs] */ 1217 lastofs = ofs; 1218 ofs = (ofs << 1) + 1; 1219 if (ofs <= 0) /* int overflow */ 1220 ofs = maxofs; 1221 } 1222 if (ofs > maxofs) 1223 ofs = maxofs; 1224 /* Translate back to positive offsets relative to &a[0]. */ 1225 k = lastofs; 1226 lastofs = hint - ofs; 1227 ofs = hint - k; 1228 } 1229 a -= hint; 1230 1231 assert(-1 <= lastofs && lastofs < ofs && ofs <= n); 1232 /* Now a[lastofs] < key <= a[ofs], so key belongs somewhere to the 1233 * right of lastofs but no farther right than ofs. Do a binary 1234 * search, with invariant a[lastofs-1] < key <= a[ofs]. 1235 */ 1236 ++lastofs; 1237 while (lastofs < ofs) { 1238 Py_ssize_t m = lastofs + ((ofs - lastofs) >> 1); 1239 1240 IFLT(a[m], key) 1241 lastofs = m+1; /* a[m] < key */ 1242 else 1243 ofs = m; /* key <= a[m] */ 1244 } 1245 assert(lastofs == ofs); /* so a[ofs-1] < key <= a[ofs] */ 1246 return ofs; 1247 1248 fail: 1249 return -1; 1250 } 1251 1252 /* 1253 Exactly like gallop_left(), except that if key already exists in a[0:n], 1254 finds the position immediately to the right of the rightmost equal value. 1255 1256 The return value is the int k in 0..n such that 1257 1258 a[k-1] <= key < a[k] 1259 1260 or -1 if error. 1261 1262 The code duplication is massive, but this is enough different given that 1263 we're sticking to "<" comparisons that it's much harder to follow if 1264 written as one routine with yet another "left or right?" flag. 1265 */ 1266 static Py_ssize_t 1267 gallop_right(PyObject *key, PyObject **a, Py_ssize_t n, Py_ssize_t hint, PyObject *compare) 1268 { 1269 Py_ssize_t ofs; 1270 Py_ssize_t lastofs; 1271 Py_ssize_t k; 1272 1273 assert(key && a && n > 0 && hint >= 0 && hint < n); 1274 1275 a += hint; 1276 lastofs = 0; 1277 ofs = 1; 1278 IFLT(key, *a) { 1279 /* key < a[hint] -- gallop left, until 1280 * a[hint - ofs] <= key < a[hint - lastofs] 1281 */ 1282 const Py_ssize_t maxofs = hint + 1; /* &a[0] is lowest */ 1283 while (ofs < maxofs) { 1284 IFLT(key, *(a-ofs)) { 1285 lastofs = ofs; 1286 ofs = (ofs << 1) + 1; 1287 if (ofs <= 0) /* int overflow */ 1288 ofs = maxofs; 1289 } 1290 else /* a[hint - ofs] <= key */ 1291 break; 1292 } 1293 if (ofs > maxofs) 1294 ofs = maxofs; 1295 /* Translate back to positive offsets relative to &a[0]. */ 1296 k = lastofs; 1297 lastofs = hint - ofs; 1298 ofs = hint - k; 1299 } 1300 else { 1301 /* a[hint] <= key -- gallop right, until 1302 * a[hint + lastofs] <= key < a[hint + ofs] 1303 */ 1304 const Py_ssize_t maxofs = n - hint; /* &a[n-1] is highest */ 1305 while (ofs < maxofs) { 1306 IFLT(key, a[ofs]) 1307 break; 1308 /* a[hint + ofs] <= key */ 1309 lastofs = ofs; 1310 ofs = (ofs << 1) + 1; 1311 if (ofs <= 0) /* int overflow */ 1312 ofs = maxofs; 1313 } 1314 if (ofs > maxofs) 1315 ofs = maxofs; 1316 /* Translate back to offsets relative to &a[0]. */ 1317 lastofs += hint; 1318 ofs += hint; 1319 } 1320 a -= hint; 1321 1322 assert(-1 <= lastofs && lastofs < ofs && ofs <= n); 1323 /* Now a[lastofs] <= key < a[ofs], so key belongs somewhere to the 1324 * right of lastofs but no farther right than ofs. Do a binary 1325 * search, with invariant a[lastofs-1] <= key < a[ofs]. 1326 */ 1327 ++lastofs; 1328 while (lastofs < ofs) { 1329 Py_ssize_t m = lastofs + ((ofs - lastofs) >> 1); 1330 1331 IFLT(key, a[m]) 1332 ofs = m; /* key < a[m] */ 1333 else 1334 lastofs = m+1; /* a[m] <= key */ 1335 } 1336 assert(lastofs == ofs); /* so a[ofs-1] <= key < a[ofs] */ 1337 return ofs; 1338 1339 fail: 1340 return -1; 1341 } 1342 1343 /* The maximum number of entries in a MergeState's pending-runs stack. 1344 * This is enough to sort arrays of size up to about 1345 * 32 * phi ** MAX_MERGE_PENDING 1346 * where phi ~= 1.618. 85 is ridiculouslylarge enough, good for an array 1347 * with 2**64 elements. 1348 */ 1349 #define MAX_MERGE_PENDING 85 1350 1351 /* When we get into galloping mode, we stay there until both runs win less 1352 * often than MIN_GALLOP consecutive times. See listsort.txt for more info. 1353 */ 1354 #define MIN_GALLOP 7 1355 1356 /* Avoid malloc for small temp arrays. */ 1357 #define MERGESTATE_TEMP_SIZE 256 1358 1359 /* One MergeState exists on the stack per invocation of mergesort. It's just 1360 * a convenient way to pass state around among the helper functions. 1361 */ 1362 struct s_slice { 1363 PyObject **base; 1364 Py_ssize_t len; 1365 }; 1366 1367 typedef struct s_MergeState { 1368 /* The user-supplied comparison function. or NULL if none given. */ 1369 PyObject *compare; 1370 1371 /* This controls when we get *into* galloping mode. It's initialized 1372 * to MIN_GALLOP. merge_lo and merge_hi tend to nudge it higher for 1373 * random data, and lower for highly structured data. 1374 */ 1375 Py_ssize_t min_gallop; 1376 1377 /* 'a' is temp storage to help with merges. It contains room for 1378 * alloced entries. 1379 */ 1380 PyObject **a; /* may point to temparray below */ 1381 Py_ssize_t alloced; 1382 1383 /* A stack of n pending runs yet to be merged. Run #i starts at 1384 * address base[i] and extends for len[i] elements. It's always 1385 * true (so long as the indices are in bounds) that 1386 * 1387 * pending[i].base + pending[i].len == pending[i+1].base 1388 * 1389 * so we could cut the storage for this, but it's a minor amount, 1390 * and keeping all the info explicit simplifies the code. 1391 */ 1392 int n; 1393 struct s_slice pending[MAX_MERGE_PENDING]; 1394 1395 /* 'a' points to this when possible, rather than muck with malloc. */ 1396 PyObject *temparray[MERGESTATE_TEMP_SIZE]; 1397 } MergeState; 1398 1399 /* Conceptually a MergeState's constructor. */ 1400 static void 1401 merge_init(MergeState *ms, PyObject *compare) 1402 { 1403 assert(ms != NULL); 1404 ms->compare = compare; 1405 ms->a = ms->temparray; 1406 ms->alloced = MERGESTATE_TEMP_SIZE; 1407 ms->n = 0; 1408 ms->min_gallop = MIN_GALLOP; 1409 } 1410 1411 /* Free all the temp memory owned by the MergeState. This must be called 1412 * when you're done with a MergeState, and may be called before then if 1413 * you want to free the temp memory early. 1414 */ 1415 static void 1416 merge_freemem(MergeState *ms) 1417 { 1418 assert(ms != NULL); 1419 if (ms->a != ms->temparray) 1420 PyMem_Free(ms->a); 1421 ms->a = ms->temparray; 1422 ms->alloced = MERGESTATE_TEMP_SIZE; 1423 } 1424 1425 /* Ensure enough temp memory for 'need' array slots is available. 1426 * Returns 0 on success and -1 if the memory can't be gotten. 1427 */ 1428 static int 1429 merge_getmem(MergeState *ms, Py_ssize_t need) 1430 { 1431 assert(ms != NULL); 1432 if (need <= ms->alloced) 1433 return 0; 1434 /* Don't realloc! That can cost cycles to copy the old data, but 1435 * we don't care what's in the block. 1436 */ 1437 merge_freemem(ms); 1438 if ((size_t)need > PY_SSIZE_T_MAX / sizeof(PyObject*)) { 1439 PyErr_NoMemory(); 1440 return -1; 1441 } 1442 ms->a = (PyObject **)PyMem_Malloc(need * sizeof(PyObject*)); 1443 if (ms->a) { 1444 ms->alloced = need; 1445 return 0; 1446 } 1447 PyErr_NoMemory(); 1448 merge_freemem(ms); /* reset to sane state */ 1449 return -1; 1450 } 1451 #define MERGE_GETMEM(MS, NEED) ((NEED) <= (MS)->alloced ? 0 : \ 1452 merge_getmem(MS, NEED)) 1453 1454 /* Merge the na elements starting at pa with the nb elements starting at pb 1455 * in a stable way, in-place. na and nb must be > 0, and pa + na == pb. 1456 * Must also have that *pb < *pa, that pa[na-1] belongs at the end of the 1457 * merge, and should have na <= nb. See listsort.txt for more info. 1458 * Return 0 if successful, -1 if error. 1459 */ 1460 static Py_ssize_t 1461 merge_lo(MergeState *ms, PyObject **pa, Py_ssize_t na, 1462 PyObject **pb, Py_ssize_t nb) 1463 { 1464 Py_ssize_t k; 1465 PyObject *compare; 1466 PyObject **dest; 1467 int result = -1; /* guilty until proved innocent */ 1468 Py_ssize_t min_gallop; 1469 1470 assert(ms && pa && pb && na > 0 && nb > 0 && pa + na == pb); 1471 if (MERGE_GETMEM(ms, na) < 0) 1472 return -1; 1473 memcpy(ms->a, pa, na * sizeof(PyObject*)); 1474 dest = pa; 1475 pa = ms->a; 1476 1477 *dest++ = *pb++; 1478 --nb; 1479 if (nb == 0) 1480 goto Succeed; 1481 if (na == 1) 1482 goto CopyB; 1483 1484 min_gallop = ms->min_gallop; 1485 compare = ms->compare; 1486 for (;;) { 1487 Py_ssize_t acount = 0; /* # of times A won in a row */ 1488 Py_ssize_t bcount = 0; /* # of times B won in a row */ 1489 1490 /* Do the straightforward thing until (if ever) one run 1491 * appears to win consistently. 1492 */ 1493 for (;;) { 1494 assert(na > 1 && nb > 0); 1495 k = ISLT(*pb, *pa, compare); 1496 if (k) { 1497 if (k < 0) 1498 goto Fail; 1499 *dest++ = *pb++; 1500 ++bcount; 1501 acount = 0; 1502 --nb; 1503 if (nb == 0) 1504 goto Succeed; 1505 if (bcount >= min_gallop) 1506 break; 1507 } 1508 else { 1509 *dest++ = *pa++; 1510 ++acount; 1511 bcount = 0; 1512 --na; 1513 if (na == 1) 1514 goto CopyB; 1515 if (acount >= min_gallop) 1516 break; 1517 } 1518 } 1519 1520 /* One run is winning so consistently that galloping may 1521 * be a huge win. So try that, and continue galloping until 1522 * (if ever) neither run appears to be winning consistently 1523 * anymore. 1524 */ 1525 ++min_gallop; 1526 do { 1527 assert(na > 1 && nb > 0); 1528 min_gallop -= min_gallop > 1; 1529 ms->min_gallop = min_gallop; 1530 k = gallop_right(*pb, pa, na, 0, compare); 1531 acount = k; 1532 if (k) { 1533 if (k < 0) 1534 goto Fail; 1535 memcpy(dest, pa, k * sizeof(PyObject *)); 1536 dest += k; 1537 pa += k; 1538 na -= k; 1539 if (na == 1) 1540 goto CopyB; 1541 /* na==0 is impossible now if the comparison 1542 * function is consistent, but we can't assume 1543 * that it is. 1544 */ 1545 if (na == 0) 1546 goto Succeed; 1547 } 1548 *dest++ = *pb++; 1549 --nb; 1550 if (nb == 0) 1551 goto Succeed; 1552 1553 k = gallop_left(*pa, pb, nb, 0, compare); 1554 bcount = k; 1555 if (k) { 1556 if (k < 0) 1557 goto Fail; 1558 memmove(dest, pb, k * sizeof(PyObject *)); 1559 dest += k; 1560 pb += k; 1561 nb -= k; 1562 if (nb == 0) 1563 goto Succeed; 1564 } 1565 *dest++ = *pa++; 1566 --na; 1567 if (na == 1) 1568 goto CopyB; 1569 } while (acount >= MIN_GALLOP || bcount >= MIN_GALLOP); 1570 ++min_gallop; /* penalize it for leaving galloping mode */ 1571 ms->min_gallop = min_gallop; 1572 } 1573 Succeed: 1574 result = 0; 1575 Fail: 1576 if (na) 1577 memcpy(dest, pa, na * sizeof(PyObject*)); 1578 return result; 1579 CopyB: 1580 assert(na == 1 && nb > 0); 1581 /* The last element of pa belongs at the end of the merge. */ 1582 memmove(dest, pb, nb * sizeof(PyObject *)); 1583 dest[nb] = *pa; 1584 return 0; 1585 } 1586 1587 /* Merge the na elements starting at pa with the nb elements starting at pb 1588 * in a stable way, in-place. na and nb must be > 0, and pa + na == pb. 1589 * Must also have that *pb < *pa, that pa[na-1] belongs at the end of the 1590 * merge, and should have na >= nb. See listsort.txt for more info. 1591 * Return 0 if successful, -1 if error. 1592 */ 1593 static Py_ssize_t 1594 merge_hi(MergeState *ms, PyObject **pa, Py_ssize_t na, PyObject **pb, Py_ssize_t nb) 1595 { 1596 Py_ssize_t k; 1597 PyObject *compare; 1598 PyObject **dest; 1599 int result = -1; /* guilty until proved innocent */ 1600 PyObject **basea; 1601 PyObject **baseb; 1602 Py_ssize_t min_gallop; 1603 1604 assert(ms && pa && pb && na > 0 && nb > 0 && pa + na == pb); 1605 if (MERGE_GETMEM(ms, nb) < 0) 1606 return -1; 1607 dest = pb + nb - 1; 1608 memcpy(ms->a, pb, nb * sizeof(PyObject*)); 1609 basea = pa; 1610 baseb = ms->a; 1611 pb = ms->a + nb - 1; 1612 pa += na - 1; 1613 1614 *dest-- = *pa--; 1615 --na; 1616 if (na == 0) 1617 goto Succeed; 1618 if (nb == 1) 1619 goto CopyA; 1620 1621 min_gallop = ms->min_gallop; 1622 compare = ms->compare; 1623 for (;;) { 1624 Py_ssize_t acount = 0; /* # of times A won in a row */ 1625 Py_ssize_t bcount = 0; /* # of times B won in a row */ 1626 1627 /* Do the straightforward thing until (if ever) one run 1628 * appears to win consistently. 1629 */ 1630 for (;;) { 1631 assert(na > 0 && nb > 1); 1632 k = ISLT(*pb, *pa, compare); 1633 if (k) { 1634 if (k < 0) 1635 goto Fail; 1636 *dest-- = *pa--; 1637 ++acount; 1638 bcount = 0; 1639 --na; 1640 if (na == 0) 1641 goto Succeed; 1642 if (acount >= min_gallop) 1643 break; 1644 } 1645 else { 1646 *dest-- = *pb--; 1647 ++bcount; 1648 acount = 0; 1649 --nb; 1650 if (nb == 1) 1651 goto CopyA; 1652 if (bcount >= min_gallop) 1653 break; 1654 } 1655 } 1656 1657 /* One run is winning so consistently that galloping may 1658 * be a huge win. So try that, and continue galloping until 1659 * (if ever) neither run appears to be winning consistently 1660 * anymore. 1661 */ 1662 ++min_gallop; 1663 do { 1664 assert(na > 0 && nb > 1); 1665 min_gallop -= min_gallop > 1; 1666 ms->min_gallop = min_gallop; 1667 k = gallop_right(*pb, basea, na, na-1, compare); 1668 if (k < 0) 1669 goto Fail; 1670 k = na - k; 1671 acount = k; 1672 if (k) { 1673 dest -= k; 1674 pa -= k; 1675 memmove(dest+1, pa+1, k * sizeof(PyObject *)); 1676 na -= k; 1677 if (na == 0) 1678 goto Succeed; 1679 } 1680 *dest-- = *pb--; 1681 --nb; 1682 if (nb == 1) 1683 goto CopyA; 1684 1685 k = gallop_left(*pa, baseb, nb, nb-1, compare); 1686 if (k < 0) 1687 goto Fail; 1688 k = nb - k; 1689 bcount = k; 1690 if (k) { 1691 dest -= k; 1692 pb -= k; 1693 memcpy(dest+1, pb+1, k * sizeof(PyObject *)); 1694 nb -= k; 1695 if (nb == 1) 1696 goto CopyA; 1697 /* nb==0 is impossible now if the comparison 1698 * function is consistent, but we can't assume 1699 * that it is. 1700 */ 1701 if (nb == 0) 1702 goto Succeed; 1703 } 1704 *dest-- = *pa--; 1705 --na; 1706 if (na == 0) 1707 goto Succeed; 1708 } while (acount >= MIN_GALLOP || bcount >= MIN_GALLOP); 1709 ++min_gallop; /* penalize it for leaving galloping mode */ 1710 ms->min_gallop = min_gallop; 1711 } 1712 Succeed: 1713 result = 0; 1714 Fail: 1715 if (nb) 1716 memcpy(dest-(nb-1), baseb, nb * sizeof(PyObject*)); 1717 return result; 1718 CopyA: 1719 assert(nb == 1 && na > 0); 1720 /* The first element of pb belongs at the front of the merge. */ 1721 dest -= na; 1722 pa -= na; 1723 memmove(dest+1, pa+1, na * sizeof(PyObject *)); 1724 *dest = *pb; 1725 return 0; 1726 } 1727 1728 /* Merge the two runs at stack indices i and i+1. 1729 * Returns 0 on success, -1 on error. 1730 */ 1731 static Py_ssize_t 1732 merge_at(MergeState *ms, Py_ssize_t i) 1733 { 1734 PyObject **pa, **pb; 1735 Py_ssize_t na, nb; 1736 Py_ssize_t k; 1737 PyObject *compare; 1738 1739 assert(ms != NULL); 1740 assert(ms->n >= 2); 1741 assert(i >= 0); 1742 assert(i == ms->n - 2 || i == ms->n - 3); 1743 1744 pa = ms->pending[i].base; 1745 na = ms->pending[i].len; 1746 pb = ms->pending[i+1].base; 1747 nb = ms->pending[i+1].len; 1748 assert(na > 0 && nb > 0); 1749 assert(pa + na == pb); 1750 1751 /* Record the length of the combined runs; if i is the 3rd-last 1752 * run now, also slide over the last run (which isn't involved 1753 * in this merge). The current run i+1 goes away in any case. 1754 */ 1755 ms->pending[i].len = na + nb; 1756 if (i == ms->n - 3) 1757 ms->pending[i+1] = ms->pending[i+2]; 1758 --ms->n; 1759 1760 /* Where does b start in a? Elements in a before that can be 1761 * ignored (already in place). 1762 */ 1763 compare = ms->compare; 1764 k = gallop_right(*pb, pa, na, 0, compare); 1765 if (k < 0) 1766 return -1; 1767 pa += k; 1768 na -= k; 1769 if (na == 0) 1770 return 0; 1771 1772 /* Where does a end in b? Elements in b after that can be 1773 * ignored (already in place). 1774 */ 1775 nb = gallop_left(pa[na-1], pb, nb, nb-1, compare); 1776 if (nb <= 0) 1777 return nb; 1778 1779 /* Merge what remains of the runs, using a temp array with 1780 * min(na, nb) elements. 1781 */ 1782 if (na <= nb) 1783 return merge_lo(ms, pa, na, pb, nb); 1784 else 1785 return merge_hi(ms, pa, na, pb, nb); 1786 } 1787 1788 /* Examine the stack of runs waiting to be merged, merging adjacent runs 1789 * until the stack invariants are re-established: 1790 * 1791 * 1. len[-3] > len[-2] + len[-1] 1792 * 2. len[-2] > len[-1] 1793 * 1794 * See listsort.txt for more info. 1795 * 1796 * Returns 0 on success, -1 on error. 1797 */ 1798 static int 1799 merge_collapse(MergeState *ms) 1800 { 1801 struct s_slice *p = ms->pending; 1802 1803 assert(ms); 1804 while (ms->n > 1) { 1805 Py_ssize_t n = ms->n - 2; 1806 if ((n > 0 && p[n-1].len <= p[n].len + p[n+1].len) || 1807 (n > 1 && p[n-2].len <= p[n-1].len + p[n].len)) { 1808 if (p[n-1].len < p[n+1].len) 1809 --n; 1810 if (merge_at(ms, n) < 0) 1811 return -1; 1812 } 1813 else if (p[n].len <= p[n+1].len) { 1814 if (merge_at(ms, n) < 0) 1815 return -1; 1816 } 1817 else 1818 break; 1819 } 1820 return 0; 1821 } 1822 1823 /* Regardless of invariants, merge all runs on the stack until only one 1824 * remains. This is used at the end of the mergesort. 1825 * 1826 * Returns 0 on success, -1 on error. 1827 */ 1828 static int 1829 merge_force_collapse(MergeState *ms) 1830 { 1831 struct s_slice *p = ms->pending; 1832 1833 assert(ms); 1834 while (ms->n > 1) { 1835 Py_ssize_t n = ms->n - 2; 1836 if (n > 0 && p[n-1].len < p[n+1].len) 1837 --n; 1838 if (merge_at(ms, n) < 0) 1839 return -1; 1840 } 1841 return 0; 1842 } 1843 1844 /* Compute a good value for the minimum run length; natural runs shorter 1845 * than this are boosted artificially via binary insertion. 1846 * 1847 * If n < 64, return n (it's too small to bother with fancy stuff). 1848 * Else if n is an exact power of 2, return 32. 1849 * Else return an int k, 32 <= k <= 64, such that n/k is close to, but 1850 * strictly less than, an exact power of 2. 1851 * 1852 * See listsort.txt for more info. 1853 */ 1854 static Py_ssize_t 1855 merge_compute_minrun(Py_ssize_t n) 1856 { 1857 Py_ssize_t r = 0; /* becomes 1 if any 1 bits are shifted off */ 1858 1859 assert(n >= 0); 1860 while (n >= 64) { 1861 r |= n & 1; 1862 n >>= 1; 1863 } 1864 return n + r; 1865 } 1866 1867 /* Special wrapper to support stable sorting using the decorate-sort-undecorate 1868 pattern. Holds a key which is used for comparisons and the original record 1869 which is returned during the undecorate phase. By exposing only the key 1870 during comparisons, the underlying sort stability characteristics are left 1871 unchanged. Also, if a custom comparison function is used, it will only see 1872 the key instead of a full record. */ 1873 1874 typedef struct { 1875 PyObject_HEAD 1876 PyObject *key; 1877 PyObject *value; 1878 } sortwrapperobject; 1879 1880 PyDoc_STRVAR(sortwrapper_doc, "Object wrapper with a custom sort key."); 1881 static PyObject * 1882 sortwrapper_richcompare(sortwrapperobject *, sortwrapperobject *, int); 1883 static void 1884 sortwrapper_dealloc(sortwrapperobject *); 1885 1886 static PyTypeObject sortwrapper_type = { 1887 PyVarObject_HEAD_INIT(&PyType_Type, 0) 1888 "sortwrapper", /* tp_name */ 1889 sizeof(sortwrapperobject), /* tp_basicsize */ 1890 0, /* tp_itemsize */ 1891 /* methods */ 1892 (destructor)sortwrapper_dealloc, /* tp_dealloc */ 1893 0, /* tp_print */ 1894 0, /* tp_getattr */ 1895 0, /* tp_setattr */ 1896 0, /* tp_compare */ 1897 0, /* tp_repr */ 1898 0, /* tp_as_number */ 1899 0, /* tp_as_sequence */ 1900 0, /* tp_as_mapping */ 1901 0, /* tp_hash */ 1902 0, /* tp_call */ 1903 0, /* tp_str */ 1904 PyObject_GenericGetAttr, /* tp_getattro */ 1905 0, /* tp_setattro */ 1906 0, /* tp_as_buffer */ 1907 Py_TPFLAGS_DEFAULT | 1908 Py_TPFLAGS_HAVE_RICHCOMPARE, /* tp_flags */ 1909 sortwrapper_doc, /* tp_doc */ 1910 0, /* tp_traverse */ 1911 0, /* tp_clear */ 1912 (richcmpfunc)sortwrapper_richcompare, /* tp_richcompare */ 1913 }; 1914 1915 1916 static PyObject * 1917 sortwrapper_richcompare(sortwrapperobject *a, sortwrapperobject *b, int op) 1918 { 1919 if (!PyObject_TypeCheck(b, &sortwrapper_type)) { 1920 PyErr_SetString(PyExc_TypeError, 1921 "expected a sortwrapperobject"); 1922 return NULL; 1923 } 1924 return PyObject_RichCompare(a->key, b->key, op); 1925 } 1926 1927 static void 1928 sortwrapper_dealloc(sortwrapperobject *so) 1929 { 1930 Py_XDECREF(so->key); 1931 Py_XDECREF(so->value); 1932 PyObject_Del(so); 1933 } 1934 1935 /* Returns a new reference to a sortwrapper. 1936 Consumes the references to the two underlying objects. */ 1937 1938 static PyObject * 1939 build_sortwrapper(PyObject *key, PyObject *value) 1940 { 1941 sortwrapperobject *so; 1942 1943 so = PyObject_New(sortwrapperobject, &sortwrapper_type); 1944 if (so == NULL) 1945 return NULL; 1946 so->key = key; 1947 so->value = value; 1948 return (PyObject *)so; 1949 } 1950 1951 /* Returns a new reference to the value underlying the wrapper. */ 1952 static PyObject * 1953 sortwrapper_getvalue(PyObject *so) 1954 { 1955 PyObject *value; 1956 1957 if (!PyObject_TypeCheck(so, &sortwrapper_type)) { 1958 PyErr_SetString(PyExc_TypeError, 1959 "expected a sortwrapperobject"); 1960 return NULL; 1961 } 1962 value = ((sortwrapperobject *)so)->value; 1963 Py_INCREF(value); 1964 return value; 1965 } 1966 1967 /* Wrapper for user specified cmp functions in combination with a 1968 specified key function. Makes sure the cmp function is presented 1969 with the actual key instead of the sortwrapper */ 1970 1971 typedef struct { 1972 PyObject_HEAD 1973 PyObject *func; 1974 } cmpwrapperobject; 1975 1976 static void 1977 cmpwrapper_dealloc(cmpwrapperobject *co) 1978 { 1979 Py_XDECREF(co->func); 1980 PyObject_Del(co); 1981 } 1982 1983 static PyObject * 1984 cmpwrapper_call(cmpwrapperobject *co, PyObject *args, PyObject *kwds) 1985 { 1986 PyObject *x, *y, *xx, *yy; 1987 1988 if (!PyArg_UnpackTuple(args, "", 2, 2, &x, &y)) 1989 return NULL; 1990 if (!PyObject_TypeCheck(x, &sortwrapper_type) || 1991 !PyObject_TypeCheck(y, &sortwrapper_type)) { 1992 PyErr_SetString(PyExc_TypeError, 1993 "expected a sortwrapperobject"); 1994 return NULL; 1995 } 1996 xx = ((sortwrapperobject *)x)->key; 1997 yy = ((sortwrapperobject *)y)->key; 1998 return PyObject_CallFunctionObjArgs(co->func, xx, yy, NULL); 1999 } 2000 2001 PyDoc_STRVAR(cmpwrapper_doc, "cmp() wrapper for sort with custom keys."); 2002 2003 static PyTypeObject cmpwrapper_type = { 2004 PyVarObject_HEAD_INIT(&PyType_Type, 0) 2005 "cmpwrapper", /* tp_name */ 2006 sizeof(cmpwrapperobject), /* tp_basicsize */ 2007 0, /* tp_itemsize */ 2008 /* methods */ 2009 (destructor)cmpwrapper_dealloc, /* tp_dealloc */ 2010 0, /* tp_print */ 2011 0, /* tp_getattr */ 2012 0, /* tp_setattr */ 2013 0, /* tp_compare */ 2014 0, /* tp_repr */ 2015 0, /* tp_as_number */ 2016 0, /* tp_as_sequence */ 2017 0, /* tp_as_mapping */ 2018 0, /* tp_hash */ 2019 (ternaryfunc)cmpwrapper_call, /* tp_call */ 2020 0, /* tp_str */ 2021 PyObject_GenericGetAttr, /* tp_getattro */ 2022 0, /* tp_setattro */ 2023 0, /* tp_as_buffer */ 2024 Py_TPFLAGS_DEFAULT, /* tp_flags */ 2025 cmpwrapper_doc, /* tp_doc */ 2026 }; 2027 2028 static PyObject * 2029 build_cmpwrapper(PyObject *cmpfunc) 2030 { 2031 cmpwrapperobject *co; 2032 2033 co = PyObject_New(cmpwrapperobject, &cmpwrapper_type); 2034 if (co == NULL) 2035 return NULL; 2036 Py_INCREF(cmpfunc); 2037 co->func = cmpfunc; 2038 return (PyObject *)co; 2039 } 2040 2041 /* An adaptive, stable, natural mergesort. See listsort.txt. 2042 * Returns Py_None on success, NULL on error. Even in case of error, the 2043 * list will be some permutation of its input state (nothing is lost or 2044 * duplicated). 2045 */ 2046 static PyObject * 2047 listsort(PyListObject *self, PyObject *args, PyObject *kwds) 2048 { 2049 MergeState ms; 2050 PyObject **lo, **hi; 2051 Py_ssize_t nremaining; 2052 Py_ssize_t minrun; 2053 Py_ssize_t saved_ob_size, saved_allocated; 2054 PyObject **saved_ob_item; 2055 PyObject **final_ob_item; 2056 PyObject *compare = NULL; 2057 PyObject *result = NULL; /* guilty until proved innocent */ 2058 int reverse = 0; 2059 PyObject *keyfunc = NULL; 2060 Py_ssize_t i; 2061 PyObject *key, *value, *kvpair; 2062 static char *kwlist[] = {"cmp", "key", "reverse", 0}; 2063 2064 assert(self != NULL); 2065 assert (PyList_Check(self)); 2066 if (args != NULL) { 2067 if (!PyArg_ParseTupleAndKeywords(args, kwds, "|OOi:sort", 2068 kwlist, &compare, &keyfunc, &reverse)) 2069 return NULL; 2070 } 2071 if (compare == Py_None) 2072 compare = NULL; 2073 if (compare != NULL && 2074 PyErr_WarnPy3k("the cmp argument is not supported in 3.x", 1) < 0) 2075 return NULL; 2076 if (keyfunc == Py_None) 2077 keyfunc = NULL; 2078 if (compare != NULL && keyfunc != NULL) { 2079 compare = build_cmpwrapper(compare); 2080 if (compare == NULL) 2081 return NULL; 2082 } else 2083 Py_XINCREF(compare); 2084 2085 /* The list is temporarily made empty, so that mutations performed 2086 * by comparison functions can't affect the slice of memory we're 2087 * sorting (allowing mutations during sorting is a core-dump 2088 * factory, since ob_item may change). 2089 */ 2090 saved_ob_size = Py_SIZE(self); 2091 saved_ob_item = self->ob_item; 2092 saved_allocated = self->allocated; 2093 Py_SIZE(self) = 0; 2094 self->ob_item = NULL; 2095 self->allocated = -1; /* any operation will reset it to >= 0 */ 2096 2097 if (keyfunc != NULL) { 2098 for (i=0 ; i < saved_ob_size ; i++) { 2099 value = saved_ob_item[i]; 2100 key = PyObject_CallFunctionObjArgs(keyfunc, value, 2101 NULL); 2102 if (key == NULL) { 2103 for (i=i-1 ; i>=0 ; i--) { 2104 kvpair = saved_ob_item[i]; 2105 value = sortwrapper_getvalue(kvpair); 2106 saved_ob_item[i] = value; 2107 Py_DECREF(kvpair); 2108 } 2109 goto dsu_fail; 2110 } 2111 kvpair = build_sortwrapper(key, value); 2112 if (kvpair == NULL) 2113 goto dsu_fail; 2114 saved_ob_item[i] = kvpair; 2115 } 2116 } 2117 2118 /* Reverse sort stability achieved by initially reversing the list, 2119 applying a stable forward sort, then reversing the final result. */ 2120 if (reverse && saved_ob_size > 1) 2121 reverse_slice(saved_ob_item, saved_ob_item + saved_ob_size); 2122 2123 merge_init(&ms, compare); 2124 2125 nremaining = saved_ob_size; 2126 if (nremaining < 2) 2127 goto succeed; 2128 2129 /* March over the array once, left to right, finding natural runs, 2130 * and extending short natural runs to minrun elements. 2131 */ 2132 lo = saved_ob_item; 2133 hi = lo + nremaining; 2134 minrun = merge_compute_minrun(nremaining); 2135 do { 2136 int descending; 2137 Py_ssize_t n; 2138 2139 /* Identify next run. */ 2140 n = count_run(lo, hi, compare, &descending); 2141 if (n < 0) 2142 goto fail; 2143 if (descending) 2144 reverse_slice(lo, lo + n); 2145 /* If short, extend to min(minrun, nremaining). */ 2146 if (n < minrun) { 2147 const Py_ssize_t force = nremaining <= minrun ? 2148 nremaining : minrun; 2149 if (binarysort(lo, lo + force, lo + n, compare) < 0) 2150 goto fail; 2151 n = force; 2152 } 2153 /* Push run onto pending-runs stack, and maybe merge. */ 2154 assert(ms.n < MAX_MERGE_PENDING); 2155 ms.pending[ms.n].base = lo; 2156 ms.pending[ms.n].len = n; 2157 ++ms.n; 2158 if (merge_collapse(&ms) < 0) 2159 goto fail; 2160 /* Advance to find next run. */ 2161 lo += n; 2162 nremaining -= n; 2163 } while (nremaining); 2164 assert(lo == hi); 2165 2166 if (merge_force_collapse(&ms) < 0) 2167 goto fail; 2168 assert(ms.n == 1); 2169 assert(ms.pending[0].base == saved_ob_item); 2170 assert(ms.pending[0].len == saved_ob_size); 2171 2172 succeed: 2173 result = Py_None; 2174 fail: 2175 if (keyfunc != NULL) { 2176 for (i=0 ; i < saved_ob_size ; i++) { 2177 kvpair = saved_ob_item[i]; 2178 value = sortwrapper_getvalue(kvpair); 2179 saved_ob_item[i] = value; 2180 Py_DECREF(kvpair); 2181 } 2182 } 2183 2184 if (self->allocated != -1 && result != NULL) { 2185 /* The user mucked with the list during the sort, 2186 * and we don't already have another error to report. 2187 */ 2188 PyErr_SetString(PyExc_ValueError, "list modified during sort"); 2189 result = NULL; 2190 } 2191 2192 if (reverse && saved_ob_size > 1) 2193 reverse_slice(saved_ob_item, saved_ob_item + saved_ob_size); 2194 2195 merge_freemem(&ms); 2196 2197 dsu_fail: 2198 final_ob_item = self->ob_item; 2199 i = Py_SIZE(self); 2200 Py_SIZE(self) = saved_ob_size; 2201 self->ob_item = saved_ob_item; 2202 self->allocated = saved_allocated; 2203 if (final_ob_item != NULL) { 2204 /* we cannot use list_clear() for this because it does not 2205 guarantee that the list is really empty when it returns */ 2206 while (--i >= 0) { 2207 Py_XDECREF(final_ob_item[i]); 2208 } 2209 PyMem_FREE(final_ob_item); 2210 } 2211 Py_XDECREF(compare); 2212 Py_XINCREF(result); 2213 return result; 2214 } 2215 #undef IFLT 2216 #undef ISLT 2217 2218 int 2219 PyList_Sort(PyObject *v) 2220 { 2221 if (v == NULL || !PyList_Check(v)) { 2222 PyErr_BadInternalCall(); 2223 return -1; 2224 } 2225 v = listsort((PyListObject *)v, (PyObject *)NULL, (PyObject *)NULL); 2226 if (v == NULL) 2227 return -1; 2228 Py_DECREF(v); 2229 return 0; 2230 } 2231 2232 static PyObject * 2233 listreverse(PyListObject *self) 2234 { 2235 if (Py_SIZE(self) > 1) 2236 reverse_slice(self->ob_item, self->ob_item + Py_SIZE(self)); 2237 Py_RETURN_NONE; 2238 } 2239 2240 int 2241 PyList_Reverse(PyObject *v) 2242 { 2243 PyListObject *self = (PyListObject *)v; 2244 2245 if (v == NULL || !PyList_Check(v)) { 2246 PyErr_BadInternalCall(); 2247 return -1; 2248 } 2249 if (Py_SIZE(self) > 1) 2250 reverse_slice(self->ob_item, self->ob_item + Py_SIZE(self)); 2251 return 0; 2252 } 2253 2254 PyObject * 2255 PyList_AsTuple(PyObject *v) 2256 { 2257 PyObject *w; 2258 PyObject **p, **q; 2259 Py_ssize_t n; 2260 if (v == NULL || !PyList_Check(v)) { 2261 PyErr_BadInternalCall(); 2262 return NULL; 2263 } 2264 n = Py_SIZE(v); 2265 w = PyTuple_New(n); 2266 if (w == NULL) 2267 return NULL; 2268 p = ((PyTupleObject *)w)->ob_item; 2269 q = ((PyListObject *)v)->ob_item; 2270 while (--n >= 0) { 2271 Py_INCREF(*q); 2272 *p = *q; 2273 p++; 2274 q++; 2275 } 2276 return w; 2277 } 2278 2279 static PyObject * 2280 listindex(PyListObject *self, PyObject *args) 2281 { 2282 Py_ssize_t i, start=0, stop=Py_SIZE(self); 2283 PyObject *v, *format_tuple, *err_string; 2284 static PyObject *err_format = NULL; 2285 2286 if (!PyArg_ParseTuple(args, "O|O&O&:index", &v, 2287 _PyEval_SliceIndex, &start, 2288 _PyEval_SliceIndex, &stop)) 2289 return NULL; 2290 if (start < 0) { 2291 start += Py_SIZE(self); 2292 if (start < 0) 2293 start = 0; 2294 } 2295 if (stop < 0) { 2296 stop += Py_SIZE(self); 2297 if (stop < 0) 2298 stop = 0; 2299 } 2300 for (i = start; i < stop && i < Py_SIZE(self); i++) { 2301 int cmp = PyObject_RichCompareBool(self->ob_item[i], v, Py_EQ); 2302 if (cmp > 0) 2303 return PyInt_FromSsize_t(i); 2304 else if (cmp < 0) 2305 return NULL; 2306 } 2307 if (err_format == NULL) { 2308 err_format = PyString_FromString("%r is not in list"); 2309 if (err_format == NULL) 2310 return NULL; 2311 } 2312 format_tuple = PyTuple_Pack(1, v); 2313 if (format_tuple == NULL) 2314 return NULL; 2315 err_string = PyString_Format(err_format, format_tuple); 2316 Py_DECREF(format_tuple); 2317 if (err_string == NULL) 2318 return NULL; 2319 PyErr_SetObject(PyExc_ValueError, err_string); 2320 Py_DECREF(err_string); 2321 return NULL; 2322 } 2323 2324 static PyObject * 2325 listcount(PyListObject *self, PyObject *v) 2326 { 2327 Py_ssize_t count = 0; 2328 Py_ssize_t i; 2329 2330 for (i = 0; i < Py_SIZE(self); i++) { 2331 int cmp = PyObject_RichCompareBool(self->ob_item[i], v, Py_EQ); 2332 if (cmp > 0) 2333 count++; 2334 else if (cmp < 0) 2335 return NULL; 2336 } 2337 return PyInt_FromSsize_t(count); 2338 } 2339 2340 static PyObject * 2341 listremove(PyListObject *self, PyObject *v) 2342 { 2343 Py_ssize_t i; 2344 2345 for (i = 0; i < Py_SIZE(self); i++) { 2346 int cmp = PyObject_RichCompareBool(self->ob_item[i], v, Py_EQ); 2347 if (cmp > 0) { 2348 if (list_ass_slice(self, i, i+1, 2349 (PyObject *)NULL) == 0) 2350 Py_RETURN_NONE; 2351 return NULL; 2352 } 2353 else if (cmp < 0) 2354 return NULL; 2355 } 2356 PyErr_SetString(PyExc_ValueError, "list.remove(x): x not in list"); 2357 return NULL; 2358 } 2359 2360 static int 2361 list_traverse(PyListObject *o, visitproc visit, void *arg) 2362 { 2363 Py_ssize_t i; 2364 2365 for (i = Py_SIZE(o); --i >= 0; ) 2366 Py_VISIT(o->ob_item[i]); 2367 return 0; 2368 } 2369 2370 static PyObject * 2371 list_richcompare(PyObject *v, PyObject *w, int op) 2372 { 2373 PyListObject *vl, *wl; 2374 Py_ssize_t i; 2375 2376 if (!PyList_Check(v) || !PyList_Check(w)) { 2377 Py_INCREF(Py_NotImplemented); 2378 return Py_NotImplemented; 2379 } 2380 2381 vl = (PyListObject *)v; 2382 wl = (PyListObject *)w; 2383 2384 if (Py_SIZE(vl) != Py_SIZE(wl) && (op == Py_EQ || op == Py_NE)) { 2385 /* Shortcut: if the lengths differ, the lists differ */ 2386 PyObject *res; 2387 if (op == Py_EQ) 2388 res = Py_False; 2389 else 2390 res = Py_True; 2391 Py_INCREF(res); 2392 return res; 2393 } 2394 2395 /* Search for the first index where items are different */ 2396 for (i = 0; i < Py_SIZE(vl) && i < Py_SIZE(wl); i++) { 2397 int k = PyObject_RichCompareBool(vl->ob_item[i], 2398 wl->ob_item[i], Py_EQ); 2399 if (k < 0) 2400 return NULL; 2401 if (!k) 2402 break; 2403 } 2404 2405 if (i >= Py_SIZE(vl) || i >= Py_SIZE(wl)) { 2406 /* No more items to compare -- compare sizes */ 2407 Py_ssize_t vs = Py_SIZE(vl); 2408 Py_ssize_t ws = Py_SIZE(wl); 2409 int cmp; 2410 PyObject *res; 2411 switch (op) { 2412 case Py_LT: cmp = vs < ws; break; 2413 case Py_LE: cmp = vs <= ws; break; 2414 case Py_EQ: cmp = vs == ws; break; 2415 case Py_NE: cmp = vs != ws; break; 2416 case Py_GT: cmp = vs > ws; break; 2417 case Py_GE: cmp = vs >= ws; break; 2418 default: return NULL; /* cannot happen */ 2419 } 2420 if (cmp) 2421 res = Py_True; 2422 else 2423 res = Py_False; 2424 Py_INCREF(res); 2425 return res; 2426 } 2427 2428 /* We have an item that differs -- shortcuts for EQ/NE */ 2429 if (op == Py_EQ) { 2430 Py_INCREF(Py_False); 2431 return Py_False; 2432 } 2433 if (op == Py_NE) { 2434 Py_INCREF(Py_True); 2435 return Py_True; 2436 } 2437 2438 /* Compare the final item again using the proper operator */ 2439 return PyObject_RichCompare(vl->ob_item[i], wl->ob_item[i], op); 2440 } 2441 2442 static int 2443 list_init(PyListObject *self, PyObject *args, PyObject *kw) 2444 { 2445 PyObject *arg = NULL; 2446 static char *kwlist[] = {"sequence", 0}; 2447 2448 if (!PyArg_ParseTupleAndKeywords(args, kw, "|O:list", kwlist, &arg)) 2449 return -1; 2450 2451 /* Verify list invariants established by PyType_GenericAlloc() */ 2452 assert(0 <= Py_SIZE(self)); 2453 assert(Py_SIZE(self) <= self->allocated || self->allocated == -1); 2454 assert(self->ob_item != NULL || 2455 self->allocated == 0 || self->allocated == -1); 2456 2457 /* Empty previous contents */ 2458 if (self->ob_item != NULL) { 2459 (void)list_clear(self); 2460 } 2461 if (arg != NULL) { 2462 PyObject *rv = listextend(self, arg); 2463 if (rv == NULL) 2464 return -1; 2465 Py_DECREF(rv); 2466 } 2467 return 0; 2468 } 2469 2470 static PyObject * 2471 list_sizeof(PyListObject *self) 2472 { 2473 Py_ssize_t res; 2474 2475 res = _PyObject_SIZE(Py_TYPE(self)) + self->allocated * sizeof(void*); 2476 return PyInt_FromSsize_t(res); 2477 } 2478 2479 static PyObject *list_iter(PyObject *seq); 2480 static PyObject *list_reversed(PyListObject* seq, PyObject* unused); 2481 2482 PyDoc_STRVAR(getitem_doc, 2483 "x.__getitem__(y) <==> x[y]"); 2484 PyDoc_STRVAR(reversed_doc, 2485 "L.__reversed__() -- return a reverse iterator over the list"); 2486 PyDoc_STRVAR(sizeof_doc, 2487 "L.__sizeof__() -- size of L in memory, in bytes"); 2488 PyDoc_STRVAR(append_doc, 2489 "L.append(object) -- append object to end"); 2490 PyDoc_STRVAR(extend_doc, 2491 "L.extend(iterable) -- extend list by appending elements from the iterable"); 2492 PyDoc_STRVAR(insert_doc, 2493 "L.insert(index, object) -- insert object before index"); 2494 PyDoc_STRVAR(pop_doc, 2495 "L.pop([index]) -> item -- remove and return item at index (default last).\n" 2496 "Raises IndexError if list is empty or index is out of range."); 2497 PyDoc_STRVAR(remove_doc, 2498 "L.remove(value) -- remove first occurrence of value.\n" 2499 "Raises ValueError if the value is not present."); 2500 PyDoc_STRVAR(index_doc, 2501 "L.index(value, [start, [stop]]) -> integer -- return first index of value.\n" 2502 "Raises ValueError if the value is not present."); 2503 PyDoc_STRVAR(count_doc, 2504 "L.count(value) -> integer -- return number of occurrences of value"); 2505 PyDoc_STRVAR(reverse_doc, 2506 "L.reverse() -- reverse *IN PLACE*"); 2507 PyDoc_STRVAR(sort_doc, 2508 "L.sort(cmp=None, key=None, reverse=False) -- stable sort *IN PLACE*;\n\ 2509 cmp(x, y) -> -1, 0, 1"); 2510 2511 static PyObject *list_subscript(PyListObject*, PyObject*); 2512 2513 static PyMethodDef list_methods[] = { 2514 {"__getitem__", (PyCFunction)list_subscript, METH_O|METH_COEXIST, getitem_doc}, 2515 {"__reversed__",(PyCFunction)list_reversed, METH_NOARGS, reversed_doc}, 2516 {"__sizeof__", (PyCFunction)list_sizeof, METH_NOARGS, sizeof_doc}, 2517 {"append", (PyCFunction)listappend, METH_O, append_doc}, 2518 {"insert", (PyCFunction)listinsert, METH_VARARGS, insert_doc}, 2519 {"extend", (PyCFunction)listextend, METH_O, extend_doc}, 2520 {"pop", (PyCFunction)listpop, METH_VARARGS, pop_doc}, 2521 {"remove", (PyCFunction)listremove, METH_O, remove_doc}, 2522 {"index", (PyCFunction)listindex, METH_VARARGS, index_doc}, 2523 {"count", (PyCFunction)listcount, METH_O, count_doc}, 2524 {"reverse", (PyCFunction)listreverse, METH_NOARGS, reverse_doc}, 2525 {"sort", (PyCFunction)listsort, METH_VARARGS | METH_KEYWORDS, sort_doc}, 2526 {NULL, NULL} /* sentinel */ 2527 }; 2528 2529 static PySequenceMethods list_as_sequence = { 2530 (lenfunc)list_length, /* sq_length */ 2531 (binaryfunc)list_concat, /* sq_concat */ 2532 (ssizeargfunc)list_repeat, /* sq_repeat */ 2533 (ssizeargfunc)list_item, /* sq_item */ 2534 (ssizessizeargfunc)list_slice, /* sq_slice */ 2535 (ssizeobjargproc)list_ass_item, /* sq_ass_item */ 2536 (ssizessizeobjargproc)list_ass_slice, /* sq_ass_slice */ 2537 (objobjproc)list_contains, /* sq_contains */ 2538 (binaryfunc)list_inplace_concat, /* sq_inplace_concat */ 2539 (ssizeargfunc)list_inplace_repeat, /* sq_inplace_repeat */ 2540 }; 2541 2542 PyDoc_STRVAR(list_doc, 2543 "list() -> new empty list\n" 2544 "list(iterable) -> new list initialized from iterable's items"); 2545 2546 2547 static PyObject * 2548 list_subscript(PyListObject* self, PyObject* item) 2549 { 2550 if (PyIndex_Check(item)) { 2551 Py_ssize_t i; 2552 i = PyNumber_AsSsize_t(item, PyExc_IndexError); 2553 if (i == -1 && PyErr_Occurred()) 2554 return NULL; 2555 if (i < 0) 2556 i += PyList_GET_SIZE(self); 2557 return list_item(self, i); 2558 } 2559 else if (PySlice_Check(item)) { 2560 Py_ssize_t start, stop, step, slicelength, cur, i; 2561 PyObject* result; 2562 PyObject* it; 2563 PyObject **src, **dest; 2564 2565 if (PySlice_GetIndicesEx((PySliceObject*)item, Py_SIZE(self), 2566 &start, &stop, &step, &slicelength) < 0) { 2567 return NULL; 2568 } 2569 2570 if (slicelength <= 0) { 2571 return PyList_New(0); 2572 } 2573 else if (step == 1) { 2574 return list_slice(self, start, stop); 2575 } 2576 else { 2577 result = PyList_New(slicelength); 2578 if (!result) return NULL; 2579 2580 src = self->ob_item; 2581 dest = ((PyListObject *)result)->ob_item; 2582 for (cur = start, i = 0; i < slicelength; 2583 cur += step, i++) { 2584 it = src[cur]; 2585 Py_INCREF(it); 2586 dest[i] = it; 2587 } 2588 2589 return result; 2590 } 2591 } 2592 else { 2593 PyErr_Format(PyExc_TypeError, 2594 "list indices must be integers, not %.200s", 2595 item->ob_type->tp_name); 2596 return NULL; 2597 } 2598 } 2599 2600 static int 2601 list_ass_subscript(PyListObject* self, PyObject* item, PyObject* value) 2602 { 2603 if (PyIndex_Check(item)) { 2604 Py_ssize_t i = PyNumber_AsSsize_t(item, PyExc_IndexError); 2605 if (i == -1 && PyErr_Occurred()) 2606 return -1; 2607 if (i < 0) 2608 i += PyList_GET_SIZE(self); 2609 return list_ass_item(self, i, value); 2610 } 2611 else if (PySlice_Check(item)) { 2612 Py_ssize_t start, stop, step, slicelength; 2613 2614 if (PySlice_GetIndicesEx((PySliceObject*)item, Py_SIZE(self), 2615 &start, &stop, &step, &slicelength) < 0) { 2616 return -1; 2617 } 2618 2619 if (step == 1) 2620 return list_ass_slice(self, start, stop, value); 2621 2622 /* Make sure s[5:2] = [..] inserts at the right place: 2623 before 5, not before 2. */ 2624 if ((step < 0 && start < stop) || 2625 (step > 0 && start > stop)) 2626 stop = start; 2627 2628 if (value == NULL) { 2629 /* delete slice */ 2630 PyObject **garbage; 2631 size_t cur; 2632 Py_ssize_t i; 2633 2634 if (slicelength <= 0) 2635 return 0; 2636 2637 if (step < 0) { 2638 stop = start + 1; 2639 start = stop + step*(slicelength - 1) - 1; 2640 step = -step; 2641 } 2642 2643 assert((size_t)slicelength <= 2644 PY_SIZE_MAX / sizeof(PyObject*)); 2645 2646 garbage = (PyObject**) 2647 PyMem_MALLOC(slicelength*sizeof(PyObject*)); 2648 if (!garbage) { 2649 PyErr_NoMemory(); 2650 return -1; 2651 } 2652 2653 /* drawing pictures might help understand these for 2654 loops. Basically, we memmove the parts of the 2655 list that are *not* part of the slice: step-1 2656 items for each item that is part of the slice, 2657 and then tail end of the list that was not 2658 covered by the slice */ 2659 for (cur = start, i = 0; 2660 cur < (size_t)stop; 2661 cur += step, i++) { 2662 Py_ssize_t lim = step - 1; 2663 2664 garbage[i] = PyList_GET_ITEM(self, cur); 2665 2666 if (cur + step >= (size_t)Py_SIZE(self)) { 2667 lim = Py_SIZE(self) - cur - 1; 2668 } 2669 2670 memmove(self->ob_item + cur - i, 2671 self->ob_item + cur + 1, 2672 lim * sizeof(PyObject *)); 2673 } 2674 cur = start + slicelength*step; 2675 if (cur < (size_t)Py_SIZE(self)) { 2676 memmove(self->ob_item + cur - slicelength, 2677 self->ob_item + cur, 2678 (Py_SIZE(self) - cur) * 2679 sizeof(PyObject *)); 2680 } 2681 2682 Py_SIZE(self) -= slicelength; 2683 list_resize(self, Py_SIZE(self)); 2684 2685 for (i = 0; i < slicelength; i++) { 2686 Py_DECREF(garbage[i]); 2687 } 2688 PyMem_FREE(garbage); 2689 2690 return 0; 2691 } 2692 else { 2693 /* assign slice */ 2694 PyObject *ins, *seq; 2695 PyObject **garbage, **seqitems, **selfitems; 2696 Py_ssize_t cur, i; 2697 2698 /* protect against a[::-1] = a */ 2699 if (self == (PyListObject*)value) { 2700 seq = list_slice((PyListObject*)value, 0, 2701 PyList_GET_SIZE(value)); 2702 } 2703 else { 2704 seq = PySequence_Fast(value, 2705 "must assign iterable " 2706 "to extended slice"); 2707 } 2708 if (!seq) 2709 return -1; 2710 2711 if (PySequence_Fast_GET_SIZE(seq) != slicelength) { 2712 PyErr_Format(PyExc_ValueError, 2713 "attempt to assign sequence of " 2714 "size %zd to extended slice of " 2715 "size %zd", 2716 PySequence_Fast_GET_SIZE(seq), 2717 slicelength); 2718 Py_DECREF(seq); 2719 return -1; 2720 } 2721 2722 if (!slicelength) { 2723 Py_DECREF(seq); 2724 return 0; 2725 } 2726 2727 garbage = (PyObject**) 2728 PyMem_MALLOC(slicelength*sizeof(PyObject*)); 2729 if (!garbage) { 2730 Py_DECREF(seq); 2731 PyErr_NoMemory(); 2732 return -1; 2733 } 2734 2735 selfitems = self->ob_item; 2736 seqitems = PySequence_Fast_ITEMS(seq); 2737 for (cur = start, i = 0; i < slicelength; 2738 cur += step, i++) { 2739 garbage[i] = selfitems[cur]; 2740 ins = seqitems[i]; 2741 Py_INCREF(ins); 2742 selfitems[cur] = ins; 2743 } 2744 2745 for (i = 0; i < slicelength; i++) { 2746 Py_DECREF(garbage[i]); 2747 } 2748 2749 PyMem_FREE(garbage); 2750 Py_DECREF(seq); 2751 2752 return 0; 2753 } 2754 } 2755 else { 2756 PyErr_Format(PyExc_TypeError, 2757 "list indices must be integers, not %.200s", 2758 item->ob_type->tp_name); 2759 return -1; 2760 } 2761 } 2762 2763 static PyMappingMethods list_as_mapping = { 2764 (lenfunc)list_length, 2765 (binaryfunc)list_subscript, 2766 (objobjargproc)list_ass_subscript 2767 }; 2768 2769 PyTypeObject PyList_Type = { 2770 PyVarObject_HEAD_INIT(&PyType_Type, 0) 2771 "list", 2772 sizeof(PyListObject), 2773 0, 2774 (destructor)list_dealloc, /* tp_dealloc */ 2775 (printfunc)list_print, /* tp_print */ 2776 0, /* tp_getattr */ 2777 0, /* tp_setattr */ 2778 0, /* tp_compare */ 2779 (reprfunc)list_repr, /* tp_repr */ 2780 0, /* tp_as_number */ 2781 &list_as_sequence, /* tp_as_sequence */ 2782 &list_as_mapping, /* tp_as_mapping */ 2783 (hashfunc)PyObject_HashNotImplemented, /* tp_hash */ 2784 0, /* tp_call */ 2785 0, /* tp_str */ 2786 PyObject_GenericGetAttr, /* tp_getattro */ 2787 0, /* tp_setattro */ 2788 0, /* tp_as_buffer */ 2789 Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC | 2790 Py_TPFLAGS_BASETYPE | Py_TPFLAGS_LIST_SUBCLASS, /* tp_flags */ 2791 list_doc, /* tp_doc */ 2792 (traverseproc)list_traverse, /* tp_traverse */ 2793 (inquiry)list_clear, /* tp_clear */ 2794 list_richcompare, /* tp_richcompare */ 2795 0, /* tp_weaklistoffset */ 2796 list_iter, /* tp_iter */ 2797 0, /* tp_iternext */ 2798 list_methods, /* tp_methods */ 2799 0, /* tp_members */ 2800 0, /* tp_getset */ 2801 0, /* tp_base */ 2802 0, /* tp_dict */ 2803 0, /* tp_descr_get */ 2804 0, /* tp_descr_set */ 2805 0, /* tp_dictoffset */ 2806 (initproc)list_init, /* tp_init */ 2807 PyType_GenericAlloc, /* tp_alloc */ 2808 PyType_GenericNew, /* tp_new */ 2809 PyObject_GC_Del, /* tp_free */ 2810 }; 2811 2812 2813 /*********************** List Iterator **************************/ 2814 2815 typedef struct { 2816 PyObject_HEAD 2817 long it_index; 2818 PyListObject *it_seq; /* Set to NULL when iterator is exhausted */ 2819 } listiterobject; 2820 2821 static PyObject *list_iter(PyObject *); 2822 static void listiter_dealloc(listiterobject *); 2823 static int listiter_traverse(listiterobject *, visitproc, void *); 2824 static PyObject *listiter_next(listiterobject *); 2825 static PyObject *listiter_len(listiterobject *); 2826 2827 PyDoc_STRVAR(length_hint_doc, "Private method returning an estimate of len(list(it))."); 2828 2829 static PyMethodDef listiter_methods[] = { 2830 {"__length_hint__", (PyCFunction)listiter_len, METH_NOARGS, length_hint_doc}, 2831 {NULL, NULL} /* sentinel */ 2832 }; 2833 2834 PyTypeObject PyListIter_Type = { 2835 PyVarObject_HEAD_INIT(&PyType_Type, 0) 2836 "listiterator", /* tp_name */ 2837 sizeof(listiterobject), /* tp_basicsize */ 2838 0, /* tp_itemsize */ 2839 /* methods */ 2840 (destructor)listiter_dealloc, /* tp_dealloc */ 2841 0, /* tp_print */ 2842 0, /* tp_getattr */ 2843 0, /* tp_setattr */ 2844 0, /* tp_compare */ 2845 0, /* tp_repr */ 2846 0, /* tp_as_number */ 2847 0, /* tp_as_sequence */ 2848 0, /* tp_as_mapping */ 2849 0, /* tp_hash */ 2850 0, /* tp_call */ 2851 0, /* tp_str */ 2852 PyObject_GenericGetAttr, /* tp_getattro */ 2853 0, /* tp_setattro */ 2854 0, /* tp_as_buffer */ 2855 Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC,/* tp_flags */ 2856 0, /* tp_doc */ 2857 (traverseproc)listiter_traverse, /* tp_traverse */ 2858 0, /* tp_clear */ 2859 0, /* tp_richcompare */ 2860 0, /* tp_weaklistoffset */ 2861 PyObject_SelfIter, /* tp_iter */ 2862 (iternextfunc)listiter_next, /* tp_iternext */ 2863 listiter_methods, /* tp_methods */ 2864 0, /* tp_members */ 2865 }; 2866 2867 2868 static PyObject * 2869 list_iter(PyObject *seq) 2870 { 2871 listiterobject *it; 2872 2873 if (!PyList_Check(seq)) { 2874 PyErr_BadInternalCall(); 2875 return NULL; 2876 } 2877 it = PyObject_GC_New(listiterobject, &PyListIter_Type); 2878 if (it == NULL) 2879 return NULL; 2880 it->it_index = 0; 2881 Py_INCREF(seq); 2882 it->it_seq = (PyListObject *)seq; 2883 _PyObject_GC_TRACK(it); 2884 return (PyObject *)it; 2885 } 2886 2887 static void 2888 listiter_dealloc(listiterobject *it) 2889 { 2890 _PyObject_GC_UNTRACK(it); 2891 Py_XDECREF(it->it_seq); 2892 PyObject_GC_Del(it); 2893 } 2894 2895 static int 2896 listiter_traverse(listiterobject *it, visitproc visit, void *arg) 2897 { 2898 Py_VISIT(it->it_seq); 2899 return 0; 2900 } 2901 2902 static PyObject * 2903 listiter_next(listiterobject *it) 2904 { 2905 PyListObject *seq; 2906 PyObject *item; 2907 2908 assert(it != NULL); 2909 seq = it->it_seq; 2910 if (seq == NULL) 2911 return NULL; 2912 assert(PyList_Check(seq)); 2913 2914 if (it->it_index < PyList_GET_SIZE(seq)) { 2915 item = PyList_GET_ITEM(seq, it->it_index); 2916 ++it->it_index; 2917 Py_INCREF(item); 2918 return item; 2919 } 2920 2921 it->it_seq = NULL; 2922 Py_DECREF(seq); 2923 return NULL; 2924 } 2925 2926 static PyObject * 2927 listiter_len(listiterobject *it) 2928 { 2929 Py_ssize_t len; 2930 if (it->it_seq) { 2931 len = PyList_GET_SIZE(it->it_seq) - it->it_index; 2932 if (len >= 0) 2933 return PyInt_FromSsize_t(len); 2934 } 2935 return PyInt_FromLong(0); 2936 } 2937 /*********************** List Reverse Iterator **************************/ 2938 2939 typedef struct { 2940 PyObject_HEAD 2941 Py_ssize_t it_index; 2942 PyListObject *it_seq; /* Set to NULL when iterator is exhausted */ 2943 } listreviterobject; 2944 2945 static PyObject *list_reversed(PyListObject *, PyObject *); 2946 static void listreviter_dealloc(listreviterobject *); 2947 static int listreviter_traverse(listreviterobject *, visitproc, void *); 2948 static PyObject *listreviter_next(listreviterobject *); 2949 static PyObject *listreviter_len(listreviterobject *); 2950 2951 static PyMethodDef listreviter_methods[] = { 2952 {"__length_hint__", (PyCFunction)listreviter_len, METH_NOARGS, length_hint_doc}, 2953 {NULL, NULL} /* sentinel */ 2954 }; 2955 2956 PyTypeObject PyListRevIter_Type = { 2957 PyVarObject_HEAD_INIT(&PyType_Type, 0) 2958 "listreverseiterator", /* tp_name */ 2959 sizeof(listreviterobject), /* tp_basicsize */ 2960 0, /* tp_itemsize */ 2961 /* methods */ 2962 (destructor)listreviter_dealloc, /* tp_dealloc */ 2963 0, /* tp_print */ 2964 0, /* tp_getattr */ 2965 0, /* tp_setattr */ 2966 0, /* tp_compare */ 2967 0, /* tp_repr */ 2968 0, /* tp_as_number */ 2969 0, /* tp_as_sequence */ 2970 0, /* tp_as_mapping */ 2971 0, /* tp_hash */ 2972 0, /* tp_call */ 2973 0, /* tp_str */ 2974 PyObject_GenericGetAttr, /* tp_getattro */ 2975 0, /* tp_setattro */ 2976 0, /* tp_as_buffer */ 2977 Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC,/* tp_flags */ 2978 0, /* tp_doc */ 2979 (traverseproc)listreviter_traverse, /* tp_traverse */ 2980 0, /* tp_clear */ 2981 0, /* tp_richcompare */ 2982 0, /* tp_weaklistoffset */ 2983 PyObject_SelfIter, /* tp_iter */ 2984 (iternextfunc)listreviter_next, /* tp_iternext */ 2985 listreviter_methods, /* tp_methods */ 2986 0, 2987 }; 2988 2989 static PyObject * 2990 list_reversed(PyListObject *seq, PyObject *unused) 2991 { 2992 listreviterobject *it; 2993 2994 it = PyObject_GC_New(listreviterobject, &PyListRevIter_Type); 2995 if (it == NULL) 2996 return NULL; 2997 assert(PyList_Check(seq)); 2998 it->it_index = PyList_GET_SIZE(seq) - 1; 2999 Py_INCREF(seq); 3000 it->it_seq = seq; 3001 PyObject_GC_Track(it); 3002 return (PyObject *)it; 3003 } 3004 3005 static void 3006 listreviter_dealloc(listreviterobject *it) 3007 { 3008 PyObject_GC_UnTrack(it); 3009 Py_XDECREF(it->it_seq); 3010 PyObject_GC_Del(it); 3011 } 3012 3013 static int 3014 listreviter_traverse(listreviterobject *it, visitproc visit, void *arg) 3015 { 3016 Py_VISIT(it->it_seq); 3017 return 0; 3018 } 3019 3020 static PyObject * 3021 listreviter_next(listreviterobject *it) 3022 { 3023 PyObject *item; 3024 Py_ssize_t index; 3025 PyListObject *seq; 3026 3027 assert(it != NULL); 3028 seq = it->it_seq; 3029 if (seq == NULL) { 3030 return NULL; 3031 } 3032 assert(PyList_Check(seq)); 3033 3034 index = it->it_index; 3035 if (index>=0 && index < PyList_GET_SIZE(seq)) { 3036 item = PyList_GET_ITEM(seq, index); 3037 it->it_index--; 3038 Py_INCREF(item); 3039 return item; 3040 } 3041 it->it_index = -1; 3042 it->it_seq = NULL; 3043 Py_DECREF(seq); 3044 return NULL; 3045 } 3046 3047 static PyObject * 3048 listreviter_len(listreviterobject *it) 3049 { 3050 Py_ssize_t len = it->it_index + 1; 3051 if (it->it_seq == NULL || PyList_GET_SIZE(it->it_seq) < len) 3052 len = 0; 3053 return PyLong_FromSsize_t(len); 3054 } 3055