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

   1 /* Copyright 2003-2016 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_SEQ_INDEX_OPS_HPP
  10 #define BOOST_MULTI_INDEX_DETAIL_SEQ_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 <boost/detail/no_exceptions_support.hpp>
  18 #include <boost/multi_index/detail/seq_index_node.hpp>
  19 #include <boost/limits.hpp>
  20 #include <boost/type_traits/aligned_storage.hpp>
  21 #include <boost/type_traits/alignment_of.hpp>
  22 #include <cstddef>
  23
  24 namespace boost{
  25
  26 namespace multi_index{
  27
  28 namespace detail{
  29
  30 /* Common code for sequenced_index memfuns having templatized and
  31  * non-templatized versions.
  32  */
  33
  34 template <typename SequencedIndex,typename Predicate>
  35 void sequenced_index_remove(SequencedIndex& x,Predicate pred)
  36 {
  37   typedef typename SequencedIndex::iterator iterator;
  38   iterator first=x.begin(),last=x.end();
  39   while(first!=last){
  40     if(pred(*first))x.erase(first++);
  41     else ++first;
  42   }
  43 }
  44
  45 template <typename SequencedIndex,class BinaryPredicate>
  46 void sequenced_index_unique(SequencedIndex& x,BinaryPredicate binary_pred)
  47 {
  48   typedef typename SequencedIndex::iterator iterator;
  49   iterator first=x.begin();
  50   iterator last=x.end();
  51   if(first!=last){
  52     for(iterator middle=first;++middle!=last;middle=first){
  53       if(binary_pred(*middle,*first))x.erase(middle);
  54       else first=middle;
  55     }
  56   }
  57 }
  58
  59 template <typename SequencedIndex,typename Compare>
  60 void sequenced_index_merge(SequencedIndex& x,SequencedIndex& y,Compare comp)
  61 {
  62   typedef typename SequencedIndex::iterator iterator;
  63   if(&x!=&y){
  64     iterator first0=x.begin(),last0=x.end();
  65     iterator first1=y.begin(),last1=y.end();
  66     while(first0!=last0&&first1!=last1){
  67       if(comp(*first1,*first0))x.splice(first0,y,first1++);
  68       else ++first0;
  69     }
  70     x.splice(last0,y,first1,last1);
  71   }
  72 }
  73
  74 /* sorting  */
  75
  76 /* auxiliary stuff */
  77
  78 template<typename Node,typename Compare>
  79 void sequenced_index_collate(
  80   BOOST_DEDUCED_TYPENAME Node::impl_type* x,
  81   BOOST_DEDUCED_TYPENAME Node::impl_type* y,
  82   Compare comp)
  83 {
  84   typedef typename Node::impl_type    impl_type;
  85   typedef typename Node::impl_pointer impl_pointer;
  86
  87   impl_pointer first0=x->next();
  88   impl_pointer last0=x;
  89   impl_pointer first1=y->next();
  90   impl_pointer last1=y;
  91   while(first0!=last0&&first1!=last1){
  92     if(comp(
  93         Node::from_impl(first1)->value(),Node::from_impl(first0)->value())){
  94       impl_pointer tmp=first1->next();
  95       impl_type::relink(first0,first1);
  96       first1=tmp;
  97     }
  98     else first0=first0->next();
  99   }
 100   impl_type::relink(last0,first1,last1);
 101 }
 102
 103 /* Some versions of CGG require a bogus typename in counter_spc
 104  * inside sequenced_index_sort if the following is defined
 105  * also inside sequenced_index_sort.
 106  */
 107
 108 BOOST_STATIC_CONSTANT(
 109   std::size_t,
 110   sequenced_index_sort_max_fill=
 111     (std::size_t)std::numeric_limits<std::size_t>::digits+1);
 112
 113 #include <boost/multi_index/detail/ignore_wstrict_aliasing.hpp>
 114
 115 template<typename Node,typename Compare>
 116 void sequenced_index_sort(Node* header,Compare comp)
 117 {
 118   /* Musser's mergesort, see http://www.cs.rpi.edu/~musser/gp/List/lists1.html.
 119    * The implementation is a little convoluted: in the original code
 120    * counter elements and carry are std::lists: here we do not want
 121    * to use multi_index instead, so we do things at a lower level, managing
 122    * directly the internal node representation.
 123    * Incidentally, the implementations I've seen of this algorithm (SGI,
 124    * Dinkumware, STLPort) are not exception-safe: this is. Moreover, we do not
 125    * use any dynamic storage.
 126    */
 127
 128   if(header->next()==header->impl()||
 129      header->next()->next()==header->impl())return;
 130
 131   typedef typename Node::impl_type      impl_type;
 132   typedef typename Node::impl_pointer   impl_pointer;
 133
 134   typedef typename aligned_storage<
 135     sizeof(impl_type),
 136     alignment_of<impl_type>::value
 137   >::type                               carry_spc_type;
 138   carry_spc_type                        carry_spc;
 139   impl_type&                            carry=
 140     *reinterpret_cast<impl_type*>(&carry_spc);
 141   typedef typename aligned_storage<
 142     sizeof(
 143       impl_type
 144         [sequenced_index_sort_max_fill]),
 145     alignment_of<
 146       impl_type
 147         [sequenced_index_sort_max_fill]
 148     >::value
 149   >::type                               counter_spc_type;
 150   counter_spc_type                      counter_spc;
 151   impl_type*                            counter=
 152     reinterpret_cast<impl_type*>(&counter_spc);
 153   std::size_t                           fill=0;
 154
 155   carry.prior()=carry.next()=static_cast<impl_pointer>(&carry);
 156   counter[0].prior()=counter[0].next()=static_cast<impl_pointer>(&counter[0]);
 157
 158   BOOST_TRY{
 159     while(header->next()!=header->impl()){
 160       impl_type::relink(carry.next(),header->next());
 161       std::size_t i=0;
 162       while(i<fill&&counter[i].next()!=static_cast<impl_pointer>(&counter[i])){
 163         sequenced_index_collate<Node>(&carry,&counter[i++],comp);
 164       }
 165       impl_type::swap(
 166         static_cast<impl_pointer>(&carry),
 167         static_cast<impl_pointer>(&counter[i]));
 168       if(i==fill){
 169         ++fill;
 170         counter[fill].prior()=counter[fill].next()=
 171           static_cast<impl_pointer>(&counter[fill]);
 172       }
 173     }
 174
 175     for(std::size_t i=1;i<fill;++i){
 176       sequenced_index_collate<Node>(&counter[i],&counter[i-1],comp);
 177     }
 178     impl_type::swap(
 179       header->impl(),static_cast<impl_pointer>(&counter[fill-1]));
 180   }
 181   BOOST_CATCH(...)
 182   {
 183     impl_type::relink(
 184       header->impl(),carry.next(),static_cast<impl_pointer>(&carry));
 185     for(std::size_t i=0;i<=fill;++i){
 186       impl_type::relink(
 187         header->impl(),counter[i].next(),
 188         static_cast<impl_pointer>(&counter[i]));
 189     }
 190     BOOST_RETHROW;
 191   }
 192   BOOST_CATCH_END
 193 }
 194
 195 #include <boost/multi_index/detail/restore_wstrict_aliasing.hpp>
 196
 197 } /* namespace multi_index::detail */
 198
 199 } /* namespace multi_index */
 200
 201 } /* namespace boost */
 202
 203 #endif