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         /// UPdates data by \p key
 235         /**
 236             The operation inserts new item if \p key is not found in the map and \p bInsert is \p true.
 237             Otherwise, if \p key is found, 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 or \p end() if \p key is not found and insertion is not allowed (\p bInsert is \p false),
 241             \p second is \p true if new item has been added or \p false if the item already exists.
 242         */
 243         template <typename K>
 244         std::pair<iterator, bool> update( K const& key, bool bInsert = true )
 245         {
 246             //TODO: pass arguments by reference (make_pair makes copy)
 247             return base_class::update( std::make_pair( key, mapped_type() ), bInsert );
 248         }
 249         //@cond
 250         template <typename K>
 251         CDS_DEPRECATED("ensure() is deprecated, use update()")
 252         std::pair<iterator, bool> ensure( K const& key )
 253         {
 254             return update( key, true );
 255         }
 256         //@endcond
 257
 258         /// Checks whether the map contains \p key
 259         /**
 260             The function searches the item with key equal to \p key
 261             and returns an iterator pointed to item found if the key is found,
 262             and \ref end() otherwise
 263         */
 264         template <typename K>
 265         iterator contains( K const& key )
 266         {
 267             return base_class::contains( key );
 268         }
 269         //@cond
 270
 271         template <typename K>
 272         CDS_DEPRECATED("deprecated, use contains()")
 273         iterator find( K const& key )
 274         {
 275             return contains( key );
 276         }
 277         //@endcond
 278
 279         /// Checks whether the map contains \p key using \p pred predicate for searching
 280         /**
 281             The function is similar to <tt>contains( key )</tt> but \p pred is used for key comparing.
 282             \p Less functor has the interface like \p std::less.
 283             \p Less must imply the same element order as the comparator used for building the map.
 284         */
 285         template <typename K, typename Less>
 286         iterator contains( K const& key, Less pred ) const
 287         {
 288             return base_class::contains( key, pred );
 289         }
 290         //@cond
 291         template <typename K, typename Less>
 292         CDS_DEPRECATED("deprecated, use contains()")
 293         iterator find_with( K const& key, Less pred ) const
 294         {
 295             return contains( key, pred );
 296         }
 297         //@endcond
 298
 299         /// Gets minimum key from the map
 300         /**
 301             If the map is empty the function returns \p nullptr
 302         */
 303         value_type * get_min() const
 304         {
 305             return base_class::get_min();
 306         }
 307
 308         /// Gets maximum key from the map
 309         /**
 310             The function returns \p nullptr if the map is empty
 311         */
 312         value_type * get_max() const
 313         {
 314             return base_class::get_max();
 315         }
 316
 317         /// Clears the map (not atomic)
 318         /**
 319             Finding and/or inserting is prohibited while clearing.
 320             Otherwise an unpredictable result may be encountered.
 321             Thus, \p clear() may be used only for debugging purposes.
 322         */
 323         void clear()
 324         {
 325             base_class::clear();
 326         }
 327
 328         /// Checks if the map is empty
 329         /**
 330             Emptiness is checked by item counting: if item count is zero then the map is empty.
 331             Thus, the correct item counting feature is an important part of Michael's map implementation.
 332         */
 333         bool empty() const
 334         {
 335             return base_class::empty();
 336         }
 337
 338         /// Returns item count in the map
 339         size_t size() const
 340         {
 341             return base_class::size();
 342         }
 343
 344         /// Returns maximum height of skip-list. The max height is a constant for each object and does not exceed 32.
 345         static CDS_CONSTEXPR unsigned int max_height() CDS_NOEXCEPT
 346         {
 347             return base_class::max_height();
 348         }
 349
 350         /// Returns const reference to internal statistics
 351         stat const& statistics() const
 352         {
 353             return base_class::statistics();
 354         }
 355     };
 356
 357 }} // namespace cds::container
 358
 359
 360 #endif // #ifndef CDSLIB_CONTAINER_SKIP_LIST_MAP_NOGC_H