1 // -*- mode:C++; tab-width:8; c-basic-offset:2; indent-tabs-mode:t -*-
2 // vim: ts=8 sw=2 smarttab
4 * Ceph - scalable distributed file system
6 * Copyright (C) 2016 Red Hat
8 * This is free software; you can redistribute it and/or
9 * modify it under the terms of the GNU Lesser General Public
10 * License version 2.1, as published by the Free Software
11 * Foundation. See file COPYING.
15 #include <gtest/gtest.h>
16 #include <boost/random/mersenne_twister.hpp>
17 #include <boost/random/uniform_int_distribution.hpp>
18 #include <boost/mpl/apply.hpp>
19 #include "include/buffer.h"
20 #include "common/interval_map.h"
25 class IntervalMapTest
: public ::testing::Test
{
30 template <typename _key
>
31 struct bufferlist_test_type
{
33 using value
= bufferlist
;
35 struct make_splitter
{
36 template <typename merge_t
>
41 bufferlist
&bu
) const {
43 bl
.substr_of(bu
, offset
, len
);
46 bool can_merge(const bufferlist
&left
, const bufferlist
&right
) const {
47 return merge_t::value
;
49 bufferlist
merge(bufferlist
&&left
, bufferlist
&&right
) const {
51 left
.claim_append(right
);
52 return std::move(left
);
54 uint64_t length(const bufferlist
&r
) const {
60 struct generate_random
{
61 bufferlist
operator()(key len
) {
63 boost::random::mt19937 rng
;
64 boost::random::uniform_int_distribution
<> chr(0,255);
65 for (key i
= 0; i
< len
; ++i
) {
66 bl
.append((char)chr(rng
));
73 using IntervalMapTypes
= ::testing::Types
< bufferlist_test_type
<uint64_t> >;
75 TYPED_TEST_SUITE(IntervalMapTest
, IntervalMapTypes
);
77 #define USING(_can_merge) \
78 using TT = typename TestFixture::TestType; \
79 using key = typename TT::key; (void)key(0); \
80 using val = typename TT::value; (void)val(0); \
81 using splitter = typename boost::mpl::apply< \
82 typename TT::make_splitter, \
84 using imap = interval_map<key, val, splitter>; (void)imap(); \
85 typename TT::generate_random gen; \
87 splitter split; (void)split.split(0, 0, v);
89 #define USING_NO_MERGE USING(std::false_type)
90 #define USING_WITH_MERGE USING(std::true_type)
92 TYPED_TEST(IntervalMapTest
, empty
) {
95 ASSERT_TRUE(m
.empty());
98 TYPED_TEST(IntervalMapTest
, insert
) {
101 vector
<val
> vals
{gen(5), gen(5), gen(5)};
102 m
.insert(0, 5, vals
[0]);
103 m
.insert(10, 5, vals
[2]);
104 m
.insert(5, 5, vals
[1]);
105 ASSERT_EQ(m
.ext_count(), 3u);
108 for (auto &&ext
: m
) {
109 ASSERT_EQ(ext
.get_len(), 5u);
110 ASSERT_EQ(ext
.get_off(), 5u * i
);
111 ASSERT_EQ(ext
.get_val(), vals
[i
]);
114 ASSERT_EQ(i
, m
.ext_count());
117 TYPED_TEST(IntervalMapTest
, insert_begin_overlap
) {
120 vector
<val
> vals
{gen(5), gen(5), gen(5)};
121 m
.insert(5, 5, vals
[1]);
122 m
.insert(10, 5, vals
[2]);
123 m
.insert(1, 5, vals
[0]);
125 auto iter
= m
.begin();
126 ASSERT_EQ(iter
.get_off(), 1u);
127 ASSERT_EQ(iter
.get_len(), 5u);
128 ASSERT_EQ(iter
.get_val(), vals
[0]);
131 ASSERT_EQ(iter
.get_off(), 6u);
132 ASSERT_EQ(iter
.get_len(), 4u);
133 ASSERT_EQ(iter
.get_val(), split
.split(1, 4, vals
[1]));
136 ASSERT_EQ(iter
.get_off(), 10u);
137 ASSERT_EQ(iter
.get_len(), 5u);
138 ASSERT_EQ(iter
.get_val(), vals
[2]);
141 ASSERT_EQ(iter
, m
.end());
144 TYPED_TEST(IntervalMapTest
, insert_end_overlap
) {
147 vector
<val
> vals
{gen(5), gen(5), gen(5)};
148 m
.insert(0, 5, vals
[0]);
149 m
.insert(5, 5, vals
[1]);
150 m
.insert(8, 5, vals
[2]);
152 auto iter
= m
.begin();
153 ASSERT_EQ(iter
.get_off(), 0u);
154 ASSERT_EQ(iter
.get_len(), 5u);
155 ASSERT_EQ(iter
.get_val(), vals
[0]);
158 ASSERT_EQ(iter
.get_off(), 5u);
159 ASSERT_EQ(iter
.get_len(), 3u);
160 ASSERT_EQ(iter
.get_val(), split
.split(0, 3, vals
[1]));
163 ASSERT_EQ(iter
.get_off(), 8u);
164 ASSERT_EQ(iter
.get_len(), 5u);
165 ASSERT_EQ(iter
.get_val(), vals
[2]);
168 ASSERT_EQ(iter
, m
.end());
171 TYPED_TEST(IntervalMapTest
, insert_middle_overlap
) {
174 vector
<val
> vals
{gen(5), gen(7), gen(5)};
175 m
.insert(0, 5, vals
[0]);
176 m
.insert(10, 5, vals
[2]);
177 m
.insert(4, 7, vals
[1]);
179 auto iter
= m
.begin();
180 ASSERT_EQ(iter
.get_off(), 0u);
181 ASSERT_EQ(iter
.get_len(), 4u);
182 ASSERT_EQ(iter
.get_val(), split
.split(0, 4, vals
[0]));
185 ASSERT_EQ(iter
.get_off(), 4u);
186 ASSERT_EQ(iter
.get_len(), 7u);
187 ASSERT_EQ(iter
.get_val(), vals
[1]);
190 ASSERT_EQ(iter
.get_off(), 11u);
191 ASSERT_EQ(iter
.get_len(), 4u);
192 ASSERT_EQ(iter
.get_val(), split
.split(1, 4, vals
[2]));
195 ASSERT_EQ(iter
, m
.end());
198 TYPED_TEST(IntervalMapTest
, insert_single_exact_overlap
) {
201 vector
<val
> vals
{gen(5), gen(5), gen(5)};
202 m
.insert(0, 5, gen(5));
203 m
.insert(5, 5, vals
[1]);
204 m
.insert(10, 5, vals
[2]);
205 m
.insert(0, 5, vals
[0]);
207 auto iter
= m
.begin();
208 ASSERT_EQ(iter
.get_off(), 0u);
209 ASSERT_EQ(iter
.get_len(), 5u);
210 ASSERT_EQ(iter
.get_val(), vals
[0]);
213 ASSERT_EQ(iter
.get_off(), 5u);
214 ASSERT_EQ(iter
.get_len(), 5u);
215 ASSERT_EQ(iter
.get_val(), vals
[1]);
218 ASSERT_EQ(iter
.get_off(), 10u);
219 ASSERT_EQ(iter
.get_len(), 5u);
220 ASSERT_EQ(iter
.get_val(), vals
[2]);
223 ASSERT_EQ(iter
, m
.end());
226 TYPED_TEST(IntervalMapTest
, insert_single_exact_overlap_end
) {
229 vector
<val
> vals
{gen(5), gen(5), gen(5)};
230 m
.insert(0, 5, vals
[0]);
231 m
.insert(5, 5, vals
[1]);
232 m
.insert(10, 5, gen(5));
233 m
.insert(10, 5, vals
[2]);
235 auto iter
= m
.begin();
236 ASSERT_EQ(iter
.get_off(), 0u);
237 ASSERT_EQ(iter
.get_len(), 5u);
238 ASSERT_EQ(iter
.get_val(), vals
[0]);
241 ASSERT_EQ(iter
.get_off(), 5u);
242 ASSERT_EQ(iter
.get_len(), 5u);
243 ASSERT_EQ(iter
.get_val(), vals
[1]);
246 ASSERT_EQ(iter
.get_off(), 10u);
247 ASSERT_EQ(iter
.get_len(), 5u);
248 ASSERT_EQ(iter
.get_val(), vals
[2]);
251 ASSERT_EQ(iter
, m
.end());
254 TYPED_TEST(IntervalMapTest
, erase
) {
257 vector
<val
> vals
{gen(5), gen(5), gen(5)};
258 m
.insert(0, 5, vals
[0]);
259 m
.insert(5, 5, vals
[1]);
260 m
.insert(10, 5, vals
[2]);
264 auto iter
= m
.begin();
265 ASSERT_EQ(iter
.get_off(), 0u);
266 ASSERT_EQ(iter
.get_len(), 3u);
267 ASSERT_EQ(iter
.get_val(), split
.split(0, 3, vals
[0]));
270 ASSERT_EQ(iter
.get_off(), 8u);
271 ASSERT_EQ(iter
.get_len(), 2u);
272 ASSERT_EQ(iter
.get_val(), split
.split(3, 2, vals
[1]));
275 ASSERT_EQ(iter
.get_off(), 10u);
276 ASSERT_EQ(iter
.get_len(), 5u);
277 ASSERT_EQ(iter
.get_val(), vals
[2]);
280 ASSERT_EQ(iter
, m
.end());
283 TYPED_TEST(IntervalMapTest
, erase_exact
) {
286 vector
<val
> vals
{gen(5), gen(5), gen(5)};
287 m
.insert(0, 5, vals
[0]);
288 m
.insert(5, 5, vals
[1]);
289 m
.insert(10, 5, vals
[2]);
293 auto iter
= m
.begin();
294 ASSERT_EQ(iter
.get_off(), 0u);
295 ASSERT_EQ(iter
.get_len(), 5u);
296 ASSERT_EQ(iter
.get_val(), vals
[0]);
299 ASSERT_EQ(iter
.get_off(), 10u);
300 ASSERT_EQ(iter
.get_len(), 5u);
301 ASSERT_EQ(iter
.get_val(), vals
[2]);
304 ASSERT_EQ(iter
, m
.end());
307 TYPED_TEST(IntervalMapTest
, get_containing_range
) {
310 vector
<val
> vals
{gen(5), gen(5), gen(5), gen(5)};
311 m
.insert(0, 5, vals
[0]);
312 m
.insert(10, 5, vals
[1]);
313 m
.insert(20, 5, vals
[2]);
314 m
.insert(30, 5, vals
[3]);
316 auto rng
= m
.get_containing_range(5, 21);
317 auto iter
= rng
.first
;
319 ASSERT_EQ(iter
.get_off(), 10u);
320 ASSERT_EQ(iter
.get_len(), 5u);
321 ASSERT_EQ(iter
.get_val(), vals
[1]);
324 ASSERT_EQ(iter
.get_off(), 20u);
325 ASSERT_EQ(iter
.get_len(), 5u);
326 ASSERT_EQ(iter
.get_val(), vals
[2]);
329 ASSERT_EQ(iter
, rng
.second
);
332 TYPED_TEST(IntervalMapTest
, merge
) {
335 m
.insert(10, 4, gen(4));
336 m
.insert(11, 1, gen(1));