Spaces:
Runtime error
Runtime error
/****************************************************************************** | |
* Copyright (c) 2011, Duane Merrill. All rights reserved. | |
* Copyright (c) 2011-2018, NVIDIA CORPORATION. All rights reserved. | |
* | |
* Redistribution and use in source and binary forms, with or without | |
* modification, are permitted provided that the following conditions are met: | |
* * Redistributions of source code must retain the above copyright | |
* notice, this list of conditions and the following disclaimer. | |
* * Redistributions in binary form must reproduce the above copyright | |
* notice, this list of conditions and the following disclaimer in the | |
* documentation and/or other materials provided with the distribution. | |
* * Neither the name of the NVIDIA CORPORATION nor the | |
* names of its contributors may be used to endorse or promote products | |
* derived from this software without specific prior written permission. | |
* | |
* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND | |
* ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED | |
* WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE | |
* DISCLAIMED. IN NO EVENT SHALL NVIDIA CORPORATION BE LIABLE FOR ANY | |
* DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES | |
* (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; | |
* LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND | |
* ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT | |
* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS | |
* SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. | |
* | |
******************************************************************************/ | |
/** | |
* \file | |
* Thread utilities for sequential search | |
*/ | |
#pragma once | |
#include <iterator> | |
#include "../util_namespace.cuh" | |
#include "../config.cuh" | |
/// Optional outer namespace(s) | |
CUB_NS_PREFIX | |
/// CUB namespace | |
namespace cub { | |
/** | |
* Computes the begin offsets into A and B for the specific diagonal | |
*/ | |
template < | |
typename AIteratorT, | |
typename BIteratorT, | |
typename OffsetT, | |
typename CoordinateT> | |
__host__ __device__ __forceinline__ void MergePathSearch( | |
OffsetT diagonal, | |
AIteratorT a, | |
BIteratorT b, | |
OffsetT a_len, | |
OffsetT b_len, | |
CoordinateT& path_coordinate) | |
{ | |
/// The value type of the input iterator | |
typedef typename std::iterator_traits<AIteratorT>::value_type T; | |
OffsetT split_min = CUB_MAX(diagonal - b_len, 0); | |
OffsetT split_max = CUB_MIN(diagonal, a_len); | |
while (split_min < split_max) | |
{ | |
OffsetT split_pivot = (split_min + split_max) >> 1; | |
if (a[split_pivot] <= b[diagonal - split_pivot - 1]) | |
{ | |
// Move candidate split range up A, down B | |
split_min = split_pivot + 1; | |
} | |
else | |
{ | |
// Move candidate split range up B, down A | |
split_max = split_pivot; | |
} | |
} | |
path_coordinate.x = CUB_MIN(split_min, a_len); | |
path_coordinate.y = diagonal - split_min; | |
} | |
/** | |
* \brief Returns the offset of the first value within \p input which does not compare less than \p val | |
*/ | |
template < | |
typename InputIteratorT, | |
typename OffsetT, | |
typename T> | |
__device__ __forceinline__ OffsetT LowerBound( | |
InputIteratorT input, ///< [in] Input sequence | |
OffsetT num_items, ///< [in] Input sequence length | |
T val) ///< [in] Search key | |
{ | |
OffsetT retval = 0; | |
while (num_items > 0) | |
{ | |
OffsetT half = num_items >> 1; | |
if (input[retval + half] < val) | |
{ | |
retval = retval + (half + 1); | |
num_items = num_items - (half + 1); | |
} | |
else | |
{ | |
num_items = half; | |
} | |
} | |
return retval; | |
} | |
/** | |
* \brief Returns the offset of the first value within \p input which compares greater than \p val | |
*/ | |
template < | |
typename InputIteratorT, | |
typename OffsetT, | |
typename T> | |
__device__ __forceinline__ OffsetT UpperBound( | |
InputIteratorT input, ///< [in] Input sequence | |
OffsetT num_items, ///< [in] Input sequence length | |
T val) ///< [in] Search key | |
{ | |
OffsetT retval = 0; | |
while (num_items > 0) | |
{ | |
OffsetT half = num_items >> 1; | |
if (val < input[retval + half]) | |
{ | |
num_items = half; | |
} | |
else | |
{ | |
retval = retval + (half + 1); | |
num_items = num_items - (half + 1); | |
} | |
} | |
return retval; | |
} | |
} // CUB namespace | |
CUB_NS_POSTFIX // Optional outer namespace(s) | |