Boost logo

Boost-Commit :

From: daniel_james_at_[hidden]
Date: 2007-12-20 16:15:42


Author: danieljames
Date: 2007-12-20 16:15:42 EST (Thu, 20 Dec 2007)
New Revision: 42215
URL: http://svn.boost.org/trac/boost/changeset/42215

Log:
Don't add size_type to pointers, cast to difference_type.
Text files modified:
   branches/unordered/dev/boost/unordered/detail/hash_table_impl.hpp | 103 +++++++++++++++++++++------------------
   1 files changed, 55 insertions(+), 48 deletions(-)

Modified: branches/unordered/dev/boost/unordered/detail/hash_table_impl.hpp
==============================================================================
--- branches/unordered/dev/boost/unordered/detail/hash_table_impl.hpp (original)
+++ branches/unordered/dev/boost/unordered/detail/hash_table_impl.hpp 2007-12-20 16:15:42 EST (Thu, 20 Dec 2007)
@@ -36,6 +36,7 @@
             struct node;
             struct bucket;
             typedef std::size_t size_type;
+ typedef std::ptrdiff_t difference_type;
 
             typedef Alloc value_allocator;
 
@@ -243,21 +244,11 @@
             }
 
             // pre: Must be pointing to the first node in a group.
- static inline link_ptr last_in_group(link_ptr n) {
- BOOST_ASSERT(BOOST_UNORDERED_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 inline link_ptr& next_group(link_ptr n) {
                 BOOST_ASSERT(BOOST_UNORDERED_BORLAND_BOOL(n) && n != prev_in_group(n)->next_);
                 return prev_in_group(n)->next_;
             }
 #else
- static inline link_ptr last_in_group(link_ptr n) {
- return n;
- }
-
             static inline link_ptr& next_group(link_ptr n) {
                 BOOST_ASSERT(n);
                 return n->next_;
@@ -320,6 +311,16 @@
                         node_ = bucket_->next_;
                     }
                 }
+
+ void incrementGroup()
+ {
+ node_ = data::next_group(node_);
+
+ while (!node_) {
+ ++bucket_;
+ node_ = bucket_->next_;
+ }
+ }
             };
 
             // Member Variables
@@ -345,7 +346,7 @@
                 // Creates an extra bucket to act as a sentinel.
                 constructor.construct(bucket(), bucket_count_ + 1);
 
- cached_begin_bucket_ = constructor.get() + bucket_count_;
+ cached_begin_bucket_ = constructor.get() + static_cast<difference_type>(bucket_count_);
 
                 // Set up the sentinel.
                 cached_begin_bucket_->next_ = link_ptr(cached_begin_bucket_);
@@ -368,7 +369,7 @@
                 // Creates an extra bucket to act as a sentinel.
                 constructor.construct(bucket(), bucket_count_ + 1);
 
- cached_begin_bucket_ = constructor.get() + bucket_count_;
+ cached_begin_bucket_ = constructor.get() + static_cast<difference_type>(bucket_count_);
 
                 // Set up the sentinel
                 cached_begin_bucket_->next_ = link_ptr(cached_begin_bucket_);
@@ -383,15 +384,16 @@
             {
                 if(buckets_) {
                     bucket_ptr begin = cached_begin_bucket_;
- bucket_ptr end = buckets_ + bucket_count_;
+ bucket_ptr end = buckets_end();
                     while(begin != end) {
                         clear_bucket(begin);
                         ++begin;
                     }
 
                     // Destroy an extra bucket for the sentinels.
- for(size_type i2 = 0; i2 < bucket_count_ + 1; ++i2)
- allocators_.bucket_alloc_.destroy(buckets_ + i2);
+ ++end;
+ for(begin = buckets_; begin != end; ++begin)
+ allocators_.bucket_alloc_.destroy(begin);
 
                     allocators_.bucket_alloc_.deallocate(buckets_, bucket_count_ + 1);
                 }
@@ -413,18 +415,24 @@
                 std::swap(size_, other.size_);
             }
 
- // Return the bucket index for a hashed value.
+ // Return the bucket for a hashed value.
             //
             // no throw
- size_type index_from_hash(size_type hashed) const
+ bucket_ptr bucket_from_hash(size_type hashed) const
             {
- return hashed % bucket_count_;
+ return buckets_ + static_cast<difference_type>(hashed % bucket_count_);
             }
 
             // Begin & End
             //
             // no throw
 
+ bucket_ptr buckets_end() const
+ {
+ return buckets_ + static_cast<difference_type>(bucket_count_);
+ }
+
+
             iterator_base begin() const
             {
                 return size_
@@ -434,7 +442,7 @@
 
             iterator_base end() const
             {
- return iterator_base(buckets_ + bucket_count_);
+ return iterator_base(buckets_end());
             }
 
             link_ptr begin(size_type n) const
@@ -619,8 +627,7 @@
             {
                 size_type count = group_count(*pos);
                 size_ -= count;
- link_ptr last = last_in_group(*pos);
- *pos = last->next_;
+ *pos = next_group(*pos);
                 return count;
             }
 #else
@@ -832,7 +839,7 @@
             void clear()
             {
                 bucket_ptr begin = cached_begin_bucket_;
- bucket_ptr end = buckets_ + bucket_count_;
+ bucket_ptr end = buckets_end();
 
                 size_ = 0;
                 cached_begin_bucket_ = end;
@@ -880,7 +887,8 @@
                         unlink_nodes(r1);
                         delete_to_bucket_end(r1.node_);
 
- for(bucket_ptr i = r1.bucket_ + 1; i != r2.bucket_; ++i) {
+ bucket_ptr i = r1.bucket_;
+ for(++i; i != r2.bucket_; ++i) {
                             size_ -= node_count(i->next_);
                             clear_bucket(i);
                         }
@@ -917,7 +925,7 @@
                         while (cached_begin_bucket_->empty())
                             ++cached_begin_bucket_;
                     } else {
- cached_begin_bucket_ = buckets_ + bucket_count_;
+ cached_begin_bucket_ = buckets_end();
                     }
                 }
             }
@@ -929,7 +937,7 @@
             void recompute_begin_bucket(bucket_ptr b1, bucket_ptr b2)
             {
                 BOOST_ASSERT(!(b1 < cached_begin_bucket_) && !(b2 < b1));
- BOOST_ASSERT(b2 == buckets_ + bucket_count_ || !b2->empty());
+ BOOST_ASSERT(b2 == buckets_end() || !b2->empty());
 
                 if(b1 == cached_begin_bucket_ && b1->empty())
                     cached_begin_bucket_ = b2;
@@ -985,6 +993,7 @@
             typedef Pred key_equal;
             typedef ValueType value_type;
             typedef std::size_t size_type;
+ typedef std::ptrdiff_t difference_type;
 
             // iterators
 
@@ -1248,13 +1257,14 @@
             size_type bucket(key_type const& k) const
             {
                 // hash_function can throw:
- return this->index_from_hash(hash_function()(k));
+ return hash_function()(k) % this->bucket_count_;
             }
 
+
             // strong safety
             bucket_ptr get_bucket(key_type const& k) const
             {
- return this->buckets_ + bucket(k);
+ return this->buckets_ + static_cast<difference_type>(bucket(k));
             }
 
             // no throw
@@ -1416,7 +1426,7 @@
                 BOOST_ASSERT(dst.size_ == 0);
                 //BOOST_ASSERT(src.allocators_.node_alloc_ == dst.allocators_.node_alloc_);
 
- bucket_ptr end = src.buckets_ + src.bucket_count_;
+ bucket_ptr end = src.buckets_end();
 
                 for(; src.cached_begin_bucket_ != end;
                         ++src.cached_begin_bucket_) {
@@ -1426,8 +1436,7 @@
                         // src_bucket to dst.
 
                         // This next line throws iff the hash function throws.
- bucket_ptr dst_bucket = dst.buckets_ +
- dst.index_from_hash(
+ bucket_ptr dst_bucket = dst.bucket_from_hash(
                                 hf(extract_key(data::get_value(src_bucket->next_))));
 
                         link_ptr n = src_bucket->next_;
@@ -1444,7 +1453,7 @@
             {
                 BOOST_ASSERT(dst.size_ == 0);
                 // no throw:
- bucket_ptr end = src.buckets_ + src.bucket_count_;
+ bucket_ptr end = src.buckets_end();
                 hasher const& hf = f.hash_function();
 
                 // no throw:
@@ -1453,8 +1462,8 @@
                     for(link_ptr it = src.begin(i);
                             BOOST_UNORDERED_BORLAND_BOOL(it); it = data::next_group(it)) {
                         // hash function can throw.
- bucket_ptr dst_bucket = dst.buckets_ +
- dst.index_from_hash(hf(extract_key(data::get_value(it))));
+ bucket_ptr dst_bucket = dst.bucket_from_hash(
+ hf(extract_key(data::get_value(it))));
                         // throws, strong
                         dst.copy_group(it, dst_bucket);
                     }
@@ -1478,8 +1487,7 @@
             {
                 key_type const& k = extract_key(v);
                 size_type hash_value = hash_function()(k);
- bucket_ptr bucket = this->buckets_
- + this->index_from_hash(hash_value);
+ bucket_ptr bucket = this->bucket_from_hash(hash_value);
                 link_ptr position = find_iterator(bucket, k);
 
                 // Create the node before rehashing in case it throws an
@@ -1490,7 +1498,7 @@
                 // reserve has basic exception safety if the hash function
                 // throws, strong otherwise.
                 if(reserve(size() + 1))
- bucket = this->buckets_ + this->index_from_hash(hash_value);
+ bucket = this->bucket_from_hash(hash_value);
 
                 // Nothing after the point can throw.
 
@@ -1610,7 +1618,7 @@
                 typedef BOOST_DEDUCED_TYPENAME value_type::second_type mapped_type;
 
                 size_type hash_value = hash_function()(k);
- bucket_ptr bucket = this->buckets_ + this->index_from_hash(hash_value);
+ bucket_ptr bucket = this->bucket_from_hash(hash_value);
                 link_ptr pos = find_iterator(bucket, k);
 
                 if (BOOST_UNORDERED_BORLAND_BOOL(pos))
@@ -1626,8 +1634,8 @@
 
                     // reserve has basic exception safety if the hash function
                     // throws, strong otherwise.
- if (reserve(size() + 1))
- bucket = this->buckets_ + this->index_from_hash(hash_value);
+ if(reserve(size() + 1))
+ bucket = this->bucket_from_hash(hash_value);
 
                     // Nothing after this point can throw.
 
@@ -1647,7 +1655,7 @@
                 // No side effects in this initial code
                 key_type const& k = extract_key(v);
                 size_type hash_value = hash_function()(k);
- bucket_ptr bucket = this->buckets_ + this->index_from_hash(hash_value);
+ bucket_ptr bucket = this->bucket_from_hash(hash_value);
                 link_ptr pos = find_iterator(bucket, k);
                 
                 if (BOOST_UNORDERED_BORLAND_BOOL(pos)) {
@@ -1667,7 +1675,7 @@
                     // reserve has basic exception safety if the hash function
                     // throws, strong otherwise.
                     if(reserve(size() + 1))
- bucket = this->buckets_ + this->index_from_hash(hash_value);
+ bucket = this->bucket_from_hash(hash_value);
 
                     // Nothing after this point can throw.
 
@@ -1723,8 +1731,7 @@
                 for (; i != j; ++i) {
                     // No side effects in this initial code
                     size_type hash_value = hash_function()(extract_key(*i));
- bucket_ptr bucket = this->buckets_
- + this->index_from_hash(hash_value);
+ bucket_ptr bucket = this->bucket_from_hash(hash_value);
                     link_ptr pos = find_iterator(bucket, extract_key(*i));
                     
                     if (!BOOST_UNORDERED_BORLAND_BOOL(pos)) {
@@ -1740,7 +1747,7 @@
                         // throws, strong otherwise.
                         if(size() + 1 >= max_load_) {
                             reserve(size() + insert_size(i, j));
- bucket = this->buckets_ + this->index_from_hash(hash_value);
+ bucket = this->bucket_from_hash(hash_value);
                         }
 
                         // Nothing after this point can throw.
@@ -1819,8 +1826,8 @@
                 link_ptr it = find_iterator(bucket, k);
                 if (BOOST_UNORDERED_BORLAND_BOOL(it)) {
                     iterator_base first(iterator_base(bucket, it));
- iterator_base second(iterator_base(bucket, this->last_in_group(it)));
- second.increment();
+ iterator_base second(first);
+ second.incrementGroup();
                     return std::pair<iterator_base, iterator_base>(first, second);
                 }
                 else {
@@ -1872,7 +1879,7 @@
                 if(this->size() != other.size()) return false;
 
                 for(bucket_ptr i = this->cached_begin_bucket_,
- j = this->buckets_ + this->bucket_count_; i != j; ++i)
+ j = this->buckets_end(); i != j; ++i)
                 {
                     for(link_ptr it(i->next_); BOOST_UNORDERED_BORLAND_BOOL(it); it = data::next_group(it))
                     {
@@ -1912,7 +1919,7 @@
                 std::size_t seed = 0;
 
                 for(bucket_ptr i = this->cached_begin_bucket_,
- j = this->buckets_ + this->bucket_count_; i != j; ++i)
+ j = this->buckets_end(); i != j; ++i)
                 {
                     for(link_ptr it(i->next_); BOOST_UNORDERED_BORLAND_BOOL(it); it = data::next_group(it))
                         seed ^= group_hash(it, (type_wrapper<value_type>*)0);


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