00001 #ifndef BMALGO_IMPL__H__INCLUDED__
00002 #define BMALGO_IMPL__H__INCLUDED__
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029 #ifdef _MSC_VER
00030 #pragma warning( disable : 4311 4312)
00031 #endif
00032
00033 #include "bmdef.h"
00034
00035 namespace bm
00036 {
00037
00038
00039
00040
00041
00042
00043
00044
00045
00046
00047
00048
00049
00050
00051
00052
00053 enum distance_metric
00054 {
00055 COUNT_AND = set_COUNT_AND,
00056 COUNT_XOR = set_COUNT_XOR,
00057 COUNT_OR = set_COUNT_OR,
00058 COUNT_SUB_AB = set_COUNT_SUB_AB,
00059 COUNT_SUB_BA = set_COUNT_SUB_BA,
00060 COUNT_A = set_COUNT_A,
00061 COUNT_B = set_COUNT_B
00062 };
00063
00064
00065
00066
00067
00068 inline
00069 distance_metric operation2metric(set_operation op)
00070 {
00071 BM_ASSERT(is_const_set_operation(op));
00072 if (op == set_COUNT) op = set_COUNT_B;
00073
00074
00075 return (distance_metric) op;
00076 }
00077
00078
00079
00080
00081
00082
00083 struct distance_metric_descriptor
00084 {
00085 distance_metric metric;
00086 bm::id_t result;
00087
00088 distance_metric_descriptor(distance_metric m)
00089 : metric(m),
00090 result(0)
00091 {}
00092 distance_metric_descriptor()
00093 : metric(bm::COUNT_XOR),
00094 result(0)
00095 {}
00096
00097
00098
00099
00100 void reset()
00101 {
00102 result = 0;
00103 }
00104 };
00105
00106
00107
00108
00109
00110
00111
00112
00113 inline
00114 void combine_count_operation_with_block(const bm::word_t* blk,
00115 unsigned gap,
00116 const bm::word_t* arg_blk,
00117 int arg_gap,
00118 bm::word_t* temp_blk,
00119 distance_metric_descriptor* dmit,
00120 distance_metric_descriptor* dmit_end)
00121
00122 {
00123 gap_word_t* res=0;
00124
00125 gap_word_t* g1 = BMGAP_PTR(blk);
00126 gap_word_t* g2 = BMGAP_PTR(arg_blk);
00127
00128 if (gap)
00129 {
00130 if (arg_gap)
00131 {
00132
00133 gap_word_t tmp_buf[bm::gap_equiv_len * 3];
00134
00135 for (distance_metric_descriptor* it = dmit;it < dmit_end; ++it)
00136 {
00137 distance_metric_descriptor& dmd = *it;
00138 unsigned dsize = 0;
00139
00140 switch (dmd.metric)
00141 {
00142 case bm::COUNT_AND:
00143 res = gap_operation_and(g1, g2, tmp_buf, dsize);
00144 break;
00145 case bm::COUNT_OR:
00146 res = gap_operation_or(g1, g2, tmp_buf, dsize);
00147 break;
00148 case bm::COUNT_SUB_AB:
00149 res = gap_operation_sub(g1, g2, tmp_buf, dsize);
00150 break;
00151 case bm::COUNT_SUB_BA:
00152 res = gap_operation_sub(g2, g1, tmp_buf, dsize);
00153 break;
00154 case bm::COUNT_XOR:
00155 res = gap_operation_xor(g1, g2, tmp_buf, dsize);
00156 break;
00157 case bm::COUNT_A:
00158 res = g1;
00159 break;
00160 case bm::COUNT_B:
00161 res = g2;
00162 break;
00163 }
00164
00165 if (res)
00166 dmd.result += gap_bit_count(res, dsize);
00167
00168 }
00169
00170 return;
00171
00172 }
00173 else
00174 {
00175 for (distance_metric_descriptor* it = dmit;it < dmit_end; ++it)
00176 {
00177 distance_metric_descriptor& dmd = *it;
00178
00179 switch (dmd.metric)
00180 {
00181 case bm::COUNT_AND:
00182 if (arg_blk)
00183 dmd.result += gap_bitset_and_count(arg_blk, g1);
00184 break;
00185 case bm::COUNT_OR:
00186 if (!arg_blk)
00187 dmd.result += gap_bit_count(g1);
00188 else
00189 dmd.result += gap_bitset_or_count(arg_blk, g1);
00190 break;
00191 case bm::COUNT_SUB_AB:
00192 gap_convert_to_bitset((bm::word_t*) temp_blk, g1);
00193 dmd.result +=
00194 bit_operation_sub_count((bm::word_t*)temp_blk,
00195 ((bm::word_t*)temp_blk) + bm::set_block_size,
00196 arg_blk);
00197
00198 break;
00199 case bm::COUNT_SUB_BA:
00200 dmd.metric = bm::COUNT_SUB_AB;
00201 combine_count_operation_with_block(arg_blk,
00202 arg_gap,
00203 blk,
00204 gap,
00205 temp_blk,
00206 it, it+1);
00207 dmd.metric = bm::COUNT_SUB_BA;
00208 break;
00209 case bm::COUNT_XOR:
00210 if (!arg_blk)
00211 dmd.result += gap_bit_count(g1);
00212 else
00213 dmd.result += gap_bitset_xor_count(arg_blk, g1);
00214 break;
00215 case bm::COUNT_A:
00216 if (g1)
00217 dmd.result += gap_bit_count(g1);
00218 break;
00219 case bm::COUNT_B:
00220 if (arg_blk)
00221 {
00222 dmd.result +=
00223 bit_block_calc_count(arg_blk,
00224 arg_blk + bm::set_block_size);
00225 }
00226 break;
00227 }
00228
00229 }
00230
00231 return;
00232
00233 }
00234 }
00235 else
00236 {
00237 if (arg_gap)
00238 {
00239 for (distance_metric_descriptor* it = dmit;it < dmit_end; ++it)
00240 {
00241 distance_metric_descriptor& dmd = *it;
00242
00243 switch (dmd.metric)
00244 {
00245 case bm::COUNT_AND:
00246 if (blk)
00247 dmd.result += gap_bitset_and_count(blk, g2);
00248 break;
00249 case bm::COUNT_OR:
00250 if (!blk)
00251 dmd.result += gap_bit_count(g2);
00252 else
00253 dmd.result += gap_bitset_or_count(blk, g2);
00254 break;
00255 case bm::COUNT_SUB_AB:
00256 if (blk)
00257 dmd.result += gap_bitset_sub_count(blk, g2);
00258 break;
00259 case bm::COUNT_SUB_BA:
00260 dmd.metric = bm::COUNT_SUB_AB;
00261 combine_count_operation_with_block(arg_blk,
00262 arg_gap,
00263 blk,
00264 gap,
00265 temp_blk,
00266 it, it+1);
00267 dmd.metric = bm::COUNT_SUB_BA;
00268 break;
00269 case bm::COUNT_XOR:
00270 if (!blk)
00271 dmd.result += gap_bit_count(g2);
00272 else
00273 dmd.result += gap_bitset_xor_count(blk, g2);
00274 break;
00275 case bm::COUNT_A:
00276 if (blk)
00277 {
00278 dmd.result +=
00279 bit_block_calc_count(blk,
00280 blk + bm::set_block_size);
00281 }
00282 break;
00283 case bm::COUNT_B:
00284 if (g2)
00285 dmd.result += gap_bit_count(g2);
00286 break;
00287 }
00288
00289 }
00290
00291 return;
00292 }
00293 }
00294
00295
00296
00297
00298
00299 const bm::word_t* blk_end;
00300
00301
00302 blk_end = blk + (bm::set_block_size);
00303
00304
00305
00306 for (distance_metric_descriptor* it = dmit; it < dmit_end; ++it)
00307 {
00308 distance_metric_descriptor& dmd = *it;
00309 bit_operation_count_func_type gfunc =
00310 operation_functions<true>::bit_operation_count(dmd.metric);
00311 if (gfunc)
00312 {
00313 dmd.result += (*gfunc)(blk, blk_end, arg_blk);
00314 }
00315 else
00316 {
00317 switch (dmd.metric)
00318 {
00319 case bm::COUNT_A:
00320 if (blk)
00321 dmd.result += bit_block_calc_count(blk, blk_end);
00322 break;
00323 case bm::COUNT_B:
00324 if (arg_blk)
00325 dmd.result +=
00326 bit_block_calc_count(arg_blk,
00327 arg_blk + bm::set_block_size);
00328 break;
00329 default:
00330 BM_ASSERT(0);
00331 }
00332 }
00333
00334 }
00335 }
00336
00337
00338
00339
00340
00341
00342 inline
00343 void combine_any_operation_with_block(const bm::word_t* blk,
00344 unsigned gap,
00345 const bm::word_t* arg_blk,
00346 int arg_gap,
00347 bm::word_t* temp_blk,
00348 distance_metric_descriptor* dmit,
00349 distance_metric_descriptor* dmit_end)
00350
00351 {
00352 gap_word_t* res=0;
00353
00354 gap_word_t* g1 = BMGAP_PTR(blk);
00355 gap_word_t* g2 = BMGAP_PTR(arg_blk);
00356
00357 if (gap)
00358 {
00359 if (arg_gap)
00360 {
00361 gap_word_t tmp_buf[bm::gap_max_buff_len * 3];
00362
00363 for (distance_metric_descriptor* it = dmit;it < dmit_end; ++it)
00364 {
00365 distance_metric_descriptor& dmd = *it;
00366 if (dmd.result)
00367 {
00368 continue;
00369 }
00370 res = 0;
00371 unsigned dsize = 0;
00372 switch (dmd.metric)
00373 {
00374 case bm::COUNT_AND:
00375 dmd.result += gap_operation_any_and(g1, g2);
00376 break;
00377 case bm::COUNT_OR:
00378 res = gap_operation_or(g1, g2, tmp_buf, dsize);
00379 break;
00380 case bm::COUNT_SUB_AB:
00381 dmd.result += gap_operation_any_sub(g1, g2);
00382 break;
00383 case bm::COUNT_SUB_BA:
00384 dmd.result += gap_operation_any_sub(g2, g1);
00385 break;
00386 case bm::COUNT_XOR:
00387 dmd.result += gap_operation_any_xor(g1, g2);
00388 break;
00389 case bm::COUNT_A:
00390 res = g1;
00391 break;
00392 case bm::COUNT_B:
00393 res = g2;
00394 break;
00395 }
00396 if (res)
00397 dmd.result += !gap_is_all_zero(res, bm::gap_max_bits);
00398
00399 }
00400
00401 return;
00402
00403 }
00404 else
00405 {
00406 for (distance_metric_descriptor* it = dmit;it < dmit_end; ++it)
00407 {
00408 distance_metric_descriptor& dmd = *it;
00409 if (dmd.result)
00410 {
00411 continue;
00412 }
00413
00414 switch (dmd.metric)
00415 {
00416 case bm::COUNT_AND:
00417 if (arg_blk)
00418 dmd.result += gap_bitset_and_any(arg_blk, g1);
00419 break;
00420 case bm::COUNT_OR:
00421 if (!arg_blk)
00422 dmd.result += !gap_is_all_zero(g1, bm::gap_max_bits);
00423 else
00424 dmd.result += gap_bitset_or_any(arg_blk, g1);
00425 break;
00426 case bm::COUNT_SUB_AB:
00427 gap_convert_to_bitset((bm::word_t*) temp_blk, g1);
00428 dmd.result +=
00429 bit_operation_sub_any((bm::word_t*)temp_blk,
00430 ((bm::word_t*)temp_blk) + bm::set_block_size,
00431 arg_blk);
00432
00433 break;
00434 case bm::COUNT_SUB_BA:
00435 dmd.metric = bm::COUNT_SUB_AB;
00436 combine_any_operation_with_block(arg_blk,
00437 arg_gap,
00438 blk,
00439 gap,
00440 temp_blk,
00441 it, it+1);
00442 dmd.metric = bm::COUNT_SUB_BA;
00443 break;
00444 case bm::COUNT_XOR:
00445 if (!arg_blk)
00446 dmd.result += !gap_is_all_zero(g1, bm::gap_max_bits);
00447 else
00448 dmd.result += gap_bitset_xor_any(arg_blk, g1);
00449 break;
00450 case bm::COUNT_A:
00451 if (g1)
00452 dmd.result += !gap_is_all_zero(g1, bm::gap_max_bits);
00453 break;
00454 case bm::COUNT_B:
00455 if (arg_blk)
00456 {
00457 dmd.result +=
00458 !bit_is_all_zero((bm::wordop_t*)arg_blk,
00459 (bm::wordop_t*)(arg_blk + bm::set_block_size));
00460 }
00461 break;
00462 }
00463
00464 }
00465
00466 return;
00467
00468 }
00469 }
00470 else
00471 {
00472 if (arg_gap)
00473 {
00474 for (distance_metric_descriptor* it = dmit;it < dmit_end; ++it)
00475 {
00476 distance_metric_descriptor& dmd = *it;
00477 if (dmd.result)
00478 {
00479 continue;
00480 }
00481
00482 switch (dmd.metric)
00483 {
00484 case bm::COUNT_AND:
00485 if (blk)
00486 dmd.result += gap_bitset_and_any(blk, g2);
00487 break;
00488 case bm::COUNT_OR:
00489 if (!blk)
00490 dmd.result += !gap_is_all_zero(g2, bm::gap_max_bits);
00491 else
00492 dmd.result += gap_bitset_or_any(blk, g2);
00493 break;
00494 case bm::COUNT_SUB_AB:
00495 if (blk)
00496 dmd.result += gap_bitset_sub_any(blk, g2);
00497 break;
00498 case bm::COUNT_SUB_BA:
00499 dmd.metric = bm::COUNT_SUB_AB;
00500 combine_any_operation_with_block(arg_blk,
00501 arg_gap,
00502 blk,
00503 gap,
00504 temp_blk,
00505 it, it+1);
00506 dmd.metric = bm::COUNT_SUB_BA;
00507 break;
00508 case bm::COUNT_XOR:
00509 if (!blk)
00510 dmd.result += !gap_is_all_zero(g2, bm::gap_max_bits);
00511 else
00512 dmd.result += gap_bitset_xor_any(blk, g2);
00513 break;
00514 case bm::COUNT_A:
00515 if (blk)
00516 {
00517 dmd.result+=
00518 !bit_is_all_zero((bm::wordop_t*)blk,
00519 (bm::wordop_t*)blk + bm::set_block_size);
00520 }
00521 break;
00522 case bm::COUNT_B:
00523 if (g2)
00524 dmd.result += !gap_is_all_zero(g2, bm::gap_max_bits);
00525 break;
00526 }
00527
00528 }
00529
00530 return;
00531 }
00532 }
00533
00534
00535
00536
00537
00538 const bm::word_t* blk_end;
00539 const bm::word_t* arg_end;
00540
00541 blk_end = blk + (bm::set_block_size);
00542 arg_end = arg_blk + (bm::set_block_size);
00543
00544 for (distance_metric_descriptor* it = dmit; it < dmit_end; ++it)
00545 {
00546 distance_metric_descriptor& dmd = *it;
00547 if (dmd.result)
00548 {
00549 continue;
00550 }
00551
00552 switch (dmd.metric)
00553 {
00554 case bm::COUNT_AND:
00555 dmd.result +=
00556 bit_operation_and_any(blk, blk_end, arg_blk);
00557 break;
00558 case bm::COUNT_OR:
00559 dmd.result +=
00560 bit_operation_or_any(blk, blk_end, arg_blk);
00561 break;
00562 case bm::COUNT_SUB_AB:
00563 dmd.result +=
00564 bit_operation_sub_any(blk, blk_end, arg_blk);
00565 break;
00566 case bm::COUNT_SUB_BA:
00567 dmd.result +=
00568 bit_operation_sub_any(arg_blk, arg_end, blk);
00569 break;
00570 case bm::COUNT_XOR:
00571 dmd.result +=
00572 bit_operation_xor_any(blk, blk_end, arg_blk);
00573 break;
00574 case bm::COUNT_A:
00575 if (blk)
00576 dmd.result += !bit_is_all_zero((bm::wordop_t*)blk,
00577 (bm::wordop_t*)blk_end);
00578 break;
00579 case bm::COUNT_B:
00580 if (arg_blk)
00581 dmd.result += !bit_is_all_zero((bm::wordop_t*)arg_blk,
00582 (bm::wordop_t*)arg_end);
00583 break;
00584 }
00585
00586 }
00587 }
00588
00589
00590
00591
00592
00593
00594
00595
00596 inline
00597 unsigned combine_count_operation_with_block(const bm::word_t* blk,
00598 unsigned gap,
00599 const bm::word_t* arg_blk,
00600 int arg_gap,
00601 bm::word_t* temp_blk,
00602 distance_metric metric)
00603 {
00604 distance_metric_descriptor dmd(metric);
00605 combine_count_operation_with_block(blk, gap,
00606 arg_blk, arg_gap,
00607 temp_blk,
00608 &dmd, &dmd+1);
00609 return dmd.result;
00610 }
00611
00612
00613
00614
00615
00616
00617
00618 inline
00619 unsigned combine_any_operation_with_block(const bm::word_t* blk,
00620 unsigned gap,
00621 const bm::word_t* arg_blk,
00622 int arg_gap,
00623 bm::word_t* temp_blk,
00624 distance_metric metric)
00625 {
00626 distance_metric_descriptor dmd(metric);
00627 combine_any_operation_with_block(blk, gap,
00628 arg_blk, arg_gap,
00629 temp_blk,
00630 &dmd, &dmd+1);
00631 return dmd.result;
00632 }
00633
00634
00635
00636
00637
00638
00639
00640
00641 template<class BV>
00642 bm::word_t* distance_stage(const BV& bv1,
00643 const distance_metric_descriptor* dmit,
00644 const distance_metric_descriptor* dmit_end,
00645 bool* is_all_and)
00646 {
00647 bm::word_t* temp_blk = 0;
00648 for (const distance_metric_descriptor* it = dmit; it < dmit_end; ++it)
00649 {
00650
00651 if (temp_blk == 0)
00652 {
00653 if (it->metric == bm::COUNT_SUB_AB ||
00654 it->metric == bm::COUNT_SUB_BA)
00655 {
00656 temp_blk = bv1.allocate_tempblock();
00657 }
00658 }
00659 if (it->metric != bm::COUNT_AND)
00660 {
00661 *is_all_and = false;
00662 }
00663 }
00664 return temp_blk;
00665 }
00666
00667
00668
00669
00670
00671
00672
00673
00674
00675
00676
00677
00678
00679
00680
00681
00682
00683
00684
00685
00686
00687 template<class BV>
00688 void distance_operation(const BV& bv1,
00689 const BV& bv2,
00690 distance_metric_descriptor* dmit,
00691 distance_metric_descriptor* dmit_end)
00692 {
00693 const typename BV::blocks_manager_type& bman1 = bv1.get_blocks_manager();
00694 const typename BV::blocks_manager_type& bman2 = bv2.get_blocks_manager();
00695
00696 bool is_all_and = true;
00697 bm::word_t* temp_blk = distance_stage(bv1, dmit, dmit_end, &is_all_and);
00698
00699 bm::word_t*** blk_root = bman1.get_rootblock();
00700 unsigned block_idx = 0;
00701 unsigned i, j;
00702
00703 const bm::word_t* blk;
00704 const bm::word_t* arg_blk;
00705 bool blk_gap;
00706 bool arg_gap;
00707
00708 BM_SET_MMX_GUARD
00709
00710 unsigned effective_top_block_size = bman1.effective_top_block_size();
00711 unsigned ebs2 = bman2.effective_top_block_size();
00712 if (ebs2 > effective_top_block_size)
00713 effective_top_block_size = ebs2;
00714
00715 for (i = 0; i < effective_top_block_size; ++i)
00716 {
00717 bm::word_t** blk_blk = blk_root[i];
00718
00719 if (blk_blk == 0)
00720 {
00721
00722 if (is_all_and)
00723 {
00724 block_idx += bm::set_array_size;
00725 continue;
00726 }
00727 const bm::word_t* const* bvbb = bman2.get_topblock(i);
00728 if (bvbb == 0)
00729 {
00730 block_idx += bm::set_array_size;
00731 continue;
00732 }
00733
00734 blk = 0;
00735 blk_gap = false;
00736
00737 for (j = 0; j < bm::set_array_size; ++j,++block_idx)
00738 {
00739 arg_blk = bman2.get_block(i, j);
00740 arg_gap = BM_IS_GAP(bman2, arg_blk, block_idx);
00741
00742 if (!arg_blk)
00743 continue;
00744 combine_count_operation_with_block(blk, blk_gap,
00745 arg_blk, arg_gap,
00746 temp_blk,
00747 dmit, dmit_end);
00748 }
00749 continue;
00750 }
00751
00752 for (j = 0; j < bm::set_array_size; ++j, ++block_idx)
00753 {
00754 blk = blk_blk[j];
00755 if (blk == 0 && is_all_and)
00756 continue;
00757
00758 arg_blk = bman2.get_block(i, j);
00759
00760 if (blk == 0 && arg_blk == 0)
00761 continue;
00762
00763 arg_gap = BM_IS_GAP(bman2, arg_blk, block_idx);
00764 blk_gap = BM_IS_GAP(bman1, blk, block_idx);
00765
00766 combine_count_operation_with_block(blk, blk_gap,
00767 arg_blk, arg_gap,
00768 temp_blk,
00769 dmit, dmit_end);
00770
00771
00772 }
00773
00774 }
00775
00776 if (temp_blk)
00777 {
00778 bv1.free_tempblock(temp_blk);
00779 }
00780
00781 }
00782
00783
00784
00785
00786
00787
00788
00789
00790
00791
00792
00793
00794
00795
00796
00797
00798
00799
00800
00801
00802
00803
00804
00805
00806 template<class BV>
00807 void distance_operation_any(const BV& bv1,
00808 const BV& bv2,
00809 distance_metric_descriptor* dmit,
00810 distance_metric_descriptor* dmit_end)
00811 {
00812 const typename BV::blocks_manager_type& bman1 = bv1.get_blocks_manager();
00813 const typename BV::blocks_manager_type& bman2 = bv2.get_blocks_manager();
00814
00815 bool is_all_and = true;
00816 bm::word_t* temp_blk = distance_stage(bv1, dmit, dmit_end, &is_all_and);
00817
00818 bm::word_t*** blk_root = bman1.get_rootblock();
00819 unsigned block_idx = 0;
00820 unsigned i, j;
00821
00822 const bm::word_t* blk;
00823 const bm::word_t* arg_blk;
00824 bool blk_gap;
00825 bool arg_gap;
00826
00827 BM_SET_MMX_GUARD
00828
00829 unsigned effective_top_block_size = bman1.effective_top_block_size();
00830 unsigned ebs2 = bman2.effective_top_block_size();
00831 if (ebs2 > effective_top_block_size)
00832 effective_top_block_size = ebs2;
00833
00834 for (i = 0; i < effective_top_block_size; ++i)
00835 {
00836 bm::word_t** blk_blk = blk_root[i];
00837
00838 if (blk_blk == 0)
00839 {
00840
00841 if (is_all_and)
00842 {
00843 block_idx += bm::set_array_size;
00844 continue;
00845 }
00846
00847 const bm::word_t* const* bvbb = bman2.get_topblock(i);
00848 if (bvbb == 0)
00849 {
00850 block_idx += bm::set_array_size;
00851 continue;
00852 }
00853
00854 blk = 0;
00855 blk_gap = false;
00856
00857 for (j = 0; j < bm::set_array_size; ++j,++block_idx)
00858 {
00859 arg_blk = bman2.get_block(i, j);
00860 arg_gap = BM_IS_GAP(bman2, arg_blk, block_idx);
00861
00862 if (!arg_blk)
00863 continue;
00864 combine_any_operation_with_block(blk, blk_gap,
00865 arg_blk, arg_gap,
00866 temp_blk,
00867 dmit, dmit_end);
00868
00869
00870 bool all_resolved = false;
00871 distance_metric_descriptor* it=dmit;
00872 do
00873 {
00874 if (!it->result)
00875 {
00876 all_resolved = false;
00877 break;
00878 }
00879 ++it;
00880 } while (it < dmit_end);
00881 if (all_resolved)
00882 goto return_proc;
00883 }
00884
00885 continue;
00886 }
00887
00888 for (j = 0; j < bm::set_array_size; ++j, ++block_idx)
00889 {
00890 blk = blk_blk[j];
00891 if (blk == 0 && is_all_and)
00892 continue;
00893
00894 arg_blk = bman2.get_block(i, j);
00895
00896 if (blk == 0 && arg_blk == 0)
00897 continue;
00898
00899 arg_gap = BM_IS_GAP(bman2, arg_blk, block_idx);
00900 blk_gap = BM_IS_GAP(bman1, blk, block_idx);
00901
00902 combine_any_operation_with_block(blk, blk_gap,
00903 arg_blk, arg_gap,
00904 temp_blk,
00905 dmit, dmit_end);
00906
00907
00908 bool all_resolved = false;
00909 distance_metric_descriptor* it=dmit;
00910 do
00911 {
00912 if (!it->result)
00913 {
00914 all_resolved = false;
00915 break;
00916 }
00917 ++it;
00918 } while (it < dmit_end);
00919 if (all_resolved)
00920 goto return_proc;
00921
00922 }
00923
00924 }
00925 return_proc:
00926 if (temp_blk)
00927 {
00928 bv1.free_tempblock(temp_blk);
00929 }
00930
00931 }
00932
00933
00934
00935
00936
00937
00938
00939
00940
00941
00942 template<class BV>
00943 bm::id_t count_and(const BV& bv1, const BV& bv2)
00944 {
00945 distance_metric_descriptor dmd(bm::COUNT_AND);
00946
00947 distance_operation(bv1, bv2, &dmd, &dmd+1);
00948 return dmd.result;
00949 }
00950
00951
00952
00953
00954
00955
00956
00957
00958 template<class BV>
00959 bm::id_t any_and(const BV& bv1, const BV& bv2)
00960 {
00961 distance_metric_descriptor dmd(bm::COUNT_AND);
00962
00963 distance_operation_any(bv1, bv2, &dmd, &dmd+1);
00964 return dmd.result;
00965 }
00966
00967
00968
00969
00970
00971
00972
00973
00974
00975
00976 template<class BV>
00977 bm::id_t count_xor(const BV& bv1, const BV& bv2)
00978 {
00979 distance_metric_descriptor dmd(bm::COUNT_XOR);
00980
00981 distance_operation(bv1, bv2, &dmd, &dmd+1);
00982 return dmd.result;
00983 }
00984
00985
00986
00987
00988
00989
00990
00991
00992 template<class BV>
00993 bm::id_t any_xor(const BV& bv1, const BV& bv2)
00994 {
00995 distance_metric_descriptor dmd(bm::COUNT_XOR);
00996
00997 distance_operation_any(bv1, bv2, &dmd, &dmd+1);
00998 return dmd.result;
00999 }
01000
01001
01002
01003
01004
01005
01006
01007
01008
01009
01010 template<class BV>
01011 bm::id_t count_sub(const BV& bv1, const BV& bv2)
01012 {
01013 distance_metric_descriptor dmd(bm::COUNT_SUB_AB);
01014
01015 distance_operation(bv1, bv2, &dmd, &dmd+1);
01016 return dmd.result;
01017 }
01018
01019
01020
01021
01022
01023
01024
01025
01026
01027 template<class BV>
01028 bm::id_t any_sub(const BV& bv1, const BV& bv2)
01029 {
01030 distance_metric_descriptor dmd(bm::COUNT_SUB_AB);
01031
01032 distance_operation_any(bv1, bv2, &dmd, &dmd+1);
01033 return dmd.result;
01034 }
01035
01036
01037
01038
01039
01040
01041
01042
01043
01044 template<class BV>
01045 bm::id_t count_or(const BV& bv1, const BV& bv2)
01046 {
01047 distance_metric_descriptor dmd(bm::COUNT_OR);
01048
01049 distance_operation(bv1, bv2, &dmd, &dmd+1);
01050 return dmd.result;
01051 }
01052
01053
01054
01055
01056
01057
01058
01059
01060 template<class BV>
01061 bm::id_t any_or(const BV& bv1, const BV& bv2)
01062 {
01063 distance_metric_descriptor dmd(bm::COUNT_OR);
01064
01065 distance_operation_any(bv1, bv2, &dmd, &dmd+1);
01066 return dmd.result;
01067 }
01068
01069
01070
01071
01072
01073
01074 template<class It>
01075 It block_range_scan(It first, It last, unsigned nblock, unsigned* max_id)
01076 {
01077 It right;
01078 for (right = first; right != last; ++right)
01079 {
01080 unsigned v = unsigned(*right);
01081 BM_ASSERT(v < bm::id_max);
01082 if (v >= *max_id)
01083 *max_id = v;
01084 unsigned nb = v >> bm::set_block_shift;
01085 if (nb != nblock)
01086 break;
01087 }
01088 return right;
01089 }
01090
01091
01092
01093
01094
01095
01096
01097
01098
01099
01100
01101
01102
01103
01104 template<class BV, class It>
01105 void combine_or(BV& bv, It first, It last)
01106 {
01107 typename BV::blocks_manager_type& bman = bv.get_blocks_manager();
01108 unsigned max_id = 0;
01109
01110 while (first < last)
01111 {
01112 unsigned nblock = unsigned((*first) >> bm::set_block_shift);
01113 It right = block_range_scan(first, last, nblock, &max_id);
01114
01115 if (max_id >= bv.size())
01116 {
01117 BM_ASSERT(max_id < bm::id_max);
01118 bv.resize(max_id + 1);
01119 }
01120
01121
01122
01123 label1:
01124
01125 int block_type;
01126 bm::word_t* blk =
01127 bman.check_allocate_block(nblock,
01128 true,
01129 bv.get_new_blocks_strat(),
01130 &block_type);
01131 if (!blk)
01132 continue;
01133
01134 if (block_type == 1)
01135 {
01136 bm::gap_word_t* gap_blk = BMGAP_PTR(blk);
01137 unsigned threshold = bm::gap_limit(gap_blk, bman.glen());
01138
01139 for (; first < right; ++first)
01140 {
01141 unsigned is_set;
01142 unsigned nbit = (*first) & bm::set_block_mask;
01143
01144 unsigned new_block_len =
01145 gap_set_value(true, gap_blk, nbit, &is_set);
01146 if (new_block_len > threshold)
01147 {
01148 bman.extend_gap_block(nblock, gap_blk);
01149 ++first;
01150 goto label1;
01151 }
01152 }
01153 }
01154 else
01155 {
01156 for (; first < right; ++first)
01157 {
01158 unsigned nbit = unsigned(*first & bm::set_block_mask);
01159 unsigned nword = unsigned(nbit >> bm::set_word_shift);
01160 nbit &= bm::set_word_mask;
01161 blk[nword] |= (bm::word_t)1 << nbit;
01162 }
01163 }
01164 }
01165
01166 bv.forget_count();
01167 }
01168
01169
01170
01171
01172
01173
01174
01175
01176
01177
01178
01179
01180
01181
01182
01183 template<class BV, class It>
01184 void combine_xor(BV& bv, It first, It last)
01185 {
01186 typename BV::blocks_manager_type& bman = bv.get_blocks_manager();
01187 unsigned max_id = 0;
01188
01189 while (first < last)
01190 {
01191 unsigned nblock = unsigned((*first) >> bm::set_block_shift);
01192 It right = block_range_scan(first, last, nblock, &max_id);
01193
01194 if (max_id >= bv.size())
01195 {
01196 BM_ASSERT(max_id < bm::id_max);
01197 bv.resize(max_id + 1);
01198 }
01199
01200
01201
01202 label1:
01203
01204 int block_type;
01205 bm::word_t* blk =
01206 bman.check_allocate_block(nblock,
01207 true,
01208 bv.get_new_blocks_strat(),
01209 &block_type,
01210 false );
01211 BM_ASSERT(blk);
01212
01213 if (block_type == 1)
01214 {
01215 bm::gap_word_t* gap_blk = BMGAP_PTR(blk);
01216 unsigned threshold = bm::gap_limit(gap_blk, bman.glen());
01217
01218 for (; first < right; ++first)
01219 {
01220 unsigned is_set;
01221 unsigned nbit = (*first) & bm::set_block_mask;
01222
01223 is_set = gap_test(gap_blk, nbit);
01224 BM_ASSERT(is_set <= 1);
01225 is_set ^= 1;
01226
01227 unsigned new_block_len =
01228 gap_set_value(is_set, gap_blk, nbit, &is_set);
01229 if (new_block_len > threshold)
01230 {
01231 bman.extend_gap_block(nblock, gap_blk);
01232 ++first;
01233 goto label1;
01234 }
01235 }
01236 }
01237 else
01238 {
01239 for (; first < right; ++first)
01240 {
01241 unsigned nbit = unsigned(*first & bm::set_block_mask);
01242 unsigned nword = unsigned(nbit >> bm::set_word_shift);
01243 nbit &= bm::set_word_mask;
01244 blk[nword] ^= (bm::word_t)1 << nbit;
01245 }
01246 }
01247 }
01248
01249 bv.forget_count();
01250 }
01251
01252
01253
01254
01255
01256
01257
01258
01259
01260
01261
01262
01263
01264
01265
01266
01267 template<class BV, class It>
01268 void combine_sub(BV& bv, It first, It last)
01269 {
01270 typename BV::blocks_manager_type& bman = bv.get_blocks_manager();
01271 unsigned max_id = 0;
01272
01273 while (first < last)
01274 {
01275 unsigned nblock = unsigned((*first) >> bm::set_block_shift);
01276 It right = block_range_scan(first, last, nblock, &max_id);
01277
01278 if (max_id >= bv.size())
01279 {
01280 BM_ASSERT(max_id < bm::id_max);
01281 bv.resize(max_id + 1);
01282 }
01283
01284
01285
01286 label1:
01287
01288 int block_type;
01289 bm::word_t* blk =
01290 bman.check_allocate_block(nblock,
01291 false,
01292 bv.get_new_blocks_strat(),
01293 &block_type);
01294
01295 if (!blk)
01296 continue;
01297
01298 if (block_type == 1)
01299 {
01300 bm::gap_word_t* gap_blk = BMGAP_PTR(blk);
01301 unsigned threshold = bm::gap_limit(gap_blk, bman.glen());
01302
01303 for (; first < right; ++first)
01304 {
01305 unsigned is_set;
01306 unsigned nbit = (*first) & bm::set_block_mask;
01307
01308 is_set = gap_test(gap_blk, nbit);
01309 if (!is_set)
01310 continue;
01311
01312 unsigned new_block_len =
01313 gap_set_value(false, gap_blk, nbit, &is_set);
01314 if (new_block_len > threshold)
01315 {
01316 bman.extend_gap_block(nblock, gap_blk);
01317 ++first;
01318 goto label1;
01319 }
01320 }
01321 }
01322 else
01323 {
01324 for (; first < right; ++first)
01325 {
01326 unsigned nbit = unsigned(*first & bm::set_block_mask);
01327 unsigned nword = unsigned(nbit >> bm::set_word_shift);
01328 nbit &= bm::set_word_mask;
01329 blk[nword] &= ~((bm::word_t)1 << nbit);
01330 }
01331 }
01332 }
01333
01334 bv.forget_count();
01335 }
01336
01337
01338
01339
01340
01341
01342
01343
01344
01345
01346
01347
01348
01349 template<class BV, class It>
01350 void combine_and_sorted(BV& bv, It first, It last)
01351 {
01352 bm::id_t prev = 0;
01353 for ( ;first < last; ++first)
01354 {
01355 bm::id_t id = *first;
01356 BM_ASSERT(id >= prev);
01357 bv.set_bit_and(id, true);
01358 if (++prev < id)
01359 {
01360 bv.set_range(prev, id-1, false);
01361 }
01362 prev = id;
01363 }
01364 }
01365
01366
01367
01368
01369
01370
01371
01372
01373
01374
01375
01376
01377
01378
01379
01380
01381 template<class BV, class It>
01382 void combine_and(BV& bv, It first, It last)
01383 {
01384 BV bv_tmp;
01385 combine_or(bv_tmp, first, last);
01386 bv &= bv_tmp;
01387 }
01388
01389
01390
01391
01392
01393
01394
01395
01396
01397
01398
01399
01400
01401
01402
01403
01404 template<class BV>
01405 bm::id_t count_intervals(const BV& bv)
01406 {
01407 const typename BV::blocks_manager_type& bman = bv.get_blocks_manager();
01408
01409 bm::word_t*** blk_root = bman.get_rootblock();
01410 typename BV::blocks_manager_type::block_count_change_func func(bman);
01411 for_each_block(blk_root, bman.top_block_size(), bm::set_array_size, func);
01412
01413 return func.count();
01414 }
01415
01416
01417
01418
01419
01420
01421
01422
01423
01424
01425
01426
01427
01428
01429
01430 template<class BV, class It>
01431 void export_array(BV& bv, It first, It last)
01432 {
01433 typename BV::blocks_manager_type& bman = bv.get_blocks_manager();
01434 unsigned inp_word_size = sizeof(*first);
01435 size_t array_size = last - first;
01436 size_t bit_cnt = array_size * inp_word_size * 8;
01437 int block_type;
01438 bm::word_t tmp;
01439 unsigned b1, b2, b3, b4;
01440
01441 if (bit_cnt >= bv.size())
01442 bv.resize((bm::id_t)bit_cnt + 1);
01443 else
01444 bv.set_range((bm::id_t)bit_cnt, bv.size() - 1, false);
01445
01446 switch (inp_word_size)
01447 {
01448 case 1:
01449 {
01450 size_t word_cnt = array_size / 4;
01451 for (unsigned i = 0; i < bm::set_total_blocks; ++i)
01452 {
01453 bm::word_t* blk =
01454 bman.check_allocate_block(i,
01455 false,
01456 BM_BIT,
01457 &block_type,
01458 false );
01459 if (block_type == 1)
01460 {
01461 blk = bman.convert_gap2bitset(i, BMGAP_PTR(blk));
01462 }
01463
01464 bm::word_t* wrd_ptr = blk;
01465 if (word_cnt >= bm::set_block_size) {
01466 bm::word_t* wrd_end = blk + bm::set_block_size;
01467 do {
01468 b1 = *first++; b2 = *first++;
01469 b3 = *first++; b4 = *first++;
01470 tmp = b1 | (b2 << 8) | (b3 << 16) | (b4 << 24);
01471 *wrd_ptr++ = tmp;
01472 } while (wrd_ptr < wrd_end);
01473 word_cnt -= bm::set_block_size;
01474 }
01475 else
01476 {
01477 size_t to_convert = last - first;
01478 for (size_t j = 0; j < to_convert / 4; ++j)
01479 {
01480 b1 = *first++; b2 = *first++;
01481 b3 = *first++; b4 = *first++;
01482 tmp = b1 | (b2 << 8) | (b3 << 16) | (b4 << 24);
01483 *wrd_ptr++ = tmp;
01484 }
01485 while (1)
01486 {
01487 if (first == last) break;
01488 *wrd_ptr = *first++;
01489 if (first == last) break;
01490 *wrd_ptr |= (*first++) << 8;
01491 if (first == last) break;
01492 *wrd_ptr |= (*first++) << 16;
01493 if (first == last) break;
01494 *wrd_ptr |= (*first++) << 24;
01495 ++wrd_ptr;
01496 }
01497 }
01498 if (first == last) break;
01499 }
01500 }
01501 break;
01502 case 2:
01503 {
01504 size_t word_cnt = array_size / 2;
01505 for (unsigned i = 0; i < bm::set_total_blocks; ++i)
01506 {
01507 bm::word_t* blk =
01508 bman.check_allocate_block(i,
01509 false,
01510 BM_BIT,
01511 &block_type,
01512 false );
01513 if (block_type == 1)
01514 {
01515 blk = bman.convert_gap2bitset(i, BMGAP_PTR(blk));
01516 }
01517
01518 bm::word_t* wrd_ptr = blk;
01519 if (word_cnt >= bm::set_block_size) {
01520 bm::word_t* wrd_end = blk + bm::set_block_size;
01521 do {
01522 b1 = *first++; b2 = *first++;
01523 tmp = b1 | (b2 << 16);
01524 *wrd_ptr++ = tmp;
01525 } while (wrd_ptr < wrd_end);
01526 word_cnt -= bm::set_block_size;
01527 }
01528 else
01529 {
01530 size_t to_convert = last - first;
01531 for (unsigned j = 0; j < to_convert / 2; ++j)
01532 {
01533 b1 = *first++; b2 = *first++;
01534 tmp = b1 | (b2 << 16);
01535 *wrd_ptr++ = tmp;
01536 }
01537 while (1)
01538 {
01539 if (first == last) break;
01540 *wrd_ptr = *first++;
01541 if (first == last) break;
01542 *wrd_ptr |= (*first++) << 16;
01543 ++wrd_ptr;
01544 }
01545 }
01546 if (first == last) break;
01547 }
01548 }
01549 break;
01550 case 4:
01551 {
01552 size_t word_cnt = array_size;
01553 for (unsigned i = 0; i < bm::set_total_blocks; ++i)
01554 {
01555 bm::word_t* blk =
01556 bman.check_allocate_block(i,
01557 false,
01558 BM_BIT,
01559 &block_type,
01560 false );
01561 if (block_type == 1)
01562 {
01563 blk = bman.convert_gap2bitset(i, BMGAP_PTR(blk));
01564 }
01565
01566 bm::word_t* wrd_ptr = blk;
01567 if (word_cnt >= bm::set_block_size) {
01568 bm::word_t* wrd_end = blk + bm::set_block_size;
01569 do {
01570 *wrd_ptr++ = *first++;
01571 } while (wrd_ptr < wrd_end);
01572 word_cnt -= bm::set_block_size;
01573 }
01574 else
01575 {
01576 while (1)
01577 {
01578 if (first == last) break;
01579 *wrd_ptr = *first++;
01580 ++wrd_ptr;
01581 }
01582 }
01583 if (first == last) break;
01584 }
01585 }
01586 break;
01587 default:
01588 BM_ASSERT(0);
01589 }
01590
01591 }
01592
01593 }
01594
01595 #ifdef _MSC_VER
01596 #pragma warning( default : 4311 4312)
01597 #endif
01598
01599 #endif