Module: ppl/ppl Branch: master Commit: 0873d966a21ec85959b2d8274e9e3ac561a3a09f URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=0873d966a21ec... Author: Enea Zaffanella <zaffanella@cs.unipr.it> Date: Fri Aug 17 17:13:39 2012 +0200 Added helper method insert_precise_aux to avoid recursive call. Detected by ECLAIR service funrecsn. --- src/CO_Tree.cc | 70 +++++++++++++++++++++++++++++--------------------- src/CO_Tree.defs.hh | 11 ++++++++ 2 files changed, 52 insertions(+), 29 deletions(-) diff --git a/src/CO_Tree.cc b/src/CO_Tree.cc index cbc1d50..68d49d4 100644 --- a/src/CO_Tree.cc +++ b/src/CO_Tree.cc @@ -357,54 +357,69 @@ PPL::CO_Tree::insert_precise(dimension_type key1, PPL_ASSERT(!empty()); #ifndef NDEBUG + // Check that `itr' is a correct hint. tree_iterator itr2(*this); itr2.go_down_searching_key(key1); PPL_ASSERT(itr == itr2); #endif if (itr.index() == key1) { + // Replacement, rather than insertion. *itr = data1; PPL_ASSERT(OK()); return itr; } - if (data <= &data1 && &data1 < data + (reserved_size + 1)) { - // data1 is a coefficient of this row. - // Avoid invalidating it. - data_type x = data1; + // Proper insertion: check if it would invalidate `data1'. + const bool invalidating + = (data <= &data1) && (&data1 < data + (reserved_size + 1)); + + if (!invalidating) + return insert_precise_aux(key1, data1, itr); + + // `data1' could be invalidated by the insert, because it is + // a coefficient of this row. Avoid the issue by copying it. + data_type data1_copy = data1; #ifndef NDEBUG - dimension_type i = &data1 - data; - dimension_type key2 = indexes[i]; - PPL_ASSERT(key2 != unused_index); - // This is true since key1 is not in the tree. - PPL_ASSERT(key2 != key1); + dimension_type i = &data1 - data; + dimension_type key2 = indexes[i]; + PPL_ASSERT(key2 != unused_index); + // This is true since `key1' is not in the tree. + PPL_ASSERT(key2 != key1); #endif - // Insert a dummy coefficient. - // NOTE: This may invalidate data1, because it may reallocate the tree - // and/or move coefficients during rebalancing). - itr = insert_precise(key1, Coefficient_zero(), itr); + // Insert a dummy coefficient. + // NOTE: this may invalidate `data1', because it may reallocate the tree + // and/or move coefficients during rebalancing. + itr = insert_precise_aux(key1, Coefficient_zero(), itr); - PPL_ASSERT(itr.index() == key1); + PPL_ASSERT(itr.index() == key1); - using std::swap; + // Swap the correct coefficient in place. + using std::swap; + swap(*itr, data1_copy); - // Swap the correct coefficient in place. - swap(*itr, x); + PPL_ASSERT(OK()); + return itr; +} - PPL_ASSERT(OK()); - return itr; - } +PPL::CO_Tree::tree_iterator +PPL::CO_Tree::insert_precise_aux(dimension_type key1, + data_type_const_reference data1, + tree_iterator itr) { + PPL_ASSERT(key1 != unused_index); + PPL_ASSERT(!empty()); + // This is a proper insert. + PPL_ASSERT(itr.index() != key1); + // `data1' is not going to be invalidated. + PPL_ASSERT(!(data <= &data1 && &data1 < data + (reserved_size + 1))); if (is_greater_than_ratio(size_ + 1, reserved_size, max_density_percent)) { - rebuild_bigger_tree(); - - // itr was invalidated by the rebuild operation + // `itr' was invalidated by the rebuild operation itr.get_root(); itr.go_down_searching_key(key1); - PPL_ASSERT(itr.index() != key1); } @@ -423,13 +438,10 @@ PPL::CO_Tree::insert_precise(dimension_type key1, new (&(*itr)) data_type(data1); // Set the index only if the construction was successful. itr.index() = key1; - - } else { - + } + else { itr = rebalance(itr, key1, data1); - itr.go_down_searching_key(key1); - PPL_ASSERT(itr.index() == key1); } PPL_ASSERT(OK()); diff --git a/src/CO_Tree.defs.hh b/src/CO_Tree.defs.hh index d02b467..c09f6f8 100644 --- a/src/CO_Tree.defs.hh +++ b/src/CO_Tree.defs.hh @@ -954,6 +954,17 @@ private: data_type_const_reference data, tree_iterator itr); + //! Helper for \c insert_precise. + /*! + This helper method takes the same arguments as \c insert_precise, + but besides assuming that \p itr is a correct hint, it also assumes + that \p key and \p data are not in the tree; namely, a proper + insertion has to be done and the insertion can not invalidate \p data. + */ + tree_iterator insert_precise_aux(dimension_type key, + data_type_const_reference data, + tree_iterator itr); + //! Inserts an element in the tree. /*!