1
# Copyright (C) 2007, 2009, 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 bisect_multi."""
19
from bzrlib.bisect_multi import bisect_multi_bytes
20
from bzrlib.tests import TestCase
23
class TestBisectMultiBytes(TestCase):
25
def test_lookup_no_keys_no_calls(self):
27
def missing_content(location_keys):
28
calls.append(location_keys)
29
return ((location_key, False) for location_key in location_keys)
31
list(bisect_multi_bytes(missing_content, 100, [])))
32
self.assertEqual([], calls)
34
def test_lookup_missing_key_no_content(self):
35
"""Doing a lookup in a zero-length file still does a single request.
37
This makes sense because the bisector cannot tell how long content is
38
and its more flexible to only stop when the content object says 'False'
39
for a given location, key pair.
42
def missing_content(location_keys):
43
calls.append(location_keys)
44
return ((location_key, False) for location_key in location_keys)
46
list(bisect_multi_bytes(missing_content, 0, ['foo', 'bar'])))
47
self.assertEqual([[(0, 'foo'), (0, 'bar')]], calls)
49
def test_lookup_missing_key_before_all_others(self):
51
def missing_first_content(location_keys):
52
# returns -1 for all keys unless the byte offset is 0 when it
54
calls.append(location_keys)
56
for location_key in location_keys:
57
if location_key[0] == 0:
58
result.append((location_key, False))
60
result.append((location_key, -1))
62
# given a 0 length file, this should terminate with one call.
64
list(bisect_multi_bytes(missing_first_content, 0, ['foo', 'bar'])))
65
self.assertEqual([[(0, 'foo'), (0, 'bar')]], calls)
67
# given a 2 length file, this should make two calls - 1, 0.
69
list(bisect_multi_bytes(missing_first_content, 2, ['foo', 'bar'])))
71
[(1, 'foo'), (1, 'bar')],
72
[(0, 'foo'), (0, 'bar')],
75
# given a really long file - 200MB, this should make a series of calls with the
76
# gap between adjactent calls dropping by 50% each time. We choose a
77
# length which just under a power of two to generate a corner case in
78
# bisection - naively using power of two reduction in size can lead to
79
# a very long tail in the bisection process. The current users of
80
# the bisect_multi_bytes api are not expected to be concerned by this,
81
# as the delta gets down to 4K (the minimum we expect to read and
82
# parse) within 16 steps even on a 200MB index (which at 4 keys/K is
83
# 800 thousand keys, and log2 of 800000 is 19 - so we're doing log2
84
# steps in the worst case there.
86
list(bisect_multi_bytes(
87
missing_first_content,268435456 - 1 , ['foo', 'bar'])))
89
[(134217727, 'foo'), (134217727, 'bar')],
90
[(67108864, 'foo'), (67108864, 'bar')],
91
[(33554433, 'foo'), (33554433, 'bar')],
92
[(16777218, 'foo'), (16777218, 'bar')],
93
[(8388611, 'foo'), (8388611, 'bar')],
94
[(4194308, 'foo'), (4194308, 'bar')],
95
[(2097157, 'foo'), (2097157, 'bar')],
96
[(1048582, 'foo'), (1048582, 'bar')],
97
[(524295, 'foo'), (524295, 'bar')],
98
[(262152, 'foo'), (262152, 'bar')],
99
[(131081, 'foo'), (131081, 'bar')],
100
[(65546, 'foo'), (65546, 'bar')],
101
[(32779, 'foo'), (32779, 'bar')],
102
[(16396, 'foo'), (16396, 'bar')],
103
[(8205, 'foo'), (8205, 'bar')],
104
[(4110, 'foo'), (4110, 'bar')],
105
[(2063, 'foo'), (2063, 'bar')],
106
[(1040, 'foo'), (1040, 'bar')],
107
[(529, 'foo'), (529, 'bar')],
108
[(274, 'foo'), (274, 'bar')],
109
[(147, 'foo'), (147, 'bar')],
110
[(84, 'foo'), (84, 'bar')],
111
[(53, 'foo'), (53, 'bar')],
112
[(38, 'foo'), (38, 'bar')],
113
[(31, 'foo'), (31, 'bar')],
114
[(28, 'foo'), (28, 'bar')],
115
[(27, 'foo'), (27, 'bar')],
116
[(26, 'foo'), (26, 'bar')],
117
[(25, 'foo'), (25, 'bar')],
118
[(24, 'foo'), (24, 'bar')],
119
[(23, 'foo'), (23, 'bar')],
120
[(22, 'foo'), (22, 'bar')],
121
[(21, 'foo'), (21, 'bar')],
122
[(20, 'foo'), (20, 'bar')],
123
[(19, 'foo'), (19, 'bar')],
124
[(18, 'foo'), (18, 'bar')],
125
[(17, 'foo'), (17, 'bar')],
126
[(16, 'foo'), (16, 'bar')],
127
[(15, 'foo'), (15, 'bar')],
128
[(14, 'foo'), (14, 'bar')],
129
[(13, 'foo'), (13, 'bar')],
130
[(12, 'foo'), (12, 'bar')],
131
[(11, 'foo'), (11, 'bar')],
132
[(10, 'foo'), (10, 'bar')],
133
[(9, 'foo'), (9, 'bar')],
134
[(8, 'foo'), (8, 'bar')],
135
[(7, 'foo'), (7, 'bar')],
136
[(6, 'foo'), (6, 'bar')],
137
[(5, 'foo'), (5, 'bar')],
138
[(4, 'foo'), (4, 'bar')],
139
[(3, 'foo'), (3, 'bar')],
140
[(2, 'foo'), (2, 'bar')],
141
[(1, 'foo'), (1, 'bar')],
142
[(0, 'foo'), (0, 'bar')],
145
def test_lookup_missing_key_after_all_others(self):
148
def missing_last_content(location_keys):
149
# returns +1 for all keys unless the byte offset is 'end' when it
151
calls.append(location_keys)
153
for location_key in location_keys:
154
if location_key[0] == end:
155
result.append((location_key, False))
157
result.append((location_key, +1))
159
# given a 0 length file, this should terminate with one call.
162
list(bisect_multi_bytes(missing_last_content, 0, ['foo', 'bar'])))
163
self.assertEqual([[(0, 'foo'), (0, 'bar')]], calls)
166
# given a 3 length file, this should make two calls - 1, 2.
168
list(bisect_multi_bytes(missing_last_content, 3, ['foo', 'bar'])))
170
[(1, 'foo'), (1, 'bar')],
171
[(2, 'foo'), (2, 'bar')],
175
# see the really-big lookup series in
176
# test_lookup_missing_key_before_all_others for details about this
179
list(bisect_multi_bytes(
180
missing_last_content,268435456 - 1 , ['foo', 'bar'])))
182
[(134217727, 'foo'), (134217727, 'bar')],
183
[(201326590, 'foo'), (201326590, 'bar')],
184
[(234881021, 'foo'), (234881021, 'bar')],
185
[(251658236, 'foo'), (251658236, 'bar')],
186
[(260046843, 'foo'), (260046843, 'bar')],
187
[(264241146, 'foo'), (264241146, 'bar')],
188
[(266338297, 'foo'), (266338297, 'bar')],
189
[(267386872, 'foo'), (267386872, 'bar')],
190
[(267911159, 'foo'), (267911159, 'bar')],
191
[(268173302, 'foo'), (268173302, 'bar')],
192
[(268304373, 'foo'), (268304373, 'bar')],
193
[(268369908, 'foo'), (268369908, 'bar')],
194
[(268402675, 'foo'), (268402675, 'bar')],
195
[(268419058, 'foo'), (268419058, 'bar')],
196
[(268427249, 'foo'), (268427249, 'bar')],
197
[(268431344, 'foo'), (268431344, 'bar')],
198
[(268433391, 'foo'), (268433391, 'bar')],
199
[(268434414, 'foo'), (268434414, 'bar')],
200
[(268434925, 'foo'), (268434925, 'bar')],
201
[(268435180, 'foo'), (268435180, 'bar')],
202
[(268435307, 'foo'), (268435307, 'bar')],
203
[(268435370, 'foo'), (268435370, 'bar')],
204
[(268435401, 'foo'), (268435401, 'bar')],
205
[(268435416, 'foo'), (268435416, 'bar')],
206
[(268435423, 'foo'), (268435423, 'bar')],
207
[(268435426, 'foo'), (268435426, 'bar')],
208
[(268435427, 'foo'), (268435427, 'bar')],
209
[(268435428, 'foo'), (268435428, 'bar')],
210
[(268435429, 'foo'), (268435429, 'bar')],
211
[(268435430, 'foo'), (268435430, 'bar')],
212
[(268435431, 'foo'), (268435431, 'bar')],
213
[(268435432, 'foo'), (268435432, 'bar')],
214
[(268435433, 'foo'), (268435433, 'bar')],
215
[(268435434, 'foo'), (268435434, 'bar')],
216
[(268435435, 'foo'), (268435435, 'bar')],
217
[(268435436, 'foo'), (268435436, 'bar')],
218
[(268435437, 'foo'), (268435437, 'bar')],
219
[(268435438, 'foo'), (268435438, 'bar')],
220
[(268435439, 'foo'), (268435439, 'bar')],
221
[(268435440, 'foo'), (268435440, 'bar')],
222
[(268435441, 'foo'), (268435441, 'bar')],
223
[(268435442, 'foo'), (268435442, 'bar')],
224
[(268435443, 'foo'), (268435443, 'bar')],
225
[(268435444, 'foo'), (268435444, 'bar')],
226
[(268435445, 'foo'), (268435445, 'bar')],
227
[(268435446, 'foo'), (268435446, 'bar')],
228
[(268435447, 'foo'), (268435447, 'bar')],
229
[(268435448, 'foo'), (268435448, 'bar')],
230
[(268435449, 'foo'), (268435449, 'bar')],
231
[(268435450, 'foo'), (268435450, 'bar')],
232
[(268435451, 'foo'), (268435451, 'bar')],
233
[(268435452, 'foo'), (268435452, 'bar')],
234
[(268435453, 'foo'), (268435453, 'bar')],
235
[(268435454, 'foo'), (268435454, 'bar')]
238
def test_lookup_when_a_key_is_missing_continues(self):
240
def missing_foo_otherwise_missing_first_content(location_keys):
241
# returns -1 for all keys unless the byte offset is 0 when it
243
calls.append(location_keys)
245
for location_key in location_keys:
246
if location_key[1] == 'foo' or location_key[0] == 0:
247
result.append((location_key, False))
249
result.append((location_key, -1))
251
# given a 2 length file, this should terminate with two calls, one for
252
# both keys, and one for bar only.
254
list(bisect_multi_bytes(
255
missing_foo_otherwise_missing_first_content, 2,
258
[(1, 'foo'), (1, 'bar')],
262
def test_found_keys_returned_other_searches_continue(self):
264
def find_bar_at_1_foo_missing_at_0(location_keys):
265
calls.append(location_keys)
267
for location_key in location_keys:
268
if location_key == (1, 'bar'):
269
result.append((location_key, 'bar-result'))
270
elif location_key[0] == 0:
271
result.append((location_key, False))
273
result.append((location_key, -1))
275
# given a 4 length file, this should terminate with three calls, two for
276
# both keys, and one for foo only.
277
self.assertEqual([('bar', 'bar-result')],
278
list(bisect_multi_bytes(
279
find_bar_at_1_foo_missing_at_0, 4,
282
[(2, 'foo'), (2, 'bar')],
283
[(1, 'foo'), (1, 'bar')],
287
def test_searches_different_keys_in_different_directions(self):
289
def missing_bar_at_1_foo_at_3(location_keys):
290
calls.append(location_keys)
292
for location_key in location_keys:
293
if location_key[1] == 'bar':
294
if location_key[0] == 1:
295
result.append((location_key, False))
298
result.append((location_key, -1))
299
elif location_key[1] == 'foo':
300
if location_key[0] == 3:
301
result.append((location_key, False))
304
result.append((location_key, +1))
306
# given a 4 length file, this should terminate with two calls.
308
list(bisect_multi_bytes(
309
missing_bar_at_1_foo_at_3, 4,
312
[(2, 'foo'), (2, 'bar')],
313
[(3, 'foo'), (1, 'bar')],
316
def test_change_direction_in_single_key_search(self):
317
# check that we can search down, up, down again -
318
# so length 8, goes 4, 6, 5
320
def missing_at_5(location_keys):
321
calls.append(location_keys)
323
for location_key in location_keys:
324
if location_key[0] == 5:
325
result.append((location_key, False))
326
elif location_key[0] > 5:
328
result.append((location_key, -1))
331
result.append((location_key, +1))
333
# given a 8 length file, this should terminate with three calls.
335
list(bisect_multi_bytes(
339
[(4, 'foo'), (4, 'bar')],
340
[(6, 'foo'), (6, 'bar')],
341
[(5, 'foo'), (5, 'bar')],
added
removed
bzrlib/tests/test_bisect_multi.py
