1
# Copyright (C) 2009, 2010, 2011 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."""
26
from bzrlib import _simple_set_pyx
28
_simple_set_pyx = None
31
class _Hashable(object):
32
"""A simple object which has a fixed hash value.
34
We could have used an 'int', but it turns out that Int objects don't
35
implement tp_richcompare...
38
def __init__(self, the_hash):
44
def __eq__(self, other):
45
if not isinstance(other, _Hashable):
47
return other.hash == self.hash
50
class _BadSecondHash(_Hashable):
52
def __init__(self, the_hash):
53
_Hashable.__init__(self, the_hash)
61
raise ValueError('I can only be hashed once.')
64
class _BadCompare(_Hashable):
66
def __eq__(self, other):
67
raise RuntimeError('I refuse to play nice')
70
class _NoImplementCompare(_Hashable):
72
def __eq__(self, other):
76
# Even though this is an extension, we don't permute the tests for a python
77
# version. As the plain python version is just a dict or set
78
compiled_simpleset_feature = tests.ModuleAvailableFeature(
79
'bzrlib._simple_set_pyx')
82
class TestSimpleSet(tests.TestCase):
84
_test_needs_features = [compiled_simpleset_feature]
85
module = _simple_set_pyx
87
def assertIn(self, obj, container):
88
self.assertTrue(obj in container,
89
'%s not found in %s' % (obj, container))
91
def assertNotIn(self, obj, container):
92
self.assertTrue(obj not in container,
93
'We found %s in %s' % (obj, container))
95
def assertFillState(self, used, fill, mask, obj):
96
self.assertEqual((used, fill, mask), (obj.used, obj.fill, obj.mask))
98
def assertLookup(self, offset, value, obj, key):
99
self.assertEqual((offset, value), obj._test_lookup(key))
101
def assertRefcount(self, count, obj):
102
"""Assert that the refcount for obj is what we expect.
104
Note that this automatically adjusts for the fact that calling
105
assertRefcount actually creates a new pointer, as does calling
106
sys.getrefcount. So pass the expected value *before* the call.
108
# I'm not sure why the offset is 3, but I've check that in the caller,
109
# an offset of 1 works, which is expected. Not sure why assertRefcount
110
# is incrementing/decrementing 2 times
111
self.assertEqual(count, sys.getrefcount(obj)-3)
113
def test_initial(self):
114
obj = self.module.SimpleSet()
115
self.assertEqual(0, len(obj))
117
self.assertFillState(0, 0, 0x3ff, obj)
119
def test__lookup(self):
120
# These are carefully chosen integers to force hash collisions in the
121
# algorithm, based on the initial set size of 1024
122
obj = self.module.SimpleSet()
123
self.assertLookup(643, '<null>', obj, _Hashable(643))
124
self.assertLookup(643, '<null>', obj, _Hashable(643 + 1024))
125
self.assertLookup(643, '<null>', obj, _Hashable(643 + 50*1024))
127
def test__lookup_collision(self):
128
obj = self.module.SimpleSet()
130
k2 = _Hashable(643 + 1024)
131
self.assertLookup(643, '<null>', obj, k1)
132
self.assertLookup(643, '<null>', obj, k2)
134
self.assertLookup(643, k1, obj, k1)
135
self.assertLookup(644, '<null>', obj, k2)
137
def test__lookup_after_resize(self):
138
obj = self.module.SimpleSet()
140
k2 = _Hashable(643 + 1024)
143
self.assertLookup(643, k1, obj, k1)
144
self.assertLookup(644, k2, obj, k2)
145
obj._py_resize(2047) # resized to 2048
146
self.assertEqual(2048, obj.mask + 1)
147
self.assertLookup(643, k1, obj, k1)
148
self.assertLookup(643+1024, k2, obj, k2)
149
obj._py_resize(1023) # resized back to 1024
150
self.assertEqual(1024, obj.mask + 1)
151
self.assertLookup(643, k1, obj, k1)
152
self.assertLookup(644, k2, obj, k2)
154
def test_get_set_del_with_collisions(self):
155
obj = self.module.SimpleSet()
170
self.assertLookup(643, '<null>', obj, k1)
171
self.assertLookup(643, '<null>', obj, k2)
172
self.assertLookup(643, '<null>', obj, k3)
173
self.assertLookup(643, '<null>', obj, k4)
174
self.assertLookup(644, '<null>', obj, k5)
175
self.assertLookup(644, '<null>', obj, k6)
177
self.assertIn(k1, obj)
178
self.assertNotIn(k2, obj)
179
self.assertNotIn(k3, obj)
180
self.assertNotIn(k4, obj)
181
self.assertLookup(643, k1, obj, k1)
182
self.assertLookup(644, '<null>', obj, k2)
183
self.assertLookup(644, '<null>', obj, k3)
184
self.assertLookup(644, '<null>', obj, k4)
185
self.assertLookup(644, '<null>', obj, k5)
186
self.assertLookup(644, '<null>', obj, k6)
187
self.assertIs(k1, obj[k1])
188
self.assertIs(k2, obj.add(k2))
189
self.assertIs(k2, obj[k2])
190
self.assertLookup(643, k1, obj, k1)
191
self.assertLookup(644, k2, obj, k2)
192
self.assertLookup(646, '<null>', obj, k3)
193
self.assertLookup(646, '<null>', obj, k4)
194
self.assertLookup(645, '<null>', obj, k5)
195
self.assertLookup(645, '<null>', obj, k6)
196
self.assertLookup(643, k1, obj, _Hashable(h1))
197
self.assertLookup(644, k2, obj, _Hashable(h2))
198
self.assertLookup(646, '<null>', obj, _Hashable(h3))
199
self.assertLookup(646, '<null>', obj, _Hashable(h4))
200
self.assertLookup(645, '<null>', obj, _Hashable(h5))
201
self.assertLookup(645, '<null>', obj, _Hashable(h6))
203
self.assertIs(k3, obj[k3])
204
self.assertIn(k1, obj)
205
self.assertIn(k2, obj)
206
self.assertIn(k3, obj)
207
self.assertNotIn(k4, obj)
210
self.assertLookup(643, '<dummy>', obj, k1)
211
self.assertLookup(644, k2, obj, k2)
212
self.assertLookup(646, k3, obj, k3)
213
self.assertLookup(643, '<dummy>', obj, k4)
214
self.assertNotIn(k1, obj)
215
self.assertIn(k2, obj)
216
self.assertIn(k3, obj)
217
self.assertNotIn(k4, obj)
220
obj = self.module.SimpleSet()
221
self.assertFillState(0, 0, 0x3ff, obj)
222
# We use this clumsy notation, because otherwise the refcounts are off.
223
# I'm guessing the python compiler sees it is a static tuple, and adds
224
# it to the function variables, or somesuch
226
self.assertRefcount(1, k1)
227
self.assertIs(k1, obj.add(k1))
228
self.assertFillState(1, 1, 0x3ff, obj)
229
self.assertRefcount(2, k1)
231
self.assertRefcount(3, k1)
232
self.assertIs(k1, ktest)
234
self.assertRefcount(2, k1)
236
self.assertRefcount(1, k2)
237
self.assertIsNot(k1, k2)
238
# doesn't add anything, so the counters shouldn't be adjusted
239
self.assertIs(k1, obj.add(k2))
240
self.assertFillState(1, 1, 0x3ff, obj)
241
self.assertRefcount(2, k1) # not changed
242
self.assertRefcount(1, k2) # not incremented
243
self.assertIs(k1, obj[k1])
244
self.assertIs(k1, obj[k2])
245
self.assertRefcount(2, k1)
246
self.assertRefcount(1, k2)
247
# Deleting an entry should remove the fill, but not the used
249
self.assertFillState(0, 1, 0x3ff, obj)
250
self.assertRefcount(1, k1)
252
self.assertRefcount(1, k3)
253
self.assertIs(k3, obj.add(k3))
254
self.assertFillState(1, 2, 0x3ff, obj)
255
self.assertRefcount(2, k3)
256
self.assertIs(k2, obj.add(k2))
257
self.assertFillState(2, 2, 0x3ff, obj)
258
self.assertRefcount(1, k1)
259
self.assertRefcount(2, k2)
260
self.assertRefcount(2, k3)
262
def test_discard(self):
263
obj = self.module.SimpleSet()
267
self.assertRefcount(1, k1)
268
self.assertRefcount(1, k2)
269
self.assertRefcount(1, k3)
271
self.assertRefcount(2, k1)
272
self.assertEqual(0, obj.discard(k3))
273
self.assertRefcount(1, k3)
275
self.assertRefcount(2, k3)
276
self.assertEqual(1, obj.discard(k3))
277
self.assertRefcount(1, k3)
279
def test__resize(self):
280
obj = self.module.SimpleSet()
288
self.assertFillState(2, 3, 0x3ff, obj)
289
self.assertEqual(1024, obj._py_resize(500))
290
# Doesn't change the size, but does change the content
291
self.assertFillState(2, 2, 0x3ff, obj)
294
self.assertFillState(2, 3, 0x3ff, obj)
295
self.assertEqual(4096, obj._py_resize(4095))
296
self.assertFillState(2, 2, 0xfff, obj)
297
self.assertIn(k1, obj)
298
self.assertIn(k2, obj)
299
self.assertNotIn(k3, obj)
301
self.assertIn(k2, obj)
303
self.assertEqual((591, '<dummy>'), obj._test_lookup(k2))
304
self.assertFillState(1, 2, 0xfff, obj)
305
self.assertEqual(2048, obj._py_resize(1024))
306
self.assertFillState(1, 1, 0x7ff, obj)
307
self.assertEqual((591, '<null>'), obj._test_lookup(k2))
309
def test_second_hash_failure(self):
310
obj = self.module.SimpleSet()
311
k1 = _BadSecondHash(200)
313
# Should only call hash() one time
315
self.assertFalse(k1._first)
316
self.assertRaises(ValueError, obj.add, k2)
318
def test_richcompare_failure(self):
319
obj = self.module.SimpleSet()
321
k2 = _BadCompare(200)
323
# Tries to compare with k1, fails
324
self.assertRaises(RuntimeError, obj.add, k2)
326
def test_richcompare_not_implemented(self):
327
obj = self.module.SimpleSet()
328
# Even though their hashes are the same, tp_richcompare returns
329
# NotImplemented, which means we treat them as not equal
330
k1 = _NoImplementCompare(200)
331
k2 = _NoImplementCompare(200)
332
self.assertLookup(200, '<null>', obj, k1)
333
self.assertLookup(200, '<null>', obj, k2)
334
self.assertIs(k1, obj.add(k1))
335
self.assertLookup(200, k1, obj, k1)
336
self.assertLookup(201, '<null>', obj, k2)
337
self.assertIs(k2, obj.add(k2))
338
self.assertIs(k1, obj[k1])
340
def test_add_and_remove_lots_of_items(self):
341
obj = self.module.SimpleSet()
342
chars = 'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz1234567890'
347
num = len(chars)*len(chars)
348
self.assertFillState(num, num, 0x1fff, obj)
349
# Now delete all of the entries and it should shrink again
354
# It should be back to 1024 wide mask, though there may still be some
355
# dummy values in there
356
self.assertFillState(0, obj.fill, 0x3ff, obj)
357
# but there should be fewer than 1/5th dummy entries
358
self.assertTrue(obj.fill < 1024 / 5)
360
def test__iter__(self):
361
obj = self.module.SimpleSet()
371
self.assertEqual(sorted([k1, k2, k3]), sorted(all))
376
self.assertRaises(RuntimeError, iterator.next)
377
# And even removing an item still causes it to fail
379
self.assertRaises(RuntimeError, iterator.next)
381
def test__sizeof__(self):
382
# SimpleSet needs a custom sizeof implementation, because it allocates
383
# memory that Python cannot directly see (_table).
384
# Too much variability in platform sizes for us to give a fixed size
385
# here. However without a custom implementation, __sizeof__ would give
386
# us only the size of the object, and not its table. We know the table
387
# is at least 4bytes*1024entries in size.
388
obj = self.module.SimpleSet()
389
self.assertTrue(obj.__sizeof__() > 4096)
added
removed
bzrlib/tests/test__simple_set.py
