MySQL 8.2.0
Source Code Documentation
overflow_bitset.h
Go to the documentation of this file.
1/* Copyright (c) 2021, 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_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 using iterator_category = std::forward_iterator_tag;
355 using difference_type = size_t;
356 using value_type = size_t;
359
360 // For inline bitsets.
361 iterator(uint64_t state, const Combine *combine)
362 : m_combine(combine), m_state(state), m_end(nullptr), m_base(0) {
363 m_next[0] = nullptr;
364 }
365
366 // For overflow bitsets.
367 iterator(const std::array<const uint64_t *, N> begin, const uint64_t *end,
368 const Combine *combine)
369 : m_combine(combine),
370 m_state(0),
371 m_next(begin),
372 m_end(end),
373 m_base(-64) {
374 while (m_state == 0 && m_next[0] != m_end) {
376 for (size_t i = 0; i < N; ++i) {
377 ++m_next[i];
378 }
379 m_base += 64;
380 }
381 }
382
383 bool operator==(const iterator &other) const {
384 assert(m_end == other.m_end);
385 return m_state == other.m_state && m_next[0] == other.m_next[0];
386 }
387 bool operator!=(const iterator &other) const {
388 assert(m_end == other.m_end);
389 return m_state != other.m_state || m_next[0] != other.m_next[0];
390 }
391 size_t operator*() const { return FindLowestBitSet(m_state) + m_base; }
393 // Clear the lowest set bit.
394 assert(m_state != 0);
395 m_state = m_state & (m_state - 1);
396
397 while (m_state == 0 && m_next[0] != m_end) {
399 for (size_t i = 0; i < N; ++i) {
400 ++m_next[i];
401 }
402 m_base += 64;
403 }
404 return *this;
405 }
406 };
407
408 OverflowBitsetBitsIn(std::array<OverflowBitset, N> bitsets, Combine combine)
409 : m_bitsets(bitsets), m_combine(std::move(combine)) {}
410
411 iterator begin() const {
412 if (m_bitsets[0].is_inline()) {
413 std::array<uint64_t, N> bits;
414 for (size_t i = 0; i < N; ++i) {
415 assert(m_bitsets[i].is_inline());
416 bits[i] = m_bitsets[i].m_bits;
417 }
418 uint64_t state = std::apply(m_combine, bits);
419 return iterator{state >> 1, &m_combine};
420 } else {
421 std::array<const uint64_t *, N> ptrs;
422 for (size_t i = 0; i < N; ++i) {
423 assert(!m_bitsets[i].is_inline());
424 assert(m_bitsets[i].capacity() == m_bitsets[0].capacity());
425 ptrs[i] = m_bitsets[i].m_ext->m_bits;
426 }
427 const uint64_t *end =
428 m_bitsets[0].m_ext->m_bits + m_bitsets[0].m_ext->m_num_blocks;
429 return iterator{ptrs, end, &m_combine};
430 }
431 }
432 iterator end() const {
433 if (m_bitsets[0].is_inline()) {
434 return iterator{0, &m_combine};
435 } else {
436 std::array<const uint64_t *, N> ptrs;
437 for (size_t i = 0; i < N; ++i) {
438 assert(m_bitsets[i].is_inline() == m_bitsets[0].is_inline());
439 assert(m_bitsets[i].capacity() == m_bitsets[0].capacity());
440 ptrs[i] = m_bitsets[i].m_ext->m_bits + m_bitsets[i].m_ext->m_num_blocks;
441 }
442 return iterator{ptrs, ptrs[0], &m_combine};
443 }
444 }
445
446 private:
447 static inline uint64_t ReadAndCombine(
448 const std::array<const uint64_t *, N> &ptrs, const Combine *combine) {
449 std::array<uint64_t, N> bits;
450 for (size_t i = 0; i < N; ++i) {
451 bits[i] = *ptrs[i];
452 }
453 return std::apply(*combine, bits);
454 }
455
456 const std::array<OverflowBitset, N> m_bitsets;
457 const Combine m_combine;
458};
459
461 uint64_t operator()(uint64_t x) const { return x; }
462};
463inline auto BitsSetIn(OverflowBitset bitset) {
465}
466
468 uint64_t operator()(uint64_t x, uint64_t y) const { return x & y; }
469};
470inline auto BitsSetInBoth(OverflowBitset bitset_a, OverflowBitset bitset_b) {
471 return OverflowBitsetBitsIn<2, AndCombine>{{bitset_a, bitset_b},
472 AndCombine()};
473}
474
476
478 if (a.m_bits == 1 || b.m_bits == 1) {
479 // Empty and inline, so nothing overlaps.
480 // This is a special case that does not require the two
481 // sets to be of the same size (see file comment).
482 return false;
483 }
484 assert(a.is_inline() == b.is_inline());
485 assert(a.capacity() == b.capacity());
486 if (a.is_inline()) {
487 return (a.m_bits & b.m_bits) != 1;
488 } else {
489 return OverlapsOverflow(a, b);
490 }
491}
492
494 return Overlaps(a, static_cast<const OverflowBitset &>(b));
495}
496
497inline bool Overlaps(const MutableOverflowBitset &a,
498 const MutableOverflowBitset &b) {
499 return Overlaps(static_cast<const OverflowBitset &>(a),
500 static_cast<const OverflowBitset &>(b));
501}
502
504 return Overlaps(static_cast<const OverflowBitset &>(a), b);
505}
506
508 assert(a.is_inline() == b.is_inline());
509 assert(a.capacity() == b.capacity());
510 if (a.is_inline()) {
511 return IsSubset(a.m_bits, b.m_bits);
512 } else {
513 return IsSubsetOverflow(a, b);
514 }
515}
516
517inline bool IsBitSet(int bit_num, OverflowBitset x) {
518 assert(bit_num >= 0);
519 assert(static_cast<size_t>(bit_num) < x.capacity());
520 const unsigned bn = bit_num; // To avoid sign extension taking time.
521 if (x.is_inline()) {
522 return Overlaps(x.m_bits, uint64_t{1} << (bn + 1));
523 } else {
524 return Overlaps(x.m_ext->m_bits[bn / 64], uint64_t{1} << (bn % 64));
525 }
526}
527
528inline bool IsBitSet(int bit_num, const MutableOverflowBitset &x) {
529 return IsBitSet(bit_num, static_cast<const OverflowBitset &>(x));
530}
531
533 return IsSubset(a, static_cast<const OverflowBitset &>(b));
534}
535
536inline bool IsSubset(const MutableOverflowBitset &a,
537 const MutableOverflowBitset &b) {
538 return IsSubset(static_cast<const OverflowBitset &>(a),
539 static_cast<const OverflowBitset &>(b));
540}
541
543 return IsSubset(static_cast<const OverflowBitset &>(a), b);
544}
545
546// This is mostly used to guard a few asserts, so it's better that it's
547// completely visible, so that the compiler can remove it totally
548// in optimized mode.
549inline bool IsEmpty(OverflowBitset x) {
550 if (x.is_inline()) {
551 return x.m_bits == 1;
552 } else {
553 for (unsigned i = 0; i < x.m_ext->m_num_blocks; ++i) {
554 if (x.m_ext->m_bits[i] != 0) {
555 return false;
556 }
557 }
558 return true;
559 }
560}
561
562inline bool IsEmpty(const MutableOverflowBitset &x) {
563 return IsEmpty(static_cast<const OverflowBitset &>(x));
564}
565
567 if (x.is_inline()) {
568 return PopulationCount(x.m_bits) - 1;
569 } else {
570 return PopulationCountOverflow(x);
571 }
572}
573
574/// Find the nuber of bits set in 'x'.
576 return PopulationCount(static_cast<const OverflowBitset &>(x));
577}
578
579#endif // SQL_JOIN_OPTIMIZER_OVERFLOW_BITSET_H
Kerberos Client Authentication nullptr
Definition: auth_kerberos_client_plugin.cc:250
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:575
friend bool IsBitSet(int bit_num, const MutableOverflowBitset &x)
Definition: overflow_bitset.h:528
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:532
MutableOverflowBitset & operator=(const MutableOverflowBitset &)=delete
friend bool Overlaps(OverflowBitset a, const MutableOverflowBitset &b)
Definition: overflow_bitset.h:493
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:562
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:383
value_type * pointer
Definition: overflow_bitset.h:357
iterator(uint64_t state, const Combine *combine)
Definition: overflow_bitset.h:361
value_type & reference
Definition: overflow_bitset.h:358
size_t operator*() const
Definition: overflow_bitset.h:391
size_t difference_type
Definition: overflow_bitset.h:355
iterator(const std::array< const uint64_t *, N > begin, const uint64_t *end, const Combine *combine)
Definition: overflow_bitset.h:367
size_t value_type
Definition: overflow_bitset.h:356
bool operator!=(const iterator &other) const
Definition: overflow_bitset.h:387
std::array< const uint64_t *, N > m_next
Definition: overflow_bitset.h:349
const uint64_t *const m_end
Definition: overflow_bitset.h:350
std::forward_iterator_tag iterator_category
Definition: overflow_bitset.h:354
int m_base
Definition: overflow_bitset.h:351
iterator & operator++()
Definition: overflow_bitset.h:392
uint64_t m_state
Definition: overflow_bitset.h:340
Definition: overflow_bitset.h:335
iterator end() const
Definition: overflow_bitset.h:432
static uint64_t ReadAndCombine(const std::array< const uint64_t *, N > &ptrs, const Combine *combine)
Definition: overflow_bitset.h:447
iterator begin() const
Definition: overflow_bitset.h:411
const std::array< OverflowBitset, N > m_bitsets
Definition: overflow_bitset.h:456
const Combine m_combine
Definition: overflow_bitset.h:457
OverflowBitsetBitsIn(std::array< OverflowBitset, N > bitsets, Combine combine)
Definition: overflow_bitset.h:408
Definition: overflow_bitset.h:76
friend bool IsSubset(OverflowBitset a, OverflowBitset b)
Definition: overflow_bitset.h:507
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:477
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:566
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:549
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:517
void Clear()
Definition: overflow_bitset.h:89
OverflowBitset & operator=(OverflowBitset &&)=default
static MEM_ROOT mem_root
Definition: client_plugin.cc:113
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:507
bool Overlaps(OverflowBitset a, OverflowBitset b)
Definition: overflow_bitset.h:477
auto BitsSetInBoth(OverflowBitset bitset_a, OverflowBitset bitset_b)
Definition: overflow_bitset.h:470
int PopulationCount(OverflowBitset x)
Definition: overflow_bitset.h:566
bool OverlapsOverflow(OverflowBitset a, OverflowBitset b)
Definition: overflow_bitset.cc:113
auto BitsSetIn(OverflowBitset bitset)
Definition: overflow_bitset.h:463
bool IsEmpty(OverflowBitset x)
Definition: overflow_bitset.h:549
bool IsBitSet(int bit_num, OverflowBitset x)
Definition: overflow_bitset.h:517
Definition: overflow_bitset.h:467
uint64_t operator()(uint64_t x, uint64_t y) const
Definition: overflow_bitset.h:468
Definition: overflow_bitset.h:460
uint64_t operator()(uint64_t x) const
Definition: overflow_bitset.h:461
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