1 // -*- C++ -*- 2 //===----------------------------------------------------------------------===// 3 // 4 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 5 // See https://llvm.org/LICENSE.txt for license information. 6 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 7 // 8 //===----------------------------------------------------------------------===// 9 10 #ifndef _LIBCPP___FLAT_MAP_UTILS_H 11 #define _LIBCPP___FLAT_MAP_UTILS_H 12 13 #include <__config> 14 #include <__iterator/product_iterator.h> 15 #include <__type_traits/container_traits.h> 16 #include <__utility/exception_guard.h> 17 #include <__utility/forward.h> 18 #include <__utility/move.h> 19 20 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 21 # pragma GCC system_header 22 #endif 23 24 _LIBCPP_PUSH_MACROS 25 #include <__undef_macros> 26 27 #if _LIBCPP_STD_VER >= 23 28 29 _LIBCPP_BEGIN_NAMESPACE_STD 30 31 // These utilities are defined in a class instead of a namespace so that this class can be befriended more easily. 32 struct __flat_map_utils { 33 // Emplace a {key: value} into a flat_{multi}map, at the exact position that 34 // __it_key and __it_mapped point to, assuming that the key is not already present in the map. 35 // When an exception is thrown during the emplacement, the function will try its best to 36 // roll back the changes it made to the map. If it cannot roll back the changes, it will 37 // clear the map. 38 template <class _Map, class _IterK, class _IterM, class _KeyArg, class... _MArgs> __emplace_exact_pos__flat_map_utils39 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 static typename _Map::iterator __emplace_exact_pos( 40 _Map& __map, _IterK&& __it_key, _IterM&& __it_mapped, _KeyArg&& __key, _MArgs&&... __mapped_args) { 41 auto __on_key_failed = std::__make_exception_guard([&]() noexcept { 42 using _KeyContainer = typename _Map::key_container_type; 43 if constexpr (__container_traits<_KeyContainer>::__emplacement_has_strong_exception_safety_guarantee) { 44 // Nothing to roll back! 45 } else { 46 // we need to clear both because we don't know the state of our keys anymore 47 __map.clear() /* noexcept */; 48 } 49 }); 50 auto __key_it = __map.__containers_.keys.emplace(__it_key, std::forward<_KeyArg>(__key)); 51 __on_key_failed.__complete(); 52 53 auto __on_value_failed = std::__make_exception_guard([&]() noexcept { 54 using _MappedContainer = typename _Map::mapped_container_type; 55 if constexpr (!__container_traits<_MappedContainer>::__emplacement_has_strong_exception_safety_guarantee) { 56 // we need to clear both because we don't know the state of our values anymore 57 __map.clear() /* noexcept */; 58 } else { 59 // In this case, we know the values are just like before we attempted emplacement, 60 // and we also know that the keys have been emplaced successfully. Just roll back the keys. 61 # if _LIBCPP_HAS_EXCEPTIONS 62 try { 63 # endif // _LIBCPP_HAS_EXCEPTIONS 64 __map.__containers_.keys.erase(__key_it); 65 # if _LIBCPP_HAS_EXCEPTIONS 66 } catch (...) { 67 // Now things are funky for real. We're failing to rollback the keys. 68 // Just give up and clear the whole thing. 69 // 70 // Also, swallow the exception that happened during the rollback and let the 71 // original value-emplacement exception propagate normally. 72 __map.clear() /* noexcept */; 73 } 74 # endif // _LIBCPP_HAS_EXCEPTIONS 75 } 76 }); 77 auto __mapped_it = __map.__containers_.values.emplace(__it_mapped, std::forward<_MArgs>(__mapped_args)...); 78 __on_value_failed.__complete(); 79 80 return typename _Map::iterator(std::move(__key_it), std::move(__mapped_it)); 81 } 82 83 template <class _Map, class _InputIterator, class _Sentinel> 84 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 static typename _Map::size_type __append__flat_map_utils85 __append(_Map& __map, _InputIterator __first, _Sentinel __last) { 86 typename _Map::size_type __num_appended = 0; 87 for (; __first != __last; ++__first) { 88 typename _Map::value_type __kv = *__first; 89 __map.__containers_.keys.insert(__map.__containers_.keys.end(), std::move(__kv.first)); 90 __map.__containers_.values.insert(__map.__containers_.values.end(), std::move(__kv.second)); 91 ++__num_appended; 92 } 93 return __num_appended; 94 } 95 96 template <class _Map, class _InputIterator> 97 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 static typename _Map::size_type __append__flat_map_utils98 __append(_Map& __map, _InputIterator __first, _InputIterator __last) 99 requires __is_product_iterator_of_size<_InputIterator, 2>::value 100 { 101 auto __s1 = __map.__containers_.keys.size(); 102 __map.__containers_.keys.insert( 103 __map.__containers_.keys.end(), 104 __product_iterator_traits<_InputIterator>::template __get_iterator_element<0>(__first), 105 __product_iterator_traits<_InputIterator>::template __get_iterator_element<0>(__last)); 106 107 __map.__containers_.values.insert( 108 __map.__containers_.values.end(), 109 __product_iterator_traits<_InputIterator>::template __get_iterator_element<1>(__first), 110 __product_iterator_traits<_InputIterator>::template __get_iterator_element<1>(__last)); 111 112 return __map.__containers_.keys.size() - __s1; 113 } 114 }; 115 _LIBCPP_END_NAMESPACE_STD 116 117 #endif // _LIBCPP_STD_VER >= 23 118 119 _LIBCPP_POP_MACROS 120 121 #endif // #define _LIBCPP___FLAT_MAP_UTILS_H 122