//----------------------------------------------------------------------------
|
/// @file backbone.hpp
|
/// @brief This file constains the class backbone, which is part of the
|
/// block_indirect_sort algorithm
|
///
|
/// @author Copyright (c) 2016 Francisco Jose Tapia (fjtapia@gmail.com )\n
|
/// Distributed under the Boost Software License, Version 1.0.\n
|
/// ( See accompanying file LICENSE_1_0.txt or copy at
|
/// http://www.boost.org/LICENSE_1_0.txt )
|
/// @version 0.1
|
///
|
/// @remarks
|
//-----------------------------------------------------------------------------
|
#ifndef __BOOST_SORT_PARALLEL_DETAIL_BACKBONE_HPP
|
#define __BOOST_SORT_PARALLEL_DETAIL_BACKBONE_HPP
|
|
#include <atomic>
|
#include <boost/sort/pdqsort/pdqsort.hpp>
|
#include <boost/sort/common/util/atomic.hpp>
|
#include <boost/sort/common/util/algorithm.hpp>
|
#include <boost/sort/common/stack_cnc.hpp>
|
#include <future>
|
#include <iostream>
|
#include <iterator>
|
|
#include <boost/sort/block_indirect_sort/blk_detail/block.hpp>
|
|
namespace boost
|
{
|
namespace sort
|
{
|
namespace blk_detail
|
{
|
|
//---------------------------------------------------------------------------
|
// USING SENTENCES
|
//---------------------------------------------------------------------------
|
namespace bsc = boost::sort::common;
|
namespace bscu = bsc::util;
|
using bsc::stack_cnc;
|
using bsc::range;
|
|
///---------------------------------------------------------------------------
|
/// @struct backbone
|
/// @brief This contains all the information shared betwen the classes of the
|
/// block indirect sort algorithm
|
|
//----------------------------------------------------------------------------
|
template < uint32_t Block_size, class Iter_t, class Compare >
|
struct backbone
|
{
|
//-------------------------------------------------------------------------
|
// D E F I N I T I O N S
|
//-------------------------------------------------------------------------
|
typedef typename std::iterator_traits< Iter_t >::value_type value_t;
|
typedef std::atomic< uint32_t > atomic_t;
|
typedef range< size_t > range_pos;
|
typedef range< Iter_t > range_it;
|
typedef range< value_t * > range_buf;
|
typedef std::function< void(void) > function_t;
|
typedef block< Block_size, Iter_t > block_t;
|
|
//------------------------------------------------------------------------
|
// V A R I A B L E S
|
//------------------------------------------------------------------------
|
// range with all the element to sort
|
range< Iter_t > global_range;
|
|
// index vector of block_pos elements
|
std::vector< block_pos > index;
|
|
// Number of elements to sort
|
size_t nelem;
|
|
// Number of blocks to sort
|
size_t nblock;
|
|
// Number of elements in the last block (tail)
|
size_t ntail;
|
|
// object for to compare two elements
|
Compare cmp;
|
|
// range of elements of the last block (tail)
|
range_it range_tail;
|
|
// thread local varible. It is a pointer to the buffer
|
static thread_local value_t *buf;
|
|
// concurrent stack where store the function_t elements
|
stack_cnc< function_t > works;
|
|
// global indicator of error
|
bool error;
|
//
|
//------------------------------------------------------------------------
|
// F U N C T I O N S
|
//------------------------------------------------------------------------
|
backbone (Iter_t first, Iter_t last, Compare comp);
|
|
//------------------------------------------------------------------------
|
// function : get_block
|
/// @brief obtain the block in the position pos
|
/// @param pos : position of the range
|
/// @return block required
|
//------------------------------------------------------------------------
|
block_t get_block (size_t pos) const
|
{
|
return block_t (global_range.first + (pos * Block_size));
|
};
|
//-------------------------------------------------------------------------
|
// function : get_range
|
/// @brief obtain the range in the position pos
|
/// @param pos : position of the range
|
/// @return range required
|
//-------------------------------------------------------------------------
|
range_it get_range (size_t pos) const
|
{
|
Iter_t it1 = global_range.first + (pos * Block_size);
|
Iter_t it2 =
|
(pos == (nblock - 1)) ? global_range.last : it1 + Block_size;
|
return range_it (it1, it2);
|
};
|
//-------------------------------------------------------------------------
|
// function : get_range_buf
|
/// @brief obtain the auxiliary buffer of the thread
|
//-------------------------------------------------------------------------
|
range_buf get_range_buf ( ) const
|
{
|
return range_buf (buf, buf + Block_size);
|
};
|
|
//-------------------------------------------------------------------------
|
// function : exec
|
/// @brief Initialize the thread local buffer with the ptr_buf pointer,
|
/// and begin with the execution of the functions stored in works
|
//
|
/// @param ptr_buf : Pointer to the memory assigned to the thread_local
|
/// buffer
|
/// @param counter : atomic counter for to invoke to the exec function
|
/// with only 1 parameter
|
//-------------------------------------------------------------------------
|
void exec (value_t *ptr_buf, atomic_t &counter)
|
{
|
buf = ptr_buf;
|
exec (counter);
|
};
|
|
void exec (atomic_t &counter);
|
|
//---------------------------------------------------------------------------
|
}; // end struct backbone
|
//---------------------------------------------------------------------------
|
//
|
//############################################################################
|
// ##
|
// ##
|
// N O N I N L I N E F U N C T I O N S ##
|
// ##
|
// ##
|
//############################################################################
|
//
|
// initialization of the thread_local pointer to the auxiliary buffer
|
template < uint32_t Block_size, class Iter_t, class Compare >
|
thread_local typename std::iterator_traits< Iter_t >
|
::value_type *backbone< Block_size, Iter_t, Compare >::buf = nullptr;
|
|
//------------------------------------------------------------------------
|
// function : backbone
|
/// @brief constructor of the class
|
//
|
/// @param first : iterator to the first element of the range to sort
|
/// @param last : iterator after the last element to the range to sort
|
/// @param comp : object for to compare two elements pointed by Iter_t
|
/// iterators
|
//------------------------------------------------------------------------
|
template < uint32_t Block_size, class Iter_t, class Compare >
|
backbone< Block_size, Iter_t, Compare >
|
::backbone (Iter_t first, Iter_t last, Compare comp)
|
: global_range (first, last), cmp (comp), error (false)
|
{
|
assert ((last - first) >= 0);
|
if (first == last) return; // nothing to do
|
|
nelem = size_t (last - first);
|
nblock = (nelem + Block_size - 1) / Block_size;
|
ntail = (nelem % Block_size);
|
index.reserve (nblock + 1);
|
|
for (size_t i = 0; i < nblock; ++i) index.emplace_back (block_pos (i));
|
|
range_tail.first =
|
(ntail == 0) ? last : (first + ((nblock - 1) * Block_size));
|
range_tail.last = last;
|
};
|
//
|
//-------------------------------------------------------------------------
|
// function : exec
|
/// @brief execute the function_t stored in works, until counter is zero
|
//
|
/// @param counter : atomic counter. When 0 exits the function
|
//-------------------------------------------------------------------------
|
template < uint32_t Block_size, class Iter_t, class Compare >
|
void backbone< Block_size, Iter_t, Compare >::exec (atomic_t &counter)
|
{
|
function_t func_exec;
|
while (bscu::atomic_read (counter) != 0)
|
{
|
if (works.pop_move_back (func_exec)) func_exec ( );
|
else std::this_thread::yield ( );
|
};
|
};
|
//
|
//****************************************************************************
|
}; // End namespace blk_detail
|
}; // End namespace sort
|
}; // End namespace boost
|
//****************************************************************************
|
#endif
|
