MySQL  8.0.25
Source Code Documentation
varlen_sort.h
Go to the documentation of this file.
1 #ifndef VARLEN_SORT_INCLUDED
2 #define VARLEN_SORT_INCLUDED
3 
4 /* Copyright (c) 2017, 2021, Oracle and/or its affiliates.
5 
6  This program is free software; you can redistribute it and/or modify
7  it under the terms of the GNU General Public License, version 2.0,
8  as published by the Free Software Foundation.
9 
10  This program is also distributed with certain software (including
11  but not limited to OpenSSL) that is licensed under separate terms,
12  as designated in a particular file or component or in included license
13  documentation. The authors of MySQL hereby grant you an additional
14  permission to link the program and your derivative works with the
15  separately licensed software that they have included with MySQL.
16 
17  This program is distributed in the hope that it will be useful,
18  but WITHOUT ANY WARRANTY; without even the implied warranty of
19  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
20  GNU General Public License, version 2.0, for more details.
21 
22  You should have received a copy of the GNU General Public License
23  along with this program; if not, write to the Free Software
24  Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA */
25 
26 /**
27  A RandomAccessIterator that splits up a char/uchar array into fixed-length
28  elements, so that they can be sorted using std::sort. There is also a helper
29  function varlen_sort() that is an adapter around std::sort for this purpose.
30 */
31 
32 #include <assert.h>
33 
34 #include "template_utils.h"
35 
36 #include <algorithm>
37 #include <memory>
38 #include <utility>
39 
40 /*
41  Conceptually similar to a struct { uchar[N] },
42  except that most of the time, it just holds a reference to an underlying
43  array, instead of keeping the memory itself.
44 */
46  varlen_element(unsigned char *ptr_arg, size_t elem_size_arg)
47  : ptr(ptr_arg), elem_size(elem_size_arg) {}
48 
49  varlen_element(varlen_element &other) = delete;
50 
51  /*
52  In this case, we need to own the memory ourselves. It is really only used
53  when std::sort wants to do an insertion sort and needs a temporary element.
54  */
56  if (other.mem != nullptr) {
57  mem = std::move(other.mem);
58  } else {
59  mem.reset(new unsigned char[other.elem_size]);
60  memcpy(mem.get(), other.ptr, elem_size);
61  }
62  ptr = mem.get();
63  }
64 
65  varlen_element &operator=(const varlen_element &other) = delete;
67  assert(elem_size == other.elem_size);
68  memcpy(ptr, other.ptr, elem_size);
69  return *this;
70  }
71 
72  std::unique_ptr<unsigned char[]> mem;
73  unsigned char *ptr = nullptr;
74  size_t elem_size = 0;
75 };
76 
77 // ValueSwappable.
78 static inline void swap(const varlen_element &a, const varlen_element &b) {
79  assert(a.elem_size == b.elem_size);
80  std::swap_ranges(a.ptr, a.ptr + a.elem_size, b.ptr);
81 }
82 
83 // Conceptually similar to a _pointer_ to an uchar[N].
85  public:
86  varlen_iterator(unsigned char *ptr_arg, size_t elem_size_arg)
87  : ptr(ptr_arg), elem_size(elem_size_arg) {}
88 
89  // Iterator (required for InputIterator).
92  ptr += elem_size;
93  return *this;
94  }
95 
96  // EqualityComparable (required for InputIterator).
97  bool operator==(const varlen_iterator &other) const {
98  return ptr == other.ptr && elem_size == other.elem_size;
99  }
100 
101  // InputIterator (required for ForwardIterator).
102  bool operator!=(const varlen_iterator &other) const {
103  return !(*this == other);
104  }
105 
107 
108  // DefaultConstructible (required for ForwardIterator).
110 
111  // ForwardIterator (required for RandomAccessIterator).
113  varlen_iterator copy = *this;
114  ptr += elem_size;
115  return copy;
116  }
117 
118  // BidirectionalIterator (required for RandomAccessIterator).
120  ptr -= elem_size;
121  return *this;
122  }
124  varlen_iterator copy = *this;
125  ptr -= elem_size;
126  return copy;
127  }
128 
129  // RandomAccessIterator.
131  ptr += elem_size * n;
132  return *this;
133  }
134 
136  ptr -= elem_size * n;
137  return *this;
138  }
139 
140  varlen_iterator operator+(size_t n) const {
141  return varlen_iterator{ptr + elem_size * n, elem_size};
142  }
143 
144  varlen_iterator operator-(size_t n) const {
145  return varlen_iterator{ptr - elem_size * n, elem_size};
146  }
147 
148  ptrdiff_t operator-(const varlen_iterator &other) const {
149  assert(elem_size == other.elem_size);
150  assert((ptr - other.ptr) % elem_size == 0);
151  return (ptr - other.ptr) / elem_size;
152  }
153 
154  varlen_element operator[](size_t i) const {
155  return varlen_element{ptr + i * elem_size, elem_size};
156  }
157 
158  bool operator<(varlen_iterator &other) const {
159  assert(elem_size == other.elem_size);
160  return ptr < other.ptr;
161  }
162 
163  bool operator>(varlen_iterator &other) const {
164  assert(elem_size == other.elem_size);
165  return ptr > other.ptr;
166  }
167 
168  bool operator>=(varlen_iterator &other) const {
169  assert(elem_size == other.elem_size);
170  return ptr >= other.ptr;
171  }
172 
173  bool operator<=(varlen_iterator &other) const {
174  assert(elem_size == other.elem_size);
175  return ptr <= other.ptr;
176  }
177 
178  private:
179  unsigned char *ptr = nullptr;
180  size_t elem_size = 0;
181 };
182 
183 namespace std {
184 
185 // Required for Iterator.
186 template <>
187 struct iterator_traits<varlen_iterator> : iterator_traits<varlen_element *> {};
188 
189 } // namespace std
190 
191 /*
192  Compare should be a functor that takes in two T*.
193  T does not need to be char or uchar.
194 */
195 template <class T, class Compare>
196 inline void varlen_sort(T *first, T *last, size_t elem_size, Compare comp) {
197  std::sort(varlen_iterator(pointer_cast<unsigned char *>(first), elem_size),
198  varlen_iterator(pointer_cast<unsigned char *>(last), elem_size),
199  [comp](const varlen_element &a, const varlen_element &b) {
200  return comp(pointer_cast<T *>(a.ptr), pointer_cast<T *>(b.ptr));
201  });
202 }
203 
204 #endif // !defined(VARLEN_SORT_INCLUDED)
Definition: varlen_sort.h:84
bool operator!=(const varlen_iterator &other) const
Definition: varlen_sort.h:102
varlen_iterator()
Definition: varlen_sort.h:109
varlen_iterator & operator++()
Definition: varlen_sort.h:91
varlen_iterator(unsigned char *ptr_arg, size_t elem_size_arg)
Definition: varlen_sort.h:86
bool operator==(const varlen_iterator &other) const
Definition: varlen_sort.h:97
bool operator>(varlen_iterator &other) const
Definition: varlen_sort.h:163
unsigned char * ptr
Definition: varlen_sort.h:179
ptrdiff_t operator-(const varlen_iterator &other) const
Definition: varlen_sort.h:148
varlen_iterator operator++(int)
Definition: varlen_sort.h:112
bool operator<=(varlen_iterator &other) const
Definition: varlen_sort.h:173
varlen_iterator & operator--()
Definition: varlen_sort.h:119
varlen_iterator & operator-=(size_t n)
Definition: varlen_sort.h:135
varlen_iterator operator-(size_t n) const
Definition: varlen_sort.h:144
varlen_iterator operator+(size_t n) const
Definition: varlen_sort.h:140
varlen_element operator*() const
Definition: varlen_sort.h:90
varlen_iterator & operator+=(size_t n)
Definition: varlen_sort.h:130
varlen_element operator[](size_t i) const
Definition: varlen_sort.h:154
varlen_iterator operator--(int)
Definition: varlen_sort.h:123
size_t elem_size
Definition: varlen_sort.h:180
bool operator<(varlen_iterator &other) const
Definition: varlen_sort.h:158
varlen_element operator->() const
Definition: varlen_sort.h:106
bool operator>=(varlen_iterator &other) const
Definition: varlen_sort.h:168
void copy(Shards< COUNT > &dst, const Shards< COUNT > &src) noexcept
Copy the counters, overwrite destination.
Definition: ut0counter.h:353
Definition: varlen_sort.h:183
A RandomAccessIterator that splits up a char/uchar array into fixed-length elements,...
Definition: varlen_sort.h:45
std::unique_ptr< unsigned char[]> mem
Definition: varlen_sort.h:72
varlen_element(varlen_element &&other)
Definition: varlen_sort.h:55
varlen_element & operator=(const varlen_element &other)=delete
varlen_element & operator=(varlen_element &&other)
Definition: varlen_sort.h:66
varlen_element(varlen_element &other)=delete
size_t elem_size
Definition: varlen_sort.h:74
varlen_element(unsigned char *ptr_arg, size_t elem_size_arg)
Definition: varlen_sort.h:46
unsigned char * ptr
Definition: varlen_sort.h:73
static void swap(const varlen_element &a, const varlen_element &b)
Definition: varlen_sort.h:78
void varlen_sort(T *first, T *last, size_t elem_size, Compare comp)
Definition: varlen_sort.h:196
int n
Definition: xcom_base.cc:445