1 // Copyright 2018 The Abseil Authors.
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
7 // https://www.apache.org/licenses/LICENSE-2.0
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.
18 #include <initializer_list>
20 #include <type_traits>
25 namespace btree::internal
{
27 // A common base class for btree_set, btree_map, btree_multiset, and
29 template <typename Tree
>
30 class btree_container
{
31 using params_type
= typename
Tree::params_type
;
34 // Alias used for heterogeneous lookup functions.
35 // `key_arg<K>` evaluates to `K` when the functors are transparent and to
36 // `key_type` otherwise. It permits template argument deduction on `K` for the
38 template <class Compare
>
39 using is_transparent_t
= typename
Compare::is_transparent
;
43 std::experimental::is_detected_v
<is_transparent_t
, typename
Tree::key_compare
>,
45 typename
Tree::key_type
>;
48 using key_type
= typename
Tree::key_type
;
49 using value_type
= typename
Tree::value_type
;
50 using size_type
= typename
Tree::size_type
;
51 using difference_type
= typename
Tree::difference_type
;
52 using key_compare
= typename
Tree::key_compare
;
53 using value_compare
= typename
Tree::value_compare
;
54 using allocator_type
= typename
Tree::allocator_type
;
55 using reference
= typename
Tree::reference
;
56 using const_reference
= typename
Tree::const_reference
;
57 using pointer
= typename
Tree::pointer
;
58 using const_pointer
= typename
Tree::const_pointer
;
59 using iterator
= typename
Tree::iterator
;
60 using const_iterator
= typename
Tree::const_iterator
;
61 using reverse_iterator
= typename
Tree::reverse_iterator
;
62 using const_reverse_iterator
= typename
Tree::const_reverse_iterator
;
64 // Constructors/assignments.
65 btree_container() : tree_(key_compare(), allocator_type()) {}
66 explicit btree_container(const key_compare
&comp
,
67 const allocator_type
&alloc
= allocator_type())
68 : tree_(comp
, alloc
) {}
69 btree_container(const btree_container
&x
) = default;
70 btree_container(btree_container
&&x
) noexcept
= default;
71 btree_container
&operator=(const btree_container
&x
) = default;
72 btree_container
&operator=(btree_container
&&x
) noexcept(
73 std::is_nothrow_move_assignable
<Tree
>::value
) = default;
76 iterator
begin() { return tree_
.begin(); }
77 const_iterator
begin() const { return tree_
.begin(); }
78 const_iterator
cbegin() const { return tree_
.begin(); }
79 iterator
end() { return tree_
.end(); }
80 const_iterator
end() const { return tree_
.end(); }
81 const_iterator
cend() const { return tree_
.end(); }
82 reverse_iterator
rbegin() { return tree_
.rbegin(); }
83 const_reverse_iterator
rbegin() const { return tree_
.rbegin(); }
84 const_reverse_iterator
crbegin() const { return tree_
.rbegin(); }
85 reverse_iterator
rend() { return tree_
.rend(); }
86 const_reverse_iterator
rend() const { return tree_
.rend(); }
87 const_reverse_iterator
crend() const { return tree_
.rend(); }
90 template <typename K
= key_type
>
91 iterator
find(const key_arg
<K
> &key
) {
92 return tree_
.find(key
);
94 template <typename K
= key_type
>
95 const_iterator
find(const key_arg
<K
> &key
) const {
96 return tree_
.find(key
);
98 template <typename K
= key_type
>
99 bool contains(const key_arg
<K
> &key
) const {
100 return find(key
) != end();
102 template <typename K
= key_type
>
103 iterator
lower_bound(const key_arg
<K
> &key
) {
104 return tree_
.lower_bound(key
);
106 template <typename K
= key_type
>
107 const_iterator
lower_bound(const key_arg
<K
> &key
) const {
108 return tree_
.lower_bound(key
);
110 template <typename K
= key_type
>
111 iterator
upper_bound(const key_arg
<K
> &key
) {
112 return tree_
.upper_bound(key
);
114 template <typename K
= key_type
>
115 const_iterator
upper_bound(const key_arg
<K
> &key
) const {
116 return tree_
.upper_bound(key
);
118 template <typename K
= key_type
>
119 std::pair
<iterator
, iterator
> equal_range(const key_arg
<K
> &key
) {
120 return tree_
.equal_range(key
);
122 template <typename K
= key_type
>
123 std::pair
<const_iterator
, const_iterator
> equal_range(
124 const key_arg
<K
> &key
) const {
125 return tree_
.equal_range(key
);
128 // Deletion routines. Note that there is also a deletion routine that is
129 // specific to btree_set_container/btree_multiset_container.
131 // Erase the specified iterator from the btree. The iterator must be valid
132 // (i.e. not equal to end()). Return an iterator pointing to the node after
133 // the one that was erased (or end() if none exists).
134 iterator
erase(const_iterator iter
) { return tree_
.erase(iterator(iter
)); }
135 iterator
erase(iterator iter
) { return tree_
.erase(iter
); }
136 iterator
erase(const_iterator first
, const_iterator last
) {
137 return tree_
.erase(iterator(first
), iterator(last
)).second
;
142 void clear() { tree_
.clear(); }
143 void swap(btree_container
&x
) { tree_
.swap(x
.tree_
); }
144 void verify() const { tree_
.verify(); }
147 size_type
size() const { return tree_
.size(); }
148 size_type
max_size() const { return tree_
.max_size(); }
149 bool empty() const { return tree_
.empty(); }
151 friend bool operator==(const btree_container
&x
, const btree_container
&y
) {
152 if (x
.size() != y
.size()) return false;
153 return std::equal(x
.begin(), x
.end(), y
.begin());
156 friend bool operator!=(const btree_container
&x
, const btree_container
&y
) {
160 friend bool operator<(const btree_container
&x
, const btree_container
&y
) {
161 return std::lexicographical_compare(x
.begin(), x
.end(), y
.begin(), y
.end());
164 friend bool operator>(const btree_container
&x
, const btree_container
&y
) {
168 friend bool operator<=(const btree_container
&x
, const btree_container
&y
) {
172 friend bool operator>=(const btree_container
&x
, const btree_container
&y
) {
176 // The allocator used by the btree.
177 allocator_type
get_allocator() const { return tree_
.get_allocator(); }
179 // The key comparator used by the btree.
180 key_compare
key_comp() const { return tree_
.key_comp(); }
181 value_compare
value_comp() const { return tree_
.value_comp(); }
187 // A common base class for btree_set and btree_map.
188 template <typename Tree
>
189 class btree_set_container
: public btree_container
<Tree
> {
190 using super_type
= btree_container
<Tree
>;
191 using params_type
= typename
Tree::params_type
;
192 using init_type
= typename
params_type::init_type
;
193 using is_key_compare_to
= typename
params_type::is_key_compare_to
;
194 friend class BtreeNodePeer
;
198 using key_arg
= typename
super_type::template key_arg
<K
>;
201 using key_type
= typename
Tree::key_type
;
202 using value_type
= typename
Tree::value_type
;
203 using size_type
= typename
Tree::size_type
;
204 using key_compare
= typename
Tree::key_compare
;
205 using allocator_type
= typename
Tree::allocator_type
;
206 using iterator
= typename
Tree::iterator
;
207 using const_iterator
= typename
Tree::const_iterator
;
209 // Inherit constructors.
210 using super_type::super_type
;
211 btree_set_container() {}
213 // Range constructor.
214 template <class InputIterator
>
215 btree_set_container(InputIterator b
, InputIterator e
,
216 const key_compare
&comp
= key_compare(),
217 const allocator_type
&alloc
= allocator_type())
218 : super_type(comp
, alloc
) {
222 // Initializer list constructor.
223 btree_set_container(std::initializer_list
<init_type
> init
,
224 const key_compare
&comp
= key_compare(),
225 const allocator_type
&alloc
= allocator_type())
226 : btree_set_container(init
.begin(), init
.end(), comp
, alloc
) {}
229 template <typename K
= key_type
>
230 size_type
count(const key_arg
<K
> &key
) const {
231 return this->tree_
.count_unique(key
);
234 // Insertion routines.
235 std::pair
<iterator
, bool> insert(const value_type
&x
) {
236 return this->tree_
.insert_unique(params_type::key(x
), x
);
238 std::pair
<iterator
, bool> insert(value_type
&&x
) {
239 return this->tree_
.insert_unique(params_type::key(x
), std::move(x
));
241 template <typename
... Args
>
242 std::pair
<iterator
, bool> emplace(Args
&&... args
) {
243 init_type
v(std::forward
<Args
>(args
)...);
244 return this->tree_
.insert_unique(params_type::key(v
), std::move(v
));
246 iterator
insert(const_iterator position
, const value_type
&x
) {
248 .insert_hint_unique(iterator(position
), params_type::key(x
), x
)
251 iterator
insert(const_iterator position
, value_type
&&x
) {
253 .insert_hint_unique(iterator(position
), params_type::key(x
),
257 template <typename
... Args
>
258 iterator
emplace_hint(const_iterator position
, Args
&&... args
) {
259 init_type
v(std::forward
<Args
>(args
)...);
261 .insert_hint_unique(iterator(position
), params_type::key(v
),
265 template <typename InputIterator
>
266 void insert(InputIterator b
, InputIterator e
) {
267 this->tree_
.insert_iterator_unique(b
, e
);
269 void insert(std::initializer_list
<init_type
> init
) {
270 this->tree_
.insert_iterator_unique(init
.begin(), init
.end());
272 // Deletion routines.
273 template <typename K
= key_type
>
274 size_type
erase(const key_arg
<K
> &key
) {
275 return this->tree_
.erase_unique(key
);
277 using super_type::erase
;
280 // Moves elements from `src` into `this`. If the element already exists in
281 // `this`, it is left unmodified in `src`.
284 typename
std::enable_if_t
<
286 std::is_same
<value_type
, typename
T::value_type
>,
287 std::is_same
<allocator_type
, typename
T::allocator_type
>,
288 std::is_same
<typename
params_type::is_map_container
,
289 typename
T::params_type::is_map_container
>>,
291 void merge(btree_container
<T
> &src
) { // NOLINT
292 for (auto src_it
= src
.begin(); src_it
!= src
.end();) {
293 if (insert(std::move(*src_it
)).second
) {
294 src_it
= src
.erase(src_it
);
303 typename
std::enable_if_t
<
305 std::is_same
<value_type
, typename
T::value_type
>,
306 std::is_same
<allocator_type
, typename
T::allocator_type
>,
307 std::is_same
<typename
params_type::is_map_container
,
308 typename
T::params_type::is_map_container
>>,
310 void merge(btree_container
<T
> &&src
) {
315 // A common base class for btree_map and safe_btree_map.
316 // Base class for btree_map.
317 template <typename Tree
>
318 class btree_map_container
: public btree_set_container
<Tree
> {
319 using super_type
= btree_set_container
<Tree
>;
320 using params_type
= typename
Tree::params_type
;
324 using key_arg
= typename
super_type::template key_arg
<K
>;
327 using key_type
= typename
Tree::key_type
;
328 using mapped_type
= typename
params_type::mapped_type
;
329 using value_type
= typename
Tree::value_type
;
330 using key_compare
= typename
Tree::key_compare
;
331 using allocator_type
= typename
Tree::allocator_type
;
332 using iterator
= typename
Tree::iterator
;
333 using const_iterator
= typename
Tree::const_iterator
;
335 // Inherit constructors.
336 using super_type::super_type
;
337 btree_map_container() {}
339 // Insertion routines.
340 template <typename
... Args
>
341 std::pair
<iterator
, bool> try_emplace(const key_type
&k
, Args
&&... args
) {
342 return this->tree_
.insert_unique(
343 k
, std::piecewise_construct
, std::forward_as_tuple(k
),
344 std::forward_as_tuple(std::forward
<Args
>(args
)...));
346 template <typename
... Args
>
347 std::pair
<iterator
, bool> try_emplace(key_type
&&k
, Args
&&... args
) {
348 // Note: `key_ref` exists to avoid a ClangTidy warning about moving from `k`
349 // and then using `k` unsequenced. This is safe because the move is into a
350 // forwarding reference and insert_unique guarantees that `key` is never
351 // referenced after consuming `args`.
352 const key_type
& key_ref
= k
;
353 return this->tree_
.insert_unique(
354 key_ref
, std::piecewise_construct
, std::forward_as_tuple(std::move(k
)),
355 std::forward_as_tuple(std::forward
<Args
>(args
)...));
357 template <typename
... Args
>
358 iterator
try_emplace(const_iterator hint
, const key_type
&k
,
361 .insert_hint_unique(iterator(hint
), k
, std::piecewise_construct
,
362 std::forward_as_tuple(k
),
363 std::forward_as_tuple(std::forward
<Args
>(args
)...))
366 template <typename
... Args
>
367 iterator
try_emplace(const_iterator hint
, key_type
&&k
, Args
&&... args
) {
368 // Note: `key_ref` exists to avoid a ClangTidy warning about moving from `k`
369 // and then using `k` unsequenced. This is safe because the move is into a
370 // forwarding reference and insert_hint_unique guarantees that `key` is
371 // never referenced after consuming `args`.
372 const key_type
& key_ref
= k
;
374 .insert_hint_unique(iterator(hint
), key_ref
, std::piecewise_construct
,
375 std::forward_as_tuple(std::move(k
)),
376 std::forward_as_tuple(std::forward
<Args
>(args
)...))
379 mapped_type
&operator[](const key_type
&k
) {
380 return try_emplace(k
).first
->second
;
382 mapped_type
&operator[](key_type
&&k
) {
383 return try_emplace(std::move(k
)).first
->second
;
386 template <typename K
= key_type
>
387 mapped_type
&at(const key_arg
<K
> &key
) {
388 auto it
= this->find(key
);
389 if (it
== this->end())
390 throw std::out_of_range("btree_map::at");
393 template <typename K
= key_type
>
394 const mapped_type
&at(const key_arg
<K
> &key
) const {
395 auto it
= this->find(key
);
396 if (it
== this->end())
397 throw std::out_of_range("btree_map::at");
402 // A common base class for btree_multiset and btree_multimap.
403 template <typename Tree
>
404 class btree_multiset_container
: public btree_container
<Tree
> {
405 using super_type
= btree_container
<Tree
>;
406 using params_type
= typename
Tree::params_type
;
407 using init_type
= typename
params_type::init_type
;
408 using is_key_compare_to
= typename
params_type::is_key_compare_to
;
411 using key_arg
= typename
super_type::template key_arg
<K
>;
414 using key_type
= typename
Tree::key_type
;
415 using value_type
= typename
Tree::value_type
;
416 using size_type
= typename
Tree::size_type
;
417 using key_compare
= typename
Tree::key_compare
;
418 using allocator_type
= typename
Tree::allocator_type
;
419 using iterator
= typename
Tree::iterator
;
420 using const_iterator
= typename
Tree::const_iterator
;
421 using node_type
= typename
super_type::node_type
;
423 // Inherit constructors.
424 using super_type::super_type
;
425 btree_multiset_container() {}
427 // Range constructor.
428 template <class InputIterator
>
429 btree_multiset_container(InputIterator b
, InputIterator e
,
430 const key_compare
&comp
= key_compare(),
431 const allocator_type
&alloc
= allocator_type())
432 : super_type(comp
, alloc
) {
436 // Initializer list constructor.
437 btree_multiset_container(std::initializer_list
<init_type
> init
,
438 const key_compare
&comp
= key_compare(),
439 const allocator_type
&alloc
= allocator_type())
440 : btree_multiset_container(init
.begin(), init
.end(), comp
, alloc
) {}
443 template <typename K
= key_type
>
444 size_type
count(const key_arg
<K
> &key
) const {
445 return this->tree_
.count_multi(key
);
448 // Insertion routines.
449 iterator
insert(const value_type
&x
) { return this->tree_
.insert_multi(x
); }
450 iterator
insert(value_type
&&x
) {
451 return this->tree_
.insert_multi(std::move(x
));
453 iterator
insert(const_iterator position
, const value_type
&x
) {
454 return this->tree_
.insert_hint_multi(iterator(position
), x
);
456 iterator
insert(const_iterator position
, value_type
&&x
) {
457 return this->tree_
.insert_hint_multi(iterator(position
), std::move(x
));
459 template <typename InputIterator
>
460 void insert(InputIterator b
, InputIterator e
) {
461 this->tree_
.insert_iterator_multi(b
, e
);
463 void insert(std::initializer_list
<init_type
> init
) {
464 this->tree_
.insert_iterator_multi(init
.begin(), init
.end());
466 template <typename
... Args
>
467 iterator
emplace(Args
&&... args
) {
468 return this->tree_
.insert_multi(init_type(std::forward
<Args
>(args
)...));
470 template <typename
... Args
>
471 iterator
emplace_hint(const_iterator position
, Args
&&... args
) {
472 return this->tree_
.insert_hint_multi(
473 iterator(position
), init_type(std::forward
<Args
>(args
)...));
475 iterator
insert(node_type
&&node
) {
476 if (!node
) return this->end();
478 this->tree_
.insert_multi(params_type::key(node
.slot()),
483 iterator
insert(const_iterator hint
, node_type
&&node
) {
484 if (!node
) return this->end();
485 iterator res
= this->tree_
.insert_hint_multi(
487 std::move(params_type::element(node
.slot())));
492 // Deletion routines.
493 template <typename K
= key_type
>
494 size_type
erase(const key_arg
<K
> &key
) {
495 return this->tree_
.erase_multi(key
);
497 using super_type::erase
;
500 // Moves all elements from `src` into `this`.
503 typename
std::enable_if_t
<
505 std::is_same
<value_type
, typename
T::value_type
>,
506 std::is_same
<allocator_type
, typename
T::allocator_type
>,
507 std::is_same
<typename
params_type::is_map_container
,
508 typename
T::params_type::is_map_container
>>,
510 void merge(btree_container
<T
> &src
) { // NOLINT
511 insert(std::make_move_iterator(src
.begin()),
512 std::make_move_iterator(src
.end()));
518 typename
std::enable_if_t
<
520 std::is_same
<value_type
, typename
T::value_type
>,
521 std::is_same
<allocator_type
, typename
T::allocator_type
>,
522 std::is_same
<typename
params_type::is_map_container
,
523 typename
T::params_type::is_map_container
>>,
525 void merge(btree_container
<T
> &&src
) {
530 // A base class for btree_multimap.
531 template <typename Tree
>
532 class btree_multimap_container
: public btree_multiset_container
<Tree
> {
533 using super_type
= btree_multiset_container
<Tree
>;
534 using params_type
= typename
Tree::params_type
;
537 using mapped_type
= typename
params_type::mapped_type
;
539 // Inherit constructors.
540 using super_type::super_type
;
541 btree_multimap_container() {}
543 } // namespace btree::internal