[PATCH 1 of 4 V3] util: add an LRU cache dict
Siddharth Agarwal
sid0 at fb.com
Sat Feb 9 15:48:53 UTC 2013
# HG changeset patch
# User Siddharth Agarwal <sid0 at fb.com>
# Date 1360424506 0
# Node ID c5e8d2d68a8e1a7bada44d98cbe528f8b25dae15
# Parent 08e00496e7b3bda8db3fbe7084a013d77e4932d2
util: add an LRU cache dict
In certain cases we would like to have a cache of the last N results of a
given computation, where N is small. This will be used in an upcoming patch to
increase the size of the manifest cache from 1 to 3.
diff --git a/mercurial/util.py b/mercurial/util.py
--- a/mercurial/util.py
+++ b/mercurial/util.py
@@ -211,6 +211,31 @@ except AttributeError:
del self[i]
break
+class lrucachedict(object):
+ '''cache most recent gets from or sets to this dictionary'''
+ def __init__(self, maxsize):
+ self._cache = {}
+ self._maxsize = maxsize
+ self._order = deque()
+
+ def __getitem__(self, key):
+ value = self._cache[key]
+ self._order.remove(key)
+ self._order.append(key)
+ return value
+
+ def __setitem__(self, key, value):
+ if key not in self._cache:
+ if len(self._cache) >= self._maxsize:
+ del self._cache[self._order.popleft()]
+ else:
+ self._order.remove(key)
+ self._cache[key] = value
+ self._order.append(key)
+
+ def __contains__(self, key):
+ return key in self._cache
+
def lrucachefunc(func):
'''cache most recent results of function calls'''
cache = {}
diff --git a/tests/test-lrucachedict.py b/tests/test-lrucachedict.py
new file mode 100644
--- /dev/null
+++ b/tests/test-lrucachedict.py
@@ -0,0 +1,35 @@
+from mercurial import util
+
+def printifpresent(d, xs):
+ for x in xs:
+ present = x in d
+ print "'%s' in d: %s" % (x, present)
+ if present:
+ print "d['%s']: %s" % (x, d[x])
+
+def test_lrucachedict():
+ d = util.lrucachedict(4)
+ d['a'] = 'va'
+ d['b'] = 'vb'
+ d['c'] = 'vc'
+ d['d'] = 'vd'
+
+ # all of these should be present
+ printifpresent(d, ['a', 'b', 'c', 'd'])
+
+ # 'a' should be dropped because it was least recently used
+ d['e'] = 've'
+ printifpresent(d, ['a', 'b', 'c', 'd', 'e'])
+
+ # touch entries in some order (get or set).
+ d['e']
+ d['c'] = 'vc2'
+ d['d']
+ d['b'] = 'vb2'
+
+ # 'e' should be dropped now
+ d['f'] = 'vf'
+ printifpresent(d, ['b', 'c', 'd', 'e', 'f'])
+
+if __name__ == '__main__':
+ test_lrucachedict()
diff --git a/tests/test-lrucachedict.py.out b/tests/test-lrucachedict.py.out
new file mode 100644
--- /dev/null
+++ b/tests/test-lrucachedict.py.out
@@ -0,0 +1,26 @@
+'a' in d: True
+d['a']: va
+'b' in d: True
+d['b']: vb
+'c' in d: True
+d['c']: vc
+'d' in d: True
+d['d']: vd
+'a' in d: False
+'b' in d: True
+d['b']: vb
+'c' in d: True
+d['c']: vc
+'d' in d: True
+d['d']: vd
+'e' in d: True
+d['e']: ve
+'b' in d: True
+d['b']: vb2
+'c' in d: True
+d['c']: vc2
+'d' in d: True
+d['d']: vd
+'e' in d: False
+'f' in d: True
+d['f']: vf
More information about the Mercurial-devel
mailing list