Line data Source code
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 : /**
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)
38 : template <typename T, typename K, typename LESS>
39 0 : int SkTSearch(const T base[], int count, const K& key, size_t elemSize, LESS& less)
40 : {
41 0 : SkASSERT(count >= 0);
42 0 : if (count <= 0) {
43 0 : return ~0;
44 : }
45 :
46 0 : SkASSERT(base != NULL); // base may be NULL if count is zero
47 :
48 0 : int lo = 0;
49 0 : int hi = count - 1;
50 :
51 0 : while (lo < hi) {
52 0 : int mid = lo + ((hi - lo) >> 1);
53 0 : const T* elem = (const T*)((const char*)base + mid * elemSize);
54 :
55 0 : if (less(*elem, key))
56 0 : lo = mid + 1;
57 : else
58 0 : hi = mid;
59 : }
60 :
61 0 : const T* elem = (const T*)((const char*)base + hi * elemSize);
62 0 : if (less(*elem, key)) {
63 0 : hi += 1;
64 0 : hi = ~hi;
65 0 : } else if (less(key, *elem)) {
66 0 : hi = ~hi;
67 : }
68 0 : return hi;
69 : }
70 :
71 : // Adapts a less-than function to a functor.
72 : template <typename T, bool (LESS)(const T&, const T&)> struct SkTLessFunctionToFunctorAdaptor {
73 0 : 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.
77 : template <typename T, bool (LESS)(const T&, const T&)>
78 0 : int SkTSearch(const T base[], int count, const T& target, size_t elemSize) {
79 : static SkTLessFunctionToFunctorAdaptor<T, LESS> functor;
80 0 : return SkTSearch(base, count, target, elemSize, functor);
81 : }
82 :
83 : // Adapts operator < to a functor.
84 : template <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 <.
89 : template <typename T>
90 : int 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.
96 : template <typename T, bool (LESS)(const T&, const T&)> struct SkTLessFunctionToPtrFunctorAdaptor {
97 0 : 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.
102 : template <typename T, bool (LESS)(const T&, const T&)>
103 0 : int SkTSearch(T* base[], int count, T* target, size_t elemSize) {
104 : static SkTLessFunctionToPtrFunctorAdaptor<T, LESS> functor;
105 0 : return SkTSearch(base, count, target, elemSize, functor);
106 : }
107 :
108 : int SkStrSearch(const char*const* base, int count, const char target[],
109 : size_t target_len, size_t elemSize);
110 : int 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 : */
116 : int SkStrLCSearch(const char*const* base, int count, const char target[],
117 : size_t target_len, size_t elemSize);
118 : int 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 : */
126 : class SkAutoAsciiToLC {
127 : public:
128 : SkAutoAsciiToLC(const char str[], size_t len = (size_t)-1);
129 : ~SkAutoAsciiToLC();
130 :
131 0 : const char* lc() const { return fLC; }
132 : size_t length() const { return fLength; }
133 :
134 : private:
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
|
