diff options
Diffstat (limited to 'contrib/tools/python3/Modules/_collectionsmodule.c')
| -rw-r--r-- | contrib/tools/python3/Modules/_collectionsmodule.c | 662 |
1 files changed, 456 insertions, 206 deletions
diff --git a/contrib/tools/python3/Modules/_collectionsmodule.c b/contrib/tools/python3/Modules/_collectionsmodule.c index 4e195f0d5f5..b2c3d0e42be 100644 --- a/contrib/tools/python3/Modules/_collectionsmodule.c +++ b/contrib/tools/python3/Modules/_collectionsmodule.c @@ -1,9 +1,12 @@ #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 "structmember.h" // PyMemberDef +#include "pycore_weakref.h" // FT_CLEAR_WEAKREFS() + #include <stddef.h> typedef struct { @@ -43,8 +46,11 @@ find_module_state_by_def(PyTypeObject *type) /*[clinic input] module _collections class _tuplegetter "_tuplegetterobject *" "clinic_state()->tuplegetter_type" +class _collections.deque "dequeobject *" "clinic_state()->deque_type" [clinic start generated code]*/ -/*[clinic end generated code: output=da39a3ee5e6b4b0d input=7356042a89862e0e]*/ +/*[clinic end generated code: output=da39a3ee5e6b4b0d input=a033cc2a8476b3f1]*/ + +typedef struct dequeobject dequeobject; /* We can safely assume type to be the defining class, * since tuplegetter is not a base type */ @@ -52,6 +58,12 @@ class _tuplegetter "_tuplegetterobject *" "clinic_state()->tuplegetter_type" #include "clinic/_collectionsmodule.c.h" #undef clinic_state +/*[python input] +class dequeobject_converter(self_converter): + type = "dequeobject *" +[python start generated code]*/ +/*[python end generated code: output=da39a3ee5e6b4b0d input=b6ae4a3ff852be2f]*/ + /* collections module implementation of a deque() datatype Written and maintained by Raymond D. Hettinger <[email protected]> */ @@ -120,7 +132,7 @@ typedef struct BLOCK { struct BLOCK *rightlink; } block; -typedef struct { +struct dequeobject { PyObject_VAR_HEAD block *leftblock; block *rightblock; @@ -131,7 +143,7 @@ typedef struct { Py_ssize_t numfreeblocks; block *freeblocks[MAXFREEBLOCKS]; PyObject *weakreflist; -} dequeobject; +}; /* For debug builds, add error checking to track the endpoints * in the chain of links. The goal is to make sure that link @@ -218,8 +230,18 @@ deque_new(PyTypeObject *type, PyObject *args, PyObject *kwds) return (PyObject *)deque; } +/*[clinic input] +@critical_section +_collections.deque.pop as deque_pop + + deque: dequeobject + +Remove and return the rightmost element. +[clinic start generated code]*/ + static PyObject * -deque_pop(dequeobject *deque, PyObject *unused) +deque_pop_impl(dequeobject *deque) +/*[clinic end generated code: output=2e5f7890c4251f07 input=55c5b6a8ad51d72f]*/ { PyObject *item; block *prevblock; @@ -253,10 +275,18 @@ deque_pop(dequeobject *deque, PyObject *unused) return item; } -PyDoc_STRVAR(pop_doc, "Remove and return the rightmost element."); +/*[clinic input] +@critical_section +_collections.deque.popleft as deque_popleft + + deque: dequeobject + +Remove and return the leftmost element. +[clinic start generated code]*/ static PyObject * -deque_popleft(dequeobject *deque, PyObject *unused) +deque_popleft_impl(dequeobject *deque) +/*[clinic end generated code: output=62b154897097ff68 input=1571ce88fe3053de]*/ { PyObject *item; block *prevblock; @@ -291,8 +321,6 @@ deque_popleft(dequeobject *deque, PyObject *unused) return item; } -PyDoc_STRVAR(popleft_doc, "Remove and return the leftmost element."); - /* The deque's size limit is d.maxlen. The limit can be zero or positive. * If there is no limit, then d.maxlen == -1. * @@ -308,7 +336,7 @@ PyDoc_STRVAR(popleft_doc, "Remove and return the leftmost element."); #define NEEDS_TRIM(deque, maxlen) ((size_t)(maxlen) < (size_t)(Py_SIZE(deque))) static inline int -deque_append_internal(dequeobject *deque, PyObject *item, Py_ssize_t maxlen) +deque_append_lock_held(dequeobject *deque, PyObject *item, Py_ssize_t maxlen) { if (deque->rightindex == BLOCKLEN - 1) { block *b = newblock(deque); @@ -325,7 +353,7 @@ deque_append_internal(dequeobject *deque, PyObject *item, Py_ssize_t maxlen) deque->rightindex++; deque->rightblock->data[deque->rightindex] = item; if (NEEDS_TRIM(deque, maxlen)) { - PyObject *olditem = deque_popleft(deque, NULL); + PyObject *olditem = deque_popleft_impl(deque); Py_DECREF(olditem); } else { deque->state++; @@ -333,18 +361,29 @@ deque_append_internal(dequeobject *deque, PyObject *item, Py_ssize_t maxlen) return 0; } +/*[clinic input] +@critical_section +_collections.deque.append as deque_append + + deque: dequeobject + item: object + / + +Add an element to the right side of the deque. +[clinic start generated code]*/ + static PyObject * -deque_append(dequeobject *deque, PyObject *item) +deque_append_impl(dequeobject *deque, PyObject *item) +/*[clinic end generated code: output=9c7bcb8b599c6362 input=b0eeeb09b9f5cf18]*/ { - if (deque_append_internal(deque, Py_NewRef(item), deque->maxlen) < 0) + if (deque_append_lock_held(deque, Py_NewRef(item), deque->maxlen) < 0) return NULL; Py_RETURN_NONE; } -PyDoc_STRVAR(append_doc, "Add an element to the right side of the deque."); - static inline int -deque_appendleft_internal(dequeobject *deque, PyObject *item, Py_ssize_t maxlen) +deque_appendleft_lock_held(dequeobject *deque, PyObject *item, + Py_ssize_t maxlen) { if (deque->leftindex == 0) { block *b = newblock(deque); @@ -360,8 +399,8 @@ deque_appendleft_internal(dequeobject *deque, PyObject *item, Py_ssize_t maxlen) Py_SET_SIZE(deque, Py_SIZE(deque) + 1); deque->leftindex--; deque->leftblock->data[deque->leftindex] = item; - if (NEEDS_TRIM(deque, deque->maxlen)) { - PyObject *olditem = deque_pop(deque, NULL); + if (NEEDS_TRIM(deque, maxlen)) { + PyObject *olditem = deque_pop_impl(deque); Py_DECREF(olditem); } else { deque->state++; @@ -369,16 +408,26 @@ deque_appendleft_internal(dequeobject *deque, PyObject *item, Py_ssize_t maxlen) return 0; } +/*[clinic input] +@critical_section +_collections.deque.appendleft as deque_appendleft + + deque: dequeobject + item: object + / + +Add an element to the left side of the deque. +[clinic start generated code]*/ + static PyObject * -deque_appendleft(dequeobject *deque, PyObject *item) +deque_appendleft_impl(dequeobject *deque, PyObject *item) +/*[clinic end generated code: output=9a192edbcd0f20db input=236c2fbceaf08e14]*/ { - if (deque_appendleft_internal(deque, Py_NewRef(item), deque->maxlen) < 0) + if (deque_appendleft_lock_held(deque, Py_NewRef(item), deque->maxlen) < 0) return NULL; Py_RETURN_NONE; } -PyDoc_STRVAR(appendleft_doc, "Add an element to the left side of the deque."); - static PyObject* finalize_iterator(PyObject *it) { @@ -409,8 +458,20 @@ consume_iterator(PyObject *it) return finalize_iterator(it); } +/*[clinic input] +@critical_section +_collections.deque.extend as deque_extend + + deque: dequeobject + iterable: object + / + +Extend the right side of the deque with elements from the iterable. +[clinic start generated code]*/ + static PyObject * -deque_extend(dequeobject *deque, PyObject *iterable) +deque_extend_impl(dequeobject *deque, PyObject *iterable) +/*[clinic end generated code: output=8b5ffa57ce82d980 input=85861954127c81da]*/ { PyObject *it, *item; PyObject *(*iternext)(PyObject *); @@ -444,7 +505,7 @@ deque_extend(dequeobject *deque, PyObject *iterable) iternext = *Py_TYPE(it)->tp_iternext; while ((item = iternext(it)) != NULL) { - if (deque_append_internal(deque, item, maxlen) == -1) { + if (deque_append_lock_held(deque, item, maxlen) == -1) { Py_DECREF(item); Py_DECREF(it); return NULL; @@ -453,11 +514,20 @@ deque_extend(dequeobject *deque, PyObject *iterable) return finalize_iterator(it); } -PyDoc_STRVAR(extend_doc, -"Extend the right side of the deque with elements from the iterable"); +/*[clinic input] +@critical_section +_collections.deque.extendleft as deque_extendleft + + deque: dequeobject + iterable: object + / + +Extend the left side of the deque with elements from the iterable. +[clinic start generated code]*/ static PyObject * -deque_extendleft(dequeobject *deque, PyObject *iterable) +deque_extendleft_impl(dequeobject *deque, PyObject *iterable) +/*[clinic end generated code: output=ba44191aa8e35a26 input=640dabd086115689]*/ { PyObject *it, *item; PyObject *(*iternext)(PyObject *); @@ -469,7 +539,7 @@ deque_extendleft(dequeobject *deque, PyObject *iterable) PyObject *s = PySequence_List(iterable); if (s == NULL) return NULL; - result = deque_extendleft(deque, s); + result = deque_extendleft_impl(deque, s); Py_DECREF(s); return result; } @@ -491,7 +561,7 @@ deque_extendleft(dequeobject *deque, PyObject *iterable) iternext = *Py_TYPE(it)->tp_iternext; while ((item = iternext(it)) != NULL) { - if (deque_appendleft_internal(deque, item, maxlen) == -1) { + if (deque_appendleft_lock_held(deque, item, maxlen) == -1) { Py_DECREF(item); Py_DECREF(it); return NULL; @@ -500,14 +570,12 @@ deque_extendleft(dequeobject *deque, PyObject *iterable) return finalize_iterator(it); } -PyDoc_STRVAR(extendleft_doc, -"Extend the left side of the deque with elements from the iterable"); - static PyObject * deque_inplace_concat(dequeobject *deque, PyObject *other) { PyObject *result; + // deque_extend is thread-safe result = deque_extend(deque, other); if (result == NULL) return result; @@ -516,8 +584,18 @@ deque_inplace_concat(dequeobject *deque, PyObject *other) return (PyObject *)deque; } +/*[clinic input] +@critical_section +_collections.deque.copy as deque_copy + + deque: dequeobject + +Return a shallow copy of a deque. +[clinic start generated code]*/ + static PyObject * -deque_copy(PyObject *deque, PyObject *Py_UNUSED(ignored)) +deque_copy_impl(dequeobject *deque) +/*[clinic end generated code: output=6409b3d1ad2898b5 input=51d2ed1a23bab5e2]*/ { PyObject *result; dequeobject *old_deque = (dequeobject *)deque; @@ -531,12 +609,16 @@ deque_copy(PyObject *deque, PyObject *Py_UNUSED(ignored)) if (new_deque == NULL) return NULL; new_deque->maxlen = old_deque->maxlen; - /* Fast path for the deque_repeat() common case where len(deque) == 1 */ + /* Fast path for the deque_repeat() common case where len(deque) == 1 + * + * It's safe to not acquire the per-object lock for new_deque; it's + * invisible to other threads. + */ if (Py_SIZE(deque) == 1) { PyObject *item = old_deque->leftblock->data[old_deque->leftindex]; - rv = deque_append(new_deque, item); + rv = deque_append_impl(new_deque, item); } else { - rv = deque_extend(new_deque, deque); + rv = deque_extend_impl(new_deque, (PyObject *)deque); } if (rv != NULL) { Py_DECREF(rv); @@ -546,7 +628,8 @@ deque_copy(PyObject *deque, PyObject *Py_UNUSED(ignored)) return NULL; } if (old_deque->maxlen < 0) - result = PyObject_CallOneArg((PyObject *)(Py_TYPE(deque)), deque); + result = PyObject_CallOneArg((PyObject *)(Py_TYPE(deque)), + (PyObject *)deque); else result = PyObject_CallFunction((PyObject *)(Py_TYPE(deque)), "Oi", deque, old_deque->maxlen, NULL); @@ -560,10 +643,22 @@ deque_copy(PyObject *deque, PyObject *Py_UNUSED(ignored)) return result; } -PyDoc_STRVAR(copy_doc, "Return a shallow copy of a deque."); +/*[clinic input] +@critical_section +_collections.deque.__copy__ as deque___copy__ = _collections.deque.copy + +Return a shallow copy of a deque. +[clinic start generated code]*/ static PyObject * -deque_concat(dequeobject *deque, PyObject *other) +deque___copy___impl(dequeobject *deque) +/*[clinic end generated code: output=7c5821504342bf23 input=f5464036f9686a55]*/ +{ + return deque_copy_impl(deque); +} + +static PyObject * +deque_concat_lock_held(dequeobject *deque, PyObject *other) { PyObject *new_deque, *result; int rv; @@ -579,10 +674,13 @@ deque_concat(dequeobject *deque, PyObject *other) return NULL; } - new_deque = deque_copy((PyObject *)deque, NULL); + new_deque = deque_copy_impl(deque); if (new_deque == NULL) return NULL; - result = deque_extend((dequeobject *)new_deque, other); + + // 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; @@ -591,6 +689,16 @@ deque_concat(dequeobject *deque, PyObject *other) return new_deque; } +static PyObject * +deque_concat(dequeobject *deque, PyObject *other) +{ + PyObject *result; + Py_BEGIN_CRITICAL_SECTION(deque); + result = deque_concat_lock_held(deque, other); + Py_END_CRITICAL_SECTION(); + return result; +} + static int deque_clear(dequeobject *deque) { @@ -668,24 +776,32 @@ deque_clear(dequeobject *deque) alternate_method: while (Py_SIZE(deque)) { - item = deque_pop(deque, NULL); + item = deque_pop_impl(deque); assert (item != NULL); Py_DECREF(item); } return 0; } +/*[clinic input] +@critical_section +_collections.deque.clear as deque_clearmethod + + deque: dequeobject + +Remove all elements from the deque. +[clinic start generated code]*/ + static PyObject * -deque_clearmethod(dequeobject *deque, PyObject *Py_UNUSED(ignored)) +deque_clearmethod_impl(dequeobject *deque) +/*[clinic end generated code: output=79b2513e097615c1 input=3a22e9605d20c5e9]*/ { deque_clear(deque); Py_RETURN_NONE; } -PyDoc_STRVAR(clear_doc, "Remove all elements from the deque."); - static PyObject * -deque_inplace_repeat(dequeobject *deque, Py_ssize_t n) +deque_inplace_repeat_lock_held(dequeobject *deque, Py_ssize_t n) { Py_ssize_t i, m, size; PyObject *seq; @@ -749,7 +865,7 @@ deque_inplace_repeat(dequeobject *deque, Py_ssize_t n) n = (deque->maxlen + size - 1) / size; for (i = 0 ; i < n-1 ; i++) { - rv = deque_extend(deque, seq); + rv = deque_extend_impl(deque, seq); if (rv == NULL) { Py_DECREF(seq); return NULL; @@ -762,15 +878,29 @@ deque_inplace_repeat(dequeobject *deque, Py_ssize_t n) } static PyObject * +deque_inplace_repeat(dequeobject *deque, Py_ssize_t n) +{ + 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(dequeobject *deque, Py_ssize_t n) { dequeobject *new_deque; PyObject *rv; - new_deque = (dequeobject *)deque_copy((PyObject *) deque, NULL); + Py_BEGIN_CRITICAL_SECTION(deque); + new_deque = (dequeobject *)deque_copy_impl(deque); + Py_END_CRITICAL_SECTION(); if (new_deque == NULL) return NULL; - rv = deque_inplace_repeat(new_deque, n); + // 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; } @@ -924,36 +1054,38 @@ done: return rv; } -static PyObject * -deque_rotate(dequeobject *deque, PyObject *const *args, Py_ssize_t nargs) -{ - Py_ssize_t n=1; +/*[clinic input] +@critical_section +_collections.deque.rotate as deque_rotate - if (!_PyArg_CheckPositional("deque.rotate", nargs, 0, 1)) { - return NULL; - } - if (nargs) { - PyObject *index = _PyNumber_Index(args[0]); - if (index == NULL) { - return NULL; - } - n = PyLong_AsSsize_t(index); - Py_DECREF(index); - if (n == -1 && PyErr_Occurred()) { - return NULL; - } - } + deque: dequeobject + n: Py_ssize_t = 1 + / + +Rotate the deque n steps to the right. If n is negative, rotates left. +[clinic start generated code]*/ +static PyObject * +deque_rotate_impl(dequeobject *deque, Py_ssize_t n) +/*[clinic end generated code: output=96c2402a371eb15d input=5bf834296246e002]*/ +{ if (!_deque_rotate(deque, n)) Py_RETURN_NONE; return NULL; } -PyDoc_STRVAR(rotate_doc, -"Rotate the deque n steps to the right (default n=1). If n is negative, rotates left."); +/*[clinic input] +@critical_section +_collections.deque.reverse as deque_reverse + + deque: dequeobject + +Reverse *IN PLACE*. +[clinic start generated code]*/ static PyObject * -deque_reverse(dequeobject *deque, PyObject *unused) +deque_reverse_impl(dequeobject *deque) +/*[clinic end generated code: output=bdeebc2cf8c1f064 input=26f4167fd623027f]*/ { block *leftblock = deque->leftblock; block *rightblock = deque->rightblock; @@ -990,11 +1122,20 @@ deque_reverse(dequeobject *deque, PyObject *unused) Py_RETURN_NONE; } -PyDoc_STRVAR(reverse_doc, -"D.reverse() -- reverse *IN PLACE*"); +/*[clinic input] +@critical_section +_collections.deque.count as deque_count + + deque: dequeobject + value as v: object + / + +Return number of occurrences of value. +[clinic start generated code]*/ static PyObject * -deque_count(dequeobject *deque, PyObject *v) +deque_count_impl(dequeobject *deque, PyObject *v) +/*[clinic end generated code: output=2ca26c49b6ab0400 input=4ef67ef2b34dc1fc]*/ { block *b = deque->leftblock; Py_ssize_t index = deque->leftindex; @@ -1029,11 +1170,8 @@ deque_count(dequeobject *deque, PyObject *v) return PyLong_FromSsize_t(count); } -PyDoc_STRVAR(count_doc, -"D.count(value) -- return number of occurrences of value"); - static int -deque_contains(dequeobject *deque, PyObject *v) +deque_contains_lock_held(dequeobject *deque, PyObject *v) { block *b = deque->leftblock; Py_ssize_t index = deque->leftindex; @@ -1064,28 +1202,50 @@ deque_contains(dequeobject *deque, PyObject *v) return 0; } +static int +deque_contains(dequeobject *deque, PyObject *v) +{ + int result; + Py_BEGIN_CRITICAL_SECTION(deque); + result = deque_contains_lock_held(deque, v); + Py_END_CRITICAL_SECTION(); + return result; +} + static Py_ssize_t deque_len(dequeobject *deque) { - return Py_SIZE(deque); + return FT_ATOMIC_LOAD_SSIZE(((PyVarObject *)deque)->ob_size); } +/*[clinic input] +@critical_section +@text_signature "($self, value, [start, [stop]])" +_collections.deque.index as deque_index + + deque: dequeobject + value as v: object + start: object(converter='_PyEval_SliceIndexNotNone', type='Py_ssize_t', c_default='0') = NULL + stop: object(converter='_PyEval_SliceIndexNotNone', type='Py_ssize_t', c_default='Py_SIZE(deque)') = NULL + / + +Return first index of value. + +Raises ValueError if the value is not present. +[clinic start generated code]*/ + static PyObject * -deque_index(dequeobject *deque, PyObject *const *args, Py_ssize_t nargs) +deque_index_impl(dequeobject *deque, PyObject *v, Py_ssize_t start, + Py_ssize_t stop) +/*[clinic end generated code: output=df45132753175ef9 input=90f48833a91e1743]*/ { - Py_ssize_t i, n, start=0, stop=Py_SIZE(deque); - PyObject *v, *item; + Py_ssize_t i, n; + PyObject *item; block *b = deque->leftblock; Py_ssize_t index = deque->leftindex; size_t start_state = deque->state; int cmp; - if (!_PyArg_ParseStack(args, nargs, "O|O&O&:index", &v, - _PyEval_SliceIndexNotNone, &start, - _PyEval_SliceIndexNotNone, &stop)) { - return NULL; - } - if (start < 0) { start += Py_SIZE(deque); if (start < 0) @@ -1138,10 +1298,6 @@ deque_index(dequeobject *deque, PyObject *const *args, Py_ssize_t nargs) return NULL; } -PyDoc_STRVAR(index_doc, -"D.index(value, [start, [stop]]) -- return first index of value.\n" -"Raises ValueError if the value is not present."); - /* insert(), remove(), and delitem() are implemented in terms of rotate() for simplicity and reasonable performance near the end points. If for some reason these methods become popular, it is not @@ -1150,32 +1306,39 @@ PyDoc_STRVAR(index_doc, boost (by moving each pointer only once instead of twice). */ +/*[clinic input] +@critical_section +_collections.deque.insert as deque_insert + + deque: dequeobject + index: Py_ssize_t + value: object + / + +Insert value before index. +[clinic start generated code]*/ + static PyObject * -deque_insert(dequeobject *deque, PyObject *const *args, Py_ssize_t nargs) +deque_insert_impl(dequeobject *deque, Py_ssize_t index, PyObject *value) +/*[clinic end generated code: output=ef4d2c15d5532b80 input=dbee706586cc9cde]*/ { - Py_ssize_t index; Py_ssize_t n = Py_SIZE(deque); - PyObject *value; PyObject *rv; - if (!_PyArg_ParseStack(args, nargs, "nO:insert", &index, &value)) { - return NULL; - } - if (deque->maxlen == Py_SIZE(deque)) { PyErr_SetString(PyExc_IndexError, "deque already at its maximum size"); return NULL; } if (index >= n) - return deque_append(deque, value); + return deque_append_impl(deque, value); if (index <= -n || index == 0) - return deque_appendleft(deque, value); + return deque_appendleft_impl(deque, value); if (_deque_rotate(deque, -index)) return NULL; if (index < 0) - rv = deque_append(deque, value); + rv = deque_append_impl(deque, value); else - rv = deque_appendleft(deque, value); + rv = deque_appendleft_impl(deque, value); if (rv == NULL) return NULL; Py_DECREF(rv); @@ -1184,12 +1347,6 @@ deque_insert(dequeobject *deque, PyObject *const *args, Py_ssize_t nargs) Py_RETURN_NONE; } -PyDoc_STRVAR(insert_doc, -"D.insert(index, object) -- insert object before index"); - -PyDoc_STRVAR(remove_doc, -"D.remove(value) -- remove first occurrence of value."); - static int valid_index(Py_ssize_t i, Py_ssize_t limit) { @@ -1199,7 +1356,7 @@ valid_index(Py_ssize_t i, Py_ssize_t limit) } static PyObject * -deque_item(dequeobject *deque, Py_ssize_t i) +deque_item_lock_held(dequeobject *deque, Py_ssize_t i) { block *b; PyObject *item; @@ -1237,6 +1394,16 @@ deque_item(dequeobject *deque, Py_ssize_t i) return Py_NewRef(item); } +static PyObject * +deque_item(dequeobject *deque, Py_ssize_t i) +{ + PyObject *result; + Py_BEGIN_CRITICAL_SECTION(deque); + result = deque_item_lock_held(deque, i); + Py_END_CRITICAL_SECTION(); + return result; +} + static int deque_del_item(dequeobject *deque, Py_ssize_t i) { @@ -1246,15 +1413,27 @@ deque_del_item(dequeobject *deque, Py_ssize_t i) assert (i >= 0 && i < Py_SIZE(deque)); if (_deque_rotate(deque, -i)) return -1; - item = deque_popleft(deque, NULL); + item = deque_popleft_impl(deque); rv = _deque_rotate(deque, i); assert (item != NULL); Py_DECREF(item); return rv; } +/*[clinic input] +@critical_section +_collections.deque.remove as deque_remove + + deque: dequeobject + value: object + / + +Remove first occurrence of value. +[clinic start generated code]*/ + static PyObject * -deque_remove(dequeobject *deque, PyObject *value) +deque_remove_impl(dequeobject *deque, PyObject *value) +/*[clinic end generated code: output=54cff28b8ef78c5b input=60eb3f8aa4de532a]*/ { PyObject *item; block *b = deque->leftblock; @@ -1295,7 +1474,7 @@ deque_remove(dequeobject *deque, PyObject *value) } static int -deque_ass_item(dequeobject *deque, Py_ssize_t i, PyObject *v) +deque_ass_item_lock_held(dequeobject *deque, Py_ssize_t i, PyObject *v) { block *b; Py_ssize_t n, len=Py_SIZE(deque), halflen=(len+1)>>1, index=i; @@ -1326,6 +1505,16 @@ deque_ass_item(dequeobject *deque, Py_ssize_t i, PyObject *v) return 0; } +static int +deque_ass_item(dequeobject *deque, Py_ssize_t i, PyObject *v) +{ + int result; + Py_BEGIN_CRITICAL_SECTION(deque); + result = deque_ass_item_lock_held(deque, i, v); + Py_END_CRITICAL_SECTION(); + return result; +} + static void deque_dealloc(dequeobject *deque) { @@ -1333,8 +1522,7 @@ deque_dealloc(dequeobject *deque) Py_ssize_t i; PyObject_GC_UnTrack(deque); - if (deque->weakreflist != NULL) - PyObject_ClearWeakRefs((PyObject *) deque); + FT_CLEAR_WEAKREFS((PyObject*)deque, deque->weakreflist); if (deque->leftblock != NULL) { deque_clear(deque); assert(deque->leftblock != NULL); @@ -1375,8 +1563,17 @@ deque_traverse(dequeobject *deque, visitproc visit, void *arg) return 0; } +/*[clinic input] +_collections.deque.__reduce__ as deque___reduce__ + + deque: dequeobject + +Return state information for pickling. +[clinic start generated code]*/ + static PyObject * -deque_reduce(dequeobject *deque, PyObject *Py_UNUSED(ignored)) +deque___reduce___impl(dequeobject *deque) +/*[clinic end generated code: output=cb85d9e0b7d2c5ad input=991a933a5bc7a526]*/ { PyObject *state, *it; @@ -1391,6 +1588,8 @@ deque_reduce(dequeobject *deque, PyObject *Py_UNUSED(ignored)) return NULL; } + // It's safe to access deque->maxlen here without holding the per object + // lock for deque; deque->maxlen is only assigned during construction. if (deque->maxlen < 0) { return Py_BuildValue("O()NN", Py_TYPE(deque), state, it); } @@ -1510,26 +1709,23 @@ done: return NULL; } +/*[clinic input] +@critical_section +@text_signature "([iterable[, maxlen]])" +_collections.deque.__init__ as deque_init + + deque: dequeobject + iterable: object = NULL + maxlen as maxlenobj: object = NULL + +A list-like sequence optimized for data accesses near its endpoints. +[clinic start generated code]*/ + static int -deque_init(dequeobject *deque, PyObject *args, PyObject *kwdargs) +deque_init_impl(dequeobject *deque, PyObject *iterable, PyObject *maxlenobj) +/*[clinic end generated code: output=7084a39d71218dcd input=2b9e37af1fd73143]*/ { - PyObject *iterable = NULL; - PyObject *maxlenobj = NULL; Py_ssize_t maxlen = -1; - char *kwlist[] = {"iterable", "maxlen", 0}; - - if (kwdargs == NULL && PyTuple_GET_SIZE(args) <= 2) { - if (PyTuple_GET_SIZE(args) > 0) { - iterable = PyTuple_GET_ITEM(args, 0); - } - if (PyTuple_GET_SIZE(args) > 1) { - maxlenobj = PyTuple_GET_ITEM(args, 1); - } - } else { - if (!PyArg_ParseTupleAndKeywords(args, kwdargs, "|OO:deque", kwlist, - &iterable, &maxlenobj)) - return -1; - } if (maxlenobj != NULL && maxlenobj != Py_None) { maxlen = PyLong_AsSsize_t(maxlenobj); if (maxlen == -1 && PyErr_Occurred()) @@ -1543,7 +1739,7 @@ deque_init(dequeobject *deque, PyObject *args, PyObject *kwdargs) if (Py_SIZE(deque) > 0) deque_clear(deque); if (iterable != NULL) { - PyObject *rv = deque_extend(deque, iterable); + PyObject *rv = deque_extend_impl(deque, iterable); if (rv == NULL) return -1; Py_DECREF(rv); @@ -1551,8 +1747,18 @@ deque_init(dequeobject *deque, PyObject *args, PyObject *kwdargs) return 0; } +/*[clinic input] +@critical_section +_collections.deque.__sizeof__ as deque___sizeof__ + + deque: dequeobject + +Return the size of the deque in memory, in bytes. +[clinic start generated code]*/ + static PyObject * -deque_sizeof(dequeobject *deque, void *unused) +deque___sizeof___impl(dequeobject *deque) +/*[clinic end generated code: output=4d36e9fb4f30bbaf input=762312f2d4813535]*/ { size_t res = _PyObject_SIZE(Py_TYPE(deque)); size_t blocks; @@ -1563,9 +1769,6 @@ deque_sizeof(dequeobject *deque, void *unused) return PyLong_FromSize_t(res); } -PyDoc_STRVAR(sizeof_doc, -"D.__sizeof__() -- size of D in memory, in bytes"); - static PyObject * deque_get_maxlen(dequeobject *deque, void *Py_UNUSED(ignored)) { @@ -1574,6 +1777,22 @@ deque_get_maxlen(dequeobject *deque, void *Py_UNUSED(ignored)) return PyLong_FromSsize_t(deque->maxlen); } +static PyObject *deque_reviter(dequeobject *deque); + +/*[clinic input] +_collections.deque.__reversed__ as deque___reversed__ + + deque: dequeobject + +Return a reverse iterator over the deque. +[clinic start generated code]*/ + +static PyObject * +deque___reversed___impl(dequeobject *deque) +/*[clinic end generated code: output=3e7e7e715883cf2e input=3d494c25a6fe5c7e]*/ +{ + return deque_reviter(deque); +} /* deque object ********************************************************/ @@ -1584,68 +1803,42 @@ static PyGetSetDef deque_getset[] = { }; static PyObject *deque_iter(dequeobject *deque); -static PyObject *deque_reviter(dequeobject *deque, PyObject *Py_UNUSED(ignored)); -PyDoc_STRVAR(reversed_doc, - "D.__reversed__() -- return a reverse iterator over the deque"); static PyMethodDef deque_methods[] = { - {"append", (PyCFunction)deque_append, - METH_O, append_doc}, - {"appendleft", (PyCFunction)deque_appendleft, - METH_O, appendleft_doc}, - {"clear", (PyCFunction)deque_clearmethod, - METH_NOARGS, clear_doc}, - {"__copy__", deque_copy, - METH_NOARGS, copy_doc}, - {"copy", deque_copy, - METH_NOARGS, copy_doc}, - {"count", (PyCFunction)deque_count, - METH_O, count_doc}, - {"extend", (PyCFunction)deque_extend, - METH_O, extend_doc}, - {"extendleft", (PyCFunction)deque_extendleft, - METH_O, extendleft_doc}, - {"index", _PyCFunction_CAST(deque_index), - METH_FASTCALL, index_doc}, - {"insert", _PyCFunction_CAST(deque_insert), - METH_FASTCALL, insert_doc}, - {"pop", (PyCFunction)deque_pop, - METH_NOARGS, pop_doc}, - {"popleft", (PyCFunction)deque_popleft, - METH_NOARGS, popleft_doc}, - {"__reduce__", (PyCFunction)deque_reduce, - METH_NOARGS, reduce_doc}, - {"remove", (PyCFunction)deque_remove, - METH_O, remove_doc}, - {"__reversed__", (PyCFunction)deque_reviter, - METH_NOARGS, reversed_doc}, - {"reverse", (PyCFunction)deque_reverse, - METH_NOARGS, reverse_doc}, - {"rotate", _PyCFunction_CAST(deque_rotate), - METH_FASTCALL, rotate_doc}, - {"__sizeof__", (PyCFunction)deque_sizeof, - METH_NOARGS, sizeof_doc}, + DEQUE_APPEND_METHODDEF + DEQUE_APPENDLEFT_METHODDEF + DEQUE_CLEARMETHOD_METHODDEF + DEQUE___COPY___METHODDEF + DEQUE_COPY_METHODDEF + DEQUE_COUNT_METHODDEF + DEQUE_EXTEND_METHODDEF + DEQUE_EXTENDLEFT_METHODDEF + DEQUE_INDEX_METHODDEF + DEQUE_INSERT_METHODDEF + DEQUE_POP_METHODDEF + DEQUE_POPLEFT_METHODDEF + DEQUE___REDUCE___METHODDEF + DEQUE_REMOVE_METHODDEF + DEQUE___REVERSED___METHODDEF + DEQUE_REVERSE_METHODDEF + DEQUE_ROTATE_METHODDEF + DEQUE___SIZEOF___METHODDEF {"__class_getitem__", Py_GenericAlias, METH_O|METH_CLASS, PyDoc_STR("See PEP 585")}, {NULL, NULL} /* sentinel */ }; static PyMemberDef deque_members[] = { - {"__weaklistoffset__", T_PYSSIZET, offsetof(dequeobject, weakreflist), READONLY}, + {"__weaklistoffset__", Py_T_PYSSIZET, offsetof(dequeobject, weakreflist), Py_READONLY}, {NULL}, }; -PyDoc_STRVAR(deque_doc, -"deque([iterable[, maxlen]]) --> deque object\n\ -\n\ -A list-like sequence optimized for data accesses near its endpoints."); - static PyType_Slot deque_slots[] = { {Py_tp_dealloc, deque_dealloc}, {Py_tp_repr, deque_repr}, {Py_tp_hash, PyObject_HashNotImplemented}, {Py_tp_getattro, PyObject_GenericGetAttr}, - {Py_tp_doc, (void *)deque_doc}, + {Py_tp_doc, (void *)deque_init__doc__}, {Py_tp_traverse, deque_traverse}, {Py_tp_clear, deque_clear}, {Py_tp_richcompare, deque_richcompare}, @@ -1699,11 +1892,13 @@ deque_iter(dequeobject *deque) it = PyObject_GC_New(dequeiterobject, state->dequeiter_type); if (it == NULL) return NULL; + Py_BEGIN_CRITICAL_SECTION(deque); it->b = deque->leftblock; it->index = deque->leftindex; it->deque = (dequeobject*)Py_NewRef(deque); it->state = deque->state; it->counter = Py_SIZE(deque); + Py_END_CRITICAL_SECTION(); PyObject_GC_Track(it); return (PyObject *)it; } @@ -1735,7 +1930,7 @@ dequeiter_dealloc(dequeiterobject *dio) } static PyObject * -dequeiter_next(dequeiterobject *it) +dequeiter_next_lock_held(dequeiterobject *it, dequeobject *deque) { PyObject *item; @@ -1762,6 +1957,20 @@ dequeiter_next(dequeiterobject *it) } static PyObject * +dequeiter_next(dequeiterobject *it) +{ + PyObject *result; + // It's safe to access it->deque without holding the per-object lock for it + // here; it->deque is only assigned during construction of it. + dequeobject *deque = it->deque; + Py_BEGIN_CRITICAL_SECTION2(it, deque); + result = dequeiter_next_lock_held(it, deque); + Py_END_CRITICAL_SECTION2(); + + return result; +} + +static PyObject * dequeiter_new(PyTypeObject *type, PyObject *args, PyObject *kwds) { Py_ssize_t i, index=0; @@ -1781,6 +1990,11 @@ dequeiter_new(PyTypeObject *type, PyObject *args, PyObject *kwds) if (item) { Py_DECREF(item); } else { + /* + * It's safe to read directly from it without acquiring the + * per-object lock; the iterator isn't visible to any other threads + * yet. + */ if (it->counter) { Py_DECREF(it); return NULL; @@ -1794,7 +2008,8 @@ dequeiter_new(PyTypeObject *type, PyObject *args, PyObject *kwds) static PyObject * dequeiter_len(dequeiterobject *it, PyObject *Py_UNUSED(ignored)) { - return PyLong_FromSsize_t(it->counter); + Py_ssize_t len = FT_ATOMIC_LOAD_SSIZE(it->counter); + return PyLong_FromSsize_t(len); } PyDoc_STRVAR(length_hint_doc, "Private method returning an estimate of len(list(it))."); @@ -1802,7 +2017,16 @@ PyDoc_STRVAR(length_hint_doc, "Private method returning an estimate of len(list( static PyObject * dequeiter_reduce(dequeiterobject *it, PyObject *Py_UNUSED(ignored)) { - return Py_BuildValue("O(On)", Py_TYPE(it), it->deque, Py_SIZE(it->deque) - it->counter); + PyTypeObject *ty = Py_TYPE(it); + // It's safe to access it->deque without holding the per-object lock for it + // here; it->deque is only assigned during construction of it. + dequeobject *deque = it->deque; + Py_ssize_t size, counter; + Py_BEGIN_CRITICAL_SECTION2(it, deque); + size = Py_SIZE(deque); + counter = it->counter; + Py_END_CRITICAL_SECTION2(); + return Py_BuildValue("O(On)", ty, deque, size - counter); } static PyMethodDef dequeiter_methods[] = { @@ -1834,7 +2058,7 @@ static PyType_Spec dequeiter_spec = { /*********************** Deque Reverse Iterator **************************/ static PyObject * -deque_reviter(dequeobject *deque, PyObject *Py_UNUSED(ignored)) +deque_reviter(dequeobject *deque) { dequeiterobject *it; collections_state *state = find_module_state_by_def(Py_TYPE(deque)); @@ -1842,17 +2066,19 @@ deque_reviter(dequeobject *deque, PyObject *Py_UNUSED(ignored)) it = PyObject_GC_New(dequeiterobject, state->dequereviter_type); if (it == NULL) return NULL; + Py_BEGIN_CRITICAL_SECTION(deque); it->b = deque->rightblock; it->index = deque->rightindex; it->deque = (dequeobject*)Py_NewRef(deque); it->state = deque->state; it->counter = Py_SIZE(deque); + Py_END_CRITICAL_SECTION(); PyObject_GC_Track(it); return (PyObject *)it; } static PyObject * -dequereviter_next(dequeiterobject *it) +dequereviter_next_lock_held(dequeiterobject *it, dequeobject *deque) { PyObject *item; if (it->counter == 0) @@ -1879,6 +2105,19 @@ dequereviter_next(dequeiterobject *it) } static PyObject * +dequereviter_next(dequeiterobject *it) +{ + PyObject *item; + // It's safe to access it->deque without holding the per-object lock for it + // here; it->deque is only assigned during construction of it. + dequeobject *deque = it->deque; + Py_BEGIN_CRITICAL_SECTION2(it, deque); + item = dequereviter_next_lock_held(it, deque); + Py_END_CRITICAL_SECTION2(); + return item; +} + +static PyObject * dequereviter_new(PyTypeObject *type, PyObject *args, PyObject *kwds) { Py_ssize_t i, index=0; @@ -1889,7 +2128,7 @@ dequereviter_new(PyTypeObject *type, PyObject *args, PyObject *kwds) return NULL; assert(type == state->dequereviter_type); - it = (dequeiterobject*)deque_reviter((dequeobject *)deque, NULL); + it = (dequeiterobject *)deque_reviter((dequeobject *)deque); if (!it) return NULL; /* consume items from the queue */ @@ -1898,6 +2137,11 @@ dequereviter_new(PyTypeObject *type, PyObject *args, PyObject *kwds) if (item) { Py_DECREF(item); } else { + /* + * It's safe to read directly from it without acquiring the + * per-object lock; the iterator isn't visible to any other threads + * yet. + */ if (it->counter) { Py_DECREF(it); return NULL; @@ -1959,11 +2203,11 @@ defdict_missing(defdictobject *dd, PyObject *key) value = _PyObject_CallNoArgs(factory); if (value == NULL) return value; - if (PyObject_SetItem((PyObject *)dd, key, value) < 0) { - Py_DECREF(value); - return NULL; - } - return value; + PyObject *result = NULL; + (void)PyDict_SetDefaultRef((PyObject *)dd, key, value, &result); + // 'result' is NULL, or a strong reference to 'value' or 'dd[key]' + Py_DECREF(value); + return result; } static inline PyObject* @@ -2055,7 +2299,7 @@ static PyMethodDef defdict_methods[] = { }; static PyMemberDef defdict_members[] = { - {"default_factory", T_OBJECT, + {"default_factory", _Py_T_OBJECT, offsetof(defdictobject, default_factory), 0, PyDoc_STR("Factory for default value called by __missing__().")}, {NULL} @@ -2093,9 +2337,10 @@ defdict_repr(defdictobject *dd) } defrepr = PyUnicode_FromString("..."); } - else + else { defrepr = PyObject_Repr(dd->default_factory); - Py_ReprLeave(dd->default_factory); + Py_ReprLeave(dd->default_factory); + } } if (defrepr == NULL) { Py_DECREF(baserepr); @@ -2267,9 +2512,9 @@ _collections__count_elements_impl(PyObject *module, PyObject *mapping, /* Only take the fast path when get() and __setitem__() * have not been overridden. */ - mapping_get = _PyType_Lookup(Py_TYPE(mapping), &_Py_ID(get)); + mapping_get = _PyType_LookupRef(Py_TYPE(mapping), &_Py_ID(get)); dict_get = _PyType_Lookup(&PyDict_Type, &_Py_ID(get)); - mapping_setitem = _PyType_Lookup(Py_TYPE(mapping), &_Py_ID(__setitem__)); + mapping_setitem = _PyType_LookupRef(Py_TYPE(mapping), &_Py_ID(__setitem__)); dict_setitem = _PyType_Lookup(&PyDict_Type, &_Py_ID(__setitem__)); if (mapping_get != NULL && mapping_get == dict_get && @@ -2293,12 +2538,9 @@ _collections__count_elements_impl(PyObject *module, PyObject *mapping, if (key == NULL) break; - if (!PyUnicode_CheckExact(key) || - (hash = _PyASCIIObject_CAST(key)->hash) == -1) - { - hash = PyObject_Hash(key); - if (hash == -1) - goto done; + hash = _PyObject_HashFast(key); + if (hash == -1) { + goto done; } oldval = _PyDict_GetItem_KnownHash(mapping, key, hash); @@ -2308,7 +2550,12 @@ _collections__count_elements_impl(PyObject *module, PyObject *mapping, if (_PyDict_SetItem_KnownHash(mapping, key, one, hash) < 0) goto done; } else { + /* oldval is a borrowed reference. Keep it alive across + PyNumber_Add(), which can execute arbitrary user code and + mutate (or even clear) the underlying dict. */ + Py_INCREF(oldval); newval = PyNumber_Add(oldval, one); + Py_DECREF(oldval); if (newval == NULL) goto done; if (_PyDict_SetItem_KnownHash(mapping, key, newval, hash) < 0) @@ -2343,6 +2590,8 @@ _collections__count_elements_impl(PyObject *module, PyObject *mapping, } done: + Py_XDECREF(mapping_get); + Py_XDECREF(mapping_setitem); Py_DECREF(it); Py_XDECREF(key); Py_XDECREF(newval); @@ -2467,7 +2716,7 @@ tuplegetter_repr(_tuplegetterobject *self) static PyMemberDef tuplegetter_members[] = { - {"__doc__", T_OBJECT, offsetof(_tuplegetterobject, doc), 0}, + {"__doc__", _Py_T_OBJECT, offsetof(_tuplegetterobject, doc), 0}, {0} }; @@ -2573,6 +2822,7 @@ collections_exec(PyObject *module) { static struct PyModuleDef_Slot collections_slots[] = { {Py_mod_exec, collections_exec}, {Py_mod_multiple_interpreters, Py_MOD_PER_INTERPRETER_GIL_SUPPORTED}, + {Py_mod_gil, Py_MOD_GIL_NOT_USED}, {0, NULL} }; |