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