One SkTSearch to rule them all. Allow key to be of different type than the array.

include/core/SkTSearch.h

 
 /*
  * Copyright 2006 The Android Open Source Project
  *
  * Use of this source code is governed by a BSD-style license that can be
  * found in the LICENSE file.
  */
 
 
 #ifndef SkTSearch_DEFINED
@@ skipping 12 matching lines @@
  *
  *  int index = SkTSearch(...);
  *  if (index >= 0) {
  *      // found at index
  *  } else {
  *      index = ~index; // now we are positive
  *      // insert at index
  *  }
  */
 
-template <typename T>
-int SkTSearch(const T* base, int count, const T& target, size_t elemSize)
-{
-    SkASSERT(count >= 0);
-    if (count <= 0)
-        return ~0;
 
-    SkASSERT(base != NULL); // base may be NULL if count is zero
-
-    int lo = 0;
-    int hi = count - 1;
-
-    while (lo < hi)
-    {
-        int mid = (hi + lo) >> 1;
-        const T* elem = (const T*)((const char*)base + mid * elemSize);
-
-        if (*elem < target)
-            lo = mid + 1;
-        else
-            hi = mid;
-    }
-
-    const T* elem = (const T*)((const char*)base + hi * elemSize);
-    if (*elem != target)
-    {
-        if (*elem < target)
-            hi += 1;
-        hi = ~hi;
-    }
-    return hi;
-}
-
-template <typename T, int (COMPARE)(const T*, const T*)>
-int SkTSearch(const T* base, int count, const T& target, size_t elemSize)
+// The most general form of SkTSearch takes an array of T and a key of type K. A functor, less, is
+// used to perform comparisons. It has two function operators:
+//      bool operator() (const T& t, const K& k)
+//      bool operator() (const K& t, const T& k)
+template <typename T, typename K, typename LESS>
+int SkTSearch(const T base[], int count, const K& key, size_t elemSize, LESS& less)
 {
     SkASSERT(count >= 0);
     if (count <= 0) {
         return ~0;
     }
 
     SkASSERT(base != NULL); // base may be NULL if count is zero
 
     int lo = 0;
     int hi = count - 1;
 
     while (lo < hi) {
         int mid = (hi + lo) >> 1;
         const T* elem = (const T*)((const char*)base + mid * elemSize);
 
-        if (COMPARE(elem, &target) < 0)
+        if (less(*elem, key))
             lo = mid + 1;
         else
             hi = mid;
     }
 
     const T* elem = (const T*)((const char*)base + hi * elemSize);
-    int pred = COMPARE(elem, &target);
-    if (pred != 0) {
-        if (pred < 0)
-            hi += 1;
+    if (less(*elem, key)) {
+        hi += 1;
+        hi = ~hi;
+    } else if (less(key, *elem)) {
         hi = ~hi;
     }
     return hi;
 }
 
-template <typename T>
-int SkTSearch(const T* base, int count, const T& target, size_t elemSize,
-              int (*compare)(const T*, const T*))
-{
-    SkASSERT(count >= 0);
-    if (count <= 0) {
-        return ~0;
-    }
+// Adapts a less-than function to a functor.
+template <typename T, bool (LESS)(const T&, const T&)>
+class SkTLessFunctionToFunctorAdaptor {

[bungeman-skia, 2013/05/16 22:00:39]

If this were a struct there would be no need for the 'public' on the next line.

[bsalomon, 2013/05/17 14:24:30]

Done.

+public:
+    bool operator()(const T& a, const T& b) { return LESS(a, b); }
+};
 
-    SkASSERT(base != NULL); // base may be NULL if count is zero
-
-    int lo = 0;
-    int hi = count - 1;
-
-    while (lo < hi) {
-        int mid = (hi + lo) >> 1;
-        const T* elem = (const T*)((const char*)base + mid * elemSize);
-
-        if ((*compare)(elem, &target) < 0)
-            lo = mid + 1;
-        else
-            hi = mid;
-    }
-
-    const T* elem = (const T*)((const char*)base + hi * elemSize);
-    int pred = (*compare)(elem, &target);
-    if (pred != 0) {
-        if (pred < 0)
-            hi += 1;
-        hi = ~hi;
-    }
-    return hi;
+// Specialization for case when T==K and the caller wants to use a function rather than functor.
+template <typename T, bool (LESS)(const T&, const T&)>
+int SkTSearch(const T base[], int count, const T& target, size_t elemSize) {
+    typedef SkTLessFunctionToFunctorAdaptor<T, LESS> Functor;
+    Functor functor;
+    return SkTSearch<T, T, Functor>(base, count, target, elemSize, functor);

[bungeman-skia, 2013/05/16 22:00:39]

I think this can just be

return SkTSearch(base, count, target, elemSize, Functor());

and the previous line removed. All of the function template parameters should be
inferred.

Actually the line

return SkTSearch(base, count, target, elemSize,
SkTLessFunctionToFunctorAdaptor<T, LESS>());

appears to be 97 characters (after adding the four leading spaces). This allows
this function to be one line.

[bsalomon, 2013/05/17 14:24:30]

Done.

 }
 
+// Adapts operator < to a functor.
+template <typename T> struct SkTLessFunctor {
+public:

[bungeman-skia, 2013/05/16 22:00:39]

nit: This is a struct, so public is already implied.

[bsalomon, 2013/05/17 14:24:30]

Done.

+    bool operator()(const T& a, const T& b) { return a < b; }
+};
+
+// Specialization for T==K, compare using op <.
 template <typename T>
-int SkTSearch(const T** base, int count, const T* target, size_t elemSize,
-    int (*compare)(const T*, const T*))
-{
-    SkASSERT(count >= 0);
-    if (count <= 0)
-        return ~0;
-
-    SkASSERT(base != NULL); // base may be NULL if count is zero
-
-    int lo = 0;
-    int hi = count - 1;
-
-    while (lo < hi)
-    {
-        int mid = (hi + lo) >> 1;
-        const T* elem = *(const T**)((const char*)base + mid * elemSize);
-
-        if ((*compare)(elem, target) < 0)
-            lo = mid + 1;
-        else
-            hi = mid;
-    }
-
-    const T* elem = *(const T**)((const char*)base + hi * elemSize);
-    int pred = (*compare)(elem, target);
-    if (pred != 0)
-    {
-        if (pred < 0)
-            hi += 1;
-        hi = ~hi;
-    }
-    return hi;
+int SkTSearch(const T base[], int count, const T& target, size_t elemSize) {
+    SkTLessFunctor<T> functor;
+    return SkTSearch<T, T, SkTLessFunctor<T> >(base, count, target, elemSize, functor);

[bungeman-skia, 2013/05/16 22:00:39]

This line can probably be

return SkTSearch(base, count, target, elemSize, SkTLessFunctor<T>());

and the previous line removed.

I wonder if this helps with the 'const' issues, since the compiler will be the
one figuring out the types.

[bsalomon, 2013/05/17 14:24:30]

Done. I'll leave fighting the const battle for another day ( or at least another
changelist).

 }
 
-template <typename T,  int (COMPARE)(const T*, const T*)>
-int SkTSearch(const T** base, int count, const T* target, size_t elemSize)
-{
-    SkASSERT(count >= 0);
-    if (count <= 0)
-        return ~0;
+// Similar to SkLessFunctionToFunctorAdaptor but makes the functor interface take T* rather than T.
+template <typename T, bool (LESS)(const T&, const T&)>
+class SkTLessFunctionToPtrFunctorAdaptor {

[bungeman-skia, 2013/05/16 22:00:39]

If this were a struct there would be no need for the 'public' on the next line.

[bsalomon, 2013/05/17 14:24:30]

Done.

+public:
+    bool operator() (const T* t, const T* k) { return LESS(*t, *k); }
+};
 
-    SkASSERT(base != NULL); // base may be NULL if count is zero
+// Specialization for case where domain is an array of T* and the key value is a T*, and you want
+// to compare the T objects, not the pointers.
+template <typename T, bool (LESS)(const T&, const T&)>
+int SkTSearch(T* base[], int count, T* target, size_t elemSize) {
+    typedef SkTLessFunctionToPtrFunctorAdaptor<T, LESS> Functor;
+    Functor functor;
+    return SkTSearch<T*, T*, Functor>(base, count, target, elemSize, functor);

[bungeman-skia, 2013/05/16 22:00:39]

Likewise, this line can probably be

return SkTSearch(base, count, target, elemSize,
SkTLessFunctionToPtrFunctorAdaptor<T, LESS>());

for a single line (exactly 100 columns with the four leading spaces).

[bsalomon, 2013/05/17 14:24:30]

Actually only 99!

+}
 
-    int lo = 0;
-    int hi = count - 1;
-
-    while (lo < hi)
-    {
-        int mid = (hi + lo) >> 1;
-        const T* elem = *(const T**)((const char*)base + mid * elemSize);
-
-        if (COMPARE(elem, target) < 0)
-            lo = mid + 1;
-        else
-            hi = mid;
-    }
-
-    const T* elem = *(const T**)((const char*)base + hi * elemSize);
-    int pred = COMPARE(elem, target);
-    if (pred != 0)
-    {
-        if (pred < 0)
-            hi += 1;
-        hi = ~hi;
-    }
-    return hi;
-}
 int SkStrSearch(const char*const* base, int count, const char target[],
                 size_t target_len, size_t elemSize);
 int SkStrSearch(const char*const* base, int count, const char target[],
                 size_t elemSize);
 
 /** Like SkStrSearch, but treats target as if it were all lower-case. Assumes that
     base points to a table of lower-case strings.
 */
 int SkStrLCSearch(const char*const* base, int count, const char target[],
                   size_t target_len, size_t elemSize);
@@ skipping 19 matching lines @@
     enum {
         STORAGE = 64
     };
     char    fStorage[STORAGE+1];
 };
 
 // Helper when calling qsort with a compare proc that has typed its arguments
 #define SkCastForQSort(compare) reinterpret_cast<int (*)(const void*, const void*)>(compare)
 
 #endif