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
index_into_base(const char * const * base,int index,size_t elemSize)15 static 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
SkStrSearch(const char * const * base,int count,const char target[],size_t target_len,size_t elemSize)21 int 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
SkStrSearch(const char * const * base,int count,const char target[],size_t elemSize)57 int 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
SkStrLCSearch(const char * const * base,int count,const char target[],size_t len,size_t elemSize)63 int 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
SkStrLCSearch(const char * const * base,int count,const char target[],size_t elemSize)73 int 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
SkAutoAsciiToLC(const char str[],size_t len)81 SkAutoAsciiToLC::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
~SkAutoAsciiToLC()111 SkAutoAsciiToLC::~SkAutoAsciiToLC()
112 {
113 if (fLC != fStorage) {
114 sk_free(fLC);
115 }
116 }
117