Boost logo

Boost-Commit :

Subject: [Boost-commit] svn:boost r49927 - in trunk: boost/unordered/detail libs/unordered/doc
From: daniel_james_at_[hidden]
Date: 2008-11-24 18:15:56


Author: danieljames
Date: 2008-11-24 18:15:55 EST (Mon, 24 Nov 2008)
New Revision: 49927
URL: http://svn.boost.org/trac/boost/changeset/49927

Log:
Use aligned storage for the value.
Text files modified:
   trunk/boost/unordered/detail/hash_table.hpp | 2
   trunk/boost/unordered/detail/hash_table_impl.hpp | 180 +++++++++------------------------------
   trunk/libs/unordered/doc/changes.qbk | 7 +
   3 files changed, 50 insertions(+), 139 deletions(-)

Modified: trunk/boost/unordered/detail/hash_table.hpp
==============================================================================
--- trunk/boost/unordered/detail/hash_table.hpp (original)
+++ trunk/boost/unordered/detail/hash_table.hpp 2008-11-24 18:15:55 EST (Mon, 24 Nov 2008)
@@ -26,6 +26,8 @@
 #include <boost/static_assert.hpp>
 #include <boost/unordered/detail/allocator_helpers.hpp>
 #include <boost/type_traits/is_same.hpp>
+#include <boost/type_traits/aligned_storage.hpp>
+#include <boost/type_traits/alignment_of.hpp>
 #include <boost/mpl/if.hpp>
 #include <boost/mpl/and.hpp>
 #include <boost/detail/workaround.hpp>

Modified: trunk/boost/unordered/detail/hash_table_impl.hpp
==============================================================================
--- trunk/boost/unordered/detail/hash_table_impl.hpp (original)
+++ trunk/boost/unordered/detail/hash_table_impl.hpp 2008-11-24 18:15:55 EST (Mon, 24 Nov 2008)
@@ -34,7 +34,6 @@
         public:
             typedef BOOST_UNORDERED_TABLE_DATA data;
 
- struct node_base;
             struct node;
             struct bucket;
             typedef std::size_t size_type;
@@ -46,9 +45,6 @@
                 boost::unordered_detail::rebind_wrap<Alloc, node>::type
                 node_allocator;
             typedef BOOST_DEDUCED_TYPENAME
- boost::unordered_detail::rebind_wrap<Alloc, node_base>::type
- node_base_allocator;
- typedef BOOST_DEDUCED_TYPENAME
                 boost::unordered_detail::rebind_wrap<Alloc, bucket>::type
                 bucket_allocator;
 
@@ -88,39 +84,36 @@
                 }
             };
 
+ // Value Base
+
+ struct value_base {
+ typename boost::aligned_storage<
+ sizeof(value_type),
+ boost::alignment_of<value_type>::value>::type data_;
+
+ void* address() { return this; }
+ };
+
             // Hash Node
             //
             // all no throw
 
- struct node_base : bucket
- {
+ struct node : value_base, bucket {
 #if BOOST_UNORDERED_EQUIVALENT_KEYS
             public:
- node_base() : group_prev_()
+ node() : group_prev_()
                 {
                     BOOST_UNORDERED_MSVC_RESET_PTR(group_prev_);
                 }
 
                 link_ptr group_prev_;
 #endif
- };
-
- struct node : node_base
- {
- public:
-#if defined(BOOST_HAS_RVALUE_REFS) && defined(BOOST_HAS_VARIADIC_TMPL)
- template <typename... Args>
- node(Args&&... args)
- : node_base(), value_(std::forward<Args>(args)...) {}
-#else
- node(value_type const& v) : node_base(), value_(v) {}
-#endif
 
- value_type value_;
+ value_type& value() {
+ return *static_cast<value_type*>(this->address());
+ }
             };
 
-#if defined(BOOST_HAS_RVALUE_REFS) && defined(BOOST_HAS_VARIADIC_TMPL)
-
             // allocators
             //
             // Stores all the allocators that we're going to need.
@@ -136,7 +129,9 @@
 
                 void destroy(link_ptr ptr)
                 {
- node_ptr n(node_alloc_.address(*static_cast<node*>(&*ptr)));
+ node* raw_ptr = static_cast<node*>(&*ptr);
+ raw_ptr->value().~value_type();
+ node_ptr n(node_alloc_.address(*raw_ptr));
                     node_alloc_.destroy(n);
                     node_alloc_.deallocate(n, 1);
                 }
@@ -163,146 +158,62 @@
 
                 node_ptr node_;
                 bool node_constructed_;
+ bool value_constructed_;
 
             public:
 
                 node_constructor(allocators& a)
                     : allocators_(a),
- node_(), node_constructed_(false)
+ node_(), node_constructed_(false), value_constructed_(false)
                 {
                 }
 
                 ~node_constructor()
                 {
                     if (node_) {
+ if (value_constructed_) {
+ node_->value().~value_type();
+ }
+
                         if (node_constructed_)
                             allocators_.node_alloc_.destroy(node_);
                         allocators_.node_alloc_.deallocate(node_, 1);
                     }
                 }
 
+#if defined(BOOST_HAS_RVALUE_REFS) && defined(BOOST_HAS_VARIADIC_TMPL)
                 template <typename... Args>
                 void construct(Args&&... args)
                 {
                     BOOST_ASSERT(!node_);
                     node_constructed_ = false;
+ value_constructed_ = false;
 
                     node_ = allocators_.node_alloc_.allocate(1);
- allocators_.node_alloc_.construct(node_, std::forward<Args>(args)...);
- node_constructed_ = true;
- }
 
- node_ptr get() const
- {
- BOOST_ASSERT(node_);
- return node_;
- }
+ allocators_.node_alloc_.construct(node_, node());
+ node_constructed_ = true;
 
- // no throw
- link_ptr release()
- {
- node_ptr p = node_;
- unordered_detail::reset(node_);
- return link_ptr(allocators_.bucket_alloc_.address(*p));
+ new(node_->address()) value_type(std::forward<Args>(args)...);
+ value_constructed_ = true;
                 }
-
- private:
- node_constructor(node_constructor const&);
- node_constructor& operator=(node_constructor const&);
- };
 #else
-
- // allocators
- //
- // Stores all the allocators that we're going to need.
-
- struct allocators
- {
- node_allocator node_alloc_;
- bucket_allocator bucket_alloc_;
- value_allocator value_alloc_;
- node_base_allocator node_base_alloc_;
-
- allocators(value_allocator const& a)
- : node_alloc_(a), bucket_alloc_(a),
- value_alloc_(a), node_base_alloc_(a)
- {}
-
- void destroy(link_ptr ptr)
- {
- node_ptr n(node_alloc_.address(*static_cast<node*>(&*ptr)));
- value_alloc_.destroy(value_alloc_.address(n->value_));
- node_base_alloc_.destroy(node_base_alloc_.address(*n));
- node_alloc_.deallocate(n, 1);
- }
-
- void swap(allocators& x)
- {
- boost::swap(node_alloc_, x.node_alloc_);
- boost::swap(bucket_alloc_, x.bucket_alloc_);
- boost::swap(value_alloc_, x.value_alloc_);
- boost::swap(node_base_alloc_, x.node_base_alloc_);
- }
-
- bool operator==(allocators const& x)
- {
- return value_alloc_ == x.value_alloc_;
- }
- };
-
- // node_constructor
- //
- // Used to construct nodes in an exception safe manner.
-
- class node_constructor
- {
- allocators& allocators_;
-
- node_ptr node_;
- bool value_constructed_;
- bool node_base_constructed_;
-
- public:
-
- node_constructor(allocators& a)
- : allocators_(a),
- node_(), value_constructed_(false), node_base_constructed_(false)
- {
- BOOST_UNORDERED_MSVC_RESET_PTR(node_);
- }
-
- ~node_constructor()
- {
- if (node_) {
- if (value_constructed_)
- allocators_.value_alloc_.destroy(
- allocators_.value_alloc_.address(node_->value_));
- if (node_base_constructed_)
- allocators_.node_base_alloc_.destroy(
- allocators_.node_base_alloc_.address(*node_));
-
- allocators_.node_alloc_.deallocate(node_, 1);
- }
- }
-
                 template <typename V>
                 void construct(V const& v)
                 {
                     BOOST_ASSERT(!node_);
+ node_constructed_ = false;
                     value_constructed_ = false;
- node_base_constructed_ = false;
 
                     node_ = allocators_.node_alloc_.allocate(1);
 
- allocators_.node_base_alloc_.construct(
- allocators_.node_base_alloc_.address(*node_),
- node_base());
- node_base_constructed_ = true;
+ allocators_.node_alloc_.construct(node_, node());
+ node_constructed_ = true;
 
- allocators_.value_alloc_.construct(
- allocators_.value_alloc_.address(node_->value_), v);
+ new(node_->address()) value_type(v);
                     value_constructed_ = true;
                 }
+#endif
 
                 node_ptr get() const
                 {
@@ -322,7 +233,6 @@
                 node_constructor(node_constructor const&);
                 node_constructor& operator=(node_constructor const&);
             };
-#endif
 
             // Methods for navigating groups of elements with equal keys.
 
@@ -351,8 +261,7 @@
 
             // pre: Must be pointing to a node
             static inline reference get_value(link_ptr p) {
- BOOST_ASSERT(p);
- return static_cast<node*>(&*p)->value_;
+ return get_node(p).value();
             }
 
             class iterator_base
@@ -1357,17 +1266,10 @@
             // accessors
 
             // no throw
-#if defined(BOOST_HAS_RVALUE_REFS) && defined(BOOST_HAS_VARIADIC_TMPL)
             node_allocator get_allocator() const
             {
                 return data_.allocators_.node_alloc_;
             }
-#else
- value_allocator get_allocator() const
- {
- return data_.allocators_.value_alloc_;
- }
-#endif
 
             // no throw
             hasher const& hash_function() const
@@ -1728,7 +1630,7 @@
 
             iterator_base insert_impl(node_constructor& a)
             {
- key_type const& k = extract_key(a.get()->value_);
+ key_type const& k = extract_key(a.get()->value());
                 size_type hash_value = hash_function()(k);
                 bucket_ptr bucket = data_.bucket_ptr_from_hash(hash_value);
                 link_ptr position = find_iterator(bucket, k);
@@ -1750,7 +1652,7 @@
             iterator_base insert_hint_impl(iterator_base const& it, node_constructor& a)
             {
                 // equal can throw, but with no effects
- if (it == data_.end() || !equal(extract_key(a.get()->value_), *it)) {
+ if (it == data_.end() || !equal(extract_key(a.get()->value()), *it)) {
                     // Use the standard insert if the iterator doesn't point
                     // to a matching key.
                     return insert_impl(a);
@@ -1766,7 +1668,7 @@
                     // reserve has basic exception safety if the hash function
                     // throws, strong otherwise.
                     bucket_ptr base = reserve_for_insert(size() + 1) ?
- get_bucket(extract_key(a.get()->value_)) : it.bucket_;
+ get_bucket(extract_key(a.get()->value())) : it.bucket_;
 
                     // Nothing after this point can throw
 
@@ -1796,7 +1698,7 @@
                     for (; i != j; ++i) {
                         a.construct(*i);
 
- key_type const& k = extract_key(a.get()->value_);
+ key_type const& k = extract_key(a.get()->value());
                         bucket_ptr bucket = get_bucket(k);
                         link_ptr position = find_iterator(bucket, k);
 
@@ -1981,7 +1883,7 @@
                 a.construct(std::forward<Args>(args)...);
 
                 // No side effects in this initial code
- key_type const& k = extract_key(a.get()->value_);
+ key_type const& k = extract_key(a.get()->value());
                 size_type hash_value = hash_function()(k);
                 bucket_ptr bucket = data_.bucket_ptr_from_hash(hash_value);
                 link_ptr pos = find_iterator(bucket, k);

Modified: trunk/libs/unordered/doc/changes.qbk
==============================================================================
--- trunk/libs/unordered/doc/changes.qbk (original)
+++ trunk/libs/unordered/doc/changes.qbk 2008-11-24 18:15:55 EST (Mon, 24 Nov 2008)
@@ -52,5 +52,12 @@
 * [@https://svn.boost.org/trac/boost/ticket/1710 Ticket 1710]:
   Use a larger prime number list. Thanks to Thorsten Ottosen and Hervé
   Brönnimann.
+* Use
+ [@../../libs/type_traits/doc/html/boost_typetraits/category/alignment.html
+ aligned storage] to store the types. This changes the way the allocator is
+ used to construct nodes. It used to construct the node with two calls to
+ the allocator's `construct` method - once for the pointers and once for the
+ value. It now constructs the node with a single call to construct and
+ then constructs the value using in place construction.
 
 [endsect]


Boost-Commit list run by bdawes at acm.org, david.abrahams at rcn.com, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk