home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / py2s152.zip / Objects / listobject.c < prev    next >
C/C++ Source or Header  |  1999-06-27  |  39KB  |  1,516 lines

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