3 #ifndef CDSLIB_CONTAINER_DETAILS_MAKE_SKIP_LIST_MAP_H
4 #define CDSLIB_CONTAINER_DETAILS_MAKE_SKIP_LIST_MAP_H
6 #include <cds/container/details/skip_list_base.h>
7 #include <cds/details/binary_functor_wrapper.h>
10 namespace cds { namespace container { namespace details {
12 template <typename GC, typename K, typename T, typename Traits>
13 struct make_skip_list_map
17 typedef T mapped_type;
18 typedef std::pair< key_type const, mapped_type> value_type;
19 typedef Traits traits;
21 typedef cds::intrusive::skip_list::node< gc > intrusive_node_type;
22 struct node_type: public intrusive_node_type
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;
29 //atomic_marked_ptr m_arrTower[] ; // allocated together with node_type in single memory block
32 node_type( unsigned int nHeight, atomic_marked_ptr * pTower, Q const& key )
33 : m_Value( std::make_pair( key, mapped_type() ))
35 init_tower( nHeight, pTower );
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 ))
42 init_tower( nHeight, pTower );
45 template <typename Q, typename... Args>
46 node_type( unsigned int nHeight, atomic_marked_ptr * pTower, Q&& key, Args&&... args )
47 : m_Value( std::forward<Q>(key), std::move( mapped_type( std::forward<Args>(args)... )))
49 init_tower( nHeight, pTower );
55 void init_tower( unsigned int nHeight, atomic_marked_ptr * pTower )
58 new (pTower) atomic_marked_ptr[ nHeight - 1 ];
59 base_class::make_tower( nHeight, pTower );
64 class node_allocator : public skip_list::details::node_allocator< node_type, traits>
66 typedef skip_list::details::node_allocator< node_type, traits> base_class;
69 node_type * New( unsigned int nHeight, Q const& key )
71 return base_class::New( nHeight, key );
73 template <typename Q, typename U>
74 node_type * New( unsigned int nHeight, Q const& key, U const& val )
76 unsigned char * pMem = base_class::alloc_space( nHeight );
79 nHeight > 1 ? reinterpret_cast<typename base_class::node_tower_item *>( pMem + base_class::c_nNodeSize ) : nullptr,
83 template <typename... Args>
84 node_type * New( unsigned int nHeight, Args&&... args )
86 unsigned char * pMem = base_class::alloc_space( nHeight );
89 nHeight > 1 ? reinterpret_cast<typename base_class::node_tower_item *>( pMem + base_class::c_nNodeSize ) : nullptr,
90 std::forward<Args>(args)...
95 struct node_deallocator {
96 void operator ()( node_type * pNode )
98 node_allocator().Delete( pNode );
102 typedef skip_list::details::dummy_node_builder<intrusive_node_type> dummy_node_builder;
106 key_type const & operator()( node_type const& node ) const
108 return node.m_Value.first;
111 typedef typename opt::details::make_comparator< key_type, traits >::type key_comparator;
113 class intrusive_type_traits: public cds::intrusive::skip_list::make_traits<
114 cds::opt::type_traits< traits >
115 ,cds::intrusive::opt::hook< intrusive::skip_list::base_hook< cds::opt::gc< gc > > >
116 ,cds::intrusive::opt::disposer< node_deallocator >
117 ,cds::intrusive::skip_list::internal_node_builder< dummy_node_builder >
118 ,cds::opt::compare< cds::details::compare_wrapper< node_type, key_comparator, key_accessor > >
122 typedef cds::intrusive::SkipListSet< gc, node_type, intrusive_type_traits> type;
125 }}} // namespace cds::container::details
128 #endif // CDSLIB_CONTAINER_DETAILS_MAKE_SKIP_LIST_MAP_H