From 72c5baff65bc82e010a6f0701324e5e09c05969c Mon Sep 17 00:00:00 2001
From: Chris McDonough <chrism@agendaless.com>
Date: Thu, 22 Jan 2009 08:30:29 +0000
Subject: - ``repoze.bfg.lru`` implements an LRU cache class and a decorator
 for   internal use.

---
 repoze/bfg/lru.py            | 94 ++++++++++++++++++++++++++++++++++++++++++++
 repoze/bfg/tests/test_lru.py | 75 +++++++++++++++++++++++++++++++++++
 2 files changed, 169 insertions(+)
 create mode 100644 repoze/bfg/lru.py
 create mode 100644 repoze/bfg/tests/test_lru.py

diff --git a/repoze/bfg/lru.py b/repoze/bfg/lru.py
new file mode 100644
index 000000000..059750d15
--- /dev/null
+++ b/repoze/bfg/lru.py
@@ -0,0 +1,94 @@
+""" LRU caching class and decorator """
+
+import threading
+
+_marker = object()
+
+class Node(object):
+    def __init__(self, key):
+        self.key = key
+        self.ref = False
+
+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, _marker=_marker):
+        datum = self.data.get(key, _marker)
+        if datum is _marker:
+            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 is not _marker:
+                        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(key):
+            val = cache.get(key, marker)
+            if val is marker:
+                val = f(key)
+                cache.put(key, val)
+            return val
+        return lru_cached
+    
+    
+    
+    
diff --git a/repoze/bfg/tests/test_lru.py b/repoze/bfg/tests/test_lru.py
new file mode 100644
index 000000000..02bee3052
--- /dev/null
+++ b/repoze/bfg/tests/test_lru.py
@@ -0,0 +1,75 @@
+import unittest
+
+class LRUCacheTests(unittest.TestCase):
+    def _getTargetClass(self):
+        from repoze.bfg.lru import LRUCache
+        return LRUCache
+
+    def _makeOne(self, size):
+        return self._getTargetClass()(size)
+
+    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)
+        
+class DecoratorTests(unittest.TestCase):
+    def _getTargetClass(self):
+        from repoze.bfg.lru import lru_cache
+        return lru_cache
+
+    def _makeOne(self, cache):
+        return self._getTargetClass()(0, cache)
+
+    def test_it(self):
+        cache = DummyLRUCache()
+        decorator = self._makeOne(cache)
+        def wrapped(k):
+            return k
+        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)
+   
+class DummyLRUCache(dict):
+    def put(self, k, v):
+        return self.__setitem__(k, v)
+    
-- 
cgit v1.2.3