cub/device/device_partition.cuh

File members: cub/device/device_partition.cuh

/******************************************************************************
 * Copyright (c) 2011, Duane Merrill.  All rights reserved.
 * Copyright (c) 2011-2022, 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.
 *
 ******************************************************************************/

#pragma once

#include <cub/config.cuh>

#if defined(_CCCL_IMPLICIT_SYSTEM_HEADER_GCC)
#  pragma GCC system_header
#elif defined(_CCCL_IMPLICIT_SYSTEM_HEADER_CLANG)
#  pragma clang system_header
#elif defined(_CCCL_IMPLICIT_SYSTEM_HEADER_MSVC)
#  pragma system_header
#endif // no system header

#include <cub/detail/choose_offset.cuh>
#include <cub/detail/nvtx.cuh>
#include <cub/device/dispatch/dispatch_select_if.cuh>
#include <cub/device/dispatch/dispatch_three_way_partition.cuh>
#include <cub/util_deprecated.cuh>

#include <iterator>

#include <stdio.h>

CUB_NAMESPACE_BEGIN

struct DevicePartition
{
  template <typename InputIteratorT,
            typename FlagIterator,
            typename OutputIteratorT,
            typename NumSelectedIteratorT,
            typename NumItemsT>
  CUB_RUNTIME_FUNCTION _CCCL_FORCEINLINE static cudaError_t Flagged(
    void* d_temp_storage,
    size_t& temp_storage_bytes,
    InputIteratorT d_in,
    FlagIterator d_flags,
    OutputIteratorT d_out,
    NumSelectedIteratorT d_num_selected_out,
    NumItemsT num_items,
    cudaStream_t stream = 0)
  {
    CUB_DETAIL_NVTX_RANGE_SCOPE_IF(d_temp_storage, "cub::DevicePartition::Flagged");
    using ChooseOffsetT = detail::choose_signed_offset<NumItemsT>;
    using OffsetT       = typename ChooseOffsetT::type; // Signed integer type for global offsets
    using SelectOp      = NullType; // Selection op (not used)
    using EqualityOp    = NullType; // Equality operator (not used)
    using DispatchSelectIfT =
      DispatchSelectIf<InputIteratorT,
                       FlagIterator,
                       OutputIteratorT,
                       NumSelectedIteratorT,
                       SelectOp,
                       EqualityOp,
                       OffsetT,
                       true>;

    // Check if the number of items exceeds the range covered by the selected signed offset type
    cudaError_t error = ChooseOffsetT::is_exceeding_offset_type(num_items);
    if (error)
    {
      return error;
    }

    return DispatchSelectIfT::Dispatch(
      d_temp_storage,
      temp_storage_bytes,
      d_in,
      d_flags,
      d_out,
      d_num_selected_out,
      SelectOp{},
      EqualityOp{},
      num_items,
      stream);
  }

#ifndef _CCCL_DOXYGEN_INVOKED // Do not document
  template <typename InputIteratorT,
            typename FlagIterator,
            typename OutputIteratorT,
            typename NumSelectedIteratorT,
            typename NumItemsT>
  CUB_DETAIL_RUNTIME_DEBUG_SYNC_IS_NOT_SUPPORTED CUB_RUNTIME_FUNCTION _CCCL_FORCEINLINE static cudaError_t Flagged(
    void* d_temp_storage,
    size_t& temp_storage_bytes,
    InputIteratorT d_in,
    FlagIterator d_flags,
    OutputIteratorT d_out,
    NumSelectedIteratorT d_num_selected_out,
    NumItemsT num_items,
    cudaStream_t stream,
    bool debug_synchronous)
  {
    CUB_DETAIL_RUNTIME_DEBUG_SYNC_USAGE_LOG

    return Flagged<InputIteratorT, FlagIterator, OutputIteratorT, NumSelectedIteratorT>(
      d_temp_storage, temp_storage_bytes, d_in, d_flags, d_out, d_num_selected_out, num_items, stream);
  }
#endif // _CCCL_DOXYGEN_INVOKED

  template <typename InputIteratorT,
            typename OutputIteratorT,
            typename NumSelectedIteratorT,
            typename SelectOp,
            typename NumItemsT>
  CUB_RUNTIME_FUNCTION _CCCL_FORCEINLINE static cudaError_t
  If(void* d_temp_storage,
     size_t& temp_storage_bytes,
     InputIteratorT d_in,
     OutputIteratorT d_out,
     NumSelectedIteratorT d_num_selected_out,
     NumItemsT num_items,
     SelectOp select_op,
     cudaStream_t stream = 0)
  {
    CUB_DETAIL_NVTX_RANGE_SCOPE_IF(d_temp_storage, "cub::DevicePartition::If");
    using ChooseOffsetT = detail::choose_signed_offset<NumItemsT>;
    using OffsetT       = typename ChooseOffsetT::type; // Signed integer type for global offsets
    using FlagIterator  = NullType*; // FlagT iterator type (not used)
    using EqualityOp    = NullType; // Equality operator (not used)

    // Check if the number of items exceeds the range covered by the selected signed offset type
    cudaError_t error = ChooseOffsetT::is_exceeding_offset_type(num_items);
    if (error)
    {
      return error;
    }

    using DispatchSelectIfT =
      DispatchSelectIf<InputIteratorT,
                       FlagIterator,
                       OutputIteratorT,
                       NumSelectedIteratorT,
                       SelectOp,
                       EqualityOp,
                       OffsetT,
                       true>;

    return DispatchSelectIfT::Dispatch(
      d_temp_storage,
      temp_storage_bytes,
      d_in,
      nullptr,
      d_out,
      d_num_selected_out,
      select_op,
      EqualityOp{},
      num_items,
      stream);
  }

#ifndef _CCCL_DOXYGEN_INVOKED // Do not document
  template <typename InputIteratorT,
            typename OutputIteratorT,
            typename NumSelectedIteratorT,
            typename SelectOp,
            typename NumItemsT>
  CUB_DETAIL_RUNTIME_DEBUG_SYNC_IS_NOT_SUPPORTED CUB_RUNTIME_FUNCTION _CCCL_FORCEINLINE static cudaError_t
  If(void* d_temp_storage,
     size_t& temp_storage_bytes,
     InputIteratorT d_in,
     OutputIteratorT d_out,
     NumSelectedIteratorT d_num_selected_out,
     NumItemsT num_items,
     SelectOp select_op,
     cudaStream_t stream,
     bool debug_synchronous)
  {
    CUB_DETAIL_RUNTIME_DEBUG_SYNC_USAGE_LOG

    return If<InputIteratorT, OutputIteratorT, NumSelectedIteratorT, SelectOp, NumItemsT>(
      d_temp_storage, temp_storage_bytes, d_in, d_out, d_num_selected_out, num_items, select_op, stream);
  }
#endif // _CCCL_DOXYGEN_INVOKED

private:
  template <bool IS_DESCENDING,
            typename KeyT,
            typename ValueT,
            typename OffsetT,
            typename BeginOffsetIteratorT,
            typename EndOffsetIteratorT,
            typename SelectedPolicy>
  friend class DispatchSegmentedSort;

  // Internal version without NVTX range
  template <typename InputIteratorT,
            typename FirstOutputIteratorT,
            typename SecondOutputIteratorT,
            typename UnselectedOutputIteratorT,
            typename NumSelectedIteratorT,
            typename SelectFirstPartOp,
            typename SelectSecondPartOp>
  CUB_RUNTIME_FUNCTION _CCCL_FORCEINLINE static cudaError_t IfNoNVTX(
    void* d_temp_storage,
    std::size_t& temp_storage_bytes,
    InputIteratorT d_in,
    FirstOutputIteratorT d_first_part_out,
    SecondOutputIteratorT d_second_part_out,
    UnselectedOutputIteratorT d_unselected_out,
    NumSelectedIteratorT d_num_selected_out,
    int num_items,
    SelectFirstPartOp select_first_part_op,
    SelectSecondPartOp select_second_part_op,
    cudaStream_t stream = 0)
  {
    using OffsetT                      = int;
    using DispatchThreeWayPartitionIfT = DispatchThreeWayPartitionIf<
      InputIteratorT,
      FirstOutputIteratorT,
      SecondOutputIteratorT,
      UnselectedOutputIteratorT,
      NumSelectedIteratorT,
      SelectFirstPartOp,
      SelectSecondPartOp,
      OffsetT>;

    return DispatchThreeWayPartitionIfT::Dispatch(
      d_temp_storage,
      temp_storage_bytes,
      d_in,
      d_first_part_out,
      d_second_part_out,
      d_unselected_out,
      d_num_selected_out,
      select_first_part_op,
      select_second_part_op,
      num_items,
      stream);
  }

public:
  template <typename InputIteratorT,
            typename FirstOutputIteratorT,
            typename SecondOutputIteratorT,
            typename UnselectedOutputIteratorT,
            typename NumSelectedIteratorT,
            typename SelectFirstPartOp,
            typename SelectSecondPartOp>
  CUB_RUNTIME_FUNCTION _CCCL_FORCEINLINE static cudaError_t
  If(void* d_temp_storage,
     std::size_t& temp_storage_bytes,
     InputIteratorT d_in,
     FirstOutputIteratorT d_first_part_out,
     SecondOutputIteratorT d_second_part_out,
     UnselectedOutputIteratorT d_unselected_out,
     NumSelectedIteratorT d_num_selected_out,
     int num_items,
     SelectFirstPartOp select_first_part_op,
     SelectSecondPartOp select_second_part_op,
     cudaStream_t stream = 0)
  {
    CUB_DETAIL_NVTX_RANGE_SCOPE_IF(d_temp_storage, "cub::DevicePartition::If");
    return IfNoNVTX(
      d_temp_storage,
      temp_storage_bytes,
      d_in,
      d_first_part_out,
      d_second_part_out,
      d_unselected_out,
      d_num_selected_out,
      num_items,
      select_first_part_op,
      select_second_part_op,
      stream);
  }

#ifndef _CCCL_DOXYGEN_INVOKED // Do not document
  template <typename InputIteratorT,
            typename FirstOutputIteratorT,
            typename SecondOutputIteratorT,
            typename UnselectedOutputIteratorT,
            typename NumSelectedIteratorT,
            typename SelectFirstPartOp,
            typename SelectSecondPartOp>
  CUB_DETAIL_RUNTIME_DEBUG_SYNC_IS_NOT_SUPPORTED CUB_RUNTIME_FUNCTION _CCCL_FORCEINLINE static cudaError_t
  If(void* d_temp_storage,
     std::size_t& temp_storage_bytes,
     InputIteratorT d_in,
     FirstOutputIteratorT d_first_part_out,
     SecondOutputIteratorT d_second_part_out,
     UnselectedOutputIteratorT d_unselected_out,
     NumSelectedIteratorT d_num_selected_out,
     int num_items,
     SelectFirstPartOp select_first_part_op,
     SelectSecondPartOp select_second_part_op,
     cudaStream_t stream,
     bool debug_synchronous)
  {
    CUB_DETAIL_RUNTIME_DEBUG_SYNC_USAGE_LOG

    return If<InputIteratorT,
              FirstOutputIteratorT,
              SecondOutputIteratorT,
              UnselectedOutputIteratorT,
              NumSelectedIteratorT,
              SelectFirstPartOp,
              SelectSecondPartOp>(
      d_temp_storage,
      temp_storage_bytes,
      d_in,
      d_first_part_out,
      d_second_part_out,
      d_unselected_out,
      d_num_selected_out,
      num_items,
      select_first_part_op,
      select_second_part_op,
      stream);
  }
#endif // _CCCL_DOXYGEN_INVOKED
};

CUB_NAMESPACE_END