Backed out changeset 57776eee74f2

1 files changed, 1 insertions, 546 deletions

diff --git a/Modules/_functoolsmodule.c b/Modules/_functoolsmodule.c
index 99b50b0e9d..3c82e5134a 100644
--- a/Modules/_functoolsmodule.c
+++ b/Modules/_functoolsmodule.c
@@ -590,539 +590,6 @@ For example, reduce(lambda x, y: x+y, [1, 2, 3, 4, 5]) calculates\n\
 of the sequence in the calculation, and serves as a default when the\n\
 sequence is empty.");
 
-/* lru_cache object **********************************************************/
-
-/* this object is used delimit args and keywords in the cache keys */
-static PyObject *kwd_mark = NULL;
-
-struct lru_list_elem;
-struct lru_cache_object;
-
-typedef struct lru_list_elem {
-    PyObject_HEAD
-    struct lru_list_elem *prev, *next;  /* borrowed links */
-    PyObject *key, *result;
-} lru_list_elem;
-
-static void
-lru_list_elem_dealloc(lru_list_elem *link)
-{
-    _PyObject_GC_UNTRACK(link);
-    Py_XDECREF(link->key);
-    Py_XDECREF(link->result);
-    PyObject_GC_Del(link);
-}
-
-static int
-lru_list_elem_traverse(lru_list_elem *link, visitproc visit, void *arg)
-{
-    Py_VISIT(link->key);
-    Py_VISIT(link->result);
-    return 0;
-}
-
-static int
-lru_list_elem_clear(lru_list_elem *link)
-{
-    Py_CLEAR(link->key);
-    Py_CLEAR(link->result);
-    return 0;
-}
-
-static PyTypeObject lru_list_elem_type = {
-    PyVarObject_HEAD_INIT(&PyType_Type, 0)
-    "functools._lru_list_elem",         /* tp_name */
-    sizeof(lru_list_elem),              /* tp_basicsize */
-    0,                                  /* tp_itemsize */
-    /* methods */
-    (destructor)lru_list_elem_dealloc,  /* tp_dealloc */
-    0,                                  /* tp_print */
-    0,                                  /* tp_getattr */
-    0,                                  /* tp_setattr */
-    0,                                  /* tp_reserved */
-    0,                                  /* tp_repr */
-    0,                                  /* tp_as_number */
-    0,                                  /* tp_as_sequence */
-    0,                                  /* tp_as_mapping */
-    0,                                  /* tp_hash */
-    0,                                  /* tp_call */
-    0,                                  /* tp_str */
-    0,                                  /* tp_getattro */
-    0,                                  /* tp_setattro */
-    0,                                  /* tp_as_buffer */
-    Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC,  /* tp_flags */
-    0,                                  /* tp_doc */
-    (traverseproc)lru_list_elem_traverse,  /* tp_traverse */
-    (inquiry)lru_list_elem_clear,       /* tp_clear */
-};
-
-
-typedef PyObject *(*lru_cache_ternaryfunc)(struct lru_cache_object *, PyObject *, PyObject *);
-
-typedef struct lru_cache_object {
-    lru_list_elem root;  /* includes PyObject_HEAD */
-    Py_ssize_t maxsize;
-    PyObject *maxsize_O;
-    PyObject *func;
-    lru_cache_ternaryfunc wrapper;
-    PyObject *cache;
-    PyObject *cache_info_type;
-    Py_ssize_t misses, hits;
-    int typed;
-    PyObject *dict;
-    int full;
-} lru_cache_object;
-
-static PyTypeObject lru_cache_type;
-
-static PyObject *
-lru_cache_make_key(PyObject *args, PyObject *kwds, int typed)
-{
-    PyObject *key, *sorted_items;
-    Py_ssize_t key_size, pos, key_pos;
-
-    /* short path, key will match args anyway, which is a tuple */
-    if (!typed && !kwds) {
-        Py_INCREF(args);
-        return args;
-    }
-
-    if (kwds && PyDict_Size(kwds) > 0) {
-        sorted_items = PyDict_Items(kwds);
-        if (!sorted_items)
-            return NULL;
-        if (PyList_Sort(sorted_items) < 0) {
-            Py_DECREF(sorted_items);
-            return NULL;
-        }
-    } else
-        sorted_items = NULL;
-
-    key_size = PyTuple_GET_SIZE(args);
-    if (sorted_items)
-        key_size += PyList_GET_SIZE(sorted_items);
-    if (typed)
-        key_size *= 2;
-    if (sorted_items)
-        key_size++;
-
-    key = PyTuple_New(key_size);
-    if (key == NULL)
-        goto done;
-
-    key_pos = 0;
-    for (pos = 0; pos < PyTuple_GET_SIZE(args); ++pos) {
-        PyObject *item = PyTuple_GET_ITEM(args, pos);
-        Py_INCREF(item);
-        PyTuple_SET_ITEM(key, key_pos++, item);
-    }
-    if (sorted_items) {
-        Py_INCREF(kwd_mark);
-        PyTuple_SET_ITEM(key, key_pos++, kwd_mark);
-        for (pos = 0; pos < PyList_GET_SIZE(sorted_items); ++pos) {
-            PyObject *item = PyList_GET_ITEM(sorted_items, pos);
-            Py_INCREF(item);
-            PyTuple_SET_ITEM(key, key_pos++, item);
-        }
-    }
-    if (typed) {
-        for (pos = 0; pos < PyTuple_GET_SIZE(args); ++pos) {
-            PyObject *item = (PyObject *)Py_TYPE(PyTuple_GET_ITEM(args, pos));
-            Py_INCREF(item);
-            PyTuple_SET_ITEM(key, key_pos++, item);
-        }
-        if (sorted_items) {
-            for (pos = 0; pos < PyList_GET_SIZE(sorted_items); ++pos) {
-                PyObject *tp_items = PyList_GET_ITEM(sorted_items, pos);
-                PyObject *item = (PyObject *)Py_TYPE(PyTuple_GET_ITEM(tp_items, 1));
-                Py_INCREF(item);
-                PyTuple_SET_ITEM(key, key_pos++, item);
-            }
-        }
-    }
-    assert(key_pos == key_size);
-
-done:
-    if (sorted_items)
-        Py_DECREF(sorted_items);
-    return key;
-}
-
-static PyObject *
-uncached_lru_cache_wrapper(lru_cache_object *self, PyObject *args, PyObject *kwds)
-{
-    PyObject *result = PyObject_Call(self->func, args, kwds);
-    if (!result)
-        return NULL;
-    self->misses++;
-    return result;
-}
-
-static PyObject *
-infinite_lru_cache_wrapper(lru_cache_object *self, PyObject *args, PyObject *kwds)
-{
-    PyObject *result;
-    PyObject *key = lru_cache_make_key(args, kwds, self->typed);
-    if (!key)
-        return NULL;
-    result = PyDict_GetItemWithError(self->cache, key);
-    if (result) {
-        Py_INCREF(result);
-        self->hits++;
-        Py_DECREF(key);
-        return result;
-    }
-    if (PyErr_Occurred()) {
-        Py_DECREF(key);
-        return NULL;
-    }
-    result = PyObject_Call(self->func, args, kwds);
-    if (!result) {
-        Py_DECREF(key);
-        return NULL;
-    }
-    if (PyDict_SetItem(self->cache, key, result) < 0) {
-        Py_DECREF(result);
-        Py_DECREF(key);
-        return NULL;
-    }
-    Py_DECREF(key);
-    self->misses++;
-    return result;
-}
-
-static void
-lru_cache_extricate_link(lru_list_elem *link)
-{
-    link->prev->next = link->next;
-    link->next->prev = link->prev;
-}
-
-static void
-lru_cache_append_link(lru_cache_object *self, lru_list_elem *link)
-{
-    lru_list_elem *root = &self->root;
-    lru_list_elem *last = root->prev;
-    last->next = root->prev = link;
-    link->prev = last;
-    link->next = root;
-}
-
-static PyObject *
-bounded_lru_cache_wrapper(lru_cache_object *self, PyObject *args, PyObject *kwds)
-{
-    lru_list_elem *link;
-    PyObject *key, *result;
-
-    key = lru_cache_make_key(args, kwds, self->typed);
-    if (!key)
-        return NULL;
-    link  = (lru_list_elem *)PyDict_GetItemWithError(self->cache, key);
-    if (link) {
-        lru_cache_extricate_link(link);
-        lru_cache_append_link(self, link);
-        self->hits++;
-        result = link->result;
-        Py_INCREF(result);
-        Py_DECREF(key);
-        return result;
-    }
-    if (PyErr_Occurred()) {
-        Py_DECREF(key);
-        return NULL;
-    }
-    result = PyObject_Call(self->func, args, kwds);
-    if (!result) {
-        Py_DECREF(key);
-        return NULL;
-    }
-    if (self->full && self->root.next != &self->root) {
-        /* Use the oldest item to store the new key and result. */
-        PyObject *oldkey, *oldresult;
-        /* Extricate the oldest item. */
-        link = self->root.next;
-        lru_cache_extricate_link(link);
-        /* Remove it from the cache.
-           The cache dict holds one reference to the link,
-           and the linked list holds yet one reference to it. */
-        if (PyDict_DelItem(self->cache, link->key) < 0) {
-            lru_cache_append_link(self, link);
-            Py_DECREF(key);
-            Py_DECREF(result);
-            return NULL;
-        }
-        /* Keep a reference to the old key and old result to
-           prevent their ref counts from going to zero during the
-           update. That will prevent potentially arbitrary object
-           clean-up code (i.e. __del__) from running while we're
-           still adjusting the links. */
-        oldkey = link->key;
-        oldresult = link->result;
-
-        link->key = key;
-        link->result = result;
-        if (PyDict_SetItem(self->cache, key, (PyObject *)link) < 0) {
-            Py_DECREF(link);
-            Py_DECREF(oldkey);
-            Py_DECREF(oldresult);
-            return NULL;
-        }
-        lru_cache_append_link(self, link);
-        Py_INCREF(result); /* for return */
-        Py_DECREF(oldkey);
-        Py_DECREF(oldresult);
-    } else {
-        /* Put result in a new link at the front of the queue. */
-        link = (lru_list_elem *)PyObject_GC_New(lru_list_elem,
-                                                &lru_list_elem_type);
-        if (link == NULL) {
-            Py_DECREF(key);
-            Py_DECREF(result);
-            return NULL;
-        }
-
-        link->key = key;
-        link->result = result;
-        _PyObject_GC_TRACK(link);
-        if (PyDict_SetItem(self->cache, key, (PyObject *)link) < 0) {
-            Py_DECREF(link);
-            return NULL;
-        }
-        lru_cache_append_link(self, link);
-        Py_INCREF(result); /* for return */
-        self->full = (PyDict_Size(self->cache) >= self->maxsize);
-    }
-    self->misses++;
-    return result;
-}
-
-static PyObject *
-lru_cache_new(PyTypeObject *type, PyObject *args, PyObject *kw)
-{
-    PyObject *func, *maxsize_O, *cache_info_type;
-    int typed;
-    lru_cache_object *obj;
-    Py_ssize_t maxsize;
-    PyObject *(*wrapper)(lru_cache_object *, PyObject *, PyObject *);
-    static char *keywords[] = {"user_function", "maxsize", "typed",
-                               "cache_info_type", NULL};
-
-    if (!PyArg_ParseTupleAndKeywords(args, kw, "OOpO:lru_cache", keywords,
-                                     &func, &maxsize_O, &typed,
-                                     &cache_info_type)) {
-        return NULL;
-    }
-
-    if (!PyCallable_Check(func)) {
-        PyErr_SetString(PyExc_TypeError,
-                        "the first argument must be callable");
-        return NULL;
-    }
-
-    /* select the caching function, and make/inc maxsize_O */
-    if (maxsize_O == Py_None) {
-        wrapper = infinite_lru_cache_wrapper;
-        /* use this only to initialize lru_cache_object attribute maxsize */
-        maxsize = -1;
-    } else if (PyIndex_Check(maxsize_O)) {
-        maxsize = PyNumber_AsSsize_t(maxsize_O, PyExc_OverflowError);
-        if (maxsize == -1 && PyErr_Occurred())
-            return NULL;
-        if (maxsize == 0)
-            wrapper = uncached_lru_cache_wrapper;
-        else
-            wrapper = bounded_lru_cache_wrapper;
-    } else {
-        PyErr_SetString(PyExc_TypeError, "maxsize should be integer or None");
-        return NULL;
-    }
-
-    obj = (lru_cache_object *)type->tp_alloc(type, 0);
-    if (obj == NULL)
-        return NULL;
-
-    if (!(obj->cache = PyDict_New())) {
-        Py_DECREF(obj);
-        return NULL;
-    }
-
-    obj->root.prev = &obj->root;
-    obj->root.next = &obj->root;
-    obj->maxsize = maxsize;
-    Py_INCREF(maxsize_O);
-    obj->maxsize_O = maxsize_O;
-    Py_INCREF(func);
-    obj->func = func;
-    obj->wrapper = wrapper;
-    obj->misses = obj->hits = 0;
-    obj->typed = typed;
-    Py_INCREF(cache_info_type);
-    obj->cache_info_type = cache_info_type;
-
-    return (PyObject *)obj;
-}
-
-static lru_list_elem *
-lru_cache_unlink_list(lru_cache_object *self)
-{
-    lru_list_elem *root = &self->root;
-    lru_list_elem *link = root->next;
-    if (link == root)
-        return NULL;
-    root->prev->next = NULL;
-    root->next = root->prev = root;
-    return link;
-}
-
-static void
-lru_cache_clear_list(lru_list_elem *link)
-{
-    while (link != NULL) {
-        lru_list_elem *next = link->next;
-        Py_DECREF(link);
-        link = next;
-    }
-}
-
-static void
-lru_cache_dealloc(lru_cache_object *obj)
-{
-    lru_list_elem *list = lru_cache_unlink_list(obj);
-    Py_XDECREF(obj->maxsize_O);
-    Py_XDECREF(obj->func);
-    Py_XDECREF(obj->cache);
-    Py_XDECREF(obj->dict);
-    Py_XDECREF(obj->cache_info_type);
-    lru_cache_clear_list(list);
-    Py_TYPE(obj)->tp_free(obj);
-}
-
-static PyObject *
-lru_cache_call(lru_cache_object *self, PyObject *args, PyObject *kwds)
-{
-    return self->wrapper(self, args, kwds);
-}
-
-static PyObject *
-lru_cache_cache_info(lru_cache_object *self, PyObject *unused)
-{
-    return PyObject_CallFunction(self->cache_info_type, "nnOn",
-                                 self->hits, self->misses, self->maxsize_O,
-                                 PyDict_Size(self->cache));
-}
-
-static PyObject *
-lru_cache_cache_clear(lru_cache_object *self, PyObject *unused)
-{
-    lru_list_elem *list = lru_cache_unlink_list(self);
-    self->hits = self->misses = 0;
-    self->full = 0;
-    PyDict_Clear(self->cache);
-    lru_cache_clear_list(list);
-    Py_RETURN_NONE;
-}
-
-static int
-lru_cache_tp_traverse(lru_cache_object *self, visitproc visit, void *arg)
-{
-    lru_list_elem *link = self->root.next;
-    while (link != &self->root) {
-        lru_list_elem *next = link->next;
-        Py_VISIT(link);
-        link = next;
-    }
-    Py_VISIT(self->maxsize_O);
-    Py_VISIT(self->func);
-    Py_VISIT(self->cache);
-    Py_VISIT(self->cache_info_type);
-    Py_VISIT(self->dict);
-    return 0;
-}
-
-static int
-lru_cache_tp_clear(lru_cache_object *self)
-{
-    lru_list_elem *list = lru_cache_unlink_list(self);
-    Py_CLEAR(self->maxsize_O);
-    Py_CLEAR(self->func);
-    Py_CLEAR(self->cache);
-    Py_CLEAR(self->cache_info_type);
-    Py_CLEAR(self->dict);
-    lru_cache_clear_list(list);
-    return 0;
-}
-
-
-PyDoc_STRVAR(lru_cache_doc,
-"Create a cached callable that wraps another function.\n\
-\n\
-user_function:      the function being cached\n\
-\n\
-maxsize:  0         for no caching\n\
-          None      for unlimited cache size\n\
-          n         for a bounded cache\n\
-\n\
-typed:    False     cache f(3) and f(3.0) as identical calls\n\
-          True      cache f(3) and f(3.0) as distinct calls\n\
-\n\
-cache_info_type:    namedtuple class with the fields:\n\
-                        hits misses currsize maxsize\n"
-);
-
-static PyMethodDef lru_cache_methods[] = {
-    {"cache_info", (PyCFunction)lru_cache_cache_info, METH_NOARGS},
-    {"cache_clear", (PyCFunction)lru_cache_cache_clear, METH_NOARGS},
-    {NULL}
-};
-
-static PyGetSetDef lru_cache_getsetlist[] = {
-    {"__dict__", PyObject_GenericGetDict, PyObject_GenericSetDict},
-    {NULL}
-};
-
-static PyTypeObject lru_cache_type = {
-    PyVarObject_HEAD_INIT(NULL, 0)
-    "functools._lru_cache_wrapper",     /* tp_name */
-    sizeof(lru_cache_object),           /* tp_basicsize */
-    0,                                  /* tp_itemsize */
-    /* methods */
-    (destructor)lru_cache_dealloc,      /* tp_dealloc */
-    0,                                  /* tp_print */
-    0,                                  /* tp_getattr */
-    0,                                  /* tp_setattr */
-    0,                                  /* tp_reserved */
-    0,                                  /* tp_repr */
-    0,                                  /* tp_as_number */
-    0,                                  /* tp_as_sequence */
-    0,                                  /* tp_as_mapping */
-    0,                                  /* tp_hash */
-    (ternaryfunc)lru_cache_call,        /* tp_call */
-    0,                                  /* tp_str */
-    0,                                  /* tp_getattro */
-    0,                                  /* tp_setattro */
-    0,                                  /* tp_as_buffer */
-    Py_TPFLAGS_DEFAULT|Py_TPFLAGS_BASETYPE|Py_TPFLAGS_HAVE_GC,
-                                        /* tp_flags */
-    lru_cache_doc,                      /* tp_doc */
-    (traverseproc)lru_cache_tp_traverse,/* tp_traverse */
-    (inquiry)lru_cache_tp_clear,        /* tp_clear */
-    0,                                  /* tp_richcompare */
-    0,                                  /* tp_weaklistoffset */
-    0,                                  /* tp_iter */
-    0,                                  /* tp_iternext */
-    lru_cache_methods,                  /* tp_methods */
-    0,                                  /* tp_members */
-    lru_cache_getsetlist,               /* tp_getset */
-    0,                                  /* tp_base */
-    0,                                  /* tp_dict */
-    0,                                  /* tp_descr_get */
-    0,                                  /* tp_descr_set */
-    offsetof(lru_cache_object, dict),   /* tp_dictoffset */
-    0,                                  /* tp_init */
-    0,                                  /* tp_alloc */
-    lru_cache_new,                      /* tp_new */
-};
-
 /* module level code ********************************************************/
 
 PyDoc_STRVAR(module_doc,
@@ -1135,11 +602,6 @@ static PyMethodDef module_methods[] = {
     {NULL,              NULL}           /* sentinel */
 };
 
-static void
-module_free(void *m)
-{
-    Py_CLEAR(kwd_mark);
-}
 
 static struct PyModuleDef _functoolsmodule = {
     PyModuleDef_HEAD_INIT,
@@ -1150,7 +612,7 @@ static struct PyModuleDef _functoolsmodule = {
     NULL,
     NULL,
     NULL,
-    module_free,
+    NULL
 };
 
 PyMODINIT_FUNC
@@ -1161,7 +623,6 @@ PyInit__functools(void)
     char *name;
     PyTypeObject *typelist[] = {
         &partial_type,
-        &lru_cache_type,
         NULL
     };
 
@@ -1169,12 +630,6 @@ PyInit__functools(void)
     if (m == NULL)
         return NULL;
 
-    kwd_mark = PyObject_CallObject((PyObject *)&PyBaseObject_Type, NULL);
-    if (!kwd_mark) {
-        Py_DECREF(m);
-        return NULL;
-    }
-
     for (i=0 ; typelist[i] != NULL ; i++) {
         if (PyType_Ready(typelist[i]) < 0) {
             Py_DECREF(m);