MySQL 8.1.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 <string.h>
30#include "my_compiler.h"
31#ifdef _MSC_VER
32#include <intrin.h>
33#pragma intrinsic(_BitScanForward64)
34#pragma intrinsic(_BitScanReverse64)
35#endif
36
37// Wraps iteration over interesting states (based on the given policy) over a
38// single uint64_t into an STL-style adapter.
39template <class Policy>
41 public:
42 class iterator {
43 private:
44 uint64_t m_state;
45
46 public:
47 explicit iterator(uint64_t state) : m_state(state) {}
48 bool operator==(const iterator &other) const {
49 return m_state == other.m_state;
50 }
51 bool operator!=(const iterator &other) const {
52 return m_state != other.m_state;
53 }
54 size_t operator*() const { return Policy::NextValue(m_state); }
56 m_state = Policy::AdvanceState(m_state);
57 return *this;
58 }
59 };
60
61 explicit BitIteratorAdaptor(uint64_t state) : m_initial_state(state) {}
62
64 iterator end() const { return iterator{0}; }
65
66 private:
67 const uint64_t m_initial_state;
68};
69
70inline size_t FindLowestBitSet(uint64_t x) {
71 assert(x != 0);
72#ifdef _MSC_VER
73 unsigned long idx;
74 _BitScanForward64(&idx, x);
75 return idx;
76#elif defined(__GNUC__) && defined(__x86_64__)
77 // Using this instead of ffsll() (which maps to the same instruction,
78 // but has an extra zero test and returns an int value) helps
79 // a whopping 10% on some of the microbenchmarks! (GCC 9.2, Skylake.)
80 // Evidently, the test for zero is rewritten into a conditional move,
81 // which turns out to be add a lot of latency into these hot loops.
82 size_t idx;
83 asm("bsfq %1,%q0" : "=r"(idx) : "rm"(x));
84 return idx;
85#else
86 // The cast to unsigned at least gets rid of the sign extension.
87 return static_cast<unsigned>(ffsll(x)) - 1u;
88#endif
89}
90
91// A policy for BitIteratorAdaptor that gives out the index of each set bit in
92// the value, ascending.
94 public:
95 static size_t NextValue(uint64_t state) {
96 // Find the lowest set bit.
97 return FindLowestBitSet(state);
98 }
99
100 static uint64_t AdvanceState(uint64_t state) {
101 // Clear the lowest set bit.
102 assert(state != 0);
103 return state & (state - 1);
104 }
105};
106
107// Same as CountBitsAscending, just descending.
109 public:
110 static size_t NextValue(uint64_t state) {
111 // Find the lowest set bit.
112 assert(state != 0);
113#ifdef _MSC_VER
114 unsigned long idx;
115 _BitScanReverse64(&idx, state);
116 return idx;
117#else
118 return __builtin_clzll(state) ^ 63u;
119#endif
120 }
121
122 static uint64_t AdvanceState(uint64_t state) {
123 // Clear the highest set bit. (This is fewer operations
124 // then the standard bit-fiddling trick, especially given
125 // that NextValue() is probably already computed.)
126 return state & ~(uint64_t{1} << NextValue(state));
127 }
128};
129
132}
134 uint64_t state) {
136}
137
138// An iterator (for range-based for loops) that returns all non-zero subsets of
139// a given set. This includes the set itself.
140//
141// In the database literature, this algorithm is often attributed to
142// a 1995 paper of Vance and Maier, but it is known to be older than
143// that. In particular, here is a 1994 reference from Marcel van Kervinck:
144//
145// https://groups.google.com/forum/#!msg/rec.games.chess/KnJvBnhgDKU/yCi5yBx18PQJ
147 public:
148 class iterator {
149 private:
150 uint64_t m_state;
151 uint64_t m_set;
152
153 public:
154 iterator(uint64_t state, uint64_t set) : m_state(state), m_set(set) {}
155 bool operator==(const iterator &other) const {
156 assert(m_set == other.m_set);
157 return m_state == other.m_state;
158 }
159 bool operator!=(const iterator &other) const {
160 assert(m_set == other.m_set);
161 return m_state != other.m_state;
162 }
163 uint64_t operator*() const { return m_state; }
165 m_state = (m_state - m_set) & m_set;
166 return *this;
167 }
168 };
169
170 explicit NonzeroSubsetsOf(uint64_t set) : m_set(set) {}
171
173 // Suppress warning C4146 unary minus operator applied to unsigned type,
174 // result still unsigned
176 iterator begin() const { return {(-m_set) & m_set, m_set}; }
178 iterator end() const { return {0, m_set}; }
179
180 private:
181 const uint64_t m_set;
182};
183
184// Returns a bitmap representing a single table.
185constexpr uint64_t TableBitmap(unsigned x) { return uint64_t{1} << x; }
186
187// Returns a bitmap representing multiple tables.
188template <typename... Args>
189constexpr uint64_t TableBitmap(unsigned first, Args... rest) {
190 return TableBitmap(first) | TableBitmap(rest...);
191}
192
193// Returns a bitmap representing the semi-open interval [start, end).
195// Suppress warning C4146 unary minus operator applied to unsigned type,
196// result still unsigned
198inline uint64_t BitsBetween(unsigned start, unsigned end) {
199 assert(end >= start);
200 assert(end <= 64);
201 if (end == 64) {
202 if (start == 64) {
203 return 0;
204 } else {
205 return -(uint64_t{1} << start);
206 }
207 } else {
208 return (uint64_t{1} << end) - (uint64_t{1} << start);
209 }
210}
212
213// The same, just with a different name for clarity.
214inline uint64_t TablesBetween(unsigned start, unsigned end) {
215 return BitsBetween(start, end);
216}
217
218// Isolates the LSB of x. Ie., if x = 0b110001010, returns 0b000000010.
219// Zero input gives zero output.
221// Suppress warning C4146 unary minus operator applied to unsigned type,
222// result still unsigned
224inline uint64_t IsolateLowestBit(uint64_t x) { return x & (-x); }
226
227// Returns whether X is a subset of Y.
228inline bool IsSubset(uint64_t x, uint64_t y) { return (x & y) == x; }
229
230/// Returns whether X is a proper subset of Y.
231inline bool IsProperSubset(uint64_t x, uint64_t y) {
232 return IsSubset(x, y) && x != y;
233}
234
235// Returns whether X and Y overlap. Symmetric.
236inline bool Overlaps(uint64_t x, uint64_t y) { return (x & y) != 0; }
237
238// Returns whether X has more than one bit set.
239inline bool AreMultipleBitsSet(uint64_t x) { return (x & (x - 1)) != 0; }
240
241// Returns whether X has exactly one bit set.
242inline bool IsSingleBitSet(uint64_t x) {
243 return x != 0 && !AreMultipleBitsSet(x);
244}
245
246// Returns whether the given bit is set in X.
247inline bool IsBitSet(int bit_num, uint64_t x) {
248 return Overlaps(x, uint64_t{1} << bit_num);
249}
250
251// Fairly slow implementation of population count (number of bits set).
252inline int PopulationCount(uint64_t x) {
253 int count = 0;
254 while (x != 0) {
255 x &= x - 1;
256 ++count;
257 }
258 return count;
259}
260
261#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:231
uint64_t TablesBetween(unsigned start, unsigned end)
Definition: bit_utils.h:214
bool AreMultipleBitsSet(uint64_t x)
Definition: bit_utils.h:239
bool IsSingleBitSet(uint64_t x)
Definition: bit_utils.h:242
BitIteratorAdaptor< CountBitsDescending > BitsSetInDescending(uint64_t state)
Definition: bit_utils.h:133
bool IsSubset(uint64_t x, uint64_t y)
Definition: bit_utils.h:228
constexpr uint64_t TableBitmap(unsigned x)
Definition: bit_utils.h:185
uint64_t IsolateLowestBit(uint64_t x)
Definition: bit_utils.h:224
bool Overlaps(uint64_t x, uint64_t y)
Definition: bit_utils.h:236
uint64_t BitsBetween(unsigned start, unsigned end)
Definition: bit_utils.h:198
bool IsBitSet(int bit_num, uint64_t x)
Definition: bit_utils.h:247
int PopulationCount(uint64_t x)
Definition: bit_utils.h:252
BitIteratorAdaptor< CountBitsAscending > BitsSetIn(uint64_t state)
Definition: bit_utils.h:130
size_t FindLowestBitSet(uint64_t x)
Definition: bit_utils.h:70
Definition: bit_utils.h:42
bool operator!=(const iterator &other) const
Definition: bit_utils.h:51
iterator & operator++()
Definition: bit_utils.h:55
size_t operator*() const
Definition: bit_utils.h:54
uint64_t m_state
Definition: bit_utils.h:44
bool operator==(const iterator &other) const
Definition: bit_utils.h:48
iterator(uint64_t state)
Definition: bit_utils.h:47
Definition: bit_utils.h:40
const uint64_t m_initial_state
Definition: bit_utils.h:67
BitIteratorAdaptor(uint64_t state)
Definition: bit_utils.h:61
iterator begin() const
Definition: bit_utils.h:63
iterator end() const
Definition: bit_utils.h:64
Definition: bit_utils.h:93
static size_t NextValue(uint64_t state)
Definition: bit_utils.h:95
static uint64_t AdvanceState(uint64_t state)
Definition: bit_utils.h:100
Definition: bit_utils.h:108
static size_t NextValue(uint64_t state)
Definition: bit_utils.h:110
static uint64_t AdvanceState(uint64_t state)
Definition: bit_utils.h:122
Definition: bit_utils.h:148
bool operator!=(const iterator &other) const
Definition: bit_utils.h:159
uint64_t m_state
Definition: bit_utils.h:150
iterator & operator++()
Definition: bit_utils.h:164
uint64_t operator*() const
Definition: bit_utils.h:163
iterator(uint64_t state, uint64_t set)
Definition: bit_utils.h:154
uint64_t m_set
Definition: bit_utils.h:151
bool operator==(const iterator &other) const
Definition: bit_utils.h:155
Definition: bit_utils.h:146
NonzeroSubsetsOf(uint64_t set)
Definition: bit_utils.h:170
iterator end() const
Definition: bit_utils.h:178
const uint64_t m_set
Definition: bit_utils.h:181
iterator begin() const
Definition: bit_utils.h:176
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
static int count
Definition: myisam_ftdump.cc:44
Cursor end()
A past-the-end Cursor.
Definition: rules_table_service.cc:191
std::set< Key, Compare, ut::allocator< Key > > set
Specialization of set which uses ut_allocator.
Definition: ut0new.h:2881