1 //===----------------------------------------------------------------------===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 9 #ifndef SUPPORT_FROM_RANGE_UNORDERED_CONTAINERS_H 10 #define SUPPORT_FROM_RANGE_UNORDERED_CONTAINERS_H 11 12 #include <algorithm> 13 #include <cassert> 14 #include <cmath> 15 #include <cstddef> 16 #include <limits> 17 #include <ranges> 18 #include <vector> 19 #include <utility> 20 21 #include "../exception_safety_helpers.h" 22 #include "../from_range_helpers.h" 23 #include "../test_compare.h" 24 #include "../test_hash.h" 25 #include "MoveOnly.h" 26 #include "almost_satisfies_types.h" 27 #include "count_new.h" 28 #include "test_macros.h" 29 30 // template<container-compatible-range<value_type> R> 31 // unordered-container(from_range_t, R&& rg, size_type n = see below, 32 // const hasher& hf = hasher(), const key_equal& eql = key_equal(), 33 // const allocator_type& a = allocator_type()); // C++23 34 // 35 // template<container-compatible-range<value_type> R> 36 // unordered-container(from_range_t, R&& rg, size_type n, const allocator_type& a) 37 // : unordered-container(from_range, std::forward<R>(rg), n, hasher(), key_equal(), a) { } // C++23 38 // 39 // template<container-compatible-range<value_type> R> 40 // unordered-container(from_range_t, R&& rg, size_type n, const hasher& hf, const allocator_type& a) 41 // : unordered-container(from_range, std::forward<R>(rg), n, hf, key_equal(), a) { } // C++23 42 43 template <class Container, class Range> 44 concept HasFromRangeCtr = requires (Range&& range) { 45 // (from_range, range) 46 Container(std::from_range, std::forward<Range>(range)); 47 // (from_range, range, n) 48 Container(std::from_range, std::forward<Range>(range), 0); 49 // (from_range, range, n, hash) 50 Container(std::from_range, std::forward<Range>(range), 0, std::hash<typename Container::key_type>()); 51 // (from_range, range, n, hash, equal) 52 Container(std::from_range, std::forward<Range>(range), 0, std::hash<typename Container::key_type>(), 53 std::equal_to<typename Container::key_type>()); 54 // (from_range, range, n, hash, equal, alloc) 55 Container(std::from_range, std::forward<Range>(range), 0, std::hash<typename Container::key_type>(), 56 std::equal_to<typename Container::key_type>(), std::allocator<typename Container::value_type>()); 57 // (from_range, range, n, alloc) 58 Container(std::from_range, std::forward<Range>(range), 0, std::allocator<typename Container::value_type>()); 59 // (from_range, range, n, hash, alloc) 60 Container(std::from_range, std::forward<Range>(range), 0, std::hash<typename Container::key_type>(), 61 std::allocator<typename Container::value_type>()); 62 }; 63 64 template <template <class...> class Container, class K, class V, class K2, class V2> 65 constexpr bool test_map_constraints() { 66 using ValueType = std::pair<const K, V>; 67 68 // Input range with the same value type. 69 static_assert(HasFromRangeCtr<Container<K, V>, InputRange<ValueType>>); 70 // Input range with a convertible value type. 71 static_assert(HasFromRangeCtr<Container<K, V>, InputRange<std::pair<const K2, V2>>>); 72 // Input range with a non-convertible value type. 73 static_assert(!HasFromRangeCtr<Container<K, V>, InputRange<std::pair<const Empty, V>>>); 74 static_assert(!HasFromRangeCtr<Container<K, V>, InputRange<std::pair<const K, Empty>>>); 75 // Not an input range. 76 static_assert(!HasFromRangeCtr<Container<K, V>, InputRangeNotDerivedFromGeneric<ValueType>>); 77 78 return true; 79 } 80 81 template <template <class ...> class Container, 82 class K, 83 class V, 84 class Iter, 85 class Sent, 86 class Hash, 87 class Equal, 88 class Alloc, 89 class ValueType = std::pair<const K, V>> 90 void test_unordered_map_with_input(std::vector<ValueType>&& input) { 91 using DefaultHash = std::hash<int>; 92 using DefaultEqual = std::equal_to<int>; 93 94 auto validate = [](auto&& c) { 95 if (!c.empty()) { 96 auto diff = c.load_factor() - (static_cast<float>(c.size()) / c.bucket_count()); 97 assert(std::fabs(diff) < std::numeric_limits<float>::epsilon()); 98 } 99 assert(c.max_load_factor() == 1); 100 }; 101 102 { // (range) 103 auto in = wrap_input<Iter, Sent>(input); 104 Container<K, V> c(std::from_range, in); 105 106 assert(c.size() == static_cast<std::size_t>(std::distance(c.begin(), c.end()))); 107 assert(std::ranges::is_permutation(input, c)); 108 validate(c); 109 } 110 111 { // (range, n) 112 auto in = wrap_input<Iter, Sent>(input); 113 Container<K, V> c(std::from_range, in, 123); 114 115 assert(c.size() == static_cast<std::size_t>(std::distance(c.begin(), c.end()))); 116 assert(std::ranges::is_permutation(input, c)); 117 validate(c); 118 } 119 120 { // (range, n, hasher) 121 auto in = wrap_input<Iter, Sent>(input); 122 Container<K, V, Hash> c(std::from_range, in, 123, Hash()); 123 124 assert(c.hash_function() == Hash()); 125 assert(c.size() == static_cast<std::size_t>(std::distance(c.begin(), c.end()))); 126 assert(std::ranges::is_permutation(input, c)); 127 validate(c); 128 } 129 130 { // (range, n, hasher, key_equal) 131 auto in = wrap_input<Iter, Sent>(input); 132 Container<K, V, Hash, Equal> c(std::from_range, in, 123, Hash(), Equal()); 133 134 assert(c.hash_function() == Hash()); 135 assert(c.key_eq() == Equal()); 136 assert(c.size() == static_cast<std::size_t>(std::distance(c.begin(), c.end()))); 137 assert(std::ranges::is_permutation(input, c)); 138 validate(c); 139 } 140 141 { // (range, n, hasher, key_equal, allocator) 142 auto in = wrap_input<Iter, Sent>(input); 143 Alloc alloc; 144 Container<K, V, Hash, Equal, Alloc> c(std::from_range, in, 123, Hash(), Equal(), alloc); 145 146 assert(c.hash_function() == Hash()); 147 assert(c.key_eq() == Equal()); 148 assert(c.get_allocator() == alloc); 149 assert(c.size() == static_cast<std::size_t>(std::distance(c.begin(), c.end()))); 150 assert(std::ranges::is_permutation(input, c)); 151 validate(c); 152 } 153 154 { // (range, n, allocator) 155 auto in = wrap_input<Iter, Sent>(input); 156 Alloc alloc; 157 Container<K, V, DefaultHash, DefaultEqual, Alloc> c(std::from_range, in, 123, alloc); 158 159 assert(c.get_allocator() == alloc); 160 assert(c.size() == static_cast<std::size_t>(std::distance(c.begin(), c.end()))); 161 assert(std::ranges::is_permutation(input, c)); 162 validate(c); 163 } 164 165 { // (range, n, hasher, allocator) 166 auto in = wrap_input<Iter, Sent>(input); 167 Alloc alloc; 168 Container<K, V, Hash, DefaultEqual, Alloc> c(std::from_range, in, 123, Hash(), alloc); 169 170 assert(c.hash_function() == Hash()); 171 assert(c.get_allocator() == alloc); 172 assert(c.size() == static_cast<std::size_t>(std::distance(c.begin(), c.end()))); 173 assert(std::ranges::is_permutation(input, c)); 174 validate(c); 175 } 176 } 177 178 template <template <class ...> class Container, 179 class K, 180 class V, 181 class Iter, 182 class Sent, 183 class Hash, 184 class Equal, 185 class Alloc> 186 void test_unordered_map() { 187 auto test_with_input = &test_unordered_map_with_input<Container, K, V, Iter, Sent, Hash, Equal, Alloc>; 188 189 // Normal input. 190 test_with_input({{1, 2}, {3, 4}, {5, 6}, {7, 8}, {9, 10}}); 191 // Empty input. 192 test_with_input({}); 193 // Single-element input. 194 test_with_input({{1, 2}}); 195 } 196 197 template <template <class ...> class Container> 198 void test_unordered_map_move_only() { 199 std::pair<const int, MoveOnly> input[5]; 200 std::ranges::subrange in(std::move_iterator{input}, std::move_iterator{input + 5}); 201 202 [[maybe_unused]] Container<int, MoveOnly> c(std::from_range, in); 203 } 204 205 template <template <class ...> class Container> 206 void test_map_exception_safety_throwing_copy() { 207 #if !defined(TEST_HAS_NO_EXCEPTIONS) 208 using K = int; 209 using V = ThrowingCopy<3>; 210 211 V::throwing_enabled = false; 212 std::pair<const K, V> in[5] = { 213 {1, {}}, {2, {}}, {3, {}}, {4, {}}, {5, {}} 214 }; 215 V::throwing_enabled = true; 216 V::reset(); 217 218 try { 219 Container<K, V> c(std::from_range, in); 220 assert(false); // The constructor call above should throw. 221 222 } catch (int) { 223 assert(V::created_by_copying == 3); 224 assert(V::destroyed == 2); // No destructor call for the partially-constructed element. 225 } 226 #endif 227 } 228 229 template <template <class ...> class Container, class K, class V> 230 void test_map_exception_safety_throwing_allocator() { 231 #if !defined(TEST_HAS_NO_EXCEPTIONS) 232 using ValueType = std::pair<const K, V>; 233 ValueType in[] = { 234 ValueType{K{1}, V{1}} 235 }; 236 237 try { 238 ThrowingAllocator<ValueType> alloc; 239 240 globalMemCounter.reset(); 241 Container<K, V, test_hash<K>, test_equal_to<K>, ThrowingAllocator<ValueType>> 242 c(std::from_range, in, /*n=*/0, alloc); 243 assert(false); // The constructor call should throw. 244 245 } catch (int) { 246 assert(globalMemCounter.new_called == globalMemCounter.delete_called); 247 } 248 #endif 249 } 250 251 template <class Container, class Range> 252 concept SetHasFromRangeCtr = requires (Range&& range) { 253 // (from_range, range) 254 Container(std::from_range, std::forward<Range>(range)); 255 // (from_range, range, n) 256 Container(std::from_range, std::forward<Range>(range), 0); 257 // (from_range, range, n, hash) 258 Container(std::from_range, std::forward<Range>(range), 0, std::hash<typename Container::value_type>()); 259 // (from_range, range, n, hash, equal) 260 Container(std::from_range, std::forward<Range>(range), 0, std::hash<typename Container::value_type>(), 261 std::equal_to<typename Container::value_type>()); 262 // (from_range, range, n, hash, equal, alloc) 263 Container(std::from_range, std::forward<Range>(range), 0, std::hash<typename Container::value_type>(), 264 std::equal_to<typename Container::value_type>(), std::allocator<typename Container::value_type>()); 265 // (from_range, range, n, alloc) 266 Container(std::from_range, std::forward<Range>(range), 0, std::allocator<typename Container::value_type>()); 267 // (from_range, range, n, hash, alloc) 268 Container(std::from_range, std::forward<Range>(range), 0, std::hash<typename Container::value_type>(), 269 std::allocator<typename Container::value_type>()); 270 }; 271 272 template <template <class...> class Container, class T, class U> 273 constexpr bool test_set_constraints() { 274 // Input range with the same value type. 275 static_assert(HasFromRangeCtr<Container<T>, InputRange<T>>); 276 // Input range with a convertible value type. 277 static_assert(HasFromRangeCtr<Container<T>, InputRange<U>>); 278 // Input range with a non-convertible value type. 279 static_assert(!HasFromRangeCtr<Container<T>, InputRange<Empty>>); 280 // Not an input range. 281 static_assert(!HasFromRangeCtr<Container<T>, InputRangeNotDerivedFromGeneric<T>>); 282 283 return true; 284 } 285 286 template <template <class ...> class Container, 287 class T, 288 class Iter, 289 class Sent, 290 class Hash, 291 class Equal, 292 class Alloc> 293 void test_unordered_set_with_input(std::vector<T>&& input) { 294 using DefaultHash = std::hash<int>; 295 using DefaultEqual = std::equal_to<int>; 296 297 auto validate = [](auto&& c) { 298 if (!c.empty()) { 299 auto diff = c.load_factor() - (static_cast<float>(c.size()) / c.bucket_count()); 300 assert(std::fabs(diff) < std::numeric_limits<float>::epsilon()); 301 } 302 assert(c.max_load_factor() == 1); 303 }; 304 305 { // (range) 306 std::ranges::subrange in(Iter(input.data()), Sent(Iter(input.data() + input.size()))); 307 Container<T> c(std::from_range, in); 308 309 assert(c.size() == static_cast<std::size_t>(std::distance(c.begin(), c.end()))); 310 assert(std::ranges::is_permutation(input, c)); 311 validate(c); 312 } 313 314 { // (range, n) 315 std::ranges::subrange in(Iter(input.data()), Sent(Iter(input.data() + input.size()))); 316 Container<T> c(std::from_range, in, 123); 317 318 assert(c.size() == static_cast<std::size_t>(std::distance(c.begin(), c.end()))); 319 assert(std::ranges::is_permutation(input, c)); 320 validate(c); 321 } 322 323 { // (range, n, hasher) 324 std::ranges::subrange in(Iter(input.data()), Sent(Iter(input.data() + input.size()))); 325 Container<T, Hash> c(std::from_range, in, 123, Hash()); 326 327 assert(c.hash_function() == Hash()); 328 assert(c.size() == static_cast<std::size_t>(std::distance(c.begin(), c.end()))); 329 assert(std::ranges::is_permutation(input, c)); 330 validate(c); 331 } 332 333 { // (range, n, hasher, key_equal) 334 std::ranges::subrange in(Iter(input.data()), Sent(Iter(input.data() + input.size()))); 335 Container<T, Hash, Equal> c(std::from_range, in, 123, Hash(), Equal()); 336 337 assert(c.hash_function() == Hash()); 338 assert(c.key_eq() == Equal()); 339 assert(c.size() == static_cast<std::size_t>(std::distance(c.begin(), c.end()))); 340 assert(std::ranges::is_permutation(input, c)); 341 validate(c); 342 } 343 344 { // (range, n, hasher, key_equal, allocator) 345 std::ranges::subrange in(Iter(input.data()), Sent(Iter(input.data() + input.size()))); 346 Alloc alloc; 347 Container<T, Hash, Equal, Alloc> c(std::from_range, in, 123, Hash(), Equal(), alloc); 348 349 assert(c.hash_function() == Hash()); 350 assert(c.key_eq() == Equal()); 351 assert(c.get_allocator() == alloc); 352 assert(c.size() == static_cast<std::size_t>(std::distance(c.begin(), c.end()))); 353 assert(std::ranges::is_permutation(input, c)); 354 validate(c); 355 } 356 357 { // (range, n, allocator) 358 std::ranges::subrange in(Iter(input.data()), Sent(Iter(input.data() + input.size()))); 359 Alloc alloc; 360 Container<T, DefaultHash, DefaultEqual, Alloc> c(std::from_range, in, 123, alloc); 361 362 assert(c.get_allocator() == alloc); 363 assert(c.size() == static_cast<std::size_t>(std::distance(c.begin(), c.end()))); 364 assert(std::ranges::is_permutation(input, c)); 365 validate(c); 366 } 367 368 { // (range, n, hasher, allocator) 369 std::ranges::subrange in(Iter(input.data()), Sent(Iter(input.data() + input.size()))); 370 Alloc alloc; 371 Container<T, Hash, DefaultEqual, Alloc> c(std::from_range, in, 123, Hash(), alloc); 372 373 assert(c.hash_function() == Hash()); 374 assert(c.get_allocator() == alloc); 375 assert(c.size() == static_cast<std::size_t>(std::distance(c.begin(), c.end()))); 376 assert(std::ranges::is_permutation(input, c)); 377 validate(c); 378 } 379 } 380 381 template <template <class ...> class Container, 382 class T, 383 class Iter, 384 class Sent, 385 class Hash, 386 class Equal, 387 class Alloc> 388 void test_unordered_set() { 389 auto test_with_input = &test_unordered_set_with_input<Container, T, Iter, Sent, Hash, Equal, Alloc>; 390 391 // Normal input. 392 test_with_input({0, 5, 12, 7, -1, 8, 26}); 393 // Empty input. 394 test_with_input({}); 395 // Single-element input. 396 test_with_input({5}); 397 } 398 399 template <template <class ...> class Container> 400 void test_unordered_set_move_only() { 401 MoveOnly input[5]; 402 std::ranges::subrange in(std::move_iterator{input}, std::move_iterator{input + 5}); 403 404 [[maybe_unused]] Container<MoveOnly> c(std::from_range, in); 405 } 406 407 template <template <class ...> class Container> 408 void test_set_exception_safety_throwing_copy() { 409 #if !defined(TEST_HAS_NO_EXCEPTIONS) 410 using T = ThrowingCopy<3>; 411 T::reset(); 412 T in[5] = {{1}, {2}, {3}, {4}, {5}}; 413 414 try { 415 Container<T, test_hash<T>> c(std::from_range, in); 416 assert(false); // The constructor call above should throw. 417 418 } catch (int) { 419 assert(T::created_by_copying == 3); 420 assert(T::destroyed == 2); // No destructor call for the partially-constructed element. 421 } 422 #endif 423 } 424 425 template <template <class ...> class Container, class T> 426 void test_set_exception_safety_throwing_allocator() { 427 #if !defined(TEST_HAS_NO_EXCEPTIONS) 428 T in[] = {1, 2, 3}; 429 430 try { 431 ThrowingAllocator<T> alloc; 432 433 globalMemCounter.reset(); 434 Container<T, test_hash<T>, test_equal_to<T>, ThrowingAllocator<T>> c(std::from_range, in, /*n=*/0, alloc); 435 assert(false); // The constructor call should throw. 436 437 } catch (int) { 438 assert(globalMemCounter.new_called == globalMemCounter.delete_called); 439 } 440 #endif 441 } 442 443 #endif // SUPPORT_FROM_RANGE_UNORDERED_CONTAINERS_H 444