Fixed rare heap-use-after-free bug

[libcds.git] / cds / intrusive / optimistic_queue.h

diff --git a/cds/intrusive/optimistic_queue.h b/cds/intrusive/optimistic_queue.h
index 50d0641c2a289af8ec7230d1fa57a4c0d0008fb0..461021e92800c28721369d61c75d231602361749 100644 (file)
--- a/cds/intrusive/optimistic_queue.h
+++ b/cds/intrusive/optimistic_queue.h
@@ -1,4 +1,32 @@
-//$$CDS-header$$
+/*
+    This file is a part of libcds - Concurrent Data Structures library
+
+    (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2016
+
+    Source code repo: http://github.com/khizmax/libcds/
+    Download: http://sourceforge.net/projects/libcds/files/
+    
+    Redistribution and use in source and binary forms, with or without
+    modification, are permitted provided that the following conditions are met:
+
+    * Redistributions of source code must retain the above copyright notice, this
+      list of conditions and the following disclaimer.
+
+    * Redistributions in binary form must reproduce the above copyright notice,
+      this list of conditions and the following disclaimer in the documentation
+      and/or other materials provided with the distribution.
+
+    THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+    AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+    IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+    DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
+    FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+    DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
+    SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
+    CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
+    OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+    OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.     
+*/
 
 #ifndef CDSLIB_INTRUSIVE_OPTIMISTIC_QUEUE_H
 #define CDSLIB_INTRUSIVE_OPTIMISTIC_QUEUE_H
@@ -10,7 +38,7 @@
 
 namespace cds { namespace intrusive {
 
-    /// OptimisticQueue related definitions
+    /// \p OptimisticQueue related definitions
     /** @ingroup cds_intrusive_helper
     */
     namespace optimistic_queue {
@@ -60,8 +88,8 @@ namespace cds { namespace intrusive {
         /// Base hook
         /**
             \p Options are:
-            - opt::gc - garbage collector used.
-            - opt::tag - a \ref cds_intrusive_hook_tag "tag"
+            - \p opt::gc - garbage collector used.
+            - \p opt::tag - a \ref cds_intrusive_hook_tag "tag"
         */
         template < typename... Options >
         struct base_hook: public hook< opt::base_hook_tag, Options... >
@@ -73,8 +101,8 @@ namespace cds { namespace intrusive {
             Use \p offsetof macro to define \p MemberOffset
 
             \p Options are:
-            - opt::gc - garbage collector used.
-            - opt::tag - a \ref cds_intrusive_hook_tag "tag"
+            - \p opt::gc - garbage collector used.
+            - \p opt::tag - a \ref cds_intrusive_hook_tag "tag"
         */
         template < size_t MemberOffset, typename... Options >
         struct member_hook: public hook< opt::member_hook_tag, Options... >
@@ -90,8 +118,8 @@ namespace cds { namespace intrusive {
             See \ref node_traits for \p NodeTraits interface description
 
             \p Options are:
-            - opt::gc - garbage collector used.
-            - opt::tag - a \ref cds_intrusive_hook_tag "tag"
+            - \p opt::gc - garbage collector used.
+            - \p opt::tag - a \ref cds_intrusive_hook_tag "tag"
         */
         template <typename NodeTraits, typename... Options >
         struct traits_hook: public hook< opt::traits_hook_tag, Options... >
@@ -146,11 +174,10 @@ namespace cds { namespace intrusive {
         };
         //@endcond
 
-        /// OptimisticQueue internal statistics. May be used for debugging or profiling
+        /// \p OptimisticQueue internal statistics. May be used for debugging or profiling
         /**
             Template argument \p Counter defines type of counter.
-            Default is \p cds::atomicity::event_counter, that is weak, i.e. it is not guaranteed
-            strict event counting.
+            Default is \p cds::atomicity::event_counter.
             You may use stronger type of counter like as \p cds::atomicity::item_counter,
             or even integral type, for example, \p int.
         */
@@ -214,7 +241,7 @@ namespace cds { namespace intrusive {
             //@endcond
         };
 
-        /// Dummy OptimisticQueue statistics - no counting is performed. Support interface like \ref optimistic_queue::stat
+        /// Dummy \p OptimisticQueue statistics - no counting is performed. Support interface like \p optimistic_queue::stat
         struct empty_stat
         {
             //@cond
@@ -235,7 +262,7 @@ namespace cds { namespace intrusive {
             //@endcond
         };
 
-        /// OptimisticQueue default type traits
+        /// \p OptimisticQueue default type traits
         struct traits
         {
             /// Back-off strategy
@@ -419,6 +446,8 @@ namespace cds { namespace intrusive {
             typedef OptimisticQueue< GC2, T2, Traits2 > other   ;   ///< Rebinding result
         };
 
+        static CDS_CONSTEXPR const size_t c_nHazardPtrCount = 5; ///< Count of hazard pointer required for the algorithm
+
     protected:
         //@cond
         typedef typename node_type::atomic_node_ptr atomic_node_ptr;
@@ -442,8 +471,6 @@ namespace cds { namespace intrusive {
         item_counter        m_ItemCounter   ;   ///< Item counter
         stat                m_Stat          ;   ///< Internal statistics
 
-        static CDS_CONSTEXPR const size_t c_nHazardPtrCount = 5 ; ///< Count of hazard pointer required for the algorithm
-
     protected:
         //@cond
         static void clear_links( node_type * pNode )
@@ -618,10 +645,10 @@ namespace cds { namespace intrusive {
             |       ...        |
             \endcode
 
-            \p dequeue function returns Item 2, that becomes new top of queue, and calls
+            \p %dequeue() function returns Item 2, that becomes new top of queue, and calls
             the disposer for Item 1, that was queue's top on function entry.
             Thus, you cannot manually delete item returned because it is still included in
-            item sequence and it has valuable link field that must not be zeroed.
+            the queue and it has valuable link field that must not be zeroed.
             The item may be deleted only in disposer call.
         */
         value_type * dequeue()