230 lines · c
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-exception6//7//===----------------------------------------------------------------------===//8 9#ifndef SUPPORT_FLAT_MULTIMAP_HELPERS_H10#define SUPPORT_FLAT_MULTIMAP_HELPERS_H11 12#include <algorithm>13#include <cassert>14#include <string>15#include <vector>16#include <flat_map>17#include <ranges>18#include <type_traits>19 20#include "../flat_helpers.h"21#include "test_allocator.h"22#include "test_macros.h"23 24template <class... Args>25constexpr void check_invariant(const std::flat_multimap<Args...>& m) {26 assert(m.keys().size() == m.values().size());27 const auto& keys = m.keys();28 assert(std::is_sorted(keys.begin(), keys.end(), m.key_comp()));29}30 31constexpr void check_possible_values(const auto& actual, const auto& expected) {32 assert(std::ranges::size(actual) == std::ranges::size(expected));33 34 for (const auto& [actual_value, possible_values] : std::views::zip(actual, expected)) {35 assert(std::ranges::find(possible_values, actual_value) != std::ranges::end(possible_values));36 }37}38 39template <class F>40void test_emplace_exception_guarantee([[maybe_unused]] F&& emplace_function) {41#ifndef TEST_HAS_NO_EXCEPTIONS42 using C = TransparentComparator;43 {44 // Throw on emplace the key, and underlying has strong exception guarantee45 using KeyContainer = std::vector<int, test_allocator<int>>;46 using M = std::flat_multimap<int, int, C, KeyContainer>;47 48 LIBCPP_STATIC_ASSERT(std::__container_traits<KeyContainer>::__emplacement_has_strong_exception_safety_guarantee);49 50 test_allocator_statistics stats;51 52 KeyContainer a({1, 1, 2, 4}, test_allocator<int>{&stats});53 std::vector<int> b = {5, 6, 7, 8};54 [[maybe_unused]] auto expected_keys = a;55 [[maybe_unused]] auto expected_values = b;56 M m(std::sorted_equivalent, std::move(a), std::move(b));57 58 stats.throw_after = 1;59 try {60 emplace_function(m, 1, 1);61 assert(false);62 } catch (const std::bad_alloc&) {63 check_invariant(m);64 // In libc++, the flat_multimap is unchanged65 LIBCPP_ASSERT(m.size() == 4);66 LIBCPP_ASSERT(m.keys() == expected_keys);67 LIBCPP_ASSERT(m.values() == expected_values);68 }69 }70 {71 // Throw on emplace the key, and underlying has no strong exception guarantee72 using KeyContainer = EmplaceUnsafeContainer<int>;73 using M = std::flat_multimap<int, int, C, KeyContainer>;74 75 LIBCPP_STATIC_ASSERT(!std::__container_traits<KeyContainer>::__emplacement_has_strong_exception_safety_guarantee);76 KeyContainer a = {1, 2, 2, 4};77 std::vector<int> b = {5, 6, 7, 8};78 M m(std::sorted_equivalent, std::move(a), std::move(b));79 try {80 emplace_function(m, 1, 1);81 assert(false);82 } catch (int) {83 check_invariant(m);84 // In libc++, the flat_multimap is cleared85 LIBCPP_ASSERT(m.size() == 0);86 }87 }88 {89 // Throw on emplace the value, and underlying has strong exception guarantee90 using ValueContainer = std::vector<int, test_allocator<int>>;91 ;92 using M = std::flat_multimap<int, int, C, std::vector<int>, ValueContainer>;93 94 LIBCPP_STATIC_ASSERT(std::__container_traits<ValueContainer>::__emplacement_has_strong_exception_safety_guarantee);95 96 std::vector<int> a = {1, 3, 3, 4};97 test_allocator_statistics stats;98 ValueContainer b({1, 2, 3, 4}, test_allocator<int>{&stats});99 100 [[maybe_unused]] auto expected_keys = a;101 [[maybe_unused]] auto expected_values = b;102 M m(std::sorted_equivalent, std::move(a), std::move(b));103 104 stats.throw_after = 1;105 try {106 emplace_function(m, 3, 3);107 assert(false);108 } catch (const std::bad_alloc&) {109 check_invariant(m);110 // In libc++, the emplaced key is erased and the flat_multimap is unchanged111 LIBCPP_ASSERT(m.size() == 4);112 LIBCPP_ASSERT(m.keys() == expected_keys);113 LIBCPP_ASSERT(m.values() == expected_values);114 }115 }116 {117 // Throw on emplace the value, and underlying has no strong exception guarantee118 using ValueContainer = EmplaceUnsafeContainer<int>;119 using M = std::flat_multimap<int, int, C, std::vector<int>, ValueContainer>;120 121 LIBCPP_STATIC_ASSERT(!std::__container_traits<ValueContainer>::__emplacement_has_strong_exception_safety_guarantee);122 std::vector<int> a = {1, 1, 1, 1};123 ValueContainer b = {1, 2, 3, 4};124 125 M m(std::sorted_equivalent, std::move(a), std::move(b));126 127 try {128 emplace_function(m, 1, 5);129 assert(false);130 } catch (int) {131 check_invariant(m);132 // In libc++, the flat_multimap is cleared133 LIBCPP_ASSERT(m.size() == 0);134 }135 }136 {137 // Throw on emplace the value, then throw again on erasing the key138 using KeyContainer = ThrowOnEraseContainer<int>;139 using ValueContainer = std::vector<int, test_allocator<int>>;140 using M = std::flat_multimap<int, int, C, KeyContainer, ValueContainer>;141 142 LIBCPP_STATIC_ASSERT(std::__container_traits<ValueContainer>::__emplacement_has_strong_exception_safety_guarantee);143 144 KeyContainer a = {4, 4, 4, 4};145 test_allocator_statistics stats;146 ValueContainer b({1, 2, 3, 4}, test_allocator<int>{&stats});147 148 M m(std::sorted_equivalent, std::move(a), std::move(b));149 stats.throw_after = 1;150 try {151 emplace_function(m, 0, 0);152 assert(false);153 } catch (const std::bad_alloc&) {154 check_invariant(m);155 // In libc++, we try to erase the key after value emplacement failure.156 // and after erasure failure, we clear the flat_multimap157 LIBCPP_ASSERT(m.size() == 0);158 }159 }160#endif161}162 163template <class F>164void test_insert_range_exception_guarantee([[maybe_unused]] F&& insert_function) {165#ifndef TEST_HAS_NO_EXCEPTIONS166 using KeyContainer = EmplaceUnsafeContainer<int>;167 using ValueContainer = std::vector<int>;168 using M = std::flat_multimap<int, int, std::ranges::less, KeyContainer, ValueContainer>;169 test_allocator_statistics stats;170 KeyContainer a{1, 2, 3, 4};171 ValueContainer b{1, 2, 3, 4};172 M m(std::sorted_equivalent, std::move(a), std::move(b));173 174 std::vector<std::pair<int, int>> newValues = {{0, 0}, {1, 1}, {5, 5}, {6, 6}, {7, 7}, {8, 8}};175 stats.throw_after = 1;176 try {177 insert_function(m, newValues);178 assert(false);179 } catch (int) {180 check_invariant(m);181 // In libc++, we clear if anything goes wrong when inserting a range182 LIBCPP_ASSERT(m.size() == 0);183 }184#endif185}186 187template <class F>188void test_erase_exception_guarantee([[maybe_unused]] F&& erase_function) {189#ifndef TEST_HAS_NO_EXCEPTIONS190 {191 // key erase throws192 using KeyContainer = ThrowOnEraseContainer<int>;193 using ValueContainer = std::vector<int>;194 using M = std::flat_multimap<int, int, TransparentComparator, KeyContainer, ValueContainer>;195 196 KeyContainer a{1, 3, 3, 4};197 ValueContainer b{1, 3, 3, 4};198 M m(std::sorted_equivalent, std::move(a), std::move(b));199 try {200 erase_function(m, 3);201 assert(false);202 } catch (int) {203 check_invariant(m);204 // In libc++, we clear if anything goes wrong when erasing205 LIBCPP_ASSERT(m.size() == 0);206 }207 }208 {209 // key erase throws210 using KeyContainer = std::vector<int>;211 using ValueContainer = ThrowOnEraseContainer<int>;212 using M = std::flat_multimap<int, int, TransparentComparator, KeyContainer, ValueContainer>;213 214 KeyContainer a{1, 3, 3, 4};215 ValueContainer b{1, 3, 3, 4};216 M m(std::sorted_equivalent, std::move(a), std::move(b));217 try {218 erase_function(m, 3);219 assert(false);220 } catch (int) {221 check_invariant(m);222 // In libc++, we clear if anything goes wrong when erasing223 LIBCPP_ASSERT(m.size() == 0);224 }225 }226#endif227}228 229#endif // SUPPORT_FLAT_MULTIMAP_HELPERS_H230