[Boost-commit] svn:boost r81207 - trunk/boost/unordered/detail

Subject: [Boost-commit] svn:boost r81207 - trunk/boost/unordered/detail
From: dnljms_at_[hidden]
Date: 2012-11-05 13:33:00

Author: danieljames
Date: 2012-11-05 13:32:59 EST (Mon, 05 Nov 2012)
New Revision: 81207
URL: http://svn.boost.org/trac/boost/changeset/81207

Log:
Unordered: Simpler erase implementation.
Text files modified: 
   trunk/boost/unordered/detail/equivalent.hpp |   151 ++++++++++++--------------------------- 
   trunk/boost/unordered/detail/table.hpp      |   121 +++++++++----------------------         
   trunk/boost/unordered/detail/unique.hpp     |    55 +++++---------                          
   3 files changed, 102 insertions(+), 225 deletions(-)

Modified: trunk/boost/unordered/detail/equivalent.hpp
==============================================================================
--- trunk/boost/unordered/detail/equivalent.hpp	(original)
+++ trunk/boost/unordered/detail/equivalent.hpp	2012-11-05 13:32:59 EST (Mon, 05 Nov 2012)
@@ -545,9 +545,7 @@
             std::size_t key_hash = this->hash(k);
             std::size_t bucket_index =
                 policy::to_bucket(this->bucket_count_, key_hash);
-            bucket_pointer this_bucket = this->get_bucket(bucket_index);
-
-            link_pointer prev = this_bucket->next_;
+            link_pointer prev = this->get_previous_start(bucket_index);
             if (!prev) return 0;
 
             for (;;)
@@ -565,13 +563,12 @@
                 prev = static_cast<node_pointer>(prev->next_)->group_prev_;
             }
 
-            node_pointer pos = static_cast<node_pointer>(prev->next_);
-            link_pointer end1 =
-                static_cast<node_pointer>(pos->group_prev_)->next_;
-            node_pointer end = static_cast<node_pointer>(end1);
-            prev->next_ = end1;
-            this->fix_buckets(this_bucket, prev, end);
-            return this->delete_nodes(c_iterator(pos), c_iterator(end));
+            node_pointer first_node = static_cast<node_pointer>(prev->next_);
+            link_pointer end = static_cast<node_pointer>(first_node->group_prev_)->next_;
+
+            std::size_t count = this->delete_nodes(prev, end);
+            this->fix_bucket(bucket_index, prev);
+            return count;
         }
 
         iterator erase(c_iterator r)
@@ -579,128 +576,74 @@
             BOOST_ASSERT(r.node_);
             iterator next(r.node_);
             ++next;
-
-            bucket_pointer this_bucket = this->get_bucket(
-                policy::to_bucket(this->bucket_count_, r.node_->hash_));
-            link_pointer prev = unlink_node(*this_bucket, r.node_);
-
-            this->fix_buckets(this_bucket, prev, next.node_);
-
-            this->delete_node(r);
-
+            erase_nodes(r.node_, next.node_);
             return next;
         }
 
         iterator erase_range(c_iterator r1, c_iterator r2)
         {
             if (r1 == r2) return iterator(r2.node_);
-
-            std::size_t bucket_index =
-                policy::to_bucket(this->bucket_count_, r1.node_->hash_);
-            link_pointer prev = unlink_nodes(
-                *this->get_bucket(bucket_index), r1.node_, r2.node_);
-            this->fix_buckets_range(bucket_index, prev, r1.node_, r2.node_);
-            this->delete_nodes(r1, r2);
-
+            erase_nodes(r1.node_, r2.node_);
             return iterator(r2.node_);
         }
 
-        static link_pointer unlink_node(bucket& b, node_pointer n)
+        link_pointer erase_nodes(node_pointer begin, node_pointer end)
         {
-            node_pointer next = static_cast<node_pointer>(n->next_);
-            link_pointer prev = n->group_prev_;
-
-            if(prev->next_ != n) {
-                // The node is at the beginning of a group.
+            std::size_t bucket_index =
+                policy::to_bucket(this->bucket_count_, begin->hash_);
 
-                // Find the previous node pointer:
-                prev = b.next_;
-                while(prev->next_ != n) {
+            // Split the groups containing 'begin' and 'end'.
+            // And get the pointer to the node before begin while
+            // we're at it.
+            link_pointer prev = split_groups(begin, end);
+
+            // If we don't have a 'prev' it means that begin is at the
+            // beginning of a block, so search through the blocks in the
+            // same bucket.
+            if (!prev) {
+                prev = this->get_previous_start(bucket_index);
+                while (prev->next_ != begin)
                     prev = static_cast<node_pointer>(prev->next_)->group_prev_;
-                }
-
-                // Remove from group
-                if (next && next->group_prev_ == n)
-                {
-                    next->group_prev_ = n->group_prev_;
-                }
-            }
-            else if (next && next->group_prev_ == n)
-            {
-                // The deleted node is not at the end of the group, so
-                // change the link from the next node.
-                next->group_prev_ = n->group_prev_;
-            }
-            else {
-                // The deleted node is at the end of the group, so the
-                // first node in the group is pointing to it.
-                // Find that to change its pointer.
-                node_pointer x = static_cast<node_pointer>(n->group_prev_);
-                while (x->group_prev_ != n) {
-                    x = static_cast<node_pointer>(x->group_prev_);
-                }
-                x->group_prev_ = n->group_prev_;
             }
 
-            prev->next_ = next;
+            // Delete the nodes.
+            do {
+                link_pointer group_end =
+                    static_cast<node_pointer>(
+                        static_cast<node_pointer>(prev->next_)->group_prev_)->next_;
+                this->delete_nodes(prev, group_end);
+                bucket_index = this->fix_bucket(bucket_index, prev);
+            } while(prev->next_ != end);
+
             return prev;
         }
 
-        static link_pointer unlink_nodes(bucket& b,
-                node_pointer begin, node_pointer end)
+        static link_pointer split_groups(node_pointer begin, node_pointer end)
         {
-            link_pointer prev = begin->group_prev_;
+            node_pointer prev = static_cast<node_pointer>(begin->group_prev_);
+            if (prev->next_ != begin) prev = node_pointer();
 
-            if (prev->next_ != begin) {
-                // The node is at the beginning of a group.
-
-                // Find the previous node pointer:
-                prev = b.next_;
-                while (prev->next_ != begin)
-                    prev = static_cast<node_pointer>(prev->next_)->group_prev_;
+            if (end) {
+                node_pointer first = end;
+                while (first != begin && static_cast<node_pointer>(first->group_prev_)->next_ == first) {
+                    first = static_cast<node_pointer>(first->group_prev_);
+                }
 
-                if (end) split_group(end);
+                boost::swap(first->group_prev_, end->group_prev_);
+                if (first == begin) return prev;
             }
-            else {
-                node_pointer group1 = split_group(begin);
-
-                if (end) {
-                    node_pointer group2 = split_group(end);
 
-                    if(begin == group2) {
-                        link_pointer end1 = group1->group_prev_;
-                        link_pointer end2 = end->group_prev_;
-                        group1->group_prev_ = end2;
-                        end->group_prev_ = end1;
-                    }
+            if (prev) {
+                node_pointer first = prev;
+                while (static_cast<node_pointer>(first->group_prev_)->next_ == first) {
+                    first = static_cast<node_pointer>(first->group_prev_);
                 }
+                boost::swap(first->group_prev_, begin->group_prev_);
             }
 
-            prev->next_ = end;
-
             return prev;
         }
 
-        // Break a ciruclar list into two, with split as the beginning
-        // of the second group (if split is at the beginning then don't
-        // split).
-        static node_pointer split_group(node_pointer split)
-        {
-            // Find first node in group.
-            node_pointer first = split;
-            while (static_cast<node_pointer>(first->group_prev_)->next_ ==
-                    first)
-                first = static_cast<node_pointer>(first->group_prev_);
-
-            if(first == split) return split;
-
-            link_pointer last = first->group_prev_;
-            first->group_prev_ = split->group_prev_;
-            split->group_prev_ = last;
-
-            return first;
-        }
-
         ////////////////////////////////////////////////////////////////////////
         // fill_buckets
 

Modified: trunk/boost/unordered/detail/table.hpp
==============================================================================
--- trunk/boost/unordered/detail/table.hpp	(original)
+++ trunk/boost/unordered/detail/table.hpp	2012-11-05 13:32:59 EST (Mon, 05 Nov 2012)
@@ -498,26 +498,29 @@
             delete_buckets();
         }
 
-        void delete_node(c_iterator n)
+        void delete_node(link_pointer prev)
         {
+            node_pointer n = static_cast<node_pointer>(prev->next_);
+            prev->next_ = n->next_;
+
             boost::unordered::detail::destroy_value_impl(node_alloc(),
-                n.node_->value_ptr());
+                n->value_ptr());
             node_allocator_traits::destroy(node_alloc(),
-                    boost::addressof(*n.node_));
-            node_allocator_traits::deallocate(node_alloc(), n.node_, 1);
+                    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;
         }
@@ -525,7 +528,7 @@
         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>(
@@ -545,10 +548,9 @@
 
         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_);
@@ -577,86 +579,33 @@
         }
 
         ////////////////////////////////////////////////////////////////////////
-        // 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,
-                link_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_));
+                bucket_index2 = policy::to_bucket(bucket_count_,
+                    static_cast<node_pointer>(end)->hash_);
 
-                if (next_bucket != this_bucket)
-                {
-                    next_bucket->next_ = prev;
-                    if (this_bucket->next_ == prev)
-                        this_bucket->next_ = node_pointer();
-                }
-            }
-        }
+                // If begin and end are in the same bucket, then
+                // there's nothing to do.
+                if (bucket_index == bucket_index2) return bucket_index2;
 
-        // 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,
-                link_pointer prev, node_pointer begin, node_pointer end)
-        {
-            node_pointer n = begin;
-
-            // 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_ = link_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_ = link_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;
         }
 
         ////////////////////////////////////////////////////////////////////////

Modified: trunk/boost/unordered/detail/unique.hpp
==============================================================================
--- trunk/boost/unordered/detail/unique.hpp	(original)
+++ trunk/boost/unordered/detail/unique.hpp	2012-11-05 13:32:59 EST (Mon, 05 Nov 2012)
@@ -519,9 +519,7 @@
             std::size_t key_hash = this->hash(k);
             std::size_t bucket_index =
                 policy::to_bucket(this->bucket_count_, key_hash);
-            bucket_pointer this_bucket = this->get_bucket(bucket_index);
-
-            link_pointer prev = this_bucket->next_;
+            link_pointer prev = this->get_previous_start(bucket_index);
             if (!prev) return 0;
 
             for (;;)
@@ -539,11 +537,11 @@
                 prev = prev->next_;
             }
 
-            node_pointer pos = static_cast<node_pointer>(prev->next_);
-            node_pointer end = static_cast<node_pointer>(pos->next_);
-            prev->next_ = pos->next_;
-            this->fix_buckets(this_bucket, prev, end);
-            return this->delete_nodes(c_iterator(pos), c_iterator(end));
+            link_pointer end = static_cast<node_pointer>(prev->next_)->next_;
+
+            std::size_t count = this->delete_nodes(prev, end);
+            this->fix_bucket(bucket_index, prev);
+            return count;
         }
 
         iterator erase(c_iterator r)
@@ -551,44 +549,31 @@
             BOOST_ASSERT(r.node_);
             iterator next(r.node_);
             ++next;
-
-            bucket_pointer this_bucket = this->get_bucket(
-                policy::to_bucket(this->bucket_count_, r.node_->hash_));
-            link_pointer prev = unlink_node(*this_bucket, r.node_);
-
-            this->fix_buckets(this_bucket, prev, next.node_);
-
-            this->delete_node(r);
-
+            erase_nodes(r.node_, next.node_);
             return next;
         }
 
         iterator erase_range(c_iterator r1, c_iterator r2)
         {
             if (r1 == r2) return iterator(r2.node_);
-
-            std::size_t bucket_index =
-                policy::to_bucket(this->bucket_count_, r1.node_->hash_);
-            link_pointer prev = unlink_nodes(
-                *this->get_bucket(bucket_index), r1.node_, r2.node_);
-            this->fix_buckets_range(bucket_index, prev, r1.node_, r2.node_);
-            this->delete_nodes(r1, r2);
-
+            erase_nodes(r1.node_, r2.node_);
             return iterator(r2.node_);
         }
 
-        static link_pointer unlink_node(bucket& b, node_pointer n)
+        void erase_nodes(node_pointer begin, node_pointer end)
         {
-            return unlink_nodes(b, n, static_cast<node_pointer>(n->next_));
-        }
+            std::size_t bucket_index =
+                policy::to_bucket(this->bucket_count_, begin->hash_);
 
-        static link_pointer unlink_nodes(bucket& b,
-                node_pointer begin, node_pointer end)
-        {
-            link_pointer prev = b.next_;
-            while (prev->next_ != begin) prev = prev->next_;
-            prev->next_ = end;
-            return prev;
+            // Find the node before begin.
+            link_pointer prev = this->get_previous_start(bucket_index);
+            while(prev->next_ != begin) prev = prev->next_;
+
+            // Delete the nodes.
+            do {
+                this->delete_node(prev);
+                bucket_index = this->fix_bucket(bucket_index, prev);
+            } while (prev->next_ != end);
         }
 
         ////////////////////////////////////////////////////////////////////////