123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219 |
- //----------------------------------------------------------------------------
- /// @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
|