MySQL 8.0.30
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, 2022, 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
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.
78static 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).
109 varlen_iterator() = default;
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
142 }
143
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
183namespace std {
184
185// Required for Iterator.
186template <>
187struct 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*/
195template <class T, class Compare>
196inline 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(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+=(size_t n)
Definition: varlen_sort.h:130
varlen_iterator()=default
varlen_iterator operator++(int)
Definition: varlen_sort.h:112
bool operator<=(varlen_iterator &other) const
Definition: varlen_sort.h:173
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_iterator & operator--()
Definition: varlen_sort.h:119
varlen_element operator*() const
Definition: varlen_sort.h:90
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
varlen_iterator & operator-=(size_t n)
Definition: varlen_sort.h:135
varlen_iterator & operator++()
Definition: varlen_sort.h:91
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(varlen_element &other)=delete
size_t elem_size
Definition: varlen_sort.h:74
varlen_element & operator=(varlen_element &&other)
Definition: varlen_sort.h:66
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:505