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-2016
   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         /// Forward iterator
 126         /**
 127             Remember, the iterator <tt>operator -> </tt> and <tt>operator *</tt> returns \ref value_type pointer and reference.
 128             To access item key and value use <tt>it->first</tt> and <tt>it->second</tt> respectively.
 129         */
 130         typedef typename base_class::iterator iterator;
 131
 132         /// Const forward iterator
 133         typedef typename base_class::const_iterator const_iterator;
 134
 135         /// Returns a forward iterator addressing the first element in a map
 136         /**
 137             For empty set \code begin() == end() \endcode
 138         */
 139         iterator begin()
 140         {
 141             return base_class::begin();
 142         }
 143
 144         /// Returns an iterator that addresses the location succeeding the last element in a map
 145         /**
 146             Do not use the value returned by <tt>end</tt> function to access any item.
 147             The returned value can be used only to control reaching the end of the set.
 148             For empty set \code begin() == end() \endcode
 149         */
 150         iterator end()
 151         {
 152             return base_class::end();
 153         }
 154
 155         /// Returns a forward const iterator addressing the first element in a map
 156         const_iterator begin() const
 157         {
 158             return base_class::begin();
 159         }
 160         /// Returns a forward const iterator addressing the first element in a map
 161         const_iterator cbegin() const
 162         {
 163             return base_class::cbegin();
 164         }
 165
 166         /// Returns an const iterator that addresses the location succeeding the last element in a map
 167         const_iterator end() const
 168         {
 169             return base_class::end();
 170         }
 171         /// Returns an const iterator that addresses the location succeeding the last element in a map
 172         const_iterator cend() const
 173         {
 174             return base_class::cend();
 175         }
 176
 177     public:
 178         /// Inserts new node with key and default value
 179         /**
 180             The function creates a node with \p key and default value, and then inserts the node created into the map.
 181
 182             Preconditions:
 183             - The \ref key_type should be constructible from value of type \p K.
 184                 In trivial case, \p K is equal to \ref key_type.
 185             - The \ref mapped_type should be default-constructible.
 186
 187             Returns an iterator pointed to inserted value, or \p end() if inserting is failed
 188         */
 189         template <typename K>
 190         iterator insert( K const& key )
 191         {
 192             //TODO: pass arguments by reference (make_pair makes copy)
 193             return base_class::insert( std::make_pair( key, mapped_type() ) );
 194         }
 195
 196         /// Inserts new node
 197         /**
 198             The function creates a node with copy of \p val value
 199             and then inserts the node created into the map.
 200
 201             Preconditions:
 202             - The \ref key_type should be constructible from \p key of type \p K.
 203             - The \ref mapped_type should be constructible from \p val of type \p V.
 204
 205             Returns an iterator pointed to inserted value, or \p end() if inserting is failed
 206         */
 207         template <typename K, typename V>
 208         iterator insert( K const& key, V const& val )
 209         {
 210             //TODO: pass arguments by reference (make_pair makes copy)
 211             return base_class::insert( std::make_pair( key, val ) );
 212         }
 213
 214         /// Inserts new node and initialize it by a functor
 215         /**
 216             This function inserts new node with key \p key and if inserting is successful then it calls
 217             \p func functor with signature
 218             \code
 219             struct functor {
 220                 void operator()( value_type& item );
 221             };
 222             \endcode
 223
 224             The argument \p item of user-defined functor \p func is the reference
 225             to the map's item inserted. <tt>item.second</tt> is a reference to item's value that may be changed.
 226             User-defined functor \p func should guarantee that during changing item's value no any other changes
 227             could be made on this map's item by concurrent threads.
 228
 229             The key_type should be constructible from value of type \p K.
 230
 231             The function allows to split creating of new item into three part:
 232             - create item from \p key;
 233             - insert new item into the map;
 234             - if inserting is successful, initialize the value of item by calling \p f functor
 235
 236             This can be useful if complete initialization of object of \p mapped_type is heavyweight and
 237             it is preferable that the initialization should be completed only if inserting is successful.
 238
 239             Returns an iterator pointed to inserted value, or \p end() if inserting is failed
 240         */
 241         template <typename K, typename Func>
 242         iterator insert_with( K const& key, Func func )
 243         {
 244             iterator it = insert( key );
 245             if ( it != end() )
 246                 func( (*it) );
 247             return it;
 248         }
 249
 250         /// For key \p key inserts data of type \p mapped_type created in-place from \p args
 251         /**
 252             \p key_type should be constructible from type \p K
 253
 254             Returns \p true if inserting successful, \p false otherwise.
 255         */
 256         template <typename K, typename... Args>
 257         iterator emplace( K&& key, Args&&... args )
 258         {
 259             return base_class::emplace( std::forward<K>(key), std::move(mapped_type(std::forward<Args>(args)...)));
 260         }
 261
 262         /// UPdates data by \p key
 263         /**
 264             The operation inserts new item if \p key is not found in the map and \p bInsert is \p true.
 265             Otherwise, if \p key is found, the function returns an iterator that points to item found.
 266
 267             Returns <tt> std::pair<iterator, bool>  </tt> where \p first is an iterator pointing to
 268             item found or inserted or \p end() if \p key is not found and insertion is not allowed (\p bInsert is \p false),
 269             \p second is \p true if new item has been added or \p false if the item already exists.
 270         */
 271         template <typename K>
 272         std::pair<iterator, bool> update( K const& key, bool bInsert = true )
 273         {
 274             //TODO: pass arguments by reference (make_pair makes copy)
 275             return base_class::update( std::make_pair( key, mapped_type() ), bInsert );
 276         }
 277         //@cond
 278         template <typename K>
 279         CDS_DEPRECATED("ensure() is deprecated, use update()")
 280         std::pair<iterator, bool> ensure( K const& key )
 281         {
 282             return update( key, true );
 283         }
 284         //@endcond
 285
 286         /// Checks whether the map contains \p key
 287         /**
 288             The function searches the item with key equal to \p key
 289             and returns an iterator pointed to item found if the key is found,
 290             and \ref end() otherwise
 291         */
 292         template <typename K>
 293         iterator contains( K const& key )
 294         {
 295             return base_class::contains( key );
 296         }
 297         //@cond
 298
 299         template <typename K>
 300         CDS_DEPRECATED("deprecated, use contains()")
 301         iterator find( K const& key )
 302         {
 303             return contains( key );
 304         }
 305         //@endcond
 306
 307         /// Checks whether the map contains \p key using \p pred predicate for searching
 308         /**
 309             The function is similar to <tt>contains( key )</tt> but \p pred is used for key comparing.
 310             \p Less functor has the interface like \p std::less.
 311             \p Less must imply the same element order as the comparator used for building the map.
 312         */
 313         template <typename K, typename Less>
 314         iterator contains( K const& key, Less pred ) const
 315         {
 316             return base_class::contains( key, pred );
 317         }
 318         //@cond
 319         template <typename K, typename Less>
 320         CDS_DEPRECATED("deprecated, use contains()")
 321         iterator find_with( K const& key, Less pred ) const
 322         {
 323             return contains( key, pred );
 324         }
 325         //@endcond
 326
 327         /// Gets minimum key from the map
 328         /**
 329             If the map is empty the function returns \p nullptr
 330         */
 331         value_type * get_min() const
 332         {
 333             return base_class::get_min();
 334         }
 335
 336         /// Gets maximum key from the map
 337         /**
 338             The function returns \p nullptr if the map is empty
 339         */
 340         value_type * get_max() const
 341         {
 342             return base_class::get_max();
 343         }
 344
 345         /// Clears the map (not atomic)
 346         /**
 347             Finding and/or inserting is prohibited while clearing.
 348             Otherwise an unpredictable result may be encountered.
 349             Thus, \p clear() may be used only for debugging purposes.
 350         */
 351         void clear()
 352         {
 353             base_class::clear();
 354         }
 355
 356         /// Checks if the map is empty
 357         /**
 358             Emptiness is checked by item counting: if item count is zero then the map is empty.
 359             Thus, the correct item counting feature is an important part of Michael's map implementation.
 360         */
 361         bool empty() const
 362         {
 363             return base_class::empty();
 364         }
 365
 366         /// Returns item count in the map
 367         size_t size() const
 368         {
 369             return base_class::size();
 370         }
 371
 372         /// Returns maximum height of skip-list. The max height is a constant for each object and does not exceed 32.
 373         static CDS_CONSTEXPR unsigned int max_height() CDS_NOEXCEPT
 374         {
 375             return base_class::max_height();
 376         }
 377
 378         /// Returns const reference to internal statistics
 379         stat const& statistics() const
 380         {
 381             return base_class::statistics();
 382         }
 383     };
 384
 385 }} // namespace cds::container
 386
 387
 388 #endif // #ifndef CDSLIB_CONTAINER_SKIP_LIST_MAP_NOGC_H