comparison DEPENDENCIES/generic/include/boost/unordered/detail/buckets.hpp @ 101:c530137014c0

Update Boost headers (1.58.0)

 // file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
 
 #ifndef BOOST_UNORDERED_DETAIL_MANAGER_HPP_INCLUDED
 #define BOOST_UNORDERED_DETAIL_MANAGER_HPP_INCLUDED
 
-#if defined(_MSC_VER) && (_MSC_VER >= 1020)
-# pragma once
+#include <boost/config.hpp>
+#if defined(BOOST_HAS_PRAGMA_ONCE)
+#pragma once
 #endif
 
 #include <boost/unordered/detail/util.hpp>
 #include <boost/unordered/detail/allocate.hpp>
 #include <boost/type_traits/aligned_storage.hpp>

     // Iterators
     //
     // all no throw
 
     template <typename Node> struct iterator;
-    template <typename Node, typename ConstNodePointer> struct c_iterator;
+    template <typename Node> struct c_iterator;
     template <typename Node, typename Policy> struct l_iterator;
-    template <typename Node, typename ConstNodePointer, typename Policy>
+    template <typename Node, typename Policy>
         struct cl_iterator;
 
     // Local Iterators
     //
     // all no throw

     struct l_iterator
         : public boost::iterator<
             std::forward_iterator_tag,
             typename Node::value_type,
             std::ptrdiff_t,
-            typename Node::node_pointer,
+            typename Node::value_type*,
             typename Node::value_type&>
     {
 #if !defined(BOOST_NO_MEMBER_TEMPLATE_FRIENDS)
-        template <typename Node2, typename ConstNodePointer, typename Policy2>
+        template <typename Node2, typename Policy2>
         friend struct boost::unordered::iterator_detail::cl_iterator;
     private:
 #endif
         typedef typename Node::node_pointer node_pointer;
-        typedef boost::unordered::iterator_detail::iterator<Node> iterator;
+        typedef boost::unordered::iterator_detail::iterator<Node> n_iterator;
         node_pointer ptr_;
         std::size_t bucket_;
         std::size_t bucket_count_;
 
     public:
 
         typedef typename Node::value_type value_type;
 
         l_iterator() BOOST_NOEXCEPT : ptr_() {}
 
-        l_iterator(iterator x, std::size_t b, std::size_t c) BOOST_NOEXCEPT
+        l_iterator(n_iterator x, std::size_t b, std::size_t c) BOOST_NOEXCEPT
             : ptr_(x.node_), bucket_(b), bucket_count_(c) {}
 
         value_type& operator*() const {
             return ptr_->value();
         }

         bool operator!=(l_iterator x) const BOOST_NOEXCEPT {
             return ptr_ != x.ptr_;
         }
     };
 
-    template <typename Node, typename ConstNodePointer, typename Policy>
+    template <typename Node, typename Policy>
     struct cl_iterator
         : public boost::iterator<
             std::forward_iterator_tag,
             typename Node::value_type,
             std::ptrdiff_t,
-            ConstNodePointer,
+            typename Node::value_type const*,
             typename Node::value_type const&>
     {
         friend struct boost::unordered::iterator_detail::l_iterator
             <Node, Policy>;
     private:
 
         typedef typename Node::node_pointer node_pointer;
-        typedef boost::unordered::iterator_detail::iterator<Node> iterator;
+        typedef boost::unordered::iterator_detail::iterator<Node> n_iterator;
         node_pointer ptr_;
         std::size_t bucket_;
         std::size_t bucket_count_;
 
     public:
 
         typedef typename Node::value_type value_type;
 
         cl_iterator() BOOST_NOEXCEPT : ptr_() {}
 
-        cl_iterator(iterator x, std::size_t b, std::size_t c) BOOST_NOEXCEPT :
+        cl_iterator(n_iterator x, std::size_t b, std::size_t c) BOOST_NOEXCEPT :
             ptr_(x.node_), bucket_(b), bucket_count_(c) {}
 
         cl_iterator(boost::unordered::iterator_detail::l_iterator<
                 Node, Policy> const& x) BOOST_NOEXCEPT :
             ptr_(x.ptr_), bucket_(x.bucket_), bucket_count_(x.bucket_count_)

     struct iterator
         : public boost::iterator<
             std::forward_iterator_tag,
             typename Node::value_type,
             std::ptrdiff_t,
-            typename Node::node_pointer,
+            typename Node::value_type*,
             typename Node::value_type&>
     {
 #if !defined(BOOST_NO_MEMBER_TEMPLATE_FRIENDS)
-        template <typename, typename>
+        template <typename>
         friend struct boost::unordered::iterator_detail::c_iterator;
         template <typename, typename>
         friend struct boost::unordered::iterator_detail::l_iterator;
-        template <typename, typename, typename>
+        template <typename, typename>
         friend struct boost::unordered::iterator_detail::cl_iterator;
         template <typename>
         friend struct boost::unordered::detail::table;
         template <typename>
         friend struct boost::unordered::detail::table_impl;

         value_type& operator*() const {
             return node_->value();
         }
 
         value_type* operator->() const {
-            return &node_->value();
+            return node_->value_ptr();
         }
 
         iterator& operator++() {
             node_ = static_cast<node_pointer>(node_->next_);
             return *this;

         bool operator!=(iterator const& x) const BOOST_NOEXCEPT {
             return node_ != x.node_;
         }
     };
 
-    template <typename Node, typename ConstNodePointer>
+    template <typename Node>
     struct c_iterator
         : public boost::iterator<
             std::forward_iterator_tag,
             typename Node::value_type,
             std::ptrdiff_t,
-            ConstNodePointer,
+            typename Node::value_type const*,
             typename Node::value_type const&>
     {
         friend struct boost::unordered::iterator_detail::iterator<Node>;
 
 #if !defined(BOOST_NO_MEMBER_TEMPLATE_FRIENDS)

         friend struct boost::unordered::detail::grouped_table_impl;
 
     private:
 #endif
         typedef typename Node::node_pointer node_pointer;
-        typedef boost::unordered::iterator_detail::iterator<Node> iterator;
+        typedef boost::unordered::iterator_detail::iterator<Node> n_iterator;
         node_pointer node_;
 
     public:
 
         typedef typename Node::value_type value_type;

         c_iterator() BOOST_NOEXCEPT : node_() {}
 
         explicit c_iterator(typename Node::link_pointer x) BOOST_NOEXCEPT :
             node_(static_cast<node_pointer>(x)) {}
 
-        c_iterator(iterator const& x) BOOST_NOEXCEPT : node_(x.node_) {}
+        c_iterator(n_iterator const& x) BOOST_NOEXCEPT : node_(x.node_) {}
 
         value_type const& operator*() const {
             return node_->value();
         }
 
         value_type const* operator->() const {
-            return &node_->value();
+            return node_->value_ptr();
         }
 
         c_iterator& operator++() {
             node_ = static_cast<node_pointer>(node_->next_);
             return *this;

                 boost::unordered::detail::func::destroy_value_impl(alloc_,
                     node_->value_ptr());
             }
 
             if (node_constructed_) {
-                node_allocator_traits::destroy(alloc_,
+                boost::unordered::detail::func::destroy(
                     boost::addressof(*node_));
             }
 
             node_allocator_traits::deallocate(alloc_, node_, 1);
         }

             node_constructed_ = false;
             value_constructed_ = false;
 
             node_ = node_allocator_traits::allocate(alloc_, 1);
 
-            node_allocator_traits::construct(alloc_,
-                boost::addressof(*node_), node());
+            new ((void*) boost::addressof(*node_)) node();
             node_->init(node_);
             node_constructed_ = true;
         }
         else {
             BOOST_ASSERT(node_constructed_);

             node_pointer p = nodes_;
             nodes_ = static_cast<node_pointer>(p->next_);
 
             boost::unordered::detail::func::destroy_value_impl(this->alloc_,
                 p->value_ptr());
-            node_allocator_traits::destroy(this->alloc_, boost::addressof(*p));
+            boost::unordered::detail::func::destroy(boost::addressof(*p));
             node_allocator_traits::deallocate(this->alloc_, p, 1);
         }
     }
 
     ///////////////////////////////////////////////////////////////////

     template <>
     struct pick_policy_impl<64, 2> {
         typedef mix64_policy<std::size_t> type;
     };
 
+    template <typename T>
     struct pick_policy :
         pick_policy_impl<
             std::numeric_limits<std::size_t>::digits,
             std::numeric_limits<std::size_t>::radix> {};
+
+    // While the mix policy is generally faster, the prime policy is a lot
+    // faster when a large number consecutive integers are used, because
+    // there are no collisions. Since that is probably quite common, use
+    // prime policy for integeral types. But not the smaller ones, as they
+    // don't have enough unique values for this to be an issue.
+
+    template <>
+    struct pick_policy<int> {
+        typedef prime_policy<std::size_t> type;
+    };
+
+    template <>
+    struct pick_policy<unsigned int> {
+        typedef prime_policy<std::size_t> type;
+    };
+
+    template <>
+    struct pick_policy<long> {
+        typedef prime_policy<std::size_t> type;
+    };
+
+    template <>
+    struct pick_policy<unsigned long> {
+        typedef prime_policy<std::size_t> type;
+    };
+
+    // TODO: Maybe not if std::size_t is smaller than long long.
+#if !defined(BOOST_NO_LONG_LONG)
+    template <>
+    struct pick_policy<long long> {
+        typedef prime_policy<std::size_t> type;
+    };
+
+    template <>
+    struct pick_policy<unsigned long long> {
+        typedef prime_policy<std::size_t> type;
+    };
+#endif
 
     ////////////////////////////////////////////////////////////////////////////
     // Functions
 
     // Assigning and swapping the equality and hash function objects