[Bug libstdc++/66742] abort on sorting list with custom allocator that is not stateless

[cvs-commit at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=66742

--- Comment #16 from CVS Commits <cvs-commit at gcc dot gnu.org> ---
The master branch has been updated by Jonathan Wakely <redi@gcc.gnu.org>:

https://gcc.gnu.org/g:ff7793bea465019683b3a07d7ffceb6eae22def5

commit r12-4082-gff7793bea465019683b3a07d7ffceb6eae22def5
Author: Jonathan Wakely <jwakely@redhat.com>
Date:   Tue May 25 14:33:15 2021 +0100

    libstdc++: Allow stateful allocators in std::list::sort [PR 66742]

    The temporary lists used by std::list::sort are default constructed,
    which means they use default constructed allocators. The sort operation
    is defined in terms of merge and splice operations, which have undefined
    behaviour (and abort) if the allocators do not compare equal. This means
    it is not possible to sort a list that uses an allocator that compares
    unequal to an default constructed allocator.

    The solution is to avoid using temporary std::list objects at all. We do
    not need to be able to allocate memory because no nodes are allocated,
    only spliced from one list to another. That means the temporary lists
    don't need an allocator at all, so whether it would compare equal
    doesn't matter.

    Instead of temporary std::list objects, we can just use a collection of
    _List_node_base objects that nodes can be spliced onto as needed. Those
    objects are wrapped in a _Scratch_list type that implements the splicing
    and merging operations used by list::sort.

    We also don't need to update the list size during the sort, because
    sorting doesn't alter the number of nodes. Although we move nodes in and
    out of the scratch lists, at the end of the function all nodes are back
    in the original std::list and the scratch lists are empty.  So for the
    cxx11 ABI we can avoid the _M_size modifications usually done when
    splicing nodes.

    Signed-off-by: Jonathan Wakely <jwakely@redhat.com>

    libstdc++-v3/ChangeLog:

            PR libstdc++/66742
            * include/bits/list.tcc (list::sort()): Use _Scratch_list
            objects for splicing and merging.
            (list::sort(StrictWeakOrdering)): Likewise.
            * include/bits/stl_list.h (__detail::_Scratch_list): New type.
            * src/c++98/list.cc (_List_node_base::_M_transfer): Add
            assertion for --enable-libstdcxx-debug library.
            * testsuite/23_containers/list/operations/66742.cc: New test.