A bottom-up merge sort over row indices that can stop and resume. More...

#include <sort.hpp>

Public Member Functions
	ChunkedMergeSort (std::vector< std::uint32_t > rows, RowOrder order)
	Prepares to sort `rows` by `order`.
bool	run (Deadline deadline, ::core::async::StopToken const &stop)
	Sorts until done, the deadline passes, or a stop is requested.
bool	done () const noexcept
	Whether the sort has finished.
std::vector< std::uint32_t >	take () &&
	The sorted rows. Valid once done().

Static Public Attributes
static constexpr std::size_t	kRun = 512
	Rows per initial run.

Detailed Description

A bottom-up merge sort over row indices that can stop and resume.

Runs of kRun rows are sorted first, then merged pass by pass. run returns at a deadline or a stop request and continues from there on the next call, which is how the engine sorts 100,000 rows on an owner thread in frame-sized steps, or abandons a superseded sort on a worker.

Definition at line 528 of file sort.hpp.

Constructor & Destructor Documentation

◆ ChunkedMergeSort()

morph::table::ChunkedMergeSort::ChunkedMergeSort	(	std::vector< std::uint32_t >	rows,
		RowOrder	order )

inline

Prepares to sort rows by order.

Parameters

rows	Row indices to sort.
order	The comparator; its key columns must outlive the sort.

Definition at line 536 of file sort.hpp.

Member Function Documentation

◆ run()

bool morph::table::ChunkedMergeSort::run	(	Deadline	deadline,
		::core::async::StopToken const &	stop )

inline

Sorts until done, the deadline passes, or a stop is requested.

Parameters

deadline	When to yield.
stop	A stop request ends the step early.

Returns: true when the rows are sorted.

Definition at line 545 of file sort.hpp.

◆ done()

bool morph::table::ChunkedMergeSort::done ( ) const

inlinenodiscardnoexcept

Whether the sort has finished.

Returns: true once run returned true.

Definition at line 551 of file sort.hpp.

◆ take()

std::vector< std::uint32_t > morph::table::ChunkedMergeSort::take ( ) &&

inlinenodiscard

The sorted rows. Valid once done().

Returns: The rows, moved out.

Definition at line 555 of file sort.hpp.

Member Data Documentation

◆ kRun

std::size_t morph::table::ChunkedMergeSort::kRun = 512

staticconstexpr

Rows per initial run.

Definition at line 531 of file sort.hpp.

The documentation for this class was generated from the following file:

morph/table/sort.hpp

Public Member Functions

Static Public Attributes