Once Chromium starts holding on to paths and we can actually reuse cached path data (e.g., masks & geometry) we will need a way to preserve that reuse in the skps. This CL begins adding that capability. More analysis & profiling needs to be done before it is always enabled.

When enabled it does make the disabled path de-duping test in the Canvas unit test pass.

BUG=skia:507
R=bsalomon@google.com, mtklein@google.com

Author: robertphillips@google.com

Review URL: https://codereview.chromium.org/190923002

git-svn-id: http://skia.googlecode.com/svn/trunk@13709 2bbb7eff-a529-9590-31e7-b0007b416f81

4 files changed, 79 insertions, 13 deletions

diff --git a/src/core/SkPathHeap.cpp b/src/core/SkPathHeap.cpp
index a8271e1fa2..d71257d731 100644
--- a/src/core/SkPathHeap.cpp
+++ b/src/core/SkPathHeap.cpp
@@ -9,6 +9,7 @@
 #include "SkPath.h"
 #include "SkStream.h"
 #include "SkReadBuffer.h"
+#include "SkTSearch.h"
 #include "SkWriteBuffer.h"
 #include <new>
 
@@ -49,6 +50,38 @@ int SkPathHeap::append(const SkPath& path) {
     return fPaths.count();
 }
 
+SkPathHeap::LookupEntry::LookupEntry(const SkPath& path) 
+    : fGenerationID(path.getGenerationID()), fStorageSlot(0) {
+}
+
+SkPathHeap::LookupEntry* SkPathHeap::addIfNotPresent(const SkPath& path) {
+    LookupEntry searchKey(path);
+    int index = SkTSearch<const LookupEntry, LookupEntry::Less>(
+                                    fLookupTable.begin(),
+                                    fLookupTable.count(),
+                                    searchKey, 
+                                    sizeof(LookupEntry));
+    if (index < 0) {
+        index = ~index;
+        *fLookupTable.insert(index) = LookupEntry(path);
+    }
+
+    return &fLookupTable[index];;
+}
+
+int SkPathHeap::insert(const SkPath& path) {
+    SkPathHeap::LookupEntry* entry = this->addIfNotPresent(path);
+
+    if (entry->storageSlot() > 0) {
+        return entry->storageSlot();
+    }
+
+    int newSlot = this->append(path);
+    SkASSERT(newSlot > 0);
+    entry->setStorageSlot(newSlot);
+    return newSlot;
+}
+
 void SkPathHeap::flatten(SkWriteBuffer& buffer) const {
     int count = fPaths.count();
 
diff --git a/src/core/SkPathHeap.h b/src/core/SkPathHeap.h
index e3b0f7a84f..7fdcdd93e0 100644
--- a/src/core/SkPathHeap.h
+++ b/src/core/SkPathHeap.h
@@ -30,6 +30,11 @@ public:
      */
     int append(const SkPath&);
 
+    /** Add the specified path to the heap using its gen ID to de-duplicate.
+        Returns the path's index in the heap + 1.
+     */
+    int insert(const SkPath&);
+
     // called during picture-playback
     int count() const { return fPaths.count(); }
     const SkPath& operator[](int index) const {
@@ -44,6 +49,27 @@ private:
     // we just store ptrs into fHeap here
     SkTDArray<SkPath*>  fPaths;
 
+    class LookupEntry {
+    public:
+        LookupEntry(const SkPath& path);
+
+        int storageSlot() const { return fStorageSlot; }
+        void setStorageSlot(int storageSlot) { fStorageSlot = storageSlot; }
+
+        static bool Less(const LookupEntry& a, const LookupEntry& b) {
+            return a.fGenerationID < b.fGenerationID;
+        }
+
+    private:
+        uint32_t fGenerationID;     // the SkPath's generation ID
+        // the path's index in the heap + 1. It is 0 if the path is not yet in the heap.
+        int      fStorageSlot;      
+    };
+
+    SkTDArray<LookupEntry> fLookupTable;
+
+    SkPathHeap::LookupEntry* addIfNotPresent(const SkPath& path);
+
     typedef SkRefCnt INHERITED;
 };
 
diff --git a/src/core/SkPictureRecord.cpp b/src/core/SkPictureRecord.cpp
index b9e8b93843..08b69b8527 100644
--- a/src/core/SkPictureRecord.cpp
+++ b/src/core/SkPictureRecord.cpp
@@ -1672,7 +1672,11 @@ int SkPictureRecord::addPathToHeap(const SkPath& path) {
     if (NULL == fPathHeap) {
         fPathHeap = SkNEW(SkPathHeap);
     }
+#ifdef SK_DEDUP_PICTURE_PATHS
+    return fPathHeap->insert(path);
+#else
     return fPathHeap->append(path);
+#endif
 }
 
 void SkPictureRecord::addPath(const SkPath& path) {
diff --git a/tests/CanvasTest.cpp b/tests/CanvasTest.cpp
index c9a7db18e9..b3a63f1cbe 100644
--- a/tests/CanvasTest.cpp
+++ b/tests/CanvasTest.cpp
@@ -196,13 +196,26 @@ static SkMatrix testMatrix() {
     return matrix;
 }
 const SkMatrix kTestMatrix = testMatrix();
-static SkPath testPath() {
+static SkPath test_path() {
     SkPath path;
     path.addRect(SkRect::MakeXYWH(SkIntToScalar(0), SkIntToScalar(0),
                                   SkIntToScalar(2), SkIntToScalar(1)));
     return path;
 }
-const SkPath kTestPath = testPath();
+const SkPath kTestPath = test_path();
+static SkPath test_nearly_zero_length_path() {
+    SkPath path;
+    SkPoint pt1 = { 0, 0 };
+    SkPoint pt2 = { 0, SK_ScalarNearlyZero };
+    SkPoint pt3 = { SkIntToScalar(1), 0 };
+    SkPoint pt4 = { SkIntToScalar(1), SK_ScalarNearlyZero/2 };
+    path.moveTo(pt1);
+    path.lineTo(pt2);
+    path.lineTo(pt3);
+    path.lineTo(pt4);
+    return path;
+}
+const SkPath kNearlyZeroLengthPath = test_nearly_zero_length_path();
 static SkRegion testRegion() {
     SkRegion region;
     SkIRect rect = SkIRect::MakeXYWH(0, 0, 2, 1);
@@ -449,17 +462,7 @@ static void DrawNearlyZeroLengthPathTestStep(SkCanvas* canvas,
     paint.setStrokeWidth(SkIntToScalar(1));
     paint.setStyle(SkPaint::kStroke_Style);
 
-    SkPath path;
-    SkPoint pt1 = { 0, 0 };
-    SkPoint pt2 = { 0, SK_ScalarNearlyZero };
-    SkPoint pt3 = { SkIntToScalar(1), 0 };
-    SkPoint pt4 = { SkIntToScalar(1), SK_ScalarNearlyZero/2 };
-    path.moveTo(pt1);
-    path.lineTo(pt2);
-    path.lineTo(pt3);
-    path.lineTo(pt4);
-
-    canvas->drawPath(path, paint);
+    canvas->drawPath(kNearlyZeroLengthPath, paint);
 }
 TEST_STEP(DrawNearlyZeroLengthPath, DrawNearlyZeroLengthPathTestStep);