text: /* cache .c - a LRU cache
   *
   * Copyright (C) 2004-2010 Gerhard Häring <gh@ghaering.de>
   *
   * This file is part of pysqlite.
   *
   * This software is provided 'as-is', without any express or implied
   * warranty.  In no event will the authors be held liable for any damages
   * arising from the use of this software.
   *
   * Permission is granted to anyone to use this software for any purpose,
   * including commercial applications, and to alter it and redistribute it
   * freely, subject to the following restrictions:
   *
   * 1. The origin of this software must not be misrepresented; you must not
   *    claim that you wrote the original software. If you use this software
   *    in a product, an acknowledgment in the product documentation would be
   *    appreciated but is not required.
   * 2. Altered source versions must be plainly marked as such, and must not be
   *    misrepresented as being the original software.
   * 3. This notice may not be removed or altered from any source distribution.
   */
  
  #include "cache.h"
  #include <limits.h>
  
  #define PyDict_GET_SIZE(mp)  (assert(PyDict_Check(mp)),Py_SIZE(mp)) // PLASTICITY
  
  /* only used internally */
  pysqlite_Node* pysqlite_new_node(PyObject* key, PyObject* data)
  {
      pysqlite_Node* node;
  
      node = (pysqlite_Node*) (pysqlite_NodeType.tp_alloc(&pysqlite_NodeType, 0));
      if (!node) {
          return NULL;
      }
  
      Py_INCREF(key);
      node->key = key;
  
      Py_INCREF(data);
      node->data = data;
  
      node->prev = NULL;
      node->next = NULL;
  
      return node;
  }
  
  void pysqlite_node_dealloc(pysqlite_Node* self)
  {
      Py_DECREF(self->key);
      Py_DECREF(self->data);
  
      Py_TYPE(self)->tp_free((PyObject*)self);
  }
  
  int pysqlite_cache_init(pysqlite_Cache* self, PyObject* args, PyObject* kwargs)
  {
      PyObject* factory;
      int size = 10;
  
      self->factory = NULL;
  
      if (!PyArg_ParseTuple(args, "O|i", &factory, &size)) {
          return -1;
      }
  
      /* minimum cache size is 5 entries */
      if (size < 5) {
          size = 5;
      }
      self->size = size;
      self->first = NULL;
      self->last = NULL;
  
      self->mapping = PyDict_New();
      if (!self->mapping) {
          return -1;
      }
  
      Py_INCREF(factory);
      self->factory = factory;
  
      self->decref_factory = 1;
  
      return 0;
  }
  
  void pysqlite_cache_dealloc(pysqlite_Cache* self)
  {
      pysqlite_Node* node;
      pysqlite_Node* delete_node;
  
      if (!self->factory) {
          /* constructor failed, just get out of here */
          return;
      }
  
      /* iterate over all nodes and deallocate them */
      node = self->first;
      while (node) {
          delete_node = node;
          node = node->next;
          Py_DECREF(delete_node);
      }
  
      if (self->decref_factory) {
          Py_DECREF(self->factory);
      }
      Py_DECREF(self->mapping);
  
      Py_TYPE(self)->tp_free((PyObject*)self);
  }
  
  PyObject* pysqlite_cache_get(pysqlite_Cache* self, PyObject* args)
  {
      PyObject* key = args;
      pysqlite_Node* node;
      pysqlite_Node* ptr;
      PyObject* data;
  
      node = (pysqlite_Node*)PyDict_GetItem(self->mapping, key);
      if (node) {
          /* an entry for this key already exists in the cache */
  
          /* increase usage counter of the node found */
          if (node->count < LONG_MAX) {
              node->count++;
          }
  
          /* if necessary, reorder entries in the cache by swapping positions */
          if (node->prev && node->count > node->prev->count) {
              ptr = node->prev;
  
              while (ptr->prev && node->count > ptr->prev->count) {
                  ptr = ptr->prev;
              }
  
              if (node->next) {
                  node->next->prev = node->prev;
              } else {
                  self->last = node->prev;
              }
              if (node->prev) {
                  node->prev->next = node->next;
              }
              if (ptr->prev) {
                  ptr->prev->next = node;
              } else {
                  self->first = node;
              }
  
              node->next = ptr;
              node->prev = ptr->prev;
              if (!node->prev) {
                  self->first = node;
              }
              ptr->prev = node;
          }
      } else {
          /* There is no entry for this key in the cache, yet. We'll insert a new
           * entry in the cache, and make space if necessary by throwing the
           * least used item out of the cache. */
  
          if (PyDict_GET_SIZE(self->mapping) == self->size) {
              if (self->last) {
                  node = self->last;
  
                  if (PyDict_DelItem(self->mapping, self->last->key) != 0) {
                      return NULL;
                  }
  
                  if (node->prev) {
                      node->prev->next = NULL;
                  }
                  self->last = node->prev;
                  node->prev = NULL;
  
                  Py_DECREF(node);
              }
          }
  
          data = PyObject_CallFunction(self->factory, "O", key);
  
          if (!data) {
              return NULL;
          }
  
          node = pysqlite_new_node(key, data);
          if (!node) {
              return NULL;
          }
          node->prev = self->last;
  
          Py_DECREF(data);
  
          if (PyDict_SetItem(self->mapping, key, (PyObject*)node) != 0) {
              Py_DECREF(node);
              return NULL;
          }
  
          if (self->last) {
              self->last->next = node;
          } else {
              self->first = node;
          }
          self->last = node;
      }
  
      Py_INCREF(node->data);
      return node->data;
  }
  
  PyObject* pysqlite_cache_display(pysqlite_Cache* self, PyObject* args)
  {
      pysqlite_Node* ptr;
      PyObject* prevkey;
      PyObject* nextkey;
      PyObject* display_str;
  
      ptr = self->first;
  
      while (ptr) {
          if (ptr->prev) {
              prevkey = ptr->prev->key;
          } else {
              prevkey = Py_None;
          }
  
          if (ptr->next) {
              nextkey = ptr->next->key;
          } else {
              nextkey = Py_None;
          }
  
          display_str = PyUnicode_FromFormat("%S <- %S -> %S\n",
                                             prevkey, ptr->key, nextkey);
          if (!display_str) {
              return NULL;
          }
          PyObject_Print(display_str, stdout, Py_PRINT_RAW);
          Py_DECREF(display_str);
  
          ptr = ptr->next;
      }
  
      Py_RETURN_NONE;
  }
  
  static PyMethodDef cache_methods[] = {
      {"get", (PyCFunction)pysqlite_cache_get, METH_O,
          PyDoc_STR("Gets an entry from the cache or calls the factory function to produce one.")},
      {"display", (PyCFunction)pysqlite_cache_display, METH_NOARGS,
          PyDoc_STR("For debugging only.")},
      {NULL, NULL}
  };
  
  PyTypeObject pysqlite_NodeType = {
          PyVarObject_HEAD_INIT(NULL, 0)
          MODULE_NAME "Node",                             /* tp_name */
          sizeof(pysqlite_Node),                          /* tp_basicsize */
          0,                                              /* tp_itemsize */
          (destructor)pysqlite_node_dealloc,              /* tp_dealloc */
          0,                                              /* tp_print */
          0,                                              /* tp_getattr */
          0,                                              /* tp_setattr */
          0,                                              /* tp_reserved */
          0,                                              /* tp_repr */
          0,                                              /* tp_as_number */
          0,                                              /* tp_as_sequence */
          0,                                              /* tp_as_mapping */
          0,                                              /* tp_hash */
          0,                                              /* tp_call */
          0,                                              /* tp_str */
          0,                                              /* tp_getattro */
          0,                                              /* tp_setattro */
          0,                                              /* tp_as_buffer */
          Py_TPFLAGS_DEFAULT|Py_TPFLAGS_BASETYPE,         /* tp_flags */
          0,                                              /* tp_doc */
          0,                                              /* tp_traverse */
          0,                                              /* tp_clear */
          0,                                              /* tp_richcompare */
          0,                                              /* tp_weaklistoffset */
          0,                                              /* tp_iter */
          0,                                              /* tp_iternext */
          0,                                              /* tp_methods */
          0,                                              /* tp_members */
          0,                                              /* tp_getset */
          0,                                              /* tp_base */
          0,                                              /* tp_dict */
          0,                                              /* tp_descr_get */
          0,                                              /* tp_descr_set */
          0,                                              /* tp_dictoffset */
          (initproc)0,                                    /* tp_init */
          0,                                              /* tp_alloc */
          0,                                              /* tp_new */
          0                                               /* tp_free */
  };
  
  PyTypeObject pysqlite_CacheType = {
          PyVarObject_HEAD_INIT(NULL, 0)
          MODULE_NAME ".Cache",                           /* tp_name */
          sizeof(pysqlite_Cache),                         /* tp_basicsize */
          0,                                              /* tp_itemsize */
          (destructor)pysqlite_cache_dealloc,             /* tp_dealloc */
          0,                                              /* tp_print */
          0,                                              /* tp_getattr */
          0,                                              /* tp_setattr */
          0,                                              /* tp_reserved */
          0,                                              /* tp_repr */
          0,                                              /* tp_as_number */
          0,                                              /* tp_as_sequence */
          0,                                              /* tp_as_mapping */
          0,                                              /* tp_hash */
          0,                                              /* tp_call */
          0,                                              /* tp_str */
          0,                                              /* tp_getattro */
          0,                                              /* tp_setattro */
          0,                                              /* tp_as_buffer */
          Py_TPFLAGS_DEFAULT|Py_TPFLAGS_BASETYPE,         /* tp_flags */
          0,                                              /* tp_doc */
          0,                                              /* tp_traverse */
          0,                                              /* tp_clear */
          0,                                              /* tp_richcompare */
          0,                                              /* tp_weaklistoffset */
          0,                                              /* tp_iter */
          0,                                              /* tp_iternext */
          cache_methods,                                  /* tp_methods */
          0,                                              /* tp_members */
          0,                                              /* tp_getset */
          0,                                              /* tp_base */
          0,                                              /* tp_dict */
          0,                                              /* tp_descr_get */
          0,                                              /* tp_descr_set */
          0,                                              /* tp_dictoffset */
          (initproc)pysqlite_cache_init,                  /* tp_init */
          0,                                              /* tp_alloc */
          0,                                              /* tp_new */
          0                                               /* tp_free */
  };
  
  extern int pysqlite_cache_setup_types(void)
  {
      int rc;
  
      pysqlite_NodeType.tp_new = PyType_GenericNew;
      pysqlite_CacheType.tp_new = PyType_GenericNew;
  
      rc = PyType_Ready(&pysqlite_NodeType);
      if (rc < 0) {
          return rc;
      }
  
      rc = PyType_Ready(&pysqlite_CacheType);
      return rc;
  }
  