[Libreoffice-commits] core.git: include/svl svl/source
Jochen Nitschke
j.nitschke+logerrit at ok.de
Sun Oct 30 18:59:37 UTC 2016
include/svl/nranges.hxx | 22 ---
svl/source/items/itemset.cxx | 56 ++++++++-
svl/source/items/nranges.cxx | 250 -------------------------------------------
3 files changed, 52 insertions(+), 276 deletions(-)
New commits:
commit e75561bd19faa332c077ec249a397d056fae63f2
Author: Jochen Nitschke <j.nitschke+logerrit at ok.de>
Date: Sun Oct 30 12:31:26 2016 +0100
bin SfxUShortRanges, inline and rewrite only usage
only use was to merge 2 range tables in SfxItemSet::MergeRange
of which one table always contained a single range.
rewrite the merge algorithm (SfxUShortRanges += operator).
sort new range into the table of ranges and merge overlapping
ranges afterwards. Not as optimal as the original code but it's
short, maintainable and works without 'goto'
inline the DBG_CHECK_RANGES macro
Change-Id: I991c050f069d44fe72b3ea374863f5f26e7099e9
Reviewed-on: https://gerrit.libreoffice.org/30299
Tested-by: Jochen Nitschke <j.nitschke+logerrit at ok.de>
Reviewed-by: Noel Grandin <noel.grandin at collabora.co.uk>
diff --git a/include/svl/nranges.hxx b/include/svl/nranges.hxx
index d374475..d9329d1 100644
--- a/include/svl/nranges.hxx
+++ b/include/svl/nranges.hxx
@@ -22,28 +22,6 @@
#include <cstdarg>
#include <sal/types.h>
-class SfxUShortRanges
-{
- sal_uInt16* _pRanges; // 0-terminated array of sal_uInt16-pairs
-
-public:
- SfxUShortRanges( const SfxUShortRanges &rOrig );
- SfxUShortRanges( sal_uInt16 nWhich1, sal_uInt16 nWhich2 );
- SfxUShortRanges( const sal_uInt16* nNumTable );
- ~SfxUShortRanges()
- { delete [] _pRanges; }
-
- SfxUShortRanges& operator = ( const SfxUShortRanges & );
-
- SfxUShortRanges& operator += ( const SfxUShortRanges & );
-
- bool IsEmpty() const
- { return !_pRanges || 0 == *_pRanges; }
-
- operator const sal_uInt16* () const
- { return _pRanges; }
-};
-
/**
* Creates a sal_uInt16-ranges-array in 'rpRanges' using 'nWh1' and 'nWh2' as
* first range, 'nNull' as terminator or start of 2nd range and 'pArgs' as
diff --git a/svl/source/items/itemset.cxx b/svl/source/items/itemset.cxx
index c104305..745d96a 100644
--- a/svl/source/items/itemset.cxx
+++ b/svl/source/items/itemset.cxx
@@ -593,10 +593,58 @@ void SfxItemSet::MergeRange( sal_uInt16 nFrom, sal_uInt16 nTo )
if ( nFrom == nTo && ( eItemState == SfxItemState::DEFAULT || eItemState == SfxItemState::SET ) )
return;
- // merge new range
- SfxUShortRanges aRanges( m_pWhichRanges );
- aRanges += SfxUShortRanges( nFrom, nTo );
- SetRanges( aRanges );
+#ifdef DBG_UTIL
+ assert(nFrom <= nTo);
+ for (const sal_uInt16 *pRange = m_pWhichRanges; *pRange; pRange += 2)
+ {
+ assert(pRange[0] <= pRange[1]);
+ // ranges must be sorted and discrete
+ assert(!pRange[2] || (pRange[2] - pRange[1]) > 1);
+ }
+#endif
+
+ // create vector of ranges (sal_uInt16 pairs of lower and upper bound)
+ const size_t nOldCount = Count_Impl(m_pWhichRanges);
+ std::vector<std::pair<sal_uInt16, sal_uInt16>> aRangesTable;
+ aRangesTable.reserve(nOldCount/2 + 1);
+ bool bAdded = false;
+ for (size_t i = 0; i < nOldCount; i += 2)
+ {
+ if (!bAdded && m_pWhichRanges[i] >= nFrom)
+ { // insert new range, keep ranges sorted
+ aRangesTable.emplace_back(std::pair<sal_uInt16, sal_uInt16>(nFrom, nTo));
+ bAdded = true;
+ }
+ // insert current range
+ aRangesTable.emplace_back(std::pair<sal_uInt16, sal_uInt16>(m_pWhichRanges[i], m_pWhichRanges[i+1]));
+ }
+ if (!bAdded)
+ aRangesTable.emplace_back(std::pair<sal_uInt16, sal_uInt16>(nFrom, nTo));
+
+ // true if ranges overlap or adjoin, false if ranges are separate
+ auto needMerge = [](std::pair<sal_uInt16, sal_uInt16> lhs, std::pair<sal_uInt16, sal_uInt16> rhs)
+ {return (lhs.first-1) <= rhs.second && (rhs.first-1) <= lhs.second;};
+
+ std::vector<std::pair<sal_uInt16, sal_uInt16> >::iterator it = aRangesTable.begin();
+ // check neighbouring ranges, find first range which overlaps or adjoins a previous range
+ while ((it = std::is_sorted_until(it, aRangesTable.end(), needMerge)) != aRangesTable.end())
+ {
+ --it; // merge with previous range
+ // lower bounds are sorted, implies: it->first = min(it[0].first, it[1].first)
+ it->second = std::max(it[0].second, it[1].second);
+ aRangesTable.erase(std::next(it));
+ }
+
+ // construct range array
+ const size_t nNewSize = 2 * aRangesTable.size() + 1;
+ std::vector<sal_uInt16> aRanges(nNewSize);
+ for (size_t i = 0; i < (nNewSize - 1); i +=2)
+ std::tie(aRanges[i], aRanges[i+1]) = aRangesTable[i/2];
+
+ // null terminate to be compatible with sal_uInt16* array pointers
+ aRanges.back() = 0;
+
+ SetRanges( aRanges.data() );
}
/**
diff --git a/svl/source/items/nranges.cxx b/svl/source/items/nranges.cxx
index 85ed671..9dfb876 100644
--- a/svl/source/items/nranges.cxx
+++ b/svl/source/items/nranges.cxx
@@ -19,35 +19,10 @@
#include <svl/nranges.hxx>
#include <cassert>
-#include <cstring>
#include <vector>
-#include <osl/diagnose.h>
#include <tools/debug.hxx>
-#ifdef DBG_UTIL
-
-#define DBG_CHECK_RANGES(sal_uInt16, pArr) \
- for ( const sal_uInt16 *pRange = pArr; *pRange; pRange += 2 ) \
- { \
- DBG_ASSERT( pRange[0] <= pRange[1], "ranges must be sorted" ); \
- DBG_ASSERT( !pRange[2] || ( pRange[2] - pRange[1] ) > 1, \
- "ranges must be sorted and discrete" ); \
- }
-
-#else
-
-#define DBG_CHECK_RANGES(sal_uInt16,pArr)
-
-#endif
-
-inline void Swap_Impl(const sal_uInt16 *& rp1, const sal_uInt16 *& rp2)
-{
- const sal_uInt16 * pTemp = rp1;
- rp1 = rp2;
- rp2 = pTemp;
-}
-
/**
* Creates a sal_uInt16-ranges-array in 'rpRanges' using 'nWh1' and 'nWh2' as
* first range, 'nNull' as terminator or start of 2nd range and 'pArgs' as
@@ -127,229 +102,4 @@ sal_uInt16 Capacity_Impl( const sal_uInt16 *pRanges )
return nCount;
}
-/**
- * Copy ctor
- */
-SfxUShortRanges::SfxUShortRanges( const SfxUShortRanges &rOrig )
-{
- if ( rOrig._pRanges )
- {
- sal_uInt16 nCount = Count_Impl( rOrig._pRanges ) + 1;
- _pRanges = new sal_uInt16[nCount];
- memcpy( _pRanges, rOrig._pRanges, sizeof(sal_uInt16) * nCount );
- }
- else
- _pRanges = nullptr;
-}
-
-/**
- * Constructs a SfxUShortRanges instance from one range of sal_uInt16s.
- *
- * Precondition: nWhich1 <= nWhich2
- */
-SfxUShortRanges::SfxUShortRanges( sal_uInt16 nWhich1, sal_uInt16 nWhich2 )
-: _pRanges( new sal_uInt16[3] )
-{
- _pRanges[0] = nWhich1;
- _pRanges[1] = nWhich2;
- _pRanges[2] = 0;
-}
-
-/**
- * Constructs an SfxUShortRanges-instance from an sorted ranges of sal_uInt16s,
- * terminates with on 0.
- *
- * Precondition: for each n >= 0 && n < (sizeof(pArr)-1)
- * pArr[2n] <= pArr[2n+1] && ( pArr[2n+2]-pArr[2n+1] ) > 1
- */
-SfxUShortRanges::SfxUShortRanges( const sal_uInt16* pArr )
-{
- DBG_CHECK_RANGES(sal_uInt16, pArr);
- sal_uInt16 nCount = Count_Impl(pArr) + 1;
- _pRanges = new sal_uInt16[ nCount ];
- memcpy( _pRanges, pArr, sizeof(sal_uInt16) * nCount );
-}
-
-
-/**
- * Assigns ranges from 'rRanges' to '*this'.
- */
-SfxUShortRanges& SfxUShortRanges::operator =
-(
- const SfxUShortRanges &rRanges
-)
-{
- // special case: assign itself
- if ( &rRanges == this )
- return *this;
-
- delete[] _pRanges;
-
- // special case: 'rRanges' is empty
- if ( rRanges.IsEmpty() )
- _pRanges = nullptr;
- else
- {
- // copy ranges
- sal_uInt16 nCount = Count_Impl( rRanges._pRanges ) + 1;
- _pRanges = new sal_uInt16[ nCount ];
- memcpy( _pRanges, rRanges._pRanges, sizeof(sal_uInt16) * nCount );
- }
- return *this;
-}
-
-/**
- * Merges *this with 'rRanges'.
- * for each sal_uInt16 n:
- * this->Contains( n ) || rRanges.Contains( n ) => this'->Contains( n )
- * !this->Contains( n ) && !rRanges.Contains( n ) => !this'->Contains( n )
- */
-SfxUShortRanges& SfxUShortRanges::operator +=
-(
- const SfxUShortRanges &rRanges
-)
-{
- // special cases: one is empty
- if ( rRanges.IsEmpty() )
- return *this;
- if ( IsEmpty() )
- return *this = rRanges;
-
- // First, run through _pRanges and rRanges._pRanges and determine the size of
- // the new, merged ranges:
- sal_uInt16 nCount = 0;
- const sal_uInt16 * pRA = _pRanges;
- const sal_uInt16 * pRB = rRanges._pRanges;
-
- for (;;)
- {
- // The first pair of pRA has a lower lower bound than the first pair
- // of pRB:
- if (pRA[0] > pRB[0])
- Swap_Impl(pRA, pRB);
-
- // We are done with the merging if at least pRA is exhausted:
- if (!pRA[0])
- break;
-
- for (;;)
- {
- // Skip those pairs in pRB that completely lie in the first pair
- // of pRA:
- while (pRB[1] <= pRA[1])
- {
- pRB += 2;
-
- // Watch out for exhaustion of pRB:
- if (!pRB[0])
- {
- Swap_Impl(pRA, pRB);
- goto count_rest;
- }
- }
-
- // If the next pair of pRA does not at least touch the current new
- // pair, we are done with the current new pair:
- if (pRB[0] > pRA[1] + 1)
- break;
-
- // The next pair of pRB extends the current new pair; first,
- // extend the current new pair (we are done if pRB is then
- // exhausted); second, switch the roles of pRA and pRB in order to
- // merge in those following pairs of the original pRA that will
- // lie in the (now larger) current new pair or will even extend it
- // further:
- pRA += 2;
- if (!pRA[0])
- goto count_rest;
- Swap_Impl(pRA, pRB);
- }
-
- // Done with the current new pair:
- pRA += 2;
- nCount += 2;
- }
-
- // Only pRB has more pairs available, pRA is already exhausted:
-count_rest:
- for (; pRB[0]; pRB += 2)
- nCount += 2;
-
- // Now, create new ranges of the correct size and, on a second run through
- // _pRanges and rRanges._pRanges, copy the merged pairs into the new
- // ranges:
- sal_uInt16 * pNew = new sal_uInt16[nCount + 1];
- pRA = _pRanges;
- pRB = rRanges._pRanges;
- sal_uInt16 * pRN = pNew;
-
- for (;;)
- {
- // The first pair of pRA has a lower lower bound than the first pair
- // of pRB:
- if (pRA[0] > pRB[0])
- Swap_Impl(pRA, pRB);
-
- // We are done with the merging if at least pRA is exhausted:
- if (!pRA[0])
- break;
-
- // Lower bound of current new pair is already known:
- *pRN++ = pRA[0];
-
- for (;;)
- {
- // Skip those pairs in pRB that completely lie in the first pair
- // of pRA:
- while (pRB[1] <= pRA[1])
- {
- pRB += 2;
-
- // Watch out for exhaustion of pRB:
- if (!pRB[0])
- {
- Swap_Impl(pRA, pRB);
- ++pRB;
- goto copy_rest;
- }
- }
-
- // If the next pair of pRA does not at least touch the current new
- // pair, we are done with the current new pair:
- if (pRB[0] > pRA[1] + 1)
- break;
-
- // The next pair of pRB extends the current new pair; first,
- // extend the current new pair (we are done if pRB is then
- // exhausted); second, switch the roles of pRA and pRB in order to
- // merge in those following pairs of the original pRA that will
- // lie in the (now larger) current new pair or will even extend it
- // further:
- pRA += 2;
- if (!pRA[0])
- {
- ++pRB;
- goto copy_rest;
- }
- Swap_Impl(pRA, pRB);
- }
-
- // Done with the current new pair, now upper bound is also known:
- *pRN++ = pRA[1];
- pRA += 2;
- }
-
- // Only pRB has more pairs available (which are copied to the new ranges
- // unchanged), pRA is already exhausted:
-copy_rest:
- for (; *pRB;)
- *pRN++ = *pRB++;
- *pRN = 0;
-
- delete[] _pRanges;
- _pRanges = pNew;
-
- return *this;
-}
-
/* vim:set shiftwidth=4 softtabstop=4 expandtab: */
More information about the Libreoffice-commits
mailing list