/* List object implementation */
#include "Python.h"
#ifdef STDC_HEADERS
#include
#else
#include /* For size_t */
#endif
/* Ensure ob_item has room for at least newsize elements, and set
* ob_size to newsize. If newsize > ob_size on entry, the content
* of the new slots at exit is undefined heap trash; it's the caller's
* responsiblity to overwrite them with sane values.
* The number of allocated elements may grow, shrink, or stay the same.
* Failure is impossible if newsize = 0) {
Py_XDECREF(op->ob_item[i]);
}
PyMem_FREE(op->ob_item);
}
if (numfree < PyList_MAXFREELIST && PyList_CheckExact(op))
free_list[numfree++] = op;
else
Py_TYPE(op)->tp_free((PyObject *)op);
Py_TRASHCAN_SAFE_END(op)
}
static int
list_print(PyListObject *op, FILE *fp, int flags)
{
int rc;
Py_ssize_t i;
rc = Py_ReprEnter((PyObject*)op);
if (rc != 0) {
if (rc < 0)
return rc;
Py_BEGIN_ALLOW_THREADS
fprintf(fp, "[...]");
Py_END_ALLOW_THREADS
return 0;
}
Py_BEGIN_ALLOW_THREADS
fprintf(fp, "[");
Py_END_ALLOW_THREADS
for (i = 0; i < Py_SIZE(op); i++) {
if (i > 0) {
Py_BEGIN_ALLOW_THREADS
fprintf(fp, ", ");
Py_END_ALLOW_THREADS
}
if (PyObject_Print(op->ob_item[i], fp, 0) != 0) {
Py_ReprLeave((PyObject *)op);
return -1;
}
}
Py_BEGIN_ALLOW_THREADS
fprintf(fp, "]");
Py_END_ALLOW_THREADS
Py_ReprLeave((PyObject *)op);
return 0;
}
static PyObject *
list_repr(PyListObject *v)
{
Py_ssize_t i;
PyObject *s, *temp;
PyObject *pieces = NULL, *result = NULL;
i = Py_ReprEnter((PyObject*)v);
if (i != 0) {
return i > 0 ? PyString_FromString("[...]") : NULL;
}
if (Py_SIZE(v) == 0) {
result = PyString_FromString("[]");
goto Done;
}
pieces = PyList_New(0);
if (pieces == NULL)
goto Done;
/* Do repr() on each element. Note that this may mutate the list,
so must refetch the list size on each iteration. */
for (i = 0; i < Py_SIZE(v); ++i) {
int status;
if (Py_EnterRecursiveCall(" while getting the repr of a list"))
goto Done;
s = PyObject_Repr(v->ob_item[i]);
Py_LeaveRecursiveCall();
if (s == NULL)
goto Done;
status = PyList_Append(pieces, s);
Py_DECREF(s); /* append created a new ref */
if (status < 0)
goto Done;
}
/* Add "[]" decorations to the first and last items. */
assert(PyList_GET_SIZE(pieces) > 0);
s = PyString_FromString("[");
if (s == NULL)
goto Done;
temp = PyList_GET_ITEM(pieces, 0);
PyString_ConcatAndDel(&s, temp);
PyList_SET_ITEM(pieces, 0, s);
if (s == NULL)
goto Done;
s = PyString_FromString("]");
if (s == NULL)
goto Done;
temp = PyList_GET_ITEM(pieces, PyList_GET_SIZE(pieces) - 1);
PyString_ConcatAndDel(&temp, s);
PyList_SET_ITEM(pieces, PyList_GET_SIZE(pieces) - 1, temp);
if (temp == NULL)
goto Done;
/* Paste them all together with ", " between. */
s = PyString_FromString(", ");
if (s == NULL)
goto Done;
result = _PyString_Join(s, pieces);
Py_DECREF(s);
Done:
Py_XDECREF(pieces);
Py_ReprLeave((PyObject *)v);
return result;
}
static Py_ssize_t
list_length(PyListObject *a)
{
return Py_SIZE(a);
}
static int
list_contains(PyListObject *a, PyObject *el)
{
Py_ssize_t i;
int cmp;
for (i = 0, cmp = 0 ; cmp == 0 && i < Py_SIZE(a); ++i)
cmp = PyObject_RichCompareBool(el, PyList_GET_ITEM(a, i),
Py_EQ);
return cmp;
}
static PyObject *
list_item(PyListObject *a, Py_ssize_t i)
{
if (i < 0 || i >= Py_SIZE(a)) {
if (indexerr == NULL)
indexerr = PyString_FromString(
"list index out of range");
PyErr_SetObject(PyExc_IndexError, indexerr);
return NULL;
}
Py_INCREF(a->ob_item[i]);
return a->ob_item[i];
}
static PyObject *
list_slice(PyListObject *a, Py_ssize_t ilow, Py_ssize_t ihigh)
{
PyListObject *np;
PyObject **src, **dest;
Py_ssize_t i, len;
if (ilow < 0)
ilow = 0;
else if (ilow > Py_SIZE(a))
ilow = Py_SIZE(a);
if (ihigh < ilow)
ihigh = ilow;
else if (ihigh > Py_SIZE(a))
ihigh = Py_SIZE(a);
len = ihigh - ilow;
np = (PyListObject *) PyList_New(len);
if (np == NULL)
return NULL;
src = a->ob_item + ilow;
dest = np->ob_item;
for (i = 0; i < len; i++) {
PyObject *v = src[i];
Py_INCREF(v);
dest[i] = v;
}
return (PyObject *)np;
}
PyObject *
PyList_GetSlice(PyObject *a, Py_ssize_t ilow, Py_ssize_t ihigh)
{
if (!PyList_Check(a)) {
PyErr_BadInternalCall();
return NULL;
}
return list_slice((PyListObject *)a, ilow, ihigh);
}
static PyObject *
list_concat(PyListObject *a, PyObject *bb)
{
Py_ssize_t size;
Py_ssize_t i;
PyObject **src, **dest;
PyListObject *np;
if (!PyList_Check(bb)) {
PyErr_Format(PyExc_TypeError,
"can only concatenate list (not \"%.200s\") to list",
bb->ob_type->tp_name);
return NULL;
}
#define b ((PyListObject *)bb)
size = Py_SIZE(a) + Py_SIZE(b);
if (size < 0)
return PyErr_NoMemory();
np = (PyListObject *) PyList_New(size);
if (np == NULL) {
return NULL;
}
src = a->ob_item;
dest = np->ob_item;
for (i = 0; i < Py_SIZE(a); i++) {
PyObject *v = src[i];
Py_INCREF(v);
dest[i] = v;
}
src = b->ob_item;
dest = np->ob_item + Py_SIZE(a);
for (i = 0; i < Py_SIZE(b); i++) {
PyObject *v = src[i];
Py_INCREF(v);
dest[i] = v;
}
return (PyObject *)np;
#undef b
}
static PyObject *
list_repeat(PyListObject *a, Py_ssize_t n)
{
Py_ssize_t i, j;
Py_ssize_t size;
PyListObject *np;
PyObject **p, **items;
PyObject *elem;
if (n < 0)
n = 0;
size = Py_SIZE(a) * n;
if (n && size/n != Py_SIZE(a))
return PyErr_NoMemory();
if (size == 0)
return PyList_New(0);
np = (PyListObject *) PyList_New(size);
if (np == NULL)
return NULL;
items = np->ob_item;
if (Py_SIZE(a) == 1) {
elem = a->ob_item[0];
for (i = 0; i < n; i++) {
items[i] = elem;
Py_INCREF(elem);
}
return (PyObject *) np;
}
p = np->ob_item;
items = a->ob_item;
for (i = 0; i < n; i++) {
for (j = 0; j < Py_SIZE(a); j++) {
*p = items[j];
Py_INCREF(*p);
p++;
}
}
return (PyObject *) np;
}
static int
list_clear(PyListObject *a)
{
Py_ssize_t i;
PyObject **item = a->ob_item;
if (item != NULL) {
/* Because XDECREF can recursively invoke operations on
this list, we make it empty first. */
i = Py_SIZE(a);
Py_SIZE(a) = 0;
a->ob_item = NULL;
a->allocated = 0;
while (--i >= 0) {
Py_XDECREF(item[i]);
}
PyMem_FREE(item);
}
/* Never fails; the return value can be ignored.
Note that there is no guarantee that the list is actually empty
at this point, because XDECREF may have populated it again! */
return 0;
}
/* a[ilow:ihigh] = v if v != NULL.
* del a[ilow:ihigh] if v == NULL.
*
* Special speed gimmick: when v is NULL and ihigh - ilow ob_item + m;
for (i = 0; i < n; i++) {
PyObject *o = src[i];
Py_INCREF(o);
dest[i] = o;
}
Py_DECREF(b);
Py_RETURN_NONE;
}
it = PyObject_GetIter(b);
if (it == NULL)
return NULL;
iternext = *it->ob_type->tp_iternext;
/* Guess a result list size. */
n = _PyObject_LengthHint(b, 8);
if (n == -1) {
Py_DECREF(it);
return NULL;
}
m = Py_SIZE(self);
mn = m + n;
if (mn >= m) {
/* Make room. */
if (list_resize(self, mn) == -1)
goto error;
/* Make the list sane again. */
Py_SIZE(self) = m;
}
/* Else m + n overflowed; on the chance that n lied, and there really
* is enough room, ignore it. If n was telling the truth, we'll
* eventually run out of memory during the loop.
*/
/* Run iterator to exhaustion. */
for (;;) {
PyObject *item = iternext(it);
if (item == NULL) {
if (PyErr_Occurred()) {
if (PyErr_ExceptionMatches(PyExc_StopIteration))
PyErr_Clear();
else
goto error;
}
break;
}
if (Py_SIZE(self) < self->allocated) {
/* steals ref */
PyList_SET_ITEM(self, Py_SIZE(self), item);
++Py_SIZE(self);
}
else {
int status = app1(self, item);
Py_DECREF(item); /* append creates a new ref */
if (status < 0)
goto error;
}
}
/* Cut back result list if initial guess was too large. */
if (Py_SIZE(self) < self->allocated)
list_resize(self, Py_SIZE(self)); /* shrinking can't fail */
Py_DECREF(it);
Py_RETURN_NONE;
error:
Py_DECREF(it);
return NULL;
}
PyObject *
_PyList_Extend(PyListObject *self, PyObject *b)
{
return listextend(self, b);
}
static PyObject *
list_inplace_concat(PyListObject *self, PyObject *other)
{
PyObject *result;
result = listextend(self, other);
if (result == NULL)
return result;
Py_DECREF(result);
Py_INCREF(self);
return (PyObject *)self;
}
static PyObject *
listpop(PyListObject *self, PyObject *args)
{
Py_ssize_t i = -1;
PyObject *v;
int status;
if (!PyArg_ParseTuple(args, "|n:pop", &i))
return NULL;
if (Py_SIZE(self) == 0) {
/* Special-case most common failure cause */
PyErr_SetString(PyExc_IndexError, "pop from empty list");
return NULL;
}
if (i < 0)
i += Py_SIZE(self);
if (i < 0 || i >= Py_SIZE(self)) {
PyErr_SetString(PyExc_IndexError, "pop index out of range");
return NULL;
}
v = self->ob_item[i];
if (i == Py_SIZE(self) - 1) {
status = list_resize(self, Py_SIZE(self) - 1);
assert(status >= 0);
return v; /* and v now owns the reference the list had */
}
Py_INCREF(v);
status = list_ass_slice(self, i, i+1, (PyObject *)NULL);
assert(status >= 0);
/* Use status, so that in a release build compilers don't
* complain about the unused name.
*/
(void) status;
return v;
}
/* Reverse a slice of a list in place, from lo up to (exclusive) hi. */
static void
reverse_slice(PyObject **lo, PyObject **hi)
{
assert(lo && hi);
--hi;
while (lo < hi) {
PyObject *t = *lo;
*lo = *hi;
*hi = t;
++lo;
--hi;
}
}
/* Lots of code for an adaptive, stable, natural mergesort. There are many
* pieces to this algorithm; read listsort.txt for overviews and details.
*/
/* Comparison function. Takes care of calling a user-supplied
* comparison function (any callable Python object), which must not be
* NULL (use the ISLT macro if you don't know, or call PyObject_RichCompareBool
* with Py_LT if you know it's NULL).
* Returns -1 on error, 1 if x < y, 0 if x >= y.
*/
static int
islt(PyObject *x, PyObject *y, PyObject *compare)
{
PyObject *res;
PyObject *args;
Py_ssize_t i;
assert(compare != NULL);
/* Call the user's comparison function and translate the 3-way
* result into true or false (or error).
*/
args = PyTuple_New(2);
if (args == NULL)
return -1;
Py_INCREF(x);
Py_INCREF(y);
PyTuple_SET_ITEM(args, 0, x);
PyTuple_SET_ITEM(args, 1, y);
res = PyObject_Call(compare, args, NULL);
Py_DECREF(args);
if (res == NULL)
return -1;
if (!PyInt_Check(res)) {
PyErr_Format(PyExc_TypeError,
"comparison function must return int, not %.200s",
res->ob_type->tp_name);
Py_DECREF(res);
return -1;
}
i = PyInt_AsLong(res);
Py_DECREF(res);
return i < 0;
}
/* If COMPARE is NULL, calls PyObject_RichCompareBool with Py_LT, else calls
* islt. This avoids a layer of function call in the usual case, and
* sorting does many comparisons.
* Returns -1 on error, 1 if x < y, 0 if x >= y.
*/
#define ISLT(X, Y, COMPARE) ((COMPARE) == NULL ? \
PyObject_RichCompareBool(X, Y, Py_LT) : \
islt(X, Y, COMPARE))
/* Compare X to Y via " item -- remove and return item at index (default last).\n"
"Raises IndexError if list is empty or index is out of range.");
PyDoc_STRVAR(remove_doc,
"L.remove(value) -- remove first occurrence of value.\n"
"Raises ValueError if the value is not present.");
PyDoc_STRVAR(index_doc,
"L.index(value, [start, [stop]]) -> integer -- return first index of value.\n"
"Raises ValueError if the value is not present.");
PyDoc_STRVAR(count_doc,
"L.count(value) -> integer -- return number of occurrences of value");
PyDoc_STRVAR(reverse_doc,
"L.reverse() -- reverse *IN PLACE*");
PyDoc_STRVAR(sort_doc,
"L.sort(cmp=None, key=None, reverse=False) -- stable sort *IN PLACE*;\n\
cmp(x, y) -> -1, 0, 1");
static PyObject *list_subscript(PyListObject*, PyObject*);
static PyMethodDef list_methods[] = {
{"__getitem__", (PyCFunction)list_subscript, METH_O|METH_COEXIST, getitem_doc},
{"__reversed__",(PyCFunction)list_reversed, METH_NOARGS, reversed_doc},
{"__sizeof__", (PyCFunction)list_sizeof, METH_NOARGS, sizeof_doc},
{"append", (PyCFunction)listappend, METH_O, append_doc},
{"insert", (PyCFunction)listinsert, METH_VARARGS, insert_doc},
{"extend", (PyCFunction)listextend, METH_O, extend_doc},
{"pop", (PyCFunction)listpop, METH_VARARGS, pop_doc},
{"remove", (PyCFunction)listremove, METH_O, remove_doc},
{"index", (PyCFunction)listindex, METH_VARARGS, index_doc},
{"count", (PyCFunction)listcount, METH_O, count_doc},
{"reverse", (PyCFunction)listreverse, METH_NOARGS, reverse_doc},
{"sort", (PyCFunction)listsort, METH_VARARGS | METH_KEYWORDS, sort_doc},
{NULL, NULL} /* sentinel */
};
static PySequenceMethods list_as_sequence = {
(lenfunc)list_length, /* sq_length */
(binaryfunc)list_concat, /* sq_concat */
(ssizeargfunc)list_repeat, /* sq_repeat */
(ssizeargfunc)list_item, /* sq_item */
(ssizessizeargfunc)list_slice, /* sq_slice */
(ssizeobjargproc)list_ass_item, /* sq_ass_item */
(ssizessizeobjargproc)list_ass_slice, /* sq_ass_slice */
(objobjproc)list_contains, /* sq_contains */
(binaryfunc)list_inplace_concat, /* sq_inplace_concat */
(ssizeargfunc)list_inplace_repeat, /* sq_inplace_repeat */
};
PyDoc_STRVAR(list_doc,
"list() -> new list\n"
"list(sequence) -> new list initialized from sequence's items");
static PyObject *
list_subscript(PyListObject* self, PyObject* item)
{
if (PyIndex_Check(item)) {
Py_ssize_t i;
i = PyNumber_AsSsize_t(item, PyExc_IndexError);
if (i == -1 && PyErr_Occurred())
return NULL;
if (i < 0)
i += PyList_GET_SIZE(self);
return list_item(self, i);
}
else if (PySlice_Check(item)) {
Py_ssize_t start, stop, step, slicelength, cur, i;
PyObject* result;
PyObject* it;
PyObject **src, **dest;
if (PySlice_GetIndicesEx((PySliceObject*)item, Py_SIZE(self),
&start, &stop, &step, &slicelength) < 0) {
return NULL;
}
if (slicelength ob_item;
dest = ((PyListObject *)result)->ob_item;
for (cur = start, i = 0; i < slicelength;
cur += step, i++) {
it = src[cur];
Py_INCREF(it);
dest[i] = it;
}
return result;
}
}
else {
PyErr_Format(PyExc_TypeError,
"list indices must be integers, not %.200s",
item->ob_type->tp_name);
return NULL;
}
}
static int
list_ass_subscript(PyListObject* self, PyObject* item, PyObject* value)
{
if (PyIndex_Check(item)) {
Py_ssize_t i = PyNumber_AsSsize_t(item, PyExc_IndexError);
if (i == -1 && PyErr_Occurred())
return -1;
if (i < 0)
i += PyList_GET_SIZE(self);
return list_ass_item(self, i, value);
}
else if (PySlice_Check(item)) {
Py_ssize_t start, stop, step, slicelength;
if (PySlice_GetIndicesEx((PySliceObject*)item, Py_SIZE(self),
&start, &stop, &step, &slicelength) < 0) {
return -1;
}
if (step == 1)
return list_ass_slice(self, start, stop, value);
/* Make sure s[5:2] = [..] inserts at the right place:
before 5, not before 2. */
if ((step < 0 && start < stop) ||
(step > 0 && start > stop))
stop = start;
if (value == NULL) {
/* delete slice */
PyObject **garbage;
Py_ssize_t cur, i;
if (slicelength ob_item + cur - i,
self->ob_item + cur + 1,
lim * sizeof(PyObject *));
}
cur = start + slicelength*step;
if (cur < Py_SIZE(self)) {
memmove(self->ob_item + cur - slicelength,
self->ob_item + cur,
(Py_SIZE(self) - cur) *
sizeof(PyObject *));
}
Py_SIZE(self) -= slicelength;
list_resize(self, Py_SIZE(self));
for (i = 0; i < slicelength; i++) {
Py_DECREF(garbage[i]);
}
PyMem_FREE(garbage);
return 0;
}
else {
/* assign slice */
PyObject *ins, *seq;
PyObject **garbage, **seqitems, **selfitems;
Py_ssize_t cur, i;
/* protect against a[::-1] = a */
if (self == (PyListObject*)value) {
seq = list_slice((PyListObject*)value, 0,
PyList_GET_SIZE(value));
}
else {
seq = PySequence_Fast(value,
"must assign iterable "
"to extended slice");
}
if (!seq)
return -1;
if (PySequence_Fast_GET_SIZE(seq) != slicelength) {
PyErr_Format(PyExc_ValueError,
"attempt to assign sequence of "
"size %zd to extended slice of "
"size %zd",
PySequence_Fast_GET_SIZE(seq),
slicelength);
Py_DECREF(seq);
return -1;
}
if (!slicelength) {
Py_DECREF(seq);
return 0;
}
garbage = (PyObject**)
PyMem_MALLOC(slicelength*sizeof(PyObject*));
if (!garbage) {
Py_DECREF(seq);
PyErr_NoMemory();
return -1;
}
selfitems = self->ob_item;
seqitems = PySequence_Fast_ITEMS(seq);
for (cur = start, i = 0; i < slicelength;
cur += step, i++) {
garbage[i] = selfitems[cur];
ins = seqitems[i];
Py_INCREF(ins);
selfitems[cur] = ins;
}
for (i = 0; i < slicelength; i++) {
Py_DECREF(garbage[i]);
}
PyMem_FREE(garbage);
Py_DECREF(seq);
return 0;
}
}
else {
PyErr_Format(PyExc_TypeError,
"list indices must be integers, not %.200s",
item->ob_type->tp_name);
return -1;
}
}
static PyMappingMethods list_as_mapping = {
(lenfunc)list_length,
(binaryfunc)list_subscript,
(objobjargproc)list_ass_subscript
};
PyTypeObject PyList_Type = {
PyVarObject_HEAD_INIT(&PyType_Type, 0)
"list",
sizeof(PyListObject),
0,
(destructor)list_dealloc, /* tp_dealloc */
(printfunc)list_print, /* tp_print */
0, /* tp_getattr */
0, /* tp_setattr */
0, /* tp_compare */
(reprfunc)list_repr, /* tp_repr */
0, /* tp_as_number */
&list_as_sequence, /* tp_as_sequence */
&list_as_mapping, /* tp_as_mapping */
(hashfunc)PyObject_HashNotImplemented, /* 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 |
Py_TPFLAGS_BASETYPE | Py_TPFLAGS_LIST_SUBCLASS, /* tp_flags */
list_doc, /* tp_doc */
(traverseproc)list_traverse, /* tp_traverse */
(inquiry)list_clear, /* tp_clear */
list_richcompare, /* tp_richcompare */
0, /* tp_weaklistoffset */
list_iter, /* tp_iter */
0, /* tp_iternext */
list_methods, /* tp_methods */
0, /* tp_members */
0, /* tp_getset */
0, /* tp_base */
0, /* tp_dict */
0, /* tp_descr_get */
0, /* tp_descr_set */
0, /* tp_dictoffset */
(initproc)list_init, /* tp_init */
PyType_GenericAlloc, /* tp_alloc */
PyType_GenericNew, /* tp_new */
PyObject_GC_Del, /* tp_free */
};
/*********************** List Iterator **************************/
typedef struct {
PyObject_HEAD
long it_index;
PyListObject *it_seq; /* Set to NULL when iterator is exhausted */
} listiterobject;
static PyObject *list_iter(PyObject *);
static void listiter_dealloc(listiterobject *);
static int listiter_traverse(listiterobject *, visitproc, void *);
static PyObject *listiter_next(listiterobject *);
static PyObject *listiter_len(listiterobject *);
PyDoc_STRVAR(length_hint_doc, "Private method returning an estimate of len(list(it)).");
static PyMethodDef listiter_methods[] = {
{"__length_hint__", (PyCFunction)listiter_len, METH_NOARGS, length_hint_doc},
{NULL, NULL} /* sentinel */
};
PyTypeObject PyListIter_Type = {
PyVarObject_HEAD_INIT(&PyType_Type, 0)
"listiterator", /* tp_name */
sizeof(listiterobject), /* tp_basicsize */
0, /* tp_itemsize */
/* methods */
(destructor)listiter_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)listiter_traverse, /* tp_traverse */
0, /* tp_clear */
0, /* tp_richcompare */
0, /* tp_weaklistoffset */
PyObject_SelfIter, /* tp_iter */
(iternextfunc)listiter_next, /* tp_iternext */
listiter_methods, /* tp_methods */
0, /* tp_members */
};
static PyObject *
list_iter(PyObject *seq)
{
listiterobject *it;
if (!PyList_Check(seq)) {
PyErr_BadInternalCall();
return NULL;
}
it = PyObject_GC_New(listiterobject, &PyListIter_Type);
if (it == NULL)
return NULL;
it->it_index = 0;
Py_INCREF(seq);
it->it_seq = (PyListObject *)seq;
_PyObject_GC_TRACK(it);
return (PyObject *)it;
}
static void
listiter_dealloc(listiterobject *it)
{
_PyObject_GC_UNTRACK(it);
Py_XDECREF(it->it_seq);
PyObject_GC_Del(it);
}
static int
listiter_traverse(listiterobject *it, visitproc visit, void *arg)
{
Py_VISIT(it->it_seq);
return 0;
}
static PyObject *
listiter_next(listiterobject *it)
{
PyListObject *seq;
PyObject *item;
assert(it != NULL);
seq = it->it_seq;
if (seq == NULL)
return NULL;
assert(PyList_Check(seq));
if (it->it_index < PyList_GET_SIZE(seq)) {
item = PyList_GET_ITEM(seq, it->it_index);
++it->it_index;
Py_INCREF(item);
return item;
}
Py_DECREF(seq);
it->it_seq = NULL;
return NULL;
}
static PyObject *
listiter_len(listiterobject *it)
{
Py_ssize_t len;
if (it->it_seq) {
len = PyList_GET_SIZE(it->it_seq) - it->it_index;
if (len >= 0)
return PyInt_FromSsize_t(len);
}
return PyInt_FromLong(0);
}
/*********************** List Reverse Iterator **************************/
typedef struct {
PyObject_HEAD
Py_ssize_t it_index;
PyListObject *it_seq; /* Set to NULL when iterator is exhausted */
} listreviterobject;
static PyObject *list_reversed(PyListObject *, PyObject *);
static void listreviter_dealloc(listreviterobject *);
static int listreviter_traverse(listreviterobject *, visitproc, void *);
static PyObject *listreviter_next(listreviterobject *);
static PyObject *listreviter_len(listreviterobject *);
static PyMethodDef listreviter_methods[] = {
{"__length_hint__", (PyCFunction)listreviter_len, METH_NOARGS, length_hint_doc},
{NULL, NULL} /* sentinel */
};
PyTypeObject PyListRevIter_Type = {
PyVarObject_HEAD_INIT(&PyType_Type, 0)
"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 */
listreviter_methods, /* tp_methods */
0,
};
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)
{
Py_VISIT(it->it_seq);
return 0;
}
static PyObject *
listreviter_next(listreviterobject *it)
{
PyObject *item;
Py_ssize_t index = it->it_index;
PyListObject *seq = it->it_seq;
if (index>=0 && index < PyList_GET_SIZE(seq)) {
item = PyList_GET_ITEM(seq, index);
it->it_index--;
Py_INCREF(item);
return item;
}
it->it_index = -1;
if (seq != NULL) {
it->it_seq = NULL;
Py_DECREF(seq);
}
return NULL;
}
static PyObject *
listreviter_len(listreviterobject *it)
{
Py_ssize_t len = it->it_index + 1;
if (it->it_seq == NULL || PyList_GET_SIZE(it->it_seq) < len)
len = 0;
return PyLong_FromSsize_t(len);
}