OmniSciDB  fe05a0c208
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
DoubleSort.h
Go to the documentation of this file.
1 /*
2  * Copyright (c) 2020 OmniSci, 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 : public std::iterator<std::input_iterator_tag, Value<T0, T1>> {
101  Value<T0, T1> this_; // this_ is always a reference object. I.e. this_.ref_ == true.
102  DEVICE Iterator(T0* ptr0, T1* ptr1) : this_(ptr0, ptr1) {}
103  DEVICE Iterator(Iterator const& b) : this_(b.this_.v0_.ptr_, b.this_.v1_.ptr_) {}
104  DEVICE Iterator(Iterator&& b) : this_(b.this_.v0_.ptr_, b.this_.v1_.ptr_) {}
106  this_.v0_.ptr_ = b.this_.v0_.ptr_;
107  this_.v1_.ptr_ = b.this_.v1_.ptr_;
108  return *this;
109  }
111  this_.v0_.ptr_ = b.this_.v0_.ptr_;
112  this_.v1_.ptr_ = b.this_.v1_.ptr_;
113  return *this;
114  }
115  // Returns a reference object by reference
117  return const_cast<Iterator<T0, T1>*>(this)->this_;
118  }
119  // Required by thrust::sort().
120  // Returns a reference object by value
121  DEVICE Value<T0, T1> operator[](int i) const { return operator+(i).this_; }
123  ++this_.v0_.ptr_;
124  ++this_.v1_.ptr_;
125  return *this;
126  }
127  // Required by thrust::sort().
129  this_.v0_.ptr_ += i;
130  this_.v1_.ptr_ += i;
131  return *this;
132  }
134  --this_.v0_.ptr_;
135  --this_.v1_.ptr_;
136  return *this;
137  }
138  DEVICE
139  auto operator-(Iterator const& b) const { return this_.v0_.ptr_ - b.this_.v0_.ptr_; }
140  DEVICE
141  Iterator operator+(int i) const { return {this_.v0_.ptr_ + i, this_.v1_.ptr_ + i}; }
142  DEVICE
143  Iterator operator-(int i) const { return {this_.v0_.ptr_ - i, this_.v1_.ptr_ - i}; }
144  DEVICE
145  bool operator==(Iterator const& b) const { return this_.v0_.ptr_ == b.this_.v0_.ptr_; }
146  DEVICE
147  bool operator!=(Iterator const& b) const { return this_.v0_.ptr_ != b.this_.v0_.ptr_; }
148  DEVICE
149  bool operator<(Iterator const& b) const { return this_.v0_.ptr_ < b.this_.v0_.ptr_; }
150  // Required by MacOS /usr/local/opt/llvm/include/c++/v1/algorithm:4036
151  DEVICE
152  bool operator>(Iterator const& b) const { return this_.v0_.ptr_ > b.this_.v0_.ptr_; }
153  // Required by MacOS /usr/local/opt/llvm/include/c++/v1/algorithm:4000
154  DEVICE
155  bool operator>=(Iterator const& b) const { return this_.v0_.ptr_ >= b.this_.v0_.ptr_; }
156 };
157 
158 } // namespace double_sort
DEVICE bool operator==(Iterator const &b) const
Definition: DoubleSort.h:145
DEVICE Value< T0, T1 > & operator*() const
Definition: DoubleSort.h:116
DEVICE bool operator>=(Iterator const &b) const
Definition: DoubleSort.h:155
DEVICE auto operator-(Iterator const &b) const
Definition: DoubleSort.h:139
DEVICE Iterator(Iterator const &b)
Definition: DoubleSort.h:103
DEVICE Iterator & operator+=(int i)
Definition: DoubleSort.h:128
DEVICE bool operator!=(Iterator const &b) const
Definition: DoubleSort.h:147
DEVICE Iterator(Iterator &&b)
Definition: DoubleSort.h:104
DEVICE Iterator & operator--()
Definition: DoubleSort.h:133
Value & operator=(Value &&b)
Definition: DoubleSort.h:76
DEVICE Value< T0, T1 > operator[](int i) const
Definition: DoubleSort.h:121
#define DEVICE
DEVICE Iterator & operator=(Iterator &&b)
Definition: DoubleSort.h:110
Value< T0, T1 > this_
Definition: DoubleSort.h:101
bool const ref_
Definition: DoubleSort.h:51
DEVICE Iterator(T0 *ptr0, T1 *ptr1)
Definition: DoubleSort.h:102
DEVICE bool operator<(Iterator const &b) const
Definition: DoubleSort.h:149
DEVICE T0 value0() const
Definition: DoubleSort.h:87
Value(Value &&b)
Definition: DoubleSort.h:72
DEVICE Iterator operator+(int i) const
Definition: DoubleSort.h:141
bool g_enable_watchdog false
Definition: Execute.cpp:76
DEVICE bool operator>(Iterator const &b) const
Definition: DoubleSort.h:152
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:143
DEVICE T1 value1() const
Definition: DoubleSort.h:88
DEVICE Iterator & operator=(Iterator const &b)
Definition: DoubleSort.h:105
Variant< T1 > v1_
Definition: DoubleSort.h:50
DEVICE Iterator & operator++()
Definition: DoubleSort.h:122