cds/container/split_list_map_nogc.h

   1 //$$CDS-header$$
   2
   3 #ifndef __CDS_CONTAINER_SPLIT_LIST_MAP_NOGC_H
   4 #define __CDS_CONTAINER_SPLIT_LIST_MAP_NOGC_H
   5
   6 #include <cds/container/split_list_set_nogc.h>
   7 #include <cds/details/binary_functor_wrapper.h>
   8
   9 namespace cds { namespace container {
  10
  11     /// Split-ordered list map (template specialization for gc::nogc)
  12     /** @ingroup cds_nonintrusive_map
  13         \anchor cds_nonintrusive_SplitListMap_nogc
  14
  15         This specialization is intended for so-called persistent usage when no item
  16         reclamation may be performed. The class does not support deleting of list item.
  17
  18         See \ref cds_nonintrusive_SplitListMap_hp "SplitListMap" for description of template parameters.
  19
  20         The interface of the specialization is a slightly different.
  21     */
  22     template <
  23         typename Key,
  24         typename Value,
  25 #ifdef CDS_DOXYGEN_INVOKED
  26         class Traits = split_list::type_traits
  27 #else
  28         class Traits
  29 #endif
  30     >
  31     class SplitListMap<cds::gc::nogc, Key, Value, Traits>:
  32         protected container::SplitListSet<
  33             cds::gc::nogc,
  34             std::pair<Key const, Value>,
  35             split_list::details::wrap_map_traits<Key, Value, Traits>
  36         >
  37     {
  38         //@cond
  39         typedef container::SplitListSet<
  40             cds::gc::nogc,
  41             std::pair<Key const, Value>,
  42             split_list::details::wrap_map_traits<Key, Value, Traits>
  43         > base_class;
  44         //@endcond
  45     public:
  46         typedef typename base_class::gc gc              ;   ///< Garbage collector
  47         typedef Key                     key_type        ;   ///< key type
  48         typedef Value                   mapped_type     ;   ///< type of value stored in the map
  49
  50         typedef std::pair<key_type const, mapped_type>  value_type  ;   ///< Pair type
  51         typedef typename base_class::ordered_list       ordered_list;   ///< Underlying ordered list class
  52         typedef typename base_class::key_comparator     key_comparator  ;   ///< key comparison functor
  53
  54         typedef typename base_class::hash           hash            ;   ///< Hash functor for \ref key_type
  55         typedef typename base_class::item_counter   item_counter    ;   ///< Item counter type
  56
  57     protected:
  58         //@cond
  59         typedef typename base_class::options::type_traits::key_accessor key_accessor;
  60         //@endcond
  61
  62     public:
  63         /// Forward iterator (see SplitListSet::iterator)
  64         /**
  65             Remember, the iterator <tt>operator -> </tt> and <tt>operator *</tt> returns \ref value_type pointer and reference.
  66             To access item key and value use <tt>it->first</tt> and <tt>it->second</tt> respectively.
  67         */
  68         typedef typename base_class::iterator iterator;
  69
  70         /// Const forward iterator (see SplitListSet::const_iterator)
  71         typedef typename base_class::const_iterator const_iterator;
  72
  73         /// Returns a forward iterator addressing the first element in a map
  74         /**
  75             For empty set \code begin() == end() \endcode
  76         */
  77         iterator begin()
  78         {
  79             return base_class::begin();
  80         }
  81
  82         /// Returns an iterator that addresses the location succeeding the last element in a map
  83         /**
  84             Do not use the value returned by <tt>end</tt> function to access any item.
  85             The returned value can be used only to control reaching the end of the set.
  86             For empty set \code begin() == end() \endcode
  87         */
  88         iterator end()
  89         {
  90             return base_class::end();
  91         }
  92
  93         /// Returns a forward const iterator addressing the first element in a map
  94         //@{
  95         const_iterator begin() const
  96         {
  97             return base_class::begin();
  98         }
  99         const_iterator cbegin()
 100         {
 101             return base_class::cbegin();
 102         }
 103         //@}
 104
 105         /// Returns an const iterator that addresses the location succeeding the last element in a map
 106         //@{
 107         const_iterator end() const
 108         {
 109             return base_class::end();
 110         }
 111         const_iterator cend()
 112         {
 113             return base_class::cend();
 114         }
 115         //@}
 116
 117     public:
 118         /// Initialize split-ordered map of default capacity
 119         /**
 120             The default capacity is defined in bucket table constructor.
 121             See intrusive::split_list::expandable_bucket_table, intrusive::split_list::static_ducket_table
 122             which selects by intrusive::split_list::dynamic_bucket_table option.
 123         */
 124         SplitListMap()
 125             : base_class()
 126         {}
 127
 128         /// Initialize split-ordered map
 129         SplitListMap(
 130             size_t nItemCount           ///< estimate average item count
 131             , size_t nLoadFactor = 1    ///< load factor - average item count per bucket. Small integer up to 10, default is 1.
 132             )
 133             : base_class( nItemCount, nLoadFactor )
 134         {}
 135
 136     public:
 137         /// Inserts new node with key and default value
 138         /**
 139             The function creates a node with \p key and default value, and then inserts the node created into the map.
 140
 141             Preconditions:
 142             - The \ref key_type should be constructible from value of type \p K.
 143                 In trivial case, \p K is equal to \ref key_type.
 144             - The \ref mapped_type should be default-constructible.
 145
 146             Returns an iterator pointed to inserted value, or \p end() if inserting is failed
 147         */
 148         template <typename K>
 149         iterator insert( K const& key )
 150         {
 151             //TODO: pass arguments by reference (make_pair makes copy)
 152             return base_class::insert( std::make_pair( key, mapped_type() ) );
 153         }
 154
 155         /// Inserts new node
 156         /**
 157             The function creates a node with copy of \p val value
 158             and then inserts the node created into the map.
 159
 160             Preconditions:
 161             - The \ref key_type should be constructible from \p key of type \p K.
 162             - The \ref mapped_type should be constructible from \p val of type \p V.
 163
 164             Returns an iterator pointed to inserted value, or \p end() if inserting is failed
 165         */
 166         template <typename K, typename V>
 167         iterator insert( K const& key, V const& val )
 168         {
 169             //TODO: pass arguments by reference (make_pair makes copy)
 170             return base_class::insert( std::make_pair( key, val ) );
 171         }
 172
 173         /// Inserts new node and initialize it by a functor
 174         /**
 175             This function inserts new node with key \p key and if inserting is successful then it calls
 176             \p func functor with signature
 177             \code
 178             struct functor {
 179                 void operator()( value_type& item );
 180             };
 181             \endcode
 182
 183             The argument \p item of user-defined functor \p func is the reference
 184             to the map's item inserted. <tt>item.second</tt> is a reference to item's value that may be changed.
 185             User-defined functor \p func should guarantee that during changing item's value no any other changes
 186             could be made on this map's item by concurrent threads.
 187             The user-defined functor can be passed by reference using \p std::ref
 188             and it is called only if the inserting is successful.
 189
 190             The key_type should be constructible from value of type \p K.
 191
 192             The function allows to split creating of new item into two part:
 193             - create item from \p key;
 194             - insert new item into the map;
 195             - if inserting is successful, initialize the value of item by calling \p f functor
 196
 197             This can be useful if complete initialization of object of \p mapped_type is heavyweight and
 198             it is preferable that the initialization should be completed only if inserting is successful.
 199
 200             Returns an iterator pointed to inserted value, or \p end() if inserting is failed
 201         */
 202         template <typename K, typename Func>
 203         iterator insert_key( const K& key, Func func )
 204         {
 205             iterator it = insert( key );
 206             if ( it != end() )
 207                 func( (*it) );
 208             return it;
 209         }
 210
 211         /// For key \p key inserts data of type \ref mapped_type constructed with <tt>std::forward<Args>(args)...</tt>
 212         /**
 213             \p key_type should be constructible from type \p K
 214
 215             Returns \p true if inserting successful, \p false otherwise.
 216         */
 217         template <typename K, typename... Args>
 218         iterator emplace( K&& key, Args&&... args )
 219         {
 220             return base_class::emplace( std::forward<K>(key), std::move(mapped_type(std::forward<Args>(args)...)));
 221         }
 222
 223         /// Ensures that the key \p key exists in the map
 224         /**
 225             The operation inserts new item if the key \p key is not found in the map.
 226             Otherwise, the function returns an iterator that points to item found.
 227
 228             Returns <tt> std::pair<iterator, bool>  </tt> where \p first is an iterator pointing to
 229             item found or inserted, \p second is true if new item has been added or \p false if the item
 230             already is in the list.
 231         */
 232         template <typename K>
 233         std::pair<iterator, bool> ensure( K const& key )
 234         {
 235             //TODO: pass arguments by reference (make_pair makes copy)
 236             return base_class::ensure( std::make_pair( key, mapped_type() ));
 237         }
 238
 239         /// Find the key \p key
 240         /** \anchor cds_nonintrusive_SplitListMap_nogc_find
 241
 242             The function searches the item with key equal to \p key
 243             and returns an iterator pointed to item found if the key is found,
 244             and \ref end() otherwise
 245         */
 246         template <typename K>
 247         iterator find( K const& key )
 248         {
 249             return base_class::find( key );
 250         }
 251
 252         /// Finds the key \p val using \p pred predicate for searching
 253         /**
 254             The function is an analog of \ref cds_nonintrusive_SplitListMap_nogc_find "find(K const&)"
 255             but \p pred is used for key comparing.
 256             \p Less functor has the interface like \p std::less.
 257             \p Less must imply the same element order as the comparator used for building the map.
 258         */
 259         template <typename K, typename Less>
 260         iterator find_with( K const& key, Less pred )
 261         {
 262             return base_class::find_with( key, cds::details::predicate_wrapper<value_type, Less, key_accessor>() );
 263         }
 264
 265         /// Checks if the map is empty
 266         /**
 267             Emptiness is checked by item counting: if item count is zero then the map is empty.
 268             Thus, the correct item counting feature is an important part of Michael's map implementation.
 269         */
 270         bool empty() const
 271         {
 272             return base_class::empty();
 273         }
 274
 275         /// Returns item count in the map
 276         size_t size() const
 277         {
 278             return base_class::size();
 279         }
 280     };
 281 }}  // namespace cds::container
 282
 283
 284 #endif // #ifndef __CDS_CONTAINER_SPLIT_LIST_MAP_NOGC_H