OmniSciDB  a5dc49c757
 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 {
88  return ref_ ? *v0_.ptr_ : v0_.value_;
89  }
90  DEVICE T1 value1() const {
91  return ref_ ? *v1_.ptr_ : v1_.value_;
92  }
93 };
94 
95 #ifndef __CUDACC__
96 template <typename T0, typename T1>
97 std::ostream& operator<<(std::ostream& out, Value<T0, T1> const& ds) {
98  return out << "ref_(" << ds.ref_ << ") v0_.value_(" << ds.v0_.value_ << ") v1_.value_("
99  << ds.v1_.value_ << ')' << std::endl;
100 }
101 #endif
102 
103 template <typename T0, typename T1>
104 struct Iterator {
105  using iterator_category = std::input_iterator_tag;
107  using difference_type = std::ptrdiff_t;
108  using pointer = value_type*;
110  Value<T0, T1> this_; // this_ is always a reference object. I.e. this_.ref_ == true.
111  DEVICE Iterator(T0* ptr0, T1* ptr1) : this_(ptr0, ptr1) {}
112  DEVICE Iterator(Iterator const& b) : this_(b.this_.v0_.ptr_, b.this_.v1_.ptr_) {}
113  DEVICE Iterator(Iterator&& b) : this_(b.this_.v0_.ptr_, b.this_.v1_.ptr_) {}
115  this_.v0_.ptr_ = b.this_.v0_.ptr_;
116  this_.v1_.ptr_ = b.this_.v1_.ptr_;
117  return *this;
118  }
120  this_.v0_.ptr_ = b.this_.v0_.ptr_;
121  this_.v1_.ptr_ = b.this_.v1_.ptr_;
122  return *this;
123  }
124  // Returns a reference object by reference
126  return const_cast<Iterator<T0, T1>*>(this)->this_;
127  }
128  // Required by thrust::sort().
129  // Returns a reference object by value
130  DEVICE Value<T0, T1> operator[](int i) const { return operator+(i).this_; }
132  ++this_.v0_.ptr_;
133  ++this_.v1_.ptr_;
134  return *this;
135  }
136  // Required by thrust::sort().
138  this_.v0_.ptr_ += i;
139  this_.v1_.ptr_ += i;
140  return *this;
141  }
143  --this_.v0_.ptr_;
144  --this_.v1_.ptr_;
145  return *this;
146  }
147  DEVICE
148  auto operator-(Iterator const& b) const { return this_.v0_.ptr_ - b.this_.v0_.ptr_; }
149  DEVICE
150  Iterator operator+(int i) const { return {this_.v0_.ptr_ + i, this_.v1_.ptr_ + i}; }
151  DEVICE
152  Iterator operator-(int i) const { return {this_.v0_.ptr_ - i, this_.v1_.ptr_ - i}; }
153  DEVICE
154  bool operator==(Iterator const& b) const { return this_.v0_.ptr_ == b.this_.v0_.ptr_; }
155  DEVICE
156  bool operator!=(Iterator const& b) const { return this_.v0_.ptr_ != b.this_.v0_.ptr_; }
157  DEVICE
158  bool operator<(Iterator const& b) const { return this_.v0_.ptr_ < b.this_.v0_.ptr_; }
159  // Required by MacOS /usr/local/opt/llvm/include/c++/v1/algorithm:4036
160  DEVICE
161  bool operator>(Iterator const& b) const { return this_.v0_.ptr_ > b.this_.v0_.ptr_; }
162  // Required by MacOS /usr/local/opt/llvm/include/c++/v1/algorithm:4000
163  DEVICE
164  bool operator>=(Iterator const& b) const { return this_.v0_.ptr_ >= b.this_.v0_.ptr_; }
165 };
166 
167 } // namespace double_sort
DEVICE bool operator==(Iterator const &b) const
Definition: DoubleSort.h:154
DEVICE Value< T0, T1 > & operator*() const
Definition: DoubleSort.h:125
DEVICE bool operator>=(Iterator const &b) const
Definition: DoubleSort.h:164
DEVICE auto operator-(Iterator const &b) const
Definition: DoubleSort.h:148
DEVICE Iterator(Iterator const &b)
Definition: DoubleSort.h:112
DEVICE Iterator & operator+=(int i)
Definition: DoubleSort.h:137
DEVICE bool operator!=(Iterator const &b) const
Definition: DoubleSort.h:156
DEVICE Iterator(Iterator &&b)
Definition: DoubleSort.h:113
DEVICE Iterator & operator--()
Definition: DoubleSort.h:142
Value & operator=(Value &&b)
Definition: DoubleSort.h:76
DEVICE Value< T0, T1 > operator[](int i) const
Definition: DoubleSort.h:130
#define DEVICE
DEVICE Iterator & operator=(Iterator &&b)
Definition: DoubleSort.h:119
Value< T0, T1 > this_
Definition: DoubleSort.h:110
std::ptrdiff_t difference_type
Definition: DoubleSort.h:107
bool const ref_
Definition: DoubleSort.h:51
DEVICE Iterator(T0 *ptr0, T1 *ptr1)
Definition: DoubleSort.h:111
DEVICE bool operator<(Iterator const &b) const
Definition: DoubleSort.h:158
DEVICE T0 value0() const
Definition: DoubleSort.h:87
Value(Value &&b)
Definition: DoubleSort.h:72
DEVICE Iterator operator+(int i) const
Definition: DoubleSort.h:150
bool g_enable_watchdog false
Definition: Execute.cpp:80
DEVICE bool operator>(Iterator const &b) const
Definition: DoubleSort.h:161
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:152
DEVICE T1 value1() const
Definition: DoubleSort.h:90
std::input_iterator_tag iterator_category
Definition: DoubleSort.h:105
DEVICE Iterator & operator=(Iterator const &b)
Definition: DoubleSort.h:114
Variant< T1 > v1_
Definition: DoubleSort.h:50
DEVICE Iterator & operator++()
Definition: DoubleSort.h:131