|
1 /* cache .c - a LRU cache |
|
2 * |
|
3 * Copyright (C) 2004-2007 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 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 |
|
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 |
|
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 |
|
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 |
|
115 PyObject* pysqlite_cache_get(pysqlite_Cache* self, PyObject* args) |
|
116 { |
|
117 PyObject* key = args; |
|
118 pysqlite_Node* node; |
|
119 pysqlite_Node* ptr; |
|
120 PyObject* data; |
|
121 |
|
122 node = (pysqlite_Node*)PyDict_GetItem(self->mapping, key); |
|
123 if (node) { |
|
124 /* an entry for this key already exists in the cache */ |
|
125 |
|
126 /* increase usage counter of the node found */ |
|
127 if (node->count < LONG_MAX) { |
|
128 node->count++; |
|
129 } |
|
130 |
|
131 /* if necessary, reorder entries in the cache by swapping positions */ |
|
132 if (node->prev && node->count > node->prev->count) { |
|
133 ptr = node->prev; |
|
134 |
|
135 while (ptr->prev && node->count > ptr->prev->count) { |
|
136 ptr = ptr->prev; |
|
137 } |
|
138 |
|
139 if (node->next) { |
|
140 node->next->prev = node->prev; |
|
141 } else { |
|
142 self->last = node->prev; |
|
143 } |
|
144 if (node->prev) { |
|
145 node->prev->next = node->next; |
|
146 } |
|
147 if (ptr->prev) { |
|
148 ptr->prev->next = node; |
|
149 } else { |
|
150 self->first = node; |
|
151 } |
|
152 |
|
153 node->next = ptr; |
|
154 node->prev = ptr->prev; |
|
155 if (!node->prev) { |
|
156 self->first = node; |
|
157 } |
|
158 ptr->prev = node; |
|
159 } |
|
160 } else { |
|
161 /* There is no entry for this key in the cache, yet. We'll insert a new |
|
162 * entry in the cache, and make space if necessary by throwing the |
|
163 * least used item out of the cache. */ |
|
164 |
|
165 if (PyDict_Size(self->mapping) == self->size) { |
|
166 if (self->last) { |
|
167 node = self->last; |
|
168 |
|
169 if (PyDict_DelItem(self->mapping, self->last->key) != 0) { |
|
170 return NULL; |
|
171 } |
|
172 |
|
173 if (node->prev) { |
|
174 node->prev->next = NULL; |
|
175 } |
|
176 self->last = node->prev; |
|
177 node->prev = NULL; |
|
178 |
|
179 Py_DECREF(node); |
|
180 } |
|
181 } |
|
182 |
|
183 data = PyObject_CallFunction(self->factory, "O", key); |
|
184 |
|
185 if (!data) { |
|
186 return NULL; |
|
187 } |
|
188 |
|
189 node = pysqlite_new_node(key, data); |
|
190 if (!node) { |
|
191 return NULL; |
|
192 } |
|
193 node->prev = self->last; |
|
194 |
|
195 Py_DECREF(data); |
|
196 |
|
197 if (PyDict_SetItem(self->mapping, key, (PyObject*)node) != 0) { |
|
198 Py_DECREF(node); |
|
199 return NULL; |
|
200 } |
|
201 |
|
202 if (self->last) { |
|
203 self->last->next = node; |
|
204 } else { |
|
205 self->first = node; |
|
206 } |
|
207 self->last = node; |
|
208 } |
|
209 |
|
210 Py_INCREF(node->data); |
|
211 return node->data; |
|
212 } |
|
213 |
|
214 PyObject* pysqlite_cache_display(pysqlite_Cache* self, PyObject* args) |
|
215 { |
|
216 pysqlite_Node* ptr; |
|
217 PyObject* prevkey; |
|
218 PyObject* nextkey; |
|
219 PyObject* fmt_args; |
|
220 PyObject* template; |
|
221 PyObject* display_str; |
|
222 |
|
223 ptr = self->first; |
|
224 |
|
225 while (ptr) { |
|
226 if (ptr->prev) { |
|
227 prevkey = ptr->prev->key; |
|
228 } else { |
|
229 prevkey = Py_None; |
|
230 } |
|
231 Py_INCREF(prevkey); |
|
232 |
|
233 if (ptr->next) { |
|
234 nextkey = ptr->next->key; |
|
235 } else { |
|
236 nextkey = Py_None; |
|
237 } |
|
238 Py_INCREF(nextkey); |
|
239 |
|
240 fmt_args = Py_BuildValue("OOO", prevkey, ptr->key, nextkey); |
|
241 if (!fmt_args) { |
|
242 return NULL; |
|
243 } |
|
244 template = PyString_FromString("%s <- %s ->%s\n"); |
|
245 if (!template) { |
|
246 Py_DECREF(fmt_args); |
|
247 return NULL; |
|
248 } |
|
249 display_str = PyString_Format(template, fmt_args); |
|
250 Py_DECREF(template); |
|
251 Py_DECREF(fmt_args); |
|
252 if (!display_str) { |
|
253 return NULL; |
|
254 } |
|
255 PyObject_Print(display_str, stdout, Py_PRINT_RAW); |
|
256 Py_DECREF(display_str); |
|
257 |
|
258 Py_DECREF(prevkey); |
|
259 Py_DECREF(nextkey); |
|
260 |
|
261 ptr = ptr->next; |
|
262 } |
|
263 |
|
264 Py_INCREF(Py_None); |
|
265 return Py_None; |
|
266 } |
|
267 |
|
268 static PyMethodDef cache_methods[] = { |
|
269 {"get", (PyCFunction)pysqlite_cache_get, METH_O, |
|
270 PyDoc_STR("Gets an entry from the cache or calls the factory function to produce one.")}, |
|
271 {"display", (PyCFunction)pysqlite_cache_display, METH_NOARGS, |
|
272 PyDoc_STR("For debugging only.")}, |
|
273 {NULL, NULL} |
|
274 }; |
|
275 |
|
276 PyTypeObject pysqlite_NodeType = { |
|
277 PyVarObject_HEAD_INIT(NULL, 0) |
|
278 MODULE_NAME "Node", /* tp_name */ |
|
279 sizeof(pysqlite_Node), /* tp_basicsize */ |
|
280 0, /* tp_itemsize */ |
|
281 (destructor)pysqlite_node_dealloc, /* tp_dealloc */ |
|
282 0, /* tp_print */ |
|
283 0, /* tp_getattr */ |
|
284 0, /* tp_setattr */ |
|
285 0, /* tp_compare */ |
|
286 0, /* tp_repr */ |
|
287 0, /* tp_as_number */ |
|
288 0, /* tp_as_sequence */ |
|
289 0, /* tp_as_mapping */ |
|
290 0, /* tp_hash */ |
|
291 0, /* tp_call */ |
|
292 0, /* tp_str */ |
|
293 0, /* tp_getattro */ |
|
294 0, /* tp_setattro */ |
|
295 0, /* tp_as_buffer */ |
|
296 Py_TPFLAGS_DEFAULT|Py_TPFLAGS_BASETYPE, /* tp_flags */ |
|
297 0, /* tp_doc */ |
|
298 0, /* tp_traverse */ |
|
299 0, /* tp_clear */ |
|
300 0, /* tp_richcompare */ |
|
301 0, /* tp_weaklistoffset */ |
|
302 0, /* tp_iter */ |
|
303 0, /* tp_iternext */ |
|
304 0, /* tp_methods */ |
|
305 0, /* tp_members */ |
|
306 0, /* tp_getset */ |
|
307 0, /* tp_base */ |
|
308 0, /* tp_dict */ |
|
309 0, /* tp_descr_get */ |
|
310 0, /* tp_descr_set */ |
|
311 0, /* tp_dictoffset */ |
|
312 (initproc)0, /* tp_init */ |
|
313 0, /* tp_alloc */ |
|
314 0, /* tp_new */ |
|
315 0 /* tp_free */ |
|
316 }; |
|
317 |
|
318 PyTypeObject pysqlite_CacheType = { |
|
319 PyVarObject_HEAD_INIT(NULL, 0) |
|
320 MODULE_NAME ".Cache", /* tp_name */ |
|
321 sizeof(pysqlite_Cache), /* tp_basicsize */ |
|
322 0, /* tp_itemsize */ |
|
323 (destructor)pysqlite_cache_dealloc, /* tp_dealloc */ |
|
324 0, /* tp_print */ |
|
325 0, /* tp_getattr */ |
|
326 0, /* tp_setattr */ |
|
327 0, /* tp_compare */ |
|
328 0, /* tp_repr */ |
|
329 0, /* tp_as_number */ |
|
330 0, /* tp_as_sequence */ |
|
331 0, /* tp_as_mapping */ |
|
332 0, /* tp_hash */ |
|
333 0, /* tp_call */ |
|
334 0, /* tp_str */ |
|
335 0, /* tp_getattro */ |
|
336 0, /* tp_setattro */ |
|
337 0, /* tp_as_buffer */ |
|
338 Py_TPFLAGS_DEFAULT|Py_TPFLAGS_BASETYPE, /* tp_flags */ |
|
339 0, /* tp_doc */ |
|
340 0, /* tp_traverse */ |
|
341 0, /* tp_clear */ |
|
342 0, /* tp_richcompare */ |
|
343 0, /* tp_weaklistoffset */ |
|
344 0, /* tp_iter */ |
|
345 0, /* tp_iternext */ |
|
346 cache_methods, /* tp_methods */ |
|
347 0, /* tp_members */ |
|
348 0, /* tp_getset */ |
|
349 0, /* tp_base */ |
|
350 0, /* tp_dict */ |
|
351 0, /* tp_descr_get */ |
|
352 0, /* tp_descr_set */ |
|
353 0, /* tp_dictoffset */ |
|
354 (initproc)pysqlite_cache_init, /* tp_init */ |
|
355 0, /* tp_alloc */ |
|
356 0, /* tp_new */ |
|
357 0 /* tp_free */ |
|
358 }; |
|
359 |
|
360 extern int pysqlite_cache_setup_types(void) |
|
361 { |
|
362 int rc; |
|
363 |
|
364 pysqlite_NodeType.tp_new = PyType_GenericNew; |
|
365 pysqlite_CacheType.tp_new = PyType_GenericNew; |
|
366 |
|
367 rc = PyType_Ready(&pysqlite_NodeType); |
|
368 if (rc < 0) { |
|
369 return rc; |
|
370 } |
|
371 |
|
372 rc = PyType_Ready(&pysqlite_CacheType); |
|
373 return rc; |
|
374 } |