#include <memory.h>
Include dependency graph for bmfunc.h:
This graph shows which files directly or indirectly include this file:
Go to the source code of this file.
Namespaces | |
namespace | bm |
Defines | |
#define | BM_INCWORD_BITCOUNT(cnt, w) |
Typedefs | |
typedef void(* | gap_operation_to_bitset_func_type )(unsigned *, const gap_word_t *) |
typedef gap_word_t *(* | gap_operation_func_type )(const gap_word_t *, const gap_word_t *, gap_word_t *) |
typedef bm::id_t(* | bit_operation_count_func_type )(const bm::word_t *, const bm::word_t *, const bm::word_t *) |
Enumerations | |
enum | set_operation { set_AND = 0, set_OR = 1, set_SUB = 2, set_XOR = 3, set_ASSIGN = 4, set_COUNT = 5, set_COUNT_AND = 6, set_COUNT_XOR = 7, set_COUNT_OR = 8, set_COUNT_SUB_AB = 9, set_COUNT_SUB_BA = 10, set_COUNT_A = 11, set_COUNT_B = 12, set_END } |
Nomenclature of set operations. More... | |
enum | operation { BM_AND = set_AND, BM_OR = set_OR, BM_SUB = set_SUB, BM_XOR = set_XOR } |
Bit operations enumeration. More... | |
enum | ByteOrder { BigEndian = 0, LittleEndian = 1 } |
Byte orders recognized by the library. More... | |
Functions | |
BMFORCEINLINE bm::id_t | word_bitcount (bm::id_t w) |
bm::id_t | word_bitcount64 (bm::id64_t w) |
bool | is_const_set_operation (set_operation op) |
Returns true if set operation is constant (bitcount). | |
bm::operation | setop2op (bm::set_operation op) |
Convert set operation to operation. | |
template<typename W> | |
void | xor_swap (W &x, W &y) |
XOR swap two scalar variables. | |
template<typename T> | |
int | wordcmp0 (T w1, T w2) |
Lexicographical comparison of two words as bit strings. Auxiliary implementation for testing and reference purposes. | |
template<typename T> | |
int | wordcmp (T a, T b) |
Lexicographical comparison of two words as bit strings. Auxiliary implementation for testing and reference purposes. | |
template<typename T> | |
unsigned | gap_bfind (const T *buf, unsigned pos, unsigned *is_set) |
template<typename T> | |
unsigned | gap_test (const T *buf, unsigned pos) |
Tests if bit = pos is true. | |
template<class T, class F> | |
void | for_each_nzblock (T ***root, unsigned size1, unsigned size2, F &f) |
template<class T, class F> | |
bool | for_each_nzblock_if (T ***root, unsigned size1, unsigned size2, F &f) |
template<class T, class F> | |
void | for_each_block (T ***root, unsigned size1, unsigned size2, F &f) |
template<class T, class F> | |
F | bmfor_each (T first, T last, F f) |
template<class T> | |
T | sum_arr (T *first, T *last) |
template<typename T> | |
unsigned | gap_bit_count (const T *buf) |
Calculates number of bits ON in GAP buffer. | |
template<typename T> | |
unsigned | gap_bit_count_range (const T *buf, T left, T right) |
Counts 1 bits in GAP buffer in the closed [left, right] diapason. | |
template<typename T> | |
int | gapcmp (const T *buf1, const T *buf2) |
Lexicographical comparison of GAP buffers. | |
template<typename T, class F> | |
void | gap_buff_op (T *BMRESTRICT dest, const T *BMRESTRICT vect1, unsigned vect1_mask, const T *BMRESTRICT vect2, unsigned vect2_mask, F f) |
Abstract operation for GAP buffers. Receives functor F as a template argument. | |
template<typename T, class F> | |
unsigned | gap_buff_any_op (const T *BMRESTRICT vect1, unsigned vect1_mask, const T *BMRESTRICT vect2, unsigned vect2_mask, F f) |
Abstract distance test operation for GAP buffers. Receives functor F as a template argument. | |
template<typename T> | |
unsigned | gap_set_value (unsigned val, T *BMRESTRICT buf, unsigned pos, unsigned *BMRESTRICT is_set) |
Abstract distance(similarity) operation for GAP buffers. Receives functor F as a template argument Sets or clears bit in the GAP buffer. | |
template<typename T> | |
int | gap_find_in_block (const T *buf, unsigned nbit, bm::id_t *prev) |
Searches for the next 1 bit in the GAP block. | |
void | or_bit_block (unsigned *dest, unsigned bitpos, unsigned bitcount) |
Sets bits to 1 in the bitblock. | |
void | sub_bit_block (unsigned *dest, unsigned bitpos, unsigned bitcount) |
SUB (AND NOT) bit interval to 1 in the bitblock. | |
void | xor_bit_block (unsigned *dest, unsigned bitpos, unsigned bitcount) |
XOR bit interval to 1 in the bitblock. | |
template<typename T> | |
void | gap_sub_to_bitset (unsigned *dest, const T *buf) |
SUB (AND NOT) GAP block to bitblock. | |
template<typename T> | |
void | gap_xor_to_bitset (unsigned *dest, const T *buf) |
XOR GAP block to bitblock. | |
template<typename T> | |
void | gap_add_to_bitset (unsigned *dest, const T *buf) |
Adds(OR) GAP block to bitblock. | |
template<typename T> | |
void | gap_and_to_bitset (unsigned *dest, const T *buf) |
ANDs GAP block to bitblock. | |
template<typename T> | |
bm::id_t | gap_bitset_and_count (const unsigned *block, const T *buf) |
Compute bitcount of bit block AND masked by GAP block. | |
template<typename T> | |
bm::id_t | gap_bitset_and_any (const unsigned *block, const T *buf) |
Bitcount test of bit block AND masked by GAP block. | |
template<typename T> | |
bm::id_t | gap_bitset_sub_count (const unsigned *block, const T *buf) |
Compute bitcount of bit block SUB masked by GAP block. | |
template<typename T> | |
bm::id_t | gap_bitset_sub_any (const unsigned *block, const T *buf) |
Compute bitcount test of bit block SUB masked by GAP block. | |
template<typename T> | |
bm::id_t | gap_bitset_xor_count (const unsigned *block, const T *buf) |
Compute bitcount of bit block XOR masked by GAP block. | |
template<typename T> | |
bm::id_t | gap_bitset_xor_any (const unsigned *block, const T *buf) |
Compute bitcount test of bit block XOR masked by GAP block. | |
template<typename T> | |
bm::id_t | gap_bitset_or_count (const unsigned *block, const T *buf) |
Compute bitcount of bit block OR masked by GAP block. | |
template<typename T> | |
bm::id_t | gap_bitset_or_any (const unsigned *block, const T *buf) |
Compute bitcount test of bit block OR masked by GAP block. | |
void | bit_block_set (bm::word_t *BMRESTRICT dst, bm::word_t value) |
Bitblock memset operation. | |
template<typename T> | |
void | gap_convert_to_bitset (unsigned *dest, const T *buf) |
GAP block to bitblock conversion. | |
template<typename T> | |
void | gap_convert_to_bitset (unsigned *dest, const T *buf, unsigned dest_len) |
GAP block to bitblock conversion. | |
template<typename T> | |
unsigned * | gap_convert_to_bitset_smart (unsigned *dest, const T *buf, id_t set_max) |
Smart GAP block to bitblock conversion. | |
template<typename T> | |
unsigned | gap_control_sum (const T *buf) |
Calculates sum of all words in GAP block. (For debugging purposes). | |
template<class T> | |
void | gap_set_all (T *buf, unsigned set_max, unsigned value) |
Sets all bits to 0 or 1 (GAP). | |
template<class T> | |
void | gap_init_range_block (T *buf, unsigned from, unsigned to, unsigned value, unsigned set_max) |
Init gap block so it has block in it (can be whole block). | |
template<typename T> | |
void | gap_invert (T *buf) |
Inverts all bits in the GAP buffer. | |
template<typename T> | |
bool | gap_is_all_zero (const T *buf, unsigned set_max) |
Temporary inverts all bits in the GAP buffer. Checks if GAP block is all-zero. | |
template<typename T> | |
bool | gap_is_all_one (const T *buf, unsigned set_max) |
Checks if GAP block is all-one. | |
template<typename T> | |
unsigned | gap_length (const T *buf) |
Returs GAP block length. | |
template<typename T> | |
unsigned | gap_capacity (const T *buf, const T *glevel_len) |
Returs GAP block capacity. | |
template<typename T> | |
unsigned | gap_limit (const T *buf, const T *glevel_len) |
Returs GAP block capacity limit. | |
template<typename T> | |
unsigned | gap_level (const T *buf) |
Returs GAP blocks capacity level. | |
template<typename T> | |
void | set_gap_level (T *buf, unsigned level) |
Sets GAP block capacity level. | |
template<typename T> | |
int | gap_calc_level (int len, const T *glevel_len) |
Calculates GAP block capacity level. | |
template<typename T> | |
unsigned | gap_free_elements (const T *buf, const T *glevel_len) |
Returns number of free elements in GAP block array. Difference between GAP block capacity on this level and actual GAP length. | |
template<typename T> | |
int | bitcmp (const T *buf1, const T *buf2, unsigned len) |
Lexicographical comparison of BIT buffers. | |
template<typename T> | |
unsigned | bit_convert_to_gap (T *BMRESTRICT dest, const unsigned *BMRESTRICT src, bm::id_t bits, unsigned dest_len) |
Converts bit block to GAP. | |
template<typename D, typename T> | |
D | gap_convert_to_arr (D *BMRESTRICT dest, const T *BMRESTRICT buf, unsigned dest_len) |
Convert gap block into array of ints corresponding to 1 bits. | |
template<typename T> | |
T | bit_convert_to_arr (T *BMRESTRICT dest, const unsigned *BMRESTRICT src, bm::id_t bits, unsigned dest_len) |
Convert bit block into an array of ints corresponding to 1 bits. | |
bm::id_t | bit_block_calc_count (const bm::word_t *block, const bm::word_t *block_end) |
Bitcount for bit string. | |
bm::id_t | bit_count_change (bm::word_t w) |
bm::id_t | bit_block_calc_count_change (const bm::word_t *block, const bm::word_t *block_end) |
bm::id_t | bit_block_calc_count_range (const bm::word_t *block, bm::word_t left, bm::word_t right) |
bm::id_t | bit_block_any_range (const bm::word_t *block, bm::word_t left, bm::word_t right) |
template<typename T> | |
void | bit_invert (T *start, T *end) |
bool | is_bits_one (const bm::wordop_t *start, const bm::wordop_t *end) |
Returns "true" if all bits in the block are 1. | |
bool | bit_is_all_zero (const bm::wordop_t *start, const bm::wordop_t *end) |
Returns "true" if all bits in the block are 0. | |
unsigned | and_op (unsigned v1, unsigned v2) |
GAP and functor. | |
unsigned | xor_op (unsigned v1, unsigned v2) |
GAP xor functor. | |
gap_word_t * | gap_operation_and (const gap_word_t *BMRESTRICT vect1, const gap_word_t *BMRESTRICT vect2, gap_word_t *BMRESTRICT tmp_buf) |
GAP AND operation. | |
unsigned | gap_operation_any_and (const gap_word_t *BMRESTRICT vect1, const gap_word_t *BMRESTRICT vect2) |
GAP AND operation test. | |
gap_word_t * | gap_operation_xor (const gap_word_t *BMRESTRICT vect1, const gap_word_t *BMRESTRICT vect2, gap_word_t *BMRESTRICT tmp_buf) |
GAP XOR operation. | |
unsigned | gap_operation_any_xor (const gap_word_t *BMRESTRICT vect1, const gap_word_t *BMRESTRICT vect2) |
GAP XOR operation test. | |
gap_word_t * | gap_operation_or (const gap_word_t *BMRESTRICT vect1, const gap_word_t *BMRESTRICT vect2, gap_word_t *BMRESTRICT tmp_buf) |
GAP OR operation. | |
gap_word_t * | gap_operation_sub (const gap_word_t *BMRESTRICT vect1, const gap_word_t *BMRESTRICT vect2, gap_word_t *BMRESTRICT tmp_buf) |
GAP SUB (AND NOT) operation. | |
unsigned | gap_operation_any_sub (const gap_word_t *BMRESTRICT vect1, const gap_word_t *BMRESTRICT vect2) |
GAP SUB operation test. | |
void | bit_block_copy (bm::word_t *BMRESTRICT dst, const bm::word_t *BMRESTRICT src) |
Bitblock copy operation. | |
void | bit_block_and (bm::word_t *BMRESTRICT dst, const bm::word_t *BMRESTRICT src) |
Plain bitblock AND operation. Function does not analyse availability of source and destination blocks. | |
unsigned | bit_block_and_count (const bm::word_t *src1, const bm::word_t *src1_end, const bm::word_t *src2) |
Function ANDs two bitblocks and computes the bitcount. Function does not analyse availability of source blocks. | |
unsigned | bit_block_and_any (const bm::word_t *src1, const bm::word_t *src1_end, const bm::word_t *src2) |
Function ANDs two bitblocks and tests for any bit. Function does not analyse availability of source blocks. | |
unsigned | bit_block_xor_count (const bm::word_t *BMRESTRICT src1, const bm::word_t *BMRESTRICT src1_end, const bm::word_t *BMRESTRICT src2) |
Function XORs two bitblocks and computes the bitcount. Function does not analyse availability of source blocks. | |
unsigned | bit_block_xor_any (const bm::word_t *BMRESTRICT src1, const bm::word_t *BMRESTRICT src1_end, const bm::word_t *BMRESTRICT src2) |
Function XORs two bitblocks and and tests for any bit. Function does not analyse availability of source blocks. | |
unsigned | bit_block_sub_count (const bm::word_t *BMRESTRICT src1, const bm::word_t *BMRESTRICT src1_end, const bm::word_t *BMRESTRICT src2) |
Function SUBs two bitblocks and computes the bitcount. Function does not analyse availability of source blocks. | |
unsigned | bit_block_sub_any (const bm::word_t *BMRESTRICT src1, const bm::word_t *BMRESTRICT src1_end, const bm::word_t *BMRESTRICT src2) |
Function SUBs two bitblocks and and tests for any bit. Function does not analyse availability of source blocks. | |
unsigned | bit_block_or_count (const bm::word_t *src1, const bm::word_t *src1_end, const bm::word_t *src2) |
Function ORs two bitblocks and computes the bitcount. Function does not analyse availability of source blocks. | |
unsigned | bit_block_or_any (const bm::word_t *BMRESTRICT src1, const bm::word_t *BMRESTRICT src1_end, const bm::word_t *BMRESTRICT src2) |
Function ORs two bitblocks and and tests for any bit. Function does not analyse availability of source blocks. | |
bm::word_t * | bit_operation_and (bm::word_t *BMRESTRICT dst, const bm::word_t *BMRESTRICT src) |
bitblock AND operation. | |
bm::id_t | bit_operation_and_count (const bm::word_t *BMRESTRICT src1, const bm::word_t *BMRESTRICT src1_end, const bm::word_t *BMRESTRICT src2) |
Performs bitblock AND operation and calculates bitcount of the result. | |
bm::id_t | bit_operation_and_any (const bm::word_t *BMRESTRICT src1, const bm::word_t *BMRESTRICT src1_end, const bm::word_t *BMRESTRICT src2) |
Performs bitblock AND operation test. | |
bm::id_t | bit_operation_sub_count (const bm::word_t *BMRESTRICT src1, const bm::word_t *BMRESTRICT src1_end, const bm::word_t *BMRESTRICT src2) |
Performs bitblock SUB operation and calculates bitcount of the result. | |
bm::id_t | bit_operation_sub_count_inv (const bm::word_t *BMRESTRICT src1, const bm::word_t *BMRESTRICT src1_end, const bm::word_t *BMRESTRICT src2) |
Performs inverted bitblock SUB operation and calculates bitcount of the result. | |
bm::id_t | bit_operation_sub_any (const bm::word_t *BMRESTRICT src1, const bm::word_t *BMRESTRICT src1_end, const bm::word_t *BMRESTRICT src2) |
Performs bitblock test of SUB operation. | |
bm::id_t | bit_operation_or_count (const bm::word_t *BMRESTRICT src1, const bm::word_t *BMRESTRICT src1_end, const bm::word_t *BMRESTRICT src2) |
Performs bitblock OR operation and calculates bitcount of the result. | |
bm::id_t | bit_operation_or_any (const bm::word_t *BMRESTRICT src1, const bm::word_t *BMRESTRICT src1_end, const bm::word_t *BMRESTRICT src2) |
Performs bitblock OR operation test. | |
void | bit_block_or (bm::word_t *BMRESTRICT dst, const bm::word_t *BMRESTRICT src) |
Plain bitblock OR operation. Function does not analyse availability of source and destination blocks. | |
bm::word_t * | bit_operation_or (bm::word_t *BMRESTRICT dst, const bm::word_t *BMRESTRICT src) |
Block OR operation. Makes analysis if block is 0 or FULL. | |
void | bit_block_sub (bm::word_t *BMRESTRICT dst, const bm::word_t *BMRESTRICT src) |
Plain bitblock SUB (AND NOT) operation. Function does not analyse availability of source and destination blocks. | |
bm::word_t * | bit_operation_sub (bm::word_t *BMRESTRICT dst, const bm::word_t *BMRESTRICT src) |
bitblock SUB operation. | |
void | bit_block_xor (bm::word_t *BMRESTRICT dst, const bm::word_t *BMRESTRICT src) |
Plain bitblock XOR operation. Function does not analyse availability of source and destination blocks. | |
bm::word_t * | bit_operation_xor (bm::word_t *BMRESTRICT dst, const bm::word_t *BMRESTRICT src) |
bitblock XOR operation. | |
bm::id_t | bit_operation_xor_count (const bm::word_t *BMRESTRICT src1, const bm::word_t *BMRESTRICT src1_end, const bm::word_t *BMRESTRICT src2) |
Performs bitblock XOR operation and calculates bitcount of the result. | |
bm::id_t | bit_operation_xor_any (const bm::word_t *BMRESTRICT src1, const bm::word_t *BMRESTRICT src1_end, const bm::word_t *BMRESTRICT src2) |
Performs bitblock XOR operation test. | |
void | bit_find_head_tail (const bm::word_t *data, unsigned *head_idx, unsigned *tail_idx) |
Inspects bit block for zero words at the head and at the end. | |
int | bit_find_in_block (const bm::word_t *data, unsigned nbit, bm::id_t *prev) |
Searches for the next 1 bit in the BIT block. | |
template<typename T, typename B> | |
unsigned | bit_list (T w, B *bits) |
Unpacks word into list of ON bit indexes. | |
template<typename T> | |
unsigned | gap_overhead (const T *length, const T *length_end, const T *glevel_len) |
Calculates memory overhead for number of gap blocks sharing the same memory allocation table (level lengths table). | |
template<typename T> | |
bool | improve_gap_levels (const T *length, const T *length_end, T *glevel_len) |
Finds optimal gap blocks lengths. | |
template<class It1, class It2, class BinaryOp, class Encoder> | |
void | bit_recomb (It1 &it1, It2 &it2, BinaryOp &op, Encoder &enc, unsigned block_size=bm::set_block_size) |
|
|
|
|
|
|
|
Byte orders recognized by the library.
|
|
Bit operations enumeration.
|
|
Nomenclature of set operations.
|
|
GAP and functor.
|
|
Abstract recombination algorithm for two bit-blocks Bit blocks can come as dserialization decoders or bit-streams |
|
Special BM optimized analog of STL for_each |
|
For each block executes supplied function. Definition at line 600 of file bmfunc.h. Referenced by bm::bvector< Alloc, MS >::invert(). |
|
For each non-zero block executes supplied function. Definition at line 535 of file bmfunc.h. Referenced by bm::bvector< Alloc, MS >::count(), bm::bvector< Alloc, MS >::count_blocks(), bm::bvector< Alloc, MS >::optimize(), and bm::bvector< Alloc, MS >::set_gap_levels(). |
|
For each non-zero block executes supplied function-predicate. Function returns if function-predicate returns true Definition at line 575 of file bmfunc.h. Referenced by bm::bvector< Alloc, MS >::any(). |
|
Definition at line 469 of file bmfunc.h. References BM_ASSERT. Referenced by bm::gap_bit_count_range(), bm::gap_find_in_block(), and bm::gap_set_value(). |
|
Counts 1 bits in GAP buffer in the closed [left, right] diapason.
Definition at line 691 of file bmfunc.h. References BM_ASSERT, and bm::gap_bfind(). Referenced by bm::bvector< Alloc, MS >::count_range(). |
|
Returns true if set operation is constant (bitcount).
Definition at line 274 of file bmfunc.h. References bm::set_COUNT. |
|
Convert set operation to operation.
Definition at line 294 of file bmfunc.h. References BM_ASSERT, bm::set_AND, bm::set_OR, bm::set_SUB, and bm::set_XOR. |
|
Computes SUM of all elements of the sequence |
|
GAP xor functor.
|
|
XOR swap two scalar variables.
Definition at line 329 of file bmfunc.h. References BM_ASSERT. Referenced by bm::bvector< Alloc, MS >::swap(). |