huwcampbell.com
Reactos
1//
2// bsearch.cpp
3//
4// Copyright (c) Microsoft Corporation. All rights reserved.
5//
6// Defines bsearch(), which performs a binary search over an array.
7//
8#include <corecrt_internal.h>
9#include <search.h>
10
11#ifdef _M_CEE
12 #define __fileDECL __clrcall
13#else
14 #define __fileDECL __cdecl
15#endif
16
17/***
18*char *bsearch() - do a binary search on an array
19*
20*Purpose:
21* Does a binary search of a sorted array for a key.
22*
23*Entry:
24* const char *key - key to search for
25* const char *base - base of sorted array to search
26* unsigned int num - number of elements in array
27* unsigned int width - number of bytes per element
28* int (*compare)() - pointer to function that compares two array
29* elements, returning neg when #1 < #2, pos when #1 > #2, and
30* 0 when they are equal. Function is passed pointers to two
31* array elements.
32*
33*Exit:
34* if key is found:
35* returns pointer to occurrence of key in array
36* if key is not found:
37* returns nullptr
38*
39*Exceptions:
40* Input parameters are validated. Refer to the validation section of the function.
41*
42*******************************************************************************/
43
44#ifdef __USE_CONTEXT
45 #define __COMPARE(context, p1, p2) (*compare)(context, p1, p2)
46#else
47 #define __COMPARE(context, p1, p2) (*compare)(p1, p2)
48#endif
49
50#ifndef _M_CEE
51extern "C"
52#endif
53
54_CRT_SECURITYSAFECRITICAL_ATTRIBUTE
55#ifdef __USE_CONTEXT
56void* __fileDECL bsearch_s(
57 void const* const key,
58 void const* const base,
59 size_t num,
60 size_t const width,
61 int (__fileDECL* const compare)(void*, void const*, void const*),
62 void* const context
63 )
64#else // __USE_CONTEXT
65void* __fileDECL bsearch(
66 void const* const key,
67 void const* const base,
68 size_t num,
69 size_t const width,
70 int (__fileDECL* const compare)(void const*, void const*)
71 )
72#endif // __USE_CONTEXT
73{
74 _VALIDATE_RETURN(base != nullptr || num == 0, EINVAL, nullptr);
75 _VALIDATE_RETURN(width > 0, EINVAL, nullptr);
76 _VALIDATE_RETURN(compare != nullptr, EINVAL, nullptr);
77
78 char const* lo = reinterpret_cast<char const*>(base);
79 char const* hi = reinterpret_cast<char const*>(base) + (num - 1) * width;
80
81 // Reentrancy diligence: Save (and unset) global-state mode to the stack before making callout to 'compare'
82 __crt_state_management::scoped_global_state_reset saved_state;
83
84 // We allow a nullptr key here because it breaks some older code and because
85 // we do not dereference this ourselves so we can't be sure that it's a
86 // problem for the comparison function
87
88 while (lo <= hi)
89 {
90 size_t const half = num / 2;
91 if (half != 0)
92 {
93 char const* const mid = lo + (num & 1 ? half : (half - 1)) * width;
94
95 int const result = __COMPARE(context, key, mid);
96 if (result == 0)
97 {
98 return const_cast<void*>(static_cast<void const*>(mid));
99 }
100 else if (result < 0)
101 {
102 hi = mid - width;
103 num = num & 1 ? half : half - 1;
104 }
105 else
106 {
107 lo = mid + width;
108 num = half;
109 }
110 }
111 else if (num != 0)
112 {
113 return __COMPARE(context, key, lo)
114 ? nullptr
115 : const_cast<void*>(static_cast<void const*>(lo));
116 }
117 else
118 {
119 break;
120 }
121 }
122
123 return nullptr;
124}
125
126#undef __COMPARE