1 /* List object implementation */

     2 

     3 #include "Python.h"

     4 

     5 #ifdef STDC_HEADERS

     6 #include <stddef.h>

     7 #else

     8 #include <sys/types.h>		/* For size_t */

     9 #endif

    10 

    11 /* Ensure ob_item has room for at least newsize elements, and set

    12  * ob_size to newsize.  If newsize > ob_size on entry, the content

    13  * of the new slots at exit is undefined heap trash; it's the caller's

    14  * responsiblity to overwrite them with sane values.

    15  * The number of allocated elements may grow, shrink, or stay the same.

    16  * Failure is impossible if newsize <= self.allocated on entry, although

    17  * that partly relies on an assumption that the system realloc() never

    18  * fails when passed a number of bytes <= the number of bytes last

    19  * allocated (the C standard doesn't guarantee this, but it's hard to

    20  * imagine a realloc implementation where it wouldn't be true).

    21  * Note that self->ob_item may change, and even if newsize is less

    22  * than ob_size on entry.

    23  */

    24 static int

    25 list_resize(PyListObject *self, Py_ssize_t newsize)

    26 {

    27 	PyObject **items;

    28 	size_t new_allocated;

    29 	Py_ssize_t allocated = self->allocated;

    30 

    31 	/* Bypass realloc() when a previous overallocation is large enough

    32 	   to accommodate the newsize.  If the newsize falls lower than half

    33 	   the allocated size, then proceed with the realloc() to shrink the list.

    34 	*/

    35 	if (allocated >= newsize && newsize >= (allocated >> 1)) {

    36 		assert(self->ob_item != NULL || newsize == 0);

    37 		Py_SIZE(self) = newsize;

    38 		return 0;

    39 	}

    40 

    41 	/* This over-allocates proportional to the list size, making room

    42 	 * for additional growth.  The over-allocation is mild, but is

    43 	 * enough to give linear-time amortized behavior over a long

    44 	 * sequence of appends() in the presence of a poorly-performing

    45 	 * system realloc().

    46 	 * The growth pattern is:  0, 4, 8, 16, 25, 35, 46, 58, 72, 88, ...

    47 	 */

    48 	new_allocated = (newsize >> 3) + (newsize < 9 ? 3 : 6);

    49 

    50 	/* check for integer overflow */

    51 	if (new_allocated > PY_SIZE_MAX - newsize) {

    52 		PyErr_NoMemory();

    53 		return -1;

    54 	} else {

    55 		new_allocated += newsize;

    56 	}

    57 

    58 	if (newsize == 0)

    59 		new_allocated = 0;

    60 	items = self->ob_item;

    61 	if (new_allocated <= ((~(size_t)0) / sizeof(PyObject *)))

    62 		PyMem_RESIZE(items, PyObject *, new_allocated);

    63 	else

    64 		items = NULL;

    65 	if (items == NULL) {

    66 		PyErr_NoMemory();

    67 		return -1;

    68 	}

    69 	self->ob_item = items;

    70 	Py_SIZE(self) = newsize;

    71 	self->allocated = new_allocated;

    72 	return 0;

    73 }

    74 

    75 /* Debug statistic to compare allocations with reuse through the free list */

    76 #undef SHOW_ALLOC_COUNT

    77 #ifdef SHOW_ALLOC_COUNT

    78 static size_t count_alloc = 0;

    79 static size_t count_reuse = 0;

    80 

    81 static void

    82 show_alloc(void)

    83 {

    84 	fprintf(stderr, "List allocations: %" PY_FORMAT_SIZE_T "d\n",

    85 		count_alloc);

    86 	fprintf(stderr, "List reuse through freelist: %" PY_FORMAT_SIZE_T

    87 		"d\n", count_reuse);

    88 	fprintf(stderr, "%.2f%% reuse rate\n\n",

    89 		(100.0*count_reuse/(count_alloc+count_reuse)));

    90 }

    91 #endif

    92 

    93 /* Empty list reuse scheme to save calls to malloc and free */

    94 #ifndef PyList_MAXFREELIST

    95 #define PyList_MAXFREELIST 80

    96 #endif

    97 static PyListObject *free_list[PyList_MAXFREELIST];

    98 static int numfree = 0;

    99 

   100 void

   101 PyList_Fini(void)

   102 {

   103 	PyListObject *op;

   104 

   105 	while (numfree) {

   106 		op = free_list[--numfree];

   107 		assert(PyList_CheckExact(op));

   108 		PyObject_GC_Del(op);

   109 	}

   110 }

   111 

   112 PyObject *

   113 PyList_New(Py_ssize_t size)

   114 {

   115 	PyListObject *op;

   116 	size_t nbytes;

   117 #ifdef SHOW_ALLOC_COUNT

   118 	static int initialized = 0;

   119 	if (!initialized) {

   120 		Py_AtExit(show_alloc);

   121 		initialized = 1;

   122 	}

   123 #endif

   124 

   125 	if (size < 0) {

   126 		PyErr_BadInternalCall();

   127 		return NULL;

   128 	}

   129 	nbytes = size * sizeof(PyObject *);

   130 	/* Check for overflow without an actual overflow,

   131 	 *  which can cause compiler to optimise out */

   132 	if (size > PY_SIZE_MAX / sizeof(PyObject *))

   133 		return PyErr_NoMemory();

   134 	if (numfree) {

   135 		numfree--;

   136 		op = free_list[numfree];

   137 		_Py_NewReference((PyObject *)op);

   138 #ifdef SHOW_ALLOC_COUNT

   139 		count_reuse++;

   140 #endif

   141 	} else {

   142 		op = PyObject_GC_New(PyListObject, &PyList_Type);

   143 		if (op == NULL)

   144 			return NULL;

   145 #ifdef SHOW_ALLOC_COUNT

   146 		count_alloc++;

   147 #endif

   148 	}

   149 	if (size <= 0)

   150 		op->ob_item = NULL;

   151 	else {

   152 		op->ob_item = (PyObject **) PyMem_MALLOC(nbytes);

   153 		if (op->ob_item == NULL) {

   154 			Py_DECREF(op);

   155 			return PyErr_NoMemory();

   156 		}

   157 		memset(op->ob_item, 0, nbytes);

   158 	}

   159 	Py_SIZE(op) = size;

   160 	op->allocated = size;

   161 	_PyObject_GC_TRACK(op);

   162 	return (PyObject *) op;

   163 }

   164 

   165 Py_ssize_t

   166 PyList_Size(PyObject *op)

   167 {

   168 	if (!PyList_Check(op)) {

   169 		PyErr_BadInternalCall();

   170 		return -1;

   171 	}

   172 	else

   173 		return Py_SIZE(op);

   174 }

   175 

   176 static PyObject *indexerr = NULL;

   177 

   178 PyObject *

   179 PyList_GetItem(PyObject *op, Py_ssize_t i)

   180 {

   181 	if (!PyList_Check(op)) {

   182 		PyErr_BadInternalCall();

   183 		return NULL;

   184 	}

   185 	if (i < 0 || i >= Py_SIZE(op)) {

   186 		if (indexerr == NULL)

   187 			indexerr = PyString_FromString(

   188 				"list index out of range");

   189 		PyErr_SetObject(PyExc_IndexError, indexerr);

   190 		return NULL;

   191 	}

   192 	return ((PyListObject *)op) -> ob_item[i];

   193 }

   194 

   195 int

   196 PyList_SetItem(register PyObject *op, register Py_ssize_t i,

   197                register PyObject *newitem)

   198 {

   199 	register PyObject *olditem;

   200 	register PyObject **p;

   201 	if (!PyList_Check(op)) {

   202 		Py_XDECREF(newitem);

   203 		PyErr_BadInternalCall();

   204 		return -1;

   205 	}

   206 	if (i < 0 || i >= Py_SIZE(op)) {

   207 		Py_XDECREF(newitem);

   208 		PyErr_SetString(PyExc_IndexError,

   209 				"list assignment index out of range");

   210 		return -1;

   211 	}

   212 	p = ((PyListObject *)op) -> ob_item + i;

   213 	olditem = *p;

   214 	*p = newitem;

   215 	Py_XDECREF(olditem);

   216 	return 0;

   217 }

   218 

   219 static int

   220 ins1(PyListObject *self, Py_ssize_t where, PyObject *v)

   221 {

   222 	Py_ssize_t i, n = Py_SIZE(self);

   223 	PyObject **items;

   224 	if (v == NULL) {

   225 		PyErr_BadInternalCall();

   226 		return -1;

   227 	}

   228 	if (n == PY_SSIZE_T_MAX) {

   229 		PyErr_SetString(PyExc_OverflowError,

   230 			"cannot add more objects to list");

   231 		return -1;

   232 	}

   233 

   234 	if (list_resize(self, n+1) == -1)

   235 		return -1;

   236 

   237 	if (where < 0) {

   238 		where += n;

   239 		if (where < 0)

   240 			where = 0;

   241 	}

   242 	if (where > n)

   243 		where = n;

   244 	items = self->ob_item;

   245 	for (i = n; --i >= where; )

   246 		items[i+1] = items[i];

   247 	Py_INCREF(v);

   248 	items[where] = v;

   249 	return 0;

   250 }

   251 

   252 int

   253 PyList_Insert(PyObject *op, Py_ssize_t where, PyObject *newitem)

   254 {

   255 	if (!PyList_Check(op)) {

   256 		PyErr_BadInternalCall();

   257 		return -1;

   258 	}

   259 	return ins1((PyListObject *)op, where, newitem);

   260 }

   261 

   262 static int

   263 app1(PyListObject *self, PyObject *v)

   264 {

   265 	Py_ssize_t n = PyList_GET_SIZE(self);

   266 

   267 	assert (v != NULL);

   268 	if (n == PY_SSIZE_T_MAX) {

   269 		PyErr_SetString(PyExc_OverflowError,

   270 			"cannot add more objects to list");

   271 		return -1;

   272 	}

   273 

   274 	if (list_resize(self, n+1) == -1)

   275 		return -1;

   276 

   277 	Py_INCREF(v);

   278 	PyList_SET_ITEM(self, n, v);

   279 	return 0;

   280 }

   281 

   282 int

   283 PyList_Append(PyObject *op, PyObject *newitem)

   284 {

   285 	if (PyList_Check(op) && (newitem != NULL))

   286 		return app1((PyListObject *)op, newitem);

   287 	PyErr_BadInternalCall();

   288 	return -1;

   289 }

   290 

   291 /* Methods */

   292 

   293 static void

   294 list_dealloc(PyListObject *op)

   295 {

   296 	Py_ssize_t i;

   297 	PyObject_GC_UnTrack(op);

   298 	Py_TRASHCAN_SAFE_BEGIN(op)

   299 	if (op->ob_item != NULL) {

   300 		/* Do it backwards, for Christian Tismer.

   301 		   There's a simple test case where somehow this reduces

   302 		   thrashing when a *very* large list is created and

   303 		   immediately deleted. */

   304 		i = Py_SIZE(op);

   305 		while (--i >= 0) {

   306 			Py_XDECREF(op->ob_item[i]);

   307 		}

   308 		PyMem_FREE(op->ob_item);

   309 	}

   310 	if (numfree < PyList_MAXFREELIST && PyList_CheckExact(op))

   311 		free_list[numfree++] = op;

   312 	else

   313 		Py_TYPE(op)->tp_free((PyObject *)op);

   314 	Py_TRASHCAN_SAFE_END(op)

   315 }

   316 

   317 static int

   318 list_print(PyListObject *op, FILE *fp, int flags)

   319 {

   320 	int rc;

   321 	Py_ssize_t i;

   322 

   323 	rc = Py_ReprEnter((PyObject*)op);

   324 	if (rc != 0) {

   325 		if (rc < 0)

   326 			return rc;

   327 		Py_BEGIN_ALLOW_THREADS

   328 		fprintf(fp, "[...]");

   329 		Py_END_ALLOW_THREADS

   330 		return 0;

   331 	}

   332 	Py_BEGIN_ALLOW_THREADS

   333 	fprintf(fp, "[");

   334 	Py_END_ALLOW_THREADS

   335 	for (i = 0; i < Py_SIZE(op); i++) {

   336 		if (i > 0) {

   337 			Py_BEGIN_ALLOW_THREADS

   338 			fprintf(fp, ", ");

   339 			Py_END_ALLOW_THREADS

   340 		}

   341 		if (PyObject_Print(op->ob_item[i], fp, 0) != 0) {

   342 			Py_ReprLeave((PyObject *)op);

   343 			return -1;

   344 		}

   345 	}

   346 	Py_BEGIN_ALLOW_THREADS

   347 	fprintf(fp, "]");

   348 	Py_END_ALLOW_THREADS

   349 	Py_ReprLeave((PyObject *)op);

   350 	return 0;

   351 }

   352 

   353 static PyObject *

   354 list_repr(PyListObject *v)

   355 {

   356 	Py_ssize_t i;

   357 	PyObject *s, *temp;

   358 	PyObject *pieces = NULL, *result = NULL;

   359 

   360 	i = Py_ReprEnter((PyObject*)v);

   361 	if (i != 0) {

   362 		return i > 0 ? PyString_FromString("[...]") : NULL;

   363 	}

   364 

   365 	if (Py_SIZE(v) == 0) {

   366 		result = PyString_FromString("[]");

   367 		goto Done;

   368 	}

   369 

   370 	pieces = PyList_New(0);

   371 	if (pieces == NULL)

   372 		goto Done;

   373 

   374 	/* Do repr() on each element.  Note that this may mutate the list,

   375 	   so must refetch the list size on each iteration. */

   376 	for (i = 0; i < Py_SIZE(v); ++i) {

   377 		int status;

   378 		if (Py_EnterRecursiveCall(" while getting the repr of a list"))

   379 			goto Done;

   380 		s = PyObject_Repr(v->ob_item[i]);

   381 		Py_LeaveRecursiveCall();

   382 		if (s == NULL)

   383 			goto Done;

   384 		status = PyList_Append(pieces, s);

   385 		Py_DECREF(s);  /* append created a new ref */

   386 		if (status < 0)

   387 			goto Done;

   388 	}

   389 

   390 	/* Add "[]" decorations to the first and last items. */

   391 	assert(PyList_GET_SIZE(pieces) > 0);

   392 	s = PyString_FromString("[");

   393 	if (s == NULL)

   394 		goto Done;

   395 	temp = PyList_GET_ITEM(pieces, 0);

   396 	PyString_ConcatAndDel(&s, temp);

   397 	PyList_SET_ITEM(pieces, 0, s);

   398 	if (s == NULL)

   399 		goto Done;

   400 

   401 	s = PyString_FromString("]");

   402 	if (s == NULL)

   403 		goto Done;

   404 	temp = PyList_GET_ITEM(pieces, PyList_GET_SIZE(pieces) - 1);

   405 	PyString_ConcatAndDel(&temp, s);

   406 	PyList_SET_ITEM(pieces, PyList_GET_SIZE(pieces) - 1, temp);

   407 	if (temp == NULL)

   408 		goto Done;

   409 

   410 	/* Paste them all together with ", " between. */

   411 	s = PyString_FromString(", ");

   412 	if (s == NULL)

   413 		goto Done;

   414 	result = _PyString_Join(s, pieces);

   415 	Py_DECREF(s);

   416 

   417 Done:

   418 	Py_XDECREF(pieces);

   419 	Py_ReprLeave((PyObject *)v);

   420 	return result;

   421 }

   422 

   423 static Py_ssize_t

   424 list_length(PyListObject *a)

   425 {

   426 	return Py_SIZE(a);

   427 }

   428 

   429 static int

   430 list_contains(PyListObject *a, PyObject *el)

   431 {

   432 	Py_ssize_t i;

   433 	int cmp;

   434 

   435 	for (i = 0, cmp = 0 ; cmp == 0 && i < Py_SIZE(a); ++i)

   436 		cmp = PyObject_RichCompareBool(el, PyList_GET_ITEM(a, i),

   437 						   Py_EQ);

   438 	return cmp;

   439 }

   440 

   441 static PyObject *

   442 list_item(PyListObject *a, Py_ssize_t i)

   443 {

   444 	if (i < 0 || i >= Py_SIZE(a)) {

   445 		if (indexerr == NULL)

   446 			indexerr = PyString_FromString(

   447 				"list index out of range");

   448 		PyErr_SetObject(PyExc_IndexError, indexerr);

   449 		return NULL;

   450 	}

   451 	Py_INCREF(a->ob_item[i]);

   452 	return a->ob_item[i];

   453 }

   454 

   455 static PyObject *

   456 list_slice(PyListObject *a, Py_ssize_t ilow, Py_ssize_t ihigh)

   457 {

   458 	PyListObject *np;

   459 	PyObject **src, **dest;

   460 	Py_ssize_t i, len;

   461 	if (ilow < 0)

   462 		ilow = 0;

   463 	else if (ilow > Py_SIZE(a))

   464 		ilow = Py_SIZE(a);

   465 	if (ihigh < ilow)

   466 		ihigh = ilow;

   467 	else if (ihigh > Py_SIZE(a))

   468 		ihigh = Py_SIZE(a);

   469 	len = ihigh - ilow;

   470 	np = (PyListObject *) PyList_New(len);

   471 	if (np == NULL)

   472 		return NULL;

   473 

   474 	src = a->ob_item + ilow;

   475 	dest = np->ob_item;

   476 	for (i = 0; i < len; i++) {

   477 		PyObject *v = src[i];

   478 		Py_INCREF(v);

   479 		dest[i] = v;

   480 	}

   481 	return (PyObject *)np;

   482 }

   483 

   484 PyObject *

   485 PyList_GetSlice(PyObject *a, Py_ssize_t ilow, Py_ssize_t ihigh)

   486 {

   487 	if (!PyList_Check(a)) {

   488 		PyErr_BadInternalCall();

   489 		return NULL;

   490 	}

   491 	return list_slice((PyListObject *)a, ilow, ihigh);

   492 }

   493 

   494 static PyObject *

   495 list_concat(PyListObject *a, PyObject *bb)

   496 {

   497 	Py_ssize_t size;

   498 	Py_ssize_t i;

   499 	PyObject **src, **dest;

   500 	PyListObject *np;

   501 	if (!PyList_Check(bb)) {

   502 		PyErr_Format(PyExc_TypeError,

   503 			  "can only concatenate list (not \"%.200s\") to list",

   504 			  bb->ob_type->tp_name);

   505 		return NULL;

   506 	}

   507 #define b ((PyListObject *)bb)

   508 	size = Py_SIZE(a) + Py_SIZE(b);

   509 	if (size < 0)

   510 		return PyErr_NoMemory();

   511 	np = (PyListObject *) PyList_New(size);

   512 	if (np == NULL) {

   513 		return NULL;

   514 	}

   515 	src = a->ob_item;

   516 	dest = np->ob_item;

   517 	for (i = 0; i < Py_SIZE(a); i++) {

   518 		PyObject *v = src[i];

   519 		Py_INCREF(v);

   520 		dest[i] = v;

   521 	}

   522 	src = b->ob_item;

   523 	dest = np->ob_item + Py_SIZE(a);

   524 	for (i = 0; i < Py_SIZE(b); i++) {

   525 		PyObject *v = src[i];

   526 		Py_INCREF(v);

   527 		dest[i] = v;

   528 	}

   529 	return (PyObject *)np;

   530 #undef b

   531 }

   532 

   533 static PyObject *

   534 list_repeat(PyListObject *a, Py_ssize_t n)

   535 {

   536 	Py_ssize_t i, j;

   537 	Py_ssize_t size;

   538 	PyListObject *np;

   539 	PyObject **p, **items;

   540 	PyObject *elem;

   541 	if (n < 0)

   542 		n = 0;

   543 	size = Py_SIZE(a) * n;

   544 	if (n && size/n != Py_SIZE(a))

   545 		return PyErr_NoMemory();

   546 	if (size == 0)

   547 		return PyList_New(0);

   548 	np = (PyListObject *) PyList_New(size);

   549 	if (np == NULL)

   550 		return NULL;

   551 

   552 	items = np->ob_item;

   553 	if (Py_SIZE(a) == 1) {

   554 		elem = a->ob_item[0];

   555 		for (i = 0; i < n; i++) {

   556 			items[i] = elem;

   557 			Py_INCREF(elem);

   558 		}

   559 		return (PyObject *) np;

   560 	}

   561 	p = np->ob_item;

   562 	items = a->ob_item;

   563 	for (i = 0; i < n; i++) {

   564 		for (j = 0; j < Py_SIZE(a); j++) {

   565 			*p = items[j];

   566 			Py_INCREF(*p);

   567 			p++;

   568 		}

   569 	}

   570 	return (PyObject *) np;

   571 }

   572 

   573 static int

   574 list_clear(PyListObject *a)

   575 {

   576 	Py_ssize_t i;

   577 	PyObject **item = a->ob_item;

   578 	if (item != NULL) {

   579 		/* Because XDECREF can recursively invoke operations on

   580 		   this list, we make it empty first. */

   581 		i = Py_SIZE(a);

   582 		Py_SIZE(a) = 0;

   583 		a->ob_item = NULL;

   584 		a->allocated = 0;

   585 		while (--i >= 0) {

   586 			Py_XDECREF(item[i]);

   587 		}

   588 		PyMem_FREE(item);

   589 	}

   590 	/* Never fails; the return value can be ignored.

   591 	   Note that there is no guarantee that the list is actually empty

   592 	   at this point, because XDECREF may have populated it again! */

   593 	return 0;

   594 }

   595 

   596 /* a[ilow:ihigh] = v if v != NULL.

   597  * del a[ilow:ihigh] if v == NULL.

   598  *

   599  * Special speed gimmick:  when v is NULL and ihigh - ilow <= 8, it's

   600  * guaranteed the call cannot fail.

   601  */

   602 static int

   603 list_ass_slice(PyListObject *a, Py_ssize_t ilow, Py_ssize_t ihigh, PyObject *v)

   604 {

   605 	/* Because [X]DECREF can recursively invoke list operations on

   606 	   this list, we must postpone all [X]DECREF activity until

   607 	   after the list is back in its canonical shape.  Therefore

   608 	   we must allocate an additional array, 'recycle', into which

   609 	   we temporarily copy the items that are deleted from the

   610 	   list. :-( */

   611 	PyObject *recycle_on_stack[8];

   612 	PyObject **recycle = recycle_on_stack; /* will allocate more if needed */

   613 	PyObject **item;

   614 	PyObject **vitem = NULL;

   615 	PyObject *v_as_SF = NULL; /* PySequence_Fast(v) */

   616 	Py_ssize_t n; /* # of elements in replacement list */

   617 	Py_ssize_t norig; /* # of elements in list getting replaced */

   618 	Py_ssize_t d; /* Change in size */

   619 	Py_ssize_t k;

   620 	size_t s;

   621 	int result = -1;	/* guilty until proved innocent */

   622 #define b ((PyListObject *)v)

   623 	if (v == NULL)

   624 		n = 0;

   625 	else {

   626 		if (a == b) {

   627 			/* Special case "a[i:j] = a" -- copy b first */

   628 			v = list_slice(b, 0, Py_SIZE(b));

   629 			if (v == NULL)

   630 				return result;

   631 			result = list_ass_slice(a, ilow, ihigh, v);

   632 			Py_DECREF(v);

   633 			return result;

   634 		}

   635 		v_as_SF = PySequence_Fast(v, "can only assign an iterable");

   636 		if(v_as_SF == NULL)

   637 			goto Error;

   638 		n = PySequence_Fast_GET_SIZE(v_as_SF);

   639 		vitem = PySequence_Fast_ITEMS(v_as_SF);

   640 	}

   641 	if (ilow < 0)

   642 		ilow = 0;

   643 	else if (ilow > Py_SIZE(a))

   644 		ilow = Py_SIZE(a);

   645 

   646 	if (ihigh < ilow)

   647 		ihigh = ilow;

   648 	else if (ihigh > Py_SIZE(a))

   649 		ihigh = Py_SIZE(a);

   650 

   651 	norig = ihigh - ilow;

   652 	assert(norig >= 0);

   653 	d = n - norig;

   654 	if (Py_SIZE(a) + d == 0) {

   655 		Py_XDECREF(v_as_SF);

   656 		return list_clear(a);

   657 	}

   658 	item = a->ob_item;

   659 	/* recycle the items that we are about to remove */

   660 	s = norig * sizeof(PyObject *);

   661 	if (s > sizeof(recycle_on_stack)) {

   662 		recycle = (PyObject **)PyMem_MALLOC(s);

   663 		if (recycle == NULL) {

   664 			PyErr_NoMemory();

   665 			goto Error;

   666 		}

   667 	}

   668 	memcpy(recycle, &item[ilow], s);

   669 

   670 	if (d < 0) { /* Delete -d items */

   671 		memmove(&item[ihigh+d], &item[ihigh],

   672 			(Py_SIZE(a) - ihigh)*sizeof(PyObject *));

   673 		list_resize(a, Py_SIZE(a) + d);

   674 		item = a->ob_item;

   675 	}

   676 	else if (d > 0) { /* Insert d items */

   677 		k = Py_SIZE(a);

   678 		if (list_resize(a, k+d) < 0)

   679 			goto Error;

   680 		item = a->ob_item;

   681 		memmove(&item[ihigh+d], &item[ihigh],

   682 			(k - ihigh)*sizeof(PyObject *));

   683 	}

   684 	for (k = 0; k < n; k++, ilow++) {

   685 		PyObject *w = vitem[k];

   686 		Py_XINCREF(w);

   687 		item[ilow] = w;

   688 	}

   689 	for (k = norig - 1; k >= 0; --k)

   690 		Py_XDECREF(recycle[k]);

   691 	result = 0;

   692  Error:

   693 	if (recycle != recycle_on_stack)

   694 		PyMem_FREE(recycle);

   695 	Py_XDECREF(v_as_SF);

   696 	return result;

   697 #undef b

   698 }

   699 

   700 int

   701 PyList_SetSlice(PyObject *a, Py_ssize_t ilow, Py_ssize_t ihigh, PyObject *v)

   702 {

   703 	if (!PyList_Check(a)) {

   704 		PyErr_BadInternalCall();

   705 		return -1;

   706 	}

   707 	return list_ass_slice((PyListObject *)a, ilow, ihigh, v);

   708 }

   709 

   710 static PyObject *

   711 list_inplace_repeat(PyListObject *self, Py_ssize_t n)

   712 {

   713 	PyObject **items;

   714 	Py_ssize_t size, i, j, p;

   715 

   716 

   717 	size = PyList_GET_SIZE(self);

   718 	if (size == 0 || n == 1) {

   719 		Py_INCREF(self);

   720 		return (PyObject *)self;

   721 	}

   722 

   723 	if (n < 1) {

   724 		(void)list_clear(self);

   725 		Py_INCREF(self);

   726 		return (PyObject *)self;

   727 	}

   728 

   729 	if (size > PY_SSIZE_T_MAX / n) {

   730 		return PyErr_NoMemory();

   731 	}

   732 

   733 	if (list_resize(self, size*n) == -1)

   734 		return NULL;

   735 

   736 	p = size;

   737 	items = self->ob_item;

   738 	for (i = 1; i < n; i++) { /* Start counting at 1, not 0 */

   739 		for (j = 0; j < size; j++) {

   740 			PyObject *o = items[j];

   741 			Py_INCREF(o);

   742 			items[p++] = o;

   743 		}

   744 	}

   745 	Py_INCREF(self);

   746 	return (PyObject *)self;

   747 }

   748 

   749 static int

   750 list_ass_item(PyListObject *a, Py_ssize_t i, PyObject *v)

   751 {

   752 	PyObject *old_value;

   753 	if (i < 0 || i >= Py_SIZE(a)) {

   754 		PyErr_SetString(PyExc_IndexError,

   755 				"list assignment index out of range");

   756 		return -1;

   757 	}

   758 	if (v == NULL)

   759 		return list_ass_slice(a, i, i+1, v);

   760 	Py_INCREF(v);

   761 	old_value = a->ob_item[i];

   762 	a->ob_item[i] = v;

   763 	Py_DECREF(old_value);

   764 	return 0;

   765 }

   766 

   767 static PyObject *

   768 listinsert(PyListObject *self, PyObject *args)

   769 {

   770 	Py_ssize_t i;

   771 	PyObject *v;

   772 	if (!PyArg_ParseTuple(args, "nO:insert", &i, &v))

   773 		return NULL;

   774 	if (ins1(self, i, v) == 0)

   775 		Py_RETURN_NONE;

   776 	return NULL;

   777 }

   778 

   779 static PyObject *

   780 listappend(PyListObject *self, PyObject *v)

   781 {

   782 	if (app1(self, v) == 0)

   783 		Py_RETURN_NONE;

   784 	return NULL;

   785 }

   786 

   787 static PyObject *

   788 listextend(PyListObject *self, PyObject *b)

   789 {

   790 	PyObject *it;      /* iter(v) */

   791 	Py_ssize_t m;		   /* size of self */

   792 	Py_ssize_t n;		   /* guess for size of b */

   793 	Py_ssize_t mn;		   /* m + n */

   794 	Py_ssize_t i;

   795 	PyObject *(*iternext)(PyObject *);

   796 

   797 	/* Special cases:

   798 	   1) lists and tuples which can use PySequence_Fast ops

   799 	   2) extending self to self requires making a copy first

   800 	*/

   801 	if (PyList_CheckExact(b) || PyTuple_CheckExact(b) || (PyObject *)self == b) {

   802 		PyObject **src, **dest;

   803 		b = PySequence_Fast(b, "argument must be iterable");

   804 		if (!b)

   805 			return NULL;

   806 		n = PySequence_Fast_GET_SIZE(b);

   807 		if (n == 0) {

   808 			/* short circuit when b is empty */

   809 			Py_DECREF(b);

   810 			Py_RETURN_NONE;

   811 		}

   812 		m = Py_SIZE(self);

   813 		if (list_resize(self, m + n) == -1) {

   814 			Py_DECREF(b);

   815 			return NULL;

   816 		}

   817 		/* note that we may still have self == b here for the

   818 		 * situation a.extend(a), but the following code works

   819 		 * in that case too.  Just make sure to resize self

   820 		 * before calling PySequence_Fast_ITEMS.

   821 		 */

   822 		/* populate the end of self with b's items */

   823 		src = PySequence_Fast_ITEMS(b);

   824 		dest = self->ob_item + m;

   825 		for (i = 0; i < n; i++) {

   826 			PyObject *o = src[i];

   827 			Py_INCREF(o);

   828 			dest[i] = o;

   829 		}

   830 		Py_DECREF(b);

   831 		Py_RETURN_NONE;

   832 	}

   833 

   834 	it = PyObject_GetIter(b);

   835 	if (it == NULL)

   836 		return NULL;

   837 	iternext = *it->ob_type->tp_iternext;

   838 

   839 	/* Guess a result list size. */

   840 	n = _PyObject_LengthHint(b, 8);

   841 	m = Py_SIZE(self);

   842 	mn = m + n;

   843 	if (mn >= m) {

   844 		/* Make room. */

   845 		if (list_resize(self, mn) == -1)

   846 			goto error;

   847 		/* Make the list sane again. */

   848 		Py_SIZE(self) = m;

   849 	}

   850 	/* Else m + n overflowed; on the chance that n lied, and there really

   851 	 * is enough room, ignore it.  If n was telling the truth, we'll

   852 	 * eventually run out of memory during the loop.

   853 	 */

   854 

   855 	/* Run iterator to exhaustion. */

   856 	for (;;) {

   857 		PyObject *item = iternext(it);

   858 		if (item == NULL) {

   859 			if (PyErr_Occurred()) {

   860 				if (PyErr_ExceptionMatches(PyExc_StopIteration))

   861 					PyErr_Clear();

   862 				else

   863 					goto error;

   864 			}

   865 			break;

   866 		}

   867 		if (Py_SIZE(self) < self->allocated) {

   868 			/* steals ref */

   869 			PyList_SET_ITEM(self, Py_SIZE(self), item);

   870 			++Py_SIZE(self);

   871 		}

   872 		else {

   873 			int status = app1(self, item);

   874 			Py_DECREF(item);  /* append creates a new ref */

   875 			if (status < 0)

   876 				goto error;

   877 		}

   878 	}

   879 

   880 	/* Cut back result list if initial guess was too large. */

   881 	if (Py_SIZE(self) < self->allocated)

   882 		list_resize(self, Py_SIZE(self));  /* shrinking can't fail */

   883 

   884 	Py_DECREF(it);

   885 	Py_RETURN_NONE;

   886 

   887   error:

   888 	Py_DECREF(it);

   889 	return NULL;

   890 }

   891 

   892 PyObject *

   893 _PyList_Extend(PyListObject *self, PyObject *b)

   894 {

   895 	return listextend(self, b);

   896 }

   897 

   898 static PyObject *

   899 list_inplace_concat(PyListObject *self, PyObject *other)

   900 {

   901 	PyObject *result;

   902 

   903 	result = listextend(self, other);

   904 	if (result == NULL)

   905 		return result;

   906 	Py_DECREF(result);

   907 	Py_INCREF(self);

   908 	return (PyObject *)self;

   909 }

   910 

   911 static PyObject *

   912 listpop(PyListObject *self, PyObject *args)

   913 {

   914 	Py_ssize_t i = -1;

   915 	PyObject *v;

   916 	int status;

   917 

   918 	if (!PyArg_ParseTuple(args, "|n:pop", &i))

   919 		return NULL;

   920 

   921 	if (Py_SIZE(self) == 0) {

   922 		/* Special-case most common failure cause */

   923 		PyErr_SetString(PyExc_IndexError, "pop from empty list");

   924 		return NULL;

   925 	}

   926 	if (i < 0)

   927 		i += Py_SIZE(self);

   928 	if (i < 0 || i >= Py_SIZE(self)) {

   929 		PyErr_SetString(PyExc_IndexError, "pop index out of range");

   930 		return NULL;

   931 	}

   932 	v = self->ob_item[i];

   933 	if (i == Py_SIZE(self) - 1) {

   934 		status = list_resize(self, Py_SIZE(self) - 1);

   935 		assert(status >= 0);

   936 		return v; /* and v now owns the reference the list had */

   937 	}

   938 	Py_INCREF(v);

   939 	status = list_ass_slice(self, i, i+1, (PyObject *)NULL);

   940 	assert(status >= 0);

   941 	/* Use status, so that in a release build compilers don't

   942 	 * complain about the unused name.

   943 	 */

   944 	(void) status;

   945 

   946 	return v;

   947 }

   948 

   949 /* Reverse a slice of a list in place, from lo up to (exclusive) hi. */

   950 static void

   951 reverse_slice(PyObject **lo, PyObject **hi)

   952 {

   953 	assert(lo && hi);

   954 

   955 	--hi;

   956 	while (lo < hi) {

   957 		PyObject *t = *lo;

   958 		*lo = *hi;

   959 		*hi = t;

   960 		++lo;

   961 		--hi;

   962 	}

   963 }

   964 

   965 /* Lots of code for an adaptive, stable, natural mergesort.  There are many

   966  * pieces to this algorithm; read listsort.txt for overviews and details.

   967  */

   968 

   969 /* Comparison function.  Takes care of calling a user-supplied

   970  * comparison function (any callable Python object), which must not be

   971  * NULL (use the ISLT macro if you don't know, or call PyObject_RichCompareBool

   972  * with Py_LT if you know it's NULL).

   973  * Returns -1 on error, 1 if x < y, 0 if x >= y.

   974  */

   975 static int

   976 islt(PyObject *x, PyObject *y, PyObject *compare)

   977 {

   978 	PyObject *res;

   979 	PyObject *args;

   980 	Py_ssize_t i;

   981 

   982 	assert(compare != NULL);

   983 	/* Call the user's comparison function and translate the 3-way

   984 	 * result into true or false (or error).

   985 	 */

   986 	args = PyTuple_New(2);

   987 	if (args == NULL)

   988 		return -1;

   989 	Py_INCREF(x);

   990 	Py_INCREF(y);

   991 	PyTuple_SET_ITEM(args, 0, x);

   992 	PyTuple_SET_ITEM(args, 1, y);

   993 	res = PyObject_Call(compare, args, NULL);

   994 	Py_DECREF(args);

   995 	if (res == NULL)

   996 		return -1;

   997 	if (!PyInt_Check(res)) {

   998 		PyErr_Format(PyExc_TypeError,

   999 			     "comparison function must return int, not %.200s",

  1000 			     res->ob_type->tp_name);

  1001 		Py_DECREF(res);

  1002 		return -1;

  1003 	}

  1004 	i = PyInt_AsLong(res);

  1005 	Py_DECREF(res);

  1006 	return i < 0;

  1007 }

  1008 

  1009 /* If COMPARE is NULL, calls PyObject_RichCompareBool with Py_LT, else calls

  1010  * islt.  This avoids a layer of function call in the usual case, and

  1011  * sorting does many comparisons.

  1012  * Returns -1 on error, 1 if x < y, 0 if x >= y.

  1013  */

  1014 #define ISLT(X, Y, COMPARE) ((COMPARE) == NULL ?			\

  1015 			     PyObject_RichCompareBool(X, Y, Py_LT) :	\

  1016 			     islt(X, Y, COMPARE))

  1017 

  1018 /* Compare X to Y via "<".  Goto "fail" if the comparison raises an

  1019    error.  Else "k" is set to true iff X<Y, and an "if (k)" block is

  1020    started.  It makes more sense in context <wink>.  X and Y are PyObject*s.

  1021 */

  1022 #define IFLT(X, Y) if ((k = ISLT(X, Y, compare)) < 0) goto fail;  \

  1023 		   if (k)

  1024 

  1025 /* binarysort is the best method for sorting small arrays: it does

  1026    few compares, but can do data movement quadratic in the number of

  1027    elements.

  1028    [lo, hi) is a contiguous slice of a list, and is sorted via

  1029    binary insertion.  This sort is stable.

  1030    On entry, must have lo <= start <= hi, and that [lo, start) is already

  1031    sorted (pass start == lo if you don't know!).

  1032    If islt() complains return -1, else 0.

  1033    Even in case of error, the output slice will be some permutation of

  1034    the input (nothing is lost or duplicated).

  1035 */

  1036 static int

  1037 binarysort(PyObject **lo, PyObject **hi, PyObject **start, PyObject *compare)

  1038      /* compare -- comparison function object, or NULL for default */

  1039 {

  1040 	register Py_ssize_t k;

  1041 	register PyObject **l, **p, **r;

  1042 	register PyObject *pivot;

  1043 

  1044 	assert(lo <= start && start <= hi);

  1045 	/* assert [lo, start) is sorted */

  1046 	if (lo == start)

  1047 		++start;

  1048 	for (; start < hi; ++start) {

  1049 		/* set l to where *start belongs */

  1050 		l = lo;

  1051 		r = start;

  1052 		pivot = *r;

  1053 		/* Invariants:

  1054 		 * pivot >= all in [lo, l).

  1055 		 * pivot  < all in [r, start).

  1056 		 * The second is vacuously true at the start.

  1057 		 */

  1058 		assert(l < r);

  1059 		do {

  1060 			p = l + ((r - l) >> 1);

  1061 			IFLT(pivot, *p)

  1062 				r = p;

  1063 			else

  1064 				l = p+1;

  1065 		} while (l < r);

  1066 		assert(l == r);

  1067 		/* The invariants still hold, so pivot >= all in [lo, l) and

  1068 		   pivot < all in [l, start), so pivot belongs at l.  Note

  1069 		   that if there are elements equal to pivot, l points to the

  1070 		   first slot after them -- that's why this sort is stable.

  1071 		   Slide over to make room.

  1072 		   Caution: using memmove is much slower under MSVC 5;

  1073 		   we're not usually moving many slots. */

  1074 		for (p = start; p > l; --p)

  1075 			*p = *(p-1);

  1076 		*l = pivot;

  1077 	}

  1078 	return 0;

  1079 

  1080  fail:

  1081 	return -1;

  1082 }

  1083 

  1084 /*

  1085 Return the length of the run beginning at lo, in the slice [lo, hi).  lo < hi

  1086 is required on entry.  "A run" is the longest ascending sequence, with

  1087 

  1088     lo[0] <= lo[1] <= lo[2] <= ...

  1089 

  1090 or the longest descending sequence, with

  1091 

  1092     lo[0] > lo[1] > lo[2] > ...

  1093 

  1094 Boolean *descending is set to 0 in the former case, or to 1 in the latter.

  1095 For its intended use in a stable mergesort, the strictness of the defn of

  1096 "descending" is needed so that the caller can safely reverse a descending

  1097 sequence without violating stability (strict > ensures there are no equal

  1098 elements to get out of order).

  1099 

  1100 Returns -1 in case of error.

  1101 */

  1102 static Py_ssize_t

  1103 count_run(PyObject **lo, PyObject **hi, PyObject *compare, int *descending)

  1104 {

  1105 	Py_ssize_t k;

  1106 	Py_ssize_t n;

  1107 

  1108 	assert(lo < hi);

  1109 	*descending = 0;

  1110 	++lo;

  1111 	if (lo == hi)

  1112 		return 1;

  1113 

  1114 	n = 2;

  1115 	IFLT(*lo, *(lo-1)) {

  1116 		*descending = 1;

  1117 		for (lo = lo+1; lo < hi; ++lo, ++n) {

  1118 			IFLT(*lo, *(lo-1))

  1119 				;

  1120 			else

  1121 				break;

  1122 		}

  1123 	}

  1124 	else {

  1125 		for (lo = lo+1; lo < hi; ++lo, ++n) {

  1126 			IFLT(*lo, *(lo-1))

  1127 				break;

  1128 		}

  1129 	}

  1130 

  1131 	return n;

  1132 fail:

  1133 	return -1;

  1134 }

  1135