1 #ifndef BMBMATRIX__H__INCLUDED__
2 #define BMBMATRIX__H__INCLUDED__
243 template<
typename Val,
typename BV,
unsigned MAX_SIZE>
327 bool is_null(size_type idx)
const;
472 template<
typename BV>
477 : bv_size_(bv_max_size),
484 allocate_rows(rsize);
489 template<
typename BV>
497 template<
typename BV>
499 : bv_size_(bbm.bv_size_),
511 template<
typename BV>
513 : bv_size_(bbm.bv_size_),
525 template<
typename BV>
535 template<
typename BV>
545 template<
typename BV>
555 template<
typename BV>
559 #if defined(BM64_SSE4)
560 __m128i w0 = _mm_loadu_si128((__m128i*)(bv_rows_ + j));
561 __m128i w1 = _mm_loadu_si128((__m128i*)(bv_rows_ + j + 2));
562 w0 = _mm_or_si128(w0, w1);
563 return !_mm_testz_si128(w0, w0);
564 #elif defined(BM64_AVX2) || defined(BM64_AVX512)
565 __m256i w0 = _mm256_loadu_si256((__m256i*)(bv_rows_ + j));
566 return !_mm256_testz_si256(w0, w0);
568 bool b = bv_rows_[j + 0] || bv_rows_[j + 1] || bv_rows_[j + 2] || bv_rows_[j + 3];
575 template<
typename BV>
589 bv_rows_ = (bvector_type_ptr*)alloc_.alloc_ptr(rsize);
597 const bvector_type_ptr bv = bbm.
bv_rows_[i];
608 template<
typename BV>
615 bv_rows_ = (bvector_type_ptr*)alloc_.alloc_ptr(
unsigned(rsize));
629 template<
typename BV>
634 bvector_type_ptr bv = bv_rows_[i];
637 destruct_bvector(bv);
643 alloc_.free_ptr(bv_rows_,
unsigned(rsize_));
650 template<
typename BV>
660 bbm.alloc_ = alloc_tmp;
666 allocator_pool_type* pool_tmp = pool_;
668 bbm.pool_ = pool_tmp;
672 bvector_type_ptr* rtmp = bv_rows_;
673 bv_rows_ = bbm.bv_rows_;
679 template<
typename BV>
684 bvector_type_ptr bv = bv_rows_[row];
694 template<
typename BV>
699 bvector_type_ptr bv = bv_rows_[row];
714 template<
typename BV>
718 bvector_type_ptr bv = bv_rows_[row];
721 destruct_bvector(bv);
729 template<
typename BV>
734 #ifdef BM_NO_STL // C compatibility mode
738 BM_THROW(
false, BM_ERR_BADALLOC);
755 template<
typename BV>
758 #ifdef BM_NO_STL // C compatibility mode
768 template<
typename BV>
772 bvector_type_const_ptr bv = this->row(p);
776 return bman.get_block_ptr(i, j);
784 template<
typename BV>
794 for (; row < row_end; ++row)
801 bv = this->construct_row(row);
817 for (++row; row < row_end; ++row)
827 template<
typename BV>
837 for (; row < row_end; ++row)
844 bv = this->construct_row(row);
864 for (++row; row < row_end; ++row)
875 template<
typename BV>
891 unsigned row_idx = unsigned(octet_idx * 8);
893 blka[0] = get_block(row_idx+0, i0, j0);
894 blka[1] = get_block(row_idx+1, i0, j0);
895 blka[2] = get_block(row_idx+2, i0, j0);
896 blka[3] = get_block(row_idx+3, i0, j0);
897 blka[4] = get_block(row_idx+4, i0, j0);
898 blka[5] = get_block(row_idx+5, i0, j0);
899 blka[6] = get_block(row_idx+6, i0, j0);
900 blka[7] = get_block(row_idx+7, i0, j0);
903 if ((blk = blka[0])!=0)
909 v |= (unsigned)
bool(is_set);
911 if ((blk = blka[1])!=0)
917 v |= unsigned(
bool(is_set)) << 1u;
919 if ((blk = blka[2])!=0)
925 v |= unsigned(
bool(is_set)) << 2u;
927 if ((blk = blka[3])!=0)
933 v |= unsigned(
bool(is_set)) << 3u;
937 if ((blk = blka[4])!=0)
943 v |= unsigned(
bool(is_set)) << 4u;
945 if ((blk = blka[5])!=0)
951 v |= unsigned(
bool(is_set)) << 5u;
953 if ((blk = blka[6])!=0)
959 v |= unsigned(
bool(is_set)) << 6u;
961 if ((blk = blka[7])!=0)
967 v |= unsigned(
bool(is_set)) << 7u;
970 return (
unsigned char)v;
975 template<
typename BV>
980 char value = char(get_octet(pos, octet_idx));
981 return (value > octet) - (value < octet);
986 template<
typename BV>
1002 blka[0] = get_block(row_idx+0, i0, j0);
1003 blka[1] = get_block(row_idx+1, i0, j0);
1004 blka[2] = get_block(row_idx+2, i0, j0);
1005 blka[3] = get_block(row_idx+3, i0, j0);
1008 if ((blk = blka[0])!=0)
1014 v |= unsigned(
bool(is_set));
1016 if ((blk = blka[1])!=0)
1022 v |= unsigned(
bool(is_set)) << 1u;
1024 if ((blk = blka[2])!=0)
1030 v |= unsigned(
bool(is_set)) << 2u;
1032 if ((blk = blka[3])!=0)
1038 v |= unsigned(
bool(is_set)) << 3u;
1045 template<
typename BV>
1057 for (
unsigned k = 0; k < rsize_; ++k)
1064 bv->
optimize(temp_block, opt_mode, st ? &stbv : 0);
1080 template<
class Val,
class BV,
unsigned MAX_SIZE>
1084 effective_plains_(0)
1090 template<
class Val,
class BV,
unsigned MAX_SIZE>
1096 : bmatr_(sv_plains, ap, bv_max_size, alloc),
1098 effective_plains_(0)
1102 unsigned i = null_plain();
1103 bmatr_.construct_row(i)->init();
1109 template<
class Val,
class BV,
unsigned MAX_SIZE>
1112 : bmatr_(bsv.bmatr_),
1114 effective_plains_(bsv.effective_plains_)
1120 template<
class Val,
class BV,
unsigned MAX_SIZE>
1127 unsigned ni = this->null_plain();
1139 bv->set_range(0, size_-1);
1145 bmatr_.destruct_row(i);
1147 bmatr_.construct_row(i, *bv_src);
1153 template<
class Val,
class BV,
unsigned MAX_SIZE>
1159 bmatr_.swap(bsv.bmatr_);
1162 bm::xor_swap(effective_plains_, bsv.effective_plains_);
1168 template<
class Val,
class BV,
unsigned MAX_SIZE>
1171 unsigned plains = value_bits();
1174 bmatr_.destruct_row(i);
1184 template<
class Val,
class BV,
unsigned MAX_SIZE>
1192 return clear_range(right, left, set_null);
1194 unsigned plains = value_bits();
1195 for (
unsigned i = 0; i < plains; ++i)
1199 bv->set_range(left, right,
false);
1206 bv_null->set_range(left, right,
false);
1212 template<
class Val,
class BV,
unsigned MAX_SIZE>
1223 clear_range(sz, this->size_-1,
true);
1230 template<
class Val,
class BV,
unsigned MAX_SIZE>
1234 return (bv_null) ? (!bv_null->test(idx)) :
false;
1239 template<
class Val,
class BV,
unsigned MAX_SIZE>
1245 bv_null->insert(idx, not_null);
1250 template<
class Val,
class BV,
unsigned MAX_SIZE>
1257 bv = bmatr_.construct_row(i);
1259 if (i > effective_plains_ && i < value_bits())
1260 effective_plains_ = i;
1267 template<
class Val,
class BV,
unsigned MAX_SIZE>
1269 unsigned element_idx)
const
1274 const unsigned plains =
sizeof(
value_type) * 8;
1276 for (
unsigned i = element_idx * plains; i < (element_idx+1) * plains; i+=4)
1278 mask |= get_plain(i+0) ? (mask1 << (bidx+0)) : 0ull;
1279 mask |= get_plain(i+1) ? (mask1 << (bidx+1)) : 0ull;
1280 mask |= get_plain(i+2) ? (mask1 << (bidx+2)) : 0ull;
1281 mask |= get_plain(i+3) ? (mask1 << (bidx+3)) : 0ull;
1289 template<
class Val,
class BV,
unsigned MAX_SIZE>
1295 bmatr_.optimize(temp_block, opt_mode, &stbv);
1301 unsigned stored_plains = this->stored_plains();
1302 for (
unsigned j = 0; j < stored_plains; ++j)
1305 if (bv && (bv != bv_null))
1310 this->bmatr_.destruct_row(j);
1319 template<
class Val,
class BV,
unsigned MAX_SIZE>
1327 unsigned stored_plains = this->stored_plains();
1328 for (
unsigned j = 0; j < stored_plains; ++j)
1334 bv->calc_stat(&stbv);
1350 template<
class Val,
class BV,
unsigned MAX_SIZE>
1354 for (
unsigned i = plain_idx; i < sv_value_plains; ++i)
1358 bv->clear_bit_no_check(idx);
1364 template<
class Val,
class BV,
unsigned MAX_SIZE>
1368 for (
unsigned i = plain_idx; i < sv_value_plains; ++i)
1372 bv->insert(idx,
false);
1378 template<
class Val,
class BV,
unsigned MAX_SIZE>
1381 for (
unsigned i = 0; i < sv_value_plains; ++i)
1391 template<
class Val,
class BV,
unsigned MAX_SIZE>
1397 if (this->size_ != arg_size)
1401 unsigned plains = this->plains();
1402 for (
unsigned j = 0; j < plains; ++j)
1422 int cmp = bv->compare(*arg_bv);
1429 const bvector_type* bv_null = this->get_null_bvector();
1433 if (bv_null == bv_null_arg)
1435 if (!bv_null || !bv_null_arg)
1439 int cmp = bv_null->compare(*bv_null);