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