Line data    Source code

       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           0 : static inline const char* index_into_base(const char*const* base, int index,
      16             :                                           size_t elemSize)
      17             : {
      18           0 :     return *(const char*const*)((const char*)base + index * elemSize);
      19             : }
      20             : 
      21           0 : int SkStrSearch(const char*const* base, int count, const char target[],
      22             :                 size_t target_len, size_t elemSize)
      23             : {
      24           0 :     if (count <= 0)
      25           0 :         return ~0;
      26             : 
      27           0 :     SkASSERT(base != nullptr);
      28             : 
      29           0 :     int lo = 0;
      30           0 :     int hi = count - 1;
      31             : 
      32           0 :     while (lo < hi)
      33             :     {
      34           0 :         int mid = (hi + lo) >> 1;
      35           0 :         const char* elem = index_into_base(base, mid, elemSize);
      36             : 
      37           0 :         int cmp = strncmp(elem, target, target_len);
      38           0 :         if (cmp < 0)
      39           0 :             lo = mid + 1;
      40           0 :         else if (cmp > 0 || strlen(elem) > target_len)
      41           0 :             hi = mid;
      42             :         else
      43           0 :             return mid;
      44             :     }
      45             : 
      46           0 :     const char* elem = index_into_base(base, hi, elemSize);
      47           0 :     int cmp = strncmp(elem, target, target_len);
      48           0 :     if (cmp || strlen(elem) > target_len)
      49             :     {
      50           0 :         if (cmp < 0)
      51           0 :             hi += 1;
      52           0 :         hi = ~hi;
      53             :     }
      54           0 :     return hi;
      55             : }
      56             : 
      57           0 : int SkStrSearch(const char*const* base, int count, const char target[],
      58             :                 size_t elemSize)
      59             : {
      60           0 :     return SkStrSearch(base, count, target, strlen(target), elemSize);
      61             : }
      62             : 
      63           0 : int SkStrLCSearch(const char*const* base, int count, const char target[],
      64             :                   size_t len, size_t elemSize)
      65             : {
      66           0 :     SkASSERT(target);
      67             : 
      68           0 :     SkAutoAsciiToLC tolc(target, len);
      69             : 
      70           0 :     return SkStrSearch(base, count, tolc.lc(), len, elemSize);
      71             : }
      72             : 
      73           0 : int SkStrLCSearch(const char*const* base, int count, const char target[],
      74             :                   size_t elemSize)
      75             : {
      76           0 :     return SkStrLCSearch(base, count, target, strlen(target), elemSize);
      77             : }
      78             : 
      79             : //////////////////////////////////////////////////////////////////////////////
      80             : 
      81           0 : SkAutoAsciiToLC::SkAutoAsciiToLC(const char str[], size_t len)
      82             : {
      83             :     // see if we need to compute the length
      84           0 :     if ((long)len < 0) {
      85           0 :         len = strlen(str);
      86             :     }
      87           0 :     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           0 :     if (len <= STORAGE) {
      93           0 :         lc = fStorage;
      94             :     } else {
      95           0 :         lc = (char*)sk_malloc_throw(len + 1);
      96             :     }
      97           0 :     fLC = lc;
      98             : 
      99             :     // convert any asii to lower-case. we let non-ascii (utf8) chars pass
     100             :     // through unchanged
     101           0 :     for (int i = (int)(len - 1); i >= 0; --i) {
     102           0 :         int c = str[i];
     103           0 :         if ((c & 0x80) == 0) {   // is just ascii
     104           0 :             c = tolower(c);
     105             :         }
     106           0 :         lc[i] = c;
     107             :     }
     108           0 :     lc[len] = 0;
     109           0 : }
     110             : 
     111           0 : SkAutoAsciiToLC::~SkAutoAsciiToLC()
     112             : {
     113           0 :     if (fLC != fStorage) {
     114           0 :         sk_free(fLC);
     115             :     }
     116           0 : }