cpython-lru_cache-weakref: Objects/listobject.c annotate

annotate Objects/listobject.c @ 15842:f6cd36498a50 legacy-trunk

Document extensions to .pth files.

author	Martin v. Löwis <martin@v.loewis.de>
date	Sat, 13 Jan 2001 09:54:41 +0000
parents	3075a153a083
children	e21da84d0c65

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

Mercurial > cpython-lru_cache-weakref

annotate Objects/listobject.c @ 15842:f6cd36498a50 legacy-trunk