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
index_into_base(const char * const * base,int index,size_t elemSize)13 static 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
SkStrSearch(const char * const * base,int count,const char target[],size_t target_len,size_t elemSize)19 int 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
SkStrSearch(const char * const * base,int count,const char target[],size_t elemSize)55 int 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
SkStrLCSearch(const char * const * base,int count,const char target[],size_t len,size_t elemSize)61 int 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
SkStrLCSearch(const char * const * base,int count,const char target[],size_t elemSize)71 int 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
SkAutoAsciiToLC(const char str[],size_t len)79 SkAutoAsciiToLC::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
~SkAutoAsciiToLC()109 SkAutoAsciiToLC::~SkAutoAsciiToLC()
110 {
111 if (fLC != fStorage) {
112 sk_free(fLC);
113 }
114 }
115