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