ppqsort::impl::cpp namespace

Classes

template<typename taskType = std::function<void()>>
class TaskStack
template<typename taskType = std::function<void()>>
class ThreadPool
struct ThreadPools

Functions

template<typename RandomIt, typename Compare>
auto is_sorted_par(RandomIt begin, RandomIt end, Compare comp, const std::size_t size, const int n_threads, bool leftmost, ThreadPool<>& thread_pool) -> bool
template<typename RandomIt, typename Compare, bool branchless, typename diff_t = typename std::iterator_traits<RandomIt>::difference_type>
auto par_loop(RandomIt begin, RandomIt end, Compare comp, diff_t bad_allowed, diff_t seq_thr, int threads, ThreadPools& thread_pools, bool leftmost = true) -> void
template<typename RandomIt, typename Compare, typename T = typename std::iterator_traits<RandomIt>::value_type, typename diff_t = typename std::iterator_traits<RandomIt>::difference_type>
auto process_blocks_branchless(const RandomIt& g_begin, const Compare& comp, const diff_t& g_size, std::atomic<diff_t>& g_distance, std::atomic<diff_t>& g_first_offset, std::atomic<diff_t>& g_last_offset, const int& block_size, const T& pivot, std::atomic<unsigned char>& g_already_partitioned, std::atomic<int>& g_dirty_blocks_left, std::atomic<int>& g_dirty_blocks_right, std::unique_ptr<std::atomic<bool>[]>& g_reserved_left, std::unique_ptr<std::atomic<bool>[]>& g_reserved_right, std::barrier<>& barrier, const int t_my_id, std::latch& part_done) -> void
template<class RandomIt, class Compare, typename T = typename std::iterator_traits<RandomIt>::value_type, typename diff_t = typename std::iterator_traits<RandomIt>::difference_type>
auto partition_right_branchless_par(const RandomIt g_begin, const RandomIt g_end, Compare comp, const int thread_count, ThreadPool<>& thread_pool) -> std::pair<RandomIt, bool>
template<side s, typename diff_t>
auto get_new_block(diff_t& t_iter, diff_t& t_block_bound, std::atomic<diff_t>& g_distance, std::atomic<diff_t>& g_offset, const int& block_size) -> bool
template<side s, typename RandomIt, typename diff_t>
auto swap_blocks(const std::atomic<int>& g_dirty_blocks_side, const RandomIt& g_begin, const diff_t& t_old, const diff_t& t_block_bound, std::unique_ptr<std::atomic<bool>[]>& reserved, const int& block_size) -> void
template<typename RandomIt, typename diff_t>
auto swap_dirty_blocks(const RandomIt& g_begin, const diff_t& t_left, const diff_t& t_right, const diff_t& t_left_end, const diff_t& t_right_start, std::atomic<int>& g_dirty_blocks_left, std::atomic<int>& g_dirty_blocks_right, std::atomic<diff_t>& g_first_offset, std::atomic<diff_t>& g_last_offset, std::unique_ptr<std::atomic<bool>[]>& g_reserved_left, std::unique_ptr<std::atomic<bool>[]>& g_reserved_right, const int& block_size, std::barrier<>& barrier, const int& t_my_id) -> void
template<typename RandomIt, typename Compare, typename T = typename std::iterator_traits<RandomIt>::value_type, typename diff_t = typename std::iterator_traits<RandomIt>::difference_type>
auto process_blocks(const RandomIt& g_begin, const Compare& comp, const diff_t& g_size, std::atomic<diff_t>& g_distance, std::atomic<diff_t>& g_first_offset, std::atomic<diff_t>& g_last_offset, const int& block_size, const T& pivot, std::atomic<unsigned char>& g_already_partitioned, std::atomic<int>& g_dirty_blocks_left, std::atomic<int>& g_dirty_blocks_right, std::unique_ptr<std::atomic<bool>[]>& g_reserved_left, std::unique_ptr<std::atomic<bool>[]>& g_reserved_right, std::barrier<>& barrier, const int t_my_id, std::latch& part_done) -> void
template<typename RandomIt, typename Compare, typename T = typename std::iterator_traits<RandomIt>::value_type, typename diff_t = typename std::iterator_traits<RandomIt>::difference_type>
auto partition_to_right_par(const RandomIt g_begin, const RandomIt g_end, Compare comp, const int thread_count, ThreadPool<>& thread_pool) -> std::pair<RandomIt, bool>
template<typename RandomIt, typename Compare, typename T = typename std::iterator_traits<RandomIt>::value_type, typename diff_t = typename std::iterator_traits<RandomIt>::difference_type>
auto process_blocks_branchless(const RandomIt& g_begin, const Compare& comp, const diff_t& g_size, std::atomic<diff_t>& g_distance, diff_t& g_first_offset, diff_t& g_last_offset, const int& block_size, const T& pivot, unsigned char& g_already_partitioned, std::atomic<int>& g_dirty_blocks_left, std::atomic<int>& g_dirty_blocks_right, std::unique_ptr<std::atomic<bool>[]>& g_reserved_left, std::unique_ptr<std::atomic<bool>[]>& g_reserved_right, std::barrier<>& barrier, const int t_my_id, std::latch& part_done) -> void
template<side s, typename diff_t>
auto get_new_block(diff_t& t_iter, diff_t& t_block_bound, std::atomic<diff_t>& g_distance, std::atomic_ref<diff_t>& g_offset, const int& block_size) -> bool
template<typename RandomIt, typename diff_t>
auto swap_dirty_blocks(const RandomIt& g_begin, const diff_t& t_left, const diff_t& t_right, const diff_t& t_left_end, const diff_t& t_right_start, std::atomic<int>& g_dirty_blocks_left, std::atomic<int>& g_dirty_blocks_right, std::atomic_ref<diff_t>& a_g_first_offset, std::atomic_ref<diff_t>& a_g_last_offset, std::unique_ptr<std::atomic<bool>[]>& g_reserved_left, std::unique_ptr<std::atomic<bool>[]>& g_reserved_right, const int& block_size, std::barrier<>& barrier, const int& t_my_id) -> void
template<typename RandomIt, typename Compare, typename T = typename std::iterator_traits<RandomIt>::value_type, typename diff_t = typename std::iterator_traits<RandomIt>::difference_type>
auto process_blocks(const RandomIt& g_begin, const Compare& comp, const diff_t& g_size, std::atomic<diff_t>& g_distance, diff_t& g_first_offset, diff_t& g_last_offset, const int& block_size, const T& pivot, unsigned char& g_already_partitioned, std::atomic<int>& g_dirty_blocks_left, std::atomic<int>& g_dirty_blocks_right, std::unique_ptr<std::atomic<bool>[]>& g_reserved_left, std::unique_ptr<std::atomic<bool>[]>& g_reserved_right, std::barrier<>& barrier, const int t_my_id, std::latch& part_done) -> void

Function documentation

#include <ppqsort/parallel/cpp/mainloop_par.h>
template<typename RandomIt, typename Compare>
bool ppqsort::impl::cpp::is_sorted_par(RandomIt begin, RandomIt end, Compare comp, const std::size_t size, const int n_threads, bool leftmost, ThreadPool<>& thread_pool)

#include <ppqsort/parallel/cpp/mainloop_par.h>
template<typename RandomIt, typename Compare, bool branchless, typename diff_t = typename std::iterator_traits<RandomIt>::difference_type>
void ppqsort::impl::cpp::par_loop(RandomIt begin, RandomIt end, Compare comp, diff_t bad_allowed, diff_t seq_thr, int threads, ThreadPools& thread_pools, bool leftmost = true)

#include <ppqsort/parallel/cpp/no_atomic_ref/partition_branchless_par.h>
template<typename RandomIt, typename Compare, typename T = typename std::iterator_traits<RandomIt>::value_type, typename diff_t = typename std::iterator_traits<RandomIt>::difference_type>
void ppqsort::impl::cpp::process_blocks_branchless(const RandomIt& g_begin, const Compare& comp, const diff_t& g_size, std::atomic<diff_t>& g_distance, std::atomic<diff_t>& g_first_offset, std::atomic<diff_t>& g_last_offset, const int& block_size, const T& pivot, std::atomic<unsigned char>& g_already_partitioned, std::atomic<int>& g_dirty_blocks_left, std::atomic<int>& g_dirty_blocks_right, std::unique_ptr<std::atomic<bool>[]>& g_reserved_left, std::unique_ptr<std::atomic<bool>[]>& g_reserved_right, std::barrier<>& barrier, const int t_my_id, std::latch& part_done)

#include <ppqsort/parallel/cpp/no_atomic_ref/partition_branchless_par.h>
template<class RandomIt, class Compare, typename T = typename std::iterator_traits<RandomIt>::value_type, typename diff_t = typename std::iterator_traits<RandomIt>::difference_type>
std::pair<RandomIt, bool> ppqsort::impl::cpp::partition_right_branchless_par(const RandomIt g_begin, const RandomIt g_end, Compare comp, const int thread_count, ThreadPool<>& thread_pool)

#include <ppqsort/parallel/cpp/no_atomic_ref/partition_par.h>
template<side s, typename diff_t>
bool ppqsort::impl::cpp::get_new_block(diff_t& t_iter, diff_t& t_block_bound, std::atomic<diff_t>& g_distance, std::atomic<diff_t>& g_offset, const int& block_size)

#include <ppqsort/parallel/cpp/no_atomic_ref/partition_par.h>
template<side s, typename RandomIt, typename diff_t>
void ppqsort::impl::cpp::swap_blocks(const std::atomic<int>& g_dirty_blocks_side, const RandomIt& g_begin, const diff_t& t_old, const diff_t& t_block_bound, std::unique_ptr<std::atomic<bool>[]>& reserved, const int& block_size)

#include <ppqsort/parallel/cpp/no_atomic_ref/partition_par.h>
template<typename RandomIt, typename diff_t>
void ppqsort::impl::cpp::swap_dirty_blocks(const RandomIt& g_begin, const diff_t& t_left, const diff_t& t_right, const diff_t& t_left_end, const diff_t& t_right_start, std::atomic<int>& g_dirty_blocks_left, std::atomic<int>& g_dirty_blocks_right, std::atomic<diff_t>& g_first_offset, std::atomic<diff_t>& g_last_offset, std::unique_ptr<std::atomic<bool>[]>& g_reserved_left, std::unique_ptr<std::atomic<bool>[]>& g_reserved_right, const int& block_size, std::barrier<>& barrier, const int& t_my_id)

#include <ppqsort/parallel/cpp/no_atomic_ref/partition_par.h>
template<typename RandomIt, typename Compare, typename T = typename std::iterator_traits<RandomIt>::value_type, typename diff_t = typename std::iterator_traits<RandomIt>::difference_type>
void ppqsort::impl::cpp::process_blocks(const RandomIt& g_begin, const Compare& comp, const diff_t& g_size, std::atomic<diff_t>& g_distance, std::atomic<diff_t>& g_first_offset, std::atomic<diff_t>& g_last_offset, const int& block_size, const T& pivot, std::atomic<unsigned char>& g_already_partitioned, std::atomic<int>& g_dirty_blocks_left, std::atomic<int>& g_dirty_blocks_right, std::unique_ptr<std::atomic<bool>[]>& g_reserved_left, std::unique_ptr<std::atomic<bool>[]>& g_reserved_right, std::barrier<>& barrier, const int t_my_id, std::latch& part_done)

#include <ppqsort/parallel/cpp/no_atomic_ref/partition_par.h>
template<typename RandomIt, typename Compare, typename T = typename std::iterator_traits<RandomIt>::value_type, typename diff_t = typename std::iterator_traits<RandomIt>::difference_type>
std::pair<RandomIt, bool> ppqsort::impl::cpp::partition_to_right_par(const RandomIt g_begin, const RandomIt g_end, Compare comp, const int thread_count, ThreadPool<>& thread_pool)

#include <ppqsort/parallel/cpp/partition_branchless_par.h>
template<typename RandomIt, typename Compare, typename T = typename std::iterator_traits<RandomIt>::value_type, typename diff_t = typename std::iterator_traits<RandomIt>::difference_type>
void ppqsort::impl::cpp::process_blocks_branchless(const RandomIt& g_begin, const Compare& comp, const diff_t& g_size, std::atomic<diff_t>& g_distance, diff_t& g_first_offset, diff_t& g_last_offset, const int& block_size, const T& pivot, unsigned char& g_already_partitioned, std::atomic<int>& g_dirty_blocks_left, std::atomic<int>& g_dirty_blocks_right, std::unique_ptr<std::atomic<bool>[]>& g_reserved_left, std::unique_ptr<std::atomic<bool>[]>& g_reserved_right, std::barrier<>& barrier, const int t_my_id, std::latch& part_done)

#include <ppqsort/parallel/cpp/partition_par.h>
template<side s, typename diff_t>
bool ppqsort::impl::cpp::get_new_block(diff_t& t_iter, diff_t& t_block_bound, std::atomic<diff_t>& g_distance, std::atomic_ref<diff_t>& g_offset, const int& block_size)

#include <ppqsort/parallel/cpp/partition_par.h>
template<typename RandomIt, typename diff_t>
void ppqsort::impl::cpp::swap_dirty_blocks(const RandomIt& g_begin, const diff_t& t_left, const diff_t& t_right, const diff_t& t_left_end, const diff_t& t_right_start, std::atomic<int>& g_dirty_blocks_left, std::atomic<int>& g_dirty_blocks_right, std::atomic_ref<diff_t>& a_g_first_offset, std::atomic_ref<diff_t>& a_g_last_offset, std::unique_ptr<std::atomic<bool>[]>& g_reserved_left, std::unique_ptr<std::atomic<bool>[]>& g_reserved_right, const int& block_size, std::barrier<>& barrier, const int& t_my_id)

#include <ppqsort/parallel/cpp/partition_par.h>
template<typename RandomIt, typename Compare, typename T = typename std::iterator_traits<RandomIt>::value_type, typename diff_t = typename std::iterator_traits<RandomIt>::difference_type>
void ppqsort::impl::cpp::process_blocks(const RandomIt& g_begin, const Compare& comp, const diff_t& g_size, std::atomic<diff_t>& g_distance, diff_t& g_first_offset, diff_t& g_last_offset, const int& block_size, const T& pivot, unsigned char& g_already_partitioned, std::atomic<int>& g_dirty_blocks_left, std::atomic<int>& g_dirty_blocks_right, std::unique_ptr<std::atomic<bool>[]>& g_reserved_left, std::unique_ptr<std::atomic<bool>[]>& g_reserved_right, std::barrier<>& barrier, const int t_my_id, std::latch& part_done)