1 /*
2 * Copyright (C) 2006 The Android Open Source Project
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17 #ifndef SkTSearch_DEFINED
18 #define SkTSearch_DEFINED
19
20 #include "SkTypes.h"
21
22 template <typename T>
SkTSearch(const T * base,int count,const T & target,size_t elemSize)23 int SkTSearch(const T* base, int count, const T& target, size_t elemSize)
24 {
25 SkASSERT(count >= 0);
26 if (count <= 0)
27 return ~0;
28
29 SkASSERT(base != NULL); // base may be NULL if count is zero
30
31 int lo = 0;
32 int hi = count - 1;
33
34 while (lo < hi)
35 {
36 int mid = (hi + lo) >> 1;
37 const T* elem = (const T*)((const char*)base + mid * elemSize);
38
39 if (*elem < target)
40 lo = mid + 1;
41 else
42 hi = mid;
43 }
44
45 const T* elem = (const T*)((const char*)base + hi * elemSize);
46 if (*elem != target)
47 {
48 if (*elem < target)
49 hi += 1;
50 hi = ~hi;
51 }
52 return hi;
53 }
54
55 template <typename T>
SkTSearch(const T * base,int count,const T & target,size_t elemSize,int (* compare)(const T &,const T &))56 int SkTSearch(const T* base, int count, const T& target, size_t elemSize,
57 int (*compare)(const T&, const T&))
58 {
59 SkASSERT(count >= 0);
60 if (count <= 0) {
61 return ~0;
62 }
63
64 SkASSERT(base != NULL); // base may be NULL if count is zero
65
66 int lo = 0;
67 int hi = count - 1;
68
69 while (lo < hi) {
70 int mid = (hi + lo) >> 1;
71 const T* elem = (const T*)((const char*)base + mid * elemSize);
72
73 if ((*compare)(*elem, target) < 0)
74 lo = mid + 1;
75 else
76 hi = mid;
77 }
78
79 const T* elem = (const T*)((const char*)base + hi * elemSize);
80 int pred = (*compare)(*elem, target);
81 if (pred != 0) {
82 if (pred < 0)
83 hi += 1;
84 hi = ~hi;
85 }
86 return hi;
87 }
88
89 template <typename T>
SkTSearch(const T ** base,int count,const T * target,size_t elemSize,int (* compare)(const T *,const T *))90 int SkTSearch(const T** base, int count, const T* target, size_t elemSize,
91 int (*compare)(const T*, const T*))
92 {
93 SkASSERT(count >= 0);
94 if (count <= 0)
95 return ~0;
96
97 SkASSERT(base != NULL); // base may be NULL if count is zero
98
99 int lo = 0;
100 int hi = count - 1;
101
102 while (lo < hi)
103 {
104 int mid = (hi + lo) >> 1;
105 const T* elem = *(const T**)((const char*)base + mid * elemSize);
106
107 if ((*compare)(elem, target) < 0)
108 lo = mid + 1;
109 else
110 hi = mid;
111 }
112
113 const T* elem = *(const T**)((const char*)base + hi * elemSize);
114 int pred = (*compare)(elem, target);
115 if (pred != 0)
116 {
117 if (pred < 0)
118 hi += 1;
119 hi = ~hi;
120 }
121 return hi;
122 }
123
124 int SkStrSearch(const char*const* base, int count, const char target[],
125 size_t target_len, size_t elemSize);
126 int SkStrSearch(const char*const* base, int count, const char target[],
127 size_t elemSize);
128
129 /** Like SkStrSearch, but treats target as if it were all lower-case. Assumes that
130 base points to a table of lower-case strings.
131 */
132 int SkStrLCSearch(const char*const* base, int count, const char target[],
133 size_t target_len, size_t elemSize);
134 int SkStrLCSearch(const char*const* base, int count, const char target[],
135 size_t elemSize);
136
137 /** Helper class to convert a string to lower-case, but only modifying the ascii
138 characters. This makes the routine very fast and never changes the string
139 length, but it is not suitable for linguistic purposes. Normally this is
140 used for buiding and searching string tables.
141 */
142 class SkAutoAsciiToLC {
143 public:
144 SkAutoAsciiToLC(const char str[], size_t len = (size_t)-1);
145 ~SkAutoAsciiToLC();
146
lc()147 const char* lc() const { return fLC; }
length()148 size_t length() const { return fLength; }
149
150 private:
151 char* fLC; // points to either the heap or fStorage
152 size_t fLength;
153 enum {
154 STORAGE = 64
155 };
156 char fStorage[STORAGE+1];
157 };
158
159 extern "C" {
160 typedef int (*SkQSortCompareProc)(const void*, const void*);
161 void SkQSort(void* base, size_t count, size_t elemSize, SkQSortCompareProc);
162 }
163
164 #endif
165
166