123 lines · c
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-exception7//8//===----------------------------------------------------------------------===//9 10#ifndef _LIBCPP___FLAT_MAP_UTILS_H11#define _LIBCPP___FLAT_MAP_UTILS_H12 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#include <__vector/container_traits.h>20 21#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)22# pragma GCC system_header23#endif24 25_LIBCPP_PUSH_MACROS26#include <__undef_macros>27 28#if _LIBCPP_STD_VER >= 2329 30_LIBCPP_BEGIN_NAMESPACE_STD31 32// These utilities are defined in a class instead of a namespace so that this class can be befriended more easily.33struct __flat_map_utils {34 // Emplace a {key: value} into a flat_{multi}map, at the exact position that35 // __it_key and __it_mapped point to, assuming that the key is not already present in the map.36 // When an exception is thrown during the emplacement, the function will try its best to37 // roll back the changes it made to the map. If it cannot roll back the changes, it will38 // clear the map.39 template <class _Map, class _IterK, class _IterM, class _KeyArg, class... _MArgs>40 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 static typename _Map::iterator __emplace_exact_pos(41 _Map& __map, _IterK&& __it_key, _IterM&& __it_mapped, _KeyArg&& __key, _MArgs&&... __mapped_args) {42 auto __on_key_failed = std::__make_exception_guard([&]() noexcept {43 using _KeyContainer = typename _Map::key_container_type;44 if constexpr (__container_traits<_KeyContainer>::__emplacement_has_strong_exception_safety_guarantee) {45 // Nothing to roll back!46 } else {47 // we need to clear both because we don't know the state of our keys anymore48 __map.clear() /* noexcept */;49 }50 });51 auto __key_it = __map.__containers_.keys.emplace(__it_key, std::forward<_KeyArg>(__key));52 __on_key_failed.__complete();53 54 auto __on_value_failed = std::__make_exception_guard([&]() noexcept {55 using _MappedContainer = typename _Map::mapped_container_type;56 if constexpr (!__container_traits<_MappedContainer>::__emplacement_has_strong_exception_safety_guarantee) {57 // we need to clear both because we don't know the state of our values anymore58 __map.clear() /* noexcept */;59 } else {60 // In this case, we know the values are just like before we attempted emplacement,61 // and we also know that the keys have been emplaced successfully. Just roll back the keys.62# if _LIBCPP_HAS_EXCEPTIONS63 try {64# endif // _LIBCPP_HAS_EXCEPTIONS65 __map.__containers_.keys.erase(__key_it);66# if _LIBCPP_HAS_EXCEPTIONS67 } catch (...) {68 // Now things are funky for real. We're failing to rollback the keys.69 // Just give up and clear the whole thing.70 //71 // Also, swallow the exception that happened during the rollback and let the72 // original value-emplacement exception propagate normally.73 __map.clear() /* noexcept */;74 }75# endif // _LIBCPP_HAS_EXCEPTIONS76 }77 });78 auto __mapped_it = __map.__containers_.values.emplace(__it_mapped, std::forward<_MArgs>(__mapped_args)...);79 __on_value_failed.__complete();80 81 return typename _Map::iterator(std::move(__key_it), std::move(__mapped_it));82 }83 84 template <class _Map, class _InputIterator, class _Sentinel>85 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 static typename _Map::size_type86 __append(_Map& __map, _InputIterator __first, _Sentinel __last) {87 typename _Map::size_type __num_appended = 0;88 for (; __first != __last; ++__first) {89 typename _Map::value_type __kv = *__first;90 __map.__containers_.keys.insert(__map.__containers_.keys.end(), std::move(__kv.first));91 __map.__containers_.values.insert(__map.__containers_.values.end(), std::move(__kv.second));92 ++__num_appended;93 }94 return __num_appended;95 }96 97 template <class _Map, class _InputIterator>98 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 static typename _Map::size_type99 __append(_Map& __map, _InputIterator __first, _InputIterator __last)100 requires __is_product_iterator_of_size<_InputIterator, 2>::value101 {102 auto __s1 = __map.__containers_.keys.size();103 __map.__containers_.keys.insert(104 __map.__containers_.keys.end(),105 __product_iterator_traits<_InputIterator>::template __get_iterator_element<0>(__first),106 __product_iterator_traits<_InputIterator>::template __get_iterator_element<0>(__last));107 108 __map.__containers_.values.insert(109 __map.__containers_.values.end(),110 __product_iterator_traits<_InputIterator>::template __get_iterator_element<1>(__first),111 __product_iterator_traits<_InputIterator>::template __get_iterator_element<1>(__last));112 113 return __map.__containers_.keys.size() - __s1;114 }115};116_LIBCPP_END_NAMESPACE_STD117 118#endif // _LIBCPP_STD_VER >= 23119 120_LIBCPP_POP_MACROS121 122#endif // #define _LIBCPP___FLAT_MAP_UTILS_H123