Modules/_sqlite/cache.c

   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 }