src/ceph/src/test/common/test_interval_map.cc

   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);
  52         return left;
  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
  75 TYPED_TEST_CASE(IntervalMapTest, IntervalMapTypes);
  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 }