summaryrefslogtreecommitdiff
path: root/src/cache.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/cache.c')
-rw-r--r--src/cache.c375
1 files changed, 375 insertions, 0 deletions
diff --git a/src/cache.c b/src/cache.c
new file mode 100644
index 0000000..0653367
--- /dev/null
+++ b/src/cache.c
@@ -0,0 +1,375 @@
+/* cache .c - a LRU cache
+ *
+ * Copyright (C) 2004-2010 Gerhard Häring <gh@ghaering.de>
+ *
+ * This file is part of pysqlite.
+ *
+ * This software is provided 'as-is', without any express or implied
+ * warranty. In no event will the authors be held liable for any damages
+ * arising from the use of this software.
+ *
+ * Permission is granted to anyone to use this software for any purpose,
+ * including commercial applications, and to alter it and redistribute it
+ * freely, subject to the following restrictions:
+ *
+ * 1. The origin of this software must not be misrepresented; you must not
+ * claim that you wrote the original software. If you use this software
+ * in a product, an acknowledgment in the product documentation would be
+ * appreciated but is not required.
+ * 2. Altered source versions must be plainly marked as such, and must not be
+ * misrepresented as being the original software.
+ * 3. This notice may not be removed or altered from any source distribution.
+ */
+
+#include "sqlitecompat.h"
+#include "cache.h"
+#include <limits.h>
+
+/* only used internally */
+pysqlite_Node* pysqlite_new_node(PyObject* key, PyObject* data)
+{
+ pysqlite_Node* node;
+
+ node = (pysqlite_Node*) (pysqlite_NodeType.tp_alloc(&pysqlite_NodeType, 0));
+ if (!node) {
+ return NULL;
+ }
+
+ Py_INCREF(key);
+ node->key = key;
+
+ Py_INCREF(data);
+ node->data = data;
+
+ node->prev = NULL;
+ node->next = NULL;
+
+ return node;
+}
+
+void pysqlite_node_dealloc(pysqlite_Node* self)
+{
+ Py_DECREF(self->key);
+ Py_DECREF(self->data);
+
+ Py_TYPE(self)->tp_free((PyObject*)self);
+}
+
+int pysqlite_cache_init(pysqlite_Cache* self, PyObject* args, PyObject* kwargs)
+{
+ PyObject* factory;
+ int size = 10;
+
+ self->factory = NULL;
+
+ if (!PyArg_ParseTuple(args, "O|i", &factory, &size)) {
+ return -1;
+ }
+
+ /* minimum cache size is 5 entries */
+ if (size < 5) {
+ size = 5;
+ }
+ self->size = size;
+ self->first = NULL;
+ self->last = NULL;
+
+ self->mapping = PyDict_New();
+ if (!self->mapping) {
+ return -1;
+ }
+
+ Py_INCREF(factory);
+ self->factory = factory;
+
+ self->decref_factory = 1;
+
+ return 0;
+}
+
+void pysqlite_cache_dealloc(pysqlite_Cache* self)
+{
+ pysqlite_Node* node;
+ pysqlite_Node* delete_node;
+
+ if (!self->factory) {
+ /* constructor failed, just get out of here */
+ return;
+ }
+
+ /* iterate over all nodes and deallocate them */
+ node = self->first;
+ while (node) {
+ delete_node = node;
+ node = node->next;
+ Py_DECREF(delete_node);
+ }
+
+ if (self->decref_factory) {
+ Py_DECREF(self->factory);
+ }
+ Py_DECREF(self->mapping);
+
+ Py_TYPE(self)->tp_free((PyObject*)self);
+}
+
+PyObject* pysqlite_cache_get(pysqlite_Cache* self, PyObject* args)
+{
+ PyObject* key = args;
+ pysqlite_Node* node;
+ pysqlite_Node* ptr;
+ PyObject* data;
+
+ node = (pysqlite_Node*)PyDict_GetItem(self->mapping, key);
+ if (node) {
+ /* an entry for this key already exists in the cache */
+
+ /* increase usage counter of the node found */
+ if (node->count < LONG_MAX) {
+ node->count++;
+ }
+
+ /* if necessary, reorder entries in the cache by swapping positions */
+ if (node->prev && node->count > node->prev->count) {
+ ptr = node->prev;
+
+ while (ptr->prev && node->count > ptr->prev->count) {
+ ptr = ptr->prev;
+ }
+
+ if (node->next) {
+ node->next->prev = node->prev;
+ } else {
+ self->last = node->prev;
+ }
+ if (node->prev) {
+ node->prev->next = node->next;
+ }
+ if (ptr->prev) {
+ ptr->prev->next = node;
+ } else {
+ self->first = node;
+ }
+
+ node->next = ptr;
+ node->prev = ptr->prev;
+ if (!node->prev) {
+ self->first = node;
+ }
+ ptr->prev = node;
+ }
+ } else {
+ /* There is no entry for this key in the cache, yet. We'll insert a new
+ * entry in the cache, and make space if necessary by throwing the
+ * least used item out of the cache. */
+
+ if (PyDict_Size(self->mapping) == self->size) {
+ if (self->last) {
+ node = self->last;
+
+ if (PyDict_DelItem(self->mapping, self->last->key) != 0) {
+ return NULL;
+ }
+
+ if (node->prev) {
+ node->prev->next = NULL;
+ }
+ self->last = node->prev;
+ node->prev = NULL;
+
+ Py_DECREF(node);
+ }
+ }
+
+ data = PyObject_CallFunction(self->factory, "O", key);
+
+ if (!data) {
+ return NULL;
+ }
+
+ node = pysqlite_new_node(key, data);
+ if (!node) {
+ return NULL;
+ }
+ node->prev = self->last;
+
+ Py_DECREF(data);
+
+ if (PyDict_SetItem(self->mapping, key, (PyObject*)node) != 0) {
+ Py_DECREF(node);
+ return NULL;
+ }
+
+ if (self->last) {
+ self->last->next = node;
+ } else {
+ self->first = node;
+ }
+ self->last = node;
+ }
+
+ Py_INCREF(node->data);
+ return node->data;
+}
+
+PyObject* pysqlite_cache_display(pysqlite_Cache* self, PyObject* args)
+{
+ pysqlite_Node* ptr;
+ PyObject* prevkey;
+ PyObject* nextkey;
+ PyObject* fmt_args;
+ PyObject* template;
+ PyObject* display_str;
+
+ ptr = self->first;
+
+ while (ptr) {
+ if (ptr->prev) {
+ prevkey = ptr->prev->key;
+ } else {
+ prevkey = Py_None;
+ }
+ Py_INCREF(prevkey);
+
+ if (ptr->next) {
+ nextkey = ptr->next->key;
+ } else {
+ nextkey = Py_None;
+ }
+ Py_INCREF(nextkey);
+
+ fmt_args = Py_BuildValue("OOO", prevkey, ptr->key, nextkey);
+ if (!fmt_args) {
+ return NULL;
+ }
+ template = PyString_FromString("%s <- %s ->%s\n");
+ if (!template) {
+ Py_DECREF(fmt_args);
+ return NULL;
+ }
+ display_str = PyString_Format(template, fmt_args);
+ Py_DECREF(template);
+ Py_DECREF(fmt_args);
+ if (!display_str) {
+ return NULL;
+ }
+ PyObject_Print(display_str, stdout, Py_PRINT_RAW);
+ Py_DECREF(display_str);
+
+ Py_DECREF(prevkey);
+ Py_DECREF(nextkey);
+
+ ptr = ptr->next;
+ }
+
+ Py_INCREF(Py_None);
+ return Py_None;
+}
+
+static PyMethodDef cache_methods[] = {
+ {"get", (PyCFunction)pysqlite_cache_get, METH_O,
+ PyDoc_STR("Gets an entry from the cache or calls the factory function to produce one.")},
+ {"display", (PyCFunction)pysqlite_cache_display, METH_NOARGS,
+ PyDoc_STR("For debugging only.")},
+ {NULL, NULL}
+};
+
+PyTypeObject pysqlite_NodeType = {
+ PyVarObject_HEAD_INIT(NULL, 0)
+ MODULE_NAME "Node", /* tp_name */
+ sizeof(pysqlite_Node), /* tp_basicsize */
+ 0, /* tp_itemsize */
+ (destructor)pysqlite_node_dealloc, /* tp_dealloc */
+ 0, /* tp_print */
+ 0, /* tp_getattr */
+ 0, /* tp_setattr */
+ 0, /* tp_compare */
+ 0, /* tp_repr */
+ 0, /* tp_as_number */
+ 0, /* tp_as_sequence */
+ 0, /* tp_as_mapping */
+ 0, /* tp_hash */
+ 0, /* tp_call */
+ 0, /* tp_str */
+ 0, /* tp_getattro */
+ 0, /* tp_setattro */
+ 0, /* tp_as_buffer */
+ Py_TPFLAGS_DEFAULT|Py_TPFLAGS_BASETYPE, /* tp_flags */
+ 0, /* tp_doc */
+ 0, /* tp_traverse */
+ 0, /* tp_clear */
+ 0, /* tp_richcompare */
+ 0, /* tp_weaklistoffset */
+ 0, /* tp_iter */
+ 0, /* tp_iternext */
+ 0, /* tp_methods */
+ 0, /* tp_members */
+ 0, /* tp_getset */
+ 0, /* tp_base */
+ 0, /* tp_dict */
+ 0, /* tp_descr_get */
+ 0, /* tp_descr_set */
+ 0, /* tp_dictoffset */
+ (initproc)0, /* tp_init */
+ 0, /* tp_alloc */
+ 0, /* tp_new */
+ 0 /* tp_free */
+};
+
+PyTypeObject pysqlite_CacheType = {
+ PyVarObject_HEAD_INIT(NULL, 0)
+ MODULE_NAME ".Cache", /* tp_name */
+ sizeof(pysqlite_Cache), /* tp_basicsize */
+ 0, /* tp_itemsize */
+ (destructor)pysqlite_cache_dealloc, /* tp_dealloc */
+ 0, /* tp_print */
+ 0, /* tp_getattr */
+ 0, /* tp_setattr */
+ 0, /* tp_compare */
+ 0, /* tp_repr */
+ 0, /* tp_as_number */
+ 0, /* tp_as_sequence */
+ 0, /* tp_as_mapping */
+ 0, /* tp_hash */
+ 0, /* tp_call */
+ 0, /* tp_str */
+ 0, /* tp_getattro */
+ 0, /* tp_setattro */
+ 0, /* tp_as_buffer */
+ Py_TPFLAGS_DEFAULT|Py_TPFLAGS_BASETYPE, /* tp_flags */
+ 0, /* tp_doc */
+ 0, /* tp_traverse */
+ 0, /* tp_clear */
+ 0, /* tp_richcompare */
+ 0, /* tp_weaklistoffset */
+ 0, /* tp_iter */
+ 0, /* tp_iternext */
+ cache_methods, /* tp_methods */
+ 0, /* tp_members */
+ 0, /* tp_getset */
+ 0, /* tp_base */
+ 0, /* tp_dict */
+ 0, /* tp_descr_get */
+ 0, /* tp_descr_set */
+ 0, /* tp_dictoffset */
+ (initproc)pysqlite_cache_init, /* tp_init */
+ 0, /* tp_alloc */
+ 0, /* tp_new */
+ 0 /* tp_free */
+};
+
+extern int pysqlite_cache_setup_types(void)
+{
+ int rc;
+
+ pysqlite_NodeType.tp_new = PyType_GenericNew;
+ pysqlite_CacheType.tp_new = PyType_GenericNew;
+
+ rc = PyType_Ready(&pysqlite_NodeType);
+ if (rc < 0) {
+ return rc;
+ }
+
+ rc = PyType_Ready(&pysqlite_CacheType);
+ return rc;
+}
generated by cgit v1.2.3 (git 2.25.1) at 2024-04-27 06:02:00 +0000