1/* cache .c - a LRU cache
2 *
3 * Copyright (C) 2004-2010 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 "sqlitecompat.h"
25#include "cache.h"
26#include <limits.h>
27
28/* only used internally */
29pysqlite_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
50void 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
58int 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
90void 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
116PyObject* 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
215PyObject* 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
269static 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
277PyTypeObject 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
319PyTypeObject 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
361extern 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