BitMagic-C++
bmaggregator.h
Go to the documentation of this file.
1 #ifndef BMAGGREGATOR__H__INCLUDED__
2 #define BMAGGREGATOR__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 bmaggregator.h
22  \brief Algorithms for fast aggregation of N bvectors
23 */
24 
25 
26 #ifndef BM__H__INCLUDED__
27 // BitMagic utility headers do not include main "bm.h" declaration
28 // #include "bm.h" or "bm64.h" explicitly
29 # error missing include (bm.h or bm64.h)
30 #endif
31 
32 
33 #include "bmfunc.h"
34 #include "bmdef.h"
35 
36 #include "bmalgo_impl.h"
37 
38 
39 namespace bm
40 {
41 
42 
43 /**
44  Algorithms for fast aggregation of a group of bit-vectors
45 
46  Current implementation can aggregate up to max_aggregator_cap vectors
47  (TODO: remove this limitation)
48 
49  Algorithms of this class use cache locality optimizations and efficient
50  on cases, wehen we need to apply the same logical operation (aggregate)
51  more than 2x vectors.
52 
53  TARGET = BV1 or BV2 or BV3 or BV4 ...
54 
55  @ingroup setalgo
56 */
57 template<typename BV>
59 {
60 public:
61  typedef BV bvector_type;
62  typedef typename BV::size_type size_type;
65 
67 
68  /// Maximum aggregation capacity in one pass
69  enum max_size
70  {
72  };
73 
74  /// Codes for aggregation operations which can be pipelined for efficient execution
75  ///
76  enum operation
77  {
80  };
81 
83  {
88  };
89 
90 public:
91 
92  // -----------------------------------------------------------------------
93  /*! @name Construction and setup */
94  //@{
95  aggregator();
96  ~aggregator();
97 
98  /**
99  \brief set on-the-fly bit-block compression
100  By default aggregator does not try to optimize result, but in some cases
101  it can be quite a lot faster than calling bvector<>::optimize() later
102  (because block data sits in CPU cache).
103 
104  \param opt - optimization mode (full compression by default)
105  */
108  { opt_mode_ = opt; }
109 
110  void set_compute_count(bool count_mode)
111  {
112  compute_count_ = count_mode; count_ = 0;
113  }
114 
115  //@}
116 
117 
118  // -----------------------------------------------------------------------
119 
120  /*! @name Methods to setup argument groups and run operations on groups */
121  //@{
122 
123  /**
124  Attach source bit-vector to a argument group (0 or 1).
125  Arg group 1 used for fused operations like (AND-SUB)
126  \param bv - input bit-vector pointer to attach
127  \param agr_group - input argument group (0 - default, 1 - fused op)
128 
129  @return current arg group size (0 if vector was not added (empty))
130  @sa reset
131  */
132  unsigned add(const bvector_type* bv, unsigned agr_group = 0) BMNOEXCEPT;
133 
134  /**
135  Reset aggregate groups, forget all attached vectors
136  */
137  void reset() BMNOEXCEPT;
138 
139  /**
140  Aggregate added group of vectors using logical OR
141  Operation does NOT perform an explicit reset of arg group(s)
142 
143  \param bv_target - target vector (input is arg group 0)
144 
145  @sa add, reset
146  */
147  void combine_or(bvector_type& bv_target);
148 
149  /**
150  Aggregate added group of vectors using logical AND
151  Operation does NOT perform an explicit reset of arg group(s)
152 
153  \param bv_target - target vector (input is arg group 0)
154 
155  @sa add, reset
156  */
157  void combine_and(bvector_type& bv_target);
158 
159  /**
160  Aggregate added group of vectors using fused logical AND-SUB
161  Operation does NOT perform an explicit reset of arg group(s)
162 
163  \param bv_target - target vector (input is arg group 0(AND), 1(SUB) )
164 
165  \return true if anything was found
166 
167  @sa add, reset
168  */
169  bool combine_and_sub(bvector_type& bv_target);
170 
171 
172  /**
173  Aggregate added group of vectors using fused logical AND-SUB
174  Operation does NOT perform an explicit reset of arg group(s)
175  Operation can terminate early if anything was found.
176 
177  \param bv_target - target vector (input is arg group 0(AND), 1(SUB) )
178  \param any - if true, search result will terminate of first found result
179 
180  \return true if anything was found
181 
182  @sa add, reset
183  */
184  bool combine_and_sub(bvector_type& bv_target, bool any);
185 
186  bool find_first_and_sub(size_type& idx);
187 
188 
189  /**
190  Aggregate added group of vectors using SHIFT-RIGHT and logical AND
191  Operation does NOT perform an explicit reset of arg group(s)
192 
193  \param bv_target - target vector (input is arg group 0)
194 
195  @return bool if anything was found
196 
197  @sa add, reset
198  */
199  void combine_shift_right_and(bvector_type& bv_target);
200 
201  /**
202  Set search hint for the range, where results needs to be searched
203  (experimental for internal use).
204  */
206 
207  size_type count() const { return count_; }
208 
209  //@}
210 
211  // -----------------------------------------------------------------------
212 
213  /*! @name Logical operations (C-style interface) */
214  //@{
215 
216  /**
217  Aggregate group of vectors using logical OR
218  \param bv_target - target vector
219  \param bv_src - array of pointers on bit-vector aggregate arguments
220  \param src_size - size of bv_src (how many vectors to aggregate)
221  */
222  void combine_or(bvector_type& bv_target,
223  const bvector_type_const_ptr* bv_src, unsigned src_size);
224 
225  /**
226  Aggregate group of vectors using logical AND
227  \param bv_target - target vector
228  \param bv_src - array of pointers on bit-vector aggregate arguments
229  \param src_size - size of bv_src (how many vectors to aggregate)
230  */
231  void combine_and(bvector_type& bv_target,
232  const bvector_type_const_ptr* bv_src, unsigned src_size);
233 
234  /**
235  Fusion aggregate group of vectors using logical AND MINUS another set
236 
237  \param bv_target - target vector
238  \param bv_src_and - array of pointers on bit-vectors for AND
239  \param src_and_size - size of AND group
240  \param bv_src_sub - array of pointers on bit-vectors for SUBstract
241  \param src_sub_size - size of SUB group
242  \param any - flag if caller needs any results asap (incomplete results)
243 
244  \return true when found
245  */
246  bool combine_and_sub(bvector_type& bv_target,
247  const bvector_type_const_ptr* bv_src_and, unsigned src_and_size,
248  const bvector_type_const_ptr* bv_src_sub, unsigned src_sub_size,
249  bool any);
250 
251  bool find_first_and_sub(size_type& idx,
252  const bvector_type_const_ptr* bv_src_and, unsigned src_and_size,
253  const bvector_type_const_ptr* bv_src_sub, unsigned src_sub_size);
254 
255  /**
256  Fusion aggregate group of vectors using SHIFT right with AND
257 
258  \param bv_target - target vector
259  \param bv_src_and - array of pointers on bit-vectors for AND masking
260  \param src_and_size - size of AND group
261  \param any - flag if caller needs any results asap (incomplete results)
262 
263  \return true when found
264  */
265  bool combine_shift_right_and(bvector_type& bv_target,
266  const bvector_type_const_ptr* bv_src_and, unsigned src_and_size,
267  bool any);
268 
269 
270  //@}
271 
272  // -----------------------------------------------------------------------
273 
274  /*! @name Horizontal Logical operations used for tests (C-style interface) */
275  //@{
276 
277  /**
278  Horizontal OR aggregation (potentially slower) method.
279  \param bv_target - target vector
280  \param bv_src - array of pointers on bit-vector aggregate arguments
281  \param src_size - size of bv_src (how many vectors to aggregate)
282  */
283  void combine_or_horizontal(bvector_type& bv_target,
284  const bvector_type_const_ptr* bv_src, unsigned src_size);
285  /**
286  Horizontal AND aggregation (potentially slower) method.
287  \param bv_target - target vector
288  \param bv_src - array of pointers on bit-vector aggregate arguments
289  \param src_size - size of bv_src (how many vectors to aggregate)
290  */
291  void combine_and_horizontal(bvector_type& bv_target,
292  const bvector_type_const_ptr* bv_src, unsigned src_size);
293 
294  /**
295  Horizontal AND-SUB aggregation (potentially slower) method.
296  \param bv_target - target vector
297  \param bv_src_and - array of pointers on bit-vector to AND aggregate
298  \param src_and_size - size of bv_src_and
299  \param bv_src_sub - array of pointers on bit-vector to SUB aggregate
300  \param src_sub_size - size of bv_src_sub
301  */
303  const bvector_type_const_ptr* bv_src_and,
304  unsigned src_and_size,
305  const bvector_type_const_ptr* bv_src_sub,
306  unsigned src_sub_size);
307 
308  //@}
309 
310 
311  // -----------------------------------------------------------------------
312 
313  /*! @name Pipeline operations */
314  //@{
315 
316  /** Get current operation code */
317  int get_operation() const BMNOEXCEPT { return operation_; }
318 
319  /** Set operation code for the aggregator */
320  void set_operation(int op_code) BMNOEXCEPT { operation_ = op_code; }
321 
322  /**
323  Prepare operation, create internal resources, analyse dependencies.
324  Prerequisites are: that operation is set and all argument vectors are added
325  */
326  void stage(bm::word_t* temp_block);
327 
328  /**
329  Run a step of current arrgegation operation
330  */
331  operation_status run_step(unsigned i, unsigned j);
332 
333  operation_status get_operation_status() const { return operation_status_; }
334 
335  const bvector_type* get_target() const { return bv_target_; }
336 
337  bm::word_t* get_temp_block() { return ar_->tb1; }
338 
339  //@}
340 
341 protected:
343  typedef typename BV::block_idx_type block_idx_type;
344 
345 
346  void combine_or(unsigned i, unsigned j,
347  bvector_type& bv_target,
348  const bvector_type_const_ptr* bv_src, unsigned src_size);
349 
350  void combine_and(unsigned i, unsigned j,
351  bvector_type& bv_target,
352  const bvector_type_const_ptr* bv_src, unsigned src_size);
353 
354  digest_type combine_and_sub(unsigned i, unsigned j,
355  const bvector_type_const_ptr* bv_src_and, unsigned src_and_size,
356  const bvector_type_const_ptr* bv_src_sub, unsigned src_sub_size,
357  int* is_result_full);
358 
359  void prepare_shift_right_and(bvector_type& bv_target,
360  const bvector_type_const_ptr* bv_src, unsigned src_size);
361 
362  bool combine_shift_right_and(unsigned i, unsigned j,
363  bvector_type& bv_target,
364  const bvector_type_const_ptr* bv_src, unsigned src_size);
365 
366  static
367  unsigned resize_target(bvector_type& bv_target,
368  const bvector_type_const_ptr* bv_src,
369  unsigned src_size,
370  bool init_clear = true);
371 
372  static
373  unsigned max_top_blocks(const bvector_type_const_ptr* bv_src,
374  unsigned src_size) BMNOEXCEPT;
375 
377  unsigned src_size,
378  unsigned i, unsigned j,
379  unsigned* arg_blk_count,
380  unsigned* arg_blk_gap_count) BMNOEXCEPT;
381 
383  unsigned src_size,
384  unsigned i, unsigned j,
385  unsigned* arg_blk_count,
386  unsigned* arg_blk_gap_count) BMNOEXCEPT;
387 
388 
389  bool process_bit_blocks_or(blocks_manager_type& bman_target,
390  unsigned i, unsigned j, unsigned block_count);
391 
392  void process_gap_blocks_or(unsigned block_count);
393 
394  digest_type process_bit_blocks_and(unsigned block_count, digest_type digest);
395 
396  digest_type process_gap_blocks_and(unsigned block_count, digest_type digest);
397 
398  bool test_gap_blocks_and(unsigned block_count, unsigned bit_idx);
399  bool test_gap_blocks_sub(unsigned block_count, unsigned bit_idx);
400 
401  digest_type process_bit_blocks_sub(unsigned block_count, digest_type digest);
402 
403  digest_type process_gap_blocks_sub(unsigned block_count, digest_type digest);
404 
405  static
406  unsigned find_effective_sub_block_size(unsigned i,
407  const bvector_type_const_ptr* bv_src,
408  unsigned src_size,
409  bool top_null_as_zero) BMNOEXCEPT;
410 
411  static
412  bool any_carry_overs(const unsigned char* carry_overs,
413  unsigned co_size) BMNOEXCEPT;
414 
415  /**
416  @return carry over
417  */
418  static
420  const bm::word_t* BMRESTRICT arg_blk,
421  digest_type& BMRESTRICT digest,
422  unsigned carry_over) BMNOEXCEPT;
423 
424  static
425  const bm::word_t* get_arg_block(const bvector_type_const_ptr* bv_src,
426  unsigned k, unsigned i, unsigned j) BMNOEXCEPT;
427 
429 
430 private:
431  /// Memory arena for logical operations
432  ///
433  /// @internal
434  struct arena
435  {
437  BM_DECLARE_TEMP_BLOCK(tb_opt) ///< temp block for results optimization
438  const bm::word_t* v_arg_or_blk[max_aggregator_cap]; ///< source blocks list (OR)
439  const bm::gap_word_t* v_arg_or_blk_gap[max_aggregator_cap]; ///< source GAP blocks list (OR)
440  const bm::word_t* v_arg_and_blk[max_aggregator_cap]; ///< source blocks list (AND)
441  const bm::gap_word_t* v_arg_and_blk_gap[max_aggregator_cap]; ///< source GAP blocks list (AND)
442 
443  bvector_type_const_ptr arg_bv0[max_aggregator_cap]; ///< arg group 0
444  bvector_type_const_ptr arg_bv1[max_aggregator_cap]; ///< arg group 1
445  unsigned char carry_overs_[max_aggregator_cap]; /// carry over flags
446  };
447 
448  aggregator(const aggregator&) = delete;
449  aggregator& operator=(const aggregator&) = delete;
450 
451 private:
452  arena* ar_; ///< data arena ptr (heap allocated)
453  unsigned arg_group0_size = 0;
454  unsigned arg_group1_size = 0;
455  allocator_pool_type pool_; ///< pool for operations with cyclic mem.use
456 
457  bm::word_t* temp_blk_= 0; ///< external temp block ptr
458  int operation_ = 0; ///< operation code (default: not defined)
459  operation_status operation_status_ = op_undefined;
460  bvector_type* bv_target_ = 0; ///< target bit-vector
461  unsigned top_block_size_ = 0; ///< operation top block (i) size
462 
463  // search range setting (hint) [from, to]
464  bool range_set_ = false; ///< range flag
465  size_type range_from_ = bm::id_max; ///< search from
466  size_type range_to_ = bm::id_max; ///< search to
467 
468  typename bvector_type::optmode opt_mode_; ///< perform search result optimization
469  bool compute_count_; ///< compute search result count
470  size_type count_; ///< search result count
471 };
472 
473 
474 
475 
476 // ------------------------------------------------------------------------
477 //
478 // ------------------------------------------------------------------------
479 
480 /**
481  Experimental method ro run multiple aggregators in sync
482 
483  Pipeleine algorithm walts the sequence of iterators (pointers on aggregators)
484  and run them all via aggregator<>::run_step() method
485 
486  @param first - iterator (pointer on aggregator)
487  @param last - iterator (pointer on aggregator)
488  @ingroup setalgo
489 */
490 template<typename Agg, typename It>
491 void aggregator_pipeline_execute(It first, It last)
492 {
493  bm::word_t* tb = (*first)->get_temp_block();
494 
495  int pipeline_size = 0;
496  for (It it = first; it != last; ++it, ++pipeline_size)
497  {
498  Agg& agg = *(*it);
499  agg.stage(tb);
500  }
501  for (unsigned i = 0; i < bm::set_sub_array_size; ++i)
502  {
503  unsigned j = 0;
504  do
505  {
506  // run all aggregators for the [i,j] coordinate
507  unsigned w = 0;
508  for (It it = first; it != last; ++it, ++w)
509  {
510  Agg& agg = *(*it);
511  auto op_st = agg.get_operation_status();
512  if (op_st != Agg::op_done)
513  {
514  op_st = agg.run_step(i, j);
515  pipeline_size -= (op_st == Agg::op_done);
516  }
517  } // for it
518  if (pipeline_size <= 0)
519  return;
520 
521  } while (++j < bm::set_sub_array_size);
522 
523  } // for i
524 }
525 
526 
527 // ------------------------------------------------------------------------
528 //
529 // ------------------------------------------------------------------------
530 
531 
532 template<typename BV>
534 : opt_mode_(bvector_type::opt_none),
535  compute_count_(false),
536  count_(0)
537 {
538  ar_ = (arena*) bm::aligned_new_malloc(sizeof(arena));
539 }
540 
541 // ------------------------------------------------------------------------
542 
543 template<typename BV>
545 {
546  BM_ASSERT(ar_);
547  bm::aligned_free(ar_);
548  delete bv_target_;
549 }
550 
551 // ------------------------------------------------------------------------
552 
553 template<typename BV>
555 {
556  arg_group0_size = arg_group1_size = operation_ = top_block_size_ = 0;
557  operation_status_ = op_undefined;
558  range_set_ = false;
559  range_from_ = range_to_ = bm::id_max;
560  count_ = 0;
561 }
562 
563 // ------------------------------------------------------------------------
564 
565 template<typename BV>
567 {
568  range_from_ = from; range_to_ = to;
569  range_set_ = true;
570 }
571 
572 // ------------------------------------------------------------------------
573 
574 template<typename BV>
577 {
578  if (!bv_target_)
579  {
580  bv_target_ = new bvector_type(); //TODO: get rid of "new"
581  bv_target_->init();
582  }
583  return bv_target_;
584 }
585 
586 // ------------------------------------------------------------------------
587 
588 template<typename BV>
590  unsigned agr_group) BMNOEXCEPT
591 {
592  BM_ASSERT_THROW(agr_group <= 1, BM_ERR_RANGE);
593  BM_ASSERT(agr_group <= 1);
594 
595  if (agr_group) // arg group 1
596  {
597  BM_ASSERT(arg_group1_size < max_aggregator_cap);
598  BM_ASSERT_THROW(arg_group1_size < max_aggregator_cap, BM_ERR_RANGE);
599 
600  if (!bv)
601  return arg_group1_size;
602 
603  ar_->arg_bv1[arg_group1_size++] = bv;
604  return arg_group1_size;
605  }
606  else // arg group 0
607  {
608  BM_ASSERT(arg_group0_size < max_aggregator_cap);
609  BM_ASSERT_THROW(arg_group0_size < max_aggregator_cap, BM_ERR_RANGE);
610 
611  if (!bv)
612  return arg_group0_size;
613 
614  ar_->arg_bv0[arg_group0_size++] = bv;
615  return arg_group0_size;
616  }
617 }
618 
619 // ------------------------------------------------------------------------
620 
621 template<typename BV>
623 {
624  combine_or(bv_target, ar_->arg_bv0, arg_group0_size);
625 }
626 
627 // ------------------------------------------------------------------------
628 
629 template<typename BV>
631 {
632  combine_and(bv_target, ar_->arg_bv0, arg_group0_size);
633 }
634 
635 // ------------------------------------------------------------------------
636 
637 template<typename BV>
639 {
640  return combine_and_sub(bv_target,
641  ar_->arg_bv0, arg_group0_size,
642  ar_->arg_bv1, arg_group1_size, false);
643 }
644 
645 // ------------------------------------------------------------------------
646 
647 template<typename BV>
649 {
650  return combine_and_sub(bv_target,
651  ar_->arg_bv0, arg_group0_size,
652  ar_->arg_bv1, arg_group1_size, any);
653 }
654 
655 // ------------------------------------------------------------------------
656 
657 template<typename BV>
659 {
660  return find_first_and_sub(idx,
661  ar_->arg_bv0, arg_group0_size,
662  ar_->arg_bv1, arg_group1_size);
663 }
664 
665 // ------------------------------------------------------------------------
666 
667 template<typename BV>
669 {
670  count_ = 0;
671  combine_shift_right_and(bv_target, ar_->arg_bv0, arg_group0_size, false);
672 }
673 
674 // ------------------------------------------------------------------------
675 
676 template<typename BV>
678  const bvector_type_const_ptr* bv_src, unsigned src_size)
679 {
680  BM_ASSERT_THROW(src_size < max_aggregator_cap, BM_ERR_RANGE);
681  if (!src_size)
682  {
683  bv_target.clear();
684  return;
685  }
686  unsigned top_blocks = resize_target(bv_target, bv_src, src_size);
687  for (unsigned i = 0; i < top_blocks; ++i)
688  {
689  unsigned set_array_max =
690  find_effective_sub_block_size(i, bv_src, src_size, false);
691  for (unsigned j = 0; j < set_array_max; ++j)
692  {
693  combine_or(i, j, bv_target, bv_src, src_size);
694  } // for j
695  } // for i
696 }
697 
698 // ------------------------------------------------------------------------
699 
700 template<typename BV>
702  const bvector_type_const_ptr* bv_src,
703  unsigned src_size)
704 {
705  BM_ASSERT_THROW(src_size < max_aggregator_cap, BM_ERR_RANGE);
706  if (src_size == 1)
707  {
708  const bvector_type* bv = bv_src[0];
709  bv_target = *bv;
710  return;
711  }
712  if (!src_size)
713  {
714  bv_target.clear();
715  return;
716  }
717  unsigned top_blocks = resize_target(bv_target, bv_src, src_size);
718  for (unsigned i = 0; i < top_blocks; ++i)
719  {
720  // TODO: find range, not just size
721  unsigned set_array_max =
722  find_effective_sub_block_size(i, bv_src, src_size, true);
723  for (unsigned j = 0; j < set_array_max; ++j)
724  {
725  // TODO: use block_managers not bvectors to avoid extra indirect
726  combine_and(i, j, bv_target, bv_src, src_size);
727  } // for j
728  } // for i
729 }
730 
731 // ------------------------------------------------------------------------
732 
733 template<typename BV>
735  const bvector_type_const_ptr* bv_src_and, unsigned src_and_size,
736  const bvector_type_const_ptr* bv_src_sub, unsigned src_sub_size,
737  bool any)
738 {
739  BM_ASSERT_THROW(src_and_size < max_aggregator_cap, BM_ERR_RANGE);
740  BM_ASSERT_THROW(src_sub_size < max_aggregator_cap, BM_ERR_RANGE);
741 
742  bool global_found = false;
743 
744  if (!bv_src_and || !src_and_size)
745  {
746  bv_target.clear();
747  return false;
748  }
749 
750  blocks_manager_type& bman_target = bv_target.get_blocks_manager();
751 
752  unsigned top_blocks = resize_target(bv_target, bv_src_and, src_and_size);
753  unsigned top_blocks2 = resize_target(bv_target, bv_src_sub, src_sub_size, false);
754 
755  if (top_blocks2 > top_blocks)
756  top_blocks = top_blocks2;
757 
758  for (unsigned i = 0; i < top_blocks; ++i)
759  {
760  unsigned set_array_max = find_effective_sub_block_size(i, bv_src_and, src_and_size, true);
761  if (!set_array_max)
762  continue;
763  if (src_sub_size)
764  {
765  unsigned set_array_max2 =
766  find_effective_sub_block_size(i, bv_src_sub, src_sub_size, false);
767  if (set_array_max2 > set_array_max) // TODO: use range intersect
768  set_array_max = set_array_max2;
769  }
770  for (unsigned j = 0; j < set_array_max; ++j)
771  {
772  int is_res_full;
773  digest_type digest = combine_and_sub(i, j,
774  bv_src_and, src_and_size,
775  bv_src_sub, src_sub_size,
776  &is_res_full);
777  if (is_res_full)
778  {
779  bman_target.check_alloc_top_subblock(i);
780  bman_target.set_block_ptr(i, j, (bm::word_t*)FULL_BLOCK_FAKE_ADDR);
781  if (j == bm::set_sub_array_size-1)
782  {
783  bman_target.validate_top_full(i);
784  }
785  if (any)
786  return any;
787  }
788  else
789  {
790  bool found = digest;
791  if (found)
792  {
793  bman_target.opt_copy_bit_block(i, j, ar_->tb1,
794  opt_mode_, ar_->tb_opt);
795  if (any)
796  return found;
797  }
798  global_found |= found;
799  }
800  } // for j
801  } // for i
802  return global_found;
803 }
804 
805 // ------------------------------------------------------------------------
806 
807 template<typename BV>
809  const bvector_type_const_ptr* bv_src_and, unsigned src_and_size,
810  const bvector_type_const_ptr* bv_src_sub, unsigned src_sub_size)
811 {
812  BM_ASSERT_THROW(src_and_size < max_aggregator_cap, BM_ERR_RANGE);
813  BM_ASSERT_THROW(src_sub_size < max_aggregator_cap, BM_ERR_RANGE);
814 
815  if (!bv_src_and || !src_and_size)
816  return false;
817 
818  unsigned top_blocks = max_top_blocks(bv_src_and, src_and_size);
819  unsigned top_blocks2 = max_top_blocks(bv_src_sub, src_sub_size);
820 
821  if (top_blocks2 > top_blocks)
822  top_blocks = top_blocks2;
823 
824  // compute range blocks coordinates
825  //
826  block_idx_type nblock_from = (range_from_ >> bm::set_block_shift);
827  block_idx_type nblock_to = (range_to_ >> bm::set_block_shift);
828  unsigned top_from = unsigned(nblock_from >> bm::set_array_shift);
829  unsigned top_to = unsigned(nblock_to >> bm::set_array_shift);
830 
831  if (range_set_)
832  {
833  if (nblock_from == nblock_to) // one block search
834  {
835  int is_res_full;
836  unsigned i = top_from;
837  unsigned j = unsigned(nblock_from & bm::set_array_mask);
838  digest_type digest = combine_and_sub(i, j,
839  bv_src_and, src_and_size,
840  bv_src_sub, src_sub_size,
841  &is_res_full);
842  // is_res_full is not needed here, since it is just 1 block
843  if (digest)
844  {
845  unsigned block_bit_idx = 0;
846  bool found = bm::bit_find_first(ar_->tb1, &block_bit_idx, digest);
847  BM_ASSERT(found);
848  idx = bm::block_to_global_index(i, j, block_bit_idx);
849  return found;
850  }
851  return false;
852  }
853 
854  if (top_to < top_blocks)
855  top_blocks = top_to+1;
856  }
857  else
858  {
859  top_from = 0;
860  }
861 
862  for (unsigned i = top_from; i < top_blocks; ++i)
863  {
864  unsigned set_array_max = bm::set_sub_array_size;
865  unsigned j = 0;
866  if (range_set_)
867  {
868  if (i == top_from)
869  {
870  j = nblock_from & bm::set_array_mask;
871  }
872  if (i == top_to)
873  {
874  set_array_max = 1 + unsigned(nblock_to & bm::set_array_mask);
875  }
876  }
877  else
878  {
879  set_array_max = find_effective_sub_block_size(i, bv_src_and, src_and_size, true);
880  if (!set_array_max)
881  continue;
882  if (src_sub_size)
883  {
884  unsigned set_array_max2 =
885  find_effective_sub_block_size(i, bv_src_sub, src_sub_size, false);
886  if (set_array_max2 > set_array_max)
887  set_array_max = set_array_max2;
888  }
889  }
890  for (; j < set_array_max; ++j)
891  {
892  int is_res_full;
893  digest_type digest = combine_and_sub(i, j,
894  bv_src_and, src_and_size,
895  bv_src_sub, src_sub_size,
896  &is_res_full);
897  if (digest)
898  {
899  unsigned block_bit_idx = 0;
900  bool found = bm::bit_find_first(ar_->tb1, &block_bit_idx, digest);
901  BM_ASSERT(found);
902  idx = bm::block_to_global_index(i, j, block_bit_idx);
903  return found;
904  }
905  } // for j
906  //while (++j < set_array_max);
907  } // for i
908  return false;
909 }
910 
911 // ------------------------------------------------------------------------
912 
913 template<typename BV>
914 unsigned
916  unsigned i,
917  const bvector_type_const_ptr* bv_src,
918  unsigned src_size,
919  bool top_null_as_zero) BMNOEXCEPT
920 {
921  // quick hack to avoid scanning large, arrays, where such scan can be quite
922  // expensive by itself (this makes this function approximate)
923  if (src_size > 32)
924  return bm::set_sub_array_size;
925 
926  unsigned max_size = 1;
927  for (unsigned k = 0; k < src_size; ++k)
928  {
929  const bvector_type* bv = bv_src[k];
930  BM_ASSERT(bv);
931  const typename bvector_type::blocks_manager_type& bman_arg =
932  bv->get_blocks_manager();
933  const bm::word_t* const* blk_blk_arg = bman_arg.get_topblock(i);
934  if (!blk_blk_arg)
935  {
936  if (top_null_as_zero)
937  return 0;
938  continue;
939  }
940  if ((bm::word_t*)blk_blk_arg == FULL_BLOCK_FAKE_ADDR)
941  return bm::set_sub_array_size;
942 
943  for (unsigned j = bm::set_sub_array_size - 1; j > max_size; --j)
944  {
945  if (blk_blk_arg[j])
946  {
947  max_size = j;
948  break;
949  }
950  } // for j
951  if (max_size == bm::set_sub_array_size - 1)
952  break;
953  } // for k
954  ++max_size;
956 
957  return max_size;
958 }
959 
960 // ------------------------------------------------------------------------
961 
962 template<typename BV>
963 void aggregator<BV>::combine_or(unsigned i, unsigned j,
964  bvector_type& bv_target,
965  const bvector_type_const_ptr* bv_src,
966  unsigned src_size)
967 {
968  typename bvector_type::blocks_manager_type& bman_target = bv_target.get_blocks_manager();
969 
970  unsigned arg_blk_count = 0;
971  unsigned arg_blk_gap_count = 0;
972  bm::word_t* blk =
973  sort_input_blocks_or(bv_src, src_size, i, j,
974  &arg_blk_count, &arg_blk_gap_count);
975 
976  BM_ASSERT(blk == 0 || blk == FULL_BLOCK_FAKE_ADDR);
977 
978  if (blk == FULL_BLOCK_FAKE_ADDR) // nothing to do - golden block(!)
979  {
980  bman_target.check_alloc_top_subblock(i);
981  bman_target.set_block_ptr(i, j, blk);
982  if (++j == bm::set_sub_array_size)
983  {
984  bman_target.validate_top_full(i);
985  }
986  }
987  else
988  {
989  blk = ar_->tb1;
990  if (arg_blk_count || arg_blk_gap_count)
991  {
992  bool all_one =
993  process_bit_blocks_or(bman_target, i, j, arg_blk_count);
994  if (!all_one)
995  {
996  if (arg_blk_gap_count)
997  {
998  process_gap_blocks_or(arg_blk_gap_count);
999  }
1000  // we have some results, allocate block and copy from temp
1001  bman_target.opt_copy_bit_block(i, j, ar_->tb1,
1002  opt_mode_, ar_->tb_opt);
1003  }
1004  }
1005  }
1006 }
1007 
1008 // ------------------------------------------------------------------------
1009 
1010 template<typename BV>
1011 void aggregator<BV>::combine_and(unsigned i, unsigned j,
1012  bvector_type& bv_target,
1013  const bvector_type_const_ptr* bv_src,
1014  unsigned src_size)
1015 {
1016  BM_ASSERT(src_size);
1017 
1018  unsigned arg_blk_count = 0;
1019  unsigned arg_blk_gap_count = 0;
1020  bm::word_t* blk =
1021  sort_input_blocks_and(bv_src, src_size,
1022  i, j,
1023  &arg_blk_count, &arg_blk_gap_count);
1024 
1025  BM_ASSERT(blk == 0 || blk == FULL_BLOCK_FAKE_ADDR);
1026 
1027  if (!blk) // nothing to do - golden block(!)
1028  return;
1029  if (arg_blk_count || arg_blk_gap_count)
1030  {
1031  if (!arg_blk_gap_count && (arg_blk_count == 1))
1032  {
1033  if (ar_->v_arg_and_blk[0] == FULL_BLOCK_REAL_ADDR)
1034  {
1035  // another nothing to do: one FULL block
1036  blocks_manager_type& bman_target = bv_target.get_blocks_manager();
1037  bman_target.check_alloc_top_subblock(i);
1038  bman_target.set_block_ptr(i, j, blk);
1039  if (++j == bm::set_sub_array_size)
1040  bman_target.validate_top_full(i);
1041  return;
1042  }
1043  }
1044  // AND bit-blocks
1045  //
1046  bm::id64_t digest = ~0ull;
1047  digest = process_bit_blocks_and(arg_blk_count, digest);
1048  if (!digest)
1049  return;
1050 
1051  // AND all GAP blocks (if any)
1052  //
1053  if (arg_blk_gap_count)
1054  {
1055  digest = process_gap_blocks_and(arg_blk_gap_count, digest);
1056  }
1057  if (digest) // we have results , allocate block and copy from temp
1058  {
1059  blocks_manager_type& bman_target = bv_target.get_blocks_manager();
1060  bman_target.opt_copy_bit_block(i, j, ar_->tb1,
1061  opt_mode_, ar_->tb_opt);
1062  }
1063  }
1064 }
1065 
1066 // ------------------------------------------------------------------------
1067 
1068 template<typename BV>
1070 aggregator<BV>::combine_and_sub(unsigned i, unsigned j,
1071  const bvector_type_const_ptr* bv_src_and, unsigned src_and_size,
1072  const bvector_type_const_ptr* bv_src_sub, unsigned src_sub_size,
1073  int* is_result_full)
1074 {
1075  BM_ASSERT(src_and_size);
1076  BM_ASSERT(is_result_full);
1077 
1078  unsigned arg_blk_and_count = 0;
1079  unsigned arg_blk_and_gap_count = 0;
1080  unsigned arg_blk_sub_count = 0;
1081  unsigned arg_blk_sub_gap_count = 0;
1082 
1083  *is_result_full = 0;
1084  bm::word_t* blk = sort_input_blocks_and(bv_src_and, src_and_size,
1085  i, j,
1086  &arg_blk_and_count, &arg_blk_and_gap_count);
1087  BM_ASSERT(blk == 0 || blk == FULL_BLOCK_FAKE_ADDR);
1088  if (!blk || !(arg_blk_and_count | arg_blk_and_gap_count))
1089  return 0; // nothing to do - golden block(!)
1090 
1091  if (src_sub_size)
1092  {
1093  blk = sort_input_blocks_or(bv_src_sub, src_sub_size,
1094  i, j,
1095  &arg_blk_sub_count, &arg_blk_sub_gap_count);
1096  BM_ASSERT(blk == 0 || blk == FULL_BLOCK_FAKE_ADDR);
1097  if (blk == FULL_BLOCK_FAKE_ADDR)
1098  return 0; // nothing to do - golden block(!)
1099  }
1100  else
1101  {
1102  if (!arg_blk_and_gap_count && (arg_blk_and_count == 1))
1103  {
1104  if (ar_->v_arg_and_blk[0] == FULL_BLOCK_REAL_ADDR)
1105  {
1106  *is_result_full = 1;
1107  return ~0ull;
1108  }
1109  }
1110  }
1111 
1112  digest_type digest = ~0ull;
1113 
1114  // AND-SUB bit-blocks
1115  //
1116  digest = process_bit_blocks_and(arg_blk_and_count, digest);
1117  if (!digest)
1118  return digest;
1119  digest = process_bit_blocks_sub(arg_blk_sub_count, digest);
1120  if (!digest)
1121  return digest;
1122 
1123  // AND all GAP block
1124  //
1125  digest =
1126  process_gap_blocks_and(arg_blk_and_gap_count, digest);
1127  if (!digest)
1128  return digest;
1129 
1130  if (arg_blk_sub_gap_count)
1131  {
1132  digest =
1133  process_gap_blocks_sub(arg_blk_sub_gap_count, digest);
1134  }
1135 
1136  return digest;
1137 }
1138 
1139 // ------------------------------------------------------------------------
1140 
1141 template<typename BV>
1142 void aggregator<BV>::process_gap_blocks_or(unsigned arg_blk_gap_count)
1143 {
1144  bm::word_t* blk = ar_->tb1;
1145  for (unsigned k = 0; k < arg_blk_gap_count; ++k)
1146  bm::gap_add_to_bitset(blk, ar_->v_arg_or_blk_gap[k]);
1147 }
1148 
1149 // ------------------------------------------------------------------------
1150 
1151 template<typename BV>
1153 aggregator<BV>::process_gap_blocks_and(unsigned arg_blk_gap_count,
1154  digest_type digest)
1155 {
1156  bm::word_t* blk = ar_->tb1;
1157  bool single_bit_found;
1158  unsigned single_bit_idx;
1159  for (unsigned k = 0; k < arg_blk_gap_count; ++k)
1160  {
1161  bm::gap_and_to_bitset(blk, ar_->v_arg_and_blk_gap[k], digest);
1162  digest = bm::update_block_digest0(blk, digest);
1163  if (!digest)
1164  {
1166  break;
1167  }
1168  single_bit_found = bm::bit_find_first_if_1(blk, &single_bit_idx, digest);
1169  if (single_bit_found)
1170  {
1171  for (++k; k < arg_blk_gap_count; ++k)
1172  {
1173  bool b = bm::gap_test_unr(ar_->v_arg_and_blk_gap[k], single_bit_idx);
1174  if (!b)
1175  return 0; // AND 0 causes result to turn 0
1176  } // for k
1177  break;
1178  }
1179  }
1180  return digest;
1181 }
1182 
1183 // ------------------------------------------------------------------------
1184 
1185 template<typename BV>
1187 aggregator<BV>::process_gap_blocks_sub(unsigned arg_blk_gap_count,
1188  digest_type digest)
1189 {
1190  bm::word_t* blk = ar_->tb1;
1191  bool single_bit_found;
1192  unsigned single_bit_idx;
1193  for (unsigned k = 0; k < arg_blk_gap_count; ++k)
1194  {
1195  bm::gap_sub_to_bitset(blk, ar_->v_arg_or_blk_gap[k], digest);
1196  digest = bm::update_block_digest0(blk, digest);
1197  if (!digest)
1198  {
1200  break;
1201  }
1202  // check if logical operation reduced to a corner case of one single bit
1203  single_bit_found = bm::bit_find_first_if_1(blk, &single_bit_idx, digest);
1204  if (single_bit_found)
1205  {
1206  for (++k; k < arg_blk_gap_count; ++k)
1207  {
1208  bool b = bm::gap_test_unr(ar_->v_arg_or_blk_gap[k], single_bit_idx);
1209  if (b)
1210  return 0; // AND-NOT causes search result to turn 0
1211  } // for k
1212  break;
1213  }
1214  } // for k
1215  return digest;
1216 }
1217 
1218 // ------------------------------------------------------------------------
1219 
1220 template<typename BV>
1221 bool aggregator<BV>::test_gap_blocks_and(unsigned arg_blk_gap_count,
1222  unsigned bit_idx)
1223 {
1224  unsigned b = 1;
1225  for (unsigned i = 0; i < arg_blk_gap_count && b; ++i)
1226  {
1227  b = bm::gap_test_unr(ar_->v_arg_and_blk_gap[i], bit_idx);
1228  }
1229  return b;
1230 }
1231 
1232 // ------------------------------------------------------------------------
1233 
1234 template<typename BV>
1235 bool aggregator<BV>::test_gap_blocks_sub(unsigned arg_blk_gap_count,
1236  unsigned bit_idx)
1237 {
1238  unsigned b = 1;
1239  for (unsigned i = 0; i < arg_blk_gap_count; ++i)
1240  {
1241  b = bm::gap_test_unr(ar_->v_arg_or_blk_gap[i], bit_idx);
1242  if (b)
1243  return false;
1244  }
1245  return true;
1246 }
1247 
1248 // ------------------------------------------------------------------------
1249 
1250 
1251 template<typename BV>
1253  unsigned i, unsigned j,
1254  unsigned arg_blk_count)
1255 {
1256  bm::word_t* blk = ar_->tb1;
1257  bool all_one;
1258 
1259  unsigned k = 0;
1260 
1261  if (arg_blk_count) // copy the first block
1262  bm::bit_block_copy(blk, ar_->v_arg_or_blk[k++]);
1263  else
1264  bm::bit_block_set(blk, 0);
1265 
1266  // process all BIT blocks
1267  //
1268  unsigned unroll_factor, len, len_unr;
1269 
1270  unroll_factor = 4;
1271  len = arg_blk_count - k;
1272  len_unr = len - (len % unroll_factor);
1273  for( ;k < len_unr; k+=unroll_factor)
1274  {
1275  all_one = bm::bit_block_or_5way(blk,
1276  ar_->v_arg_or_blk[k], ar_->v_arg_or_blk[k+1],
1277  ar_->v_arg_or_blk[k+2], ar_->v_arg_or_blk[k+3]);
1278  if (all_one)
1279  {
1280  BM_ASSERT(blk == ar_->tb1);
1282  bman_target.set_block(i, j, FULL_BLOCK_FAKE_ADDR, false);
1283  return true;
1284  }
1285  } // for k
1286 
1287  unroll_factor = 2;
1288  len = arg_blk_count - k;
1289  len_unr = len - (len % unroll_factor);
1290  for( ;k < len_unr; k+=unroll_factor)
1291  {
1292  all_one = bm::bit_block_or_3way(blk, ar_->v_arg_or_blk[k], ar_->v_arg_or_blk[k+1]);
1293  if (all_one)
1294  {
1295  BM_ASSERT(blk == ar_->tb1);
1297  bman_target.set_block(i, j, FULL_BLOCK_FAKE_ADDR, false);
1298  return true;
1299  }
1300  } // for k
1301 
1302  for (; k < arg_blk_count; ++k)
1303  {
1304  all_one = bm::bit_block_or(blk, ar_->v_arg_or_blk[k]);
1305  if (all_one)
1306  {
1307  BM_ASSERT(blk == ar_->tb1);
1309  bman_target.set_block(i, j, FULL_BLOCK_FAKE_ADDR, false);
1310  return true;
1311  }
1312  } // for k
1313 
1314  return false;
1315 }
1316 
1317 // ------------------------------------------------------------------------
1318 
1319 template<typename BV>
1322  digest_type digest)
1323 {
1324  bm::word_t* blk = ar_->tb1;
1325  unsigned k = 0;
1326 
1327  block_idx_type nb_from = (range_from_ >> bm::set_block_shift);
1328  block_idx_type nb_to = (range_to_ >> bm::set_block_shift);
1329  if (range_set_ && (nb_from == nb_to))
1330  {
1331  unsigned nbit_from = unsigned(range_from_ & bm::set_block_mask);
1332  unsigned nbit_to = unsigned(range_to_ & bm::set_block_mask);
1333  digest_type digest0 = bm::digest_mask(nbit_from, nbit_to);
1334  digest &= digest0;
1335  bm::block_init_digest0(blk, digest);
1336  }
1337  else
1338  {
1339  switch (arg_blk_count)
1340  {
1341  case 0:
1342  bm::block_init_digest0(blk, digest); // 0xFF... by default
1343  return digest;
1344  case 1:
1345  bm::bit_block_copy(blk, ar_->v_arg_and_blk[k]);
1346  return bm::calc_block_digest0(blk);
1347  default:
1348  digest = bm::bit_block_and_2way(blk,
1349  ar_->v_arg_and_blk[k],
1350  ar_->v_arg_and_blk[k+1],
1351  ~0ull);
1352  k += 2;
1353  break;
1354  } // switch
1355  }
1356 
1357  unsigned unroll_factor, len, len_unr;
1358  unsigned single_bit_idx;
1359 
1360  unroll_factor = 4;
1361  len = arg_blk_count - k;
1362  len_unr = len - (len % unroll_factor);
1363  for (; k < len_unr; k += unroll_factor)
1364  {
1365  digest =
1367  ar_->v_arg_and_blk[k], ar_->v_arg_and_blk[k + 1],
1368  ar_->v_arg_and_blk[k + 2], ar_->v_arg_and_blk[k + 3],
1369  digest);
1370  if (!digest) // all zero
1371  return digest;
1372  bool found = bm::bit_find_first_if_1(blk, &single_bit_idx, digest);
1373  if (found)
1374  {
1375  unsigned nword = unsigned(single_bit_idx >> bm::set_word_shift);
1376  unsigned mask = 1u << (single_bit_idx & bm::set_word_mask);
1377  for (++k; k < arg_blk_count; ++k)
1378  {
1379  const bm::word_t* arg_blk = ar_->v_arg_and_blk[k];
1380  if (!(mask & arg_blk[nword]))
1381  {
1382  blk[nword] = 0;
1383  return 0;
1384  }
1385  } // for k
1386  break;
1387  }
1388  } // for k
1389 
1390  for (; k < arg_blk_count; ++k)
1391  {
1392  if (ar_->v_arg_and_blk[k] == FULL_BLOCK_REAL_ADDR)
1393  continue;
1394  digest = bm::bit_block_and(blk, ar_->v_arg_and_blk[k], digest);
1395  if (!digest) // all zero
1396  return digest;
1397  } // for k
1398  return digest;
1399 }
1400 
1401 // ------------------------------------------------------------------------
1402 
1403 template<typename BV>
1406  digest_type digest)
1407 {
1408  bm::word_t* blk = ar_->tb1;
1409  unsigned single_bit_idx;
1410  const word_t** args = &ar_->v_arg_or_blk[0];
1411  for (unsigned k = 0; k < arg_blk_count; ++k)
1412  {
1413  if (ar_->v_arg_or_blk[k] == FULL_BLOCK_REAL_ADDR) // golden block
1414  {
1415  digest = 0;
1416  break;
1417  }
1418  digest = bm::bit_block_sub(blk, args[k], digest);
1419  if (!digest) // all zero
1420  break;
1421 
1422  bool found = bm::bit_find_first_if_1(blk, &single_bit_idx, digest);
1423  if (found)
1424  {
1425  const unsigned mask = 1u << (single_bit_idx & bm::set_word_mask);
1426  unsigned nword = unsigned(single_bit_idx >> bm::set_word_shift);
1427  for (++k; k < arg_blk_count; ++k)
1428  {
1429  if (mask & args[k][nword])
1430  {
1431  blk[nword] = 0;
1432  return 0;
1433  }
1434  } // for k
1435  break;
1436  }
1437  } // for k
1438  return digest;
1439 }
1440 
1441 // ------------------------------------------------------------------------
1442 
1443 template<typename BV>
1445  const bvector_type_const_ptr* bv_src, unsigned src_size,
1446  bool init_clear)
1447 {
1448  typename bvector_type::blocks_manager_type& bman_target = bv_target.get_blocks_manager();
1449  if (init_clear)
1450  {
1451  if (bman_target.is_init())
1452  bman_target.deinit_tree();
1453  }
1454 
1455  unsigned top_blocks = bman_target.top_block_size();
1456  size_type size = bv_target.size();
1457  bool need_realloc = false;
1458 
1459  // pre-scan to do target size harmonization
1460  for (unsigned i = 0; i < src_size; ++i)
1461  {
1462  const bvector_type* bv = bv_src[i];
1463  BM_ASSERT(bv);
1464  const typename bvector_type::blocks_manager_type& bman_arg =
1465  bv->get_blocks_manager();
1466  unsigned arg_top_blocks = bman_arg.top_block_size();
1467  if (arg_top_blocks > top_blocks)
1468  {
1469  need_realloc = true;
1470  top_blocks = arg_top_blocks;
1471  }
1472  size_type arg_size = bv->size();
1473  if (arg_size > size)
1474  size = arg_size;
1475  } // for i
1476 
1477  if (need_realloc)
1478  {
1479  bman_target.reserve_top_blocks(top_blocks);
1480  }
1481  if (!bman_target.is_init())
1482  bman_target.init_tree();
1483  if (size > bv_target.size())
1484  bv_target.resize(size);
1485 
1486  return top_blocks;
1487 }
1488 
1489 // ------------------------------------------------------------------------
1490 
1491 template<typename BV>
1492 unsigned
1493 aggregator<BV>::max_top_blocks(const bvector_type_const_ptr* bv_src,
1494  unsigned src_size) BMNOEXCEPT
1495 {
1496  unsigned top_blocks = 1;
1497 
1498  // pre-scan to do target size harmonization
1499  for (unsigned i = 0; i < src_size; ++i)
1500  {
1501  const bvector_type* bv = bv_src[i];
1502  BM_ASSERT(bv);
1503  const typename bvector_type::blocks_manager_type& bman_arg = bv->get_blocks_manager();
1504  unsigned arg_top_blocks = bman_arg.top_block_size();
1505  if (arg_top_blocks > top_blocks)
1506  top_blocks = arg_top_blocks;
1507  } // for i
1508  return top_blocks;
1509 }
1510 
1511 // ------------------------------------------------------------------------
1512 
1513 template<typename BV>
1515  const bvector_type_const_ptr* bv_src,
1516  unsigned src_size,
1517  unsigned i, unsigned j,
1518  unsigned* arg_blk_count,
1519  unsigned* arg_blk_gap_count) BMNOEXCEPT
1520 {
1521  bm::word_t* blk = 0;
1522  for (unsigned k = 0; k < src_size; ++k)
1523  {
1524  const bvector_type* bv = bv_src[k];
1525  BM_ASSERT(bv);
1526  const blocks_manager_type& bman_arg = bv->get_blocks_manager();
1527  const bm::word_t* arg_blk = bman_arg.get_block_ptr(i, j);
1528  if (!arg_blk)
1529  continue;
1530  if (BM_IS_GAP(arg_blk))
1531  {
1532  ar_->v_arg_or_blk_gap[*arg_blk_gap_count] = BMGAP_PTR(arg_blk);
1533  (*arg_blk_gap_count)++;
1534  }
1535  else // FULL or bit block
1536  {
1537  if (IS_FULL_BLOCK(arg_blk))
1538  {
1539  blk = FULL_BLOCK_FAKE_ADDR;
1540  *arg_blk_gap_count = *arg_blk_count = 0; // nothing to do
1541  break;
1542  }
1543  ar_->v_arg_or_blk[*arg_blk_count] = arg_blk;
1544  (*arg_blk_count)++;
1545  }
1546  } // for k
1547  return blk;
1548 }
1549 
1550 // ------------------------------------------------------------------------
1551 
1552 template<typename BV>
1554  const bvector_type_const_ptr* bv_src,
1555  unsigned src_size,
1556  unsigned i, unsigned j,
1557  unsigned* arg_blk_count,
1558  unsigned* arg_blk_gap_count) BMNOEXCEPT
1559 {
1560  unsigned full_blk_cnt = 0;
1562  for (unsigned k = 0; k < src_size; ++k)
1563  {
1564  const bvector_type* bv = bv_src[k];
1565  BM_ASSERT(bv);
1566  const blocks_manager_type& bman_arg = bv->get_blocks_manager();
1567  const bm::word_t* arg_blk = bman_arg.get_block_ptr(i, j);
1568  if (!arg_blk)
1569  {
1570  blk = 0;
1571  *arg_blk_gap_count = *arg_blk_count = 0; // nothing to do
1572  break;
1573  }
1574  if (BM_IS_GAP(arg_blk))
1575  {
1576  ar_->v_arg_and_blk_gap[*arg_blk_gap_count] = BMGAP_PTR(arg_blk);
1577  (*arg_blk_gap_count)++;
1578  }
1579  else // FULL or bit block
1580  {
1581  if (IS_FULL_BLOCK(arg_blk))
1582  {
1583  // add only first FULL encounter, others ignore
1584  if (!full_blk_cnt) // first 0xFFF....
1585  {
1586  ar_->v_arg_and_blk[*arg_blk_count] = FULL_BLOCK_REAL_ADDR;
1587  ++full_blk_cnt;
1588  (*arg_blk_count)++;
1589  }
1590  }
1591  else
1592  {
1593  ar_->v_arg_and_blk[*arg_blk_count] = arg_blk;
1594  (*arg_blk_count)++;
1595  }
1596  /*
1597  ar_->v_arg_and_blk[*arg_blk_count] =
1598  IS_FULL_BLOCK(arg_blk) ? FULL_BLOCK_REAL_ADDR: arg_blk;
1599  (*arg_blk_count)++; */
1600  }
1601  } // for k
1602  return blk;
1603 }
1604 
1605 // ------------------------------------------------------------------------
1606 
1607 template<typename BV>
1609  const bvector_type_const_ptr* bv_src, unsigned src_size)
1610 {
1611  BM_ASSERT(src_size);
1612  if (src_size == 0)
1613  {
1614  bv_target.clear();
1615  return;
1616  }
1617 
1618  const bvector_type* bv = bv_src[0];
1619  bv_target = *bv;
1620 
1621  for (unsigned i = 1; i < src_size; ++i)
1622  {
1623  bv = bv_src[i];
1624  BM_ASSERT(bv);
1625  bv_target.bit_or(*bv);
1626  }
1627 }
1628 
1629 // ------------------------------------------------------------------------
1630 
1631 template<typename BV>
1633  const bvector_type_const_ptr* bv_src, unsigned src_size)
1634 {
1635  BM_ASSERT(src_size);
1636 
1637  if (src_size == 0)
1638  {
1639  bv_target.clear();
1640  return;
1641  }
1642  const bvector_type* bv = bv_src[0];
1643  bv_target = *bv;
1644 
1645  for (unsigned i = 1; i < src_size; ++i)
1646  {
1647  bv = bv_src[i];
1648  BM_ASSERT(bv);
1649  bv_target.bit_and(*bv);
1650  }
1651 }
1652 
1653 // ------------------------------------------------------------------------
1654 
1655 template<typename BV>
1657  const bvector_type_const_ptr* bv_src_and,
1658  unsigned src_and_size,
1659  const bvector_type_const_ptr* bv_src_sub,
1660  unsigned src_sub_size)
1661 {
1662  BM_ASSERT(src_and_size);
1663 
1664  combine_and_horizontal(bv_target, bv_src_and, src_and_size);
1665 
1666  for (unsigned i = 0; i < src_sub_size; ++i)
1667  {
1668  const bvector_type* bv = bv_src_sub[i];
1669  BM_ASSERT(bv);
1670  bv_target -= *bv;
1671  }
1672 }
1673 
1674 // ------------------------------------------------------------------------
1675 
1676 template<typename BV>
1678  const bvector_type_const_ptr* bv_src,
1679  unsigned src_size)
1680 {
1681  top_block_size_ = resize_target(bv_target, bv_src, src_size);
1682 
1683  // set initial carry overs all to 0
1684  for (unsigned i = 0; i < src_size; ++i) // reset co flags
1685  ar_->carry_overs_[i] = 0;
1686 }
1687 
1688 // ------------------------------------------------------------------------
1689 
1690 template<typename BV>
1692  bvector_type& bv_target,
1693  const bvector_type_const_ptr* bv_src_and, unsigned src_and_size,
1694  bool any)
1695 {
1696  BM_ASSERT_THROW(src_size < max_aggregator_cap, BM_ERR_RANGE);
1697  if (!src_and_size)
1698  {
1699  bv_target.clear();
1700  return false;
1701  }
1702  prepare_shift_right_and(bv_target, bv_src_and, src_and_size);
1703 
1704  for (unsigned i = 0; i < bm::set_top_array_size; ++i)
1705  {
1706  if (i > top_block_size_)
1707  {
1708  if (!any_carry_overs(&ar_->carry_overs_[0], src_and_size))
1709  break; // quit early if there is nothing to carry on
1710  }
1711 
1712  unsigned j = 0;
1713  do
1714  {
1715  bool found =
1716  combine_shift_right_and(i, j, bv_target, bv_src_and, src_and_size);
1717  if (found && any)
1718  return found;
1719  } while (++j < bm::set_sub_array_size);
1720 
1721  } // for i
1722 
1723  if (compute_count_)
1724  return bool(count_);
1725 
1726  return bv_target.any();
1727 }
1728 
1729 // ------------------------------------------------------------------------
1730 
1731 template<typename BV>
1732 bool aggregator<BV>::combine_shift_right_and(unsigned i, unsigned j,
1733  bvector_type& bv_target,
1734  const bvector_type_const_ptr* bv_src,
1735  unsigned src_size)
1736 {
1737  bm::word_t* blk = temp_blk_ ? temp_blk_ : ar_->tb1;
1738  unsigned char* carry_overs = &(ar_->carry_overs_[0]);
1739 
1740  bm::id64_t digest = ~0ull; // start with a full content digest
1741 
1742  bool blk_zero = false;
1743  // first initial block is just copied over from the first AND
1744  {
1745  const blocks_manager_type& bman_arg = bv_src[0]->get_blocks_manager();
1746  BM_ASSERT(bman_arg.is_init());
1747  const bm::word_t* arg_blk = bman_arg.get_block(i, j);
1748  if (BM_IS_GAP(arg_blk))
1749  {
1750  bm::bit_block_set(blk, 0);
1751  bm::gap_add_to_bitset(blk, BMGAP_PTR(arg_blk));
1752  }
1753  else
1754  {
1755  if (arg_blk)
1756  {
1757  bm::bit_block_copy(blk, arg_blk);
1758  }
1759  else
1760  {
1761  blk_zero = true; // set flag for delayed block init
1762  digest = 0;
1763  }
1764  }
1765  carry_overs[0] = 0;
1766  }
1767 
1768  for (unsigned k = 1; k < src_size; ++k)
1769  {
1770  unsigned carry_over = carry_overs[k];
1771  if (!digest && !carry_over) // 0 into "00000" block >> 0
1772  continue;
1773  if (blk_zero) // delayed temp block 0-init requested
1774  {
1775  bm::bit_block_set(blk, 0);
1776  blk_zero = !blk_zero; // = false
1777  }
1778  const bm::word_t* arg_blk = get_arg_block(bv_src, k, i, j);
1779  carry_overs[k] = (unsigned char)
1780  process_shift_right_and(blk, arg_blk, digest, carry_over);
1781  BM_ASSERT(carry_overs[k] == 0 || carry_overs[k] == 1);
1782  } // for k
1783 
1784  if (blk_zero) // delayed temp block 0-init
1785  {
1786  bm::bit_block_set(blk, 0);
1787  }
1788  // block now gets emitted into the target bit-vector
1789  if (digest)
1790  {
1792 
1793  if (compute_count_)
1794  {
1795  unsigned cnt = bm::bit_block_count(blk, digest);
1796  count_ += cnt;
1797  }
1798  else
1799  {
1800  blocks_manager_type& bman_target = bv_target.get_blocks_manager();
1801  bman_target.opt_copy_bit_block(i, j, blk, opt_mode_, ar_->tb_opt);
1802  }
1803  return true;
1804  }
1805  return false;
1806 }
1807 
1808 // ------------------------------------------------------------------------
1809 
1810 template<typename BV>
1812  bm::word_t* BMRESTRICT blk,
1813  const bm::word_t* BMRESTRICT arg_blk,
1814  digest_type& BMRESTRICT digest,
1815  unsigned carry_over) BMNOEXCEPT
1816 {
1817  BM_ASSERT(carry_over == 1 || carry_over == 0);
1818 
1819  if (BM_IS_GAP(arg_blk)) // GAP argument
1820  {
1821  if (digest)
1822  {
1823  carry_over =
1824  bm::bit_block_shift_r1_and_unr(blk, carry_over,
1825  FULL_BLOCK_REAL_ADDR, &digest);
1826  }
1827  else // digest == 0, but carry_over can change that
1828  {
1829  blk[0] = carry_over;
1830  carry_over = 0;
1831  digest = blk[0]; // NOTE: this does NOT account for AND (yet)
1832  }
1833  BM_ASSERT(bm::calc_block_digest0(blk) == digest);
1834 
1835  bm::gap_and_to_bitset(blk, BMGAP_PTR(arg_blk), digest);
1836  digest = bm::update_block_digest0(blk, digest);
1837  }
1838  else // 2 bit-blocks
1839  {
1840  if (arg_blk) // use fast fused SHIFT-AND operation
1841  {
1842  if (digest)
1843  {
1844  carry_over =
1845  bm::bit_block_shift_r1_and_unr(blk, carry_over, arg_blk,
1846  &digest);
1847  }
1848  else // digest == 0
1849  {
1850  blk[0] = carry_over & arg_blk[0];
1851  carry_over = 0;
1852  digest = blk[0];
1853  }
1854  BM_ASSERT(bm::calc_block_digest0(blk) == digest);
1855  }
1856  else // arg is zero - target block => zero
1857  {
1858  carry_over = blk[bm::set_block_size-1] >> 31; // carry out
1859  if (digest)
1860  {
1861  bm::bit_block_set(blk, 0); // TODO: digest based set
1862  digest = 0;
1863  }
1864  }
1865  }
1866  return carry_over;
1867 }
1868 
1869 // ------------------------------------------------------------------------
1870 
1871 template<typename BV>
1873  const bvector_type_const_ptr* bv_src,
1874  unsigned k, unsigned i, unsigned j) BMNOEXCEPT
1875 {
1876  return bv_src[k]->get_blocks_manager().get_block(i, j);
1877 }
1878 
1879 // ------------------------------------------------------------------------
1880 
1881 template<typename BV>
1882 bool aggregator<BV>::any_carry_overs(const unsigned char* carry_overs,
1883  unsigned co_size) BMNOEXCEPT
1884 {
1885  // TODO: loop unroll?
1886  unsigned acc = carry_overs[0];
1887  for (unsigned i = 1; i < co_size; ++i)
1888  acc |= carry_overs[i];
1889 // if (ar_->carry_overs_[i])
1890 // return true;
1891 // return false;
1892  return acc;
1893 }
1894 
1895 // ------------------------------------------------------------------------
1896 
1897 template<typename BV>
1899 {
1900  bvector_type* bv_target = check_create_target(); // create target vector
1901  BM_ASSERT(bv_target);
1902 
1903  temp_blk_ = temp_block;
1904 
1905  switch (operation_)
1906  {
1907  case BM_NOT_DEFINED:
1908  break;
1909  case BM_SHIFT_R_AND:
1910  prepare_shift_right_and(*bv_target, ar_->arg_bv0, arg_group0_size);
1911  operation_status_ = op_prepared;
1912  break;
1913  default:
1914  BM_ASSERT(0);
1915  } // switch
1916 }
1917 
1918 // ------------------------------------------------------------------------
1919 
1920 template<typename BV>
1922 aggregator<BV>::run_step(unsigned i, unsigned j)
1923 {
1924  BM_ASSERT(operation_status_ == op_prepared || operation_status_ == op_in_progress);
1926 
1927  switch (operation_)
1928  {
1929  case BM_NOT_DEFINED:
1930  break;
1931 
1932  case BM_SHIFT_R_AND:
1933  {
1934  if (i > top_block_size_)
1935  {
1936  if (!this->any_carry_overs(&ar_->carry_overs_[0], arg_group0_size))
1937  {
1938  operation_status_ = op_done;
1939  return operation_status_;
1940  }
1941  }
1942  //bool found =
1943  this->combine_shift_right_and(i, j, *bv_target_,
1944  ar_->arg_bv0, arg_group0_size);
1945  operation_status_ = op_in_progress;
1946  }
1947  break;
1948  default:
1949  BM_ASSERT(0);
1950  break;
1951  } // switch
1952 
1953  return operation_status_;
1954 }
1955 
1956 
1957 // ------------------------------------------------------------------------
1958 
1959 
1960 } // bm
1961 
1962 #include "bmundef.h"
1963 
1964 #endif
bm::aggregator::combine_or_horizontal
void combine_or_horizontal(bvector_type &bv_target, const bvector_type_const_ptr *bv_src, unsigned src_size)
Horizontal OR aggregation (potentially slower) method.
Definition: bmaggregator.h:1608
bm::aggregator::check_create_target
bvector_type * check_create_target()
Definition: bmaggregator.h:576
bm::aggregator::process_bit_blocks_sub
digest_type process_bit_blocks_sub(unsigned block_count, digest_type digest)
Definition: bmaggregator.h:1405
bm::aggregator::allocator_pool_type
bvector_type::allocator_type::allocator_pool_type allocator_pool_type
Definition: bmaggregator.h:66
bm::bit_block_sub
bm::id64_t bit_block_sub(bm::word_t *BMRESTRICT dst, const bm::word_t *BMRESTRICT src) BMNOEXCEPT
Plain bitblock SUB (AND NOT) operation. Function does not analyse availability of source and destinat...
Definition: bmfunc.h:6992
bm::bit_is_all_zero
bool bit_is_all_zero(const bm::word_t *BMRESTRICT start) BMNOEXCEPT
Returns "true" if all bits in the block are 0.
Definition: bmfunc.h:1047
bm::bit_block_count
bm::id_t bit_block_count(const bm::word_t *block) BMNOEXCEPT
Bitcount for bit block.
Definition: bmfunc.h:4367
bmfunc.h
Bit manipulation primitives (internal)
bm::aggregator::combine_or
void combine_or(bvector_type &bv_target)
Aggregate added group of vectors using logical OR Operation does NOT perform an explicit reset of arg...
Definition: bmaggregator.h:622
BM_IS_GAP
#define BM_IS_GAP(ptr)
Definition: bmdef.h:181
bm::block_to_global_index
bm::id_t block_to_global_index(unsigned i, unsigned j, unsigned block_idx) BMNOEXCEPT
calculate bvector<> global bit-index from block-local coords
Definition: bmfunc.h:8801
bm::aggregator::prepare_shift_right_and
void prepare_shift_right_and(bvector_type &bv_target, const bvector_type_const_ptr *bv_src, unsigned src_size)
Definition: bmaggregator.h:1677
bm::combine_and
void combine_and(BV &bv, It first, It last)
AND Combine bitvector and the iterable sequence.
Definition: bmalgo_impl.h:1301
bm::set_block_size
const unsigned set_block_size
Definition: bmconst.h:54
bm::bvector::optmode
optmode
Optimization mode Every next level means additional checks (better compression vs time)
Definition: bm.h:129
bm::aggregator::op_done
@ op_done
Definition: bmaggregator.h:87
bm::bit_find_first
bool bit_find_first(const bm::word_t *BMRESTRICT block, unsigned *BMRESTRICT pos) BMNOEXCEPT
BIT block find the first set bit.
Definition: bmfunc.h:7525
bm::aggregator::max_top_blocks
static unsigned max_top_blocks(const bvector_type_const_ptr *bv_src, unsigned src_size) BMNOEXCEPT
Definition: bmaggregator.h:1493
bm::aggregator::bvector_type
BV bvector_type
Definition: bmaggregator.h:61
bm::aggregator::aggregator
aggregator()
Definition: bmaggregator.h:533
BM_DECLARE_TEMP_BLOCK
#define BM_DECLARE_TEMP_BLOCK(x)
Definition: bm.h:47
bm::aligned_new_malloc
void * aligned_new_malloc(size_t size)
Aligned malloc (unlike classic malloc it throws bad_alloc exception)
Definition: bmalloc.h:396
bm::aggregator::sort_input_blocks_or
bm::word_t * sort_input_blocks_or(const bvector_type_const_ptr *bv_src, unsigned src_size, unsigned i, unsigned j, unsigned *arg_blk_count, unsigned *arg_blk_gap_count) BMNOEXCEPT
Definition: bmaggregator.h:1514
bm::is_bits_one
bool is_bits_one(const bm::wordop_t *start) BMNOEXCEPT
Returns "true" if all bits in the block are 1.
Definition: bmfunc.h:5269
bm::aggregator::combine_and
void combine_and(bvector_type &bv_target)
Aggregate added group of vectors using logical AND Operation does NOT perform an explicit reset of ar...
Definition: bmaggregator.h:630
bm::aggregator::any_carry_overs
static bool any_carry_overs(const unsigned char *carry_overs, unsigned co_size) BMNOEXCEPT
Definition: bmaggregator.h:1882
BMGAP_PTR
#define BMGAP_PTR(ptr)
Definition: bmdef.h:179
bm::aggregator::BM_NOT_DEFINED
@ BM_NOT_DEFINED
Definition: bmaggregator.h:78
bm::aggregator::op_prepared
@ op_prepared
Definition: bmaggregator.h:85
bm::id64_t
unsigned long long int id64_t
Definition: bmconst.h:34
bm::aggregator
Algorithms for fast aggregation of a group of bit-vectors.
Definition: bmaggregator.h:58
bm::aggregator::block_idx_type
BV::block_idx_type block_idx_type
Definition: bmaggregator.h:343
bm::gap_sub_to_bitset
void gap_sub_to_bitset(unsigned *BMRESTRICT dest, const T *BMRESTRICT pcurr) BMNOEXCEPT
SUB (AND NOT) GAP block to bitblock.
Definition: bmfunc.h:3308
BM_ASSERT_THROW
#define BM_ASSERT_THROW(x, xerrcode)
Definition: bmdef.h:401
bm::aggregator::process_shift_right_and
static unsigned process_shift_right_and(bm::word_t *BMRESTRICT blk, const bm::word_t *BMRESTRICT arg_blk, digest_type &BMRESTRICT digest, unsigned carry_over) BMNOEXCEPT
Definition: bmaggregator.h:1811
bm::set_word_shift
const unsigned set_word_shift
Definition: bmconst.h:71
bm::aggregator::get_target
const bvector_type * get_target() const
Definition: bmaggregator.h:335
bm::aggregator::blocks_manager_type
bvector_type::blocks_manager_type blocks_manager_type
Definition: bmaggregator.h:342
bm::gap_and_to_bitset
void gap_and_to_bitset(unsigned *BMRESTRICT dest, const T *BMRESTRICT pcurr) BMNOEXCEPT
ANDs GAP block to bitblock.
Definition: bmfunc.h:3474
bm::set_sub_array_size
const unsigned set_sub_array_size
Definition: bmconst.h:94
bm::wordop_t
id64_t wordop_t
Definition: bmconst.h:127
bm::digest_mask
BMFORCEINLINE bm::id64_t digest_mask(unsigned from, unsigned to) BMNOEXCEPT
Compute digest mask for [from..to] positions.
Definition: bmfunc.h:667
bm::aggregator::set_operation
void set_operation(int op_code) BMNOEXCEPT
Set operation code for the aggregator.
Definition: bmaggregator.h:320
bm::aggregator::combine_and_sub
bool combine_and_sub(bvector_type &bv_target)
Aggregate added group of vectors using fused logical AND-SUB Operation does NOT perform an explicit r...
Definition: bmaggregator.h:638
bm::aggregator::bvector_type_const_ptr
const typedef bvector_type * bvector_type_const_ptr
Definition: bmaggregator.h:63
bm::set_top_array_size
const unsigned set_top_array_size
Definition: bmconst.h:109
bm::aggregator::process_bit_blocks_and
digest_type process_bit_blocks_and(unsigned block_count, digest_type digest)
Definition: bmaggregator.h:1321
bm::bit_block_and
bm::id64_t bit_block_and(bm::word_t *BMRESTRICT dst, const bm::word_t *BMRESTRICT src) BMNOEXCEPT
Plain bitblock AND operation. Function does not analyse availability of source and destination blocks...
Definition: bmfunc.h:5913
bm::bvector
Bitvector Bit-vector container with runtime compression of bits.
Definition: bm.h:107
bmundef.h
pre-processor un-defines to avoid global space pollution (internal)
bm::bit_block_or
bool bit_block_or(bm::word_t *BMRESTRICT dst, const bm::word_t *BMRESTRICT src) BMNOEXCEPT
Plain bitblock OR operation. Function does not analyse availability of source and destination blocks.
Definition: bmfunc.h:6722
bm::id_max
const unsigned id_max
Definition: bmconst.h:108
bm::set_block_mask
const unsigned set_block_mask
Definition: bmconst.h:56
bm::bit_block_or_5way
bool bit_block_or_5way(bm::word_t *BMRESTRICT dst, const bm::word_t *BMRESTRICT src1, const bm::word_t *BMRESTRICT src2, const bm::word_t *BMRESTRICT src3, const bm::word_t *BMRESTRICT src4) BMNOEXCEPT
5 way (target, source1, source2) bitblock OR operation. Function does not analyse availability of sou...
Definition: bmfunc.h:6883
bm::aggregator< bvector_type >::max_size
max_size
Maximum aggregation capacity in one pass.
Definition: bmaggregator.h:69
bm::set_array_mask
const unsigned set_array_mask
Definition: bmconst.h:96
bm::aggregator< bvector_type >::operation
operation
Codes for aggregation operations which can be pipelined for efficient execution.
Definition: bmaggregator.h:76
max_size
const unsigned max_size
Definition: xsample01.cpp:56
bm::bvector::allocator_pool_type
allocator_type::allocator_pool_type allocator_pool_type
Definition: bm.h:111
bm::aggregator::sort_input_blocks_and
bm::word_t * sort_input_blocks_and(const bvector_type_const_ptr *bv_src, unsigned src_size, unsigned i, unsigned j, unsigned *arg_blk_count, unsigned *arg_blk_gap_count) BMNOEXCEPT
Definition: bmaggregator.h:1553
bm::aggregator::digest_type
bm::id64_t digest_type
Definition: bmaggregator.h:64
BMNOEXCEPT
#define BMNOEXCEPT
Definition: bmdef.h:79
bm::bit_block_or_3way
bool bit_block_or_3way(bm::word_t *BMRESTRICT dst, const bm::word_t *BMRESTRICT src1, const bm::word_t *BMRESTRICT src2) BMNOEXCEPT
3 way (target | source1 | source2) bitblock OR operation. Function does not analyse availability of s...
Definition: bmfunc.h:6839
bm::aggregator::set_compute_count
void set_compute_count(bool count_mode)
Definition: bmaggregator.h:110
bm::bvector::opt_compress
@ opt_compress
compress blocks when possible (GAP/prefix sum)
Definition: bm.h:134
bm::update_block_digest0
bm::id64_t update_block_digest0(const bm::word_t *const block, bm::id64_t digest) BMNOEXCEPT
Compute digest for 64 non-zero areas based on existing digest (function revalidates zero areas)
Definition: bmfunc.h:778
bm::aggregator::resize_target
static unsigned resize_target(bvector_type &bv_target, const bvector_type_const_ptr *bv_src, unsigned src_size, bool init_clear=true)
Definition: bmaggregator.h:1444
bm::calc_block_digest0
bm::id64_t calc_block_digest0(const bm::word_t *const block) BMNOEXCEPT
Compute digest for 64 non-zero areas.
Definition: bmfunc.h:736
FULL_BLOCK_FAKE_ADDR
#define FULL_BLOCK_FAKE_ADDR
Definition: bmdef.h:149
bm::gap_word_t
unsigned short gap_word_t
Definition: bmconst.h:77
bm::set_array_shift
const unsigned set_array_shift
Definition: bmconst.h:95
bvector_type
bm::bvector bvector_type
Definition: xsample07a.cpp:93
BM_ASSERT
#define BM_ASSERT
Definition: bmdef.h:130
bm::aggregator::set_optimization
void set_optimization(typename bvector_type::optmode opt=bvector_type::opt_compress)
set on-the-fly bit-block compression By default aggregator does not try to optimize result,...
Definition: bmaggregator.h:106
bm::aggregator::op_undefined
@ op_undefined
Definition: bmaggregator.h:84
bm::aggregator::process_bit_blocks_or
bool process_bit_blocks_or(blocks_manager_type &bman_target, unsigned i, unsigned j, unsigned block_count)
Definition: bmaggregator.h:1252
bm::aggregator::get_operation_status
operation_status get_operation_status() const
Definition: bmaggregator.h:333
bm::aggregator< bvector_type >::operation_status
operation_status
Definition: bmaggregator.h:82
bm::aggregator::combine_and_sub_horizontal
void combine_and_sub_horizontal(bvector_type &bv_target, const bvector_type_const_ptr *bv_src_and, unsigned src_and_size, const bvector_type_const_ptr *bv_src_sub, unsigned src_sub_size)
Horizontal AND-SUB aggregation (potentially slower) method.
Definition: bmaggregator.h:1656
bmdef.h
Definitions(internal)
bm::aggregator::add
unsigned add(const bvector_type *bv, unsigned agr_group=0) BMNOEXCEPT
Attach source bit-vector to a argument group (0 or 1).
Definition: bmaggregator.h:589
bm::gap_test_unr
unsigned gap_test_unr(const T *BMRESTRICT buf, const unsigned pos) BMNOEXCEPT
Tests if bit = pos is true. Analog of bm::gap_test with SIMD unrolling.
Definition: bmfunc.h:1300
bm::aggregator::size_type
BV::size_type size_type
Definition: bmaggregator.h:62
bm::aligned_free
void aligned_free(void *ptr) BMNOEXCEPT
Aligned free.
Definition: bmalloc.h:424
bm::aggregator_pipeline_execute
void aggregator_pipeline_execute(It first, It last)
Experimental method ro run multiple aggregators in sync.
Definition: bmaggregator.h:491
bm::aggregator::combine_and_horizontal
void combine_and_horizontal(bvector_type &bv_target, const bvector_type_const_ptr *bv_src, unsigned src_size)
Horizontal AND aggregation (potentially slower) method.
Definition: bmaggregator.h:1632
bm::combine_or
void combine_or(BV &bv, It first, It last)
OR Combine bitvector and the iterable sequence.
Definition: bmalgo_impl.h:1016
bm::gap_add_to_bitset
void gap_add_to_bitset(unsigned *BMRESTRICT dest, const T *BMRESTRICT pcurr, unsigned len) BMNOEXCEPT
Adds(OR) GAP block to bitblock.
Definition: bmfunc.h:3424
bm::aggregator::combine_shift_right_and
void combine_shift_right_and(bvector_type &bv_target)
Aggregate added group of vectors using SHIFT-RIGHT and logical AND Operation does NOT perform an expl...
Definition: bmaggregator.h:668
bm::bit_find_first_if_1
bool bit_find_first_if_1(const bm::word_t *BMRESTRICT block, unsigned *BMRESTRICT first, bm::id64_t digest) BMNOEXCEPT
BIT block find the first set bit if only 1 bit is set.
Definition: bmfunc.h:7598
bm::aggregator::process_gap_blocks_sub
digest_type process_gap_blocks_sub(unsigned block_count, digest_type digest)
Definition: bmaggregator.h:1187
FULL_BLOCK_REAL_ADDR
#define FULL_BLOCK_REAL_ADDR
Definition: bmdef.h:148
bm::aggregator::test_gap_blocks_and
bool test_gap_blocks_and(unsigned block_count, unsigned bit_idx)
Definition: bmaggregator.h:1221
bm::aggregator::~aggregator
~aggregator()
Definition: bmaggregator.h:544
bmalgo_impl.h
Algorithms for bvector<>
bm::set_block_shift
const unsigned set_block_shift
Definition: bmconst.h:55
bm::aggregator::reset
void reset() BMNOEXCEPT
Reset aggregate groups, forget all attached vectors.
Definition: bmaggregator.h:554
bm::aggregator::run_step
operation_status run_step(unsigned i, unsigned j)
Run a step of current arrgegation operation.
Definition: bmaggregator.h:1922
bm::aggregator::stage
void stage(bm::word_t *temp_block)
Prepare operation, create internal resources, analyse dependencies.
Definition: bmaggregator.h:1898
bm
Definition: bm.h:76
IS_FULL_BLOCK
#define IS_FULL_BLOCK(addr)
Definition: bmdef.h:153
bm::aggregator::test_gap_blocks_sub
bool test_gap_blocks_sub(unsigned block_count, unsigned bit_idx)
Definition: bmaggregator.h:1235
bm::bit_block_shift_r1_and_unr
bool bit_block_shift_r1_and_unr(bm::word_t *BMRESTRICT block, bm::word_t co_flag, const bm::word_t *BMRESTRICT mask_block, bm::id64_t *BMRESTRICT digest) BMNOEXCEPT
Right bit-shift bitblock by 1 bit (reference) + AND.
Definition: bmfunc.h:5153
bm::aggregator::get_temp_block
bm::word_t * get_temp_block()
Definition: bmaggregator.h:337
bm::aggregator::process_gap_blocks_or
void process_gap_blocks_or(unsigned block_count)
Definition: bmaggregator.h:1142
bm::aggregator::set_range_hint
void set_range_hint(size_type from, size_type to) BMNOEXCEPT
Set search hint for the range, where results needs to be searched (experimental for internal use).
Definition: bmaggregator.h:566
bm::bit_block_and_2way
bm::id64_t bit_block_and_2way(bm::word_t *BMRESTRICT dst, const bm::word_t *BMRESTRICT src1, const bm::word_t *BMRESTRICT src2, bm::id64_t digest) BMNOEXCEPT
digest based bit-block AND
Definition: bmfunc.h:6074
bm::set_word_mask
const unsigned set_word_mask
Definition: bmconst.h:72
bm::bit_block_copy
void bit_block_copy(bm::word_t *BMRESTRICT dst, const bm::word_t *BMRESTRICT src) BMNOEXCEPT
Bitblock copy operation.
Definition: bmfunc.h:5871
bm::word_t
unsigned int word_t
Definition: bmconst.h:38
BMRESTRICT
#define BMRESTRICT
Definition: bmdef.h:193
bm::bvector::blocks_manager_type
blocks_manager< Alloc > blocks_manager_type
Definition: bm.h:112
bm::aggregator::get_arg_block
static const bm::word_t * get_arg_block(const bvector_type_const_ptr *bv_src, unsigned k, unsigned i, unsigned j) BMNOEXCEPT
Definition: bmaggregator.h:1872
bm::aggregator::BM_SHIFT_R_AND
@ BM_SHIFT_R_AND
Definition: bmaggregator.h:79
bm::aggregator::process_gap_blocks_and
digest_type process_gap_blocks_and(unsigned block_count, digest_type digest)
Definition: bmaggregator.h:1153
bm::bit_block_and_5way
bm::id64_t bit_block_and_5way(bm::word_t *BMRESTRICT dst, const bm::word_t *BMRESTRICT src0, const bm::word_t *BMRESTRICT src1, const bm::word_t *BMRESTRICT src2, const bm::word_t *BMRESTRICT src3, bm::id64_t digest) BMNOEXCEPT
digest based bit-block AND 5-way
Definition: bmfunc.h:6007
bm::aggregator::count
size_type count() const
Definition: bmaggregator.h:207
bm::aggregator::max_aggregator_cap
@ max_aggregator_cap
Definition: bmaggregator.h:71
bm::aggregator::op_in_progress
@ op_in_progress
Definition: bmaggregator.h:86
bm::aggregator::find_effective_sub_block_size
static unsigned find_effective_sub_block_size(unsigned i, const bvector_type_const_ptr *bv_src, unsigned src_size, bool top_null_as_zero) BMNOEXCEPT
Definition: bmaggregator.h:915
bm::bit_block_set
void bit_block_set(bm::word_t *BMRESTRICT dst, bm::word_t value) BMNOEXCEPT
Bitblock memset operation.
Definition: bmfunc.h:3829
bm::block_init_digest0
void block_init_digest0(bm::word_t *const block, bm::id64_t digest) BMNOEXCEPT
Init block with 000111000 pattren based on digest.
Definition: bmfunc.h:706
bm::aggregator::find_first_and_sub
bool find_first_and_sub(size_type &idx)
Definition: bmaggregator.h:658
bm::aggregator::get_operation
int get_operation() const BMNOEXCEPT
Get current operation code.
Definition: bmaggregator.h:317