]> git.proxmox.com Git - ceph.git/blame - ceph/src/test/common/test_interval_set.cc
projects / ceph.git / blame
? search:
summary | shortlog | log | commit | commitdiff | tree
blob | blame (incremental) | history | HEAD
update sources to v12.2.5
[ceph.git] / ceph / src / test / common / test_interval_set.cc
CommitLineData
7c673cae
FG		 1// -*- mode:C++; tab-width:8; c-basic-offset:2; indent-tabs-mode:t -*-
2// vim: ts=8 sw=2 smarttab
3/*
4 * Ceph - scalable distributed file system
5 *
6 * Copyright (C) 2015 Mirantis, Inc.
7 *
8 * Author: Igor Fedotov <ifedotov@mirantis.com>
9 *
10 * This is free software; you can redistribute it and/or
11 * modify it under the terms of the GNU Lesser General Public
12 * License version 2.1, as published by the Free Software
13 * Foundation. See file COPYING.
14 *
15 */
16
17#include <gtest/gtest.h>
94b18763 18#include <boost/container/flat_map.hpp>
7c673cae 19#include "include/interval_set.h"
94b18763 20#include "include/btree_map.h"
7c673cae
FG		 21
22using namespace ceph;
23
24typedef uint64_t IntervalValueType;
25
26template<typename T> // tuple<type to test on, test array size>
27class IntervalSetTest : public ::testing::Test {
28
29 public:
30 typedef T ISet;
31};
32
94b18763
FG		 33typedef ::testing::Types<
34 interval_set<IntervalValueType>,
35 interval_set<IntervalValueType,
36 btree::btree_map<IntervalValueType,IntervalValueType>>,
37 interval_set<IntervalValueType,
38 boost::container::flat_map<IntervalValueType,IntervalValueType>>
39 > IntervalSetTypes;
7c673cae
FG		 40
41TYPED_TEST_CASE(IntervalSetTest, IntervalSetTypes);
42
43TYPED_TEST(IntervalSetTest, compare) {
44 typedef typename TestFixture::ISet ISet;
45 ISet iset1, iset2;
46 ASSERT_TRUE(iset1 == iset1);
47 ASSERT_TRUE(iset1 == iset2);
48
49 iset1.insert(1);
50 ASSERT_FALSE(iset1 == iset2);
51
52 iset2.insert(1);
53 ASSERT_TRUE(iset1 == iset2);
54
55 iset1.insert(2, 3);
56 iset2.insert(2, 4);
57 ASSERT_FALSE(iset1 == iset2);
58
59 iset2.erase(2, 4);
60 iset2.erase(1);
61 iset2.insert(2, 3);
62 iset2.insert(1);
63 ASSERT_TRUE(iset1 == iset2);
64
65 iset1.insert(100, 10);
66 iset2.insert(100, 5);
67 ASSERT_FALSE(iset1 == iset2);
68 iset2.insert(105, 5);
69 ASSERT_TRUE(iset1 == iset2);
70
71 iset1.insert(200, 10);
72 iset2.insert(205, 5);
73 ASSERT_FALSE(iset1 == iset2);
74 iset2.insert(200, 1);
75 iset2.insert(202, 3);
76 ASSERT_FALSE(iset1 == iset2);
77 iset2.insert(201, 1);
78 ASSERT_TRUE(iset1 == iset2);
79
80 iset1.clear();
81 ASSERT_FALSE(iset1 == iset2);
82 iset2.clear();
83 ASSERT_TRUE(iset1 == iset2);
84}
85
86TYPED_TEST(IntervalSetTest, contains) {
87 typedef typename TestFixture::ISet ISet;
88 ISet iset1;
89 ASSERT_FALSE(iset1.contains( 1 ));
90 ASSERT_FALSE(iset1.contains( 0, 1 ));
91
92 iset1.insert(1);
93 ASSERT_TRUE(iset1.contains( 1 ));
94 ASSERT_FALSE(iset1.contains( 0 ));
95 ASSERT_FALSE(iset1.contains( 2 ));
96 ASSERT_FALSE(iset1.contains( 0, 1 ));
97 ASSERT_FALSE(iset1.contains( 0, 2 ));
98 ASSERT_TRUE(iset1.contains( 1, 1 ));
99 ASSERT_FALSE(iset1.contains( 1, 2 ));
100
101 iset1.insert(2, 3);
102 ASSERT_TRUE(iset1.contains( 1 ));
103 ASSERT_FALSE(iset1.contains( 0 ));
104 ASSERT_TRUE(iset1.contains( 2 ));
105 ASSERT_FALSE(iset1.contains( 0, 1 ));
106 ASSERT_FALSE(iset1.contains( 0, 2 ));
107 ASSERT_TRUE(iset1.contains( 1, 1 ));
108 ASSERT_TRUE(iset1.contains( 1, 2 ));
109 ASSERT_TRUE(iset1.contains( 1, 3 ));
110 ASSERT_TRUE(iset1.contains( 1, 4 ));
111 ASSERT_FALSE(iset1.contains( 1, 5 ));
112 ASSERT_TRUE(iset1.contains( 2, 1 ));
113 ASSERT_TRUE(iset1.contains( 2, 2 ));
114 ASSERT_TRUE(iset1.contains( 2, 3 ));
115 ASSERT_FALSE(iset1.contains( 2, 4 ));
116 ASSERT_TRUE(iset1.contains( 3, 2 ));
117 ASSERT_TRUE(iset1.contains( 4, 1 ));
118 ASSERT_FALSE(iset1.contains( 4, 2 ));
119
120 iset1.insert(10, 10);
121 ASSERT_TRUE(iset1.contains( 1, 4 ));
122 ASSERT_FALSE(iset1.contains( 1, 5 ));
123 ASSERT_TRUE(iset1.contains( 2, 2 ));
124 ASSERT_FALSE(iset1.contains( 2, 4 ));
125
126 ASSERT_FALSE(iset1.contains( 1, 10 ));
127 ASSERT_FALSE(iset1.contains( 9, 1 ));
128 ASSERT_FALSE(iset1.contains( 9 ));
129 ASSERT_FALSE(iset1.contains( 9, 11 ));
130 ASSERT_TRUE(iset1.contains( 10, 1 ));
131 ASSERT_TRUE(iset1.contains( 11, 9 ));
132 ASSERT_TRUE(iset1.contains( 11, 2 ));
133 ASSERT_TRUE(iset1.contains( 18, 2 ));
134 ASSERT_TRUE(iset1.contains( 18, 2 ));
135 ASSERT_TRUE(iset1.contains( 10 ));
136 ASSERT_TRUE(iset1.contains( 19 ));
137 ASSERT_FALSE(iset1.contains( 20 ));
138 ASSERT_FALSE(iset1.contains( 21 ));
139
140 ASSERT_FALSE(iset1.contains( 11, 11 ));
141 ASSERT_FALSE(iset1.contains( 18, 9 ));
142
143 iset1.clear();
144 ASSERT_FALSE(iset1.contains( 1 ));
145 ASSERT_FALSE(iset1.contains( 0 ));
146 ASSERT_FALSE(iset1.contains( 2 ));
147 ASSERT_FALSE(iset1.contains( 0, 1 ));
148 ASSERT_FALSE(iset1.contains( 0, 2 ));
149 ASSERT_FALSE(iset1.contains( 1, 1 ));
150 ASSERT_FALSE(iset1.contains( 10, 2 ));
151}
152
153TYPED_TEST(IntervalSetTest, intersects) {
154 typedef typename TestFixture::ISet ISet;
155 ISet iset1;
156 ASSERT_FALSE(iset1.intersects( 1, 1 ));
157 ASSERT_FALSE(iset1.intersects( 0, 1 ));
158 ASSERT_FALSE(iset1.intersects( 0, 10 ));
159
160 iset1.insert(1);
161 ASSERT_TRUE(iset1.intersects( 1, 1 ));
162 ASSERT_FALSE(iset1.intersects( 0, 1 ));
163 ASSERT_FALSE(iset1.intersects( 2, 1 ));
164 ASSERT_TRUE(iset1.intersects( 0, 2 ));
165 ASSERT_TRUE(iset1.intersects( 0, 20 ));
166 ASSERT_TRUE(iset1.intersects( 1, 2 ));
167 ASSERT_TRUE(iset1.intersects( 1, 20 ));
168
169 iset1.insert(2, 3);
170 ASSERT_FALSE(iset1.intersects( 0, 1 ));
171 ASSERT_TRUE(iset1.intersects( 0, 2 ));
172 ASSERT_TRUE(iset1.intersects( 0, 200 ));
173 ASSERT_TRUE(iset1.intersects( 1, 1 ));
174 ASSERT_TRUE(iset1.intersects( 1, 4 ));
175 ASSERT_TRUE(iset1.intersects( 1, 5 ));
176 ASSERT_TRUE(iset1.intersects( 2, 1 ));
177 ASSERT_TRUE(iset1.intersects( 2, 2 ));
178 ASSERT_TRUE(iset1.intersects( 2, 3 ));
179 ASSERT_TRUE(iset1.intersects( 2, 4 ));
180 ASSERT_TRUE(iset1.intersects( 3, 2 ));
181 ASSERT_TRUE(iset1.intersects( 4, 1 ));
182 ASSERT_TRUE(iset1.intersects( 4, 2 ));
183 ASSERT_FALSE(iset1.intersects( 5, 2 ));
184
185 iset1.insert(10, 10);
186 ASSERT_TRUE(iset1.intersects( 1, 4 ));
187 ASSERT_TRUE(iset1.intersects( 1, 5 ));
188 ASSERT_TRUE(iset1.intersects( 1, 10 ));
189 ASSERT_TRUE(iset1.intersects( 2, 2 ));
190 ASSERT_TRUE(iset1.intersects( 2, 4 ));
191 ASSERT_FALSE(iset1.intersects( 5, 1 ));
192 ASSERT_FALSE(iset1.intersects( 5, 2 ));
193 ASSERT_FALSE(iset1.intersects( 5, 5 ));
194 ASSERT_TRUE(iset1.intersects( 5, 12 ));
195 ASSERT_TRUE(iset1.intersects( 5, 20 ));
196
197 ASSERT_FALSE(iset1.intersects( 9, 1 ));
198 ASSERT_TRUE(iset1.intersects( 9, 2 ));
199
200 ASSERT_TRUE(iset1.intersects( 9, 11 ));
201 ASSERT_TRUE(iset1.intersects( 10, 1 ));
202 ASSERT_TRUE(iset1.intersects( 11, 9 ));
203 ASSERT_TRUE(iset1.intersects( 11, 2 ));
204 ASSERT_TRUE(iset1.intersects( 11, 11 ));
205 ASSERT_TRUE(iset1.intersects( 18, 2 ));
206 ASSERT_TRUE(iset1.intersects( 18, 9 ));
207 ASSERT_FALSE(iset1.intersects( 20, 1 ));
208 ASSERT_FALSE(iset1.intersects( 21, 12 ));
209
210 iset1.clear();
211 ASSERT_FALSE(iset1.intersects( 0, 1 ));
212 ASSERT_FALSE(iset1.intersects( 0, 2 ));
213 ASSERT_FALSE(iset1.intersects( 1, 1 ));
214 ASSERT_FALSE(iset1.intersects( 5, 2 ));
215 ASSERT_FALSE(iset1.intersects( 10, 2 ));
216}
217
218TYPED_TEST(IntervalSetTest, insert_erase) {
219 typedef typename TestFixture::ISet ISet;
220 ISet iset1, iset2;
221 IntervalValueType start, len;
222
223 iset1.insert(3, 5, &start, &len);
224 ASSERT_TRUE( start == 3 );
225 ASSERT_TRUE( len == 5 );
226 ASSERT_TRUE( iset1.num_intervals() == 1 );
227 ASSERT_TRUE( iset1.size() == 5 );
228
229 //adding standalone interval
230 iset1.insert(15, 10, &start, &len);
231 ASSERT_TRUE( start == 15 );
232 ASSERT_TRUE( len == 10 );
233 ASSERT_TRUE( iset1.num_intervals() == 2 );
234 ASSERT_EQ( iset1.size(), 15 );
235
236 //adding leftmost standalone interval
237 iset1.insert(1, 1, &start, &len);
238 ASSERT_TRUE( start == 1 );
239 ASSERT_TRUE( len == 1 );
240 ASSERT_TRUE( iset1.num_intervals() == 3 );
241 ASSERT_EQ( iset1.size(), 16 );
242
243 //adding leftmost adjusent interval
244 iset1.insert(0, 1, &start, &len);
245 ASSERT_TRUE( start == 0 );
246 ASSERT_TRUE( len == 2 );
247 ASSERT_TRUE( iset1.num_intervals() == 3 );
248 ASSERT_EQ( iset1.size(), 17 );
249
250 //adding interim interval that merges leftmost and subseqent intervals
251 iset1.insert(2, 1, &start, &len);
252 ASSERT_TRUE( start == 0 );
253 ASSERT_TRUE( len == 8 );
254 ASSERT_TRUE( iset1.num_intervals() == 2);
255 ASSERT_EQ( iset1.size(), 18);
256
257 //adding rigtmost standalone interval
258 iset1.insert(30, 5, &start, &len);
259 ASSERT_TRUE( start == 30 );
260 ASSERT_TRUE( len == 5 );
261 ASSERT_TRUE( iset1.num_intervals() == 3);
262 ASSERT_EQ( iset1.size(), 23 );
263
264 //adding rigtmost adjusent interval
265 iset1.insert(35, 10, &start, &len);
266 ASSERT_TRUE( start == 30 );
267 ASSERT_TRUE( len == 15 );
268 ASSERT_TRUE( iset1.num_intervals() == 3);
269 ASSERT_EQ( iset1.size(), 33 );
270
271 //adding interim interval that merges with the interval preceeding the rightmost
272 iset1.insert(25, 1, &start, &len);
273 ASSERT_TRUE( start == 15 );
274 ASSERT_TRUE( len == 11 );
275 ASSERT_TRUE( iset1.num_intervals() == 3);
276 ASSERT_EQ( iset1.size(), 34);
277
278 //adding interim interval that merges with the rightmost and preceeding intervals
279 iset1.insert(26, 4, &start, &len);
280 ASSERT_TRUE( start == 15 );
281 ASSERT_TRUE( len == 30 );
282 ASSERT_TRUE( iset1.num_intervals() == 2);
283 ASSERT_EQ( iset1.size(), 38);
284
285 //and finally build single interval filling the gap at 8-15 using different interval set
286 iset2.insert( 8, 1 );
287 iset2.insert( 14, 1 );
288 iset2.insert( 9, 4 );
289 iset1.insert( iset2 );
290 iset1.insert(13, 1, &start, &len);
291 ASSERT_TRUE( start == 0 );
292 ASSERT_TRUE( len == 45 );
293 ASSERT_TRUE( iset1.num_intervals() == 1);
294 ASSERT_EQ( iset1.size(), 45);
295
296 //now reverses the process using subtract & erase
297 iset1.subtract( iset2 );
298 iset1.erase(13, 1);
299 ASSERT_TRUE( iset1.num_intervals() == 2);
300 ASSERT_EQ( iset1.size(), 38);
301 ASSERT_TRUE( iset1.contains( 7, 1 ));
302 ASSERT_FALSE( iset1.contains( 8, 7 ));
303 ASSERT_TRUE( iset1.contains( 15, 1 ));
304 ASSERT_TRUE( iset1.contains( 26, 4 ));
305
306 iset1.erase(26, 4);
307 ASSERT_TRUE( iset1.num_intervals() == 3);
308 ASSERT_EQ( iset1.size(), 34);
309 ASSERT_TRUE( iset1.contains( 7, 1 ));
310 ASSERT_FALSE( iset1.intersects( 8, 7 ));
311 ASSERT_TRUE( iset1.contains( 15, 1 ));
312 ASSERT_TRUE( iset1.contains( 25, 1 ));
313 ASSERT_FALSE( iset1.contains( 26, 4 ));
314 ASSERT_TRUE( iset1.contains( 30, 1 ));
315
316 iset1.erase(25, 1);
317 ASSERT_TRUE( iset1.num_intervals() == 3);
318 ASSERT_EQ( iset1.size(), 33 );
319 ASSERT_TRUE( iset1.contains( 24, 1 ));
320 ASSERT_FALSE( iset1.contains( 25, 1 ));
321 ASSERT_FALSE( iset1.intersects( 26, 4 ));
322 ASSERT_TRUE( iset1.contains( 30, 1 ));
323 ASSERT_TRUE( iset1.contains( 35, 10 ));
324
325 iset1.erase(35, 10);
326 ASSERT_TRUE( iset1.num_intervals() == 3);
327 ASSERT_EQ( iset1.size(), 23 );
328 ASSERT_TRUE( iset1.contains( 30, 5 ));
329 ASSERT_TRUE( iset1.contains( 34, 1 ));
330 ASSERT_FALSE( iset1.contains( 35, 10 ));
331 ASSERT_FALSE(iset1.contains( 45, 1 ));
332
333 iset1.erase(30, 5);
334 ASSERT_TRUE( iset1.num_intervals() == 2);
335 ASSERT_EQ( iset1.size(), 18);
336 ASSERT_TRUE( iset1.contains( 2, 1 ));
337 ASSERT_TRUE( iset1.contains( 24, 1 ));
338 ASSERT_FALSE( iset1.contains( 25, 1 ));
339 ASSERT_FALSE( iset1.contains( 29, 1 ));
340 ASSERT_FALSE( iset1.contains( 30, 5 ));
341 ASSERT_FALSE( iset1.contains( 35, 1 ));
342
343 iset1.erase(2, 1);
344 ASSERT_TRUE( iset1.num_intervals() == 3 );
345 ASSERT_EQ( iset1.size(), 17 );
346 ASSERT_TRUE( iset1.contains( 0, 1 ));
347 ASSERT_TRUE( iset1.contains( 1, 1 ));
348 ASSERT_FALSE( iset1.contains( 2, 1 ));
349 ASSERT_TRUE( iset1.contains( 3, 1 ));
350 ASSERT_TRUE( iset1.contains( 15, 1 ));
351 ASSERT_FALSE( iset1.contains( 25, 1 ));
352
353 iset1.erase( 0, 1);
354 ASSERT_TRUE( iset1.num_intervals() == 3 );
355 ASSERT_EQ( iset1.size(), 16 );
356 ASSERT_FALSE( iset1.contains( 0, 1 ));
357 ASSERT_TRUE( iset1.contains( 1, 1 ));
358 ASSERT_FALSE( iset1.contains( 2, 1 ));
359 ASSERT_TRUE( iset1.contains( 3, 1 ));
360 ASSERT_TRUE( iset1.contains( 15, 1 ));
361
362 iset1.erase(1, 1);
363 ASSERT_TRUE( iset1.num_intervals() == 2 );
364 ASSERT_EQ( iset1.size(), 15 );
365 ASSERT_FALSE( iset1.contains( 1, 1 ));
366 ASSERT_TRUE( iset1.contains( 15, 10 ));
367 ASSERT_TRUE( iset1.contains( 3, 5 ));
368
369 iset1.erase(15, 10);
370 ASSERT_TRUE( iset1.num_intervals() == 1 );
371 ASSERT_TRUE( iset1.size() == 5 );
372 ASSERT_FALSE( iset1.contains( 1, 1 ));
373 ASSERT_FALSE( iset1.contains( 15, 10 ));
374 ASSERT_FALSE( iset1.contains( 25, 1 ));
375 ASSERT_TRUE( iset1.contains( 3, 5 ));
376
377 iset1.erase( 3, 1);
378 ASSERT_TRUE( iset1.num_intervals() == 1 );
379 ASSERT_TRUE( iset1.size() == 4 );
380 ASSERT_FALSE( iset1.contains( 1, 1 ));
381 ASSERT_FALSE( iset1.contains( 15, 10 ));
382 ASSERT_FALSE( iset1.contains( 25, 1 ));
383 ASSERT_TRUE( iset1.contains( 4, 4 ));
384 ASSERT_FALSE( iset1.contains( 3, 5 ));
385
386 iset1.erase( 4, 4);
387 ASSERT_TRUE( iset1.num_intervals() == 0);
388 ASSERT_TRUE( iset1.size() == 0);
389 ASSERT_FALSE( iset1.contains( 1, 1 ));
390 ASSERT_FALSE( iset1.contains( 15, 10 ));
391 ASSERT_FALSE( iset1.contains( 25, 1 ));
392 ASSERT_FALSE( iset1.contains( 3, 4 ));
393 ASSERT_FALSE( iset1.contains( 3, 5 ));
394 ASSERT_FALSE( iset1.contains( 4, 4 ));
395
396
397}
398
399TYPED_TEST(IntervalSetTest, intersect_of) {
400 typedef typename TestFixture::ISet ISet;
401 ISet iset1, iset2, iset3;
402
403 iset1.intersection_of( iset2, iset3 );
404 ASSERT_TRUE( iset1.num_intervals() == 0);
405 ASSERT_TRUE( iset1.size() == 0);
406
407 iset2.insert( 0, 1 );
408 iset2.insert( 5, 10 );
409 iset2.insert( 30, 10 );
410
411 iset3.insert( 0, 2 );
412 iset3.insert( 15, 1 );
413 iset3.insert( 20, 5 );
414 iset3.insert( 29, 3 );
415 iset3.insert( 35, 3 );
416 iset3.insert( 39, 3 );
417
418 iset1.intersection_of( iset2, iset3 );
419 ASSERT_TRUE( iset1.num_intervals() == 4);
420 ASSERT_TRUE( iset1.size() == 7);
421
422 ASSERT_TRUE( iset1.contains( 0, 1 ));
423 ASSERT_FALSE( iset1.contains( 0, 2 ));
424
425 ASSERT_FALSE( iset1.contains( 5, 11 ));
426 ASSERT_FALSE( iset1.contains( 4, 1 ));
427 ASSERT_FALSE( iset1.contains( 16, 1 ));
428
429 ASSERT_FALSE( iset1.contains( 20, 5 ));
430
431 ASSERT_FALSE( iset1.contains( 29, 1 ));
432 ASSERT_FALSE( iset1.contains( 30, 10 ));
433
434 ASSERT_TRUE( iset1.contains( 30, 2 ));
435 ASSERT_TRUE( iset1.contains( 35, 3 ));
436 ASSERT_FALSE( iset1.contains( 35, 4 ));
437
438 ASSERT_TRUE( iset1.contains( 39, 1 ));
439 ASSERT_FALSE( iset1.contains( 38, 2 ));
440 ASSERT_FALSE( iset1.contains( 39, 2 ));
441
442 iset3=iset1;
443 iset1.intersection_of(iset2);
444 ASSERT_TRUE( iset1 == iset3);
445
446 iset2.clear();
447 iset2.insert(0,1);
448 iset1.intersection_of(iset2);
449 ASSERT_TRUE( iset1.num_intervals() == 1);
450 ASSERT_TRUE( iset1.size() == 1);
451
452 iset1 = iset3;
453 iset2.clear();
454 iset1.intersection_of(iset2);
455 ASSERT_TRUE( iset1.num_intervals() == 0);
456 ASSERT_TRUE( iset1.size() == 0);
457
458}
459
460TYPED_TEST(IntervalSetTest, union_of) {
461 typedef typename TestFixture::ISet ISet;
462 ISet iset1, iset2, iset3;
463
464 iset1.union_of( iset2, iset3 );
465 ASSERT_TRUE( iset1.num_intervals() == 0);
466 ASSERT_TRUE( iset1.size() == 0);
467
468 iset2.insert( 0, 1 );
469 iset2.insert( 5, 10 );
470 iset2.insert( 30, 10 );
471
472 iset3.insert( 0, 2 );
473 iset3.insert( 15, 1 );
474 iset3.insert( 20, 5 );
475 iset3.insert( 29, 3 );
476 iset3.insert( 39, 3 );
477
478 iset1.union_of( iset2, iset3 );
479 ASSERT_TRUE( iset1.num_intervals() == 4);
480 ASSERT_EQ( iset1.size(), 31);
481 ASSERT_TRUE( iset1.contains( 0, 2 ));
482 ASSERT_FALSE( iset1.contains( 0, 3 ));
483
484 ASSERT_TRUE( iset1.contains( 5, 11 ));
485 ASSERT_FALSE( iset1.contains( 4, 1 ));
486 ASSERT_FALSE( iset1.contains( 16, 1 ));
487
488 ASSERT_TRUE( iset1.contains( 20, 5 ));
489
490 ASSERT_TRUE( iset1.contains( 30, 10 ));
491 ASSERT_TRUE( iset1.contains( 29, 13 ));
492 ASSERT_FALSE( iset1.contains( 29, 14 ));
493 ASSERT_FALSE( iset1.contains( 42, 1 ));
494
495 iset2.clear();
496 iset1.union_of(iset2);
497 ASSERT_TRUE( iset1.num_intervals() == 4);
498 ASSERT_EQ( iset1.size(), 31);
499
500 iset3.clear();
501 iset3.insert( 29, 3 );
502 iset3.insert( 39, 2 );
503 iset1.union_of(iset3);
504
505 ASSERT_TRUE( iset1.num_intervals() == 4);
506 ASSERT_EQ( iset1.size(), 31); //actually we added nothing
507 ASSERT_TRUE( iset1.contains( 29, 13 ));
508 ASSERT_FALSE( iset1.contains( 29, 14 ));
509 ASSERT_FALSE( iset1.contains( 42, 1 ));
510
511}
512
513TYPED_TEST(IntervalSetTest, subset_of) {
514 typedef typename TestFixture::ISet ISet;
515 ISet iset1, iset2;
516
517 ASSERT_TRUE(iset1.subset_of(iset2));
518
519 iset1.insert(5,10);
520 ASSERT_FALSE(iset1.subset_of(iset2));
521
522 iset2.insert(6,8);
523 ASSERT_FALSE(iset1.subset_of(iset2));
524
525 iset2.insert(5,1);
526 ASSERT_FALSE(iset1.subset_of(iset2));
527
528 iset2.insert(14,10);
529 ASSERT_TRUE(iset1.subset_of(iset2));
530
531 iset1.insert( 20, 4);
532 ASSERT_TRUE(iset1.subset_of(iset2));
533
534 iset1.insert( 24, 1);
535 ASSERT_FALSE(iset1.subset_of(iset2));
94b18763
FG		 536
537 iset2.insert( 24, 1);
538 ASSERT_TRUE(iset1.subset_of(iset2));
539
540 iset1.insert( 30, 5);
541 ASSERT_FALSE(iset1.subset_of(iset2));
542
543 iset2.insert( 30, 5);
544 ASSERT_TRUE(iset1.subset_of(iset2));
545
546 iset2.erase( 30, 1);
547 ASSERT_FALSE(iset1.subset_of(iset2));
548
549 iset1.erase( 30, 1);
550 ASSERT_TRUE(iset1.subset_of(iset2));
551
552 iset2.erase( 34, 1);
553 ASSERT_FALSE(iset1.subset_of(iset2));
554
555 iset1.erase( 34, 1);
556 ASSERT_TRUE(iset1.subset_of(iset2));
557
558 iset1.insert( 40, 5);
559 ASSERT_FALSE(iset1.subset_of(iset2));
560
561 iset2.insert( 39, 7);
562 ASSERT_TRUE(iset1.subset_of(iset2));
563
564 iset1.insert( 50, 5);
565 iset2.insert( 55, 2);
566 ASSERT_FALSE(iset1.subset_of(iset2));
567
568 ISet iset3, iset4, expected;
569 iset3.insert(5, 10);
570 iset3.insert(20, 5);
571
572 iset4.subset_of(iset3, 0, 100);
573 expected.insert(5, 10);
574 expected.insert(20, 5);
575 ASSERT_TRUE(iset4 == expected);
576
577 iset4.clear();
578 iset4.subset_of(iset3, 5, 25);
579 ASSERT_TRUE(iset4 == expected);
580
581 iset4.clear();
582 iset4.subset_of(iset3, 1, 10);
583 expected.clear();
584 expected.insert(5, 5);
585 ASSERT_TRUE(iset4 == expected);
586
587 iset4.clear();
588 iset4.subset_of(iset3, 8, 24);
589 expected.clear();
590 expected.insert(8, 7);
591 expected.insert(20, 4);
592 ASSERT_TRUE(iset4 == expected);
593
594 iset4.clear();
595 iset4.subset_of(iset3, 0, 0);
596 expected.clear();
597 ASSERT_TRUE(iset4 == expected);
598
599 iset4.clear();
600 iset4.subset_of(iset3, 0, 1);
601 ASSERT_TRUE(iset4 == expected);
602
603 iset4.clear();
604 iset4.subset_of(iset3, 0, 5);
605 ASSERT_TRUE(iset4 == expected);
606
607 iset4.clear();
608 iset4.subset_of(iset3, 25, 30);
609 ASSERT_TRUE(iset4 == expected);
610
611 iset4.clear();
612 iset4.subset_of(iset3, 26, 40);
613 ASSERT_TRUE(iset4 == expected);
7c673cae
FG		 614}
615
616TYPED_TEST(IntervalSetTest, span_of) {
617 typedef typename TestFixture::ISet ISet;
618 ISet iset1, iset2;
619
620 iset2.insert(5,5);
621 iset2.insert(20,5);
622
623 iset1.span_of( iset2, 8, 5 );
624 ASSERT_EQ( iset1.num_intervals(), 2);
625 ASSERT_EQ( iset1.size(), 5);
626 ASSERT_TRUE( iset1.contains( 8, 2 ));
627 ASSERT_TRUE( iset1.contains( 20, 3 ));
628
629 iset1.span_of( iset2, 3, 5 );
630 ASSERT_EQ( iset1.num_intervals(), 1);
631 ASSERT_EQ( iset1.size(), 5);
632 ASSERT_TRUE( iset1.contains( 5, 5 ));
633
634 iset1.span_of( iset2, 10, 7 );
635 ASSERT_EQ( iset1.num_intervals(), 1);
636 ASSERT_EQ( iset1.size(), 5);
637 ASSERT_TRUE( iset1.contains( 20, 5 ));
638 ASSERT_FALSE( iset1.contains( 20, 6 ));
639
640 iset1.span_of( iset2, 5, 10);
641 ASSERT_EQ( iset1.num_intervals(), 2);
642 ASSERT_EQ( iset1.size(), 10);
643 ASSERT_TRUE( iset1.contains( 5, 5 ));
644 ASSERT_TRUE( iset1.contains( 20, 5 ));
645
646 iset1.span_of( iset2, 100, 5 );
647 ASSERT_EQ( iset1.num_intervals(), 0);
648 ASSERT_EQ( iset1.size(), 0);
94b18763 649}
Ceph