MySQL  8.0.26
Source Code Documentation
my_bitmap.h
Go to the documentation of this file.
1 /*
2  Copyright (c) 2001, 2021, 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 <string.h>
35 #include <sys/types.h>
36 
37 #include "my_inttypes.h"
38 
40 
41 struct MY_BITMAP {
42  my_bitmap_map *bitmap{nullptr};
43  uint n_bits{0}; /* number of bits occupied by the above */
46 };
47 
48 extern void create_last_word_mask(MY_BITMAP *map);
49 extern bool bitmap_init(MY_BITMAP *map, my_bitmap_map *buf, uint n_bits);
50 extern bool bitmap_is_clear_all(const MY_BITMAP *map);
51 extern bool bitmap_is_prefix(const MY_BITMAP *map, uint prefix_size);
52 extern bool bitmap_is_set_all(const MY_BITMAP *map);
53 extern bool bitmap_is_subset(const MY_BITMAP *map1, const MY_BITMAP *map2);
54 extern bool bitmap_is_overlapping(const MY_BITMAP *map1, const MY_BITMAP *map2);
55 extern bool bitmap_test_and_set(MY_BITMAP *map, uint bitmap_bit);
56 extern uint bitmap_set_next(MY_BITMAP *map);
57 extern uint bitmap_get_first(const MY_BITMAP *map);
58 extern uint bitmap_get_first_set(const MY_BITMAP *map);
59 extern uint bitmap_get_next_set(const MY_BITMAP *map, uint bitmap_bit);
60 extern uint bitmap_bits_set(const MY_BITMAP *map);
61 extern void bitmap_free(MY_BITMAP *map);
62 extern void bitmap_set_above(MY_BITMAP *map, uint from_byte, bool use_bit);
63 extern void bitmap_set_prefix(MY_BITMAP *map, uint prefix_size);
64 extern void bitmap_intersect(MY_BITMAP *to, const MY_BITMAP *from);
65 extern void bitmap_subtract(MY_BITMAP *map, const MY_BITMAP *map2);
66 extern void bitmap_union(MY_BITMAP *map, const MY_BITMAP *map2);
67 extern void bitmap_xor(MY_BITMAP *map, const MY_BITMAP *map2);
68 extern void bitmap_invert(MY_BITMAP *map);
69 extern void bitmap_copy(MY_BITMAP *map, const MY_BITMAP *map2);
70 
71 #define bitmap_buffer_size(bits) (((bits) + 31) / 32) * 4
72 #define no_bytes_in_map(map) (((map)->n_bits + 7) / 8)
73 #define no_words_in_map(map) (((map)->n_bits + 31) / 32)
74 
75 static inline void bitmap_set_bit(MY_BITMAP *map, uint bit) {
76  assert(bit < map->n_bits);
77  ((uchar *)map->bitmap)[bit / 8] |= (1 << (bit & 7));
78 }
79 
80 static inline void bitmap_flip_bit(MY_BITMAP *map, uint bit) {
81  assert(bit < map->n_bits);
82  ((uchar *)map->bitmap)[bit / 8] ^= (1 << (bit & 7));
83 }
84 
85 static inline void bitmap_clear_bit(MY_BITMAP *map, uint bit) {
86  assert(bit < map->n_bits);
87  ((uchar *)map->bitmap)[bit / 8] &= ~(1 << (bit & 7));
88 }
89 
90 static inline bool bitmap_is_set(const MY_BITMAP *map, uint bit) {
91  assert(bit < map->n_bits);
92  return ((uchar *)map->bitmap)[bit / 8] & (1 << (bit & 7));
93 }
94 
95 /**
96  Quite unlike other C comparison functions ending with 'cmp', e.g. memcmp(),
97  strcmp(), this function returns true if the bitmaps are equal, and false
98  otherwise.
99 
100  @retval true The bitmaps are equal.
101  @retval false The bitmaps differ.
102  */
103 static inline bool bitmap_cmp(const MY_BITMAP *map1, const MY_BITMAP *map2) {
104  assert(map1->n_bits > 0);
105  assert(map2->n_bits > 0);
106 
107  if (memcmp(map1->bitmap, map2->bitmap, 4 * (no_words_in_map(map1) - 1)) != 0)
108  return false;
109  return ((*map1->last_word_ptr | map1->last_word_mask) ==
110  (*map2->last_word_ptr | map2->last_word_mask));
111 }
112 
113 /*
114  Clears all bits. This is allowed even for a zero-size bitmap.
115  */
116 static inline void bitmap_clear_all(MY_BITMAP *map) {
117  memset(map->bitmap, 0, 4 * no_words_in_map(map));
118 }
119 
120 /*
121  Sets all bits. This is allowed even for a zero-size bitmap.
122  */
123 static inline void bitmap_set_all(MY_BITMAP *map) {
124  memset(map->bitmap, 0xFF, 4 * no_words_in_map(map));
125 }
126 
127 #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:103
uint32 my_bitmap_map
Definition: my_bitmap.h:39
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:381
static void bitmap_set_all(MY_BITMAP *map)
Definition: my_bitmap.h:123
bool bitmap_is_clear_all(const MY_BITMAP *map)
Definition: my_bitmap.cc:267
void bitmap_invert(MY_BITMAP *map)
Definition: my_bitmap.cc:390
static bool bitmap_is_set(const MY_BITMAP *map, uint bit)
Definition: my_bitmap.h:90
static void bitmap_flip_bit(MY_BITMAP *map, uint bit)
Definition: my_bitmap.h:80
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:116
void bitmap_subtract(MY_BITMAP *map, const MY_BITMAP *map2)
Definition: my_bitmap.cc:363
uint bitmap_bits_set(const MY_BITMAP *map)
Definition: my_bitmap.cc:399
void bitmap_intersect(MY_BITMAP *to, const MY_BITMAP *from)
Definition: my_bitmap.cc:318
uint bitmap_get_next_set(const MY_BITMAP *map, uint bitmap_bit)
Get the next set bit.
Definition: my_bitmap.cc:445
void bitmap_set_above(MY_BITMAP *map, uint from_byte, bool use_bit)
Definition: my_bitmap.cc:355
uint bitmap_get_first_set(const MY_BITMAP *map)
Definition: my_bitmap.cc:422
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:372
static void bitmap_clear_bit(MY_BITMAP *map, uint bit)
Definition: my_bitmap.h:85
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:73
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:75
uint bitmap_get_first(const MY_BITMAP *map)
Definition: my_bitmap.cc:477
void bitmap_copy(MY_BITMAP *map, const MY_BITMAP *map2)
Definition: my_bitmap.cc:413
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
Definition: my_bitmap.h:41
my_bitmap_map * bitmap
Definition: my_bitmap.h:42
uint n_bits
Definition: my_bitmap.h:43
my_bitmap_map last_word_mask
Definition: my_bitmap.h:44
my_bitmap_map * last_word_ptr
Definition: my_bitmap.h:45
unsigned int uint
Definition: uca-dump.cc:29