cds/container/details/make_skip_list_map.h

   1 //$$CDS-header$$
   2
   3 #ifndef __CDS_CONTAINER_DETAILS_MAKE_SKIP_LIST_MAP_H
   4 #define __CDS_CONTAINER_DETAILS_MAKE_SKIP_LIST_MAP_H
   5
   6 #include <cds/container/skip_list_base.h>
   7 #include <cds/details/binary_functor_wrapper.h>
   8
   9 //@cond
  10 namespace cds { namespace container { namespace details {
  11
  12     template <typename GC, typename K, typename T, typename Traits>
  13     struct make_skip_list_map
  14     {
  15         typedef GC      gc;
  16         typedef K       key_type;
  17         typedef T       mapped_type;
  18         typedef std::pair< key_type const, mapped_type> value_type;
  19         typedef Traits  type_traits;
  20
  21         typedef cds::intrusive::skip_list::node< gc >   intrusive_node_type;
  22         struct node_type: public intrusive_node_type
  23         {
  24             typedef intrusive_node_type                     base_class;
  25             typedef typename base_class::atomic_marked_ptr  atomic_marked_ptr;
  26             typedef value_type                              stored_value_type;
  27
  28             value_type m_Value;
  29             //atomic_marked_ptr m_arrTower[] ;  // allocated together with node_type in single memory block
  30
  31             template <typename Q>
  32             node_type( unsigned int nHeight, atomic_marked_ptr * pTower, Q const& key )
  33                 : m_Value( std::make_pair( key, mapped_type() ))
  34             {
  35                 init_tower( nHeight, pTower );
  36             }
  37
  38             template <typename Q, typename U>
  39             node_type( unsigned int nHeight, atomic_marked_ptr * pTower, Q const& key, U const& val )
  40                 : m_Value( std::make_pair( key, val ))
  41             {
  42                 init_tower( nHeight, pTower );
  43             }
  44
  45 #       ifdef CDS_EMPLACE_SUPPORT
  46             template <typename Q, typename... Args>
  47             node_type( unsigned int nHeight, atomic_marked_ptr * pTower, Q&& key, Args&&... args )
  48                 : m_Value( std::forward<Q>(key), std::move( mapped_type( std::forward<Args>(args)... )))
  49             {
  50                 init_tower( nHeight, pTower );
  51             }
  52 #       endif
  53
  54         private:
  55             node_type() ;   // no default ctor
  56
  57             void init_tower( unsigned int nHeight, atomic_marked_ptr * pTower )
  58             {
  59                 if ( nHeight > 1 ) {
  60                     new (pTower) atomic_marked_ptr[ nHeight - 1 ];
  61                     base_class::make_tower( nHeight, pTower );
  62                 }
  63             }
  64         };
  65
  66         class node_allocator: public skip_list::details::node_allocator< node_type, type_traits>
  67         {
  68             typedef skip_list::details::node_allocator< node_type, type_traits> base_class;
  69         public:
  70             template <typename Q>
  71             node_type * New( unsigned int nHeight, Q const& key )
  72             {
  73                 return base_class::New( nHeight, key );
  74             }
  75             template <typename Q, typename U>
  76             node_type * New( unsigned int nHeight, Q const& key, U const& val )
  77             {
  78                 unsigned char * pMem = base_class::alloc_space( nHeight );
  79                 return new( pMem )
  80                     node_type( nHeight,
  81                         nHeight > 1 ? reinterpret_cast<typename base_class::node_tower_item *>( pMem + base_class::c_nNodeSize )
  82                             : null_ptr<typename base_class::node_tower_item *>(),
  83                         key, val );
  84             }
  85 #       ifdef CDS_EMPLACE_SUPPORT
  86             template <typename... Args>
  87             node_type * New( unsigned int nHeight, Args&&... args )
  88             {
  89                 unsigned char * pMem = base_class::alloc_space( nHeight );
  90                 return new( pMem )
  91                     node_type( nHeight, nHeight > 1 ? reinterpret_cast<typename base_class::node_tower_item *>( pMem + base_class::c_nNodeSize )
  92                         : null_ptr<typename base_class::node_tower_item *>(),
  93                     std::forward<Args>(args)... );
  94             }
  95 #       endif
  96         };
  97
  98         struct node_deallocator {
  99             void operator ()( node_type * pNode )
 100             {
 101                 node_allocator().Delete( pNode );
 102             }
 103         };
 104
 105         typedef skip_list::details::dummy_node_builder<intrusive_node_type> dummy_node_builder;
 106
 107         struct key_accessor
 108         {
 109             key_type const & operator()( node_type const& node ) const
 110             {
 111                 return node.m_Value.first;
 112             }
 113         };
 114         typedef typename opt::details::make_comparator< key_type, type_traits >::type key_comparator;
 115
 116         class intrusive_type_traits: public cds::intrusive::skip_list::make_traits<
 117             cds::opt::type_traits< type_traits >
 118             ,cds::intrusive::opt::hook< intrusive::skip_list::base_hook< cds::opt::gc< gc > > >
 119             ,cds::intrusive::opt::disposer< node_deallocator >
 120             ,cds::intrusive::skip_list::internal_node_builder< dummy_node_builder >
 121             ,cds::opt::compare< cds::details::compare_wrapper< node_type, key_comparator, key_accessor > >
 122         >::type
 123         {};
 124
 125         typedef cds::intrusive::SkipListSet< gc, node_type, intrusive_type_traits>   type;
 126     };
 127
 128 }}} // namespace cds::container::details
 129 //@endcond
 130
 131 #endif // __CDS_CONTAINER_DETAILS_MAKE_SKIP_LIST_MAP_H