/src/skia/src/core/SkTSearch.cpp
Line | Count | Source (jump to first uncovered line) |
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 "src/core/SkTSearch.h" |
10 | | |
11 | | #include "include/private/SkMalloc.h" |
12 | | |
13 | | #include <ctype.h> |
14 | | |
15 | | static inline const char* index_into_base(const char*const* base, int index, |
16 | | size_t elemSize) |
17 | 2.06M | { |
18 | 2.06M | return *(const char*const*)((const char*)base + index * elemSize); |
19 | 2.06M | } |
20 | | |
21 | | int SkStrSearch(const char*const* base, int count, const char target[], |
22 | | size_t target_len, size_t elemSize) |
23 | 429k | { |
24 | 429k | if (count <= 0) |
25 | 0 | return ~0; |
26 | | |
27 | 429k | SkASSERT(base != nullptr); |
28 | | |
29 | 429k | int lo = 0; |
30 | 429k | int hi = count - 1; |
31 | | |
32 | 2.06M | while (lo < hi) |
33 | 1.86M | { |
34 | 1.86M | int mid = (hi + lo) >> 1; |
35 | 1.86M | const char* elem = index_into_base(base, mid, elemSize); |
36 | | |
37 | 1.86M | int cmp = strncmp(elem, target, target_len); |
38 | 1.86M | if (cmp < 0) |
39 | 809k | lo = mid + 1; |
40 | 1.05M | else if (cmp > 0 || strlen(elem) > target_len) |
41 | 825k | hi = mid; |
42 | 228k | else |
43 | 228k | return mid; |
44 | 1.86M | } |
45 | | |
46 | 201k | const char* elem = index_into_base(base, hi, elemSize); |
47 | 201k | int cmp = strncmp(elem, target, target_len); |
48 | 201k | if (cmp || strlen(elem) > target_len) |
49 | 199k | { |
50 | 199k | if (cmp < 0) |
51 | 2.55k | hi += 1; |
52 | 199k | hi = ~hi; |
53 | 199k | } |
54 | 201k | return hi; |
55 | 429k | } |
56 | | |
57 | | int SkStrSearch(const char*const* base, int count, const char target[], |
58 | | size_t elemSize) |
59 | 429k | { |
60 | 429k | return SkStrSearch(base, count, target, strlen(target), elemSize); |
61 | 429k | } |
62 | | |
63 | | int SkStrLCSearch(const char*const* base, int count, const char target[], |
64 | | size_t len, size_t elemSize) |
65 | 141 | { |
66 | 141 | SkASSERT(target); |
67 | | |
68 | 141 | SkAutoAsciiToLC tolc(target, len); |
69 | | |
70 | 141 | return SkStrSearch(base, count, tolc.lc(), len, elemSize); |
71 | 141 | } |
72 | | |
73 | | int SkStrLCSearch(const char*const* base, int count, const char target[], |
74 | | size_t elemSize) |
75 | 141 | { |
76 | 141 | return SkStrLCSearch(base, count, target, strlen(target), elemSize); |
77 | 141 | } |
78 | | |
79 | | ////////////////////////////////////////////////////////////////////////////// |
80 | | |
81 | | SkAutoAsciiToLC::SkAutoAsciiToLC(const char str[], size_t len) |
82 | 141 | { |
83 | | // see if we need to compute the length |
84 | 141 | if ((long)len < 0) { |
85 | 0 | len = strlen(str); |
86 | 0 | } |
87 | 141 | fLength = len; |
88 | | |
89 | | // assign lc to our preallocated storage if len is small enough, or allocate |
90 | | // it on the heap |
91 | 141 | char* lc; |
92 | 141 | if (len <= STORAGE) { |
93 | 141 | lc = fStorage; |
94 | 0 | } else { |
95 | 0 | lc = (char*)sk_malloc_throw(len + 1); |
96 | 0 | } |
97 | 141 | fLC = lc; |
98 | | |
99 | | // convert any asii to lower-case. we let non-ascii (utf8) chars pass |
100 | | // through unchanged |
101 | 1.12k | for (int i = (int)(len - 1); i >= 0; --i) { |
102 | 987 | int c = str[i]; |
103 | 987 | if ((c & 0x80) == 0) { // is just ascii |
104 | 987 | c = tolower(c); |
105 | 987 | } |
106 | 987 | lc[i] = c; |
107 | 987 | } |
108 | 141 | lc[len] = 0; |
109 | 141 | } |
110 | | |
111 | | SkAutoAsciiToLC::~SkAutoAsciiToLC() |
112 | 141 | { |
113 | 141 | if (fLC != fStorage) { |
114 | 0 | sk_free(fLC); |
115 | 0 | } |
116 | 141 | } |