summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
Diffstat (limited to '3rdParty/Boost/src/boost/unordered/detail/util.hpp')
-rw-r--r--3rdParty/Boost/src/boost/unordered/detail/util.hpp331
1 files changed, 331 insertions, 0 deletions
diff --git a/3rdParty/Boost/src/boost/unordered/detail/util.hpp b/3rdParty/Boost/src/boost/unordered/detail/util.hpp
new file mode 100644
index 0000000..5540965
--- /dev/null
+++ b/3rdParty/Boost/src/boost/unordered/detail/util.hpp
@@ -0,0 +1,331 @@
+
+// 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_UTIL_HPP_INCLUDED
+#define BOOST_UNORDERED_DETAIL_UTIL_HPP_INCLUDED
+
+#include <cstddef>
+#include <utility>
+#include <algorithm>
+#include <boost/limits.hpp>
+#include <boost/iterator/iterator_categories.hpp>
+#include <boost/preprocessor/seq/size.hpp>
+#include <boost/preprocessor/seq/enum.hpp>
+#include <boost/unordered/detail/fwd.hpp>
+
+namespace boost { namespace unordered_detail {
+
+ ////////////////////////////////////////////////////////////////////////////
+ // convert double to std::size_t
+
+ inline std::size_t double_to_size_t(double f)
+ {
+ return f >= static_cast<double>(
+ (std::numeric_limits<std::size_t>::max)()) ?
+ (std::numeric_limits<std::size_t>::max)() :
+ static_cast<std::size_t>(f);
+ }
+
+ ////////////////////////////////////////////////////////////////////////////
+ // primes
+
+#define BOOST_UNORDERED_PRIMES \
+ (5ul)(11ul)(17ul)(29ul)(37ul)(53ul)(67ul)(79ul) \
+ (97ul)(131ul)(193ul)(257ul)(389ul)(521ul)(769ul) \
+ (1031ul)(1543ul)(2053ul)(3079ul)(6151ul)(12289ul)(24593ul) \
+ (49157ul)(98317ul)(196613ul)(393241ul)(786433ul) \
+ (1572869ul)(3145739ul)(6291469ul)(12582917ul)(25165843ul) \
+ (50331653ul)(100663319ul)(201326611ul)(402653189ul)(805306457ul) \
+ (1610612741ul)(3221225473ul)(4294967291ul)
+
+ template<class T> struct prime_list_template
+ {
+ static std::size_t const value[];
+
+#if !defined(SUNPRO_CC)
+ static std::ptrdiff_t const length;
+#else
+ static std::ptrdiff_t const length
+ = BOOST_PP_SEQ_SIZE(BOOST_UNORDERED_PRIMES);
+#endif
+ };
+
+ template<class T>
+ std::size_t const prime_list_template<T>::value[] = {
+ BOOST_PP_SEQ_ENUM(BOOST_UNORDERED_PRIMES)
+ };
+
+#if !defined(SUNPRO_CC)
+ template<class T>
+ std::ptrdiff_t const prime_list_template<T>::length
+ = BOOST_PP_SEQ_SIZE(BOOST_UNORDERED_PRIMES);
+#endif
+
+#undef BOOST_UNORDERED_PRIMES
+
+ typedef prime_list_template<std::size_t> prime_list;
+
+ // no throw
+ inline std::size_t next_prime(std::size_t num) {
+ std::size_t const* const prime_list_begin = prime_list::value;
+ std::size_t const* const prime_list_end = prime_list_begin +
+ prime_list::length;
+ std::size_t const* bound =
+ std::lower_bound(prime_list_begin, prime_list_end, num);
+ if(bound == prime_list_end)
+ bound--;
+ return *bound;
+ }
+
+ // no throw
+ inline std::size_t prev_prime(std::size_t num) {
+ std::size_t const* const prime_list_begin = prime_list::value;
+ std::size_t const* const prime_list_end = prime_list_begin +
+ prime_list::length;
+ std::size_t const* bound =
+ std::upper_bound(prime_list_begin,prime_list_end, num);
+ if(bound != prime_list_begin)
+ bound--;
+ return *bound;
+ }
+
+ ////////////////////////////////////////////////////////////////////////////
+ // pair_cast - because some libraries don't have the full pair constructors.
+
+ template <class Dst1, class Dst2, class Src1, class Src2>
+ inline std::pair<Dst1, Dst2> pair_cast(std::pair<Src1, Src2> const& x)
+ {
+ return std::pair<Dst1, Dst2>(Dst1(x.first), Dst2(x.second));
+ }
+
+ ////////////////////////////////////////////////////////////////////////////
+ // insert_size/initial_size
+
+#if !defined(BOOST_NO_STD_DISTANCE)
+ using ::std::distance;
+#else
+ template <class ForwardIterator>
+ inline std::size_t distance(ForwardIterator i, ForwardIterator j) {
+ std::size_t x;
+ std::distance(i, j, x);
+ return x;
+ }
+#endif
+
+ template <class I>
+ inline std::size_t insert_size(I i, I j, boost::forward_traversal_tag)
+ {
+ return std::distance(i, j);
+ }
+
+ template <class I>
+ inline std::size_t insert_size(I, I, boost::incrementable_traversal_tag)
+ {
+ return 1;
+ }
+
+ template <class I>
+ inline std::size_t insert_size(I i, I j)
+ {
+ BOOST_DEDUCED_TYPENAME boost::iterator_traversal<I>::type
+ iterator_traversal_tag;
+ return insert_size(i, j, iterator_traversal_tag);
+ }
+
+ template <class I>
+ inline std::size_t initial_size(I i, I j,
+ std::size_t num_buckets = boost::unordered_detail::default_bucket_count)
+ {
+ return (std::max)(static_cast<std::size_t>(insert_size(i, j)) + 1,
+ num_buckets);
+ }
+
+ ////////////////////////////////////////////////////////////////////////////
+ // Node Constructors
+
+#if defined(BOOST_UNORDERED_STD_FORWARD)
+
+ template <class T, class... Args>
+ inline void construct_impl(T*, void* address, Args&&... args)
+ {
+ new(address) T(std::forward<Args>(args)...);
+ }
+
+#if defined(BOOST_UNORDERED_CPP0X_PAIR)
+ template <class First, class Second, class Key, class Arg0, class... Args>
+ inline void construct_impl(std::pair<First, Second>*, void* address,
+ Key&& k, Arg0&& arg0, Args&&... args)
+ )
+ {
+ new(address) std::pair<First, Second>(k,
+ Second(arg0, std::forward<Args>(args)...);
+ }
+#endif
+
+#else
+
+#define BOOST_UNORDERED_CONSTRUCT_IMPL(z, num_params, _) \
+ template < \
+ class T, \
+ BOOST_UNORDERED_TEMPLATE_ARGS(z, num_params) \
+ > \
+ inline void construct_impl( \
+ T*, void* address, \
+ BOOST_UNORDERED_FUNCTION_PARAMS(z, num_params) \
+ ) \
+ { \
+ new(address) T( \
+ BOOST_UNORDERED_CALL_PARAMS(z, num_params)); \
+ } \
+ \
+ template <class First, class Second, class Key, \
+ BOOST_UNORDERED_TEMPLATE_ARGS(z, num_params) \
+ > \
+ inline void construct_impl( \
+ std::pair<First, Second>*, void* address, \
+ Key const& k, BOOST_UNORDERED_FUNCTION_PARAMS(z, num_params)) \
+ { \
+ new(address) std::pair<First, Second>(k, \
+ Second(BOOST_UNORDERED_CALL_PARAMS(z, num_params))); \
+ }
+
+ BOOST_PP_REPEAT_FROM_TO(1, BOOST_UNORDERED_EMPLACE_LIMIT,
+ BOOST_UNORDERED_CONSTRUCT_IMPL, _)
+
+#undef BOOST_UNORDERED_CONSTRUCT_IMPL
+#endif
+
+ // hash_node_constructor
+ //
+ // Used to construct nodes in an exception safe manner.
+
+ template <class Alloc, class Grouped>
+ class hash_node_constructor
+ {
+ typedef hash_buckets<Alloc, Grouped> buckets;
+ typedef BOOST_DEDUCED_TYPENAME buckets::node node;
+ typedef BOOST_DEDUCED_TYPENAME buckets::real_node_ptr real_node_ptr;
+ typedef BOOST_DEDUCED_TYPENAME buckets::value_type value_type;
+
+ buckets& buckets_;
+ real_node_ptr node_;
+ bool node_constructed_;
+ bool value_constructed_;
+
+ public:
+
+ hash_node_constructor(buckets& m) :
+ buckets_(m),
+ node_(),
+ node_constructed_(false),
+ value_constructed_(false)
+ {
+ }
+
+ ~hash_node_constructor();
+ void construct_preamble();
+
+#if defined(BOOST_UNORDERED_STD_FORWARD)
+ template <class... Args>
+ void construct(Args&&... args)
+ {
+ construct_preamble();
+ construct_impl((value_type*) 0, node_->address(),
+ std::forward<Args>(args)...);
+ value_constructed_ = true;
+ }
+#else
+
+#define BOOST_UNORDERED_CONSTRUCT(z, num_params, _) \
+ template < \
+ BOOST_UNORDERED_TEMPLATE_ARGS(z, num_params) \
+ > \
+ void construct( \
+ BOOST_UNORDERED_FUNCTION_PARAMS(z, num_params) \
+ ) \
+ { \
+ construct_preamble(); \
+ construct_impl( \
+ (value_type*) 0, node_->address(), \
+ BOOST_UNORDERED_CALL_PARAMS(z, num_params) \
+ ); \
+ value_constructed_ = true; \
+ }
+
+ BOOST_PP_REPEAT_FROM_TO(1, BOOST_UNORDERED_EMPLACE_LIMIT,
+ BOOST_UNORDERED_CONSTRUCT, _)
+
+#undef BOOST_UNORDERED_CONSTRUCT
+
+#endif
+ template <class K, class M>
+ void construct_pair(K const& k, M*)
+ {
+ construct_preamble();
+ new(node_->address()) value_type(k, M());
+ value_constructed_ = true;
+ }
+
+ value_type& value() const
+ {
+ BOOST_ASSERT(node_);
+ return node_->value();
+ }
+
+ // no throw
+ BOOST_DEDUCED_TYPENAME buckets::node_ptr release()
+ {
+ real_node_ptr p = node_;
+ node_ = real_node_ptr();
+ // node_ptr cast
+ return buckets_.bucket_alloc().address(*p);
+ }
+
+ private:
+ hash_node_constructor(hash_node_constructor const&);
+ hash_node_constructor& operator=(hash_node_constructor const&);
+ };
+
+ // hash_node_constructor
+
+ template <class Alloc, class Grouped>
+ inline hash_node_constructor<Alloc, Grouped>::~hash_node_constructor()
+ {
+ if (node_) {
+ if (value_constructed_) {
+#if BOOST_WORKAROUND(__CODEGEARC__, BOOST_TESTED_AT(0x0613))
+ struct dummy { hash_node<Alloc, Grouped> x; };
+#endif
+ boost::unordered_detail::destroy(&node_->value());
+ }
+
+ if (node_constructed_)
+ buckets_.node_alloc().destroy(node_);
+
+ buckets_.node_alloc().deallocate(node_, 1);
+ }
+ }
+
+ template <class Alloc, class Grouped>
+ inline void hash_node_constructor<Alloc, Grouped>::construct_preamble()
+ {
+ if(!node_) {
+ node_constructed_ = false;
+ value_constructed_ = false;
+
+ node_ = buckets_.node_alloc().allocate(1);
+ buckets_.node_alloc().construct(node_, node());
+ node_constructed_ = true;
+ }
+ else {
+ BOOST_ASSERT(node_constructed_ && value_constructed_);
+ boost::unordered_detail::destroy(&node_->value());
+ value_constructed_ = false;
+ }
+ }
+}}
+
+#endif