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 #ifndef SkTSearch_DEFINED
11 #define SkTSearch_DEFINED
12
13 #include "SkTypes.h"
14
15 template <typename T>
SkTSearch(const T * base,int count,const T & target,size_t elemSize)16 int SkTSearch(const T* base, int count, const T& target, size_t elemSize)
17 {
18 SkASSERT(count >= 0);
19 if (count <= 0)
20 return ~0;
21
22 SkASSERT(base != NULL); // base may be NULL if count is zero
23
24 int lo = 0;
25 int hi = count - 1;
26
27 while (lo < hi)
28 {
29 int mid = (hi + lo) >> 1;
30 const T* elem = (const T*)((const char*)base + mid * elemSize);
31
32 if (*elem < target)
33 lo = mid + 1;
34 else
35 hi = mid;
36 }
37
38 const T* elem = (const T*)((const char*)base + hi * elemSize);
39 if (*elem != target)
40 {
41 if (*elem < target)
42 hi += 1;
43 hi = ~hi;
44 }
45 return hi;
46 }
47
48 template <typename T>
SkTSearch(const T * base,int count,const T & target,size_t elemSize,int (* compare)(const T &,const T &))49 int SkTSearch(const T* base, int count, const T& target, size_t elemSize,
50 int (*compare)(const T&, const T&))
51 {
52 SkASSERT(count >= 0);
53 if (count <= 0) {
54 return ~0;
55 }
56
57 SkASSERT(base != NULL); // base may be NULL if count is zero
58
59 int lo = 0;
60 int hi = count - 1;
61
62 while (lo < hi) {
63 int mid = (hi + lo) >> 1;
64 const T* elem = (const T*)((const char*)base + mid * elemSize);
65
66 if ((*compare)(*elem, target) < 0)
67 lo = mid + 1;
68 else
69 hi = mid;
70 }
71
72 const T* elem = (const T*)((const char*)base + hi * elemSize);
73 int pred = (*compare)(*elem, target);
74 if (pred != 0) {
75 if (pred < 0)
76 hi += 1;
77 hi = ~hi;
78 }
79 return hi;
80 }
81
82 template <typename T>
SkTSearch(const T ** base,int count,const T * target,size_t elemSize,int (* compare)(const T *,const T *))83 int SkTSearch(const T** base, int count, const T* target, size_t elemSize,
84 int (*compare)(const T*, const T*))
85 {
86 SkASSERT(count >= 0);
87 if (count <= 0)
88 return ~0;
89
90 SkASSERT(base != NULL); // base may be NULL if count is zero
91
92 int lo = 0;
93 int hi = count - 1;
94
95 while (lo < hi)
96 {
97 int mid = (hi + lo) >> 1;
98 const T* elem = *(const T**)((const char*)base + mid * elemSize);
99
100 if ((*compare)(elem, target) < 0)
101 lo = mid + 1;
102 else
103 hi = mid;
104 }
105
106 const T* elem = *(const T**)((const char*)base + hi * elemSize);
107 int pred = (*compare)(elem, target);
108 if (pred != 0)
109 {
110 if (pred < 0)
111 hi += 1;
112 hi = ~hi;
113 }
114 return hi;
115 }
116
117 int SkStrSearch(const char*const* base, int count, const char target[],
118 size_t target_len, size_t elemSize);
119 int SkStrSearch(const char*const* base, int count, const char target[],
120 size_t elemSize);
121
122 /** Like SkStrSearch, but treats target as if it were all lower-case. Assumes that
123 base points to a table of lower-case strings.
124 */
125 int SkStrLCSearch(const char*const* base, int count, const char target[],
126 size_t target_len, size_t elemSize);
127 int SkStrLCSearch(const char*const* base, int count, const char target[],
128 size_t elemSize);
129
130 /** Helper class to convert a string to lower-case, but only modifying the ascii
131 characters. This makes the routine very fast and never changes the string
132 length, but it is not suitable for linguistic purposes. Normally this is
133 used for buiding and searching string tables.
134 */
135 class SkAutoAsciiToLC {
136 public:
137 SkAutoAsciiToLC(const char str[], size_t len = (size_t)-1);
138 ~SkAutoAsciiToLC();
139
lc()140 const char* lc() const { return fLC; }
length()141 size_t length() const { return fLength; }
142
143 private:
144 char* fLC; // points to either the heap or fStorage
145 size_t fLength;
146 enum {
147 STORAGE = 64
148 };
149 char fStorage[STORAGE+1];
150 };
151
152 extern "C" {
153 typedef int (*SkQSortCompareProc)(const void*, const void*);
154 void SkQSort(void* base, size_t count, size_t elemSize, SkQSortCompareProc);
155 }
156
157 #endif
158
159