forked from twitter-forks/mysql
/
my_bitmap.h
166 lines (149 loc) · 6.55 KB
/
my_bitmap.h
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
/* Copyright (C) 2000 MySQL AB
This program is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation; version 2 of the License.
This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU General Public License for more details.
You should have received a copy of the GNU General Public License
along with this program; if not, write to the Free Software
Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA */
#ifndef _my_bitmap_h_
#define _my_bitmap_h_
#define MY_BIT_NONE (~(uint) 0)
#include <m_string.h>
typedef uint32 my_bitmap_map;
typedef struct st_bitmap
{
my_bitmap_map *bitmap;
uint n_bits; /* number of bits occupied by the above */
my_bitmap_map last_word_mask;
my_bitmap_map *last_word_ptr;
/*
mutex will be acquired for the duration of each bitmap operation if
thread_safe flag in bitmap_init was set. Otherwise, we optimize by not
acquiring the mutex
*/
#ifdef THREAD
pthread_mutex_t *mutex;
#endif
} MY_BITMAP;
#ifdef __cplusplus
extern "C" {
#endif
extern void create_last_word_mask(MY_BITMAP *map);
extern my_bool bitmap_init(MY_BITMAP *map, my_bitmap_map *buf, uint n_bits,
my_bool thread_safe);
extern my_bool bitmap_is_clear_all(const MY_BITMAP *map);
extern my_bool bitmap_is_prefix(const MY_BITMAP *map, uint prefix_size);
extern my_bool bitmap_is_set_all(const MY_BITMAP *map);
extern my_bool bitmap_is_subset(const MY_BITMAP *map1, const MY_BITMAP *map2);
extern my_bool bitmap_is_overlapping(const MY_BITMAP *map1,
const MY_BITMAP *map2);
extern my_bool bitmap_test_and_set(MY_BITMAP *map, uint bitmap_bit);
extern my_bool bitmap_test_and_clear(MY_BITMAP *map, uint bitmap_bit);
extern my_bool bitmap_fast_test_and_set(MY_BITMAP *map, uint bitmap_bit);
extern uint bitmap_set_next(MY_BITMAP *map);
extern uint bitmap_get_first(const MY_BITMAP *map);
extern uint bitmap_get_first_set(const MY_BITMAP *map);
extern uint bitmap_bits_set(const MY_BITMAP *map);
extern void bitmap_free(MY_BITMAP *map);
extern void bitmap_set_above(MY_BITMAP *map, uint from_byte, uint use_bit);
extern void bitmap_set_prefix(MY_BITMAP *map, uint prefix_size);
extern void bitmap_intersect(MY_BITMAP *map, const MY_BITMAP *map2);
extern void bitmap_subtract(MY_BITMAP *map, const MY_BITMAP *map2);
extern void bitmap_union(MY_BITMAP *map, const MY_BITMAP *map2);
extern void bitmap_xor(MY_BITMAP *map, const MY_BITMAP *map2);
extern void bitmap_invert(MY_BITMAP *map);
extern void bitmap_copy(MY_BITMAP *map, const MY_BITMAP *map2);
extern uint bitmap_lock_set_next(MY_BITMAP *map);
extern void bitmap_lock_clear_bit(MY_BITMAP *map, uint bitmap_bit);
#ifdef NOT_USED
extern uint bitmap_lock_bits_set(const MY_BITMAP *map);
extern my_bool bitmap_lock_is_set_all(const MY_BITMAP *map);
extern uint bitmap_lock_get_first(const MY_BITMAP *map);
extern uint bitmap_lock_get_first_set(const MY_BITMAP *map);
extern my_bool bitmap_lock_is_subset(const MY_BITMAP *map1,
const MY_BITMAP *map2);
extern my_bool bitmap_lock_is_prefix(const MY_BITMAP *map, uint prefix_size);
extern my_bool bitmap_lock_is_set(const MY_BITMAP *map, uint bitmap_bit);
extern my_bool bitmap_lock_is_clear_all(const MY_BITMAP *map);
extern my_bool bitmap_lock_cmp(const MY_BITMAP *map1, const MY_BITMAP *map2);
extern void bitmap_lock_set_all(MY_BITMAP *map);
extern void bitmap_lock_clear_all(MY_BITMAP *map);
extern void bitmap_lock_set_bit(MY_BITMAP *map, uint bitmap_bit);
extern void bitmap_lock_flip_bit(MY_BITMAP *map, uint bitmap_bit);
extern void bitmap_lock_set_prefix(MY_BITMAP *map, uint prefix_size);
extern void bitmap_lock_intersect(MY_BITMAP *map, const MY_BITMAP *map2);
extern void bitmap_lock_subtract(MY_BITMAP *map, const MY_BITMAP *map2);
extern void bitmap_lock_union(MY_BITMAP *map, const MY_BITMAP *map2);
extern void bitmap_lock_xor(MY_BITMAP *map, const MY_BITMAP *map2);
extern void bitmap_lock_invert(MY_BITMAP *map);
#endif
/* Fast, not thread safe, bitmap functions */
#define bitmap_buffer_size(bits) (((bits)+31)/32)*4
#define no_bytes_in_map(map) (((map)->n_bits + 7)/8)
#define no_words_in_map(map) (((map)->n_bits + 31)/32)
#define bytes_word_aligned(bytes) (4*((bytes + 3)/4))
#define _bitmap_set_bit(MAP, BIT) (((uchar*)(MAP)->bitmap)[(BIT) / 8] \
|= (1 << ((BIT) & 7)))
#define _bitmap_flip_bit(MAP, BIT) (((uchar*)(MAP)->bitmap)[(BIT) / 8] \
^= (1 << ((BIT) & 7)))
#define _bitmap_clear_bit(MAP, BIT) (((uchar*)(MAP)->bitmap)[(BIT) / 8] \
&= ~ (1 << ((BIT) & 7)))
#define _bitmap_is_set(MAP, BIT) (uint) (((uchar*)(MAP)->bitmap)[(BIT) / 8] \
& (1 << ((BIT) & 7)))
/*
WARNING!
The below symbols are inline functions in DEBUG builds and macros in
non-DEBUG builds. The latter evaluate their 'bit' argument twice.
NEVER use an increment/decrement operator with the 'bit' argument.
It would work with DEBUG builds, but fails later in production builds!
FORBIDDEN: bitmap_set_bit($my_bitmap, (field++)->field_index);
*/
#ifndef DBUG_OFF
static inline void
bitmap_set_bit(MY_BITMAP *map,uint bit)
{
DBUG_ASSERT(bit < (map)->n_bits);
_bitmap_set_bit(map,bit);
}
static inline void
bitmap_flip_bit(MY_BITMAP *map,uint bit)
{
DBUG_ASSERT(bit < (map)->n_bits);
_bitmap_flip_bit(map,bit);
}
static inline void
bitmap_clear_bit(MY_BITMAP *map,uint bit)
{
DBUG_ASSERT(bit < (map)->n_bits);
_bitmap_clear_bit(map,bit);
}
static inline uint
bitmap_is_set(const MY_BITMAP *map,uint bit)
{
DBUG_ASSERT(bit < (map)->n_bits);
return _bitmap_is_set(map,bit);
}
#else
#define bitmap_set_bit(MAP, BIT) _bitmap_set_bit(MAP, BIT)
#define bitmap_flip_bit(MAP, BIT) _bitmap_flip_bit(MAP, BIT)
#define bitmap_clear_bit(MAP, BIT) _bitmap_clear_bit(MAP, BIT)
#define bitmap_is_set(MAP, BIT) _bitmap_is_set(MAP, BIT)
#endif
static inline my_bool bitmap_cmp(const MY_BITMAP *map1, const MY_BITMAP *map2)
{
*(map1)->last_word_ptr|= (map1)->last_word_mask;
*(map2)->last_word_ptr|= (map2)->last_word_mask;
return memcmp((map1)->bitmap, (map2)->bitmap, 4*no_words_in_map((map1)))==0;
}
#define bitmap_clear_all(MAP) \
{ memset((MAP)->bitmap, 0, 4*no_words_in_map((MAP))); }
#define bitmap_set_all(MAP) \
(memset((MAP)->bitmap, 0xFF, 4*no_words_in_map((MAP))))
#ifdef __cplusplus
}
#endif
#endif /* _my_bitmap_h_ */