1// Copyright (C) 2022-2023 Christian Mazakas
2// Distributed under the Boost Software License, Version 1.0. (See accompanying
3// file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
4
5#ifndef BOOST_UNORDERED_UNORDERED_NODE_SET_HPP_INCLUDED
6#define BOOST_UNORDERED_UNORDERED_NODE_SET_HPP_INCLUDED
7
8#include <boost/config.hpp>
9#if defined(BOOST_HAS_PRAGMA_ONCE)
10#pragma once
11#endif
12
13#include <boost/unordered/detail/foa/element_type.hpp>
14#include <boost/unordered/detail/foa/node_handle.hpp>
15#include <boost/unordered/detail/foa/node_set_types.hpp>
16#include <boost/unordered/detail/foa/table.hpp>
17#include <boost/unordered/detail/serialize_container.hpp>
18#include <boost/unordered/detail/type_traits.hpp>
19#include <boost/unordered/unordered_node_set_fwd.hpp>
20
21#include <boost/core/allocator_access.hpp>
22#include <boost/container_hash/hash.hpp>
23#include <boost/throw_exception.hpp>
24
25#include <initializer_list>
26#include <iterator>
27#include <type_traits>
28#include <utility>
29
30namespace boost {
31 namespace unordered {
32
33#if defined(BOOST_MSVC)
34#pragma warning(push)
35#pragma warning(disable : 4714) /* marked as __forceinline not inlined */
36#endif
37
38 namespace detail {
39 template <class TypePolicy, class Allocator>
40 struct node_set_handle
41 : public detail::foa::node_handle_base<TypePolicy, Allocator>
42 {
43 private:
44 using base_type = detail::foa::node_handle_base<TypePolicy, Allocator>;
45
46 using typename base_type::type_policy;
47
48 template <class Key, class Hash, class Pred, class Alloc>
49 friend class boost::unordered::unordered_node_set;
50
51 public:
52 using value_type = typename TypePolicy::value_type;
53
54 constexpr node_set_handle() noexcept = default;
55 node_set_handle(node_set_handle&& nh) noexcept = default;
56 node_set_handle& operator=(node_set_handle&&) noexcept = default;
57
58 value_type& value() const
59 {
60 BOOST_ASSERT(!this->empty());
61 return const_cast<value_type&>(this->data());
62 }
63 };
64 } // namespace detail
65
66 template <class Key, class Hash, class KeyEqual, class Allocator>
67 class unordered_node_set
68 {
69 using set_types = detail::foa::node_set_types<Key,
70 typename boost::allocator_void_pointer<Allocator>::type>;
71
72 using table_type = detail::foa::table<set_types, Hash, KeyEqual,
73 typename boost::allocator_rebind<Allocator,
74 typename set_types::value_type>::type>;
75
76 table_type table_;
77
78 template <class K, class H, class KE, class A>
79 bool friend operator==(unordered_node_set<K, H, KE, A> const& lhs,
80 unordered_node_set<K, H, KE, A> const& rhs);
81
82 template <class K, class H, class KE, class A, class Pred>
83 typename unordered_node_set<K, H, KE, A>::size_type friend erase_if(
84 unordered_node_set<K, H, KE, A>& set, Pred pred);
85
86 public:
87 using key_type = Key;
88 using value_type = typename set_types::value_type;
89 using init_type = typename set_types::init_type;
90 using size_type = std::size_t;
91 using difference_type = std::ptrdiff_t;
92 using hasher = Hash;
93 using key_equal = KeyEqual;
94 using allocator_type = Allocator;
95 using reference = value_type&;
96 using const_reference = value_type const&;
97 using pointer = typename boost::allocator_pointer<allocator_type>::type;
98 using const_pointer =
99 typename boost::allocator_const_pointer<allocator_type>::type;
100 using iterator = typename table_type::iterator;
101 using const_iterator = typename table_type::const_iterator;
102 using node_type = detail::node_set_handle<set_types,
103 typename boost::allocator_rebind<Allocator,
104 typename set_types::value_type>::type>;
105 using insert_return_type =
106 detail::foa::insert_return_type<iterator, node_type>;
107
108 unordered_node_set() : unordered_node_set(0) {}
109
110 explicit unordered_node_set(size_type n, hasher const& h = hasher(),
111 key_equal const& pred = key_equal(),
112 allocator_type const& a = allocator_type())
113 : table_(n, h, pred, a)
114 {
115 }
116
117 unordered_node_set(size_type n, allocator_type const& a)
118 : unordered_node_set(n, hasher(), key_equal(), a)
119 {
120 }
121
122 unordered_node_set(size_type n, hasher const& h, allocator_type const& a)
123 : unordered_node_set(n, h, key_equal(), a)
124 {
125 }
126
127 template <class InputIterator>
128 unordered_node_set(
129 InputIterator f, InputIterator l, allocator_type const& a)
130 : unordered_node_set(f, l, size_type(0), hasher(), key_equal(), a)
131 {
132 }
133
134 explicit unordered_node_set(allocator_type const& a)
135 : unordered_node_set(0, a)
136 {
137 }
138
139 template <class Iterator>
140 unordered_node_set(Iterator first, Iterator last, size_type n = 0,
141 hasher const& h = hasher(), key_equal const& pred = key_equal(),
142 allocator_type const& a = allocator_type())
143 : unordered_node_set(n, h, pred, a)
144 {
145 this->insert(first, last);
146 }
147
148 template <class InputIt>
149 unordered_node_set(
150 InputIt first, InputIt last, size_type n, allocator_type const& a)
151 : unordered_node_set(first, last, n, hasher(), key_equal(), a)
152 {
153 }
154
155 template <class Iterator>
156 unordered_node_set(Iterator first, Iterator last, size_type n,
157 hasher const& h, allocator_type const& a)
158 : unordered_node_set(first, last, n, h, key_equal(), a)
159 {
160 }
161
162 unordered_node_set(unordered_node_set const& other) : table_(other.table_)
163 {
164 }
165
166 unordered_node_set(
167 unordered_node_set const& other, allocator_type const& a)
168 : table_(other.table_, a)
169 {
170 }
171
172 unordered_node_set(unordered_node_set&& other)
173 noexcept(std::is_nothrow_move_constructible<table_type>::value)
174 : table_(std::move(other.table_))
175 {
176 }
177
178 unordered_node_set(unordered_node_set&& other, allocator_type const& al)
179 : table_(std::move(other.table_), al)
180 {
181 }
182
183 unordered_node_set(std::initializer_list<value_type> ilist,
184 size_type n = 0, hasher const& h = hasher(),
185 key_equal const& pred = key_equal(),
186 allocator_type const& a = allocator_type())
187 : unordered_node_set(ilist.begin(), ilist.end(), n, h, pred, a)
188 {
189 }
190
191 unordered_node_set(
192 std::initializer_list<value_type> il, allocator_type const& a)
193 : unordered_node_set(il, size_type(0), hasher(), key_equal(), a)
194 {
195 }
196
197 unordered_node_set(std::initializer_list<value_type> init, size_type n,
198 allocator_type const& a)
199 : unordered_node_set(init, n, hasher(), key_equal(), a)
200 {
201 }
202
203 unordered_node_set(std::initializer_list<value_type> init, size_type n,
204 hasher const& h, allocator_type const& a)
205 : unordered_node_set(init, n, h, key_equal(), a)
206 {
207 }
208
209 ~unordered_node_set() = default;
210
211 unordered_node_set& operator=(unordered_node_set const& other)
212 {
213 table_ = other.table_;
214 return *this;
215 }
216
217 unordered_node_set& operator=(unordered_node_set&& other) noexcept(
218 noexcept(std::declval<table_type&>() = std::declval<table_type&&>()))
219 {
220 table_ = std::move(other.table_);
221 return *this;
222 }
223
224 allocator_type get_allocator() const noexcept
225 {
226 return table_.get_allocator();
227 }
228
229 /// Iterators
230 ///
231
232 iterator begin() noexcept { return table_.begin(); }
233 const_iterator begin() const noexcept { return table_.begin(); }
234 const_iterator cbegin() const noexcept { return table_.cbegin(); }
235
236 iterator end() noexcept { return table_.end(); }
237 const_iterator end() const noexcept { return table_.end(); }
238 const_iterator cend() const noexcept { return table_.cend(); }
239
240 /// Capacity
241 ///
242
243 BOOST_ATTRIBUTE_NODISCARD bool empty() const noexcept
244 {
245 return table_.empty();
246 }
247
248 size_type size() const noexcept { return table_.size(); }
249
250 size_type max_size() const noexcept { return table_.max_size(); }
251
252 /// Modifiers
253 ///
254
255 void clear() noexcept { table_.clear(); }
256
257 BOOST_FORCEINLINE std::pair<iterator, bool> insert(
258 value_type const& value)
259 {
260 return table_.insert(value);
261 }
262
263 BOOST_FORCEINLINE std::pair<iterator, bool> insert(value_type&& value)
264 {
265 return table_.insert(std::move(value));
266 }
267
268 template <class K>
269 BOOST_FORCEINLINE typename std::enable_if<
270 detail::transparent_non_iterable<K, unordered_node_set>::value,
271 std::pair<iterator, bool> >::type
272 insert(K&& k)
273 {
274 return table_.try_emplace(std::forward<K>(k));
275 }
276
277 BOOST_FORCEINLINE iterator insert(const_iterator, value_type const& value)
278 {
279 return table_.insert(value).first;
280 }
281
282 BOOST_FORCEINLINE iterator insert(const_iterator, value_type&& value)
283 {
284 return table_.insert(std::move(value)).first;
285 }
286
287 template <class K>
288 BOOST_FORCEINLINE typename std::enable_if<
289 detail::transparent_non_iterable<K, unordered_node_set>::value,
290 iterator>::type
291 insert(const_iterator, K&& k)
292 {
293 return table_.try_emplace(std::forward<K>(k)).first;
294 }
295
296 template <class InputIterator>
297 void insert(InputIterator first, InputIterator last)
298 {
299 for (auto pos = first; pos != last; ++pos) {
300 table_.emplace(*pos);
301 }
302 }
303
304 void insert(std::initializer_list<value_type> ilist)
305 {
306 this->insert(ilist.begin(), ilist.end());
307 }
308
309 insert_return_type insert(node_type&& nh)
310 {
311 if (nh.empty()) {
312 return {end(), false, node_type{}};
313 }
314
315 BOOST_ASSERT(get_allocator() == nh.get_allocator());
316
317 auto itp = table_.insert(std::move(nh.element()));
318 if (itp.second) {
319 nh.reset();
320 return {itp.first, true, node_type{}};
321 } else {
322 return {itp.first, false, std::move(nh)};
323 }
324 }
325
326 iterator insert(const_iterator, node_type&& nh)
327 {
328 if (nh.empty()) {
329 return end();
330 }
331
332 BOOST_ASSERT(get_allocator() == nh.get_allocator());
333
334 auto itp = table_.insert(std::move(nh.element()));
335 if (itp.second) {
336 nh.reset();
337 return itp.first;
338 } else {
339 return itp.first;
340 }
341 }
342
343 template <class... Args>
344 BOOST_FORCEINLINE std::pair<iterator, bool> emplace(Args&&... args)
345 {
346 return table_.emplace(std::forward<Args>(args)...);
347 }
348
349 template <class... Args>
350 BOOST_FORCEINLINE iterator emplace_hint(const_iterator, Args&&... args)
351 {
352 return table_.emplace(std::forward<Args>(args)...).first;
353 }
354
355 BOOST_FORCEINLINE typename table_type::erase_return_type erase(
356 const_iterator pos)
357 {
358 return table_.erase(pos);
359 }
360
361 iterator erase(const_iterator first, const_iterator last)
362 {
363 while (first != last) {
364 this->erase(first++);
365 }
366 return iterator{detail::foa::const_iterator_cast_tag{}, last};
367 }
368
369 BOOST_FORCEINLINE size_type erase(key_type const& key)
370 {
371 return table_.erase(key);
372 }
373
374 template <class K>
375 BOOST_FORCEINLINE typename std::enable_if<
376 detail::transparent_non_iterable<K, unordered_node_set>::value,
377 size_type>::type
378 erase(K const& key)
379 {
380 return table_.erase(key);
381 }
382
383 void swap(unordered_node_set& rhs) noexcept(
384 noexcept(std::declval<table_type&>().swap(std::declval<table_type&>())))
385 {
386 table_.swap(rhs.table_);
387 }
388
389 node_type extract(const_iterator pos)
390 {
391 BOOST_ASSERT(pos != end());
392 node_type nh;
393 auto elem = table_.extract(pos);
394 nh.emplace(std::move(elem), get_allocator());
395 return nh;
396 }
397
398 node_type extract(key_type const& key)
399 {
400 auto pos = find(key);
401 return pos != end() ? extract(pos) : node_type();
402 }
403
404 template <class K>
405 typename std::enable_if<
406 boost::unordered::detail::transparent_non_iterable<K,
407 unordered_node_set>::value,
408 node_type>::type
409 extract(K const& key)
410 {
411 auto pos = find(key);
412 return pos != end() ? extract(pos) : node_type();
413 }
414
415 template <class H2, class P2>
416 void merge(unordered_node_set<key_type, H2, P2, allocator_type>& source)
417 {
418 BOOST_ASSERT(get_allocator() == source.get_allocator());
419 table_.merge(source.table_);
420 }
421
422 template <class H2, class P2>
423 void merge(unordered_node_set<key_type, H2, P2, allocator_type>&& source)
424 {
425 BOOST_ASSERT(get_allocator() == source.get_allocator());
426 table_.merge(std::move(source.table_));
427 }
428
429 /// Lookup
430 ///
431
432 BOOST_FORCEINLINE size_type count(key_type const& key) const
433 {
434 auto pos = table_.find(key);
435 return pos != table_.end() ? 1 : 0;
436 }
437
438 template <class K>
439 BOOST_FORCEINLINE typename std::enable_if<
440 detail::are_transparent<K, hasher, key_equal>::value, size_type>::type
441 count(K const& key) const
442 {
443 auto pos = table_.find(key);
444 return pos != table_.end() ? 1 : 0;
445 }
446
447 BOOST_FORCEINLINE iterator find(key_type const& key)
448 {
449 return table_.find(key);
450 }
451
452 BOOST_FORCEINLINE const_iterator find(key_type const& key) const
453 {
454 return table_.find(key);
455 }
456
457 template <class K>
458 BOOST_FORCEINLINE typename std::enable_if<
459 boost::unordered::detail::are_transparent<K, hasher, key_equal>::value,
460 iterator>::type
461 find(K const& key)
462 {
463 return table_.find(key);
464 }
465
466 template <class K>
467 BOOST_FORCEINLINE typename std::enable_if<
468 boost::unordered::detail::are_transparent<K, hasher, key_equal>::value,
469 const_iterator>::type
470 find(K const& key) const
471 {
472 return table_.find(key);
473 }
474
475 BOOST_FORCEINLINE bool contains(key_type const& key) const
476 {
477 return this->find(key) != this->end();
478 }
479
480 template <class K>
481 BOOST_FORCEINLINE typename std::enable_if<
482 boost::unordered::detail::are_transparent<K, hasher, key_equal>::value,
483 bool>::type
484 contains(K const& key) const
485 {
486 return this->find(key) != this->end();
487 }
488
489 std::pair<iterator, iterator> equal_range(key_type const& key)
490 {
491 auto pos = table_.find(key);
492 if (pos == table_.end()) {
493 return {pos, pos};
494 }
495
496 auto next = pos;
497 ++next;
498 return {pos, next};
499 }
500
501 std::pair<const_iterator, const_iterator> equal_range(
502 key_type const& key) const
503 {
504 auto pos = table_.find(key);
505 if (pos == table_.end()) {
506 return {pos, pos};
507 }
508
509 auto next = pos;
510 ++next;
511 return {pos, next};
512 }
513
514 template <class K>
515 typename std::enable_if<
516 detail::are_transparent<K, hasher, key_equal>::value,
517 std::pair<iterator, iterator> >::type
518 equal_range(K const& key)
519 {
520 auto pos = table_.find(key);
521 if (pos == table_.end()) {
522 return {pos, pos};
523 }
524
525 auto next = pos;
526 ++next;
527 return {pos, next};
528 }
529
530 template <class K>
531 typename std::enable_if<
532 detail::are_transparent<K, hasher, key_equal>::value,
533 std::pair<const_iterator, const_iterator> >::type
534 equal_range(K const& key) const
535 {
536 auto pos = table_.find(key);
537 if (pos == table_.end()) {
538 return {pos, pos};
539 }
540
541 auto next = pos;
542 ++next;
543 return {pos, next};
544 }
545
546 /// Hash Policy
547 ///
548
549 size_type bucket_count() const noexcept { return table_.capacity(); }
550
551 float load_factor() const noexcept { return table_.load_factor(); }
552
553 float max_load_factor() const noexcept
554 {
555 return table_.max_load_factor();
556 }
557
558 void max_load_factor(float) {}
559
560 size_type max_load() const noexcept { return table_.max_load(); }
561
562 void rehash(size_type n) { table_.rehash(n); }
563
564 void reserve(size_type n) { table_.reserve(n); }
565
566 /// Observers
567 ///
568
569 hasher hash_function() const { return table_.hash_function(); }
570
571 key_equal key_eq() const { return table_.key_eq(); }
572 };
573
574 template <class Key, class Hash, class KeyEqual, class Allocator>
575 bool operator==(
576 unordered_node_set<Key, Hash, KeyEqual, Allocator> const& lhs,
577 unordered_node_set<Key, Hash, KeyEqual, Allocator> const& rhs)
578 {
579 return lhs.table_ == rhs.table_;
580 }
581
582 template <class Key, class Hash, class KeyEqual, class Allocator>
583 bool operator!=(
584 unordered_node_set<Key, Hash, KeyEqual, Allocator> const& lhs,
585 unordered_node_set<Key, Hash, KeyEqual, Allocator> const& rhs)
586 {
587 return !(lhs == rhs);
588 }
589
590 template <class Key, class Hash, class KeyEqual, class Allocator>
591 void swap(unordered_node_set<Key, Hash, KeyEqual, Allocator>& lhs,
592 unordered_node_set<Key, Hash, KeyEqual, Allocator>& rhs)
593 noexcept(noexcept(lhs.swap(rhs)))
594 {
595 lhs.swap(rhs);
596 }
597
598 template <class Key, class Hash, class KeyEqual, class Allocator,
599 class Pred>
600 typename unordered_node_set<Key, Hash, KeyEqual, Allocator>::size_type
601 erase_if(unordered_node_set<Key, Hash, KeyEqual, Allocator>& set, Pred pred)
602 {
603 return erase_if(set.table_, pred);
604 }
605
606 template <class Archive, class Key, class Hash, class KeyEqual,
607 class Allocator>
608 void serialize(Archive& ar,
609 unordered_node_set<Key, Hash, KeyEqual, Allocator>& set,
610 unsigned int version)
611 {
612 detail::serialize_container(ar, set, version);
613 }
614
615#if defined(BOOST_MSVC)
616#pragma warning(pop) /* C4714 */
617#endif
618
619#if BOOST_UNORDERED_TEMPLATE_DEDUCTION_GUIDES
620 template <class InputIterator,
621 class Hash =
622 boost::hash<typename std::iterator_traits<InputIterator>::value_type>,
623 class Pred =
624 std::equal_to<typename std::iterator_traits<InputIterator>::value_type>,
625 class Allocator = std::allocator<
626 typename std::iterator_traits<InputIterator>::value_type>,
627 class = std::enable_if_t<detail::is_input_iterator_v<InputIterator> >,
628 class = std::enable_if_t<detail::is_hash_v<Hash> >,
629 class = std::enable_if_t<detail::is_pred_v<Pred> >,
630 class = std::enable_if_t<detail::is_allocator_v<Allocator> > >
631 unordered_node_set(InputIterator, InputIterator,
632 std::size_t = boost::unordered::detail::foa::default_bucket_count,
633 Hash = Hash(), Pred = Pred(), Allocator = Allocator())
634 -> unordered_node_set<
635 typename std::iterator_traits<InputIterator>::value_type, Hash, Pred,
636 Allocator>;
637
638 template <class T, class Hash = boost::hash<T>,
639 class Pred = std::equal_to<T>, class Allocator = std::allocator<T>,
640 class = std::enable_if_t<detail::is_hash_v<Hash> >,
641 class = std::enable_if_t<detail::is_pred_v<Pred> >,
642 class = std::enable_if_t<detail::is_allocator_v<Allocator> > >
643 unordered_node_set(std::initializer_list<T>,
644 std::size_t = boost::unordered::detail::foa::default_bucket_count,
645 Hash = Hash(), Pred = Pred(), Allocator = Allocator())
646 -> unordered_node_set<T, Hash, Pred, Allocator>;
647
648 template <class InputIterator, class Allocator,
649 class = std::enable_if_t<detail::is_input_iterator_v<InputIterator> >,
650 class = std::enable_if_t<detail::is_allocator_v<Allocator> > >
651 unordered_node_set(InputIterator, InputIterator, std::size_t, Allocator)
652 -> unordered_node_set<
653 typename std::iterator_traits<InputIterator>::value_type,
654 boost::hash<typename std::iterator_traits<InputIterator>::value_type>,
655 std::equal_to<typename std::iterator_traits<InputIterator>::value_type>,
656 Allocator>;
657
658 template <class InputIterator, class Hash, class Allocator,
659 class = std::enable_if_t<detail::is_hash_v<Hash> >,
660 class = std::enable_if_t<detail::is_input_iterator_v<InputIterator> >,
661 class = std::enable_if_t<detail::is_allocator_v<Allocator> > >
662 unordered_node_set(
663 InputIterator, InputIterator, std::size_t, Hash, Allocator)
664 -> unordered_node_set<
665 typename std::iterator_traits<InputIterator>::value_type, Hash,
666 std::equal_to<typename std::iterator_traits<InputIterator>::value_type>,
667 Allocator>;
668
669 template <class T, class Allocator,
670 class = std::enable_if_t<detail::is_allocator_v<Allocator> > >
671 unordered_node_set(std::initializer_list<T>, std::size_t, Allocator)
672 -> unordered_node_set<T, boost::hash<T>, std::equal_to<T>, Allocator>;
673
674 template <class T, class Hash, class Allocator,
675 class = std::enable_if_t<detail::is_hash_v<Hash> >,
676 class = std::enable_if_t<detail::is_allocator_v<Allocator> > >
677 unordered_node_set(std::initializer_list<T>, std::size_t, Hash, Allocator)
678 -> unordered_node_set<T, Hash, std::equal_to<T>, Allocator>;
679
680 template <class InputIterator, class Allocator,
681 class = std::enable_if_t<detail::is_input_iterator_v<InputIterator> >,
682 class = std::enable_if_t<detail::is_allocator_v<Allocator> > >
683 unordered_node_set(InputIterator, InputIterator, Allocator)
684 -> unordered_node_set<
685 typename std::iterator_traits<InputIterator>::value_type,
686 boost::hash<typename std::iterator_traits<InputIterator>::value_type>,
687 std::equal_to<typename std::iterator_traits<InputIterator>::value_type>,
688 Allocator>;
689
690 template <class T, class Allocator,
691 class = std::enable_if_t<detail::is_allocator_v<Allocator> > >
692 unordered_node_set(std::initializer_list<T>, Allocator)
693 -> unordered_node_set<T, boost::hash<T>, std::equal_to<T>, Allocator>;
694#endif
695
696 } // namespace unordered
697} // namespace boost
698
699#endif
700

source code of boost/libs/unordered/include/boost/unordered/unordered_node_set.hpp