incubator-bloodhound-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From j...@apache.org
Subject svn commit: r1453952 - in /incubator/bloodhound/branches/bep_0003_multiproduct: ./ bloodhound_multiproduct/multiproduct/
Date Thu, 07 Mar 2013 16:41:04 GMT
Author: jure
Date: Thu Mar  7 16:41:03 2013
New Revision: 1453952

URL: http://svn.apache.org/r1453952
Log:
LRU & LFU cache implementations added, appropriate files (license, notice,...) updated
appropriately


Added:
    incubator/bloodhound/branches/bep_0003_multiproduct/bloodhound_multiproduct/multiproduct/cache.py
Modified:
    incubator/bloodhound/branches/bep_0003_multiproduct/.rat-ignore
    incubator/bloodhound/branches/bep_0003_multiproduct/LICENSE
    incubator/bloodhound/branches/bep_0003_multiproduct/NOTICE
    incubator/bloodhound/branches/bep_0003_multiproduct/bloodhound_multiproduct/multiproduct/dbcursor.py
    incubator/bloodhound/branches/bep_0003_multiproduct/bloodhound_multiproduct/multiproduct/env.py
    incubator/bloodhound/branches/bep_0003_multiproduct/bloodhound_multiproduct/multiproduct/util.py

Modified: incubator/bloodhound/branches/bep_0003_multiproduct/.rat-ignore
URL: http://svn.apache.org/viewvc/incubator/bloodhound/branches/bep_0003_multiproduct/.rat-ignore?rev=1453952&r1=1453951&r2=1453952&view=diff
==============================================================================
--- incubator/bloodhound/branches/bep_0003_multiproduct/.rat-ignore (original)
+++ incubator/bloodhound/branches/bep_0003_multiproduct/.rat-ignore Thu Mar  7 16:41:03 2013
@@ -5,6 +5,7 @@
 **/TODO
 bloodhound_dashboard/bhdashboard/default-pages/
 bloodhound_search/bhsearch/default-pages/
+bloodhound_multiproduct/multiproduct/cache.py
 doc/html-templates/js/jquery-1.8.2.js
 doc/wireframes/src/
 installer/README.rst

Modified: incubator/bloodhound/branches/bep_0003_multiproduct/LICENSE
URL: http://svn.apache.org/viewvc/incubator/bloodhound/branches/bep_0003_multiproduct/LICENSE?rev=1453952&r1=1453951&r2=1453952&view=diff
==============================================================================
--- incubator/bloodhound/branches/bep_0003_multiproduct/LICENSE (original)
+++ incubator/bloodhound/branches/bep_0003_multiproduct/LICENSE Thu Mar  7 16:41:03 2013
@@ -284,3 +284,55 @@ bloodhound_theme/bhtheme/htdocs/js/jquer
     OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
     WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
 
+
+For LRU and LFU cache decorators, developed by Raymond Hettinger, in the file
+bloodhound_multiproduct/multiproduct/cache.py:
+
+    PSF LICENSE AGREEMENT
+
+    This LICENSE AGREEMENT is between the Python Software Foundation
+    (“PSF”), and the Individual or Organization (“Licensee”) accessing
+    and otherwise using Python 2.7.3 software in source or binary form
+    and its associated documentation.
+
+    Subject to the terms and conditions of this License Agreement, PSF
+    hereby grants Licensee a nonexclusive, royalty-free, world-wide
+    license to reproduce, analyze, test, perform and/or display
+    publicly, prepare derivative works, distribute, and otherwise use
+    Python 2.7.3 alone or in any derivative version, provided,
+    however, that PSF’s License Agreement and PSF’s notice of
+    copyright, i.e., “Copyright © 2001-2013 Python Software
+    Foundation; All Rights Reserved” are retained in Python 2.7.3
+    alone or in any derivative version prepared by Licensee.
+
+    In the event Licensee prepares a derivative work that is based on
+    or incorporates Python 2.7.3 or any part thereof, and wants to
+    make the derivative work available to others as provided herein,
+    then Licensee hereby agrees to include in any such work a brief
+    summary of the changes made to Python 2.7.3.
+
+    PSF is making Python 2.7.3 available to Licensee on an “AS IS”
+    basis. PSF MAKES NO REPRESENTATIONS OR WARRANTIES, EXPRESS OR
+    IMPLIED. BY WAY OF EXAMPLE, BUT NOT LIMITATION, PSF MAKES NO AND
+    DISCLAIMS ANY REPRESENTATION OR WARRANTY OF MERCHANTABILITY OR
+    FITNESS FOR ANY PARTICULAR PURPOSE OR THAT THE USE OF PYTHON 2.7.3
+    WILL NOT INFRINGE ANY THIRD PARTY RIGHTS.
+
+    PSF SHALL NOT BE LIABLE TO LICENSEE OR ANY OTHER USERS OF PYTHON
+    2.7.3 FOR ANY INCIDENTAL, SPECIAL, OR CONSEQUENTIAL DAMAGES OR
+    LOSS AS A RESULT OF MODIFYING, DISTRIBUTING, OR OTHERWISE USING
+    PYTHON 2.7.3, OR ANY DERIVATIVE THEREOF, EVEN IF ADVISED OF THE
+    POSSIBILITY THEREOF.
+
+    This License Agreement will automatically terminate upon a
+    material breach of its terms and conditions.
+
+    Nothing in this License Agreement shall be deemed to create any
+    relationship of agency, partnership, or joint venture between PSF
+    and Licensee. This License Agreement does not grant permission to
+    use PSF trademarks or trade name in a trademark sense to endorse
+    or promote products or services of Licensee, or any third party.
+
+    By copying, installing or otherwise using Python 2.7.3, Licensee
+    agrees to be bound by the terms and conditions of this License
+    Agreement.

Modified: incubator/bloodhound/branches/bep_0003_multiproduct/NOTICE
URL: http://svn.apache.org/viewvc/incubator/bloodhound/branches/bep_0003_multiproduct/NOTICE?rev=1453952&r1=1453951&r2=1453952&view=diff
==============================================================================
--- incubator/bloodhound/branches/bep_0003_multiproduct/NOTICE (original)
+++ incubator/bloodhound/branches/bep_0003_multiproduct/NOTICE Thu Mar  7 16:41:03 2013
@@ -16,3 +16,7 @@ jQuery - licensed under the MIT License
 This product includes software (jQuery) developed by
 jQuery (http://jquery.org/)
 
+LRU and LFU cache decorators - licensed under the PSF License
+This product includes code (LRU and LFU cache decorators) developed by
+Raymond Hettinger (http://code.activestate.com/recipes/498245-lru-and-lfu-cache-decorators/)
+

Added: incubator/bloodhound/branches/bep_0003_multiproduct/bloodhound_multiproduct/multiproduct/cache.py
URL: http://svn.apache.org/viewvc/incubator/bloodhound/branches/bep_0003_multiproduct/bloodhound_multiproduct/multiproduct/cache.py?rev=1453952&view=auto
==============================================================================
--- incubator/bloodhound/branches/bep_0003_multiproduct/bloodhound_multiproduct/multiproduct/cache.py
(added)
+++ incubator/bloodhound/branches/bep_0003_multiproduct/bloodhound_multiproduct/multiproduct/cache.py
Thu Mar  7 16:41:03 2013
@@ -0,0 +1,142 @@
+#
+# LRU and LFU cache decorators - licensed under the PSF License
+# Developed by Raymond Hettinger
+# (http://code.activestate.com/recipes/498245-lru-and-lfu-cache-decorators/)
+#
+
+import collections
+import functools
+from itertools import ifilterfalse
+from heapq import nsmallest
+from operator import itemgetter
+
+class Counter(dict):
+    'Mapping where default values are zero'
+    def __missing__(self, key):
+        return 0
+
+def lru_cache(maxsize=100):
+    '''Least-recently-used cache decorator.
+
+    Arguments to the cached function must be hashable.
+    Cache performance statistics stored in f.hits and f.misses.
+    Clear the cache with f.clear().
+    http://en.wikipedia.org/wiki/Cache_algorithms#Least_Recently_Used
+
+    '''
+    maxqueue = maxsize * 10
+    def decorating_function(user_function,
+                            len=len, iter=iter, tuple=tuple, sorted=sorted, KeyError=KeyError):
+        cache = {}                  # mapping of args to results
+        queue = collections.deque() # order that keys have been used
+        refcount = Counter()        # times each key is in the queue
+        sentinel = object()         # marker for looping around the queue
+        kwd_mark = object()         # separate positional and keyword args
+
+        # lookup optimizations (ugly but fast)
+        queue_append, queue_popleft = queue.append, queue.popleft
+        queue_appendleft, queue_pop = queue.appendleft, queue.pop
+
+        @functools.wraps(user_function)
+        def wrapper(*args, **kwds):
+            # cache key records both positional and keyword args
+            key = args
+            if kwds:
+                key += (kwd_mark,) + tuple(sorted(kwds.items()))
+
+            # record recent use of this key
+            queue_append(key)
+            refcount[key] += 1
+
+            # get cache entry or compute if not found
+            try:
+                result = cache[key]
+                wrapper.hits += 1
+            except KeyError:
+                result = user_function(*args, **kwds)
+                cache[key] = result
+                wrapper.misses += 1
+
+                # purge least recently used cache entry
+                if len(cache) > maxsize:
+                    key = queue_popleft()
+                    refcount[key] -= 1
+                    while refcount[key]:
+                        key = queue_popleft()
+                        refcount[key] -= 1
+                    del cache[key], refcount[key]
+
+            # periodically compact the queue by eliminating duplicate keys
+            # while preserving order of most recent access
+            if len(queue) > maxqueue:
+                refcount.clear()
+                queue_appendleft(sentinel)
+                for key in ifilterfalse(refcount.__contains__,
+                    iter(queue_pop, sentinel)):
+                    queue_appendleft(key)
+                    refcount[key] = 1
+
+
+            return result
+
+        def clear():
+            cache.clear()
+            queue.clear()
+            refcount.clear()
+            wrapper.hits = wrapper.misses = 0
+
+        wrapper.hits = wrapper.misses = 0
+        wrapper.clear = clear
+        return wrapper
+    return decorating_function
+
+
+def lfu_cache(maxsize=100):
+    '''Least-frequenty-used cache decorator.
+
+    Arguments to the cached function must be hashable.
+    Cache performance statistics stored in f.hits and f.misses.
+    Clear the cache with f.clear().
+    http://en.wikipedia.org/wiki/Least_Frequently_Used
+
+    '''
+    def decorating_function(user_function):
+        cache = {}                      # mapping of args to results
+        use_count = Counter()           # times each key has been accessed
+        kwd_mark = object()             # separate positional and keyword args
+
+        @functools.wraps(user_function)
+        def wrapper(*args, **kwds):
+            key = args
+            if kwds:
+                key += (kwd_mark,) + tuple(sorted(kwds.items()))
+            use_count[key] += 1
+
+            # get cache entry or compute if not found
+            try:
+                result = cache[key]
+                wrapper.hits += 1
+            except KeyError:
+                result = user_function(*args, **kwds)
+                cache[key] = result
+                wrapper.misses += 1
+
+                # purge least frequently used cache entry
+                if len(cache) > maxsize:
+                    for key, _ in nsmallest(maxsize // 10,
+                        use_count.iteritems(),
+                        key=itemgetter(1)):
+                        del cache[key], use_count[key]
+
+            return result
+
+        def clear():
+            cache.clear()
+            use_count.clear()
+            wrapper.hits = wrapper.misses = 0
+
+        wrapper.hits = wrapper.misses = 0
+        wrapper.clear = clear
+        return wrapper
+    return decorating_function
+

Modified: incubator/bloodhound/branches/bep_0003_multiproduct/bloodhound_multiproduct/multiproduct/dbcursor.py
URL: http://svn.apache.org/viewvc/incubator/bloodhound/branches/bep_0003_multiproduct/bloodhound_multiproduct/multiproduct/dbcursor.py?rev=1453952&r1=1453951&r2=1453952&view=diff
==============================================================================
--- incubator/bloodhound/branches/bep_0003_multiproduct/bloodhound_multiproduct/multiproduct/dbcursor.py
(original)
+++ incubator/bloodhound/branches/bep_0003_multiproduct/bloodhound_multiproduct/multiproduct/dbcursor.py
Thu Mar  7 16:41:03 2013
@@ -23,7 +23,7 @@ import sqlparse
 import sqlparse.tokens as Tokens
 import sqlparse.sql as Types
 
-from multiproduct.util import lru_cache
+from multiproduct.cache import lru_cache
 
 __all__ = ['BloodhoundIterableCursor', 'BloodhoundConnectionWrapper', 'ProductEnvContextManager']
 

Modified: incubator/bloodhound/branches/bep_0003_multiproduct/bloodhound_multiproduct/multiproduct/env.py
URL: http://svn.apache.org/viewvc/incubator/bloodhound/branches/bep_0003_multiproduct/bloodhound_multiproduct/multiproduct/env.py?rev=1453952&r1=1453951&r2=1453952&view=diff
==============================================================================
--- incubator/bloodhound/branches/bep_0003_multiproduct/bloodhound_multiproduct/multiproduct/env.py
(original)
+++ incubator/bloodhound/branches/bep_0003_multiproduct/bloodhound_multiproduct/multiproduct/env.py
Thu Mar  7 16:41:03 2013
@@ -804,7 +804,7 @@ class ProductEnvironment(Component, Comp
                 self._abs_href = Href(self.base_url)
         return self._abs_href
 
-from multiproduct.util import lru_cache
+from multiproduct.cache import lru_cache
 
 @lru_cache(maxsize=100)
 def ProductEnvironmentFactory(global_env, product):

Modified: incubator/bloodhound/branches/bep_0003_multiproduct/bloodhound_multiproduct/multiproduct/util.py
URL: http://svn.apache.org/viewvc/incubator/bloodhound/branches/bep_0003_multiproduct/bloodhound_multiproduct/multiproduct/util.py?rev=1453952&r1=1453951&r2=1453952&view=diff
==============================================================================
--- incubator/bloodhound/branches/bep_0003_multiproduct/bloodhound_multiproduct/multiproduct/util.py
(original)
+++ incubator/bloodhound/branches/bep_0003_multiproduct/bloodhound_multiproduct/multiproduct/util.py
Thu Mar  7 16:41:03 2013
@@ -21,9 +21,6 @@
 from trac import db_default
 from multiproduct.api import MultiProductSystem
 
-import collections
-import functools
-
 class ProductDelegate(object):
     @staticmethod
     def add_product(env, product, keys, field_data):
@@ -54,25 +51,3 @@ class ProductDelegate(object):
             cols = ('username', 'action', 'product')
             db.executemany("INSERT INTO permission (%s) VALUES (%s)" %
                 (','.join(cols), ','.join(['%s' for c in cols])), rows)
-
-def lru_cache(maxsize=100):
-    """Simple LRU cache decorator, using `collections.OrderedDict` for
-    item store
-    """
-    def wrap(f):
-        cache = collections.OrderedDict()
-        @functools.wraps(f)
-        def wrapped_func(*args, **kwargs):
-            key = args
-            if kwargs:
-                key += tuple(sorted(kwargs.items()))
-            try:
-                item = cache.pop(key)
-            except KeyError:
-                item = f(*args, **kwargs)
-                if len(cache) >= maxsize:
-                    cache.popitem(last=False)
-            cache[key] = item
-            return item
-        return wrapped_func
-    return wrap



Mime
View raw message