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

Go to the SVN repository for this file.

1 #ifndef BM_BLOCKS__H__INCLUDED__
2 #define BM_BLOCKS__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 
22 #include "bmfwd.h"
23 
24 #ifdef _MSC_VER
25 #pragma warning( push )
26 #pragma warning( disable : 4100)
27 #endif
28 
29 
30 namespace bm
31 {
32 
33 /*!
34  @brief bitvector blocks manager
35  Embedded class managing bit-blocks on very low level.
36  Includes number of functor classes used in different bitset algorithms.
37  @ingroup bvector
38  @internal
39 */
40 template<class Alloc>
42 {
43 public:
44  template<typename TAlloc> friend class bvector;
45 
47 #ifdef BM64ADDR
48  typedef bm::id64_t id_type;
49  typedef bm::id64_t block_idx_type;
50 #else
51  typedef bm::id_t id_type;
53 #endif
54  typedef id_type size_type;
55 
56 
57  /// Allocation arena for ReadOnly vectors
58  ///
59  /// @internal
60  struct arena
61  {
62  void* a_ptr_; ///< main allocated pointer
63  bm::word_t*** top_blocks_; ///< top descriptor
64  bm::word_t* blocks_; ///< bit-blocks area
65  bm::gap_word_t* gap_blocks_; ///< GAP blocks area
66  bm::word_t** blk_blks_; ///< PTR sub-blocks area
67  bm::bv_arena_statistics st_; ///< statistics and sizes
68 
69  /// Set all arena fields to zero
70  void reset()
71  { a_ptr_ = 0; top_blocks_ = 0; blocks_ = 0; gap_blocks_ = 0; blk_blks_ = 0;
72  st_.reset(); }
73  };
74 
75 
76  /** Base functor class (block visitor)*/
78  {
79  public:
80  typedef id_type size_type;
81 
83 
84  void on_empty_top(unsigned /* top_block_idx*/ ) BMNOEXCEPT {}
85  void on_empty_block(block_idx_type /* block_idx*/ )BMNOEXCEPT {}
86  private:
89  protected:
91  };
92 
93 
94  /** Base functor class connected for "constant" functors*/
96  {
97  public:
98  typedef id_type size_type;
100 
101  void on_empty_top(unsigned /* top_block_idx*/ ) BMNOEXCEPT {}
102  void on_empty_block(block_idx_type /* block_idx*/ ) BMNOEXCEPT {}
103  private:
106  protected:
108  };
109 
110 
111  /** Base class for bitcounting functors */
113  {
114  protected:
116  : bm_func_base_const(bm) {}
117 
119  {
120  return this->bm_.block_bitcount(block);
121  }
122  };
123 
124 
125  /** Bitcounting functor */
127  {
128  public:
130 
132  : block_count_base(bm), count_(0) {}
133 
135 
136  void operator()(const bm::word_t* block) BMNOEXCEPT
137  {
138  count_ += this->block_count(block);
139  }
140  void add_full(id_type c) BMNOEXCEPT { count_ += c; }
141  void reset() BMNOEXCEPT { count_ = 0; }
142 
143  private:
145  };
146 
147 
148  /** Bitcounting functor filling the block counts array*/
150  {
151  public:
153 
156  {
157  arr_[0] = 0;
158  }
159 
160  void operator()(const bm::word_t* block, id_type idx) BMNOEXCEPT
161  {
162  while (++last_idx_ < idx)
163  arr_[last_idx_] = 0;
164  arr_[idx] = this->block_count(block);
165  last_idx_ = idx;
166  }
167 
169  void on_non_empty_top(unsigned) BMNOEXCEPT {}
170 
171  private:
172  unsigned* arr_;
174  };
175 
176  /** bit value change counting functor */
178  {
179  public:
181 
184  count_(0),
186  {}
187 
190  {
191  block_idx_type cnt = 0;
192  id_type first_bit;
193 
194  if (IS_FULL_BLOCK(block) || (block == 0))
195  {
196  cnt = 1;
197  if (idx)
198  {
199  first_bit = block ? 1 : 0;
200  cnt -= !(prev_block_border_bit_ ^ first_bit);
201  }
202  prev_block_border_bit_ = block ? 1 : 0;
203  }
204  else
205  {
206  if (BM_IS_GAP(block))
207  {
208  gap_word_t* gap_block = BMGAP_PTR(block);
209  cnt = bm::gap_length(gap_block) - 1;
210  if (idx)
211  {
212  first_bit = bm::gap_test_unr(gap_block, 0);
213  cnt -= !(prev_block_border_bit_ ^ first_bit);
214  }
215 
217  bm::gap_test_unr(gap_block, gap_max_bits-1);
218  }
219  else // bitset
220  {
222  if (idx)
223  {
224  first_bit = block[0] & 1;
225  cnt -= !(prev_block_border_bit_ ^ first_bit);
226  }
228  block[set_block_size-1] >> ((sizeof(block[0]) * 8) - 1);
229 
230  }
231  }
232  return cnt;
233  }
234 
236 
238  {
239  count_ += block_count(block, idx);
240  }
241 
242  private:
245  };
246 
247 
248  /** Functor detects if any bit set*/
250  {
251  public:
253 
256  {}
257 
258  bool operator()
259  (const bm::word_t* block, block_idx_type /*idx*/) BMNOEXCEPT
260  {
261  if (BM_IS_GAP(block)) // gap block
262  return (!gap_is_all_zero(BMGAP_PTR(block)));
263  if (IS_FULL_BLOCK(block))
264  return true;
265  return (!bit_is_all_zero(block));
266  }
267  };
268 
269  /*! Change GAP level lengths functor */
271  {
272  public:
274  const gap_word_t* glevel_len) BMNOEXCEPT
275  : bm_func_base(bm), glevel_len_(glevel_len)
276  {
277  BM_ASSERT(glevel_len);
278  }
279 
281  {
282  blocks_manager& bman = this->bm_;
283 
284  if (!BM_IS_GAP(block))
285  return;
286 
287  gap_word_t* gap_blk = BMGAP_PTR(block);
288 
289  // TODO: Use the same code as in the optimize functor
290  if (gap_is_all_zero(gap_blk))
291  {
292  bman.set_block_ptr(idx, 0);
293  bman.get_allocator().free_gap_block(gap_blk,
294  bman.glen());
295  }
296  else
297  if (gap_is_all_one(gap_blk))
298  {
300  bman.get_allocator().free_gap_block(gap_blk,
301  bman.glen());
302  return;
303  }
304 
305  unsigned len = bm::gap_length(gap_blk);
306  int level = bm::gap_calc_level(len, glevel_len_);
307  if (level == -1)
308  {
309  bm::word_t* blk = bman.get_allocator().alloc_bit_block();
310  bman.set_block_ptr(idx, blk);
311  bm::gap_convert_to_bitset(blk, gap_blk);
312  }
313  else
314  {
315  gap_word_t* gap_blk_new =
316  bman.allocate_gap_block(unsigned(level), gap_blk, glevel_len_);
317 
318  bm::word_t* p = (bm::word_t*) gap_blk_new;
319  BMSET_PTRGAP(p);
320  bman.set_block_ptr(idx, p);
321  }
322  bman.get_allocator().free_gap_block(gap_blk, bman.glen());
323  }
324  void on_non_empty_top(unsigned) {}
325 
326  private:
328  };
329 
330  /** Fill block with all-one bits functor */
332  {
333  public:
335 
337  {
338  if (!IS_FULL_BLOCK(block))
339  this->bm_.set_block_all_set(idx);
340  }
341  };
342 
343 public:
345  : alloc_(Alloc())
346  {
348  top_block_size_ = 1;
349  }
350 
351  blocks_manager(const gap_word_t* glevel_len,
352  id_type max_bits,
353  const Alloc& alloc = Alloc())
354  : max_bits_(max_bits),
355  alloc_(alloc)
356  {
357  ::memcpy(glevel_len_, glevel_len, sizeof(glevel_len_));
358  top_block_size_ = 1;
359  }
360 
362  : max_bits_(blockman.max_bits_),
364  alloc_(blockman.alloc_)
365  {
366  ::memcpy(glevel_len_, blockman.glevel_len_, sizeof(glevel_len_));
367  if (blockman.is_init())
368  {
369  if (blockman.arena_)
370  this->copy_to_arena(blockman);
371  else
372  this->copy(blockman);
373  }
374  }
375 
376 #ifndef BM_NO_CXX11
378  : max_bits_(blockman.max_bits_),
379  top_block_size_(blockman.top_block_size_),
380  alloc_(blockman.alloc_)
381  {
382  ::memcpy(glevel_len_, blockman.glevel_len_, sizeof(glevel_len_));
383  move_from(blockman);
384  }
385 #endif
386 
388  {
389  if (temp_block_)
390  alloc_.free_bit_block(temp_block_);
391  deinit_tree();
392  }
393 
394  /*! \brief Swaps content
395  \param bm another blocks manager
396  */
398  {
399  BM_ASSERT(this != &bm);
400 
401  word_t*** btmp = top_blocks_;
402  top_blocks_ = bm.top_blocks_;
403  bm.top_blocks_ = btmp;
404 
405  bm::xor_swap(this->max_bits_, bm.max_bits_);
406  bm::xor_swap(this->top_block_size_, bm.top_block_size_);
407 
408  arena* ar = arena_; arena_ = bm.arena_; bm.arena_ = ar;
409 
410  BM_ASSERT(sizeof(glevel_len_) / sizeof(glevel_len_[0]) == bm::gap_levels); // paranoiya check
411  for (unsigned i = 0; i < bm::gap_levels; ++i)
412  bm::xor_swap(glevel_len_[i], bm.glevel_len_[i]);
413  }
414 
415  /*! \brief implementation of moving semantics
416  */
418  {
419  deinit_tree();
420  swap(bm);
421  alloc_ = bm.alloc_;
422  if (!temp_block_) // this does not have temp_block, borrow it from the donor
423  {
424  temp_block_ = bm.temp_block_;
425  bm.temp_block_ = 0;
426  }
427  }
428 
429 
431  {
432  alloc_.free_ptr(ptr);
433  }
434 
435  /**
436  \brief Compute size of the block array needed to store bits
437  \param bits_to_store - supposed capacity (number of bits)
438  \return size of the top level block
439  */
440  unsigned compute_top_block_size(id_type bits_to_store) const BMNOEXCEPT
441  {
442  if (bits_to_store >= bm::id_max) // working in full-range mode
443  return bm::set_top_array_size;
444 
445  unsigned top_block_sz = (unsigned)
446  (bits_to_store / (bm::set_block_size * sizeof(bm::word_t) *
448  if (top_block_sz < bm::set_sub_array_size) ++top_block_sz;
449  return top_block_sz;
450  }
451 
452  /**
453  Returns current capacity (bits)
454  */
455  /*
456  bm::id_t capacity() const
457  {
458  // arithmetic overflow protection...
459  return top_block_size_ == bm::set_array_size ? bm::id_max :
460  top_block_size_ * bm::set_array_size * bm::bits_in_block;
461  }
462  */
463 
464 
465  /**
466  \brief Finds block in 2-level blocks array
467  Specilized version of get_block(unsigned), returns an additional
468  condition when there are no more blocks
469 
470  \param nb - Index of block (logical linear number)
471  \param no_more_blocks - 1 if there are no more blocks at all
472  \return block adress or NULL if not yet allocated
473  */
474  const bm::word_t*
475  get_block(block_idx_type nb, int* no_more_blocks) const BMNOEXCEPT
476  {
478  unsigned i = unsigned(nb >> bm::set_array_shift);
479  if (i >= top_block_size_)
480  {
481  *no_more_blocks = 1;
482  return 0;
483  }
484  *no_more_blocks = 0;
485  bm::word_t** blk_blk = top_blocks_[i];
486  bm::word_t* ret;
487  if ((bm::word_t*)blk_blk == FULL_BLOCK_FAKE_ADDR)
488  {
489  ret = FULL_BLOCK_REAL_ADDR;
490  }
491  else
492  {
493  ret = blk_blk ? blk_blk[nb & bm::set_array_mask] : 0;
494  if (ret == FULL_BLOCK_FAKE_ADDR)
495  ret = FULL_BLOCK_REAL_ADDR;
496  }
497  return ret;
498  }
499 
500 
501  /**
502  Find the next non-zero block starting from nb
503  \param nb - block index
504  \param deep_scan - flag to perform detailed bit-block analysis
505  @return bm::set_total_blocks - no more blocks
506  */
509  {
510  if (is_init())
511  {
512  unsigned i,j;
513  get_block_coord(nb, i, j);
514  for (;i < top_block_size_; ++i)
515  {
516  bm::word_t** blk_blk = top_blocks_[i];
517  if (!blk_blk)
518  {
519  nb += bm::set_sub_array_size - j;
520  }
521  else
522  for (;j < bm::set_sub_array_size; ++j, ++nb)
523  {
524  bm::word_t* blk = blk_blk[j];
525  if (blk && !bm::check_block_zero(blk, deep_scan))
526  return nb;
527  } // for j
528  j = 0;
529  } // for i
530  } // is_init()
531  return bm::set_total_blocks;
532  }
533 
534  /**
535  \brief Finds block in 2-level blocks array
536  \param i - top level block index
537  \param j - second level block index
538  \return block adress or NULL if not yet allocated
539  */
540  const bm::word_t* get_block(unsigned i, unsigned j) const BMNOEXCEPT
541  {
542  if (!top_blocks_ || i >= top_block_size_) return 0;
543  const bm::word_t* const* blk_blk = top_blocks_[i];
544  if ((bm::word_t*)blk_blk == FULL_BLOCK_FAKE_ADDR)
545  return FULL_BLOCK_REAL_ADDR;
546  const bm::word_t* ret = (blk_blk == 0) ? 0 : blk_blk[j];
547  return (ret == FULL_BLOCK_FAKE_ADDR) ? FULL_BLOCK_REAL_ADDR : ret;
548  }
549 
550  /**
551  \brief Finds block in 2-level blocks array (unsinitized)
552  \param i - top level block index
553  \param j - second level block index
554  \return block adress or NULL if not yet allocated
555  */
556  const bm::word_t* get_block_ptr(unsigned i, unsigned j) const BMNOEXCEPT
557  {
558  if (!top_blocks_ || i >= top_block_size_) return 0;
559 
560  const bm::word_t* const* blk_blk = top_blocks_[i];
561  if ((bm::word_t*)blk_blk == FULL_BLOCK_FAKE_ADDR)
562  return (bm::word_t*)blk_blk;
563  return (blk_blk) ? blk_blk[j] : 0;
564  }
565  /**
566  \brief Finds block in 2-level blocks array (unsinitized)
567  \param i - top level block index
568  \param j - second level block index
569  \return block adress or NULL if not yet allocated
570  */
571  bm::word_t* get_block_ptr(unsigned i, unsigned j) BMNOEXCEPT
572  {
573  if (!top_blocks_ || i >= top_block_size_)
574  return 0;
575  bm::word_t* const* blk_blk = top_blocks_[i];
576  if ((bm::word_t*)blk_blk == FULL_BLOCK_FAKE_ADDR)
577  return (bm::word_t*)blk_blk;
578  return (blk_blk) ? blk_blk[j] : 0;
579  }
580 
581 
582  /**
583  \brief Function returns top-level block in 2-level blocks array
584  \param i - top level block index
585  \return block adress or NULL if not yet allocated
586  */
587  const bm::word_t* const * get_topblock(unsigned i) const BMNOEXCEPT
588  {
589  return (!top_blocks_ || i >= top_block_size_) ? 0 : top_blocks_[i];
590  }
591 
592  /**
593  \brief Returns root block in the tree.
594  */
596  {
597  blocks_manager* bm =
598  const_cast<blocks_manager*>(this);
599  return bm->top_blocks_root();
600  }
601 
603  {
604  unsigned i, j;
605  get_block_coord(nb, i, j);
606  set_block_all_set(i, j);
607  }
608 
609  void set_block_all_set(unsigned i, unsigned j)
610  {
613  }
614 
615  void set_block_all_set_no_check(unsigned i, unsigned j)
616  {
617  bm::word_t* block = this->get_block_ptr(i, j);
618  if (IS_VALID_ADDR(block))
619  {
620  if (BM_IS_GAP(block))
621  alloc_.free_gap_block(BMGAP_PTR(block), glevel_len_);
622  else
623  alloc_.free_bit_block(block);
624  }
626  }
627 
628  /**
629  Places new block into blocks table.
630  */
631  void set_block_all_set_ptr(unsigned i, unsigned j)
632  {
634  return;
635  if (!top_blocks_[i])
636  alloc_top_subblock(i, 0);
638  }
639 
640 
641  /**
642  set all-set block pointers for [start..end]
643  */
645  {
646  BM_ASSERT(nb <= nb_to);
647 
648  unsigned i, j, i_from, j_from, i_to, j_to;
649  get_block_coord(nb, i_from, j_from);
650  get_block_coord(nb_to, i_to, j_to);
651 
652  reserve_top_blocks(i_to+1);
653 
654  bm::word_t*** blk_root = top_blocks_root();
655 
656  if (i_from == i_to) // same subblock
657  {
658  bm::word_t** blk_blk = blk_root[i_from];
659  if (blk_blk != (bm::word_t**)FULL_BLOCK_FAKE_ADDR)
660  {
661  for (j = j_from; j <= j_to; ++j)
662  set_block_all_set_no_check(i_from, j);
663  }
664  return;
665  }
666  if (j_from > 0) // process first sub
667  {
668  bm::word_t** blk_blk = blk_root[i_from];
669  if (blk_blk != (bm::word_t**)FULL_BLOCK_FAKE_ADDR)
670  {
671  for (j = j_from; j < bm::set_sub_array_size; ++j)
672  set_block_all_set_no_check(i_from, j); // TODO: optimize
673  }
674  ++i_from;
675  }
676  if (j_to < bm::set_sub_array_size-1) // process last sub
677  {
678  bm::word_t** blk_blk = blk_root[i_to];
679  if (blk_blk != (bm::word_t**)FULL_BLOCK_FAKE_ADDR)
680  {
681  for (j = 0; j <= j_to; ++j)
683  }
684  --i_to; // safe because (i_from == i_to) case is covered
685  }
686 
687  // process all full sub-lanes
688  //
689  for (i = i_from; i <= i_to; ++i)
690  {
691  bm::word_t** blk_blk = blk_root[i];
692  if (!blk_blk || blk_blk == (bm::word_t**)FULL_BLOCK_FAKE_ADDR)
693  {
694  blk_root[i] = (bm::word_t**)FULL_BLOCK_FAKE_ADDR;
695  continue;
696  }
697  j = 0;
698  do
699  {
700  if (blk_blk[j] != FULL_BLOCK_FAKE_ADDR)
702  } while (++j < bm::set_sub_array_size);
703  } // for i
704  }
705 
706  /**
707  set all-Zero block pointers for [start..end]
708  */
710  {
711  BM_ASSERT(nb <= nb_to);
712 
713  unsigned i, j, i_from, j_from, i_to, j_to;
714  get_block_coord(nb, i_from, j_from);
715 
716  if (i_from >= top_block_size_) // nothing to do
717  return;
718 
719  get_block_coord(nb_to, i_to, j_to);
720 
721  if (i_to >= top_block_size_)
722  {
723  i_to = top_block_size_-1;
724  j_to = bm::set_sub_array_size;
725  }
726 
727  bm::word_t*** blk_root = top_blocks_root();
728 
729  if (i_from == i_to) // same subblock
730  {
731  bm::word_t** blk_blk = blk_root[i_from];
732  if (blk_blk)
733  {
734  j_to -= (j_to == bm::set_sub_array_size);
735  for (j = j_from; j <= j_to; ++j)
736  zero_block(i_from, j); // TODO: optimization (lots of ifs in this loop)
737  }
738  return;
739  }
740  if (j_from > 0) // process first sub
741  {
742  bm::word_t** blk_blk = blk_root[i_from];
743  if (blk_blk)
744  {
745  for (j = j_from; j < bm::set_sub_array_size; ++j)
746  zero_block(i_from, j); // TODO: optimize (zero_block is slo)
747  }
748  ++i_from;
749  }
750  if (j_to < bm::set_sub_array_size-1) // process last sub
751  {
752  bm::word_t** blk_blk = blk_root[i_to];
753  if (blk_blk)
754  {
755  for (j = 0; j <= j_to; ++j)
756  zero_block(i_to, j);
757  }
758  --i_to; // safe because (i_from == i_to) case is covered
759  }
760  // process all full sub-lanes
761  // TODO: loop unroll /SIMD
762  for (i = i_from; i <= i_to; ++i)
763  {
764  bm::word_t** blk_blk = blk_root[i];
765  if (!blk_blk)
766  continue;
767  if (blk_blk == (bm::word_t**)FULL_BLOCK_FAKE_ADDR)
768  {
769  blk_root[i] = 0;
770  continue;
771  }
772  j = 0;
773  do
774  {
775  if (blk_blk[j])
776  zero_block(i, j);
777  } while (++j < bm::set_sub_array_size);
778  } // for i
779  }
780 
781 
782  /**
783  Create(allocate) bit block. Old block (if exists) gets deleted.
784  */
786  {
787  bm::word_t* block = this->get_allocator().alloc_bit_block();
788  bm::word_t* old_block = set_block(nb, block);
789  if (IS_VALID_ADDR(old_block))
790  {
791  if (BM_IS_GAP(old_block))
792  alloc_.free_gap_block(BMGAP_PTR(old_block), glen());
793  else
794  alloc_.free_bit_block(old_block);
795  }
796  return block;
797  }
798 
799  /**
800  Create all-zeros bit block. Old block (if exists) gets deleted.
801  */
803  {
804  bm::word_t* block = this->alloc_bit_block(nb);
805  bit_block_set(block, 0);
806  return block;
807  }
808 
809  /**
810  Create bit block as a copy of source block (bit or gap).
811  Old block (if exists) gets deleted.
812  */
814  const bm::word_t* block_src, int is_src_gap)
815  {
816  if (block_src == 0)
817  {
818  zero_block(nb);
819  return 0;
820  }
821  bm::word_t* block = alloc_bit_block(nb);
822  if (is_src_gap)
823  {
824  gap_word_t* gap_block = BMGAP_PTR(block_src);
825  bm::gap_convert_to_bitset(block, gap_block);
826  }
827  else
828  {
829  bm::bit_block_copy(block, block_src);
830  }
831  return block;
832  }
833 
834  /**
835  Clone GAP block from another GAP
836  It can mutate into a bit-block if does not fit
837  */
838  bm::word_t* clone_gap_block(const bm::gap_word_t* gap_block, bool& gap_res)
839  {
840  BM_ASSERT(gap_block);
841 
842  bm::word_t* new_block;
843  unsigned len = bm::gap_length(gap_block);
844  int new_level = bm::gap_calc_level(len, glen());
845  if (new_level < 0) // mutation
846  {
847  gap_res = false;
848  new_block = alloc_.alloc_bit_block();
849  bm::gap_convert_to_bitset(new_block, gap_block);
850  }
851  else
852  {
853  gap_res = true;
854  new_block = (bm::word_t*)
855  get_allocator().alloc_gap_block(unsigned(new_level), glen());
856  ::memcpy(new_block, gap_block, len * sizeof(bm::gap_word_t));
857  bm::set_gap_level(new_block, new_level);
858  }
859  return new_block;
860  }
861 
862  /** Clone static known block, assign to i-j position. Old block must be NULL.
863  @return new block address
864  */
865  void clone_gap_block(unsigned i,
866  unsigned j,
867  const bm::gap_word_t* gap_block,
868  unsigned len)
869  {
870  BM_ASSERT(get_block(i, j) == 0);
871 
872  int new_level = bm::gap_calc_level(len, this->glen());
873  if (!new_level) // level 0, check if it is empty
874  {
875  if (bm::gap_is_all_zero(gap_block))
876  return;
877  }
878 
879  if (new_level < 0)
880  {
881  convert_gap2bitset(i, j, gap_block, len);
882  return;
883  }
884  bm::gap_word_t* new_blk = allocate_gap_block(unsigned(new_level), gap_block);
885  bm::set_gap_level(new_blk, new_level);
886  bm::word_t* p = (bm::word_t*)new_blk;
887  BMSET_PTRGAP(p);
888  set_block(i, j, p, true); // set GAP block
889  }
890 
891  /** Clone block, assign to i-j position
892  @return new block address
893  */
894  bm::word_t* clone_assign_block(unsigned i, unsigned j,
895  const bm::word_t* src_block,
896  bool invert = false)
897  {
898  BM_ASSERT(src_block);
899  bm::word_t* block = 0;
900  if (BM_IS_GAP(src_block))
901  {
902  const bm::gap_word_t* gap_block = BMGAP_PTR(src_block);
903  if (bm::gap_is_all_zero(gap_block))
904  block = invert ? FULL_BLOCK_FAKE_ADDR : 0;
905  else
906  if (bm::gap_is_all_one(gap_block))
907  block = invert ? 0 : FULL_BLOCK_FAKE_ADDR;
908  else
909  {
910  bool is_gap;
911  block = clone_gap_block(gap_block, is_gap);
912  if (is_gap)
913  {
914  if (invert)
915  bm::gap_invert(block);
916  BMSET_PTRGAP(block);
917  }
918  else
919  {
920  if (invert) // TODO: implement inverted copy
921  bm::bit_invert((wordop_t*)block);
922  }
923  }
924  }
925  else // bit-block
926  {
927  if (src_block == FULL_BLOCK_FAKE_ADDR /*IS_FULL_BLOCK(blk_arg)*/)
928  block = invert ? 0 : FULL_BLOCK_FAKE_ADDR;
929  else
930  {
931  bm::bit_block_copy(block = alloc_.alloc_bit_block(), src_block);
932  if (invert) // TODO: implement inverted copy
933  bm::bit_invert((wordop_t*) block);
934  }
935  }
936  BM_ASSERT(top_blocks_[i][j] == 0);
937  top_blocks_[i][j] = block;
938  return block;
939  }
940 
941  /**
942  Attach the result of a GAP logical operation
943  */
945  const bm::gap_word_t* res,
946  unsigned res_len,
947  bm::word_t* blk,
948  gap_word_t* tmp_buf)
949  {
950  unsigned i, j;
951  get_block_coord(nb, i, j);
952  assign_gap(i, j, res, res_len, blk, tmp_buf);
953  }
954 
955  /** Attach the result of a GAP logical operation
956  but check if it is all 000.. or FF..
957  */
958  void assign_gap_check(unsigned i,
959  unsigned j,
960  const bm::gap_word_t* res,
961  unsigned res_len,
962  bm::word_t* blk,
963  gap_word_t* tmp_buf)
964  {
965  if (bm::gap_is_all_one(res))
966  {
967  zero_gap_block_ptr(i, j);
969  }
970  else
971  {
972  if (bm::gap_is_all_zero(res))
973  zero_gap_block_ptr(i, j);
974  else
975  assign_gap(i, j, res, ++res_len, blk, tmp_buf);
976  }
977  }
978 
979  /** Attach the result of a GAP logical operation
980  */
981  void assign_gap(unsigned i,
982  unsigned j,
983  const bm::gap_word_t* res,
984  unsigned res_len,
985  bm::word_t* blk,
986  gap_word_t* tmp_buf)
987  {
988  int level = bm::gap_level(BMGAP_PTR(blk));
989  BM_ASSERT(level >= 0);
990  unsigned threshold = unsigned(this->glen(unsigned(level)) - 4u);
991  int new_level = bm::gap_calc_level(res_len, this->glen());
992  if (new_level < 0)
993  {
994  convert_gap2bitset(i, j, res);
995  return;
996  }
997  if (res_len > threshold) // GAP block needs next level up extension
998  {
999  BM_ASSERT(new_level >= 0);
1000  gap_word_t* new_blk = allocate_gap_block(unsigned(new_level), res);
1001  bm::set_gap_level(new_blk, new_level);
1002  bm::word_t* p = (bm::word_t*)new_blk;
1003  BMSET_PTRGAP(p);
1004  if (blk)
1005  {
1006  set_block_ptr(i, j, p);
1007  alloc_.free_gap_block(BMGAP_PTR(blk), this->glen());
1008  }
1009  else
1010  {
1011  set_block(i, j, p, true); // set GAP block
1012  }
1013  return;
1014  }
1015  // gap operation result is in the temporary buffer
1016  // we copy it back to the gap_block (target size/level - fits)
1017  BM_ASSERT(blk);
1018  bm::set_gap_level(tmp_buf, level);
1019  ::memcpy(BMGAP_PTR(blk), tmp_buf, res_len * sizeof(gap_word_t));
1020  }
1021 
1022 
1023  /**
1024  Copy block from another vector.
1025  Note:Target block is always replaced through re-allocation.
1026  */
1028  {
1029  const bm::word_t* block = bm_src.get_block(idx);
1030  if (block == 0)
1031  {
1032  zero_block(idx);
1033  return 0;
1034  }
1035  bm::word_t* new_blk = 0;
1036  bool is_gap = BM_IS_GAP(block);
1037 
1038  if (is_gap)
1039  {
1040  bm::gap_word_t* gap_block = BMGAP_PTR(block);
1041  new_blk = clone_gap_block(gap_block, is_gap); // is_gap - output
1042  }
1043  else
1044  {
1045  if (IS_FULL_BLOCK(block))
1046  {
1047  new_blk = FULL_BLOCK_FAKE_ADDR;
1048  }
1049  else
1050  {
1051  new_blk = alloc_.alloc_bit_block();
1052  bm::bit_block_copy(new_blk, block);
1053  }
1054  }
1055  set_block(idx, new_blk, is_gap);
1056  return new_blk;
1057  }
1058 
1059 
1060  /**
1061  Function checks if block is not yet allocated, allocates it and sets to
1062  all-zero or all-one bits.
1063 
1064  If content_flag == 1 (ALLSET block) requested and taken block is already ALLSET,
1065  function will return NULL
1066 
1067  initial_block_type and actual_block_type : 0 - bitset, 1 - gap
1068  */
1070  unsigned content_flag,
1071  int initial_block_type,
1072  int* actual_block_type,
1073  bool allow_null_ret=true)
1074  {
1075  unsigned i, j;
1076  bm::get_block_coord(nb, i, j);
1077  bm::word_t* block = this->get_block_ptr(i, j);
1078 
1079  if (!IS_VALID_ADDR(block)) // NULL block or ALLSET
1080  {
1081  // if we wanted ALLSET and requested block is ALLSET return NULL
1082  unsigned block_flag = IS_FULL_BLOCK(block);
1083 
1084  *actual_block_type = initial_block_type;
1085  if (block_flag == content_flag && allow_null_ret)
1086  {
1087  if (block_flag)
1088  return FULL_BLOCK_FAKE_ADDR;
1089  return 0; // it means nothing to do for the caller
1090  }
1091 
1092  reserve_top_blocks(i + 1);
1093  if (initial_block_type == 0) // bitset requested
1094  {
1095  block = alloc_.alloc_bit_block();
1096  // initialize block depending on its previous status
1097  bm::bit_block_set(block, block_flag ? ~0u : 0u);
1098  set_block(i, j, block, false/*bit*/);
1099  }
1100  else // gap block requested
1101  {
1102  bm::gap_word_t* gap_block = allocate_gap_block(0);
1103  bm::gap_set_all(gap_block, bm::gap_max_bits, block_flag);
1104  set_block(i, j, (bm::word_t*)gap_block, true/*gap*/);
1105  return (bm::word_t*)gap_block;
1106  }
1107  }
1108  else // block already exists
1109  {
1110  *actual_block_type = BM_IS_GAP(block);
1111  }
1112  return block;
1113  }
1114 
1115  /**
1116  Function checks if block is not yet allocated, allocates and returns
1117  */
1118  bm::word_t* check_allocate_block(block_idx_type nb, int initial_block_type)
1119  {
1120  unsigned i, j;
1121  bm::get_block_coord(nb, i, j);
1122  bm::word_t* block = this->get_block_ptr(i, j);
1123  if (!IS_VALID_ADDR(block)) // NULL block or ALLSET
1124  {
1125  // if we wanted ALLSET and requested block is ALLSET return NULL
1126  unsigned block_flag = IS_FULL_BLOCK(block);
1127  if (initial_block_type == 0) // bitset requested
1128  {
1129  block = alloc_.alloc_bit_block();
1130  // initialize block depending on its previous status
1131  bm::bit_block_set(block, block_flag ? ~0u : 0);
1132  set_block(nb, block);
1133  }
1134  else // gap block requested
1135  {
1136  bm::gap_word_t* gap_block = allocate_gap_block(0);
1137  gap_set_all(gap_block, bm::gap_max_bits, block_flag);
1138  block = (bm::word_t*)gap_block;
1139  set_block(nb, block, true/*gap*/);
1140  BMSET_PTRGAP(block);
1141  }
1142  }
1143  return block;
1144  }
1145 
1146 
1147  /*! @brief Fills all blocks with 0.
1148  @param free_mem - if true function frees the resources (obsolete)
1149  */
1150  void set_all_zero(bool /*free_mem*/) BMNOEXCEPT
1151  {
1152  if (!is_init()) return;
1153  deinit_tree(); // TODO: optimization of top-level realloc
1154  }
1155 
1156  /*! Replaces all blocks with ALL_ONE block.
1157  */
1159  {
1160  if (!is_init())
1161  init_tree();
1162  block_one_func func(*this);
1164  bm::set_sub_array_size, func);
1165  }
1166 
1167  void free_top_subblock(unsigned nblk_blk) BMNOEXCEPT
1168  {
1169  BM_ASSERT(top_blocks_[nblk_blk]);
1170  if ((bm::word_t*)top_blocks_[nblk_blk] != FULL_BLOCK_FAKE_ADDR)
1171  alloc_.free_ptr(top_blocks_[nblk_blk], bm::set_sub_array_size);
1172  top_blocks_[nblk_blk] = 0;
1173  }
1174 
1175 
1176  bm::word_t** alloc_top_subblock(unsigned nblk_blk)
1177  {
1178  BM_ASSERT(!top_blocks_[nblk_blk] || top_blocks_[nblk_blk] == (bm::word_t**)FULL_BLOCK_FAKE_ADDR);
1179 
1180  bm::word_t** p = (bm::word_t**)alloc_.alloc_ptr(bm::set_sub_array_size);
1181  ::memset(top_blocks_[nblk_blk] = p, 0,
1182  bm::set_sub_array_size * sizeof(bm::word_t*));
1183  return p;
1184  }
1185 
1186  /**
1187  Allocate top sub-block if not allocated. If FULLBLOCK - deoptimize
1188  */
1190  {
1191  if (!top_blocks_[nblk_blk])
1192  return alloc_top_subblock(nblk_blk);
1193  if (top_blocks_[nblk_blk] == (bm::word_t**)FULL_BLOCK_FAKE_ADDR)
1194  return alloc_top_subblock(nblk_blk, FULL_BLOCK_FAKE_ADDR);
1195  return top_blocks_[nblk_blk];
1196  }
1197 
1198  /**
1199  Places new block into descriptors table, returns old block's address.
1200  Old block is NOT deleted.
1201  */
1203  {
1204  bm::word_t* old_block;
1205 
1206  if (!is_init())
1207  init_tree();
1208 
1209  // never use real full block adress, it may be instantiated in another DLL
1210  // (unsafe static instantiation on windows)
1211  if (block == FULL_BLOCK_REAL_ADDR)
1212  block = FULL_BLOCK_FAKE_ADDR;
1213 
1214  unsigned nblk_blk = unsigned(nb >> bm::set_array_shift);
1215  reserve_top_blocks(nblk_blk+1);
1216 
1217  if (!top_blocks_[nblk_blk])
1218  {
1219  alloc_top_subblock(nblk_blk);
1220  old_block = 0;
1221  }
1222  else
1223  {
1224  if (top_blocks_[nblk_blk] == (bm::word_t**)FULL_BLOCK_FAKE_ADDR)
1226  old_block = top_blocks_[nblk_blk][nb & bm::set_array_mask];
1227  }
1228 
1229  // NOTE: block will be replaced without freeing, potential memory leak?
1230  top_blocks_[nblk_blk][nb & bm::set_array_mask] = block;
1231  return old_block;
1232  }
1233 
1234  /**
1235  Allocate an place new GAP block (copy of provided block)
1236  */
1238  const gap_word_t* gap_block_src,
1239  int level)
1240  {
1241  if (level < 0)
1242  {
1243  bm::word_t* blk = alloc_.alloc_bit_block();
1244  set_block(nb, blk);
1245  gap_convert_to_bitset(blk, gap_block_src);
1246  return blk;
1247  }
1248  else
1249  {
1250  gap_word_t* gap_blk = alloc_.alloc_gap_block(
1251  unsigned(level), this->glen());
1252  gap_word_t* gap_blk_ptr = BMGAP_PTR(gap_blk);
1253  ::memcpy(gap_blk_ptr, gap_block_src,
1254  gap_length(gap_block_src) * sizeof(gap_word_t));
1255  set_gap_level(gap_blk_ptr, level);
1256  set_block(nb, (bm::word_t*)gap_blk, true /*GAP*/);
1257  return (bm::word_t*)gap_blk;
1258  }
1259  }
1260 
1261  /**
1262  Places new block into descriptors table, returns old block's address.
1263  Old block is not deleted.
1264  */
1266  {
1267  unsigned i, j;
1268  get_block_coord(nb, i, j);
1269  reserve_top_blocks(i + 1);
1270 
1271  return set_block(i, j, block, gap);
1272  }
1273 
1274 
1275  /**
1276  Places new block into descriptors table, returns old block's address.
1277  Old block is not deleted.
1278  */
1279  bm::word_t* set_block(unsigned i, unsigned j, bm::word_t* block, bool gap)
1280  {
1282  bm::word_t* old_block;
1283  if (block)
1284  {
1285  if (block == FULL_BLOCK_REAL_ADDR)
1286  block = FULL_BLOCK_FAKE_ADDR;
1287  else
1288  block =
1289  (bm::word_t*) (gap ? BMPTR_SETBIT0(block) : BMPTR_CLEARBIT0(block));
1290  }
1291 
1292  // If first level array not yet allocated, allocate it and
1293  // assign block to it
1294  if (!top_blocks_[i])
1295  {
1297  ::memset(top_blocks_[i], 0, bm::set_sub_array_size * sizeof(void*));
1298  old_block = 0;
1299  }
1300  else
1301  {
1304  old_block = top_blocks_[i][j];
1305  }
1306 
1307  // NOTE: block will be replaced without freeing, potential memory leak?
1308  top_blocks_[i][j] = block;
1309  return old_block;
1310  }
1311 
1312  /**
1313  Allocate subblock and fill based on
1314  */
1316  {
1317  BM_ASSERT(addr == 0 || addr == FULL_BLOCK_FAKE_ADDR);
1318  BM_ASSERT(top_blocks_[i] == 0 ||
1320  bm::word_t** blk_blk =
1322  top_blocks_[i] = blk_blk;
1323  for (unsigned j = 0; j < bm::set_sub_array_size; j+=4)
1324  blk_blk[j+0] = blk_blk[j+1] = blk_blk[j+2] = blk_blk[j+3] = addr;
1325  return blk_blk;
1326  }
1327 
1328  /**
1329  Allocate and copy block.
1330  (no checks, no validation, may cause a memory leak if not used carefully)
1331  */
1332  void copy_bit_block(unsigned i, unsigned j, const bm::word_t* src_block)
1333  {
1334  BM_ASSERT(src_block);
1335  BM_ASSERT(src_block != FULL_BLOCK_FAKE_ADDR);
1336 
1337  reserve_top_blocks(i + 1);
1339  BM_ASSERT(top_blocks_[i][j]==0);
1340  bm::word_t* blk = top_blocks_[i][j] = alloc_.alloc_bit_block();
1341  bm::bit_block_stream(blk, src_block);
1342  }
1343 
1344  /**
1345  Optimize and copy bit-block
1346  */
1347  void opt_copy_bit_block(unsigned i, unsigned j,
1348  const bm::word_t* src_block,
1349  int opt_mode,
1350  bm::word_t* tmp_block)
1351  {
1352  if (!opt_mode)
1353  {
1354  copy_bit_block(i, j, src_block);
1355  return;
1356  }
1357 
1358  reserve_top_blocks(i + 1);
1360 
1361  unsigned gap_count = bm::bit_block_calc_change(src_block);
1362  if (gap_count == 1) // solid block
1363  {
1364  if (*src_block) // 0xFFF...
1365  {
1366  BM_ASSERT(bm::is_bits_one((bm::wordop_t*)src_block));
1368  if (++j == bm::set_sub_array_size)
1369  {
1371  }
1372  }
1373  else
1374  {
1375  BM_ASSERT(bm::bit_is_all_zero(src_block));
1376  top_blocks_[i][j] = 0;
1378  }
1379  return;
1380  }
1381  // try to compress
1382  //
1383  unsigned threashold = this->glen(bm::gap_max_level)-4;
1384  if (gap_count < threashold) // compressable
1385  {
1386  BM_ASSERT(tmp_block);
1387  bm::gap_word_t* tmp_gap_blk = (gap_word_t*)tmp_block;
1388 
1389  unsigned len = bm::bit_to_gap(tmp_gap_blk, src_block, threashold);
1390  BM_ASSERT(len);
1391  int level = bm::gap_calc_level(len, this->glen());
1392  BM_ASSERT(level >= 0);
1393  bm::gap_word_t* gap_blk =
1394  allocate_gap_block(unsigned(level), tmp_gap_blk);
1395  BM_ASSERT(top_blocks_[i][j]==0);
1396  top_blocks_[i][j] = (bm::word_t*)BMPTR_SETBIT0(gap_blk);
1397  return;
1398  }
1399  // non-compressable bit-block
1400  copy_bit_block(i, j, src_block);
1401  }
1402 
1403  /**
1404  Optimize bit-block at i-j position
1405  */
1406  void optimize_bit_block(unsigned i, unsigned j, int opt_mode)
1407  {
1408  bm::word_t* block = get_block_ptr(i, j);
1409  if (IS_VALID_ADDR(block))
1410  {
1411  if (BM_IS_GAP(block))
1412  return;
1413 
1414  unsigned gap_count = bm::bit_block_calc_change(block);
1415  if (gap_count == 1) // solid block
1416  {
1417  top_blocks_[i][j] = (*block) ? FULL_BLOCK_FAKE_ADDR : 0;
1418  return_tempblock(block);
1419  return;
1420  }
1421  if (opt_mode < 3) // less than opt_compress
1422  return;
1423 
1424  unsigned threashold = this->glen(bm::gap_max_level)-4;
1425  if (gap_count < threashold) // compressable
1426  optimize_gap_convert_bit_block(i, j, block, threashold);
1427  }
1428  }
1429 
1430  /**
1431  Full Optimize bit-block at i-j position (no checks)
1432  */
1433  void optimize_bit_block_nocheck(unsigned i, unsigned j)
1434  {
1435  bm::word_t* block = get_block_ptr(i, j);
1436 
1437  BM_ASSERT(IS_VALID_ADDR(block));
1438  BM_ASSERT(!BM_IS_GAP(block));
1439 
1440  unsigned gap_count = bm::bit_block_calc_change(block);
1441  if (gap_count == 1) // solid block
1442  {
1443  top_blocks_[i][j] = (*block) ? FULL_BLOCK_FAKE_ADDR : 0;
1444  return_tempblock(block);
1445  return;
1446  }
1447  unsigned threashold = this->glen(bm::gap_max_level)-4;
1448  if (gap_count < threashold) // compressable
1449  optimize_gap_convert_bit_block(i, j, block, threashold);
1450  }
1451 
1452  void optimize_gap_convert_bit_block(unsigned i, unsigned j,
1453  bm::word_t* block,
1454  unsigned threashold)
1455  {
1456  unsigned len;
1457  bm::gap_word_t tmp_gap_buf[bm::gap_equiv_len * 2];
1458 
1459  len = bm::bit_to_gap(tmp_gap_buf, block, threashold);
1460  BM_ASSERT(len);
1461  int level = bm::gap_calc_level(len, this->glen());
1462  BM_ASSERT(level >= 0);
1463  bm::gap_word_t* gap_blk =
1464  allocate_gap_block(unsigned(level), tmp_gap_buf);
1465  top_blocks_[i][j] = (bm::word_t*)BMPTR_SETBIT0(gap_blk);
1466  return_tempblock(block);
1467  }
1468 
1469 
1470  /**
1471  Places new block into blocks table.
1472  */
1473  inline
1475  {
1477  BM_ASSERT(is_init());
1479 
1480  unsigned i = unsigned(nb >> bm::set_array_shift);
1482  {
1483  if (block == FULL_BLOCK_FAKE_ADDR)
1484  return;
1486  }
1487 
1489  (block == FULL_BLOCK_REAL_ADDR) ? FULL_BLOCK_FAKE_ADDR : block;
1490  }
1491 
1492  /**
1493  Places new block into blocks table.
1494  */
1496  void set_block_ptr(unsigned i, unsigned j, bm::word_t* block) BMNOEXCEPT
1497  {
1498  BM_ASSERT(is_init());
1501 
1502  top_blocks_[i][j] =
1503  (block == FULL_BLOCK_REAL_ADDR) ? FULL_BLOCK_FAKE_ADDR : block;
1504  }
1505 
1506 
1507  /**
1508  \brief Converts block from type gap to conventional bitset block.
1509  \param nb - Block's index.
1510  \param gap_block - Pointer to the gap block, if NULL block nb is taken
1511  \return new bit block's memory
1512  */
1514  {
1515  BM_ASSERT(is_init());
1516 
1517  unsigned i, j;
1518  get_block_coord(nb, i, j);
1520 
1521  return convert_gap2bitset(i, j, gap_block);
1522  }
1523 
1524  /**
1525  \brief Converts block from type gap to conventional bitset block.
1526  \param i - top index.
1527  \param j - secondary index.
1528  \param gap_block - Pointer to the gap block, if NULL block [i,j] is taken
1529  \param len - gap length
1530  \return new bit block's memory
1531  */
1532  bm::word_t* convert_gap2bitset(unsigned i, unsigned j,
1533  const gap_word_t* gap_block=0,
1534  unsigned len = 0)
1535  {
1536  BM_ASSERT(is_init());
1537 
1538  if (!top_blocks_[i])
1540  bm::word_t* block = top_blocks_[i][j];
1541  gap_block = gap_block ? gap_block : BMGAP_PTR(block);
1542 
1543  BM_ASSERT(IS_VALID_ADDR((bm::word_t*)gap_block));
1544 
1545  bm::word_t* new_block = alloc_.alloc_bit_block();
1546  bm::gap_convert_to_bitset(new_block, gap_block, len);
1547 
1548  top_blocks_[i][j] = new_block;
1549 
1550  // new block will replace the old one(no deletion)
1551  if (block)
1552  alloc_.free_gap_block(BMGAP_PTR(block), glen());
1553 
1554  return new_block;
1555  }
1556 
1557 
1558  /**
1559  Make sure block turns into true bit-block if it is GAP or a full block
1560  @return bit-block pointer
1561  */
1563  {
1564  unsigned i, j;
1565  bm::get_block_coord(nb, i, j);
1566  return deoptimize_block(i, j, false);
1567  }
1568 
1569  /** deoptimize block and return bit-block ptr
1570  can return NULL if block does not exists or allocate (if requested)
1571  */
1572  bm::word_t* deoptimize_block(unsigned i, unsigned j, bool alloc)
1573  {
1574  bm::word_t* block = this->get_block_ptr(i, j);
1575  if (!block && alloc)
1576  {
1577  reserve_top_blocks(i+1);
1578  if (!top_blocks_[i])
1579  {
1580  alloc_top_subblock(i, 0);
1581  }
1582  bm::word_t* new_block = alloc_.alloc_bit_block();
1583  bm::bit_block_set(new_block, 0u);
1584  set_block_ptr(i, j, new_block);
1585  return new_block;
1586  }
1587  return deoptimize_block_no_check(block, i, j);
1588  }
1589 
1591  unsigned i, unsigned j)
1592  {
1593  BM_ASSERT(block);
1594  if (BM_IS_GAP(block))
1595  {
1596  gap_word_t* gap_block = BMGAP_PTR(block);
1597  bm::word_t* new_block = alloc_.alloc_bit_block();
1598  bm::gap_convert_to_bitset(new_block, gap_block);
1599  alloc_.free_gap_block(gap_block, this->glen());
1600 
1601  set_block_ptr(i, j, new_block);
1602  return new_block;
1603  }
1604  if (IS_FULL_BLOCK(block))
1605  {
1608 
1609  bm::word_t* new_block = alloc_.alloc_bit_block();
1610  bm::bit_block_set(new_block, ~0u);
1611  set_block_ptr(i, j, new_block);
1612  return new_block;
1613  }
1614  return block;
1615  }
1616 
1617 
1618 
1619  /**
1620  Free block, make it zero pointer in the tree
1621  */
1623  {
1624  unsigned i, j;
1625  get_block_coord(nb, i, j);
1626  if (!top_blocks_ || i >= top_block_size_)
1627  return;
1628  zero_block(i, j);
1629  }
1630 
1631 
1632  /**
1633  Free block, make it zero pointer in the tree
1634  */
1635  void zero_block(unsigned i, unsigned j) BMNOEXCEPT
1636  {
1638 
1639  bm::word_t** blk_blk = top_blocks_[i];
1640  if (blk_blk)
1641  {
1642  if (blk_blk == (bm::word_t**)FULL_BLOCK_FAKE_ADDR)
1644 
1645  bm::word_t* block = blk_blk[j];
1646  blk_blk[j] = 0;
1647  if (IS_VALID_ADDR(block))
1648  {
1649  if (BM_IS_GAP(block))
1650  {
1651  alloc_.free_gap_block(BMGAP_PTR(block), glen());
1652  }
1653  else
1654  {
1655  alloc_.free_bit_block(block);
1656  }
1657  }
1658 
1659  if (j == bm::set_sub_array_size-1)
1660  {
1661  // back scan if top sub-block can also be dropped
1662  do {
1663  if (blk_blk[--j])
1664  return;
1665  if (!j)
1666  {
1668  top_blocks_[i] = 0;
1669  return;
1670  }
1671  } while (1);
1672  }
1673  }
1674  }
1675 
1676  /**
1677  Free block, make it zero pointer in the tree
1678  */
1679  void zero_gap_block_ptr(unsigned i, unsigned j) BMNOEXCEPT
1680  {
1682 
1683  bm::word_t** blk_blk = top_blocks_[i];
1684  bm::word_t* block = blk_blk[j];
1685 
1686  BM_ASSERT(blk_blk);
1687  BM_ASSERT(BM_IS_GAP(block));
1688 
1689  blk_blk[j] = 0;
1690  alloc_.free_gap_block(BMGAP_PTR(block), glen());
1691  }
1692 
1693 
1694  /**
1695  Count number of bits ON in the block
1696  */
1697  static
1699  {
1700  BM_ASSERT(block);
1701  id_t count;
1702  if (BM_IS_GAP(block))
1703  count = bm::gap_bit_count_unr(BMGAP_PTR(block));
1704  else // bitset
1705  count = (IS_FULL_BLOCK(block)) ? bm::bits_in_block
1706  : bm::bit_block_count(block);
1707  return count;
1708  }
1709 
1710  /**
1711  Bit count all blocks to determine if it is very sparse
1712  */
1713  bool is_sparse_sblock(unsigned i, unsigned sparse_cut_off) const BMNOEXCEPT
1714  {
1715  if (!sparse_cut_off)
1716  return false;
1717  const unsigned non_sparse_cut_off = sparse_cut_off * bm::set_sub_array_size;
1718 
1719  BM_ASSERT(i < top_block_size());
1720  word_t*** blk_root = top_blocks_root();
1721  if (!blk_root)
1722  return false;
1723  bm::word_t** blk_blk = blk_root[i];
1724  if (!blk_blk || (bm::word_t*)blk_blk == FULL_BLOCK_FAKE_ADDR)
1725  return false;
1726  bm::id_t cnt_sum(0), effective_blocks(0), gap_len_sum(0);
1727  for (unsigned j = 0; j < bm::set_sub_array_size; ++j)
1728  {
1729  const bm::word_t* blk = blk_blk[j]; // this->get_block(i, j);
1730  if (blk == FULL_BLOCK_FAKE_ADDR)
1731  return false;
1732  if (blk)
1733  {
1734  bm::id_t cnt;
1735  if (BM_IS_GAP(blk))
1736  {
1737  const bm::gap_word_t* gp = BMGAP_PTR(blk);
1738  cnt = bm::gap_bit_count_unr(gp);
1739  gap_len_sum += bm::gap_length(gp);
1740  }
1741  else // bitset
1742  {
1743  cnt = bm::bit_block_count(blk);
1744  }
1745  if (cnt)
1746  {
1747  ++effective_blocks;
1748  cnt_sum += cnt;
1749  if (cnt_sum > non_sparse_cut_off) // too many bits set
1750  return false;
1751  }
1752  }
1753  } // for j
1754 
1755  BM_ASSERT(effective_blocks <= bm::set_sub_array_size);
1756  if (effective_blocks > 1)
1757  {
1758  if (cnt_sum < 5) // super-duper sparse ...
1759  return false;
1760 
1761  bm::id_t blk_avg = cnt_sum / effective_blocks;
1762  if (blk_avg <= sparse_cut_off)
1763  {
1764  if (gap_len_sum)
1765  {
1766  gap_len_sum += effective_blocks * 3;
1767  if (gap_len_sum < cnt_sum)
1768  return false;
1769  }
1770  return true;
1771  }
1772  }
1773  return false;
1774  }
1775 
1776  /**
1777  \brief Extends GAP block to the next level or converts it to bit block.
1778  \param nb - Block's linear index.
1779  \param blk - Blocks's pointer
1780 
1781  \return new GAP block pointer or NULL if block type mutated into NULL
1782  */
1784  {
1785  unsigned level = bm::gap_level(blk);
1786  unsigned len = bm::gap_length(blk);
1787  if (level == bm::gap_max_level || len >= gap_max_buff_len)
1788  {
1789  deoptimize_block(nb);
1790  }
1791  else
1792  {
1793  bm::gap_word_t* new_gap_blk = allocate_gap_block(++level, blk);
1794  bm::word_t* new_blk = (bm::word_t*)new_gap_blk;
1795  BMSET_PTRGAP(new_blk);
1796 
1797  set_block_ptr(nb, new_blk);
1798  alloc_.free_gap_block(blk, glen());
1799 
1800  return new_gap_blk;
1801  }
1802  return 0;
1803  }
1804  /**
1805  Mark pointer as GAP and assign to the blocks tree
1806  */
1808  {
1809  bm::word_t* block = (bm::word_t*)BMPTR_SETBIT0(gap_blk);
1810  set_block_ptr(nb, block);
1811  }
1812 
1813 
1814  /*! Returns temporary block, allocates if needed. */
1816  {
1817  return temp_block_ ? temp_block_
1818  : (temp_block_ = alloc_.alloc_bit_block());
1819  }
1820 
1821  /*! deallocate temp block */
1823  {
1824  if (temp_block_)
1825  {
1826  alloc_.free_bit_block(temp_block_);
1827  temp_block_ = 0;
1828  }
1829  }
1830 
1831  /*! Detach and return temp block.
1832  if temp block is NULL allocates a bit-block
1833  caller is responsible for returning
1834  @sa return_tempblock
1835  */
1837  {
1838  if (temp_block_)
1839  {
1840  bm::word_t* ret = temp_block_; temp_block_ = 0;
1841  return ret;
1842  }
1843  return alloc_.alloc_bit_block();
1844  }
1845 
1846  /*! Return temp block
1847  if temp block already exists - block gets deallocated
1848  */
1850  {
1851  BM_ASSERT(block != temp_block_);
1852  BM_ASSERT(IS_VALID_ADDR(block));
1853 
1854  if (temp_block_)
1855  alloc_.free_bit_block(block);
1856  else
1857  temp_block_ = block;
1858  }
1859 
1860  /*! Assigns new GAP lengths vector */
1861  void set_glen(const gap_word_t* glevel_len) BMNOEXCEPT
1862  {
1863  ::memcpy(glevel_len_, glevel_len, sizeof(glevel_len_));
1864  }
1865 
1867  const gap_word_t* src = 0,
1868  const gap_word_t* glevel_len = 0)
1869  {
1870  if (!glevel_len)
1871  glevel_len = glevel_len_;
1872  gap_word_t* ptr = alloc_.alloc_gap_block(level, glevel_len);
1873  if (src)
1874  {
1875  unsigned len = gap_length(src);
1876  ::memcpy(ptr, src, len * sizeof(gap_word_t));
1877  // Reconstruct the mask word using the new level code.
1878  *ptr = (gap_word_t)(((len-1) << 3) | (level << 1) | (*src & 1));
1879  }
1880  else
1881  {
1882  *ptr = (gap_word_t)(level << 1);
1883  }
1884  return ptr;
1885  }
1886 
1887  /** Returns true if second level block pointer is 0.
1888  */
1889  bool is_subblock_null(unsigned nsub) const BMNOEXCEPT
1890  {
1892  if (nsub >= top_block_size_)
1893  return true;
1894  return top_blocks_[nsub] == NULL;
1895  }
1896 
1898 
1899  /*! \brief Returns current GAP level vector
1900  */
1902  {
1903  return glevel_len_;
1904  }
1905 
1906  /*! \brief Returns GAP level length for specified level
1907  \param level - level number
1908  */
1909  unsigned glen(unsigned level) const BMNOEXCEPT
1910  {
1911  return glevel_len_[level];
1912  }
1913 
1914  /*! \brief Returns size of the top block array in the tree
1915  */
1917  {
1918  return top_block_size_;
1919  }
1920 
1921  /**
1922  \brief reserve capacity for specified number of bits
1923  */
1924  void reserve(id_type max_bits)
1925  {
1926  if (max_bits)
1927  {
1928  unsigned bc = compute_top_block_size(max_bits);
1929  reserve_top_blocks(bc);
1930  }
1931  }
1932 
1933  /*!
1934  \brief Make sure blocks manager has enough blocks capacity
1935  */
1936  unsigned reserve_top_blocks(unsigned top_blocks)
1937  {
1938  if ((top_blocks_ && top_blocks <= top_block_size_) || !top_blocks )
1939  return top_block_size_; // nothing to do
1940 
1941  bm::word_t*** new_blocks =
1942  (bm::word_t***)alloc_.alloc_ptr(top_blocks);
1943 
1944  unsigned i = 0;
1945  if (top_blocks_)
1946  {
1947  if (i < top_block_size_)
1948  {
1949  ::memcpy(&new_blocks[0], &top_blocks_[0],
1950  top_block_size_ * sizeof(top_blocks_[0]));
1951  i = top_block_size_;
1952  }
1953  alloc_.free_ptr(top_blocks_, top_block_size_);
1954  }
1955  if (i < top_blocks)
1956  ::memset(&new_blocks[i], 0, sizeof(void*) * (top_blocks-i));
1957  top_blocks_ = new_blocks;
1958  top_block_size_ = top_blocks;
1959  return top_block_size_;
1960  }
1961 
1962  /**
1963  \brief shrink unused top blocks array (via reallocation)
1964  */
1966  {
1967  if (!top_blocks_)
1968  return;
1969  unsigned tb_cnt = top_block_size() - 1;
1970  for ( ; tb_cnt; --tb_cnt)
1971  {
1972  if (top_blocks_[tb_cnt])
1973  break;
1974  } // for
1975  if (++tb_cnt < top_block_size_) // shrink is possible
1976  {
1977  BM_ASSERT(tb_cnt <= top_block_size_);
1978  bm::word_t*** new_blocks =
1979  (bm::word_t***)alloc_.alloc_ptr(tb_cnt);
1980  ::memcpy(&new_blocks[0], &top_blocks_[0],
1981  tb_cnt * sizeof(top_blocks_[0]));
1982  alloc_.free_ptr(top_blocks_, top_block_size_);
1983  top_blocks_ = new_blocks;
1984  top_block_size_ = tb_cnt;
1985  }
1986  }
1987 
1988  /** \brief Returns reference on the allocator
1989  */
1991 
1992  /** \brief Returns allocator
1993  */
1995 
1996 
1997  /// if tree of blocks already up
1998  bool is_init() const BMNOEXCEPT { return top_blocks_ != 0; }
1999 
2000  // ----------------------------------------------------------------
2001 
2002  /// allocate first level of descr. of blocks
2003  void init_tree()
2004  {
2005  // not clear why but GCC reports "maybe uninit" for top_blocks_ in -O3
2006  // all attempts to do a different fix failed, supressed for now...
2007 #if defined(__GNUG__)
2008  #if defined( __has_warning )
2009  #if __has_warning("-Wmaybe-uninitialized")
2010  #define BM_SUPPRESSING
2011  #endif
2012  #else
2013  #define BM_SUPPRESSING
2014  #endif
2015  #ifdef BM_SUPPRESSING
2016  #pragma GCC diagnostic push
2017  #pragma GCC diagnostic ignored "-Wmaybe-uninitialized"
2018  #endif
2019 #endif
2020  if(top_blocks_ != 0)
2021  return;
2022 #ifdef BM_SUPPRESSING
2023 #pragma GCC diagnostic pop
2024 #undef BM_SUPPRESSING
2025 #endif
2026  if (top_block_size_)
2027  {
2028  top_blocks_ = (bm::word_t***) alloc_.alloc_ptr(top_block_size_);
2029  ::memset(top_blocks_, 0, top_block_size_ * sizeof(bm::word_t**));
2030  return;
2031  }
2032  top_blocks_ = 0;
2033  }
2034 
2035  /// allocate first level of descr. of blocks
2036  void init_tree(unsigned top_size)
2037  {
2038  BM_ASSERT(top_blocks_ == 0);
2039  if (top_size > top_block_size_)
2040  top_block_size_ = top_size;
2041  init_tree();
2042  }
2043 
2044  // ----------------------------------------------------------------
2045  #define BM_FREE_OP(x) blk = blk_blk[j + x]; \
2046  if (IS_VALID_ADDR(blk)) \
2047  { \
2048  if (BM_IS_GAP(blk)) \
2049  alloc_.free_gap_block(BMGAP_PTR(blk), glen()); \
2050  else \
2051  alloc_.free_bit_block(blk); \
2052  }
2053 
2054  void deallocate_top_subblock(unsigned nblk_blk) BMNOEXCEPT
2055  {
2056  if (!top_blocks_[nblk_blk])
2057  return;
2058  bm::word_t** blk_blk = top_blocks_[nblk_blk];
2059  if ((bm::word_t*)blk_blk == FULL_BLOCK_FAKE_ADDR)
2060  {
2061  top_blocks_[nblk_blk] = 0;
2062  return;
2063  }
2064  unsigned j = 0; bm::word_t* blk;
2065  do
2066  {
2067  #if defined(BM64_AVX2) || defined(BM64_AVX512)
2068  if (!avx2_test_all_zero_wave(blk_blk + j))
2069  {
2070  BM_FREE_OP(0)
2071  BM_FREE_OP(1)
2072  BM_FREE_OP(2)
2073  BM_FREE_OP(3)
2074  }
2075  j += 4;
2076  #elif defined(BM64_SSE4)
2077  if (!sse42_test_all_zero_wave(blk_blk + j))
2078  {
2079  BM_FREE_OP(0)
2080  BM_FREE_OP(1)
2081  }
2082  j += 2;
2083  #else
2084  BM_FREE_OP(0)
2085  ++j;
2086  #endif
2087  } while (j < bm::set_sub_array_size);
2088 
2089  alloc_.free_ptr(top_blocks_[nblk_blk], bm::set_sub_array_size);
2090  top_blocks_[nblk_blk] = 0;
2091  }
2092 
2093  /** destroy tree, free memory in all blocks and control structures
2094  Note: pointers are NOT assigned to zero(!)
2095  */
2097  {
2098  BM_ASSERT(!arena_); // arena must be NULL here
2099 
2100  if (!top_blocks_)
2101  return;
2102 
2103  unsigned top_blocks = top_block_size();
2104  for (unsigned i = 0; i < top_blocks; )
2105  {
2106  bm::word_t** blk_blk = top_blocks_[i];
2107  if (!blk_blk)
2108  {
2109  ++i; // look ahead
2110  bool found = bm::find_not_null_ptr(top_blocks_, i, top_blocks, &i);
2111  if (!found) // nothing to do
2112  break;
2113  blk_blk = top_blocks_[i];
2114  }
2115  if ((bm::word_t*)blk_blk != FULL_BLOCK_FAKE_ADDR)
2117  ++i;
2118  } // for i
2119 
2120  alloc_.free_ptr(top_blocks_, top_block_size_); // free the top
2121  }
2122  #undef BM_FREE_OP
2123 
2125  {
2126  if (arena_)
2127  destroy_arena();
2128  else
2129  destroy_tree();
2130  top_blocks_ = 0; top_block_size_ = 0;
2131  }
2132 
2133  // ----------------------------------------------------------------
2134 
2135  /// calculate top blocks which are not NULL and not FULL
2137  {
2138  unsigned cnt = 0;
2139  unsigned top_blocks = top_block_size();
2140  // TODO: SIMD
2141  for (unsigned i = 0; i < top_blocks; ++i)
2142  {
2143  bm::word_t** blk_blk = top_blocks_[i];
2144  if (!blk_blk || ((bm::word_t*)blk_blk == FULL_BLOCK_FAKE_ADDR))
2145  continue;
2146  ++cnt;
2147  } // for i
2148  return cnt;
2149  }
2150 
2151  // ----------------------------------------------------------------
2152 
2153  /// calculate max top blocks size whithout NULL-tail
2155  {
2156  unsigned top_blocks = top_block_size();
2157  if (!top_blocks)
2158  return 0;
2159  unsigned i = top_blocks - 1;
2160  for (; i > 0; --i)
2161  {
2162  bm::word_t** blk_blk = top_blocks_[i];
2163  if (blk_blk)
2164  break;
2165  } // for i
2166  return i+1;
2167  }
2168 
2169  // ----------------------------------------------------------------
2170 
2172  {
2173  BM_ASSERT(i < top_block_size());
2174  bm::word_t** blk_blk = top_blocks_[i];
2175  // TODO: SIMD or unroll
2176  for (unsigned j = 0; j < bm::set_sub_array_size; ++j)
2177  {
2178  if (blk_blk[j])
2179  return;
2180  } // for j
2181  alloc_.free_ptr(blk_blk, bm::set_sub_array_size);
2182  top_blocks_[i] = 0;
2183  }
2184 
2185  // ----------------------------------------------------------------
2186 
2188  {
2189  BM_ASSERT(i < top_block_size());
2190  bm::word_t** blk_blk = top_blocks_[i];
2191  // TODO: SIMD
2192  for (unsigned j = 0; j < bm::set_sub_array_size; ++j)
2193  {
2194  if (blk_blk[j] != FULL_BLOCK_FAKE_ADDR)
2195  return;
2196  } // for j
2197  alloc_.free_ptr(blk_blk, bm::set_sub_array_size);
2199  }
2200 
2201  /**
2202  Calculate approximate memory needed to serialize big runs
2203  of 0000s and 111s (as blocks)
2204  */
2206  {
2207  size_t s_size = sizeof(unsigned);
2208  if (!top_blocks_)
2209  return s_size;
2210  block_idx_type nb_empty = 0;
2211  block_idx_type nb_full = 0;
2212  unsigned top_blocks = top_block_size();
2213  for (unsigned i = 0; i < top_blocks; )
2214  {
2215  bm::word_t** blk_blk = top_blocks_[i];
2216  if (!blk_blk)
2217  {
2218  s_size += nb_full ? 1+sizeof(block_idx_type) : 0; nb_full = 0;
2219  nb_empty += bm::set_sub_array_size;
2220 
2221  unsigned nb_prev = i++;
2222  bool found = bm::find_not_null_ptr(top_blocks_, i, top_blocks, &i);
2223  BM_ASSERT(i >= nb_prev);
2224  if (!found)
2225  {
2226  nb_empty = 0;
2227  break;
2228  }
2229  nb_empty += (i - nb_prev) * bm::set_sub_array_size;
2230  blk_blk = top_blocks_[i];
2231  BM_ASSERT(blk_blk);
2232  if (!blk_blk)
2233  break;
2234  }
2235  if ((bm::word_t*)blk_blk == FULL_BLOCK_FAKE_ADDR)
2236  {
2237  s_size += nb_empty ? 1+sizeof(block_idx_type) : 0; nb_empty = 0;
2238  nb_full += bm::set_sub_array_size;
2239  ++i;
2240  continue;
2241  }
2242  unsigned j = 0; bm::word_t* blk;
2243  do
2244  {
2245  blk = blk_blk[j];
2246  if (!blk)
2247  {
2248  s_size += nb_full ? 1+sizeof(block_idx_type) : 0; nb_full = 0;
2249  ++nb_empty;
2250  }
2251  else
2252  if (blk == FULL_BLOCK_FAKE_ADDR)
2253  {
2254  s_size += nb_empty ? 1+sizeof(block_idx_type) : 0; nb_empty = 0;
2255  ++nb_full;
2256  }
2257  else // real block (not 000 and not 0xFFF)
2258  {
2259  s_size += nb_empty ? 1+sizeof(block_idx_type) : 0; nb_empty = 0;
2260  s_size += nb_full ? 1+sizeof(block_idx_type) : 0; nb_full = 0;
2261  }
2262  } while (++j < bm::set_sub_array_size);
2263 
2264  ++i;
2265  } // for i
2266  s_size += nb_empty ? 1+sizeof(block_idx_type) : 0;
2267  s_size += nb_full ? 1+sizeof(block_idx_type) : 0;
2268  return s_size;
2269  }
2270 
2271  // ----------------------------------------------------------------
2272 
2273  void optimize_block(unsigned i, unsigned j,
2274  bm::word_t* block,
2275  bm::word_t* temp_block,
2276  int opt_mode,
2277  bv_statistics* bv_stat)
2278  {
2279  if (!IS_VALID_ADDR(block))
2280  return;
2281 
2282  if (BM_IS_GAP(block)) // gap block
2283  {
2284  gap_word_t* gap_blk = BMGAP_PTR(block);
2285  if (bm::gap_is_all_zero(gap_blk))
2286  {
2287  set_block_ptr(i, j, 0);
2288  alloc_.free_gap_block(gap_blk, glen());
2289  }
2290  else
2291  if (bm::gap_is_all_one(gap_blk))
2292  {
2294  alloc_.free_gap_block(gap_blk, glen());
2295  }
2296  else
2297  {
2298  // try to shrink the GAP block
2299  //
2300  unsigned len = bm::gap_length(gap_blk);
2301  int old_level = bm::gap_level(gap_blk);
2302  int new_level = bm::gap_calc_level(len, glen());
2303  if (new_level >= 0 && new_level < old_level) // can shrink
2304  {
2305  gap_word_t* new_gap_blk =
2306  allocate_gap_block(unsigned(new_level), gap_blk);
2307  bm::word_t* blk = (bm::word_t*)BMPTR_SETBIT0(new_gap_blk);
2308  set_block_ptr(i, j, blk);
2309  alloc_.free_gap_block(gap_blk, glen());
2310  gap_blk = new_gap_blk;
2311  }
2312 
2313  if (bv_stat)
2314  {
2315  unsigned level = bm::gap_level(gap_blk);
2316  bv_stat->add_gap_block(
2317  bm::gap_capacity(gap_blk, glen()), len, level);
2318  }
2319  }
2320  }
2321  else // bit-block
2322  {
2323  // evaluate bit-block complexity
2324  unsigned gap_count = bm::bit_block_calc_change(block);
2325  if (gap_count == 1) // all-zero OR all-one block
2326  {
2327  if ((block[0] & 1u)) // all-ONE
2328  {
2330  get_allocator().free_bit_block(block);
2331  block = FULL_BLOCK_FAKE_ADDR;
2332  }
2333  else // empty block
2334  {
2336  get_allocator().free_bit_block(block);
2337  block = 0;
2338  }
2339  set_block_ptr(i, j, block);
2340  return;
2341  }
2342  if (opt_mode < 3) // free_01 optimization
2343  {
2344  if (bv_stat)
2345  bv_stat->add_bit_block();
2346  return;
2347  }
2348  // try to compress
2349  //
2350  gap_word_t* tmp_gap_blk = (bm::gap_word_t*)temp_block;
2351  *tmp_gap_blk = bm::gap_max_level << 1;
2352  unsigned threashold = glen(bm::gap_max_level)-4;
2353  unsigned len = 0;
2354  if (gap_count < threashold)
2355  {
2356  len = bm::bit_to_gap(tmp_gap_blk, block, threashold);
2357  BM_ASSERT(len);
2358  }
2359  if (len) // GAP compression successful
2360  {
2361  get_allocator().free_bit_block(block);
2362  // check if new gap block can be eliminated
2363  BM_ASSERT(!(bm::gap_is_all_zero(tmp_gap_blk)
2364  || bm::gap_is_all_one(tmp_gap_blk)));
2365 
2366  int level = bm::gap_calc_level(len, glen());
2367  BM_ASSERT(level >= 0);
2368  gap_word_t* gap_blk =
2369  allocate_gap_block(unsigned(level), tmp_gap_blk);
2370  bm::word_t* blk = (bm::word_t*)BMPTR_SETBIT0(gap_blk);
2371  set_block_ptr(i, j, blk);
2372  if (bv_stat)
2373  {
2374  level = bm::gap_level(gap_blk);
2375  bv_stat->add_gap_block(
2376  bm::gap_capacity(gap_blk, glen()),
2377  bm::gap_length(gap_blk), unsigned(level));
2378  }
2379  }
2380  else // non-compressable bit-block
2381  {
2382  if (bv_stat)
2383  bv_stat->add_bit_block();
2384  }
2385  } // bit-block
2386  }
2387 
2388  // ----------------------------------------------------------------
2389 
2390  void optimize_tree(bm::word_t* temp_block, int opt_mode,
2391  bv_statistics* bv_stat)
2392  {
2393  if (!top_blocks_)
2394  return;
2395 
2396  unsigned top_blocks = top_block_size();
2397  for (unsigned i = 0; i < top_blocks; ++i)
2398  {
2399  bm::word_t** blk_blk = top_blocks_[i];
2400  if (!blk_blk)
2401  {
2402  ++i;
2403  bool found = bm::find_not_null_ptr(top_blocks_, i, top_blocks, &i);
2404  if (!found)
2405  break;
2406  blk_blk = top_blocks_[i];
2407  }
2408  if ((bm::word_t*)blk_blk == FULL_BLOCK_FAKE_ADDR)
2409  continue;
2410 
2411  for (unsigned j = 0; j < bm::set_sub_array_size; ++j)
2412  {
2413  optimize_block(i, j, blk_blk[j], temp_block, opt_mode, bv_stat);
2414  }
2415 
2416  // optimize the top level
2417  //
2418  if (blk_blk[0] == FULL_BLOCK_FAKE_ADDR)
2420  else
2421  if (!blk_blk[0])
2423 
2424  blk_blk = top_blocks_[i];
2425  if (!blk_blk || (bm::word_t*)blk_blk == FULL_BLOCK_FAKE_ADDR)
2426  {}
2427  else
2428  {
2429  if (bv_stat)
2430  bv_stat->ptr_sub_blocks++;
2431  }
2432  } // for i
2433 
2434  if (bv_stat)
2435  {
2436  size_t full_null_size = calc_serialization_null_full();
2437  bv_stat->max_serialize_mem += full_null_size;
2438  }
2439  }
2440 
2441  // ----------------------------------------------------------------
2442 
2443  void stat_correction(bv_statistics* stat) noexcept
2444  {
2445  BM_ASSERT(stat);
2446 
2447  size_t safe_inc = stat->max_serialize_mem / 10; // 10% increment
2448  if (!safe_inc) safe_inc = 256;
2449  stat->max_serialize_mem += safe_inc;
2450 
2451  unsigned top_size = top_block_size();
2452  size_t blocks_mem = sizeof(*this);
2453  blocks_mem += sizeof(bm::word_t**) * top_size;
2454  blocks_mem += stat->ptr_sub_blocks * (sizeof(void*) * bm::set_sub_array_size);
2455  stat->memory_used += blocks_mem;
2456  stat->bv_count = 1;
2457  }
2458 
2459 
2460 
2461  // -----------------------------------------------------------------------
2462 
2463  /*!
2464  @brief Calculates bitvector arena statistics.
2465  */
2467  {
2468  BM_ASSERT(st);
2469 
2470  st->reset();
2471  const bm::word_t* const * const* blk_root = top_blocks_root();
2472 
2473  if (!blk_root)
2474  return;
2475  unsigned top_size = st->top_block_size = top_block_size();
2476  for (unsigned i = 0; i < top_size; ++i)
2477  {
2478  const bm::word_t* const* blk_blk = blk_root[i];
2479  if (!blk_blk)
2480  {
2481  ++i;
2482  bool found = bm::find_not_null_ptr(blk_root, i, top_size, &i);
2483  if (!found)
2484  break;
2485  blk_blk = blk_root[i];
2486  BM_ASSERT(blk_blk);
2487  if (!blk_blk)
2488  break;
2489  }
2490  if ((bm::word_t*)blk_blk == FULL_BLOCK_FAKE_ADDR)
2491  continue;
2492  st->ptr_sub_blocks_sz += bm::set_sub_array_size;
2493  for (unsigned j = 0; j < bm::set_sub_array_size; ++j)
2494  {
2495  const bm::word_t* blk = blk_blk[j];
2496  if (IS_VALID_ADDR(blk))
2497  {
2498  if (BM_IS_GAP(blk))
2499  {
2500  const bm::gap_word_t* gap_blk = BMGAP_PTR(blk);
2501  unsigned len = bm::gap_length(gap_blk);
2502  BM_ASSERT(gap_blk[len-1] == 65535);
2503  st->gap_blocks_sz += len;
2504  }
2505  else // bit block
2506  st->bit_blocks_sz += bm::set_block_size;
2507  }
2508  } // for j
2509  } // for i
2510 
2511  }
2512 
2513  /**
2514  Arena allocation memory guard
2515  @internal
2516  */
2518  {
2519  arena_guard(arena* ar, blocks_manager& bman) noexcept
2520  : ar_(ar), bman_(bman)
2521  {}
2522  ~arena_guard() noexcept
2523  {
2524  if (ar_)
2525  {
2527  ::free(ar_);
2528  }
2529  }
2530  void release() noexcept { ar_ = 0; }
2531 
2534  };
2535 
2536  /// calculate arena statistics, calculate and copy all blocks there
2537  ///
2538  void copy_to_arena(const blocks_manager& bman)
2539  {
2540  BM_ASSERT(arena_ == 0 && top_blocks_ == 0);
2541 
2542  bm::bv_arena_statistics src_arena_st;
2543  if (bman.arena_)
2544  src_arena_st = bman.arena_->st_;
2545  else
2546  bman.calc_arena_stat(&src_arena_st);
2547 
2548  arena* ar = (arena*)::malloc(sizeof(arena));
2549  if (!ar)
2550  {
2551  #ifndef BM_NO_STL
2552  throw std::bad_alloc();
2553  #else
2554  BM_THROW(BM_ERR_BADALLOC);
2555  #endif
2556  }
2557  ar->reset();
2558  arena_guard aguard(ar, *this); // alloc_arena can throw an exception..
2559 
2560  alloc_arena(ar, src_arena_st, get_allocator());
2561  bman.copy_to_arena(ar);
2562  arena_ = ar;
2563  aguard.release(); // ownership of arena is transfered
2564 
2565  // reset the top tree link to work with the arena
2566  top_blocks_ = ar->top_blocks_;
2568  }
2569 
2570 
2571  // ----------------------------------------------------------------
2572 
2573  /// Allocate arena (content memory) based on arena statistics
2574  ///
2575  /// @param ar - arena pointer to allocate its buffers
2576  /// @param st - arena statistics (should be calculated for the same vector
2577  /// @para alloc - allocator
2578  ///
2579  static
2581  allocator_type& alloc)
2582  {
2583  BM_ASSERT(ar);
2584  ar->st_ = st;
2585 
2586  // compute total allocation size in bytes
2587  size_t alloc_sz = st.get_alloc_size();
2588  // size to alloc in pointers
2589  size_t alloc_sz_v = (alloc_sz + (sizeof(void*)-1)) / sizeof(void*);
2590 
2591  char* arena_mem_ptr = (char*) alloc.alloc_ptr(alloc_sz_v);
2592  ar->a_ptr_ = arena_mem_ptr;
2593 
2594  if (st.bit_blocks_sz)
2595  {
2596  ar->blocks_ = (bm::word_t*)arena_mem_ptr;
2598  arena_mem_ptr += st.bit_blocks_sz * sizeof(bm::word_t);
2599  }
2600  else
2601  ar->blocks_ = 0;
2602 
2603  ar->top_blocks_ = (bm::word_t***) arena_mem_ptr;
2604  for (unsigned i = 0; i < ar->st_.top_block_size; ++i) // init as NULLs
2605  ar->top_blocks_[i] = 0;
2606  arena_mem_ptr += st.top_block_size * sizeof(void*);
2607 
2608  if (st.ptr_sub_blocks_sz)
2609  {
2610  ar->blk_blks_ = (bm::word_t**) arena_mem_ptr;
2611  arena_mem_ptr += st.ptr_sub_blocks_sz * sizeof(void*);
2612  }
2613  else
2614  ar->blk_blks_ = 0;
2615 
2616  if (st.gap_blocks_sz)
2617  ar->gap_blocks_ = (bm::gap_word_t*)arena_mem_ptr;
2618  else
2619  ar->gap_blocks_ = 0;
2620  }
2621 
2622  // ----------------------------------------------------------------
2623 
2624  /// Free arena (content memory) based on arena statistics
2625  /// @param ar - arena pointer to free its buffers
2626  /// @param alloc - allocator
2627  ///
2628  static
2630  {
2631  BM_ASSERT(ar);
2632  if (ar->a_ptr_)
2633  {
2634  size_t alloc_sz = ar->st_.get_alloc_size();
2635  // size to alloc in pointers
2636  size_t alloc_sz_v = (alloc_sz + (sizeof(void*)-1)) / sizeof(void*);
2637  alloc.free_ptr(ar->a_ptr_, alloc_sz_v);
2638  }
2639  }
2640 
2641  // ----------------------------------------------------------------
2642  /// free all arena memory
2643  ///
2645  {
2648  }
2649 
2650  // ----------------------------------------------------------------
2651 
2652  /**
2653  Copy blocks into arena allocated memory
2654  @param ar - target allocated arena
2655  @param arena_st - arena allocation statistics
2656  @sa alloc_arena
2657  */
2659  {
2660  BM_ASSERT(ar);
2661 
2662  bm::bv_arena_statistics& st = ar->st_; (void) st;
2663  bm::bv_arena_statistics arena_st;
2664  arena_st.reset();
2665 
2666  bm::word_t*** blk_root = ar->top_blocks_;
2667  const bm::word_t* const * const * blk_root_arg = top_blocks_root();
2668  BM_ASSERT (blk_root_arg);
2669 
2670  // arena target pointers
2671  bm::word_t** t_blk_blk = ar->blk_blks_;
2672  bm::word_t* t_block = ar->blocks_;
2673  bm::gap_word_t* t_gap_block = ar->gap_blocks_;
2674 
2675  unsigned top_size = top_block_size();
2676  for (unsigned i = 0; i < top_size; ++i)
2677  {
2678  const bm::word_t* const* blk_blk_arg = blk_root_arg[i];
2679  if (!blk_blk_arg)
2680  {
2681  ++i;
2682  bool found = bm::find_not_null_ptr(blk_root_arg, i, top_size, &i);
2683  if (!found)
2684  break;
2685  blk_blk_arg = blk_root_arg[i];
2686  BM_ASSERT(blk_blk_arg);
2687  if (!blk_blk_arg)
2688  break;
2689  }
2690  if ((bm::word_t*)blk_blk_arg == FULL_BLOCK_FAKE_ADDR)
2691  {
2692  blk_root[i] = (bm::word_t**)FULL_BLOCK_FAKE_ADDR;
2693  continue;
2694  }
2695 
2696  blk_root[i] = t_blk_blk;
2697  for (unsigned j = 0; j < bm::set_sub_array_size; ++j)
2698  {
2699  const bm::word_t* blk = blk_blk_arg[j];
2700  t_blk_blk[j] = (bm::word_t*)blk; // copy FULL and NULL blocks
2701  if (!IS_VALID_ADDR(blk))
2702  continue;
2703 
2704  if (BM_IS_GAP(blk))
2705  {
2706  const bm::gap_word_t* gap_blk = BMGAP_PTR(blk);
2707  unsigned len = bm::gap_length(gap_blk);
2708  BM_ASSERT(gap_blk[len-1] == 65535);
2709 
2710  ::memcpy(t_gap_block, gap_blk, len * sizeof(bm::gap_word_t));
2711  bm::word_t* blk_p = (bm::word_t*) t_gap_block;
2712  BMSET_PTRGAP(blk_p);
2713  t_blk_blk[j] = blk_p;
2714  t_gap_block += len;
2715 
2716  arena_st.gap_blocks_sz += len;
2717  BM_ASSERT(st.gap_blocks_sz >= arena_st.gap_blocks_sz);
2718  }
2719  else // bit block
2720  {
2721  bm::bit_block_copy(t_block, blk);
2722  t_blk_blk[j] = t_block;
2723  t_block += bm::set_block_size;
2724 
2725  arena_st.bit_blocks_sz += bm::set_block_size;
2726  BM_ASSERT(st.bit_blocks_sz >= arena_st.bit_blocks_sz);
2727  }
2728 
2729  } // for j
2730 
2731  t_blk_blk += bm::set_sub_array_size;
2734 
2735  } // for i
2736 
2737  }
2738 
2739 
2740 private:
2741 
2743 
2744  void copy(const blocks_manager& blockman,
2745  block_idx_type block_from = 0,
2747  {
2748  BM_ASSERT(!arena_);
2749  bm::word_t*** blk_root_arg = blockman.top_blocks_root();
2750  if (!blk_root_arg)
2751  return;
2752 
2753  unsigned arg_top_blocks = blockman.top_block_size();
2754  {
2755  block_idx_type need_top_blocks = 1 + (block_to / 256);
2756  if (need_top_blocks < arg_top_blocks)
2757  arg_top_blocks = unsigned(need_top_blocks);
2758  }
2759 
2760  this->reserve_top_blocks(arg_top_blocks);
2761  bm::word_t*** blk_root = top_blocks_root();
2762 
2763 
2764  unsigned i_from, j_from, i_to, j_to;
2765  get_block_coord(block_from, i_from, j_from);
2766  get_block_coord(block_to, i_to, j_to);
2767 
2768  if (i_to >= arg_top_blocks-1)
2769  {
2770  i_to = arg_top_blocks-1;
2771  j_to = bm::set_sub_array_size-1;
2772  }
2773 
2774  for (unsigned i = i_from; i <= i_to; ++i)
2775  {
2776  bm::word_t** blk_blk_arg = blk_root_arg[i];
2777  if (!blk_blk_arg)
2778  continue;
2779  if ((bm::word_t*)blk_blk_arg == FULL_BLOCK_FAKE_ADDR)
2780  {
2781  BM_ASSERT(!blk_root[i]);
2782  if (i < i_to)
2783  {
2784  unsigned j = (i == i_from) ? j_from : 0;
2785  if (!j)
2786  {
2787  blk_root[i] = blk_blk_arg;
2788  continue;
2789  }
2790  }
2791  blk_blk_arg = FULL_SUB_BLOCK_REAL_ADDR;
2792  }
2793 
2794  BM_ASSERT(blk_root[i] == 0);
2795 
2796  bm::word_t** blk_blk = blk_root[i] = (bm::word_t**)alloc_.alloc_ptr(bm::set_sub_array_size);
2797  ::memset(blk_blk, 0, bm::set_sub_array_size * sizeof(bm::word_t*));
2798 
2799  unsigned j = (i == i_from) ? j_from : 0;
2800  unsigned j_limit = (i == i_to) ? j_to+1 : bm::set_sub_array_size;
2801  bm::word_t* blk;
2802  const bm::word_t* blk_arg;
2803  do
2804  {
2805  blk = blk_blk[j]; blk_arg = blk_blk_arg[j];
2806  if (blk_arg)
2807  {
2808  bool is_gap = BM_IS_GAP(blk_arg);
2809  if (is_gap)
2810  {
2811  blk = clone_gap_block(BMGAP_PTR(blk_arg), is_gap);
2812  if (is_gap)
2813  BMSET_PTRGAP(blk);
2814  }
2815  else
2816  {
2817  if (blk_arg == FULL_BLOCK_FAKE_ADDR)
2818  blk = FULL_BLOCK_FAKE_ADDR;
2819  else
2820  {
2821  BM_ASSERT(!IS_FULL_BLOCK(blk_arg));
2822  blk = alloc_.alloc_bit_block();
2823  bm::bit_block_copy(blk, blk_arg);
2824  }
2825  }
2826  blk_blk[j] = blk;
2827  }
2828  ++j;
2829  } while (j < j_limit);
2830  } // for i
2831  }
2832 
2833 private:
2834  /// maximum addresable bits
2836  /// Tree of blocks.
2838  /// Size of the top level block array in blocks_ tree
2840  /// Temp block.
2842  /// vector defines gap block lengths for different levels
2844  /// allocator
2846  /// memory arena pointer
2848 };
2849 
2850 /**
2851  Bit block buffer guard
2852  \internal
2853 */
2854 template<class BlocksManager>
2856 {
2857 public:
2858  bit_block_guard(BlocksManager& bman, bm::word_t* blk=0) BMNOEXCEPT
2859  : bman_(bman),
2860  block_(blk)
2861  {}
2863  {
2864  if (IS_VALID_ADDR(block_))
2865  bman_.get_allocator().free_bit_block(block_, 3);
2866  }
2867 
2869  {
2870  if (IS_VALID_ADDR(block_))
2871  bman_.get_allocator().free_bit_block(block_);
2872  block_ = blk;
2873  }
2874 
2876  {
2877  attach(bman_.get_allocator().alloc_bit_block(3));
2878  return block_;
2879  }
2881 
2882 private:
2885 private:
2886  BlocksManager& bman_;
2888 };
2889 
2890 /*!
2891  Resource guard for PCLASS::set_allocator_pool()
2892  @ingroup bvector
2893  @internal
2894 */
2895 template<typename POOL, typename PCLASS>
2897 {
2898 public:
2900  {}
2901 
2902  alloc_pool_guard(POOL& pool, PCLASS& obj) BMNOEXCEPT
2903  : optr_(&obj)
2904  {
2905  obj.set_allocator_pool(&pool);
2906  }
2908  {
2909  if (optr_)
2910  optr_->set_allocator_pool(0);
2911  }
2912 
2913  /// check if vector has no assigned allocator and set one
2914  void assign_if_not_set(POOL& pool,
2915  PCLASS& obj) BMNOEXCEPT
2916  {
2917  if (!obj.get_allocator_pool()) // alloc pool not set yet
2918  {
2919  BM_ASSERT(!optr_);
2920  optr_ = &obj;
2921  optr_->set_allocator_pool(&pool);
2922  }
2923  }
2924 
2925 private:
2927  void operator=(const alloc_pool_guard&) = delete;
2928 private:
2929  PCLASS* optr_; ///< garded object
2930 };
2931 
2932 
2933 
2934 }
2935 
2936 #ifdef _MSC_VER
2937 #pragma warning( pop )
2938 #endif
2939 
2940 #endif
2941 
static void * Alloc(size_t size)
Definition: asntypes.cpp:59
#define BM_FREE_OP(x)
Definition: bmblocks.h:2045
#define IS_FULL_BLOCK(addr)
Definition: bmdef.h:162
#define IS_VALID_ADDR(addr)
Definition: bmdef.h:161
#define BMNOEXCEPT
Definition: bmdef.h:82
#define BMPTR_SETBIT0(ptr)
Definition: bmdef.h:177
#define BMGAP_PTR(ptr)
Definition: bmdef.h:189
#define BM_IS_GAP(ptr)
Definition: bmdef.h:191
#define BMFORCEINLINE
Definition: bmdef.h:213
#define BMSET_PTRGAP(ptr)
Definition: bmdef.h:190
#define BM_ASSERT
Definition: bmdef.h:139
#define BMPTR_CLEARBIT0(ptr)
Definition: bmdef.h:178
#define FULL_BLOCK_FAKE_ADDR
Definition: bmdef.h:158
#define FULL_SUB_BLOCK_REAL_ADDR
Definition: bmdef.h:159
#define FULL_BLOCK_REAL_ADDR
Definition: bmdef.h:157
Forward declarations.
void assign_if_not_set(POOL &pool, PCLASS &obj) BMNOEXCEPT
check if vector has no assigned allocator and set one
Definition: bmblocks.h:2914
PCLASS * optr_
garded object
Definition: bmblocks.h:2929
void operator=(const alloc_pool_guard &)=delete
alloc_pool_guard(const alloc_pool_guard &)=delete
~alloc_pool_guard() BMNOEXCEPT
Definition: bmblocks.h:2907
alloc_pool_guard() BMNOEXCEPT
Definition: bmblocks.h:2899
alloc_pool_guard(POOL &pool, PCLASS &obj) BMNOEXCEPT
Definition: bmblocks.h:2902
Bit block buffer guard.
Definition: bmblocks.h:2856
bm::word_t * get() BMNOEXCEPT
Definition: bmblocks.h:2880
bit_block_guard & operator=(const bit_block_guard &)
bm::word_t * block_
Definition: bmblocks.h:2887
bm::word_t * allocate()
Definition: bmblocks.h:2875
BlocksManager & bman_
Definition: bmblocks.h:2886
bit_block_guard(const bit_block_guard &)
bit_block_guard(BlocksManager &bman, bm::word_t *blk=0) BMNOEXCEPT
Definition: bmblocks.h:2858
void attach(bm::word_t *blk) BMNOEXCEPT
Definition: bmblocks.h:2868
Functor detects if any bit set.
Definition: bmblocks.h:250
block_any_func(const blocks_manager &bm) BMNOEXCEPT
Definition: bmblocks.h:254
Bitcounting functor filling the block counts array.
Definition: bmblocks.h:150
void operator()(const bm::word_t *block, id_type idx) BMNOEXCEPT
Definition: bmblocks.h:160
void on_non_empty_top(unsigned) BMNOEXCEPT
Definition: bmblocks.h:169
id_type last_block() const BMNOEXCEPT
Definition: bmblocks.h:168
block_count_arr_func(const blocks_manager &bm, unsigned *arr) BMNOEXCEPT
Definition: bmblocks.h:154
Base class for bitcounting functors.
Definition: bmblocks.h:113
bm::id_t block_count(const bm::word_t *block) const BMNOEXCEPT
Definition: bmblocks.h:118
block_count_base(const blocks_manager &bm) BMNOEXCEPT
Definition: bmblocks.h:115
bit value change counting functor
Definition: bmblocks.h:178
block_count_change_func(const blocks_manager &bm) BMNOEXCEPT
Definition: bmblocks.h:182
id_type count() const BMNOEXCEPT
Definition: bmblocks.h:235
void operator()(const bm::word_t *block, block_idx_type idx) BMNOEXCEPT
Definition: bmblocks.h:237
block_idx_type block_count(const bm::word_t *block, block_idx_type idx) BMNOEXCEPT
Definition: bmblocks.h:188
id_type count() const BMNOEXCEPT
Definition: bmblocks.h:134
void operator()(const bm::word_t *block) BMNOEXCEPT
Definition: bmblocks.h:136
void add_full(id_type c) BMNOEXCEPT
Definition: bmblocks.h:140
block_count_func(const blocks_manager &bm) BMNOEXCEPT
Definition: bmblocks.h:131
Fill block with all-one bits functor.
Definition: bmblocks.h:332
void operator()(bm::word_t *block, block_idx_type idx)
Definition: bmblocks.h:336
block_one_func(blocks_manager &bm) BMNOEXCEPT
Definition: bmblocks.h:334
Base functor class connected for "constant" functors.
Definition: bmblocks.h:96
void on_empty_block(block_idx_type) BMNOEXCEPT
Definition: bmblocks.h:102
bm_func_base_const(const blocks_manager &bman) BMNOEXCEPT
Definition: bmblocks.h:99
bm_func_base_const & operator=(const bm_func_base_const &) BMNOEXCEPT
bm_func_base_const(const bm_func_base_const &) BMNOEXCEPT
void on_empty_top(unsigned) BMNOEXCEPT
Definition: bmblocks.h:101
const blocks_manager & bm_
Definition: bmblocks.h:107
Base functor class (block visitor)
Definition: bmblocks.h:78
void on_empty_top(unsigned) BMNOEXCEPT
Definition: bmblocks.h:84
bm_func_base(blocks_manager &bman) BMNOEXCEPT
Definition: bmblocks.h:82
bm_func_base(const bm_func_base &)
bm_func_base & operator=(const bm_func_base &)
void on_empty_block(block_idx_type) BMNOEXCEPT
Definition: bmblocks.h:85
const gap_word_t * glevel_len_
Definition: bmblocks.h:327
gap_level_func(blocks_manager &bm, const gap_word_t *glevel_len) BMNOEXCEPT
Definition: bmblocks.h:273
void operator()(bm::word_t *block, block_idx_type idx)
Definition: bmblocks.h:280
bitvector blocks manager Embedded class managing bit-blocks on very low level. Includes number of fun...
Definition: bmblocks.h:42
unsigned top_block_size_
Size of the top level block array in blocks_ tree.
Definition: bmblocks.h:2839
void set_glen(const gap_word_t *glevel_len) BMNOEXCEPT
Definition: bmblocks.h:1861
bool is_sparse_sblock(unsigned i, unsigned sparse_cut_off) const BMNOEXCEPT
Bit count all blocks to determine if it is very sparse.
Definition: bmblocks.h:1713
void zero_block(unsigned i, unsigned j) BMNOEXCEPT
Free block, make it zero pointer in the tree.
Definition: bmblocks.h:1635
void set_all_zero(block_idx_type nb, block_idx_type nb_to) BMNOEXCEPT
set all-Zero block pointers for [start..end]
Definition: bmblocks.h:709
bm::word_t *** top_blocks_
Tree of blocks.
Definition: bmblocks.h:2837
arena * arena_
memory arena pointer
Definition: bmblocks.h:2847
void assign_gap(unsigned i, unsigned j, const bm::gap_word_t *res, unsigned res_len, bm::word_t *blk, gap_word_t *tmp_buf)
Attach the result of a GAP logical operation.
Definition: bmblocks.h:981
bm::word_t * get_block_ptr(unsigned i, unsigned j) BMNOEXCEPT
Finds block in 2-level blocks array (unsinitized)
Definition: bmblocks.h:571
void set_block_all_set(block_idx_type nb)
Definition: bmblocks.h:602
bm::word_t * check_allocate_tempblock()
Definition: bmblocks.h:1815
unsigned find_max_top_blocks() const BMNOEXCEPT
calculate max top blocks size whithout NULL-tail
Definition: bmblocks.h:2154
bm::word_t * deoptimize_block(block_idx_type nb)
Make sure block turns into true bit-block if it is GAP or a full block.
Definition: bmblocks.h:1562
gap_word_t glevel_len_[bm::gap_levels]
vector defines gap block lengths for different levels
Definition: bmblocks.h:2843
void return_tempblock(bm::word_t *block) BMNOEXCEPT
Definition: bmblocks.h:1849
void set_all_set(block_idx_type nb, block_idx_type nb_to)
set all-set block pointers for [start..end]
Definition: bmblocks.h:644
const bm::word_t *const * get_topblock(unsigned i) const BMNOEXCEPT
Function returns top-level block in 2-level blocks array.
Definition: bmblocks.h:587
id_type max_bits_
maximum addresable bits
Definition: bmblocks.h:2835
void validate_top_full(unsigned i) BMNOEXCEPT
Definition: bmblocks.h:2187
void shrink_top_blocks()
shrink unused top blocks array (via reallocation)
Definition: bmblocks.h:1965
allocator_type get_allocator() const BMNOEXCEPT
Returns allocator.
Definition: bmblocks.h:1994
blocks_manager(const gap_word_t *glevel_len, id_type max_bits, const Alloc &alloc=Alloc())
Definition: bmblocks.h:351
void copy_to_arena(arena *ar) const BMNOEXCEPT
Copy blocks into arena allocated memory.
Definition: bmblocks.h:2658
void init_tree(unsigned top_size)
allocate first level of descr. of blocks
Definition: bmblocks.h:2036
bm::word_t * alloc_bit_block(block_idx_type nb)
Create(allocate) bit block.
Definition: bmblocks.h:785
void destroy_arena() BMNOEXCEPT
free all arena memory
Definition: bmblocks.h:2644
bool is_subblock_null(unsigned nsub) const BMNOEXCEPT
Returns true if second level block pointer is 0.
Definition: bmblocks.h:1889
void move_from(blocks_manager &bm) BMNOEXCEPT
implementation of moving semantics
Definition: bmblocks.h:417
void set_block_all_set_ptr(unsigned i, unsigned j)
Places new block into blocks table.
Definition: bmblocks.h:631
static void alloc_arena(arena *ar, const bm::bv_arena_statistics &st, allocator_type &alloc)
Allocate arena (content memory) based on arena statistics.
Definition: bmblocks.h:2580
blocks_manager(blocks_manager &&blockman) BMNOEXCEPT
Definition: bmblocks.h:377
bm::gap_word_t * extend_gap_block(block_idx_type nb, gap_word_t *blk)
Extends GAP block to the next level or converts it to bit block.
Definition: bmblocks.h:1783
void assign_gap_check(unsigned i, unsigned j, const bm::gap_word_t *res, unsigned res_len, bm::word_t *blk, gap_word_t *tmp_buf)
Attach the result of a GAP logical operation but check if it is all 000.
Definition: bmblocks.h:958
bm::word_t ** check_alloc_top_subblock(unsigned nblk_blk)
Allocate top sub-block if not allocated.
Definition: bmblocks.h:1189
Alloc allocator_type
Definition: bmblocks.h:46
block_idx_type find_next_nz_block(block_idx_type nb, bool deep_scan=true) const BMNOEXCEPT
Find the next non-zero block starting from nb.
Definition: bmblocks.h:508
bm::word_t * temp_block_
Temp block.
Definition: bmblocks.h:2841
bm::word_t *** top_blocks_root() const BMNOEXCEPT
Returns root block in the tree.
Definition: bmblocks.h:595
void deinit_tree() BMNOEXCEPT
Definition: bmblocks.h:2124
const bm::word_t * get_block(block_idx_type nb, int *no_more_blocks) const BMNOEXCEPT
Returns current capacity (bits)
Definition: bmblocks.h:475
unsigned top_block_size() const BMNOEXCEPT
Returns size of the top block array in the tree.
Definition: bmblocks.h:1916
void destroy_tree() BMNOEXCEPT
destroy tree, free memory in all blocks and control structures Note: pointers are NOT assigned to zer...
Definition: bmblocks.h:2096
void free_temp_block() BMNOEXCEPT
Definition: bmblocks.h:1822
bm::word_t * copy_bit_block(block_idx_type nb, const bm::word_t *block_src, int is_src_gap)
Create bit block as a copy of source block (bit or gap).
Definition: bmblocks.h:813
size_t calc_serialization_null_full() const BMNOEXCEPT
Calculate approximate memory needed to serialize big runs of 0000s and 111s (as blocks)
Definition: bmblocks.h:2205
void free_top_subblock(unsigned nblk_blk) BMNOEXCEPT
Definition: bmblocks.h:1167
bm::word_t * check_allocate_block(block_idx_type nb, int initial_block_type)
Function checks if block is not yet allocated, allocates and returns.
Definition: bmblocks.h:1118
bm::word_t ** alloc_top_subblock(unsigned i, bm::word_t *addr)
Allocate subblock and fill based on.
Definition: bmblocks.h:1315
const bm::word_t * get_block_ptr(unsigned i, unsigned j) const BMNOEXCEPT
Finds block in 2-level blocks array (unsinitized)
Definition: bmblocks.h:556
bm::word_t * set_gap_block(block_idx_type nb, const gap_word_t *gap_block_src, int level)
Allocate an place new GAP block (copy of provided block)
Definition: bmblocks.h:1237
unsigned glen(unsigned level) const BMNOEXCEPT
Returns GAP level length for specified level.
Definition: bmblocks.h:1909
void assign_gap(block_idx_type nb, const bm::gap_word_t *res, unsigned res_len, bm::word_t *blk, gap_word_t *tmp_buf)
Attach the result of a GAP logical operation.
Definition: bmblocks.h:944
void clone_gap_block(unsigned i, unsigned j, const bm::gap_word_t *gap_block, unsigned len)
Clone static known block, assign to i-j position.
Definition: bmblocks.h:865
bm::id_t block_idx_type
Definition: bmblocks.h:52
allocator_type alloc_
allocator
Definition: bmblocks.h:2845
void init_tree()
allocate first level of descr. of blocks
Definition: bmblocks.h:2003
allocator_type & get_allocator() BMNOEXCEPT
Returns reference on the allocator.
Definition: bmblocks.h:1990
bool is_init() const BMNOEXCEPT
if tree of blocks already up
Definition: bmblocks.h:1998
void validate_top_zero(unsigned i) BMNOEXCEPT
Definition: bmblocks.h:2171
void swap(blocks_manager &bm) BMNOEXCEPT
Swaps content.
Definition: bmblocks.h:397
void opt_copy_bit_block(unsigned i, unsigned j, const bm::word_t *src_block, int opt_mode, bm::word_t *tmp_block)
Optimize and copy bit-block.
Definition: bmblocks.h:1347
bm::word_t *** top_blocks_root() BMNOEXCEPT
Definition: bmblocks.h:1897
void deallocate_top_subblock(unsigned nblk_blk) BMNOEXCEPT
Definition: bmblocks.h:2054
void optimize_gap_convert_bit_block(unsigned i, unsigned j, bm::word_t *block, unsigned threashold)
Definition: bmblocks.h:1452
const bm::word_t * get_block(unsigned i, unsigned j) const BMNOEXCEPT
Finds block in 2-level blocks array.
Definition: bmblocks.h:540
void copy_to_arena(const blocks_manager &bman)
calculate arena statistics, calculate and copy all blocks there
Definition: bmblocks.h:2538
void set_block_all_set_no_check(unsigned i, unsigned j)
Definition: bmblocks.h:615
bm::word_t * copy_block(block_idx_type idx, const blocks_manager &bm_src)
Copy block from another vector.
Definition: bmblocks.h:1027
void optimize_bit_block_nocheck(unsigned i, unsigned j)
Full Optimize bit-block at i-j position (no checks)
Definition: bmblocks.h:1433
bm::word_t * convert_gap2bitset(unsigned i, unsigned j, const gap_word_t *gap_block=0, unsigned len=0)
Converts block from type gap to conventional bitset block.
Definition: bmblocks.h:1532
bm::word_t * check_allocate_block(block_idx_type nb, unsigned content_flag, int initial_block_type, int *actual_block_type, bool allow_null_ret=true)
Function checks if block is not yet allocated, allocates it and sets to all-zero or all-one bits.
Definition: bmblocks.h:1069
void free_ptr(bm::word_t **ptr) BMNOEXCEPT
Definition: bmblocks.h:430
BMFORCEINLINE void set_block_ptr(unsigned i, unsigned j, bm::word_t *block) BMNOEXCEPT
Places new block into blocks table.
Definition: bmblocks.h:1496
void operator=(const blocks_manager &)
void copy(const blocks_manager &blockman, block_idx_type block_from=0, block_idx_type block_to=bm::set_total_blocks)
Definition: bmblocks.h:2744
const gap_word_t * glen() const BMNOEXCEPT
Returns current GAP level vector.
Definition: bmblocks.h:1901
unsigned compute_top_block_size(id_type bits_to_store) const BMNOEXCEPT
Compute size of the block array needed to store bits.
Definition: bmblocks.h:440
unsigned find_real_top_blocks() const BMNOEXCEPT
calculate top blocks which are not NULL and not FULL
Definition: bmblocks.h:2136
void zero_gap_block_ptr(unsigned i, unsigned j) BMNOEXCEPT
Free block, make it zero pointer in the tree.
Definition: bmblocks.h:1679
blocks_manager(const blocks_manager &blockman)
Definition: bmblocks.h:361
void zero_block(block_idx_type nb) BMNOEXCEPT
Free block, make it zero pointer in the tree.
Definition: bmblocks.h:1622
void set_block_all_set(unsigned i, unsigned j)
Definition: bmblocks.h:609
bm::word_t * deoptimize_block_no_check(bm::word_t *block, unsigned i, unsigned j)
Definition: bmblocks.h:1590
bm::word_t * deoptimize_block(unsigned i, unsigned j, bool alloc)
deoptimize block and return bit-block ptr can return NULL if block does not exists or allocate (if re...
Definition: bmblocks.h:1572
bm::word_t * make_bit_block(block_idx_type nb)
Create all-zeros bit block.
Definition: bmblocks.h:802
bm::id_t id_type
Definition: bmblocks.h:51
bm::gap_word_t * allocate_gap_block(unsigned level, const gap_word_t *src=0, const gap_word_t *glevel_len=0)
Definition: bmblocks.h:1866
static void free_arena(arena *ar, allocator_type &alloc) BMNOEXCEPT
Free arena (content memory) based on arena statistics.
Definition: bmblocks.h:2629
void optimize_bit_block(unsigned i, unsigned j, int opt_mode)
Optimize bit-block at i-j position.
Definition: bmblocks.h:1406
bm::word_t * borrow_tempblock()
Definition: bmblocks.h:1836
void optimize_block(unsigned i, unsigned j, bm::word_t *block, bm::word_t *temp_block, int opt_mode, bv_statistics *bv_stat)
Definition: bmblocks.h:2273
void calc_arena_stat(bm::bv_arena_statistics *st) const BMNOEXCEPT
Calculates bitvector arena statistics.
Definition: bmblocks.h:2466
bm::word_t * set_block(unsigned i, unsigned j, bm::word_t *block, bool gap)
Places new block into descriptors table, returns old block's address.
Definition: bmblocks.h:1279
~blocks_manager() BMNOEXCEPT
Definition: bmblocks.h:387
bm::word_t ** alloc_top_subblock(unsigned nblk_blk)
Definition: bmblocks.h:1176
unsigned reserve_top_blocks(unsigned top_blocks)
Make sure blocks manager has enough blocks capacity.
Definition: bmblocks.h:1936
bm::word_t * set_block(block_idx_type nb, bm::word_t *block)
Places new block into descriptors table, returns old block's address.
Definition: bmblocks.h:1202
bm::word_t * convert_gap2bitset(block_idx_type nb, const gap_word_t *gap_block=0)
Converts block from type gap to conventional bitset block.
Definition: bmblocks.h:1513
void optimize_tree(bm::word_t *temp_block, int opt_mode, bv_statistics *bv_stat)
Definition: bmblocks.h:2390
void set_block_ptr(block_idx_type nb, bm::word_t *block)
Places new block into blocks table.
Definition: bmblocks.h:1474
bm::word_t * clone_gap_block(const bm::gap_word_t *gap_block, bool &gap_res)
Clone GAP block from another GAP It can mutate into a bit-block if does not fit.
Definition: bmblocks.h:838
void set_all_zero(bool) BMNOEXCEPT
Fills all blocks with 0.
Definition: bmblocks.h:1150
void copy_bit_block(unsigned i, unsigned j, const bm::word_t *src_block)
Allocate and copy block.
Definition: bmblocks.h:1332
static bm::id_t block_bitcount(const bm::word_t *block) BMNOEXCEPT
Count number of bits ON in the block.
Definition: bmblocks.h:1698
bm::word_t * clone_assign_block(unsigned i, unsigned j, const bm::word_t *src_block, bool invert=false)
Clone block, assign to i-j position.
Definition: bmblocks.h:894
void reserve(id_type max_bits)
reserve capacity for specified number of bits
Definition: bmblocks.h:1924
void stat_correction(bv_statistics *stat) noexcept
Definition: bmblocks.h:2443
void set_block_gap_ptr(block_idx_type nb, gap_word_t *gap_blk)
Mark pointer as GAP and assign to the blocks tree.
Definition: bmblocks.h:1807
id_type size_type
Definition: bmblocks.h:54
bm::word_t * set_block(block_idx_type nb, bm::word_t *block, bool gap)
Places new block into descriptors table, returns old block's address.
Definition: bmblocks.h:1265
Bitvector Bit-vector container with runtime compression of bits.
Definition: bm.h:115
bool avx2_test_all_zero_wave(const void *ptr)
check if wave of pointers is all NULL
Definition: bmavx2.h:1805
#define NULL
Definition: ncbistd.hpp:225
bool sse42_test_all_zero_wave(const void *ptr) noexcept
check if wave of pointers is all NULL
Definition: bmsse4.h:910
bm::id_t bit_block_count(const bm::word_t *block) noexcept
Bitcount for bit block.
Definition: bmfunc.h:5051
void bit_invert(T *start) noexcept
Definition: bmfunc.h:6057
void bit_block_stream(bm::word_t *dst, const bm::word_t *src) noexcept
Bitblock copy/stream operation.
Definition: bmfunc.h:6816
bool is_bits_one(const bm::wordop_t *start) noexcept
Returns "true" if all bits in the block are 1.
Definition: bmfunc.h:6081
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
void bit_block_set(bm::word_t *dst, bm::word_t value) noexcept
Bitblock memset operation.
Definition: bmfunc.h:4456
void bit_block_copy(bm::word_t *dst, const bm::word_t *src) noexcept
Bitblock copy operation.
Definition: bmfunc.h:6777
unsigned bit_block_calc_change(const bm::word_t *block) noexcept
Definition: bmfunc.h:5283
bool gap_is_all_one(const bm::gap_word_t *buf) noexcept
Checks if GAP block is all-one.
Definition: bmfunc.h:1590
void gap_invert(T *buf) noexcept
Inverts all bits in the GAP buffer.
Definition: bmfunc.h:4620
void set_gap_level(T *buf, int level) noexcept
Sets GAP block capacity level.
Definition: bmfunc.h:4639
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_bit_count_unr(const T *buf) noexcept
Calculates number of bits ON in GAP buffer. Loop unrolled version.
Definition: bmfunc.h:2327
unsigned gap_capacity(const T *buf, const T *glevel_len) noexcept
Returs GAP block capacity.
Definition: bmfunc.h:1619
T gap_level(const T *buf) noexcept
Returs GAP blocks capacity level.
Definition: bmfunc.h:1649
int gap_calc_level(unsigned len, const T *glevel_len) noexcept
Calculates GAP block capacity level.
Definition: bmfunc.h:4661
bm::gap_word_t gap_length(const bm::gap_word_t *buf) noexcept
Returs GAP block length.
Definition: bmfunc.h:1603
void gap_set_all(T *buf, unsigned set_max, unsigned value) noexcept
Sets all bits to 0 or 1 (GAP)
Definition: bmfunc.h:4552
int i
int len
#include<zmmintrin.h>
Definition: bm.h:78
const unsigned set_array_mask
Definition: bmconst.h:97
const unsigned id_max
Definition: bmconst.h:109
const unsigned gap_max_level
Definition: bmconst.h:86
void xor_swap(W &x, W &y) noexcept
XOR swap two variables.
Definition: bmutil.h:534
unsigned int word_t
Definition: bmconst.h:39
bool find_not_null_ptr(const bm::word_t *const *const *arr, N start, N size, N *pos) noexcept
Definition: bmfunc.h:1427
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
bool check_block_zero(const bm::word_t *blk, bool deep_scan) noexcept
Checks all conditions and returns true if block consists of only 0 bits.
Definition: bmfunc.h:9096
const unsigned set_total_blocks
Definition: bmconst.h:111
word_t wordop_t
Definition: bmconst.h:135
const unsigned gap_levels
Definition: bmconst.h:85
const unsigned set_block_size
Definition: bmconst.h:55
unsigned bit_to_gap(gap_word_t *dest, const unsigned *block, unsigned dest_len) noexcept
Convert bit block to GAP representation.
Definition: bmfunc.h:4870
unsigned long long int id64_t
Definition: bmconst.h:35
const unsigned gap_equiv_len
Definition: bmconst.h:82
unsigned int id_t
Definition: bmconst.h:38
const unsigned gap_max_buff_len
Definition: bmconst.h:80
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
const unsigned set_top_array_size
Definition: bmconst.h:110
void for_each_block(T ***root, unsigned size1, F &f, BLOCK_IDX start)
Definition: bmfunc.h:2173
bool is_aligned(T *p) noexcept
Check pointer alignment.
Definition: bmutil.h:637
const unsigned bits_in_block
Definition: bmconst.h:114
static unsigned cnt[256]
static BOOL invert
Definition: pcregrep.c:189
Arena allocation memory guard.
Definition: bmblocks.h:2518
arena_guard(arena *ar, blocks_manager &bman) noexcept
Definition: bmblocks.h:2519
Allocation arena for ReadOnly vectors.
Definition: bmblocks.h:61
void reset()
Set all arena fields to zero.
Definition: bmblocks.h:70
bm::bv_arena_statistics st_
statistics and sizes
Definition: bmblocks.h:67
bm::word_t ** blk_blks_
PTR sub-blocks area.
Definition: bmblocks.h:66
void * a_ptr_
main allocated pointer
Definition: bmblocks.h:62
bm::gap_word_t * gap_blocks_
GAP blocks area.
Definition: bmblocks.h:65
bm::word_t *** top_blocks_
top descriptor
Definition: bmblocks.h:63
bm::word_t * blocks_
bit-blocks area
Definition: bmblocks.h:64
Structure with statistical information about memory allocation for arena based vectors.
Definition: bmfunc.h:121
size_t bit_blocks_sz
Total size of bit blocks.
Definition: bmfunc.h:122
size_t gap_blocks_sz
Total size of gap blocks.
Definition: bmfunc.h:123
size_t ptr_sub_blocks_sz
Total size of sub-blocks ptrs.
Definition: bmfunc.h:124
size_t get_alloc_size() const noexcept
Get allocation size in bytes.
Definition: bmfunc.h:134
unsigned top_block_size
size of top descriptor
Definition: bmfunc.h:125
void reset() noexcept
Reset statisctics.
Definition: bmfunc.h:128
Structure with statistical information about memory allocation footprint, serialization projection,...
Definition: bmfunc.h:56
void add_gap_block(unsigned capacity, unsigned length, unsigned level) noexcept
count gap block
Definition: bmfunc.h:79
size_t ptr_sub_blocks
Number of sub-blocks.
Definition: bmfunc.h:59
void add_bit_block() noexcept
cound bit block
Definition: bmfunc.h:70
size_t max_serialize_mem
estimated maximum memory for serialization
Definition: bmfunc.h:61
Default GAP lengths table.
Definition: bmconst.h:396
#define const
Definition: zconf.h:232
void free(voidpf ptr)
voidp malloc(uInt size)
Modified on Mon Apr 22 04:02:07 2024 by modify_doxy.py rev. 669887