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) | |