From 710efe5438a585b071085fc7d7ea14aebd8328fd Mon Sep 17 00:00:00 2001
From: Mikko Rasa <tdb@tdb.fi>
Date: Mon, 19 Aug 2013 19:06:42 +0300
Subject: [PATCH] Improve block recreation algorithms

These changes result in a more than 100% performance improvement in
operations that create and delete a lot of tracks, such as the extend
tool.
---
 source/libr2c2/layout.cpp | 29 +++++++++++++++++------------
 source/libr2c2/track.cpp  | 11 ++++++++---
 2 files changed, 25 insertions(+), 15 deletions(-)

diff --git a/source/libr2c2/layout.cpp b/source/libr2c2/layout.cpp
index b847637..f318958 100644
--- a/source/libr2c2/layout.cpp
+++ b/source/libr2c2/layout.cpp
@@ -255,26 +255,31 @@ Block &Layout::get_block(unsigned id) const
 
 void Layout::create_blocks()
 {
-	set<Track *> used_tracks;
+	set<Track *> loose_tracks = objects.get<Track>();
 	const set<Block *> *blocks = &track_chains.get<Block>();
 	for(set<Block *>::const_iterator i=blocks->begin(); i!=blocks->end(); ++i)
 	{
 		const set<Track *> &btracks = (*i)->get_tracks();
-		used_tracks.insert(btracks.begin(), btracks.end());
+		for(set<Track *>::const_iterator j=btracks.begin(); j!=btracks.end(); ++j)
+			loose_tracks.erase(*j);
 	}
 
-	const set<Track *> &tracks = objects.get<Track>();
-	for(set<Track *>::const_iterator i=tracks.begin(); i!=tracks.end(); ++i)
-		if(used_tracks.count(*i)==0)
-		{
-			Block *block = new Block(*this, **i);
-			used_tracks.insert(block->get_tracks().begin(), block->get_tracks().end());
-		}
+	list<Block *> created_blocks;
+	while(!loose_tracks.empty())
+	{
+		Block *block = new Block(*this, **loose_tracks.begin());
+		created_blocks.push_back(block);
+
+		const set<Track *> &btracks = block->get_tracks();
+		for(set<Track *>::const_iterator i=btracks.begin(); i!=btracks.end(); ++i)
+			loose_tracks.erase(*i);
+	}
 
+	// The previously obtained set has been invalidated by creating new blocks
 	blocks = &track_chains.get<Block>();
-	for(set<Block *>::iterator i=blocks->begin(); i!=blocks->end(); ++i)
-		for(set<Block *>::iterator j=i; j!=blocks->end(); ++j)
-			if(j!=i)
+	for(list<Block *>::iterator i=created_blocks.begin(); i!=created_blocks.end(); ++i)
+		for(set<Block *>::const_iterator j=blocks->begin(); j!=blocks->end(); ++j)
+			if(*j!=*i)
 				(*i)->check_link(**j);
 }
 
diff --git a/source/libr2c2/track.cpp b/source/libr2c2/track.cpp
index 4708db5..7a17467 100644
--- a/source/libr2c2/track.cpp
+++ b/source/libr2c2/track.cpp
@@ -344,9 +344,14 @@ bool Track::break_link(unsigned i)
 		return false;
 
 	links[i] = 0;
-	other->break_link(*this);
-	// XXX Creates the blocks twice, because the other track calls this too
-	layout.create_blocks(*this);
+	if(!other->break_link(*this))
+	{
+		/* If the call doesn't succeed, it means that the other track already
+		broke the link and is calling us right now.  Recreate blocks in the inner
+		call so it occurs before any signals are emitted. */
+		layout.create_blocks(*this);
+	}
+
 	signal_link_changed.emit(i, 0);
 
 	return true;
-- 
2.45.2