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 15static 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 21int 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 57int 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 63int 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 73int 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 81SkAutoAsciiToLC::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 111SkAutoAsciiToLC::~SkAutoAsciiToLC() 112{ 113 if (fLC != fStorage) { 114 sk_free(fLC); 115 } 116} 117