180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru/* 380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * Copyright 2006 The Android Open Source Project 480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * 580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * Use of this source code is governed by a BSD-style license that can be 680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * found in the LICENSE file. 780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru */ 880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 1080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru#include "SkTSearch.h" 1180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru#include <ctype.h> 1280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 1380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Querustatic inline const char* index_into_base(const char*const* base, int index, 1480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru size_t elemSize) 1580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru{ 1680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru return *(const char*const*)((const char*)base + index * elemSize); 1780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru} 1880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 1980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queruint SkStrSearch(const char*const* base, int count, const char target[], 2080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru size_t target_len, size_t elemSize) 2180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru{ 2280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (count <= 0) 2380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru return ~0; 2480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 2580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkASSERT(base != NULL); 2680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 2780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru int lo = 0; 2880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru int hi = count - 1; 2980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 3080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru while (lo < hi) 3180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru { 3280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru int mid = (hi + lo) >> 1; 3380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru const char* elem = index_into_base(base, mid, elemSize); 3480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 3580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru int cmp = strncmp(elem, target, target_len); 3680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (cmp < 0) 3780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru lo = mid + 1; 3880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru else if (cmp > 0 || strlen(elem) > target_len) 3980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru hi = mid; 4080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru else 4180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru return mid; 4280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 4380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 4480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru const char* elem = index_into_base(base, hi, elemSize); 4580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru int cmp = strncmp(elem, target, target_len); 4680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (cmp || strlen(elem) > target_len) 4780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru { 4880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (cmp < 0) 4980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru hi += 1; 5080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru hi = ~hi; 5180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 5280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru return hi; 5380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru} 5480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 5580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queruint SkStrSearch(const char*const* base, int count, const char target[], 5680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru size_t elemSize) 5780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru{ 5880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru return SkStrSearch(base, count, target, strlen(target), elemSize); 5980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru} 6080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 6180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queruint SkStrLCSearch(const char*const* base, int count, const char target[], 6280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru size_t len, size_t elemSize) 6380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru{ 6480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkASSERT(target); 6580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 6680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkAutoAsciiToLC tolc(target, len); 6780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 6880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru return SkStrSearch(base, count, tolc.lc(), len, elemSize); 6980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru} 7080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 7180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queruint SkStrLCSearch(const char*const* base, int count, const char target[], 7280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru size_t elemSize) 7380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru{ 7480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru return SkStrLCSearch(base, count, target, strlen(target), elemSize); 7580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru} 7680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 7780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru////////////////////////////////////////////////////////////////////////////// 7880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 7980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste QueruSkAutoAsciiToLC::SkAutoAsciiToLC(const char str[], size_t len) 8080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru{ 8180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru // see if we need to compute the length 8280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if ((long)len < 0) { 8380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru len = strlen(str); 8480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 8580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru fLength = len; 8680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 8780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru // assign lc to our preallocated storage if len is small enough, or allocate 8880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru // it on the heap 8980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru char* lc; 9080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (len <= STORAGE) { 9180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru lc = fStorage; 9280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } else { 9380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru lc = (char*)sk_malloc_throw(len + 1); 9480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 9580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru fLC = lc; 9680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 9780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru // convert any asii to lower-case. we let non-ascii (utf8) chars pass 9880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru // through unchanged 9980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru for (int i = (int)(len - 1); i >= 0; --i) { 10080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru int c = str[i]; 10180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if ((c & 0x80) == 0) { // is just ascii 10280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru c = tolower(c); 10380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 10480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru lc[i] = c; 10580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 10680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru lc[len] = 0; 10780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru} 10880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 10980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste QueruSkAutoAsciiToLC::~SkAutoAsciiToLC() 11080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru{ 11180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (fLC != fStorage) { 11280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru sk_free(fLC); 11380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 11480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru} 115