bsearch.cpp File Reference

#include <corecrt_internal.h>
#include <search.h>

Include dependency graph for bsearch.cpp:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Macros
#define	__fileDECL   __cdecl
#define	__COMPARE(context, p1, p2)   (*compare)(p1, p2)

Functions
_CRT_SECURITYSAFECRITICAL_ATTRIBUTE void *__fileDECL	bsearch (void const *const key, void const *const base, size_t num, size_t const width, int(__fileDECL *const compare)(void const *, void const *))

Macro Definition Documentation

__COMPARE

#define __COMPARE	(		context,
			p1,
			p2
	)		(*compare)(p1, p2)

Definition at line 47 of file bsearch.cpp.

__fileDECL

#define __fileDECL   __cdecl

Definition at line 14 of file bsearch.cpp.

Function Documentation

bsearch()

_CRT_SECURITYSAFECRITICAL_ATTRIBUTE void *__fileDECL bsearch	(	void const *const	key,
		void const *const	base,
		size_t	num,
		size_t const	width,
		int(__fileDECL *const compare)(void const *, void const *)
	)

Definition at line 65 of file bsearch.cpp.

{
    _VALIDATE_RETURN(base != nullptr || num == 0, EINVAL, nullptr);
    _VALIDATE_RETURN(width > 0, EINVAL, nullptr);
    _VALIDATE_RETURN(compare != nullptr, EINVAL, nullptr);
 
    char const* lo = reinterpret_cast<char const*>(base);
    char const* hi = reinterpret_cast<char const*>(base) + (num - 1) * width;
 
    // Reentrancy diligence: Save (and unset) global-state mode to the stack before making callout to 'compare'
    __crt_state_management::scoped_global_state_reset saved_state;
 
    // We allow a nullptr key here because it breaks some older code and because
    // we do not dereference this ourselves so we can't be sure that it's a
    // problem for the comparison function
 
    while (lo <= hi)
    {
        size_t const half = num / 2;
        if (half != 0)
        {
            char const* const mid = lo + (num & 1 ? half : (half - 1)) * width;
 
            int const result = __COMPARE(context, key, mid);
            if (result == 0)
            {
                return const_cast<void*>(static_cast<void const*>(mid));
            }
            else if (result < 0)
            {
                hi = mid - width;
                num = num & 1 ? half : half - 1;
            }
            else
            {
                lo = mid + width;
                num = half;
            }
        }
        else if (num != 0)
        {
            return __COMPARE(context, key, lo)
                ? nullptr
                : const_cast<void*>(static_cast<void const*>(lo));
        }
        else
        {
            break;
        }
    }
 
    return nullptr;
}