/brz/remove-bazaar

To get this branch, use:
bzr branch http://gegoxaren.bato24.eu/bzr/brz/remove-bazaar

« back to all changes in this revision

Viewing changes to bzrlib/fifo_cache.py

  • Committer: John Arbash Meinel
  • Date: 2008-12-09 21:35:49 UTC
  • mto: This revision was merged to the branch mainline in revision 3888.
  • Revision ID: john@arbash-meinel.com-20081209213549-yc1mqv3l5gun9c63
Start working on a FIFOCache.

This is designed to have less runtime cost than the LRUCache.
Mostly because we don't have to do any recording work on *access*
only on update or delete.
As such, we subclass dict directly, because experiments show that
it performed the best. Unfortunately, even though we don't have
a custom __getitem__ implementation, it is still approx 2x slower
than using a raw dict.

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/fifo_cache.py
 
1
# Copyright (C) 2008 Canonical Ltd
 
2
#
 
3
# This program is free software; you can redistribute it and/or modify
 
4
# it under the terms of the GNU General Public License as published by
 
5
# the Free Software Foundation; either version 2 of the License, or
 
6
# (at your option) any later version.
 
7
#
 
8
# This program is distributed in the hope that it will be useful,
 
9
# but WITHOUT ANY WARRANTY; without even the implied warranty of
 
10
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 
11
# GNU General Public License for more details.
 
12
#
 
13
# You should have received a copy of the GNU General Public License
 
14
# along with this program; if not, write to the Free Software
 
15
# Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 
16
 
 
17
"""A simple first-in-first-out (FIFO) cache."""
 
18
 
 
19
from collections import deque
 
20
 
 
21
 
 
22
class FIFOCache(dict):
 
23
    """A class which manages a cache of entries, removing old ones."""
 
24
 
 
25
    def __init__(self, max_cache=100, after_cleanup_count=None):
 
26
        dict.__init__(self)
 
27
        self._max_cache = max_cache
 
28
        if after_cleanup_count is None:
 
29
            self._after_cleanup_count = self._max_cache * 8 / 10
 
30
        else:
 
31
            self._after_cleanup_count = min(after_cleanup_count,
 
32
                                            self._max_cache)
 
33
        self._cleanup = {} # map to cleanup functions when items are removed
 
34
        self._queue = deque() # Track when things are accessed
 
35
 
 
36
    def __setitem__(self, key, value):
 
37
        """Add a value to the cache, there will be no cleanup function."""
 
38
        self.add(key, value, cleanup=None)
 
39
 
 
40
    def __delitem__(self, key):
 
41
        self._queue.remove(key)
 
42
        self._remove(key)
 
43
 
 
44
    def add(self, key, value, cleanup=None):
 
45
        """Add a new value to the cache.
 
46
 
 
47
        Also, if the entry is ever removed from the queue, call cleanup.
 
48
        Passing it the key and value being removed.
 
49
 
 
50
        :param key: The key to store it under
 
51
        :param value: The object to store
 
52
        :param cleanup: None or a function taking (key, value) to indicate
 
53
                        'value' should be cleaned up
 
54
        """
 
55
        if key in self:
 
56
            # Remove the earlier reference to this key, adding it again bumps
 
57
            # it to the end of the queue
 
58
            del self[key]
 
59
        self._queue.append(key)
 
60
        dict.__setitem__(self, key, value)
 
61
        if len(self) > self._max_cache:
 
62
            self.cleanup()
 
63
        if cleanup is not None:
 
64
            self._cleanup[key] = cleanup
 
65
 
 
66
    def cleanup(self):
 
67
        """Clear the cache until it shrinks to the requested size.
 
68
 
 
69
        This does not completely wipe the cache, just makes sure it is under
 
70
        the after_cleanup_count.
 
71
        """
 
72
        # Make sure the cache is shrunk to the correct size
 
73
        while len(self) > self._after_cleanup_count:
 
74
            self._remove_oldest()
 
75
 
 
76
    def clear(self):
 
77
        """Clear out all of the cache."""
 
78
        # Clean up in FIFO order
 
79
        while self:
 
80
            self._remove_oldest()
 
81
 
 
82
    def _remove(self, key):
 
83
        """Remove an entry, making sure to call any cleanup function."""
 
84
        cleanup = self._cleanup.pop(key, None)
 
85
        # We override self.pop() because it doesn't play well with cleanup
 
86
        # functions.
 
87
        val = dict.pop(self, key)
 
88
        if cleanup is not None:
 
89
            cleanup(key, val)
 
90
        return val
 
91
 
 
92
    def _remove_oldest(self):
 
93
        """Remove the oldest entry."""
 
94
        key = self._queue.popleft()
 
95
        self._remove(key)
 
96
 
 
97
    # raise NotImplementedError on dict functions that would mutate the cache
 
98
    # which have not been properly implemented yet.
 
99
    def copy(self):
 
100
        raise NotImplementedError(self.copy)
 
101
 
 
102
    def pop(self, key, default=None):
 
103
        # If there is a cleanup() function, than it is unclear what pop()
 
104
        # should do. Specifically, we would have to call the cleanup on the
 
105
        # value before we return it, which should cause whatever resources were
 
106
        # allocated to be removed, which makes the return value fairly useless.
 
107
        # So instead, we just don't implement it.
 
108
        raise NotImplementedError(self.pop)
 
109
 
 
110
    def popitem(self):
 
111
        # See pop()
 
112
        raise NotImplementedError(self.popitem)
 
113
 
 
114
    def setdefault(self):
 
115
        raise NotImplementedError(self.setdefault)
 
116
 
 
117
    def update(self, *args, **kwargs):
 
118
        raise NotImplementedError(self.update)