1 files changed, 304 insertions, 0 deletions
diff --git a/3rdParty/Boost/src/boost/unordered/detail/equivalent.hpp b/3rdParty/Boost/src/boost/unordered/detail/equivalent.hpp
new file mode 100644
index 0000000..1c497c3
--- /dev/null
+++ b/3rdParty/Boost/src/boost/unordered/detail/equivalent.hpp
@@ -0,0 +1,304 @@
+
+// Copyright (C) 2003-2004 Jeremy B. Maitin-Shepard.
+// Copyright (C) 2005-2009 Daniel James
+// Distributed under the Boost Software License, Version 1.0. (See accompanying
+// file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
+
+#ifndef BOOST_UNORDERED_DETAIL_EQUIVALENT_HPP_INCLUDED
+#define BOOST_UNORDERED_DETAIL_EQUIVALENT_HPP_INCLUDED
+
+#include <boost/unordered/detail/table.hpp>
+#include <boost/unordered/detail/extract_key.hpp>
+
+namespace boost { namespace unordered_detail {
+
+    template <class T>
+    class hash_equivalent_table : public T::table
+    {
+    public:
+        typedef BOOST_DEDUCED_TYPENAME T::hasher hasher;
+        typedef BOOST_DEDUCED_TYPENAME T::key_equal key_equal;
+        typedef BOOST_DEDUCED_TYPENAME T::value_allocator value_allocator;
+        typedef BOOST_DEDUCED_TYPENAME T::key_type key_type;
+        typedef BOOST_DEDUCED_TYPENAME T::value_type value_type;
+        typedef BOOST_DEDUCED_TYPENAME T::table table;
+        typedef BOOST_DEDUCED_TYPENAME T::node_constructor node_constructor;
+
+        typedef BOOST_DEDUCED_TYPENAME T::node node;
+        typedef BOOST_DEDUCED_TYPENAME T::node_ptr node_ptr;
+        typedef BOOST_DEDUCED_TYPENAME T::bucket_ptr bucket_ptr;
+        typedef BOOST_DEDUCED_TYPENAME T::iterator_base iterator_base;
+        typedef BOOST_DEDUCED_TYPENAME T::extractor extractor;
+
+        // Constructors
+
+        hash_equivalent_table(std::size_t n,
+            hasher const& hf, key_equal const& eq, value_allocator const& a)
+          : table(n, hf, eq, a) {}
+        hash_equivalent_table(hash_equivalent_table const& x)
+          : table(x, x.node_alloc()) {}
+        hash_equivalent_table(hash_equivalent_table const& x,
+            value_allocator const& a)
+          : table(x, a) {}
+        hash_equivalent_table(hash_equivalent_table& x, move_tag m)
+          : table(x, m) {}
+        hash_equivalent_table(hash_equivalent_table& x,
+            value_allocator const& a, move_tag m)
+          : table(x, a, m) {}
+        ~hash_equivalent_table() {}
+
+        // Insert methods
+
+        iterator_base emplace_impl(node_constructor& a);
+        void emplace_impl_no_rehash(node_constructor& a);
+
+        // equals
+
+        bool equals(hash_equivalent_table const&) const;
+
+        inline node_ptr add_node(node_constructor& a,
+            bucket_ptr bucket, node_ptr pos);
+
+#if defined(BOOST_UNORDERED_STD_FORWARD)
+
+        template <class... Args>
+        iterator_base emplace(Args&&... args);
+
+#else
+
+#define BOOST_UNORDERED_INSERT_IMPL(z, n, _)                                   \
+        template <BOOST_UNORDERED_TEMPLATE_ARGS(z, n)>                         \
+        iterator_base emplace(BOOST_UNORDERED_FUNCTION_PARAMS(z, n));
+
+        BOOST_PP_REPEAT_FROM_TO(1, BOOST_UNORDERED_EMPLACE_LIMIT,
+            BOOST_UNORDERED_INSERT_IMPL, _)
+
+#undef BOOST_UNORDERED_INSERT_IMPL
+#endif
+
+        template <class I>
+        void insert_for_range(I i, I j, forward_traversal_tag);
+        template <class I>
+        void insert_for_range(I i, I j, boost::incrementable_traversal_tag);
+        template <class I>
+        void insert_range(I i, I j);
+    };
+
+    template <class H, class P, class A>
+    struct multiset : public types<
+        BOOST_DEDUCED_TYPENAME A::value_type,
+        BOOST_DEDUCED_TYPENAME A::value_type,
+        H, P, A,
+        set_extractor<BOOST_DEDUCED_TYPENAME A::value_type>,
+        grouped>
+    {
+        typedef hash_equivalent_table<multiset<H, P, A> > impl;
+        typedef hash_table<multiset<H, P, A> > table;
+    };
+
+    template <class K, class H, class P, class A>
+    struct multimap : public types<
+        K, BOOST_DEDUCED_TYPENAME A::value_type,
+        H, P, A,
+        map_extractor<K, BOOST_DEDUCED_TYPENAME A::value_type>,
+        grouped>
+    {
+        typedef hash_equivalent_table<multimap<K, H, P, A> > impl;
+        typedef hash_table<multimap<K, H, P, A> > table;
+    };
+
+    ////////////////////////////////////////////////////////////////////////////
+    // Equality
+
+    template <class T>
+    bool hash_equivalent_table<T>
+        ::equals(hash_equivalent_table<T> const& other) const
+    {
+        if(this->size_ != other.size_) return false;
+        if(!this->size_) return true;
+
+        bucket_ptr end = this->get_bucket(this->bucket_count_);
+        for(bucket_ptr i = this->cached_begin_bucket_; i != end; ++i)
+        {
+            node_ptr it1 = i->next_;
+            while(BOOST_UNORDERED_BORLAND_BOOL(it1))
+            {
+                node_ptr it2 = other.find_iterator(this->get_key_from_ptr(it1));
+                if(!BOOST_UNORDERED_BORLAND_BOOL(it2)) return false;
+                
+                node_ptr end1 = node::next_group(it1);
+                node_ptr end2 = node::next_group(it2);
+
+                do {
+                    if(!extractor::compare_mapped(
+                        node::get_value(it1), node::get_value(it2)))
+                        return false;
+                    it1 = it1->next_;
+                    it2 = it2->next_;
+                } while(it1 != end1 && it2 != end2);
+                if(it1 != end1 || it2 != end2) return false;
+            }
+        }
+
+        return true;
+    }
+
+    ////////////////////////////////////////////////////////////////////////////
+    // A convenience method for adding nodes.
+
+    template <class T>
+    inline BOOST_DEDUCED_TYPENAME hash_equivalent_table<T>::node_ptr
+        hash_equivalent_table<T>
+            ::add_node(node_constructor& a, bucket_ptr bucket, node_ptr pos)
+    {
+        node_ptr n = a.release();
+        if(BOOST_UNORDERED_BORLAND_BOOL(pos)) {
+            node::add_after_node(n, pos);                
+        }
+        else {
+            node::add_to_bucket(n, *bucket);
+            if(bucket < this->cached_begin_bucket_)
+                this->cached_begin_bucket_ = bucket;
+        }
+        ++this->size_;
+        return n;
+    }
+
+    ////////////////////////////////////////////////////////////////////////////
+    // Insert methods
+
+    template <class T>
+    inline BOOST_DEDUCED_TYPENAME
+        hash_equivalent_table<T>::iterator_base
+        hash_equivalent_table<T>::emplace_impl(node_constructor& a)
+    {
+        key_type const& k = this->get_key(a.value());
+        std::size_t hash_value = this->hash_function()(k);
+        
+        if(!this->size_) {
+            return this->emplace_empty_impl_with_node(a, 1);
+        }
+        else {
+            bucket_ptr bucket = this->bucket_ptr_from_hash(hash_value);
+            node_ptr position = this->find_iterator(bucket, k);
+
+            // reserve has basic exception safety if the hash function
+            // throws, strong otherwise.
+            if(this->reserve_for_insert(this->size_ + 1))
+                bucket = this->bucket_ptr_from_hash(hash_value);
+
+            return iterator_base(bucket, add_node(a, bucket, position));
+        }
+    }
+    
+    template <class T>
+    inline void hash_equivalent_table<T>
+            ::emplace_impl_no_rehash(node_constructor& a)
+    {
+        key_type const& k = this->get_key(a.value());
+        bucket_ptr bucket = this->get_bucket(this->bucket_index(k));
+        add_node(a, bucket, this->find_iterator(bucket, k));
+    }
+
+#if defined(BOOST_UNORDERED_STD_FORWARD)
+
+    // Emplace (equivalent key containers)
+    // (I'm using an overloaded emplace for both 'insert' and 'emplace')
+
+    // if hash function throws, basic exception safety
+    // strong otherwise
+    template <class T>
+    template <class... Args>
+    BOOST_DEDUCED_TYPENAME hash_equivalent_table<T>::iterator_base
+        hash_equivalent_table<T>
+            ::emplace(Args&&... args)
+    {
+        // Create the node before rehashing in case it throws an
+        // exception (need strong safety in such a case).
+        node_constructor a(*this);
+        a.construct(std::forward<Args>(args)...);
+
+        return emplace_impl(a);
+    }
+
+#else
+
+#define BOOST_UNORDERED_INSERT_IMPL(z, num_params, _)                       \
+    template <class T>                                                      \
+    template <BOOST_UNORDERED_TEMPLATE_ARGS(z, num_params)>                 \
+    BOOST_DEDUCED_TYPENAME hash_equivalent_table<T>::iterator_base          \
+        hash_equivalent_table<T>                                            \
+            ::emplace(BOOST_UNORDERED_FUNCTION_PARAMS(z, num_params))       \
+    {                                                                       \
+        node_constructor a(*this);                                          \
+        a.construct(BOOST_UNORDERED_CALL_PARAMS(z, num_params));            \
+        return emplace_impl(a);                                             \
+    }
+
+    BOOST_PP_REPEAT_FROM_TO(1, BOOST_UNORDERED_EMPLACE_LIMIT,
+        BOOST_UNORDERED_INSERT_IMPL, _)
+
+#undef BOOST_UNORDERED_INSERT_IMPL
+#endif
+
+    ////////////////////////////////////////////////////////////////////////////
+    // Insert range methods
+
+    // if hash function throws, or inserting > 1 element, basic exception safety
+    // strong otherwise
+    template <class T>
+    template <class I>
+    inline void hash_equivalent_table<T>
+        ::insert_for_range(I i, I j, forward_traversal_tag)
+    {
+        if(i == j) return;
+        std::size_t distance = unordered_detail::distance(i, j);
+        if(distance == 1) {
+            emplace(*i);
+        }
+        else {
+            node_constructor a(*this);
+
+            // Only require basic exception safety here
+            if(this->size_) {
+                this->reserve_for_insert(this->size_ + distance);
+            }
+            else {
+                a.construct(*i++);
+                this->emplace_empty_impl_with_node(a, distance);
+            }
+
+            for (; i != j; ++i) {
+                a.construct(*i);
+                emplace_impl_no_rehash(a);
+            }
+        }
+    }
+
+    // if hash function throws, or inserting > 1 element, basic exception safety
+    // strong otherwise
+    template <class T>
+    template <class I>
+    inline void hash_equivalent_table<T>
+        ::insert_for_range(I i, I j, boost::incrementable_traversal_tag)
+    {
+        node_constructor a(*this);
+        for (; i != j; ++i) {
+            a.construct(*i);
+            emplace_impl(a);
+        }
+    }
+
+    // if hash function throws, or inserting > 1 element, basic exception safety
+    // strong otherwise
+    template <class T>
+    template <class I>
+    void hash_equivalent_table<T>::insert_range(I i, I j)
+    {
+        BOOST_DEDUCED_TYPENAME boost::iterator_traversal<I>::type
+            iterator_traversal_tag;
+        insert_for_range(i, j, iterator_traversal_tag);
+    }
+}}
+
+#endif