← Back to branch summary

~drizzle-trunk/drizzle/development

« back to all changes in this revision

Viewing changes to include/my_bitmap.h

  • Committer: brian
  • Date: 2008-06-25 05:29:13 UTC
  • Revision ID: brian@localhost.localdomain-20080625052913-6upwo0jsrl4lnapl
clean slate

Show diffs side-by-side

added added

removed removed

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