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