Main Page | Modules | Namespace List | Class Hierarchy | Alphabetical List | Data Structures | Directories | File List | Namespace Members | Data Fields | Globals | Examples

bmfunc.h File Reference

#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>
bmfor_each (T first, T last, F f)
template<class 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>
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>
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_tgap_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_tgap_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_tgap_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_tgap_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_tbit_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_tbit_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_tbit_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_tbit_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)


Typedef Documentation

typedef bm::id_t(* bm::bit_operation_count_func_type)(const bm::word_t *, const bm::word_t *, const bm::word_t *)
 

Definition at line 4301 of file bmfunc.h.

typedef gap_word_t*(* bm::gap_operation_func_type)(const gap_word_t *, const gap_word_t *, gap_word_t *)
 

Definition at line 4296 of file bmfunc.h.

typedef void(* bm::gap_operation_to_bitset_func_type)(unsigned *, const gap_word_t *)
 

Definition at line 4292 of file bmfunc.h.


Enumeration Type Documentation

enum bm::ByteOrder
 

Byte orders recognized by the library.

Enumeration values:
BigEndian 
LittleEndian 

Definition at line 405 of file bmfunc.h.

enum bm::operation
 

Bit operations enumeration.

Enumeration values:
BM_AND 
BM_OR 
BM_SUB 
BM_XOR 

Definition at line 282 of file bmfunc.h.

enum bm::set_operation
 

Nomenclature of set operations.

Enumeration values:
set_AND 
set_OR 
set_SUB 
set_XOR 
set_ASSIGN 
set_COUNT 
set_COUNT_AND 
set_COUNT_XOR 
set_COUNT_OR 
set_COUNT_SUB_AB 
set_COUNT_SUB_BA 
set_COUNT_A 
set_COUNT_B 
set_END 

Definition at line 253 of file bmfunc.h.


Function Documentation

unsigned and_op unsigned  v1,
unsigned  v2
[inline]
 

GAP and functor.

Definition at line 2749 of file bmfunc.h.

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
 

Abstract recombination algorithm for two bit-blocks Bit blocks can come as dserialization decoders or bit-streams

Definition at line 4158 of file bmfunc.h.

template<class T, class F>
F bmfor_each first,
last,
f
 

Special BM optimized analog of STL for_each

Definition at line 629 of file bmfunc.h.

template<class T, class F>
void for_each_block T ***  root,
unsigned  size1,
unsigned  size2,
F &  f
 

For each block executes supplied function.

Definition at line 600 of file bmfunc.h.

Referenced by bm::bvector< Alloc, MS >::invert().

template<class T, class F>
void for_each_nzblock T ***  root,
unsigned  size1,
unsigned  size2,
F &  f
 

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().

template<class T, class F>
bool for_each_nzblock_if T ***  root,
unsigned  size1,
unsigned  size2,
F &  f
 

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().

template<typename T>
unsigned gap_bfind const T *  buf,
unsigned  pos,
unsigned *  is_set
 

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().

template<typename T>
unsigned gap_bit_count_range const T *  buf,
left,
right
 

Counts 1 bits in GAP buffer in the closed [left, right] diapason.

Parameters:
buf - GAP buffer pointer.
left - leftmost bit index to start from
right- rightmost bit index
Returns:
Number of non-zero bits.

Definition at line 691 of file bmfunc.h.

References BM_ASSERT, and bm::gap_bfind().

Referenced by bm::bvector< Alloc, MS >::count_range().

bool is_const_set_operation set_operation  op  )  [inline]
 

Returns true if set operation is constant (bitcount).

Definition at line 274 of file bmfunc.h.

References bm::set_COUNT.

bm::operation setop2op bm::set_operation  op  )  [inline]
 

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.

template<class T>
T sum_arr T *  first,
T *  last
 

Computes SUM of all elements of the sequence

Definition at line 641 of file bmfunc.h.

unsigned xor_op unsigned  v1,
unsigned  v2
[inline]
 

GAP xor functor.

Definition at line 2756 of file bmfunc.h.

template<typename W>
void xor_swap W &  x,
W &  y
 

XOR swap two scalar variables.

Definition at line 329 of file bmfunc.h.

References BM_ASSERT.

Referenced by bm::bvector< Alloc, MS >::swap().


Generated on Sun Aug 5 14:12:29 2007 for BitMagic by  doxygen 1.4.1