use SkTDynamicHash in picture recording

src/core/SkPictureFlat.h

Index: src/core/SkPictureFlat.h
diff --git a/src/core/SkPictureFlat.h b/src/core/SkPictureFlat.h
index 76120f79cbad892530b2235155062312aa2f3267..ac8e304c0f2c3031885efb09e47d5a6fe00d4913 100644
--- a/src/core/SkPictureFlat.h
+++ b/src/core/SkPictureFlat.h
@@ -10,17 +10,19 @@
 
 //#define SK_DEBUG_SIZE
 
-#include "SkChunkAlloc.h"
 #include "SkBitmap.h"
 #include "SkBitmapHeap.h"
+#include "SkChecksum.h"
+#include "SkChunkAlloc.h"
+#include "SkMatrix.h"
 #include "SkOrderedReadBuffer.h"
 #include "SkOrderedWriteBuffer.h"
-#include "SkPicture.h"
-#include "SkPtrRecorder.h"
-#include "SkMatrix.h"
 #include "SkPaint.h"
 #include "SkPath.h"
+#include "SkPicture.h"
+#include "SkPtrRecorder.h"
 #include "SkRegion.h"
+#include "SkTDynamicHash.h"
 #include "SkTRefArray.h"
 #include "SkTSearch.h"
 
@@ -263,87 +265,32 @@ private:
 
 class SkFlatData {
 public:
-    /**
-     *  Compare two SkFlatData ptrs, returning -1, 0, 1 to allow them to be
-     *  sorted.
-     *
-     *  Note: this assumes that a and b have different sentinel values, either
-     *  InCache or AsCandidate, otherwise the loop will go beyond the end of
-     *  the buffers.
-     *
-     *  dataToCompare() returns 2 fields before the flattened data:
-     *      - checksum
-     *      - size
-     *  This ensures that if we see two blocks of different length, we will
-     *  notice that right away, and not read any further. It also ensures that
-     *  we see the checksum right away, so that most of the time it is enough
-     *  to short-circuit our comparison.
-     */
-    static int Compare(const SkFlatData& a, const SkFlatData& b) {
-        const uint32_t* stop = a.dataStop();
-        const uint32_t* a_ptr = a.dataToCompare() - 1;
-        const uint32_t* b_ptr = b.dataToCompare() - 1;
-        // We use -1 above, so we can pre-increment our pointers in the loop
-        while (*++a_ptr == *++b_ptr) {}
-
-        if (a_ptr == stop) {    // sentinel
-            SkASSERT(b.dataStop() == b_ptr);
-            return 0;
-        }
-        SkASSERT(a_ptr < a.dataStop());
-        SkASSERT(b_ptr < b.dataStop());
-        return (*a_ptr < *b_ptr) ? -1 : 1;
-    }
-
-    // Adapts Compare to be used with SkTSearch
-    static bool Less(const SkFlatData& a, const SkFlatData& b) {
-        return Compare(a, b) < 0;
-    }
-
-    int index() const { return fIndex; }
-    const void* data() const { return (const char*)this + sizeof(*this); }
-    void* data() { return (char*)this + sizeof(*this); }
-    // Our data is always 32bit aligned, so we can offer this accessor
-    uint32_t* data32() { return (uint32_t*)this->data(); }
-    // Returns the size of the flattened data.
-    size_t flatSize() const { return fFlatSize; }
-
-    void setSentinelInCache() {
-        this->setSentinel(kInCache_Sentinel);
-    }
-    void setSentinelAsCandidate() {
-        this->setSentinel(kCandidate_Sentinel);
-    }
-
-    uint32_t checksum() const { return fChecksum; }
-
-#ifdef SK_DEBUG_SIZE
-    // returns the logical size of our data. Does not return any sentinel or
-    // padding we might have.
-    size_t size() const {
-        return sizeof(SkFlatData) + fFlatSize;
-    }
-#endif
-
-    static SkFlatData* Create(SkFlatController* controller, const void* obj, int index,
+    // Flatten obj into an SkFlatData with this index.  controller owns the SkFlatData*.
+    static SkFlatData* Create(SkFlatController* controller,
+                              const void* obj,
+                              int index,
                               void (*flattenProc)(SkOrderedWriteBuffer&, const void*));
 
+    // Unflatten this into result, using bitmapHeap and facePlayback for bitmaps and fonts if given.
     void unflatten(void* result,
                    void (*unflattenProc)(SkOrderedReadBuffer&, void*),
                    SkBitmapHeap* bitmapHeap = NULL,
                    SkTypefacePlayback* facePlayback = NULL) const;
 
-    // When we purge an entry, we want to reuse an old index for the new entry,
-    // so we expose this setter.
-    void setIndex(int index) { fIndex = index; }
-
-    // for unittesting
-    friend bool operator==(const SkFlatData& a, const SkFlatData& b) {
-        size_t N = (const char*)a.dataStop() - (const char*)a.dataToCompare();
-        return !memcmp(a.dataToCompare(), b.dataToCompare(), N);
+    // Do these contain the same data?  Ignores index() and topBot().
+    bool operator==(const SkFlatData& that) const {
+        if (this->checksum() != that.checksum() || this->flatSize() != that.flatSize()) {
+            return false;
+        }
+        return memcmp(this->data(), that.data(), this->flatSize()) == 0;
     }
 
-    // returns true if fTopBot[] has been recorded
+    int index() const { return fIndex; }
+    const uint8_t* data() const { return (const uint8_t*)this + sizeof(*this); }
+    size_t flatSize() const { return fFlatSize; }
+    uint32_t checksum() const { return fChecksum; }
+
+    // Returns true if fTopBot[] has been recorded.
     bool isTopBotWritten() const {
         return !SkScalarIsNaN(fTopBot[0]);
     }
@@ -355,54 +302,37 @@ public:
         return fTopBot;
     }
 
-    // return the topbot[] after it has been recorded
+    // Return the topbot[] after it has been recorded.
     const SkScalar* topBot() const {
         SkASSERT(this->isTopBotWritten());
         return fTopBot;
     }
 
 private:
-    // This is *not* part of the key for search/sort
-    int fIndex;
+    // For SkTDynamicHash.
+    static const SkFlatData& Identity(const SkFlatData& flat) { return flat; }
+    static uint32_t Hash(const SkFlatData& flat) { return flat.checksum(); }
+    static bool Equal(const SkFlatData& a, const SkFlatData& b) { return a == b; }
 
-    // Cache of paint's FontMetrics fTop,fBottom
-    // initialied to [NaN,NaN] as a sentinel that they have not been recorded yet
-    //
-    // This is *not* part of the key for search/sort
-    mutable SkScalar fTopBot[2];
+    void setIndex(int index) { fIndex = index; }
+    uint8_t* data() { return (uint8_t*)this + sizeof(*this); }
 
-    // marks fTopBot[] as unrecorded
-    void setTopBotUnwritten() {
-        this->fTopBot[0] = SK_ScalarNaN; // initial to sentinel values
+    // This assumes the payload flat data has already been written and does not modify it.
+    void stampHeader(int index, int32_t size) {
+        SkASSERT(SkIsAlign4(size));
+        fIndex     = index;
+        fFlatSize  = size;
+        fTopBot[0] = SK_ScalarNaN;  // Mark as unwritten.
+        fChecksum  = SkChecksum::Compute((uint32_t*)this->data(), size);
     }
 
-    // From here down is the data we look at in the search/sort. We always begin
-    // with the checksum and then length.
+    int fIndex;
+    int32_t fFlatSize;
     uint32_t fChecksum;
-    int32_t  fFlatSize;  // size of flattened data
-    // uint32_t flattenedData[]
-    // uint32_t sentinelValue
-
-    const uint32_t* dataToCompare() const {
-        return (const uint32_t*)&fChecksum;
-    }
-    const uint32_t* dataStop() const {
-        SkASSERT(SkIsAlign4(fFlatSize));
-        return (const uint32_t*)((const char*)this->data() + fFlatSize);
-    }
-
-    enum {
-        kInCache_Sentinel = 0,
-        kCandidate_Sentinel = ~0U,
-    };
-    void setSentinel(uint32_t value) {
-        SkASSERT(SkIsAlign4(fFlatSize));
-        this->data32()[fFlatSize >> 2] = value;
-    }
+    mutable SkScalar fTopBot[2];  // Cache of FontMetrics fTop, fBottom.  Starts as [NaN,?].
+    // uint32_t flattenedData[] implicitly hangs off the end.
 
-    // This does not modify the payload flat data, in case it's already been written.
-    void stampHeaderAndSentinel(int index, int32_t size);
-    template <class T> friend class SkFlatDictionary;  // For stampHeaderAndSentinel().
+    template <class T> friend class SkFlatDictionary;
 };
 
 template <class T>
@@ -417,11 +347,20 @@ public:
     , fScratchSize(scratchSizeGuess)
     , fScratch(AllocScratch(fScratchSize))
     , fWriteBuffer(kWriteBufferGrowthBytes)
-    , fWriteBufferReady(false)
-    , fNextIndex(1)  { // set to 1 since returning a zero from find() indicates failure
-        sk_bzero(fHash, sizeof(fHash));
+    , fWriteBufferReady(false) {
+        this->reset();
+    }
+
+    /**
+     * Clears the dictionary of all entries. However, it does NOT free the
+     * memory that was allocated for each entry (that's owned by controller).
+     */
+    void reset() {
+        fIndexedData.rewind();
+        // TODO(mtklein): There's no reason to have the index start from 1.  Clean this up.
         // index 0 is always empty since it is used as a signal that find failed
         fIndexedData.push(NULL);
+        fNextIndex = 1;
     }
 
     ~SkFlatDictionary() {
@@ -429,26 +368,24 @@ public:
     }
 
     int count() const {
-        SkASSERT(fIndexedData.count() == fSortedData.count()+1);
-        return fSortedData.count();
+        SkASSERT(fIndexedData.count() == fNextIndex);
+        SkASSERT(fHash.count() == fNextIndex - 1);
+        return fNextIndex - 1;
     }
 
-    const SkFlatData*  operator[](int index) const {
-        SkASSERT(index >= 0 && index < fSortedData.count());
-        return fSortedData[index];
+    // For testing only.  Index is zero-based.
+    const SkFlatData* operator[](int index) {
+        return fIndexedData[index+1];
     }
 
     /**
-     * Clears the dictionary of all entries. However, it does NOT free the
-     * memory that was allocated for each entry.
+     * Given an element of type T return its 1-based index in the dictionary. If
+     * the element wasn't previously in the dictionary it is automatically
+     * added.
+     *
      */
-    void reset() {
-        fSortedData.reset();
-        fIndexedData.rewind();
-        // index 0 is always empty since it is used as a signal that find failed
-        fIndexedData.push(NULL);
-        fNextIndex = 1;
-        sk_bzero(fHash, sizeof(fHash));
+    int find(const T& element) {
+        return this->findAndReturnFlat(element)->index();
     }
 
     /**
@@ -459,76 +396,64 @@ public:
      * the entry in the dictionary, it returns the actual SkFlatData.
      */
     const SkFlatData* findAndReplace(const T& element,
-                                     const SkFlatData* toReplace, bool* added,
+                                     const SkFlatData* toReplace,
+                                     bool* added,
                                      bool* replaced) {
         SkASSERT(added != NULL && replaced != NULL);
-        int oldCount = fSortedData.count();
-        const SkFlatData* flat = this->findAndReturnFlat(element);
-        *added = fSortedData.count() == oldCount + 1;
-        *replaced = false;
-        if (*added && toReplace != NULL) {
-            // First, find the index of the one to replace
-            int indexToReplace = fSortedData.find(toReplace);
-            if (indexToReplace >= 0) {
-                // findAndReturnFlat set the index to fNextIndex and increased
-                // fNextIndex by one. Reuse the index from the one being
-                // replaced and reset fNextIndex to the proper value.
-                int oldIndex = flat->index();
-                const_cast<SkFlatData*>(flat)->setIndex(toReplace->index());
-                fIndexedData[toReplace->index()] = flat;
-                fNextIndex--;
-                // Remove from the arrays.
-                fSortedData.remove(indexToReplace);
-                fIndexedData.remove(oldIndex);
-                // Remove from the hash table.
-                int oldHash = ChecksumToHashIndex(toReplace->checksum());
-                if (fHash[oldHash] == toReplace) {
-                    fHash[oldHash] = NULL;
-                }
-                // Delete the actual object.
-                fController->unalloc((void*)toReplace);
-                *replaced = true;
-                SkASSERT(fIndexedData.count() == fSortedData.count()+1);
-            }
+
+        const int oldCount = this->count();
+        SkFlatData* flat = this->findAndReturnMutableFlat(element);
+        *added = this->count() > oldCount;
+
+        // If we don't want to replace anything, we're done.
+        if (!*added || toReplace == NULL) {
+            *replaced = false;
+            return flat;
         }
-        return flat;
-    }
 
-    /**
-     * Given an element of type T return its 1-based index in the dictionary. If
-     * the element wasn't previously in the dictionary it is automatically
-     * added.
-     *
-     * To make the Compare function fast, we write a sentinel value at the end
-     * of each block. The blocks in our fSortedData[] all have a 0 sentinel. The
-     * newly created block we're comparing against has a -1 in the sentinel.
-     *
-     * This trick allows Compare to always loop until failure. If it fails on
-     * the sentinal value, we know the blocks are equal.
-     */
-    int find(const T& element) {
-        return this->findAndReturnFlat(element)->index();
+        // If we don't have the thing to replace, we're done.
+        const SkFlatData* found = fHash.find(*toReplace);
+        if (found == NULL) {
+            *replaced = false;
+            return flat;
+        }
+
+        // findAndReturnMutableFlat gave us index (fNextIndex-1), but we'll use the old one.
+        fIndexedData.remove(flat->index());
+        fNextIndex--;
+        flat->setIndex(found->index());
+        fIndexedData[flat->index()] = flat;
+
+        // findAndReturnMutableFlat already called fHash.add(), so we just clean up the old entry.
+        fHash.remove(*found);
+        fController->unalloc((void*)found);
+        SkASSERT(this->count() == oldCount);
+
+        *replaced = true;
+        return flat;
     }
 
     /**
      *  Unflatten the objects and return them in SkTRefArray, or return NULL
-     *  if there no objects (instead of an empty array).
+     *  if there no objects.  Caller takes ownership of result.
      */
     SkTRefArray<T>* unflattenToArray() const {
-        int count = fSortedData.count();
-        SkTRefArray<T>* array = NULL;
-        if (count > 0) {
-            array = SkTRefArray<T>::Create(count);
-            this->unflattenIntoArray(&array->writableAt(0));
+        const int count = this->count();
+        if (count == 0) {
+            return NULL;
+        }
+        SkTRefArray<T>* array = SkTRefArray<T>::Create(count);
+        for (int i = 0; i < count; i++) {
+            this->unflatten(&array->writableAt(i), fIndexedData[i+1]);
         }
         return array;
     }
 
     /**
-     * Unflatten the specific object at the given index
+     * Unflatten the specific object at the given index.
+     * Caller takes ownership of the result.
      */
     T* unflatten(int index) const {
-        SkASSERT(fIndexedData.count() == fSortedData.count()+1);
         const SkFlatData* element = fIndexedData[index];
         SkASSERT(index == element->index());
 
@@ -537,41 +462,12 @@ public:
         return dst;
     }
 
+    /**
+     * Find or insert a flattened version of element into the dictionary.
+     * Caller does not take ownership of the result.  This will not return NULL.
+     */
     const SkFlatData* findAndReturnFlat(const T& element) {
-        // Only valid until the next call to resetScratch().
-        const SkFlatData& scratch = this->resetScratch(element, fNextIndex);
-
-        // See if we have it in the hash?
-        const int hashIndex = ChecksumToHashIndex(scratch.checksum());
-        const SkFlatData* candidate = fHash[hashIndex];
-        if (candidate != NULL && SkFlatData::Compare(scratch, *candidate) == 0) {
-            return candidate;
-        }
-
-        // See if we have it at all?
-        const int index = SkTSearch<const SkFlatData, SkFlatData::Less>(fSortedData.begin(),
-                                                                        fSortedData.count(),
-                                                                        &scratch,
-                                                                        sizeof(&scratch));
-        if (index >= 0) {
-            // Found.  Update hash before we return.
-            fHash[hashIndex] = fSortedData[index];
-            return fSortedData[index];
-        }
-
-        // We don't have it.  Add it.
-        SkFlatData* detached = this->detachScratch();
-        // detached will live beyond the next call to resetScratch(), but is owned by fController.
-        *fSortedData.insert(~index) = detached;  // SkTSearch returned bit-not of where to insert.
-        *fIndexedData.insert(detached->index()) = detached;
-        fHash[hashIndex] = detached;
-
-        SkASSERT(detached->index() == fNextIndex);
-        SkASSERT(fSortedData.count() == fNextIndex);
-        SkASSERT(fIndexedData.count() == fNextIndex+1);
-        fNextIndex++;
-
-        return detached;
+        return this->findAndReturnMutableFlat(element);
     }
 
 protected:
@@ -579,10 +475,10 @@ protected:
     void (*fUnflattenProc)(SkOrderedReadBuffer&, void*);
 
 private:
-    // Layout: [ SkFlatData header, 20 bytes ] [ data ..., 4-byte aligned ] [ sentinel, 4 bytes]
+    // Layout: [ SkFlatData header, 20 bytes ] [ data ..., 4-byte aligned ]
     static size_t SizeWithPadding(size_t flatDataSize) {
         SkASSERT(SkIsAlign4(flatDataSize));
-        return sizeof(SkFlatData) + flatDataSize + sizeof(uint32_t);
+        return sizeof(SkFlatData) + flatDataSize;
     }
 
     // Allocate a new scratch SkFlatData.  Must be sk_freed.
@@ -605,6 +501,21 @@ private:
         fWriteBufferReady = true;
     }
 
+    // As findAndReturnFlat, but returns a mutable pointer for internal use.
+    SkFlatData* findAndReturnMutableFlat(const T& element) {
+        // Only valid until the next call to resetScratch().
+        const SkFlatData& scratch = this->resetScratch(element, fNextIndex);
+
+        SkFlatData* candidate = fHash.find(scratch);
+        if (candidate != NULL) return candidate;
+
+        SkFlatData* detached = this->detachScratch();
+        fHash.add(detached);
+        *fIndexedData.insert(fNextIndex) = detached;
+        fNextIndex++;
+        return detached;
+    }
+
     // This reference is valid only until the next call to resetScratch() or detachScratch().
     const SkFlatData& resetScratch(const T& element, int index) {
         this->lazyWriteBufferInit();
@@ -628,8 +539,8 @@ private:
             fScratch = larger;
         }
 
-        // The data is in fScratch now, but we need to stamp its header and trailing sentinel.
-        fScratch->stampHeaderAndSentinel(index, bytesWritten);
+        // The data is in fScratch now but we need to stamp its header.
+        fScratch->stampHeader(index, bytesWritten);
         return *fScratch;
     }
 
@@ -641,72 +552,36 @@ private:
         const size_t paddedSize = SizeWithPadding(fScratch->flatSize());
         SkFlatData* detached = (SkFlatData*)fController->allocThrow(paddedSize);
 
-        // Copy scratch into the new SkFlatData, setting the sentinel for cache storage.
+        // Copy scratch into the new SkFlatData.
         memcpy(detached, fScratch, paddedSize);
-        detached->setSentinelInCache();
 
         // We can now reuse fScratch, and detached will live until fController dies.
         return detached;
     }
 
     void unflatten(T* dst, const SkFlatData* element) const {
-        element->unflatten(dst, fUnflattenProc,
+        element->unflatten(dst,
+                           fUnflattenProc,
                            fController->getBitmapHeap(),
                            fController->getTypefacePlayback());
     }
 
-    void unflattenIntoArray(T* array) const {
-        const int count = fSortedData.count();
-        SkASSERT(fIndexedData.count() == fSortedData.count()+1);
-        const SkFlatData* const* iter = fSortedData.begin();
-        for (int i = 0; i < count; ++i) {
-            const SkFlatData* element = iter[i];
-            int index = element->index() - 1;
-            SkASSERT((unsigned)index < (unsigned)count);
-            unflatten(&array[index], element);
-        }
-    }
-
+    // All SkFlatData* stored in fIndexedData and fHash are owned by the controller.
     SkAutoTUnref<SkFlatController> fController;
     size_t fScratchSize;  // How many bytes fScratch has allocated for data itself.
     SkFlatData* fScratch;  // Owned, must be freed with sk_free.
     SkOrderedWriteBuffer fWriteBuffer;
     bool fWriteBufferReady;
 
-    // SkFlatDictionary has two copies of the data one indexed by the
-    // SkFlatData's index and the other sorted. The sorted data is used
-    // for finding and uniquification while the indexed copy is used
-    // for standard array-style lookups based on the SkFlatData's index
-    // (as in 'unflatten').
+    // We map between SkFlatData and a 1-based integer index.
     int fNextIndex;
+
+    // For index -> SkFlatData.  fIndexedData[0] is always NULL.
     SkTDArray<const SkFlatData*> fIndexedData;
-    // fSortedData is sorted by checksum/size/data.
-    SkTDArray<const SkFlatData*> fSortedData;
-
-    enum {
-        // Determined by trying diff values on picture-recording benchmarks
-        // (e.g. PictureRecordBench.cpp), choosing the smallest value that
-        // showed a big improvement. Even better would be to benchmark diff
-        // values on recording representative web-pages or other "real" content.
-        HASH_BITS   = 7,
-        HASH_MASK   = (1 << HASH_BITS) - 1,
-        HASH_COUNT  = 1 << HASH_BITS
-    };
-    const SkFlatData* fHash[HASH_COUNT];
-
-    static int ChecksumToHashIndex(uint32_t checksum) {
-        int n = checksum;
-        if (HASH_BITS < 32) {
-            n ^= n >> 16;
-        }
-        if (HASH_BITS < 16) {
-            n ^= n >> 8;
-        }
-        if (HASH_BITS < 8) {
-            n ^= n >> 4;
-        }
-        return n & HASH_MASK;
-    }
+
+    // For SkFlatData -> cached SkFlatData, which has index().
+    SkTDynamicHash<SkFlatData, SkFlatData,
+                   SkFlatData::Identity, SkFlatData::Hash, SkFlatData::Equal> fHash;
 };
 
 ///////////////////////////////////////////////////////////////////////////////