Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(1176)

Unified Diff: src/pdf/SkTSet.h

Issue 19283005: Deterministic SkTSet and PDF Output (Closed) Base URL: https://skia.googlecode.com/svn/trunk
Patch Set: Add sorting for testing in SkTSet::validate() and some code review fixes Created 7 years, 5 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View side-by-side diff with in-line comments
Download patch
« no previous file with comments | « no previous file | tests/TSetTest.cpp » ('j') | no next file with comments »
Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
Index: src/pdf/SkTSet.h
diff --git a/src/pdf/SkTSet.h b/src/pdf/SkTSet.h
index 8d5bbb6897e3b94249a63c7e99379fcaf33bb0f1..c2d2785f0fa27be6b5fd22378754ec439b542739 100644
--- a/src/pdf/SkTSet.h
+++ b/src/pdf/SkTSet.h
@@ -8,12 +8,14 @@
#ifndef SkTSet_DEFINED
#define SkTSet_DEFINED
+#include "SkTSort.h"
#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.
@@ -24,23 +26,28 @@
template <typename T> class SkTSet {
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
@@ -48,23 +55,39 @@ public:
}
/** 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++;
@@ -72,17 +95,17 @@ public:
}
}
- 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
@@ -91,18 +114,20 @@ public:
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
@@ -112,150 +137,130 @@ public:
/** Returns true if this set is empty.
*/
bool isEmpty() const {
- SkASSERT(fArray);
- return fArray->isEmpty();
+ SkASSERT(fOrderedArray);
+ SkASSERT(fSetArray);
+ SkASSERT(fSetArray->isEmpty() == fOrderedArray->isEmpty());
+ return fOrderedArray->isEmpty();
}
/** Return the number of elements in the set.
*/
int count() const {
- SkASSERT(fArray);
- return fArray->count();
+ SkASSERT(fOrderedArray);
+ SkASSERT(fSetArray);
+ SkASSERT(fSetArray->count() == fOrderedArray->count());
+ return fOrderedArray->count();
}
/** Return the number of bytes in the set: count * sizeof(T).
*/
size_t bytes() const {
edisonn 2013/07/17 20:03:28 if this function is not used anywhere, please remo
- SkASSERT(fArray);
- return fArray->bytes();
+ SkASSERT(fOrderedArray);
+ 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(dst, 0, fOrderedArray->count());
}
/** 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();
+ // Also reset the other array, as SkTDArray::unrefAll does an
+ // implcit reset
+ fSetArray->reset();
}
/** safeUnref all elements in the set.
*/
- void safeUnrefAll() {
- SkASSERT(fArray);
- fArray->safeUnrefAll();
+ void safeUnrefAll() {
+ SkASSERT(fSetArray);
+ SkASSERT(fOrderedArray);
+ fOrderedArray->safeUnrefAll();
+ // Also reset the other array, as SkTDArray::safeUnrefAll does an
+ // implcit reset
+ fSetArray->reset();
}
#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;
}
}
@@ -263,18 +268,89 @@ public:
}
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 {
+ if (fSetArray->count() != fOrderedArray->count()) {
+ return false;
+ }
+ if (fOrderedArray->count() == 0) {
+ return true;
+ }
+
+ // Copy and sort fOrderedArray, then compare to fSetArray.
+ // A O(n log n) algorithm is necessary as O(n^2) will choke some GMs.
+ SkAutoMalloc sortedArray(fOrderedArray->bytes());
+ T* sortedBase = reinterpret_cast<T*>(sortedArray.get());
+ size_t count = fOrderedArray->count();
+ fOrderedArray->copyRange(sortedBase, 0, count);
+
+ SkTQSort<T>(sortedBase, sortedBase + count - 1);
+
+ for (size_t i = 0; i < count; ++i) {
+ if (sortedBase[i] != (*fSetArray)[i]) {
return false;
}
}
+
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
« no previous file with comments | « no previous file | tests/TSetTest.cpp » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698