| /* |
| * Copyright 2006 The Android Open Source Project |
| * |
| * Use of this source code is governed by a BSD-style license that can be |
| * found in the LICENSE file. |
| */ |
| |
| |
| #include "src/core/SkTSearch.h" |
| |
| #include "include/private/SkMalloc.h" |
| |
| #include <ctype.h> |
| |
| static inline const char* index_into_base(const char*const* base, int index, |
| size_t elemSize) |
| { |
| return *(const char*const*)((const char*)base + index * elemSize); |
| } |
| |
| int SkStrSearch(const char*const* base, int count, const char target[], |
| size_t target_len, size_t elemSize) |
| { |
| if (count <= 0) |
| return ~0; |
| |
| SkASSERT(base != nullptr); |
| |
| int lo = 0; |
| int hi = count - 1; |
| |
| while (lo < hi) |
| { |
| int mid = (hi + lo) >> 1; |
| const char* elem = index_into_base(base, mid, elemSize); |
| |
| int cmp = strncmp(elem, target, target_len); |
| if (cmp < 0) |
| lo = mid + 1; |
| else if (cmp > 0 || strlen(elem) > target_len) |
| hi = mid; |
| else |
| return mid; |
| } |
| |
| const char* elem = index_into_base(base, hi, elemSize); |
| int cmp = strncmp(elem, target, target_len); |
| if (cmp || strlen(elem) > target_len) |
| { |
| if (cmp < 0) |
| hi += 1; |
| hi = ~hi; |
| } |
| return hi; |
| } |
| |
| int SkStrSearch(const char*const* base, int count, const char target[], |
| size_t elemSize) |
| { |
| return SkStrSearch(base, count, target, strlen(target), elemSize); |
| } |
| |
| int SkStrLCSearch(const char*const* base, int count, const char target[], |
| size_t len, size_t elemSize) |
| { |
| SkASSERT(target); |
| |
| SkAutoAsciiToLC tolc(target, len); |
| |
| return SkStrSearch(base, count, tolc.lc(), len, elemSize); |
| } |
| |
| int SkStrLCSearch(const char*const* base, int count, const char target[], |
| size_t elemSize) |
| { |
| return SkStrLCSearch(base, count, target, strlen(target), elemSize); |
| } |
| |
| ////////////////////////////////////////////////////////////////////////////// |
| |
| SkAutoAsciiToLC::SkAutoAsciiToLC(const char str[], size_t len) |
| { |
| // see if we need to compute the length |
| if ((long)len < 0) { |
| len = strlen(str); |
| } |
| fLength = len; |
| |
| // assign lc to our preallocated storage if len is small enough, or allocate |
| // it on the heap |
| char* lc; |
| if (len <= STORAGE) { |
| lc = fStorage; |
| } else { |
| lc = (char*)sk_malloc_throw(len + 1); |
| } |
| fLC = lc; |
| |
| // convert any asii to lower-case. we let non-ascii (utf8) chars pass |
| // through unchanged |
| for (int i = (int)(len - 1); i >= 0; --i) { |
| int c = str[i]; |
| if ((c & 0x80) == 0) { // is just ascii |
| c = tolower(c); |
| } |
| lc[i] = c; |
| } |
| lc[len] = 0; |
| } |
| |
| SkAutoAsciiToLC::~SkAutoAsciiToLC() |
| { |
| if (fLC != fStorage) { |
| sk_free(fLC); |
| } |
| } |