Home | History | Annotate | Download | only in core 
      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 template <typename T>
     16 int SkTSearch(const T* base, int count, const T& target, size_t elemSize)
     17 {
     18     SkASSERT(count >= 0);
     19     if (count <= 0)
     20         return ~0;
     21 
     22     SkASSERT(base != NULL); // base may be NULL if count is zero
     23 
     24     int lo = 0;
     25     int hi = count - 1;
     26 
     27     while (lo < hi)
     28     {
     29         int mid = (hi + lo) >> 1;
     30         const T* elem = (const T*)((const char*)base + mid * elemSize);
     31 
     32         if (*elem < target)
     33             lo = mid + 1;
     34         else
     35             hi = mid;
     36     }
     37 
     38     const T* elem = (const T*)((const char*)base + hi * elemSize);
     39     if (*elem != target)
     40     {
     41         if (*elem < target)
     42             hi += 1;
     43         hi = ~hi;
     44     }
     45     return hi;
     46 }
     47 
     48 template <typename T>
     49 int SkTSearch(const T* base, int count, const T& target, size_t elemSize,
     50               int (*compare)(const T&, const T&))
     51 {
     52     SkASSERT(count >= 0);
     53     if (count <= 0) {
     54         return ~0;
     55     }
     56 
     57     SkASSERT(base != NULL); // base may be NULL if count is zero
     58 
     59     int lo = 0;
     60     int hi = count - 1;
     61 
     62     while (lo < hi) {
     63         int mid = (hi + lo) >> 1;
     64         const T* elem = (const T*)((const char*)base + mid * elemSize);
     65 
     66         if ((*compare)(*elem, target) < 0)
     67             lo = mid + 1;
     68         else
     69             hi = mid;
     70     }
     71 
     72     const T* elem = (const T*)((const char*)base + hi * elemSize);
     73     int pred = (*compare)(*elem, target);
     74     if (pred != 0) {
     75         if (pred < 0)
     76             hi += 1;
     77         hi = ~hi;
     78     }
     79     return hi;
     80 }
     81 
     82 template <typename T>
     83 int SkTSearch(const T** base, int count, const T* target, size_t elemSize,
     84     int (*compare)(const T*, const T*))
     85 {
     86     SkASSERT(count >= 0);
     87     if (count <= 0)
     88         return ~0;
     89 
     90     SkASSERT(base != NULL); // base may be NULL if count is zero
     91 
     92     int lo = 0;
     93     int hi = count - 1;
     94 
     95     while (lo < hi)
     96     {
     97         int mid = (hi + lo) >> 1;
     98         const T* elem = *(const T**)((const char*)base + mid * elemSize);
     99 
    100         if ((*compare)(elem, target) < 0)
    101             lo = mid + 1;
    102         else
    103             hi = mid;
    104     }
    105 
    106     const T* elem = *(const T**)((const char*)base + hi * elemSize);
    107     int pred = (*compare)(elem, target);
    108     if (pred != 0)
    109     {
    110         if (pred < 0)
    111             hi += 1;
    112         hi = ~hi;
    113     }
    114     return hi;
    115 }
    116 
    117 int SkStrSearch(const char*const* base, int count, const char target[],
    118                 size_t target_len, size_t elemSize);
    119 int SkStrSearch(const char*const* base, int count, const char target[],
    120                 size_t elemSize);
    121 
    122 /** Like SkStrSearch, but treats target as if it were all lower-case. Assumes that
    123     base points to a table of lower-case strings.
    124 */
    125 int SkStrLCSearch(const char*const* base, int count, const char target[],
    126                   size_t target_len, size_t elemSize);
    127 int SkStrLCSearch(const char*const* base, int count, const char target[],
    128                   size_t elemSize);
    129 
    130 /** Helper class to convert a string to lower-case, but only modifying the ascii
    131     characters. This makes the routine very fast and never changes the string
    132     length, but it is not suitable for linguistic purposes. Normally this is
    133     used for buiding and searching string tables.
    134 */
    135 class SkAutoAsciiToLC {
    136 public:
    137     SkAutoAsciiToLC(const char str[], size_t len = (size_t)-1);
    138     ~SkAutoAsciiToLC();
    139 
    140     const char* lc() const { return fLC; }
    141     size_t      length() const { return fLength; }
    142 
    143 private:
    144     char*   fLC;    // points to either the heap or fStorage
    145     size_t  fLength;
    146     enum {
    147         STORAGE = 64
    148     };
    149     char    fStorage[STORAGE+1];
    150 };
    151 
    152 extern "C" {
    153     typedef int (*SkQSortCompareProc)(const void*, const void*);
    154     void SkQSort(void* base, size_t count, size_t elemSize, SkQSortCompareProc);
    155 }
    156 
    157 #endif
    158 
    159