master
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.
32struct __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>
39 _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
85 __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
98 __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