MySQL 9.1.0
Source Code Documentation
my_bitmap.h
Go to the documentation of this file.
1/*
2 Copyright (c) 2001, 2024, 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 designed to work 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 either included with
14 the program or referenced in the documentation.
15
16 This program is distributed in the hope that it will be useful,
17 but WITHOUT ANY WARRANTY; without even the implied warranty of
18 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
19 GNU General Public License, version 2.0, for more details.
20
21 You should have received a copy of the GNU General Public License
22 along with this program; if not, write to the Free Software
23 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA */
24
25#ifndef MY_BITMAP_INCLUDED
26#define MY_BITMAP_INCLUDED
27
28/**
29 @file include/my_bitmap.h
30*/
31
32#define MY_BIT_NONE (~(uint)0)
33
34#include <assert.h>
35#include <limits.h>
36#include <string.h>
37#include <sys/types.h>
38
39#include "my_inttypes.h"
40
42
43struct MY_BITMAP {
45 uint n_bits{0}; /* number of bits occupied by the above */
48};
49
51extern bool bitmap_init(MY_BITMAP *map, my_bitmap_map *buf, uint n_bits);
52extern bool bitmap_is_clear_all(const MY_BITMAP *map);
53extern bool bitmap_is_prefix(const MY_BITMAP *map, uint prefix_size);
54extern bool bitmap_is_set_all(const MY_BITMAP *map);
55extern bool bitmap_is_subset(const MY_BITMAP *map1, const MY_BITMAP *map2);
56extern bool bitmap_is_overlapping(const MY_BITMAP *map1, const MY_BITMAP *map2);
57extern bool bitmap_is_valid(const MY_BITMAP *map);
58extern bool bitmap_test_and_set(MY_BITMAP *map, uint bitmap_bit);
59extern uint bitmap_set_next(MY_BITMAP *map);
60extern uint bitmap_get_first(const MY_BITMAP *map);
61extern uint bitmap_get_first_set(const MY_BITMAP *map);
62extern uint bitmap_get_next_set(const MY_BITMAP *map, uint bitmap_bit);
63extern uint bitmap_bits_set(const MY_BITMAP *map);
64extern void bitmap_free(MY_BITMAP *map);
65extern void bitmap_set_above(MY_BITMAP *map, uint from_byte, bool use_bit);
66extern void bitmap_set_prefix(MY_BITMAP *map, uint prefix_size);
67extern void bitmap_intersect(MY_BITMAP *to, const MY_BITMAP *from);
68extern void bitmap_subtract(MY_BITMAP *map, const MY_BITMAP *map2);
69extern void bitmap_union(MY_BITMAP *map, const MY_BITMAP *map2);
70extern void bitmap_xor(MY_BITMAP *map, const MY_BITMAP *map2);
71extern void bitmap_invert(MY_BITMAP *map);
72extern void bitmap_copy(MY_BITMAP *map, const MY_BITMAP *map2);
73extern uint bitmap_n_copy(MY_BITMAP *dst, const MY_BITMAP *src,
74 uint max_bits_to_copy = UINT_MAX);
75
76#define bitmap_buffer_size(bits) (((bits) + 31) / 32) * 4
77#define no_bytes_in_map(map) (((map)->n_bits + 7) / 8)
78#define no_words_in_map(map) (((map)->n_bits + 31) / 32)
79
80static inline void bitmap_set_bit(MY_BITMAP *map, uint bit) {
81 assert(bit < map->n_bits);
82 ((uchar *)map->bitmap)[bit / 8] |= (1 << (bit & 7));
83}
84
85static inline void bitmap_flip_bit(MY_BITMAP *map, uint bit) {
86 assert(bit < map->n_bits);
87 ((uchar *)map->bitmap)[bit / 8] ^= (1 << (bit & 7));
88}
89
90static inline void bitmap_clear_bit(MY_BITMAP *map, uint bit) {
91 assert(bit < map->n_bits);
92 ((uchar *)map->bitmap)[bit / 8] &= ~(1 << (bit & 7));
93}
94
95static inline bool bitmap_is_set(const MY_BITMAP *map, uint bit) {
96 assert(bit < map->n_bits);
97 return ((uchar *)map->bitmap)[bit / 8] & (1 << (bit & 7));
98}
99
100/**
101 Quite unlike other C comparison functions ending with 'cmp', e.g. memcmp(),
102 strcmp(), this function returns true if the bitmaps are equal, and false
103 otherwise.
104
105 @retval true The bitmaps are equal.
106 @retval false The bitmaps differ.
107 */
108static inline bool bitmap_cmp(const MY_BITMAP *map1, const MY_BITMAP *map2) {
109 assert(map1->n_bits > 0);
110 assert(map2->n_bits > 0);
111
112 if (memcmp(map1->bitmap, map2->bitmap, 4 * (no_words_in_map(map1) - 1)) != 0)
113 return false;
114 return ((*map1->last_word_ptr | map1->last_word_mask) ==
115 (*map2->last_word_ptr | map2->last_word_mask));
116}
117
118/*
119 Clears all bits. This is allowed even for a zero-size bitmap.
120 */
121static inline void bitmap_clear_all(MY_BITMAP *map) {
122 memset(map->bitmap, 0, 4 * no_words_in_map(map));
123}
124
125/*
126 Sets all bits. This is allowed even for a zero-size bitmap.
127 */
128static inline void bitmap_set_all(MY_BITMAP *map) {
129 memset(map->bitmap, 0xFF, 4 * no_words_in_map(map));
130}
131
132#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:108
uint32 my_bitmap_map
Definition: my_bitmap.h:41
bool bitmap_is_overlapping(const MY_BITMAP *map1, const MY_BITMAP *map2)
Definition: my_bitmap.cc:301
void bitmap_xor(MY_BITMAP *map, const MY_BITMAP *map2)
Definition: my_bitmap.cc:398
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:519
static void bitmap_set_all(MY_BITMAP *map)
Definition: my_bitmap.h:128
bool bitmap_is_clear_all(const MY_BITMAP *map)
Definition: my_bitmap.cc:268
void bitmap_invert(MY_BITMAP *map)
Definition: my_bitmap.cc:407
static bool bitmap_is_set(const MY_BITMAP *map, uint bit)
Definition: my_bitmap.h:95
static void bitmap_flip_bit(MY_BITMAP *map, uint bit)
Definition: my_bitmap.h:85
bool bitmap_is_set_all(const MY_BITMAP *map)
Definition: my_bitmap.cc:257
static void bitmap_clear_all(MY_BITMAP *map)
Definition: my_bitmap.h:121
void bitmap_subtract(MY_BITMAP *map, const MY_BITMAP *map2)
Definition: my_bitmap.cc:380
uint bitmap_bits_set(const MY_BITMAP *map)
Definition: my_bitmap.cc:416
void bitmap_intersect(MY_BITMAP *to, const MY_BITMAP *from)
Definition: my_bitmap.cc:335
uint bitmap_get_next_set(const MY_BITMAP *map, uint bitmap_bit)
Get the next set bit.
Definition: my_bitmap.cc:462
void bitmap_set_above(MY_BITMAP *map, uint from_byte, bool use_bit)
Definition: my_bitmap.cc:372
bool bitmap_is_valid(const MY_BITMAP *map)
Check if 'map' is valid.
Definition: my_bitmap.cc:324
uint bitmap_get_first_set(const MY_BITMAP *map)
Definition: my_bitmap.cc:439
bool bitmap_init(MY_BITMAP *map, my_bitmap_map *buf, uint n_bits)
Definition: my_bitmap.cc:140
void bitmap_union(MY_BITMAP *map, const MY_BITMAP *map2)
Definition: my_bitmap.cc:389
static void bitmap_clear_bit(MY_BITMAP *map, uint bit)
Definition: my_bitmap.h:90
bool bitmap_test_and_set(MY_BITMAP *map, uint bitmap_bit)
Definition: my_bitmap.cc:179
#define no_words_in_map(map)
Definition: my_bitmap.h:78
void bitmap_set_prefix(MY_BITMAP *map, uint prefix_size)
Set the specified number of bits in the bitmap buffer.
Definition: my_bitmap.cc:201
void create_last_word_mask(MY_BITMAP *map)
Definition: my_bitmap.cc:64
bool bitmap_is_subset(const MY_BITMAP *map1, const MY_BITMAP *map2)
Definition: my_bitmap.cc:281
void bitmap_free(MY_BITMAP *map)
Definition: my_bitmap.cc:158
uint bitmap_set_next(MY_BITMAP *map)
Definition: my_bitmap.cc:187
static void bitmap_set_bit(MY_BITMAP *map, uint bit)
Definition: my_bitmap.h:80
uint bitmap_get_first(const MY_BITMAP *map)
Definition: my_bitmap.cc:494
void bitmap_copy(MY_BITMAP *map, const MY_BITMAP *map2)
Definition: my_bitmap.cc:430
bool bitmap_is_prefix(const MY_BITMAP *map, uint prefix_size)
Definition: my_bitmap.cc:218
Some integer typedefs for easier portability.
unsigned char uchar
Definition: my_inttypes.h:52
uint32_t uint32
Definition: my_inttypes.h:67
Definition: buf0block_hint.cc:30
std::map< Key, Value, Compare, ut::allocator< std::pair< const Key, Value > > > map
Specialization of map which uses ut_allocator.
Definition: ut0new.h:2894
Definition: my_bitmap.h:43
my_bitmap_map * bitmap
Definition: my_bitmap.h:44
uint n_bits
Definition: my_bitmap.h:45
my_bitmap_map last_word_mask
Definition: my_bitmap.h:46
my_bitmap_map * last_word_ptr
Definition: my_bitmap.h:47