source: trunk/essentials/dev-lang/python/Modules/_sqlite/cache.c@ 3403

Last change on this file since 3403 was 3225, checked in by bird, 19 years ago

Python 2.5
File size: 12.4 KB
Line 
1/* cache .c - a LRU cache
2 *
3 * Copyright (C) 2004-2006 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 */
28Node* new_node(PyObject* key, PyObject* data)
29{
30 Node* node;
31
32 node = (Node*) (NodeType.tp_alloc(&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
49void node_dealloc(Node* self)
50{
51 Py_DECREF(self->key);
52 Py_DECREF(self->data);
53
54 self->ob_type->tp_free((PyObject*)self);
55}
56
57int cache_init(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
89void cache_dealloc(Cache* self)
90{
91 Node* node;
92 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 self->ob_type->tp_free((PyObject*)self);
113}
114
115PyObject* cache_get(Cache* self, PyObject* args)
116{
117 PyObject* key = args;
118 Node* node;
119 Node* ptr;
120 PyObject* data;
121
122 node = (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 = 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
214PyObject* cache_display(Cache* self, PyObject* args)
215{
216 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 return NULL;
247 }
248 display_str = PyString_Format(template, fmt_args);
249 Py_DECREF(template);
250 Py_DECREF(fmt_args);
251 if (!display_str) {
252 return NULL;
253 }
254 PyObject_Print(display_str, stdout, Py_PRINT_RAW);
255 Py_DECREF(display_str);
256
257 Py_DECREF(prevkey);
258 Py_DECREF(nextkey);
259
260 ptr = ptr->next;
261 }
262
263 Py_INCREF(Py_None);
264 return Py_None;
265}
266
267static PyMethodDef cache_methods[] = {
268 {"get", (PyCFunction)cache_get, METH_O,
269 PyDoc_STR("Gets an entry from the cache or calls the factory function to produce one.")},
270 {"display", (PyCFunction)cache_display, METH_NOARGS,
271 PyDoc_STR("For debugging only.")},
272 {NULL, NULL}
273};
274
275PyTypeObject NodeType = {
276 PyObject_HEAD_INIT(NULL)
277 0, /* ob_size */
278 MODULE_NAME "Node", /* tp_name */
279 sizeof(Node), /* tp_basicsize */
280 0, /* tp_itemsize */
281 (destructor)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
318PyTypeObject CacheType = {
319 PyObject_HEAD_INIT(NULL)
320 0, /* ob_size */
321 MODULE_NAME ".Cache", /* tp_name */
322 sizeof(Cache), /* tp_basicsize */
323 0, /* tp_itemsize */
324 (destructor)cache_dealloc, /* tp_dealloc */
325 0, /* tp_print */
326 0, /* tp_getattr */
327 0, /* tp_setattr */
328 0, /* tp_compare */
329 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 */
355 (initproc)cache_init, /* tp_init */
356 0, /* tp_alloc */
357 0, /* tp_new */
358 0 /* tp_free */
359};
360
361extern int cache_setup_types(void)
362{
363 int rc;
364
365 NodeType.tp_new = PyType_GenericNew;
366 CacheType.tp_new = PyType_GenericNew;
367
368 rc = PyType_Ready(&NodeType);
369 if (rc < 0) {
370 return rc;
371 }
372
373 rc = PyType_Ready(&CacheType);
374 return rc;
375}
Note: See TracBrowser for help on using the repository browser.