← Back to branch summary

~drizzle-trunk/drizzle/development

« back to all changes in this revision

Viewing changes to mysys/my_bitmap.cc

  • Committer: Eric Day
  • Date: 2009-08-27 18:06:03 UTC
  • mfrom: (1125 staging)
  • mto: This revision was merged to the branch mainline in revision 1131.
  • Revision ID: eday@oddments.org-20090827180603-hy264dq4s78dptdo
Merged trunk.

Show diffs side-by-side

added added

removed removed

Lines of Context:
mysys/my_bitmap.cc
13
13
   along with this program; if not, write to the Free Software
14
14
   Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA */
15
15
 
16
 
/*
17
 
  Handling of unsigned char arrays as large bitmaps.
18
 
 
19
 
  API limitations (or, rather asserted safety assumptions,
20
 
  to encourage correct programming)
21
 
 
22
 
    * the internal size is a set of 32 bit words
23
 
    * the number of bits specified in creation can be any number > 0
24
 
 
25
 
 
26
 
  Original version created by Sergei Golubchik 2001 - 2004.
27
 
  New version written and test program added and some changes to the interface
28
 
  was made by Mikael Ronström 2005, with assistance of Tomas Ulin and Mats
29
 
  Kindahl.
30
 
*/
31
 
 
32
16
#include "mysys_priv.h"
33
17
#include <mysys/my_bitmap.h>
34
18
#include <mystrings/m_string.h>
35
19
#include <mysys/my_bit.h>
36
20
 
37
 
#include <algorithm>
38
 
 
39
21
using namespace std;
40
22
 
41
 
void create_last_word_mask(MY_BITMAP *map)
 
23
void MyBitmap::createLastWordMask()
42
24
{
43
25
  /* Get the number of used bits (1..8) in the last byte */
44
 
  unsigned int const used= 1U + ((map->n_bits-1U) & 0x7U);
 
26
  unsigned int const used= 1U + ((n_bits-1U) & 0x7U);
45
27
 
46
28
  /*
47
29
    Create a mask with the upper 'unused' bits set and the lower 'used'
55
37
    bytes not used by the bitvector. Finally the last byte contains  bits
56
38
    as set by the mask above.
57
39
  */
58
 
  unsigned char *ptr= (unsigned char*)&map->last_word_mask;
 
40
  unsigned char *ptr= (unsigned char*)&last_word_mask;
59
41
 
60
 
  map->last_word_ptr= map->bitmap + no_words_in_map(map)-1;
61
 
  switch (no_bytes_in_map(map) & 3) {
 
42
  last_word_ptr= bitmap + numOfWordsInMap()-1;
 
43
  switch (numOfBytesInMap() & 3) 
 
44
  {
62
45
  case 1:
63
 
    map->last_word_mask= UINT32_MAX;
 
46
    last_word_mask= UINT32_MAX;
64
47
    ptr[0]= mask;
65
48
    return;
66
49
  case 2:
67
 
    map->last_word_mask= UINT32_MAX;
 
50
    last_word_mask= UINT32_MAX;
68
51
    ptr[0]= 0;
69
52
    ptr[1]= mask;
70
53
    return;
71
54
  case 3:
72
 
    map->last_word_mask= 0;
 
55
    last_word_mask= 0;
73
56
    ptr[2]= mask;
74
57
    ptr[3]= 0xFFU;
75
58
    return;
76
59
  case 0:
77
 
    map->last_word_mask= 0U;
 
60
    last_word_mask= 0U;
78
61
    ptr[3]= mask;
79
62
    return;
80
63
  }
81
64
}
82
65
 
83
66
 
84
 
bool bitmap_init(MY_BITMAP *map, my_bitmap_map *buf, uint32_t n_bits)
85
 
{
86
 
  if (!buf)
87
 
  {
88
 
    uint32_t size_in_bytes= bitmap_buffer_size(n_bits);
89
 
    size_in_bytes= ALIGN_SIZE(size_in_bytes);
90
 
    if (!(buf= (my_bitmap_map*) malloc(size_in_bytes)))
91
 
      return(1);
92
 
  }
93
 
 
94
 
  map->bitmap= buf;
95
 
  map->n_bits= n_bits;
96
 
  create_last_word_mask(map);
97
 
  bitmap_clear_all(map);
98
 
  return(0);
99
 
}
100
 
 
101
 
 
102
 
void bitmap_free(MY_BITMAP *map)
103
 
{
104
 
  if (map->bitmap)
105
 
  {
106
 
    free((char*) map->bitmap);
107
 
    map->bitmap=0;
108
 
  }
109
 
  return;
110
 
}
111
 
 
112
 
 
113
 
/*
114
 
  test if bit already set and set it if it was not
115
 
 
116
 
  SYNOPSIS
117
 
    bitmap_test_and_set()
118
 
    MAP   bit map struct
119
 
    BIT   bit number
120
 
 
121
 
  RETURN
122
 
    0    bit was not set
123
 
    !=0  bit was set
124
 
*/
125
 
 
126
 
bool bitmap_test_and_set(MY_BITMAP *map, uint32_t bitmap_bit)
127
 
{
128
 
  unsigned char *value= ((unsigned char*) map->bitmap) + (bitmap_bit / 8);
129
 
  unsigned char bit= 1 << ((bitmap_bit) & 7);
 
67
bool MyBitmap::init(my_bitmap_map *buf, uint32_t num_bits)
 
68
{
 
69
  if (! buf)
 
70
  {
 
71
    uint32_t size_in_bytes= bitmap_buffer_size(num_bits);
 
72
    if (! (buf= new(std::nothrow) my_bitmap_map[size_in_bytes]()))
 
73
    {
 
74
      return true;
 
75
    }
 
76
  }
 
77
 
 
78
  bitmap= buf;
 
79
  n_bits= num_bits;
 
80
  createLastWordMask();
 
81
  clearAll();
 
82
 
 
83
  return false;
 
84
}
 
85
 
 
86
 
 
87
bool MyBitmap::testAndSet(const uint32_t bitPos)
 
88
{
 
89
  unsigned char *value= ((unsigned char*) bitmap) + (bitPos / 8);
 
90
  unsigned char bit= 1 << ((bitPos) & 7);
130
91
  unsigned char res= (*value) & bit;
131
92
  *value|= bit;
132
93
  return res;
134
95
 
135
96
 
136
97
 
137
 
/*
138
 
  test if bit already set and clear it if it was set
139
 
 
140
 
  SYNOPSIS
141
 
    bitmap_test_and_set()
142
 
    MAP   bit map struct
143
 
    BIT   bit number
144
 
 
145
 
  RETURN
146
 
    0    bit was not set
147
 
    !=0  bit was set
148
 
*/
149
 
 
150
 
bool bitmap_test_and_clear(MY_BITMAP *map, uint32_t bitmap_bit)
 
98
bool MyBitmap::testAndClear(const uint32_t bitPos)
151
99
{
152
 
  unsigned char *byte= (unsigned char*) map->bitmap + (bitmap_bit / 8);
153
 
  unsigned char bit= 1 << ((bitmap_bit) & 7);
 
100
  unsigned char *byte= (unsigned char*) bitmap + (bitPos / 8);
 
101
  unsigned char bit= 1 << ((bitPos) & 7);
154
102
  unsigned char res= (*byte) & bit;
155
103
  *byte&= ~bit;
156
104
  return res;
158
106
 
159
107
 
160
108
 
161
 
uint32_t bitmap_set_next(MY_BITMAP *map)
 
109
uint32_t MyBitmap::setNext()
162
110
{
163
111
  uint32_t bit_found;
164
 
  assert(map->bitmap);
165
 
  if ((bit_found= bitmap_get_first(map)) != MY_BIT_NONE)
166
 
    bitmap_set_bit(map, bit_found);
 
112
  assert(bitmap);
 
113
  if ((bit_found= getFirst()) != MY_BIT_NONE)
 
114
  {
 
115
    setBit(bit_found);
 
116
  }
167
117
  return bit_found;
168
118
}
169
119
 
170
120
 
171
 
void bitmap_set_prefix(MY_BITMAP *map, uint32_t prefix_size)
 
121
void MyBitmap::setPrefix(uint32_t prefix_size)
172
122
{
173
123
  uint32_t prefix_bytes, prefix_bits, d;
174
 
  unsigned char *m= (unsigned char *)map->bitmap;
 
124
  unsigned char *m= (unsigned char *) bitmap;
175
125
 
176
 
  assert(map->bitmap &&
177
 
              (prefix_size <= map->n_bits || prefix_size == UINT32_MAX));
178
 
  set_if_smaller(prefix_size, map->n_bits);
 
126
  assert(bitmap &&
 
127
         (prefix_size <= n_bits || prefix_size == UINT32_MAX));
 
128
  set_if_smaller(prefix_size, n_bits);
179
129
  if ((prefix_bytes= prefix_size / 8))
 
130
  {
180
131
    memset(m, 0xff, prefix_bytes);
 
132
  }
181
133
  m+= prefix_bytes;
182
134
  if ((prefix_bits= prefix_size & 7))
 
135
  {
183
136
    *m++= (1 << prefix_bits)-1;
184
 
  if ((d= no_bytes_in_map(map)-prefix_bytes))
 
137
  }
 
138
  if ((d= numOfBytesInMap() - prefix_bytes))
 
139
  {
185
140
    memset(m, 0, d);
 
141
  }
186
142
}
187
143
 
188
144
 
189
 
bool bitmap_is_prefix(const MY_BITMAP *map, uint32_t prefix_size)
 
145
bool MyBitmap::isPrefix(const uint32_t prefix_size) const
190
146
{
191
147
  uint32_t prefix_bits= prefix_size & 0x7, res;
192
 
  unsigned char *m= (unsigned char*)map->bitmap;
193
 
  unsigned char *end_prefix= m+prefix_size/8;
 
148
  unsigned char *m= (unsigned char*) bitmap;
 
149
  unsigned char *end_prefix= m + prefix_size/8;
194
150
  unsigned char *end;
195
 
  assert(m && prefix_size <= map->n_bits);
196
 
  end= m+no_bytes_in_map(map);
 
151
  assert(m && prefix_size <= n_bits);
 
152
  end= m + numOfBytesInMap();
197
153
 
198
154
  while (m < end_prefix)
 
155
  {
199
156
    if (*m++ != 0xff)
 
157
    {
200
158
      return 0;
 
159
    }
 
160
  }
201
161
 
202
 
  *map->last_word_ptr&= ~map->last_word_mask; /*Clear bits*/
 
162
  *last_word_ptr&= ~last_word_mask; /*Clear bits*/
203
163
  res= 0;
204
164
  if (prefix_bits && *m++ != (1 << prefix_bits)-1)
 
165
  {
205
166
    goto ret;
 
167
  }
206
168
 
207
169
  while (m < end)
 
170
  {
208
171
    if (*m++ != 0)
 
172
    {
209
173
      goto ret;
 
174
    }
 
175
  }
210
176
  res= 1;
211
177
ret:
212
178
  return res;
213
179
}
214
180
 
215
181
 
216
 
bool bitmap_is_set_all(const MY_BITMAP *map)
 
182
bool MyBitmap::isSetAll() const
217
183
{
218
 
  my_bitmap_map *data_ptr= map->bitmap;
219
 
  my_bitmap_map *end= map->last_word_ptr;
220
 
  *map->last_word_ptr |= map->last_word_mask;
 
184
  my_bitmap_map *data_ptr= bitmap;
 
185
  my_bitmap_map *end= last_word_ptr;
 
186
  *last_word_ptr |= last_word_mask;
221
187
  for (; data_ptr <= end; data_ptr++)
 
188
  {
222
189
    if (*data_ptr != 0xFFFFFFFF)
 
190
    {
223
191
      return false;
 
192
    }
 
193
  }
224
194
  return true;
225
195
}
226
196
 
227
197
 
228
 
bool bitmap_is_clear_all(const MY_BITMAP *map)
 
198
bool MyBitmap::isClearAll() const
229
199
{
230
 
  my_bitmap_map *data_ptr= map->bitmap;
 
200
  my_bitmap_map *data_ptr= bitmap;
231
201
  my_bitmap_map *end;
232
 
  if (*map->last_word_ptr & ~map->last_word_mask)
 
202
  if (*last_word_ptr & ~last_word_mask)
 
203
  {
233
204
    return false;
234
 
  end= map->last_word_ptr;
 
205
  }
 
206
  end= last_word_ptr;
235
207
  for (; data_ptr < end; data_ptr++)
 
208
  {
236
209
    if (*data_ptr)
 
210
    {
237
211
      return false;
 
212
    }
 
213
  }
238
214
  return true;
239
215
}
240
216
 
241
217
/* Return true if map1 is a subset of map2 */
242
218
 
243
 
bool bitmap_is_subset(const MY_BITMAP *map1, const MY_BITMAP *map2)
 
219
bool bitmap_is_subset(const MyBitmap *map1, const MyBitmap *map2)
244
220
{
245
 
  my_bitmap_map *m1= map1->bitmap, *m2= map2->bitmap, *end;
246
 
 
247
 
  assert(map1->bitmap && map2->bitmap &&
248
 
              map1->n_bits==map2->n_bits);
249
 
 
250
 
  end= map1->last_word_ptr;
251
 
  *map1->last_word_ptr &= ~map1->last_word_mask;
252
 
  *map2->last_word_ptr &= ~map2->last_word_mask;
 
221
  my_bitmap_map *m1= map1->getBitmap(), *m2= map2->getBitmap(), *end;
 
222
 
 
223
  assert(map1->getBitmap() && map2->getBitmap() &&
 
224
         map1->numOfBitsInMap() == map2->numOfBitsInMap());
 
225
 
 
226
  end= map1->getLastWordPtr();
 
227
  map1->subtractMaskFromLastWord();
 
228
  map2->subtractMaskFromLastWord();
253
229
  while (m1 <= end)
254
230
  {
255
231
    if ((*m1++) & ~(*m2++))
 
232
    {
256
233
      return 0;
 
234
    }
257
235
  }
258
236
  return 1;
259
237
}
260
238
 
261
239
/* True if bitmaps has any common bits */
262
240
 
263
 
bool bitmap_is_overlapping(const MY_BITMAP *map1, const MY_BITMAP *map2)
 
241
bool bitmap_is_overlapping(const MyBitmap *map1, const MyBitmap *map2)
264
242
{
265
 
  my_bitmap_map *m1= map1->bitmap, *m2= map2->bitmap, *end;
266
 
 
267
 
  assert(map1->bitmap && map2->bitmap &&
268
 
              map1->n_bits==map2->n_bits);
269
 
 
270
 
  end= map1->last_word_ptr;
271
 
  *map1->last_word_ptr &= ~map1->last_word_mask;
272
 
  *map2->last_word_ptr &= ~map2->last_word_mask;
 
243
  my_bitmap_map *m1= map1->getBitmap(), *m2= map2->getBitmap(), *end;
 
244
 
 
245
  assert(map1->getBitmap() && map2->getBitmap() &&
 
246
         map1->numOfBitsInMap() == map2->numOfBitsInMap());
 
247
 
 
248
  end= map1->getLastWordPtr();
 
249
  map1->subtractMaskFromLastWord();
 
250
  map2->subtractMaskFromLastWord();
273
251
  while (m1 <= end)
274
252
  {
275
253
    if ((*m1++) & (*m2++))
279
257
}
280
258
 
281
259
 
282
 
void bitmap_intersect(MY_BITMAP *map, const MY_BITMAP *map2)
 
260
void bitmap_intersect(MyBitmap *map, const MyBitmap *map2)
283
261
{
284
 
  my_bitmap_map *to= map->bitmap, *from= map2->bitmap, *end;
285
 
  uint32_t len= no_words_in_map(map), len2 = no_words_in_map(map2);
 
262
  my_bitmap_map *to= map->getBitmap(), *from= map2->getBitmap(), *end;
 
263
  uint32_t len= map->numOfWordsInMap(), len2 = map2->numOfWordsInMap();
286
264
 
287
 
  assert(map->bitmap && map2->bitmap);
 
265
  assert(map->getBitmap() && map2->getBitmap());
288
266
 
289
267
  end= to+min(len,len2);
290
 
  *map2->last_word_ptr&= ~map2->last_word_mask; /*Clear last bits in map2*/
 
268
  map2->subtractMaskFromLastWord(); /* Clear last bits in map2 */
291
269
  while (to < end)
 
270
  {
292
271
    *to++ &= *from++;
 
272
  }
293
273
 
294
274
  if (len2 < len)
295
275
  {
296
276
    end+=len-len2;
297
277
    while (to < end)
 
278
    {
298
279
      *to++=0;
 
280
    }
299
281
  }
300
282
}
301
283
 
302
284
 
303
 
/*
304
 
  Set/clear all bits above a bit.
305
 
 
306
 
  SYNOPSIS
307
 
    bitmap_set_above()
308
 
    map                  RETURN The bitmap to change.
309
 
    from_byte                   The bitmap buffer byte offset to start with.
310
 
    use_bit                     The bit value (1/0) to use for all upper bits.
311
 
 
312
 
  NOTE
313
 
    You can only set/clear full bytes.
314
 
    The function is meant for the situation that you copy a smaller bitmap
315
 
    to a bigger bitmap. Bitmap lengths are always multiple of eigth (the
316
 
    size of a byte). Using 'from_byte' saves multiplication and division
317
 
    by eight during parameter passing.
318
 
 
319
 
  RETURN
320
 
    void
321
 
*/
322
 
 
323
 
void bitmap_set_above(MY_BITMAP *map, uint32_t from_byte, uint32_t use_bit)
 
285
void MyBitmap::setAbove(const uint32_t from_byte, const uint32_t use_bit)
324
286
{
325
287
  unsigned char use_byte= use_bit ? 0xff : 0;
326
 
  unsigned char *to= (unsigned char *)map->bitmap + from_byte;
327
 
  unsigned char *end= (unsigned char *)map->bitmap + (map->n_bits+7)/8;
 
288
  unsigned char *to= (unsigned char *) bitmap + from_byte;
 
289
  unsigned char *end= (unsigned char *) bitmap + (n_bits+7)/8;
328
290
 
329
291
  while (to < end)
 
292
  {
330
293
    *to++= use_byte;
 
294
  }
331
295
}
332
296
 
333
297
 
334
 
void bitmap_subtract(MY_BITMAP *map, const MY_BITMAP *map2)
 
298
void bitmap_subtract(MyBitmap *map, const MyBitmap *map2)
335
299
{
336
 
  my_bitmap_map *to= map->bitmap, *from= map2->bitmap, *end;
337
 
  assert(map->bitmap && map2->bitmap &&
338
 
              map->n_bits==map2->n_bits);
 
300
  my_bitmap_map *to= map->getBitmap(), *from= map2->getBitmap(), *end;
 
301
  assert(map->getBitmap() && map2->getBitmap() &&
 
302
         map->numOfBitsInMap() == map2->numOfBitsInMap());
339
303
 
340
 
  end= map->last_word_ptr;
 
304
  end= map->getLastWordPtr();
341
305
 
342
306
  while (to <= end)
 
307
  {
343
308
    *to++ &= ~(*from++);
 
309
  }
344
310
}
345
311
 
346
312
 
347
 
void bitmap_union(MY_BITMAP *map, const MY_BITMAP *map2)
 
313
void bitmap_union(MyBitmap *map, const MyBitmap *map2)
348
314
{
349
 
  my_bitmap_map *to= map->bitmap, *from= map2->bitmap, *end;
 
315
  my_bitmap_map *to= map->getBitmap(), *from= map2->getBitmap(), *end;
350
316
 
351
 
  assert(map->bitmap && map2->bitmap &&
352
 
              map->n_bits==map2->n_bits);
353
 
  end= map->last_word_ptr;
 
317
  assert(map->getBitmap() && map2->getBitmap() &&
 
318
         map->numOfBitsInMap() == map2->numOfBitsInMap());
 
319
  end= map->getLastWordPtr();
354
320
 
355
321
  while (to <= end)
 
322
  {
356
323
    *to++ |= *from++;
 
324
  }
357
325
}
358
326
 
359
327
 
360
 
void bitmap_xor(MY_BITMAP *map, const MY_BITMAP *map2)
 
328
void bitmap_xor(MyBitmap *map, const MyBitmap *map2)
361
329
{
362
 
  my_bitmap_map *to= map->bitmap, *from= map2->bitmap, *end= map->last_word_ptr;
363
 
  assert(map->bitmap && map2->bitmap &&
364
 
              map->n_bits==map2->n_bits);
 
330
  my_bitmap_map *to= map->getBitmap();
 
331
  my_bitmap_map *from= map2->getBitmap();
 
332
  my_bitmap_map *end= map->getLastWordPtr();
 
333
  assert(map->getBitmap() && map2->getBitmap() &&
 
334
         map->numOfBitsInMap() == map2->numOfBitsInMap());
365
335
  while (to <= end)
 
336
  {
366
337
    *to++ ^= *from++;
 
338
  }
367
339
}
368
340
 
369
341
 
370
 
void bitmap_invert(MY_BITMAP *map)
 
342
void bitmap_invert(MyBitmap *map)
371
343
{
372
 
  my_bitmap_map *to= map->bitmap, *end;
 
344
  my_bitmap_map *to= map->getBitmap(), *end;
373
345
 
374
 
  assert(map->bitmap);
375
 
  end= map->last_word_ptr;
 
346
  assert(map->getBitmap());
 
347
  end= map->getLastWordPtr();
376
348
 
377
349
  while (to <= end)
 
350
  {
378
351
    *to++ ^= 0xFFFFFFFF;
 
352
  }
379
353
}
380
354
 
381
355
 
382
 
uint32_t bitmap_bits_set(const MY_BITMAP *map)
 
356
uint32_t MyBitmap::getBitsSet()
383
357
{
384
 
  unsigned char *m= (unsigned char*)map->bitmap;
385
 
  unsigned char *end= m + no_bytes_in_map(map);
 
358
  unsigned char *m= (unsigned char*) bitmap;
 
359
  unsigned char *end= m + numOfBytesInMap();
386
360
  uint32_t res= 0;
387
361
 
388
 
  assert(map->bitmap);
389
 
  *map->last_word_ptr&= ~map->last_word_mask; /*Reset last bits to zero*/
 
362
  assert(bitmap);
 
363
  *last_word_ptr&= ~last_word_mask; /*Reset last bits to zero*/
390
364
  while (m < end)
 
365
  {
391
366
    res+= my_count_bits_uint16(*m++);
 
367
  }
392
368
  return res;
393
369
}
394
370
 
395
 
 
396
 
void bitmap_copy(MY_BITMAP *map, const MY_BITMAP *map2)
397
 
{
398
 
  my_bitmap_map *to= map->bitmap, *from= map2->bitmap, *end;
399
 
 
400
 
  assert(map->bitmap && map2->bitmap &&
401
 
              map->n_bits==map2->n_bits);
402
 
  end= map->last_word_ptr;
403
 
  while (to <= end)
404
 
    *to++ = *from++;
405
 
}
406
 
 
407
 
 
408
 
uint32_t bitmap_get_first_set(const MY_BITMAP *map)
 
371
MyBitmap::MyBitmap(const MyBitmap& rhs)
 
372
{
 
373
  my_bitmap_map *to= this->bitmap, *from= rhs.bitmap, *end;
 
374
 
 
375
  if (this->bitmap && rhs.bitmap &&
 
376
      this->n_bits == rhs.n_bits)
 
377
  {
 
378
    end= this->last_word_ptr;
 
379
    while (to <= end)
 
380
    {
 
381
      *to++ = *from++;
 
382
    }
 
383
  }
 
384
  else
 
385
  {
 
386
    this->n_bits= rhs.n_bits;
 
387
    this->bitmap= rhs.bitmap;
 
388
  }
 
389
}
 
390
 
 
391
MyBitmap& MyBitmap::operator=(const MyBitmap& rhs)
 
392
{
 
393
  if (this == &rhs)
 
394
    return *this;
 
395
 
 
396
  my_bitmap_map *to= this->bitmap, *from= rhs.bitmap, *end;
 
397
 
 
398
  if (this->bitmap && rhs.bitmap &&
 
399
      this->n_bits == rhs.n_bits)
 
400
  {
 
401
    end= this->last_word_ptr;
 
402
    while (to <= end)
 
403
    {
 
404
      *to++ = *from++;
 
405
    }
 
406
  }
 
407
  else
 
408
  {
 
409
    this->n_bits= rhs.n_bits;
 
410
    this->bitmap= rhs.bitmap;
 
411
  }
 
412
 
 
413
  return *this;
 
414
}
 
415
 
 
416
uint32_t MyBitmap::getFirstSet()
409
417
{
410
418
  unsigned char *byte_ptr;
411
419
  uint32_t i,j,k;
412
 
  my_bitmap_map *data_ptr, *end= map->last_word_ptr;
 
420
  my_bitmap_map *data_ptr, *end= last_word_ptr;
413
421
 
414
 
  assert(map->bitmap);
415
 
  data_ptr= map->bitmap;
416
 
  *map->last_word_ptr &= ~map->last_word_mask;
 
422
  assert(bitmap);
 
423
  data_ptr= bitmap;
 
424
  *last_word_ptr &= ~last_word_mask;
417
425
 
418
426
  for (i=0; data_ptr <= end; data_ptr++, i++)
419
427
  {
437
445
}
438
446
 
439
447
 
440
 
uint32_t bitmap_get_first(const MY_BITMAP *map)
 
448
uint32_t MyBitmap::getFirst()
441
449
{
442
450
  unsigned char *byte_ptr;
443
451
  uint32_t i,j,k;
444
 
  my_bitmap_map *data_ptr, *end= map->last_word_ptr;
 
452
  my_bitmap_map *data_ptr, *end= last_word_ptr;
445
453
 
446
 
  assert(map->bitmap);
447
 
  data_ptr= map->bitmap;
448
 
  *map->last_word_ptr|= map->last_word_mask;
 
454
  assert(bitmap);
 
455
  data_ptr= bitmap;
 
456
  *last_word_ptr|= last_word_mask;
449
457
 
450
458
  for (i=0; data_ptr <= end; data_ptr++, i++)
451
459
  {
476
484
  return (rand() % bitsize);
477
485
}
478
486
 
479
 
bool test_set_get_clear_bit(MY_BITMAP *map, uint32_t bitsize)
 
487
bool test_set_get_clear_bit(MyBitmap *map, uint32_t bitsize)
480
488
{
481
489
  uint32_t i, test_bit;
482
490
  uint32_t no_loops= bitsize > 128 ? 128 : bitsize;
483
491
  for (i=0; i < no_loops; i++)
484
492
  {
485
493
    test_bit= get_rand_bit(bitsize);
486
 
    bitmap_set_bit(map, test_bit);
487
 
    if (!bitmap_is_set(map, test_bit))
 
494
    map->setBit(test_bit);
 
495
    if (! map->isBitSet(test_bit))
 
496
    {
488
497
      goto error1;
489
 
    bitmap_clear_bit(map, test_bit);
490
 
    if (bitmap_is_set(map, test_bit))
 
498
    }
 
499
    map->clearBit(test_bit);
 
500
    if (map->isBitSet(test_bit))
 
501
    {
491
502
      goto error2;
 
503
    }
492
504
  }
493
505
  return false;
494
506
error1:
499
511
  return true;
500
512
}
501
513
 
502
 
bool test_flip_bit(MY_BITMAP *map, uint32_t bitsize)
 
514
bool test_flip_bit(MyBitmap *map, uint32_t bitsize)
503
515
{
504
516
  uint32_t i, test_bit;
505
517
  uint32_t no_loops= bitsize > 128 ? 128 : bitsize;
506
518
  for (i=0; i < no_loops; i++)
507
519
  {
508
520
    test_bit= get_rand_bit(bitsize);
509
 
    bitmap_flip_bit(map, test_bit);
510
 
    if (!bitmap_is_set(map, test_bit))
 
521
    map->flipBit(test_bit);
 
522
    if (!map->isBitSet(test_bit))
511
523
      goto error1;
512
 
    bitmap_flip_bit(map, test_bit);
513
 
    if (bitmap_is_set(map, test_bit))
 
524
    map->flipBit(test_bit);
 
525
    if (map->isBitSet(test_bit))
514
526
      goto error2;
515
527
  }
516
528
  return false;
522
534
  return true;
523
535
}
524
536
 
525
 
bool test_operators(MY_BITMAP *, uint32_t)
 
537
bool test_operators(MyBitmap *, uint32_t)
526
538
{
527
539
  return false;
528
540
}
529
541
 
530
 
bool test_get_all_bits(MY_BITMAP *map, uint32_t bitsize)
 
542
bool test_get_all_bits(MyBitmap *map, uint32_t bitsize)
531
543
{
532
544
  uint32_t i;
533
 
  bitmap_set_all(map);
534
 
  if (!bitmap_is_set_all(map))
 
545
  map->setAll();
 
546
  if (!map->isSetAll())
535
547
    goto error1;
536
 
  if (!bitmap_is_prefix(map, bitsize))
 
548
  if (!map->isPrefix(bitsize))
537
549
    goto error5;
538
 
  bitmap_clear_all(map);
539
 
  if (!bitmap_is_clear_all(map))
 
550
  map->clearAll();
 
551
  if (!map->isClearAll())
540
552
    goto error2;
541
 
  if (!bitmap_is_prefix(map, 0))
 
553
  if (!map->isPrefix(0))
542
554
    goto error6;
543
555
  for (i=0; i<bitsize;i++)
544
 
    bitmap_set_bit(map, i);
545
 
  if (!bitmap_is_set_all(map))
 
556
    map->setBit(i);
 
557
  if (!map->isSetAll())
546
558
    goto error3;
547
559
  for (i=0; i<bitsize;i++)
548
 
    bitmap_clear_bit(map, i);
549
 
  if (!bitmap_is_clear_all(map))
 
560
    map->clearBit(i);
 
561
  if (!map->isClearAll())
550
562
    goto error4;
551
563
  return false;
552
564
error1:
569
581
  return true;
570
582
}
571
583
 
572
 
bool test_compare_operators(MY_BITMAP *map, uint32_t bitsize)
 
584
bool test_compare_operators(MyBitmap *map, uint32_t bitsize)
573
585
{
574
586
  uint32_t i, j, test_bit1, test_bit2, test_bit3,test_bit4;
575
587
  uint32_t no_loops= bitsize > 128 ? 128 : bitsize;
576
 
  MY_BITMAP map2_obj, map3_obj;
577
 
  MY_BITMAP *map2= &map2_obj, *map3= &map3_obj;
 
588
  MyBitmap map2_obj, map3_obj;
 
589
  MyBitmap *map2= &map2_obj, *map3= &map3_obj;
578
590
  my_bitmap_map map2buf[1024];
579
591
  my_bitmap_map map3buf[1024];
580
 
  bitmap_init(&map2_obj, map2buf, bitsize);
581
 
  bitmap_init(&map3_obj, map3buf, bitsize);
582
 
  bitmap_clear_all(map2);
583
 
  bitmap_clear_all(map3);
 
592
  map2_obj.init(map2buf, bitsize);
 
593
  map3_obj.init(map3buf, bitsize);
 
594
  map2->clearAll();
 
595
  map3->clearAll();
584
596
  for (i=0; i < no_loops; i++)
585
597
  {
586
598
    test_bit1=get_rand_bit(bitsize);
587
 
    bitmap_set_prefix(map, test_bit1);
 
599
    map->setPrefix(test_bit1);
588
600
    test_bit2=get_rand_bit(bitsize);
589
 
    bitmap_set_prefix(map2, test_bit2);
 
601
    map2->setPrefix(test_bit2);
590
602
    bitmap_intersect(map, map2);
591
603
    test_bit3= test_bit2 < test_bit1 ? test_bit2 : test_bit1;
592
 
    bitmap_set_prefix(map3, test_bit3);
 
604
    map3->setPrefix(test_bit3);
593
605
    if (!bitmap_cmp(map, map3))
594
606
      goto error1;
595
 
    bitmap_clear_all(map);
596
 
    bitmap_clear_all(map2);
597
 
    bitmap_clear_all(map3);
 
607
    map->clearAll();
 
608
    map2->clearAll();
 
609
    map3->clearAll();
598
610
    test_bit1=get_rand_bit(bitsize);
599
611
    test_bit2=get_rand_bit(bitsize);
600
612
    test_bit3=get_rand_bit(bitsize);
601
 
    bitmap_set_prefix(map, test_bit1);
602
 
    bitmap_set_prefix(map2, test_bit2);
 
613
    map->setPrefix(test_bit1);
 
614
    map2->setPrefix(test_bit2);
603
615
    test_bit3= test_bit2 > test_bit1 ? test_bit2 : test_bit1;
604
 
    bitmap_set_prefix(map3, test_bit3);
 
616
    map3->setPrefix(test_bit3);
605
617
    bitmap_union(map, map2);
606
618
    if (!bitmap_cmp(map, map3))
607
619
      goto error2;
608
 
    bitmap_clear_all(map);
609
 
    bitmap_clear_all(map2);
610
 
    bitmap_clear_all(map3);
 
620
    map->clearAll();
 
621
    map2->clearAll();
 
622
    map3->clearAll();
611
623
    test_bit1=get_rand_bit(bitsize);
612
624
    test_bit2=get_rand_bit(bitsize);
613
625
    test_bit3=get_rand_bit(bitsize);
614
 
    bitmap_set_prefix(map, test_bit1);
615
 
    bitmap_set_prefix(map2, test_bit2);
 
626
    map->setPrefix(test_bit1);
 
627
    map2->setPrefix(test_bit2);
616
628
    bitmap_xor(map, map2);
617
629
    test_bit3= test_bit2 > test_bit1 ? test_bit2 : test_bit1;
618
630
    test_bit4= test_bit2 < test_bit1 ? test_bit2 : test_bit1;
619
 
    bitmap_set_prefix(map3, test_bit3);
 
631
    map3->setPrefix(test_bit3);
620
632
    for (j=0; j < test_bit4; j++)
621
 
      bitmap_clear_bit(map3, j);
 
633
      map3->clearBit(j);
622
634
    if (!bitmap_cmp(map, map3))
623
635
      goto error3;
624
 
    bitmap_clear_all(map);
625
 
    bitmap_clear_all(map2);
626
 
    bitmap_clear_all(map3);
 
636
    map->clearAll();
 
637
    map2->clearAll();
 
638
    map3->clearAll();
627
639
    test_bit1=get_rand_bit(bitsize);
628
640
    test_bit2=get_rand_bit(bitsize);
629
641
    test_bit3=get_rand_bit(bitsize);
630
 
    bitmap_set_prefix(map, test_bit1);
631
 
    bitmap_set_prefix(map2, test_bit2);
 
642
    map->setPrefix(test_bit1);
 
643
    map2->setPrefix(test_bit2);
632
644
    bitmap_subtract(map, map2);
633
645
    if (test_bit2 < test_bit1)
634
646
    {
635
 
      bitmap_set_prefix(map3, test_bit1);
 
647
      map3->setPrefix(test_bit1);
636
648
      for (j=0; j < test_bit2; j++)
637
 
        bitmap_clear_bit(map3, j);
 
649
        map3->clearBit(j);
638
650
    }
639
651
    if (!bitmap_cmp(map, map3))
640
652
      goto error4;
641
 
    bitmap_clear_all(map);
642
 
    bitmap_clear_all(map2);
643
 
    bitmap_clear_all(map3);
 
653
    map->clearAll();
 
654
    map2->clearAll();
 
655
    map3->clearAll();
644
656
    test_bit1=get_rand_bit(bitsize);
645
 
    bitmap_set_prefix(map, test_bit1);
 
657
    map->setPrefix(test_bit1);
646
658
    bitmap_invert(map);
647
 
    bitmap_set_all(map3);
 
659
    map3->setAll();
648
660
    for (j=0; j < test_bit1; j++)
649
 
      bitmap_clear_bit(map3, j);
 
661
      map3->clearBit(j);
650
662
    if (!bitmap_cmp(map, map3))
651
663
      goto error5;
652
 
    bitmap_clear_all(map);
653
 
    bitmap_clear_all(map3);
 
664
    map->clearAll();
 
665
    map3->clearAll();
654
666
  }
655
667
  return false;
656
668
error1:
675
687
  return true;
676
688
}
677
689
 
678
 
bool test_count_bits_set(MY_BITMAP *map, uint32_t bitsize)
 
690
bool test_count_bits_set(MyBitmap *map, uint32_t bitsize)
679
691
{
680
692
  uint32_t i, bit_count=0, test_bit;
681
693
  uint32_t no_loops= bitsize > 128 ? 128 : bitsize;
682
694
  for (i=0; i < no_loops; i++)
683
695
  {
684
696
    test_bit=get_rand_bit(bitsize);
685
 
    if (!bitmap_is_set(map, test_bit))
 
697
    if (!map->isBitSet(test_bit))
686
698
    {
687
 
      bitmap_set_bit(map, test_bit);
 
699
      map->setBit(test_bit);
688
700
      bit_count++;
689
701
    }
690
702
  }
691
703
  if (bit_count==0 && bitsize > 0)
692
704
    goto error1;
693
 
  if (bitmap_bits_set(map) != bit_count)
 
705
  if (getBitsSet() != bit_count)
694
706
    goto error2;
695
707
  return false;
696
708
error1:
701
713
  return true;
702
714
}
703
715
 
704
 
bool test_get_first_bit(MY_BITMAP *map, uint32_t bitsize)
 
716
bool test_get_first_bit(MyBitmap *map, uint32_t bitsize)
705
717
{
706
718
  uint32_t i, test_bit;
707
719
  uint32_t no_loops= bitsize > 128 ? 128 : bitsize;
708
720
  for (i=0; i < no_loops; i++)
709
721
  {
710
722
    test_bit=get_rand_bit(bitsize);
711
 
    bitmap_set_bit(map, test_bit);
 
723
    map->setBit(test_bit);
712
724
    if (bitmap_get_first_set(map) != test_bit)
713
725
      goto error1;
714
 
    bitmap_set_all(map);
715
 
    bitmap_clear_bit(map, test_bit);
716
 
    if (bitmap_get_first(map) != test_bit)
 
726
    map->setAll();
 
727
    map->clearBit(test_bit);
 
728
    if (getFirst() != test_bit)
717
729
      goto error2;
718
 
    bitmap_clear_all(map);
 
730
    map->clearAll();
719
731
  }
720
732
  return false;
721
733
error1:
726
738
  return true;
727
739
}
728
740
 
729
 
bool test_get_next_bit(MY_BITMAP *map, uint32_t bitsize)
 
741
bool test_get_next_bit(MyBitmap *map, uint32_t bitsize)
730
742
{
731
743
  uint32_t i, j, test_bit;
732
744
  uint32_t no_loops= bitsize > 128 ? 128 : bitsize;
734
746
  {
735
747
    test_bit=get_rand_bit(bitsize);
736
748
    for (j=0; j < test_bit; j++)
737
 
      bitmap_set_next(map);
738
 
    if (!bitmap_is_prefix(map, test_bit))
 
749
      setNext();
 
750
    if (!map->isPrefix(test_bit))
739
751
      goto error1;
740
 
    bitmap_clear_all(map);
 
752
    map->clearAll();
741
753
  }
742
754
  return false;
743
755
error1:
745
757
  return true;
746
758
}
747
759
 
748
 
bool test_prefix(MY_BITMAP *map, uint32_t bitsize)
 
760
bool test_prefix(MyBitmap *map, uint32_t bitsize)
749
761
{
750
762
  uint32_t i, j, test_bit;
751
763
  uint32_t no_loops= bitsize > 128 ? 128 : bitsize;
752
764
  for (i=0; i < no_loops; i++)
753
765
  {
754
766
    test_bit=get_rand_bit(bitsize);
755
 
    bitmap_set_prefix(map, test_bit);
756
 
    if (!bitmap_is_prefix(map, test_bit))
 
767
    map->setPrefix(map, test_bit);
 
768
    if (!map->isPrefix(test_bit))
757
769
      goto error1;
758
 
    bitmap_clear_all(map);
 
770
    map->clearAll();
759
771
    for (j=0; j < test_bit; j++)
760
 
      bitmap_set_bit(map, j);
761
 
    if (!bitmap_is_prefix(map, test_bit))
 
772
      map->setBit(j);
 
773
    if (!map->isPrefix(test_bit))
762
774
      goto error2;
763
 
    bitmap_set_all(map);
 
775
    map->setAll();
764
776
    for (j=bitsize - 1; ~(j-test_bit); j--)
765
 
      bitmap_clear_bit(map, j);
766
 
    if (!bitmap_is_prefix(map, test_bit))
 
777
      map->clearBit(j);
 
778
    if (!map->isPrefix(test_bit))
767
779
      goto error3;
768
 
    bitmap_clear_all(map);
 
780
    map->clearAll();
769
781
  }
770
782
  return false;
771
783
error1:
782
794
 
783
795
bool do_test(uint32_t bitsize)
784
796
{
785
 
  MY_BITMAP map;
 
797
  MyBitmap map;
786
798
  my_bitmap_map buf[1024];
787
 
  if (bitmap_init(&map, buf, bitsize))
 
799
  if (map.init(buf, bitsize))
788
800
  {
789
801
    printf("init error for bitsize %d", bitsize);
790
802
    goto error;
791
803
  }
792
804
  if (test_set_get_clear_bit(&map,bitsize))
793
805
    goto error;
794
 
  bitmap_clear_all(&map);
 
806
  map.clearAll();
795
807
  if (test_flip_bit(&map,bitsize))
796
808
    goto error;
797
 
  bitmap_clear_all(&map);
 
809
  map.clearAll();
798
810
  if (test_operators(&map,bitsize))
799
811
    goto error;
800
 
  bitmap_clear_all(&map);
 
812
  map.clearAll();
801
813
  if (test_get_all_bits(&map, bitsize))
802
814
    goto error;
803
 
  bitmap_clear_all(&map);
 
815
  map.clearAll();
804
816
  if (test_compare_operators(&map,bitsize))
805
817
    goto error;
806
 
  bitmap_clear_all(&map);
 
818
  map.clearAll();
807
819
  if (test_count_bits_set(&map,bitsize))
808
820
    goto error;
809
 
  bitmap_clear_all(&map);
 
821
  map.clearAll();
810
822
  if (test_get_first_bit(&map,bitsize))
811
823
    goto error;
812
 
  bitmap_clear_all(&map);
 
824
  map.clearAll();
813
825
  if (test_get_next_bit(&map,bitsize))
814
826
    goto error;
815
827
  if (test_prefix(&map,bitsize))