1 #ifndef BMBMATRIX__H__INCLUDED__
2 #define BMBMATRIX__H__INCLUDED__
102 {
pool_ = pool_ptr; }
252 template<
typename Val,
typename BV,
unsigned MAX_SIZE>
505 template<
typename BV>
510 : bv_size_(bv_max_size),
517 allocate_rows(rsize);
522 template<
typename BV>
530 template<
typename BV>
532 : bv_size_(bbm.bv_size_),
544 template<
typename BV>
546 : bv_size_(bbm.bv_size_),
558 template<
typename BV>
568 template<
typename BV>
578 template<
typename BV>
588 template<
typename BV>
592 #if defined(BM64_SSE4)
593 __m128i w0 = _mm_loadu_si128((__m128i*)(bv_rows_ + j));
594 __m128i w1 = _mm_loadu_si128((__m128i*)(bv_rows_ + j + 2));
595 w0 = _mm_or_si128(w0, w1);
596 return !_mm_testz_si128(w0, w0);
597 #elif defined(BM64_AVX2) || defined(BM64_AVX512)
598 __m256i w0 = _mm256_loadu_si256((__m256i*)(bv_rows_ + j));
599 return !_mm256_testz_si256(w0, w0);
601 bool b = bv_rows_[j + 0] || bv_rows_[j + 1] ||
602 bv_rows_[j + 2] || bv_rows_[j + 3];
609 template<
typename BV>
623 bv_rows_ = (bvector_type_ptr*)alloc_.alloc_ptr(rsize);
631 const bvector_type_ptr bv = bbm.
bv_rows_[i];
642 template<
typename BV>
649 bv_rows_ = (bvector_type_ptr*)alloc_.alloc_ptr(
unsigned(rsize));
663 template<
typename BV>
668 bvector_type_ptr bv = bv_rows_[i];
671 destruct_bvector(bv);
677 alloc_.free_ptr(bv_rows_,
unsigned(rsize_));
684 template<
typename BV>
694 bbm.alloc_ = alloc_tmp;
700 allocator_pool_type* pool_tmp = pool_;
702 bbm.pool_ = pool_tmp;
706 bvector_type_ptr* rtmp = bv_rows_;
707 bv_rows_ = bbm.bv_rows_;
713 template<
typename BV>
718 bvector_type_ptr bv = bv_rows_[row];
728 template<
typename BV>
733 bvector_type_ptr bv = bv_rows_[row];
748 template<
typename BV>
752 bvector_type_ptr bv = bv_rows_[row];
755 destruct_bvector(bv);
763 template<
typename BV>
768 #ifdef BM_NO_STL // C compatibility mode
772 BM_THROW(
false, BM_ERR_BADALLOC);
789 template<
typename BV>
792 #ifdef BM_NO_STL // C compatibility mode
802 template<
typename BV>
807 bvector_type_const_ptr bv = this->row(p);
811 bv->get_blocks_manager();
812 return bman.get_block_ptr(i, j);
820 template<
typename BV>
830 for (; row < row_end; ++row)
837 bv = this->construct_row(row);
853 for (++row; row < row_end; ++row)
863 template<
typename BV>
873 for (; row < row_end; ++row)
880 bv = this->construct_row(row);
900 for (++row; row < row_end; ++row)
911 template<
typename BV>
927 unsigned row_idx = unsigned(octet_idx * 8);
929 blka[0] = get_block(row_idx+0, i0, j0);
930 blka[1] = get_block(row_idx+1, i0, j0);
931 blka[2] = get_block(row_idx+2, i0, j0);
932 blka[3] = get_block(row_idx+3, i0, j0);
933 blka[4] = get_block(row_idx+4, i0, j0);
934 blka[5] = get_block(row_idx+5, i0, j0);
935 blka[6] = get_block(row_idx+6, i0, j0);
936 blka[7] = get_block(row_idx+7, i0, j0);
939 if ((blk = blka[0])!=0)
945 v |= (unsigned)
bool(is_set);
947 if ((blk = blka[1])!=0)
953 v |= unsigned(
bool(is_set)) << 1u;
955 if ((blk = blka[2])!=0)
961 v |= unsigned(
bool(is_set)) << 2u;
963 if ((blk = blka[3])!=0)
969 v |= unsigned(
bool(is_set)) << 3u;
973 if ((blk = blka[4])!=0)
979 v |= unsigned(
bool(is_set)) << 4u;
981 if ((blk = blka[5])!=0)
987 v |= unsigned(
bool(is_set)) << 5u;
989 if ((blk = blka[6])!=0)
995 v |= unsigned(
bool(is_set)) << 6u;
997 if ((blk = blka[7])!=0)
1003 v |= unsigned(
bool(is_set)) << 7u;
1006 return (
unsigned char)v;
1011 template<
typename BV>
1016 char value = char(get_octet(pos, octet_idx));
1017 return (value > octet) - (value < octet);
1022 template<
typename BV>
1038 blka[0] = get_block(row_idx+0, i0, j0);
1039 blka[1] = get_block(row_idx+1, i0, j0);
1040 blka[2] = get_block(row_idx+2, i0, j0);
1041 blka[3] = get_block(row_idx+3, i0, j0);
1044 if ((blk = blka[0])!=0)
1050 v |= unsigned(
bool(is_set));
1052 if ((blk = blka[1])!=0)
1058 v |= unsigned(
bool(is_set)) << 1u;
1060 if ((blk = blka[2])!=0)
1066 v |= unsigned(
bool(is_set)) << 2u;
1068 if ((blk = blka[3])!=0)
1074 v |= unsigned(
bool(is_set)) << 3u;
1081 template<
typename BV>
1093 for (
unsigned k = 0; k < rsize_; ++k)
1100 bv->
optimize(temp_block, opt_mode, st ? &stbv : 0);
1111 template<
typename BV>
1114 for (
unsigned k = 0; k < rsize_; ++k)
1123 bman.optimize_bit_block(i, j);
1134 template<
class Val,
class BV,
unsigned MAX_SIZE>
1138 effective_plains_(0)
1144 template<
class Val,
class BV,
unsigned MAX_SIZE>
1150 : bmatr_(sv_plains, ap, bv_max_size, alloc),
1152 effective_plains_(0)
1156 unsigned i = null_plain();
1157 bmatr_.construct_row(i)->init();
1163 template<
class Val,
class BV,
unsigned MAX_SIZE>
1166 : bmatr_(bsv.bmatr_),
1168 effective_plains_(bsv.effective_plains_)
1174 template<
class Val,
class BV,
unsigned MAX_SIZE>
1181 unsigned ni = this->null_plain();
1193 bv->set_range(0, size_-1);
1199 bmatr_.destruct_row(i);
1201 bmatr_.construct_row(i, *bv_src);
1207 template<
class Val,
class BV,
unsigned MAX_SIZE>
1213 bmatr_.swap(bsv.bmatr_);
1216 bm::xor_swap(effective_plains_, bsv.effective_plains_);
1222 template<
class Val,
class BV,
unsigned MAX_SIZE>
1225 unsigned plains = value_bits();
1228 bmatr_.destruct_row(i);
1238 template<
class Val,
class BV,
unsigned MAX_SIZE>
1246 return clear_range(right, left, set_null);
1248 unsigned plains = value_bits();
1249 for (
unsigned i = 0; i < plains; ++i)
1253 bv->set_range(left, right,
false);
1260 bv_null->set_range(left, right,
false);
1266 template<
class Val,
class BV,
unsigned MAX_SIZE>
1277 clear_range(sz, this->size_-1,
true);
1284 template<
class Val,
class BV,
unsigned MAX_SIZE>
1289 return (bv_null) ? (!bv_null->test(idx)) :
false;
1294 template<
class Val,
class BV,
unsigned MAX_SIZE>
1300 bv_null->insert(idx, not_null);
1305 template<
class Val,
class BV,
unsigned MAX_SIZE>
1312 bv = bmatr_.construct_row(i);
1314 if (i > effective_plains_ && i < value_bits())
1315 effective_plains_ = i;
1322 template<
class Val,
class BV,
unsigned MAX_SIZE>
1329 const unsigned plains =
sizeof(value_type) * 8;
1331 for (
unsigned i = element_idx * plains; i < (element_idx+1) * plains; i+=4)
1333 mask |= get_plain(i+0) ? (mask1 << (bidx+0)) : 0ull;
1334 mask |= get_plain(i+1) ? (mask1 << (bidx+1)) : 0ull;
1335 mask |= get_plain(i+2) ? (mask1 << (bidx+2)) : 0ull;
1336 mask |= get_plain(i+3) ? (mask1 << (bidx+3)) : 0ull;
1344 template<
class Val,
class BV,
unsigned MAX_SIZE>
1350 bmatr_.optimize(temp_block, opt_mode, &stbv);
1356 unsigned stored_plains = this->stored_plains();
1357 for (
unsigned j = 0; j < stored_plains; ++j)
1360 if (bv && (bv != bv_null))
1365 this->bmatr_.destruct_row(j);
1374 template<
class Val,
class BV,
unsigned MAX_SIZE>
1382 unsigned stored_plains = this->stored_plains();
1383 for (
unsigned j = 0; j < stored_plains; ++j)
1389 bv->calc_stat(&stbv);
1394 st->max_serialize_mem += 8;
1399 st->max_serialize_mem += 1 + 1 + 1 + 1 + 8 + (8 * this->stored_plains());
1400 st->max_serialize_mem += 1 + 8;
1405 template<
class Val,
class BV,
unsigned MAX_SIZE>
1409 for (
unsigned i = plain_idx; i < sv_value_plains; ++i)
1413 bv->clear_bit_no_check(idx);
1419 template<
class Val,
class BV,
unsigned MAX_SIZE>
1423 for (
unsigned i = plain_idx; i < sv_value_plains; ++i)
1427 bv->insert(idx,
false);
1433 template<
class Val,
class BV,
unsigned MAX_SIZE>
1436 for (
unsigned i = 0; i < sv_value_plains; ++i)
1446 template<
class Val,
class BV,
unsigned MAX_SIZE>
1452 if (this->size_ != arg_size)
1456 unsigned plains = this->plains();
1457 for (
unsigned j = 0; j < plains; ++j)
1477 bool eq = bv->equal(*arg_bv);
1484 const bvector_type* bv_null = this->get_null_bvector();
1485 const bvector_type* bv_null_arg = sv.get_null_bvector();
1488 if (bv_null == bv_null_arg)
1490 if (!bv_null || !bv_null_arg)
1494 bool eq = bv_null->equal(*bv_null_arg);
1503 template<
class Val,
class BV,
unsigned MAX_SIZE>
1515 plains = this->stored_plains();
1517 bv_null->copy_range(*bv_null_arg, left, right);
1521 plains = this->plains();
1523 for (
unsigned j = 0; j < plains; ++j)
1530 bv = this->get_plain(j);
1531 bv->copy_range(*arg_bv, left, right);