Ignore:
Timestamp:
Mar 19, 2014, 11:11:30 AM (11 years ago)
Author:
dmik
Message:

python: Update vendor to 2.7.6.

File:
1 edited

Legend:

Unmodified
Added
Removed
  • python/vendor/current/Modules/itertoolsmodule.c

    r2 r388  
    33#include "structmember.h"
    44
    5 /* Itertools module written and maintained 
     5/* Itertools module written and maintained
    66   by Raymond D. Hettinger <python@rcn.com>
    77   Copyright (c) 2003 Python Software Foundation.
     
    1313
    1414typedef struct {
    15         PyObject_HEAD
    16         PyObject *it;
    17         PyObject *keyfunc;
    18         PyObject *tgtkey;
    19         PyObject *currkey;
    20         PyObject *currvalue;
     15    PyObject_HEAD
     16    PyObject *it;
     17    PyObject *keyfunc;
     18    PyObject *tgtkey;
     19    PyObject *currkey;
     20    PyObject *currvalue;
    2121} groupbyobject;
    2222
     
    2727groupby_new(PyTypeObject *type, PyObject *args, PyObject *kwds)
    2828{
    29         static char *kwargs[] = {"iterable", "key", NULL};
    30         groupbyobject *gbo;
    31         PyObject *it, *keyfunc = Py_None;
    32  
    33         if (!PyArg_ParseTupleAndKeywords(args, kwds, "O|O:groupby", kwargs,
    34                                         &it, &keyfunc))
    35                 return NULL;
    36 
    37         gbo = (groupbyobject *)type->tp_alloc(type, 0);
    38         if (gbo == NULL)
    39                 return NULL;
    40         gbo->tgtkey = NULL;
    41         gbo->currkey = NULL;
    42         gbo->currvalue = NULL;
    43         gbo->keyfunc = keyfunc;
    44         Py_INCREF(keyfunc);
    45         gbo->it = PyObject_GetIter(it);
    46         if (gbo->it == NULL) {
    47                 Py_DECREF(gbo);
    48                 return NULL;
    49         }
    50         return (PyObject *)gbo;
     29    static char *kwargs[] = {"iterable", "key", NULL};
     30    groupbyobject *gbo;
     31    PyObject *it, *keyfunc = Py_None;
     32
     33    if (!PyArg_ParseTupleAndKeywords(args, kwds, "O|O:groupby", kwargs,
     34                                    &it, &keyfunc))
     35        return NULL;
     36
     37    gbo = (groupbyobject *)type->tp_alloc(type, 0);
     38    if (gbo == NULL)
     39        return NULL;
     40    gbo->tgtkey = NULL;
     41    gbo->currkey = NULL;
     42    gbo->currvalue = NULL;
     43    gbo->keyfunc = keyfunc;
     44    Py_INCREF(keyfunc);
     45    gbo->it = PyObject_GetIter(it);
     46    if (gbo->it == NULL) {
     47        Py_DECREF(gbo);
     48        return NULL;
     49    }
     50    return (PyObject *)gbo;
    5151}
    5252
     
    5454groupby_dealloc(groupbyobject *gbo)
    5555{
    56         PyObject_GC_UnTrack(gbo);
    57         Py_XDECREF(gbo->it);
    58         Py_XDECREF(gbo->keyfunc);
    59         Py_XDECREF(gbo->tgtkey);
    60         Py_XDECREF(gbo->currkey);
    61         Py_XDECREF(gbo->currvalue);
    62         Py_TYPE(gbo)->tp_free(gbo);
     56    PyObject_GC_UnTrack(gbo);
     57    Py_XDECREF(gbo->it);
     58    Py_XDECREF(gbo->keyfunc);
     59    Py_XDECREF(gbo->tgtkey);
     60    Py_XDECREF(gbo->currkey);
     61    Py_XDECREF(gbo->currvalue);
     62    Py_TYPE(gbo)->tp_free(gbo);
    6363}
    6464
     
    6666groupby_traverse(groupbyobject *gbo, visitproc visit, void *arg)
    6767{
    68         Py_VISIT(gbo->it);
    69         Py_VISIT(gbo->keyfunc);
    70         Py_VISIT(gbo->tgtkey);
    71         Py_VISIT(gbo->currkey);
    72         Py_VISIT(gbo->currvalue);
    73         return 0;
     68    Py_VISIT(gbo->it);
     69    Py_VISIT(gbo->keyfunc);
     70    Py_VISIT(gbo->tgtkey);
     71    Py_VISIT(gbo->currkey);
     72    Py_VISIT(gbo->currvalue);
     73    return 0;
    7474}
    7575
     
    7777groupby_next(groupbyobject *gbo)
    7878{
    79         PyObject *newvalue, *newkey, *r, *grouper, *tmp;
    80 
    81         /* skip to next iteration group */
    82         for (;;) {
    83                 if (gbo->currkey == NULL)
    84                         /* pass */;
    85                 else if (gbo->tgtkey == NULL)
    86                         break;
    87                 else {
    88                         int rcmp;
    89 
    90                         rcmp = PyObject_RichCompareBool(gbo->tgtkey,
    91                                                         gbo->currkey, Py_EQ);
    92                         if (rcmp == -1)
    93                                 return NULL;
    94                         else if (rcmp == 0)
    95                                 break;
    96                 }
    97 
    98                 newvalue = PyIter_Next(gbo->it);
    99                 if (newvalue == NULL)
    100                         return NULL;
    101 
    102                 if (gbo->keyfunc == Py_None) {
    103                         newkey = newvalue;
    104                         Py_INCREF(newvalue);
    105                 } else {
    106                         newkey = PyObject_CallFunctionObjArgs(gbo->keyfunc,
    107                                                               newvalue, NULL);
    108                         if (newkey == NULL) {
    109                                 Py_DECREF(newvalue);
    110                                 return NULL;
    111                         }
    112                 }
    113 
    114                 tmp = gbo->currkey;
    115                 gbo->currkey = newkey;
    116                 Py_XDECREF(tmp);
    117 
    118                 tmp = gbo->currvalue;
    119                 gbo->currvalue = newvalue;
    120                 Py_XDECREF(tmp);
    121         }
    122 
    123         Py_INCREF(gbo->currkey);
    124         tmp = gbo->tgtkey;
    125         gbo->tgtkey = gbo->currkey;
    126         Py_XDECREF(tmp);
    127 
    128         grouper = _grouper_create(gbo, gbo->tgtkey);
    129         if (grouper == NULL)
    130                 return NULL;
    131 
    132         r = PyTuple_Pack(2, gbo->currkey, grouper);
    133         Py_DECREF(grouper);
    134         return r;
     79    PyObject *newvalue, *newkey, *r, *grouper, *tmp;
     80
     81    /* skip to next iteration group */
     82    for (;;) {
     83        if (gbo->currkey == NULL)
     84            /* pass */;
     85        else if (gbo->tgtkey == NULL)
     86            break;
     87        else {
     88            int rcmp;
     89
     90            rcmp = PyObject_RichCompareBool(gbo->tgtkey,
     91                                            gbo->currkey, Py_EQ);
     92            if (rcmp == -1)
     93                return NULL;
     94            else if (rcmp == 0)
     95                break;
     96        }
     97
     98        newvalue = PyIter_Next(gbo->it);
     99        if (newvalue == NULL)
     100            return NULL;
     101
     102        if (gbo->keyfunc == Py_None) {
     103            newkey = newvalue;
     104            Py_INCREF(newvalue);
     105        } else {
     106            newkey = PyObject_CallFunctionObjArgs(gbo->keyfunc,
     107                                                  newvalue, NULL);
     108            if (newkey == NULL) {
     109                Py_DECREF(newvalue);
     110                return NULL;
     111            }
     112        }
     113
     114        tmp = gbo->currkey;
     115        gbo->currkey = newkey;
     116        Py_XDECREF(tmp);
     117
     118        tmp = gbo->currvalue;
     119        gbo->currvalue = newvalue;
     120        Py_XDECREF(tmp);
     121    }
     122
     123    Py_INCREF(gbo->currkey);
     124    tmp = gbo->tgtkey;
     125    gbo->tgtkey = gbo->currkey;
     126    Py_XDECREF(tmp);
     127
     128    grouper = _grouper_create(gbo, gbo->tgtkey);
     129    if (grouper == NULL)
     130        return NULL;
     131
     132    r = PyTuple_Pack(2, gbo->currkey, grouper);
     133    Py_DECREF(grouper);
     134    return r;
    135135}
    136136
     
    140140
    141141static PyTypeObject groupby_type = {
    142         PyVarObject_HEAD_INIT(NULL, 0)
    143         "itertools.groupby",            /* tp_name */
    144         sizeof(groupbyobject),          /* tp_basicsize */
    145         0,                              /* tp_itemsize */
    146         /* methods */
    147         (destructor)groupby_dealloc,    /* tp_dealloc */
    148         0,                              /* tp_print */
    149         0,                              /* tp_getattr */
    150         0,                              /* tp_setattr */
    151         0,                              /* tp_compare */
    152         0,                              /* tp_repr */
    153         0,                              /* tp_as_number */
    154         0,                              /* tp_as_sequence */
    155         0,                              /* tp_as_mapping */
    156         0,                              /* tp_hash */
    157         0,                              /* tp_call */
    158         0,                              /* tp_str */
    159         PyObject_GenericGetAttr,        /* tp_getattro */
    160         0,                              /* tp_setattro */
    161         0,                              /* tp_as_buffer */
    162         Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC |
    163                 Py_TPFLAGS_BASETYPE,    /* tp_flags */
    164         groupby_doc,                    /* tp_doc */
    165         (traverseproc)groupby_traverse, /* tp_traverse */
    166         0,                              /* tp_clear */
    167         0,                              /* tp_richcompare */
    168         0,                              /* tp_weaklistoffset */
    169         PyObject_SelfIter,              /* tp_iter */
    170         (iternextfunc)groupby_next,     /* tp_iternext */
    171         0,                              /* tp_methods */
    172         0,                              /* tp_members */
    173         0,                              /* tp_getset */
    174         0,                              /* tp_base */
    175         0,                              /* tp_dict */
    176         0,                              /* tp_descr_get */
    177         0,                              /* tp_descr_set */
    178         0,                              /* tp_dictoffset */
    179         0,                              /* tp_init */
    180         0,                              /* tp_alloc */
    181         groupby_new,                    /* tp_new */
    182         PyObject_GC_Del,                /* tp_free */
     142    PyVarObject_HEAD_INIT(NULL, 0)
     143    "itertools.groupby",                /* tp_name */
     144    sizeof(groupbyobject),              /* tp_basicsize */
     145    0,                                  /* tp_itemsize */
     146    /* methods */
     147    (destructor)groupby_dealloc,        /* tp_dealloc */
     148    0,                                  /* tp_print */
     149    0,                                  /* tp_getattr */
     150    0,                                  /* tp_setattr */
     151    0,                                  /* tp_compare */
     152    0,                                  /* tp_repr */
     153    0,                                  /* tp_as_number */
     154    0,                                  /* tp_as_sequence */
     155    0,                                  /* tp_as_mapping */
     156    0,                                  /* tp_hash */
     157    0,                                  /* tp_call */
     158    0,                                  /* tp_str */
     159    PyObject_GenericGetAttr,            /* tp_getattro */
     160    0,                                  /* tp_setattro */
     161    0,                                  /* tp_as_buffer */
     162    Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC |
     163        Py_TPFLAGS_BASETYPE,            /* tp_flags */
     164    groupby_doc,                        /* tp_doc */
     165    (traverseproc)groupby_traverse,     /* tp_traverse */
     166    0,                                  /* tp_clear */
     167    0,                                  /* tp_richcompare */
     168    0,                                  /* tp_weaklistoffset */
     169    PyObject_SelfIter,                  /* tp_iter */
     170    (iternextfunc)groupby_next,         /* tp_iternext */
     171    0,                                  /* tp_methods */
     172    0,                                  /* tp_members */
     173    0,                                  /* tp_getset */
     174    0,                                  /* tp_base */
     175    0,                                  /* tp_dict */
     176    0,                                  /* tp_descr_get */
     177    0,                                  /* tp_descr_set */
     178    0,                                  /* tp_dictoffset */
     179    0,                                  /* tp_init */
     180    0,                                  /* tp_alloc */
     181    groupby_new,                        /* tp_new */
     182    PyObject_GC_Del,                    /* tp_free */
    183183};
    184184
     
    187187
    188188typedef struct {
    189         PyObject_HEAD
    190         PyObject *parent;
    191         PyObject *tgtkey;
     189    PyObject_HEAD
     190    PyObject *parent;
     191    PyObject *tgtkey;
    192192} _grouperobject;
    193193
     
    197197_grouper_create(groupbyobject *parent, PyObject *tgtkey)
    198198{
    199         _grouperobject *igo;
    200 
    201         igo = PyObject_GC_New(_grouperobject, &_grouper_type);
    202         if (igo == NULL)
    203                 return NULL;
    204         igo->parent = (PyObject *)parent;
    205         Py_INCREF(parent);
    206         igo->tgtkey = tgtkey;
    207         Py_INCREF(tgtkey);
    208 
    209         PyObject_GC_Track(igo);
    210         return (PyObject *)igo;
     199    _grouperobject *igo;
     200
     201    igo = PyObject_GC_New(_grouperobject, &_grouper_type);
     202    if (igo == NULL)
     203        return NULL;
     204    igo->parent = (PyObject *)parent;
     205    Py_INCREF(parent);
     206    igo->tgtkey = tgtkey;
     207    Py_INCREF(tgtkey);
     208
     209    PyObject_GC_Track(igo);
     210    return (PyObject *)igo;
    211211}
    212212
     
    214214_grouper_dealloc(_grouperobject *igo)
    215215{
    216         PyObject_GC_UnTrack(igo);
    217         Py_DECREF(igo->parent);
    218         Py_DECREF(igo->tgtkey);
    219         PyObject_GC_Del(igo);
     216    PyObject_GC_UnTrack(igo);
     217    Py_DECREF(igo->parent);
     218    Py_DECREF(igo->tgtkey);
     219    PyObject_GC_Del(igo);
    220220}
    221221
     
    223223_grouper_traverse(_grouperobject *igo, visitproc visit, void *arg)
    224224{
    225         Py_VISIT(igo->parent);
    226         Py_VISIT(igo->tgtkey);
    227         return 0;
     225    Py_VISIT(igo->parent);
     226    Py_VISIT(igo->tgtkey);
     227    return 0;
    228228}
    229229
     
    231231_grouper_next(_grouperobject *igo)
    232232{
    233         groupbyobject *gbo = (groupbyobject *)igo->parent;
    234         PyObject *newvalue, *newkey, *r;
    235         int rcmp;
    236 
    237         if (gbo->currvalue == NULL) {
    238                 newvalue = PyIter_Next(gbo->it);
    239                 if (newvalue == NULL)
    240                         return NULL;
    241 
    242                 if (gbo->keyfunc == Py_None) {
    243                         newkey = newvalue;
    244                         Py_INCREF(newvalue);
    245                 } else {
    246                         newkey = PyObject_CallFunctionObjArgs(gbo->keyfunc,
    247                                                               newvalue, NULL);
    248                         if (newkey == NULL) {
    249                                 Py_DECREF(newvalue);
    250                                 return NULL;
    251                         }
    252                 }
    253 
    254                 assert(gbo->currkey == NULL);
    255                 gbo->currkey = newkey;
    256                 gbo->currvalue = newvalue;
    257         }
    258 
    259         assert(gbo->currkey != NULL);
    260         rcmp = PyObject_RichCompareBool(igo->tgtkey, gbo->currkey, Py_EQ);
    261         if (rcmp <= 0)
    262                 /* got any error or current group is end */
    263                 return NULL;
    264 
    265         r = gbo->currvalue;
    266         gbo->currvalue = NULL;
    267         Py_CLEAR(gbo->currkey);
    268 
    269         return r;
     233    groupbyobject *gbo = (groupbyobject *)igo->parent;
     234    PyObject *newvalue, *newkey, *r;
     235    int rcmp;
     236
     237    if (gbo->currvalue == NULL) {
     238        newvalue = PyIter_Next(gbo->it);
     239        if (newvalue == NULL)
     240            return NULL;
     241
     242        if (gbo->keyfunc == Py_None) {
     243            newkey = newvalue;
     244            Py_INCREF(newvalue);
     245        } else {
     246            newkey = PyObject_CallFunctionObjArgs(gbo->keyfunc,
     247                                                  newvalue, NULL);
     248            if (newkey == NULL) {
     249                Py_DECREF(newvalue);
     250                return NULL;
     251            }
     252        }
     253
     254        assert(gbo->currkey == NULL);
     255        gbo->currkey = newkey;
     256        gbo->currvalue = newvalue;
     257    }
     258
     259    assert(gbo->currkey != NULL);
     260    rcmp = PyObject_RichCompareBool(igo->tgtkey, gbo->currkey, Py_EQ);
     261    if (rcmp <= 0)
     262        /* got any error or current group is end */
     263        return NULL;
     264
     265    r = gbo->currvalue;
     266    gbo->currvalue = NULL;
     267    Py_CLEAR(gbo->currkey);
     268
     269    return r;
    270270}
    271271
    272272static PyTypeObject _grouper_type = {
    273         PyVarObject_HEAD_INIT(NULL, 0)
    274         "itertools._grouper",           /* tp_name */
    275         sizeof(_grouperobject),         /* tp_basicsize */
    276         0,                              /* tp_itemsize */
    277         /* methods */
    278         (destructor)_grouper_dealloc,   /* tp_dealloc */
    279         0,                              /* tp_print */
    280         0,                              /* tp_getattr */
    281         0,                              /* tp_setattr */
    282         0,                              /* tp_compare */
    283         0,                              /* tp_repr */
    284         0,                              /* tp_as_number */
    285         0,                              /* tp_as_sequence */
    286         0,                              /* tp_as_mapping */
    287         0,                              /* tp_hash */
    288         0,                              /* tp_call */
    289         0,                              /* tp_str */
    290         PyObject_GenericGetAttr,        /* tp_getattro */
    291         0,                              /* tp_setattro */
    292         0,                              /* tp_as_buffer */
    293         Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC,        /* tp_flags */
    294         0,                              /* tp_doc */
    295         (traverseproc)_grouper_traverse,/* tp_traverse */
    296         0,                              /* tp_clear */
    297         0,                              /* tp_richcompare */
    298         0,                              /* tp_weaklistoffset */
    299         PyObject_SelfIter,              /* tp_iter */
    300         (iternextfunc)_grouper_next,    /* tp_iternext */
    301         0,                              /* tp_methods */
    302         0,                              /* tp_members */
    303         0,                              /* tp_getset */
    304         0,                              /* tp_base */
    305         0,                              /* tp_dict */
    306         0,                              /* tp_descr_get */
    307         0,                              /* tp_descr_set */
    308         0,                              /* tp_dictoffset */
    309         0,                              /* tp_init */
    310         0,                              /* tp_alloc */
    311         0,                              /* tp_new */
    312         PyObject_GC_Del,                /* tp_free */
     273    PyVarObject_HEAD_INIT(NULL, 0)
     274    "itertools._grouper",               /* tp_name */
     275    sizeof(_grouperobject),             /* tp_basicsize */
     276    0,                                  /* tp_itemsize */
     277    /* methods */
     278    (destructor)_grouper_dealloc,       /* tp_dealloc */
     279    0,                                  /* tp_print */
     280    0,                                  /* tp_getattr */
     281    0,                                  /* tp_setattr */
     282    0,                                  /* tp_compare */
     283    0,                                  /* tp_repr */
     284    0,                                  /* tp_as_number */
     285    0,                                  /* tp_as_sequence */
     286    0,                                  /* tp_as_mapping */
     287    0,                                  /* tp_hash */
     288    0,                                  /* tp_call */
     289    0,                                  /* tp_str */
     290    PyObject_GenericGetAttr,            /* tp_getattro */
     291    0,                                  /* tp_setattro */
     292    0,                                  /* tp_as_buffer */
     293    Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC,            /* tp_flags */
     294    0,                                  /* tp_doc */
     295    (traverseproc)_grouper_traverse,/* tp_traverse */
     296    0,                                  /* tp_clear */
     297    0,                                  /* tp_richcompare */
     298    0,                                  /* tp_weaklistoffset */
     299    PyObject_SelfIter,                  /* tp_iter */
     300    (iternextfunc)_grouper_next,        /* tp_iternext */
     301    0,                                  /* tp_methods */
     302    0,                                  /* tp_members */
     303    0,                                  /* tp_getset */
     304    0,                                  /* tp_base */
     305    0,                                  /* tp_dict */
     306    0,                                  /* tp_descr_get */
     307    0,                                  /* tp_descr_set */
     308    0,                                  /* tp_dictoffset */
     309    0,                                  /* tp_init */
     310    0,                                  /* tp_alloc */
     311    0,                                  /* tp_new */
     312    PyObject_GC_Del,                    /* tp_free */
    313313};
    314314
    315  
     315
    316316
    317317/* tee object and with supporting function and objects ***************/
     
    319319/* The teedataobject pre-allocates space for LINKCELLS number of objects.
    320320   To help the object fit neatly inside cache lines (space for 16 to 32
    321    pointers), the value should be a multiple of 16 minus  space for 
     321   pointers), the value should be a multiple of 16 minus  space for
    322322   the other structure members including PyHEAD overhead.  The larger the
    323323   value, the less memory overhead per object and the less time spent
     
    328328
    329329typedef struct {
    330         PyObject_HEAD
    331         PyObject *it;
    332         int numread;
    333         PyObject *nextlink;
    334         PyObject *(values[LINKCELLS]);
     330    PyObject_HEAD
     331    PyObject *it;
     332    int numread;
     333    PyObject *nextlink;
     334    PyObject *(values[LINKCELLS]);
    335335} teedataobject;
    336336
    337337typedef struct {
    338         PyObject_HEAD
    339         teedataobject *dataobj;
    340         int index;
    341         PyObject *weakreflist;
     338    PyObject_HEAD
     339    teedataobject *dataobj;
     340    int index;
     341    PyObject *weakreflist;
    342342} teeobject;
    343343
     
    347347teedataobject_new(PyObject *it)
    348348{
    349         teedataobject *tdo;
    350 
    351         tdo = PyObject_GC_New(teedataobject, &teedataobject_type);
    352         if (tdo == NULL)
    353                 return NULL;
    354 
    355         tdo->numread = 0;
    356         tdo->nextlink = NULL;
    357         Py_INCREF(it);
    358         tdo->it = it;
    359         PyObject_GC_Track(tdo);
    360         return (PyObject *)tdo;
     349    teedataobject *tdo;
     350
     351    tdo = PyObject_GC_New(teedataobject, &teedataobject_type);
     352    if (tdo == NULL)
     353        return NULL;
     354
     355    tdo->numread = 0;
     356    tdo->nextlink = NULL;
     357    Py_INCREF(it);
     358    tdo->it = it;
     359    PyObject_GC_Track(tdo);
     360    return (PyObject *)tdo;
    361361}
    362362
     
    364364teedataobject_jumplink(teedataobject *tdo)
    365365{
    366         if (tdo->nextlink == NULL)
    367                 tdo->nextlink = teedataobject_new(tdo->it);
    368         Py_XINCREF(tdo->nextlink);
    369         return tdo->nextlink;
     366    if (tdo->nextlink == NULL)
     367        tdo->nextlink = teedataobject_new(tdo->it);
     368    Py_XINCREF(tdo->nextlink);
     369    return tdo->nextlink;
    370370}
    371371
     
    373373teedataobject_getitem(teedataobject *tdo, int i)
    374374{
    375         PyObject *value;
    376 
    377         assert(i < LINKCELLS);
    378         if (i < tdo->numread)
    379                 value = tdo->values[i];
    380         else {
    381                 /* this is the lead iterator, so fetch more data */
    382                 assert(i == tdo->numread);
    383                 value = PyIter_Next(tdo->it);
    384                 if (value == NULL)
    385                         return NULL;
    386                 tdo->numread++;
    387                 tdo->values[i] = value;
    388         }
    389         Py_INCREF(value);
    390         return value;
     375    PyObject *value;
     376
     377    assert(i < LINKCELLS);
     378    if (i < tdo->numread)
     379        value = tdo->values[i];
     380    else {
     381        /* this is the lead iterator, so fetch more data */
     382        assert(i == tdo->numread);
     383        value = PyIter_Next(tdo->it);
     384        if (value == NULL)
     385            return NULL;
     386        tdo->numread++;
     387        tdo->values[i] = value;
     388    }
     389    Py_INCREF(value);
     390    return value;
    391391}
    392392
     
    394394teedataobject_traverse(teedataobject *tdo, visitproc visit, void * arg)
    395395{
    396         int i;
    397         Py_VISIT(tdo->it);
    398         for (i = 0; i < tdo->numread; i++)
    399                 Py_VISIT(tdo->values[i]);
    400         Py_VISIT(tdo->nextlink);
    401         return 0;
     396    int i;
     397    Py_VISIT(tdo->it);
     398    for (i = 0; i < tdo->numread; i++)
     399        Py_VISIT(tdo->values[i]);
     400    Py_VISIT(tdo->nextlink);
     401    return 0;
     402}
     403
     404static void
     405teedataobject_safe_decref(PyObject *obj)
     406{
     407    while (obj && Py_TYPE(obj) == &teedataobject_type &&
     408           Py_REFCNT(obj) == 1) {
     409        PyObject *nextlink = ((teedataobject *)obj)->nextlink;
     410        ((teedataobject *)obj)->nextlink = NULL;
     411        Py_DECREF(obj);
     412        obj = nextlink;
     413    }
     414    Py_XDECREF(obj);
    402415}
    403416
     
    405418teedataobject_clear(teedataobject *tdo)
    406419{
    407         int i;
    408         Py_CLEAR(tdo->it);
    409         for (i=0 ; i<tdo->numread ; i++)
    410                 Py_CLEAR(tdo->values[i]);
    411         Py_CLEAR(tdo->nextlink);
    412         return 0;
     420    int i;
     421    PyObject *tmp;
     422
     423    Py_CLEAR(tdo->it);
     424    for (i=0 ; i<tdo->numread ; i++)
     425        Py_CLEAR(tdo->values[i]);
     426    tmp = tdo->nextlink;
     427    tdo->nextlink = NULL;
     428    teedataobject_safe_decref(tmp);
     429    return 0;
    413430}
    414431
     
    416433teedataobject_dealloc(teedataobject *tdo)
    417434{
    418         PyObject_GC_UnTrack(tdo);
    419         teedataobject_clear(tdo);
    420         PyObject_GC_Del(tdo);
     435    PyObject_GC_UnTrack(tdo);
     436    teedataobject_clear(tdo);
     437    PyObject_GC_Del(tdo);
    421438}
    422439
     
    424441
    425442static PyTypeObject teedataobject_type = {
    426         PyVarObject_HEAD_INIT(0, 0)     /* Must fill in type value later */
    427         "itertools.tee_dataobject",             /* tp_name */
    428         sizeof(teedataobject),                  /* tp_basicsize */
    429         0,                                      /* tp_itemsize */
    430         /* methods */
    431         (destructor)teedataobject_dealloc,      /* tp_dealloc */
    432         0,                                      /* tp_print */
    433         0,                                      /* tp_getattr */
    434         0,                                      /* tp_setattr */
    435         0,                                      /* tp_compare */
    436         0,                                      /* tp_repr */
    437         0,                                      /* tp_as_number */
    438         0,                                      /* tp_as_sequence */
    439         0,                                      /* tp_as_mapping */
    440         0,                                      /* tp_hash */
    441         0,                                      /* tp_call */
    442         0,                                      /* tp_str */
    443         PyObject_GenericGetAttr,                /* tp_getattro */
    444         0,                                      /* tp_setattro */
    445         0,                                      /* tp_as_buffer */
    446         Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC,        /* tp_flags */
    447         teedataobject_doc,                      /* tp_doc */
    448         (traverseproc)teedataobject_traverse,   /* tp_traverse */
    449         (inquiry)teedataobject_clear,           /* tp_clear */
    450         0,                                      /* tp_richcompare */
    451         0,                                      /* tp_weaklistoffset */
    452         0,                                      /* tp_iter */
    453         0,                                      /* tp_iternext */
    454         0,                                      /* tp_methods */
    455         0,                                      /* tp_members */
    456         0,                                      /* tp_getset */
    457         0,                                      /* tp_base */
    458         0,                                      /* tp_dict */
    459         0,                                      /* tp_descr_get */
    460         0,                                      /* tp_descr_set */
    461         0,                                      /* tp_dictoffset */
    462         0,                                      /* tp_init */
    463         0,                                      /* tp_alloc */
    464         0,                                      /* tp_new */
    465         PyObject_GC_Del,                        /* tp_free */
     443    PyVarObject_HEAD_INIT(0, 0)         /* Must fill in type value later */
     444    "itertools.tee_dataobject",                 /* tp_name */
     445    sizeof(teedataobject),                      /* tp_basicsize */
     446    0,                                          /* tp_itemsize */
     447    /* methods */
     448    (destructor)teedataobject_dealloc,          /* tp_dealloc */
     449    0,                                          /* tp_print */
     450    0,                                          /* tp_getattr */
     451    0,                                          /* tp_setattr */
     452    0,                                          /* tp_compare */
     453    0,                                          /* tp_repr */
     454    0,                                          /* tp_as_number */
     455    0,                                          /* tp_as_sequence */
     456    0,                                          /* tp_as_mapping */
     457    0,                                          /* tp_hash */
     458    0,                                          /* tp_call */
     459    0,                                          /* tp_str */
     460    PyObject_GenericGetAttr,                    /* tp_getattro */
     461    0,                                          /* tp_setattro */
     462    0,                                          /* tp_as_buffer */
     463    Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC,            /* tp_flags */
     464    teedataobject_doc,                          /* tp_doc */
     465    (traverseproc)teedataobject_traverse,       /* tp_traverse */
     466    (inquiry)teedataobject_clear,               /* tp_clear */
     467    0,                                          /* tp_richcompare */
     468    0,                                          /* tp_weaklistoffset */
     469    0,                                          /* tp_iter */
     470    0,                                          /* tp_iternext */
     471    0,                                          /* tp_methods */
     472    0,                                          /* tp_members */
     473    0,                                          /* tp_getset */
     474    0,                                          /* tp_base */
     475    0,                                          /* tp_dict */
     476    0,                                          /* tp_descr_get */
     477    0,                                          /* tp_descr_set */
     478    0,                                          /* tp_dictoffset */
     479    0,                                          /* tp_init */
     480    0,                                          /* tp_alloc */
     481    0,                                          /* tp_new */
     482    PyObject_GC_Del,                            /* tp_free */
    466483};
    467484
     
    472489tee_next(teeobject *to)
    473490{
    474         PyObject *value, *link;
    475 
    476         if (to->index >= LINKCELLS) {
    477                 link = teedataobject_jumplink(to->dataobj);
    478                 Py_DECREF(to->dataobj);
    479                 to->dataobj = (teedataobject *)link;
    480                 to->index = 0;
    481         }
    482         value = teedataobject_getitem(to->dataobj, to->index);
    483         if (value == NULL)
    484                 return NULL;
    485         to->index++;
    486         return value;
     491    PyObject *value, *link;
     492
     493    if (to->index >= LINKCELLS) {
     494        link = teedataobject_jumplink(to->dataobj);
     495        if (link == NULL)
     496            return NULL;
     497        Py_DECREF(to->dataobj);
     498        to->dataobj = (teedataobject *)link;
     499        to->index = 0;
     500    }
     501    value = teedataobject_getitem(to->dataobj, to->index);
     502    if (value == NULL)
     503        return NULL;
     504    to->index++;
     505    return value;
    487506}
    488507
     
    490509tee_traverse(teeobject *to, visitproc visit, void *arg)
    491510{
    492         Py_VISIT((PyObject *)to->dataobj);
    493         return 0;
     511    Py_VISIT((PyObject *)to->dataobj);
     512    return 0;
    494513}
    495514
     
    497516tee_copy(teeobject *to)
    498517{
    499         teeobject *newto;
    500 
    501         newto = PyObject_GC_New(teeobject, &tee_type);
    502         if (newto == NULL)
    503                 return NULL;
    504         Py_INCREF(to->dataobj);
    505         newto->dataobj = to->dataobj;
    506         newto->index = to->index;
    507         newto->weakreflist = NULL;
    508         PyObject_GC_Track(newto);
    509         return (PyObject *)newto;
     518    teeobject *newto;
     519
     520    newto = PyObject_GC_New(teeobject, &tee_type);
     521    if (newto == NULL)
     522        return NULL;
     523    Py_INCREF(to->dataobj);
     524    newto->dataobj = to->dataobj;
     525    newto->index = to->index;
     526    newto->weakreflist = NULL;
     527    PyObject_GC_Track(newto);
     528    return (PyObject *)newto;
    510529}
    511530
     
    515534tee_fromiterable(PyObject *iterable)
    516535{
    517         teeobject *to;
    518         PyObject *it = NULL;
    519 
    520         it = PyObject_GetIter(iterable);
    521         if (it == NULL)
    522                 return NULL;
    523         if (PyObject_TypeCheck(it, &tee_type)) {
    524                 to = (teeobject *)tee_copy((teeobject *)it);
    525                 goto done;
    526         }
    527 
    528         to = PyObject_GC_New(teeobject, &tee_type);
    529         if (to == NULL)
    530                 goto done;
    531         to->dataobj = (teedataobject *)teedataobject_new(it);
    532         if (!to->dataobj) {
    533                 PyObject_GC_Del(to);
    534                 to = NULL;
    535                 goto done;
    536         }
    537 
    538         to->index = 0;
    539         to->weakreflist = NULL;
    540         PyObject_GC_Track(to);
     536    teeobject *to;
     537    PyObject *it = NULL;
     538
     539    it = PyObject_GetIter(iterable);
     540    if (it == NULL)
     541        return NULL;
     542    if (PyObject_TypeCheck(it, &tee_type)) {
     543        to = (teeobject *)tee_copy((teeobject *)it);
     544        goto done;
     545    }
     546
     547    to = PyObject_GC_New(teeobject, &tee_type);
     548    if (to == NULL)
     549        goto done;
     550    to->dataobj = (teedataobject *)teedataobject_new(it);
     551    if (!to->dataobj) {
     552        PyObject_GC_Del(to);
     553        to = NULL;
     554        goto done;
     555    }
     556
     557    to->index = 0;
     558    to->weakreflist = NULL;
     559    PyObject_GC_Track(to);
    541560done:
    542         Py_XDECREF(it);
    543         return (PyObject *)to;
     561    Py_XDECREF(it);
     562    return (PyObject *)to;
    544563}
    545564
     
    547566tee_new(PyTypeObject *type, PyObject *args, PyObject *kw)
    548567{
    549         PyObject *iterable;
    550 
    551         if (!PyArg_UnpackTuple(args, "tee", 1, 1, &iterable))
    552                 return NULL;
    553         return tee_fromiterable(iterable);
     568    PyObject *iterable;
     569
     570    if (!PyArg_UnpackTuple(args, "tee", 1, 1, &iterable))
     571        return NULL;
     572    return tee_fromiterable(iterable);
    554573}
    555574
     
    557576tee_clear(teeobject *to)
    558577{
    559         if (to->weakreflist != NULL)
    560                 PyObject_ClearWeakRefs((PyObject *) to);
    561         Py_CLEAR(to->dataobj);
    562         return 0;
     578    if (to->weakreflist != NULL)
     579        PyObject_ClearWeakRefs((PyObject *) to);
     580    Py_CLEAR(to->dataobj);
     581    return 0;
    563582}
    564583
     
    566585tee_dealloc(teeobject *to)
    567586{
    568         PyObject_GC_UnTrack(to);
    569         tee_clear(to);
    570         PyObject_GC_Del(to);
     587    PyObject_GC_UnTrack(to);
     588    tee_clear(to);
     589    PyObject_GC_Del(to);
    571590}
    572591
     
    575594
    576595static PyMethodDef tee_methods[] = {
    577         {"__copy__",    (PyCFunction)tee_copy,  METH_NOARGS, teecopy_doc},
    578         {NULL,          NULL}           /* sentinel */
     596    {"__copy__",        (PyCFunction)tee_copy,  METH_NOARGS, teecopy_doc},
     597    {NULL,              NULL}           /* sentinel */
    579598};
    580599
    581600static PyTypeObject tee_type = {
    582         PyVarObject_HEAD_INIT(NULL, 0)
    583         "itertools.tee",                /* tp_name */
    584         sizeof(teeobject),              /* tp_basicsize */
    585         0,                              /* tp_itemsize */
    586         /* methods */
    587         (destructor)tee_dealloc,        /* tp_dealloc */
    588         0,                              /* tp_print */
    589         0,                              /* tp_getattr */
    590         0,                              /* tp_setattr */
    591         0,                              /* tp_compare */
    592         0,                              /* tp_repr */
    593         0,                              /* tp_as_number */
    594         0,                              /* tp_as_sequence */
    595         0,                              /* tp_as_mapping */
    596         0,                              /* tp_hash */
    597         0,                              /* tp_call */
    598         0,                              /* tp_str */
    599         0,                              /* tp_getattro */
    600         0,                              /* tp_setattro */
    601         0,                              /* tp_as_buffer */
    602         Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC,        /* tp_flags */
    603         teeobject_doc,                  /* tp_doc */
    604         (traverseproc)tee_traverse,     /* tp_traverse */
    605         (inquiry)tee_clear,             /* tp_clear */
    606         0,                              /* tp_richcompare */
    607         offsetof(teeobject, weakreflist),       /* tp_weaklistoffset */
    608         PyObject_SelfIter,              /* tp_iter */
    609         (iternextfunc)tee_next,         /* tp_iternext */
    610         tee_methods,                    /* tp_methods */
    611         0,                              /* tp_members */
    612         0,                              /* tp_getset */
    613         0,                              /* tp_base */
    614         0,                              /* tp_dict */
    615         0,                              /* tp_descr_get */
    616         0,                              /* tp_descr_set */
    617         0,                              /* tp_dictoffset */
    618         0,                              /* tp_init */
    619         0,                              /* tp_alloc */
    620         tee_new,                        /* tp_new */
    621         PyObject_GC_Del,                /* tp_free */
     601    PyVarObject_HEAD_INIT(NULL, 0)
     602    "itertools.tee",                    /* tp_name */
     603    sizeof(teeobject),                  /* tp_basicsize */
     604    0,                                  /* tp_itemsize */
     605    /* methods */
     606    (destructor)tee_dealloc,            /* tp_dealloc */
     607    0,                                  /* tp_print */
     608    0,                                  /* tp_getattr */
     609    0,                                  /* tp_setattr */
     610    0,                                  /* tp_compare */
     611    0,                                  /* tp_repr */
     612    0,                                  /* tp_as_number */
     613    0,                                  /* tp_as_sequence */
     614    0,                                  /* tp_as_mapping */
     615    0,                                  /* tp_hash */
     616    0,                                  /* tp_call */
     617    0,                                  /* tp_str */
     618    0,                                  /* tp_getattro */
     619    0,                                  /* tp_setattro */
     620    0,                                  /* tp_as_buffer */
     621    Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC,            /* tp_flags */
     622    teeobject_doc,                      /* tp_doc */
     623    (traverseproc)tee_traverse,         /* tp_traverse */
     624    (inquiry)tee_clear,                 /* tp_clear */
     625    0,                                  /* tp_richcompare */
     626    offsetof(teeobject, weakreflist),           /* tp_weaklistoffset */
     627    PyObject_SelfIter,                  /* tp_iter */
     628    (iternextfunc)tee_next,             /* tp_iternext */
     629    tee_methods,                        /* tp_methods */
     630    0,                                  /* tp_members */
     631    0,                                  /* tp_getset */
     632    0,                                  /* tp_base */
     633    0,                                  /* tp_dict */
     634    0,                                  /* tp_descr_get */
     635    0,                                  /* tp_descr_set */
     636    0,                                  /* tp_dictoffset */
     637    0,                                  /* tp_init */
     638    0,                                  /* tp_alloc */
     639    tee_new,                            /* tp_new */
     640    PyObject_GC_Del,                    /* tp_free */
    622641};
    623642
     
    625644tee(PyObject *self, PyObject *args)
    626645{
    627         Py_ssize_t i, n=2;
    628         PyObject *it, *iterable, *copyable, *result;
    629 
    630         if (!PyArg_ParseTuple(args, "O|n", &iterable, &n))
    631                 return NULL;
    632         if (n < 0) {
    633                 PyErr_SetString(PyExc_ValueError, "n must be >= 0");
    634                 return NULL;
    635         }
    636         result = PyTuple_New(n);
    637         if (result == NULL)
    638                 return NULL;
    639         if (n == 0)
    640                 return result;
    641         it = PyObject_GetIter(iterable);
    642         if (it == NULL) {
    643                 Py_DECREF(result);
    644                 return NULL;
    645         }
    646         if (!PyObject_HasAttrString(it, "__copy__")) {
    647                 copyable = tee_fromiterable(it);
    648                 Py_DECREF(it);
    649                 if (copyable == NULL) {
    650                         Py_DECREF(result);
    651                         return NULL;
    652                 }
    653         } else
    654                 copyable = it;
    655         PyTuple_SET_ITEM(result, 0, copyable);
    656         for (i=1 ; i<n ; i++) {
    657                 copyable = PyObject_CallMethod(copyable, "__copy__", NULL);
    658                 if (copyable == NULL) {
    659                         Py_DECREF(result);
    660                         return NULL;
    661                 }
    662                 PyTuple_SET_ITEM(result, i, copyable);
    663         }
    664         return result;
     646    Py_ssize_t i, n=2;
     647    PyObject *it, *iterable, *copyable, *result;
     648
     649    if (!PyArg_ParseTuple(args, "O|n", &iterable, &n))
     650        return NULL;
     651    if (n < 0) {
     652        PyErr_SetString(PyExc_ValueError, "n must be >= 0");
     653        return NULL;
     654    }
     655    result = PyTuple_New(n);
     656    if (result == NULL)
     657        return NULL;
     658    if (n == 0)
     659        return result;
     660    it = PyObject_GetIter(iterable);
     661    if (it == NULL) {
     662        Py_DECREF(result);
     663        return NULL;
     664    }
     665    if (!PyObject_HasAttrString(it, "__copy__")) {
     666        copyable = tee_fromiterable(it);
     667        Py_DECREF(it);
     668        if (copyable == NULL) {
     669            Py_DECREF(result);
     670            return NULL;
     671        }
     672    } else
     673        copyable = it;
     674    PyTuple_SET_ITEM(result, 0, copyable);
     675    for (i=1 ; i<n ; i++) {
     676        copyable = PyObject_CallMethod(copyable, "__copy__", NULL);
     677        if (copyable == NULL) {
     678            Py_DECREF(result);
     679            return NULL;
     680        }
     681        PyTuple_SET_ITEM(result, i, copyable);
     682    }
     683    return result;
    665684}
    666685
     
    672691
    673692typedef struct {
    674         PyObject_HEAD
    675         PyObject *it;
    676         PyObject *saved;
    677         int firstpass;
     693    PyObject_HEAD
     694    PyObject *it;
     695    PyObject *saved;
     696    int firstpass;
    678697} cycleobject;
    679698
     
    683702cycle_new(PyTypeObject *type, PyObject *args, PyObject *kwds)
    684703{
    685         PyObject *it;
    686         PyObject *iterable;
    687         PyObject *saved;
    688         cycleobject *lz;
    689 
    690         if (type == &cycle_type && !_PyArg_NoKeywords("cycle()", kwds))
    691                 return NULL;
    692 
    693         if (!PyArg_UnpackTuple(args, "cycle", 1, 1, &iterable))
    694                 return NULL;
    695 
    696         /* Get iterator. */
    697         it = PyObject_GetIter(iterable);
    698         if (it == NULL)
    699                 return NULL;
    700 
    701         saved = PyList_New(0);
    702         if (saved == NULL) {
    703                 Py_DECREF(it);
    704                 return NULL;
    705         }
    706 
    707         /* create cycleobject structure */
    708         lz = (cycleobject *)type->tp_alloc(type, 0);
    709         if (lz == NULL) {
    710                 Py_DECREF(it);
    711                 Py_DECREF(saved);
    712                 return NULL;
    713         }
    714         lz->it = it;
    715         lz->saved = saved;
    716         lz->firstpass = 0;
    717 
    718         return (PyObject *)lz;
     704    PyObject *it;
     705    PyObject *iterable;
     706    PyObject *saved;
     707    cycleobject *lz;
     708
     709    if (type == &cycle_type && !_PyArg_NoKeywords("cycle()", kwds))
     710        return NULL;
     711
     712    if (!PyArg_UnpackTuple(args, "cycle", 1, 1, &iterable))
     713        return NULL;
     714
     715    /* Get iterator. */
     716    it = PyObject_GetIter(iterable);
     717    if (it == NULL)
     718        return NULL;
     719
     720    saved = PyList_New(0);
     721    if (saved == NULL) {
     722        Py_DECREF(it);
     723        return NULL;
     724    }
     725
     726    /* create cycleobject structure */
     727    lz = (cycleobject *)type->tp_alloc(type, 0);
     728    if (lz == NULL) {
     729        Py_DECREF(it);
     730        Py_DECREF(saved);
     731        return NULL;
     732    }
     733    lz->it = it;
     734    lz->saved = saved;
     735    lz->firstpass = 0;
     736
     737    return (PyObject *)lz;
    719738}
    720739
     
    722741cycle_dealloc(cycleobject *lz)
    723742{
    724         PyObject_GC_UnTrack(lz);
    725         Py_XDECREF(lz->saved);
    726         Py_XDECREF(lz->it);
    727         Py_TYPE(lz)->tp_free(lz);
     743    PyObject_GC_UnTrack(lz);
     744    Py_XDECREF(lz->saved);
     745    Py_XDECREF(lz->it);
     746    Py_TYPE(lz)->tp_free(lz);
    728747}
    729748
     
    731750cycle_traverse(cycleobject *lz, visitproc visit, void *arg)
    732751{
    733         Py_VISIT(lz->it);
    734         Py_VISIT(lz->saved);
    735         return 0;
     752    Py_VISIT(lz->it);
     753    Py_VISIT(lz->saved);
     754    return 0;
    736755}
    737756
     
    739758cycle_next(cycleobject *lz)
    740759{
    741         PyObject *item;
    742         PyObject *it;
    743         PyObject *tmp;
    744 
    745         while (1) {
    746                 item = PyIter_Next(lz->it);
    747                 if (item != NULL) {
    748                         if (!lz->firstpass)
    749                                 PyList_Append(lz->saved, item);
    750                         return item;
    751                 }
    752                 if (PyErr_Occurred()) {
    753                         if (PyErr_ExceptionMatches(PyExc_StopIteration))
    754                                 PyErr_Clear();
    755                         else
    756                                 return NULL;
    757                 }
    758                 if (PyList_Size(lz->saved) == 0)
    759                         return NULL;
    760                 it = PyObject_GetIter(lz->saved);
    761                 if (it == NULL)
    762                         return NULL;
    763                 tmp = lz->it;
    764                 lz->it = it;
    765                 lz->firstpass = 1;
    766                 Py_DECREF(tmp);
    767         }
     760    PyObject *item;
     761    PyObject *it;
     762    PyObject *tmp;
     763
     764    while (1) {
     765        item = PyIter_Next(lz->it);
     766        if (item != NULL) {
     767            if (!lz->firstpass && PyList_Append(lz->saved, item)) {
     768                Py_DECREF(item);
     769                return NULL;
     770            }
     771            return item;
     772        }
     773        if (PyErr_Occurred()) {
     774            if (PyErr_ExceptionMatches(PyExc_StopIteration))
     775                PyErr_Clear();
     776            else
     777                return NULL;
     778        }
     779        if (PyList_Size(lz->saved) == 0)
     780            return NULL;
     781        it = PyObject_GetIter(lz->saved);
     782        if (it == NULL)
     783            return NULL;
     784        tmp = lz->it;
     785        lz->it = it;
     786        lz->firstpass = 1;
     787        Py_DECREF(tmp);
     788    }
    768789}
    769790
     
    775796
    776797static PyTypeObject cycle_type = {
    777         PyVarObject_HEAD_INIT(NULL, 0)
    778         "itertools.cycle",              /* tp_name */
    779         sizeof(cycleobject),            /* tp_basicsize */
    780         0,                              /* tp_itemsize */
    781         /* methods */
    782         (destructor)cycle_dealloc,      /* tp_dealloc */
    783         0,                              /* tp_print */
    784         0,                              /* tp_getattr */
    785         0,                              /* tp_setattr */
    786         0,                              /* tp_compare */
    787         0,                              /* tp_repr */
    788         0,                              /* tp_as_number */
    789         0,                              /* tp_as_sequence */
    790         0,                              /* tp_as_mapping */
    791         0,                              /* tp_hash */
    792         0,                              /* tp_call */
    793         0,                              /* tp_str */
    794         PyObject_GenericGetAttr,        /* tp_getattro */
    795         0,                              /* tp_setattro */
    796         0,                              /* tp_as_buffer */
    797         Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC |
    798                 Py_TPFLAGS_BASETYPE,    /* tp_flags */
    799         cycle_doc,                      /* tp_doc */
    800         (traverseproc)cycle_traverse,   /* tp_traverse */
    801         0,                              /* tp_clear */
    802         0,                              /* tp_richcompare */
    803         0,                              /* tp_weaklistoffset */
    804         PyObject_SelfIter,              /* tp_iter */
    805         (iternextfunc)cycle_next,       /* tp_iternext */
    806         0,                              /* tp_methods */
    807         0,                              /* tp_members */
    808         0,                              /* tp_getset */
    809         0,                              /* tp_base */
    810         0,                              /* tp_dict */
    811         0,                              /* tp_descr_get */
    812         0,                              /* tp_descr_set */
    813         0,                              /* tp_dictoffset */
    814         0,                              /* tp_init */
    815         0,                              /* tp_alloc */
    816         cycle_new,                      /* tp_new */
    817         PyObject_GC_Del,                /* tp_free */
     798    PyVarObject_HEAD_INIT(NULL, 0)
     799    "itertools.cycle",                  /* tp_name */
     800    sizeof(cycleobject),                /* tp_basicsize */
     801    0,                                  /* tp_itemsize */
     802    /* methods */
     803    (destructor)cycle_dealloc,          /* tp_dealloc */
     804    0,                                  /* tp_print */
     805    0,                                  /* tp_getattr */
     806    0,                                  /* tp_setattr */
     807    0,                                  /* tp_compare */
     808    0,                                  /* tp_repr */
     809    0,                                  /* tp_as_number */
     810    0,                                  /* tp_as_sequence */
     811    0,                                  /* tp_as_mapping */
     812    0,                                  /* tp_hash */
     813    0,                                  /* tp_call */
     814    0,                                  /* tp_str */
     815    PyObject_GenericGetAttr,            /* tp_getattro */
     816    0,                                  /* tp_setattro */
     817    0,                                  /* tp_as_buffer */
     818    Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC |
     819        Py_TPFLAGS_BASETYPE,            /* tp_flags */
     820    cycle_doc,                          /* tp_doc */
     821    (traverseproc)cycle_traverse,       /* tp_traverse */
     822    0,                                  /* tp_clear */
     823    0,                                  /* tp_richcompare */
     824    0,                                  /* tp_weaklistoffset */
     825    PyObject_SelfIter,                  /* tp_iter */
     826    (iternextfunc)cycle_next,           /* tp_iternext */
     827    0,                                  /* tp_methods */
     828    0,                                  /* tp_members */
     829    0,                                  /* tp_getset */
     830    0,                                  /* tp_base */
     831    0,                                  /* tp_dict */
     832    0,                                  /* tp_descr_get */
     833    0,                                  /* tp_descr_set */
     834    0,                                  /* tp_dictoffset */
     835    0,                                  /* tp_init */
     836    0,                                  /* tp_alloc */
     837    cycle_new,                          /* tp_new */
     838    PyObject_GC_Del,                    /* tp_free */
    818839};
    819840
     
    822843
    823844typedef struct {
    824         PyObject_HEAD
    825         PyObject *func;
    826         PyObject *it;
    827         long    start;
     845    PyObject_HEAD
     846    PyObject *func;
     847    PyObject *it;
     848    long        start;
    828849} dropwhileobject;
    829850
     
    833854dropwhile_new(PyTypeObject *type, PyObject *args, PyObject *kwds)
    834855{
    835         PyObject *func, *seq;
    836         PyObject *it;
    837         dropwhileobject *lz;
    838 
    839         if (type == &dropwhile_type && !_PyArg_NoKeywords("dropwhile()", kwds))
    840                 return NULL;
    841 
    842         if (!PyArg_UnpackTuple(args, "dropwhile", 2, 2, &func, &seq))
    843                 return NULL;
    844 
    845         /* Get iterator. */
    846         it = PyObject_GetIter(seq);
    847         if (it == NULL)
    848                 return NULL;
    849 
    850         /* create dropwhileobject structure */
    851         lz = (dropwhileobject *)type->tp_alloc(type, 0);
    852         if (lz == NULL) {
    853                 Py_DECREF(it);
    854                 return NULL;
    855         }
    856         Py_INCREF(func);
    857         lz->func = func;
    858         lz->it = it;
    859         lz->start = 0;
    860 
    861         return (PyObject *)lz;
     856    PyObject *func, *seq;
     857    PyObject *it;
     858    dropwhileobject *lz;
     859
     860    if (type == &dropwhile_type && !_PyArg_NoKeywords("dropwhile()", kwds))
     861        return NULL;
     862
     863    if (!PyArg_UnpackTuple(args, "dropwhile", 2, 2, &func, &seq))
     864        return NULL;
     865
     866    /* Get iterator. */
     867    it = PyObject_GetIter(seq);
     868    if (it == NULL)
     869        return NULL;
     870
     871    /* create dropwhileobject structure */
     872    lz = (dropwhileobject *)type->tp_alloc(type, 0);
     873    if (lz == NULL) {
     874        Py_DECREF(it);
     875        return NULL;
     876    }
     877    Py_INCREF(func);
     878    lz->func = func;
     879    lz->it = it;
     880    lz->start = 0;
     881
     882    return (PyObject *)lz;
    862883}
    863884
     
    865886dropwhile_dealloc(dropwhileobject *lz)
    866887{
    867         PyObject_GC_UnTrack(lz);
    868         Py_XDECREF(lz->func);
    869         Py_XDECREF(lz->it);
    870         Py_TYPE(lz)->tp_free(lz);
     888    PyObject_GC_UnTrack(lz);
     889    Py_XDECREF(lz->func);
     890    Py_XDECREF(lz->it);
     891    Py_TYPE(lz)->tp_free(lz);
    871892}
    872893
     
    874895dropwhile_traverse(dropwhileobject *lz, visitproc visit, void *arg)
    875896{
    876         Py_VISIT(lz->it);
    877         Py_VISIT(lz->func);
    878         return 0;
     897    Py_VISIT(lz->it);
     898    Py_VISIT(lz->func);
     899    return 0;
    879900}
    880901
     
    882903dropwhile_next(dropwhileobject *lz)
    883904{
    884         PyObject *item, *good;
    885         PyObject *it = lz->it;
    886         long ok;
    887         PyObject *(*iternext)(PyObject *);
    888 
    889         assert(PyIter_Check(it));
    890         iternext = *Py_TYPE(it)->tp_iternext;
    891         for (;;) {
    892                 item = iternext(it);
    893                 if (item == NULL)
    894                         return NULL;
    895                 if (lz->start == 1)
    896                         return item;
    897 
    898                 good = PyObject_CallFunctionObjArgs(lz->func, item, NULL);
    899                 if (good == NULL) {
    900                         Py_DECREF(item);
    901                         return NULL;
    902                 }
    903                 ok = PyObject_IsTrue(good);
    904                 Py_DECREF(good);
    905                 if (!ok) {
    906                         lz->start = 1;
    907                         return item;
    908                 }
    909                 Py_DECREF(item);
    910         }
     905    PyObject *item, *good;
     906    PyObject *it = lz->it;
     907    long ok;
     908    PyObject *(*iternext)(PyObject *);
     909
     910    iternext = *Py_TYPE(it)->tp_iternext;
     911    for (;;) {
     912        item = iternext(it);
     913        if (item == NULL)
     914            return NULL;
     915        if (lz->start == 1)
     916            return item;
     917
     918        good = PyObject_CallFunctionObjArgs(lz->func, item, NULL);
     919        if (good == NULL) {
     920            Py_DECREF(item);
     921            return NULL;
     922        }
     923        ok = PyObject_IsTrue(good);
     924        Py_DECREF(good);
     925        if (ok == 0) {
     926            lz->start = 1;
     927            return item;
     928        }
     929        Py_DECREF(item);
     930        if (ok < 0)
     931            return NULL;
     932    }
    911933}
    912934
     
    918940
    919941static PyTypeObject dropwhile_type = {
    920         PyVarObject_HEAD_INIT(NULL, 0)
    921         "itertools.dropwhile",          /* tp_name */
    922         sizeof(dropwhileobject),        /* tp_basicsize */
    923         0,                              /* tp_itemsize */
    924         /* methods */
    925         (destructor)dropwhile_dealloc,  /* tp_dealloc */
    926         0,                              /* tp_print */
    927         0,                              /* tp_getattr */
    928         0,                              /* tp_setattr */
    929         0,                              /* tp_compare */
    930         0,                              /* tp_repr */
    931         0,                              /* tp_as_number */
    932         0,                              /* tp_as_sequence */
    933         0,                              /* tp_as_mapping */
    934         0,                              /* tp_hash */
    935         0,                              /* tp_call */
    936         0,                              /* tp_str */
    937         PyObject_GenericGetAttr,        /* tp_getattro */
    938         0,                              /* tp_setattro */
    939         0,                              /* tp_as_buffer */
    940         Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC |
    941                 Py_TPFLAGS_BASETYPE,    /* tp_flags */
    942         dropwhile_doc,                  /* tp_doc */
    943         (traverseproc)dropwhile_traverse,    /* tp_traverse */
    944         0,                              /* tp_clear */
    945         0,                              /* tp_richcompare */
    946         0,                              /* tp_weaklistoffset */
    947         PyObject_SelfIter,              /* tp_iter */
    948         (iternextfunc)dropwhile_next,   /* tp_iternext */
    949         0,                              /* tp_methods */
    950         0,                              /* tp_members */
    951         0,                              /* tp_getset */
    952         0,                              /* tp_base */
    953         0,                              /* tp_dict */
    954         0,                              /* tp_descr_get */
    955         0,                              /* tp_descr_set */
    956         0,                              /* tp_dictoffset */
    957         0,                              /* tp_init */
    958         0,                              /* tp_alloc */
    959         dropwhile_new,                  /* tp_new */
    960         PyObject_GC_Del,                /* tp_free */
     942    PyVarObject_HEAD_INIT(NULL, 0)
     943    "itertools.dropwhile",              /* tp_name */
     944    sizeof(dropwhileobject),            /* tp_basicsize */
     945    0,                                  /* tp_itemsize */
     946    /* methods */
     947    (destructor)dropwhile_dealloc,      /* tp_dealloc */
     948    0,                                  /* tp_print */
     949    0,                                  /* tp_getattr */
     950    0,                                  /* tp_setattr */
     951    0,                                  /* tp_compare */
     952    0,                                  /* tp_repr */
     953    0,                                  /* tp_as_number */
     954    0,                                  /* tp_as_sequence */
     955    0,                                  /* tp_as_mapping */
     956    0,                                  /* tp_hash */
     957    0,                                  /* tp_call */
     958    0,                                  /* tp_str */
     959    PyObject_GenericGetAttr,            /* tp_getattro */
     960    0,                                  /* tp_setattro */
     961    0,                                  /* tp_as_buffer */
     962    Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC |
     963        Py_TPFLAGS_BASETYPE,            /* tp_flags */
     964    dropwhile_doc,                      /* tp_doc */
     965    (traverseproc)dropwhile_traverse,    /* tp_traverse */
     966    0,                                  /* tp_clear */
     967    0,                                  /* tp_richcompare */
     968    0,                                  /* tp_weaklistoffset */
     969    PyObject_SelfIter,                  /* tp_iter */
     970    (iternextfunc)dropwhile_next,       /* tp_iternext */
     971    0,                                  /* tp_methods */
     972    0,                                  /* tp_members */
     973    0,                                  /* tp_getset */
     974    0,                                  /* tp_base */
     975    0,                                  /* tp_dict */
     976    0,                                  /* tp_descr_get */
     977    0,                                  /* tp_descr_set */
     978    0,                                  /* tp_dictoffset */
     979    0,                                  /* tp_init */
     980    0,                                  /* tp_alloc */
     981    dropwhile_new,                      /* tp_new */
     982    PyObject_GC_Del,                    /* tp_free */
    961983};
    962984
     
    965987
    966988typedef struct {
    967         PyObject_HEAD
    968         PyObject *func;
    969         PyObject *it;
    970         long    stop;
     989    PyObject_HEAD
     990    PyObject *func;
     991    PyObject *it;
     992    long        stop;
    971993} takewhileobject;
    972994
     
    976998takewhile_new(PyTypeObject *type, PyObject *args, PyObject *kwds)
    977999{
    978         PyObject *func, *seq;
    979         PyObject *it;
    980         takewhileobject *lz;
    981 
    982         if (type == &takewhile_type && !_PyArg_NoKeywords("takewhile()", kwds))
    983                 return NULL;
    984 
    985         if (!PyArg_UnpackTuple(args, "takewhile", 2, 2, &func, &seq))
    986                 return NULL;
    987 
    988         /* Get iterator. */
    989         it = PyObject_GetIter(seq);
    990         if (it == NULL)
    991                 return NULL;
    992 
    993         /* create takewhileobject structure */
    994         lz = (takewhileobject *)type->tp_alloc(type, 0);
    995         if (lz == NULL) {
    996                 Py_DECREF(it);
    997                 return NULL;
    998         }
    999         Py_INCREF(func);
    1000         lz->func = func;
    1001         lz->it = it;
    1002         lz->stop = 0;
    1003 
    1004         return (PyObject *)lz;
     1000    PyObject *func, *seq;
     1001    PyObject *it;
     1002    takewhileobject *lz;
     1003
     1004    if (type == &takewhile_type && !_PyArg_NoKeywords("takewhile()", kwds))
     1005        return NULL;
     1006
     1007    if (!PyArg_UnpackTuple(args, "takewhile", 2, 2, &func, &seq))
     1008        return NULL;
     1009
     1010    /* Get iterator. */
     1011    it = PyObject_GetIter(seq);
     1012    if (it == NULL)
     1013        return NULL;
     1014
     1015    /* create takewhileobject structure */
     1016    lz = (takewhileobject *)type->tp_alloc(type, 0);
     1017    if (lz == NULL) {
     1018        Py_DECREF(it);
     1019        return NULL;
     1020    }
     1021    Py_INCREF(func);
     1022    lz->func = func;
     1023    lz->it = it;
     1024    lz->stop = 0;
     1025
     1026    return (PyObject *)lz;
    10051027}
    10061028
     
    10081030takewhile_dealloc(takewhileobject *lz)
    10091031{
    1010         PyObject_GC_UnTrack(lz);
    1011         Py_XDECREF(lz->func);
    1012         Py_XDECREF(lz->it);
    1013         Py_TYPE(lz)->tp_free(lz);
     1032    PyObject_GC_UnTrack(lz);
     1033    Py_XDECREF(lz->func);
     1034    Py_XDECREF(lz->it);
     1035    Py_TYPE(lz)->tp_free(lz);
    10141036}
    10151037
     
    10171039takewhile_traverse(takewhileobject *lz, visitproc visit, void *arg)
    10181040{
    1019         Py_VISIT(lz->it);
    1020         Py_VISIT(lz->func);
    1021         return 0;
     1041    Py_VISIT(lz->it);
     1042    Py_VISIT(lz->func);
     1043    return 0;
    10221044}
    10231045
     
    10251047takewhile_next(takewhileobject *lz)
    10261048{
    1027         PyObject *item, *good;
    1028         PyObject *it = lz->it;
    1029         long ok;
    1030 
    1031         if (lz->stop == 1)
    1032                 return NULL;
    1033 
    1034         assert(PyIter_Check(it));
    1035         item = (*Py_TYPE(it)->tp_iternext)(it);
    1036         if (item == NULL)
    1037                 return NULL;
    1038 
    1039         good = PyObject_CallFunctionObjArgs(lz->func, item, NULL);
    1040         if (good == NULL) {
    1041                 Py_DECREF(item);
    1042                 return NULL;
    1043         }
    1044         ok = PyObject_IsTrue(good);
    1045         Py_DECREF(good);
    1046         if (ok)
    1047                 return item;
    1048         Py_DECREF(item);
    1049         lz->stop = 1;
    1050         return NULL;
     1049    PyObject *item, *good;
     1050    PyObject *it = lz->it;
     1051    long ok;
     1052
     1053    if (lz->stop == 1)
     1054        return NULL;
     1055
     1056    item = (*Py_TYPE(it)->tp_iternext)(it);
     1057    if (item == NULL)
     1058        return NULL;
     1059
     1060    good = PyObject_CallFunctionObjArgs(lz->func, item, NULL);
     1061    if (good == NULL) {
     1062        Py_DECREF(item);
     1063        return NULL;
     1064    }
     1065    ok = PyObject_IsTrue(good);
     1066    Py_DECREF(good);
     1067    if (ok > 0)
     1068        return item;
     1069    Py_DECREF(item);
     1070    if (ok == 0)
     1071        lz->stop = 1;
     1072    return NULL;
    10511073}
    10521074
     
    10581080
    10591081static PyTypeObject takewhile_type = {
    1060         PyVarObject_HEAD_INIT(NULL, 0)
    1061         "itertools.takewhile",          /* tp_name */
    1062         sizeof(takewhileobject),        /* tp_basicsize */
    1063         0,                              /* tp_itemsize */
    1064         /* methods */
    1065         (destructor)takewhile_dealloc,  /* tp_dealloc */
    1066         0,                              /* tp_print */
    1067         0,                              /* tp_getattr */
    1068         0,                              /* tp_setattr */
    1069         0,                              /* tp_compare */
    1070         0,                              /* tp_repr */
    1071         0,                              /* tp_as_number */
    1072         0,                              /* tp_as_sequence */
    1073         0,                              /* tp_as_mapping */
    1074         0,                              /* tp_hash */
    1075         0,                              /* tp_call */
    1076         0,                              /* tp_str */
    1077         PyObject_GenericGetAttr,        /* tp_getattro */
    1078         0,                              /* tp_setattro */
    1079         0,                              /* tp_as_buffer */
    1080         Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC |
    1081                 Py_TPFLAGS_BASETYPE,    /* tp_flags */
    1082         takewhile_doc,                  /* tp_doc */
    1083         (traverseproc)takewhile_traverse,    /* tp_traverse */
    1084         0,                              /* tp_clear */
    1085         0,                              /* tp_richcompare */
    1086         0,                              /* tp_weaklistoffset */
    1087         PyObject_SelfIter,              /* tp_iter */
    1088         (iternextfunc)takewhile_next,   /* tp_iternext */
    1089         0,                              /* tp_methods */
    1090         0,                              /* tp_members */
    1091         0,                              /* tp_getset */
    1092         0,                              /* tp_base */
    1093         0,                              /* tp_dict */
    1094         0,                              /* tp_descr_get */
    1095         0,                              /* tp_descr_set */
    1096         0,                              /* tp_dictoffset */
    1097         0,                              /* tp_init */
    1098         0,                              /* tp_alloc */
    1099         takewhile_new,                  /* tp_new */
    1100         PyObject_GC_Del,                /* tp_free */
     1082    PyVarObject_HEAD_INIT(NULL, 0)
     1083    "itertools.takewhile",              /* tp_name */
     1084    sizeof(takewhileobject),            /* tp_basicsize */
     1085    0,                                  /* tp_itemsize */
     1086    /* methods */
     1087    (destructor)takewhile_dealloc,      /* tp_dealloc */
     1088    0,                                  /* tp_print */
     1089    0,                                  /* tp_getattr */
     1090    0,                                  /* tp_setattr */
     1091    0,                                  /* tp_compare */
     1092    0,                                  /* tp_repr */
     1093    0,                                  /* tp_as_number */
     1094    0,                                  /* tp_as_sequence */
     1095    0,                                  /* tp_as_mapping */
     1096    0,                                  /* tp_hash */
     1097    0,                                  /* tp_call */
     1098    0,                                  /* tp_str */
     1099    PyObject_GenericGetAttr,            /* tp_getattro */
     1100    0,                                  /* tp_setattro */
     1101    0,                                  /* tp_as_buffer */
     1102    Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC |
     1103        Py_TPFLAGS_BASETYPE,            /* tp_flags */
     1104    takewhile_doc,                      /* tp_doc */
     1105    (traverseproc)takewhile_traverse,    /* tp_traverse */
     1106    0,                                  /* tp_clear */
     1107    0,                                  /* tp_richcompare */
     1108    0,                                  /* tp_weaklistoffset */
     1109    PyObject_SelfIter,                  /* tp_iter */
     1110    (iternextfunc)takewhile_next,       /* tp_iternext */
     1111    0,                                  /* tp_methods */
     1112    0,                                  /* tp_members */
     1113    0,                                  /* tp_getset */
     1114    0,                                  /* tp_base */
     1115    0,                                  /* tp_dict */
     1116    0,                                  /* tp_descr_get */
     1117    0,                                  /* tp_descr_set */
     1118    0,                                  /* tp_dictoffset */
     1119    0,                                  /* tp_init */
     1120    0,                                  /* tp_alloc */
     1121    takewhile_new,                      /* tp_new */
     1122    PyObject_GC_Del,                    /* tp_free */
    11011123};
    11021124
     
    11051127
    11061128typedef struct {
    1107         PyObject_HEAD
    1108         PyObject *it;
    1109         Py_ssize_t next;
    1110         Py_ssize_t stop;
    1111         Py_ssize_t step;
    1112         Py_ssize_t cnt;
     1129    PyObject_HEAD
     1130    PyObject *it;
     1131    Py_ssize_t next;
     1132    Py_ssize_t stop;
     1133    Py_ssize_t step;
     1134    Py_ssize_t cnt;
    11131135} isliceobject;
    11141136
     
    11181140islice_new(PyTypeObject *type, PyObject *args, PyObject *kwds)
    11191141{
    1120         PyObject *seq;
    1121         Py_ssize_t start=0, stop=-1, step=1;
    1122         PyObject *it, *a1=NULL, *a2=NULL, *a3=NULL;
    1123         Py_ssize_t numargs;
    1124         isliceobject *lz;
    1125 
    1126         if (type == &islice_type && !_PyArg_NoKeywords("islice()", kwds))
    1127                 return NULL;
    1128 
    1129         if (!PyArg_UnpackTuple(args, "islice", 2, 4, &seq, &a1, &a2, &a3))
    1130                 return NULL;
    1131 
    1132         numargs = PyTuple_Size(args);
    1133         if (numargs == 2) {
    1134                 if (a1 != Py_None) {
    1135                         stop = PyInt_AsSsize_t(a1);
    1136                         if (stop == -1) {
    1137                                 if (PyErr_Occurred())
    1138                                         PyErr_Clear();
    1139                                 PyErr_SetString(PyExc_ValueError,
    1140                                    "Stop argument for islice() must be a non-negative integer or None.");
    1141                                 return NULL;
    1142                         }
    1143                 }
    1144         } else {
    1145                 if (a1 != Py_None)
    1146                         start = PyInt_AsSsize_t(a1);
    1147                 if (start == -1 && PyErr_Occurred())
    1148                         PyErr_Clear();
    1149                 if (a2 != Py_None) {
    1150                         stop = PyInt_AsSsize_t(a2);
    1151                         if (stop == -1) {
    1152                                 if (PyErr_Occurred())
    1153                                         PyErr_Clear();
    1154                                 PyErr_SetString(PyExc_ValueError,
    1155                                    "Stop argument for islice() must be a non-negative integer or None.");
    1156                                 return NULL;
    1157                         }
    1158                 }
    1159         }
    1160         if (start<0 || stop<-1) {
    1161                 PyErr_SetString(PyExc_ValueError,
    1162                    "Indices for islice() must be non-negative integers or None.");
    1163                 return NULL;
    1164         }
    1165 
    1166         if (a3 != NULL) {
    1167                 if (a3 != Py_None)
    1168                         step = PyInt_AsSsize_t(a3);
    1169                 if (step == -1 && PyErr_Occurred())
    1170                         PyErr_Clear();
    1171         }
    1172         if (step<1) {
    1173                 PyErr_SetString(PyExc_ValueError,
    1174                    "Step for islice() must be a positive integer or None.");
    1175                 return NULL;
    1176         }
    1177 
    1178         /* Get iterator. */
    1179         it = PyObject_GetIter(seq);
    1180         if (it == NULL)
    1181                 return NULL;
    1182 
    1183         /* create isliceobject structure */
    1184         lz = (isliceobject *)type->tp_alloc(type, 0);
    1185         if (lz == NULL) {
    1186                 Py_DECREF(it);
    1187                 return NULL;
    1188         }
    1189         lz->it = it;
    1190         lz->next = start;
    1191         lz->stop = stop;
    1192         lz->step = step;
    1193         lz->cnt = 0L;
    1194 
    1195         return (PyObject *)lz;
     1142    PyObject *seq;
     1143    Py_ssize_t start=0, stop=-1, step=1;
     1144    PyObject *it, *a1=NULL, *a2=NULL, *a3=NULL;
     1145    Py_ssize_t numargs;
     1146    isliceobject *lz;
     1147
     1148    if (type == &islice_type && !_PyArg_NoKeywords("islice()", kwds))
     1149        return NULL;
     1150
     1151    if (!PyArg_UnpackTuple(args, "islice", 2, 4, &seq, &a1, &a2, &a3))
     1152        return NULL;
     1153
     1154    numargs = PyTuple_Size(args);
     1155    if (numargs == 2) {
     1156        if (a1 != Py_None) {
     1157            stop = PyInt_AsSsize_t(a1);
     1158            if (stop == -1) {
     1159                if (PyErr_Occurred())
     1160                    PyErr_Clear();
     1161                PyErr_SetString(PyExc_ValueError,
     1162                    "Stop argument for islice() must be None or an integer: 0 <= x <= maxint.");
     1163                return NULL;
     1164            }
     1165        }
     1166    } else {
     1167        if (a1 != Py_None)
     1168            start = PyInt_AsSsize_t(a1);
     1169        if (start == -1 && PyErr_Occurred())
     1170            PyErr_Clear();
     1171        if (a2 != Py_None) {
     1172            stop = PyInt_AsSsize_t(a2);
     1173            if (stop == -1) {
     1174                if (PyErr_Occurred())
     1175                    PyErr_Clear();
     1176                PyErr_SetString(PyExc_ValueError,
     1177                   "Stop argument for islice() must be None or an integer: 0 <= x <= maxint.");
     1178                return NULL;
     1179            }
     1180        }
     1181    }
     1182    if (start<0 || stop<-1) {
     1183        PyErr_SetString(PyExc_ValueError,
     1184           "Indices for islice() must be None or an integer: 0 <= x <= maxint.");
     1185        return NULL;
     1186    }
     1187
     1188    if (a3 != NULL) {
     1189        if (a3 != Py_None)
     1190            step = PyInt_AsSsize_t(a3);
     1191        if (step == -1 && PyErr_Occurred())
     1192            PyErr_Clear();
     1193    }
     1194    if (step<1) {
     1195        PyErr_SetString(PyExc_ValueError,
     1196           "Step for islice() must be a positive integer or None.");
     1197        return NULL;
     1198    }
     1199
     1200    /* Get iterator. */
     1201    it = PyObject_GetIter(seq);
     1202    if (it == NULL)
     1203        return NULL;
     1204
     1205    /* create isliceobject structure */
     1206    lz = (isliceobject *)type->tp_alloc(type, 0);
     1207    if (lz == NULL) {
     1208        Py_DECREF(it);
     1209        return NULL;
     1210    }
     1211    lz->it = it;
     1212    lz->next = start;
     1213    lz->stop = stop;
     1214    lz->step = step;
     1215    lz->cnt = 0L;
     1216
     1217    return (PyObject *)lz;
    11961218}
    11971219
     
    11991221islice_dealloc(isliceobject *lz)
    12001222{
    1201         PyObject_GC_UnTrack(lz);
    1202         Py_XDECREF(lz->it);
    1203         Py_TYPE(lz)->tp_free(lz);
     1223    PyObject_GC_UnTrack(lz);
     1224    Py_XDECREF(lz->it);
     1225    Py_TYPE(lz)->tp_free(lz);
    12041226}
    12051227
     
    12071229islice_traverse(isliceobject *lz, visitproc visit, void *arg)
    12081230{
    1209         Py_VISIT(lz->it);
    1210         return 0;
     1231    Py_VISIT(lz->it);
     1232    return 0;
    12111233}
    12121234
     
    12141236islice_next(isliceobject *lz)
    12151237{
    1216         PyObject *item;
    1217         PyObject *it = lz->it;
    1218         Py_ssize_t oldnext;
    1219         PyObject *(*iternext)(PyObject *);
    1220 
    1221         assert(PyIter_Check(it));
    1222         iternext = *Py_TYPE(it)->tp_iternext;
    1223         while (lz->cnt < lz->next) {
    1224                 item = iternext(it);
    1225                 if (item == NULL)
    1226                         return NULL;
    1227                 Py_DECREF(item);
    1228                 lz->cnt++;
    1229         }
    1230         if (lz->stop != -1 && lz->cnt >= lz->stop)
    1231                 return NULL;
    1232         assert(PyIter_Check(it));
    1233         item = iternext(it);
    1234         if (item == NULL)
    1235                 return NULL;
    1236         lz->cnt++;
    1237         oldnext = lz->next;
    1238         lz->next += lz->step;
    1239         if (lz->next < oldnext) /* Check for overflow */
    1240                 lz->next = lz->stop;
    1241         return item;
     1238    PyObject *item;
     1239    PyObject *it = lz->it;
     1240    Py_ssize_t stop = lz->stop;
     1241    Py_ssize_t oldnext;
     1242    PyObject *(*iternext)(PyObject *);
     1243
     1244    iternext = *Py_TYPE(it)->tp_iternext;
     1245    while (lz->cnt < lz->next) {
     1246        item = iternext(it);
     1247        if (item == NULL)
     1248            return NULL;
     1249        Py_DECREF(item);
     1250        lz->cnt++;
     1251    }
     1252    if (stop != -1 && lz->cnt >= stop)
     1253        return NULL;
     1254    item = iternext(it);
     1255    if (item == NULL)
     1256        return NULL;
     1257    lz->cnt++;
     1258    oldnext = lz->next;
     1259    /* The (size_t) cast below avoids the danger of undefined
     1260       behaviour from signed integer overflow. */
     1261    lz->next += (size_t)lz->step;
     1262    if (lz->next < oldnext || (stop != -1 && lz->next > stop))
     1263        lz->next = stop;
     1264    return item;
    12421265}
    12431266
     
    12531276
    12541277static PyTypeObject islice_type = {
    1255         PyVarObject_HEAD_INIT(NULL, 0)
    1256         "itertools.islice",             /* tp_name */
    1257         sizeof(isliceobject),           /* tp_basicsize */
    1258         0,                              /* tp_itemsize */
    1259         /* methods */
    1260         (destructor)islice_dealloc,     /* tp_dealloc */
    1261         0,                              /* tp_print */
    1262         0,                              /* tp_getattr */
    1263         0,                              /* tp_setattr */
    1264         0,                              /* tp_compare */
    1265         0,                              /* tp_repr */
    1266         0,                              /* tp_as_number */
    1267         0,                              /* tp_as_sequence */
    1268         0,                              /* tp_as_mapping */
    1269         0,                              /* tp_hash */
    1270         0,                              /* tp_call */
    1271         0,                              /* tp_str */
    1272         PyObject_GenericGetAttr,        /* tp_getattro */
    1273         0,                              /* tp_setattro */
    1274         0,                              /* tp_as_buffer */
    1275         Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC |
    1276                 Py_TPFLAGS_BASETYPE,    /* tp_flags */
    1277         islice_doc,                     /* tp_doc */
    1278         (traverseproc)islice_traverse,  /* tp_traverse */
    1279         0,                              /* tp_clear */
    1280         0,                              /* tp_richcompare */
    1281         0,                              /* tp_weaklistoffset */
    1282         PyObject_SelfIter,              /* tp_iter */
    1283         (iternextfunc)islice_next,      /* tp_iternext */
    1284         0,                              /* tp_methods */
    1285         0,                              /* tp_members */
    1286         0,                              /* tp_getset */
    1287         0,                              /* tp_base */
    1288         0,                              /* tp_dict */
    1289         0,                              /* tp_descr_get */
    1290         0,                              /* tp_descr_set */
    1291         0,                              /* tp_dictoffset */
    1292         0,                              /* tp_init */
    1293         0,                              /* tp_alloc */
    1294         islice_new,                     /* tp_new */
    1295         PyObject_GC_Del,                /* tp_free */
     1278    PyVarObject_HEAD_INIT(NULL, 0)
     1279    "itertools.islice",                 /* tp_name */
     1280    sizeof(isliceobject),               /* tp_basicsize */
     1281    0,                                  /* tp_itemsize */
     1282    /* methods */
     1283    (destructor)islice_dealloc,         /* tp_dealloc */
     1284    0,                                  /* tp_print */
     1285    0,                                  /* tp_getattr */
     1286    0,                                  /* tp_setattr */
     1287    0,                                  /* tp_compare */
     1288    0,                                  /* tp_repr */
     1289    0,                                  /* tp_as_number */
     1290    0,                                  /* tp_as_sequence */
     1291    0,                                  /* tp_as_mapping */
     1292    0,                                  /* tp_hash */
     1293    0,                                  /* tp_call */
     1294    0,                                  /* tp_str */
     1295    PyObject_GenericGetAttr,            /* tp_getattro */
     1296    0,                                  /* tp_setattro */
     1297    0,                                  /* tp_as_buffer */
     1298    Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC |
     1299        Py_TPFLAGS_BASETYPE,            /* tp_flags */
     1300    islice_doc,                         /* tp_doc */
     1301    (traverseproc)islice_traverse,      /* tp_traverse */
     1302    0,                                  /* tp_clear */
     1303    0,                                  /* tp_richcompare */
     1304    0,                                  /* tp_weaklistoffset */
     1305    PyObject_SelfIter,                  /* tp_iter */
     1306    (iternextfunc)islice_next,          /* tp_iternext */
     1307    0,                                  /* tp_methods */
     1308    0,                                  /* tp_members */
     1309    0,                                  /* tp_getset */
     1310    0,                                  /* tp_base */
     1311    0,                                  /* tp_dict */
     1312    0,                                  /* tp_descr_get */
     1313    0,                                  /* tp_descr_set */
     1314    0,                                  /* tp_dictoffset */
     1315    0,                                  /* tp_init */
     1316    0,                                  /* tp_alloc */
     1317    islice_new,                         /* tp_new */
     1318    PyObject_GC_Del,                    /* tp_free */
    12961319};
    12971320
     
    13001323
    13011324typedef struct {
    1302         PyObject_HEAD
    1303         PyObject *func;
    1304         PyObject *it;
     1325    PyObject_HEAD
     1326    PyObject *func;
     1327    PyObject *it;
    13051328} starmapobject;
    13061329
     
    13101333starmap_new(PyTypeObject *type, PyObject *args, PyObject *kwds)
    13111334{
    1312         PyObject *func, *seq;
    1313         PyObject *it;
    1314         starmapobject *lz;
    1315 
    1316         if (type == &starmap_type && !_PyArg_NoKeywords("starmap()", kwds))
    1317                 return NULL;
    1318 
    1319         if (!PyArg_UnpackTuple(args, "starmap", 2, 2, &func, &seq))
    1320                 return NULL;
    1321 
    1322         /* Get iterator. */
    1323         it = PyObject_GetIter(seq);
    1324         if (it == NULL)
    1325                 return NULL;
    1326 
    1327         /* create starmapobject structure */
    1328         lz = (starmapobject *)type->tp_alloc(type, 0);
    1329         if (lz == NULL) {
    1330                 Py_DECREF(it);
    1331                 return NULL;
    1332         }
    1333         Py_INCREF(func);
    1334         lz->func = func;
    1335         lz->it = it;
    1336 
    1337         return (PyObject *)lz;
     1335    PyObject *func, *seq;
     1336    PyObject *it;
     1337    starmapobject *lz;
     1338
     1339    if (type == &starmap_type && !_PyArg_NoKeywords("starmap()", kwds))
     1340        return NULL;
     1341
     1342    if (!PyArg_UnpackTuple(args, "starmap", 2, 2, &func, &seq))
     1343        return NULL;
     1344
     1345    /* Get iterator. */
     1346    it = PyObject_GetIter(seq);
     1347    if (it == NULL)
     1348        return NULL;
     1349
     1350    /* create starmapobject structure */
     1351    lz = (starmapobject *)type->tp_alloc(type, 0);
     1352    if (lz == NULL) {
     1353        Py_DECREF(it);
     1354        return NULL;
     1355    }
     1356    Py_INCREF(func);
     1357    lz->func = func;
     1358    lz->it = it;
     1359
     1360    return (PyObject *)lz;
    13381361}
    13391362
     
    13411364starmap_dealloc(starmapobject *lz)
    13421365{
    1343         PyObject_GC_UnTrack(lz);
    1344         Py_XDECREF(lz->func);
    1345         Py_XDECREF(lz->it);
    1346         Py_TYPE(lz)->tp_free(lz);
     1366    PyObject_GC_UnTrack(lz);
     1367    Py_XDECREF(lz->func);
     1368    Py_XDECREF(lz->it);
     1369    Py_TYPE(lz)->tp_free(lz);
    13471370}
    13481371
     
    13501373starmap_traverse(starmapobject *lz, visitproc visit, void *arg)
    13511374{
    1352         Py_VISIT(lz->it);
    1353         Py_VISIT(lz->func);
    1354         return 0;
     1375    Py_VISIT(lz->it);
     1376    Py_VISIT(lz->func);
     1377    return 0;
    13551378}
    13561379
     
    13581381starmap_next(starmapobject *lz)
    13591382{
    1360         PyObject *args;
    1361         PyObject *result;
    1362         PyObject *it = lz->it;
    1363 
    1364         assert(PyIter_Check(it));
    1365         args = (*Py_TYPE(it)->tp_iternext)(it);
    1366         if (args == NULL)
    1367                 return NULL;
    1368         if (!PyTuple_CheckExact(args)) {
    1369                 PyObject *newargs = PySequence_Tuple(args);
    1370                 Py_DECREF(args);
    1371                 if (newargs == NULL)
    1372                         return NULL;
    1373                 args = newargs;
    1374         }
    1375         result = PyObject_Call(lz->func, args, NULL);
    1376         Py_DECREF(args);
    1377         return result;
     1383    PyObject *args;
     1384    PyObject *result;
     1385    PyObject *it = lz->it;
     1386
     1387    args = (*Py_TYPE(it)->tp_iternext)(it);
     1388    if (args == NULL)
     1389        return NULL;
     1390    if (!PyTuple_CheckExact(args)) {
     1391        PyObject *newargs = PySequence_Tuple(args);
     1392        Py_DECREF(args);
     1393        if (newargs == NULL)
     1394            return NULL;
     1395        args = newargs;
     1396    }
     1397    result = PyObject_Call(lz->func, args, NULL);
     1398    Py_DECREF(args);
     1399    return result;
    13781400}
    13791401
     
    13851407
    13861408static PyTypeObject starmap_type = {
    1387         PyVarObject_HEAD_INIT(NULL, 0)
    1388         "itertools.starmap",            /* tp_name */
    1389         sizeof(starmapobject),          /* tp_basicsize */
    1390         0,                              /* tp_itemsize */
    1391         /* methods */
    1392         (destructor)starmap_dealloc,    /* tp_dealloc */
    1393         0,                              /* tp_print */
    1394         0,                              /* tp_getattr */
    1395         0,                              /* tp_setattr */
    1396         0,                              /* tp_compare */
    1397         0,                              /* tp_repr */
    1398         0,                              /* tp_as_number */
    1399         0,                              /* tp_as_sequence */
    1400         0,                              /* tp_as_mapping */
    1401         0,                              /* tp_hash */
    1402         0,                              /* tp_call */
    1403         0,                              /* tp_str */
    1404         PyObject_GenericGetAttr,        /* tp_getattro */
    1405         0,                              /* tp_setattro */
    1406         0,                              /* tp_as_buffer */
    1407         Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC |
    1408                 Py_TPFLAGS_BASETYPE,    /* tp_flags */
    1409         starmap_doc,                    /* tp_doc */
    1410         (traverseproc)starmap_traverse, /* tp_traverse */
    1411         0,                              /* tp_clear */
    1412         0,                              /* tp_richcompare */
    1413         0,                              /* tp_weaklistoffset */
    1414         PyObject_SelfIter,              /* tp_iter */
    1415         (iternextfunc)starmap_next,     /* tp_iternext */
    1416         0,                              /* tp_methods */
    1417         0,                              /* tp_members */
    1418         0,                              /* tp_getset */
    1419         0,                              /* tp_base */
    1420         0,                              /* tp_dict */
    1421         0,                              /* tp_descr_get */
    1422         0,                              /* tp_descr_set */
    1423         0,                              /* tp_dictoffset */
    1424         0,                              /* tp_init */
    1425         0,                              /* tp_alloc */
    1426         starmap_new,                    /* tp_new */
    1427         PyObject_GC_Del,                /* tp_free */
     1409    PyVarObject_HEAD_INIT(NULL, 0)
     1410    "itertools.starmap",                /* tp_name */
     1411    sizeof(starmapobject),              /* tp_basicsize */
     1412    0,                                  /* tp_itemsize */
     1413    /* methods */
     1414    (destructor)starmap_dealloc,        /* tp_dealloc */
     1415    0,                                  /* tp_print */
     1416    0,                                  /* tp_getattr */
     1417    0,                                  /* tp_setattr */
     1418    0,                                  /* tp_compare */
     1419    0,                                  /* tp_repr */
     1420    0,                                  /* tp_as_number */
     1421    0,                                  /* tp_as_sequence */
     1422    0,                                  /* tp_as_mapping */
     1423    0,                                  /* tp_hash */
     1424    0,                                  /* tp_call */
     1425    0,                                  /* tp_str */
     1426    PyObject_GenericGetAttr,            /* tp_getattro */
     1427    0,                                  /* tp_setattro */
     1428    0,                                  /* tp_as_buffer */
     1429    Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC |
     1430        Py_TPFLAGS_BASETYPE,            /* tp_flags */
     1431    starmap_doc,                        /* tp_doc */
     1432    (traverseproc)starmap_traverse,     /* tp_traverse */
     1433    0,                                  /* tp_clear */
     1434    0,                                  /* tp_richcompare */
     1435    0,                                  /* tp_weaklistoffset */
     1436    PyObject_SelfIter,                  /* tp_iter */
     1437    (iternextfunc)starmap_next,         /* tp_iternext */
     1438    0,                                  /* tp_methods */
     1439    0,                                  /* tp_members */
     1440    0,                                  /* tp_getset */
     1441    0,                                  /* tp_base */
     1442    0,                                  /* tp_dict */
     1443    0,                                  /* tp_descr_get */
     1444    0,                                  /* tp_descr_set */
     1445    0,                                  /* tp_dictoffset */
     1446    0,                                  /* tp_init */
     1447    0,                                  /* tp_alloc */
     1448    starmap_new,                        /* tp_new */
     1449    PyObject_GC_Del,                    /* tp_free */
    14281450};
    14291451
     
    14321454
    14331455typedef struct {
    1434         PyObject_HEAD
    1435         PyObject *iters;
    1436         PyObject *func;
     1456    PyObject_HEAD
     1457    PyObject *iters;
     1458    PyObject *func;
    14371459} imapobject;
    14381460
     
    14421464imap_new(PyTypeObject *type, PyObject *args, PyObject *kwds)
    14431465{
    1444         PyObject *it, *iters, *func;
    1445         imapobject *lz;
    1446         Py_ssize_t numargs, i;
    1447 
    1448         if (type == &imap_type && !_PyArg_NoKeywords("imap()", kwds))
    1449                 return NULL;
    1450 
    1451         numargs = PyTuple_Size(args);
    1452         if (numargs < 2) {
    1453                 PyErr_SetString(PyExc_TypeError,
    1454                    "imap() must have at least two arguments.");
    1455                 return NULL;
    1456         }
    1457 
    1458         iters = PyTuple_New(numargs-1);
    1459         if (iters == NULL)
    1460                 return NULL;
    1461 
    1462         for (i=1 ; i<numargs ; i++) {
    1463                 /* Get iterator. */
    1464                 it = PyObject_GetIter(PyTuple_GET_ITEM(args, i));
    1465                 if (it == NULL) {
    1466                         Py_DECREF(iters);
    1467                         return NULL;
    1468                 }
    1469                 PyTuple_SET_ITEM(iters, i-1, it);
    1470         }
    1471 
    1472         /* create imapobject structure */
    1473         lz = (imapobject *)type->tp_alloc(type, 0);
    1474         if (lz == NULL) {
    1475                 Py_DECREF(iters);
    1476                 return NULL;
    1477         }
    1478         lz->iters = iters;
    1479         func = PyTuple_GET_ITEM(args, 0);
    1480         Py_INCREF(func);
    1481         lz->func = func;
    1482 
    1483         return (PyObject *)lz;
     1466    PyObject *it, *iters, *func;
     1467    imapobject *lz;
     1468    Py_ssize_t numargs, i;
     1469
     1470    if (type == &imap_type && !_PyArg_NoKeywords("imap()", kwds))
     1471        return NULL;
     1472
     1473    numargs = PyTuple_Size(args);
     1474    if (numargs < 2) {
     1475        PyErr_SetString(PyExc_TypeError,
     1476           "imap() must have at least two arguments.");
     1477        return NULL;
     1478    }
     1479
     1480    iters = PyTuple_New(numargs-1);
     1481    if (iters == NULL)
     1482        return NULL;
     1483
     1484    for (i=1 ; i<numargs ; i++) {
     1485        /* Get iterator. */
     1486        it = PyObject_GetIter(PyTuple_GET_ITEM(args, i));
     1487        if (it == NULL) {
     1488            Py_DECREF(iters);
     1489            return NULL;
     1490        }
     1491        PyTuple_SET_ITEM(iters, i-1, it);
     1492    }
     1493
     1494    /* create imapobject structure */
     1495    lz = (imapobject *)type->tp_alloc(type, 0);
     1496    if (lz == NULL) {
     1497        Py_DECREF(iters);
     1498        return NULL;
     1499    }
     1500    lz->iters = iters;
     1501    func = PyTuple_GET_ITEM(args, 0);
     1502    Py_INCREF(func);
     1503    lz->func = func;
     1504
     1505    return (PyObject *)lz;
    14841506}
    14851507
     
    14871509imap_dealloc(imapobject *lz)
    14881510{
    1489         PyObject_GC_UnTrack(lz);
    1490         Py_XDECREF(lz->iters);
    1491         Py_XDECREF(lz->func);
    1492         Py_TYPE(lz)->tp_free(lz);
     1511    PyObject_GC_UnTrack(lz);
     1512    Py_XDECREF(lz->iters);
     1513    Py_XDECREF(lz->func);
     1514    Py_TYPE(lz)->tp_free(lz);
    14931515}
    14941516
     
    14961518imap_traverse(imapobject *lz, visitproc visit, void *arg)
    14971519{
    1498         Py_VISIT(lz->iters);
    1499         Py_VISIT(lz->func);
    1500         return 0;
    1501 }
    1502 
    1503 /*     
     1520    Py_VISIT(lz->iters);
     1521    Py_VISIT(lz->func);
     1522    return 0;
     1523}
     1524
     1525/*
    15041526imap() is an iterator version of __builtins__.map() except that it does
    15051527not have the None fill-in feature.  That was intentionally left out for
     
    15121534     or constant arguments to a function).
    15131535
    1514   2) In typical use cases for combining itertools, having one finite data 
     1536  2) In typical use cases for combining itertools, having one finite data
    15151537     supplier run out before another is likely to be an error condition which
    15161538     should not pass silently by automatically supplying None.
     
    15181540  3) The use cases for automatic None fill-in are rare -- not many functions
    15191541     do something useful when a parameter suddenly switches type and becomes
    1520      None. 
    1521 
    1522   4) If a need does arise, it can be met by __builtins__.map() or by 
     1542     None.
     1543
     1544  4) If a need does arise, it can be met by __builtins__.map() or by
    15231545     writing:  chain(iterable, repeat(None)).
    15241546
     
    15291551imap_next(imapobject *lz)
    15301552{
    1531         PyObject *val;
    1532         PyObject *argtuple;
    1533         PyObject *result;
    1534         Py_ssize_t numargs, i;
    1535 
    1536         numargs = PyTuple_Size(lz->iters);
    1537         argtuple = PyTuple_New(numargs);
    1538         if (argtuple == NULL)
    1539                 return NULL;
    1540 
    1541         for (i=0 ; i<numargs ; i++) {
    1542                 val = PyIter_Next(PyTuple_GET_ITEM(lz->iters, i));
    1543                 if (val == NULL) {
    1544                         Py_DECREF(argtuple);
    1545                         return NULL;
    1546                 }
    1547                 PyTuple_SET_ITEM(argtuple, i, val);
    1548         }
    1549         if (lz->func == Py_None)
    1550                 return argtuple;
    1551         result = PyObject_Call(lz->func, argtuple, NULL);
    1552         Py_DECREF(argtuple);
    1553         return result;
     1553    PyObject *val;
     1554    PyObject *argtuple;
     1555    PyObject *result;
     1556    Py_ssize_t numargs, i;
     1557
     1558    numargs = PyTuple_Size(lz->iters);
     1559    argtuple = PyTuple_New(numargs);
     1560    if (argtuple == NULL)
     1561        return NULL;
     1562
     1563    for (i=0 ; i<numargs ; i++) {
     1564        val = PyIter_Next(PyTuple_GET_ITEM(lz->iters, i));
     1565        if (val == NULL) {
     1566            Py_DECREF(argtuple);
     1567            return NULL;
     1568        }
     1569        PyTuple_SET_ITEM(argtuple, i, val);
     1570    }
     1571    if (lz->func == Py_None)
     1572        return argtuple;
     1573    result = PyObject_Call(lz->func, argtuple, NULL);
     1574    Py_DECREF(argtuple);
     1575    return result;
    15541576}
    15551577
     
    15581580\n\
    15591581Make an iterator that computes the function using arguments from\n\
    1560 each of the iterables.  Like map() except that it returns\n\
     1582each of the iterables.  Like map() except that it returns\n\
    15611583an iterator instead of a list and that it stops when the shortest\n\
    15621584iterable is exhausted instead of filling in None for shorter\n\
     
    15641586
    15651587static PyTypeObject imap_type = {
    1566         PyVarObject_HEAD_INIT(NULL, 0)
    1567         "itertools.imap",               /* tp_name */
    1568         sizeof(imapobject),             /* tp_basicsize */
    1569         0,                              /* tp_itemsize */
    1570         /* methods */
    1571         (destructor)imap_dealloc,       /* tp_dealloc */
    1572         0,                              /* tp_print */
    1573         0,                              /* tp_getattr */
    1574         0,                              /* tp_setattr */
    1575         0,                              /* tp_compare */
    1576         0,                              /* tp_repr */
    1577         0,                              /* tp_as_number */
    1578         0,                              /* tp_as_sequence */
    1579         0,                              /* tp_as_mapping */
    1580         0,                              /* tp_hash */
    1581         0,                              /* tp_call */
    1582         0,                              /* tp_str */
    1583         PyObject_GenericGetAttr,        /* tp_getattro */
    1584         0,                              /* tp_setattro */
    1585         0,                              /* tp_as_buffer */
    1586         Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC |
    1587                 Py_TPFLAGS_BASETYPE,    /* tp_flags */
    1588         imap_doc,                       /* tp_doc */
    1589         (traverseproc)imap_traverse,    /* tp_traverse */
    1590         0,                              /* tp_clear */
    1591         0,                              /* tp_richcompare */
    1592         0,                              /* tp_weaklistoffset */
    1593         PyObject_SelfIter,              /* tp_iter */
    1594         (iternextfunc)imap_next,        /* tp_iternext */
    1595         0,                              /* tp_methods */
    1596         0,                              /* tp_members */
    1597         0,                              /* tp_getset */
    1598         0,                              /* tp_base */
    1599         0,                              /* tp_dict */
    1600         0,                              /* tp_descr_get */
    1601         0,                              /* tp_descr_set */
    1602         0,                              /* tp_dictoffset */
    1603         0,                              /* tp_init */
    1604         0,                              /* tp_alloc */
    1605         imap_new,                       /* tp_new */
    1606         PyObject_GC_Del,                /* tp_free */
     1588    PyVarObject_HEAD_INIT(NULL, 0)
     1589    "itertools.imap",                   /* tp_name */
     1590    sizeof(imapobject),                 /* tp_basicsize */
     1591    0,                                  /* tp_itemsize */
     1592    /* methods */
     1593    (destructor)imap_dealloc,           /* tp_dealloc */
     1594    0,                                  /* tp_print */
     1595    0,                                  /* tp_getattr */
     1596    0,                                  /* tp_setattr */
     1597    0,                                  /* tp_compare */
     1598    0,                                  /* tp_repr */
     1599    0,                                  /* tp_as_number */
     1600    0,                                  /* tp_as_sequence */
     1601    0,                                  /* tp_as_mapping */
     1602    0,                                  /* tp_hash */
     1603    0,                                  /* tp_call */
     1604    0,                                  /* tp_str */
     1605    PyObject_GenericGetAttr,            /* tp_getattro */
     1606    0,                                  /* tp_setattro */
     1607    0,                                  /* tp_as_buffer */
     1608    Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC |
     1609        Py_TPFLAGS_BASETYPE,            /* tp_flags */
     1610    imap_doc,                           /* tp_doc */
     1611    (traverseproc)imap_traverse,        /* tp_traverse */
     1612    0,                                  /* tp_clear */
     1613    0,                                  /* tp_richcompare */
     1614    0,                                  /* tp_weaklistoffset */
     1615    PyObject_SelfIter,                  /* tp_iter */
     1616    (iternextfunc)imap_next,            /* tp_iternext */
     1617    0,                                  /* tp_methods */
     1618    0,                                  /* tp_members */
     1619    0,                                  /* tp_getset */
     1620    0,                                  /* tp_base */
     1621    0,                                  /* tp_dict */
     1622    0,                                  /* tp_descr_get */
     1623    0,                                  /* tp_descr_set */
     1624    0,                                  /* tp_dictoffset */
     1625    0,                                  /* tp_init */
     1626    0,                                  /* tp_alloc */
     1627    imap_new,                           /* tp_new */
     1628    PyObject_GC_Del,                    /* tp_free */
    16071629};
    16081630
     
    16111633
    16121634typedef struct {
    1613         PyObject_HEAD
    1614         PyObject *source;               /* Iterator over input iterables */
    1615         PyObject *active;               /* Currently running input iterator */
     1635    PyObject_HEAD
     1636    PyObject *source;                   /* Iterator over input iterables */
     1637    PyObject *active;                   /* Currently running input iterator */
    16161638} chainobject;
    16171639
    16181640static PyTypeObject chain_type;
    16191641
    1620 static PyObject * 
     1642static PyObject *
    16211643chain_new_internal(PyTypeObject *type, PyObject *source)
    16221644{
    1623         chainobject *lz;
    1624 
    1625         lz = (chainobject *)type->tp_alloc(type, 0);
    1626         if (lz == NULL) {
    1627                 Py_DECREF(source);
    1628                 return NULL;
    1629         }
    1630        
    1631         lz->source = source;
    1632         lz->active = NULL;
    1633         return (PyObject *)lz;
     1645    chainobject *lz;
     1646
     1647    lz = (chainobject *)type->tp_alloc(type, 0);
     1648    if (lz == NULL) {
     1649        Py_DECREF(source);
     1650        return NULL;
     1651    }
     1652
     1653    lz->source = source;
     1654    lz->active = NULL;
     1655    return (PyObject *)lz;
    16341656}
    16351657
     
    16371659chain_new(PyTypeObject *type, PyObject *args, PyObject *kwds)
    16381660{
    1639         PyObject *source;
    1640 
    1641         if (type == &chain_type && !_PyArg_NoKeywords("chain()", kwds))
    1642                 return NULL;
    1643        
    1644         source = PyObject_GetIter(args);
    1645         if (source == NULL)
    1646                 return NULL;
    1647 
    1648         return chain_new_internal(type, source);
     1661    PyObject *source;
     1662
     1663    if (type == &chain_type && !_PyArg_NoKeywords("chain()", kwds))
     1664        return NULL;
     1665
     1666    source = PyObject_GetIter(args);
     1667    if (source == NULL)
     1668        return NULL;
     1669
     1670    return chain_new_internal(type, source);
    16491671}
    16501672
     
    16521674chain_new_from_iterable(PyTypeObject *type, PyObject *arg)
    16531675{
    1654         PyObject *source;
    1655        
    1656         source = PyObject_GetIter(arg);
    1657         if (source == NULL)
    1658                 return NULL;
    1659 
    1660         return chain_new_internal(type, source);
     1676    PyObject *source;
     1677
     1678    source = PyObject_GetIter(arg);
     1679    if (source == NULL)
     1680        return NULL;
     1681
     1682    return chain_new_internal(type, source);
    16611683}
    16621684
     
    16641686chain_dealloc(chainobject *lz)
    16651687{
    1666         PyObject_GC_UnTrack(lz);
    1667         Py_XDECREF(lz->active);
    1668         Py_XDECREF(lz->source);
    1669         Py_TYPE(lz)->tp_free(lz);
     1688    PyObject_GC_UnTrack(lz);
     1689    Py_XDECREF(lz->active);
     1690    Py_XDECREF(lz->source);
     1691    Py_TYPE(lz)->tp_free(lz);
    16701692}
    16711693
     
    16731695chain_traverse(chainobject *lz, visitproc visit, void *arg)
    16741696{
    1675         Py_VISIT(lz->source);
    1676         Py_VISIT(lz->active);
    1677         return 0;
     1697    Py_VISIT(lz->source);
     1698    Py_VISIT(lz->active);
     1699    return 0;
    16781700}
    16791701
     
    16811703chain_next(chainobject *lz)
    16821704{
    1683         PyObject *item;
    1684 
    1685         if (lz->source == NULL)
    1686                 return NULL;                            /* already stopped */
    1687 
    1688         if (lz->active == NULL) {
    1689                 PyObject *iterable = PyIter_Next(lz->source);
    1690                 if (iterable == NULL) {
    1691                         Py_CLEAR(lz->source);
    1692                         return NULL;                    /* no more input sources */
    1693                 }
    1694                 lz->active = PyObject_GetIter(iterable);
    1695                 Py_DECREF(iterable);
    1696                 if (lz->active == NULL) {
    1697                         Py_CLEAR(lz->source);
    1698                         return NULL;                    /* input not iterable */
    1699                 }
    1700         }
    1701         item = PyIter_Next(lz->active);
    1702         if (item != NULL)
    1703                 return item;
    1704         if (PyErr_Occurred()) {
    1705                 if (PyErr_ExceptionMatches(PyExc_StopIteration))
    1706                         PyErr_Clear();
    1707                 else
    1708                         return NULL;                    /* input raised an exception */
    1709         }
    1710         Py_CLEAR(lz->active);
    1711         return chain_next(lz);                  /* recurse and use next active */
     1705    PyObject *item;
     1706
     1707    if (lz->source == NULL)
     1708        return NULL;                                    /* already stopped */
     1709
     1710    if (lz->active == NULL) {
     1711        PyObject *iterable = PyIter_Next(lz->source);
     1712        if (iterable == NULL) {
     1713            Py_CLEAR(lz->source);
     1714            return NULL;                                /* no more input sources */
     1715        }
     1716        lz->active = PyObject_GetIter(iterable);
     1717        Py_DECREF(iterable);
     1718        if (lz->active == NULL) {
     1719            Py_CLEAR(lz->source);
     1720            return NULL;                                /* input not iterable */
     1721        }
     1722    }
     1723    item = PyIter_Next(lz->active);
     1724    if (item != NULL)
     1725        return item;
     1726    if (PyErr_Occurred()) {
     1727        if (PyErr_ExceptionMatches(PyExc_StopIteration))
     1728            PyErr_Clear();
     1729        else
     1730            return NULL;                                /* input raised an exception */
     1731    }
     1732    Py_CLEAR(lz->active);
     1733    return chain_next(lz);                      /* recurse and use next active */
    17121734}
    17131735
     
    17261748
    17271749static PyMethodDef chain_methods[] = {
    1728         {"from_iterable", (PyCFunction) chain_new_from_iterable,        METH_O | METH_CLASS,
    1729                 chain_from_iterable_doc},
    1730         {NULL,          NULL}   /* sentinel */
     1750    {"from_iterable", (PyCFunction) chain_new_from_iterable,            METH_O | METH_CLASS,
     1751        chain_from_iterable_doc},
     1752    {NULL,              NULL}   /* sentinel */
    17311753};
    17321754
    17331755static PyTypeObject chain_type = {
    1734         PyVarObject_HEAD_INIT(NULL, 0)
    1735         "itertools.chain",              /* tp_name */
    1736         sizeof(chainobject),            /* tp_basicsize */
    1737         0,                              /* tp_itemsize */
    1738         /* methods */
    1739         (destructor)chain_dealloc,      /* tp_dealloc */
    1740         0,                              /* tp_print */
    1741         0,                              /* tp_getattr */
    1742         0,                              /* tp_setattr */
    1743         0,                              /* tp_compare */
    1744         0,                              /* tp_repr */
    1745         0,                              /* tp_as_number */
    1746         0,                              /* tp_as_sequence */
    1747         0,                              /* tp_as_mapping */
    1748         0,                              /* tp_hash */
    1749         0,                              /* tp_call */
    1750         0,                              /* tp_str */
    1751         PyObject_GenericGetAttr,        /* tp_getattro */
    1752         0,                              /* tp_setattro */
    1753         0,                              /* tp_as_buffer */
    1754         Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC |
    1755                 Py_TPFLAGS_BASETYPE,    /* tp_flags */
    1756         chain_doc,                      /* tp_doc */
    1757         (traverseproc)chain_traverse,   /* tp_traverse */
    1758         0,                              /* tp_clear */
    1759         0,                              /* tp_richcompare */
    1760         0,                              /* tp_weaklistoffset */
    1761         PyObject_SelfIter,              /* tp_iter */
    1762         (iternextfunc)chain_next,       /* tp_iternext */
    1763         chain_methods,                  /* tp_methods */
    1764         0,                              /* tp_members */
    1765         0,                              /* tp_getset */
    1766         0,                              /* tp_base */
    1767         0,                              /* tp_dict */
    1768         0,                              /* tp_descr_get */
    1769         0,                              /* tp_descr_set */
    1770         0,                              /* tp_dictoffset */
    1771         0,                              /* tp_init */
    1772         0,                              /* tp_alloc */
    1773         chain_new,                      /* tp_new */
    1774         PyObject_GC_Del,                /* tp_free */
     1756    PyVarObject_HEAD_INIT(NULL, 0)
     1757    "itertools.chain",                  /* tp_name */
     1758    sizeof(chainobject),                /* tp_basicsize */
     1759    0,                                  /* tp_itemsize */
     1760    /* methods */
     1761    (destructor)chain_dealloc,          /* tp_dealloc */
     1762    0,                                  /* tp_print */
     1763    0,                                  /* tp_getattr */
     1764    0,                                  /* tp_setattr */
     1765    0,                                  /* tp_compare */
     1766    0,                                  /* tp_repr */
     1767    0,                                  /* tp_as_number */
     1768    0,                                  /* tp_as_sequence */
     1769    0,                                  /* tp_as_mapping */
     1770    0,                                  /* tp_hash */
     1771    0,                                  /* tp_call */
     1772    0,                                  /* tp_str */
     1773    PyObject_GenericGetAttr,            /* tp_getattro */
     1774    0,                                  /* tp_setattro */
     1775    0,                                  /* tp_as_buffer */
     1776    Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC |
     1777        Py_TPFLAGS_BASETYPE,            /* tp_flags */
     1778    chain_doc,                          /* tp_doc */
     1779    (traverseproc)chain_traverse,       /* tp_traverse */
     1780    0,                                  /* tp_clear */
     1781    0,                                  /* tp_richcompare */
     1782    0,                                  /* tp_weaklistoffset */
     1783    PyObject_SelfIter,                  /* tp_iter */
     1784    (iternextfunc)chain_next,           /* tp_iternext */
     1785    chain_methods,                      /* tp_methods */
     1786    0,                                  /* tp_members */
     1787    0,                                  /* tp_getset */
     1788    0,                                  /* tp_base */
     1789    0,                                  /* tp_dict */
     1790    0,                                  /* tp_descr_get */
     1791    0,                                  /* tp_descr_set */
     1792    0,                                  /* tp_dictoffset */
     1793    0,                                  /* tp_init */
     1794    0,                                  /* tp_alloc */
     1795    chain_new,                          /* tp_new */
     1796    PyObject_GC_Del,                    /* tp_free */
    17751797};
    17761798
     
    17791801
    17801802typedef struct {
    1781         PyObject_HEAD
    1782         PyObject *pools;                /* tuple of pool tuples */
    1783         Py_ssize_t *indices;            /* one index per pool */
    1784         PyObject *result;               /* most recently returned result tuple */
    1785         int stopped;                    /* set to 1 when the product iterator is exhausted */
     1803    PyObject_HEAD
     1804    PyObject *pools;                    /* tuple of pool tuples */
     1805    Py_ssize_t *indices;            /* one index per pool */
     1806    PyObject *result;               /* most recently returned result tuple */
     1807    int stopped;                    /* set to 1 when the product iterator is exhausted */
    17861808} productobject;
    17871809
     
    17911813product_new(PyTypeObject *type, PyObject *args, PyObject *kwds)
    17921814{
    1793         productobject *lz;
    1794         Py_ssize_t nargs, npools, repeat=1;
    1795         PyObject *pools = NULL;
    1796         Py_ssize_t *indices = NULL;
    1797         Py_ssize_t i;
    1798 
    1799         if (kwds != NULL) {
    1800                 char *kwlist[] = {"repeat", 0};
    1801                 PyObject *tmpargs = PyTuple_New(0);
    1802                 if (tmpargs == NULL)
    1803                         return NULL;
    1804                 if (!PyArg_ParseTupleAndKeywords(tmpargs, kwds, "|n:product", kwlist, &repeat)) {
    1805                         Py_DECREF(tmpargs);
    1806                         return NULL;
    1807                 }
    1808                 Py_DECREF(tmpargs);
    1809                 if (repeat < 0) {
    1810                         PyErr_SetString(PyExc_ValueError,
    1811                                         "repeat argument cannot be negative");
    1812                         return NULL;
    1813                 }
    1814         }
    1815 
    1816         assert(PyTuple_Check(args));
    1817         nargs = (repeat == 0) ? 0 : PyTuple_GET_SIZE(args);
    1818         npools = nargs * repeat;
    1819 
    1820         indices = PyMem_Malloc(npools * sizeof(Py_ssize_t));
    1821         if (indices == NULL) {
    1822                 PyErr_NoMemory();
    1823                 goto error;
    1824         }
    1825 
    1826         pools = PyTuple_New(npools);
    1827         if (pools == NULL)
    1828                 goto error;
    1829 
    1830         for (i=0; i < nargs ; ++i) {
    1831                 PyObject *item = PyTuple_GET_ITEM(args, i);
    1832                 PyObject *pool = PySequence_Tuple(item);
    1833                 if (pool == NULL)
    1834                         goto error;
    1835                 PyTuple_SET_ITEM(pools, i, pool);
    1836                 indices[i] = 0;
    1837         }
    1838         for ( ; i < npools; ++i) {
    1839                 PyObject *pool = PyTuple_GET_ITEM(pools, i - nargs);
    1840                 Py_INCREF(pool);
    1841                 PyTuple_SET_ITEM(pools, i, pool);
    1842                 indices[i] = 0;
    1843         }
    1844 
    1845         /* create productobject structure */
    1846         lz = (productobject *)type->tp_alloc(type, 0);
    1847         if (lz == NULL)
    1848                 goto error;
    1849 
    1850         lz->pools = pools;
    1851         lz->indices = indices;
    1852         lz->result = NULL;
    1853         lz->stopped = 0;
    1854 
    1855         return (PyObject *)lz;
     1815    productobject *lz;
     1816    Py_ssize_t nargs, npools, repeat=1;
     1817    PyObject *pools = NULL;
     1818    Py_ssize_t *indices = NULL;
     1819    Py_ssize_t i;
     1820
     1821    if (kwds != NULL) {
     1822        char *kwlist[] = {"repeat", 0};
     1823        PyObject *tmpargs = PyTuple_New(0);
     1824        if (tmpargs == NULL)
     1825            return NULL;
     1826        if (!PyArg_ParseTupleAndKeywords(tmpargs, kwds, "|n:product", kwlist, &repeat)) {
     1827            Py_DECREF(tmpargs);
     1828            return NULL;
     1829        }
     1830        Py_DECREF(tmpargs);
     1831        if (repeat < 0) {
     1832            PyErr_SetString(PyExc_ValueError,
     1833                            "repeat argument cannot be negative");
     1834            return NULL;
     1835        }
     1836    }
     1837
     1838    assert(PyTuple_Check(args));
     1839    nargs = (repeat == 0) ? 0 : PyTuple_GET_SIZE(args);
     1840    npools = nargs * repeat;
     1841
     1842    indices = PyMem_Malloc(npools * sizeof(Py_ssize_t));
     1843    if (indices == NULL) {
     1844        PyErr_NoMemory();
     1845        goto error;
     1846    }
     1847
     1848    pools = PyTuple_New(npools);
     1849    if (pools == NULL)
     1850        goto error;
     1851
     1852    for (i=0; i < nargs ; ++i) {
     1853        PyObject *item = PyTuple_GET_ITEM(args, i);
     1854        PyObject *pool = PySequence_Tuple(item);
     1855        if (pool == NULL)
     1856            goto error;
     1857        PyTuple_SET_ITEM(pools, i, pool);
     1858        indices[i] = 0;
     1859    }
     1860    for ( ; i < npools; ++i) {
     1861        PyObject *pool = PyTuple_GET_ITEM(pools, i - nargs);
     1862        Py_INCREF(pool);
     1863        PyTuple_SET_ITEM(pools, i, pool);
     1864        indices[i] = 0;
     1865    }
     1866
     1867    /* create productobject structure */
     1868    lz = (productobject *)type->tp_alloc(type, 0);
     1869    if (lz == NULL)
     1870        goto error;
     1871
     1872    lz->pools = pools;
     1873    lz->indices = indices;
     1874    lz->result = NULL;
     1875    lz->stopped = 0;
     1876
     1877    return (PyObject *)lz;
    18561878
    18571879error:
    1858         if (indices != NULL)
    1859                 PyMem_Free(indices);
    1860         Py_XDECREF(pools);
    1861         return NULL;
     1880    if (indices != NULL)
     1881        PyMem_Free(indices);
     1882    Py_XDECREF(pools);
     1883    return NULL;
    18621884}
    18631885
     
    18651887product_dealloc(productobject *lz)
    18661888{
    1867         PyObject_GC_UnTrack(lz);
    1868         Py_XDECREF(lz->pools);
    1869         Py_XDECREF(lz->result);
    1870         PyMem_Free(lz->indices);
    1871         Py_TYPE(lz)->tp_free(lz);
     1889    PyObject_GC_UnTrack(lz);
     1890    Py_XDECREF(lz->pools);
     1891    Py_XDECREF(lz->result);
     1892    if (lz->indices != NULL)
     1893        PyMem_Free(lz->indices);
     1894    Py_TYPE(lz)->tp_free(lz);
    18721895}
    18731896
     
    18751898product_traverse(productobject *lz, visitproc visit, void *arg)
    18761899{
    1877         Py_VISIT(lz->pools);
    1878         Py_VISIT(lz->result);
    1879         return 0;
     1900    Py_VISIT(lz->pools);
     1901    Py_VISIT(lz->result);
     1902    return 0;
    18801903}
    18811904
     
    18831906product_next(productobject *lz)
    18841907{
    1885         PyObject *pool;
    1886         PyObject *elem;
    1887         PyObject *oldelem;
    1888         PyObject *pools = lz->pools;
    1889         PyObject *result = lz->result;
    1890         Py_ssize_t npools = PyTuple_GET_SIZE(pools);
    1891         Py_ssize_t i;
    1892 
    1893         if (lz->stopped)
    1894                 return NULL;
    1895 
    1896         if (result == NULL) {
    1897                 /* On the first pass, return an initial tuple filled with the
    1898                    first element from each pool. */
    1899                 result = PyTuple_New(npools);
    1900                 if (result == NULL)
    1901                         goto empty;
    1902                 lz->result = result;
    1903                 for (i=0; i < npools; i++) {
    1904                         pool = PyTuple_GET_ITEM(pools, i);
    1905                         if (PyTuple_GET_SIZE(pool) == 0)
    1906                                 goto empty;
    1907                         elem = PyTuple_GET_ITEM(pool, 0);
    1908                         Py_INCREF(elem);
    1909                         PyTuple_SET_ITEM(result, i, elem);
    1910                 }
    1911         } else {
    1912                 Py_ssize_t *indices = lz->indices;
    1913 
    1914                 /* Copy the previous result tuple or re-use it if available */
    1915                 if (Py_REFCNT(result) > 1) {
    1916                         PyObject *old_result = result;
    1917                         result = PyTuple_New(npools);
    1918                         if (result == NULL)
    1919                                 goto empty;
    1920                         lz->result = result;
    1921                         for (i=0; i < npools; i++) {
    1922                                 elem = PyTuple_GET_ITEM(old_result, i);
    1923                                 Py_INCREF(elem);
    1924                                 PyTuple_SET_ITEM(result, i, elem);
    1925                         }
    1926                         Py_DECREF(old_result);
    1927                 }
    1928                 /* Now, we've got the only copy so we can update it in-place */
    1929                 assert (npools==0 || Py_REFCNT(result) == 1);
    1930 
    1931                 /* Update the pool indices right-to-left.  Only advance to the
    1932                    next pool when the previous one rolls-over */
    1933                 for (i=npools-1 ; i >= 0 ; i--) {
    1934                         pool = PyTuple_GET_ITEM(pools, i);
    1935                         indices[i]++;
    1936                         if (indices[i] == PyTuple_GET_SIZE(pool)) {
    1937                                 /* Roll-over and advance to next pool */
    1938                                 indices[i] = 0;
    1939                                 elem = PyTuple_GET_ITEM(pool, 0);
    1940                                 Py_INCREF(elem);
    1941                                 oldelem = PyTuple_GET_ITEM(result, i);
    1942                                 PyTuple_SET_ITEM(result, i, elem);
    1943                                 Py_DECREF(oldelem);
    1944                         } else {
    1945                                 /* No rollover. Just increment and stop here. */
    1946                                 elem = PyTuple_GET_ITEM(pool, indices[i]);
    1947                                 Py_INCREF(elem);
    1948                                 oldelem = PyTuple_GET_ITEM(result, i);
    1949                                 PyTuple_SET_ITEM(result, i, elem);
    1950                                 Py_DECREF(oldelem);
    1951                                 break;
    1952                         }
    1953                 }
    1954 
    1955                 /* If i is negative, then the indices have all rolled-over
    1956                    and we're done. */
    1957                 if (i < 0)
    1958                         goto empty;
    1959         }
    1960 
    1961         Py_INCREF(result);
    1962         return result;
     1908    PyObject *pool;
     1909    PyObject *elem;
     1910    PyObject *oldelem;
     1911    PyObject *pools = lz->pools;
     1912    PyObject *result = lz->result;
     1913    Py_ssize_t npools = PyTuple_GET_SIZE(pools);
     1914    Py_ssize_t i;
     1915
     1916    if (lz->stopped)
     1917        return NULL;
     1918
     1919    if (result == NULL) {
     1920        /* On the first pass, return an initial tuple filled with the
     1921           first element from each pool. */
     1922        result = PyTuple_New(npools);
     1923        if (result == NULL)
     1924            goto empty;
     1925        lz->result = result;
     1926        for (i=0; i < npools; i++) {
     1927            pool = PyTuple_GET_ITEM(pools, i);
     1928            if (PyTuple_GET_SIZE(pool) == 0)
     1929                goto empty;
     1930            elem = PyTuple_GET_ITEM(pool, 0);
     1931            Py_INCREF(elem);
     1932            PyTuple_SET_ITEM(result, i, elem);
     1933        }
     1934    } else {
     1935        Py_ssize_t *indices = lz->indices;
     1936
     1937        /* Copy the previous result tuple or re-use it if available */
     1938        if (Py_REFCNT(result) > 1) {
     1939            PyObject *old_result = result;
     1940            result = PyTuple_New(npools);
     1941            if (result == NULL)
     1942                goto empty;
     1943            lz->result = result;
     1944            for (i=0; i < npools; i++) {
     1945                elem = PyTuple_GET_ITEM(old_result, i);
     1946                Py_INCREF(elem);
     1947                PyTuple_SET_ITEM(result, i, elem);
     1948            }
     1949            Py_DECREF(old_result);
     1950        }
     1951        /* Now, we've got the only copy so we can update it in-place */
     1952        assert (npools==0 || Py_REFCNT(result) == 1);
     1953
     1954        /* Update the pool indices right-to-left.  Only advance to the
     1955           next pool when the previous one rolls-over */
     1956        for (i=npools-1 ; i >= 0 ; i--) {
     1957            pool = PyTuple_GET_ITEM(pools, i);
     1958            indices[i]++;
     1959            if (indices[i] == PyTuple_GET_SIZE(pool)) {
     1960                /* Roll-over and advance to next pool */
     1961                indices[i] = 0;
     1962                elem = PyTuple_GET_ITEM(pool, 0);
     1963                Py_INCREF(elem);
     1964                oldelem = PyTuple_GET_ITEM(result, i);
     1965                PyTuple_SET_ITEM(result, i, elem);
     1966                Py_DECREF(oldelem);
     1967            } else {
     1968                /* No rollover. Just increment and stop here. */
     1969                elem = PyTuple_GET_ITEM(pool, indices[i]);
     1970                Py_INCREF(elem);
     1971                oldelem = PyTuple_GET_ITEM(result, i);
     1972                PyTuple_SET_ITEM(result, i, elem);
     1973                Py_DECREF(oldelem);
     1974                break;
     1975            }
     1976        }
     1977
     1978        /* If i is negative, then the indices have all rolled-over
     1979           and we're done. */
     1980        if (i < 0)
     1981            goto empty;
     1982    }
     1983
     1984    Py_INCREF(result);
     1985    return result;
    19631986
    19641987empty:
    1965         lz->stopped = 1;
    1966         return NULL;
     1988    lz->stopped = 1;
     1989    return NULL;
    19671990}
    19681991
     
    19751998cycle in a manner similar to an odometer (with the rightmost element changing\n\
    19761999on every iteration).\n\n\
     2000To compute the product of an iterable with itself, specify the number\n\
     2001of repetitions with the optional repeat keyword argument. For example,\n\
     2002product(A, repeat=4) means the same as product(A, A, A, A).\n\n\
    19772003product('ab', range(3)) --> ('a',0) ('a',1) ('a',2) ('b',0) ('b',1) ('b',2)\n\
    19782004product((0,1), (0,1), (0,1)) --> (0,0,0) (0,0,1) (0,1,0) (0,1,1) (1,0,0) ...");
    19792005
    19802006static PyTypeObject product_type = {
    1981         PyVarObject_HEAD_INIT(NULL, 0)
    1982         "itertools.product",            /* tp_name */
    1983         sizeof(productobject),  /* tp_basicsize */
    1984         0,                              /* tp_itemsize */
    1985         /* methods */
    1986         (destructor)product_dealloc,    /* tp_dealloc */
    1987         0,                              /* tp_print */
    1988         0,                              /* tp_getattr */
    1989         0,                              /* tp_setattr */
    1990         0,                              /* tp_compare */
    1991         0,                              /* tp_repr */
    1992         0,                              /* tp_as_number */
    1993         0,                              /* tp_as_sequence */
    1994         0,                              /* tp_as_mapping */
    1995         0,                              /* tp_hash */
    1996         0,                              /* tp_call */
    1997         0,                              /* tp_str */
    1998         PyObject_GenericGetAttr,        /* tp_getattro */
    1999         0,                              /* tp_setattro */
    2000         0,                              /* tp_as_buffer */
    2001         Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC |
    2002                 Py_TPFLAGS_BASETYPE,    /* tp_flags */
    2003         product_doc,                    /* tp_doc */
    2004         (traverseproc)product_traverse, /* tp_traverse */
    2005         0,                              /* tp_clear */
    2006         0,                              /* tp_richcompare */
    2007         0,                              /* tp_weaklistoffset */
    2008         PyObject_SelfIter,              /* tp_iter */
    2009         (iternextfunc)product_next,     /* tp_iternext */
    2010         0,                              /* tp_methods */
    2011         0,                              /* tp_members */
    2012         0,                              /* tp_getset */
    2013         0,                              /* tp_base */
    2014         0,                              /* tp_dict */
    2015         0,                              /* tp_descr_get */
    2016         0,                              /* tp_descr_set */
    2017         0,                              /* tp_dictoffset */
    2018         0,                              /* tp_init */
    2019         0,                              /* tp_alloc */
    2020         product_new,                    /* tp_new */
    2021         PyObject_GC_Del,                /* tp_free */
     2007    PyVarObject_HEAD_INIT(NULL, 0)
     2008    "itertools.product",                /* tp_name */
     2009    sizeof(productobject),      /* tp_basicsize */
     2010    0,                                  /* tp_itemsize */
     2011    /* methods */
     2012    (destructor)product_dealloc,        /* tp_dealloc */
     2013    0,                                  /* tp_print */
     2014    0,                                  /* tp_getattr */
     2015    0,                                  /* tp_setattr */
     2016    0,                                  /* tp_compare */
     2017    0,                                  /* tp_repr */
     2018    0,                                  /* tp_as_number */
     2019    0,                                  /* tp_as_sequence */
     2020    0,                                  /* tp_as_mapping */
     2021    0,                                  /* tp_hash */
     2022    0,                                  /* tp_call */
     2023    0,                                  /* tp_str */
     2024    PyObject_GenericGetAttr,            /* tp_getattro */
     2025    0,                                  /* tp_setattro */
     2026    0,                                  /* tp_as_buffer */
     2027    Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC |
     2028        Py_TPFLAGS_BASETYPE,            /* tp_flags */
     2029    product_doc,                        /* tp_doc */
     2030    (traverseproc)product_traverse,     /* tp_traverse */
     2031    0,                                  /* tp_clear */
     2032    0,                                  /* tp_richcompare */
     2033    0,                                  /* tp_weaklistoffset */
     2034    PyObject_SelfIter,                  /* tp_iter */
     2035    (iternextfunc)product_next,         /* tp_iternext */
     2036    0,                                  /* tp_methods */
     2037    0,                                  /* tp_members */
     2038    0,                                  /* tp_getset */
     2039    0,                                  /* tp_base */
     2040    0,                                  /* tp_dict */
     2041    0,                                  /* tp_descr_get */
     2042    0,                                  /* tp_descr_set */
     2043    0,                                  /* tp_dictoffset */
     2044    0,                                  /* tp_init */
     2045    0,                                  /* tp_alloc */
     2046    product_new,                        /* tp_new */
     2047    PyObject_GC_Del,                    /* tp_free */
    20222048};
    20232049
     
    20262052
    20272053typedef struct {
    2028         PyObject_HEAD
    2029         PyObject *pool;                 /* input converted to a tuple */
    2030         Py_ssize_t *indices;            /* one index per result element */
    2031         PyObject *result;               /* most recently returned result tuple */
    2032         Py_ssize_t r;                   /* size of result tuple */
    2033         int stopped;                    /* set to 1 when the combinations iterator is exhausted */
     2054    PyObject_HEAD
     2055    PyObject *pool;                     /* input converted to a tuple */
     2056    Py_ssize_t *indices;            /* one index per result element */
     2057    PyObject *result;               /* most recently returned result tuple */
     2058    Py_ssize_t r;                       /* size of result tuple */
     2059    int stopped;                        /* set to 1 when the combinations iterator is exhausted */
    20342060} combinationsobject;
    20352061
     
    20392065combinations_new(PyTypeObject *type, PyObject *args, PyObject *kwds)
    20402066{
    2041         combinationsobject *co;
    2042         Py_ssize_t n;
    2043         Py_ssize_t r;
    2044         PyObject *pool = NULL;
    2045         PyObject *iterable = NULL;
    2046         Py_ssize_t *indices = NULL;
    2047         Py_ssize_t i;
    2048         static char *kwargs[] = {"iterable", "r", NULL};
    2049  
    2050         if (!PyArg_ParseTupleAndKeywords(args, kwds, "On:combinations", kwargs,
    2051                                         &iterable, &r))
    2052                 return NULL;
    2053 
    2054         pool = PySequence_Tuple(iterable);
    2055         if (pool == NULL)
    2056                 goto error;
    2057         n = PyTuple_GET_SIZE(pool);
    2058         if (r < 0) {
    2059                 PyErr_SetString(PyExc_ValueError, "r must be non-negative");
    2060                 goto error;
    2061         }
    2062 
    2063         indices = PyMem_Malloc(r * sizeof(Py_ssize_t));
    2064         if (indices == NULL) {
    2065                 PyErr_NoMemory();
    2066                 goto error;
    2067         }
    2068 
    2069         for (i=0 ; i<r ; i++)
    2070                 indices[i] = i;
    2071 
    2072         /* create combinationsobject structure */
    2073         co = (combinationsobject *)type->tp_alloc(type, 0);
    2074         if (co == NULL)
    2075                 goto error;
    2076 
    2077         co->pool = pool;
    2078         co->indices = indices;
    2079         co->result = NULL;
    2080         co->r = r;
    2081         co->stopped = r > n ? 1 : 0;
    2082 
    2083         return (PyObject *)co;
     2067    combinationsobject *co;
     2068    Py_ssize_t n;
     2069    Py_ssize_t r;
     2070    PyObject *pool = NULL;
     2071    PyObject *iterable = NULL;
     2072    Py_ssize_t *indices = NULL;
     2073    Py_ssize_t i;
     2074    static char *kwargs[] = {"iterable", "r", NULL};
     2075
     2076    if (!PyArg_ParseTupleAndKeywords(args, kwds, "On:combinations", kwargs,
     2077                                    &iterable, &r))
     2078        return NULL;
     2079
     2080    pool = PySequence_Tuple(iterable);
     2081    if (pool == NULL)
     2082        goto error;
     2083    n = PyTuple_GET_SIZE(pool);
     2084    if (r < 0) {
     2085        PyErr_SetString(PyExc_ValueError, "r must be non-negative");
     2086        goto error;
     2087    }
     2088
     2089    indices = PyMem_Malloc(r * sizeof(Py_ssize_t));
     2090    if (indices == NULL) {
     2091        PyErr_NoMemory();
     2092        goto error;
     2093    }
     2094
     2095    for (i=0 ; i<r ; i++)
     2096        indices[i] = i;
     2097
     2098    /* create combinationsobject structure */
     2099    co = (combinationsobject *)type->tp_alloc(type, 0);
     2100    if (co == NULL)
     2101        goto error;
     2102
     2103    co->pool = pool;
     2104    co->indices = indices;
     2105    co->result = NULL;
     2106    co->r = r;
     2107    co->stopped = r > n ? 1 : 0;
     2108
     2109    return (PyObject *)co;
    20842110
    20852111error:
    2086         if (indices != NULL)
    2087                 PyMem_Free(indices);
    2088         Py_XDECREF(pool);
    2089         return NULL;
     2112    if (indices != NULL)
     2113        PyMem_Free(indices);
     2114    Py_XDECREF(pool);
     2115    return NULL;
    20902116}
    20912117
     
    20932119combinations_dealloc(combinationsobject *co)
    20942120{
    2095         PyObject_GC_UnTrack(co);
    2096         Py_XDECREF(co->pool);
    2097         Py_XDECREF(co->result);
    2098         PyMem_Free(co->indices);
    2099         Py_TYPE(co)->tp_free(co);
     2121    PyObject_GC_UnTrack(co);
     2122    Py_XDECREF(co->pool);
     2123    Py_XDECREF(co->result);
     2124    if (co->indices != NULL)
     2125        PyMem_Free(co->indices);
     2126    Py_TYPE(co)->tp_free(co);
    21002127}
    21012128
     
    21032130combinations_traverse(combinationsobject *co, visitproc visit, void *arg)
    21042131{
    2105         Py_VISIT(co->pool);
    2106         Py_VISIT(co->result);
    2107         return 0;
     2132    Py_VISIT(co->pool);
     2133    Py_VISIT(co->result);
     2134    return 0;
    21082135}
    21092136
     
    21112138combinations_next(combinationsobject *co)
    21122139{
    2113         PyObject *elem;
    2114         PyObject *oldelem;
    2115         PyObject *pool = co->pool;
    2116         Py_ssize_t *indices = co->indices;
    2117         PyObject *result = co->result;
    2118         Py_ssize_t n = PyTuple_GET_SIZE(pool);
    2119         Py_ssize_t r = co->r;
    2120         Py_ssize_t i, j, index;
    2121 
    2122         if (co->stopped)
    2123                 return NULL;
    2124 
    2125         if (result == NULL) {
    2126                 /* On the first pass, initialize result tuple using the indices */
    2127                 result = PyTuple_New(r);
    2128                 if (result == NULL)
    2129                         goto empty;
    2130                 co->result = result;
    2131                 for (i=0; i<r ; i++) {
    2132                         index = indices[i];
    2133                         elem = PyTuple_GET_ITEM(pool, index);
    2134                         Py_INCREF(elem);
    2135                         PyTuple_SET_ITEM(result, i, elem);
    2136                 }
    2137         } else {
    2138                 /* Copy the previous result tuple or re-use it if available */
    2139                 if (Py_REFCNT(result) > 1) {
    2140                         PyObject *old_result = result;
    2141                         result = PyTuple_New(r);
    2142                         if (result == NULL)
    2143                                 goto empty;
    2144                         co->result = result;
    2145                         for (i=0; i<r ; i++) {
    2146                                 elem = PyTuple_GET_ITEM(old_result, i);
    2147                                 Py_INCREF(elem);
    2148                                 PyTuple_SET_ITEM(result, i, elem);
    2149                         }
    2150                         Py_DECREF(old_result);
    2151                 }
    2152                 /* Now, we've got the only copy so we can update it in-place
    2153                  * CPython's empty tuple is a singleton and cached in
    2154                  * PyTuple's freelist.
    2155                 */
    2156                 assert(r == 0 || Py_REFCNT(result) == 1);
    2157 
    2158                 /* Scan indices right-to-left until finding one that is not
    2159                    at its maximum (i + n - r). */
    2160                 for (i=r-1 ; i >= 0 && indices[i] == i+n-r ; i--)
    2161                         ;
    2162 
    2163                 /* If i is negative, then the indices are all at
    2164                    their maximum value and we're done. */
    2165                 if (i < 0)
    2166                         goto empty;
    2167 
    2168                 /* Increment the current index which we know is not at its
    2169                    maximum.  Then move back to the right setting each index
    2170                    to its lowest possible value (one higher than the index
    2171                    to its left -- this maintains the sort order invariant). */
    2172                 indices[i]++;
    2173                 for (j=i+1 ; j<r ; j++)
    2174                         indices[j] = indices[j-1] + 1;
    2175 
    2176                 /* Update the result tuple for the new indices
    2177                    starting with i, the leftmost index that changed */
    2178                 for ( ; i<r ; i++) {
    2179                         index = indices[i];
    2180                         elem = PyTuple_GET_ITEM(pool, index);
    2181                         Py_INCREF(elem);
    2182                         oldelem = PyTuple_GET_ITEM(result, i);
    2183                         PyTuple_SET_ITEM(result, i, elem);
    2184                         Py_DECREF(oldelem);
    2185                 }
    2186         }
    2187 
    2188         Py_INCREF(result);
    2189         return result;
     2140    PyObject *elem;
     2141    PyObject *oldelem;
     2142    PyObject *pool = co->pool;
     2143    Py_ssize_t *indices = co->indices;
     2144    PyObject *result = co->result;
     2145    Py_ssize_t n = PyTuple_GET_SIZE(pool);
     2146    Py_ssize_t r = co->r;
     2147    Py_ssize_t i, j, index;
     2148
     2149    if (co->stopped)
     2150        return NULL;
     2151
     2152    if (result == NULL) {
     2153        /* On the first pass, initialize result tuple using the indices */
     2154        result = PyTuple_New(r);
     2155        if (result == NULL)
     2156            goto empty;
     2157        co->result = result;
     2158        for (i=0; i<r ; i++) {
     2159            index = indices[i];
     2160            elem = PyTuple_GET_ITEM(pool, index);
     2161            Py_INCREF(elem);
     2162            PyTuple_SET_ITEM(result, i, elem);
     2163        }
     2164    } else {
     2165        /* Copy the previous result tuple or re-use it if available */
     2166        if (Py_REFCNT(result) > 1) {
     2167            PyObject *old_result = result;
     2168            result = PyTuple_New(r);
     2169            if (result == NULL)
     2170                goto empty;
     2171            co->result = result;
     2172            for (i=0; i<r ; i++) {
     2173                elem = PyTuple_GET_ITEM(old_result, i);
     2174                Py_INCREF(elem);
     2175                PyTuple_SET_ITEM(result, i, elem);
     2176            }
     2177            Py_DECREF(old_result);
     2178        }
     2179        /* Now, we've got the only copy so we can update it in-place
     2180         * CPython's empty tuple is a singleton and cached in
     2181         * PyTuple's freelist.
     2182        */
     2183        assert(r == 0 || Py_REFCNT(result) == 1);
     2184
     2185        /* Scan indices right-to-left until finding one that is not
     2186           at its maximum (i + n - r). */
     2187        for (i=r-1 ; i >= 0 && indices[i] == i+n-r ; i--)
     2188            ;
     2189
     2190        /* If i is negative, then the indices are all at
     2191           their maximum value and we're done. */
     2192        if (i < 0)
     2193            goto empty;
     2194
     2195        /* Increment the current index which we know is not at its
     2196           maximum.  Then move back to the right setting each index
     2197           to its lowest possible value (one higher than the index
     2198           to its left -- this maintains the sort order invariant). */
     2199        indices[i]++;
     2200        for (j=i+1 ; j<r ; j++)
     2201            indices[j] = indices[j-1] + 1;
     2202
     2203        /* Update the result tuple for the new indices
     2204           starting with i, the leftmost index that changed */
     2205        for ( ; i<r ; i++) {
     2206            index = indices[i];
     2207            elem = PyTuple_GET_ITEM(pool, index);
     2208            Py_INCREF(elem);
     2209            oldelem = PyTuple_GET_ITEM(result, i);
     2210            PyTuple_SET_ITEM(result, i, elem);
     2211            Py_DECREF(oldelem);
     2212        }
     2213    }
     2214
     2215    Py_INCREF(result);
     2216    return result;
    21902217
    21912218empty:
    2192         co->stopped = 1;
    2193         return NULL;
     2219    co->stopped = 1;
     2220    return NULL;
    21942221}
    21952222
     
    22012228
    22022229static PyTypeObject combinations_type = {
    2203         PyVarObject_HEAD_INIT(NULL, 0)
    2204         "itertools.combinations",               /* tp_name */
    2205         sizeof(combinationsobject),     /* tp_basicsize */
    2206         0,                              /* tp_itemsize */
    2207         /* methods */
    2208         (destructor)combinations_dealloc,       /* tp_dealloc */
    2209         0,                              /* tp_print */
    2210         0,                              /* tp_getattr */
    2211         0,                              /* tp_setattr */
    2212         0,                              /* tp_compare */
    2213         0,                              /* tp_repr */
    2214         0,                              /* tp_as_number */
    2215         0,                              /* tp_as_sequence */
    2216         0,                              /* tp_as_mapping */
    2217         0,                              /* tp_hash */
    2218         0,                              /* tp_call */
    2219         0,                              /* tp_str */
    2220         PyObject_GenericGetAttr,        /* tp_getattro */
    2221         0,                              /* tp_setattro */
    2222         0,                              /* tp_as_buffer */
    2223         Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC |
    2224                 Py_TPFLAGS_BASETYPE,    /* tp_flags */
    2225         combinations_doc,                       /* tp_doc */
    2226         (traverseproc)combinations_traverse,    /* tp_traverse */
    2227         0,                              /* tp_clear */
    2228         0,                              /* tp_richcompare */
    2229         0,                              /* tp_weaklistoffset */
    2230         PyObject_SelfIter,              /* tp_iter */
    2231         (iternextfunc)combinations_next,        /* tp_iternext */
    2232         0,                              /* tp_methods */
    2233         0,                              /* tp_members */
    2234         0,                              /* tp_getset */
    2235         0,                              /* tp_base */
    2236         0,                              /* tp_dict */
    2237         0,                              /* tp_descr_get */
    2238         0,                              /* tp_descr_set */
    2239         0,                              /* tp_dictoffset */
    2240         0,                              /* tp_init */
    2241         0,                              /* tp_alloc */
    2242         combinations_new,                       /* tp_new */
    2243         PyObject_GC_Del,                /* tp_free */
     2230    PyVarObject_HEAD_INIT(NULL, 0)
     2231    "itertools.combinations",                   /* tp_name */
     2232    sizeof(combinationsobject),         /* tp_basicsize */
     2233    0,                                  /* tp_itemsize */
     2234    /* methods */
     2235    (destructor)combinations_dealloc,           /* tp_dealloc */
     2236    0,                                  /* tp_print */
     2237    0,                                  /* tp_getattr */
     2238    0,                                  /* tp_setattr */
     2239    0,                                  /* tp_compare */
     2240    0,                                  /* tp_repr */
     2241    0,                                  /* tp_as_number */
     2242    0,                                  /* tp_as_sequence */
     2243    0,                                  /* tp_as_mapping */
     2244    0,                                  /* tp_hash */
     2245    0,                                  /* tp_call */
     2246    0,                                  /* tp_str */
     2247    PyObject_GenericGetAttr,            /* tp_getattro */
     2248    0,                                  /* tp_setattro */
     2249    0,                                  /* tp_as_buffer */
     2250    Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC |
     2251        Py_TPFLAGS_BASETYPE,            /* tp_flags */
     2252    combinations_doc,                           /* tp_doc */
     2253    (traverseproc)combinations_traverse,        /* tp_traverse */
     2254    0,                                  /* tp_clear */
     2255    0,                                  /* tp_richcompare */
     2256    0,                                  /* tp_weaklistoffset */
     2257    PyObject_SelfIter,                  /* tp_iter */
     2258    (iternextfunc)combinations_next,            /* tp_iternext */
     2259    0,                                  /* tp_methods */
     2260    0,                                  /* tp_members */
     2261    0,                                  /* tp_getset */
     2262    0,                                  /* tp_base */
     2263    0,                                  /* tp_dict */
     2264    0,                                  /* tp_descr_get */
     2265    0,                                  /* tp_descr_set */
     2266    0,                                  /* tp_dictoffset */
     2267    0,                                  /* tp_init */
     2268    0,                                  /* tp_alloc */
     2269    combinations_new,                           /* tp_new */
     2270    PyObject_GC_Del,                    /* tp_free */
    22442271};
    22452272
    22462273
     2274/* combinations with replacement object *******************************************/
     2275
     2276/* Equivalent to:
     2277
     2278        def combinations_with_replacement(iterable, r):
     2279            "combinations_with_replacement('ABC', 2) --> AA AB AC BB BC CC"
     2280            # number items returned:  (n+r-1)! / r! / (n-1)!
     2281            pool = tuple(iterable)
     2282            n = len(pool)
     2283            indices = [0] * r
     2284            yield tuple(pool[i] for i in indices)
     2285            while 1:
     2286                for i in reversed(range(r)):
     2287                    if indices[i] != n - 1:
     2288                        break
     2289                else:
     2290                    return
     2291                indices[i:] = [indices[i] + 1] * (r - i)
     2292                yield tuple(pool[i] for i in indices)
     2293
     2294        def combinations_with_replacement2(iterable, r):
     2295            'Alternate version that filters from product()'
     2296            pool = tuple(iterable)
     2297            n = len(pool)
     2298            for indices in product(range(n), repeat=r):
     2299                if sorted(indices) == list(indices):
     2300                    yield tuple(pool[i] for i in indices)
     2301*/
     2302typedef struct {
     2303    PyObject_HEAD
     2304    PyObject *pool;                     /* input converted to a tuple */
     2305    Py_ssize_t *indices;    /* one index per result element */
     2306    PyObject *result;       /* most recently returned result tuple */
     2307    Py_ssize_t r;                       /* size of result tuple */
     2308    int stopped;                        /* set to 1 when the cwr iterator is exhausted */
     2309} cwrobject;
     2310
     2311static PyTypeObject cwr_type;
     2312
     2313static PyObject *
     2314cwr_new(PyTypeObject *type, PyObject *args, PyObject *kwds)
     2315{
     2316    cwrobject *co;
     2317    Py_ssize_t n;
     2318    Py_ssize_t r;
     2319    PyObject *pool = NULL;
     2320    PyObject *iterable = NULL;
     2321    Py_ssize_t *indices = NULL;
     2322    Py_ssize_t i;
     2323    static char *kwargs[] = {"iterable", "r", NULL};
     2324
     2325    if (!PyArg_ParseTupleAndKeywords(args, kwds, "On:combinations_with_replacement", kwargs,
     2326                                     &iterable, &r))
     2327        return NULL;
     2328
     2329    pool = PySequence_Tuple(iterable);
     2330    if (pool == NULL)
     2331        goto error;
     2332    n = PyTuple_GET_SIZE(pool);
     2333    if (r < 0) {
     2334        PyErr_SetString(PyExc_ValueError, "r must be non-negative");
     2335        goto error;
     2336    }
     2337
     2338    indices = PyMem_Malloc(r * sizeof(Py_ssize_t));
     2339    if (indices == NULL) {
     2340        PyErr_NoMemory();
     2341        goto error;
     2342    }
     2343
     2344    for (i=0 ; i<r ; i++)
     2345        indices[i] = 0;
     2346
     2347    /* create cwrobject structure */
     2348    co = (cwrobject *)type->tp_alloc(type, 0);
     2349    if (co == NULL)
     2350        goto error;
     2351
     2352    co->pool = pool;
     2353    co->indices = indices;
     2354    co->result = NULL;
     2355    co->r = r;
     2356    co->stopped = !n && r;
     2357
     2358    return (PyObject *)co;
     2359
     2360error:
     2361    if (indices != NULL)
     2362        PyMem_Free(indices);
     2363    Py_XDECREF(pool);
     2364    return NULL;
     2365}
     2366
     2367static void
     2368cwr_dealloc(cwrobject *co)
     2369{
     2370    PyObject_GC_UnTrack(co);
     2371    Py_XDECREF(co->pool);
     2372    Py_XDECREF(co->result);
     2373    if (co->indices != NULL)
     2374        PyMem_Free(co->indices);
     2375    Py_TYPE(co)->tp_free(co);
     2376}
     2377
     2378static int
     2379cwr_traverse(cwrobject *co, visitproc visit, void *arg)
     2380{
     2381    Py_VISIT(co->pool);
     2382    Py_VISIT(co->result);
     2383    return 0;
     2384}
     2385
     2386static PyObject *
     2387cwr_next(cwrobject *co)
     2388{
     2389    PyObject *elem;
     2390    PyObject *oldelem;
     2391    PyObject *pool = co->pool;
     2392    Py_ssize_t *indices = co->indices;
     2393    PyObject *result = co->result;
     2394    Py_ssize_t n = PyTuple_GET_SIZE(pool);
     2395    Py_ssize_t r = co->r;
     2396    Py_ssize_t i, j, index;
     2397
     2398    if (co->stopped)
     2399        return NULL;
     2400
     2401    if (result == NULL) {
     2402        /* On the first pass, initialize result tuple using the indices */
     2403        result = PyTuple_New(r);
     2404        if (result == NULL)
     2405            goto empty;
     2406        co->result = result;
     2407        for (i=0; i<r ; i++) {
     2408            index = indices[i];
     2409            elem = PyTuple_GET_ITEM(pool, index);
     2410            Py_INCREF(elem);
     2411            PyTuple_SET_ITEM(result, i, elem);
     2412        }
     2413    } else {
     2414        /* Copy the previous result tuple or re-use it if available */
     2415        if (Py_REFCNT(result) > 1) {
     2416            PyObject *old_result = result;
     2417            result = PyTuple_New(r);
     2418            if (result == NULL)
     2419                goto empty;
     2420            co->result = result;
     2421            for (i=0; i<r ; i++) {
     2422                elem = PyTuple_GET_ITEM(old_result, i);
     2423                Py_INCREF(elem);
     2424                PyTuple_SET_ITEM(result, i, elem);
     2425            }
     2426            Py_DECREF(old_result);
     2427        }
     2428        /* Now, we've got the only copy so we can update it in-place CPython's
     2429           empty tuple is a singleton and cached in PyTuple's freelist. */
     2430        assert(r == 0 || Py_REFCNT(result) == 1);
     2431
     2432    /* Scan indices right-to-left until finding one that is not
     2433     * at its maximum (n-1). */
     2434        for (i=r-1 ; i >= 0 && indices[i] == n-1; i--)
     2435            ;
     2436
     2437        /* If i is negative, then the indices are all at
     2438       their maximum value and we're done. */
     2439        if (i < 0)
     2440            goto empty;
     2441
     2442        /* Increment the current index which we know is not at its
     2443       maximum.  Then set all to the right to the same value. */
     2444        indices[i]++;
     2445        for (j=i+1 ; j<r ; j++)
     2446            indices[j] = indices[j-1];
     2447
     2448        /* Update the result tuple for the new indices
     2449           starting with i, the leftmost index that changed */
     2450        for ( ; i<r ; i++) {
     2451            index = indices[i];
     2452            elem = PyTuple_GET_ITEM(pool, index);
     2453            Py_INCREF(elem);
     2454            oldelem = PyTuple_GET_ITEM(result, i);
     2455            PyTuple_SET_ITEM(result, i, elem);
     2456            Py_DECREF(oldelem);
     2457        }
     2458    }
     2459
     2460    Py_INCREF(result);
     2461    return result;
     2462
     2463empty:
     2464    co->stopped = 1;
     2465    return NULL;
     2466}
     2467
     2468PyDoc_STRVAR(cwr_doc,
     2469"combinations_with_replacement(iterable, r) --> combinations_with_replacement object\n\
     2470\n\
     2471Return successive r-length combinations of elements in the iterable\n\
     2472allowing individual elements to have successive repeats.\n\
     2473combinations_with_replacement('ABC', 2) --> AA AB AC BB BC CC");
     2474
     2475static PyTypeObject cwr_type = {
     2476    PyVarObject_HEAD_INIT(NULL, 0)
     2477    "itertools.combinations_with_replacement",                  /* tp_name */
     2478    sizeof(cwrobject),                  /* tp_basicsize */
     2479    0,                                                  /* tp_itemsize */
     2480    /* methods */
     2481    (destructor)cwr_dealloc,            /* tp_dealloc */
     2482    0,                                                  /* tp_print */
     2483    0,                                                  /* tp_getattr */
     2484    0,                                                  /* tp_setattr */
     2485    0,                                                  /* tp_compare */
     2486    0,                                                  /* tp_repr */
     2487    0,                                                  /* tp_as_number */
     2488    0,                                                  /* tp_as_sequence */
     2489    0,                                                  /* tp_as_mapping */
     2490    0,                                                  /* tp_hash */
     2491    0,                                                  /* tp_call */
     2492    0,                                                  /* tp_str */
     2493    PyObject_GenericGetAttr,            /* tp_getattro */
     2494    0,                                                  /* tp_setattro */
     2495    0,                                                  /* tp_as_buffer */
     2496    Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC |
     2497        Py_TPFLAGS_BASETYPE,            /* tp_flags */
     2498    cwr_doc,                                    /* tp_doc */
     2499    (traverseproc)cwr_traverse,         /* tp_traverse */
     2500    0,                                                  /* tp_clear */
     2501    0,                                                  /* tp_richcompare */
     2502    0,                                                  /* tp_weaklistoffset */
     2503    PyObject_SelfIter,                  /* tp_iter */
     2504    (iternextfunc)cwr_next,     /* tp_iternext */
     2505    0,                                                  /* tp_methods */
     2506    0,                                                  /* tp_members */
     2507    0,                                                  /* tp_getset */
     2508    0,                                                  /* tp_base */
     2509    0,                                                  /* tp_dict */
     2510    0,                                                  /* tp_descr_get */
     2511    0,                                                  /* tp_descr_set */
     2512    0,                                                  /* tp_dictoffset */
     2513    0,                                                  /* tp_init */
     2514    0,                                                  /* tp_alloc */
     2515    cwr_new,                                    /* tp_new */
     2516    PyObject_GC_Del,                    /* tp_free */
     2517};
     2518
     2519
    22472520/* permutations object ************************************************************
    2248  
     2521
    22492522def permutations(iterable, r=None):
    22502523    'permutations(range(3), 2) --> (0,1) (0,2) (1,0) (1,2) (2,0) (2,1)'
     
    22562529    yield tuple(pool[i] for i in indices[:r])
    22572530    while n:
    2258         for i in reversed(range(r)):
    2259             cycles[i] -= 1
    2260             if cycles[i] == 0:
    2261                 indices[i:] = indices[i+1:] + indices[i:i+1]
    2262                 cycles[i] = n - i
    2263             else:
    2264                 j = cycles[i]
    2265                 indices[i], indices[-j] = indices[-j], indices[i]
    2266                 yield tuple(pool[i] for i in indices[:r])
    2267                 break
     2531    for i in reversed(range(r)):
     2532        cycles[i] -= 1
     2533        if cycles[i] == 0:
     2534        indices[i:] = indices[i+1:] + indices[i:i+1]
     2535        cycles[i] = n - i
    22682536        else:
    2269             return
     2537        j = cycles[i]
     2538        indices[i], indices[-j] = indices[-j], indices[i]
     2539        yield tuple(pool[i] for i in indices[:r])
     2540        break
     2541    else:
     2542        return
    22702543*/
    22712544
    22722545typedef struct {
    2273         PyObject_HEAD
    2274         PyObject *pool;                 /* input converted to a tuple */
    2275         Py_ssize_t *indices;            /* one index per element in the pool */
    2276         Py_ssize_t *cycles;             /* one rollover counter per element in the result */
    2277         PyObject *result;               /* most recently returned result tuple */
    2278         Py_ssize_t r;                   /* size of result tuple */
    2279         int stopped;                    /* set to 1 when the permutations iterator is exhausted */
     2546    PyObject_HEAD
     2547    PyObject *pool;                     /* input converted to a tuple */
     2548    Py_ssize_t *indices;            /* one index per element in the pool */
     2549    Py_ssize_t *cycles;                 /* one rollover counter per element in the result */
     2550    PyObject *result;               /* most recently returned result tuple */
     2551    Py_ssize_t r;                       /* size of result tuple */
     2552    int stopped;                        /* set to 1 when the permutations iterator is exhausted */
    22802553} permutationsobject;
    22812554
     
    22852558permutations_new(PyTypeObject *type, PyObject *args, PyObject *kwds)
    22862559{
    2287         permutationsobject *po;
    2288         Py_ssize_t n;
    2289         Py_ssize_t r;
    2290         PyObject *robj = Py_None;
    2291         PyObject *pool = NULL;
    2292         PyObject *iterable = NULL;
    2293         Py_ssize_t *indices = NULL;
    2294         Py_ssize_t *cycles = NULL;
    2295         Py_ssize_t i;
    2296         static char *kwargs[] = {"iterable", "r", NULL};
    2297  
    2298         if (!PyArg_ParseTupleAndKeywords(args, kwds, "O|O:permutations", kwargs,
    2299                                         &iterable, &robj))
    2300                 return NULL;
    2301 
    2302         pool = PySequence_Tuple(iterable);
    2303         if (pool == NULL)
    2304                 goto error;
    2305         n = PyTuple_GET_SIZE(pool);
    2306 
    2307         r = n;
    2308         if (robj != Py_None) {
    2309                 r = PyInt_AsSsize_t(robj);
    2310                 if (r == -1 && PyErr_Occurred())
    2311                         goto error;
    2312         }
    2313         if (r < 0) {
    2314                 PyErr_SetString(PyExc_ValueError, "r must be non-negative");
    2315                 goto error;
    2316         }
    2317 
    2318         indices = PyMem_Malloc(n * sizeof(Py_ssize_t));
    2319         cycles = PyMem_Malloc(r * sizeof(Py_ssize_t));
    2320         if (indices == NULL || cycles == NULL) {
    2321                 PyErr_NoMemory();
    2322                 goto error;
    2323         }
    2324 
    2325         for (i=0 ; i<n ; i++)
    2326                 indices[i] = i;
    2327         for (i=0 ; i<r ; i++)
    2328                 cycles[i] = n - i;
    2329 
    2330         /* create permutationsobject structure */
    2331         po = (permutationsobject *)type->tp_alloc(type, 0);
    2332         if (po == NULL)
    2333                 goto error;
    2334 
    2335         po->pool = pool;
    2336         po->indices = indices;
    2337         po->cycles = cycles;
    2338         po->result = NULL;
    2339         po->r = r;
    2340         po->stopped = r > n ? 1 : 0;
    2341 
    2342         return (PyObject *)po;
     2560    permutationsobject *po;
     2561    Py_ssize_t n;
     2562    Py_ssize_t r;
     2563    PyObject *robj = Py_None;
     2564    PyObject *pool = NULL;
     2565    PyObject *iterable = NULL;
     2566    Py_ssize_t *indices = NULL;
     2567    Py_ssize_t *cycles = NULL;
     2568    Py_ssize_t i;
     2569    static char *kwargs[] = {"iterable", "r", NULL};
     2570
     2571    if (!PyArg_ParseTupleAndKeywords(args, kwds, "O|O:permutations", kwargs,
     2572                                    &iterable, &robj))
     2573        return NULL;
     2574
     2575    pool = PySequence_Tuple(iterable);
     2576    if (pool == NULL)
     2577        goto error;
     2578    n = PyTuple_GET_SIZE(pool);
     2579
     2580    r = n;
     2581    if (robj != Py_None) {
     2582        r = PyInt_AsSsize_t(robj);
     2583        if (r == -1 && PyErr_Occurred())
     2584            goto error;
     2585    }
     2586    if (r < 0) {
     2587        PyErr_SetString(PyExc_ValueError, "r must be non-negative");
     2588        goto error;
     2589    }
     2590
     2591    indices = PyMem_Malloc(n * sizeof(Py_ssize_t));
     2592    cycles = PyMem_Malloc(r * sizeof(Py_ssize_t));
     2593    if (indices == NULL || cycles == NULL) {
     2594        PyErr_NoMemory();
     2595        goto error;
     2596    }
     2597
     2598    for (i=0 ; i<n ; i++)
     2599        indices[i] = i;
     2600    for (i=0 ; i<r ; i++)
     2601        cycles[i] = n - i;
     2602
     2603    /* create permutationsobject structure */
     2604    po = (permutationsobject *)type->tp_alloc(type, 0);
     2605    if (po == NULL)
     2606        goto error;
     2607
     2608    po->pool = pool;
     2609    po->indices = indices;
     2610    po->cycles = cycles;
     2611    po->result = NULL;
     2612    po->r = r;
     2613    po->stopped = r > n ? 1 : 0;
     2614
     2615    return (PyObject *)po;
    23432616
    23442617error:
    2345         if (indices != NULL)
    2346                 PyMem_Free(indices);
    2347         if (cycles != NULL)
    2348                 PyMem_Free(cycles);
    2349         Py_XDECREF(pool);
    2350         return NULL;
     2618    if (indices != NULL)
     2619        PyMem_Free(indices);
     2620    if (cycles != NULL)
     2621        PyMem_Free(cycles);
     2622    Py_XDECREF(pool);
     2623    return NULL;
    23512624}
    23522625
     
    23542627permutations_dealloc(permutationsobject *po)
    23552628{
    2356         PyObject_GC_UnTrack(po);
    2357         Py_XDECREF(po->pool);
    2358         Py_XDECREF(po->result);
    2359         PyMem_Free(po->indices);
    2360         PyMem_Free(po->cycles);
    2361         Py_TYPE(po)->tp_free(po);
     2629    PyObject_GC_UnTrack(po);
     2630    Py_XDECREF(po->pool);
     2631    Py_XDECREF(po->result);
     2632    PyMem_Free(po->indices);
     2633    PyMem_Free(po->cycles);
     2634    Py_TYPE(po)->tp_free(po);
    23622635}
    23632636
     
    23652638permutations_traverse(permutationsobject *po, visitproc visit, void *arg)
    23662639{
    2367         Py_VISIT(po->pool);
    2368         Py_VISIT(po->result);
    2369         return 0;
     2640    Py_VISIT(po->pool);
     2641    Py_VISIT(po->result);
     2642    return 0;
    23702643}
    23712644
     
    23732646permutations_next(permutationsobject *po)
    23742647{
    2375         PyObject *elem;
    2376         PyObject *oldelem;
    2377         PyObject *pool = po->pool;
    2378         Py_ssize_t *indices = po->indices;
    2379         Py_ssize_t *cycles = po->cycles;
    2380         PyObject *result = po->result;
    2381         Py_ssize_t n = PyTuple_GET_SIZE(pool);
    2382         Py_ssize_t r = po->r;
    2383         Py_ssize_t i, j, k, index;
    2384 
    2385         if (po->stopped)
    2386                 return NULL;
    2387 
    2388         if (result == NULL) {
    2389                 /* On the first pass, initialize result tuple using the indices */
    2390                 result = PyTuple_New(r);
    2391                 if (result == NULL)
    2392                         goto empty;
    2393                 po->result = result;
    2394                 for (i=0; i<r ; i++) {
    2395                         index = indices[i];
    2396                         elem = PyTuple_GET_ITEM(pool, index);
    2397                         Py_INCREF(elem);
    2398                         PyTuple_SET_ITEM(result, i, elem);
    2399                 }
    2400         } else {
    2401                 if (n == 0)
    2402                         goto empty;
    2403 
    2404                 /* Copy the previous result tuple or re-use it if available */
    2405                 if (Py_REFCNT(result) > 1) {
    2406                         PyObject *old_result = result;
    2407                         result = PyTuple_New(r);
    2408                         if (result == NULL)
    2409                                 goto empty;
    2410                         po->result = result;
    2411                         for (i=0; i<r ; i++) {
    2412                                 elem = PyTuple_GET_ITEM(old_result, i);
    2413                                 Py_INCREF(elem);
    2414                                 PyTuple_SET_ITEM(result, i, elem);
    2415                         }
    2416                         Py_DECREF(old_result);
    2417                 }
    2418                 /* Now, we've got the only copy so we can update it in-place */
    2419                 assert(r == 0 || Py_REFCNT(result) == 1);
    2420 
    2421                 /* Decrement rightmost cycle, moving leftward upon zero rollover */
    2422                 for (i=r-1 ; i>=0 ; i--) {
    2423                         cycles[i] -= 1;
    2424                         if (cycles[i] == 0) {
    2425                                 /* rotatation: indices[i:] = indices[i+1:] + indices[i:i+1] */
    2426                                 index = indices[i];
    2427                                 for (j=i ; j<n-1 ; j++)
    2428                                         indices[j] = indices[j+1];
    2429                                 indices[n-1] = index;
    2430                                 cycles[i] = n - i;
    2431                         } else {
    2432                                 j = cycles[i];
    2433                                 index = indices[i];
    2434                                 indices[i] = indices[n-j];
    2435                                 indices[n-j] = index;
    2436 
    2437                                 for (k=i; k<r ; k++) {
    2438                                         /* start with i, the leftmost element that changed */
    2439                                         /* yield tuple(pool[k] for k in indices[:r]) */
    2440                                         index = indices[k];
    2441                                         elem = PyTuple_GET_ITEM(pool, index);
    2442                                         Py_INCREF(elem);
    2443                                         oldelem = PyTuple_GET_ITEM(result, k);
    2444                                         PyTuple_SET_ITEM(result, k, elem);
    2445                                         Py_DECREF(oldelem);
    2446                                 }
    2447                                 break;
    2448                         }
    2449                 }
    2450                 /* If i is negative, then the cycles have all
    2451                    rolled-over and we're done. */
    2452                 if (i < 0)
    2453                         goto empty;
    2454         }
    2455         Py_INCREF(result);
    2456         return result;
     2648    PyObject *elem;
     2649    PyObject *oldelem;
     2650    PyObject *pool = po->pool;
     2651    Py_ssize_t *indices = po->indices;
     2652    Py_ssize_t *cycles = po->cycles;
     2653    PyObject *result = po->result;
     2654    Py_ssize_t n = PyTuple_GET_SIZE(pool);
     2655    Py_ssize_t r = po->r;
     2656    Py_ssize_t i, j, k, index;
     2657
     2658    if (po->stopped)
     2659        return NULL;
     2660
     2661    if (result == NULL) {
     2662        /* On the first pass, initialize result tuple using the indices */
     2663        result = PyTuple_New(r);
     2664        if (result == NULL)
     2665            goto empty;
     2666        po->result = result;
     2667        for (i=0; i<r ; i++) {
     2668            index = indices[i];
     2669            elem = PyTuple_GET_ITEM(pool, index);
     2670            Py_INCREF(elem);
     2671            PyTuple_SET_ITEM(result, i, elem);
     2672        }
     2673    } else {
     2674        if (n == 0)
     2675            goto empty;
     2676
     2677        /* Copy the previous result tuple or re-use it if available */
     2678        if (Py_REFCNT(result) > 1) {
     2679            PyObject *old_result = result;
     2680            result = PyTuple_New(r);
     2681            if (result == NULL)
     2682                goto empty;
     2683            po->result = result;
     2684            for (i=0; i<r ; i++) {
     2685                elem = PyTuple_GET_ITEM(old_result, i);
     2686                Py_INCREF(elem);
     2687                PyTuple_SET_ITEM(result, i, elem);
     2688            }
     2689            Py_DECREF(old_result);
     2690        }
     2691        /* Now, we've got the only copy so we can update it in-place */
     2692        assert(r == 0 || Py_REFCNT(result) == 1);
     2693
     2694        /* Decrement rightmost cycle, moving leftward upon zero rollover */
     2695        for (i=r-1 ; i>=0 ; i--) {
     2696            cycles[i] -= 1;
     2697            if (cycles[i] == 0) {
     2698                /* rotatation: indices[i:] = indices[i+1:] + indices[i:i+1] */
     2699                index = indices[i];
     2700                for (j=i ; j<n-1 ; j++)
     2701                    indices[j] = indices[j+1];
     2702                indices[n-1] = index;
     2703                cycles[i] = n - i;
     2704            } else {
     2705                j = cycles[i];
     2706                index = indices[i];
     2707                indices[i] = indices[n-j];
     2708                indices[n-j] = index;
     2709
     2710                for (k=i; k<r ; k++) {
     2711                    /* start with i, the leftmost element that changed */
     2712                    /* yield tuple(pool[k] for k in indices[:r]) */
     2713                    index = indices[k];
     2714                    elem = PyTuple_GET_ITEM(pool, index);
     2715                    Py_INCREF(elem);
     2716                    oldelem = PyTuple_GET_ITEM(result, k);
     2717                    PyTuple_SET_ITEM(result, k, elem);
     2718                    Py_DECREF(oldelem);
     2719                }
     2720                break;
     2721            }
     2722        }
     2723        /* If i is negative, then the cycles have all
     2724           rolled-over and we're done. */
     2725        if (i < 0)
     2726            goto empty;
     2727    }
     2728    Py_INCREF(result);
     2729    return result;
    24572730
    24582731empty:
    2459         po->stopped = 1;
    2460         return NULL;
     2732    po->stopped = 1;
     2733    return NULL;
    24612734}
    24622735
     
    24682741
    24692742static PyTypeObject permutations_type = {
    2470         PyVarObject_HEAD_INIT(NULL, 0)
    2471         "itertools.permutations",               /* tp_name */
    2472         sizeof(permutationsobject),     /* tp_basicsize */
    2473         0,                              /* tp_itemsize */
    2474         /* methods */
    2475         (destructor)permutations_dealloc,       /* tp_dealloc */
    2476         0,                              /* tp_print */
    2477         0,                              /* tp_getattr */
    2478         0,                              /* tp_setattr */
    2479         0,                              /* tp_compare */
    2480         0,                              /* tp_repr */
    2481         0,                              /* tp_as_number */
    2482         0,                              /* tp_as_sequence */
    2483         0,                              /* tp_as_mapping */
    2484         0,                              /* tp_hash */
    2485         0,                              /* tp_call */
    2486         0,                              /* tp_str */
    2487         PyObject_GenericGetAttr,        /* tp_getattro */
    2488         0,                              /* tp_setattro */
    2489         0,                              /* tp_as_buffer */
    2490         Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC |
    2491                 Py_TPFLAGS_BASETYPE,    /* tp_flags */
    2492         permutations_doc,                       /* tp_doc */
    2493         (traverseproc)permutations_traverse,    /* tp_traverse */
    2494         0,                              /* tp_clear */
    2495         0,                              /* tp_richcompare */
    2496         0,                              /* tp_weaklistoffset */
    2497         PyObject_SelfIter,              /* tp_iter */
    2498         (iternextfunc)permutations_next,        /* tp_iternext */
    2499         0,                              /* tp_methods */
    2500         0,                              /* tp_members */
    2501         0,                              /* tp_getset */
    2502         0,                              /* tp_base */
    2503         0,                              /* tp_dict */
    2504         0,                              /* tp_descr_get */
    2505         0,                              /* tp_descr_set */
    2506         0,                              /* tp_dictoffset */
    2507         0,                              /* tp_init */
    2508         0,                              /* tp_alloc */
    2509         permutations_new,                       /* tp_new */
    2510         PyObject_GC_Del,                /* tp_free */
     2743    PyVarObject_HEAD_INIT(NULL, 0)
     2744    "itertools.permutations",                   /* tp_name */
     2745    sizeof(permutationsobject),         /* tp_basicsize */
     2746    0,                                  /* tp_itemsize */
     2747    /* methods */
     2748    (destructor)permutations_dealloc,           /* tp_dealloc */
     2749    0,                                  /* tp_print */
     2750    0,                                  /* tp_getattr */
     2751    0,                                  /* tp_setattr */
     2752    0,                                  /* tp_compare */
     2753    0,                                  /* tp_repr */
     2754    0,                                  /* tp_as_number */
     2755    0,                                  /* tp_as_sequence */
     2756    0,                                  /* tp_as_mapping */
     2757    0,                                  /* tp_hash */
     2758    0,                                  /* tp_call */
     2759    0,                                  /* tp_str */
     2760    PyObject_GenericGetAttr,            /* tp_getattro */
     2761    0,                                  /* tp_setattro */
     2762    0,                                  /* tp_as_buffer */
     2763    Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC |
     2764        Py_TPFLAGS_BASETYPE,            /* tp_flags */
     2765    permutations_doc,                           /* tp_doc */
     2766    (traverseproc)permutations_traverse,        /* tp_traverse */
     2767    0,                                  /* tp_clear */
     2768    0,                                  /* tp_richcompare */
     2769    0,                                  /* tp_weaklistoffset */
     2770    PyObject_SelfIter,                  /* tp_iter */
     2771    (iternextfunc)permutations_next,            /* tp_iternext */
     2772    0,                                  /* tp_methods */
     2773    0,                                  /* tp_members */
     2774    0,                                  /* tp_getset */
     2775    0,                                  /* tp_base */
     2776    0,                                  /* tp_dict */
     2777    0,                                  /* tp_descr_get */
     2778    0,                                  /* tp_descr_set */
     2779    0,                                  /* tp_dictoffset */
     2780    0,                                  /* tp_init */
     2781    0,                                  /* tp_alloc */
     2782    permutations_new,                           /* tp_new */
     2783    PyObject_GC_Del,                    /* tp_free */
    25112784};
    25122785
    25132786
     2787/* compress object ************************************************************/
     2788
     2789/* Equivalent to:
     2790
     2791    def compress(data, selectors):
     2792        "compress('ABCDEF', [1,0,1,0,1,1]) --> A C E F"
     2793        return (d for d, s in izip(data, selectors) if s)
     2794*/
     2795
     2796typedef struct {
     2797    PyObject_HEAD
     2798    PyObject *data;
     2799    PyObject *selectors;
     2800} compressobject;
     2801
     2802static PyTypeObject compress_type;
     2803
     2804static PyObject *
     2805compress_new(PyTypeObject *type, PyObject *args, PyObject *kwds)
     2806{
     2807    PyObject *seq1, *seq2;
     2808    PyObject *data=NULL, *selectors=NULL;
     2809    compressobject *lz;
     2810    static char *kwargs[] = {"data", "selectors", NULL};
     2811
     2812    if (!PyArg_ParseTupleAndKeywords(args, kwds, "OO:compress", kwargs, &seq1, &seq2))
     2813        return NULL;
     2814
     2815    data = PyObject_GetIter(seq1);
     2816    if (data == NULL)
     2817        goto fail;
     2818    selectors = PyObject_GetIter(seq2);
     2819    if (selectors == NULL)
     2820        goto fail;
     2821
     2822    /* create compressobject structure */
     2823    lz = (compressobject *)type->tp_alloc(type, 0);
     2824    if (lz == NULL)
     2825        goto fail;
     2826    lz->data = data;
     2827    lz->selectors = selectors;
     2828    return (PyObject *)lz;
     2829
     2830fail:
     2831    Py_XDECREF(data);
     2832    Py_XDECREF(selectors);
     2833    return NULL;
     2834}
     2835
     2836static void
     2837compress_dealloc(compressobject *lz)
     2838{
     2839    PyObject_GC_UnTrack(lz);
     2840    Py_XDECREF(lz->data);
     2841    Py_XDECREF(lz->selectors);
     2842    Py_TYPE(lz)->tp_free(lz);
     2843}
     2844
     2845static int
     2846compress_traverse(compressobject *lz, visitproc visit, void *arg)
     2847{
     2848    Py_VISIT(lz->data);
     2849    Py_VISIT(lz->selectors);
     2850    return 0;
     2851}
     2852
     2853static PyObject *
     2854compress_next(compressobject *lz)
     2855{
     2856    PyObject *data = lz->data, *selectors = lz->selectors;
     2857    PyObject *datum, *selector;
     2858    PyObject *(*datanext)(PyObject *) = *Py_TYPE(data)->tp_iternext;
     2859    PyObject *(*selectornext)(PyObject *) = *Py_TYPE(selectors)->tp_iternext;
     2860    int ok;
     2861
     2862    while (1) {
     2863        /* Steps:  get datum, get selector, evaluate selector.
     2864           Order is important (to match the pure python version
     2865           in terms of which input gets a chance to raise an
     2866           exception first).
     2867        */
     2868
     2869        datum = datanext(data);
     2870        if (datum == NULL)
     2871            return NULL;
     2872
     2873        selector = selectornext(selectors);
     2874        if (selector == NULL) {
     2875            Py_DECREF(datum);
     2876            return NULL;
     2877        }
     2878
     2879        ok = PyObject_IsTrue(selector);
     2880        Py_DECREF(selector);
     2881        if (ok == 1)
     2882            return datum;
     2883        Py_DECREF(datum);
     2884        if (ok == -1)
     2885            return NULL;
     2886    }
     2887}
     2888
     2889PyDoc_STRVAR(compress_doc,
     2890"compress(data, selectors) --> iterator over selected data\n\
     2891\n\
     2892Return data elements corresponding to true selector elements.\n\
     2893Forms a shorter iterator from selected data elements using the\n\
     2894selectors to choose the data elements.");
     2895
     2896static PyTypeObject compress_type = {
     2897    PyVarObject_HEAD_INIT(NULL, 0)
     2898    "itertools.compress",               /* tp_name */
     2899    sizeof(compressobject),             /* tp_basicsize */
     2900    0,                                                          /* tp_itemsize */
     2901    /* methods */
     2902    (destructor)compress_dealloc,       /* tp_dealloc */
     2903    0,                                                                  /* tp_print */
     2904    0,                                                                  /* tp_getattr */
     2905    0,                                                                  /* tp_setattr */
     2906    0,                                                                  /* tp_compare */
     2907    0,                                                                  /* tp_repr */
     2908    0,                                                                  /* tp_as_number */
     2909    0,                                                                  /* tp_as_sequence */
     2910    0,                                                                  /* tp_as_mapping */
     2911    0,                                                                  /* tp_hash */
     2912    0,                                                                  /* tp_call */
     2913    0,                                                                  /* tp_str */
     2914    PyObject_GenericGetAttr,                    /* tp_getattro */
     2915    0,                                                                  /* tp_setattro */
     2916    0,                                                                  /* tp_as_buffer */
     2917    Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC |
     2918        Py_TPFLAGS_BASETYPE,                    /* tp_flags */
     2919    compress_doc,                                       /* tp_doc */
     2920    (traverseproc)compress_traverse,            /* tp_traverse */
     2921    0,                                                                  /* tp_clear */
     2922    0,                                                                  /* tp_richcompare */
     2923    0,                                                                  /* tp_weaklistoffset */
     2924    PyObject_SelfIter,                                  /* tp_iter */
     2925    (iternextfunc)compress_next,        /* tp_iternext */
     2926    0,                                                                  /* tp_methods */
     2927    0,                                                                  /* tp_members */
     2928    0,                                                                  /* tp_getset */
     2929    0,                                                                  /* tp_base */
     2930    0,                                                                  /* tp_dict */
     2931    0,                                                                  /* tp_descr_get */
     2932    0,                                                                  /* tp_descr_set */
     2933    0,                                                                  /* tp_dictoffset */
     2934    0,                                                                  /* tp_init */
     2935    0,                                                                  /* tp_alloc */
     2936    compress_new,                                       /* tp_new */
     2937    PyObject_GC_Del,                                    /* tp_free */
     2938};
     2939
     2940
    25142941/* ifilter object ************************************************************/
    25152942
    25162943typedef struct {
    2517         PyObject_HEAD
    2518         PyObject *func;
    2519         PyObject *it;
     2944    PyObject_HEAD
     2945    PyObject *func;
     2946    PyObject *it;
    25202947} ifilterobject;
    25212948
     
    25252952ifilter_new(PyTypeObject *type, PyObject *args, PyObject *kwds)
    25262953{
    2527         PyObject *func, *seq;
    2528         PyObject *it;
    2529         ifilterobject *lz;
    2530 
    2531         if (type == &ifilter_type && !_PyArg_NoKeywords("ifilter()", kwds))
    2532                 return NULL;
    2533 
    2534         if (!PyArg_UnpackTuple(args, "ifilter", 2, 2, &func, &seq))
    2535                 return NULL;
    2536 
    2537         /* Get iterator. */
    2538         it = PyObject_GetIter(seq);
    2539         if (it == NULL)
    2540                 return NULL;
    2541 
    2542         /* create ifilterobject structure */
    2543         lz = (ifilterobject *)type->tp_alloc(type, 0);
    2544         if (lz == NULL) {
    2545                 Py_DECREF(it);
    2546                 return NULL;
    2547         }
    2548         Py_INCREF(func);
    2549         lz->func = func;
    2550         lz->it = it;
    2551 
    2552         return (PyObject *)lz;
     2954    PyObject *func, *seq;
     2955    PyObject *it;
     2956    ifilterobject *lz;
     2957
     2958    if (type == &ifilter_type && !_PyArg_NoKeywords("ifilter()", kwds))
     2959        return NULL;
     2960
     2961    if (!PyArg_UnpackTuple(args, "ifilter", 2, 2, &func, &seq))
     2962        return NULL;
     2963
     2964    /* Get iterator. */
     2965    it = PyObject_GetIter(seq);
     2966    if (it == NULL)
     2967        return NULL;
     2968
     2969    /* create ifilterobject structure */
     2970    lz = (ifilterobject *)type->tp_alloc(type, 0);
     2971    if (lz == NULL) {
     2972        Py_DECREF(it);
     2973        return NULL;
     2974    }
     2975    Py_INCREF(func);
     2976    lz->func = func;
     2977    lz->it = it;
     2978
     2979    return (PyObject *)lz;
    25532980}
    25542981
     
    25562983ifilter_dealloc(ifilterobject *lz)
    25572984{
    2558         PyObject_GC_UnTrack(lz);
    2559         Py_XDECREF(lz->func);
    2560         Py_XDECREF(lz->it);
    2561         Py_TYPE(lz)->tp_free(lz);
     2985    PyObject_GC_UnTrack(lz);
     2986    Py_XDECREF(lz->func);
     2987    Py_XDECREF(lz->it);
     2988    Py_TYPE(lz)->tp_free(lz);
    25622989}
    25632990
     
    25652992ifilter_traverse(ifilterobject *lz, visitproc visit, void *arg)
    25662993{
    2567         Py_VISIT(lz->it);
    2568         Py_VISIT(lz->func);
    2569         return 0;
     2994    Py_VISIT(lz->it);
     2995    Py_VISIT(lz->func);
     2996    return 0;
    25702997}
    25712998
     
    25733000ifilter_next(ifilterobject *lz)
    25743001{
    2575         PyObject *item;
    2576         PyObject *it = lz->it;
    2577         long ok;
    2578         PyObject *(*iternext)(PyObject *);
    2579 
    2580         assert(PyIter_Check(it));
    2581         iternext = *Py_TYPE(it)->tp_iternext;
    2582         for (;;) {
    2583                 item = iternext(it);
    2584                 if (item == NULL)
    2585                         return NULL;
    2586 
    2587                 if (lz->func == Py_None || lz->func == (PyObject *)&PyBool_Type) {
    2588                         ok = PyObject_IsTrue(item);
    2589                 } else {
    2590                         PyObject *good;
    2591                         good = PyObject_CallFunctionObjArgs(lz->func,
    2592                                                             item, NULL);
    2593                         if (good == NULL) {
    2594                                 Py_DECREF(item);
    2595                                 return NULL;
    2596                         }
    2597                         ok = PyObject_IsTrue(good);
    2598                         Py_DECREF(good);
    2599                 }
    2600                 if (ok)
    2601                         return item;
    2602                 Py_DECREF(item);
    2603         }
     3002    PyObject *item;
     3003    PyObject *it = lz->it;
     3004    long ok;
     3005    PyObject *(*iternext)(PyObject *);
     3006
     3007    iternext = *Py_TYPE(it)->tp_iternext;
     3008    for (;;) {
     3009        item = iternext(it);
     3010        if (item == NULL)
     3011            return NULL;
     3012
     3013        if (lz->func == Py_None || lz->func == (PyObject *)&PyBool_Type) {
     3014            ok = PyObject_IsTrue(item);
     3015        } else {
     3016            PyObject *good;
     3017            good = PyObject_CallFunctionObjArgs(lz->func,
     3018                                                item, NULL);
     3019            if (good == NULL) {
     3020                Py_DECREF(item);
     3021                return NULL;
     3022            }
     3023            ok = PyObject_IsTrue(good);
     3024            Py_DECREF(good);
     3025        }
     3026        if (ok > 0)
     3027            return item;
     3028        Py_DECREF(item);
     3029        if (ok < 0)
     3030            return NULL;
     3031    }
    26043032}
    26053033
     
    26113039
    26123040static PyTypeObject ifilter_type = {
    2613         PyVarObject_HEAD_INIT(NULL, 0)
    2614         "itertools.ifilter",            /* tp_name */
    2615         sizeof(ifilterobject),          /* tp_basicsize */
    2616         0,                              /* tp_itemsize */
    2617         /* methods */
    2618         (destructor)ifilter_dealloc,    /* tp_dealloc */
    2619         0,                              /* tp_print */
    2620         0,                              /* tp_getattr */
    2621         0,                              /* tp_setattr */
    2622         0,                              /* tp_compare */
    2623         0,                              /* tp_repr */
    2624         0,                              /* tp_as_number */
    2625         0,                              /* tp_as_sequence */
    2626         0,                              /* tp_as_mapping */
    2627         0,                              /* tp_hash */
    2628         0,                              /* tp_call */
    2629         0,                              /* tp_str */
    2630         PyObject_GenericGetAttr,        /* tp_getattro */
    2631         0,                              /* tp_setattro */
    2632         0,                              /* tp_as_buffer */
    2633         Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC |
    2634                 Py_TPFLAGS_BASETYPE,    /* tp_flags */
    2635         ifilter_doc,                    /* tp_doc */
    2636         (traverseproc)ifilter_traverse, /* tp_traverse */
    2637         0,                              /* tp_clear */
    2638         0,                              /* tp_richcompare */
    2639         0,                              /* tp_weaklistoffset */
    2640         PyObject_SelfIter,              /* tp_iter */
    2641         (iternextfunc)ifilter_next,     /* tp_iternext */
    2642         0,                              /* tp_methods */
    2643         0,                              /* tp_members */
    2644         0,                              /* tp_getset */
    2645         0,                              /* tp_base */
    2646         0,                              /* tp_dict */
    2647         0,                              /* tp_descr_get */
    2648         0,                              /* tp_descr_set */
    2649         0,                              /* tp_dictoffset */
    2650         0,                              /* tp_init */
    2651         0,                              /* tp_alloc */
    2652         ifilter_new,                    /* tp_new */
    2653         PyObject_GC_Del,                /* tp_free */
     3041    PyVarObject_HEAD_INIT(NULL, 0)
     3042    "itertools.ifilter",                /* tp_name */
     3043    sizeof(ifilterobject),              /* tp_basicsize */
     3044    0,                                  /* tp_itemsize */
     3045    /* methods */
     3046    (destructor)ifilter_dealloc,        /* tp_dealloc */
     3047    0,                                  /* tp_print */
     3048    0,                                  /* tp_getattr */
     3049    0,                                  /* tp_setattr */
     3050    0,                                  /* tp_compare */
     3051    0,                                  /* tp_repr */
     3052    0,                                  /* tp_as_number */
     3053    0,                                  /* tp_as_sequence */
     3054    0,                                  /* tp_as_mapping */
     3055    0,                                  /* tp_hash */
     3056    0,                                  /* tp_call */
     3057    0,                                  /* tp_str */
     3058    PyObject_GenericGetAttr,            /* tp_getattro */
     3059    0,                                  /* tp_setattro */
     3060    0,                                  /* tp_as_buffer */
     3061    Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC |
     3062        Py_TPFLAGS_BASETYPE,            /* tp_flags */
     3063    ifilter_doc,                        /* tp_doc */
     3064    (traverseproc)ifilter_traverse,     /* tp_traverse */
     3065    0,                                  /* tp_clear */
     3066    0,                                  /* tp_richcompare */
     3067    0,                                  /* tp_weaklistoffset */
     3068    PyObject_SelfIter,                  /* tp_iter */
     3069    (iternextfunc)ifilter_next,         /* tp_iternext */
     3070    0,                                  /* tp_methods */
     3071    0,                                  /* tp_members */
     3072    0,                                  /* tp_getset */
     3073    0,                                  /* tp_base */
     3074    0,                                  /* tp_dict */
     3075    0,                                  /* tp_descr_get */
     3076    0,                                  /* tp_descr_set */
     3077    0,                                  /* tp_dictoffset */
     3078    0,                                  /* tp_init */
     3079    0,                                  /* tp_alloc */
     3080    ifilter_new,                        /* tp_new */
     3081    PyObject_GC_Del,                    /* tp_free */
    26543082};
    26553083
     
    26583086
    26593087typedef struct {
    2660         PyObject_HEAD
    2661         PyObject *func;
    2662         PyObject *it;
     3088    PyObject_HEAD
     3089    PyObject *func;
     3090    PyObject *it;
    26633091} ifilterfalseobject;
    26643092
     
    26683096ifilterfalse_new(PyTypeObject *type, PyObject *args, PyObject *kwds)
    26693097{
    2670         PyObject *func, *seq;
    2671         PyObject *it;
    2672         ifilterfalseobject *lz;
    2673 
    2674         if (type == &ifilterfalse_type &&
    2675             !_PyArg_NoKeywords("ifilterfalse()", kwds))
    2676                 return NULL;
    2677 
    2678         if (!PyArg_UnpackTuple(args, "ifilterfalse", 2, 2, &func, &seq))
    2679                 return NULL;
    2680 
    2681         /* Get iterator. */
    2682         it = PyObject_GetIter(seq);
    2683         if (it == NULL)
    2684                 return NULL;
    2685 
    2686         /* create ifilterfalseobject structure */
    2687         lz = (ifilterfalseobject *)type->tp_alloc(type, 0);
    2688         if (lz == NULL) {
    2689                 Py_DECREF(it);
    2690                 return NULL;
    2691         }
    2692         Py_INCREF(func);
    2693         lz->func = func;
    2694         lz->it = it;
    2695 
    2696         return (PyObject *)lz;
     3098    PyObject *func, *seq;
     3099    PyObject *it;
     3100    ifilterfalseobject *lz;
     3101
     3102    if (type == &ifilterfalse_type &&
     3103        !_PyArg_NoKeywords("ifilterfalse()", kwds))
     3104        return NULL;
     3105
     3106    if (!PyArg_UnpackTuple(args, "ifilterfalse", 2, 2, &func, &seq))
     3107        return NULL;
     3108
     3109    /* Get iterator. */
     3110    it = PyObject_GetIter(seq);
     3111    if (it == NULL)
     3112        return NULL;
     3113
     3114    /* create ifilterfalseobject structure */
     3115    lz = (ifilterfalseobject *)type->tp_alloc(type, 0);
     3116    if (lz == NULL) {
     3117        Py_DECREF(it);
     3118        return NULL;
     3119    }
     3120    Py_INCREF(func);
     3121    lz->func = func;
     3122    lz->it = it;
     3123
     3124    return (PyObject *)lz;
    26973125}
    26983126
     
    27003128ifilterfalse_dealloc(ifilterfalseobject *lz)
    27013129{
    2702         PyObject_GC_UnTrack(lz);
    2703         Py_XDECREF(lz->func);
    2704         Py_XDECREF(lz->it);
    2705         Py_TYPE(lz)->tp_free(lz);
     3130    PyObject_GC_UnTrack(lz);
     3131    Py_XDECREF(lz->func);
     3132    Py_XDECREF(lz->it);
     3133    Py_TYPE(lz)->tp_free(lz);
    27063134}
    27073135
     
    27093137ifilterfalse_traverse(ifilterfalseobject *lz, visitproc visit, void *arg)
    27103138{
    2711         Py_VISIT(lz->it);
    2712         Py_VISIT(lz->func);
    2713         return 0;
     3139    Py_VISIT(lz->it);
     3140    Py_VISIT(lz->func);
     3141    return 0;
    27143142}
    27153143
     
    27173145ifilterfalse_next(ifilterfalseobject *lz)
    27183146{
    2719         PyObject *item;
    2720         PyObject *it = lz->it;
    2721         long ok;
    2722         PyObject *(*iternext)(PyObject *);
    2723 
    2724         assert(PyIter_Check(it));
    2725         iternext = *Py_TYPE(it)->tp_iternext;
    2726         for (;;) {
    2727                 item = iternext(it);
    2728                 if (item == NULL)
    2729                         return NULL;
    2730 
    2731                 if (lz->func == Py_None || lz->func == (PyObject *)&PyBool_Type) {
    2732                         ok = PyObject_IsTrue(item);
    2733                 } else {
    2734                         PyObject *good;
    2735                         good = PyObject_CallFunctionObjArgs(lz->func,
    2736                                                             item, NULL);
    2737                         if (good == NULL) {
    2738                                 Py_DECREF(item);
    2739                                 return NULL;
    2740                         }
    2741                         ok = PyObject_IsTrue(good);
    2742                         Py_DECREF(good);
    2743                 }
    2744                 if (!ok)
    2745                         return item;
    2746                 Py_DECREF(item);
    2747         }
     3147    PyObject *item;
     3148    PyObject *it = lz->it;
     3149    long ok;
     3150    PyObject *(*iternext)(PyObject *);
     3151
     3152    iternext = *Py_TYPE(it)->tp_iternext;
     3153    for (;;) {
     3154        item = iternext(it);
     3155        if (item == NULL)
     3156            return NULL;
     3157
     3158        if (lz->func == Py_None || lz->func == (PyObject *)&PyBool_Type) {
     3159            ok = PyObject_IsTrue(item);
     3160        } else {
     3161            PyObject *good;
     3162            good = PyObject_CallFunctionObjArgs(lz->func,
     3163                                                item, NULL);
     3164            if (good == NULL) {
     3165                Py_DECREF(item);
     3166                return NULL;
     3167            }
     3168            ok = PyObject_IsTrue(good);
     3169            Py_DECREF(good);
     3170        }
     3171        if (ok == 0)
     3172            return item;
     3173        Py_DECREF(item);
     3174        if (ok < 0)
     3175            return NULL;
     3176    }
    27483177}
    27493178
     
    27553184
    27563185static PyTypeObject ifilterfalse_type = {
    2757         PyVarObject_HEAD_INIT(NULL, 0)
    2758         "itertools.ifilterfalse",       /* tp_name */
    2759         sizeof(ifilterfalseobject),     /* tp_basicsize */
    2760         0,                              /* tp_itemsize */
    2761         /* methods */
    2762         (destructor)ifilterfalse_dealloc,       /* tp_dealloc */
    2763         0,                              /* tp_print */
    2764         0,                              /* tp_getattr */
    2765         0,                              /* tp_setattr */
    2766         0,                              /* tp_compare */
    2767         0,                              /* tp_repr */
    2768         0,                              /* tp_as_number */
    2769         0,                              /* tp_as_sequence */
    2770         0,                              /* tp_as_mapping */
    2771         0,                              /* tp_hash */
    2772         0,                              /* tp_call */
    2773         0,                              /* tp_str */
    2774         PyObject_GenericGetAttr,        /* tp_getattro */
    2775         0,                              /* tp_setattro */
    2776         0,                              /* tp_as_buffer */
    2777         Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC |
    2778                 Py_TPFLAGS_BASETYPE,    /* tp_flags */
    2779         ifilterfalse_doc,               /* tp_doc */
    2780         (traverseproc)ifilterfalse_traverse,    /* tp_traverse */
    2781         0,                              /* tp_clear */
    2782         0,                              /* tp_richcompare */
    2783         0,                              /* tp_weaklistoffset */
    2784         PyObject_SelfIter,              /* tp_iter */
    2785         (iternextfunc)ifilterfalse_next,        /* tp_iternext */
    2786         0,                              /* tp_methods */
    2787         0,                              /* tp_members */
    2788         0,                              /* tp_getset */
    2789         0,                              /* tp_base */
    2790         0,                              /* tp_dict */
    2791         0,                              /* tp_descr_get */
    2792         0,                              /* tp_descr_set */
    2793         0,                              /* tp_dictoffset */
    2794         0,                              /* tp_init */
    2795         0,                              /* tp_alloc */
    2796         ifilterfalse_new,               /* tp_new */
    2797         PyObject_GC_Del,                /* tp_free */
     3186    PyVarObject_HEAD_INIT(NULL, 0)
     3187    "itertools.ifilterfalse",           /* tp_name */
     3188    sizeof(ifilterfalseobject),         /* tp_basicsize */
     3189    0,                                  /* tp_itemsize */
     3190    /* methods */
     3191    (destructor)ifilterfalse_dealloc,           /* tp_dealloc */
     3192    0,                                  /* tp_print */
     3193    0,                                  /* tp_getattr */
     3194    0,                                  /* tp_setattr */
     3195    0,                                  /* tp_compare */
     3196    0,                                  /* tp_repr */
     3197    0,                                  /* tp_as_number */
     3198    0,                                  /* tp_as_sequence */
     3199    0,                                  /* tp_as_mapping */
     3200    0,                                  /* tp_hash */
     3201    0,                                  /* tp_call */
     3202    0,                                  /* tp_str */
     3203    PyObject_GenericGetAttr,            /* tp_getattro */
     3204    0,                                  /* tp_setattro */
     3205    0,                                  /* tp_as_buffer */
     3206    Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC |
     3207        Py_TPFLAGS_BASETYPE,            /* tp_flags */
     3208    ifilterfalse_doc,                   /* tp_doc */
     3209    (traverseproc)ifilterfalse_traverse,        /* tp_traverse */
     3210    0,                                  /* tp_clear */
     3211    0,                                  /* tp_richcompare */
     3212    0,                                  /* tp_weaklistoffset */
     3213    PyObject_SelfIter,                  /* tp_iter */
     3214    (iternextfunc)ifilterfalse_next,            /* tp_iternext */
     3215    0,                                  /* tp_methods */
     3216    0,                                  /* tp_members */
     3217    0,                                  /* tp_getset */
     3218    0,                                  /* tp_base */
     3219    0,                                  /* tp_dict */
     3220    0,                                  /* tp_descr_get */
     3221    0,                                  /* tp_descr_set */
     3222    0,                                  /* tp_dictoffset */
     3223    0,                                  /* tp_init */
     3224    0,                                  /* tp_alloc */
     3225    ifilterfalse_new,                   /* tp_new */
     3226    PyObject_GC_Del,                    /* tp_free */
    27983227};
    27993228
     
    28023231
    28033232typedef struct {
    2804         PyObject_HEAD
    2805         Py_ssize_t cnt;
    2806         PyObject *long_cnt;     /* Arbitrarily large count when cnt >= PY_SSIZE_T_MAX */
     3233    PyObject_HEAD
     3234    Py_ssize_t cnt;
     3235    PyObject *long_cnt;
     3236    PyObject *long_step;
    28073237} countobject;
    28083238
     3239/* Counting logic and invariants:
     3240
     3241fast_mode:  when cnt an integer < PY_SSIZE_T_MAX and no step is specified.
     3242
     3243    assert(cnt != PY_SSIZE_T_MAX && long_cnt == NULL && long_step==PyInt(1));
     3244    Advances with:  cnt += 1
     3245    When count hits Y_SSIZE_T_MAX, switch to slow_mode.
     3246
     3247slow_mode:  when cnt == PY_SSIZE_T_MAX, step is not int(1), or cnt is a float.
     3248
     3249    assert(cnt == PY_SSIZE_T_MAX && long_cnt != NULL && long_step != NULL);
     3250    All counting is done with python objects (no overflows or underflows).
     3251    Advances with:  long_cnt += long_step
     3252    Step may be zero -- effectively a slow version of repeat(cnt).
     3253    Either long_cnt or long_step may be a float, Fraction, or Decimal.
     3254*/
     3255
    28093256static PyTypeObject count_type;
    28103257
     
    28123259count_new(PyTypeObject *type, PyObject *args, PyObject *kwds)
    28133260{
    2814         countobject *lz;
    2815         Py_ssize_t cnt = 0;
    2816         PyObject *cnt_arg = NULL;
    2817         PyObject *long_cnt = NULL;
    2818 
    2819         if (type == &count_type && !_PyArg_NoKeywords("count()", kwds))
    2820                 return NULL;
    2821 
    2822         if (!PyArg_UnpackTuple(args, "count", 0, 1, &cnt_arg))
    2823                 return NULL;
    2824 
    2825         if (cnt_arg != NULL) {
    2826                 cnt = PyInt_AsSsize_t(cnt_arg);
    2827                 if (cnt == -1 && PyErr_Occurred()) {
    2828                         PyErr_Clear();
    2829                         if (!PyLong_Check(cnt_arg)) {
    2830                                 PyErr_SetString(PyExc_TypeError, "an integer is required");
    2831                                 return NULL;
    2832                         }
    2833                         long_cnt = cnt_arg;
    2834                         Py_INCREF(long_cnt);
    2835                         cnt = PY_SSIZE_T_MAX;
    2836                 }
    2837         }
    2838 
    2839         /* create countobject structure */
    2840         lz = (countobject *)PyObject_New(countobject, &count_type);
    2841         if (lz == NULL) {
    2842                 Py_XDECREF(long_cnt);
    2843                 return NULL;
    2844         }
    2845         lz->cnt = cnt;
    2846         lz->long_cnt = long_cnt;
    2847 
    2848         return (PyObject *)lz;
     3261    countobject *lz;
     3262    int slow_mode = 0;
     3263    Py_ssize_t cnt = 0;
     3264    PyObject *long_cnt = NULL;
     3265    PyObject *long_step = NULL;
     3266    static char *kwlist[] = {"start", "step", 0};
     3267
     3268    if (!PyArg_ParseTupleAndKeywords(args, kwds, "|OO:count",
     3269                    kwlist, &long_cnt, &long_step))
     3270        return NULL;
     3271
     3272    if ((long_cnt != NULL && !PyNumber_Check(long_cnt)) ||
     3273        (long_step != NULL && !PyNumber_Check(long_step))) {
     3274                    PyErr_SetString(PyExc_TypeError, "a number is required");
     3275                    return NULL;
     3276    }
     3277
     3278    if (long_cnt != NULL) {
     3279        cnt = PyInt_AsSsize_t(long_cnt);
     3280        if ((cnt == -1 && PyErr_Occurred()) || !PyInt_Check(long_cnt)) {
     3281            PyErr_Clear();
     3282            slow_mode = 1;
     3283        }
     3284        Py_INCREF(long_cnt);
     3285    } else {
     3286        cnt = 0;
     3287        long_cnt = PyInt_FromLong(0);
     3288    }
     3289
     3290    /* If not specified, step defaults to 1 */
     3291    if (long_step == NULL) {
     3292        long_step = PyInt_FromLong(1);
     3293        if (long_step == NULL) {
     3294            Py_DECREF(long_cnt);
     3295            return NULL;
     3296        }
     3297    } else
     3298        Py_INCREF(long_step);
     3299
     3300    assert(long_cnt != NULL && long_step != NULL);
     3301
     3302    /* Fast mode only works when the step is 1 */
     3303    if (!PyInt_Check(long_step) ||
     3304        PyInt_AS_LONG(long_step) != 1) {
     3305            slow_mode = 1;
     3306    }
     3307
     3308    if (slow_mode)
     3309        cnt = PY_SSIZE_T_MAX;
     3310    else
     3311        Py_CLEAR(long_cnt);
     3312
     3313    assert((cnt != PY_SSIZE_T_MAX && long_cnt == NULL && !slow_mode) ||
     3314           (cnt == PY_SSIZE_T_MAX && long_cnt != NULL && slow_mode));
     3315    assert(slow_mode ||
     3316           (PyInt_Check(long_step) && PyInt_AS_LONG(long_step) == 1));
     3317
     3318    /* create countobject structure */
     3319    lz = (countobject *)type->tp_alloc(type, 0);
     3320    if (lz == NULL) {
     3321        Py_XDECREF(long_cnt);
     3322        return NULL;
     3323    }
     3324    lz->cnt = cnt;
     3325    lz->long_cnt = long_cnt;
     3326    lz->long_step = long_step;
     3327
     3328    return (PyObject *)lz;
    28493329}
    28503330
     
    28523332count_dealloc(countobject *lz)
    28533333{
    2854         Py_XDECREF(lz->long_cnt);
    2855         PyObject_Del(lz);
     3334    PyObject_GC_UnTrack(lz);
     3335    Py_XDECREF(lz->long_cnt);
     3336    Py_XDECREF(lz->long_step);
     3337    Py_TYPE(lz)->tp_free(lz);
     3338}
     3339
     3340static int
     3341count_traverse(countobject *lz, visitproc visit, void *arg)
     3342{
     3343    Py_VISIT(lz->long_cnt);
     3344    Py_VISIT(lz->long_step);
     3345    return 0;
    28563346}
    28573347
     
    28593349count_nextlong(countobject *lz)
    28603350{
    2861         static PyObject *one = NULL;
    2862         PyObject *cnt;
    2863         PyObject *stepped_up;
    2864 
    2865         if (lz->long_cnt == NULL) {
    2866                 lz->long_cnt = PyInt_FromSsize_t(PY_SSIZE_T_MAX);
    2867                 if (lz->long_cnt == NULL)
    2868                         return NULL;
    2869         }
    2870         if (one == NULL) {
    2871                 one = PyInt_FromLong(1);
    2872                 if (one == NULL)
    2873                         return NULL;
    2874         }
    2875         cnt = lz->long_cnt;
    2876         assert(cnt != NULL);
    2877         stepped_up = PyNumber_Add(cnt, one);
    2878         if (stepped_up == NULL)
    2879                 return NULL;
    2880         lz->long_cnt = stepped_up;
    2881         return cnt;
     3351    PyObject *long_cnt;
     3352    PyObject *stepped_up;
     3353
     3354    long_cnt = lz->long_cnt;
     3355    if (long_cnt == NULL) {
     3356        /* Switch to slow_mode */
     3357        long_cnt = PyInt_FromSsize_t(PY_SSIZE_T_MAX);
     3358        if (long_cnt == NULL)
     3359            return NULL;
     3360    }
     3361    assert(lz->cnt == PY_SSIZE_T_MAX && long_cnt != NULL);
     3362
     3363    stepped_up = PyNumber_Add(long_cnt, lz->long_step);
     3364    if (stepped_up == NULL)
     3365        return NULL;
     3366    lz->long_cnt = stepped_up;
     3367    return long_cnt;
    28823368}
    28833369
     
    28853371count_next(countobject *lz)
    28863372{
    2887         if (lz->cnt == PY_SSIZE_T_MAX)
    2888                 return count_nextlong(lz);
    2889         return PyInt_FromSsize_t(lz->cnt++);
     3373    if (lz->cnt == PY_SSIZE_T_MAX)
     3374        return count_nextlong(lz);
     3375    return PyInt_FromSsize_t(lz->cnt++);
    28903376}
    28913377
     
    28933379count_repr(countobject *lz)
    28943380{
    2895         PyObject *cnt_repr;
    2896         PyObject *result;
    2897 
    2898         if (lz->cnt != PY_SSIZE_T_MAX)
    2899                 return PyString_FromFormat("count(%zd)", lz->cnt);
    2900 
    2901         cnt_repr = PyObject_Repr(lz->long_cnt);
    2902         if (cnt_repr == NULL)
    2903                 return NULL;
    2904         result = PyString_FromFormat("count(%s)", PyString_AS_STRING(cnt_repr));
    2905         Py_DECREF(cnt_repr);
    2906         return result;
     3381    PyObject *cnt_repr, *step_repr = NULL;
     3382    PyObject *result = NULL;
     3383
     3384    if (lz->cnt != PY_SSIZE_T_MAX)
     3385                return PyString_FromFormat("count(%zd)", lz->cnt);
     3386
     3387    cnt_repr = PyObject_Repr(lz->long_cnt);
     3388    if (cnt_repr == NULL)
     3389        return NULL;
     3390
     3391    if (PyInt_Check(lz->long_step) && PyInt_AS_LONG(lz->long_step) == 1) {
     3392                    /* Don't display step when it is an integer equal to 1 */
     3393            result = PyString_FromFormat("count(%s)",
     3394                                                                     PyString_AS_STRING(cnt_repr));
     3395    } else {
     3396        step_repr = PyObject_Repr(lz->long_step);
     3397        if (step_repr != NULL)
     3398            result = PyString_FromFormat("count(%s, %s)",
     3399                                                                    PyString_AS_STRING(cnt_repr),
     3400                                                                    PyString_AS_STRING(step_repr));
     3401    }
     3402    Py_DECREF(cnt_repr);
     3403    Py_XDECREF(step_repr);
     3404    return result;
    29073405}
    29083406
     
    29103408count_reduce(countobject *lz)
    29113409{
    2912         if (lz->cnt == PY_SSIZE_T_MAX)
    2913                 return Py_BuildValue("O(O)", Py_TYPE(lz), lz->long_cnt);
    2914         return Py_BuildValue("O(n)", Py_TYPE(lz), lz->cnt);
     3410    if (lz->cnt == PY_SSIZE_T_MAX)
     3411        return Py_BuildValue("O(OO)", Py_TYPE(lz), lz->long_cnt, lz->long_step);
     3412    return Py_BuildValue("O(n)", Py_TYPE(lz), lz->cnt);
    29153413}
    29163414
     
    29183416
    29193417static PyMethodDef count_methods[] = {
    2920         {"__reduce__",  (PyCFunction)count_reduce,      METH_NOARGS,
    2921         count_reduce_doc},
    2922         {NULL,          NULL}   /* sentinel */
     3418    {"__reduce__",      (PyCFunction)count_reduce,      METH_NOARGS,
     3419    count_reduce_doc},
     3420    {NULL,              NULL}   /* sentinel */
    29233421};
    29243422
    29253423PyDoc_STRVAR(count_doc,
    2926 "count([firstval]) --> count object\n\
     3424                         "count(start=0, step=1) --> count object\n\
    29273425\n\
    2928 Return a count object whose .next() method returns consecutive\n\
    2929 integers starting from zero or, if specified, from firstval.");
     3426Return a count object whose .next() method returns consecutive values.\n\
     3427Equivalent to:\n\n\
     3428    def count(firstval=0, step=1):\n\
     3429        x = firstval\n\
     3430        while 1:\n\
     3431            yield x\n\
     3432            x += step\n");
    29303433
    29313434static PyTypeObject count_type = {
    2932         PyVarObject_HEAD_INIT(NULL, 0)
    2933         "itertools.count",              /* tp_name */
    2934         sizeof(countobject),            /* tp_basicsize */
    2935         0,                              /* tp_itemsize */
    2936         /* methods */
    2937         (destructor)count_dealloc,      /* tp_dealloc */
    2938         0,                              /* tp_print */
    2939         0,                              /* tp_getattr */
    2940         0,                              /* tp_setattr */
    2941         0,                              /* tp_compare */
    2942         (reprfunc)count_repr,           /* tp_repr */
    2943         0,                              /* tp_as_number */
    2944         0,                              /* tp_as_sequence */
    2945         0,                              /* tp_as_mapping */
    2946         0,                              /* tp_hash */
    2947         0,                              /* tp_call */
    2948         0,                              /* tp_str */
    2949         PyObject_GenericGetAttr,        /* tp_getattro */
    2950         0,                              /* tp_setattro */
    2951         0,                              /* tp_as_buffer */
    2952         Py_TPFLAGS_DEFAULT,             /* tp_flags */
    2953         count_doc,                      /* tp_doc */
    2954         0,                              /* tp_traverse */
    2955         0,                              /* tp_clear */
    2956         0,                              /* tp_richcompare */
    2957         0,                              /* tp_weaklistoffset */
    2958         PyObject_SelfIter,              /* tp_iter */
    2959         (iternextfunc)count_next,       /* tp_iternext */
    2960         count_methods,                          /* tp_methods */
    2961         0,                              /* tp_members */
    2962         0,                              /* tp_getset */
    2963         0,                              /* tp_base */
    2964         0,                              /* tp_dict */
    2965         0,                              /* tp_descr_get */
    2966         0,                              /* tp_descr_set */
    2967         0,                              /* tp_dictoffset */
    2968         0,                              /* tp_init */
    2969         0,                              /* tp_alloc */
    2970         count_new,                      /* tp_new */
     3435    PyVarObject_HEAD_INIT(NULL, 0)
     3436    "itertools.count",                  /* tp_name */
     3437    sizeof(countobject),                /* tp_basicsize */
     3438    0,                                  /* tp_itemsize */
     3439    /* methods */
     3440    (destructor)count_dealloc,          /* tp_dealloc */
     3441    0,                                  /* tp_print */
     3442    0,                                  /* tp_getattr */
     3443    0,                                  /* tp_setattr */
     3444    0,                                  /* tp_compare */
     3445    (reprfunc)count_repr,               /* tp_repr */
     3446    0,                                  /* tp_as_number */
     3447    0,                                  /* tp_as_sequence */
     3448    0,                                  /* tp_as_mapping */
     3449    0,                                  /* tp_hash */
     3450    0,                                  /* tp_call */
     3451    0,                                  /* tp_str */
     3452    PyObject_GenericGetAttr,            /* tp_getattro */
     3453    0,                                  /* tp_setattro */
     3454    0,                                  /* tp_as_buffer */
     3455    Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC |
     3456        Py_TPFLAGS_BASETYPE,                    /* tp_flags */
     3457    count_doc,                          /* tp_doc */
     3458    (traverseproc)count_traverse,                               /* tp_traverse */
     3459    0,                                  /* tp_clear */
     3460    0,                                  /* tp_richcompare */
     3461    0,                                  /* tp_weaklistoffset */
     3462    PyObject_SelfIter,                  /* tp_iter */
     3463    (iternextfunc)count_next,           /* tp_iternext */
     3464    count_methods,                              /* tp_methods */
     3465    0,                                  /* tp_members */
     3466    0,                                  /* tp_getset */
     3467    0,                                  /* tp_base */
     3468    0,                                  /* tp_dict */
     3469    0,                                  /* tp_descr_get */
     3470    0,                                  /* tp_descr_set */
     3471    0,                                  /* tp_dictoffset */
     3472    0,                                  /* tp_init */
     3473    0,                                  /* tp_alloc */
     3474    count_new,                          /* tp_new */
     3475    PyObject_GC_Del,                    /* tp_free */
    29713476};
    29723477
     
    29773482
    29783483typedef struct {
    2979         PyObject_HEAD
    2980         Py_ssize_t      tuplesize;
    2981         PyObject *ittuple;              /* tuple of iterators */
    2982         PyObject *result;
     3484    PyObject_HEAD
     3485    Py_ssize_t          tuplesize;
     3486    PyObject *ittuple;                  /* tuple of iterators */
     3487    PyObject *result;
    29833488} izipobject;
    29843489
     
    29883493izip_new(PyTypeObject *type, PyObject *args, PyObject *kwds)
    29893494{
    2990         izipobject *lz;
    2991         Py_ssize_t i;
    2992         PyObject *ittuple;  /* tuple of iterators */
    2993         PyObject *result;
    2994         Py_ssize_t tuplesize = PySequence_Length(args);
    2995 
    2996         if (type == &izip_type && !_PyArg_NoKeywords("izip()", kwds))
    2997                 return NULL;
    2998 
    2999         /* args must be a tuple */
    3000         assert(PyTuple_Check(args));
    3001 
    3002         /* obtain iterators */
    3003         ittuple = PyTuple_New(tuplesize);
    3004         if (ittuple == NULL)
    3005                 return NULL;
    3006         for (i=0; i < tuplesize; ++i) {
    3007                 PyObject *item = PyTuple_GET_ITEM(args, i);
    3008                 PyObject *it = PyObject_GetIter(item);
    3009                 if (it == NULL) {
    3010                         if (PyErr_ExceptionMatches(PyExc_TypeError))
    3011                                 PyErr_Format(PyExc_TypeError,
    3012                                     "izip argument #%zd must support iteration",
    3013                                     i+1);
    3014                         Py_DECREF(ittuple);
    3015                         return NULL;
    3016                 }
    3017                 PyTuple_SET_ITEM(ittuple, i, it);
    3018         }
    3019 
    3020         /* create a result holder */
    3021         result = PyTuple_New(tuplesize);
    3022         if (result == NULL) {
    3023                 Py_DECREF(ittuple);
    3024                 return NULL;
    3025         }
    3026         for (i=0 ; i < tuplesize ; i++) {
    3027                 Py_INCREF(Py_None);
    3028                 PyTuple_SET_ITEM(result, i, Py_None);
    3029         }
    3030 
    3031         /* create izipobject structure */
    3032         lz = (izipobject *)type->tp_alloc(type, 0);
    3033         if (lz == NULL) {
    3034                 Py_DECREF(ittuple);
    3035                 Py_DECREF(result);
    3036                 return NULL;
    3037         }
    3038         lz->ittuple = ittuple;
    3039         lz->tuplesize = tuplesize;
    3040         lz->result = result;
    3041 
    3042         return (PyObject *)lz;
     3495    izipobject *lz;
     3496    Py_ssize_t i;
     3497    PyObject *ittuple;  /* tuple of iterators */
     3498    PyObject *result;
     3499    Py_ssize_t tuplesize = PySequence_Length(args);
     3500
     3501    if (type == &izip_type && !_PyArg_NoKeywords("izip()", kwds))
     3502        return NULL;
     3503
     3504    /* args must be a tuple */
     3505    assert(PyTuple_Check(args));
     3506
     3507    /* obtain iterators */
     3508    ittuple = PyTuple_New(tuplesize);
     3509    if (ittuple == NULL)
     3510        return NULL;
     3511    for (i=0; i < tuplesize; ++i) {
     3512        PyObject *item = PyTuple_GET_ITEM(args, i);
     3513        PyObject *it = PyObject_GetIter(item);
     3514        if (it == NULL) {
     3515            if (PyErr_ExceptionMatches(PyExc_TypeError))
     3516                PyErr_Format(PyExc_TypeError,
     3517                    "izip argument #%zd must support iteration",
     3518                    i+1);
     3519            Py_DECREF(ittuple);
     3520            return NULL;
     3521        }
     3522        PyTuple_SET_ITEM(ittuple, i, it);
     3523    }
     3524
     3525    /* create a result holder */
     3526    result = PyTuple_New(tuplesize);
     3527    if (result == NULL) {
     3528        Py_DECREF(ittuple);
     3529        return NULL;
     3530    }
     3531    for (i=0 ; i < tuplesize ; i++) {
     3532        Py_INCREF(Py_None);
     3533        PyTuple_SET_ITEM(result, i, Py_None);
     3534    }
     3535
     3536    /* create izipobject structure */
     3537    lz = (izipobject *)type->tp_alloc(type, 0);
     3538    if (lz == NULL) {
     3539        Py_DECREF(ittuple);
     3540        Py_DECREF(result);
     3541        return NULL;
     3542    }
     3543    lz->ittuple = ittuple;
     3544    lz->tuplesize = tuplesize;
     3545    lz->result = result;
     3546
     3547    return (PyObject *)lz;
    30433548}
    30443549
     
    30463551izip_dealloc(izipobject *lz)
    30473552{
    3048         PyObject_GC_UnTrack(lz);
    3049         Py_XDECREF(lz->ittuple);
    3050         Py_XDECREF(lz->result);
    3051         Py_TYPE(lz)->tp_free(lz);
     3553    PyObject_GC_UnTrack(lz);
     3554    Py_XDECREF(lz->ittuple);
     3555    Py_XDECREF(lz->result);
     3556    Py_TYPE(lz)->tp_free(lz);
    30523557}
    30533558
     
    30553560izip_traverse(izipobject *lz, visitproc visit, void *arg)
    30563561{
    3057         Py_VISIT(lz->ittuple);
    3058         Py_VISIT(lz->result);
    3059         return 0;
     3562    Py_VISIT(lz->ittuple);
     3563    Py_VISIT(lz->result);
     3564    return 0;
    30603565}
    30613566
     
    30633568izip_next(izipobject *lz)
    30643569{
    3065         Py_ssize_t i;
    3066         Py_ssize_t tuplesize = lz->tuplesize;
    3067         PyObject *result = lz->result;
    3068         PyObject *it;
    3069         PyObject *item;
    3070         PyObject *olditem;
    3071 
    3072         if (tuplesize == 0)
    3073                 return NULL;
    3074         if (Py_REFCNT(result) == 1) {
    3075                 Py_INCREF(result);
    3076                 for (i=0 ; i < tuplesize ; i++) {
    3077                         it = PyTuple_GET_ITEM(lz->ittuple, i);
    3078                         assert(PyIter_Check(it));
    3079                         item = (*Py_TYPE(it)->tp_iternext)(it);
    3080                         if (item == NULL) {
    3081                                 Py_DECREF(result);
    3082                                 return NULL;
    3083                         }
    3084                         olditem = PyTuple_GET_ITEM(result, i);
    3085                         PyTuple_SET_ITEM(result, i, item);
    3086                         Py_DECREF(olditem);
    3087                 }
    3088         } else {
    3089                 result = PyTuple_New(tuplesize);
    3090                 if (result == NULL)
    3091                         return NULL;
    3092                 for (i=0 ; i < tuplesize ; i++) {
    3093                         it = PyTuple_GET_ITEM(lz->ittuple, i);
    3094                         assert(PyIter_Check(it));
    3095                         item = (*Py_TYPE(it)->tp_iternext)(it);
    3096                         if (item == NULL) {
    3097                                 Py_DECREF(result);
    3098                                 return NULL;
    3099                         }
    3100                         PyTuple_SET_ITEM(result, i, item);
    3101                 }
    3102         }
    3103         return result;
     3570    Py_ssize_t i;
     3571    Py_ssize_t tuplesize = lz->tuplesize;
     3572    PyObject *result = lz->result;
     3573    PyObject *it;
     3574    PyObject *item;
     3575    PyObject *olditem;
     3576
     3577    if (tuplesize == 0)
     3578        return NULL;
     3579    if (Py_REFCNT(result) == 1) {
     3580        Py_INCREF(result);
     3581        for (i=0 ; i < tuplesize ; i++) {
     3582            it = PyTuple_GET_ITEM(lz->ittuple, i);
     3583            item = (*Py_TYPE(it)->tp_iternext)(it);
     3584            if (item == NULL) {
     3585                Py_DECREF(result);
     3586                return NULL;
     3587            }
     3588            olditem = PyTuple_GET_ITEM(result, i);
     3589            PyTuple_SET_ITEM(result, i, item);
     3590            Py_DECREF(olditem);
     3591        }
     3592    } else {
     3593        result = PyTuple_New(tuplesize);
     3594        if (result == NULL)
     3595            return NULL;
     3596        for (i=0 ; i < tuplesize ; i++) {
     3597            it = PyTuple_GET_ITEM(lz->ittuple, i);
     3598            item = (*Py_TYPE(it)->tp_iternext)(it);
     3599            if (item == NULL) {
     3600                Py_DECREF(result);
     3601                return NULL;
     3602            }
     3603            PyTuple_SET_ITEM(result, i, item);
     3604        }
     3605    }
     3606    return result;
    31043607}
    31053608
     
    31153618
    31163619static PyTypeObject izip_type = {
    3117         PyVarObject_HEAD_INIT(NULL, 0)
    3118         "itertools.izip",               /* tp_name */
    3119         sizeof(izipobject),             /* tp_basicsize */
    3120         0,                              /* tp_itemsize */
    3121         /* methods */
    3122         (destructor)izip_dealloc,       /* tp_dealloc */
    3123         0,                              /* tp_print */
    3124         0,                              /* tp_getattr */
    3125         0,                              /* tp_setattr */
    3126         0,                              /* tp_compare */
    3127         0,                              /* tp_repr */
    3128         0,                              /* tp_as_number */
    3129         0,                              /* tp_as_sequence */
    3130         0,                              /* tp_as_mapping */
    3131         0,                              /* tp_hash */
    3132         0,                              /* tp_call */
    3133         0,                              /* tp_str */
    3134         PyObject_GenericGetAttr,        /* tp_getattro */
    3135         0,                              /* tp_setattro */
    3136         0,                              /* tp_as_buffer */
    3137         Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC |
    3138                 Py_TPFLAGS_BASETYPE,    /* tp_flags */
    3139         izip_doc,                       /* tp_doc */
    3140         (traverseproc)izip_traverse,    /* tp_traverse */
    3141         0,                              /* tp_clear */
    3142         0,                              /* tp_richcompare */
    3143         0,                              /* tp_weaklistoffset */
    3144         PyObject_SelfIter,              /* tp_iter */
    3145         (iternextfunc)izip_next,        /* tp_iternext */
    3146         0,                              /* tp_methods */
    3147         0,                              /* tp_members */
    3148         0,                              /* tp_getset */
    3149         0,                              /* tp_base */
    3150         0,                              /* tp_dict */
    3151         0,                              /* tp_descr_get */
    3152         0,                              /* tp_descr_set */
    3153         0,                              /* tp_dictoffset */
    3154         0,                              /* tp_init */
    3155         0,                              /* tp_alloc */
    3156         izip_new,                       /* tp_new */
    3157         PyObject_GC_Del,                /* tp_free */
     3620    PyVarObject_HEAD_INIT(NULL, 0)
     3621    "itertools.izip",                   /* tp_name */
     3622    sizeof(izipobject),                 /* tp_basicsize */
     3623    0,                                  /* tp_itemsize */
     3624    /* methods */
     3625    (destructor)izip_dealloc,           /* tp_dealloc */
     3626    0,                                  /* tp_print */
     3627    0,                                  /* tp_getattr */
     3628    0,                                  /* tp_setattr */
     3629    0,                                  /* tp_compare */
     3630    0,                                  /* tp_repr */
     3631    0,                                  /* tp_as_number */
     3632    0,                                  /* tp_as_sequence */
     3633    0,                                  /* tp_as_mapping */
     3634    0,                                  /* tp_hash */
     3635    0,                                  /* tp_call */
     3636    0,                                  /* tp_str */
     3637    PyObject_GenericGetAttr,            /* tp_getattro */
     3638    0,                                  /* tp_setattro */
     3639    0,                                  /* tp_as_buffer */
     3640    Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC |
     3641        Py_TPFLAGS_BASETYPE,            /* tp_flags */
     3642    izip_doc,                           /* tp_doc */
     3643    (traverseproc)izip_traverse,    /* tp_traverse */
     3644    0,                                  /* tp_clear */
     3645    0,                                  /* tp_richcompare */
     3646    0,                                  /* tp_weaklistoffset */
     3647    PyObject_SelfIter,                  /* tp_iter */
     3648    (iternextfunc)izip_next,            /* tp_iternext */
     3649    0,                                  /* tp_methods */
     3650    0,                                  /* tp_members */
     3651    0,                                  /* tp_getset */
     3652    0,                                  /* tp_base */
     3653    0,                                  /* tp_dict */
     3654    0,                                  /* tp_descr_get */
     3655    0,                                  /* tp_descr_set */
     3656    0,                                  /* tp_dictoffset */
     3657    0,                                  /* tp_init */
     3658    0,                                  /* tp_alloc */
     3659    izip_new,                           /* tp_new */
     3660    PyObject_GC_Del,                    /* tp_free */
    31583661};
    31593662
     
    31623665
    31633666typedef struct {
    3164         PyObject_HEAD
    3165         PyObject *element;
    3166         Py_ssize_t cnt;
     3667    PyObject_HEAD
     3668    PyObject *element;
     3669    Py_ssize_t cnt;
    31673670} repeatobject;
    31683671
     
    31723675repeat_new(PyTypeObject *type, PyObject *args, PyObject *kwds)
    31733676{
    3174         repeatobject *ro;
    3175         PyObject *element;
    3176         Py_ssize_t cnt = -1;
    3177 
    3178         if (type == &repeat_type && !_PyArg_NoKeywords("repeat()", kwds))
    3179                 return NULL;
    3180 
    3181         if (!PyArg_ParseTuple(args, "O|n:repeat", &element, &cnt))
    3182                 return NULL;
    3183 
    3184         if (PyTuple_Size(args) == 2 && cnt < 0)
    3185                 cnt = 0;
    3186 
    3187         ro = (repeatobject *)type->tp_alloc(type, 0);
    3188         if (ro == NULL)
    3189                 return NULL;
    3190         Py_INCREF(element);
    3191         ro->element = element;
    3192         ro->cnt = cnt;
    3193         return (PyObject *)ro;
     3677    repeatobject *ro;
     3678    PyObject *element;
     3679    Py_ssize_t cnt = -1;
     3680    static char *kwargs[] = {"object", "times", NULL};
     3681
     3682    if (!PyArg_ParseTupleAndKeywords(args, kwds, "O|n:repeat", kwargs,
     3683                                     &element, &cnt))
     3684        return NULL;
     3685
     3686    if (PyTuple_Size(args) == 2 && cnt < 0)
     3687        cnt = 0;
     3688
     3689    ro = (repeatobject *)type->tp_alloc(type, 0);
     3690    if (ro == NULL)
     3691        return NULL;
     3692    Py_INCREF(element);
     3693    ro->element = element;
     3694    ro->cnt = cnt;
     3695    return (PyObject *)ro;
    31943696}
    31953697
     
    31973699repeat_dealloc(repeatobject *ro)
    31983700{
    3199         PyObject_GC_UnTrack(ro);
    3200         Py_XDECREF(ro->element);
    3201         Py_TYPE(ro)->tp_free(ro);
     3701    PyObject_GC_UnTrack(ro);
     3702    Py_XDECREF(ro->element);
     3703    Py_TYPE(ro)->tp_free(ro);
    32023704}
    32033705
     
    32053707repeat_traverse(repeatobject *ro, visitproc visit, void *arg)
    32063708{
    3207         Py_VISIT(ro->element);
    3208         return 0;
     3709    Py_VISIT(ro->element);
     3710    return 0;
    32093711}
    32103712
     
    32123714repeat_next(repeatobject *ro)
    32133715{
    3214         if (ro->cnt == 0)
    3215                 return NULL;
    3216         if (ro->cnt > 0)
    3217                 ro->cnt--;
    3218         Py_INCREF(ro->element);
    3219         return ro->element;
     3716    if (ro->cnt == 0)
     3717        return NULL;
     3718    if (ro->cnt > 0)
     3719        ro->cnt--;
     3720    Py_INCREF(ro->element);
     3721    return ro->element;
    32203722}
    32213723
     
    32233725repeat_repr(repeatobject *ro)
    32243726{
    3225         PyObject *result, *objrepr;
    3226 
    3227         objrepr = PyObject_Repr(ro->element);
    3228         if (objrepr == NULL)
    3229                 return NULL;
    3230 
    3231         if (ro->cnt == -1)
    3232                 result = PyString_FromFormat("repeat(%s)",
    3233                         PyString_AS_STRING(objrepr));
    3234         else
    3235                 result = PyString_FromFormat("repeat(%s, %zd)",
    3236                         PyString_AS_STRING(objrepr), ro->cnt);
    3237         Py_DECREF(objrepr);
    3238         return result;
    3239 }       
     3727    PyObject *result, *objrepr;
     3728
     3729    objrepr = PyObject_Repr(ro->element);
     3730    if (objrepr == NULL)
     3731        return NULL;
     3732
     3733    if (ro->cnt == -1)
     3734        result = PyString_FromFormat("repeat(%s)",
     3735            PyString_AS_STRING(objrepr));
     3736    else
     3737        result = PyString_FromFormat("repeat(%s, %zd)",
     3738            PyString_AS_STRING(objrepr), ro->cnt);
     3739    Py_DECREF(objrepr);
     3740    return result;
     3741}
    32403742
    32413743static PyObject *
    32423744repeat_len(repeatobject *ro)
    32433745{
    3244         if (ro->cnt == -1) {
    3245                 PyErr_SetString(PyExc_TypeError, "len() of unsized object");
    3246                 return NULL;
    3247         }
    3248         return PyInt_FromSize_t(ro->cnt);
     3746    if (ro->cnt == -1) {
     3747        PyErr_SetString(PyExc_TypeError, "len() of unsized object");
     3748        return NULL;
     3749    }
     3750    return PyInt_FromSize_t(ro->cnt);
    32493751}
    32503752
     
    32523754
    32533755static PyMethodDef repeat_methods[] = {
    3254         {"__length_hint__", (PyCFunction)repeat_len, METH_NOARGS, length_hint_doc},
    3255         {NULL,          NULL}           /* sentinel */
     3756    {"__length_hint__", (PyCFunction)repeat_len, METH_NOARGS, length_hint_doc},
     3757    {NULL,              NULL}           /* sentinel */
    32563758};
    32573759
    32583760PyDoc_STRVAR(repeat_doc,
    3259 "repeat(element [,times]) -> create an iterator which returns the element\n\
    3260 for the specified number of times.  If not specified, returns the element\n\
     3761"repeat(object [,times]) -> create an iterator which returns the object\n\
     3762for the specified number of times.  If not specified, returns the object\n\
    32613763endlessly.");
    32623764
    32633765static PyTypeObject repeat_type = {
    3264         PyVarObject_HEAD_INIT(NULL, 0)
    3265         "itertools.repeat",             /* tp_name */
    3266         sizeof(repeatobject),           /* tp_basicsize */
    3267         0,                              /* tp_itemsize */
    3268         /* methods */
    3269         (destructor)repeat_dealloc,     /* tp_dealloc */
    3270         0,                              /* tp_print */
    3271         0,                              /* tp_getattr */
    3272         0,                              /* tp_setattr */
    3273         0,                              /* tp_compare */
    3274         (reprfunc)repeat_repr,          /* tp_repr */
    3275         0,                              /* tp_as_number */
    3276         0,                              /* tp_as_sequence */
    3277         0,                              /* tp_as_mapping */
    3278         0,                              /* tp_hash */
    3279         0,                              /* tp_call */
    3280         0,                              /* tp_str */
    3281         PyObject_GenericGetAttr,        /* tp_getattro */
    3282         0,                              /* tp_setattro */
    3283         0,                              /* tp_as_buffer */
    3284         Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC |
    3285                 Py_TPFLAGS_BASETYPE,    /* tp_flags */
    3286         repeat_doc,                     /* tp_doc */
    3287         (traverseproc)repeat_traverse,  /* tp_traverse */
    3288         0,                              /* tp_clear */
    3289         0,                              /* tp_richcompare */
    3290         0,                              /* tp_weaklistoffset */
    3291         PyObject_SelfIter,              /* tp_iter */
    3292         (iternextfunc)repeat_next,      /* tp_iternext */
    3293         repeat_methods,                 /* tp_methods */
    3294         0,                              /* tp_members */
    3295         0,                              /* tp_getset */
    3296         0,                              /* tp_base */
    3297         0,                              /* tp_dict */
    3298         0,                              /* tp_descr_get */
    3299         0,                              /* tp_descr_set */
    3300         0,                              /* tp_dictoffset */
    3301         0,                              /* tp_init */
    3302         0,                              /* tp_alloc */
    3303         repeat_new,                     /* tp_new */
    3304         PyObject_GC_Del,                /* tp_free */
     3766    PyVarObject_HEAD_INIT(NULL, 0)
     3767    "itertools.repeat",                 /* tp_name */
     3768    sizeof(repeatobject),               /* tp_basicsize */
     3769    0,                                  /* tp_itemsize */
     3770    /* methods */
     3771    (destructor)repeat_dealloc,         /* tp_dealloc */
     3772    0,                                  /* tp_print */
     3773    0,                                  /* tp_getattr */
     3774    0,                                  /* tp_setattr */
     3775    0,                                  /* tp_compare */
     3776    (reprfunc)repeat_repr,              /* tp_repr */
     3777    0,                                  /* tp_as_number */
     3778    0,                                  /* tp_as_sequence */
     3779    0,                                  /* tp_as_mapping */
     3780    0,                                  /* tp_hash */
     3781    0,                                  /* tp_call */
     3782    0,                                  /* tp_str */
     3783    PyObject_GenericGetAttr,            /* tp_getattro */
     3784    0,                                  /* tp_setattro */
     3785    0,                                  /* tp_as_buffer */
     3786    Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC |
     3787        Py_TPFLAGS_BASETYPE,            /* tp_flags */
     3788    repeat_doc,                         /* tp_doc */
     3789    (traverseproc)repeat_traverse,      /* tp_traverse */
     3790    0,                                  /* tp_clear */
     3791    0,                                  /* tp_richcompare */
     3792    0,                                  /* tp_weaklistoffset */
     3793    PyObject_SelfIter,                  /* tp_iter */
     3794    (iternextfunc)repeat_next,          /* tp_iternext */
     3795    repeat_methods,                     /* tp_methods */
     3796    0,                                  /* tp_members */
     3797    0,                                  /* tp_getset */
     3798    0,                                  /* tp_base */
     3799    0,                                  /* tp_dict */
     3800    0,                                  /* tp_descr_get */
     3801    0,                                  /* tp_descr_set */
     3802    0,                                  /* tp_dictoffset */
     3803    0,                                  /* tp_init */
     3804    0,                                  /* tp_alloc */
     3805    repeat_new,                         /* tp_new */
     3806    PyObject_GC_Del,                    /* tp_free */
    33053807};
    33063808
     
    33103812
    33113813typedef struct {
    3312         PyObject_HEAD
    3313         Py_ssize_t tuplesize;
    3314         Py_ssize_t numactive;   
    3315         PyObject *ittuple;              /* tuple of iterators */
    3316         PyObject *result;
    3317         PyObject *fillvalue;
     3814    PyObject_HEAD
     3815    Py_ssize_t tuplesize;
     3816    Py_ssize_t numactive;
     3817    PyObject *ittuple;                  /* tuple of iterators */
     3818    PyObject *result;
     3819    PyObject *fillvalue;
    33183820} iziplongestobject;
    33193821
     
    33233825izip_longest_new(PyTypeObject *type, PyObject *args, PyObject *kwds)
    33243826{
    3325         iziplongestobject *lz;
    3326         Py_ssize_t i;
    3327         PyObject *ittuple;  /* tuple of iterators */
    3328         PyObject *result;
    3329         PyObject *fillvalue = Py_None;
    3330         Py_ssize_t tuplesize = PySequence_Length(args);
    3331 
    3332         if (kwds != NULL && PyDict_CheckExact(kwds) && PyDict_Size(kwds) > 0) {
    3333                 fillvalue = PyDict_GetItemString(kwds, "fillvalue");
    3334                 if (fillvalue == NULL  ||  PyDict_Size(kwds) > 1) {
    3335                         PyErr_SetString(PyExc_TypeError,
    3336                                 "izip_longest() got an unexpected keyword argument");
    3337                         return NULL;                     
    3338                 }
     3827    iziplongestobject *lz;
     3828    Py_ssize_t i;
     3829    PyObject *ittuple;  /* tuple of iterators */
     3830    PyObject *result;
     3831    PyObject *fillvalue = Py_None;
     3832    Py_ssize_t tuplesize = PySequence_Length(args);
     3833
     3834    if (kwds != NULL && PyDict_CheckExact(kwds) && PyDict_Size(kwds) > 0) {
     3835        fillvalue = PyDict_GetItemString(kwds, "fillvalue");
     3836        if (fillvalue == NULL  ||  PyDict_Size(kwds) > 1) {
     3837            PyErr_SetString(PyExc_TypeError,
     3838                "izip_longest() got an unexpected keyword argument");
     3839            return NULL;
    33393840        }
    3340 
    3341         /* args must be a tuple */
    3342         assert(PyTuple_Check(args));
    3343 
    3344         /* obtain iterators */
    3345         ittuple = PyTuple_New(tuplesize);
    3346         if (ittuple == NULL)
    3347                 return NULL;
    3348         for (i=0; i < tuplesize; ++i) {
    3349                 PyObject *item = PyTuple_GET_ITEM(args, i);
    3350                 PyObject *it = PyObject_GetIter(item);
    3351                 if (it == NULL) {
    3352                         if (PyErr_ExceptionMatches(PyExc_TypeError))
    3353                                 PyErr_Format(PyExc_TypeError,
    3354                                     "izip_longest argument #%zd must support iteration",
    3355                                     i+1);
    3356                         Py_DECREF(ittuple);
    3357                         return NULL;
    3358                 }
    3359                 PyTuple_SET_ITEM(ittuple, i, it);
    3360         }
    3361 
    3362         /* create a result holder */
    3363         result = PyTuple_New(tuplesize);
    3364         if (result == NULL) {
    3365                 Py_DECREF(ittuple);
    3366                 return NULL;
    3367         }
    3368         for (i=0 ; i < tuplesize ; i++) {
    3369                 Py_INCREF(Py_None);
    3370                 PyTuple_SET_ITEM(result, i, Py_None);
    3371         }
    3372 
    3373         /* create iziplongestobject structure */
    3374         lz = (iziplongestobject *)type->tp_alloc(type, 0);
    3375         if (lz == NULL) {
    3376                 Py_DECREF(ittuple);
    3377                 Py_DECREF(result);
    3378                 return NULL;
    3379         }
    3380         lz->ittuple = ittuple;
    3381         lz->tuplesize = tuplesize;
    3382         lz->numactive = tuplesize;
    3383         lz->result = result;
    3384         Py_INCREF(fillvalue);
    3385         lz->fillvalue = fillvalue;
    3386         return (PyObject *)lz;
     3841    }
     3842
     3843    /* args must be a tuple */
     3844    assert(PyTuple_Check(args));
     3845
     3846    /* obtain iterators */
     3847    ittuple = PyTuple_New(tuplesize);
     3848    if (ittuple == NULL)
     3849        return NULL;
     3850    for (i=0; i < tuplesize; ++i) {
     3851        PyObject *item = PyTuple_GET_ITEM(args, i);
     3852        PyObject *it = PyObject_GetIter(item);
     3853        if (it == NULL) {
     3854            if (PyErr_ExceptionMatches(PyExc_TypeError))
     3855                PyErr_Format(PyExc_TypeError,
     3856                    "izip_longest argument #%zd must support iteration",
     3857                    i+1);
     3858            Py_DECREF(ittuple);
     3859            return NULL;
     3860        }
     3861        PyTuple_SET_ITEM(ittuple, i, it);
     3862    }
     3863
     3864    /* create a result holder */
     3865    result = PyTuple_New(tuplesize);
     3866    if (result == NULL) {
     3867        Py_DECREF(ittuple);
     3868        return NULL;
     3869    }
     3870    for (i=0 ; i < tuplesize ; i++) {
     3871        Py_INCREF(Py_None);
     3872        PyTuple_SET_ITEM(result, i, Py_None);
     3873    }
     3874
     3875    /* create iziplongestobject structure */
     3876    lz = (iziplongestobject *)type->tp_alloc(type, 0);
     3877    if (lz == NULL) {
     3878        Py_DECREF(ittuple);
     3879        Py_DECREF(result);
     3880        return NULL;
     3881    }
     3882    lz->ittuple = ittuple;
     3883    lz->tuplesize = tuplesize;
     3884    lz->numactive = tuplesize;
     3885    lz->result = result;
     3886    Py_INCREF(fillvalue);
     3887    lz->fillvalue = fillvalue;
     3888    return (PyObject *)lz;
    33873889}
    33883890
     
    33903892izip_longest_dealloc(iziplongestobject *lz)
    33913893{
    3392         PyObject_GC_UnTrack(lz);
    3393         Py_XDECREF(lz->ittuple);
    3394         Py_XDECREF(lz->result);
    3395         Py_XDECREF(lz->fillvalue);
    3396         Py_TYPE(lz)->tp_free(lz);
     3894    PyObject_GC_UnTrack(lz);
     3895    Py_XDECREF(lz->ittuple);
     3896    Py_XDECREF(lz->result);
     3897    Py_XDECREF(lz->fillvalue);
     3898    Py_TYPE(lz)->tp_free(lz);
    33973899}
    33983900
     
    34003902izip_longest_traverse(iziplongestobject *lz, visitproc visit, void *arg)
    34013903{
    3402         Py_VISIT(lz->ittuple);
    3403         Py_VISIT(lz->result);
    3404         Py_VISIT(lz->fillvalue);
    3405         return 0;
     3904    Py_VISIT(lz->ittuple);
     3905    Py_VISIT(lz->result);
     3906    Py_VISIT(lz->fillvalue);
     3907    return 0;
    34063908}
    34073909
     
    34093911izip_longest_next(iziplongestobject *lz)
    34103912{
    3411         Py_ssize_t i;
    3412         Py_ssize_t tuplesize = lz->tuplesize;
    3413         PyObject *result = lz->result;
    3414         PyObject *it;
    3415         PyObject *item;
    3416         PyObject *olditem;
    3417 
    3418         if (tuplesize == 0)
    3419                 return NULL;
    3420         if (lz->numactive == 0)
    3421                 return NULL;
    3422         if (Py_REFCNT(result) == 1) {
    3423                 Py_INCREF(result);
    3424                 for (i=0 ; i < tuplesize ; i++) {
    3425                         it = PyTuple_GET_ITEM(lz->ittuple, i);
    3426                         if (it == NULL) {
    3427                                 Py_INCREF(lz->fillvalue);
    3428                                 item = lz->fillvalue;
    3429                         } else {
    3430                                 assert(PyIter_Check(it));
    3431                                 item = PyIter_Next(it);
    3432                                 if (item == NULL) {
    3433                                         lz->numactive -= 1;
    3434                                         if (lz->numactive == 0 || PyErr_Occurred()) {
    3435                                                 lz->numactive = 0;
    3436                                                 Py_DECREF(result);
    3437                                                 return NULL;
    3438                                         } else {
    3439                                                 Py_INCREF(lz->fillvalue);
    3440                                                 item = lz->fillvalue;                                       
    3441                                                 PyTuple_SET_ITEM(lz->ittuple, i, NULL);
    3442                                                 Py_DECREF(it);
    3443                                         }
    3444                                 }
    3445                         }
    3446                         olditem = PyTuple_GET_ITEM(result, i);
    3447                         PyTuple_SET_ITEM(result, i, item);
    3448                         Py_DECREF(olditem);
     3913    Py_ssize_t i;
     3914    Py_ssize_t tuplesize = lz->tuplesize;
     3915    PyObject *result = lz->result;
     3916    PyObject *it;
     3917    PyObject *item;
     3918    PyObject *olditem;
     3919
     3920    if (tuplesize == 0)
     3921        return NULL;
     3922    if (lz->numactive == 0)
     3923        return NULL;
     3924    if (Py_REFCNT(result) == 1) {
     3925        Py_INCREF(result);
     3926        for (i=0 ; i < tuplesize ; i++) {
     3927            it = PyTuple_GET_ITEM(lz->ittuple, i);
     3928            if (it == NULL) {
     3929                Py_INCREF(lz->fillvalue);
     3930                item = lz->fillvalue;
     3931            } else {
     3932                item = PyIter_Next(it);
     3933                if (item == NULL) {
     3934                    lz->numactive -= 1;
     3935                    if (lz->numactive == 0 || PyErr_Occurred()) {
     3936                        lz->numactive = 0;
     3937                        Py_DECREF(result);
     3938                        return NULL;
     3939                    } else {
     3940                        Py_INCREF(lz->fillvalue);
     3941                        item = lz->fillvalue;
     3942                        PyTuple_SET_ITEM(lz->ittuple, i, NULL);
     3943                        Py_DECREF(it);
     3944                    }
    34493945                }
    3450         } else {
    3451                 result = PyTuple_New(tuplesize);
    3452                 if (result == NULL)
     3946            }
     3947            olditem = PyTuple_GET_ITEM(result, i);
     3948            PyTuple_SET_ITEM(result, i, item);
     3949            Py_DECREF(olditem);
     3950        }
     3951    } else {
     3952        result = PyTuple_New(tuplesize);
     3953        if (result == NULL)
     3954            return NULL;
     3955        for (i=0 ; i < tuplesize ; i++) {
     3956            it = PyTuple_GET_ITEM(lz->ittuple, i);
     3957            if (it == NULL) {
     3958                Py_INCREF(lz->fillvalue);
     3959                item = lz->fillvalue;
     3960            } else {
     3961                item = PyIter_Next(it);
     3962                if (item == NULL) {
     3963                    lz->numactive -= 1;
     3964                    if (lz->numactive == 0 || PyErr_Occurred()) {
     3965                        lz->numactive = 0;
     3966                        Py_DECREF(result);
    34533967                        return NULL;
    3454                 for (i=0 ; i < tuplesize ; i++) {
    3455                         it = PyTuple_GET_ITEM(lz->ittuple, i);
    3456                         if (it == NULL) {
    3457                                 Py_INCREF(lz->fillvalue);
    3458                                 item = lz->fillvalue;
    3459                         } else {
    3460                                 assert(PyIter_Check(it));
    3461                                 item = PyIter_Next(it);
    3462                                 if (item == NULL) {
    3463                                         lz->numactive -= 1;
    3464                                         if (lz->numactive == 0 || PyErr_Occurred()) {
    3465                                                 lz->numactive = 0;
    3466                                                 Py_DECREF(result);
    3467                                                 return NULL;
    3468                                         } else {
    3469                                                 Py_INCREF(lz->fillvalue);
    3470                                                 item = lz->fillvalue;                                       
    3471                                                 PyTuple_SET_ITEM(lz->ittuple, i, NULL);
    3472                                                 Py_DECREF(it);
    3473                                         }
    3474                                 }
    3475                         }
    3476                         PyTuple_SET_ITEM(result, i, item);
     3968                    } else {
     3969                        Py_INCREF(lz->fillvalue);
     3970                        item = lz->fillvalue;
     3971                        PyTuple_SET_ITEM(lz->ittuple, i, NULL);
     3972                        Py_DECREF(it);
     3973                    }
    34773974                }
     3975            }
     3976            PyTuple_SET_ITEM(result, i, item);
    34783977        }
    3479         return result;
     3978    }
     3979    return result;
    34803980}
    34813981
     
    34923992
    34933993static PyTypeObject iziplongest_type = {
    3494         PyVarObject_HEAD_INIT(NULL, 0)
    3495         "itertools.izip_longest",       /* tp_name */
    3496         sizeof(iziplongestobject),      /* tp_basicsize */
    3497         0,                              /* tp_itemsize */
    3498         /* methods */
    3499         (destructor)izip_longest_dealloc,       /* tp_dealloc */
    3500         0,                              /* tp_print */
    3501         0,                              /* tp_getattr */
    3502         0,                              /* tp_setattr */
    3503         0,                              /* tp_compare */
    3504         0,                              /* tp_repr */
    3505         0,                              /* tp_as_number */
    3506         0,                              /* tp_as_sequence */
    3507         0,                              /* tp_as_mapping */
    3508         0,                              /* tp_hash */
    3509         0,                              /* tp_call */
    3510         0,                              /* tp_str */
    3511         PyObject_GenericGetAttr,        /* tp_getattro */
    3512         0,                              /* tp_setattro */
    3513         0,                              /* tp_as_buffer */
    3514         Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC |
    3515                 Py_TPFLAGS_BASETYPE,    /* tp_flags */
    3516         izip_longest_doc,                       /* tp_doc */
    3517         (traverseproc)izip_longest_traverse,    /* tp_traverse */
    3518         0,                              /* tp_clear */
    3519         0,                              /* tp_richcompare */
    3520         0,                              /* tp_weaklistoffset */
    3521         PyObject_SelfIter,              /* tp_iter */
    3522         (iternextfunc)izip_longest_next,        /* tp_iternext */
    3523         0,                              /* tp_methods */
    3524         0,                              /* tp_members */
    3525         0,                              /* tp_getset */
    3526         0,                              /* tp_base */
    3527         0,                              /* tp_dict */
    3528         0,                              /* tp_descr_get */
    3529         0,                              /* tp_descr_set */
    3530         0,                              /* tp_dictoffset */
    3531         0,                              /* tp_init */
    3532         0,                              /* tp_alloc */
    3533         izip_longest_new,                       /* tp_new */
    3534         PyObject_GC_Del,                /* tp_free */
     3994    PyVarObject_HEAD_INIT(NULL, 0)
     3995    "itertools.izip_longest",           /* tp_name */
     3996    sizeof(iziplongestobject),          /* tp_basicsize */
     3997    0,                                  /* tp_itemsize */
     3998    /* methods */
     3999    (destructor)izip_longest_dealloc,           /* tp_dealloc */
     4000    0,                                  /* tp_print */
     4001    0,                                  /* tp_getattr */
     4002    0,                                  /* tp_setattr */
     4003    0,                                  /* tp_compare */
     4004    0,                                  /* tp_repr */
     4005    0,                                  /* tp_as_number */
     4006    0,                                  /* tp_as_sequence */
     4007    0,                                  /* tp_as_mapping */
     4008    0,                                  /* tp_hash */
     4009    0,                                  /* tp_call */
     4010    0,                                  /* tp_str */
     4011    PyObject_GenericGetAttr,            /* tp_getattro */
     4012    0,                                  /* tp_setattro */
     4013    0,                                  /* tp_as_buffer */
     4014    Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC |
     4015        Py_TPFLAGS_BASETYPE,            /* tp_flags */
     4016    izip_longest_doc,                           /* tp_doc */
     4017    (traverseproc)izip_longest_traverse,    /* tp_traverse */
     4018    0,                                  /* tp_clear */
     4019    0,                                  /* tp_richcompare */
     4020    0,                                  /* tp_weaklistoffset */
     4021    PyObject_SelfIter,                  /* tp_iter */
     4022    (iternextfunc)izip_longest_next,            /* tp_iternext */
     4023    0,                                  /* tp_methods */
     4024    0,                                  /* tp_members */
     4025    0,                                  /* tp_getset */
     4026    0,                                  /* tp_base */
     4027    0,                                  /* tp_dict */
     4028    0,                                  /* tp_descr_get */
     4029    0,                                  /* tp_descr_set */
     4030    0,                                  /* tp_dictoffset */
     4031    0,                                  /* tp_init */
     4032    0,                                  /* tp_alloc */
     4033    izip_longest_new,                           /* tp_new */
     4034    PyObject_GC_Del,                    /* tp_free */
    35354035};
    35364036
     
    35464046\n\
    35474047Iterators terminating on the shortest input sequence:\n\
    3548 izip(p, q, ...) --> (p[0], q[0]), (p[1], q[1]), ... \n\
    3549 izip_longest(p, q, ...) --> (p[0], q[0]), (p[1], q[1]), ... \n\
     4048chain(p, q, ...) --> p0, p1, ... plast, q0, q1, ... \n\
     4049compress(data, selectors) --> (d[0] if s[0]), (d[1] if s[1]), ...\n\
     4050dropwhile(pred, seq) --> seq[n], seq[n+1], starting when pred fails\n\
     4051groupby(iterable[, keyfunc]) --> sub-iterators grouped by value of keyfunc(v)\n\
    35504052ifilter(pred, seq) --> elements of seq where pred(elem) is True\n\
    35514053ifilterfalse(pred, seq) --> elements of seq where pred(elem) is False\n\
     
    35554057starmap(fun, seq) --> fun(*seq[0]), fun(*seq[1]), ...\n\
    35564058tee(it, n=2) --> (it1, it2 , ... itn) splits one iterator into n\n\
    3557 chain(p, q, ...) --> p0, p1, ... plast, q0, q1, ... \n\
    35584059takewhile(pred, seq) --> seq[0], seq[1], until pred fails\n\
    3559 dropwhile(pred, seq) --> seq[n], seq[n+1], starting when pred fails\n\
    3560 groupby(iterable[, keyfunc]) --> sub-iterators grouped by value of keyfunc(v)\n\
     4060izip(p, q, ...) --> (p[0], q[0]), (p[1], q[1]), ... \n\
     4061izip_longest(p, q, ...) --> (p[0], q[0]), (p[1], q[1]), ... \n\
    35614062\n\
    35624063Combinatoric generators:\n\
     
    35644065permutations(p[, r])\n\
    35654066combinations(p, r)\n\
     4067combinations_with_replacement(p, r)\n\
    35664068");
    35674069
    35684070
    35694071static PyMethodDef module_methods[] = {
    3570         {"tee", (PyCFunction)tee,       METH_VARARGS, tee_doc},
    3571         {NULL,          NULL}           /* sentinel */
     4072    {"tee",     (PyCFunction)tee,       METH_VARARGS, tee_doc},
     4073    {NULL,              NULL}           /* sentinel */
    35724074};
    35734075
     
    35754077inititertools(void)
    35764078{
    3577         int i;
    3578         PyObject *m;
    3579         char *name;
    3580         PyTypeObject *typelist[] = {
    3581                 &combinations_type,
    3582                 &cycle_type,
    3583                 &dropwhile_type,
    3584                 &takewhile_type,
    3585                 &islice_type,
    3586                 &starmap_type,
    3587                 &imap_type,
    3588                 &chain_type,
    3589                 &ifilter_type,
    3590                 &ifilterfalse_type,
    3591                 &count_type,
    3592                 &izip_type,
    3593                 &iziplongest_type,
    3594                 &permutations_type,
    3595                 &product_type,
    3596                 &repeat_type,
    3597                 &groupby_type,
    3598                 NULL
    3599         };
    3600 
    3601         Py_TYPE(&teedataobject_type) = &PyType_Type;
    3602         m = Py_InitModule3("itertools", module_methods, module_doc);
    3603         if (m == NULL)
    3604                 return;
    3605 
    3606         for (i=0 ; typelist[i] != NULL ; i++) {
    3607                 if (PyType_Ready(typelist[i]) < 0)
    3608                         return;
    3609                 name = strchr(typelist[i]->tp_name, '.');
    3610                 assert (name != NULL);
    3611                 Py_INCREF(typelist[i]);
    3612                 PyModule_AddObject(m, name+1, (PyObject *)typelist[i]);
    3613         }
    3614 
    3615         if (PyType_Ready(&teedataobject_type) < 0)
    3616                 return;
    3617         if (PyType_Ready(&tee_type) < 0)
    3618                 return;
    3619         if (PyType_Ready(&_grouper_type) < 0)
    3620                 return;
    3621 }
     4079    int i;
     4080    PyObject *m;
     4081    char *name;
     4082    PyTypeObject *typelist[] = {
     4083        &combinations_type,
     4084        &cwr_type,
     4085        &cycle_type,
     4086        &dropwhile_type,
     4087        &takewhile_type,
     4088        &islice_type,
     4089        &starmap_type,
     4090        &imap_type,
     4091        &chain_type,
     4092        &compress_type,
     4093        &ifilter_type,
     4094        &ifilterfalse_type,
     4095        &count_type,
     4096        &izip_type,
     4097        &iziplongest_type,
     4098        &permutations_type,
     4099        &product_type,
     4100        &repeat_type,
     4101        &groupby_type,
     4102        NULL
     4103    };
     4104
     4105    Py_TYPE(&teedataobject_type) = &PyType_Type;
     4106    m = Py_InitModule3("itertools", module_methods, module_doc);
     4107    if (m == NULL)
     4108        return;
     4109
     4110    for (i=0 ; typelist[i] != NULL ; i++) {
     4111        if (PyType_Ready(typelist[i]) < 0)
     4112            return;
     4113        name = strchr(typelist[i]->tp_name, '.');
     4114        assert (name != NULL);
     4115        Py_INCREF(typelist[i]);
     4116        PyModule_AddObject(m, name+1, (PyObject *)typelist[i]);
     4117    }
     4118
     4119    if (PyType_Ready(&teedataobject_type) < 0)
     4120        return;
     4121    if (PyType_Ready(&tee_type) < 0)
     4122        return;
     4123    if (PyType_Ready(&_grouper_type) < 0)
     4124        return;
     4125}
Note: See TracChangeset for help on using the changeset viewer.