MySQL 8.3.0
Source Code Documentation
my_bitmap.h
Go to the documentation of this file.
1/*
2 Copyright (c) 2001, 2023, Oracle and/or its affiliates.
3
4 This program is free software; you can redistribute it and/or modify
5 it under the terms of the GNU General Public License, version 2.0,
6 as published by the Free Software Foundation.
7
8 This program is also distributed with certain software (including
9 but not limited to OpenSSL) that is licensed under separate terms,
10 as designated in a particular file or component or in included license
11 documentation. The authors of MySQL hereby grant you an additional
12 permission to link the program and your derivative works with the
13 separately licensed software that they have included with MySQL.
14
15 This program is distributed in the hope that it will be useful,
16 but WITHOUT ANY WARRANTY; without even the implied warranty of
17 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
18 GNU General Public License, version 2.0, for more details.
19
20 You should have received a copy of the GNU General Public License
21 along with this program; if not, write to the Free Software
22 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA */
23
24#ifndef MY_BITMAP_INCLUDED
25#define MY_BITMAP_INCLUDED
26
27/**
28 @file include/my_bitmap.h
29*/
30
31#define MY_BIT_NONE (~(uint)0)
32
33#include <assert.h>
34#include <limits.h>
35#include <string.h>
36#include <sys/types.h>
37
38#include "my_inttypes.h"
39
41
42struct MY_BITMAP {
44 uint n_bits{0}; /* number of bits occupied by the above */
47};
48
50extern bool bitmap_init(MY_BITMAP *map, my_bitmap_map *buf, uint n_bits);
51extern bool bitmap_is_clear_all(const MY_BITMAP *map);
52extern bool bitmap_is_prefix(const MY_BITMAP *map, uint prefix_size);
53extern bool bitmap_is_set_all(const MY_BITMAP *map);
54extern bool bitmap_is_subset(const MY_BITMAP *map1, const MY_BITMAP *map2);
55extern bool bitmap_is_overlapping(const MY_BITMAP *map1, const MY_BITMAP *map2);
56extern bool bitmap_is_valid(const MY_BITMAP *map);
57extern bool bitmap_test_and_set(MY_BITMAP *map, uint bitmap_bit);
58extern uint bitmap_set_next(MY_BITMAP *map);
59extern uint bitmap_get_first(const MY_BITMAP *map);
60extern uint bitmap_get_first_set(const MY_BITMAP *map);
61extern uint bitmap_get_next_set(const MY_BITMAP *map, uint bitmap_bit);
62extern uint bitmap_bits_set(const MY_BITMAP *map);
63extern void bitmap_free(MY_BITMAP *map);
64extern void bitmap_set_above(MY_BITMAP *map, uint from_byte, bool use_bit);
65extern void bitmap_set_prefix(MY_BITMAP *map, uint prefix_size);
66extern void bitmap_intersect(MY_BITMAP *to, const MY_BITMAP *from);
67extern void bitmap_subtract(MY_BITMAP *map, const MY_BITMAP *map2);
68extern void bitmap_union(MY_BITMAP *map, const MY_BITMAP *map2);
69extern void bitmap_xor(MY_BITMAP *map, const MY_BITMAP *map2);
70extern void bitmap_invert(MY_BITMAP *map);
71extern void bitmap_copy(MY_BITMAP *map, const MY_BITMAP *map2);
72extern uint bitmap_n_copy(MY_BITMAP *dst, const MY_BITMAP *src,
73 uint max_bits_to_copy = UINT_MAX);
74
75#define bitmap_buffer_size(bits) (((bits) + 31) / 32) * 4
76#define no_bytes_in_map(map) (((map)->n_bits + 7) / 8)
77#define no_words_in_map(map) (((map)->n_bits + 31) / 32)
78
79static inline void bitmap_set_bit(MY_BITMAP *map, uint bit) {
80 assert(bit < map->n_bits);
81 ((uchar *)map->bitmap)[bit / 8] |= (1 << (bit & 7));
82}
83
84static inline void bitmap_flip_bit(MY_BITMAP *map, uint bit) {
85 assert(bit < map->n_bits);
86 ((uchar *)map->bitmap)[bit / 8] ^= (1 << (bit & 7));
87}
88
89static inline void bitmap_clear_bit(MY_BITMAP *map, uint bit) {
90 assert(bit < map->n_bits);
91 ((uchar *)map->bitmap)[bit / 8] &= ~(1 << (bit & 7));
92}
93
94static inline bool bitmap_is_set(const MY_BITMAP *map, uint bit) {
95 assert(bit < map->n_bits);
96 return ((uchar *)map->bitmap)[bit / 8] & (1 << (bit & 7));
97}
98
99/**
100 Quite unlike other C comparison functions ending with 'cmp', e.g. memcmp(),
101 strcmp(), this function returns true if the bitmaps are equal, and false
102 otherwise.
103
104 @retval true The bitmaps are equal.
105 @retval false The bitmaps differ.
106 */
107static inline bool bitmap_cmp(const MY_BITMAP *map1, const MY_BITMAP *map2) {
108 assert(map1->n_bits > 0);
109 assert(map2->n_bits > 0);
110
111 if (memcmp(map1->bitmap, map2->bitmap, 4 * (no_words_in_map(map1) - 1)) != 0)
112 return false;
113 return ((*map1->last_word_ptr | map1->last_word_mask) ==
114 (*map2->last_word_ptr | map2->last_word_mask));
115}
116
117/*
118 Clears all bits. This is allowed even for a zero-size bitmap.
119 */
120static inline void bitmap_clear_all(MY_BITMAP *map) {
121 memset(map->bitmap, 0, 4 * no_words_in_map(map));
122}
123
124/*
125 Sets all bits. This is allowed even for a zero-size bitmap.
126 */
127static inline void bitmap_set_all(MY_BITMAP *map) {
128 memset(map->bitmap, 0xFF, 4 * no_words_in_map(map));
129}
130
131#endif // MY_BITMAP_INCLUDED
static bool bitmap_cmp(const MY_BITMAP *map1, const MY_BITMAP *map2)
Quite unlike other C comparison functions ending with 'cmp', e.g.
Definition: my_bitmap.h:107
uint32 my_bitmap_map
Definition: my_bitmap.h:40
bool bitmap_is_overlapping(const MY_BITMAP *map1, const MY_BITMAP *map2)
Definition: my_bitmap.cc:300
void bitmap_xor(MY_BITMAP *map, const MY_BITMAP *map2)
Definition: my_bitmap.cc:397
uint bitmap_n_copy(MY_BITMAP *dst, const MY_BITMAP *src, uint max_bits_to_copy=UINT_MAX)
Copy as many bits as 'dst' can hold from 'src', but no more than max_bits_to_copy bits.
Definition: my_bitmap.cc:518
static void bitmap_set_all(MY_BITMAP *map)
Definition: my_bitmap.h:127
bool bitmap_is_clear_all(const MY_BITMAP *map)
Definition: my_bitmap.cc:267
void bitmap_invert(MY_BITMAP *map)
Definition: my_bitmap.cc:406
static bool bitmap_is_set(const MY_BITMAP *map, uint bit)
Definition: my_bitmap.h:94
static void bitmap_flip_bit(MY_BITMAP *map, uint bit)
Definition: my_bitmap.h:84
bool bitmap_is_set_all(const MY_BITMAP *map)
Definition: my_bitmap.cc:256
static void bitmap_clear_all(MY_BITMAP *map)
Definition: my_bitmap.h:120
void bitmap_subtract(MY_BITMAP *map, const MY_BITMAP *map2)
Definition: my_bitmap.cc:379
uint bitmap_bits_set(const MY_BITMAP *map)
Definition: my_bitmap.cc:415
void bitmap_intersect(MY_BITMAP *to, const MY_BITMAP *from)
Definition: my_bitmap.cc:334
uint bitmap_get_next_set(const MY_BITMAP *map, uint bitmap_bit)
Get the next set bit.
Definition: my_bitmap.cc:461
void bitmap_set_above(MY_BITMAP *map, uint from_byte, bool use_bit)
Definition: my_bitmap.cc:371
bool bitmap_is_valid(const MY_BITMAP *map)
Check if 'map' is valid.
Definition: my_bitmap.cc:323
uint bitmap_get_first_set(const MY_BITMAP *map)
Definition: my_bitmap.cc:438
bool bitmap_init(MY_BITMAP *map, my_bitmap_map *buf, uint n_bits)
Definition: my_bitmap.cc:139
void bitmap_union(MY_BITMAP *map, const MY_BITMAP *map2)
Definition: my_bitmap.cc:388
static void bitmap_clear_bit(MY_BITMAP *map, uint bit)
Definition: my_bitmap.h:89
bool bitmap_test_and_set(MY_BITMAP *map, uint bitmap_bit)
Definition: my_bitmap.cc:178
#define no_words_in_map(map)
Definition: my_bitmap.h:77
void bitmap_set_prefix(MY_BITMAP *map, uint prefix_size)
Set the specified number of bits in the bitmap buffer.
Definition: my_bitmap.cc:200
void create_last_word_mask(MY_BITMAP *map)
Definition: my_bitmap.cc:63
bool bitmap_is_subset(const MY_BITMAP *map1, const MY_BITMAP *map2)
Definition: my_bitmap.cc:280
void bitmap_free(MY_BITMAP *map)
Definition: my_bitmap.cc:157
uint bitmap_set_next(MY_BITMAP *map)
Definition: my_bitmap.cc:186
static void bitmap_set_bit(MY_BITMAP *map, uint bit)
Definition: my_bitmap.h:79
uint bitmap_get_first(const MY_BITMAP *map)
Definition: my_bitmap.cc:493
void bitmap_copy(MY_BITMAP *map, const MY_BITMAP *map2)
Definition: my_bitmap.cc:429
bool bitmap_is_prefix(const MY_BITMAP *map, uint prefix_size)
Definition: my_bitmap.cc:217
Some integer typedefs for easier portability.
unsigned char uchar
Definition: my_inttypes.h:51
uint32_t uint32
Definition: my_inttypes.h:66
Definition: buf0block_hint.cc:29
std::map< Key, Value, Compare, ut::allocator< std::pair< const Key, Value > > > map
Specialization of map which uses ut_allocator.
Definition: ut0new.h:2891
Definition: my_bitmap.h:42
my_bitmap_map * bitmap
Definition: my_bitmap.h:43
uint n_bits
Definition: my_bitmap.h:44
my_bitmap_map last_word_mask
Definition: my_bitmap.h:45
my_bitmap_map * last_word_ptr
Definition: my_bitmap.h:46