[PATCH 1 of 5 V2] util: add an LRU cache dict

Siddharth Agarwal sid0 at fb.com
Fri Feb 8 16:18:04 CST 2013


# HG changeset patch
# User Siddharth Agarwal <sid0 at fb.com>
# Date 1360360128 0
# Node ID c55453aed518c09e71f3e7941e7fb46f947b19c1
# Parent  08e00496e7b3bda8db3fbe7084a013d77e4932d2
util: add an LRU cache dict

This is the bare minimum dictionary implementation needed for an upcoming
patch.

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 get or sets to this dictionary'''
+    def __init__(self, size):
+        self._cache = {}
+        self._size = size
+        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._size:
+                del self._cache[self._order.popleft()]
+            self._cache[key] = value
+        else:
+            self._order.remove(key)
+        self._order.append(key)
+
+    def __contains__(self, key):
+        return key in self._cache
+
 def lrucachefunc(func):
     '''cache most recent results of function calls'''
     cache = {}


More information about the Mercurial-devel mailing list