Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

Out-of-bound access in grail_sorter #183

Closed
Morwenn opened this issue Feb 3, 2021 · 0 comments
Closed

Out-of-bound access in grail_sorter #183

Morwenn opened this issue Feb 3, 2021 · 0 comments
Labels
bug
Milestone
1.10.0

Comments

@Morwenn
Copy link
Owner

Morwenn commented Feb 3, 2021

When running the test suite with MSVC in Debug mode, some grail_sorter tests failed because of the creation of out-of-bounds iterators.

353 - every random-access sorter with stable_adapter - cppsort::grail_sorter<> (Failed)
407 - test random-access sorters with all_equal distribution - cppsort::grail_sorter<> (Failed)
408 - test random-access sorters with all_equal distribution - cppsort::grail_sorter< cppsort::utility::dynamic_buffer<cppsort::utility::sqrt> > (Failed)
445 - test sorter with alternating_16_values distribution - cppsort::grail_sorter<> (Failed)
446 - test sorter with alternating_16_values distribution - cppsort::grail_sorter< cppsort::utility::dynamic_buffer<cppsort::utility::sqrt> > (Failed)
651 - test sorter with shuffled_16_values distribution - cppsort::grail_sorter<> (Failed)
652 - test sorter with shuffled_16_values distribution - cppsort::grail_sorter< cppsort::utility::dynamic_buffer<cppsort::utility::sqrt> > (Failed)

There is a clear pattern here: grail_sorter fails when there are lots of equivalent elements, which means that the culprit is likely in strategy 2 and/or strategy 3.
@Morwenn Morwenn added the bug label Feb 3, 2021
Morwenn added a commit that referenced this issue Feb 8, 2021
@Morwenn
Fix invalid iterators in grailsort strategy 3 (#183)
39c15d5 
Grailsort creates invalid pointers here and there that are never
dereferenced, so generally don't cause any issues. However, forming
invalid iterators like that might cause issues, and MSVC debug iterators
do trip on grailsort.

This commit only fixes "strategy 3": when the algorithm can't find at
least 4 unique keys in the collection.
Morwenn added a commit that referenced this issue Feb 14, 2021
@Morwenn
Fix invalid iterators in grailsort strategy 2 (#183)
e49dd01
@Morwenn Morwenn added this to the 1.10.0 milestone Feb 14, 2021
@Morwenn Morwenn closed this as completed Feb 14, 2021
Morwenn added a commit that referenced this issue Feb 16, 2021
@Morwenn
Fix invalid iterators in grailsort strategy 3 (#183)
a5db222 
Grailsort creates invalid pointers here and there that are never
dereferenced, so generally don't cause any issues. However, forming
invalid iterators like that might cause issues, and MSVC debug iterators
do trip on grailsort.

This commit only fixes "strategy 3": when the algorithm can't find at
least 4 unique keys in the collection.
Morwenn added a commit that referenced this issue Feb 16, 2021
@Morwenn
Fix invalid iterators in grailsort strategy 2 (#183)
e0b4f3b
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
bug
Projects
None yet
Milestone
1.10.0
Development

No branches or pull requests
1 participant
@Morwenn