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