diff options
| author | Daniel Baumann <daniel.baumann@progress-linux.org> | 2024-04-19 00:47:55 +0000 |
|---|---|---|
| committer | Daniel Baumann <daniel.baumann@progress-linux.org> | 2024-04-19 00:47:55 +0000 |
| commit | 26a029d407be480d791972afb5975cf62c9360a6 (patch) | |
| tree | f435a8308119effd964b339f76abb83a57c29483 /third_party/libwebrtc/rtc_base/containers | |
| parent | Initial commit. (diff) | |
| download | firefox-26a029d407be480d791972afb5975cf62c9360a6.tar.xz firefox-26a029d407be480d791972afb5975cf62c9360a6.zip | |
Adding upstream version 124.0.1.upstream/124.0.1
Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>
Diffstat (limited to 'third_party/libwebrtc/rtc_base/containers')
14 files changed, 4729 insertions, 0 deletions
diff --git a/third_party/libwebrtc/rtc_base/containers/BUILD.gn b/third_party/libwebrtc/rtc_base/containers/BUILD.gn new file mode 100644 index 0000000000..621b6122a3 --- /dev/null +++ b/third_party/libwebrtc/rtc_base/containers/BUILD.gn @@ -0,0 +1,56 @@ +# Copyright (c) 2021 The WebRTC project authors. All Rights Reserved. +# +# Use of this source code is governed by a BSD-style license +# that can be found in the LICENSE file in the root of the source +# tree. An additional intellectual property rights grant can be found +# in the file PATENTS. All contributing project authors may +# be found in the AUTHORS file in the root of the source tree. + +import("../../webrtc.gni") + +rtc_library("flat_containers_internal") { + sources = [ + "flat_tree.cc", + "flat_tree.h", + "identity.h", + "invoke.h", + "move_only_int.h", + ] + deps = [ + "..:checks", + "../system:no_unique_address", + ] + absl_deps = [ "//third_party/abseil-cpp/absl/algorithm:container" ] + visibility = [ ":*" ] +} + +rtc_source_set("flat_set") { + sources = [ "flat_set.h" ] + deps = [ ":flat_containers_internal" ] +} + +rtc_source_set("flat_map") { + sources = [ "flat_map.h" ] + deps = [ + ":flat_containers_internal", + "..:checks", + ] +} + +rtc_library("unittests") { + testonly = true + sources = [ + "flat_map_unittest.cc", + "flat_set_unittest.cc", + "flat_tree_unittest.cc", + ] + deps = [ + ":flat_containers_internal", + ":flat_map", + ":flat_set", + "../../test:test_support", + "//testing/gmock:gmock", + "//testing/gtest:gtest", + ] + absl_deps = [ "//third_party/abseil-cpp/absl/algorithm:container" ] +} diff --git a/third_party/libwebrtc/rtc_base/containers/flat_containers_internal_gn/moz.build b/third_party/libwebrtc/rtc_base/containers/flat_containers_internal_gn/moz.build new file mode 100644 index 0000000000..8fd59a6ce2 --- /dev/null +++ b/third_party/libwebrtc/rtc_base/containers/flat_containers_internal_gn/moz.build @@ -0,0 +1,225 @@ +# This Source Code Form is subject to the terms of the Mozilla Public +# License, v. 2.0. If a copy of the MPL was not distributed with this +# file, You can obtain one at http://mozilla.org/MPL/2.0/. + + + ### This moz.build was AUTOMATICALLY GENERATED from a GN config, ### + ### DO NOT edit it by hand. ### + +COMPILE_FLAGS["OS_INCLUDES"] = [] +AllowCompilerWarnings() + +DEFINES["ABSL_ALLOCATOR_NOTHROW"] = "1" +DEFINES["RTC_DAV1D_IN_INTERNAL_DECODER_FACTORY"] = True +DEFINES["RTC_ENABLE_VP9"] = True +DEFINES["WEBRTC_ENABLE_PROTOBUF"] = "0" +DEFINES["WEBRTC_LIBRARY_IMPL"] = True +DEFINES["WEBRTC_MOZILLA_BUILD"] = True +DEFINES["WEBRTC_NON_STATIC_TRACE_EVENT_HANDLERS"] = "0" +DEFINES["WEBRTC_STRICT_FIELD_TRIALS"] = "0" + +FINAL_LIBRARY = "webrtc" + + +LOCAL_INCLUDES += [ + "!/ipc/ipdl/_ipdlheaders", + "!/third_party/libwebrtc/gen", + "/ipc/chromium/src", + "/third_party/libwebrtc/", + "/third_party/libwebrtc/third_party/abseil-cpp/", + "/tools/profiler/public" +] + +UNIFIED_SOURCES += [ + "/third_party/libwebrtc/rtc_base/containers/flat_tree.cc" +] + +if not CONFIG["MOZ_DEBUG"]: + + DEFINES["DYNAMIC_ANNOTATIONS_ENABLED"] = "0" + DEFINES["NDEBUG"] = True + DEFINES["NVALGRIND"] = True + +if CONFIG["MOZ_DEBUG"] == "1": + + DEFINES["DYNAMIC_ANNOTATIONS_ENABLED"] = "1" + +if CONFIG["OS_TARGET"] == "Android": + + DEFINES["ANDROID"] = True + DEFINES["ANDROID_NDK_VERSION_ROLL"] = "r22_1" + DEFINES["HAVE_SYS_UIO_H"] = True + DEFINES["WEBRTC_ANDROID"] = True + DEFINES["WEBRTC_ANDROID_OPENSLES"] = True + DEFINES["WEBRTC_ENABLE_LIBEVENT"] = True + DEFINES["WEBRTC_LINUX"] = True + DEFINES["WEBRTC_POSIX"] = True + DEFINES["_GNU_SOURCE"] = True + DEFINES["__STDC_CONSTANT_MACROS"] = True + DEFINES["__STDC_FORMAT_MACROS"] = True + + OS_LIBS += [ + "log" + ] + +if CONFIG["OS_TARGET"] == "Darwin": + + DEFINES["WEBRTC_MAC"] = True + DEFINES["WEBRTC_POSIX"] = True + DEFINES["_LIBCPP_HAS_NO_ALIGNED_ALLOCATION"] = True + DEFINES["__ASSERT_MACROS_DEFINE_VERSIONS_WITHOUT_UNDERSCORES"] = "0" + DEFINES["__STDC_CONSTANT_MACROS"] = True + DEFINES["__STDC_FORMAT_MACROS"] = True + +if CONFIG["OS_TARGET"] == "Linux": + + DEFINES["USE_AURA"] = "1" + DEFINES["USE_GLIB"] = "1" + DEFINES["USE_NSS_CERTS"] = "1" + DEFINES["USE_OZONE"] = "1" + DEFINES["USE_UDEV"] = True + DEFINES["WEBRTC_ENABLE_LIBEVENT"] = True + DEFINES["WEBRTC_LINUX"] = True + DEFINES["WEBRTC_POSIX"] = True + DEFINES["_FILE_OFFSET_BITS"] = "64" + DEFINES["_LARGEFILE64_SOURCE"] = True + DEFINES["_LARGEFILE_SOURCE"] = True + DEFINES["__STDC_CONSTANT_MACROS"] = True + DEFINES["__STDC_FORMAT_MACROS"] = True + +if CONFIG["OS_TARGET"] == "OpenBSD": + + DEFINES["USE_GLIB"] = "1" + DEFINES["USE_OZONE"] = "1" + DEFINES["USE_X11"] = "1" + DEFINES["WEBRTC_BSD"] = True + DEFINES["WEBRTC_ENABLE_LIBEVENT"] = True + DEFINES["WEBRTC_POSIX"] = True + DEFINES["_FILE_OFFSET_BITS"] = "64" + DEFINES["_LARGEFILE64_SOURCE"] = True + DEFINES["_LARGEFILE_SOURCE"] = True + DEFINES["__STDC_CONSTANT_MACROS"] = True + DEFINES["__STDC_FORMAT_MACROS"] = True + +if CONFIG["OS_TARGET"] == "WINNT": + + DEFINES["CERT_CHAIN_PARA_HAS_EXTRA_FIELDS"] = True + DEFINES["NOMINMAX"] = True + DEFINES["NTDDI_VERSION"] = "0x0A000000" + DEFINES["PSAPI_VERSION"] = "2" + DEFINES["RTC_ENABLE_WIN_WGC"] = True + DEFINES["UNICODE"] = True + DEFINES["USE_AURA"] = "1" + DEFINES["WEBRTC_WIN"] = True + DEFINES["WIN32"] = True + DEFINES["WIN32_LEAN_AND_MEAN"] = True + DEFINES["WINAPI_FAMILY"] = "WINAPI_FAMILY_DESKTOP_APP" + DEFINES["WINVER"] = "0x0A00" + DEFINES["_ATL_NO_OPENGL"] = True + DEFINES["_CRT_RAND_S"] = True + DEFINES["_CRT_SECURE_NO_DEPRECATE"] = True + DEFINES["_ENABLE_EXTENDED_ALIGNED_STORAGE"] = True + DEFINES["_HAS_EXCEPTIONS"] = "0" + DEFINES["_HAS_NODISCARD"] = True + DEFINES["_SCL_SECURE_NO_DEPRECATE"] = True + DEFINES["_SECURE_ATL"] = True + DEFINES["_UNICODE"] = True + DEFINES["_WIN32_WINNT"] = "0x0A00" + DEFINES["_WINDOWS"] = True + DEFINES["__STD_C"] = True + +if CONFIG["TARGET_CPU"] == "aarch64": + + DEFINES["WEBRTC_ARCH_ARM64"] = True + DEFINES["WEBRTC_HAS_NEON"] = True + +if CONFIG["TARGET_CPU"] == "arm": + + CXXFLAGS += [ + "-mfpu=neon" + ] + + DEFINES["WEBRTC_ARCH_ARM"] = True + DEFINES["WEBRTC_ARCH_ARM_V7"] = True + DEFINES["WEBRTC_HAS_NEON"] = True + +if CONFIG["TARGET_CPU"] == "mips32": + + DEFINES["MIPS32_LE"] = True + DEFINES["MIPS_FPU_LE"] = True + DEFINES["_GNU_SOURCE"] = True + +if CONFIG["TARGET_CPU"] == "mips64": + + DEFINES["_GNU_SOURCE"] = True + +if CONFIG["TARGET_CPU"] == "x86": + + DEFINES["WEBRTC_ENABLE_AVX2"] = True + +if CONFIG["TARGET_CPU"] == "x86_64": + + DEFINES["WEBRTC_ENABLE_AVX2"] = True + +if CONFIG["MOZ_DEBUG"] == "1" and CONFIG["OS_TARGET"] == "Android": + + DEFINES["_DEBUG"] = True + +if CONFIG["MOZ_DEBUG"] == "1" and CONFIG["OS_TARGET"] == "Darwin": + + DEFINES["_DEBUG"] = True + +if CONFIG["MOZ_DEBUG"] == "1" and CONFIG["OS_TARGET"] == "Linux": + + DEFINES["_DEBUG"] = True + +if CONFIG["MOZ_DEBUG"] == "1" and CONFIG["OS_TARGET"] == "OpenBSD": + + DEFINES["_DEBUG"] = True + +if CONFIG["MOZ_DEBUG"] == "1" and CONFIG["OS_TARGET"] == "WINNT": + + DEFINES["_HAS_ITERATOR_DEBUGGING"] = "0" + +if CONFIG["MOZ_X11"] == "1" and CONFIG["OS_TARGET"] == "Linux": + + DEFINES["USE_X11"] = "1" + +if CONFIG["OS_TARGET"] == "Android" and CONFIG["TARGET_CPU"] == "arm": + + OS_LIBS += [ + "android_support", + "unwind" + ] + +if CONFIG["OS_TARGET"] == "Android" and CONFIG["TARGET_CPU"] == "x86": + + CXXFLAGS += [ + "-msse2" + ] + + OS_LIBS += [ + "android_support" + ] + +if CONFIG["OS_TARGET"] == "Linux" and CONFIG["TARGET_CPU"] == "aarch64": + + DEFINES["_GNU_SOURCE"] = True + +if CONFIG["OS_TARGET"] == "Linux" and CONFIG["TARGET_CPU"] == "arm": + + DEFINES["_GNU_SOURCE"] = True + +if CONFIG["OS_TARGET"] == "Linux" and CONFIG["TARGET_CPU"] == "x86": + + CXXFLAGS += [ + "-msse2" + ] + + DEFINES["_GNU_SOURCE"] = True + +if CONFIG["OS_TARGET"] == "Linux" and CONFIG["TARGET_CPU"] == "x86_64": + + DEFINES["_GNU_SOURCE"] = True + +Library("flat_containers_internal_gn") diff --git a/third_party/libwebrtc/rtc_base/containers/flat_map.h b/third_party/libwebrtc/rtc_base/containers/flat_map.h new file mode 100644 index 0000000000..d1f757f669 --- /dev/null +++ b/third_party/libwebrtc/rtc_base/containers/flat_map.h @@ -0,0 +1,374 @@ +/* + * Copyright (c) 2021 The WebRTC project authors. All Rights Reserved. + * + * Use of this source code is governed by a BSD-style license + * that can be found in the LICENSE file in the root of the source + * tree. An additional intellectual property rights grant can be found + * in the file PATENTS. All contributing project authors may + * be found in the AUTHORS file in the root of the source tree. + */ + +// This implementation is borrowed from Chromium. + +#ifndef RTC_BASE_CONTAINERS_FLAT_MAP_H_ +#define RTC_BASE_CONTAINERS_FLAT_MAP_H_ + +#include <functional> +#include <tuple> +#include <utility> +#include <vector> + +#include "rtc_base/checks.h" +#include "rtc_base/containers/flat_tree.h" // IWYU pragma: export + +namespace webrtc { + +namespace flat_containers_internal { + +// An implementation of the flat_tree GetKeyFromValue template parameter that +// extracts the key as the first element of a pair. +struct GetFirst { + template <class Key, class Mapped> + constexpr const Key& operator()(const std::pair<Key, Mapped>& p) const { + return p.first; + } +}; + +} // namespace flat_containers_internal + +// flat_map is a container with a std::map-like interface that stores its +// contents in a sorted container, by default a vector. +// +// Its implementation mostly tracks the corresponding standardization proposal +// https://wg21.link/P0429, except that the storage of keys and values is not +// split. +// +// PROS +// +// - Good memory locality. +// - Low overhead, especially for smaller maps. +// - Performance is good for more workloads than you might expect (see +// //base/containers/README.md in Chromium repository) +// - Supports C++14 map interface. +// +// CONS +// +// - Inserts and removals are O(n). +// +// IMPORTANT NOTES +// +// - Iterators are invalidated across mutations. This means that the following +// line of code has undefined behavior since adding a new element could +// resize the container, invalidating all iterators: +// container["new element"] = it.second; +// - If possible, construct a flat_map in one operation by inserting into +// a container and moving that container into the flat_map constructor. +// +// QUICK REFERENCE +// +// Most of the core functionality is inherited from flat_tree. Please see +// flat_tree.h for more details for most of these functions. As a quick +// reference, the functions available are: +// +// Constructors (inputs need not be sorted): +// flat_map(const flat_map&); +// flat_map(flat_map&&); +// flat_map(InputIterator first, InputIterator last, +// const Compare& compare = Compare()); +// flat_map(const container_type& items, +// const Compare& compare = Compare()); +// flat_map(container_type&& items, +// const Compare& compare = Compare()); // Re-use storage. +// flat_map(std::initializer_list<value_type> ilist, +// const Compare& comp = Compare()); +// +// Constructors (inputs need to be sorted): +// flat_map(sorted_unique_t, +// InputIterator first, InputIterator last, +// const Compare& compare = Compare()); +// flat_map(sorted_unique_t, +// const container_type& items, +// const Compare& compare = Compare()); +// flat_map(sorted_unique_t, +// container_type&& items, +// const Compare& compare = Compare()); // Re-use storage. +// flat_map(sorted_unique_t, +// std::initializer_list<value_type> ilist, +// const Compare& comp = Compare()); +// +// Assignment functions: +// flat_map& operator=(const flat_map&); +// flat_map& operator=(flat_map&&); +// flat_map& operator=(initializer_list<value_type>); +// +// Memory management functions: +// void reserve(size_t); +// size_t capacity() const; +// void shrink_to_fit(); +// +// Size management functions: +// void clear(); +// size_t size() const; +// size_t max_size() const; +// bool empty() const; +// +// Iterator functions: +// iterator begin(); +// const_iterator begin() const; +// const_iterator cbegin() const; +// iterator end(); +// const_iterator end() const; +// const_iterator cend() const; +// reverse_iterator rbegin(); +// const reverse_iterator rbegin() const; +// const_reverse_iterator crbegin() const; +// reverse_iterator rend(); +// const_reverse_iterator rend() const; +// const_reverse_iterator crend() const; +// +// Insert and accessor functions: +// mapped_type& operator[](const key_type&); +// mapped_type& operator[](key_type&&); +// mapped_type& at(const K&); +// const mapped_type& at(const K&) const; +// pair<iterator, bool> insert(const value_type&); +// pair<iterator, bool> insert(value_type&&); +// iterator insert(const_iterator hint, const value_type&); +// iterator insert(const_iterator hint, value_type&&); +// void insert(InputIterator first, InputIterator last); +// pair<iterator, bool> insert_or_assign(K&&, M&&); +// iterator insert_or_assign(const_iterator hint, K&&, M&&); +// pair<iterator, bool> emplace(Args&&...); +// iterator emplace_hint(const_iterator, Args&&...); +// pair<iterator, bool> try_emplace(K&&, Args&&...); +// iterator try_emplace(const_iterator hint, K&&, Args&&...); + +// Underlying type functions: +// container_type extract() &&; +// void replace(container_type&&); +// +// Erase functions: +// iterator erase(iterator); +// iterator erase(const_iterator); +// iterator erase(const_iterator first, const_iterator& last); +// template <class K> size_t erase(const K& key); +// +// Comparators (see std::map documentation). +// key_compare key_comp() const; +// value_compare value_comp() const; +// +// Search functions: +// template <typename K> size_t count(const K&) const; +// template <typename K> iterator find(const K&); +// template <typename K> const_iterator find(const K&) const; +// template <typename K> bool contains(const K&) const; +// template <typename K> pair<iterator, iterator> equal_range(const K&); +// template <typename K> iterator lower_bound(const K&); +// template <typename K> const_iterator lower_bound(const K&) const; +// template <typename K> iterator upper_bound(const K&); +// template <typename K> const_iterator upper_bound(const K&) const; +// +// General functions: +// void swap(flat_map&); +// +// Non-member operators: +// bool operator==(const flat_map&, const flat_map); +// bool operator!=(const flat_map&, const flat_map); +// bool operator<(const flat_map&, const flat_map); +// bool operator>(const flat_map&, const flat_map); +// bool operator>=(const flat_map&, const flat_map); +// bool operator<=(const flat_map&, const flat_map); +// +template <class Key, + class Mapped, + class Compare = std::less<>, + class Container = std::vector<std::pair<Key, Mapped>>> +class flat_map : public ::webrtc::flat_containers_internal::flat_tree< + Key, + flat_containers_internal::GetFirst, + Compare, + Container> { + private: + using tree = typename ::webrtc::flat_containers_internal:: + flat_tree<Key, flat_containers_internal::GetFirst, Compare, Container>; + + public: + using key_type = typename tree::key_type; + using mapped_type = Mapped; + using value_type = typename tree::value_type; + using reference = typename Container::reference; + using const_reference = typename Container::const_reference; + using size_type = typename Container::size_type; + using difference_type = typename Container::difference_type; + using iterator = typename tree::iterator; + using const_iterator = typename tree::const_iterator; + using reverse_iterator = typename tree::reverse_iterator; + using const_reverse_iterator = typename tree::const_reverse_iterator; + using container_type = typename tree::container_type; + + // -------------------------------------------------------------------------- + // Lifetime and assignments. + // + // Note: we explicitly bring operator= in because otherwise + // flat_map<...> x; + // x = {...}; + // Would first create a flat_map and then move assign it. This most likely + // would be optimized away but still affects our debug builds. + + using tree::tree; + using tree::operator=; + + // Out-of-bound calls to at() will CHECK. + template <class K> + mapped_type& at(const K& key); + template <class K> + const mapped_type& at(const K& key) const; + + // -------------------------------------------------------------------------- + // Map-specific insert operations. + // + // Normal insert() functions are inherited from flat_tree. + // + // Assume that every operation invalidates iterators and references. + // Insertion of one element can take O(size). + + mapped_type& operator[](const key_type& key); + mapped_type& operator[](key_type&& key); + + template <class K, class M> + std::pair<iterator, bool> insert_or_assign(K&& key, M&& obj); + template <class K, class M> + iterator insert_or_assign(const_iterator hint, K&& key, M&& obj); + + template <class K, class... Args> + std::enable_if_t<std::is_constructible<key_type, K&&>::value, + std::pair<iterator, bool>> + try_emplace(K&& key, Args&&... args); + + template <class K, class... Args> + std::enable_if_t<std::is_constructible<key_type, K&&>::value, iterator> + try_emplace(const_iterator hint, K&& key, Args&&... args); + + // -------------------------------------------------------------------------- + // General operations. + // + // Assume that swap invalidates iterators and references. + + void swap(flat_map& other) noexcept; + + friend void swap(flat_map& lhs, flat_map& rhs) noexcept { lhs.swap(rhs); } +}; + +// ---------------------------------------------------------------------------- +// Lookups. + +template <class Key, class Mapped, class Compare, class Container> +template <class K> +auto flat_map<Key, Mapped, Compare, Container>::at(const K& key) + -> mapped_type& { + iterator found = tree::find(key); + RTC_CHECK(found != tree::end()); + return found->second; +} + +template <class Key, class Mapped, class Compare, class Container> +template <class K> +auto flat_map<Key, Mapped, Compare, Container>::at(const K& key) const + -> const mapped_type& { + const_iterator found = tree::find(key); + RTC_CHECK(found != tree::cend()); + return found->second; +} + +// ---------------------------------------------------------------------------- +// Insert operations. + +template <class Key, class Mapped, class Compare, class Container> +auto flat_map<Key, Mapped, Compare, Container>::operator[](const key_type& key) + -> mapped_type& { + iterator found = tree::lower_bound(key); + if (found == tree::end() || tree::key_comp()(key, found->first)) + found = tree::unsafe_emplace(found, key, mapped_type()); + return found->second; +} + +template <class Key, class Mapped, class Compare, class Container> +auto flat_map<Key, Mapped, Compare, Container>::operator[](key_type&& key) + -> mapped_type& { + iterator found = tree::lower_bound(key); + if (found == tree::end() || tree::key_comp()(key, found->first)) + found = tree::unsafe_emplace(found, std::move(key), mapped_type()); + return found->second; +} + +template <class Key, class Mapped, class Compare, class Container> +template <class K, class M> +auto flat_map<Key, Mapped, Compare, Container>::insert_or_assign(K&& key, + M&& obj) + -> std::pair<iterator, bool> { + auto result = + tree::emplace_key_args(key, std::forward<K>(key), std::forward<M>(obj)); + if (!result.second) + result.first->second = std::forward<M>(obj); + return result; +} + +template <class Key, class Mapped, class Compare, class Container> +template <class K, class M> +auto flat_map<Key, Mapped, Compare, Container>::insert_or_assign( + const_iterator hint, + K&& key, + M&& obj) -> iterator { + auto result = tree::emplace_hint_key_args(hint, key, std::forward<K>(key), + std::forward<M>(obj)); + if (!result.second) + result.first->second = std::forward<M>(obj); + return result.first; +} + +template <class Key, class Mapped, class Compare, class Container> +template <class K, class... Args> +auto flat_map<Key, Mapped, Compare, Container>::try_emplace(K&& key, + Args&&... args) + -> std::enable_if_t<std::is_constructible<key_type, K&&>::value, + std::pair<iterator, bool>> { + return tree::emplace_key_args( + key, std::piecewise_construct, + std::forward_as_tuple(std::forward<K>(key)), + std::forward_as_tuple(std::forward<Args>(args)...)); +} + +template <class Key, class Mapped, class Compare, class Container> +template <class K, class... Args> +auto flat_map<Key, Mapped, Compare, Container>::try_emplace(const_iterator hint, + K&& key, + Args&&... args) + -> std::enable_if_t<std::is_constructible<key_type, K&&>::value, iterator> { + return tree::emplace_hint_key_args( + hint, key, std::piecewise_construct, + std::forward_as_tuple(std::forward<K>(key)), + std::forward_as_tuple(std::forward<Args>(args)...)) + .first; +} + +// ---------------------------------------------------------------------------- +// General operations. + +template <class Key, class Mapped, class Compare, class Container> +void flat_map<Key, Mapped, Compare, Container>::swap(flat_map& other) noexcept { + tree::swap(other); +} + +// Erases all elements that match predicate. It has O(size) complexity. +// +// flat_map<int, Timestamp> last_times; +// ... +// EraseIf(last_times, +// [&](const auto& element) { return now - element.second > kLimit; }); + +// NOLINTNEXTLINE(misc-unused-using-decls) +using ::webrtc::flat_containers_internal::EraseIf; + +} // namespace webrtc + +#endif // RTC_BASE_CONTAINERS_FLAT_MAP_H_ diff --git a/third_party/libwebrtc/rtc_base/containers/flat_map_gn/moz.build b/third_party/libwebrtc/rtc_base/containers/flat_map_gn/moz.build new file mode 100644 index 0000000000..164aae2969 --- /dev/null +++ b/third_party/libwebrtc/rtc_base/containers/flat_map_gn/moz.build @@ -0,0 +1,209 @@ +# This Source Code Form is subject to the terms of the Mozilla Public +# License, v. 2.0. If a copy of the MPL was not distributed with this +# file, You can obtain one at http://mozilla.org/MPL/2.0/. + + + ### This moz.build was AUTOMATICALLY GENERATED from a GN config, ### + ### DO NOT edit it by hand. ### + +COMPILE_FLAGS["OS_INCLUDES"] = [] +AllowCompilerWarnings() + +DEFINES["ABSL_ALLOCATOR_NOTHROW"] = "1" +DEFINES["RTC_DAV1D_IN_INTERNAL_DECODER_FACTORY"] = True +DEFINES["RTC_ENABLE_VP9"] = True +DEFINES["WEBRTC_ENABLE_PROTOBUF"] = "0" +DEFINES["WEBRTC_LIBRARY_IMPL"] = True +DEFINES["WEBRTC_MOZILLA_BUILD"] = True +DEFINES["WEBRTC_NON_STATIC_TRACE_EVENT_HANDLERS"] = "0" +DEFINES["WEBRTC_STRICT_FIELD_TRIALS"] = "0" + +FINAL_LIBRARY = "webrtc" + + +LOCAL_INCLUDES += [ + "!/ipc/ipdl/_ipdlheaders", + "!/third_party/libwebrtc/gen", + "/ipc/chromium/src", + "/third_party/libwebrtc/", + "/third_party/libwebrtc/third_party/abseil-cpp/", + "/tools/profiler/public" +] + +if not CONFIG["MOZ_DEBUG"]: + + DEFINES["DYNAMIC_ANNOTATIONS_ENABLED"] = "0" + DEFINES["NDEBUG"] = True + DEFINES["NVALGRIND"] = True + +if CONFIG["MOZ_DEBUG"] == "1": + + DEFINES["DYNAMIC_ANNOTATIONS_ENABLED"] = "1" + +if CONFIG["OS_TARGET"] == "Android": + + DEFINES["ANDROID"] = True + DEFINES["ANDROID_NDK_VERSION_ROLL"] = "r22_1" + DEFINES["HAVE_SYS_UIO_H"] = True + DEFINES["WEBRTC_ANDROID"] = True + DEFINES["WEBRTC_ANDROID_OPENSLES"] = True + DEFINES["WEBRTC_ENABLE_LIBEVENT"] = True + DEFINES["WEBRTC_LINUX"] = True + DEFINES["WEBRTC_POSIX"] = True + DEFINES["_GNU_SOURCE"] = True + DEFINES["__STDC_CONSTANT_MACROS"] = True + DEFINES["__STDC_FORMAT_MACROS"] = True + + OS_LIBS += [ + "log" + ] + +if CONFIG["OS_TARGET"] == "Darwin": + + DEFINES["WEBRTC_MAC"] = True + DEFINES["WEBRTC_POSIX"] = True + DEFINES["_LIBCPP_HAS_NO_ALIGNED_ALLOCATION"] = True + DEFINES["__ASSERT_MACROS_DEFINE_VERSIONS_WITHOUT_UNDERSCORES"] = "0" + DEFINES["__STDC_CONSTANT_MACROS"] = True + DEFINES["__STDC_FORMAT_MACROS"] = True + +if CONFIG["OS_TARGET"] == "Linux": + + DEFINES["USE_AURA"] = "1" + DEFINES["USE_GLIB"] = "1" + DEFINES["USE_NSS_CERTS"] = "1" + DEFINES["USE_OZONE"] = "1" + DEFINES["USE_UDEV"] = True + DEFINES["WEBRTC_ENABLE_LIBEVENT"] = True + DEFINES["WEBRTC_LINUX"] = True + DEFINES["WEBRTC_POSIX"] = True + DEFINES["_FILE_OFFSET_BITS"] = "64" + DEFINES["_LARGEFILE64_SOURCE"] = True + DEFINES["_LARGEFILE_SOURCE"] = True + DEFINES["__STDC_CONSTANT_MACROS"] = True + DEFINES["__STDC_FORMAT_MACROS"] = True + +if CONFIG["OS_TARGET"] == "OpenBSD": + + DEFINES["USE_GLIB"] = "1" + DEFINES["USE_OZONE"] = "1" + DEFINES["USE_X11"] = "1" + DEFINES["WEBRTC_BSD"] = True + DEFINES["WEBRTC_ENABLE_LIBEVENT"] = True + DEFINES["WEBRTC_POSIX"] = True + DEFINES["_FILE_OFFSET_BITS"] = "64" + DEFINES["_LARGEFILE64_SOURCE"] = True + DEFINES["_LARGEFILE_SOURCE"] = True + DEFINES["__STDC_CONSTANT_MACROS"] = True + DEFINES["__STDC_FORMAT_MACROS"] = True + +if CONFIG["OS_TARGET"] == "WINNT": + + DEFINES["CERT_CHAIN_PARA_HAS_EXTRA_FIELDS"] = True + DEFINES["NOMINMAX"] = True + DEFINES["NTDDI_VERSION"] = "0x0A000000" + DEFINES["PSAPI_VERSION"] = "2" + DEFINES["RTC_ENABLE_WIN_WGC"] = True + DEFINES["UNICODE"] = True + DEFINES["USE_AURA"] = "1" + DEFINES["WEBRTC_WIN"] = True + DEFINES["WIN32"] = True + DEFINES["WIN32_LEAN_AND_MEAN"] = True + DEFINES["WINAPI_FAMILY"] = "WINAPI_FAMILY_DESKTOP_APP" + DEFINES["WINVER"] = "0x0A00" + DEFINES["_ATL_NO_OPENGL"] = True + DEFINES["_CRT_RAND_S"] = True + DEFINES["_CRT_SECURE_NO_DEPRECATE"] = True + DEFINES["_ENABLE_EXTENDED_ALIGNED_STORAGE"] = True + DEFINES["_HAS_EXCEPTIONS"] = "0" + DEFINES["_HAS_NODISCARD"] = True + DEFINES["_SCL_SECURE_NO_DEPRECATE"] = True + DEFINES["_SECURE_ATL"] = True + DEFINES["_UNICODE"] = True + DEFINES["_WIN32_WINNT"] = "0x0A00" + DEFINES["_WINDOWS"] = True + DEFINES["__STD_C"] = True + +if CONFIG["TARGET_CPU"] == "aarch64": + + DEFINES["WEBRTC_ARCH_ARM64"] = True + DEFINES["WEBRTC_HAS_NEON"] = True + +if CONFIG["TARGET_CPU"] == "arm": + + DEFINES["WEBRTC_ARCH_ARM"] = True + DEFINES["WEBRTC_ARCH_ARM_V7"] = True + DEFINES["WEBRTC_HAS_NEON"] = True + +if CONFIG["TARGET_CPU"] == "mips32": + + DEFINES["MIPS32_LE"] = True + DEFINES["MIPS_FPU_LE"] = True + DEFINES["_GNU_SOURCE"] = True + +if CONFIG["TARGET_CPU"] == "mips64": + + DEFINES["_GNU_SOURCE"] = True + +if CONFIG["TARGET_CPU"] == "x86": + + DEFINES["WEBRTC_ENABLE_AVX2"] = True + +if CONFIG["TARGET_CPU"] == "x86_64": + + DEFINES["WEBRTC_ENABLE_AVX2"] = True + +if CONFIG["MOZ_DEBUG"] == "1" and CONFIG["OS_TARGET"] == "Android": + + DEFINES["_DEBUG"] = True + +if CONFIG["MOZ_DEBUG"] == "1" and CONFIG["OS_TARGET"] == "Darwin": + + DEFINES["_DEBUG"] = True + +if CONFIG["MOZ_DEBUG"] == "1" and CONFIG["OS_TARGET"] == "Linux": + + DEFINES["_DEBUG"] = True + +if CONFIG["MOZ_DEBUG"] == "1" and CONFIG["OS_TARGET"] == "OpenBSD": + + DEFINES["_DEBUG"] = True + +if CONFIG["MOZ_DEBUG"] == "1" and CONFIG["OS_TARGET"] == "WINNT": + + DEFINES["_HAS_ITERATOR_DEBUGGING"] = "0" + +if CONFIG["MOZ_X11"] == "1" and CONFIG["OS_TARGET"] == "Linux": + + DEFINES["USE_X11"] = "1" + +if CONFIG["OS_TARGET"] == "Android" and CONFIG["TARGET_CPU"] == "arm": + + OS_LIBS += [ + "android_support", + "unwind" + ] + +if CONFIG["OS_TARGET"] == "Android" and CONFIG["TARGET_CPU"] == "x86": + + OS_LIBS += [ + "android_support" + ] + +if CONFIG["OS_TARGET"] == "Linux" and CONFIG["TARGET_CPU"] == "aarch64": + + DEFINES["_GNU_SOURCE"] = True + +if CONFIG["OS_TARGET"] == "Linux" and CONFIG["TARGET_CPU"] == "arm": + + DEFINES["_GNU_SOURCE"] = True + +if CONFIG["OS_TARGET"] == "Linux" and CONFIG["TARGET_CPU"] == "x86": + + DEFINES["_GNU_SOURCE"] = True + +if CONFIG["OS_TARGET"] == "Linux" and CONFIG["TARGET_CPU"] == "x86_64": + + DEFINES["_GNU_SOURCE"] = True + +Library("flat_map_gn") diff --git a/third_party/libwebrtc/rtc_base/containers/flat_map_unittest.cc b/third_party/libwebrtc/rtc_base/containers/flat_map_unittest.cc new file mode 100644 index 0000000000..98846a0206 --- /dev/null +++ b/third_party/libwebrtc/rtc_base/containers/flat_map_unittest.cc @@ -0,0 +1,455 @@ +/* + * Copyright (c) 2021 The WebRTC project authors. All Rights Reserved. + * + * Use of this source code is governed by a BSD-style license + * that can be found in the LICENSE file in the root of the source + * tree. An additional intellectual property rights grant can be found + * in the file PATENTS. All contributing project authors may + * be found in the AUTHORS file in the root of the source tree. + */ + +// This implementation is borrowed from Chromium. + +#include "rtc_base/containers/flat_map.h" + +#include <algorithm> +#include <string> +#include <type_traits> +#include <vector> + +#include "rtc_base/containers/move_only_int.h" +#include "test/gmock.h" +#include "test/gtest.h" + +// A flat_map is basically a interface to flat_tree. So several basic +// operations are tested to make sure things are set up properly, but the bulk +// of the tests are in flat_tree_unittests.cc. + +using ::testing::ElementsAre; + +namespace webrtc { + +namespace { + +struct Unsortable { + int value; +}; + +bool operator==(const Unsortable& lhs, const Unsortable& rhs) { + return lhs.value == rhs.value; +} + +bool operator<(const Unsortable& lhs, const Unsortable& rhs) = delete; +bool operator<=(const Unsortable& lhs, const Unsortable& rhs) = delete; +bool operator>(const Unsortable& lhs, const Unsortable& rhs) = delete; +bool operator>=(const Unsortable& lhs, const Unsortable& rhs) = delete; + +TEST(FlatMap, IncompleteType) { + struct A { + using Map = flat_map<A, A>; + int data; + Map set_with_incomplete_type; + Map::iterator it; + Map::const_iterator cit; + + // We do not declare operator< because clang complains that it's unused. + }; + + A a; +} + +TEST(FlatMap, RangeConstructor) { + flat_map<int, int>::value_type input_vals[] = { + {1, 1}, {1, 2}, {1, 3}, {2, 1}, {2, 2}, {2, 3}, {3, 1}, {3, 2}, {3, 3}}; + + flat_map<int, int> first(std::begin(input_vals), std::end(input_vals)); + EXPECT_THAT(first, ElementsAre(std::make_pair(1, 1), std::make_pair(2, 1), + std::make_pair(3, 1))); +} + +TEST(FlatMap, MoveConstructor) { + using pair = std::pair<MoveOnlyInt, MoveOnlyInt>; + + flat_map<MoveOnlyInt, MoveOnlyInt> original; + original.insert(pair(MoveOnlyInt(1), MoveOnlyInt(1))); + original.insert(pair(MoveOnlyInt(2), MoveOnlyInt(2))); + original.insert(pair(MoveOnlyInt(3), MoveOnlyInt(3))); + original.insert(pair(MoveOnlyInt(4), MoveOnlyInt(4))); + + flat_map<MoveOnlyInt, MoveOnlyInt> moved(std::move(original)); + + EXPECT_EQ(1U, moved.count(MoveOnlyInt(1))); + EXPECT_EQ(1U, moved.count(MoveOnlyInt(2))); + EXPECT_EQ(1U, moved.count(MoveOnlyInt(3))); + EXPECT_EQ(1U, moved.count(MoveOnlyInt(4))); +} + +TEST(FlatMap, VectorConstructor) { + using IntPair = std::pair<int, int>; + using IntMap = flat_map<int, int>; + std::vector<IntPair> vect{{1, 1}, {1, 2}, {2, 1}}; + IntMap map(std::move(vect)); + EXPECT_THAT(map, ElementsAre(IntPair(1, 1), IntPair(2, 1))); +} + +TEST(FlatMap, InitializerListConstructor) { + flat_map<int, int> cont( + {{1, 1}, {2, 2}, {3, 3}, {4, 4}, {5, 5}, {1, 2}, {10, 10}, {8, 8}}); + EXPECT_THAT(cont, ElementsAre(std::make_pair(1, 1), std::make_pair(2, 2), + std::make_pair(3, 3), std::make_pair(4, 4), + std::make_pair(5, 5), std::make_pair(8, 8), + std::make_pair(10, 10))); +} + +TEST(FlatMap, SortedRangeConstructor) { + using PairType = std::pair<int, Unsortable>; + using MapType = flat_map<int, Unsortable>; + MapType::value_type input_vals[] = {{1, {1}}, {2, {1}}, {3, {1}}}; + MapType map(sorted_unique, std::begin(input_vals), std::end(input_vals)); + EXPECT_THAT( + map, ElementsAre(PairType(1, {1}), PairType(2, {1}), PairType(3, {1}))); +} + +TEST(FlatMap, SortedCopyFromVectorConstructor) { + using PairType = std::pair<int, Unsortable>; + using MapType = flat_map<int, Unsortable>; + std::vector<PairType> vect{{1, {1}}, {2, {1}}}; + MapType map(sorted_unique, vect); + EXPECT_THAT(map, ElementsAre(PairType(1, {1}), PairType(2, {1}))); +} + +TEST(FlatMap, SortedMoveFromVectorConstructor) { + using PairType = std::pair<int, Unsortable>; + using MapType = flat_map<int, Unsortable>; + std::vector<PairType> vect{{1, {1}}, {2, {1}}}; + MapType map(sorted_unique, std::move(vect)); + EXPECT_THAT(map, ElementsAre(PairType(1, {1}), PairType(2, {1}))); +} + +TEST(FlatMap, SortedInitializerListConstructor) { + using PairType = std::pair<int, Unsortable>; + flat_map<int, Unsortable> map( + sorted_unique, + {{1, {1}}, {2, {2}}, {3, {3}}, {4, {4}}, {5, {5}}, {8, {8}}, {10, {10}}}); + EXPECT_THAT(map, + ElementsAre(PairType(1, {1}), PairType(2, {2}), PairType(3, {3}), + PairType(4, {4}), PairType(5, {5}), PairType(8, {8}), + PairType(10, {10}))); +} + +TEST(FlatMap, InitializerListAssignment) { + flat_map<int, int> cont; + cont = {{1, 1}, {2, 2}}; + EXPECT_THAT(cont, ElementsAre(std::make_pair(1, 1), std::make_pair(2, 2))); +} + +TEST(FlatMap, InsertFindSize) { + flat_map<int, int> s; + s.insert(std::make_pair(1, 1)); + s.insert(std::make_pair(1, 1)); + s.insert(std::make_pair(2, 2)); + + EXPECT_EQ(2u, s.size()); + EXPECT_EQ(std::make_pair(1, 1), *s.find(1)); + EXPECT_EQ(std::make_pair(2, 2), *s.find(2)); + EXPECT_EQ(s.end(), s.find(7)); +} + +TEST(FlatMap, CopySwap) { + flat_map<int, int> original; + original.insert({1, 1}); + original.insert({2, 2}); + EXPECT_THAT(original, + ElementsAre(std::make_pair(1, 1), std::make_pair(2, 2))); + + flat_map<int, int> copy(original); + EXPECT_THAT(copy, ElementsAre(std::make_pair(1, 1), std::make_pair(2, 2))); + + copy.erase(copy.begin()); + copy.insert({10, 10}); + EXPECT_THAT(copy, ElementsAre(std::make_pair(2, 2), std::make_pair(10, 10))); + + original.swap(copy); + EXPECT_THAT(original, + ElementsAre(std::make_pair(2, 2), std::make_pair(10, 10))); + EXPECT_THAT(copy, ElementsAre(std::make_pair(1, 1), std::make_pair(2, 2))); +} + +// operator[](const Key&) +TEST(FlatMap, SubscriptConstKey) { + flat_map<std::string, int> m; + + // Default construct elements that don't exist yet. + int& s = m["a"]; + EXPECT_EQ(0, s); + EXPECT_EQ(1u, m.size()); + + // The returned mapped reference should refer into the map. + s = 22; + EXPECT_EQ(22, m["a"]); + + // Overwrite existing elements. + m["a"] = 44; + EXPECT_EQ(44, m["a"]); +} + +// operator[](Key&&) +TEST(FlatMap, SubscriptMoveOnlyKey) { + flat_map<MoveOnlyInt, int> m; + + // Default construct elements that don't exist yet. + int& s = m[MoveOnlyInt(1)]; + EXPECT_EQ(0, s); + EXPECT_EQ(1u, m.size()); + + // The returned mapped reference should refer into the map. + s = 22; + EXPECT_EQ(22, m[MoveOnlyInt(1)]); + + // Overwrite existing elements. + m[MoveOnlyInt(1)] = 44; + EXPECT_EQ(44, m[MoveOnlyInt(1)]); +} + +// Mapped& at(const Key&) +// const Mapped& at(const Key&) const +TEST(FlatMap, AtFunction) { + flat_map<int, std::string> m = {{1, "a"}, {2, "b"}}; + + // Basic Usage. + EXPECT_EQ("a", m.at(1)); + EXPECT_EQ("b", m.at(2)); + + // Const reference works. + const std::string& const_ref = std::as_const(m).at(1); + EXPECT_EQ("a", const_ref); + + // Reference works, can operate on the string. + m.at(1)[0] = 'x'; + EXPECT_EQ("x", m.at(1)); + + // Out-of-bounds will CHECK. + EXPECT_DEATH_IF_SUPPORTED(m.at(-1), ""); + EXPECT_DEATH_IF_SUPPORTED({ m.at(-1)[0] = 'z'; }, ""); + + // Heterogeneous look-up works. + flat_map<std::string, int> m2 = {{"a", 1}, {"b", 2}}; + EXPECT_EQ(1, m2.at(absl::string_view("a"))); + EXPECT_EQ(2, std::as_const(m2).at(absl::string_view("b"))); +} + +// insert_or_assign(K&&, M&&) +TEST(FlatMap, InsertOrAssignMoveOnlyKey) { + flat_map<MoveOnlyInt, MoveOnlyInt> m; + + // Initial insertion should return an iterator to the element and set the + // second pair member to `true`. The inserted key and value should be moved + // from. + MoveOnlyInt key(1); + MoveOnlyInt val(22); + auto result = m.insert_or_assign(std::move(key), std::move(val)); + EXPECT_EQ(1, result.first->first.data()); + EXPECT_EQ(22, result.first->second.data()); + EXPECT_TRUE(result.second); + EXPECT_EQ(1u, m.size()); + EXPECT_EQ(0, key.data()); // moved from + EXPECT_EQ(0, val.data()); // moved from + + // Second call with same key should result in an assignment, overwriting the + // old value. Assignment should be indicated by setting the second pair member + // to `false`. Only the inserted value should be moved from, the key should be + // left intact. + key = MoveOnlyInt(1); + val = MoveOnlyInt(44); + result = m.insert_or_assign(std::move(key), std::move(val)); + EXPECT_EQ(1, result.first->first.data()); + EXPECT_EQ(44, result.first->second.data()); + EXPECT_FALSE(result.second); + EXPECT_EQ(1u, m.size()); + EXPECT_EQ(1, key.data()); // not moved from + EXPECT_EQ(0, val.data()); // moved from + + // Check that random insertion results in sorted range. + flat_map<MoveOnlyInt, int> map; + for (int i : {3, 1, 5, 6, 8, 7, 0, 9, 4, 2}) { + map.insert_or_assign(MoveOnlyInt(i), i); + EXPECT_TRUE(absl::c_is_sorted(map)); + } +} + +// insert_or_assign(const_iterator hint, K&&, M&&) +TEST(FlatMap, InsertOrAssignMoveOnlyKeyWithHint) { + flat_map<MoveOnlyInt, MoveOnlyInt> m; + + // Initial insertion should return an iterator to the element. The inserted + // key and value should be moved from. + MoveOnlyInt key(1); + MoveOnlyInt val(22); + auto result = m.insert_or_assign(m.end(), std::move(key), std::move(val)); + EXPECT_EQ(1, result->first.data()); + EXPECT_EQ(22, result->second.data()); + EXPECT_EQ(1u, m.size()); + EXPECT_EQ(0, key.data()); // moved from + EXPECT_EQ(0, val.data()); // moved from + + // Second call with same key should result in an assignment, overwriting the + // old value. Only the inserted value should be moved from, the key should be + // left intact. + key = MoveOnlyInt(1); + val = MoveOnlyInt(44); + result = m.insert_or_assign(m.end(), std::move(key), std::move(val)); + EXPECT_EQ(1, result->first.data()); + EXPECT_EQ(44, result->second.data()); + EXPECT_EQ(1u, m.size()); + EXPECT_EQ(1, key.data()); // not moved from + EXPECT_EQ(0, val.data()); // moved from + + // Check that random insertion results in sorted range. + flat_map<MoveOnlyInt, int> map; + for (int i : {3, 1, 5, 6, 8, 7, 0, 9, 4, 2}) { + map.insert_or_assign(map.end(), MoveOnlyInt(i), i); + EXPECT_TRUE(absl::c_is_sorted(map)); + } +} + +// try_emplace(K&&, Args&&...) +TEST(FlatMap, TryEmplaceMoveOnlyKey) { + flat_map<MoveOnlyInt, std::pair<MoveOnlyInt, MoveOnlyInt>> m; + + // Trying to emplace into an empty map should succeed. Insertion should return + // an iterator to the element and set the second pair member to `true`. The + // inserted key and value should be moved from. + MoveOnlyInt key(1); + MoveOnlyInt val1(22); + MoveOnlyInt val2(44); + // Test piecewise construction of mapped_type. + auto result = m.try_emplace(std::move(key), std::move(val1), std::move(val2)); + EXPECT_EQ(1, result.first->first.data()); + EXPECT_EQ(22, result.first->second.first.data()); + EXPECT_EQ(44, result.first->second.second.data()); + EXPECT_TRUE(result.second); + EXPECT_EQ(1u, m.size()); + EXPECT_EQ(0, key.data()); // moved from + EXPECT_EQ(0, val1.data()); // moved from + EXPECT_EQ(0, val2.data()); // moved from + + // Second call with same key should result in a no-op, returning an iterator + // to the existing element and returning false as the second pair member. + // Key and values that were attempted to be inserted should be left intact. + key = MoveOnlyInt(1); + auto paired_val = std::make_pair(MoveOnlyInt(33), MoveOnlyInt(55)); + // Test construction of mapped_type from pair. + result = m.try_emplace(std::move(key), std::move(paired_val)); + EXPECT_EQ(1, result.first->first.data()); + EXPECT_EQ(22, result.first->second.first.data()); + EXPECT_EQ(44, result.first->second.second.data()); + EXPECT_FALSE(result.second); + EXPECT_EQ(1u, m.size()); + EXPECT_EQ(1, key.data()); // not moved from + EXPECT_EQ(33, paired_val.first.data()); // not moved from + EXPECT_EQ(55, paired_val.second.data()); // not moved from + + // Check that random insertion results in sorted range. + flat_map<MoveOnlyInt, int> map; + for (int i : {3, 1, 5, 6, 8, 7, 0, 9, 4, 2}) { + map.try_emplace(MoveOnlyInt(i), i); + EXPECT_TRUE(absl::c_is_sorted(map)); + } +} + +// try_emplace(const_iterator hint, K&&, Args&&...) +TEST(FlatMap, TryEmplaceMoveOnlyKeyWithHint) { + flat_map<MoveOnlyInt, std::pair<MoveOnlyInt, MoveOnlyInt>> m; + + // Trying to emplace into an empty map should succeed. Insertion should return + // an iterator to the element. The inserted key and value should be moved + // from. + MoveOnlyInt key(1); + MoveOnlyInt val1(22); + MoveOnlyInt val2(44); + // Test piecewise construction of mapped_type. + auto result = + m.try_emplace(m.end(), std::move(key), std::move(val1), std::move(val2)); + EXPECT_EQ(1, result->first.data()); + EXPECT_EQ(22, result->second.first.data()); + EXPECT_EQ(44, result->second.second.data()); + EXPECT_EQ(1u, m.size()); + EXPECT_EQ(0, key.data()); // moved from + EXPECT_EQ(0, val1.data()); // moved from + EXPECT_EQ(0, val2.data()); // moved from + + // Second call with same key should result in a no-op, returning an iterator + // to the existing element. Key and values that were attempted to be inserted + // should be left intact. + key = MoveOnlyInt(1); + val1 = MoveOnlyInt(33); + val2 = MoveOnlyInt(55); + auto paired_val = std::make_pair(MoveOnlyInt(33), MoveOnlyInt(55)); + // Test construction of mapped_type from pair. + result = m.try_emplace(m.end(), std::move(key), std::move(paired_val)); + EXPECT_EQ(1, result->first.data()); + EXPECT_EQ(22, result->second.first.data()); + EXPECT_EQ(44, result->second.second.data()); + EXPECT_EQ(1u, m.size()); + EXPECT_EQ(1, key.data()); // not moved from + EXPECT_EQ(33, paired_val.first.data()); // not moved from + EXPECT_EQ(55, paired_val.second.data()); // not moved from + + // Check that random insertion results in sorted range. + flat_map<MoveOnlyInt, int> map; + for (int i : {3, 1, 5, 6, 8, 7, 0, 9, 4, 2}) { + map.try_emplace(map.end(), MoveOnlyInt(i), i); + EXPECT_TRUE(absl::c_is_sorted(map)); + } +} + +TEST(FlatMap, UsingTransparentCompare) { + using ExplicitInt = MoveOnlyInt; + flat_map<ExplicitInt, int> m; + const auto& m1 = m; + int x = 0; + + // Check if we can use lookup functions without converting to key_type. + // Correctness is checked in flat_tree tests. + m.count(x); + m1.count(x); + m.find(x); + m1.find(x); + m.equal_range(x); + m1.equal_range(x); + m.lower_bound(x); + m1.lower_bound(x); + m.upper_bound(x); + m1.upper_bound(x); + m.erase(x); + + // Check if we broke overload resolution. + m.emplace(ExplicitInt(0), 0); + m.emplace(ExplicitInt(1), 0); + m.erase(m.begin()); + m.erase(m.cbegin()); +} + +TEST(FlatMap, SupportsEraseIf) { + flat_map<MoveOnlyInt, MoveOnlyInt> m; + m.insert(std::make_pair(MoveOnlyInt(1), MoveOnlyInt(1))); + m.insert(std::make_pair(MoveOnlyInt(2), MoveOnlyInt(2))); + m.insert(std::make_pair(MoveOnlyInt(3), MoveOnlyInt(3))); + m.insert(std::make_pair(MoveOnlyInt(4), MoveOnlyInt(4))); + m.insert(std::make_pair(MoveOnlyInt(5), MoveOnlyInt(5))); + + EraseIf(m, [to_be_removed = MoveOnlyInt(2)]( + const std::pair<MoveOnlyInt, MoveOnlyInt>& e) { + return e.first == to_be_removed; + }); + + EXPECT_EQ(m.size(), 4u); + ASSERT_TRUE(m.find(MoveOnlyInt(1)) != m.end()); + ASSERT_FALSE(m.find(MoveOnlyInt(2)) != m.end()); + ASSERT_TRUE(m.find(MoveOnlyInt(3)) != m.end()); + ASSERT_TRUE(m.find(MoveOnlyInt(4)) != m.end()); + ASSERT_TRUE(m.find(MoveOnlyInt(5)) != m.end()); +} + +} // namespace +} // namespace webrtc diff --git a/third_party/libwebrtc/rtc_base/containers/flat_set.h b/third_party/libwebrtc/rtc_base/containers/flat_set.h new file mode 100644 index 0000000000..355690b09d --- /dev/null +++ b/third_party/libwebrtc/rtc_base/containers/flat_set.h @@ -0,0 +1,178 @@ +/* + * Copyright (c) 2021 The WebRTC project authors. All Rights Reserved. + * + * Use of this source code is governed by a BSD-style license + * that can be found in the LICENSE file in the root of the source + * tree. An additional intellectual property rights grant can be found + * in the file PATENTS. All contributing project authors may + * be found in the AUTHORS file in the root of the source tree. + */ + +// This implementation is borrowed from Chromium. + +#ifndef RTC_BASE_CONTAINERS_FLAT_SET_H_ +#define RTC_BASE_CONTAINERS_FLAT_SET_H_ + +#include <functional> +#include <vector> + +#include "rtc_base/containers/flat_tree.h" // IWYU pragma: export +#include "rtc_base/containers/identity.h" + +namespace webrtc { + +// flat_set is a container with a std::set-like interface that stores its +// contents in a sorted container, by default a vector. +// +// Its implementation mostly tracks the corresponding standardization proposal +// https://wg21.link/P1222. +// +// +// PROS +// +// - Good memory locality. +// - Low overhead, especially for smaller sets. +// - Performance is good for more workloads than you might expect (see +// //base/containers/README.md in Chromium repository) +// - Supports C++14 set interface. +// +// CONS +// +// - Inserts and removals are O(n). +// +// IMPORTANT NOTES +// +// - Iterators are invalidated across mutations. +// - If possible, construct a flat_set in one operation by inserting into +// a container and moving that container into the flat_set constructor. +// - For multiple removals use base::EraseIf() which is O(n) rather than +// O(n * removed_items). +// +// QUICK REFERENCE +// +// Most of the core functionality is inherited from flat_tree. Please see +// flat_tree.h for more details for most of these functions. As a quick +// reference, the functions available are: +// +// Constructors (inputs need not be sorted): +// flat_set(const flat_set&); +// flat_set(flat_set&&); +// flat_set(InputIterator first, InputIterator last, +// const Compare& compare = Compare()); +// flat_set(const container_type& items, +// const Compare& compare = Compare()); +// flat_set(container_type&& items, +// const Compare& compare = Compare()); // Re-use storage. +// flat_set(std::initializer_list<value_type> ilist, +// const Compare& comp = Compare()); +// +// Constructors (inputs need to be sorted): +// flat_set(sorted_unique_t, +// InputIterator first, InputIterator last, +// const Compare& compare = Compare()); +// flat_set(sorted_unique_t, +// const container_type& items, +// const Compare& compare = Compare()); +// flat_set(sorted_unique_t, +// container_type&& items, +// const Compare& compare = Compare()); // Re-use storage. +// flat_set(sorted_unique_t, +// std::initializer_list<value_type> ilist, +// const Compare& comp = Compare()); +// +// Assignment functions: +// flat_set& operator=(const flat_set&); +// flat_set& operator=(flat_set&&); +// flat_set& operator=(initializer_list<Key>); +// +// Memory management functions: +// void reserve(size_t); +// size_t capacity() const; +// void shrink_to_fit(); +// +// Size management functions: +// void clear(); +// size_t size() const; +// size_t max_size() const; +// bool empty() const; +// +// Iterator functions: +// iterator begin(); +// const_iterator begin() const; +// const_iterator cbegin() const; +// iterator end(); +// const_iterator end() const; +// const_iterator cend() const; +// reverse_iterator rbegin(); +// const reverse_iterator rbegin() const; +// const_reverse_iterator crbegin() const; +// reverse_iterator rend(); +// const_reverse_iterator rend() const; +// const_reverse_iterator crend() const; +// +// Insert and accessor functions: +// pair<iterator, bool> insert(const key_type&); +// pair<iterator, bool> insert(key_type&&); +// void insert(InputIterator first, InputIterator last); +// iterator insert(const_iterator hint, const key_type&); +// iterator insert(const_iterator hint, key_type&&); +// pair<iterator, bool> emplace(Args&&...); +// iterator emplace_hint(const_iterator, Args&&...); +// +// Underlying type functions: +// container_type extract() &&; +// void replace(container_type&&); +// +// Erase functions: +// iterator erase(iterator); +// iterator erase(const_iterator); +// iterator erase(const_iterator first, const_iterator& last); +// template <typename K> size_t erase(const K& key); +// +// Comparators (see std::set documentation). +// key_compare key_comp() const; +// value_compare value_comp() const; +// +// Search functions: +// template <typename K> size_t count(const K&) const; +// template <typename K> iterator find(const K&); +// template <typename K> const_iterator find(const K&) const; +// template <typename K> bool contains(const K&) const; +// template <typename K> pair<iterator, iterator> equal_range(K&); +// template <typename K> iterator lower_bound(const K&); +// template <typename K> const_iterator lower_bound(const K&) const; +// template <typename K> iterator upper_bound(const K&); +// template <typename K> const_iterator upper_bound(const K&) const; +// +// General functions: +// void swap(flat_set&); +// +// Non-member operators: +// bool operator==(const flat_set&, const flat_set); +// bool operator!=(const flat_set&, const flat_set); +// bool operator<(const flat_set&, const flat_set); +// bool operator>(const flat_set&, const flat_set); +// bool operator>=(const flat_set&, const flat_set); +// bool operator<=(const flat_set&, const flat_set); +// +template <class Key, + class Compare = std::less<>, + class Container = std::vector<Key>> +using flat_set = typename ::webrtc::flat_containers_internal:: + flat_tree<Key, webrtc::identity, Compare, Container>; + +// ---------------------------------------------------------------------------- +// General operations. + +// Erases all elements that match predicate. It has O(size) complexity. +// +// flat_set<int> numbers; +// ... +// EraseIf(numbers, [](int number) { return number % 2 == 1; }); + +// NOLINTNEXTLINE(misc-unused-using-decls) +using ::webrtc::flat_containers_internal::EraseIf; + +} // namespace webrtc + +#endif // RTC_BASE_CONTAINERS_FLAT_SET_H_ diff --git a/third_party/libwebrtc/rtc_base/containers/flat_set_gn/moz.build b/third_party/libwebrtc/rtc_base/containers/flat_set_gn/moz.build new file mode 100644 index 0000000000..5283c7e3d3 --- /dev/null +++ b/third_party/libwebrtc/rtc_base/containers/flat_set_gn/moz.build @@ -0,0 +1,209 @@ +# This Source Code Form is subject to the terms of the Mozilla Public +# License, v. 2.0. If a copy of the MPL was not distributed with this +# file, You can obtain one at http://mozilla.org/MPL/2.0/. + + + ### This moz.build was AUTOMATICALLY GENERATED from a GN config, ### + ### DO NOT edit it by hand. ### + +COMPILE_FLAGS["OS_INCLUDES"] = [] +AllowCompilerWarnings() + +DEFINES["ABSL_ALLOCATOR_NOTHROW"] = "1" +DEFINES["RTC_DAV1D_IN_INTERNAL_DECODER_FACTORY"] = True +DEFINES["RTC_ENABLE_VP9"] = True +DEFINES["WEBRTC_ENABLE_PROTOBUF"] = "0" +DEFINES["WEBRTC_LIBRARY_IMPL"] = True +DEFINES["WEBRTC_MOZILLA_BUILD"] = True +DEFINES["WEBRTC_NON_STATIC_TRACE_EVENT_HANDLERS"] = "0" +DEFINES["WEBRTC_STRICT_FIELD_TRIALS"] = "0" + +FINAL_LIBRARY = "webrtc" + + +LOCAL_INCLUDES += [ + "!/ipc/ipdl/_ipdlheaders", + "!/third_party/libwebrtc/gen", + "/ipc/chromium/src", + "/third_party/libwebrtc/", + "/third_party/libwebrtc/third_party/abseil-cpp/", + "/tools/profiler/public" +] + +if not CONFIG["MOZ_DEBUG"]: + + DEFINES["DYNAMIC_ANNOTATIONS_ENABLED"] = "0" + DEFINES["NDEBUG"] = True + DEFINES["NVALGRIND"] = True + +if CONFIG["MOZ_DEBUG"] == "1": + + DEFINES["DYNAMIC_ANNOTATIONS_ENABLED"] = "1" + +if CONFIG["OS_TARGET"] == "Android": + + DEFINES["ANDROID"] = True + DEFINES["ANDROID_NDK_VERSION_ROLL"] = "r22_1" + DEFINES["HAVE_SYS_UIO_H"] = True + DEFINES["WEBRTC_ANDROID"] = True + DEFINES["WEBRTC_ANDROID_OPENSLES"] = True + DEFINES["WEBRTC_ENABLE_LIBEVENT"] = True + DEFINES["WEBRTC_LINUX"] = True + DEFINES["WEBRTC_POSIX"] = True + DEFINES["_GNU_SOURCE"] = True + DEFINES["__STDC_CONSTANT_MACROS"] = True + DEFINES["__STDC_FORMAT_MACROS"] = True + + OS_LIBS += [ + "log" + ] + +if CONFIG["OS_TARGET"] == "Darwin": + + DEFINES["WEBRTC_MAC"] = True + DEFINES["WEBRTC_POSIX"] = True + DEFINES["_LIBCPP_HAS_NO_ALIGNED_ALLOCATION"] = True + DEFINES["__ASSERT_MACROS_DEFINE_VERSIONS_WITHOUT_UNDERSCORES"] = "0" + DEFINES["__STDC_CONSTANT_MACROS"] = True + DEFINES["__STDC_FORMAT_MACROS"] = True + +if CONFIG["OS_TARGET"] == "Linux": + + DEFINES["USE_AURA"] = "1" + DEFINES["USE_GLIB"] = "1" + DEFINES["USE_NSS_CERTS"] = "1" + DEFINES["USE_OZONE"] = "1" + DEFINES["USE_UDEV"] = True + DEFINES["WEBRTC_ENABLE_LIBEVENT"] = True + DEFINES["WEBRTC_LINUX"] = True + DEFINES["WEBRTC_POSIX"] = True + DEFINES["_FILE_OFFSET_BITS"] = "64" + DEFINES["_LARGEFILE64_SOURCE"] = True + DEFINES["_LARGEFILE_SOURCE"] = True + DEFINES["__STDC_CONSTANT_MACROS"] = True + DEFINES["__STDC_FORMAT_MACROS"] = True + +if CONFIG["OS_TARGET"] == "OpenBSD": + + DEFINES["USE_GLIB"] = "1" + DEFINES["USE_OZONE"] = "1" + DEFINES["USE_X11"] = "1" + DEFINES["WEBRTC_BSD"] = True + DEFINES["WEBRTC_ENABLE_LIBEVENT"] = True + DEFINES["WEBRTC_POSIX"] = True + DEFINES["_FILE_OFFSET_BITS"] = "64" + DEFINES["_LARGEFILE64_SOURCE"] = True + DEFINES["_LARGEFILE_SOURCE"] = True + DEFINES["__STDC_CONSTANT_MACROS"] = True + DEFINES["__STDC_FORMAT_MACROS"] = True + +if CONFIG["OS_TARGET"] == "WINNT": + + DEFINES["CERT_CHAIN_PARA_HAS_EXTRA_FIELDS"] = True + DEFINES["NOMINMAX"] = True + DEFINES["NTDDI_VERSION"] = "0x0A000000" + DEFINES["PSAPI_VERSION"] = "2" + DEFINES["RTC_ENABLE_WIN_WGC"] = True + DEFINES["UNICODE"] = True + DEFINES["USE_AURA"] = "1" + DEFINES["WEBRTC_WIN"] = True + DEFINES["WIN32"] = True + DEFINES["WIN32_LEAN_AND_MEAN"] = True + DEFINES["WINAPI_FAMILY"] = "WINAPI_FAMILY_DESKTOP_APP" + DEFINES["WINVER"] = "0x0A00" + DEFINES["_ATL_NO_OPENGL"] = True + DEFINES["_CRT_RAND_S"] = True + DEFINES["_CRT_SECURE_NO_DEPRECATE"] = True + DEFINES["_ENABLE_EXTENDED_ALIGNED_STORAGE"] = True + DEFINES["_HAS_EXCEPTIONS"] = "0" + DEFINES["_HAS_NODISCARD"] = True + DEFINES["_SCL_SECURE_NO_DEPRECATE"] = True + DEFINES["_SECURE_ATL"] = True + DEFINES["_UNICODE"] = True + DEFINES["_WIN32_WINNT"] = "0x0A00" + DEFINES["_WINDOWS"] = True + DEFINES["__STD_C"] = True + +if CONFIG["TARGET_CPU"] == "aarch64": + + DEFINES["WEBRTC_ARCH_ARM64"] = True + DEFINES["WEBRTC_HAS_NEON"] = True + +if CONFIG["TARGET_CPU"] == "arm": + + DEFINES["WEBRTC_ARCH_ARM"] = True + DEFINES["WEBRTC_ARCH_ARM_V7"] = True + DEFINES["WEBRTC_HAS_NEON"] = True + +if CONFIG["TARGET_CPU"] == "mips32": + + DEFINES["MIPS32_LE"] = True + DEFINES["MIPS_FPU_LE"] = True + DEFINES["_GNU_SOURCE"] = True + +if CONFIG["TARGET_CPU"] == "mips64": + + DEFINES["_GNU_SOURCE"] = True + +if CONFIG["TARGET_CPU"] == "x86": + + DEFINES["WEBRTC_ENABLE_AVX2"] = True + +if CONFIG["TARGET_CPU"] == "x86_64": + + DEFINES["WEBRTC_ENABLE_AVX2"] = True + +if CONFIG["MOZ_DEBUG"] == "1" and CONFIG["OS_TARGET"] == "Android": + + DEFINES["_DEBUG"] = True + +if CONFIG["MOZ_DEBUG"] == "1" and CONFIG["OS_TARGET"] == "Darwin": + + DEFINES["_DEBUG"] = True + +if CONFIG["MOZ_DEBUG"] == "1" and CONFIG["OS_TARGET"] == "Linux": + + DEFINES["_DEBUG"] = True + +if CONFIG["MOZ_DEBUG"] == "1" and CONFIG["OS_TARGET"] == "OpenBSD": + + DEFINES["_DEBUG"] = True + +if CONFIG["MOZ_DEBUG"] == "1" and CONFIG["OS_TARGET"] == "WINNT": + + DEFINES["_HAS_ITERATOR_DEBUGGING"] = "0" + +if CONFIG["MOZ_X11"] == "1" and CONFIG["OS_TARGET"] == "Linux": + + DEFINES["USE_X11"] = "1" + +if CONFIG["OS_TARGET"] == "Android" and CONFIG["TARGET_CPU"] == "arm": + + OS_LIBS += [ + "android_support", + "unwind" + ] + +if CONFIG["OS_TARGET"] == "Android" and CONFIG["TARGET_CPU"] == "x86": + + OS_LIBS += [ + "android_support" + ] + +if CONFIG["OS_TARGET"] == "Linux" and CONFIG["TARGET_CPU"] == "aarch64": + + DEFINES["_GNU_SOURCE"] = True + +if CONFIG["OS_TARGET"] == "Linux" and CONFIG["TARGET_CPU"] == "arm": + + DEFINES["_GNU_SOURCE"] = True + +if CONFIG["OS_TARGET"] == "Linux" and CONFIG["TARGET_CPU"] == "x86": + + DEFINES["_GNU_SOURCE"] = True + +if CONFIG["OS_TARGET"] == "Linux" and CONFIG["TARGET_CPU"] == "x86_64": + + DEFINES["_GNU_SOURCE"] = True + +Library("flat_set_gn") diff --git a/third_party/libwebrtc/rtc_base/containers/flat_set_unittest.cc b/third_party/libwebrtc/rtc_base/containers/flat_set_unittest.cc new file mode 100644 index 0000000000..617db92440 --- /dev/null +++ b/third_party/libwebrtc/rtc_base/containers/flat_set_unittest.cc @@ -0,0 +1,149 @@ +/* + * Copyright (c) 2021 The WebRTC project authors. All Rights Reserved. + * + * Use of this source code is governed by a BSD-style license + * that can be found in the LICENSE file in the root of the source + * tree. An additional intellectual property rights grant can be found + * in the file PATENTS. All contributing project authors may + * be found in the AUTHORS file in the root of the source tree. + */ + +// This implementation is borrowed from Chromium. + +#include "rtc_base/containers/flat_set.h" + +#include <algorithm> +#include <string> +#include <utility> +#include <vector> + +#include "rtc_base/containers/move_only_int.h" +#include "test/gmock.h" +#include "test/gtest.h" + +// A flat_set is basically a interface to flat_tree. So several basic +// operations are tested to make sure things are set up properly, but the bulk +// of the tests are in flat_tree_unittests.cc. + +using ::testing::ElementsAre; + +namespace webrtc { +namespace { + +TEST(FlatSet, IncompleteType) { + struct A { + using Set = flat_set<A>; + int data; + Set set_with_incomplete_type; + Set::iterator it; + Set::const_iterator cit; + + // We do not declare operator< because clang complains that it's unused. + }; + + A a; +} + +TEST(FlatSet, RangeConstructor) { + flat_set<int>::value_type input_vals[] = {1, 1, 1, 2, 2, 2, 3, 3, 3}; + + flat_set<int> cont(std::begin(input_vals), std::end(input_vals)); + EXPECT_THAT(cont, ElementsAre(1, 2, 3)); +} + +TEST(FlatSet, MoveConstructor) { + int input_range[] = {1, 2, 3, 4}; + + flat_set<MoveOnlyInt> original(std::begin(input_range), + std::end(input_range)); + flat_set<MoveOnlyInt> moved(std::move(original)); + + EXPECT_EQ(1U, moved.count(MoveOnlyInt(1))); + EXPECT_EQ(1U, moved.count(MoveOnlyInt(2))); + EXPECT_EQ(1U, moved.count(MoveOnlyInt(3))); + EXPECT_EQ(1U, moved.count(MoveOnlyInt(4))); +} + +TEST(FlatSet, InitializerListConstructor) { + flat_set<int> cont({1, 2, 3, 4, 5, 6, 10, 8}); + EXPECT_THAT(cont, ElementsAre(1, 2, 3, 4, 5, 6, 8, 10)); +} + +TEST(FlatSet, InsertFindSize) { + flat_set<int> s; + s.insert(1); + s.insert(1); + s.insert(2); + + EXPECT_EQ(2u, s.size()); + EXPECT_EQ(1, *s.find(1)); + EXPECT_EQ(2, *s.find(2)); + EXPECT_EQ(s.end(), s.find(7)); +} + +TEST(FlatSet, CopySwap) { + flat_set<int> original; + original.insert(1); + original.insert(2); + EXPECT_THAT(original, ElementsAre(1, 2)); + + flat_set<int> copy(original); + EXPECT_THAT(copy, ElementsAre(1, 2)); + + copy.erase(copy.begin()); + copy.insert(10); + EXPECT_THAT(copy, ElementsAre(2, 10)); + + original.swap(copy); + EXPECT_THAT(original, ElementsAre(2, 10)); + EXPECT_THAT(copy, ElementsAre(1, 2)); +} + +TEST(FlatSet, UsingTransparentCompare) { + using ExplicitInt = webrtc::MoveOnlyInt; + flat_set<ExplicitInt> s; + const auto& s1 = s; + int x = 0; + + // Check if we can use lookup functions without converting to key_type. + // Correctness is checked in flat_tree tests. + s.count(x); + s1.count(x); + s.find(x); + s1.find(x); + s.equal_range(x); + s1.equal_range(x); + s.lower_bound(x); + s1.lower_bound(x); + s.upper_bound(x); + s1.upper_bound(x); + s.erase(x); + + // Check if we broke overload resolution. + s.emplace(0); + s.emplace(1); + s.erase(s.begin()); + s.erase(s.cbegin()); +} + +TEST(FlatSet, SupportsEraseIf) { + flat_set<MoveOnlyInt> s; + s.emplace(MoveOnlyInt(1)); + s.emplace(MoveOnlyInt(2)); + s.emplace(MoveOnlyInt(3)); + s.emplace(MoveOnlyInt(4)); + s.emplace(MoveOnlyInt(5)); + + EraseIf(s, [to_be_removed = MoveOnlyInt(2)](const MoveOnlyInt& elem) { + return elem == to_be_removed; + }); + + EXPECT_EQ(s.size(), 4u); + ASSERT_TRUE(s.find(MoveOnlyInt(1)) != s.end()); + ASSERT_FALSE(s.find(MoveOnlyInt(2)) != s.end()); + ASSERT_TRUE(s.find(MoveOnlyInt(3)) != s.end()); + ASSERT_TRUE(s.find(MoveOnlyInt(4)) != s.end()); + ASSERT_TRUE(s.find(MoveOnlyInt(5)) != s.end()); +} +} // namespace +} // namespace webrtc diff --git a/third_party/libwebrtc/rtc_base/containers/flat_tree.cc b/third_party/libwebrtc/rtc_base/containers/flat_tree.cc new file mode 100644 index 0000000000..9e86db191a --- /dev/null +++ b/third_party/libwebrtc/rtc_base/containers/flat_tree.cc @@ -0,0 +1,19 @@ +/* + * Copyright (c) 2021 The WebRTC project authors. All Rights Reserved. + * + * Use of this source code is governed by a BSD-style license + * that can be found in the LICENSE file in the root of the source + * tree. An additional intellectual property rights grant can be found + * in the file PATENTS. All contributing project authors may + * be found in the AUTHORS file in the root of the source tree. + */ + +// This implementation is borrowed from Chromium. + +#include "rtc_base/containers/flat_tree.h" + +namespace webrtc { + +sorted_unique_t sorted_unique; + +} // namespace webrtc diff --git a/third_party/libwebrtc/rtc_base/containers/flat_tree.h b/third_party/libwebrtc/rtc_base/containers/flat_tree.h new file mode 100644 index 0000000000..480784ced4 --- /dev/null +++ b/third_party/libwebrtc/rtc_base/containers/flat_tree.h @@ -0,0 +1,1099 @@ +/* + * Copyright (c) 2021 The WebRTC project authors. All Rights Reserved. + * + * Use of this source code is governed by a BSD-style license + * that can be found in the LICENSE file in the root of the source + * tree. An additional intellectual property rights grant can be found + * in the file PATENTS. All contributing project authors may + * be found in the AUTHORS file in the root of the source tree. + */ + +// This implementation is borrowed from Chromium. + +#ifndef RTC_BASE_CONTAINERS_FLAT_TREE_H_ +#define RTC_BASE_CONTAINERS_FLAT_TREE_H_ + +#include <algorithm> +#include <iterator> +#include <type_traits> +#include <utility> +#include <vector> + +#include "absl/algorithm/container.h" +#include "rtc_base/checks.h" +#include "rtc_base/system/no_unique_address.h" + +namespace webrtc { +// Tag type that allows skipping the sort_and_unique step when constructing a +// flat_tree in case the underlying container is already sorted and has no +// duplicate elements. +struct sorted_unique_t { + constexpr sorted_unique_t() = default; +}; +extern sorted_unique_t sorted_unique; + +namespace flat_containers_internal { + +// Helper functions used in RTC_DCHECKs below to make sure that inputs tagged +// with sorted_unique are indeed sorted and unique. +template <typename Range, typename Comp> +constexpr bool is_sorted_and_unique(const Range& range, Comp comp) { + // Being unique implies that there are no adjacent elements that + // compare equal. So this checks that each element is strictly less + // than the element after it. + return absl::c_adjacent_find(range, std::not_fn(comp)) == std::end(range); +} + +// This is a convenience trait inheriting from std::true_type if Iterator is at +// least a ForwardIterator and thus supports multiple passes over a range. +template <class Iterator> +using is_multipass = + std::is_base_of<std::forward_iterator_tag, + typename std::iterator_traits<Iterator>::iterator_category>; + +// Uses SFINAE to detect whether type has is_transparent member. +template <typename T, typename = void> +struct IsTransparentCompare : std::false_type {}; +template <typename T> +struct IsTransparentCompare<T, std::void_t<typename T::is_transparent>> + : std::true_type {}; + +// Helper inspired by C++20's std::to_array to convert a C-style array to a +// std::array. As opposed to the C++20 version this implementation does not +// provide an overload for rvalues and does not strip cv qualifers from the +// returned std::array::value_type. The returned value_type needs to be +// specified explicitly, allowing the construction of std::arrays with const +// elements. +// +// Reference: https://en.cppreference.com/w/cpp/container/array/to_array +template <typename U, typename T, size_t N, size_t... I> +constexpr std::array<U, N> ToArrayImpl(const T (&data)[N], + std::index_sequence<I...>) { + return {{data[I]...}}; +} + +template <typename U, typename T, size_t N> +constexpr std::array<U, N> ToArray(const T (&data)[N]) { + return ToArrayImpl<U>(data, std::make_index_sequence<N>()); +} + +// std::pair's operator= is not constexpr prior to C++20. Thus we need this +// small helper to invoke operator= on the .first and .second member explicitly. +template <typename T> +constexpr void Assign(T& lhs, T&& rhs) { + lhs = std::move(rhs); +} + +template <typename T, typename U> +constexpr void Assign(std::pair<T, U>& lhs, std::pair<T, U>&& rhs) { + Assign(lhs.first, std::move(rhs.first)); + Assign(lhs.second, std::move(rhs.second)); +} + +// constexpr swap implementation. std::swap is not constexpr prior to C++20. +template <typename T> +constexpr void Swap(T& lhs, T& rhs) { + T tmp = std::move(lhs); + Assign(lhs, std::move(rhs)); + Assign(rhs, std::move(tmp)); +} + +// constexpr prev implementation. std::prev is not constexpr prior to C++17. +template <typename BidirIt> +constexpr BidirIt Prev(BidirIt it) { + return --it; +} + +// constexpr next implementation. std::next is not constexpr prior to C++17. +template <typename InputIt> +constexpr InputIt Next(InputIt it) { + return ++it; +} + +// constexpr sort implementation. std::sort is not constexpr prior to C++20. +// While insertion sort has a quadratic worst case complexity, it was chosen +// because it has linear complexity for nearly sorted data, is stable, and +// simple to implement. +template <typename BidirIt, typename Compare> +constexpr void InsertionSort(BidirIt first, BidirIt last, const Compare& comp) { + if (first == last) + return; + + for (auto it = Next(first); it != last; ++it) { + for (auto curr = it; curr != first && comp(*curr, *Prev(curr)); --curr) + Swap(*curr, *Prev(curr)); + } +} + +// Implementation ------------------------------------------------------------- + +// Implementation for the sorted associative flat_set and flat_map using a +// sorted vector as the backing store. Do not use directly. +// +// The use of "value" in this is like std::map uses, meaning it's the thing +// contained (in the case of map it's a <Kay, Mapped> pair). The Key is how +// things are looked up. In the case of a set, Key == Value. In the case of +// a map, the Key is a component of a Value. +// +// The helper class GetKeyFromValue provides the means to extract a key from a +// value for comparison purposes. It should implement: +// const Key& operator()(const Value&). +template <class Key, class GetKeyFromValue, class KeyCompare, class Container> +class flat_tree { + public: + // -------------------------------------------------------------------------- + // Types. + // + using key_type = Key; + using key_compare = KeyCompare; + using value_type = typename Container::value_type; + + // Wraps the templated key comparison to compare values. + struct value_compare { + constexpr bool operator()(const value_type& left, + const value_type& right) const { + GetKeyFromValue extractor; + return comp(extractor(left), extractor(right)); + } + + RTC_NO_UNIQUE_ADDRESS key_compare comp; + }; + + using pointer = typename Container::pointer; + using const_pointer = typename Container::const_pointer; + using reference = typename Container::reference; + using const_reference = typename Container::const_reference; + using size_type = typename Container::size_type; + using difference_type = typename Container::difference_type; + using iterator = typename Container::iterator; + using const_iterator = typename Container::const_iterator; + using reverse_iterator = typename Container::reverse_iterator; + using const_reverse_iterator = typename Container::const_reverse_iterator; + using container_type = Container; + + // -------------------------------------------------------------------------- + // Lifetime. + // + // Constructors that take range guarantee O(N * log^2(N)) + O(N) complexity + // and take O(N * log(N)) + O(N) if extra memory is available (N is a range + // length). + // + // Assume that move constructors invalidate iterators and references. + // + // The constructors that take ranges, lists, and vectors do not require that + // the input be sorted. + // + // When passing the webrtc::sorted_unique tag as the first argument no sort + // and unique step takes places. This is useful if the underlying container + // already has the required properties. + + flat_tree() = default; + flat_tree(const flat_tree&) = default; + flat_tree(flat_tree&&) = default; + + explicit flat_tree(const key_compare& comp); + + template <class InputIterator> + flat_tree(InputIterator first, + InputIterator last, + const key_compare& comp = key_compare()); + + flat_tree(const container_type& items, + const key_compare& comp = key_compare()); + + explicit flat_tree(container_type&& items, + const key_compare& comp = key_compare()); + + flat_tree(std::initializer_list<value_type> ilist, + const key_compare& comp = key_compare()); + + template <class InputIterator> + flat_tree(sorted_unique_t, + InputIterator first, + InputIterator last, + const key_compare& comp = key_compare()); + + flat_tree(sorted_unique_t, + const container_type& items, + const key_compare& comp = key_compare()); + + constexpr flat_tree(sorted_unique_t, + container_type&& items, + const key_compare& comp = key_compare()); + + flat_tree(sorted_unique_t, + std::initializer_list<value_type> ilist, + const key_compare& comp = key_compare()); + + ~flat_tree() = default; + + // -------------------------------------------------------------------------- + // Assignments. + // + // Assume that move assignment invalidates iterators and references. + + flat_tree& operator=(const flat_tree&) = default; + flat_tree& operator=(flat_tree&&) = default; + // Takes the first if there are duplicates in the initializer list. + flat_tree& operator=(std::initializer_list<value_type> ilist); + + // -------------------------------------------------------------------------- + // Memory management. + // + // Beware that shrink_to_fit() simply forwards the request to the + // container_type and its implementation is free to optimize otherwise and + // leave capacity() to be greater that its size. + // + // reserve() and shrink_to_fit() invalidate iterators and references. + + void reserve(size_type new_capacity); + size_type capacity() const; + void shrink_to_fit(); + + // -------------------------------------------------------------------------- + // Size management. + // + // clear() leaves the capacity() of the flat_tree unchanged. + + void clear(); + + constexpr size_type size() const; + constexpr size_type max_size() const; + constexpr bool empty() const; + + // -------------------------------------------------------------------------- + // Iterators. + // + // Iterators follow the ordering defined by the key comparator used in + // construction of the flat_tree. + + iterator begin(); + constexpr const_iterator begin() const; + const_iterator cbegin() const; + + iterator end(); + constexpr const_iterator end() const; + const_iterator cend() const; + + reverse_iterator rbegin(); + const_reverse_iterator rbegin() const; + const_reverse_iterator crbegin() const; + + reverse_iterator rend(); + const_reverse_iterator rend() const; + const_reverse_iterator crend() const; + + // -------------------------------------------------------------------------- + // Insert operations. + // + // Assume that every operation invalidates iterators and references. + // Insertion of one element can take O(size). Capacity of flat_tree grows in + // an implementation-defined manner. + // + // NOTE: Prefer to build a new flat_tree from a std::vector (or similar) + // instead of calling insert() repeatedly. + + std::pair<iterator, bool> insert(const value_type& val); + std::pair<iterator, bool> insert(value_type&& val); + + iterator insert(const_iterator position_hint, const value_type& x); + iterator insert(const_iterator position_hint, value_type&& x); + + // This method inserts the values from the range [first, last) into the + // current tree. + template <class InputIterator> + void insert(InputIterator first, InputIterator last); + + template <class... Args> + std::pair<iterator, bool> emplace(Args&&... args); + + template <class... Args> + iterator emplace_hint(const_iterator position_hint, Args&&... args); + + // -------------------------------------------------------------------------- + // Underlying type operations. + // + // Assume that either operation invalidates iterators and references. + + // Extracts the container_type and returns it to the caller. Ensures that + // `this` is `empty()` afterwards. + container_type extract() &&; + + // Replaces the container_type with `body`. Expects that `body` is sorted + // and has no repeated elements with regard to value_comp(). + void replace(container_type&& body); + + // -------------------------------------------------------------------------- + // Erase operations. + // + // Assume that every operation invalidates iterators and references. + // + // erase(position), erase(first, last) can take O(size). + // erase(key) may take O(size) + O(log(size)). + // + // Prefer webrtc::EraseIf() or some other variation on erase(remove(), end()) + // idiom when deleting multiple non-consecutive elements. + + iterator erase(iterator position); + // Artificially templatized to break ambiguity if `iterator` and + // `const_iterator` are the same type. + template <typename DummyT = void> + iterator erase(const_iterator position); + iterator erase(const_iterator first, const_iterator last); + template <typename K> + size_type erase(const K& key); + + // -------------------------------------------------------------------------- + // Comparators. + + constexpr key_compare key_comp() const; + constexpr value_compare value_comp() const; + + // -------------------------------------------------------------------------- + // Search operations. + // + // Search operations have O(log(size)) complexity. + + template <typename K> + size_type count(const K& key) const; + + template <typename K> + iterator find(const K& key); + + template <typename K> + const_iterator find(const K& key) const; + + template <typename K> + bool contains(const K& key) const; + + template <typename K> + std::pair<iterator, iterator> equal_range(const K& key); + + template <typename K> + std::pair<const_iterator, const_iterator> equal_range(const K& key) const; + + template <typename K> + iterator lower_bound(const K& key); + + template <typename K> + const_iterator lower_bound(const K& key) const; + + template <typename K> + iterator upper_bound(const K& key); + + template <typename K> + const_iterator upper_bound(const K& key) const; + + // -------------------------------------------------------------------------- + // General operations. + // + // Assume that swap invalidates iterators and references. + // + // Implementation note: currently we use operator==() and operator<() on + // std::vector, because they have the same contract we need, so we use them + // directly for brevity and in case it is more optimal than calling equal() + // and lexicograhpical_compare(). If the underlying container type is changed, + // this code may need to be modified. + + void swap(flat_tree& other) noexcept; + + friend bool operator==(const flat_tree& lhs, const flat_tree& rhs) { + return lhs.body_ == rhs.body_; + } + + friend bool operator!=(const flat_tree& lhs, const flat_tree& rhs) { + return !(lhs == rhs); + } + + friend bool operator<(const flat_tree& lhs, const flat_tree& rhs) { + return lhs.body_ < rhs.body_; + } + + friend bool operator>(const flat_tree& lhs, const flat_tree& rhs) { + return rhs < lhs; + } + + friend bool operator>=(const flat_tree& lhs, const flat_tree& rhs) { + return !(lhs < rhs); + } + + friend bool operator<=(const flat_tree& lhs, const flat_tree& rhs) { + return !(lhs > rhs); + } + + friend void swap(flat_tree& lhs, flat_tree& rhs) noexcept { lhs.swap(rhs); } + + protected: + // Emplaces a new item into the tree that is known not to be in it. This + // is for implementing map operator[]. + template <class... Args> + iterator unsafe_emplace(const_iterator position, Args&&... args); + + // Attempts to emplace a new element with key `key`. Only if `key` is not yet + // present, construct value_type from `args` and insert it. Returns an + // iterator to the element with key `key` and a bool indicating whether an + // insertion happened. + template <class K, class... Args> + std::pair<iterator, bool> emplace_key_args(const K& key, Args&&... args); + + // Similar to `emplace_key_args`, but checks `hint` first as a possible + // insertion position. + template <class K, class... Args> + std::pair<iterator, bool> emplace_hint_key_args(const_iterator hint, + const K& key, + Args&&... args); + + private: + // Helper class for e.g. lower_bound that can compare a value on the left + // to a key on the right. + struct KeyValueCompare { + // The key comparison object must outlive this class. + explicit KeyValueCompare(const key_compare& comp) : comp_(comp) {} + + template <typename T, typename U> + bool operator()(const T& lhs, const U& rhs) const { + return comp_(extract_if_value_type(lhs), extract_if_value_type(rhs)); + } + + private: + const key_type& extract_if_value_type(const value_type& v) const { + GetKeyFromValue extractor; + return extractor(v); + } + + template <typename K> + const K& extract_if_value_type(const K& k) const { + return k; + } + + const key_compare& comp_; + }; + + iterator const_cast_it(const_iterator c_it) { + auto distance = std::distance(cbegin(), c_it); + return std::next(begin(), distance); + } + + // This method is inspired by both std::map::insert(P&&) and + // std::map::insert_or_assign(const K&, V&&). It inserts val if an equivalent + // element is not present yet, otherwise it overwrites. It returns an iterator + // to the modified element and a flag indicating whether insertion or + // assignment happened. + template <class V> + std::pair<iterator, bool> insert_or_assign(V&& val) { + auto position = lower_bound(GetKeyFromValue()(val)); + + if (position == end() || value_comp()(val, *position)) + return {body_.emplace(position, std::forward<V>(val)), true}; + + *position = std::forward<V>(val); + return {position, false}; + } + + // This method is similar to insert_or_assign, with the following differences: + // - Instead of searching [begin(), end()) it only searches [first, last). + // - In case no equivalent element is found, val is appended to the end of the + // underlying body and an iterator to the next bigger element in [first, + // last) is returned. + template <class V> + std::pair<iterator, bool> append_or_assign(iterator first, + iterator last, + V&& val) { + auto position = std::lower_bound(first, last, val, value_comp()); + + if (position == last || value_comp()(val, *position)) { + // emplace_back might invalidate position, which is why distance needs to + // be cached. + const difference_type distance = std::distance(begin(), position); + body_.emplace_back(std::forward<V>(val)); + return {std::next(begin(), distance), true}; + } + + *position = std::forward<V>(val); + return {position, false}; + } + + // This method is similar to insert, with the following differences: + // - Instead of searching [begin(), end()) it only searches [first, last). + // - In case no equivalent element is found, val is appended to the end of the + // underlying body and an iterator to the next bigger element in [first, + // last) is returned. + template <class V> + std::pair<iterator, bool> append_unique(iterator first, + iterator last, + V&& val) { + auto position = std::lower_bound(first, last, val, value_comp()); + + if (position == last || value_comp()(val, *position)) { + // emplace_back might invalidate position, which is why distance needs to + // be cached. + const difference_type distance = std::distance(begin(), position); + body_.emplace_back(std::forward<V>(val)); + return {std::next(begin(), distance), true}; + } + + return {position, false}; + } + + void sort_and_unique(iterator first, iterator last) { + // Preserve stability for the unique code below. + std::stable_sort(first, last, value_comp()); + + // lhs is already <= rhs due to sort, therefore !(lhs < rhs) <=> lhs == rhs. + auto equal_comp = std::not_fn(value_comp()); + erase(std::unique(first, last, equal_comp), last); + } + + void sort_and_unique() { sort_and_unique(begin(), end()); } + + // To support comparators that may not be possible to default-construct, we + // have to store an instance of Compare. Since Compare commonly is stateless, + // we use the RTC_NO_UNIQUE_ADDRESS attribute to save space. + RTC_NO_UNIQUE_ADDRESS key_compare comp_; + // Declare after `key_compare_comp_` to workaround GCC ICE. For details + // see https://crbug.com/1156268 + container_type body_; + + // If the compare is not transparent we want to construct key_type once. + template <typename K> + using KeyTypeOrK = typename std:: + conditional<IsTransparentCompare<key_compare>::value, K, key_type>::type; +}; + +// ---------------------------------------------------------------------------- +// Lifetime. + +template <class Key, class GetKeyFromValue, class KeyCompare, class Container> +flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::flat_tree( + const KeyCompare& comp) + : comp_(comp) {} + +template <class Key, class GetKeyFromValue, class KeyCompare, class Container> +template <class InputIterator> +flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::flat_tree( + InputIterator first, + InputIterator last, + const KeyCompare& comp) + : comp_(comp), body_(first, last) { + sort_and_unique(); +} + +template <class Key, class GetKeyFromValue, class KeyCompare, class Container> +flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::flat_tree( + const container_type& items, + const KeyCompare& comp) + : comp_(comp), body_(items) { + sort_and_unique(); +} + +template <class Key, class GetKeyFromValue, class KeyCompare, class Container> +flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::flat_tree( + container_type&& items, + const KeyCompare& comp) + : comp_(comp), body_(std::move(items)) { + sort_and_unique(); +} + +template <class Key, class GetKeyFromValue, class KeyCompare, class Container> +flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::flat_tree( + std::initializer_list<value_type> ilist, + const KeyCompare& comp) + : flat_tree(std::begin(ilist), std::end(ilist), comp) {} + +template <class Key, class GetKeyFromValue, class KeyCompare, class Container> +template <class InputIterator> +flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::flat_tree( + sorted_unique_t, + InputIterator first, + InputIterator last, + const KeyCompare& comp) + : comp_(comp), body_(first, last) { + RTC_DCHECK(is_sorted_and_unique(*this, value_comp())); +} + +template <class Key, class GetKeyFromValue, class KeyCompare, class Container> +flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::flat_tree( + sorted_unique_t, + const container_type& items, + const KeyCompare& comp) + : comp_(comp), body_(items) { + RTC_DCHECK(is_sorted_and_unique(*this, value_comp())); +} + +template <class Key, class GetKeyFromValue, class KeyCompare, class Container> +constexpr flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::flat_tree( + sorted_unique_t, + container_type&& items, + const KeyCompare& comp) + : comp_(comp), body_(std::move(items)) { + RTC_DCHECK(is_sorted_and_unique(*this, value_comp())); +} + +template <class Key, class GetKeyFromValue, class KeyCompare, class Container> +flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::flat_tree( + sorted_unique_t, + std::initializer_list<value_type> ilist, + const KeyCompare& comp) + : flat_tree(sorted_unique, std::begin(ilist), std::end(ilist), comp) {} + +// ---------------------------------------------------------------------------- +// Assignments. + +template <class Key, class GetKeyFromValue, class KeyCompare, class Container> +auto flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::operator=( + std::initializer_list<value_type> ilist) -> flat_tree& { + body_ = ilist; + sort_and_unique(); + return *this; +} + +// ---------------------------------------------------------------------------- +// Memory management. + +template <class Key, class GetKeyFromValue, class KeyCompare, class Container> +void flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::reserve( + size_type new_capacity) { + body_.reserve(new_capacity); +} + +template <class Key, class GetKeyFromValue, class KeyCompare, class Container> +auto flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::capacity() const + -> size_type { + return body_.capacity(); +} + +template <class Key, class GetKeyFromValue, class KeyCompare, class Container> +void flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::shrink_to_fit() { + body_.shrink_to_fit(); +} + +// ---------------------------------------------------------------------------- +// Size management. + +template <class Key, class GetKeyFromValue, class KeyCompare, class Container> +void flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::clear() { + body_.clear(); +} + +template <class Key, class GetKeyFromValue, class KeyCompare, class Container> +constexpr auto flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::size() + const -> size_type { + return body_.size(); +} + +template <class Key, class GetKeyFromValue, class KeyCompare, class Container> +constexpr auto +flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::max_size() const + -> size_type { + return body_.max_size(); +} + +template <class Key, class GetKeyFromValue, class KeyCompare, class Container> +constexpr bool flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::empty() + const { + return body_.empty(); +} + +// ---------------------------------------------------------------------------- +// Iterators. + +template <class Key, class GetKeyFromValue, class KeyCompare, class Container> +auto flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::begin() + -> iterator { + return body_.begin(); +} + +template <class Key, class GetKeyFromValue, class KeyCompare, class Container> +constexpr auto flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::begin() + const -> const_iterator { + return std::begin(body_); +} + +template <class Key, class GetKeyFromValue, class KeyCompare, class Container> +auto flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::cbegin() const + -> const_iterator { + return body_.cbegin(); +} + +template <class Key, class GetKeyFromValue, class KeyCompare, class Container> +auto flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::end() -> iterator { + return body_.end(); +} + +template <class Key, class GetKeyFromValue, class KeyCompare, class Container> +constexpr auto flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::end() + const -> const_iterator { + return std::end(body_); +} + +template <class Key, class GetKeyFromValue, class KeyCompare, class Container> +auto flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::cend() const + -> const_iterator { + return body_.cend(); +} + +template <class Key, class GetKeyFromValue, class KeyCompare, class Container> +auto flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::rbegin() + -> reverse_iterator { + return body_.rbegin(); +} + +template <class Key, class GetKeyFromValue, class KeyCompare, class Container> +auto flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::rbegin() const + -> const_reverse_iterator { + return body_.rbegin(); +} + +template <class Key, class GetKeyFromValue, class KeyCompare, class Container> +auto flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::crbegin() const + -> const_reverse_iterator { + return body_.crbegin(); +} + +template <class Key, class GetKeyFromValue, class KeyCompare, class Container> +auto flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::rend() + -> reverse_iterator { + return body_.rend(); +} + +template <class Key, class GetKeyFromValue, class KeyCompare, class Container> +auto flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::rend() const + -> const_reverse_iterator { + return body_.rend(); +} + +template <class Key, class GetKeyFromValue, class KeyCompare, class Container> +auto flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::crend() const + -> const_reverse_iterator { + return body_.crend(); +} + +// ---------------------------------------------------------------------------- +// Insert operations. +// +// Currently we use position_hint the same way as eastl or boost: +// https://github.com/electronicarts/EASTL/blob/master/include/EASTL/vector_set.h#L493 + +template <class Key, class GetKeyFromValue, class KeyCompare, class Container> +auto flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::insert( + const value_type& val) -> std::pair<iterator, bool> { + return emplace_key_args(GetKeyFromValue()(val), val); +} + +template <class Key, class GetKeyFromValue, class KeyCompare, class Container> +auto flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::insert( + value_type&& val) -> std::pair<iterator, bool> { + return emplace_key_args(GetKeyFromValue()(val), std::move(val)); +} + +template <class Key, class GetKeyFromValue, class KeyCompare, class Container> +auto flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::insert( + const_iterator position_hint, + const value_type& val) -> iterator { + return emplace_hint_key_args(position_hint, GetKeyFromValue()(val), val) + .first; +} + +template <class Key, class GetKeyFromValue, class KeyCompare, class Container> +auto flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::insert( + const_iterator position_hint, + value_type&& val) -> iterator { + return emplace_hint_key_args(position_hint, GetKeyFromValue()(val), + std::move(val)) + .first; +} + +template <class Key, class GetKeyFromValue, class KeyCompare, class Container> +template <class InputIterator> +void flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::insert( + InputIterator first, + InputIterator last) { + if (first == last) + return; + + // Dispatch to single element insert if the input range contains a single + // element. + if (is_multipass<InputIterator>() && std::next(first) == last) { + insert(end(), *first); + return; + } + + // Provide a convenience lambda to obtain an iterator pointing past the last + // old element. This needs to be dymanic due to possible re-allocations. + auto middle = [this, size = size()] { return std::next(begin(), size); }; + + // For batch updates initialize the first insertion point. + difference_type pos_first_new = size(); + + // Loop over the input range while appending new values and overwriting + // existing ones, if applicable. Keep track of the first insertion point. + for (; first != last; ++first) { + std::pair<iterator, bool> result = append_unique(begin(), middle(), *first); + if (result.second) { + pos_first_new = + std::min(pos_first_new, std::distance(begin(), result.first)); + } + } + + // The new elements might be unordered and contain duplicates, so post-process + // the just inserted elements and merge them with the rest, inserting them at + // the previously found spot. + sort_and_unique(middle(), end()); + std::inplace_merge(std::next(begin(), pos_first_new), middle(), end(), + value_comp()); +} + +template <class Key, class GetKeyFromValue, class KeyCompare, class Container> +template <class... Args> +auto flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::emplace( + Args&&... args) -> std::pair<iterator, bool> { + return insert(value_type(std::forward<Args>(args)...)); +} + +template <class Key, class GetKeyFromValue, class KeyCompare, class Container> +template <class... Args> +auto flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::emplace_hint( + const_iterator position_hint, + Args&&... args) -> iterator { + return insert(position_hint, value_type(std::forward<Args>(args)...)); +} + +// ---------------------------------------------------------------------------- +// Underlying type operations. + +template <class Key, class GetKeyFromValue, class KeyCompare, class Container> +auto flat_tree<Key, GetKeyFromValue, KeyCompare, Container>:: + extract() && -> container_type { + return std::exchange(body_, container_type()); +} + +template <class Key, class GetKeyFromValue, class KeyCompare, class Container> +void flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::replace( + container_type&& body) { + // Ensure that `body` is sorted and has no repeated elements according to + // `value_comp()`. + RTC_DCHECK(is_sorted_and_unique(body, value_comp())); + body_ = std::move(body); +} + +// ---------------------------------------------------------------------------- +// Erase operations. + +template <class Key, class GetKeyFromValue, class KeyCompare, class Container> +auto flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::erase( + iterator position) -> iterator { + RTC_CHECK(position != body_.end()); + return body_.erase(position); +} + +template <class Key, class GetKeyFromValue, class KeyCompare, class Container> +template <typename DummyT> +auto flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::erase( + const_iterator position) -> iterator { + RTC_CHECK(position != body_.end()); + return body_.erase(position); +} + +template <class Key, class GetKeyFromValue, class KeyCompare, class Container> +template <typename K> +auto flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::erase(const K& val) + -> size_type { + auto eq_range = equal_range(val); + auto res = std::distance(eq_range.first, eq_range.second); + erase(eq_range.first, eq_range.second); + return res; +} + +template <class Key, class GetKeyFromValue, class KeyCompare, class Container> +auto flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::erase( + const_iterator first, + const_iterator last) -> iterator { + return body_.erase(first, last); +} + +// ---------------------------------------------------------------------------- +// Comparators. + +template <class Key, class GetKeyFromValue, class KeyCompare, class Container> +constexpr auto +flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::key_comp() const + -> key_compare { + return comp_; +} + +template <class Key, class GetKeyFromValue, class KeyCompare, class Container> +constexpr auto +flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::value_comp() const + -> value_compare { + return value_compare{comp_}; +} + +// ---------------------------------------------------------------------------- +// Search operations. + +template <class Key, class GetKeyFromValue, class KeyCompare, class Container> +template <typename K> +auto flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::count( + const K& key) const -> size_type { + auto eq_range = equal_range(key); + return std::distance(eq_range.first, eq_range.second); +} + +template <class Key, class GetKeyFromValue, class KeyCompare, class Container> +template <typename K> +auto flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::find(const K& key) + -> iterator { + return const_cast_it(std::as_const(*this).find(key)); +} + +template <class Key, class GetKeyFromValue, class KeyCompare, class Container> +template <typename K> +auto flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::find( + const K& key) const -> const_iterator { + auto eq_range = equal_range(key); + return (eq_range.first == eq_range.second) ? end() : eq_range.first; +} + +template <class Key, class GetKeyFromValue, class KeyCompare, class Container> +template <typename K> +bool flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::contains( + const K& key) const { + auto lower = lower_bound(key); + return lower != end() && !comp_(key, GetKeyFromValue()(*lower)); +} + +template <class Key, class GetKeyFromValue, class KeyCompare, class Container> +template <typename K> +auto flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::equal_range( + const K& key) -> std::pair<iterator, iterator> { + auto res = std::as_const(*this).equal_range(key); + return {const_cast_it(res.first), const_cast_it(res.second)}; +} + +template <class Key, class GetKeyFromValue, class KeyCompare, class Container> +template <typename K> +auto flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::equal_range( + const K& key) const -> std::pair<const_iterator, const_iterator> { + auto lower = lower_bound(key); + + KeyValueCompare comp(comp_); + if (lower == end() || comp(key, *lower)) + return {lower, lower}; + + return {lower, std::next(lower)}; +} + +template <class Key, class GetKeyFromValue, class KeyCompare, class Container> +template <typename K> +auto flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::lower_bound( + const K& key) -> iterator { + return const_cast_it(std::as_const(*this).lower_bound(key)); +} + +template <class Key, class GetKeyFromValue, class KeyCompare, class Container> +template <typename K> +auto flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::lower_bound( + const K& key) const -> const_iterator { + static_assert(std::is_convertible<const KeyTypeOrK<K>&, const K&>::value, + "Requested type cannot be bound to the container's key_type " + "which is required for a non-transparent compare."); + + const KeyTypeOrK<K>& key_ref = key; + + KeyValueCompare comp(comp_); + return absl::c_lower_bound(*this, key_ref, comp); +} + +template <class Key, class GetKeyFromValue, class KeyCompare, class Container> +template <typename K> +auto flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::upper_bound( + const K& key) -> iterator { + return const_cast_it(std::as_const(*this).upper_bound(key)); +} + +template <class Key, class GetKeyFromValue, class KeyCompare, class Container> +template <typename K> +auto flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::upper_bound( + const K& key) const -> const_iterator { + static_assert(std::is_convertible<const KeyTypeOrK<K>&, const K&>::value, + "Requested type cannot be bound to the container's key_type " + "which is required for a non-transparent compare."); + + const KeyTypeOrK<K>& key_ref = key; + + KeyValueCompare comp(comp_); + return absl::c_upper_bound(*this, key_ref, comp); +} + +// ---------------------------------------------------------------------------- +// General operations. + +template <class Key, class GetKeyFromValue, class KeyCompare, class Container> +void flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::swap( + flat_tree& other) noexcept { + std::swap(*this, other); +} + +template <class Key, class GetKeyFromValue, class KeyCompare, class Container> +template <class... Args> +auto flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::unsafe_emplace( + const_iterator position, + Args&&... args) -> iterator { + return body_.emplace(position, std::forward<Args>(args)...); +} + +template <class Key, class GetKeyFromValue, class KeyCompare, class Container> +template <class K, class... Args> +auto flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::emplace_key_args( + const K& key, + Args&&... args) -> std::pair<iterator, bool> { + auto lower = lower_bound(key); + if (lower == end() || comp_(key, GetKeyFromValue()(*lower))) + return {unsafe_emplace(lower, std::forward<Args>(args)...), true}; + return {lower, false}; +} + +template <class Key, class GetKeyFromValue, class KeyCompare, class Container> +template <class K, class... Args> +auto flat_tree<Key, GetKeyFromValue, KeyCompare, Container>:: + emplace_hint_key_args(const_iterator hint, const K& key, Args&&... args) + -> std::pair<iterator, bool> { + KeyValueCompare comp(comp_); + if ((hint == begin() || comp(*std::prev(hint), key))) { + if (hint == end() || comp(key, *hint)) { + // *(hint - 1) < key < *hint => key did not exist and hint is correct. + return {unsafe_emplace(hint, std::forward<Args>(args)...), true}; + } + if (!comp(*hint, key)) { + // key == *hint => no-op, return correct hint. + return {const_cast_it(hint), false}; + } + } + // hint was not helpful, dispatch to hintless version. + return emplace_key_args(key, std::forward<Args>(args)...); +} + +// ---------------------------------------------------------------------------- +// Free functions. + +// Erases all elements that match predicate. It has O(size) complexity. +template <class Key, + class GetKeyFromValue, + class KeyCompare, + class Container, + typename Predicate> +size_t EraseIf( + webrtc::flat_containers_internal:: + flat_tree<Key, GetKeyFromValue, KeyCompare, Container>& container, + Predicate pred) { + auto it = std::remove_if(container.begin(), container.end(), + std::forward<Predicate>(pred)); + size_t removed = std::distance(it, container.end()); + container.erase(it, container.end()); + return removed; +} + +} // namespace flat_containers_internal +} // namespace webrtc + +#endif // RTC_BASE_CONTAINERS_FLAT_TREE_H_ diff --git a/third_party/libwebrtc/rtc_base/containers/flat_tree_unittest.cc b/third_party/libwebrtc/rtc_base/containers/flat_tree_unittest.cc new file mode 100644 index 0000000000..9bb803d16d --- /dev/null +++ b/third_party/libwebrtc/rtc_base/containers/flat_tree_unittest.cc @@ -0,0 +1,1484 @@ +/* + * Copyright (c) 2021 The WebRTC project authors. All Rights Reserved. + * + * Use of this source code is governed by a BSD-style license + * that can be found in the LICENSE file in the root of the source + * tree. An additional intellectual property rights grant can be found + * in the file PATENTS. All contributing project authors may + * be found in the AUTHORS file in the root of the source tree. + */ + +// This implementation is borrowed from Chromium. + +#include "rtc_base/containers/flat_tree.h" + +// Following tests are ported and extended tests from libcpp for std::set. +// They can be found here: +// https://github.com/llvm/llvm-project/tree/main/libcxx/test/std/containers/associative/set +// +// Not ported tests: +// * No tests with PrivateConstructor and std::less<> changed to std::less<T> +// These tests have to do with C++14 std::less<> +// http://en.cppreference.com/w/cpp/utility/functional/less_void +// and add support for templated versions of lookup functions. +// Because we use same implementation, we figured that it's OK just to check +// compilation and this is what we do in flat_set_unittest/flat_map_unittest. +// * No tests for max_size() +// Has to do with allocator support. +// * No tests with DefaultOnly. +// Standard containers allocate each element in the separate node on the heap +// and then manipulate these nodes. Flat containers store their elements in +// contiguous memory and move them around, type is required to be movable. +// * No tests for N3644. +// This proposal suggests that all default constructed iterators compare +// equal. Currently we use std::vector iterators and they don't implement +// this. +// * No tests with min_allocator and no tests counting allocations. +// Flat sets currently don't support allocators. + +#include <array> +#include <deque> +#include <forward_list> +#include <functional> +#include <iterator> +#include <list> +#include <string> +#include <vector> + +#include "rtc_base/containers/identity.h" +#include "rtc_base/containers/move_only_int.h" +#include "test/gmock.h" +#include "test/gtest.h" + +namespace webrtc { +namespace flat_containers_internal { +namespace { + +template <class It> +class InputIterator { + public: + using iterator_category = std::input_iterator_tag; + using value_type = typename std::iterator_traits<It>::value_type; + using difference_type = typename std::iterator_traits<It>::difference_type; + using pointer = It; + using reference = typename std::iterator_traits<It>::reference; + + InputIterator() : it_() {} + explicit InputIterator(It it) : it_(it) {} + + reference operator*() const { return *it_; } + pointer operator->() const { return it_; } + + InputIterator& operator++() { + ++it_; + return *this; + } + InputIterator operator++(int) { + InputIterator tmp(*this); + ++(*this); + return tmp; + } + + friend bool operator==(const InputIterator& lhs, const InputIterator& rhs) { + return lhs.it_ == rhs.it_; + } + friend bool operator!=(const InputIterator& lhs, const InputIterator& rhs) { + return !(lhs == rhs); + } + + private: + It it_; +}; + +template <typename It> +InputIterator<It> MakeInputIterator(It it) { + return InputIterator<It>(it); +} + +class Emplaceable { + public: + Emplaceable() : Emplaceable(0, 0.0) {} + Emplaceable(int i, double d) : int_(i), double_(d) {} + Emplaceable(Emplaceable&& other) : int_(other.int_), double_(other.double_) { + other.int_ = 0; + other.double_ = 0.0; + } + Emplaceable(const Emplaceable&) = delete; + Emplaceable& operator=(const Emplaceable&) = delete; + + Emplaceable& operator=(Emplaceable&& other) { + int_ = other.int_; + other.int_ = 0; + double_ = other.double_; + other.double_ = 0.0; + return *this; + } + + friend bool operator==(const Emplaceable& lhs, const Emplaceable& rhs) { + return std::tie(lhs.int_, lhs.double_) == std::tie(rhs.int_, rhs.double_); + } + + friend bool operator<(const Emplaceable& lhs, const Emplaceable& rhs) { + return std::tie(lhs.int_, lhs.double_) < std::tie(rhs.int_, rhs.double_); + } + + private: + int int_; + double double_; +}; + +struct TemplateConstructor { + template <typename T> + explicit TemplateConstructor(const T&) {} + + friend bool operator<(const TemplateConstructor&, + const TemplateConstructor&) { + return false; + } +}; + +class NonDefaultConstructibleCompare { + public: + explicit NonDefaultConstructibleCompare(int) {} + + template <typename T> + bool operator()(const T& lhs, const T& rhs) const { + return std::less<T>()(lhs, rhs); + } +}; + +template <class PairType> +struct LessByFirst { + bool operator()(const PairType& lhs, const PairType& rhs) const { + return lhs.first < rhs.first; + } +}; + +// Common test trees. +template <typename ContainerT> +using TypedTree = flat_tree<typename ContainerT::value_type, + identity, + std::less<>, + ContainerT>; +using IntTree = TypedTree<std::vector<int>>; +using IntPair = std::pair<int, int>; +using IntPairTree = + flat_tree<IntPair, identity, LessByFirst<IntPair>, std::vector<IntPair>>; +using MoveOnlyTree = + flat_tree<MoveOnlyInt, identity, std::less<>, std::vector<MoveOnlyInt>>; +using EmplaceableTree = + flat_tree<Emplaceable, identity, std::less<>, std::vector<Emplaceable>>; +using ReversedTree = + flat_tree<int, identity, std::greater<int>, std::vector<int>>; + +using TreeWithStrangeCompare = + flat_tree<int, identity, NonDefaultConstructibleCompare, std::vector<int>>; + +using ::testing::ElementsAre; +using ::testing::IsEmpty; + +template <typename T> +class FlatTreeTest : public testing::Test {}; +TYPED_TEST_SUITE_P(FlatTreeTest); + +TEST(FlatTree, IsMultipass) { + static_assert(!is_multipass<std::istream_iterator<int>>(), + "InputIterator is not multipass"); + static_assert(!is_multipass<std::ostream_iterator<int>>(), + "OutputIterator is not multipass"); + + static_assert(is_multipass<std::forward_list<int>::iterator>(), + "ForwardIterator is multipass"); + static_assert(is_multipass<std::list<int>::iterator>(), + "BidirectionalIterator is multipass"); + static_assert(is_multipass<std::vector<int>::iterator>(), + "RandomAccessIterator is multipass"); +} + +// Tests that the compiler generated move operators propagrate noexcept +// specifiers. +TEST(FlatTree, NoExcept) { + struct MoveThrows { + MoveThrows(MoveThrows&&) noexcept(false) {} + MoveThrows& operator=(MoveThrows&&) noexcept(false) { return *this; } + }; + + using MoveThrowsTree = + flat_tree<MoveThrows, identity, std::less<>, std::array<MoveThrows, 1>>; + + static_assert(std::is_nothrow_move_constructible<IntTree>::value, + "Error: IntTree is not nothrow move constructible"); + static_assert(std::is_nothrow_move_assignable<IntTree>::value, + "Error: IntTree is not nothrow move assignable"); + + static_assert(!std::is_nothrow_move_constructible<MoveThrowsTree>::value, + "Error: MoveThrowsTree is nothrow move constructible"); + static_assert(!std::is_nothrow_move_assignable<MoveThrowsTree>::value, + "Error: MoveThrowsTree is nothrow move assignable"); +} + +// ---------------------------------------------------------------------------- +// Class. + +// Check that flat_tree and its iterators can be instantiated with an +// incomplete type. + +TEST(FlatTree, IncompleteType) { + struct A { + using Tree = flat_tree<A, identity, std::less<A>, std::vector<A>>; + int data; + Tree set_with_incomplete_type; + Tree::iterator it; + Tree::const_iterator cit; + + // We do not declare operator< because clang complains that it's unused. + }; + + A a; +} + +TEST(FlatTree, Stability) { + using Pair = std::pair<int, int>; + + using Tree = flat_tree<Pair, identity, LessByFirst<Pair>, std::vector<Pair>>; + + // Constructors are stable. + Tree cont({{0, 0}, {1, 0}, {0, 1}, {2, 0}, {0, 2}, {1, 1}}); + + auto AllOfSecondsAreZero = [&cont] { + return absl::c_all_of(cont, + [](const Pair& elem) { return elem.second == 0; }); + }; + + EXPECT_TRUE(AllOfSecondsAreZero()) << "constructor should be stable"; + + // Should not replace existing. + cont.insert(Pair(0, 2)); + cont.insert(Pair(1, 2)); + cont.insert(Pair(2, 2)); + + EXPECT_TRUE(AllOfSecondsAreZero()) << "insert should be stable"; + + cont.insert(Pair(3, 0)); + cont.insert(Pair(3, 2)); + + EXPECT_TRUE(AllOfSecondsAreZero()) << "insert should be stable"; +} + +// ---------------------------------------------------------------------------- +// Types. + +// key_type +// key_compare +// value_type +// value_compare +// pointer +// const_pointer +// reference +// const_reference +// size_type +// difference_type +// iterator +// const_iterator +// reverse_iterator +// const_reverse_iterator + +TEST(FlatTree, Types) { + // These are guaranteed to be portable. + static_assert((std::is_same<int, IntTree::key_type>::value), ""); + static_assert((std::is_same<int, IntTree::value_type>::value), ""); + static_assert((std::is_same<std::less<>, IntTree::key_compare>::value), ""); + static_assert((std::is_same<int&, IntTree::reference>::value), ""); + static_assert((std::is_same<const int&, IntTree::const_reference>::value), + ""); + static_assert((std::is_same<int*, IntTree::pointer>::value), ""); + static_assert((std::is_same<const int*, IntTree::const_pointer>::value), ""); +} + +// ---------------------------------------------------------------------------- +// Lifetime. + +// flat_tree() +// flat_tree(const Compare& comp) + +TYPED_TEST_P(FlatTreeTest, DefaultConstructor) { + { + TypedTree<TypeParam> cont; + EXPECT_THAT(cont, ElementsAre()); + } + + { + TreeWithStrangeCompare cont(NonDefaultConstructibleCompare(0)); + EXPECT_THAT(cont, ElementsAre()); + } +} + +// flat_tree(const flat_tree& x) + +TYPED_TEST_P(FlatTreeTest, CopyConstructor) { + TypedTree<TypeParam> original({1, 2, 3, 4}); + TypedTree<TypeParam> copied(original); + + EXPECT_THAT(copied, ElementsAre(1, 2, 3, 4)); + + EXPECT_THAT(copied, ElementsAre(1, 2, 3, 4)); + EXPECT_THAT(original, ElementsAre(1, 2, 3, 4)); + EXPECT_EQ(original, copied); +} + +// flat_tree(flat_tree&& x) + +TEST(FlatTree, MoveConstructor) { + int input_range[] = {1, 2, 3, 4}; + + MoveOnlyTree original(std::begin(input_range), std::end(input_range)); + MoveOnlyTree moved(std::move(original)); + + EXPECT_EQ(1U, moved.count(MoveOnlyInt(1))); + EXPECT_EQ(1U, moved.count(MoveOnlyInt(2))); + EXPECT_EQ(1U, moved.count(MoveOnlyInt(3))); + EXPECT_EQ(1U, moved.count(MoveOnlyInt(4))); +} + +// flat_tree(InputIterator first, +// InputIterator last, +// const Compare& comp = Compare()) + +TEST(FlatTree, RangeConstructor) { + { + IntPair input_vals[] = {{1, 1}, {1, 2}, {2, 1}, {2, 2}, {1, 3}, + {2, 3}, {3, 1}, {3, 2}, {3, 3}}; + + IntPairTree first_of(MakeInputIterator(std::begin(input_vals)), + MakeInputIterator(std::end(input_vals))); + EXPECT_THAT(first_of, + ElementsAre(IntPair(1, 1), IntPair(2, 1), IntPair(3, 1))); + } + { + TreeWithStrangeCompare::value_type input_vals[] = {1, 1, 1, 2, 2, + 2, 3, 3, 3}; + + TreeWithStrangeCompare cont(MakeInputIterator(std::begin(input_vals)), + MakeInputIterator(std::end(input_vals)), + NonDefaultConstructibleCompare(0)); + EXPECT_THAT(cont, ElementsAre(1, 2, 3)); + } +} + +// flat_tree(const container_type&) + +TYPED_TEST_P(FlatTreeTest, ContainerCopyConstructor) { + TypeParam items = {1, 2, 3, 4}; + TypedTree<TypeParam> tree(items); + + EXPECT_THAT(tree, ElementsAre(1, 2, 3, 4)); + EXPECT_THAT(items, ElementsAre(1, 2, 3, 4)); +} + +// flat_tree(container_type&&) + +TEST(FlatTree, ContainerMoveConstructor) { + using Pair = std::pair<int, MoveOnlyInt>; + + // Construct an unsorted vector with a duplicate item in it. Sorted by the + // first item, the second allows us to test for stability. Using a move + // only type to ensure the vector is not copied. + std::vector<Pair> storage; + storage.push_back(Pair(2, MoveOnlyInt(0))); + storage.push_back(Pair(1, MoveOnlyInt(0))); + storage.push_back(Pair(2, MoveOnlyInt(1))); + + using Tree = flat_tree<Pair, identity, LessByFirst<Pair>, std::vector<Pair>>; + Tree tree(std::move(storage)); + + // The list should be two items long, with only the first "2" saved. + ASSERT_EQ(2u, tree.size()); + const Pair& zeroth = *tree.begin(); + ASSERT_EQ(1, zeroth.first); + ASSERT_EQ(0, zeroth.second.data()); + + const Pair& first = *(tree.begin() + 1); + ASSERT_EQ(2, first.first); + ASSERT_EQ(0, first.second.data()); +} + +// flat_tree(std::initializer_list<value_type> ilist, +// const Compare& comp = Compare()) + +TYPED_TEST_P(FlatTreeTest, InitializerListConstructor) { + { + TypedTree<TypeParam> cont({1, 2, 3, 4, 5, 6, 10, 8}); + EXPECT_THAT(cont, ElementsAre(1, 2, 3, 4, 5, 6, 8, 10)); + } + { + TypedTree<TypeParam> cont({1, 2, 3, 4, 5, 6, 10, 8}); + EXPECT_THAT(cont, ElementsAre(1, 2, 3, 4, 5, 6, 8, 10)); + } + { + TreeWithStrangeCompare cont({1, 2, 3, 4, 5, 6, 10, 8}, + NonDefaultConstructibleCompare(0)); + EXPECT_THAT(cont, ElementsAre(1, 2, 3, 4, 5, 6, 8, 10)); + } + { + IntPairTree first_of({{1, 1}, {2, 1}, {1, 2}}); + EXPECT_THAT(first_of, ElementsAre(IntPair(1, 1), IntPair(2, 1))); + } +} + +// flat_tree(sorted_unique_t, +// InputIterator first, +// InputIterator last, +// const Compare& comp = Compare()) + +TEST(FlatTree, SortedUniqueRangeConstructor) { + { + IntPair input_vals[] = {{1, 1}, {2, 1}, {3, 1}}; + + IntPairTree first_of(sorted_unique, + MakeInputIterator(std::begin(input_vals)), + MakeInputIterator(std::end(input_vals))); + EXPECT_THAT(first_of, + ElementsAre(IntPair(1, 1), IntPair(2, 1), IntPair(3, 1))); + } + { + TreeWithStrangeCompare::value_type input_vals[] = {1, 2, 3}; + + TreeWithStrangeCompare cont(sorted_unique, + MakeInputIterator(std::begin(input_vals)), + MakeInputIterator(std::end(input_vals)), + NonDefaultConstructibleCompare(0)); + EXPECT_THAT(cont, ElementsAre(1, 2, 3)); + } +} + +// flat_tree(sorted_unique_t, const container_type&) + +TYPED_TEST_P(FlatTreeTest, SortedUniqueContainerCopyConstructor) { + TypeParam items = {1, 2, 3, 4}; + TypedTree<TypeParam> tree(sorted_unique, items); + + EXPECT_THAT(tree, ElementsAre(1, 2, 3, 4)); + EXPECT_THAT(items, ElementsAre(1, 2, 3, 4)); +} + +// flat_tree(sorted_unique_t, std::vector<value_type>&&) + +TEST(FlatTree, SortedUniqueVectorMoveConstructor) { + using Pair = std::pair<int, MoveOnlyInt>; + + std::vector<Pair> storage; + storage.push_back(Pair(1, MoveOnlyInt(0))); + storage.push_back(Pair(2, MoveOnlyInt(0))); + + using Tree = flat_tree<Pair, identity, LessByFirst<Pair>, std::vector<Pair>>; + Tree tree(sorted_unique, std::move(storage)); + + ASSERT_EQ(2u, tree.size()); + const Pair& zeroth = *tree.begin(); + ASSERT_EQ(1, zeroth.first); + ASSERT_EQ(0, zeroth.second.data()); + + const Pair& first = *(tree.begin() + 1); + ASSERT_EQ(2, first.first); + ASSERT_EQ(0, first.second.data()); +} + +// flat_tree(sorted_unique_t, +// std::initializer_list<value_type> ilist, +// const Compare& comp = Compare()) + +TYPED_TEST_P(FlatTreeTest, SortedUniqueInitializerListConstructor) { + { + TypedTree<TypeParam> cont(sorted_unique, {1, 2, 3, 4, 5, 6, 8, 10}); + EXPECT_THAT(cont, ElementsAre(1, 2, 3, 4, 5, 6, 8, 10)); + } + { + TypedTree<TypeParam> cont(sorted_unique, {1, 2, 3, 4, 5, 6, 8, 10}); + EXPECT_THAT(cont, ElementsAre(1, 2, 3, 4, 5, 6, 8, 10)); + } + { + TreeWithStrangeCompare cont(sorted_unique, {1, 2, 3, 4, 5, 6, 8, 10}, + NonDefaultConstructibleCompare(0)); + EXPECT_THAT(cont, ElementsAre(1, 2, 3, 4, 5, 6, 8, 10)); + } + { + IntPairTree first_of(sorted_unique, {{1, 1}, {2, 1}}); + EXPECT_THAT(first_of, ElementsAre(IntPair(1, 1), IntPair(2, 1))); + } +} + +// ---------------------------------------------------------------------------- +// Assignments. + +// flat_tree& operator=(const flat_tree&) + +TYPED_TEST_P(FlatTreeTest, CopyAssignable) { + TypedTree<TypeParam> original({1, 2, 3, 4}); + TypedTree<TypeParam> copied; + copied = original; + + EXPECT_THAT(copied, ElementsAre(1, 2, 3, 4)); + EXPECT_THAT(original, ElementsAre(1, 2, 3, 4)); + EXPECT_EQ(original, copied); +} + +// flat_tree& operator=(flat_tree&&) + +TEST(FlatTree, MoveAssignable) { + int input_range[] = {1, 2, 3, 4}; + + MoveOnlyTree original(std::begin(input_range), std::end(input_range)); + MoveOnlyTree moved; + moved = std::move(original); + + EXPECT_EQ(1U, moved.count(MoveOnlyInt(1))); + EXPECT_EQ(1U, moved.count(MoveOnlyInt(2))); + EXPECT_EQ(1U, moved.count(MoveOnlyInt(3))); + EXPECT_EQ(1U, moved.count(MoveOnlyInt(4))); +} + +// flat_tree& operator=(std::initializer_list<value_type> ilist) + +TYPED_TEST_P(FlatTreeTest, InitializerListAssignable) { + TypedTree<TypeParam> cont({0}); + cont = {1, 2, 3, 4, 5, 6, 10, 8}; + + EXPECT_EQ(0U, cont.count(0)); + EXPECT_THAT(cont, ElementsAre(1, 2, 3, 4, 5, 6, 8, 10)); +} + +// -------------------------------------------------------------------------- +// Memory management. + +// void reserve(size_type new_capacity) + +TEST(FlatTreeTest, Reserve) { + IntTree cont({1, 2, 3}); + + cont.reserve(5); + EXPECT_LE(5U, cont.capacity()); +} + +// size_type capacity() const + +TEST(FlatTreeTest, Capacity) { + IntTree cont({1, 2, 3}); + + EXPECT_LE(cont.size(), cont.capacity()); + cont.reserve(5); + EXPECT_LE(cont.size(), cont.capacity()); +} + +// void shrink_to_fit() + +TEST(FlatTreeTest, ShrinkToFit) { + IntTree cont({1, 2, 3}); + + IntTree::size_type capacity_before = cont.capacity(); + cont.shrink_to_fit(); + EXPECT_GE(capacity_before, cont.capacity()); +} + +// ---------------------------------------------------------------------------- +// Size management. + +// void clear() + +TYPED_TEST_P(FlatTreeTest, Clear) { + TypedTree<TypeParam> cont({1, 2, 3, 4, 5, 6, 7, 8}); + cont.clear(); + EXPECT_THAT(cont, ElementsAre()); +} + +// size_type size() const + +TYPED_TEST_P(FlatTreeTest, Size) { + TypedTree<TypeParam> cont; + + EXPECT_EQ(0U, cont.size()); + cont.insert(2); + EXPECT_EQ(1U, cont.size()); + cont.insert(1); + EXPECT_EQ(2U, cont.size()); + cont.insert(3); + EXPECT_EQ(3U, cont.size()); + cont.erase(cont.begin()); + EXPECT_EQ(2U, cont.size()); + cont.erase(cont.begin()); + EXPECT_EQ(1U, cont.size()); + cont.erase(cont.begin()); + EXPECT_EQ(0U, cont.size()); +} + +// bool empty() const + +TYPED_TEST_P(FlatTreeTest, Empty) { + TypedTree<TypeParam> cont; + + EXPECT_TRUE(cont.empty()); + cont.insert(1); + EXPECT_FALSE(cont.empty()); + cont.clear(); + EXPECT_TRUE(cont.empty()); +} + +// ---------------------------------------------------------------------------- +// Iterators. + +// iterator begin() +// const_iterator begin() const +// iterator end() +// const_iterator end() const +// +// reverse_iterator rbegin() +// const_reverse_iterator rbegin() const +// reverse_iterator rend() +// const_reverse_iterator rend() const +// +// const_iterator cbegin() const +// const_iterator cend() const +// const_reverse_iterator crbegin() const +// const_reverse_iterator crend() const + +TYPED_TEST_P(FlatTreeTest, Iterators) { + TypedTree<TypeParam> cont({1, 2, 3, 4, 5, 6, 7, 8}); + + auto size = + static_cast<typename TypedTree<TypeParam>::difference_type>(cont.size()); + + EXPECT_EQ(size, std::distance(cont.begin(), cont.end())); + EXPECT_EQ(size, std::distance(cont.cbegin(), cont.cend())); + EXPECT_EQ(size, std::distance(cont.rbegin(), cont.rend())); + EXPECT_EQ(size, std::distance(cont.crbegin(), cont.crend())); + + { + auto it = cont.begin(); + auto c_it = cont.cbegin(); + EXPECT_EQ(it, c_it); + for (int j = 1; it != cont.end(); ++it, ++c_it, ++j) { + EXPECT_EQ(j, *it); + EXPECT_EQ(j, *c_it); + } + } + { + auto rit = cont.rbegin(); + auto c_rit = cont.crbegin(); + EXPECT_EQ(rit, c_rit); + for (int j = static_cast<int>(size); rit != cont.rend(); + ++rit, ++c_rit, --j) { + EXPECT_EQ(j, *rit); + EXPECT_EQ(j, *c_rit); + } + } +} + +// ---------------------------------------------------------------------------- +// Insert operations. + +// pair<iterator, bool> insert(const value_type& val) + +TYPED_TEST_P(FlatTreeTest, InsertLValue) { + TypedTree<TypeParam> cont; + + int value = 2; + std::pair<typename TypedTree<TypeParam>::iterator, bool> result = + cont.insert(value); + EXPECT_TRUE(result.second); + EXPECT_EQ(cont.begin(), result.first); + EXPECT_EQ(1U, cont.size()); + EXPECT_EQ(2, *result.first); + + value = 1; + result = cont.insert(value); + EXPECT_TRUE(result.second); + EXPECT_EQ(cont.begin(), result.first); + EXPECT_EQ(2U, cont.size()); + EXPECT_EQ(1, *result.first); + + value = 3; + result = cont.insert(value); + EXPECT_TRUE(result.second); + EXPECT_EQ(std::prev(cont.end()), result.first); + EXPECT_EQ(3U, cont.size()); + EXPECT_EQ(3, *result.first); + + value = 3; + result = cont.insert(value); + EXPECT_FALSE(result.second); + EXPECT_EQ(std::prev(cont.end()), result.first); + EXPECT_EQ(3U, cont.size()); + EXPECT_EQ(3, *result.first); +} + +// pair<iterator, bool> insert(value_type&& val) + +TEST(FlatTree, InsertRValue) { + MoveOnlyTree cont; + + std::pair<MoveOnlyTree::iterator, bool> result = cont.insert(MoveOnlyInt(2)); + EXPECT_TRUE(result.second); + EXPECT_EQ(cont.begin(), result.first); + EXPECT_EQ(1U, cont.size()); + EXPECT_EQ(2, result.first->data()); + + result = cont.insert(MoveOnlyInt(1)); + EXPECT_TRUE(result.second); + EXPECT_EQ(cont.begin(), result.first); + EXPECT_EQ(2U, cont.size()); + EXPECT_EQ(1, result.first->data()); + + result = cont.insert(MoveOnlyInt(3)); + EXPECT_TRUE(result.second); + EXPECT_EQ(std::prev(cont.end()), result.first); + EXPECT_EQ(3U, cont.size()); + EXPECT_EQ(3, result.first->data()); + + result = cont.insert(MoveOnlyInt(3)); + EXPECT_FALSE(result.second); + EXPECT_EQ(std::prev(cont.end()), result.first); + EXPECT_EQ(3U, cont.size()); + EXPECT_EQ(3, result.first->data()); +} + +// iterator insert(const_iterator position_hint, const value_type& val) + +TYPED_TEST_P(FlatTreeTest, InsertPositionLValue) { + TypedTree<TypeParam> cont; + + auto result = cont.insert(cont.cend(), 2); + EXPECT_EQ(cont.begin(), result); + EXPECT_EQ(1U, cont.size()); + EXPECT_EQ(2, *result); + + result = cont.insert(cont.cend(), 1); + EXPECT_EQ(cont.begin(), result); + EXPECT_EQ(2U, cont.size()); + EXPECT_EQ(1, *result); + + result = cont.insert(cont.cend(), 3); + EXPECT_EQ(std::prev(cont.end()), result); + EXPECT_EQ(3U, cont.size()); + EXPECT_EQ(3, *result); + + result = cont.insert(cont.cend(), 3); + EXPECT_EQ(std::prev(cont.end()), result); + EXPECT_EQ(3U, cont.size()); + EXPECT_EQ(3, *result); +} + +// iterator insert(const_iterator position_hint, value_type&& val) + +TEST(FlatTree, InsertPositionRValue) { + MoveOnlyTree cont; + + auto result = cont.insert(cont.cend(), MoveOnlyInt(2)); + EXPECT_EQ(cont.begin(), result); + EXPECT_EQ(1U, cont.size()); + EXPECT_EQ(2, result->data()); + + result = cont.insert(cont.cend(), MoveOnlyInt(1)); + EXPECT_EQ(cont.begin(), result); + EXPECT_EQ(2U, cont.size()); + EXPECT_EQ(1, result->data()); + + result = cont.insert(cont.cend(), MoveOnlyInt(3)); + EXPECT_EQ(std::prev(cont.end()), result); + EXPECT_EQ(3U, cont.size()); + EXPECT_EQ(3, result->data()); + + result = cont.insert(cont.cend(), MoveOnlyInt(3)); + EXPECT_EQ(std::prev(cont.end()), result); + EXPECT_EQ(3U, cont.size()); + EXPECT_EQ(3, result->data()); +} + +// template <class InputIterator> +// void insert(InputIterator first, InputIterator last); + +TEST(FlatTree, InsertIterIter) { + struct GetKeyFromIntIntPair { + const int& operator()(const std::pair<int, int>& p) const { + return p.first; + } + }; + + using IntIntMap = flat_tree<int, GetKeyFromIntIntPair, std::less<int>, + std::vector<IntPair>>; + + { + IntIntMap cont; + IntPair int_pairs[] = {{3, 1}, {1, 1}, {4, 1}, {2, 1}}; + cont.insert(std::begin(int_pairs), std::end(int_pairs)); + EXPECT_THAT(cont, ElementsAre(IntPair(1, 1), IntPair(2, 1), IntPair(3, 1), + IntPair(4, 1))); + } + + { + IntIntMap cont({{1, 1}, {2, 1}, {3, 1}, {4, 1}}); + std::vector<IntPair> int_pairs; + cont.insert(std::begin(int_pairs), std::end(int_pairs)); + EXPECT_THAT(cont, ElementsAre(IntPair(1, 1), IntPair(2, 1), IntPair(3, 1), + IntPair(4, 1))); + } + + { + IntIntMap cont({{1, 1}, {2, 1}, {3, 1}, {4, 1}}); + IntPair int_pairs[] = {{1, 1}}; + cont.insert(std::begin(int_pairs), std::end(int_pairs)); + EXPECT_THAT(cont, ElementsAre(IntPair(1, 1), IntPair(2, 1), IntPair(3, 1), + IntPair(4, 1))); + } + + { + IntIntMap cont({{1, 1}, {2, 1}, {3, 1}, {4, 1}}); + IntPair int_pairs[] = {{5, 1}}; + cont.insert(std::begin(int_pairs), std::end(int_pairs)); + EXPECT_THAT(cont, ElementsAre(IntPair(1, 1), IntPair(2, 1), IntPair(3, 1), + IntPair(4, 1), IntPair(5, 1))); + } + + { + IntIntMap cont({{1, 1}, {2, 1}, {3, 1}, {4, 1}}); + IntPair int_pairs[] = {{3, 2}, {1, 2}, {4, 2}, {2, 2}}; + cont.insert(std::begin(int_pairs), std::end(int_pairs)); + EXPECT_THAT(cont, ElementsAre(IntPair(1, 1), IntPair(2, 1), IntPair(3, 1), + IntPair(4, 1))); + } + + { + IntIntMap cont({{1, 1}, {2, 1}, {3, 1}, {4, 1}}); + IntPair int_pairs[] = {{3, 2}, {1, 2}, {4, 2}, {2, 2}, {7, 2}, {6, 2}, + {8, 2}, {5, 2}, {5, 3}, {6, 3}, {7, 3}, {8, 3}}; + cont.insert(std::begin(int_pairs), std::end(int_pairs)); + EXPECT_THAT(cont, ElementsAre(IntPair(1, 1), IntPair(2, 1), IntPair(3, 1), + IntPair(4, 1), IntPair(5, 2), IntPair(6, 2), + IntPair(7, 2), IntPair(8, 2))); + } +} + +// template <class... Args> +// pair<iterator, bool> emplace(Args&&... args) + +TYPED_TEST_P(FlatTreeTest, Emplace) { + { + EmplaceableTree cont; + + std::pair<EmplaceableTree::iterator, bool> result = cont.emplace(); + EXPECT_TRUE(result.second); + EXPECT_EQ(cont.begin(), result.first); + EXPECT_EQ(1U, cont.size()); + EXPECT_EQ(Emplaceable(), *cont.begin()); + + result = cont.emplace(2, 3.5); + EXPECT_TRUE(result.second); + EXPECT_EQ(std::next(cont.begin()), result.first); + EXPECT_EQ(2U, cont.size()); + EXPECT_EQ(Emplaceable(2, 3.5), *result.first); + + result = cont.emplace(2, 3.5); + EXPECT_FALSE(result.second); + EXPECT_EQ(std::next(cont.begin()), result.first); + EXPECT_EQ(2U, cont.size()); + EXPECT_EQ(Emplaceable(2, 3.5), *result.first); + } + { + TypedTree<TypeParam> cont; + + std::pair<typename TypedTree<TypeParam>::iterator, bool> result = + cont.emplace(2); + EXPECT_TRUE(result.second); + EXPECT_EQ(cont.begin(), result.first); + EXPECT_EQ(1U, cont.size()); + EXPECT_EQ(2, *result.first); + } +} + +// template <class... Args> +// iterator emplace_hint(const_iterator position_hint, Args&&... args) + +TYPED_TEST_P(FlatTreeTest, EmplacePosition) { + { + EmplaceableTree cont; + + auto result = cont.emplace_hint(cont.cend()); + EXPECT_EQ(cont.begin(), result); + EXPECT_EQ(1U, cont.size()); + EXPECT_EQ(Emplaceable(), *cont.begin()); + + result = cont.emplace_hint(cont.cend(), 2, 3.5); + EXPECT_EQ(std::next(cont.begin()), result); + EXPECT_EQ(2U, cont.size()); + EXPECT_EQ(Emplaceable(2, 3.5), *result); + + result = cont.emplace_hint(cont.cbegin(), 2, 3.5); + EXPECT_EQ(std::next(cont.begin()), result); + EXPECT_EQ(2U, cont.size()); + EXPECT_EQ(Emplaceable(2, 3.5), *result); + } + { + TypedTree<TypeParam> cont; + + auto result = cont.emplace_hint(cont.cend(), 2); + EXPECT_EQ(cont.begin(), result); + EXPECT_EQ(1U, cont.size()); + EXPECT_EQ(2, *result); + } +} + +// ---------------------------------------------------------------------------- +// Underlying type operations. + +// underlying_type extract() && +TYPED_TEST_P(FlatTreeTest, Extract) { + TypedTree<TypeParam> cont; + cont.emplace(3); + cont.emplace(1); + cont.emplace(2); + cont.emplace(4); + + TypeParam body = std::move(cont).extract(); + EXPECT_THAT(cont, IsEmpty()); + EXPECT_THAT(body, ElementsAre(1, 2, 3, 4)); +} + +// replace(underlying_type&&) +TYPED_TEST_P(FlatTreeTest, Replace) { + TypeParam body = {1, 2, 3, 4}; + TypedTree<TypeParam> cont; + cont.replace(std::move(body)); + + EXPECT_THAT(cont, ElementsAre(1, 2, 3, 4)); +} + +// ---------------------------------------------------------------------------- +// Erase operations. + +// iterator erase(const_iterator position_hint) + +TYPED_TEST_P(FlatTreeTest, ErasePosition) { + { + TypedTree<TypeParam> cont({1, 2, 3, 4, 5, 6, 7, 8}); + + auto it = cont.erase(std::next(cont.cbegin(), 3)); + EXPECT_EQ(std::next(cont.begin(), 3), it); + EXPECT_THAT(cont, ElementsAre(1, 2, 3, 5, 6, 7, 8)); + + it = cont.erase(std::next(cont.cbegin(), 0)); + EXPECT_EQ(cont.begin(), it); + EXPECT_THAT(cont, ElementsAre(2, 3, 5, 6, 7, 8)); + + it = cont.erase(std::next(cont.cbegin(), 5)); + EXPECT_EQ(cont.end(), it); + EXPECT_THAT(cont, ElementsAre(2, 3, 5, 6, 7)); + + it = cont.erase(std::next(cont.cbegin(), 1)); + EXPECT_EQ(std::next(cont.begin()), it); + EXPECT_THAT(cont, ElementsAre(2, 5, 6, 7)); + + it = cont.erase(std::next(cont.cbegin(), 2)); + EXPECT_EQ(std::next(cont.begin(), 2), it); + EXPECT_THAT(cont, ElementsAre(2, 5, 7)); + + it = cont.erase(std::next(cont.cbegin(), 2)); + EXPECT_EQ(std::next(cont.begin(), 2), it); + EXPECT_THAT(cont, ElementsAre(2, 5)); + + it = cont.erase(std::next(cont.cbegin(), 0)); + EXPECT_EQ(std::next(cont.begin(), 0), it); + EXPECT_THAT(cont, ElementsAre(5)); + + it = cont.erase(cont.cbegin()); + EXPECT_EQ(cont.begin(), it); + EXPECT_EQ(cont.end(), it); + } + // This is LWG #2059. + // There is a potential ambiguity between erase with an iterator and erase + // with a key, if key has a templated constructor. + { + using T = TemplateConstructor; + + flat_tree<T, identity, std::less<>, std::vector<T>> cont; + T v(0); + + auto it = cont.find(v); + if (it != cont.end()) + cont.erase(it); + } +} + +// iterator erase(const_iterator first, const_iterator last) + +TYPED_TEST_P(FlatTreeTest, EraseRange) { + TypedTree<TypeParam> cont({1, 2, 3, 4, 5, 6, 7, 8}); + + auto it = + cont.erase(std::next(cont.cbegin(), 5), std::next(cont.cbegin(), 5)); + EXPECT_EQ(std::next(cont.begin(), 5), it); + EXPECT_THAT(cont, ElementsAre(1, 2, 3, 4, 5, 6, 7, 8)); + + it = cont.erase(std::next(cont.cbegin(), 3), std::next(cont.cbegin(), 4)); + EXPECT_EQ(std::next(cont.begin(), 3), it); + EXPECT_THAT(cont, ElementsAre(1, 2, 3, 5, 6, 7, 8)); + + it = cont.erase(std::next(cont.cbegin(), 2), std::next(cont.cbegin(), 5)); + EXPECT_EQ(std::next(cont.begin(), 2), it); + EXPECT_THAT(cont, ElementsAre(1, 2, 7, 8)); + + it = cont.erase(std::next(cont.cbegin(), 0), std::next(cont.cbegin(), 2)); + EXPECT_EQ(std::next(cont.begin(), 0), it); + EXPECT_THAT(cont, ElementsAre(7, 8)); + + it = cont.erase(cont.cbegin(), cont.cend()); + EXPECT_EQ(cont.begin(), it); + EXPECT_EQ(cont.end(), it); +} + +// size_type erase(const key_type& key) + +TYPED_TEST_P(FlatTreeTest, EraseKey) { + TypedTree<TypeParam> cont({1, 2, 3, 4, 5, 6, 7, 8}); + + EXPECT_EQ(0U, cont.erase(9)); + EXPECT_THAT(cont, ElementsAre(1, 2, 3, 4, 5, 6, 7, 8)); + + EXPECT_EQ(1U, cont.erase(4)); + EXPECT_THAT(cont, ElementsAre(1, 2, 3, 5, 6, 7, 8)); + + EXPECT_EQ(1U, cont.erase(1)); + EXPECT_THAT(cont, ElementsAre(2, 3, 5, 6, 7, 8)); + + EXPECT_EQ(1U, cont.erase(8)); + EXPECT_THAT(cont, ElementsAre(2, 3, 5, 6, 7)); + + EXPECT_EQ(1U, cont.erase(3)); + EXPECT_THAT(cont, ElementsAre(2, 5, 6, 7)); + + EXPECT_EQ(1U, cont.erase(6)); + EXPECT_THAT(cont, ElementsAre(2, 5, 7)); + + EXPECT_EQ(1U, cont.erase(7)); + EXPECT_THAT(cont, ElementsAre(2, 5)); + + EXPECT_EQ(1U, cont.erase(2)); + EXPECT_THAT(cont, ElementsAre(5)); + + EXPECT_EQ(1U, cont.erase(5)); + EXPECT_THAT(cont, ElementsAre()); +} + +TYPED_TEST_P(FlatTreeTest, EraseEndDeath) { + { + TypedTree<TypeParam> tree; + ASSERT_DEATH_IF_SUPPORTED(tree.erase(tree.cend()), ""); + } + + { + TypedTree<TypeParam> tree = {1, 2, 3, 4}; + ASSERT_DEATH_IF_SUPPORTED(tree.erase(tree.find(5)), ""); + } +} + +// ---------------------------------------------------------------------------- +// Comparators. + +// key_compare key_comp() const + +TEST(FlatTree, KeyComp) { + ReversedTree cont({1, 2, 3, 4, 5}); + + EXPECT_TRUE(absl::c_is_sorted(cont, cont.key_comp())); + int new_elements[] = {6, 7, 8, 9, 10}; + std::copy(std::begin(new_elements), std::end(new_elements), + std::inserter(cont, cont.end())); + EXPECT_TRUE(absl::c_is_sorted(cont, cont.key_comp())); +} + +// value_compare value_comp() const + +TEST(FlatTree, ValueComp) { + ReversedTree cont({1, 2, 3, 4, 5}); + + EXPECT_TRUE(absl::c_is_sorted(cont, cont.value_comp())); + int new_elements[] = {6, 7, 8, 9, 10}; + std::copy(std::begin(new_elements), std::end(new_elements), + std::inserter(cont, cont.end())); + EXPECT_TRUE(absl::c_is_sorted(cont, cont.value_comp())); +} + +// ---------------------------------------------------------------------------- +// Search operations. + +// size_type count(const key_type& key) const + +TYPED_TEST_P(FlatTreeTest, Count) { + const TypedTree<TypeParam> cont({5, 6, 7, 8, 9, 10, 11, 12}); + + EXPECT_EQ(1U, cont.count(5)); + EXPECT_EQ(1U, cont.count(6)); + EXPECT_EQ(1U, cont.count(7)); + EXPECT_EQ(1U, cont.count(8)); + EXPECT_EQ(1U, cont.count(9)); + EXPECT_EQ(1U, cont.count(10)); + EXPECT_EQ(1U, cont.count(11)); + EXPECT_EQ(1U, cont.count(12)); + EXPECT_EQ(0U, cont.count(4)); +} + +// iterator find(const key_type& key) +// const_iterator find(const key_type& key) const + +TYPED_TEST_P(FlatTreeTest, Find) { + { + TypedTree<TypeParam> cont({5, 6, 7, 8, 9, 10, 11, 12}); + + EXPECT_EQ(cont.begin(), cont.find(5)); + EXPECT_EQ(std::next(cont.begin()), cont.find(6)); + EXPECT_EQ(std::next(cont.begin(), 2), cont.find(7)); + EXPECT_EQ(std::next(cont.begin(), 3), cont.find(8)); + EXPECT_EQ(std::next(cont.begin(), 4), cont.find(9)); + EXPECT_EQ(std::next(cont.begin(), 5), cont.find(10)); + EXPECT_EQ(std::next(cont.begin(), 6), cont.find(11)); + EXPECT_EQ(std::next(cont.begin(), 7), cont.find(12)); + EXPECT_EQ(std::next(cont.begin(), 8), cont.find(4)); + } + { + const TypedTree<TypeParam> cont({5, 6, 7, 8, 9, 10, 11, 12}); + + EXPECT_EQ(cont.begin(), cont.find(5)); + EXPECT_EQ(std::next(cont.begin()), cont.find(6)); + EXPECT_EQ(std::next(cont.begin(), 2), cont.find(7)); + EXPECT_EQ(std::next(cont.begin(), 3), cont.find(8)); + EXPECT_EQ(std::next(cont.begin(), 4), cont.find(9)); + EXPECT_EQ(std::next(cont.begin(), 5), cont.find(10)); + EXPECT_EQ(std::next(cont.begin(), 6), cont.find(11)); + EXPECT_EQ(std::next(cont.begin(), 7), cont.find(12)); + EXPECT_EQ(std::next(cont.begin(), 8), cont.find(4)); + } +} + +// bool contains(const key_type& key) const + +TYPED_TEST_P(FlatTreeTest, Contains) { + const TypedTree<TypeParam> cont({5, 6, 7, 8, 9, 10, 11, 12}); + + EXPECT_TRUE(cont.contains(5)); + EXPECT_TRUE(cont.contains(6)); + EXPECT_TRUE(cont.contains(7)); + EXPECT_TRUE(cont.contains(8)); + EXPECT_TRUE(cont.contains(9)); + EXPECT_TRUE(cont.contains(10)); + EXPECT_TRUE(cont.contains(11)); + EXPECT_TRUE(cont.contains(12)); + EXPECT_FALSE(cont.contains(4)); +} + +// pair<iterator, iterator> equal_range(const key_type& key) +// pair<const_iterator, const_iterator> equal_range(const key_type& key) const + +TYPED_TEST_P(FlatTreeTest, EqualRange) { + { + TypedTree<TypeParam> cont({5, 7, 9, 11, 13, 15, 17, 19}); + + std::pair<typename TypedTree<TypeParam>::iterator, + typename TypedTree<TypeParam>::iterator> + result = cont.equal_range(5); + EXPECT_EQ(std::next(cont.begin(), 0), result.first); + EXPECT_EQ(std::next(cont.begin(), 1), result.second); + result = cont.equal_range(7); + EXPECT_EQ(std::next(cont.begin(), 1), result.first); + EXPECT_EQ(std::next(cont.begin(), 2), result.second); + result = cont.equal_range(9); + EXPECT_EQ(std::next(cont.begin(), 2), result.first); + EXPECT_EQ(std::next(cont.begin(), 3), result.second); + result = cont.equal_range(11); + EXPECT_EQ(std::next(cont.begin(), 3), result.first); + EXPECT_EQ(std::next(cont.begin(), 4), result.second); + result = cont.equal_range(13); + EXPECT_EQ(std::next(cont.begin(), 4), result.first); + EXPECT_EQ(std::next(cont.begin(), 5), result.second); + result = cont.equal_range(15); + EXPECT_EQ(std::next(cont.begin(), 5), result.first); + EXPECT_EQ(std::next(cont.begin(), 6), result.second); + result = cont.equal_range(17); + EXPECT_EQ(std::next(cont.begin(), 6), result.first); + EXPECT_EQ(std::next(cont.begin(), 7), result.second); + result = cont.equal_range(19); + EXPECT_EQ(std::next(cont.begin(), 7), result.first); + EXPECT_EQ(std::next(cont.begin(), 8), result.second); + result = cont.equal_range(4); + EXPECT_EQ(std::next(cont.begin(), 0), result.first); + EXPECT_EQ(std::next(cont.begin(), 0), result.second); + result = cont.equal_range(6); + EXPECT_EQ(std::next(cont.begin(), 1), result.first); + EXPECT_EQ(std::next(cont.begin(), 1), result.second); + result = cont.equal_range(8); + EXPECT_EQ(std::next(cont.begin(), 2), result.first); + EXPECT_EQ(std::next(cont.begin(), 2), result.second); + result = cont.equal_range(10); + EXPECT_EQ(std::next(cont.begin(), 3), result.first); + EXPECT_EQ(std::next(cont.begin(), 3), result.second); + result = cont.equal_range(12); + EXPECT_EQ(std::next(cont.begin(), 4), result.first); + EXPECT_EQ(std::next(cont.begin(), 4), result.second); + result = cont.equal_range(14); + EXPECT_EQ(std::next(cont.begin(), 5), result.first); + EXPECT_EQ(std::next(cont.begin(), 5), result.second); + result = cont.equal_range(16); + EXPECT_EQ(std::next(cont.begin(), 6), result.first); + EXPECT_EQ(std::next(cont.begin(), 6), result.second); + result = cont.equal_range(18); + EXPECT_EQ(std::next(cont.begin(), 7), result.first); + EXPECT_EQ(std::next(cont.begin(), 7), result.second); + result = cont.equal_range(20); + EXPECT_EQ(std::next(cont.begin(), 8), result.first); + EXPECT_EQ(std::next(cont.begin(), 8), result.second); + } + { + const TypedTree<TypeParam> cont({5, 7, 9, 11, 13, 15, 17, 19}); + + std::pair<typename TypedTree<TypeParam>::const_iterator, + typename TypedTree<TypeParam>::const_iterator> + result = cont.equal_range(5); + EXPECT_EQ(std::next(cont.begin(), 0), result.first); + EXPECT_EQ(std::next(cont.begin(), 1), result.second); + result = cont.equal_range(7); + EXPECT_EQ(std::next(cont.begin(), 1), result.first); + EXPECT_EQ(std::next(cont.begin(), 2), result.second); + result = cont.equal_range(9); + EXPECT_EQ(std::next(cont.begin(), 2), result.first); + EXPECT_EQ(std::next(cont.begin(), 3), result.second); + result = cont.equal_range(11); + EXPECT_EQ(std::next(cont.begin(), 3), result.first); + EXPECT_EQ(std::next(cont.begin(), 4), result.second); + result = cont.equal_range(13); + EXPECT_EQ(std::next(cont.begin(), 4), result.first); + EXPECT_EQ(std::next(cont.begin(), 5), result.second); + result = cont.equal_range(15); + EXPECT_EQ(std::next(cont.begin(), 5), result.first); + EXPECT_EQ(std::next(cont.begin(), 6), result.second); + result = cont.equal_range(17); + EXPECT_EQ(std::next(cont.begin(), 6), result.first); + EXPECT_EQ(std::next(cont.begin(), 7), result.second); + result = cont.equal_range(19); + EXPECT_EQ(std::next(cont.begin(), 7), result.first); + EXPECT_EQ(std::next(cont.begin(), 8), result.second); + result = cont.equal_range(4); + EXPECT_EQ(std::next(cont.begin(), 0), result.first); + EXPECT_EQ(std::next(cont.begin(), 0), result.second); + result = cont.equal_range(6); + EXPECT_EQ(std::next(cont.begin(), 1), result.first); + EXPECT_EQ(std::next(cont.begin(), 1), result.second); + result = cont.equal_range(8); + EXPECT_EQ(std::next(cont.begin(), 2), result.first); + EXPECT_EQ(std::next(cont.begin(), 2), result.second); + result = cont.equal_range(10); + EXPECT_EQ(std::next(cont.begin(), 3), result.first); + EXPECT_EQ(std::next(cont.begin(), 3), result.second); + result = cont.equal_range(12); + EXPECT_EQ(std::next(cont.begin(), 4), result.first); + EXPECT_EQ(std::next(cont.begin(), 4), result.second); + result = cont.equal_range(14); + EXPECT_EQ(std::next(cont.begin(), 5), result.first); + EXPECT_EQ(std::next(cont.begin(), 5), result.second); + result = cont.equal_range(16); + EXPECT_EQ(std::next(cont.begin(), 6), result.first); + EXPECT_EQ(std::next(cont.begin(), 6), result.second); + result = cont.equal_range(18); + EXPECT_EQ(std::next(cont.begin(), 7), result.first); + EXPECT_EQ(std::next(cont.begin(), 7), result.second); + result = cont.equal_range(20); + EXPECT_EQ(std::next(cont.begin(), 8), result.first); + EXPECT_EQ(std::next(cont.begin(), 8), result.second); + } +} + +// iterator lower_bound(const key_type& key); +// const_iterator lower_bound(const key_type& key) const; + +TYPED_TEST_P(FlatTreeTest, LowerBound) { + { + TypedTree<TypeParam> cont({5, 7, 9, 11, 13, 15, 17, 19}); + + EXPECT_EQ(cont.begin(), cont.lower_bound(5)); + EXPECT_EQ(std::next(cont.begin()), cont.lower_bound(7)); + EXPECT_EQ(std::next(cont.begin(), 2), cont.lower_bound(9)); + EXPECT_EQ(std::next(cont.begin(), 3), cont.lower_bound(11)); + EXPECT_EQ(std::next(cont.begin(), 4), cont.lower_bound(13)); + EXPECT_EQ(std::next(cont.begin(), 5), cont.lower_bound(15)); + EXPECT_EQ(std::next(cont.begin(), 6), cont.lower_bound(17)); + EXPECT_EQ(std::next(cont.begin(), 7), cont.lower_bound(19)); + EXPECT_EQ(std::next(cont.begin(), 0), cont.lower_bound(4)); + EXPECT_EQ(std::next(cont.begin(), 1), cont.lower_bound(6)); + EXPECT_EQ(std::next(cont.begin(), 2), cont.lower_bound(8)); + EXPECT_EQ(std::next(cont.begin(), 3), cont.lower_bound(10)); + EXPECT_EQ(std::next(cont.begin(), 4), cont.lower_bound(12)); + EXPECT_EQ(std::next(cont.begin(), 5), cont.lower_bound(14)); + EXPECT_EQ(std::next(cont.begin(), 6), cont.lower_bound(16)); + EXPECT_EQ(std::next(cont.begin(), 7), cont.lower_bound(18)); + EXPECT_EQ(std::next(cont.begin(), 8), cont.lower_bound(20)); + } + { + const TypedTree<TypeParam> cont({5, 7, 9, 11, 13, 15, 17, 19}); + + EXPECT_EQ(cont.begin(), cont.lower_bound(5)); + EXPECT_EQ(std::next(cont.begin()), cont.lower_bound(7)); + EXPECT_EQ(std::next(cont.begin(), 2), cont.lower_bound(9)); + EXPECT_EQ(std::next(cont.begin(), 3), cont.lower_bound(11)); + EXPECT_EQ(std::next(cont.begin(), 4), cont.lower_bound(13)); + EXPECT_EQ(std::next(cont.begin(), 5), cont.lower_bound(15)); + EXPECT_EQ(std::next(cont.begin(), 6), cont.lower_bound(17)); + EXPECT_EQ(std::next(cont.begin(), 7), cont.lower_bound(19)); + EXPECT_EQ(std::next(cont.begin(), 0), cont.lower_bound(4)); + EXPECT_EQ(std::next(cont.begin(), 1), cont.lower_bound(6)); + EXPECT_EQ(std::next(cont.begin(), 2), cont.lower_bound(8)); + EXPECT_EQ(std::next(cont.begin(), 3), cont.lower_bound(10)); + EXPECT_EQ(std::next(cont.begin(), 4), cont.lower_bound(12)); + EXPECT_EQ(std::next(cont.begin(), 5), cont.lower_bound(14)); + EXPECT_EQ(std::next(cont.begin(), 6), cont.lower_bound(16)); + EXPECT_EQ(std::next(cont.begin(), 7), cont.lower_bound(18)); + EXPECT_EQ(std::next(cont.begin(), 8), cont.lower_bound(20)); + } +} + +// iterator upper_bound(const key_type& key) +// const_iterator upper_bound(const key_type& key) const + +TYPED_TEST_P(FlatTreeTest, UpperBound) { + { + TypedTree<TypeParam> cont({5, 7, 9, 11, 13, 15, 17, 19}); + + EXPECT_EQ(std::next(cont.begin(), 1), cont.upper_bound(5)); + EXPECT_EQ(std::next(cont.begin(), 2), cont.upper_bound(7)); + EXPECT_EQ(std::next(cont.begin(), 3), cont.upper_bound(9)); + EXPECT_EQ(std::next(cont.begin(), 4), cont.upper_bound(11)); + EXPECT_EQ(std::next(cont.begin(), 5), cont.upper_bound(13)); + EXPECT_EQ(std::next(cont.begin(), 6), cont.upper_bound(15)); + EXPECT_EQ(std::next(cont.begin(), 7), cont.upper_bound(17)); + EXPECT_EQ(std::next(cont.begin(), 8), cont.upper_bound(19)); + EXPECT_EQ(std::next(cont.begin(), 0), cont.upper_bound(4)); + EXPECT_EQ(std::next(cont.begin(), 1), cont.upper_bound(6)); + EXPECT_EQ(std::next(cont.begin(), 2), cont.upper_bound(8)); + EXPECT_EQ(std::next(cont.begin(), 3), cont.upper_bound(10)); + EXPECT_EQ(std::next(cont.begin(), 4), cont.upper_bound(12)); + EXPECT_EQ(std::next(cont.begin(), 5), cont.upper_bound(14)); + EXPECT_EQ(std::next(cont.begin(), 6), cont.upper_bound(16)); + EXPECT_EQ(std::next(cont.begin(), 7), cont.upper_bound(18)); + EXPECT_EQ(std::next(cont.begin(), 8), cont.upper_bound(20)); + } + { + const TypedTree<TypeParam> cont({5, 7, 9, 11, 13, 15, 17, 19}); + + EXPECT_EQ(std::next(cont.begin(), 1), cont.upper_bound(5)); + EXPECT_EQ(std::next(cont.begin(), 2), cont.upper_bound(7)); + EXPECT_EQ(std::next(cont.begin(), 3), cont.upper_bound(9)); + EXPECT_EQ(std::next(cont.begin(), 4), cont.upper_bound(11)); + EXPECT_EQ(std::next(cont.begin(), 5), cont.upper_bound(13)); + EXPECT_EQ(std::next(cont.begin(), 6), cont.upper_bound(15)); + EXPECT_EQ(std::next(cont.begin(), 7), cont.upper_bound(17)); + EXPECT_EQ(std::next(cont.begin(), 8), cont.upper_bound(19)); + EXPECT_EQ(std::next(cont.begin(), 0), cont.upper_bound(4)); + EXPECT_EQ(std::next(cont.begin(), 1), cont.upper_bound(6)); + EXPECT_EQ(std::next(cont.begin(), 2), cont.upper_bound(8)); + EXPECT_EQ(std::next(cont.begin(), 3), cont.upper_bound(10)); + EXPECT_EQ(std::next(cont.begin(), 4), cont.upper_bound(12)); + EXPECT_EQ(std::next(cont.begin(), 5), cont.upper_bound(14)); + EXPECT_EQ(std::next(cont.begin(), 6), cont.upper_bound(16)); + EXPECT_EQ(std::next(cont.begin(), 7), cont.upper_bound(18)); + EXPECT_EQ(std::next(cont.begin(), 8), cont.upper_bound(20)); + } +} + +// ---------------------------------------------------------------------------- +// General operations. + +// void swap(flat_tree& other) +// void swap(flat_tree& lhs, flat_tree& rhs) + +TYPED_TEST_P(FlatTreeTest, Swap) { + TypedTree<TypeParam> x({1, 2, 3}); + TypedTree<TypeParam> y({4}); + swap(x, y); + EXPECT_THAT(x, ElementsAre(4)); + EXPECT_THAT(y, ElementsAre(1, 2, 3)); + + y.swap(x); + EXPECT_THAT(x, ElementsAre(1, 2, 3)); + EXPECT_THAT(y, ElementsAre(4)); +} + +// bool operator==(const flat_tree& lhs, const flat_tree& rhs) +// bool operator!=(const flat_tree& lhs, const flat_tree& rhs) +// bool operator<(const flat_tree& lhs, const flat_tree& rhs) +// bool operator>(const flat_tree& lhs, const flat_tree& rhs) +// bool operator<=(const flat_tree& lhs, const flat_tree& rhs) +// bool operator>=(const flat_tree& lhs, const flat_tree& rhs) + +TEST(FlatTree, Comparison) { + // Provided comparator does not participate in comparison. + ReversedTree biggest({3}); + ReversedTree smallest({1}); + ReversedTree middle({1, 2}); + + EXPECT_EQ(biggest, biggest); + EXPECT_NE(biggest, smallest); + EXPECT_LT(smallest, middle); + EXPECT_LE(smallest, middle); + EXPECT_LE(middle, middle); + EXPECT_GT(biggest, middle); + EXPECT_GE(biggest, middle); + EXPECT_GE(biggest, biggest); +} + +TYPED_TEST_P(FlatTreeTest, SupportsEraseIf) { + TypedTree<TypeParam> x; + EXPECT_EQ(0u, EraseIf(x, [](int) { return false; })); + EXPECT_THAT(x, ElementsAre()); + + x = {1, 2, 3}; + EXPECT_EQ(1u, EraseIf(x, [](int elem) { return !(elem & 1); })); + EXPECT_THAT(x, ElementsAre(1, 3)); + + x = {1, 2, 3, 4}; + EXPECT_EQ(2u, EraseIf(x, [](int elem) { return elem & 1; })); + EXPECT_THAT(x, ElementsAre(2, 4)); +} + +REGISTER_TYPED_TEST_SUITE_P(FlatTreeTest, + DefaultConstructor, + CopyConstructor, + ContainerCopyConstructor, + InitializerListConstructor, + SortedUniqueContainerCopyConstructor, + SortedUniqueInitializerListConstructor, + CopyAssignable, + InitializerListAssignable, + Clear, + Size, + Empty, + Iterators, + InsertLValue, + InsertPositionLValue, + Emplace, + EmplacePosition, + Extract, + Replace, + ErasePosition, + EraseRange, + EraseKey, + EraseEndDeath, + Count, + Find, + Contains, + EqualRange, + LowerBound, + UpperBound, + Swap, + SupportsEraseIf); + +using IntSequenceContainers = + ::testing::Types<std::deque<int>, std::vector<int>>; +INSTANTIATE_TYPED_TEST_SUITE_P(My, FlatTreeTest, IntSequenceContainers); + +} // namespace +} // namespace flat_containers_internal +} // namespace webrtc diff --git a/third_party/libwebrtc/rtc_base/containers/identity.h b/third_party/libwebrtc/rtc_base/containers/identity.h new file mode 100644 index 0000000000..29592931bd --- /dev/null +++ b/third_party/libwebrtc/rtc_base/containers/identity.h @@ -0,0 +1,36 @@ +/* + * Copyright (c) 2021 The WebRTC project authors. All Rights Reserved. + * + * Use of this source code is governed by a BSD-style license + * that can be found in the LICENSE file in the root of the source + * tree. An additional intellectual property rights grant can be found + * in the file PATENTS. All contributing project authors may + * be found in the AUTHORS file in the root of the source tree. + */ + +// This implementation is borrowed from Chromium. + +#ifndef RTC_BASE_CONTAINERS_IDENTITY_H_ +#define RTC_BASE_CONTAINERS_IDENTITY_H_ + +#include <utility> + +namespace webrtc { + +// Implementation of C++20's std::identity. +// +// Reference: +// - https://en.cppreference.com/w/cpp/utility/functional/identity +// - https://wg21.link/func.identity +struct identity { + template <typename T> + constexpr T&& operator()(T&& t) const noexcept { + return std::forward<T>(t); + } + + using is_transparent = void; +}; + +} // namespace webrtc + +#endif // RTC_BASE_CONTAINERS_IDENTITY_H_ diff --git a/third_party/libwebrtc/rtc_base/containers/invoke.h b/third_party/libwebrtc/rtc_base/containers/invoke.h new file mode 100644 index 0000000000..5d17a70beb --- /dev/null +++ b/third_party/libwebrtc/rtc_base/containers/invoke.h @@ -0,0 +1,162 @@ +/* + * Copyright (c) 2021 The WebRTC project authors. All Rights Reserved. + * + * Use of this source code is governed by a BSD-style license + * that can be found in the LICENSE file in the root of the source + * tree. An additional intellectual property rights grant can be found + * in the file PATENTS. All contributing project authors may + * be found in the AUTHORS file in the root of the source tree. + */ + +// This implementation is borrowed from Chromium. + +#ifndef RTC_BASE_CONTAINERS_INVOKE_H_ +#define RTC_BASE_CONTAINERS_INVOKE_H_ + +#include <type_traits> +#include <utility> + +namespace webrtc { + +namespace invoke_internal { + +// Helper struct and alias to deduce the class type from a member function +// pointer or member object pointer. +template <typename DecayedF> +struct member_pointer_class {}; + +template <typename ReturnT, typename ClassT> +struct member_pointer_class<ReturnT ClassT::*> { + using type = ClassT; +}; + +template <typename DecayedF> +using member_pointer_class_t = typename member_pointer_class<DecayedF>::type; + +// Utility struct to detect specializations of std::reference_wrapper. +template <typename T> +struct is_reference_wrapper : std::false_type {}; + +template <typename T> +struct is_reference_wrapper<std::reference_wrapper<T>> : std::true_type {}; + +// Small helpers used below in invoke_internal::invoke to make the SFINAE more +// concise. +template <typename F> +const bool& IsMemFunPtr = + std::is_member_function_pointer<std::decay_t<F>>::value; + +template <typename F> +const bool& IsMemObjPtr = std::is_member_object_pointer<std::decay_t<F>>::value; + +template <typename F, + typename T, + typename MemPtrClass = member_pointer_class_t<std::decay_t<F>>> +const bool& IsMemPtrToBaseOf = + std::is_base_of<MemPtrClass, std::decay_t<T>>::value; + +template <typename T> +const bool& IsRefWrapper = is_reference_wrapper<std::decay_t<T>>::value; + +template <bool B> +using EnableIf = std::enable_if_t<B, bool>; + +// Invokes a member function pointer on a reference to an object of a suitable +// type. Covers bullet 1 of the INVOKE definition. +// +// Reference: https://wg21.link/func.require#1.1 +template <typename F, + typename T1, + typename... Args, + EnableIf<IsMemFunPtr<F> && IsMemPtrToBaseOf<F, T1>> = true> +constexpr decltype(auto) InvokeImpl(F&& f, T1&& t1, Args&&... args) { + return (std::forward<T1>(t1).*f)(std::forward<Args>(args)...); +} + +// Invokes a member function pointer on a std::reference_wrapper to an object of +// a suitable type. Covers bullet 2 of the INVOKE definition. +// +// Reference: https://wg21.link/func.require#1.2 +template <typename F, + typename T1, + typename... Args, + EnableIf<IsMemFunPtr<F> && IsRefWrapper<T1>> = true> +constexpr decltype(auto) InvokeImpl(F&& f, T1&& t1, Args&&... args) { + return (t1.get().*f)(std::forward<Args>(args)...); +} + +// Invokes a member function pointer on a pointer-like type to an object of a +// suitable type. Covers bullet 3 of the INVOKE definition. +// +// Reference: https://wg21.link/func.require#1.3 +template <typename F, + typename T1, + typename... Args, + EnableIf<IsMemFunPtr<F> && !IsMemPtrToBaseOf<F, T1> && + !IsRefWrapper<T1>> = true> +constexpr decltype(auto) InvokeImpl(F&& f, T1&& t1, Args&&... args) { + return ((*std::forward<T1>(t1)).*f)(std::forward<Args>(args)...); +} + +// Invokes a member object pointer on a reference to an object of a suitable +// type. Covers bullet 4 of the INVOKE definition. +// +// Reference: https://wg21.link/func.require#1.4 +template <typename F, + typename T1, + EnableIf<IsMemObjPtr<F> && IsMemPtrToBaseOf<F, T1>> = true> +constexpr decltype(auto) InvokeImpl(F&& f, T1&& t1) { + return std::forward<T1>(t1).*f; +} + +// Invokes a member object pointer on a std::reference_wrapper to an object of +// a suitable type. Covers bullet 5 of the INVOKE definition. +// +// Reference: https://wg21.link/func.require#1.5 +template <typename F, + typename T1, + EnableIf<IsMemObjPtr<F> && IsRefWrapper<T1>> = true> +constexpr decltype(auto) InvokeImpl(F&& f, T1&& t1) { + return t1.get().*f; +} + +// Invokes a member object pointer on a pointer-like type to an object of a +// suitable type. Covers bullet 6 of the INVOKE definition. +// +// Reference: https://wg21.link/func.require#1.6 +template <typename F, + typename T1, + EnableIf<IsMemObjPtr<F> && !IsMemPtrToBaseOf<F, T1> && + !IsRefWrapper<T1>> = true> +constexpr decltype(auto) InvokeImpl(F&& f, T1&& t1) { + return (*std::forward<T1>(t1)).*f; +} + +// Invokes a regular function or function object. Covers bullet 7 of the INVOKE +// definition. +// +// Reference: https://wg21.link/func.require#1.7 +template <typename F, typename... Args> +constexpr decltype(auto) InvokeImpl(F&& f, Args&&... args) { + return std::forward<F>(f)(std::forward<Args>(args)...); +} + +} // namespace invoke_internal + +// Implementation of C++17's std::invoke. This is not based on implementation +// referenced in original std::invoke proposal, but rather a manual +// implementation, so that it can be constexpr. +// +// References: +// - https://wg21.link/n4169#implementability +// - https://en.cppreference.com/w/cpp/utility/functional/invoke +// - https://wg21.link/func.invoke +template <typename F, typename... Args> +constexpr decltype(auto) invoke(F&& f, Args&&... args) { + return invoke_internal::InvokeImpl(std::forward<F>(f), + std::forward<Args>(args)...); +} + +} // namespace webrtc + +#endif // RTC_BASE_CONTAINERS_INVOKE_H_ diff --git a/third_party/libwebrtc/rtc_base/containers/move_only_int.h b/third_party/libwebrtc/rtc_base/containers/move_only_int.h new file mode 100644 index 0000000000..8f745aa688 --- /dev/null +++ b/third_party/libwebrtc/rtc_base/containers/move_only_int.h @@ -0,0 +1,74 @@ +/* + * Copyright (c) 2021 The WebRTC project authors. All Rights Reserved. + * + * Use of this source code is governed by a BSD-style license + * that can be found in the LICENSE file in the root of the source + * tree. An additional intellectual property rights grant can be found + * in the file PATENTS. All contributing project authors may + * be found in the AUTHORS file in the root of the source tree. + */ + +// This implementation is borrowed from Chromium. + +#ifndef RTC_BASE_CONTAINERS_MOVE_ONLY_INT_H_ +#define RTC_BASE_CONTAINERS_MOVE_ONLY_INT_H_ + +namespace webrtc { + +// A move-only class that holds an integer. This is designed for testing +// containers. See also CopyOnlyInt. +class MoveOnlyInt { + public: + explicit MoveOnlyInt(int data = 1) : data_(data) {} + MoveOnlyInt(const MoveOnlyInt& other) = delete; + MoveOnlyInt& operator=(const MoveOnlyInt& other) = delete; + MoveOnlyInt(MoveOnlyInt&& other) : data_(other.data_) { other.data_ = 0; } + ~MoveOnlyInt() { data_ = 0; } + + MoveOnlyInt& operator=(MoveOnlyInt&& other) { + data_ = other.data_; + other.data_ = 0; + return *this; + } + + friend bool operator==(const MoveOnlyInt& lhs, const MoveOnlyInt& rhs) { + return lhs.data_ == rhs.data_; + } + + friend bool operator!=(const MoveOnlyInt& lhs, const MoveOnlyInt& rhs) { + return !operator==(lhs, rhs); + } + + friend bool operator<(const MoveOnlyInt& lhs, int rhs) { + return lhs.data_ < rhs; + } + + friend bool operator<(int lhs, const MoveOnlyInt& rhs) { + return lhs < rhs.data_; + } + + friend bool operator<(const MoveOnlyInt& lhs, const MoveOnlyInt& rhs) { + return lhs.data_ < rhs.data_; + } + + friend bool operator>(const MoveOnlyInt& lhs, const MoveOnlyInt& rhs) { + return rhs < lhs; + } + + friend bool operator<=(const MoveOnlyInt& lhs, const MoveOnlyInt& rhs) { + return !(rhs < lhs); + } + + friend bool operator>=(const MoveOnlyInt& lhs, const MoveOnlyInt& rhs) { + return !(lhs < rhs); + } + + int data() const { return data_; } + + private: + volatile int data_; +}; + +} // namespace webrtc + +#endif // RTC_BASE_CONTAINERS_MOVE_ONLY_INT_H_ |