1
# Copyright (C) 2009, 2010 Canonical Ltd
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.
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.
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
17
"""Tests for the StaticTupleInterned type."""
28
from bzrlib import _simple_set_pyx
30
_simple_set_pyx = None
33
class _Hashable(object):
34
"""A simple object which has a fixed hash value.
36
We could have used an 'int', but it turns out that Int objects don't
37
implement tp_richcompare...
40
def __init__(self, the_hash):
46
def __eq__(self, other):
47
if not isinstance(other, _Hashable):
49
return other.hash == self.hash
52
class _BadSecondHash(_Hashable):
54
def __init__(self, the_hash):
55
_Hashable.__init__(self, the_hash)
63
raise ValueError('I can only be hashed once.')
66
class _BadCompare(_Hashable):
68
def __eq__(self, other):
69
raise RuntimeError('I refuse to play nice')
72
class _NoImplementCompare(_Hashable):
74
def __eq__(self, other):
78
# Even though this is an extension, we don't permute the tests for a python
79
# version. As the plain python version is just a dict or set
80
compiled_simpleset_feature = tests.ModuleAvailableFeature(
81
'bzrlib._simple_set_pyx')
84
class TestSimpleSet(tests.TestCase):
86
_test_needs_features = [compiled_simpleset_feature]
87
module = _simple_set_pyx
89
def assertIn(self, obj, container):
90
self.assertTrue(obj in container,
91
'%s not found in %s' % (obj, container))
93
def assertNotIn(self, obj, container):
94
self.assertTrue(obj not in container,
95
'We found %s in %s' % (obj, container))
97
def assertFillState(self, used, fill, mask, obj):
98
self.assertEqual((used, fill, mask), (obj.used, obj.fill, obj.mask))
100
def assertLookup(self, offset, value, obj, key):
101
self.assertEqual((offset, value), obj._test_lookup(key))
103
def assertRefcount(self, count, obj):
104
"""Assert that the refcount for obj is what we expect.
106
Note that this automatically adjusts for the fact that calling
107
assertRefcount actually creates a new pointer, as does calling
108
sys.getrefcount. So pass the expected value *before* the call.
110
# I'm not sure why the offset is 3, but I've check that in the caller,
111
# an offset of 1 works, which is expected. Not sure why assertRefcount
112
# is incrementing/decrementing 2 times
113
self.assertEqual(count, sys.getrefcount(obj)-3)
115
def test_initial(self):
116
obj = self.module.SimpleSet()
117
self.assertEqual(0, len(obj))
119
self.assertFillState(0, 0, 0x3ff, obj)
121
def test__lookup(self):
122
# These are carefully chosen integers to force hash collisions in the
123
# algorithm, based on the initial set size of 1024
124
obj = self.module.SimpleSet()
125
self.assertLookup(643, '<null>', obj, _Hashable(643))
126
self.assertLookup(643, '<null>', obj, _Hashable(643 + 1024))
127
self.assertLookup(643, '<null>', obj, _Hashable(643 + 50*1024))
129
def test__lookup_collision(self):
130
obj = self.module.SimpleSet()
132
k2 = _Hashable(643 + 1024)
133
self.assertLookup(643, '<null>', obj, k1)
134
self.assertLookup(643, '<null>', obj, k2)
136
self.assertLookup(643, k1, obj, k1)
137
self.assertLookup(644, '<null>', obj, k2)
139
def test__lookup_after_resize(self):
140
obj = self.module.SimpleSet()
142
k2 = _Hashable(643 + 1024)
145
self.assertLookup(643, k1, obj, k1)
146
self.assertLookup(644, k2, obj, k2)
147
obj._py_resize(2047) # resized to 2048
148
self.assertEqual(2048, obj.mask + 1)
149
self.assertLookup(643, k1, obj, k1)
150
self.assertLookup(643+1024, k2, obj, k2)
151
obj._py_resize(1023) # resized back to 1024
152
self.assertEqual(1024, obj.mask + 1)
153
self.assertLookup(643, k1, obj, k1)
154
self.assertLookup(644, k2, obj, k2)
156
def test_get_set_del_with_collisions(self):
157
obj = self.module.SimpleSet()
172
self.assertLookup(643, '<null>', obj, k1)
173
self.assertLookup(643, '<null>', obj, k2)
174
self.assertLookup(643, '<null>', obj, k3)
175
self.assertLookup(643, '<null>', obj, k4)
176
self.assertLookup(644, '<null>', obj, k5)
177
self.assertLookup(644, '<null>', obj, k6)
179
self.assertIn(k1, obj)
180
self.assertNotIn(k2, obj)
181
self.assertNotIn(k3, obj)
182
self.assertNotIn(k4, obj)
183
self.assertLookup(643, k1, obj, k1)
184
self.assertLookup(644, '<null>', obj, k2)
185
self.assertLookup(644, '<null>', obj, k3)
186
self.assertLookup(644, '<null>', obj, k4)
187
self.assertLookup(644, '<null>', obj, k5)
188
self.assertLookup(644, '<null>', obj, k6)
189
self.assertIs(k1, obj[k1])
190
self.assertIs(k2, obj.add(k2))
191
self.assertIs(k2, obj[k2])
192
self.assertLookup(643, k1, obj, k1)
193
self.assertLookup(644, k2, obj, k2)
194
self.assertLookup(646, '<null>', obj, k3)
195
self.assertLookup(646, '<null>', obj, k4)
196
self.assertLookup(645, '<null>', obj, k5)
197
self.assertLookup(645, '<null>', obj, k6)
198
self.assertLookup(643, k1, obj, _Hashable(h1))
199
self.assertLookup(644, k2, obj, _Hashable(h2))
200
self.assertLookup(646, '<null>', obj, _Hashable(h3))
201
self.assertLookup(646, '<null>', obj, _Hashable(h4))
202
self.assertLookup(645, '<null>', obj, _Hashable(h5))
203
self.assertLookup(645, '<null>', obj, _Hashable(h6))
205
self.assertIs(k3, obj[k3])
206
self.assertIn(k1, obj)
207
self.assertIn(k2, obj)
208
self.assertIn(k3, obj)
209
self.assertNotIn(k4, obj)
212
self.assertLookup(643, '<dummy>', obj, k1)
213
self.assertLookup(644, k2, obj, k2)
214
self.assertLookup(646, k3, obj, k3)
215
self.assertLookup(643, '<dummy>', obj, k4)
216
self.assertNotIn(k1, obj)
217
self.assertIn(k2, obj)
218
self.assertIn(k3, obj)
219
self.assertNotIn(k4, obj)
222
obj = self.module.SimpleSet()
223
self.assertFillState(0, 0, 0x3ff, obj)
224
# We use this clumsy notation, because otherwise the refcounts are off.
225
# I'm guessing the python compiler sees it is a static tuple, and adds
226
# it to the function variables, or somesuch
228
self.assertRefcount(1, k1)
229
self.assertIs(k1, obj.add(k1))
230
self.assertFillState(1, 1, 0x3ff, obj)
231
self.assertRefcount(2, k1)
233
self.assertRefcount(3, k1)
234
self.assertIs(k1, ktest)
236
self.assertRefcount(2, k1)
238
self.assertRefcount(1, k2)
239
self.assertIsNot(k1, k2)
240
# doesn't add anything, so the counters shouldn't be adjusted
241
self.assertIs(k1, obj.add(k2))
242
self.assertFillState(1, 1, 0x3ff, obj)
243
self.assertRefcount(2, k1) # not changed
244
self.assertRefcount(1, k2) # not incremented
245
self.assertIs(k1, obj[k1])
246
self.assertIs(k1, obj[k2])
247
self.assertRefcount(2, k1)
248
self.assertRefcount(1, k2)
249
# Deleting an entry should remove the fill, but not the used
251
self.assertFillState(0, 1, 0x3ff, obj)
252
self.assertRefcount(1, k1)
254
self.assertRefcount(1, k3)
255
self.assertIs(k3, obj.add(k3))
256
self.assertFillState(1, 2, 0x3ff, obj)
257
self.assertRefcount(2, k3)
258
self.assertIs(k2, obj.add(k2))
259
self.assertFillState(2, 2, 0x3ff, obj)
260
self.assertRefcount(1, k1)
261
self.assertRefcount(2, k2)
262
self.assertRefcount(2, k3)
264
def test_discard(self):
265
obj = self.module.SimpleSet()
269
self.assertRefcount(1, k1)
270
self.assertRefcount(1, k2)
271
self.assertRefcount(1, k3)
273
self.assertRefcount(2, k1)
274
self.assertEqual(0, obj.discard(k3))
275
self.assertRefcount(1, k3)
277
self.assertRefcount(2, k3)
278
self.assertEqual(1, obj.discard(k3))
279
self.assertRefcount(1, k3)
281
def test__resize(self):
282
obj = self.module.SimpleSet()
290
self.assertFillState(2, 3, 0x3ff, obj)
291
self.assertEqual(1024, obj._py_resize(500))
292
# Doesn't change the size, but does change the content
293
self.assertFillState(2, 2, 0x3ff, obj)
296
self.assertFillState(2, 3, 0x3ff, obj)
297
self.assertEqual(4096, obj._py_resize(4095))
298
self.assertFillState(2, 2, 0xfff, obj)
299
self.assertIn(k1, obj)
300
self.assertIn(k2, obj)
301
self.assertNotIn(k3, obj)
303
self.assertIn(k2, obj)
305
self.assertEqual((591, '<dummy>'), obj._test_lookup(k2))
306
self.assertFillState(1, 2, 0xfff, obj)
307
self.assertEqual(2048, obj._py_resize(1024))
308
self.assertFillState(1, 1, 0x7ff, obj)
309
self.assertEqual((591, '<null>'), obj._test_lookup(k2))
311
def test_second_hash_failure(self):
312
obj = self.module.SimpleSet()
313
k1 = _BadSecondHash(200)
315
# Should only call hash() one time
317
self.assertFalse(k1._first)
318
self.assertRaises(ValueError, obj.add, k2)
320
def test_richcompare_failure(self):
321
obj = self.module.SimpleSet()
323
k2 = _BadCompare(200)
325
# Tries to compare with k1, fails
326
self.assertRaises(RuntimeError, obj.add, k2)
328
def test_richcompare_not_implemented(self):
329
obj = self.module.SimpleSet()
330
# Even though their hashes are the same, tp_richcompare returns
331
# NotImplemented, which means we treat them as not equal
332
k1 = _NoImplementCompare(200)
333
k2 = _NoImplementCompare(200)
334
self.assertLookup(200, '<null>', obj, k1)
335
self.assertLookup(200, '<null>', obj, k2)
336
self.assertIs(k1, obj.add(k1))
337
self.assertLookup(200, k1, obj, k1)
338
self.assertLookup(201, '<null>', obj, k2)
339
self.assertIs(k2, obj.add(k2))
340
self.assertIs(k1, obj[k1])
342
def test_add_and_remove_lots_of_items(self):
343
obj = self.module.SimpleSet()
344
chars = 'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz1234567890'
349
num = len(chars)*len(chars)
350
self.assertFillState(num, num, 0x1fff, obj)
351
# Now delete all of the entries and it should shrink again
356
# It should be back to 1024 wide mask, though there may still be some
357
# dummy values in there
358
self.assertFillState(0, obj.fill, 0x3ff, obj)
359
# but there should be fewer than 1/5th dummy entries
360
self.assertTrue(obj.fill < 1024 / 5)
362
def test__iter__(self):
363
obj = self.module.SimpleSet()
373
self.assertEqual(sorted([k1, k2, k3]), sorted(all))
378
self.assertRaises(RuntimeError, iterator.next)
379
# And even removing an item still causes it to fail
381
self.assertRaises(RuntimeError, iterator.next)
added
removed
bzrlib/tests/test__simple_set.py
