OmniSciDB  a987f07e93
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
DoubleSort.h
Go to the documentation of this file.
1 /*
2  * Copyright 2022 HEAVY.AI, Inc.
3  *
4  * Licensed under the Apache License, Version 2.0 (the "License");
5  * you may not use this file except in compliance with the License.
6  * You may obtain a copy of the License at
7  *
8  * http://www.apache.org/licenses/LICENSE-2.0
9  *
10  * Unless required by applicable law or agreed to in writing, software
11  * distributed under the License is distributed on an "AS IS" BASIS,
12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13  * See the License for the specific language governing permissions and
14  * limitations under the License.
15  */
16 
17 // Used for creating iterators that can be used to sort two vectors.
18 // In other words, double_sort::Iterator<> is a writable zip iterator.
19 
20 #pragma once
21 
22 #include "funcannotations.h"
23 
24 #include <algorithm>
25 #include <iterator>
26 #include <numeric>
27 #include <vector>
28 
29 #ifndef __CUDACC__
30 #include <ostream>
31 #endif
32 
33 // Overriding swap() isn't sufficient, since std:sort() uses insertion sort
34 // when the number of elements is 16 or less which bypasses swap.
35 
36 // Iterator sent to sort() sorts two containers simultaneously.
37 namespace double_sort {
38 
39 template <typename T>
40 union Variant {
41  T* ptr_;
43 };
44 
45 // Named Value insofar as it is the return value of Iterator::operator*().
46 // Default and copy/move constructors initial to a value (ref_=false).
47 template <typename T0, typename T1>
48 struct Value {
51  bool const ref_; // Use ptr_ if true, else value_.
52  DEVICE Value(T0* ptr0, T1* ptr1) : v0_{ptr0}, v1_{ptr1}, ref_(true) {}
53  // thrust::sort() copies Values, std::sort() moves Values.
54 #ifdef __CUDACC__
55  DEVICE Value() : ref_(false) {}
56  DEVICE Value(Value const& b) : ref_(false) {
57  v0_.value_ = b.ref_ ? *b.v0_.ptr_ : b.v0_.value_;
58  v1_.value_ = b.ref_ ? *b.v1_.ptr_ : b.v1_.value_;
59  }
60  DEVICE Value& operator=(Value const& b) {
61  // Both branches are used by thrust::sort().
62  if (ref_) {
63  *v0_.ptr_ = b.ref_ ? *b.v0_.ptr_ : b.v0_.value_;
64  *v1_.ptr_ = b.ref_ ? *b.v1_.ptr_ : b.v1_.value_;
65  } else {
66  v0_.value_ = b.ref_ ? *b.v0_.ptr_ : b.v0_.value_;
67  v1_.value_ = b.ref_ ? *b.v1_.ptr_ : b.v1_.value_;
68  }
69  return *this;
70  }
71 #else
72  Value(Value&& b) : ref_(false) {
73  v0_.value_ = b.ref_ ? std::move(*b.v0_.ptr_) : std::move(b.v0_.value_);
74  v1_.value_ = b.ref_ ? std::move(*b.v1_.ptr_) : std::move(b.v1_.value_);
75  }
77  if (ref_) {
78  *v0_.ptr_ = b.ref_ ? std::move(*b.v0_.ptr_) : std::move(b.v0_.value_);
79  *v1_.ptr_ = b.ref_ ? std::move(*b.v1_.ptr_) : std::move(b.v1_.value_);
80  } else {
81  v0_.value_ = b.ref_ ? std::move(*b.v0_.ptr_) : std::move(b.v0_.value_);
82  v1_.value_ = b.ref_ ? std::move(*b.v1_.ptr_) : std::move(b.v1_.value_);
83  }
84  return *this;
85  }
86 #endif
87  DEVICE T0 value0() const { return ref_ ? *v0_.ptr_ : v0_.value_; }
88  DEVICE T1 value1() const { return ref_ ? *v1_.ptr_ : v1_.value_; }
89 };
90 
91 #ifndef __CUDACC__
92 template <typename T0, typename T1>
93 std::ostream& operator<<(std::ostream& out, Value<T0, T1> const& ds) {
94  return out << "ref_(" << ds.ref_ << ") v0_.value_(" << ds.v0_.value_ << ") v1_.value_("
95  << ds.v1_.value_ << ')' << std::endl;
96 }
97 #endif
98 
99 template <typename T0, typename T1>
100 struct Iterator {
101  using iterator_category = std::input_iterator_tag;
103  using difference_type = std::ptrdiff_t;
104  using pointer = value_type*;
106  Value<T0, T1> this_; // this_ is always a reference object. I.e. this_.ref_ == true.
107  DEVICE Iterator(T0* ptr0, T1* ptr1) : this_(ptr0, ptr1) {}
108  DEVICE Iterator(Iterator const& b) : this_(b.this_.v0_.ptr_, b.this_.v1_.ptr_) {}
109  DEVICE Iterator(Iterator&& b) : this_(b.this_.v0_.ptr_, b.this_.v1_.ptr_) {}
111  this_.v0_.ptr_ = b.this_.v0_.ptr_;
112  this_.v1_.ptr_ = b.this_.v1_.ptr_;
113  return *this;
114  }
116  this_.v0_.ptr_ = b.this_.v0_.ptr_;
117  this_.v1_.ptr_ = b.this_.v1_.ptr_;
118  return *this;
119  }
120  // Returns a reference object by reference
122  return const_cast<Iterator<T0, T1>*>(this)->this_;
123  }
124  // Required by thrust::sort().
125  // Returns a reference object by value
126  DEVICE Value<T0, T1> operator[](int i) const { return operator+(i).this_; }
128  ++this_.v0_.ptr_;
129  ++this_.v1_.ptr_;
130  return *this;
131  }
132  // Required by thrust::sort().
134  this_.v0_.ptr_ += i;
135  this_.v1_.ptr_ += i;
136  return *this;
137  }
139  --this_.v0_.ptr_;
140  --this_.v1_.ptr_;
141  return *this;
142  }
143  DEVICE
144  auto operator-(Iterator const& b) const { return this_.v0_.ptr_ - b.this_.v0_.ptr_; }
145  DEVICE
146  Iterator operator+(int i) const { return {this_.v0_.ptr_ + i, this_.v1_.ptr_ + i}; }
147  DEVICE
148  Iterator operator-(int i) const { return {this_.v0_.ptr_ - i, this_.v1_.ptr_ - i}; }
149  DEVICE
150  bool operator==(Iterator const& b) const { return this_.v0_.ptr_ == b.this_.v0_.ptr_; }
151  DEVICE
152  bool operator!=(Iterator const& b) const { return this_.v0_.ptr_ != b.this_.v0_.ptr_; }
153  DEVICE
154  bool operator<(Iterator const& b) const { return this_.v0_.ptr_ < b.this_.v0_.ptr_; }
155  // Required by MacOS /usr/local/opt/llvm/include/c++/v1/algorithm:4036
156  DEVICE
157  bool operator>(Iterator const& b) const { return this_.v0_.ptr_ > b.this_.v0_.ptr_; }
158  // Required by MacOS /usr/local/opt/llvm/include/c++/v1/algorithm:4000
159  DEVICE
160  bool operator>=(Iterator const& b) const { return this_.v0_.ptr_ >= b.this_.v0_.ptr_; }
161 };
162 
163 } // namespace double_sort
DEVICE bool operator==(Iterator const &b) const
Definition: DoubleSort.h:150
DEVICE Value< T0, T1 > & operator*() const
Definition: DoubleSort.h:121
DEVICE bool operator>=(Iterator const &b) const
Definition: DoubleSort.h:160
DEVICE auto operator-(Iterator const &b) const
Definition: DoubleSort.h:144
DEVICE Iterator(Iterator const &b)
Definition: DoubleSort.h:108
DEVICE Iterator & operator+=(int i)
Definition: DoubleSort.h:133
DEVICE bool operator!=(Iterator const &b) const
Definition: DoubleSort.h:152
DEVICE Iterator(Iterator &&b)
Definition: DoubleSort.h:109
DEVICE Iterator & operator--()
Definition: DoubleSort.h:138
Value & operator=(Value &&b)
Definition: DoubleSort.h:76
DEVICE Value< T0, T1 > operator[](int i) const
Definition: DoubleSort.h:126
#define DEVICE
DEVICE Iterator & operator=(Iterator &&b)
Definition: DoubleSort.h:115
Value< T0, T1 > this_
Definition: DoubleSort.h:106
std::ptrdiff_t difference_type
Definition: DoubleSort.h:103
bool const ref_
Definition: DoubleSort.h:51
DEVICE Iterator(T0 *ptr0, T1 *ptr1)
Definition: DoubleSort.h:107
DEVICE bool operator<(Iterator const &b) const
Definition: DoubleSort.h:154
DEVICE T0 value0() const
Definition: DoubleSort.h:87
Value(Value &&b)
Definition: DoubleSort.h:72
DEVICE Iterator operator+(int i) const
Definition: DoubleSort.h:146
bool g_enable_watchdog false
Definition: Execute.cpp:79
DEVICE bool operator>(Iterator const &b) const
Definition: DoubleSort.h:157
Variant< T0 > v0_
Definition: DoubleSort.h:49
DEVICE Value(T0 *ptr0, T1 *ptr1)
Definition: DoubleSort.h:52
DEVICE Iterator operator-(int i) const
Definition: DoubleSort.h:148
DEVICE T1 value1() const
Definition: DoubleSort.h:88
std::input_iterator_tag iterator_category
Definition: DoubleSort.h:101
DEVICE Iterator & operator=(Iterator const &b)
Definition: DoubleSort.h:110
Variant< T1 > v1_
Definition: DoubleSort.h:50
DEVICE Iterator & operator++()
Definition: DoubleSort.h:127