Replace std::list with an intrusive list in raw_linked_hash_set. Storing elements in std::list forces temporary donor lists on emplace and extract and couples node handles to std::list. Allocate intrusive doubly-linked list nodes directly with a circular sentinel so node handles own raw nodes and support incomplete recursive value types. Keep indexing node pointers in absl::flat_hash_set as an intermediate step before switching the hash index to raw_hash_set. PiperOrigin-RevId: 1023620041
diff --git a/CMake/AbseilDll.cmake b/CMake/AbseilDll.cmake index 253898d..407b72a 100644 --- a/CMake/AbseilDll.cmake +++ b/CMake/AbseilDll.cmake
@@ -100,6 +100,7 @@ "container/internal/raw_hash_set.cc" "container/internal/raw_hash_set.h" "container/internal/raw_hash_set_resize_impl.h" + "container/internal/raw_linked_hash_set.h" "container/linked_hash_map.h" "container/linked_hash_set.h" "container/node_hash_map.h"
diff --git a/absl/container/BUILD.bazel b/absl/container/BUILD.bazel index fbf0d56..e002288 100644 --- a/absl/container/BUILD.bazel +++ b/absl/container/BUILD.bazel
@@ -1374,16 +1374,42 @@ ) cc_library( + name = "raw_linked_hash_set", + hdrs = ["internal/raw_linked_hash_set.h"], + copts = ABSL_DEFAULT_COPTS, + linkopts = ABSL_DEFAULT_LINKOPTS, + visibility = ["//absl/container:__pkg__"], + deps = [ + ":common", + ":flat_hash_set", + ":hash_container_defaults", + "//absl/base:config", + "//absl/base:core_headers", + ], +) + +cc_test( + name = "raw_linked_hash_set_test", + srcs = ["internal/raw_linked_hash_set_test.cc"], + copts = ABSL_TEST_COPTS, + linkopts = ABSL_DEFAULT_LINKOPTS, + deps = [ + ":raw_linked_hash_set", + "//absl/base:config", + "@googletest//:gtest", + "@googletest//:gtest_main", + ], +) + +cc_library( name = "linked_hash_set", hdrs = ["linked_hash_set.h"], copts = ABSL_DEFAULT_COPTS, linkopts = ABSL_DEFAULT_LINKOPTS, visibility = ["//visibility:public"], deps = [ - ":common", - ":flat_hash_set", + ":raw_linked_hash_set", "//absl/base:config", - "//absl/base:core_headers", ], ) @@ -1434,8 +1460,7 @@ linkopts = ABSL_DEFAULT_LINKOPTS, visibility = ["//visibility:public"], deps = [ - ":common", - ":flat_hash_set", + ":raw_linked_hash_set", "//absl/base:config", "//absl/base:core_headers", "//absl/base:throw_delegate",
diff --git a/absl/container/CMakeLists.txt b/absl/container/CMakeLists.txt index 2d234aa..4a8d3b8 100644 --- a/absl/container/CMakeLists.txt +++ b/absl/container/CMakeLists.txt
@@ -1156,6 +1156,40 @@ TESTONLY ) +# Internal-only target, do not depend on directly. +absl_cc_library( + NAME + raw_linked_hash_set + HDRS + "internal/raw_linked_hash_set.h" + COPTS + ${ABSL_DEFAULT_COPTS} + LINKOPTS + ${ABSL_DEFAULT_LINKOPTS} + DEPS + absl::config + absl::container_common + absl::core_headers + absl::flat_hash_set + absl::hash_container_defaults + PUBLIC +) + +absl_cc_test( + NAME + raw_linked_hash_set_test + SRCS + "internal/raw_linked_hash_set_test.cc" + COPTS + ${ABSL_TEST_COPTS} + LINKOPTS + ${ABSL_DEFAULT_LINKOPTS} + DEPS + absl::config + absl::raw_linked_hash_set + GTest::gmock_main +) + absl_cc_library( NAME linked_hash_set @@ -1167,9 +1201,7 @@ ${ABSL_DEFAULT_LINKOPTS} DEPS absl::config - absl::container_common - absl::core_headers - absl::flat_hash_set + absl::raw_linked_hash_set ) absl_cc_test( @@ -1208,9 +1240,8 @@ ${ABSL_DEFAULT_LINKOPTS} DEPS absl::config - absl::container_common absl::core_headers - absl::flat_hash_set + absl::raw_linked_hash_set absl::throw_delegate )
diff --git a/absl/container/internal/raw_linked_hash_set.h b/absl/container/internal/raw_linked_hash_set.h new file mode 100644 index 0000000..373ec4c --- /dev/null +++ b/absl/container/internal/raw_linked_hash_set.h
@@ -0,0 +1,1016 @@ +// Copyright 2025 The Abseil Authors. +// +// Licensed under the Apache License, Version 2.0 (the "License"); +// you may not use this file except in compliance with the License. +// You may obtain a copy of the License at +// +// https://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, software +// distributed under the License is distributed on an "AS IS" BASIS, +// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +// See the License for the specific language governing permissions and +// limitations under the License. + +#ifndef ABSL_CONTAINER_INTERNAL_RAW_LINKED_HASH_SET_H_ +#define ABSL_CONTAINER_INTERNAL_RAW_LINKED_HASH_SET_H_ + +#include <cassert> +#include <cstddef> +#include <cstdint> +#include <initializer_list> +#include <iterator> +#include <memory> +#include <new> +#include <optional> +#include <tuple> +#include <type_traits> +#include <utility> + +#include "absl/base/attributes.h" +#include "absl/base/config.h" +#include "absl/container/flat_hash_set.h" +#include "absl/container/hash_container_defaults.h" +#include "absl/container/internal/common.h" + +namespace absl { +ABSL_NAMESPACE_BEGIN +namespace container_internal { + +template <typename Policy, typename... Params> +class raw_linked_hash_set; + +template <typename Policy, typename Hash, typename Eq, typename Alloc> +struct InstantiateRawLinkedHashSet { + using type = typename ApplyWithoutDefaultSuffix< + raw_linked_hash_set, + TypeList<void, typename Policy::DefaultHash, typename Policy::DefaultEq, + typename Policy::DefaultAlloc>, + TypeList<Policy, Hash, Eq, Alloc>>::type; +}; + +// Intrusive doubly-linked list pointers storing node addresses, or a shifted +// sentinel address for the list end. +struct LinkedListLink { + void* prev; + void* next; +}; + +// Heap-allocated list node placing the element storage union at offset 0, +// followed by any alignment padding and the intrusive list pointers: +// +// [ ValueStorage | padding | LinkedListLink (prev, next) ] +template <typename ValueType> +struct LinkedListNode { + // Union deferring element construction and destruction to the allocator. + union ValueStorage { + ValueStorage() noexcept {} + ~ValueStorage() noexcept {} + ValueType value; + }; + + LinkedListNode() noexcept = default; + ~LinkedListNode() noexcept = default; + +#if defined(__GNUC__) || defined(__clang__) +#pragma GCC diagnostic push +#pragma GCC diagnostic ignored "-Winvalid-offsetof" +#endif + static constexpr size_t LinkOffset() noexcept { + static_assert(offsetof(LinkedListNode, storage) == 0); + return offsetof(LinkedListNode, link); + } +#if defined(__GNUC__) || defined(__clang__) +#pragma GCC diagnostic pop +#endif + + // Steps from a node address or shifted sentinel address to its list link. + static LinkedListLink* LinkOf(void* ptr) noexcept { + return reinterpret_cast<LinkedListLink*>( + reinterpret_cast<uintptr_t>(ptr) + LinkOffset()); + } + static const LinkedListLink* LinkOf(const void* ptr) noexcept { + return reinterpret_cast<const LinkedListLink*>( + reinterpret_cast<uintptr_t>(ptr) + LinkOffset()); + } + + // Returns the shifted address whose link offset lands on the sentinel. + static void* SentinelPtr(const LinkedListLink* sentinel) noexcept { + return reinterpret_cast<void*>( + reinterpret_cast<uintptr_t>(sentinel) - LinkOffset()); + } + + static void LinkBefore(void* pos, LinkedListNode* node) noexcept { + LinkedListLink* pos_link = LinkOf(pos); + node->link.prev = pos_link->prev; + node->link.next = pos; + LinkOf(pos_link->prev)->next = node; + pos_link->prev = node; + } + + static void Unlink(LinkedListNode* node) noexcept { + LinkOf(node->link.prev)->next = node->link.next; + LinkOf(node->link.next)->prev = node->link.prev; + } + + // Allocates a node and constructs its element in place via the rebound + // allocator, leaving the link pointers uninitialized for the caller to link. + template <typename Alloc, typename... Args> + static LinkedListNode* New(const Alloc& alloc, Args&&... args) { + using NodeAlloc = typename std::allocator_traits< + Alloc>::template rebind_alloc<LinkedListNode>; + using NodeAllocTraits = std::allocator_traits<NodeAlloc>; + NodeAlloc node_alloc(alloc); + LinkedListNode* node = NodeAllocTraits::allocate(node_alloc, 1); + ::new (static_cast<void*>(node)) LinkedListNode(); + NodeAllocTraits::construct(node_alloc, std::addressof(node->storage.value), + std::forward<Args>(args)...); + return node; + } + + // Destroys the element and deallocates the node via the rebound allocator. + // The node must already be unlinked from any list. + template <typename Alloc> + static void Delete(const Alloc& alloc, LinkedListNode* node) noexcept { + using NodeAlloc = typename std::allocator_traits< + Alloc>::template rebind_alloc<LinkedListNode>; + using NodeAllocTraits = std::allocator_traits<NodeAlloc>; + NodeAlloc node_alloc(alloc); + NodeAllocTraits::destroy(node_alloc, std::addressof(node->storage.value)); + node->~LinkedListNode(); + NodeAllocTraits::deallocate(node_alloc, node, 1); + } + + ValueStorage storage; + LinkedListLink link; +}; + +// Circular head/tail sentinel owning the endpoints of an intrusive list. +template <typename ValueType> +struct LinkedListSentinel { + using Node = LinkedListNode<ValueType>; + + LinkedListLink head; + + LinkedListSentinel() noexcept { Reset(); } + LinkedListSentinel(const LinkedListSentinel&) = delete; + LinkedListSentinel& operator=(const LinkedListSentinel&) = delete; + + void* EndPtr() const noexcept { return Node::SentinelPtr(&head); } + + void Reset() noexcept { + void* end = EndPtr(); + head.prev = end; + head.next = end; + } + + bool empty() const noexcept { return head.next == EndPtr(); } + + // Moves all nodes from another distinct sentinel into this empty sentinel. + void TakeFrom(LinkedListSentinel& other) noexcept { + if (other.empty()) { + Reset(); + return; + } + void* end = EndPtr(); + head.next = other.head.next; + head.prev = other.head.prev; + Node::LinkOf(head.next)->prev = end; + Node::LinkOf(head.prev)->next = end; + other.Reset(); + } + + // Swaps the node chains of two distinct sentinels. + void Swap(LinkedListSentinel& other) noexcept { + LinkedListSentinel tmp; + tmp.TakeFrom(*this); + TakeFrom(other); + other.TakeFrom(tmp); + } +}; + +// Trivially copyable bidirectional iterator over intrusive list nodes. +template <typename ValueType, bool IsConst> +class LinkedListIterator { + using VoidPtr = std::conditional_t<IsConst, const void*, void*>; + using Node = LinkedListNode<ValueType>; + using NodePtr = std::conditional_t<IsConst, const Node*, Node*>; + + public: + using iterator_category = std::bidirectional_iterator_tag; + using value_type = ValueType; + using difference_type = ptrdiff_t; + using pointer = std::conditional_t<IsConst, const ValueType*, ValueType*>; + using reference = std::conditional_t<IsConst, const ValueType&, ValueType&>; + + constexpr LinkedListIterator() noexcept = default; + + // Implicitly converts mutable iterators to const iterators. + template <bool OtherConst, + std::enable_if_t<IsConst && !OtherConst, int> = 0> + // NOLINTNEXTLINE(google-explicit-constructor) + constexpr LinkedListIterator( + const LinkedListIterator<ValueType, OtherConst>& other) noexcept + : ptr_(other.ptr_) {} + + reference operator*() const noexcept { + return static_cast<NodePtr>(ptr_)->storage.value; + } + pointer operator->() const noexcept { + return std::addressof(static_cast<NodePtr>(ptr_)->storage.value); + } + + LinkedListIterator& operator++() noexcept { + ptr_ = Node::LinkOf(ptr_)->next; + return *this; + } + LinkedListIterator operator++(int) noexcept { + LinkedListIterator tmp = *this; + ptr_ = Node::LinkOf(ptr_)->next; + return tmp; + } + LinkedListIterator& operator--() noexcept { + ptr_ = Node::LinkOf(ptr_)->prev; + return *this; + } + LinkedListIterator operator--(int) noexcept { + LinkedListIterator tmp = *this; + ptr_ = Node::LinkOf(ptr_)->prev; + return tmp; + } + + friend bool operator==(LinkedListIterator a, LinkedListIterator b) noexcept { + return a.ptr_ == b.ptr_; + } + friend bool operator!=(LinkedListIterator a, LinkedListIterator b) noexcept { + return a.ptr_ != b.ptr_; + } + + private: + template <typename, bool> + friend class LinkedListIterator; + template <typename, typename...> + friend class raw_linked_hash_set; + + explicit constexpr LinkedListIterator(VoidPtr ptr) noexcept : ptr_(ptr) {} + + VoidPtr ptr_ = nullptr; +}; + +template <typename Policy, typename... Params> +class LinkedHashNodeHandle; + +template <typename Policy, typename Alloc> +struct InstantiateLinkedHashNodeHandle { + using type = typename ApplyWithoutDefaultSuffix< + LinkedHashNodeHandle, TypeList<void, typename Policy::DefaultAlloc>, + TypeList<Policy, Alloc>>::type; +}; + +template <typename Derived, typename Policy, bool kIsMap = Policy::kIsMap> +class LinkedHashNodeHandleAccess { + public: + using key_type = typename Policy::key_type; + using mapped_type = typename Policy::mapped_type; + + const key_type& key() const { + return static_cast<const Derived*>(this)->node_->storage.value.first; + } + mapped_type& mapped() const { + return static_cast<const Derived*>(this)->node_->storage.value.second; + } +}; + +template <typename Derived, typename Policy> +class LinkedHashNodeHandleAccess<Derived, Policy, /*kIsMap=*/false> { + public: + using value_type = typename Policy::value_type; + + value_type& value() const { + return static_cast<const Derived*>(this)->node_->storage.value; + } +}; + +// Owning node handle for linked hash containers, independent of hash and +// equality functor types so nodes can be transferred across heterogeneous +// container specializations. +template <typename Policy, typename... Params> +class LinkedHashNodeHandle + : public LinkedHashNodeHandleAccess<LinkedHashNodeHandle<Policy, Params...>, + Policy> { + using Node = LinkedListNode<typename Policy::value_type>; + using Alloc = GetFromListOr<typename Policy::DefaultAlloc, 0, Params...>; + + static_assert( + std::is_same_v< + typename InstantiateLinkedHashNodeHandle<Policy, Alloc>::type, + LinkedHashNodeHandle>, + "Redundant template parameters were passed. Use " + "InstantiateLinkedHashNodeHandle<> instead"); + + public: + using allocator_type = Alloc; + + constexpr LinkedHashNodeHandle() noexcept = default; + LinkedHashNodeHandle(LinkedHashNodeHandle&& other) noexcept + : node_(std::exchange(other.node_, nullptr)), + alloc_(std::move(other.alloc_)) { + other.alloc_.reset(); + } + ~LinkedHashNodeHandle() { Destroy(); } + LinkedHashNodeHandle& operator=(LinkedHashNodeHandle&& other) noexcept { + if (this == &other) return *this; + Destroy(); + if (!other.empty()) { + node_ = std::exchange(other.node_, nullptr); + alloc_.emplace(std::move(*other.alloc_)); + other.alloc_.reset(); + } + return *this; + } + + bool empty() const noexcept { return node_ == nullptr; } + explicit operator bool() const noexcept { return !empty(); } + allocator_type get_allocator() const { return *alloc_; } + + void swap(LinkedHashNodeHandle& other) noexcept { + if (this == &other) return; + using std::swap; + swap(node_, other.node_); + swap(alloc_, other.alloc_); + } + friend void swap(LinkedHashNodeHandle& a, LinkedHashNodeHandle& b) noexcept { + a.swap(b); + } + + private: + friend class LinkedHashNodeHandleAccess<LinkedHashNodeHandle, Policy>; + template <typename, typename...> + friend class raw_linked_hash_set; + + LinkedHashNodeHandle(Node* node, const allocator_type& alloc) + : node_(node), alloc_(alloc) {} + + Node* Release() noexcept { + alloc_.reset(); + return std::exchange(node_, nullptr); + } + + void Destroy() noexcept { + if (node_ != nullptr) { + Node::Delete(*alloc_, node_); + node_ = nullptr; + alloc_.reset(); + } + } + + Node* node_ = nullptr; + std::optional<allocator_type> alloc_; +}; + +template <typename Key> +struct LinkedHashSetPolicy { + using key_type = Key; + using value_type = Key; + using DefaultHash = absl::DefaultHashContainerHash<Key>; + using DefaultEq = absl::DefaultHashContainerEq<Key>; + using DefaultAlloc = std::allocator<Key>; + static constexpr bool kIsMap = false; + + template <typename V> + static const V& key(const V& v) { + return v; + } +}; + +template <typename Key, typename Value> +struct LinkedHashMapPolicy { + using key_type = Key; + using mapped_type = Value; + using value_type = std::pair<const key_type, mapped_type>; + using DefaultHash = absl::DefaultHashContainerHash<Key>; + using DefaultEq = absl::DefaultHashContainerEq<Key>; + using DefaultAlloc = std::allocator<value_type>; + static constexpr bool kIsMap = true; + + static const key_type& key(const value_type& v) { return v.first; } +}; + +// Shared container implementation backing linked hash sets and maps. +template <typename Policy, typename... Params> +class raw_linked_hash_set { + using Hash = GetFromListOr<typename Policy::DefaultHash, 0, Params...>; + using Eq = GetFromListOr<typename Policy::DefaultEq, 1, Params...>; + using Alloc = GetFromListOr<typename Policy::DefaultAlloc, 2, Params...>; + + static_assert( + std::is_same_v< + typename InstantiateRawLinkedHashSet<Policy, Hash, Eq, Alloc>::type, + raw_linked_hash_set>, + "Redundant template parameters were passed. Use " + "InstantiateRawLinkedHashSet<> instead"); + + protected: + static constexpr bool kIsTransparent = + IsTransparent<Eq>::value && IsTransparent<Hash>::value; + using KeyArgImpl = KeyArg<kIsTransparent>; + + public: + using key_type = typename Policy::key_type; + using value_type = typename Policy::value_type; + using hasher = Hash; + using key_equal = Eq; + using allocator_type = Alloc; + using difference_type = ptrdiff_t; + using size_type = typename std::allocator_traits<allocator_type>::size_type; + using pointer = typename std::allocator_traits<allocator_type>::pointer; + using const_pointer = + typename std::allocator_traits<allocator_type>::const_pointer; + using reference = value_type&; + using const_reference = const value_type&; + using iterator = LinkedListIterator<value_type, /*IsConst=*/!Policy::kIsMap>; + using const_iterator = LinkedListIterator<value_type, /*IsConst=*/true>; + using reverse_iterator = std::reverse_iterator<iterator>; + using const_reverse_iterator = std::reverse_iterator<const_iterator>; + using node_type = + typename InstantiateLinkedHashNodeHandle<Policy, allocator_type>::type; + using insert_return_type = InsertReturnType<iterator, node_type>; + + protected: + template <class K> + using key_arg = typename KeyArgImpl::template Select<K, key_type>; + + using Node = LinkedListNode<value_type>; + + template <class Fn> + class Wrapped { + template <typename K> + static const K& ToKey(const K& k) { + return k; + } + static const key_type& ToKey(Node* node) { + return Policy::key(node->storage.value); + } + static const key_type& ToKey(const Node* node) { + return Policy::key(node->storage.value); + } + + Fn fn_; + + friend raw_linked_hash_set; + + public: + using is_transparent = void; + + Wrapped() = default; + explicit Wrapped(Fn fn) : fn_(std::move(fn)) {} + + template <class... Args> + auto operator()(Args&&... args) const + -> decltype(this->fn_(ToKey(args)...)) { + return fn_(ToKey(args)...); + } + }; + + using NodePtrAlloc = typename std::allocator_traits< + allocator_type>::template rebind_alloc<Node*>; + using SetType = absl::flat_hash_set<Node*, Wrapped<hasher>, + Wrapped<key_equal>, NodePtrAlloc>; + + public: + raw_linked_hash_set() = default; + + explicit raw_linked_hash_set(size_t reservation_size, + const hasher& hash = hasher(), + const key_equal& eq = key_equal(), + const allocator_type& alloc = allocator_type()) + : set_(reservation_size, Wrapped<hasher>(hash), Wrapped<key_equal>(eq), + NodePtrAlloc(alloc)) {} + + raw_linked_hash_set(size_t reservation_size, const hasher& hash, + const allocator_type& alloc) + : raw_linked_hash_set(reservation_size, hash, key_equal(), alloc) {} + + raw_linked_hash_set(size_t reservation_size, const allocator_type& alloc) + : raw_linked_hash_set(reservation_size, hasher(), key_equal(), alloc) {} + + explicit raw_linked_hash_set(const allocator_type& alloc) + : raw_linked_hash_set(0, hasher(), key_equal(), alloc) {} + + template <class InputIt> + raw_linked_hash_set(InputIt first, InputIt last, size_t reservation_size = 0, + const hasher& hash = hasher(), + const key_equal& eq = key_equal(), + const allocator_type& alloc = allocator_type()) + : raw_linked_hash_set(reservation_size, hash, eq, alloc) { + insert(first, last); + } + + template <class InputIt> + raw_linked_hash_set(InputIt first, InputIt last, size_t reservation_size, + const hasher& hash, const allocator_type& alloc) + : raw_linked_hash_set(first, last, reservation_size, hash, key_equal(), + alloc) {} + + template <class InputIt> + raw_linked_hash_set(InputIt first, InputIt last, size_t reservation_size, + const allocator_type& alloc) + : raw_linked_hash_set(first, last, reservation_size, hasher(), + key_equal(), alloc) {} + + template <class InputIt> + raw_linked_hash_set(InputIt first, InputIt last, const allocator_type& alloc) + : raw_linked_hash_set(first, last, /*reservation_size=*/0, hasher(), + key_equal(), alloc) {} + + raw_linked_hash_set(std::initializer_list<value_type> init, + size_t reservation_size = 0, + const hasher& hash = hasher(), + const key_equal& eq = key_equal(), + const allocator_type& alloc = allocator_type()) + : raw_linked_hash_set(init.begin(), init.end(), reservation_size, hash, + eq, alloc) {} + + raw_linked_hash_set(std::initializer_list<value_type> init, + size_t reservation_size, const hasher& hash, + const allocator_type& alloc) + : raw_linked_hash_set(init, reservation_size, hash, key_equal(), alloc) {} + + raw_linked_hash_set(std::initializer_list<value_type> init, + size_t reservation_size, const allocator_type& alloc) + : raw_linked_hash_set(init, reservation_size, hasher(), key_equal(), + alloc) {} + + raw_linked_hash_set(std::initializer_list<value_type> init, + const allocator_type& alloc) + : raw_linked_hash_set(init, /*reservation_size=*/0, hasher(), key_equal(), + alloc) {} + + raw_linked_hash_set(const raw_linked_hash_set& other) + : raw_linked_hash_set(0, other.hash_function(), other.key_eq(), + other.get_allocator()) { + reserve(other.size()); + CopyFrom(other); + } + + raw_linked_hash_set(const raw_linked_hash_set& other, + const allocator_type& alloc) + : raw_linked_hash_set(0, other.hash_function(), other.key_eq(), alloc) { + reserve(other.size()); + CopyFrom(other); + } + + raw_linked_hash_set(raw_linked_hash_set&& other) noexcept + : set_(std::move(other.set_)) { + // Reset the moved-from hash index so the source remains valid and empty. + other.set_.clear(); + sentinel_.TakeFrom(other.sentinel_); + } + + raw_linked_hash_set(raw_linked_hash_set&& other, const allocator_type& alloc) + : raw_linked_hash_set(0, other.hash_function(), other.key_eq(), alloc) { + if (get_allocator() == other.get_allocator()) { + set_ = std::move(other.set_); + other.set_.clear(); + sentinel_.TakeFrom(other.sentinel_); + } else { + reserve(other.size()); + CopyFrom(std::move(other)); + } + } + + ~raw_linked_hash_set() { + void* cur = sentinel_.head.next; + void* end = sentinel_.EndPtr(); + sentinel_.Reset(); + DeleteList(cur, end); + } + + raw_linked_hash_set& operator=(const raw_linked_hash_set& other) { + if (this != &other) { + // Destroy existing nodes before the hash index may replace its allocator. + clear(); + const SetType empty_set(0, other.set_.hash_function(), + other.set_.key_eq(), other.set_.get_allocator()); + set_ = empty_set; + set_.reserve(other.size()); + CopyFrom(other); + } + return *this; + } + + raw_linked_hash_set& operator=(raw_linked_hash_set&& other) noexcept { + if (this != &other) { + using AllocTraits = std::allocator_traits<allocator_type>; + constexpr bool kStealUnconditionally = + AllocTraits::propagate_on_container_move_assignment::value || + AllocTraits::is_always_equal::value; + if (kStealUnconditionally || get_allocator() == other.get_allocator()) { + // Destroy existing nodes before the hash index may replace its + // allocator. + clear(); + set_ = std::move(other.set_); + other.set_.clear(); + sentinel_.TakeFrom(other.sentinel_); + } else if constexpr (!kStealUnconditionally) { + // The allocators are unequal and do not propagate, so move each + // element into a new node allocated with this container's allocator + // and rebuild the index over them, adopting other's hash and equality. + clear(); + set_ = SetType(0, other.set_.hash_function(), other.set_.key_eq(), + set_.get_allocator()); + set_.reserve(other.size()); + CopyFrom(std::move(other)); + } + } + return *this; + } + + raw_linked_hash_set& operator=(std::initializer_list<value_type> values) { + clear(); + reserve(values.size()); + insert(values.begin(), values.end()); + return *this; + } + + size_type size() const { return set_.size(); } + size_type max_size() const noexcept { return ~size_type{}; } + bool empty() const { return set_.empty(); } + + // Iteration is list-like, in insertion order. + iterator begin() { return iterator(sentinel_.head.next); } + iterator end() { return iterator(sentinel_.EndPtr()); } + const_iterator begin() const { return const_iterator(sentinel_.head.next); } + const_iterator end() const { return const_iterator(sentinel_.EndPtr()); } + const_iterator cbegin() const { return begin(); } + const_iterator cend() const { return end(); } + reverse_iterator rbegin() { return reverse_iterator(end()); } + reverse_iterator rend() { return reverse_iterator(begin()); } + const_reverse_iterator rbegin() const { + return const_reverse_iterator(end()); + } + const_reverse_iterator rend() const { + return const_reverse_iterator(begin()); + } + const_reverse_iterator crbegin() const { return rbegin(); } + const_reverse_iterator crend() const { return rend(); } + + reference front() { + assert(!empty()); + return static_cast<Node*>(sentinel_.head.next)->storage.value; + } + reference back() { + assert(!empty()); + return static_cast<Node*>(sentinel_.head.prev)->storage.value; + } + const_reference front() const { + assert(!empty()); + return static_cast<const Node*>(sentinel_.head.next)->storage.value; + } + const_reference back() const { + assert(!empty()); + return static_cast<const Node*>(sentinel_.head.prev)->storage.value; + } + + void pop_front() { erase(begin()); } + void pop_back() { erase(std::prev(end())); } + + ABSL_ATTRIBUTE_REINITIALIZES void clear() { + void* cur = sentinel_.head.next; + void* end = sentinel_.EndPtr(); + sentinel_.Reset(); + set_.clear(); + DeleteList(cur, end); + } + + void reserve(size_t n) { set_.reserve(n); } + size_t capacity() const { return set_.capacity(); } + size_t bucket_count() const { return set_.bucket_count(); } + float load_factor() const { return set_.load_factor(); } + + hasher hash_function() const { return set_.hash_function().fn_; } + key_equal key_eq() const { return set_.key_eq().fn_; } + allocator_type get_allocator() const { + return allocator_type(set_.get_allocator()); + } + + template <class K = key_type> + size_type erase(const key_arg<K>& key) { + auto found = set_.find(key); + if (found == set_.end()) return 0; + Node* node = static_cast<Node*>(*found); + // Erase the hash entry before destroying the node it references. + set_.erase(found); + Node::Unlink(node); + Node::Delete(set_.get_allocator(), node); + return 1; + } + + iterator erase(const_iterator position) { + Node* node = static_cast<Node*>(RawPtr(position)); + auto found = set_.find(Policy::key(node->storage.value)); + assert(found != set_.end() && *found == node); + set_.erase(found); + void* next = node->link.next; + Node::Unlink(node); + Node::Delete(set_.get_allocator(), node); + return iterator(next); + } + + template <bool kMap = Policy::kIsMap, std::enable_if_t<kMap, int> = 0> + iterator erase(iterator position) { + return erase(static_cast<const_iterator>(position)); + } + + template <bool kMap = Policy::kIsMap, std::enable_if_t<kMap, int> = 0> + iterator erase(iterator first, iterator last) { + while (first != last) first = erase(first); + return first; + } + + iterator erase(const_iterator first, const_iterator last) { + while (first != last) first = erase(first); + return iterator(RawPtr(first)); + } + + template <class K = key_type> + iterator find(const key_arg<K>& key) { + auto found = set_.find(key); + if (found == set_.end()) return end(); + return iterator(*found); + } + + template <class K = key_type> + const_iterator find(const key_arg<K>& key) const { + auto found = set_.find(key); + if (found == set_.end()) return end(); + return const_iterator(*found); + } + + template <class K = key_type> + size_type count(const key_arg<K>& key) const { + return contains(key) ? 1 : 0; + } + template <class K = key_type> + bool contains(const key_arg<K>& key) const { + return set_.contains(key); + } + + template <class K = key_type> + std::pair<iterator, iterator> equal_range(const key_arg<K>& key) { + auto iter = find(key); + if (iter == end()) return {end(), end()}; + return {iter, std::next(iter)}; + } + + template <class K = key_type> + std::pair<const_iterator, const_iterator> equal_range( + const key_arg<K>& key) const { + auto iter = find(key); + if (iter == end()) return {end(), end()}; + return {iter, std::next(iter)}; + } + + void insert(std::initializer_list<value_type> ilist) { + insert(ilist.begin(), ilist.end()); + } + + template <class InputIt> + void insert(InputIt first, InputIt last) { + for (; first != last; ++first) InsertRangeElement(*first); + } + + insert_return_type insert(node_type&& node) { + if (node.empty()) return {end(), false, node_type()}; + assert(get_allocator() == node.get_allocator()); + auto [set_iter, inserted] = set_.insert(node.node_); + if (!inserted) { + return {iterator(*set_iter), false, std::move(node)}; + } + Node* n = node.Release(); + Node::LinkBefore(sentinel_.EndPtr(), n); + return {iterator(n), true, node_type()}; + } + + iterator insert(const_iterator, node_type&& node) { + return insert(std::move(node)).position; + } + + template <typename... Args> + std::pair<iterator, bool> emplace(Args&&... args) { + return EmplaceAt(end(), std::forward<Args>(args)...); + } + + template <typename... Args> + iterator emplace_hint(const_iterator hint, Args&&... args) { + return EmplaceAt(Policy::kIsMap ? end() : hint, std::forward<Args>(args)...) + .first; + } + + template < + typename... OtherParams, + typename = std::enable_if_t<std::is_same_v< + Alloc, typename raw_linked_hash_set< + Policy, OtherParams...>::allocator_type>>> + void merge(raw_linked_hash_set<Policy, OtherParams...>& src) { + auto itr = src.begin(); + while (itr != src.end()) { + if (contains(Policy::key(*itr))) { + ++itr; + } else { + insert(src.extract(itr++)); + } + } + } + + template < + typename... OtherParams, + typename = std::enable_if_t<std::is_same_v< + Alloc, typename raw_linked_hash_set< + Policy, OtherParams...>::allocator_type>>> + void merge(raw_linked_hash_set<Policy, OtherParams...>&& src) { + merge(src); + } + + node_type extract(const_iterator position) { + Node* node = static_cast<Node*>(RawPtr(position)); + auto found = set_.find(Policy::key(node->storage.value)); + assert(found != set_.end() && *found == node); + set_.erase(found); + Node::Unlink(node); + return node_type(node, get_allocator()); + } + + template <class K = key_type, + std::enable_if_t<!std::is_same_v<K, iterator>, int> = 0> + node_type extract(const key_arg<K>& key) { + auto found = set_.find(key); + if (found == set_.end()) return node_type(); + Node* node = static_cast<Node*>(*found); + set_.erase(found); + Node::Unlink(node); + return node_type(node, get_allocator()); + } + + void swap(raw_linked_hash_set& other) noexcept { + if (this == &other) return; + set_.swap(other.set_); + sentinel_.Swap(other.sentinel_); + } + + friend bool operator==(const raw_linked_hash_set& a, + const raw_linked_hash_set& b) { + if (a.size() != b.size()) return false; + const raw_linked_hash_set* outer = &a; + const raw_linked_hash_set* inner = &b; + if (outer->capacity() > inner->capacity()) std::swap(outer, inner); + for (const value_type& elem : *outer) { + if constexpr (Policy::kIsMap) { + auto it = inner->find(elem.first); + if (it == inner->end()) return false; + if (it->second != elem.second) return false; + } else { + if (!inner->contains(elem)) return false; + } + } + return true; + } + + friend bool operator!=(const raw_linked_hash_set& a, + const raw_linked_hash_set& b) { + return !(a == b); + } + + void rehash(size_t n) { set_.rehash(n); } + + protected: + template <typename, typename...> + friend class raw_linked_hash_set; + + static void* RawPtr(const_iterator it) noexcept { + return const_cast<void*>(it.ptr_); + } + + template <typename U> + std::pair<iterator, bool> InsertValueAt(const_iterator hint, U&& val) { + bool constructed = false; + auto set_iter = set_.lazy_emplace(Policy::key(val), [&](const auto& ctor) { + Node* node = Node::New(set_.get_allocator(), std::forward<U>(val)); + constructed = true; + ctor(node); + Node::LinkBefore(RawPtr(hint), node); + }); + return {iterator(*set_iter), constructed}; + } + + template <typename... Args> + std::pair<iterator, bool> EmplaceAt(const_iterator hint, Args&&... args) { + Node* node = Node::New(set_.get_allocator(), std::forward<Args>(args)...); + auto [set_iter, inserted] = set_.insert(node); + if (!inserted) { + Node::Delete(set_.get_allocator(), node); + return {iterator(*set_iter), false}; + } + Node::LinkBefore(RawPtr(hint), node); + return {iterator(node), true}; + } + + template <typename K, typename... Args> + std::pair<iterator, bool> LazyEmplaceMap(K&& key, Args&&... args) { + bool constructed = false; + auto set_iter = set_.lazy_emplace( + key, [this, &constructed, &key, &args...](const auto& ctor) { + Node* node = + Node::New(set_.get_allocator(), std::piecewise_construct, + std::forward_as_tuple(std::forward<K>(key)), + std::forward_as_tuple(std::forward<Args>(args)...)); + constructed = true; + ctor(node); + Node::LinkBefore(sentinel_.EndPtr(), node); + }); + return {iterator(*set_iter), constructed}; + } + + template <typename... OtherParams> + void SpliceFrom(raw_linked_hash_set<Policy, OtherParams...>& list, + const_iterator it) { + if constexpr (std::is_same_v<raw_linked_hash_set<Policy, OtherParams...>, + raw_linked_hash_set>) { + if (&list == this) { + Node* node = static_cast<Node*>(RawPtr(it)); + if (node != sentinel_.head.prev) { + Node::Unlink(node); + Node::LinkBefore(sentinel_.EndPtr(), node); + } + return; + } + } + insert(list.extract(it)); + } + + private: + void DeleteList(void* cur, void* end) noexcept { + while (cur != end) { + Node* node = static_cast<Node*>(cur); + cur = node->link.next; + Node::Delete(set_.get_allocator(), node); + } + } + + template <typename Elem> + void InsertRangeElement(Elem&& elem) { + if constexpr (Policy::kIsMap) { + InsertMapRangeElement(std::forward<Elem>(elem)); + } else { + InsertSetRangeElement(std::forward<Elem>(elem)); + } + } + + void InsertMapRangeElement(const value_type& v) { InsertValueAt(end(), v); } + void InsertMapRangeElement(value_type&& v) { + InsertValueAt(end(), std::move(v)); + } + + template <typename K = key_type> + void InsertSetRangeElement(const key_arg<K>& k) { + InsertValueAt(end(), k); + } + template <typename K = key_type, + std::enable_if_t<!std::is_reference_v<K>, int> = 0> + void InsertSetRangeElement(key_arg<K>&& k) { + InsertValueAt(end(), std::move(k)); + } + + template <typename Other> + void CopyFrom(Other&& other) { + constexpr bool kIsMove = !std::is_const_v<std::remove_reference_t<Other>>; + void* other_end = other.sentinel_.EndPtr(); + for (void* cur = other.sentinel_.head.next; cur != other_end; + cur = static_cast<Node*>(cur)->link.next) { + Node* src_node = static_cast<Node*>(cur); + if constexpr (kIsMove) { + InsertValueAt(end(), std::move(src_node->storage.value)); + } else { + InsertValueAt(end(), std::as_const(src_node->storage.value)); + } + } + if constexpr (kIsMove) { + // Moving elements in place invalidates the source hash index, so clear + // the source container to leave it consistent and empty. + other.clear(); + } + } + + // The hash index over allocated list nodes. + SetType set_; + + // Circular sentinel for the intrusive doubly-linked list maintaining + // insertion order. + LinkedListSentinel<value_type> sentinel_; +}; + +} // namespace container_internal +ABSL_NAMESPACE_END +} // namespace absl + +#endif // ABSL_CONTAINER_INTERNAL_RAW_LINKED_HASH_SET_H_
diff --git a/absl/container/internal/raw_linked_hash_set_test.cc b/absl/container/internal/raw_linked_hash_set_test.cc new file mode 100644 index 0000000..c9ecdd2 --- /dev/null +++ b/absl/container/internal/raw_linked_hash_set_test.cc
@@ -0,0 +1,125 @@ +// Copyright 2026 The Abseil Authors. +// +// Licensed under the Apache License, Version 2.0 (the "License"); +// you may not use this file except in compliance with the License. +// You may obtain a copy of the License at +// +// https://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, software +// distributed under the License is distributed on an "AS IS" BASIS, +// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +// See the License for the specific language governing permissions and +// limitations under the License. + +#include "absl/container/internal/raw_linked_hash_set.h" + +#include <memory> +#include <string> +#include <utility> +#include <vector> + +#include "gmock/gmock.h" +#include "gtest/gtest.h" +#include "absl/base/config.h" + +namespace absl { +ABSL_NAMESPACE_BEGIN +namespace container_internal { +namespace { + +using ::testing::ElementsAre; +using ::testing::Pair; + +std::vector<int> CollectValues(const LinkedListSentinel<int>& sentinel) { + std::vector<int> out; + const void* end = sentinel.EndPtr(); + for (const void* cur = sentinel.head.next; cur != end; + cur = static_cast<const LinkedListNode<int>*>(cur)->link.next) { + out.push_back(static_cast<const LinkedListNode<int>*>(cur)->storage.value); + } + return out; +} + +TEST(RawLinkedHashSetTest, IntrusiveListLinkAndSentinel) { + using Node = LinkedListNode<int>; + std::allocator<int> alloc; + LinkedListSentinel<int> a; + LinkedListSentinel<int> b; + EXPECT_TRUE(a.empty()); + + auto* n1 = Node::New(alloc, 10); + auto* n2 = Node::New(alloc, 20); + auto* n3 = Node::New(alloc, 30); + Node::LinkBefore(a.EndPtr(), n1); + Node::LinkBefore(a.EndPtr(), n2); + Node::LinkBefore(n2, n3); + EXPECT_THAT(CollectValues(a), ElementsAre(10, 30, 20)); + + b.TakeFrom(a); + EXPECT_TRUE(a.empty()); + EXPECT_THAT(CollectValues(b), ElementsAre(10, 30, 20)); + EXPECT_EQ(Node::LinkOf(b.head.next)->prev, b.EndPtr()); + EXPECT_EQ(Node::LinkOf(b.head.prev)->next, b.EndPtr()); + + auto* n4 = Node::New(alloc, 40); + Node::LinkBefore(a.EndPtr(), n4); + a.Swap(b); + EXPECT_THAT(CollectValues(a), ElementsAre(10, 30, 20)); + EXPECT_THAT(CollectValues(b), ElementsAre(40)); + EXPECT_EQ(Node::LinkOf(a.head.prev)->next, a.EndPtr()); + EXPECT_EQ(Node::LinkOf(b.head.prev)->next, b.EndPtr()); + + for (LinkedListSentinel<int>* list : {&a, &b}) { + while (!list->empty()) { + auto* node = static_cast<Node*>(list->head.next); + Node::Unlink(node); + Node::Delete(alloc, node); + } + } +} + +TEST(RawLinkedHashSetTest, RawLinkedHashSetAndMap) { + using RawSet = raw_linked_hash_set<LinkedHashSetPolicy<int>>; + using RawMap = raw_linked_hash_set<LinkedHashMapPolicy<int, std::string>>; + + RawSet s = {3, 1, 2}; + EXPECT_THAT(s, ElementsAre(3, 1, 2)); + EXPECT_EQ(s.front(), 3); + EXPECT_EQ(s.back(), 2); + + auto n1 = s.extract(1); + auto n2 = s.extract(2); + using std::swap; + swap(n1, n2); + EXPECT_EQ(n1.value(), 2); + EXPECT_EQ(n2.value(), 1); + n2.value() = 4; + EXPECT_TRUE(s.insert(std::move(n1)).inserted); + EXPECT_TRUE(s.insert(std::move(n2)).inserted); + EXPECT_THAT(s, ElementsAre(3, 2, 4)); + + RawMap m = {{3, "c"}, {1, "a"}, {2, "b"}}; + EXPECT_THAT(m, ElementsAre(Pair(3, "c"), Pair(1, "a"), Pair(2, "b"))); + auto mn = m.extract(1); + ASSERT_TRUE(mn); + EXPECT_EQ(mn.key(), 1); + mn.mapped() = "aa"; + EXPECT_TRUE(m.insert(std::move(mn)).inserted); + EXPECT_THAT(m, ElementsAre(Pair(3, "c"), Pair(2, "b"), Pair(1, "aa"))); + + struct alignas(64) AlignedVal { + int x; + }; + raw_linked_hash_set<LinkedHashMapPolicy<int, AlignedVal>> aligned_map; + aligned_map.emplace(1, AlignedVal{7}); + aligned_map.emplace(2, AlignedVal{9}); + EXPECT_EQ(aligned_map.rbegin()->second.x, 9); + aligned_map.pop_back(); + EXPECT_EQ(aligned_map.back().second.x, 7); +} + +} // namespace +} // namespace container_internal +ABSL_NAMESPACE_END +} // namespace absl
diff --git a/absl/container/linked_hash_map.h b/absl/container/linked_hash_map.h index b89e433..000e936 100644 --- a/absl/container/linked_hash_map.h +++ b/absl/container/linked_hash_map.h
@@ -32,380 +32,55 @@ #ifndef ABSL_CONTAINER_LINKED_HASH_MAP_H_ #define ABSL_CONTAINER_LINKED_HASH_MAP_H_ -#include <cassert> -#include <cstddef> #include <initializer_list> -#include <list> -#include <memory> -#include <string> -#include <tuple> #include <type_traits> #include <utility> -#include "absl/base/attributes.h" #include "absl/base/config.h" #include "absl/base/optimization.h" #include "absl/base/throw_delegate.h" -#include "absl/container/flat_hash_set.h" -#include "absl/container/internal/common.h" +#include "absl/container/internal/raw_linked_hash_set.h" // IWYU pragma: export namespace absl { ABSL_NAMESPACE_BEGIN -template <typename Key, typename Value, - typename KeyHash = typename absl::flat_hash_set<Key>::hasher, - typename KeyEq = - typename absl::flat_hash_set<Key, KeyHash>::key_equal, - typename Alloc = std::allocator<std::pair<const Key, Value>>> -class linked_hash_map { - using KeyArgImpl = absl::container_internal::KeyArg< - absl::container_internal::IsTransparent<KeyEq>::value && - absl::container_internal::IsTransparent<KeyHash>::value>; - - public: - using key_type = Key; - using mapped_type = Value; - using hasher = KeyHash; - using key_equal = KeyEq; - using value_type = std::pair<const key_type, mapped_type>; - using allocator_type = Alloc; - using difference_type = ptrdiff_t; - - private: +template < + typename Key, typename Value, + typename KeyHash = + typename container_internal::LinkedHashMapPolicy<Key, + Value>::DefaultHash, + typename KeyEq = + typename container_internal::LinkedHashMapPolicy<Key, Value>::DefaultEq, + typename Alloc = typename container_internal::LinkedHashMapPolicy< + Key, Value>::DefaultAlloc> +class linked_hash_map + : public container_internal::InstantiateRawLinkedHashSet< + container_internal::LinkedHashMapPolicy<Key, Value>, KeyHash, KeyEq, + Alloc>::type { + using Policy = container_internal::LinkedHashMapPolicy<Key, Value>; + using Base = typename linked_hash_map::raw_linked_hash_set; template <class K> - using key_arg = typename KeyArgImpl::template Select<K, key_type>; - - using ListType = std::list<value_type, Alloc>; - - template <class Fn> - class Wrapped { - template <typename K> - static const K& ToKey(const K& k) { - return k; - } - static const key_type& ToKey(typename ListType::const_iterator it) { - return it->first; - } - static const key_type& ToKey(typename ListType::iterator it) { - return it->first; - } - - Fn fn_; - - friend linked_hash_map; - - public: - using is_transparent = void; - - Wrapped() = default; - explicit Wrapped(Fn fn) : fn_(std::move(fn)) {} - - template <class... Args> - auto operator()(Args&&... args) const - -> decltype(this->fn_(ToKey(args)...)) { - return fn_(ToKey(args)...); - } - }; - using SetType = - absl::flat_hash_set<typename ListType::iterator, Wrapped<hasher>, - Wrapped<key_equal>, Alloc>; - - class NodeHandle { - public: - using key_type = linked_hash_map::key_type; - using mapped_type = linked_hash_map::mapped_type; - using allocator_type = linked_hash_map::allocator_type; - - constexpr NodeHandle() noexcept = default; - NodeHandle(NodeHandle&& nh) noexcept = default; - ~NodeHandle() = default; - NodeHandle& operator=(NodeHandle&& node) noexcept = default; - bool empty() const noexcept { return list_.empty(); } - explicit operator bool() const noexcept { return !empty(); } - allocator_type get_allocator() const { return list_.get_allocator(); } - const key_type& key() const { return list_.front().first; } - mapped_type& mapped() { return list_.front().second; } - void swap(NodeHandle& nh) noexcept { list_.swap(nh.list_); } - - private: - friend linked_hash_map; - - explicit NodeHandle(ListType list) : list_(std::move(list)) {} - ListType list_; - }; - - template <class Iterator, class NodeType> - struct InsertReturnType { - Iterator position; - bool inserted; - NodeType node; - }; + using key_arg = typename Base::template key_arg<K>; public: - using iterator = typename ListType::iterator; - using const_iterator = typename ListType::const_iterator; - using reverse_iterator = typename ListType::reverse_iterator; - using const_reverse_iterator = typename ListType::const_reverse_iterator; - using reference = typename ListType::reference; - using const_reference = typename ListType::const_reference; - using size_type = typename ListType::size_type; - using pointer = typename std::allocator_traits<allocator_type>::pointer; - using const_pointer = - typename std::allocator_traits<allocator_type>::const_pointer; - using node_type = NodeHandle; - using insert_return_type = InsertReturnType<iterator, node_type>; + using mapped_type = Value; + using typename Base::const_iterator; + using typename Base::iterator; + using typename Base::key_type; + using typename Base::value_type; - linked_hash_map() {} - - explicit linked_hash_map(size_t reservation_size, - const hasher& hash = hasher(), - const key_equal& eq = key_equal(), - const allocator_type& alloc = allocator_type()) - : set_(reservation_size, Wrapped<hasher>(hash), Wrapped<key_equal>(eq), - alloc), - list_(alloc) {} - - linked_hash_map(size_t reservation_size, const hasher& hash, - const allocator_type& alloc) - : linked_hash_map(reservation_size, hash, key_equal(), alloc) {} - - linked_hash_map(size_t reservation_size, const allocator_type& alloc) - : linked_hash_map(reservation_size, hasher(), key_equal(), alloc) {} - - explicit linked_hash_map(const allocator_type& alloc) - : linked_hash_map(0, hasher(), key_equal(), alloc) {} - - template <class InputIt> - linked_hash_map(InputIt first, InputIt last, size_t reservation_size = 0, - const hasher& hash = hasher(), - const key_equal& eq = key_equal(), - const allocator_type& alloc = allocator_type()) - : linked_hash_map(reservation_size, hash, eq, alloc) { - insert(first, last); - } - - template <class InputIt> - linked_hash_map(InputIt first, InputIt last, size_t reservation_size, - const hasher& hash, const allocator_type& alloc) - : linked_hash_map(first, last, reservation_size, hash, key_equal(), - alloc) {} - - template <class InputIt> - linked_hash_map(InputIt first, InputIt last, size_t reservation_size, - const allocator_type& alloc) - : linked_hash_map(first, last, reservation_size, hasher(), key_equal(), - alloc) {} - - template <class InputIt> - linked_hash_map(InputIt first, InputIt last, const allocator_type& alloc) - : linked_hash_map(first, last, /*reservation_size=*/0, hasher(), - key_equal(), alloc) {} - - linked_hash_map(std::initializer_list<value_type> init, - size_t reservation_size = 0, const hasher& hash = hasher(), - const key_equal& eq = key_equal(), - const allocator_type& alloc = allocator_type()) - : linked_hash_map(init.begin(), init.end(), reservation_size, hash, eq, - alloc) {} - - linked_hash_map(std::initializer_list<value_type> init, - size_t reservation_size, const hasher& hash, - const allocator_type& alloc) - : linked_hash_map(init, reservation_size, hash, key_equal(), alloc) {} - - linked_hash_map(std::initializer_list<value_type> init, - size_t reservation_size, const allocator_type& alloc) - : linked_hash_map(init, reservation_size, hasher(), key_equal(), alloc) {} - - linked_hash_map(std::initializer_list<value_type> init, - const allocator_type& alloc) - : linked_hash_map(init, /*reservation_size=*/0, hasher(), key_equal(), - alloc) {} - - linked_hash_map(const linked_hash_map& other) - : linked_hash_map(0, other.hash_function(), other.key_eq(), - other.get_allocator()) { - reserve(other.size()); - CopyFrom(other); - } - - linked_hash_map(const linked_hash_map& other, const allocator_type& alloc) - : linked_hash_map(0, other.hash_function(), other.key_eq(), alloc) { - reserve(other.size()); - CopyFrom(other); - } - - linked_hash_map(linked_hash_map&& other) noexcept - : set_(std::move(other.set_)), list_(std::move(other.list_)) { - // Since the list and set must agree for other to end up "valid", - // explicitly clear them. - other.set_.clear(); - other.list_.clear(); - } - - linked_hash_map(linked_hash_map&& other, const allocator_type& alloc) - : linked_hash_map(0, other.hash_function(), other.key_eq(), alloc) { - if (get_allocator() == other.get_allocator()) { - *this = std::move(other); - } else { - reserve(other.size()); - CopyFrom(std::move(other)); - } - } - - linked_hash_map& operator=(const linked_hash_map& other) { - if (this != &other) { - // Make a new set, with other's hash/eq/alloc. - set_ = SetType(0, other.set_.hash_function(), other.set_.key_eq(), - other.get_allocator()); - set_.reserve(other.size()); - // Copy the list, with other's allocator. - list_ = ListType(other.get_allocator()); - CopyFrom(other); - } - return *this; - } - - linked_hash_map& operator=(linked_hash_map&& other) noexcept { - if (this != &other) { - using AllocTraits = std::allocator_traits<Alloc>; - if constexpr (AllocTraits::propagate_on_container_move_assignment:: - value) { - set_ = std::move(other.set_); - list_ = std::move(other.list_); - other.clear(); - } else if (AllocTraits::is_always_equal::value || - get_allocator() == other.get_allocator()) { - // The allocators are equal, so the list can take over other's nodes. - // std::list's move assignment can not be used here: with an allocator - // that does not propagate on move assignment it element-assigns, which - // is ill-formed for value_type, std::pair<const K, V>. - clear(); - set_ = std::move(other.set_); - list_.splice(list_.end(), other.list_); - other.set_.clear(); - } else if constexpr (!AllocTraits::is_always_equal::value) { - // The list can not take over other's nodes, so move each element into - // a new node allocated with this map's allocator and rebuild the index - // over them, adopting other's hash and equality state. This is the - // same pattern as raw_hash_set::move_assign. - clear(); - set_ = SetType(other.size(), other.set_.hash_function(), - other.set_.key_eq(), get_allocator()); - CopyFrom(std::move(other)); - } - } - return *this; - } + linked_hash_map() = default; + using Base::Base; linked_hash_map& operator=(std::initializer_list<value_type> values) { - clear(); - reserve(values.size()); - insert(values.begin(), values.end()); + Base::operator=(values); return *this; } - // Derive size_ from set_, as list::size might be O(N). - size_type size() const { return set_.size(); } - size_type max_size() const noexcept { return ~size_type{}; } - bool empty() const { return set_.empty(); } - - // Iteration is list-like, in insertion order. - // These are all forwarded. - iterator begin() { return list_.begin(); } - iterator end() { return list_.end(); } - const_iterator begin() const { return list_.begin(); } - const_iterator end() const { return list_.end(); } - const_iterator cbegin() const { return list_.cbegin(); } - const_iterator cend() const { return list_.cend(); } - reverse_iterator rbegin() { return list_.rbegin(); } - reverse_iterator rend() { return list_.rend(); } - const_reverse_iterator rbegin() const { return list_.rbegin(); } - const_reverse_iterator rend() const { return list_.rend(); } - const_reverse_iterator crbegin() const { return list_.crbegin(); } - const_reverse_iterator crend() const { return list_.crend(); } - reference front() { return list_.front(); } - reference back() { return list_.back(); } - const_reference front() const { return list_.front(); } - const_reference back() const { return list_.back(); } - - void pop_front() { erase(begin()); } - void pop_back() { erase(std::prev(end())); } - - ABSL_ATTRIBUTE_REINITIALIZES void clear() { - set_.clear(); - list_.clear(); - } - - void reserve(size_t n) { set_.reserve(n); } - size_t capacity() const { return set_.capacity(); } - size_t bucket_count() const { return set_.bucket_count(); } - float load_factor() const { return set_.load_factor(); } - - hasher hash_function() const { return set_.hash_function().fn_; } - key_equal key_eq() const { return set_.key_eq().fn_; } - allocator_type get_allocator() const { return list_.get_allocator(); } - - template <class K = key_type> - size_type erase(const key_arg<K>& key) { - auto found = set_.find(key); - if (found == set_.end()) return 0; - auto list_it = *found; - // Erase set entry first since it refers to the list element. - set_.erase(found); - list_.erase(list_it); - return 1; - } - - iterator erase(const_iterator position) { - auto found = set_.find(position); - assert(*found == position); - set_.erase(found); - return list_.erase(position); - } - - iterator erase(iterator position) { - return erase(static_cast<const_iterator>(position)); - } - - iterator erase(iterator first, iterator last) { - while (first != last) first = erase(first); - return first; - } - - iterator erase(const_iterator first, const_iterator last) { - while (first != last) first = erase(first); - if (first == end()) return end(); - return *set_.find(first); - } - - template <class K = key_type> - iterator find(const key_arg<K>& key) { - auto found = set_.find(key); - if (found == set_.end()) return end(); - return *found; - } - - template <class K = key_type> - const_iterator find(const key_arg<K>& key) const { - auto found = set_.find(key); - if (found == set_.end()) return end(); - return *found; - } - - template <class K = key_type> - size_type count(const key_arg<K>& key) const { - return contains(key) ? 1 : 0; - } - template <class K = key_type> - bool contains(const key_arg<K>& key) const { - return set_.contains(key); - } - template <class K = key_type> mapped_type& at(const key_arg<K>& key) { - auto it = find(key); - if (ABSL_PREDICT_FALSE(it == end())) { + auto it = this->find(key); + if (ABSL_PREDICT_FALSE(it == this->end())) { ThrowStdOutOfRange("absl::linked_hash_map::at"); } return it->second; @@ -417,36 +92,23 @@ } template <class K = key_type> - std::pair<iterator, iterator> equal_range(const key_arg<K>& key) { - auto iter = set_.find(key); - if (iter == set_.end()) return {end(), end()}; - return {*iter, std::next(*iter)}; - } - - template <class K = key_type> - std::pair<const_iterator, const_iterator> equal_range( - const key_arg<K>& key) const { - auto iter = set_.find(key); - if (iter == set_.end()) return {end(), end()}; - return {*iter, std::next(*iter)}; - } - - template <class K = key_type> mapped_type& operator[](const key_arg<K>& key) { - return LazyEmplaceInternal(key).first->second; + return this->LazyEmplaceMap(key).first->second; } template <class K = key_type, std::enable_if_t<!std::is_reference_v<K>, int> = 0> mapped_type& operator[](key_arg<K>&& key) { - return LazyEmplaceInternal(std::forward<key_arg<K>>(key)).first->second; + return this->LazyEmplaceMap(std::forward<key_arg<K>>(key)).first->second; } + using Base::insert; + std::pair<iterator, bool> insert(const value_type& v) { - return InsertInternal(v); + return this->InsertValueAt(this->end(), v); } std::pair<iterator, bool> insert(value_type&& v) { - return InsertInternal(std::move(v)); + return this->InsertValueAt(this->end(), std::move(v)); } iterator insert(const_iterator, const value_type& v) { @@ -456,29 +118,6 @@ return insert(std::move(v)).first; } - void insert(std::initializer_list<value_type> ilist) { - insert(ilist.begin(), ilist.end()); - } - - template <class InputIt> - void insert(InputIt first, InputIt last) { - for (; first != last; ++first) insert(*first); - } - - insert_return_type insert(node_type&& node) { - if (node.empty()) return {end(), false, node_type()}; - if (auto [set_itr, inserted] = set_.emplace(node.list_.begin()); inserted) { - list_.splice(list_.end(), node.list_); - return {*set_itr, true, node_type()}; - } else { - return {*set_itr, false, std::move(node)}; - } - } - - iterator insert(const_iterator, node_type&& node) { - return insert(std::move(node)).first; - } - // The last two template parameters ensure that both arguments are rvalues // (lvalue arguments are handled by the overloads below). This is necessary // for supporting bitfield arguments. @@ -536,17 +175,6 @@ return insert_or_assign(k, v).first; } - template <typename... Args> - std::pair<iterator, bool> emplace(Args&&... args) { - ListType node_donor(get_allocator()); - auto list_iter = - node_donor.emplace(node_donor.end(), std::forward<Args>(args)...); - auto ins = set_.insert(list_iter); - if (!ins.second) return {*ins.first, false}; - list_.splice(list_.end(), node_donor, list_iter); - return {list_iter, true}; - } - template <class K = key_type, class... Args, std::enable_if_t<!std::is_reference_v<K>, int> = 0> iterator try_emplace(const_iterator, key_arg<K>&& k, Args&&... args) { @@ -554,154 +182,50 @@ .first; } - template <typename... Args> - iterator emplace_hint(const_iterator, Args&&... args) { - return emplace(std::forward<Args>(args)...).first; - } - template <class K = key_type, typename... Args, std::enable_if_t<!std::is_reference_v<K>, int> = 0> std::pair<iterator, bool> try_emplace(key_arg<K>&& key, Args&&... args) { - return LazyEmplaceInternal(std::forward<key_arg<K>>(key), - std::forward<Args>(args)...); + return this->LazyEmplaceMap(std::forward<key_arg<K>>(key), + std::forward<Args>(args)...); } - template <typename H, typename E> - void merge(linked_hash_map<Key, Value, H, E, Alloc>& src) { - auto itr = src.list_.begin(); - while (itr != src.list_.end()) { - if (contains(itr->first)) { - ++itr; - } else { - insert(src.extract(itr++)); - } - } - } + using Base::merge; - template <typename H, typename E> - void merge(linked_hash_map<Key, Value, H, E, Alloc>&& src) { - merge(src); - } - - node_type extract(const_iterator position) { - set_.erase(position->first); - ListType extracted_node_list(get_allocator()); - extracted_node_list.splice(extracted_node_list.end(), list_, position); - return node_type(std::move(extracted_node_list)); - } - - template <class K = key_type, - std::enable_if_t<!std::is_same_v<K, iterator>, int> = 0> - node_type extract(const key_arg<K>& key) { - auto node = set_.extract(key); - if (node.empty()) return node_type(); - ListType extracted_node_list(get_allocator()); - extracted_node_list.splice(extracted_node_list.end(), list_, node.value()); - return node_type(std::move(extracted_node_list)); - } - - template <typename H, typename E> - void splice(const_iterator, linked_hash_map<Key, Value, H, E, Alloc>& list, - const_iterator it) { - if (&list == this) { - list_.splice(list_.end(), list.list_, it); - } else { - insert(list.extract(it)); - } + template < + typename... OtherParams, + typename = std::enable_if_t<std::is_same_v< + Alloc, typename container_internal::raw_linked_hash_set< + Policy, OtherParams...>::allocator_type>>> + void splice( + const_iterator, + container_internal::raw_linked_hash_set<Policy, OtherParams...>& list, + const_iterator it) { + this->SpliceFrom(list, it); } template <class K = key_type, typename... Args> std::pair<iterator, bool> try_emplace(const key_arg<K>& key, Args&&... args) { - return LazyEmplaceInternal(key, std::forward<Args>(args)...); + return this->LazyEmplaceMap(key, std::forward<Args>(args)...); } template <class K = key_type, typename... Args> iterator try_emplace(const_iterator, const key_arg<K>& key, Args&&... args) { - return LazyEmplaceInternal(key, std::forward<Args>(args)...).first; + return this->LazyEmplaceMap(key, std::forward<Args>(args)...).first; } - void swap(linked_hash_map& other) noexcept { - using std::swap; - swap(set_, other.set_); - swap(list_, other.list_); - } - - friend bool operator==(const linked_hash_map& a, const linked_hash_map& b) { - if (a.size() != b.size()) return false; - const linked_hash_map* outer = &a; - const linked_hash_map* inner = &b; - if (outer->capacity() > inner->capacity()) std::swap(outer, inner); - for (const value_type& elem : *outer) { - auto it = inner->find(elem.first); - if (it == inner->end()) return false; - if (it->second != elem.second) return false; - } - - return true; - } - - friend bool operator!=(const linked_hash_map& a, const linked_hash_map& b) { - return !(a == b); - } - - void rehash(size_t n) { set_.rehash(n); } + void swap(linked_hash_map& other) noexcept { Base::swap(other); } private: - template <typename Other> - void CopyFrom(Other&& other) { - for (auto& elem : other.list_) { - set_.insert(list_.insert(list_.end(), std::move(elem))); - } - if constexpr (!std::is_const_v<std::remove_reference_t<Other>>) { - // When moving from `other`, `std::move(elem)` above mutates the elements - // of `other.list_` in place, invalidating `other.set_`'s index over them. - // Clear `other` so its `set_` and `list_` remain consistent and empty. - other.clear(); - } - assert(set_.size() == list_.size()); - } - - template <typename U> - std::pair<iterator, bool> InsertInternal(U&& pair) { // NOLINT(build/c++11) - bool constructed = false; - auto set_iter = set_.lazy_emplace(pair.first, [&](const auto& ctor) { - constructed = true; - ctor(list_.emplace(list_.end(), std::forward<U>(pair))); - }); - return {*set_iter, constructed}; - } - template <class K, class V> std::pair<iterator, bool> InsertOrAssignInternal(K&& k, V&& v) { auto [it, inserted] = - LazyEmplaceInternal(std::forward<K>(k), std::forward<V>(v)); + this->LazyEmplaceMap(std::forward<K>(k), std::forward<V>(v)); if (!inserted) { // NOLINTNEXTLINE(bugprone-use-after-move) it->second = std::forward<V>(v); } return {it, inserted}; } - - template <typename K, typename... Args> - std::pair<iterator, bool> LazyEmplaceInternal(K&& key, Args&&... args) { - bool constructed = false; - auto set_iter = set_.lazy_emplace( - key, [this, &constructed, &key, &args...](const auto& ctor) { - auto list_iter = - list_.emplace(list_.end(), std::piecewise_construct, - std::forward_as_tuple(std::forward<K>(key)), - std::forward_as_tuple(std::forward<Args>(args)...)); - constructed = true; - ctor(list_iter); - }); - return {*set_iter, constructed}; - } - - // The set component, used for speedy lookups. - SetType set_; - - // The list component, used for maintaining insertion order. - ListType list_; }; ABSL_NAMESPACE_END
diff --git a/absl/container/linked_hash_map_test.cc b/absl/container/linked_hash_map_test.cc index ef03e13..121ffa6 100644 --- a/absl/container/linked_hash_map_test.cc +++ b/absl/container/linked_hash_map_test.cc
@@ -18,6 +18,7 @@ #include <cstddef> #include <cstdint> #include <functional> +#include <iterator> #include <memory> #include <stdexcept> #include <string> @@ -526,11 +527,14 @@ m1.insert(std::make_pair(1, 1)); m1.insert(std::make_pair(2, 2)); m2.insert(std::make_pair(3, 3)); + auto it1 = std::prev(m1.end()); ASSERT_EQ(2, m1.size()); ASSERT_EQ(1, m2.size()); m1.swap(m2); ASSERT_EQ(1, m1.size()); ASSERT_EQ(2, m2.size()); + EXPECT_EQ(std::next(it1), m2.end()); + EXPECT_EQ(std::prev(m2.end()), it1); } TEST(LinkedHashMapTest, SelfSwap) { @@ -954,7 +958,7 @@ TEST(LinkedHashMap, Merge) { linked_hash_map<int, int> m = {{1, 7}, {3, 6}}; - linked_hash_map<int, int> src = {{1, 10}, {2, 9}, {4, 16}}; + linked_hash_map<int, int, std::hash<int>> src = {{1, 10}, {2, 9}, {4, 16}}; m.merge(src); @@ -967,7 +971,7 @@ TEST(LinkedHashMap, Splice) { linked_hash_map<int, int> m = {{1, 7}, {3, 6}}; - linked_hash_map<int, int> src = {{1, 10}, {2, 9}, {4, 16}}; + linked_hash_map<int, int, std::hash<int>> src = {{1, 10}, {2, 9}, {4, 16}}; m.splice(m.end(), m, m.begin()); EXPECT_THAT(m, ElementsAre(Pair(3, 6), Pair(1, 7))); @@ -1141,6 +1145,14 @@ } } +TEST(LinkedHashMap, RecursiveTypeCompiles) { + struct RecursiveType { + linked_hash_map<int, RecursiveType> m; + }; + RecursiveType t; + t.m[0] = RecursiveType{}; +} + } // namespace } // namespace container_internal ABSL_NAMESPACE_END
diff --git a/absl/container/linked_hash_set.h b/absl/container/linked_hash_set.h index b1c0024..d2de130 100644 --- a/absl/container/linked_hash_set.h +++ b/absl/container/linked_hash_set.h
@@ -32,379 +32,59 @@ #ifndef ABSL_CONTAINER_LINKED_HASH_SET_H_ #define ABSL_CONTAINER_LINKED_HASH_SET_H_ -#include <cassert> -#include <cstddef> #include <initializer_list> -#include <list> -#include <memory> #include <type_traits> #include <utility> -#include "absl/base/attributes.h" #include "absl/base/config.h" -#include "absl/container/flat_hash_set.h" -#include "absl/container/internal/common.h" +#include "absl/container/internal/raw_linked_hash_set.h" // IWYU pragma: export namespace absl { ABSL_NAMESPACE_BEGIN template < - typename Key, typename KeyHash = typename absl::flat_hash_set<Key>::hasher, - typename KeyEq = typename absl::flat_hash_set<Key, KeyHash>::key_equal, - typename Alloc = std::allocator<Key>> -class linked_hash_set { - using KeyArgImpl = absl::container_internal::KeyArg< - absl::container_internal::IsTransparent<KeyEq>::value && - absl::container_internal::IsTransparent<KeyHash>::value>; - - public: - using key_type = Key; - using hasher = KeyHash; - using key_equal = KeyEq; - using value_type = key_type; - using allocator_type = Alloc; - using difference_type = ptrdiff_t; - - private: + typename Key, + typename KeyHash = + typename container_internal::LinkedHashSetPolicy<Key>::DefaultHash, + typename KeyEq = + typename container_internal::LinkedHashSetPolicy<Key>::DefaultEq, + typename Alloc = + typename container_internal::LinkedHashSetPolicy<Key>::DefaultAlloc> +class linked_hash_set + : public container_internal::InstantiateRawLinkedHashSet< + container_internal::LinkedHashSetPolicy<Key>, KeyHash, KeyEq, + Alloc>::type { + using Base = typename linked_hash_set::raw_linked_hash_set; template <class K> - using key_arg = typename KeyArgImpl::template Select<K, key_type>; - - using ListType = std::list<key_type, Alloc>; - - template <class Fn> - class Wrapped { - template <typename K> - static const K& ToKey(const K& k) { - return k; - } - static const key_type& ToKey(typename ListType::const_iterator it) { - return *it; - } - static const key_type& ToKey(typename ListType::iterator it) { return *it; } - - Fn fn_; - - friend linked_hash_set; - - public: - using is_transparent = void; - - Wrapped() = default; - explicit Wrapped(Fn fn) : fn_(std::move(fn)) {} - - template <class... Args> - auto operator()(Args&&... args) const - -> decltype(this->fn_(ToKey(args)...)) { - return fn_(ToKey(args)...); - } - }; - using SetType = - absl::flat_hash_set<typename ListType::iterator, Wrapped<hasher>, - Wrapped<key_equal>, Alloc>; - - class NodeHandle { - public: - using allocator_type = linked_hash_set::allocator_type; - using value_type = linked_hash_set::value_type; - - constexpr NodeHandle() noexcept = default; - NodeHandle(NodeHandle&& nh) noexcept = default; - ~NodeHandle() = default; - NodeHandle& operator=(NodeHandle&& node) noexcept = default; - bool empty() const noexcept { return list_.empty(); } - explicit operator bool() const noexcept { return !empty(); } - allocator_type get_allocator() const { return list_.get_allocator(); } - value_type& value() { return list_.front(); } - void swap(NodeHandle& nh) noexcept { list_.swap(nh.list_); } - - private: - friend linked_hash_set; - - explicit NodeHandle(ListType list) : list_(std::move(list)) {} - ListType list_; - }; - - template <class Iterator, class NodeType> - struct InsertReturnType { - Iterator position; - bool inserted; - NodeType node; - }; + using key_arg = typename Base::template key_arg<K>; public: - using iterator = typename ListType::const_iterator; - using const_iterator = typename ListType::const_iterator; - using reverse_iterator = typename ListType::const_reverse_iterator; - using const_reverse_iterator = typename ListType::const_reverse_iterator; - using reference = typename ListType::reference; - using const_reference = typename ListType::const_reference; - using pointer = typename std::allocator_traits<allocator_type>::pointer; - using const_pointer = - typename std::allocator_traits<allocator_type>::const_pointer; - using size_type = typename ListType::size_type; - using node_type = NodeHandle; - using insert_return_type = InsertReturnType<iterator, node_type>; + using typename Base::allocator_type; + using typename Base::const_iterator; + using typename Base::hasher; + using typename Base::iterator; + using typename Base::key_equal; + using typename Base::key_type; + using typename Base::value_type; - linked_hash_set() {} + linked_hash_set() = default; + using Base::Base; - explicit linked_hash_set(size_t reservation_size, - const hasher& hash = hasher(), - const key_equal& eq = key_equal(), - const allocator_type& alloc = allocator_type()) - : set_(reservation_size, Wrapped<hasher>(hash), Wrapped<key_equal>(eq), - alloc), - list_(alloc) {} - - linked_hash_set(size_t reservation_size, const hasher& hash, - const allocator_type& alloc) - : linked_hash_set(reservation_size, hash, key_equal(), alloc) {} - - linked_hash_set(size_t reservation_size, const allocator_type& alloc) - : linked_hash_set(reservation_size, hasher(), key_equal(), alloc) {} - - explicit linked_hash_set(const allocator_type& alloc) - : linked_hash_set(0, hasher(), key_equal(), alloc) {} - - template <class InputIt> - linked_hash_set(InputIt first, InputIt last, size_t reservation_size = 0, - const hasher& hash = hasher(), - const key_equal& eq = key_equal(), - const allocator_type& alloc = allocator_type()) - : linked_hash_set(reservation_size, hash, eq, alloc) { - insert(first, last); - } - - template <class InputIter> - linked_hash_set(InputIter first, InputIter last, size_t reservation_size, - const hasher& hash, const allocator_type& alloc) - : linked_hash_set(first, last, reservation_size, hash, key_equal(), - alloc) {} - - template <class InputIter> - linked_hash_set(InputIter first, InputIter last, size_t reservation_size, - const allocator_type& alloc) - : linked_hash_set(first, last, reservation_size, hasher(), key_equal(), - alloc) {} - - template <class InputIt> - linked_hash_set(InputIt first, InputIt last, const allocator_type& alloc) - : linked_hash_set(first, last, /*reservation_size=*/0, hasher(), - key_equal(), alloc) {} - - linked_hash_set(std::initializer_list<key_type> init, - size_t reservation_size = 0, const hasher& hash = hasher(), - const key_equal& eq = key_equal(), - const allocator_type& alloc = allocator_type()) - : linked_hash_set(init.begin(), init.end(), reservation_size, hash, eq, - alloc) {} - - linked_hash_set(std::initializer_list<key_type> init, size_t reservation_size, - const allocator_type& alloc) - : linked_hash_set(init, reservation_size, hasher(), key_equal(), alloc) {} - - linked_hash_set(std::initializer_list<key_type> init, size_t reservation_size, - const hasher& hash, const allocator_type& alloc) - : linked_hash_set(init, reservation_size, hash, key_equal(), alloc) {} - - linked_hash_set(std::initializer_list<key_type> init, - const allocator_type& alloc) - : linked_hash_set(init, /*reservation_size=*/0, hasher(), key_equal(), - alloc) {} - - linked_hash_set(const linked_hash_set& other) - : linked_hash_set(0, other.hash_function(), other.key_eq(), - other.get_allocator()) { - reserve(other.size()); - CopyFrom(other); - } - - linked_hash_set(const linked_hash_set& other, const allocator_type& alloc) - : linked_hash_set(0, other.hash_function(), other.key_eq(), alloc) { - reserve(other.size()); - CopyFrom(other); - } - - linked_hash_set(linked_hash_set&& other) noexcept - : set_(std::move(other.set_)), list_(std::move(other.list_)) { - // Since the list and set must agree for other to end up "valid", - // explicitly clear them. - other.set_.clear(); - other.list_.clear(); - } - - linked_hash_set(linked_hash_set&& other, const allocator_type& alloc) - : linked_hash_set(0, other.hash_function(), other.key_eq(), alloc) { - if (get_allocator() == other.get_allocator()) { - *this = std::move(other); - } else { - reserve(other.size()); - CopyFrom(std::move(other)); - } - } - - linked_hash_set& operator=(const linked_hash_set& other) { - if (this != &other) { - // Make a new set, with other's hash/eq/alloc. - set_ = SetType(0, other.set_.hash_function(), - other.set_.key_eq(), other.get_allocator()); - set_.reserve(other.size()); - // Copy the list, with other's allocator. - list_ = ListType(other.get_allocator()); - CopyFrom(other); - } + linked_hash_set& operator=(std::initializer_list<value_type> values) { + Base::operator=(values); return *this; } - linked_hash_set& operator=(linked_hash_set&& other) noexcept { - if (this != &other) { - using AllocTraits = std::allocator_traits<Alloc>; - if constexpr (AllocTraits::propagate_on_container_move_assignment:: - value) { - set_ = std::move(other.set_); - list_ = std::move(other.list_); - other.clear(); - } else if (AllocTraits::is_always_equal::value || - get_allocator() == other.get_allocator()) { - // The allocators are equal, so the list can take over other's nodes. - // std::list's move assignment can not be used here: with an allocator - // that does not propagate on move assignment it element-assigns, which - // is ill-formed for value types that are not assignable, such as - // linked_hash_map's std::pair<const K, V>. - clear(); - set_ = std::move(other.set_); - list_.splice(list_.end(), other.list_); - other.set_.clear(); - } else if constexpr (!AllocTraits::is_always_equal::value) { - // The list can not take over other's nodes, so move each element into - // a new node allocated with this set's allocator and rebuild the index - // over them, adopting other's hash and equality state. This is the - // same pattern as raw_hash_set::move_assign. - clear(); - set_ = SetType(other.size(), other.set_.hash_function(), - other.set_.key_eq(), get_allocator()); - CopyFrom(std::move(other)); - } - } - return *this; - } - - linked_hash_set& operator=(std::initializer_list<key_type> values) { - clear(); - reserve(values.size()); - insert(values.begin(), values.end()); - return *this; - } - - // Derive size from set_, as list::size might be O(N). - size_type size() const { return set_.size(); } - size_type max_size() const noexcept { return ~size_type{}; } - bool empty() const { return set_.empty(); } - - // Iteration is list-like, in insertion order. - // These are all forwarded. - iterator begin() { return list_.begin(); } - iterator end() { return list_.end(); } - const_iterator begin() const { return list_.begin(); } - const_iterator end() const { return list_.end(); } - const_iterator cbegin() const { return list_.cbegin(); } - const_iterator cend() const { return list_.cend(); } - reverse_iterator rbegin() { return list_.rbegin(); } - reverse_iterator rend() { return list_.rend(); } - const_reverse_iterator rbegin() const { return list_.rbegin(); } - const_reverse_iterator rend() const { return list_.rend(); } - const_reverse_iterator crbegin() const { return list_.crbegin(); } - const_reverse_iterator crend() const { return list_.crend(); } - reference front() { return list_.front(); } - reference back() { return list_.back(); } - const_reference front() const { return list_.front(); } - const_reference back() const { return list_.back(); } - - void pop_front() { erase(begin()); } - void pop_back() { erase(std::prev(end())); } - - ABSL_ATTRIBUTE_REINITIALIZES void clear() { - set_.clear(); - list_.clear(); - } - - void reserve(size_t n) { set_.reserve(n); } - size_t bucket_count() const { return set_.bucket_count(); } - size_t capacity() const { return set_.capacity(); } - float load_factor() const { return set_.load_factor(); } - - hasher hash_function() const { return set_.hash_function().fn_; } - key_equal key_eq() const { return set_.key_eq().fn_; } - allocator_type get_allocator() const { return list_.get_allocator(); } - - template <typename K = key_type> - size_type erase(const key_arg<K>& key) { - auto found = set_.find(key); - if (found == set_.end()) return 0; - auto list_it = *found; - // Erase set entry first since it refers to the list element. - set_.erase(found); - list_.erase(list_it); - return 1; - } - - iterator erase(const_iterator position) { - auto found = set_.find(position); - assert(*found == position); - set_.erase(found); - return list_.erase(position); - } - - iterator erase(const_iterator first, const_iterator last) { - while (first != last) first = erase(first); - return first; - } - - template <typename K = key_type> - iterator find(const key_arg<K>& key) { - auto found = set_.find(key); - if (found == set_.end()) return end(); - return *found; - } - - template <typename K = key_type> - const_iterator find(const key_arg<K>& key) const { - auto found = set_.find(key); - if (found == set_.end()) return end(); - return *found; - } - - template <typename K = key_type> - size_t count(const key_arg<K>& key) const { - return contains(key) ? 1 : 0; - } - template <typename K = key_type> - bool contains(const key_arg<K>& key) const { - return set_.contains(key); - } - - template <typename K = key_type> - std::pair<iterator, iterator> equal_range(const key_arg<K>& key) { - auto iter = set_.find(key); - if (iter == set_.end()) return {end(), end()}; - return {*iter, std::next(*iter)}; - } - - template <typename K = key_type> - std::pair<const_iterator, const_iterator> equal_range( - const key_arg<K>& key) const { - auto iter = set_.find(key); - if (iter == set_.end()) return {end(), end()}; - return {*iter, std::next(*iter)}; - } + using Base::insert; template <typename K = key_type> std::pair<iterator, bool> insert(const key_arg<K>& k) { - return InsertInternal(list_.end(), k); + return this->InsertValueAt(this->end(), k); } template <typename K = key_type, std::enable_if_t<!std::is_reference_v<K>, int> = 0> std::pair<iterator, bool> insert(key_arg<K>&& k) { - return InsertInternal(list_.end(), std::move(k)); + return this->InsertValueAt(this->end(), std::move(k)); } template <typename K = key_type, @@ -413,7 +93,7 @@ !std::is_convertible_v<const key_arg<K>&, iterator>, int> = 0> iterator insert(const_iterator hint, const key_arg<K>& k) { - return InsertInternal(hint, k).first; + return this->InsertValueAt(hint, k).first; } template <typename K = key_type, std::enable_if_t< @@ -422,141 +102,12 @@ !std::is_convertible_v<key_arg<K>&&, iterator>, int> = 0> iterator insert(const_iterator hint, key_arg<K>&& k) { - return InsertInternal(hint, std::move(k)).first; + return this->InsertValueAt(hint, std::move(k)).first; } - void insert(std::initializer_list<key_type> ilist) { - insert(ilist.begin(), ilist.end()); - } + using Base::merge; - template <class InputIt> - void insert(InputIt first, InputIt last) { - for (; first != last; ++first) insert(*first); - } - - insert_return_type insert(node_type&& node) { - if (node.empty()) return {end(), false, node_type()}; - if (auto [set_itr, inserted] = set_.emplace(node.list_.begin()); inserted) { - list_.splice(list_.end(), node.list_); - return {*set_itr, true, node_type()}; - } else { - return {*set_itr, false, std::move(node)}; - } - } - - iterator insert(const_iterator, node_type&& node) { - return insert(std::move(node)).first; - } - - template <typename... Args> - std::pair<iterator, bool> emplace(Args&&... args) { - return EmplaceInternal(list_.end(), std::forward<Args>(args)...); - } - - template <typename... Args> - iterator emplace_hint(const_iterator hint, Args&&... args) { - return EmplaceInternal(hint, std::forward<Args>(args)...).first; - } - - template <typename H, typename E> - void merge(linked_hash_set<Key, H, E, Alloc>& src) { - auto itr = src.list_.begin(); - while (itr != src.list_.end()) { - if (contains(*itr)) { - ++itr; - } else { - insert(src.extract(itr++)); - } - } - } - - template <typename H, typename E> - void merge(linked_hash_set<Key, H, E, Alloc>&& src) { - merge(src); - } - - node_type extract(const_iterator position) { - set_.erase(position); - ListType extracted_node_list(get_allocator()); - extracted_node_list.splice(extracted_node_list.end(), list_, position); - return node_type(std::move(extracted_node_list)); - } - - template <class K = key_type, - typename std::enable_if_t<!std::is_same_v<K, iterator>, int> = 0> - node_type extract(const key_arg<K>& key) { - auto node = set_.extract(key); - if (node.empty()) return node_type(); - ListType extracted_node_list(get_allocator()); - extracted_node_list.splice(extracted_node_list.end(), list_, node.value()); - return node_type(std::move(extracted_node_list)); - } - - void swap(linked_hash_set& other) noexcept { - using std::swap; - swap(set_, other.set_); - swap(list_, other.list_); - } - - friend bool operator==(const linked_hash_set& a, const linked_hash_set& b) { - if (a.size() != b.size()) return false; - const linked_hash_set* outer = &a; - const linked_hash_set* inner = &b; - if (outer->capacity() > inner->capacity()) std::swap(outer, inner); - for (const value_type& elem : *outer) - if (!inner->contains(elem)) return false; - return true; - } - - friend bool operator!=(const linked_hash_set& a, const linked_hash_set& b) { - return !(a == b); - } - - void rehash(size_t n) { set_.rehash(n); } - - private: - template <typename Other> - void CopyFrom(Other&& other) { - for (auto& elem : other.list_) { - set_.insert(list_.insert(list_.end(), std::move(elem))); - } - if constexpr (!std::is_const_v<std::remove_reference_t<Other>>) { - // When moving from `other`, `std::move(elem)` above mutates the elements - // of `other.list_` in place, invalidating `other.set_`'s index over them. - // Clear `other` so its `set_` and `list_` remain consistent and empty. - other.clear(); - } - assert(set_.size() == list_.size()); - } - - template <typename... Args> - std::pair<iterator, bool> EmplaceInternal(const_iterator hint, - Args&&... args) { - ListType node_donor(get_allocator()); - auto list_iter = - node_donor.emplace(node_donor.end(), std::forward<Args>(args)...); - auto ins = set_.insert(list_iter); - if (!ins.second) return {*ins.first, false}; - list_.splice(hint, node_donor, list_iter); - return {list_iter, true}; - } - - template <typename U> - std::pair<iterator, bool> InsertInternal(const_iterator hint, - U&& key) { // NOLINT(build/c++11) - bool constructed = false; - auto set_iter = set_.lazy_emplace(key, [&](const auto& ctor) { - constructed = true; - ctor(list_.emplace(hint, std::forward<U>(key))); - }); - return {*set_iter, constructed}; - } - - // The set component, used for speedy lookups. - SetType set_; - - // The list component, used for maintaining insertion order. - ListType list_; + void swap(linked_hash_set& other) noexcept { Base::swap(other); } }; ABSL_NAMESPACE_END
diff --git a/absl/container/linked_hash_set_test.cc b/absl/container/linked_hash_set_test.cc index 5e4c176..8b3555a 100644 --- a/absl/container/linked_hash_set_test.cc +++ b/absl/container/linked_hash_set_test.cc
@@ -19,6 +19,7 @@ #include <cstddef> #include <cstdint> #include <functional> +#include <iterator> #include <memory> #include <string> #include <utility> @@ -541,11 +542,14 @@ m1.insert(1); m1.insert(2); m2.insert(3); + auto it1 = std::prev(m1.end()); ASSERT_EQ(2, m1.size()); ASSERT_EQ(1, m2.size()); m1.swap(m2); ASSERT_EQ(1, m1.size()); ASSERT_EQ(2, m2.size()); + EXPECT_EQ(std::next(it1), m2.end()); + EXPECT_EQ(std::prev(m2.end()), it1); } TEST(LinkedHashSetTest, SelfSwap) { @@ -827,6 +831,11 @@ EXPECT_EQ(node.value(), 9); EXPECT_THAT(s, ElementsAre(7, 2, 17)); EXPECT_FALSE(s.contains(9)); + + node.value() = 19; + auto it = s.insert(s.begin(), std::move(node)); + EXPECT_EQ(it, s.find(19)); + EXPECT_THAT(s, ElementsAre(7, 2, 17, 19)); } // Verify that emplacing and extracting nodes results in the same stateful @@ -982,7 +991,7 @@ TEST(LinkedHashSet, Merge) { linked_hash_set<int> m = {1, 7, 3, 6, 10}; - linked_hash_set<int> src = {1, 2, 9, 10, 4, 16}; + linked_hash_set<int, std::hash<int>> src = {1, 2, 9, 10, 4, 16}; m.merge(src);