Dead loop bug in multi_index

[Zachary_zhou <zac_zhou@…>]

The bug can be replayed in the following attachment. The program can run ok if debug using gdb and run in single steps. But in full speed running test, the program will fall in a dead loop if modify is used, maybe it will cause the change of iterator?

The bug can be replayed on linux 2.6.25-2-686 gcc version 4.2.4 and windows vs2005.

[Zachary_zhou <zac_zhou@…>]

the bug project sample

[Joaquín M López Muñoz]

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.