Better line cache. Without a tempo change occurring, lines are never moved (except to 'steal' from outside the visible range).

Scrolling left now gets perfect cache hits as well as scrolling right, and steals minimally from the right.


git-svn-id: svn://localhost/ardour2/branches/3.0@3800 d708f5d6-7413-0410-9779-e7cbd77b26cf

1 files changed, 97 insertions, 41 deletions

diff --git a/gtk2_ardour/tempo_lines.cc b/gtk2_ardour/tempo_lines.cc
index ed54708cc6..5b73c877ac 100644
--- a/gtk2_ardour/tempo_lines.cc
+++ b/gtk2_ardour/tempo_lines.cc
@@ -40,14 +40,15 @@ TempoLines::tempo_map_changed()
 	_clean_left = DBL_MAX;
 	_clean_right = 0.0;
 
+	size_t d = 0;
 	// TODO: Dirty/slow, but 'needed' for zoom :(
-	for (Lines::iterator i = _lines.begin(); i != _lines.end(); ) {
+	for (Lines::iterator i = _lines.begin(); i != _lines.end(); ++d) {
 		Lines::iterator next = i;
 		++next;
-      	i->second->property_x1() = DBL_MAX;
-      	i->second->property_x2() = DBL_MAX;
+      	i->second->property_x1() = DBL_MAX - d;
+      	i->second->property_x2() = DBL_MAX - d;
 		_lines.erase(i);
-		_lines.insert(make_pair(DBL_MAX, i->second));
+		_lines.insert(make_pair(DBL_MAX - d, i->second));
 		i = next;
 	}
 }
@@ -72,7 +73,7 @@ void
 TempoLines::draw (ARDOUR::TempoMap::BBTPointList& points, double frames_per_unit)
 {
 	ARDOUR::TempoMap::BBTPointList::iterator i;
-	ArdourCanvas::SimpleLine *line;
+	ArdourCanvas::SimpleLine *line = NULL;
 	gdouble xpos;
 	double who_cares;
 	double x1, x2, y1, y2, beat_density;
@@ -112,17 +113,19 @@ TempoLines::draw (ARDOUR::TempoMap::BBTPointList& points, double frames_per_unit
 
 	bool exhausted = (left == _lines.end());
 	Lines::iterator li = left;
+	if (li != _lines.end())
+		line = li->second;
 	
 	// Tempo map hasn't changed and we're entirely within a clean
 	// range, don't need to do anything.  Yay.
 	if (needed_left >= _clean_left && needed_right <= _clean_right) {
-		//cout << "LINE CACHE PERFECT HIT!" << endl;
+		//cout << endl << "*** LINE CACHE PERFECT HIT" << endl;
 		return;
 	}
 
-	//cout << "LINE CACHE MISS :/" << endl;
+	//cout << endl << "*** LINE CACHE MISS" << endl;
 
-	bool inserted_last_time = false;
+	bool inserted_last_time = true;
 	bool invalidated = false;
 	
 	for (i = points.begin(); i != points.end(); ++i) {
@@ -132,29 +135,88 @@ TempoLines::draw (ARDOUR::TempoMap::BBTPointList& points, double frames_per_unit
 			break;
 
 		case ARDOUR::TempoMap::Beat:
-			
 			if ((*i).beat == 1) {
 				color = ARDOUR_UI::config()->canvasvar_MeasureLineBar.get();
 			} else {
 				color = ARDOUR_UI::config()->canvasvar_MeasureLineBeat.get();
-
 				if (beat_density > 2.0) {
-					/* only draw beat lines if the gaps between beats are large. */
-					break;
+					break; /* only draw beat lines if the gaps between beats are large. */
 				}
 			}
 			
 			xpos = rint(((nframes64_t)(*i).frame) / (double)frames_per_unit);
 
-			if (inserted_last_time) {
+			if (inserted_last_time && !_lines.empty()) {
 				li = _lines.lower_bound(xpos); // first line >= xpos
 			}
+				
+			line = (li != _lines.end()) ? li->second : NULL;
+			assert(!line || line->property_x1() == li->first);
+				
+			Lines::iterator next = li;
+			if (next != _lines.end())
+				++next;
+
+			exhausted = (next == _lines.end());
 			
-			if (!exhausted) {
-				line = li->second;
-				exhausted = ((++li) == _lines.end());
-				inserted_last_time = false;
+			// Hooray, line is perfect			
+			if (line && line->property_x1() == xpos) {
+				if (li != _lines.end())
+					++li;
+
+				line->property_color_rgba() = color;
+				inserted_last_time = false; // don't search next time
+
+			// Use existing line, moving if necessary
+			} else if (!exhausted) {
+				Lines::iterator steal = _lines.end();
+				--steal;
+				
+				// Steal from the right
+				if (left->first > needed_left && li != steal && steal->first > needed_right) {
+					//cout << "*** STEALING FROM RIGHT" << endl;
+					line = steal->second;
+					_lines.erase(steal);
+					line->property_x1() = xpos;
+					line->property_x2() = xpos;
+					line->property_color_rgba() = color;
+					_lines.insert(make_pair(xpos, line));
+					inserted_last_time = true; // search next time
+					invalidated = true;
+
+					// Shift clean range left
+					_clean_left = min(_clean_left, xpos);
+					_clean_right = min(_clean_right, steal->first);
+
+				// Move this line to where we need it
+				} else {
+					Lines::iterator existing = _lines.find(xpos);
+					if (existing != _lines.end()) {
+						//cout << "*** EXISTING LINE" << endl;
+						li = existing;
+						li->second->property_color_rgba() = color;
+						inserted_last_time = false; // don't search next time
+					} else {
+						//cout << "*** MOVING LINE" << endl;
+						const double x1 = line->property_x1();
+						const bool was_clean = x1 >= _clean_left && x1 <= _clean_right;
+						invalidated = invalidated || was_clean;
+						// Invalidate clean portion (XXX: too harsh?)
+						_clean_left  = needed_left;
+						_clean_right = needed_right;
+						_lines.erase(li);
+						line->property_color_rgba() = color;
+						line->property_x1() = xpos;
+						line->property_x2() = xpos;
+						_lines.insert(make_pair(xpos, line));
+						inserted_last_time = true; // search next time
+					}
+				}
+
+			// Create a new line
 			} else if (_lines.size() < needed || _lines.size() < MAX_CACHED_LINES) {
+				//cout << "*** CREATING LINE" << endl;
+				assert(_lines.find(xpos) == _lines.end());
 				line = new ArdourCanvas::SimpleLine (*_group);
 				line->property_x1() = xpos;
 				line->property_x2() = xpos;
@@ -162,38 +224,32 @@ TempoLines::draw (ARDOUR::TempoMap::BBTPointList& points, double frames_per_unit
 				line->property_color_rgba() = color;
 				_lines.insert(make_pair(xpos, line));
 				inserted_last_time = true;
-			} else {
-				assert(li != _lines.begin());
-				line = _lines.begin()->second; // steal leftmost line
-				_lines.erase(_lines.begin());
-				_lines.insert(make_pair(xpos, line));
-				inserted_last_time = true;
-				invalidated = true;
-			}
 
-			/* At this point, line's key is correct, but actual pos may not be */
-			if (line->property_x1() != xpos) {
-				// Turn this on to see the case where this isn't quite ideal yet
-				// (scrolling left, lots of lines are moved left when there is
-				// likely to be a huge chunk with equivalent coords)
-				//cout << "MOVE " << line->property_x1() << " -> " << xpos << endl;
-				double x1 = line->property_x1();
-				bool was_clean = x1 >= _clean_left && x1 <= _clean_right;
-				invalidated = invalidated || was_clean;
+			// Steal from the left
+			} else {
+				//cout << "*** STEALING FROM LEFT" << endl;
+				assert(_lines.find(xpos) == _lines.end());
+				Lines::iterator steal = _lines.begin();
+				line = steal->second;
+				_lines.erase(steal);
+				line->property_color_rgba() = color;
 				line->property_x1() = xpos;
 				line->property_x2() = xpos;
-				line->property_y2() = y2;
-				line->property_color_rgba() = color;
+				_lines.insert(make_pair(xpos, line));
+				inserted_last_time = true; // search next time
+				invalidated = true;
+				
+				// Shift clean range right
+				_clean_left = max(_clean_left, steal->first);
+				_clean_right = max(_clean_right, xpos);
 			}
 
 			break;
 		}
 	}
-	
-	if (invalidated) { // We messed things up, visible range is all we know is valid
-		_clean_left  = needed_left;
-		_clean_right = needed_right;
-	} else { // Extend range to what we've 'fixed'
+
+	// Extend range to what we've 'fixed'
+	if (!invalidated) {
 		_clean_left  = min(_clean_left, needed_left);
 		_clean_right = max(_clean_right, needed_right);
 	}