MySQL 8.3.0
Source Code Documentation
bit_utils.h
Go to the documentation of this file.
1/* Copyright (c) 2020, 2023, Oracle and/or its affiliates.
2
3 This program is free software; you can redistribute it and/or modify
4 it under the terms of the GNU General Public License, version 2.0,
5 as published by the Free Software Foundation.
6
7 This program is also distributed with certain software (including
8 but not limited to OpenSSL) that is licensed under separate terms,
9 as designated in a particular file or component or in included license
10 documentation. The authors of MySQL hereby grant you an additional
11 permission to link the program and your derivative works with the
12 separately licensed software that they have included with MySQL.
13
14 This program is distributed in the hope that it will be useful,
15 but WITHOUT ANY WARRANTY; without even the implied warranty of
16 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
17 GNU General Public License, version 2.0, for more details.
18
19 You should have received a copy of the GNU General Public License
20 along with this program; if not, write to the Free Software
21 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA */
22
23#ifndef SQL_JOIN_OPTIMIZER_BIT_UTILS_H
24#define SQL_JOIN_OPTIMIZER_BIT_UTILS_H 1
25
26#include <assert.h>
27#include <stddef.h>
28#include <stdint.h>
29#include <bit>
30#include "my_compiler.h"
31
32// Wraps iteration over interesting states (based on the given policy) over a
33// single uint64_t into an STL-style adapter.
34template <class Policy>
36 public:
37 class iterator {
38 private:
39 uint64_t m_state;
40
41 public:
42 explicit iterator(uint64_t state) : m_state(state) {}
43 bool operator==(const iterator &other) const {
44 return m_state == other.m_state;
45 }
46 bool operator!=(const iterator &other) const {
47 return m_state != other.m_state;
48 }
49 size_t operator*() const { return Policy::NextValue(m_state); }
51 m_state = Policy::AdvanceState(m_state);
52 return *this;
53 }
54 };
55
56 explicit BitIteratorAdaptor(uint64_t state) : m_initial_state(state) {}
57
59 iterator end() const { return iterator{0}; }
60
61 private:
62 const uint64_t m_initial_state;
63};
64
65inline size_t FindLowestBitSet(uint64_t x) {
66 assert(x != 0);
67#if defined(__GNUC__) && defined(__x86_64__)
68 // Using this instead of ffsll() or std::countr_zero() (which map to the same
69 // instruction, but has an extra zero test and return an int value) helps
70 // a whopping 10% on some of the microbenchmarks! (GCC 9.2, Skylake.)
71 // Evidently, the test for zero is rewritten into a conditional move,
72 // which turns out to be add a lot of latency into these hot loops.
73 // GCC also adds an unnecessary sign extension of the result on some
74 // architectures; see https://gcc.gnu.org/bugzilla/show_bug.cgi?id=29776.
75 //
76 // Revisit if this is necessary once we move to C++23, as the C++23 construct
77 // [[assume(x != 0)]] seems to get rid of the conditional move. Also, if the
78 // target architecture supports a similar instruction which is well-defined
79 // for zero, like TZCNT in x86-64-v3, GCC eliminates both the conditional move
80 // and the sign extension, and there's no need for any inline assembly.
81 size_t idx;
82 asm("bsfq %1,%q0" : "=r"(idx) : "rm"(x));
83 return idx;
84#else
85 return std::countr_zero(x);
86#endif
87}
88
89// A policy for BitIteratorAdaptor that gives out the index of each set bit in
90// the value, ascending.
92 public:
93 static size_t NextValue(uint64_t state) {
94 // Find the lowest set bit.
95 return FindLowestBitSet(state);
96 }
97
98 static uint64_t AdvanceState(uint64_t state) {
99 // Clear the lowest set bit.
100 assert(state != 0);
101 return state & (state - 1);
102 }
103};
104
105// Same as CountBitsAscending, just descending.
107 public:
108 static size_t NextValue(uint64_t state) {
109 // Find the highest set bit.
110 assert(state != 0);
111 return std::countl_zero(state) ^ 63u;
112 }
113
114 static uint64_t AdvanceState(uint64_t state) {
115 // Clear the highest set bit. (This is fewer operations
116 // then the standard bit-fiddling trick, especially given
117 // that NextValue() is probably already computed.)
118 return state & ~(uint64_t{1} << NextValue(state));
119 }
120};
121
124}
126 uint64_t state) {
128}
129
130// An iterator (for range-based for loops) that returns all non-zero subsets of
131// a given set. This includes the set itself.
132//
133// In the database literature, this algorithm is often attributed to
134// a 1995 paper of Vance and Maier, but it is known to be older than
135// that. In particular, here is a 1994 reference from Marcel van Kervinck:
136//
137// https://groups.google.com/forum/#!msg/rec.games.chess/KnJvBnhgDKU/yCi5yBx18PQJ
139 public:
140 class iterator {
141 private:
142 uint64_t m_state;
143 uint64_t m_set;
144
145 public:
146 iterator(uint64_t state, uint64_t set) : m_state(state), m_set(set) {}
147 bool operator==(const iterator &other) const {
148 assert(m_set == other.m_set);
149 return m_state == other.m_state;
150 }
151 bool operator!=(const iterator &other) const {
152 assert(m_set == other.m_set);
153 return m_state != other.m_state;
154 }
155 uint64_t operator*() const { return m_state; }
157 m_state = (m_state - m_set) & m_set;
158 return *this;
159 }
160 };
161
162 explicit NonzeroSubsetsOf(uint64_t set) : m_set(set) {}
163
165 // Suppress warning C4146 unary minus operator applied to unsigned type,
166 // result still unsigned
168 iterator begin() const { return {(-m_set) & m_set, m_set}; }
170 iterator end() const { return {0, m_set}; }
171
172 private:
173 const uint64_t m_set;
174};
175
176// Returns a bitmap representing a single table.
177constexpr uint64_t TableBitmap(unsigned x) { return uint64_t{1} << x; }
178
179// Returns a bitmap representing multiple tables.
180template <typename... Args>
181constexpr uint64_t TableBitmap(unsigned first, Args... rest) {
182 return TableBitmap(first) | TableBitmap(rest...);
183}
184
185// Returns a bitmap representing the semi-open interval [start, end).
187// Suppress warning C4146 unary minus operator applied to unsigned type,
188// result still unsigned
190inline uint64_t BitsBetween(unsigned start, unsigned end) {
191 assert(end >= start);
192 assert(end <= 64);
193 if (end == 64) {
194 if (start == 64) {
195 return 0;
196 } else {
197 return -(uint64_t{1} << start);
198 }
199 } else {
200 return (uint64_t{1} << end) - (uint64_t{1} << start);
201 }
202}
204
205// The same, just with a different name for clarity.
206inline uint64_t TablesBetween(unsigned start, unsigned end) {
207 return BitsBetween(start, end);
208}
209
210// Isolates the LSB of x. Ie., if x = 0b110001010, returns 0b000000010.
211// Zero input gives zero output.
213// Suppress warning C4146 unary minus operator applied to unsigned type,
214// result still unsigned
216inline uint64_t IsolateLowestBit(uint64_t x) { return x & (-x); }
218
219// Returns whether X is a subset of Y.
220inline bool IsSubset(uint64_t x, uint64_t y) { return (x & y) == x; }
221
222/// Returns whether X is a proper subset of Y.
223inline bool IsProperSubset(uint64_t x, uint64_t y) {
224 return IsSubset(x, y) && x != y;
225}
226
227// Returns whether X and Y overlap. Symmetric.
228inline bool Overlaps(uint64_t x, uint64_t y) { return (x & y) != 0; }
229
230// Returns whether the given bit is set in X.
231inline bool IsBitSet(int bit_num, uint64_t x) {
232 return Overlaps(x, uint64_t{1} << bit_num);
233}
234
235#endif // SQL_JOIN_OPTIMIZER_BIT_UTILS_H
bool IsProperSubset(uint64_t x, uint64_t y)
Returns whether X is a proper subset of Y.
Definition: bit_utils.h:223
uint64_t TablesBetween(unsigned start, unsigned end)
Definition: bit_utils.h:206
BitIteratorAdaptor< CountBitsDescending > BitsSetInDescending(uint64_t state)
Definition: bit_utils.h:125
bool IsSubset(uint64_t x, uint64_t y)
Definition: bit_utils.h:220
constexpr uint64_t TableBitmap(unsigned x)
Definition: bit_utils.h:177
uint64_t IsolateLowestBit(uint64_t x)
Definition: bit_utils.h:216
bool Overlaps(uint64_t x, uint64_t y)
Definition: bit_utils.h:228
uint64_t BitsBetween(unsigned start, unsigned end)
Definition: bit_utils.h:190
bool IsBitSet(int bit_num, uint64_t x)
Definition: bit_utils.h:231
BitIteratorAdaptor< CountBitsAscending > BitsSetIn(uint64_t state)
Definition: bit_utils.h:122
size_t FindLowestBitSet(uint64_t x)
Definition: bit_utils.h:65
Definition: bit_utils.h:37
bool operator!=(const iterator &other) const
Definition: bit_utils.h:46
iterator & operator++()
Definition: bit_utils.h:50
size_t operator*() const
Definition: bit_utils.h:49
uint64_t m_state
Definition: bit_utils.h:39
bool operator==(const iterator &other) const
Definition: bit_utils.h:43
iterator(uint64_t state)
Definition: bit_utils.h:42
Definition: bit_utils.h:35
const uint64_t m_initial_state
Definition: bit_utils.h:62
BitIteratorAdaptor(uint64_t state)
Definition: bit_utils.h:56
iterator begin() const
Definition: bit_utils.h:58
iterator end() const
Definition: bit_utils.h:59
Definition: bit_utils.h:91
static size_t NextValue(uint64_t state)
Definition: bit_utils.h:93
static uint64_t AdvanceState(uint64_t state)
Definition: bit_utils.h:98
Definition: bit_utils.h:106
static size_t NextValue(uint64_t state)
Definition: bit_utils.h:108
static uint64_t AdvanceState(uint64_t state)
Definition: bit_utils.h:114
Definition: bit_utils.h:140
bool operator!=(const iterator &other) const
Definition: bit_utils.h:151
uint64_t m_state
Definition: bit_utils.h:142
iterator & operator++()
Definition: bit_utils.h:156
uint64_t operator*() const
Definition: bit_utils.h:155
iterator(uint64_t state, uint64_t set)
Definition: bit_utils.h:146
uint64_t m_set
Definition: bit_utils.h:143
bool operator==(const iterator &other) const
Definition: bit_utils.h:147
Definition: bit_utils.h:138
NonzeroSubsetsOf(uint64_t set)
Definition: bit_utils.h:162
iterator end() const
Definition: bit_utils.h:170
const uint64_t m_set
Definition: bit_utils.h:173
iterator begin() const
Definition: bit_utils.h:168
static void start(mysql_harness::PluginFuncEnv *env)
Definition: http_auth_backend_plugin.cc:176
Header for compiler-dependent features.
#define MY_COMPILER_MSVC_DIAGNOSTIC_IGNORE(X)
Definition: my_compiler.h:254
#define MY_COMPILER_DIAGNOSTIC_PUSH()
save the compiler's diagnostic (enabled warnings, errors, ...) state
Definition: my_compiler.h:284
#define MY_COMPILER_DIAGNOSTIC_POP()
restore the compiler's diagnostic (enabled warnings, errors, ...) state
Definition: my_compiler.h:285
Cursor end()
A past-the-end Cursor.
Definition: rules_table_service.cc:191
constexpr std::enable_if_t< std::is_unsigned< T >::value, int > countr_zero(T x) noexcept
consecutive 0-bits starting from LSB (right).
Definition: bit.h:462
constexpr std::enable_if_t< std::is_unsigned< T >::value, int > countl_zero(T x) noexcept
consecutive 0-bits starting from MSB.
Definition: bit.h:447
std::set< Key, Compare, ut::allocator< Key > > set
Specialization of set which uses ut_allocator.
Definition: ut0new.h:2881