Python code coverage for Objects/listobject.c

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