ceph/src/boost/libs/histogram/test/unlimited_storage_test.cpp

   1 // Copyright 2015-2017 Hans Dembinski
   2 //
   3 // Distributed under the Boost Software License, Version 1.0.
   4 // (See accompanying file LICENSE_1_0.txt
   5 // or copy at http://www.boost.org/LICENSE_1_0.txt)
   6
   7 #include <algorithm>
   8 #include <boost/core/lightweight_test.hpp>
   9 #include <boost/core/lightweight_test_trait.hpp>
  10 #include <boost/histogram/detail/detect.hpp>
  11 #include <boost/histogram/storage_adaptor.hpp>
  12 #include <boost/histogram/unlimited_storage.hpp>
  13 #include <boost/histogram/unsafe_access.hpp>
  14 #include <boost/mp11.hpp>
  15 #include <iosfwd>
  16 #include <limits>
  17 #include <memory>
  18 #include <numeric>
  19 #include <vector>
  20 #include "std_ostream.hpp"
  21 #include "throw_exception.hpp"
  22 #include "utility_allocator.hpp"
  23
  24 namespace boost {
  25 namespace histogram {
  26 namespace detail {
  27 template <class Allocator>
  28 std::ostream& operator<<(std::ostream& os, const large_int<Allocator>& x) {
  29   os << "large_int";
  30   os << x.data;
  31   return os;
  32 }
  33 } // namespace detail
  34 } // namespace histogram
  35 } // namespace boost
  36
  37 using namespace boost::histogram;
  38
  39 using unlimited_storage_type = unlimited_storage<>;
  40 template <typename T>
  41 using vector_storage = storage_adaptor<std::vector<T>>;
  42 using large_int = unlimited_storage_type::large_int;
  43
  44 template <typename T = std::uint8_t>
  45 unlimited_storage_type prepare(std::size_t n, T x = T{}) {
  46   std::unique_ptr<T[]> v(new T[n]);
  47   std::fill(v.get(), v.get() + n, static_cast<T>(0));
  48   v.get()[0] = x;
  49   return unlimited_storage_type(n, v.get());
  50 }
  51
  52 template <class T>
  53 auto limits_max() {
  54   return (std::numeric_limits<T>::max)();
  55 }
  56
  57 template <>
  58 inline auto limits_max<large_int>() {
  59   return large_int(limits_max<uint64_t>());
  60 }
  61
  62 template <typename T>
  63 void copy() {
  64   const auto b = prepare<T>(1);
  65   auto a(b);
  66   BOOST_TEST(a == b);
  67   ++a[0];
  68   BOOST_TEST(!(a == b));
  69   a = b;
  70   BOOST_TEST(a == b);
  71   ++a[0];
  72   BOOST_TEST(!(a == b));
  73   a = prepare<T>(2);
  74   BOOST_TEST(!(a == b));
  75   a = b;
  76   BOOST_TEST(a == b);
  77 }
  78
  79 template <typename T>
  80 void equal_1() {
  81   auto a = prepare(1);
  82   auto b = prepare(1, T(0));
  83   BOOST_TEST_EQ(a[0], 0.0);
  84   BOOST_TEST(a == b);
  85   ++b[0];
  86   BOOST_TEST(!(a == b));
  87 }
  88
  89 template <typename T, typename U>
  90 void equal_2() {
  91   auto a = prepare<T>(1);
  92   vector_storage<U> b;
  93   b.reset(1);
  94   BOOST_TEST(a == b);
  95   ++b[0];
  96   BOOST_TEST(!(a == b));
  97 }
  98
  99 template <typename T>
 100 void increase_and_grow() {
 101   auto tmax = limits_max<T>();
 102   auto s = prepare(2, tmax);
 103   auto n = s;
 104   auto n2 = s;
 105
 106   ++n[0];
 107
 108   auto x = prepare(2);
 109   ++x[0];
 110   n2[0] += x[0];
 111
 112   auto v = static_cast<double>(tmax);
 113   ++v;
 114   BOOST_TEST_EQ(n[0], v);
 115   BOOST_TEST_EQ(n2[0], v);
 116   BOOST_TEST_EQ(n[1], 0.0);
 117   BOOST_TEST_EQ(n2[1], 0.0);
 118 }
 119
 120 template <typename T>
 121 void convert_foreign_storage() {
 122
 123   {
 124     vector_storage<T> s;
 125     s.reset(1);
 126     ++s[0];
 127     BOOST_TEST_EQ(s[0], 1);
 128
 129     // test converting copy ctor
 130     unlimited_storage_type u(s);
 131     using buffer_t = std::decay_t<decltype(unsafe_access::unlimited_storage_buffer(u))>;
 132     BOOST_TEST_EQ(unsafe_access::unlimited_storage_buffer(u).type,
 133                   buffer_t::template type_index<T>());
 134     BOOST_TEST(u == s);
 135     BOOST_TEST_EQ(u.size(), 1u);
 136     BOOST_TEST_EQ(u[0], 1.0);
 137     ++s[0];
 138     BOOST_TEST_NOT(u == s);
 139   }
 140
 141   vector_storage<uint8_t> s;
 142   s.reset(1);
 143   ++s[0];
 144
 145   // test assign and equal
 146   auto a = prepare<T>(1);
 147   a = s;
 148   BOOST_TEST_EQ(a[0], 1.0);
 149   BOOST_TEST(a == s);
 150   ++a[0];
 151   BOOST_TEST_NOT(a == s);
 152
 153   // test radd
 154   auto c = prepare<T>(1);
 155   c[0] += s[0];
 156   BOOST_TEST_EQ(c[0], 1);
 157   BOOST_TEST(c == s);
 158   c[0] += s[0];
 159   BOOST_TEST_EQ(c[0], 2);
 160   BOOST_TEST_NOT(c == s);
 161
 162   // test assign from float
 163   vector_storage<float> t;
 164   t.reset(1);
 165   t[0] = 1.5;
 166   auto d = prepare<T>(1);
 167   d = t;
 168   BOOST_TEST(d == t);
 169   BOOST_TEST(d[0] == 1.5);
 170
 171   // test "copy" ctor from float
 172   unlimited_storage_type f(t);
 173   BOOST_TEST_EQ(f[0], 1.5);
 174   BOOST_TEST(f == t);
 175
 176   // test radd from float
 177   auto g = prepare<T>(1);
 178   g[0] += t[0];
 179   BOOST_TEST_EQ(g[0], 1.5);
 180   BOOST_TEST(g == t);
 181
 182   vector_storage<int8_t> u;
 183   u.reset(1);
 184   u[0] = -10;
 185   auto h = prepare<T>(1);
 186   BOOST_TEST_NOT(h == u);
 187   h = u;
 188   BOOST_TEST(h == u);
 189   BOOST_TEST_EQ(h[0], -10);
 190   h[0] -= u[0];
 191   BOOST_TEST_EQ(h[0], 0);
 192 }
 193
 194 struct adder {
 195   template <class LHS, class RHS>
 196   void operator()(boost::mp11::mp_list<LHS, RHS>) {
 197     using buffer_type =
 198         std::remove_reference_t<decltype(unsafe_access::unlimited_storage_buffer(
 199             std::declval<unlimited_storage_type&>()))>;
 200     constexpr auto iLHS = buffer_type::template type_index<LHS>();
 201     constexpr auto iRHS = buffer_type::template type_index<RHS>();
 202     {
 203       auto a = prepare<LHS>(1);
 204       BOOST_TEST_EQ(unsafe_access::unlimited_storage_buffer(a).type, iLHS);
 205       a[0] += static_cast<RHS>(2);
 206       // LHS is never downgraded, only upgraded to RHS.
 207       // If RHS is normal integer, LHS doesn't change.
 208       BOOST_TEST_EQ(unsafe_access::unlimited_storage_buffer(a).type,
 209                     iRHS < 4 ? iLHS : (std::max)(iLHS, iRHS));
 210       BOOST_TEST_EQ(a[0], 2);
 211     }
 212     {
 213       auto a = prepare<LHS>(1);
 214       a[0] += 2;
 215       BOOST_TEST_EQ(a[0], 2);
 216       // subtracting converts to double
 217       a[0] -= 2;
 218       BOOST_TEST_EQ(unsafe_access::unlimited_storage_buffer(a).type, 5);
 219       BOOST_TEST_EQ(a[0], 0);
 220     }
 221     {
 222       auto a = prepare<LHS>(1);
 223       auto b = prepare<RHS>(1, static_cast<RHS>(2u));
 224       // LHS is never downgraded, only upgraded to RHS.
 225       // If RHS is normal integer, LHS doesn't change.
 226       a[0] += b[0];
 227       BOOST_TEST_EQ(unsafe_access::unlimited_storage_buffer(a).type,
 228                     iRHS < 4 ? iLHS : (std::max)(iLHS, iRHS));
 229       BOOST_TEST_EQ(a[0], 2);
 230       a[0] -= b[0];
 231       BOOST_TEST_EQ(a[0], 0);
 232       a[0] -= b[0];
 233       BOOST_TEST_EQ(a[0], -2);
 234     }
 235     {
 236       auto a = prepare<LHS>(1);
 237       auto b = limits_max<RHS>();
 238       // LHS is never downgraded, only upgraded to RHS.
 239       // If RHS is normal integer, LHS doesn't change.
 240       a[0] += b;
 241       // BOOST_TEST_EQ(unsafe_access::unlimited_storage_buffer(a).type,
 242       //               iRHS < 4 ? iLHS : std::max(iLHS, iRHS));
 243       BOOST_TEST_EQ(a[0], limits_max<RHS>());
 244       a[0] += prepare<RHS>(1, b)[0];
 245       // BOOST_TEST_EQ(unsafe_access::unlimited_storage_buffer(a).type,
 246       //               iRHS < 4 ? iLHS + 1 : std::max(iLHS, iRHS));
 247       BOOST_TEST_EQ(a[0], 2 * double(limits_max<RHS>()));
 248     }
 249   }
 250 };
 251
 252 int main() {
 253   // empty state
 254   {
 255     unlimited_storage_type a;
 256     BOOST_TEST_EQ(a.size(), 0);
 257   }
 258
 259   // copy
 260   {
 261     copy<uint8_t>();
 262     copy<uint16_t>();
 263     copy<uint32_t>();
 264     copy<uint64_t>();
 265     copy<large_int>();
 266     copy<double>();
 267   }
 268
 269   // equal_operator
 270   {
 271     equal_1<uint8_t>();
 272     equal_1<uint16_t>();
 273     equal_1<uint32_t>();
 274     equal_1<uint64_t>();
 275     equal_1<large_int>();
 276     equal_1<double>();
 277
 278     equal_2<uint8_t, unsigned>();
 279     equal_2<uint16_t, unsigned>();
 280     equal_2<uint32_t, unsigned>();
 281     equal_2<uint64_t, unsigned>();
 282     equal_2<large_int, unsigned>();
 283     equal_2<double, unsigned>();
 284
 285     equal_2<large_int, double>();
 286
 287     auto a = prepare<double>(1);
 288     auto b = prepare<large_int>(1);
 289     BOOST_TEST(a == b);
 290     ++a[0];
 291     BOOST_TEST_NOT(a == b);
 292   }
 293
 294   // increase_and_grow
 295   {
 296     increase_and_grow<uint8_t>();
 297     increase_and_grow<uint16_t>();
 298     increase_and_grow<uint32_t>();
 299     increase_and_grow<uint64_t>();
 300
 301     // only increase for large_int
 302     auto a = prepare<large_int>(2, static_cast<large_int>(1));
 303     BOOST_TEST_EQ(a[0], 1);
 304     BOOST_TEST_EQ(a[1], 0);
 305     ++a[0];
 306     BOOST_TEST_EQ(a[0], 2);
 307     BOOST_TEST_EQ(a[1], 0);
 308   }
 309
 310   // add
 311   {
 312     using namespace boost::mp11;
 313     using L = mp_list<uint8_t, uint16_t, uint64_t, large_int, double>;
 314     mp_for_each<mp_product<mp_list, L, L>>(adder());
 315   }
 316
 317   // add_and_grow
 318   {
 319     auto a = prepare(1);
 320     a[0] += a[0];
 321     BOOST_TEST_EQ(a[0], 0);
 322     ++a[0];
 323     double x = 1;
 324     auto b = prepare(1);
 325     ++b[0];
 326     BOOST_TEST_EQ(b[0], x);
 327     for (unsigned i = 0; i < 80; ++i) {
 328       x += x;
 329       a[0] += a[0];
 330       b[0] += b[0];
 331       BOOST_TEST_EQ(a[0], x);
 332       BOOST_TEST_EQ(b[0], x);
 333       auto c = prepare(1);
 334       c[0] += a[0];
 335       BOOST_TEST_EQ(c[0], x);
 336       c[0] += 0;
 337       BOOST_TEST_EQ(c[0], x);
 338       auto d = prepare(1);
 339       d[0] += x;
 340       BOOST_TEST_EQ(d[0], x);
 341     }
 342   }
 343
 344   // multiply
 345   {
 346     auto a = prepare(2);
 347     ++a[0];
 348     a *= 3;
 349     BOOST_TEST_EQ(a[0], 3);
 350     BOOST_TEST_EQ(a[1], 0);
 351     a[1] += 2;
 352     a *= 3;
 353     BOOST_TEST_EQ(a[0], 9);
 354     BOOST_TEST_EQ(a[1], 6);
 355   }
 356
 357   // convert_foreign_storage
 358   {
 359     convert_foreign_storage<uint8_t>();
 360     convert_foreign_storage<uint16_t>();
 361     convert_foreign_storage<uint32_t>();
 362     convert_foreign_storage<uint64_t>();
 363     convert_foreign_storage<large_int>();
 364     convert_foreign_storage<double>();
 365   }
 366
 367   // reference
 368   {
 369     auto a = prepare(1);
 370     auto b = prepare<uint32_t>(1);
 371     BOOST_TEST_EQ(a[0], b[0]);
 372     BOOST_TEST_GE(a[0], b[0]);
 373     BOOST_TEST_LE(a[0], b[0]);
 374     a[0] = 1;
 375     BOOST_TEST_NE(a[0], b[0]);
 376     BOOST_TEST_LT(b[0], a[0]);
 377     BOOST_TEST_GT(a[0], b[0]);
 378     BOOST_TEST_EQ(a[0], 1);
 379     BOOST_TEST_GE(a[0], 1);
 380     BOOST_TEST_LE(a[0], 1);
 381     BOOST_TEST_NE(a[0], 2);
 382     BOOST_TEST_GT(2, a[0]);
 383     BOOST_TEST_LT(0, a[0]);
 384     BOOST_TEST_GE(1, a[0]);
 385     BOOST_TEST_GE(2, a[0]);
 386     BOOST_TEST_LE(0, a[0]);
 387     BOOST_TEST_LE(1, a[0]);
 388     BOOST_TEST_EQ(1, a[0]);
 389     BOOST_TEST_NE(2, a[0]);
 390
 391     ++b[0];
 392     BOOST_TEST_EQ(a[0], b[0]);
 393     b[0] += 2;
 394     a[0] = b[0];
 395     BOOST_TEST_EQ(a[0], 3);
 396     a[0] -= 10;
 397     BOOST_TEST_EQ(a[0], -7);
 398     auto c = prepare(2);
 399     c[0] = c[1] = 1;
 400     BOOST_TEST_EQ(c[0], 1);
 401     BOOST_TEST_EQ(c[1], 1);
 402
 403     auto d = prepare(2);
 404     d[1] = unlimited_storage_type::large_int{2};
 405     BOOST_TEST_EQ(unsafe_access::unlimited_storage_buffer(d).type, 4);
 406     d[0] = -2;
 407     BOOST_TEST_EQ(unsafe_access::unlimited_storage_buffer(d).type, 5);
 408     BOOST_TEST_EQ(d[0], -2);
 409     BOOST_TEST_EQ(d[1], 2);
 410
 411     BOOST_TEST_TRAIT_TRUE((detail::has_operator_preincrement<decltype(d[0])>));
 412   }
 413
 414   // iterators
 415   {
 416     using iterator = typename unlimited_storage_type::iterator;
 417     using value_type = typename std::iterator_traits<iterator>::value_type;
 418     using reference = typename std::iterator_traits<iterator>::reference;
 419
 420     BOOST_TEST_TRAIT_SAME(value_type, double);
 421     BOOST_TEST_TRAIT_FALSE((std::is_same<reference, double&>));
 422
 423     auto a = prepare(2);
 424     for (auto&& x : a) BOOST_TEST_EQ(x, 0);
 425
 426     std::vector<double> b(2, 1);
 427     std::copy(b.begin(), b.end(), a.begin());
 428
 429     const auto& aconst = a;
 430     BOOST_TEST(std::equal(aconst.begin(), aconst.end(), b.begin(), b.end()));
 431
 432     unlimited_storage_type::iterator it1 = a.begin();
 433     BOOST_TEST_EQ(*it1, 1);
 434     *it1 = 3;
 435     BOOST_TEST_EQ(*it1, 3);
 436     unlimited_storage_type::const_iterator it2 = a.begin();
 437     BOOST_TEST_EQ(*it2, 3);
 438     unlimited_storage_type::const_iterator it3 = aconst.begin();
 439     BOOST_TEST_EQ(*it3, 3);
 440
 441     std::copy(b.begin(), b.end(), a.begin());
 442     std::partial_sum(a.begin(), a.end(), a.begin());
 443     BOOST_TEST_EQ(a[0], 1);
 444     BOOST_TEST_EQ(a[1], 2);
 445   }
 446
 447   // memory exhaustion
 448   {
 449     using S = unlimited_storage<tracing_allocator<char>>;
 450     using alloc_t = typename S::allocator_type;
 451     {
 452       // check that large_int allocates in ctor
 453       tracing_allocator_db db;
 454       typename S::large_int li{1, alloc_t{db}};
 455       BOOST_TEST_GT(db.first, 0);
 456     }
 457
 458     tracing_allocator_db db;
 459     // db.tracing = true; // uncomment this to monitor allocator activity
 460     S s(alloc_t{db});
 461     s.reset(10); // should work
 462     BOOST_TEST_EQ(db.at<uint8_t>().first, 10);
 463
 464 #ifndef BOOST_NO_EXCEPTIONS
 465     db.failure_countdown = 0;
 466     BOOST_TEST_THROWS(s.reset(5), std::bad_alloc);
 467     // storage must be still in valid state
 468     BOOST_TEST_EQ(s.size(), 0);
 469     auto& buffer = unsafe_access::unlimited_storage_buffer(s);
 470     BOOST_TEST_EQ(buffer.ptr, nullptr);
 471     BOOST_TEST_EQ(buffer.type, 0);
 472     // all allocated memory should have returned
 473     BOOST_TEST_EQ(db.first, 0);
 474
 475     // test failure in buffer.make<large_int>(n, iter), AT::construct
 476     s.reset(3);
 477     s[1] = (std::numeric_limits<std::uint64_t>::max)();
 478     db.failure_countdown = 2;
 479     const auto old_ptr = buffer.ptr;
 480     BOOST_TEST_THROWS(++s[1], std::bad_alloc);
 481
 482     // storage remains in previous state
 483     BOOST_TEST_EQ(buffer.size, 3);
 484     BOOST_TEST_EQ(buffer.ptr, old_ptr);
 485     BOOST_TEST_EQ(buffer.type, 3);
 486
 487     // test buffer.make<large_int>(n), AT::construct, called by serialization code
 488     db.failure_countdown = 1;
 489     BOOST_TEST_THROWS(buffer.make<typename S::large_int>(2), std::bad_alloc);
 490
 491     // storage still in valid state
 492     BOOST_TEST_EQ(s.size(), 0);
 493     BOOST_TEST_EQ(buffer.ptr, nullptr);
 494     BOOST_TEST_EQ(buffer.type, 0);
 495     // all memory returned
 496     BOOST_TEST_EQ(db.first, 0);
 497 #endif
 498   }
 499
 500   return boost::report_errors();
 501 }