[Boost-commit] svn:boost r58619 - in trunk: boost/circular_buffer libs/circular_buffer/doc libs/circular_buffer/test

Subject: [Boost-commit] svn:boost r58619 - in trunk: boost/circular_buffer libs/circular_buffer/doc libs/circular_buffer/test
From: jano_gaspar_at_[hidden]
Date: 2010-01-01 17:23:29

Author: jano_gaspar
Date: 2010-01-01 17:23:27 EST (Fri, 01 Jan 2010)
New Revision: 58619
URL: http://svn.boost.org/trac/boost/changeset/58619

Log:
circular_buffer: constant complexity of clear method and destructor
Added:
   trunk/libs/circular_buffer/test/constant_erase_test.cpp
      - copied, changed from r57296, /trunk/libs/circular_buffer/test/erase_begin_end.cpp
Removed:
   trunk/libs/circular_buffer/test/erase_begin_end.cpp
Text files modified: 
   trunk/boost/circular_buffer/base.hpp                    |    36 +++++++++++++++++------                 
   trunk/boost/circular_buffer/space_optimized.hpp         |    20 +++++++------                           
   trunk/libs/circular_buffer/doc/circular_buffer.html     |     8 ++++-                                   
   trunk/libs/circular_buffer/test/Jamfile.v2              |     2                                         
   trunk/libs/circular_buffer/test/constant_erase_test.cpp |    60 ++++++++++++++++++++++++++++++++++++++- 
   5 files changed, 102 insertions(+), 24 deletions(-)

Modified: trunk/boost/circular_buffer/base.hpp
==============================================================================
--- trunk/boost/circular_buffer/base.hpp	(original)
+++ trunk/boost/circular_buffer/base.hpp	2010-01-01 17:23:27 EST (Fri, 01 Jan 2010)
@@ -394,7 +394,7 @@
              Does not invalidate any iterators.
         \par Complexity
              Constant (in the size of the <code>circular_buffer</code>).
-        \sa <code>operator[]</code>
+        \sa <code>\link operator[](size_type) operator[] \endlink</code>
     */
     reference at(size_type index) {
         check_position(index);
@@ -1166,7 +1166,7 @@
              Invalidates all iterators pointing to the <code>circular_buffer</code> (including iterators equal to
              <code>end()</code>).
         \par Complexity
-             Linear (in the size of the <code>circular_buffer</code>).
+             Constant (in the size of the <code>circular_buffer</code>) for scalar types; linear for other types.
         \sa <code>clear()</code>
     */
     ~circular_buffer() {
@@ -1232,7 +1232,8 @@
              <code>end()</code>).
         \par Complexity
              Linear (in the <code>n</code>).
-        \sa <code>operator=</code>, <code>\link assign(capacity_type, size_type, param_value_type)
+        \sa <code>\link operator=(const circular_buffer&) operator=\endlink</code>,
+            <code>\link assign(capacity_type, size_type, param_value_type)
             assign(capacity_type, size_type, const_reference)\endlink</code>,
             <code>assign(InputIterator, InputIterator)</code>,
             <code>assign(capacity_type, InputIterator, InputIterator)</code>
@@ -1261,8 +1262,9 @@
              <code>end()</code>).
         \par Complexity
              Linear (in the <code>n</code>).
-        \sa <code>operator=</code>, <code>\link assign(size_type, param_value_type)
-            assign(size_type, const_reference)\endlink</code>, <code>assign(InputIterator, InputIterator)</code>,
+        \sa <code>\link operator=(const circular_buffer&) operator=\endlink</code>,
+            <code>\link assign(size_type, param_value_type) assign(size_type, const_reference)\endlink</code>,
+            <code>assign(InputIterator, InputIterator)</code>,
             <code>assign(capacity_type, InputIterator, InputIterator)</code>
     */
     void assign(capacity_type buffer_capacity, size_type n, param_value_type item) {
@@ -1292,8 +1294,8 @@
              <code>end()</code>).
         \par Complexity
              Linear (in the <code>std::distance(first, last)</code>).
-        \sa <code>operator=</code>, <code>\link assign(size_type, param_value_type)
-            assign(size_type, const_reference)\endlink</code>,
+        \sa <code>\link operator=(const circular_buffer&) operator=\endlink</code>,
+            <code>\link assign(size_type, param_value_type) assign(size_type, const_reference)\endlink</code>,
             <code>\link assign(capacity_type, size_type, param_value_type)
             assign(capacity_type, size_type, const_reference)\endlink</code>,
             <code>assign(capacity_type, InputIterator, InputIterator)</code>
@@ -1331,8 +1333,8 @@
              Linear (in <code>std::distance(first, last)</code>; in
              <code>min[capacity, std::distance(first, last)]</code> if the <code>InputIterator</code> is a
              <a href="http://www.sgi.com/tech/stl/RandomAccessIterator.html">RandomAccessIterator</a>).
-        \sa <code>operator=</code>, <code>\link assign(size_type, param_value_type)
-            assign(size_type, const_reference)\endlink</code>,
+        \sa <code>\link operator=(const circular_buffer&) operator=\endlink</code>,
+            <code>\link assign(size_type, param_value_type) assign(size_type, const_reference)\endlink</code>,
             <code>\link assign(capacity_type, size_type, param_value_type)
             assign(capacity_type, size_type, const_reference)\endlink</code>,
             <code>assign(InputIterator, InputIterator)</code>
@@ -2024,7 +2026,7 @@
              Invalidates all iterators pointing to the <code>circular_buffer</code> (except iterators equal to
              <code>end()</code>).
         \par Complexity
-             Linear (in the size of the <code>circular_buffer</code>).
+             Constant (in the size of the <code>circular_buffer</code>) for scalar types; linear for other types.
         \sa <code>~circular_buffer()</code>, <code>erase(iterator)</code>, <code>erase(iterator, iterator)</code>,
             <code>rerase(iterator)</code>, <code>rerase(iterator, iterator)</code>,
             <code>erase_begin(size_type)</code>, <code>erase_end(size_type)</code>
@@ -2134,6 +2136,20 @@
 
     //! Destroy the whole content of the circular buffer.
     void destroy_content() {
+#if BOOST_CB_ENABLE_DEBUG
+        destroy_content(false_type());
+#else
+        destroy_content(is_scalar<value_type>());
+#endif
+    }
+
+    //! Specialized destroy_content method.
+    void destroy_content(const true_type&) {
+        m_first = add(m_first, size());
+    }
+
+    //! Specialized destroy_content method.
+    void destroy_content(const false_type&) {
         for (size_type ii = 0; ii < size(); ++ii, increment(m_first))
             destroy_item(m_first);
     }

Modified: trunk/boost/circular_buffer/space_optimized.hpp
==============================================================================
--- trunk/boost/circular_buffer/space_optimized.hpp	(original)
+++ trunk/boost/circular_buffer/space_optimized.hpp	2010-01-01 17:23:27 EST (Fri, 01 Jan 2010)
@@ -189,9 +189,9 @@
         \par Complexity
              Linear (in <code>min[size(), capacity_ctrl.%capacity()]</code>).
         \note To explicitly clear the extra allocated memory use the <b>shrink-to-fit</b> technique:<br><br>
-              <code>boost::%circular_buffer_space_optimized\<int\> cb(1000);<br>
+              <code>%boost::%circular_buffer_space_optimized\<int\> cb(1000);<br>
               ...<br>
-              boost::%circular_buffer_space_optimized\<int\>(cb).swap(cb);</code><br><br>
+              %boost::%circular_buffer_space_optimized\<int\>(cb).swap(cb);</code><br><br>
               For more information about the shrink-to-fit technique in STL see
               <a href="http://www.gotw.ca/gotw/054.htm">http://www.gotw.ca/gotw/054.htm>.
         \sa <code>rset_capacity(const capacity_type&)</code>,
@@ -571,7 +571,8 @@
              equal to <code>end()</code>).
         \par Complexity
              Linear (in the <code>n</code>).
-        \sa <code>operator=</code>, <code>\link assign(capacity_type, size_type, param_value_type)
+        \sa <code>\link operator=(const circular_buffer_space_optimized&) operator=\endlink</code>,
+            <code>\link assign(capacity_type, size_type, param_value_type)
             assign(capacity_type, size_type, const_reference)\endlink</code>,
             <code>assign(InputIterator, InputIterator)</code>,
             <code>assign(capacity_type, InputIterator, InputIterator)</code>
@@ -603,8 +604,9 @@
              equal to <code>end()</code>).
         \par Complexity
              Linear (in the <code>n</code>).
-        \sa <code>operator=</code>, <code>\link assign(size_type, param_value_type)
-            assign(size_type, const_reference)\endlink</code>, <code>assign(InputIterator, InputIterator)</code>,
+        \sa <code>\link operator=(const circular_buffer_space_optimized&) operator=\endlink</code>,
+            <code>\link assign(size_type, param_value_type) assign(size_type, const_reference)\endlink</code>,
+            <code>assign(InputIterator, InputIterator)</code>,
             <code>assign(capacity_type, InputIterator, InputIterator)</code>
     */
     void assign(capacity_type capacity_ctrl, size_type n, param_value_type item) {
@@ -636,8 +638,8 @@
              equal to <code>end()</code>).
         \par Complexity
              Linear (in the <code>std::distance(first, last)</code>).
-        \sa <code>operator=</code>, <code>\link assign(size_type, param_value_type)
-            assign(size_type, const_reference)\endlink</code>,
+        \sa <code>\link operator=(const circular_buffer_space_optimized&) operator=\endlink</code>,
+            <code>\link assign(size_type, param_value_type) assign(size_type, const_reference)\endlink</code>,
             <code>\link assign(capacity_type, size_type, param_value_type)
             assign(capacity_type, size_type, const_reference)\endlink</code>,
             <code>assign(capacity_type, InputIterator, InputIterator)</code>
@@ -678,8 +680,8 @@
              Linear (in <code>std::distance(first, last)</code>; in
              <code>min[capacity_ctrl.%capacity(), std::distance(first, last)]</code> if the <code>InputIterator</code>
              is a RandomAccessIterator).
-        \sa <code>operator=</code>, <code>\link assign(size_type, param_value_type)
-            assign(size_type, const_reference)\endlink</code>,
+        \sa <code>\link operator=(const circular_buffer_space_optimized&) operator=\endlink</code>,
+            <code>\link assign(size_type, param_value_type) assign(size_type, const_reference)\endlink</code>,
             <code>\link assign(capacity_type, size_type, param_value_type)
             assign(capacity_type, size_type, const_reference)\endlink</code>,
             <code>assign(InputIterator, InputIterator)</code>

Modified: trunk/libs/circular_buffer/doc/circular_buffer.html
==============================================================================
--- trunk/libs/circular_buffer/doc/circular_buffer.html	(original)
+++ trunk/libs/circular_buffer/doc/circular_buffer.html	2010-01-01 17:23:27 EST (Fri, 01 Jan 2010)
@@ -1609,7 +1609,7 @@
                 <b>Complexity:</b>
               </dt>
               <dd>
-                Linear (in the size of the <code>circular_buffer</code>).
+                Constant (in the size of the <code>circular_buffer</code>) for scalar types; linear for other types.
               </dd>
             </dl>
             <dl>
@@ -6735,7 +6735,7 @@
                 <b>Complexity:</b>
               </dt>
               <dd>
-                Linear (in the size of the <code>circular_buffer</code>).
+                Constant (in the size of the <code>circular_buffer</code>) for scalar types; linear for other types.
               </dd>
             </dl>
             <dl>
@@ -7360,6 +7360,10 @@
           <li>Added methods <code>erase_begin(size_type)</code> and <code>erase_end(size_type)</code> with constant
           complexity for such types of stored elements which do not need an explicit destruction.
           </li>
+          <li>Changed implementation of <code>clear()</code> method and the destructor so their complexity is now
+          constant for such types of stored elements which do not require an explicit destruction (the complexity for
+          other types remains linear).
+          </li>
         </ul>
       </dd>
       <dd>

Modified: trunk/libs/circular_buffer/test/Jamfile.v2
==============================================================================
--- trunk/libs/circular_buffer/test/Jamfile.v2	(original)
+++ trunk/libs/circular_buffer/test/Jamfile.v2	2010-01-01 17:23:27 EST (Fri, 01 Jan 2010)
@@ -25,6 +25,6 @@
   : [ run base_test.cpp : <threading>single : ]
     [ run space_optimized_test.cpp : <threading>single : ]
     [ run soft_iterator_invalidation.cpp : <threading>single : ]
-    [ run erase_begin_end.cpp : <threading>single : ]
+    [ run constant_erase_test.cpp : <threading>single : ]
     [ compile bounded_buffer_comparison.cpp : <threading>multi : ]
   ;

Copied: trunk/libs/circular_buffer/test/constant_erase_test.cpp (from r57296, /trunk/libs/circular_buffer/test/erase_begin_end.cpp)
==============================================================================
--- /trunk/libs/circular_buffer/test/erase_begin_end.cpp	(original)
+++ trunk/libs/circular_buffer/test/constant_erase_test.cpp	2010-01-01 17:23:27 EST (Fri, 01 Jan 2010)
@@ -1,4 +1,4 @@
-// Tests for erase_begin and erase_end methods.
+// Special tests for erase_begin, erase_end and clear methods.
 
 // Copyright (c) 2009 Jan Gaspar
 
@@ -22,6 +22,9 @@
     cb1.push_back(4);
     cb1.push_back(5);
     cb1.push_back(6);
+
+    circular_buffer<int>::pointer p = &cb1[0];
+
     cb1.erase_begin(2);
 
     BOOST_CHECK(cb1.size() == 3);
@@ -31,6 +34,9 @@
 
     cb1.erase_begin(3);
     BOOST_CHECK(cb1.empty());
+    BOOST_CHECK(*p == 2);
+    BOOST_CHECK(*(p + 1) == 3);
+    BOOST_CHECK(*(p + 2) == 4);
 
     cb1.push_back(10);
     cb1.push_back(11);
@@ -75,6 +81,9 @@
     cb1.push_back(4);
     cb1.push_back(5);
     cb1.push_back(6);
+
+    circular_buffer<int>::pointer p = &cb1[3];
+
     cb1.erase_end(2);
 
     BOOST_CHECK(cb1.size() == 3);
@@ -84,6 +93,9 @@
 
     cb1.erase_end(3);
     BOOST_CHECK(cb1.empty());
+    BOOST_CHECK(*p == 5);
+    BOOST_CHECK(*(p - 1) == 4);
+    BOOST_CHECK(*(p - 2) == 3);
 
     cb1.push_back(10);
     cb1.push_back(11);
@@ -119,13 +131,57 @@
     BOOST_CHECK(cb3[2] == 4);
 }
 
+void clear_test() {
+
+    circular_buffer<int> cb1(5);
+    cb1.push_back(1);
+    cb1.push_back(2);
+    cb1.push_back(3);
+    cb1.push_back(4);
+    cb1.push_back(5);
+    cb1.push_back(6);
+
+    circular_buffer<int>::pointer p = &cb1[0];
+
+    cb1.clear();
+
+    BOOST_CHECK(cb1.empty());
+    BOOST_CHECK(*p == 2);
+    BOOST_CHECK(*(p + 1) == 3);
+    BOOST_CHECK(*(p + 2) == 4);
+    BOOST_CHECK(*(p + 3) == 5);
+    BOOST_CHECK(*(p - 1) == 6);
+
+    circular_buffer<InstanceCounter> cb2(5, InstanceCounter());
+
+    BOOST_CHECK(cb2.size() == 5);
+    BOOST_CHECK(InstanceCounter::count() == 5);
+
+    cb2.clear();
+
+    BOOST_CHECK(cb2.empty());
+    BOOST_CHECK(InstanceCounter::count() == 0);
+
+    circular_buffer<MyInteger> cb3(5);
+    cb3.push_back(1);
+    cb3.push_back(2);
+    cb3.push_back(3);
+    cb3.push_back(4);
+    cb3.push_back(5);
+    cb3.push_back(6);
+    cb3.clear();
+
+    BOOST_CHECK(cb3.empty());
+}
+
 // test main
 test_suite* init_unit_test_suite(int /*argc*/, char* /*argv*/[]) {
 
-    test_suite* tests = BOOST_TEST_SUITE("Unit tests for erase_begin/erase_end methods of the circular_buffer.");
+    test_suite* tests = BOOST_TEST_SUITE("Unit tests for erase_begin/end and clear methods of the circular_buffer.");
 
     tests->add(BOOST_TEST_CASE(&erase_begin_test));
     tests->add(BOOST_TEST_CASE(&erase_end_test));
+    tests->add(BOOST_TEST_CASE(&clear_test));
 
     return tests;
 }

Deleted: trunk/libs/circular_buffer/test/erase_begin_end.cpp
==============================================================================
--- trunk/libs/circular_buffer/test/erase_begin_end.cpp	2010-01-01 17:23:27 EST (Fri, 01 Jan 2010)
+++ (empty file)
@@ -1,131 +0,0 @@
-// Tests for erase_begin and erase_end methods.
-
-// Copyright (c) 2009 Jan Gaspar
-
-// Use, modification, and distribution is subject to the Boost Software
-// License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
-// http://www.boost.org/LICENSE_1_0.txt)
-
-#define BOOST_CB_DISABLE_DEBUG
-
-#include "test.hpp"
-
-int MyInteger::ms_exception_trigger = 0;
-int InstanceCounter::ms_count = 0;
-
-void erase_begin_test() {
-
-    circular_buffer<int> cb1(5);
-    cb1.push_back(1);
-    cb1.push_back(2);
-    cb1.push_back(3);
-    cb1.push_back(4);
-    cb1.push_back(5);
-    cb1.push_back(6);
-    cb1.erase_begin(2);
-
-    BOOST_CHECK(cb1.size() == 3);
-    BOOST_CHECK(cb1[0] == 4);
-    BOOST_CHECK(cb1[1] == 5);
-    BOOST_CHECK(cb1[2] == 6);
-
-    cb1.erase_begin(3);
-    BOOST_CHECK(cb1.empty());
-
-    cb1.push_back(10);
-    cb1.push_back(11);
-    cb1.push_back(12);
-
-    BOOST_CHECK(cb1.size() == 3);
-    BOOST_CHECK(cb1[0] == 10);
-    BOOST_CHECK(cb1[1] == 11);
-    BOOST_CHECK(cb1[2] == 12);
-
-    circular_buffer<InstanceCounter> cb2(5, InstanceCounter());
-
-    BOOST_CHECK(cb2.size() == 5);
-    BOOST_CHECK(InstanceCounter::count() == 5);
-
-    cb2.erase_begin(2);
-
-    BOOST_CHECK(cb2.size() == 3);
-    BOOST_CHECK(InstanceCounter::count() == 3);
-
-    circular_buffer<MyInteger> cb3(5);
-    cb3.push_back(1);
-    cb3.push_back(2);
-    cb3.push_back(3);
-    cb3.push_back(4);
-    cb3.push_back(5);
-    cb3.push_back(6);
-    cb3.erase_begin(2);
-
-    BOOST_CHECK(cb3.size() == 3);
-    BOOST_CHECK(cb3[0] == 4);
-    BOOST_CHECK(cb3[1] == 5);
-    BOOST_CHECK(cb3[2] == 6);
-}
-
-void erase_end_test() {
-
-    circular_buffer<int> cb1(5);
-    cb1.push_back(1);
-    cb1.push_back(2);
-    cb1.push_back(3);
-    cb1.push_back(4);
-    cb1.push_back(5);
-    cb1.push_back(6);
-    cb1.erase_end(2);
-
-    BOOST_CHECK(cb1.size() == 3);
-    BOOST_CHECK(cb1[0] == 2);
-    BOOST_CHECK(cb1[1] == 3);
-    BOOST_CHECK(cb1[2] ==4);
-
-    cb1.erase_end(3);
-    BOOST_CHECK(cb1.empty());
-
-    cb1.push_back(10);
-    cb1.push_back(11);
-    cb1.push_back(12);
-
-    BOOST_CHECK(cb1.size() == 3);
-    BOOST_CHECK(cb1[0] == 10);
-    BOOST_CHECK(cb1[1] == 11);
-    BOOST_CHECK(cb1[2] == 12);
-
-    circular_buffer<InstanceCounter> cb2(5, InstanceCounter());
-
-    BOOST_CHECK(cb2.size() == 5);
-    BOOST_CHECK(InstanceCounter::count() == 5);
-
-    cb2.erase_end(2);
-
-    BOOST_CHECK(cb2.size() == 3);
-    BOOST_CHECK(InstanceCounter::count() == 3);
-
-    circular_buffer<MyInteger> cb3(5);
-    cb3.push_back(1);
-    cb3.push_back(2);
-    cb3.push_back(3);
-    cb3.push_back(4);
-    cb3.push_back(5);
-    cb3.push_back(6);
-    cb3.erase_end(2);
-
-    BOOST_CHECK(cb3.size() == 3);
-    BOOST_CHECK(cb3[0] == 2);
-    BOOST_CHECK(cb3[1] == 3);
-    BOOST_CHECK(cb3[2] == 4);
-}
-
-// test main
-test_suite* init_unit_test_suite(int /*argc*/, char* /*argv*/[]) {
-
-    test_suite* tests = BOOST_TEST_SUITE("Unit tests for erase_begin/erase_end methods of the circular_buffer.");
-
-    tests->add(BOOST_TEST_CASE(&erase_begin_test));
-    tests->add(BOOST_TEST_CASE(&erase_end_test));
-
-    return tests;
-}