source: snakeoil/src/lists.c @ ferringb@gmail.com-20100620031426-dczh83nqpkzytiwb

Revision ferringb@gmail.com-20100620031426-dczh83nqpkzytiwb, 12.7 KB checked in by Brian Harring <ferringb@…>, 6 weeks ago (diff)

tabs, not spaces
Line 
1/*
2 * Copyright: 2006 Marien Zwart <marienz@gentoo.org>
3 * License: GPL2/BSD
4 *
5 * C version of some of snakeoil (for extra speed).
6 */
7
8/* This does not really do anything since we do not use the "#"
9 * specifier in a PyArg_Parse or similar call, but hey, not using it
10 * means we are Py_ssize_t-clean too!
11 */
12
13#define PY_SSIZE_T_CLEAN
14
15#include "Python.h"
16#include "snakeoil/py24-compatibility.h"
17
18
19/* Helper functions */
20
21static PyObject *
22build_initial_iterables(PyObject *l) {
23        PyObject *result, *iter = PyObject_GetIter(l);
24        if (!iter)
25                return NULL;
26
27        result = PyList_New(1);
28        if (!result) {
29                Py_DECREF(iter);
30                return NULL;
31        }
32        PyList_SET_ITEM(result, 0, iter);
33        return result;
34}
35
36/* iflatten_func: recursively flatten an iterable with a func as filter. */
37
38typedef struct {
39        PyObject_HEAD
40        PyObject *skip_func;
41        PyObject *iterables;
42        char in_iternext;
43} snakeoil_iflatten_func;
44
45static void
46snakeoil_iflatten_func_dealloc(snakeoil_iflatten_func *self)
47{
48        Py_CLEAR(self->skip_func);
49        Py_CLEAR(self->iterables);
50        self->ob_type->tp_free((PyObject*) self);
51}
52
53static PyObject *
54snakeoil_iflatten_func_new(PyTypeObject *type,
55                                                          PyObject *args, PyObject *kwargs)
56{
57        snakeoil_iflatten_func *self;
58        PyObject *l=NULL, *skip_func=NULL, *tmp;
59        int res;
60
61        if (kwargs && PyDict_Size(kwargs)) {
62                PyErr_SetString(PyExc_TypeError,
63                                                "iflatten_func takes no keyword arguments");
64                return NULL;
65        }
66        if (!PyArg_UnpackTuple(args, "iflatten_func", 2, 2, &l, &skip_func)) {
67                return NULL;
68        }
69
70        /* Check if we got a single argument that should be skipped. */
71        tmp = PyObject_CallFunctionObjArgs(skip_func, l, NULL);
72        if (!tmp) {
73                return NULL;
74        }
75        // Py_(True|False) are singletons, thus we're trying to bypass
76        // the PyObject_IsTrue triggering __nonzero__ protocol.
77        if(tmp == Py_True) {
78                res = 1;
79        } else if (tmp == Py_False) {
80                res = 0;
81        } else {
82                res = PyObject_IsTrue(tmp);
83                if(res == -1) {
84                        Py_DECREF(tmp);
85                        return NULL;
86                }
87        }
88        Py_DECREF(tmp);
89        if (res) {
90                PyObject *tuple = PyTuple_Pack(1, l);
91                if (!tuple) {
92                        return NULL;
93                }
94                PyObject *iter = PyObject_GetIter(tuple);
95                Py_DECREF(tuple);
96                return iter;
97        }
98
99        self = (snakeoil_iflatten_func *)type->tp_alloc(type, 0);
100        if (!self)
101                return NULL;
102
103        self->in_iternext = 0;
104
105        if (!(self->iterables = build_initial_iterables(l))) {
106                Py_DECREF(self);
107                return NULL;
108        }
109
110        Py_INCREF(skip_func);
111        self->skip_func = skip_func;
112
113        return (PyObject *)self;
114}
115
116static PyObject *
117snakeoil_iflatten_func_iternext(snakeoil_iflatten_func *self) {
118        PyObject *tail, *result, *tmp;
119        int res;
120        Py_ssize_t n;
121
122        if (self->in_iternext) {
123                /* We do not allow this because it means our list could be
124                 * manipulated while we are running. Exception raised matches
125                 * what a generator raises if you try the same thing.
126                 */
127                PyErr_SetString(PyExc_ValueError,
128                                                "Recursive calls to iflatten_func.next are illegal");
129                return NULL;
130        }
131        self->in_iternext = 1;
132
133        /* Look at the final iterator on our stack: */
134        while ((n = PyList_GET_SIZE(self->iterables))) {
135                tail = PyList_GET_ITEM(self->iterables, n - 1);
136
137                /* See if it has any results left: */
138
139                /* (This reference is borrowed from the list, but since we
140                   disallow recursive calls in here it should be safe to not
141                   increment it). */
142
143                result = PyIter_Next(tail);
144                if (result) {
145
146                        /* See if we need to iterate over this new result: */
147
148                        tmp = PyObject_CallFunctionObjArgs(self->skip_func, result, NULL);
149                        if (!tmp) {
150                                Py_DECREF(result);
151                                self->in_iternext = 0;
152                                return NULL;
153                        }
154                        res = PyObject_IsTrue(tmp);
155                        Py_DECREF(tmp);
156                        if (res == -1) {
157                                Py_DECREF(result);
158                                result = NULL;
159                        } else if (!res) {
160                                /* False from our skip func. */
161                                /* If it is an iterator add it to our chain, else return it. */
162                                tmp = PyObject_GetIter(result);
163                                if (tmp) {
164                                        /* Iterable, append to our stack and continue. */
165                                        Py_DECREF(result);
166                                        result = NULL;
167                                        res = PyList_Append(self->iterables, tmp);
168                                        Py_DECREF(tmp);
169                                        if (res != -1) {
170                                                continue;
171                                        }
172                                        /* Fall through and propagate the error. */
173                                } else {
174                                        /* If we get here PyObject_GetIter raised an exception.
175                                         * If it was TypeError we have a non-iterator we can
176                                         * just return, else we propagate the error.
177                                         */
178                                        if (PyErr_ExceptionMatches(PyExc_TypeError)) {
179                                                PyErr_Clear();
180                                        } else {
181                                                Py_DECREF(result);
182                                                result = NULL;
183                                        }
184                                }
185                        }
186                } else {
187                        /* PyIter_Next did not return an item. If this was not
188                         * because of an error we should pop the exhausted
189                         * iterable off and continue. */
190                        if (!PyErr_Occurred() &&
191                                PySequence_DelItem(self->iterables, n - 1) != -1) {
192                                continue;
193                        }
194                }
195                self->in_iternext = 0;
196                return result;
197        }
198
199        /* We ran out of iterables entirely, so we are done */
200        self->in_iternext = 0;
201        return NULL;
202}
203
204PyDoc_STRVAR(
205        snakeoil_iflatten_func_documentation,
206        "iflatten_func(iters, func): collapse [(1),2] into [1,2]\n"
207        "\n"
208        "func is called with one argument and should return true if this \n"
209        "should not be iterated over.\n"
210        );
211
212static PyTypeObject snakeoil_iflatten_func_type = {
213        PyObject_HEAD_INIT(NULL)
214        0,                                                                                         /* ob_size*/
215        "snakeoil._lists.iflatten_func",                                 /* tp_name*/
216        sizeof(snakeoil_iflatten_func),                            /* tp_basicsize*/
217        0,                                                                                         /* tp_itemsize*/
218        (destructor)snakeoil_iflatten_func_dealloc,        /* tp_dealloc*/
219        0,                                                                                         /* tp_print*/
220        0,                                                                                         /* tp_getattr*/
221        0,                                                                                         /* tp_setattr*/
222        0,                                                                                         /* tp_compare*/
223        0,                                                                                         /* tp_repr*/
224        0,                                                                                         /* tp_as_number*/
225        0,                                                                                         /* tp_as_sequence*/
226        0,                                                                                         /* tp_as_mapping*/
227        0,                                                                                         /* tp_hash */
228        (ternaryfunc)0,                                                           /* tp_call*/
229        (reprfunc)0,                                                                     /* tp_str*/
230        0,                                                                                         /* tp_getattro*/
231        0,                                                                                         /* tp_setattro*/
232        0,                                                                                         /* tp_as_buffer*/
233        Py_TPFLAGS_DEFAULT,                                                       /* tp_flags*/
234        snakeoil_iflatten_func_documentation,                    /* tp_doc */
235        (traverseproc)0,                                                                 /* tp_traverse */
236        (inquiry)0,                                                                       /* tp_clear */
237        (richcmpfunc)0,                                                           /* tp_richcompare */
238        0,                                                                                         /* tp_weaklistoffset */
239        (getiterfunc)PyObject_SelfIter,                           /* tp_iter */
240        (iternextfunc)snakeoil_iflatten_func_iternext,  /* tp_iternext */
241        0,                                                                                         /* tp_methods */
242        0,                                                                                         /* tp_members */
243        0,                                                                                         /* tp_getset */
244        0,                                                                                         /* tp_base */
245        0,                                                                                         /* tp_dict */
246        0,                                                                                         /* tp_descr_get */
247        0,                                                                                         /* tp_descr_set */
248        0,                                                                                         /* tp_dictoffset */
249        (initproc)0,                                                                     /* tp_init */
250        0,                                                                                         /* tp_alloc */
251        snakeoil_iflatten_func_new,                                        /* tp_new */
252};
253
254/* iflatten_instance: recursively flatten an iterable
255   except for some instances */
256
257typedef struct {
258        PyObject_HEAD
259        PyObject *skip_flattening;
260        PyObject *iterables;
261        char in_iternext;
262} snakeoil_iflatten_instance;
263
264static void
265snakeoil_iflatten_instance_dealloc(snakeoil_iflatten_instance *self)
266{
267        Py_CLEAR(self->skip_flattening);
268        Py_CLEAR(self->iterables);
269        self->ob_type->tp_free((PyObject*) self);
270}
271
272static PyObject *
273snakeoil_iflatten_instance_new(PyTypeObject *type,
274                                                                  PyObject *args, PyObject *kwargs)
275{
276        snakeoil_iflatten_instance *self;
277        PyObject *l=NULL, *skip_flattening=(PyObject*)&PyBaseString_Type;
278        int res;
279
280        if (kwargs && PyDict_Size(kwargs)) {
281                PyErr_SetString(PyExc_TypeError,
282                                                "iflatten_instance takes no keyword arguments");
283                return NULL;
284        }
285        if (!PyArg_UnpackTuple(args, "iflatten_instance", 1, 2,
286                                                   &l, &skip_flattening)) {
287                return NULL;
288        }
289
290        /* Check if we got a single argument that should be skipped. */
291        res = PyObject_IsInstance(l, skip_flattening);
292        if (res == -1) {
293                return NULL;
294        } else if (res) {
295                PyObject *tuple = PyTuple_Pack(1, l);
296                if (!tuple) {
297                        return NULL;
298                }
299                PyObject *iter = PyObject_GetIter(tuple);
300                Py_DECREF(tuple);
301                return iter;
302        }
303
304        self = (snakeoil_iflatten_instance *)type->tp_alloc(type, 0);
305        if (!self)
306                return NULL;
307
308        self->in_iternext = 0;
309
310        if (!(self->iterables = build_initial_iterables(l))) {
311                Py_DECREF(self);
312                return NULL;
313        }
314
315        Py_INCREF(skip_flattening);
316        self->skip_flattening = skip_flattening;
317
318        return (PyObject *)self;
319}
320
321static PyObject *
322snakeoil_iflatten_instance_iternext(snakeoil_iflatten_instance *self) {
323        PyObject *tail, *result, *iter;
324        int n, res;
325
326        if (self->in_iternext) {
327                /* We do not allow this because it means our list could be
328                 * manipulated while we are running. Exception raised matches
329                 * what a generator raises if you try the same thing.
330                 */
331                PyErr_SetString(
332                        PyExc_ValueError,
333                        "Recursive calls to iflatten_instance.next are illegal");
334                return NULL;
335        }
336        self->in_iternext = 1;
337
338        /* Look at the final iterator on our stack: */
339
340        while ((n = PyList_GET_SIZE(self->iterables))) {
341                tail = PyList_GET_ITEM(self->iterables, n - 1);
342
343                /* See if it has any results left: */
344                /* (This reference is borrowed from the list, but since we
345                   disallow recursive calls in here it should be safe to not
346                   increment it). */
347
348                result = PyIter_Next(tail);
349                if (result) {
350                        /* See if we need to iterate over this new result: */
351
352                        res = PyObject_IsInstance(result, self->skip_flattening);
353                        if (res == -1) {
354                                Py_DECREF(result);
355                                result = NULL;
356                        } else if (!res) {
357                                /* Not in skip_flattening. */
358                                /* If it is an iterator add it to our chain, else return it. */
359                                iter = PyObject_GetIter(result);
360                                if (iter) {
361                                        /* Iterable, append to our stack and continue. */
362                                        Py_DECREF(result);
363                                        result = NULL;
364                                        res = PyList_Append(self->iterables, iter);
365                                        Py_DECREF(iter);
366                                        if (res != -1) {
367                                                continue;
368                                        }
369                                        /* Fall through and propagate the error. */
370                                } else {
371                                        /* If we get here PyObject_GetIter raised an exception.
372                                         * If it was TypeError we have a non-iterator we can
373                                         * just return, else we propagate the error.
374                                         */
375                                        if (PyErr_ExceptionMatches(PyExc_TypeError)) {
376                                                PyErr_Clear();
377                                        } else {
378                                                Py_DECREF(result);
379                                                result = NULL;
380                                        }
381                                }
382                        }
383                } else {
384                        /* PyIter_Next did not return an item. If this was not
385                         * because of an error we should pop the exhausted
386                         * iterable off and continue. */
387                        if (!PyErr_Occurred() &&
388                                PySequence_DelItem(self->iterables, n - 1) != -1) {
389                                continue;
390                        }
391                }
392                self->in_iternext = 0;
393                return result;
394        }
395
396        /* We ran out of iterables entirely, so we are done */
397        self->in_iternext = 0;
398        return NULL;
399}
400
401PyDoc_STRVAR(
402        snakeoil_iflatten_instance_documentation,
403        "iflatten_func(iters, skip_flattening=basestring)\n"
404        "\n"
405        "collapse [(1),2] into [1,2]\n"
406        "skip_flattening is a list of classes to not descend through\n"
407        );
408
409static PyTypeObject snakeoil_iflatten_instance_type = {
410        PyObject_HEAD_INIT(NULL)
411        0,                                                                                         /* ob_size*/
412        "snakeoil._lists.iflatten_instance",                     /* tp_name*/
413        sizeof(snakeoil_iflatten_instance),                        /* tp_basicsize*/
414        0,                                                                                         /* tp_itemsize*/
415        (destructor)snakeoil_iflatten_instance_dealloc,   /* tp_dealloc*/
416        0,                                                                                         /* tp_print*/
417        0,                                                                                         /* tp_getattr*/
418        0,                                                                                         /* tp_setattr*/
419        0,                                                                                         /* tp_compare*/
420        0,                                                                                         /* tp_repr*/
421        0,                                                                                         /* tp_as_number*/
422        0,                                                                                         /* tp_as_sequence*/
423        0,                                                                                         /* tp_as_mapping*/
424        0,                                                                                         /* tp_hash */
425        (ternaryfunc)0,                                                           /* tp_call*/
426        (reprfunc)0,                                                                     /* tp_str*/
427        0,                                                                                         /* tp_getattro*/
428        0,                                                                                         /* tp_setattro*/
429        0,                                                                                         /* tp_as_buffer*/
430        Py_TPFLAGS_DEFAULT,                                                       /* tp_flags*/
431        snakeoil_iflatten_instance_documentation,                /* tp_doc */
432        (traverseproc)0,                                                                 /* tp_traverse */
433        (inquiry)0,                                                                       /* tp_clear */
434        (richcmpfunc)0,                                                           /* tp_richcompare */
435        0,                                                                                         /* tp_weaklistoffset */
436        (getiterfunc)PyObject_SelfIter,                           /* tp_iter */
437        (iternextfunc)snakeoil_iflatten_instance_iternext, /* tp_iternext */
438        0,                                                                                         /* tp_methods */
439        0,                                                                                         /* tp_members */
440        0,                                                                                         /* tp_getset */
441        0,                                                                                         /* tp_base */
442        0,                                                                                         /* tp_dict */
443        0,                                                                                         /* tp_descr_get */
444        0,                                                                                         /* tp_descr_set */
445        0,                                                                                         /* tp_dictoffset */
446        (initproc)0,                                                                     /* tp_init */
447        0,                                                                                         /* tp_alloc */
448        snakeoil_iflatten_instance_new,                            /* tp_new */
449};
450
451
452/* Initialization function for the module */
453
454PyDoc_STRVAR(
455        snakeoil_lists_documentation,
456        "C reimplementation of some of snakeoil.lists.");
457
458PyMODINIT_FUNC
459init_lists(void)
460{
461        /* Create the module and add the functions */
462        PyObject *m = Py_InitModule3("_lists", NULL, snakeoil_lists_documentation);
463        if (!m)
464                return;
465
466        if (PyType_Ready(&snakeoil_iflatten_func_type) < 0)
467                return;
468
469        if (PyType_Ready(&snakeoil_iflatten_instance_type) < 0)
470                return;
471
472        Py_INCREF(&snakeoil_iflatten_func_type);
473        if (PyModule_AddObject(
474                        m, "iflatten_func", (PyObject *)&snakeoil_iflatten_func_type) == -1)
475                return;
476
477        Py_INCREF(&snakeoil_iflatten_instance_type);
478        if (PyModule_AddObject(
479                        m, "iflatten_instance",
480                        (PyObject *)&snakeoil_iflatten_instance_type) == -1)
481                return;
482}
Note: See TracBrowser for help on using the repository browser.