← Back to branch summary

~ubuntu-branches/ubuntu/precise/mysql-5.5/precise-201203300109

« back to all changes in this revision

Viewing changes to mysys/my_bitmap.c

  • Committer: Package Import Robot
  • Author(s): Clint Byrum
  • Date: 2011-11-08 11:31:13 UTC
  • Revision ID: package-import@ubuntu.com-20111108113113-3ulw01fvi4vn8m25
Tags: upstream-5.5.17
Import upstream version 5.5.17

Show diffs side-by-side

added added

removed removed

Lines of Context:
mysys/my_bitmap.c
 
1
/*
 
2
   Copyright (c) 2001, 2011, 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 as published by
 
6
   the Free Software Foundation; version 2 of the License.
 
7
 
 
8
   This program is distributed in the hope that it will be useful,
 
9
   but WITHOUT ANY WARRANTY; without even the implied warranty of
 
10
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 
11
   GNU General Public License for more details.
 
12
 
 
13
   You should have received a copy of the GNU General Public License
 
14
   along with this program; if not, write to the Free Software
 
15
   Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA */
 
16
 
 
17
/*
 
18
  Handling of uchar arrays as large bitmaps.
 
19
 
 
20
  API limitations (or, rather asserted safety assumptions,
 
21
  to encourage correct programming)
 
22
 
 
23
    * the internal size is a set of 32 bit words
 
24
    * the number of bits specified in creation can be any number > 0
 
25
    * there are THREAD safe versions of most calls called bitmap_lock_*
 
26
 
 
27
  TODO:
 
28
  Make assembler THREAD safe versions of these using test-and-set instructions
 
29
 
 
30
  Original version created by Sergei Golubchik 2001 - 2004.
 
31
  New version written and test program added and some changes to the interface
 
32
  was made by Mikael Ronström 2005, with assistance of Tomas Ulin and Mats
 
33
  Kindahl.
 
34
*/
 
35
 
 
36
#include "mysys_priv.h"
 
37
#include <my_bitmap.h>
 
38
#include <m_string.h>
 
39
#include <my_bit.h>
 
40
 
 
41
void create_last_word_mask(MY_BITMAP *map)
 
42
{
 
43
  /* Get the number of used bits (1..8) in the last byte */
 
44
  unsigned int const used= 1U + ((map->n_bits-1U) & 0x7U);
 
45
 
 
46
  /*
 
47
    Create a mask with the upper 'unused' bits set and the lower 'used'
 
48
    bits clear. The bits within each byte is stored in big-endian order.
 
49
   */
 
50
  unsigned char const mask= (~((1 << used) - 1)) & 255;
 
51
 
 
52
  /*
 
53
    The first bytes are to be set to zero since they represent real  bits
 
54
    in the bitvector. The last bytes are set to 0xFF since they  represent
 
55
    bytes not used by the bitvector. Finally the last byte contains  bits
 
56
    as set by the mask above.
 
57
  */
 
58
  unsigned char *ptr= (unsigned char*)&map->last_word_mask;
 
59
 
 
60
  map->last_word_ptr= map->bitmap + no_words_in_map(map)-1;
 
61
  switch (no_bytes_in_map(map) & 3) {
 
62
  case 1:
 
63
    map->last_word_mask= ~0U;
 
64
    ptr[0]= mask;
 
65
    return;
 
66
  case 2:
 
67
    map->last_word_mask= ~0U;
 
68
    ptr[0]= 0;
 
69
    ptr[1]= mask;
 
70
    return;
 
71
  case 3:
 
72
    map->last_word_mask= 0U;
 
73
    ptr[2]= mask;
 
74
    ptr[3]= 0xFFU;
 
75
    return;
 
76
  case 0:
 
77
    map->last_word_mask= 0U;
 
78
    ptr[3]= mask;
 
79
    return;
 
80
  }
 
81
}
 
82
 
 
83
 
 
84
static inline void bitmap_lock(MY_BITMAP *map __attribute__((unused)))
 
85
{
 
86
  if (map->mutex)
 
87
    mysql_mutex_lock(map->mutex);
 
88
}
 
89
 
 
90
 
 
91
static inline void bitmap_unlock(MY_BITMAP *map __attribute__((unused)))
 
92
{
 
93
  if (map->mutex)
 
94
    mysql_mutex_unlock(map->mutex);
 
95
}
 
96
 
 
97
 
 
98
static inline uint get_first_set(uint32 value, uint word_pos)
 
99
{
 
100
  uchar *byte_ptr= (uchar*)&value;
 
101
  uchar byte_value;
 
102
  uint byte_pos, bit_pos;
 
103
 
 
104
  for (byte_pos=0; byte_pos < 4; byte_pos++, byte_ptr++)
 
105
  {
 
106
    byte_value= *byte_ptr;
 
107
    if (byte_value)
 
108
    {
 
109
      for (bit_pos=0; ; bit_pos++)
 
110
        if (byte_value & (1 << bit_pos))
 
111
          return (word_pos*32) + (byte_pos*8) + bit_pos;
 
112
    }
 
113
  }
 
114
  return MY_BIT_NONE;
 
115
}
 
116
 
 
117
 
 
118
static inline uint get_first_not_set(uint32 value, uint word_pos)
 
119
{
 
120
  uchar *byte_ptr= (uchar*)&value;
 
121
  uchar byte_value;
 
122
  uint byte_pos, bit_pos;
 
123
 
 
124
  for (byte_pos=0; byte_pos < 4; byte_pos++, byte_ptr++)
 
125
  {
 
126
    byte_value= *byte_ptr;
 
127
    if (byte_value != 0xFF)
 
128
    {
 
129
      for (bit_pos=0; ; bit_pos++)
 
130
        if (!(byte_value & (1 << bit_pos)))
 
131
          return (word_pos*32) + (byte_pos*8) + bit_pos;
 
132
    }
 
133
  }
 
134
  return MY_BIT_NONE;
 
135
}
 
136
 
 
137
 
 
138
my_bool bitmap_init(MY_BITMAP *map, my_bitmap_map *buf, uint n_bits,
 
139
                    my_bool thread_safe __attribute__((unused)))
 
140
{
 
141
  DBUG_ENTER("bitmap_init");
 
142
  if (!buf)
 
143
  {
 
144
    uint size_in_bytes= bitmap_buffer_size(n_bits);
 
145
    uint extra= 0;
 
146
 
 
147
    if (thread_safe)
 
148
    {
 
149
      size_in_bytes= ALIGN_SIZE(size_in_bytes);
 
150
      extra= sizeof(mysql_mutex_t);
 
151
    }
 
152
    map->mutex= 0;
 
153
 
 
154
    if (!(buf= (my_bitmap_map*) my_malloc(size_in_bytes+extra, MYF(MY_WME))))
 
155
      DBUG_RETURN(1);
 
156
 
 
157
    if (thread_safe)
 
158
    {
 
159
      map->mutex= (mysql_mutex_t *) ((char*) buf + size_in_bytes);
 
160
      mysql_mutex_init(key_BITMAP_mutex, map->mutex, MY_MUTEX_INIT_FAST);
 
161
    }
 
162
 
 
163
  }
 
164
 
 
165
  else
 
166
  {
 
167
    DBUG_ASSERT(thread_safe == 0);
 
168
  }
 
169
 
 
170
 
 
171
  map->bitmap= buf;
 
172
  map->n_bits= n_bits;
 
173
  create_last_word_mask(map);
 
174
  bitmap_clear_all(map);
 
175
  DBUG_RETURN(0);
 
176
}
 
177
 
 
178
 
 
179
void bitmap_free(MY_BITMAP *map)
 
180
{
 
181
  DBUG_ENTER("bitmap_free");
 
182
  if (map->bitmap)
 
183
  {
 
184
    if (map->mutex)
 
185
      mysql_mutex_destroy(map->mutex);
 
186
 
 
187
    my_free(map->bitmap);
 
188
    map->bitmap=0;
 
189
  }
 
190
  DBUG_VOID_RETURN;
 
191
}
 
192
 
 
193
 
 
194
/*
 
195
  test if bit already set and set it if it was not (thread unsafe method)
 
196
 
 
197
  SYNOPSIS
 
198
    bitmap_fast_test_and_set()
 
199
    MAP   bit map struct
 
200
    BIT   bit number
 
201
 
 
202
  RETURN
 
203
    0    bit was not set
 
204
    !=0  bit was set
 
205
*/
 
206
 
 
207
my_bool bitmap_fast_test_and_set(MY_BITMAP *map, uint bitmap_bit)
 
208
{
 
209
  uchar *value= ((uchar*) map->bitmap) + (bitmap_bit / 8);
 
210
  uchar bit= 1 << ((bitmap_bit) & 7);
 
211
  uchar res= (*value) & bit;
 
212
  *value|= bit;
 
213
  return res;
 
214
}
 
215
 
 
216
 
 
217
/*
 
218
  test if bit already set and set it if it was not (thread safe method)
 
219
 
 
220
  SYNOPSIS
 
221
    bitmap_fast_test_and_set()
 
222
    map          bit map struct
 
223
    bitmap_bit   bit number
 
224
 
 
225
  RETURN
 
226
    0    bit was not set
 
227
    !=0  bit was set
 
228
*/
 
229
 
 
230
my_bool bitmap_test_and_set(MY_BITMAP *map, uint bitmap_bit)
 
231
{
 
232
  my_bool res;
 
233
  DBUG_ASSERT(map->bitmap && bitmap_bit < map->n_bits);
 
234
  bitmap_lock(map);
 
235
  res= bitmap_fast_test_and_set(map, bitmap_bit);
 
236
  bitmap_unlock(map);
 
237
  return res;
 
238
}
 
239
 
 
240
/*
 
241
  test if bit already set and clear it if it was set(thread unsafe method)
 
242
 
 
243
  SYNOPSIS
 
244
    bitmap_fast_test_and_set()
 
245
    MAP   bit map struct
 
246
    BIT   bit number
 
247
 
 
248
  RETURN
 
249
    0    bit was not set
 
250
    !=0  bit was set
 
251
*/
 
252
 
 
253
my_bool bitmap_fast_test_and_clear(MY_BITMAP *map, uint bitmap_bit)
 
254
{
 
255
  uchar *byte= (uchar*) map->bitmap + (bitmap_bit / 8);
 
256
  uchar bit= 1 << ((bitmap_bit) & 7);
 
257
  uchar res= (*byte) & bit;
 
258
  *byte&= ~bit;
 
259
  return res;
 
260
}
 
261
 
 
262
 
 
263
my_bool bitmap_test_and_clear(MY_BITMAP *map, uint bitmap_bit)
 
264
{
 
265
  my_bool res;
 
266
  DBUG_ASSERT(map->bitmap && bitmap_bit < map->n_bits);
 
267
  bitmap_lock(map);
 
268
  res= bitmap_fast_test_and_clear(map, bitmap_bit);
 
269
  bitmap_unlock(map);
 
270
  return res;
 
271
}
 
272
 
 
273
 
 
274
uint bitmap_set_next(MY_BITMAP *map)
 
275
{
 
276
  uint bit_found;
 
277
  DBUG_ASSERT(map->bitmap);
 
278
  if ((bit_found= bitmap_get_first(map)) != MY_BIT_NONE)
 
279
    bitmap_set_bit(map, bit_found);
 
280
  return bit_found;
 
281
}
 
282
 
 
283
 
 
284
void bitmap_set_prefix(MY_BITMAP *map, uint prefix_size)
 
285
{
 
286
  uint prefix_bytes, prefix_bits, d;
 
287
  uchar *m= (uchar *)map->bitmap;
 
288
 
 
289
  DBUG_ASSERT(map->bitmap &&
 
290
              (prefix_size <= map->n_bits || prefix_size == (uint) ~0));
 
291
  set_if_smaller(prefix_size, map->n_bits);
 
292
  if ((prefix_bytes= prefix_size / 8))
 
293
    memset(m, 0xff, prefix_bytes);
 
294
  m+= prefix_bytes;
 
295
  if ((prefix_bits= prefix_size & 7))
 
296
    *(m++)= (1 << prefix_bits)-1;
 
297
  if ((d= no_bytes_in_map(map)-prefix_bytes))
 
298
    bzero(m, d);
 
299
}
 
300
 
 
301
 
 
302
my_bool bitmap_is_prefix(const MY_BITMAP *map, uint prefix_size)
 
303
{
 
304
  uint prefix_bits= prefix_size % 32;
 
305
  my_bitmap_map *word_ptr= map->bitmap, last_word;
 
306
  my_bitmap_map *end_prefix= word_ptr + prefix_size / 32;
 
307
  DBUG_ASSERT(word_ptr && prefix_size <= map->n_bits);
 
308
 
 
309
  /* 1: Words that should be filled with 1 */
 
310
  for (; word_ptr < end_prefix; word_ptr++)
 
311
    if (*word_ptr != 0xFFFFFFFF)
 
312
      return FALSE;
 
313
 
 
314
  last_word= *map->last_word_ptr & ~map->last_word_mask;
 
315
 
 
316
  /* 2: Word which contains the end of the prefix (if any) */
 
317
  if (prefix_bits)
 
318
  {
 
319
    if (word_ptr == map->last_word_ptr)
 
320
      return uint4korr((uchar*)&last_word) == (uint32)((1 << prefix_bits) - 1);
 
321
    else if (uint4korr((uchar*)word_ptr) != (uint32)((1 << prefix_bits) - 1))
 
322
      return FALSE;
 
323
    word_ptr++;
 
324
  }
 
325
 
 
326
  /* 3: Words that should be filled with 0 */
 
327
  for (; word_ptr < map->last_word_ptr; word_ptr++)
 
328
    if (*word_ptr != 0)
 
329
      return FALSE;
 
330
 
 
331
  /*
 
332
    We can end up here in two situations:
 
333
    1) We went through the whole bitmap in step 1. This will happen if the
 
334
       whole bitmap is filled with 1 and prefix_size is a multiple of 32
 
335
       (i.e. the prefix does not end in the middle of a word).
 
336
       In this case word_ptr will be larger than map->last_word_ptr.
 
337
    2) We have gone through steps 1-3 and just need to check that also
 
338
       the last word is 0.
 
339
  */
 
340
  return word_ptr > map->last_word_ptr || last_word == 0;
 
341
}
 
342
 
 
343
 
 
344
my_bool bitmap_is_set_all(const MY_BITMAP *map)
 
345
{
 
346
  my_bitmap_map *data_ptr= map->bitmap;
 
347
  my_bitmap_map *end= map->last_word_ptr;
 
348
 
 
349
  for (; data_ptr < end; data_ptr++)
 
350
    if (*data_ptr != 0xFFFFFFFF)
 
351
      return FALSE;
 
352
  if ((*map->last_word_ptr | map->last_word_mask) != 0xFFFFFFFF)
 
353
    return FALSE;
 
354
  return TRUE;
 
355
}
 
356
 
 
357
 
 
358
my_bool bitmap_is_clear_all(const MY_BITMAP *map)
 
359
{
 
360
  my_bitmap_map *data_ptr= map->bitmap;
 
361
  my_bitmap_map *end= map->last_word_ptr;
 
362
 
 
363
  for (; data_ptr < end; data_ptr++)
 
364
    if (*data_ptr)
 
365
      return FALSE;
 
366
  if (*map->last_word_ptr & ~map->last_word_mask)
 
367
    return FALSE;
 
368
  return TRUE;
 
369
}
 
370
 
 
371
/* Return TRUE if map1 is a subset of map2 */
 
372
 
 
373
my_bool bitmap_is_subset(const MY_BITMAP *map1, const MY_BITMAP *map2)
 
374
{
 
375
  my_bitmap_map *m1= map1->bitmap, *m2= map2->bitmap, *end;
 
376
 
 
377
  DBUG_ASSERT(map1->bitmap && map2->bitmap &&
 
378
              map1->n_bits==map2->n_bits);
 
379
 
 
380
  end= map1->last_word_ptr;
 
381
  for (; m1 < end; m1++, m2++)
 
382
    if (*m1 & ~(*m2))
 
383
      return FALSE;
 
384
 
 
385
  if ((*map1->last_word_ptr & ~map1->last_word_mask) &
 
386
      ~(*map2->last_word_ptr & ~map2->last_word_mask))
 
387
    return FALSE;
 
388
  return TRUE;
 
389
}
 
390
 
 
391
/* True if bitmaps has any common bits */
 
392
 
 
393
my_bool bitmap_is_overlapping(const MY_BITMAP *map1, const MY_BITMAP *map2)
 
394
{
 
395
  my_bitmap_map *m1= map1->bitmap, *m2= map2->bitmap, *end;
 
396
 
 
397
  DBUG_ASSERT(map1->bitmap && map2->bitmap &&
 
398
              map1->n_bits==map2->n_bits);
 
399
 
 
400
  end= map1->last_word_ptr;
 
401
  for (; m1 < end; m1++, m2++)
 
402
    if (*m1 & *m2)
 
403
      return TRUE;
 
404
 
 
405
  if ((*map1->last_word_ptr & ~map1->last_word_mask) &
 
406
      (*map2->last_word_ptr & ~map2->last_word_mask))
 
407
    return TRUE;
 
408
  return FALSE;
 
409
}
 
410
 
 
411
 
 
412
void bitmap_intersect(MY_BITMAP *map, const MY_BITMAP *map2)
 
413
{
 
414
  my_bitmap_map *to= map->bitmap, *from= map2->bitmap, *end;
 
415
  uint len= no_words_in_map(map), len2 = no_words_in_map(map2);
 
416
 
 
417
  DBUG_ASSERT(map->bitmap && map2->bitmap);
 
418
 
 
419
  end= to+min(len,len2);
 
420
  for (; to < end; to++, from++)
 
421
    *to &= *from;
 
422
 
 
423
  if (len >= len2)
 
424
    map->bitmap[len2 - 1] &= ~map2->last_word_mask;
 
425
 
 
426
  if (len2 < len)
 
427
  {
 
428
    end+=len-len2;
 
429
    for (; to < end; to++)
 
430
      *to= 0;
 
431
  }
 
432
}
 
433
 
 
434
 
 
435
/*
 
436
  Set/clear all bits above a bit.
 
437
 
 
438
  SYNOPSIS
 
439
    bitmap_set_above()
 
440
    map                  RETURN The bitmap to change.
 
441
    from_byte                   The bitmap buffer byte offset to start with.
 
442
    use_bit                     The bit value (1/0) to use for all upper bits.
 
443
 
 
444
  NOTE
 
445
    You can only set/clear full bytes.
 
446
    The function is meant for the situation that you copy a smaller bitmap
 
447
    to a bigger bitmap. Bitmap lengths are always multiple of eigth (the
 
448
    size of a byte). Using 'from_byte' saves multiplication and division
 
449
    by eight during parameter passing.
 
450
 
 
451
  RETURN
 
452
    void
 
453
*/
 
454
 
 
455
void bitmap_set_above(MY_BITMAP *map, uint from_byte, uint use_bit)
 
456
{
 
457
  uchar use_byte= use_bit ? 0xff : 0;
 
458
  uchar *to= (uchar *)map->bitmap + from_byte;
 
459
  uchar *end= (uchar *)map->bitmap + (map->n_bits+7)/8;
 
460
 
 
461
  for (; to < end; to++)
 
462
    *to= use_byte;
 
463
}
 
464
 
 
465
 
 
466
void bitmap_subtract(MY_BITMAP *map, const MY_BITMAP *map2)
 
467
{
 
468
  my_bitmap_map *to= map->bitmap, *from= map2->bitmap, *end;
 
469
  DBUG_ASSERT(map->bitmap && map2->bitmap &&
 
470
              map->n_bits==map2->n_bits);
 
471
  end= map->last_word_ptr;
 
472
 
 
473
  for (; to <= end; to++, from++)
 
474
    *to &= ~(*from);
 
475
}
 
476
 
 
477
 
 
478
void bitmap_union(MY_BITMAP *map, const MY_BITMAP *map2)
 
479
{
 
480
  my_bitmap_map *to= map->bitmap, *from= map2->bitmap, *end;
 
481
  DBUG_ASSERT(map->bitmap && map2->bitmap &&
 
482
              map->n_bits==map2->n_bits);
 
483
  end= map->last_word_ptr;
 
484
 
 
485
  for (; to <= end; to++, from++)
 
486
    *to |= *from;
 
487
}
 
488
 
 
489
 
 
490
void bitmap_xor(MY_BITMAP *map, const MY_BITMAP *map2)
 
491
{
 
492
  my_bitmap_map *to= map->bitmap, *from= map2->bitmap, *end;
 
493
  DBUG_ASSERT(map->bitmap && map2->bitmap &&
 
494
              map->n_bits==map2->n_bits);
 
495
  end= map->last_word_ptr;
 
496
 
 
497
  for (; to <= end; to++, from++)
 
498
    *to ^= *from;
 
499
}
 
500
 
 
501
 
 
502
void bitmap_invert(MY_BITMAP *map)
 
503
{
 
504
  my_bitmap_map *to= map->bitmap, *end;
 
505
  DBUG_ASSERT(map->bitmap);
 
506
  end= map->last_word_ptr;
 
507
 
 
508
  for (; to <= end; to++)
 
509
    *to ^= 0xFFFFFFFF;
 
510
}
 
511
 
 
512
 
 
513
uint bitmap_bits_set(const MY_BITMAP *map)
 
514
{
 
515
  my_bitmap_map *data_ptr= map->bitmap;
 
516
  my_bitmap_map *end= map->last_word_ptr;
 
517
  uint res= 0;
 
518
  DBUG_ASSERT(map->bitmap);
 
519
 
 
520
  for (; data_ptr < end; data_ptr++)
 
521
    res+= my_count_bits_uint32(*data_ptr);
 
522
 
 
523
  /*Reset last bits to zero*/
 
524
  res+= my_count_bits_uint32(*map->last_word_ptr & ~map->last_word_mask);
 
525
  return res;
 
526
}
 
527
 
 
528
 
 
529
void bitmap_copy(MY_BITMAP *map, const MY_BITMAP *map2)
 
530
{
 
531
  my_bitmap_map *to= map->bitmap, *from= map2->bitmap, *end;
 
532
  DBUG_ASSERT(map->bitmap && map2->bitmap &&
 
533
              map->n_bits==map2->n_bits);
 
534
  end= map->last_word_ptr;
 
535
 
 
536
  for (; to <= end; to++, from++)
 
537
    *to = *from;
 
538
}
 
539
 
 
540
 
 
541
uint bitmap_get_first_set(const MY_BITMAP *map)
 
542
{
 
543
  uint word_pos;
 
544
  my_bitmap_map *data_ptr, *end= map->last_word_ptr;
 
545
 
 
546
  DBUG_ASSERT(map->bitmap);
 
547
  data_ptr= map->bitmap;
 
548
 
 
549
  for (word_pos=0; data_ptr < end; data_ptr++, word_pos++)
 
550
    if (*data_ptr)
 
551
      return get_first_set(*data_ptr, word_pos);
 
552
 
 
553
  return get_first_set(*map->last_word_ptr & ~map->last_word_mask, word_pos);
 
554
}
 
555
 
 
556
 
 
557
uint bitmap_get_first(const MY_BITMAP *map)
 
558
{
 
559
  uint word_pos;
 
560
  my_bitmap_map *data_ptr, *end= map->last_word_ptr;
 
561
 
 
562
  DBUG_ASSERT(map->bitmap);
 
563
  data_ptr= map->bitmap;
 
564
 
 
565
  for (word_pos=0; data_ptr < end; data_ptr++, word_pos++)
 
566
    if (*data_ptr != 0xFFFFFFFF)
 
567
      return get_first_not_set(*data_ptr, word_pos);
 
568
 
 
569
  return get_first_not_set(*map->last_word_ptr | map->last_word_mask, word_pos);
 
570
}
 
571
 
 
572
 
 
573
uint bitmap_lock_set_next(MY_BITMAP *map)
 
574
{
 
575
  uint bit_found;
 
576
  bitmap_lock(map);
 
577
  bit_found= bitmap_set_next(map);
 
578
  bitmap_unlock(map);
 
579
  return bit_found;
 
580
}
 
581
 
 
582
 
 
583
void bitmap_lock_clear_bit(MY_BITMAP *map, uint bitmap_bit)
 
584
{
 
585
  bitmap_lock(map);
 
586
  DBUG_ASSERT(map->bitmap && bitmap_bit < map->n_bits);
 
587
  bitmap_clear_bit(map, bitmap_bit);
 
588
  bitmap_unlock(map);
 
589
}