»Core Development>Code coverage>Modules/_sqlite/cache.c

Python code coverage for Modules/_sqlite/cache.c

#countcontent
1n/a/* cache .c - a LRU cache
2n/a *
3n/a * Copyright (C) 2004-2010 Gerhard Häring <gh@ghaering.de>
4n/a *
5n/a * This file is part of pysqlite.
6n/a *
7n/a * This software is provided 'as-is', without any express or implied
8n/a * warranty. In no event will the authors be held liable for any damages
9n/a * arising from the use of this software.
10n/a *
11n/a * Permission is granted to anyone to use this software for any purpose,
12n/a * including commercial applications, and to alter it and redistribute it
13n/a * freely, subject to the following restrictions:
14n/a *
15n/a * 1. The origin of this software must not be misrepresented; you must not
16n/a * claim that you wrote the original software. If you use this software
17n/a * in a product, an acknowledgment in the product documentation would be
18n/a * appreciated but is not required.
19n/a * 2. Altered source versions must be plainly marked as such, and must not be
20n/a * misrepresented as being the original software.
21n/a * 3. This notice may not be removed or altered from any source distribution.
22n/a */
23n/a
24n/a#include "cache.h"
25n/a#include <limits.h>
26n/a
27n/a/* only used internally */
28n/apysqlite_Node* pysqlite_new_node(PyObject* key, PyObject* data)
29n/a{
30n/a pysqlite_Node* node;
31n/a
32n/a node = (pysqlite_Node*) (pysqlite_NodeType.tp_alloc(&pysqlite_NodeType, 0));
33n/a if (!node) {
34n/a return NULL;
35n/a }
36n/a
37n/a Py_INCREF(key);
38n/a node->key = key;
39n/a
40n/a Py_INCREF(data);
41n/a node->data = data;
42n/a
43n/a node->prev = NULL;
44n/a node->next = NULL;
45n/a
46n/a return node;
47n/a}
48n/a
49n/avoid pysqlite_node_dealloc(pysqlite_Node* self)
50n/a{
51n/a Py_DECREF(self->key);
52n/a Py_DECREF(self->data);
53n/a
54n/a Py_TYPE(self)->tp_free((PyObject*)self);
55n/a}
56n/a
57n/aint pysqlite_cache_init(pysqlite_Cache* self, PyObject* args, PyObject* kwargs)
58n/a{
59n/a PyObject* factory;
60n/a int size = 10;
61n/a
62n/a self->factory = NULL;
63n/a
64n/a if (!PyArg_ParseTuple(args, "O|i", &factory, &size)) {
65n/a return -1;
66n/a }
67n/a
68n/a /* minimum cache size is 5 entries */
69n/a if (size < 5) {
70n/a size = 5;
71n/a }
72n/a self->size = size;
73n/a self->first = NULL;
74n/a self->last = NULL;
75n/a
76n/a self->mapping = PyDict_New();
77n/a if (!self->mapping) {
78n/a return -1;
79n/a }
80n/a
81n/a Py_INCREF(factory);
82n/a self->factory = factory;
83n/a
84n/a self->decref_factory = 1;
85n/a
86n/a return 0;
87n/a}
88n/a
89n/avoid pysqlite_cache_dealloc(pysqlite_Cache* self)
90n/a{
91n/a pysqlite_Node* node;
92n/a pysqlite_Node* delete_node;
93n/a
94n/a if (!self->factory) {
95n/a /* constructor failed, just get out of here */
96n/a return;
97n/a }
98n/a
99n/a /* iterate over all nodes and deallocate them */
100n/a node = self->first;
101n/a while (node) {
102n/a delete_node = node;
103n/a node = node->next;
104n/a Py_DECREF(delete_node);
105n/a }
106n/a
107n/a if (self->decref_factory) {
108n/a Py_DECREF(self->factory);
109n/a }
110n/a Py_DECREF(self->mapping);
111n/a
112n/a Py_TYPE(self)->tp_free((PyObject*)self);
113n/a}
114n/a
115n/aPyObject* pysqlite_cache_get(pysqlite_Cache* self, PyObject* args)
116n/a{
117n/a PyObject* key = args;
118n/a pysqlite_Node* node;
119n/a pysqlite_Node* ptr;
120n/a PyObject* data;
121n/a
122n/a node = (pysqlite_Node*)PyDict_GetItem(self->mapping, key);
123n/a if (node) {
124n/a /* an entry for this key already exists in the cache */
125n/a
126n/a /* increase usage counter of the node found */
127n/a if (node->count < LONG_MAX) {
128n/a node->count++;
129n/a }
130n/a
131n/a /* if necessary, reorder entries in the cache by swapping positions */
132n/a if (node->prev && node->count > node->prev->count) {
133n/a ptr = node->prev;
134n/a
135n/a while (ptr->prev && node->count > ptr->prev->count) {
136n/a ptr = ptr->prev;
137n/a }
138n/a
139n/a if (node->next) {
140n/a node->next->prev = node->prev;
141n/a } else {
142n/a self->last = node->prev;
143n/a }
144n/a if (node->prev) {
145n/a node->prev->next = node->next;
146n/a }
147n/a if (ptr->prev) {
148n/a ptr->prev->next = node;
149n/a } else {
150n/a self->first = node;
151n/a }
152n/a
153n/a node->next = ptr;
154n/a node->prev = ptr->prev;
155n/a if (!node->prev) {
156n/a self->first = node;
157n/a }
158n/a ptr->prev = node;
159n/a }
160n/a } else {
161n/a /* There is no entry for this key in the cache, yet. We'll insert a new
162n/a * entry in the cache, and make space if necessary by throwing the
163n/a * least used item out of the cache. */
164n/a
165n/a if (PyDict_GET_SIZE(self->mapping) == self->size) {
166n/a if (self->last) {
167n/a node = self->last;
168n/a
169n/a if (PyDict_DelItem(self->mapping, self->last->key) != 0) {
170n/a return NULL;
171n/a }
172n/a
173n/a if (node->prev) {
174n/a node->prev->next = NULL;
175n/a }
176n/a self->last = node->prev;
177n/a node->prev = NULL;
178n/a
179n/a Py_DECREF(node);
180n/a }
181n/a }
182n/a
183n/a data = PyObject_CallFunction(self->factory, "O", key);
184n/a
185n/a if (!data) {
186n/a return NULL;
187n/a }
188n/a
189n/a node = pysqlite_new_node(key, data);
190n/a if (!node) {
191n/a return NULL;
192n/a }
193n/a node->prev = self->last;
194n/a
195n/a Py_DECREF(data);
196n/a
197n/a if (PyDict_SetItem(self->mapping, key, (PyObject*)node) != 0) {
198n/a Py_DECREF(node);
199n/a return NULL;
200n/a }
201n/a
202n/a if (self->last) {
203n/a self->last->next = node;
204n/a } else {
205n/a self->first = node;
206n/a }
207n/a self->last = node;
208n/a }
209n/a
210n/a Py_INCREF(node->data);
211n/a return node->data;
212n/a}
213n/a
214n/aPyObject* pysqlite_cache_display(pysqlite_Cache* self, PyObject* args)
215n/a{
216n/a pysqlite_Node* ptr;
217n/a PyObject* prevkey;
218n/a PyObject* nextkey;
219n/a PyObject* display_str;
220n/a
221n/a ptr = self->first;
222n/a
223n/a while (ptr) {
224n/a if (ptr->prev) {
225n/a prevkey = ptr->prev->key;
226n/a } else {
227n/a prevkey = Py_None;
228n/a }
229n/a
230n/a if (ptr->next) {
231n/a nextkey = ptr->next->key;
232n/a } else {
233n/a nextkey = Py_None;
234n/a }
235n/a
236n/a display_str = PyUnicode_FromFormat("%S <- %S -> %S\n",
237n/a prevkey, ptr->key, nextkey);
238n/a if (!display_str) {
239n/a return NULL;
240n/a }
241n/a PyObject_Print(display_str, stdout, Py_PRINT_RAW);
242n/a Py_DECREF(display_str);
243n/a
244n/a ptr = ptr->next;
245n/a }
246n/a
247n/a Py_RETURN_NONE;
248n/a}
249n/a
250n/astatic PyMethodDef cache_methods[] = {
251n/a {"get", (PyCFunction)pysqlite_cache_get, METH_O,
252n/a PyDoc_STR("Gets an entry from the cache or calls the factory function to produce one.")},
253n/a {"display", (PyCFunction)pysqlite_cache_display, METH_NOARGS,
254n/a PyDoc_STR("For debugging only.")},
255n/a {NULL, NULL}
256n/a};
257n/a
258n/aPyTypeObject pysqlite_NodeType = {
259n/a PyVarObject_HEAD_INIT(NULL, 0)
260n/a MODULE_NAME "Node", /* tp_name */
261n/a sizeof(pysqlite_Node), /* tp_basicsize */
262n/a 0, /* tp_itemsize */
263n/a (destructor)pysqlite_node_dealloc, /* tp_dealloc */
264n/a 0, /* tp_print */
265n/a 0, /* tp_getattr */
266n/a 0, /* tp_setattr */
267n/a 0, /* tp_reserved */
268n/a 0, /* tp_repr */
269n/a 0, /* tp_as_number */
270n/a 0, /* tp_as_sequence */
271n/a 0, /* tp_as_mapping */
272n/a 0, /* tp_hash */
273n/a 0, /* tp_call */
274n/a 0, /* tp_str */
275n/a 0, /* tp_getattro */
276n/a 0, /* tp_setattro */
277n/a 0, /* tp_as_buffer */
278n/a Py_TPFLAGS_DEFAULT|Py_TPFLAGS_BASETYPE, /* tp_flags */
279n/a 0, /* tp_doc */
280n/a 0, /* tp_traverse */
281n/a 0, /* tp_clear */
282n/a 0, /* tp_richcompare */
283n/a 0, /* tp_weaklistoffset */
284n/a 0, /* tp_iter */
285n/a 0, /* tp_iternext */
286n/a 0, /* tp_methods */
287n/a 0, /* tp_members */
288n/a 0, /* tp_getset */
289n/a 0, /* tp_base */
290n/a 0, /* tp_dict */
291n/a 0, /* tp_descr_get */
292n/a 0, /* tp_descr_set */
293n/a 0, /* tp_dictoffset */
294n/a (initproc)0, /* tp_init */
295n/a 0, /* tp_alloc */
296n/a 0, /* tp_new */
297n/a 0 /* tp_free */
298n/a};
299n/a
300n/aPyTypeObject pysqlite_CacheType = {
301n/a PyVarObject_HEAD_INIT(NULL, 0)
302n/a MODULE_NAME ".Cache", /* tp_name */
303n/a sizeof(pysqlite_Cache), /* tp_basicsize */
304n/a 0, /* tp_itemsize */
305n/a (destructor)pysqlite_cache_dealloc, /* tp_dealloc */
306n/a 0, /* tp_print */
307n/a 0, /* tp_getattr */
308n/a 0, /* tp_setattr */
309n/a 0, /* tp_reserved */
310n/a 0, /* tp_repr */
311n/a 0, /* tp_as_number */
312n/a 0, /* tp_as_sequence */
313n/a 0, /* tp_as_mapping */
314n/a 0, /* tp_hash */
315n/a 0, /* tp_call */
316n/a 0, /* tp_str */
317n/a 0, /* tp_getattro */
318n/a 0, /* tp_setattro */
319n/a 0, /* tp_as_buffer */
320n/a Py_TPFLAGS_DEFAULT|Py_TPFLAGS_BASETYPE, /* tp_flags */
321n/a 0, /* tp_doc */
322n/a 0, /* tp_traverse */
323n/a 0, /* tp_clear */
324n/a 0, /* tp_richcompare */
325n/a 0, /* tp_weaklistoffset */
326n/a 0, /* tp_iter */
327n/a 0, /* tp_iternext */
328n/a cache_methods, /* tp_methods */
329n/a 0, /* tp_members */
330n/a 0, /* tp_getset */
331n/a 0, /* tp_base */
332n/a 0, /* tp_dict */
333n/a 0, /* tp_descr_get */
334n/a 0, /* tp_descr_set */
335n/a 0, /* tp_dictoffset */
336n/a (initproc)pysqlite_cache_init, /* tp_init */
337n/a 0, /* tp_alloc */
338n/a 0, /* tp_new */
339n/a 0 /* tp_free */
340n/a};
341n/a
342n/aextern int pysqlite_cache_setup_types(void)
343n/a{
344n/a int rc;
345n/a
346n/a pysqlite_NodeType.tp_new = PyType_GenericNew;
347n/a pysqlite_CacheType.tp_new = PyType_GenericNew;
348n/a
349n/a rc = PyType_Ready(&pysqlite_NodeType);
350n/a if (rc < 0) {
351n/a return rc;
352n/a }
353n/a
354n/a rc = PyType_Ready(&pysqlite_CacheType);
355n/a return rc;
356n/a}