MySQL 8.3.0
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, 2023, 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#include <assert.h>
27
28#include "template_utils.h"
29
30#include <algorithm>
31#include <cstddef>
32#include <iterator>
33
34template <class RandomIt, class Compare>
35void my_insert_sort(RandomIt first, RandomIt last, Compare comp) {
36 for (RandomIt high_water_mark = first + 1; high_water_mark < last;
37 ++high_water_mark) {
38 for (RandomIt cur = high_water_mark; cur > first; --cur) {
39 RandomIt prev = cur - 1;
40 if (comp(*prev, *cur)) break;
41 std::iter_swap(cur - 1, cur);
42 }
43 }
44}
45
46/*
47 Conceptually similar to a struct { uchar[N] },
48 except that it just holds a reference to an underlying
49 array, instead of keeping the memory itself.
50*/
52 varlen_element(unsigned char *ptr_arg, size_t elem_size_arg)
53 : ptr(ptr_arg), elem_size(elem_size_arg) {}
54
55 varlen_element(const varlen_element &other) = delete;
56 varlen_element(varlen_element &&other) = delete;
57 varlen_element &operator=(const varlen_element &other) = delete;
59
60 unsigned char *ptr{nullptr};
61 size_t elem_size{0};
62};
63
64// ValueSwappable.
65inline void swap(const varlen_element &a, const varlen_element &b) {
66 assert(a.elem_size == b.elem_size);
67 std::swap_ranges(a.ptr, a.ptr + a.elem_size, b.ptr);
68}
69
70/**
71 A RandomAccessIterator that splits up a char/uchar array into fixed-length
72 elements. Conceptually similar to a _pointer_ to an uchar[N].
73*/
75 public:
76 varlen_iterator(unsigned char *ptr_arg, size_t elem_size_arg)
77 : ptr(ptr_arg), elem_size(elem_size_arg) {}
78
79 // Iterator (required for InputIterator).
82 ptr += elem_size;
83 return *this;
84 }
85
86 // EqualityComparable (required for InputIterator).
87 bool operator==(const varlen_iterator &other) const {
88 assert(elem_size == other.elem_size);
89 return ptr == other.ptr;
90 }
91
92 // InputIterator (required for ForwardIterator).
93 bool operator!=(const varlen_iterator &other) const {
94 return !(*this == other);
95 }
96
98
99 // DefaultConstructible (required for ForwardIterator).
100 varlen_iterator() = default;
101
102 // ForwardIterator (required for RandomAccessIterator).
104 varlen_iterator copy = *this;
105 ptr += elem_size;
106 return copy;
107 }
108
109 // BidirectionalIterator (required for RandomAccessIterator).
111 ptr -= elem_size;
112 return *this;
113 }
115 varlen_iterator copy = *this;
116 ptr -= elem_size;
117 return copy;
118 }
119
120 // RandomAccessIterator.
122 ptr += elem_size * n;
123 return *this;
124 }
125
127 ptr -= elem_size * n;
128 return *this;
129 }
130
133 }
134
137 }
138
139 ptrdiff_t operator-(const varlen_iterator &other) const {
140 assert(elem_size == other.elem_size);
141 assert((ptr - other.ptr) % elem_size == 0);
142 return (ptr - other.ptr) / elem_size;
143 }
144
145 varlen_element operator[](size_t i) const {
146 return varlen_element{ptr + i * elem_size, elem_size};
147 }
148
149 bool operator<(varlen_iterator &other) const {
150 assert(elem_size == other.elem_size);
151 return ptr < other.ptr;
152 }
153
154 bool operator>(varlen_iterator &other) const {
155 assert(elem_size == other.elem_size);
156 return ptr > other.ptr;
157 }
158
159 bool operator>=(varlen_iterator &other) const {
160 assert(elem_size == other.elem_size);
161 return ptr >= other.ptr;
162 }
163
164 bool operator<=(varlen_iterator &other) const {
165 assert(elem_size == other.elem_size);
166 return ptr <= other.ptr;
167 }
168
169 private:
170 unsigned char *ptr = nullptr;
171 size_t elem_size = 0;
172};
173
174namespace std {
175
176// Required for Iterator.
177template <>
178struct iterator_traits<varlen_iterator> : iterator_traits<varlen_element *> {
180};
181} // namespace std
182
183/*
184 Compare should be a functor that takes in two T*.
185 T does not need to be char or uchar.
186*/
187template <class T, class Compare>
188inline void varlen_sort(T *first, T *last, size_t elem_size, Compare comp) {
190 varlen_iterator(pointer_cast<unsigned char *>(first), elem_size),
191 varlen_iterator(pointer_cast<unsigned char *>(last), elem_size),
192 [comp](const varlen_element &a, const varlen_element &b) {
193 return comp(pointer_cast<T *>(a.ptr), pointer_cast<T *>(b.ptr));
194 });
195}
196
197#endif // !defined(VARLEN_SORT_INCLUDED)
A RandomAccessIterator that splits up a char/uchar array into fixed-length elements.
Definition: varlen_sort.h:74
bool operator!=(const varlen_iterator &other) const
Definition: varlen_sort.h:93
varlen_iterator(unsigned char *ptr_arg, size_t elem_size_arg)
Definition: varlen_sort.h:76
bool operator==(const varlen_iterator &other) const
Definition: varlen_sort.h:87
bool operator>(varlen_iterator &other) const
Definition: varlen_sort.h:154
unsigned char * ptr
Definition: varlen_sort.h:170
ptrdiff_t operator-(const varlen_iterator &other) const
Definition: varlen_sort.h:139
varlen_iterator & operator+=(size_t n)
Definition: varlen_sort.h:121
varlen_iterator()=default
varlen_iterator operator++(int)
Definition: varlen_sort.h:103
bool operator<=(varlen_iterator &other) const
Definition: varlen_sort.h:164
varlen_iterator operator-(size_t n) const
Definition: varlen_sort.h:135
varlen_iterator operator+(size_t n) const
Definition: varlen_sort.h:131
varlen_iterator & operator--()
Definition: varlen_sort.h:110
varlen_element operator*() const
Definition: varlen_sort.h:80
varlen_element operator[](size_t i) const
Definition: varlen_sort.h:145
varlen_iterator operator--(int)
Definition: varlen_sort.h:114
size_t elem_size
Definition: varlen_sort.h:171
bool operator<(varlen_iterator &other) const
Definition: varlen_sort.h:149
varlen_element operator->() const
Definition: varlen_sort.h:97
varlen_iterator & operator-=(size_t n)
Definition: varlen_sort.h:126
varlen_iterator & operator++()
Definition: varlen_sort.h:81
bool operator>=(varlen_iterator &other) const
Definition: varlen_sort.h:159
void copy(Shards< COUNT > &dst, const Shards< COUNT > &src) noexcept
Copy the counters, overwrite destination.
Definition: ut0counter.h:353
Definition: varlen_sort.h:174
Definition: varlen_sort.h:51
varlen_element & operator=(varlen_element &&other)=delete
varlen_element & operator=(const varlen_element &other)=delete
varlen_element(const varlen_element &other)=delete
varlen_element(varlen_element &&other)=delete
size_t elem_size
Definition: varlen_sort.h:61
varlen_element(unsigned char *ptr_arg, size_t elem_size_arg)
Definition: varlen_sort.h:52
unsigned char * ptr
Definition: varlen_sort.h:60
void my_insert_sort(RandomIt first, RandomIt last, Compare comp)
Definition: varlen_sort.h:35
void swap(const varlen_element &a, const varlen_element &b)
Definition: varlen_sort.h:65
void varlen_sort(T *first, T *last, size_t elem_size, Compare comp)
Definition: varlen_sort.h:188
int n
Definition: xcom_base.cc:508