00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017 #ifndef SkTSearch_DEFINED
00018 #define SkTSearch_DEFINED
00019
00020 #include "SkTypes.h"
00021
00022 template <typename T>
00023 int SkTSearch(const T* base, int count, const T& target, size_t elemSize)
00024 {
00025 SkASSERT(count >= 0);
00026 if (count <= 0)
00027 return ~0;
00028
00029 SkASSERT(base != NULL);
00030
00031 int lo = 0;
00032 int hi = count - 1;
00033
00034 while (lo < hi)
00035 {
00036 int mid = (hi + lo) >> 1;
00037 const T* elem = (const T*)((const char*)base + mid * elemSize);
00038
00039 if (*elem < target)
00040 lo = mid + 1;
00041 else
00042 hi = mid;
00043 }
00044
00045 const T* elem = (const T*)((const char*)base + hi * elemSize);
00046 if (*elem != target)
00047 {
00048 if (*elem < target)
00049 hi += 1;
00050 hi = ~hi;
00051 }
00052 return hi;
00053 }
00054
00055 template <typename T>
00056 int SkTSearch(const T* base, int count, const T& target, size_t elemSize,
00057 int (*compare)(const T&, const T&))
00058 {
00059 SkASSERT(count >= 0);
00060 if (count <= 0) {
00061 return ~0;
00062 }
00063
00064 SkASSERT(base != NULL);
00065
00066 int lo = 0;
00067 int hi = count - 1;
00068
00069 while (lo < hi) {
00070 int mid = (hi + lo) >> 1;
00071 const T* elem = (const T*)((const char*)base + mid * elemSize);
00072
00073 if ((*compare)(*elem, target) < 0)
00074 lo = mid + 1;
00075 else
00076 hi = mid;
00077 }
00078
00079 const T* elem = (const T*)((const char*)base + hi * elemSize);
00080 int pred = (*compare)(*elem, target);
00081 if (pred != 0) {
00082 if (pred < 0)
00083 hi += 1;
00084 hi = ~hi;
00085 }
00086 return hi;
00087 }
00088
00089 template <typename T>
00090 int SkTSearch(const T** base, int count, const T* target, size_t elemSize,
00091 int (*compare)(const T*, const T*))
00092 {
00093 SkASSERT(count >= 0);
00094 if (count <= 0)
00095 return ~0;
00096
00097 SkASSERT(base != NULL);
00098
00099 int lo = 0;
00100 int hi = count - 1;
00101
00102 while (lo < hi)
00103 {
00104 int mid = (hi + lo) >> 1;
00105 const T* elem = *(const T**)((const char*)base + mid * elemSize);
00106
00107 if ((*compare)(elem, target) < 0)
00108 lo = mid + 1;
00109 else
00110 hi = mid;
00111 }
00112
00113 const T* elem = *(const T**)((const char*)base + hi * elemSize);
00114 int pred = (*compare)(elem, target);
00115 if (pred != 0)
00116 {
00117 if (pred < 0)
00118 hi += 1;
00119 hi = ~hi;
00120 }
00121 return hi;
00122 }
00123
00124 int SkStrSearch(const char*const* base, int count, const char target[],
00125 size_t target_len, size_t elemSize);
00126 int SkStrSearch(const char*const* base, int count, const char target[],
00127 size_t elemSize);
00128
00132 int SkStrLCSearch(const char*const* base, int count, const char target[],
00133 size_t target_len, size_t elemSize);
00134 int SkStrLCSearch(const char*const* base, int count, const char target[],
00135 size_t elemSize);
00136
00142 class SkAutoAsciiToLC {
00143 public:
00144 SkAutoAsciiToLC(const char str[], size_t len = (size_t)-1);
00145 ~SkAutoAsciiToLC();
00146
00147 const char* lc() const { return fLC; }
00148 size_t length() const { return fLength; }
00149
00150 private:
00151 char* fLC;
00152 size_t fLength;
00153 enum {
00154 STORAGE = 64
00155 };
00156 char fStorage[STORAGE+1];
00157 };
00158
00159 extern "C" {
00160 typedef int (*SkQSortCompareProc)(const void*, const void*);
00161 void SkQSort(void* base, size_t count, size_t elemSize, SkQSortCompareProc);
00162 }
00163
00164 #endif
00165