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 \p std::ref
 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                 func( (*it) );
 262             return it;
 263         }
 264
 265         /// For key \p key inserts data of type \ref mapped_type constructed with <tt>std::forward<Args>(args)...</tt>
 266         /**
 267             \p key_type should be constructible from type \p K
 268
 269             Returns \p true if inserting successful, \p false otherwise.
 270         */
 271         template <typename K, typename... Args>
 272         iterator emplace( K&& key, Args&&... args )
 273         {
 274             return base_class::emplace( std::forward<K>(key), std::move(mapped_type(std::forward<Args>(args)...)));
 275         }
 276
 277         /// Ensures that the key \p key exists in the map
 278         /**
 279             The operation inserts new item if the key \p key is not found in the map.
 280             Otherwise, the function returns an iterator that points to item found.
 281
 282             Returns <tt> std::pair<iterator, bool>  </tt> where \p first is an iterator pointing to
 283             item found or inserted, \p second is true if new item has been added or \p false if the item
 284             already is in the list.
 285         */
 286         template <typename K>
 287         std::pair<iterator, bool> ensure( K const& key )
 288         {
 289             //TODO: pass arguments by reference (make_pair makes copy)
 290             return base_class::ensure( std::make_pair( key, mapped_type() ));
 291         }
 292
 293         /// Finds the key \p key
 294         /** \anchor cds_nonintrusive_SkipListMap_nogc_find_val
 295
 296             The function searches the item with key equal to \p key
 297             and returns an iterator pointed to item found if the key is found,
 298             and \ref end() otherwise
 299         */
 300         template <typename K>
 301         iterator find( K const& key )
 302         {
 303             return base_class::find( key );
 304         }
 305
 306         /// Finds the key \p key with comparing functor \p cmp
 307         /**
 308             The function is an analog of \ref cds_nonintrusive_SkipListMap_nogc_find_val "find(K const&)"
 309             but \p pred is used for key comparing.
 310             \p Less functor has the interface like \p std::less.
 311             \p Less must imply the same element order as the comparator used for building the set.
 312         */
 313         template <typename K, typename Less>
 314         iterator find_with( K const& key, Less pred ) const
 315         {
 316             return base_class::find_with( key, pred );
 317         }
 318
 319         /// Gets minimum key from the map
 320         /**
 321             If the map is empty the function returns \p nullptr
 322         */
 323         value_type * get_min() const
 324         {
 325             return base_class::get_min();
 326         }
 327
 328         /// Gets maximum key from the map
 329         /**
 330             The function returns \p nullptr if the map is empty
 331         */
 332         value_type * get_max() const
 333         {
 334             return base_class::get_max();
 335         }
 336
 337         /// Clears the map (non-atomic)
 338         /**
 339             The function is not atomic.
 340             Finding and/or inserting is prohibited while clearing.
 341             Otherwise an unpredictable result may be encountered.
 342             Thus, \p clear() may be used only for debugging purposes.
 343         */
 344         void clear()
 345         {
 346             base_class::clear();
 347         }
 348
 349         /// Checks if the map is empty
 350         /**
 351             Emptiness is checked by item counting: if item count is zero then the map is empty.
 352             Thus, the correct item counting feature is an important part of Michael's map implementation.
 353         */
 354         bool empty() const
 355         {
 356             return base_class::empty();
 357         }
 358
 359         /// Returns item count in the map
 360         size_t size() const
 361         {
 362             return base_class::size();
 363         }
 364
 365         /// Returns maximum height of skip-list. The max height is a constant for each object and does not exceed 32.
 366         static CDS_CONSTEXPR unsigned int max_height() CDS_NOEXCEPT
 367         {
 368             return base_class::max_height();
 369         }
 370
 371         /// Returns const reference to internal statistics
 372         stat const& statistics() const
 373         {
 374             return base_class::statistics();
 375         }
 376     };
 377
 378 }} // namespace cds::container
 379
 380
 381 #endif // #ifndef __CDS_CONTAINER_SKIP_LIST_MAP_NOGC_H