/home/docs/checkouts/readthedocs.org/user_builds/advanced-micro-devices-hipcub/checkouts/docs-5.7.0/hipcub/include/hipcub/backend/rocprim/thread/thread_search.hpp Source File

/home/docs/checkouts/readthedocs.org/user_builds/advanced-micro-devices-hipcub/checkouts/docs-5.7.0/hipcub/include/hipcub/backend/rocprim/thread/thread_search.hpp Source File#

hipCUB: /home/docs/checkouts/readthedocs.org/user_builds/advanced-micro-devices-hipcub/checkouts/docs-5.7.0/hipcub/include/hipcub/backend/rocprim/thread/thread_search.hpp Source File
thread_search.hpp
1 /******************************************************************************
2  * Copyright (c) 2011, Duane Merrill. All rights reserved.
3  * Copyright (c) 2011-2018, NVIDIA CORPORATION. All rights reserved.
4  * Modifications Copyright (c) 2021, Advanced Micro Devices, Inc. All rights reserved.
5  *
6  * Redistribution and use in source and binary forms, with or without
7  * modification, are permitted provided that the following conditions are met:
8  * * Redistributions of source code must retain the above copyright
9  * notice, this list of conditions and the following disclaimer.
10  * * Redistributions in binary form must reproduce the above copyright
11  * notice, this list of conditions and the following disclaimer in the
12  * documentation and/or other materials provided with the distribution.
13  * * Neither the name of the NVIDIA CORPORATION nor the
14  * names of its contributors may be used to endorse or promote products
15  * derived from this software without specific prior written permission.
16  *
17  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
18  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
19  * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
20  * DISCLAIMED. IN NO EVENT SHALL NVIDIA CORPORATION BE LIABLE FOR ANY
21  * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
22  * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
23  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
24  * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
26  * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27  *
28  ******************************************************************************/
29 
30  #ifndef HIBCUB_ROCPRIM_THREAD_THREAD_SEARCH_HPP_
31  #define HIBCUB_ROCPRIM_THREAD_THREAD_SEARCH_HPP_
32 
33  #include <iterator>
34 
35  BEGIN_HIPCUB_NAMESPACE
36 
37 #ifndef DOXYGEN_SHOULD_SKIP_THIS // Do not document
38 
43 template <
44  typename AIteratorT,
45  typename BIteratorT,
46  typename OffsetT,
47  typename CoordinateT>
48 __host__ __device__ __forceinline__ void MergePathSearch(
49  OffsetT diagonal,
50  AIteratorT a,
51  BIteratorT b,
52  OffsetT a_len,
53  OffsetT b_len,
54  CoordinateT& path_coordinate)
55 {
56  OffsetT split_min = CUB_MAX(diagonal - b_len, 0);
57  OffsetT split_max = CUB_MIN(diagonal, a_len);
58 
59  while (split_min < split_max)
60  {
61  OffsetT split_pivot = (split_min + split_max) >> 1;
62  if (a[split_pivot] <= b[diagonal - split_pivot - 1])
63  {
64  // Move candidate split range up A, down B
65  split_min = split_pivot + 1;
66  }
67  else
68  {
69  // Move candidate split range up B, down A
70  split_max = split_pivot;
71  }
72  }
73 
74  path_coordinate.x = CUB_MIN(split_min, a_len);
75  path_coordinate.y = diagonal - split_min;
76 }
77 
78 
79 
83 template <
84  typename InputIteratorT,
85  typename OffsetT,
86  typename T>
87 __device__ __forceinline__ OffsetT LowerBound(
88  InputIteratorT input,
89  OffsetT num_items,
90  T val)
91 {
92  OffsetT retval = 0;
93  while (num_items > 0)
94  {
95  OffsetT half = num_items >> 1;
96  if (input[retval + half] < val)
97  {
98  retval = retval + (half + 1);
99  num_items = num_items - (half + 1);
100  }
101  else
102  {
103  num_items = half;
104  }
105  }
106 
107  return retval;
108 }
109 
110 
114 template <
115  typename InputIteratorT,
116  typename OffsetT,
117  typename T>
118 __device__ __forceinline__ OffsetT UpperBound(
119  InputIteratorT input,
120  OffsetT num_items,
121  T val)
122 {
123  OffsetT retval = 0;
124  while (num_items > 0)
125  {
126  OffsetT half = num_items >> 1;
127  if (val < input[retval + half])
128  {
129  num_items = half;
130  }
131  else
132  {
133  retval = retval + (half + 1);
134  num_items = num_items - (half + 1);
135  }
136  }
137 
138  return retval;
139 }
140 
141 #endif
142 
143 END_HIPCUB_NAMESPACE
144 
145 #endif // HIBCUB_ROCPRIM_THREAD_THREAD_SCAN_HPP_