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