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 */
28 static pysqlite_Node *
pysqlite_new_node(PyObject * key,PyObject * data)29 pysqlite_new_node(PyObject *key, PyObject *data)
30 {
31 pysqlite_Node* node;
32
33 node = (pysqlite_Node*) (pysqlite_NodeType->tp_alloc(pysqlite_NodeType, 0));
34 if (!node) {
35 return NULL;
36 }
37
38 node->key = Py_NewRef(key);
39 node->data = Py_NewRef(data);
40
41 node->prev = NULL;
42 node->next = NULL;
43
44 return node;
45 }
46
47 static int
node_traverse(pysqlite_Node * self,visitproc visit,void * arg)48 node_traverse(pysqlite_Node *self, visitproc visit, void *arg)
49 {
50 Py_VISIT(Py_TYPE(self));
51 Py_VISIT(self->key);
52 Py_VISIT(self->data);
53 return 0;
54 }
55
56 static int
node_clear(pysqlite_Node * self)57 node_clear(pysqlite_Node *self)
58 {
59 Py_CLEAR(self->key);
60 Py_CLEAR(self->data);
61 return 0;
62 }
63
64 static void
pysqlite_node_dealloc(pysqlite_Node * self)65 pysqlite_node_dealloc(pysqlite_Node *self)
66 {
67 PyTypeObject *tp = Py_TYPE(self);
68 PyObject_GC_UnTrack(self);
69 tp->tp_clear((PyObject *)self);
70 tp->tp_free(self);
71 Py_DECREF(tp);
72 }
73
74 static int
pysqlite_cache_init(pysqlite_Cache * self,PyObject * args,PyObject * kwargs)75 pysqlite_cache_init(pysqlite_Cache *self, PyObject *args, PyObject *kwargs)
76 {
77 PyObject* factory;
78 int size = 10;
79
80 self->factory = NULL;
81
82 if (!PyArg_ParseTuple(args, "O|i", &factory, &size)) {
83 return -1;
84 }
85
86 /* minimum cache size is 5 entries */
87 if (size < 5) {
88 size = 5;
89 }
90 self->size = size;
91 self->first = NULL;
92 self->last = NULL;
93
94 self->mapping = PyDict_New();
95 if (!self->mapping) {
96 return -1;
97 }
98
99 self->factory = Py_NewRef(factory);
100
101 self->decref_factory = 1;
102
103 return 0;
104 }
105
106 static int
cache_traverse(pysqlite_Cache * self,visitproc visit,void * arg)107 cache_traverse(pysqlite_Cache *self, visitproc visit, void *arg)
108 {
109 Py_VISIT(Py_TYPE(self));
110 Py_VISIT(self->mapping);
111 if (self->decref_factory) {
112 Py_VISIT(self->factory);
113 }
114
115 pysqlite_Node *node = self->first;
116 while (node) {
117 Py_VISIT(node);
118 node = node->next;
119 }
120 return 0;
121 }
122
123 static int
cache_clear(pysqlite_Cache * self)124 cache_clear(pysqlite_Cache *self)
125 {
126 Py_CLEAR(self->mapping);
127 if (self->decref_factory) {
128 Py_CLEAR(self->factory);
129 }
130
131 /* iterate over all nodes and deallocate them */
132 pysqlite_Node *node = self->first;
133 self->first = NULL;
134 while (node) {
135 pysqlite_Node *delete_node = node;
136 node = node->next;
137 Py_CLEAR(delete_node);
138 }
139 return 0;
140 }
141
142 static void
pysqlite_cache_dealloc(pysqlite_Cache * self)143 pysqlite_cache_dealloc(pysqlite_Cache *self)
144 {
145 if (!self->factory) {
146 /* constructor failed, just get out of here */
147 return;
148 }
149
150 PyObject_GC_UnTrack(self);
151 PyTypeObject *tp = Py_TYPE(self);
152 tp->tp_clear((PyObject *)self);
153 tp->tp_free(self);
154 Py_DECREF(tp);
155 }
156
pysqlite_cache_get(pysqlite_Cache * self,PyObject * key)157 PyObject* pysqlite_cache_get(pysqlite_Cache* self, PyObject* key)
158 {
159 pysqlite_Node* node;
160 pysqlite_Node* ptr;
161 PyObject* data;
162
163 node = (pysqlite_Node*)PyDict_GetItemWithError(self->mapping, key);
164 if (node) {
165 /* an entry for this key already exists in the cache */
166
167 /* increase usage counter of the node found */
168 if (node->count < LONG_MAX) {
169 node->count++;
170 }
171
172 /* if necessary, reorder entries in the cache by swapping positions */
173 if (node->prev && node->count > node->prev->count) {
174 ptr = node->prev;
175
176 while (ptr->prev && node->count > ptr->prev->count) {
177 ptr = ptr->prev;
178 }
179
180 if (node->next) {
181 node->next->prev = node->prev;
182 } else {
183 self->last = node->prev;
184 }
185 if (node->prev) {
186 node->prev->next = node->next;
187 }
188 if (ptr->prev) {
189 ptr->prev->next = node;
190 } else {
191 self->first = node;
192 }
193
194 node->next = ptr;
195 node->prev = ptr->prev;
196 if (!node->prev) {
197 self->first = node;
198 }
199 ptr->prev = node;
200 }
201 }
202 else if (PyErr_Occurred()) {
203 return NULL;
204 }
205 else {
206 /* There is no entry for this key in the cache, yet. We'll insert a new
207 * entry in the cache, and make space if necessary by throwing the
208 * least used item out of the cache. */
209
210 if (PyDict_GET_SIZE(self->mapping) == self->size) {
211 if (self->last) {
212 node = self->last;
213
214 if (PyDict_DelItem(self->mapping, self->last->key) != 0) {
215 return NULL;
216 }
217
218 if (node->prev) {
219 node->prev->next = NULL;
220 }
221 self->last = node->prev;
222 node->prev = NULL;
223
224 Py_DECREF(node);
225 }
226 }
227
228 /* We cannot replace this by PyObject_CallOneArg() since
229 * PyObject_CallFunction() has a special case when using a
230 * single tuple as argument. */
231 data = PyObject_CallFunction(self->factory, "O", key);
232
233 if (!data) {
234 return NULL;
235 }
236
237 node = pysqlite_new_node(key, data);
238 if (!node) {
239 return NULL;
240 }
241 node->prev = self->last;
242
243 Py_DECREF(data);
244
245 if (PyDict_SetItem(self->mapping, key, (PyObject*)node) != 0) {
246 Py_DECREF(node);
247 return NULL;
248 }
249
250 if (self->last) {
251 self->last->next = node;
252 } else {
253 self->first = node;
254 }
255 self->last = node;
256 }
257
258 return Py_NewRef(node->data);
259 }
260
261 static PyObject *
pysqlite_cache_display(pysqlite_Cache * self,PyObject * args)262 pysqlite_cache_display(pysqlite_Cache *self, PyObject *args)
263 {
264 pysqlite_Node* ptr;
265 PyObject* prevkey;
266 PyObject* nextkey;
267 PyObject* display_str;
268
269 ptr = self->first;
270
271 while (ptr) {
272 if (ptr->prev) {
273 prevkey = ptr->prev->key;
274 } else {
275 prevkey = Py_None;
276 }
277
278 if (ptr->next) {
279 nextkey = ptr->next->key;
280 } else {
281 nextkey = Py_None;
282 }
283
284 display_str = PyUnicode_FromFormat("%S <- %S -> %S\n",
285 prevkey, ptr->key, nextkey);
286 if (!display_str) {
287 return NULL;
288 }
289 PyObject_Print(display_str, stdout, Py_PRINT_RAW);
290 Py_DECREF(display_str);
291
292 ptr = ptr->next;
293 }
294
295 Py_RETURN_NONE;
296 }
297
298 static PyType_Slot node_slots[] = {
299 {Py_tp_dealloc, pysqlite_node_dealloc},
300 {Py_tp_traverse, node_traverse},
301 {Py_tp_clear, node_clear},
302 {0, NULL},
303 };
304
305 static PyType_Spec node_spec = {
306 .name = MODULE_NAME ".Node",
307 .basicsize = sizeof(pysqlite_Node),
308 .flags = Py_TPFLAGS_DEFAULT | Py_TPFLAGS_BASETYPE | Py_TPFLAGS_HAVE_GC,
309 .slots = node_slots,
310 };
311 PyTypeObject *pysqlite_NodeType = NULL;
312
313 static PyMethodDef cache_methods[] = {
314 {"get", (PyCFunction)pysqlite_cache_get, METH_O,
315 PyDoc_STR("Gets an entry from the cache or calls the factory function to produce one.")},
316 {"display", (PyCFunction)pysqlite_cache_display, METH_NOARGS,
317 PyDoc_STR("For debugging only.")},
318 {NULL, NULL}
319 };
320
321 static PyType_Slot cache_slots[] = {
322 {Py_tp_dealloc, pysqlite_cache_dealloc},
323 {Py_tp_methods, cache_methods},
324 {Py_tp_init, pysqlite_cache_init},
325 {Py_tp_traverse, cache_traverse},
326 {Py_tp_clear, cache_clear},
327 {0, NULL},
328 };
329
330 static PyType_Spec cache_spec = {
331 .name = MODULE_NAME ".Cache",
332 .basicsize = sizeof(pysqlite_Cache),
333 .flags = Py_TPFLAGS_DEFAULT | Py_TPFLAGS_BASETYPE | Py_TPFLAGS_HAVE_GC,
334 .slots = cache_slots,
335 };
336 PyTypeObject *pysqlite_CacheType = NULL;
337
338 int
pysqlite_cache_setup_types(PyObject * mod)339 pysqlite_cache_setup_types(PyObject *mod)
340 {
341 pysqlite_NodeType = (PyTypeObject *)PyType_FromModuleAndSpec(mod, &node_spec, NULL);
342 if (pysqlite_NodeType == NULL) {
343 return -1;
344 }
345
346 pysqlite_CacheType = (PyTypeObject *)PyType_FromModuleAndSpec(mod, &cache_spec, NULL);
347 if (pysqlite_CacheType == NULL) {
348 return -1;
349 }
350 return 0;
351 }
352