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 #include "SkTSearch.h"
     11 #include <ctype.h>
     12 
     13 static inline const char* index_into_base(const char*const* base, int index,
     14                                           size_t elemSize)
     15 {
     16     return *(const char*const*)((const char*)base + index * elemSize);
     17 }
     18 
     19 int SkStrSearch(const char*const* base, int count, const char target[],
     20                 size_t target_len, size_t elemSize)
     21 {
     22     if (count <= 0)
     23         return ~0;
     24 
     25     SkASSERT(base != NULL);
     26 
     27     int lo = 0;
     28     int hi = count - 1;
     29 
     30     while (lo < hi)
     31     {
     32         int mid = (hi + lo) >> 1;
     33         const char* elem = index_into_base(base, mid, elemSize);
     34 
     35         int cmp = strncmp(elem, target, target_len);
     36         if (cmp < 0)
     37             lo = mid + 1;
     38         else if (cmp > 0 || strlen(elem) > target_len)
     39             hi = mid;
     40         else
     41             return mid;
     42     }
     43 
     44     const char* elem = index_into_base(base, hi, elemSize);
     45     int cmp = strncmp(elem, target, target_len);
     46     if (cmp || strlen(elem) > target_len)
     47     {
     48         if (cmp < 0)
     49             hi += 1;
     50         hi = ~hi;
     51     }
     52     return hi;
     53 }
     54 
     55 int SkStrSearch(const char*const* base, int count, const char target[],
     56                 size_t elemSize)
     57 {
     58     return SkStrSearch(base, count, target, strlen(target), elemSize);
     59 }
     60 
     61 int SkStrLCSearch(const char*const* base, int count, const char target[],
     62                   size_t len, size_t elemSize)
     63 {
     64     SkASSERT(target);
     65 
     66     SkAutoAsciiToLC tolc(target, len);
     67 
     68     return SkStrSearch(base, count, tolc.lc(), len, elemSize);
     69 }
     70 
     71 int SkStrLCSearch(const char*const* base, int count, const char target[],
     72                   size_t elemSize)
     73 {
     74     return SkStrLCSearch(base, count, target, strlen(target), elemSize);
     75 }
     76 
     77 //////////////////////////////////////////////////////////////////////////////
     78 
     79 SkAutoAsciiToLC::SkAutoAsciiToLC(const char str[], size_t len)
     80 {
     81     // see if we need to compute the length
     82     if ((long)len < 0) {
     83         len = strlen(str);
     84     }
     85     fLength = len;
     86 
     87     // assign lc to our preallocated storage if len is small enough, or allocate
     88     // it on the heap
     89     char*   lc;
     90     if (len <= STORAGE) {
     91         lc = fStorage;
     92     } else {
     93         lc = (char*)sk_malloc_throw(len + 1);
     94     }
     95     fLC = lc;
     96 
     97     // convert any asii to lower-case. we let non-ascii (utf8) chars pass
     98     // through unchanged
     99     for (int i = (int)(len - 1); i >= 0; --i) {
    100         int c = str[i];
    101         if ((c & 0x80) == 0) {   // is just ascii
    102             c = tolower(c);
    103         }
    104         lc[i] = c;
    105     }
    106     lc[len] = 0;
    107 }
    108 
    109 SkAutoAsciiToLC::~SkAutoAsciiToLC()
    110 {
    111     if (fLC != fStorage) {
    112         sk_free(fLC);
    113     }
    114 }
    115 
    116 //////////////////////////////////////////////////////////////////////////////
    117 
    118 #define SK_QSortTempSize    16
    119 
    120 static inline void sk_qsort_swap(char a[], char b[], size_t elemSize)
    121 {
    122     char    tmp[SK_QSortTempSize];
    123 
    124     while (elemSize > 0)
    125     {
    126         size_t size = elemSize;
    127         if (size > SK_QSortTempSize)
    128             size = SK_QSortTempSize;
    129         elemSize -= size;
    130 
    131         memcpy(tmp, a, size);
    132         memcpy(a, b, size);
    133         memcpy(b, tmp, size);
    134         a += size;
    135         b += size;
    136     }
    137 }
    138 
    139 static void SkQSort_Partition(char* first, char* last, size_t elemSize, SkQSortCompareProc compare)
    140 {
    141     char*   left = first;
    142     char*   rite = last;
    143     char*   pivot = left;
    144 
    145     while (left <= rite)
    146     {
    147         while (left < last && compare(left, pivot) < 0)
    148             left += elemSize;
    149         while (first < rite && compare(rite, pivot) > 0)
    150             rite -= elemSize;
    151         if (left <= rite)
    152         {
    153             if (left < rite)
    154             {
    155                 SkASSERT(compare(left, rite) >= 0);
    156                 sk_qsort_swap(left, rite, elemSize);
    157             }
    158             left += elemSize;
    159             rite -= elemSize;
    160         }
    161     }
    162     if (first < rite)
    163         SkQSort_Partition(first, rite, elemSize, compare);
    164     if (left < last)
    165         SkQSort_Partition(left, last, elemSize, compare);
    166 }
    167 
    168 void SkQSort(void* base, size_t count, size_t elemSize, SkQSortCompareProc compare)
    169 {
    170     SkASSERT(base);
    171     SkASSERT(compare);
    172     SkASSERT(elemSize > 0);
    173 
    174     if (count <= 1)
    175         return;
    176 
    177     SkQSort_Partition((char*)base, (char*)base + (count - 1) * elemSize, elemSize, compare);
    178 }
    179 
    180