cds/container/skip_list_map_nogc.h

   1 /*
   2     This file is a part of libcds - Concurrent Data Structures library
   3
   4     (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2017
   5
   6     Source code repo: http://github.com/khizmax/libcds/
   7     Download: http://sourceforge.net/projects/libcds/files/
   8
   9     Redistribution and use in source and binary forms, with or without
  10     modification, are permitted provided that the following conditions are met:
  11
  12     * Redistributions of source code must retain the above copyright notice, this
  13       list of conditions and the following disclaimer.
  14
  15     * Redistributions in binary form must reproduce the above copyright notice,
  16       this list of conditions and the following disclaimer in the documentation
  17       and/or other materials provided with the distribution.
  18
  19     THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
  20     AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  21     IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
  22     DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
  23     FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  24     DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
  25     SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
  26     CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
  27     OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  28     OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  29 */
  30
  31 #ifndef CDSLIB_CONTAINER_SKIP_LIST_MAP_NOGC_H
  32 #define CDSLIB_CONTAINER_SKIP_LIST_MAP_NOGC_H
  33
  34 #include <cds/container/skip_list_set_nogc.h>
  35
  36 namespace cds { namespace container {
  37     //@cond
  38     namespace skip_list { namespace details {
  39         struct map_key_accessor
  40         {
  41             template <typename NodeType>
  42             typename NodeType::stored_value_type::first_type const& operator()( NodeType const& node ) const
  43             {
  44                 return node.m_Value.first;
  45             }
  46         };
  47     }} // namespace skip_list::details
  48     //@endcond
  49
  50     /// Lock-free skip-list map (template specialization for gc::nogc)
  51     /** @ingroup cds_nonintrusive_map
  52         \anchor cds_nonintrusive_SkipListMap_nogc
  53
  54         This specialization is intended for so-called persistent usage when no item
  55         reclamation may be performed. The class does not support deleting of map item.
  56         See \ref cds_nonintrusive_SkipListMap_hp "SkipListMap" for detailed description.
  57
  58         Template arguments:
  59         - \p K - type of a key to be stored in the map.
  60         - \p T - type of a value to be stored in the map.
  61         - \p Traits - map traits, default is \p skip_list::traits
  62             It is possible to declare option-based list with \p cds::container::skip_list::make_traits
  63             metafunction istead of \p Traits template argument.
  64     */
  65     template <
  66         typename Key,
  67         typename T,
  68 #ifdef CDS_DOXYGEN_INVOKED
  69         typename Traits = skip_list::traits
  70 #else
  71         typename Traits
  72 #endif
  73     >
  74     class SkipListMap< cds::gc::nogc, Key, T, Traits >:
  75 #ifdef CDS_DOXYGEN_INVOKED
  76         protected SkipListSet< cds::gc::nogc, std::pair< Key const, T >, Traits >
  77 #else
  78         protected SkipListSet<
  79             cds::gc::nogc
  80             ,std::pair< Key const, T >
  81             ,typename cds::opt::replace_key_accessor< Traits, skip_list::details::map_key_accessor >::type
  82         >
  83 #endif
  84     {
  85         //@cond
  86         typedef SkipListSet<
  87             cds::gc::nogc
  88             ,std::pair< Key const, T >
  89             ,typename cds::opt::replace_key_accessor< Traits, skip_list::details::map_key_accessor >::type
  90         > base_class;
  91         //@endcond
  92
  93     public:
  94         typedef cds::gc::nogc gc;   ///< Garbage collector
  95         typedef Key key_type;       ///< Key type
  96         typedef T   mapped_type;    ///< Mapped type
  97         typedef std::pair< key_type const, mapped_type> value_type; ///< Key-value pair stored in the map
  98         typedef Traits  traits;     ///< Options specified
  99
 100         typedef typename base_class::back_off       back_off;       ///< Back-off strategy
 101         typedef typename base_class::allocator_type allocator_type; ///< Allocator type used for allocate/deallocate the skip-list nodes
 102         typedef typename base_class::item_counter   item_counter;   ///< Item counting policy
 103         typedef typename base_class::key_comparator key_comparator; ///< key compare functor
 104         typedef typename base_class::memory_model   memory_model;   ///< Memory ordering, see \p cds::opt::memory_model option
 105         typedef typename base_class::stat           stat;           ///< internal statistics type
 106         typedef typename base_class::random_level_generator random_level_generator; ///< random level generator
 107
 108     protected:
 109         //@cond
 110         typedef typename base_class::node_type      node_type;
 111         typedef typename base_class::node_allocator node_allocator;
 112         //@endcond
 113
 114     public:
 115         /// Default constructor
 116         SkipListMap()
 117             : base_class()
 118         {}
 119
 120         /// Destructor clears the map
 121         ~SkipListMap()
 122         {}
 123
 124     public:
 125     ///@name Forward ordered iterators
 126     //@{
 127         /// Forward iterator
 128         /**
 129             The forward iterator for a split-list has some features:
 130             - it has no post-increment operator
 131             - it depends on iterator of underlying \p OrderedList
 132         */
 133         typedef typename base_class::iterator iterator;
 134
 135         /// Const forward iterator
 136         typedef typename base_class::const_iterator const_iterator;
 137
 138         /// Returns a forward iterator addressing the first element in a map
 139         /**
 140             For empty set \code begin() == end() \endcode
 141         */
 142         iterator begin()
 143         {
 144             return base_class::begin();
 145         }
 146
 147         /// Returns an iterator that addresses the location succeeding the last element in a map
 148         /**
 149             Do not use the value returned by <tt>end</tt> function to access any item.
 150             The returned value can be used only to control reaching the end of the set.
 151             For empty set \code begin() == end() \endcode
 152         */
 153         iterator end()
 154         {
 155             return base_class::end();
 156         }
 157
 158         /// Returns a forward const iterator addressing the first element in a map
 159         const_iterator begin() const
 160         {
 161             return base_class::begin();
 162         }
 163
 164         /// Returns a forward const iterator addressing the first element in a map
 165         const_iterator cbegin() const
 166         {
 167             return base_class::cbegin();
 168         }
 169
 170         /// Returns an const iterator that addresses the location succeeding the last element in a map
 171         const_iterator end() const
 172         {
 173             return base_class::end();
 174         }
 175
 176         /// Returns an const iterator that addresses the location succeeding the last element in a map
 177         const_iterator cend() const
 178         {
 179             return base_class::cend();
 180         }
 181     //@}
 182
 183     public:
 184         /// Inserts new node with key and default value
 185         /**
 186             The function creates a node with \p key and default value, and then inserts the node created into the map.
 187
 188             Preconditions:
 189             - The \ref key_type should be constructible from value of type \p K.
 190                 In trivial case, \p K is equal to \ref key_type.
 191             - The \ref mapped_type should be default-constructible.
 192
 193             Returns an iterator pointed to inserted value, or \p end() if inserting is failed
 194         */
 195         template <typename K>
 196         iterator insert( K const& key )
 197         {
 198             //TODO: pass arguments by reference (make_pair makes copy)
 199             return base_class::insert( std::make_pair( key_type( key ), mapped_type()));
 200         }
 201
 202         /// Inserts new node
 203         /**
 204             The function creates a node with copy of \p val value
 205             and then inserts the node created into the map.
 206
 207             Preconditions:
 208             - The \ref key_type should be constructible from \p key of type \p K.
 209             - The \ref mapped_type should be constructible from \p val of type \p V.
 210
 211             Returns an iterator pointed to inserted value, or \p end() if inserting is failed
 212         */
 213         template <typename K, typename V>
 214         iterator insert( K const& key, V const& val )
 215         {
 216             //TODO: pass arguments by reference (make_pair makes copy)
 217             return base_class::insert( std::make_pair( key_type( key ), mapped_type( val )));
 218         }
 219
 220         /// Inserts new node and initialize it by a functor
 221         /**
 222             This function inserts new node with key \p key and if inserting is successful then it calls
 223             \p func functor with signature
 224             \code
 225             struct functor {
 226                 void operator()( value_type& item );
 227             };
 228             \endcode
 229
 230             The argument \p item of user-defined functor \p func is the reference
 231             to the map's item inserted. <tt>item.second</tt> is a reference to item's value that may be changed.
 232             User-defined functor \p func should guarantee that during changing item's value no any other changes
 233             could be made on this map's item by concurrent threads.
 234
 235             The key_type should be constructible from value of type \p K.
 236
 237             The function allows to split creating of new item into three part:
 238             - create item from \p key;
 239             - insert new item into the map;
 240             - if inserting is successful, initialize the value of item by calling \p f functor
 241
 242             This can be useful if complete initialization of object of \p mapped_type is heavyweight and
 243             it is preferable that the initialization should be completed only if inserting is successful.
 244
 245             Returns an iterator pointed to inserted value, or \p end() if inserting is failed
 246         */
 247         template <typename K, typename Func>
 248         iterator insert_with( K const& key, Func func )
 249         {
 250             iterator it = insert( key );
 251             if ( it != end())
 252                 func( (*it));
 253             return it;
 254         }
 255
 256         /// For key \p key inserts data of type \p mapped_type created in-place from \p args
 257         /**
 258             \p key_type should be constructible from type \p K
 259
 260             Returns \p true if inserting successful, \p false otherwise.
 261         */
 262         template <typename K, typename... Args>
 263         iterator emplace( K&& key, Args&&... args )
 264         {
 265             return base_class::emplace( key_type( std::forward<K>( key )), mapped_type( std::forward<Args>(args)... ));
 266         }
 267
 268         /// UPdates data by \p key
 269         /**
 270             The operation inserts new item if \p key is not found in the map and \p bInsert is \p true.
 271             Otherwise, if \p key is found, the function returns an iterator that points to item found.
 272
 273             Returns <tt> std::pair<iterator, bool>  </tt> where \p first is an iterator pointing to
 274             item found or inserted or \p end() if \p key is not found and insertion is not allowed (\p bInsert is \p false),
 275             \p second is \p true if new item has been added or \p false if the item already exists.
 276         */
 277         template <typename K>
 278         std::pair<iterator, bool> update( K const& key, bool bInsert = true )
 279         {
 280             //TODO: pass arguments by reference (make_pair makes copy)
 281             return base_class::update( std::make_pair( key_type( key ), mapped_type()), bInsert );
 282         }
 283         //@cond
 284         template <typename K>
 285         CDS_DEPRECATED("ensure() is deprecated, use update()")
 286         std::pair<iterator, bool> ensure( K const& key )
 287         {
 288             return update( key, true );
 289         }
 290         //@endcond
 291
 292         /// Checks whether the map contains \p key
 293         /**
 294             The function searches the item with key equal to \p key
 295             and returns an iterator pointed to item found if the key is found,
 296             and \ref end() otherwise
 297         */
 298         template <typename K>
 299         iterator contains( K const& key )
 300         {
 301             return base_class::contains( key );
 302         }
 303         //@cond
 304
 305         template <typename K>
 306         CDS_DEPRECATED("deprecated, use contains()")
 307         iterator find( K const& key )
 308         {
 309             return contains( key );
 310         }
 311         //@endcond
 312
 313         /// Checks whether the map contains \p key using \p pred predicate for searching
 314         /**
 315             The function is similar to <tt>contains( key )</tt> but \p pred is used for key comparing.
 316             \p Less functor has the interface like \p std::less.
 317             \p Less must imply the same element order as the comparator used for building the map.
 318         */
 319         template <typename K, typename Less>
 320         iterator contains( K const& key, Less pred ) const
 321         {
 322             return base_class::contains( key, pred );
 323         }
 324         //@cond
 325         template <typename K, typename Less>
 326         CDS_DEPRECATED("deprecated, use contains()")
 327         iterator find_with( K const& key, Less pred ) const
 328         {
 329             return contains( key, pred );
 330         }
 331         //@endcond
 332
 333         /// Gets minimum key from the map
 334         /**
 335             If the map is empty the function returns \p nullptr
 336         */
 337         value_type * get_min() const
 338         {
 339             return base_class::get_min();
 340         }
 341
 342         /// Gets maximum key from the map
 343         /**
 344             The function returns \p nullptr if the map is empty
 345         */
 346         value_type * get_max() const
 347         {
 348             return base_class::get_max();
 349         }
 350
 351         /// Clears the map (not atomic)
 352         /**
 353             Finding and/or inserting is prohibited while clearing.
 354             Otherwise an unpredictable result may be encountered.
 355             Thus, \p clear() may be used only for debugging purposes.
 356         */
 357         void clear()
 358         {
 359             base_class::clear();
 360         }
 361
 362         /// Checks if the map is empty
 363         /**
 364             Emptiness is checked by item counting: if item count is zero then the map is empty.
 365             Thus, the correct item counting feature is an important part of Michael's map implementation.
 366         */
 367         bool empty() const
 368         {
 369             return base_class::empty();
 370         }
 371
 372         /// Returns item count in the map
 373         size_t size() const
 374         {
 375             return base_class::size();
 376         }
 377
 378         /// Returns maximum height of skip-list. The max height is a constant for each object and does not exceed 32.
 379         static CDS_CONSTEXPR unsigned int max_height() CDS_NOEXCEPT
 380         {
 381             return base_class::max_height();
 382         }
 383
 384         /// Returns const reference to internal statistics
 385         stat const& statistics() const
 386         {
 387             return base_class::statistics();
 388         }
 389     };
 390
 391 }} // namespace cds::container
 392
 393
 394 #endif // #ifndef CDSLIB_CONTAINER_SKIP_LIST_MAP_NOGC_H