KDE/kdelibs
David Nolden
david.nolden.kde at art-master.de
Mon Oct 6 23:51:35 UTC 2008
SVN commit 868736 by zwabel:
- Speed up the child-handling of smart-ranges by using a binary search in the sorted child-list wherever possible, instead of iterating over all children.
- Use binary search in the renderer to find the next boundary.
This makes the whole smart-range stuff scale up a lot better up when there is many of them. On my machine this speeds up the rendering in KDevelop-4 by magnitudes, finally it feels nearly like in KDE3.
CCMAIL: rodda at kde.org
CCMAIL: kdevelop-devel at barney.cs.uni-potsdam.de
M +132 -67 interfaces/ktexteditor/smartrange.cpp
M +38 -3 kate/render/katerenderrange.cpp
--- trunk/KDE/kdelibs/interfaces/ktexteditor/smartrange.cpp #868735:868736
@@ -1,5 +1,6 @@
/* This file is part of the KDE libraries
Copyright (C) 2003-2005 Hamish Rodda <rodda at kde.org>
+ Copyright (C) 2008 David Nolden <david.nolden.kdevelop at art-master.de>
This library is free software; you can redistribute it and/or
modify it under the terms of the GNU Library General Public
@@ -30,6 +31,80 @@
using namespace KTextEditor;
+// #define DEBUG_BINARY_SEARCH
+
+///Returns the first index of a range that contains @param pos, or the index of the first range that is behind pos(or ranges.count() if pos is behind all ranges)
+///The list must be sorted by the ranges end-positions.
+static int lowerBound(const QList<SmartRange*>& ranges, const Cursor& pos)
+{
+ int begin = 0;
+ int n = ranges.count();
+
+ int half;
+ int middle;
+
+ while (n > 0) {
+ half = n >> 1;
+ middle = begin + half;
+ if(ranges[middle]->end() > pos) {
+ n = half;
+ }else{
+ begin = middle + 1;
+ n -= half + 1;
+ }
+ }
+ return begin;
+}
+
+///Searches for the given range, or a lower bound for the given position.
+static int lowerBoundRange(const QList<SmartRange*>& ranges, const Cursor& pos, const SmartRange* range)
+{
+ int begin = 0;
+ int n = ranges.count();
+
+ int half;
+ int middle;
+
+ while (n > 0) {
+ half = n >> 1;
+ middle = begin + half;
+ if(ranges[begin] == range)
+ return begin;
+ if(ranges[middle] == range)
+ return middle;
+
+ if(ranges[middle]->end() > pos) {
+ n = half;
+ }else{
+ begin = middle + 1;
+ n -= half + 1;
+ }
+ }
+ return begin;
+}
+
+///Finds the index of the given SmartRange in the sorted list using binary search. Uses @param range For searching, and @param smartRange for equality comparison.
+static int findIndex(const QList<SmartRange*>& ranges, const SmartRange* smartRange, const Range* range) {
+ int index = lowerBoundRange(ranges, range->start(), smartRange);
+ int childCount = ranges.count();
+
+ //In case of degenerated ranges, we may have found the wrong index.
+ while(index < childCount && ranges[index] != smartRange)
+ ++index;
+
+ if(index == childCount) {
+ //During rangeChanged the order may temporarily be inconsistent, so we use indexOf as fallback
+ return ranges.indexOf(const_cast<SmartRange*>(smartRange));
+/* if(smartRange != range) //Try again finding the range, using the smart-range only
+ return findIndex(ranges, smartRange, smartRange);*/
+
+// Q_ASSERT(ranges.indexOf(const_cast<SmartRange*>(smartRange)) == -1);
+ return -1;
+ }
+
+ return index;
+}
+
SmartRange::SmartRange(SmartCursor* start, SmartCursor* end, SmartRange * parent, InsertBehaviors insertBehavior )
: Range(start, end)
, m_attribute(0L)
@@ -102,15 +177,17 @@
SmartRange * SmartRange::childBefore( const SmartRange * range ) const
{
- int index = m_childRanges.indexOf(const_cast<SmartRange*>(range));
+ int index = findIndex(m_childRanges, range, range);
+
if (--index >= 0)
return m_childRanges[index];
+
return 0L;
}
SmartRange * SmartRange::childAfter( const SmartRange * range ) const
{
- int index = m_childRanges.indexOf(const_cast<SmartRange*>(range));
+ int index = findIndex(m_childRanges, range, range);
if (index != -1 && ++index < m_childRanges.count())
return m_childRanges[index];
return 0L;
@@ -124,41 +201,45 @@
// A new child has been added, so expand this range if required.
expandToRange(*newChild);
+ #ifdef DEBUG_BINARY_SEARCH
+ {
+ KTextEditor::Cursor lastEnd = KTextEditor::Cursor(-1,-1);
+ for(int a = 0; a < m_childRanges.size(); ++a) {
+ Q_ASSERT(m_childRanges[a]->end() >= lastEnd);
+ lastEnd = m_childRanges[a]->end();
+ }
+ }
+ #endif
- QMutableListIterator<SmartRange*> it = m_childRanges;
- it.toBack();
-
- bool done = false;
- while (it.hasPrevious()) {
- if (it.peekPrevious()->end() <= newChild->start()) {
- it.insert(newChild);
- if (it.hasNext() && it.peekNext()->start() < newChild->end())
- {
- Range oldRange = *it.peekNext();
- //Give a warning here, because this most probably results in unwanted behavior, and is extremely hard to debug. This at least gives a clue what'is going wrong. The alternative would be an assertion.
- it.peekNext()->start() = newChild->end();
-
- kDebug() << "SmartRange warning: " << this << ": Added child-range " << newChild << "(" << *newChild << ") intersects child-range " << it.peekNext() << "(" << oldRange << "), the second one is trimmed to " << *it.peekNext() << endl;
+ int insertAt = lowerBound(m_childRanges, newChild->start());
+ if(insertAt != m_childRanges.size()) {
+ if(m_childRanges[insertAt]->start() < newChild->end()) {
+ //Give a warning here, because this most probably results in unwanted behavior, and is extremely hard to debug. This at least gives a clue what'is going wrong. The alternative would be an assertion.
+ kDebug() << "SmartRange warning: " << this << ": Added child-range " << newChild << "(" << *newChild << ") intersects child-range " << m_childRanges[insertAt] << "(" << *m_childRanges[insertAt] << "), the old one is trimmed." << endl;
+ m_childRanges[insertAt]->start() = newChild->end(); //Smartrange logic will trim all the other ranges out of the way
+ if(m_childRanges[insertAt]->start() != newChild->end()) {
+ m_childRanges[insertAt]->start() = newChild->end();
+ Q_ASSERT(m_childRanges[insertAt]->start() == newChild->end());
}
-
- done = true;
- break;
+ for(int a = insertAt; a < m_childRanges.size(); ++a) {
+ Q_ASSERT(m_childRanges[a]->start() >= newChild->end());
+ }
}
-
- it.previous();
}
-
- if (!done) {
- if (m_childRanges.count() && m_childRanges.first()->start() < newChild->end())
- {
- Range oldRange = *m_childRanges.first();
-
- m_childRanges.first()->start() = newChild->end();
-
- kDebug() << "SmartRange warning: " << this << ": Added child-range " << newChild << "(" << *newChild << ") intersects child-range " << m_childRanges.first() << "(" << oldRange << "), the second one is trimmed to " << *m_childRanges.first() << endl;
- }
- m_childRanges.prepend(newChild);
+ m_childRanges.insert(insertAt, newChild);
+
+ #ifdef DEBUG_BINARY_SEARCH
+ {
+ KTextEditor::Cursor lastEnd = KTextEditor::Cursor(-1,-1);
+ for(int a = 0; a < m_childRanges.size(); ++a) {
+ Q_ASSERT(m_childRanges[a]->end() >= lastEnd);
+ lastEnd = m_childRanges[a]->end();
}
+ }
+ #endif
+
+ QMutableListIterator<SmartRange*> it = m_childRanges;
+ it.toBack();
foreach (SmartRangeNotifier* n, m_notifiers)
emit n->childRangeInserted(this, newChild);
@@ -169,7 +250,7 @@
void SmartRange::removeChildRange(SmartRange* child)
{
- int index = m_childRanges.lastIndexOf(child);
+ int index = findIndex(m_childRanges, child, child);
if (index != -1) {
m_childRanges.removeAt(index);
@@ -187,9 +268,13 @@
return 0L;
if (contains(input)) {
- foreach (SmartRange* r, m_childRanges)
- if (r->contains(input))
+ int child = lowerBound(m_childRanges, input.start());
+
+ if(child != m_childRanges.size()) {
+ SmartRange* r = m_childRanges[child];
+ if(r->contains(input))
return r->mostSpecificRange(input);
+ }
return const_cast<SmartRange*>(this);
@@ -243,14 +328,13 @@
if (!first && rangesEntered)
rangesEntered->push(const_cast<SmartRange*>(this));
- foreach (SmartRange* r, m_childRanges) {
- int result = r->positionRelativeToCursor(pos);
- if (result == 0)
+ int child = lowerBound(m_childRanges, pos);
+ if(child != m_childRanges.size()) {
+ SmartRange* r = m_childRanges[child];
+ if(r->contains(pos))
return r->deepestRangeContainingInternal(pos, rangesEntered, rangesExited);
- else if (result == 1)
- break;
}
-
+
return const_cast<SmartRange*>(this);
} else {
@@ -416,33 +500,14 @@
}
// Contract child ranges if required
- if (childRanges().count()) {
- SmartRange* r;
- QList<SmartRange*>::ConstIterator it;
+ if(!m_childRanges.isEmpty()) {
+ if (start() > from.start())
+ if(m_childRanges.front()->start() < start())
+ m_childRanges.front()->start() = start(); //Adjust the first child-range, all the other ones will be changed automatically using this mechanism
- int i = 0;
- if (start() > from.start()) {
- // Start has contracted - adjust from the start of the child ranges
- for (; i < childRanges().count(); ++i) {
- r = childRanges().at(i);
- if (r->start() < start())
- r->confineToRange(*this);
- else
- break;
- }
- }
-
- if (end() < from.end()) {
- // end has contracted - adjust from the start of the child ranges, if they
- // haven't already been adjusted above
- for (int j = childRanges().count() - 1; j >= i; --j) {
- r = childRanges().at(j);
- if (r->end() > end())
- r->confineToRange(*this);
- else
- break;
- }
- }
+ if (end() < from.end())
+ if(m_childRanges.back()->end() > end())
+ m_childRanges.back()->end() = end(); //Adjust the last child-range only, all the other ones will be changed automatically using this mechanism
}
// SmartCursor and its subclasses take care of adjusting ranges if the tree
--- trunk/KDE/kdelibs/kate/render/katerenderrange.cpp #868735:868736
@@ -24,6 +24,29 @@
#include "katesmartrange.h"
#include "katedynamicanimation.h"
+///Returns the first index of a range that contains @param pos, or the index of the first range that is behind pos(or ranges.count() if pos is behind all ranges)
+///The list must be sorted by the ranges end-positions.
+static int lowerBound(const QList<KTextEditor::SmartRange*>& ranges, const KTextEditor::Cursor& pos)
+{
+ int begin = 0;
+ int n = ranges.count();
+
+ int half;
+ int middle;
+
+ while (n > 0) {
+ half = n >> 1;
+ middle = begin + half;
+ if(ranges[middle]->end() > pos) {
+ n = half;
+ }else{
+ begin = middle + 1;
+ n -= half + 1;
+ }
+ }
+ return begin;
+}
+
SmartRenderRange::SmartRenderRange(KateSmartRange* range, bool useDynamic, KateView* view)
: m_currentRange(0L)
, m_view(view)
@@ -36,6 +59,8 @@
}
}
+#define USE_BINARY_BOUNDARY_SEARCH
+
KTextEditor::Cursor SmartRenderRange::nextBoundary() const
{
if (!m_currentRange)
@@ -50,10 +75,20 @@
return KTextEditor::Cursor(INT_MAX, INT_MAX);
}
- foreach (KTextEditor::SmartRange* child, r->childRanges()) {
- if (child->start() > m_currentPos)
- return child->start();
+#ifdef USE_BINARY_BOUNDARY_SEARCH
+ int nextChild = lowerBound(r->childRanges(), m_currentPos);
+ while(nextChild != r->childRanges().size() && r->childRanges()[nextChild]->start() <= m_currentPos)
+ ++nextChild;
+
+ if(nextChild != r->childRanges().size() && r->childRanges()[nextChild]->start() > m_currentPos)
+ return r->childRanges()[nextChild]->start();
+#else
+ foreach(KTextEditor::SmartRange* child, r->childRanges()) {
+ if(child->start() > m_currentPos)
+ return child->start();
}
+#endif
+
return m_currentRange->end();
}
More information about the KDevelop-devel
mailing list