http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/libstdc++-v3/include/bits/stl_heap.h?rev=1.16&content-type=text/x-cvsweb-markup Any function that relies on the __adjust_heap functions have a potential integer overflow error in their calculation of __secondChild.
Actually, all the callers of __adjust_heap either pass a null second argument, or a "small" second argument (case of make_heap). Thus, no real risks. Notice that the function is an internal detail (double underscore prefix) and is not supposed to be externally used.
I know there are no practical risks to this (heap isn't that popular and it's practically impossible to allocate an array that large) but it won't work if the user made a custom iterator with unsigned char as the size_type and signed char as the distance_type on a machine with small chars. The initialization of __secondChild isn't the problem, it's the updating of it in the loop that will cause it.
Please, either provide an analysis that the problem really happens, *given the specific algorithm*, or provide a testcase.
Ok, let's reopen the PR as "enhancement": actually, it's easy to produce a testcase that leads to __secondChild growing beyond __len and the latter can be equal to the biggest representable _Distance.
Working on a fix.
A straightforward approach to the problem uses the unsigned type associated with _Distance (via __gnu_cxx::__add_unsigned) to avoid the risk of overflows in __adjust_heap completely. I'm currently looking into the cleanest way to follow this route...
Subject: Bug 21172 Author: paolo Date: Tue Feb 13 00:25:30 2007 New Revision: 121875 URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=121875 Log: 2007-02-12 Paolo Carlini <pcarlini@suse.de> PR libstdc++/21172 * include/bits/stl_heap.h (__adjust_heap(_RandomAccessIterator, _Distance, _Distance, _Tp), __adjust_heap(_RandomAccessIterator, _Distance, _Distance, _Tp, _Compare)): Avoid potential integer overflow. * include/bits/stl_heap.h (__is_heap(_RandomAccessIterator, _RandomAccessIterator), __is_heap(_RandomAccessIterator, _RandomAccessIterator, _StrictWeakOrdering): Mark inline. (make_heap(_RandomAccessIterator, _RandomAccessIterator, _Compare)): Do not mark inline. * include/bits/stl_heap.h (push_heap(_RandomAccessIterator, _RandomAccessIterator), sort_heap(_RandomAccessIterator, _RandomAccessIterator)): Uncomment __glibcxx_requires_heap. Modified: trunk/libstdc++-v3/ChangeLog trunk/libstdc++-v3/include/bits/stl_heap.h
Fixed.