# HG changeset patch
# User cmlenz
# Date 1159716782 0
# Node ID f2b8932a610e1a15030eb2cc80dd921f636fa9b9
# Parent  f17bde33c1a6a305ec7ed72f2eed3d3743e2e5ae
Use an LRU cache for caching parsed templates in the `TemplateLoader`. LRU cache implementation is a simplified version of the `LRUCache` class in [http://www.myghty.org/ Myghty].

diff --git a/genshi/template.py b/genshi/template.py
--- a/genshi/template.py
+++ b/genshi/template.py
@@ -24,12 +24,17 @@
 import os
 import re
 from StringIO import StringIO
+try:
+    import threading
+except ImportError:
+    import dummythreading as threading
 
 from genshi.core import Attrs, Namespace, Stream, StreamEventKind, _ensure
 from genshi.core import START, END, START_NS, END_NS, TEXT, COMMENT
 from genshi.eval import Expression
 from genshi.input import XMLParser
 from genshi.path import Path
+from genshi.util import LRUCache
 
 __all__ = ['BadDirectiveError', 'MarkupTemplate', 'Template', 'TemplateError',
            'TemplateSyntaxError', 'TemplateNotFound', 'TemplateLoader',
@@ -1241,20 +1246,23 @@
     
     >>> os.remove(path)
     """
-    def __init__(self, search_path=None, auto_reload=False):
+    def __init__(self, search_path=None, auto_reload=False, max_cache_size=25):
         """Create the template laoder.
         
         @param search_path: a list of absolute path names that should be
             searched for template files
         @param auto_reload: whether to check the last modification time of
             template files, and reload them if they have changed
+        @param max_cache_size: the maximum number of templates to keep in the
+            cache
         """
         self.search_path = search_path
         if self.search_path is None:
             self.search_path = []
         self.auto_reload = auto_reload
-        self._cache = {}
+        self._cache = LRUCache(max_cache_size)
         self._mtime = {}
+        self._lock = threading.Lock()
 
     def load(self, filename, relative_to=None, cls=MarkupTemplate):
         """Load the template with the given name.
@@ -1286,36 +1294,41 @@
             filename = os.path.join(os.path.dirname(relative_to), filename)
         filename = os.path.normpath(filename)
 
-        # First check the cache to avoid reparsing the same file
+        self._lock.acquire()
         try:
-            tmpl = self._cache[filename]
-            if not self.auto_reload or \
-                    os.path.getmtime(tmpl.filepath) == self._mtime[filename]:
-                return tmpl
-        except KeyError:
-            pass
-
-        # Bypass the search path if the filename is absolute
-        search_path = self.search_path
-        if os.path.isabs(filename):
-            search_path = [os.path.dirname(filename)]
+            # First check the cache to avoid reparsing the same file
+            try:
+                tmpl = self._cache[filename]
+                if not self.auto_reload or \
+                        os.path.getmtime(tmpl.filepath) == self._mtime[filename]:
+                    return tmpl
+            except KeyError:
+                pass
 
-        if not search_path:
-            raise TemplateError('Search path for templates not configured')
+            # Bypass the search path if the filename is absolute
+            search_path = self.search_path
+            if os.path.isabs(filename):
+                search_path = [os.path.dirname(filename)]
 
-        for dirname in search_path:
-            filepath = os.path.join(dirname, filename)
-            try:
-                fileobj = open(filepath, 'U')
+            if not search_path:
+                raise TemplateError('Search path for templates not configured')
+
+            for dirname in search_path:
+                filepath = os.path.join(dirname, filename)
                 try:
-                    tmpl = cls(fileobj, basedir=dirname, filename=filename,
-                               loader=self)
-                finally:
-                    fileobj.close()
-                self._cache[filename] = tmpl
-                self._mtime[filename] = os.path.getmtime(filepath)
-                return tmpl
-            except IOError:
-                continue
+                    fileobj = open(filepath, 'U')
+                    try:
+                        tmpl = cls(fileobj, basedir=dirname, filename=filename,
+                                   loader=self)
+                    finally:
+                        fileobj.close()
+                    self._cache[filename] = tmpl
+                    self._mtime[filename] = os.path.getmtime(filepath)
+                    return tmpl
+                except IOError:
+                    continue
 
-        raise TemplateNotFound(filename, self.search_path)
+            raise TemplateNotFound(filename, self.search_path)
+
+        finally:
+            self._lock.release()
diff --git a/genshi/tests/__init__.py b/genshi/tests/__init__.py
--- a/genshi/tests/__init__.py
+++ b/genshi/tests/__init__.py
@@ -17,7 +17,7 @@
 def suite():
     import genshi
     from genshi.tests import builder, core, eval, filters, input, output, \
-                             path, template
+                             path, template, util
     suite = unittest.TestSuite()
     suite.addTest(doctest.DocTestSuite(genshi))
     suite.addTest(builder.suite())
@@ -28,6 +28,7 @@
     suite.addTest(output.suite())
     suite.addTest(path.suite())
     suite.addTest(template.suite())
+    suite.addTest(util.suite())
     return suite
 
 if __name__ == '__main__':
diff --git a/genshi/tests/util.py b/genshi/tests/util.py
new file mode 100644
--- /dev/null
+++ b/genshi/tests/util.py
@@ -0,0 +1,94 @@
+# -*- coding: utf-8 -*-
+#
+# Copyright (C) 2006 Edgewall Software
+# All rights reserved.
+#
+# This software is licensed as described in the file COPYING, which
+# you should have received as part of this distribution. The terms
+# are also available at http://genshi.edgewall.org/wiki/License.
+#
+# This software consists of voluntary contributions made by many
+# individuals. For the exact contribution history, see the revision
+# history and logs, available at http://genshi.edgewall.org/log/.
+
+import doctest
+import unittest
+
+from genshi import util
+from genshi.util import LRUCache
+
+
+class LRUCacheTestCase(unittest.TestCase):
+
+    def test_setitem(self):
+        cache = LRUCache(2)
+        cache['A'] = 0
+        self.assertEqual(1, len(cache))
+        self.assertEqual('A', cache.head.key)
+        self.assertEqual('A', cache.tail.key)
+        item_a = cache._dict['A']
+        self.assertEqual('A', item_a.key)
+        self.assertEqual(0, item_a.value)
+        self.assertEqual(None, item_a.previous)
+        self.assertEqual(None, item_a.next)
+
+        cache['B'] = 1
+        self.assertEqual(2, len(cache))
+        self.assertEqual('B', cache.head.key)
+        self.assertEqual('A', cache.tail.key)
+        item_a = cache._dict['A']
+        item_b = cache._dict['B']
+        self.assertEqual('A', item_a.key)
+        self.assertEqual(0, item_a.value)
+        self.assertEqual(item_b, item_a.previous)
+        self.assertEqual(None, item_a.next)
+        self.assertEqual('B', item_b.key)
+        self.assertEqual(1, item_b.value)
+        self.assertEqual(None, item_b.previous)
+        self.assertEqual(item_a, item_b.next)
+
+        cache['C'] = 2
+        self.assertEqual(2, len(cache))
+        self.assertEqual('C', cache.head.key)
+        self.assertEqual('B', cache.tail.key)
+        item_b = cache._dict['B']
+        item_c = cache._dict['C']
+        self.assertEqual('B', item_b.key)
+        self.assertEqual(1, item_b.value)
+        self.assertEqual(item_c, item_b.previous)
+        self.assertEqual(None, item_b.next)
+        self.assertEqual('C', item_c.key)
+        self.assertEqual(2, item_c.value)
+        self.assertEqual(None, item_c.previous)
+        self.assertEqual(item_b, item_c.next)
+
+    def test_getitem(self):
+        cache = LRUCache(2)
+        cache['A'] = 0
+        cache['B'] = 1
+
+        cache['A']
+
+        self.assertEqual(2, len(cache))
+        self.assertEqual('A', cache.head.key)
+        self.assertEqual('B', cache.tail.key)
+        item_a = cache._dict['A']
+        item_b = cache._dict['B']
+        self.assertEqual('A', item_a.key)
+        self.assertEqual(0, item_a.value)
+        self.assertEqual(None, item_a.previous)
+        self.assertEqual(item_b, item_a.next)
+        self.assertEqual('B', item_b.key)
+        self.assertEqual(1, item_b.value)
+        self.assertEqual(item_a, item_b.previous)
+        self.assertEqual(None, item_b.next)
+
+
+def suite():
+    suite = unittest.TestSuite()
+    suite.addTest(doctest.DocTestSuite(util))
+    suite.addTest(unittest.makeSuite(LRUCacheTestCase, 'test'))
+    return suite
+
+if __name__ == '__main__':
+    unittest.main(defaultTest='suite')
diff --git a/genshi/util.py b/genshi/util.py
new file mode 100644
--- /dev/null
+++ b/genshi/util.py
@@ -0,0 +1,133 @@
+# -*- coding: utf-8 -*-
+#
+# Copyright (C) 2006 Edgewall Software
+# All rights reserved.
+#
+# This software is licensed as described in the file COPYING, which
+# you should have received as part of this distribution. The terms
+# are also available at http://genshi.edgewall.org/wiki/License.
+#
+# This software consists of voluntary contributions made by many
+# individuals. For the exact contribution history, see the revision
+# history and logs, available at http://genshi.edgewall.org/log/.
+
+"""Various utility classes and functions."""
+
+
+class LRUCache(dict):
+    """A dictionary-like object that stores only a certain number of items, and
+    discards its least recently used item when full.
+    
+    >>> cache = LRUCache(3)
+    >>> cache['A'] = 0
+    >>> cache['B'] = 1
+    >>> cache['C'] = 2
+    >>> len(cache)
+    3
+    
+    >>> cache['A']
+    0
+    
+    Adding new items to the cache does not increase its size. Instead, the least
+    recently used item is dropped:
+    
+    >>> cache['D'] = 3
+    >>> len(cache)
+    3
+    >>> 'B' in cache
+    False
+    
+    Iterating over the cache returns the keys, starting with the most recently
+    used:
+    
+    >>> for key in cache:
+    ...     print key
+    D
+    A
+    C
+
+    This code is based on the LRUCache class from ``myghtyutils.util``, written
+    by Mike Bayer and released under the MIT license. See:
+
+      http://svn.myghty.org/myghtyutils/trunk/lib/myghtyutils/util.py
+    """
+
+    class _Item(object):
+        def __init__(self, key, value):
+            self.previous = self.next = None
+            self.key = key
+            self.value = value
+        def __repr__(self):
+            return repr(self.value)
+
+    def __init__(self, capacity):
+        self._dict = dict()
+        self.capacity = capacity
+        self.head = None
+        self.tail = None
+
+    def __contains__(self, key):
+        return key in self._dict
+
+    def __iter__(self):
+        cur = self.head
+        while cur:
+            yield cur.key
+            cur = cur.next
+
+    def __len__(self):
+        return len(self._dict)
+
+    def __getitem__(self, key):
+        item = self._dict[key]
+        self._update_item(item)
+        return item.value
+
+    def __setitem__(self, key, value):
+        item = self._dict.get(key)
+        if item is None:
+            item = self._Item(key, value)
+            self._dict[key] = item
+            self._insert_item(item)
+        else:
+            item.value = value
+            self._update_item(item)
+            self._manage_size()
+
+    def __repr__(self):
+        return repr(self._dict)
+
+    def _insert_item(self, item):
+        item.previous = None
+        item.next = self.head
+        if self.head is not None:
+            self.head.previous = item
+        else:
+            self.tail = item
+        self.head = item
+        self._manage_size()
+
+    def _manage_size(self):
+        while len(self._dict) > self.capacity:
+            olditem = self._dict[self.tail.key]
+            del self._dict[self.tail.key]
+            if self.tail != self.head:
+                self.tail = self.tail.previous
+                self.tail.next = None
+            else:
+                self.head = self.tail = None
+
+    def _update_item(self, item):
+        if self.head == item:
+            return
+
+        previous = item.previous
+        previous.next = item.next
+        if item.next is not None:
+            item.next.previous = previous
+        else:
+            self.tail = previous
+
+        item.previous = None
+        item.next = self.head
+        self.head.previous = self.head = item