v1/__flat_map/utils.h

0001 // -*- C++ -*-
0002 //===----------------------------------------------------------------------===//
0003 //
0004 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
0005 // See https://llvm.org/LICENSE.txt for license information.
0006 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
0007 //
0008 //===----------------------------------------------------------------------===//
0009
0010 #ifndef _LIBCPP___FLAT_MAP_UTILS_H
0011 #define _LIBCPP___FLAT_MAP_UTILS_H
0012
0013 #include <__config>
0014 #include <__type_traits/container_traits.h>
0015 #include <__utility/exception_guard.h>
0016 #include <__utility/forward.h>
0017 #include <__utility/move.h>
0018
0019 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
0020 #  pragma GCC system_header
0021 #endif
0022
0023 _LIBCPP_PUSH_MACROS
0024 #include <__undef_macros>
0025
0026 #if _LIBCPP_STD_VER >= 23
0027
0028 _LIBCPP_BEGIN_NAMESPACE_STD
0029
0030 // These utilities are defined in a class instead of a namespace so that this class can be befriended more easily.
0031 struct __flat_map_utils {
0032   // Emplace a {key: value} into a flat_{multi}map, at the exact position that
0033   // __it_key and __it_mapped point to, assuming that the key is not already present in the map.
0034   // When an exception is thrown during the emplacement, the function will try its best to
0035   // roll back the changes it made to the map. If it cannot roll back the changes, it will
0036   // clear the map.
0037   template <class _Map, class _IterK, class _IterM, class _KeyArg, class... _MArgs>
0038   _LIBCPP_HIDE_FROM_ABI static typename _Map::iterator __emplace_exact_pos(
0039       _Map& __map, _IterK&& __it_key, _IterM&& __it_mapped, _KeyArg&& __key, _MArgs&&... __mapped_args) {
0040     auto __on_key_failed = std::__make_exception_guard([&]() noexcept {
0041       using _KeyContainer = typename _Map::key_container_type;
0042       if constexpr (__container_traits<_KeyContainer>::__emplacement_has_strong_exception_safety_guarantee) {
0043         // Nothing to roll back!
0044       } else {
0045         // we need to clear both because we don't know the state of our keys anymore
0046         __map.clear() /* noexcept */;
0047       }
0048     });
0049     auto __key_it        = __map.__containers_.keys.emplace(__it_key, std::forward<_KeyArg>(__key));
0050     __on_key_failed.__complete();
0051
0052     auto __on_value_failed = std::__make_exception_guard([&]() noexcept {
0053       using _MappedContainer = typename _Map::mapped_container_type;
0054       if constexpr (!__container_traits<_MappedContainer>::__emplacement_has_strong_exception_safety_guarantee) {
0055         // we need to clear both because we don't know the state of our values anymore
0056         __map.clear() /* noexcept */;
0057       } else {
0058         // In this case, we know the values are just like before we attempted emplacement,
0059         // and we also know that the keys have been emplaced successfully. Just roll back the keys.
0060 #  if _LIBCPP_HAS_EXCEPTIONS
0061         try {
0062 #  endif // _LIBCPP_HAS_EXCEPTIONS
0063           __map.__containers_.keys.erase(__key_it);
0064 #  if _LIBCPP_HAS_EXCEPTIONS
0065         } catch (...) {
0066           // Now things are funky for real. We're failing to rollback the keys.
0067           // Just give up and clear the whole thing.
0068           //
0069           // Also, swallow the exception that happened during the rollback and let the
0070           // original value-emplacement exception propagate normally.
0071           __map.clear() /* noexcept */;
0072         }
0073 #  endif // _LIBCPP_HAS_EXCEPTIONS
0074       }
0075     });
0076     auto __mapped_it = __map.__containers_.values.emplace(__it_mapped, std::forward<_MArgs>(__mapped_args)...);
0077     __on_value_failed.__complete();
0078
0079     return typename _Map::iterator(std::move(__key_it), std::move(__mapped_it));
0080   }
0081
0082   // TODO: We could optimize this, see
0083   // https://github.com/llvm/llvm-project/issues/108624
0084   template <class _Map, class _InputIterator, class _Sentinel>
0085   _LIBCPP_HIDE_FROM_ABI static typename _Map::size_type
0086   __append(_Map& __map, _InputIterator __first, _Sentinel __last) {
0087     typename _Map::size_type __num_appended = 0;
0088     for (; __first != __last; ++__first) {
0089       typename _Map::value_type __kv = *__first;
0090       __map.__containers_.keys.insert(__map.__containers_.keys.end(), std::move(__kv.first));
0091       __map.__containers_.values.insert(__map.__containers_.values.end(), std::move(__kv.second));
0092       ++__num_appended;
0093     }
0094     return __num_appended;
0095   }
0096 };
0097 _LIBCPP_END_NAMESPACE_STD
0098
0099 #endif // _LIBCPP_STD_VER >= 23
0100
0101 _LIBCPP_POP_MACROS
0102
0103 #endif // #define _LIBCPP___FLAT_MAP_UTILS_H