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