Home | History | Annotate | Download | only in private 
      1 
      2 /*
      3  * Copyright 2006 The Android Open Source Project
      4  *
      5  * Use of this source code is governed by a BSD-style license that can be
      6  * found in the LICENSE file.
      7  */
      8 
      9 
     10 #ifndef SkTSearch_DEFINED
     11 #define SkTSearch_DEFINED
     12 
     13 #include "SkTypes.h"
     14 
     15 /**
     16  *  All of the SkTSearch variants want to return the index (0...N-1) of the
     17  *  found element, or the bit-not of where to insert the element.
     18  *
     19  *  At a simple level, if the return value is negative, it was not found.
     20  *
     21  *  For clients that want to insert the new element if it was not found, use
     22  *  the following logic:
     23  *
     24  *  int index = SkTSearch(...);
     25  *  if (index >= 0) {
     26  *      // found at index
     27  *  } else {
     28  *      index = ~index; // now we are positive
     29  *      // insert at index
     30  *  }
     31  */
     32 
     33 
     34 // The most general form of SkTSearch takes an array of T and a key of type K. A functor, less, is
     35 // used to perform comparisons. It has two function operators:
     36 //      bool operator() (const T& t, const K& k)
     37 //      bool operator() (const K& t, const T& k)
     38 template <typename T, typename K, typename LESS>
     39 int SkTSearch(const T base[], int count, const K& key, size_t elemSize, LESS& less)
     40 {
     41     SkASSERT(count >= 0);
     42     if (count <= 0) {
     43         return ~0;
     44     }
     45 
     46     SkASSERT(base != NULL); // base may be NULL if count is zero
     47 
     48     int lo = 0;
     49     int hi = count - 1;
     50 
     51     while (lo < hi) {
     52         int mid = lo + ((hi - lo) >> 1);
     53         const T* elem = (const T*)((const char*)base + mid * elemSize);
     54 
     55         if (less(*elem, key))
     56             lo = mid + 1;
     57         else
     58             hi = mid;
     59     }
     60 
     61     const T* elem = (const T*)((const char*)base + hi * elemSize);
     62     if (less(*elem, key)) {
     63         hi += 1;
     64         hi = ~hi;
     65     } else if (less(key, *elem)) {
     66         hi = ~hi;
     67     }
     68     return hi;
     69 }
     70 
     71 // Adapts a less-than function to a functor.
     72 template <typename T, bool (LESS)(const T&, const T&)> struct SkTLessFunctionToFunctorAdaptor {
     73     bool operator()(const T& a, const T& b) { return LESS(a, b); }
     74 };
     75 
     76 // Specialization for case when T==K and the caller wants to use a function rather than functor.
     77 template <typename T, bool (LESS)(const T&, const T&)>
     78 int SkTSearch(const T base[], int count, const T& target, size_t elemSize) {
     79     static SkTLessFunctionToFunctorAdaptor<T, LESS> functor;
     80     return SkTSearch(base, count, target, elemSize, functor);
     81 }
     82 
     83 // Adapts operator < to a functor.
     84 template <typename T> struct SkTLessFunctor {
     85     bool operator()(const T& a, const T& b) { return a < b; }
     86 };
     87 
     88 // Specialization for T==K, compare using op <.
     89 template <typename T>
     90 int SkTSearch(const T base[], int count, const T& target, size_t elemSize) {
     91     static SkTLessFunctor<T> functor;
     92     return SkTSearch(base, count, target, elemSize, functor);
     93 }
     94 
     95 // Similar to SkLessFunctionToFunctorAdaptor but makes the functor interface take T* rather than T.
     96 template <typename T, bool (LESS)(const T&, const T&)> struct SkTLessFunctionToPtrFunctorAdaptor {
     97     bool operator() (const T* t, const T* k) { return LESS(*t, *k); }
     98 };
     99 
    100 // Specialization for case where domain is an array of T* and the key value is a T*, and you want
    101 // to compare the T objects, not the pointers.
    102 template <typename T, bool (LESS)(const T&, const T&)>
    103 int SkTSearch(T* base[], int count, T* target, size_t elemSize) {
    104     static SkTLessFunctionToPtrFunctorAdaptor<T, LESS> functor;
    105     return SkTSearch(base, count, target, elemSize, functor);
    106 }
    107 
    108 int SkStrSearch(const char*const* base, int count, const char target[],
    109                 size_t target_len, size_t elemSize);
    110 int SkStrSearch(const char*const* base, int count, const char target[],
    111                 size_t elemSize);
    112 
    113 /** Like SkStrSearch, but treats target as if it were all lower-case. Assumes that
    114     base points to a table of lower-case strings.
    115 */
    116 int SkStrLCSearch(const char*const* base, int count, const char target[],
    117                   size_t target_len, size_t elemSize);
    118 int SkStrLCSearch(const char*const* base, int count, const char target[],
    119                   size_t elemSize);
    120 
    121 /** Helper class to convert a string to lower-case, but only modifying the ascii
    122     characters. This makes the routine very fast and never changes the string
    123     length, but it is not suitable for linguistic purposes. Normally this is
    124     used for buiding and searching string tables.
    125 */
    126 class SkAutoAsciiToLC {
    127 public:
    128     SkAutoAsciiToLC(const char str[], size_t len = (size_t)-1);
    129     ~SkAutoAsciiToLC();
    130 
    131     const char* lc() const { return fLC; }
    132     size_t      length() const { return fLength; }
    133 
    134 private:
    135     char*   fLC;    // points to either the heap or fStorage
    136     size_t  fLength;
    137     enum {
    138         STORAGE = 64
    139     };
    140     char    fStorage[STORAGE+1];
    141 };
    142 
    143 // Helper when calling qsort with a compare proc that has typed its arguments
    144 #define SkCastForQSort(compare) reinterpret_cast<int (*)(const void*, const void*)>(compare)
    145 
    146 #endif
    147