Morwenn / cpp-sort

Sorting algorithms & related tools for C++14
MIT License
617 stars 57 forks source link

grail_sorter calls swap_ranges on overlapping ranges #180

Closed Morwenn closed 3 years ago

Morwenn commented 3 years ago

I recently noticed that swap_ranges was occasionally called on overlapping ranges, which is prohibited by the standard. It wasn't a problem until I tried to implement swap_ranges differently and ended up being bitten by this failed precondition.

Actions:

Morwenn commented 3 years ago

In the end I did not implement an "optimized" swap_ranges function for which the no-overlap guarantee really mattered because it encountered too many optimization issues that made it actually worse in what looked like easy-to-optimize cases. Anyway, instead of just having swap_ranges calls all over the place, I decided to replace them with three different functions:

Now there wasn't a single swap_ranges called between unrelated ranges in the library, so the implementation doesn't contain any such "normal" swap_ranges. The rest of the call were split between swap_ranges_overlap and swap_ranges_inner, with a conservative bias toward the former when I wasn't sure whether the ranges could actually overlap or not. This means that more checks can occur when debugging, and it will be easier to introduce an optimized swap_ranges function that actually requires the no-overlap guarantee in the future.

I also introduced CPPSORT_AUDIT and the user-definable macro CPPSORT_ENABLE_AUDITS to check that the ranges passed to swap_ranges_inner don't overlap.