20 #include <cudf/detail/utilities/assert.cuh>
21 #include <cudf/hashing/detail/hash_functions.cuh>
22 #include <cudf/hashing/detail/hashing.hpp>
27 #include <cuda/std/limits>
28 #include <thrust/equal.h>
29 #include <thrust/execution_policy.h>
30 #include <thrust/iterator/counting_iterator.h>
31 #include <thrust/transform_reduce.h>
58 template <
typename Element>
59 __device__
weak_ordering compare_elements(Element lhs, Element rhs)
63 }
else if (rhs < lhs) {
79 template <
typename Element, std::enable_if_t<std::is_
floating_po
int_v<Element>>* =
nullptr>
82 if (isnan(lhs) and isnan(rhs)) {
84 }
else if (isnan(rhs)) {
86 }
else if (isnan(lhs)) {
90 return detail::compare_elements(lhs, rhs);
103 if (lhs_is_null and rhs_is_null) {
105 }
else if (lhs_is_null) {
107 }
else if (rhs_is_null) {
121 template <
typename Element, std::enable_if_t<not std::is_
floating_po
int_v<Element>>* =
nullptr>
124 return detail::compare_elements(lhs, rhs);
135 template <
typename Element, std::enable_if_t<std::is_
floating_po
int_v<Element>>* =
nullptr>
138 if (isnan(lhs) and isnan(rhs)) {
return true; }
150 template <
typename Element, std::enable_if_t<not std::is_
floating_po
int_v<Element>>* =
nullptr>
161 template <
typename Nullate>
180 : lhs{lhs}, rhs{rhs}, nulls{
has_nulls}, nulls_are_equal{nulls_are_equal}
191 template <
typename Element,
192 std::enable_if_t<cudf::is_equality_comparable<Element, Element>()>* =
nullptr>
194 size_type rhs_element_index)
const noexcept
197 bool const lhs_is_null{lhs.is_null(lhs_element_index)};
198 bool const rhs_is_null{rhs.is_null(rhs_element_index)};
199 if (lhs_is_null and rhs_is_null) {
201 }
else if (lhs_is_null != rhs_is_null) {
207 rhs.element<Element>(rhs_element_index));
211 template <
typename Element,
212 std::enable_if_t<not cudf::is_equality_comparable<Element, Element>()>* =
nullptr>
215 CUDF_UNREACHABLE(
"Attempted to compare elements of uncomparable types.");
220 column_device_view lhs;
221 column_device_view rhs;
231 template <
typename Nullate>
246 : lhs{lhs}, rhs{rhs}, nulls{
has_nulls}, nulls_are_equal{nulls_are_equal}
267 return thrust::equal(thrust::seq, lhs.begin(), lhs.end(), rhs.begin(), equal_elements);
282 template <
typename Nullate>
300 : lhs{lhs}, rhs{rhs}, nulls{
has_nulls}, null_precedence{null_precedence}
327 template <
typename Element,
328 std::enable_if_t<cudf::is_relationally_comparable<Element, Element>()>* =
nullptr>
330 size_type rhs_element_index)
const noexcept
333 bool const lhs_is_null{lhs.is_null(lhs_element_index)};
334 bool const rhs_is_null{rhs.is_null(rhs_element_index)};
336 if (lhs_is_null or rhs_is_null) {
337 return null_compare(lhs_is_null, rhs_is_null, null_precedence);
342 rhs.element<Element>(rhs_element_index));
346 template <
typename Element,
347 std::enable_if_t<not cudf::is_relationally_comparable<Element, Element>()>* =
nullptr>
350 CUDF_UNREACHABLE(
"Attempted to compare elements of uncomparable types.");
355 column_device_view lhs;
356 column_device_view rhs;
376 template <
typename Nullate>
401 order const* column_order =
nullptr,
406 _column_order{column_order},
407 _null_precedence{null_precedence}
424 bool ascending = (_column_order ==
nullptr) or (_column_order[i] ==
order::ASCENDING);
447 order const* _column_order{};
456 template <
template <
typename>
class hash_function,
typename Nullate>
467 template <typename T, CUDF_ENABLE_IF(column_device_view::has_element_accessor<T>())>
471 return cuda::std::numeric_limits<hash_value_type>::max();
473 return hash_function<T>{}(col.
element<T>(row_index));
484 template <typename T, CUDF_ENABLE_IF(not column_device_view::has_element_accessor<T>())>
487 CUDF_UNREACHABLE(
"Unsupported type in hash.");
499 template <
template <
typename>
class hash_function,
typename Nullate>
521 : _seed{seed}, _null_hash{null_hash}, _has_nulls{
has_nulls}
533 template <typename T, CUDF_ENABLE_IF(column_device_view::has_element_accessor<T>())>
536 if (_has_nulls && col.
is_null(row_index)) {
return _null_hash; }
537 return hash_function<T>{_seed}(col.
element<T>(row_index));
548 template <typename T, CUDF_ENABLE_IF(not column_device_view::has_element_accessor<T>())>
551 CUDF_UNREACHABLE(
"Unsupported type in hash.");
555 uint32_t _seed{DEFAULT_HASH_SEED};
556 hash_value_type _null_hash{cuda::std::numeric_limits<hash_value_type>::max()};
566 template <
template <
typename>
class hash_function,
typename Nullate>
589 : _table{t}, _seed(seed), _has_nulls{
has_nulls}
602 auto const initial_hash = cudf::hashing::detail::hash_combine(
604 type_dispatcher<dispatch_storage_type>(
611 auto hasher = [=](
size_type column_index) {
612 return cudf::type_dispatcher<dispatch_storage_type>(
615 _table.
column(column_index),
620 return thrust::transform_reduce(
623 thrust::make_counting_iterator(1),
624 thrust::make_counting_iterator(_table.
num_columns()),
628 return cudf::hashing::detail::hash_combine(lhs, rhs);
635 uint32_t _seed{DEFAULT_HASH_SEED};
An immutable, non-owning view of device data as a column of elements that is trivially copyable and u...
T element(size_type element_index) const noexcept
Returns reference to element at the specified index.
CUDF_HOST_DEVICE data_type type() const noexcept
Returns the element type.
bool is_null(size_type element_index) const noexcept
Returns whether the specified element is null.
ColumnDeviceView const & column(size_type column_index) const noexcept
Returns a reference to the view of the specified column.
size_type num_columns() const noexcept
Returns the number of columns.
Performs an equality comparison between two elements in two columns.
element_equality_comparator(Nullate has_nulls, column_device_view lhs, column_device_view rhs, null_equality nulls_are_equal=null_equality::EQUAL)
Construct type-dispatched function object for comparing equality between two elements.
bool operator()(size_type lhs_element_index, size_type rhs_element_index) const noexcept
Compares the specified elements for equality.
Function object for computing the hash value of a row in a column.
element_hasher_with_seed(Nullate has_nulls, uint32_t seed)
Constructs a function object for hashing an element in the given column.
element_hasher_with_seed(Nullate has_nulls, uint32_t seed, hash_value_type null_hash)
Constructs a function object for hashing an element in the given column.
Computes the hash value of an element in the given column.
Nullate has_nulls
A cudf::nullate type describing how to check for nulls.
Performs a relational comparison between two elements in two columns.
weak_ordering operator()(size_type lhs_element_index, size_type rhs_element_index) const noexcept
Performs a relational comparison between the specified elements.
element_relational_comparator(Nullate has_nulls, column_device_view lhs, column_device_view rhs)
Construct type-dispatched function object for performing a relational comparison between two elements...
element_relational_comparator(Nullate has_nulls, column_device_view lhs, column_device_view rhs, null_order null_precedence)
Construct type-dispatched function object for performing a relational comparison between two elements...
Performs a relational comparison between two elements in two tables.
row_equality_comparator(Nullate has_nulls, table_device_view lhs, table_device_view rhs, null_equality nulls_are_equal=null_equality::EQUAL)
Construct a new row equality comparator object.
bool operator()(size_type lhs_row_index, size_type rhs_row_index) const noexcept
Compares the specified rows for equality.
Computes the hash value of a row in the given table.
CUDF_HOST_DEVICE row_hasher(Nullate has_nulls, table_device_view t, uint32_t seed)
Constructs a row_hasher object with a seed value.
CUDF_HOST_DEVICE row_hasher(Nullate has_nulls, table_device_view t)
Constructs a row_hasher object.
auto operator()(size_type row_index) const
Computes the hash value of the row at row_index in the table
Computes whether one row is lexicographically less than another row.
bool operator()(size_type lhs_index, size_type rhs_index) const noexcept
Checks whether the row at lhs_index in the lhs table compares lexicographically less than the row at ...
row_lexicographic_comparator(Nullate has_nulls, table_device_view lhs, table_device_view rhs, order const *column_order=nullptr, null_order const *null_precedence=nullptr)
Construct a function object for performing a lexicographic comparison between the rows of two tables.
Table device view that is usable in device memory.
Column device view class definitions.
uint32_t hash_value_type
Type of hash value.
CUDF_HOST_DEVICE constexpr decltype(auto) __forceinline__ type_dispatcher(cudf::data_type dtype, Functor f, Ts &&... args)
Invokes an operator() template with the type instantiation based on the specified cudf::data_type's i...
#define CUDF_EXPECTS(...)
Macro for checking (pre-)conditions that throws an exception when a condition is violated.
null_order
Indicates how null values compare against all other values.
null_equality
Enum to consider two nulls as equal or unequal.
int32_t size_type
Row index type for columns and tables.
order
Indicates the order in which elements should be sorted.
@ BEFORE
NULL values ordered before all other values.
@ AFTER
NULL values ordered after all other values.
@ EQUAL
nulls compare equal
@ ASCENDING
Elements ordered from small to large.
bool has_nulls(table_view const &view)
Returns True if the table has nulls in any of its columns.
weak_ordering
Result type of the element_relational_comparator function object.
@ LESS
Indicates a is less than (ordered before) b
@ EQUIVALENT
Indicates a is ordered neither before nor after b
@ GREATER
Indicates a is greater than (ordered after) b
auto null_compare(bool lhs_is_null, bool rhs_is_null, null_order null_precedence)
Compare the nulls according to null order.
weak_ordering relational_compare(Element lhs, Element rhs)
A specialization for floating-point Element type relational comparison to derive the order of the ele...
bool equality_compare(Element lhs, Element rhs)
A specialization for floating-point Element type to check if lhs is equivalent to rhs....
Table device view class definitions.
Defines the mapping between cudf::type_id runtime type information and concrete C++ types.
#define CUDF_HOST_DEVICE
Indicates that the function or method is usable on host and device.