#include "Python.h"

#include "pycore_call.h" // _PyObject_CallNoArgs()

#include "pycore_dict.h" // _PyDict_GetItem_KnownHash()

#include "pycore_long.h" // _PyLong_GetZero()

#include "pycore_moduleobject.h" // _PyModule_GetState()

#include "pycore_pyatomic_ft_wrappers.h"

#include "pycore_typeobject.h" // _PyType_GetModuleState()

#include "pycore_weakref.h" // FT_CLEAR_WEAKREFS()

#include <stddef.h>

typedef struct {

PyTypeObject *deque_type;

PyTypeObject *defdict_type;

PyTypeObject *dequeiter_type;

PyTypeObject *dequereviter_type;

PyTypeObject *tuplegetter_type;

} collections_state;

static inline collections_state *

get_module_state(PyObject *mod)

{

void *state = _PyModule_GetState(mod);

assert(state != NULL);

return (collections_state *)state;

}

static inline collections_state *

get_module_state_by_cls(PyTypeObject *cls)

{

void *state = _PyType_GetModuleState(cls);

assert(state != NULL);

return (collections_state *)state;

}

static struct PyModuleDef _collectionsmodule;

static inline collections_state *

find_module_state_by_def(PyTypeObject *type)

{

PyObject *mod = PyType_GetModuleByDef(type, &_collectionsmodule);

assert(mod != NULL);

return get_module_state(mod);

}

typedef struct dequeobject dequeobject;

#define clinic_state() (get_module_state_by_cls(type))

#include "clinic/_collectionsmodule.c.h"

#undef clinic_state

#define BLOCKLEN 64

#define CENTER ((BLOCKLEN - 1) / 2)

#define MAXFREEBLOCKS 16

typedef struct BLOCK {

struct BLOCK *leftlink;

PyObject *data[BLOCKLEN];

struct BLOCK *rightlink;

} block;

struct dequeobject {

PyObject_VAR_HEAD

block *leftblock;

block *rightblock;

Py_ssize_t leftindex; /* 0 <= leftindex < BLOCKLEN */

Py_ssize_t rightindex; /* 0 <= rightindex < BLOCKLEN */

size_t state; /* incremented whenever the indices move */

Py_ssize_t maxlen; /* maxlen is -1 for unbounded deques */

Py_ssize_t numfreeblocks;

block *freeblocks[MAXFREEBLOCKS];

PyObject *weakreflist;

};

#define dequeobject_CAST(op) ((dequeobject *)(op))

#ifndef NDEBUG

#define MARK_END(link) link = NULL;

#define CHECK_END(link) assert(link == NULL);

#define CHECK_NOT_END(link) assert(link != NULL);

#define MARK_END(link)

#define CHECK_END(link)

#define CHECK_NOT_END(link)

static inline block *

newblock(dequeobject *deque) {

block *b;

if (deque->numfreeblocks) {

deque->numfreeblocks--;

return deque->freeblocks[deque->numfreeblocks];

}

b = PyMem_Malloc(sizeof(block));

if (b != NULL) {

return b;

}

PyErr_NoMemory();

return NULL;

}

static inline void

freeblock(dequeobject *deque, block *b)

{

if (deque->numfreeblocks < MAXFREEBLOCKS) {

deque->freeblocks[deque->numfreeblocks] = b;

deque->numfreeblocks++;

} else {

PyMem_Free(b);

}

}

static PyObject *

deque_new(PyTypeObject *type, PyObject *args, PyObject *kwds)

{

dequeobject *deque;

block *b;

/* create dequeobject structure */

deque = (dequeobject *)type->tp_alloc(type, 0);

if (deque == NULL)

return NULL;

b = newblock(deque);

if (b == NULL) {

Py_DECREF(deque);

return NULL;

}

MARK_END(b->leftlink);

MARK_END(b->rightlink);

assert(BLOCKLEN >= 2);

Py_SET_SIZE(deque, 0);

deque->leftblock = b;

deque->rightblock = b;

deque->leftindex = CENTER + 1;

deque->rightindex = CENTER;

deque->state = 0;

deque->maxlen = -1;

deque->numfreeblocks = 0;

deque->weakreflist = NULL;

return (PyObject *)deque;

}

static PyObject *

deque_pop_impl(dequeobject *deque)

{

PyObject *item;

block *prevblock;

if (Py_SIZE(deque) == 0) {

PyErr_SetString(PyExc_IndexError, "pop from an empty deque");

return NULL;

}

item = deque->rightblock->data[deque->rightindex];

deque->rightindex--;

Py_SET_SIZE(deque, Py_SIZE(deque) - 1);

deque->state++;

if (deque->rightindex < 0) {

if (Py_SIZE(deque)) {

prevblock = deque->rightblock->leftlink;

assert(deque->leftblock != deque->rightblock);

freeblock(deque, deque->rightblock);

CHECK_NOT_END(prevblock);

MARK_END(prevblock->rightlink);

deque->rightblock = prevblock;

deque->rightindex = BLOCKLEN - 1;

} else {

assert(deque->leftblock == deque->rightblock);

assert(deque->leftindex == deque->rightindex+1);

/* re-center instead of freeing a block */

deque->leftindex = CENTER + 1;

deque->rightindex = CENTER;

}

}

return item;

}

static PyObject *

deque_popleft_impl(dequeobject *deque)

{

PyObject *item;

block *prevblock;

if (Py_SIZE(deque) == 0) {

PyErr_SetString(PyExc_IndexError, "pop from an empty deque");

return NULL;

}

assert(deque->leftblock != NULL);

item = deque->leftblock->data[deque->leftindex];

deque->leftindex++;

Py_SET_SIZE(deque, Py_SIZE(deque) - 1);

deque->state++;

if (deque->leftindex == BLOCKLEN) {

if (Py_SIZE(deque)) {

assert(deque->leftblock != deque->rightblock);

prevblock = deque->leftblock->rightlink;

freeblock(deque, deque->leftblock);

CHECK_NOT_END(prevblock);

MARK_END(prevblock->leftlink);

deque->leftblock = prevblock;

deque->leftindex = 0;

} else {

assert(deque->leftblock == deque->rightblock);

assert(deque->leftindex == deque->rightindex+1);

/* re-center instead of freeing a block */

deque->leftindex = CENTER + 1;

deque->rightindex = CENTER;

}

}

return item;

}

#define NEEDS_TRIM(deque, maxlen) ((size_t)(maxlen) < (size_t)(Py_SIZE(deque)))

static inline int

deque_append_lock_held(dequeobject *deque, PyObject *item, Py_ssize_t maxlen)

{

if (deque->rightindex == BLOCKLEN - 1) {

block *b = newblock(deque);

if (b == NULL) {

Py_DECREF(item);

return -1;

}

b->leftlink = deque->rightblock;

CHECK_END(deque->rightblock->rightlink);

deque->rightblock->rightlink = b;

deque->rightblock = b;

MARK_END(b->rightlink);

deque->rightindex = -1;

}

Py_SET_SIZE(deque, Py_SIZE(deque) + 1);

deque->rightindex++;

deque->rightblock->data[deque->rightindex] = item;

if (NEEDS_TRIM(deque, maxlen)) {

PyObject *olditem = deque_popleft_impl(deque);

Py_DECREF(olditem);

} else {

deque->state++;

}

return 0;

}

static PyObject *

deque_append_impl(dequeobject *deque, PyObject *item)

{

if (deque_append_lock_held(deque, Py_NewRef(item), deque->maxlen) < 0)

return NULL;

Py_RETURN_NONE;

}

static inline int

deque_appendleft_lock_held(dequeobject *deque, PyObject *item,

Py_ssize_t maxlen)

{

if (deque->leftindex == 0) {

block *b = newblock(deque);

if (b == NULL) {

Py_DECREF(item);

return -1;

}

b->rightlink = deque->leftblock;

CHECK_END(deque->leftblock->leftlink);

deque->leftblock->leftlink = b;

deque->leftblock = b;

MARK_END(b->leftlink);

deque->leftindex = BLOCKLEN;

}

Py_SET_SIZE(deque, Py_SIZE(deque) + 1);

deque->leftindex--;

deque->leftblock->data[deque->leftindex] = item;

if (NEEDS_TRIM(deque, maxlen)) {

PyObject *olditem = deque_pop_impl(deque);

Py_DECREF(olditem);

} else {

deque->state++;

}

return 0;

}

static PyObject *

deque_appendleft_impl(dequeobject *deque, PyObject *item)

{

if (deque_appendleft_lock_held(deque, Py_NewRef(item), deque->maxlen) < 0)

return NULL;

Py_RETURN_NONE;

}

static PyObject*

finalize_iterator(PyObject *it)

{

if (PyErr_Occurred()) {

if (PyErr_ExceptionMatches(PyExc_StopIteration))

PyErr_Clear();

else {

Py_DECREF(it);

return NULL;

}

}

Py_DECREF(it);

Py_RETURN_NONE;

}

static PyObject*

consume_iterator(PyObject *it)

{

PyObject *(*iternext)(PyObject *);

PyObject *item;

iternext = *Py_TYPE(it)->tp_iternext;

while ((item = iternext(it)) != NULL) {

Py_DECREF(item);

}

return finalize_iterator(it);

}

static PyObject *

deque_extend_impl(dequeobject *deque, PyObject *iterable)

{

PyObject *it, *item;

PyObject *(*iternext)(PyObject *);

Py_ssize_t maxlen = deque->maxlen;

/* Handle case where id(deque) == id(iterable) */

if ((PyObject *)deque == iterable) {

PyObject *result;

PyObject *s = PySequence_List(iterable);

if (s == NULL)

return NULL;

result = deque_extend((PyObject*)deque, s);

Py_DECREF(s);

return result;

}

it = PyObject_GetIter(iterable);

if (it == NULL)

return NULL;

if (maxlen == 0)

return consume_iterator(it);

/* Space saving heuristic. Start filling from the left */

if (Py_SIZE(deque) == 0) {

assert(deque->leftblock == deque->rightblock);

assert(deque->leftindex == deque->rightindex+1);

deque->leftindex = 1;

deque->rightindex = 0;

}

iternext = *Py_TYPE(it)->tp_iternext;

while ((item = iternext(it)) != NULL) {

if (deque_append_lock_held(deque, item, maxlen) == -1) {

Py_DECREF(item);

Py_DECREF(it);

return NULL;

}

}

return finalize_iterator(it);

}

static PyObject *

deque_extendleft_impl(dequeobject *deque, PyObject *iterable)

{

PyObject *it, *item;

PyObject *(*iternext)(PyObject *);

Py_ssize_t maxlen = deque->maxlen;

/* Handle case where id(deque) == id(iterable) */

if ((PyObject *)deque == iterable) {

PyObject *result;

PyObject *s = PySequence_List(iterable);

if (s == NULL)

return NULL;

result = deque_extendleft_impl(deque, s);

Py_DECREF(s);

return result;

}

it = PyObject_GetIter(iterable);

if (it == NULL)

return NULL;

if (maxlen == 0)

return consume_iterator(it);

/* Space saving heuristic. Start filling from the right */

if (Py_SIZE(deque) == 0) {

assert(deque->leftblock == deque->rightblock);

assert(deque->leftindex == deque->rightindex+1);

deque->leftindex = BLOCKLEN - 1;

deque->rightindex = BLOCKLEN - 2;

}

iternext = *Py_TYPE(it)->tp_iternext;

while ((item = iternext(it)) != NULL) {

if (deque_appendleft_lock_held(deque, item, maxlen) == -1) {

Py_DECREF(it);

return NULL;

}

}

return finalize_iterator(it);

}

static PyObject *

deque_inplace_concat(PyObject *self, PyObject *other)

{

dequeobject *deque = dequeobject_CAST(self);

PyObject *result;

// deque_extend is thread-safe

result = deque_extend((PyObject*)deque, other);

if (result == NULL)

return result;

Py_INCREF(deque);

Py_DECREF(result);

return (PyObject *)deque;

}

static PyObject *

deque_copy_impl(dequeobject *deque)

{

PyObject *result;

dequeobject *old_deque = deque;

collections_state *state = find_module_state_by_def(Py_TYPE(deque));

if (Py_IS_TYPE(deque, state->deque_type)) {

dequeobject *new_deque;

Py_ssize_t n = Py_SIZE(deque);

new_deque = (dequeobject *)deque_new(state->deque_type, NULL, NULL);

if (new_deque == NULL)

return NULL;

new_deque->maxlen = old_deque->maxlen;

/* Copy elements directly by walking the block structure.

if (n > 0) {

block *b = old_deque->leftblock;

Py_ssize_t index = old_deque->leftindex;

/* Space saving heuristic. Start filling from the left */

assert(new_deque->leftblock == new_deque->rightblock);

assert(new_deque->leftindex == new_deque->rightindex + 1);

new_deque->leftindex = 1;

new_deque->rightindex = 0;

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

PyObject *item = b->data[index];

if (deque_append_lock_held(new_deque, Py_NewRef(item),

new_deque->maxlen) < 0) {

Py_DECREF(new_deque);

return NULL;

}

index++;

if (index == BLOCKLEN) {

b = b->rightlink;

index = 0;

}

}

}

return (PyObject *)new_deque;

}

if (old_deque->maxlen < 0)

result = PyObject_CallOneArg((PyObject *)(Py_TYPE(deque)),

(PyObject *)deque);

else

result = PyObject_CallFunction((PyObject *)(Py_TYPE(deque)), "Oi",

deque, old_deque->maxlen, NULL);

if (result != NULL && !PyObject_TypeCheck(result, state->deque_type)) {

PyErr_Format(PyExc_TypeError,

"%.200s() must return a deque, not %.200s",

Py_TYPE(deque)->tp_name, Py_TYPE(result)->tp_name);

Py_DECREF(result);

return NULL;

}

return result;

}

static PyObject *

deque___copy___impl(dequeobject *deque)

{

return deque_copy_impl(deque);

}

static PyObject *

deque_concat_lock_held(dequeobject *deque, PyObject *other)

{

PyObject *new_deque, *result;

int rv;

collections_state *state = find_module_state_by_def(Py_TYPE(deque));

rv = PyObject_IsInstance(other, (PyObject *)state->deque_type);

if (rv <= 0) {

if (rv == 0) {

PyErr_Format(PyExc_TypeError,

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

Py_TYPE(other)->tp_name);

}

return NULL;

}

new_deque = deque_copy_impl(deque);

if (new_deque == NULL)

return NULL;

// It's safe to not acquire the per-object lock for new_deque; it's

// invisible to other threads.

result = deque_extend_impl((dequeobject *)new_deque, other);

if (result == NULL) {

Py_DECREF(new_deque);

return NULL;

}

Py_DECREF(result);

return new_deque;

}

static PyObject *

deque_concat(PyObject *self, PyObject *other)

{

dequeobject *deque = dequeobject_CAST(self);

PyObject *result;

Py_BEGIN_CRITICAL_SECTION(deque);

result = deque_concat_lock_held(deque, other);

Py_END_CRITICAL_SECTION();

return result;

}

static int

deque_clear(PyObject *self)

{

block *b;

block *prevblock;

block *leftblock;

Py_ssize_t leftindex;

Py_ssize_t n, m;

PyObject *item;

PyObject **itemptr, **limit;

dequeobject *deque = dequeobject_CAST(self);

if (Py_SIZE(deque) == 0)

return 0;

/* During the process of clearing a deque, decrefs can cause the

b = newblock(deque);

if (b == NULL) {

PyErr_Clear();

goto alternate_method;

}

/* Remember the old size, leftblock, and leftindex */

n = Py_SIZE(deque);

leftblock = deque->leftblock;

leftindex = deque->leftindex;

/* Set the deque to be empty using the newly allocated block */

MARK_END(b->leftlink);

MARK_END(b->rightlink);

Py_SET_SIZE(deque, 0);

deque->leftblock = b;

deque->rightblock = b;

deque->leftindex = CENTER + 1;

deque->rightindex = CENTER;

deque->state++;

/* Now the old size, leftblock, and leftindex are disconnected from

m = (BLOCKLEN - leftindex > n) ? n : BLOCKLEN - leftindex;

itemptr = &leftblock->data[leftindex];

limit = itemptr + m;

n -= m;

while (1) {

if (itemptr == limit) {

if (n == 0)

break;

CHECK_NOT_END(leftblock->rightlink);

prevblock = leftblock;

leftblock = leftblock->rightlink;

m = (n > BLOCKLEN) ? BLOCKLEN : n;

itemptr = leftblock->data;

limit = itemptr + m;

n -= m;

freeblock(deque, prevblock);

}

item = *(itemptr++);

Py_DECREF(item);

}

CHECK_END(leftblock->rightlink);

freeblock(deque, leftblock);

return 0;

alternate_method:

while (Py_SIZE(deque)) {

item = deque_pop_impl(deque);

assert (item != NULL);

Py_DECREF(item);

}

return 0;

}

static PyObject *

deque_clearmethod_impl(dequeobject *deque)

{

(void)deque_clear((PyObject *)deque);

Py_RETURN_NONE;

}

static PyObject *

deque_inplace_repeat_lock_held(dequeobject *deque, Py_ssize_t n)

{

Py_ssize_t i, m, size;

PyObject *seq;

PyObject *rv;

size = Py_SIZE(deque);

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

return Py_NewRef(deque);

}

if (n <= 0) {

(void)deque_clear((PyObject *)deque);

return Py_NewRef(deque);

}

if (size == 1) {

/* common case, repeating a single element */

PyObject *item = deque->leftblock->data[deque->leftindex];

if (deque->maxlen >= 0 && n > deque->maxlen)

n = deque->maxlen;

deque->state++;

for (i = 0 ; i < n-1 ; ) {

if (deque->rightindex == BLOCKLEN - 1) {

block *b = newblock(deque);

if (b == NULL) {

Py_SET_SIZE(deque, Py_SIZE(deque) + i);

return NULL;

}

b->leftlink = deque->rightblock;

CHECK_END(deque->rightblock->rightlink);

deque->rightblock->rightlink = b;

deque->rightblock = b;

MARK_END(b->rightlink);

deque->rightindex = -1;

}

m = n - 1 - i;

if (m > BLOCKLEN - 1 - deque->rightindex)

m = BLOCKLEN - 1 - deque->rightindex;

i += m;

while (m--) {

deque->rightindex++;

deque->rightblock->data[deque->rightindex] = Py_NewRef(item);

}

}

Py_SET_SIZE(deque, Py_SIZE(deque) + i);

return Py_NewRef(deque);

}

if ((size_t)size > PY_SSIZE_T_MAX / (size_t)n) {

return PyErr_NoMemory();

}

seq = PySequence_List((PyObject *)deque);

if (seq == NULL)

return seq;

/* Reduce the number of repetitions when maxlen would be exceeded */

if (deque->maxlen >= 0 && n * size > deque->maxlen)

n = (deque->maxlen + size - 1) / size;

for (i = 0 ; i < n-1 ; i++) {

rv = deque_extend_impl(deque, seq);

if (rv == NULL) {

Py_DECREF(seq);

return NULL;

}

Py_DECREF(rv);

}

Py_INCREF(deque);

Py_DECREF(seq);

return (PyObject *)deque;

}

static PyObject *

deque_inplace_repeat(PyObject *self, Py_ssize_t n)

{

dequeobject *deque = dequeobject_CAST(self);

PyObject *result;

Py_BEGIN_CRITICAL_SECTION(deque);

result = deque_inplace_repeat_lock_held(deque, n);

Py_END_CRITICAL_SECTION();

return result;

}

static PyObject *

deque_repeat(PyObject *self, Py_ssize_t n)

{

dequeobject *deque = dequeobject_CAST(self);

dequeobject *new_deque;

PyObject *rv;

Py_BEGIN_CRITICAL_SECTION(deque);

new_deque = (dequeobject *)deque_copy_impl(deque);

Py_END_CRITICAL_SECTION();

if (new_deque == NULL)

return NULL;

// It's safe to not acquire the per-object lock for new_deque; it's

// invisible to other threads.

rv = deque_inplace_repeat_lock_held(new_deque, n);

Py_DECREF(new_deque);

return rv;

}

static int

_deque_rotate(dequeobject *deque, Py_ssize_t n)

{

block *b = NULL;

block *leftblock = deque->leftblock;

block *rightblock = deque->rightblock;

Py_ssize_t leftindex = deque->leftindex;

Py_ssize_t rightindex = deque->rightindex;

Py_ssize_t len=Py_SIZE(deque), halflen=len>>1;

int rv = -1;

if (len <= 1)

return 0;

if (n > halflen || n < -halflen) {

n %= len;

if (n > halflen)

n -= len;

else if (n < -halflen)

n += len;

}

assert(len > 1);

assert(-halflen <= n && n <= halflen);

deque->state++;

while (n > 0) {

if (leftindex == 0) {

if (b == NULL) {

b = newblock(deque);

if (b == NULL)

goto done;

}

b->rightlink = leftblock;

CHECK_END(leftblock->leftlink);

leftblock->leftlink = b;

leftblock = b;

MARK_END(b->leftlink);

leftindex = BLOCKLEN;

b = NULL;

}

assert(leftindex > 0);

{

PyObject **src, **dest;

Py_ssize_t m = n;

if (m > rightindex + 1)

m = rightindex + 1;