Merge branch 'wme_lineartickets' into wme_rendering

This replaces the (quadratic time) renderqueue drawnum logic by a
(linear time) approach based on following along the queue with an iterator.

This branch first implements the new iterator logic next to the old drawnum
logic, adding asserts that they produce identical results to facilitate testing
and debugging. The old code is removed after that.

4 files changed, 50 insertions, 66 deletions

diff --git a/engines/wintermute/base/gfx/osystem/base_render_osystem.cpp b/engines/wintermute/base/gfx/osystem/base_render_osystem.cpp
index 96bc3186b6..37f577d202 100644
--- a/engines/wintermute/base/gfx/osystem/base_render_osystem.cpp
+++ b/engines/wintermute/base/gfx/osystem/base_render_osystem.cpp
@@ -52,6 +52,7 @@ BaseRenderOSystem::BaseRenderOSystem(BaseGame *inGame) : BaseRenderer(inGame) {
 	_renderSurface = new Graphics::Surface();
 	_blankSurface = new Graphics::Surface();
 	_drawNum = 1;
+	_lastFrameIter = _renderQueue.end();
 	_needsFlip = true;
 	_skipThisFrame = false;
 	_previousTicket = nullptr;
@@ -159,6 +160,7 @@ bool BaseRenderOSystem::flip() {
 		g_system->updateScreen();
 		_needsFlip = false;
 		_drawNum = 1;
+		_lastFrameIter = _renderQueue.end();
 		addDirtyRect(_renderRect);
 		return true;
 	}
@@ -189,6 +191,7 @@ bool BaseRenderOSystem::flip() {
 		_needsFlip = false;
 	}
 	_drawNum = 1;
+	_lastFrameIter = _renderQueue.end();
 
 	return STATUS_OK;
 }
@@ -292,7 +295,7 @@ void BaseRenderOSystem::drawSurface(BaseSurfaceOSystem *owner, const Graphics::S
 				if (_disableDirtyRects) {
 					drawFromSurface(compareTicket);
 				} else {
-					drawFromTicket(compareTicket);
+					drawFromQueuedTicket(it);
 					_previousTicket = compareTicket;
 				}
 				return;
@@ -370,59 +373,40 @@ void BaseRenderOSystem::invalidateTicketsFromSurface(BaseSurfaceOSystem *surf) {
 
 void BaseRenderOSystem::drawFromTicket(RenderTicket *renderTicket) {
 	renderTicket->_wantsDraw = true;
-	// A new item always has _drawNum == 0
-	if (renderTicket->_drawNum == 0) {
-		// In-order
-		if (_renderQueue.empty() || _drawNum > (_renderQueue.back())->_drawNum) {
-			renderTicket->_drawNum = _drawNum++;
-			_renderQueue.push_back(renderTicket);
-			addDirtyRect(renderTicket->_dstRect);
-			++_lastAddedTicket;
-		} else {
-			// Before something
-			RenderQueueIterator pos;
-			for (pos = _renderQueue.begin(); pos != _renderQueue.end(); pos++) {
-				if ((*pos)->_drawNum >= _drawNum) {
-					break;
-				}
-			}
-			_renderQueue.insert(pos, renderTicket);
-			renderTicket->_drawNum = _drawNum++;
-			// Increment the following tickets, so they still are in line
-			RenderQueueIterator it;
-			for (it = pos; it != _renderQueue.end(); ++it) {
-				(*it)->_drawNum++;
-				(*it)->_wantsDraw = false;
-			}
-			addDirtyRect(renderTicket->_dstRect);
-			_lastAddedTicket = pos;
-		}
+
+	++_lastFrameIter;
+	// In-order
+	if (_renderQueue.empty() || _lastFrameIter == _renderQueue.end()) {
+		_lastFrameIter--;
+		_renderQueue.push_back(renderTicket);
+		++_lastFrameIter;
+		addDirtyRect(renderTicket->_dstRect);
+		++_lastAddedTicket;
 	} else {
-		// Was drawn last round, still in the same order
-		if (_drawNum == renderTicket->_drawNum) {
-			_drawNum++;
-			++_lastAddedTicket;
-		} else {
-			// Remove the ticket from the list
-			RenderQueueIterator it = _renderQueue.begin();
-			while (it != _renderQueue.end()) {
-				if ((*it) == renderTicket) {
-					it = _renderQueue.erase(it);
-					break;
-				} else {
-					++it;
-				}
-			}
-			if (it != _renderQueue.end()) {
-				// Decreement the following tickets.
-				for (; it != _renderQueue.end(); ++it) {
-					(*it)->_drawNum--;
-				}
-			}
-			// Is not in order, so readd it as if it was a new ticket
-			renderTicket->_drawNum = 0;
-			drawFromTicket(renderTicket);
-		}
+		// Before something
+		RenderQueueIterator pos = _lastFrameIter;
+		_renderQueue.insert(pos, renderTicket);
+		--_lastFrameIter;
+		addDirtyRect(renderTicket->_dstRect);
+		_lastAddedTicket = pos;
+	}
+}
+
+void BaseRenderOSystem::drawFromQueuedTicket(const RenderQueueIterator &ticket) {
+	RenderTicket *renderTicket = *ticket;
+	renderTicket->_wantsDraw = true;
+
+	++_lastFrameIter;
+	// Was drawn last round, still in the same order
+	if (*_lastFrameIter == renderTicket) {
+		_drawNum++;
+		++_lastAddedTicket;
+	} else {
+		--_lastFrameIter;
+		// Remove the ticket from the list
+		_renderQueue.erase(ticket);
+		// Is not in order, so readd it as if it was a new ticket
+		drawFromTicket(renderTicket);
 	}
 }
 
@@ -441,16 +425,13 @@ void BaseRenderOSystem::drawTickets() {
 	// Note: We draw invalid tickets too, otherwise we wouldn't be honouring
 	// the draw request they obviously made BEFORE becoming invalid, either way
 	// we have a copy of their data, so their invalidness won't affect us.
-	uint32 decrement = 0;
 	while (it != _renderQueue.end()) {
 		if ((*it)->_wantsDraw == false) {
 			RenderTicket *ticket = *it;
 			addDirtyRect((*it)->_dstRect);
 			it = _renderQueue.erase(it);
 			delete ticket;
-			decrement++;
 		} else {
-			(*it)->_drawNum -= decrement;
 			++it;
 		}
 	}
@@ -470,9 +451,9 @@ void BaseRenderOSystem::drawTickets() {
 	// Apply the clear-color to the dirty rect.
 	_renderSurface->fillRect(*_dirtyRect, _clearColor);
 	_drawNum = 1;
+	_lastFrameIter = _renderQueue.end();
 	for (it = _renderQueue.begin(); it != _renderQueue.end(); ++it) {
 		RenderTicket *ticket = *it;
-		assert(ticket->_drawNum == _drawNum);
 		++_drawNum;
 		if (ticket->_dstRect.intersects(*_dirtyRect)) {
 			// dstClip is the area we want redrawn.
@@ -500,16 +481,13 @@ void BaseRenderOSystem::drawTickets() {
 
 	it = _renderQueue.begin();
 	// Clean out the old tickets
-	decrement = 0;
 	while (it != _renderQueue.end()) {
 		if ((*it)->_isValid == false) {
 			RenderTicket *ticket = *it;
 			addDirtyRect((*it)->_dstRect);
 			it = _renderQueue.erase(it);
 			delete ticket;
-			decrement++;
 		} else {
-			(*it)->_drawNum -= decrement;
 			++it;
 		}
 	}
@@ -641,6 +619,7 @@ void BaseRenderOSystem::endSaveLoad() {
 	// so just skip this single frame.
 	_skipThisFrame = true;
 	_drawNum = 1;
+	_lastFrameIter = _renderQueue.end();
 
 	_renderSurface->fillRect(Common::Rect(0, 0, _renderSurface->h, _renderSurface->w), _renderSurface->format.ARGBToColor(255, 0, 0, 0));
 	g_system->copyRectToScreen((byte *)_renderSurface->getPixels(), _renderSurface->pitch, 0, 0, _renderSurface->w, _renderSurface->h);
diff --git a/engines/wintermute/base/gfx/osystem/base_render_osystem.h b/engines/wintermute/base/gfx/osystem/base_render_osystem.h
index dd3cc6140e..fd5d33622e 100644
--- a/engines/wintermute/base/gfx/osystem/base_render_osystem.h
+++ b/engines/wintermute/base/gfx/osystem/base_render_osystem.h
@@ -62,6 +62,8 @@ public:
 	BaseRenderOSystem(BaseGame *inGame);
 	~BaseRenderOSystem();
 
+	typedef Common::List<RenderTicket *>::iterator RenderQueueIterator;
+
 	Common::String getName() const;
 
 	bool initRenderer(int width, int height, bool windowed) override;
@@ -79,11 +81,16 @@ public:
 	void invalidateTicket(RenderTicket *renderTicket);
 	void invalidateTicketsFromSurface(BaseSurfaceOSystem *surf);
 	/**
-	 * Insert a ticket into the queue, adding a dirty rect if it's
-	 * new, or out-of-order from last draw from the ticket.
+	 * Insert a new ticket into the queue, adding a dirty rect
 	 * param renderTicket the ticket to be added.
 	 */
 	void drawFromTicket(RenderTicket *renderTicket);
+	/**
+	 * Re-insert an existing ticket into the queue, adding a dirty rect
+	 * out-of-order from last draw from the ticket.
+	 * param ticket iterator pointing to the ticket to be added.
+	 */
+	void drawFromQueuedTicket(const RenderQueueIterator &ticket);
 
 	bool setViewport(int left, int top, int right, int bottom) override;
 	bool setViewport(Rect32 *rect) override { return BaseRenderer::setViewport(rect); }
@@ -120,7 +127,6 @@ private:
 	void drawFromSurface(RenderTicket *ticket);
 	// Dirty-rects:
 	void drawFromSurface(RenderTicket *ticket, Common::Rect *dstRect, Common::Rect *clipRect);
-	typedef Common::List<RenderTicket *>::iterator RenderQueueIterator;
 	Common::Rect *_dirtyRect;
 	Common::List<RenderTicket *> _renderQueue;
 	RenderQueueIterator _lastAddedTicket;
@@ -128,6 +134,7 @@ private:
 
 	bool _needsFlip;
 	uint32 _drawNum; ///< The global number of the current draw-operation.
+	RenderQueueIterator _lastFrameIter;
 	Common::Rect _renderRect;
 	Graphics::Surface *_renderSurface;
 	Graphics::Surface *_blankSurface;
diff --git a/engines/wintermute/base/gfx/osystem/render_ticket.cpp b/engines/wintermute/base/gfx/osystem/render_ticket.cpp
index ad193bcf60..006dd77e18 100644
--- a/engines/wintermute/base/gfx/osystem/render_ticket.cpp
+++ b/engines/wintermute/base/gfx/osystem/render_ticket.cpp
@@ -38,7 +38,6 @@ RenderTicket::RenderTicket(BaseSurfaceOSystem *owner, const Graphics::Surface *s
 	_owner(owner),
 	_srcRect(*srcRect),
 	_dstRect(*dstRect),
-	_drawNum(0),
 	_isValid(true),
 	_wantsDraw(true),
 	_transform(transform) {
diff --git a/engines/wintermute/base/gfx/osystem/render_ticket.h b/engines/wintermute/base/gfx/osystem/render_ticket.h
index 3690e34774..e824c09fe7 100644
--- a/engines/wintermute/base/gfx/osystem/render_ticket.h
+++ b/engines/wintermute/base/gfx/osystem/render_ticket.h
@@ -52,7 +52,7 @@ class BaseSurfaceOSystem;
 class RenderTicket {
 public:
 	RenderTicket(BaseSurfaceOSystem *owner, const Graphics::Surface *surf, Common::Rect *srcRect, Common::Rect *dstRest, TransformStruct transform); 
-	RenderTicket() : _isValid(true), _wantsDraw(false), _drawNum(0), _transform(TransformStruct()) {}
+	RenderTicket() : _isValid(true), _wantsDraw(false), _transform(TransformStruct()) {}
 	~RenderTicket();
 	const Graphics::Surface *getSurface() const { return _surface; }
 	// Non-dirty-rects:
@@ -64,7 +64,6 @@ public:
 
 	bool _isValid;
 	bool _wantsDraw;
-	uint32 _drawNum;
 
 	TransformStruct _transform;