Re: [Boost-bugs] [Boost C++ Libraries] #1968: Dead loop bug in multi_index

Subject: Re: [Boost-bugs] [Boost C++ Libraries] #1968: Dead loop bug in multi_index
From: Boost C++ Libraries (noreply_at_[hidden])
Date: 2008-05-30 16:18:41

#1968: Dead loop bug in multi_index
----------------------------------------------+-----------------------------
  Reporter:  Zachary_zhou <zac_zhou_at_[hidden]>  |       Owner:  joaquin    
      Type:  Bugs                             |      Status:  closed     
 Milestone:  Boost 1.36.0                     |   Component:  multi_index
   Version:  Boost 1.35.0                     |    Severity:  Problem    
Resolution:  invalid                          |    Keywords:  dead loop  
----------------------------------------------+-----------------------------
Changes (by joaquin):

  * status:  new => closed
  * resolution:  => invalid

Comment:

 Hello Zachary, I'm closing this as a non-bug, but you've
 touched on a very tricky issue and an explanation is in
 order. I've been able to reproduce the problem you describe,
 except that the neverending loop happens always, regardless
 of whether I'm in debug mode or no (so, I don't have an
 explanation for your differing behavior when using gdb).
 The problem can be reduced to the following snippet:
 {{{
 #include <boost/multi_index_container.hpp>
 #include <boost/multi_index/hashed_index.hpp>
 #include <boost/multi_index/identity.hpp>

 struct do_nothing
 {
   template<typename T> void operator()(const T&)const{}
 };

 int main()
 {
   using namespace boost::multi_index;

   typedef multi_index_container<
     int,
     indexed_by<hashed_non_unique<identity<int> > >
   > hashed_container;

   hashed_container c;
   c.insert(0);
   c.insert(0);
   std::pair<
     hashed_container::iterator,
     hashed_container::iterator
   > p=c.equal_range(0);
   while(p.first!=p.second){
     c.modify(p.first,do_nothing());
     ++p.first;
   }
 }
 }}}
 The program inserts two identical elements 0 into a
 multi_index_container with a hashed index and then
 iterate over them and modify them, although  the
 modifying functor does not really do anything.
 Nevertheless, the loop does not end! How come? The
 key point to understand here is that
 {{{
   modify(it,mod)
 }}}
 is free to rearrange the element pointed to by it even
 if the key has not been modified: by virtue of its
 internal machinery, an element in a (non-unique) hashed
 index gets moved right before every other equivalent
 element after modify(); this is legal as the only
 requirement is that equivalent elements remain together.
 So, when the program reaches the second 0 element, this
 is moved to the front position and the loop keeps
 stepping into itself ad infinitum. The same thing happens
 with the example you've provided.

 So, inconvenient as the behavior is I'm not labeling it
 as a bug since the guarantee you relied upon (unmodified
 elements retain their position) has never been given (and
 it's not easy to provide for hashed indices). What can
 you do to circumvent this? Three options come to mind
 (I continue my exposition with the snippet above, but
 translating to your own code should be straigthforward):

 1. Increment the iterator before modifying the element:
 {{{
   while(p.first!=p.second){
     c.modify(p.first++,do_nothing());
   }
 }}}
 This *happens* to work but again you're relying and
 undocumented behavior: a conformant implementation of
 B.MI could move elements after their equivalent
 elements and you'd be in a neverending loop again.

 2. Use a ordered_non_unique index instead of a
 hashed_non_unique: ordered indices do not move equivalent
 elements around in a modify() operation; again, this is
 undocumented and you'd be playing at your own risk.

 3. Use replace() instead of modify():
 {{{
   while(p.first!=p.second){
     c.replace(p.first,0);
     ++p.first;
   }
 }}}
 replace() does guarantee that an element with an unchanged
 key is not moved anywhere (I've reread the docs and this
 guarantee is not explicitly mentioned, though, I'll update
 the reference accordingly).

 So, (3) is the only legal choice, but if you don't mind
 playing with undocumented features you can stick with
 the simpler (and marginally faster) option (1).

 Hope this helps, please reopen the ticket if something is
 not entirely clear.

-- 
Ticket URL: <http://svn.boost.org/trac/boost/ticket/1968#comment:1>
Boost C++ Libraries <http://www.boost.org/>
Boost provides free peer-reviewed portable C++ source libraries.