]>
Commit | Line | Data |
---|---|---|
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) 2016 Red Hat | |
7 | * | |
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. | |
12 | * | |
13 | */ | |
14 | ||
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" | |
21 | ||
22 | using namespace std; | |
23 | ||
24 | template<typename T> | |
25 | class IntervalMapTest : public ::testing::Test { | |
26 | public: | |
27 | using TestType = T; | |
28 | }; | |
29 | ||
30 | template <typename _key> | |
31 | struct bufferlist_test_type { | |
32 | using key = _key; | |
33 | using value = bufferlist; | |
34 | ||
35 | struct make_splitter { | |
36 | template <typename merge_t> | |
37 | struct apply { | |
38 | bufferlist split( | |
39 | key offset, | |
40 | key len, | |
41 | bufferlist &bu) const { | |
42 | bufferlist bl; | |
43 | bl.substr_of(bu, offset, len); | |
44 | return bl; | |
45 | } | |
46 | bool can_merge(const bufferlist &left, const bufferlist &right) const { | |
47 | return merge_t::value; | |
48 | } | |
49 | bufferlist merge(bufferlist &&left, bufferlist &&right) const { | |
50 | bufferlist bl; | |
51 | left.claim_append(right); | |
9f95a23c | 52 | return std::move(left); |
7c673cae FG |
53 | } |
54 | uint64_t length(const bufferlist &r) const { | |
55 | return r.length(); | |
56 | } | |
57 | }; | |
58 | }; | |
59 | ||
60 | struct generate_random { | |
61 | bufferlist operator()(key len) { | |
62 | bufferlist bl; | |
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)); | |
67 | } | |
68 | return bl; | |
69 | } | |
70 | }; | |
71 | }; | |
72 | ||
73 | using IntervalMapTypes = ::testing::Types< bufferlist_test_type<uint64_t> >; | |
74 | ||
9f95a23c | 75 | TYPED_TEST_SUITE(IntervalMapTest, IntervalMapTypes); |
7c673cae FG |
76 | |
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, \ | |
83 | _can_merge>; \ | |
84 | using imap = interval_map<key, val, splitter>; (void)imap(); \ | |
85 | typename TT::generate_random gen; \ | |
86 | val v(gen(5)); \ | |
87 | splitter split; (void)split.split(0, 0, v); | |
88 | ||
89 | #define USING_NO_MERGE USING(std::false_type) | |
90 | #define USING_WITH_MERGE USING(std::true_type) | |
91 | ||
92 | TYPED_TEST(IntervalMapTest, empty) { | |
93 | USING_NO_MERGE; | |
94 | imap m; | |
95 | ASSERT_TRUE(m.empty()); | |
96 | } | |
97 | ||
98 | TYPED_TEST(IntervalMapTest, insert) { | |
99 | USING_NO_MERGE; | |
100 | imap m; | |
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); | |
106 | ||
107 | unsigned i = 0; | |
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]); | |
112 | ++i; | |
113 | } | |
114 | ASSERT_EQ(i, m.ext_count()); | |
115 | } | |
116 | ||
117 | TYPED_TEST(IntervalMapTest, insert_begin_overlap) { | |
118 | USING_NO_MERGE; | |
119 | imap m; | |
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]); | |
124 | ||
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]); | |
129 | ++iter; | |
130 | ||
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])); | |
134 | ++iter; | |
135 | ||
136 | ASSERT_EQ(iter.get_off(), 10u); | |
137 | ASSERT_EQ(iter.get_len(), 5u); | |
138 | ASSERT_EQ(iter.get_val(), vals[2]); | |
139 | ++iter; | |
140 | ||
141 | ASSERT_EQ(iter, m.end()); | |
142 | } | |
143 | ||
144 | TYPED_TEST(IntervalMapTest, insert_end_overlap) { | |
145 | USING_NO_MERGE; | |
146 | imap m; | |
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]); | |
151 | ||
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]); | |
156 | ++iter; | |
157 | ||
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])); | |
161 | ++iter; | |
162 | ||
163 | ASSERT_EQ(iter.get_off(), 8u); | |
164 | ASSERT_EQ(iter.get_len(), 5u); | |
165 | ASSERT_EQ(iter.get_val(), vals[2]); | |
166 | ++iter; | |
167 | ||
168 | ASSERT_EQ(iter, m.end()); | |
169 | } | |
170 | ||
171 | TYPED_TEST(IntervalMapTest, insert_middle_overlap) { | |
172 | USING_NO_MERGE; | |
173 | imap m; | |
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]); | |
178 | ||
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])); | |
183 | ++iter; | |
184 | ||
185 | ASSERT_EQ(iter.get_off(), 4u); | |
186 | ASSERT_EQ(iter.get_len(), 7u); | |
187 | ASSERT_EQ(iter.get_val(), vals[1]); | |
188 | ++iter; | |
189 | ||
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])); | |
193 | ++iter; | |
194 | ||
195 | ASSERT_EQ(iter, m.end()); | |
196 | } | |
197 | ||
198 | TYPED_TEST(IntervalMapTest, insert_single_exact_overlap) { | |
199 | USING_NO_MERGE; | |
200 | imap m; | |
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]); | |
206 | ||
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]); | |
211 | ++iter; | |
212 | ||
213 | ASSERT_EQ(iter.get_off(), 5u); | |
214 | ASSERT_EQ(iter.get_len(), 5u); | |
215 | ASSERT_EQ(iter.get_val(), vals[1]); | |
216 | ++iter; | |
217 | ||
218 | ASSERT_EQ(iter.get_off(), 10u); | |
219 | ASSERT_EQ(iter.get_len(), 5u); | |
220 | ASSERT_EQ(iter.get_val(), vals[2]); | |
221 | ++iter; | |
222 | ||
223 | ASSERT_EQ(iter, m.end()); | |
224 | } | |
225 | ||
226 | TYPED_TEST(IntervalMapTest, insert_single_exact_overlap_end) { | |
227 | USING_NO_MERGE; | |
228 | imap m; | |
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]); | |
234 | ||
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]); | |
239 | ++iter; | |
240 | ||
241 | ASSERT_EQ(iter.get_off(), 5u); | |
242 | ASSERT_EQ(iter.get_len(), 5u); | |
243 | ASSERT_EQ(iter.get_val(), vals[1]); | |
244 | ++iter; | |
245 | ||
246 | ASSERT_EQ(iter.get_off(), 10u); | |
247 | ASSERT_EQ(iter.get_len(), 5u); | |
248 | ASSERT_EQ(iter.get_val(), vals[2]); | |
249 | ++iter; | |
250 | ||
251 | ASSERT_EQ(iter, m.end()); | |
252 | } | |
253 | ||
254 | TYPED_TEST(IntervalMapTest, erase) { | |
255 | USING_NO_MERGE; | |
256 | imap m; | |
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]); | |
261 | ||
262 | m.erase(3, 5); | |
263 | ||
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])); | |
268 | ++iter; | |
269 | ||
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])); | |
273 | ++iter; | |
274 | ||
275 | ASSERT_EQ(iter.get_off(), 10u); | |
276 | ASSERT_EQ(iter.get_len(), 5u); | |
277 | ASSERT_EQ(iter.get_val(), vals[2]); | |
278 | ++iter; | |
279 | ||
280 | ASSERT_EQ(iter, m.end()); | |
281 | } | |
282 | ||
283 | TYPED_TEST(IntervalMapTest, erase_exact) { | |
284 | USING_NO_MERGE; | |
285 | imap m; | |
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]); | |
290 | ||
291 | m.erase(5, 5); | |
292 | ||
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]); | |
297 | ++iter; | |
298 | ||
299 | ASSERT_EQ(iter.get_off(), 10u); | |
300 | ASSERT_EQ(iter.get_len(), 5u); | |
301 | ASSERT_EQ(iter.get_val(), vals[2]); | |
302 | ++iter; | |
303 | ||
304 | ASSERT_EQ(iter, m.end()); | |
305 | } | |
306 | ||
307 | TYPED_TEST(IntervalMapTest, get_containing_range) { | |
308 | USING_NO_MERGE; | |
309 | imap m; | |
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]); | |
315 | ||
316 | auto rng = m.get_containing_range(5, 21); | |
317 | auto iter = rng.first; | |
318 | ||
319 | ASSERT_EQ(iter.get_off(), 10u); | |
320 | ASSERT_EQ(iter.get_len(), 5u); | |
321 | ASSERT_EQ(iter.get_val(), vals[1]); | |
322 | ++iter; | |
323 | ||
324 | ASSERT_EQ(iter.get_off(), 20u); | |
325 | ASSERT_EQ(iter.get_len(), 5u); | |
326 | ASSERT_EQ(iter.get_val(), vals[2]); | |
327 | ++iter; | |
328 | ||
329 | ASSERT_EQ(iter, rng.second); | |
330 | } | |
331 | ||
332 | TYPED_TEST(IntervalMapTest, merge) { | |
333 | USING_WITH_MERGE; | |
334 | imap m; | |
335 | m.insert(10, 4, gen(4)); | |
336 | m.insert(11, 1, gen(1)); | |
337 | } |