ยปCore Development>Code coverage>Objects/listobject.c

Python code coverage for Objects/listobject.c

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