[ceph.git] / ceph / src / test / common / test_interval_map.cc

// -*- mode:C++; tab-width:8; c-basic-offset:2; indent-tabs-mode:t -*-
// vim: ts=8 sw=2 smarttab
/*
 * Ceph - scalable distributed file system
 *
 * Copyright (C) 2016 Red Hat
 *
 * This is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Lesser General Public
 * License version 2.1, as published by the Free Software
 * Foundation.  See file COPYING.
 *
 */

#include <gtest/gtest.h>
#include <boost/random/mersenne_twister.hpp>
#include <boost/random/uniform_int_distribution.hpp>
#include <boost/mpl/apply.hpp>
#include "include/buffer.h"
#include "common/interval_map.h"

using namespace std;

template<typename T>
class IntervalMapTest : public ::testing::Test {
public:
  using TestType = T;
};

template <typename _key>
struct bufferlist_test_type {
  using key = _key;
  using value = bufferlist;

  struct make_splitter {
    template <typename merge_t>
    struct apply {
      bufferlist split(
	key offset,
	key len,
	bufferlist &bu) const {
	bufferlist bl;
	bl.substr_of(bu, offset, len);
	return bl;
      }
      bool can_merge(const bufferlist &left, const bufferlist &right) const {
	return merge_t::value;
      }
      bufferlist merge(bufferlist &&left, bufferlist &&right) const {
	bufferlist bl;
	left.claim_append(right);
	return std::move(left);
      }
      uint64_t length(const bufferlist &r) const {
	return r.length();
      }
    };
  };

  struct generate_random {
    bufferlist operator()(key len) {
      bufferlist bl;
      boost::random::mt19937 rng;
      boost::random::uniform_int_distribution<> chr(0,255);
      for (key i = 0; i < len; ++i) {
	bl.append((char)chr(rng));
      }
      return bl;
    }
  };
};

using IntervalMapTypes = ::testing::Types< bufferlist_test_type<uint64_t> >;

TYPED_TEST_SUITE(IntervalMapTest, IntervalMapTypes);

#define USING(_can_merge)					 \
  using TT = typename TestFixture::TestType;                     \
  using key = typename TT::key; (void)key(0);	                 \
  using val = typename TT::value; (void)val(0);			 \
  using splitter = typename boost::mpl::apply<                   \
    typename TT::make_splitter,                                  \
    _can_merge>;                                                 \
  using imap = interval_map<key, val, splitter>; (void)imap();	 \
  typename TT::generate_random gen;                              \
  val v(gen(5));	                                         \
  splitter split; (void)split.split(0, 0, v);

#define USING_NO_MERGE USING(std::false_type)
#define USING_WITH_MERGE USING(std::true_type)

TYPED_TEST(IntervalMapTest, empty) {
  USING_NO_MERGE;
  imap m;
  ASSERT_TRUE(m.empty());
}

TYPED_TEST(IntervalMapTest, insert) {
  USING_NO_MERGE;
  imap m;
  vector<val> vals{gen(5), gen(5), gen(5)};
  m.insert(0, 5, vals[0]);
  m.insert(10, 5, vals[2]);
  m.insert(5, 5, vals[1]);
  ASSERT_EQ(m.ext_count(), 3u);

  unsigned i = 0;
  for (auto &&ext: m) {
    ASSERT_EQ(ext.get_len(), 5u);
    ASSERT_EQ(ext.get_off(), 5u * i);
    ASSERT_EQ(ext.get_val(), vals[i]);
    ++i;
  }
  ASSERT_EQ(i, m.ext_count());
}

TYPED_TEST(IntervalMapTest, insert_begin_overlap) {
  USING_NO_MERGE;
  imap m;
  vector<val> vals{gen(5), gen(5), gen(5)};
  m.insert(5, 5, vals[1]);
  m.insert(10, 5, vals[2]);
  m.insert(1, 5, vals[0]);

  auto iter = m.begin();
  ASSERT_EQ(iter.get_off(), 1u);
  ASSERT_EQ(iter.get_len(), 5u);
  ASSERT_EQ(iter.get_val(), vals[0]);
  ++iter;

  ASSERT_EQ(iter.get_off(), 6u);
  ASSERT_EQ(iter.get_len(), 4u);
  ASSERT_EQ(iter.get_val(), split.split(1, 4, vals[1]));
  ++iter;

  ASSERT_EQ(iter.get_off(), 10u);
  ASSERT_EQ(iter.get_len(), 5u);
  ASSERT_EQ(iter.get_val(), vals[2]);
  ++iter;

  ASSERT_EQ(iter, m.end());
}

TYPED_TEST(IntervalMapTest, insert_end_overlap) {
  USING_NO_MERGE;
  imap m;
  vector<val> vals{gen(5), gen(5), gen(5)};
  m.insert(0, 5, vals[0]);
  m.insert(5, 5, vals[1]);
  m.insert(8, 5, vals[2]);

  auto iter = m.begin();
  ASSERT_EQ(iter.get_off(), 0u);
  ASSERT_EQ(iter.get_len(), 5u);
  ASSERT_EQ(iter.get_val(), vals[0]);
  ++iter;

  ASSERT_EQ(iter.get_off(), 5u);
  ASSERT_EQ(iter.get_len(), 3u);
  ASSERT_EQ(iter.get_val(), split.split(0, 3, vals[1]));
  ++iter;

  ASSERT_EQ(iter.get_off(), 8u);
  ASSERT_EQ(iter.get_len(), 5u);
  ASSERT_EQ(iter.get_val(), vals[2]);
  ++iter;

  ASSERT_EQ(iter, m.end());
}

TYPED_TEST(IntervalMapTest, insert_middle_overlap) {
  USING_NO_MERGE;
  imap m;
  vector<val> vals{gen(5), gen(7), gen(5)};
  m.insert(0, 5, vals[0]);
  m.insert(10, 5, vals[2]);
  m.insert(4, 7, vals[1]);

  auto iter = m.begin();
  ASSERT_EQ(iter.get_off(), 0u);
  ASSERT_EQ(iter.get_len(), 4u);
  ASSERT_EQ(iter.get_val(), split.split(0, 4, vals[0]));
  ++iter;

  ASSERT_EQ(iter.get_off(), 4u);
  ASSERT_EQ(iter.get_len(), 7u);
  ASSERT_EQ(iter.get_val(), vals[1]);
  ++iter;

  ASSERT_EQ(iter.get_off(), 11u);
  ASSERT_EQ(iter.get_len(), 4u);
  ASSERT_EQ(iter.get_val(), split.split(1, 4, vals[2]));
  ++iter;

  ASSERT_EQ(iter, m.end());
}

TYPED_TEST(IntervalMapTest, insert_single_exact_overlap) {
  USING_NO_MERGE;
  imap m;
  vector<val> vals{gen(5), gen(5), gen(5)};
  m.insert(0, 5, gen(5));
  m.insert(5, 5, vals[1]);
  m.insert(10, 5, vals[2]);
  m.insert(0, 5, vals[0]);

  auto iter = m.begin();
  ASSERT_EQ(iter.get_off(), 0u);
  ASSERT_EQ(iter.get_len(), 5u);
  ASSERT_EQ(iter.get_val(), vals[0]);
  ++iter;

  ASSERT_EQ(iter.get_off(), 5u);
  ASSERT_EQ(iter.get_len(), 5u);
  ASSERT_EQ(iter.get_val(), vals[1]);
  ++iter;

  ASSERT_EQ(iter.get_off(), 10u);
  ASSERT_EQ(iter.get_len(), 5u);
  ASSERT_EQ(iter.get_val(), vals[2]);
  ++iter;

  ASSERT_EQ(iter, m.end());
}

TYPED_TEST(IntervalMapTest, insert_single_exact_overlap_end) {
  USING_NO_MERGE;
  imap m;
  vector<val> vals{gen(5), gen(5), gen(5)};
  m.insert(0, 5, vals[0]);
  m.insert(5, 5, vals[1]);
  m.insert(10, 5, gen(5));
  m.insert(10, 5, vals[2]);

  auto iter = m.begin();
  ASSERT_EQ(iter.get_off(), 0u);
  ASSERT_EQ(iter.get_len(), 5u);
  ASSERT_EQ(iter.get_val(), vals[0]);
  ++iter;

  ASSERT_EQ(iter.get_off(), 5u);
  ASSERT_EQ(iter.get_len(), 5u);
  ASSERT_EQ(iter.get_val(), vals[1]);
  ++iter;

  ASSERT_EQ(iter.get_off(), 10u);
  ASSERT_EQ(iter.get_len(), 5u);
  ASSERT_EQ(iter.get_val(), vals[2]);
  ++iter;

  ASSERT_EQ(iter, m.end());
}

TYPED_TEST(IntervalMapTest, erase) {
  USING_NO_MERGE;
  imap m;
  vector<val> vals{gen(5), gen(5), gen(5)};
  m.insert(0, 5, vals[0]);
  m.insert(5, 5, vals[1]);
  m.insert(10, 5, vals[2]);

  m.erase(3, 5);

  auto iter = m.begin();
  ASSERT_EQ(iter.get_off(), 0u);
  ASSERT_EQ(iter.get_len(), 3u);
  ASSERT_EQ(iter.get_val(), split.split(0, 3, vals[0]));
  ++iter;

  ASSERT_EQ(iter.get_off(), 8u);
  ASSERT_EQ(iter.get_len(), 2u);
  ASSERT_EQ(iter.get_val(), split.split(3, 2, vals[1]));
  ++iter;

  ASSERT_EQ(iter.get_off(), 10u);
  ASSERT_EQ(iter.get_len(), 5u);
  ASSERT_EQ(iter.get_val(), vals[2]);
  ++iter;

  ASSERT_EQ(iter, m.end());
}

TYPED_TEST(IntervalMapTest, erase_exact) {
  USING_NO_MERGE;
  imap m;
  vector<val> vals{gen(5), gen(5), gen(5)};
  m.insert(0, 5, vals[0]);
  m.insert(5, 5, vals[1]);
  m.insert(10, 5, vals[2]);

  m.erase(5, 5);

  auto iter = m.begin();
  ASSERT_EQ(iter.get_off(), 0u);
  ASSERT_EQ(iter.get_len(), 5u);
  ASSERT_EQ(iter.get_val(), vals[0]);
  ++iter;

  ASSERT_EQ(iter.get_off(), 10u);
  ASSERT_EQ(iter.get_len(), 5u);
  ASSERT_EQ(iter.get_val(), vals[2]);
  ++iter;

  ASSERT_EQ(iter, m.end());
}

TYPED_TEST(IntervalMapTest, get_containing_range) {
  USING_NO_MERGE;
  imap m;
  vector<val> vals{gen(5), gen(5), gen(5), gen(5)};
  m.insert(0, 5, vals[0]);
  m.insert(10, 5, vals[1]);
  m.insert(20, 5, vals[2]);
  m.insert(30, 5, vals[3]);

  auto rng = m.get_containing_range(5, 21);
  auto iter = rng.first;

  ASSERT_EQ(iter.get_off(), 10u);
  ASSERT_EQ(iter.get_len(), 5u);
  ASSERT_EQ(iter.get_val(), vals[1]);
  ++iter;

  ASSERT_EQ(iter.get_off(), 20u);
  ASSERT_EQ(iter.get_len(), 5u);
  ASSERT_EQ(iter.get_val(), vals[2]);
  ++iter;

  ASSERT_EQ(iter, rng.second);
}

TYPED_TEST(IntervalMapTest, merge) {
  USING_WITH_MERGE;
  imap m;
  m.insert(10, 4, gen(4));
  m.insert(11, 1, gen(1));
}
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	}