1 files changed, 219 insertions, 0 deletions
diff --git a/boost/sort/block_indirect_sort/blk_detail/backbone.hpp b/boost/sort/block_indirect_sort/blk_detail/backbone.hpp
new file mode 100644
index 0000000000..1c2fdfec88
--- /dev/null
+++ b/boost/sort/block_indirect_sort/blk_detail/backbone.hpp
@@ -0,0 +1,219 @@
+//----------------------------------------------------------------------------
+/// @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