9
3

my_bitmap.h 5.9 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157
  1. /* Copyright (c) 2001, 2011, Oracle and/or its affiliates.
  2. Copyright (c) 2009-2011, Monty Program Ab
  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. This program is distributed in the hope that it will be useful,
  7. but WITHOUT ANY WARRANTY; without even the implied warranty of
  8. MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
  9. GNU General Public License for more details.
  10. You should have received a copy of the GNU General Public License
  11. along with this program; if not, write to the Free Software
  12. Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA */
  13. #ifndef _my_bitmap_h_
  14. #define _my_bitmap_h_
  15. #define MY_BIT_NONE (~(uint) 0)
  16. #include <m_string.h>
  17. #include <my_pthread.h>
  18. typedef uint32 my_bitmap_map;
  19. typedef struct st_bitmap
  20. {
  21. my_bitmap_map *bitmap;
  22. my_bitmap_map *last_word_ptr;
  23. /*
  24. mutex will be acquired for the duration of each bitmap operation if
  25. thread_safe flag in bitmap_init was set. Otherwise, we optimize by not
  26. acquiring the mutex
  27. */
  28. mysql_mutex_t *mutex;
  29. my_bitmap_map last_word_mask;
  30. uint32 n_bits; /* number of bits occupied by the above */
  31. } MY_BITMAP;
  32. #ifdef __cplusplus
  33. extern "C" {
  34. #endif
  35. /* compatibility functions */
  36. #define bitmap_init(A,B,C,D) my_bitmap_init(A,B,C,D)
  37. #define bitmap_free(A) my_bitmap_free(A)
  38. extern void create_last_word_mask(MY_BITMAP *map);
  39. extern my_bool my_bitmap_init(MY_BITMAP *map, my_bitmap_map *buf, uint n_bits,
  40. my_bool thread_safe);
  41. extern my_bool bitmap_is_clear_all(const MY_BITMAP *map);
  42. extern my_bool bitmap_is_prefix(const MY_BITMAP *map, uint prefix_size);
  43. extern my_bool bitmap_is_set_all(const MY_BITMAP *map);
  44. extern my_bool bitmap_is_subset(const MY_BITMAP *map1, const MY_BITMAP *map2);
  45. extern my_bool bitmap_is_overlapping(const MY_BITMAP *map1,
  46. const MY_BITMAP *map2);
  47. extern my_bool bitmap_test_and_set(MY_BITMAP *map, uint bitmap_bit);
  48. extern my_bool bitmap_test_and_clear(MY_BITMAP *map, uint bitmap_bit);
  49. extern my_bool bitmap_fast_test_and_set(MY_BITMAP *map, uint bitmap_bit);
  50. extern my_bool bitmap_union_is_set_all(const MY_BITMAP *map1,
  51. const MY_BITMAP *map2);
  52. extern my_bool bitmap_exists_intersection(const MY_BITMAP **bitmap_array,
  53. uint bitmap_count,
  54. uint start_bit, uint end_bit);
  55. extern uint bitmap_set_next(MY_BITMAP *map);
  56. extern uint bitmap_get_first(const MY_BITMAP *map);
  57. extern uint bitmap_get_first_set(const MY_BITMAP *map);
  58. extern uint bitmap_bits_set(const MY_BITMAP *map);
  59. extern uint bitmap_get_next_set(const MY_BITMAP *map, uint bitmap_bit);
  60. extern void my_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. extern uint bitmap_lock_set_next(MY_BITMAP *map);
  70. extern void bitmap_lock_clear_bit(MY_BITMAP *map, uint bitmap_bit);
  71. /* Fast, not thread safe, bitmap functions */
  72. #define bitmap_buffer_size(bits) (((bits)+31)/32)*4
  73. #define no_bytes_in_map(map) (((map)->n_bits + 7)/8)
  74. #define no_words_in_map(map) (((map)->n_bits + 31)/32)
  75. #define bytes_word_aligned(bytes) (4*((bytes + 3)/4))
  76. #define _bitmap_set_bit(MAP, BIT) (((uchar*)(MAP)->bitmap)[(BIT) / 8] \
  77. |= (1 << ((BIT) & 7)))
  78. #define _bitmap_flip_bit(MAP, BIT) (((uchar*)(MAP)->bitmap)[(BIT) / 8] \
  79. ^= (1 << ((BIT) & 7)))
  80. #define _bitmap_clear_bit(MAP, BIT) (((uchar*)(MAP)->bitmap)[(BIT) / 8] \
  81. &= ~ (1 << ((BIT) & 7)))
  82. #define _bitmap_is_set(MAP, BIT) (uint) (((uchar*)(MAP)->bitmap)[(BIT) / 8] \
  83. & (1 << ((BIT) & 7)))
  84. /*
  85. WARNING!
  86. The below symbols are inline functions in DEBUG builds and macros in
  87. non-DEBUG builds. The latter evaluate their 'bit' argument twice.
  88. NEVER use an increment/decrement operator with the 'bit' argument.
  89. It would work with DEBUG builds, but fails later in production builds!
  90. FORBIDDEN: bitmap_set_bit($my_bitmap, (field++)->field_index);
  91. */
  92. #ifndef DBUG_OFF
  93. static inline void
  94. bitmap_set_bit(MY_BITMAP *map,uint bit)
  95. {
  96. DBUG_ASSERT(bit < (map)->n_bits);
  97. _bitmap_set_bit(map,bit);
  98. }
  99. static inline void
  100. bitmap_flip_bit(MY_BITMAP *map,uint bit)
  101. {
  102. DBUG_ASSERT(bit < (map)->n_bits);
  103. _bitmap_flip_bit(map,bit);
  104. }
  105. static inline void
  106. bitmap_clear_bit(MY_BITMAP *map,uint bit)
  107. {
  108. DBUG_ASSERT(bit < (map)->n_bits);
  109. _bitmap_clear_bit(map,bit);
  110. }
  111. static inline uint
  112. bitmap_is_set(const MY_BITMAP *map,uint bit)
  113. {
  114. DBUG_ASSERT(bit < (map)->n_bits);
  115. return _bitmap_is_set(map,bit);
  116. }
  117. #else
  118. #define bitmap_set_bit(MAP, BIT) _bitmap_set_bit(MAP, BIT)
  119. #define bitmap_flip_bit(MAP, BIT) _bitmap_flip_bit(MAP, BIT)
  120. #define bitmap_clear_bit(MAP, BIT) _bitmap_clear_bit(MAP, BIT)
  121. #define bitmap_is_set(MAP, BIT) _bitmap_is_set(MAP, BIT)
  122. #endif
  123. static inline my_bool bitmap_cmp(const MY_BITMAP *map1, const MY_BITMAP *map2)
  124. {
  125. if (memcmp(map1->bitmap, map2->bitmap, 4*(no_words_in_map(map1)-1)) != 0)
  126. return FALSE;
  127. return ((*map1->last_word_ptr | map1->last_word_mask) ==
  128. (*map2->last_word_ptr | map2->last_word_mask));
  129. }
  130. #define bitmap_clear_all(MAP) \
  131. { memset((MAP)->bitmap, 0, 4*no_words_in_map((MAP))); }
  132. #define bitmap_set_all(MAP) \
  133. (memset((MAP)->bitmap, 0xFF, 4*no_words_in_map((MAP))))
  134. #ifdef __cplusplus
  135. }
  136. #endif
  137. #endif /* _my_bitmap_h_ */