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 +++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 94 insertions(+)
 create mode 100644 repoze/bfg/lru.py

(limited to 'repoze/bfg/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
+    
+    
+    
+    
-- 
cgit v1.2.3