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