ECCE @ EIC Software
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
MultiIndexTests.cpp
Go to the documentation of this file. Or view the newest version in sPHENIX GitHub for file MultiIndexTests.cpp
1 // This file is part of the Acts project.
2 //
3 // Copyright (C) 2017-2018 CERN for the benefit of the Acts project
4 //
5 // This Source Code Form is subject to the terms of the Mozilla Public
6 // License, v. 2.0. If a copy of the MPL was not distributed with this
7 // file, You can obtain one at http://mozilla.org/MPL/2.0/.
8 
9 #include <boost/test/unit_test.hpp>
10 
11 #include <cstdint>
12 #include <type_traits>
13 #include <unordered_set>
14 
15 #include <boost/mpl/list.hpp>
16 
17 #include "Acts/Utilities/MultiIndex.hpp"
18 
19 // 32bit split into a three level hierachy.
20 using Index32 = Acts::MultiIndex<uint32_t, 16, 8, 8>;
21 // 64bit split into a four level hierachy
22 using Index64 = Acts::MultiIndex<uint64_t, 13, 17, 21, 13>;
23 using Indices = boost::mpl::list<Index32, Index64>;
24 
25 BOOST_AUTO_TEST_CASE_TEMPLATE(triviality, T, Indices) {
26  // verify that the MultiIndex is a trivial type
27  // this seems to be compiler-dependent; disable for now
28  // BOOST_TEST(std::is_trivial_v<T>);
29  BOOST_TEST(std::is_standard_layout_v<T>);
30  BOOST_TEST(std::is_trivially_default_constructible_v<T>);
31  BOOST_TEST(std::is_trivially_copy_constructible_v<T>);
32  BOOST_TEST(std::is_trivially_move_constructible_v<T>);
33  BOOST_TEST((std::is_trivially_assignable_v<T, T>));
34  BOOST_TEST((std::is_trivially_copy_assignable_v<T>));
35  BOOST_TEST((std::is_trivially_move_assignable_v<T>));
36 }
37 
38 BOOST_AUTO_TEST_CASE(index32_construct) {
39  // construct from encoded value
40  {
41  Index32 idx(0xabcd2400u);
42  BOOST_TEST(idx.value() == 0xabcd2400u);
43  BOOST_TEST(idx.level(0) == 0xabcdu);
44  BOOST_TEST(idx.level(1) == 0x24u);
45  BOOST_TEST(idx.level(2) == 0x00u);
46  }
47  // assign from encoded value
48  {
49  Index32 idx = 0xabcd2400u;
50  BOOST_TEST(idx.value() == 0xabcd2400u);
51  BOOST_TEST(idx.level(0) == 0xabcdu);
52  BOOST_TEST(idx.level(1) == 0x24u);
53  BOOST_TEST(idx.level(2) == 0x00u);
54  }
55 }
56 
57 BOOST_AUTO_TEST_CASE(index32_set) {
58  Index32 idx = Index32::Zeros();
59  // set a specific level within limits
60  idx.set(0, 24u);
61  BOOST_TEST(idx.value() == 0x00180000u);
62  BOOST_TEST(idx.level(0) == 24u);
63  BOOST_TEST(idx.level(1) == 0u);
64  BOOST_TEST(idx.level(2) == 0u);
65  // set a specific level outside the valid range, should be truncated
66  idx.set(2, 0xfff);
67  BOOST_TEST(idx.value() == 0x001800ffu);
68  BOOST_TEST(idx.level(0) == 24u);
69  BOOST_TEST(idx.level(1) == 0u);
70  BOOST_TEST(idx.level(2) == 255u);
71 }
72 
73 BOOST_AUTO_TEST_CASE(index32_set_overflow) {
74  // maximum values for each level
75  Index32::Value maxValues[] = {
76  (1u << 16u) - 1u,
77  (1u << 8u) - 1u,
78  (1u << 8u) - 1u,
79  };
80  // check that values above max are truncated
81  std::size_t lvl = 0;
82  for (auto maxValue : maxValues) {
83  BOOST_TEST(Index32::Zeros().set(lvl, maxValue + 1) ==
84  Index32::Zeros().set(lvl, 0u));
85  lvl += 1;
86  }
87 }
88 
89 BOOST_AUTO_TEST_CASE(index64_set_overflow) {
90  // maximum values for each level
91  Index32::Value maxValues[] = {
92  (1u << 13u) - 1u,
93  (1u << 17u) - 1u,
94  (1u << 21u) - 1u,
95  (1u << 13u) - 1u,
96  };
97  // check that values above max are truncated
98  std::size_t lvl = 0;
99  for (auto maxValue : maxValues) {
100  BOOST_TEST(Index64::Zeros().set(lvl, maxValue + 1) ==
101  Index64::Zeros().set(lvl, 0u));
102  lvl += 1;
103  }
104 }
105 
106 BOOST_AUTO_TEST_CASE(index32_encode) {
107  // all three levels set
108  auto idx3 = Index32::Encode(13u, 14u, 15u);
109  BOOST_TEST(idx3.level(0) == 13u);
110  BOOST_TEST(idx3.level(1) == 14u);
111  BOOST_TEST(idx3.level(2) == 15u);
112  // first two levels set
113  auto idx2 = Index32::Encode(13u, 14u);
114  BOOST_TEST(idx2.level(0) == 13u);
115  BOOST_TEST(idx2.level(1) == 14u);
116  BOOST_TEST(idx2.level(2) == 0u);
117  // only the first level set
118  auto idx1 = Index32::Encode(13u);
119  BOOST_TEST(idx1.level(0) == 13u);
120  BOOST_TEST(idx1.level(1) == 0u);
121  BOOST_TEST(idx1.level(2) == 0u);
122  // nothing set
123  auto idx0 = Index32::Encode();
124  BOOST_TEST(idx0 == Index32::Zeros());
125  BOOST_TEST(idx0.value() == 0u);
126  BOOST_TEST(idx0.level(0) == 0u);
127  BOOST_TEST(idx0.level(1) == 0u);
128  BOOST_TEST(idx0.level(2) == 0u);
129 }
130 
131 BOOST_AUTO_TEST_CASE(index64_encode) {
132  // all four levels set
133  auto idx4 = Index64::Encode(23u, 14u, 15u, 17u);
134  BOOST_TEST(idx4.level(0) == 23u);
135  BOOST_TEST(idx4.level(1) == 14u);
136  BOOST_TEST(idx4.level(2) == 15u);
137  BOOST_TEST(idx4.level(3) == 17u);
138  // first three levels set
139  auto idx3 = Index64::Encode(23u, 14u, 15u);
140  BOOST_TEST(idx3.level(0) == 23u);
141  BOOST_TEST(idx3.level(1) == 14u);
142  BOOST_TEST(idx3.level(2) == 15u);
143  BOOST_TEST(idx3.level(3) == 0u);
144  // first two levels set
145  auto idx2 = Index64::Encode(23u, 14u);
146  BOOST_TEST(idx2.level(0) == 23u);
147  BOOST_TEST(idx2.level(1) == 14u);
148  BOOST_TEST(idx2.level(2) == 0u);
149  BOOST_TEST(idx2.level(3) == 0u);
150  // only the first level set
151  auto idx1 = Index64::Encode(23u);
152  BOOST_TEST(idx1.level(0) == 23u);
153  BOOST_TEST(idx1.level(1) == 0u);
154  BOOST_TEST(idx1.level(2) == 0u);
155  BOOST_TEST(idx1.level(3) == 0u);
156  // nothing set
157  auto idx0 = Index64::Encode();
158  BOOST_TEST(idx0 == Index64::Zeros());
159  BOOST_TEST(idx0.value() == 0u);
160  BOOST_TEST(idx0.level(0) == 0u);
161  BOOST_TEST(idx0.level(1) == 0u);
162  BOOST_TEST(idx0.level(2) == 0u);
163  BOOST_TEST(idx0.level(3) == 0u);
164 }
165 
166 BOOST_AUTO_TEST_CASE(uint32_sibling) {
167  auto idx = Index32::Encode(1u, 12u, 123u);
168  BOOST_TEST(idx.makeNextSibling(0) == Index32::Encode(2u));
169  BOOST_TEST(idx.makeNextSibling(1) == Index32::Encode(1u, 13u));
170  BOOST_TEST(idx.makeNextSibling(2) == Index32::Encode(1u, 12u, 124u));
171 }
172 
173 BOOST_AUTO_TEST_CASE(uint64_sibling) {
174  auto idx = Index64::Encode(1u, 12u, 123u, 1234u);
175  BOOST_TEST(idx.makeNextSibling(0) == Index64::Encode(2u));
176  BOOST_TEST(idx.makeNextSibling(1) == Index64::Encode(1u, 13u));
177  BOOST_TEST(idx.makeNextSibling(2) == Index64::Encode(1u, 12u, 124u));
178  BOOST_TEST(idx.makeNextSibling(3) == Index64::Encode(1u, 12u, 123u, 1235u));
179 }
180 
181 BOOST_AUTO_TEST_CASE(uint32_descendant) {
182  auto idx = Index32::Encode(1u, 12u, 123u);
183  BOOST_TEST(idx.makeLastDescendant(0) == Index32::Encode(1u, 255u, 255u));
184  BOOST_TEST(idx.makeLastDescendant(1) == Index32::Encode(1u, 12u, 255u));
185  // last index has no descendant and stays the same
186  BOOST_TEST(idx.makeLastDescendant(2) == Index32::Encode(1u, 12u, 123u));
187 }
188 
189 BOOST_AUTO_TEST_CASE(uint64_descendant) {
190  auto idx = Index64::Encode(1u, 12u, 123u, 1234u);
191  // from Index64 definition above
192  auto max1 = (1u << 17) - 1u;
193  auto max2 = (1u << 21) - 1u;
194  auto max3 = (1u << 13) - 1u;
195  BOOST_TEST(idx.makeLastDescendant(0) ==
196  Index64::Encode(1u, max1, max2, max3));
197  BOOST_TEST(idx.makeLastDescendant(1) == Index64::Encode(1u, 12u, max2, max3));
198  BOOST_TEST(idx.makeLastDescendant(2) == Index64::Encode(1u, 12u, 123u, max3));
199  // last index has no descendant and stays the same
200  BOOST_TEST(idx.makeLastDescendant(3) ==
201  Index64::Encode(1u, 12u, 123u, 1234u));
202 }
203 
204 BOOST_AUTO_TEST_CASE(index32_as_key) {
205  std::unordered_set<Index32> set;
206 
207  set.emplace(Index32::Encode(1u, 2u, 4u));
208  set.emplace(Index32::Encode(1u, 3u, 4u));
209  set.emplace(Index32::Encode(2u));
210 
211  BOOST_TEST(not set.count(Index32(0u)));
212  BOOST_TEST(not set.count(Index32(UINT32_MAX)));
213  BOOST_TEST(set.size() == 3);
214  // automatically converts encoded value to MultiIndex
215  BOOST_TEST(set.count(0x00010204u));
216  BOOST_TEST(set.count(0x00010304u));
217  BOOST_TEST(set.count(Index32::Encode(2u)));
218 }
219 
220 BOOST_AUTO_TEST_CASE(index64_as_key) {
221  std::unordered_set<Index64> set;
222 
223  set.emplace(Index64::Encode(1u, 1u, 1u));
224  set.emplace(Index64::Encode(2u));
225  // same as above
226  set.emplace(Index64::Encode(2u, 0u, 0u, 0u));
227  set.emplace(Index64::Encode(2u, 1u));
228 
229  BOOST_TEST(not set.count(Index64(0u)));
230  BOOST_TEST(not set.count(Index64(UINT64_MAX)));
231  BOOST_TEST(set.size() == 3);
232 }