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