cds/container/skip_list_map_nogc.h

   1 //$$CDS-header$$
   2
   3 #ifndef __CDS_CONTAINER_SKIP_LIST_MAP_NOGC_H
   4 #define __CDS_CONTAINER_SKIP_LIST_MAP_NOGC_H
   5
   6 #include <cds/container/skip_list_set_nogc.h>
   7
   8 namespace cds { namespace container {
   9     //@cond
  10     namespace skip_list { namespace details {
  11         struct map_key_accessor
  12         {
  13             template <typename NodeType>
  14             typename NodeType::stored_value_type::first_type const& operator()( NodeType const& node ) const
  15             {
  16                 return node.m_Value.first;
  17             }
  18         };
  19     }} // namespace skip_list::details
  20     //@endcond
  21
  22
  23     /// Lock-free skip-list map (template specialization for gc::nogc)
  24     /** @ingroup cds_nonintrusive_map
  25         \anchor cds_nonintrusive_SkipListMap_nogc
  26
  27         This specialization is intended for so-called persistent usage when no item
  28         reclamation may be performed. The class does not support deleting of map item.
  29         See \ref cds_nonintrusive_SkipListMap_hp "SkipListMap" for detailed description.
  30
  31         Template arguments:
  32         - \p K - type of a key to be stored in the list.
  33         - \p T - type of a value to be stored in the list.
  34         - \p Traits - type traits. See skip_list::type_traits for explanation.
  35
  36         It is possible to declare option-based list with cds::container::skip_list::make_traits metafunction istead of \p Traits template
  37         argument.
  38         Template argument list \p Options of cds::container::skip_list::make_traits metafunction are:
  39         - opt::compare - key compare functor. No default functor is provided.
  40             If the option is not specified, the opt::less is used.
  41         - opt::less - specifies binary predicate used for key comparison. Default is \p std::less<K>.
  42         - opt::item_counter - the type of item counting feature. Default is \ref atomicity::empty_item_counter that is no item counting.
  43         - opt::memory_model - C++ memory ordering model. Can be opt::v::relaxed_ordering (relaxed memory model, the default)
  44             or opt::v::sequential_consistent (sequentially consisnent memory model).
  45         - skip_list::random_level_generator - random level generator. Can be skip_list::xorshift, skip_list::turbo_pascal or
  46             user-provided one. See skip_list::random_level_generator option description for explanation.
  47             Default is \p %skip_list::turbo_pascal.
  48         - opt::allocator - allocator for skip-list node. Default is \ref CDS_DEFAULT_ALLOCATOR.
  49         - opt::back_off - back-off strategy used. If the option is not specified, the cds::backoff::Default is used.
  50         - opt::stat - internal statistics. Available types: skip_list::stat, skip_list::empty_stat (the default)
  51     */
  52     template <
  53         typename Key,
  54         typename T,
  55 #ifdef CDS_DOXYGEN_INVOKED
  56         typename Traits = skip_list::type_traits
  57 #else
  58         typename Traits
  59 #endif
  60     >
  61     class SkipListMap< cds::gc::nogc, Key, T, Traits >:
  62 #ifdef CDS_DOXYGEN_INVOKED
  63         protected SkipListSet< cds::gc::nogc, std::pair< Key const, T >, Traits >
  64 #else
  65         protected SkipListSet<
  66             cds::gc::nogc
  67             ,std::pair< Key const, T >
  68             ,typename cds::opt::replace_key_accessor< Traits, skip_list::details::map_key_accessor >::type
  69         >
  70 #endif
  71     {
  72         //@cond
  73         typedef SkipListSet<
  74             cds::gc::nogc
  75             ,std::pair< Key const, T >
  76             ,typename cds::opt::replace_key_accessor< Traits, skip_list::details::map_key_accessor >::type
  77         > base_class;
  78         //@endcond
  79
  80     public:
  81         typedef typename base_class::gc gc  ; ///< Garbage collector used
  82         typedef Key key_type      ;   ///< Key type
  83         typedef T   mapped_type   ;   ///< Mapped type
  84         typedef std::pair< key_type const, mapped_type> value_type  ;   ///< Key-value pair stored in the map
  85         typedef Traits  options     ;   ///< Options specified
  86
  87         typedef typename base_class::back_off       back_off        ;   ///< Back-off strategy used
  88         typedef typename base_class::allocator_type allocator_type  ;   ///< Allocator type used for allocate/deallocate the skip-list nodes
  89         typedef typename base_class::item_counter   item_counter    ;   ///< Item counting policy used
  90         typedef typename base_class::key_comparator key_comparator  ;   ///< key compare functor
  91         typedef typename base_class::memory_model   memory_model    ;   ///< Memory ordering. See cds::opt::memory_model option
  92         typedef typename base_class::stat           stat            ;   ///< internal statistics type
  93         typedef typename base_class::random_level_generator random_level_generator  ;   ///< random level generator
  94
  95     protected:
  96         //@cond
  97         typedef typename base_class::node_type      node_type;
  98         typedef typename base_class::node_allocator node_allocator;
  99
 100         /*
 101         template <class Less>
 102         struct less_wrapper {
 103             typedef Less    less_op;
 104
 105             bool operator()( value_type const& v1, value_type const& v2 ) const
 106             {
 107                 return less_op()( v1.first, v2.first);
 108             }
 109
 110             template <typename Q>
 111             bool operator()( value_type const& v1, Q const& v2 ) const
 112             {
 113                 return less_op()( v1.first, v2 );
 114             }
 115
 116             template <typename Q>
 117             bool operator()( Q const& v1, value_type const& v2 ) const
 118             {
 119                 return less_op()( v1, v2.first );
 120             }
 121         };
 122         */
 123         //@endcond
 124
 125     public:
 126         /// Default constructor
 127         SkipListMap()
 128             : base_class()
 129         {}
 130
 131         /// Destructor clears the map
 132         ~SkipListMap()
 133         {}
 134
 135     public:
 136         /// Forward iterator
 137         /**
 138             Remember, the iterator <tt>operator -> </tt> and <tt>operator *</tt> returns \ref value_type pointer and reference.
 139             To access item key and value use <tt>it->first</tt> and <tt>it->second</tt> respectively.
 140         */
 141         typedef typename base_class::iterator iterator;
 142
 143         /// Const forward iterator
 144         typedef typename base_class::const_iterator const_iterator;
 145
 146         /// Returns a forward iterator addressing the first element in a map
 147         /**
 148             For empty set \code begin() == end() \endcode
 149         */
 150         iterator begin()
 151         {
 152             return base_class::begin();
 153         }
 154
 155         /// Returns an iterator that addresses the location succeeding the last element in a map
 156         /**
 157             Do not use the value returned by <tt>end</tt> function to access any item.
 158             The returned value can be used only to control reaching the end of the set.
 159             For empty set \code begin() == end() \endcode
 160         */
 161         iterator end()
 162         {
 163             return base_class::end();
 164         }
 165
 166         /// Returns a forward const iterator addressing the first element in a map
 167         //@{
 168         const_iterator begin() const
 169         {
 170             return base_class::begin();
 171         }
 172         const_iterator cbegin()
 173         {
 174             return base_class::cbegin();
 175         }
 176         //@}
 177
 178         /// Returns an const iterator that addresses the location succeeding the last element in a map
 179         //@{
 180         const_iterator end() const
 181         {
 182             return base_class::end();
 183         }
 184         const_iterator cend()
 185         {
 186             return base_class::cend();
 187         }
 188         //@}
 189
 190     public:
 191         /// Inserts new node with key and default value
 192         /**
 193             The function creates a node with \p key and default value, and then inserts the node created into the map.
 194
 195             Preconditions:
 196             - The \ref key_type should be constructible from value of type \p K.
 197                 In trivial case, \p K is equal to \ref key_type.
 198             - The \ref mapped_type should be default-constructible.
 199
 200             Returns an iterator pointed to inserted value, or \p end() if inserting is failed
 201         */
 202         template <typename K>
 203         iterator insert( K const& key )
 204         {
 205             //TODO: pass arguments by reference (make_pair makes copy)
 206             return base_class::insert( std::make_pair( key, mapped_type() ) );
 207         }
 208
 209         /// Inserts new node
 210         /**
 211             The function creates a node with copy of \p val value
 212             and then inserts the node created into the map.
 213
 214             Preconditions:
 215             - The \ref key_type should be constructible from \p key of type \p K.
 216             - The \ref mapped_type should be constructible from \p val of type \p V.
 217
 218             Returns an iterator pointed to inserted value, or \p end() if inserting is failed
 219         */
 220         template <typename K, typename V>
 221         iterator insert( K const& key, V const& val )
 222         {
 223             //TODO: pass arguments by reference (make_pair makes copy)
 224             return base_class::insert( std::make_pair( key, val ) );
 225         }
 226
 227         /// Inserts new node and initialize it by a functor
 228         /**
 229             This function inserts new node with key \p key and if inserting is successful then it calls
 230             \p func functor with signature
 231             \code
 232             struct functor {
 233                 void operator()( value_type& item );
 234             };
 235             \endcode
 236
 237             The argument \p item of user-defined functor \p func is the reference
 238             to the map's item inserted. <tt>item.second</tt> is a reference to item's value that may be changed.
 239             User-defined functor \p func should guarantee that during changing item's value no any other changes
 240             could be made on this map's item by concurrent threads.
 241             The user-defined functor can be passed by reference using <tt>boost::ref</tt>
 242             and it is called only if the inserting is successful.
 243
 244             The key_type should be constructible from value of type \p K.
 245
 246             The function allows to split creating of new item into two part:
 247             - create item from \p key;
 248             - insert new item into the map;
 249             - if inserting is successful, initialize the value of item by calling \p f functor
 250
 251             This can be useful if complete initialization of object of \p mapped_type is heavyweight and
 252             it is preferable that the initialization should be completed only if inserting is successful.
 253
 254             Returns an iterator pointed to inserted value, or \p end() if inserting is failed
 255         */
 256         template <typename K, typename Func>
 257         iterator insert_key( K const& key, Func func )
 258         {
 259             iterator it = insert( key );
 260             if ( it != end() )
 261                 cds::unref( func )( (*it) );
 262             return it;
 263         }
 264
 265 #   ifdef CDS_EMPLACE_SUPPORT
 266         /// For key \p key inserts data of type \ref mapped_type constructed with <tt>std::forward<Args>(args)...</tt>
 267         /**
 268             \p key_type should be constructible from type \p K
 269
 270             Returns \p true if inserting successful, \p false otherwise.
 271
 272             This function is available only for compiler that supports
 273             variadic template and move semantics
 274         */
 275         template <typename K, typename... Args>
 276         iterator emplace( K&& key, Args&&... args )
 277         {
 278             return base_class::emplace( std::forward<K>(key), std::move(mapped_type(std::forward<Args>(args)...)));
 279         }
 280 #   endif
 281
 282         /// Ensures that the key \p key exists in the map
 283         /**
 284             The operation inserts new item if the key \p key is not found in the map.
 285             Otherwise, the function returns an iterator that points to item found.
 286
 287             Returns <tt> std::pair<iterator, bool>  </tt> where \p first is an iterator pointing to
 288             item found or inserted, \p second is true if new item has been added or \p false if the item
 289             already is in the list.
 290         */
 291         template <typename K>
 292         std::pair<iterator, bool> ensure( K const& key )
 293         {
 294             //TODO: pass arguments by reference (make_pair makes copy)
 295             return base_class::ensure( std::make_pair( key, mapped_type() ));
 296         }
 297
 298         /// Finds the key \p key
 299         /** \anchor cds_nonintrusive_SkipListMap_nogc_find_val
 300
 301             The function searches the item with key equal to \p key
 302             and returns an iterator pointed to item found if the key is found,
 303             and \ref end() otherwise
 304         */
 305         template <typename K>
 306         iterator find( K const& key )
 307         {
 308             return base_class::find( key );
 309         }
 310
 311         /// Finds the key \p key with comparing functor \p cmp
 312         /**
 313             The function is an analog of \ref cds_nonintrusive_SkipListMap_nogc_find_val "find(K const&)"
 314             but \p pred is used for key comparing.
 315             \p Less functor has the interface like \p std::less.
 316             \p Less must imply the same element order as the comparator used for building the set.
 317         */
 318         template <typename K, typename Less>
 319         iterator find_with( K const& key, Less pred ) const
 320         {
 321             return base_class::find_with( key, pred );
 322         }
 323
 324         /// Gets minimum key from the map
 325         /**
 326             If the map is empty the function returns \p nullptr
 327         */
 328         value_type * get_min() const
 329         {
 330             return base_class::get_min();
 331         }
 332
 333         /// Gets maximum key from the map
 334         /**
 335             The function returns \p nullptr if the map is empty
 336         */
 337         value_type * get_max() const
 338         {
 339             return base_class::get_max();
 340         }
 341
 342         /// Clears the map (non-atomic)
 343         /**
 344             The function is not atomic.
 345             Finding and/or inserting is prohibited while clearing.
 346             Otherwise an unpredictable result may be encountered.
 347             Thus, \p clear() may be used only for debugging purposes.
 348         */
 349         void clear()
 350         {
 351             base_class::clear();
 352         }
 353
 354         /// Checks if the map is empty
 355         /**
 356             Emptiness is checked by item counting: if item count is zero then the map is empty.
 357             Thus, the correct item counting feature is an important part of Michael's map implementation.
 358         */
 359         bool empty() const
 360         {
 361             return base_class::empty();
 362         }
 363
 364         /// Returns item count in the map
 365         size_t size() const
 366         {
 367             return base_class::size();
 368         }
 369
 370         /// Returns maximum height of skip-list. The max height is a constant for each object and does not exceed 32.
 371         static CDS_CONSTEXPR unsigned int max_height() CDS_NOEXCEPT
 372         {
 373             return base_class::max_height();
 374         }
 375
 376         /// Returns const reference to internal statistics
 377         stat const& statistics() const
 378         {
 379             return base_class::statistics();
 380         }
 381     };
 382
 383 }} // namespace cds::container
 384
 385
 386 #endif // #ifndef __CDS_CONTAINER_SKIP_LIST_MAP_NOGC_H