#include "Python.h"

#include "pycore_call.h" // _PyObject_CallNoArgs()

#include "pycore_long.h" // _PyLong_GetZero()

#include "pycore_moduleobject.h" // _PyModule_GetState()

#include "pycore_object.h" // _PyObject_GC_TRACK

#include "pycore_pystate.h" // _PyThreadState_GET()

#include "pycore_tuple.h" // _PyTuple_ITEMS()

#include "structmember.h" // PyMemberDef

#include "clinic/_functoolsmodule.c.h"

typedef struct _functools_state {

} _functools_state;

static inline _functools_state *

get_functools_state(PyObject *module)

{

void *state = _PyModule_GetState(module);

assert(state != NULL);

return (_functools_state *)state;

}

typedef struct {

PyObject_HEAD

PyObject *fn;

PyObject *args;

PyObject *kw;

PyObject *dict; /* __dict__ */

PyObject *weakreflist; /* List of weak references */

vectorcallfunc vectorcall;

} partialobject;

static void partial_setvectorcall(partialobject *pto);

static struct PyModuleDef _functools_module;

static PyObject *

partial_call(partialobject *pto, PyObject *args, PyObject *kwargs);

static inline _functools_state *

get_functools_state_by_type(PyTypeObject *type)

{

PyObject *module = PyType_GetModuleByDef(type, &_functools_module);

if (module == NULL) {

return NULL;

}

return get_functools_state(module);

}

static PyObject *

partial_new(PyTypeObject *type, PyObject *args, PyObject *kw)

{

PyObject *func, *pargs, *nargs, *pkw;

partialobject *pto;

if (PyTuple_GET_SIZE(args) < 1) {

PyErr_SetString(PyExc_TypeError,

"type 'partial' takes at least one argument");

return NULL;

}

pargs = pkw = NULL;

func = PyTuple_GET_ITEM(args, 0);

if (Py_TYPE(func)->tp_call == (ternaryfunc)partial_call) {

// The type of "func" might not be exactly the same type object

// as "type", but if it is called using partial_call, it must have the

// same memory layout (fn, args and kw members).

// We can use its underlying function directly and merge the arguments.

partialobject *part = (partialobject *)func;

if (part->dict == NULL) {

pargs = part->args;

pkw = part->kw;

func = part->fn;

assert(PyTuple_Check(pargs));

assert(PyDict_Check(pkw));

}

}

if (!PyCallable_Check(func)) {

PyErr_SetString(PyExc_TypeError,

"the first argument must be callable");

return NULL;

}

/* create partialobject structure */

pto = (partialobject *)type->tp_alloc(type, 0);

if (pto == NULL)

return NULL;

pto->fn = func;

Py_INCREF(func);

nargs = PyTuple_GetSlice(args, 1, PY_SSIZE_T_MAX);

if (nargs == NULL) {

Py_DECREF(pto);

return NULL;

}

if (pargs == NULL) {

pto->args = nargs;

}

else {

pto->args = PySequence_Concat(pargs, nargs);

Py_DECREF(nargs);

if (pto->args == NULL) {

Py_DECREF(pto);

return NULL;

}

assert(PyTuple_Check(pto->args));

}

if (pkw == NULL || PyDict_GET_SIZE(pkw) == 0) {

if (kw == NULL) {

pto->kw = PyDict_New();

}

else if (Py_REFCNT(kw) == 1) {

Py_INCREF(kw);

pto->kw = kw;

}

else {

pto->kw = PyDict_Copy(kw);

}

}

else {

pto->kw = PyDict_Copy(pkw);

if (kw != NULL && pto->kw != NULL) {

if (PyDict_Merge(pto->kw, kw, 1) != 0) {

Py_DECREF(pto);

return NULL;

}

}

}

if (pto->kw == NULL) {

Py_DECREF(pto);

return NULL;

}

partial_setvectorcall(pto);

return (PyObject *)pto;

}

static int

partial_clear(partialobject *pto)

{

Py_CLEAR(pto->fn);

Py_CLEAR(pto->args);

Py_CLEAR(pto->kw);

Py_CLEAR(pto->dict);

return 0;

}

static int

partial_traverse(partialobject *pto, visitproc visit, void *arg)

{

Py_VISIT(Py_TYPE(pto));

Py_VISIT(pto->fn);

Py_VISIT(pto->args);

Py_VISIT(pto->kw);

Py_VISIT(pto->dict);

return 0;

}

static void

partial_dealloc(partialobject *pto)

{

PyTypeObject *tp = Py_TYPE(pto);

/* bpo-31095: UnTrack is needed before calling any callbacks */

PyObject_GC_UnTrack(pto);

if (pto->weakreflist != NULL) {

PyObject_ClearWeakRefs((PyObject *) pto);

}

(void)partial_clear(pto);

tp->tp_free(pto);

Py_DECREF(tp);

}

Py_NO_INLINE static PyObject *

partial_vectorcall_fallback(PyThreadState *tstate, partialobject *pto,

PyObject *const *args, size_t nargsf,

PyObject *kwnames)

{

pto->vectorcall = NULL;

Py_ssize_t nargs = PyVectorcall_NARGS(nargsf);

return _PyObject_MakeTpCall(tstate, (PyObject *)pto,

args, nargs, kwnames);

}

static PyObject *

partial_vectorcall(partialobject *pto, PyObject *const *args,

size_t nargsf, PyObject *kwnames)

{

PyThreadState *tstate = _PyThreadState_GET();

/* pto->kw is mutable, so need to check every time */

if (PyDict_GET_SIZE(pto->kw)) {

return partial_vectorcall_fallback(tstate, pto, args, nargsf, kwnames);

}

Py_ssize_t nargs = PyVectorcall_NARGS(nargsf);

Py_ssize_t nargs_total = nargs;

if (kwnames != NULL) {

nargs_total += PyTuple_GET_SIZE(kwnames);

}

PyObject **pto_args = _PyTuple_ITEMS(pto->args);

Py_ssize_t pto_nargs = PyTuple_GET_SIZE(pto->args);

/* Fast path if we're called without arguments */

if (nargs_total == 0) {

return _PyObject_VectorcallTstate(tstate, pto->fn,

pto_args, pto_nargs, NULL);

}

/* Fast path using PY_VECTORCALL_ARGUMENTS_OFFSET to prepend a single

if (pto_nargs == 1 && (nargsf & PY_VECTORCALL_ARGUMENTS_OFFSET)) {

PyObject **newargs = (PyObject **)args - 1;

PyObject *tmp = newargs[0];

newargs[0] = pto_args[0];

PyObject *ret = _PyObject_VectorcallTstate(tstate, pto->fn,

newargs, nargs + 1, kwnames);

newargs[0] = tmp;

return ret;

}

Py_ssize_t newnargs_total = pto_nargs + nargs_total;

PyObject *small_stack[_PY_FASTCALL_SMALL_STACK];

PyObject *ret;

PyObject **stack;

if (newnargs_total <= (Py_ssize_t)Py_ARRAY_LENGTH(small_stack)) {

stack = small_stack;

}

else {

stack = PyMem_Malloc(newnargs_total * sizeof(PyObject *));

if (stack == NULL) {

PyErr_NoMemory();

return NULL;

}

}

/* Copy to new stack, using borrowed references */

memcpy(stack, pto_args, pto_nargs * sizeof(PyObject*));

memcpy(stack + pto_nargs, args, nargs_total * sizeof(PyObject*));

ret = _PyObject_VectorcallTstate(tstate, pto->fn,

stack, pto_nargs + nargs, kwnames);

if (stack != small_stack) {

PyMem_Free(stack);

}

return ret;

}

static void

partial_setvectorcall(partialobject *pto)

{

if (_PyVectorcall_Function(pto->fn) == NULL) {

/* Don't use vectorcall if the underlying function doesn't support it */

pto->vectorcall = NULL;

}

/* We could have a special case if there are no arguments,

else {

pto->vectorcall = (vectorcallfunc)partial_vectorcall;

}

}

static PyObject *

partial_call(partialobject *pto, PyObject *args, PyObject *kwargs)

{

assert(PyCallable_Check(pto->fn));

assert(PyTuple_Check(pto->args));

assert(PyDict_Check(pto->kw));

/* Merge keywords */

PyObject *kwargs2;

if (PyDict_GET_SIZE(pto->kw) == 0) {

/* kwargs can be NULL */

kwargs2 = kwargs;

Py_XINCREF(kwargs2);

}

else {

/* bpo-27840, bpo-29318: dictionary of keyword parameters must be

kwargs2 = PyDict_Copy(pto->kw);

if (kwargs2 == NULL) {

return NULL;

}

if (kwargs != NULL) {

if (PyDict_Merge(kwargs2, kwargs, 1) != 0) {

Py_DECREF(kwargs2);

return NULL;

}

}

}

/* Merge positional arguments */

/* Note: tupleconcat() is optimized for empty tuples */

PyObject *args2 = PySequence_Concat(pto->args, args);

if (args2 == NULL) {

Py_XDECREF(kwargs2);

return NULL;

}

PyObject *res = PyObject_Call(pto->fn, args2, kwargs2);

Py_DECREF(args2);

Py_XDECREF(kwargs2);

return res;

}

PyDoc_STRVAR(partial_doc,

of the given arguments and keywords.\n");

#define OFF(x) offsetof(partialobject, x)

static PyMemberDef partial_memberlist[] = {

{"func", T_OBJECT, OFF(fn), READONLY,

"function object to use in future partial calls"},

{"args", T_OBJECT, OFF(args), READONLY,

"tuple of arguments to future partial calls"},

{"keywords", T_OBJECT, OFF(kw), READONLY,

"dictionary of keyword arguments to future partial calls"},

{"__weaklistoffset__", T_PYSSIZET,

offsetof(partialobject, weakreflist), READONLY},

{"__dictoffset__", T_PYSSIZET,

offsetof(partialobject, dict), READONLY},

{"__vectorcalloffset__", T_PYSSIZET,

offsetof(partialobject, vectorcall), READONLY},

{NULL} /* Sentinel */

};

static PyGetSetDef partial_getsetlist[] = {

{"__dict__", PyObject_GenericGetDict, PyObject_GenericSetDict},

{NULL} /* Sentinel */

};

static PyObject *

partial_repr(partialobject *pto)

{

PyObject *result = NULL;

PyObject *arglist;

Py_ssize_t i, n;

PyObject *key, *value;

int status;

status = Py_ReprEnter((PyObject *)pto);

if (status != 0) {

if (status < 0)

return NULL;

return PyUnicode_FromString("...");

}

arglist = PyUnicode_FromString("");

if (arglist == NULL)

goto done;

/* Pack positional arguments */

assert (PyTuple_Check(pto->args));

n = PyTuple_GET_SIZE(pto->args);

for (i = 0; i < n; i++) {

Py_SETREF(arglist, PyUnicode_FromFormat("%U, %R", arglist,

PyTuple_GET_ITEM(pto->args, i)));

if (arglist == NULL)

goto done;

}

/* Pack keyword arguments */

assert (PyDict_Check(pto->kw));

for (i = 0; PyDict_Next(pto->kw, &i, &key, &value);) {

/* Prevent key.__str__ from deleting the value. */

Py_INCREF(value);

Py_SETREF(arglist, PyUnicode_FromFormat("%U, %S=%R", arglist,

key, value));

Py_DECREF(value);

if (arglist == NULL)

goto done;

}

result = PyUnicode_FromFormat("%s(%R%U)", Py_TYPE(pto)->tp_name,

pto->fn, arglist);

Py_DECREF(arglist);

done:

Py_ReprLeave((PyObject *)pto);

return result;

}

static PyObject *

partial_reduce(partialobject *pto, PyObject *unused)

{

return Py_BuildValue("O(O)(OOOO)", Py_TYPE(pto), pto->fn, pto->fn,

pto->args, pto->kw,

pto->dict ? pto->dict : Py_None);

}

static PyObject *

partial_setstate(partialobject *pto, PyObject *state)

{

PyObject *fn, *fnargs, *kw, *dict;

if (!PyTuple_Check(state) ||

!PyArg_ParseTuple(state, "OOOO", &fn, &fnargs, &kw, &dict) ||

!PyCallable_Check(fn) ||

!PyTuple_Check(fnargs) ||

(kw != Py_None && !PyDict_Check(kw)))

{

PyErr_SetString(PyExc_TypeError, "invalid partial state");

return NULL;

}

if(!PyTuple_CheckExact(fnargs))

fnargs = PySequence_Tuple(fnargs);

else

Py_INCREF(fnargs);

if (fnargs == NULL)

return NULL;

if (kw == Py_None)

kw = PyDict_New();

else if(!PyDict_CheckExact(kw))

kw = PyDict_Copy(kw);

else

Py_INCREF(kw);

if (kw == NULL) {

Py_DECREF(fnargs);

return NULL;

}

if (dict == Py_None)

dict = NULL;

else

Py_INCREF(dict);

Py_INCREF(fn);

Py_SETREF(pto->fn, fn);

Py_SETREF(pto->args, fnargs);

Py_SETREF(pto->kw, kw);

Py_XSETREF(pto->dict, dict);

partial_setvectorcall(pto);

Py_RETURN_NONE;

}

static PyMethodDef partial_methods[] = {

{"__reduce__", (PyCFunction)partial_reduce, METH_NOARGS},

{"__setstate__", (PyCFunction)partial_setstate, METH_O},

{"__class_getitem__", Py_GenericAlias,

METH_O|METH_CLASS, PyDoc_STR("See PEP 585")},

{NULL, NULL} /* sentinel */

};

static PyType_Slot partial_type_slots[] = {

{Py_tp_dealloc, partial_dealloc},

{Py_tp_repr, partial_repr},

{Py_tp_call, partial_call},

{Py_tp_getattro, PyObject_GenericGetAttr},

{Py_tp_setattro, PyObject_GenericSetAttr},

{Py_tp_doc, (void *)partial_doc},

{Py_tp_traverse, partial_traverse},

{Py_tp_clear, partial_clear},

{Py_tp_methods, partial_methods},

{Py_tp_members, partial_memberlist},

{Py_tp_getset, partial_getsetlist},

{Py_tp_new, partial_new},

{Py_tp_free, PyObject_GC_Del},

{0, 0}

};

static PyType_Spec partial_type_spec = {

.name = "functools.partial",

.basicsize = sizeof(partialobject),

.flags = Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC |

Py_TPFLAGS_BASETYPE | Py_TPFLAGS_HAVE_VECTORCALL |

Py_TPFLAGS_IMMUTABLETYPE,

.slots = partial_type_slots

};

typedef struct {

PyObject_HEAD

PyObject *cmp;

PyObject *object;

} keyobject;

static int

keyobject_clear(keyobject *ko)

{

Py_CLEAR(ko->cmp);

Py_CLEAR(ko->object);

return 0;

}

static void

keyobject_dealloc(keyobject *ko)

{

PyTypeObject *tp = Py_TYPE(ko);

PyObject_GC_UnTrack(ko);

(void)keyobject_clear(ko);

tp->tp_free(ko);

Py_DECREF(tp);

}

static int

keyobject_traverse(keyobject *ko, visitproc visit, void *arg)

{

Py_VISIT(Py_TYPE(ko));

Py_VISIT(ko->cmp);

Py_VISIT(ko->object);

return 0;

}

static PyMemberDef keyobject_members[] = {

{"obj", T_OBJECT,

offsetof(keyobject, object), 0,

PyDoc_STR("Value wrapped by a key function.")},

{NULL}

};

static PyObject *

keyobject_call(keyobject *ko, PyObject *args, PyObject *kwds);

static PyObject *

keyobject_richcompare(PyObject *ko, PyObject *other, int op);

static PyType_Slot keyobject_type_slots[] = {

{Py_tp_dealloc, keyobject_dealloc},

{Py_tp_call, keyobject_call},

{Py_tp_getattro, PyObject_GenericGetAttr},

{Py_tp_traverse, keyobject_traverse},

{Py_tp_clear, keyobject_clear},

{Py_tp_richcompare, keyobject_richcompare},

{Py_tp_members, keyobject_members},

{0, 0}

};

static PyType_Spec keyobject_type_spec = {

.name = "functools.KeyWrapper",

.basicsize = sizeof(keyobject),

.flags = (Py_TPFLAGS_DEFAULT | Py_TPFLAGS_DISALLOW_INSTANTIATION |

Py_TPFLAGS_HAVE_GC | Py_TPFLAGS_IMMUTABLETYPE),

.slots = keyobject_type_slots

};

static PyObject *

keyobject_call(keyobject *ko, PyObject *args, PyObject *kwds)

{

PyObject *object;

keyobject *result;

static char *kwargs[] = {"obj", NULL};

if (!PyArg_ParseTupleAndKeywords(args, kwds, "O:K", kwargs, &object))

return NULL;

result = PyObject_GC_New(keyobject, Py_TYPE(ko));

if (result == NULL) {

return NULL;

}

Py_INCREF(ko->cmp);

result->cmp = ko->cmp;

Py_INCREF(object);

result->object = object;

PyObject_GC_Track(result);

return (PyObject *)result;

}

static PyObject *

keyobject_richcompare(PyObject *ko, PyObject *other, int op)

{

PyObject *res;

PyObject *x;

PyObject *y;

PyObject *compare;

PyObject *answer;

PyObject* stack[2];

if (!Py_IS_TYPE(other, Py_TYPE(ko))) {

PyErr_Format(PyExc_TypeError, "other argument must be K instance");

return NULL;

}

compare = ((keyobject *) ko)->cmp;

assert(compare != NULL);

x = ((keyobject *) ko)->object;

y = ((keyobject *) other)->object;

if (!x || !y){

PyErr_Format(PyExc_AttributeError, "object");

return NULL;

}

/* Call the user's comparison function and translate the 3-way

stack[0] = x;

stack[1] = y;

res = _PyObject_FastCall(compare, stack, 2);

if (res == NULL) {

return NULL;

}

answer = PyObject_RichCompare(res, _PyLong_GetZero(), op);

Py_DECREF(res);

return answer;

}

static PyObject *

_functools_cmp_to_key_impl(PyObject *module, PyObject *mycmp)

{

keyobject *object;

_functools_state *state;

state = get_functools_state(module);

object = PyObject_GC_New(keyobject, state->keyobject_type);

if (!object)

return NULL;

Py_INCREF(mycmp);

object->cmp = mycmp;

object->object = NULL;

PyObject_GC_Track(object);

return (PyObject *)object;

}

static PyObject *

functools_reduce(PyObject *self, PyObject *args)

{

PyObject *seq, *func, *result = NULL, *it;

if (!PyArg_UnpackTuple(args, "reduce", 2, 3, &func, &seq, &result))

return NULL;

if (result != NULL)

Py_INCREF(result);

it = PyObject_GetIter(seq);

if (it == NULL) {

if (PyErr_ExceptionMatches(PyExc_TypeError))

PyErr_SetString(PyExc_TypeError,

"reduce() arg 2 must support iteration");

Py_XDECREF(result);

return NULL;

}

if ((args = PyTuple_New(2)) == NULL)

goto Fail;

for (;;) {

PyObject *op2;

if (Py_REFCNT(args) > 1) {

Py_DECREF(args);

if ((args = PyTuple_New(2)) == NULL)

goto Fail;

}

op2 = PyIter_Next(it);

if (op2 == NULL) {

if (PyErr_Occurred())

goto Fail;

break;

}

if (result == NULL)

result = op2;

else {

/* Update the args tuple in-place */

assert(Py_REFCNT(args) == 1);

Py_XSETREF(_PyTuple_ITEMS(args)[0], result);

Py_XSETREF(_PyTuple_ITEMS(args)[1], op2);

if ((result = PyObject_Call(func, args, NULL)) == NULL) {

goto Fail;

}

// bpo-42536: The GC may have untracked this args tuple. Since we're

// recycling it, make sure it's tracked again:

if (!_PyObject_GC_IS_TRACKED(args)) {

_PyObject_GC_TRACK(args);

}

}

}

Py_DECREF(args);

if (result == NULL)

PyErr_SetString(PyExc_TypeError,

"reduce() of empty iterable with no initial value");

Py_DECREF(it);

return result;

Fail:

Py_XDECREF(args);

Py_XDECREF(result);

Py_DECREF(it);

return NULL;

}

PyDoc_STRVAR(functools_reduce_doc,

iterable is empty.");

struct lru_list_elem;

struct lru_cache_object;

typedef struct lru_list_elem {

} lru_list_elem;

static void

lru_list_elem_dealloc(lru_list_elem *link)

{

PyTypeObject *tp = Py_TYPE(link);

Py_XDECREF(link->key);

Py_XDECREF(link->result);

tp->tp_free(link);

Py_DECREF(tp);

}

static PyType_Slot lru_list_elem_type_slots[] = {

{Py_tp_dealloc, lru_list_elem_dealloc},

{0, 0}

};

static PyType_Spec lru_list_elem_type_spec = {

.name = "functools._lru_list_elem",

.basicsize = sizeof(lru_list_elem),

.flags = Py_TPFLAGS_DEFAULT | Py_TPFLAGS_DISALLOW_INSTANTIATION |

Py_TPFLAGS_IMMUTABLETYPE,

.slots = lru_list_elem_type_slots

};

typedef PyObject *(*lru_cache_ternaryfunc)(struct lru_cache_object *, PyObject *, PyObject *);

typedef struct lru_cache_object {

} lru_cache_object;

static PyObject *

lru_cache_make_key(PyObject *kwd_mark, PyObject *args,

PyObject *kwds, int typed)

{

PyObject *key, *keyword, *value;

Py_ssize_t key_size, pos, key_pos, kwds_size;

kwds_size = kwds ? PyDict_GET_SIZE(kwds) : 0;

/* short path, key will match args anyway, which is a tuple */

if (!typed && !kwds_size) {

if (PyTuple_GET_SIZE(args) == 1) {

key = PyTuple_GET_ITEM(args, 0);

if (PyUnicode_CheckExact(key) || PyLong_CheckExact(key)) {

/* For common scalar keys, save space by

Py_INCREF(key);

return key;

}

}

Py_INCREF(args);

return args;

}

key_size = PyTuple_GET_SIZE(args);

if (kwds_size)

key_size += kwds_size * 2 + 1;

if (typed)

key_size += PyTuple_GET_SIZE(args) + kwds_size;

key = PyTuple_New(key_size);

if (key == NULL)

return NULL;

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 (kwds_size) {

Py_INCREF(kwd_mark);

PyTuple_SET_ITEM(key, key_pos++, kwd_mark);

for (pos = 0; PyDict_Next(kwds, &pos, &keyword, &value);) {

Py_INCREF(keyword);

PyTuple_SET_ITEM(key, key_pos++, keyword);

Py_INCREF(value);

PyTuple_SET_ITEM(key, key_pos++, value);

}

assert(key_pos == PyTuple_GET_SIZE(args) + kwds_size * 2 + 1);

}

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 (kwds_size) {

for (pos = 0; PyDict_Next(kwds, &pos, &keyword, &value);) {

PyObject *item = (PyObject *)Py_TYPE(value);

Py_INCREF(item);

PyTuple_SET_ITEM(key, key_pos++, item);

}

}

}

assert(key_pos == key_size);

return key;

}

static PyObject *

uncached_lru_cache_wrapper(lru_cache_object *self, PyObject *args, PyObject *kwds)

{

PyObject *result;

self->misses++;

result = PyObject_Call(self->func, args, kwds);

if (!result)

return NULL;

return result;

}

static PyObject *

infinite_lru_cache_wrapper(lru_cache_object *self, PyObject *args, PyObject *kwds)

{

PyObject *result;

Py_hash_t hash;

PyObject *key = lru_cache_make_key(self->kwd_mark, args, kwds, self->typed);

if (!key)

return NULL;

hash = PyObject_Hash(key);

if (hash == -1) {

Py_DECREF(key);

return NULL;

}

result = _PyDict_GetItem_KnownHash(self->cache, key, hash);

if (result) {

Py_INCREF(result);

self->hits++;

Py_DECREF(key);

return result;

}

if (PyErr_Occurred()) {

Py_DECREF(key);

return NULL;

}

self->misses++;

result = PyObject_Call(self->func, args, kwds);

if (!result) {

Py_DECREF(key);

return NULL;

}

if (_PyDict_SetItem_KnownHash(self->cache, key, result, hash) < 0) {

Py_DECREF(result);

Py_DECREF(key);

return NULL;

}

Py_DECREF(key);

return result;

}

static void

lru_cache_extract_link(lru_list_elem *link)

{

lru_list_elem *link_prev = link->prev;

lru_list_elem *link_next = link->next;

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 void

lru_cache_prepend_link(lru_cache_object *self, lru_list_elem *link)

{

lru_list_elem *root = &self->root;

lru_list_elem *first = root->next;

first->prev = root->next = link;

link->prev = root;

link->next = first;

}