Optimize reversed(list) using a custom iterator.

2 files changed, 98 insertions, 4 deletions

diff --git a/Objects/enumobject.c b/Objects/enumobject.c
index 998e381..8b2e6e1 100644
--- a/Objects/enumobject.c
+++ b/Objects/enumobject.c
@@ -174,8 +174,8 @@ reversed_new(PyTypeObject *type, PyObject *args, PyObject *kwds)
 	if (!PyArg_UnpackTuple(args, "reversed", 1, 1, &seq))
 		return NULL;
 
-	/* Special case optimization for xrange */
-	if (PyRange_Check(seq))
+	/* Special case optimization for xrange and lists */
+	if (PyRange_Check(seq) || PyList_Check(seq))
 		return PyObject_CallMethod(seq, "__reversed__", NULL);
 
 	if (!PySequence_Check(seq)) {
diff --git a/Objects/listobject.c b/Objects/listobject.c
index fd98b63..cf00ab2 100644
--- a/Objects/listobject.c
+++ b/Objects/listobject.c
@@ -2349,6 +2349,11 @@ list_nohash(PyObject *self)
 	return -1;
 }
 
+static PyObject *list_iter(PyObject *seq);
+static PyObject *list_reversed(PyListObject* seq, PyObject* unused);
+
+PyDoc_STRVAR(reversed_doc,
+"L.__reversed__() -- return a reverse iterator over the list");
 PyDoc_STRVAR(append_doc,
 "L.append(object) -- append object to end");
 PyDoc_STRVAR(extend_doc,
@@ -2373,6 +2378,7 @@ PyDoc_STRVAR(sorted_doc,
 cmp(x, y) -> -1, 0, 1");
 
 static PyMethodDef list_methods[] = {
+	{"__reversed__",(PyCFunction)list_reversed, METH_NOARGS, reversed_doc},
 	{"append",	(PyCFunction)listappend,  METH_O, append_doc},
 	{"insert",	(PyCFunction)listinsert,  METH_VARARGS, insert_doc},
 	{"extend",      (PyCFunction)listextend,  METH_O, extend_doc},
@@ -2404,8 +2410,6 @@ PyDoc_STRVAR(list_doc,
 "list() -> new list\n"
 "list(sequence) -> new list initialized from sequence's items");
 
-static PyObject *list_iter(PyObject *seq);
-
 static PyObject *
 list_subscript(PyListObject* self, PyObject* item)
 {
@@ -2760,3 +2764,93 @@ PyTypeObject PyListIter_Type = {
 	0,					/* tp_descr_get */
 	0,					/* tp_descr_set */
 };
+
+/*********************** List Reverse Iterator **************************/
+
+typedef struct {
+	PyObject_HEAD
+	long it_index;
+	PyListObject *it_seq;
+} listreviterobject;
+
+PyTypeObject PyListRevIter_Type;
+
+static PyObject *
+list_reversed(PyListObject *seq, PyObject *unused)
+{
+	listreviterobject *it;
+
+	it = PyObject_GC_New(listreviterobject, &PyListRevIter_Type);
+	if (it == NULL)
+		return NULL;
+	assert(PyList_Check(seq));
+	it->it_index = PyList_GET_SIZE(seq) - 1;
+	Py_INCREF(seq);
+	it->it_seq = seq;
+	PyObject_GC_Track(it);
+	return (PyObject *)it;
+}
+
+static void
+listreviter_dealloc(listreviterobject *it)
+{
+	PyObject_GC_UnTrack(it);
+	Py_XDECREF(it->it_seq);
+	PyObject_GC_Del(it);
+}
+
+static int
+listreviter_traverse(listreviterobject *it, visitproc visit, void *arg)
+{
+	if (it->it_seq == NULL)
+		return 0;
+	return visit((PyObject *)it->it_seq, arg);
+}
+
+static PyObject *
+listreviter_next(listreviterobject *it)
+{
+	PyObject *item = NULL;
+
+	assert(PyList_Check(it->it_seq));
+	if (it->it_index >= 0) {
+		assert(it->it_index < PyList_GET_SIZE(it->it_seq));
+		item = PyList_GET_ITEM(it->it_seq, it->it_index);
+		it->it_index--;
+		Py_INCREF(item);
+	}
+	return item;
+}
+
+PyTypeObject PyListRevIter_Type = {
+	PyObject_HEAD_INIT(&PyType_Type)
+	0,					/* ob_size */
+	"listreverseiterator",			/* tp_name */
+	sizeof(listreviterobject),		/* tp_basicsize */
+	0,					/* tp_itemsize */
+	/* methods */
+	(destructor)listreviter_dealloc,	/* tp_dealloc */
+	0,					/* tp_print */
+	0,					/* tp_getattr */
+	0,					/* tp_setattr */
+	0,					/* tp_compare */
+	0,					/* tp_repr */
+	0,					/* tp_as_number */
+	0,					/* tp_as_sequence */
+	0,					/* tp_as_mapping */
+	0,					/* tp_hash */
+	0,					/* tp_call */
+	0,					/* tp_str */
+	PyObject_GenericGetAttr,		/* tp_getattro */
+	0,					/* tp_setattro */
+	0,					/* tp_as_buffer */
+	Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC,/* tp_flags */
+	0,					/* tp_doc */
+	(traverseproc)listreviter_traverse,	/* tp_traverse */
+	0,					/* tp_clear */
+	0,					/* tp_richcompare */
+	0,					/* tp_weaklistoffset */
+	PyObject_SelfIter,			/* tp_iter */
+	(iternextfunc)listreviter_next,		/* tp_iternext */
+	0,
+};