MySQL  8.0.17
Source Code Documentation
my_bitmap.h
Go to the documentation of this file.
1 /*
2  Copyright (c) 2001, 2017, Oracle and/or its affiliates. All rights reserved.
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_h_
25 #define _my_bitmap_h_
26 
27 /**
28  @file include/my_bitmap.h
29 */
30 
31 #define MY_BIT_NONE (~(uint)0)
32 
33 #include <string.h>
34 #include <sys/types.h>
35 
36 #include "my_dbug.h"
37 #include "my_inttypes.h"
38 #include "mysql/psi/mysql_mutex.h" /* mysql_mutex_t */
39 
41 
42 struct MY_BITMAP {
43  my_bitmap_map *bitmap{nullptr};
44  uint n_bits{0}; /* number of bits occupied by the above */
47  /*
48  mutex will be acquired for the duration of each bitmap operation if
49  thread_safe flag in bitmap_init was set. Otherwise, we optimize by not
50  acquiring the mutex
51  */
52  mysql_mutex_t *mutex{nullptr};
53 };
54 
55 extern void create_last_word_mask(MY_BITMAP *map);
56 extern bool bitmap_init(MY_BITMAP *map, my_bitmap_map *buf, uint n_bits,
57  bool thread_safe);
58 extern bool bitmap_is_clear_all(const MY_BITMAP *map);
59 extern bool bitmap_is_prefix(const MY_BITMAP *map, uint prefix_size);
60 extern bool bitmap_is_set_all(const MY_BITMAP *map);
61 extern bool bitmap_is_subset(const MY_BITMAP *map1, const MY_BITMAP *map2);
62 extern bool bitmap_is_overlapping(const MY_BITMAP *map1, const MY_BITMAP *map2);
63 extern bool bitmap_test_and_set(MY_BITMAP *map, uint bitmap_bit);
64 extern bool bitmap_test_and_clear(MY_BITMAP *map, uint bitmap_bit);
65 extern bool bitmap_fast_test_and_set(MY_BITMAP *map, uint bitmap_bit);
66 extern uint bitmap_set_next(MY_BITMAP *map);
67 extern uint bitmap_get_first(const MY_BITMAP *map);
68 extern uint bitmap_get_first_set(const MY_BITMAP *map);
69 extern uint bitmap_get_next_set(const MY_BITMAP *map, uint bitmap_bit);
70 extern uint bitmap_bits_set(const MY_BITMAP *map);
71 extern void bitmap_free(MY_BITMAP *map);
72 extern void bitmap_set_above(MY_BITMAP *map, uint from_byte, uint use_bit);
73 extern void bitmap_set_prefix(MY_BITMAP *map, uint prefix_size);
74 extern void bitmap_intersect(MY_BITMAP *map, const MY_BITMAP *map2);
75 extern void bitmap_subtract(MY_BITMAP *map, const MY_BITMAP *map2);
76 extern void bitmap_union(MY_BITMAP *map, const MY_BITMAP *map2);
77 extern void bitmap_xor(MY_BITMAP *map, const MY_BITMAP *map2);
78 extern void bitmap_invert(MY_BITMAP *map);
79 extern void bitmap_copy(MY_BITMAP *map, const MY_BITMAP *map2);
80 
82 extern void bitmap_lock_clear_bit(MY_BITMAP *map, uint bitmap_bit);
83 /* Fast, not thread safe, bitmap functions */
84 #define bitmap_buffer_size(bits) (((bits) + 31) / 32) * 4
85 #define no_bytes_in_map(map) (((map)->n_bits + 7) / 8)
86 #define no_words_in_map(map) (((map)->n_bits + 31) / 32)
87 
88 static inline void bitmap_set_bit(MY_BITMAP *map, uint bit) {
89  DBUG_ASSERT(bit < map->n_bits);
90  ((uchar *)map->bitmap)[bit / 8] |= (1 << (bit & 7));
91 }
92 
93 static inline void bitmap_flip_bit(MY_BITMAP *map, uint bit) {
94  DBUG_ASSERT(bit < map->n_bits);
95  ((uchar *)map->bitmap)[bit / 8] ^= (1 << (bit & 7));
96 }
97 
98 static inline void bitmap_clear_bit(MY_BITMAP *map, uint bit) {
99  DBUG_ASSERT(bit < map->n_bits);
100  ((uchar *)map->bitmap)[bit / 8] &= ~(1 << (bit & 7));
101 }
102 
103 static inline bool bitmap_is_set(const MY_BITMAP *map, uint bit) {
104  DBUG_ASSERT(bit < map->n_bits);
105  return ((uchar *)map->bitmap)[bit / 8] & (1 << (bit & 7));
106 }
107 
108 /**
109  Quite unlike other C comparison functions ending with 'cmp', e.g. memcmp(),
110  strcmp(), this function returns true if the bitmaps are equal, and false
111  otherwise.
112 
113  @retval true The bitmaps are equal.
114  @retval false The bitmaps differ.
115  */
116 static inline bool bitmap_cmp(const MY_BITMAP *map1, const MY_BITMAP *map2) {
117  DBUG_ASSERT(map1->n_bits > 0);
118  DBUG_ASSERT(map2->n_bits > 0);
119 
120  if (memcmp(map1->bitmap, map2->bitmap, 4 * (no_words_in_map(map1) - 1)) != 0)
121  return false;
122  return ((*map1->last_word_ptr | map1->last_word_mask) ==
123  (*map2->last_word_ptr | map2->last_word_mask));
124 }
125 
126 /*
127  Clears all bits. This is allowed even for a zero-size bitmap.
128  */
129 static inline void bitmap_clear_all(MY_BITMAP *map) {
130  memset(map->bitmap, 0, 4 * no_words_in_map(map));
131 }
132 
133 /*
134  Sets all bits. This is allowed even for a zero-size bitmap.
135  */
136 static inline void bitmap_set_all(MY_BITMAP *map) {
137  memset(map->bitmap, 0xFF, 4 * no_words_in_map(map));
138 }
139 
140 #endif /* _my_bitmap_h_ */
static void bitmap_set_all(MY_BITMAP *map)
Definition: my_bitmap.h:136
Instrumentation helpers for mutexes.
unsigned char uchar
Definition: my_inttypes.h:51
void create_last_word_mask(MY_BITMAP *map)
Definition: my_bitmap.cc:66
void bitmap_xor(MY_BITMAP *map, const MY_BITMAP *map2)
Definition: my_bitmap.cc:465
void bitmap_copy(MY_BITMAP *map, const MY_BITMAP *map2)
Definition: my_bitmap.cc:497
uint n_bits
Definition: my_bitmap.h:44
my_bitmap_map * last_word_ptr
Definition: my_bitmap.h:46
uint bitmap_lock_set_next(MY_BITMAP *map)
Definition: my_bitmap.cc:575
void bitmap_union(MY_BITMAP *map, const MY_BITMAP *map2)
Definition: my_bitmap.cc:456
Some integer typedefs for easier portability.
uint bitmap_get_first_set(const MY_BITMAP *map)
Definition: my_bitmap.cc:506
void bitmap_free(MY_BITMAP *map)
Definition: my_bitmap.cc:186
bool bitmap_is_prefix(const MY_BITMAP *map, uint prefix_size)
Definition: my_bitmap.cc:301
my_bitmap_map * bitmap
Definition: my_bitmap.h:43
static bool bitmap_is_set(const MY_BITMAP *map, uint bit)
Definition: my_bitmap.h:103
static void bitmap_clear_bit(MY_BITMAP *map, uint bit)
Definition: my_bitmap.h:98
uint bitmap_set_next(MY_BITMAP *map)
Definition: my_bitmap.cc:270
bool bitmap_fast_test_and_set(MY_BITMAP *map, uint bitmap_bit)
Definition: my_bitmap.cc:210
static void bitmap_set_bit(MY_BITMAP *map, uint bit)
Definition: my_bitmap.h:88
bool bitmap_init(MY_BITMAP *map, my_bitmap_map *buf, uint n_bits, bool thread_safe)
Definition: my_bitmap.cc:150
#define DBUG_ASSERT(A)
Definition: my_dbug.h:183
void bitmap_invert(MY_BITMAP *map)
Definition: my_bitmap.cc:474
bool bitmap_is_subset(const MY_BITMAP *map1, const MY_BITMAP *map2)
Definition: my_bitmap.cc:364
Definition: my_bitmap.h:42
static void bitmap_flip_bit(MY_BITMAP *map, uint bit)
Definition: my_bitmap.h:93
unsigned int uint
Definition: uca-dump.cc:29
uint32_t uint32
Definition: my_inttypes.h:62
void bitmap_subtract(MY_BITMAP *map, const MY_BITMAP *map2)
Definition: my_bitmap.cc:447
void bitmap_set_prefix(MY_BITMAP *map, uint prefix_size)
Set the specified number of bits in the bitmap buffer.
Definition: my_bitmap.cc:284
bool bitmap_is_set_all(const MY_BITMAP *map)
Definition: my_bitmap.cc:340
uint bitmap_get_next_set(const MY_BITMAP *map, uint bitmap_bit)
Get the next set bit.
Definition: my_bitmap.cc:529
void bitmap_set_above(MY_BITMAP *map, uint from_byte, uint use_bit)
Definition: my_bitmap.cc:439
static void bitmap_clear_all(MY_BITMAP *map)
Definition: my_bitmap.h:129
static bool bitmap_cmp(const MY_BITMAP *map1, const MY_BITMAP *map2)
Quite unlike other C comparison functions ending with &#39;cmp&#39;, e.g.
Definition: my_bitmap.h:116
An instrumented mutex structure.
Definition: mysql_mutex_bits.h:49
bool bitmap_test_and_set(MY_BITMAP *map, uint bitmap_bit)
Definition: my_bitmap.cc:231
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:384
uint bitmap_get_first(const MY_BITMAP *map)
Definition: my_bitmap.cc:561
mysql_mutex_t * mutex
Definition: my_bitmap.h:52
my_bitmap_map last_word_mask
Definition: my_bitmap.h:45
uint bitmap_bits_set(const MY_BITMAP *map)
Definition: my_bitmap.cc:483
void bitmap_lock_clear_bit(MY_BITMAP *map, uint bitmap_bit)
Definition: my_bitmap.cc:583
bool bitmap_test_and_clear(MY_BITMAP *map, uint bitmap_bit)
Definition: my_bitmap.cc:261
#define no_words_in_map(map)
Definition: my_bitmap.h:86
void bitmap_intersect(MY_BITMAP *map, const MY_BITMAP *map2)
Definition: my_bitmap.cc:402
bool bitmap_is_clear_all(const MY_BITMAP *map)
Definition: my_bitmap.cc:351