public inbox for gcc-bugs@sourceware.org
help / color / mirror / Atom feed
* [Bug libstdc++/61107] New: [4.8/4.9/4.10] stl_algo.h : std::__inplace_stable_partition() doesn't process the whole data range
@ 2014-05-07 22:46 tomytsai at gmail dot com
  2014-10-08 21:21 ` [Bug libstdc++/61107] stl_algo.h: " fdumont at gcc dot gnu.org
  0 siblings, 1 reply; 2+ messages in thread
From: tomytsai at gmail dot com @ 2014-05-07 22:46 UTC (permalink / raw)
  To: gcc-bugs

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=61107

            Bug ID: 61107
           Summary: [4.8/4.9/4.10] stl_algo.h :
                    std::__inplace_stable_partition() doesn't process the
                    whole data range
           Product: gcc
           Version: 4.10.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: libstdc++
          Assignee: unassigned at gcc dot gnu.org
          Reporter: tomytsai at gmail dot com

In GCC 4.8.2 / 4.9 (20140430 snapsot) / 4.10.0 (20140504 snapshot)

If we test the following code:

  auto vec = vector<int> {1, 0, 1}
  auto cmp = [] (int v) {return v == 0;};
  std::__inplace_stable_partition( begin(vec), cmp, vec.size() )

  final vec == {1, 0, 1}
  (the expected result is {0, 1, 1})

It is because of the following line in stl_algo.h :
__inplace_stable_partition()

(from
http://gcc.gnu.org/onlinedocs/gcc-4.9.0/libstdc++/api/a01499_source.html#l01519)

1531  _ForwardIterator __right_split =
1532  std::__find_if_not_n(__middle, __right_len, __pred);
1533  if (__right_len)
1534  __right_split = std::__inplace_stable_partition(__middle,
1535  __pred,
1536  __right_len);

In line 1534, __middle should be replaced with __right_split. Otherwise,
the recursive call will start from __middle, with the updated __right_len
(modified by __find_if_not_n() ), That is, if  __find_if_not_n()  reduces
__right_len , some of the tailing data will leave unprocessed by 
the current function.

Note this problem is not critical because:

1. The corresponding function __stable_partition_adaptive() has the right
   logic (it uses __right_split instead of __middle ). Maybe someone forgot
   to update __inplace_stable_partition() when he/she updated 
   __stable_partition_adaptive().

2. This function is only called when the available buffer size is 0. Otherwise,
   __stable_partition_adaptive() will be called and it has mirrored all the 
   codes from __stable_partition_adaptive(), with the correct logic.

However it is still good to patch this bug. We can do either
   1. Replace the __middle with __right_split , as shown above.
or 2. From stable_partition() , call __stable_partition_adaptive() exclusively.
      This way we can totally remove __inplace_stable_partition(), as 
      __stable_partition_adaptive() is doing the same thing if the memory is 
      not enough (or totally not available).

Thanks!

Tomy


^ permalink raw reply	[flat|nested] 2+ messages in thread
end of thread, other threads:[~2014-10-08 21:21 UTC | newest]

Thread overview: 2+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2014-05-07 22:46 [Bug libstdc++/61107] New: [4.8/4.9/4.10] stl_algo.h : std::__inplace_stable_partition() doesn't process the whole data range tomytsai at gmail dot com
2014-10-08 21:21 ` [Bug libstdc++/61107] stl_algo.h: " fdumont at gcc dot gnu.org

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).