Re: [Boost-users] Problem with multi_index and shared_ptr
Hello John, johneddy101@comcast.net ha escrito:
I'm running into a problem while using hashed indices in a container storing shared_ptr's. The problem is occuring in the hashed_index::erase(key) method in both the 1_33_1 release and the CVS head version. This is what the problem seems to be:
It is possible that the call to erase (or final_erase_) occurring within the do loop causes destruction of the passed in key object. The key object (k) is then used in a comparison in the while portion of the loop (y!=x&&eq(k, key( ))). The default predicate uses == in this comparison but one of the items (the left hand side) will have already been destroyed.
Umm... Thank you for spotting this, indeed the key passed to erase() can become invalid during the process if it physically belongs to one of the elements to be erased. Matter of fact, the problem is not specifically related to shared_ptr's. I don't know if it's too late to try to fix this on time for Boost 1.34; in case I find the time and permission to do it I'll let you know.
I'm afraid that I don't know a good solution to this problem. I see from your commit logs on this file that there is a problem using something like is done in the ordered_indices (deleting equal_range items) whereby it increases the complexity. I can see from the implementation of equal_range on hashed indices that this is a potentially expensive operation for non-unique collections with many collisions. However, since speed is a secondary consideration for me, this is the solution I'm using for now.
Do you mean that instead of c.erase(k); you do the following? std::pair<iterator,iterator> p=c.equal_range(k); c.erase(p.first,p.second); This is a viable solution. The potential performance problem you point out is actually present in both methods. On the other hand, the different problem I talk about in the commit logs only affects to erase(first,last), not erase(k), and is exposed here: http://open-std.org/jtc1/sc22/wg21/docs/papers/2006/n2023.pdf An alternative solution is to do the following: c.erase(key_type(k)); i.e. doing an external copy of the key before calling erase(k). This is the solution I'd use if your keys are cheap to copy.
Thanks,
John
Thank you for reporting, good luck with your project. Joaquín M López Muñoz Telefónica, Investigación y Desarrollo
Joaquín Mª López Muñoz ha escrito:
Hello John,
johneddy101@comcast.net ha escrito:
I'm running into a problem while using hashed indices in a container storing shared_ptr's. The problem is occuring in the hashed_index::erase(key) method in both the 1_33_1 release and the CVS head version. This is what the problem seems to be:
It is possible that the call to erase (or final_erase_) occurring within the do loop causes destruction of the passed in key object. The key object (k) is then used in a comparison in the while portion of the loop (y!=x&&eq(k, key( ))). The default predicate uses == in this comparison but one of the items (the left hand side) will have already been destroyed.
Umm... Thank you for spotting this, indeed the key passed to erase() can become invalid during the process if it physically belongs to one of the elements to be erased. Matter of fact, the problem is not specifically related to shared_ptr's.
I don't know if it's too late to try to fix this on time for Boost 1.34; in case I find the time and permission to do it I'll let you know.
An update on this. The following rewrite of erase(key) in hashed_index.hpp should clear the problem: size_type erase(key_param_type k) { BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT; size_type s=0; std::size_t buc=buckets.position(hash(k)); hashed_index_node_impl* x=buckets.at(buc); hashed_index_node_impl* y=x->next(); while(y!=x){ if(eq(k,key(node_type::from_impl(y)->value()))){ bool b; do{ hashed_index_node_impl* z=y->next(); b=z!=x&&eq( key(node_type::from_impl(y)->value()), key(node_type::from_impl(z)->value())); this->final_erase_( static_cast<final_node_type*>(node_type::from_impl(y))); y=z; ++s; }while(b); break; } y=y->next(); } return s; } Would you mind pasting this into your local copy of hashed_index.hpp (CVS version) and report whether your prior problems get solved? I'm writing a testcase for the issue and running my entire regression tests, if everything goes OK I think I'll be able to commit this into the CVS before the week ends. Thank you, Joaquín M López Muñoz Telefónica, Investigación y Desarrollo
participants (5)
-
Joaquín Mª López Muñoz