Simplify DecorationList and its clients by using a vector instead of an

intrusive linked list. Restrict clients to a read-only view.

5 files changed, 71 insertions, 88 deletions

diff --git a/src/Decoration.cxx b/src/Decoration.cxx
index 2a6060c52..f5f82832f 100644
--- a/src/Decoration.cxx
+++ b/src/Decoration.cxx
@@ -11,6 +11,7 @@
 #include <cstdarg>
 
 #include <stdexcept>
+#include <vector>
 #include <algorithm>
 #include <memory>
 
@@ -27,7 +28,7 @@
 using namespace Scintilla;
 #endif
 
-Decoration::Decoration(int indicator_) : indicator(indicator_), next(0) {
+Decoration::Decoration(int indicator_) : indicator(indicator_) {
 }
 
 Decoration::~Decoration() {
@@ -37,76 +38,48 @@ bool Decoration::Empty() const {
 	return (rs.Runs() == 1) && (rs.AllSameAs(0));
 }
 
-DecorationList::DecorationList() : currentIndicator(0), currentValue(1), current(0),
-	lengthDocument(0), root(0), clickNotified(false) {
+DecorationList::DecorationList() : currentIndicator(0), currentValue(1), current(nullptr),
+	lengthDocument(0), clickNotified(false) {
 }
 
 DecorationList::~DecorationList() {
-	Decoration *deco = root;
-	while (deco) {
-		Decoration *decoNext = deco->Next();
-		delete deco;
-		deco = decoNext;
-	}
-	root = 0;
-	current = 0;
+	current = nullptr;
 }
 
 Decoration *DecorationList::DecorationFromIndicator(int indicator) {
-	for (Decoration *deco=root; deco; deco = deco->Next()) {
+	for (const std::unique_ptr<Decoration> &deco : decorationList) {
 		if (deco->Indicator() == indicator) {
-			return deco;
+			return deco.get();
 		}
 	}
-	return 0;
+	return nullptr;
 }
 
 Decoration *DecorationList::Create(int indicator, int length) {
 	currentIndicator = indicator;
-	Decoration *decoNew = new Decoration(indicator);
+	std::unique_ptr<Decoration> decoNew(new Decoration(indicator));
 	decoNew->rs.InsertSpace(0, length);
 
-	Decoration *decoPrev = 0;
-	Decoration *deco = root;
+	std::vector<std::unique_ptr<Decoration>>::iterator it = std::lower_bound(
+		decorationList.begin(), decorationList.end(), decoNew, 
+		[](const std::unique_ptr<Decoration> &a, const std::unique_ptr<Decoration> &b) {
+		return a->Indicator() < b->Indicator();
+	});
+	std::vector<std::unique_ptr<Decoration>>::iterator itAdded = 
+		decorationList.insert(it, std::move(decoNew));
 
-	while (deco && (deco->Indicator() < indicator)) {
-		decoPrev = deco;
-		deco = deco->Next();
-	}
-	if (decoPrev == 0) {
-		decoNew->next = root;
-		root = decoNew;
-	} else {
-		decoNew->next = deco;
-		decoPrev->next = decoNew;
-	}
-	return decoNew;
+	SetView();
+
+	return itAdded->get();
 }
 
 void DecorationList::Delete(int indicator) {
-	Decoration *decoToDelete = 0;
-	if (root) {
-		if (root->Indicator() == indicator) {
-			decoToDelete = root;
-			root = root->Next();
-		} else {
-			Decoration *deco = root;
-			while (deco && deco->Next() && !decoToDelete) {
-				// decoNext ensures no warning from MSVC Code Analysis
-				Decoration *decoNext = deco->Next();
-				if (decoNext && deco->Next()->Indicator() == indicator) {
-					decoToDelete = decoNext;
-					deco->next = decoToDelete->Next();
-				} else {
-					deco = deco->Next();
-				}
-			}
-		}
-	}
-	if (decoToDelete) {
-		delete decoToDelete;
-		current = 0;
-	}
+	decorationList.erase(std::remove_if(decorationList.begin(), decorationList.end(),
+		[=](const std::unique_ptr<Decoration> &deco) {
+		return deco->Indicator() == indicator;
+	}), decorationList.end());
+	current = nullptr;
+	SetView();
 }
 
 void DecorationList::SetCurrentIndicator(int indicator) {
@@ -136,7 +109,7 @@ bool DecorationList::FillRange(int &position, int value, int &fillLength) {
 void DecorationList::InsertSpace(int position, int insertLength) {
 	const bool atEnd = position == lengthDocument;
 	lengthDocument += insertLength;
-	for (Decoration *deco=root; deco; deco = deco->Next()) {
+	for (const std::unique_ptr<Decoration> &deco : decorationList) {
 		deco->rs.InsertSpace(position, insertLength);
 		if (atEnd) {
 			deco->rs.FillRange(position, 0, insertLength);
@@ -146,28 +119,47 @@ void DecorationList::InsertSpace(int position, int insertLength) {
 
 void DecorationList::DeleteRange(int position, int deleteLength) {
 	lengthDocument -= deleteLength;
-	Decoration *deco;
-	for (deco=root; deco; deco = deco->Next()) {
+	for (const std::unique_ptr<Decoration> &deco : decorationList) {
 		deco->rs.DeleteRange(position, deleteLength);
 	}
 	DeleteAnyEmpty();
+	if (decorationList.size() != decorationView.size()) {
+		// One or more empty decorations deleted so update view.
+		current = nullptr;
+		SetView();
+	}
+}
+
+void DecorationList::DeleteLexerDecorations() {
+	decorationList.erase(std::remove_if(decorationList.begin(), decorationList.end(),
+		[=](const std::unique_ptr<Decoration> &deco) {
+		return deco->Indicator() < INDIC_CONTAINER;
+	}), decorationList.end());
+	current = nullptr;
+	SetView();
 }
 
 void DecorationList::DeleteAnyEmpty() {
-	Decoration *deco = root;
-	while (deco) {
-		if ((lengthDocument == 0) || deco->Empty()) {
-			Delete(deco->Indicator());
-			deco = root;
-		} else {
-			deco = deco->Next();
-		}
+	if (lengthDocument == 0) {
+		decorationList.clear();
+	} else {
+		decorationList.erase(std::remove_if(decorationList.begin(), decorationList.end(),
+			[=](const std::unique_ptr<Decoration> &deco) {
+			return deco->Empty();
+		}), decorationList.end());
+	}
+}
+
+void DecorationList::SetView() {
+	decorationView.clear();
+	for (const std::unique_ptr<Decoration> &deco : decorationList) {
+		decorationView.push_back(deco.get());
 	}
 }
 
 int DecorationList::AllOnFor(int position) const {
 	int mask = 0;
-	for (Decoration *deco=root; deco; deco = deco->Next()) {
+	for (const std::unique_ptr<Decoration> &deco : decorationList) {
 		if (deco->rs.ValueAt(position)) {
 			if (deco->Indicator() < INDIC_IME) {
 				mask |= 1 << deco->Indicator();
diff --git a/src/Decoration.h b/src/Decoration.h
index 881bd1ff5..d096da385 100644
--- a/src/Decoration.h
+++ b/src/Decoration.h
@@ -14,16 +14,12 @@ namespace Scintilla {
 class Decoration {
 	int indicator;
 public:
-	Decoration *next;
 	RunStyles rs;
 
 	explicit Decoration(int indicator_);
 	~Decoration();
 
 	bool Empty() const;
-	Decoration *Next() const {
-		return next;
-	}
 	int Indicator() const {
 		return indicator;
 	}
@@ -32,22 +28,24 @@ public:
 class DecorationList {
 	int currentIndicator;
 	int currentValue;
-	Decoration *current;
+	Decoration *current;	// Cached so FillRange doesn't have to search for each call.
 	int lengthDocument;
+	// Ordered by indicator
+	std::vector<std::unique_ptr<Decoration>> decorationList;
+	std::vector<const Decoration*> decorationView;	// Read-only view of decorationList
+	bool clickNotified;
+
 	Decoration *DecorationFromIndicator(int indicator);
 	Decoration *Create(int indicator, int length);
 	void Delete(int indicator);
 	void DeleteAnyEmpty();
-	Decoration *root;
-	bool clickNotified;
+	void SetView();
 public:
 
 	DecorationList();
 	~DecorationList();
 
-	Decoration *Root() const {
-		return root;
-	}
+	const std::vector<const Decoration*> &View() const { return decorationView; }
 
 	void SetCurrentIndicator(int indicator);
 	int GetCurrentIndicator() const { return currentIndicator; }
@@ -61,6 +59,8 @@ public:
 	void InsertSpace(int position, int insertLength);
 	void DeleteRange(int position, int deleteLength);
 
+	void DeleteLexerDecorations();
+
 	int AllOnFor(int position) const;
 	int ValueAt(int indicator, int position);
 	int Start(int indicator, int position);
diff --git a/src/EditView.cxx b/src/EditView.cxx
index 2798bb25f..808daa6fa 100644
--- a/src/EditView.cxx
+++ b/src/EditView.cxx
@@ -1041,7 +1041,7 @@ static void DrawIndicators(Surface *surface, const EditModel &model, const ViewS
 	const Sci::Position lineStart = ll->LineStart(subLine);
 	const Sci::Position posLineEnd = posLineStart + lineEnd;
 
-	for (Decoration *deco = model.pdoc->decorations.Root(); deco; deco = deco->Next()) {
+	for (const Decoration *deco : model.pdoc->decorations.View()) {
 		if (under == vsDraw.indicators[deco->Indicator()].under) {
 			Sci::Position startPos = posLineStart + lineStart;
 			if (!deco->rs.ValueAt(startPos)) {
@@ -1658,7 +1658,7 @@ void EditView::DrawForeground(Surface *surface, const EditModel &model, const Vi
 			}
 			if (vsDraw.indicatorsSetFore) {
 				// At least one indicator sets the text colour so see if it applies to this segment
-				for (Decoration *deco = model.pdoc->decorations.Root(); deco; deco = deco->Next()) {
+				for (const Decoration *deco : model.pdoc->decorations.View()) {
 					const int indicatorValue = deco->rs.ValueAt(ts.start + posLineStart);
 					if (indicatorValue) {
 						const Indicator &indicator = vsDraw.indicators[deco->Indicator()];
diff --git a/src/Editor.cxx b/src/Editor.cxx
index 9344b7d94..77443d52f 100644
--- a/src/Editor.cxx
+++ b/src/Editor.cxx
@@ -2097,16 +2097,7 @@ void Editor::ClearAll() {
 }
 
 void Editor::ClearDocumentStyle() {
-	Decoration *deco = pdoc->decorations.Root();
-	while (deco) {
-		// Save next in case deco deleted
-		Decoration *decoNext = deco->Next();
-		if (deco->Indicator() < INDIC_CONTAINER) {
-			pdoc->DecorationSetCurrentIndicator(deco->Indicator());
-			pdoc->DecorationFillRange(0, 0, pdoc->Length());
-		}
-		deco = decoNext;
-	}
+	pdoc->decorations.DeleteLexerDecorations();
 	pdoc->StartStyling(0, '\377');
 	pdoc->SetStyleFor(pdoc->Length(), 0);
 	cs.ShowAll();
@@ -4651,7 +4642,7 @@ void Editor::SetHoverIndicatorPosition(Sci::Position position) {
 	if (!vs.indicatorsDynamic)
 		return;
 	if (position != INVALID_POSITION) {
-		for (Decoration *deco = pdoc->decorations.Root(); deco; deco = deco->Next()) {
+		for (const Decoration *deco : pdoc->decorations.View()) {
 			if (vs.indicators[deco->Indicator()].IsDynamic()) {
 				if (pdoc->decorations.ValueAt(deco->Indicator(), position)) {
 					hoverIndicatorPos = position;
diff --git a/src/PositionCache.cxx b/src/PositionCache.cxx
index b6e6c375c..2099046b8 100644
--- a/src/PositionCache.cxx
+++ b/src/PositionCache.cxx
@@ -470,7 +470,7 @@ BreakFinder::BreakFinder(const LineLayout *ll_, const Selection *psel, Range lin
 		}
 	}
 	if (pvsDraw && pvsDraw->indicatorsSetFore) {
-		for (Decoration *deco = pdoc->decorations.Root(); deco; deco = deco->Next()) {
+		for (const Decoration *deco : pdoc->decorations.View()) {
 			if (pvsDraw->indicators[deco->Indicator()].OverridesTextFore()) {
 				Sci::Position startPos = deco->rs.EndRun(posLineStart);
 				while (startPos < (posLineStart + lineRange.end)) {