Python code coverage for Modules/_functoolsmodule.c

#	count	content
1	n/a
2	n/a	#include "Python.h"
3	n/a	#include "structmember.h"
4	n/a
5	n/a	/* _functools module written and maintained
6	n/a	by Hye-Shik Chang <perky@FreeBSD.org>
7	n/a	with adaptations by Raymond Hettinger <python@rcn.com>
8	n/a	Copyright (c) 2004, 2005, 2006 Python Software Foundation.
9	n/a	All rights reserved.
10	n/a	*/
11	n/a
12	n/a	/* partial object **********************************************************/
13	n/a
14	n/a	typedef struct {
15	n/a	PyObject_HEAD
16	n/a	PyObject *fn;
17	n/a	PyObject *args;
18	n/a	PyObject *kw;
19	n/a	PyObject *dict;
20	n/a	PyObject weakreflist; / List of weak references */
21	n/a	} partialobject;
22	n/a
23	n/a	static PyTypeObject partial_type;
24	n/a
25	n/a	static PyObject *
26	n/a	partial_new(PyTypeObject type, PyObject args, PyObject *kw)
27	n/a	{
28	n/a	PyObject func, pargs, nargs, pkw;
29	n/a	partialobject *pto;
30	n/a
31	n/a	if (PyTuple_GET_SIZE(args) < 1) {
32	n/a	PyErr_SetString(PyExc_TypeError,
33	n/a	"type 'partial' takes at least one argument");
34	n/a	return NULL;
35	n/a	}
36	n/a
37	n/a	pargs = pkw = NULL;
38	n/a	func = PyTuple_GET_ITEM(args, 0);
39	n/a	if (Py_TYPE(func) == &partial_type && type == &partial_type) {
40	n/a	partialobject part = (partialobject )func;
41	n/a	if (part->dict == NULL) {
42	n/a	pargs = part->args;
43	n/a	pkw = part->kw;
44	n/a	func = part->fn;
45	n/a	assert(PyTuple_Check(pargs));
46	n/a	assert(PyDict_Check(pkw));
47	n/a	}
48	n/a	}
49	n/a	if (!PyCallable_Check(func)) {
50	n/a	PyErr_SetString(PyExc_TypeError,
51	n/a	"the first argument must be callable");
52	n/a	return NULL;
53	n/a	}
54	n/a
55	n/a	/* create partialobject structure */
56	n/a	pto = (partialobject *)type->tp_alloc(type, 0);
57	n/a	if (pto == NULL)
58	n/a	return NULL;
59	n/a
60	n/a	pto->fn = func;
61	n/a	Py_INCREF(func);
62	n/a
63	n/a	nargs = PyTuple_GetSlice(args, 1, PY_SSIZE_T_MAX);
64	n/a	if (nargs == NULL) {
65	n/a	Py_DECREF(pto);
66	n/a	return NULL;
67	n/a	}
68	n/a	if (pargs == NULL \|\| PyTuple_GET_SIZE(pargs) == 0) {
69	n/a	pto->args = nargs;
70	n/a	Py_INCREF(nargs);
71	n/a	}
72	n/a	else if (PyTuple_GET_SIZE(nargs) == 0) {
73	n/a	pto->args = pargs;
74	n/a	Py_INCREF(pargs);
75	n/a	}
76	n/a	else {
77	n/a	pto->args = PySequence_Concat(pargs, nargs);
78	n/a	if (pto->args == NULL) {
79	n/a	Py_DECREF(nargs);
80	n/a	Py_DECREF(pto);
81	n/a	return NULL;
82	n/a	}
83	n/a	assert(PyTuple_Check(pto->args));
84	n/a	}
85	n/a	Py_DECREF(nargs);
86	n/a
87	n/a	if (pkw == NULL \|\| PyDict_GET_SIZE(pkw) == 0) {
88	n/a	if (kw == NULL) {
89	n/a	pto->kw = PyDict_New();
90	n/a	}
91	n/a	else {
92	n/a	Py_INCREF(kw);
93	n/a	pto->kw = kw;
94	n/a	}
95	n/a	}
96	n/a	else {
97	n/a	pto->kw = PyDict_Copy(pkw);
98	n/a	if (kw != NULL && pto->kw != NULL) {
99	n/a	if (PyDict_Merge(pto->kw, kw, 1) != 0) {
100	n/a	Py_DECREF(pto);
101	n/a	return NULL;
102	n/a	}
103	n/a	}
104	n/a	}
105	n/a	if (pto->kw == NULL) {
106	n/a	Py_DECREF(pto);
107	n/a	return NULL;
108	n/a	}
109	n/a
110	n/a	return (PyObject *)pto;
111	n/a	}
112	n/a
113	n/a	static void
114	n/a	partial_dealloc(partialobject *pto)
115	n/a	{
116	n/a	PyObject_GC_UnTrack(pto);
117	n/a	if (pto->weakreflist != NULL)
118	n/a	PyObject_ClearWeakRefs((PyObject *) pto);
119	n/a	Py_XDECREF(pto->fn);
120	n/a	Py_XDECREF(pto->args);
121	n/a	Py_XDECREF(pto->kw);
122	n/a	Py_XDECREF(pto->dict);
123	n/a	Py_TYPE(pto)->tp_free(pto);
124	n/a	}
125	n/a
126	n/a	static PyObject *
127	n/a	partial_call(partialobject pto, PyObject args, PyObject *kw)
128	n/a	{
129	n/a	PyObject *ret;
130	n/a	PyObject argappl, kwappl;
131	n/a	PyObject **stack;
132	n/a	Py_ssize_t nargs;
133	n/a
134	n/a	assert (PyCallable_Check(pto->fn));
135	n/a	assert (PyTuple_Check(pto->args));
136	n/a	assert (PyDict_Check(pto->kw));
137	n/a
138	n/a	if (PyTuple_GET_SIZE(pto->args) == 0) {
139	n/a	stack = &PyTuple_GET_ITEM(args, 0);
140	n/a	nargs = PyTuple_GET_SIZE(args);
141	n/a	argappl = NULL;
142	n/a	}
143	n/a	else if (PyTuple_GET_SIZE(args) == 0) {
144	n/a	stack = &PyTuple_GET_ITEM(pto->args, 0);
145	n/a	nargs = PyTuple_GET_SIZE(pto->args);
146	n/a	argappl = NULL;
147	n/a	}
148	n/a	else {
149	n/a	stack = NULL;
150	n/a	argappl = PySequence_Concat(pto->args, args);
151	n/a	if (argappl == NULL) {
152	n/a	return NULL;
153	n/a	}
154	n/a
155	n/a	assert(PyTuple_Check(argappl));
156	n/a	}
157	n/a
158	n/a	if (PyDict_GET_SIZE(pto->kw) == 0) {
159	n/a	kwappl = kw;
160	n/a	Py_XINCREF(kwappl);
161	n/a	}
162	n/a	else {
163	n/a	kwappl = PyDict_Copy(pto->kw);
164	n/a	if (kwappl == NULL) {
165	n/a	Py_XDECREF(argappl);
166	n/a	return NULL;
167	n/a	}
168	n/a
169	n/a	if (kw != NULL) {
170	n/a	if (PyDict_Merge(kwappl, kw, 1) != 0) {
171	n/a	Py_XDECREF(argappl);
172	n/a	Py_DECREF(kwappl);
173	n/a	return NULL;
174	n/a	}
175	n/a	}
176	n/a	}
177	n/a
178	n/a	if (stack) {
179	n/a	ret = _PyObject_FastCallDict(pto->fn, stack, nargs, kwappl);
180	n/a	}
181	n/a	else {
182	n/a	ret = PyObject_Call(pto->fn, argappl, kwappl);
183	n/a	Py_DECREF(argappl);
184	n/a	}
185	n/a	Py_XDECREF(kwappl);
186	n/a	return ret;
187	n/a	}
188	n/a
189	n/a	static int
190	n/a	partial_traverse(partialobject pto, visitproc visit, void arg)
191	n/a	{
192	n/a	Py_VISIT(pto->fn);
193	n/a	Py_VISIT(pto->args);
194	n/a	Py_VISIT(pto->kw);
195	n/a	Py_VISIT(pto->dict);
196	n/a	return 0;
197	n/a	}
198	n/a
199	n/a	PyDoc_STRVAR(partial_doc,
200	n/a	"partial(func, args, *keywords) - new function with partial application\n\
201	n/a	of the given arguments and keywords.\n");
202	n/a
203	n/a	#define OFF(x) offsetof(partialobject, x)
204	n/a	static PyMemberDef partial_memberlist[] = {
205	n/a	{"func", T_OBJECT, OFF(fn), READONLY,
206	n/a	"function object to use in future partial calls"},
207	n/a	{"args", T_OBJECT, OFF(args), READONLY,
208	n/a	"tuple of arguments to future partial calls"},
209	n/a	{"keywords", T_OBJECT, OFF(kw), READONLY,
210	n/a	"dictionary of keyword arguments to future partial calls"},
211	n/a	{NULL} /* Sentinel */
212	n/a	};
213	n/a
214	n/a	static PyGetSetDef partial_getsetlist[] = {
215	n/a	{"__dict__", PyObject_GenericGetDict, PyObject_GenericSetDict},
216	n/a	{NULL} /* Sentinel */
217	n/a	};
218	n/a
219	n/a	static PyObject *
220	n/a	partial_repr(partialobject *pto)
221	n/a	{
222	n/a	PyObject *result = NULL;
223	n/a	PyObject *arglist;
224	n/a	Py_ssize_t i, n;
225	n/a	PyObject key, value;
226	n/a	int status;
227	n/a
228	n/a	status = Py_ReprEnter((PyObject *)pto);
229	n/a	if (status != 0) {
230	n/a	if (status < 0)
231	n/a	return NULL;
232	n/a	return PyUnicode_FromString("...");
233	n/a	}
234	n/a
235	n/a	arglist = PyUnicode_FromString("");
236	n/a	if (arglist == NULL)
237	n/a	goto done;
238	n/a	/* Pack positional arguments */
239	n/a	assert (PyTuple_Check(pto->args));
240	n/a	n = PyTuple_GET_SIZE(pto->args);
241	n/a	for (i = 0; i < n; i++) {
242	n/a	Py_SETREF(arglist, PyUnicode_FromFormat("%U, %R", arglist,
243	n/a	PyTuple_GET_ITEM(pto->args, i)));
244	n/a	if (arglist == NULL)
245	n/a	goto done;
246	n/a	}
247	n/a	/* Pack keyword arguments */
248	n/a	assert (PyDict_Check(pto->kw));
249	n/a	for (i = 0; PyDict_Next(pto->kw, &i, &key, &value);) {
250	n/a	Py_SETREF(arglist, PyUnicode_FromFormat("%U, %U=%R", arglist,
251	n/a	key, value));
252	n/a	if (arglist == NULL)
253	n/a	goto done;
254	n/a	}
255	n/a	result = PyUnicode_FromFormat("%s(%R%U)", Py_TYPE(pto)->tp_name,
256	n/a	pto->fn, arglist);
257	n/a	Py_DECREF(arglist);
258	n/a
259	n/a	done:
260	n/a	Py_ReprLeave((PyObject *)pto);
261	n/a	return result;
262	n/a	}
263	n/a
264	n/a	/* Pickle strategy:
265	n/a	__reduce__ by itself doesn't support getting kwargs in the unpickle
266	n/a	operation so we define a __setstate__ that replaces all the information
267	n/a	about the partial. If we only replaced part of it someone would use
268	n/a	it as a hook to do strange things.
269	n/a	*/
270	n/a
271	n/a	static PyObject *
272	n/a	partial_reduce(partialobject pto, PyObject unused)
273	n/a	{
274	n/a	return Py_BuildValue("O(O)(OOOO)", Py_TYPE(pto), pto->fn, pto->fn,
275	n/a	pto->args, pto->kw,
276	n/a	pto->dict ? pto->dict : Py_None);
277	n/a	}
278	n/a
279	n/a	static PyObject *
280	n/a	partial_setstate(partialobject pto, PyObject state)
281	n/a	{
282	n/a	PyObject fn, fnargs, kw, dict;
283	n/a
284	n/a	if (!PyTuple_Check(state) \|\|
285	n/a	!PyArg_ParseTuple(state, "OOOO", &fn, &fnargs, &kw, &dict) \|\|
286	n/a	!PyCallable_Check(fn) \|\|
287	n/a	!PyTuple_Check(fnargs) \|\|
288	n/a	(kw != Py_None && !PyDict_Check(kw)))
289	n/a	{
290	n/a	PyErr_SetString(PyExc_TypeError, "invalid partial state");
291	n/a	return NULL;
292	n/a	}
293	n/a
294	n/a	if(!PyTuple_CheckExact(fnargs))
295	n/a	fnargs = PySequence_Tuple(fnargs);
296	n/a	else
297	n/a	Py_INCREF(fnargs);
298	n/a	if (fnargs == NULL)
299	n/a	return NULL;
300	n/a
301	n/a	if (kw == Py_None)
302	n/a	kw = PyDict_New();
303	n/a	else if(!PyDict_CheckExact(kw))
304	n/a	kw = PyDict_Copy(kw);
305	n/a	else
306	n/a	Py_INCREF(kw);
307	n/a	if (kw == NULL) {
308	n/a	Py_DECREF(fnargs);
309	n/a	return NULL;
310	n/a	}
311	n/a
312	n/a	Py_INCREF(fn);
313	n/a	if (dict == Py_None)
314	n/a	dict = NULL;
315	n/a	else
316	n/a	Py_INCREF(dict);
317	n/a
318	n/a	Py_SETREF(pto->fn, fn);
319	n/a	Py_SETREF(pto->args, fnargs);
320	n/a	Py_SETREF(pto->kw, kw);
321	n/a	Py_XSETREF(pto->dict, dict);
322	n/a	Py_RETURN_NONE;
323	n/a	}
324	n/a
325	n/a	static PyMethodDef partial_methods[] = {
326	n/a	{"__reduce__", (PyCFunction)partial_reduce, METH_NOARGS},
327	n/a	{"__setstate__", (PyCFunction)partial_setstate, METH_O},
328	n/a	{NULL, NULL} /* sentinel */
329	n/a	};
330	n/a
331	n/a	static PyTypeObject partial_type = {
332	n/a	PyVarObject_HEAD_INIT(NULL, 0)
333	n/a	"functools.partial", /* tp_name */
334	n/a	sizeof(partialobject), /* tp_basicsize */
335	n/a	0, /* tp_itemsize */
336	n/a	/* methods */
337	n/a	(destructor)partial_dealloc, /* tp_dealloc */
338	n/a	0, /* tp_print */
339	n/a	0, /* tp_getattr */
340	n/a	0, /* tp_setattr */
341	n/a	0, /* tp_reserved */
342	n/a	(reprfunc)partial_repr, /* tp_repr */
343	n/a	0, /* tp_as_number */
344	n/a	0, /* tp_as_sequence */
345	n/a	0, /* tp_as_mapping */
346	n/a	0, /* tp_hash */
347	n/a	(ternaryfunc)partial_call, /* tp_call */
348	n/a	0, /* tp_str */
349	n/a	PyObject_GenericGetAttr, /* tp_getattro */
350	n/a	PyObject_GenericSetAttr, /* tp_setattro */
351	n/a	0, /* tp_as_buffer */
352	n/a	Py_TPFLAGS_DEFAULT \| Py_TPFLAGS_HAVE_GC \|
353	n/a	Py_TPFLAGS_BASETYPE, /* tp_flags */
354	n/a	partial_doc, /* tp_doc */
355	n/a	(traverseproc)partial_traverse, /* tp_traverse */
356	n/a	0, /* tp_clear */
357	n/a	0, /* tp_richcompare */
358	n/a	offsetof(partialobject, weakreflist), /* tp_weaklistoffset */
359	n/a	0, /* tp_iter */
360	n/a	0, /* tp_iternext */
361	n/a	partial_methods, /* tp_methods */
362	n/a	partial_memberlist, /* tp_members */
363	n/a	partial_getsetlist, /* tp_getset */
364	n/a	0, /* tp_base */
365	n/a	0, /* tp_dict */
366	n/a	0, /* tp_descr_get */
367	n/a	0, /* tp_descr_set */
368	n/a	offsetof(partialobject, dict), /* tp_dictoffset */
369	n/a	0, /* tp_init */
370	n/a	0, /* tp_alloc */
371	n/a	partial_new, /* tp_new */
372	n/a	PyObject_GC_Del, /* tp_free */
373	n/a	};
374	n/a
375	n/a
376	n/a	/* cmp_to_key ***************************************************************/
377	n/a
378	n/a	typedef struct {
379	n/a	PyObject_HEAD
380	n/a	PyObject *cmp;
381	n/a	PyObject *object;
382	n/a	} keyobject;
383	n/a
384	n/a	static void
385	n/a	keyobject_dealloc(keyobject *ko)
386	n/a	{
387	n/a	Py_DECREF(ko->cmp);
388	n/a	Py_XDECREF(ko->object);
389	n/a	PyObject_FREE(ko);
390	n/a	}
391	n/a
392	n/a	static int
393	n/a	keyobject_traverse(keyobject ko, visitproc visit, void arg)
394	n/a	{
395	n/a	Py_VISIT(ko->cmp);
396	n/a	if (ko->object)
397	n/a	Py_VISIT(ko->object);
398	n/a	return 0;
399	n/a	}
400	n/a
401	n/a	static int
402	n/a	keyobject_clear(keyobject *ko)
403	n/a	{
404	n/a	Py_CLEAR(ko->cmp);
405	n/a	if (ko->object)
406	n/a	Py_CLEAR(ko->object);
407	n/a	return 0;
408	n/a	}
409	n/a
410	n/a	static PyMemberDef keyobject_members[] = {
411	n/a	{"obj", T_OBJECT,
412	n/a	offsetof(keyobject, object), 0,
413	n/a	PyDoc_STR("Value wrapped by a key function.")},
414	n/a	{NULL}
415	n/a	};
416	n/a
417	n/a	static PyObject *
418	n/a	keyobject_call(keyobject ko, PyObject args, PyObject *kwds);
419	n/a
420	n/a	static PyObject *
421	n/a	keyobject_richcompare(PyObject ko, PyObject other, int op);
422	n/a
423	n/a	static PyTypeObject keyobject_type = {
424	n/a	PyVarObject_HEAD_INIT(&PyType_Type, 0)
425	n/a	"functools.KeyWrapper", /* tp_name */
426	n/a	sizeof(keyobject), /* tp_basicsize */
427	n/a	0, /* tp_itemsize */
428	n/a	/* methods */
429	n/a	(destructor)keyobject_dealloc, /* tp_dealloc */
430	n/a	0, /* tp_print */
431	n/a	0, /* tp_getattr */
432	n/a	0, /* tp_setattr */
433	n/a	0, /* tp_reserved */
434	n/a	0, /* tp_repr */
435	n/a	0, /* tp_as_number */
436	n/a	0, /* tp_as_sequence */
437	n/a	0, /* tp_as_mapping */
438	n/a	0, /* tp_hash */
439	n/a	(ternaryfunc)keyobject_call, /* tp_call */
440	n/a	0, /* tp_str */
441	n/a	PyObject_GenericGetAttr, /* tp_getattro */
442	n/a	0, /* tp_setattro */
443	n/a	0, /* tp_as_buffer */
444	n/a	Py_TPFLAGS_DEFAULT, /* tp_flags */
445	n/a	0, /* tp_doc */
446	n/a	(traverseproc)keyobject_traverse, /* tp_traverse */
447	n/a	(inquiry)keyobject_clear, /* tp_clear */
448	n/a	keyobject_richcompare, /* tp_richcompare */
449	n/a	0, /* tp_weaklistoffset */
450	n/a	0, /* tp_iter */
451	n/a	0, /* tp_iternext */
452	n/a	0, /* tp_methods */
453	n/a	keyobject_members, /* tp_members */
454	n/a	0, /* tp_getset */
455	n/a	};
456	n/a
457	n/a	static PyObject *
458	n/a	keyobject_call(keyobject ko, PyObject args, PyObject *kwds)
459	n/a	{
460	n/a	PyObject *object;
461	n/a	keyobject *result;
462	n/a	static char *kwargs[] = {"obj", NULL};
463	n/a
464	n/a	if (!PyArg_ParseTupleAndKeywords(args, kwds, "O:K", kwargs, &object))
465	n/a	return NULL;
466	n/a	result = PyObject_New(keyobject, &keyobject_type);
467	n/a	if (!result)
468	n/a	return NULL;
469	n/a	Py_INCREF(ko->cmp);
470	n/a	result->cmp = ko->cmp;
471	n/a	Py_INCREF(object);
472	n/a	result->object = object;
473	n/a	return (PyObject *)result;
474	n/a	}
475	n/a
476	n/a	static PyObject *
477	n/a	keyobject_richcompare(PyObject ko, PyObject other, int op)
478	n/a	{
479	n/a	PyObject *res;
480	n/a	PyObject *x;
481	n/a	PyObject *y;
482	n/a	PyObject *compare;
483	n/a	PyObject *answer;
484	n/a	static PyObject *zero;
485	n/a	PyObject* stack[2];
486	n/a
487	n/a	if (zero == NULL) {
488	n/a	zero = PyLong_FromLong(0);
489	n/a	if (!zero)
490	n/a	return NULL;
491	n/a	}
492	n/a
493	n/a	if (Py_TYPE(other) != &keyobject_type){
494	n/a	PyErr_Format(PyExc_TypeError, "other argument must be K instance");
495	n/a	return NULL;
496	n/a	}
497	n/a	compare = ((keyobject *) ko)->cmp;
498	n/a	assert(compare != NULL);
499	n/a	x = ((keyobject *) ko)->object;
500	n/a	y = ((keyobject *) other)->object;
501	n/a	if (!x \|\| !y){
502	n/a	PyErr_Format(PyExc_AttributeError, "object");
503	n/a	return NULL;
504	n/a	}
505	n/a
506	n/a	/* Call the user's comparison function and translate the 3-way
507	n/a	* result into true or false (or error).
508	n/a	*/
509	n/a	stack[0] = x;
510	n/a	stack[1] = y;
511	n/a	res = _PyObject_FastCall(compare, stack, 2);
512	n/a	if (res == NULL) {
513	n/a	return NULL;
514	n/a	}
515	n/a
516	n/a	answer = PyObject_RichCompare(res, zero, op);
517	n/a	Py_DECREF(res);
518	n/a	return answer;
519	n/a	}
520	n/a
521	n/a	static PyObject *
522	n/a	functools_cmp_to_key(PyObject self, PyObject args, PyObject *kwds)
523	n/a	{
524	n/a	PyObject *cmp;
525	n/a	static char *kwargs[] = {"mycmp", NULL};
526	n/a	keyobject *object;
527	n/a
528	n/a	if (!PyArg_ParseTupleAndKeywords(args, kwds, "O:cmp_to_key", kwargs, &cmp))
529	n/a	return NULL;
530	n/a	object = PyObject_New(keyobject, &keyobject_type);
531	n/a	if (!object)
532	n/a	return NULL;
533	n/a	Py_INCREF(cmp);
534	n/a	object->cmp = cmp;
535	n/a	object->object = NULL;
536	n/a	return (PyObject *)object;
537	n/a	}
538	n/a
539	n/a	PyDoc_STRVAR(functools_cmp_to_key_doc,
540	n/a	"Convert a cmp= function into a key= function.");
541	n/a
542	n/a	/* reduce (used to be a builtin) ********************************************/
543	n/a
544	n/a	static PyObject *
545	n/a	functools_reduce(PyObject self, PyObject args)
546	n/a	{
547	n/a	PyObject seq, func, result = NULL, it;
548	n/a
549	n/a	if (!PyArg_UnpackTuple(args, "reduce", 2, 3, &func, &seq, &result))
550	n/a	return NULL;
551	n/a	if (result != NULL)
552	n/a	Py_INCREF(result);
553	n/a
554	n/a	it = PyObject_GetIter(seq);
555	n/a	if (it == NULL) {
556	n/a	if (PyErr_ExceptionMatches(PyExc_TypeError))
557	n/a	PyErr_SetString(PyExc_TypeError,
558	n/a	"reduce() arg 2 must support iteration");
559	n/a	Py_XDECREF(result);
560	n/a	return NULL;
561	n/a	}
562	n/a
563	n/a	if ((args = PyTuple_New(2)) == NULL)
564	n/a	goto Fail;
565	n/a
566	n/a	for (;;) {
567	n/a	PyObject *op2;
568	n/a
569	n/a	if (args->ob_refcnt > 1) {
570	n/a	Py_DECREF(args);
571	n/a	if ((args = PyTuple_New(2)) == NULL)
572	n/a	goto Fail;
573	n/a	}
574	n/a
575	n/a	op2 = PyIter_Next(it);
576	n/a	if (op2 == NULL) {
577	n/a	if (PyErr_Occurred())
578	n/a	goto Fail;
579	n/a	break;
580	n/a	}
581	n/a
582	n/a	if (result == NULL)
583	n/a	result = op2;
584	n/a	else {
585	n/a	PyTuple_SetItem(args, 0, result);
586	n/a	PyTuple_SetItem(args, 1, op2);
587	n/a	if ((result = PyEval_CallObject(func, args)) == NULL)
588	n/a	goto Fail;
589	n/a	}
590	n/a	}
591	n/a
592	n/a	Py_DECREF(args);
593	n/a
594	n/a	if (result == NULL)
595	n/a	PyErr_SetString(PyExc_TypeError,
596	n/a	"reduce() of empty sequence with no initial value");
597	n/a
598	n/a	Py_DECREF(it);
599	n/a	return result;
600	n/a
601	n/a	Fail:
602	n/a	Py_XDECREF(args);
603	n/a	Py_XDECREF(result);
604	n/a	Py_DECREF(it);
605	n/a	return NULL;
606	n/a	}
607	n/a
608	n/a	PyDoc_STRVAR(functools_reduce_doc,
609	n/a	"reduce(function, sequence[, initial]) -> value\n\
610	n/a	\n\
611	n/a	Apply a function of two arguments cumulatively to the items of a sequence,\n\
612	n/a	from left to right, so as to reduce the sequence to a single value.\n\
613	n/a	For example, reduce(lambda x, y: x+y, [1, 2, 3, 4, 5]) calculates\n\
614	n/a	((((1+2)+3)+4)+5). If initial is present, it is placed before the items\n\
615	n/a	of the sequence in the calculation, and serves as a default when the\n\
616	n/a	sequence is empty.");
617	n/a
618	n/a	/* lru_cache object **********************************************************/
619	n/a
620	n/a	/* this object is used delimit args and keywords in the cache keys */
621	n/a	static PyObject *kwd_mark = NULL;
622	n/a
623	n/a	struct lru_list_elem;
624	n/a	struct lru_cache_object;
625	n/a
626	n/a	typedef struct lru_list_elem {
627	n/a	PyObject_HEAD
628	n/a	struct lru_list_elem prev, next; /* borrowed links */
629	n/a	Py_hash_t hash;
630	n/a	PyObject key, result;
631	n/a	} lru_list_elem;
632	n/a
633	n/a	static void
634	n/a	lru_list_elem_dealloc(lru_list_elem *link)
635	n/a	{
636	n/a	_PyObject_GC_UNTRACK(link);
637	n/a	Py_XDECREF(link->key);
638	n/a	Py_XDECREF(link->result);
639	n/a	PyObject_GC_Del(link);
640	n/a	}
641	n/a
642	n/a	static int
643	n/a	lru_list_elem_traverse(lru_list_elem link, visitproc visit, void arg)
644	n/a	{
645	n/a	Py_VISIT(link->key);
646	n/a	Py_VISIT(link->result);
647	n/a	return 0;
648	n/a	}
649	n/a
650	n/a	static int
651	n/a	lru_list_elem_clear(lru_list_elem *link)
652	n/a	{
653	n/a	Py_CLEAR(link->key);
654	n/a	Py_CLEAR(link->result);
655	n/a	return 0;
656	n/a	}
657	n/a
658	n/a	static PyTypeObject lru_list_elem_type = {
659	n/a	PyVarObject_HEAD_INIT(&PyType_Type, 0)
660	n/a	"functools._lru_list_elem", /* tp_name */
661	n/a	sizeof(lru_list_elem), /* tp_basicsize */
662	n/a	0, /* tp_itemsize */
663	n/a	/* methods */
664	n/a	(destructor)lru_list_elem_dealloc, /* tp_dealloc */
665	n/a	0, /* tp_print */
666	n/a	0, /* tp_getattr */
667	n/a	0, /* tp_setattr */
668	n/a	0, /* tp_reserved */
669	n/a	0, /* tp_repr */
670	n/a	0, /* tp_as_number */
671	n/a	0, /* tp_as_sequence */
672	n/a	0, /* tp_as_mapping */
673	n/a	0, /* tp_hash */
674	n/a	0, /* tp_call */
675	n/a	0, /* tp_str */
676	n/a	0, /* tp_getattro */
677	n/a	0, /* tp_setattro */
678	n/a	0, /* tp_as_buffer */
679	n/a	Py_TPFLAGS_DEFAULT \| Py_TPFLAGS_HAVE_GC, /* tp_flags */
680	n/a	0, /* tp_doc */
681	n/a	(traverseproc)lru_list_elem_traverse, /* tp_traverse */
682	n/a	(inquiry)lru_list_elem_clear, /* tp_clear */
683	n/a	};
684	n/a
685	n/a
686	n/a	typedef PyObject (lru_cache_ternaryfunc)(struct lru_cache_object , PyObject , PyObject *);
687	n/a
688	n/a	typedef struct lru_cache_object {
689	n/a	lru_list_elem root; /* includes PyObject_HEAD */
690	n/a	Py_ssize_t maxsize;
691	n/a	PyObject *maxsize_O;
692	n/a	PyObject *func;
693	n/a	lru_cache_ternaryfunc wrapper;
694	n/a	PyObject *cache;
695	n/a	PyObject *cache_info_type;
696	n/a	Py_ssize_t misses, hits;
697	n/a	int typed;
698	n/a	PyObject *dict;
699	n/a	int full;
700	n/a	} lru_cache_object;
701	n/a
702	n/a	static PyTypeObject lru_cache_type;
703	n/a
704	n/a	static PyObject *
705	n/a	lru_cache_make_key(PyObject args, PyObject kwds, int typed)
706	n/a	{
707	n/a	PyObject key, keyword, *value;
708	n/a	Py_ssize_t key_size, pos, key_pos, kwds_size;
709	n/a
710	n/a	/* short path, key will match args anyway, which is a tuple */
711	n/a	if (!typed && !kwds) {
712	n/a	Py_INCREF(args);
713	n/a	return args;
714	n/a	}
715	n/a
716	n/a	kwds_size = kwds ? PyDict_GET_SIZE(kwds) : 0;
717	n/a	assert(kwds_size >= 0);
718	n/a
719	n/a	key_size = PyTuple_GET_SIZE(args);
720	n/a	if (kwds_size)
721	n/a	key_size += kwds_size * 2 + 1;
722	n/a	if (typed)
723	n/a	key_size += PyTuple_GET_SIZE(args) + kwds_size;
724	n/a
725	n/a	key = PyTuple_New(key_size);
726	n/a	if (key == NULL)
727	n/a	return NULL;
728	n/a
729	n/a	key_pos = 0;
730	n/a	for (pos = 0; pos < PyTuple_GET_SIZE(args); ++pos) {
731	n/a	PyObject *item = PyTuple_GET_ITEM(args, pos);
732	n/a	Py_INCREF(item);
733	n/a	PyTuple_SET_ITEM(key, key_pos++, item);
734	n/a	}
735	n/a	if (kwds_size) {
736	n/a	Py_INCREF(kwd_mark);
737	n/a	PyTuple_SET_ITEM(key, key_pos++, kwd_mark);
738	n/a	for (pos = 0; PyDict_Next(kwds, &pos, &keyword, &value);) {
739	n/a	Py_INCREF(keyword);
740	n/a	PyTuple_SET_ITEM(key, key_pos++, keyword);
741	n/a	Py_INCREF(value);
742	n/a	PyTuple_SET_ITEM(key, key_pos++, value);
743	n/a	}
744	n/a	assert(key_pos == PyTuple_GET_SIZE(args) + kwds_size * 2 + 1);
745	n/a	}
746	n/a	if (typed) {
747	n/a	for (pos = 0; pos < PyTuple_GET_SIZE(args); ++pos) {
748	n/a	PyObject item = (PyObject )Py_TYPE(PyTuple_GET_ITEM(args, pos));
749	n/a	Py_INCREF(item);
750	n/a	PyTuple_SET_ITEM(key, key_pos++, item);
751	n/a	}
752	n/a	if (kwds_size) {
753	n/a	for (pos = 0; PyDict_Next(kwds, &pos, &keyword, &value);) {
754	n/a	PyObject item = (PyObject )Py_TYPE(value);
755	n/a	Py_INCREF(item);
756	n/a	PyTuple_SET_ITEM(key, key_pos++, item);
757	n/a	}
758	n/a	}
759	n/a	}
760	n/a	assert(key_pos == key_size);
761	n/a	return key;
762	n/a	}
763	n/a
764	n/a	static PyObject *
765	n/a	uncached_lru_cache_wrapper(lru_cache_object self, PyObject args, PyObject *kwds)
766	n/a	{
767	n/a	PyObject *result = PyObject_Call(self->func, args, kwds);
768	n/a	if (!result)
769	n/a	return NULL;
770	n/a	self->misses++;
771	n/a	return result;
772	n/a	}
773	n/a
774	n/a	static PyObject *
775	n/a	infinite_lru_cache_wrapper(lru_cache_object self, PyObject args, PyObject *kwds)
776	n/a	{
777	n/a	PyObject *result;
778	n/a	Py_hash_t hash;
779	n/a	PyObject *key = lru_cache_make_key(args, kwds, self->typed);
780	n/a	if (!key)
781	n/a	return NULL;
782	n/a	hash = PyObject_Hash(key);
783	n/a	if (hash == -1) {
784	n/a	Py_DECREF(key);
785	n/a	return NULL;
786	n/a	}
787	n/a	result = _PyDict_GetItem_KnownHash(self->cache, key, hash);
788	n/a	if (result) {
789	n/a	Py_INCREF(result);
790	n/a	self->hits++;
791	n/a	Py_DECREF(key);
792	n/a	return result;
793	n/a	}
794	n/a	if (PyErr_Occurred()) {
795	n/a	Py_DECREF(key);
796	n/a	return NULL;
797	n/a	}
798	n/a	result = PyObject_Call(self->func, args, kwds);
799	n/a	if (!result) {
800	n/a	Py_DECREF(key);
801	n/a	return NULL;
802	n/a	}
803	n/a	if (_PyDict_SetItem_KnownHash(self->cache, key, result, hash) < 0) {
804	n/a	Py_DECREF(result);
805	n/a	Py_DECREF(key);
806	n/a	return NULL;
807	n/a	}
808	n/a	Py_DECREF(key);
809	n/a	self->misses++;
810	n/a	return result;
811	n/a	}
812	n/a
813	n/a	static void
814	n/a	lru_cache_extricate_link(lru_list_elem *link)
815	n/a	{
816	n/a	link->prev->next = link->next;
817	n/a	link->next->prev = link->prev;
818	n/a	}
819	n/a
820	n/a	static void
821	n/a	lru_cache_append_link(lru_cache_object self, lru_list_elem link)
822	n/a	{
823	n/a	lru_list_elem *root = &self->root;
824	n/a	lru_list_elem *last = root->prev;
825	n/a	last->next = root->prev = link;
826	n/a	link->prev = last;
827	n/a	link->next = root;
828	n/a	}
829	n/a
830	n/a	static PyObject *
831	n/a	bounded_lru_cache_wrapper(lru_cache_object self, PyObject args, PyObject *kwds)
832	n/a	{
833	n/a	lru_list_elem *link;
834	n/a	PyObject key, result;
835	n/a	Py_hash_t hash;
836	n/a
837	n/a	key = lru_cache_make_key(args, kwds, self->typed);
838	n/a	if (!key)
839	n/a	return NULL;
840	n/a	hash = PyObject_Hash(key);
841	n/a	if (hash == -1) {
842	n/a	Py_DECREF(key);
843	n/a	return NULL;
844	n/a	}
845	n/a	link = (lru_list_elem *)_PyDict_GetItem_KnownHash(self->cache, key, hash);
846	n/a	if (link) {
847	n/a	lru_cache_extricate_link(link);
848	n/a	lru_cache_append_link(self, link);
849	n/a	self->hits++;
850	n/a	result = link->result;
851	n/a	Py_INCREF(result);
852	n/a	Py_DECREF(key);
853	n/a	return result;
854	n/a	}
855	n/a	if (PyErr_Occurred()) {
856	n/a	Py_DECREF(key);
857	n/a	return NULL;
858	n/a	}
859	n/a	result = PyObject_Call(self->func, args, kwds);
860	n/a	if (!result) {
861	n/a	Py_DECREF(key);
862	n/a	return NULL;
863	n/a	}
864	n/a	if (self->full && self->root.next != &self->root) {
865	n/a	/* Use the oldest item to store the new key and result. */
866	n/a	PyObject oldkey, oldresult, *popresult;
867	n/a	/* Extricate the oldest item. */
868	n/a	link = self->root.next;
869	n/a	lru_cache_extricate_link(link);
870	n/a	/* Remove it from the cache.
871	n/a	The cache dict holds one reference to the link,
872	n/a	and the linked list holds yet one reference to it. */
873	n/a	popresult = _PyDict_Pop_KnownHash(self->cache,
874	n/a	link->key, link->hash,
875	n/a	Py_None);
876	n/a	if (popresult == Py_None) {
877	n/a	/* Getting here means that this same key was added to the
878	n/a	cache while the lock was released. Since the link
879	n/a	update is already done, we need only return the
880	n/a	computed result and update the count of misses. */
881	n/a	Py_DECREF(popresult);
882	n/a	Py_DECREF(link);
883	n/a	Py_DECREF(key);
884	n/a	}
885	n/a	else if (popresult == NULL) {
886	n/a	lru_cache_append_link(self, link);
887	n/a	Py_DECREF(key);
888	n/a	Py_DECREF(result);
889	n/a	return NULL;
890	n/a	}
891	n/a	else {
892	n/a	Py_DECREF(popresult);
893	n/a	/* Keep a reference to the old key and old result to
894	n/a	prevent their ref counts from going to zero during the
895	n/a	update. That will prevent potentially arbitrary object
896	n/a	clean-up code (i.e. __del__) from running while we're
897	n/a	still adjusting the links. */
898	n/a	oldkey = link->key;
899	n/a	oldresult = link->result;
900	n/a
901	n/a	link->hash = hash;
902	n/a	link->key = key;
903	n/a	link->result = result;
904	n/a	if (_PyDict_SetItem_KnownHash(self->cache, key, (PyObject *)link,
905	n/a	hash) < 0) {
906	n/a	Py_DECREF(link);
907	n/a	Py_DECREF(oldkey);
908	n/a	Py_DECREF(oldresult);
909	n/a	return NULL;
910	n/a	}
911	n/a	lru_cache_append_link(self, link);
912	n/a	Py_INCREF(result); /* for return */
913	n/a	Py_DECREF(oldkey);
914	n/a	Py_DECREF(oldresult);
915	n/a	}
916	n/a	} else {
917	n/a	/* Put result in a new link at the front of the queue. */
918	n/a	link = (lru_list_elem *)PyObject_GC_New(lru_list_elem,
919	n/a	&lru_list_elem_type);
920	n/a	if (link == NULL) {
921	n/a	Py_DECREF(key);
922	n/a	Py_DECREF(result);
923	n/a	return NULL;
924	n/a	}
925	n/a
926	n/a	link->hash = hash;
927	n/a	link->key = key;
928	n/a	link->result = result;
929	n/a	_PyObject_GC_TRACK(link);
930	n/a	if (_PyDict_SetItem_KnownHash(self->cache, key, (PyObject *)link,
931	n/a	hash) < 0) {
932	n/a	Py_DECREF(link);
933	n/a	return NULL;
934	n/a	}
935	n/a	lru_cache_append_link(self, link);
936	n/a	Py_INCREF(result); /* for return */
937	n/a	self->full = (PyDict_GET_SIZE(self->cache) >= self->maxsize);
938	n/a	}
939	n/a	self->misses++;
940	n/a	return result;
941	n/a	}
942	n/a
943	n/a	static PyObject *
944	n/a	lru_cache_new(PyTypeObject type, PyObject args, PyObject *kw)
945	n/a	{
946	n/a	PyObject func, maxsize_O, cache_info_type, cachedict;
947	n/a	int typed;
948	n/a	lru_cache_object *obj;
949	n/a	Py_ssize_t maxsize;
950	n/a	PyObject (wrapper)(lru_cache_object , PyObject , PyObject *);
951	n/a	static char *keywords[] = {"user_function", "maxsize", "typed",
952	n/a	"cache_info_type", NULL};
953	n/a
954	n/a	if (!PyArg_ParseTupleAndKeywords(args, kw, "OOpO:lru_cache", keywords,
955	n/a	&func, &maxsize_O, &typed,
956	n/a	&cache_info_type)) {
957	n/a	return NULL;
958	n/a	}
959	n/a
960	n/a	if (!PyCallable_Check(func)) {
961	n/a	PyErr_SetString(PyExc_TypeError,
962	n/a	"the first argument must be callable");
963	n/a	return NULL;
964	n/a	}
965	n/a
966	n/a	/* select the caching function, and make/inc maxsize_O */
967	n/a	if (maxsize_O == Py_None) {
968	n/a	wrapper = infinite_lru_cache_wrapper;
969	n/a	/* use this only to initialize lru_cache_object attribute maxsize */
970	n/a	maxsize = -1;
971	n/a	} else if (PyIndex_Check(maxsize_O)) {
972	n/a	maxsize = PyNumber_AsSsize_t(maxsize_O, PyExc_OverflowError);
973	n/a	if (maxsize == -1 && PyErr_Occurred())
974	n/a	return NULL;
975	n/a	if (maxsize == 0)
976	n/a	wrapper = uncached_lru_cache_wrapper;
977	n/a	else
978	n/a	wrapper = bounded_lru_cache_wrapper;
979	n/a	} else {
980	n/a	PyErr_SetString(PyExc_TypeError, "maxsize should be integer or None");
981	n/a	return NULL;
982	n/a	}
983	n/a
984	n/a	if (!(cachedict = PyDict_New()))
985	n/a	return NULL;
986	n/a
987	n/a	obj = (lru_cache_object *)type->tp_alloc(type, 0);
988	n/a	if (obj == NULL) {
989	n/a	Py_DECREF(cachedict);
990	n/a	return NULL;
991	n/a	}
992	n/a
993	n/a	obj->cache = cachedict;
994	n/a	obj->root.prev = &obj->root;
995	n/a	obj->root.next = &obj->root;
996	n/a	obj->maxsize = maxsize;
997	n/a	Py_INCREF(maxsize_O);
998	n/a	obj->maxsize_O = maxsize_O;
999	n/a	Py_INCREF(func);
1000	n/a	obj->func = func;
1001	n/a	obj->wrapper = wrapper;
1002	n/a	obj->misses = obj->hits = 0;
1003	n/a	obj->typed = typed;
1004	n/a	Py_INCREF(cache_info_type);
1005	n/a	obj->cache_info_type = cache_info_type;
1006	n/a
1007	n/a	return (PyObject *)obj;
1008	n/a	}
1009	n/a
1010	n/a	static lru_list_elem *
1011	n/a	lru_cache_unlink_list(lru_cache_object *self)
1012	n/a	{
1013	n/a	lru_list_elem *root = &self->root;
1014	n/a	lru_list_elem *link = root->next;
1015	n/a	if (link == root)
1016	n/a	return NULL;
1017	n/a	root->prev->next = NULL;
1018	n/a	root->next = root->prev = root;
1019	n/a	return link;
1020	n/a	}
1021	n/a
1022	n/a	static void
1023	n/a	lru_cache_clear_list(lru_list_elem *link)
1024	n/a	{
1025	n/a	while (link != NULL) {
1026	n/a	lru_list_elem *next = link->next;
1027	n/a	Py_DECREF(link);
1028	n/a	link = next;
1029	n/a	}
1030	n/a	}
1031	n/a
1032	n/a	static void
1033	n/a	lru_cache_dealloc(lru_cache_object *obj)
1034	n/a	{
1035	n/a	lru_list_elem *list = lru_cache_unlink_list(obj);
1036	n/a	Py_XDECREF(obj->maxsize_O);
1037	n/a	Py_XDECREF(obj->func);
1038	n/a	Py_XDECREF(obj->cache);
1039	n/a	Py_XDECREF(obj->dict);
1040	n/a	Py_XDECREF(obj->cache_info_type);
1041	n/a	lru_cache_clear_list(list);
1042	n/a	Py_TYPE(obj)->tp_free(obj);
1043	n/a	}
1044	n/a
1045	n/a	static PyObject *
1046	n/a	lru_cache_call(lru_cache_object self, PyObject args, PyObject *kwds)
1047	n/a	{
1048	n/a	return self->wrapper(self, args, kwds);
1049	n/a	}
1050	n/a
1051	n/a	static PyObject *
1052	n/a	lru_cache_descr_get(PyObject self, PyObject obj, PyObject *type)
1053	n/a	{
1054	n/a	if (obj == Py_None \|\| obj == NULL) {
1055	n/a	Py_INCREF(self);
1056	n/a	return self;
1057	n/a	}
1058	n/a	return PyMethod_New(self, obj);
1059	n/a	}
1060	n/a
1061	n/a	static PyObject *
1062	n/a	lru_cache_cache_info(lru_cache_object self, PyObject unused)
1063	n/a	{
1064	n/a	return PyObject_CallFunction(self->cache_info_type, "nnOn",
1065	n/a	self->hits, self->misses, self->maxsize_O,
1066	n/a	PyDict_GET_SIZE(self->cache));
1067	n/a	}
1068	n/a
1069	n/a	static PyObject *
1070	n/a	lru_cache_cache_clear(lru_cache_object self, PyObject unused)
1071	n/a	{
1072	n/a	lru_list_elem *list = lru_cache_unlink_list(self);
1073	n/a	self->hits = self->misses = 0;
1074	n/a	self->full = 0;
1075	n/a	PyDict_Clear(self->cache);
1076	n/a	lru_cache_clear_list(list);
1077	n/a	Py_RETURN_NONE;
1078	n/a	}
1079	n/a
1080	n/a	static PyObject *
1081	n/a	lru_cache_reduce(PyObject self, PyObject unused)
1082	n/a	{
1083	n/a	return PyObject_GetAttrString(self, "__qualname__");
1084	n/a	}
1085	n/a
1086	n/a	static PyObject *
1087	n/a	lru_cache_copy(PyObject self, PyObject unused)
1088	n/a	{
1089	n/a	Py_INCREF(self);
1090	n/a	return self;
1091	n/a	}
1092	n/a
1093	n/a	static PyObject *
1094	n/a	lru_cache_deepcopy(PyObject self, PyObject unused)
1095	n/a	{
1096	n/a	Py_INCREF(self);
1097	n/a	return self;
1098	n/a	}
1099	n/a
1100	n/a	static int
1101	n/a	lru_cache_tp_traverse(lru_cache_object self, visitproc visit, void arg)
1102	n/a	{
1103	n/a	lru_list_elem *link = self->root.next;
1104	n/a	while (link != &self->root) {
1105	n/a	lru_list_elem *next = link->next;
1106	n/a	Py_VISIT(link);
1107	n/a	link = next;
1108	n/a	}
1109	n/a	Py_VISIT(self->maxsize_O);
1110	n/a	Py_VISIT(self->func);
1111	n/a	Py_VISIT(self->cache);
1112	n/a	Py_VISIT(self->cache_info_type);
1113	n/a	Py_VISIT(self->dict);
1114	n/a	return 0;
1115	n/a	}
1116	n/a
1117	n/a	static int
1118	n/a	lru_cache_tp_clear(lru_cache_object *self)
1119	n/a	{
1120	n/a	lru_list_elem *list = lru_cache_unlink_list(self);
1121	n/a	Py_CLEAR(self->maxsize_O);
1122	n/a	Py_CLEAR(self->func);
1123	n/a	Py_CLEAR(self->cache);
1124	n/a	Py_CLEAR(self->cache_info_type);
1125	n/a	Py_CLEAR(self->dict);
1126	n/a	lru_cache_clear_list(list);
1127	n/a	return 0;
1128	n/a	}
1129	n/a
1130	n/a
1131	n/a	PyDoc_STRVAR(lru_cache_doc,
1132	n/a	"Create a cached callable that wraps another function.\n\
1133	n/a	\n\
1134	n/a	user_function: the function being cached\n\
1135	n/a	\n\
1136	n/a	maxsize: 0 for no caching\n\
1137	n/a	None for unlimited cache size\n\
1138	n/a	n for a bounded cache\n\
1139	n/a	\n\
1140	n/a	typed: False cache f(3) and f(3.0) as identical calls\n\
1141	n/a	True cache f(3) and f(3.0) as distinct calls\n\
1142	n/a	\n\
1143	n/a	cache_info_type: namedtuple class with the fields:\n\
1144	n/a	hits misses currsize maxsize\n"
1145	n/a	);
1146	n/a
1147	n/a	static PyMethodDef lru_cache_methods[] = {
1148	n/a	{"cache_info", (PyCFunction)lru_cache_cache_info, METH_NOARGS},
1149	n/a	{"cache_clear", (PyCFunction)lru_cache_cache_clear, METH_NOARGS},
1150	n/a	{"__reduce__", (PyCFunction)lru_cache_reduce, METH_NOARGS},
1151	n/a	{"__copy__", (PyCFunction)lru_cache_copy, METH_VARARGS},
1152	n/a	{"__deepcopy__", (PyCFunction)lru_cache_deepcopy, METH_VARARGS},
1153	n/a	{NULL}
1154	n/a	};
1155	n/a
1156	n/a	static PyGetSetDef lru_cache_getsetlist[] = {
1157	n/a	{"__dict__", PyObject_GenericGetDict, PyObject_GenericSetDict},
1158	n/a	{NULL}
1159	n/a	};
1160	n/a
1161	n/a	static PyTypeObject lru_cache_type = {
1162	n/a	PyVarObject_HEAD_INIT(NULL, 0)
1163	n/a	"functools._lru_cache_wrapper", /* tp_name */
1164	n/a	sizeof(lru_cache_object), /* tp_basicsize */
1165	n/a	0, /* tp_itemsize */
1166	n/a	/* methods */
1167	n/a	(destructor)lru_cache_dealloc, /* tp_dealloc */
1168	n/a	0, /* tp_print */
1169	n/a	0, /* tp_getattr */
1170	n/a	0, /* tp_setattr */
1171	n/a	0, /* tp_reserved */
1172	n/a	0, /* tp_repr */
1173	n/a	0, /* tp_as_number */
1174	n/a	0, /* tp_as_sequence */
1175	n/a	0, /* tp_as_mapping */
1176	n/a	0, /* tp_hash */
1177	n/a	(ternaryfunc)lru_cache_call, /* tp_call */
1178	n/a	0, /* tp_str */
1179	n/a	0, /* tp_getattro */
1180	n/a	0, /* tp_setattro */
1181	n/a	0, /* tp_as_buffer */
1182	n/a	Py_TPFLAGS_DEFAULT\|Py_TPFLAGS_BASETYPE\|Py_TPFLAGS_HAVE_GC,
1183	n/a	/* tp_flags */
1184	n/a	lru_cache_doc, /* tp_doc */
1185	n/a	(traverseproc)lru_cache_tp_traverse,/* tp_traverse */
1186	n/a	(inquiry)lru_cache_tp_clear, /* tp_clear */
1187	n/a	0, /* tp_richcompare */
1188	n/a	0, /* tp_weaklistoffset */
1189	n/a	0, /* tp_iter */
1190	n/a	0, /* tp_iternext */
1191	n/a	lru_cache_methods, /* tp_methods */
1192	n/a	0, /* tp_members */
1193	n/a	lru_cache_getsetlist, /* tp_getset */
1194	n/a	0, /* tp_base */
1195	n/a	0, /* tp_dict */
1196	n/a	lru_cache_descr_get, /* tp_descr_get */
1197	n/a	0, /* tp_descr_set */
1198	n/a	offsetof(lru_cache_object, dict), /* tp_dictoffset */
1199	n/a	0, /* tp_init */
1200	n/a	0, /* tp_alloc */
1201	n/a	lru_cache_new, /* tp_new */
1202	n/a	};
1203	n/a
1204	n/a	/* module level code ********************************************************/
1205	n/a
1206	n/a	PyDoc_STRVAR(module_doc,
1207	n/a	"Tools that operate on functions.");
1208	n/a
1209	n/a	static PyMethodDef module_methods[] = {
1210	n/a	{"reduce", functools_reduce, METH_VARARGS, functools_reduce_doc},
1211	n/a	{"cmp_to_key", (PyCFunction)functools_cmp_to_key,
1212	n/a	METH_VARARGS \| METH_KEYWORDS, functools_cmp_to_key_doc},
1213	n/a	{NULL, NULL} /* sentinel */
1214	n/a	};
1215	n/a
1216	n/a	static void
1217	n/a	module_free(void *m)
1218	n/a	{
1219	n/a	Py_CLEAR(kwd_mark);
1220	n/a	}
1221	n/a
1222	n/a	static struct PyModuleDef _functoolsmodule = {
1223	n/a	PyModuleDef_HEAD_INIT,
1224	n/a	"_functools",
1225	n/a	module_doc,
1226	n/a	-1,
1227	n/a	module_methods,
1228	n/a	NULL,
1229	n/a	NULL,
1230	n/a	NULL,
1231	n/a	module_free,
1232	n/a	};
1233	n/a
1234	n/a	PyMODINIT_FUNC
1235	n/a	PyInit__functools(void)
1236	n/a	{
1237	n/a	int i;
1238	n/a	PyObject *m;
1239	n/a	char *name;
1240	n/a	PyTypeObject *typelist[] = {
1241	n/a	&partial_type,
1242	n/a	&lru_cache_type,
1243	n/a	NULL
1244	n/a	};
1245	n/a
1246	n/a	m = PyModule_Create(&_functoolsmodule);
1247	n/a	if (m == NULL)
1248	n/a	return NULL;
1249	n/a
1250	n/a	kwd_mark = _PyObject_CallNoArg((PyObject *)&PyBaseObject_Type);
1251	n/a	if (!kwd_mark) {
1252	n/a	Py_DECREF(m);
1253	n/a	return NULL;
1254	n/a	}
1255	n/a
1256	n/a	for (i=0 ; typelist[i] != NULL ; i++) {
1257	n/a	if (PyType_Ready(typelist[i]) < 0) {
1258	n/a	Py_DECREF(m);
1259	n/a	return NULL;
1260	n/a	}
1261	n/a	name = strchr(typelist[i]->tp_name, '.');
1262	n/a	assert (name != NULL);
1263	n/a	Py_INCREF(typelist[i]);
1264	n/a	PyModule_AddObject(m, name+1, (PyObject *)typelist[i]);
1265	n/a	}
1266	n/a	return m;
1267	n/a	}