NCBI C++ ToolKit
bmalgo_impl.h
Go to the documentation of this file.

Go to the SVN repository for this file.

1 #ifndef BMALGO_IMPL__H__INCLUDED__
2 #define BMALGO_IMPL__H__INCLUDED__
3 /*
4 Copyright(c) 2002-2017 Anatoliy Kuznetsov(anatoliy_kuznetsov at yahoo.com)
5 
6 Licensed under the Apache License, Version 2.0 (the "License");
7 you may not use this file except in compliance with the License.
8 You may obtain a copy of the License at
9 
10  http://www.apache.org/licenses/LICENSE-2.0
11 
12 Unless required by applicable law or agreed to in writing, software
13 distributed under the License is distributed on an "AS IS" BASIS,
14 WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
15 See the License for the specific language governing permissions and
16 limitations under the License.
17 
18 For more information please visit: http://bitmagic.io
19 */
20 
21 /*! \file bmalgo_impl.h
22  \brief Algorithms for bvector<>
23 */
24 
25 #ifdef _MSC_VER
26 #pragma warning( push )
27 #pragma warning( disable : 4311 4312 4127)
28 #endif
29 
30 #include "bmdef.h"
31 #include "bmutil.h"
32 
33 namespace bm
34 {
35 
36 /*!
37  @defgroup setalgo bvector<> algorithms
38 
39  Set algebra algorithms using bit-vectors, arrays.
40  Binary metrics and distances. Random sub-sets.
41 
42  @ingroup bvector
43  */
44 
45 /*!
46  @defgroup distance Binary-distance metrics
47 
48  Distance metrics and algorithms to compute binary distances
49  @ingroup setalgo
50  */
51 
52 
53 /*!
54  \brief Distance metrics codes defined for vectors A and B
55  \ingroup distance
56 */
58 {
59  COUNT_AND = set_COUNT_AND, //!< (A & B).count()
60  COUNT_XOR = set_COUNT_XOR, //!< (A ^ B).count()
61  COUNT_OR = set_COUNT_OR, //!< (A | B).count()
62  COUNT_SUB_AB = set_COUNT_SUB_AB, //!< (A - B).count()
63  COUNT_SUB_BA = set_COUNT_SUB_BA, //!< (B - A).count()
64  COUNT_A = set_COUNT_A, //!< A.count()
65  COUNT_B = set_COUNT_B //!< B.count()
66 };
67 
68 /**
69  Convert set operation into compatible distance metric
70  \ingroup distance
71 */
72 inline
74 {
76  if (op == set_COUNT) op = set_COUNT_B;
77  // distance metric is created as a set operation sub-class
78  // simple cast will work to convert
79  return (distance_metric) op;
80 }
81 
82 /*!
83  \brief Distance metric descriptor, holds metric code and result.
84  \sa distance_operation
85 */
87 {
88 #ifdef BM64ADDR
89  typedef bm::id64_t size_type;
90 #else
92 #endif
93 
96 
98  : metric(m),
99  result(0)
100  {}
102  : metric(bm::COUNT_XOR),
103  result(0)
104  {}
105 
106  /*!
107  \brief Sets metric result to 0
108  */
110  {
111  result = 0;
112  }
113 };
114 
115 /// functor-adaptor for C-style callbacks
116 ///
117 /// @internal
118 ///
119 template <class VCBT, class size_type>
121 {
123 
125  : handle_(h), func_(cb_func)
126  {}
127 
128  int add_bits(size_type offset, const unsigned char* bits, unsigned size)
129  {
130  for (unsigned i = 0; i < size; ++i)
131  {
132  int ret = func_(handle_, offset + bits[i]);
133  if (ret < 0)
134  return ret;
135  }
136  return 0;
137  }
138  int add_range(size_type offset, size_type size)
139  {
140  for (size_type i = 0; i < size; ++i)
141  {
142  int ret = func_(handle_, offset + i);
143  if (ret < 0)
144  return ret;
145  }
146  return 0;
147  }
148 
149  void* handle_;
151 };
152 
153 /// functor-adaptor for back-inserter
154 ///
155 /// @internal
156 ///
157 template <class BII, class size_type>
159 {
160 
162  : bi_(bi)
163  {}
164 
165  int add_bits(size_type offset, const unsigned char* bits, unsigned size)
166  {
167  for (unsigned i = 0; i < size; ++i)
168  *bi_ = offset + bits[i];
169  return 0;
170  }
171  int add_range(size_type offset, size_type size)
172  {
173  for (size_type i = 0; i < size; ++i)
174  *bi_ = offset + i;
175  return 0;
176  }
177 
178  BII bi_;
179 };
180 
181 
182 /*!
183  \brief Internal function computes different distance metrics.
184  \internal
185  \ingroup distance
186 
187 */
188 inline
190  const bm::word_t* arg_blk,
193 
194 {
195  gap_word_t* g1 = BMGAP_PTR(blk);
196  gap_word_t* g2 = BMGAP_PTR(arg_blk);
197 
198  unsigned gap = BM_IS_GAP(blk);
199  unsigned arg_gap = BM_IS_GAP(arg_blk);
200 
201  if (gap) // first block GAP-type
202  {
203  if (arg_gap) // both blocks GAP-type
204  {
205  for (distance_metric_descriptor* it = dmit;it < dmit_end; ++it)
206  {
207  distance_metric_descriptor& dmd = *it;
208 
209  switch (dmd.metric)
210  {
211  case bm::COUNT_AND:
212  dmd.result += gap_count_and(g1, g2);
213  break;
214  case bm::COUNT_OR:
215  dmd.result += gap_count_or(g1, g2);
216  break;
217  case bm::COUNT_SUB_AB:
218  dmd.result += gap_count_sub(g1, g2);
219  break;
220  case bm::COUNT_SUB_BA:
221  dmd.result += gap_count_sub(g2, g1);
222  break;
223  case bm::COUNT_XOR:
224  dmd.result += gap_count_xor(g1, g2);
225  break;
226  case bm::COUNT_A:
227  dmd.result += gap_bit_count_unr(g1);
228  break;
229  case bm::COUNT_B:
230  dmd.result += gap_bit_count_unr(g2);
231  break;
232  default:
233  BM_ASSERT(0);
234  } // switch
235 
236  } // for it
237 
238  return;
239 
240  }
241  else // first block - GAP, argument - BITSET
242  {
243  for (distance_metric_descriptor* it = dmit;it < dmit_end; ++it)
244  {
245  distance_metric_descriptor& dmd = *it;
246 
247  switch (dmd.metric)
248  {
249  case bm::COUNT_AND:
250  if (arg_blk)
251  dmd.result += gap_bitset_and_count(arg_blk, g1);
252  break;
253  case bm::COUNT_OR:
254  if (!arg_blk)
255  dmd.result += gap_bit_count_unr(g1);
256  else
257  dmd.result += gap_bitset_or_count(arg_blk, g1);
258  break;
259  case bm::COUNT_SUB_AB:
260  {
262 
263  gap_convert_to_bitset((bm::word_t*) temp_bit_blk, g1);
264  dmd.result +=
265  bit_operation_sub_count((bm::word_t*)temp_bit_blk, arg_blk);
266  }
267  break;
268  case bm::COUNT_SUB_BA:
269  dmd.metric = bm::COUNT_SUB_AB; // recursive call to SUB_AB
271  blk,
272  it, it+1);
273  dmd.metric = bm::COUNT_SUB_BA; // restore status quo
274  break;
275  case bm::COUNT_XOR:
276  if (!arg_blk)
277  dmd.result += gap_bit_count_unr(g1);
278  else
279  dmd.result += gap_bitset_xor_count(arg_blk, g1);
280  break;
281  case bm::COUNT_A:
282  if (g1)
283  dmd.result += gap_bit_count_unr(g1);
284  break;
285  case bm::COUNT_B:
286  if (arg_blk)
287  {
288  dmd.result +=
289  bit_block_count(arg_blk);
290  }
291  break;
292  default:
293  BM_ASSERT(0);
294  } // switch
295 
296  } // for it
297 
298  return;
299 
300  }
301  }
302  else // first block is BITSET-type
303  {
304  if (arg_gap) // second argument block is GAP-type
305  {
306  for (distance_metric_descriptor* it = dmit;it < dmit_end; ++it)
307  {
308  distance_metric_descriptor& dmd = *it;
309 
310  switch (dmd.metric)
311  {
312  case bm::COUNT_AND:
313  if (blk)
314  dmd.result += gap_bitset_and_count(blk, g2);
315  break;
316  case bm::COUNT_OR:
317  if (!blk)
318  dmd.result += gap_bit_count_unr(g2);
319  else
320  dmd.result += gap_bitset_or_count(blk, g2);
321  break;
322  case bm::COUNT_SUB_AB:
323  if (blk)
324  dmd.result += gap_bitset_sub_count(blk, g2);
325  break;
326  case bm::COUNT_SUB_BA:
327  dmd.metric = bm::COUNT_SUB_AB; // recursive call to SUB_AB
329  //arg_gap,
330  blk,
331  //gap,
332  it, it+1);
333  dmd.metric = bm::COUNT_SUB_BA; // restore status quo
334  break;
335  case bm::COUNT_XOR:
336  if (!blk)
337  dmd.result += gap_bit_count_unr(g2);
338  else
339  dmd.result += gap_bitset_xor_count(blk, g2);
340  break;
341  case bm::COUNT_A:
342  if (blk)
343  {
344  dmd.result +=
345  bit_block_count(blk);
346  }
347  break;
348  case bm::COUNT_B:
349  if (g2)
350  dmd.result += gap_bit_count_unr(g2);
351  break;
352  default:
353  BM_ASSERT(0);
354  } // switch
355 
356  } // for it
357 
358  return;
359  }
360  }
361 
362  // --------------------------------------------
363  //
364  // Here we combine two plain bitblocks
365 
366  for (distance_metric_descriptor* it = dmit; it < dmit_end; ++it)
367  {
368  distance_metric_descriptor& dmd = *it;
371  if (gfunc)
372  {
373  dmd.result += (*gfunc)(blk, arg_blk);
374  }
375  else
376  {
377  switch (dmd.metric)
378  {
379  case bm::COUNT_A:
380  if (blk)
381  dmd.result += bm::bit_block_count(blk);
382  break;
383  case bm::COUNT_B:
384  if (arg_blk)
385  dmd.result += bm::bit_block_count(arg_blk);
386  break;
387  case bm::COUNT_AND:
388  case bm::COUNT_XOR:
389  case bm::COUNT_OR:
390  case bm::COUNT_SUB_AB:
391  case bm::COUNT_SUB_BA:
392  default:
393  BM_ASSERT(0);
394  } // switch
395  }
396 
397  } // for it
398 }
399 
400 /*!
401 \brief Internal function computes AND distance.
402 \internal
403 \ingroup distance
404 */
405 inline
407  const bm::word_t* arg_blk) BMNOEXCEPT
408 {
409  unsigned gap = BM_IS_GAP(blk);
410  unsigned arg_gap = BM_IS_GAP(arg_blk);
411  if (gap) // first block GAP-type
412  {
413  if (arg_gap) // both blocks GAP-type
414  {
415  return gap_count_and(BMGAP_PTR(blk), BMGAP_PTR(arg_blk));
416  }
417  else // first block - GAP, argument - BITSET
418  {
419  return gap_bitset_and_count(arg_blk, BMGAP_PTR(blk));
420  }
421  }
422  else // first block is BITSET-type
423  {
424  if (arg_gap) // second argument block is GAP-type
425  {
426  return gap_bitset_and_count(blk, BMGAP_PTR(arg_blk));
427  }
428  }
429 
430  // --------------------------------------------
431  // Here we combine two plain bitblocks
432 
433  return bit_operation_and_count(blk, arg_blk);
434 }
435 
436 
437 /*!
438  \brief Internal function computes different existense of distance metric.
439  \internal
440  \ingroup distance
441 */
442 inline
444  unsigned gap,
445  const bm::word_t* arg_blk,
446  unsigned arg_gap,
449 
450 {
451  gap_word_t* res=0;
452 
453  gap_word_t* g1 = BMGAP_PTR(blk);
454  gap_word_t* g2 = BMGAP_PTR(arg_blk);
455 
456  if (gap) // first block GAP-type
457  {
458  if (arg_gap) // both blocks GAP-type
459  {
460  gap_word_t tmp_buf[bm::gap_max_buff_len * 3]; // temporary result
461 
462  for (distance_metric_descriptor* it = dmit;it < dmit_end; ++it)
463  {
464  distance_metric_descriptor& dmd = *it;
465  if (dmd.result)
466  {
467  continue;
468  }
469  res = 0;
470  unsigned dsize = 0;
471  switch (dmd.metric)
472  {
473  case bm::COUNT_AND:
474  dmd.result += gap_operation_any_and(g1, g2);
475  break;
476  case bm::COUNT_OR:
477  res = gap_operation_or(g1, g2, tmp_buf, dsize);
478  break;
479  case bm::COUNT_SUB_AB:
480  dmd.result += gap_operation_any_sub(g1, g2);
481  break;
482  case bm::COUNT_SUB_BA:
483  dmd.result += gap_operation_any_sub(g2, g1);
484  break;
485  case bm::COUNT_XOR:
486  dmd.result += gap_operation_any_xor(g1, g2);
487  break;
488  case bm::COUNT_A:
489  res = g1;
490  break;
491  case bm::COUNT_B:
492  res = g2;
493  break;
494  default:
495  BM_ASSERT(0);
496  } // switch
497  if (res)
498  dmd.result += !gap_is_all_zero(res);
499 
500  } // for it
501 
502  return;
503 
504  }
505  else // first block - GAP, argument - BITSET
506  {
507  for (distance_metric_descriptor* it = dmit;it < dmit_end; ++it)
508  {
509  distance_metric_descriptor& dmd = *it;
510  if (dmd.result)
511  {
512  continue;
513  }
514 
515  switch (dmd.metric)
516  {
517  case bm::COUNT_AND:
518  if (arg_blk)
519  dmd.result += gap_bitset_and_any(arg_blk, g1);
520  break;
521  case bm::COUNT_OR:
522  if (!arg_blk)
523  dmd.result += !gap_is_all_zero(g1);
524  else
525  dmd.result += gap_bitset_or_any(arg_blk, g1);
526  break;
527  case bm::COUNT_SUB_AB:
528  {
530  gap_convert_to_bitset((bm::word_t*) temp_blk, g1);
531  dmd.result +=
532  bit_operation_sub_any((bm::word_t*)temp_blk, arg_blk);
533  }
534  break;
535  case bm::COUNT_SUB_BA:
536  dmd.metric = bm::COUNT_SUB_AB; // recursive call to SUB_AB
538  arg_gap,
539  blk,
540  gap,
541  it, it+1);
542  dmd.metric = bm::COUNT_SUB_BA; // restore status quo
543  break;
544  case bm::COUNT_XOR:
545  if (!arg_blk)
546  dmd.result += !gap_is_all_zero(g1);
547  else
548  dmd.result += gap_bitset_xor_any(arg_blk, g1);
549  break;
550  case bm::COUNT_A:
551  if (g1)
552  dmd.result += !gap_is_all_zero(g1);
553  break;
554  case bm::COUNT_B:
555  if (arg_blk)
556  {
557  dmd.result +=
558  !bit_is_all_zero(arg_blk);
559  }
560  break;
561  default:
562  BM_ASSERT(0);
563  } // switch
564 
565  } // for it
566 
567  return;
568 
569  }
570  }
571  else // first block is BITSET-type
572  {
573  if (arg_gap) // second argument block is GAP-type
574  {
575  for (distance_metric_descriptor* it = dmit;it < dmit_end; ++it)
576  {
577  distance_metric_descriptor& dmd = *it;
578  if (dmd.result)
579  {
580  continue;
581  }
582 
583  switch (dmd.metric)
584  {
585  case bm::COUNT_AND:
586  if (blk)
587  dmd.result += gap_bitset_and_any(blk, g2);
588  break;
589  case bm::COUNT_OR:
590  if (!blk)
591  dmd.result += !gap_is_all_zero(g2);
592  else
593  dmd.result += gap_bitset_or_any(blk, g2);
594  break;
595  case bm::COUNT_SUB_AB:
596  if (blk)
597  dmd.result += gap_bitset_sub_any(blk, g2);
598  break;
599  case bm::COUNT_SUB_BA:
600  dmd.metric = bm::COUNT_SUB_AB; // recursive call to SUB_AB
602  arg_gap,
603  blk,
604  gap,
605  it, it+1);
606  dmd.metric = bm::COUNT_SUB_BA; // restore status quo
607  break;
608  case bm::COUNT_XOR:
609  if (!blk)
610  dmd.result += !gap_is_all_zero(g2);
611  else
612  dmd.result += gap_bitset_xor_any(blk, g2);
613  break;
614  case bm::COUNT_A:
615  if (blk)
616  {
617  dmd.result+=
618  !bm::bit_is_all_zero(blk);
619  }
620  break;
621  case bm::COUNT_B:
622  if (g2)
623  dmd.result += !gap_is_all_zero(g2);
624  break;
625  default:
626  BM_ASSERT(0);
627  } // switch
628 
629  } // for it
630 
631  return;
632  }
633  }
634 
635  // --------------------------------------------
636  //
637  // Here we combine two plain bitblocks
638 
639  for (distance_metric_descriptor* it = dmit; it < dmit_end; ++it)
640  {
641  distance_metric_descriptor& dmd = *it;
642  if (dmd.result)
643  {
644  continue;
645  }
646 
647  switch (dmd.metric)
648  {
649  case bm::COUNT_AND:
650  dmd.result +=
651  bit_operation_and_any(blk, arg_blk);
652  break;
653  case bm::COUNT_OR:
654  dmd.result +=
655  bit_operation_or_any(blk, arg_blk);
656  break;
657  case bm::COUNT_SUB_AB:
658  dmd.result +=
659  bit_operation_sub_any(blk, arg_blk);
660  break;
661  case bm::COUNT_SUB_BA:
662  dmd.result +=
663  bit_operation_sub_any(arg_blk, blk);
664  break;
665  case bm::COUNT_XOR:
666  dmd.result +=
667  bit_operation_xor_any(blk, arg_blk);
668  break;
669  case bm::COUNT_A:
670  if (blk)
671  dmd.result += !bit_is_all_zero(blk);
672  break;
673  case bm::COUNT_B:
674  if (arg_blk)
675  dmd.result += !bit_is_all_zero(arg_blk);
676  break;
677  default:
678  BM_ASSERT(0);
679  } // switch
680 
681  } // for it
682 }
683 
684 
685 
686 /*!
687  Convenience internal function to compute combine count for one metric
688  \internal
689  \ingroup distance
690 */
691 inline
692 unsigned
694  const bm::word_t* arg_blk,
696 {
697  distance_metric_descriptor dmd(metric);
699  arg_blk, //arg_gap,
700  &dmd, &dmd+1);
701  return unsigned(dmd.result);
702 }
703 
704 
705 /*!
706  Convenience internal function to compute combine any for one metric
707  \internal
708  \ingroup distance
709 */
710 inline
713  unsigned gap,
714  const bm::word_t* arg_blk,
715  unsigned arg_gap,
717 {
718  distance_metric_descriptor dmd(metric);
720  arg_blk, arg_gap,
721  &dmd, &dmd+1);
722  return dmd.result;
723 }
724 
725 /*!
726  \brief Staging function for distance operation
727 
728  \return temp block allocated (or NULL)
729 
730  \internal
731 */
732 inline
734  const distance_metric_descriptor* dmit_end,
735  bool* is_all_and) BMNOEXCEPT
736 {
737  for (const distance_metric_descriptor* it = dmit; it < dmit_end; ++it)
738  {
739  if (it->metric != bm::COUNT_AND)
740  {
741  *is_all_and = false;
742  }
743  } // for
744 }
745 
746 /*!
747  \brief Distance computing template function.
748 
749  Function receives two bitvectors and an array of distance metrics
750  (metrics pipeline). Function computes all metrics saves result into
751  corresponding pipeline results (distance_metric_descriptor::result)
752  An important detail is that function reuses metric descriptors,
753  incrementing received values. It allows you to accumulate results
754  from different calls in the pipeline.
755 
756  \param bv1 - argument bitvector 1 (A)
757  \param bv2 - argument bitvector 2 (B)
758  \param dmit - pointer to first element of metric descriptors array
759  Input-Output parameter, receives metric code as input,
760  computation is added to "result" field
761  \param dmit_end - pointer to (last+1) element of metric descriptors array
762  \ingroup distance
763 
764 */
765 template<class BV>
766 void distance_operation(const BV& bv1,
767  const BV& bv2,
770 {
771  const typename BV::blocks_manager_type& bman1 = bv1.get_blocks_manager();
772  const typename BV::blocks_manager_type& bman2 = bv2.get_blocks_manager();
773 
774  bool is_all_and = true; // flag is distance operation is just COUNT_AND
775  distance_stage(dmit, dmit_end, &is_all_and);
776 
777  bm::word_t*** blk_root = bman1.top_blocks_root();
778  typename BV::size_type block_idx = 0;
779  unsigned i, j;
780 
781  const bm::word_t* blk;
782  const bm::word_t* arg_blk;
783 
784  unsigned top_block_size = bman1.top_block_size();
785  unsigned ebs2 = bman2.top_block_size();
786  unsigned top_size;
787  if (ebs2 > top_block_size)
788  top_size = ebs2;
789  else
790  top_size = top_block_size;
791 
792  for (i = 0; i < top_size; ++i)
793  {
794  bm::word_t** blk_blk = (blk_root && (i < top_block_size)) ? blk_root[i] : 0;
795  if (!blk_blk)
796  {
797  // AND operation requested - we can skip this portion here
798  if (is_all_and)
799  {
800  block_idx += bm::set_sub_array_size;
801  continue;
802  }
803  const bm::word_t* const* bvbb = bman2.get_topblock(i);
804  if (bvbb == 0)
805  {
806  block_idx += bm::set_sub_array_size;
807  continue;
808  }
809 
810  blk = 0;
811  for (j = 0; j < bm::set_sub_array_size; ++j,++block_idx)
812  {
813  arg_blk = bman2.get_block(i, j);
814  if (!arg_blk)
815  continue;
817  arg_blk,
818  dmit, dmit_end);
819  } // for j
820  continue;
821  }
822 
823  for (j = 0; j < bm::set_sub_array_size; ++j, ++block_idx)
824  {
825  blk = bman1.get_block(i, j);
826  if (blk == 0 && is_all_and)
827  continue;
828 
829  arg_blk = bman2.get_block(i, j);
830 
831  if (!blk && !arg_blk)
832  continue;
833 
835  arg_blk,
836  dmit, dmit_end);
837  } // for j
838 
839  } // for i
840 }
841 
842 
843 /*!
844 \brief Distance AND computing template function.
845 
846 
847 \param bv1 - argument bitvector 1 (A)
848 \param bv2 - argument bitvector 2 (B)
849 \ingroup distance
850 
851 */
852 template<class BV>
853 typename BV::size_type distance_and_operation(const BV& bv1,
854  const BV& bv2) BMNOEXCEPT
855 {
856  const typename BV::blocks_manager_type& bman1 = bv1.get_blocks_manager();
857  const typename BV::blocks_manager_type& bman2 = bv2.get_blocks_manager();
858 
859  if (!bman1.is_init() || !bman2.is_init())
860  return 0;
861 
862  bm::word_t*** blk_root = bman1.top_blocks_root();
863  bm::word_t*** blk_root_arg = bman2.top_blocks_root();
864  typename BV::size_type count = 0;
865 
866  unsigned top_block_size =
867  bm::min_value(bman1.top_block_size(),bman2.top_block_size());
868 
869  for (unsigned i = 0; i < top_block_size; ++i)
870  {
871  bm::word_t** blk_blk;
872  bm::word_t** blk_blk_arg;
873  if ((blk_blk = blk_root[i]) == 0 || (blk_blk_arg= blk_root_arg[i]) == 0)
874  continue;
875 
876  if ((bm::word_t*)blk_blk == FULL_BLOCK_FAKE_ADDR)
877  blk_blk = FULL_SUB_BLOCK_REAL_ADDR;
878  if ((bm::word_t*)blk_blk_arg == FULL_BLOCK_FAKE_ADDR)
879  blk_blk_arg = FULL_SUB_BLOCK_REAL_ADDR;
880 
881  for (unsigned j = 0; j < bm::set_sub_array_size; j+=4)
882  {
883  (blk_blk[j] && blk_blk_arg[j]) ?
884  count += combine_count_and_operation_with_block(BLOCK_ADDR_SAN(blk_blk[j]), BLOCK_ADDR_SAN(blk_blk_arg[j]))
885  :0;
886  (blk_blk[j+1] && blk_blk_arg[j+1]) ?
887  count += combine_count_and_operation_with_block(BLOCK_ADDR_SAN(blk_blk[j+1]), BLOCK_ADDR_SAN(blk_blk_arg[j+1]))
888  :0;
889  (blk_blk[j+2] && blk_blk_arg[j+2]) ?
890  count += combine_count_and_operation_with_block(BLOCK_ADDR_SAN(blk_blk[j+2]), BLOCK_ADDR_SAN(blk_blk_arg[j+2]))
891  :0;
892  (blk_blk[j+3] && blk_blk_arg[j+3]) ?
893  count += combine_count_and_operation_with_block(BLOCK_ADDR_SAN(blk_blk[j+3]), BLOCK_ADDR_SAN(blk_blk_arg[j+3]))
894  :0;
895  } // for j
896 
897  } // for i
898  return count;
899 }
900 
901 
902 /*!
903  \brief Distance screening template function.
904 
905  Function receives two bitvectors and an array of distance metrics
906  (metrics pipeline). Function computes possybility of a metric(any bit)
907  saves result into corresponding pipeline results
908  (distance_metric_descriptor::result)
909  An important detail is that function reuses metric descriptors,
910  incrementing received values. It allows you to accumulate results
911  from different calls in the pipeline.
912 
913  \param bv1 - argument bitvector 1 (A)
914  \param bv2 - argument bitvector 2 (B)
915  \param dmit - pointer to first element of metric descriptors array
916  Input-Output parameter, receives metric code as input,
917  computation is added to "result" field
918  \param dmit_end - pointer to (last+1) element of metric descriptors array
919  \ingroup distance
920 */
921 template<class BV>
922 void distance_operation_any(const BV& bv1,
923  const BV& bv2,
926 {
927  const typename BV::blocks_manager_type& bman1 = bv1.get_blocks_manager();
928  const typename BV::blocks_manager_type& bman2 = bv2.get_blocks_manager();
929 
930  bool is_all_and = true; // flag is distance operation is just COUNT_AND
931  distance_stage(dmit, dmit_end, &is_all_and);
932 
933  bm::word_t*** blk_root = bman1.top_blocks_root();
934  unsigned block_idx = 0;
935  unsigned i, j;
936 
937  const bm::word_t* blk;
938  const bm::word_t* arg_blk;
939  bool blk_gap;
940  bool arg_gap;
941 
942  unsigned top_block_size = bman1.top_block_size();
943  unsigned ebs2 = bman2.top_block_size();
944  unsigned top_size;
945  if (ebs2 > top_block_size)
946  top_size = ebs2;
947  else
948  top_size = top_block_size;
949 
950  for (i = 0; i < top_size; ++i)
951  {
952  bm::word_t** blk_blk = (blk_root && (i < top_block_size)) ? blk_root[i] : 0;
953  if (blk_blk == 0) // not allocated
954  {
955  // AND operation requested - we can skip this portion here
956  if (is_all_and)
957  {
958  block_idx += bm::set_sub_array_size;
959  continue;
960  }
961 
962  const bm::word_t* const* bvbb = bman2.get_topblock(i);
963  if (bvbb == 0)
964  {
965  block_idx += bm::set_sub_array_size;
966  continue;
967  }
968 
969  blk = 0;
970  blk_gap = false;
971 
972  for (j = 0; j < bm::set_sub_array_size; ++j,++block_idx)
973  {
974  arg_blk = bman2.get_block(i, j);
975  if (!arg_blk)
976  continue;
977  arg_gap = BM_IS_GAP(arg_blk);
978 
980  arg_blk, arg_gap,
981  dmit, dmit_end);
982 
983  // check if all distance requests alredy resolved
984  bool all_resolved = false;
986  do
987  {
988  if (!it->result)
989  {
990  all_resolved = false;
991  break;
992  }
993  ++it;
994  } while (it < dmit_end);
995  if (all_resolved)
996  return;
997  } // for j
998 
999  continue;
1000  }
1001 
1002  for (j = 0; j < bm::set_sub_array_size; ++j, ++block_idx)
1003  {
1004  blk = bman1.get_block(i, j);
1005  if (blk == 0 && is_all_and)
1006  continue;
1007 
1008  arg_blk = bman2.get_block(i, j);
1009 
1010  if (blk == 0 && arg_blk == 0)
1011  continue;
1012 
1013  arg_gap = BM_IS_GAP(arg_blk);
1014  blk_gap = BM_IS_GAP(blk);
1015 
1016  combine_any_operation_with_block(blk, blk_gap,
1017  arg_blk, arg_gap,
1018  dmit, dmit_end);
1019 
1020  // check if all distance requests alredy resolved
1021  bool all_resolved = true;
1022  distance_metric_descriptor* it=dmit;
1023  do
1024  {
1025  if (!it->result)
1026  {
1027  all_resolved = false;
1028  break;
1029  }
1030  ++it;
1031  } while (it < dmit_end);
1032  if (all_resolved)
1033  return;
1034 
1035  } // for j
1036 
1037  } // for i
1038 }
1039 
1040 
1041 
1042 /**
1043  \brief Internal algorithms scans the input for the block range limit
1044  \internal
1045 */
1046 template<typename It, typename SIZE_TYPE>
1048  SIZE_TYPE nblock, SIZE_TYPE* max_id) BMNOEXCEPT
1049 {
1050  SIZE_TYPE m = *max_id;
1051  It right;
1052  for (right = first; right != last; ++right)
1053  {
1054  SIZE_TYPE v = SIZE_TYPE(*right);
1055  BM_ASSERT(v < bm::id_max);
1056  if (v >= m)
1057  m = v;
1058  SIZE_TYPE nb = v >> bm::set_block_shift;
1059  if (nb != nblock)
1060  break;
1061  }
1062  *max_id = m;
1063  return right;
1064 }
1065 
1066 /**
1067  \brief OR Combine bitvector and the iterable sequence
1068 
1069  Algorithm combines bvector with sequence of integers
1070  (represents another set). When the agrument set is sorted
1071  this method can give serious increase in performance.
1072 
1073  \param bv - destination bitvector
1074  \param first - first element of the iterated sequence
1075  \param last - last element of the iterated sequence
1076 
1077  \ingroup setalgo
1078 */
1079 template<class BV, class It>
1080 void combine_or(BV& bv, It first, It last)
1081 {
1082  typedef typename BV::size_type size_type;
1083  typename BV::blocks_manager_type& bman = bv.get_blocks_manager();
1084  if (!bman.is_init())
1085  bman.init_tree();
1086 
1087  size_type max_id = 0;
1088 
1089  while (first < last)
1090  {
1091  typename BV::block_idx_type nblock = (*first) >> bm::set_block_shift;
1092  It right = bm::block_range_scan(first, last, nblock, &max_id);
1093  if (max_id >= bv.size())
1094  {
1095  BM_ASSERT(max_id < bm::id_max);
1096  bv.resize(max_id + 1);
1097  }
1098 
1099  // now we have one in-block array of bits to set
1100 
1101  label1:
1102 
1103  int block_type;
1104  bm::word_t* blk =
1105  bman.check_allocate_block(nblock,
1106  true,
1107  bv.get_new_blocks_strat(),
1108  &block_type);
1109  if (!blk)
1110  continue;
1111 
1112  if (block_type == 1) // gap
1113  {
1114  bm::gap_word_t* gap_blk = BMGAP_PTR(blk);
1115  unsigned threshold = bm::gap_limit(gap_blk, bman.glen());
1116 
1117  for (; first < right; ++first)
1118  {
1119  unsigned is_set;
1120  unsigned nbit = (*first) & bm::set_block_mask;
1121 
1122  unsigned new_block_len =
1123  bm::gap_set_value(true, gap_blk, nbit, &is_set);
1124  if (new_block_len > threshold)
1125  {
1126  bman.extend_gap_block(nblock, gap_blk);
1127  ++first;
1128  goto label1; // block pointer changed - goto reset
1129  }
1130  }
1131  }
1132  else // bit block
1133  {
1134  for (; first < right; ++first)
1135  {
1136  size_type pos = *first;
1137  unsigned nbit = unsigned(pos & bm::set_block_mask);
1138  unsigned nword = unsigned(nbit >> bm::set_word_shift);
1139  nbit &= bm::set_word_mask;
1140  blk[nword] |= (1u << nbit);
1141  } // for
1142  }
1143  } // while
1144 }
1145 
1146 
1147 /**
1148  \brief XOR Combine bitvector and the iterable sequence
1149 
1150  Algorithm combines bvector with sequence of integers
1151  (represents another set). When the agrument set is sorted
1152  this method can give serious increase in performance.
1153 
1154  \param bv - destination bitvector
1155  \param first - first element of the iterated sequence
1156  \param last - last element of the iterated sequence
1157 
1158  \ingroup setalgo
1159 */
1160 template<class BV, class It>
1161 void combine_xor(BV& bv, It first, It last)
1162 {
1163  typename BV::blocks_manager_type& bman = bv.get_blocks_manager();
1164  if (!bman.is_init())
1165  bman.init_tree();
1166 
1167  typename BV::size_type max_id = 0;
1168 
1169  while (first < last)
1170  {
1171  typename BV::block_idx_type nblock = ((*first) >> bm::set_block_shift);
1172  It right = block_range_scan(first, last, nblock, &max_id);
1173 
1174  if (max_id >= bv.size())
1175  {
1176  BM_ASSERT(max_id < bm::id_max);
1177  bv.resize(max_id + 1);
1178  }
1179 
1180  // now we have one in-block array of bits to set
1181 
1182  label1:
1183 
1184  int block_type;
1185  bm::word_t* blk =
1186  bman.check_allocate_block(nblock,
1187  true,
1188  bv.get_new_blocks_strat(),
1189  &block_type,
1190  false /* no null return */);
1191  BM_ASSERT(blk);
1192 
1193  if (block_type == 1) // gap
1194  {
1195  bm::gap_word_t* gap_blk = BMGAP_PTR(blk);
1196  unsigned threshold = bm::gap_limit(gap_blk, bman.glen());
1197 
1198  for (; first < right; ++first)
1199  {
1200  unsigned is_set;
1201  unsigned nbit = (*first) & bm::set_block_mask;
1202 
1203  is_set = bm::gap_test_unr(gap_blk, nbit);
1204  BM_ASSERT(is_set <= 1);
1205  is_set ^= 1;
1206 
1207  unsigned new_block_len =
1208  gap_set_value(is_set, gap_blk, nbit, &is_set);
1209  if (new_block_len > threshold)
1210  {
1211  bman.extend_gap_block(nblock, gap_blk);
1212  ++first;
1213  goto label1; // block pointer changed - goto reset
1214  }
1215  }
1216  }
1217  else // bit block
1218  {
1219  for (; first < right; ++first)
1220  {
1221  unsigned nbit = unsigned(*first & bm::set_block_mask);
1222  unsigned nword = unsigned(nbit >> bm::set_word_shift);
1223  nbit &= bm::set_word_mask;
1224  blk[nword] ^= (1u << nbit);
1225  } // for
1226  }
1227  } // while
1228 
1229  bv.forget_count();
1230 }
1231 
1232 
1233 
1234 /**
1235  \brief SUB Combine bitvector and the iterable sequence
1236 
1237  Algorithm combines bvector with sequence of integers
1238  (represents another set). When the agrument set is sorted
1239  this method can give serious increase in performance.
1240 
1241  \param bv - destination bitvector
1242  \param first - first element of the iterated sequence
1243  \param last - last element of the iterated sequence
1244 
1245  \ingroup setalgo
1246 */
1247 template<class BV, class It>
1248 void combine_sub(BV& bv, It first, It last)
1249 {
1250  typename BV::blocks_manager_type& bman = bv.get_blocks_manager();
1251  if (!bman.is_init())
1252  bman.init_tree();
1253 
1254  typename BV::size_type max_id = 0;
1255 
1256  while (first < last)
1257  {
1258  typename BV::block_idx_type nblock = (*first) >> bm::set_block_shift;
1259  It right = bm::block_range_scan(first, last, nblock, &max_id);
1260 
1261  if (max_id >= bv.size())
1262  {
1263  BM_ASSERT(max_id < bm::id_max);
1264  bv.resize(max_id + 1);
1265  }
1266 
1267  // now we have one in-block array of bits to set
1268 
1269  label1:
1270 
1271  int block_type;
1272  bm::word_t* blk =
1273  bman.check_allocate_block(nblock,
1274  false,
1275  bv.get_new_blocks_strat(),
1276  &block_type);
1277 
1278  if (!blk)
1279  continue;
1280 
1281  if (block_type == 1) // gap
1282  {
1283  bm::gap_word_t* gap_blk = BMGAP_PTR(blk);
1284  unsigned threshold = bm::gap_limit(gap_blk, bman.glen());
1285 
1286  for (; first < right; ++first)
1287  {
1288  unsigned is_set;
1289  unsigned nbit = (*first) & bm::set_block_mask;
1290 
1291  is_set = bm::gap_test_unr(gap_blk, nbit);
1292  if (!is_set)
1293  continue;
1294 
1295  unsigned new_block_len =
1296  gap_set_value(false, gap_blk, nbit, &is_set);
1297  if (new_block_len > threshold)
1298  {
1299  bman.extend_gap_block(nblock, gap_blk);
1300  ++first;
1301  goto label1; // block pointer changed - goto reset
1302  }
1303  }
1304  }
1305  else // bit block
1306  {
1307  for (; first < right; ++first)
1308  {
1309  unsigned nbit = unsigned(*first & bm::set_block_mask);
1310  unsigned nword = unsigned(nbit >> bm::set_word_shift);
1311  nbit &= bm::set_word_mask;
1312  blk[nword] &= ~((bm::word_t)1 << nbit);
1313  } // for
1314  }
1315  } // while
1316 
1317  bv.forget_count();
1318 }
1319 
1320 /**
1321  \brief AND Combine bitvector and the iterable sequence
1322 
1323  Algorithm combines bvector with sorted sequence of integers
1324  (represents another set).
1325 
1326  \param bv - destination bitvector
1327  \param first - first element of the iterated sequence
1328  \param last - last element of the iterated sequence
1329 
1330  \ingroup setalgo
1331 */
1332 template<class BV, class It>
1333 void combine_and_sorted(BV& bv, It first, It last)
1334 {
1335  typename BV::size_type prev = 0;
1336  for ( ;first < last; ++first)
1337  {
1338  typename BV::size_type id = *first;
1339  BM_ASSERT(id >= prev); // make sure it's sorted
1340  bv.set_bit_and(id, true);
1341  if (++prev < id)
1342  {
1343  bv.set_range(prev, id-1, false);
1344  }
1345  prev = id;
1346  }
1347 }
1348 
1349 
1350 /**
1351  \brief AND Combine bitvector and the iterable sequence
1352 
1353  Algorithm combines bvector with sequence of integers
1354  (represents another set). When the agrument set is sorted
1355  this method can give serious increase in performance.
1356 
1357  \param bv - destination bitvector
1358  \param first - first element of the iterated sequence
1359  \param last - last element of the iterated sequence
1360 
1361  \ingroup setalgo
1362  \sa combine_and_sorted
1363 */
1364 template<class BV, class It>
1365 void combine_and(BV& bv, It first, It last)
1366 {
1367  BV bv_tmp;
1368  combine_or(bv_tmp, first, last);
1369  bv &= bv_tmp;
1370 }
1371 
1372 /*!
1373  \brief Compute number of bit intervals (GAPs) in the bitvector
1374 
1375  Algorithm traverses bit vector and count number of uninterrupted
1376  intervals of 1s and 0s.
1377  <pre>
1378  For example:
1379  empty vector - 1 interval
1380  00001111100000 - gives us 3 intervals
1381  10001111100000 - 4 intervals
1382  00000000000000 - 1 interval
1383  11111111111111 - 1 interval
1384  </pre>
1385  \return Number of intervals
1386  \ingroup setalgo
1387 */
1388 template<class BV>
1389 typename BV::size_type count_intervals(const BV& bv)
1390 {
1391  const typename BV::blocks_manager_type& bman = bv.get_blocks_manager();
1392 
1393  if (!bman.is_init())
1394  return 1;
1395 
1396  bm::word_t*** blk_root = bman.top_blocks_root();
1397  typename BV::blocks_manager_type::block_count_change_func func(bman);
1398  typename BV::blocks_manager_type::block_idx_type st = 0;
1399  bm::for_each_block(blk_root, bman.top_block_size(), func, st);
1400 
1401  typename BV::size_type intervals = func.count();
1402  bool last_bit_set = bv.test(bm::id_max-1);
1403 
1404  intervals -= last_bit_set; // correct last (out of range) interval
1405  return intervals;
1406 }
1407 
1408 /*!
1409  \brief Export bitset from an array of binary data representing
1410  the bit vector.
1411 
1412  Input array can be array of ints, chars or other native C types.
1413  Method works with iterators, which makes it compatible with
1414  STL containers and C arrays
1415 
1416  \param bv - destination bitvector
1417  \param first - first element of the iterated sequence
1418  \param last - last element of the iterated sequence
1419 
1420  \ingroup setalgo
1421 */
1422 template<typename BV, class It>
1423 void export_array(BV& bv, It first, It last)
1424 {
1425  typename BV::blocks_manager_type& bman = bv.get_blocks_manager();
1426  if (!bman.is_init())
1427  bman.init_tree();
1428 
1429  unsigned inp_word_size = sizeof(*first);
1430  size_t array_size = size_t(last - first);
1431  size_t bit_cnt = array_size * inp_word_size * 8;
1432  int block_type;
1433  bm::word_t tmp;
1434  bm::word_t b1, b2, b3, b4;
1435 
1436  if (bit_cnt >= bv.size())
1437  bv.resize((bm::id_t)bit_cnt + 1);
1438  else
1439  bv.set_range((typename BV::size_type)bit_cnt, bv.size() - 1, false);
1440  switch (inp_word_size)
1441  {
1442  case 1:
1443  {
1444  size_t word_cnt = array_size / 4;
1445  for (typename BV::block_idx_type i = 0; i < bm::set_total_blocks; ++i)
1446  {
1447  bm::word_t* blk =
1448  bman.check_allocate_block(i,
1449  false,
1450  BM_BIT,
1451  &block_type,
1452  false /*no NULL ret*/);
1453  if (block_type == 1) // gap
1454  {
1455  blk = bman.deoptimize_block(i);
1456  }
1457 
1458  bm::word_t* wrd_ptr = blk;
1459  if (word_cnt >= bm::set_block_size) {
1460  bm::word_t* wrd_end = blk + bm::set_block_size;
1461  do {
1462  b1 = bm::word_t(*first++); b2 = bm::word_t(*first++);
1463  b3 = bm::word_t(*first++); b4 = bm::word_t(*first++);
1464  tmp = b1 | (b2 << 8u) | (b3 << 16u) | (b4 << 24u);
1465  *wrd_ptr++ = tmp;
1466  } while (wrd_ptr < wrd_end);
1467  word_cnt -= bm::set_block_size;
1468  }
1469  else
1470  {
1471  size_t to_convert = size_t(last - first);
1472  for (size_t j = 0; j < to_convert / 4; ++j)
1473  {
1474  b1 = bm::word_t(*first++); b2 = bm::word_t(*first++);
1475  b3 = bm::word_t(*first++); b4 = bm::word_t(*first++);
1476  tmp = b1 | (b2 << 8u) | (b3 << 16u) | (b4 << 24u);
1477  *wrd_ptr++ = tmp;
1478  }
1479  while (1)
1480  {
1481  if (first == last) break;
1482  *wrd_ptr = bm::word_t(*first++);
1483  if (first == last) break;
1484  *wrd_ptr |= bm::word_t(*first++) << 8u;
1485  if (first == last) break;
1486  *wrd_ptr |= bm::word_t(*first++) << 16u;
1487  if (first == last) break;
1488  *wrd_ptr |= bm::word_t(*first++) << 24u;
1489  ++wrd_ptr;
1490  }
1491  }
1492  if (first == last) break;
1493  } // for
1494  }
1495  break;
1496  case 2:
1497  {
1498  size_t word_cnt = array_size / 2;
1499  for (typename BV::block_idx_type i = 0; i < bm::set_total_blocks; ++i)
1500  {
1501  bm::word_t* blk =
1502  bman.check_allocate_block(i,
1503  false,
1504  BM_BIT,
1505  &block_type,
1506  false /*no NULL ret*/);
1507  if (block_type) // gap
1508  blk = bman.deoptimize_block(i);
1509 
1510  bm::word_t* wrd_ptr = blk;
1511  if (word_cnt >= bm::set_block_size) {
1512  bm::word_t* wrd_end = blk + bm::set_block_size;
1513  do {
1514  b1 = bm::word_t(*first++); b2 = bm::word_t(*first++);
1515  tmp = b1 | (b2 << 16);
1516  *wrd_ptr++ = tmp;
1517  } while (wrd_ptr < wrd_end);
1518  word_cnt -= bm::set_block_size;
1519  }
1520  else
1521  {
1522  size_t to_convert = size_t(last - first);
1523  for (unsigned j = 0; j < to_convert / 2; ++j)
1524  {
1525  b1 = bm::word_t(*first++); b2 = bm::word_t(*first++);
1526  tmp = b1 | (b2 << 16u);
1527  *wrd_ptr++ = tmp;
1528  }
1529  while (1)
1530  {
1531  if (first == last) break;
1532  *wrd_ptr = bm::word_t(*first++);
1533  if (first == last) break;
1534  *wrd_ptr |= bm::word_t((*first++) << 16u);
1535  ++wrd_ptr;
1536  }
1537  }
1538  if (first == last) break;
1539  } // for
1540  }
1541  break;
1542  case 4:
1543  {
1544  size_t word_cnt = array_size;
1545  for (typename BV::block_idx_type i = 0; i < bm::set_total_blocks; ++i)
1546  {
1547  bm::word_t* blk =
1548  bman.check_allocate_block(i,
1549  false,
1550  BM_BIT,
1551  &block_type,
1552  false /*no NULL ret*/);
1553  if (block_type == 1) // gap
1554  blk = bman.deoptimize_block(i);
1555 
1556  bm::word_t* wrd_ptr = blk;
1557  if (word_cnt >= bm::set_block_size) {
1558  bm::word_t* wrd_end = blk + bm::set_block_size;
1559  do
1560  {
1561  *wrd_ptr++ = bm::word_t(*first++);
1562  } while (wrd_ptr < wrd_end);
1563  word_cnt -= bm::set_block_size;
1564  }
1565  else
1566  {
1567  while (1)
1568  {
1569  if (first == last) break;
1570  *wrd_ptr = bm::word_t(*first++);
1571  ++wrd_ptr;
1572  }
1573  }
1574  if (first == last) break;
1575  } // for
1576  }
1577  break;
1578  default:
1579  BM_ASSERT(0);
1580  } // switch
1581 
1582 }
1583 
1584 
1585 /*!
1586  \brief for-each visitor, calls a visitor functor for each 1 bit group
1587 
1588  \param block - bit block buffer pointer
1589  \param offset - global block offset (number of bits)
1590  \param bit_functor - functor must support .add_bits(offset, bits_ptr, size)
1591  \return - functor return code (< 0 - interrupt the processing)
1592 
1593  @ingroup bitfunc
1594  @internal
1595 */
1596 template<typename Func, typename SIZE_TYPE>
1598  Func& bit_functor)
1599 {
1600  BM_ASSERT(block);
1601  int ret;
1602  if (IS_FULL_BLOCK(block))
1603  {
1604  ret = bit_functor.add_range(offset, bm::gap_max_bits);
1605  return ret;
1606  }
1607  unsigned char bits[bm::set_bitscan_wave_size*32];
1608  SIZE_TYPE offs = offset;
1609  const word_t* block_end = block + bm::set_block_size;
1610  do
1611  {
1612  if (unsigned cnt = bm::bitscan_wave(block, bits))
1613  {
1614  ret = bit_functor.add_bits(offs, bits, cnt);
1615  if (ret < 0)
1616  return ret;
1617  }
1618  offs += bm::set_bitscan_wave_size * 32;
1619  block += bm::set_bitscan_wave_size;
1620  } while (block < block_end);
1621  return 0;
1622 }
1623 
1624 /*!
1625  \brief for-each range visitor, calls a visitor functor for each 1 bit group
1626 
1627  \param block - bit block buffer pointer
1628  \param offset - global block offset (number of bits)
1629  \param left - bit addredd in block from [from..to]
1630  \param right - bit addredd in block to [from..to]
1631  \param bit_functor - functor must support .add_bits(offset, bits_ptr, size)
1632  \return - functor return code (< 0 - interrupt the processing)
1633  @ingroup bitfunc
1634  @internal
1635 */
1636 template<typename Func, typename SIZE_TYPE>
1638  unsigned left, unsigned right,
1639  Func& bit_functor)
1640 {
1641  BM_ASSERT(block);
1642  BM_ASSERT(left <= right);
1643  BM_ASSERT(right < bm::bits_in_block);
1644 
1645  int ret = 0;
1646  if (IS_FULL_BLOCK(block))
1647  {
1648  unsigned sz = right - left + 1;
1649  ret = bit_functor.add_range(offset + left, sz);
1650  return ret;
1651  }
1652  unsigned char bits[bm::set_bitscan_wave_size*32];
1653 
1654  unsigned cnt, nword, nbit, bitcount, temp;
1655  nbit = left & bm::set_word_mask;
1656  const bm::word_t* word =
1657  block + (nword = unsigned(left >> bm::set_word_shift));
1658  if (left == right) // special case (only 1 bit to check)
1659  {
1660  if ((*word >> nbit) & 1u)
1661  {
1662  bits[0] = (unsigned char)nbit;
1663  ret = bit_functor.add_bits(offset + (nword * 32), bits, 1);
1664  }
1665  return ret;
1666  }
1667 
1668  bitcount = right - left + 1u;
1669  if (nbit) // starting position is not aligned
1670  {
1671  unsigned right_margin = nbit + right - left;
1672  if (right_margin < 32)
1673  {
1674  unsigned mask_r = bm::mask_r_u32(nbit);
1675  unsigned mask_l = bm::mask_l_u32(right_margin);
1676  unsigned mask = mask_r & mask_l;
1677 
1678  temp = (*word & mask);
1679  cnt = bm::bitscan(temp, bits);
1680  if (cnt)
1681  ret = bit_functor.add_bits(offset + (nword * 32), bits, cnt);
1682  return ret;
1683  }
1684  unsigned mask_r = bm::mask_r_u32(nbit);
1685  temp = *word & mask_r;
1686  cnt = bm::bitscan(temp, bits);
1687  if (cnt)
1688  {
1689  ret = bit_functor.add_bits(offset + (nword * 32), bits, cnt);
1690  if (ret < 0)
1691  return ret;
1692  }
1693  bitcount -= 32 - nbit;
1694  ++word; ++nword;
1695  }
1696  else
1697  {
1698  bitcount = right - left + 1u;
1699  }
1700 
1701  // word aligned now - scan the bit-stream loop unrolled 4x words(wave)
1703  for ( ;bitcount >= 128;
1704  bitcount-=128, word+=bm::set_bitscan_wave_size,
1705  nword += bm::set_bitscan_wave_size)
1706  {
1707  cnt = bm::bitscan_wave(word, bits);
1708  if (cnt)
1709  {
1710  ret = bit_functor.add_bits(offset + (nword * 32), bits, cnt);
1711  if (ret < 0)
1712  return ret;
1713  }
1714  } // for
1715 
1716  for ( ;bitcount >= 32; bitcount-=32, ++word)
1717  {
1718  temp = *word;
1719  cnt = bm::bitscan(temp, bits);
1720  if (cnt)
1721  {
1722  ret = bit_functor.add_bits(offset + (nword * 32), bits, cnt);
1723  if (ret < 0)
1724  return ret;
1725  }
1726  ++nword;
1727  } // for
1728 
1729  BM_ASSERT(bitcount < 32);
1730 
1731  if (bitcount) // we have a tail to count
1732  {
1733  unsigned mask_l = bm::mask_l_u32(bitcount-1);
1734  temp = *word & mask_l;
1735  cnt = bm::bitscan(temp, bits);
1736  if (cnt)
1737  {
1738  ret = bit_functor.add_bits(offset + (nword * 32), bits, cnt);
1739  if (ret < 0)
1740  return ret;
1741  }
1742  }
1743  return 0;
1744 }
1745 
1746 
1747 
1748 /*!
1749  \brief for-each visitor, calls a special visitor functor for each 1 bit range
1750 
1751  \param buf - bit block buffer pointer
1752  \param offset - global block offset (number of bits)
1753  \param bit_functor - functor must support .add_range(offset, bits_ptr, size)
1754  \return - functor return code (< 0 - interrupt the processing)
1755 
1756  @ingroup gapfunc
1757  @internal
1758 */
1759 template<typename T, typename Func, typename SIZE_TYPE>
1761  Func& bit_functor)
1762 {
1763  const T* pcurr = buf + 1;
1764  const T* pend = buf + (*buf >> 3);
1765  int ret = 0;
1766  if (*buf & 1)
1767  {
1768  ret = bit_functor.add_range(offset, *pcurr + 1);
1769  if (ret < 0)
1770  return ret;
1771  ++pcurr;
1772  }
1773  for (++pcurr; (pcurr <= pend) && (ret >= 0); pcurr += 2)
1774  {
1775  T prev = *(pcurr-1);
1776  ret = bit_functor.add_range(offset + prev + 1, *pcurr - prev);
1777  }
1778  return ret;
1779 }
1780 
1781 /*!
1782  \brief for-each visitor, calls a special visitor functor for each 1 bit range
1783 
1784  \param buf - bit block buffer pointer
1785  \param offset - global block offset (number of bits)
1786  \param left - interval start [left..right]
1787  \param right - intreval end [left..right]
1788  \param bit_functor - functor must support .add_range(offset, bits_ptr, size)
1789  \return - functor return code (< 0 - interrupt the processing)
1790 
1791  @ingroup gapfunc
1792  @internal
1793 */
1794 template<typename T, typename Func, typename SIZE_TYPE>
1796  SIZE_TYPE offset,
1797  unsigned left, unsigned right,
1798  Func& bit_functor)
1799 {
1800  BM_ASSERT(left <= right);
1801  BM_ASSERT(right < bm::bits_in_block);
1802 
1803  unsigned is_set;
1804  unsigned start_pos = bm::gap_bfind(buf, left, &is_set);
1805  const T* BMRESTRICT pcurr = buf + start_pos;
1806  int ret = 0;
1807  if (is_set)
1808  {
1809  if (right <= *pcurr)
1810  {
1811  ret = bit_functor.add_range(offset + left, (right + 1)-left);
1812  return ret;
1813  }
1814  ret = bit_functor.add_range(offset + left, (*pcurr + 1)-left);
1815  if (ret < 0)
1816  return ret;
1817  ++pcurr;
1818  }
1819 
1820  const T* BMRESTRICT pend = buf + (*buf >> 3);
1821  for (++pcurr; pcurr <= pend; pcurr += 2)
1822  {
1823  T prev = *(pcurr-1);
1824  if (right <= *pcurr)
1825  {
1826  int sz = int(right) - int(prev);
1827  if (sz > 0)
1828  ret = bit_functor.add_range(offset + prev + 1, unsigned(sz));
1829  return ret;
1830  }
1831  ret = bit_functor.add_range(offset + prev + 1, *pcurr - prev);
1832  if (ret < 0)
1833  return ret;
1834  } // for
1835  return 0;
1836 }
1837 
1838 
1839 
1840 /*! For each non-zero block in [from, to] executes supplied functor
1841  \internal
1842 */
1843 template<typename T, typename N, typename F>
1845  N top_size, N nb_from, N nb_to, F& f)
1846 {
1847  BM_ASSERT(top_size);
1848  if (nb_from > nb_to)
1849  return 0;
1850  unsigned i_from = unsigned(nb_from >> bm::set_array_shift);
1851  unsigned j_from = unsigned(nb_from & bm::set_array_mask);
1852  unsigned i_to = unsigned(nb_to >> bm::set_array_shift);
1853  unsigned j_to = unsigned(nb_to & bm::set_array_mask);
1854 
1855  if (i_from >= top_size)
1856  return 0;
1857  if (i_to >= top_size)
1858  {
1859  i_to = unsigned(top_size-1);
1860  j_to = bm::set_sub_array_size-1;
1861  }
1862  int ret;
1863  for (unsigned i = i_from; i <= i_to; ++i)
1864  {
1865  T** blk_blk = root[i];
1866  if (!blk_blk)
1867  continue;
1868  if ((bm::word_t*)blk_blk == FULL_BLOCK_FAKE_ADDR)
1869  {
1870  unsigned j = (i == i_from) ? j_from : 0;
1871  if (!j && (i != i_to)) // full sub-block
1872  {
1873  N base_idx = bm::get_super_block_start<N>(i);
1874  ret = f.add_range(base_idx, bm::set_sub_total_bits);
1875  if (ret < 0)
1876  return ret;
1877  }
1878  else
1879  {
1880  do
1881  {
1882  N base_idx = bm::get_block_start<N>(i, j);
1883  ret = f.add_range(base_idx, bm::gap_max_bits);
1884  if (ret < 0)
1885  return ret;
1886  if ((i == i_to) && (j == j_to))
1887  return 0;
1888  } while (++j < bm::set_sub_array_size);
1889  }
1890  }
1891  else
1892  {
1893  unsigned j = (i == i_from) ? j_from : 0;
1894  do
1895  {
1896  const T* block;
1897  if (blk_blk[j])
1898  {
1899  N base_idx = bm::get_block_start<N>(i, j);
1900  if (0 != (block = blk_blk[j]))
1901  {
1902  if (BM_IS_GAP(block))
1903  ret = bm::for_each_gap_blk(BMGAP_PTR(block), base_idx, f);
1904  else
1905  ret = bm::for_each_bit_blk(block, base_idx, f);
1906  if (ret < 0)
1907  return ret;
1908  }
1909  }
1910 
1911  if ((i == i_to) && (j == j_to))
1912  return 0;
1913  } while (++j < bm::set_sub_array_size);
1914  }
1915  } // for i
1916  return 0;
1917 }
1918 
1919 
1920 /**
1921  Implementation of for_each_bit_range without boilerplave checks
1922  @internal
1923 */
1924 template<class BV, class Func>
1926  typename BV::size_type left,
1927  typename BV::size_type right,
1928  Func& bit_functor)
1929 {
1930  typedef typename BV::size_type size_type;
1931  typedef typename BV::block_idx_type block_idx_type;
1932 
1933  const typename BV::blocks_manager_type& bman = bv.get_blocks_manager();
1934  bm::word_t*** blk_root = bman.top_blocks_root();
1935  if (!blk_root)
1936  return 0;
1937 
1938  block_idx_type nblock_left = (left >> bm::set_block_shift);
1939  block_idx_type nblock_right = (right >> bm::set_block_shift);
1940 
1941  unsigned i0, j0;
1942  bm::get_block_coord(nblock_left, i0, j0);
1943  const bm::word_t* block = bman.get_block_ptr(i0, j0);
1944  unsigned nbit_left = unsigned(left & bm::set_block_mask);
1945  size_type offset = nblock_left * bm::bits_in_block;
1946  int ret = 0;
1947  if (nblock_left == nblock_right) // hit in the same block
1948  {
1949  if (!block)
1950  return ret;
1951  unsigned nbit_right = unsigned(right & bm::set_block_mask);
1952  if (BM_IS_GAP(block))
1953  {
1955  nbit_left, nbit_right, bit_functor);
1956  }
1957  else
1958  {
1959  ret = bm::for_each_bit_blk(block, offset, nbit_left, nbit_right,
1960  bit_functor);
1961  }
1962  return ret;
1963  }
1964  // process left block
1965  if (nbit_left && block)
1966  {
1967  if (BM_IS_GAP(block))
1968  {
1970  nbit_left, bm::bits_in_block-1, bit_functor);
1971  }
1972  else
1973  {
1974  ret = bm::for_each_bit_blk(block, offset, nbit_left, bm::bits_in_block-1,
1975  bit_functor);
1976  }
1977  if (ret < 0)
1978  return ret;
1979  ++nblock_left;
1980  }
1981 
1982  // process all complete blocks in the middle
1983  {
1984  block_idx_type top_blocks_size = bman.top_block_size();
1985  ret = bm::for_each_bit_block_range(blk_root, top_blocks_size,
1986  nblock_left, nblock_right-1, bit_functor);
1987  if (ret < 0)
1988  return ret;
1989  }
1990 
1991  unsigned nbit_right = unsigned(right & bm::set_block_mask);
1992  bm::get_block_coord(nblock_right, i0, j0);
1993  block = bman.get_block_ptr(i0, j0);
1994 
1995  if (block)
1996  {
1997  offset = nblock_right * bm::bits_in_block;
1998  if (BM_IS_GAP(block))
1999  {
2001  0, nbit_right, bit_functor);
2002  }
2003  else
2004  {
2005  ret = bm::for_each_bit_blk(block, offset, 0, nbit_right, bit_functor);
2006  }
2007  }
2008  return ret;
2009 }
2010 
2011 /**
2012  convert sub-blocks to an array of set 1s (32-bit)
2013  @internal
2014  */
2015 template<typename BV, typename VECT>
2016 void convert_sub_to_arr(const BV& bv, unsigned sb, VECT& vect)
2017 {
2018  vect.resize(0);
2019 
2020  typename BV::size_type from, to, idx;
2021  typename BV::size_type sb_max_bc = bm::set_sub_array_size * bm::gap_max_bits;
2022  from = sb * sb_max_bc;
2023  to = (sb+1) * sb_max_bc;
2024  if (!to || to > bm::id_max) // overflow check
2025  to = bm::id_max;
2026 
2027  typename BV::enumerator en = bv.get_enumerator(from);
2028  for (; en.valid(); ++en)
2029  {
2030  idx = *en;
2031  if (idx >= to)
2032  break;
2033  idx -= from;
2034  vect.push_back((typename VECT::value_type)idx);
2035  } // for en
2036 }
2037 
2038 
2039 } // namespace bm
2040 
2041 #ifdef _MSC_VER
2042 #pragma warning( pop )
2043 #endif
2044 
2045 #endif
ncbi::TMaskedQueryRegions mask
Definitions(internal)
#define IS_FULL_BLOCK(addr)
Definition: bmdef.h:162
#define BMRESTRICT
Definition: bmdef.h:203
#define BMNOEXCEPT
Definition: bmdef.h:82
#define BMGAP_PTR(ptr)
Definition: bmdef.h:189
#define BM_IS_GAP(ptr)
Definition: bmdef.h:191
#define BLOCK_ADDR_SAN(addr)
Definition: bmdef.h:160
#define BM_ASSERT
Definition: bmdef.h:139
#define FULL_BLOCK_FAKE_ADDR
Definition: bmdef.h:158
#define BM_VECT_ALIGN_ATTR
Definition: bmdef.h:328
#define FULL_SUB_BLOCK_REAL_ADDR
Definition: bmdef.h:159
#define BM_VECT_ALIGN
Definition: bmdef.h:327
Bit manipulation primitives (internal)
#define T(s)
Definition: common.h:230
static DLIST_TYPE *DLIST_NAME() first(DLIST_LIST_TYPE *list)
Definition: dlist.tmpl.h:46
static DLIST_TYPE *DLIST_NAME() last(DLIST_LIST_TYPE *list)
Definition: dlist.tmpl.h:51
static DLIST_TYPE *DLIST_NAME() prev(DLIST_LIST_TYPE *list, DLIST_TYPE *item)
Definition: dlist.tmpl.h:61
static char tmp[3200]
Definition: utf8.c:42
int offset
Definition: replacements.h:160
NCBI_NS_STD::string::size_type SIZE_TYPE
Definition: ncbistr.hpp:132
bm::id_t bit_block_count(const bm::word_t *block) noexcept
Bitcount for bit block.
Definition: bmfunc.h:5051
bm::id_t bit_operation_sub_count(const bm::word_t *src1, const bm::word_t *src2) noexcept
Performs bitblock SUB operation and calculates bitcount of the result.
Definition: bmfunc.h:7675
int for_each_bit_blk(const bm::word_t *block, SIZE_TYPE offset, Func &bit_functor)
for-each visitor, calls a visitor functor for each 1 bit group
Definition: bmalgo_impl.h:1597
unsigned short bitscan(V w, B *bits) noexcept
Templated Bitscan with dynamic dispatch for best type.
Definition: bmfunc.h:769
unsigned short bitscan_wave(const bm::word_t *w_ptr, unsigned char *bits) noexcept
Unpacks word wave (Nx 32-bit words)
Definition: bmfunc.h:9635
bm::id_t bit_operation_xor_any(const bm::word_t *src1, const bm::word_t *src2) noexcept
Performs bitblock XOR operation test.
Definition: bmfunc.h:8575
bool bit_is_all_zero(const bm::word_t *start) noexcept
Returns "true" if all bits in the block are 0.
Definition: bmfunc.h:1550
bm::id_t bit_operation_or_any(const bm::word_t *src1, const bm::word_t *src2) noexcept
Performs bitblock OR operation test.
Definition: bmfunc.h:7802
bm::id_t bit_operation_and_any(const bm::word_t *src1, const bm::word_t *src2) noexcept
Performs bitblock AND operation test.
Definition: bmfunc.h:7650
bm::id_t bit_operation_sub_any(const bm::word_t *src1, const bm::word_t *src2) noexcept
Performs bitblock test of SUB operation.
Definition: bmfunc.h:7730
bm::id_t bit_operation_and_count(const bm::word_t *src1, const bm::word_t *src2) noexcept
Performs bitblock AND operation and calculates bitcount of the result.
Definition: bmfunc.h:7626
set_operation
Codes of set operations.
Definition: bmconst.h:168
@ set_COUNT_SUB_AB
Definition: bmconst.h:178
@ set_COUNT_XOR
Definition: bmconst.h:176
@ set_COUNT_OR
Definition: bmconst.h:177
@ set_COUNT_B
Definition: bmconst.h:181
@ set_COUNT_SUB_BA
Definition: bmconst.h:179
@ set_COUNT_AND
Definition: bmconst.h:175
@ set_COUNT
Definition: bmconst.h:174
@ set_COUNT_A
Definition: bmconst.h:180
@ BM_BIT
No GAP compression strategy. All new blocks are bit blocks.
Definition: bmconst.h:147
void distance_operation(const BV &bv1, const BV &bv2, distance_metric_descriptor *dmit, distance_metric_descriptor *dmit_end) noexcept
Distance computing template function.
Definition: bmalgo_impl.h:766
BV::size_type distance_and_operation(const BV &bv1, const BV &bv2) noexcept
Distance AND computing template function.
Definition: bmalgo_impl.h:853
void distance_operation_any(const BV &bv1, const BV &bv2, distance_metric_descriptor *dmit, distance_metric_descriptor *dmit_end) noexcept
Distance screening template function.
Definition: bmalgo_impl.h:922
distance_metric
Distance metrics codes defined for vectors A and B.
Definition: bmalgo_impl.h:58
distance_metric operation2metric(set_operation op) noexcept
Convert set operation into compatible distance metric.
Definition: bmalgo_impl.h:73
@ COUNT_XOR
(A ^ B).count()
Definition: bmalgo_impl.h:60
@ COUNT_SUB_AB
(A - B).count()
Definition: bmalgo_impl.h:62
@ COUNT_A
A.count()
Definition: bmalgo_impl.h:64
@ COUNT_B
B.count()
Definition: bmalgo_impl.h:65
@ COUNT_AND
(A & B).count()
Definition: bmalgo_impl.h:59
@ COUNT_OR
(A | B).count()
Definition: bmalgo_impl.h:61
@ COUNT_SUB_BA
(B - A).count()
Definition: bmalgo_impl.h:63
bm::id_t gap_bitset_sub_any(const unsigned *block, const T *buf) noexcept
Compute bitcount test of bit block SUB masked by GAP block.
Definition: bmfunc.h:4291
unsigned gap_operation_any_xor(const gap_word_t *vect1, const gap_word_t *vect2) noexcept
GAP XOR operation test.
Definition: bmfunc.h:6625
unsigned gap_limit(const T *buf, const T *glevel_len) noexcept
Returs GAP block capacity limit.
Definition: bmfunc.h:1635
unsigned gap_count_or(const gap_word_t *vect1, const gap_word_t *vect2) noexcept
GAP bitcount OR operation test.
Definition: bmfunc.h:6686
int for_each_gap_blk(const T *buf, SIZE_TYPE offset, Func &bit_functor)
for-each visitor, calls a special visitor functor for each 1 bit range
Definition: bmalgo_impl.h:1760
bm::id_t gap_bitset_xor_count(const unsigned *block, const T *buf) noexcept
Compute bitcount of bit block XOR masked by GAP block.
Definition: bmfunc.h:4329
gap_word_t * gap_operation_or(const gap_word_t *vect1, const gap_word_t *vect2, gap_word_t *tmp_buf, unsigned &dsize) noexcept
GAP OR operation.
Definition: bmfunc.h:6666
bm::id_t gap_bitset_sub_count(const unsigned *block, const T *buf) noexcept
Compute bitcount of bit block SUB masked by GAP block.
Definition: bmfunc.h:4256
unsigned gap_count_xor(const gap_word_t *vect1, const gap_word_t *vect2) noexcept
GAP bitcount XOR operation test.
Definition: bmfunc.h:6641
unsigned gap_test_unr(const T *buf, const unsigned pos) noexcept
Tests if bit = pos is true. Analog of bm::gap_test with SIMD unrolling.
Definition: bmfunc.h:1833
bool gap_is_all_zero(const bm::gap_word_t *buf) noexcept
Checks if GAP block is all-zero.
Definition: bmfunc.h:1577
void gap_convert_to_bitset(unsigned *dest, const T *buf, unsigned len=0) noexcept
GAP block to bitblock conversion.
Definition: bmfunc.h:4475
unsigned gap_count_sub(const gap_word_t *vect1, const gap_word_t *vect2) noexcept
GAP bitcount SUB (AND NOT) operation test.
Definition: bmfunc.h:6757
bm::id_t gap_bitset_xor_any(const unsigned *block, const T *buf) noexcept
Compute bitcount test of bit block XOR masked by GAP block.
Definition: bmfunc.h:4367
unsigned gap_bit_count_unr(const T *buf) noexcept
Calculates number of bits ON in GAP buffer. Loop unrolled version.
Definition: bmfunc.h:2327
unsigned gap_operation_any_and(const gap_word_t *vect1, const gap_word_t *vect2) noexcept
GAP AND operation test.
Definition: bmfunc.h:6543
bm::id_t gap_bitset_or_count(const unsigned *block, const T *buf) noexcept
Compute bitcount of bit block OR masked by GAP block.
Definition: bmfunc.h:4405
bm::id_t gap_bitset_and_count(const unsigned *block, const T *pcurr) noexcept
Compute bitcount of bit block AND masked by GAP block.
Definition: bmfunc.h:4198
int for_each_gap_blk_range(const T *buf, SIZE_TYPE offset, unsigned left, unsigned right, Func &bit_functor)
for-each visitor, calls a special visitor functor for each 1 bit range
Definition: bmalgo_impl.h:1795
unsigned gap_set_value(unsigned val, T *buf, unsigned pos, unsigned *is_set) noexcept
Sets or clears bit in the GAP buffer.
Definition: bmfunc.h:3254
unsigned gap_count_and(const gap_word_t *vect1, const gap_word_t *vect2) noexcept
GAP bitcount AND operation test.
Definition: bmfunc.h:6560
bm::id_t gap_bitset_and_any(const unsigned *block, const T *pcurr) noexcept
Bitcount test of bit block AND masked by GAP block.
Definition: bmfunc.h:4226
unsigned gap_operation_any_sub(const gap_word_t *vect1, const gap_word_t *vect2) noexcept
GAP SUB operation test.
Definition: bmfunc.h:6738
bm::id_t gap_bitset_or_any(const unsigned *block, const T *buf) noexcept
Compute bitcount test of bit block OR masked by GAP block.
Definition: bmfunc.h:4437
unsigned int
A callback function used to compare two keys in a database.
Definition: types.hpp:1210
void combine_and_sorted(BV &bv, It first, It last)
AND Combine bitvector and the iterable sequence.
Definition: bmalgo_impl.h:1333
void export_array(BV &bv, It first, It last)
Export bitset from an array of binary data representing the bit vector.
Definition: bmalgo_impl.h:1423
void combine_and(BV &bv, It first, It last)
AND Combine bitvector and the iterable sequence.
Definition: bmalgo_impl.h:1365
void combine_sub(BV &bv, It first, It last)
SUB Combine bitvector and the iterable sequence.
Definition: bmalgo_impl.h:1248
void combine_xor(BV &bv, It first, It last)
XOR Combine bitvector and the iterable sequence.
Definition: bmalgo_impl.h:1161
void combine_or(BV &bv, It first, It last)
OR Combine bitvector and the iterable sequence.
Definition: bmalgo_impl.h:1080
BV::size_type count_intervals(const BV &bv)
Compute number of bit intervals (GAPs) in the bitvector.
Definition: bmalgo_impl.h:1389
char * buf
int i
#include<zmmintrin.h>
Definition: bm.h:78
const unsigned set_array_mask
Definition: bmconst.h:97
void combine_any_operation_with_block(const bm::word_t *blk, unsigned gap, const bm::word_t *arg_blk, unsigned arg_gap, distance_metric_descriptor *dmit, distance_metric_descriptor *dmit_end) noexcept
Internal function computes different existense of distance metric.
Definition: bmalgo_impl.h:443
It block_range_scan(It first, It last, SIZE_TYPE nblock, SIZE_TYPE *max_id) noexcept
Internal algorithms scans the input for the block range limit.
Definition: bmalgo_impl.h:1047
bm::id_t(* bit_operation_count_func_type)(const bm::word_t *, const bm::word_t *)
Definition: bmfunc.h:9547
const unsigned id_max
Definition: bmconst.h:109
unsigned int word_t
Definition: bmconst.h:39
int for_each_bit_range_no_check(const BV &bv, typename BV::size_type left, typename BV::size_type right, Func &bit_functor)
Implementation of for_each_bit_range without boilerplave checks.
Definition: bmalgo_impl.h:1925
const unsigned set_block_mask
Definition: bmconst.h:57
const unsigned set_sub_array_size
Definition: bmconst.h:95
void get_block_coord(BI_TYPE nb, unsigned &i, unsigned &j) noexcept
Recalc linear bvector block index into 2D matrix coordinates.
Definition: bmfunc.h:180
const unsigned set_total_blocks
Definition: bmconst.h:111
int for_each_bit_block_range(T ***root, N top_size, N nb_from, N nb_to, F &f)
Definition: bmalgo_impl.h:1844
void convert_sub_to_arr(const BV &bv, unsigned sb, VECT &vect)
convert sub-blocks to an array of set 1s (32-bit)
Definition: bmalgo_impl.h:2016
const unsigned set_word_shift
Definition: bmconst.h:72
const unsigned set_sub_total_bits
Definition: bmconst.h:100
const unsigned set_block_size
Definition: bmconst.h:55
unsigned long long int id64_t
Definition: bmconst.h:35
unsigned gap_bfind(const T *buf, unsigned pos, unsigned *is_set) noexcept
Definition: bmfunc.h:1725
unsigned int id_t
Definition: bmconst.h:38
const unsigned gap_max_buff_len
Definition: bmconst.h:80
unsigned mask_r_u32(unsigned nbit) noexcept
Definition: bmutil.h:513
unsigned combine_count_and_operation_with_block(const bm::word_t *blk, const bm::word_t *arg_blk) noexcept
Internal function computes AND distance.
Definition: bmalgo_impl.h:406
void distance_stage(const distance_metric_descriptor *dmit, const distance_metric_descriptor *dmit_end, bool *is_all_and) noexcept
Staging function for distance operation.
Definition: bmalgo_impl.h:733
const unsigned short set_bitscan_wave_size
Size of bit decode wave in words.
Definition: bmfunc.h:9623
const unsigned set_array_shift
Definition: bmconst.h:96
unsigned short gap_word_t
Definition: bmconst.h:78
const unsigned gap_max_bits
Definition: bmconst.h:81
void for_each_block(T ***root, unsigned size1, F &f, BLOCK_IDX start)
Definition: bmfunc.h:2173
const unsigned set_block_shift
Definition: bmconst.h:56
const unsigned set_word_mask
Definition: bmconst.h:73
T min_value(T v1, T v2) noexcept
Get minimum of 2 values.
Definition: bmutil.h:103
const unsigned bits_in_block
Definition: bmconst.h:114
void combine_count_operation_with_block(const bm::word_t *blk, const bm::word_t *arg_blk, distance_metric_descriptor *dmit, distance_metric_descriptor *dmit_end) noexcept
Internal function computes different distance metrics.
Definition: bmalgo_impl.h:189
bool is_const_set_operation(set_operation op) noexcept
Returns true if set operation is constant (bitcount)
Definition: bmfunc.h:1330
unsigned mask_l_u32(unsigned nbit) noexcept
Definition: bmutil.h:522
double value_type
The numeric datatype used by the parser.
Definition: muParserDef.h:228
const struct ncbi::grid::netcache::search::fields::SIZE size
#define F(x)
Make a parametrized function appear to have only one variable.
Definition: ncbi_math.c:342
double f(double x_, const double &y_)
Definition: njn_root.hpp:188
static unsigned cnt[256]
functor-adaptor for back-inserter
Definition: bmalgo_impl.h:159
int add_range(size_type offset, size_type size)
Definition: bmalgo_impl.h:171
int add_bits(size_type offset, const unsigned char *bits, unsigned size)
Definition: bmalgo_impl.h:165
functor-adaptor for C-style callbacks
Definition: bmalgo_impl.h:121
bit_visitor_callback_adaptor(void *h, bit_visitor_callback_type cb_func)
Definition: bmalgo_impl.h:124
int add_bits(size_type offset, const unsigned char *bits, unsigned size)
Definition: bmalgo_impl.h:128
bit_visitor_callback_type func_
Definition: bmalgo_impl.h:150
int add_range(size_type offset, size_type size)
Definition: bmalgo_impl.h:138
Distance metric descriptor, holds metric code and result.
Definition: bmalgo_impl.h:87
void reset() noexcept
Sets metric result to 0.
Definition: bmalgo_impl.h:109
distance_metric_descriptor(distance_metric m) noexcept
Definition: bmalgo_impl.h:97
static bit_operation_count_func_type bit_operation_count(unsigned i)
Definition: bmfunc.h:9574
#define N
Definition: crc32.c:57
Modified on Sun Apr 14 05:24:30 2024 by modify_doxy.py rev. 669887