#
#
# add_file "tracmtn/lru_cache.py"
#  content [28ec5fd2ba80b1cb0c4127a6d755b5a56d163548]
#
============================================================
--- tracmtn/lru_cache.py	28ec5fd2ba80b1cb0c4127a6d755b5a56d163548
+++ tracmtn/lru_cache.py	28ec5fd2ba80b1cb0c4127a6d755b5a56d163548
@@ -0,0 +1,134 @@
+# -*- coding: utf-8 -*-
+"""
+Trac Plugin for Monotone
+
+Copyright 2008 Thomas Moschny (address@hidden)
+
+{{{
+This program is free software; you can redistribute it and/or modify
+it under the terms of the GNU General Public License as published by
+the Free Software Foundation; either version 2 of the License, or (at
+your option) any later version.
+
+This program is distributed in the hope that it will be useful, but
+WITHOUT ANY WARRANTY; without even the implied warranty of
+MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+General Public License for more details.
+
+You should have received a copy of the GNU General Public License
+along with this program; if not, write to the Free Software
+Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307
+USA
+}}}
+
+"""
+
+from UserDict import DictMixin
+from collections import deque
+
+try:
+    from threading import Lock
+except ImportError:
+    from dummy_threading import Lock #IGNORE:E0611
+
+
+class LRUCache(DictMixin):
+
+    class ListItem(object):
+
+        def __init__(self, key=None, val=None):
+            self.next = self.prev = self
+            self.key = key
+            self.val = val
+
+        def link_to(self, other):
+            # detach
+            self.next.prev = self.prev
+            self.prev.next = self.next
+
+            # attach
+            self.prev = other
+            self.next = other.next
+            self.prev.next = self
+            self.next.prev = self
+
+
+    def __init__(self, maxsize):
+        assert maxsize > 0
+        self.maxsize = maxsize
+        self._data = {}
+        self._list_head = self.ListItem()
+        self.lock = Lock()
+
+    def __getitem__(self, key):
+        self.lock.acquire()
+        try:
+            l = self._data[key]
+            l.link_to(self._list_head)
+            return l.val
+        finally:
+            self.lock.release()
+
+    def _shrink(self):
+        while len(self._data) > self.maxsize:
+            key = self._list_head.prev.key
+            # delete key
+            l = self._data.pop(key)
+            l.link_to(l) # detach
+
+    def __setitem__(self, key, val):
+        self.lock.acquire()
+        try:
+            try:
+                l = self._data[key]
+                l.val = val
+            except KeyError:
+                l = self._data[key] = self.ListItem(key, val)
+            l.link_to(self._list_head)
+            self._shrink()
+        finally:
+            self.lock.release()
+
+
+    def __delitem__(self, key):
+        self.lock.acquire()
+        try:
+            l = self._data.pop(key)
+            l.link_to(l) # detach
+        finally:
+            self.lock.release()
+
+    def keys(self):
+        return self._data.keys()
+
+    def __repr__(self):
+        self.lock.acquire()
+        try:
+            res = '{'
+            cur = self._list_head.next
+            while cur is not self._list_head:
+                res += "%s: %s, " % (cur.key, cur.val)
+                assert cur is not cur.next
+                cur = cur.next
+            res += '}'
+            return res
+        finally:
+            self.lock.release()
+
+# ----------------------------------------------------------------------
+
+if __name__ == "__main__":
+    c = LRUCache(3)
+
+    print c
+    c['f'] = 'x'
+    del c['f']
+    print c
+    c['1'] = 11
+    c['2'] = 12
+    c['4'] = 14
+    c['1'] = 45
+    c['4'] = 32
+    c['5'] = 64
+    print c
+