|
27
|
1 /* List object implementation */
|
|
|
2
|
|
|
3 #include "Python.h"
|
|
|
4
|
|
|
5 /* Ensure ob_item has room for at least newsize elements, and set
|
|
|
6 * ob_size to newsize. If newsize > ob_size on entry, the content
|
|
|
7 * of the new slots at exit is undefined heap trash; it's the caller's
|
|
|
8 * responsibility to overwrite them with sane values.
|
|
|
9 * The number of allocated elements may grow, shrink, or stay the same.
|
|
|
10 * Failure is impossible if newsize <= self.allocated on entry, although
|
|
|
11 * that partly relies on an assumption that the system realloc() never
|
|
|
12 * fails when passed a number of bytes <= the number of bytes last
|
|
|
13 * allocated (the C standard doesn't guarantee this, but it's hard to
|
|
|
14 * imagine a realloc implementation where it wouldn't be true).
|
|
|
15 * Note that self->ob_item may change, and even if newsize is less
|
|
|
16 * than ob_size on entry.
|
|
|
17 */
|
|
|
18 static int
|
|
|
19 list_resize(PyListObject *self, Py_ssize_t newsize)
|
|
|
20 {
|
|
|
21 PyObject **items;
|
|
|
22 size_t new_allocated;
|
|
|
23 Py_ssize_t allocated = self->allocated;
|
|
|
24
|
|
|
25 /* Bypass realloc() when a previous overallocation is large enough
|
|
|
26 to accommodate the newsize. If the newsize falls lower than half
|
|
|
27 the allocated size, then proceed with the realloc() to shrink the list.
|
|
|
28 */
|
|
|
29 if (allocated >= newsize && newsize >= (allocated >> 1)) {
|
|
|
30 assert(self->ob_item != NULL || newsize == 0);
|
|
|
31 Py_SIZE(self) = newsize;
|
|
|
32 return 0;
|
|
|
33 }
|
|
|
34
|
|
|
35 /* This over-allocates proportional to the list size, making room
|
|
|
36 * for additional growth. The over-allocation is mild, but is
|
|
|
37 * enough to give linear-time amortized behavior over a long
|
|
|
38 * sequence of appends() in the presence of a poorly-performing
|
|
|
39 * system realloc().
|
|
|
40 * The growth pattern is: 0, 4, 8, 16, 25, 35, 46, 58, 72, 88, ...
|
|
|
41 */
|
|
|
42 new_allocated = (newsize >> 3) + (newsize < 9 ? 3 : 6);
|
|
|
43
|
|
|
44 /* check for integer overflow */
|
|
|
45 if (new_allocated > PY_SIZE_MAX - newsize) {
|
|
|
46 PyErr_NoMemory();
|
|
|
47 return -1;
|
|
|
48 } else {
|
|
|
49 new_allocated += newsize;
|
|
|
50 }
|
|
|
51
|
|
|
52 if (newsize == 0)
|
|
|
53 new_allocated = 0;
|
|
|
54 items = self->ob_item;
|
|
|
55 if (new_allocated <= (PY_SIZE_MAX / sizeof(PyObject *)))
|
|
|
56 PyMem_RESIZE(items, PyObject *, new_allocated);
|
|
|
57 else
|
|
|
58 items = NULL;
|
|
|
59 if (items == NULL) {
|
|
|
60 PyErr_NoMemory();
|
|
|
61 return -1;
|
|
|
62 }
|
|
|
63 self->ob_item = items;
|
|
|
64 Py_SIZE(self) = newsize;
|
|
|
65 self->allocated = new_allocated;
|
|
|
66 return 0;
|
|
|
67 }
|
|
|
68
|
|
|
69
|
|
|
70 /* Empty list reuse scheme to save calls to malloc and free */
|
|
|
71 #ifndef PyList_MAXFREELIST
|
|
|
72 #define PyList_MAXFREELIST 80
|
|
|
73 #endif
|
|
|
74 static PyListObject *free_list[PyList_MAXFREELIST];
|
|
|
75 static int numfree = 0;
|
|
|
76
|
|
|
77 int
|
|
|
78 PyList_ClearFreeList(void)
|
|
|
79 {
|
|
|
80 PyListObject *op;
|
|
|
81 int ret = numfree;
|
|
|
82 while (numfree) {
|
|
|
83 op = free_list[--numfree];
|
|
|
84 assert(PyList_CheckExact(op));
|
|
|
85 PyObject_GC_Del(op);
|
|
|
86 }
|
|
|
87 return ret;
|
|
|
88 }
|
|
|
89
|
|
|
90 void
|
|
|
91 PyList_Fini(void)
|
|
|
92 {
|
|
|
93 PyList_ClearFreeList();
|
|
|
94 }
|
|
|
95
|
|
|
96 PyObject *
|
|
|
97 PyList_New(Py_ssize_t size)
|
|
|
98 {
|
|
|
99 PyListObject *op;
|
|
|
100 size_t nbytes;
|
|
|
101
|
|
|
102 if (size < 0) {
|
|
|
103 PyErr_BadInternalCall();
|
|
|
104 return NULL;
|
|
|
105 }
|
|
|
106 /* Check for overflow without an actual overflow,
|
|
|
107 * which can cause compiler to optimise out */
|
|
|
108 if ((size_t)size > PY_SIZE_MAX / sizeof(PyObject *))
|
|
|
109 return PyErr_NoMemory();
|
|
|
110 nbytes = size * sizeof(PyObject *);
|
|
|
111 if (numfree) {
|
|
|
112 numfree--;
|
|
|
113 op = free_list[numfree];
|
|
|
114 _Py_NewReference((PyObject *)op);
|
|
|
115 } else {
|
|
|
116 op = PyObject_GC_New(PyListObject, &PyList_Type);
|
|
|
117 if (op == NULL)
|
|
|
118 return NULL;
|
|
|
119 }
|
|
|
120 if (size <= 0)
|
|
|
121 op->ob_item = NULL;
|
|
|
122 else {
|
|
|
123 op->ob_item = (PyObject **) PyMem_MALLOC(nbytes);
|
|
|
124 if (op->ob_item == NULL) {
|
|
|
125 Py_DECREF(op);
|
|
|
126 return PyErr_NoMemory();
|
|
|
127 }
|
|
|
128 memset(op->ob_item, 0, nbytes);
|
|
|
129 }
|
|
|
130 Py_SIZE(op) = size;
|
|
|
131 op->allocated = size;
|
|
|
132 _PyObject_GC_TRACK(op);
|
|
|
133 return (PyObject *) op;
|
|
|
134 }
|
|
|
135
|
|
|
136 Py_ssize_t
|
|
|
137 PyList_Size(PyObject *op)
|
|
|
138 {
|
|
|
139 if (!PyList_Check(op)) {
|
|
|
140 PyErr_BadInternalCall();
|
|
|
141 return -1;
|
|
|
142 }
|
|
|
143 else
|
|
|
144 return Py_SIZE(op);
|
|
|
145 }
|
|
|
146
|
|
|
147 static PyObject *indexerr = NULL;
|
|
|
148
|
|
|
149 PyObject *
|
|
|
150 PyList_GetItem(PyObject *op, Py_ssize_t i)
|
|
|
151 {
|
|
|
152 if (!PyList_Check(op)) {
|
|
|
153 PyErr_BadInternalCall();
|
|
|
154 return NULL;
|
|
|
155 }
|
|
|
156 if (i < 0 || i >= Py_SIZE(op)) {
|
|
|
157 if (indexerr == NULL) {
|
|
|
158 indexerr = PyUnicode_FromString(
|
|
|
159 "list index out of range");
|
|
|
160 if (indexerr == NULL)
|
|
|
161 return NULL;
|
|
|
162 }
|
|
|
163 PyErr_SetObject(PyExc_IndexError, indexerr);
|
|
|
164 return NULL;
|
|
|
165 }
|
|
|
166 return ((PyListObject *)op) -> ob_item[i];
|
|
|
167 }
|
|
|
168
|
|
|
169 int
|
|
|
170 PyList_SetItem(register PyObject *op, register int i,
|
|
|
171 register PyObject *newitem)
|
|
|
172 {
|
|
|
173 register PyObject *olditem;
|
|
|
174 register PyObject **p;
|
|
|
175 if (!PyList_Check(op))
|
|
|
176 {
|
|
|
177 Py_XDECREF(newitem);
|
|
|
178 PyErr_BadInternalCall();
|
|
|
179 return -1;
|
|
|
180 }
|
|
|
181 if (i < 0 || i >= Py_SIZE(op))
|
|
|
182 {
|
|
|
183 Py_XDECREF(newitem);
|
|
|
184 PyErr_SetString(PyExc_IndexError,
|
|
|
185 "list assignment index out of range");
|
|
|
186 return -1;
|
|
|
187 }
|
|
|
188 p = ((PyListObject *)op) -> ob_item + i;
|
|
|
189 olditem = *p;
|
|
|
190 *p = newitem;
|
|
|
191 Py_XDECREF(olditem);
|
|
|
192 return 0;
|
|
|
193 }
|
|
|
194
|
|
|
195 static int
|
|
|
196 ins1(PyListObject *self, int where, PyObject *v)
|
|
|
197 {
|
|
|
198 int i, n = Py_SIZE(self);
|
|
|
199 PyObject **items;
|
|
|
200 if (v == NULL) {
|
|
|
201 PyErr_BadInternalCall();
|
|
|
202 return -1;
|
|
|
203 }
|
|
|
204 if (n == PY_SSIZE_T_MAX) {
|
|
|
205 PyErr_SetString(PyExc_OverflowError,
|
|
|
206 "cannot add more objects to list");
|
|
|
207 return -1;
|
|
|
208 }
|
|
|
209
|
|
|
210 if (list_resize(self, n+1) == -1)
|
|
|
211 return -1;
|
|
|
212
|
|
|
213 if (where < 0) {
|
|
|
214 where += n;
|
|
|
215 if (where < 0)
|
|
|
216 where = 0;
|
|
|
217 }
|
|
|
218 if (where > n)
|
|
|
219 where = n;
|
|
|
220 items = self->ob_item;
|
|
|
221 for (i = n; --i >= where; )
|
|
|
222 items[i+1] = items[i];
|
|
|
223 Py_INCREF(v);
|
|
|
224 items[where] = v;
|
|
|
225 return 0;
|
|
|
226 }
|
|
|
227
|
|
|
228 int
|
|
|
229 PyList_Insert(PyObject *op, int where, PyObject *newitem)
|
|
|
230 {
|
|
|
231 if (!PyList_Check(op)) {
|
|
|
232 PyErr_BadInternalCall();
|
|
|
233 return -1;
|
|
|
234 }
|
|
|
235 return ins1((PyListObject *)op, where, newitem);
|
|
|
236 }
|
|
|
237
|
|
|
238 static int
|
|
|
239 app1(PyListObject *self, PyObject *v)
|
|
|
240 {
|
|
|
241 Py_ssize_t n = PyList_GET_SIZE(self);
|
|
|
242
|
|
|
243 assert (v != NULL);
|
|
|
244 if (n == PY_SSIZE_T_MAX) {
|
|
|
245 PyErr_SetString(PyExc_OverflowError,
|
|
|
246 "cannot add more objects to list");
|
|
|
247 return -1;
|
|
|
248 }
|
|
|
249
|
|
|
250 if (list_resize(self, n+1) == -1)
|
|
|
251 return -1;
|
|
|
252
|
|
|
253 Py_INCREF(v);
|
|
|
254 PyList_SET_ITEM(self, n, v);
|
|
|
255 return 0;
|
|
|
256 }
|
|
|
257
|
|
|
258 int
|
|
|
259 PyList_Append(PyObject *op, PyObject *newitem)
|
|
|
260 {
|
|
|
261 if (PyList_Check(op) && (newitem != NULL))
|
|
|
262 return app1((PyListObject *)op, newitem);
|
|
|
263 PyErr_BadInternalCall();
|
|
|
264 return -1;
|
|
|
265 }
|
|
|
266
|
|
|
267 /* Methods */
|
|
|
268
|
|
|
269 static void
|
|
|
270 list_dealloc(PyListObject *op)
|
|
|
271 {
|
|
|
272 Py_ssize_t i;
|
|
|
273 PyObject_GC_UnTrack(op);
|
|
|
274 Py_TRASHCAN_SAFE_BEGIN(op)
|
|
|
275 if (op->ob_item != NULL) {
|
|
|
276 /* Do it backwards, for Christian Tismer.
|
|
|
277 There's a simple test case where somehow this reduces
|
|
|
278 thrashing when a *very* large list is created and
|
|
|
279 immediately deleted. */
|
|
|
280 i = Py_SIZE(op);
|
|
|
281 while (--i >= 0) {
|
|
|
282 Py_XDECREF(op->ob_item[i]);
|
|
|
283 }
|
|
|
284 PyMem_FREE(op->ob_item);
|
|
|
285 }
|
|
|
286 if (numfree < PyList_MAXFREELIST && PyList_CheckExact(op))
|
|
|
287 free_list[numfree++] = op;
|
|
|
288 else
|
|
|
289 Py_TYPE(op)->tp_free((PyObject *)op);
|
|
|
290 Py_TRASHCAN_SAFE_END(op)
|
|
|
291 }
|
|
|
292
|
|
|
293 static PyObject *
|
|
|
294 list_repr(PyListObject *v)
|
|
|
295 {
|
|
|
296 Py_ssize_t i;
|
|
|
297 PyObject *s = NULL;
|
|
|
298 _PyAccu acc;
|
|
|
299 static PyObject *sep = NULL;
|
|
|
300
|
|
|
301 if (Py_SIZE(v) == 0) {
|
|
|
302 return PyUnicode_FromString("[]");
|
|
|
303 }
|
|
|
304
|
|
|
305 if (sep == NULL) {
|
|
|
306 sep = PyUnicode_FromString(", ");
|
|
|
307 if (sep == NULL)
|
|
|
308 return NULL;
|
|
|
309 }
|
|
|
310
|
|
|
311 i = Py_ReprEnter((PyObject*)v);
|
|
|
312 if (i != 0) {
|
|
|
313 return i > 0 ? PyUnicode_FromString("[...]") : NULL;
|
|
|
314 }
|
|
|
315
|
|
|
316 if (_PyAccu_Init(&acc))
|
|
|
317 goto error;
|
|
|
318
|
|
|
319 s = PyUnicode_FromString("[");
|
|
|
320 if (s == NULL || _PyAccu_Accumulate(&acc, s))
|
|
|
321 goto error;
|
|
|
322 Py_CLEAR(s);
|
|
|
323
|
|
|
324 /* Do repr() on each element. Note that this may mutate the list,
|
|
|
325 so must refetch the list size on each iteration. */
|
|
|
326 for (i = 0; i < Py_SIZE(v); ++i) {
|
|
|
327 if (Py_EnterRecursiveCall(" while getting the repr of a list"))
|
|
|
328 goto error;
|
|
|
329 s = PyObject_Repr(v->ob_item[i]);
|
|
|
330 Py_LeaveRecursiveCall();
|
|
|
331 if (i > 0 && _PyAccu_Accumulate(&acc, sep))
|
|
|
332 goto error;
|
|
|
333 if (s == NULL || _PyAccu_Accumulate(&acc, s))
|
|
|
334 goto error;
|
|
|
335 Py_CLEAR(s);
|
|
|
336 }
|
|
|
337 s = PyUnicode_FromString("]");
|
|
|
338 if (s == NULL || _PyAccu_Accumulate(&acc, s))
|
|
|
339 goto error;
|
|
|
340 Py_CLEAR(s);
|
|
|
341
|
|
|
342 Py_ReprLeave((PyObject *)v);
|
|
|
343 return _PyAccu_Finish(&acc);
|
|
|
344
|
|
|
345 error:
|
|
|
346 _PyAccu_Destroy(&acc);
|
|
|
347 Py_XDECREF(s);
|
|
|
348 Py_ReprLeave((PyObject *)v);
|
|
|
349 return NULL;
|
|
|
350 }
|
|
|
351
|
|
|
352 static Py_ssize_t
|
|
|
353 list_length(PyListObject *a)
|
|
|
354 {
|
|
|
355 return Py_SIZE(a);
|
|
|
356 }
|
|
|
357
|
|
|
358 static int
|
|
|
359 list_contains(PyListObject *a, PyObject *el)
|
|
|
360 {
|
|
|
361 Py_ssize_t i;
|
|
|
362 int cmp;
|
|
|
363
|
|
|
364 for (i = 0, cmp = 0 ; cmp == 0 && i < Py_SIZE(a); ++i)
|
|
|
365 cmp = PyObject_RichCompareBool(el, PyList_GET_ITEM(a, i),
|
|
|
366 Py_EQ);
|
|
|
367 return cmp;
|
|
|
368 }
|
|
|
369
|
|
|
370 static PyObject *
|
|
|
371 list_item(PyListObject *a, int i)
|
|
|
372 {
|
|
|
373 if (i < 0 || i >= Py_SIZE(a)) {
|
|
|
374 if (indexerr == NULL) {
|
|
|
375 indexerr = PyUnicode_FromString(
|
|
|
376 "list index out of range");
|
|
|
377 if (indexerr == NULL)
|
|
|
378 return NULL;
|
|
|
379 }
|
|
|
380 PyErr_SetObject(PyExc_IndexError, indexerr);
|
|
|
381 return NULL;
|
|
|
382 }
|
|
|
383 Py_INCREF(a->ob_item[i]);
|
|
|
384 return a->ob_item[i];
|
|
|
385 }
|
|
|
386
|
|
|
387 static PyObject *
|
|
|
388 list_slice(PyListObject *a, int ilow, int ihigh)
|
|
|
389 {
|
|
|
390 PyListObject *np;
|
|
|
391 PyObject **src, **dest;
|
|
|
392 int i, len;
|
|
|
393 if (ilow < 0)
|
|
|
394 ilow = 0;
|
|
|
395 else if (ilow > Py_SIZE(a))
|
|
|
396 ilow = Py_SIZE(a);
|
|
|
397 if (ihigh < ilow)
|
|
|
398 ihigh = ilow;
|
|
|
399 else if (ihigh > Py_SIZE(a))
|
|
|
400 ihigh = Py_SIZE(a);
|
|
|
401 len = ihigh - ilow;
|
|
|
402 np = (PyListObject *) PyList_New(len);
|
|
|
403 if (np == NULL)
|
|
|
404 return NULL;
|
|
|
405
|
|
|
406 src = a->ob_item + ilow;
|
|
|
407 dest = np->ob_item;
|
|
|
408 for (i = 0; i < len; i++) {
|
|
|
409 PyObject *v = src[i];
|
|
|
410 Py_INCREF(v);
|
|
|
411 dest[i] = v;
|
|
|
412 }
|
|
|
413 return (PyObject *)np;
|
|
|
414 }
|
|
|
415
|
|
|
416 PyObject *
|
|
|
417 PyList_GetSlice(PyObject *a, int ilow, int ihigh)
|
|
|
418 {
|
|
|
419 if (!PyList_Check(a)) {
|
|
|
420 PyErr_BadInternalCall();
|
|
|
421 return NULL;
|
|
|
422 }
|
|
|
423 return list_slice((PyListObject *)a, ilow, ihigh);
|
|
|
424 }
|
|
|
425
|
|
|
426 static PyObject *
|
|
|
427 list_concat(PyListObject *a, PyObject *bb)
|
|
|
428 {
|
|
|
429 Py_ssize_t size;
|
|
|
430 Py_ssize_t i;
|
|
|
431 PyObject **src, **dest;
|
|
|
432 PyListObject *np;
|
|
|
433 if (!PyList_Check(bb)) {
|
|
|
434 PyErr_Format(PyExc_TypeError,
|
|
|
435 "can only concatenate list (not \"%.200s\") to list",
|
|
|
436 bb->ob_type->tp_name);
|
|
|
437 return NULL;
|
|
|
438 }
|
|
|
439 #define b ((PyListObject *)bb)
|
|
|
440 size = Py_SIZE(a) + Py_SIZE(b);
|
|
|
441 if (size < 0)
|
|
|
442 return PyErr_NoMemory();
|
|
|
443 np = (PyListObject *) PyList_New(size);
|
|
|
444 if (np == NULL) {
|
|
|
445 return NULL;
|
|
|
446 }
|
|
|
447 src = a->ob_item;
|
|
|
448 dest = np->ob_item;
|
|
|
449 for (i = 0; i < Py_SIZE(a); i++) {
|
|
|
450 PyObject *v = src[i];
|
|
|
451 Py_INCREF(v);
|
|
|
452 dest[i] = v;
|
|
|
453 }
|
|
|
454 src = b->ob_item;
|
|
|
455 dest = np->ob_item + Py_SIZE(a);
|
|
|
456 for (i = 0; i < Py_SIZE(b); i++) {
|
|
|
457 PyObject *v = src[i];
|
|
|
458 Py_INCREF(v);
|
|
|
459 dest[i] = v;
|
|
|
460 }
|
|
|
461 return (PyObject *)np;
|
|
|
462 #undef b
|
|
|
463 }
|
|
|
464
|
|
|
465 static PyObject *
|
|
|
466 list_repeat(PyListObject *a, int n)
|
|
|
467 {
|
|
|
468 Py_ssize_t i, j;
|
|
|
469 Py_ssize_t size;
|
|
|
470 PyListObject *np;
|
|
|
471 PyObject **p, **items;
|
|
|
472 PyObject *elem;
|
|
|
473 if (n < 0)
|
|
|
474 n = 0;
|
|
|
475 if (n > 0 && Py_SIZE(a) > PY_SSIZE_T_MAX / n)
|
|
|
476 return PyErr_NoMemory();
|
|
|
477 size = Py_SIZE(a) * n;
|
|
|
478 if (size == 0)
|
|
|
479 return PyList_New(0);
|
|
|
480 np = (PyListObject *) PyList_New(size);
|
|
|
481 if (np == NULL)
|
|
|
482 return NULL;
|
|
|
483
|
|
|
484 items = np->ob_item;
|
|
|
485 if (Py_SIZE(a) == 1) {
|
|
|
486 elem = a->ob_item[0];
|
|
|
487 for (i = 0; i < n; i++) {
|
|
|
488 items[i] = elem;
|
|
|
489 Py_INCREF(elem);
|
|
|
490 }
|
|
|
491 return (PyObject *) np;
|
|
|
492 }
|
|
|
493 p = np->ob_item;
|
|
|
494 items = a->ob_item;
|
|
|
495 for (i = 0; i < n; i++) {
|
|
|
496 for (j = 0; j < Py_SIZE(a); j++) {
|
|
|
497 *p = items[j];
|
|
|
498 Py_INCREF(*p);
|
|
|
499 p++;
|
|
|
500 }
|
|
|
501 }
|
|
|
502 return (PyObject *) np;
|
|
|
503 }
|
|
|
504
|
|
|
505 static int
|
|
|
506 list_clear(PyListObject *a)
|
|
|
507 {
|
|
|
508 Py_ssize_t i;
|
|
|
509 PyObject **item = a->ob_item;
|
|
|
510 if (item != NULL) {
|
|
|
511 /* Because XDECREF can recursively invoke operations on
|
|
|
512 this list, we make it empty first. */
|
|
|
513 i = Py_SIZE(a);
|
|
|
514 Py_SIZE(a) = 0;
|
|
|
515 a->ob_item = NULL;
|
|
|
516 a->allocated = 0;
|
|
|
517 while (--i >= 0) {
|
|
|
518 Py_XDECREF(item[i]);
|
|
|
519 }
|
|
|
520 PyMem_FREE(item);
|
|
|
521 }
|
|
|
522 /* Never fails; the return value can be ignored.
|
|
|
523 Note that there is no guarantee that the list is actually empty
|
|
|
524 at this point, because XDECREF may have populated it again! */
|
|
|
525 return 0;
|
|
|
526 }
|
|
|
527
|
|
|
528 /* a[ilow:ihigh] = v if v != NULL.
|
|
|
529 * del a[ilow:ihigh] if v == NULL.
|
|
|
530 *
|
|
|
531 * Special speed gimmick: when v is NULL and ihigh - ilow <= 8, it's
|
|
|
532 * guaranteed the call cannot fail.
|
|
|
533 */
|
|
|
534 static int
|
|
|
535 list_ass_slice(PyListObject *a, Py_ssize_t ilow, Py_ssize_t ihigh, PyObject *v)
|
|
|
536 {
|
|
|
537 /* Because [X]DECREF can recursively invoke list operations on
|
|
|
538 this list, we must postpone all [X]DECREF activity until
|
|
|
539 after the list is back in its canonical shape. Therefore
|
|
|
540 we must allocate an additional array, 'recycle', into which
|
|
|
541 we temporarily copy the items that are deleted from the
|
|
|
542 list. :-( */
|
|
|
543 PyObject *recycle_on_stack[8];
|
|
|
544 PyObject **recycle = recycle_on_stack; /* will allocate more if needed */
|
|
|
545 PyObject **item;
|
|
|
546 PyObject **vitem = NULL;
|
|
|
547 PyObject *v_as_SF = NULL; /* PySequence_Fast(v) */
|
|
|
548 Py_ssize_t n; /* # of elements in replacement list */
|
|
|
549 Py_ssize_t norig; /* # of elements in list getting replaced */
|
|
|
550 Py_ssize_t d; /* Change in size */
|
|
|
551 Py_ssize_t k;
|
|
|
552 size_t s;
|
|
|
553 int result = -1; /* guilty until proved innocent */
|
|
|
554 #define b ((PyListObject *)v)
|
|
|
555 if (v == NULL)
|
|
|
556 n = 0;
|
|
|
557 else {
|
|
|
558 if (a == b) {
|
|
|
559 /* Special case "a[i:j] = a" -- copy b first */
|
|
|
560 v = list_slice(b, 0, Py_SIZE(b));
|
|
|
561 if (v == NULL)
|
|
|
562 return result;
|
|
|
563 result = list_ass_slice(a, ilow, ihigh, v);
|
|
|
564 Py_DECREF(v);
|
|
|
565 return result;
|
|
|
566 }
|
|
|
567 v_as_SF = PySequence_Fast(v, "can only assign an iterable");
|
|
|
568 if(v_as_SF == NULL)
|
|
|
569 goto Error;
|
|
|
570 n = PySequence_Fast_GET_SIZE(v_as_SF);
|
|
|
571 vitem = PySequence_Fast_ITEMS(v_as_SF);
|
|
|
572 }
|
|
|
573 if (ilow < 0)
|
|
|
574 ilow = 0;
|
|
|
575 else if (ilow > Py_SIZE(a))
|
|
|
576 ilow = Py_SIZE(a);
|
|
|
577
|
|
|
578 if (ihigh < ilow)
|
|
|
579 ihigh = ilow;
|
|
|
580 else if (ihigh > Py_SIZE(a))
|
|
|
581 ihigh = Py_SIZE(a);
|
|
|
582
|
|
|
583 norig = ihigh - ilow;
|
|
|
584 assert(norig >= 0);
|
|
|
585 d = n - norig;
|
|
|
586 if (Py_SIZE(a) + d == 0) {
|
|
|
587 Py_XDECREF(v_as_SF);
|
|
|
588 return list_clear(a);
|
|
|
589 }
|
|
|
590 item = a->ob_item;
|
|
|
591 /* recycle the items that we are about to remove */
|
|
|
592 s = norig * sizeof(PyObject *);
|
|
|
593 if (s > sizeof(recycle_on_stack)) {
|
|
|
594 recycle = (PyObject **)PyMem_MALLOC(s);
|
|
|
595 if (recycle == NULL) {
|
|
|
596 PyErr_NoMemory();
|
|
|
597 goto Error;
|
|
|
598 }
|
|
|
599 }
|
|
|
600 memcpy(recycle, &item[ilow], s);
|
|
|
601
|
|
|
602 if (d < 0) { /* Delete -d items */
|
|
|
603 memmove(&item[ihigh+d], &item[ihigh],
|
|
|
604 (Py_SIZE(a) - ihigh)*sizeof(PyObject *));
|
|
|
605 list_resize(a, Py_SIZE(a) + d);
|
|
|
606 item = a->ob_item;
|
|
|
607 }
|
|
|
608 else if (d > 0) { /* Insert d items */
|
|
|
609 k = Py_SIZE(a);
|
|
|
610 if (list_resize(a, k+d) < 0)
|
|
|
611 goto Error;
|
|
|
612 item = a->ob_item;
|
|
|
613 memmove(&item[ihigh+d], &item[ihigh],
|
|
|
614 (k - ihigh)*sizeof(PyObject *));
|
|
|
615 }
|
|
|
616 for (k = 0; k < n; k++, ilow++) {
|
|
|
617 PyObject *w = vitem[k];
|
|
|
618 Py_XINCREF(w);
|
|
|
619 item[ilow] = w;
|
|
|
620 }
|
|
|
621 for (k = norig - 1; k >= 0; --k)
|
|
|
622 Py_XDECREF(recycle[k]);
|
|
|
623 result = 0;
|
|
|
624 Error:
|
|
|
625 if (recycle != recycle_on_stack)
|
|
|
626 PyMem_FREE(recycle);
|
|
|
627 Py_XDECREF(v_as_SF);
|
|
|
628 return result;
|
|
|
629 #undef b
|
|
|
630 }
|
|
|
631
|
|
|
632 int
|
|
|
633 PyList_SetSlice(PyObject *a, Py_ssize_t ilow, Py_ssize_t ihigh, PyObject *v)
|
|
|
634 {
|
|
|
635 if (!PyList_Check(a)) {
|
|
|
636 PyErr_BadInternalCall();
|
|
|
637 return -1;
|
|
|
638 }
|
|
|
639 return list_ass_slice((PyListObject *)a, ilow, ihigh, v);
|
|
|
640 }
|
|
|
641
|
|
|
642 static PyObject *
|
|
|
643 list_inplace_repeat(PyListObject *self, Py_ssize_t n)
|
|
|
644 {
|
|
|
645 PyObject **items;
|
|
|
646 Py_ssize_t size, i, j, p;
|
|
|
647
|
|
|
648
|
|
|
649 size = PyList_GET_SIZE(self);
|
|
|
650 if (size == 0 || n == 1) {
|
|
|
651 Py_INCREF(self);
|
|
|
652 return (PyObject *)self;
|
|
|
653 }
|
|
|
654
|
|
|
655 if (n < 1) {
|
|
|
656 (void)list_clear(self);
|
|
|
657 Py_INCREF(self);
|
|
|
658 return (PyObject *)self;
|
|
|
659 }
|
|
|
660
|
|
|
661 if (size > PY_SSIZE_T_MAX / n) {
|
|
|
662 return PyErr_NoMemory();
|
|
|
663 }
|
|
|
664
|
|
|
665 if (list_resize(self, size*n) == -1)
|
|
|
666 return NULL;
|
|
|
667
|
|
|
668 p = size;
|
|
|
669 items = self->ob_item;
|
|
|
670 for (i = 1; i < n; i++) { /* Start counting at 1, not 0 */
|
|
|
671 for (j = 0; j < size; j++) {
|
|
|
672 PyObject *o = items[j];
|
|
|
673 Py_INCREF(o);
|
|
|
674 items[p++] = o;
|
|
|
675 }
|
|
|
676 }
|
|
|
677 Py_INCREF(self);
|
|
|
678 return (PyObject *)self;
|
|
|
679 }
|
|
|
680
|
|
|
681 static int
|
|
|
682 list_ass_item(PyListObject *a, Py_ssize_t i, PyObject *v)
|
|
|
683 {
|
|
|
684 PyObject *old_value;
|
|
|
685 if (i < 0 || i >= Py_SIZE(a)) {
|
|
|
686 PyErr_SetString(PyExc_IndexError,
|
|
|
687 "list assignment index out of range");
|
|
|
688 return -1;
|
|
|
689 }
|
|
|
690 if (v == NULL)
|
|
|
691 return list_ass_slice(a, i, i+1, v);
|
|
|
692 Py_INCREF(v);
|
|
|
693 old_value = a->ob_item[i];
|
|
|
694 a->ob_item[i] = v;
|
|
|
695 Py_DECREF(old_value);
|
|
|
696 return 0;
|
|
|
697 }
|
|
|
698
|
|
|
699 static PyObject *
|
|
|
700 listinsert(PyListObject *self, PyObject *args)
|
|
|
701 {
|
|
|
702 Py_ssize_t i;
|
|
|
703 PyObject *v;
|
|
|
704 if (!PyArg_ParseTuple(args, "nO:insert", &i, &v))
|
|
|
705 return NULL;
|
|
|
706 if (ins1(self, i, v) == 0)
|
|
|
707 Py_RETURN_NONE;
|
|
|
708 return NULL;
|
|
|
709 }
|
|
|
710
|
|
|
711 static PyObject *
|
|
|
712 listclear(PyListObject *self)
|
|
|
713 {
|
|
|
714 list_clear(self);
|
|
|
715 Py_RETURN_NONE;
|
|
|
716 }
|
|
|
717
|
|
|
718 static PyObject *
|
|
|
719 listcopy(PyListObject *self)
|
|
|
720 {
|
|
|
721 return list_slice(self, 0, Py_SIZE(self));
|
|
|
722 }
|
|
|
723
|
|
|
724 static PyObject *
|
|
|
725 listappend(PyListObject *self, PyObject *v)
|
|
|
726 {
|
|
|
727 if (app1(self, v) == 0)
|
|
|
728 Py_RETURN_NONE;
|
|
|
729 return NULL;
|
|
|
730 }
|
|
|
731
|
|
|
732 static PyObject *
|
|
|
733 listextend(PyListObject *self, PyObject *b)
|
|
|
734 {
|
|
|
735 PyObject *it; /* iter(v) */
|
|
|
736 Py_ssize_t m; /* size of self */
|
|
|
737 Py_ssize_t n; /* guess for size of b */
|
|
|
738 Py_ssize_t mn; /* m + n */
|
|
|
739 Py_ssize_t i;
|
|
|
740 PyObject *(*iternext)(PyObject *);
|
|
|
741
|
|
|
742 /* Special cases:
|
|
|
743 1) lists and tuples which can use PySequence_Fast ops
|
|
|
744 2) extending self to self requires making a copy first
|
|
|
745 */
|
|
|
746 if (PyList_CheckExact(b) || PyTuple_CheckExact(b) || (PyObject *)self == b) {
|
|
|
747 PyObject **src, **dest;
|
|
|
748 b = PySequence_Fast(b, "argument must be iterable");
|
|
|
749 if (!b)
|
|
|
750 return NULL;
|
|
|
751 n = PySequence_Fast_GET_SIZE(b);
|
|
|
752 if (n == 0) {
|
|
|
753 /* short circuit when b is empty */
|
|
|
754 Py_DECREF(b);
|
|
|
755 Py_RETURN_NONE;
|
|
|
756 }
|
|
|
757 m = Py_SIZE(self);
|
|
|
758 if (list_resize(self, m + n) == -1) {
|
|
|
759 Py_DECREF(b);
|
|
|
760 return NULL;
|
|
|
761 }
|
|
|
762 /* note that we may still have self == b here for the
|
|
|
763 * situation a.extend(a), but the following code works
|
|
|
764 * in that case too. Just make sure to resize self
|
|
|
765 * before calling PySequence_Fast_ITEMS.
|
|
|
766 */
|
|
|
767 /* populate the end of self with b's items */
|
|
|
768 src = PySequence_Fast_ITEMS(b);
|
|
|
769 dest = self->ob_item + m;
|
|
|
770 for (i = 0; i < n; i++) {
|
|
|
771 PyObject *o = src[i];
|
|
|
772 Py_INCREF(o);
|
|
|
773 dest[i] = o;
|
|
|
774 }
|
|
|
775 Py_DECREF(b);
|
|
|
776 Py_RETURN_NONE;
|
|
|
777 }
|
|
|
778
|
|
|
779 it = PyObject_GetIter(b);
|
|
|
780 if (it == NULL)
|
|
|
781 return NULL;
|
|
|
782 iternext = *it->ob_type->tp_iternext;
|
|
|
783
|
|
|
784 /* Guess a result list size. */
|
|
|
785 n = _PyObject_LengthHint(b, 8);
|
|
|
786 if (n == -1) {
|
|
|
787 Py_DECREF(it);
|
|
|
788 return NULL;
|
|
|
789 }
|
|
|
790 m = Py_SIZE(self);
|
|
|
791 mn = m + n;
|
|
|
792 if (mn >= m) {
|
|
|
793 /* Make room. */
|
|
|
794 if (list_resize(self, mn) == -1)
|
|
|
795 goto error;
|
|
|
796 /* Make the list sane again. */
|
|
|
797 Py_SIZE(self) = m;
|
|
|
798 }
|
|
|
799 /* Else m + n overflowed; on the chance that n lied, and there really
|
|
|
800 * is enough room, ignore it. If n was telling the truth, we'll
|
|
|
801 * eventually run out of memory during the loop.
|
|
|
802 */
|
|
|
803
|
|
|
804 /* Run iterator to exhaustion. */
|
|
|
805 for (;;) {
|
|
|
806 PyObject *item = iternext(it);
|
|
|
807 if (item == NULL) {
|
|
|
808 if (PyErr_Occurred()) {
|
|
|
809 if (PyErr_ExceptionMatches(PyExc_StopIteration))
|
|
|
810 PyErr_Clear();
|
|
|
811 else
|
|
|
812 goto error;
|
|
|
813 }
|
|
|
814 break;
|
|
|
815 }
|
|
|
816 if (Py_SIZE(self) < self->allocated) {
|
|
|
817 /* steals ref */
|
|
|
818 PyList_SET_ITEM(self, Py_SIZE(self), item);
|
|
|
819 ++Py_SIZE(self);
|
|
|
820 }
|
|
|
821 else {
|
|
|
822 int status = app1(self, item);
|
|
|
823 Py_DECREF(item); /* append creates a new ref */
|
|
|
824 if (status < 0)
|
|
|
825 goto error;
|
|
|
826 }
|
|
|
827 }
|
|
|
828
|
|
|
829 /* Cut back result list if initial guess was too large. */
|
|
|
830 if (Py_SIZE(self) < self->allocated)
|
|
|
831 list_resize(self, Py_SIZE(self)); /* shrinking can't fail */
|
|
|
832
|
|
|
833 Py_DECREF(it);
|
|
|
834 Py_RETURN_NONE;
|
|
|
835
|
|
|
836 error:
|
|
|
837 Py_DECREF(it);
|
|
|
838 return NULL;
|
|
|
839 }
|
|
|
840
|
|
|
841 PyObject *
|
|
|
842 _PyList_Extend(PyListObject *self, PyObject *b)
|
|
|
843 {
|
|
|
844 return listextend(self, b);
|
|
|
845 }
|
|
|
846
|
|
|
847 static PyObject *
|
|
|
848 list_inplace_concat(PyListObject *self, PyObject *other)
|
|
|
849 {
|
|
|
850 PyObject *result;
|
|
|
851
|
|
|
852 result = listextend(self, other);
|
|
|
853 if (result == NULL)
|
|
|
854 return result;
|
|
|
855 Py_DECREF(result);
|
|
|
856 Py_INCREF(self);
|
|
|
857 return (PyObject *)self;
|
|
|
858 }
|
|
|
859
|
|
|
860 static PyObject *
|
|
|
861 listpop(PyListObject *self, PyObject *args)
|
|
|
862 {
|
|
|
863 Py_ssize_t i = -1;
|
|
|
864 PyObject *v;
|
|
|
865 int status;
|
|
|
866
|
|
|
867 if (!PyArg_ParseTuple(args, "|n:pop", &i))
|
|
|
868 return NULL;
|
|
|
869
|
|
|
870 if (Py_SIZE(self) == 0) {
|
|
|
871 /* Special-case most common failure cause */
|
|
|
872 PyErr_SetString(PyExc_IndexError, "pop from empty list");
|
|
|
873 return NULL;
|
|
|
874 }
|
|
|
875 if (i < 0)
|
|
|
876 i += Py_SIZE(self);
|
|
|
877 if (i < 0 || i >= Py_SIZE(self)) {
|
|
|
878 PyErr_SetString(PyExc_IndexError, "pop index out of range");
|
|
|
879 return NULL;
|
|
|
880 }
|
|
|
881 v = self->ob_item[i];
|
|
|
882 if (i == Py_SIZE(self) - 1) {
|
|
|
883 status = list_resize(self, Py_SIZE(self) - 1);
|
|
|
884 assert(status >= 0);
|
|
|
885 return v; /* and v now owns the reference the list had */
|
|
|
886 }
|
|
|
887 Py_INCREF(v);
|
|
|
888 status = list_ass_slice(self, i, i+1, (PyObject *)NULL);
|
|
|
889 assert(status >= 0);
|
|
|
890 /* Use status, so that in a release build compilers don't
|
|
|
891 * complain about the unused name.
|
|
|
892 */
|
|
|
893 (void) status;
|
|
|
894
|
|
|
895 return v;
|
|
|
896 }
|
|
|
897
|
|
|
898 /* Reverse a slice of a list in place, from lo up to (exclusive) hi. */
|
|
|
899 static void
|
|
|
900 reverse_slice(PyObject **lo, PyObject **hi)
|
|
|
901 {
|
|
|
902 assert(lo && hi);
|
|
|
903
|
|
|
904 --hi;
|
|
|
905 while (lo < hi) {
|
|
|
906 PyObject *t = *lo;
|
|
|
907 *lo = *hi;
|
|
|
908 *hi = t;
|
|
|
909 ++lo;
|
|
|
910 --hi;
|
|
|
911 }
|
|
|
912 }
|
|
|
913
|
|
|
914 /* Lots of code for an adaptive, stable, natural mergesort. There are many
|
|
|
915 * pieces to this algorithm; read listsort.txt for overviews and details.
|
|
|
916 */
|
|
|
917
|
|
|
918 /* A sortslice contains a pointer to an array of keys and a pointer to
|
|
|
919 * an array of corresponding values. In other words, keys[i]
|
|
|
920 * corresponds with values[i]. If values == NULL, then the keys are
|
|
|
921 * also the values.
|
|
|
922 *
|
|
|
923 * Several convenience routines are provided here, so that keys and
|
|
|
924 * values are always moved in sync.
|
|
|
925 */
|
|
|
926
|
|
|
927 typedef struct {
|
|
|
928 PyObject **keys;
|
|
|
929 PyObject **values;
|
|
|
930 } sortslice;
|
|
|
931
|
|
|
932 Py_LOCAL_INLINE(void)
|
|
|
933 sortslice_copy(sortslice *s1, int i, sortslice *s2, int j)
|
|
|
934 {
|
|
|
935 s1->keys[i] = s2->keys[j];
|
|
|
936 if (s1->values != NULL)
|
|
|
937 s1->values[i] = s2->values[j];
|
|
|
938 }
|
|
|
939
|
|
|
940 Py_LOCAL_INLINE(void)
|
|
|
941 sortslice_copy_incr(sortslice *dst, sortslice *src)
|
|
|
942 {
|
|
|
943 *dst->keys++ = *src->keys++;
|
|
|
944 if (dst->values != NULL)
|
|
|
945 *dst->values++ = *src->values++;
|
|
|
946 }
|
|
|
947
|
|
|
948 Py_LOCAL_INLINE(void)
|
|
|
949 sortslice_copy_decr(sortslice *dst, sortslice *src)
|
|
|
950 {
|
|
|
951 *dst->keys-- = *src->keys--;
|
|
|
952 if (dst->values != NULL)
|
|
|
953 *dst->values-- = *src->values--;
|
|
|
954 }
|
|
|
955
|
|
|
956
|
|
|
957 Py_LOCAL_INLINE(void)
|
|
|
958 sortslice_memcpy(sortslice *s1, int i, sortslice *s2, int j, int n)
|
|
|
959 {
|
|
|
960 memcpy(&s1->keys[i], &s2->keys[j], sizeof(PyObject *) * n);
|
|
|
961 if (s1->values != NULL)
|
|
|
962 memcpy(&s1->values[i], &s2->values[j], sizeof(PyObject *) * n);
|
|
|
963 }
|
|
|
964
|
|
|
965 Py_LOCAL_INLINE(void)
|
|
|
966 sortslice_memmove(sortslice *s1, Py_ssize_t i, sortslice *s2, Py_ssize_t j,
|
|
|
967 Py_ssize_t n)
|
|
|
968 {
|
|
|
969 memmove(&s1->keys[i], &s2->keys[j], sizeof(PyObject *) * n);
|
|
|
970 if (s1->values != NULL)
|
|
|
971 memmove(&s1->values[i], &s2->values[j], sizeof(PyObject *) * n);
|
|
|
972 }
|
|
|
973
|
|
|
974 Py_LOCAL_INLINE(void)
|
|
|
975 sortslice_advance(sortslice *slice, Py_ssize_t n)
|
|
|
976 {
|
|
|
977 slice->keys += n;
|
|
|
978 if (slice->values != NULL)
|
|
|
979 slice->values += n;
|
|
|
980 }
|
|
|
981
|
|
|
982 /* Comparison function: PyObject_RichCompareBool with Py_LT.
|
|
|
983 * Returns -1 on error, 1 if x < y, 0 if x >= y.
|
|
|
984 */
|
|
|
985
|
|
|
986 #define ISLT(X, Y) (PyObject_RichCompareBool(X, Y, Py_LT))
|
|
|
987
|
|
|
988 /* Compare X to Y via "<". Goto "fail" if the comparison raises an
|
|
|
989 error. Else "k" is set to true iff X<Y, and an "if (k)" block is
|
|
|
990 started. It makes more sense in context <wink>. X and Y are PyObject*s.
|
|
|
991 */
|
|
|
992 #define IFLT(X, Y) if ((k = ISLT(X, Y)) < 0) goto fail; \
|
|
|
993 if (k)
|
|
|
994
|
|
|
995 /* binarysort is the best method for sorting small arrays: it does
|
|
|
996 few compares, but can do data movement quadratic in the number of
|
|
|
997 elements.
|
|
|
998 [lo, hi) is a contiguous slice of a list, and is sorted via
|
|
|
999 binary insertion. This sort is stable.
|
|
|
1000 On entry, must have lo <= start <= hi, and that [lo, start) is already
|
|
|
1001 sorted (pass start == lo if you don't know!).
|
|
|
1002 If islt() complains return -1, else 0.
|
|
|
1003 Even in case of error, the output slice will be some permutation of
|
|
|
1004 the input (nothing is lost or duplicated).
|
|
|
1005 */
|
|
|
1006 static int
|
|
|
1007 binarysort(sortslice lo, PyObject **hi, PyObject **start)
|
|
|
1008 {
|
|
|
1009 register Py_ssize_t k;
|
|
|
1010 register PyObject **l, **p, **r;
|
|
|
1011 register PyObject *pivot;
|
|
|
1012
|
|
|
1013 assert(lo.keys <= start && start <= hi);
|
|
|
1014 /* assert [lo, start) is sorted */
|
|
|
1015 if (lo.keys == start)
|
|
|
1016 ++start;
|
|
|
1017 for (; start < hi; ++start) {
|
|
|
1018 /* set l to where *start belongs */
|
|
|
1019 l = lo.keys;
|
|
|
1020 r = start;
|
|
|
1021 pivot = *r;
|
|
|
1022 /* Invariants:
|
|
|
1023 * pivot >= all in [lo, l).
|
|
|
1024 * pivot < all in [r, start).
|
|
|
1025 * The second is vacuously true at the start.
|
|
|
1026 */
|
|
|
1027 assert(l < r);
|
|
|
1028 do {
|
|
|
1029 p = l + ((r - l) >> 1);
|
|
|
1030 IFLT(pivot, *p)
|
|
|
1031 r = p;
|
|
|
1032 else
|
|
|
1033 l = p+1;
|
|
|
1034 } while (l < r);
|
|
|
1035 assert(l == r);
|
|
|
1036 /* The invariants still hold, so pivot >= all in [lo, l) and
|
|
|
1037 pivot < all in [l, start), so pivot belongs at l. Note
|
|
|
1038 that if there are elements equal to pivot, l points to the
|
|
|
1039 first slot after them -- that's why this sort is stable.
|
|
|
1040 Slide over to make room.
|
|
|
1041 Caution: using memmove is much slower under MSVC 5;
|
|
|
1042 we're not usually moving many slots. */
|
|
|
1043 for (p = start; p > l; --p)
|
|
|
1044 *p = *(p-1);
|
|
|
1045 *l = pivot;
|
|
|
1046 if (lo.values != NULL) {
|
|
|
1047 Py_ssize_t offset = lo.values - lo.keys;
|
|
|
1048 p = start + offset;
|
|
|
1049 pivot = *p;
|
|
|
1050 l += offset;
|
|
|
1051 for (p = start + offset; p > l; --p)
|
|
|
1052 *p = *(p-1);
|
|
|
1053 *l = pivot;
|
|
|
1054 }
|
|
|
1055 }
|
|
|
1056 return 0;
|
|
|
1057
|
|
|
1058 fail:
|
|
|
1059 return -1;
|
|
|
1060 }
|
|
|
1061
|
|
|
1062 /*
|
|
|
1063 Return the length of the run beginning at lo, in the slice [lo, hi). lo < hi
|
|
|
1064 is required on entry. "A run" is the longest ascending sequence, with
|
|
|
1065
|
|
|
1066 lo[0] <= lo[1] <= lo[2] <= ...
|
|
|
1067
|
|
|
1068 or the longest descending sequence, with
|
|
|
1069
|
|
|
1070 lo[0] > lo[1] > lo[2] > ...
|
|
|
1071
|
|
|
1072 Boolean *descending is set to 0 in the former case, or to 1 in the latter.
|
|
|
1073 For its intended use in a stable mergesort, the strictness of the defn of
|
|
|
1074 "descending" is needed so that the caller can safely reverse a descending
|
|
|
1075 sequence without violating stability (strict > ensures there are no equal
|
|
|
1076 elements to get out of order).
|
|
|
1077
|
|
|
1078 Returns -1 in case of error.
|
|
|
1079 */
|
|
|
1080 static Py_ssize_t
|
|
|
1081 count_run(PyObject **lo, PyObject **hi, int *descending)
|
|
|
1082 {
|
|
|
1083 Py_ssize_t k;
|
|
|
1084 Py_ssize_t n;
|
|
|
1085
|
|
|
1086 assert(lo < hi);
|
|
|
1087 *descending = 0;
|
|
|
1088 ++lo;
|
|
|
1089 if (lo == hi)
|
|
|
1090 return 1;
|
|
|
1091
|
|
|
1092 n = 2;
|
|
|
1093 IFLT(*lo, *(lo-1)) {
|
|
|
1094 *descending = 1;
|
|
|
1095 for (lo = lo+1; lo < hi; ++lo, ++n) {
|
|
|
1096 IFLT(*lo, *(lo-1))
|
|
|
1097 ;
|
|
|
1098 else
|
|
|
1099 break;
|
|
|
1100 }
|
|
|
1101 }
|
|
|
1102 else {
|
|
|
1103 for (lo = lo+1; lo < hi; ++lo, ++n) {
|
|
|
1104 IFLT(*lo, *(lo-1))
|
|
|
1105 break;
|
|
|
1106 }
|
|
|
1107 }
|
|
|
1108
|
|
|
1109 return n;
|
|
|
1110 fail:
|
|
|
1111 return -1;
|
|
|
1112 }
|
|
|
1113
|
|
|
1114 /*
|
|
|
1115 Locate the proper position of key in a sorted vector; if the vector contains
|
|
|
1116 an element equal to key, return the position immediately to the left of
|
|
|
1117 the leftmost equal element. [gallop_right() does the same except returns
|
|
|
1118 the position to the right of the rightmost equal element (if any).]
|
|
|
1119
|
|
|
1120 "a" is a sorted vector with n elements, starting at a[0]. n must be > 0.
|
|
|
1121
|
|
|
1122 "hint" is an index at which to begin the search, 0 <= hint < n. The closer
|
|
|
1123 hint is to the final result, the faster this runs.
|
|
|
1124
|
|
|
1125 The return value is the int k in 0..n such that
|
|
|
1126
|
|
|
1127 a[k-1] < key <= a[k]
|
|
|
1128
|
|
|
1129 pretending that *(a-1) is minus infinity and a[n] is plus infinity. IOW,
|
|
|
1130 key belongs at index k; or, IOW, the first k elements of a should precede
|
|
|
1131 key, and the last n-k should follow key.
|
|
|
1132
|
|
|
1133 Returns -1 on error. See listsort.txt for info on the method.
|
|
|
1134 */
|
|
|
1135 static Py_ssize_t
|
|
|
1136 gallop_left(PyObject *key, PyObject **a, Py_ssize_t n, Py_ssize_t hint)
|
|
|
1137 {
|
|
|
1138 Py_ssize_t ofs;
|
|
|
1139 Py_ssize_t lastofs;
|
|
|
1140 Py_ssize_t k;
|
|
|
1141
|
|
|
1142 assert(key && a && n > 0 && hint >= 0 && hint < n);
|
|
|
1143
|
|
|
1144 a += hint;
|
|
|
1145 lastofs = 0;
|
|
|
1146 ofs = 1;
|
|
|
1147 IFLT(*a, key) {
|
|
|
1148 /* a[hint] < key -- gallop right, until
|
|
|
1149 * a[hint + lastofs] < key <= a[hint + ofs]
|
|
|
1150 */
|
|
|
1151 const Py_ssize_t maxofs = n - hint; /* &a[n-1] is highest */
|
|
|
1152 while (ofs < maxofs) {
|
|
|
1153 IFLT(a[ofs], key) {
|
|
|
1154 lastofs = ofs;
|
|
|
1155 ofs = (ofs << 1) + 1;
|
|
|
1156 if (ofs <= 0) /* int overflow */
|
|
|
1157 ofs = maxofs;
|
|
|
1158 }
|
|
|
1159 else /* key <= a[hint + ofs] */
|
|
|
1160 break;
|
|
|
1161 }
|
|
|
1162 if (ofs > maxofs)
|
|
|
1163 ofs = maxofs;
|
|
|
1164 /* Translate back to offsets relative to &a[0]. */
|
|
|
1165 lastofs += hint;
|
|
|
1166 ofs += hint;
|
|
|
1167 }
|
|
|
1168 else {
|
|
|
1169 /* key <= a[hint] -- gallop left, until
|
|
|
1170 * a[hint - ofs] < key <= a[hint - lastofs]
|
|
|
1171 */
|
|
|
1172 const Py_ssize_t maxofs = hint + 1; /* &a[0] is lowest */
|
|
|
1173 while (ofs < maxofs) {
|
|
|
1174 IFLT(*(a-ofs), key)
|
|
|
1175 break;
|
|
|
1176 /* key <= a[hint - ofs] */
|
|
|
1177 lastofs = ofs;
|
|
|
1178 ofs = (ofs << 1) + 1;
|
|
|
1179 if (ofs <= 0) /* int overflow */
|
|
|
1180 ofs = maxofs;
|
|
|
1181 }
|
|
|
1182 if (ofs > maxofs)
|
|
|
1183 ofs = maxofs;
|
|
|
1184 /* Translate back to positive offsets relative to &a[0]. */
|
|
|
1185 k = lastofs;
|
|
|
1186 lastofs = hint - ofs;
|
|
|
1187 ofs = hint - k;
|
|
|
1188 }
|
|
|
1189 a -= hint;
|
|
|
1190
|
|
|
1191 assert(-1 <= lastofs && lastofs < ofs && ofs <= n);
|
|
|
1192 /* Now a[lastofs] < key <= a[ofs], so key belongs somewhere to the
|
|
|
1193 * right of lastofs but no farther right than ofs. Do a binary
|
|
|
1194 * search, with invariant a[lastofs-1] < key <= a[ofs].
|
|
|
1195 */
|
|
|
1196 ++lastofs;
|
|
|
1197 while (lastofs < ofs) {
|
|
|
1198 Py_ssize_t m = lastofs + ((ofs - lastofs) >> 1);
|
|
|
1199
|
|
|
1200 IFLT(a[m], key)
|
|
|
1201 lastofs = m+1; /* a[m] < key */
|
|
|
1202 else
|
|
|
1203 ofs = m; /* key <= a[m] */
|
|
|
1204 }
|
|
|
1205 assert(lastofs == ofs); /* so a[ofs-1] < key <= a[ofs] */
|
|
|
1206 return ofs;
|
|
|
1207
|
|
|
1208 fail:
|
|
|
1209 return -1;
|
|
|
1210 }
|
|
|
1211
|
|
|
1212 /*
|
|
|
1213 Exactly like gallop_left(), except that if key already exists in a[0:n],
|
|
|
1214 finds the position immediately to the right of the rightmost equal value.
|
|
|
1215
|
|
|
1216 The return value is the int k in 0..n such that
|
|
|
1217
|
|
|
1218 a[k-1] <= key < a[k]
|
|
|
1219
|
|
|
1220 or -1 if error.
|
|
|
1221
|
|
|
1222 The code duplication is massive, but this is enough different given that
|
|
|
1223 we're sticking to "<" comparisons that it's much harder to follow if
|
|
|
1224 written as one routine with yet another "left or right?" flag.
|
|
|
1225 */
|
|
|
1226 static Py_ssize_t
|
|
|
1227 gallop_right(PyObject *key, PyObject **a, Py_ssize_t n, Py_ssize_t hint)
|
|
|
1228 {
|
|
|
1229 Py_ssize_t ofs;
|
|
|
1230 Py_ssize_t lastofs;
|
|
|
1231 Py_ssize_t k;
|
|
|
1232
|
|
|
1233 assert(key && a && n > 0 && hint >= 0 && hint < n);
|
|
|
1234
|
|
|
1235 a += hint;
|
|
|
1236 lastofs = 0;
|
|
|
1237 ofs = 1;
|
|
|
1238 IFLT(key, *a) {
|
|
|
1239 /* key < a[hint] -- gallop left, until
|
|
|
1240 * a[hint - ofs] <= key < a[hint - lastofs]
|
|
|
1241 */
|
|
|
1242 const Py_ssize_t maxofs = hint + 1; /* &a[0] is lowest */
|
|
|
1243 while (ofs < maxofs) {
|
|
|
1244 IFLT(key, *(a-ofs)) {
|
|
|
1245 lastofs = ofs;
|
|
|
1246 ofs = (ofs << 1) + 1;
|
|
|
1247 if (ofs <= 0) /* int overflow */
|
|
|
1248 ofs = maxofs;
|
|
|
1249 }
|
|
|
1250 else /* a[hint - ofs] <= key */
|
|
|
1251 break;
|
|
|
1252 }
|
|
|
1253 if (ofs > maxofs)
|
|
|
1254 ofs = maxofs;
|
|
|
1255 /* Translate back to positive offsets relative to &a[0]. */
|
|
|
1256 k = lastofs;
|
|
|
1257 lastofs = hint - ofs;
|
|
|
1258 ofs = hint - k;
|
|
|
1259 }
|
|
|
1260 else {
|
|
|
1261 /* a[hint] <= key -- gallop right, until
|
|
|
1262 * a[hint + lastofs] <= key < a[hint + ofs]
|
|
|
1263 */
|
|
|
1264 const Py_ssize_t maxofs = n - hint; /* &a[n-1] is highest */
|
|
|
1265 while (ofs < maxofs) {
|
|
|
1266 IFLT(key, a[ofs])
|
|
|
1267 break;
|
|
|
1268 /* a[hint + ofs] <= key */
|
|
|
1269 lastofs = ofs;
|
|
|
1270 ofs = (ofs << 1) + 1;
|
|
|
1271 if (ofs <= 0) /* int overflow */
|
|
|
1272 ofs = maxofs;
|
|
|
1273 }
|
|
|
1274 if (ofs > maxofs)
|
|
|
1275 ofs = maxofs;
|
|
|
1276 /* Translate back to offsets relative to &a[0]. */
|
|
|
1277 lastofs += hint;
|
|
|
1278 ofs += hint;
|
|
|
1279 }
|
|
|
1280 a -= hint;
|
|
|
1281
|
|
|
1282 assert(-1 <= lastofs && lastofs < ofs && ofs <= n);
|
|
|
1283 /* Now a[lastofs] <= key < a[ofs], so key belongs somewhere to the
|
|
|
1284 * right of lastofs but no farther right than ofs. Do a binary
|
|
|
1285 * search, with invariant a[lastofs-1] <= key < a[ofs].
|
|
|
1286 */
|
|
|
1287 ++lastofs;
|
|
|
1288 while (lastofs < ofs) {
|
|
|
1289 Py_ssize_t m = lastofs + ((ofs - lastofs) >> 1);
|
|
|
1290
|
|
|
1291 IFLT(key, a[m])
|
|
|
1292 ofs = m; /* key < a[m] */
|
|
|
1293 else
|
|
|
1294 lastofs = m+1; /* a[m] <= key */
|
|
|
1295 }
|
|
|
1296 assert(lastofs == ofs); /* so a[ofs-1] <= key < a[ofs] */
|
|
|
1297 return ofs;
|
|
|
1298
|
|
|
1299 fail:
|
|
|
1300 return -1;
|
|
|
1301 }
|
|
|
1302
|
|
|
1303 /* The maximum number of entries in a MergeState's pending-runs stack.
|
|
|
1304 * This is enough to sort arrays of size up to about
|
|
|
1305 * 32 * phi ** MAX_MERGE_PENDING
|
|
|
1306 * where phi ~= 1.618. 85 is ridiculouslylarge enough, good for an array
|
|
|
1307 * with 2**64 elements.
|
|
|
1308 */
|
|
|
1309 #define MAX_MERGE_PENDING 85
|
|
|
1310
|
|
|
1311 /* When we get into galloping mode, we stay there until both runs win less
|
|
|
1312 * often than MIN_GALLOP consecutive times. See listsort.txt for more info.
|
|
|
1313 */
|
|
|
1314 #define MIN_GALLOP 7
|
|
|
1315
|
|
|
1316 /* Avoid malloc for small temp arrays. */
|
|
|
1317 #define MERGESTATE_TEMP_SIZE 256
|
|
|
1318
|
|
|
1319 /* One MergeState exists on the stack per invocation of mergesort. It's just
|
|
|
1320 * a convenient way to pass state around among the helper functions.
|
|
|
1321 */
|
|
|
1322 struct s_slice {
|
|
|
1323 sortslice base;
|
|
|
1324 Py_ssize_t len;
|
|
|
1325 };
|
|
|
1326
|
|
|
1327 typedef struct s_MergeState {
|
|
|
1328 /* This controls when we get *into* galloping mode. It's initialized
|
|
|
1329 * to MIN_GALLOP. merge_lo and merge_hi tend to nudge it higher for
|
|
|
1330 * random data, and lower for highly structured data.
|
|
|
1331 */
|
|
|
1332 Py_ssize_t min_gallop;
|
|
|
1333
|
|
|
1334 /* 'a' is temp storage to help with merges. It contains room for
|
|
|
1335 * alloced entries.
|
|
|
1336 */
|
|
|
1337 sortslice a; /* may point to temparray below */
|
|
|
1338 Py_ssize_t alloced;
|
|
|
1339
|
|
|
1340 /* A stack of n pending runs yet to be merged. Run #i starts at
|
|
|
1341 * address base[i] and extends for len[i] elements. It's always
|
|
|
1342 * true (so long as the indices are in bounds) that
|
|
|
1343 *
|
|
|
1344 * pending[i].base + pending[i].len == pending[i+1].base
|
|
|
1345 *
|
|
|
1346 * so we could cut the storage for this, but it's a minor amount,
|
|
|
1347 * and keeping all the info explicit simplifies the code.
|
|
|
1348 */
|
|
|
1349 int n;
|
|
|
1350 struct s_slice pending[MAX_MERGE_PENDING];
|
|
|
1351
|
|
|
1352 /* 'a' points to this when possible, rather than muck with malloc. */
|
|
|
1353 PyObject *temparray[MERGESTATE_TEMP_SIZE];
|
|
|
1354 } MergeState;
|
|
|
1355
|
|
|
1356 /* Conceptually a MergeState's constructor. */
|
|
|
1357 static void
|
|
|
1358 merge_init(MergeState *ms, Py_ssize_t list_size, int has_keyfunc)
|
|
|
1359 {
|
|
|
1360 assert(ms != NULL);
|
|
|
1361 if (has_keyfunc) {
|
|
|
1362 /* The temporary space for merging will need at most half the list
|
|
|
1363 * size rounded up. Use the minimum possible space so we can use the
|
|
|
1364 * rest of temparray for other things. In particular, if there is
|
|
|
1365 * enough extra space, listsort() will use it to store the keys.
|
|
|
1366 */
|
|
|
1367 ms->alloced = (list_size + 1) / 2;
|
|
|
1368
|
|
|
1369 /* ms->alloced describes how many keys will be stored at
|
|
|
1370 ms->temparray, but we also need to store the values. Hence,
|
|
|
1371 ms->alloced is capped at half of MERGESTATE_TEMP_SIZE. */
|
|
|
1372 if (MERGESTATE_TEMP_SIZE / 2 < ms->alloced)
|
|
|
1373 ms->alloced = MERGESTATE_TEMP_SIZE / 2;
|
|
|
1374 ms->a.values = &ms->temparray[ms->alloced];
|
|
|
1375 }
|
|
|
1376 else {
|
|
|
1377 ms->alloced = MERGESTATE_TEMP_SIZE;
|
|
|
1378 ms->a.values = NULL;
|
|
|
1379 }
|
|
|
1380 ms->a.keys = ms->temparray;
|
|
|
1381 ms->n = 0;
|
|
|
1382 ms->min_gallop = MIN_GALLOP;
|
|
|
1383 }
|
|
|
1384
|
|
|
1385 /* Free all the temp memory owned by the MergeState. This must be called
|
|
|
1386 * when you're done with a MergeState, and may be called before then if
|
|
|
1387 * you want to free the temp memory early.
|
|
|
1388 */
|
|
|
1389 static void
|
|
|
1390 merge_freemem(MergeState *ms)
|
|
|
1391 {
|
|
|
1392 assert(ms != NULL);
|
|
|
1393 if (ms->a.keys != ms->temparray)
|
|
|
1394 PyMem_Free(ms->a.keys);
|
|
|
1395 }
|
|
|
1396
|
|
|
1397 /* Ensure enough temp memory for 'need' array slots is available.
|
|
|
1398 * Returns 0 on success and -1 if the memory can't be gotten.
|
|
|
1399 */
|
|
|
1400 static int
|
|
|
1401 merge_getmem(MergeState *ms, Py_ssize_t need)
|
|
|
1402 {
|
|
|
1403 int multiplier;
|
|
|
1404
|
|
|
1405 assert(ms != NULL);
|
|
|
1406 if (need <= ms->alloced)
|
|
|
1407 return 0;
|
|
|
1408
|
|
|
1409 multiplier = ms->a.values != NULL ? 2 : 1;
|
|
|
1410
|
|
|
1411 /* Don't realloc! That can cost cycles to copy the old data, but
|
|
|
1412 * we don't care what's in the block.
|
|
|
1413 */
|
|
|
1414 merge_freemem(ms);
|
|
|
1415 if ((size_t)need > PY_SSIZE_T_MAX / sizeof(PyObject*) / multiplier) {
|
|
|
1416 PyErr_NoMemory();
|
|
|
1417 return -1;
|
|
|
1418 }
|
|
|
1419 ms->a.keys = (PyObject**)PyMem_Malloc(multiplier * need
|
|
|
1420 * sizeof(PyObject *));
|
|
|
1421 if (ms->a.keys != NULL) {
|
|
|
1422 ms->alloced = need;
|
|
|
1423 if (ms->a.values != NULL)
|
|
|
1424 ms->a.values = &ms->a.keys[need];
|
|
|
1425 return 0;
|
|
|
1426 }
|
|
|
1427 PyErr_NoMemory();
|
|
|
1428 return -1;
|
|
|
1429 }
|
|
|
1430 #define MERGE_GETMEM(MS, NEED) ((NEED) <= (MS)->alloced ? 0 : \
|
|
|
1431 merge_getmem(MS, NEED))
|
|
|
1432
|
|
|
1433 /* Merge the na elements starting at ssa with the nb elements starting at
|
|
|
1434 * ssb.keys = ssa.keys + na in a stable way, in-place. na and nb must be > 0.
|
|
|
1435 * Must also have that ssa.keys[na-1] belongs at the end of the merge, and
|
|
|
1436 * should have na <= nb. See listsort.txt for more info. Return 0 if
|
|
|
1437 * successful, -1 if error.
|
|
|
1438 */
|
|
|
1439 static Py_ssize_t
|
|
|
1440 merge_lo(MergeState *ms, sortslice ssa, Py_ssize_t na,
|
|
|
1441 sortslice ssb, Py_ssize_t nb)
|
|
|
1442 {
|
|
|
1443 Py_ssize_t k;
|
|
|
1444 sortslice dest;
|
|
|
1445 int result = -1; /* guilty until proved innocent */
|
|
|
1446 Py_ssize_t min_gallop;
|
|
|
1447
|
|
|
1448 assert(ms && ssa.keys && ssb.keys && na > 0 && nb > 0);
|
|
|
1449 assert(ssa.keys + na == ssb.keys);
|
|
|
1450 if (MERGE_GETMEM(ms, na) < 0)
|
|
|
1451 return -1;
|
|
|
1452 sortslice_memcpy(&ms->a, 0, &ssa, 0, na);
|
|
|
1453 dest = ssa;
|
|
|
1454 ssa = ms->a;
|
|
|
1455
|
|
|
1456 sortslice_copy_incr(&dest, &ssb);
|
|
|
1457 --nb;
|
|
|
1458 if (nb == 0)
|
|
|
1459 goto Succeed;
|
|
|
1460 if (na == 1)
|
|
|
1461 goto CopyB;
|
|
|
1462
|
|
|
1463 min_gallop = ms->min_gallop;
|
|
|
1464 for (;;) {
|
|
|
1465 Py_ssize_t acount = 0; /* # of times A won in a row */
|
|
|
1466 Py_ssize_t bcount = 0; /* # of times B won in a row */
|
|
|
1467
|
|
|
1468 /* Do the straightforward thing until (if ever) one run
|
|
|
1469 * appears to win consistently.
|
|
|
1470 */
|
|
|
1471 for (;;) {
|
|
|
1472 assert(na > 1 && nb > 0);
|
|
|
1473 k = ISLT(ssb.keys[0], ssa.keys[0]);
|
|
|
1474 if (k) {
|
|
|
1475 if (k < 0)
|
|
|
1476 goto Fail;
|
|
|
1477 sortslice_copy_incr(&dest, &ssb);
|
|
|
1478 ++bcount;
|
|
|
1479 acount = 0;
|
|
|
1480 --nb;
|
|
|
1481 if (nb == 0)
|
|
|
1482 goto Succeed;
|
|
|
1483 if (bcount >= min_gallop)
|
|
|
1484 break;
|
|
|
1485 }
|
|
|
1486 else {
|
|
|
1487 sortslice_copy_incr(&dest, &ssa);
|
|
|
1488 ++acount;
|
|
|
1489 bcount = 0;
|
|
|
1490 --na;
|
|
|
1491 if (na == 1)
|
|
|
1492 goto CopyB;
|
|
|
1493 if (acount >= min_gallop)
|
|
|
1494 break;
|
|
|
1495 }
|
|
|
1496 }
|
|
|
1497
|
|
|
1498 /* One run is winning so consistently that galloping may
|
|
|
1499 * be a huge win. So try that, and continue galloping until
|
|
|
1500 * (if ever) neither run appears to be winning consistently
|
|
|
1501 * anymore.
|
|
|
1502 */
|
|
|
1503 ++min_gallop;
|
|
|
1504 do {
|
|
|
1505 assert(na > 1 && nb > 0);
|
|
|
1506 min_gallop -= min_gallop > 1;
|
|
|
1507 ms->min_gallop = min_gallop;
|
|
|
1508 k = gallop_right(ssb.keys[0], ssa.keys, na, 0);
|
|
|
1509 acount = k;
|
|
|
1510 if (k) {
|
|
|
1511 if (k < 0)
|
|
|
1512 goto Fail;
|
|
|
1513 sortslice_memcpy(&dest, 0, &ssa, 0, k);
|
|
|
1514 sortslice_advance(&dest, k);
|
|
|
1515 sortslice_advance(&ssa, k);
|
|
|
1516 na -= k;
|
|
|
1517 if (na == 1)
|
|
|
1518 goto CopyB;
|
|
|
1519 /* na==0 is impossible now if the comparison
|
|
|
1520 * function is consistent, but we can't assume
|
|
|
1521 * that it is.
|
|
|
1522 */
|
|
|
1523 if (na == 0)
|
|
|
1524 goto Succeed;
|
|
|
1525 }
|
|
|
1526 sortslice_copy_incr(&dest, &ssb);
|
|
|
1527 --nb;
|
|
|
1528 if (nb == 0)
|
|
|
1529 goto Succeed;
|
|
|
1530
|
|
|
1531 k = gallop_left(ssa.keys[0], ssb.keys, nb, 0);
|
|
|
1532 bcount = k;
|
|
|
1533 if (k) {
|
|
|
1534 if (k < 0)
|
|
|
1535 goto Fail;
|
|
|
1536 sortslice_memmove(&dest, 0, &ssb, 0, k);
|
|
|
1537 sortslice_advance(&dest, k);
|
|
|
1538 sortslice_advance(&ssb, k);
|
|
|
1539 nb -= k;
|
|
|
1540 if (nb == 0)
|
|
|
1541 goto Succeed;
|
|
|
1542 }
|
|
|
1543 sortslice_copy_incr(&dest, &ssa);
|
|
|
1544 --na;
|
|
|
1545 if (na == 1)
|
|
|
1546 goto CopyB;
|
|
|
1547 } while (acount >= MIN_GALLOP || bcount >= MIN_GALLOP);
|
|
|
1548 ++min_gallop; /* penalize it for leaving galloping mode */
|
|
|
1549 ms->min_gallop = min_gallop;
|
|
|
1550 }
|
|
|
1551 Succeed:
|
|
|
1552 result = 0;
|
|
|
1553 Fail:
|
|
|
1554 if (na)
|
|
|
1555 sortslice_memcpy(&dest, 0, &ssa, 0, na);
|
|
|
1556 return result;
|
|
|
1557 CopyB:
|
|
|
1558 assert(na == 1 && nb > 0);
|
|
|
1559 /* The last element of ssa belongs at the end of the merge. */
|
|
|
1560 sortslice_memmove(&dest, 0, &ssb, 0, nb);
|
|
|
1561 sortslice_copy(&dest, nb, &ssa, 0);
|
|
|
1562 return 0;
|
|
|
1563 }
|
|
|
1564
|
|
|
1565 /* Merge the na elements starting at pa with the nb elements starting at
|
|
|
1566 * ssb.keys = ssa.keys + na in a stable way, in-place. na and nb must be > 0.
|
|
|
1567 * Must also have that ssa.keys[na-1] belongs at the end of the merge, and
|
|
|
1568 * should have na >= nb. See listsort.txt for more info. Return 0 if
|
|
|
1569 * successful, -1 if error.
|
|
|
1570 */
|
|
|
1571 static Py_ssize_t
|
|
|
1572 merge_hi(MergeState *ms, sortslice ssa, Py_ssize_t na,
|
|
|
1573 sortslice ssb, Py_ssize_t nb)
|
|
|
1574 {
|
|
|
1575 Py_ssize_t k;
|
|
|
1576 sortslice dest, basea, baseb;
|
|
|
1577 int result = -1; /* guilty until proved innocent */
|
|
|
1578 Py_ssize_t min_gallop;
|
|
|
1579
|
|
|
1580 assert(ms && ssa.keys && ssb.keys && na > 0 && nb > 0);
|
|
|
1581 assert(ssa.keys + na == ssb.keys);
|
|
|
1582 if (MERGE_GETMEM(ms, nb) < 0)
|
|
|
1583 return -1;
|
|
|
1584 dest = ssb;
|
|
|
1585 sortslice_advance(&dest, nb-1);
|
|
|
1586 sortslice_memcpy(&ms->a, 0, &ssb, 0, nb);
|
|
|
1587 basea = ssa;
|
|
|
1588 baseb = ms->a;
|
|
|
1589 ssb.keys = ms->a.keys + nb - 1;
|
|
|
1590 if (ssb.values != NULL)
|
|
|
1591 ssb.values = ms->a.values + nb - 1;
|
|
|
1592 sortslice_advance(&ssa, na - 1);
|
|
|
1593
|
|
|
1594 sortslice_copy_decr(&dest, &ssa);
|
|
|
1595 --na;
|
|
|
1596 if (na == 0)
|
|
|
1597 goto Succeed;
|
|
|
1598 if (nb == 1)
|
|
|
1599 goto CopyA;
|
|
|
1600
|
|
|
1601 min_gallop = ms->min_gallop;
|
|
|
1602 for (;;) {
|
|
|
1603 Py_ssize_t acount = 0; /* # of times A won in a row */
|
|
|
1604 Py_ssize_t bcount = 0; /* # of times B won in a row */
|
|
|
1605
|
|
|
1606 /* Do the straightforward thing until (if ever) one run
|
|
|
1607 * appears to win consistently.
|
|
|
1608 */
|
|
|
1609 for (;;) {
|
|
|
1610 assert(na > 0 && nb > 1);
|
|
|
1611 k = ISLT(ssb.keys[0], ssa.keys[0]);
|
|
|
1612 if (k) {
|
|
|
1613 if (k < 0)
|
|
|
1614 goto Fail;
|
|
|
1615 sortslice_copy_decr(&dest, &ssa);
|
|
|
1616 ++acount;
|
|
|
1617 bcount = 0;
|
|
|
1618 --na;
|
|
|
1619 if (na == 0)
|
|
|
1620 goto Succeed;
|
|
|
1621 if (acount >= min_gallop)
|
|
|
1622 break;
|
|
|
1623 }
|
|
|
1624 else {
|
|
|
1625 sortslice_copy_decr(&dest, &ssb);
|
|
|
1626 ++bcount;
|
|
|
1627 acount = 0;
|
|
|
1628 --nb;
|
|
|
1629 if (nb == 1)
|
|
|
1630 goto CopyA;
|
|
|
1631 if (bcount >= min_gallop)
|
|
|
1632 break;
|
|
|
1633 }
|
|
|
1634 }
|
|
|
1635
|
|
|
1636 /* One run is winning so consistently that galloping may
|
|
|
1637 * be a huge win. So try that, and continue galloping until
|
|
|
1638 * (if ever) neither run appears to be winning consistently
|
|
|
1639 * anymore.
|
|
|
1640 */
|
|
|
1641 ++min_gallop;
|
|
|
1642 do {
|
|
|
1643 assert(na > 0 && nb > 1);
|
|
|
1644 min_gallop -= min_gallop > 1;
|
|
|
1645 ms->min_gallop = min_gallop;
|
|
|
1646 k = gallop_right(ssb.keys[0], basea.keys, na, na-1);
|
|
|
1647 if (k < 0)
|
|
|
1648 goto Fail;
|
|
|
1649 k = na - k;
|
|
|
1650 acount = k;
|
|
|
1651 if (k) {
|
|
|
1652 sortslice_advance(&dest, -k);
|
|
|
1653 sortslice_advance(&ssa, -k);
|
|
|
1654 sortslice_memmove(&dest, 1, &ssa, 1, k);
|
|
|
1655 na -= k;
|
|
|
1656 if (na == 0)
|
|
|
1657 goto Succeed;
|
|
|
1658 }
|
|
|
1659 sortslice_copy_decr(&dest, &ssb);
|
|
|
1660 --nb;
|
|
|
1661 if (nb == 1)
|
|
|
1662 goto CopyA;
|
|
|
1663
|
|
|
1664 k = gallop_left(ssa.keys[0], baseb.keys, nb, nb-1);
|
|
|
1665 if (k < 0)
|
|
|
1666 goto Fail;
|
|
|
1667 k = nb - k;
|
|
|
1668 bcount = k;
|
|
|
1669 if (k) {
|
|
|
1670 sortslice_advance(&dest, -k);
|
|
|
1671 sortslice_advance(&ssb, -k);
|
|
|
1672 sortslice_memcpy(&dest, 1, &ssb, 1, k);
|
|
|
1673 nb -= k;
|
|
|
1674 if (nb == 1)
|
|
|
1675 goto CopyA;
|
|
|
1676 /* nb==0 is impossible now if the comparison
|
|
|
1677 * function is consistent, but we can't assume
|
|
|
1678 * that it is.
|
|
|
1679 */
|
|
|
1680 if (nb == 0)
|
|
|
1681 goto Succeed;
|
|
|
1682 }
|
|
|
1683 sortslice_copy_decr(&dest, &ssa);
|
|
|
1684 --na;
|
|
|
1685 if (na == 0)
|
|
|
1686 goto Succeed;
|
|
|
1687 } while (acount >= MIN_GALLOP || bcount >= MIN_GALLOP);
|
|
|
1688 ++min_gallop; /* penalize it for leaving galloping mode */
|
|
|
1689 ms->min_gallop = min_gallop;
|
|
|
1690 }
|
|
|
1691 Succeed:
|
|
|
1692 result = 0;
|
|
|
1693 Fail:
|
|
|
1694 if (nb)
|
|
|
1695 sortslice_memcpy(&dest, -(nb-1), &baseb, 0, nb);
|
|
|
1696 return result;
|
|
|
1697 CopyA:
|
|
|
1698 assert(nb == 1 && na > 0);
|
|
|
1699 /* The first element of ssb belongs at the front of the merge. */
|
|
|
1700 sortslice_memmove(&dest, 1-na, &ssa, 1-na, na);
|
|
|
1701 sortslice_advance(&dest, -na);
|
|
|
1702 sortslice_advance(&ssa, -na);
|
|
|
1703 sortslice_copy(&dest, 0, &ssb, 0);
|
|
|
1704 return 0;
|
|
|
1705 }
|
|
|
1706
|
|
|
1707 /* Merge the two runs at stack indices i and i+1.
|
|
|
1708 * Returns 0 on success, -1 on error.
|
|
|
1709 */
|
|
|
1710 static Py_ssize_t
|
|
|
1711 merge_at(MergeState *ms, Py_ssize_t i)
|
|
|
1712 {
|
|
|
1713 sortslice ssa, ssb;
|
|
|
1714 Py_ssize_t na, nb;
|
|
|
1715 Py_ssize_t k;
|
|
|
1716
|
|
|
1717 assert(ms != NULL);
|
|
|
1718 assert(ms->n >= 2);
|
|
|
1719 assert(i >= 0);
|
|
|
1720 assert(i == ms->n - 2 || i == ms->n - 3);
|
|
|
1721
|
|
|
1722 ssa = ms->pending[i].base;
|
|
|
1723 na = ms->pending[i].len;
|
|
|
1724 ssb = ms->pending[i+1].base;
|
|
|
1725 nb = ms->pending[i+1].len;
|
|
|
1726 assert(na > 0 && nb > 0);
|
|
|
1727 assert(ssa.keys + na == ssb.keys);
|
|
|
1728
|
|
|
1729 /* Record the length of the combined runs; if i is the 3rd-last
|
|
|
1730 * run now, also slide over the last run (which isn't involved
|
|
|
1731 * in this merge). The current run i+1 goes away in any case.
|
|
|
1732 */
|
|
|
1733 ms->pending[i].len = na + nb;
|
|
|
1734 if (i == ms->n - 3)
|
|
|
1735 ms->pending[i+1] = ms->pending[i+2];
|
|
|
1736 --ms->n;
|
|
|
1737
|
|
|
1738 /* Where does b start in a? Elements in a before that can be
|
|
|
1739 * ignored (already in place).
|
|
|
1740 */
|
|
|
1741 k = gallop_right(*ssb.keys, ssa.keys, na, 0);
|
|
|
1742 if (k < 0)
|
|
|
1743 return -1;
|
|
|
1744 sortslice_advance(&ssa, k);
|
|
|
1745 na -= k;
|
|
|
1746 if (na == 0)
|
|
|
1747 return 0;
|
|
|
1748
|
|
|
1749 /* Where does a end in b? Elements in b after that can be
|
|
|
1750 * ignored (already in place).
|
|
|
1751 */
|
|
|
1752 nb = gallop_left(ssa.keys[na-1], ssb.keys, nb, nb-1);
|
|
|
1753 if (nb <= 0)
|
|
|
1754 return nb;
|
|
|
1755
|
|
|
1756 /* Merge what remains of the runs, using a temp array with
|
|
|
1757 * min(na, nb) elements.
|
|
|
1758 */
|
|
|
1759 if (na <= nb)
|
|
|
1760 return merge_lo(ms, ssa, na, ssb, nb);
|
|
|
1761 else
|
|
|
1762 return merge_hi(ms, ssa, na, ssb, nb);
|
|
|
1763 }
|
|
|
1764
|
|
|
1765 /* Examine the stack of runs waiting to be merged, merging adjacent runs
|
|
|
1766 * until the stack invariants are re-established:
|
|
|
1767 *
|
|
|
1768 * 1. len[-3] > len[-2] + len[-1]
|
|
|
1769 * 2. len[-2] > len[-1]
|
|
|
1770 *
|
|
|
1771 * See listsort.txt for more info.
|
|
|
1772 *
|
|
|
1773 * Returns 0 on success, -1 on error.
|
|
|
1774 */
|
|
|
1775 static int
|
|
|
1776 merge_collapse(MergeState *ms)
|
|
|
1777 {
|
|
|
1778 struct s_slice *p = ms->pending;
|
|
|
1779
|
|
|
1780 assert(ms);
|
|
|
1781 while (ms->n > 1) {
|
|
|
1782 Py_ssize_t n = ms->n - 2;
|
|
|
1783 if (n > 0 && p[n-1].len <= p[n].len + p[n+1].len) {
|
|
|
1784 if (p[n-1].len < p[n+1].len)
|
|
|
1785 --n;
|
|
|
1786 if (merge_at(ms, n) < 0)
|
|
|
1787 return -1;
|
|
|
1788 }
|
|
|
1789 else if (p[n].len <= p[n+1].len) {
|
|
|
1790 if (merge_at(ms, n) < 0)
|
|
|
1791 return -1;
|
|
|
1792 }
|
|
|
1793 else
|
|
|
1794 break;
|
|
|
1795 }
|
|
|
1796 return 0;
|
|
|
1797 }
|
|
|
1798
|
|
|
1799 /* Regardless of invariants, merge all runs on the stack until only one
|
|
|
1800 * remains. This is used at the end of the mergesort.
|
|
|
1801 *
|
|
|
1802 * Returns 0 on success, -1 on error.
|
|
|
1803 */
|
|
|
1804 static int
|
|
|
1805 merge_force_collapse(MergeState *ms)
|
|
|
1806 {
|
|
|
1807 struct s_slice *p = ms->pending;
|
|
|
1808
|
|
|
1809 assert(ms);
|
|
|
1810 while (ms->n > 1) {
|
|
|
1811 Py_ssize_t n = ms->n - 2;
|
|
|
1812 if (n > 0 && p[n-1].len < p[n+1].len)
|
|
|
1813 --n;
|
|
|
1814 if (merge_at(ms, n) < 0)
|
|
|
1815 return -1;
|
|
|
1816 }
|
|
|
1817 return 0;
|
|
|
1818 }
|
|
|
1819
|
|
|
1820 /* Compute a good value for the minimum run length; natural runs shorter
|
|
|
1821 * than this are boosted artificially via binary insertion.
|
|
|
1822 *
|
|
|
1823 * If n < 64, return n (it's too small to bother with fancy stuff).
|
|
|
1824 * Else if n is an exact power of 2, return 32.
|
|
|
1825 * Else return an int k, 32 <= k <= 64, such that n/k is close to, but
|
|
|
1826 * strictly less than, an exact power of 2.
|
|
|
1827 *
|
|
|
1828 * See listsort.txt for more info.
|
|
|
1829 */
|
|
|
1830 static Py_ssize_t
|
|
|
1831 merge_compute_minrun(Py_ssize_t n)
|
|
|
1832 {
|
|
|
1833 Py_ssize_t r = 0; /* becomes 1 if any 1 bits are shifted off */
|
|
|
1834
|
|
|
1835 assert(n >= 0);
|
|
|
1836 while (n >= 64) {
|
|
|
1837 r |= n & 1;
|
|
|
1838 n >>= 1;
|
|
|
1839 }
|
|
|
1840 return n + r;
|
|
|
1841 }
|
|
|
1842
|
|
|
1843 static void
|
|
|
1844 reverse_sortslice(sortslice *s, Py_ssize_t n)
|
|
|
1845 {
|
|
|
1846 reverse_slice(s->keys, &s->keys[n]);
|
|
|
1847 if (s->values != NULL)
|
|
|
1848 reverse_slice(s->values, &s->values[n]);
|
|
|
1849 }
|
|
|
1850
|
|
|
1851 /* An adaptive, stable, natural mergesort. See listsort.txt.
|
|
|
1852 * Returns Py_None on success, NULL on error. Even in case of error, the
|
|
|
1853 * list will be some permutation of its input state (nothing is lost or
|
|
|
1854 * duplicated).
|
|
|
1855 */
|
|
|
1856 static PyObject *
|
|
|
1857 listsort(PyListObject *self, PyObject *args, PyObject *kwds)
|
|
|
1858 {
|
|
|
1859 MergeState ms;
|
|
|
1860 Py_ssize_t nremaining;
|
|
|
1861 Py_ssize_t minrun;
|
|
|
1862 sortslice lo;
|
|
|
1863 Py_ssize_t saved_ob_size, saved_allocated;
|
|
|
1864 PyObject **saved_ob_item;
|
|
|
1865 PyObject **final_ob_item;
|
|
|
1866 PyObject *result = NULL; /* guilty until proved innocent */
|
|
|
1867 int reverse = 0;
|
|
|
1868 PyObject *keyfunc = NULL;
|
|
|
1869 Py_ssize_t i;
|
|
|
1870 static char *kwlist[] = {"key", "reverse", 0};
|
|
|
1871 PyObject **keys;
|
|
|
1872
|
|
|
1873 assert(self != NULL);
|
|
|
1874 assert (PyList_Check(self));
|
|
|
1875 if (args != NULL) {
|
|
|
1876 if (!PyArg_ParseTupleAndKeywords(args, kwds, "|Oi:sort",
|
|
|
1877 kwlist, &keyfunc, &reverse))
|
|
|
1878 return NULL;
|
|
|
1879 if (Py_SIZE(args) > 0) {
|
|
|
1880 PyErr_SetString(PyExc_TypeError,
|
|
|
1881 "must use keyword argument for key function");
|
|
|
1882 return NULL;
|
|
|
1883 }
|
|
|
1884 }
|
|
|
1885 if (keyfunc == Py_None)
|
|
|
1886 keyfunc = NULL;
|
|
|
1887
|
|
|
1888 /* The list is temporarily made empty, so that mutations performed
|
|
|
1889 * by comparison functions can't affect the slice of memory we're
|
|
|
1890 * sorting (allowing mutations during sorting is a core-dump
|
|
|
1891 * factory, since ob_item may change).
|
|
|
1892 */
|
|
|
1893 saved_ob_size = Py_SIZE(self);
|
|
|
1894 saved_ob_item = self->ob_item;
|
|
|
1895 saved_allocated = self->allocated;
|
|
|
1896 Py_SIZE(self) = 0;
|
|
|
1897 self->ob_item = NULL;
|
|
|
1898 self->allocated = -1; /* any operation will reset it to >= 0 */
|
|
|
1899
|
|
|
1900 if (keyfunc == NULL) {
|
|
|
1901 keys = NULL;
|
|
|
1902 lo.keys = saved_ob_item;
|
|
|
1903 lo.values = NULL;
|
|
|
1904 }
|
|
|
1905 else {
|
|
|
1906 if (saved_ob_size < MERGESTATE_TEMP_SIZE/2)
|
|
|
1907 /* Leverage stack space we allocated but won't otherwise use */
|
|
|
1908 keys = &ms.temparray[saved_ob_size+1];
|
|
|
1909 else {
|
|
|
1910 keys = PyMem_MALLOC(sizeof(PyObject *) * saved_ob_size);
|
|
|
1911 if (keys == NULL)
|
|
|
1912 return NULL;
|
|
|
1913 }
|
|
|
1914
|
|
|
1915 for (i = 0; i < saved_ob_size ; i++) {
|
|
|
1916 keys[i] = PyObject_CallFunctionObjArgs(keyfunc, saved_ob_item[i],
|
|
|
1917 NULL);
|
|
|
1918 if (keys[i] == NULL) {
|
|
|
1919 for (i=i-1 ; i>=0 ; i--)
|
|
|
1920 Py_DECREF(keys[i]);
|
|
|
1921 if (keys != &ms.temparray[saved_ob_size+1])
|
|
|
1922 PyMem_FREE(keys);
|
|
|
1923 goto keyfunc_fail;
|
|
|
1924 }
|
|
|
1925 }
|
|
|
1926
|
|
|
1927 lo.keys = keys;
|
|
|
1928 lo.values = saved_ob_item;
|
|
|
1929 }
|
|
|
1930
|
|
|
1931 merge_init(&ms, saved_ob_size, keys != NULL);
|
|
|
1932
|
|
|
1933 nremaining = saved_ob_size;
|
|
|
1934 if (nremaining < 2)
|
|
|
1935 goto succeed;
|
|
|
1936
|
|
|
1937 /* Reverse sort stability achieved by initially reversing the list,
|
|
|
1938 applying a stable forward sort, then reversing the final result. */
|
|
|
1939 if (reverse) {
|
|
|
1940 if (keys != NULL)
|
|
|
1941 reverse_slice(&keys[0], &keys[saved_ob_size]);
|
|
|
1942 reverse_slice(&saved_ob_item[0], &saved_ob_item[saved_ob_size]);
|
|
|
1943 }
|
|
|
1944
|
|
|
1945 /* March over the array once, left to right, finding natural runs,
|
|
|
1946 * and extending short natural runs to minrun elements.
|
|
|
1947 */
|
|
|
1948 minrun = merge_compute_minrun(nremaining);
|
|
|
1949 do {
|
|
|
1950 int descending;
|
|
|
1951 Py_ssize_t n;
|
|
|
1952
|
|
|
1953 /* Identify next run. */
|
|
|
1954 n = count_run(lo.keys, lo.keys + nremaining, &descending);
|
|
|
1955 if (n < 0)
|
|
|
1956 goto fail;
|
|
|
1957 if (descending)
|
|
|
1958 reverse_sortslice(&lo, n);
|
|
|
1959 /* If short, extend to min(minrun, nremaining). */
|
|
|
1960 if (n < minrun) {
|
|
|
1961 const Py_ssize_t force = nremaining <= minrun ?
|
|
|
1962 nremaining : minrun;
|
|
|
1963 if (binarysort(lo, lo.keys + force, lo.keys + n) < 0)
|
|
|
1964 goto fail;
|
|
|
1965 n = force;
|
|
|
1966 }
|
|
|
1967 /* Push run onto pending-runs stack, and maybe merge. */
|
|
|
1968 assert(ms.n < MAX_MERGE_PENDING);
|
|
|
1969 ms.pending[ms.n].base = lo;
|
|
|
1970 ms.pending[ms.n].len = n;
|
|
|
1971 ++ms.n;
|
|
|
1972 if (merge_collapse(&ms) < 0)
|
|
|
1973 goto fail;
|
|
|
1974 /* Advance to find next run. */
|
|
|
1975 sortslice_advance(&lo, n);
|
|
|
1976 nremaining -= n;
|
|
|
1977 } while (nremaining);
|
|
|
1978
|
|
|
1979 if (merge_force_collapse(&ms) < 0)
|
|
|
1980 goto fail;
|
|
|
1981 assert(ms.n == 1);
|
|
|
1982 assert(keys == NULL
|
|
|
1983 ? ms.pending[0].base.keys == saved_ob_item
|
|
|
1984 : ms.pending[0].base.keys == &keys[0]);
|
|
|
1985 assert(ms.pending[0].len == saved_ob_size);
|
|
|
1986 lo = ms.pending[0].base;
|
|
|
1987
|
|
|
1988 succeed:
|
|
|
1989 result = Py_None;
|
|
|
1990 fail:
|
|
|
1991 if (keys != NULL) {
|
|
|
1992 for (i = 0; i < saved_ob_size; i++)
|
|
|
1993 Py_DECREF(keys[i]);
|
|
|
1994 if (keys != &ms.temparray[saved_ob_size+1])
|
|
|
1995 PyMem_FREE(keys);
|
|
|
1996 }
|
|
|
1997
|
|
|
1998 if (self->allocated != -1 && result != NULL) {
|
|
|
1999 /* The user mucked with the list during the sort,
|
|
|
2000 * and we don't already have another error to report.
|
|
|
2001 */
|
|
|
2002 PyErr_SetString(PyExc_ValueError, "list modified during sort");
|
|
|
2003 result = NULL;
|
|
|
2004 }
|
|
|
2005
|
|
|
2006 if (reverse && saved_ob_size > 1)
|
|
|
2007 reverse_slice(saved_ob_item, saved_ob_item + saved_ob_size);
|
|
|
2008
|
|
|
2009 merge_freemem(&ms);
|
|
|
2010
|
|
|
2011 keyfunc_fail:
|
|
|
2012 final_ob_item = self->ob_item;
|
|
|
2013 i = Py_SIZE(self);
|
|
|
2014 Py_SIZE(self) = saved_ob_size;
|
|
|
2015 self->ob_item = saved_ob_item;
|
|
|
2016 self->allocated = saved_allocated;
|
|
|
2017 if (final_ob_item != NULL) {
|
|
|
2018 /* we cannot use list_clear() for this because it does not
|
|
|
2019 guarantee that the list is really empty when it returns */
|
|
|
2020 while (--i >= 0) {
|
|
|
2021 Py_XDECREF(final_ob_item[i]);
|
|
|
2022 }
|
|
|
2023 PyMem_FREE(final_ob_item);
|
|
|
2024 }
|
|
|
2025 Py_XINCREF(result);
|
|
|
2026 return result;
|
|
|
2027 }
|
|
|
2028 #undef IFLT
|
|
|
2029 #undef ISLT
|
|
|
2030
|
|
|
2031 int
|
|
|
2032 PyList_Sort(PyObject *v)
|
|
|
2033 {
|
|
|
2034 if (v == NULL || !PyList_Check(v)) {
|
|
|
2035 PyErr_BadInternalCall();
|
|
|
2036 return -1;
|
|
|
2037 }
|
|
|
2038 v = listsort((PyListObject *)v, (PyObject *)NULL, (PyObject *)NULL);
|
|
|
2039 if (v == NULL)
|
|
|
2040 return -1;
|
|
|
2041 Py_DECREF(v);
|
|
|
2042 return 0;
|
|
|
2043 }
|
|
|
2044
|
|
|
2045 static PyObject *
|
|
|
2046 listreverse(PyListObject *self)
|
|
|
2047 {
|
|
|
2048 if (Py_SIZE(self) > 1)
|
|
|
2049 reverse_slice(self->ob_item, self->ob_item + Py_SIZE(self));
|
|
|
2050 Py_RETURN_NONE;
|
|
|
2051 }
|
|
|
2052
|
|
|
2053 int
|
|
|
2054 PyList_Reverse(PyObject *v)
|
|
|
2055 {
|
|
|
2056 PyListObject *self = (PyListObject *)v;
|
|
|
2057
|
|
|
2058 if (v == NULL || !PyList_Check(v)) {
|
|
|
2059 PyErr_BadInternalCall();
|
|
|
2060 return -1;
|
|
|
2061 }
|
|
|
2062 if (Py_SIZE(self) > 1)
|
|
|
2063 reverse_slice(self->ob_item, self->ob_item + Py_SIZE(self));
|
|
|
2064 return 0;
|
|
|
2065 }
|
|
|
2066
|
|
|
2067 PyObject *
|
|
|
2068 PyList_AsTuple(PyObject *v)
|
|
|
2069 {
|
|
|
2070 PyObject *w;
|
|
|
2071 PyObject **p, **q;
|
|
|
2072 Py_ssize_t n;
|
|
|
2073 if (v == NULL || !PyList_Check(v)) {
|
|
|
2074 PyErr_BadInternalCall();
|
|
|
2075 return NULL;
|
|
|
2076 }
|
|
|
2077 n = Py_SIZE(v);
|
|
|
2078 w = PyTuple_New(n);
|
|
|
2079 if (w == NULL)
|
|
|
2080 return NULL;
|
|
|
2081 p = ((PyTupleObject *)w)->ob_item;
|
|
|
2082 q = ((PyListObject *)v)->ob_item;
|
|
|
2083 while (--n >= 0) {
|
|
|
2084 Py_INCREF(*q);
|
|
|
2085 *p = *q;
|
|
|
2086 p++;
|
|
|
2087 q++;
|
|
|
2088 }
|
|
|
2089 return w;
|
|
|
2090 }
|
|
|
2091
|
|
|
2092 static PyObject *
|
|
|
2093 listindex(PyListObject *self, PyObject *args)
|
|
|
2094 {
|
|
|
2095 Py_ssize_t i, start=0, stop=Py_SIZE(self);
|
|
|
2096 PyObject *v;
|
|
|
2097
|
|
|
2098 if (!PyArg_ParseTuple(args, "O|O&O&:index", &v,
|
|
|
2099 _PyEval_SliceIndex, &start,
|
|
|
2100 _PyEval_SliceIndex, &stop))
|
|
|
2101 return NULL;
|
|
|
2102 if (start < 0) {
|
|
|
2103 start += Py_SIZE(self);
|
|
|
2104 if (start < 0)
|
|
|
2105 start = 0;
|
|
|
2106 }
|
|
|
2107 if (stop < 0) {
|
|
|
2108 stop += Py_SIZE(self);
|
|
|
2109 if (stop < 0)
|
|
|
2110 stop = 0;
|
|
|
2111 }
|
|
|
2112 for (i = start; i < stop && i < Py_SIZE(self); i++) {
|
|
|
2113 int cmp = PyObject_RichCompareBool(self->ob_item[i], v, Py_EQ);
|
|
|
2114 if (cmp > 0)
|
|
|
2115 return PyLong_FromSsize_t(i);
|
|
|
2116 else if (cmp < 0)
|
|
|
2117 return NULL;
|
|
|
2118 }
|
|
|
2119 PyErr_Format(PyExc_ValueError, "%R is not in list", v);
|
|
|
2120 return NULL;
|
|
|
2121 }
|
|
|
2122
|
|
|
2123 static PyObject *
|
|
|
2124 listcount(PyListObject *self, PyObject *v)
|
|
|
2125 {
|
|
|
2126 Py_ssize_t count = 0;
|
|
|
2127 Py_ssize_t i;
|
|
|
2128
|
|
|
2129 for (i = 0; i < Py_SIZE(self); i++) {
|
|
|
2130 int cmp = PyObject_RichCompareBool(self->ob_item[i], v, Py_EQ);
|
|
|
2131 if (cmp > 0)
|
|
|
2132 count++;
|
|
|
2133 else if (cmp < 0)
|
|
|
2134 return NULL;
|
|
|
2135 }
|
|
|
2136 return PyLong_FromSsize_t(count);
|
|
|
2137 }
|
|
|
2138
|
|
|
2139 static PyObject *
|
|
|
2140 listremove(PyListObject *self, PyObject *v)
|
|
|
2141 {
|
|
|
2142 Py_ssize_t i;
|
|
|
2143
|
|
|
2144 for (i = 0; i < Py_SIZE(self); i++) {
|
|
|
2145 int cmp = PyObject_RichCompareBool(self->ob_item[i], v, Py_EQ);
|
|
|
2146 if (cmp > 0) {
|
|
|
2147 if (list_ass_slice(self, i, i+1,
|
|
|
2148 (PyObject *)NULL) == 0)
|
|
|
2149 Py_RETURN_NONE;
|
|
|
2150 return NULL;
|
|
|
2151 }
|
|
|
2152 else if (cmp < 0)
|
|
|
2153 return NULL;
|
|
|
2154 }
|
|
|
2155 PyErr_SetString(PyExc_ValueError, "list.remove(x): x not in list");
|
|
|
2156 return NULL;
|
|
|
2157 }
|
|
|
2158
|
|
|
2159 static int
|
|
|
2160 list_traverse(PyListObject *o, visitproc visit, void *arg)
|
|
|
2161 {
|
|
|
2162 Py_ssize_t i;
|
|
|
2163
|
|
|
2164 for (i = Py_SIZE(o); --i >= 0; )
|
|
|
2165 Py_VISIT(o->ob_item[i]);
|
|
|
2166 return 0;
|
|
|
2167 }
|
|
|
2168
|
|
|
2169 static PyObject *
|
|
|
2170 list_richcompare(PyObject *v, PyObject *w, int op)
|
|
|
2171 {
|
|
|
2172 PyListObject *vl, *wl;
|
|
|
2173 Py_ssize_t i;
|
|
|
2174
|
|
|
2175 if (!PyList_Check(v) || !PyList_Check(w))
|
|
|
2176 Py_RETURN_NOTIMPLEMENTED;
|
|
|
2177
|
|
|
2178 vl = (PyListObject *)v;
|
|
|
2179 wl = (PyListObject *)w;
|
|
|
2180
|
|
|
2181 if (Py_SIZE(vl) != Py_SIZE(wl) && (op == Py_EQ || op == Py_NE)) {
|
|
|
2182 /* Shortcut: if the lengths differ, the lists differ */
|
|
|
2183 PyObject *res;
|
|
|
2184 if (op == Py_EQ)
|
|
|
2185 res = Py_False;
|
|
|
2186 else
|
|
|
2187 res = Py_True;
|
|
|
2188 Py_INCREF(res);
|
|
|
2189 return res;
|
|
|
2190 }
|
|
|
2191
|
|
|
2192 /* Search for the first index where items are different */
|
|
|
2193 for (i = 0; i < Py_SIZE(vl) && i < Py_SIZE(wl); i++) {
|
|
|
2194 int k = PyObject_RichCompareBool(vl->ob_item[i],
|
|
|
2195 wl->ob_item[i], Py_EQ);
|
|
|
2196 if (k < 0)
|
|
|
2197 return NULL;
|
|
|
2198 if (!k)
|
|
|
2199 break;
|
|
|
2200 }
|
|
|
2201
|
|
|
2202 if (i >= Py_SIZE(vl) || i >= Py_SIZE(wl)) {
|
|
|
2203 /* No more items to compare -- compare sizes */
|
|
|
2204 Py_ssize_t vs = Py_SIZE(vl);
|
|
|
2205 Py_ssize_t ws = Py_SIZE(wl);
|
|
|
2206 int cmp;
|
|
|
2207 PyObject *res;
|
|
|
2208 switch (op) {
|
|
|
2209 case Py_LT: cmp = vs < ws; break;
|
|
|
2210 case Py_LE: cmp = vs <= ws; break;
|
|
|
2211 case Py_EQ: cmp = vs == ws; break;
|
|
|
2212 case Py_NE: cmp = vs != ws; break;
|
|
|
2213 case Py_GT: cmp = vs > ws; break;
|
|
|
2214 case Py_GE: cmp = vs >= ws; break;
|
|
|
2215 default: return NULL; /* cannot happen */
|
|
|
2216 }
|
|
|
2217 if (cmp)
|
|
|
2218 res = Py_True;
|
|
|
2219 else
|
|
|
2220 res = Py_False;
|
|
|
2221 Py_INCREF(res);
|
|
|
2222 return res;
|
|
|
2223 }
|
|
|
2224
|
|
|
2225 /* We have an item that differs -- shortcuts for EQ/NE */
|
|
|
2226 if (op == Py_EQ) {
|
|
|
2227 Py_INCREF(Py_False);
|
|
|
2228 return Py_False;
|
|
|
2229 }
|
|
|
2230 if (op == Py_NE) {
|
|
|
2231 Py_INCREF(Py_True);
|
|
|
2232 return Py_True;
|
|
|
2233 }
|
|
|
2234
|
|
|
2235 /* Compare the final item again using the proper operator */
|
|
|
2236 return PyObject_RichCompare(vl->ob_item[i], wl->ob_item[i], op);
|
|
|
2237 }
|
|
|
2238
|
|
|
2239 static int
|
|
|
2240 list_init(PyListObject *self, PyObject *args, PyObject *kw)
|
|
|
2241 {
|
|
|
2242 PyObject *arg = NULL;
|
|
|
2243 static char *kwlist[] = {"sequence", 0};
|
|
|
2244
|
|
|
2245 if (!PyArg_ParseTupleAndKeywords(args, kw, "|O:list", kwlist, &arg))
|
|
|
2246 return -1;
|
|
|
2247
|
|
|
2248 /* Verify list invariants established by PyType_GenericAlloc() */
|
|
|
2249 assert(0 <= Py_SIZE(self));
|
|
|
2250 assert(Py_SIZE(self) <= self->allocated || self->allocated == -1);
|
|
|
2251 assert(self->ob_item != NULL ||
|
|
|
2252 self->allocated == 0 || self->allocated == -1);
|
|
|
2253
|
|
|
2254 /* Empty previous contents */
|
|
|
2255 if (self->ob_item != NULL) {
|
|
|
2256 (void)list_clear(self);
|
|
|
2257 }
|
|
|
2258 if (arg != NULL) {
|
|
|
2259 PyObject *rv = listextend(self, arg);
|
|
|
2260 if (rv == NULL)
|
|
|
2261 return -1;
|
|
|
2262 Py_DECREF(rv);
|
|
|
2263 }
|
|
|
2264 return 0;
|
|
|
2265 }
|
|
|
2266
|
|
|
2267 static PyObject *
|
|
|
2268 list_sizeof(PyListObject *self)
|
|
|
2269 {
|
|
|
2270 Py_ssize_t res;
|
|
|
2271
|
|
|
2272 res = sizeof(PyListObject) + self->allocated * sizeof(void*);
|
|
|
2273 return PyLong_FromSsize_t(res);
|
|
|
2274 }
|
|
|
2275
|
|
|
2276 static PyObject *list_iter(PyObject *seq);
|
|
|
2277 static PyObject *list_reversed(PyListObject* seq, PyObject* unused);
|
|
|
2278
|
|
|
2279 PyDoc_STRVAR(getitem_doc,
|
|
|
2280 "x.__getitem__(y) <==> x[y]");
|
|
|
2281 PyDoc_STRVAR(reversed_doc,
|
|
|
2282 "L.__reversed__() -- return a reverse iterator over the list");
|
|
|
2283 PyDoc_STRVAR(sizeof_doc,
|
|
|
2284 "L.__sizeof__() -- size of L in memory, in bytes");
|
|
|
2285 PyDoc_STRVAR(clear_doc,
|
|
|
2286 "L.clear() -> None -- remove all items from L");
|
|
|
2287 PyDoc_STRVAR(copy_doc,
|
|
|
2288 "L.copy() -> list -- a shallow copy of L");
|
|
|
2289 PyDoc_STRVAR(append_doc,
|
|
|
2290 "L.append(object) -> None -- append object to end");
|
|
|
2291 PyDoc_STRVAR(extend_doc,
|
|
|
2292 "L.extend(iterable) -> None -- extend list by appending elements from the iterable");
|
|
|
2293 PyDoc_STRVAR(insert_doc,
|
|
|
2294 "L.insert(index, object) -- insert object before index");
|
|
|
2295 PyDoc_STRVAR(pop_doc,
|
|
|
2296 "L.pop([index]) -> item -- remove and return item at index (default last).\n"
|
|
|
2297 "Raises IndexError if list is empty or index is out of range.");
|
|
|
2298 PyDoc_STRVAR(remove_doc,
|
|
|
2299 "L.remove(value) -> None -- remove first occurrence of value.\n"
|
|
|
2300 "Raises ValueError if the value is not present.");
|
|
|
2301 PyDoc_STRVAR(index_doc,
|
|
|
2302 "L.index(value, [start, [stop]]) -> integer -- return first index of value.\n"
|
|
|
2303 "Raises ValueError if the value is not present.");
|
|
|
2304 PyDoc_STRVAR(count_doc,
|
|
|
2305 "L.count(value) -> integer -- return number of occurrences of value");
|
|
|
2306 PyDoc_STRVAR(reverse_doc,
|
|
|
2307 "L.reverse() -- reverse *IN PLACE*");
|
|
|
2308 PyDoc_STRVAR(sort_doc,
|
|
|
2309 "L.sort(key=None, reverse=False) -> None -- stable sort *IN PLACE*");
|
|
|
2310
|
|
|
2311 static PyObject *list_subscript(PyListObject*, PyObject*);
|
|
|
2312
|
|
|
2313 static PyMethodDef list_methods[] = {
|
|
|
2314 {"__getitem__", (PyCFunction)list_subscript, METH_O|METH_COEXIST, getitem_doc},
|
|
|
2315 {"__reversed__",(PyCFunction)list_reversed, METH_NOARGS, reversed_doc},
|
|
|
2316 {"__sizeof__", (PyCFunction)list_sizeof, METH_NOARGS, sizeof_doc},
|
|
|
2317 {"clear", (PyCFunction)listclear, METH_NOARGS, clear_doc},
|
|
|
2318 {"copy", (PyCFunction)listcopy, METH_NOARGS, copy_doc},
|
|
|
2319 {"append", (PyCFunction)listappend, METH_O, append_doc},
|
|
|
2320 {"insert", (PyCFunction)listinsert, METH_VARARGS, insert_doc},
|
|
|
2321 {"extend", (PyCFunction)listextend, METH_O, extend_doc},
|
|
|
2322 {"pop", (PyCFunction)listpop, METH_VARARGS, pop_doc},
|
|
|
2323 {"remove", (PyCFunction)listremove, METH_O, remove_doc},
|
|
|
2324 {"index", (PyCFunction)listindex, METH_VARARGS, index_doc},
|
|
|
2325 {"count", (PyCFunction)listcount, METH_O, count_doc},
|
|
|
2326 {"reverse", (PyCFunction)listreverse, METH_NOARGS, reverse_doc},
|
|
|
2327 {"sort", (PyCFunction)listsort, METH_VARARGS | METH_KEYWORDS, sort_doc},
|
|
|
2328 {NULL, NULL} /* sentinel */
|
|
|
2329 };
|
|
|
2330
|
|
|
2331 static PySequenceMethods list_as_sequence = {
|
|
|
2332 (lenfunc)list_length, /* sq_length */
|
|
|
2333 (binaryfunc)list_concat, /* sq_concat */
|
|
|
2334 (ssizeargfunc)list_repeat, /* sq_repeat */
|
|
|
2335 (ssizeargfunc)list_item, /* sq_item */
|
|
|
2336 0, /* sq_slice */
|
|
|
2337 (ssizeobjargproc)list_ass_item, /* sq_ass_item */
|
|
|
2338 0, /* sq_ass_slice */
|
|
|
2339 (objobjproc)list_contains, /* sq_contains */
|
|
|
2340 (binaryfunc)list_inplace_concat, /* sq_inplace_concat */
|
|
|
2341 (ssizeargfunc)list_inplace_repeat, /* sq_inplace_repeat */
|
|
|
2342 };
|
|
|
2343
|
|
|
2344 PyDoc_STRVAR(list_doc,
|
|
|
2345 "list() -> new empty list\n"
|
|
|
2346 "list(iterable) -> new list initialized from iterable's items");
|
|
|
2347
|
|
|
2348 static PyObject *
|
|
|
2349 list_subscript(PyListObject* self, PyObject* item)
|
|
|
2350 {
|
|
|
2351 if (PyIndex_Check(item)) {
|
|
|
2352 Py_ssize_t i;
|
|
|
2353 i = PyNumber_AsSsize_t(item, PyExc_IndexError);
|
|
|
2354 if (i == -1 && PyErr_Occurred())
|
|
|
2355 return NULL;
|
|
|
2356 if (i < 0)
|
|
|
2357 i += PyList_GET_SIZE(self);
|
|
|
2358 return list_item(self, i);
|
|
|
2359 }
|
|
|
2360 else if (PySlice_Check(item)) {
|
|
|
2361 Py_ssize_t start, stop, step, slicelength, cur, i;
|
|
|
2362 PyObject* result;
|
|
|
2363 PyObject* it;
|
|
|
2364 PyObject **src, **dest;
|
|
|
2365
|
|
|
2366 if (PySlice_GetIndicesEx(item, Py_SIZE(self),
|
|
|
2367 &start, &stop, &step, &slicelength) < 0) {
|
|
|
2368 return NULL;
|
|
|
2369 }
|
|
|
2370
|
|
|
2371 if (slicelength <= 0) {
|
|
|
2372 return PyList_New(0);
|
|
|
2373 }
|
|
|
2374 else if (step == 1) {
|
|
|
2375 return list_slice(self, start, stop);
|
|
|
2376 }
|
|
|
2377 else {
|
|
|
2378 result = PyList_New(slicelength);
|
|
|
2379 if (!result) return NULL;
|
|
|
2380
|
|
|
2381 src = self->ob_item;
|
|
|
2382 dest = ((PyListObject *)result)->ob_item;
|
|
|
2383 for (cur = start, i = 0; i < slicelength;
|
|
|
2384 cur += (size_t)step, i++) {
|
|
|
2385 it = src[cur];
|
|
|
2386 Py_INCREF(it);
|
|
|
2387 dest[i] = it;
|
|
|
2388 }
|
|
|
2389
|
|
|
2390 return result;
|
|
|
2391 }
|
|
|
2392 }
|
|
|
2393 else {
|
|
|
2394 PyErr_Format(PyExc_TypeError,
|
|
|
2395 "list indices must be integers, not %.200s",
|
|
|
2396 item->ob_type->tp_name);
|
|
|
2397 return NULL;
|
|
|
2398 }
|
|
|
2399 }
|
|
|
2400
|
|
|
2401 static int
|
|
|
2402 list_ass_subscript(PyListObject* self, PyObject* item, PyObject* value)
|
|
|
2403 {
|
|
|
2404 if (PyIndex_Check(item)) {
|
|
|
2405 Py_ssize_t i = PyNumber_AsSsize_t(item, PyExc_IndexError);
|
|
|
2406 if (i == -1 && PyErr_Occurred())
|
|
|
2407 return -1;
|
|
|
2408 if (i < 0)
|
|
|
2409 i += PyList_GET_SIZE(self);
|
|
|
2410 return list_ass_item(self, i, value);
|
|
|
2411 }
|
|
|
2412 else if (PySlice_Check(item)) {
|
|
|
2413 Py_ssize_t start, stop, step, slicelength;
|
|
|
2414
|
|
|
2415 if (PySlice_GetIndicesEx(item, Py_SIZE(self),
|
|
|
2416 &start, &stop, &step, &slicelength) < 0) {
|
|
|
2417 return -1;
|
|
|
2418 }
|
|
|
2419
|
|
|
2420 if (step == 1)
|
|
|
2421 return list_ass_slice(self, start, stop, value);
|
|
|
2422
|
|
|
2423 /* Make sure s[5:2] = [..] inserts at the right place:
|
|
|
2424 before 5, not before 2. */
|
|
|
2425 if ((step < 0 && start < stop) ||
|
|
|
2426 (step > 0 && start > stop))
|
|
|
2427 stop = start;
|
|
|
2428
|
|
|
2429 if (value == NULL) {
|
|
|
2430 /* delete slice */
|
|
|
2431 PyObject **garbage;
|
|
|
2432 size_t cur;
|
|
|
2433 Py_ssize_t i;
|
|
|
2434
|
|
|
2435 if (slicelength <= 0)
|
|
|
2436 return 0;
|
|
|
2437
|
|
|
2438 if (step < 0) {
|
|
|
2439 stop = start + 1;
|
|
|
2440 start = stop + step*(slicelength - 1) - 1;
|
|
|
2441 step = -step;
|
|
|
2442 }
|
|
|
2443
|
|
|
2444 assert((size_t)slicelength <=
|
|
|
2445 PY_SIZE_MAX / sizeof(PyObject*));
|
|
|
2446
|
|
|
2447 garbage = (PyObject**)
|
|
|
2448 PyMem_MALLOC(slicelength*sizeof(PyObject*));
|
|
|
2449 if (!garbage) {
|
|
|
2450 PyErr_NoMemory();
|
|
|
2451 return -1;
|
|
|
2452 }
|
|
|
2453
|
|
|
2454 /* drawing pictures might help understand these for
|
|
|
2455 loops. Basically, we memmove the parts of the
|
|
|
2456 list that are *not* part of the slice: step-1
|
|
|
2457 items for each item that is part of the slice,
|
|
|
2458 and then tail end of the list that was not
|
|
|
2459 covered by the slice */
|
|
|
2460 for (cur = start, i = 0;
|
|
|
2461 cur < (size_t)stop;
|
|
|
2462 cur += step, i++) {
|
|
|
2463 Py_ssize_t lim = step - 1;
|
|
|
2464
|
|
|
2465 garbage[i] = PyList_GET_ITEM(self, cur);
|
|
|
2466
|
|
|
2467 if (cur + step >= (size_t)Py_SIZE(self)) {
|
|
|
2468 lim = Py_SIZE(self) - cur - 1;
|
|
|
2469 }
|
|
|
2470
|
|
|
2471 memmove(self->ob_item + cur - i,
|
|
|
2472 self->ob_item + cur + 1,
|
|
|
2473 lim * sizeof(PyObject *));
|
|
|
2474 }
|
|
|
2475 cur = start + (size_t)slicelength * step;
|
|
|
2476 if (cur < (size_t)Py_SIZE(self)) {
|
|
|
2477 memmove(self->ob_item + cur - slicelength,
|
|
|
2478 self->ob_item + cur,
|
|
|
2479 (Py_SIZE(self) - cur) *
|
|
|
2480 sizeof(PyObject *));
|
|
|
2481 }
|
|
|
2482
|
|
|
2483 Py_SIZE(self) -= slicelength;
|
|
|
2484 list_resize(self, Py_SIZE(self));
|
|
|
2485
|
|
|
2486 for (i = 0; i < slicelength; i++) {
|
|
|
2487 Py_DECREF(garbage[i]);
|
|
|
2488 }
|
|
|
2489 PyMem_FREE(garbage);
|
|
|
2490
|
|
|
2491 return 0;
|
|
|
2492 }
|
|
|
2493 else {
|
|
|
2494 /* assign slice */
|
|
|
2495 PyObject *ins, *seq;
|
|
|
2496 PyObject **garbage, **seqitems, **selfitems;
|
|
|
2497 Py_ssize_t cur, i;
|
|
|
2498
|
|
|
2499 /* protect against a[::-1] = a */
|
|
|
2500 if (self == (PyListObject*)value) {
|
|
|
2501 seq = list_slice((PyListObject*)value, 0,
|
|
|
2502 PyList_GET_SIZE(value));
|
|
|
2503 }
|
|
|
2504 else {
|
|
|
2505 seq = PySequence_Fast(value,
|
|
|
2506 "must assign iterable "
|
|
|
2507 "to extended slice");
|
|
|
2508 }
|
|
|
2509 if (!seq)
|
|
|
2510 return -1;
|
|
|
2511
|
|
|
2512 if (PySequence_Fast_GET_SIZE(seq) != slicelength) {
|
|
|
2513 PyErr_Format(PyExc_ValueError,
|
|
|
2514 "attempt to assign sequence of "
|
|
|
2515 "size %zd to extended slice of "
|
|
|
2516 "size %zd",
|
|
|
2517 PySequence_Fast_GET_SIZE(seq),
|
|
|
2518 slicelength);
|
|
|
2519 Py_DECREF(seq);
|
|
|
2520 return -1;
|
|
|
2521 }
|
|
|
2522
|
|
|
2523 if (!slicelength) {
|
|
|
2524 Py_DECREF(seq);
|
|
|
2525 return 0;
|
|
|
2526 }
|
|
|
2527
|
|
|
2528 garbage = (PyObject**)
|
|
|
2529 PyMem_MALLOC(slicelength*sizeof(PyObject*));
|
|
|
2530 if (!garbage) {
|
|
|
2531 Py_DECREF(seq);
|
|
|
2532 PyErr_NoMemory();
|
|
|
2533 return -1;
|
|
|
2534 }
|
|
|
2535
|
|
|
2536 selfitems = self->ob_item;
|
|
|
2537 seqitems = PySequence_Fast_ITEMS(seq);
|
|
|
2538 for (cur = start, i = 0; i < slicelength;
|
|
|
2539 cur += (size_t)step, i++) {
|
|
|
2540 garbage[i] = selfitems[cur];
|
|
|
2541 ins = seqitems[i];
|
|
|
2542 Py_INCREF(ins);
|
|
|
2543 selfitems[cur] = ins;
|
|
|
2544 }
|
|
|
2545
|
|
|
2546 for (i = 0; i < slicelength; i++) {
|
|
|
2547 Py_DECREF(garbage[i]);
|
|
|
2548 }
|
|
|
2549
|
|
|
2550 PyMem_FREE(garbage);
|
|
|
2551 Py_DECREF(seq);
|
|
|
2552
|
|
|
2553 return 0;
|
|
|
2554 }
|
|
|
2555 }
|
|
|
2556 else {
|
|
|
2557 PyErr_Format(PyExc_TypeError,
|
|
|
2558 "list indices must be integers, not %.200s",
|
|
|
2559 item->ob_type->tp_name);
|
|
|
2560 return -1;
|
|
|
2561 }
|
|
|
2562 }
|
|
|
2563
|
|
|
2564 static PyMappingMethods list_as_mapping = {
|
|
|
2565 (lenfunc)list_length,
|
|
|
2566 (binaryfunc)list_subscript,
|
|
|
2567 (objobjargproc)list_ass_subscript
|
|
|
2568 };
|
|
|
2569
|
|
|
2570 PyTypeObject PyList_Type = {
|
|
|
2571 PyVarObject_HEAD_INIT(&PyType_Type, 0)
|
|
|
2572 "list",
|
|
|
2573 sizeof(PyListObject),
|
|
|
2574 0,
|
|
|
2575 (destructor)list_dealloc, /* tp_dealloc */
|
|
|
2576 0, /* tp_print */
|
|
|
2577 0, /* tp_getattr */
|
|
|
2578 0, /* tp_setattr */
|
|
|
2579 0, /* tp_reserved */
|
|
|
2580 (reprfunc)list_repr, /* tp_repr */
|
|
|
2581 0, /* tp_as_number */
|
|
|
2582 &list_as_sequence, /* tp_as_sequence */
|
|
|
2583 &list_as_mapping, /* tp_as_mapping */
|
|
|
2584 PyObject_HashNotImplemented, /* tp_hash */
|
|
|
2585 0, /* tp_call */
|
|
|
2586 0, /* tp_str */
|
|
|
2587 PyObject_GenericGetAttr, /* tp_getattro */
|
|
|
2588 0, /* tp_setattro */
|
|
|
2589 0, /* tp_as_buffer */
|
|
|
2590 Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC |
|
|
|
2591 Py_TPFLAGS_BASETYPE | Py_TPFLAGS_LIST_SUBCLASS, /* tp_flags */
|
|
|
2592 list_doc, /* tp_doc */
|
|
|
2593 (traverseproc)list_traverse, /* tp_traverse */
|
|
|
2594 (inquiry)list_clear, /* tp_clear */
|
|
|
2595 list_richcompare, /* tp_richcompare */
|
|
|
2596 0, /* tp_weaklistoffset */
|
|
|
2597 list_iter, /* tp_iter */
|
|
|
2598 0, /* tp_iternext */
|
|
|
2599 list_methods, /* tp_methods */
|
|
|
2600 0, /* tp_members */
|
|
|
2601 0, /* tp_getset */
|
|
|
2602 0, /* tp_base */
|
|
|
2603 0, /* tp_dict */
|
|
|
2604 0, /* tp_descr_get */
|
|
|
2605 0, /* tp_descr_set */
|
|
|
2606 0, /* tp_dictoffset */
|
|
|
2607 (initproc)list_init, /* tp_init */
|
|
|
2608 PyType_GenericAlloc, /* tp_alloc */
|
|
|
2609 PyType_GenericNew, /* tp_new */
|
|
|
2610 PyObject_GC_Del, /* tp_free */
|
|
|
2611 };
|
|
|
2612
|
|
|
2613
|
|
|
2614 /*********************** List Iterator **************************/
|
|
|
2615
|
|
|
2616 typedef struct {
|
|
|
2617 PyObject_HEAD
|
|
|
2618 long it_index;
|
|
|
2619 PyListObject *it_seq; /* Set to NULL when iterator is exhausted */
|
|
|
2620 } listiterobject;
|
|
|
2621
|
|
|
2622 static PyObject *list_iter(PyObject *);
|
|
|
2623 static void listiter_dealloc(listiterobject *);
|
|
|
2624 static int listiter_traverse(listiterobject *, visitproc, void *);
|
|
|
2625 static PyObject *listiter_next(listiterobject *);
|
|
|
2626 static PyObject *listiter_len(listiterobject *);
|
|
|
2627
|
|
|
2628 PyDoc_STRVAR(length_hint_doc, "Private method returning an estimate of len(list(it)).");
|
|
|
2629
|
|
|
2630 static PyMethodDef listiter_methods[] = {
|
|
|
2631 {"__length_hint__", (PyCFunction)listiter_len, METH_NOARGS, length_hint_doc},
|
|
|
2632 {NULL, NULL} /* sentinel */
|
|
|
2633 };
|
|
|
2634
|
|
|
2635 PyTypeObject PyListIter_Type = {
|
|
|
2636 PyVarObject_HEAD_INIT(&PyType_Type, 0)
|
|
|
2637 "list_iterator", /* tp_name */
|
|
|
2638 sizeof(listiterobject), /* tp_basicsize */
|
|
|
2639 0, /* tp_itemsize */
|
|
|
2640 /* methods */
|
|
|
2641 (destructor)listiter_dealloc, /* tp_dealloc */
|
|
|
2642 0, /* tp_print */
|
|
|
2643 0, /* tp_getattr */
|
|
|
2644 0, /* tp_setattr */
|
|
|
2645 0, /* tp_reserved */
|
|
|
2646 0, /* tp_repr */
|
|
|
2647 0, /* tp_as_number */
|
|
|
2648 0, /* tp_as_sequence */
|
|
|
2649 0, /* tp_as_mapping */
|
|
|
2650 0, /* tp_hash */
|
|
|
2651 0, /* tp_call */
|
|
|
2652 0, /* tp_str */
|
|
|
2653 PyObject_GenericGetAttr, /* tp_getattro */
|
|
|
2654 0, /* tp_setattro */
|
|
|
2655 0, /* tp_as_buffer */
|
|
|
2656 Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC,/* tp_flags */
|
|
|
2657 0, /* tp_doc */
|
|
|
2658 (traverseproc)listiter_traverse, /* tp_traverse */
|
|
|
2659 0, /* tp_clear */
|
|
|
2660 0, /* tp_richcompare */
|
|
|
2661 0, /* tp_weaklistoffset */
|
|
|
2662 PyObject_SelfIter, /* tp_iter */
|
|
|
2663 (iternextfunc)listiter_next, /* tp_iternext */
|
|
|
2664 listiter_methods, /* tp_methods */
|
|
|
2665 0, /* tp_members */
|
|
|
2666 };
|
|
|
2667
|
|
|
2668
|
|
|
2669 static PyObject *
|
|
|
2670 list_iter(PyObject *seq)
|
|
|
2671 {
|
|
|
2672 listiterobject *it;
|
|
|
2673
|
|
|
2674 if (!PyList_Check(seq)) {
|
|
|
2675 PyErr_BadInternalCall();
|
|
|
2676 return NULL;
|
|
|
2677 }
|
|
|
2678 it = PyObject_GC_New(listiterobject, &PyListIter_Type);
|
|
|
2679 if (it == NULL)
|
|
|
2680 return NULL;
|
|
|
2681 it->it_index = 0;
|
|
|
2682 Py_INCREF(seq);
|
|
|
2683 it->it_seq = (PyListObject *)seq;
|
|
|
2684 _PyObject_GC_TRACK(it);
|
|
|
2685 return (PyObject *)it;
|
|
|
2686 }
|
|
|
2687
|
|
|
2688 static void
|
|
|
2689 listiter_dealloc(listiterobject *it)
|
|
|
2690 {
|
|
|
2691 _PyObject_GC_UNTRACK(it);
|
|
|
2692 Py_XDECREF(it->it_seq);
|
|
|
2693 PyObject_GC_Del(it);
|
|
|
2694 }
|
|
|
2695
|
|
|
2696 static int
|
|
|
2697 listiter_traverse(listiterobject *it, visitproc visit, void *arg)
|
|
|
2698 {
|
|
|
2699 Py_VISIT(it->it_seq);
|
|
|
2700 return 0;
|
|
|
2701 }
|
|
|
2702
|
|
|
2703 static PyObject *
|
|
|
2704 listiter_next(listiterobject *it)
|
|
|
2705 {
|
|
|
2706 PyListObject *seq;
|
|
|
2707 PyObject *item;
|
|
|
2708
|
|
|
2709 assert(it != NULL);
|
|
|
2710 seq = it->it_seq;
|
|
|
2711 if (seq == NULL)
|
|
|
2712 return NULL;
|
|
|
2713 assert(PyList_Check(seq));
|
|
|
2714
|
|
|
2715 if (it->it_index < PyList_GET_SIZE(seq)) {
|
|
|
2716 item = PyList_GET_ITEM(seq, it->it_index);
|
|
|
2717 ++it->it_index;
|
|
|
2718 Py_INCREF(item);
|
|
|
2719 return item;
|
|
|
2720 }
|
|
|
2721
|
|
|
2722 Py_DECREF(seq);
|
|
|
2723 it->it_seq = NULL;
|
|
|
2724 return NULL;
|
|
|
2725 }
|
|
|
2726
|
|
|
2727 static PyObject *
|
|
|
2728 listiter_len(listiterobject *it)
|
|
|
2729 {
|
|
|
2730 Py_ssize_t len;
|
|
|
2731 if (it->it_seq) {
|
|
|
2732 len = PyList_GET_SIZE(it->it_seq) - it->it_index;
|
|
|
2733 if (len >= 0)
|
|
|
2734 return PyLong_FromSsize_t(len);
|
|
|
2735 }
|
|
|
2736 return PyLong_FromLong(0);
|
|
|
2737 }
|
|
|
2738 /*********************** List Reverse Iterator **************************/
|
|
|
2739
|
|
|
2740 typedef struct {
|
|
|
2741 PyObject_HEAD
|
|
|
2742 Py_ssize_t it_index;
|
|
|
2743 PyListObject *it_seq; /* Set to NULL when iterator is exhausted */
|
|
|
2744 } listreviterobject;
|
|
|
2745
|
|
|
2746 static PyObject *list_reversed(PyListObject *, PyObject *);
|
|
|
2747 static void listreviter_dealloc(listreviterobject *);
|
|
|
2748 static int listreviter_traverse(listreviterobject *, visitproc, void *);
|
|
|
2749 static PyObject *listreviter_next(listreviterobject *);
|
|
|
2750 static PyObject *listreviter_len(listreviterobject *);
|
|
|
2751
|
|
|
2752 static PyMethodDef listreviter_methods[] = {
|
|
|
2753 {"__length_hint__", (PyCFunction)listreviter_len, METH_NOARGS, length_hint_doc},
|
|
|
2754 {NULL, NULL} /* sentinel */
|
|
|
2755 };
|
|
|
2756
|
|
|
2757 PyTypeObject PyListRevIter_Type = {
|
|
|
2758 PyVarObject_HEAD_INIT(&PyType_Type, 0)
|
|
|
2759 "list_reverseiterator", /* tp_name */
|
|
|
2760 sizeof(listreviterobject), /* tp_basicsize */
|
|
|
2761 0, /* tp_itemsize */
|
|
|
2762 /* methods */
|
|
|
2763 (destructor)listreviter_dealloc, /* tp_dealloc */
|
|
|
2764 0, /* tp_print */
|
|
|
2765 0, /* tp_getattr */
|
|
|
2766 0, /* tp_setattr */
|
|
|
2767 0, /* tp_reserved */
|
|
|
2768 0, /* tp_repr */
|
|
|
2769 0, /* tp_as_number */
|
|
|
2770 0, /* tp_as_sequence */
|
|
|
2771 0, /* tp_as_mapping */
|
|
|
2772 0, /* tp_hash */
|
|
|
2773 0, /* tp_call */
|
|
|
2774 0, /* tp_str */
|
|
|
2775 PyObject_GenericGetAttr, /* tp_getattro */
|
|
|
2776 0, /* tp_setattro */
|
|
|
2777 0, /* tp_as_buffer */
|
|
|
2778 Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC,/* tp_flags */
|
|
|
2779 0, /* tp_doc */
|
|
|
2780 (traverseproc)listreviter_traverse, /* tp_traverse */
|
|
|
2781 0, /* tp_clear */
|
|
|
2782 0, /* tp_richcompare */
|
|
|
2783 0, /* tp_weaklistoffset */
|
|
|
2784 PyObject_SelfIter, /* tp_iter */
|
|
|
2785 (iternextfunc)listreviter_next, /* tp_iternext */
|
|
|
2786 listreviter_methods, /* tp_methods */
|
|
|
2787 0,
|
|
|
2788 };
|
|
|
2789
|
|
|
2790 static PyObject *
|
|
|
2791 list_reversed(PyListObject *seq, PyObject *unused)
|
|
|
2792 {
|
|
|
2793 listreviterobject *it;
|
|
|
2794
|
|
|
2795 it = PyObject_GC_New(listreviterobject, &PyListRevIter_Type);
|
|
|
2796 if (it == NULL)
|
|
|
2797 return NULL;
|
|
|
2798 assert(PyList_Check(seq));
|
|
|
2799 it->it_index = PyList_GET_SIZE(seq) - 1;
|
|
|
2800 Py_INCREF(seq);
|
|
|
2801 it->it_seq = seq;
|
|
|
2802 PyObject_GC_Track(it);
|
|
|
2803 return (PyObject *)it;
|
|
|
2804 }
|
|
|
2805
|
|
|
2806 static void
|
|
|
2807 listreviter_dealloc(listreviterobject *it)
|
|
|
2808 {
|
|
|
2809 PyObject_GC_UnTrack(it);
|
|
|
2810 Py_XDECREF(it->it_seq);
|
|
|
2811 PyObject_GC_Del(it);
|
|
|
2812 }
|
|
|
2813
|
|
|
2814 static int
|
|
|
2815 listreviter_traverse(listreviterobject *it, visitproc visit, void *arg)
|
|
|
2816 {
|
|
|
2817 Py_VISIT(it->it_seq);
|
|
|
2818 return 0;
|
|
|
2819 }
|
|
|
2820
|
|
|
2821 static PyObject *
|
|
|
2822 listreviter_next(listreviterobject *it)
|
|
|
2823 {
|
|
|
2824 PyObject *item;
|
|
|
2825 Py_ssize_t index = it->it_index;
|
|
|
2826 PyListObject *seq = it->it_seq;
|
|
|
2827
|
|
|
2828 if (index>=0 && index < PyList_GET_SIZE(seq)) {
|
|
|
2829 item = PyList_GET_ITEM(seq, index);
|
|
|
2830 it->it_index--;
|
|
|
2831 Py_INCREF(item);
|
|
|
2832 return item;
|
|
|
2833 }
|
|
|
2834 it->it_index = -1;
|
|
|
2835 if (seq != NULL) {
|
|
|
2836 it->it_seq = NULL;
|
|
|
2837 Py_DECREF(seq);
|
|
|
2838 }
|
|
|
2839 return NULL;
|
|
|
2840 }
|
|
|
2841
|
|
|
2842 static PyObject *
|
|
|
2843 listreviter_len(listreviterobject *it)
|
|
|
2844 {
|
|
|
2845 Py_ssize_t len = it->it_index + 1;
|
|
|
2846 if (it->it_seq == NULL || PyList_GET_SIZE(it->it_seq) < len)
|
|
|
2847 len = 0;
|
|
|
2848 return PyLong_FromSsize_t(len);
|
|
|
2849 }
|
