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