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