From 1216ad50c697235be1cbe9547b91140b6867c5c1 Mon Sep 17 00:00:00 2001 From: Chris McDonough Date: Mon, 15 Jun 2009 00:10:59 +0000 Subject: - Move LRU cache implementation into a separate package (``repoze.lru``). --- CHANGES.txt | 3 ++ repoze/bfg/lru.py | 91 -------------------------------------------- repoze/bfg/tests/test_lru.py | 83 ---------------------------------------- repoze/bfg/traversal.py | 4 +- setup.py | 1 + 5 files changed, 6 insertions(+), 176 deletions(-) delete mode 100644 repoze/bfg/lru.py delete mode 100644 repoze/bfg/tests/test_lru.py diff --git a/CHANGES.txt b/CHANGES.txt index f64f1442a..c9f3313c2 100644 --- a/CHANGES.txt +++ b/CHANGES.txt @@ -4,6 +4,9 @@ Next release Features -------- +- Move LRU cache implementation into a separate package + (``repoze.lru``). + - The concepts of traversal and URL dispatch have been unified. It is now possible to use the same sort of factory as both a traversal "root factory" and what used to be referred to as a urldispatch diff --git a/repoze/bfg/lru.py b/repoze/bfg/lru.py deleted file mode 100644 index 947f8193f..000000000 --- a/repoze/bfg/lru.py +++ /dev/null @@ -1,91 +0,0 @@ -""" LRU caching class and decorator """ - -import threading - -try: - from functools import wraps -except ImportError: # < 2.5 #pragma NO COVERAGE - from repoze.bfg.functional import wraps #pragma NO COVERAGE - -_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(key): - val = cache.get(key, marker) - if val is marker: - val = f(key) - cache.put(key, val) - return val - return wraps(f)(lru_cached) diff --git a/repoze/bfg/tests/test_lru.py b/repoze/bfg/tests/test_lru.py deleted file mode 100644 index c5224420b..000000000 --- a/repoze/bfg/tests/test_lru.py +++ /dev/null @@ -1,83 +0,0 @@ -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_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.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) - diff --git a/repoze/bfg/traversal.py b/repoze/bfg/traversal.py index 223de4309..40f65901f 100644 --- a/repoze/bfg/traversal.py +++ b/repoze/bfg/traversal.py @@ -6,9 +6,9 @@ from zope.component import getMultiAdapter from zope.interface import classProvides from zope.interface import implements -from repoze.bfg.location import lineage +from repoze.lru import lru_cache -from repoze.bfg.lru import lru_cache +from repoze.bfg.location import lineage from repoze.bfg.interfaces import IContextURL from repoze.bfg.interfaces import ITraverser diff --git a/setup.py b/setup.py index f6f1e1c72..aee13805c 100644 --- a/setup.py +++ b/setup.py @@ -39,6 +39,7 @@ install_requires=[ 'zope.component >= 3.6.0', # independent of zope.hookable 'zope.deprecation', 'repoze.zcml', + 'repoze.lru', 'martian', ] -- cgit v1.2.3