1 /* cache .c - a LRU cache 2 * 3 * Copyright (C) 2004-2010 Gerhard Hring <gh (at) 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 "sqlitecompat.h" 25 #include "cache.h" 26 #include <limits.h> 27 28 /* only used internally */ 29 pysqlite_Node* pysqlite_new_node(PyObject* key, PyObject* data) 30 { 31 pysqlite_Node* node; 32 33 node = (pysqlite_Node*) (pysqlite_NodeType.tp_alloc(&pysqlite_NodeType, 0)); 34 if (!node) { 35 return NULL; 36 } 37 38 Py_INCREF(key); 39 node->key = key; 40 41 Py_INCREF(data); 42 node->data = data; 43 44 node->prev = NULL; 45 node->next = NULL; 46 47 return node; 48 } 49 50 void pysqlite_node_dealloc(pysqlite_Node* self) 51 { 52 Py_DECREF(self->key); 53 Py_DECREF(self->data); 54 55 Py_TYPE(self)->tp_free((PyObject*)self); 56 } 57 58 int pysqlite_cache_init(pysqlite_Cache* self, PyObject* args, PyObject* kwargs) 59 { 60 PyObject* factory; 61 int size = 10; 62 63 self->factory = NULL; 64 65 if (!PyArg_ParseTuple(args, "O|i", &factory, &size)) { 66 return -1; 67 } 68 69 /* minimum cache size is 5 entries */ 70 if (size < 5) { 71 size = 5; 72 } 73 self->size = size; 74 self->first = NULL; 75 self->last = NULL; 76 77 self->mapping = PyDict_New(); 78 if (!self->mapping) { 79 return -1; 80 } 81 82 Py_INCREF(factory); 83 self->factory = factory; 84 85 self->decref_factory = 1; 86 87 return 0; 88 } 89 90 void pysqlite_cache_dealloc(pysqlite_Cache* self) 91 { 92 pysqlite_Node* node; 93 pysqlite_Node* delete_node; 94 95 if (!self->factory) { 96 /* constructor failed, just get out of here */ 97 return; 98 } 99 100 /* iterate over all nodes and deallocate them */ 101 node = self->first; 102 while (node) { 103 delete_node = node; 104 node = node->next; 105 Py_DECREF(delete_node); 106 } 107 108 if (self->decref_factory) { 109 Py_DECREF(self->factory); 110 } 111 Py_DECREF(self->mapping); 112 113 Py_TYPE(self)->tp_free((PyObject*)self); 114 } 115 116 PyObject* pysqlite_cache_get(pysqlite_Cache* self, PyObject* args) 117 { 118 PyObject* key = args; 119 pysqlite_Node* node; 120 pysqlite_Node* ptr; 121 PyObject* data; 122 123 node = (pysqlite_Node*)PyDict_GetItem(self->mapping, key); 124 if (node) { 125 /* an entry for this key already exists in the cache */ 126 127 /* increase usage counter of the node found */ 128 if (node->count < LONG_MAX) { 129 node->count++; 130 } 131 132 /* if necessary, reorder entries in the cache by swapping positions */ 133 if (node->prev && node->count > node->prev->count) { 134 ptr = node->prev; 135 136 while (ptr->prev && node->count > ptr->prev->count) { 137 ptr = ptr->prev; 138 } 139 140 if (node->next) { 141 node->next->prev = node->prev; 142 } else { 143 self->last = node->prev; 144 } 145 if (node->prev) { 146 node->prev->next = node->next; 147 } 148 if (ptr->prev) { 149 ptr->prev->next = node; 150 } else { 151 self->first = node; 152 } 153 154 node->next = ptr; 155 node->prev = ptr->prev; 156 if (!node->prev) { 157 self->first = node; 158 } 159 ptr->prev = node; 160 } 161 } else { 162 /* There is no entry for this key in the cache, yet. We'll insert a new 163 * entry in the cache, and make space if necessary by throwing the 164 * least used item out of the cache. */ 165 166 if (PyDict_Size(self->mapping) == self->size) { 167 if (self->last) { 168 node = self->last; 169 170 if (PyDict_DelItem(self->mapping, self->last->key) != 0) { 171 return NULL; 172 } 173 174 if (node->prev) { 175 node->prev->next = NULL; 176 } 177 self->last = node->prev; 178 node->prev = NULL; 179 180 Py_DECREF(node); 181 } 182 } 183 184 data = PyObject_CallFunction(self->factory, "O", key); 185 186 if (!data) { 187 return NULL; 188 } 189 190 node = pysqlite_new_node(key, data); 191 if (!node) { 192 return NULL; 193 } 194 node->prev = self->last; 195 196 Py_DECREF(data); 197 198 if (PyDict_SetItem(self->mapping, key, (PyObject*)node) != 0) { 199 Py_DECREF(node); 200 return NULL; 201 } 202 203 if (self->last) { 204 self->last->next = node; 205 } else { 206 self->first = node; 207 } 208 self->last = node; 209 } 210 211 Py_INCREF(node->data); 212 return node->data; 213 } 214 215 PyObject* pysqlite_cache_display(pysqlite_Cache* self, PyObject* args) 216 { 217 pysqlite_Node* ptr; 218 PyObject* prevkey; 219 PyObject* nextkey; 220 PyObject* fmt_args; 221 PyObject* template; 222 PyObject* display_str; 223 224 ptr = self->first; 225 226 while (ptr) { 227 if (ptr->prev) { 228 prevkey = ptr->prev->key; 229 } else { 230 prevkey = Py_None; 231 } 232 Py_INCREF(prevkey); 233 234 if (ptr->next) { 235 nextkey = ptr->next->key; 236 } else { 237 nextkey = Py_None; 238 } 239 Py_INCREF(nextkey); 240 241 fmt_args = Py_BuildValue("OOO", prevkey, ptr->key, nextkey); 242 if (!fmt_args) { 243 return NULL; 244 } 245 template = PyString_FromString("%s <- %s ->%s\n"); 246 if (!template) { 247 Py_DECREF(fmt_args); 248 return NULL; 249 } 250 display_str = PyString_Format(template, fmt_args); 251 Py_DECREF(template); 252 Py_DECREF(fmt_args); 253 if (!display_str) { 254 return NULL; 255 } 256 PyObject_Print(display_str, stdout, Py_PRINT_RAW); 257 Py_DECREF(display_str); 258 259 Py_DECREF(prevkey); 260 Py_DECREF(nextkey); 261 262 ptr = ptr->next; 263 } 264 265 Py_INCREF(Py_None); 266 return Py_None; 267 } 268 269 static PyMethodDef cache_methods[] = { 270 {"get", (PyCFunction)pysqlite_cache_get, METH_O, 271 PyDoc_STR("Gets an entry from the cache or calls the factory function to produce one.")}, 272 {"display", (PyCFunction)pysqlite_cache_display, METH_NOARGS, 273 PyDoc_STR("For debugging only.")}, 274 {NULL, NULL} 275 }; 276 277 PyTypeObject pysqlite_NodeType = { 278 PyVarObject_HEAD_INIT(NULL, 0) 279 MODULE_NAME "Node", /* tp_name */ 280 sizeof(pysqlite_Node), /* tp_basicsize */ 281 0, /* tp_itemsize */ 282 (destructor)pysqlite_node_dealloc, /* tp_dealloc */ 283 0, /* tp_print */ 284 0, /* tp_getattr */ 285 0, /* tp_setattr */ 286 0, /* tp_compare */ 287 0, /* tp_repr */ 288 0, /* tp_as_number */ 289 0, /* tp_as_sequence */ 290 0, /* tp_as_mapping */ 291 0, /* tp_hash */ 292 0, /* tp_call */ 293 0, /* tp_str */ 294 0, /* tp_getattro */ 295 0, /* tp_setattro */ 296 0, /* tp_as_buffer */ 297 Py_TPFLAGS_DEFAULT|Py_TPFLAGS_BASETYPE, /* tp_flags */ 298 0, /* tp_doc */ 299 0, /* tp_traverse */ 300 0, /* tp_clear */ 301 0, /* tp_richcompare */ 302 0, /* tp_weaklistoffset */ 303 0, /* tp_iter */ 304 0, /* tp_iternext */ 305 0, /* tp_methods */ 306 0, /* tp_members */ 307 0, /* tp_getset */ 308 0, /* tp_base */ 309 0, /* tp_dict */ 310 0, /* tp_descr_get */ 311 0, /* tp_descr_set */ 312 0, /* tp_dictoffset */ 313 (initproc)0, /* tp_init */ 314 0, /* tp_alloc */ 315 0, /* tp_new */ 316 0 /* tp_free */ 317 }; 318 319 PyTypeObject pysqlite_CacheType = { 320 PyVarObject_HEAD_INIT(NULL, 0) 321 MODULE_NAME ".Cache", /* tp_name */ 322 sizeof(pysqlite_Cache), /* tp_basicsize */ 323 0, /* tp_itemsize */ 324 (destructor)pysqlite_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)pysqlite_cache_init, /* tp_init */ 356 0, /* tp_alloc */ 357 0, /* tp_new */ 358 0 /* tp_free */ 359 }; 360 361 extern int pysqlite_cache_setup_types(void) 362 { 363 int rc; 364 365 pysqlite_NodeType.tp_new = PyType_GenericNew; 366 pysqlite_CacheType.tp_new = PyType_GenericNew; 367 368 rc = PyType_Ready(&pysqlite_NodeType); 369 if (rc < 0) { 370 return rc; 371 } 372 373 rc = PyType_Ready(&pysqlite_CacheType); 374 return rc; 375 } 376
