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
15template <typename T>
16int 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
48template <typename T>
49int 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
82template <typename T>
83int 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
117int SkStrSearch(const char*const* base, int count, const char target[],
118                size_t target_len, size_t elemSize);
119int 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*/
125int SkStrLCSearch(const char*const* base, int count, const char target[],
126                  size_t target_len, size_t elemSize);
127int 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*/
135class SkAutoAsciiToLC {
136public:
137    SkAutoAsciiToLC(const char str[], size_t len = (size_t)-1);
138    ~SkAutoAsciiToLC();
139
140    const char* lc() const { return fLC; }
141    size_t      length() const { return fLength; }
142
143private:
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
152extern "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