Home | History | Annotate | Download | only in core 
      1 /* libs/graphics/sgl/SkTSearch.cpp
      2 **
      3 ** Copyright 2006, The Android Open Source Project
      4 **
      5 ** Licensed under the Apache License, Version 2.0 (the "License");
      6 ** you may not use this file except in compliance with the License.
      7 ** You may obtain a copy of the License at
      8 **
      9 **     http://www.apache.org/licenses/LICENSE-2.0
     10 **
     11 ** Unless required by applicable law or agreed to in writing, software
     12 ** distributed under the License is distributed on an "AS IS" BASIS,
     13 ** WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
     14 ** See the License for the specific language governing permissions and
     15 ** limitations under the License.
     16 */
     17 
     18 #include "SkTSearch.h"
     19 #include <ctype.h>
     20 
     21 static inline const char* index_into_base(const char*const* base, int index,
     22                                           size_t elemSize)
     23 {
     24     return *(const char*const*)((const char*)base + index * elemSize);
     25 }
     26 
     27 int SkStrSearch(const char*const* base, int count, const char target[],
     28                 size_t target_len, size_t elemSize)
     29 {
     30     if (count <= 0)
     31         return ~0;
     32 
     33     SkASSERT(base != NULL);
     34 
     35     int lo = 0;
     36     int hi = count - 1;
     37 
     38     while (lo < hi)
     39     {
     40         int mid = (hi + lo) >> 1;
     41         const char* elem = index_into_base(base, mid, elemSize);
     42 
     43         int cmp = strncmp(elem, target, target_len);
     44         if (cmp < 0)
     45             lo = mid + 1;
     46         else if (cmp > 0 || strlen(elem) > target_len)
     47             hi = mid;
     48         else
     49             return mid;
     50     }
     51 
     52     const char* elem = index_into_base(base, hi, elemSize);
     53     int cmp = strncmp(elem, target, target_len);
     54     if (cmp || strlen(elem) > target_len)
     55     {
     56         if (cmp < 0)
     57             hi += 1;
     58         hi = ~hi;
     59     }
     60     return hi;
     61 }
     62 
     63 int SkStrSearch(const char*const* base, int count, const char target[],
     64                 size_t elemSize)
     65 {
     66     return SkStrSearch(base, count, target, strlen(target), elemSize);
     67 }
     68 
     69 int SkStrLCSearch(const char*const* base, int count, const char target[],
     70                   size_t len, size_t elemSize)
     71 {
     72     SkASSERT(target);
     73 
     74     SkAutoAsciiToLC tolc(target, len);
     75 
     76     return SkStrSearch(base, count, tolc.lc(), len, elemSize);
     77 }
     78 
     79 int SkStrLCSearch(const char*const* base, int count, const char target[],
     80                   size_t elemSize)
     81 {
     82     return SkStrLCSearch(base, count, target, strlen(target), elemSize);
     83 }
     84 
     85 //////////////////////////////////////////////////////////////////////////////
     86 
     87 SkAutoAsciiToLC::SkAutoAsciiToLC(const char str[], size_t len)
     88 {
     89     // see if we need to compute the length
     90     if ((long)len < 0) {
     91         len = strlen(str);
     92     }
     93     fLength = len;
     94 
     95     // assign lc to our preallocated storage if len is small enough, or allocate
     96     // it on the heap
     97     char*   lc;
     98     if (len <= STORAGE) {
     99         lc = fStorage;
    100     } else {
    101         lc = (char*)sk_malloc_throw(len + 1);
    102     }
    103     fLC = lc;
    104 
    105     // convert any asii to lower-case. we let non-ascii (utf8) chars pass
    106     // through unchanged
    107     for (int i = (int)(len - 1); i >= 0; --i) {
    108         int c = str[i];
    109         if ((c & 0x80) == 0) {   // is just ascii
    110             c = tolower(c);
    111         }
    112         lc[i] = c;
    113     }
    114     lc[len] = 0;
    115 }
    116 
    117 SkAutoAsciiToLC::~SkAutoAsciiToLC()
    118 {
    119     if (fLC != fStorage) {
    120         sk_free(fLC);
    121     }
    122 }
    123 
    124 //////////////////////////////////////////////////////////////////////////////
    125 
    126 #define SK_QSortTempSize    16
    127 
    128 static inline void sk_qsort_swap(char a[], char b[], size_t elemSize)
    129 {
    130     char    tmp[SK_QSortTempSize];
    131 
    132     while (elemSize > 0)
    133     {
    134         size_t size = elemSize;
    135         if (size > SK_QSortTempSize)
    136             size = SK_QSortTempSize;
    137         elemSize -= size;
    138 
    139         memcpy(tmp, a, size);
    140         memcpy(a, b, size);
    141         memcpy(b, tmp, size);
    142         a += size;
    143         b += size;
    144     }
    145 }
    146 
    147 static void SkQSort_Partition(char* first, char* last, size_t elemSize, SkQSortCompareProc compare)
    148 {
    149     char*   left = first;
    150     char*   rite = last;
    151     char*   pivot = left;
    152 
    153     while (left <= rite)
    154     {
    155         while (left < last && compare(left, pivot) < 0)
    156             left += elemSize;
    157         while (first < rite && compare(rite, pivot) > 0)
    158             rite -= elemSize;
    159         if (left <= rite)
    160         {
    161             if (left < rite)
    162             {
    163                 SkASSERT(compare(left, rite) >= 0);
    164                 sk_qsort_swap(left, rite, elemSize);
    165             }
    166             left += elemSize;
    167             rite -= elemSize;
    168         }
    169     }
    170     if (first < rite)
    171         SkQSort_Partition(first, rite, elemSize, compare);
    172     if (left < last)
    173         SkQSort_Partition(left, last, elemSize, compare);
    174 }
    175 
    176 void SkQSort(void* base, size_t count, size_t elemSize, SkQSortCompareProc compare)
    177 {
    178     SkASSERT(base);
    179     SkASSERT(compare);
    180     SkASSERT(elemSize > 0);
    181 
    182     if (count <= 1)
    183         return;
    184 
    185     SkQSort_Partition((char*)base, (char*)base + (count - 1) * elemSize, elemSize, compare);
    186 }
    187 
    188