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 "include/core/SkTypes.h"
14
15/**
16 * All of the SkTSearch variants want to return the index (0...N-1) of the
17 * found element, or the bit-not of where to insert the element.
18 *
19 * At a simple level, if the return value is negative, it was not found.
20 *
21 * For clients that want to insert the new element if it was not found, use
22 * the following logic:
23 *
24 * int index = SkTSearch(...);
25 * if (index >= 0) {
26 * // found at index
27 * } else {
28 * index = ~index; // now we are positive
29 * // insert at index
30 * }
31 */
32
33
34// The most general form of SkTSearch takes an array of T and a key of type K. A functor, less, is
35// used to perform comparisons. It has two function operators:
36// bool operator() (const T& t, const K& k)
37// bool operator() (const K& t, const T& k)
38template <typename T, typename K, typename LESS>
39int SkTSearch(const T base[], int count, const K& key, size_t elemSize, LESS& less)
40{
41 SkASSERT(count >= 0);
42 if (count <= 0) {
43 return ~0;
44 }
45
46 SkASSERT(base != nullptr); // base may be nullptr if count is zero
47
48 int lo = 0;
49 int hi = count - 1;
50
51 while (lo < hi) {
52 int mid = lo + ((hi - lo) >> 1);
53 const T* elem = (const T*)((const char*)base + mid * elemSize);
54
55 if (less(*elem, key))
56 lo = mid + 1;
57 else
58 hi = mid;
59 }
60
61 const T* elem = (const T*)((const char*)base + hi * elemSize);
62 if (less(*elem, key)) {
63 hi += 1;
64 hi = ~hi;
65 } else if (less(key, *elem)) {
66 hi = ~hi;
67 }
68 return hi;
69}
70
71// Adapts a less-than function to a functor.
72template <typename T, bool (LESS)(const T&, const T&)> struct SkTLessFunctionToFunctorAdaptor {
73 bool operator()(const T& a, const T& b) { return LESS(a, b); }
74};
75
76// Specialization for case when T==K and the caller wants to use a function rather than functor.
77template <typename T, bool (LESS)(const T&, const T&)>
78int SkTSearch(const T base[], int count, const T& target, size_t elemSize) {
79 static SkTLessFunctionToFunctorAdaptor<T, LESS> functor;
80 return SkTSearch(base, count, target, elemSize, functor);
81}
82
83// Adapts operator < to a functor.
84template <typename T> struct SkTLessFunctor {
85 bool operator()(const T& a, const T& b) { return a < b; }
86};
87
88// Specialization for T==K, compare using op <.
89template <typename T>
90int SkTSearch(const T base[], int count, const T& target, size_t elemSize) {
91 static SkTLessFunctor<T> functor;
92 return SkTSearch(base, count, target, elemSize, functor);
93}
94
95// Similar to SkLessFunctionToFunctorAdaptor but makes the functor interface take T* rather than T.
96template <typename T, bool (LESS)(const T&, const T&)> struct SkTLessFunctionToPtrFunctorAdaptor {
97 bool operator() (const T* t, const T* k) { return LESS(*t, *k); }
98};
99
100// Specialization for case where domain is an array of T* and the key value is a T*, and you want
101// to compare the T objects, not the pointers.
102template <typename T, bool (LESS)(const T&, const T&)>
103int SkTSearch(T* base[], int count, T* target, size_t elemSize) {
104 static SkTLessFunctionToPtrFunctorAdaptor<T, LESS> functor;
105 return SkTSearch(base, count, target, elemSize, functor);
106}
107
108int SkStrSearch(const char*const* base, int count, const char target[],
109 size_t target_len, size_t elemSize);
110int SkStrSearch(const char*const* base, int count, const char target[],
111 size_t elemSize);
112
113/** Like SkStrSearch, but treats target as if it were all lower-case. Assumes that
114 base points to a table of lower-case strings.
115*/
116int SkStrLCSearch(const char*const* base, int count, const char target[],
117 size_t target_len, size_t elemSize);
118int SkStrLCSearch(const char*const* base, int count, const char target[],
119 size_t elemSize);
120
121/** Helper class to convert a string to lower-case, but only modifying the ascii
122 characters. This makes the routine very fast and never changes the string
123 length, but it is not suitable for linguistic purposes. Normally this is
124 used for buiding and searching string tables.
125*/
126class SkAutoAsciiToLC {
127public:
128 SkAutoAsciiToLC(const char str[], size_t len = (size_t)-1);
129 ~SkAutoAsciiToLC();
130
131 const char* lc() const { return fLC; }
132 size_t length() const { return fLength; }
133
134private:
135 char* fLC; // points to either the heap or fStorage
136 size_t fLength;
137 enum {
138 STORAGE = 64
139 };
140 char fStorage[STORAGE+1];
141};
142
143// Helper when calling qsort with a compare proc that has typed its arguments
144#define SkCastForQSort(compare) reinterpret_cast<int (*)(const void*, const void*)>(compare)
145
146#endif
147