← 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: 2008-10-04 14:10:13 UTC
  • mto: This revision was merged to the branch mainline in revision 3805.
  • Revision ID: john@arbash-meinel.com-20081004141013-yskxjlwtuy2k18ue
Playing around with expanding requests for btree index nodes into neighboring nodes.

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
 
        # As a matter of design, bzr does not (can not) count on anything
233
 
        # being run from Python __del__ methods, because they may not run for
234
 
        # a long time, and because in cPython merely having them defined
235
 
        # interferes with garbage collection.
236
 
        self.assertEqual([], 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)