fixed adding file problem
[c11concurrency-benchmarks.git] / gdax-orderbook-hpp / demo / dependencies / libcds-2.3.2 / cds / container / details / bronson_avltree_base.h
1 /*
2     This file is a part of libcds - Concurrent Data Structures library
3
4     (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2017
5
6     Source code repo: http://github.com/khizmax/libcds/
7     Download: http://sourceforge.net/projects/libcds/files/
8
9     Redistribution and use in source and binary forms, with or without
10     modification, are permitted provided that the following conditions are met:
11
12     * Redistributions of source code must retain the above copyright notice, this
13       list of conditions and the following disclaimer.
14
15     * Redistributions in binary form must reproduce the above copyright notice,
16       this list of conditions and the following disclaimer in the documentation
17       and/or other materials provided with the distribution.
18
19     THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
20     AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
21     IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
22     DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
23     FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
24     DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
25     SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
26     CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
27     OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
28     OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
29 */
30
31 #ifndef CDSLIB_CONTAINER_DETAILS_BRONSON_AVLTREE_BASE_H
32 #define CDSLIB_CONTAINER_DETAILS_BRONSON_AVLTREE_BASE_H
33
34 #include <cds/container/details/base.h>
35 #include <cds/opt/compare.h>
36 #include <cds/urcu/options.h>
37 #include <cds/sync/spinlock.h>
38 #include <cds/sync/injecting_monitor.h>
39
40 namespace cds { namespace container {
41
42     /// BronsonAVLTree related declarations
43     namespace bronson_avltree {
44
45         template <typename Key, typename T, typename SyncMonitor >
46         struct node;
47
48         //@cond
49         template <typename Node, typename T, typename SyncMonitor>
50         struct link_node
51         {
52             typedef Node     node_type;
53             typedef T        mapped_type;
54             typedef uint32_t version_type;  ///< version type (internal)
55
56             enum
57             {
58                 shrinking = 1,
59                 unlinked = 2,
60                 version_flags = shrinking | unlinked
61                 // the rest is version counter
62             };
63
64             atomics::atomic< int >          m_nHeight;  ///< Node height
65             atomics::atomic<version_type>   m_nVersion; ///< Version bits
66             atomics::atomic<node_type *>    m_pParent;  ///< Parent node
67             atomics::atomic<node_type *>    m_pLeft;    ///< Left child
68             atomics::atomic<node_type *>    m_pRight;   ///< Right child
69             typename SyncMonitor::node_injection m_SyncMonitorInjection;    ///< @ref cds_sync_monitor "synchronization monitor" injected data
70             atomics::atomic<mapped_type *>  m_pValue;   ///< Value
71
72         public:
73             link_node()
74                 : m_nHeight( 0 )
75                 , m_nVersion( 0 )
76                 , m_pParent( nullptr )
77                 , m_pLeft( nullptr )
78                 , m_pRight( nullptr )
79             {
80                 m_pValue.store( nullptr, atomics::memory_order_release );
81             }
82
83             link_node( int nHeight, version_type version, node_type * pParent, node_type * pLeft, node_type * pRight )
84                 : m_nHeight( nHeight )
85                 , m_nVersion( version )
86                 , m_pParent( pParent )
87                 , m_pLeft( pLeft )
88                 , m_pRight( pRight )
89             {
90                 m_pValue.store( nullptr, atomics::memory_order_release );
91             }
92
93             node_type * parent( atomics::memory_order order ) const
94             {
95                 return m_pParent.load( order );
96             }
97
98             void parent( node_type * p, atomics::memory_order order )
99             {
100                 m_pParent.store( p, order );
101             }
102
103             node_type * child( int nDirection, atomics::memory_order order ) const
104             {
105                 assert( nDirection != 0 );
106                 return nDirection < 0 ? m_pLeft.load( order ) : m_pRight.load( order );
107             }
108
109             void child( node_type * pChild, int nDirection, atomics::memory_order order )
110             {
111                 assert( nDirection != 0 );
112                 if ( nDirection < 0 )
113                     m_pLeft.store( pChild, order );
114                 else
115                     m_pRight.store( pChild, order );
116             }
117
118             version_type version( atomics::memory_order order ) const
119             {
120                 return m_nVersion.load( order );
121             }
122
123             void version( version_type ver, atomics::memory_order order )
124             {
125                 m_nVersion.store( ver, order );
126             }
127
128             void exchange_version( version_type ver, atomics::memory_order order )
129             {
130                 m_nVersion.exchange( ver, order );
131             }
132
133             int height( atomics::memory_order order ) const
134             {
135                 return m_nHeight.load( order );
136             }
137
138             void height( int h, atomics::memory_order order )
139             {
140                 m_nHeight.store( h, order );
141             }
142
143             template <typename BackOff>
144             void wait_until_shrink_completed( atomics::memory_order order ) const
145             {
146                 BackOff bkoff;
147                 while ( is_shrinking( order ))
148                     bkoff();
149             }
150
151             bool is_unlinked( atomics::memory_order order ) const
152             {
153                 return m_nVersion.load( order ) == unlinked;
154             }
155
156             bool is_shrinking( atomics::memory_order order ) const
157             {
158                 return (m_nVersion.load( order ) & shrinking) != 0;
159             }
160
161             mapped_type * value( atomics::memory_order order ) const
162             {
163                 return m_pValue.load( order );
164             }
165
166             bool is_valued( atomics::memory_order order ) const
167             {
168                 return value( order ) != nullptr;
169             }
170         };
171         //@endcond
172
173         /// BronsonAVLTree internal node
174         template <typename Key, typename T, typename SyncMonitor >
175         struct node<Key, T*, SyncMonitor>: public link_node< node<Key, T*, SyncMonitor>, T, SyncMonitor >
176         {
177             //@cond
178             typedef link_node< node<Key, T*, SyncMonitor>, T, SyncMonitor > base_class;
179             //@endcond
180
181             typedef Key key_type;       ///< key type
182             typedef T   mapped_type;    ///< value type
183             //@cond
184             typedef typename base_class::version_type version_type;
185             //@endcond
186
187             key_type const                  m_key;      ///< Key
188             node *                          m_pNextRemoved; ///< thread-local list of removed node
189
190         public:
191             //@cond
192             template <typename Q>
193             node( Q&& key )
194                 : base_class()
195                 , m_key( std::forward<Q>( key ))
196                 , m_pNextRemoved( nullptr )
197             {}
198
199             template <typename Q>
200             node( Q&& key, int nHeight, version_type version, node * pParent, node * pLeft, node * pRight )
201                 : base_class( nHeight, version, pParent, pLeft, pRight )
202                 , m_key( std::forward<Q>( key ))
203                 , m_pNextRemoved( nullptr )
204             {}
205             //@endcond
206         };
207
208         /// BronsonAVLTreeMap internal statistics
209         template <typename Counter = cds::atomicity::event_counter>
210         struct stat {
211             typedef Counter   event_counter; ///< Event counter type
212
213             event_counter   m_nFindSuccess; ///< Count of success \p find() call
214             event_counter   m_nFindFailed;  ///< Count of failed \p find() call
215             event_counter   m_nFindRetry;   ///< Count of retries during \p find()
216             event_counter   m_nFindWaitShrinking;   ///< Count of waiting until shrinking completed duting \p find() call
217
218             event_counter   m_nInsertSuccess;       ///< Count of inserting data node
219             event_counter   m_nInsertFailed;        ///< Count of insert failures
220             event_counter   m_nRelaxedInsertFailed; ///< Count of false creating of data nodes (only if @ref bronson_avltree::relaxed_insert "relaxed insertion" is enabled)
221             event_counter   m_nInsertRetry;         ///< Count of insert retries via concurrent operations
222             event_counter   m_nUpdateWaitShrinking; ///< Count of waiting until shrinking completed during \p update() call
223             event_counter   m_nUpdateRetry;         ///< Count of update retries via concurrent operations
224             event_counter   m_nUpdateRootWaitShrinking;  ///< Count of waiting until root shrinking completed duting \p update() call
225             event_counter   m_nUpdateSuccess;       ///< Count of updating data node
226             event_counter   m_nUpdateUnlinked;      ///< Count of attempts to update unlinked node
227             event_counter   m_nDisposedNode;        ///< Count of disposed node
228             event_counter   m_nDisposedValue;       ///< Count of disposed value
229             event_counter   m_nExtractedValue;      ///< Count of extracted value
230             event_counter   m_nRemoveSuccess;       ///< Count of successfully \p erase() call
231             event_counter   m_nRemoveFailed;        ///< Count of failed \p erase() call
232             event_counter   m_nRemoveRetry;         ///< Count o erase/extract retries
233             event_counter   m_nExtractSuccess;      ///< Count of successfully \p extract() call
234             event_counter   m_nExtractFailed;       ///< Count of failed \p extract() call
235             event_counter   m_nRemoveWaitShrinking; ///< ount of waiting until shrinking completed during \p erase() or \p extract() call
236             event_counter   m_nRemoveRootWaitShrinking;  ///< Count of waiting until root shrinking completed duting \p erase() or \p extract() call
237             event_counter   m_nMakeRoutingNode;     ///< How many nodes were converted to routing (valueless) nodes
238
239             event_counter   m_nRightRotation;       ///< Count of single right rotation
240             event_counter   m_nLeftRotation;        ///< Count of single left rotation
241             event_counter   m_nLeftRightRotation;   ///< Count of double left-over-right rotation
242             event_counter   m_nRightLeftRotation;   ///< Count of double right-over-left rotation
243
244             event_counter   m_nRotateAfterRightRotation; ///< Count of rotation required after single right rotation
245             event_counter   m_nRemoveAfterRightRotation; ///< Count of removal required after single right rotation
246             event_counter   m_nDamageAfterRightRotation; ///< Count of damaged node after single right rotation
247
248             event_counter   m_nRotateAfterLeftRotation;  ///< Count of rotation required after signle left rotation
249             event_counter   m_nRemoveAfterLeftRotation;  ///< Count of removal required after single left rotation
250             event_counter   m_nDamageAfterLeftRotation;  ///< Count of damaged node after single left rotation
251
252             event_counter   m_nRotateAfterRLRotation;    ///< Count of rotation required after right-over-left rotation
253             event_counter   m_nRemoveAfterRLRotation;    ///< Count of removal required after right-over-left rotation
254             event_counter   m_nRotateAfterLRRotation;    ///< Count of rotation required after left-over-right rotation
255             event_counter   m_nRemoveAfterLRRotation;    ///< Count of removal required after left-over-right rotation
256
257             event_counter   m_nInsertRebalanceReq;  ///< Count of rebalance required after inserting
258             event_counter   m_nRemoveRebalanceReq;  ///< Count of rebalance required after removing
259
260             //@cond
261             void onFindSuccess()        { ++m_nFindSuccess      ; }
262             void onFindFailed()         { ++m_nFindFailed       ; }
263             void onFindRetry()          { ++m_nFindRetry        ; }
264             void onFindWaitShrinking()  { ++m_nFindWaitShrinking; }
265
266             void onInsertSuccess()          { ++m_nInsertSuccess; }
267             void onInsertFailed()           { ++m_nInsertFailed; }
268             void onRelaxedInsertFailed()    { ++m_nRelaxedInsertFailed; }
269             void onInsertRetry()            { ++m_nInsertRetry      ; }
270             void onUpdateWaitShrinking()    { ++m_nUpdateWaitShrinking; }
271             void onUpdateRetry()            { ++m_nUpdateRetry; }
272             void onUpdateRootWaitShrinking() { ++m_nUpdateRootWaitShrinking; }
273             void onUpdateSuccess()          { ++m_nUpdateSuccess;  }
274             void onUpdateUnlinked()         { ++m_nUpdateUnlinked; }
275             void onDisposeNode()            { ++m_nDisposedNode; }
276             void onDisposeValue()           { ++m_nDisposedValue; }
277             void onExtractValue()           { ++m_nExtractedValue; }
278             void onRemove(bool bSuccess)
279             {
280                 if ( bSuccess )
281                     ++m_nRemoveSuccess;
282                 else
283                     ++m_nRemoveFailed;
284             }
285             void onExtract( bool bSuccess )
286             {
287                 if ( bSuccess )
288                     ++m_nExtractSuccess;
289                 else
290                     ++m_nExtractFailed;
291             }
292             void onRemoveRetry()            { ++m_nRemoveRetry; }
293             void onRemoveWaitShrinking()    { ++m_nRemoveWaitShrinking; }
294             void onRemoveRootWaitShrinking() { ++m_nRemoveRootWaitShrinking; }
295             void onMakeRoutingNode()        { ++m_nMakeRoutingNode; }
296
297             void onRotateRight()            { ++m_nRightRotation; }
298             void onRotateLeft()             { ++m_nLeftRotation; }
299             void onRotateRightOverLeft()    { ++m_nRightLeftRotation; }
300             void onRotateLeftOverRight()    { ++m_nLeftRightRotation; }
301
302             void onRotateAfterRightRotation() { ++m_nRotateAfterRightRotation; }
303             void onRemoveAfterRightRotation() { ++m_nRemoveAfterRightRotation; }
304             void onDamageAfterRightRotation() { ++m_nDamageAfterRightRotation; }
305
306             void onRotateAfterLeftRotation()  { ++m_nRotateAfterLeftRotation; }
307             void onRemoveAfterLeftRotation()  { ++m_nRemoveAfterLeftRotation; }
308             void onDamageAfterLeftRotation()  { ++m_nDamageAfterLeftRotation; }
309
310             void onRotateAfterRLRotation()    { ++m_nRotateAfterRLRotation; }
311             void onRemoveAfterRLRotation()    { ++m_nRemoveAfterRLRotation; }
312             void onRotateAfterLRRotation()    { ++m_nRotateAfterLRRotation; }
313             void onRemoveAfterLRRotation()    { ++m_nRemoveAfterLRRotation; }
314
315             void onInsertRebalanceRequired() { ++m_nInsertRebalanceReq; }
316             void onRemoveRebalanceRequired() { ++m_nRemoveRebalanceReq; }
317             //@endcond
318         };
319
320         /// BronsonAVLTreeMap empty statistics
321         struct empty_stat {
322             //@cond
323             void onFindSuccess()        const {}
324             void onFindFailed()         const {}
325             void onFindRetry()          const {}
326             void onFindWaitShrinking()  const {}
327
328             void onInsertSuccess()          const {}
329             void onInsertFailed()           const {}
330             void onRelaxedInsertFailed()    const {}
331             void onInsertRetry()            const {}
332             void onUpdateWaitShrinking()    const {}
333             void onUpdateRetry()            const {}
334             void onUpdateRootWaitShrinking() const {}
335             void onUpdateSuccess()          const {}
336             void onUpdateUnlinked()         const {}
337             void onDisposeNode()            const {}
338             void onDisposeValue()           const {}
339             void onExtractValue()           const {}
340             void onRemove(bool /*bSuccess*/) const {}
341             void onExtract(bool /*bSuccess*/) const {}
342             void onRemoveRetry()            const {}
343             void onRemoveWaitShrinking()    const {}
344             void onRemoveRootWaitShrinking() const {}
345             void onMakeRoutingNode()        const {}
346
347             void onRotateRight()            const {}
348             void onRotateLeft()             const {}
349             void onRotateRightOverLeft()    const {}
350             void onRotateLeftOverRight()    const {}
351
352             void onRotateAfterRightRotation() const {}
353             void onRemoveAfterRightRotation() const {}
354             void onDamageAfterRightRotation() const {}
355
356             void onRotateAfterLeftRotation()  const {}
357             void onRemoveAfterLeftRotation()  const {}
358             void onDamageAfterLeftRotation()  const {}
359
360             void onRotateAfterRLRotation()    const {}
361             void onRemoveAfterRLRotation()    const {}
362             void onRotateAfterLRRotation()    const {}
363             void onRemoveAfterLRRotation()    const {}
364
365             void onInsertRebalanceRequired() const {}
366             void onRemoveRebalanceRequired() const {}
367             //@endcond
368         };
369
370         /// Option to allow relaxed insert into \ref cds_container_BronsonAVLTreeMap_rcu "Bronson et al AVL-tree"
371         /**
372             By default, this option is disabled and the new node is created under its parent lock.
373             In this case, it is guaranteed the new node will be attached to its parent.
374             On the other hand, constructing of the new node can be too complex to make it under the lock,
375             that can lead to lock contention.
376
377             When this option is enabled, the new node is created before locking the parent node.
378             After that, the parent is locked and checked whether the new node can be attached to the parent.
379             In this case, false node creating can be performed, but locked section can be significantly small.
380         */
381         template <bool Enable>
382         struct relaxed_insert {
383             //@cond
384             template <typename Base> struct pack : public Base
385             {
386                 enum { relaxed_insert = Enable };
387             };
388             //@endcond
389         };
390
391         /// \p BronsonAVLTreeMap traits
392         /**
393             Note that there are two main specialization of Bronson et al AVL-tree:
394             - \ref cds_container_BronsonAVLTreeMap_rcu_ptr "pointer-oriented" - the tree node stores an user-provided pointer to value
395             - \ref cds_container_BronsonAVLTreeMap_rcu "data-oriented" - the tree node contains a copy of values
396
397             Depends on tree specialization, different traits member can be used.
398         */
399         struct traits
400         {
401             /// Key comparison functor
402             /**
403                 No default functor is provided. If the option is not specified, the \p less is used.
404
405                 See \p cds::opt::compare option description for functor interface.
406
407                 You should provide \p compare or \p less functor.
408             */
409             typedef opt::none                       compare;
410
411             /// Specifies binary predicate used for key compare.
412             /**
413                 See \p cds::opt::less option description for predicate interface.
414
415                 You should provide \p compare or \p less functor.
416             */
417             typedef opt::none                       less;
418
419             /// Allocator for internal node
420             typedef CDS_DEFAULT_ALLOCATOR           node_allocator;
421
422             /// Allocator for node's value (not used in \p BronsonAVLTreeMap<RCU, Key, T*, Traits> specialisation)
423             typedef CDS_DEFAULT_ALLOCATOR           allocator;
424
425             /// Disposer (only for pointer-oriented tree specialization)
426             /**
427                 The functor used for dispose removed values.
428                 The user-provided disposer is used only for pointer-oriented tree specialization
429                 like \p BronsonAVLTreeMap<GC, Key, T*, Traits>. When the node becomes the routing node without value,
430                 the disposer will be called to signal that the memory for the value can be safely freed.
431                 Default is \ref cds::intrusive::opt::delete_disposer "cds::container::opt::v::delete_disposer<>" which calls \p delete operator.
432             */
433             typedef opt::v::delete_disposer<>       disposer;
434
435             /// @ref cds_sync_monitor "Synchronization monitor" type for node-level locking
436             typedef cds::sync::injecting_monitor<cds::sync::spin>  sync_monitor;
437
438             /// Enable relaxed insertion.
439             /**
440                 About relaxed insertion see \p bronson_avltree::relaxed_insert option.
441                 By default, this option is disabled.
442             */
443             static bool const relaxed_insert = false;
444
445             /// Item counter
446             /**
447                 The type for item counter, by default it is disabled (\p atomicity::empty_item_counter).
448                 To enable it use \p atomicity::item_counter or \p atomicity::cache_friendly_item_counter.
449             */
450             typedef atomicity::empty_item_counter     item_counter;
451
452             /// C++ memory ordering model
453             /**
454                 List of available memory ordering see \p opt::memory_model
455             */
456             typedef opt::v::relaxed_ordering        memory_model;
457
458             /// Internal statistics
459             /**
460                 By default, internal statistics is disabled (\p bronson_avltree::empty_stat).
461                 To enable it use \p bronson_avltree::stat.
462             */
463             typedef empty_stat                      stat;
464
465             /// Back-off strategy
466             typedef cds::backoff::empty             back_off;
467
468             /// RCU deadlock checking policy
469             /**
470                 List of available options see \p opt::rcu_check_deadlock
471             */
472             typedef cds::opt::v::rcu_throw_deadlock      rcu_check_deadlock;
473         };
474
475         /// Metafunction converting option list to BronsonAVLTreeMap traits
476         /**
477             Note that there are two main specialization of Bronson et al AVL-tree:
478             - \ref cds_container_BronsonAVLTreeMap_rcu_ptr "pointer-oriented" - the tree node stores an user-provided pointer to value
479             - \ref cds_container_BronsonAVLTreeMap_rcu "data-oriented" - the tree node contains a copy of values
480
481             Depends on tree specialization, different options can be specified.
482
483             \p Options are:
484             - \p opt::compare - key compare functor. No default functor is provided.
485                 If the option is not specified, \p %opt::less is used.
486             - \p opt::less - specifies binary predicate used for key compare. At least \p %opt::compare or \p %opt::less should be defined.
487             - \p opt::node_allocator - the allocator for internal nodes. Default is \ref CDS_DEFAULT_ALLOCATOR.
488             - \p opt::allocator - the allocator for node's value. Default is \ref CDS_DEFAULT_ALLOCATOR.
489                 This option is not used in \p BronsonAVLTreeMap<RCU, Key, T*, Traits> specialisation
490             - \p cds::intrusive::opt::disposer - the functor used for dispose removed values.
491                 The user-provided disposer is used only for pointer-oriented tree specialization
492                 like \p BronsonAVLTreeMap<GC, Key, T*, Traits>. When the node becomes the rounting node without value,
493                 the disposer will be called to signal that the memory for the value can be safely freed.
494                 Default is \p cds::intrusive::opt::delete_disposer which calls \p delete operator.
495                 Due the nature of GC schema the disposer may be called asynchronously.
496             - \p opt::sync_monitor -  @ref cds_sync_monitor "synchronization monitor" type for node-level locking,
497                 default is \p cds::sync::injecting_monitor<cds::sync::spin>
498             - \p bronson_avltree::relaxed_insert - enable (\p true) or disable (\p false, the default)
499                 @ref bronson_avltree::relaxed_insert "relaxed insertion"
500             - \p opt::item_counter - the type of item counting feature, by default it is disabled (\p atomicity::empty_item_counter)
501                 To enable it use \p atomicity::item_counter or \p atomicity::cache_friendly_item_counter
502             - \p opt::memory_model - C++ memory ordering model. Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
503                 or \p opt::v::sequential_consistent (sequentially consisnent memory model).
504             - \p opt::stat - internal statistics, by default it is disabled (\p bronson_avltree::empty_stat)
505                 To enable statistics use \p \p bronson_avltree::stat
506             - \p opt::backoff - back-off strategy, by default no strategy is used (\p cds::backoff::empty)
507             - \p opt::rcu_check_deadlock - a deadlock checking policy for RCU-based tree, default is \p opt::v::rcu_throw_deadlock
508         */
509         template <typename... Options>
510         struct make_traits {
511 #   ifdef CDS_DOXYGEN_INVOKED
512             typedef implementation_defined type ;   ///< Metafunction result
513 #   else
514             typedef typename cds::opt::make_options<
515                 typename cds::opt::find_type_traits< traits, Options... >::type
516                 ,Options...
517             >::type   type;
518 #   endif
519         };
520     } // namespace bronson_avltree
521
522     // Forwards
523     template < class GC, typename Key, typename T, class Traits = bronson_avltree::traits >
524     class BronsonAVLTreeMap;
525
526 }} // namespace cds::container
527
528 #endif // #ifndef CDSLIB_CONTAINER_DETAILS_BRONSON_AVLTREE_BASE_H