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