MySQL 8.0.29
Source Code Documentation
overflow_bitset.h
Go to the documentation of this file.
1/* Copyright (c) 2021, 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 uintptr_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 void SetBitOverflow(int bit_num);
239 void ClearBitsOverflow(int begin_bit_num, int end_bit_num);
240
241 friend class OverflowBitset;
242};
243
245 m_bits = other.m_bits;
246 other.m_bits = 1;
247}
248
250 MutableOverflowBitset &&other) {
251 m_bits = other.m_bits;
252 other.m_bits = 1;
253 return *this;
254}
255
258 if (is_inline()) {
259 ret.m_bits = m_bits;
260 } else {
261 memcpy(ret.m_ext, m_ext,
262 sizeof(m_ext->m_num_blocks) +
263 m_ext->m_num_blocks * sizeof(m_ext->m_bits));
264 }
265 return ret;
266}
267
270 OverflowBitset b) {
271 assert(a.is_inline() == b.is_inline());
272 assert(a.capacity() == b.capacity());
273 if (a.is_inline()) {
275 ret.m_bits = a.m_bits | b.m_bits;
276 return ret;
277 } else {
278 return OrOverflow(mem_root, a, b);
279 }
280}
281
284 OverflowBitset b) {
285 assert(a.is_inline() == b.is_inline());
286 assert(a.capacity() == b.capacity());
287 if (a.is_inline()) {
289 ret.m_bits = a.m_bits & b.m_bits;
290 return ret;
291 } else {
292 return AndOverflow(mem_root, a, b);
293 }
294}
295
298 OverflowBitset b) {
299 assert(a.is_inline() == b.is_inline());
300 assert(a.capacity() == b.capacity());
301 if (a.is_inline()) {
303 ret.m_bits = (a.m_bits ^ b.m_bits) | 1;
304 return ret;
305 } else {
306 return XorOverflow(mem_root, a, b);
307 }
308}
309
310// Definitions overloading utility functions in bit_utils.h, making it generally
311// possible to use OverflowBitset as we use regular uint64_t bitsets
312// (e.g. NodeMap).
313//
314// Since one cannot easily combine non-inline OverflowBitsets without allocating
315// memory, the BitsSetIn() overload supports combining state as-we-go.
316// For instance, where you would normally write (for uint64_t)
317//
318// for (int bit_idx : BitsSetIn(x & y))
319//
320// you would use this variation for OverflowBitsets:
321//
322// for (int bit_idx : BitsSetInBoth(x, y))
323//
324// Under the hood, BitsSetInBoth() calls a Combine functor that ANDs the two
325// uint64_t bitwise (for inline bitsets only once, but for overflow bitsets
326// multiple times, on-demand as we iterate), which can potentially save
327// on a lot of bitscan operations and loop iterations versus trying to test
328// one-by-one. This can be extended to any number of arguments.
329//
330// Combine::operator() must be const, Combine must be movable (but can have
331// state).
332
333template <size_t N, class Combine>
335 public:
336 class iterator {
337 private:
338 const Combine *m_combine;
339 uint64_t m_state;
340
341 // m_next holds, for each bitset array, the pointer to the next
342 // uint64_t to be processed/read (once m_state is zero, ie.,
343 // there are no more bits in the current state). When m_next[0] == m_end,
344 // iteration is over. For inline bitsets, m_next[0] == m_end == nullptr,
345 // so once the first 64-bit group is processed, we are done.
346 // (We assume all arrays have the same length, so we only need one
347 // end pointer.)
348 std::array<const uint64_t *, N> m_next;
349 const uint64_t *const m_end;
351
352 public:
353 // For inline bitsets.
354 iterator(uint64_t state, const Combine *combine)
355 : m_combine(combine), m_state(state), m_end(nullptr), m_base(0) {
356 m_next[0] = nullptr;
357 }
358
359 // For overflow bitsets.
360 iterator(const std::array<const uint64_t *, N> begin, const uint64_t *end,
361 const Combine *combine)
362 : m_combine(combine),
363 m_state(0),
364 m_next(begin),
365 m_end(end),
366 m_base(-64) {
367 while (m_state == 0 && m_next[0] != m_end) {
369 for (size_t i = 0; i < N; ++i) {
370 ++m_next[i];
371 }
372 m_base += 64;
373 }
374 }
375
376 bool operator==(const iterator &other) const {
377 assert(m_end == other.m_end);
378 return m_state == other.m_state && m_next[0] == other.m_next[0];
379 }
380 bool operator!=(const iterator &other) const {
381 assert(m_end == other.m_end);
382 return m_state != other.m_state || m_next[0] != other.m_next[0];
383 }
384 size_t operator*() const { return FindLowestBitSet(m_state) + m_base; }
386 // Clear the lowest set bit.
387 assert(m_state != 0);
388 m_state = m_state & (m_state - 1);
389
390 while (m_state == 0 && m_next[0] != m_end) {
392 for (size_t i = 0; i < N; ++i) {
393 ++m_next[i];
394 }
395 m_base += 64;
396 }
397 return *this;
398 }
399 };
400
401 OverflowBitsetBitsIn(std::array<OverflowBitset, N> bitsets, Combine combine)
402 : m_bitsets(bitsets), m_combine(std::move(combine)) {}
403
404 iterator begin() const {
405 if (m_bitsets[0].is_inline()) {
406 std::array<uint64_t, N> bits;
407 for (size_t i = 0; i < N; ++i) {
408 assert(m_bitsets[i].is_inline());
409 bits[i] = m_bitsets[i].m_bits;
410 }
411 uint64_t state = std::apply(m_combine, bits);
412 return iterator{state >> 1, &m_combine};
413 } else {
414 std::array<const uint64_t *, N> ptrs;
415 for (size_t i = 0; i < N; ++i) {
416 assert(!m_bitsets[i].is_inline());
417 assert(m_bitsets[i].capacity() == m_bitsets[0].capacity());
418 ptrs[i] = m_bitsets[i].m_ext->m_bits;
419 }
420 const uint64_t *end =
421 m_bitsets[0].m_ext->m_bits + m_bitsets[0].m_ext->m_num_blocks;
422 return iterator{ptrs, end, &m_combine};
423 }
424 }
425 iterator end() const {
426 if (m_bitsets[0].is_inline()) {
427 return iterator{0, &m_combine};
428 } else {
429 std::array<const uint64_t *, N> ptrs;
430 for (size_t i = 0; i < N; ++i) {
431 assert(m_bitsets[i].is_inline() == m_bitsets[0].is_inline());
432 assert(m_bitsets[i].capacity() == m_bitsets[0].capacity());
433 ptrs[i] = m_bitsets[i].m_ext->m_bits + m_bitsets[i].m_ext->m_num_blocks;
434 }
435 return iterator{ptrs, ptrs[0], &m_combine};
436 }
437 }
438
439 private:
440 static inline uint64_t ReadAndCombine(
441 const std::array<const uint64_t *, N> &ptrs, const Combine *combine) {
442 std::array<uint64_t, N> bits;
443 for (size_t i = 0; i < N; ++i) {
444 bits[i] = *ptrs[i];
445 }
446 return std::apply(*combine, bits);
447 }
448
449 const std::array<OverflowBitset, N> m_bitsets;
450 const Combine m_combine;
451};
452
454 uint64_t operator()(uint64_t x) const { return x; }
455};
456inline auto BitsSetIn(OverflowBitset bitset) {
458}
459
461 uint64_t operator()(uint64_t x, uint64_t y) const { return x & y; }
462};
463inline auto BitsSetInBoth(OverflowBitset bitset_a, OverflowBitset bitset_b) {
464 return OverflowBitsetBitsIn<2, AndCombine>{{bitset_a, bitset_b},
465 AndCombine()};
466}
467
469
471 if (a.m_bits == 1 || b.m_bits == 1) {
472 // Empty and inline, so nothing overlaps.
473 // This is a special case that does not require the two
474 // sets to be of the same size (see file comment).
475 return false;
476 }
477 assert(a.is_inline() == b.is_inline());
478 assert(a.capacity() == b.capacity());
479 if (a.is_inline()) {
480 return (a.m_bits & b.m_bits) != 1;
481 } else {
482 return OverlapsOverflow(a, b);
483 }
484}
485
487 return Overlaps(a, static_cast<const OverflowBitset &>(b));
488}
489
490inline bool Overlaps(const MutableOverflowBitset &a,
491 const MutableOverflowBitset &b) {
492 return Overlaps(static_cast<const OverflowBitset &>(a),
493 static_cast<const OverflowBitset &>(b));
494}
495
497 return Overlaps(static_cast<const OverflowBitset &>(a), b);
498}
499
501 assert(a.is_inline() == b.is_inline());
502 assert(a.capacity() == b.capacity());
503 if (a.is_inline()) {
504 return IsSubset(a.m_bits, b.m_bits);
505 } else {
506 return IsSubsetOverflow(a, b);
507 }
508}
509
510inline bool IsBitSet(int bit_num, OverflowBitset x) {
511 assert(bit_num >= 0);
512 assert(static_cast<size_t>(bit_num) < x.capacity());
513 const unsigned bn = bit_num; // To avoid sign extension taking time.
514 if (x.is_inline()) {
515 return Overlaps(x.m_bits, uint64_t{1} << (bn + 1));
516 } else {
517 return Overlaps(x.m_ext->m_bits[bn / 64], uint64_t{1} << (bn % 64));
518 }
519}
520
521inline bool IsBitSet(int bit_num, const MutableOverflowBitset &x) {
522 return IsBitSet(bit_num, static_cast<const OverflowBitset &>(x));
523}
524
526 return IsSubset(a, static_cast<const OverflowBitset &>(b));
527}
528
529inline bool IsSubset(const MutableOverflowBitset &a,
530 const MutableOverflowBitset &b) {
531 return IsSubset(static_cast<const OverflowBitset &>(a),
532 static_cast<const OverflowBitset &>(b));
533}
534
536 return IsSubset(static_cast<const OverflowBitset &>(a), b);
537}
538
539// This is mostly used to guard a few asserts, so it's better that it's
540// completely visible, so that the compiler can remove it totally
541// in optimized mode.
542inline bool IsEmpty(OverflowBitset x) {
543 if (x.is_inline()) {
544 return x.m_bits == 1;
545 } else {
546 for (unsigned i = 0; i < x.m_ext->m_num_blocks; ++i) {
547 if (x.m_ext->m_bits[i] != 0) {
548 return false;
549 }
550 }
551 return true;
552 }
553}
554
555inline bool IsEmpty(const MutableOverflowBitset &x) {
556 return IsEmpty(static_cast<const OverflowBitset &>(x));
557}
558
560 if (x.is_inline()) {
561 return PopulationCount(x.m_bits) - 1;
562 } else {
563 return PopulationCountOverflow(x);
564 }
565}
566
567#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 bool IsBitSet(int bit_num, const MutableOverflowBitset &x)
Definition: overflow_bitset.h:521
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:525
MutableOverflowBitset & operator=(const MutableOverflowBitset &)=delete
friend bool Overlaps(OverflowBitset a, const MutableOverflowBitset &b)
Definition: overflow_bitset.h:486
MutableOverflowBitset(MEM_ROOT *mem_root, size_t capacity)
Definition: overflow_bitset.h:171
friend class OverflowBitset
Definition: overflow_bitset.h:241
friend bool IsEmpty(const MutableOverflowBitset &x)
Definition: overflow_bitset.h:555
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:336
const Combine * m_combine
Definition: overflow_bitset.h:338
bool operator==(const iterator &other) const
Definition: overflow_bitset.h:376
iterator(uint64_t state, const Combine *combine)
Definition: overflow_bitset.h:354
size_t operator*() const
Definition: overflow_bitset.h:384
iterator(const std::array< const uint64_t *, N > begin, const uint64_t *end, const Combine *combine)
Definition: overflow_bitset.h:360
bool operator!=(const iterator &other) const
Definition: overflow_bitset.h:380
std::array< const uint64_t *, N > m_next
Definition: overflow_bitset.h:348
const uint64_t *const m_end
Definition: overflow_bitset.h:349
int m_base
Definition: overflow_bitset.h:350
iterator & operator++()
Definition: overflow_bitset.h:385
uint64_t m_state
Definition: overflow_bitset.h:339
Definition: overflow_bitset.h:334
iterator end() const
Definition: overflow_bitset.h:425
static uint64_t ReadAndCombine(const std::array< const uint64_t *, N > &ptrs, const Combine *combine)
Definition: overflow_bitset.h:440
iterator begin() const
Definition: overflow_bitset.h:404
const std::array< OverflowBitset, N > m_bitsets
Definition: overflow_bitset.h:449
const Combine m_combine
Definition: overflow_bitset.h:450
OverflowBitsetBitsIn(std::array< OverflowBitset, N > bitsets, Combine combine)
Definition: overflow_bitset.h:401
Definition: overflow_bitset.h:76
friend bool IsSubset(OverflowBitset a, OverflowBitset b)
Definition: overflow_bitset.h:500
uintptr_t m_bits
Definition: overflow_bitset.h:135
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:268
friend int PopulationCountOverflow(OverflowBitset x)
Definition: overflow_bitset.cc:137
friend bool Overlaps(OverflowBitset a, OverflowBitset b)
Definition: overflow_bitset.h:470
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:559
MutableOverflowBitset Clone(MEM_ROOT *mem_root) const
Definition: overflow_bitset.h:256
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
OverflowBitset(const OverflowBitset &)=default
friend bool IsBitSetOverflow(int bit_num, OverflowBitset x)
friend bool IsEmpty(OverflowBitset x)
Definition: overflow_bitset.h:542
static MutableOverflowBitset And(MEM_ROOT *mem_root, OverflowBitset a, OverflowBitset b)
Definition: overflow_bitset.h:282
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:296
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:510
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:500
bool Overlaps(OverflowBitset a, OverflowBitset b)
Definition: overflow_bitset.h:470
auto BitsSetInBoth(OverflowBitset bitset_a, OverflowBitset bitset_b)
Definition: overflow_bitset.h:463
int PopulationCount(OverflowBitset x)
Definition: overflow_bitset.h:559
bool OverlapsOverflow(OverflowBitset a, OverflowBitset b)
Definition: overflow_bitset.cc:113
auto BitsSetIn(OverflowBitset bitset)
Definition: overflow_bitset.h:456
bool IsEmpty(OverflowBitset x)
Definition: overflow_bitset.h:542
bool IsBitSet(int bit_num, OverflowBitset x)
Definition: overflow_bitset.h:510
Definition: overflow_bitset.h:460
uint64_t operator()(uint64_t x, uint64_t y) const
Definition: overflow_bitset.h:461
Definition: overflow_bitset.h:453
uint64_t operator()(uint64_t x) const
Definition: overflow_bitset.h:454
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