1 /* libs/graphics/sgl/SkTSearch.cpp
2 **
3 ** Copyright 2006, The Android Open Source Project
4 **
5 ** Licensed under the Apache License, Version 2.0 (the "License");
6 ** you may not use this file except in compliance with the License.
7 ** You may obtain a copy of the License at
8 **
9 ** http://www.apache.org/licenses/LICENSE-2.0
10 **
11 ** Unless required by applicable law or agreed to in writing, software
12 ** distributed under the License is distributed on an "AS IS" BASIS,
13 ** WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14 ** See the License for the specific language governing permissions and
15 ** limitations under the License.
16 */
17
18 #include "SkTSearch.h"
19 #include <ctype.h>
20
index_into_base(const char * const * base,int index,size_t elemSize)21 static inline const char* index_into_base(const char*const* base, int index,
22 size_t elemSize)
23 {
24 return *(const char*const*)((const char*)base + index * elemSize);
25 }
26
SkStrSearch(const char * const * base,int count,const char target[],size_t target_len,size_t elemSize)27 int SkStrSearch(const char*const* base, int count, const char target[],
28 size_t target_len, size_t elemSize)
29 {
30 if (count <= 0)
31 return ~0;
32
33 SkASSERT(base != NULL);
34
35 int lo = 0;
36 int hi = count - 1;
37
38 while (lo < hi)
39 {
40 int mid = (hi + lo) >> 1;
41 const char* elem = index_into_base(base, mid, elemSize);
42
43 int cmp = strncmp(elem, target, target_len);
44 if (cmp < 0)
45 lo = mid + 1;
46 else if (cmp > 0 || strlen(elem) > target_len)
47 hi = mid;
48 else
49 return mid;
50 }
51
52 const char* elem = index_into_base(base, hi, elemSize);
53 int cmp = strncmp(elem, target, target_len);
54 if (cmp || strlen(elem) > target_len)
55 {
56 if (cmp < 0)
57 hi += 1;
58 hi = ~hi;
59 }
60 return hi;
61 }
62
SkStrSearch(const char * const * base,int count,const char target[],size_t elemSize)63 int SkStrSearch(const char*const* base, int count, const char target[],
64 size_t elemSize)
65 {
66 return SkStrSearch(base, count, target, strlen(target), elemSize);
67 }
68
SkStrLCSearch(const char * const * base,int count,const char target[],size_t len,size_t elemSize)69 int SkStrLCSearch(const char*const* base, int count, const char target[],
70 size_t len, size_t elemSize)
71 {
72 SkASSERT(target);
73
74 SkAutoAsciiToLC tolc(target, len);
75
76 return SkStrSearch(base, count, tolc.lc(), len, elemSize);
77 }
78
SkStrLCSearch(const char * const * base,int count,const char target[],size_t elemSize)79 int SkStrLCSearch(const char*const* base, int count, const char target[],
80 size_t elemSize)
81 {
82 return SkStrLCSearch(base, count, target, strlen(target), elemSize);
83 }
84
85 //////////////////////////////////////////////////////////////////////////////
86
SkAutoAsciiToLC(const char str[],size_t len)87 SkAutoAsciiToLC::SkAutoAsciiToLC(const char str[], size_t len)
88 {
89 // see if we need to compute the length
90 if ((long)len < 0) {
91 len = strlen(str);
92 }
93 fLength = len;
94
95 // assign lc to our preallocated storage if len is small enough, or allocate
96 // it on the heap
97 char* lc;
98 if (len <= STORAGE) {
99 lc = fStorage;
100 } else {
101 lc = (char*)sk_malloc_throw(len + 1);
102 }
103 fLC = lc;
104
105 // convert any asii to lower-case. we let non-ascii (utf8) chars pass
106 // through unchanged
107 for (int i = (int)(len - 1); i >= 0; --i) {
108 int c = str[i];
109 if ((c & 0x80) == 0) { // is just ascii
110 c = tolower(c);
111 }
112 lc[i] = c;
113 }
114 lc[len] = 0;
115 }
116
~SkAutoAsciiToLC()117 SkAutoAsciiToLC::~SkAutoAsciiToLC()
118 {
119 if (fLC != fStorage) {
120 sk_free(fLC);
121 }
122 }
123
124 //////////////////////////////////////////////////////////////////////////////
125
126 #define SK_QSortTempSize 16
127
sk_qsort_swap(char a[],char b[],size_t elemSize)128 static inline void sk_qsort_swap(char a[], char b[], size_t elemSize)
129 {
130 char tmp[SK_QSortTempSize];
131
132 while (elemSize > 0)
133 {
134 size_t size = elemSize;
135 if (size > SK_QSortTempSize)
136 size = SK_QSortTempSize;
137 elemSize -= size;
138
139 memcpy(tmp, a, size);
140 memcpy(a, b, size);
141 memcpy(b, tmp, size);
142 a += size;
143 b += size;
144 }
145 }
146
SkQSort_Partition(char * first,char * last,size_t elemSize,SkQSortCompareProc compare)147 static void SkQSort_Partition(char* first, char* last, size_t elemSize, SkQSortCompareProc compare)
148 {
149 char* left = first;
150 char* rite = last;
151 char* pivot = left;
152
153 while (left <= rite)
154 {
155 while (left < last && compare(left, pivot) < 0)
156 left += elemSize;
157 while (first < rite && compare(rite, pivot) > 0)
158 rite -= elemSize;
159 if (left <= rite)
160 {
161 if (left < rite)
162 {
163 SkASSERT(compare(left, rite) >= 0);
164 sk_qsort_swap(left, rite, elemSize);
165 }
166 left += elemSize;
167 rite -= elemSize;
168 }
169 }
170 if (first < rite)
171 SkQSort_Partition(first, rite, elemSize, compare);
172 if (left < last)
173 SkQSort_Partition(left, last, elemSize, compare);
174 }
175
SkQSort(void * base,size_t count,size_t elemSize,SkQSortCompareProc compare)176 void SkQSort(void* base, size_t count, size_t elemSize, SkQSortCompareProc compare)
177 {
178 SkASSERT(base);
179 SkASSERT(compare);
180 SkASSERT(elemSize > 0);
181
182 if (count <= 1)
183 return;
184
185 SkQSort_Partition((char*)base, (char*)base + (count - 1) * elemSize, elemSize, compare);
186 }
187
188