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
116 //////////////////////////////////////////////////////////////////////////////
117
118 #define SK_QSortTempSize 16
119
sk_qsort_swap(char a[],char b[],size_t elemSize)120 static inline void sk_qsort_swap(char a[], char b[], size_t elemSize)
121 {
122 char tmp[SK_QSortTempSize];
123
124 while (elemSize > 0)
125 {
126 size_t size = elemSize;
127 if (size > SK_QSortTempSize)
128 size = SK_QSortTempSize;
129 elemSize -= size;
130
131 memcpy(tmp, a, size);
132 memcpy(a, b, size);
133 memcpy(b, tmp, size);
134 a += size;
135 b += size;
136 }
137 }
138
SkQSort_Partition(char * first,char * last,size_t elemSize,SkQSortCompareProc compare)139 static void SkQSort_Partition(char* first, char* last, size_t elemSize, SkQSortCompareProc compare)
140 {
141 char* left = first;
142 char* rite = last;
143 char* pivot = left;
144
145 while (left <= rite)
146 {
147 while (left < last && compare(left, pivot) < 0)
148 left += elemSize;
149 while (first < rite && compare(rite, pivot) > 0)
150 rite -= elemSize;
151 if (left <= rite)
152 {
153 if (left < rite)
154 {
155 SkASSERT(compare(left, rite) >= 0);
156 sk_qsort_swap(left, rite, elemSize);
157 }
158 left += elemSize;
159 rite -= elemSize;
160 }
161 }
162 if (first < rite)
163 SkQSort_Partition(first, rite, elemSize, compare);
164 if (left < last)
165 SkQSort_Partition(left, last, elemSize, compare);
166 }
167
SkQSort(void * base,size_t count,size_t elemSize,SkQSortCompareProc compare)168 void SkQSort(void* base, size_t count, size_t elemSize, SkQSortCompareProc compare)
169 {
170 SkASSERT(base);
171 SkASSERT(compare);
172 SkASSERT(elemSize > 0);
173
174 if (count <= 1)
175 return;
176
177 SkQSort_Partition((char*)base, (char*)base + (count - 1) * elemSize, elemSize, compare);
178 }
179
180