From 6b57fc54ec5c8b93071b4136ddb6756d7423bd0f Mon Sep 17 00:00:00 2001
From: Jason Crain <jason@aquaticape.us>
Date: Fri, 19 Feb 2016 10:54:29 -0600
Subject: [PATCH] Cache result of inner loop in visitDepthFirst

Speeds up sorting of text blocks.

bug #77087
---
 poppler/TextOutputDev.cc | 42 ++++++++++++++++++++++++++++++++++--------
 poppler/TextOutputDev.h  |  4 ++++
 2 files changed, 38 insertions(+), 8 deletions(-)

diff --git a/poppler/TextOutputDev.cc b/poppler/TextOutputDev.cc
index fff3f05..431a19d 100644
--- a/poppler/TextOutputDev.cc
+++ b/poppler/TextOutputDev.cc
@@ -54,6 +54,7 @@
 #include <math.h>
 #include <float.h>
 #include <ctype.h>
+#include <algorithm>
 #ifdef _WIN32
 #include <fcntl.h> // for O_BINARY
 #include <io.h>    // for setmode
@@ -2064,7 +2065,8 @@ GBool TextBlock::isBeforeByRule2(TextBlock *blk1) {
 // http://en.wikipedia.org/wiki/Topological_sorting
 int TextBlock::visitDepthFirst(TextBlock *blkList, int pos1,
 			       TextBlock **sorted, int sortPos,
-			       GBool* visited) {
+			       GBool* visited,
+			       TextBlock **cache, int cacheSize) {
   int pos2;
   TextBlock *blk1, *blk2, *blk3;
   GBool before;
@@ -2119,15 +2121,29 @@ int TextBlock::visitDepthFirst(TextBlock *blkList, int pos1,
         //          such that blk1 is before blk3 by rule 1,
         //          and blk3 is before blk2 by rule 1.
         before = gTrue;
-        for (blk3 = blkList; blk3; blk3 = blk3->next) {
-	  if (blk3 == blk2 || blk3 == blk1) {
-	    continue;
-	  }
-	  if (blk1->isBeforeByRule1(blk3) &&
-	      blk3->isBeforeByRule1(blk2)) {
+	for (int i = 0; i < cacheSize && cache[i]; ++i) {
+	  if (blk1->isBeforeByRule1(cache[i]) &&
+	      cache[i]->isBeforeByRule1(blk2)) {
 	    before = gFalse;
+	    std::rotate(cache, cache + i, cache + i + 1);
 	    break;
 	  }
+	}
+
+	if (before) {
+	  for (blk3 = blkList; blk3; blk3 = blk3->next) {
+	    if (blk3 == blk2 || blk3 == blk1) {
+	      continue;
+	    }
+	    if (blk1->isBeforeByRule1(blk3) &&
+		blk3->isBeforeByRule1(blk2)) {
+	      before = gFalse;
+	      std::copy_backward(cache, cache + cacheSize - 1,
+				 cache + cacheSize);
+	      cache[0] = blk3;
+	      break;
+	    }
+	  }
         }
 #if 0 // for debugging
         if (before) {
@@ -2141,7 +2157,7 @@ int TextBlock::visitDepthFirst(TextBlock *blkList, int pos1,
     if (before) {
       // blk2 is before blk1, so it needs to be visited
       // before we can add blk1 to the sorted list.
-      sortPos = blk2->visitDepthFirst(blkList, pos2, sorted, sortPos, visited);
+      sortPos = blk2->visitDepthFirst(blkList, pos2, sorted, sortPos, visited, cache, cacheSize);
     }
   }
 #if 0 // for debugging
@@ -2152,6 +2168,16 @@ int TextBlock::visitDepthFirst(TextBlock *blkList, int pos1,
   return sortPos;
 }
 
+int TextBlock::visitDepthFirst(TextBlock *blkList, int pos1,
+			       TextBlock **sorted, int sortPos,
+			       GBool* visited) {
+  const int blockCacheSize = 4;
+  TextBlock *blockCache[blockCacheSize];
+  std::fill(blockCache, blockCache + blockCacheSize, (TextBlock*)NULL);
+  return visitDepthFirst(blkList, pos1, sorted, sortPos, visited, blockCache,
+			 blockCacheSize);
+}
+
 //------------------------------------------------------------------------
 // TextFlow
 //------------------------------------------------------------------------
diff --git a/poppler/TextOutputDev.h b/poppler/TextOutputDev.h
index 2aab94f..545f743 100644
--- a/poppler/TextOutputDev.h
+++ b/poppler/TextOutputDev.h
@@ -396,6 +396,10 @@ private:
   int visitDepthFirst(TextBlock *blkList, int pos1,
 		      TextBlock **sorted, int sortPos,
 		      GBool* visited);
+  int visitDepthFirst(TextBlock *blkList, int pos1,
+		      TextBlock **sorted, int sortPos,
+		      GBool* visited,
+		      TextBlock **cache, int cacheSize);
 
   TextPage *page;		// the parent page
   int rot;			// text rotation
-- 
2.7.0