sc/source/core/tool/rangelst.cxx | 164 +++++++++++++++++++++------------------
1 file changed, 89 insertions(+), 75 deletions(-)
New commits:
commit 74812a91ff29f6968dceba093250064985c0baa7
Author: Eike Rathke <er...@redhat.com>
Date: Mon Jan 22 19:55:38 2018 +0100
Flatten ScRangeList::Join() and ScRangePairList::Join() recursion
This is a combination of 2 commits.
Flatten ScRangeList::Join() recursion
Joining an existing list of identical ranges could end up in a
very deep (but not infinite) recursion which could lead to stack
exhaustion. Recursion is unnecessary if we re-enter the loop with
the picked range. Continuing the loop as it was done after
recursion isn't necessary either, to the contrary, as long as
there is one join try the entire list again.
Commit f6eefd96cb16a9b5607fe59bdbf9b1121c9b56e8 pointed this out
as the UBSan build runs with ulimit -s 8192
Reviewed-on: https://gerrit.libreoffice.org/48360
Reviewed-by: Eike Rathke <er...@redhat.com>
Tested-by: Jenkins <c...@libreoffice.org>
(cherry picked from commit 03f429665b4d57f63b8e2862a55e5c4273bc7a2b)
Flatten ScRangePairList::Join() recursion
Similar to ScRangeList::Join() done before.
Reviewed-on: https://gerrit.libreoffice.org/48361
Reviewed-by: Eike Rathke <er...@redhat.com>
Tested-by: Jenkins <c...@libreoffice.org>
(cherry picked from commit 73049e5dbf9430df077dd26bed9d01435f745544)
e513b4c72bc211c196e13761b63446174321a389
Conflicts:
sc/source/core/tool/rangelst.cxx
Backported.
Change-Id: Ibbc542fc8ae6d1509744aa731771eb6e32a38841
Reviewed-on: https://gerrit.libreoffice.org/48411
Tested-by: Jenkins <c...@libreoffice.org>
Reviewed-by: Caolán McNamara <caol...@redhat.com>
Tested-by: Caolán McNamara <caol...@redhat.com>
diff --git a/sc/source/core/tool/rangelst.cxx b/sc/source/core/tool/rangelst.cxx
index 19fed29aba75..f4d9170c0161 100644
--- a/sc/source/core/tool/rangelst.cxx
+++ b/sc/source/core/tool/rangelst.cxx
@@ -218,12 +218,6 @@ void ScRangeList::Join( const ScRange& r, bool bIsInList )
Append( r );
return ;
}
- SCCOL nCol1 = r.aStart.Col();
- SCROW nRow1 = r.aStart.Row();
- SCTAB nTab1 = r.aStart.Tab();
- SCCOL nCol2 = r.aEnd.Col();
- SCROW nRow2 = r.aEnd.Row();
- SCTAB nTab2 = r.aEnd.Tab();
// One common usage is to join ranges that actually are top to bottom
// appends but the caller doesn't exactly know about it, e.g. when invoked
@@ -236,6 +230,7 @@ void ScRangeList::Join( const ScRange& r, bool bIsInList )
if (!bIsInList)
{
+ const SCROW nRow1 = r.aStart.Row();
if (nRow1 > mnMaxRowUsed + 1)
{
Append( r );
@@ -246,9 +241,10 @@ void ScRangeList::Join( const ScRange& r, bool bIsInList )
// Check if we can simply enlarge the last range.
ScRange* p = maRanges.back();
if (p->aEnd.Row() + 1 == nRow1 &&
- p->aStart.Col() == nCol1 && p->aEnd.Col() == nCol2 &&
- p->aStart.Tab() == nTab1 && p->aEnd.Tab() == nTab2)
+ p->aStart.Col() == r.aStart.Col() && p->aEnd.Col() ==
r.aEnd.Col() &&
+ p->aStart.Tab() == r.aStart.Tab() && p->aEnd.Tab() ==
r.aEnd.Tab())
{
+ const SCROW nRow2 = r.aEnd.Row();
p->aEnd.SetRow( nRow2 );
mnMaxRowUsed = nRow2;
return;
@@ -256,43 +252,45 @@ void ScRangeList::Join( const ScRange& r, bool bIsInList )
}
}
- ScRange* pOver = const_cast<ScRange*>(&r); // fies aber wahr wenn
bInList
- size_t nOldPos = 0;
- if ( bIsInList )
- {
- // Find the current position of this range.
- for ( size_t i = 0, nRanges = maRanges.size(); i < nRanges; ++i )
- {
- if ( maRanges[i] == pOver )
- {
- nOldPos = i;
- break;
- }
- }
- }
bool bJoinedInput = false;
+ const ScRange* pOver = &r;
+
+Label_Range_Join:
- // We need to query the size of the container dynamically since its size
- // may change during the loop.
- for ( size_t i = 0; i < maRanges.size() && pOver; ++i )
+ assert(pOver);
+ const SCCOL nCol1 = pOver->aStart.Col();
+ const SCROW nRow1 = pOver->aStart.Row();
+ const SCCOL nTab1 = pOver->aStart.Tab();
+ const SCCOL nCol2 = pOver->aEnd.Col();
+ const SCROW nRow2 = pOver->aEnd.Row();
+ const SCCOL nTab2 = pOver->aEnd.Tab();
+
+ size_t nOverPos = std::numeric_limits<size_t>::max();
+ for (size_t i = 0; i < maRanges.size(); ++i)
{
ScRange* p = maRanges[i];
if ( p == pOver )
+ {
+ nOverPos = i;
continue; // the same one, continue with the next
+ }
bool bJoined = false;
- if ( p->In( r ) )
- { //range r included in or identical to range p
+ if ( p->In( *pOver ) )
+ { // range pOver included in or identical to range p
+ // XXX if we never used Append() before Join() we could remove
+ // pOver and end processing, but it is not guranteed and there can
+ // be duplicates.
if ( bIsInList )
- bJoined = true; // do away with range r
+ bJoined = true; // do away with range pOver
else
{ // that was all then
- bJoinedInput = true; // don't attach
+ bJoinedInput = true; // don't append
break; // for
}
}
- else if ( r.In( *p ) )
- { // range p included in range r, make r the new range
- *p = r;
+ else if ( pOver->In( *p ) )
+ { // range p included in range pOver, make pOver the new range
+ *p = *pOver;
bJoined = true;
}
if ( !bJoined && p->aStart.Tab() == nTab1 && p->aEnd.Tab() == nTab2 )
@@ -331,15 +329,25 @@ void ScRangeList::Join( const ScRange& r, bool bIsInList )
if ( bJoined )
{
if ( bIsInList )
- { // delete range within the list
- Remove(nOldPos);
- i--;
- pOver = nullptr;
- if ( nOldPos )
- nOldPos--; // configure seek correctly
+ { // delete range pOver within the list
+ if (nOverPos != std::numeric_limits<size_t>::max())
+ Remove(nOverPos);
+ else
+ {
+ for (size_t nOver = 0, nRanges = maRanges.size(); nOver <
nRanges; ++nOver)
+ {
+ if (maRanges[nOver] == pOver)
+ {
+ Remove(nOver);
+ break;
+ }
+ }
+ }
}
bJoinedInput = true;
- Join( *p, true ); // recursive!
+ pOver = p;
+ bIsInList = true;
+ goto Label_Range_Join;
}
}
if ( !bIsInList && !bJoinedInput )
@@ -1443,53 +1451,49 @@ void ScRangePairList::Join( const ScRangePair& r, bool
bIsInList )
Append( r );
return ;
}
- const ScRange& r1 = r.GetRange(0);
- const ScRange& r2 = r.GetRange(1);
- SCCOL nCol1 = r1.aStart.Col();
- SCROW nRow1 = r1.aStart.Row();
- SCTAB nTab1 = r1.aStart.Tab();
- SCCOL nCol2 = r1.aEnd.Col();
- SCROW nRow2 = r1.aEnd.Row();
- SCTAB nTab2 = r1.aEnd.Tab();
- ScRangePair* pOver = const_cast<ScRangePair*>(&r); // fies aber wahr
wenn bInList
- size_t nOldPos = 0;
- if ( bIsInList )
- {
- // Find the current position of this range.
- for ( size_t i = 0, nPairs = maPairs.size(); i < nPairs; ++i )
- {
- if ( maPairs[i] == pOver )
- {
- nOldPos = i;
- break;
- }
- }
- }
- bool bJoinedInput = false;
- for ( size_t i = 0; i < maPairs.size() && pOver; ++i )
+ bool bJoinedInput = false;
+ const ScRangePair* pOver = &r;
+
+Label_RangePair_Join:
+
+ assert(pOver);
+ const ScRange& r1 = pOver->GetRange(0);
+ const ScRange& r2 = pOver->GetRange(1);
+ const SCCOL nCol1 = r1.aStart.Col();
+ const SCROW nRow1 = r1.aStart.Row();
+ const SCTAB nTab1 = r1.aStart.Tab();
+ const SCCOL nCol2 = r1.aEnd.Col();
+ const SCROW nRow2 = r1.aEnd.Row();
+ const SCTAB nTab2 = r1.aEnd.Tab();
+
+ size_t nOverPos = std::numeric_limits<size_t>::max();
+ for (size_t i = 0; i < maPairs.size(); ++i)
{
ScRangePair* p = maPairs[ i ];
if ( p == pOver )
+ {
+ nOverPos = i;
continue; // the same one, continue with the next
+ }
bool bJoined = false;
ScRange& rp1 = p->GetRange(0);
ScRange& rp2 = p->GetRange(1);
if ( rp2 == r2 )
{ // only if Range2 is equal
if ( rp1.In( r1 ) )
- { // RangePair r included in or identical to RangePair p
+ { // RangePair pOver included in or identical to RangePair p
if ( bIsInList )
- bJoined = true; // do away with RangePair r
+ bJoined = true; // do away with RangePair pOver
else
{ // that was all then
- bJoinedInput = true; // don't attach
+ bJoinedInput = true; // don't append
break; // for
}
}
else if ( r1.In( rp1 ) )
- { // RangePair p included in RangePair r enthalten, make r the
new RangePair
- *p = r;
+ { // RangePair p included in RangePair pOver, make pOver the new
RangePair
+ *p = *pOver;
bJoined = true;
}
}
@@ -1539,15 +1543,25 @@ void ScRangePairList::Join( const ScRangePair& r, bool
bIsInList )
if ( bJoined )
{
if ( bIsInList )
- { // delete RangePair within the list
- Remove( nOldPos );
- i--;
- pOver = nullptr;
- if ( nOldPos )
- nOldPos--; // configure seek correctly
+ { // delete RangePair pOver within the list
+ if (nOverPos != std::numeric_limits<size_t>::max())
+ Remove(nOverPos);
+ else
+ {
+ for (size_t nOver = 0, nPairs = maPairs.size(); nOver <
nPairs; ++nOver)
+ {
+ if (maPairs[nOver] == pOver)
+ {
+ Remove(nOver);
+ break;
+ }
+ }
+ }
}
bJoinedInput = true;
- Join( *p, true ); // recursive!
+ pOver = p;
+ bIsInList = true;
+ goto Label_RangePair_Join;
}
}
if ( !bIsInList && !bJoinedInput )
_______________________________________________
Libreoffice-commits mailing list
libreoffice-comm...@lists.freedesktop.org
https://lists.freedesktop.org/mailman/listinfo/libreoffice-commits
