MySQL 8.0.32
Source Code Documentation
overflow_bitset.h
Go to the documentation of this file.
1/* Copyright (c) 2021, 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_OVERFLOW_BITSET_H
24#define SQL_JOIN_OPTIMIZER_OVERFLOW_BITSET_H
25
26/**
27 @file
28
29 OverflowBitset is a fixed-size (once allocated) bitmap that is optimized for
30 the common case of few elements, yet can support an arbitrary number.
31 For 63 bits or fewer, it fits into a simple 64-bit machine word; for more,
32 it instead “overflows” to a pointer to externally-allocated storage
33 (typically on a MEM_ROOT). In other words, one loses only 1 bit for the common
34 (small) case. For small (“inline”) bit sets, most operations are simple
35 bit-twiddling operations, adding only a small and easily-predicatable test to
36 each of them.
37
38 This is possible because a pointer to external storage of 64-bit values
39 will (must) be aligned to 8 bytes, so the lowest bit of the address
40 cannot be 1. We can use this to distinguish between inline and non-inline
41 sets.
42
43 There are two classes: OverflowBitset is an immutable (const) bitset with
44 value semantics; it can be freely assigned, copied, stored in AccessPath
45 (which also has value semantics), etc. with no worries, but not modified.
46 (The storage is never freed; it is presumed to live on a MEM_ROOT.)
47 MutableOverflowBitset can be modified, but it is move-only; this avoids
48 the problem where one takes a copy of a (non-inline) bit set and then
49 modify one of them, not expecting that modification to also affect
50 the other one. (Ie., it avoids the design mistake in String, where the
51 copy constructor unexpectedly can become a shallow copy, but not always.)
52 MutableOverflowBitset can be converted to OverflowBitset by means of a
53 move, at which point it is effectively frozen and cannot be changed further.
54
55 For simplicity, most operations over OverflowBitset require the two
56 bit sets to be of the same size. The exception is that an all-zero inline
57 bit set can be tested against others in Overlaps(); this is useful so that we
58 don't need to initialize bit sets in AccessPath that never have any filters
59 set (the default constructor makes them inline and all-zero).
60 */
61
62#include <assert.h>
63#include <limits.h>
64#include <stddef.h>
65#include <stdint.h>
66#include <string.h>
67
68#include <array>
69#include <tuple>
70
71#include "my_alloc.h"
73
75
77 public:
78 // Default is to zero-initialize.
80
81 explicit OverflowBitset(uint32_t bits) : m_bits((uintptr_t{bits} << 1) | 1) {
82 // Check that we didn't overflow on 32-bit platforms.
83 assert((m_bits >> 1) == bits);
84 }
85
86 // Reset the entire bitset to an inline all-zero bitset.
87 // This is distinct from ClearBits(), which only clears a given number
88 // of bits, and does not change the capacity.
89 void Clear() { m_bits = 1; }
90
91 // Value semantics, so:
92 OverflowBitset(const OverflowBitset &) = default;
96
97 // Can move-convert MutableOverflowBitset into OverflowBitset.
100
101 bool is_inline() const { return m_bits & 1; }
102 bool empty() { return m_bits == 1; }
103
104 size_t capacity() const {
105 if (is_inline()) {
106 return kInlineBits;
107 } else {
108 return m_ext->m_num_blocks * sizeof(uint64_t) * CHAR_BIT;
109 }
110 }
111
113
114 bool IsContainedIn(const MEM_ROOT *mem_root) const {
115 return !is_inline() && mem_root->Contains(m_ext);
116 }
117
118 // NOTE: These could also be made to take in MutableOverflowBitset(),
119 // simply by templating them (due to the private inheritance).
126
127 protected:
128 struct Ext {
130 uint64_t m_bits[1];
131 };
132 static_assert(alignof(Ext) % 2 == 0, "The lowest bit must be zero.");
133
134 union {
135 uint64_t m_bits; // Lowest bit must be 1.
137 };
138 static constexpr int kInlineBits = sizeof(m_bits) * CHAR_BIT - 1;
139
140 void InitOverflow(MEM_ROOT *mem_root, size_t capacity);
147
148 friend bool Overlaps(OverflowBitset a, OverflowBitset b);
150 friend bool IsSubset(OverflowBitset a, OverflowBitset b);
152 friend bool IsBitSet(int bit_num, OverflowBitset x);
153 friend bool IsBitSetOverflow(int bit_num, OverflowBitset x);
154 friend bool IsEmpty(OverflowBitset x);
155 friend int PopulationCount(OverflowBitset x);
157 template <size_t N, class Combine>
160};
161static_assert(
162 sizeof(OverflowBitset) <= sizeof(uint64_t),
163 "OverflowBitset is intended to be as compact as a regular 64-bit set.");
164
165// Private inheritance, so that the only way of converting to OverflowBitset
166// for external callers is by a move-convert.
168 public:
169 // NOTE: Will round up the given capacity to either 31/63 (for anything
170 // smaller than 32/64), or to the next multiple of 64 (for anything else).
172 if (capacity <= kInlineBits) {
173 m_bits = 1;
174 } else {
176 }
177 }
178
179 // Move-only, so that we don't inadvertently modify aliases.
183 m_bits = other.m_bits;
184 other.m_bits = 1;
185 }
187 m_bits = other.m_bits;
188 other.m_bits = 1;
189 return *this;
190 }
191
192 void SetBit(int bit_num) {
193 assert(bit_num >= 0);
194 assert(static_cast<size_t>(bit_num) < capacity());
195 const unsigned bn = bit_num; // To avoid sign extension taking time.
196 if (is_inline()) {
197 assert(bit_num < 63);
198 m_bits |= uint64_t{1} << (bn + 1);
199 } else {
200 m_ext->m_bits[bn / 64] |= uint64_t{1} << (bn % 64);
201 }
202 }
203
204 void ClearBits(int begin_bit_num, int end_bit_num) {
205 assert(begin_bit_num >= 0);
206 assert(end_bit_num >= 0);
207 assert(begin_bit_num <= end_bit_num);
208 assert(static_cast<size_t>(begin_bit_num) <= capacity());
209 assert(static_cast<size_t>(end_bit_num) <= capacity());
210 if (is_inline()) {
211 m_bits &= ~BitsBetween(begin_bit_num + 1, end_bit_num + 1);
212 } else {
213 ClearBitsOverflow(begin_bit_num, end_bit_num);
214 }
215 }
216
217 inline void ClearBit(int bit_num) {
218 // TODO: Consider a more specialized version here if it starts
219 // showing up in the profiles.
220 ClearBits(bit_num, bit_num + 1);
221 }
222
225 }
226
227 private:
228 friend bool IsBitSet(int bit_num, const MutableOverflowBitset &x);
229 friend bool Overlaps(OverflowBitset a, const MutableOverflowBitset &b);
230 friend bool Overlaps(const MutableOverflowBitset &a,
231 const MutableOverflowBitset &b);
232 friend bool Overlaps(const MutableOverflowBitset &a, OverflowBitset b);
233 friend bool IsSubset(OverflowBitset a, const MutableOverflowBitset &b);
234 friend bool IsSubset(const MutableOverflowBitset &a,
235 const MutableOverflowBitset &b);
236 friend bool IsSubset(const MutableOverflowBitset &a, OverflowBitset b);
237 friend bool IsEmpty(const MutableOverflowBitset &x);
238 friend int PopulationCount(const MutableOverflowBitset &x);
239 void SetBitOverflow(int bit_num);
240 void ClearBitsOverflow(int begin_bit_num, int end_bit_num);
241
242 friend class OverflowBitset;
243};
244
246 m_bits = other.m_bits;
247 other.m_bits = 1;
248}
249
251 MutableOverflowBitset &&other) {
252 m_bits = other.m_bits;
253 other.m_bits = 1;
254 return *this;
255}
256
259 if (is_inline()) {
260 ret.m_bits = m_bits;
261 } else {
262 memcpy(ret.m_ext, m_ext,
263 sizeof(m_ext->m_num_blocks) +
264 m_ext->m_num_blocks * sizeof(m_ext->m_bits));
265 }
266 return ret;
267}
268
271 OverflowBitset b) {
272 assert(a.is_inline() == b.is_inline());
273 assert(a.capacity() == b.capacity());
274 if (a.is_inline()) {
276 ret.m_bits = a.m_bits | b.m_bits;
277 return ret;
278 } else {
279 return OrOverflow(mem_root, a, b);
280 }
281}
282
285 OverflowBitset b) {
286 assert(a.is_inline() == b.is_inline());
287 assert(a.capacity() == b.capacity());
288 if (a.is_inline()) {
290 ret.m_bits = a.m_bits & b.m_bits;
291 return ret;
292 } else {
293 return AndOverflow(mem_root, a, b);
294 }
295}
296
299 OverflowBitset b) {
300 assert(a.is_inline() == b.is_inline());
301 assert(a.capacity() == b.capacity());
302 if (a.is_inline()) {
304 ret.m_bits = (a.m_bits ^ b.m_bits) | 1;
305 return ret;
306 } else {
307 return XorOverflow(mem_root, a, b);
308 }
309}
310
311// Definitions overloading utility functions in bit_utils.h, making it generally
312// possible to use OverflowBitset as we use regular uint64_t bitsets
313// (e.g. NodeMap).
314//
315// Since one cannot easily combine non-inline OverflowBitsets without allocating
316// memory, the BitsSetIn() overload supports combining state as-we-go.
317// For instance, where you would normally write (for uint64_t)
318//
319// for (int bit_idx : BitsSetIn(x & y))
320//
321// you would use this variation for OverflowBitsets:
322//
323// for (int bit_idx : BitsSetInBoth(x, y))
324//
325// Under the hood, BitsSetInBoth() calls a Combine functor that ANDs the two
326// uint64_t bitwise (for inline bitsets only once, but for overflow bitsets
327// multiple times, on-demand as we iterate), which can potentially save
328// on a lot of bitscan operations and loop iterations versus trying to test
329// one-by-one. This can be extended to any number of arguments.
330//
331// Combine::operator() must be const, Combine must be movable (but can have
332// state).
333
334template <size_t N, class Combine>
336 public:
337 class iterator {
338 private:
339 const Combine *m_combine;
340 uint64_t m_state;
341
342 // m_next holds, for each bitset array, the pointer to the next
343 // uint64_t to be processed/read (once m_state is zero, ie.,
344 // there are no more bits in the current state). When m_next[0] == m_end,
345 // iteration is over. For inline bitsets, m_next[0] == m_end == nullptr,
346 // so once the first 64-bit group is processed, we are done.
347 // (We assume all arrays have the same length, so we only need one
348 // end pointer.)
349 std::array<const uint64_t *, N> m_next;
350 const uint64_t *const m_end;
352
353 public:
354 // For inline bitsets.
355 iterator(uint64_t state, const Combine *combine)
356 : m_combine(combine), m_state(state), m_end(nullptr), m_base(0) {
357 m_next[0] = nullptr;
358 }
359
360 // For overflow bitsets.
361 iterator(const std::array<const uint64_t *, N> begin, const uint64_t *end,
362 const Combine *combine)
363 : m_combine(combine),
364 m_state(0),
365 m_next(begin),
366 m_end(end),
367 m_base(-64) {
368 while (m_state == 0 && m_next[0] != m_end) {
370 for (size_t i = 0; i < N; ++i) {
371 ++m_next[i];
372 }
373 m_base += 64;
374 }
375 }
376
377 bool operator==(const iterator &other) const {
378 assert(m_end == other.m_end);
379 return m_state == other.m_state && m_next[0] == other.m_next[0];
380 }
381 bool operator!=(const iterator &other) const {
382 assert(m_end == other.m_end);
383 return m_state != other.m_state || m_next[0] != other.m_next[0];
384 }
385 size_t operator*() const { return FindLowestBitSet(m_state) + m_base; }
387 // Clear the lowest set bit.
388 assert(m_state != 0);
389 m_state = m_state & (m_state - 1);
390
391 while (m_state == 0 && m_next[0] != m_end) {
393 for (size_t i = 0; i < N; ++i) {
394 ++m_next[i];
395 }
396 m_base += 64;
397 }
398 return *this;
399 }
400 };
401
402 OverflowBitsetBitsIn(std::array<OverflowBitset, N> bitsets, Combine combine)
403 : m_bitsets(bitsets), m_combine(std::move(combine)) {}
404
405 iterator begin() const {
406 if (m_bitsets[0].is_inline()) {
407 std::array<uint64_t, N> bits;
408 for (size_t i = 0; i < N; ++i) {
409 assert(m_bitsets[i].is_inline());
410 bits[i] = m_bitsets[i].m_bits;
411 }
412 uint64_t state = std::apply(m_combine, bits);
413 return iterator{state >> 1, &m_combine};
414 } else {
415 std::array<const uint64_t *, N> ptrs;
416 for (size_t i = 0; i < N; ++i) {
417 assert(!m_bitsets[i].is_inline());
418 assert(m_bitsets[i].capacity() == m_bitsets[0].capacity());
419 ptrs[i] = m_bitsets[i].m_ext->m_bits;
420 }
421 const uint64_t *end =
422 m_bitsets[0].m_ext->m_bits + m_bitsets[0].m_ext->m_num_blocks;
423 return iterator{ptrs, end, &m_combine};
424 }
425 }
426 iterator end() const {
427 if (m_bitsets[0].is_inline()) {
428 return iterator{0, &m_combine};
429 } else {
430 std::array<const uint64_t *, N> ptrs;
431 for (size_t i = 0; i < N; ++i) {
432 assert(m_bitsets[i].is_inline() == m_bitsets[0].is_inline());
433 assert(m_bitsets[i].capacity() == m_bitsets[0].capacity());
434 ptrs[i] = m_bitsets[i].m_ext->m_bits + m_bitsets[i].m_ext->m_num_blocks;
435 }
436 return iterator{ptrs, ptrs[0], &m_combine};
437 }
438 }
439
440 private:
441 static inline uint64_t ReadAndCombine(
442 const std::array<const uint64_t *, N> &ptrs, const Combine *combine) {
443 std::array<uint64_t, N> bits;
444 for (size_t i = 0; i < N; ++i) {
445 bits[i] = *ptrs[i];
446 }
447 return std::apply(*combine, bits);
448 }
449
450 const std::array<OverflowBitset, N> m_bitsets;
451 const Combine m_combine;
452};
453
455 uint64_t operator()(uint64_t x) const { return x; }
456};
457inline auto BitsSetIn(OverflowBitset bitset) {
459}
460
462 uint64_t operator()(uint64_t x, uint64_t y) const { return x & y; }
463};
464inline auto BitsSetInBoth(OverflowBitset bitset_a, OverflowBitset bitset_b) {
465 return OverflowBitsetBitsIn<2, AndCombine>{{bitset_a, bitset_b},
466 AndCombine()};
467}
468
470
472 if (a.m_bits == 1 || b.m_bits == 1) {
473 // Empty and inline, so nothing overlaps.
474 // This is a special case that does not require the two
475 // sets to be of the same size (see file comment).
476 return false;
477 }
478 assert(a.is_inline() == b.is_inline());
479 assert(a.capacity() == b.capacity());
480 if (a.is_inline()) {
481 return (a.m_bits & b.m_bits) != 1;
482 } else {
483 return OverlapsOverflow(a, b);
484 }
485}
486
488 return Overlaps(a, static_cast<const OverflowBitset &>(b));
489}
490
491inline bool Overlaps(const MutableOverflowBitset &a,
492 const MutableOverflowBitset &b) {
493 return Overlaps(static_cast<const OverflowBitset &>(a),
494 static_cast<const OverflowBitset &>(b));
495}
496
498 return Overlaps(static_cast<const OverflowBitset &>(a), b);
499}
500
502 assert(a.is_inline() == b.is_inline());
503 assert(a.capacity() == b.capacity());
504 if (a.is_inline()) {
505 return IsSubset(a.m_bits, b.m_bits);
506 } else {
507 return IsSubsetOverflow(a, b);
508 }
509}
510
511inline bool IsBitSet(int bit_num, OverflowBitset x) {
512 assert(bit_num >= 0);
513 assert(static_cast<size_t>(bit_num) < x.capacity());
514 const unsigned bn = bit_num; // To avoid sign extension taking time.
515 if (x.is_inline()) {
516 return Overlaps(x.m_bits, uint64_t{1} << (bn + 1));
517 } else {
518 return Overlaps(x.m_ext->m_bits[bn / 64], uint64_t{1} << (bn % 64));
519 }
520}
521
522inline bool IsBitSet(int bit_num, const MutableOverflowBitset &x) {
523 return IsBitSet(bit_num, static_cast<const OverflowBitset &>(x));
524}
525
527 return IsSubset(a, static_cast<const OverflowBitset &>(b));
528}
529
530inline bool IsSubset(const MutableOverflowBitset &a,
531 const MutableOverflowBitset &b) {
532 return IsSubset(static_cast<const OverflowBitset &>(a),
533 static_cast<const OverflowBitset &>(b));
534}
535
537 return IsSubset(static_cast<const OverflowBitset &>(a), b);
538}
539
540// This is mostly used to guard a few asserts, so it's better that it's
541// completely visible, so that the compiler can remove it totally
542// in optimized mode.
543inline bool IsEmpty(OverflowBitset x) {
544 if (x.is_inline()) {
545 return x.m_bits == 1;
546 } else {
547 for (unsigned i = 0; i < x.m_ext->m_num_blocks; ++i) {
548 if (x.m_ext->m_bits[i] != 0) {
549 return false;
550 }
551 }
552 return true;
553 }
554}
555
556inline bool IsEmpty(const MutableOverflowBitset &x) {
557 return IsEmpty(static_cast<const OverflowBitset &>(x));
558}
559
561 if (x.is_inline()) {
562 return PopulationCount(x.m_bits) - 1;
563 } else {
564 return PopulationCountOverflow(x);
565 }
566}
567
568/// Find the nuber of bits set in 'x'.
570 return PopulationCount(static_cast<const OverflowBitset &>(x));
571}
572
573#endif // SQL_JOIN_OPTIMIZER_OVERFLOW_BITSET_H
size_t FindLowestBitSet(uint64_t x)
Definition: bit_utils.h:70
Definition: overflow_bitset.h:167
void ClearBits(int begin_bit_num, int end_bit_num)
Definition: overflow_bitset.h:204
MutableOverflowBitset(MutableOverflowBitset &&other)
Definition: overflow_bitset.h:182
friend int PopulationCount(const MutableOverflowBitset &x)
Find the nuber of bits set in 'x'.
Definition: overflow_bitset.h:569
friend bool IsBitSet(int bit_num, const MutableOverflowBitset &x)
Definition: overflow_bitset.h:522
void ClearBitsOverflow(int begin_bit_num, int end_bit_num)
Definition: overflow_bitset.cc:79
void SetBit(int bit_num)
Definition: overflow_bitset.h:192
friend bool IsSubset(OverflowBitset a, const MutableOverflowBitset &b)
Definition: overflow_bitset.h:526
MutableOverflowBitset & operator=(const MutableOverflowBitset &)=delete
friend bool Overlaps(OverflowBitset a, const MutableOverflowBitset &b)
Definition: overflow_bitset.h:487
MutableOverflowBitset(MEM_ROOT *mem_root, size_t capacity)
Definition: overflow_bitset.h:171
friend class OverflowBitset
Definition: overflow_bitset.h:242
friend bool IsEmpty(const MutableOverflowBitset &x)
Definition: overflow_bitset.h:556
MutableOverflowBitset(const MutableOverflowBitset &)=delete
void SetBitOverflow(int bit_num)
MutableOverflowBitset & operator=(MutableOverflowBitset &&other)
Definition: overflow_bitset.h:186
void ClearBit(int bit_num)
Definition: overflow_bitset.h:217
MutableOverflowBitset Clone(MEM_ROOT *mem_root) const
Definition: overflow_bitset.h:223
Definition: overflow_bitset.h:337
const Combine * m_combine
Definition: overflow_bitset.h:339
bool operator==(const iterator &other) const
Definition: overflow_bitset.h:377
iterator(uint64_t state, const Combine *combine)
Definition: overflow_bitset.h:355
size_t operator*() const
Definition: overflow_bitset.h:385
iterator(const std::array< const uint64_t *, N > begin, const uint64_t *end, const Combine *combine)
Definition: overflow_bitset.h:361
bool operator!=(const iterator &other) const
Definition: overflow_bitset.h:381
std::array< const uint64_t *, N > m_next
Definition: overflow_bitset.h:349
const uint64_t *const m_end
Definition: overflow_bitset.h:350
int m_base
Definition: overflow_bitset.h:351
iterator & operator++()
Definition: overflow_bitset.h:386
uint64_t m_state
Definition: overflow_bitset.h:340
Definition: overflow_bitset.h:335
iterator end() const
Definition: overflow_bitset.h:426
static uint64_t ReadAndCombine(const std::array< const uint64_t *, N > &ptrs, const Combine *combine)
Definition: overflow_bitset.h:441
iterator begin() const
Definition: overflow_bitset.h:405
const std::array< OverflowBitset, N > m_bitsets
Definition: overflow_bitset.h:450
const Combine m_combine
Definition: overflow_bitset.h:451
OverflowBitsetBitsIn(std::array< OverflowBitset, N > bitsets, Combine combine)
Definition: overflow_bitset.h:402
Definition: overflow_bitset.h:76
friend bool IsSubset(OverflowBitset a, OverflowBitset b)
Definition: overflow_bitset.h:501
bool IsContainedIn(const MEM_ROOT *mem_root) const
Definition: overflow_bitset.h:114
static MutableOverflowBitset Or(MEM_ROOT *mem_root, OverflowBitset a, OverflowBitset b)
Definition: overflow_bitset.h:269
friend int PopulationCountOverflow(OverflowBitset x)
Definition: overflow_bitset.cc:137
friend bool Overlaps(OverflowBitset a, OverflowBitset b)
Definition: overflow_bitset.h:471
OverflowBitset()
Definition: overflow_bitset.h:79
static MutableOverflowBitset OrOverflow(MEM_ROOT *mem_root, OverflowBitset a, OverflowBitset b)
Definition: overflow_bitset.cc:40
friend bool IsSubsetOverflow(OverflowBitset a, OverflowBitset b)
Definition: overflow_bitset.cc:125
friend int PopulationCount(OverflowBitset x)
Definition: overflow_bitset.h:560
MutableOverflowBitset Clone(MEM_ROOT *mem_root) const
Definition: overflow_bitset.h:257
size_t capacity() const
Definition: overflow_bitset.h:104
static constexpr int kInlineBits
Definition: overflow_bitset.h:138
bool empty()
Definition: overflow_bitset.h:102
OverflowBitset & operator=(const OverflowBitset &)=default
bool is_inline() const
Definition: overflow_bitset.h:101
static MutableOverflowBitset XorOverflow(MEM_ROOT *mem_root, OverflowBitset a, OverflowBitset b)
Definition: overflow_bitset.cc:66
friend bool OverlapsOverflow(OverflowBitset a, OverflowBitset b)
Definition: overflow_bitset.cc:113
static MutableOverflowBitset AndOverflow(MEM_ROOT *mem_root, OverflowBitset a, OverflowBitset b)
Definition: overflow_bitset.cc:53
uint64_t m_bits
Definition: overflow_bitset.h:135
OverflowBitset(const OverflowBitset &)=default
friend bool IsBitSetOverflow(int bit_num, OverflowBitset x)
friend bool IsEmpty(OverflowBitset x)
Definition: overflow_bitset.h:543
static MutableOverflowBitset And(MEM_ROOT *mem_root, OverflowBitset a, OverflowBitset b)
Definition: overflow_bitset.h:283
OverflowBitset(uint32_t bits)
Definition: overflow_bitset.h:81
OverflowBitset(OverflowBitset &&)=default
Ext * m_ext
Definition: overflow_bitset.h:136
static MutableOverflowBitset Xor(MEM_ROOT *mem_root, OverflowBitset a, OverflowBitset b)
Definition: overflow_bitset.h:297
void InitOverflow(MEM_ROOT *mem_root, size_t capacity)
Definition: overflow_bitset.cc:31
friend bool IsBitSet(int bit_num, OverflowBitset x)
Definition: overflow_bitset.h:511
void Clear()
Definition: overflow_bitset.h:89
OverflowBitset & operator=(OverflowBitset &&)=default
static MEM_ROOT mem_root
Definition: client_plugin.cc:109
Fido Client Authentication nullptr
Definition: fido_client_plugin.cc:221
This file follows Google coding style, except for the name MEM_ROOT (which is kept for historical rea...
std::atomic< Type > N
Definition: ut0counter.h:224
Definition: varlen_sort.h:183
int PopulationCountOverflow(OverflowBitset x)
Definition: overflow_bitset.cc:137
bool IsSubsetOverflow(OverflowBitset a, OverflowBitset b)
Definition: overflow_bitset.cc:125
bool IsSubset(OverflowBitset a, OverflowBitset b)
Definition: overflow_bitset.h:501
bool Overlaps(OverflowBitset a, OverflowBitset b)
Definition: overflow_bitset.h:471
auto BitsSetInBoth(OverflowBitset bitset_a, OverflowBitset bitset_b)
Definition: overflow_bitset.h:464
int PopulationCount(OverflowBitset x)
Definition: overflow_bitset.h:560
bool OverlapsOverflow(OverflowBitset a, OverflowBitset b)
Definition: overflow_bitset.cc:113
auto BitsSetIn(OverflowBitset bitset)
Definition: overflow_bitset.h:457
bool IsEmpty(OverflowBitset x)
Definition: overflow_bitset.h:543
bool IsBitSet(int bit_num, OverflowBitset x)
Definition: overflow_bitset.h:511
Definition: overflow_bitset.h:461
uint64_t operator()(uint64_t x, uint64_t y) const
Definition: overflow_bitset.h:462
Definition: overflow_bitset.h:454
uint64_t operator()(uint64_t x) const
Definition: overflow_bitset.h:455
The MEM_ROOT is a simple arena, where allocations are carved out of larger blocks.
Definition: my_alloc.h:82
bool Contains(void *ptr) const
Returns whether this MEM_ROOT contains the given pointer, ie., whether it was given back from Alloc(n...
Definition: my_alloc.h:352
Definition: overflow_bitset.h:128
uint64_t m_bits[1]
Definition: overflow_bitset.h:130
size_t m_num_blocks
Definition: overflow_bitset.h:129