MySQL 8.0.30
Source Code Documentation
bit_utils.h
Go to the documentation of this file.
1/* Copyright (c) 2020, 2022, 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.
185inline uint64_t TableBitmap(unsigned x) { return uint64_t{1} << x; }
186
187// Returns a bitmap representing the semi-open interval [start, end).
189// Suppress warning C4146 unary minus operator applied to unsigned type,
190// result still unsigned
192inline uint64_t BitsBetween(unsigned start, unsigned end) {
193 assert(end >= start);
194 assert(end <= 64);
195 if (end == 64) {
196 if (start == 64) {
197 return 0;
198 } else {
199 return -(uint64_t{1} << start);
200 }
201 } else {
202 return (uint64_t{1} << end) - (uint64_t{1} << start);
203 }
204}
206
207// The same, just with a different name for clarity.
208inline uint64_t TablesBetween(unsigned start, unsigned end) {
209 return BitsBetween(start, end);
210}
211
212// Isolates the LSB of x. Ie., if x = 0b110001010, returns 0b000000010.
213// Zero input gives zero output.
215// Suppress warning C4146 unary minus operator applied to unsigned type,
216// result still unsigned
218inline uint64_t IsolateLowestBit(uint64_t x) { return x & (-x); }
220
221// Returns whether X is a subset of Y.
222inline bool IsSubset(uint64_t x, uint64_t y) { return (x & y) == x; }
223
224/// Returns whether X is a proper subset of Y.
225inline bool IsProperSubset(uint64_t x, uint64_t y) {
226 return IsSubset(x, y) && x != y;
227}
228
229// Returns whether X and Y overlap. Symmetric.
230inline bool Overlaps(uint64_t x, uint64_t y) { return (x & y) != 0; }
231
232// Returns whether X is a power of two.
233inline bool IsSingleBitSet(uint64_t x) { return (x & (x - 1)) == 0; }
234
235// Returns whether the given bit is set in X.
236inline bool IsBitSet(int bit_num, uint64_t x) {
237 return Overlaps(x, uint64_t{1} << bit_num);
238}
239
240// Fairly slow implementation of population count (number of bits set).
241inline int PopulationCount(uint64_t x) {
242 int count = 0;
243 while (x != 0) {
244 x &= x - 1;
245 ++count;
246 }
247 return count;
248}
249
250#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:225
uint64_t TablesBetween(unsigned start, unsigned end)
Definition: bit_utils.h:208
bool IsSingleBitSet(uint64_t x)
Definition: bit_utils.h:233
BitIteratorAdaptor< CountBitsDescending > BitsSetInDescending(uint64_t state)
Definition: bit_utils.h:133
bool IsSubset(uint64_t x, uint64_t y)
Definition: bit_utils.h:222
uint64_t IsolateLowestBit(uint64_t x)
Definition: bit_utils.h:218
bool Overlaps(uint64_t x, uint64_t y)
Definition: bit_utils.h:230
uint64_t BitsBetween(unsigned start, unsigned end)
Definition: bit_utils.h:192
bool IsBitSet(int bit_num, uint64_t x)
Definition: bit_utils.h:236
int PopulationCount(uint64_t x)
Definition: bit_utils.h:241
uint64_t TableBitmap(unsigned x)
Definition: bit_utils.h:185
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:168
Header for compiler-dependent features.
#define MY_COMPILER_MSVC_DIAGNOSTIC_IGNORE(X)
Definition: my_compiler.h:265
#define MY_COMPILER_DIAGNOSTIC_PUSH()
save the compiler's diagnostic (enabled warnings, errors, ...) state
Definition: my_compiler.h:295
#define MY_COMPILER_DIAGNOSTIC_POP()
restore the compiler's diagnostic (enabled warnings, errors, ...) state
Definition: my_compiler.h:296
static int count
Definition: myisam_ftdump.cc:42
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:2863