Mercurial > cpython-lru_cache-weakref

annotate Objects/listobject.c @ 5817:48b94de85bf3 legacy-trunk

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Extensive changes by AMK.
author Guido van Rossum <guido@python.org>
date Thu, 17 Jul 1997 16:29:42 +0000
parents c043901fa1fe
children 2ee9811c92fd
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
145
853b736a6a9e Added copyright notice.
Guido van Rossum <guido@python.org>
parents: 86
diff changeset
1 /***********************************************************
2059
866c81068dbd Added 1995 to copyright message.
Guido van Rossum <guido@python.org>
parents: 2053
diff changeset
2 Copyright 1991-1995 by Stichting Mathematisch Centrum, Amsterdam,
866c81068dbd Added 1995 to copyright message.
Guido van Rossum <guido@python.org>
parents: 2053
diff changeset
3 The Netherlands.
145
853b736a6a9e Added copyright notice.
Guido van Rossum <guido@python.org>
parents: 86
diff changeset
4
853b736a6a9e Added copyright notice.
Guido van Rossum <guido@python.org>
parents: 86
diff changeset
5 All Rights Reserved
853b736a6a9e Added copyright notice.
Guido van Rossum <guido@python.org>
parents: 86
diff changeset
6
4503
65d2d8e67da3 New permission notice, includes CNRI.
Guido van Rossum <guido@python.org>
parents: 3985
diff changeset
7 Permission to use, copy, modify, and distribute this software and its
65d2d8e67da3 New permission notice, includes CNRI.
Guido van Rossum <guido@python.org>
parents: 3985
diff changeset
8 documentation for any purpose and without fee is hereby granted,
145
853b736a6a9e Added copyright notice.
Guido van Rossum <guido@python.org>
parents: 86
diff changeset
9 provided that the above copyright notice appear in all copies and that
4503
65d2d8e67da3 New permission notice, includes CNRI.
Guido van Rossum <guido@python.org>
parents: 3985
diff changeset
10 both that copyright notice and this permission notice appear in
145
853b736a6a9e Added copyright notice.
Guido van Rossum <guido@python.org>
parents: 86
diff changeset
11 supporting documentation, and that the names of Stichting Mathematisch
4503
65d2d8e67da3 New permission notice, includes CNRI.
Guido van Rossum <guido@python.org>
parents: 3985
diff changeset
12 Centrum or CWI or Corporation for National Research Initiatives or
65d2d8e67da3 New permission notice, includes CNRI.
Guido van Rossum <guido@python.org>
parents: 3985
diff changeset
13 CNRI not be used in advertising or publicity pertaining to
65d2d8e67da3 New permission notice, includes CNRI.
Guido van Rossum <guido@python.org>
parents: 3985
diff changeset
14 distribution of the software without specific, written prior
65d2d8e67da3 New permission notice, includes CNRI.
Guido van Rossum <guido@python.org>
parents: 3985
diff changeset
15 permission.
145
853b736a6a9e Added copyright notice.
Guido van Rossum <guido@python.org>
parents: 86
diff changeset
16
4503
65d2d8e67da3 New permission notice, includes CNRI.
Guido van Rossum <guido@python.org>
parents: 3985
diff changeset
17 While CWI is the initial source for this software, a modified version
65d2d8e67da3 New permission notice, includes CNRI.
Guido van Rossum <guido@python.org>
parents: 3985
diff changeset
18 is made available by the Corporation for National Research Initiatives
65d2d8e67da3 New permission notice, includes CNRI.
Guido van Rossum <guido@python.org>
parents: 3985
diff changeset
19 (CNRI) at the Internet address ftp://ftp.python.org.
65d2d8e67da3 New permission notice, includes CNRI.
Guido van Rossum <guido@python.org>
parents: 3985
diff changeset
20
65d2d8e67da3 New permission notice, includes CNRI.
Guido van Rossum <guido@python.org>
parents: 3985
diff changeset
21 STICHTING MATHEMATISCH CENTRUM AND CNRI DISCLAIM ALL WARRANTIES WITH
65d2d8e67da3 New permission notice, includes CNRI.
Guido van Rossum <guido@python.org>
parents: 3985
diff changeset
22 REGARD TO THIS SOFTWARE, INCLUDING ALL IMPLIED WARRANTIES OF
65d2d8e67da3 New permission notice, includes CNRI.
Guido van Rossum <guido@python.org>
parents: 3985
diff changeset
23 MERCHANTABILITY AND FITNESS, IN NO EVENT SHALL STICHTING MATHEMATISCH
65d2d8e67da3 New permission notice, includes CNRI.
Guido van Rossum <guido@python.org>
parents: 3985
diff changeset
24 CENTRUM OR CNRI BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL
65d2d8e67da3 New permission notice, includes CNRI.
Guido van Rossum <guido@python.org>
parents: 3985
diff changeset
25 DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR
65d2d8e67da3 New permission notice, includes CNRI.
Guido van Rossum <guido@python.org>
parents: 3985
diff changeset
26 PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER
65d2d8e67da3 New permission notice, includes CNRI.
Guido van Rossum <guido@python.org>
parents: 3985
diff changeset
27 TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
65d2d8e67da3 New permission notice, includes CNRI.
Guido van Rossum <guido@python.org>
parents: 3985
diff changeset
28 PERFORMANCE OF THIS SOFTWARE.
145
853b736a6a9e Added copyright notice.
Guido van Rossum <guido@python.org>
parents: 86
diff changeset
29
853b736a6a9e Added copyright notice.
Guido van Rossum <guido@python.org>
parents: 86
diff changeset
30 ******************************************************************/
853b736a6a9e Added copyright notice.
Guido van Rossum <guido@python.org>
parents: 86
diff changeset
31
6
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
32 /* List object implementation */
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
33
5396
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
34 #include "Python.h"
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
35
1836
1203f0629527 Correct problems found by THINK C 6.0
Guido van Rossum <guido@python.org>
parents: 1405
diff changeset
36 #ifdef STDC_HEADERS
1203f0629527 Correct problems found by THINK C 6.0
Guido van Rossum <guido@python.org>
parents: 1405
diff changeset
37 #include <stddef.h>
1203f0629527 Correct problems found by THINK C 6.0
Guido van Rossum <guido@python.org>
parents: 1405
diff changeset
38 #else
1203f0629527 Correct problems found by THINK C 6.0
Guido van Rossum <guido@python.org>
parents: 1405
diff changeset
39 #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
40 #endif
6
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
41
5396
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
42 #define ROUNDUP(n, PyTryBlock) \
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
43 ((((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
44
ee4c954cd5df round up list item counts to improve realloc performance
Guido van Rossum <guido@python.org>
parents: 2188
diff changeset
45 static int
ee4c954cd5df round up list item counts to improve realloc performance
Guido van Rossum <guido@python.org>
parents: 2188
diff changeset
46 roundup(n)
ee4c954cd5df round up list item counts to improve realloc performance
Guido van Rossum <guido@python.org>
parents: 2188
diff changeset
47 int n;
ee4c954cd5df round up list item counts to improve realloc performance
Guido van Rossum <guido@python.org>
parents: 2188
diff changeset
48 {
ee4c954cd5df round up list item counts to improve realloc performance
Guido van Rossum <guido@python.org>
parents: 2188
diff changeset
49 if (n < 500)
ee4c954cd5df round up list item counts to improve realloc performance
Guido van Rossum <guido@python.org>
parents: 2188
diff changeset
50 return ROUNDUP(n, 10);
ee4c954cd5df round up list item counts to improve realloc performance
Guido van Rossum <guido@python.org>
parents: 2188
diff changeset
51 else
ee4c954cd5df round up list item counts to improve realloc performance
Guido van Rossum <guido@python.org>
parents: 2188
diff changeset
52 return ROUNDUP(n, 100);
ee4c954cd5df round up list item counts to improve realloc performance
Guido van Rossum <guido@python.org>
parents: 2188
diff changeset
53 }
ee4c954cd5df round up list item counts to improve realloc performance
Guido van Rossum <guido@python.org>
parents: 2188
diff changeset
54
5396
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
55 #define NRESIZE(var, type, nitems) PyMem_RESIZE(var, type, roundup(nitems))
2257
ee4c954cd5df round up list item counts to improve realloc performance
Guido van Rossum <guido@python.org>
parents: 2188
diff changeset
56
5396
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
57 PyObject *
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
58 PyList_New(size)
6
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
59 int size;
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
60 {
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
61 int i;
5396
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
62 PyListObject *op;
1836
1203f0629527 Correct problems found by THINK C 6.0
Guido van Rossum <guido@python.org>
parents: 1405
diff changeset
63 size_t nbytes;
6
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
64 if (size < 0) {
5396
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
65 PyErr_BadInternalCall();
6
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
66 return NULL;
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 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
69 /* Check for overflow */
5396
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
70 if (nbytes / sizeof(PyObject *) != (size_t)size) {
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
71 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
72 }
5396
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
73 op = (PyListObject *) malloc(sizeof(PyListObject));
6
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
74 if (op == NULL) {
5396
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
75 return PyErr_NoMemory();
6
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
76 }
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
77 if (size <= 0) {
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
78 op->ob_item = NULL;
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
79 }
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
80 else {
5396
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
81 op->ob_item = (PyObject **) malloc(nbytes);
6
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
82 if (op->ob_item == NULL) {
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
83 free((ANY *)op);
5396
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
84 return PyErr_NoMemory();
6
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
85 }
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
86 }
5396
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
87 op->ob_type = &PyList_Type;
6
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
88 op->ob_size = size;
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
89 for (i = 0; i < size; i++)
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
90 op->ob_item[i] = NULL;
5396
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
91 _Py_NewReference(op);
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
92 return (PyObject *) op;
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
5396
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
96 PyList_Size(op)
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
97 PyObject *op;
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 if (!PyList_Check(op)) {
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
100 PyErr_BadInternalCall();
6
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
101 return -1;
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
102 }
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
103 else
5396
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
104 return ((PyListObject *)op) -> ob_size;
6
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
105 }
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
106
5396
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
107 static PyObject *indexerr;
3985
011cfe7490eb Use pre-created string objects for most common exceptions
Guido van Rossum <guido@python.org>
parents: 2827
diff changeset
108
5396
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
109 PyObject *
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
110 PyList_GetItem(op, i)
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
111 PyObject *op;
6
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
112 int i;
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
113 {
5396
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
114 if (!PyList_Check(op)) {
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
115 PyErr_BadInternalCall();
6
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
116 return NULL;
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
117 }
5396
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
118 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
119 if (indexerr == NULL)
5396
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
120 indexerr = PyString_FromString(
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
121 "list index out of range");
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
122 PyErr_SetObject(PyExc_IndexError, indexerr);
6
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
123 return NULL;
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
124 }
5396
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
125 return ((PyListObject *)op) -> ob_item[i];
6
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
126 }
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
127
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
128 int
5396
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
129 PyList_SetItem(op, i, newitem)
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
130 register PyObject *op;
6
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
131 register int i;
5396
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
132 register PyObject *newitem;
6
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
133 {
5396
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
134 register PyObject *olditem;
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
135 register PyObject **p;
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
136 if (!PyList_Check(op)) {
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
137 Py_XDECREF(newitem);
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
138 PyErr_BadInternalCall();
27
82c7bab78bb1 New errors.
Guido van Rossum <guido@python.org>
parents: 6
diff changeset
139 return -1;
6
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
140 }
5396
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
141 if (i < 0 || i >= ((PyListObject *)op) -> ob_size) {
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
142 Py_XDECREF(newitem);
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
143 PyErr_SetString(PyExc_IndexError,
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
144 "list assignment index out of range");
27
82c7bab78bb1 New errors.
Guido van Rossum <guido@python.org>
parents: 6
diff changeset
145 return -1;
6
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
146 }
5396
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
147 p = ((PyListObject *)op) -> ob_item + i;
2504
425835b88099 a few peephole optimizations
Guido van Rossum <guido@python.org>
parents: 2397
diff changeset
148 olditem = *p;
425835b88099 a few peephole optimizations
Guido van Rossum <guido@python.org>
parents: 2397
diff changeset
149 *p = newitem;
5396
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
150 Py_XDECREF(olditem);
6
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
151 return 0;
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
152 }
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
153
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
154 static int
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
155 ins1(self, where, v)
5396
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
156 PyListObject *self;
6
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
157 int where;
5396
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
158 PyObject *v;
6
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
159 {
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
160 int i;
5396
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
161 PyObject **items;
27
82c7bab78bb1 New errors.
Guido van Rossum <guido@python.org>
parents: 6
diff changeset
162 if (v == NULL) {
5396
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
163 PyErr_BadInternalCall();
27
82c7bab78bb1 New errors.
Guido van Rossum <guido@python.org>
parents: 6
diff changeset
164 return -1;
82c7bab78bb1 New errors.
Guido van Rossum <guido@python.org>
parents: 6
diff changeset
165 }
6
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
166 items = self->ob_item;
5396
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
167 NRESIZE(items, PyObject *, self->ob_size+1);
27
82c7bab78bb1 New errors.
Guido van Rossum <guido@python.org>
parents: 6
diff changeset
168 if (items == NULL) {
5396
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
169 PyErr_NoMemory();
27
82c7bab78bb1 New errors.
Guido van Rossum <guido@python.org>
parents: 6
diff changeset
170 return -1;
82c7bab78bb1 New errors.
Guido van Rossum <guido@python.org>
parents: 6
diff changeset
171 }
6
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
172 if (where < 0)
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
173 where = 0;
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
174 if (where > self->ob_size)
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
175 where = self->ob_size;
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
176 for (i = self->ob_size; --i >= where; )
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
177 items[i+1] = items[i];
5396
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
178 Py_INCREF(v);
6
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
179 items[where] = v;
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
180 self->ob_item = items;
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
181 self->ob_size++;
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
182 return 0;
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
183 }
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
184
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
185 int
5396
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
186 PyList_Insert(op, where, newitem)
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
187 PyObject *op;
6
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
188 int where;
5396
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
189 PyObject *newitem;
6
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
190 {
5396
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
191 if (!PyList_Check(op)) {
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
192 PyErr_BadInternalCall();
27
82c7bab78bb1 New errors.
Guido van Rossum <guido@python.org>
parents: 6
diff changeset
193 return -1;
82c7bab78bb1 New errors.
Guido van Rossum <guido@python.org>
parents: 6
diff changeset
194 }
5396
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
195 return ins1((PyListObject *)op, where, newitem);
6
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
196 }
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
197
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
198 int
5396
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
199 PyList_Append(op, newitem)
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
200 PyObject *op;
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
201 PyObject *newitem;
6
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
202 {
5396
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
203 if (!PyList_Check(op)) {
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
204 PyErr_BadInternalCall();
27
82c7bab78bb1 New errors.
Guido van Rossum <guido@python.org>
parents: 6
diff changeset
205 return -1;
82c7bab78bb1 New errors.
Guido van Rossum <guido@python.org>
parents: 6
diff changeset
206 }
5396
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
207 return ins1((PyListObject *)op,
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
208 (int) ((PyListObject *)op)->ob_size, newitem);
6
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
209 }
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
210
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
211 /* Methods */
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
212
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
213 static void
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
214 list_dealloc(op)
5396
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
215 PyListObject *op;
6
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
216 {
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
217 int i;
2188
6461ff0c4bee Fix NULL dereference in case of out-of-memory condition
Jack Jansen <jack.jansen@cwi.nl>
parents: 2159
diff changeset
218 if (op->ob_item != NULL) {
6461ff0c4bee Fix NULL dereference in case of out-of-memory condition
Jack Jansen <jack.jansen@cwi.nl>
parents: 2159
diff changeset
219 for (i = 0; i < op->ob_size; i++) {
5396
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
220 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
221 }
6461ff0c4bee Fix NULL dereference in case of out-of-memory condition
Jack Jansen <jack.jansen@cwi.nl>
parents: 2159
diff changeset
222 free((ANY *)op->ob_item);
6
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
223 }
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
224 free((ANY *)op);
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
225 }
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
226
284
6ac402023cac printobject now returns an error code
Guido van Rossum <guido@python.org>
parents: 205
diff changeset
227 static int
6
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
228 list_print(op, fp, flags)
5396
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
229 PyListObject *op;
6
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
230 FILE *fp;
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
231 int flags;
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
232 {
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
233 int i;
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
234 fprintf(fp, "[");
284
6ac402023cac printobject now returns an error code
Guido van Rossum <guido@python.org>
parents: 205
diff changeset
235 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
236 if (i > 0)
6
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
237 fprintf(fp, ", ");
5396
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
238 if (PyObject_Print(op->ob_item[i], fp, 0) != 0)
284
6ac402023cac printobject now returns an error code
Guido van Rossum <guido@python.org>
parents: 205
diff changeset
239 return -1;
6
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
240 }
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
241 fprintf(fp, "]");
284
6ac402023cac printobject now returns an error code
Guido van Rossum <guido@python.org>
parents: 205
diff changeset
242 return 0;
6
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
243 }
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
244
5396
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
245 static PyObject *
6
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
246 list_repr(v)
5396
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
247 PyListObject *v;
6
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
248 {
5396
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
249 PyObject *s, *comma;
6
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
250 int i;
5396
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
251 s = PyString_FromString("[");
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
252 comma = PyString_FromString(", ");
6
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
253 for (i = 0; i < v->ob_size && s != NULL; i++) {
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
254 if (i > 0)
5396
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
255 PyString_Concat(&s, comma);
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
256 PyString_ConcatAndDel(&s, PyObject_Repr(v->ob_item[i]));
6
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
257 }
5396
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
258 Py_XDECREF(comma);
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
259 PyString_ConcatAndDel(&s, PyString_FromString("]"));
6
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
260 return s;
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
261 }
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
262
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
263 static int
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
264 list_compare(v, w)
5396
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
265 PyListObject *v, *w;
6
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
266 {
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
267 int len = (v->ob_size < w->ob_size) ? v->ob_size : w->ob_size;
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
268 int i;
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
269 for (i = 0; i < len; i++) {
5396
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
270 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
271 if (cmp != 0)
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
272 return cmp;
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
273 }
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
274 return v->ob_size - w->ob_size;
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
275 }
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
276
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
277 static int
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
278 list_length(a)
5396
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
279 PyListObject *a;
6
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
280 {
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
281 return a->ob_size;
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
282 }
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
283
5396
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
284 static PyObject *
6
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
285 list_item(a, i)
5396
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
286 PyListObject *a;
6
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
287 int i;
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
288 {
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
289 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
290 if (indexerr == NULL)
5396
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
291 indexerr = PyString_FromString(
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
292 "list index out of range");
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
293 PyErr_SetObject(PyExc_IndexError, indexerr);
6
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
294 return NULL;
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
295 }
5396
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
296 Py_INCREF(a->ob_item[i]);
6
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
297 return a->ob_item[i];
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
298 }
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
299
5396
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
300 static PyObject *
6
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
301 list_slice(a, ilow, ihigh)
5396
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
302 PyListObject *a;
6
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
303 int ilow, ihigh;
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
304 {
5396
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
305 PyListObject *np;
6
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
306 int i;
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
307 if (ilow < 0)
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
308 ilow = 0;
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
309 else if (ilow > a->ob_size)
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
310 ilow = a->ob_size;
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
311 if (ihigh < 0)
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
312 ihigh = 0;
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
313 if (ihigh < ilow)
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
314 ihigh = ilow;
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
315 else if (ihigh > a->ob_size)
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
316 ihigh = a->ob_size;
5396
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
317 np = (PyListObject *) PyList_New(ihigh - ilow);
6
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
318 if (np == NULL)
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
319 return NULL;
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
320 for (i = ilow; i < ihigh; i++) {
5396
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
321 PyObject *v = a->ob_item[i];
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
322 Py_INCREF(v);
6
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
323 np->ob_item[i - ilow] = v;
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
324 }
5396
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
325 return (PyObject *)np;
6
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
326 }
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
327
5396
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
328 PyObject *
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
329 PyList_GetSlice(a, ilow, ihigh)
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
330 PyObject *a;
1313
6ee380349c84 * Added gmtime/localtime/mktime and SYSV timezone globals to timemodule.c.
Guido van Rossum <guido@python.org>
parents: 1211
diff changeset
331 int ilow, ihigh;
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 if (!PyList_Check(a)) {
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
334 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
335 return NULL;
6ee380349c84 * Added gmtime/localtime/mktime and SYSV timezone globals to timemodule.c.
Guido van Rossum <guido@python.org>
parents: 1211
diff changeset
336 }
5396
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
337 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
338 }
6ee380349c84 * Added gmtime/localtime/mktime and SYSV timezone globals to timemodule.c.
Guido van Rossum <guido@python.org>
parents: 1211
diff changeset
339
5396
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
340 static PyObject *
6
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
341 list_concat(a, bb)
5396
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
342 PyListObject *a;
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
343 PyObject *bb;
6
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
344 {
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
345 int size;
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
346 int i;
5396
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
347 PyListObject *np;
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
348 if (!PyList_Check(bb)) {
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
349 PyErr_BadArgument();
6
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
350 return NULL;
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
351 }
5396
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
352 #define b ((PyListObject *)bb)
6
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
353 size = a->ob_size + b->ob_size;
5396
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
354 np = (PyListObject *) PyList_New(size);
6
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
355 if (np == NULL) {
284
6ac402023cac printobject now returns an error code
Guido van Rossum <guido@python.org>
parents: 205
diff changeset
356 return NULL;
6
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
357 }
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
358 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
359 PyObject *v = a->ob_item[i];
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
360 Py_INCREF(v);
6
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
361 np->ob_item[i] = v;
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
362 }
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
363 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
364 PyObject *v = b->ob_item[i];
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
365 Py_INCREF(v);
6
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
366 np->ob_item[i + a->ob_size] = v;
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
367 }
5396
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
368 return (PyObject *)np;
6
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
369 #undef b
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
370 }
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
371
5396
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
372 static PyObject *
155
896c825f2f71 Added repeat (for list*integet).
Guido van Rossum <guido@python.org>
parents: 145
diff changeset
373 list_repeat(a, n)
5396
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
374 PyListObject *a;
155
896c825f2f71 Added repeat (for list*integet).
Guido van Rossum <guido@python.org>
parents: 145
diff changeset
375 int n;
896c825f2f71 Added repeat (for list*integet).
Guido van Rossum <guido@python.org>
parents: 145
diff changeset
376 {
896c825f2f71 Added repeat (for list*integet).
Guido van Rossum <guido@python.org>
parents: 145
diff changeset
377 int i, j;
896c825f2f71 Added repeat (for list*integet).
Guido van Rossum <guido@python.org>
parents: 145
diff changeset
378 int size;
5396
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
379 PyListObject *np;
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
380 PyObject **p;
155
896c825f2f71 Added repeat (for list*integet).
Guido van Rossum <guido@python.org>
parents: 145
diff changeset
381 if (n < 0)
896c825f2f71 Added repeat (for list*integet).
Guido van Rossum <guido@python.org>
parents: 145
diff changeset
382 n = 0;
896c825f2f71 Added repeat (for list*integet).
Guido van Rossum <guido@python.org>
parents: 145
diff changeset
383 size = a->ob_size * n;
5396
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
384 np = (PyListObject *) PyList_New(size);
155
896c825f2f71 Added repeat (for list*integet).
Guido van Rossum <guido@python.org>
parents: 145
diff changeset
385 if (np == NULL)
896c825f2f71 Added repeat (for list*integet).
Guido van Rossum <guido@python.org>
parents: 145
diff changeset
386 return NULL;
896c825f2f71 Added repeat (for list*integet).
Guido van Rossum <guido@python.org>
parents: 145
diff changeset
387 p = np->ob_item;
896c825f2f71 Added repeat (for list*integet).
Guido van Rossum <guido@python.org>
parents: 145
diff changeset
388 for (i = 0; i < n; i++) {
896c825f2f71 Added repeat (for list*integet).
Guido van Rossum <guido@python.org>
parents: 145
diff changeset
389 for (j = 0; j < a->ob_size; j++) {
896c825f2f71 Added repeat (for list*integet).
Guido van Rossum <guido@python.org>
parents: 145
diff changeset
390 *p = a->ob_item[j];
5396
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
391 Py_INCREF(*p);
155
896c825f2f71 Added repeat (for list*integet).
Guido van Rossum <guido@python.org>
parents: 145
diff changeset
392 p++;
896c825f2f71 Added repeat (for list*integet).
Guido van Rossum <guido@python.org>
parents: 145
diff changeset
393 }
896c825f2f71 Added repeat (for list*integet).
Guido van Rossum <guido@python.org>
parents: 145
diff changeset
394 }
5396
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
395 return (PyObject *) np;
155
896c825f2f71 Added repeat (for list*integet).
Guido van Rossum <guido@python.org>
parents: 145
diff changeset
396 }
896c825f2f71 Added repeat (for list*integet).
Guido van Rossum <guido@python.org>
parents: 145
diff changeset
397
6
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
398 static int
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
399 list_ass_slice(a, ilow, ihigh, v)
5396
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
400 PyListObject *a;
6
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
401 int ilow, ihigh;
5396
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
402 PyObject *v;
6
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
403 {
2143
7ae847b1b269 fix reentrancy bug in slice assignment
Guido van Rossum <guido@python.org>
parents: 2059
diff changeset
404 /* 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
405 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
406 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
407 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
408 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
409 list. :-( */
5396
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
410 PyObject **recycle, **p;
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
411 PyObject **item;
6
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
412 int n; /* Size of replacement list */
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
413 int d; /* Change in size */
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
414 int k; /* Loop index */
5396
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
415 #define b ((PyListObject *)v)
6
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
416 if (v == NULL)
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
417 n = 0;
5396
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
418 else if (PyList_Check(v)) {
6
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
419 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
420 if (a == b) {
766cc820f511 Fix assignment of a list to a slice of itself.
Guido van Rossum <guido@python.org>
parents: 475
diff changeset
421 /* 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
422 int ret;
766cc820f511 Fix assignment of a list to a slice of itself.
Guido van Rossum <guido@python.org>
parents: 475
diff changeset
423 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
424 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
425 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
426 return ret;
766cc820f511 Fix assignment of a list to a slice of itself.
Guido van Rossum <guido@python.org>
parents: 475
diff changeset
427 }
766cc820f511 Fix assignment of a list to a slice of itself.
Guido van Rossum <guido@python.org>
parents: 475
diff changeset
428 }
27
82c7bab78bb1 New errors.
Guido van Rossum <guido@python.org>
parents: 6
diff changeset
429 else {
5396
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
430 PyErr_BadArgument();
27
82c7bab78bb1 New errors.
Guido van Rossum <guido@python.org>
parents: 6
diff changeset
431 return -1;
82c7bab78bb1 New errors.
Guido van Rossum <guido@python.org>
parents: 6
diff changeset
432 }
6
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
433 if (ilow < 0)
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
434 ilow = 0;
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
435 else if (ilow > a->ob_size)
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
436 ilow = a->ob_size;
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
437 if (ihigh < 0)
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
438 ihigh = 0;
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
439 if (ihigh < ilow)
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
440 ihigh = ilow;
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
441 else if (ihigh > a->ob_size)
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
442 ihigh = a->ob_size;
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
443 item = a->ob_item;
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
444 d = n - (ihigh-ilow);
2143
7ae847b1b269 fix reentrancy bug in slice assignment
Guido van Rossum <guido@python.org>
parents: 2059
diff changeset
445 if (ihigh > ilow)
5396
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
446 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
447 else
7ae847b1b269 fix reentrancy bug in slice assignment
Guido van Rossum <guido@python.org>
parents: 2059
diff changeset
448 p = recycle = NULL;
7ae847b1b269 fix reentrancy bug in slice assignment
Guido van Rossum <guido@python.org>
parents: 2059
diff changeset
449 if (d <= 0) { /* Delete -d items; recycle ihigh-ilow items */
6
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
450 for (k = ilow; k < ihigh; k++)
2143
7ae847b1b269 fix reentrancy bug in slice assignment
Guido van Rossum <guido@python.org>
parents: 2059
diff changeset
451 *p++ = item[k];
6
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
452 if (d < 0) {
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
453 for (/*k = ihigh*/; k < a->ob_size; k++)
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
454 item[k+d] = item[k];
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
455 a->ob_size += d;
5396
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
456 NRESIZE(item, PyObject *, a->ob_size); /* Can't fail */
6
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
457 a->ob_item = item;
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
458 }
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
459 }
2143
7ae847b1b269 fix reentrancy bug in slice assignment
Guido van Rossum <guido@python.org>
parents: 2059
diff changeset
460 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
461 NRESIZE(item, PyObject *, a->ob_size + d);
27
82c7bab78bb1 New errors.
Guido van Rossum <guido@python.org>
parents: 6
diff changeset
462 if (item == NULL) {
5396
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
463 PyMem_XDEL(recycle);
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
464 PyErr_NoMemory();
27
82c7bab78bb1 New errors.
Guido van Rossum <guido@python.org>
parents: 6
diff changeset
465 return -1;
82c7bab78bb1 New errors.
Guido van Rossum <guido@python.org>
parents: 6
diff changeset
466 }
6
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
467 for (k = a->ob_size; --k >= ihigh; )
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
468 item[k+d] = item[k];
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
469 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
470 *p++ = item[k];
6
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
471 a->ob_item = item;
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
472 a->ob_size += d;
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
473 }
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
474 for (k = 0; k < n; k++, ilow++) {
5396
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
475 PyObject *w = b->ob_item[k];
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
476 Py_XINCREF(w);
6
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
477 item[ilow] = w;
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
478 }
2143
7ae847b1b269 fix reentrancy bug in slice assignment
Guido van Rossum <guido@python.org>
parents: 2059
diff changeset
479 if (recycle) {
7ae847b1b269 fix reentrancy bug in slice assignment
Guido van Rossum <guido@python.org>
parents: 2059
diff changeset
480 while (--p >= recycle)
5396
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
481 Py_XDECREF(*p);
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
482 PyMem_DEL(recycle);
2143
7ae847b1b269 fix reentrancy bug in slice assignment
Guido van Rossum <guido@python.org>
parents: 2059
diff changeset
483 }
6
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
484 return 0;
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
485 #undef b
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
486 }
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
487
1313
6ee380349c84 * Added gmtime/localtime/mktime and SYSV timezone globals to timemodule.c.
Guido van Rossum <guido@python.org>
parents: 1211
diff changeset
488 int
5396
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
489 PyList_SetSlice(a, ilow, ihigh, v)
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
490 PyObject *a;
1313
6ee380349c84 * Added gmtime/localtime/mktime and SYSV timezone globals to timemodule.c.
Guido van Rossum <guido@python.org>
parents: 1211
diff changeset
491 int ilow, ihigh;
5396
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
492 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
493 {
5396
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
494 if (!PyList_Check(a)) {
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
495 PyErr_BadInternalCall();
1330
409ea74feb21 Minor fixes / changes for Mac compatibility.
Guido van Rossum <guido@python.org>
parents: 1313
diff changeset
496 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
497 }
5396
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
498 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
499 }
6ee380349c84 * Added gmtime/localtime/mktime and SYSV timezone globals to timemodule.c.
Guido van Rossum <guido@python.org>
parents: 1211
diff changeset
500
167
3fa2b14be270 Swapped list_ass_item and list_ass_slice to satisfy Standard C.
Guido van Rossum <guido@python.org>
parents: 155
diff changeset
501 static int
3fa2b14be270 Swapped list_ass_item and list_ass_slice to satisfy Standard C.
Guido van Rossum <guido@python.org>
parents: 155
diff changeset
502 list_ass_item(a, i, v)
5396
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
503 PyListObject *a;
167
3fa2b14be270 Swapped list_ass_item and list_ass_slice to satisfy Standard C.
Guido van Rossum <guido@python.org>
parents: 155
diff changeset
504 int i;
5396
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
505 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
506 {
5396
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
507 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
508 if (i < 0 || i >= a->ob_size) {
5396
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
509 PyErr_SetString(PyExc_IndexError,
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
510 "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
511 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
512 }
3fa2b14be270 Swapped list_ass_item and list_ass_slice to satisfy Standard C.
Guido van Rossum <guido@python.org>
parents: 155
diff changeset
513 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
514 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
515 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
516 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
517 a->ob_item[i] = v;
5396
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
518 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
519 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
520 }
3fa2b14be270 Swapped list_ass_item and list_ass_slice to satisfy Standard C.
Guido van Rossum <guido@python.org>
parents: 155
diff changeset
521
5396
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
522 static PyObject *
6
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
523 ins(self, where, v)
5396
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
524 PyListObject *self;
6
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
525 int where;
5396
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
526 PyObject *v;
6
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
527 {
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
528 if (ins1(self, where, v) != 0)
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
529 return NULL;
5396
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
530 Py_INCREF(Py_None);
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
531 return Py_None;
6
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
532 }
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
533
5396
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
534 static PyObject *
6
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
535 listinsert(self, args)
5396
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
536 PyListObject *self;
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
537 PyObject *args;
6
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
538 {
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
539 int i;
5396
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
540 PyObject *v;
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
541 if (!PyArg_Parse(args, "(iO)", &i, &v))
6
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
542 return NULL;
1211
406860dfaac7 * stdwinmodule.c: various new commands: setwin{pos,size},
Guido van Rossum <guido@python.org>
parents: 1198
diff changeset
543 return ins(self, i, v);
6
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
544 }
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
545
5396
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
546 static PyObject *
6
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
547 listappend(self, args)
5396
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
548 PyListObject *self;
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
549 PyObject *args;
6
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
550 {
5396
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
551 PyObject *v;
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
552 if (!PyArg_Parse(args, "O", &v))
1211
406860dfaac7 * stdwinmodule.c: various new commands: setwin{pos,size},
Guido van Rossum <guido@python.org>
parents: 1198
diff changeset
553 return NULL;
406860dfaac7 * stdwinmodule.c: various new commands: setwin{pos,size},
Guido van Rossum <guido@python.org>
parents: 1198
diff changeset
554 return ins(self, (int) self->ob_size, v);
6
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
555 }
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
556
4673
a3cdc8164990 Added new quicksort implementation, tailored to sorting arrays of
Guido van Rossum <guido@python.org>
parents: 4503
diff changeset
557 #define NEWSORT
a3cdc8164990 Added new quicksort implementation, tailored to sorting arrays of
Guido van Rossum <guido@python.org>
parents: 4503
diff changeset
558
a3cdc8164990 Added new quicksort implementation, tailored to sorting arrays of
Guido van Rossum <guido@python.org>
parents: 4503
diff changeset
559 #ifdef NEWSORT
a3cdc8164990 Added new quicksort implementation, tailored to sorting arrays of
Guido van Rossum <guido@python.org>
parents: 4503
diff changeset
560
a3cdc8164990 Added new quicksort implementation, tailored to sorting arrays of
Guido van Rossum <guido@python.org>
parents: 4503
diff changeset
561 /* 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
562 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
563
a3cdc8164990 Added new quicksort implementation, tailored to sorting arrays of
Guido van Rossum <guido@python.org>
parents: 4503
diff changeset
564 /* 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
565 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
566 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
567 #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
568
a3cdc8164990 Added new quicksort implementation, tailored to sorting arrays of
Guido van Rossum <guido@python.org>
parents: 4503
diff changeset
569 /* 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
570 comparison function (any callable Python object). Calls the
a3cdc8164990 Added new quicksort implementation, tailored to sorting arrays of
Guido van Rossum <guido@python.org>
parents: 4503
diff changeset
571 standard comparison function, cmpobject(), if the user-supplied
a3cdc8164990 Added new quicksort implementation, tailored to sorting arrays of
Guido van Rossum <guido@python.org>
parents: 4503
diff changeset
572 function is NULL. */
a3cdc8164990 Added new quicksort implementation, tailored to sorting arrays of
Guido van Rossum <guido@python.org>
parents: 4503
diff changeset
573
a3cdc8164990 Added new quicksort implementation, tailored to sorting arrays of
Guido van Rossum <guido@python.org>
parents: 4503
diff changeset
574 static int
a3cdc8164990 Added new quicksort implementation, tailored to sorting arrays of
Guido van Rossum <guido@python.org>
parents: 4503
diff changeset
575 docompare(x, y, compare)
5396
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
576 PyObject *x;
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
577 PyObject *y;
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
578 PyObject *compare;
4673
a3cdc8164990 Added new quicksort implementation, tailored to sorting arrays of
Guido van Rossum <guido@python.org>
parents: 4503
diff changeset
579 {
5396
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
580 PyObject *args, *res;
4673
a3cdc8164990 Added new quicksort implementation, tailored to sorting arrays of
Guido van Rossum <guido@python.org>
parents: 4503
diff changeset
581 int i;
a3cdc8164990 Added new quicksort implementation, tailored to sorting arrays of
Guido van Rossum <guido@python.org>
parents: 4503
diff changeset
582
5610
10e9cfa010f0 PyObject_Compare can raise an exception now.
Guido van Rossum <guido@python.org>
parents: 5396
diff changeset
583 if (compare == NULL) {
10e9cfa010f0 PyObject_Compare can raise an exception now.
Guido van Rossum <guido@python.org>
parents: 5396
diff changeset
584 i = PyObject_Compare(x, y);
10e9cfa010f0 PyObject_Compare can raise an exception now.
Guido van Rossum <guido@python.org>
parents: 5396
diff changeset
585 if (i && PyErr_Occurred())
10e9cfa010f0 PyObject_Compare can raise an exception now.
Guido van Rossum <guido@python.org>
parents: 5396
diff changeset
586 i = CMPERROR;
10e9cfa010f0 PyObject_Compare can raise an exception now.
Guido van Rossum <guido@python.org>
parents: 5396
diff changeset
587 return i;
10e9cfa010f0 PyObject_Compare can raise an exception now.
Guido van Rossum <guido@python.org>
parents: 5396
diff changeset
588 }
4673
a3cdc8164990 Added new quicksort implementation, tailored to sorting arrays of
Guido van Rossum <guido@python.org>
parents: 4503
diff changeset
589
5396
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
590 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
591 if (args == NULL)
a3cdc8164990 Added new quicksort implementation, tailored to sorting arrays of
Guido van Rossum <guido@python.org>
parents: 4503
diff changeset
592 return CMPERROR;
5396
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
593 res = PyEval_CallObject(compare, args);
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
594 Py_DECREF(args);
4673
a3cdc8164990 Added new quicksort implementation, tailored to sorting arrays of
Guido van Rossum <guido@python.org>
parents: 4503
diff changeset
595 if (res == NULL)
a3cdc8164990 Added new quicksort implementation, tailored to sorting arrays of
Guido van Rossum <guido@python.org>
parents: 4503
diff changeset
596 return CMPERROR;
5396
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
597 if (!PyInt_Check(res)) {
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
598 Py_DECREF(res);
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
599 PyErr_SetString(PyExc_TypeError,
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
600 "comparison function should return int");
4673
a3cdc8164990 Added new quicksort implementation, tailored to sorting arrays of
Guido van Rossum <guido@python.org>
parents: 4503
diff changeset
601 return CMPERROR;
a3cdc8164990 Added new quicksort implementation, tailored to sorting arrays of
Guido van Rossum <guido@python.org>
parents: 4503
diff changeset
602 }
5396
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
603 i = PyInt_AsLong(res);
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
604 Py_DECREF(res);
4673
a3cdc8164990 Added new quicksort implementation, tailored to sorting arrays of
Guido van Rossum <guido@python.org>
parents: 4503
diff changeset
605 if (i < 0)
a3cdc8164990 Added new quicksort implementation, tailored to sorting arrays of
Guido van Rossum <guido@python.org>
parents: 4503
diff changeset
606 return -1;
a3cdc8164990 Added new quicksort implementation, tailored to sorting arrays of
Guido van Rossum <guido@python.org>
parents: 4503
diff changeset
607 if (i > 0)
a3cdc8164990 Added new quicksort implementation, tailored to sorting arrays of
Guido van Rossum <guido@python.org>
parents: 4503
diff changeset
608 return 1;
a3cdc8164990 Added new quicksort implementation, tailored to sorting arrays of
Guido van Rossum <guido@python.org>
parents: 4503
diff changeset
609 return 0;
a3cdc8164990 Added new quicksort implementation, tailored to sorting arrays of
Guido van Rossum <guido@python.org>
parents: 4503
diff changeset
610 }
a3cdc8164990 Added new quicksort implementation, tailored to sorting arrays of
Guido van Rossum <guido@python.org>
parents: 4503
diff changeset
611
a3cdc8164990 Added new quicksort implementation, tailored to sorting arrays of
Guido van Rossum <guido@python.org>
parents: 4503
diff changeset
612 /* Straight insertion sort. More efficient for sorting small arrays. */
a3cdc8164990 Added new quicksort implementation, tailored to sorting arrays of
Guido van Rossum <guido@python.org>
parents: 4503
diff changeset
613
a3cdc8164990 Added new quicksort implementation, tailored to sorting arrays of
Guido van Rossum <guido@python.org>
parents: 4503
diff changeset
614 static int
a3cdc8164990 Added new quicksort implementation, tailored to sorting arrays of
Guido van Rossum <guido@python.org>
parents: 4503
diff changeset
615 insertionsort(array, size, compare)
5396
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
616 PyObject **array; /* Start of array to sort */
4673
a3cdc8164990 Added new quicksort implementation, tailored to sorting arrays of
Guido van Rossum <guido@python.org>
parents: 4503
diff changeset
617 int size; /* Number of elements to sort */
5396
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
618 PyObject *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
619 {
5396
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
620 register PyObject **a = array;
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
621 register PyObject **end = array+size;
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
622 register PyObject **p;
4673
a3cdc8164990 Added new quicksort implementation, tailored to sorting arrays of
Guido van Rossum <guido@python.org>
parents: 4503
diff changeset
623
4690
c2b831f923c2 Some more tuning of quicksort: use pointers instead of indexing.
Guido van Rossum <guido@python.org>
parents: 4673
diff changeset
624 for (p = a+1; p < end; p++) {
5396
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
625 register PyObject *key = *p;
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
626 register PyObject **q = p;
4690
c2b831f923c2 Some more tuning of quicksort: use pointers instead of indexing.
Guido van Rossum <guido@python.org>
parents: 4673
diff changeset
627 while (--q >= a) {
c2b831f923c2 Some more tuning of quicksort: use pointers instead of indexing.
Guido van Rossum <guido@python.org>
parents: 4673
diff changeset
628 register int k = docompare(*q, key, compare);
4673
a3cdc8164990 Added new quicksort implementation, tailored to sorting arrays of
Guido van Rossum <guido@python.org>
parents: 4503
diff changeset
629 if (k == CMPERROR)
a3cdc8164990 Added new quicksort implementation, tailored to sorting arrays of
Guido van Rossum <guido@python.org>
parents: 4503
diff changeset
630 return -1;
a3cdc8164990 Added new quicksort implementation, tailored to sorting arrays of
Guido van Rossum <guido@python.org>
parents: 4503
diff changeset
631 if (k <= 0)
a3cdc8164990 Added new quicksort implementation, tailored to sorting arrays of
Guido van Rossum <guido@python.org>
parents: 4503
diff changeset
632 break;
4690
c2b831f923c2 Some more tuning of quicksort: use pointers instead of indexing.
Guido van Rossum <guido@python.org>
parents: 4673
diff changeset
633 *(q+1) = *q;
c2b831f923c2 Some more tuning of quicksort: use pointers instead of indexing.
Guido van Rossum <guido@python.org>
parents: 4673
diff changeset
634 *q = key; /* For consistency */
4673
a3cdc8164990 Added new quicksort implementation, tailored to sorting arrays of
Guido van Rossum <guido@python.org>
parents: 4503
diff changeset
635 }
a3cdc8164990 Added new quicksort implementation, tailored to sorting arrays of
Guido van Rossum <guido@python.org>
parents: 4503
diff changeset
636 }
a3cdc8164990 Added new quicksort implementation, tailored to sorting arrays of
Guido van Rossum <guido@python.org>
parents: 4503
diff changeset
637
a3cdc8164990 Added new quicksort implementation, tailored to sorting arrays of
Guido van Rossum <guido@python.org>
parents: 4503
diff changeset
638 return 0;
a3cdc8164990 Added new quicksort implementation, tailored to sorting arrays of
Guido van Rossum <guido@python.org>
parents: 4503
diff changeset
639 }
a3cdc8164990 Added new quicksort implementation, tailored to sorting arrays of
Guido van Rossum <guido@python.org>
parents: 4503
diff changeset
640
a3cdc8164990 Added new quicksort implementation, tailored to sorting arrays of
Guido van Rossum <guido@python.org>
parents: 4503
diff changeset
641 /* MINSIZE is the smallest array we care to partition; smaller arrays
4732
d367014200bb Change comment about MINSIZE -- 10 is optimal for Python.
Guido van Rossum <guido@python.org>
parents: 4690
diff changeset
642 are sorted using a straight insertion sort (above). It must be at
d367014200bb Change comment about MINSIZE -- 10 is optimal for Python.
Guido van Rossum <guido@python.org>
parents: 4690
diff changeset
643 least 2 for the quicksort implementation to work. Assuming that
d367014200bb Change comment about MINSIZE -- 10 is optimal for Python.
Guido van Rossum <guido@python.org>
parents: 4690
diff changeset
644 comparisons are more expensive than everything else (and this is a
d367014200bb Change comment about MINSIZE -- 10 is optimal for Python.
Guido van Rossum <guido@python.org>
parents: 4690
diff changeset
645 good assumption for Python), it should be 10, which is the cutoff
d367014200bb Change comment about MINSIZE -- 10 is optimal for Python.
Guido van Rossum <guido@python.org>
parents: 4690
diff changeset
646 point: quicksort requires more comparisons than insertion sort for
d367014200bb Change comment about MINSIZE -- 10 is optimal for Python.
Guido van Rossum <guido@python.org>
parents: 4690
diff changeset
647 smaller arrays. */
4673
a3cdc8164990 Added new quicksort implementation, tailored to sorting arrays of
Guido van Rossum <guido@python.org>
parents: 4503
diff changeset
648 #define MINSIZE 10
a3cdc8164990 Added new quicksort implementation, tailored to sorting arrays of
Guido van Rossum <guido@python.org>
parents: 4503
diff changeset
649
a3cdc8164990 Added new quicksort implementation, tailored to sorting arrays of
Guido van Rossum <guido@python.org>
parents: 4503
diff changeset
650 /* STACKSIZE is the size of our work stack. A rough estimate is that
a3cdc8164990 Added new quicksort implementation, tailored to sorting arrays of
Guido van Rossum <guido@python.org>
parents: 4503
diff changeset
651 this allows us to sort arrays of MINSIZE * 2**STACKSIZE, or large
a3cdc8164990 Added new quicksort implementation, tailored to sorting arrays of
Guido van Rossum <guido@python.org>
parents: 4503
diff changeset
652 enough. (Because of the way we push the biggest partition first,
a3cdc8164990 Added new quicksort implementation, tailored to sorting arrays of
Guido van Rossum <guido@python.org>
parents: 4503
diff changeset
653 the worst case occurs when all subarrays are always partitioned
a3cdc8164990 Added new quicksort implementation, tailored to sorting arrays of
Guido van Rossum <guido@python.org>
parents: 4503
diff changeset
654 exactly in two.) */
a3cdc8164990 Added new quicksort implementation, tailored to sorting arrays of
Guido van Rossum <guido@python.org>
parents: 4503
diff changeset
655 #define STACKSIZE 64
a3cdc8164990 Added new quicksort implementation, tailored to sorting arrays of
Guido van Rossum <guido@python.org>
parents: 4503
diff changeset
656
a3cdc8164990 Added new quicksort implementation, tailored to sorting arrays of
Guido van Rossum <guido@python.org>
parents: 4503
diff changeset
657 /* Quicksort algorithm. Return -1 if an exception occurred; in this
a3cdc8164990 Added new quicksort implementation, tailored to sorting arrays of
Guido van Rossum <guido@python.org>
parents: 4503
diff changeset
658 case we leave the array partly sorted but otherwise in good health
a3cdc8164990 Added new quicksort implementation, tailored to sorting arrays of
Guido van Rossum <guido@python.org>
parents: 4503
diff changeset
659 (i.e. no items have been removed or duplicated). */
a3cdc8164990 Added new quicksort implementation, tailored to sorting arrays of
Guido van Rossum <guido@python.org>
parents: 4503
diff changeset
660
a3cdc8164990 Added new quicksort implementation, tailored to sorting arrays of
Guido van Rossum <guido@python.org>
parents: 4503
diff changeset
661 static int
a3cdc8164990 Added new quicksort implementation, tailored to sorting arrays of
Guido van Rossum <guido@python.org>
parents: 4503
diff changeset
662 quicksort(array, size, compare)
5396
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
663 PyObject **array; /* Start of array to sort */
4673
a3cdc8164990 Added new quicksort implementation, tailored to sorting arrays of
Guido van Rossum <guido@python.org>
parents: 4503
diff changeset
664 int size; /* Number of elements to sort */
5396
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
665 PyObject *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
666 {
5396
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
667 register PyObject *tmp, *pivot;
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
668 register PyObject **lo, **hi, **l, **r;
4690
c2b831f923c2 Some more tuning of quicksort: use pointers instead of indexing.
Guido van Rossum <guido@python.org>
parents: 4673
diff changeset
669 int top, k, n, n2;
5396
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
670 PyObject **lostack[STACKSIZE];
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
671 PyObject **histack[STACKSIZE];
4673
a3cdc8164990 Added new quicksort implementation, tailored to sorting arrays of
Guido van Rossum <guido@python.org>
parents: 4503
diff changeset
672
a3cdc8164990 Added new quicksort implementation, tailored to sorting arrays of
Guido van Rossum <guido@python.org>
parents: 4503
diff changeset
673 /* Start out with the whole array on the work stack */
4690
c2b831f923c2 Some more tuning of quicksort: use pointers instead of indexing.
Guido van Rossum <guido@python.org>
parents: 4673
diff changeset
674 lostack[0] = array;
c2b831f923c2 Some more tuning of quicksort: use pointers instead of indexing.
Guido van Rossum <guido@python.org>
parents: 4673
diff changeset
675 histack[0] = array+size;
4673
a3cdc8164990 Added new quicksort implementation, tailored to sorting arrays of
Guido van Rossum <guido@python.org>
parents: 4503
diff changeset
676 top = 1;
a3cdc8164990 Added new quicksort implementation, tailored to sorting arrays of
Guido van Rossum <guido@python.org>
parents: 4503
diff changeset
677
a3cdc8164990 Added new quicksort implementation, tailored to sorting arrays of
Guido van Rossum <guido@python.org>
parents: 4503
diff changeset
678 /* Repeat until the work stack is empty */
a3cdc8164990 Added new quicksort implementation, tailored to sorting arrays of
Guido van Rossum <guido@python.org>
parents: 4503
diff changeset
679 while (--top >= 0) {
4690
c2b831f923c2 Some more tuning of quicksort: use pointers instead of indexing.
Guido van Rossum <guido@python.org>
parents: 4673
diff changeset
680 lo = lostack[top];
c2b831f923c2 Some more tuning of quicksort: use pointers instead of indexing.
Guido van Rossum <guido@python.org>
parents: 4673
diff changeset
681 hi = histack[top];
4673
a3cdc8164990 Added new quicksort implementation, tailored to sorting arrays of
Guido van Rossum <guido@python.org>
parents: 4503
diff changeset
682
a3cdc8164990 Added new quicksort implementation, tailored to sorting arrays of
Guido van Rossum <guido@python.org>
parents: 4503
diff changeset
683 /* If it's a small one, use straight insertion sort */
4690
c2b831f923c2 Some more tuning of quicksort: use pointers instead of indexing.
Guido van Rossum <guido@python.org>
parents: 4673
diff changeset
684 n = hi - lo;
4673
a3cdc8164990 Added new quicksort implementation, tailored to sorting arrays of
Guido van Rossum <guido@python.org>
parents: 4503
diff changeset
685 if (n < MINSIZE) {
4690
c2b831f923c2 Some more tuning of quicksort: use pointers instead of indexing.
Guido van Rossum <guido@python.org>
parents: 4673
diff changeset
686 if (insertionsort(lo, n, compare) < 0)
4673
a3cdc8164990 Added new quicksort implementation, tailored to sorting arrays of
Guido van Rossum <guido@python.org>
parents: 4503
diff changeset
687 return -1;
a3cdc8164990 Added new quicksort implementation, tailored to sorting arrays of
Guido van Rossum <guido@python.org>
parents: 4503
diff changeset
688 continue;
a3cdc8164990 Added new quicksort implementation, tailored to sorting arrays of
Guido van Rossum <guido@python.org>
parents: 4503
diff changeset
689 }
a3cdc8164990 Added new quicksort implementation, tailored to sorting arrays of
Guido van Rossum <guido@python.org>
parents: 4503
diff changeset
690
4690
c2b831f923c2 Some more tuning of quicksort: use pointers instead of indexing.
Guido van Rossum <guido@python.org>
parents: 4673
diff changeset
691 /* Choose median of first, middle and last item as pivot */
c2b831f923c2 Some more tuning of quicksort: use pointers instead of indexing.
Guido van Rossum <guido@python.org>
parents: 4673
diff changeset
692
c2b831f923c2 Some more tuning of quicksort: use pointers instead of indexing.
Guido van Rossum <guido@python.org>
parents: 4673
diff changeset
693 l = lo + (n>>1); /* Middle */
c2b831f923c2 Some more tuning of quicksort: use pointers instead of indexing.
Guido van Rossum <guido@python.org>
parents: 4673
diff changeset
694 r = hi - 1; /* Last */
c2b831f923c2 Some more tuning of quicksort: use pointers instead of indexing.
Guido van Rossum <guido@python.org>
parents: 4673
diff changeset
695 k = docompare(*lo, *l, compare);
4673
a3cdc8164990 Added new quicksort implementation, tailored to sorting arrays of
Guido van Rossum <guido@python.org>
parents: 4503
diff changeset
696 if (k == CMPERROR)
a3cdc8164990 Added new quicksort implementation, tailored to sorting arrays of
Guido van Rossum <guido@python.org>
parents: 4503
diff changeset
697 return -1;
a3cdc8164990 Added new quicksort implementation, tailored to sorting arrays of
Guido van Rossum <guido@python.org>
parents: 4503
diff changeset
698 if (k < 0)
4690
c2b831f923c2 Some more tuning of quicksort: use pointers instead of indexing.
Guido van Rossum <guido@python.org>
parents: 4673
diff changeset
699 { tmp = *lo; *lo = *l; *l = tmp; }
c2b831f923c2 Some more tuning of quicksort: use pointers instead of indexing.
Guido van Rossum <guido@python.org>
parents: 4673
diff changeset
700 k = docompare(*r, *l, compare);
4673
a3cdc8164990 Added new quicksort implementation, tailored to sorting arrays of
Guido van Rossum <guido@python.org>
parents: 4503
diff changeset
701 if (k == CMPERROR)
a3cdc8164990 Added new quicksort implementation, tailored to sorting arrays of
Guido van Rossum <guido@python.org>
parents: 4503
diff changeset
702 return -1;
a3cdc8164990 Added new quicksort implementation, tailored to sorting arrays of
Guido van Rossum <guido@python.org>
parents: 4503
diff changeset
703 if (k < 0)
4690
c2b831f923c2 Some more tuning of quicksort: use pointers instead of indexing.
Guido van Rossum <guido@python.org>
parents: 4673
diff changeset
704 { tmp = *r; *r = *l; *l = tmp; }
c2b831f923c2 Some more tuning of quicksort: use pointers instead of indexing.
Guido van Rossum <guido@python.org>
parents: 4673
diff changeset
705 k = docompare(*r, *lo, compare);
4673
a3cdc8164990 Added new quicksort implementation, tailored to sorting arrays of
Guido van Rossum <guido@python.org>
parents: 4503
diff changeset
706 if (k == CMPERROR)
a3cdc8164990 Added new quicksort implementation, tailored to sorting arrays of
Guido van Rossum <guido@python.org>
parents: 4503
diff changeset
707 return -1;
a3cdc8164990 Added new quicksort implementation, tailored to sorting arrays of
Guido van Rossum <guido@python.org>
parents: 4503
diff changeset
708 if (k < 0)
4690
c2b831f923c2 Some more tuning of quicksort: use pointers instead of indexing.
Guido van Rossum <guido@python.org>
parents: 4673
diff changeset
709 { tmp = *r; *r = *lo; *lo = tmp; }
c2b831f923c2 Some more tuning of quicksort: use pointers instead of indexing.
Guido van Rossum <guido@python.org>
parents: 4673
diff changeset
710 pivot = *lo;
4673
a3cdc8164990 Added new quicksort implementation, tailored to sorting arrays of
Guido van Rossum <guido@python.org>
parents: 4503
diff changeset
711
a3cdc8164990 Added new quicksort implementation, tailored to sorting arrays of
Guido van Rossum <guido@python.org>
parents: 4503
diff changeset
712 /* Partition the array */
4690
c2b831f923c2 Some more tuning of quicksort: use pointers instead of indexing.
Guido van Rossum <guido@python.org>
parents: 4673
diff changeset
713 l = lo;
c2b831f923c2 Some more tuning of quicksort: use pointers instead of indexing.
Guido van Rossum <guido@python.org>
parents: 4673
diff changeset
714 r = hi;
4673
a3cdc8164990 Added new quicksort implementation, tailored to sorting arrays of
Guido van Rossum <guido@python.org>
parents: 4503
diff changeset
715 for (;;) {
a3cdc8164990 Added new quicksort implementation, tailored to sorting arrays of
Guido van Rossum <guido@python.org>
parents: 4503
diff changeset
716 /* Move left index to element > pivot */
4690
c2b831f923c2 Some more tuning of quicksort: use pointers instead of indexing.
Guido van Rossum <guido@python.org>
parents: 4673
diff changeset
717 while (++l < hi) {
c2b831f923c2 Some more tuning of quicksort: use pointers instead of indexing.
Guido van Rossum <guido@python.org>
parents: 4673
diff changeset
718 k = docompare(*l, pivot, compare);
4673
a3cdc8164990 Added new quicksort implementation, tailored to sorting arrays of
Guido van Rossum <guido@python.org>
parents: 4503
diff changeset
719 if (k == CMPERROR)
a3cdc8164990 Added new quicksort implementation, tailored to sorting arrays of
Guido van Rossum <guido@python.org>
parents: 4503
diff changeset
720 return -1;
a3cdc8164990 Added new quicksort implementation, tailored to sorting arrays of
Guido van Rossum <guido@python.org>
parents: 4503
diff changeset
721 if (k > 0)
a3cdc8164990 Added new quicksort implementation, tailored to sorting arrays of
Guido van Rossum <guido@python.org>
parents: 4503
diff changeset
722 break;
a3cdc8164990 Added new quicksort implementation, tailored to sorting arrays of
Guido van Rossum <guido@python.org>
parents: 4503
diff changeset
723 }
a3cdc8164990 Added new quicksort implementation, tailored to sorting arrays of
Guido van Rossum <guido@python.org>
parents: 4503
diff changeset
724 /* Move right index to element < pivot */
4690
c2b831f923c2 Some more tuning of quicksort: use pointers instead of indexing.
Guido van Rossum <guido@python.org>
parents: 4673
diff changeset
725 while (--r > lo) {
c2b831f923c2 Some more tuning of quicksort: use pointers instead of indexing.
Guido van Rossum <guido@python.org>
parents: 4673
diff changeset
726 k = docompare(*r, pivot, compare);
4673
a3cdc8164990 Added new quicksort implementation, tailored to sorting arrays of
Guido van Rossum <guido@python.org>
parents: 4503
diff changeset
727 if (k == CMPERROR)
a3cdc8164990 Added new quicksort implementation, tailored to sorting arrays of
Guido van Rossum <guido@python.org>
parents: 4503
diff changeset
728 return -1;
a3cdc8164990 Added new quicksort implementation, tailored to sorting arrays of
Guido van Rossum <guido@python.org>
parents: 4503
diff changeset
729 if (k < 0)
a3cdc8164990 Added new quicksort implementation, tailored to sorting arrays of
Guido van Rossum <guido@python.org>
parents: 4503
diff changeset
730 break;
a3cdc8164990 Added new quicksort implementation, tailored to sorting arrays of
Guido van Rossum <guido@python.org>
parents: 4503
diff changeset
731 }
a3cdc8164990 Added new quicksort implementation, tailored to sorting arrays of
Guido van Rossum <guido@python.org>
parents: 4503
diff changeset
732 /* If they met, we're through */
a3cdc8164990 Added new quicksort implementation, tailored to sorting arrays of
Guido van Rossum <guido@python.org>
parents: 4503
diff changeset
733 if (r < l)
a3cdc8164990 Added new quicksort implementation, tailored to sorting arrays of
Guido van Rossum <guido@python.org>
parents: 4503
diff changeset
734 break;
a3cdc8164990 Added new quicksort implementation, tailored to sorting arrays of
Guido van Rossum <guido@python.org>
parents: 4503
diff changeset
735 /* Swap elements and continue */
4690
c2b831f923c2 Some more tuning of quicksort: use pointers instead of indexing.
Guido van Rossum <guido@python.org>
parents: 4673
diff changeset
736 { tmp = *l; *l = *r; *r = tmp; }
4673
a3cdc8164990 Added new quicksort implementation, tailored to sorting arrays of
Guido van Rossum <guido@python.org>
parents: 4503
diff changeset
737 }
a3cdc8164990 Added new quicksort implementation, tailored to sorting arrays of
Guido van Rossum <guido@python.org>
parents: 4503
diff changeset
738
a3cdc8164990 Added new quicksort implementation, tailored to sorting arrays of
Guido van Rossum <guido@python.org>
parents: 4503
diff changeset
739 /* Move the pivot into the middle */
4690
c2b831f923c2 Some more tuning of quicksort: use pointers instead of indexing.
Guido van Rossum <guido@python.org>
parents: 4673
diff changeset
740 { tmp = *lo; *lo = *r; *r = tmp; }
4673
a3cdc8164990 Added new quicksort implementation, tailored to sorting arrays of
Guido van Rossum <guido@python.org>
parents: 4503
diff changeset
741
a3cdc8164990 Added new quicksort implementation, tailored to sorting arrays of
Guido van Rossum <guido@python.org>
parents: 4503
diff changeset
742 /* We have now reached the following conditions:
4690
c2b831f923c2 Some more tuning of quicksort: use pointers instead of indexing.
Guido van Rossum <guido@python.org>
parents: 4673
diff changeset
743 lo <= r < l <= hi
c2b831f923c2 Some more tuning of quicksort: use pointers instead of indexing.
Guido van Rossum <guido@python.org>
parents: 4673
diff changeset
744 all x in [lo,r) are <= pivot
c2b831f923c2 Some more tuning of quicksort: use pointers instead of indexing.
Guido van Rossum <guido@python.org>
parents: 4673
diff changeset
745 all x in [r,l) are == pivot
c2b831f923c2 Some more tuning of quicksort: use pointers instead of indexing.
Guido van Rossum <guido@python.org>
parents: 4673
diff changeset
746 all x in [l,hi) are >= pivot
c2b831f923c2 Some more tuning of quicksort: use pointers instead of indexing.
Guido van Rossum <guido@python.org>
parents: 4673
diff changeset
747 The partitions are [lo,r) and [l,hi)
4673
a3cdc8164990 Added new quicksort implementation, tailored to sorting arrays of
Guido van Rossum <guido@python.org>
parents: 4503
diff changeset
748 */
a3cdc8164990 Added new quicksort implementation, tailored to sorting arrays of
Guido van Rossum <guido@python.org>
parents: 4503
diff changeset
749
a3cdc8164990 Added new quicksort implementation, tailored to sorting arrays of
Guido van Rossum <guido@python.org>
parents: 4503
diff changeset
750 /* Push biggest partition first */
4690
c2b831f923c2 Some more tuning of quicksort: use pointers instead of indexing.
Guido van Rossum <guido@python.org>
parents: 4673
diff changeset
751 n = r - lo;
c2b831f923c2 Some more tuning of quicksort: use pointers instead of indexing.
Guido van Rossum <guido@python.org>
parents: 4673
diff changeset
752 n2 = hi - l;
c2b831f923c2 Some more tuning of quicksort: use pointers instead of indexing.
Guido van Rossum <guido@python.org>
parents: 4673
diff changeset
753 if (n > n2) {
4673
a3cdc8164990 Added new quicksort implementation, tailored to sorting arrays of
Guido van Rossum <guido@python.org>
parents: 4503
diff changeset
754 /* First one is bigger */
4690
c2b831f923c2 Some more tuning of quicksort: use pointers instead of indexing.
Guido van Rossum <guido@python.org>
parents: 4673
diff changeset
755 if (n > 1) {
c2b831f923c2 Some more tuning of quicksort: use pointers instead of indexing.
Guido van Rossum <guido@python.org>
parents: 4673
diff changeset
756 lostack[top] = lo;
c2b831f923c2 Some more tuning of quicksort: use pointers instead of indexing.
Guido van Rossum <guido@python.org>
parents: 4673
diff changeset
757 histack[top++] = r;
4673
a3cdc8164990 Added new quicksort implementation, tailored to sorting arrays of
Guido van Rossum <guido@python.org>
parents: 4503
diff changeset
758 if (n2 > 1) {
4690
c2b831f923c2 Some more tuning of quicksort: use pointers instead of indexing.
Guido van Rossum <guido@python.org>
parents: 4673
diff changeset
759 lostack[top] = l;
c2b831f923c2 Some more tuning of quicksort: use pointers instead of indexing.
Guido van Rossum <guido@python.org>
parents: 4673
diff changeset
760 histack[top++] = hi;
4673
a3cdc8164990 Added new quicksort implementation, tailored to sorting arrays of
Guido van Rossum <guido@python.org>
parents: 4503
diff changeset
761 }
a3cdc8164990 Added new quicksort implementation, tailored to sorting arrays of
Guido van Rossum <guido@python.org>
parents: 4503
diff changeset
762 }
a3cdc8164990 Added new quicksort implementation, tailored to sorting arrays of
Guido van Rossum <guido@python.org>
parents: 4503
diff changeset
763 } else {
a3cdc8164990 Added new quicksort implementation, tailored to sorting arrays of
Guido van Rossum <guido@python.org>
parents: 4503
diff changeset
764 /* Second one is bigger */
a3cdc8164990 Added new quicksort implementation, tailored to sorting arrays of
Guido van Rossum <guido@python.org>
parents: 4503
diff changeset
765 if (n2 > 1) {
4690
c2b831f923c2 Some more tuning of quicksort: use pointers instead of indexing.
Guido van Rossum <guido@python.org>
parents: 4673
diff changeset
766 lostack[top] = l;
c2b831f923c2 Some more tuning of quicksort: use pointers instead of indexing.
Guido van Rossum <guido@python.org>
parents: 4673
diff changeset
767 histack[top++] = hi;
c2b831f923c2 Some more tuning of quicksort: use pointers instead of indexing.
Guido van Rossum <guido@python.org>
parents: 4673
diff changeset
768 if (n > 1) {
c2b831f923c2 Some more tuning of quicksort: use pointers instead of indexing.
Guido van Rossum <guido@python.org>
parents: 4673
diff changeset
769 lostack[top] = lo;
c2b831f923c2 Some more tuning of quicksort: use pointers instead of indexing.
Guido van Rossum <guido@python.org>
parents: 4673
diff changeset
770 histack[top++] = r;
4673
a3cdc8164990 Added new quicksort implementation, tailored to sorting arrays of
Guido van Rossum <guido@python.org>
parents: 4503
diff changeset
771 }
a3cdc8164990 Added new quicksort implementation, tailored to sorting arrays of
Guido van Rossum <guido@python.org>
parents: 4503
diff changeset
772 }
a3cdc8164990 Added new quicksort implementation, tailored to sorting arrays of
Guido van Rossum <guido@python.org>
parents: 4503
diff changeset
773 }
a3cdc8164990 Added new quicksort implementation, tailored to sorting arrays of
Guido van Rossum <guido@python.org>
parents: 4503
diff changeset
774
a3cdc8164990 Added new quicksort implementation, tailored to sorting arrays of
Guido van Rossum <guido@python.org>
parents: 4503
diff changeset
775 /* Should assert top < STACKSIZE-1 */
a3cdc8164990 Added new quicksort implementation, tailored to sorting arrays of
Guido van Rossum <guido@python.org>
parents: 4503
diff changeset
776 }
a3cdc8164990 Added new quicksort implementation, tailored to sorting arrays of
Guido van Rossum <guido@python.org>
parents: 4503
diff changeset
777
a3cdc8164990 Added new quicksort implementation, tailored to sorting arrays of
Guido van Rossum <guido@python.org>
parents: 4503
diff changeset
778 /* Succes */
a3cdc8164990 Added new quicksort implementation, tailored to sorting arrays of
Guido van Rossum <guido@python.org>
parents: 4503
diff changeset
779 return 0;
a3cdc8164990 Added new quicksort implementation, tailored to sorting arrays of
Guido van Rossum <guido@python.org>
parents: 4503
diff changeset
780 }
a3cdc8164990 Added new quicksort implementation, tailored to sorting arrays of
Guido van Rossum <guido@python.org>
parents: 4503
diff changeset
781
5396
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
782 static PyObject *
4673
a3cdc8164990 Added new quicksort implementation, tailored to sorting arrays of
Guido van Rossum <guido@python.org>
parents: 4503
diff changeset
783 listsort(self, compare)
5396
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
784 PyListObject *self;
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
785 PyObject *compare;
4673
a3cdc8164990 Added new quicksort implementation, tailored to sorting arrays of
Guido van Rossum <guido@python.org>
parents: 4503
diff changeset
786 {
a3cdc8164990 Added new quicksort implementation, tailored to sorting arrays of
Guido van Rossum <guido@python.org>
parents: 4503
diff changeset
787 /* XXX Don't you *dare* changing the list's length in compare()! */
a3cdc8164990 Added new quicksort implementation, tailored to sorting arrays of
Guido van Rossum <guido@python.org>
parents: 4503
diff changeset
788 if (quicksort(self->ob_item, self->ob_size, compare) < 0)
a3cdc8164990 Added new quicksort implementation, tailored to sorting arrays of
Guido van Rossum <guido@python.org>
parents: 4503
diff changeset
789 return NULL;
5396
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
790 Py_INCREF(Py_None);
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
791 return Py_None;
4673
a3cdc8164990 Added new quicksort implementation, tailored to sorting arrays of
Guido van Rossum <guido@python.org>
parents: 4503
diff changeset
792 }
a3cdc8164990 Added new quicksort implementation, tailored to sorting arrays of
Guido van Rossum <guido@python.org>
parents: 4503
diff changeset
793
a3cdc8164990 Added new quicksort implementation, tailored to sorting arrays of
Guido van Rossum <guido@python.org>
parents: 4503
diff changeset
794 #else /* !NEWSORT */
a3cdc8164990 Added new quicksort implementation, tailored to sorting arrays of
Guido van Rossum <guido@python.org>
parents: 4503
diff changeset
795
5396
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
796 static PyObject *comparefunc;
920
8c73c5f3b6ca listobject.c: added optional cmp function to list.sort().
Guido van Rossum <guido@python.org>
parents: 795
diff changeset
797
6
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
798 static int
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
799 cmp(v, w)
1836
1203f0629527 Correct problems found by THINK C 6.0
Guido van Rossum <guido@python.org>
parents: 1405
diff changeset
800 const ANY *v, *w;
6
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
801 {
5396
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
802 PyObject *t, *res;
920
8c73c5f3b6ca listobject.c: added optional cmp function to list.sort().
Guido van Rossum <guido@python.org>
parents: 795
diff changeset
803 long i;
8c73c5f3b6ca listobject.c: added optional cmp function to list.sort().
Guido van Rossum <guido@python.org>
parents: 795
diff changeset
804
5396
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
805 if (PyErr_Occurred())
920
8c73c5f3b6ca listobject.c: added optional cmp function to list.sort().
Guido van Rossum <guido@python.org>
parents: 795
diff changeset
806 return 0;
8c73c5f3b6ca listobject.c: added optional cmp function to list.sort().
Guido van Rossum <guido@python.org>
parents: 795
diff changeset
807
1836
1203f0629527 Correct problems found by THINK C 6.0
Guido van Rossum <guido@python.org>
parents: 1405
diff changeset
808 if (comparefunc == NULL)
5396
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
809 return PyObject_Compare(* (PyObject **) v, * (PyObject **) w);
920
8c73c5f3b6ca listobject.c: added optional cmp function to list.sort().
Guido van Rossum <guido@python.org>
parents: 795
diff changeset
810
8c73c5f3b6ca listobject.c: added optional cmp function to list.sort().
Guido van Rossum <guido@python.org>
parents: 795
diff changeset
811 /* Call the user-supplied comparison function */
5396
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
812 t = Py_BuildValue("(OO)", * (PyObject **) v, * (PyObject **) w);
920
8c73c5f3b6ca listobject.c: added optional cmp function to list.sort().
Guido van Rossum <guido@python.org>
parents: 795
diff changeset
813 if (t == NULL)
8c73c5f3b6ca listobject.c: added optional cmp function to list.sort().
Guido van Rossum <guido@python.org>
parents: 795
diff changeset
814 return 0;
5396
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
815 res = PyEval_CallObject(comparefunc, t);
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
816 Py_DECREF(t);
920
8c73c5f3b6ca listobject.c: added optional cmp function to list.sort().
Guido van Rossum <guido@python.org>
parents: 795
diff changeset
817 if (res == NULL)
8c73c5f3b6ca listobject.c: added optional cmp function to list.sort().
Guido van Rossum <guido@python.org>
parents: 795
diff changeset
818 return 0;
5396
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
819 if (!PyInt_Check(res)) {
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
820 PyErr_SetString(PyExc_TypeError,
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
821 "comparison function should return int");
920
8c73c5f3b6ca listobject.c: added optional cmp function to list.sort().
Guido van Rossum <guido@python.org>
parents: 795
diff changeset
822 i = 0;
8c73c5f3b6ca listobject.c: added optional cmp function to list.sort().
Guido van Rossum <guido@python.org>
parents: 795
diff changeset
823 }
8c73c5f3b6ca listobject.c: added optional cmp function to list.sort().
Guido van Rossum <guido@python.org>
parents: 795
diff changeset
824 else {
5396
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
825 i = PyInt_AsLong(res);
920
8c73c5f3b6ca listobject.c: added optional cmp function to list.sort().
Guido van Rossum <guido@python.org>
parents: 795
diff changeset
826 if (i < 0)
8c73c5f3b6ca listobject.c: added optional cmp function to list.sort().
Guido van Rossum <guido@python.org>
parents: 795
diff changeset
827 i = -1;
8c73c5f3b6ca listobject.c: added optional cmp function to list.sort().
Guido van Rossum <guido@python.org>
parents: 795
diff changeset
828 else if (i > 0)
8c73c5f3b6ca listobject.c: added optional cmp function to list.sort().
Guido van Rossum <guido@python.org>
parents: 795
diff changeset
829 i = 1;
8c73c5f3b6ca listobject.c: added optional cmp function to list.sort().
Guido van Rossum <guido@python.org>
parents: 795
diff changeset
830 }
5396
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
831 Py_DECREF(res);
920
8c73c5f3b6ca listobject.c: added optional cmp function to list.sort().
Guido van Rossum <guido@python.org>
parents: 795
diff changeset
832 return (int) i;
6
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
833 }
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
834
5396
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
835 static PyObject *
6
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
836 listsort(self, args)
5396
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
837 PyListObject *self;
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
838 PyObject *args;
6
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
839 {
5396
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
840 PyObject *save_comparefunc;
920
8c73c5f3b6ca listobject.c: added optional cmp function to list.sort().
Guido van Rossum <guido@python.org>
parents: 795
diff changeset
841 if (self->ob_size <= 1) {
5396
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
842 Py_INCREF(Py_None);
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
843 return Py_None;
6
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
844 }
1836
1203f0629527 Correct problems found by THINK C 6.0
Guido van Rossum <guido@python.org>
parents: 1405
diff changeset
845 save_comparefunc = comparefunc;
1203f0629527 Correct problems found by THINK C 6.0
Guido van Rossum <guido@python.org>
parents: 1405
diff changeset
846 comparefunc = args;
1203f0629527 Correct problems found by THINK C 6.0
Guido van Rossum <guido@python.org>
parents: 1405
diff changeset
847 if (comparefunc != NULL) {
920
8c73c5f3b6ca listobject.c: added optional cmp function to list.sort().
Guido van Rossum <guido@python.org>
parents: 795
diff changeset
848 /* Test the comparison function for obvious errors */
1836
1203f0629527 Correct problems found by THINK C 6.0
Guido van Rossum <guido@python.org>
parents: 1405
diff changeset
849 (void) cmp((ANY *)&self->ob_item[0], (ANY *)&self->ob_item[1]);
5396
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
850 if (PyErr_Occurred()) {
1836
1203f0629527 Correct problems found by THINK C 6.0
Guido van Rossum <guido@python.org>
parents: 1405
diff changeset
851 comparefunc = save_comparefunc;
920
8c73c5f3b6ca listobject.c: added optional cmp function to list.sort().
Guido van Rossum <guido@python.org>
parents: 795
diff changeset
852 return NULL;
8c73c5f3b6ca listobject.c: added optional cmp function to list.sort().
Guido van Rossum <guido@python.org>
parents: 795
diff changeset
853 }
8c73c5f3b6ca listobject.c: added optional cmp function to list.sort().
Guido van Rossum <guido@python.org>
parents: 795
diff changeset
854 }
8c73c5f3b6ca listobject.c: added optional cmp function to list.sort().
Guido van Rossum <guido@python.org>
parents: 795
diff changeset
855 qsort((char *)self->ob_item,
5396
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
856 (int) self->ob_size, sizeof(PyObject *), cmp);
1836
1203f0629527 Correct problems found by THINK C 6.0
Guido van Rossum <guido@python.org>
parents: 1405
diff changeset
857 comparefunc = save_comparefunc;
5396
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
858 if (PyErr_Occurred())
6
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
859 return NULL;
5396
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
860 Py_INCREF(Py_None);
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
861 return Py_None;
6
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
862 }
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
863
4673
a3cdc8164990 Added new quicksort implementation, tailored to sorting arrays of
Guido van Rossum <guido@python.org>
parents: 4503
diff changeset
864 #endif
a3cdc8164990 Added new quicksort implementation, tailored to sorting arrays of
Guido van Rossum <guido@python.org>
parents: 4503
diff changeset
865
5396
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
866 static PyObject *
155
896c825f2f71 Added repeat (for list*integet).
Guido van Rossum <guido@python.org>
parents: 145
diff changeset
867 listreverse(self, args)
5396
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
868 PyListObject *self;
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
869 PyObject *args;
155
896c825f2f71 Added repeat (for list*integet).
Guido van Rossum <guido@python.org>
parents: 145
diff changeset
870 {
5396
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
871 register PyObject **p, **q;
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
872 register PyObject *tmp;
155
896c825f2f71 Added repeat (for list*integet).
Guido van Rossum <guido@python.org>
parents: 145
diff changeset
873
896c825f2f71 Added repeat (for list*integet).
Guido van Rossum <guido@python.org>
parents: 145
diff changeset
874 if (args != NULL) {
5396
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
875 PyErr_BadArgument();
155
896c825f2f71 Added repeat (for list*integet).
Guido van Rossum <guido@python.org>
parents: 145
diff changeset
876 return NULL;
896c825f2f71 Added repeat (for list*integet).
Guido van Rossum <guido@python.org>
parents: 145
diff changeset
877 }
896c825f2f71 Added repeat (for list*integet).
Guido van Rossum <guido@python.org>
parents: 145
diff changeset
878
896c825f2f71 Added repeat (for list*integet).
Guido van Rossum <guido@python.org>
parents: 145
diff changeset
879 if (self->ob_size > 1) {
896c825f2f71 Added repeat (for list*integet).
Guido van Rossum <guido@python.org>
parents: 145
diff changeset
880 for (p = self->ob_item, q = self->ob_item + self->ob_size - 1;
896c825f2f71 Added repeat (for list*integet).
Guido van Rossum <guido@python.org>
parents: 145
diff changeset
881 p < q; p++, q--) {
896c825f2f71 Added repeat (for list*integet).
Guido van Rossum <guido@python.org>
parents: 145
diff changeset
882 tmp = *p;
896c825f2f71 Added repeat (for list*integet).
Guido van Rossum <guido@python.org>
parents: 145
diff changeset
883 *p = *q;
896c825f2f71 Added repeat (for list*integet).
Guido van Rossum <guido@python.org>
parents: 145
diff changeset
884 *q = tmp;
896c825f2f71 Added repeat (for list*integet).
Guido van Rossum <guido@python.org>
parents: 145
diff changeset
885 }
896c825f2f71 Added repeat (for list*integet).
Guido van Rossum <guido@python.org>
parents: 145
diff changeset
886 }
896c825f2f71 Added repeat (for list*integet).
Guido van Rossum <guido@python.org>
parents: 145
diff changeset
887
5396
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
888 Py_INCREF(Py_None);
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
889 return Py_None;
155
896c825f2f71 Added repeat (for list*integet).
Guido van Rossum <guido@python.org>
parents: 145
diff changeset
890 }
896c825f2f71 Added repeat (for list*integet).
Guido van Rossum <guido@python.org>
parents: 145
diff changeset
891
47
05057e3660f8 Added external interface to sort a list.
Guido van Rossum <guido@python.org>
parents: 27
diff changeset
892 int
5396
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
893 PyList_Reverse(v)
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
894 PyObject *v;
2159
a619a61aad1e added reverselist; free recycling bin on error exit
Guido van Rossum <guido@python.org>
parents: 2143
diff changeset
895 {
5396
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
896 if (v == NULL || !PyList_Check(v)) {
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
897 PyErr_BadInternalCall();
2159
a619a61aad1e added reverselist; free recycling bin on error exit
Guido van Rossum <guido@python.org>
parents: 2143
diff changeset
898 return -1;
a619a61aad1e added reverselist; free recycling bin on error exit
Guido van Rossum <guido@python.org>
parents: 2143
diff changeset
899 }
5396
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
900 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
901 if (v == NULL)
a619a61aad1e added reverselist; free recycling bin on error exit
Guido van Rossum <guido@python.org>
parents: 2143
diff changeset
902 return -1;
5396
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
903 Py_DECREF(v);
2159
a619a61aad1e added reverselist; free recycling bin on error exit
Guido van Rossum <guido@python.org>
parents: 2143
diff changeset
904 return 0;
a619a61aad1e added reverselist; free recycling bin on error exit
Guido van Rossum <guido@python.org>
parents: 2143
diff changeset
905 }
a619a61aad1e added reverselist; free recycling bin on error exit
Guido van Rossum <guido@python.org>
parents: 2143
diff changeset
906
a619a61aad1e added reverselist; free recycling bin on error exit
Guido van Rossum <guido@python.org>
parents: 2143
diff changeset
907 int
5396
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
908 PyList_Sort(v)
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
909 PyObject *v;
47
05057e3660f8 Added external interface to sort a list.
Guido van Rossum <guido@python.org>
parents: 27
diff changeset
910 {
5396
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
911 if (v == NULL || !PyList_Check(v)) {
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
912 PyErr_BadInternalCall();
47
05057e3660f8 Added external interface to sort a list.
Guido van Rossum <guido@python.org>
parents: 27
diff changeset
913 return -1;
05057e3660f8 Added external interface to sort a list.
Guido van Rossum <guido@python.org>
parents: 27
diff changeset
914 }
5396
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
915 v = listsort((PyListObject *)v, (PyObject *)NULL);
47
05057e3660f8 Added external interface to sort a list.
Guido van Rossum <guido@python.org>
parents: 27
diff changeset
916 if (v == NULL)
05057e3660f8 Added external interface to sort a list.
Guido van Rossum <guido@python.org>
parents: 27
diff changeset
917 return -1;
5396
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
918 Py_DECREF(v);
47
05057e3660f8 Added external interface to sort a list.
Guido van Rossum <guido@python.org>
parents: 27
diff changeset
919 return 0;
05057e3660f8 Added external interface to sort a list.
Guido van Rossum <guido@python.org>
parents: 27
diff changeset
920 }
05057e3660f8 Added external interface to sort a list.
Guido van Rossum <guido@python.org>
parents: 27
diff changeset
921
5396
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
922 PyObject *
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
923 PyList_AsTuple(v)
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
924 PyObject *v;
1836
1203f0629527 Correct problems found by THINK C 6.0
Guido van Rossum <guido@python.org>
parents: 1405
diff changeset
925 {
5396
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
926 PyObject *w;
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
927 PyObject **p;
1836
1203f0629527 Correct problems found by THINK C 6.0
Guido van Rossum <guido@python.org>
parents: 1405
diff changeset
928 int n;
5396
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
929 if (v == NULL || !PyList_Check(v)) {
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
930 PyErr_BadInternalCall();
1836
1203f0629527 Correct problems found by THINK C 6.0
Guido van Rossum <guido@python.org>
parents: 1405
diff changeset
931 return NULL;
1203f0629527 Correct problems found by THINK C 6.0
Guido van Rossum <guido@python.org>
parents: 1405
diff changeset
932 }
5396
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
933 n = ((PyListObject *)v)->ob_size;
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
934 w = PyTuple_New(n);
1836
1203f0629527 Correct problems found by THINK C 6.0
Guido van Rossum <guido@python.org>
parents: 1405
diff changeset
935 if (w == NULL)
1203f0629527 Correct problems found by THINK C 6.0
Guido van Rossum <guido@python.org>
parents: 1405
diff changeset
936 return NULL;
5396
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
937 p = ((PyTupleObject *)w)->ob_item;
1836
1203f0629527 Correct problems found by THINK C 6.0
Guido van Rossum <guido@python.org>
parents: 1405
diff changeset
938 memcpy((ANY *)p,
5396
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
939 (ANY *)((PyListObject *)v)->ob_item,
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
940 n*sizeof(PyObject *));
1836
1203f0629527 Correct problems found by THINK C 6.0
Guido van Rossum <guido@python.org>
parents: 1405
diff changeset
941 while (--n >= 0) {
5396
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
942 Py_INCREF(*p);
1836
1203f0629527 Correct problems found by THINK C 6.0
Guido van Rossum <guido@python.org>
parents: 1405
diff changeset
943 p++;
1203f0629527 Correct problems found by THINK C 6.0
Guido van Rossum <guido@python.org>
parents: 1405
diff changeset
944 }
1203f0629527 Correct problems found by THINK C 6.0
Guido van Rossum <guido@python.org>
parents: 1405
diff changeset
945 return w;
1203f0629527 Correct problems found by THINK C 6.0
Guido van Rossum <guido@python.org>
parents: 1405
diff changeset
946 }
1203f0629527 Correct problems found by THINK C 6.0
Guido van Rossum <guido@python.org>
parents: 1405
diff changeset
947
5396
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
948 static PyObject *
155
896c825f2f71 Added repeat (for list*integet).
Guido van Rossum <guido@python.org>
parents: 145
diff changeset
949 listindex(self, args)
5396
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
950 PyListObject *self;
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
951 PyObject *args;
155
896c825f2f71 Added repeat (for list*integet).
Guido van Rossum <guido@python.org>
parents: 145
diff changeset
952 {
896c825f2f71 Added repeat (for list*integet).
Guido van Rossum <guido@python.org>
parents: 145
diff changeset
953 int i;
896c825f2f71 Added repeat (for list*integet).
Guido van Rossum <guido@python.org>
parents: 145
diff changeset
954
896c825f2f71 Added repeat (for list*integet).
Guido van Rossum <guido@python.org>
parents: 145
diff changeset
955 if (args == NULL) {
5396
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
956 PyErr_BadArgument();
155
896c825f2f71 Added repeat (for list*integet).
Guido van Rossum <guido@python.org>
parents: 145
diff changeset
957 return NULL;
896c825f2f71 Added repeat (for list*integet).
Guido van Rossum <guido@python.org>
parents: 145
diff changeset
958 }
896c825f2f71 Added repeat (for list*integet).
Guido van Rossum <guido@python.org>
parents: 145
diff changeset
959 for (i = 0; i < self->ob_size; i++) {
5396
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
960 if (PyObject_Compare(self->ob_item[i], args) == 0)
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
961 return PyInt_FromLong((long)i);
5610
10e9cfa010f0 PyObject_Compare can raise an exception now.
Guido van Rossum <guido@python.org>
parents: 5396
diff changeset
962 if (PyErr_Occurred())
10e9cfa010f0 PyObject_Compare can raise an exception now.
Guido van Rossum <guido@python.org>
parents: 5396
diff changeset
963 return NULL;
155
896c825f2f71 Added repeat (for list*integet).
Guido van Rossum <guido@python.org>
parents: 145
diff changeset
964 }
5396
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
965 PyErr_SetString(PyExc_ValueError, "list.index(x): x not in list");
155
896c825f2f71 Added repeat (for list*integet).
Guido van Rossum <guido@python.org>
parents: 145
diff changeset
966 return NULL;
896c825f2f71 Added repeat (for list*integet).
Guido van Rossum <guido@python.org>
parents: 145
diff changeset
967 }
896c825f2f71 Added repeat (for list*integet).
Guido van Rossum <guido@python.org>
parents: 145
diff changeset
968
5396
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
969 static PyObject *
394
8154385248d8 Added count() method.
Guido van Rossum <guido@python.org>
parents: 284
diff changeset
970 listcount(self, args)
5396
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
971 PyListObject *self;
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
972 PyObject *args;
394
8154385248d8 Added count() method.
Guido van Rossum <guido@python.org>
parents: 284
diff changeset
973 {
8154385248d8 Added count() method.
Guido van Rossum <guido@python.org>
parents: 284
diff changeset
974 int count = 0;
8154385248d8 Added count() method.
Guido van Rossum <guido@python.org>
parents: 284
diff changeset
975 int i;
8154385248d8 Added count() method.
Guido van Rossum <guido@python.org>
parents: 284
diff changeset
976
8154385248d8 Added count() method.
Guido van Rossum <guido@python.org>
parents: 284
diff changeset
977 if (args == NULL) {
5396
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
978 PyErr_BadArgument();
394
8154385248d8 Added count() method.
Guido van Rossum <guido@python.org>
parents: 284
diff changeset
979 return NULL;
8154385248d8 Added count() method.
Guido van Rossum <guido@python.org>
parents: 284
diff changeset
980 }
8154385248d8 Added count() method.
Guido van Rossum <guido@python.org>
parents: 284
diff changeset
981 for (i = 0; i < self->ob_size; i++) {
5396
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
982 if (PyObject_Compare(self->ob_item[i], args) == 0)
394
8154385248d8 Added count() method.
Guido van Rossum <guido@python.org>
parents: 284
diff changeset
983 count++;
5610
10e9cfa010f0 PyObject_Compare can raise an exception now.
Guido van Rossum <guido@python.org>
parents: 5396
diff changeset
984 if (PyErr_Occurred())
10e9cfa010f0 PyObject_Compare can raise an exception now.
Guido van Rossum <guido@python.org>
parents: 5396
diff changeset
985 return NULL;
394
8154385248d8 Added count() method.
Guido van Rossum <guido@python.org>
parents: 284
diff changeset
986 }
5396
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
987 return PyInt_FromLong((long)count);
394
8154385248d8 Added count() method.
Guido van Rossum <guido@python.org>
parents: 284
diff changeset
988 }
8154385248d8 Added count() method.
Guido van Rossum <guido@python.org>
parents: 284
diff changeset
989
5396
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
990 static PyObject *
155
896c825f2f71 Added repeat (for list*integet).
Guido van Rossum <guido@python.org>
parents: 145
diff changeset
991 listremove(self, args)
5396
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
992 PyListObject *self;
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
993 PyObject *args;
155
896c825f2f71 Added repeat (for list*integet).
Guido van Rossum <guido@python.org>
parents: 145
diff changeset
994 {
896c825f2f71 Added repeat (for list*integet).
Guido van Rossum <guido@python.org>
parents: 145
diff changeset
995 int i;
896c825f2f71 Added repeat (for list*integet).
Guido van Rossum <guido@python.org>
parents: 145
diff changeset
996
896c825f2f71 Added repeat (for list*integet).
Guido van Rossum <guido@python.org>
parents: 145
diff changeset
997 if (args == NULL) {
5396
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
998 PyErr_BadArgument();
155
896c825f2f71 Added repeat (for list*integet).
Guido van Rossum <guido@python.org>
parents: 145
diff changeset
999 return NULL;
896c825f2f71 Added repeat (for list*integet).
Guido van Rossum <guido@python.org>
parents: 145
diff changeset
1000 }
896c825f2f71 Added repeat (for list*integet).
Guido van Rossum <guido@python.org>
parents: 145
diff changeset
1001 for (i = 0; i < self->ob_size; i++) {
5396
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
1002 if (PyObject_Compare(self->ob_item[i], args) == 0) {
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
1003 if (list_ass_slice(self, i, i+1,
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
1004 (PyObject *)NULL) != 0)
155
896c825f2f71 Added repeat (for list*integet).
Guido van Rossum <guido@python.org>
parents: 145
diff changeset
1005 return NULL;
5396
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
1006 Py_INCREF(Py_None);
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
1007 return Py_None;
155
896c825f2f71 Added repeat (for list*integet).
Guido van Rossum <guido@python.org>
parents: 145
diff changeset
1008 }
5610
10e9cfa010f0 PyObject_Compare can raise an exception now.
Guido van Rossum <guido@python.org>
parents: 5396
diff changeset
1009 if (PyErr_Occurred())
10e9cfa010f0 PyObject_Compare can raise an exception now.
Guido van Rossum <guido@python.org>
parents: 5396
diff changeset
1010 return NULL;
155
896c825f2f71 Added repeat (for list*integet).
Guido van Rossum <guido@python.org>
parents: 145
diff changeset
1011 }
5396
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
1012 PyErr_SetString(PyExc_ValueError, "list.remove(x): x not in list");
155
896c825f2f71 Added repeat (for list*integet).
Guido van Rossum <guido@python.org>
parents: 145
diff changeset
1013 return NULL;
896c825f2f71 Added repeat (for list*integet).
Guido van Rossum <guido@python.org>
parents: 145
diff changeset
1014 }
896c825f2f71 Added repeat (for list*integet).
Guido van Rossum <guido@python.org>
parents: 145
diff changeset
1015
5396
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
1016 static PyMethodDef list_methods[] = {
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
1017 {"append", (PyCFunction)listappend},
5784
c043901fa1fe Reordered list of methods to hopefully put the most frequently used
Guido van Rossum <guido@python.org>
parents: 5610
diff changeset
1018 {"insert", (PyCFunction)listinsert},
c043901fa1fe Reordered list of methods to hopefully put the most frequently used
Guido van Rossum <guido@python.org>
parents: 5610
diff changeset
1019 {"remove", (PyCFunction)listremove},
5396
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
1020 {"index", (PyCFunction)listindex},
5784
c043901fa1fe Reordered list of methods to hopefully put the most frequently used
Guido van Rossum <guido@python.org>
parents: 5610
diff changeset
1021 {"count", (PyCFunction)listcount},
c043901fa1fe Reordered list of methods to hopefully put the most frequently used
Guido van Rossum <guido@python.org>
parents: 5610
diff changeset
1022 {"reverse", (PyCFunction)listreverse},
5396
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
1023 {"sort", (PyCFunction)listsort, 0},
6
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
1024 {NULL, NULL} /* sentinel */
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
1025 };
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
1026
5396
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
1027 static PyObject *
6
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
1028 list_getattr(f, name)
5396
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
1029 PyListObject *f;
6
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
1030 char *name;
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
1031 {
5396
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
1032 return Py_FindMethod(list_methods, (PyObject *)f, name);
6
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
1033 }
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
1034
5396
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
1035 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
1036 (inquiry)list_length, /*sq_length*/
1203f0629527 Correct problems found by THINK C 6.0
Guido van Rossum <guido@python.org>
parents: 1405
diff changeset
1037 (binaryfunc)list_concat, /*sq_concat*/
1203f0629527 Correct problems found by THINK C 6.0
Guido van Rossum <guido@python.org>
parents: 1405
diff changeset
1038 (intargfunc)list_repeat, /*sq_repeat*/
1203f0629527 Correct problems found by THINK C 6.0
Guido van Rossum <guido@python.org>
parents: 1405
diff changeset
1039 (intargfunc)list_item, /*sq_item*/
1203f0629527 Correct problems found by THINK C 6.0
Guido van Rossum <guido@python.org>
parents: 1405
diff changeset
1040 (intintargfunc)list_slice, /*sq_slice*/
1203f0629527 Correct problems found by THINK C 6.0
Guido van Rossum <guido@python.org>
parents: 1405
diff changeset
1041 (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
1042 (intintobjargproc)list_ass_slice, /*sq_ass_slice*/
6
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
1043 };
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
1044
5396
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
1045 PyTypeObject PyList_Type = {
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
1046 PyObject_HEAD_INIT(&PyType_Type)
6
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
1047 0,
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
1048 "list",
5396
d1447950fa04 Quickly renamed the last directory.
Guido van Rossum <guido@python.org>
parents: 5288
diff changeset
1049 sizeof(PyListObject),
6
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
1050 0,
1836
1203f0629527 Correct problems found by THINK C 6.0
Guido van Rossum <guido@python.org>
parents: 1405
diff changeset
1051 (destructor)list_dealloc, /*tp_dealloc*/
1203f0629527 Correct problems found by THINK C 6.0
Guido van Rossum <guido@python.org>
parents: 1405
diff changeset
1052 (printfunc)list_print, /*tp_print*/
1203f0629527 Correct problems found by THINK C 6.0
Guido van Rossum <guido@python.org>
parents: 1405
diff changeset
1053 (getattrfunc)list_getattr, /*tp_getattr*/
6
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
1054 0, /*tp_setattr*/
1836
1203f0629527 Correct problems found by THINK C 6.0
Guido van Rossum <guido@python.org>
parents: 1405
diff changeset
1055 (cmpfunc)list_compare, /*tp_compare*/
1203f0629527 Correct problems found by THINK C 6.0
Guido van Rossum <guido@python.org>
parents: 1405
diff changeset
1056 (reprfunc)list_repr, /*tp_repr*/
6
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
1057 0, /*tp_as_number*/
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
1058 &list_as_sequence, /*tp_as_sequence*/
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
1059 0, /*tp_as_mapping*/
fc6fcd7df4f7 Initial revision
Guido van Rossum <guido@python.org>
parents:
diff changeset
1060 };