1 | /* cache .c - a LRU cache |
2 | * |
3 | * Copyright (C) 2004-2010 Gerhard Häring <[email protected]> |
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 * |
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 |
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 |
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 |
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 |
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 |
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 |
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 |
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 | |
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 * |
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 |
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 | |