1ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com 2ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com/* 3ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com * Copyright 2006 The Android Open Source Project 4ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com * 5ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com * Use of this source code is governed by a BSD-style license that can be 6ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com * found in the LICENSE file. 7ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com */ 8ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com 98a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 108a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com#include "SkTSearch.h" 118a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com#include <ctype.h> 128a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 138a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.comstatic inline const char* index_into_base(const char*const* base, int index, 148a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com size_t elemSize) 158a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com{ 168a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return *(const char*const*)((const char*)base + index * elemSize); 178a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 188a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 198a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.comint SkStrSearch(const char*const* base, int count, const char target[], 208a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com size_t target_len, size_t elemSize) 218a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com{ 228a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (count <= 0) 238a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return ~0; 248a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 258a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(base != NULL); 268a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 278a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com int lo = 0; 288a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com int hi = count - 1; 298a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 308a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com while (lo < hi) 318a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com { 328a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com int mid = (hi + lo) >> 1; 338a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com const char* elem = index_into_base(base, mid, elemSize); 348a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 358a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com int cmp = strncmp(elem, target, target_len); 368a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (cmp < 0) 378a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com lo = mid + 1; 388a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com else if (cmp > 0 || strlen(elem) > target_len) 398a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com hi = mid; 408a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com else 418a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return mid; 428a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 438a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 448a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com const char* elem = index_into_base(base, hi, elemSize); 458a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com int cmp = strncmp(elem, target, target_len); 468a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (cmp || strlen(elem) > target_len) 478a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com { 488a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (cmp < 0) 498a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com hi += 1; 508a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com hi = ~hi; 518a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 528a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return hi; 538a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 548a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 558a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.comint SkStrSearch(const char*const* base, int count, const char target[], 568a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com size_t elemSize) 578a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com{ 588a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return SkStrSearch(base, count, target, strlen(target), elemSize); 598a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 608a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 618a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.comint SkStrLCSearch(const char*const* base, int count, const char target[], 628a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com size_t len, size_t elemSize) 638a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com{ 648a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(target); 658a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 668a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkAutoAsciiToLC tolc(target, len); 678a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 688a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return SkStrSearch(base, count, tolc.lc(), len, elemSize); 698a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 708a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 718a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.comint SkStrLCSearch(const char*const* base, int count, const char target[], 728a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com size_t elemSize) 738a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com{ 748a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return SkStrLCSearch(base, count, target, strlen(target), elemSize); 758a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 768a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 778a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com////////////////////////////////////////////////////////////////////////////// 788a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 798a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.comSkAutoAsciiToLC::SkAutoAsciiToLC(const char str[], size_t len) 808a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com{ 818a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // see if we need to compute the length 828a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if ((long)len < 0) { 838a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com len = strlen(str); 848a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 858a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com fLength = len; 868a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 878a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // assign lc to our preallocated storage if len is small enough, or allocate 888a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // it on the heap 898a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com char* lc; 908a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (len <= STORAGE) { 918a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com lc = fStorage; 928a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } else { 938a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com lc = (char*)sk_malloc_throw(len + 1); 948a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 958a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com fLC = lc; 96fbfcd5602128ec010c82cb733c9cdc0a3254f9f3rmistry@google.com 978a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // convert any asii to lower-case. we let non-ascii (utf8) chars pass 988a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // through unchanged 998a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com for (int i = (int)(len - 1); i >= 0; --i) { 1008a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com int c = str[i]; 1018a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if ((c & 0x80) == 0) { // is just ascii 1028a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com c = tolower(c); 1038a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 1048a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com lc[i] = c; 1058a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 1068a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com lc[len] = 0; 1078a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 1088a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 1098a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.comSkAutoAsciiToLC::~SkAutoAsciiToLC() 1108a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com{ 1118a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (fLC != fStorage) { 1128a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com sk_free(fLC); 1138a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 1148a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 115