Swift
summaryrefslogtreecommitdiffstats
path: root/3rdParty/Boost/src/boost/unordered/detail/table.hpp
diff options
context:
space:
mode:
authorTobias Markmann <tm@ayena.de>2014-10-19 20:22:58 (GMT)
committerTobias Markmann <tm@ayena.de>2014-10-20 13:49:33 (GMT)
commit6b22dfcf59474dd016a0355a3102a1dd3692d92c (patch)
tree2b1fd33be433a91e81fee84fdc2bf1b52575d934 /3rdParty/Boost/src/boost/unordered/detail/table.hpp
parent38b0cb785fea8eae5e48fae56440695fdfd10ee1 (diff)
downloadswift-contrib-6b22dfcf59474dd016a0355a3102a1dd3692d92c.zip
swift-contrib-6b22dfcf59474dd016a0355a3102a1dd3692d92c.tar.bz2
Update Boost in 3rdParty to version 1.56.0.
This updates Boost in our 3rdParty directory to version 1.56.0. Updated our update.sh script to stop on error. Changed error reporting in SwiftTools/CrashReporter.cpp to SWIFT_LOG due to missing include of <iostream> with newer Boost. Change-Id: I4b35c77de951333979a524097f35f5f83d325edc
Diffstat (limited to '3rdParty/Boost/src/boost/unordered/detail/table.hpp')
-rw-r--r--3rdParty/Boost/src/boost/unordered/detail/table.hpp224
1 files changed, 92 insertions, 132 deletions
diff --git a/3rdParty/Boost/src/boost/unordered/detail/table.hpp b/3rdParty/Boost/src/boost/unordered/detail/table.hpp
index af376fe..7b4cc0e 100644
--- a/3rdParty/Boost/src/boost/unordered/detail/table.hpp
+++ b/3rdParty/Boost/src/boost/unordered/detail/table.hpp
@@ -7,6 +7,11 @@
#ifndef BOOST_UNORDERED_DETAIL_ALL_HPP_INCLUDED
#define BOOST_UNORDERED_DETAIL_ALL_HPP_INCLUDED
+#include <boost/config.hpp>
+#if defined(BOOST_HAS_PRAGMA_ONCE)
+#pragma once
+#endif
+
#include <boost/unordered/detail/buckets.hpp>
#include <boost/unordered/detail/util.hpp>
#include <boost/type_traits/aligned_storage.hpp>
@@ -18,6 +23,18 @@
#pragma warning(disable:4127) // conditional expression is constant
#endif
+#if defined(BOOST_UNORDERED_DEPRECATED_EQUALITY)
+
+#if defined(__EDG__)
+#elif defined(_MSC_VER) || defined(__BORLANDC__) || defined(__DMC__)
+#pragma message("Warning: BOOST_UNORDERED_DEPRECATED_EQUALITY is no longer supported.")
+#elif defined(__GNUC__) || defined(__HP_aCC) || \
+ defined(__SUNPRO_CC) || defined(__IBMCPP__)
+#warning "BOOST_UNORDERED_DEPRECATED_EQUALITY is no longer supported."
+#endif
+
+#endif
+
namespace boost { namespace unordered { namespace detail {
////////////////////////////////////////////////////////////////////////////
@@ -125,7 +142,6 @@ namespace boost { namespace unordered { namespace detail {
template <typename Types>
struct table :
- Types::policy,
boost::unordered::detail::functions<
typename Types::hasher,
typename Types::key_equal>
@@ -148,6 +164,7 @@ namespace boost { namespace unordered { namespace detail {
typedef boost::unordered::detail::functions<
typename Types::hasher,
typename Types::key_equal> functions;
+ typedef typename functions::set_hash_functions set_hash_functions;
typedef typename Types::allocator allocator;
typedef typename boost::unordered::detail::
@@ -164,20 +181,17 @@ namespace boost { namespace unordered { namespace detail {
const_node_pointer;
typedef typename bucket_allocator_traits::pointer
bucket_pointer;
- typedef typename bucket::previous_pointer
- previous_pointer;
typedef boost::unordered::detail::node_constructor<node_allocator>
node_constructor;
typedef boost::unordered::iterator_detail::
- iterator<node_pointer, value_type> iterator;
+ iterator<node> iterator;
typedef boost::unordered::iterator_detail::
- c_iterator<const_node_pointer, node_pointer, value_type> c_iterator;
+ c_iterator<node, const_node_pointer> c_iterator;
typedef boost::unordered::iterator_detail::
- l_iterator<node_pointer, value_type, policy> l_iterator;
+ l_iterator<node, policy> l_iterator;
typedef boost::unordered::iterator_detail::
- cl_iterator<const_node_pointer, node_pointer, value_type, policy>
- cl_iterator;
+ cl_iterator<node, const_node_pointer, policy> cl_iterator;
////////////////////////////////////////////////////////////////////////
// Members
@@ -226,28 +240,31 @@ namespace boost { namespace unordered { namespace detail {
return buckets_ + static_cast<std::ptrdiff_t>(bucket_index);
}
- previous_pointer get_previous_start() const
+ link_pointer get_previous_start() const
{
return get_bucket(bucket_count_)->first_from_start();
}
- previous_pointer get_previous_start(std::size_t bucket_index) const
+ link_pointer get_previous_start(std::size_t bucket_index) const
{
return get_bucket(bucket_index)->next_;
}
iterator begin() const
{
- return size_ ? iterator(static_cast<node_pointer>(
- get_previous_start()->next_)) : iterator();
+ return size_ ? iterator(get_previous_start()->next_) : iterator();
}
iterator begin(std::size_t bucket_index) const
{
if (!size_) return iterator();
- previous_pointer prev = get_previous_start(bucket_index);
- return prev ? iterator(static_cast<node_pointer>(prev->next_)) :
- iterator();
+ link_pointer prev = get_previous_start(bucket_index);
+ return prev ? iterator(prev->next_) : iterator();
+ }
+
+ std::size_t hash_to_bucket(std::size_t hash_value) const
+ {
+ return policy::to_bucket(bucket_count_, hash_value);
}
float load_factor() const
@@ -263,8 +280,7 @@ namespace boost { namespace unordered { namespace detail {
if (!it.node_) return 0;
std::size_t count = 0;
- while(it.node_ && policy::to_bucket(
- bucket_count_, it.node_->hash_) == index)
+ while(it.node_ && hash_to_bucket(it.node_->hash_) == index)
{
++count;
++it;
@@ -353,7 +369,7 @@ namespace boost { namespace unordered { namespace detail {
{}
table(table& x, boost::unordered::detail::move_tag m) :
- functions(x),
+ functions(x, m),
allocators_(x.allocators_, m),
bucket_count_(x.bucket_count_),
size_(x.size_),
@@ -367,8 +383,8 @@ namespace boost { namespace unordered { namespace detail {
}
table(table& x, node_allocator const& a,
- boost::unordered::detail::move_tag) :
- functions(x),
+ boost::unordered::detail::move_tag m) :
+ functions(x, m),
allocators_(a, a),
bucket_count_(x.bucket_count_),
size_(0),
@@ -384,8 +400,8 @@ namespace boost { namespace unordered { namespace detail {
{
if (x.size_) {
create_buckets(bucket_count_);
- copy_nodes<node_allocator> copy(node_alloc());
- table_impl::fill_buckets(x.begin(), *this, copy);
+ copy_nodes<node_allocator> node_creator(node_alloc());
+ table_impl::fill_buckets(x.begin(), *this, node_creator);
}
}
@@ -398,9 +414,9 @@ namespace boost { namespace unordered { namespace detail {
// TODO: Could pick new bucket size?
create_buckets(bucket_count_);
- move_nodes<node_allocator> move(node_alloc());
+ move_nodes<node_allocator> node_creator(node_alloc());
node_holder<node_allocator> nodes(x);
- table_impl::fill_buckets(nodes.begin(), *this, move);
+ table_impl::fill_buckets(nodes.begin(), *this, node_creator);
}
}
@@ -445,6 +461,8 @@ namespace boost { namespace unordered { namespace detail {
void swap_allocators(table& other, false_type)
{
+ boost::unordered::detail::func::ignore_unused_variable_warning(other);
+
// According to 23.2.1.8, if propagate_on_container_swap is
// false the behaviour is undefined unless the allocators
// are equal.
@@ -459,10 +477,8 @@ namespace boost { namespace unordered { namespace detail {
// Only swaps the allocators if propagate_on_container_swap
void swap(table& x)
{
- boost::unordered::detail::set_hash_functions<hasher, key_equal>
- op1(*this, x);
- boost::unordered::detail::set_hash_functions<hasher, key_equal>
- op2(x, *this);
+ set_hash_functions op1(*this, x);
+ set_hash_functions op2(x, *this);
// I think swap can throw if Propagate::value,
// since the allocators' swap can throw. Not sure though.
@@ -500,26 +516,28 @@ namespace boost { namespace unordered { namespace detail {
delete_buckets();
}
- void delete_node(c_iterator n)
+ void delete_node(link_pointer prev)
{
- boost::unordered::detail::destroy_value_impl(node_alloc(),
- n.node_->value_ptr());
- node_allocator_traits::destroy(node_alloc(),
- boost::addressof(*n.node_));
- node_allocator_traits::deallocate(node_alloc(), n.node_, 1);
+ node_pointer n = static_cast<node_pointer>(prev->next_);
+ prev->next_ = n->next_;
+
+ boost::unordered::detail::func::destroy_value_impl(node_alloc(),
+ n->value_ptr());
+ boost::unordered::detail::func::destroy(boost::addressof(*n));
+ node_allocator_traits::deallocate(node_alloc(), n, 1);
--size_;
}
- std::size_t delete_nodes(c_iterator begin, c_iterator end)
+ std::size_t delete_nodes(link_pointer prev, link_pointer end)
{
+ BOOST_ASSERT(prev->next_ != end);
+
std::size_t count = 0;
- while(begin != end) {
- c_iterator n = begin;
- ++begin;
- delete_node(n);
+ do {
+ delete_node(prev);
++count;
- }
+ } while (prev->next_ != end);
return count;
}
@@ -527,12 +545,12 @@ namespace boost { namespace unordered { namespace detail {
void delete_buckets()
{
if(buckets_) {
- delete_nodes(begin(), iterator());
+ if (size_) delete_nodes(get_previous_start(), link_pointer());
if (bucket::extra_node) {
node_pointer n = static_cast<node_pointer>(
get_bucket(bucket_count_)->next_);
- node_allocator_traits::destroy(node_alloc(),
+ boost::unordered::detail::func::destroy(
boost::addressof(*n));
node_allocator_traits::deallocate(node_alloc(), n, 1);
}
@@ -547,10 +565,9 @@ namespace boost { namespace unordered { namespace detail {
void clear()
{
- if(!size_) return;
+ if (!size_) return;
- delete_nodes(begin(), iterator());
- get_previous_start()->next_ = link_pointer();
+ delete_nodes(get_previous_start(), link_pointer());
clear_buckets();
BOOST_ASSERT(!size_);
@@ -570,7 +587,7 @@ namespace boost { namespace unordered { namespace detail {
bucket_pointer end = get_bucket(bucket_count_ + 1);
for(bucket_pointer it = buckets_; it != end; ++it)
{
- bucket_allocator_traits::destroy(bucket_alloc(),
+ boost::unordered::detail::func::destroy(
boost::addressof(*it));
}
@@ -579,86 +596,33 @@ namespace boost { namespace unordered { namespace detail {
}
////////////////////////////////////////////////////////////////////////
- // Fix buckets after erase
+ // Fix buckets after delete
+ //
- // This is called after erasing a node or group of nodes to fix up
- // the bucket pointers.
- void fix_buckets(bucket_pointer this_bucket,
- previous_pointer prev, node_pointer next)
+ std::size_t fix_bucket(std::size_t bucket_index, link_pointer prev)
{
- if (!next)
- {
- if (this_bucket->next_ == prev)
- this_bucket->next_ = node_pointer();
- }
- else
+ link_pointer end = prev->next_;
+ std::size_t bucket_index2 = bucket_index;
+
+ if (end)
{
- bucket_pointer next_bucket = get_bucket(
- policy::to_bucket(bucket_count_, next->hash_));
-
- if (next_bucket != this_bucket)
- {
- next_bucket->next_ = prev;
- if (this_bucket->next_ == prev)
- this_bucket->next_ = node_pointer();
- }
- }
- }
+ bucket_index2 = hash_to_bucket(
+ static_cast<node_pointer>(end)->hash_);
- // This is called after erasing a range of nodes to fix any bucket
- // pointers into that range.
- void fix_buckets_range(std::size_t bucket_index,
- previous_pointer prev, node_pointer begin, node_pointer end)
- {
- node_pointer n = begin;
+ // If begin and end are in the same bucket, then
+ // there's nothing to do.
+ if (bucket_index == bucket_index2) return bucket_index2;
- // If we're not at the start of the current bucket, then
- // go to the start of the next bucket.
- if (get_bucket(bucket_index)->next_ != prev)
- {
- for(;;) {
- n = static_cast<node_pointer>(n->next_);
- if (n == end) {
- if (n) {
- std::size_t new_bucket_index =
- policy::to_bucket(bucket_count_, n->hash_);
- if (bucket_index != new_bucket_index) {
- get_bucket(new_bucket_index)->next_ = prev;
- }
- }
- return;
- }
-
- std::size_t new_bucket_index =
- policy::to_bucket(bucket_count_, n->hash_);
- if (bucket_index != new_bucket_index) {
- bucket_index = new_bucket_index;
- break;
- }
- }
+ // Update the bucket containing end.
+ get_bucket(bucket_index2)->next_ = prev;
}
- // Iterate through the remaining nodes, clearing out the bucket
- // pointers.
- get_bucket(bucket_index)->next_ = previous_pointer();
- for(;;) {
- n = static_cast<node_pointer>(n->next_);
- if (n == end) break;
-
- std::size_t new_bucket_index =
- policy::to_bucket(bucket_count_, n->hash_);
- if (bucket_index != new_bucket_index) {
- bucket_index = new_bucket_index;
- get_bucket(bucket_index)->next_ = previous_pointer();
- }
- };
+ // Check if this bucket is now empty.
+ bucket_pointer this_bucket = get_bucket(bucket_index);
+ if (this_bucket->next_ == prev)
+ this_bucket->next_ = link_pointer();
- // Finally fix the bucket containing the trailing node.
- if (n) {
- get_bucket(
- policy::to_bucket(bucket_count_, n->hash_))->next_
- = prev;
- }
+ return bucket_index2;
}
////////////////////////////////////////////////////////////////////////
@@ -678,8 +642,7 @@ namespace boost { namespace unordered { namespace detail {
void assign(table const& x, false_type)
{
// Strong exception safety.
- boost::unordered::detail::set_hash_functions<hasher, key_equal>
- new_func_this(*this, x);
+ set_hash_functions new_func_this(*this, x);
new_func_this.commit();
mlf_ = x.mlf_;
recalculate_max_load();
@@ -696,8 +659,8 @@ namespace boost { namespace unordered { namespace detail {
// assign_nodes takes ownership of the container's elements,
// assigning to them if possible, and deleting any that are
// left over.
- assign_nodes<table> assign(*this);
- table_impl::fill_buckets(x.begin(), *this, assign);
+ assign_nodes<table> node_creator(*this);
+ table_impl::fill_buckets(x.begin(), *this, node_creator);
}
void assign(table const& x, true_type)
@@ -707,8 +670,7 @@ namespace boost { namespace unordered { namespace detail {
assign(x, false_type());
}
else {
- boost::unordered::detail::set_hash_functions<hasher, key_equal>
- new_func_this(*this, x);
+ set_hash_functions new_func_this(*this, x);
// Delete everything with current allocators before assigning
// the new ones.
@@ -724,8 +686,8 @@ namespace boost { namespace unordered { namespace detail {
// Finally copy the elements.
if (x.size_) {
create_buckets(bucket_count_);
- copy_nodes<node_allocator> copy(node_alloc());
- table_impl::fill_buckets(x.begin(), *this, copy);
+ copy_nodes<node_allocator> node_creator(node_alloc());
+ table_impl::fill_buckets(x.begin(), *this, node_creator);
}
}
}
@@ -755,8 +717,7 @@ namespace boost { namespace unordered { namespace detail {
move_assign_no_alloc(x);
}
else {
- boost::unordered::detail::set_hash_functions<hasher, key_equal>
- new_func_this(*this, x);
+ set_hash_functions new_func_this(*this, x);
new_func_this.commit();
mlf_ = x.mlf_;
recalculate_max_load();
@@ -773,16 +734,15 @@ namespace boost { namespace unordered { namespace detail {
// move_assign_nodes takes ownership of the container's
// elements, assigning to them if possible, and deleting
// any that are left over.
- move_assign_nodes<table> assign(*this);
+ move_assign_nodes<table> node_creator(*this);
node_holder<node_allocator> nodes(x);
- table_impl::fill_buckets(nodes.begin(), *this, assign);
+ table_impl::fill_buckets(nodes.begin(), *this, node_creator);
}
}
void move_assign_no_alloc(table& x)
{
- boost::unordered::detail::set_hash_functions<hasher, key_equal>
- new_func_this(*this, x);
+ set_hash_functions new_func_this(*this, x);
// No throw from here.
mlf_ = x.mlf_;
max_load_ = x.max_load_;