/* List object implementation */

#include "Python.h"

#include "pycore_abstract.h" // _PyIndex_Check()

#include "pycore_ceval.h" // _PyEval_GetBuiltin()

#include "pycore_critical_section.h" // _Py_CRITICAL_SECTION_ASSERT_OBJECT_LOCKED()

#include "pycore_dict.h" // _PyDictViewObject

#include "pycore_freelist.h" // _Py_FREELIST_FREE(), _Py_FREELIST_POP()

#include "pycore_interp.h" // PyInterpreterState.list

#include "pycore_list.h" // struct _Py_list_freelist, _PyListIterObject

#include "pycore_long.h" // _PyLong_DigitCount

#include "pycore_modsupport.h" // _PyArg_NoKwnames()

#include "pycore_object.h" // _PyObject_GC_TRACK(), _PyDebugAllocatorStats()

#include "pycore_pyatomic_ft_wrappers.h"

#include "pycore_setobject.h" // _PySet_NextEntry()

#include "pycore_stackref.h" // _Py_TryIncrefCompareStackRef()

#include "pycore_tuple.h" // _PyTuple_FromArraySteal()

#include "pycore_typeobject.h" // _Py_TYPE_VERSION_LIST

#include <stddef.h>

/*[clinic input]

class list "PyListObject *" "&PyList_Type"

[clinic start generated code]*/

/*[clinic end generated code: output=da39a3ee5e6b4b0d input=f9b222678f9f71e0]*/

#include "clinic/listobject.c.h"

_Py_DECLARE_STR(list_err, "list index out of range");

#ifdef Py_GIL_DISABLED

typedef struct {

Py_ssize_t allocated;

PyObject *ob_item[];

} _PyListArray;

static _PyListArray *

list_allocate_array(size_t capacity)

{

if (capacity > PY_SSIZE_T_MAX/sizeof(PyObject*) - 1) {

return NULL;

}

_PyListArray *array = PyMem_Malloc(sizeof(_PyListArray) + capacity * sizeof(PyObject *));

if (array == NULL) {

return NULL;

}

array->allocated = capacity;

return array;

}

static Py_ssize_t

list_capacity(PyObject **items)

{

_PyListArray *array = _Py_CONTAINER_OF(items, _PyListArray, ob_item);

return array->allocated;

}

#endif

static void

free_list_items(PyObject** items, bool use_qsbr)

{

#ifdef Py_GIL_DISABLED

_PyListArray *array = _Py_CONTAINER_OF(items, _PyListArray, ob_item);

if (use_qsbr) {

size_t size = sizeof(_PyListArray) + array->allocated * sizeof(PyObject *);

_PyMem_FreeDelayed(array, size);

}

else {

PyMem_Free(array);

}

#else

PyMem_Free(items);

#endif

}

static void

ensure_shared_on_resize(PyListObject *self)

{

#ifdef Py_GIL_DISABLED

// We can't use _Py_CRITICAL_SECTION_ASSERT_OBJECT_LOCKED here because

// the `CALL_LIST_APPEND` bytecode handler may lock the list without

// a critical section.

assert(Py_REFCNT(self) == 1 || PyMutex_IsLocked(&_PyObject_CAST(self)->ob_mutex));

// Ensure that the list array is freed using QSBR if we are not the

// owning thread.

if (!_Py_IsOwnedByCurrentThread((PyObject *)self) &&

!_PyObject_GC_IS_SHARED(self))

{

_PyObject_GC_SET_SHARED(self);

}

#endif

}

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

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

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

* responsibility to overwrite them with sane values.

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

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

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

* than ob_size on entry.

*/

static int

list_resize(PyListObject *self, Py_ssize_t newsize)

{

size_t new_allocated, target_bytes;

Py_ssize_t allocated = self->allocated;

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

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

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

*/

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

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

Py_SET_SIZE(self, newsize);

return 0;

}

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

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

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

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

* system realloc().

* Add padding to make the allocated size multiple of 4.

* The growth pattern is: 0, 4, 8, 16, 24, 32, 40, 52, 64, 76, ...

* Note: new_allocated won't overflow because the largest possible value

* is PY_SSIZE_T_MAX * (9 / 8) + 6 which always fits in a size_t.

*/

new_allocated = ((size_t)newsize + (newsize >> 3) + 6) & ~(size_t)3;

/* Do not overallocate if the new size is closer to overallocated size

* than to the old size.

*/

if (newsize - Py_SIZE(self) > (Py_ssize_t)(new_allocated - newsize))

new_allocated = ((size_t)newsize + 3) & ~(size_t)3;

if (newsize == 0)

new_allocated = 0;

ensure_shared_on_resize(self);

#ifdef Py_GIL_DISABLED

_PyListArray *array = list_allocate_array(new_allocated);

if (array == NULL) {

if (newsize < allocated) {

// Never fail when shrinking allocations

Py_SET_SIZE(self, newsize);

return 0;

}

PyErr_NoMemory();

return -1;

}

PyObject **old_items = self->ob_item;

if (self->ob_item) {

if (new_allocated < (size_t)allocated) {

target_bytes = new_allocated * sizeof(PyObject*);

}

else {

target_bytes = allocated * sizeof(PyObject*);

}

memcpy(array->ob_item, self->ob_item, target_bytes);

}

if (new_allocated > (size_t)allocated) {

memset(array->ob_item + allocated, 0, sizeof(PyObject *) * (new_allocated - allocated));

}

_Py_atomic_store_ptr_release(&self->ob_item, &array->ob_item);

self->allocated = new_allocated;

Py_SET_SIZE(self, newsize);

if (old_items != NULL) {

free_list_items(old_items, _PyObject_GC_IS_SHARED(self));

}

#else

PyObject **items;

if (new_allocated <= (size_t)PY_SSIZE_T_MAX / sizeof(PyObject *)) {

target_bytes = new_allocated * sizeof(PyObject *);

items = (PyObject **)PyMem_Realloc(self->ob_item, target_bytes);

}

else {

// integer overflow

items = NULL;

}

if (items == NULL) {

if (newsize < allocated) {

// Never fail when shrinking allocations

Py_SET_SIZE(self, newsize);

return 0;

}

PyErr_NoMemory();

return -1;

}

self->ob_item = items;

Py_SET_SIZE(self, newsize);

self->allocated = new_allocated;

#endif

return 0;

}

static int

list_preallocate_exact(PyListObject *self, Py_ssize_t size)

{

PyObject **items;

assert(self->ob_item == NULL);

assert(size > 0);

/* Since the Python memory allocator has granularity of 16 bytes on 64-bit

* platforms (8 on 32-bit), there is no benefit of allocating space for

* the odd number of items, and there is no drawback of rounding the

* allocated size up to the nearest even number.

*/

size = (size + 1) & ~(size_t)1;

#ifdef Py_GIL_DISABLED

_PyListArray *array = list_allocate_array(size);

if (array == NULL) {

PyErr_NoMemory();

return -1;

}

items = array->ob_item;

memset(items, 0, size * sizeof(PyObject *));

#else

items = PyMem_New(PyObject*, size);

if (items == NULL) {

PyErr_NoMemory();

return -1;

}

#endif

FT_ATOMIC_STORE_PTR_RELEASE(self->ob_item, items);

self->allocated = size;

return 0;

}

/* Print summary info about the state of the optimized allocator */

void

_PyList_DebugMallocStats(FILE *out)

{

_PyDebugAllocatorStats(out,

"free PyListObject",

_Py_FREELIST_SIZE(lists),

sizeof(PyListObject));

}

PyObject *

PyList_New(Py_ssize_t size)

{

if (size < 0) {

PyErr_BadInternalCall();

return NULL;

}

PyListObject *op = _Py_FREELIST_POP(PyListObject, lists);

if (op == NULL) {

op = PyObject_GC_New(PyListObject, &PyList_Type);

if (op == NULL) {

return NULL;

}

}

if (size <= 0) {

op->ob_item = NULL;

}

else {

#ifdef Py_GIL_DISABLED

_PyListArray *array = list_allocate_array(size);

if (array == NULL) {

Py_DECREF(op);

return PyErr_NoMemory();

}

memset(&array->ob_item, 0, size * sizeof(PyObject *));

op->ob_item = array->ob_item;

#else

op->ob_item = (PyObject **) PyMem_Calloc(size, sizeof(PyObject *));

#endif

if (op->ob_item == NULL) {

Py_DECREF(op);

return PyErr_NoMemory();

}

}

Py_SET_SIZE(op, size);

op->allocated = size;

_PyObject_GC_TRACK(op);

return (PyObject *) op;

}

static PyObject *

list_new_prealloc(Py_ssize_t size)

{

assert(size > 0);

PyListObject *op = (PyListObject *) PyList_New(0);

if (op == NULL) {

return NULL;

}

assert(op->ob_item == NULL);

#ifdef Py_GIL_DISABLED

_PyListArray *array = list_allocate_array(size);

if (array == NULL) {

Py_DECREF(op);

return PyErr_NoMemory();

}

op->ob_item = array->ob_item;

#else

op->ob_item = PyMem_New(PyObject *, size);

if (op->ob_item == NULL) {

Py_DECREF(op);

return PyErr_NoMemory();

}

#endif

op->allocated = size;

return (PyObject *) op;

}

Py_ssize_t

PyList_Size(PyObject *op)

{

if (!PyList_Check(op)) {

PyErr_BadInternalCall();

return -1;

}

else {

return PyList_GET_SIZE(op);

}

}

static inline int

valid_index(Py_ssize_t i, Py_ssize_t limit)

{

/* The cast to size_t lets us use just a single comparison

to check whether i is in the range: 0 <= i < limit.

See: Section 14.2 "Bounds Checking" in the Agner Fog

optimization manual found at:

https://www.agner.org/optimize/optimizing_cpp.pdf

*/

return (size_t) i < (size_t) limit;

}

#ifdef Py_GIL_DISABLED

static PyObject *

list_item_impl(PyListObject *self, Py_ssize_t idx)

{

PyObject *item = NULL;

Py_BEGIN_CRITICAL_SECTION(self);

if (!_PyObject_GC_IS_SHARED(self)) {

_PyObject_GC_SET_SHARED(self);

}

Py_ssize_t size = Py_SIZE(self);

if (!valid_index(idx, size)) {

goto exit;

}

item = _Py_NewRefWithLock(self->ob_item[idx]);

exit:

Py_END_CRITICAL_SECTION();

return item;

}

static inline PyObject*

list_get_item_ref(PyListObject *op, Py_ssize_t i)

{

if (!_Py_IsOwnedByCurrentThread((PyObject *)op) && !_PyObject_GC_IS_SHARED(op)) {

return list_item_impl(op, i);

}

// Need atomic operation for the getting size.

Py_ssize_t size = PyList_GET_SIZE(op);

if (!valid_index(i, size)) {

return NULL;

}

PyObject **ob_item = _Py_atomic_load_ptr(&op->ob_item);

if (ob_item == NULL) {

return NULL;

}

Py_ssize_t cap = list_capacity(ob_item);

assert(cap != -1);

if (!valid_index(i, cap)) {

return NULL;

}

PyObject *item = _Py_TryXGetRef(&ob_item[i]);

if (item == NULL) {

return list_item_impl(op, i);

}

return item;

}

#else

static inline PyObject*

list_get_item_ref(PyListObject *op, Py_ssize_t i)

{

if (!valid_index(i, Py_SIZE(op))) {

return NULL;

}

return Py_NewRef(PyList_GET_ITEM(op, i));

}

#endif

PyObject *

PyList_GetItem(PyObject *op, Py_ssize_t i)

{

if (!PyList_Check(op)) {

PyErr_BadInternalCall();

return NULL;

}

if (!valid_index(i, Py_SIZE(op))) {

_Py_DECLARE_STR(list_err, "list index out of range");

PyErr_SetObject(PyExc_IndexError, &_Py_STR(list_err));

return NULL;

}

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

}

PyObject *

PyList_GetItemRef(PyObject *op, Py_ssize_t i)

{

if (!PyList_Check(op)) {

PyErr_SetString(PyExc_TypeError, "expected a list");

return NULL;

}

PyObject *item = list_get_item_ref((PyListObject *)op, i);

if (item == NULL) {

_Py_DECLARE_STR(list_err, "list index out of range");

PyErr_SetObject(PyExc_IndexError, &_Py_STR(list_err));

return NULL;

}

return item;

}

PyObject *

_PyList_GetItemRef(PyListObject *list, Py_ssize_t i)

{

return list_get_item_ref(list, i);

}

#ifdef Py_GIL_DISABLED

int

_PyList_GetItemRefNoLock(PyListObject *list, Py_ssize_t i, _PyStackRef *result)

{

assert(_Py_IsOwnedByCurrentThread((PyObject *)list) ||

_PyObject_GC_IS_SHARED(list));

if (!valid_index(i, PyList_GET_SIZE(list))) {

return 0;

}

PyObject **ob_item = _Py_atomic_load_ptr(&list->ob_item);

if (ob_item == NULL) {

return 0;

}

Py_ssize_t cap = list_capacity(ob_item);

assert(cap != -1);

if (!valid_index(i, cap)) {

return 0;

}

PyObject *obj = _Py_atomic_load_ptr(&ob_item[i]);

if (obj == NULL || !_Py_TryIncrefCompareStackRef(&ob_item[i], obj, result)) {

return -1;

}

return 1;

}

#endif

int

PyList_SetItem(PyObject *op, Py_ssize_t i,

PyObject *newitem)

{

if (!PyList_Check(op)) {

Py_XDECREF(newitem);

PyErr_BadInternalCall();

return -1;

}

int ret;

PyListObject *self = ((PyListObject *)op);

Py_BEGIN_CRITICAL_SECTION(self);

if (!valid_index(i, Py_SIZE(self))) {

Py_XDECREF(newitem);

PyErr_SetString(PyExc_IndexError,

"list assignment index out of range");

ret = -1;

goto end;

}

PyObject *tmp = self->ob_item[i];

FT_ATOMIC_STORE_PTR_RELEASE(self->ob_item[i], newitem);

Py_XDECREF(tmp);

ret = 0;

end:;

Py_END_CRITICAL_SECTION();

return ret;

}

static int

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

{

Py_ssize_t i, n = Py_SIZE(self);

PyObject **items;

if (v == NULL) {

PyErr_BadInternalCall();

return -1;

}

assert((size_t)n + 1 < PY_SSIZE_T_MAX);

if (list_resize(self, n+1) < 0)

return -1;

if (where < 0) {

where += n;

if (where < 0)

where = 0;

}

if (where > n)

where = n;

items = self->ob_item;

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

FT_ATOMIC_STORE_PTR_RELEASE(items[i+1], items[i]);

FT_ATOMIC_STORE_PTR_RELEASE(items[where], Py_NewRef(v));

return 0;

}

int

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

{

if (!PyList_Check(op)) {

PyErr_BadInternalCall();

return -1;

}

PyListObject *self = (PyListObject *)op;

int err;

Py_BEGIN_CRITICAL_SECTION(self);

err = ins1(self, where, newitem);

Py_END_CRITICAL_SECTION();

return err;

}

/* internal, used by _PyList_AppendTakeRef */

int

_PyList_AppendTakeRefListResize(PyListObject *self, PyObject *newitem)

{

Py_ssize_t len = Py_SIZE(self);

assert(self->allocated == -1 || self->allocated == len);

if (list_resize(self, len + 1) < 0) {

Py_DECREF(newitem);

return -1;

}

FT_ATOMIC_STORE_PTR_RELEASE(self->ob_item[len], newitem);

return 0;

}

int

PyList_Append(PyObject *op, PyObject *newitem)

{

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

int ret;

Py_BEGIN_CRITICAL_SECTION(op);

ret = _PyList_AppendTakeRef((PyListObject *)op, Py_NewRef(newitem));

Py_END_CRITICAL_SECTION();

return ret;

}

PyErr_BadInternalCall();

return -1;

}

/* Methods */

static void

list_dealloc(PyObject *self)

{

PyListObject *op = (PyListObject *)self;

Py_ssize_t i;

PyObject_GC_UnTrack(op);

if (op->ob_item != NULL) {

/* Do it backwards, for Christian Tismer.

There's a simple test case where somehow this reduces

thrashing when a *very* large list is created and

immediately deleted. */

i = Py_SIZE(op);

while (--i >= 0) {

Py_XDECREF(op->ob_item[i]);

}

free_list_items(op->ob_item, false);

op->ob_item = NULL;

}

if (PyList_CheckExact(op)) {

_Py_FREELIST_FREE(lists, op, PyObject_GC_Del);

}

else {

PyObject_GC_Del(op);

}

}

static PyObject *

list_repr_impl(PyListObject *v)

{

int res = Py_ReprEnter((PyObject*)v);

if (res != 0) {

return (res > 0 ? PyUnicode_FromString("[...]") : NULL);

}

/* "[" + "1" + ", 2" * (len - 1) + "]" */

Py_ssize_t prealloc = 1 + 1 + (2 + 1) * (Py_SIZE(v) - 1) + 1;

PyUnicodeWriter *writer = PyUnicodeWriter_Create(prealloc);

PyObject *item = NULL;

if (writer == NULL) {

goto error;

}

if (PyUnicodeWriter_WriteChar(writer, '[') < 0) {

goto error;

}

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

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

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

/* Hold a strong reference since repr(item) can mutate the list */

item = Py_NewRef(v->ob_item[i]);

if (i > 0) {

if (PyUnicodeWriter_WriteChar(writer, ',') < 0) {

goto error;

}

if (PyUnicodeWriter_WriteChar(writer, ' ') < 0) {

goto error;

}

}

if (PyUnicodeWriter_WriteRepr(writer, item) < 0) {

goto error;

}

Py_CLEAR(item);

}

if (PyUnicodeWriter_WriteChar(writer, ']') < 0) {

goto error;

}

Py_ReprLeave((PyObject *)v);

return PyUnicodeWriter_Finish(writer);

error:

Py_XDECREF(item);

PyUnicodeWriter_Discard(writer);

Py_ReprLeave((PyObject *)v);

return NULL;

}

static PyObject *

list_repr(PyObject *self)

{

if (PyList_GET_SIZE(self) == 0) {

return PyUnicode_FromString("[]");

}

PyListObject *v = (PyListObject *)self;

PyObject *ret = NULL;

Py_BEGIN_CRITICAL_SECTION(v);

ret = list_repr_impl(v);

Py_END_CRITICAL_SECTION();

return ret;

}

static Py_ssize_t

list_length(PyObject *a)

{

return PyList_GET_SIZE(a);

}

static int

list_contains(PyObject *aa, PyObject *el)

{

for (Py_ssize_t i = 0; ; i++) {

PyObject *item = list_get_item_ref((PyListObject *)aa, i);

if (item == NULL) {

// out-of-bounds

return 0;

}

int cmp = PyObject_RichCompareBool(item, el, Py_EQ);

Py_DECREF(item);

if (cmp != 0) {

return cmp;

}

}

return 0;

}

static PyObject *

list_item(PyObject *aa, Py_ssize_t i)

{

PyListObject *a = (PyListObject *)aa;

if (!valid_index(i, PyList_GET_SIZE(a))) {

PyErr_SetObject(PyExc_IndexError, &_Py_STR(list_err));

return NULL;

}

PyObject *item;

#ifdef Py_GIL_DISABLED

item = list_get_item_ref(a, i);

if (item == NULL) {

PyErr_SetObject(PyExc_IndexError, &_Py_STR(list_err));

return NULL;

}

#else

item = Py_NewRef(a->ob_item[i]);

#endif

return item;

}

static PyObject *

list_slice_lock_held(PyListObject *a, Py_ssize_t ilow, Py_ssize_t ihigh)

{

PyListObject *np;

PyObject **src, **dest;

Py_ssize_t i, len;

len = ihigh - ilow;

if (len <= 0) {

return PyList_New(0);

}

np = (PyListObject *) list_new_prealloc(len);

if (np == NULL)

return NULL;

src = a->ob_item + ilow;

dest = np->ob_item;

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

PyObject *v = src[i];

dest[i] = Py_NewRef(v);

}

Py_SET_SIZE(np, len);

return (PyObject *)np;

}

PyObject *

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

{

if (!PyList_Check(a)) {

PyErr_BadInternalCall();

return NULL;

}

PyObject *ret;

Py_BEGIN_CRITICAL_SECTION(a);

if (ilow < 0) {

ilow = 0;

}

else if (ilow > Py_SIZE(a)) {

ilow = Py_SIZE(a);

}

if (ihigh < ilow) {

ihigh = ilow;

}

else if (ihigh > Py_SIZE(a)) {

ihigh = Py_SIZE(a);

}

ret = list_slice_lock_held((PyListObject *)a, ilow, ihigh);

Py_END_CRITICAL_SECTION();

return ret;

}

static PyObject *

list_concat_lock_held(PyListObject *a, PyListObject *b)

{

Py_ssize_t size;

Py_ssize_t i;

PyObject **src, **dest;

PyListObject *np;

assert((size_t)Py_SIZE(a) + (size_t)Py_SIZE(b) < PY_SSIZE_T_MAX);

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

if (size == 0) {

return PyList_New(0);

}

np = (PyListObject *) list_new_prealloc(size);

if (np == NULL) {

return NULL;

}

src = a->ob_item;

dest = np->ob_item;

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

PyObject *v = src[i];

dest[i] = Py_NewRef(v);

}

src = b->ob_item;

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

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

PyObject *v = src[i];

dest[i] = Py_NewRef(v);

}

Py_SET_SIZE(np, size);

return (PyObject *)np;

}

static PyObject *

list_concat(PyObject *aa, PyObject *bb)

{

if (!PyList_Check(bb)) {

PyErr_Format(PyExc_TypeError,

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

Py_TYPE(bb)->tp_name);

return NULL;

}

PyListObject *a = (PyListObject *)aa;

PyListObject *b = (PyListObject *)bb;

PyObject *ret;

Py_BEGIN_CRITICAL_SECTION2(a, b);

ret = list_concat_lock_held(a, b);

Py_END_CRITICAL_SECTION2();

return ret;

}

static PyObject *

list_repeat_lock_held(PyListObject *a, Py_ssize_t n)

{

const Py_ssize_t input_size = Py_SIZE(a);

if (input_size == 0 || n <= 0)

return PyList_New(0);

assert(n > 0);

if (input_size > PY_SSIZE_T_MAX / n)

return PyErr_NoMemory();

Py_ssize_t output_size = input_size * n;

PyListObject *np = (PyListObject *) list_new_prealloc(output_size);

if (np == NULL)

return NULL;

PyObject **dest = np->ob_item;

if (input_size == 1) {

PyObject *elem = a->ob_item[0];

_Py_RefcntAdd(elem, n);

PyObject **dest_end = dest + output_size;

while (dest < dest_end) {

*dest++ = elem;

}

}

else {

PyObject **src = a->ob_item;

PyObject **src_end = src + input_size;

while (src < src_end) {

_Py_RefcntAdd(*src, n);

*dest++ = *src++;

}

// This list is not yet visible to other threads, so atomic repeat

// is not necessary even in Py_GIL_DISABLED builds.

_Py_memory_repeat((char *)np->ob_item, sizeof(PyObject *)*output_size,

sizeof(PyObject *)*input_size);

}

Py_SET_SIZE(np, output_size);

return (PyObject *) np;

}

static PyObject *

list_repeat(PyObject *aa, Py_ssize_t n)

{

PyObject *ret;

PyListObject *a = (PyListObject *)aa;

Py_BEGIN_CRITICAL_SECTION(a);

ret = list_repeat_lock_held(a, n);

Py_END_CRITICAL_SECTION();

return ret;

}

static void

list_clear_impl(PyListObject *a, bool is_resize)

{

PyObject **items = a->ob_item;

if (items == NULL) {

return;

}

/* Because XDECREF can recursively invoke operations on

this list, we make it empty first. */

Py_ssize_t i = Py_SIZE(a);

Py_SET_SIZE(a, 0);

FT_ATOMIC_STORE_PTR_RELEASE(a->ob_item, NULL);

a->allocated = 0;

while (--i >= 0) {

Py_XDECREF(items[i]);

}

#ifdef Py_GIL_DISABLED

if (is_resize) {

ensure_shared_on_resize(a);

}

bool use_qsbr = is_resize && _PyObject_GC_IS_SHARED(a);

#else

bool use_qsbr = false;

#endif

free_list_items(items, use_qsbr);

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

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

}

static void

list_clear(PyListObject *a)

{

list_clear_impl(a, true);

}

static int

list_clear_slot(PyObject *self)

{

list_clear_impl((PyListObject *)self, false);

return 0;

}

// Pointer-by-pointer memmove for PyObject** arrays that is safe

// for shared lists in Py_GIL_DISABLED builds.

static void

ptr_wise_atomic_memmove(PyListObject *a, PyObject **dest, PyObject **src, Py_ssize_t n)

{

#ifndef Py_GIL_DISABLED

memmove(dest, src, n * sizeof(PyObject *));

#else

_Py_CRITICAL_SECTION_ASSERT_OBJECT_LOCKED(a);

if (_Py_IsOwnedByCurrentThread((PyObject *)a) && !_PyObject_GC_IS_SHARED(a)) {

// No other threads can read this list concurrently

memmove(dest, src, n * sizeof(PyObject *));

return;

}

if (dest < src) {

for (Py_ssize_t i = 0; i != n; i++) {

_Py_atomic_store_ptr_release(&dest[i], src[i]);

}

}

else {

// copy backwards to avoid overwriting src before it's read

for (Py_ssize_t i = n; i != 0; i--) {

_Py_atomic_store_ptr_release(&dest[i - 1], src[i - 1]);

}

}

#endif

}

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

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

*

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

* guaranteed the call cannot fail.

*/

static int

list_ass_slice_lock_held(PyListObject *a, Py_ssize_t ilow, Py_ssize_t ihigh, PyObject *v)

{

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

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

after the list is back in its canonical shape. Therefore

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

we temporarily copy the items that are deleted from the

list. :-( */

PyObject *recycle_on_stack[8];

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

PyObject **item;

PyObject **vitem = NULL;

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

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

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

Py_ssize_t d; /* Change in size */

Py_ssize_t k;

size_t s;

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

#define b ((PyListObject *)v)

if (v == NULL)

n = 0;

else {

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

if(v_as_SF == NULL)

goto Error;

n = PySequence_Fast_GET_SIZE(v_as_SF);

vitem = PySequence_Fast_ITEMS(v_as_SF);

}

if (ilow < 0)

ilow = 0;

else if (ilow > Py_SIZE(a))

ilow = Py_SIZE(a);

if (ihigh < ilow)

ihigh = ilow;

else if (ihigh > Py_SIZE(a))

ihigh = Py_SIZE(a);

norig = ihigh - ilow;

assert(norig >= 0);

d = n - norig;

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

Py_XDECREF(v_as_SF);

list_clear(a);

return 0;

}

item = a->ob_item;

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

s = norig * sizeof(PyObject *);

/* If norig == 0, item might be NULL, in which case we may not memcpy from it. */

if (s) {

if (s > sizeof(recycle_on_stack)) {

recycle = (PyObject **)PyMem_Malloc(s);

if (recycle == NULL) {

PyErr_NoMemory();

goto Error;

}

}

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

}

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

Py_ssize_t tail = Py_SIZE(a) - ihigh;

ptr_wise_atomic_memmove(a, &item[ihigh+d], &item[ihigh], tail);

(void)list_resize(a, Py_SIZE(a) + d); // NB: shrinking a list can't fail

item = a->ob_item;

}

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

k = Py_SIZE(a);

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

goto Error;

item = a->ob_item;

ptr_wise_atomic_memmove(a, &item[ihigh+d], &item[ihigh], k - ihigh);

}