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