#875

Committed 25 Jan 2023 03:11PM UTC coverage: 86.39% (+0.5%) from 85.911%

Build # #875

Build Type

push

Committed by StellarBot

Commit Message

Merge #6151

6151: Refactoring the Manual page in documentation r=hkaiser a=dimitraka

- Move the instructions to build the tests and examples in a new separate page 
- Add references of the most important CMake options or the comprehensive list of CMake options
- Rename the CMake options page (title was too long)
- Refer to the new page of how to build the examples in the examples section itself


Co-authored-by: kadimitra <kadimitra@ece.auth.gr>

Run Details

174481 of 201968 relevant lines covered (86.39%)

1898746.94 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

95.56

/libs/core/algorithms/include/hpx/parallel/algorithms/detail/spin_sort.hpp

//  Copyright (c) 2015-2017 Francisco Jose Tapia
//  Copyright (c) 2020 Hartmut Kaiser
//
//  SPDX-License-Identifier: BSL-1.0
//  Distributed under the Boost Software License, Version 1.0. (See accompanying
//  file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)

#pragma once

#include <hpx/assert.hpp>
#include <hpx/parallel/algorithms/detail/insertion_sort.hpp>
#include <hpx/parallel/algorithms/detail/is_sorted.hpp>
#include <hpx/parallel/util/nbits.hpp>
#include <hpx/parallel/util/range.hpp>

#include <cstddef>
#include <cstdint>
#include <cstdlib>
#include <functional>
#include <iterator>
#include <memory>
#include <stdexcept>
#include <type_traits>
#include <utility>
#include <vector>

namespace hpx { namespace parallel { inline namespace v1 { namespace detail {

    /// This function divide r_input in two parts, sort it, and merge moving
    ///        the elements to range_buf
    /// \param [in] r_input     range with the elements to sort
    /// \param [in] range_buf   range with the elements sorted
    /// \param [in] comp        object for to compare two elements
    /// \param [in] level       when is 0, sort with the insertion_sort
    ///                         algorithm if not make a recursive call swapping
    ///                         the ranges
    /// \return range with all the elements sorted and moved
    template <typename Iter1, typename Sent1, typename Iter2, typename Sent2,
        typename Compare>
    void range_sort(util::range<Iter1, Sent1> const& rng_a,
        util::range<Iter2, Sent2> const& rng_b, Compare comp,
        std::uint32_t level)
    {
        using range_it1 = util::range<Iter1, Sent1>;
        using range_it2 = util::range<Iter2, Sent2>;

        std::size_t nelem1 = (rng_a.size() + 1) >> 1;

        range_it1 rng_a1(rng_a.begin(), rng_a.begin() + nelem1);
        range_it1 rng_a2(rng_a.begin() + nelem1, rng_a.end());

        if (level < 2)
        {
            insertion_sort(rng_a1.begin(), rng_a1.end(), comp);
            insertion_sort(rng_a2.begin(), rng_a2.end(), comp);
        }
        else
        {
            range_sort(range_it2(rng_b.begin(), rng_b.begin() + nelem1), rng_a1,
                comp, level - 1);
            range_sort(range_it2(rng_b.begin() + nelem1, rng_b.end()), rng_a2,
                comp, level - 1);
        }

        parallel::util::full_merge(rng_b, rng_a1, rng_a2, comp);
    }

    /// \struct spin_sort_helper
    /// \brief this is a struct for to do a stable sort exception safe
    /// \tparam Iter : iterator to the elements
    /// \tparam Compare : object for to Compare the elements pointed by Iter
    /// \remarks
    template <typename Iter, typename Sent, typename Compare>
    class spin_sort_helper
    {
        using value_type = typename std::iterator_traits<Iter>::value_type;
        using range_it = util::range<Iter, Sent>;
        using range_buf = util::range<value_type*>;

        static constexpr std::uint32_t sort_min = 36;

        value_type* ptr;
        std::size_t nptr;
        bool construct = false;
        bool owner = false;

        /// \brief constructor of the struct
        /// \param [in] R : range of elements to sort
        /// \param [in] comp : object for to compare two elements
        spin_sort_helper(Iter first, Sent last, Compare comp, value_type* paux,
            std::size_t naux);

    public:
        /// \brief constructor of the struct
        /// \param [in] r_input : range of elements to sort
        /// \param [in] comp : object for to Compare two elements
        spin_sort_helper(Iter first, Sent last, Compare comp = Compare())
          : spin_sort_helper(first, last, comp, nullptr, 0)
        {
        }

        /// \brief constructor of the struct
        /// \param [in] r_input : range of elements to sort
        /// \param [in] comp : object for to Compare two elements
        /// \param [in] range_aux : range used as auxiliary memory
        spin_sort_helper(
            Iter first, Sent last, Compare comp, range_buf range_aux)
          : spin_sort_helper(first, last, comp, range_aux.begin(),
                (std::size_t) range_aux.size())
        {
        }

        /// \brief destructor of the struct. Deallocate all the data structure
        ///        used in the sorting
        /// \exception
        /// \return
        /// \remarks
        ~spin_sort_helper()
        {
            if (construct)
            {
                parallel::util::destroy_range(
                    util::range<value_type*>(ptr, ptr + nptr));
                construct = false;
            }

            if (owner)
            {
                std::free(ptr);
            }
        }
    };    // End of class spin_sort_helper

    /// \brief constructor of the struct
    /// \param [in] r_input : range of elements to sort
    /// \param [in] comp : object for to Compare two elements
    template <typename Iter, typename Sent, typename Compare>
    spin_sort_helper<Iter, Sent, Compare>::spin_sort_helper(
        Iter first, Sent last, Compare comp, value_type* paux, std::size_t naux)
      : ptr(paux)
      , nptr(naux)
      , construct(false)
      , owner(false)
    {
        util::range<Iter> r_input(first, last);
        HPX_ASSERT(r_input.size() >= 0);

        std::size_t nelem = r_input.size();
        owner = construct = false;

        nptr = (nelem + 1) >> 1;
        std::size_t nelem_1 = nptr;
        std::size_t nelem_2 = nelem - nelem_1;

        if (nelem <= (sort_min << 1))
        {
            insertion_sort(first, last, comp);
            return;
        }

        if (detail::is_sorted_sequential(first, last, comp))
            return;

        if (ptr == nullptr)
        {
            // acquire uninitialized memory
            ptr = static_cast<value_type*>(
                std::malloc(nptr * sizeof(value_type)));
            if (ptr == nullptr)
            {
                throw std::bad_alloc();
            }
            owner = true;
        }

        range_buf rng_buf(ptr, ptr + nptr);

        std::uint32_t nlevel =
            util::nbits64(((nelem + sort_min - 1) / sort_min) - 1) - 1;
        HPX_ASSERT(nlevel != 0);

        if ((nlevel & 1) == 1)
        {
            // if the number of levels is odd, the data are in the first parameter
            // of range_sort, and the results appear in the second parameter
            range_it rng_a1(first, first + nelem_2);
            range_it rng_a2(first + nelem_2, last);

            rng_buf = parallel::util::uninit_move(rng_buf, rng_a2);
            construct = true;

            range_sort(rng_buf, rng_a2, comp, nlevel);
            range_buf rng_bx(rng_buf.begin(), rng_buf.begin() + nelem_2);

            range_sort(rng_a1, rng_bx, comp, nlevel);
            parallel::util::half_merge(r_input, rng_bx, rng_a2, comp);
        }
        else
        {
            // If the number of levels is even, the data are in the second
            // parameter of range_sort, and the results are in the same parameter
            range_it rng_a1(first, first + nelem_1);
            range_it rng_a2(first + nelem_1, last);

            rng_buf = parallel::util::uninit_move(rng_buf, rng_a1);
            construct = true;

            range_sort(rng_a1, rng_buf, comp, nlevel);

            rng_a1 = range_it(rng_a1.begin(), rng_a1.begin() + rng_a2.size());
            range_sort(rng_a1, rng_a2, comp, nlevel);
            parallel::util::half_merge(r_input, rng_buf, rng_a2, comp);
        }
    }

    template <typename Iter, typename Sent>
    void spin_sort(Iter first, Sent last)
    {
        using compare =
            std::less<typename std::iterator_traits<Iter>::value_type>;

        spin_sort_helper<Iter, Sent, compare> sorter(first, last, compare{});
    }

    template <typename Iter, typename Sent, typename Compare>
    void spin_sort(Iter first, Sent last, Compare&& comp)
    {
        spin_sort_helper<Iter, Sent, typename std::decay<Compare>::type> sorter(
            first, last, HPX_FORWARD(Compare, comp));
    }

    template <typename Iter, typename Sent, typename Compare>
    void spin_sort(Iter first, Sent last, Compare&& comp,
        util::range<typename std::iterator_traits<Iter>::value_type*> range_aux)
    {
        spin_sort_helper<Iter, Sent, typename std::decay<Compare>::type> sorter(
            first, last, HPX_FORWARD(Compare, comp), range_aux);
    }

    template <typename Iter, typename Sent, typename Compare>
    void spin_sort(Iter first, Sent last, Compare comp,
        typename std::iterator_traits<Iter>::value_type* paux, std::size_t naux)
    {
        spin_sort_helper<Iter, Sent, typename std::decay<Compare>::type> sorter(
            first, last, HPX_FORWARD(Compare, comp), paux, naux);
    }

}}}}    // namespace hpx::parallel::v1::detail

1	// Copyright (c) 2015-2017 Francisco Jose Tapia
2	// Copyright (c) 2020 Hartmut Kaiser
3	//
4	// SPDX-License-Identifier: BSL-1.0
5	// Distributed under the Boost Software License, Version 1.0. (See accompanying
6	// file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
7
8	#pragma once
9
10	#include <hpx/assert.hpp>
11	#include <hpx/parallel/algorithms/detail/insertion_sort.hpp>
12	#include <hpx/parallel/algorithms/detail/is_sorted.hpp>
13	#include <hpx/parallel/util/nbits.hpp>
14	#include <hpx/parallel/util/range.hpp>
15
16	#include <cstddef>
17	#include <cstdint>
18	#include <cstdlib>
19	#include <functional>
20	#include <iterator>
21	#include <memory>
22	#include <stdexcept>
23	#include <type_traits>
24	#include <utility>
25	#include <vector>
26
27	namespace hpx { namespace parallel { inline namespace v1 { namespace detail {
28
29	/// This function divide r_input in two parts, sort it, and merge moving
30	/// the elements to range_buf
31	/// \param [in] r_input range with the elements to sort
32	/// \param [in] range_buf range with the elements sorted
33	/// \param [in] comp object for to compare two elements
34	/// \param [in] level when is 0, sort with the insertion_sort
35	/// algorithm if not make a recursive call swapping
36	/// the ranges
37	/// \return range with all the elements sorted and moved
38	template <typename Iter1, typename Sent1, typename Iter2, typename Sent2,
39	typename Compare>
40	void range_sort(util::range<Iter1, Sent1> const& rng_a,	255,014✔
41	util::range<Iter2, Sent2> const& rng_b, Compare comp,
42	std::uint32_t level)
43	{
44	using range_it1 = util::range<Iter1, Sent1>;
45	using range_it2 = util::range<Iter2, Sent2>;
46
47	std::size_t nelem1 = (rng_a.size() + 1) >> 1;	255,022✔
48
49	range_it1 rng_a1(rng_a.begin(), rng_a.begin() + nelem1);	255,022✔
50	range_it1 rng_a2(rng_a.begin() + nelem1, rng_a.end());	255,022✔
51
52	if (level < 2)	255,022✔
53	{
54	insertion_sort(rng_a1.begin(), rng_a1.end(), comp);	127,826✔
55	insertion_sort(rng_a2.begin(), rng_a2.end(), comp);	127,826✔
56	}	127,826✔
57	else
58	{
59	range_sort(range_it2(rng_b.begin(), rng_b.begin() + nelem1), rng_a1,	254,366✔
60	comp, level - 1);	127,163✔
61	range_sort(range_it2(rng_b.begin() + nelem1, rng_b.end()), rng_a2,	254,366✔
62	comp, level - 1);	127,163✔
63	}
64
65	parallel::util::full_merge(rng_b, rng_a1, rng_a2, comp);	254,947✔
66	}	254,947✔
67
68	/// \struct spin_sort_helper
69	/// \brief this is a struct for to do a stable sort exception safe
70	/// \tparam Iter : iterator to the elements
71	/// \tparam Compare : object for to Compare the elements pointed by Iter
72	/// \remarks
73	template <typename Iter, typename Sent, typename Compare>
74	class spin_sort_helper
75	{
76	using value_type = typename std::iterator_traits<Iter>::value_type;
77	using range_it = util::range<Iter, Sent>;
78	using range_buf = util::range<value_type*>;
79
80	static constexpr std::uint32_t sort_min = 36;
81
82	value_type* ptr;
83	std::size_t nptr;
84	bool construct = false;
85	bool owner = false;
86
87	/// \brief constructor of the struct
88	/// \param [in] R : range of elements to sort
89	/// \param [in] comp : object for to compare two elements
90	spin_sort_helper(Iter first, Sent last, Compare comp, value_type* paux,
91	std::size_t naux);
92
93	public:
94	/// \brief constructor of the struct
95	/// \param [in] r_input : range of elements to sort
96	/// \param [in] comp : object for to Compare two elements
97	spin_sort_helper(Iter first, Sent last, Compare comp = Compare())	158✔
98	: spin_sort_helper(first, last, comp, nullptr, 0)	158✔
99	{
100	}	158✔
101
102	/// \brief constructor of the struct
103	/// \param [in] r_input : range of elements to sort
104	/// \param [in] comp : object for to Compare two elements
105	/// \param [in] range_aux : range used as auxiliary memory
106	spin_sort_helper(	227✔
107	Iter first, Sent last, Compare comp, range_buf range_aux)
108	: spin_sort_helper(first, last, comp, range_aux.begin(),	454✔
109	(std::size_t) range_aux.size())	227✔
110	{
111	}	227✔
112
113	/// \brief destructor of the struct. Deallocate all the data structure
114	/// used in the sorting
115	/// \exception
116	/// \return
117	/// \remarks
118	~spin_sort_helper()	369✔
119	{
120	if (construct)	369✔
121	{
122	parallel::util::destroy_range(	333✔
123	util::range<value_type*>(ptr, ptr + nptr));	333✔
124	construct = false;	333✔
125	}	333✔
126
127	if (owner)	369✔
128	{
129	std::free(ptr);	106✔
130	}	106✔
131	}	369✔
132	}; // End of class spin_sort_helper
133
134	/// \brief constructor of the struct
135	/// \param [in] r_input : range of elements to sort
136	/// \param [in] comp : object for to Compare two elements
137	template <typename Iter, typename Sent, typename Compare>
138	spin_sort_helper<Iter, Sent, Compare>::spin_sort_helper(	385✔
139	Iter first, Sent last, Compare comp, value_type* paux, std::size_t naux)
140	: ptr(paux)	385✔
141	, nptr(naux)	385✔
142	, construct(false)	385✔
143	, owner(false)	385✔
144	{
145	util::range<Iter> r_input(first, last);	401✔
146	HPX_ASSERT(r_input.size() >= 0);	385✔
147
148	std::size_t nelem = r_input.size();	385✔
149	owner = construct = false;	385✔
150
151	nptr = (nelem + 1) >> 1;	385✔
152	std::size_t nelem_1 = nptr;	385✔
153	std::size_t nelem_2 = nelem - nelem_1;	385✔
154
155	if (nelem <= (sort_min << 1))	385✔
156	{
157	insertion_sort(first, last, comp);	×
158	return;	×
159	}
160
161	if (detail::is_sorted_sequential(first, last, comp))	385✔
162	return;	36✔
163
164	if (ptr == nullptr)	333✔
165	{
166	// acquire uninitialized memory
167	ptr = static_cast<value_type*>(	106✔
168	std::malloc(nptr * sizeof(value_type)));	106✔
169	if (ptr == nullptr)	106✔
170	{
171	throw std::bad_alloc();	×
172	}
173	owner = true;	106✔
174	}	106✔
175
176	range_buf rng_buf(ptr, ptr + nptr);	333✔
177
178	std::uint32_t nlevel =	333✔
179	util::nbits64(((nelem + sort_min - 1) / sort_min) - 1) - 1;	333✔
180	HPX_ASSERT(nlevel != 0);	333✔
181
182	if ((nlevel & 1) == 1)	333✔
183	{
184	// if the number of levels is odd, the data are in the first parameter
185	// of range_sort, and the results appear in the second parameter
186	range_it rng_a1(first, first + nelem_2);	89✔
187	range_it rng_a2(first + nelem_2, last);	89✔
188
189	rng_buf = parallel::util::uninit_move(rng_buf, rng_a2);	89✔
190	construct = true;	89✔
191
192	range_sort(rng_buf, rng_a2, comp, nlevel);	89✔
193	range_buf rng_bx(rng_buf.begin(), rng_buf.begin() + nelem_2);	89✔
194
195	range_sort(rng_a1, rng_bx, comp, nlevel);	89✔
196	parallel::util::half_merge(r_input, rng_bx, rng_a2, comp);	89✔
197	}	89✔
198	else
199	{
200	// If the number of levels is even, the data are in the second
201	// parameter of range_sort, and the results are in the same parameter
202	range_it rng_a1(first, first + nelem_1);	244✔
203	range_it rng_a2(first + nelem_1, last);	244✔
204
205	rng_buf = parallel::util::uninit_move(rng_buf, rng_a1);	244✔
206	construct = true;	244✔
207
208	range_sort(rng_a1, rng_buf, comp, nlevel);	244✔
209
210	rng_a1 = range_it(rng_a1.begin(), rng_a1.begin() + rng_a2.size());	244✔
211	range_sort(rng_a1, rng_a2, comp, nlevel);	244✔
212	parallel::util::half_merge(r_input, rng_buf, rng_a2, comp);	244✔
213	}	×
214	}	401✔
215
216	template <typename Iter, typename Sent>
217	void spin_sort(Iter first, Sent last)	7✔
218	{
219	using compare =
220	std::less<typename std::iterator_traits<Iter>::value_type>;
221
222	spin_sort_helper<Iter, Sent, compare> sorter(first, last, compare{});	7✔
223	}	7✔
224
225	template <typename Iter, typename Sent, typename Compare>
226	void spin_sort(Iter first, Sent last, Compare&& comp)	151✔
227	{
228	spin_sort_helper<Iter, Sent, typename std::decay<Compare>::type> sorter(	151✔
229	first, last, HPX_FORWARD(Compare, comp));	151✔
230	}	151✔
231
232	template <typename Iter, typename Sent, typename Compare>
233	void spin_sort(Iter first, Sent last, Compare&& comp,	227✔
234	util::range<typename std::iterator_traits<Iter>::value_type*> range_aux)
235	{
236	spin_sort_helper<Iter, Sent, typename std::decay<Compare>::type> sorter(	227✔
237	first, last, HPX_FORWARD(Compare, comp), range_aux);	227✔
238	}	227✔
239
240	template <typename Iter, typename Sent, typename Compare>
241	void spin_sort(Iter first, Sent last, Compare comp,
242	typename std::iterator_traits<Iter>::value_type* paux, std::size_t naux)
243	{
244	spin_sort_helper<Iter, Sent, typename std::decay<Compare>::type> sorter(
245	first, last, HPX_FORWARD(Compare, comp), paux, naux);
246	}
247
248	}}}} // namespace hpx::parallel::v1::detail

STEllAR-GROUP / hpx / #875

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous