Deterministic SkTSet and PDF Output

src/pdf/SkTSet.h

 /*
  * Copyright 2012 Google Inc.
  *
  * Use of this source code is governed by a BSD-style license that can be
  * found in the LICENSE file.
  */
 
 #ifndef SkTSet_DEFINED
 #define SkTSet_DEFINED
 
 #include "SkTDArray.h"
 #include "SkTypes.h"
 
 /** \class SkTSet<T>
 
-    The SkTSet template class defines a set.
+    The SkTSet template class defines a set. Elements are additionally
+    guaranteed to be sorted by their insertion order.
     Main operations supported now are: add, merge, find and contains.
 
     TSet<T> is mutable.
 */
 
 // TODO: Add remove, intersect and difference operations.
 // TODO: Add bench tests.
 template <typename T> class SkTSet {

[vandebo (ex-Chrome), 2013/07/17 15:30:43]

Should this be renamed to SkTOrderedSet now?

[ducky, 2013/07/17 19:32:21]

Renaming this class would require a lot of changes throughout the PDF code. I'm
not sure it's worth it to go through and change everything, especially since in
most of the use cases, you're only using the plain set functionality?

 public:
     SkTSet() {
-        fArray = SkNEW(SkTDArray<T>);
+        fSetArray = SkNEW(SkTDArray<T>);
+        fOrderedArray = SkNEW(SkTDArray<T>);
     }
 
     ~SkTSet() {
-        SkASSERT(fArray);
-        SkDELETE(fArray);
+        SkASSERT(fSetArray);
+        SkDELETE(fSetArray);
+        SkASSERT(fOrderedArray);
+        SkDELETE(fOrderedArray);
     }
 
     SkTSet(const SkTSet<T>& src) {
-        this->fArray = SkNEW_ARGS(SkTDArray<T>, (*src.fArray));
+        this->fSetArray = SkNEW_ARGS(SkTDArray<T>, (*src.fSetArray));
+        this->fOrderedArray = SkNEW_ARGS(SkTDArray<T>, (*src.fOrderedArray));
 #ifdef SK_DEBUG
         validate();
 #endif
     }
 
     SkTSet<T>& operator=(const SkTSet<T>& src) {
-        *this->fArray = *src.fArray;
+        *this->fSetArray = *src.fSetArray;
+        *this->fOrderedArray = *src.fOrderedArray;
 #ifdef SK_DEBUG
         validate();
 #endif
         return *this;
     }
 
     /** Merges src elements into this, and returns the number of duplicates
-     * found.
-    */
+     * found. Elements from src will retain their ordering and will be ordered
+     * after the elements currently in this set.
+     *
+     * Implementation note: this uses a 2-stage merge to obtain O(n log n) time.
+     * The first stage goes through src.fOrderedArray, checking if
+     * this->contains() is false before adding to this.fOrderedArray.
+     * The second stage does a standard sorted list merge on the fSetArrays.
+     */
     int mergeInto(const SkTSet<T>& src) {
-        SkASSERT(fArray);
+        SkASSERT(fSetArray);
+        SkASSERT(fOrderedArray);
+
+        // Do fOrderedArray merge.
+        for (int i = 0; i < src.count(); ++i) {
+            if (!contains((*src.fOrderedArray)[i])) {
+                fOrderedArray->push((*src.fOrderedArray)[i]);
+            }
+        }
+
+        // Do fSetArray merge.
         int duplicates = 0;
 
         SkTDArray<T>* fArrayNew = new SkTDArray<T>();
-        fArrayNew->setReserve(count() + src.count());
+        fArrayNew->setReserve(fOrderedArray->count());
         int i = 0;
         int j = 0;
 
-        while (i < count() && j < src.count()) {
-            if ((*fArray)[i] < (*src.fArray)[j]) {
-                fArrayNew->push((*fArray)[i]);
+        while (i < fSetArray->count() && j < src.count()) {
+            if ((*fSetArray)[i] < (*src.fSetArray)[j]) {
+                fArrayNew->push((*fSetArray)[i]);
                 i++;
-            } else if ((*fArray)[i] > (*src.fArray)[j]) {
-                fArrayNew->push((*src.fArray)[j]);
+            } else if ((*fSetArray)[i] > (*src.fSetArray)[j]) {
+                fArrayNew->push((*src.fSetArray)[j]);
                 j++;
             } else {
                 duplicates++;
                 j++; // Skip one of the duplicates.
             }
         }
 
-        while (i < count()) {
-            fArrayNew->push((*fArray)[i]);
+        while (i < fSetArray->count()) {
+            fArrayNew->push((*fSetArray)[i]);
             i++;
         }
 
         while (j < src.count()) {
-            fArrayNew->push((*src.fArray)[j]);
+            fArrayNew->push((*src.fSetArray)[j]);
             j++;
         }
-        SkDELETE(fArray);
-        fArray = fArrayNew;
+        SkDELETE(fSetArray);
+        fSetArray = fArrayNew;
         fArrayNew = NULL;
 
 #ifdef SK_DEBUG
         validate();
 #endif
         return duplicates;
     }
 
-    /** Adds a new element into set and returns true if the element is already
+    /** Adds a new element into set and returns false if the element is already
      * in this set.
     */
     bool add(const T& elem) {
-        SkASSERT(fArray);
+        SkASSERT(fSetArray);
+        SkASSERT(fOrderedArray);
 
         int pos = 0;
         int i = find(elem, &pos);
         if (i >= 0) {
             return false;
         }
-        *fArray->insert(pos) = elem;
+        *fSetArray->insert(pos) = elem;
+        fOrderedArray->push(elem);
 #ifdef SK_DEBUG
         validate();
 #endif
         return true;
     }
 
     /** Returns true if this set is empty.
     */
     bool isEmpty() const {
-        SkASSERT(fArray);
-        return fArray->isEmpty();
+        SkASSERT(fOrderedArray);

[edisonn, 2013/07/17 12:32:09]

assert fSetArray is empty too

[ducky, 2013/07/17 19:32:21]

Done.

+        return fOrderedArray->isEmpty();
     }
 
     /** Return the number of elements in the set.
      */
     int count() const {
-        SkASSERT(fArray);
-        return fArray->count();
+        SkASSERT(fOrderedArray);

[edisonn, 2013/07/17 12:32:09]

assert both array have the same number of elements

[ducky, 2013/07/17 19:32:21]

Done.

+        return fOrderedArray->count();
     }
 
     /** Return the number of bytes in the set: count * sizeof(T).
      */
     size_t bytes() const {
-        SkASSERT(fArray);
-        return fArray->bytes();
+        SkASSERT(fOrderedArray);

[edisonn, 2013/07/17 12:32:09]

I think we should report the number of total bytes (fSetArray)

[ducky, 2013/07/17 19:32:21]

Should we? According to the function comments, it should be equivalent to
count*sizeof(T), which is the bytes taken by the output array.
I don't know what the current usage cases are, but with proper encapsulation,
fSetArray should be completely hidden, right?

+        return fOrderedArray->bytes();
     }
 
     /** Return the beginning of a set iterator.
      * Elements in the iterator will be sorted ascending.
      */
     const T*  begin() const {
-        SkASSERT(fArray);
-        return fArray->begin();
+        SkASSERT(fOrderedArray);
+        return fOrderedArray->begin();
     }
 
     /** Return the end of a set iterator.
      */
     const T*  end() const {
-        SkASSERT(fArray);
-        return fArray->end();
+        SkASSERT(fOrderedArray);
+        return fOrderedArray->end();
     }
 
     const T&  operator[](int index) const {
-        SkASSERT(fArray);
-        return (*fArray)[index];
+        SkASSERT(fOrderedArray);
+        return (*fOrderedArray)[index];
     }
 
     /** Resets the set (deletes memory and initiates an empty set).
      */
     void reset() {
-        SkASSERT(fArray);
-        fArray->reset();
+        SkASSERT(fSetArray);
+        SkASSERT(fOrderedArray);
+        fSetArray->reset();
+        fOrderedArray->reset();
     }
 
     /** Rewinds the set (preserves memory and initiates an empty set).
      */
     void rewind() {
-        SkASSERT(fArray);
-        fArray->rewind();
+        SkASSERT(fSetArray);
+        SkASSERT(fOrderedArray);
+        fSetArray->rewind();
+        fOrderedArray->rewind();
     }
 
     /** Reserves memory for the set.
      */
     void setReserve(size_t reserve) {
-        SkASSERT(fArray);
-        fArray->setReserve(reserve);
-    }
-
-    /** Returns the index where an element was found.
-     * Returns -1 if the element was not found, and it fills *posToInsertSorted
-     * with the index of the place where elem should be inserted to preserve the
-     * internal array sorted.
-     * If element was found, *posToInsertSorted is undefined.
-     */
-    int find(const T& elem, int* posToInsertSorted = NULL) const {
-        SkASSERT(fArray);
-
-        if (fArray->count() == 0) {
-            if (posToInsertSorted) {
-                *posToInsertSorted = 0;
-            }
-            return -1;
-        }
-        int iMin = 0;
-        int iMax = fArray->count();
-
-        while (iMin < iMax - 1) {
-            int iMid = (iMin + iMax) / 2;
-            if (elem < (*fArray)[iMid]) {
-                iMax = iMid;
-            } else {
-                iMin = iMid;
-            }
-        }
-        if (elem == (*fArray)[iMin]) {
-            return iMin;
-        }
-        if (posToInsertSorted) {
-            if (elem < (*fArray)[iMin]) {
-                *posToInsertSorted = iMin;
-            } else {
-                *posToInsertSorted = iMin + 1;
-            }
-        }
-
-        return -1;
+        SkASSERT(fSetArray);
+        SkASSERT(fOrderedArray);
+        fSetArray->setReserve(reserve);
+        fOrderedArray->setReserve(reserve);
     }
 
     /** Returns true if the array contains this element.
      */
     bool contains(const T& elem) const {
-        SkASSERT(fArray);
+        SkASSERT(fSetArray);
         return (this->find(elem) >= 0);
     }
 
     /** Copies internal array to destination.
      */
     void copy(T* dst) const {
-        SkASSERT(fArray);
-        fArray->copyRange(0, fArray->count(), dst);
+        SkASSERT(fOrderedArray);
+        fOrderedArray->copyRange(0, fOrderedArray->count(), dst);
     }
 
     /** Returns a const reference to the internal vector.
      */
     const SkTDArray<T>& toArray() {
-        SkASSERT(fArray);
-        return *fArray;
+        SkASSERT(fOrderedArray);
+        return *fOrderedArray;
     }
 
     /** Unref all elements in the set.
      */
     void unrefAll() {
-        SkASSERT(fArray);
-        fArray->unrefAll();
+        SkASSERT(fSetArray);
+        SkASSERT(fOrderedArray);
+        fOrderedArray->unrefAll();
+        fSetArray->reset();

[edisonn, 2013/07/17 12:32:09]

I don't think we should reset fSetArray. We just call unref() on all elements,
we don't dispose of them.

[ducky, 2013/07/17 19:32:21]

This was a tricky one. I looked into SkTDArray.h, and it seems like unrefAll()
and safeUnrefAll() both invoke this->reset(). Since we don't want to
double-unref things, I've just moved the reset for the other array into SkTSet.
I'll add a comment to clarify this point (unless there's something wrong with my
logic?).

     }
 
     /** safeUnref all elements in the set.
      */
-     void safeUnrefAll() {
-        SkASSERT(fArray);
-        fArray->safeUnrefAll();
+    void safeUnrefAll() {
+        SkASSERT(fSetArray);
+        SkASSERT(fOrderedArray);
+        fOrderedArray->safeUnrefAll();
+        fSetArray->reset();

[edisonn, 2013/07/17 12:32:09]

I don't think we should reset fSetArray. We just safely call unref() on all
elements,
we don't dispose of them.

[ducky, 2013/07/17 19:32:21]

See above comment - SkTDArray::safeUnrefAll does a reset on itself.

     }
 
 #ifdef SK_DEBUG
     void validate() const {
-        SkASSERT(fArray);
-        fArray->validate();
-        SkASSERT(isSorted() && !hasDuplicates());
+        SkASSERT(fSetArray);
+        SkASSERT(fOrderedArray);
+        fSetArray->validate();
+        fOrderedArray->validate();
+        SkASSERT(isSorted() && !hasDuplicates() && arraysConsistent());
     }
 
     bool hasDuplicates() const {
-        for (int i = 0; i < fArray->count() - 1; ++i) {
-            if ((*fArray)[i] == (*fArray)[i + 1]) {
+        for (int i = 0; i < fSetArray->count() - 1; ++i) {
+            if ((*fSetArray)[i] == (*fSetArray)[i + 1]) {
                 return true;
             }
         }
         return false;
     }
 
     bool isSorted() const {
-        for (int i = 0; i < fArray->count() - 1; ++i) {
+        for (int i = 0; i < fSetArray->count() - 1; ++i) {
             // Use only < operator
-            if (!((*fArray)[i] < (*fArray)[i + 1])) {
+            if (!((*fSetArray)[i] < (*fSetArray)[i + 1])) {
                 return false;
             }
         }
         return true;
     }
+
+    /** Checks if fSetArray is consistent with fOrderedArray
+     */
+    bool arraysConsistent() const {
+        SkASSERT(fSetArray->count() == fOrderedArray->count());
+        for (int i = 0; i < fOrderedArray->count(); ++i) {
+            if (!contains((*fOrderedArray)[i])) {
+                return false;
+            }
+        }
+        // Checking fSetArray -> fOrderedArray should also be done, but

[vandebo (ex-Chrome), 2013/07/17 15:30:43]

What about sorting fSetArray into a temporary copy and checking that it's the
same as fOrderedArray ?

[ducky, 2013/07/17 19:32:21]

Done.

+        // the O(n^2)ness makes some GMs unacceptably slow.
+
+        return true;
+    }
 #endif
 
 private:
-    SkTDArray<T>* fArray;
+    SkTDArray<T>* fSetArray;        // Sorted by pointer address for fast
+                                    // lookup.
+    SkTDArray<T>* fOrderedArray;    // Sorted by insertion order for
+                                    // deterministic output.
+
+    /** Returns the index in fSetArray where an element was found.
+     * Returns -1 if the element was not found, and it fills *posToInsertSorted
+     * with the index of the place where elem should be inserted to preserve the
+     * internal array sorted.
+     * If element was found, *posToInsertSorted is undefined.
+     */
+    int find(const T& elem, int* posToInsertSorted = NULL) const {
+        SkASSERT(fSetArray);
+
+        if (fSetArray->count() == 0) {
+            if (posToInsertSorted) {
+                *posToInsertSorted = 0;
+            }
+            return -1;
+        }
+        int iMin = 0;
+        int iMax = fSetArray->count();
+
+        while (iMin < iMax - 1) {
+            int iMid = (iMin + iMax) / 2;
+            if (elem < (*fSetArray)[iMid]) {
+                iMax = iMid;
+            } else {
+                iMin = iMid;
+            }
+        }
+        if (elem == (*fSetArray)[iMin]) {
+            return iMin;
+        }
+        if (posToInsertSorted) {
+            if (elem < (*fSetArray)[iMin]) {
+                *posToInsertSorted = iMin;
+            } else {
+                *posToInsertSorted = iMin + 1;
+            }
+        }
+
+        return -1;
+    }
 };
 
 #endif