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