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