MySQL  8.0.18
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, Oracle and/or its affiliates. All rights reserved.
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 "my_dbug.h"
33 #include "template_utils.h"
34 
35 #include <algorithm>
36 #include <memory>
37 #include <utility>
38 
39 /*
40  Conceptually similar to a struct { uchar[N] },
41  except that most of the time, it just holds a reference to an underlying
42  array, instead of keeping the memory itself.
43 */
45  varlen_element(unsigned char *ptr_arg, size_t elem_size_arg)
46  : ptr(ptr_arg), elem_size(elem_size_arg) {}
47 
48  varlen_element(varlen_element &other) = delete;
49 
50  /*
51  In this case, we need to own the memory ourselves. It is really only used
52  when std::sort wants to do an insertion sort and needs a temporary element.
53  */
55  if (other.mem != nullptr) {
56  mem = std::move(other.mem);
57  } else {
58  mem.reset(new unsigned char[other.elem_size]);
59  memcpy(mem.get(), other.ptr, elem_size);
60  }
61  ptr = mem.get();
62  }
63 
64  varlen_element &operator=(const varlen_element &other) = delete;
66  DBUG_ASSERT(elem_size == other.elem_size);
67  memcpy(ptr, other.ptr, elem_size);
68  return *this;
69  }
70 
71  std::unique_ptr<unsigned char[]> mem;
72  unsigned char *ptr = nullptr;
73  size_t elem_size = 0;
74 };
75 
76 // ValueSwappable.
77 static inline void swap(const varlen_element &a, const varlen_element &b) {
79  std::swap_ranges(a.ptr, a.ptr + a.elem_size, b.ptr);
80 }
81 
82 // Conceptually similar to a _pointer_ to an uchar[N].
84  public:
85  varlen_iterator(unsigned char *ptr_arg, size_t elem_size_arg)
86  : ptr(ptr_arg), elem_size(elem_size_arg) {}
87 
88  // Iterator (required for InputIterator).
91  ptr += elem_size;
92  return *this;
93  }
94 
95  // EqualityComparable (required for InputIterator).
96  bool operator==(const varlen_iterator &other) const {
97  return ptr == other.ptr && elem_size == other.elem_size;
98  }
99 
100  // InputIterator (required for ForwardIterator).
101  bool operator!=(const varlen_iterator &other) const {
102  return !(*this == other);
103  }
104 
106 
107  // DefaultConstructible (required for ForwardIterator).
109 
110  // ForwardIterator (required for RandomAccessIterator).
112  varlen_iterator copy = *this;
113  ptr += elem_size;
114  return copy;
115  }
116 
117  // BidirectionalIterator (required for RandomAccessIterator).
119  ptr -= elem_size;
120  return *this;
121  }
123  varlen_iterator copy = *this;
124  ptr -= elem_size;
125  return copy;
126  }
127 
128  // RandomAccessIterator.
130  ptr += elem_size * n;
131  return *this;
132  }
133 
135  ptr -= elem_size * n;
136  return *this;
137  }
138 
139  varlen_iterator operator+(size_t n) const {
140  return varlen_iterator{ptr + elem_size * n, elem_size};
141  }
142 
143  varlen_iterator operator-(size_t n) const {
144  return varlen_iterator{ptr - elem_size * n, elem_size};
145  }
146 
147  ptrdiff_t operator-(const varlen_iterator &other) const {
148  DBUG_ASSERT(elem_size == other.elem_size);
149  DBUG_ASSERT((ptr - other.ptr) % elem_size == 0);
150  return (ptr - other.ptr) / elem_size;
151  }
152 
153  varlen_element operator[](size_t i) const {
154  return varlen_element{ptr + i * elem_size, elem_size};
155  }
156 
157  bool operator<(varlen_iterator &other) const {
158  DBUG_ASSERT(elem_size == other.elem_size);
159  return ptr < other.ptr;
160  }
161 
162  bool operator>(varlen_iterator &other) const {
163  DBUG_ASSERT(elem_size == other.elem_size);
164  return ptr > other.ptr;
165  }
166 
167  bool operator>=(varlen_iterator &other) const {
168  DBUG_ASSERT(elem_size == other.elem_size);
169  return ptr >= other.ptr;
170  }
171 
172  bool operator<=(varlen_iterator &other) const {
173  DBUG_ASSERT(elem_size == other.elem_size);
174  return ptr <= other.ptr;
175  }
176 
177  private:
178  unsigned char *ptr = nullptr;
179  size_t elem_size = 0;
180 };
181 
182 namespace std {
183 
184 // Required for Iterator.
185 template <>
186 struct iterator_traits<varlen_iterator> : iterator_traits<varlen_element *> {};
187 
188 } // namespace std
189 
190 /*
191  Compare should be a functor that takes in two T*.
192  T does not need to be char or uchar.
193 */
194 template <class T, class Compare>
195 inline void varlen_sort(T *first, T *last, size_t elem_size, Compare comp) {
196  std::sort(varlen_iterator(pointer_cast<unsigned char *>(first), elem_size),
197  varlen_iterator(pointer_cast<unsigned char *>(last), elem_size),
198  [comp](const varlen_element &a, const varlen_element &b) {
199  return comp(pointer_cast<T *>(a.ptr), pointer_cast<T *>(b.ptr));
200  });
201 }
202 
203 #endif // !defined(VARLEN_SORT_INCLUDED)
static void swap(const varlen_element &a, const varlen_element &b)
Definition: varlen_sort.h:77
unsigned char * ptr
Definition: varlen_sort.h:72
varlen_iterator & operator-=(size_t n)
Definition: varlen_sort.h:134
Definition: varlen_sort.h:83
varlen_iterator & operator++()
Definition: varlen_sort.h:90
A RandomAccessIterator that splits up a char/uchar array into fixed-length elements, so that they can be sorted using std::sort.
Definition: varlen_sort.h:44
Definition: varlen_sort.h:182
size_t elem_size
Definition: varlen_sort.h:179
varlen_element(unsigned char *ptr_arg, size_t elem_size_arg)
Definition: varlen_sort.h:45
varlen_iterator operator+(size_t n) const
Definition: varlen_sort.h:139
varlen_element operator*() const
Definition: varlen_sort.h:89
varlen_iterator(unsigned char *ptr_arg, size_t elem_size_arg)
Definition: varlen_sort.h:85
#define DBUG_ASSERT(A)
Definition: my_dbug.h:197
bool operator<=(varlen_iterator &other) const
Definition: varlen_sort.h:172
void varlen_sort(T *first, T *last, size_t elem_size, Compare comp)
Definition: varlen_sort.h:195
varlen_element & operator=(const varlen_element &other)=delete
varlen_iterator & operator+=(size_t n)
Definition: varlen_sort.h:129
bool operator>(varlen_iterator &other) const
Definition: varlen_sort.h:162
std::unique_ptr< unsigned char[]> mem
Definition: varlen_sort.h:71
bool operator==(const varlen_iterator &other) const
Definition: varlen_sort.h:96
varlen_element operator[](size_t i) const
Definition: varlen_sort.h:153
bool operator<(varlen_iterator &other) const
Definition: varlen_sort.h:157
varlen_element operator->() const
Definition: varlen_sort.h:105
bool operator!=(const varlen_iterator &other) const
Definition: varlen_sort.h:101
int n
Definition: xcom_base.c:425
ptrdiff_t operator-(const varlen_iterator &other) const
Definition: varlen_sort.h:147
varlen_iterator operator++(int)
Definition: varlen_sort.h:111
size_t elem_size
Definition: varlen_sort.h:73
varlen_iterator operator-(size_t n) const
Definition: varlen_sort.h:143
unsigned char * ptr
Definition: varlen_sort.h:178
varlen_iterator()
Definition: varlen_sort.h:108
bool operator>=(varlen_iterator &other) const
Definition: varlen_sort.h:167
varlen_iterator operator--(int)
Definition: varlen_sort.h:122
varlen_iterator & operator--()
Definition: varlen_sort.h:118
varlen_element(varlen_element &&other)
Definition: varlen_sort.h:54
varlen_element & operator=(varlen_element &&other)
Definition: varlen_sort.h:65