One SkTSearch to rule them all. Allow key to be of different type than the array.
R=bungeman@google.com
Review URL: https://codereview.chromium.org/15070011
git-svn-id: http://skia.googlecode.com/svn/trunk@9182 2bbb7eff-a529-9590-31e7-b0007b416f81
diff --git a/src/core/SkBitmapHeap.cpp b/src/core/SkBitmapHeap.cpp
index 48194b1..f3428db 100644
--- a/src/core/SkBitmapHeap.cpp
+++ b/src/core/SkBitmapHeap.cpp
@@ -38,26 +38,24 @@
///////////////////////////////////////////////////////////////////////////////
-int SkBitmapHeap::LookupEntry::Compare(const SkBitmapHeap::LookupEntry *a,
- const SkBitmapHeap::LookupEntry *b) {
- if (a->fGenerationId < b->fGenerationId) {
- return -1;
- } else if (a->fGenerationId > b->fGenerationId) {
- return 1;
- } else if (a->fPixelOffset < b->fPixelOffset) {
- return -1;
- } else if (a->fPixelOffset > b->fPixelOffset) {
- return 1;
- } else if (a->fWidth < b->fWidth) {
- return -1;
- } else if (a->fWidth > b->fWidth) {
- return 1;
- } else if (a->fHeight < b->fHeight) {
- return -1;
- } else if (a->fHeight > b->fHeight) {
- return 1;
+bool SkBitmapHeap::LookupEntry::Less(const SkBitmapHeap::LookupEntry& a,
+ const SkBitmapHeap::LookupEntry& b) {
+ if (a.fGenerationId < b.fGenerationId) {
+ return true;
+ } else if (a.fGenerationId > b.fGenerationId) {
+ return false;
+ } else if (a.fPixelOffset < b.fPixelOffset) {
+ return true;
+ } else if (a.fPixelOffset > b.fPixelOffset) {
+ return false;
+ } else if (a.fWidth < b.fWidth) {
+ return true;
+ } else if (a.fWidth > b.fWidth) {
+ return false;
+ } else if (a.fHeight < b.fHeight) {
+ return true;
}
- return 0;
+ return false;
}
///////////////////////////////////////////////////////////////////////////////
@@ -231,9 +229,10 @@
}
int SkBitmapHeap::findInLookupTable(const LookupEntry& indexEntry, SkBitmapHeapEntry** entry) {
- int index = SkTSearch<const LookupEntry>((const LookupEntry**)fLookupTable.begin(),
+ int index = SkTSearch<const LookupEntry, LookupEntry::Less>(
+ (const LookupEntry**)fLookupTable.begin(),
fLookupTable.count(),
- &indexEntry, sizeof(void*), LookupEntry::Compare);
+ &indexEntry, sizeof(void*));
if (index < 0) {
// insert ourselves into the bitmapIndex
diff --git a/src/core/SkBitmapHeap.h b/src/core/SkBitmapHeap.h
index be99e19..2547eee 100644
--- a/src/core/SkBitmapHeap.h
+++ b/src/core/SkBitmapHeap.h
@@ -238,9 +238,9 @@
uint32_t fStorageSlot; // slot of corresponding bitmap in fStorage.
/**
- * Compare two LookupEntry pointers, returning -1, 0, 1 for sorting.
+ * Compare two LookupEntry pointers for sorting and searching.
*/
- static int Compare(const LookupEntry* a, const LookupEntry* b);
+ static bool Less(const LookupEntry& a, const LookupEntry& b);
};
/**
diff --git a/src/core/SkPathMeasure.cpp b/src/core/SkPathMeasure.cpp
index c97c826..af2579f 100644
--- a/src/core/SkPathMeasure.cpp
+++ b/src/core/SkPathMeasure.cpp
@@ -389,8 +389,7 @@
const Segment* seg = fSegments.begin();
int count = fSegments.count();
- int index = SkTSearch<SkScalar>(&seg->fDistance, count, distance,
- sizeof(Segment));
+ int index = SkTSearch<SkScalar>(&seg->fDistance, count, distance, sizeof(Segment));
// don't care if we hit an exact match or not, so we xor index if it is negative
index ^= (index >> 31);
seg = &seg[index];
diff --git a/src/core/SkPictureFlat.h b/src/core/SkPictureFlat.h
index b0446bb..b513271 100644
--- a/src/core/SkPictureFlat.h
+++ b/src/core/SkPictureFlat.h
@@ -277,22 +277,27 @@
* 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;
+ 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);
+ SkASSERT(b.dataStop() == b_ptr);
return 0;
}
- SkASSERT(a_ptr < a->dataStop());
- SkASSERT(b_ptr < b->dataStop());
+ 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); }
@@ -528,14 +533,14 @@
int hashIndex = ChecksumToHashIndex(flat->checksum());
const SkFlatData* candidate = fHash[hashIndex];
- if (candidate && !SkFlatData::Compare(flat, candidate)) {
+ if (candidate && !SkFlatData::Compare(*flat, *candidate)) {
fController->unalloc(flat);
return candidate;
}
- int index = SkTSearch<SkFlatData>((const SkFlatData**) fSortedData.begin(),
- fSortedData.count(), flat, sizeof(flat),
- &SkFlatData::Compare);
+ int index = SkTSearch<const SkFlatData,
+ SkFlatData::Less>((const SkFlatData**) fSortedData.begin(),
+ fSortedData.count(), flat, sizeof(flat));
if (index >= 0) {
fController->unalloc(flat);
fHash[hashIndex] = fSortedData[index];
diff --git a/src/core/SkPtrRecorder.cpp b/src/core/SkPtrRecorder.cpp
index d473cab..2acb5af 100644
--- a/src/core/SkPtrRecorder.cpp
+++ b/src/core/SkPtrRecorder.cpp
@@ -21,8 +21,8 @@
fList.reset();
}
-int SkPtrSet::Cmp(const Pair* a, const Pair* b) {
- return (char*)a->fPtr - (char*)b->fPtr;
+bool SkPtrSet::Less(const Pair& a, const Pair& b) {
+ return (char*)a.fPtr < (char*)b.fPtr;
}
uint32_t SkPtrSet::find(void* ptr) const {
@@ -34,7 +34,7 @@
Pair pair;
pair.fPtr = ptr;
- int index = SkTSearch<Pair, Cmp>(fList.begin(), count, pair, sizeof(pair));
+ int index = SkTSearch<Pair, Less>(fList.begin(), count, pair, sizeof(pair));
if (index < 0) {
return 0;
}
@@ -50,7 +50,7 @@
Pair pair;
pair.fPtr = ptr;
- int index = SkTSearch<Pair, Cmp>(fList.begin(), count, pair, sizeof(pair));
+ int index = SkTSearch<Pair, Less>(fList.begin(), count, pair, sizeof(pair));
if (index < 0) {
index = ~index; // turn it back into an index for insertion
this->incPtr(ptr);
diff --git a/src/core/SkPtrRecorder.h b/src/core/SkPtrRecorder.h
index 0e7ac66..06e14ab 100644
--- a/src/core/SkPtrRecorder.h
+++ b/src/core/SkPtrRecorder.h
@@ -74,7 +74,7 @@
// is not related to its "index".
SkTDArray<Pair> fList;
- static int Cmp(const Pair* a, const Pair* b);
+ static bool Less(const Pair& a, const Pair& b);
typedef SkRefCnt INHERITED;
};
diff --git a/src/core/SkTSort.h b/src/core/SkTSort.h
index a5865a2..027ea52 100644
--- a/src/core/SkTSort.h
+++ b/src/core/SkTSort.h
@@ -207,14 +207,4 @@
SkTQSort(left, right, SkTPointerCompareLT<T>());
}
-/** Adapts a tri-state SkTSearch comparison function to a bool less-than SkTSort functor */
-template <typename T, int (COMPARE)(const T*, const T*)>
-class SkTSearchCompareLTFunctor {
-public:
- bool operator()(const T& a, const T& b) {
- return COMPARE(&a, &b) < 0;
- }
-};
-
-
#endif
diff --git a/src/gpu/effects/GrTextureStripAtlas.cpp b/src/gpu/effects/GrTextureStripAtlas.cpp
index f726b25..8e9e155 100644
--- a/src/gpu/effects/GrTextureStripAtlas.cpp
+++ b/src/gpu/effects/GrTextureStripAtlas.cpp
@@ -273,11 +273,12 @@
int GrTextureStripAtlas::searchByKey(uint32_t key) {
AtlasRow target;
target.fKey = key;
- return SkTSearch<AtlasRow, GrTextureStripAtlas::compareKeys>((const AtlasRow**)fKeyTable.begin(),
- fKeyTable.count(),
- &target,
- sizeof(AtlasRow*));
-}
+ return SkTSearch<const AtlasRow,
+ GrTextureStripAtlas::KeyLess>((const AtlasRow**)fKeyTable.begin(),
+ fKeyTable.count(),
+ &target,
+ sizeof(AtlasRow*));
+}
#ifdef SK_DEBUG
void GrTextureStripAtlas::validate() {
diff --git a/src/gpu/effects/GrTextureStripAtlas.h b/src/gpu/effects/GrTextureStripAtlas.h
index 9ac356b..0148665 100644
--- a/src/gpu/effects/GrTextureStripAtlas.h
+++ b/src/gpu/effects/GrTextureStripAtlas.h
@@ -120,8 +120,8 @@
/**
* Compare two atlas rows by key, so we can sort/search by key
*/
- static int compareKeys(const AtlasRow* lhs, const AtlasRow* rhs) {
- return lhs->fKey - rhs->fKey;
+ static bool KeyLess(const AtlasRow& lhs, const AtlasRow& rhs) {
+ return lhs.fKey < rhs.fKey;
}
#ifdef SK_DEBUG
diff --git a/src/gpu/gl/GrGLCaps.cpp b/src/gpu/gl/GrGLCaps.cpp
index 5568c48..8b296e3 100644
--- a/src/gpu/gl/GrGLCaps.cpp
+++ b/src/gpu/gl/GrGLCaps.cpp
@@ -9,6 +9,7 @@
#include "GrGLCaps.h"
#include "GrGLContext.h"
#include "SkTSearch.h"
+#include "SkTSort.h"
SK_DEFINE_INST_COUNT(GrGLCaps)
@@ -335,18 +336,16 @@
}
namespace {
-int coverage_mode_compare(const GrGLCaps::MSAACoverageMode* left,
- const GrGLCaps::MSAACoverageMode* right) {
- if (left->fCoverageSampleCnt < right->fCoverageSampleCnt) {
- return -1;
- } else if (right->fCoverageSampleCnt < left->fCoverageSampleCnt) {
- return 1;
- } else if (left->fColorSampleCnt < right->fColorSampleCnt) {
- return -1;
- } else if (right->fColorSampleCnt < left->fColorSampleCnt) {
- return 1;
+bool cov_mode_less(const GrGLCaps::MSAACoverageMode& left,
+ const GrGLCaps::MSAACoverageMode& right) {
+ if (left.fCoverageSampleCnt < right.fCoverageSampleCnt) {
+ return true;
+ } else if (right.fCoverageSampleCnt < left.fCoverageSampleCnt) {
+ return false;
+ } else if (left.fColorSampleCnt < right.fColorSampleCnt) {
+ return true;
}
- return 0;
+ return false;
}
}
@@ -389,10 +388,11 @@
(int*)&fMSAACoverageModes[0]);
// The NV driver seems to return the modes already sorted but the
// spec doesn't require this. So we sort.
- qsort(&fMSAACoverageModes[0],
- count,
- sizeof(MSAACoverageMode),
- SkCastForQSort(coverage_mode_compare));
+ typedef SkTLessFunctionToFunctorAdaptor<MSAACoverageMode, cov_mode_less> SortFunctor;
+ SortFunctor sortFunctor;
+ SkTQSort<MSAACoverageMode, SortFunctor>(fMSAACoverageModes.begin(),
+ fMSAACoverageModes.end() - 1,
+ sortFunctor);
}
}
}
@@ -406,11 +406,10 @@
int max = (fMSAACoverageModes.end() - 1)->fCoverageSampleCnt;
desiredSampleCount = GrMin(desiredSampleCount, max);
MSAACoverageMode desiredMode = {desiredSampleCount, 0};
- int idx = SkTSearch<MSAACoverageMode>(&fMSAACoverageModes[0],
- fMSAACoverageModes.count(),
- desiredMode,
- sizeof(MSAACoverageMode),
- &coverage_mode_compare);
+ int idx = SkTSearch<const MSAACoverageMode, cov_mode_less>(&fMSAACoverageModes[0],
+ fMSAACoverageModes.count(),
+ desiredMode,
+ sizeof(MSAACoverageMode));
if (idx < 0) {
idx = ~idx;
}
diff --git a/src/gpu/gl/GrGLExtensions.cpp b/src/gpu/gl/GrGLExtensions.cpp
index a071923..633796d 100644
--- a/src/gpu/gl/GrGLExtensions.cpp
+++ b/src/gpu/gl/GrGLExtensions.cpp
@@ -13,8 +13,8 @@
#include "SkTSort.h"
namespace {
-inline int extension_compare(const SkString* a, const SkString* b) {
- return strcmp(a->c_str(), b->c_str());
+inline bool extension_compare(const SkString& a, const SkString& b) {
+ return strcmp(a.c_str(), b.c_str()) < 0;
}
}
@@ -67,7 +67,7 @@
}
}
if (0 != fStrings.count()) {
- SkTSearchCompareLTFunctor<SkString, extension_compare> cmp;
+ SkTLessFunctionToFunctorAdaptor<SkString, extension_compare> cmp;
SkTQSort(&fStrings.front(), &fStrings.back(), cmp);
}
return true;
diff --git a/src/sfnt/SkOTTable_name.cpp b/src/sfnt/SkOTTable_name.cpp
index 0b309cd..769a424 100644
--- a/src/sfnt/SkOTTable_name.cpp
+++ b/src/sfnt/SkOTTable_name.cpp
@@ -431,8 +431,8 @@
};
namespace {
-int BCP47FromLanguageIdCompare(const BCP47FromLanguageId* a, const BCP47FromLanguageId* b) {
- return a->languageID - b->languageID;
+bool BCP47FromLanguageIdLess(const BCP47FromLanguageId& a, const BCP47FromLanguageId& b) {
+ return a.languageID < b.languageID;
}
}
@@ -509,7 +509,7 @@
// Handle format 0 languages, translating them into BCP 47.
const BCP47FromLanguageId target = { languageID, "" };
- int languageIndex = SkTSearch<BCP47FromLanguageId, BCP47FromLanguageIdCompare>(
+ int languageIndex = SkTSearch<BCP47FromLanguageId, BCP47FromLanguageIdLess>(
BCP47FromLanguageID, SK_ARRAY_COUNT(BCP47FromLanguageID), target, sizeof(target));
if (languageIndex >= 0) {
record.language = BCP47FromLanguageID[languageIndex].bcp47;
diff --git a/src/utils/win/SkWGL_win.cpp b/src/utils/win/SkWGL_win.cpp
index dabe136..f20262b 100644
--- a/src/utils/win/SkWGL_win.cpp
+++ b/src/utils/win/SkWGL_win.cpp
@@ -10,6 +10,7 @@
#include "SkTDArray.h"
#include "SkTSearch.h"
+#include "SkTSort.h"
bool SkWGLExtensions::hasExtension(HDC dc, const char* ext) const {
if (NULL == this->fGetExtensionsString) {
@@ -83,21 +84,19 @@
int fChoosePixelFormatRank;
};
-int compare_pf(const PixelFormat* a, const PixelFormat* b) {
- if (a->fCoverageSamples < b->fCoverageSamples) {
- return -1;
- } else if (b->fCoverageSamples < a->fCoverageSamples) {
- return 1;
- } else if (a->fColorSamples < b->fColorSamples) {
- return -1;
- } else if (b->fColorSamples < a->fColorSamples) {
- return 1;
- } else if (a->fChoosePixelFormatRank < b->fChoosePixelFormatRank) {
- return -1;
- } else if (b->fChoosePixelFormatRank < a->fChoosePixelFormatRank) {
- return 1;
+bool pf_less(const PixelFormat& a, const PixelFormat& b) {
+ if (a.fCoverageSamples < b.fCoverageSamples) {
+ return true;
+ } else if (b.fCoverageSamples < a.fCoverageSamples) {
+ return false;
+ } else if (a.fColorSamples < b.fColorSamples) {
+ return true;
+ } else if (b.fColorSamples < a.fColorSamples) {
+ return false;
+ } else if (a.fChoosePixelFormatRank < b.fChoosePixelFormatRank) {
+ return true;
}
- return 0;
+ return false;
}
}
@@ -136,15 +135,13 @@
rankedFormats[i].fColorSamples = answers[supportsCoverage ? 1 : 0];
rankedFormats[i].fChoosePixelFormatRank = i;
}
- qsort(rankedFormats.begin(),
- rankedFormats.count(),
- sizeof(PixelFormat),
- SkCastForQSort(compare_pf));
- int idx = SkTSearch<PixelFormat>(rankedFormats.begin(),
- rankedFormats.count(),
- desiredFormat,
- sizeof(PixelFormat),
- compare_pf);
+ SkTQSort(rankedFormats.begin(),
+ rankedFormats.begin() + rankedFormats.count() - 1,
+ SkTLessFunctionToFunctorAdaptor<PixelFormat, pf_less>());
+ int idx = SkTSearch<PixelFormat, pf_less>(rankedFormats.begin(),
+ rankedFormats.count(),
+ desiredFormat,
+ sizeof(PixelFormat));
if (idx < 0) {
idx = ~idx;
}