blob: 735a2426ccf1f488a888b6996e77e1bd9fc5d62c [file] [log] [blame]
Thomas Wouters49fd7fa2006-04-21 10:40:58 +00001/* cache .c - a LRU cache
2 *
Florent Xiclunac934f322010-09-03 23:47:32 +00003 * Copyright (C) 2004-2010 Gerhard Häring <gh@ghaering.de>
Thomas Wouters49fd7fa2006-04-21 10:40:58 +00004 *
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
Gerhard Häringf9cee222010-03-05 15:20:03 +000024#include "sqlitecompat.h"
Thomas Wouters49fd7fa2006-04-21 10:40:58 +000025#include "cache.h"
Thomas Wouters477c8d52006-05-27 19:21:47 +000026#include <limits.h>
Thomas Wouters49fd7fa2006-04-21 10:40:58 +000027
28/* only used internally */
Thomas Woutersfc7bb8c2007-01-15 15:49:28 +000029pysqlite_Node* pysqlite_new_node(PyObject* key, PyObject* data)
Thomas Wouters49fd7fa2006-04-21 10:40:58 +000030{
Thomas Woutersfc7bb8c2007-01-15 15:49:28 +000031 pysqlite_Node* node;
Thomas Wouters49fd7fa2006-04-21 10:40:58 +000032
Thomas Woutersfc7bb8c2007-01-15 15:49:28 +000033 node = (pysqlite_Node*) (pysqlite_NodeType.tp_alloc(&pysqlite_NodeType, 0));
Thomas Wouters49fd7fa2006-04-21 10:40:58 +000034 if (!node) {
35 return NULL;
36 }
37
38 Py_INCREF(key);
39 node->key = key;
40
41 Py_INCREF(data);
42 node->data = data;
43
44 node->prev = NULL;
45 node->next = NULL;
46
47 return node;
48}
49
Thomas Woutersfc7bb8c2007-01-15 15:49:28 +000050void pysqlite_node_dealloc(pysqlite_Node* self)
Thomas Wouters49fd7fa2006-04-21 10:40:58 +000051{
52 Py_DECREF(self->key);
53 Py_DECREF(self->data);
54
Christian Heimes90aa7642007-12-19 02:45:37 +000055 Py_TYPE(self)->tp_free((PyObject*)self);
Thomas Wouters49fd7fa2006-04-21 10:40:58 +000056}
57
Thomas Woutersfc7bb8c2007-01-15 15:49:28 +000058int pysqlite_cache_init(pysqlite_Cache* self, PyObject* args, PyObject* kwargs)
Thomas Wouters49fd7fa2006-04-21 10:40:58 +000059{
60 PyObject* factory;
61 int size = 10;
62
63 self->factory = NULL;
64
Thomas Wouters477c8d52006-05-27 19:21:47 +000065 if (!PyArg_ParseTuple(args, "O|i", &factory, &size)) {
66 return -1;
Thomas Wouters49fd7fa2006-04-21 10:40:58 +000067 }
68
Thomas Wouters477c8d52006-05-27 19:21:47 +000069 /* minimum cache size is 5 entries */
Thomas Wouters49fd7fa2006-04-21 10:40:58 +000070 if (size < 5) {
71 size = 5;
72 }
73 self->size = size;
74 self->first = NULL;
75 self->last = NULL;
76
77 self->mapping = PyDict_New();
78 if (!self->mapping) {
79 return -1;
80 }
81
82 Py_INCREF(factory);
83 self->factory = factory;
84
85 self->decref_factory = 1;
86
87 return 0;
88}
89
Thomas Woutersfc7bb8c2007-01-15 15:49:28 +000090void pysqlite_cache_dealloc(pysqlite_Cache* self)
Thomas Wouters49fd7fa2006-04-21 10:40:58 +000091{
Thomas Woutersfc7bb8c2007-01-15 15:49:28 +000092 pysqlite_Node* node;
93 pysqlite_Node* delete_node;
Thomas Wouters49fd7fa2006-04-21 10:40:58 +000094
95 if (!self->factory) {
96 /* constructor failed, just get out of here */
97 return;
98 }
99
Thomas Wouters477c8d52006-05-27 19:21:47 +0000100 /* iterate over all nodes and deallocate them */
Thomas Wouters49fd7fa2006-04-21 10:40:58 +0000101 node = self->first;
102 while (node) {
103 delete_node = node;
104 node = node->next;
105 Py_DECREF(delete_node);
106 }
107
108 if (self->decref_factory) {
109 Py_DECREF(self->factory);
110 }
111 Py_DECREF(self->mapping);
112
Christian Heimes90aa7642007-12-19 02:45:37 +0000113 Py_TYPE(self)->tp_free((PyObject*)self);
Thomas Wouters49fd7fa2006-04-21 10:40:58 +0000114}
115
Thomas Woutersfc7bb8c2007-01-15 15:49:28 +0000116PyObject* pysqlite_cache_get(pysqlite_Cache* self, PyObject* args)
Thomas Wouters49fd7fa2006-04-21 10:40:58 +0000117{
118 PyObject* key = args;
Thomas Woutersfc7bb8c2007-01-15 15:49:28 +0000119 pysqlite_Node* node;
120 pysqlite_Node* ptr;
Thomas Wouters49fd7fa2006-04-21 10:40:58 +0000121 PyObject* data;
122
Thomas Woutersfc7bb8c2007-01-15 15:49:28 +0000123 node = (pysqlite_Node*)PyDict_GetItem(self->mapping, key);
Thomas Wouters49fd7fa2006-04-21 10:40:58 +0000124 if (node) {
Thomas Wouters477c8d52006-05-27 19:21:47 +0000125 /* an entry for this key already exists in the cache */
126
127 /* increase usage counter of the node found */
128 if (node->count < LONG_MAX) {
129 node->count++;
130 }
131
132 /* if necessary, reorder entries in the cache by swapping positions */
Thomas Wouters49fd7fa2006-04-21 10:40:58 +0000133 if (node->prev && node->count > node->prev->count) {
134 ptr = node->prev;
135
136 while (ptr->prev && node->count > ptr->prev->count) {
137 ptr = ptr->prev;
138 }
139
140 if (node->next) {
141 node->next->prev = node->prev;
142 } else {
143 self->last = node->prev;
144 }
145 if (node->prev) {
146 node->prev->next = node->next;
147 }
148 if (ptr->prev) {
149 ptr->prev->next = node;
150 } else {
151 self->first = node;
152 }
153
154 node->next = ptr;
155 node->prev = ptr->prev;
156 if (!node->prev) {
157 self->first = node;
158 }
159 ptr->prev = node;
160 }
161 } else {
Thomas Wouters477c8d52006-05-27 19:21:47 +0000162 /* There is no entry for this key in the cache, yet. We'll insert a new
163 * entry in the cache, and make space if necessary by throwing the
164 * least used item out of the cache. */
165
Thomas Wouters49fd7fa2006-04-21 10:40:58 +0000166 if (PyDict_Size(self->mapping) == self->size) {
167 if (self->last) {
168 node = self->last;
169
170 if (PyDict_DelItem(self->mapping, self->last->key) != 0) {
171 return NULL;
172 }
173
174 if (node->prev) {
175 node->prev->next = NULL;
176 }
177 self->last = node->prev;
178 node->prev = NULL;
179
180 Py_DECREF(node);
181 }
182 }
183
184 data = PyObject_CallFunction(self->factory, "O", key);
185
186 if (!data) {
187 return NULL;
188 }
189
Thomas Woutersfc7bb8c2007-01-15 15:49:28 +0000190 node = pysqlite_new_node(key, data);
Thomas Wouters49fd7fa2006-04-21 10:40:58 +0000191 if (!node) {
192 return NULL;
193 }
194 node->prev = self->last;
195
196 Py_DECREF(data);
197
198 if (PyDict_SetItem(self->mapping, key, (PyObject*)node) != 0) {
199 Py_DECREF(node);
200 return NULL;
201 }
202
203 if (self->last) {
204 self->last->next = node;
205 } else {
206 self->first = node;
207 }
208 self->last = node;
209 }
210
211 Py_INCREF(node->data);
212 return node->data;
213}
214
Thomas Woutersfc7bb8c2007-01-15 15:49:28 +0000215PyObject* pysqlite_cache_display(pysqlite_Cache* self, PyObject* args)
Thomas Wouters49fd7fa2006-04-21 10:40:58 +0000216{
Thomas Woutersfc7bb8c2007-01-15 15:49:28 +0000217 pysqlite_Node* ptr;
Thomas Wouters49fd7fa2006-04-21 10:40:58 +0000218 PyObject* prevkey;
219 PyObject* nextkey;
220 PyObject* fmt_args;
221 PyObject* template;
222 PyObject* display_str;
223
224 ptr = self->first;
225
226 while (ptr) {
227 if (ptr->prev) {
228 prevkey = ptr->prev->key;
229 } else {
230 prevkey = Py_None;
231 }
232 Py_INCREF(prevkey);
233
234 if (ptr->next) {
235 nextkey = ptr->next->key;
236 } else {
237 nextkey = Py_None;
238 }
239 Py_INCREF(nextkey);
240
241 fmt_args = Py_BuildValue("OOO", prevkey, ptr->key, nextkey);
242 if (!fmt_args) {
243 return NULL;
244 }
Guido van Rossum98297ee2007-11-06 21:34:58 +0000245 template = PyUnicode_FromString("%s <- %s ->%s\n");
Thomas Wouters49fd7fa2006-04-21 10:40:58 +0000246 if (!template) {
Guido van Rossumcd16bf62007-06-13 18:07:49 +0000247 Py_DECREF(fmt_args);
Thomas Wouters49fd7fa2006-04-21 10:40:58 +0000248 return NULL;
249 }
Guido van Rossum98297ee2007-11-06 21:34:58 +0000250 display_str = PyUnicode_Format(template, fmt_args);
Thomas Wouters49fd7fa2006-04-21 10:40:58 +0000251 Py_DECREF(template);
252 Py_DECREF(fmt_args);
253 if (!display_str) {
254 return NULL;
255 }
256 PyObject_Print(display_str, stdout, Py_PRINT_RAW);
257 Py_DECREF(display_str);
258
259 Py_DECREF(prevkey);
260 Py_DECREF(nextkey);
261
262 ptr = ptr->next;
263 }
264
265 Py_INCREF(Py_None);
266 return Py_None;
267}
268
269static PyMethodDef cache_methods[] = {
Thomas Woutersfc7bb8c2007-01-15 15:49:28 +0000270 {"get", (PyCFunction)pysqlite_cache_get, METH_O,
Thomas Wouters477c8d52006-05-27 19:21:47 +0000271 PyDoc_STR("Gets an entry from the cache or calls the factory function to produce one.")},
Thomas Woutersfc7bb8c2007-01-15 15:49:28 +0000272 {"display", (PyCFunction)pysqlite_cache_display, METH_NOARGS,
Thomas Wouters49fd7fa2006-04-21 10:40:58 +0000273 PyDoc_STR("For debugging only.")},
274 {NULL, NULL}
275};
276
Thomas Woutersfc7bb8c2007-01-15 15:49:28 +0000277PyTypeObject pysqlite_NodeType = {
Martin v. Löwis9f2e3462007-07-21 17:22:18 +0000278 PyVarObject_HEAD_INIT(NULL, 0)
Thomas Wouters49fd7fa2006-04-21 10:40:58 +0000279 MODULE_NAME "Node", /* tp_name */
Thomas Woutersfc7bb8c2007-01-15 15:49:28 +0000280 sizeof(pysqlite_Node), /* tp_basicsize */
Thomas Wouters49fd7fa2006-04-21 10:40:58 +0000281 0, /* tp_itemsize */
Thomas Woutersfc7bb8c2007-01-15 15:49:28 +0000282 (destructor)pysqlite_node_dealloc, /* tp_dealloc */
Thomas Wouters49fd7fa2006-04-21 10:40:58 +0000283 0, /* tp_print */
284 0, /* tp_getattr */
285 0, /* tp_setattr */
Mark Dickinsone94c6792009-02-02 20:36:42 +0000286 0, /* tp_reserved */
Thomas Wouters49fd7fa2006-04-21 10:40:58 +0000287 0, /* tp_repr */
288 0, /* tp_as_number */
289 0, /* tp_as_sequence */
290 0, /* tp_as_mapping */
291 0, /* tp_hash */
292 0, /* tp_call */
293 0, /* tp_str */
294 0, /* tp_getattro */
295 0, /* tp_setattro */
296 0, /* tp_as_buffer */
297 Py_TPFLAGS_DEFAULT|Py_TPFLAGS_BASETYPE, /* tp_flags */
298 0, /* tp_doc */
299 0, /* tp_traverse */
300 0, /* tp_clear */
301 0, /* tp_richcompare */
302 0, /* tp_weaklistoffset */
303 0, /* tp_iter */
304 0, /* tp_iternext */
305 0, /* tp_methods */
306 0, /* tp_members */
307 0, /* tp_getset */
308 0, /* tp_base */
309 0, /* tp_dict */
310 0, /* tp_descr_get */
311 0, /* tp_descr_set */
312 0, /* tp_dictoffset */
313 (initproc)0, /* tp_init */
314 0, /* tp_alloc */
315 0, /* tp_new */
316 0 /* tp_free */
317};
318
Thomas Woutersfc7bb8c2007-01-15 15:49:28 +0000319PyTypeObject pysqlite_CacheType = {
Martin v. Löwis9f2e3462007-07-21 17:22:18 +0000320 PyVarObject_HEAD_INIT(NULL, 0)
Thomas Wouters49fd7fa2006-04-21 10:40:58 +0000321 MODULE_NAME ".Cache", /* tp_name */
Thomas Woutersfc7bb8c2007-01-15 15:49:28 +0000322 sizeof(pysqlite_Cache), /* tp_basicsize */
Thomas Wouters49fd7fa2006-04-21 10:40:58 +0000323 0, /* tp_itemsize */
Thomas Woutersfc7bb8c2007-01-15 15:49:28 +0000324 (destructor)pysqlite_cache_dealloc, /* tp_dealloc */
Thomas Wouters49fd7fa2006-04-21 10:40:58 +0000325 0, /* tp_print */
326 0, /* tp_getattr */
327 0, /* tp_setattr */
Mark Dickinsone94c6792009-02-02 20:36:42 +0000328 0, /* tp_reserved */
Thomas Wouters49fd7fa2006-04-21 10:40:58 +0000329 0, /* tp_repr */
330 0, /* tp_as_number */
331 0, /* tp_as_sequence */
332 0, /* tp_as_mapping */
333 0, /* tp_hash */
334 0, /* tp_call */
335 0, /* tp_str */
336 0, /* tp_getattro */
337 0, /* tp_setattro */
338 0, /* tp_as_buffer */
339 Py_TPFLAGS_DEFAULT|Py_TPFLAGS_BASETYPE, /* tp_flags */
340 0, /* tp_doc */
341 0, /* tp_traverse */
342 0, /* tp_clear */
343 0, /* tp_richcompare */
344 0, /* tp_weaklistoffset */
345 0, /* tp_iter */
346 0, /* tp_iternext */
347 cache_methods, /* tp_methods */
348 0, /* tp_members */
349 0, /* tp_getset */
350 0, /* tp_base */
351 0, /* tp_dict */
352 0, /* tp_descr_get */
353 0, /* tp_descr_set */
354 0, /* tp_dictoffset */
Thomas Woutersfc7bb8c2007-01-15 15:49:28 +0000355 (initproc)pysqlite_cache_init, /* tp_init */
Thomas Wouters49fd7fa2006-04-21 10:40:58 +0000356 0, /* tp_alloc */
357 0, /* tp_new */
358 0 /* tp_free */
359};
360
Thomas Woutersfc7bb8c2007-01-15 15:49:28 +0000361extern int pysqlite_cache_setup_types(void)
Thomas Wouters49fd7fa2006-04-21 10:40:58 +0000362{
363 int rc;
364
Thomas Woutersfc7bb8c2007-01-15 15:49:28 +0000365 pysqlite_NodeType.tp_new = PyType_GenericNew;
366 pysqlite_CacheType.tp_new = PyType_GenericNew;
Thomas Wouters49fd7fa2006-04-21 10:40:58 +0000367
Thomas Woutersfc7bb8c2007-01-15 15:49:28 +0000368 rc = PyType_Ready(&pysqlite_NodeType);
Thomas Wouters49fd7fa2006-04-21 10:40:58 +0000369 if (rc < 0) {
370 return rc;
371 }
372
Thomas Woutersfc7bb8c2007-01-15 15:49:28 +0000373 rc = PyType_Ready(&pysqlite_CacheType);
Thomas Wouters49fd7fa2006-04-21 10:40:58 +0000374 return rc;
375}