1// Copyright 2018 The Abseil Authors.
2//
3// Licensed under the Apache License, Version 2.0 (the "License");
4// you may not use this file except in compliance with the License.
5// You may obtain a copy of the License at
6//
7// https://www.apache.org/licenses/LICENSE-2.0
8//
9// Unless required by applicable law or agreed to in writing, software
10// distributed under the License is distributed on an "AS IS" BASIS,
11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12// See the License for the specific language governing permissions and
13// limitations under the License.
14
15#ifndef ABSL_CONTAINER_INTERNAL_CONTAINER_H_
16#define ABSL_CONTAINER_INTERNAL_CONTAINER_H_
17
18#include <cassert>
19#include <type_traits>
20
21#include "absl/meta/type_traits.h"
22#include "absl/types/optional.h"
23
24namespace absl {
25namespace container_internal {
26
27template <class, class = void>
28struct IsTransparent : std::false_type {};
29template <class T>
30struct IsTransparent<T, absl::void_t<typename T::is_transparent>>
31 : std::true_type {};
32
33template <bool is_transparent>
34struct KeyArg {
35 // Transparent. Forward `K`.
36 template <typename K, typename key_type>
37 using type = K;
38};
39
40template <>
41struct KeyArg<false> {
42 // Not transparent. Always use `key_type`.
43 template <typename K, typename key_type>
44 using type = key_type;
45};
46
47// The node_handle concept from C++17.
48// We specialize node_handle for sets and maps. node_handle_base holds the
49// common API of both.
50template <typename PolicyTraits, typename Alloc>
51class node_handle_base {
52 protected:
53 using slot_type = typename PolicyTraits::slot_type;
54
55 public:
56 using allocator_type = Alloc;
57
58 constexpr node_handle_base() {}
59 node_handle_base(node_handle_base&& other) noexcept {
60 *this = std::move(other);
61 }
62 ~node_handle_base() { destroy(); }
63 node_handle_base& operator=(node_handle_base&& other) noexcept {
64 destroy();
65 if (!other.empty()) {
66 alloc_ = other.alloc_;
67 PolicyTraits::transfer(alloc(), slot(), other.slot());
68 other.reset();
69 }
70 return *this;
71 }
72
73 bool empty() const noexcept { return !alloc_; }
74 explicit operator bool() const noexcept { return !empty(); }
75 allocator_type get_allocator() const { return *alloc_; }
76
77 protected:
78 friend struct CommonAccess;
79
80 node_handle_base(const allocator_type& a, slot_type* s) : alloc_(a) {
81 PolicyTraits::transfer(alloc(), slot(), s);
82 }
83
84 void destroy() {
85 if (!empty()) {
86 PolicyTraits::destroy(alloc(), slot());
87 reset();
88 }
89 }
90
91 void reset() {
92 assert(alloc_.has_value());
93 alloc_ = absl::nullopt;
94 }
95
96 slot_type* slot() const {
97 assert(!empty());
98 return reinterpret_cast<slot_type*>(std::addressof(slot_space_));
99 }
100 allocator_type* alloc() { return std::addressof(*alloc_); }
101
102 private:
103 absl::optional<allocator_type> alloc_;
104 mutable absl::aligned_storage_t<sizeof(slot_type), alignof(slot_type)>
105 slot_space_;
106};
107
108// For sets.
109template <typename Policy, typename PolicyTraits, typename Alloc,
110 typename = void>
111class node_handle : public node_handle_base<PolicyTraits, Alloc> {
112 using Base = typename node_handle::node_handle_base;
113
114 public:
115 using value_type = typename PolicyTraits::value_type;
116
117 constexpr node_handle() {}
118
119 value_type& value() const { return PolicyTraits::element(this->slot()); }
120
121 private:
122 friend struct CommonAccess;
123
124 node_handle(const Alloc& a, typename Base::slot_type* s) : Base(a, s) {}
125};
126
127// For maps.
128template <typename Policy, typename PolicyTraits, typename Alloc>
129class node_handle<Policy, PolicyTraits, Alloc,
130 absl::void_t<typename Policy::mapped_type>>
131 : public node_handle_base<PolicyTraits, Alloc> {
132 using Base = typename node_handle::node_handle_base;
133
134 public:
135 using key_type = typename Policy::key_type;
136 using mapped_type = typename Policy::mapped_type;
137
138 constexpr node_handle() {}
139
140 auto key() const -> decltype(PolicyTraits::key(this->slot())) {
141 return PolicyTraits::key(this->slot());
142 }
143
144 mapped_type& mapped() const {
145 return PolicyTraits::value(&PolicyTraits::element(this->slot()));
146 }
147
148 private:
149 friend struct CommonAccess;
150
151 node_handle(const Alloc& a, typename Base::slot_type* s) : Base(a, s) {}
152};
153
154// Provide access to non-public node-handle functions.
155struct CommonAccess {
156 template <typename Node>
157 static auto GetSlot(const Node& node) -> decltype(node.slot()) {
158 return node.slot();
159 }
160
161 template <typename Node>
162 static void Reset(Node* node) {
163 node->reset();
164 }
165
166 template <typename T, typename... Args>
167 static T Make(Args&&... args) {
168 return T(std::forward<Args>(args)...);
169 }
170};
171
172// Implement the insert_return_type<> concept of C++17.
173template <class Iterator, class NodeType>
174struct InsertReturnType {
175 Iterator position;
176 bool inserted;
177 NodeType node;
178};
179
180} // namespace container_internal
181} // namespace absl
182
183#endif // ABSL_CONTAINER_INTERNAL_CONTAINER_H_
184