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
