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