[Python-checkins] python/dist/src/Modules itertoolsmodule.c, 1.21,
1.22
rhettinger at users.sourceforge.net
rhettinger at users.sourceforge.net
Fri Oct 24 04:45:26 EDT 2003
Update of /cvsroot/python/python/dist/src/Modules
In directory sc8-pr-cvs1:/tmp/cvs-serv26769/Modules
Modified Files:
itertoolsmodule.c
Log Message:
Added itertools.tee()
It works like the pure python verion except:
* it stops storing data after of the iterators gets deallocated
* the data queue is implemented with two stacks instead of one dictionary.
Index: itertoolsmodule.c
===================================================================
RCS file: /cvsroot/python/python/dist/src/Modules/itertoolsmodule.c,v
retrieving revision 1.21
retrieving revision 1.22
diff -C2 -d -r1.21 -r1.22
*** itertoolsmodule.c 30 Aug 2003 00:10:06 -0000 1.21
--- itertoolsmodule.c 24 Oct 2003 08:45:23 -0000 1.22
***************
*** 8,11 ****
--- 8,269 ----
*/
+ /* independent iterator object supporting the tee object ***************/
+
+ /* The tee object maintains a queue of data seen by the leading iterator
+ but not seen by the trailing iterator. When the leading iterator
+ gets data from PyIter_Next() it appends a copy to the inbasket stack.
+ When the trailing iterator needs data, it is popped from the outbasket
+ stack. If the outbasket stack is empty, then it is filled from the
+ inbasket (i.e. the queue is implemented using two stacks so that only
+ O(n) operations like append() and pop() are used to access data and
+ calls to reverse() never move any data element more than once).
+
+ If one of the independent iterators gets deallocated, it sets tee's
+ save_mode to zero so that future calls to PyIter_Next() stop getting
+ saved to the queue (because there is no longer a second iterator that
+ may need the data).
+ */
+
+ typedef struct {
+ PyObject_HEAD
+ PyObject *it;
+ PyObject *inbasket;
+ PyObject *outbasket;
+ int save_mode;
+ int num_seen;
+ } teeobject;
+
+ typedef struct {
+ PyObject_HEAD
+ teeobject *tee;
+ int num_seen;
+ } iiobject;
+
+ static PyTypeObject ii_type;
+
+ static PyObject *
+ ii_next(iiobject *lz)
+ {
+ teeobject *to = lz->tee;
+ PyObject *result, *tmp;
+
+ if (lz->num_seen == to->num_seen) {
+ /* This instance is leading, use iter to get more data */
+ result = PyIter_Next(to->it);
+ if (result == NULL)
+ return NULL;
+ if (to->save_mode)
+ PyList_Append(to->inbasket, result);
+ to->num_seen++;
+ lz->num_seen++;
+ return result;
+ }
+
+ /* This instance is trailing, get data from the queue */
+ if (PyList_GET_SIZE(to->outbasket) == 0) {
+ /* outbasket is empty, so refill from the inbasket */
+ tmp = to->outbasket;
+ to->outbasket = to->inbasket;
+ to->inbasket = tmp;
+ PyList_Reverse(to->outbasket);
+ assert(PyList_GET_SIZE(to->outbasket) > 0);
+ }
+
+ lz->num_seen++;
+ return PyObject_CallMethod(to->outbasket, "pop", NULL);
+ }
+
+ static void
+ ii_dealloc(iiobject *ii)
+ {
+ PyObject_GC_UnTrack(ii);
+ ii->tee->save_mode = 0; /* Stop saving data */
+ Py_XDECREF(ii->tee);
+ PyObject_GC_Del(ii);
+ }
+
+ static int
+ ii_traverse(iiobject *ii, visitproc visit, void *arg)
+ {
+ if (ii->tee)
+ return visit((PyObject *)(ii->tee), arg);
+ return 0;
+ }
+
+ PyDoc_STRVAR(ii_doc, "Independent iterators linked to a tee() object.");
+
+ static PyTypeObject ii_type = {
+ PyObject_HEAD_INIT(&PyType_Type)
+ 0, /* ob_size */
+ "itertools.independent_iterator", /* tp_name */
+ sizeof(iiobject), /* tp_basicsize */
+ 0, /* tp_itemsize */
+ /* methods */
+ (destructor)ii_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 */
+ ii_doc, /* tp_doc */
+ (traverseproc)ii_traverse, /* tp_traverse */
+ 0, /* tp_clear */
+ 0, /* tp_richcompare */
+ 0, /* tp_weaklistoffset */
+ PyObject_SelfIter, /* tp_iter */
+ (iternextfunc)ii_next, /* tp_iternext */
+ 0, /* tp_methods */
+ };
+
+ /* tee object **********************************************************/
+
+ static PyTypeObject tee_type;
+
+ static PyObject *
+ tee_new(PyTypeObject *type, PyObject *args, PyObject *kwds)
+ {
+ PyObject *it = NULL;
+ PyObject *iterable;
+ PyObject *inbasket = NULL, *outbasket = NULL, *result = NULL;
+ teeobject *to = NULL;
+ int i;
+
+ if (!PyArg_UnpackTuple(args, "tee", 1, 1, &iterable))
+ return NULL;
+
+ it = PyObject_GetIter(iterable);
+ if (it == NULL) goto fail;
+
+ inbasket = PyList_New(0);
+ if (inbasket == NULL) goto fail;
+
+ outbasket = PyList_New(0);
+ if (outbasket == NULL) goto fail;
+
+ to = (teeobject *)type->tp_alloc(type, 0);
+ if (to == NULL) goto fail;
+
+ to->it = it;
+ to->inbasket = inbasket;
+ to->outbasket = outbasket;
+ to->save_mode = 1;
+ to->num_seen = 0;
+
+ /* create independent iterators */
+ result = PyTuple_New(2);
+ if (result == NULL) goto fail;
+ for (i=0 ; i<2 ; i++) {
+ iiobject *indep_it = PyObject_GC_New(iiobject, &ii_type);
+ if (indep_it == NULL) goto fail;
+ Py_INCREF(to);
+ indep_it->tee = to;
+ indep_it->num_seen = 0;
+ PyObject_GC_Track(indep_it);
+ PyTuple_SET_ITEM(result, i, (PyObject *)indep_it);
+ }
+ goto succeed;
+ fail:
+ Py_XDECREF(it);
+ Py_XDECREF(inbasket);
+ Py_XDECREF(outbasket);
+ Py_XDECREF(result);
+ succeed:
+ Py_XDECREF(to);
+ return result;
+ }
+
+ static void
+ tee_dealloc(teeobject *to)
+ {
+ PyObject_GC_UnTrack(to);
+ Py_XDECREF(to->inbasket);
+ Py_XDECREF(to->outbasket);
+ Py_XDECREF(to->it);
+ to->ob_type->tp_free(to);
+ }
+
+ static int
+ tee_traverse(teeobject *to, visitproc visit, void *arg)
+ {
+ int err;
+
+ if (to->it) {
+ err = visit(to->it, arg);
+ if (err)
+ return err;
+ }
+ if (to->inbasket) {
+ err = visit(to->inbasket, arg);
+ if (err)
+ return err;
+ }
+ if (to->outbasket) {
+ err = visit(to->outbasket, arg);
+ if (err)
+ return err;
+ }
+ return 0;
+ }
+
+ PyDoc_STRVAR(tee_doc,
+ "tee(iterable) --> (it1, it2)\n\
+ \n\
+ Split the iterable into to independent iterables.");
+
+ static PyTypeObject tee_type = {
+ PyObject_HEAD_INIT(NULL)
+ 0, /* ob_size */
+ "itertools.tee", /* tp_name */
+ sizeof(teeobject), /* tp_basicsize */
+ 0, /* tp_itemsize */
+ /* methods */
+ (destructor)tee_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 |
+ Py_TPFLAGS_BASETYPE, /* tp_flags */
+ tee_doc, /* tp_doc */
+ (traverseproc)tee_traverse, /* tp_traverse */
+ 0, /* tp_clear */
+ 0, /* tp_richcompare */
+ 0, /* tp_weaklistoffset */
+ 0, /* tp_iter */
+ 0, /* tp_iternext */
+ 0, /* 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 */
+ 0, /* tp_init */
+ 0, /* tp_alloc */
+ tee_new, /* tp_new */
+ PyObject_GC_Del, /* tp_free */
+ };
+
/* cycle object **********************************************************/
***************
*** 1825,1828 ****
--- 2083,2087 ----
char *name;
PyTypeObject *typelist[] = {
+ &tee_type,
&cycle_type,
&dropwhile_type,
More information about the Python-checkins
mailing list