Imported Upstream version 1.57.0upstream/1.57.0

1 files changed, 140 insertions, 52 deletions

diff --git a/boost/dynamic_bitset/dynamic_bitset.hpp b/boost/dynamic_bitset/dynamic_bitset.hpp
index 930e4b2dab..4d6011c2e9 100644
--- a/boost/dynamic_bitset/dynamic_bitset.hpp
+++ b/boost/dynamic_bitset/dynamic_bitset.hpp
@@ -2,6 +2,10 @@
 //
 //   Copyright (c) 2001-2002 Chuck Allison and Jeremy Siek
 //        Copyright (c) 2003-2006, 2008 Gennaro Prota
+//             Copyright (c) 2014 Ahmed Charles
+//
+// Copyright (c) 2014 Glen Joseph Fernandes
+// glenfe at live dot com
 //
 // Distributed under the Boost Software License, Version 1.0.
 //    (See accompanying file LICENSE_1_0.txt or copy at
@@ -36,9 +40,13 @@
 #include "boost/dynamic_bitset_fwd.hpp"
 #include "boost/detail/dynamic_bitset.hpp"
 #include "boost/detail/iterator.hpp" // used to implement append(Iter, Iter)
-#include "boost/static_assert.hpp"
+#include "boost/move/move.hpp"
 #include "boost/limits.hpp"
 #include "boost/pending/lowest_bit.hpp"
+#include "boost/static_assert.hpp"
+#include "boost/utility/addressof.hpp"
+#include "boost/detail/no_exceptions_support.hpp"
+#include "boost/throw_exception.hpp"
 
 
 namespace boost {
@@ -46,21 +54,22 @@ namespace boost {
 template <typename Block, typename Allocator>
 class dynamic_bitset
 {
-  // Portability note: member function templates are defined inside
-  // this class definition to avoid problems with VC++. Similarly,
-  // with the member functions of nested classes.
-  //
-  // [October 2008: the note above is mostly historical; new versions
-  // of VC++ are likely able to digest a more drinking form of the
-  // code; but changing it now is probably not worth the risks...]
+    // Portability note: member function templates are defined inside
+    // this class definition to avoid problems with VC++. Similarly,
+    // with the member functions of nested classes.
+    //
+    // [October 2008: the note above is mostly historical; new versions
+    // of VC++ are likely able to digest a more drinking form of the
+    // code; but changing it now is probably not worth the risks...]
 
-  BOOST_STATIC_ASSERT((bool)detail::dynamic_bitset_impl::allowed_block_type<Block>::value);
+    BOOST_STATIC_ASSERT((bool)detail::dynamic_bitset_impl::allowed_block_type<Block>::value);
+    typedef std::vector<Block, Allocator> buffer_type;
 
 public:
     typedef Block block_type;
     typedef Allocator allocator_type;
     typedef std::size_t size_type;
-    typedef block_type block_width_type;
+    typedef typename buffer_type::size_type block_width_type;
 
     BOOST_STATIC_CONSTANT(block_width_type, bits_per_block = (std::numeric_limits<Block>::digits));
     BOOST_STATIC_CONSTANT(size_type, npos = static_cast<size_type>(-1));
@@ -207,6 +216,11 @@ public:
     void swap(dynamic_bitset& b);
     dynamic_bitset& operator=(const dynamic_bitset& b);
 
+#ifndef BOOST_NO_CXX11_RVALUE_REFERENCES
+    dynamic_bitset(dynamic_bitset&& src);
+    dynamic_bitset& operator=(dynamic_bitset&& src);
+#endif // BOOST_NO_CXX11_RVALUE_REFERENCES
+
     allocator_type get_allocator() const;
 
     // size changing operations
@@ -270,10 +284,12 @@ public:
     dynamic_bitset& flip(size_type n);
     dynamic_bitset& flip();
     bool test(size_type n) const;
+    bool test_set(size_type n, bool val = true);
+    bool all() const;
     bool any() const;
     bool none() const;
     dynamic_bitset operator~() const;
-    size_type count() const;
+    size_type count() const BOOST_NOEXCEPT;
 
     // subscript
     reference operator[](size_type pos) {
@@ -283,10 +299,10 @@ public:
 
     unsigned long to_ulong() const;
 
-    size_type size() const;
-    size_type num_blocks() const;
-    size_type max_size() const;
-    bool empty() const;
+    size_type size() const BOOST_NOEXCEPT;
+    size_type num_blocks() const BOOST_NOEXCEPT;
+    size_type max_size() const BOOST_NOEXCEPT;
+    bool empty() const BOOST_NOEXCEPT;
 
     bool is_subset_of(const dynamic_bitset& a) const;
     bool is_proper_subset_of(const dynamic_bitset& a) const;
@@ -330,17 +346,16 @@ public:
 
 private:
     BOOST_STATIC_CONSTANT(block_width_type, ulong_width = std::numeric_limits<unsigned long>::digits);
-    typedef std::vector<block_type, allocator_type> buffer_type;
 
     void m_zero_unused_bits();
     bool m_check_invariants() const;
 
     size_type m_do_find_from(size_type first_block) const;
 
-    block_width_type count_extra_bits() const { return bit_index(size()); }
-    static size_type block_index(size_type pos) { return pos / bits_per_block; }
-    static block_width_type bit_index(size_type pos) { return static_cast<block_width_type>(pos % bits_per_block); }
-    static Block bit_mask(size_type pos) { return Block(1) << bit_index(pos); }
+    block_width_type count_extra_bits() const BOOST_NOEXCEPT { return bit_index(size()); }
+    static size_type block_index(size_type pos) BOOST_NOEXCEPT { return pos / bits_per_block; }
+    static block_width_type bit_index(size_type pos) BOOST_NOEXCEPT { return static_cast<block_width_type>(pos % bits_per_block); }
+    static Block bit_mask(size_type pos) BOOST_NOEXCEPT { return Block(1) << bit_index(pos); }
 
     template <typename CharT, typename Traits, typename Alloc>
     void init_from_string(const std::basic_string<CharT, Traits, Alloc>& s,
@@ -633,6 +648,34 @@ operator=(const dynamic_bitset<Block, Allocator>& b)
     return *this;
 }
 
+#ifndef BOOST_NO_CXX11_RVALUE_REFERENCES
+
+template <typename Block, typename Allocator>
+inline dynamic_bitset<Block, Allocator>::
+dynamic_bitset(dynamic_bitset<Block, Allocator>&& b)
+  : m_bits(boost::move(b.m_bits)), m_num_bits(boost::move(b.m_num_bits))
+{
+    // Required so that assert(m_check_invariants()); works.
+    assert((b.m_bits = buffer_type()).empty());
+    b.m_num_bits = 0;
+}
+
+template <typename Block, typename Allocator>
+inline dynamic_bitset<Block, Allocator>& dynamic_bitset<Block, Allocator>::
+operator=(dynamic_bitset<Block, Allocator>&& b)
+{
+    if (boost::addressof(b) == this) { return *this; }
+
+    m_bits = boost::move(b.m_bits);
+    m_num_bits = boost::move(b.m_num_bits);
+    // Required so that assert(m_check_invariants()); works.
+    assert((b.m_bits = buffer_type()).empty());
+    b.m_num_bits = 0;
+    return *this;
+}
+
+#endif // BOOST_NO_CXX11_RVALUE_REFERENCES
+
 template <typename Block, typename Allocator>
 inline typename dynamic_bitset<Block, Allocator>::allocator_type
 dynamic_bitset<Block, Allocator>::get_allocator() const
@@ -807,7 +850,7 @@ dynamic_bitset<Block, Allocator>::operator<<=(size_type n)
         }
 
         // zero out div blocks at the less significant end
-        std::fill_n(b, div, static_cast<block_type>(0));
+        std::fill_n(m_bits.begin(), div, static_cast<block_type>(0));
 
         // zero out any 1 bit that flowed into the unused part
         m_zero_unused_bits(); // thanks to Lester Gong
@@ -860,7 +903,7 @@ dynamic_bitset<B, A> & dynamic_bitset<B, A>::operator>>=(size_type n) {
 
 
         // div blocks are zero filled at the most significant end
-        std::fill_n(b + (num_blocks()-div), div, static_cast<block_type>(0));
+        std::fill_n(m_bits.begin() + (num_blocks()-div), div, static_cast<block_type>(0));
     }
 
     return *this;
@@ -967,6 +1010,46 @@ bool dynamic_bitset<Block, Allocator>::test(size_type pos) const
 }
 
 template <typename Block, typename Allocator>
+bool dynamic_bitset<Block, Allocator>::test_set(size_type pos, bool val)
+{
+    bool const b = test(pos);
+    if (b != val) {
+        set(pos, val);
+    }
+    return b;
+}
+
+template <typename Block, typename Allocator>
+bool dynamic_bitset<Block, Allocator>::all() const
+{
+    if (empty()) {
+        return true;
+    }
+
+    const block_width_type extra_bits = count_extra_bits();
+    block_type const all_ones = ~static_cast<Block>(0);
+
+    if (extra_bits == 0) {
+        for (size_type i = 0, e = num_blocks(); i < e; ++i) {
+            if (m_bits[i] != all_ones) {
+                return false;
+            }
+        }
+    } else {
+        for (size_type i = 0, e = num_blocks() - 1; i < e; ++i) {
+            if (m_bits[i] != all_ones) {
+                return false;
+            }
+        }
+        block_type const mask = ~(~static_cast<Block>(0) << extra_bits);
+        if (m_highest_block() != mask) {
+            return false;
+        }
+    }
+    return true;
+}
+
+template <typename Block, typename Allocator>
 bool dynamic_bitset<Block, Allocator>::any() const
 {
     for (size_type i = 0; i < num_blocks(); ++i)
@@ -992,7 +1075,7 @@ dynamic_bitset<Block, Allocator>::operator~() const
 
 template <typename Block, typename Allocator>
 typename dynamic_bitset<Block, Allocator>::size_type
-dynamic_bitset<Block, Allocator>::count() const
+dynamic_bitset<Block, Allocator>::count() const BOOST_NOEXCEPT
 {
     using detail::dynamic_bitset_impl::table_width;
     using detail::dynamic_bitset_impl::access_by_bytes;
@@ -1101,7 +1184,7 @@ to_ulong() const
   // Check for overflows. This may be a performance burden on very
   // large bitsets but is required by the specification, sorry
   if (find_next(ulong_width - 1) != npos)
-    throw std::overflow_error("boost::dynamic_bitset::to_ulong overflow");
+    BOOST_THROW_EXCEPTION(std::overflow_error("boost::dynamic_bitset::to_ulong overflow"));
 
 
   // Ok, from now on we can be sure there's no "on" bit
@@ -1126,21 +1209,21 @@ to_ulong() const
 
 template <typename Block, typename Allocator>
 inline typename dynamic_bitset<Block, Allocator>::size_type
-dynamic_bitset<Block, Allocator>::size() const
+dynamic_bitset<Block, Allocator>::size() const BOOST_NOEXCEPT
 {
     return m_num_bits;
 }
 
 template <typename Block, typename Allocator>
 inline typename dynamic_bitset<Block, Allocator>::size_type
-dynamic_bitset<Block, Allocator>::num_blocks() const
+dynamic_bitset<Block, Allocator>::num_blocks() const BOOST_NOEXCEPT
 {
     return m_bits.size();
 }
 
 template <typename Block, typename Allocator>
 inline typename dynamic_bitset<Block, Allocator>::size_type
-dynamic_bitset<Block, Allocator>::max_size() const
+dynamic_bitset<Block, Allocator>::max_size() const BOOST_NOEXCEPT
 {
     // Semantics of vector<>::max_size() aren't very clear
     // (see lib issue 197) and many library implementations
@@ -1161,7 +1244,7 @@ dynamic_bitset<Block, Allocator>::max_size() const
 }
 
 template <typename Block, typename Allocator>
-inline bool dynamic_bitset<Block, Allocator>::empty() const
+inline bool dynamic_bitset<Block, Allocator>::empty() const BOOST_NOEXCEPT
 {
   return size() == 0;
 }
@@ -1230,7 +1313,7 @@ dynamic_bitset<Block, Allocator>::m_do_find_from(size_type first_block) const
     if (i >= num_blocks())
         return npos; // not found
 
-    return i * bits_per_block + boost::lowest_bit(m_bits[i]);
+    return i * bits_per_block + static_cast<size_type>(boost::lowest_bit(m_bits[i]));
 
 }
 
@@ -1257,11 +1340,11 @@ dynamic_bitset<Block, Allocator>::find_next(size_type pos) const
     const size_type blk = block_index(pos);
     const block_width_type ind = bit_index(pos);
 
-    // mask out bits before pos
-    const Block fore = m_bits[blk] & ( ~Block(0) << ind );
+    // shift bits upto one immediately after current
+    const Block fore = m_bits[blk] >> ind;
 
     return fore?
-        blk * bits_per_block + lowest_bit(fore)
+        pos + static_cast<size_type>(lowest_bit(fore))
         :
         m_do_find_from(blk + 1);
 
@@ -1422,19 +1505,20 @@ operator<<(std::basic_ostream<Ch, Tr>& os,
         const Ch zero = BOOST_DYNAMIC_BITSET_WIDEN_CHAR(fac, '0');
         const Ch one  = BOOST_DYNAMIC_BITSET_WIDEN_CHAR(fac, '1');
 
-        try {
+        BOOST_TRY {
 
-            typedef typename dynamic_bitset<Block, Alloc>::size_type bitsetsize_type;
+            typedef typename dynamic_bitset<Block, Alloc>::size_type bitset_size_type;
             typedef basic_streambuf<Ch, Tr> buffer_type;
 
             buffer_type * buf = os.rdbuf();
-            size_t npad = os.width() <= 0  // careful: os.width() is signed (and can be < 0)
-                || (bitsetsize_type) os.width() <= b.size()? 0 : os.width() - b.size();
+            // careful: os.width() is signed (and can be < 0)
+            const bitset_size_type width = (os.width() <= 0) ? 0 : static_cast<bitset_size_type>(os.width());
+            streamsize npad = (width <= b.size()) ? 0 : width - b.size();
 
             const Ch fill_char = os.fill();
             const ios_base::fmtflags adjustfield = os.flags() & ios_base::adjustfield;
 
-            // if needed fill at left; pad is decresed along the way
+            // if needed fill at left; pad is decreased along the way
             if (adjustfield != ios_base::left) {
                 for (; 0 < npad; --npad)
                     if (Tr::eq_int_type(Tr::eof(), buf->sputc(fill_char))) {
@@ -1445,7 +1529,7 @@ operator<<(std::basic_ostream<Ch, Tr>& os,
 
             if (err == ok) {
                 // output the bitset
-                for (bitsetsize_type i = b.size(); 0 < i; --i) {
+                for (bitset_size_type i = b.size(); 0 < i; --i) {
                     typename buffer_type::int_type
                         ret = buf->sputc(b.test(i-1)? one : zero);
                     if (Tr::eq_int_type(Tr::eof(), ret)) {
@@ -1468,13 +1552,14 @@ operator<<(std::basic_ostream<Ch, Tr>& os,
 
             os.width(0);
 
-        } catch (...) { // see std 27.6.1.1/4
+        } BOOST_CATCH (...) { // see std 27.6.1.1/4
             bool rethrow = false;
-            try { os.setstate(ios_base::failbit); } catch (...) { rethrow = true; }
+            BOOST_TRY { os.setstate(ios_base::failbit); } BOOST_CATCH (...) { rethrow = true; } BOOST_CATCH_END
 
             if (rethrow)
-                throw;
+                BOOST_RETHROW;
         }
+        BOOST_CATCH_END
     }
 
     if(err != ok)
@@ -1520,7 +1605,7 @@ operator>>(std::istream& is, dynamic_bitset<Block, Alloc>& b)
 
         const std::streamsize w = is.width();
         const size_type limit = w > 0 && static_cast<size_type>(w) < b.max_size()
-                                                         ? w : b.max_size();
+                                                         ? static_cast<size_type>(w) : b.max_size();
         typename bitset_type::bit_appender appender(b);
         std::streambuf * buf = is.rdbuf();
         for(int c = buf->sgetc(); appender.get_count() < limit; c = buf->snextc() ) {
@@ -1533,13 +1618,14 @@ operator>>(std::istream& is, dynamic_bitset<Block, Alloc>& b)
                 break; // non digit character
 
             else {
-                try {
+                BOOST_TRY {
                     appender.do_append(char(c) == '1');
                 }
-                catch(...) {
+                BOOST_CATCH(...) {
                     is.setstate(std::ios::failbit); // assume this can't throw
-                    throw;
+                    BOOST_RETHROW;
                 }
+                BOOST_CATCH_END
             }
 
         } // for
@@ -1568,7 +1654,7 @@ operator>>(std::basic_istream<Ch, Tr>& is, dynamic_bitset<Block, Alloc>& b)
 
     const streamsize w = is.width();
     const size_type limit = 0 < w && static_cast<size_type>(w) < b.max_size()?
-                                         w : b.max_size();
+                                         static_cast<size_type>(w) : b.max_size();
 
     ios_base::iostate err = ios_base::goodbit;
     typename basic_istream<Ch, Tr>::sentry cerberos(is); // skips whitespaces
@@ -1580,7 +1666,7 @@ operator>>(std::basic_istream<Ch, Tr>& is, dynamic_bitset<Block, Alloc>& b)
         const Ch one  = BOOST_DYNAMIC_BITSET_WIDEN_CHAR(fac, '1');
 
         b.clear();
-        try {
+        BOOST_TRY {
             typename bitset_type::bit_appender appender(b);
             basic_streambuf <Ch, Tr> * buf = is.rdbuf();
             typename Tr::int_type c = buf->sgetc();
@@ -1603,7 +1689,7 @@ operator>>(std::basic_istream<Ch, Tr>& is, dynamic_bitset<Block, Alloc>& b)
 
             } // for
         }
-        catch (...) {
+        BOOST_CATCH (...) {
             // catches from stream buf, or from vector:
             //
             // bits_stored bits have been extracted and stored, and
@@ -1611,13 +1697,15 @@ operator>>(std::basic_istream<Ch, Tr>& is, dynamic_bitset<Block, Alloc>& b)
             // append to the underlying vector (out of memory)
 
             bool rethrow = false;   // see std 27.6.1.1/4
-            try { is.setstate(ios_base::badbit); }
-            catch(...) { rethrow = true; }
+            BOOST_TRY { is.setstate(ios_base::badbit); }
+            BOOST_CATCH(...) { rethrow = true; }
+            BOOST_CATCH_END
 
             if (rethrow)
-                throw;
+                BOOST_RETHROW;
 
         }
+        BOOST_CATCH_END
     }
 
     is.width(0);
@@ -1694,7 +1782,7 @@ inline typename dynamic_bitset<Block, Allocator>::size_type
 dynamic_bitset<Block, Allocator>::calc_num_blocks(size_type num_bits)
 {
     return num_bits / bits_per_block
-           + static_cast<int>( num_bits % bits_per_block != 0 );
+           + static_cast<size_type>( num_bits % bits_per_block != 0 );
 }
 
 // gives a reference to the highest block