1/*
2 Copyright (c) 2001, 2011, Oracle and/or its affiliates.
3 Copyright (C) 2009- 2011 Monty Program Ab
4
5 This program is free software; you can redistribute it and/or modify
6 it under the terms of the GNU General Public License as published by
7 the Free Software Foundation; version 2 of the License.
8
9 This program is distributed in the hope that it will be useful,
10 but WITHOUT ANY WARRANTY; without even the implied warranty of
11 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 GNU General Public License for more details.
13
14 You should have received a copy of the GNU General Public License
15 along with this program; if not, write to the Free Software
16 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA */
17
18/*
19 Handling of uchar arrays as large bitmaps.
20
21 API limitations (or, rather asserted safety assumptions,
22 to encourage correct programming)
23
24 * the internal size is a set of 32 bit words
25 * the number of bits specified in creation can be any number > 0
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 Ronstrom 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
42/* Create a mask of the significant bits for the last byte (1,3,7,..255) */
43
44static inline uchar last_byte_mask(uint bits)
45{
46 /* Get the number of used bits-1 (0..7) in the last byte */
47 unsigned int const used= (bits - 1U) & 7U;
48 /* Return bitmask for the significant bits */
49 return ((2U << used) - 1);
50}
51
52/*
53 Create a mask with the upper 'unused' bits set and the lower 'used'
54 bits clear. The bits within each byte is stored in big-endian order.
55*/
56
57static inline uchar invers_last_byte_mask(uint bits)
58{
59 return last_byte_mask(bits) ^ 255;
60}
61
62
63void create_last_word_mask(MY_BITMAP *map)
64{
65 unsigned char const mask= invers_last_byte_mask(map->n_bits);
66
67 /*
68 The first bytes are to be set to zero since they represent real bits
69 in the bitvector. The last bytes are set to 0xFF since they represent
70 bytes not used by the bitvector. Finally the last byte contains bits
71 as set by the mask above.
72 */
73 unsigned char *ptr= (unsigned char*)&map->last_word_mask;
74
75 map->last_word_ptr= map->bitmap + no_words_in_map(map)-1;
76 switch (no_bytes_in_map(map) & 3) {
77 case 1:
78 map->last_word_mask= ~0U;
79 ptr[0]= mask;
80 return;
81 case 2:
82 map->last_word_mask= ~0U;
83 ptr[0]= 0;
84 ptr[1]= mask;
85 return;
86 case 3:
87 map->last_word_mask= 0U;
88 ptr[2]= mask;
89 ptr[3]= 0xFFU;
90 return;
91 case 0:
92 map->last_word_mask= 0U;
93 ptr[3]= mask;
94 return;
95 }
96}
97
98
99static inline my_bitmap_map last_word_mask(uint bit)
100{
101 my_bitmap_map last_word_mask;
102 uint n_bits= bit + 1;
103 unsigned char const mask= invers_last_byte_mask(n_bits);
104
105 /*
106 The first bytes are to be set to zero since they represent real bits
107 in the bitvector. The last bytes are set to 0xFF since they represent
108 bytes not used by the bitvector. Finally the last byte contains bits
109 as set by the mask above.
110 */
111 unsigned char *ptr= (unsigned char*)&last_word_mask;
112
113 switch ((n_bits + 7)/8 & 3) {
114 case 1:
115 last_word_mask= ~0U;
116 ptr[0]= mask;
117 break;
118 case 2:
119 last_word_mask= ~0U;
120 ptr[0]= 0;
121 ptr[1]= mask;
122 break;
123 case 3:
124 last_word_mask= 0U;
125 ptr[2]= mask;
126 ptr[3]= 0xFFU;
127 break;
128 case 0:
129 last_word_mask= 0U;
130 ptr[3]= mask;
131 break;
132 }
133 return last_word_mask;
134}
135
136
137static inline void bitmap_lock(MY_BITMAP *map __attribute__((unused)))
138{
139 if (map->mutex)
140 mysql_mutex_lock(map->mutex);
141}
142
143static inline void bitmap_unlock(MY_BITMAP *map __attribute__((unused)))
144{
145 if (map->mutex)
146 mysql_mutex_unlock(map->mutex);
147}
148
149
150static inline uint get_first_set(my_bitmap_map value, uint word_pos)
151{
152 uchar *byte_ptr= (uchar*)&value;
153 uchar byte_value;
154 uint byte_pos, bit_pos;
155
156 DBUG_ASSERT(value);
157 for (byte_pos=0; ; byte_pos++, byte_ptr++)
158 {
159 if ((byte_value= *byte_ptr))
160 {
161 for (bit_pos=0; ; bit_pos++)
162 if (byte_value & (1 << bit_pos))
163 return (word_pos*32) + (byte_pos*8) + bit_pos;
164 }
165 }
166 return MY_BIT_NONE; /* Impossible */
167}
168
169/*
170 Initialize a bitmap object. All bits will be set to zero
171*/
172
173my_bool my_bitmap_init(MY_BITMAP *map, my_bitmap_map *buf, uint n_bits,
174 my_bool thread_safe)
175{
176 DBUG_ENTER("my_bitmap_init");
177 map->mutex= 0;
178 if (!buf)
179 {
180 uint size_in_bytes= bitmap_buffer_size(n_bits);
181 uint extra= 0;
182 if (thread_safe)
183 {
184 size_in_bytes= ALIGN_SIZE(size_in_bytes);
185 extra= sizeof(mysql_mutex_t);
186 }
187 if (!(buf= (my_bitmap_map*) my_malloc(size_in_bytes+extra, MYF(MY_WME))))
188 DBUG_RETURN(1);
189 if (thread_safe)
190 {
191 map->mutex= (mysql_mutex_t *) ((char*) buf + size_in_bytes);
192 mysql_mutex_init(key_BITMAP_mutex, map->mutex, MY_MUTEX_INIT_FAST);
193 }
194 }
195 else
196 {
197 DBUG_ASSERT(thread_safe == 0);
198 }
199
200 map->bitmap= buf;
201 map->n_bits= n_bits;
202 create_last_word_mask(map);
203 bitmap_clear_all(map);
204 DBUG_RETURN(0);
205}
206
207
208void my_bitmap_free(MY_BITMAP *map)
209{
210 DBUG_ENTER("my_bitmap_free");
211 if (map->bitmap)
212 {
213 if (map->mutex)
214 mysql_mutex_destroy(map->mutex);
215 my_free(map->bitmap);
216 map->bitmap=0;
217 }
218 DBUG_VOID_RETURN;
219}
220
221
222/*
223 test if bit already set and set it if it was not (thread unsafe method)
224
225 SYNOPSIS
226 bitmap_fast_test_and_set()
227 MAP bit map struct
228 BIT bit number
229
230 RETURN
231 0 bit was not set
232 !=0 bit was set
233*/
234
235my_bool bitmap_fast_test_and_set(MY_BITMAP *map, uint bitmap_bit)
236{
237 uchar *value= ((uchar*) map->bitmap) + (bitmap_bit / 8);
238 uchar bit= 1 << ((bitmap_bit) & 7);
239 uchar res= (*value) & bit;
240 *value|= bit;
241 return res;
242}
243
244
245/*
246 test if bit already set and set it if it was not (thread safe method)
247
248 SYNOPSIS
249 bitmap_fast_test_and_set()
250 map bit map struct
251 bitmap_bit bit number
252
253 RETURN
254 0 bit was not set
255 !=0 bit was set
256*/
257
258my_bool bitmap_test_and_set(MY_BITMAP *map, uint bitmap_bit)
259{
260 my_bool res;
261 DBUG_ASSERT(map->bitmap && bitmap_bit < map->n_bits);
262 bitmap_lock(map);
263 res= bitmap_fast_test_and_set(map, bitmap_bit);
264 bitmap_unlock(map);
265 return res;
266}
267
268/*
269 test if bit already set and clear it if it was set(thread unsafe method)
270
271 SYNOPSIS
272 bitmap_fast_test_and_set()
273 MAP bit map struct
274 BIT bit number
275
276 RETURN
277 0 bit was not set
278 !=0 bit was set
279*/
280
281my_bool bitmap_fast_test_and_clear(MY_BITMAP *map, uint bitmap_bit)
282{
283 uchar *byte= (uchar*) map->bitmap + (bitmap_bit / 8);
284 uchar bit= 1 << ((bitmap_bit) & 7);
285 uchar res= (*byte) & bit;
286 *byte&= ~bit;
287 return res;
288}
289
290
291my_bool bitmap_test_and_clear(MY_BITMAP *map, uint bitmap_bit)
292{
293 my_bool res;
294 DBUG_ASSERT(map->bitmap && bitmap_bit < map->n_bits);
295 bitmap_lock(map);
296 res= bitmap_fast_test_and_clear(map, bitmap_bit);
297 bitmap_unlock(map);
298 return res;
299}
300
301
302uint bitmap_set_next(MY_BITMAP *map)
303{
304 uint bit_found;
305 DBUG_ASSERT(map->bitmap);
306 if ((bit_found= bitmap_get_first(map)) != MY_BIT_NONE)
307 bitmap_set_bit(map, bit_found);
308 return bit_found;
309}
310
311
312/**
313 Set the specified number of bits in the bitmap buffer.
314
315 @param map [IN] Bitmap
316 @param prefix_size [IN] Number of bits to be set
317*/
318void bitmap_set_prefix(MY_BITMAP *map, uint prefix_size)
319{
320 uint prefix_bytes, prefix_bits, d;
321 uchar *m= (uchar *)map->bitmap;
322
323 DBUG_ASSERT(map->bitmap &&
324 (prefix_size <= map->n_bits || prefix_size == (uint) ~0));
325 set_if_smaller(prefix_size, map->n_bits);
326 if ((prefix_bytes= prefix_size / 8))
327 memset(m, 0xff, prefix_bytes);
328 m+= prefix_bytes;
329 if ((prefix_bits= prefix_size & 7))
330 {
331 *(m++)= (1 << prefix_bits)-1;
332 // As the prefix bits are set, lets count this byte too as a prefix byte.
333 prefix_bytes ++;
334 }
335 if ((d= no_bytes_in_map(map)-prefix_bytes))
336 memset(m, 0, d);
337}
338
339
340my_bool bitmap_is_prefix(const MY_BITMAP *map, uint prefix_size)
341{
342 uint prefix_mask= last_byte_mask(prefix_size);
343 uchar *m= (uchar*) map->bitmap;
344 uchar *end_prefix= m+(prefix_size-1)/8;
345 uchar *end;
346 DBUG_ASSERT(m && prefix_size <= map->n_bits);
347
348 /* Empty prefix is always true */
349 if (!prefix_size)
350 return 1;
351
352 while (m < end_prefix)
353 if (*m++ != 0xff)
354 return 0;
355
356 end= ((uchar*) map->bitmap) + no_bytes_in_map(map) - 1;
357 if (m == end)
358 return ((*m & last_byte_mask(map->n_bits)) == prefix_mask);
359
360 if (*m != prefix_mask)
361 return 0;
362
363 while (++m < end)
364 if (*m != 0)
365 return 0;
366 return ((*m & last_byte_mask(map->n_bits)) == 0);
367}
368
369
370my_bool bitmap_is_set_all(const MY_BITMAP *map)
371{
372 my_bitmap_map *data_ptr= map->bitmap;
373 my_bitmap_map *end= map->last_word_ptr;
374 for (; data_ptr < end; data_ptr++)
375 if (*data_ptr != 0xFFFFFFFF)
376 return FALSE;
377 return (*data_ptr | map->last_word_mask) == 0xFFFFFFFF;
378}
379
380
381my_bool bitmap_is_clear_all(const MY_BITMAP *map)
382{
383 my_bitmap_map *data_ptr= map->bitmap;
384 my_bitmap_map *end= map->last_word_ptr;
385
386 DBUG_ASSERT(map->n_bits > 0);
387 for (; data_ptr < end; data_ptr++)
388 if (*data_ptr)
389 return FALSE;
390 return (*data_ptr & ~map->last_word_mask) == 0;
391}
392
393/* Return TRUE if map1 is a subset of map2 */
394
395my_bool bitmap_is_subset(const MY_BITMAP *map1, const MY_BITMAP *map2)
396{
397 my_bitmap_map *m1= map1->bitmap, *m2= map2->bitmap, *end;
398
399 DBUG_ASSERT(map1->bitmap && map2->bitmap &&
400 map1->n_bits==map2->n_bits);
401
402 end= map1->last_word_ptr;
403 while (m1 < end)
404 {
405 if ((*m1++) & ~(*m2++))
406 return 0;
407 }
408 /* here both maps have the same number of bits - see assert above */
409 return ((*m1 & ~*m2 & ~map1->last_word_mask) ? 0 : 1);
410}
411
412/* True if bitmaps has any common bits */
413
414my_bool bitmap_is_overlapping(const MY_BITMAP *map1, const MY_BITMAP *map2)
415{
416 my_bitmap_map *m1= map1->bitmap, *m2= map2->bitmap, *end;
417
418 DBUG_ASSERT(map1->bitmap && map2->bitmap &&
419 map1->n_bits==map2->n_bits);
420
421 end= map1->last_word_ptr;
422 while (m1 < end)
423 {
424 if ((*m1++) & (*m2++))
425 return 1;
426 }
427 /* here both maps have the same number of bits - see assert above */
428 return ((*m1 & *m2 & ~map1->last_word_mask) ? 1 : 0);
429}
430
431
432void bitmap_intersect(MY_BITMAP *map, const MY_BITMAP *map2)
433{
434 my_bitmap_map *to= map->bitmap, *from= map2->bitmap, *end;
435 uint len= no_words_in_map(map), len2 = no_words_in_map(map2);
436
437 DBUG_ASSERT(map->bitmap && map2->bitmap);
438
439 end= to+MY_MIN(len,len2);
440 while (to < end)
441 *to++ &= *from++;
442
443 if (len2 <= len)
444 {
445 to[-1]&= ~map2->last_word_mask; /* Clear last not relevant bits */
446 end+= len-len2;
447 while (to < end)
448 *to++= 0;
449 }
450}
451
452
453/*
454 Check if there is some bit index between start_bit and end_bit, such that
455 this is bit is set for all bitmaps in bitmap_list.
456
457 SYNOPSIS
458 bitmap_exists_intersection()
459 bitmpap_array [in] a set of MY_BITMAPs
460 bitmap_count [in] number of elements in bitmpap_array
461 start_bit [in] beginning (inclusive) of the range of bits to search
462 end_bit [in] end (inclusive) of the range of bits to search, must be
463 no bigger than the bits of the shortest bitmap.
464
465 NOTES
466 This function assumes that for at least one of the bitmaps in bitmap_array all
467 bits outside the range [start_bit, end_bit] are 0. As a result is not
468 necessary to take care of the bits outside the range [start_bit, end_bit].
469
470 RETURN
471 TRUE if an intersecion exists
472 FALSE no intersection
473*/
474
475my_bool bitmap_exists_intersection(const MY_BITMAP **bitmap_array,
476 uint bitmap_count,
477 uint start_bit, uint end_bit)
478{
479 uint i, j, start_idx, end_idx;
480 my_bitmap_map cur_res;
481
482 DBUG_ASSERT(bitmap_count && end_bit >= start_bit);
483 for (j= 0; j < bitmap_count; j++)
484 DBUG_ASSERT(end_bit < bitmap_array[j]->n_bits);
485
486 start_idx= start_bit/8/sizeof(my_bitmap_map);
487 end_idx= end_bit/8/sizeof(my_bitmap_map);
488
489 for (i= start_idx; i < end_idx; i++)
490 {
491 cur_res= ~0;
492 for (j= 0; cur_res && j < bitmap_count; j++)
493 cur_res &= bitmap_array[j]->bitmap[i];
494 if (cur_res)
495 return TRUE;
496 }
497 cur_res= ~last_word_mask(end_bit);
498 for (j= 0; cur_res && j < bitmap_count; j++)
499 cur_res &= bitmap_array[j]->bitmap[end_idx];
500 return cur_res != 0;
501}
502
503
504/* True if union of bitmaps have all bits set */
505
506my_bool bitmap_union_is_set_all(const MY_BITMAP *map1, const MY_BITMAP *map2)
507{
508 my_bitmap_map *m1= map1->bitmap, *m2= map2->bitmap, *end;
509
510 DBUG_ASSERT(map1->bitmap && map2->bitmap &&
511 map1->n_bits==map2->n_bits);
512 end= map1->last_word_ptr;
513 while ( m1 < end)
514 if ((*m1++ | *m2++) != 0xFFFFFFFF)
515 return FALSE;
516 /* here both maps have the same number of bits - see assert above */
517 return ((*m1 | *m2 | map1->last_word_mask) != 0xFFFFFFFF);
518}
519
520
521
522/*
523 Set/clear all bits above a bit.
524
525 SYNOPSIS
526 bitmap_set_above()
527 map RETURN The bitmap to change.
528 from_byte The bitmap buffer byte offset to start with.
529 use_bit The bit value (1/0) to use for all upper bits.
530
531 NOTE
532 You can only set/clear full bytes.
533 The function is meant for the situation that you copy a smaller bitmap
534 to a bigger bitmap. Bitmap lengths are always multiple of eigth (the
535 size of a byte). Using 'from_byte' saves multiplication and division
536 by eight during parameter passing.
537
538 RETURN
539 void
540*/
541
542void bitmap_set_above(MY_BITMAP *map, uint from_byte, uint use_bit)
543{
544 uchar use_byte= use_bit ? 0xff : 0;
545 uchar *to= (uchar *)map->bitmap + from_byte;
546 uchar *end= (uchar *)map->bitmap + (map->n_bits+7)/8;
547
548 while (to < end)
549 *to++= use_byte;
550}
551
552
553void bitmap_subtract(MY_BITMAP *map, const MY_BITMAP *map2)
554{
555 my_bitmap_map *to= map->bitmap, *from= map2->bitmap, *end;
556 DBUG_ASSERT(map->bitmap && map2->bitmap &&
557 map->n_bits==map2->n_bits);
558
559 end= map->last_word_ptr;
560
561 while (to <= end)
562 *to++ &= ~(*from++);
563}
564
565
566void bitmap_union(MY_BITMAP *map, const MY_BITMAP *map2)
567{
568 my_bitmap_map *to= map->bitmap, *from= map2->bitmap, *end;
569
570 DBUG_ASSERT(map->bitmap && map2->bitmap &&
571 map->n_bits==map2->n_bits);
572 end= map->last_word_ptr;
573
574 while (to <= end)
575 *to++ |= *from++;
576}
577
578
579void bitmap_xor(MY_BITMAP *map, const MY_BITMAP *map2)
580{
581 my_bitmap_map *to= map->bitmap, *from= map2->bitmap, *end= map->last_word_ptr;
582 DBUG_ASSERT(map->bitmap && map2->bitmap &&
583 map->n_bits==map2->n_bits);
584 while (to <= end)
585 *to++ ^= *from++;
586}
587
588
589void bitmap_invert(MY_BITMAP *map)
590{
591 my_bitmap_map *to= map->bitmap, *end;
592
593 DBUG_ASSERT(map->bitmap);
594 end= map->last_word_ptr;
595
596 while (to <= end)
597 *to++ ^= 0xFFFFFFFF;
598}
599
600
601uint bitmap_bits_set(const MY_BITMAP *map)
602{
603 my_bitmap_map *data_ptr= map->bitmap;
604 my_bitmap_map *end= map->last_word_ptr;
605 uint res= 0;
606 DBUG_ASSERT(map->bitmap);
607
608 for (; data_ptr < end; data_ptr++)
609 res+= my_count_bits_uint32(*data_ptr);
610
611 /*Reset last bits to zero*/
612 res+= my_count_bits_uint32(*map->last_word_ptr & ~map->last_word_mask);
613 return res;
614}
615
616void bitmap_copy(MY_BITMAP *map, const MY_BITMAP *map2)
617{
618 my_bitmap_map *to= map->bitmap, *from= map2->bitmap, *end;
619
620 DBUG_ASSERT(map->bitmap && map2->bitmap &&
621 map->n_bits==map2->n_bits);
622 end= map->last_word_ptr;
623
624 while (to <= end)
625 *to++ = *from++;
626}
627
628
629uint bitmap_get_first_set(const MY_BITMAP *map)
630{
631 uint i;
632 my_bitmap_map *data_ptr= map->bitmap, *end= map->last_word_ptr;
633
634 DBUG_ASSERT(map->bitmap);
635
636 for (i=0; data_ptr < end; data_ptr++, i++)
637 if (*data_ptr)
638 goto found;
639 if (!(*data_ptr & ~map->last_word_mask))
640 return MY_BIT_NONE;
641
642found:
643 return get_first_set(*data_ptr, i);
644}
645
646
647/**
648 Get the next set bit.
649
650 @param map Bitmap
651 @param bitmap_bit Bit to start search from
652
653 @return Index to first bit set after bitmap_bit
654*/
655
656uint bitmap_get_next_set(const MY_BITMAP *map, uint bitmap_bit)
657{
658 uint word_pos, byte_to_mask, i;
659 union { my_bitmap_map bitmap ; uchar bitmap_buff[sizeof(my_bitmap_map)]; }
660 first_word;
661 uchar *ptr= &first_word.bitmap_buff[0];
662 my_bitmap_map *data_ptr, *end= map->last_word_ptr;
663
664 DBUG_ASSERT(map->bitmap);
665
666 /* Look for the next bit */
667 bitmap_bit++;
668 if (bitmap_bit >= map->n_bits)
669 return MY_BIT_NONE;
670 word_pos= bitmap_bit / 32;
671 data_ptr= map->bitmap + word_pos;
672 first_word.bitmap= *data_ptr;
673
674 /* Mask out previous bits from first_word */
675 byte_to_mask= (bitmap_bit % 32) / 8;
676 for (i= 0; i < byte_to_mask; i++)
677 ptr[i]= 0;
678 ptr[byte_to_mask]&= 0xFFU << (bitmap_bit & 7);
679
680 if (data_ptr == end)
681 {
682 if (first_word.bitmap & ~map->last_word_mask)
683 return get_first_set(first_word.bitmap, word_pos);
684 else
685 return MY_BIT_NONE;
686 }
687
688 if (first_word.bitmap)
689 return get_first_set(first_word.bitmap, word_pos);
690
691 for (data_ptr++, word_pos++; data_ptr < end; data_ptr++, word_pos++)
692 if (*data_ptr)
693 return get_first_set(*data_ptr, word_pos);
694
695 if (!(*end & ~map->last_word_mask))
696 return MY_BIT_NONE;
697 return get_first_set(*end, word_pos);
698}
699
700
701/* Get first free bit */
702
703uint bitmap_get_first(const MY_BITMAP *map)
704{
705 uchar *byte_ptr;
706 uint i,j,k;
707 my_bitmap_map *data_ptr, *end= map->last_word_ptr;
708
709 DBUG_ASSERT(map->bitmap);
710 data_ptr= map->bitmap;
711 *map->last_word_ptr|= map->last_word_mask;
712
713 for (i=0; data_ptr < end; data_ptr++, i++)
714 if (*data_ptr != 0xFFFFFFFF)
715 goto found;
716 if ((*data_ptr | map->last_word_mask) == 0xFFFFFFFF)
717 return MY_BIT_NONE;
718
719found:
720 byte_ptr= (uchar*)data_ptr;
721 for (j=0; ; j++, byte_ptr++)
722 {
723 if (*byte_ptr != 0xFF)
724 {
725 for (k=0; ; k++)
726 {
727 if (!(*byte_ptr & (1 << k)))
728 return (i*32) + (j*8) + k;
729 }
730 }
731 }
732 DBUG_ASSERT(0);
733 return MY_BIT_NONE; /* Impossible */
734}
735
736
737uint bitmap_lock_set_next(MY_BITMAP *map)
738{
739 uint bit_found;
740 bitmap_lock(map);
741 bit_found= bitmap_set_next(map);
742 bitmap_unlock(map);
743 return bit_found;
744}
745
746
747void bitmap_lock_clear_bit(MY_BITMAP *map, uint bitmap_bit)
748{
749 bitmap_lock(map);
750 DBUG_ASSERT(map->bitmap && bitmap_bit < map->n_bits);
751 bitmap_clear_bit(map, bitmap_bit);
752 bitmap_unlock(map);
753}
754
755