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