Objects/listobject.c

   1
   2 /* List object implementation */
   3
   4 #include "Python.h"
   5
   6 #ifdef STDC_HEADERS
   7 #include <stddef.h>
   8 #else
   9 #include <sys/types.h>          /* For size_t */
  10 #endif
  11
  12 static int
  13 roundupsize(int n)
  14 {
  15         unsigned int nbits = 0;
  16         unsigned int n2 = (unsigned int)n >> 5;
  17
  18         /* Round up:
  19          * If n <       256, to a multiple of        8.
  20          * If n <      2048, to a multiple of       64.
  21          * If n <     16384, to a multiple of      512.
  22          * If n <    131072, to a multiple of     4096.
  23          * If n <   1048576, to a multiple of    32768.
  24          * If n <   8388608, to a multiple of   262144.
  25          * If n <  67108864, to a multiple of  2097152.
  26          * If n < 536870912, to a multiple of 16777216.
  27          * ...
  28          * If n < 2**(5+3*i), to a multiple of 2**(3*i).
  29          *
  30          * This over-allocates proportional to the list size, making room
  31          * for additional growth.  The over-allocation is mild, but is
  32          * enough to give linear-time amortized behavior over a long
  33          * sequence of appends() in the presence of a poorly-performing
  34          * system realloc() (which is a reality, e.g., across all flavors
  35          * of Windows, with Win9x behavior being particularly bad -- and
  36          * we've still got address space fragmentation problems on Win9x
  37          * even with this scheme, although it requires much longer lists to
  38          * provoke them than it used to).
  39          */
  40         do {
  41                 n2 >>= 3;
  42                 nbits += 3;
  43         } while (n2);
  44         return ((n >> nbits) + 1) << nbits;
  45  }
  46
  47 #define NRESIZE(var, type, nitems)                              \
  48 do {                                                            \
  49         size_t _new_size = roundupsize(nitems);                 \
  50         if (_new_size <= ((~(size_t)0) / sizeof(type)))         \
  51                 PyMem_RESIZE(var, type, _new_size);             \
  52         else                                                    \
  53                 var = NULL;                                     \
  54 } while (0)
  55
  56 PyObject *
  57 PyList_New(int size)
  58 {
  59         int i;
  60         PyListObject *op;
  61         size_t nbytes;
  62         if (size < 0) {
  63                 PyErr_BadInternalCall();
  64                 return NULL;
  65         }
  66         nbytes = size * sizeof(PyObject *);
  67         /* Check for overflow */
  68         if (nbytes / sizeof(PyObject *) != (size_t)size) {
  69                 return PyErr_NoMemory();
  70         }
  71         op = PyObject_GC_New(PyListObject, &PyList_Type);
  72         if (op == NULL) {
  73                 return NULL;
  74         }
  75         if (size <= 0) {
  76                 op->ob_item = NULL;
  77         }
  78         else {
  79                 op->ob_item = (PyObject **) PyMem_MALLOC(nbytes);
  80                 if (op->ob_item == NULL) {
  81                         return PyErr_NoMemory();
  82                 }
  83         }
  84         op->ob_size = size;
  85         for (i = 0; i < size; i++)
  86                 op->ob_item[i] = NULL;
  87         _PyObject_GC_TRACK(op);
  88         return (PyObject *) op;
  89 }
  90
  91 int
  92 PyList_Size(PyObject *op)
  93 {
  94         if (!PyList_Check(op)) {
  95                 PyErr_BadInternalCall();
  96                 return -1;
  97         }
  98         else
  99                 return ((PyListObject *)op) -> ob_size;
 100 }
 101
 102 static PyObject *indexerr;
 103
 104 PyObject *
 105 PyList_GetItem(PyObject *op, int i)
 106 {
 107         if (!PyList_Check(op)) {
 108                 PyErr_BadInternalCall();
 109                 return NULL;
 110         }
 111         if (i < 0 || i >= ((PyListObject *)op) -> ob_size) {
 112                 if (indexerr == NULL)
 113                         indexerr = PyString_FromString(
 114                                 "list index out of range");
 115                 PyErr_SetObject(PyExc_IndexError, indexerr);
 116                 return NULL;
 117         }
 118         return ((PyListObject *)op) -> ob_item[i];
 119 }
 120
 121 int
 122 PyList_SetItem(register PyObject *op, register int i,
 123                register PyObject *newitem)
 124 {
 125         register PyObject *olditem;
 126         register PyObject **p;
 127         if (!PyList_Check(op)) {
 128                 Py_XDECREF(newitem);
 129                 PyErr_BadInternalCall();
 130                 return -1;
 131         }
 132         if (i < 0 || i >= ((PyListObject *)op) -> ob_size) {
 133                 Py_XDECREF(newitem);
 134                 PyErr_SetString(PyExc_IndexError,
 135                                 "list assignment index out of range");
 136                 return -1;
 137         }
 138         p = ((PyListObject *)op) -> ob_item + i;
 139         olditem = *p;
 140         *p = newitem;
 141         Py_XDECREF(olditem);
 142         return 0;
 143 }
 144
 145 static int
 146 ins1(PyListObject *self, int where, PyObject *v)
 147 {
 148         int i;
 149         PyObject **items;
 150         if (v == NULL) {
 151                 PyErr_BadInternalCall();
 152                 return -1;
 153         }
 154         if (self->ob_size == INT_MAX) {
 155                 PyErr_SetString(PyExc_OverflowError,
 156                         "cannot add more objects to list");
 157                 return -1;
 158         }
 159         items = self->ob_item;
 160         NRESIZE(items, PyObject *, self->ob_size+1);
 161         if (items == NULL) {
 162                 PyErr_NoMemory();
 163                 return -1;
 164         }
 165         if (where < 0)
 166                 where = 0;
 167         if (where > self->ob_size)
 168                 where = self->ob_size;
 169         for (i = self->ob_size; --i >= where; )
 170                 items[i+1] = items[i];
 171         Py_INCREF(v);
 172         items[where] = v;
 173         self->ob_item = items;
 174         self->ob_size++;
 175         return 0;
 176 }
 177
 178 int
 179 PyList_Insert(PyObject *op, int where, PyObject *newitem)
 180 {
 181         if (!PyList_Check(op)) {
 182                 PyErr_BadInternalCall();
 183                 return -1;
 184         }
 185         return ins1((PyListObject *)op, where, newitem);
 186 }
 187
 188 int
 189 PyList_Append(PyObject *op, PyObject *newitem)
 190 {
 191         if (!PyList_Check(op)) {
 192                 PyErr_BadInternalCall();
 193                 return -1;
 194         }
 195         return ins1((PyListObject *)op,
 196                 (int) ((PyListObject *)op)->ob_size, newitem);
 197 }
 198
 199 /* Methods */
 200
 201 static void
 202 list_dealloc(PyListObject *op)
 203 {
 204         int i;
 205         PyObject_GC_UnTrack(op);
 206         Py_TRASHCAN_SAFE_BEGIN(op)
 207         if (op->ob_item != NULL) {
 208                 /* Do it backwards, for Christian Tismer.
 209                    There's a simple test case where somehow this reduces
 210                    thrashing when a *very* large list is created and
 211                    immediately deleted. */
 212                 i = op->ob_size;
 213                 while (--i >= 0) {
 214                         Py_XDECREF(op->ob_item[i]);
 215                 }
 216                 PyMem_FREE(op->ob_item);
 217         }
 218         op->ob_type->tp_free((PyObject *)op);
 219         Py_TRASHCAN_SAFE_END(op)
 220 }
 221
 222 static int
 223 list_print(PyListObject *op, FILE *fp, int flags)
 224 {
 225         int i;
 226
 227         i = Py_ReprEnter((PyObject*)op);
 228         if (i != 0) {
 229                 if (i < 0)
 230                         return i;
 231                 fprintf(fp, "[...]");
 232                 return 0;
 233         }
 234         fprintf(fp, "[");
 235         for (i = 0; i < op->ob_size; i++) {
 236                 if (i > 0)
 237                         fprintf(fp, ", ");
 238                 if (PyObject_Print(op->ob_item[i], fp, 0) != 0) {
 239                         Py_ReprLeave((PyObject *)op);
 240                         return -1;
 241                 }
 242         }
 243         fprintf(fp, "]");
 244         Py_ReprLeave((PyObject *)op);
 245         return 0;
 246 }
 247
 248 static PyObject *
 249 list_repr(PyListObject *v)
 250 {
 251         int i;
 252         PyObject *s, *temp;
 253         PyObject *pieces = NULL, *result = NULL;
 254
 255         i = Py_ReprEnter((PyObject*)v);
 256         if (i != 0) {
 257                 return i > 0 ? PyString_FromString("[...]") : NULL;
 258         }
 259
 260         if (v->ob_size == 0) {
 261                 result = PyString_FromString("[]");
 262                 goto Done;
 263         }
 264
 265         pieces = PyList_New(0);
 266         if (pieces == NULL)
 267                 goto Done;
 268
 269         /* Do repr() on each element.  Note that this may mutate the list,
 270            so must refetch the list size on each iteration. */
 271         for (i = 0; i < v->ob_size; ++i) {
 272                 int status;
 273                 s = PyObject_Repr(v->ob_item[i]);
 274                 if (s == NULL)
 275                         goto Done;
 276                 status = PyList_Append(pieces, s);
 277                 Py_DECREF(s);  /* append created a new ref */
 278                 if (status < 0)
 279                         goto Done;
 280         }
 281
 282         /* Add "[]" decorations to the first and last items. */
 283         assert(PyList_GET_SIZE(pieces) > 0);
 284         s = PyString_FromString("[");
 285         if (s == NULL)
 286                 goto Done;
 287         temp = PyList_GET_ITEM(pieces, 0);
 288         PyString_ConcatAndDel(&s, temp);
 289         PyList_SET_ITEM(pieces, 0, s);
 290         if (s == NULL)
 291                 goto Done;
 292
 293         s = PyString_FromString("]");
 294         if (s == NULL)
 295                 goto Done;
 296         temp = PyList_GET_ITEM(pieces, PyList_GET_SIZE(pieces) - 1);
 297         PyString_ConcatAndDel(&temp, s);
 298         PyList_SET_ITEM(pieces, PyList_GET_SIZE(pieces) - 1, temp);
 299         if (temp == NULL)
 300                 goto Done;
 301
 302         /* Paste them all together with ", " between. */
 303         s = PyString_FromString(", ");
 304         if (s == NULL)
 305                 goto Done;
 306         result = _PyString_Join(s, pieces);
 307         Py_DECREF(s);
 308
 309 Done:
 310         Py_XDECREF(pieces);
 311         Py_ReprLeave((PyObject *)v);
 312         return result;
 313 }
 314
 315 static int
 316 list_length(PyListObject *a)
 317 {
 318         return a->ob_size;
 319 }
 320
 321
 322
 323 static int
 324 list_contains(PyListObject *a, PyObject *el)
 325 {
 326         int i;
 327
 328         for (i = 0; i < a->ob_size; ++i) {
 329                 int cmp = PyObject_RichCompareBool(el, PyList_GET_ITEM(a, i),
 330                                                    Py_EQ);
 331                 if (cmp > 0)
 332                         return 1;
 333                 else if (cmp < 0)
 334                         return -1;
 335         }
 336         return 0;
 337 }
 338
 339
 340 static PyObject *
 341 list_item(PyListObject *a, int i)
 342 {
 343         if (i < 0 || i >= a->ob_size) {
 344                 if (indexerr == NULL)
 345                         indexerr = PyString_FromString(
 346                                 "list index out of range");
 347                 PyErr_SetObject(PyExc_IndexError, indexerr);
 348                 return NULL;
 349         }
 350         Py_INCREF(a->ob_item[i]);
 351         return a->ob_item[i];
 352 }
 353
 354 static PyObject *
 355 list_slice(PyListObject *a, int ilow, int ihigh)
 356 {
 357         PyListObject *np;
 358         int i;
 359         if (ilow < 0)
 360                 ilow = 0;
 361         else if (ilow > a->ob_size)
 362                 ilow = a->ob_size;
 363         if (ihigh < ilow)
 364                 ihigh = ilow;
 365         else if (ihigh > a->ob_size)
 366                 ihigh = a->ob_size;
 367         np = (PyListObject *) PyList_New(ihigh - ilow);
 368         if (np == NULL)
 369                 return NULL;
 370         for (i = ilow; i < ihigh; i++) {
 371                 PyObject *v = a->ob_item[i];
 372                 Py_INCREF(v);
 373                 np->ob_item[i - ilow] = v;
 374         }
 375         return (PyObject *)np;
 376 }
 377
 378 PyObject *
 379 PyList_GetSlice(PyObject *a, int ilow, int ihigh)
 380 {
 381         if (!PyList_Check(a)) {
 382                 PyErr_BadInternalCall();
 383                 return NULL;
 384         }
 385         return list_slice((PyListObject *)a, ilow, ihigh);
 386 }
 387
 388 static PyObject *
 389 list_concat(PyListObject *a, PyObject *bb)
 390 {
 391         int size;
 392         int i;
 393         PyListObject *np;
 394         if (!PyList_Check(bb)) {
 395                 PyErr_Format(PyExc_TypeError,
 396                           "can only concatenate list (not \"%.200s\") to list",
 397                           bb->ob_type->tp_name);
 398                 return NULL;
 399         }
 400 #define b ((PyListObject *)bb)
 401         size = a->ob_size + b->ob_size;
 402         if (size < 0)
 403                 return PyErr_NoMemory();
 404         np = (PyListObject *) PyList_New(size);
 405         if (np == NULL) {
 406                 return NULL;
 407         }
 408         for (i = 0; i < a->ob_size; i++) {
 409                 PyObject *v = a->ob_item[i];
 410                 Py_INCREF(v);
 411                 np->ob_item[i] = v;
 412         }
 413         for (i = 0; i < b->ob_size; i++) {
 414                 PyObject *v = b->ob_item[i];
 415                 Py_INCREF(v);
 416                 np->ob_item[i + a->ob_size] = v;
 417         }
 418         return (PyObject *)np;
 419 #undef b
 420 }
 421
 422 static PyObject *
 423 list_repeat(PyListObject *a, int n)
 424 {
 425         int i, j;
 426         int size;
 427         PyListObject *np;
 428         PyObject **p;
 429         if (n < 0)
 430                 n = 0;
 431         size = a->ob_size * n;
 432         if (n && size/n != a->ob_size)
 433                 return PyErr_NoMemory();
 434         np = (PyListObject *) PyList_New(size);
 435         if (np == NULL)
 436                 return NULL;
 437         p = np->ob_item;
 438         for (i = 0; i < n; i++) {
 439                 for (j = 0; j < a->ob_size; j++) {
 440                         *p = a->ob_item[j];
 441                         Py_INCREF(*p);
 442                         p++;
 443                 }
 444         }
 445         return (PyObject *) np;
 446 }
 447
 448 static int
 449 list_ass_slice(PyListObject *a, int ilow, int ihigh, PyObject *v)
 450 {
 451         /* Because [X]DECREF can recursively invoke list operations on
 452            this list, we must postpone all [X]DECREF activity until
 453            after the list is back in its canonical shape.  Therefore
 454            we must allocate an additional array, 'recycle', into which
 455            we temporarily copy the items that are deleted from the
 456            list. :-( */
 457         PyObject **recycle, **p;
 458         PyObject **item;
 459         int n; /* Size of replacement list */
 460         int d; /* Change in size */
 461         int k; /* Loop index */
 462 #define b ((PyListObject *)v)
 463         if (v == NULL)
 464                 n = 0;
 465         else if (PyList_Check(v)) {
 466                 n = b->ob_size;
 467                 if (a == b) {
 468                         /* Special case "a[i:j] = a" -- copy b first */
 469                         int ret;
 470                         v = list_slice(b, 0, n);
 471                         ret = list_ass_slice(a, ilow, ihigh, v);
 472                         Py_DECREF(v);
 473                         return ret;
 474                 }
 475         }
 476         else {
 477                 PyErr_Format(PyExc_TypeError,
 478                              "must assign list (not \"%.200s\") to slice",
 479                              v->ob_type->tp_name);
 480                 return -1;
 481         }
 482         if (ilow < 0)
 483                 ilow = 0;
 484         else if (ilow > a->ob_size)
 485                 ilow = a->ob_size;
 486         if (ihigh < ilow)
 487                 ihigh = ilow;
 488         else if (ihigh > a->ob_size)
 489                 ihigh = a->ob_size;
 490         item = a->ob_item;
 491         d = n - (ihigh-ilow);
 492         if (ihigh > ilow)
 493                 p = recycle = PyMem_NEW(PyObject *, (ihigh-ilow));
 494         else
 495                 p = recycle = NULL;
 496         if (d <= 0) { /* Delete -d items; recycle ihigh-ilow items */
 497                 for (k = ilow; k < ihigh; k++)
 498                         *p++ = item[k];
 499                 if (d < 0) {
 500                         for (/*k = ihigh*/; k < a->ob_size; k++)
 501                                 item[k+d] = item[k];
 502                         a->ob_size += d;
 503                         NRESIZE(item, PyObject *, a->ob_size); /* Can't fail */
 504                         a->ob_item = item;
 505                 }
 506         }
 507         else { /* Insert d items; recycle ihigh-ilow items */
 508                 NRESIZE(item, PyObject *, a->ob_size + d);
 509                 if (item == NULL) {
 510                         if (recycle != NULL)
 511                                 PyMem_DEL(recycle);
 512                         PyErr_NoMemory();
 513                         return -1;
 514                 }
 515                 for (k = a->ob_size; --k >= ihigh; )
 516                         item[k+d] = item[k];
 517                 for (/*k = ihigh-1*/; k >= ilow; --k)
 518                         *p++ = item[k];
 519                 a->ob_item = item;
 520                 a->ob_size += d;
 521         }
 522         for (k = 0; k < n; k++, ilow++) {
 523                 PyObject *w = b->ob_item[k];
 524                 Py_XINCREF(w);
 525                 item[ilow] = w;
 526         }
 527         if (recycle) {
 528                 while (--p >= recycle)
 529                         Py_XDECREF(*p);
 530                 PyMem_DEL(recycle);
 531         }
 532         if (a->ob_size == 0 && a->ob_item != NULL) {
 533                 PyMem_FREE(a->ob_item);
 534                 a->ob_item = NULL;
 535         }
 536         return 0;
 537 #undef b
 538 }
 539
 540 int
 541 PyList_SetSlice(PyObject *a, int ilow, int ihigh, PyObject *v)
 542 {
 543         if (!PyList_Check(a)) {
 544                 PyErr_BadInternalCall();
 545                 return -1;
 546         }
 547         return list_ass_slice((PyListObject *)a, ilow, ihigh, v);
 548 }
 549
 550 static PyObject *
 551 list_inplace_repeat(PyListObject *self, int n)
 552 {
 553         PyObject **items;
 554         int size, i, j;
 555
 556
 557         size = PyList_GET_SIZE(self);
 558         if (size == 0) {
 559                 Py_INCREF(self);
 560                 return (PyObject *)self;
 561         }
 562
 563         items = self->ob_item;
 564
 565         if (n < 1) {
 566                 self->ob_item = NULL;
 567                 self->ob_size = 0;
 568                 for (i = 0; i < size; i++)
 569                         Py_XDECREF(items[i]);
 570                 PyMem_DEL(items);
 571                 Py_INCREF(self);
 572                 return (PyObject *)self;
 573         }
 574
 575         NRESIZE(items, PyObject*, size*n);
 576         if (items == NULL) {
 577                 PyErr_NoMemory();
 578                 goto finally;
 579         }
 580         self->ob_item = items;
 581         for (i = 1; i < n; i++) { /* Start counting at 1, not 0 */
 582                 for (j = 0; j < size; j++) {
 583                         PyObject *o = PyList_GET_ITEM(self, j);
 584                         Py_INCREF(o);
 585                         PyList_SET_ITEM(self, self->ob_size++, o);
 586                 }
 587         }
 588         Py_INCREF(self);
 589         return (PyObject *)self;
 590   finally:
 591         return NULL;
 592 }
 593
 594 static int
 595 list_ass_item(PyListObject *a, int i, PyObject *v)
 596 {
 597         PyObject *old_value;
 598         if (i < 0 || i >= a->ob_size) {
 599                 PyErr_SetString(PyExc_IndexError,
 600                                 "list assignment index out of range");
 601                 return -1;
 602         }
 603         if (v == NULL)
 604                 return list_ass_slice(a, i, i+1, v);
 605         Py_INCREF(v);
 606         old_value = a->ob_item[i];
 607         a->ob_item[i] = v;
 608         Py_DECREF(old_value);
 609         return 0;
 610 }
 611
 612 static PyObject *
 613 ins(PyListObject *self, int where, PyObject *v)
 614 {
 615         if (ins1(self, where, v) != 0)
 616                 return NULL;
 617         Py_INCREF(Py_None);
 618         return Py_None;
 619 }
 620
 621 static PyObject *
 622 listinsert(PyListObject *self, PyObject *args)
 623 {
 624         int i;
 625         PyObject *v;
 626         if (!PyArg_ParseTuple(args, "iO:insert", &i, &v))
 627                 return NULL;
 628         return ins(self, i, v);
 629 }
 630
 631 static PyObject *
 632 listappend(PyListObject *self, PyObject *v)
 633 {
 634         return ins(self, (int) self->ob_size, v);
 635 }
 636
 637 static int
 638 listextend_internal(PyListObject *self, PyObject *b)
 639 {
 640         PyObject **items;
 641         int selflen = PyList_GET_SIZE(self);
 642         int blen;
 643         register int i;
 644
 645         if (PyObject_Size(b) == 0) {
 646                 /* short circuit when b is empty */
 647                 Py_DECREF(b);
 648                 return 0;
 649         }
 650
 651         if (self == (PyListObject*)b) {
 652                 /* as in list_ass_slice() we must special case the
 653                  * situation: a.extend(a)
 654                  *
 655                  * XXX: I think this way ought to be faster than using
 656                  * list_slice() the way list_ass_slice() does.
 657                  */
 658                 Py_DECREF(b);
 659                 b = PyList_New(selflen);
 660                 if (!b)
 661                         return -1;
 662                 for (i = 0; i < selflen; i++) {
 663                         PyObject *o = PyList_GET_ITEM(self, i);
 664                         Py_INCREF(o);
 665                         PyList_SET_ITEM(b, i, o);
 666                 }
 667         }
 668
 669         blen = PyObject_Size(b);
 670
 671         /* resize a using idiom */
 672         items = self->ob_item;
 673         NRESIZE(items, PyObject*, selflen + blen);
 674         if (items == NULL) {
 675                 PyErr_NoMemory();
 676                 Py_DECREF(b);
 677                 return -1;
 678         }
 679
 680         self->ob_item = items;
 681
 682         /* populate the end of self with b's items */
 683         for (i = 0; i < blen; i++) {
 684                 PyObject *o = PySequence_Fast_GET_ITEM(b, i);
 685                 Py_INCREF(o);
 686                 PyList_SET_ITEM(self, self->ob_size++, o);
 687         }
 688         Py_DECREF(b);
 689         return 0;
 690 }
 691
 692
 693 static PyObject *
 694 list_inplace_concat(PyListObject *self, PyObject *other)
 695 {
 696         other = PySequence_Fast(other, "argument to += must be iterable");
 697         if (!other)
 698                 return NULL;
 699
 700         if (listextend_internal(self, other) < 0)
 701                 return NULL;
 702
 703         Py_INCREF(self);
 704         return (PyObject *)self;
 705 }
 706
 707 static PyObject *
 708 listextend(PyListObject *self, PyObject *b)
 709 {
 710
 711         b = PySequence_Fast(b, "list.extend() argument must be iterable");
 712         if (!b)
 713                 return NULL;
 714
 715         if (listextend_internal(self, b) < 0)
 716                 return NULL;
 717
 718         Py_INCREF(Py_None);
 719         return Py_None;
 720 }
 721
 722 static PyObject *
 723 listpop(PyListObject *self, PyObject *args)
 724 {
 725         int i = -1;
 726         PyObject *v;
 727         if (!PyArg_ParseTuple(args, "|i:pop", &i))
 728                 return NULL;
 729         if (self->ob_size == 0) {
 730                 /* Special-case most common failure cause */
 731                 PyErr_SetString(PyExc_IndexError, "pop from empty list");
 732                 return NULL;
 733         }
 734         if (i < 0)
 735                 i += self->ob_size;
 736         if (i < 0 || i >= self->ob_size) {
 737                 PyErr_SetString(PyExc_IndexError, "pop index out of range");
 738                 return NULL;
 739         }
 740         v = self->ob_item[i];
 741         Py_INCREF(v);
 742         if (list_ass_slice(self, i, i+1, (PyObject *)NULL) != 0) {
 743                 Py_DECREF(v);
 744                 return NULL;
 745         }
 746         return v;
 747 }
 748
 749 /* New quicksort implementation for arrays of object pointers.
 750    Thanks to discussions with Tim Peters. */
 751
 752 /* CMPERROR is returned by our comparison function when an error
 753    occurred.  This is the largest negative integer (0x80000000 on a
 754    32-bit system). */
 755 #define CMPERROR ( (int) ((unsigned int)1 << (8*sizeof(int) - 1)) )
 756
 757 /* Comparison function.  Takes care of calling a user-supplied
 758    comparison function (any callable Python object).  Calls the
 759    standard comparison function, PyObject_Compare(), if the user-
 760    supplied function is NULL. */
 761
 762 static int
 763 docompare(PyObject *x, PyObject *y, PyObject *compare)
 764 {
 765         PyObject *args, *res;
 766         int i;
 767
 768         if (compare == NULL) {
 769                 /* NOTE: we rely on the fact here that the sorting algorithm
 770                    only ever checks whether k<0, i.e., whether x<y.  So we
 771                    invoke the rich comparison function with Py_LT ('<'), and
 772                    return -1 when it returns true and 0 when it returns
 773                    false. */
 774                 i = PyObject_RichCompareBool(x, y, Py_LT);
 775                 if (i < 0)
 776                         return CMPERROR;
 777                 else
 778                         return -i;
 779         }
 780
 781         args = Py_BuildValue("(OO)", x, y);
 782         if (args == NULL)
 783                 return CMPERROR;
 784         res = PyEval_CallObject(compare, args);
 785         Py_DECREF(args);
 786         if (res == NULL)
 787                 return CMPERROR;
 788         if (!PyInt_Check(res)) {
 789                 Py_DECREF(res);
 790                 PyErr_SetString(PyExc_TypeError,
 791                                 "comparison function must return int");
 792                 return CMPERROR;
 793         }
 794         i = PyInt_AsLong(res);
 795         Py_DECREF(res);
 796         if (i < 0)
 797                 return -1;
 798         if (i > 0)
 799                 return 1;
 800         return 0;
 801 }
 802
 803 /* MINSIZE is the smallest array that will get a full-blown samplesort
 804    treatment; smaller arrays are sorted using binary insertion.  It must
 805    be at least 7 for the samplesort implementation to work.  Binary
 806    insertion does fewer compares, but can suffer O(N**2) data movement.
 807    The more expensive compares, the larger MINSIZE should be. */
 808 #define MINSIZE 100
 809
 810 /* MINPARTITIONSIZE is the smallest array slice samplesort will bother to
 811    partition; smaller slices are passed to binarysort.  It must be at
 812    least 2, and no larger than MINSIZE.  Setting it higher reduces the #
 813    of compares slowly, but increases the amount of data movement quickly.
 814    The value here was chosen assuming a compare costs ~25x more than
 815    swapping a pair of memory-resident pointers -- but under that assumption,
 816    changing the value by a few dozen more or less has aggregate effect
 817    under 1%.  So the value is crucial, but not touchy <wink>. */
 818 #define MINPARTITIONSIZE 40
 819
 820 /* MAXMERGE is the largest number of elements we'll always merge into
 821    a known-to-be sorted chunk via binary insertion, regardless of the
 822    size of that chunk.  Given a chunk of N sorted elements, and a group
 823    of K unknowns, the largest K for which it's better to do insertion
 824    (than a full-blown sort) is a complicated function of N and K mostly
 825    involving the expected number of compares and data moves under each
 826    approach, and the relative cost of those operations on a specific
 827    architecure.  The fixed value here is conservative, and should be a
 828    clear win regardless of architecture or N. */
 829 #define MAXMERGE 15
 830
 831 /* STACKSIZE is the size of our work stack.  A rough estimate is that
 832    this allows us to sort arrays of size N where
 833    N / ln(N) = MINPARTITIONSIZE * 2**STACKSIZE, so 60 is more than enough
 834    for arrays of size 2**64.  Because we push the biggest partition
 835    first, the worst case occurs when all subarrays are always partitioned
 836    exactly in two. */
 837 #define STACKSIZE 60
 838
 839
 840 #define SETK(X,Y) if ((k = docompare(X,Y,compare))==CMPERROR) goto fail
 841
 842 /* binarysort is the best method for sorting small arrays: it does
 843    few compares, but can do data movement quadratic in the number of
 844    elements.
 845    [lo, hi) is a contiguous slice of a list, and is sorted via
 846    binary insertion.
 847    On entry, must have lo <= start <= hi, and that [lo, start) is already
 848    sorted (pass start == lo if you don't know!).
 849    If docompare complains (returns CMPERROR) return -1, else 0.
 850    Even in case of error, the output slice will be some permutation of
 851    the input (nothing is lost or duplicated).
 852 */
 853
 854 static int
 855 binarysort(PyObject **lo, PyObject **hi, PyObject **start, PyObject *compare)
 856      /* compare -- comparison function object, or NULL for default */
 857 {
 858         /* assert lo <= start <= hi
 859            assert [lo, start) is sorted */
 860         register int k;
 861         register PyObject **l, **p, **r;
 862         register PyObject *pivot;
 863
 864         if (lo == start)
 865                 ++start;
 866         for (; start < hi; ++start) {
 867                 /* set l to where *start belongs */
 868                 l = lo;
 869                 r = start;
 870                 pivot = *r;
 871                 do {
 872                         p = l + ((r - l) >> 1);
 873                         SETK(pivot, *p);
 874                         if (k < 0)
 875                                 r = p;
 876                         else
 877                                 l = p + 1;
 878                 } while (l < r);
 879                 /* Pivot should go at l -- slide over to make room.
 880                    Caution: using memmove is much slower under MSVC 5;
 881                    we're not usually moving many slots. */
 882                 for (p = start; p > l; --p)
 883                         *p = *(p-1);
 884                 *l = pivot;
 885         }
 886         return 0;
 887
 888  fail:
 889         return -1;
 890 }
 891
 892 /* samplesortslice is the sorting workhorse.
 893    [lo, hi) is a contiguous slice of a list, to be sorted in place.
 894    On entry, must have lo <= hi,
 895    If docompare complains (returns CMPERROR) return -1, else 0.
 896    Even in case of error, the output slice will be some permutation of
 897    the input (nothing is lost or duplicated).
 898
 899    samplesort is basically quicksort on steroids:  a power of 2 close
 900    to n/ln(n) is computed, and that many elements (less 1) are picked at
 901    random from the array and sorted.  These 2**k - 1 elements are then
 902    used as preselected pivots for an equal number of quicksort
 903    partitioning steps, partitioning the slice into 2**k chunks each of
 904    size about ln(n).  These small final chunks are then usually handled
 905    by binarysort.  Note that when k=1, this is roughly the same as an
 906    ordinary quicksort using a random pivot, and when k=2 this is roughly
 907    a median-of-3 quicksort.  From that view, using k ~= lg(n/ln(n)) makes
 908    this a "median of n/ln(n)" quicksort.  You can also view it as a kind
 909    of bucket sort, where 2**k-1 bucket boundaries are picked dynamically.
 910
 911    The large number of samples makes a quadratic-time case almost
 912    impossible, and asymptotically drives the average-case number of
 913    compares from quicksort's 2 N ln N (or 12/7 N ln N for the median-of-
 914    3 variant) down to N lg N.
 915
 916    We also play lots of low-level tricks to cut the number of compares.
 917
 918    Very obscure:  To avoid using extra memory, the PPs are stored in the
 919    array and shuffled around as partitioning proceeds.  At the start of a
 920    partitioning step, we'll have 2**m-1 (for some m) PPs in sorted order,
 921    adjacent (either on the left or the right!) to a chunk of X elements
 922    that are to be partitioned: P X or X P.  In either case we need to
 923    shuffle things *in place* so that the 2**(m-1) smaller PPs are on the
 924    left, followed by the PP to be used for this step (that's the middle
 925    of the PPs), followed by X, followed by the 2**(m-1) larger PPs:
 926        P X or X P -> Psmall pivot X Plarge
 927    and the order of the PPs must not be altered.  It can take a while
 928    to realize this isn't trivial!  It can take even longer <wink> to
 929    understand why the simple code below works, using only 2**(m-1) swaps.
 930    The key is that the order of the X elements isn't necessarily
 931    preserved:  X can end up as some cyclic permutation of its original
 932    order.  That's OK, because X is unsorted anyway.  If the order of X
 933    had to be preserved too, the simplest method I know of using O(1)
 934    scratch storage requires len(X) + 2**(m-1) swaps, spread over 2 passes.
 935    Since len(X) is typically several times larger than 2**(m-1), that
 936    would slow things down.
 937 */
 938
 939 struct SamplesortStackNode {
 940         /* Represents a slice of the array, from (& including) lo up
 941            to (but excluding) hi.  "extra" additional & adjacent elements
 942            are pre-selected pivots (PPs), spanning [lo-extra, lo) if
 943            extra > 0, or [hi, hi-extra) if extra < 0.  The PPs are
 944            already sorted, but nothing is known about the other elements
 945            in [lo, hi). |extra| is always one less than a power of 2.
 946            When extra is 0, we're out of PPs, and the slice must be
 947            sorted by some other means. */
 948         PyObject **lo;
 949         PyObject **hi;
 950         int extra;
 951 };
 952
 953 /* The number of PPs we want is 2**k - 1, where 2**k is as close to
 954    N / ln(N) as possible.  So k ~= lg(N / ln(N)).  Calling libm routines
 955    is undesirable, so cutoff values are canned in the "cutoff" table
 956    below:  cutoff[i] is the smallest N such that k == CUTOFFBASE + i. */
 957 #define CUTOFFBASE 4
 958 static long cutoff[] = {
 959         43,        /* smallest N such that k == 4 */
 960         106,       /* etc */
 961         250,
 962         576,
 963         1298,
 964         2885,
 965         6339,
 966         13805,
 967         29843,
 968         64116,
 969         137030,
 970         291554,
 971         617916,
 972         1305130,
 973         2748295,
 974         5771662,
 975         12091672,
 976         25276798,
 977         52734615,
 978         109820537,
 979         228324027,
 980         473977813,
 981         982548444,   /* smallest N such that k == 26 */
 982         2034159050   /* largest N that fits in signed 32-bit; k == 27 */
 983 };
 984
 985 static int
 986 samplesortslice(PyObject **lo, PyObject **hi, PyObject *compare)
 987      /* compare -- comparison function object, or NULL for default */
 988 {
 989         register PyObject **l, **r;
 990         register PyObject *tmp, *pivot;
 991         register int k;
 992         int n, extra, top, extraOnRight;
 993         struct SamplesortStackNode stack[STACKSIZE];
 994
 995         /* assert lo <= hi */
 996         n = hi - lo;
 997
 998         /* ----------------------------------------------------------
 999          * Special cases
1000          * --------------------------------------------------------*/
1001         if (n < 2)
1002                 return 0;
1003
1004         /* Set r to the largest value such that [lo,r) is sorted.
1005            This catches the already-sorted case, the all-the-same
1006            case, and the appended-a-few-elements-to-a-sorted-list case.
1007            If the array is unsorted, we're very likely to get out of
1008            the loop fast, so the test is cheap if it doesn't pay off.
1009         */
1010         /* assert lo < hi */
1011         for (r = lo+1; r < hi; ++r) {
1012                 SETK(*r, *(r-1));
1013                 if (k < 0)
1014                         break;
1015         }
1016         /* [lo,r) is sorted, [r,hi) unknown.  Get out cheap if there are
1017            few unknowns, or few elements in total. */
1018         if (hi - r <= MAXMERGE || n < MINSIZE)
1019                 return binarysort(lo, hi, r, compare);
1020
1021         /* Check for the array already being reverse-sorted.  Typical
1022            benchmark-driven silliness <wink>. */
1023         /* assert lo < hi */
1024         for (r = lo+1; r < hi; ++r) {
1025                 SETK(*(r-1), *r);
1026                 if (k < 0)
1027                         break;
1028         }
1029         if (hi - r <= MAXMERGE) {
1030                 /* Reverse the reversed prefix, then insert the tail */
1031                 PyObject **originalr = r;
1032                 l = lo;
1033                 do {
1034                         --r;
1035                         tmp = *l; *l = *r; *r = tmp;
1036                         ++l;
1037                 } while (l < r);
1038                 return binarysort(lo, hi, originalr, compare);
1039         }
1040
1041         /* ----------------------------------------------------------
1042          * Normal case setup: a large array without obvious pattern.
1043          * --------------------------------------------------------*/
1044
1045         /* extra := a power of 2 ~= n/ln(n), less 1.
1046            First find the smallest extra s.t. n < cutoff[extra] */
1047         for (extra = 0;
1048              extra < sizeof(cutoff) / sizeof(cutoff[0]);
1049              ++extra) {
1050                 if (n < cutoff[extra])
1051                         break;
1052                 /* note that if we fall out of the loop, the value of
1053                    extra still makes *sense*, but may be smaller than
1054                    we would like (but the array has more than ~= 2**31
1055                    elements in this case!) */
1056         }
1057         /* Now k == extra - 1 + CUTOFFBASE.  The smallest value k can
1058            have is CUTOFFBASE-1, so
1059            assert MINSIZE >= 2**(CUTOFFBASE-1) - 1 */
1060         extra = (1 << (extra - 1 + CUTOFFBASE)) - 1;
1061         /* assert extra > 0 and n >= extra */
1062
1063         /* Swap that many values to the start of the array.  The
1064            selection of elements is pseudo-random, but the same on
1065            every run (this is intentional! timing algorithm changes is
1066            a pain if timing varies across runs).  */
1067         {
1068                 unsigned int seed = n / extra;  /* arbitrary */
1069                 unsigned int i;
1070                 for (i = 0; i < (unsigned)extra; ++i) {
1071                         /* j := random int in [i, n) */
1072                         unsigned int j;
1073                         seed = seed * 69069 + 7;
1074                         j = i + seed % (n - i);
1075                         tmp = lo[i]; lo[i] = lo[j]; lo[j] = tmp;
1076                 }
1077         }
1078
1079         /* Recursively sort the preselected pivots. */
1080         if (samplesortslice(lo, lo + extra, compare) < 0)
1081                 goto fail;
1082
1083         top = 0;          /* index of available stack slot */
1084         lo += extra;      /* point to first unknown */
1085         extraOnRight = 0; /* the PPs are at the left end */
1086
1087         /* ----------------------------------------------------------
1088          * Partition [lo, hi), and repeat until out of work.
1089          * --------------------------------------------------------*/
1090         for (;;) {
1091                 /* assert lo <= hi, so n >= 0 */
1092                 n = hi - lo;
1093
1094                 /* We may not want, or may not be able, to partition:
1095                    If n is small, it's quicker to insert.
1096                    If extra is 0, we're out of pivots, and *must* use
1097                    another method.
1098                 */
1099                 if (n < MINPARTITIONSIZE || extra == 0) {
1100                         if (n >= MINSIZE) {
1101                                 /* assert extra == 0
1102                                    This is rare, since the average size
1103                                    of a final block is only about
1104                                    ln(original n). */
1105                                 if (samplesortslice(lo, hi, compare) < 0)
1106                                         goto fail;
1107                         }
1108                         else {
1109                                 /* Binary insertion should be quicker,
1110                                    and we can take advantage of the PPs
1111                                    already being sorted. */
1112                                 if (extraOnRight && extra) {
1113                                         /* swap the PPs to the left end */
1114                                         k = extra;
1115                                         do {
1116                                                 tmp = *lo;
1117                                                 *lo = *hi;
1118                                                 *hi = tmp;
1119                                                 ++lo; ++hi;
1120                                         } while (--k);
1121                                 }
1122                                 if (binarysort(lo - extra, hi, lo,
1123                                                compare) < 0)
1124                                         goto fail;
1125                         }
1126
1127                         /* Find another slice to work on. */
1128                         if (--top < 0)
1129                                 break;   /* no more -- done! */
1130                         lo = stack[top].lo;
1131                         hi = stack[top].hi;
1132                         extra = stack[top].extra;
1133                         extraOnRight = 0;
1134                         if (extra < 0) {
1135                                 extraOnRight = 1;
1136                                 extra = -extra;
1137                         }
1138                         continue;
1139                 }
1140
1141                 /* Pretend the PPs are indexed 0, 1, ..., extra-1.
1142                    Then our preselected pivot is at (extra-1)/2, and we
1143                    want to move the PPs before that to the left end of
1144                    the slice, and the PPs after that to the right end.
1145                    The following section changes extra, lo, hi, and the
1146                    slice such that:
1147                    [lo-extra, lo) contains the smaller PPs.
1148                    *lo == our PP.
1149                    (lo, hi) contains the unknown elements.
1150                    [hi, hi+extra) contains the larger PPs.
1151                 */
1152                 k = extra >>= 1;  /* num PPs to move */
1153                 if (extraOnRight) {
1154                         /* Swap the smaller PPs to the left end.
1155                            Note that this loop actually moves k+1 items:
1156                            the last is our PP */
1157                         do {
1158                                 tmp = *lo; *lo = *hi; *hi = tmp;
1159                                 ++lo; ++hi;
1160                         } while (k--);
1161                 }
1162                 else {
1163                         /* Swap the larger PPs to the right end. */
1164                         while (k--) {
1165                                 --lo; --hi;
1166                                 tmp = *lo; *lo = *hi; *hi = tmp;
1167                         }
1168                 }
1169                 --lo;   /* *lo is now our PP */
1170                 pivot = *lo;
1171
1172                 /* Now an almost-ordinary quicksort partition step.
1173                    Note that most of the time is spent here!
1174                    Only odd thing is that we partition into < and >=,
1175                    instead of the usual <= and >=.  This helps when
1176                    there are lots of duplicates of different values,
1177                    because it eventually tends to make subfiles
1178                    "pure" (all duplicates), and we special-case for
1179                    duplicates later. */
1180                 l = lo + 1;
1181                 r = hi - 1;
1182                 /* assert lo < l < r < hi (small n weeded out above) */
1183
1184                 do {
1185                         /* slide l right, looking for key >= pivot */
1186                         do {
1187                                 SETK(*l, pivot);
1188                                 if (k < 0)
1189                                         ++l;
1190                                 else
1191                                         break;
1192                         } while (l < r);
1193
1194                         /* slide r left, looking for key < pivot */
1195                         while (l < r) {
1196                                 register PyObject *rval = *r--;
1197                                 SETK(rval, pivot);
1198                                 if (k < 0) {
1199                                         /* swap and advance */
1200                                         r[1] = *l;
1201                                         *l++ = rval;
1202                                         break;
1203                                 }
1204                         }
1205
1206                 } while (l < r);
1207
1208                 /* assert lo < r <= l < hi
1209                    assert r == l or r+1 == l
1210                    everything to the left of l is < pivot, and
1211                    everything to the right of r is >= pivot */
1212
1213                 if (l == r) {
1214                         SETK(*r, pivot);
1215                         if (k < 0)
1216                                 ++l;
1217                         else
1218                                 --r;
1219                 }
1220                 /* assert lo <= r and r+1 == l and l <= hi
1221                    assert r == lo or a[r] < pivot
1222                    assert a[lo] is pivot
1223                    assert l == hi or a[l] >= pivot
1224                    Swap the pivot into "the middle", so we can henceforth
1225                    ignore it.
1226                 */
1227                 *lo = *r;
1228                 *r = pivot;
1229
1230                 /* The following is true now, & will be preserved:
1231                    All in [lo,r) are < pivot
1232                    All in [r,l) == pivot (& so can be ignored)
1233                    All in [l,hi) are >= pivot */
1234
1235                 /* Check for duplicates of the pivot.  One compare is
1236                    wasted if there are no duplicates, but can win big
1237                    when there are.
1238                    Tricky: we're sticking to "<" compares, so deduce
1239                    equality indirectly.  We know pivot <= *l, so they're
1240                    equal iff not pivot < *l.
1241                 */
1242                 while (l < hi) {
1243                         /* pivot <= *l known */
1244                         SETK(pivot, *l);
1245                         if (k < 0)
1246                                 break;
1247                         else
1248                                 /* <= and not < implies == */
1249                                 ++l;
1250                 }
1251
1252                 /* assert lo <= r < l <= hi
1253                    Partitions are [lo, r) and [l, hi) */
1254
1255                 /* push fattest first; remember we still have extra PPs
1256                    to the left of the left chunk and to the right of
1257                    the right chunk! */
1258                 /* assert top < STACKSIZE */
1259                 if (r - lo <= hi - l) {
1260                         /* second is bigger */
1261                         stack[top].lo = l;
1262                         stack[top].hi = hi;
1263                         stack[top].extra = -extra;
1264                         hi = r;
1265                         extraOnRight = 0;
1266                 }
1267                 else {
1268                         /* first is bigger */
1269                         stack[top].lo = lo;
1270                         stack[top].hi = r;
1271                         stack[top].extra = extra;
1272                         lo = l;
1273                         extraOnRight = 1;
1274                 }
1275                 ++top;
1276
1277         }   /* end of partitioning loop */
1278
1279         return 0;
1280
1281  fail:
1282         return -1;
1283 }
1284
1285 #undef SETK
1286
1287 staticforward PyTypeObject immutable_list_type;
1288
1289 static PyObject *
1290 listsort(PyListObject *self, PyObject *args)
1291 {
1292         int err;
1293         PyObject *compare = NULL;
1294         PyTypeObject *savetype;
1295
1296         if (args != NULL) {
1297                 if (!PyArg_ParseTuple(args, "|O:sort", &compare))
1298                         return NULL;
1299         }
1300         savetype = self->ob_type;
1301         self->ob_type = &immutable_list_type;
1302         err = samplesortslice(self->ob_item,
1303                               self->ob_item + self->ob_size,
1304                               compare);
1305         self->ob_type = savetype;
1306         if (err < 0)
1307                 return NULL;
1308         Py_INCREF(Py_None);
1309         return Py_None;
1310 }
1311
1312 int
1313 PyList_Sort(PyObject *v)
1314 {
1315         if (v == NULL || !PyList_Check(v)) {
1316                 PyErr_BadInternalCall();
1317                 return -1;
1318         }
1319         v = listsort((PyListObject *)v, (PyObject *)NULL);
1320         if (v == NULL)
1321                 return -1;
1322         Py_DECREF(v);
1323         return 0;
1324 }
1325
1326 static void
1327 _listreverse(PyListObject *self)
1328 {
1329         register PyObject **p, **q;
1330         register PyObject *tmp;
1331
1332         if (self->ob_size > 1) {
1333                 for (p = self->ob_item, q = self->ob_item + self->ob_size - 1;
1334                      p < q;
1335                      p++, q--)
1336                 {
1337                         tmp = *p;
1338                         *p = *q;
1339                         *q = tmp;
1340                 }
1341         }
1342 }
1343
1344 static PyObject *
1345 listreverse(PyListObject *self)
1346 {
1347         _listreverse(self);
1348         Py_INCREF(Py_None);
1349         return Py_None;
1350 }
1351
1352 int
1353 PyList_Reverse(PyObject *v)
1354 {
1355         if (v == NULL || !PyList_Check(v)) {
1356                 PyErr_BadInternalCall();
1357                 return -1;
1358         }
1359         _listreverse((PyListObject *)v);
1360         return 0;
1361 }
1362
1363 PyObject *
1364 PyList_AsTuple(PyObject *v)
1365 {
1366         PyObject *w;
1367         PyObject **p;
1368         int n;
1369         if (v == NULL || !PyList_Check(v)) {
1370                 PyErr_BadInternalCall();
1371                 return NULL;
1372         }
1373         n = ((PyListObject *)v)->ob_size;
1374         w = PyTuple_New(n);
1375         if (w == NULL)
1376                 return NULL;
1377         p = ((PyTupleObject *)w)->ob_item;
1378         memcpy((void *)p,
1379                (void *)((PyListObject *)v)->ob_item,
1380                n*sizeof(PyObject *));
1381         while (--n >= 0) {
1382                 Py_INCREF(*p);
1383                 p++;
1384         }
1385         return w;
1386 }
1387
1388 static PyObject *
1389 listindex(PyListObject *self, PyObject *v)
1390 {
1391         int i;
1392
1393         for (i = 0; i < self->ob_size; i++) {
1394                 int cmp = PyObject_RichCompareBool(self->ob_item[i], v, Py_EQ);
1395                 if (cmp > 0)
1396                         return PyInt_FromLong((long)i);
1397                 else if (cmp < 0)
1398                         return NULL;
1399         }
1400         PyErr_SetString(PyExc_ValueError, "list.index(x): x not in list");
1401         return NULL;
1402 }
1403
1404 static PyObject *
1405 listcount(PyListObject *self, PyObject *v)
1406 {
1407         int count = 0;
1408         int i;
1409
1410         for (i = 0; i < self->ob_size; i++) {
1411                 int cmp = PyObject_RichCompareBool(self->ob_item[i], v, Py_EQ);
1412                 if (cmp > 0)
1413                         count++;
1414                 else if (cmp < 0)
1415                         return NULL;
1416         }
1417         return PyInt_FromLong((long)count);
1418 }
1419
1420 static PyObject *
1421 listremove(PyListObject *self, PyObject *v)
1422 {
1423         int i;
1424
1425         for (i = 0; i < self->ob_size; i++) {
1426                 int cmp = PyObject_RichCompareBool(self->ob_item[i], v, Py_EQ);
1427                 if (cmp > 0) {
1428                         if (list_ass_slice(self, i, i+1,
1429                                            (PyObject *)NULL) != 0)
1430                                 return NULL;
1431                         Py_INCREF(Py_None);
1432                         return Py_None;
1433                 }
1434                 else if (cmp < 0)
1435                         return NULL;
1436         }
1437         PyErr_SetString(PyExc_ValueError, "list.remove(x): x not in list");
1438         return NULL;
1439 }
1440
1441 static int
1442 list_traverse(PyListObject *o, visitproc visit, void *arg)
1443 {
1444         int i, err;
1445         PyObject *x;
1446
1447         for (i = o->ob_size; --i >= 0; ) {
1448                 x = o->ob_item[i];
1449                 if (x != NULL) {
1450                         err = visit(x, arg);
1451                         if (err)
1452                                 return err;
1453                 }
1454         }
1455         return 0;
1456 }
1457
1458 static int
1459 list_clear(PyListObject *lp)
1460 {
1461         (void) PyList_SetSlice((PyObject *)lp, 0, lp->ob_size, 0);
1462         return 0;
1463 }
1464
1465 static PyObject *
1466 list_richcompare(PyObject *v, PyObject *w, int op)
1467 {
1468         PyListObject *vl, *wl;
1469         int i;
1470
1471         if (!PyList_Check(v) || !PyList_Check(w)) {
1472                 Py_INCREF(Py_NotImplemented);
1473                 return Py_NotImplemented;
1474         }
1475
1476         vl = (PyListObject *)v;
1477         wl = (PyListObject *)w;
1478
1479         if (vl->ob_size != wl->ob_size && (op == Py_EQ || op == Py_NE)) {
1480                 /* Shortcut: if the lengths differ, the lists differ */
1481                 PyObject *res;
1482                 if (op == Py_EQ)
1483                         res = Py_False;
1484                 else
1485                         res = Py_True;
1486                 Py_INCREF(res);
1487                 return res;
1488         }
1489
1490         /* Search for the first index where items are different */
1491         for (i = 0; i < vl->ob_size && i < wl->ob_size; i++) {
1492                 int k = PyObject_RichCompareBool(vl->ob_item[i],
1493                                                  wl->ob_item[i], Py_EQ);
1494                 if (k < 0)
1495                         return NULL;
1496                 if (!k)
1497                         break;
1498         }
1499
1500         if (i >= vl->ob_size || i >= wl->ob_size) {
1501                 /* No more items to compare -- compare sizes */
1502                 int vs = vl->ob_size;
1503                 int ws = wl->ob_size;
1504                 int cmp;
1505                 PyObject *res;
1506                 switch (op) {
1507                 case Py_LT: cmp = vs <  ws; break;
1508                 case Py_LE: cmp = vs <= ws; break;
1509                 case Py_EQ: cmp = vs == ws; break;
1510                 case Py_NE: cmp = vs != ws; break;
1511                 case Py_GT: cmp = vs >  ws; break;
1512                 case Py_GE: cmp = vs >= ws; break;
1513                 default: return NULL; /* cannot happen */
1514                 }
1515                 if (cmp)
1516                         res = Py_True;
1517                 else
1518                         res = Py_False;
1519                 Py_INCREF(res);
1520                 return res;
1521         }
1522
1523         /* We have an item that differs -- shortcuts for EQ/NE */
1524         if (op == Py_EQ) {
1525                 Py_INCREF(Py_False);
1526                 return Py_False;
1527         }
1528         if (op == Py_NE) {
1529                 Py_INCREF(Py_True);
1530                 return Py_True;
1531         }
1532
1533         /* Compare the final item again using the proper operator */
1534         return PyObject_RichCompare(vl->ob_item[i], wl->ob_item[i], op);
1535 }
1536
1537 /* Adapted from newer code by Tim */
1538 static int
1539 list_fill(PyListObject *result, PyObject *v)
1540 {
1541         PyObject *it;      /* iter(v) */
1542         int n;             /* guess for result list size */
1543         int i;
1544
1545         n = result->ob_size;
1546
1547         /* Special-case list(a_list), for speed. */
1548         if (PyList_Check(v)) {
1549                 if (v == (PyObject *)result)
1550                         return 0; /* source is destination, we're done */
1551                 return list_ass_slice(result, 0, n, v);
1552         }
1553
1554         /* Empty previous contents */
1555         if (n != 0) {
1556                 if (list_ass_slice(result, 0, n, (PyObject *)NULL) != 0)
1557                         return -1;
1558         }
1559
1560         /* Get iterator.  There may be some low-level efficiency to be gained
1561          * by caching the tp_iternext slot instead of using PyIter_Next()
1562          * later, but premature optimization is the root etc.
1563          */
1564         it = PyObject_GetIter(v);
1565         if (it == NULL)
1566                 return -1;
1567
1568         /* Guess a result list size. */
1569         n = -1;  /* unknown */
1570         if (PySequence_Check(v) &&
1571             v->ob_type->tp_as_sequence->sq_length) {
1572                 n = PySequence_Size(v);
1573                 if (n < 0)
1574                         PyErr_Clear();
1575         }
1576         if (n < 0)
1577                 n = 8;  /* arbitrary */
1578         NRESIZE(result->ob_item, PyObject*, n);
1579         if (result->ob_item == NULL) {
1580                 PyErr_NoMemory();
1581                 goto error;
1582         }
1583         for (i = 0; i < n; i++)
1584                 result->ob_item[i] = NULL;
1585         result->ob_size = n;
1586
1587         /* Run iterator to exhaustion. */
1588         for (i = 0; ; i++) {
1589                 PyObject *item = PyIter_Next(it);
1590                 if (item == NULL) {
1591                         if (PyErr_Occurred())
1592                                 goto error;
1593                         break;
1594                 }
1595                 if (i < n)
1596                         PyList_SET_ITEM(result, i, item); /* steals ref */
1597                 else {
1598                         int status = ins1(result, result->ob_size, item);
1599                         Py_DECREF(item);  /* append creates a new ref */
1600                         if (status < 0)
1601                                 goto error;
1602                 }
1603         }
1604
1605         /* Cut back result list if initial guess was too large. */
1606         if (i < n && result != NULL) {
1607                 if (list_ass_slice(result, i, n, (PyObject *)NULL) != 0)
1608                         goto error;
1609         }
1610         Py_DECREF(it);
1611         return 0;
1612
1613   error:
1614         Py_DECREF(it);
1615         return -1;
1616 }
1617
1618 static int
1619 list_init(PyListObject *self, PyObject *args, PyObject *kw)
1620 {
1621         PyObject *arg = NULL;
1622         static char *kwlist[] = {"sequence", 0};
1623
1624         if (!PyArg_ParseTupleAndKeywords(args, kw, "|O:list", kwlist, &arg))
1625                 return -1;
1626         if (arg != NULL)
1627                 return list_fill(self, arg);
1628         if (self->ob_size > 0)
1629                 return list_ass_slice(self, 0, self->ob_size, (PyObject*)NULL);
1630         return 0;
1631 }
1632
1633 static long
1634 list_nohash(PyObject *self)
1635 {
1636         PyErr_SetString(PyExc_TypeError, "list objects are unhashable");
1637         return -1;
1638 }
1639
1640 static char append_doc[] =
1641 "L.append(object) -- append object to end";
1642 static char extend_doc[] =
1643 "L.extend(list) -- extend list by appending list elements";
1644 static char insert_doc[] =
1645 "L.insert(index, object) -- insert object before index";
1646 static char pop_doc[] =
1647 "L.pop([index]) -> item -- remove and return item at index (default last)";
1648 static char remove_doc[] =
1649 "L.remove(value) -- remove first occurrence of value";
1650 static char index_doc[] =
1651 "L.index(value) -> integer -- return index of first occurrence of value";
1652 static char count_doc[] =
1653 "L.count(value) -> integer -- return number of occurrences of value";
1654 static char reverse_doc[] =
1655 "L.reverse() -- reverse *IN PLACE*";
1656 static char sort_doc[] =
1657 "L.sort([cmpfunc]) -- sort *IN PLACE*; if given, cmpfunc(x, y) -> -1, 0, 1";
1658
1659 static PyMethodDef list_methods[] = {
1660         {"append",      (PyCFunction)listappend,  METH_O, append_doc},
1661         {"insert",      (PyCFunction)listinsert,  METH_VARARGS, insert_doc},
1662         {"extend",      (PyCFunction)listextend,  METH_O, extend_doc},
1663         {"pop",         (PyCFunction)listpop,     METH_VARARGS, pop_doc},
1664         {"remove",      (PyCFunction)listremove,  METH_O, remove_doc},
1665         {"index",       (PyCFunction)listindex,   METH_O, index_doc},
1666         {"count",       (PyCFunction)listcount,   METH_O, count_doc},
1667         {"reverse",     (PyCFunction)listreverse, METH_NOARGS, reverse_doc},
1668         {"sort",        (PyCFunction)listsort,    METH_VARARGS, sort_doc},
1669         {NULL,          NULL}           /* sentinel */
1670 };
1671
1672 static PySequenceMethods list_as_sequence = {
1673         (inquiry)list_length,                   /* sq_length */
1674         (binaryfunc)list_concat,                /* sq_concat */
1675         (intargfunc)list_repeat,                /* sq_repeat */
1676         (intargfunc)list_item,                  /* sq_item */
1677         (intintargfunc)list_slice,              /* sq_slice */
1678         (intobjargproc)list_ass_item,           /* sq_ass_item */
1679         (intintobjargproc)list_ass_slice,       /* sq_ass_slice */
1680         (objobjproc)list_contains,              /* sq_contains */
1681         (binaryfunc)list_inplace_concat,        /* sq_inplace_concat */
1682         (intargfunc)list_inplace_repeat,        /* sq_inplace_repeat */
1683 };
1684
1685 static char list_doc[] =
1686 "list() -> new list\n"
1687 "list(sequence) -> new list initialized from sequence's items";
1688
1689 PyTypeObject PyList_Type = {
1690         PyObject_HEAD_INIT(&PyType_Type)
1691         0,
1692         "list",
1693         sizeof(PyListObject),
1694         0,
1695         (destructor)list_dealloc,               /* tp_dealloc */
1696         (printfunc)list_print,                  /* tp_print */
1697         0,                                      /* tp_getattr */
1698         0,                                      /* tp_setattr */
1699         0,                                      /* tp_compare */
1700         (reprfunc)list_repr,                    /* tp_repr */
1701         0,                                      /* tp_as_number */
1702         &list_as_sequence,                      /* tp_as_sequence */
1703         0,                                      /* tp_as_mapping */
1704         list_nohash,                            /* tp_hash */
1705         0,                                      /* tp_call */
1706         0,                                      /* tp_str */
1707         PyObject_GenericGetAttr,                /* tp_getattro */
1708         0,                                      /* tp_setattro */
1709         0,                                      /* tp_as_buffer */
1710         Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC |
1711                 Py_TPFLAGS_BASETYPE,            /* tp_flags */
1712         list_doc,                               /* tp_doc */
1713         (traverseproc)list_traverse,            /* tp_traverse */
1714         (inquiry)list_clear,                    /* tp_clear */
1715         list_richcompare,                       /* tp_richcompare */
1716         0,                                      /* tp_weaklistoffset */
1717         0,                                      /* tp_iter */
1718         0,                                      /* tp_iternext */
1719         list_methods,                           /* tp_methods */
1720         0,                                      /* tp_members */
1721         0,                                      /* tp_getset */
1722         0,                                      /* tp_base */
1723         0,                                      /* tp_dict */
1724         0,                                      /* tp_descr_get */
1725         0,                                      /* tp_descr_set */
1726         0,                                      /* tp_dictoffset */
1727         (initproc)list_init,                    /* tp_init */
1728         PyType_GenericAlloc,                    /* tp_alloc */
1729         PyType_GenericNew,                      /* tp_new */
1730         _PyObject_GC_Del,                       /* tp_free */
1731 };
1732
1733
1734 /* During a sort, we really can't have anyone modifying the list; it could
1735    cause core dumps.  Thus, we substitute a dummy type that raises an
1736    explanatory exception when a modifying operation is used.  Caveat:
1737    comparisons may behave differently; but I guess it's a bad idea anyway to
1738    compare a list that's being sorted... */
1739
1740 static PyObject *
1741 immutable_list_op(void)
1742 {
1743         PyErr_SetString(PyExc_TypeError,
1744                         "a list cannot be modified while it is being sorted");
1745         return NULL;
1746 }
1747
1748 static PyMethodDef immutable_list_methods[] = {
1749         {"append",      (PyCFunction)immutable_list_op, METH_VARARGS},
1750         {"insert",      (PyCFunction)immutable_list_op, METH_VARARGS},
1751         {"extend",      (PyCFunction)immutable_list_op,  METH_O},
1752         {"pop",         (PyCFunction)immutable_list_op, METH_VARARGS},
1753         {"remove",      (PyCFunction)immutable_list_op, METH_VARARGS},
1754         {"index",       (PyCFunction)listindex,         METH_O},
1755         {"count",       (PyCFunction)listcount,         METH_O},
1756         {"reverse",     (PyCFunction)immutable_list_op, METH_VARARGS},
1757         {"sort",        (PyCFunction)immutable_list_op, METH_VARARGS},
1758         {NULL,          NULL}           /* sentinel */
1759 };
1760
1761 static int
1762 immutable_list_ass(void)
1763 {
1764         immutable_list_op();
1765         return -1;
1766 }
1767
1768 static PySequenceMethods immutable_list_as_sequence = {
1769         (inquiry)list_length,                   /* sq_length */
1770         (binaryfunc)list_concat,                /* sq_concat */
1771         (intargfunc)list_repeat,                /* sq_repeat */
1772         (intargfunc)list_item,                  /* sq_item */
1773         (intintargfunc)list_slice,              /* sq_slice */
1774         (intobjargproc)immutable_list_ass,      /* sq_ass_item */
1775         (intintobjargproc)immutable_list_ass,   /* sq_ass_slice */
1776         (objobjproc)list_contains,              /* sq_contains */
1777 };
1778
1779 static PyTypeObject immutable_list_type = {
1780         PyObject_HEAD_INIT(&PyType_Type)
1781         0,
1782         "list (immutable, during sort)",
1783         sizeof(PyListObject),
1784         0,
1785         0, /* Cannot happen */                  /* tp_dealloc */
1786         (printfunc)list_print,                  /* tp_print */
1787         0,                                      /* tp_getattr */
1788         0,                                      /* tp_setattr */
1789         0, /* Won't be called */                /* tp_compare */
1790         (reprfunc)list_repr,                    /* tp_repr */
1791         0,                                      /* tp_as_number */
1792         &immutable_list_as_sequence,            /* tp_as_sequence */
1793         0,                                      /* tp_as_mapping */
1794         list_nohash,                            /* tp_hash */
1795         0,                                      /* tp_call */
1796         0,                                      /* tp_str */
1797         PyObject_GenericGetAttr,                /* tp_getattro */
1798         0,                                      /* tp_setattro */
1799         0,                                      /* tp_as_buffer */
1800         Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC,/* tp_flags */
1801         list_doc,                               /* tp_doc */
1802         (traverseproc)list_traverse,            /* tp_traverse */
1803         0,                                      /* tp_clear */
1804         list_richcompare,                       /* tp_richcompare */
1805         0,                                      /* tp_weaklistoffset */
1806         0,                                      /* tp_iter */
1807         0,                                      /* tp_iternext */
1808         immutable_list_methods,                 /* tp_methods */
1809         0,                                      /* tp_members */
1810         0,                                      /* tp_getset */
1811         0,                                      /* tp_base */
1812         0,                                      /* tp_dict */
1813         0,                                      /* tp_descr_get */
1814         0,                                      /* tp_descr_set */
1815         0,                                      /* tp_init */
1816         /* NOTE: This is *not* the standard list_type struct! */
1817 };