From 4189e53a881e52de0945375a72b8748143c5bd13 Mon Sep 17 00:00:00 2001 From: Kali Kaneko Date: Mon, 4 Feb 2013 19:20:12 +0900 Subject: initial commit --- src/cache.c | 375 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 375 insertions(+) create mode 100644 src/cache.c (limited to 'src/cache.c') 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 + * + * 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 + +/* 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; +} -- cgit v1.2.3