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