cache.c 13 KB

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