|
|
Boost-Commit : |
From: daniel_james_at_[hidden]
Date: 2007-12-08 12:35:21
Author: danieljames
Date: 2007-12-08 12:35:20 EST (Sat, 08 Dec 2007)
New Revision: 41894
URL: http://svn.boost.org/trac/boost/changeset/41894
Log:
Pull the two different node_base classes out of HASH_TABLE_DATA.
Text files modified:
sandbox-branches/unordered-refactor/boost/unordered/detail/hash_table.hpp | 217 ++++++++++++++++++++++++++++++++++++++++
sandbox-branches/unordered-refactor/boost/unordered/detail/hash_table_impl.hpp | 211 --------------------------------------
2 files changed, 219 insertions(+), 209 deletions(-)
Modified: sandbox-branches/unordered-refactor/boost/unordered/detail/hash_table.hpp
==============================================================================
--- sandbox-branches/unordered-refactor/boost/unordered/detail/hash_table.hpp (original)
+++ sandbox-branches/unordered-refactor/boost/unordered/detail/hash_table.hpp 2007-12-08 12:35:20 EST (Sat, 08 Dec 2007)
@@ -140,6 +140,223 @@
return !this->next_;
}
};
+
+ // Hash Node
+ //
+ // all no throw
+
+ template <typename Alloc>
+ struct node_base_equivalent_keys : bucket<Alloc>
+ {
+ public:
+ typedef typename bucket<Alloc>::bucket_ptr bucket_ptr;
+ typedef typename bucket<Alloc>::link_ptr link_ptr;
+ typedef std::size_t size_type;
+
+ node_base_equivalent_keys() : group_prev_()
+ {
+ BOOST_HASH_MSVC_RESET_PTR(group_prev_);
+ }
+
+ link_ptr group_prev_;
+
+ static link_ptr& prev_in_group(link_ptr n) {
+ return static_cast<node_base_equivalent_keys&>(*n).group_prev_;
+ }
+
+ // pre: Must be pointing to the first node in a group.
+ static link_ptr last_in_group(link_ptr n) {
+ BOOST_ASSERT(BOOST_HASH_BORLAND_BOOL(n) && n != prev_in_group(n)->next_);
+ return prev_in_group(n);
+ }
+
+ // pre: Must be pointing to the first node in a group.
+ static link_ptr& next_group(link_ptr n) {
+ BOOST_ASSERT(BOOST_HASH_BORLAND_BOOL(n) && n != prev_in_group(n)->next_);
+ return prev_in_group(n)->next_;
+ }
+
+ // pre: Must be pointing to a node
+ static node_base_equivalent_keys& get_node(link_ptr p) {
+ BOOST_ASSERT(p);
+ return static_cast<node_base_equivalent_keys&>(*p);
+ }
+
+ static size_type group_count(link_ptr it)
+ {
+ size_type count = 0;
+ link_ptr first = it;
+ do {
+ ++count;
+ it = prev_in_group(it);
+ } while (it != first); // throws, strong
+ return count;
+ }
+
+ static link_ptr* get_for_erase(bucket_ptr bucket, link_ptr n)
+ {
+ // If the element isn't the first in its group, then
+ // the link to it will be found in the previous element
+ // in the group.
+ link_ptr* it = &prev_in_group(n)->next_;
+ if(*it == n) return it;
+
+ // The element is the first in its group, so iterate
+ // throught the groups, checking against the first element.
+ it = &bucket->next_;
+ while(*it != n) it = &next_group(*it);
+ return it;
+ }
+
+ static void link_node(link_ptr n, link_ptr pos)
+ {
+ node_base_equivalent_keys& node_ref = get_node(n);
+ node_base_equivalent_keys& pos_ref = get_node(pos);
+ node_ref.next_ = pos_ref.group_prev_->next_;
+ node_ref.group_prev_ = pos_ref.group_prev_;
+ pos_ref.group_prev_->next_ = n;
+ pos_ref.group_prev_ = n;
+ }
+
+ static void link_node_in_bucket(link_ptr n, bucket_ptr base)
+ {
+ node_base_equivalent_keys& node_ref = get_node(n);
+ node_ref.next_ = base->next_;
+ node_ref.group_prev_ = n;
+ base->next_ = n;
+ }
+
+ static void link_group(link_ptr n, bucket_ptr base)
+ {
+ node_base_equivalent_keys& node_ref = get_node(n);
+ node_base_equivalent_keys& last_ref = get_node(node_ref.group_prev_);
+ last_ref.next_ = base->next_;
+ base->next_ = n;
+ }
+
+ static void unlink_node(link_ptr* pos)
+ {
+ node_base_equivalent_keys* n = &get_node(*pos);
+ link_ptr next = n->next_;
+
+ if(n->group_prev_ == *pos) {
+ // The deleted node is the sole node in the group, so
+ // no need to unlink it from a group.
+ }
+ else if(BOOST_HASH_BORLAND_BOOL(next) && prev_in_group(next) == *pos)
+ {
+ // The deleted node is not at the end of the group, so
+ // change the link from the next node.
+ prev_in_group(next) = 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.
+ link_ptr it = n->group_prev_;
+ while(prev_in_group(it) != *pos) {
+ it = prev_in_group(it);
+ }
+ prev_in_group(it) = n->group_prev_;
+ }
+ *pos = next;
+ }
+
+ // 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 link_ptr split_group(link_ptr split) {
+ // If split is at the beginning of the group then there's
+ // nothing to split.
+ if(prev_in_group(split)->next_ != split)
+ return link_ptr();
+
+ // Find the start of the group.
+ link_ptr start = split;
+ do {
+ start = prev_in_group(start);
+ } while(prev_in_group(start)->next_ == start);
+
+ link_ptr last = prev_in_group(start);
+ prev_in_group(start) = prev_in_group(split);
+ prev_in_group(split) = last;
+
+ return start;
+ }
+
+ static void split_group(link_ptr split1, link_ptr split2) {
+ link_ptr begin1 = split_group(split1);
+ link_ptr begin2 = split_group(split2);
+
+ if(BOOST_HASH_BORLAND_BOOL(begin1) && split1 == begin2) {
+ link_ptr end1 = prev_in_group(begin1);
+ prev_in_group(begin1) = prev_in_group(begin2);
+ prev_in_group(begin2) = end1;
+ }
+ }
+ };
+
+ template <class Alloc>
+ struct node_base_unique_keys : bucket<Alloc>
+ {
+ typedef typename bucket<Alloc>::bucket_ptr bucket_ptr;
+ typedef typename bucket<Alloc>::link_ptr link_ptr;
+ typedef std::size_t size_type;
+
+ link_ptr& prev_in_group(link_ptr) const {
+ BOOST_ASSERT(false);
+ }
+
+ static link_ptr last_in_group(link_ptr n) {
+ return n;
+ }
+
+ static link_ptr& next_group(link_ptr n) {
+ BOOST_ASSERT(n);
+ return n->next_;
+ }
+
+ // pre: Must be pointing to a node
+ static node_base_unique_keys& get_node(link_ptr p) {
+ BOOST_ASSERT(p);
+ return static_cast<node_base_unique_keys&>(*p);
+ }
+
+ static size_type group_count(link_ptr){
+ return 1;
+ }
+
+ static link_ptr* get_for_erase(bucket_ptr bucket, link_ptr n)
+ {
+ link_ptr* it = &bucket->next_;
+ while(*it != n) it = &(*it)->next_;
+ return it;
+ }
+
+ static void link_node(link_ptr n, link_ptr pos)
+ {
+ BOOST_ASSERT(false);
+ }
+
+ static void link_node_in_bucket(link_ptr n, bucket_ptr base)
+ {
+ n->next_ = base->next_;
+ base->next_ = n;
+ }
+
+ static void link_group(link_ptr n, bucket_ptr base)
+ {
+ link_node_in_bucket(n, base);
+ }
+
+ static void unlink_node(link_ptr* pos)
+ {
+ *pos = (*pos)->next_;
+ }
+
+ static void split_group(link_ptr) {}
+ static void split_group(link_ptr, link_ptr) {}
+ };
}
}
Modified: sandbox-branches/unordered-refactor/boost/unordered/detail/hash_table_impl.hpp
==============================================================================
--- sandbox-branches/unordered-refactor/boost/unordered/detail/hash_table_impl.hpp (original)
+++ sandbox-branches/unordered-refactor/boost/unordered/detail/hash_table_impl.hpp 2007-12-08 12:35:20 EST (Sat, 08 Dec 2007)
@@ -40,217 +40,10 @@
typedef BOOST_DEDUCED_TYPENAME allocator_pointer<node_allocator>::type node_ptr;
typedef BOOST_DEDUCED_TYPENAME allocator_reference<value_allocator>::type reference;
- // Hash Node
- //
- // all no throw
-
- struct node_base_equivalent_keys : bucket
- {
- public:
- node_base_equivalent_keys() : group_prev_()
- {
- BOOST_HASH_MSVC_RESET_PTR(group_prev_);
- }
-
- link_ptr group_prev_;
-
- static link_ptr& prev_in_group(link_ptr n) {
- return static_cast<node_base_equivalent_keys&>(*n).group_prev_;
- }
-
- // pre: Must be pointing to the first node in a group.
- static link_ptr last_in_group(link_ptr n) {
- BOOST_ASSERT(BOOST_HASH_BORLAND_BOOL(n) && n != prev_in_group(n)->next_);
- return prev_in_group(n);
- }
-
- // pre: Must be pointing to the first node in a group.
- static link_ptr& next_group(link_ptr n) {
- BOOST_ASSERT(BOOST_HASH_BORLAND_BOOL(n) && n != prev_in_group(n)->next_);
- return prev_in_group(n)->next_;
- }
-
- // pre: Must be pointing to a node
- static node_base_equivalent_keys& get_node(link_ptr p) {
- BOOST_ASSERT(p);
- return static_cast<node_base_equivalent_keys&>(*p);
- }
-
- static size_type group_count(link_ptr it)
- {
- size_type count = 0;
- link_ptr first = it;
- do {
- ++count;
- it = prev_in_group(it);
- } while (it != first); // throws, strong
- return count;
- }
-
- static link_ptr* get_for_erase(bucket_ptr bucket, link_ptr n)
- {
- // If the element isn't the first in its group, then
- // the link to it will be found in the previous element
- // in the group.
- link_ptr* it = &prev_in_group(n)->next_;
- if(*it == n) return it;
-
- // The element is the first in its group, so iterate
- // throught the groups, checking against the first element.
- it = &bucket->next_;
- while(*it != n) it = &next_group(*it);
- return it;
- }
-
- static void link_node(link_ptr n, link_ptr pos)
- {
- node_base_equivalent_keys& node_ref = get_node(n);
- node_base_equivalent_keys& pos_ref = get_node(pos);
- node_ref.next_ = pos_ref.group_prev_->next_;
- node_ref.group_prev_ = pos_ref.group_prev_;
- pos_ref.group_prev_->next_ = n;
- pos_ref.group_prev_ = n;
- }
-
- static void link_node_in_bucket(link_ptr n, bucket_ptr base)
- {
- node_base_equivalent_keys& node_ref = get_node(n);
- node_ref.next_ = base->next_;
- node_ref.group_prev_ = n;
- base->next_ = n;
- }
-
- static void link_group(link_ptr n, bucket_ptr base)
- {
- node_base_equivalent_keys& node_ref = get_node(n);
- node_base_equivalent_keys& last_ref = get_node(node_ref.group_prev_);
- last_ref.next_ = base->next_;
- base->next_ = n;
- }
-
- static void unlink_node(link_ptr* pos)
- {
- node_base_equivalent_keys* n = &get_node(*pos);
- link_ptr next = n->next_;
-
- if(n->group_prev_ == *pos) {
- // The deleted node is the sole node in the group, so
- // no need to unlink it from a group.
- }
- else if(BOOST_HASH_BORLAND_BOOL(next) && prev_in_group(next) == *pos)
- {
- // The deleted node is not at the end of the group, so
- // change the link from the next node.
- prev_in_group(next) = 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.
- link_ptr it = n->group_prev_;
- while(prev_in_group(it) != *pos) {
- it = prev_in_group(it);
- }
- prev_in_group(it) = n->group_prev_;
- }
- *pos = next;
- }
-
- // 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 link_ptr split_group(link_ptr split) {
- // If split is at the beginning of the group then there's
- // nothing to split.
- if(prev_in_group(split)->next_ != split)
- return link_ptr();
-
- // Find the start of the group.
- link_ptr start = split;
- do {
- start = prev_in_group(start);
- } while(prev_in_group(start)->next_ == start);
-
- link_ptr last = prev_in_group(start);
- prev_in_group(start) = prev_in_group(split);
- prev_in_group(split) = last;
-
- return start;
- }
-
- static void split_group(link_ptr split1, link_ptr split2) {
- link_ptr begin1 = split_group(split1);
- link_ptr begin2 = split_group(split2);
-
- if(BOOST_HASH_BORLAND_BOOL(begin1) && split1 == begin2) {
- link_ptr end1 = prev_in_group(begin1);
- prev_in_group(begin1) = prev_in_group(begin2);
- prev_in_group(begin2) = end1;
- }
- }
- };
-
- struct node_base_unique_keys : bucket
- {
- link_ptr& prev_in_group(link_ptr) const {
- BOOST_ASSERT(false);
- }
-
- static link_ptr last_in_group(link_ptr n) {
- return n;
- }
-
- static link_ptr& next_group(link_ptr n) {
- BOOST_ASSERT(n);
- return n->next_;
- }
-
- // pre: Must be pointing to a node
- static node_base_unique_keys& get_node(link_ptr p) {
- BOOST_ASSERT(p);
- return static_cast<node_base_unique_keys&>(*p);
- }
-
- static size_type group_count(link_ptr){
- return 1;
- }
-
- static link_ptr* get_for_erase(bucket_ptr bucket, link_ptr n)
- {
- link_ptr* it = &bucket->next_;
- while(*it != n) it = &(*it)->next_;
- return it;
- }
-
- static void link_node(link_ptr n, link_ptr pos)
- {
- BOOST_ASSERT(false);
- }
-
- static void link_node_in_bucket(link_ptr n, bucket_ptr base)
- {
- n->next_ = base->next_;
- base->next_ = n;
- }
-
- static void link_group(link_ptr n, bucket_ptr base)
- {
- link_node_in_bucket(n, base);
- }
-
- static void unlink_node(link_ptr* pos)
- {
- *pos = (*pos)->next_;
- }
-
- static void split_group(link_ptr) {}
- static void split_group(link_ptr, link_ptr) {}
- };
-
#if BOOST_UNORDERED_HASH_EQUIVALENT
- typedef node_base_equivalent_keys node_base;
+ typedef node_base_equivalent_keys<Alloc> node_base;
#else
- typedef node_base_unique_keys node_base;
+ typedef node_base_unique_keys<Alloc> node_base;
#endif
typedef BOOST_DEDUCED_TYPENAME
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