Swiftdiff options
Diffstat (limited to '3rdParty/Boost/src/boost/unordered')
5 files changed, 139 insertions, 41 deletions
diff --git a/3rdParty/Boost/src/boost/unordered/detail/buckets.hpp b/3rdParty/Boost/src/boost/unordered/detail/buckets.hpp index b1dee5c..913dbcd 100644 --- a/3rdParty/Boost/src/boost/unordered/detail/buckets.hpp +++ b/3rdParty/Boost/src/boost/unordered/detail/buckets.hpp @@ -64,7 +64,7 @@ namespace boost { namespace unordered_detail { inline void hash_buckets<A, G>::delete_node(node_ptr b) { node* raw_ptr = static_cast<node*>(&*b); - boost::unordered_detail::destroy(&raw_ptr->value()); + boost::unordered_detail::destroy(raw_ptr->value_ptr()); real_node_ptr n(node_alloc().address(*raw_ptr)); node_alloc().destroy(n); node_alloc().deallocate(n, 1); diff --git a/3rdParty/Boost/src/boost/unordered/detail/fwd.hpp b/3rdParty/Boost/src/boost/unordered/detail/fwd.hpp index be4d5e1..471d1d2 100644 --- a/3rdParty/Boost/src/boost/unordered/detail/fwd.hpp +++ b/3rdParty/Boost/src/boost/unordered/detail/fwd.hpp @@ -21,14 +21,14 @@ // This header defines most of the classes used to implement the unordered // containers. It doesn't include the insert methods as they require a lot -// of preprocessor metaprogramming - they are in insert.hpp +// of preprocessor metaprogramming - they are in unique.hpp and equivalent.hpp. // Template parameters: // // H = Hash Function // P = Predicate // A = Value Allocator -// G = Grouped/Ungrouped +// G = Bucket group policy, 'grouped' or 'ungrouped' // E = Key Extractor #if !defined(BOOST_NO_RVALUE_REFERENCES) && !defined(BOOST_NO_VARIADIC_TEMPLATES) @@ -90,7 +90,37 @@ namespace boost { namespace unordered_detail { #pragma warning(pop) #endif + //////////////////////////////////////////////////////////////////////////// + // + // This section implements buckets and nodes. Here's a rough + // inheritance diagram, to show how they pull together. + // + // For unordered_set/unordered_map: + // + // hash_bucket<A> + // | + // ungrouped_node_base<A> value_base<A::value_type> + // | | + // +--------------+-------------+ + // | + // hash_node<A, ungrouped> + // + // For unordered_multiset/unordered_multimap: + // + // hash_bucket<A> + // | + // grouped_node_base<A> value_base<A::value_type> + // | | + // +--------------+-------------+ + // | + // hash_node<A, grouped> + // hash_bucket + // + // hash_bucket is used for both the buckets and as a base class for + // nodes. By using 'bucket_ptr' for 'node_ptr', 'next_' can point + // to either a bucket or a node. This is used later to implement a + // sentinel at the end of the bucket array. template <class A> class hash_bucket @@ -109,6 +139,16 @@ namespace boost { namespace unordered_detail { hash_bucket() : next_() {} }; + // In containers with equivalent keys (unordered_multimap and + // unordered_multiset) equivalent nodes are grouped together, in + // containers with unique keys (unordered_map and unordered_set) + // individual nodes are treated as groups of one. The following two + // classes implement the data structure. + + // This is used for containers with unique keys. There are no groups + // so it doesn't add any extra members, and just treats individual + // nodes as groups of one. + template <class A> struct ungrouped_node_base : hash_bucket<A> { typedef hash_bucket<A> bucket; @@ -125,6 +165,10 @@ namespace boost { namespace unordered_detail { static void unlink_nodes(bucket& b, node_ptr end); }; + // This is used for containers with equivalent keys. It implements a + // circular list running in the opposite direction to the linked + // list through the nodes. + template <class A> struct grouped_node_base : hash_bucket<A> { @@ -151,6 +195,10 @@ namespace boost { namespace unordered_detail { } }; + // These two classes implement an easy way to pass around the node + // group policy classes without the messy template parameters. + // Whenever you see the template parameter 'G' it's one of these. + struct ungrouped { template <class A> @@ -167,6 +215,8 @@ namespace boost { namespace unordered_detail { }; }; + // The space used to store values in a node. + template <class ValueType> struct value_base { @@ -181,6 +231,9 @@ namespace boost { namespace unordered_detail { value_type& value() { return *(ValueType*) this; } + value_type* value_ptr() { + return (ValueType*) this; + } private: value_base& operator=(value_base const&); }; @@ -199,11 +252,20 @@ namespace boost { namespace unordered_detail { static value_type& get_value(node_ptr p) { return static_cast<hash_node&>(*p).value(); } + static value_type* get_value_ptr(node_ptr p) { + return static_cast<hash_node&>(*p).value_ptr(); + } private: hash_node& operator=(hash_node const&); }; + //////////////////////////////////////////////////////////////////////////// + // // Iterator Base + // + // This is the iterator used internally, the external iterators are + // provided by lightweight wrappers (hash_iterator and + // hast_const_iterator) which provide the full iterator interface. template <class A, class G> class hash_iterator_base @@ -248,12 +310,24 @@ namespace boost { namespace unordered_detail { } }; + //////////////////////////////////////////////////////////////////////////// + // + // Now the main data structure: + // + // hash_buckets<A, G> hash_buffered_functions<H, P> + // | | + // +-------------+--------------+ + // | + // hash_table<T> + // + // T is a class which contains typedefs for all the types we need. + // hash_buckets // // This is responsible for allocating and deallocating buckets and nodes. // // Notes: - // 1. For the sake exception safety the allocators themselves don't allocate + // 1. For the sake exception safety the consturctors don't allocate // anything. // 2. It's the callers responsibility to allocate the buckets before calling // any of the methods (other than getters and setters). @@ -327,6 +401,17 @@ namespace boost { namespace unordered_detail { std::size_t delete_to_bucket_end(node_ptr begin); }; + // Assigning and swapping the equality and hash function objects + // needs strong exception safety. To implement that normally we'd + // require one of them to be known to not throw and the other to + // guarantee strong exception safety. Unfortunately they both only + // have basic exception safety. So to acheive strong exception + // safety we have storage space for two copies, and assign the new + // copies to the unused space. Then switch to using that to use + // them. This is implemented in 'set_hash_functions' which + // atomically assigns the new function objects in a strongly + // exception safe manner. + template <class H, class P> class set_hash_functions; template <class H, class P> @@ -429,6 +514,12 @@ namespace boost { namespace unordered_detail { } }; + // This implements almost all of the required functionality, apart + // from some things that are specific to containers with unique and + // equivalent keys which is implemented in hash_unique_table and + // hash_equivalent_table. See unique.hpp and equivalent.hpp for + // their declaration and implementation. + template <class T> class hash_table : public T::buckets, public T::buffered_functions { @@ -569,9 +660,13 @@ namespace boost { namespace unordered_detail { node_constructor&, std::size_t); }; - // Iterator Access + /////////////////////////////////////////////////////////////////// + // + // Iterators + + // iterator_access is used to access the internal iterator without + // making it publicly available. -#if !defined(__clang__) class iterator_access { public: @@ -582,30 +677,6 @@ namespace boost { namespace unordered_detail { return it.base_; } }; -#else - class iterator_access - { - public: - // Note: we access Iterator::base here, rather than in the function - // signature to work around a bug in the friend support of an - // early version of clang. - - template <class Iterator> - struct base - { - typedef BOOST_DEDUCED_TYPENAME Iterator::base type; - }; - - template <class Iterator> - static BOOST_DEDUCED_TYPENAME base<Iterator>::type const& - get(Iterator const& it) - { - return it.base_; - } - }; -#endif - - // Iterators template <class A, class G> class hash_iterator; template <class A, class G> class hash_const_iterator; @@ -644,7 +715,7 @@ namespace boost { namespace unordered_detail { return node::get_value(ptr_); } value_type* operator->() const { - return &node::get_value(ptr_); + return node::get_value_ptr(ptr_); } hash_local_iterator& operator++() { ptr_ = ptr_->next_; return *this; @@ -694,7 +765,7 @@ namespace boost { namespace unordered_detail { return node::get_value(ptr_); } value_type const* operator->() const { - return &node::get_value(ptr_); + return node::get_value_ptr(ptr_); } hash_const_local_iterator& operator++() { ptr_ = ptr_->next_; return *this; @@ -716,7 +787,7 @@ namespace boost { namespace unordered_detail { } }; - // iterators + // Iterators // // all no throw @@ -823,7 +894,12 @@ namespace boost { namespace unordered_detail { } }; + //////////////////////////////////////////////////////////////////////////// + // // types + // + // This is used to convieniently pass around a container's typedefs + // without having 7 template parameters. template <class K, class V, class H, class P, class A, class E, class G> struct types diff --git a/3rdParty/Boost/src/boost/unordered/detail/util.hpp b/3rdParty/Boost/src/boost/unordered/detail/util.hpp index 5540965..989883e 100644 --- a/3rdParty/Boost/src/boost/unordered/detail/util.hpp +++ b/3rdParty/Boost/src/boost/unordered/detail/util.hpp @@ -299,7 +299,7 @@ namespace boost { namespace unordered_detail { #if BOOST_WORKAROUND(__CODEGEARC__, BOOST_TESTED_AT(0x0613)) struct dummy { hash_node<Alloc, Grouped> x; }; #endif - boost::unordered_detail::destroy(&node_->value()); + boost::unordered_detail::destroy(node_->value_ptr()); } if (node_constructed_) @@ -322,7 +322,7 @@ namespace boost { namespace unordered_detail { } else { BOOST_ASSERT(node_constructed_ && value_constructed_); - boost::unordered_detail::destroy(&node_->value()); + boost::unordered_detail::destroy(node_->value_ptr()); value_constructed_ = false; } } diff --git a/3rdParty/Boost/src/boost/unordered/unordered_map.hpp b/3rdParty/Boost/src/boost/unordered/unordered_map.hpp index 5bad0eb..86a6fc6 100644 --- a/3rdParty/Boost/src/boost/unordered/unordered_map.hpp +++ b/3rdParty/Boost/src/boost/unordered/unordered_map.hpp @@ -160,6 +160,11 @@ namespace boost ~unordered_map() {} #if !defined(BOOST_NO_RVALUE_REFERENCES) + unordered_map(unordered_map const& other) + : table_(other.table_) + { + } + unordered_map(unordered_map&& other) : table_(other.table_, boost::unordered_detail::move_tag()) { @@ -170,6 +175,12 @@ namespace boost { } + unordered_map& operator=(unordered_map const& x) + { + table_ = x.table_; + return *this; + } + unordered_map& operator=(unordered_map&& x) { table_.move(x.table_); @@ -705,6 +716,11 @@ namespace boost ~unordered_multimap() {} #if !defined(BOOST_NO_RVALUE_REFERENCES) + unordered_multimap(unordered_multimap const& other) + : table_(other.table_) + { + } + unordered_multimap(unordered_multimap&& other) : table_(other.table_, boost::unordered_detail::move_tag()) { @@ -715,6 +731,12 @@ namespace boost { } + unordered_multimap& operator=(unordered_multimap const& x) + { + table_ = x.table_; + return *this; + } + unordered_multimap& operator=(unordered_multimap&& x) { table_.move(x.table_); diff --git a/3rdParty/Boost/src/boost/unordered/unordered_map_fwd.hpp b/3rdParty/Boost/src/boost/unordered/unordered_map_fwd.hpp index 5e9bb07..edecc5d 100644 --- a/3rdParty/Boost/src/boost/unordered/unordered_map_fwd.hpp +++ b/3rdParty/Boost/src/boost/unordered/unordered_map_fwd.hpp @@ -24,13 +24,13 @@ namespace boost class A = std::allocator<std::pair<const K, T> > > class unordered_map; template <class K, class T, class H, class P, class A> - bool operator==(unordered_map<K, T, H, P, A> const&, + inline bool operator==(unordered_map<K, T, H, P, A> const&, unordered_map<K, T, H, P, A> const&); template <class K, class T, class H, class P, class A> - bool operator!=(unordered_map<K, T, H, P, A> const&, + inline bool operator!=(unordered_map<K, T, H, P, A> const&, unordered_map<K, T, H, P, A> const&); template <class K, class T, class H, class P, class A> - void swap(unordered_map<K, T, H, P, A>&, + inline void swap(unordered_map<K, T, H, P, A>&, unordered_map<K, T, H, P, A>&); template <class K, @@ -40,13 +40,13 @@ namespace boost class A = std::allocator<std::pair<const K, T> > > class unordered_multimap; template <class K, class T, class H, class P, class A> - bool operator==(unordered_multimap<K, T, H, P, A> const&, + inline bool operator==(unordered_multimap<K, T, H, P, A> const&, unordered_multimap<K, T, H, P, A> const&); template <class K, class T, class H, class P, class A> - bool operator!=(unordered_multimap<K, T, H, P, A> const&, + inline bool operator!=(unordered_multimap<K, T, H, P, A> const&, unordered_multimap<K, T, H, P, A> const&); template <class K, class T, class H, class P, class A> - void swap(unordered_multimap<K, T, H, P, A>&, + inline void swap(unordered_multimap<K, T, H, P, A>&, unordered_multimap<K, T, H, P, A>&); } |