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