SkTSearch.h File Reference

#include "include/private/base/SkAssert.h"
#include <cstddef>

Go to the source code of this file.

Classes
class	SkAutoAsciiToLC

Macros
#define	SkCastForQSort(compare)   reinterpret_cast<int (*)(const void*, const void*)>(compare)

Functions
template<typename T , typename K , typename LESS >
int	SkTSearch (const T base[], int count, const K &key, size_t elemSize, const LESS &less)
template<typename T , bool(LESS)(const T &, const T &) >
int	SkTSearch (const T base[], int count, const T &target, size_t elemSize)
template<typename T >
int	SkTSearch (const T base[], int count, const T &target, size_t elemSize)
template<typename T , bool(LESS)(const T &, const T &) >
int	SkTSearch (T *base[], int count, T *target, size_t elemSize)
int	SkStrSearch (const char *const *base, int count, const char target[], size_t target_len, size_t elemSize)
int	SkStrSearch (const char *const *base, int count, const char target[], size_t elemSize)
int	SkStrLCSearch (const char *const *base, int count, const char target[], size_t target_len, size_t elemSize)
int	SkStrLCSearch (const char *const *base, int count, const char target[], size_t elemSize)

Macro Definition Documentation

SkCastForQSort

#define SkCastForQSort

(

compare

)

reinterpret_cast<int (*)(const void*, const void*)>(compare)

Definition at line 130 of file SkTSearch.h.

Function Documentation

SkStrLCSearch() [1/2]

int SkStrLCSearch	(	const char *const *	base,
		int	count,
		const char	target[],
		size_t	elemSize
	)

Definition at line 74 of file SkTSearch.cpp.

{
    return SkStrLCSearch(base, count, target, strlen(target), elemSize);
}

SkStrLCSearch() [2/2]

int SkStrLCSearch	(	const char *const *	base,
		int	count,
		const char	target[],
		size_t	target_len,
		size_t	elemSize
	)

Like SkStrSearch, but treats target as if it were all lower-case. Assumes that base points to a table of lower-case strings.

Definition at line 64 of file SkTSearch.cpp.

{
    SkASSERT(target);
 
    SkAutoAsciiToLC tolc(target, len);
 
    return SkStrSearch(base, count, tolc.lc(), len, elemSize);
}

SkStrSearch() [1/2]

int SkStrSearch	(	const char *const *	base,
		int	count,
		const char	target[],
		size_t	elemSize
	)

Definition at line 58 of file SkTSearch.cpp.

{
    return SkStrSearch(base, count, target, strlen(target), elemSize);
}

SkStrSearch() [2/2]

int SkStrSearch	(	const char *const *	base,
		int	count,
		const char	target[],
		size_t	target_len,
		size_t	elemSize
	)

Definition at line 22 of file SkTSearch.cpp.

{
    if (count <= 0)
        return ~0;
 
    SkASSERT(base != nullptr);
 
    int lo = 0;
    int hi = count - 1;
 
    while (lo < hi)
    {
        int mid = (hi + lo) >> 1;
        const char* elem = index_into_base(base, mid, elemSize);
 
        int cmp = strncmp(elem, target, target_len);
        if (cmp < 0)
            lo = mid + 1;
        else if (cmp > 0 || strlen(elem) > target_len)
            hi = mid;
        else
            return mid;
    }
 
    const char* elem = index_into_base(base, hi, elemSize);
    int cmp = strncmp(elem, target, target_len);
    if (cmp || strlen(elem) > target_len)
    {
        if (cmp < 0)
            hi += 1;
        hi = ~hi;
    }
    return hi;
}

SkTSearch() [1/4]

template<typename T , typename K , typename LESS >

int SkTSearch	(	const T	base[],
		int	count,
		const K &	key,
		size_t	elemSize,
		const LESS &	less
	)

All of the SkTSearch variants want to return the index (0...N-1) of the found element, or the bit-not of where to insert the element.

At a simple level, if the return value is negative, it was not found.

For clients that want to insert the new element if it was not found, use the following logic:

int index = SkTSearch(...); if (index >= 0) { // found at index } else { index = ~index; // now we are positive // insert at index }

Definition at line 41 of file SkTSearch.h.

{
    SkASSERT(count >= 0);
    if (count <= 0) {
        return ~0;
    }
 
    SkASSERT(base != nullptr); // base may be nullptr if count is zero
 
    int lo = 0;
    int hi = count - 1;
 
    while (lo < hi) {
        int mid = lo + ((hi - lo) >> 1);
        const T* elem = (const T*)((const char*)base + mid * elemSize);
 
        if (less(*elem, key))
            lo = mid + 1;
        else
            hi = mid;
    }
 
    const T* elem = (const T*)((const char*)base + hi * elemSize);
    if (less(*elem, key)) {
        hi += 1;
        hi = ~hi;
    } else if (less(key, *elem)) {
        hi = ~hi;
    }
    return hi;
}

SkTSearch() [2/4]

template<typename T , bool(LESS)(const T &, const T &) >

int SkTSearch	(	const T	base[],
		int	count,
		const T &	target,
		size_t	elemSize
	)

Definition at line 75 of file SkTSearch.h.

                                                                           {
    return SkTSearch(base, count, target, elemSize,
                     [](const T& a, const T& b) { return LESS(a, b); });
}

SkTSearch() [3/4]

template<typename T >

int SkTSearch	(	const T	base[],
		int	count,
		const T &	target,
		size_t	elemSize
	)

Definition at line 82 of file SkTSearch.h.

                                                                           {
    return SkTSearch(base, count, target, elemSize, [](const T& a, const T& b) { return a < b; });
}

SkTSearch() [4/4]

template<typename T , bool(LESS)(const T &, const T &) >

int SkTSearch	(	T *	base[],
		int	count,
		T *	target,
		size_t	elemSize
	)

Definition at line 89 of file SkTSearch.h.

                                                                {
    return SkTSearch(base, count, target, elemSize,
                     [](const T* t, const T* k) { return LESS(*t, *k); });
}