← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/tests/test_fifo_cache.py

  • Committer: John Arbash Meinel
  • Date: 2009-03-27 04:23:35 UTC
  • mto: This revision was merged to the branch mainline in revision 4209.
  • Revision ID: john@arbash-meinel.com-20090327042335-5a8ii0h5sa4ktx04
Switch to using a FIFOCache.

That gives us the lookup performance of a dict, while still being capped
at max size.

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/tests/test_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., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
 
16
 
 
17
"""Tests for the fifo_cache module."""
 
18
 
 
19
from bzrlib import (
 
20
    fifo_cache,
 
21
    tests,
 
22
    )
 
23
 
 
24
 
 
25
class TestFIFOCache(tests.TestCase):
 
26
    """Test that FIFO cache properly keeps track of entries."""
 
27
 
 
28
    def test_add_is_present(self):
 
29
        c = fifo_cache.FIFOCache()
 
30
        c[1] = 2
 
31
        self.assertTrue(1 in c)
 
32
        self.assertEqual(1, len(c))
 
33
        self.assertEqual(2, c[1])
 
34
        self.assertEqual(2, c.get(1))
 
35
        self.assertEqual(2, c.get(1, None))
 
36
        self.assertEqual([1], c.keys())
 
37
        self.assertEqual([1], list(c.iterkeys()))
 
38
        self.assertEqual([(1, 2)], c.items())
 
39
        self.assertEqual([(1, 2)], list(c.iteritems()))
 
40
        self.assertEqual([2], c.values())
 
41
        self.assertEqual([2], list(c.itervalues()))
 
42
        self.assertEqual({1: 2}, c)
 
43
 
 
44
    def test_cache_size(self):
 
45
        c = fifo_cache.FIFOCache()
 
46
        self.assertEqual(100, c.cache_size())
 
47
        c.resize(20, 5)
 
48
        self.assertEqual(20, c.cache_size())
 
49
 
 
50
    def test_missing(self):
 
51
        c = fifo_cache.FIFOCache()
 
52
        self.assertRaises(KeyError, c.__getitem__, 1)
 
53
        self.assertFalse(1 in c)
 
54
        self.assertEqual(0, len(c))
 
55
        self.assertEqual(None, c.get(1))
 
56
        self.assertEqual(None, c.get(1, None))
 
57
        self.assertEqual([], c.keys())
 
58
        self.assertEqual([], list(c.iterkeys()))
 
59
        self.assertEqual([], c.items())
 
60
        self.assertEqual([], list(c.iteritems()))
 
61
        self.assertEqual([], c.values())
 
62
        self.assertEqual([], list(c.itervalues()))
 
63
        self.assertEqual({}, c)
 
64
 
 
65
    def test_add_maintains_fifo(self):
 
66
        c = fifo_cache.FIFOCache(4, 4)
 
67
        c[1] = 2
 
68
        c[2] = 3
 
69
        c[3] = 4
 
70
        c[4] = 5
 
71
        self.assertEqual([1, 2, 3, 4], sorted(c.keys()))
 
72
        c[5] = 6
 
73
        # This should pop out the oldest entry
 
74
        self.assertEqual([2, 3, 4, 5], sorted(c.keys()))
 
75
        # Replacing an item doesn't change the stored keys
 
76
        c[2] = 7
 
77
        self.assertEqual([2, 3, 4, 5], sorted(c.keys()))
 
78
        # But it does change the position in the FIFO
 
79
        c[6] = 7
 
80
        self.assertEqual([2, 4, 5, 6], sorted(c.keys()))
 
81
        self.assertEqual([4, 5, 2, 6], list(c._queue))
 
82
 
 
83
    def test_default_after_cleanup_count(self):
 
84
        c = fifo_cache.FIFOCache(5)
 
85
        self.assertEqual(4, c._after_cleanup_count)
 
86
        c[1] = 2
 
87
        c[2] = 3
 
88
        c[3] = 4
 
89
        c[4] = 5
 
90
        c[5] = 6
 
91
        # So far, everything fits
 
92
        self.assertEqual([1, 2, 3, 4, 5], sorted(c.keys()))
 
93
        c[6] = 7
 
94
        # But adding one more should shrink down to after_cleanup_count
 
95
        self.assertEqual([3, 4, 5, 6], sorted(c.keys()))
 
96
 
 
97
    def test_clear(self):
 
98
        c = fifo_cache.FIFOCache(5)
 
99
        c[1] = 2
 
100
        c[2] = 3
 
101
        c[3] = 4
 
102
        c[4] = 5
 
103
        c[5] = 6
 
104
        c.cleanup()
 
105
        self.assertEqual([2, 3, 4, 5], sorted(c.keys()))
 
106
        c.clear()
 
107
        self.assertEqual([], c.keys())
 
108
        self.assertEqual([], list(c._queue))
 
109
        self.assertEqual({}, c)
 
110
 
 
111
    def test_copy_not_implemented(self):
 
112
        c = fifo_cache.FIFOCache()
 
113
        self.assertRaises(NotImplementedError, c.copy)
 
114
 
 
115
    def test_pop_not_implemeted(self):
 
116
        c = fifo_cache.FIFOCache()
 
117
        self.assertRaises(NotImplementedError, c.pop, 'key')
 
118
 
 
119
    def test_popitem_not_implemeted(self):
 
120
        c = fifo_cache.FIFOCache()
 
121
        self.assertRaises(NotImplementedError, c.popitem)
 
122
 
 
123
    def test_resize_smaller(self):
 
124
        c = fifo_cache.FIFOCache()
 
125
        c[1] = 2
 
126
        c[2] = 3
 
127
        c[3] = 4
 
128
        c[4] = 5
 
129
        c[5] = 6
 
130
        # No cleanup, because it is the exact size
 
131
        c.resize(5)
 
132
        self.assertEqual({1: 2, 2: 3, 3: 4, 4: 5, 5: 6}, c)
 
133
        self.assertEqual(5, c.cache_size())
 
134
        # Adding one more will trigger a cleanup, though
 
135
        c[6] = 7
 
136
        self.assertEqual({3: 4, 4: 5, 5: 6, 6: 7}, c)
 
137
        c.resize(3, 2)
 
138
        self.assertEqual({5: 6, 6: 7}, c)
 
139
 
 
140
    def test_resize_larger(self):
 
141
        c = fifo_cache.FIFOCache(5, 4)
 
142
        c[1] = 2
 
143
        c[2] = 3
 
144
        c[3] = 4
 
145
        c[4] = 5
 
146
        c[5] = 6
 
147
        # No cleanup, because it is the exact size
 
148
        c.resize(10)
 
149
        self.assertEqual({1: 2, 2: 3, 3: 4, 4: 5, 5: 6}, c)
 
150
        self.assertEqual(10, c.cache_size())
 
151
        c[6] = 7
 
152
        c[7] = 8
 
153
        c[8] = 9
 
154
        c[9] = 10
 
155
        c[10] = 11
 
156
        self.assertEqual({1: 2, 2: 3, 3: 4, 4: 5, 5: 6, 6: 7, 7: 8, 8: 9,
 
157
                          9: 10, 10: 11}, c)
 
158
        c[11] = 12
 
159
        self.assertEqual({4: 5, 5: 6, 6: 7, 7: 8, 8: 9, 9: 10, 10: 11,
 
160
                          11: 12}, c)
 
161
 
 
162
    def test_setdefault(self):
 
163
        c = fifo_cache.FIFOCache(5, 4)
 
164
        c['one'] = 1
 
165
        c['two'] = 2
 
166
        c['three'] = 3
 
167
        myobj = object()
 
168
        self.assertIs(myobj, c.setdefault('four', myobj))
 
169
        self.assertEqual({'one': 1, 'two': 2, 'three': 3, 'four': myobj}, c)
 
170
        self.assertEqual(3, c.setdefault('three', myobj))
 
171
        c.setdefault('five', myobj)
 
172
        c.setdefault('six', myobj)
 
173
        self.assertEqual({'three': 3, 'four': myobj, 'five': myobj,
 
174
                          'six': myobj}, c)
 
175
 
 
176
    def test_update(self):
 
177
        c = fifo_cache.FIFOCache(5, 4)
 
178
        # We allow an iterable
 
179
        c.update([(1, 2), (3, 4)])
 
180
        self.assertEqual({1: 2, 3: 4}, c)
 
181
        # Or kwarg form
 
182
        c.update(foo=3, bar=4)
 
183
        self.assertEqual({1: 2, 3: 4, 'foo': 3, 'bar': 4}, c)
 
184
        # Even a dict (This triggers a cleanup)
 
185
        c.update({'baz': 'biz', 'bing': 'bang'})
 
186
        self.assertEqual({'foo': 3, 'bar': 4, 'baz': 'biz', 'bing': 'bang'}, c)
 
187
        # We only allow 1 iterable, just like dict
 
188
        self.assertRaises(TypeError, c.update, [(1, 2)], [(3, 4)])
 
189
        # But you can mix and match. kwargs take precedence over iterable
 
190
        c.update([('a', 'b'), ('d', 'e')], a='c', q='r')
 
191
        self.assertEqual({'baz': 'biz', 'bing': 'bang',
 
192
                          'a': 'c', 'd': 'e', 'q': 'r'}, c)
 
193
 
 
194
    def test_cleanup_funcs(self):
 
195
        log = []
 
196
        def logging_cleanup(key, value):
 
197
            log.append((key, value))
 
198
        c = fifo_cache.FIFOCache(5, 4)
 
199
        c.add(1, 2, cleanup=logging_cleanup)
 
200
        c.add(2, 3, cleanup=logging_cleanup)
 
201
        c.add(3, 4, cleanup=logging_cleanup)
 
202
        c.add(4, 5, cleanup=None) # no cleanup for 4
 
203
        c[5] = 6 # no cleanup for 5
 
204
        self.assertEqual([], log)
 
205
        # Adding another key should cleanup 1 & 2
 
206
        c.add(6, 7, cleanup=logging_cleanup)
 
207
        self.assertEqual([(1, 2), (2, 3)], log)
 
208
        del log[:]
 
209
        # replacing 3 should trigger a cleanup
 
210
        c.add(3, 8, cleanup=logging_cleanup)
 
211
        self.assertEqual([(3, 4)], log)
 
212
        del log[:]
 
213
        c[3] = 9
 
214
        self.assertEqual([(3, 8)], log)
 
215
        del log[:]
 
216
        # Clearing everything should call all remaining cleanups
 
217
        c.clear()
 
218
        self.assertEqual([(6, 7)], log)
 
219
        del log[:]
 
220
        c.add(8, 9, cleanup=logging_cleanup)
 
221
        # __delitem__ should also trigger a cleanup
 
222
        del c[8]
 
223
        self.assertEqual([(8, 9)], log)
 
224
 
 
225
    def test_cleanup_at_deconstruct(self):
 
226
        log = []
 
227
        def logging_cleanup(key, value):
 
228
            log.append((key, value))
 
229
        c = fifo_cache.FIFOCache()
 
230
        c.add(1, 2, cleanup=logging_cleanup)
 
231
        del c
 
232
        # TODO: We currently don't support calling the cleanup() funcs during
 
233
        #       __del__. We might want to consider implementing this.
 
234
        self.expectFailure("we don't call cleanups during __del__",
 
235
                           self.assertEqual, [(1, 2)], log)
 
236
        self.assertEqual([(1, 2)], log)
 
237
 
 
238
 
 
239
class TestFIFOSizeCache(tests.TestCase):
 
240
 
 
241
    def test_add_is_present(self):
 
242
        c = fifo_cache.FIFOSizeCache()
 
243
        c[1] = '2'
 
244
        self.assertTrue(1 in c)
 
245
        self.assertEqual(1, len(c))
 
246
        self.assertEqual('2', c[1])
 
247
        self.assertEqual('2', c.get(1))
 
248
        self.assertEqual('2', c.get(1, None))
 
249
        self.assertEqual([1], c.keys())
 
250
        self.assertEqual([1], list(c.iterkeys()))
 
251
        self.assertEqual([(1, '2')], c.items())
 
252
        self.assertEqual([(1, '2')], list(c.iteritems()))
 
253
        self.assertEqual(['2'], c.values())
 
254
        self.assertEqual(['2'], list(c.itervalues()))
 
255
        self.assertEqual({1: '2'}, c)
 
256
        self.assertEqual(1024*1024, c.cache_size())
 
257
 
 
258
    def test_missing(self):
 
259
        c = fifo_cache.FIFOSizeCache()
 
260
        self.assertRaises(KeyError, c.__getitem__, 1)
 
261
        self.assertFalse(1 in c)
 
262
        self.assertEqual(0, len(c))
 
263
        self.assertEqual(None, c.get(1))
 
264
        self.assertEqual(None, c.get(1, None))
 
265
        self.assertEqual([], c.keys())
 
266
        self.assertEqual([], list(c.iterkeys()))
 
267
        self.assertEqual([], c.items())
 
268
        self.assertEqual([], list(c.iteritems()))
 
269
        self.assertEqual([], c.values())
 
270
        self.assertEqual([], list(c.itervalues()))
 
271
        self.assertEqual({}, c)
 
272
 
 
273
    def test_add_maintains_fifo(self):
 
274
        c = fifo_cache.FIFOSizeCache(10, 8)
 
275
        c[1] = 'ab'
 
276
        c[2] = 'cde'
 
277
        c[3] = 'fghi'
 
278
        self.assertEqual({1: 'ab', 2: 'cde', 3: 'fghi'}, c)
 
279
        c[4] = 'jkl' # Collapse
 
280
        self.assertEqual({3: 'fghi', 4: 'jkl'}, c)
 
281
        # Replacing an item will bump it to the end of the queue
 
282
        c[3] = 'mnop'
 
283
        self.assertEqual({3: 'mnop', 4: 'jkl'}, c)
 
284
        c[5] = 'qrst'
 
285
        self.assertEqual({3: 'mnop', 5: 'qrst'}, c)
 
286
 
 
287
    def test_adding_large_key(self):
 
288
        c = fifo_cache.FIFOSizeCache(10, 8)
 
289
        c[1] = 'abcdefgh' # Adding a large key won't get cached at all
 
290
        self.assertEqual({}, c)
 
291
        c[1] = 'abcdefg'
 
292
        self.assertEqual({1: 'abcdefg'}, c)
 
293
        # Replacing with a too-large key will remove it
 
294
        c[1] = 'abcdefgh'
 
295
        self.assertEqual({}, c)
 
296
        self.assertEqual(0, c._value_size)
 
297
 
 
298
    def test_resize_smaller(self):
 
299
        c = fifo_cache.FIFOSizeCache(20, 16)
 
300
        c[1] = 'a'
 
301
        c[2] = 'bc'
 
302
        c[3] = 'def'
 
303
        c[4] = 'ghij'
 
304
        # No cleanup, because it is the exact size
 
305
        c.resize(10, 8)
 
306
        self.assertEqual({1: 'a', 2: 'bc', 3: 'def', 4: 'ghij'}, c)
 
307
        self.assertEqual(10, c.cache_size())
 
308
        # Adding one more will trigger a cleanup, though
 
309
        c[5] = 'k'
 
310
        self.assertEqual({3: 'def', 4: 'ghij', 5: 'k'}, c)
 
311
        c.resize(5, 4)
 
312
        self.assertEqual({5: 'k'}, c)
 
313
 
 
314
    def test_resize_larger(self):
 
315
        c = fifo_cache.FIFOSizeCache(10, 8)
 
316
        c[1] = 'a'
 
317
        c[2] = 'bc'
 
318
        c[3] = 'def'
 
319
        c[4] = 'ghij'
 
320
        c.resize(12, 10)
 
321
        self.assertEqual({1: 'a', 2: 'bc', 3: 'def', 4: 'ghij'}, c)
 
322
        c[5] = 'kl'
 
323
        self.assertEqual({1: 'a', 2: 'bc', 3: 'def', 4: 'ghij', 5: 'kl'}, c)
 
324
        c[6] = 'mn'
 
325
        self.assertEqual({4: 'ghij', 5: 'kl', 6: 'mn'}, c)