Home | History | Annotate | Download | only in core 
      1 /*
      2  * Copyright 2006 The Android Open Source Project
      3  *
      4  * Use of this source code is governed by a BSD-style license that can be
      5  * found in the LICENSE file.
      6  */
      7 
      8 
      9 #include "SkTSearch.h"
     10 
     11 #include "SkMalloc.h"
     12 
     13 #include <ctype.h>
     14 
     15 static inline const char* index_into_base(const char*const* base, int index,
     16                                           size_t elemSize)
     17 {
     18     return *(const char*const*)((const char*)base + index * elemSize);
     19 }
     20 
     21 int SkStrSearch(const char*const* base, int count, const char target[],
     22                 size_t target_len, size_t elemSize)
     23 {
     24     if (count <= 0)
     25         return ~0;
     26 
     27     SkASSERT(base != nullptr);
     28 
     29     int lo = 0;
     30     int hi = count - 1;
     31 
     32     while (lo < hi)
     33     {
     34         int mid = (hi + lo) >> 1;
     35         const char* elem = index_into_base(base, mid, elemSize);
     36 
     37         int cmp = strncmp(elem, target, target_len);
     38         if (cmp < 0)
     39             lo = mid + 1;
     40         else if (cmp > 0 || strlen(elem) > target_len)
     41             hi = mid;
     42         else
     43             return mid;
     44     }
     45 
     46     const char* elem = index_into_base(base, hi, elemSize);
     47     int cmp = strncmp(elem, target, target_len);
     48     if (cmp || strlen(elem) > target_len)
     49     {
     50         if (cmp < 0)
     51             hi += 1;
     52         hi = ~hi;
     53     }
     54     return hi;
     55 }
     56 
     57 int SkStrSearch(const char*const* base, int count, const char target[],
     58                 size_t elemSize)
     59 {
     60     return SkStrSearch(base, count, target, strlen(target), elemSize);
     61 }
     62 
     63 int SkStrLCSearch(const char*const* base, int count, const char target[],
     64                   size_t len, size_t elemSize)
     65 {
     66     SkASSERT(target);
     67 
     68     SkAutoAsciiToLC tolc(target, len);
     69 
     70     return SkStrSearch(base, count, tolc.lc(), len, elemSize);
     71 }
     72 
     73 int SkStrLCSearch(const char*const* base, int count, const char target[],
     74                   size_t elemSize)
     75 {
     76     return SkStrLCSearch(base, count, target, strlen(target), elemSize);
     77 }
     78 
     79 //////////////////////////////////////////////////////////////////////////////
     80 
     81 SkAutoAsciiToLC::SkAutoAsciiToLC(const char str[], size_t len)
     82 {
     83     // see if we need to compute the length
     84     if ((long)len < 0) {
     85         len = strlen(str);
     86     }
     87     fLength = len;
     88 
     89     // assign lc to our preallocated storage if len is small enough, or allocate
     90     // it on the heap
     91     char*   lc;
     92     if (len <= STORAGE) {
     93         lc = fStorage;
     94     } else {
     95         lc = (char*)sk_malloc_throw(len + 1);
     96     }
     97     fLC = lc;
     98 
     99     // convert any asii to lower-case. we let non-ascii (utf8) chars pass
    100     // through unchanged
    101     for (int i = (int)(len - 1); i >= 0; --i) {
    102         int c = str[i];
    103         if ((c & 0x80) == 0) {   // is just ascii
    104             c = tolower(c);
    105         }
    106         lc[i] = c;
    107     }
    108     lc[len] = 0;
    109 }
    110 
    111 SkAutoAsciiToLC::~SkAutoAsciiToLC()
    112 {
    113     if (fLC != fStorage) {
    114         sk_free(fLC);
    115     }
    116 }
    117