1# Copyright 2007 Matt Chaput. All rights reserved.
2#
3# Redistribution and use in source and binary forms, with or without
4# modification, are permitted provided that the following conditions are met:
5#
6#    1. Redistributions of source code must retain the above copyright notice,
7#       this list of conditions and the following disclaimer.
8#
9#    2. Redistributions in binary form must reproduce the above copyright
10#       notice, this list of conditions and the following disclaimer in the
11#       documentation and/or other materials provided with the distribution.
12#
13# THIS SOFTWARE IS PROVIDED BY MATT CHAPUT ``AS IS'' AND ANY EXPRESS OR
14# IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
15# MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO
16# EVENT SHALL MATT CHAPUT OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
17# INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
18# LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA,
19# OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
20# LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
21# NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE,
22# EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
23#
24# The views and conclusions contained in the software and documentation are
25# those of the authors and should not be interpreted as representing official
26# policies, either expressed or implied, of Matt Chaput.
27
28from __future__ import with_statement
29import functools, random
30from array import array
31from heapq import nsmallest
32from operator import itemgetter
33from threading import Lock
34from time import time
35
36from whoosh.compat import iteritems, xrange
37
38
39try:
40    from collections import Counter
41except ImportError:
42    class Counter(dict):
43        def __missing__(self, key):
44            return 0
45
46
47def unbound_cache(func):
48    """Caching decorator with an unbounded cache size.
49    """
50
51    cache = {}
52
53    @functools.wraps(func)
54    def caching_wrapper(*args):
55        try:
56            return cache[args]
57        except KeyError:
58            result = func(*args)
59            cache[args] = result
60            return result
61
62    return caching_wrapper
63
64
65def lru_cache(maxsize=100):
66    """A simple cache that, when the cache is full, deletes the least recently
67    used 10% of the cached values.
68
69    This function duplicates (more-or-less) the protocol of the
70    ``functools.lru_cache`` decorator in the Python 3.2 standard library.
71
72    Arguments to the cached function must be hashable.
73
74    View the cache statistics tuple ``(hits, misses, maxsize, currsize)``
75    with f.cache_info().  Clear the cache and statistics with f.cache_clear().
76    Access the underlying function with f.__wrapped__.
77    """
78
79    def decorating_function(user_function):
80        stats = [0, 0]  # Hits, misses
81        data = {}
82        lastused = {}
83
84        @functools.wraps(user_function)
85        def wrapper(*args):
86            try:
87                result = data[args]
88                stats[0] += 1  # Hit
89            except KeyError:
90                stats[1] += 1  # Miss
91                if len(data) == maxsize:
92                    for k, _ in nsmallest(maxsize // 10 or 1,
93                                          iteritems(lastused),
94                                          key=itemgetter(1)):
95                        del data[k]
96                        del lastused[k]
97                data[args] = user_function(*args)
98                result = data[args]
99            finally:
100                lastused[args] = time()
101            return result
102
103        def cache_info():
104            return stats[0], stats[1], maxsize, len(data)
105
106        def cache_clear():
107            data.clear()
108            lastused.clear()
109            stats[0] = stats[1] = 0
110
111        wrapper.cache_info = cache_info
112        wrapper.cache_clear = cache_clear
113        return wrapper
114    return decorating_function
115
116
117def lfu_cache(maxsize=100):
118    """A simple cache that, when the cache is full, deletes the least frequently
119    used 10% of the cached values.
120
121    This function duplicates (more-or-less) the protocol of the
122    ``functools.lru_cache`` decorator in the Python 3.2 standard library.
123
124    Arguments to the cached function must be hashable.
125
126    View the cache statistics tuple ``(hits, misses, maxsize, currsize)``
127    with f.cache_info().  Clear the cache and statistics with f.cache_clear().
128    Access the underlying function with f.__wrapped__.
129    """
130
131    def decorating_function(user_function):
132        stats = [0, 0]  # Hits, misses
133        data = {}
134        usecount = Counter()
135
136        @functools.wraps(user_function)
137        def wrapper(*args):
138            try:
139                result = data[args]
140                stats[0] += 1  # Hit
141            except KeyError:
142                stats[1] += 1  # Miss
143                if len(data) == maxsize:
144                    for k, _ in nsmallest(maxsize // 10 or 1,
145                                          iteritems(usecount),
146                                          key=itemgetter(1)):
147                        del data[k]
148                        del usecount[k]
149                data[args] = user_function(*args)
150                result = data[args]
151            finally:
152                usecount[args] += 1
153            return result
154
155        def cache_info():
156            return stats[0], stats[1], maxsize, len(data)
157
158        def cache_clear():
159            data.clear()
160            usecount.clear()
161
162        wrapper.cache_info = cache_info
163        wrapper.cache_clear = cache_clear
164        return wrapper
165    return decorating_function
166
167
168def random_cache(maxsize=100):
169    """A very simple cache that, when the cache is filled, deletes 10% of the
170    cached values AT RANDOM.
171
172    This function duplicates (more-or-less) the protocol of the
173    ``functools.lru_cache`` decorator in the Python 3.2 standard library.
174
175    Arguments to the cached function must be hashable.
176
177    View the cache statistics tuple ``(hits, misses, maxsize, currsize)``
178    with f.cache_info().  Clear the cache and statistics with f.cache_clear().
179    Access the underlying function with f.__wrapped__.
180    """
181
182    def decorating_function(user_function):
183        stats = [0, 0]  # hits, misses
184        data = {}
185
186        @functools.wraps(user_function)
187        def wrapper(*args):
188            try:
189                result = data[args]
190                stats[0] += 1  # Hit
191            except KeyError:
192                stats[1] += 1  # Miss
193                if len(data) == maxsize:
194                    keys = data.keys()
195                    for i in xrange(maxsize // 10 or 1):
196                        n = random.randint(0, len(keys) - 1)
197                        k = keys.pop(n)
198                        del data[k]
199                data[args] = user_function(*args)
200                result = data[args]
201            return result
202
203        def cache_info():
204            return stats[0], stats[1], maxsize, len(data)
205
206        def cache_clear():
207            data.clear()
208
209        wrapper.cache_info = cache_info
210        wrapper.cache_clear = cache_clear
211        return wrapper
212    return decorating_function
213
214
215def db_lru_cache(maxsize=100):
216    """Double-barrel least-recently-used cache decorator. This is a simple
217    LRU algorithm that keeps a primary and secondary dict. Keys are checked
218    in the primary dict, and then the secondary. Once the primary dict fills
219    up, the secondary dict is cleared and the two dicts are swapped.
220
221    This function duplicates (more-or-less) the protocol of the
222    ``functools.lru_cache`` decorator in the Python 3.2 standard library.
223
224    Arguments to the cached function must be hashable.
225
226    View the cache statistics tuple ``(hits, misses, maxsize, currsize)``
227    with f.cache_info().  Clear the cache and statistics with f.cache_clear().
228    Access the underlying function with f.__wrapped__.
229    """
230
231    def decorating_function(user_function):
232        # Cache1, Cache2, Pointer, Hits, Misses
233        stats = [{}, {}, 0, 0, 0]
234
235        @functools.wraps(user_function)
236        def wrapper(*args):
237            ptr = stats[2]
238            a = stats[ptr]
239            b = stats[not ptr]
240            key = args
241
242            if key in a:
243                stats[3] += 1  # Hit
244                return a[key]
245            elif key in b:
246                stats[3] += 1  # Hit
247                return b[key]
248            else:
249                stats[4] += 1  # Miss
250                result = user_function(*args)
251                a[key] = result
252                if len(a) >= maxsize:
253                    stats[2] = not ptr
254                    b.clear()
255                return result
256
257        def cache_info():
258            return stats[3], stats[4], maxsize, len(stats[0]) + len(stats[1])
259
260        def cache_clear():
261            """Clear the cache and cache statistics"""
262            stats[0].clear()
263            stats[1].clear()
264            stats[3] = stats[4] = 0
265
266        wrapper.cache_info = cache_info
267        wrapper.cache_clear = cache_clear
268
269        return wrapper
270    return decorating_function
271
272
273def clockface_lru_cache(maxsize=100):
274    """Least-recently-used cache decorator.
275
276    This function duplicates (more-or-less) the protocol of the
277    ``functools.lru_cache`` decorator in the Python 3.2 standard library, but
278    uses the clock face LRU algorithm instead of an ordered dictionary.
279
280    If *maxsize* is set to None, the LRU features are disabled and the cache
281    can grow without bound.
282
283    Arguments to the cached function must be hashable.
284
285    View the cache statistics named tuple (hits, misses, maxsize, currsize)
286    with f.cache_info().  Clear the cache and statistics with f.cache_clear().
287    Access the underlying function with f.__wrapped__.
288    """
289
290    def decorating_function(user_function):
291        stats = [0, 0, 0]  # hits, misses, hand
292        data = {}
293
294        if maxsize:
295            # The keys at each point on the clock face
296            clock_keys = [None] * maxsize
297            # The "referenced" bits at each point on the clock face
298            clock_refs = array("B", (0 for _ in xrange(maxsize)))
299            lock = Lock()
300
301            @functools.wraps(user_function)
302            def wrapper(*args):
303                key = args
304                try:
305                    with lock:
306                        pos, result = data[key]
307                        # The key is in the cache. Set the key's reference bit
308                        clock_refs[pos] = 1
309                        # Record a cache hit
310                        stats[0] += 1
311                except KeyError:
312                    # Compute the value
313                    result = user_function(*args)
314                    with lock:
315                        # Current position of the clock hand
316                        hand = stats[2]
317                        # Remember to stop here after a full revolution
318                        end = hand
319                        # Sweep around the clock looking for a position with
320                        # the reference bit off
321                        while True:
322                            hand = (hand + 1) % maxsize
323                            current_ref = clock_refs[hand]
324                            if current_ref:
325                                # This position's "referenced" bit is set. Turn
326                                # the bit off and move on.
327                                clock_refs[hand] = 0
328                            elif not current_ref or hand == end:
329                                # We've either found a position with the
330                                # "reference" bit off or reached the end of the
331                                # circular cache. So we'll replace this
332                                # position with the new key
333                                current_key = clock_keys[hand]
334                                if current_key in data:
335                                    del data[current_key]
336                                clock_keys[hand] = key
337                                clock_refs[hand] = 1
338                                break
339                        # Put the key and result in the cache
340                        data[key] = (hand, result)
341                        # Save the new hand position
342                        stats[2] = hand
343                        # Record a cache miss
344                        stats[1] += 1
345                return result
346
347        else:
348            @functools.wraps(user_function)
349            def wrapper(*args):
350                key = args
351                try:
352                    result = data[key]
353                    stats[0] += 1
354                except KeyError:
355                    result = user_function(*args)
356                    data[key] = result
357                    stats[1] += 1
358                return result
359
360        def cache_info():
361            return stats[0], stats[1], maxsize, len(data)
362
363        def cache_clear():
364            """Clear the cache and cache statistics"""
365            data.clear()
366            stats[0] = stats[1] = stats[2] = 0
367            for i in xrange(maxsize):
368                clock_keys[i] = None
369                clock_refs[i] = 0
370
371        wrapper.cache_info = cache_info
372        wrapper.cache_clear = cache_clear
373        return wrapper
374    return decorating_function
375
376