diff options
author | Daniel Baumann <daniel.baumann@progress-linux.org> | 2024-05-04 18:07:14 +0000 |
---|---|---|
committer | Daniel Baumann <daniel.baumann@progress-linux.org> | 2024-05-04 18:07:14 +0000 |
commit | a175314c3e5827eb193872241446f2f8f5c9d33c (patch) | |
tree | cd3d60ca99ae00829c52a6ca79150a5b6e62528b /sql/sql_bitmap.h | |
parent | Initial commit. (diff) | |
download | mariadb-10.5-upstream/1%10.5.12.tar.xz mariadb-10.5-upstream/1%10.5.12.zip |
Adding upstream version 1:10.5.12.upstream/1%10.5.12upstream
Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>
Diffstat (limited to '')
-rw-r--r-- | sql/sql_bitmap.h | 314 |
1 files changed, 314 insertions, 0 deletions
diff --git a/sql/sql_bitmap.h b/sql/sql_bitmap.h new file mode 100644 index 00000000..02dc8198 --- /dev/null +++ b/sql/sql_bitmap.h @@ -0,0 +1,314 @@ +/* Copyright (c) 2003, 2013, Oracle and/or its affiliates + Copyright (c) 2009, 2013, Monty Program Ab. + + This program is free software; you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation; version 2 of the License. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program; if not, write to the Free Software + Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1335 USA */ + +/* + Implementation of a bitmap type. + The idea with this is to be able to handle any constant number of bits but + also be able to use 32 or 64 bits bitmaps very efficiently +*/ + +#ifndef SQL_BITMAP_INCLUDED +#define SQL_BITMAP_INCLUDED + +#include <my_sys.h> +#include <my_bitmap.h> +#include <my_bit.h> + + +/* An iterator to quickly walk over bits in ulonglong bitmap. */ +class Table_map_iterator +{ + ulonglong bmp; +public: + Table_map_iterator(ulonglong t): bmp(t){} + uint next_bit() + { + if (!bmp) + return BITMAP_END; + uint bit= my_find_first_bit(bmp); + bmp &= ~(1ULL << bit); + return bit; + } + int operator++(int) { return next_bit(); } + enum { BITMAP_END= 64 }; +}; + +template <uint width> class Bitmap +{ +/* + Workaround GCC optimizer bug (generating SSE instuctions on unaligned data) +*/ +#if defined (__GNUC__) && defined(__x86_64__) && (__GNUC__ < 6) && !defined(__clang__) +#define NEED_GCC_NO_SSE_WORKAROUND +#endif + +#ifdef NEED_GCC_NO_SSE_WORKAROUND +#pragma GCC push_options +#pragma GCC target ("no-sse") +#endif + +private: + static const int BITS_PER_ELEMENT= sizeof(ulonglong) * 8; + static const int ARRAY_ELEMENTS= (width + BITS_PER_ELEMENT - 1) / BITS_PER_ELEMENT; + static const ulonglong ALL_BITS_SET= ULLONG_MAX; + + ulonglong buffer[ARRAY_ELEMENTS]; + + uint bit_index(uint n) const + { + DBUG_ASSERT(n < width); + return ARRAY_ELEMENTS == 1 ? 0 : n / BITS_PER_ELEMENT; + } + ulonglong bit_mask(uint n) const + { + DBUG_ASSERT(n < width); + return ARRAY_ELEMENTS == 1 ? 1ULL << n : 1ULL << (n % BITS_PER_ELEMENT); + } + ulonglong last_element_mask(int n) const + { + DBUG_ASSERT(n % BITS_PER_ELEMENT != 0); + return bit_mask(n) - 1; + } + +public: + /* + The default constructor does nothing. + The caller is supposed to either zero the memory + or to call set_all()/clear_all()/set_prefix() + to initialize bitmap. + */ + Bitmap() { } + + explicit Bitmap(uint prefix) + { + set_prefix(prefix); + } + void init(uint prefix) + { + set_prefix(prefix); + } + uint length() const + { + return width; + } + void set_bit(uint n) + { + buffer[bit_index(n)] |= bit_mask(n); + } + void clear_bit(uint n) + { + buffer[bit_index(n)] &= ~bit_mask(n); + } + bool is_set(uint n) const + { + return buffer[bit_index(n)] & bit_mask(n); + } + void set_prefix(uint prefix_size) + { + set_if_smaller(prefix_size, width); + + size_t idx= prefix_size / BITS_PER_ELEMENT; + + for (size_t i= 0; i < idx; i++) + buffer[i]= ALL_BITS_SET; + + if (prefix_size % BITS_PER_ELEMENT) + buffer[idx++]= last_element_mask(prefix_size); + + for (size_t i= idx; i < ARRAY_ELEMENTS; i++) + buffer[i]= 0; + } + bool is_prefix(uint prefix_size) const + { + DBUG_ASSERT(prefix_size <= width); + + size_t idx= prefix_size / BITS_PER_ELEMENT; + + for (size_t i= 0; i < idx; i++) + if (buffer[i] != ALL_BITS_SET) + return false; + + if (prefix_size % BITS_PER_ELEMENT) + if (buffer[idx++] != last_element_mask(prefix_size)) + return false; + + for (size_t i= idx; i < ARRAY_ELEMENTS; i++) + if (buffer[i] != 0) + return false; + + return true; + } + void set_all() + { + if (width % BITS_PER_ELEMENT) + set_prefix(width); + else if (ARRAY_ELEMENTS > 1) + memset(buffer, 0xff, sizeof(buffer)); + else + buffer[0] = ALL_BITS_SET; + } + void clear_all() + { + if (ARRAY_ELEMENTS > 1) + memset(buffer, 0, sizeof(buffer)); + else + buffer[0]= 0; + } + void intersect(const Bitmap& map2) + { + for (size_t i= 0; i < ARRAY_ELEMENTS; i++) + buffer[i] &= map2.buffer[i]; + } + +private: + /* + Intersect with a bitmap represented as as longlong. + In addition, pad the rest of the bitmap with 0 or 1 bits + depending on pad_with_ones parameter. + */ + void intersect_and_pad(ulonglong map2buff, bool pad_with_ones) + { + buffer[0] &= map2buff; + + for (size_t i= 1; i < ARRAY_ELEMENTS; i++) + buffer[i]= pad_with_ones ? ALL_BITS_SET : 0; + + if (ARRAY_ELEMENTS > 1 && (width % BITS_PER_ELEMENT) && pad_with_ones) + buffer[ARRAY_ELEMENTS - 1]= last_element_mask(width); + } + +public: + void intersect(ulonglong map2buff) + { + intersect_and_pad(map2buff, 0); + } + /* Use highest bit for all bits above first element. */ + void intersect_extended(ulonglong map2buff) + { + intersect_and_pad(map2buff, (map2buff & (1ULL << 63))); + } + void subtract(const Bitmap& map2) + { + for (size_t i= 0; i < ARRAY_ELEMENTS; i++) + buffer[i] &= ~(map2.buffer[i]); + } + void merge(const Bitmap& map2) + { + for (size_t i= 0; i < ARRAY_ELEMENTS; i++) + buffer[i] |= map2.buffer[i]; + } + bool is_clear_all() const + { + for (size_t i= 0; i < ARRAY_ELEMENTS; i++) + if (buffer[i]) + return false; + return true; + } + bool is_subset(const Bitmap& map2) const + { + for (size_t i= 0; i < ARRAY_ELEMENTS; i++) + if (buffer[i] & ~(map2.buffer[i])) + return false; + return true; + } + bool is_overlapping(const Bitmap& map2) const + { + for (size_t i= 0; i < ARRAY_ELEMENTS; i++) + if (buffer[i] & map2.buffer[i]) + return true; + return false; + } + bool operator==(const Bitmap& map2) const + { + if (ARRAY_ELEMENTS > 1) + return !memcmp(buffer,map2.buffer,sizeof(buffer)); + return buffer[0] == map2.buffer[0]; + } + bool operator!=(const Bitmap& map2) const + { + return !(*this == map2); + } + /* + Print hexadecimal representation of bitmap. + Truncate trailing zeros. + */ + char *print(char *buf) const + { + size_t last; /*index of the last non-zero element, or 0. */ + + for (last= ARRAY_ELEMENTS - 1; last && !buffer[last]; last--){} + + const int HEX_DIGITS_PER_ELEMENT= BITS_PER_ELEMENT / 4; + for (size_t i= 0; i < last; i++) + { + ulonglong num = buffer[i]; + uint shift = BITS_PER_ELEMENT - 4; + size_t pos= i * HEX_DIGITS_PER_ELEMENT; + for (size_t j= 0; j < HEX_DIGITS_PER_ELEMENT; j++) + { + buf[pos + j]= _dig_vec_upper[(num >> shift) & 0xf]; + shift += 4; + } + } + longlong2str(buffer[last], buf, 16); + return buf; + } + ulonglong to_ulonglong() const + { + return buffer[0]; + } + uint bits_set() + { + uint res= 0; + for (size_t i= 0; i < ARRAY_ELEMENTS; i++) + res += my_count_bits(buffer[i]); + return res; + } + class Iterator + { + const Bitmap& map; + uint offset; + Table_map_iterator tmi; + public: + Iterator(const Bitmap<width>& map2) : map(map2), offset(0), tmi(map2.buffer[0]) {} + int operator++(int) + { + for (;;) + { + int nextbit= tmi++; + + if (nextbit != Table_map_iterator::BITMAP_END) + return offset + nextbit; + + if (offset + BITS_PER_ELEMENT >= map.length()) + return BITMAP_END; + + offset += BITS_PER_ELEMENT; + tmi= Table_map_iterator(map.buffer[offset / BITS_PER_ELEMENT]); + } + } + enum { BITMAP_END = width }; + }; + +#ifdef NEED_GCC_NO_SSE_WORKAROUND +#pragma GCC pop_options +#undef NEED_GCC_NO_SSE_WORKAROUND +#endif +}; + +typedef Bitmap<MAX_INDEXES> key_map; /* Used for finding keys */ + +#endif /* SQL_BITMAP_INCLUDED */ |