1 /*
2 Copyright (c) 2001, 2012, 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 Street, Fifth Floor, Boston, MA 02110-1301, USA */
23
24 #ifndef _my_bitmap_h_
25 #define _my_bitmap_h_
26
27 #define MY_BIT_NONE (~(uint) 0)
28
29 #include <m_string.h>
30
31 typedef uint32 my_bitmap_map;
32
33 typedef struct st_bitmap
34 {
35 my_bitmap_map *bitmap;
36 uint n_bits; /* number of bits occupied by the above */
37 my_bitmap_map last_word_mask;
38 my_bitmap_map *last_word_ptr;
39 /*
40 mutex will be acquired for the duration of each bitmap operation if
41 thread_safe flag in bitmap_init was set. Otherwise, we optimize by not
42 acquiring the mutex
43 */
44 mysql_mutex_t *mutex;
45 } MY_BITMAP;
46
47 #ifdef __cplusplus
48 extern "C" {
49 #endif
50 extern void create_last_word_mask(MY_BITMAP *map);
51 extern my_bool bitmap_init(MY_BITMAP *map, my_bitmap_map *buf, uint n_bits,
52 my_bool thread_safe);
53 extern my_bool bitmap_is_clear_all(const MY_BITMAP *map);
54 extern my_bool bitmap_is_prefix(const MY_BITMAP *map, uint prefix_size);
55 extern my_bool bitmap_is_set_all(const MY_BITMAP *map);
56 extern my_bool bitmap_is_subset(const MY_BITMAP *map1, const MY_BITMAP *map2);
57 extern my_bool bitmap_is_overlapping(const MY_BITMAP *map1,
58 const MY_BITMAP *map2);
59 extern my_bool bitmap_test_and_set(MY_BITMAP *map, uint bitmap_bit);
60 extern my_bool bitmap_test_and_clear(MY_BITMAP *map, uint bitmap_bit);
61 extern my_bool bitmap_fast_test_and_set(MY_BITMAP *map, uint bitmap_bit);
62 extern uint bitmap_set_next(MY_BITMAP *map);
63 extern uint bitmap_get_first(const MY_BITMAP *map);
64 extern uint bitmap_get_first_set(const MY_BITMAP *map);
65 extern uint bitmap_get_next_set(const MY_BITMAP *map, uint bitmap_bit);
66 extern uint bitmap_bits_set(const MY_BITMAP *map);
67 extern void bitmap_free(MY_BITMAP *map);
68 extern void bitmap_set_above(MY_BITMAP *map, uint from_byte, uint use_bit);
69 extern void bitmap_set_prefix(MY_BITMAP *map, uint prefix_size);
70 extern void bitmap_intersect(MY_BITMAP *map, const MY_BITMAP *map2);
71 extern void bitmap_subtract(MY_BITMAP *map, const MY_BITMAP *map2);
72 extern void bitmap_union(MY_BITMAP *map, const MY_BITMAP *map2);
73 extern void bitmap_xor(MY_BITMAP *map, const MY_BITMAP *map2);
74 extern void bitmap_invert(MY_BITMAP *map);
75 extern void bitmap_copy(MY_BITMAP *map, const MY_BITMAP *map2);
76
77 extern uint bitmap_lock_set_next(MY_BITMAP *map);
78 extern void bitmap_lock_clear_bit(MY_BITMAP *map, uint bitmap_bit);
79 /* Fast, not thread safe, bitmap functions */
80 #define bitmap_buffer_size(bits) (((bits)+31)/32)*4
81 #define no_bytes_in_map(map) (((map)->n_bits + 7)/8)
82 #define no_words_in_map(map) (((map)->n_bits + 31)/32)
83
bitmap_set_bit(MY_BITMAP * map,uint bit)84 static inline void bitmap_set_bit(MY_BITMAP *map, uint bit)
85 {
86 DBUG_ASSERT(bit < map->n_bits);
87 ((uchar*)map->bitmap)[bit / 8] |= (1 << (bit & 7));
88 }
89
90
bitmap_flip_bit(MY_BITMAP * map,uint bit)91 static inline void bitmap_flip_bit(MY_BITMAP *map, uint bit)
92 {
93 DBUG_ASSERT(bit < map->n_bits);
94 ((uchar*)map->bitmap)[bit / 8] ^= (1 << (bit & 7));
95 }
96
97
bitmap_clear_bit(MY_BITMAP * map,uint bit)98 static inline void bitmap_clear_bit(MY_BITMAP *map, uint bit)
99 {
100 DBUG_ASSERT(bit < map->n_bits);
101 ((uchar*)map->bitmap)[bit / 8] &= ~(1 << (bit & 7));
102 }
103
104
bitmap_is_set(const MY_BITMAP * map,uint bit)105 static inline my_bool bitmap_is_set(const MY_BITMAP *map, uint bit)
106 {
107 DBUG_ASSERT(bit < map->n_bits);
108 return ((uchar*)map->bitmap)[bit / 8] & (1 << (bit & 7));
109 }
110
111 /**
112 Quite unlike other C comparison functions ending with 'cmp', e.g. memcmp(),
113 strcmp(), this function returns true if the bitmaps are equal, and false
114 otherwise.
115
116 @retval true The bitmaps are equal.
117 @retval false The bitmaps differ.
118 */
bitmap_cmp(const MY_BITMAP * map1,const MY_BITMAP * map2)119 static inline my_bool bitmap_cmp(const MY_BITMAP *map1, const MY_BITMAP *map2)
120 {
121 if (memcmp(map1->bitmap, map2->bitmap, 4*(no_words_in_map(map1)-1)) != 0)
122 return FALSE;
123 return ((*map1->last_word_ptr | map1->last_word_mask) ==
124 (*map2->last_word_ptr | map2->last_word_mask));
125 }
126
127 #define bitmap_clear_all(MAP) \
128 { memset((MAP)->bitmap, 0, 4*no_words_in_map((MAP))); }
129 #define bitmap_set_all(MAP) \
130 (memset((MAP)->bitmap, 0xFF, 4*no_words_in_map((MAP))))
131
132 #ifdef __cplusplus
133 }
134 #endif
135
136 #endif /* _my_bitmap_h_ */
137