Break out the BFG lru cache implementation into a shareable package.

10 files changed, 623 insertions, 0 deletions

diff --git a/CHANGES.txt b/CHANGES.txt
new file mode 100644
index 0000000..64c4d06
--- /dev/null
+++ b/CHANGES.txt
@@ -0,0 +1,7 @@
+repoze.lru
+==========
+
+0.1 (unreleaesd)
+----------------
+
+- Initial release.
diff --git a/COPYRIGHT.txt b/COPYRIGHT.txt
new file mode 100644
index 0000000..3d9afa7
--- /dev/null
+++ b/COPYRIGHT.txt
@@ -0,0 +1,3 @@
+Copyright (c) 2009 Agendaless Consulting and Contributors.
+(http://www.agendaless.com), All Rights Reserved
+
diff --git a/LICENSE.txt b/LICENSE.txt
new file mode 100644
index 0000000..5ced96e
--- /dev/null
+++ b/LICENSE.txt
@@ -0,0 +1,41 @@
+License
+
+  A copyright notice accompanies this license document that identifies
+  the copyright holders.
+
+  Redistribution and use in source and binary forms, with or without
+  modification, are permitted provided that the following conditions are
+  met:
+
+  1.  Redistributions in source code must retain the accompanying
+      copyright notice, this list of conditions, and the following
+      disclaimer.
+
+  2.  Redistributions in binary form must reproduce the accompanying
+      copyright notice, this list of conditions, and the following
+      disclaimer in the documentation and/or other materials provided
+      with the distribution.
+
+  3.  Names of the copyright holders must not be used to endorse or
+      promote products derived from this software without prior
+      written permission from the copyright holders.
+
+  4.  If any files are modified, you must cause the modified files to
+      carry prominent notices stating that you changed the files and
+      the date of any change.
+
+  Disclaimer
+
+    THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS ``AS IS'' AND
+    ANY EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
+    TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
+    PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
+    HOLDERS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+    EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED
+    TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+    DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON
+    ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR
+    TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF
+    THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+    SUCH DAMAGE.
+
diff --git a/README.txt b/README.txt
new file mode 100644
index 0000000..c3057d7
--- /dev/null
+++ b/README.txt
@@ -0,0 +1,50 @@
+repoze.lru
+==========
+
+``repoze.lru`` is a LRU (least recently used) cache implementation.
+Keys and values that are not used frequently will be evicted from the
+cache faster than keys and values that are used frequently.
+
+API
+---
+
+Creating an LRUCache object:
+
+.. code-block:: python
+
+  from repoze.lru import LRUCache
+  cache = LRUCache(100) # 100 max length
+
+Retrieving from an LRUCache object:
+
+.. code-block:: python
+
+  cache.get('nonexisting', 'foo') # will return 'foo'
+  cache.get('nonexisting') # will return None
+  cache.get('existing') # will return the value for existing
+
+Adding to an LRUCache object:
+
+.. code-block:: python
+
+  cache.put('key', 'value') # will add the key 'key' with the value 'value'
+
+
+Decorator
+---------
+
+A ``lru_cached`` decorator exists.  All values passed to the decorated
+function must be hashable.  It does not support keyword arguments.
+
+.. code-block:: python
+
+   from repoze.lru import lru_cache
+
+   @lru_cache(500)
+   def expensive_function(*arg):
+       pass
+
+Each function decorated with the lru_cache decorator uses its own
+cache related to that function.
+
+
diff --git a/ez_setup.py b/ez_setup.py
new file mode 100644
index 0000000..d24e845
--- /dev/null
+++ b/ez_setup.py
@@ -0,0 +1,276 @@
+#!python
+"""Bootstrap setuptools installation
+
+If you want to use setuptools in your package's setup.py, just include this
+file in the same directory with it, and add this to the top of your setup.py::
+
+    from ez_setup import use_setuptools
+    use_setuptools()
+
+If you want to require a specific version of setuptools, set a download
+mirror, or use an alternate download directory, you can do so by supplying
+the appropriate options to ``use_setuptools()``.
+
+This file can also be run as a script to install or upgrade setuptools.
+"""
+import sys
+DEFAULT_VERSION = "0.6c9"
+DEFAULT_URL     = "http://pypi.python.org/packages/%s/s/setuptools/" % sys.version[:3]
+
+md5_data = {
+    'setuptools-0.6b1-py2.3.egg': '8822caf901250d848b996b7f25c6e6ca',
+    'setuptools-0.6b1-py2.4.egg': 'b79a8a403e4502fbb85ee3f1941735cb',
+    'setuptools-0.6b2-py2.3.egg': '5657759d8a6d8fc44070a9d07272d99b',
+    'setuptools-0.6b2-py2.4.egg': '4996a8d169d2be661fa32a6e52e4f82a',
+    'setuptools-0.6b3-py2.3.egg': 'bb31c0fc7399a63579975cad9f5a0618',
+    'setuptools-0.6b3-py2.4.egg': '38a8c6b3d6ecd22247f179f7da669fac',
+    'setuptools-0.6b4-py2.3.egg': '62045a24ed4e1ebc77fe039aa4e6f7e5',
+    'setuptools-0.6b4-py2.4.egg': '4cb2a185d228dacffb2d17f103b3b1c4',
+    'setuptools-0.6c1-py2.3.egg': 'b3f2b5539d65cb7f74ad79127f1a908c',
+    'setuptools-0.6c1-py2.4.egg': 'b45adeda0667d2d2ffe14009364f2a4b',
+    'setuptools-0.6c2-py2.3.egg': 'f0064bf6aa2b7d0f3ba0b43f20817c27',
+    'setuptools-0.6c2-py2.4.egg': '616192eec35f47e8ea16cd6a122b7277',
+    'setuptools-0.6c3-py2.3.egg': 'f181fa125dfe85a259c9cd6f1d7b78fa',
+    'setuptools-0.6c3-py2.4.egg': 'e0ed74682c998bfb73bf803a50e7b71e',
+    'setuptools-0.6c3-py2.5.egg': 'abef16fdd61955514841c7c6bd98965e',
+    'setuptools-0.6c4-py2.3.egg': 'b0b9131acab32022bfac7f44c5d7971f',
+    'setuptools-0.6c4-py2.4.egg': '2a1f9656d4fbf3c97bf946c0a124e6e2',
+    'setuptools-0.6c4-py2.5.egg': '8f5a052e32cdb9c72bcf4b5526f28afc',
+    'setuptools-0.6c5-py2.3.egg': 'ee9fd80965da04f2f3e6b3576e9d8167',
+    'setuptools-0.6c5-py2.4.egg': 'afe2adf1c01701ee841761f5bcd8aa64',
+    'setuptools-0.6c5-py2.5.egg': 'a8d3f61494ccaa8714dfed37bccd3d5d',
+    'setuptools-0.6c6-py2.3.egg': '35686b78116a668847237b69d549ec20',
+    'setuptools-0.6c6-py2.4.egg': '3c56af57be3225019260a644430065ab',
+    'setuptools-0.6c6-py2.5.egg': 'b2f8a7520709a5b34f80946de5f02f53',
+    'setuptools-0.6c7-py2.3.egg': '209fdf9adc3a615e5115b725658e13e2',
+    'setuptools-0.6c7-py2.4.egg': '5a8f954807d46a0fb67cf1f26c55a82e',
+    'setuptools-0.6c7-py2.5.egg': '45d2ad28f9750e7434111fde831e8372',
+    'setuptools-0.6c8-py2.3.egg': '50759d29b349db8cfd807ba8303f1902',
+    'setuptools-0.6c8-py2.4.egg': 'cba38d74f7d483c06e9daa6070cce6de',
+    'setuptools-0.6c8-py2.5.egg': '1721747ee329dc150590a58b3e1ac95b',
+    'setuptools-0.6c9-py2.3.egg': 'a83c4020414807b496e4cfbe08507c03',
+    'setuptools-0.6c9-py2.4.egg': '260a2be2e5388d66bdaee06abec6342a',
+    'setuptools-0.6c9-py2.5.egg': 'fe67c3e5a17b12c0e7c541b7ea43a8e6',
+    'setuptools-0.6c9-py2.6.egg': 'ca37b1ff16fa2ede6e19383e7b59245a',
+}
+
+import sys, os
+try: from hashlib import md5
+except ImportError: from md5 import md5
+
+def _validate_md5(egg_name, data):
+    if egg_name in md5_data:
+        digest = md5(data).hexdigest()
+        if digest != md5_data[egg_name]:
+            print >>sys.stderr, (
+                "md5 validation of %s failed!  (Possible download problem?)"
+                % egg_name
+            )
+            sys.exit(2)
+    return data
+
+def use_setuptools(
+    version=DEFAULT_VERSION, download_base=DEFAULT_URL, to_dir=os.curdir,
+    download_delay=15
+):
+    """Automatically find/download setuptools and make it available on sys.path
+
+    `version` should be a valid setuptools version number that is available
+    as an egg for download under the `download_base` URL (which should end with
+    a '/').  `to_dir` is the directory where setuptools will be downloaded, if
+    it is not already available.  If `download_delay` is specified, it should
+    be the number of seconds that will be paused before initiating a download,
+    should one be required.  If an older version of setuptools is installed,
+    this routine will print a message to ``sys.stderr`` and raise SystemExit in
+    an attempt to abort the calling script.
+    """
+    was_imported = 'pkg_resources' in sys.modules or 'setuptools' in sys.modules
+    def do_download():
+        egg = download_setuptools(version, download_base, to_dir, download_delay)
+        sys.path.insert(0, egg)
+        import setuptools; setuptools.bootstrap_install_from = egg
+    try:
+        import pkg_resources
+    except ImportError:
+        return do_download()       
+    try:
+        pkg_resources.require("setuptools>="+version); return
+    except pkg_resources.VersionConflict, e:
+        if was_imported:
+            print >>sys.stderr, (
+            "The required version of setuptools (>=%s) is not available, and\n"
+            "can't be installed while this script is running. Please install\n"
+            " a more recent version first, using 'easy_install -U setuptools'."
+            "\n\n(Currently using %r)"
+            ) % (version, e.args[0])
+            sys.exit(2)
+        else:
+            del pkg_resources, sys.modules['pkg_resources']    # reload ok
+            return do_download()
+    except pkg_resources.DistributionNotFound:
+        return do_download()
+
+def download_setuptools(
+    version=DEFAULT_VERSION, download_base=DEFAULT_URL, to_dir=os.curdir,
+    delay = 15
+):
+    """Download setuptools from a specified location and return its filename
+
+    `version` should be a valid setuptools version number that is available
+    as an egg for download under the `download_base` URL (which should end
+    with a '/'). `to_dir` is the directory where the egg will be downloaded.
+    `delay` is the number of seconds to pause before an actual download attempt.
+    """
+    import urllib2, shutil
+    egg_name = "setuptools-%s-py%s.egg" % (version,sys.version[:3])
+    url = download_base + egg_name
+    saveto = os.path.join(to_dir, egg_name)
+    src = dst = None
+    if not os.path.exists(saveto):  # Avoid repeated downloads
+        try:
+            from distutils import log
+            if delay:
+                log.warn("""
+---------------------------------------------------------------------------
+This script requires setuptools version %s to run (even to display
+help).  I will attempt to download it for you (from
+%s), but
+you may need to enable firewall access for this script first.
+I will start the download in %d seconds.
+
+(Note: if this machine does not have network access, please obtain the file
+
+   %s
+
+and place it in this directory before rerunning this script.)
+---------------------------------------------------------------------------""",
+                    version, download_base, delay, url
+                ); from time import sleep; sleep(delay)
+            log.warn("Downloading %s", url)
+            src = urllib2.urlopen(url)
+            # Read/write all in one block, so we don't create a corrupt file
+            # if the download is interrupted.
+            data = _validate_md5(egg_name, src.read())
+            dst = open(saveto,"wb"); dst.write(data)
+        finally:
+            if src: src.close()
+            if dst: dst.close()
+    return os.path.realpath(saveto)
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+def main(argv, version=DEFAULT_VERSION):
+    """Install or upgrade setuptools and EasyInstall"""
+    try:
+        import setuptools
+    except ImportError:
+        egg = None
+        try:
+            egg = download_setuptools(version, delay=0)
+            sys.path.insert(0,egg)
+            from setuptools.command.easy_install import main
+            return main(list(argv)+[egg])   # we're done here
+        finally:
+            if egg and os.path.exists(egg):
+                os.unlink(egg)
+    else:
+        if setuptools.__version__ == '0.0.1':
+            print >>sys.stderr, (
+            "You have an obsolete version of setuptools installed.  Please\n"
+            "remove it from your system entirely before rerunning this script."
+            )
+            sys.exit(2)
+
+    req = "setuptools>="+version
+    import pkg_resources
+    try:
+        pkg_resources.require(req)
+    except pkg_resources.VersionConflict:
+        try:
+            from setuptools.command.easy_install import main
+        except ImportError:
+            from easy_install import main
+        main(list(argv)+[download_setuptools(delay=0)])
+        sys.exit(0) # try to force an exit
+    else:
+        if argv:
+            from setuptools.command.easy_install import main
+            main(argv)
+        else:
+            print "Setuptools version",version,"or greater has been installed."
+            print '(Run "ez_setup.py -U setuptools" to reinstall or upgrade.)'
+
+def update_md5(filenames):
+    """Update our built-in md5 registry"""
+
+    import re
+
+    for name in filenames:
+        base = os.path.basename(name)
+        f = open(name,'rb')
+        md5_data[base] = md5(f.read()).hexdigest()
+        f.close()
+
+    data = ["    %r: %r,\n" % it for it in md5_data.items()]
+    data.sort()
+    repl = "".join(data)
+
+    import inspect
+    srcfile = inspect.getsourcefile(sys.modules[__name__])
+    f = open(srcfile, 'rb'); src = f.read(); f.close()
+
+    match = re.search("\nmd5_data = {\n([^}]+)}", src)
+    if not match:
+        print >>sys.stderr, "Internal error!"
+        sys.exit(2)
+
+    src = src[:match.start(1)] + repl + src[match.end(1):]
+    f = open(srcfile,'w')
+    f.write(src)
+    f.close()
+
+
+if __name__=='__main__':
+    if len(sys.argv)>2 and sys.argv[1]=='--md5update':
+        update_md5(sys.argv[2:])
+    else:
+        main(sys.argv[1:])
+
+
+
+
+
+
diff --git a/repoze/__init__.py b/repoze/__init__.py
new file mode 100644
index 0000000..de40ea7
--- /dev/null
+++ b/repoze/__init__.py
@@ -0,0 +1 @@
+__import__('pkg_resources').declare_namespace(__name__)
diff --git a/repoze/lru/__init__.py b/repoze/lru/__init__.py
new file mode 100644
index 0000000..b5e5203
--- /dev/null
+++ b/repoze/lru/__init__.py
@@ -0,0 +1,89 @@
+""" LRU caching class and decorator """
+
+import threading
+
+_marker = object()
+
+class LRUCache(object):
+    def __init__(self, size):
+        """ Implements a psueudo-LRU algorithm (CLOCK) """
+        if size < 1:
+            raise ValueError('size must be >1')
+        self.clock = []
+        for i in xrange(0, size):
+            self.clock.append({'key':_marker, 'ref':False})
+        self.size = size
+        self.maxpos = size - 1
+        self.hand = 0
+        self.data = {}
+        self.lock = threading.Lock()
+
+    def get(self, key, default=None):
+        try:
+            datum = self.data[key]
+        except KeyError:
+            return default
+        pos, val = datum
+        self.clock[pos]['ref'] = True
+        hand = pos + 1
+        if hand > self.maxpos:
+            hand = 0
+        self.hand = hand
+        return val
+
+    def put(self, key, val, _marker=_marker):
+        hand = self.hand
+        maxpos = self.maxpos
+        clock = self.clock
+        data = self.data
+        lock = self.lock
+
+        end = hand - 1
+        if end < 0:
+            end = maxpos
+
+        while 1:
+            current = clock[hand]
+            ref = current['ref']
+            if ref is True:
+                current['ref'] = False
+                hand = hand + 1
+                if hand > maxpos:
+                    hand = 0
+            elif ref is False or hand == end:
+                lock.acquire()
+                try:
+                    oldkey = current['key']
+                    if oldkey in data:
+                        del data[oldkey]
+                    current['key'] = key
+                    current['ref'] = True
+                    data[key] = (hand, val)
+                    hand += 1
+                    if hand > maxpos:
+                        hand = 0
+                    self.hand = hand
+                finally:
+                    lock.release()
+                break
+
+class lru_cache(object):
+    """ Decorator for LRU-cached function """
+    def __init__(self, maxsize, cache=None): # cache is an arg to serve tests
+        if cache is None:
+            cache = LRUCache(maxsize)
+        self.cache = cache
+
+    def __call__(self, f):
+        cache = self.cache
+        marker = _marker
+        def lru_cached(*arg):
+            val = cache.get(arg, marker)
+            if val is marker:
+                val = f(*arg)
+                cache.put(arg, val)
+            return val
+        lru_cached.__module__ = f.__module__
+        lru_cached.__name__ = f.__name__
+        lru_cached.__doc__ = f.__doc__
+        return lru_cached
diff --git a/repoze/lru/tests.py b/repoze/lru/tests.py
new file mode 100644
index 0000000..41a509a
--- /dev/null
+++ b/repoze/lru/tests.py
@@ -0,0 +1,99 @@
+import unittest
+
+class LRUCacheTests(unittest.TestCase):
+    def _getTargetClass(self):
+        from repoze.lru import LRUCache
+        return LRUCache
+
+    def _makeOne(self, size):
+        return self._getTargetClass()(size)
+
+    def test_size_lessthan_1(self):
+        self.assertRaises(ValueError, self._makeOne, 0)
+
+    def test_it(self):
+        cache = self._makeOne(3)
+        self.assertEqual(cache.get('a'), None)
+        cache.put('a', '1')
+        pos, value = cache.data.get('a')
+        self.assertEqual(cache.clock[pos]['ref'], True)
+        self.assertEqual(cache.clock[pos]['key'], 'a')
+        self.assertEqual(value, '1')
+        self.assertEqual(cache.get('a'), '1')
+        self.assertEqual(cache.hand, pos+1)
+        pos, value = cache.data.get('a')
+        self.assertEqual(cache.clock[pos]['ref'], True)
+        self.assertEqual(cache.hand, pos+1)
+        self.assertEqual(len(cache.data), 1)
+        cache.put('b', '2')
+        pos, value = cache.data.get('b')
+        self.assertEqual(cache.clock[pos]['ref'], True)
+        self.assertEqual(cache.clock[pos]['key'], 'b')
+        self.assertEqual(len(cache.data), 2)
+        cache.put('c', '3')
+        pos, value = cache.data.get('c')
+        self.assertEqual(cache.clock[pos]['ref'], True)
+        self.assertEqual(cache.clock[pos]['key'], 'c')
+        self.assertEqual(len(cache.data), 3)
+        pos, value = cache.data.get('a')
+        self.assertEqual(cache.clock[pos]['ref'], True)
+        cache.get('a')
+        cache.put('d', '4')
+        self.assertEqual(len(cache.data), 3)
+        self.assertEqual(cache.data.get('b'), None)
+        cache.put('e', '5')
+        self.assertEqual(len(cache.data), 3)
+        self.assertEqual(cache.data.get('c'), None)
+        self.assertEqual(cache.get('d'), '4')
+        self.assertEqual(cache.get('e'), '5')
+        self.assertEqual(cache.get('a'), '1')
+        self.assertEqual(cache.get('b'), None)
+        self.assertEqual(cache.get('c'), None)
+                         
+class DecoratorTests(unittest.TestCase):
+    def _getTargetClass(self):
+        from repoze.lru import lru_cache
+        return lru_cache
+
+    def _makeOne(self, maxsize, cache):
+        return self._getTargetClass()(maxsize, cache)
+
+    def test_ctor_nocache(self):
+        decorator = self._makeOne(10, None)
+        self.assertEqual(decorator.cache.size, 10)
+
+    def test_singlearg(self):
+        cache = DummyLRUCache()
+        decorator = self._makeOne(0, cache)
+        def wrapped(key):
+            return key
+        decorated = decorator(wrapped)
+        result = decorated(1)
+        self.assertEqual(cache[(1,)], 1)
+        self.assertEqual(result, 1)
+        self.assertEqual(len(cache), 1)
+        result = decorated(2)
+        self.assertEqual(cache[(2,)], 2) 
+        self.assertEqual(result, 2)
+        self.assertEqual(len(cache), 2)
+        result = decorated(2)
+        self.assertEqual(cache[(2,)], 2) 
+        self.assertEqual(result, 2)
+        self.assertEqual(len(cache), 2)
+
+    def test_multiargs(self):
+        cache = DummyLRUCache()
+        decorator = self._makeOne(0, cache)
+        def moreargs(*args):
+            return args
+        decorated = decorator(moreargs)
+        result = decorated(3, 4, 5)
+        self.assertEqual(cache[(3,4,5)], (3,4,5)) 
+        self.assertEqual(result, (3,4,5))
+        self.assertEqual(len(cache), 1)
+            
+   
+class DummyLRUCache(dict):
+    def put(self, k, v):
+        return self.__setitem__(k, v)
+    
diff --git a/setup.cfg b/setup.cfg
new file mode 100644
index 0000000..8128fe6
--- /dev/null
+++ b/setup.cfg
@@ -0,0 +1,6 @@
+[nosetests]
+nocapture=1
+cover-package=repoze.lru
+with-coverage=1
+cover-erase=1
+
diff --git a/setup.py b/setup.py
new file mode 100644
index 0000000..ebdcfe7
--- /dev/null
+++ b/setup.py
@@ -0,0 +1,51 @@
+##############################################################################
+#
+# Copyright (c) 2009 Agendaless Consulting and Contributors.
+# All Rights Reserved.
+#
+# This software is subject to the provisions of the BSD-like license at
+# http://www.repoze.org/LICENSE.txt.  A copy of the license should accompany
+# this distribution.  THIS SOFTWARE IS PROVIDED "AS IS" AND ANY AND ALL
+# EXPRESS OR IMPLIED WARRANTIES ARE DISCLAIMED, INCLUDING, BUT NOT LIMITED TO,
+# THE IMPLIED WARRANTIES OF TITLE, MERCHANTABILITY, AGAINST INFRINGEMENT, AND
+# FITNESS FOR A PARTICULAR PURPOSE
+#
+##############################################################################
+
+__version__ = '0.1'
+
+import os
+
+from ez_setup import use_setuptools
+use_setuptools()
+
+from setuptools import setup, find_packages
+
+here = os.path.abspath(os.path.dirname(__file__))
+README = open(os.path.join(here, 'README.txt')).read()
+CHANGES = open(os.path.join(here, 'CHANGES.txt')).read()
+
+setup(name='repoze.lru',
+      version=__version__,
+      description='A tiny LRU cache implementation and decorator',
+      long_description=README + '\n\n' +  CHANGES,
+      classifiers=[
+        "Intended Audience :: Developers",
+        "Programming Language :: Python",
+        ],
+      keywords='repoze lru cache',
+      author="Agendaless Consulting",
+      author_email="repoze-dev@lists.repoze.org",
+      url="http://www.repoze.org",
+      license="BSD-derived (http://www.repoze.org/LICENSE.txt)",
+      packages=find_packages(),
+      include_package_data=True,
+      namespace_packages=['repoze'],
+      zip_safe=False,
+      tests_require = [],
+      install_requires = [],
+      test_suite="repoze.lru",
+      entry_points = """\
+      """
+      )
+