Python code coverage for Modules/_sqlite/cache.c

#	count	content
1	n/a	/* cache .c - a LRU cache
2	n/a	*
3	n/a	* Copyright (C) 2004-2010 Gerhard HÃ¤ring <gh@ghaering.de>
4	n/a	*
5	n/a	* This file is part of pysqlite.
6	n/a	*
7	n/a	* This software is provided 'as-is', without any express or implied
8	n/a	* warranty. In no event will the authors be held liable for any damages
9	n/a	* arising from the use of this software.
10	n/a	*
11	n/a	* Permission is granted to anyone to use this software for any purpose,
12	n/a	* including commercial applications, and to alter it and redistribute it
13	n/a	* freely, subject to the following restrictions:
14	n/a	*
15	n/a	* 1. The origin of this software must not be misrepresented; you must not
16	n/a	* claim that you wrote the original software. If you use this software
17	n/a	* in a product, an acknowledgment in the product documentation would be
18	n/a	* appreciated but is not required.
19	n/a	* 2. Altered source versions must be plainly marked as such, and must not be
20	n/a	* misrepresented as being the original software.
21	n/a	* 3. This notice may not be removed or altered from any source distribution.
22	n/a	*/
23	n/a
24	n/a	#include "cache.h"
25	n/a	#include <limits.h>
26	n/a
27	n/a	/* only used internally */
28	n/a	pysqlite_Node* pysqlite_new_node(PyObject* key, PyObject* data)
29	n/a	{
30	n/a	pysqlite_Node* node;
31	n/a
32	n/a	node = (pysqlite_Node*) (pysqlite_NodeType.tp_alloc(&pysqlite_NodeType, 0));
33	n/a	if (!node) {
34	n/a	return NULL;
35	n/a	}
36	n/a
37	n/a	Py_INCREF(key);
38	n/a	node->key = key;
39	n/a
40	n/a	Py_INCREF(data);
41	n/a	node->data = data;
42	n/a
43	n/a	node->prev = NULL;
44	n/a	node->next = NULL;
45	n/a
46	n/a	return node;
47	n/a	}
48	n/a
49	n/a	void pysqlite_node_dealloc(pysqlite_Node* self)
50	n/a	{
51	n/a	Py_DECREF(self->key);
52	n/a	Py_DECREF(self->data);
53	n/a
54	n/a	Py_TYPE(self)->tp_free((PyObject*)self);
55	n/a	}
56	n/a
57	n/a	int pysqlite_cache_init(pysqlite_Cache* self, PyObject* args, PyObject* kwargs)
58	n/a	{
59	n/a	PyObject* factory;
60	n/a	int size = 10;
61	n/a
62	n/a	self->factory = NULL;
63	n/a
64	n/a	if (!PyArg_ParseTuple(args, "O\|i", &factory, &size)) {
65	n/a	return -1;
66	n/a	}
67	n/a
68	n/a	/* minimum cache size is 5 entries */
69	n/a	if (size < 5) {
70	n/a	size = 5;
71	n/a	}
72	n/a	self->size = size;
73	n/a	self->first = NULL;
74	n/a	self->last = NULL;
75	n/a
76	n/a	self->mapping = PyDict_New();
77	n/a	if (!self->mapping) {
78	n/a	return -1;
79	n/a	}
80	n/a
81	n/a	Py_INCREF(factory);
82	n/a	self->factory = factory;
83	n/a
84	n/a	self->decref_factory = 1;
85	n/a
86	n/a	return 0;
87	n/a	}
88	n/a
89	n/a	void pysqlite_cache_dealloc(pysqlite_Cache* self)
90	n/a	{
91	n/a	pysqlite_Node* node;
92	n/a	pysqlite_Node* delete_node;
93	n/a
94	n/a	if (!self->factory) {
95	n/a	/* constructor failed, just get out of here */
96	n/a	return;
97	n/a	}
98	n/a
99	n/a	/* iterate over all nodes and deallocate them */
100	n/a	node = self->first;
101	n/a	while (node) {
102	n/a	delete_node = node;
103	n/a	node = node->next;
104	n/a	Py_DECREF(delete_node);
105	n/a	}
106	n/a
107	n/a	if (self->decref_factory) {
108	n/a	Py_DECREF(self->factory);
109	n/a	}
110	n/a	Py_DECREF(self->mapping);
111	n/a
112	n/a	Py_TYPE(self)->tp_free((PyObject*)self);
113	n/a	}
114	n/a
115	n/a	PyObject* pysqlite_cache_get(pysqlite_Cache* self, PyObject* args)
116	n/a	{
117	n/a	PyObject* key = args;
118	n/a	pysqlite_Node* node;
119	n/a	pysqlite_Node* ptr;
120	n/a	PyObject* data;
121	n/a
122	n/a	node = (pysqlite_Node*)PyDict_GetItem(self->mapping, key);
123	n/a	if (node) {
124	n/a	/* an entry for this key already exists in the cache */
125	n/a
126	n/a	/* increase usage counter of the node found */
127	n/a	if (node->count < LONG_MAX) {
128	n/a	node->count++;
129	n/a	}
130	n/a
131	n/a	/* if necessary, reorder entries in the cache by swapping positions */
132	n/a	if (node->prev && node->count > node->prev->count) {
133	n/a	ptr = node->prev;
134	n/a
135	n/a	while (ptr->prev && node->count > ptr->prev->count) {
136	n/a	ptr = ptr->prev;
137	n/a	}
138	n/a
139	n/a	if (node->next) {
140	n/a	node->next->prev = node->prev;
141	n/a	} else {
142	n/a	self->last = node->prev;
143	n/a	}
144	n/a	if (node->prev) {
145	n/a	node->prev->next = node->next;
146	n/a	}
147	n/a	if (ptr->prev) {
148	n/a	ptr->prev->next = node;
149	n/a	} else {
150	n/a	self->first = node;
151	n/a	}
152	n/a
153	n/a	node->next = ptr;
154	n/a	node->prev = ptr->prev;
155	n/a	if (!node->prev) {
156	n/a	self->first = node;
157	n/a	}
158	n/a	ptr->prev = node;
159	n/a	}
160	n/a	} else {
161	n/a	/* There is no entry for this key in the cache, yet. We'll insert a new
162	n/a	* entry in the cache, and make space if necessary by throwing the
163	n/a	* least used item out of the cache. */
164	n/a
165	n/a	if (PyDict_GET_SIZE(self->mapping) == self->size) {
166	n/a	if (self->last) {
167	n/a	node = self->last;
168	n/a
169	n/a	if (PyDict_DelItem(self->mapping, self->last->key) != 0) {
170	n/a	return NULL;
171	n/a	}
172	n/a
173	n/a	if (node->prev) {
174	n/a	node->prev->next = NULL;
175	n/a	}
176	n/a	self->last = node->prev;
177	n/a	node->prev = NULL;
178	n/a
179	n/a	Py_DECREF(node);
180	n/a	}
181	n/a	}
182	n/a
183	n/a	data = PyObject_CallFunction(self->factory, "O", key);
184	n/a
185	n/a	if (!data) {
186	n/a	return NULL;
187	n/a	}
188	n/a
189	n/a	node = pysqlite_new_node(key, data);
190	n/a	if (!node) {
191	n/a	return NULL;
192	n/a	}
193	n/a	node->prev = self->last;
194	n/a
195	n/a	Py_DECREF(data);
196	n/a
197	n/a	if (PyDict_SetItem(self->mapping, key, (PyObject*)node) != 0) {
198	n/a	Py_DECREF(node);
199	n/a	return NULL;
200	n/a	}
201	n/a
202	n/a	if (self->last) {
203	n/a	self->last->next = node;
204	n/a	} else {
205	n/a	self->first = node;
206	n/a	}
207	n/a	self->last = node;
208	n/a	}
209	n/a
210	n/a	Py_INCREF(node->data);
211	n/a	return node->data;
212	n/a	}
213	n/a
214	n/a	PyObject* pysqlite_cache_display(pysqlite_Cache* self, PyObject* args)
215	n/a	{
216	n/a	pysqlite_Node* ptr;
217	n/a	PyObject* prevkey;
218	n/a	PyObject* nextkey;
219	n/a	PyObject* display_str;
220	n/a
221	n/a	ptr = self->first;
222	n/a
223	n/a	while (ptr) {
224	n/a	if (ptr->prev) {
225	n/a	prevkey = ptr->prev->key;
226	n/a	} else {
227	n/a	prevkey = Py_None;
228	n/a	}
229	n/a
230	n/a	if (ptr->next) {
231	n/a	nextkey = ptr->next->key;
232	n/a	} else {
233	n/a	nextkey = Py_None;
234	n/a	}
235	n/a
236	n/a	display_str = PyUnicode_FromFormat("%S <- %S -> %S\n",
237	n/a	prevkey, ptr->key, nextkey);
238	n/a	if (!display_str) {
239	n/a	return NULL;
240	n/a	}
241	n/a	PyObject_Print(display_str, stdout, Py_PRINT_RAW);
242	n/a	Py_DECREF(display_str);
243	n/a
244	n/a	ptr = ptr->next;
245	n/a	}
246	n/a
247	n/a	Py_RETURN_NONE;
248	n/a	}
249	n/a
250	n/a	static PyMethodDef cache_methods[] = {
251	n/a	{"get", (PyCFunction)pysqlite_cache_get, METH_O,
252	n/a	PyDoc_STR("Gets an entry from the cache or calls the factory function to produce one.")},
253	n/a	{"display", (PyCFunction)pysqlite_cache_display, METH_NOARGS,
254	n/a	PyDoc_STR("For debugging only.")},
255	n/a	{NULL, NULL}
256	n/a	};
257	n/a
258	n/a	PyTypeObject pysqlite_NodeType = {
259	n/a	PyVarObject_HEAD_INIT(NULL, 0)
260	n/a	MODULE_NAME "Node", /* tp_name */
261	n/a	sizeof(pysqlite_Node), /* tp_basicsize */
262	n/a	0, /* tp_itemsize */
263	n/a	(destructor)pysqlite_node_dealloc, /* tp_dealloc */
264	n/a	0, /* tp_print */
265	n/a	0, /* tp_getattr */
266	n/a	0, /* tp_setattr */
267	n/a	0, /* tp_reserved */
268	n/a	0, /* tp_repr */
269	n/a	0, /* tp_as_number */
270	n/a	0, /* tp_as_sequence */
271	n/a	0, /* tp_as_mapping */
272	n/a	0, /* tp_hash */
273	n/a	0, /* tp_call */
274	n/a	0, /* tp_str */
275	n/a	0, /* tp_getattro */
276	n/a	0, /* tp_setattro */
277	n/a	0, /* tp_as_buffer */
278	n/a	Py_TPFLAGS_DEFAULT\|Py_TPFLAGS_BASETYPE, /* tp_flags */
279	n/a	0, /* tp_doc */
280	n/a	0, /* tp_traverse */
281	n/a	0, /* tp_clear */
282	n/a	0, /* tp_richcompare */
283	n/a	0, /* tp_weaklistoffset */
284	n/a	0, /* tp_iter */
285	n/a	0, /* tp_iternext */
286	n/a	0, /* tp_methods */
287	n/a	0, /* tp_members */
288	n/a	0, /* tp_getset */
289	n/a	0, /* tp_base */
290	n/a	0, /* tp_dict */
291	n/a	0, /* tp_descr_get */
292	n/a	0, /* tp_descr_set */
293	n/a	0, /* tp_dictoffset */
294	n/a	(initproc)0, /* tp_init */
295	n/a	0, /* tp_alloc */
296	n/a	0, /* tp_new */
297	n/a	0 /* tp_free */
298	n/a	};
299	n/a
300	n/a	PyTypeObject pysqlite_CacheType = {
301	n/a	PyVarObject_HEAD_INIT(NULL, 0)
302	n/a	MODULE_NAME ".Cache", /* tp_name */
303	n/a	sizeof(pysqlite_Cache), /* tp_basicsize */
304	n/a	0, /* tp_itemsize */
305	n/a	(destructor)pysqlite_cache_dealloc, /* tp_dealloc */
306	n/a	0, /* tp_print */
307	n/a	0, /* tp_getattr */
308	n/a	0, /* tp_setattr */
309	n/a	0, /* tp_reserved */
310	n/a	0, /* tp_repr */
311	n/a	0, /* tp_as_number */
312	n/a	0, /* tp_as_sequence */
313	n/a	0, /* tp_as_mapping */
314	n/a	0, /* tp_hash */
315	n/a	0, /* tp_call */
316	n/a	0, /* tp_str */
317	n/a	0, /* tp_getattro */
318	n/a	0, /* tp_setattro */
319	n/a	0, /* tp_as_buffer */
320	n/a	Py_TPFLAGS_DEFAULT\|Py_TPFLAGS_BASETYPE, /* tp_flags */
321	n/a	0, /* tp_doc */
322	n/a	0, /* tp_traverse */
323	n/a	0, /* tp_clear */
324	n/a	0, /* tp_richcompare */
325	n/a	0, /* tp_weaklistoffset */
326	n/a	0, /* tp_iter */
327	n/a	0, /* tp_iternext */
328	n/a	cache_methods, /* tp_methods */
329	n/a	0, /* tp_members */
330	n/a	0, /* tp_getset */
331	n/a	0, /* tp_base */
332	n/a	0, /* tp_dict */
333	n/a	0, /* tp_descr_get */
334	n/a	0, /* tp_descr_set */
335	n/a	0, /* tp_dictoffset */
336	n/a	(initproc)pysqlite_cache_init, /* tp_init */
337	n/a	0, /* tp_alloc */
338	n/a	0, /* tp_new */
339	n/a	0 /* tp_free */
340	n/a	};
341	n/a
342	n/a	extern int pysqlite_cache_setup_types(void)
343	n/a	{
344	n/a	int rc;
345	n/a
346	n/a	pysqlite_NodeType.tp_new = PyType_GenericNew;
347	n/a	pysqlite_CacheType.tp_new = PyType_GenericNew;
348	n/a
349	n/a	rc = PyType_Ready(&pysqlite_NodeType);
350	n/a	if (rc < 0) {
351	n/a	return rc;
352	n/a	}
353	n/a
354	n/a	rc = PyType_Ready(&pysqlite_CacheType);
355	n/a	return rc;
356	n/a	}