1 // The Funnelsort Project - Cache oblivious sorting algorithm implementation
2 // Copyright (C) 2005 Kristoffer Vinther
3 //
4 // This program is free software; you can redistribute it and/or modify
5 // it under the terms of the GNU General Public License as published by
6 // the Free Software Foundation; either version 2 of the License, or
7 // (at your option) any later version.
8 //
9 // This program is distributed in the hope that it will be useful,
10 // but WITHOUT ANY WARRANTY; without even the implied warranty of
11 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 // GNU General Public License for more details.
13 //
14 // You should have received a copy of the GNU General Public License
15 // along with this program; if not, write to the Free Software
16 // Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA
17
18 #ifndef FUNNEL_H_INCLUDED__
19 #define FUNNEL_H_INCLUDED__
20
21 #include <cassert>
22 #include <memory>
23 #include <utility>
24 #include <iterator>
25 #include <functional>
26 #include <stdexcept>
27 #include <cmath>
28
29 namespace iosort
30 {
31
32 typedef unsigned short height_t;
33 typedef unsigned short basic_order_t;
34 typedef unsigned int order_t;
35
36 template<int order>
logc(order_t k)37 inline height_t logc(order_t k)
38 {
39 height_t h = 0;
40 for( order_t i=k-1; i; h++, i/=order );
41 return h;
42 }
43 /* Computes floor(log()), not ceil(log()) :( - Also beware of little- and bigendianness(?)
44 template<>
45 inline height_t logf<2>(order_t k)
46 {
47 float f = static_cast<float>(k);
48 return static_cast<height_t>(((*reinterpret_cast<int*>(&f)) >> 23) - 127);
49 }*/
50 template<int order>
pow_of_order(height_t h)51 inline order_t pow_of_order(height_t h)
52 {
53 order_t k = 1;
54 for( ; h; h--, k*=order );
55 return k;
56 }
57 template<>
58 inline order_t pow_of_order<2>(height_t h)
59 { return 1<<h; }
60 template<>
61 inline order_t pow_of_order<4>(height_t h)
62 { return 1<<(2*h); }
63 template<>
64 inline order_t pow_of_order<8>(height_t h)
65 { return 1<<(3*h); }
66 template<>
67 inline order_t pow_of_order<16>(height_t h)
68 { return 1<<(4*h); }
69
70 template<int order>
71 class bfs_index
72 {
73 public:
bfs_index()74 inline bfs_index() : i(1) { }
order_t()75 inline operator order_t() const
76 { return i; }
77 inline bfs_index<order> operator=(const bfs_index<order>& rhs)
78 { i = rhs.i; return *this; }
79 inline bool operator==(const bfs_index<order>& rhs) const
80 { return i == rhs.i; }
81 inline bool operator!=(const bfs_index<order>& rhs) const
82 { return i != rhs.i; }
child(basic_order_t ch)83 inline void child(basic_order_t ch)
84 { i = static_cast<order_t>(order*(i-1)+ch+2); }
parent()85 inline void parent()
86 { /*assert( i>1 );*/ i = static_cast<order_t>((i-2)/order+1); }
child_index()87 inline basic_order_t child_index() const
88 { /*assert( i>1 );*/ return static_cast<basic_order_t>((i+order-2) % order); }
89 private:
90 order_t i;
91 };
92
93 template<int order=2>
94 class default_splitter
95 {
96 static const int alpha = 16;
97 public:
98 template<class diff_type>
prefered_order_output(diff_type N)99 static inline order_t prefered_order_output(diff_type N)
100 { return static_cast<order_t>(std::sqrt(static_cast<double>(N)/alpha)); }
101 template<class diff_type>
prefered_order_input(diff_type N)102 static inline order_t prefered_order_input(diff_type N)
103 { assert( false ); return static_cast<order_t>(std::sqrt(static_cast<double>(N)/alpha)); }
switch_to_cache_aware()104 static inline size_t switch_to_cache_aware()
105 { return static_cast<size_t>(alpha*(order+1)*(order+1)); }
split(height_t h)106 static inline height_t split(height_t h)
107 { return h/2; }
out_buffer_size(order_t k)108 static inline size_t out_buffer_size(order_t k)
109 { return static_cast<size_t>(alpha*k*k); }
110 };
111
operatornop_refill112 template<class FwIt> struct nop_refill { template<class Merger> inline bool operator()(const Merger*, FwIt, FwIt)
113 { return false; } };
114
115
116 template<class,int,class,class,class,class>
117 class special_ { };
118
119 template<class RanIt, int Order=2, class Splitter = default_splitter<Order>, class Pred = std::less<typename std::iterator_traits<RanIt>::value_type>, class Refiller = nop_refill<RanIt>, class Alloc = std::allocator<typename std::iterator_traits<RanIt>::value_type> >
120 class merge_tree
121 {
122 friend class special_<RanIt,Order,Splitter,Pred,Refiller,Alloc>;
123 public:
124 typedef unsigned int order_t;
125 enum order_tag_ { order = Order };
126 enum mmth_tag_ { MAX_MERGE_TREE_HEIGHT = 16 };
127 typedef Splitter splitter;
128 typedef typename std::iterator_traits<RanIt>::value_type value_type;
129 typedef Alloc allocator;
130 typedef RanIt iterator;
131 typedef Pred predicate;
132 template<class NewRefiller>
133 struct rebind { typedef merge_tree<iterator, order, splitter, predicate, NewRefiller, allocator> other; };
134 private:
135 struct Node;
136 friend struct Node;
137 typedef typename allocator::pointer TPtr;
138 typedef typename allocator::size_type size_type;
139 typedef typename allocator::template rebind<Node>::other nallocator;
140 typedef typename nallocator::pointer NPtr;
141 struct Node
142 {
143 struct Edge
144 {
145 typedef typename allocator::pointer TPtr;
146 typedef typename allocator::template rebind<Node>::other nallocator;
147 typedef typename nallocator::pointer NPtr;
148 inline void construct(order_t k, height_t height, size_t *buf_size, allocator alloc, nallocator nalloc);
149 inline void destroy(allocator alloc, nallocator nalloc);
150 typename allocator::template rebind<Node>::other::pointer child;
151 typename allocator::pointer head, tail, begin, end;
152 private:
153 static inline void fill_dflt(TPtr b, TPtr e, allocator alloc);
154 } edges[order];
155 inline void construct(order_t k, height_t height, size_t *buf_size, allocator alloc, nallocator nalloc);
156 inline void destroy(allocator alloc, nallocator nalloc);
157 };
158 typedef std::pair<RanIt,RanIt> stream_t;
159 typedef typename allocator::template rebind<stream_t>::other sallocator;
160 typedef typename sallocator::pointer SPtr;
161 public:
merge_tree(order_t k)162 inline merge_tree(order_t k) : k(k), cold(true)
163 { construct(k); }
merge_tree(order_t k,const allocator & alloc)164 inline merge_tree(order_t k, const allocator& alloc) : k(k), cold(true), alloc(alloc), salloc(alloc), nalloc(alloc)
165 { construct(k); }
166 ~merge_tree();
167
min_order()168 static inline order_t min_order()
169 { return order; }
170
171 class stream
172 {
173 private:
174 SPtr pair;
175 public:
stream(SPtr pair)176 stream(SPtr pair) : pair(pair) { }
begin()177 inline RanIt& begin()
178 { return pair->first; }
end()179 inline RanIt& end()
180 { return pair->second; }
181 };
182 class stream_iterator
183 {
184 private:
185 SPtr ptr;
186 public:
stream_iterator(SPtr ptr)187 stream_iterator(SPtr ptr) : ptr(ptr) { }
188 inline order_t operator-(const stream_iterator& rhs)
189 { return static_cast<order_t>(ptr-rhs.ptr); }
190 inline stream operator*()
191 { return stream(ptr); }
192 inline stream_iterator& operator++()
193 { ++ptr; return *this; }
194 inline stream_iterator& operator++(int)
195 {
196 stream_iterator ret = stream_iterator(ptr);
197 ++ptr;
198 return ret;
199 }
200 inline bool operator==(const stream_iterator& rhs)
201 { return ptr == rhs.ptr; }
202 inline bool operator!=(const stream_iterator& rhs)
203 { return ptr != rhs.ptr; }
204 };
205
add_stream(RanIt begin,RanIt end)206 inline void add_stream(RanIt begin, RanIt end)
207 { *last_stream++ = std::make_pair(begin,end); }
begin()208 inline stream_iterator begin()
209 { return stream_iterator(input_streams); }
end()210 inline stream_iterator end()
211 { return stream_iterator(last_stream); }
212 inline void reset();
213
set_refiller(const Refiller & r)214 inline void set_refiller(const Refiller& r)
215 { refiller = r; }
get_refiller()216 inline const Refiller& get_refiller() const
217 { return refiller; }
218 template<class FwIt>
empty(FwIt begin,FwIt end)219 inline FwIt empty(FwIt begin, FwIt end)
220 { return empty_buffers(root, begin, end); }
221 template<class OutIt>
empty(OutIt begin)222 inline OutIt empty(OutIt begin)
223 { return empty_buffers(root, begin); }
224
225 template<class It>
226 inline It operator()(It begin, It end);
227 template<class OutIt>
228 inline OutIt operator()(OutIt begin);
229
230 private:
231 template<class FwIt>
232 static inline FwIt empty_buffers(NPtr n, FwIt begin, FwIt end);
233 template<class OutIt>
234 static inline OutIt empty_buffers(NPtr n, OutIt begin);
235
236 static void compute_buffer_sizes(size_type *b, size_type *e);
237 void construct(order_t k);
238
239 inline void go_down(typename Node::Edge& e, bfs_index<order> index);
240 inline void go_down_cold(typename Node::Edge& e, bfs_index<order>& index);
241
242 void warmup(NPtr n, typename Node::Edge& output, bfs_index<order> index);
243
244 template<class FwIt>
245 inline FwIt copy_root(typename Node::Edge& de, bfs_index<order> index, FwIt begin, FwIt end, std::forward_iterator_tag);
246 template<class RIt>
247 inline RIt copy_root(typename Node::Edge& de, bfs_index<order> index, RIt begin, RIt end, std::random_access_iterator_tag);
248 template<class OutIt>
249 inline OutIt copy_root(typename Node::Edge& de, bfs_index<order> index, OutIt begin);
250
251 inline TPtr copy(typename Node::Edge& de, bfs_index<order> index, TPtr b, TPtr e);
252
253 template<class FwIt>
fill_root(FwIt begin,FwIt end)254 inline FwIt fill_root(FwIt begin, FwIt end)
255 { return special_<RanIt,order,Splitter,Pred,Refiller,Alloc>::fill_root(this, begin, end); }
256 template<class OutIt>
fill_root(OutIt begin)257 inline OutIt fill_root(OutIt begin)
258 { return special_<RanIt,order,Splitter,Pred,Refiller,Alloc>::fill_root(this, begin); }
fill(NPtr n,typename Node::Edge & output,bfs_index<order> index)259 void fill(NPtr n, typename Node::Edge& output, bfs_index<order> index)
260 { special_<RanIt,order,Splitter,Pred,Refiller,Alloc>::fill(this, n, output, index); }
fill_leaf(typename Node::Edge & output,bfs_index<order> index)261 void fill_leaf(typename Node::Edge& output, bfs_index<order> index)
262 { special_<RanIt,order,Splitter,Pred,Refiller,Alloc>::fill_leaf(this, output, index); }
263
264 private:
265 order_t k;
266 order_t leaf_index;
267 bool cold;
268 NPtr root;
269 SPtr input_streams, last_stream;
270 Pred comp;
271 allocator alloc;
272 sallocator salloc;
273 nallocator nalloc;
274 Refiller refiller;
275 };
276
277
278
279 /*****
280 * Alloc::pointer iterator template specialization
281 */
282
283 template<int Order, class Splitter, class Pred, class Refiller, class Alloc>
284 class merge_tree<typename Alloc::pointer, Order, Splitter, Pred, Refiller, Alloc>
285 {
286 typedef typename Alloc::pointer RanIt;
287 friend class special_<typename Alloc::pointer,Order,Splitter,Pred,Refiller,Alloc>;
288 public:
289 typedef unsigned int order_t;
290 enum order_tag_ { order = Order };
291 enum mmth_tag_ { MAX_MERGE_TREE_HEIGHT = 16 };
292 typedef Splitter splitter;
293 typedef typename std::iterator_traits<typename Alloc::pointer>::value_type value_type;
294 typedef Alloc allocator;
295 typedef typename Alloc::pointer iterator;
296 typedef Pred predicate;
297 // template<class NewRefiller>
298 // struct rebind { typedef merge_tree<typename Alloc::pointer, Order, Splitter, Pred, NewRefiller, Alloc> other; };
299 private:
300 struct Node;
301 friend struct Node;
302 typedef typename allocator::pointer TPtr;
303 typedef typename allocator::size_type size_type;
304 typedef typename allocator::template rebind<Node>::other nallocator;
305 typedef typename nallocator::pointer NPtr;
306 struct Node
307 {
308 struct Edge
309 {
310 typedef typename allocator::pointer TPtr;
311 typedef typename allocator::template rebind<Node>::other nallocator;
312 typedef typename nallocator::pointer NPtr;
313 inline Edge** construct(order_t k, height_t height, size_t *buf_size, Edge** edge_list, allocator alloc, nallocator nalloc);
314 inline void destroy(allocator alloc, nallocator nalloc);
315 typename nallocator::pointer child;
316 typename allocator::pointer head, tail, begin, end;
317 private:
318 static inline void fill_dflt(TPtr b, TPtr e, allocator alloc);
319 } edges[order];
320 inline Edge** construct(order_t k, height_t height, size_t *buf_size, Edge** edge_list, allocator alloc, nallocator nalloc);
321 inline void destroy(allocator alloc, nallocator nalloc);
322 };
323 typedef typename Node::Edge* stream_t;
324 typedef typename allocator::template rebind<stream_t>::other sallocator;
325 typedef typename sallocator::pointer SPtr;
326 public:
merge_tree(order_t k)327 inline merge_tree(order_t k) : k(k), cold(true)
328 { construct(k); }
merge_tree(order_t k,const allocator & alloc)329 inline merge_tree(order_t k, const allocator& alloc) : k(k), cold(true), alloc(alloc), salloc(alloc), nalloc(alloc)
330 { construct(k); }
331 ~merge_tree();
332
min_order()333 static inline order_t min_order()
334 { return order; }
335
336 class stream
337 {
338 private:
339 stream_t edge;
340 public:
stream(stream_t edge)341 inline stream(stream_t edge) : edge(edge) { }
begin()342 inline typename allocator::pointer& begin()
343 { return edge->head; }
end()344 inline typename allocator::pointer& end()
345 { return edge->tail; }
346 };
347 class stream_iterator
348 {
349 private:
350 SPtr ptr;
351 public:
stream_iterator(SPtr ptr)352 inline stream_iterator(SPtr ptr) : ptr(ptr) { }
353 inline order_t operator-(const stream_iterator& rhs)
354 { return static_cast<order_t>(ptr-rhs.ptr); }
355 inline stream operator*()
356 { return stream(*ptr); }
357 inline stream_iterator& operator++()
358 { ++ptr; return *this; }
359 inline stream_iterator& operator++(int)
360 {
361 stream_iterator ret = stream_iterator(ptr);
362 ++ptr;
363 return ret;
364 }
365 inline bool operator==(const stream_iterator& rhs)
366 { return ptr == rhs.ptr; }
367 inline bool operator!=(const stream_iterator& rhs)
368 { return ptr != rhs.ptr; }
369 };
370
add_stream(typename Alloc::pointer begin,typename Alloc::pointer end)371 inline void add_stream(typename Alloc::pointer begin, typename Alloc::pointer end)
372 { (*last_stream)->head = begin, (*last_stream)->tail = end, ++last_stream; }
begin()373 inline stream_iterator begin()
374 { return input_streams; }
end()375 inline stream_iterator end()
376 { return last_stream; }
377 inline void reset();
378
set_refiller(const Refiller & r)379 inline void set_refiller(const Refiller& r)
380 { refiller = r; }
get_refiller()381 inline const Refiller& get_refiller() const
382 { return refiller; }
383 template<class FwIt>
empty(FwIt begin,FwIt end)384 inline FwIt empty(FwIt begin, FwIt end)
385 { return empty_buffers(root, begin, end); }
386 template<class OutIt>
empty(OutIt begin)387 inline OutIt empty(OutIt begin)
388 { return empty_buffers(root, begin); }
389
390 template<class FwIt>
391 inline FwIt operator()(FwIt begin, FwIt end);
392 template<class OutIt>
393 inline OutIt operator()(OutIt begin);
394 private:
395 template<class FwIt>
396 static inline FwIt empty_buffers(NPtr n, FwIt begin, FwIt end);
397 template<class OutIt>
398 static inline OutIt empty_buffers(NPtr n, OutIt begin);
399
400 void construct(order_t k);
401 static void compute_buffer_sizes(size_type *b, size_type *e);
402
403 static inline void go_down(typename Node::Edge& e, Pred comp);
404 static inline void go_down_cold(typename Node::Edge& e, Pred comp);
405
406 static void warmup(NPtr n, typename Node::Edge& output, Pred comp);
407
408 template<class OutIt>
409 static inline OutIt copy(typename Node::Edge& de, OutIt begin, Pred comp);
410 template<class FwIt>
411 static inline FwIt copy(typename Node::Edge& de, FwIt begin, FwIt end, Pred comp, std::forward_iterator_tag);
412 template<class RIt>
413 static inline RIt copy(typename Node::Edge& de, RIt begin, RIt end, Pred comp, std::random_access_iterator_tag);
414
415 template<class OutIt>
fill(NPtr n,OutIt begin,Pred comp)416 static inline OutIt fill(NPtr n, OutIt begin, Pred comp)
417 { return special_<typename Alloc::pointer,order,Splitter,Pred,Refiller,Alloc>::fill(n, begin, comp); }
418 template<class FwIt>
fill(NPtr n,FwIt begin,FwIt end,Pred comp)419 static inline FwIt fill(NPtr n, FwIt begin, FwIt end, Pred comp)
420 { return special_<typename Alloc::pointer,Order,Splitter,Pred,Refiller,Alloc>::fill(n, begin, end, comp); }
421 private:
422 order_t k;
423 order_t leaf_index;
424 bool cold;
425 NPtr root;
426 SPtr input_streams, last_stream;
427 Pred comp;
428 allocator alloc;
429 sallocator salloc;
430 nallocator nalloc;
431 Refiller refiller;
432 };
433
434 } // namespace iosort
435
436 #include "funnel.timpl.h"
437 #endif // FUNNEL_H_INCLUDED__
438