Core/Utilities/MultiIndexTests.cpp

0001 // This file is part of the ACTS project.
0002 //
0003 // Copyright (C) 2016 CERN for the benefit of the ACTS project
0004 //
0005 // This Source Code Form is subject to the terms of the Mozilla Public
0006 // License, v. 2.0. If a copy of the MPL was not distributed with this
0007 // file, You can obtain one at https://mozilla.org/MPL/2.0/.
0008
0009 #include <boost/test/unit_test.hpp>
0010
0011 #include "Acts/Utilities/MultiIndex.hpp"
0012
0013 #include <array>
0014 #include <cstddef>
0015 #include <cstdint>
0016 #include <unordered_set>
0017
0018 #include <boost/mpl/list.hpp>
0019
0020 // 32bit split into a three level hierarchy.
0021 using Index32 = Acts::MultiIndex<std::uint32_t, 16, 8, 8>;
0022 // 64bit split into a four level hierarchy
0023 using Index64 = Acts::MultiIndex<std::uint64_t, 13, 17, 21, 13>;
0024 using Indices = boost::mpl::list<Index32, Index64>;
0025
0026 BOOST_AUTO_TEST_CASE_TEMPLATE(triviality, T, Indices) {
0027   // verify that the MultiIndex is a trivial type
0028   // this seems to be compiler-dependent; disable for now
0029   BOOST_CHECK(std::is_standard_layout_v<T>);
0030   BOOST_CHECK(std::is_trivially_default_constructible_v<T>);
0031   BOOST_CHECK(std::is_trivially_copy_constructible_v<T>);
0032   BOOST_CHECK(std::is_trivially_move_constructible_v<T>);
0033   BOOST_CHECK((std::is_trivially_assignable_v<T, T>));
0034   BOOST_CHECK((std::is_trivially_copy_assignable_v<T>));
0035   BOOST_CHECK((std::is_trivially_move_assignable_v<T>));
0036 }
0037
0038 BOOST_AUTO_TEST_CASE(index32_construct) {
0039   // construct from encoded value
0040   {
0041     Index32 idx(0xabcd2400u);
0042     BOOST_CHECK_EQUAL(idx.value(), 0xabcd2400u);
0043     BOOST_CHECK_EQUAL(idx.level(0), 0xabcdu);
0044     BOOST_CHECK_EQUAL(idx.level(1), 0x24u);
0045     BOOST_CHECK_EQUAL(idx.level(2), 0x00u);
0046   }
0047   // assign from encoded value
0048   {
0049     Index32 idx = 0xabcd2400u;
0050     BOOST_CHECK_EQUAL(idx.value(), 0xabcd2400u);
0051     BOOST_CHECK_EQUAL(idx.level(0), 0xabcdu);
0052     BOOST_CHECK_EQUAL(idx.level(1), 0x24u);
0053     BOOST_CHECK_EQUAL(idx.level(2), 0x00u);
0054   }
0055 }
0056
0057 BOOST_AUTO_TEST_CASE(index32_set) {
0058   Index32 idx = Index32::Zeros();
0059   // set a specific level within limits
0060   idx.set(0, 24u);
0061   BOOST_CHECK_EQUAL(idx.value(), 0x00180000u);
0062   BOOST_CHECK_EQUAL(idx.level(0), 24u);
0063   BOOST_CHECK_EQUAL(idx.level(1), 0u);
0064   BOOST_CHECK_EQUAL(idx.level(2), 0u);
0065   // set a specific level outside the valid range, should be truncated
0066   idx.set(2, 0xfff);
0067   BOOST_CHECK_EQUAL(idx.value(), 0x001800ffu);
0068   BOOST_CHECK_EQUAL(idx.level(0), 24u);
0069   BOOST_CHECK_EQUAL(idx.level(1), 0u);
0070   BOOST_CHECK_EQUAL(idx.level(2), 255u);
0071 }
0072
0073 BOOST_AUTO_TEST_CASE(index32_set_overflow) {
0074   // maximum values for each level
0075   Index32::Value maxValues[] = {
0076       (1u << 16u) - 1u,
0077       (1u << 8u) - 1u,
0078       (1u << 8u) - 1u,
0079   };
0080   // check that values above max are truncated
0081   std::size_t lvl = 0;
0082   for (auto maxValue : maxValues) {
0083     BOOST_CHECK_EQUAL(Index32::Zeros().set(lvl, maxValue + 1),
0084                       Index32::Zeros().set(lvl, 0u));
0085     lvl += 1;
0086   }
0087 }
0088
0089 BOOST_AUTO_TEST_CASE(index64_set_overflow) {
0090   // maximum values for each level
0091   Index32::Value maxValues[] = {
0092       (1u << 13u) - 1u,
0093       (1u << 17u) - 1u,
0094       (1u << 21u) - 1u,
0095       (1u << 13u) - 1u,
0096   };
0097   // check that values above max are truncated
0098   std::size_t lvl = 0;
0099   for (auto maxValue : maxValues) {
0100     BOOST_CHECK_EQUAL(Index64::Zeros().set(lvl, maxValue + 1),
0101                       Index64::Zeros().set(lvl, 0u));
0102     lvl += 1;
0103   }
0104 }
0105
0106 BOOST_AUTO_TEST_CASE(index32_encode) {
0107   // all three levels set
0108   auto idx3 = Index32::Encode(13u, 14u, 15u);
0109   BOOST_CHECK_EQUAL(idx3.level(0), 13u);
0110   BOOST_CHECK_EQUAL(idx3.level(1), 14u);
0111   BOOST_CHECK_EQUAL(idx3.level(2), 15u);
0112   // first two levels set
0113   auto idx2 = Index32::Encode(13u, 14u);
0114   BOOST_CHECK_EQUAL(idx2.level(0), 13u);
0115   BOOST_CHECK_EQUAL(idx2.level(1), 14u);
0116   BOOST_CHECK_EQUAL(idx2.level(2), 0u);
0117   // only the first level set
0118   auto idx1 = Index32::Encode(13u);
0119   BOOST_CHECK_EQUAL(idx1.level(0), 13u);
0120   BOOST_CHECK_EQUAL(idx1.level(1), 0u);
0121   BOOST_CHECK_EQUAL(idx1.level(2), 0u);
0122   // nothing set
0123   auto idx0 = Index32::Encode();
0124   BOOST_CHECK_EQUAL(idx0, Index32::Zeros());
0125   BOOST_CHECK_EQUAL(idx0.value(), 0u);
0126   BOOST_CHECK_EQUAL(idx0.level(0), 0u);
0127   BOOST_CHECK_EQUAL(idx0.level(1), 0u);
0128   BOOST_CHECK_EQUAL(idx0.level(2), 0u);
0129 }
0130
0131 BOOST_AUTO_TEST_CASE(index64_encode) {
0132   // all four levels set
0133   auto idx4 = Index64::Encode(23u, 14u, 15u, 17u);
0134   BOOST_CHECK_EQUAL(idx4.level(0), 23u);
0135   BOOST_CHECK_EQUAL(idx4.level(1), 14u);
0136   BOOST_CHECK_EQUAL(idx4.level(2), 15u);
0137   BOOST_CHECK_EQUAL(idx4.level(3), 17u);
0138   // first three levels set
0139   auto idx3 = Index64::Encode(23u, 14u, 15u);
0140   BOOST_CHECK_EQUAL(idx3.level(0), 23u);
0141   BOOST_CHECK_EQUAL(idx3.level(1), 14u);
0142   BOOST_CHECK_EQUAL(idx3.level(2), 15u);
0143   BOOST_CHECK_EQUAL(idx3.level(3), 0u);
0144   // first two levels set
0145   auto idx2 = Index64::Encode(23u, 14u);
0146   BOOST_CHECK_EQUAL(idx2.level(0), 23u);
0147   BOOST_CHECK_EQUAL(idx2.level(1), 14u);
0148   BOOST_CHECK_EQUAL(idx2.level(2), 0u);
0149   BOOST_CHECK_EQUAL(idx2.level(3), 0u);
0150   // only the first level set
0151   auto idx1 = Index64::Encode(23u);
0152   BOOST_CHECK_EQUAL(idx1.level(0), 23u);
0153   BOOST_CHECK_EQUAL(idx1.level(1), 0u);
0154   BOOST_CHECK_EQUAL(idx1.level(2), 0u);
0155   BOOST_CHECK_EQUAL(idx1.level(3), 0u);
0156   // nothing set
0157   auto idx0 = Index64::Encode();
0158   BOOST_CHECK_EQUAL(idx0, Index64::Zeros());
0159   BOOST_CHECK_EQUAL(idx0.value(), 0u);
0160   BOOST_CHECK_EQUAL(idx0.level(0), 0u);
0161   BOOST_CHECK_EQUAL(idx0.level(1), 0u);
0162   BOOST_CHECK_EQUAL(idx0.level(2), 0u);
0163   BOOST_CHECK_EQUAL(idx0.level(3), 0u);
0164 }
0165
0166 BOOST_AUTO_TEST_CASE(uint32_sibling) {
0167   auto idx = Index32::Encode(1u, 12u, 123u);
0168   BOOST_CHECK_EQUAL(idx.makeNextSibling(0), Index32::Encode(2u));
0169   BOOST_CHECK_EQUAL(idx.makeNextSibling(1), Index32::Encode(1u, 13u));
0170   BOOST_CHECK_EQUAL(idx.makeNextSibling(2), Index32::Encode(1u, 12u, 124u));
0171 }
0172
0173 BOOST_AUTO_TEST_CASE(uint64_sibling) {
0174   auto idx = Index64::Encode(1u, 12u, 123u, 1234u);
0175   BOOST_CHECK_EQUAL(idx.makeNextSibling(0), Index64::Encode(2u));
0176   BOOST_CHECK_EQUAL(idx.makeNextSibling(1), Index64::Encode(1u, 13u));
0177   BOOST_CHECK_EQUAL(idx.makeNextSibling(2), Index64::Encode(1u, 12u, 124u));
0178   BOOST_CHECK_EQUAL(idx.makeNextSibling(3),
0179                     Index64::Encode(1u, 12u, 123u, 1235u));
0180 }
0181
0182 BOOST_AUTO_TEST_CASE(uint32_descendant) {
0183   auto idx = Index32::Encode(1u, 12u, 123u);
0184   BOOST_CHECK_EQUAL(idx.makeLastDescendant(0), Index32::Encode(1u, 255u, 255u));
0185   BOOST_CHECK_EQUAL(idx.makeLastDescendant(1), Index32::Encode(1u, 12u, 255u));
0186   // last index has no descendant and stays the same
0187   BOOST_CHECK_EQUAL(idx.makeLastDescendant(2), Index32::Encode(1u, 12u, 123u));
0188 }
0189
0190 BOOST_AUTO_TEST_CASE(uint64_descendant) {
0191   auto idx = Index64::Encode(1u, 12u, 123u, 1234u);
0192   // from Index64 definition above
0193   auto max1 = (1u << 17) - 1u;
0194   auto max2 = (1u << 21) - 1u;
0195   auto max3 = (1u << 13) - 1u;
0196   BOOST_CHECK_EQUAL(idx.makeLastDescendant(0),
0197                     Index64::Encode(1u, max1, max2, max3));
0198   BOOST_CHECK_EQUAL(idx.makeLastDescendant(1),
0199                     Index64::Encode(1u, 12u, max2, max3));
0200   BOOST_CHECK_EQUAL(idx.makeLastDescendant(2),
0201                     Index64::Encode(1u, 12u, 123u, max3));
0202   // last index has no descendant and stays the same
0203   BOOST_CHECK_EQUAL(idx.makeLastDescendant(3),
0204                     Index64::Encode(1u, 12u, 123u, 1234u));
0205 }
0206
0207 BOOST_AUTO_TEST_CASE(index32_as_key) {
0208   std::unordered_set<Index32> set;
0209
0210   set.emplace(Index32::Encode(1u, 2u, 4u));
0211   set.emplace(Index32::Encode(1u, 3u, 4u));
0212   set.emplace(Index32::Encode(2u));
0213
0214   BOOST_CHECK(!set.count(Index32(0u)));
0215   BOOST_CHECK(!set.count(Index32(std::numeric_limits<std::uint32_t>::max())));
0216   BOOST_CHECK_EQUAL(set.size(), 3);
0217   // automatically converts encoded value to MultiIndex
0218   BOOST_CHECK(set.count(0x00010204u));
0219   BOOST_CHECK(set.count(0x00010304u));
0220   BOOST_CHECK(set.count(Index32::Encode(2u)));
0221 }
0222
0223 BOOST_AUTO_TEST_CASE(index64_as_key) {
0224   std::unordered_set<Index64> set;
0225
0226   set.emplace(Index64::Encode(1u, 1u, 1u));
0227   set.emplace(Index64::Encode(2u));
0228   // same as above
0229   set.emplace(Index64::Encode(2u, 0u, 0u, 0u));
0230   set.emplace(Index64::Encode(2u, 1u));
0231
0232   BOOST_CHECK(!set.count(Index64(0u)));
0233   BOOST_CHECK(!set.count(Index64(std::numeric_limits<std::uint64_t>::max())));
0234   BOOST_CHECK_EQUAL(set.size(), 3);
0235 }