rocPRIM
device_binary_search.hpp
1 // Copyright (c) 2019-2021 Advanced Micro Devices, Inc. All rights reserved.
2 //
3 // Permission is hereby granted, free of charge, to any person obtaining a copy
4 // of this software and associated documentation files (the "Software"), to deal
5 // in the Software without restriction, including without limitation the rights
6 // to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
7 // copies of the Software, and to permit persons to whom the Software is
8 // furnished to do so, subject to the following conditions:
9 //
10 // The above copyright notice and this permission notice shall be included in
11 // all copies or substantial portions of the Software.
12 //
13 // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
14 // IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
15 // FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
16 // AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
17 // LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
18 // OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
19 // THE SOFTWARE.
20 
21 #ifndef ROCPRIM_DEVICE_DETAIL_DEVICE_BINARY_SEARCH_HPP_
22 #define ROCPRIM_DEVICE_DETAIL_DEVICE_BINARY_SEARCH_HPP_
23 
24 BEGIN_ROCPRIM_NAMESPACE
25 
26 namespace detail
27 {
28 
29 template<class Size>
30 ROCPRIM_DEVICE ROCPRIM_INLINE
31 Size get_binary_search_middle(Size left, Size right)
32 {
33  const Size d = right - left;
34  return left + d / 2 + d / 64;
35 }
36 
37 template<class RandomAccessIterator, class Size, class T, class BinaryPredicate>
38 ROCPRIM_DEVICE ROCPRIM_INLINE
39 Size lower_bound_n(RandomAccessIterator first,
40  Size size,
41  const T& value,
42  BinaryPredicate compare_op)
43 {
44  Size left = 0;
45  Size right = size;
46  while(left < right)
47  {
48  const Size mid = get_binary_search_middle(left, right);
49  if(compare_op(first[mid], value))
50  {
51  left = mid + 1;
52  }
53  else
54  {
55  right = mid;
56  }
57  }
58  return left;
59 }
60 
61 template<class RandomAccessIterator, class Size, class T, class BinaryPredicate>
62 ROCPRIM_DEVICE ROCPRIM_INLINE
63 Size upper_bound_n(RandomAccessIterator first,
64  Size size,
65  const T& value,
66  BinaryPredicate compare_op)
67 {
68  Size left = 0;
69  Size right = size;
70  while(left < right)
71  {
72  const Size mid = get_binary_search_middle(left, right);
73  if(compare_op(value, first[mid]))
74  {
75  right = mid;
76  }
77  else
78  {
79  left = mid + 1;
80  }
81  }
82  return left;
83 }
84 
86 {
87  template<class HaystackIterator, class CompareOp, class Size, class T>
88  ROCPRIM_DEVICE ROCPRIM_INLINE
89  Size operator()(HaystackIterator haystack, Size size, const T& value, CompareOp compare_op) const
90  {
91  return lower_bound_n(haystack, size, value, compare_op);
92  }
93 };
94 
96 {
97  template<class HaystackIterator, class CompareOp, class Size, class T>
98  ROCPRIM_DEVICE ROCPRIM_INLINE
99  Size operator()(HaystackIterator haystack, Size size, const T& value, CompareOp compare_op) const
100  {
101  return upper_bound_n(haystack, size, value, compare_op);
102  }
103 };
104 
106 {
107  template<class HaystackIterator, class CompareOp, class Size, class T>
108  ROCPRIM_DEVICE ROCPRIM_INLINE
109  bool operator()(HaystackIterator haystack, Size size, const T& value, CompareOp compare_op) const
110  {
111  const Size n = lower_bound_n(haystack, size, value, compare_op);
112  return n != size && !compare_op(value, haystack[n]);
113  }
114 };
115 
116 } // end of detail namespace
117 
118 END_ROCPRIM_NAMESPACE
119 
120 #endif // ROCPRIM_DEVICE_DETAIL_DEVICE_BINARY_SEARCH_HPP_
Definition: device_binary_search.hpp:105
Definition: device_binary_search.hpp:85
Definition: device_binary_search.hpp:95
Deprecated: Configuration of device-level scan primitives.
Definition: block_histogram.hpp:62