gdax-orderbook-hpp/demo/dependencies/libcds-2.3.2/cds/container/striped_set/std_vector.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_STRIPED_SET_STD_VECTOR_ADAPTER_H
  32 #define CDSLIB_CONTAINER_STRIPED_SET_STD_VECTOR_ADAPTER_H
  33
  34 #include <functional>   // ref
  35 #include <vector>
  36 #include <algorithm>    // std::lower_bound
  37 #include <utility>      // std::pair
  38 #include <cds/container/striped_set/adapter.h>     // lower_bound
  39
  40 //@cond
  41 namespace cds { namespace container {
  42     namespace striped_set {
  43
  44         // Copy policy for std::vector
  45         template <typename T, typename Alloc>
  46         struct copy_item_policy< std::vector< T, Alloc > >
  47         {
  48             typedef std::vector< T, Alloc > vector_type;
  49             typedef typename vector_type::iterator iterator;
  50
  51             void operator()( vector_type& vec, iterator itInsert, iterator itWhat )
  52             {
  53                 vec.insert( itInsert, *itWhat );
  54             }
  55         };
  56
  57         // Swap policy for std::vector
  58         template <typename T, typename Alloc>
  59         struct swap_item_policy< std::vector< T, Alloc > >
  60         {
  61             typedef std::vector< T, Alloc > vector_type;
  62             typedef typename vector_type::iterator iterator;
  63
  64             void operator()( vector_type& vec, iterator itInsert, iterator itWhat )
  65             {
  66                 typename vector_type::value_type newVal;
  67                 itInsert = vec.insert( itInsert, newVal );
  68                 std::swap( *itInsert, *itWhat );
  69             }
  70         };
  71
  72         // Move policy for std::vector
  73         template <typename T, typename Alloc>
  74         struct move_item_policy< std::vector< T, Alloc > >
  75         {
  76             typedef std::vector< T, Alloc > vector_type;
  77             typedef typename vector_type::iterator iterator;
  78
  79             void operator()( vector_type& vec, iterator itInsert, iterator itWhat )
  80             {
  81                 vec.insert( itInsert, std::move( *itWhat ));
  82             }
  83         };
  84
  85     }   // namespace striped_set
  86 }} // namespace cds::container
  87
  88 namespace cds { namespace intrusive { namespace striped_set {
  89
  90     /// std::vector adapter for hash set bucket
  91     template <typename T, class Alloc, typename... Options>
  92     class adapt< std::vector<T, Alloc>, Options... >
  93     {
  94     public:
  95         typedef std::vector<T, Alloc>     container_type          ;   ///< underlying container type
  96
  97     private:
  98         /// Adapted container type
  99         class adapted_container: public cds::container::striped_set::adapted_sequential_container
 100         {
 101         public:
 102             typedef typename container_type::value_type value_type  ;   ///< value type stored in the container
 103             typedef typename container_type::iterator      iterator ;   ///< container iterator
 104             typedef typename container_type::const_iterator const_iterator ;    ///< container const iterator
 105
 106             static bool const has_find_with = true;
 107             static bool const has_erase_with = true;
 108
 109         private:
 110             //@cond
 111             typedef typename cds::opt::details::make_comparator_from_option_list< value_type, Options... >::type key_comparator;
 112
 113             typedef typename cds::opt::select<
 114                 typename cds::opt::value<
 115                     typename cds::opt::find_option<
 116                         cds::opt::copy_policy< cds::container::striped_set::move_item >
 117                         , Options...
 118                     >::type
 119                 >::copy_policy
 120                 , cds::container::striped_set::copy_item, cds::container::striped_set::copy_item_policy<container_type>
 121                 , cds::container::striped_set::swap_item, cds::container::striped_set::swap_item_policy<container_type>
 122                 , cds::container::striped_set::move_item, cds::container::striped_set::move_item_policy<container_type>
 123             >::type copy_item;
 124
 125             struct find_predicate
 126             {
 127                 bool operator()( value_type const& i1, value_type const& i2) const
 128                 {
 129                     return key_comparator()( i1, i2 ) < 0;
 130                 }
 131
 132                 template <typename Q>
 133                 bool operator()( Q const& i1, value_type const& i2) const
 134                 {
 135                     return key_comparator()( i1, i2 ) < 0;
 136                 }
 137
 138                 template <typename Q>
 139                 bool operator()( value_type const& i1, Q const& i2) const
 140                 {
 141                     return key_comparator()( i1, i2 ) < 0;
 142                 }
 143             };
 144             //@endcond
 145
 146         private:
 147             //@cond
 148             container_type  m_Vector;
 149             //@endcond
 150
 151         public:
 152
 153             template <typename Q, typename Func>
 154             bool insert( const Q& val, Func f )
 155             {
 156                 iterator it = std::lower_bound( m_Vector.begin(), m_Vector.end(), val, find_predicate());
 157                 if ( it == m_Vector.end() || key_comparator()( val, *it ) != 0 ) {
 158                     value_type newItem( val );
 159                     it = m_Vector.insert( it, newItem );
 160                     f( *it );
 161                     return true;
 162                 }
 163                 return false;
 164             }
 165
 166             template <typename... Args>
 167             bool emplace( Args&&... args )
 168             {
 169                 value_type val( std::forward<Args>(args)... );
 170                 iterator it = std::lower_bound( m_Vector.begin(), m_Vector.end(), val, find_predicate());
 171                 if ( it == m_Vector.end() || key_comparator()( val, *it ) != 0 ) {
 172                     it = m_Vector.emplace( it, std::move( val ));
 173                     return true;
 174                 }
 175                 return false;
 176             }
 177
 178             template <typename Q, typename Func>
 179             std::pair<bool, bool> update( const Q& val, Func func, bool bAllowInsert )
 180             {
 181                 iterator it = std::lower_bound( m_Vector.begin(), m_Vector.end(), val, find_predicate());
 182                 if ( it == m_Vector.end() || key_comparator()( val, *it ) != 0 ) {
 183                     // insert new
 184                     if ( !bAllowInsert )
 185                         return std::make_pair( false, false );
 186
 187                     value_type newItem( val );
 188                     it = m_Vector.insert( it, newItem );
 189                     func( true, *it, val );
 190                     return std::make_pair( true, true );
 191                 }
 192                 else {
 193                     // already exists
 194                     func( false, *it, val );
 195                     return std::make_pair( true, false );
 196                 }
 197             }
 198
 199             template <typename Q, typename Func>
 200             bool erase( const Q& key, Func f )
 201             {
 202                 iterator it = std::lower_bound( m_Vector.begin(), m_Vector.end(), key, find_predicate());
 203                 if ( it == m_Vector.end() || key_comparator()( key, *it ) != 0 )
 204                     return false;
 205
 206                 // key exists
 207                 f( *it );
 208                 m_Vector.erase( it );
 209                 return true;
 210             }
 211
 212             template <typename Q, typename Less, typename Func>
 213             bool erase( const Q& key, Less pred, Func f )
 214             {
 215                 iterator it = std::lower_bound( m_Vector.begin(), m_Vector.end(), key, pred );
 216                 if ( it == m_Vector.end() || pred( key, *it ) || pred( *it, key ))
 217                     return false;
 218
 219                 // key exists
 220                 f( *it );
 221                 m_Vector.erase( it );
 222                 return true;
 223             }
 224
 225             template <typename Q, typename Func>
 226             bool find( Q& val, Func f )
 227             {
 228                 iterator it = std::lower_bound( m_Vector.begin(), m_Vector.end(), val, find_predicate());
 229                 if ( it == m_Vector.end() || key_comparator()( val, *it ) != 0 )
 230                     return false;
 231
 232                 // key exists
 233                 f( *it, val );
 234                 return true;
 235             }
 236
 237             template <typename Q, typename Less, typename Func>
 238             bool find( Q& val, Less pred, Func f )
 239             {
 240                 iterator it = std::lower_bound( m_Vector.begin(), m_Vector.end(), val, pred );
 241                 if ( it == m_Vector.end() || pred( val, *it ) || pred( *it, val ))
 242                     return false;
 243
 244                 // key exists
 245                 f( *it, val );
 246                 return true;
 247             }
 248
 249
 250             void clear()
 251             {
 252                 m_Vector.clear();
 253             }
 254
 255             iterator begin()                { return m_Vector.begin(); }
 256             const_iterator begin() const    { return m_Vector.begin(); }
 257             iterator end()                  { return m_Vector.end(); }
 258             const_iterator end() const      { return m_Vector.end(); }
 259
 260             void move_item( adapted_container& /*from*/, iterator itWhat )
 261             {
 262                 iterator it = std::lower_bound( m_Vector.begin(), m_Vector.end(), *itWhat, find_predicate());
 263                 assert( it == m_Vector.end() || key_comparator()( *itWhat, *it ) != 0 );
 264
 265                 copy_item()( m_Vector, it, itWhat );
 266             }
 267
 268             size_t size() const
 269             {
 270                 return m_Vector.size();
 271             }
 272         };
 273
 274     public:
 275         typedef adapted_container type ; ///< Result of \p adapt metafunction
 276
 277     };
 278 }}} // namespace cds::intrusive::striped_set
 279
 280 //@endcond
 281
 282 #endif // #ifndef CDSLIB_CONTAINER_STRIPED_SET_STD_VECTOR_ADAPTER_H