ceph/src/seastar/tests/unit/circular_buffer_fixed_capacity_test.cc

   1 /*
   2  * This file is open source software, licensed to you under the terms
   3  * of the Apache License, Version 2.0 (the "License").  See the NOTICE file
   4  * distributed with this work for additional information regarding copyright
   5  * ownership.  You may not use this file except in compliance with the License.
   6  *
   7  * You may obtain a copy of the License at
   8  *
   9  *   http://www.apache.org/licenses/LICENSE-2.0
  10  *
  11  * Unless required by applicable law or agreed to in writing,
  12  * software distributed under the License is distributed on an
  13  * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
  14  * KIND, either express or implied.  See the License for the
  15  * specific language governing permissions and limitations
  16  * under the License.
  17  */
  18 /*
  19  * Copyright (C) 2017 ScyllaDB Ltd.
  20  */
  21
  22
  23 #define BOOST_TEST_MODULE core
  24
  25 #include <boost/test/included/unit_test.hpp>
  26 #include <deque>
  27 #include <random>
  28 #include <seastar/core/circular_buffer_fixed_capacity.hh>
  29
  30 #include <boost/range/algorithm/sort.hpp>
  31 #include <boost/range/algorithm/equal.hpp>
  32 #include <boost/range/algorithm/reverse.hpp>
  33
  34 using namespace seastar;
  35
  36 using cb16_t = circular_buffer_fixed_capacity<int, 16>;
  37
  38
  39 BOOST_AUTO_TEST_CASE(test_edge_cases) {
  40     cb16_t cb;
  41     BOOST_REQUIRE(cb.begin() == cb.end());
  42     cb.push_front(3);  // underflows indexes
  43     BOOST_REQUIRE_EQUAL(cb[0], 3);
  44     BOOST_REQUIRE(cb.begin() < cb.end());
  45     cb.push_back(4);
  46     BOOST_REQUIRE_EQUAL(cb.size(), 2u);
  47     BOOST_REQUIRE_EQUAL(cb[0], 3);
  48     BOOST_REQUIRE_EQUAL(cb[1], 4);
  49     cb.pop_back();
  50     BOOST_REQUIRE_EQUAL(cb.back(), 3);
  51     cb.push_front(1);
  52     cb.pop_back();
  53     BOOST_REQUIRE_EQUAL(cb.back(), 1);
  54 }
  55
  56 using deque = std::deque<int>;
  57
  58 BOOST_AUTO_TEST_CASE(test_random_walk) {
  59     auto rand = std::default_random_engine();
  60     auto op_gen = std::uniform_int_distribution<unsigned>(0, 6);
  61     deque d;
  62     cb16_t c;
  63     for (auto i = 0; i != 1000000; ++i) {
  64         auto op = op_gen(rand);
  65         switch (op) {
  66         case 0:
  67             if (d.size() < 16) {
  68                 auto n = rand();
  69                 c.push_back(n);
  70                 d.push_back(n);
  71             }
  72             break;
  73         case 1:
  74             if (d.size() < 16) {
  75                 auto n = rand();
  76                 c.push_front(n);
  77                 d.push_front(n);
  78             }
  79             break;
  80         case 2:
  81             if (!d.empty()) {
  82                 auto n = d.back();
  83                 auto m = c.back();
  84                 BOOST_REQUIRE_EQUAL(n, m);
  85                 c.pop_back();
  86                 d.pop_back();
  87             }
  88             break;
  89         case 3:
  90             if (!d.empty()) {
  91                 auto n = d.front();
  92                 auto m = c.front();
  93                 BOOST_REQUIRE_EQUAL(n, m);
  94                 c.pop_front();
  95                 d.pop_front();
  96             }
  97             break;
  98         case 4:
  99             boost::sort(c);
 100             boost::sort(d);
 101             break;
 102         case 5:
 103             if (!d.empty()) {
 104                 auto u = std::uniform_int_distribution<size_t>(0, d.size() - 1);
 105                 auto idx = u(rand);
 106                 auto m = c[idx];
 107                 auto n = c[idx];
 108                 BOOST_REQUIRE_EQUAL(m, n);
 109             }
 110             break;
 111         case 6:
 112             c.clear();
 113             d.clear();
 114             break;
 115         case 7:
 116             boost::reverse(c);
 117             boost::reverse(d);
 118         default:
 119             abort();
 120         }
 121         BOOST_REQUIRE_EQUAL(c.size(), d.size());
 122         BOOST_REQUIRE(boost::equal(c, d));
 123     }
 124 }