cds/container/skip_list_map_nogc.h

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