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."""
24
from bzrlib.tests import (
29
from bzrlib import _simple_set_pyx
31
_simple_set_pyx = None
34
class _Hashable(object):
35
"""A simple object which has a fixed hash value.
37
We could have used an 'int', but it turns out that Int objects don't
38
implement tp_richcompare...
41
def __init__(self, the_hash):
47
def __eq__(self, other):
48
if not isinstance(other, _Hashable):
50
return other.hash == self.hash
53
class _BadSecondHash(_Hashable):
55
def __init__(self, the_hash):
56
_Hashable.__init__(self, the_hash)
64
raise ValueError('I can only be hashed once.')
67
class _BadCompare(_Hashable):
69
def __eq__(self, other):
70
raise RuntimeError('I refuse to play nice')
73
class _NoImplementCompare(_Hashable):
75
def __eq__(self, other):
79
# Even though this is an extension, we don't permute the tests for a python
80
# version. As the plain python version is just a dict or set
81
compiled_simpleset_feature = features.ModuleAvailableFeature(
82
'bzrlib._simple_set_pyx')
85
class TestSimpleSet(tests.TestCase):
87
_test_needs_features = [compiled_simpleset_feature]
88
module = _simple_set_pyx
90
def assertIn(self, obj, container):
91
self.assertTrue(obj in container,
92
'%s not found in %s' % (obj, container))
94
def assertNotIn(self, obj, container):
95
self.assertTrue(obj not in container,
96
'We found %s in %s' % (obj, container))
98
def assertFillState(self, used, fill, mask, obj):
99
self.assertEqual((used, fill, mask), (obj.used, obj.fill, obj.mask))
101
def assertLookup(self, offset, value, obj, key):
102
self.assertEqual((offset, value), obj._test_lookup(key))
104
def assertRefcount(self, count, obj):
105
"""Assert that the refcount for obj is what we expect.
107
Note that this automatically adjusts for the fact that calling
108
assertRefcount actually creates a new pointer, as does calling
109
sys.getrefcount. So pass the expected value *before* the call.
111
# I'm not sure why the offset is 3, but I've check that in the caller,
112
# an offset of 1 works, which is expected. Not sure why assertRefcount
113
# is incrementing/decrementing 2 times
114
self.assertEqual(count, sys.getrefcount(obj)-3)
116
def test_initial(self):
117
obj = self.module.SimpleSet()
118
self.assertEqual(0, len(obj))
120
self.assertFillState(0, 0, 0x3ff, obj)
122
def test__lookup(self):
123
# These are carefully chosen integers to force hash collisions in the
124
# algorithm, based on the initial set size of 1024
125
obj = self.module.SimpleSet()
126
self.assertLookup(643, '<null>', obj, _Hashable(643))
127
self.assertLookup(643, '<null>', obj, _Hashable(643 + 1024))
128
self.assertLookup(643, '<null>', obj, _Hashable(643 + 50*1024))
130
def test__lookup_collision(self):
131
obj = self.module.SimpleSet()
133
k2 = _Hashable(643 + 1024)
134
self.assertLookup(643, '<null>', obj, k1)
135
self.assertLookup(643, '<null>', obj, k2)
137
self.assertLookup(643, k1, obj, k1)
138
self.assertLookup(644, '<null>', obj, k2)
140
def test__lookup_after_resize(self):
141
obj = self.module.SimpleSet()
143
k2 = _Hashable(643 + 1024)
146
self.assertLookup(643, k1, obj, k1)
147
self.assertLookup(644, k2, obj, k2)
148
obj._py_resize(2047) # resized to 2048
149
self.assertEqual(2048, obj.mask + 1)
150
self.assertLookup(643, k1, obj, k1)
151
self.assertLookup(643+1024, k2, obj, k2)
152
obj._py_resize(1023) # resized back to 1024
153
self.assertEqual(1024, obj.mask + 1)
154
self.assertLookup(643, k1, obj, k1)
155
self.assertLookup(644, k2, obj, k2)
157
def test_get_set_del_with_collisions(self):
158
obj = self.module.SimpleSet()
173
self.assertLookup(643, '<null>', obj, k1)
174
self.assertLookup(643, '<null>', obj, k2)
175
self.assertLookup(643, '<null>', obj, k3)
176
self.assertLookup(643, '<null>', obj, k4)
177
self.assertLookup(644, '<null>', obj, k5)
178
self.assertLookup(644, '<null>', obj, k6)
180
self.assertIn(k1, obj)
181
self.assertNotIn(k2, obj)
182
self.assertNotIn(k3, obj)
183
self.assertNotIn(k4, obj)
184
self.assertLookup(643, k1, obj, k1)
185
self.assertLookup(644, '<null>', obj, k2)
186
self.assertLookup(644, '<null>', obj, k3)
187
self.assertLookup(644, '<null>', obj, k4)
188
self.assertLookup(644, '<null>', obj, k5)
189
self.assertLookup(644, '<null>', obj, k6)
190
self.assertIs(k1, obj[k1])
191
self.assertIs(k2, obj.add(k2))
192
self.assertIs(k2, obj[k2])
193
self.assertLookup(643, k1, obj, k1)
194
self.assertLookup(644, k2, obj, k2)
195
self.assertLookup(646, '<null>', obj, k3)
196
self.assertLookup(646, '<null>', obj, k4)
197
self.assertLookup(645, '<null>', obj, k5)
198
self.assertLookup(645, '<null>', obj, k6)
199
self.assertLookup(643, k1, obj, _Hashable(h1))
200
self.assertLookup(644, k2, obj, _Hashable(h2))
201
self.assertLookup(646, '<null>', obj, _Hashable(h3))
202
self.assertLookup(646, '<null>', obj, _Hashable(h4))
203
self.assertLookup(645, '<null>', obj, _Hashable(h5))
204
self.assertLookup(645, '<null>', obj, _Hashable(h6))
206
self.assertIs(k3, obj[k3])
207
self.assertIn(k1, obj)
208
self.assertIn(k2, obj)
209
self.assertIn(k3, obj)
210
self.assertNotIn(k4, obj)
213
self.assertLookup(643, '<dummy>', obj, k1)
214
self.assertLookup(644, k2, obj, k2)
215
self.assertLookup(646, k3, obj, k3)
216
self.assertLookup(643, '<dummy>', obj, k4)
217
self.assertNotIn(k1, obj)
218
self.assertIn(k2, obj)
219
self.assertIn(k3, obj)
220
self.assertNotIn(k4, obj)
223
obj = self.module.SimpleSet()
224
self.assertFillState(0, 0, 0x3ff, obj)
225
# We use this clumsy notation, because otherwise the refcounts are off.
226
# I'm guessing the python compiler sees it is a static tuple, and adds
227
# it to the function variables, or somesuch
229
self.assertRefcount(1, k1)
230
self.assertIs(k1, obj.add(k1))
231
self.assertFillState(1, 1, 0x3ff, obj)
232
self.assertRefcount(2, k1)
234
self.assertRefcount(3, k1)
235
self.assertIs(k1, ktest)
237
self.assertRefcount(2, k1)
239
self.assertRefcount(1, k2)
240
self.assertIsNot(k1, k2)
241
# doesn't add anything, so the counters shouldn't be adjusted
242
self.assertIs(k1, obj.add(k2))
243
self.assertFillState(1, 1, 0x3ff, obj)
244
self.assertRefcount(2, k1) # not changed
245
self.assertRefcount(1, k2) # not incremented
246
self.assertIs(k1, obj[k1])
247
self.assertIs(k1, obj[k2])
248
self.assertRefcount(2, k1)
249
self.assertRefcount(1, k2)
250
# Deleting an entry should remove the fill, but not the used
252
self.assertFillState(0, 1, 0x3ff, obj)
253
self.assertRefcount(1, k1)
255
self.assertRefcount(1, k3)
256
self.assertIs(k3, obj.add(k3))
257
self.assertFillState(1, 2, 0x3ff, obj)
258
self.assertRefcount(2, k3)
259
self.assertIs(k2, obj.add(k2))
260
self.assertFillState(2, 2, 0x3ff, obj)
261
self.assertRefcount(1, k1)
262
self.assertRefcount(2, k2)
263
self.assertRefcount(2, k3)
265
def test_discard(self):
266
obj = self.module.SimpleSet()
270
self.assertRefcount(1, k1)
271
self.assertRefcount(1, k2)
272
self.assertRefcount(1, k3)
274
self.assertRefcount(2, k1)
275
self.assertEqual(0, obj.discard(k3))
276
self.assertRefcount(1, k3)
278
self.assertRefcount(2, k3)
279
self.assertEqual(1, obj.discard(k3))
280
self.assertRefcount(1, k3)
282
def test__resize(self):
283
obj = self.module.SimpleSet()
291
self.assertFillState(2, 3, 0x3ff, obj)
292
self.assertEqual(1024, obj._py_resize(500))
293
# Doesn't change the size, but does change the content
294
self.assertFillState(2, 2, 0x3ff, obj)
297
self.assertFillState(2, 3, 0x3ff, obj)
298
self.assertEqual(4096, obj._py_resize(4095))
299
self.assertFillState(2, 2, 0xfff, obj)
300
self.assertIn(k1, obj)
301
self.assertIn(k2, obj)
302
self.assertNotIn(k3, obj)
304
self.assertIn(k2, obj)
306
self.assertEqual((591, '<dummy>'), obj._test_lookup(k2))
307
self.assertFillState(1, 2, 0xfff, obj)
308
self.assertEqual(2048, obj._py_resize(1024))
309
self.assertFillState(1, 1, 0x7ff, obj)
310
self.assertEqual((591, '<null>'), obj._test_lookup(k2))
312
def test_second_hash_failure(self):
313
obj = self.module.SimpleSet()
314
k1 = _BadSecondHash(200)
316
# Should only call hash() one time
318
self.assertFalse(k1._first)
319
self.assertRaises(ValueError, obj.add, k2)
321
def test_richcompare_failure(self):
322
obj = self.module.SimpleSet()
324
k2 = _BadCompare(200)
326
# Tries to compare with k1, fails
327
self.assertRaises(RuntimeError, obj.add, k2)
329
def test_richcompare_not_implemented(self):
330
obj = self.module.SimpleSet()
331
# Even though their hashes are the same, tp_richcompare returns
332
# NotImplemented, which means we treat them as not equal
333
k1 = _NoImplementCompare(200)
334
k2 = _NoImplementCompare(200)
335
self.assertLookup(200, '<null>', obj, k1)
336
self.assertLookup(200, '<null>', obj, k2)
337
self.assertIs(k1, obj.add(k1))
338
self.assertLookup(200, k1, obj, k1)
339
self.assertLookup(201, '<null>', obj, k2)
340
self.assertIs(k2, obj.add(k2))
341
self.assertIs(k1, obj[k1])
343
def test_add_and_remove_lots_of_items(self):
344
obj = self.module.SimpleSet()
345
chars = 'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz1234567890'
350
num = len(chars)*len(chars)
351
self.assertFillState(num, num, 0x1fff, obj)
352
# Now delete all of the entries and it should shrink again
357
# It should be back to 1024 wide mask, though there may still be some
358
# dummy values in there
359
self.assertFillState(0, obj.fill, 0x3ff, obj)
360
# but there should be fewer than 1/5th dummy entries
361
self.assertTrue(obj.fill < 1024 / 5)
363
def test__iter__(self):
364
obj = self.module.SimpleSet()
374
self.assertEqual(sorted([k1, k2, k3]), sorted(all))
379
self.assertRaises(RuntimeError, iterator.next)
380
# And even removing an item still causes it to fail
382
self.assertRaises(RuntimeError, iterator.next)
384
def test__sizeof__(self):
385
# SimpleSet needs a custom sizeof implementation, because it allocates
386
# memory that Python cannot directly see (_table).
387
# Too much variability in platform sizes for us to give a fixed size
388
# here. However without a custom implementation, __sizeof__ would give
389
# us only the size of the object, and not its table. We know the table
390
# is at least 4bytes*1024entries in size.
391
obj = self.module.SimpleSet()
392
self.assertTrue(obj.__sizeof__() > 4096)
added
removed
bzrlib/tests/test__simple_set.py
