funnel.h

Go to the documentation of this file.

// The Funnelsort Project  -  Cache oblivious sorting algorithm implementation
// Copyright (C) 2005  Kristoffer Vinther
//
// This program is free software; you can redistribute it and/or modify
// it under the terms of the GNU General Public License as published by
// the Free Software Foundation; either version 2 of the License, or
// (at your option) any later version.
//
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.
//
// You should have received a copy of the GNU General Public License
// along with this program; if not, write to the Free Software
// Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA

#ifndef FUNNEL_H_INCLUDED__
#define FUNNEL_H_INCLUDED__

#include <cassert>
#include <memory>
#include <utility>
#include <iterator>
#include <functional>
#include <stdexcept>
#include <cmath>

namespace iosort
{

typedef unsigned short height_t;
typedef unsigned short basic_order_t;
typedef unsigned int order_t;

template<int order>
inline height_t logc(order_t k)
{
    height_t h = 0;
    for( order_t i=k-1; i; h++, i/=order );
    return h;
}
/* Computes floor(log()), not ceil(log()) :(  - Also beware of little- and bigendianness(?)
template<>
inline height_t logf<2>(order_t k)
{
    float f = static_cast<float>(k);
    return static_cast<height_t>(((*reinterpret_cast<int*>(&f)) >> 23) - 127);
}*/
template<int order>
inline order_t pow_of_order(height_t h)
{
    order_t k = 1;
    for( ; h; h--, k*=order );
    return k;
}
template<>
inline order_t pow_of_order<2>(height_t h)
    { return 1<<h; }
template<>
inline order_t pow_of_order<4>(height_t h)
    { return 1<<(2*h); }
template<>
inline order_t pow_of_order<8>(height_t h)
    { return 1<<(3*h); }
template<>
inline order_t pow_of_order<16>(height_t h)
    { return 1<<(4*h); }

template<int order>
class bfs_index
{
public:
    inline bfs_index() : i(1) { }
    inline operator order_t() const
        { return i; }
    inline bfs_index<order> operator=(const bfs_index<order>& rhs)
        { i = rhs.i; return *this; }
    inline bool operator==(const bfs_index<order>& rhs) const
        { return i == rhs.i; }
    inline bool operator!=(const bfs_index<order>& rhs) const
        { return i != rhs.i; }
    inline void child(basic_order_t ch)
        { i = static_cast<order_t>(order*(i-1)+ch+2); }
    inline void parent()
        { /*assert( i>1 );*/ i = static_cast<order_t>((i-2)/order+1); }
    inline basic_order_t child_index() const
        { /*assert( i>1 );*/ return static_cast<basic_order_t>((i+order-2) % order); }
private:
    order_t i;
};

template<int order=2>
class default_splitter
{
    static const int alpha = 16;
public:
    template<class diff_type>
    static inline order_t prefered_order_output(diff_type N)
        { return static_cast<order_t>(std::sqrt(static_cast<double>(N)/alpha)); }
    template<class diff_type>
    static inline order_t prefered_order_input(diff_type N)
        { assert( false ); return static_cast<order_t>(std::sqrt(static_cast<double>(N)/alpha)); }
    static inline size_t switch_to_cache_aware()
        { return static_cast<size_t>(alpha*(order+1)*(order+1)); }
    static inline height_t split(height_t h)
        { return h/2; }
    static inline size_t out_buffer_size(order_t k)
        { return static_cast<size_t>(alpha*k*k); }
};

template<class FwIt> struct nop_refill { template<class Merger> inline bool operator()(const Merger*, FwIt, FwIt)
    { return false; } };


template<class,int,class,class,class,class>
class special_ { };

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> >
class merge_tree
{
    friend class special_<RanIt,Order,Splitter,Pred,Refiller,Alloc>;
public:
    typedef unsigned int order_t;
    enum order_tag_ { order = Order };
    enum mmth_tag_ { MAX_MERGE_TREE_HEIGHT = 16 };
    typedef Splitter splitter;
    typedef typename std::iterator_traits<RanIt>::value_type value_type;
    typedef Alloc allocator;
    typedef RanIt iterator;
    typedef Pred predicate;
    template<class NewRefiller>
    struct rebind { typedef merge_tree<iterator, order, splitter, predicate, NewRefiller, allocator> other; };
private:
    struct Node;
    friend struct Node;
    typedef typename allocator::pointer TPtr;
    typedef typename allocator::size_type size_type;
    typedef typename allocator::template rebind<Node>::other nallocator;
    typedef typename nallocator::pointer NPtr;
    struct Node
    {
        struct Edge
        {
            typedef typename allocator::pointer TPtr;
            typedef typename allocator::template rebind<Node>::other nallocator;
            typedef typename nallocator::pointer NPtr;
            inline void construct(order_t k, height_t height, size_t *buf_size, allocator alloc, nallocator nalloc);
            inline void destroy(allocator alloc, nallocator nalloc);
            typename allocator::template rebind<Node>::other::pointer child;
            typename allocator::pointer head, tail, begin, end;
        private:
            static inline void fill_dflt(TPtr b, TPtr e, allocator alloc);
        } edges[order];
        inline void construct(order_t k, height_t height, size_t *buf_size, allocator alloc, nallocator nalloc);
        inline void destroy(allocator alloc, nallocator nalloc);
    };
    typedef std::pair<RanIt,RanIt> stream_t;
    typedef typename allocator::template rebind<stream_t>::other sallocator;
    typedef typename sallocator::pointer SPtr;
public:
    inline merge_tree(order_t k) : k(k), cold(true)
        { construct(k); }
    inline merge_tree(order_t k, const allocator& alloc) : k(k), cold(true), alloc(alloc), salloc(alloc), nalloc(alloc)
        { construct(k); }
    ~merge_tree();

    static inline order_t min_order()
        { return order; }

    class stream
    {
    private:
        SPtr pair;
    public:
        stream(SPtr pair) : pair(pair) { }
        inline RanIt& begin()
            { return pair->first; }
        inline RanIt& end()
            { return pair->second; }
    };
    class stream_iterator
    {
    private:
        SPtr ptr;
    public:
        stream_iterator(SPtr ptr) : ptr(ptr) { }
        inline order_t operator-(const stream_iterator& rhs)
            { return static_cast<order_t>(ptr-rhs.ptr); }
        inline stream operator*()
            { return stream(ptr); }
        inline stream_iterator& operator++()
            { ++ptr; return *this; }
        inline stream_iterator& operator++(int)
        {
            stream_iterator ret = stream_iterator(ptr);
            ++ptr;
            return ret;
        }
        inline bool operator==(const stream_iterator& rhs)
            { return ptr == rhs.ptr; }
        inline bool operator!=(const stream_iterator& rhs)
            { return ptr != rhs.ptr; }
    };

    inline void add_stream(RanIt begin, RanIt end)
        { *last_stream++ = std::make_pair(begin,end); }
    inline stream_iterator begin()
        { return stream_iterator(input_streams); }
    inline stream_iterator end()
        { return stream_iterator(last_stream); }
    inline void reset();

    inline void set_refiller(const Refiller& r)
        { refiller = r; }
    inline const Refiller& get_refiller() const
        { return refiller; }
    template<class FwIt>
    inline FwIt empty(FwIt begin, FwIt end)
        { return empty_buffers(root, begin, end); }
    template<class OutIt>
    inline OutIt empty(OutIt begin)
        { return empty_buffers(root, begin); }

    template<class It>
    inline It operator()(It begin, It end);
    template<class OutIt>
    inline OutIt operator()(OutIt begin);

private:
    template<class FwIt>
    static inline FwIt empty_buffers(NPtr n, FwIt begin, FwIt end);
    template<class OutIt>
    static inline OutIt empty_buffers(NPtr n, OutIt begin);

    static void compute_buffer_sizes(size_type *b, size_type *e);
    void construct(order_t k);

    inline void go_down(typename Node::Edge& e, bfs_index<order> index);
    inline void go_down_cold(typename Node::Edge& e, bfs_index<order>& index);

    void warmup(NPtr n, typename Node::Edge& output, bfs_index<order> index);

    template<class FwIt>
    inline FwIt copy_root(typename Node::Edge& de, bfs_index<order> index, FwIt begin, FwIt end, std::forward_iterator_tag);
    template<class RIt>
    inline RIt copy_root(typename Node::Edge& de, bfs_index<order> index, RIt begin, RIt end, std::random_access_iterator_tag);
    template<class OutIt>
    inline OutIt copy_root(typename Node::Edge& de, bfs_index<order> index, OutIt begin);

    inline TPtr copy(typename Node::Edge& de, bfs_index<order> index, TPtr b, TPtr e);

    template<class FwIt>
    inline FwIt fill_root(FwIt begin, FwIt end)
        { return special_<RanIt,order,Splitter,Pred,Refiller,Alloc>::fill_root(this, begin, end); }
    template<class OutIt>
    inline OutIt fill_root(OutIt begin)
        { return special_<RanIt,order,Splitter,Pred,Refiller,Alloc>::fill_root(this, begin); }
    void fill(NPtr n, typename Node::Edge& output, bfs_index<order> index)
        { special_<RanIt,order,Splitter,Pred,Refiller,Alloc>::fill(this, n, output, index); }
    void fill_leaf(typename Node::Edge& output, bfs_index<order> index)
        { special_<RanIt,order,Splitter,Pred,Refiller,Alloc>::fill_leaf(this, output, index); }

private:
    order_t k;
    order_t leaf_index;
    bool cold;
    NPtr root;
    SPtr input_streams, last_stream;
    Pred comp;
    allocator alloc;
    sallocator salloc;
    nallocator nalloc;
    Refiller refiller;
};



/*****
 *  Alloc::pointer iterator template specialization
 */

template<int Order, class Splitter, class Pred, class Refiller, class Alloc>
class merge_tree<typename Alloc::pointer, Order, Splitter, Pred, Refiller, Alloc>
{
    typedef typename Alloc::pointer RanIt;
    friend class special_<typename Alloc::pointer,Order,Splitter,Pred,Refiller,Alloc>;
public:
    typedef unsigned int order_t;
    enum order_tag_ { order = Order };
    enum mmth_tag_ { MAX_MERGE_TREE_HEIGHT = 16 };
    typedef Splitter splitter;
    typedef typename std::iterator_traits<typename Alloc::pointer>::value_type value_type;
    typedef Alloc allocator;
    typedef typename Alloc::pointer iterator;
    typedef Pred predicate;
//  template<class NewRefiller>
//  struct rebind { typedef merge_tree<typename Alloc::pointer, Order, Splitter, Pred, NewRefiller, Alloc> other; };
private:
    struct Node;
    friend struct Node;
    typedef typename allocator::pointer TPtr;
    typedef typename allocator::size_type size_type;
    typedef typename allocator::template rebind<Node>::other nallocator;
    typedef typename nallocator::pointer NPtr;
    struct Node
    {
        struct Edge
        {
            typedef typename allocator::pointer TPtr;
            typedef typename allocator::template rebind<Node>::other nallocator;
            typedef typename nallocator::pointer NPtr;
            inline Edge** construct(order_t k, height_t height, size_t *buf_size, Edge** edge_list, allocator alloc, nallocator nalloc);
            inline void destroy(allocator alloc, nallocator nalloc);
            typename nallocator::pointer child;
            typename allocator::pointer head, tail, begin, end;
        private:
            static inline void fill_dflt(TPtr b, TPtr e, allocator alloc);
        } edges[order];
        inline Edge** construct(order_t k, height_t height, size_t *buf_size, Edge** edge_list, allocator alloc, nallocator nalloc);
        inline void destroy(allocator alloc, nallocator nalloc);
    };
    typedef typename Node::Edge* stream_t;
    typedef typename allocator::template rebind<stream_t>::other sallocator;
    typedef typename sallocator::pointer SPtr;
public:
    inline merge_tree(order_t k) : k(k), cold(true)
        { construct(k); }
    inline merge_tree(order_t k, const allocator& alloc) : k(k), cold(true), alloc(alloc), salloc(alloc), nalloc(alloc)
        { construct(k); }
    ~merge_tree();

    static inline order_t min_order()
        { return order; }

    class stream
    {
    private:
        stream_t edge;
    public:
        inline stream(stream_t edge) : edge(edge) { }
        inline typename allocator::pointer& begin()
            { return edge->head; }
        inline typename allocator::pointer& end()
            { return edge->tail; }
    };
    class stream_iterator
    {
    private:
        SPtr ptr;
    public:
        inline stream_iterator(SPtr ptr) : ptr(ptr) { }
        inline order_t operator-(const stream_iterator& rhs)
            { return static_cast<order_t>(ptr-rhs.ptr); }
        inline stream operator*()
            { return stream(*ptr); }
        inline stream_iterator& operator++()
            { ++ptr; return *this; }
        inline stream_iterator& operator++(int)
        {
            stream_iterator ret = stream_iterator(ptr);
            ++ptr;
            return ret;
        }
        inline bool operator==(const stream_iterator& rhs)
            { return ptr == rhs.ptr; }
        inline bool operator!=(const stream_iterator& rhs)
            { return ptr != rhs.ptr; }
    };

    inline void add_stream(typename Alloc::pointer begin, typename Alloc::pointer end)
        { (*last_stream)->head = begin, (*last_stream)->tail = end, ++last_stream; }
    inline stream_iterator begin()
        { return input_streams; }
    inline stream_iterator end()
        { return last_stream; }
    inline void reset();

    inline void set_refiller(const Refiller& r)
        { refiller = r; }
    inline const Refiller& get_refiller() const
        { return refiller; }
    template<class FwIt>
    inline FwIt empty(FwIt begin, FwIt end)
        { return empty_buffers(root, begin, end); }
    template<class OutIt>
    inline OutIt empty(OutIt begin)
        { return empty_buffers(root, begin); }

    template<class FwIt>
    inline FwIt operator()(FwIt begin, FwIt end);
    template<class OutIt>
    inline OutIt operator()(OutIt begin);
private:
    template<class FwIt>
    static inline FwIt empty_buffers(NPtr n, FwIt begin, FwIt end);
    template<class OutIt>
    static inline OutIt empty_buffers(NPtr n, OutIt begin);

    void construct(order_t k);
    static void compute_buffer_sizes(size_type *b, size_type *e);

    static inline void go_down(typename Node::Edge& e, Pred comp);
    static inline void go_down_cold(typename Node::Edge& e, Pred comp);

    static void warmup(NPtr n, typename Node::Edge& output, Pred comp);

    template<class OutIt>
    static inline OutIt copy(typename Node::Edge& de, OutIt begin, Pred comp);
    template<class FwIt>
    static inline FwIt copy(typename Node::Edge& de, FwIt begin, FwIt end, Pred comp, std::forward_iterator_tag);
    template<class RIt>
    static inline RIt copy(typename Node::Edge& de, RIt begin, RIt end, Pred comp, std::random_access_iterator_tag);

    template<class OutIt>
    static inline OutIt fill(NPtr n, OutIt begin, Pred comp)
        { return special_<typename Alloc::pointer,order,Splitter,Pred,Refiller,Alloc>::fill(n, begin, comp); }
    template<class FwIt>
    static inline FwIt fill(NPtr n, FwIt begin, FwIt end, Pred comp)
        { return special_<typename Alloc::pointer,Order,Splitter,Pred,Refiller,Alloc>::fill(n, begin, end, comp); }
private:
    order_t k;
    order_t leaf_index;
    bool cold;
    NPtr root;
    SPtr input_streams, last_stream;
    Pred comp;
    allocator alloc;
    sallocator salloc;
    nallocator nalloc;
    Refiller refiller;
};

} // namespace iosort

#include "funnel.timpl.h"
#endif // FUNNEL_H_INCLUDED__