1 /* cache .c - a LRU cache
3 * Copyright (C) 2004-2007 Gerhard Häring <gh@ghaering.de>
5 * This file is part of pysqlite.
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.
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:
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.
27 /* only used internally */
28 pysqlite_Node
* pysqlite_new_node(PyObject
* key
, PyObject
* data
)
32 node
= (pysqlite_Node
*) (pysqlite_NodeType
.tp_alloc(&pysqlite_NodeType
, 0));
49 void pysqlite_node_dealloc(pysqlite_Node
* self
)
52 Py_DECREF(self
->data
);
54 Py_TYPE(self
)->tp_free((PyObject
*)self
);
57 int pysqlite_cache_init(pysqlite_Cache
* self
, PyObject
* args
, PyObject
* kwargs
)
64 if (!PyArg_ParseTuple(args
, "O|i", &factory
, &size
)) {
68 /* minimum cache size is 5 entries */
76 self
->mapping
= PyDict_New();
82 self
->factory
= factory
;
84 self
->decref_factory
= 1;
89 void pysqlite_cache_dealloc(pysqlite_Cache
* self
)
92 pysqlite_Node
* delete_node
;
95 /* constructor failed, just get out of here */
99 /* iterate over all nodes and deallocate them */
104 Py_DECREF(delete_node
);
107 if (self
->decref_factory
) {
108 Py_DECREF(self
->factory
);
110 Py_DECREF(self
->mapping
);
112 Py_TYPE(self
)->tp_free((PyObject
*)self
);
115 PyObject
* pysqlite_cache_get(pysqlite_Cache
* self
, PyObject
* args
)
117 PyObject
* key
= args
;
122 node
= (pysqlite_Node
*)PyDict_GetItem(self
->mapping
, key
);
124 /* an entry for this key already exists in the cache */
126 /* increase usage counter of the node found */
127 if (node
->count
< LONG_MAX
) {
131 /* if necessary, reorder entries in the cache by swapping positions */
132 if (node
->prev
&& node
->count
> node
->prev
->count
) {
135 while (ptr
->prev
&& node
->count
> ptr
->prev
->count
) {
140 node
->next
->prev
= node
->prev
;
142 self
->last
= node
->prev
;
145 node
->prev
->next
= node
->next
;
148 ptr
->prev
->next
= node
;
154 node
->prev
= ptr
->prev
;
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. */
165 if (PyDict_Size(self
->mapping
) == self
->size
) {
169 if (PyDict_DelItem(self
->mapping
, self
->last
->key
) != 0) {
174 node
->prev
->next
= NULL
;
176 self
->last
= node
->prev
;
183 data
= PyObject_CallFunction(self
->factory
, "O", key
);
189 node
= pysqlite_new_node(key
, data
);
193 node
->prev
= self
->last
;
197 if (PyDict_SetItem(self
->mapping
, key
, (PyObject
*)node
) != 0) {
203 self
->last
->next
= node
;
210 Py_INCREF(node
->data
);
214 PyObject
* pysqlite_cache_display(pysqlite_Cache
* self
, PyObject
* args
)
221 PyObject
* display_str
;
227 prevkey
= ptr
->prev
->key
;
234 nextkey
= ptr
->next
->key
;
240 fmt_args
= Py_BuildValue("OOO", prevkey
, ptr
->key
, nextkey
);
244 template = PyString_FromString("%s <- %s ->%s\n");
249 display_str
= PyString_Format(template, fmt_args
);
255 PyObject_Print(display_str
, stdout
, Py_PRINT_RAW
);
256 Py_DECREF(display_str
);
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.")},
276 PyTypeObject pysqlite_NodeType
= {
277 PyVarObject_HEAD_INIT(NULL
, 0)
278 MODULE_NAME
"Node", /* tp_name */
279 sizeof(pysqlite_Node
), /* tp_basicsize */
281 (destructor
)pysqlite_node_dealloc
, /* tp_dealloc */
287 0, /* tp_as_number */
288 0, /* tp_as_sequence */
289 0, /* tp_as_mapping */
295 0, /* tp_as_buffer */
296 Py_TPFLAGS_DEFAULT
|Py_TPFLAGS_BASETYPE
, /* tp_flags */
300 0, /* tp_richcompare */
301 0, /* tp_weaklistoffset */
309 0, /* tp_descr_get */
310 0, /* tp_descr_set */
311 0, /* tp_dictoffset */
312 (initproc
)0, /* tp_init */
318 PyTypeObject pysqlite_CacheType
= {
319 PyVarObject_HEAD_INIT(NULL
, 0)
320 MODULE_NAME
".Cache", /* tp_name */
321 sizeof(pysqlite_Cache
), /* tp_basicsize */
323 (destructor
)pysqlite_cache_dealloc
, /* tp_dealloc */
329 0, /* tp_as_number */
330 0, /* tp_as_sequence */
331 0, /* tp_as_mapping */
337 0, /* tp_as_buffer */
338 Py_TPFLAGS_DEFAULT
|Py_TPFLAGS_BASETYPE
, /* tp_flags */
342 0, /* tp_richcompare */
343 0, /* tp_weaklistoffset */
346 cache_methods
, /* tp_methods */
351 0, /* tp_descr_get */
352 0, /* tp_descr_set */
353 0, /* tp_dictoffset */
354 (initproc
)pysqlite_cache_init
, /* tp_init */
360 extern int pysqlite_cache_setup_types(void)
364 pysqlite_NodeType
.tp_new
= PyType_GenericNew
;
365 pysqlite_CacheType
.tp_new
= PyType_GenericNew
;
367 rc
= PyType_Ready(&pysqlite_NodeType
);
372 rc
= PyType_Ready(&pysqlite_CacheType
);