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.

1 files changed, 101 insertions, 85 deletions

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 @@ typedef struct {
 	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 @@ deque_new(PyTypeObject *type, PyObject *args, PyObject *kwds)
 	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_new(PyTypeObject *type, PyObject *args, PyObject *kwds)
 	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 @@ deque_popleft(dequeobject *deque, PyObject *unused)
 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_extend(dequeobject *deque, PyObject *iterable)
 		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_extendleft(dequeobject *deque, PyObject *iterable)
 		deque->len++;
 		deque->leftindex--;
 		deque->leftblock->data[deque->leftindex] = item;
+		TRIM(deque, deque_pop);               
 	}
 	Py_DECREF(it);
 	if (PyErr_Occurred())
@@ -579,8 +598,8 @@ deque_nohash(PyObject *self)
 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 @@ PyDoc_STRVAR(copy_doc, "Return a shallow copy of a deque.");
 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 @@ PyDoc_STRVAR(reduce_doc, "Return state information for pickling.");
 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 @@ deque_repr(PyObject *deque)
 		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 @@ deque_tp_print(PyObject *deque, FILE *fp, int flags)
 	if (i != 0) {
 		if (i < 0)
 			return i;
-		Py_BEGIN_ALLOW_THREADS
 		fputs("[...]", fp);
-		Py_END_ALLOW_THREADS
 		return 0;
 	}
 
@@ -662,13 +683,9 @@ deque_tp_print(PyObject *deque, FILE *fp, int flags)
 	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 @@ deque_tp_print(PyObject *deque, FILE *fp, int flags)
 	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 @@ done:
 }
 
 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 @@ static PyMethodDef deque_methods[] = {
 };
 
 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 @@ static int
 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;
 }