1/* Copyright 2003-2020 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/core/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
24namespace boost{
25
26namespace multi_index{
27
28namespace detail{
29
30/* Common code for sequenced_index memfuns having templatized and
31 * non-templatized versions.
32 */
33
34template <typename SequencedIndex,typename Predicate>
35void 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
45template <typename SequencedIndex,class BinaryPredicate>
46void 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
59template <typename SequencedIndex,typename Compare>
60void 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
78template<typename Node,typename Compare>
79void 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
108BOOST_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
115template<typename Node,typename Compare>
116void 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
204

source code of boost/libs/multi_index/include/boost/multi_index/detail/seq_index_ops.hpp