1685cfc0ee13d7c355ae2f4f3d225ad45e945763fepoger@google.com 2685cfc0ee13d7c355ae2f4f3d225ad45e945763fepoger@google.com/* 3685cfc0ee13d7c355ae2f4f3d225ad45e945763fepoger@google.com * Copyright 2006 The Android Open Source Project 4685cfc0ee13d7c355ae2f4f3d225ad45e945763fepoger@google.com * 5685cfc0ee13d7c355ae2f4f3d225ad45e945763fepoger@google.com * Use of this source code is governed by a BSD-style license that can be 6685cfc0ee13d7c355ae2f4f3d225ad45e945763fepoger@google.com * found in the LICENSE file. 7685cfc0ee13d7c355ae2f4f3d225ad45e945763fepoger@google.com */ 8685cfc0ee13d7c355ae2f4f3d225ad45e945763fepoger@google.com 9bcd4d5ab12df062500a4df90ec90d0f2d764931reed@android.com 10bcd4d5ab12df062500a4df90ec90d0f2d764931reed@android.com#include "SkTSearch.h" 11bcd4d5ab12df062500a4df90ec90d0f2d764931reed@android.com#include <ctype.h> 12bcd4d5ab12df062500a4df90ec90d0f2d764931reed@android.com 13bcd4d5ab12df062500a4df90ec90d0f2d764931reed@android.comstatic inline const char* index_into_base(const char*const* base, int index, 14bcd4d5ab12df062500a4df90ec90d0f2d764931reed@android.com size_t elemSize) 15bcd4d5ab12df062500a4df90ec90d0f2d764931reed@android.com{ 16bcd4d5ab12df062500a4df90ec90d0f2d764931reed@android.com return *(const char*const*)((const char*)base + index * elemSize); 17bcd4d5ab12df062500a4df90ec90d0f2d764931reed@android.com} 18bcd4d5ab12df062500a4df90ec90d0f2d764931reed@android.com 19bcd4d5ab12df062500a4df90ec90d0f2d764931reed@android.comint SkStrSearch(const char*const* base, int count, const char target[], 20bcd4d5ab12df062500a4df90ec90d0f2d764931reed@android.com size_t target_len, size_t elemSize) 21bcd4d5ab12df062500a4df90ec90d0f2d764931reed@android.com{ 22bcd4d5ab12df062500a4df90ec90d0f2d764931reed@android.com if (count <= 0) 23bcd4d5ab12df062500a4df90ec90d0f2d764931reed@android.com return ~0; 24bcd4d5ab12df062500a4df90ec90d0f2d764931reed@android.com 25bcd4d5ab12df062500a4df90ec90d0f2d764931reed@android.com SkASSERT(base != NULL); 26bcd4d5ab12df062500a4df90ec90d0f2d764931reed@android.com 27bcd4d5ab12df062500a4df90ec90d0f2d764931reed@android.com int lo = 0; 28bcd4d5ab12df062500a4df90ec90d0f2d764931reed@android.com int hi = count - 1; 29bcd4d5ab12df062500a4df90ec90d0f2d764931reed@android.com 30bcd4d5ab12df062500a4df90ec90d0f2d764931reed@android.com while (lo < hi) 31bcd4d5ab12df062500a4df90ec90d0f2d764931reed@android.com { 32bcd4d5ab12df062500a4df90ec90d0f2d764931reed@android.com int mid = (hi + lo) >> 1; 33bcd4d5ab12df062500a4df90ec90d0f2d764931reed@android.com const char* elem = index_into_base(base, mid, elemSize); 34bcd4d5ab12df062500a4df90ec90d0f2d764931reed@android.com 35bcd4d5ab12df062500a4df90ec90d0f2d764931reed@android.com int cmp = strncmp(elem, target, target_len); 36bcd4d5ab12df062500a4df90ec90d0f2d764931reed@android.com if (cmp < 0) 37bcd4d5ab12df062500a4df90ec90d0f2d764931reed@android.com lo = mid + 1; 38bcd4d5ab12df062500a4df90ec90d0f2d764931reed@android.com else if (cmp > 0 || strlen(elem) > target_len) 39bcd4d5ab12df062500a4df90ec90d0f2d764931reed@android.com hi = mid; 40bcd4d5ab12df062500a4df90ec90d0f2d764931reed@android.com else 41bcd4d5ab12df062500a4df90ec90d0f2d764931reed@android.com return mid; 42bcd4d5ab12df062500a4df90ec90d0f2d764931reed@android.com } 43bcd4d5ab12df062500a4df90ec90d0f2d764931reed@android.com 44bcd4d5ab12df062500a4df90ec90d0f2d764931reed@android.com const char* elem = index_into_base(base, hi, elemSize); 45bcd4d5ab12df062500a4df90ec90d0f2d764931reed@android.com int cmp = strncmp(elem, target, target_len); 46bcd4d5ab12df062500a4df90ec90d0f2d764931reed@android.com if (cmp || strlen(elem) > target_len) 47bcd4d5ab12df062500a4df90ec90d0f2d764931reed@android.com { 48bcd4d5ab12df062500a4df90ec90d0f2d764931reed@android.com if (cmp < 0) 49bcd4d5ab12df062500a4df90ec90d0f2d764931reed@android.com hi += 1; 50bcd4d5ab12df062500a4df90ec90d0f2d764931reed@android.com hi = ~hi; 51bcd4d5ab12df062500a4df90ec90d0f2d764931reed@android.com } 52bcd4d5ab12df062500a4df90ec90d0f2d764931reed@android.com return hi; 53bcd4d5ab12df062500a4df90ec90d0f2d764931reed@android.com} 54bcd4d5ab12df062500a4df90ec90d0f2d764931reed@android.com 55bcd4d5ab12df062500a4df90ec90d0f2d764931reed@android.comint SkStrSearch(const char*const* base, int count, const char target[], 56bcd4d5ab12df062500a4df90ec90d0f2d764931reed@android.com size_t elemSize) 57bcd4d5ab12df062500a4df90ec90d0f2d764931reed@android.com{ 58bcd4d5ab12df062500a4df90ec90d0f2d764931reed@android.com return SkStrSearch(base, count, target, strlen(target), elemSize); 59bcd4d5ab12df062500a4df90ec90d0f2d764931reed@android.com} 60bcd4d5ab12df062500a4df90ec90d0f2d764931reed@android.com 61bcd4d5ab12df062500a4df90ec90d0f2d764931reed@android.comint SkStrLCSearch(const char*const* base, int count, const char target[], 62bcd4d5ab12df062500a4df90ec90d0f2d764931reed@android.com size_t len, size_t elemSize) 63bcd4d5ab12df062500a4df90ec90d0f2d764931reed@android.com{ 64bcd4d5ab12df062500a4df90ec90d0f2d764931reed@android.com SkASSERT(target); 65bcd4d5ab12df062500a4df90ec90d0f2d764931reed@android.com 66bcd4d5ab12df062500a4df90ec90d0f2d764931reed@android.com SkAutoAsciiToLC tolc(target, len); 67bcd4d5ab12df062500a4df90ec90d0f2d764931reed@android.com 68bcd4d5ab12df062500a4df90ec90d0f2d764931reed@android.com return SkStrSearch(base, count, tolc.lc(), len, elemSize); 69bcd4d5ab12df062500a4df90ec90d0f2d764931reed@android.com} 70bcd4d5ab12df062500a4df90ec90d0f2d764931reed@android.com 71bcd4d5ab12df062500a4df90ec90d0f2d764931reed@android.comint SkStrLCSearch(const char*const* base, int count, const char target[], 72bcd4d5ab12df062500a4df90ec90d0f2d764931reed@android.com size_t elemSize) 73bcd4d5ab12df062500a4df90ec90d0f2d764931reed@android.com{ 74bcd4d5ab12df062500a4df90ec90d0f2d764931reed@android.com return SkStrLCSearch(base, count, target, strlen(target), elemSize); 75bcd4d5ab12df062500a4df90ec90d0f2d764931reed@android.com} 76bcd4d5ab12df062500a4df90ec90d0f2d764931reed@android.com 77bcd4d5ab12df062500a4df90ec90d0f2d764931reed@android.com////////////////////////////////////////////////////////////////////////////// 78bcd4d5ab12df062500a4df90ec90d0f2d764931reed@android.com 79bcd4d5ab12df062500a4df90ec90d0f2d764931reed@android.comSkAutoAsciiToLC::SkAutoAsciiToLC(const char str[], size_t len) 80bcd4d5ab12df062500a4df90ec90d0f2d764931reed@android.com{ 81bcd4d5ab12df062500a4df90ec90d0f2d764931reed@android.com // see if we need to compute the length 82bcd4d5ab12df062500a4df90ec90d0f2d764931reed@android.com if ((long)len < 0) { 83bcd4d5ab12df062500a4df90ec90d0f2d764931reed@android.com len = strlen(str); 84bcd4d5ab12df062500a4df90ec90d0f2d764931reed@android.com } 85bcd4d5ab12df062500a4df90ec90d0f2d764931reed@android.com fLength = len; 86bcd4d5ab12df062500a4df90ec90d0f2d764931reed@android.com 87bcd4d5ab12df062500a4df90ec90d0f2d764931reed@android.com // assign lc to our preallocated storage if len is small enough, or allocate 88bcd4d5ab12df062500a4df90ec90d0f2d764931reed@android.com // it on the heap 89bcd4d5ab12df062500a4df90ec90d0f2d764931reed@android.com char* lc; 90bcd4d5ab12df062500a4df90ec90d0f2d764931reed@android.com if (len <= STORAGE) { 91bcd4d5ab12df062500a4df90ec90d0f2d764931reed@android.com lc = fStorage; 92bcd4d5ab12df062500a4df90ec90d0f2d764931reed@android.com } else { 93bcd4d5ab12df062500a4df90ec90d0f2d764931reed@android.com lc = (char*)sk_malloc_throw(len + 1); 94bcd4d5ab12df062500a4df90ec90d0f2d764931reed@android.com } 95bcd4d5ab12df062500a4df90ec90d0f2d764931reed@android.com fLC = lc; 96935e9f4fafdfc64130e6be9ea2bb30e3bafd852armistry@google.com 97bcd4d5ab12df062500a4df90ec90d0f2d764931reed@android.com // convert any asii to lower-case. we let non-ascii (utf8) chars pass 98bcd4d5ab12df062500a4df90ec90d0f2d764931reed@android.com // through unchanged 99bcd4d5ab12df062500a4df90ec90d0f2d764931reed@android.com for (int i = (int)(len - 1); i >= 0; --i) { 100bcd4d5ab12df062500a4df90ec90d0f2d764931reed@android.com int c = str[i]; 101bcd4d5ab12df062500a4df90ec90d0f2d764931reed@android.com if ((c & 0x80) == 0) { // is just ascii 102bcd4d5ab12df062500a4df90ec90d0f2d764931reed@android.com c = tolower(c); 103bcd4d5ab12df062500a4df90ec90d0f2d764931reed@android.com } 104bcd4d5ab12df062500a4df90ec90d0f2d764931reed@android.com lc[i] = c; 105bcd4d5ab12df062500a4df90ec90d0f2d764931reed@android.com } 106bcd4d5ab12df062500a4df90ec90d0f2d764931reed@android.com lc[len] = 0; 107bcd4d5ab12df062500a4df90ec90d0f2d764931reed@android.com} 108bcd4d5ab12df062500a4df90ec90d0f2d764931reed@android.com 109bcd4d5ab12df062500a4df90ec90d0f2d764931reed@android.comSkAutoAsciiToLC::~SkAutoAsciiToLC() 110bcd4d5ab12df062500a4df90ec90d0f2d764931reed@android.com{ 111bcd4d5ab12df062500a4df90ec90d0f2d764931reed@android.com if (fLC != fStorage) { 112bcd4d5ab12df062500a4df90ec90d0f2d764931reed@android.com sk_free(fLC); 113bcd4d5ab12df062500a4df90ec90d0f2d764931reed@android.com } 114bcd4d5ab12df062500a4df90ec90d0f2d764931reed@android.com} 115