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