Add __asdict__() to NamedTuple and refine the docs.
Add maxlen support to deque() and fixup docs.
Partially fix __reduce__(). The None as a third arg was no longer supported.
Still needs work on __reduce__() to handle recursive inputs.
diff --git a/Modules/_collectionsmodule.c b/Modules/_collectionsmodule.c
index ea68f80..33a77b6 100644
--- a/Modules/_collectionsmodule.c
+++ b/Modules/_collectionsmodule.c
@@ -83,10 +83,27 @@
int leftindex; /* in range(BLOCKLEN) */
int rightindex; /* in range(BLOCKLEN) */
int len;
+ int maxlen;
long state; /* incremented whenever the indices move */
PyObject *weakreflist; /* List of weak references */
} dequeobject;
+/* The deque's size limit is d.maxlen. The limit can be zero or positive.
+ * If there is no limit, then d.maxlen == -1.
+ *
+ * After an item is added to a deque, we check to see if the size has grown past
+ * the limit. If it has, we get the size back down to the limit by popping an
+ * item off of the opposite end. The methods that can trigger this are append(),
+ * appendleft(), extend(), and extendleft().
+ */
+
+#define TRIM(d, popfunction) \
+ if (d->maxlen != -1 && d->len > d->maxlen) { \
+ PyObject *rv = popfunction(d, NULL); \
+ assert(rv != NULL && d->len <= d->maxlen); \
+ Py_DECREF(rv); \
+ }
+
static PyTypeObject deque_type;
static PyObject *
@@ -95,9 +112,6 @@
dequeobject *deque;
block *b;
- if (type == &deque_type && !_PyArg_NoKeywords("deque()", kwds))
- return NULL;
-
/* create dequeobject structure */
deque = (dequeobject *)type->tp_alloc(type, 0);
if (deque == NULL)
@@ -117,55 +131,12 @@
deque->len = 0;
deque->state = 0;
deque->weakreflist = NULL;
+ deque->maxlen = -1;
return (PyObject *)deque;
}
static PyObject *
-deque_append(dequeobject *deque, PyObject *item)
-{
- deque->state++;
- if (deque->rightindex == BLOCKLEN-1) {
- block *b = newblock(deque->rightblock, NULL, deque->len);
- if (b == NULL)
- return NULL;
- assert(deque->rightblock->rightlink == NULL);
- deque->rightblock->rightlink = b;
- deque->rightblock = b;
- deque->rightindex = -1;
- }
- Py_INCREF(item);
- deque->len++;
- deque->rightindex++;
- deque->rightblock->data[deque->rightindex] = item;
- Py_RETURN_NONE;
-}
-
-PyDoc_STRVAR(append_doc, "Add an element to the right side of the deque.");
-
-static PyObject *
-deque_appendleft(dequeobject *deque, PyObject *item)
-{
- deque->state++;
- if (deque->leftindex == 0) {
- block *b = newblock(NULL, deque->leftblock, deque->len);
- if (b == NULL)
- return NULL;
- assert(deque->leftblock->leftlink == NULL);
- deque->leftblock->leftlink = b;
- deque->leftblock = b;
- deque->leftindex = BLOCKLEN;
- }
- Py_INCREF(item);
- deque->len++;
- deque->leftindex--;
- deque->leftblock->data[deque->leftindex] = item;
- Py_RETURN_NONE;
-}
-
-PyDoc_STRVAR(appendleft_doc, "Add an element to the left side of the deque.");
-
-static PyObject *
deque_pop(dequeobject *deque, PyObject *unused)
{
PyObject *item;
@@ -240,6 +211,52 @@
PyDoc_STRVAR(popleft_doc, "Remove and return the leftmost element.");
static PyObject *
+deque_append(dequeobject *deque, PyObject *item)
+{
+ deque->state++;
+ if (deque->rightindex == BLOCKLEN-1) {
+ block *b = newblock(deque->rightblock, NULL, deque->len);
+ if (b == NULL)
+ return NULL;
+ assert(deque->rightblock->rightlink == NULL);
+ deque->rightblock->rightlink = b;
+ deque->rightblock = b;
+ deque->rightindex = -1;
+ }
+ Py_INCREF(item);
+ deque->len++;
+ deque->rightindex++;
+ deque->rightblock->data[deque->rightindex] = item;
+ TRIM(deque, deque_popleft);
+ Py_RETURN_NONE;
+}
+
+PyDoc_STRVAR(append_doc, "Add an element to the right side of the deque.");
+
+static PyObject *
+deque_appendleft(dequeobject *deque, PyObject *item)
+{
+ deque->state++;
+ if (deque->leftindex == 0) {
+ block *b = newblock(NULL, deque->leftblock, deque->len);
+ if (b == NULL)
+ return NULL;
+ assert(deque->leftblock->leftlink == NULL);
+ deque->leftblock->leftlink = b;
+ deque->leftblock = b;
+ deque->leftindex = BLOCKLEN;
+ }
+ Py_INCREF(item);
+ deque->len++;
+ deque->leftindex--;
+ deque->leftblock->data[deque->leftindex] = item;
+ TRIM(deque, deque_pop);
+ Py_RETURN_NONE;
+}
+
+PyDoc_STRVAR(appendleft_doc, "Add an element to the left side of the deque.");
+
+static PyObject *
deque_extend(dequeobject *deque, PyObject *iterable)
{
PyObject *it, *item;
@@ -266,6 +283,7 @@
deque->len++;
deque->rightindex++;
deque->rightblock->data[deque->rightindex] = item;
+ TRIM(deque, deque_popleft);
}
Py_DECREF(it);
if (PyErr_Occurred())
@@ -303,6 +321,7 @@
deque->len++;
deque->leftindex--;
deque->leftblock->data[deque->leftindex] = item;
+ TRIM(deque, deque_pop);
}
Py_DECREF(it);
if (PyErr_Occurred())
@@ -579,8 +598,8 @@
static PyObject *
deque_copy(PyObject *deque)
{
- return PyObject_CallFunctionObjArgs((PyObject *)(Py_Type(deque)),
- deque, NULL);
+ return PyObject_CallFunction((PyObject *)(Py_Type(deque)), "Oi",
+ deque, ((dequeobject *)deque)->maxlen, NULL);
}
PyDoc_STRVAR(copy_doc, "Return a shallow copy of a deque.");
@@ -588,21 +607,22 @@
static PyObject *
deque_reduce(dequeobject *deque)
{
- PyObject *dict, *result, *it;
+ PyObject *dict, *result, *aslist;
dict = PyObject_GetAttrString((PyObject *)deque, "__dict__");
- if (dict == NULL) {
+ if (dict == NULL)
PyErr_Clear();
- dict = Py_None;
- Py_INCREF(dict);
- }
- it = PyObject_GetIter((PyObject *)deque);
- if (it == NULL) {
+ aslist = PySequence_List((PyObject *)deque);
+ if (aslist == NULL) {
Py_DECREF(dict);
return NULL;
}
- result = Py_BuildValue("O()ON", Py_Type(deque), dict, it);
- Py_DECREF(dict);
+ if (dict == NULL)
+ result = Py_BuildValue("O(Oi)", Py_Type(deque), aslist, deque->maxlen);
+ else
+ result = Py_BuildValue("O(Oi)O", Py_Type(deque), aslist, deque->maxlen, dict);
+ Py_XDECREF(dict);
+ Py_DECREF(aslist);
return result;
}
@@ -611,7 +631,7 @@
static PyObject *
deque_repr(PyObject *deque)
{
- PyObject *aslist, *result, *fmt;
+ PyObject *aslist, *result, *fmt; /*, *limit; */
int i;
i = Py_ReprEnter(deque);
@@ -626,14 +646,17 @@
Py_ReprLeave(deque);
return NULL;
}
-
- fmt = PyString_FromString("deque(%r)");
+ if (((dequeobject *)deque)->maxlen != -1)
+ fmt = PyString_FromFormat("deque(%%r, maxlen=%i)",
+ ((dequeobject *)deque)->maxlen);
+ else
+ fmt = PyString_FromString("deque(%r)");
if (fmt == NULL) {
Py_DECREF(aslist);
Py_ReprLeave(deque);
return NULL;
}
- result = PyString_Format(fmt, aslist);
+ result = PyString_Format(fmt, aslist);
Py_DECREF(fmt);
Py_DECREF(aslist);
Py_ReprLeave(deque);
@@ -652,9 +675,7 @@
if (i != 0) {
if (i < 0)
return i;
- Py_BEGIN_ALLOW_THREADS
fputs("[...]", fp);
- Py_END_ALLOW_THREADS
return 0;
}
@@ -662,13 +683,9 @@
if (it == NULL)
return -1;
- Py_BEGIN_ALLOW_THREADS
fputs("deque([", fp);
- Py_END_ALLOW_THREADS
while ((item = PyIter_Next(it)) != NULL) {
- Py_BEGIN_ALLOW_THREADS
fputs(emit, fp);
- Py_END_ALLOW_THREADS
emit = separator;
if (PyObject_Print(item, fp, 0) != 0) {
Py_DECREF(item);
@@ -682,9 +699,11 @@
Py_DECREF(it);
if (PyErr_Occurred())
return -1;
- Py_BEGIN_ALLOW_THREADS
- fputs("])", fp);
- Py_END_ALLOW_THREADS
+
+ if (((dequeobject *)deque)->maxlen == -1)
+ fputs("])", fp);
+ else
+ fprintf(fp, "], maxlen=%d)", ((dequeobject *)deque)->maxlen);
return 0;
}
@@ -767,13 +786,19 @@
}
static int
-deque_init(dequeobject *deque, PyObject *args, PyObject *kwds)
+deque_init(dequeobject *deque, PyObject *args, PyObject *kwdargs)
{
PyObject *iterable = NULL;
+ int maxlen = -1;
+ char *kwlist[] = {"iterable", "maxlen", 0};
- if (!PyArg_UnpackTuple(args, "deque", 0, 1, &iterable))
+ if (!PyArg_ParseTupleAndKeywords(args, kwdargs, "|Oi:deque", kwlist, &iterable, &maxlen))
return -1;
-
+ if (maxlen < -1) {
+ PyErr_SetString(PyExc_ValueError, "maxlen must be -1 or greater");
+ return -1;
+ }
+ deque->maxlen = maxlen;
if (iterable != NULL) {
PyObject *rv = deque_extend(deque, iterable);
if (rv == NULL)
@@ -828,7 +853,7 @@
};
PyDoc_STRVAR(deque_doc,
-"deque(iterable) --> deque object\n\
+"deque(iterable[, maxlen]) --> deque object\n\
\n\
Build an ordered collection accessible from endpoints only.");
@@ -1198,24 +1223,15 @@
defdict_print(defdictobject *dd, FILE *fp, int flags)
{
int sts;
- Py_BEGIN_ALLOW_THREADS
fprintf(fp, "defaultdict(");
- Py_END_ALLOW_THREADS
- if (dd->default_factory == NULL) {
- Py_BEGIN_ALLOW_THREADS
+ if (dd->default_factory == NULL)
fprintf(fp, "None");
- Py_END_ALLOW_THREADS
- }
else {
PyObject_Print(dd->default_factory, fp, 0);
}
- Py_BEGIN_ALLOW_THREADS
fprintf(fp, ", ");
- Py_END_ALLOW_THREADS
sts = PyDict_Type.tp_print((PyObject *)dd, fp, 0);
- Py_BEGIN_ALLOW_THREADS
fprintf(fp, ")");
- Py_END_ALLOW_THREADS
return sts;
}