ceph/src/boost/boost/multi_index/detail/rnd_index_ops.hpp

   1 /* Copyright 2003-2015 Joaquin M Lopez Munoz.
   2  * Distributed under the Boost Software License, Version 1.0.
   3  * (See accompanying file LICENSE_1_0.txt or copy at
   4  * http://www.boost.org/LICENSE_1_0.txt)
   5  *
   6  * See http://www.boost.org/libs/multi_index for library home page.
   7  */
   8
   9 #ifndef BOOST_MULTI_INDEX_DETAIL_RND_INDEX_OPS_HPP
  10 #define BOOST_MULTI_INDEX_DETAIL_RND_INDEX_OPS_HPP
  11
  12 #if defined(_MSC_VER)
  13 #pragma once
  14 #endif
  15
  16 #include <boost/config.hpp> /* keep it first to prevent nasty warns in MSVC */
  17 #include <algorithm>
  18 #include <boost/multi_index/detail/rnd_index_ptr_array.hpp>
  19
  20 namespace boost{
  21
  22 namespace multi_index{
  23
  24 namespace detail{
  25
  26 /* Common code for random_access_index memfuns having templatized and
  27  * non-templatized versions.
  28  */
  29
  30 template<typename Node,typename Allocator,typename Predicate>
  31 Node* random_access_index_remove(
  32   random_access_index_ptr_array<Allocator>& ptrs,Predicate pred)
  33 {
  34   typedef typename Node::value_type value_type;
  35   typedef typename Node::impl_ptr_pointer impl_ptr_pointer;
  36
  37   impl_ptr_pointer first=ptrs.begin(),
  38                    res=first,
  39                    last=ptrs.end();
  40   for(;first!=last;++first){
  41     if(!pred(
  42         const_cast<const value_type&>(Node::from_impl(*first)->value()))){
  43       if(first!=res){
  44         std::swap(*first,*res);
  45         (*first)->up()=first;
  46         (*res)->up()=res;
  47       }
  48       ++res;
  49     }
  50   }
  51   return Node::from_impl(*res);
  52 }
  53
  54 template<typename Node,typename Allocator,class BinaryPredicate>
  55 Node* random_access_index_unique(
  56   random_access_index_ptr_array<Allocator>& ptrs,BinaryPredicate binary_pred)
  57 {
  58   typedef typename Node::value_type       value_type;
  59   typedef typename Node::impl_ptr_pointer impl_ptr_pointer;
  60
  61   impl_ptr_pointer first=ptrs.begin(),
  62                    res=first,
  63                    last=ptrs.end();
  64   if(first!=last){
  65     for(;++first!=last;){
  66       if(!binary_pred(
  67            const_cast<const value_type&>(Node::from_impl(*res)->value()),
  68            const_cast<const value_type&>(Node::from_impl(*first)->value()))){
  69         ++res;
  70         if(first!=res){
  71           std::swap(*first,*res);
  72           (*first)->up()=first;
  73           (*res)->up()=res;
  74         }
  75       }
  76     }
  77     ++res;
  78   }
  79   return Node::from_impl(*res);
  80 }
  81
  82 template<typename Node,typename Allocator,typename Compare>
  83 void random_access_index_inplace_merge(
  84   const Allocator& al,
  85   random_access_index_ptr_array<Allocator>& ptrs,
  86   BOOST_DEDUCED_TYPENAME Node::impl_ptr_pointer first1,Compare comp)
  87 {
  88   typedef typename Node::value_type       value_type;
  89   typedef typename Node::impl_pointer     impl_pointer;
  90   typedef typename Node::impl_ptr_pointer impl_ptr_pointer;
  91
  92   auto_space<impl_pointer,Allocator> spc(al,ptrs.size());
  93
  94   impl_ptr_pointer first0=ptrs.begin(),
  95                    last0=first1,
  96                    last1=ptrs.end(),
  97                    out=spc.data();
  98   while(first0!=last0&&first1!=last1){
  99     if(comp(
 100         const_cast<const value_type&>(Node::from_impl(*first1)->value()),
 101         const_cast<const value_type&>(Node::from_impl(*first0)->value()))){
 102       *out++=*first1++;
 103     }
 104     else{
 105       *out++=*first0++;
 106     }
 107   }
 108   std::copy(&*first0,&*last0,&*out);
 109   std::copy(&*first1,&*last1,&*out);
 110
 111   first1=ptrs.begin();
 112   out=spc.data();
 113   while(first1!=last1){
 114     *first1=*out++;
 115     (*first1)->up()=first1;
 116     ++first1;
 117   }
 118 }
 119
 120 /* sorting */
 121
 122 /* auxiliary stuff */
 123
 124 template<typename Node,typename Compare>
 125 struct random_access_index_sort_compare
 126 {
 127   typedef typename Node::impl_pointer first_argument_type;
 128   typedef typename Node::impl_pointer second_argument_type;
 129   typedef bool                        result_type;
 130
 131   random_access_index_sort_compare(Compare comp_=Compare()):comp(comp_){}
 132
 133   bool operator()(
 134     typename Node::impl_pointer x,typename Node::impl_pointer y)const
 135   {
 136     typedef typename Node::value_type value_type;
 137
 138     return comp(
 139       const_cast<const value_type&>(Node::from_impl(x)->value()),
 140       const_cast<const value_type&>(Node::from_impl(y)->value()));
 141   }
 142
 143 private:
 144   Compare comp;
 145 };
 146
 147 template<typename Node,typename Allocator,class Compare>
 148 void random_access_index_sort(
 149   const Allocator& al,
 150   random_access_index_ptr_array<Allocator>& ptrs,
 151   Compare comp)
 152 {
 153   /* The implementation is extremely simple: an auxiliary
 154    * array of pointers is sorted using stdlib facilities and
 155    * then used to rearrange the index. This is suboptimal
 156    * in space and time, but has some advantages over other
 157    * possible approaches:
 158    *   - Use std::stable_sort() directly on ptrs using some
 159    *     special iterator in charge of maintaining pointers
 160    *     and up() pointers in sync: we cannot guarantee
 161    *     preservation of the container invariants in the face of
 162    *     exceptions, if, for instance, std::stable_sort throws
 163    *     when ptrs transitorily contains duplicate elements.
 164    *   - Rewrite the internal algorithms of std::stable_sort
 165    *     adapted for this case: besides being a fair amount of
 166    *     work, making a stable sort compatible with Boost.MultiIndex
 167    *     invariants (basically, no duplicates or missing elements
 168    *     even if an exception is thrown) is complicated, error-prone
 169    *     and possibly won't perform much better than the
 170    *     solution adopted.
 171    */
 172
 173   if(ptrs.size()<=1)return;
 174
 175   typedef typename Node::impl_pointer       impl_pointer;
 176   typedef typename Node::impl_ptr_pointer   impl_ptr_pointer;
 177   typedef random_access_index_sort_compare<
 178     Node,Compare>                           ptr_compare;
 179
 180   impl_ptr_pointer   first=ptrs.begin();
 181   impl_ptr_pointer   last=ptrs.end();
 182   auto_space<
 183     impl_pointer,
 184     Allocator>       spc(al,ptrs.size());
 185   impl_ptr_pointer   buf=spc.data();
 186
 187   std::copy(&*first,&*last,&*buf);
 188   std::stable_sort(&*buf,&*buf+ptrs.size(),ptr_compare(comp));
 189
 190   while(first!=last){
 191     *first=*buf++;
 192     (*first)->up()=first;
 193     ++first;
 194   }
 195 }
 196
 197 } /* namespace multi_index::detail */
 198
 199 } /* namespace multi_index */
 200
 201 } /* namespace boost */
 202
 203 #endif