Skip to content

bpo-40077: Convert itertools types to heap types #24065

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Closed
erlend-aasland wants to merge 24 commits into from
+659 −1,026
Closed

bpo-40077: Convert itertools types to heap types #24065

Show file tree
Hide file tree
Changes from 1 commit
Commits
Show all changes
24 commits
Select commit Hold shift + click to select a range
1c93d36
Convert groupby and _grouper to heap types
Jan 2, 2021
f1d27e9
Convert cycle type to heap type
Jan 2, 2021
c654ad3
Convert dropwhile type to heap type
Jan 2, 2021
09206f9
Convert takewhile type to heap type
Jan 2, 2021
676d4ef
Convert starmap type to heap type
Jan 2, 2021
68a64c6
Convert combinations & cwr types to heap types
Jan 2, 2021
f46b80c
Convert permutations type to heap type
Jan 2, 2021
520b009
Convert accumulate type to heap type
Jan 2, 2021
970c8bb
Convert compress type to heap type
Jan 2, 2021
8f24fb5
Convert filterfalse type to heap type
Jan 2, 2021
1e8d1cc
Convert count type to heap type
Jan 2, 2021
a6df90d
Convert pairwise type to heap type
Jan 2, 2021
ea4ac64
Convert ziplongest type to heap type
Jan 2, 2021
55fc088
Convert product type to heap type
Jan 2, 2021
7c32c2f
Convert repeat type to heap type
Jan 2, 2021
3bde6b4
Convert islice type to heap type
Jan 2, 2021
88b0926
Convert chain type to heap type
Jan 2, 2021
de95b43
Convert tee type to heap type
Jan 2, 2021
3df69b6
Convert teedataobject type to heap type
Jan 2, 2021
adbde61
Remove unneeded PyType_Ready() calls
Jan 2, 2021
cb8c7fe
Sort types
Jan 2, 2021
a2c9349
Remove unneeded Py_SET_TYPE on teedataobject type
Jan 2, 2021
8d8cd61
Add NEWS
Jan 2, 2021
55cee70
Address review: fix performance issue in tee_copy()
Jan 3, 2021
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
Next Next commit
Convert groupby and _grouper to heap types
  • Loading branch information
Erlend E. Aasland committed Jan 2, 2021
commit 1c93d366b767166fbe9e9734a217e61a56373e60
8 changes: 4 additions & 4 deletions Modules/clinic/itertoolsmodule.c.h
View file
Open in desktop

Some generated files are not rendered by default. Learn more about how customized files appear on GitHub.

219 changes: 116 additions & 103 deletions Modules/itertoolsmodule.c
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -11,10 +11,33 @@
by Raymond D. Hettinger <python@rcn.com>
*/

typedef struct {
PyTypeObject *groupby_type;
PyTypeObject *_grouper_type;
} itertoolsmodule_state;

static itertoolsmodule_state *
itertoolsmodule_get_state(PyObject *m)
{
itertoolsmodule_state *state = PyModule_GetState(m);
assert(state != NULL);
return state;
}

static struct PyModuleDef itertoolsmodule;
static itertoolsmodule_state *
itertoolsmodule_find_state_by_type(PyTypeObject *tp)
{
PyObject *m = _PyType_GetModuleByDef(tp, &itertoolsmodule);
assert(m != NULL);
return itertoolsmodule_get_state(m);
}
#define clinic_find_state() itertoolsmodule_find_state_by_type(type)

/*[clinic input]
module itertools
class itertools.groupby "groupbyobject *" "&groupby_type"
class itertools._grouper "_grouperobject *" "&_grouper_type"
class itertools.groupby "groupbyobject *" "clinic_find_state()->groupby_type"
class itertools._grouper "_grouperobject *" "clinic_find_state()->_grouper_type"
class itertools.teedataobject "teedataobject *" "&teedataobject_type"
class itertools._tee "teeobject *" "&tee_type"
class itertools.cycle "cycleobject *" "&cycle_type"
Expand All @@ -31,10 +54,8 @@ class itertools.filterfalse "filterfalseobject *" "&filterfalse_type"
class itertools.count "countobject *" "&count_type"
class itertools.pairwise "pairwiseobject *" "&pairwise_type"
[clinic start generated code]*/
/*[clinic end generated code: output=da39a3ee5e6b4b0d input=6498ed21fbe1bf94]*/
/*[clinic end generated code: output=da39a3ee5e6b4b0d input=bfcda45ca759edca]*/

static PyTypeObject groupby_type;
static PyTypeObject _grouper_type;
static PyTypeObject teedataobject_type;
static PyTypeObject tee_type;
static PyTypeObject cycle_type;
Expand Down Expand Up @@ -236,13 +257,15 @@ itertools_groupby_impl(PyTypeObject *type, PyObject *it, PyObject *keyfunc)
static void
groupby_dealloc(groupbyobject *gbo)
{
PyTypeObject *tp = Py_TYPE(gbo);
PyObject_GC_UnTrack(gbo);
Py_XDECREF(gbo->it);
Py_XDECREF(gbo->keyfunc);
Py_XDECREF(gbo->tgtkey);
Py_XDECREF(gbo->currkey);
Py_XDECREF(gbo->currvalue);
Py_TYPE(gbo)->tp_free(gbo);
tp->tp_free(gbo);
Py_DECREF(tp);
}

static int
Expand Down Expand Up @@ -369,50 +392,25 @@ static PyMethodDef groupby_methods[] = {
{NULL, NULL} /* sentinel */
};

static PyTypeObject groupby_type = {
PyVarObject_HEAD_INIT(NULL, 0)
"itertools.groupby", /* tp_name */
sizeof(groupbyobject), /* tp_basicsize */
0, /* tp_itemsize */
/* methods */
(destructor)groupby_dealloc, /* tp_dealloc */
0, /* tp_vectorcall_offset */
0, /* tp_getattr */
0, /* tp_setattr */
0, /* tp_as_async */
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 */
itertools_groupby__doc__, /* tp_doc */
(traverseproc)groupby_traverse, /* tp_traverse */
0, /* tp_clear */
0, /* tp_richcompare */
0, /* tp_weaklistoffset */
PyObject_SelfIter, /* tp_iter */
(iternextfunc)groupby_next, /* tp_iternext */
groupby_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 */
0, /* tp_init */
0, /* tp_alloc */
itertools_groupby, /* tp_new */
PyObject_GC_Del, /* tp_free */
static PyType_Slot groupby_slots[] = {
{Py_tp_dealloc, groupby_dealloc},
{Py_tp_getattro, PyObject_GenericGetAttr},
{Py_tp_doc, (void *)itertools_groupby__doc__},
{Py_tp_traverse, groupby_traverse},
{Py_tp_iter, PyObject_SelfIter},
{Py_tp_iternext, groupby_next},
{Py_tp_methods, groupby_methods},
{Py_tp_new, itertools_groupby},
{Py_tp_free, PyObject_GC_Del},
{0, NULL},
};

static PyType_Spec groupby_spec = {
.name = "itertools.groupby",
.basicsize= sizeof(groupbyobject),
.flags = Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC | Py_TPFLAGS_BASETYPE,
.slots = groupby_slots,
};

/* _grouper object (internal) ************************************************/

Expand All @@ -426,15 +424,15 @@ typedef struct {
@classmethod
itertools._grouper.__new__

parent: object(subclass_of='&groupby_type')
parent: object(subclass_of='clinic_find_state()->groupby_type')
tgtkey: object
/
[clinic start generated code]*/

static PyObject *
itertools__grouper_impl(PyTypeObject *type, PyObject *parent,
PyObject *tgtkey)
/*[clinic end generated code: output=462efb1cdebb5914 input=dc180d7771fc8c59]*/
/*[clinic end generated code: output=462efb1cdebb5914 input=0a93f28286c8e913]*/
{
return _grouper_create((groupbyobject*) parent, tgtkey);
}
Expand All @@ -443,8 +441,9 @@ static PyObject *
_grouper_create(groupbyobject *parent, PyObject *tgtkey)
{
_grouperobject *igo;
itertoolsmodule_state *state = itertoolsmodule_find_state_by_type(Py_TYPE(parent));

igo = PyObject_GC_New(_grouperobject, &_grouper_type);
igo = PyObject_GC_New(_grouperobject, state->_grouper_type);
if (igo == NULL)
return NULL;
igo->parent = (PyObject *)parent;
Expand All @@ -460,10 +459,12 @@ _grouper_create(groupbyobject *parent, PyObject *tgtkey)
static void
_grouper_dealloc(_grouperobject *igo)
{
PyTypeObject *tp = Py_TYPE(igo);
PyObject_GC_UnTrack(igo);
Py_DECREF(igo->parent);
Py_DECREF(igo->tgtkey);
PyObject_GC_Del(igo);
Py_DECREF(tp);
}

static int
Expand Down Expand Up @@ -517,48 +518,23 @@ static PyMethodDef _grouper_methods[] = {
{NULL, NULL} /* sentinel */
};

static PyType_Slot _grouper_slots[] = {
{Py_tp_dealloc, _grouper_dealloc},
{Py_tp_getattro, PyObject_GenericGetAttr},
{Py_tp_traverse, _grouper_traverse},
{Py_tp_iter, PyObject_SelfIter},
{Py_tp_iternext, _grouper_next},
{Py_tp_methods, _grouper_methods},
{Py_tp_new, itertools__grouper},
{Py_tp_free, PyObject_GC_Del},
{0, NULL},
};

static PyTypeObject _grouper_type = {
PyVarObject_HEAD_INIT(NULL, 0)
"itertools._grouper", /* tp_name */
sizeof(_grouperobject), /* tp_basicsize */
0, /* tp_itemsize */
/* methods */
(destructor)_grouper_dealloc, /* tp_dealloc */
0, /* tp_vectorcall_offset */
0, /* tp_getattr */
0, /* tp_setattr */
0, /* tp_as_async */
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)_grouper_traverse, /* tp_traverse */
0, /* tp_clear */
0, /* tp_richcompare */
0, /* tp_weaklistoffset */
PyObject_SelfIter, /* tp_iter */
(iternextfunc)_grouper_next, /* tp_iternext */
_grouper_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 */
0, /* tp_init */
0, /* tp_alloc */
itertools__grouper, /* tp_new */
PyObject_GC_Del, /* tp_free */
static PyType_Spec _grouper_spec = {
.name = "itertools._grouper",
.basicsize = sizeof(_grouperobject),
.flags = Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC,
.slots = _grouper_slots,
};


Expand Down Expand Up @@ -4838,9 +4814,48 @@ combinations(p, r)\n\
combinations_with_replacement(p, r)\n\
");

static int
itertoolsmodule_traverse(PyObject *m, visitproc visit, void *arg)
{
itertoolsmodule_state *state = itertoolsmodule_get_state(m);
Py_VISIT(state->groupby_type);
Py_VISIT(state->_grouper_type);
return 0;
}

static int
itertoolsmodule_clear(PyObject *m)
{
itertoolsmodule_state *state = itertoolsmodule_get_state(m);
Py_CLEAR(state->groupby_type);
Py_CLEAR(state->_grouper_type);
return 0;
}

static void
itertoolsmodule_free(void *m)
{
itertoolsmodule_clear((PyObject *)m);
}

#define ADD_TYPE(module, type, spec) \
do { \
type = (PyTypeObject *)PyType_FromModuleAndSpec(module, spec, NULL); \
if (!type) { \
return -1; \
} \
if (PyModule_AddType(module, type) < 0) { \
return -1; \
} \
} while (0)

static int
itertoolsmodule_exec(PyObject *m)
{
itertoolsmodule_state *state = itertoolsmodule_get_state(m);
ADD_TYPE(m, state->groupby_type, &groupby_spec);
ADD_TYPE(m, state->_grouper_type, &_grouper_spec);

PyTypeObject *typelist[] = {
&accumulate_type,
&combinations_type,
Expand All @@ -4859,8 +4874,6 @@ itertoolsmodule_exec(PyObject *m)
&permutations_type,
&product_type,
&repeat_type,
&groupby_type,
&_grouper_type,
&tee_type,
&teedataobject_type
};
Expand Down Expand Up @@ -4888,15 +4901,15 @@ static PyMethodDef module_methods[] = {


static struct PyModuleDef itertoolsmodule = {
PyModuleDef_HEAD_INIT,
"itertools",
module_doc,
0,
module_methods,
itertoolsmodule_slots,
NULL,
NULL,
NULL
.m_base = PyModuleDef_HEAD_INIT,
.m_name = "itertools",
.m_doc = module_doc,
.m_size = sizeof(itertoolsmodule_state),
.m_methods = module_methods,
.m_slots = itertoolsmodule_slots,
.m_traverse = itertoolsmodule_traverse,
.m_clear = itertoolsmodule_clear,
.m_free = itertoolsmodule_free,
};

PyMODINIT_FUNC
Expand Down