BitMagic-C++
bmbmatrix.h
Go to the documentation of this file.
1 #ifndef BMBMATRIX__H__INCLUDED__
2 #define BMBMATRIX__H__INCLUDED__
3 /*
4 Copyright(c) 2002-2017 Anatoliy Kuznetsov(anatoliy_kuznetsov at yahoo.com)
5 
6 Licensed under the Apache License, Version 2.0 (the "License");
7 you may not use this file except in compliance with the License.
8 You may obtain a copy of the License at
9 
10  http://www.apache.org/licenses/LICENSE-2.0
11 
12 Unless required by applicable law or agreed to in writing, software
13 distributed under the License is distributed on an "AS IS" BASIS,
14 WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
15 See the License for the specific language governing permissions and
16 limitations under the License.
17 
18 For more information please visit: http://bitmagic.io
19 */
20 
21 /*! \file bmbmatrix.h
22  \brief basic bit-matrix class and utilities
23 */
24 
25 #include <stddef.h>
26 #include "bmconst.h"
27 
28 #ifndef BM_NO_STL
29 #include <stdexcept>
30 #endif
31 
32 #include "bm.h"
33 #include "bmtrans.h"
34 #include "bmdef.h"
35 
36 
37 
38 namespace bm
39 {
40 
41 /**
42  Basic dense bit-matrix class.
43 
44  Container of row-major bit-vectors, forming a bit-matrix.
45  This class uses dense form of row storage.
46  It is applicable as a build block for other sparse containers and
47  succinct data structures, implementing high level abstractions.
48 
49  @ingroup bmagic
50  @internal
51 */
52 template<typename BV>
54 {
55 public:
56  typedef BV bvector_type;
57  typedef bvector_type* bvector_type_ptr;
58  typedef const bvector_type* bvector_type_const_ptr;
59  typedef typename BV::allocator_type allocator_type;
61  typedef typename allocator_type::allocator_pool_type allocator_pool_type;
64  typedef unsigned char octet_type;
65 
66 public:
67  // ------------------------------------------------------------
68  /*! @name Construction, assignment */
69  ///@{
70 
71  basic_bmatrix(size_type rsize,
72  allocation_policy_type ap = allocation_policy_type(),
73  size_type bv_max_size = bm::id_max,
74  const allocator_type& alloc = allocator_type());
76 
77  /*! copy-ctor */
78  basic_bmatrix(const basic_bmatrix<BV>& bbm);
79  basic_bmatrix<BV>& operator = (const basic_bmatrix<BV>& bbm)
80  {
81  copy_from(bbm);
82  return *this;
83  }
84 
85 #ifndef BM_NO_CXX11
86  /*! move-ctor */
88 
89  /*! move assignmment operator */
91  {
92  if (this != &bbm)
93  {
94  free_rows();
95  swap(bbm);
96  }
97  return *this;
98  }
99 #endif
100 
101  void set_allocator_pool(allocator_pool_type* pool_ptr) { pool_ = pool_ptr; }
102 
103  ///@}
104 
105  // ------------------------------------------------------------
106  /*! @name content manipulation */
107  ///@{
108 
109  /*! Swap content */
110  void swap(basic_bmatrix<BV>& bbm) BMNOEXEPT;
111 
112  /*! Copy content */
113  void copy_from(const basic_bmatrix<BV>& bbm);
114 
115  ///@}
116 
117  // ------------------------------------------------------------
118  /*! @name row access */
119  ///@{
120 
121  /*! Get row bit-vector */
122  const bvector_type* row(size_type i) const;
123 
124  /*! Get row bit-vector */
125  bvector_type_const_ptr get_row(size_type i) const;
126 
127  /*! Get row bit-vector */
128  bvector_type* get_row(size_type i);
129 
130  /*! get number of value rows */
131  size_type rows() const { return rsize_; }
132 
133  /*! Make sure row is constructed, return bit-vector */
134  bvector_type_ptr construct_row(size_type row);
135 
136  /*! Make sure row is copy-constructed, return bit-vector */
137  bvector_type_ptr construct_row(size_type row, const bvector_type& bv);
138 
139  void destruct_row(size_type row);
140  ///@}
141 
142 
143  // ------------------------------------------------------------
144  /*! @name octet access and transposition */
145  ///@{
146 
147  /*!
148  Bit-transpose an octet and assign it to a bit-matrix
149 
150  @param pos - column position in the matrix
151  @param octet_idx - octet based row position (1 octet - 8 rows)
152  @param octet - value to assign
153  */
154  void set_octet(size_type pos, size_type octet_idx, unsigned char octet);
155 
156  /*!
157  Bit-transpose and insert an octet and assign it to a bit-matrix
158 
159  @param pos - column position in the matrix
160  @param octet_idx - octet based row position (1 octet - 8 rows)
161  @param octet - value to assign
162  */
163  void insert_octet(size_type pos, size_type octet_idx, unsigned char octet);
164 
165  /*!
166  return octet from the matrix
167 
168  @param pos - column position in the matrix
169  @param octet_idx - octet based row position (1 octet - 8 rows)
170  */
171  unsigned char get_octet(size_type pos, size_type octet_idx) const;
172 
173  /*!
174  Compare vector[pos] with octet
175 
176  It uses regulat comparison of chars to comply with the (signed)
177  char sort order.
178 
179  @param pos - column position in the matrix
180  @param octet_idx - octet based row position (1 octet - 8 rows)
181  @param octet - octet value to compare
182 
183  @return 0 - equal, -1 - less(vect[pos] < octet), 1 - greater
184  */
185  int compare_octet(size_type pos,
186  size_type octet_idx, char octet) const;
187 
188  ///@}
189 
190 public:
191 
192  // ------------------------------------------------------------
193  /*! @name Utility function */
194  ///@{
195 
196  /// Test if 4 rows from i are not NULL
197  bool test_4rows(unsigned i) const;
198 
199  /// Get low level internal access to
200  const bm::word_t* get_block(size_type p, unsigned i, unsigned j) const;
201 
202  unsigned get_half_octet(size_type pos, size_type row_idx) const;
203 
204  /*!
205  \brief run memory optimization for all bit-vector rows
206  \param temp_block - pre-allocated memory block to avoid unnecessary re-allocs
207  \param opt_mode - requested compression depth
208  \param stat - memory allocation statistics after optimization
209  */
210  void optimize(bm::word_t* temp_block = 0,
212  typename bvector_type::statistics* stat = 0);
213 
214  ///@}
215 
216 
217 protected:
218  void allocate_rows(size_type rsize);
219  void free_rows() BMNOEXEPT;
220 
221  bvector_type* construct_bvector(const bvector_type* bv) const;
222  void destruct_bvector(bvector_type* bv) const;
223 
224  static
225  void throw_bad_alloc() { BV::throw_bad_alloc(); }
226 
227 protected:
228  size_type bv_size_;
229  allocator_type alloc_;
230  allocation_policy_type ap_;
231  allocator_pool_type* pool_;
232 
233  bvector_type_ptr* bv_rows_;
234  size_type rsize_;
235 };
236 
237 /**
238  Base class for bit-transposed sparse vector construction
239 
240  @ingroup bmagic
241  @internal
242 */
243 template<typename Val, typename BV, unsigned MAX_SIZE>
245 {
246 public:
248  {
249  sv_plains = (sizeof(Val) * 8 * MAX_SIZE + 1),
250  sv_value_plains = (sizeof(Val) * 8 * MAX_SIZE)
251  };
252 
254  {
255  max_vector_size = MAX_SIZE
256  };
257 
258  typedef Val value_type;
259  typedef BV bvector_type;
260  typedef typename BV::size_type size_type;
261  typedef bvector_type* bvector_type_ptr;
262  typedef const bvector_type* bvector_type_const_ptr;
263  typedef const value_type& const_reference;
264  typedef typename BV::allocator_type allocator_type;
267  typedef typename allocator_type::allocator_pool_type allocator_pool_type;
269 
270 public:
272 
274  allocation_policy_type ap,
275  size_type bv_max_size,
276  const allocator_type& alloc);
277 
279 
280 #ifndef BM_NO_CXX11
281  /*! move-ctor */
283  {
284  bmatr_.swap(bsv.bmatr_);
285  size_ = bsv.size_;
286  effective_plains_ = bsv.effective_plains_;
287  bsv.size_ = 0;
288  }
289 #endif
290 
292 
293  size_type size() const { return size_; }
294 
295  void resize(size_type new_size);
296 
297  void clear_range(size_type left, size_type right, bool set_null);
298 
299  /*! \brief resize to zero, free memory */
300  void clear() BMNOEXEPT;
301 
302  /*! return true if empty */
303  bool empty() const { return size() == 0; }
304 
305 public:
306 
307  // ------------------------------------------------------------
308  /*! @name Various traits */
309  //@{
310  /**
311  \brief check if container supports NULL(unassigned) values
312  */
313  bool is_nullable() const { return bmatr_.get_row(this->null_plain()) != 0; }
314 
315  /**
316  \brief Get bit-vector of assigned values or NULL
317  (if not constructed that way)
318  */
319  const bvector_type* get_null_bvector() const
320  { return bmatr_.get_row(this->null_plain()); }
321 
322  /** \brief test if specified element is NULL
323  \param idx - element index
324  \return true if it is NULL false if it was assigned or container
325  is not configured to support assignment flags
326  */
327  bool is_null(size_type idx) const;
328 
329 
330  ///@}
331 
332 
333  // ------------------------------------------------------------
334  /*! @name Access to internals */
335  ///@{
336 
337  /*!
338  \brief get access to bit-plain, function checks and creates a plain
339  \return bit-vector for the bit plain
340  */
341  bvector_type_ptr get_plain(unsigned i);
342 
343  /*!
344  \brief get read-only access to bit-plain
345  \return bit-vector for the bit plain or NULL
346  */
347  bvector_type_const_ptr
348  get_plain(unsigned i) const { return bmatr_.row(i); }
349 
350  /*!
351  \brief get total number of bit-plains in the vector
352  */
353  static unsigned plains() { return value_bits(); }
354 
355  /** Number of stored bit-plains (value plains + extra */
356  static unsigned stored_plains() { return value_bits()+1; }
357 
358 
359  /** Number of effective bit-plains in the value type */
360  unsigned effective_plains() const { return effective_plains_ + 1; }
361 
362  /*!
363  \brief get access to bit-plain as is (can return NULL)
364  */
365  bvector_type_ptr plain(unsigned i) { return bmatr_.get_row(i); }
366  const bvector_type_ptr plain(unsigned i) const { return bmatr_.get_row(i); }
367 
368  bvector_type* get_null_bvect() { return bmatr_.get_row(this->null_plain());}
369 
370  /*!
371  \brief free memory in bit-plain
372  */
373  void free_plain(unsigned i) { bmatr_.destruct_row(i); }
374 
375  /*!
376  return mask of allocated bit-plains
377  1 in the mask - means bit-plain N is present
378  returns 64-bit unsigned mask for sub 64-bit types (like int)
379  unallocated mask bits will be zero extended
380 
381  @return 64-bit mask
382  @internal
383  */
384  bm::id64_t get_plains_mask(unsigned element_idx) const;
385 
386 
387  ///@}
388 
389  /*!
390  \brief run memory optimization for all bit-vector rows
391  \param temp_block - pre-allocated memory block to avoid unnecessary re-allocs
392  \param opt_mode - requested compression depth
393  \param stat - memory allocation statistics after optimization
394  */
395  void optimize(bm::word_t* temp_block = 0,
397  typename bvector_type::statistics* stat = 0);
398 
399  /*!
400  @brief Calculates memory statistics.
401 
402  Function fills statistics structure containing information about how
403  this vector uses memory and estimation of max. amount of memory
404  bvector needs to serialize itself.
405 
406  @param st - pointer on statistics structure to be filled in.
407 
408  @sa statistics
409  */
410  void calc_stat(typename bvector_type::statistics* st) const;
411 
412  /*!
413  \brief check if another sparse vector has the same content and size
414 
415  \param sv - sparse vector for comparison
416  \param null_able - flag to consider NULL vector in comparison (default)
417  or compare only value content plains
418 
419  \return true, if it is the same
420  */
421  bool equal(const base_sparse_vector<Val, BV, MAX_SIZE>& sv,
422  bm::null_support null_able = bm::use_null) const;
423 
424 protected:
426 
427  /*!
428  clear column in all value plains
429  \param plain_idx - row (plain index to start from)
430  \param idx - bit (column) to clear
431  */
432  void clear_value_plains_from(unsigned plain_idx, size_type idx);
433 
434  /*!
435  insert false (clear) column in all value plains
436  \param plain_idx - row (plain index to start from)
437  \param idx - bit (column) to clear insert
438  */
439  void insert_clear_value_plains_from(unsigned plain_idx, size_type idx);
440 
441  /*!
442  erase bit (column) from all plains
443  \param idx - bit (column) to erase
444  */
445  void erase_column(size_type idx);
446 
447  /*!
448  insert (NOT) NULL value
449  */
450  void insert_null(size_type idx, bool not_null);
451 
452 protected:
453  /** Number of total bit-plains in the value type*/
454  static unsigned value_bits()
455  {
457  }
458 
459  /** plain index for the "NOT NULL" flag1s plain */
460  static unsigned null_plain() { return value_bits(); }
461 protected:
462  bmatrix_type bmatr_; ///< bit-transposed matrix
463  size_type size_; ///< array size
465 
466 };
467 
468 //---------------------------------------------------------------------
469 //
470 //---------------------------------------------------------------------
471 
472 template<typename BV>
474  allocation_policy_type ap,
475  size_type bv_max_size,
476  const allocator_type& alloc)
477 : bv_size_(bv_max_size),
478  alloc_(alloc),
479  ap_(ap),
480  pool_(0),
481  bv_rows_(0),
482  rsize_(0)
483 {
484  allocate_rows(rsize);
485 }
486 
487 //---------------------------------------------------------------------
488 
489 template<typename BV>
491 {
492  free_rows();
493 }
494 
495 //---------------------------------------------------------------------
496 
497 template<typename BV>
499 : bv_size_(bbm.bv_size_),
500  alloc_(bbm.alloc_),
501  ap_(bbm.ap_),
502  pool_(0),
503  bv_rows_(0),
504  rsize_(0)
505 {
506  copy_from(bbm);
507 }
508 
509 //---------------------------------------------------------------------
510 
511 template<typename BV>
513 : bv_size_(bbm.bv_size_),
514  alloc_(bbm.alloc_),
515  ap_(bbm.ap_),
516  pool_(0),
517  bv_rows_(0),
518  rsize_(0)
519 {
520  swap(bbm);
521 }
522 
523 //---------------------------------------------------------------------
524 
525 template<typename BV>
526 const typename basic_bmatrix<BV>::bvector_type*
527 basic_bmatrix<BV>::row(size_type i) const
528 {
529  BM_ASSERT(i < rsize_);
530  return bv_rows_[i];
531 }
532 
533 //---------------------------------------------------------------------
534 
535 template<typename BV>
536 const typename basic_bmatrix<BV>::bvector_type*
537 basic_bmatrix<BV>::get_row(size_type i) const
538 {
539  BM_ASSERT(i < rsize_);
540  return bv_rows_[i];
541 }
542 
543 //---------------------------------------------------------------------
544 
545 template<typename BV>
548 {
549  BM_ASSERT(i < rsize_);
550  return bv_rows_[i];
551 }
552 
553 //---------------------------------------------------------------------
554 
555 template<typename BV>
556 bool basic_bmatrix<BV>::test_4rows(unsigned j) const
557 {
558  BM_ASSERT((j + 4) <= rsize_);
559 #if defined(BM64_SSE4)
560  __m128i w0 = _mm_loadu_si128((__m128i*)(bv_rows_ + j));
561  __m128i w1 = _mm_loadu_si128((__m128i*)(bv_rows_ + j + 2));
562  w0 = _mm_or_si128(w0, w1);
563  return !_mm_testz_si128(w0, w0);
564 #elif defined(BM64_AVX2) || defined(BM64_AVX512)
565  __m256i w0 = _mm256_loadu_si256((__m256i*)(bv_rows_ + j));
566  return !_mm256_testz_si256(w0, w0);
567 #else
568  bool b = bv_rows_[j + 0] || bv_rows_[j + 1] || bv_rows_[j + 2] || bv_rows_[j + 3];
569  return b;
570 #endif
571 }
572 
573 //---------------------------------------------------------------------
574 
575 template<typename BV>
577 {
578  if (this == &bbm) // nothing to do
579  return;
580  free_rows();
581 
582  bv_size_ = bbm.bv_size_;
583  alloc_ = bbm.alloc_;
584  ap_ = bbm.ap_;
585 
586  size_type rsize = bbm.rsize_;
587  if (rsize)
588  {
589  bv_rows_ = (bvector_type_ptr*)alloc_.alloc_ptr(rsize);
590  if (!bv_rows_)
591  throw_bad_alloc();
592  else
593  {
594  rsize_ = rsize;
595  for (size_type i = 0; i < rsize_; ++i)
596  {
597  const bvector_type_ptr bv = bbm.bv_rows_[i];
598  bv_rows_[i] = bv ? construct_bvector(bv) : 0;
599  }
600  }
601  }
602 
603 }
604 
605 
606 //---------------------------------------------------------------------
607 
608 template<typename BV>
609 void basic_bmatrix<BV>::allocate_rows(size_type rsize)
610 {
611  BM_ASSERT(!bv_rows_);
612 
613  if (rsize)
614  {
615  bv_rows_ = (bvector_type_ptr*)alloc_.alloc_ptr(unsigned(rsize));
616  if (!bv_rows_)
617  throw_bad_alloc();
618  else
619  {
620  rsize_ = rsize;
621  for (size_type i = 0; i < rsize; ++i)
622  bv_rows_[i] = 0;
623  }
624  }
625 }
626 
627 //---------------------------------------------------------------------
628 
629 template<typename BV>
631 {
632  for (size_type i = 0; i < rsize_; ++i)
633  {
634  bvector_type_ptr bv = bv_rows_[i];
635  if (bv)
636  {
637  destruct_bvector(bv);
638  bv_rows_[i] = 0;
639  }
640  } // for i
641  if (bv_rows_)
642  {
643  alloc_.free_ptr(bv_rows_, unsigned(rsize_));
644  }
645  bv_rows_ = 0;
646 }
647 
648 //---------------------------------------------------------------------
649 
650 template<typename BV>
652 {
653  if (this == &bbm)
654  return;
655 
656  bm::xor_swap(bv_size_, bbm.bv_size_);
657 
658  allocator_type alloc_tmp = alloc_;
659  alloc_ = bbm.alloc_;
660  bbm.alloc_ = alloc_tmp;
661 
662  allocation_policy_type ap_tmp = ap_;
663  ap_ = bbm.ap_;
664  bbm.ap_ = ap_tmp;
665 
666  allocator_pool_type* pool_tmp = pool_;
667  pool_ = bbm.pool_;
668  bbm.pool_ = pool_tmp;
669 
670  bm::xor_swap(rsize_, bbm.rsize_);
671 
672  bvector_type_ptr* rtmp = bv_rows_;
673  bv_rows_ = bbm.bv_rows_;
674  bbm.bv_rows_ = rtmp;
675 }
676 
677 //---------------------------------------------------------------------
678 
679 template<typename BV>
682 {
683  BM_ASSERT(row < rsize_);
684  bvector_type_ptr bv = bv_rows_[row];
685  if (!bv)
686  {
687  bv = bv_rows_[row] = construct_bvector(0);
688  }
689  return bv;
690 }
691 
692 //---------------------------------------------------------------------
693 
694 template<typename BV>
696 basic_bmatrix<BV>::construct_row(size_type row, const bvector_type& bv_src)
697 {
698  BM_ASSERT(row < rsize_);
699  bvector_type_ptr bv = bv_rows_[row];
700  if (bv)
701  {
702  *bv = bv_src;
703  }
704  else
705  {
706  bv = bv_rows_[row] = construct_bvector(&bv_src);
707  }
708  return bv;
709 }
710 
711 
712 //---------------------------------------------------------------------
713 
714 template<typename BV>
716 {
717  BM_ASSERT(row < rsize_);
718  bvector_type_ptr bv = bv_rows_[row];
719  if (bv)
720  {
721  destruct_bvector(bv);
722  bv_rows_[row] = 0;
723  }
724 }
725 
726 
727 //---------------------------------------------------------------------
728 
729 template<typename BV>
731 basic_bmatrix<BV>::construct_bvector(const bvector_type* bv) const
732 {
733  bvector_type* rbv = 0;
734 #ifdef BM_NO_STL // C compatibility mode
735  void* mem = ::malloc(sizeof(bvector_type));
736  if (mem == 0)
737  {
738  BM_THROW(false, BM_ERR_BADALLOC);
739  }
740  rbv = bv ? new(mem) bvector_type(*bv)
741  : new(mem) bvector_type(ap_.strat, ap_.glevel_len,
742  bv_size_,
743  alloc_);
744 #else
745  rbv = bv ? new bvector_type(*bv)
746  : new bvector_type(ap_.strat, ap_.glevel_len,
747  bv_size_,
748  alloc_);
749 #endif
750  return rbv;
751 }
752 
753 //---------------------------------------------------------------------
754 
755 template<typename BV>
756 void basic_bmatrix<BV>::destruct_bvector(bvector_type* bv) const
757 {
758 #ifdef BM_NO_STL // C compatibility mode
759  bv->~TBM_bvector();
760  ::free((void*)bv);
761 #else
762  delete bv;
763 #endif
764 }
765 
766 //---------------------------------------------------------------------
767 
768 template<typename BV>
769 const bm::word_t*
770 basic_bmatrix<BV>::get_block(size_type p, unsigned i, unsigned j) const
771 {
772  bvector_type_const_ptr bv = this->row(p);
773  if (bv)
774  {
775  const typename bvector_type::blocks_manager_type& bman = bv->get_blocks_manager();
776  return bman.get_block_ptr(i, j);
777  }
778  return 0;
779 }
780 
781 
782 //---------------------------------------------------------------------
783 
784 template<typename BV>
785 void basic_bmatrix<BV>::set_octet(size_type pos,
786  size_type octet_idx,
787  unsigned char octet)
788 {
789  BM_ASSERT(octet_idx * 8u < rsize_);
790 
791  size_type oct = octet;
792  size_type row = octet_idx * 8;
793  size_type row_end = row + 8;
794  for (; row < row_end; ++row)
795  {
796  bvector_type* bv = this->get_row(row);
797  if (oct & 1u)
798  {
799  if (!bv)
800  {
801  bv = this->construct_row(row);
802  bv->init();
803  }
804  bv->set_bit_no_check(pos);
805  }
806  else
807  {
808  if (bv)
809  bv->clear_bit_no_check(pos);
810  }
811  oct >>= 1;
812  if (!oct)
813  break;
814  } // for
815 
816  // clear the tail
817  for (++row; row < row_end; ++row)
818  {
819  bvector_type* bv = this->get_row(row);
820  if (bv)
821  bv->clear_bit_no_check(pos);
822  } // for
823 }
824 
825 //---------------------------------------------------------------------
826 
827 template<typename BV>
829  size_type octet_idx,
830  unsigned char octet)
831 {
832  BM_ASSERT(octet_idx * 8u < rsize_);
833 
834  size_type oct = octet;
835  size_type row = octet_idx * 8;
836  size_type row_end = row + 8;
837  for (; row < row_end; ++row)
838  {
839  bvector_type* bv = this->get_row(row);
840  if (oct & 1u)
841  {
842  if (!bv)
843  {
844  bv = this->construct_row(row);
845  bv->init();
846  bv->set_bit_no_check(pos);
847  }
848  else
849  {
850  bv->insert(pos, true);
851  }
852  }
853  else
854  {
855  if (bv)
856  bv->insert(pos, false);
857  }
858  oct >>= 1;
859  if (!oct)
860  break;
861  } // for
862 
863  // clear the tail
864  for (++row; row < row_end; ++row)
865  {
866  bvector_type* bv = this->get_row(row);
867  if (bv)
868  bv->insert(pos, false);
869  } // for
870 }
871 
872 
873 //---------------------------------------------------------------------
874 
875 template<typename BV>
876 unsigned char
877 basic_bmatrix<BV>::get_octet(size_type pos, size_type octet_idx) const
878 {
879  unsigned v = 0;
880 
881  block_idx_type nb = (pos >> bm::set_block_shift);
882  unsigned i0 = unsigned(nb >> bm::set_array_shift); // top block address
883  unsigned j0 = unsigned(nb & bm::set_array_mask); // address in sub-block
884 
885  const bm::word_t* blk;
886  const bm::word_t* blka[8];
887  unsigned nbit = unsigned(pos & bm::set_block_mask);
888  unsigned nword = unsigned(nbit >> bm::set_word_shift);
889  unsigned mask0 = 1u << (nbit & bm::set_word_mask);
890 
891  unsigned row_idx = unsigned(octet_idx * 8);
892 
893  blka[0] = get_block(row_idx+0, i0, j0);
894  blka[1] = get_block(row_idx+1, i0, j0);
895  blka[2] = get_block(row_idx+2, i0, j0);
896  blka[3] = get_block(row_idx+3, i0, j0);
897  blka[4] = get_block(row_idx+4, i0, j0);
898  blka[5] = get_block(row_idx+5, i0, j0);
899  blka[6] = get_block(row_idx+6, i0, j0);
900  blka[7] = get_block(row_idx+7, i0, j0);
901  unsigned is_set;
902 
903  if ((blk = blka[0])!=0)
904  {
905  if (blk == FULL_BLOCK_FAKE_ADDR)
906  is_set = 1;
907  else
908  is_set = (BM_IS_GAP(blk)) ? bm::gap_test_unr(BMGAP_PTR(blk), nbit) : (blk[nword] & mask0);
909  v |= (unsigned)bool(is_set);
910  }
911  if ((blk = blka[1])!=0)
912  {
913  if (blk == FULL_BLOCK_FAKE_ADDR)
914  is_set = 1;
915  else
916  is_set = (BM_IS_GAP(blk)) ? bm::gap_test_unr(BMGAP_PTR(blk), nbit) : (blk[nword] & mask0);
917  v |= unsigned(bool(is_set)) << 1u;
918  }
919  if ((blk = blka[2])!=0)
920  {
921  if (blk == FULL_BLOCK_FAKE_ADDR)
922  is_set = 1;
923  else
924  is_set = (BM_IS_GAP(blk)) ? bm::gap_test_unr(BMGAP_PTR(blk), nbit) : (blk[nword] & mask0);
925  v |= unsigned(bool(is_set)) << 2u;
926  }
927  if ((blk = blka[3])!=0)
928  {
929  if (blk == FULL_BLOCK_FAKE_ADDR)
930  is_set = 1;
931  else
932  is_set = (BM_IS_GAP(blk)) ? bm::gap_test_unr(BMGAP_PTR(blk), nbit) : (blk[nword] & mask0);
933  v |= unsigned(bool(is_set)) << 3u;
934  }
935 
936 
937  if ((blk = blka[4])!=0)
938  {
939  if (blk == FULL_BLOCK_FAKE_ADDR)
940  is_set = 1;
941  else
942  is_set = (BM_IS_GAP(blk)) ? bm::gap_test_unr(BMGAP_PTR(blk), nbit) : (blk[nword] & mask0);
943  v |= unsigned(bool(is_set)) << 4u;
944  }
945  if ((blk = blka[5])!=0)
946  {
947  if (blk == FULL_BLOCK_FAKE_ADDR)
948  is_set = 1;
949  else
950  is_set = (BM_IS_GAP(blk)) ? bm::gap_test_unr(BMGAP_PTR(blk), nbit) : (blk[nword] & mask0);
951  v |= unsigned(bool(is_set)) << 5u;
952  }
953  if ((blk = blka[6])!=0)
954  {
955  if (blk == FULL_BLOCK_FAKE_ADDR)
956  is_set = 1;
957  else
958  is_set = (BM_IS_GAP(blk)) ? bm::gap_test_unr(BMGAP_PTR(blk), nbit) : (blk[nword] & mask0);
959  v |= unsigned(bool(is_set)) << 6u;
960  }
961  if ((blk = blka[7])!=0)
962  {
963  if (blk == FULL_BLOCK_FAKE_ADDR)
964  is_set = 1;
965  else
966  is_set = (BM_IS_GAP(blk)) ? bm::gap_test_unr(BMGAP_PTR(blk), nbit) : (blk[nword] & mask0);
967  v |= unsigned(bool(is_set)) << 7u;
968  }
969 
970  return (unsigned char)v;
971 }
972 
973 //---------------------------------------------------------------------
974 
975 template<typename BV>
977  size_type octet_idx,
978  char octet) const
979 {
980  char value = char(get_octet(pos, octet_idx));
981  return (value > octet) - (value < octet);
982 }
983 
984 //---------------------------------------------------------------------
985 
986 template<typename BV>
987 unsigned
988 basic_bmatrix<BV>::get_half_octet(size_type pos, size_type row_idx) const
989 {
990  unsigned v = 0;
991 
992  block_idx_type nb = (pos >> bm::set_block_shift);
993  unsigned i0 = unsigned(nb >> bm::set_array_shift); // top block address
994  unsigned j0 = unsigned(nb & bm::set_array_mask); // address in sub-block
995 
996  const bm::word_t* blk;
997  const bm::word_t* blka[4];
998  unsigned nbit = unsigned(pos & bm::set_block_mask);
999  unsigned nword = unsigned(nbit >> bm::set_word_shift);
1000  unsigned mask0 = 1u << (nbit & bm::set_word_mask);
1001 
1002  blka[0] = get_block(row_idx+0, i0, j0);
1003  blka[1] = get_block(row_idx+1, i0, j0);
1004  blka[2] = get_block(row_idx+2, i0, j0);
1005  blka[3] = get_block(row_idx+3, i0, j0);
1006  unsigned is_set;
1007 
1008  if ((blk = blka[0])!=0)
1009  {
1010  if (blk == FULL_BLOCK_FAKE_ADDR)
1011  is_set = 1;
1012  else
1013  is_set = (BM_IS_GAP(blk)) ? bm::gap_test_unr(BMGAP_PTR(blk), nbit) : (blk[nword] & mask0);
1014  v |= unsigned(bool(is_set));
1015  }
1016  if ((blk = blka[1])!=0)
1017  {
1018  if (blk == FULL_BLOCK_FAKE_ADDR)
1019  is_set = 1;
1020  else
1021  is_set = (BM_IS_GAP(blk)) ? bm::gap_test_unr(BMGAP_PTR(blk), nbit) : (blk[nword] & mask0);
1022  v |= unsigned(bool(is_set)) << 1u;
1023  }
1024  if ((blk = blka[2])!=0)
1025  {
1026  if (blk == FULL_BLOCK_FAKE_ADDR)
1027  is_set = 1;
1028  else
1029  is_set = (BM_IS_GAP(blk)) ? bm::gap_test_unr(BMGAP_PTR(blk), nbit) : (blk[nword] & mask0);
1030  v |= unsigned(bool(is_set)) << 2u;
1031  }
1032  if ((blk = blka[3])!=0)
1033  {
1034  if (blk == FULL_BLOCK_FAKE_ADDR)
1035  is_set = 1;
1036  else
1037  is_set = (BM_IS_GAP(blk)) ? bm::gap_test_unr(BMGAP_PTR(blk), nbit) : (blk[nword] & mask0);
1038  v |= unsigned(bool(is_set)) << 3u;
1039  }
1040  return v;
1041 }
1042 
1043 //---------------------------------------------------------------------
1044 
1045 template<typename BV>
1047  typename bvector_type::optmode opt_mode,
1048  typename bvector_type::statistics* st)
1049 {
1050  if (st)
1051  st->reset();
1052 
1054  if (!temp_block)
1055  temp_block = tb;
1056 
1057  for (unsigned k = 0; k < rsize_; ++k)
1058  {
1059  bvector_type* bv = get_row(k);
1060  if (bv)
1061  {
1062  typename bvector_type::statistics stbv;
1063  stbv.reset();
1064  bv->optimize(temp_block, opt_mode, st ? &stbv : 0);
1065  if (st)
1066  {
1067  st->add(stbv);
1068  }
1069  }
1070  } // for k
1071 }
1072 
1073 
1074 
1075 //---------------------------------------------------------------------
1076 //---------------------------------------------------------------------
1077 
1078 
1079 
1080 template<class Val, class BV, unsigned MAX_SIZE>
1082 : bmatr_(sv_plains, allocation_policy_type(), bm::id_max, allocator_type()),
1083  size_(0),
1084  effective_plains_(0)
1085 {
1086 }
1087 
1088 //---------------------------------------------------------------------
1089 
1090 template<class Val, class BV, unsigned MAX_SIZE>
1092  bm::null_support null_able,
1093  allocation_policy_type ap,
1094  size_type bv_max_size,
1095  const allocator_type& alloc)
1096 : bmatr_(sv_plains, ap, bv_max_size, alloc),
1097  size_(0),
1098  effective_plains_(0)
1099 {
1100  if (null_able == bm::use_null)
1101  {
1102  unsigned i = null_plain();
1103  bmatr_.construct_row(i)->init();
1104  }
1105 }
1106 
1107 //---------------------------------------------------------------------
1108 
1109 template<class Val, class BV, unsigned MAX_SIZE>
1112 : bmatr_(bsv.bmatr_),
1113  size_(bsv.size_),
1114  effective_plains_(bsv.effective_plains_)
1115 {
1116 }
1117 
1118 //---------------------------------------------------------------------
1119 
1120 template<class Val, class BV, unsigned MAX_SIZE>
1123 {
1124  resize(bsv.size());
1125  effective_plains_ = bsv.effective_plains_;
1126 
1127  unsigned ni = this->null_plain();
1128  unsigned plains = bsv.stored_plains();
1129  for (size_type i = 0; i < plains; ++i)
1130  {
1131  bvector_type* bv = bmatr_.get_row(i);
1132  const bvector_type* bv_src = bsv.bmatr_.row(i);
1133 
1134  if (i == ni) // NULL plain copy
1135  {
1136  if (bv && !bv_src) // special case (copy from not NULL)
1137  {
1138  if (size_)
1139  bv->set_range(0, size_-1);
1140  continue;
1141  }
1142  }
1143 
1144  if (bv)
1145  bmatr_.destruct_row(i);
1146  if (bv_src)
1147  bmatr_.construct_row(i, *bv_src);
1148  } // for i
1149 }
1150 
1151 //---------------------------------------------------------------------
1152 
1153 template<class Val, class BV, unsigned MAX_SIZE>
1156 {
1157  if (this != &bsv)
1158  {
1159  bmatr_.swap(bsv.bmatr_);
1160 
1161  bm::xor_swap(size_, bsv.size_);
1162  bm::xor_swap(effective_plains_, bsv.effective_plains_);
1163  }
1164 }
1165 
1166 //---------------------------------------------------------------------
1167 
1168 template<class Val, class BV, unsigned MAX_SIZE>
1170 {
1171  unsigned plains = value_bits();
1172  for (size_type i = 0; i < plains; ++i)
1173  {
1174  bmatr_.destruct_row(i);
1175  }
1176  size_ = 0;
1177  bvector_type* bv_null = get_null_bvect();
1178  if (bv_null)
1179  bv_null->clear();
1180 }
1181 
1182 //---------------------------------------------------------------------
1183 
1184 template<class Val, class BV, unsigned MAX_SIZE>
1188  bool set_null)
1189 {
1190  if (right < left)
1191  {
1192  return clear_range(right, left, set_null);
1193  }
1194  unsigned plains = value_bits();
1195  for (unsigned i = 0; i < plains; ++i)
1196  {
1197  bvector_type* bv = this->bmatr_.get_row(i);
1198  if (bv)
1199  bv->set_range(left, right, false);
1200  } // for i
1201 
1202  if (set_null)
1203  {
1204  bvector_type* bv_null = this->get_null_bvect();
1205  if (bv_null)
1206  bv_null->set_range(left, right, false);
1207  }
1208 }
1209 
1210 //---------------------------------------------------------------------
1211 
1212 template<class Val, class BV, unsigned MAX_SIZE>
1214 {
1215  if (sz == size()) // nothing to do
1216  return;
1217  if (!sz) // resize to zero is an equivalent of non-destructive deallocation
1218  {
1219  clear();
1220  return;
1221  }
1222  if (sz < size()) // vector shrink
1223  clear_range(sz, this->size_-1, true); // clear the tails and NULL vect
1224  size_ = sz;
1225 }
1226 
1227 
1228 //---------------------------------------------------------------------
1229 
1230 template<class Val, class BV, unsigned MAX_SIZE>
1232 {
1233  const bvector_type* bv_null = get_null_bvector();
1234  return (bv_null) ? (!bv_null->test(idx)) : false;
1235 }
1236 
1237 //---------------------------------------------------------------------
1238 
1239 template<class Val, class BV, unsigned MAX_SIZE>
1241  bool not_null)
1242 {
1243  bvector_type* bv_null = this->get_null_bvect();
1244  if (bv_null)
1245  bv_null->insert(idx, not_null);
1246 }
1247 
1248 //---------------------------------------------------------------------
1249 
1250 template<class Val, class BV, unsigned MAX_SIZE>
1253 {
1254  bvector_type_ptr bv = bmatr_.get_row(i);
1255  if (!bv)
1256  {
1257  bv = bmatr_.construct_row(i);
1258  bv->init();
1259  if (i > effective_plains_ && i < value_bits())
1260  effective_plains_ = i;
1261  }
1262  return bv;
1263 }
1264 
1265 //---------------------------------------------------------------------
1266 
1267 template<class Val, class BV, unsigned MAX_SIZE>
1269  unsigned element_idx) const
1270 {
1271  BM_ASSERT(element_idx < MAX_SIZE);
1272  bm::id64_t mask = 0;
1273  bm::id64_t mask1 = 1;
1274  const unsigned plains = sizeof(value_type) * 8;
1275  unsigned bidx = 0;
1276  for (unsigned i = element_idx * plains; i < (element_idx+1) * plains; i+=4)
1277  {
1278  mask |= get_plain(i+0) ? (mask1 << (bidx+0)) : 0ull;
1279  mask |= get_plain(i+1) ? (mask1 << (bidx+1)) : 0ull;
1280  mask |= get_plain(i+2) ? (mask1 << (bidx+2)) : 0ull;
1281  mask |= get_plain(i+3) ? (mask1 << (bidx+3)) : 0ull;
1282  bidx += 4;
1283  } // for i
1284  return mask;
1285 }
1286 
1287 //---------------------------------------------------------------------
1288 
1289 template<class Val, class BV, unsigned MAX_SIZE>
1291  typename bvector_type::optmode opt_mode,
1292  typename bvector_type::statistics* st)
1293 {
1294  typename bvector_type::statistics stbv;
1295  bmatr_.optimize(temp_block, opt_mode, &stbv);
1296  if (st)
1297  st->add(stbv);
1298 
1299  bvector_type* bv_null = this->get_null_bvect();
1300 
1301  unsigned stored_plains = this->stored_plains();
1302  for (unsigned j = 0; j < stored_plains; ++j)
1303  {
1304  bvector_type* bv = this->bmatr_.get_row(j);
1305  if (bv && (bv != bv_null)) // protect the NULL vector from de-allocation
1306  {
1307  // TODO: check if this can be done within optimize loop
1308  if (!bv->any()) // empty vector?
1309  {
1310  this->bmatr_.destruct_row(j);
1311  continue;
1312  }
1313  }
1314  } // for j
1315 }
1316 
1317 //---------------------------------------------------------------------
1318 
1319 template<class Val, class BV, unsigned MAX_SIZE>
1321  typename bvector_type::statistics* st) const
1322 {
1323  BM_ASSERT(st);
1324 
1325  st->reset();
1326 
1327  unsigned stored_plains = this->stored_plains();
1328  for (unsigned j = 0; j < stored_plains; ++j)
1329  {
1330  const bvector_type* bv = this->bmatr_.row(j);
1331  if (bv)
1332  {
1333  typename bvector_type::statistics stbv;
1334  bv->calc_stat(&stbv);
1335  st->add(stbv);
1336  }
1337  else
1338  {
1339  st->max_serialize_mem += 8;
1340  }
1341  } // for j
1342 
1343  // header accounting
1344  st->max_serialize_mem += 1 + 1 + 1 + 1 + 8 + (8 * this->stored_plains());
1345  st->max_serialize_mem += 1 + 8; // extra header fields for large bit-matrixes
1346 }
1347 
1348 //---------------------------------------------------------------------
1349 
1350 template<class Val, class BV, unsigned MAX_SIZE>
1352  unsigned plain_idx, size_type idx)
1353 {
1354  for (unsigned i = plain_idx; i < sv_value_plains; ++i)
1355  {
1356  bvector_type* bv = this->bmatr_.get_row(i);
1357  if (bv)
1358  bv->clear_bit_no_check(idx);
1359  }
1360 }
1361 
1362 //---------------------------------------------------------------------
1363 
1364 template<class Val, class BV, unsigned MAX_SIZE>
1366  unsigned plain_idx, size_type idx)
1367 {
1368  for (unsigned i = plain_idx; i < sv_value_plains; ++i)
1369  {
1370  bvector_type* bv = this->bmatr_.get_row(i);
1371  if (bv)
1372  bv->insert(idx, false);
1373  }
1374 }
1375 
1376 //---------------------------------------------------------------------
1377 
1378 template<class Val, class BV, unsigned MAX_SIZE>
1380 {
1381  for (unsigned i = 0; i < sv_value_plains; ++i)
1382  {
1383  bvector_type* bv = this->bmatr_.get_row(i);
1384  if (bv)
1385  bv->erase(idx);
1386  }
1387 }
1388 
1389 //---------------------------------------------------------------------
1390 
1391 template<class Val, class BV, unsigned MAX_SIZE>
1394  bm::null_support null_able) const
1395 {
1396  size_type arg_size = sv.size();
1397  if (this->size_ != arg_size)
1398  {
1399  return false;
1400  }
1401  unsigned plains = this->plains();
1402  for (unsigned j = 0; j < plains; ++j)
1403  {
1404  const bvector_type* bv = this->bmatr_.get_row(j);
1405  const bvector_type* arg_bv = sv.bmatr_.get_row(j);
1406  if (bv == arg_bv) // same NULL
1407  continue;
1408  // check if any not NULL and not empty
1409  if (!bv && arg_bv)
1410  {
1411  if (arg_bv->any())
1412  return false;
1413  continue;
1414  }
1415  if (bv && !arg_bv)
1416  {
1417  if (bv->any())
1418  return false;
1419  continue;
1420  }
1421  // both not NULL
1422  int cmp = bv->compare(*arg_bv);
1423  if (cmp != 0)
1424  return false;
1425  } // for j
1426 
1427  if (null_able == bm::use_null)
1428  {
1429  const bvector_type* bv_null = this->get_null_bvector();
1430  const bvector_type* bv_null_arg = sv.get_null_bvector();
1431 
1432  // check the NULL vectors
1433  if (bv_null == bv_null_arg)
1434  return true;
1435  if (!bv_null || !bv_null_arg)
1436  return false;
1437  BM_ASSERT(bv_null);
1438  BM_ASSERT(bv_null_arg);
1439  int cmp = bv_null->compare(*bv_null);
1440  if (cmp != 0)
1441  return false;
1442  }
1443  return true;
1444 }
1445 
1446 //---------------------------------------------------------------------
1447 
1448 
1449 } // namespace
1450 
1451 #endif
bvector_type * get_null_bvect()
Definition: bmbmatrix.h:368
memory allocation policy
Definition: bm.h:1243
const blocks_manager_type & get_blocks_manager() const
get access to memory manager (internal) Use only if you are BitMagic library
Definition: bm.h:2239
Compressed bit-vector bvector<> container, set algebraic methods, traversal iterators.
bvector_type::size_type size_type
Definition: bmbmatrix.h:62
bvector_type * bvector_type_ptr
Definition: bmbmatrix.h:57
const bm::word_t * get_block(size_type p, unsigned i, unsigned j) const
Get low level internal access to.
Definition: bmbmatrix.h:770
void clear_bit_no_check(size_type n)
Clears bit n without precondiion checks.
Definition: bm.h:1606
const bvector_type_ptr plain(unsigned i) const
Definition: bmbmatrix.h:366
bvector_type::block_idx_type block_idx_type
Definition: bmbmatrix.h:63
bool is_nullable() const
check if container supports NULL(unassigned) values
Definition: bmbmatrix.h:313
static TBVector * construct_bvector()
Definition: xsample01.cpp:99
void swap(basic_bmatrix< BV > &bbm) BMNOEXEPT
Definition: bmbmatrix.h:651
static unsigned plains()
get total number of bit-plains in the vector
Definition: bmbmatrix.h:353
Base class for bit-transposed sparse vector construction.
Definition: bmbmatrix.h:244
const unsigned set_word_shift
Definition: bmconst.h:70
bvector_type::allocation_policy allocation_policy_type
Definition: bmbmatrix.h:60
allocator_type::allocator_pool_type allocator_pool_type
Definition: bmbmatrix.h:267
bool test_4rows(unsigned i) const
Test if 4 rows from i are not NULL.
Definition: bmbmatrix.h:556
unsigned char get_octet(size_type pos, size_type octet_idx) const
Definition: bmbmatrix.h:877
Constants, tables and typedefs.
const unsigned set_array_shift
Definition: bmconst.h:92
unsigned long long int id64_t
Definition: bmconst.h:34
unsigned get_half_octet(size_type pos, size_type row_idx) const
Definition: bmbmatrix.h:988
size_type size() const
Definition: bmbmatrix.h:293
static unsigned value_bits()
Number of total bit-plains in the value type.
Definition: bmbmatrix.h:454
bm::id_t size_type
Definition: bm.h:117
void optimize(bm::word_t *temp_block=0, optmode opt_mode=opt_compress, statistics *stat=0)
Optimize memory bitvector&#39;s memory allocation.
Definition: bm.h:3136
void optimize(bm::word_t *temp_block=0, typename bvector_type::optmode opt_mode=bvector_type::opt_compress, typename bvector_type::statistics *stat=0)
run memory optimization for all bit-vector rows
Definition: bmbmatrix.h:1046
basic_bmatrix(size_type rsize, allocation_policy_type ap=allocation_policy_type(), size_type bv_max_size=bm::id_max, const allocator_type &alloc=allocator_type())
Definition: bmbmatrix.h:473
bvector_type::enumerator bvector_enumerator_type
Definition: bmbmatrix.h:266
Definition: bm.h:76
void free_plain(unsigned i)
free memory in bit-plain
Definition: bmbmatrix.h:373
void free_rows() BMNOEXEPT
Definition: bmbmatrix.h:630
size_t max_serialize_mem
estimated maximum memory for serialization
Definition: bmfunc.h:60
const bvector_type * row(size_type i) const
Definition: bmbmatrix.h:527
#define BMNOEXEPT
Definition: bmdef.h:78
BV::allocator_type allocator_type
Definition: bmbmatrix.h:59
unsigned effective_plains_
Definition: bmbmatrix.h:464
void xor_swap(W &x, W &y)
XOR swap two scalar variables.
Definition: bmfunc.h:876
compress blocks when possible (GAP/prefix sum)
Definition: bm.h:134
bm::basic_bmatrix< BV > bmatrix_type
Definition: bmbmatrix.h:268
const bvector_type * get_null_bvector() const
Get bit-vector of assigned values or NULL (if not constructed that way)
Definition: bmbmatrix.h:319
const bvector_type * bvector_type_const_ptr
Definition: bmbmatrix.h:262
const unsigned id_max
Definition: bmconst.h:105
#define BM_DECLARE_TEMP_BLOCK(x)
Definition: bm.h:47
Statistical information about bitset&#39;s memory allocation details.
Definition: bm.h:121
~basic_bmatrix() BMNOEXEPT
Definition: bmbmatrix.h:490
basic_bmatrix< BV > & operator=(const basic_bmatrix< BV > &bbm)
Definition: bmbmatrix.h:79
bvector_type_ptr plain(unsigned i)
get access to bit-plain as is (can return NULL)
Definition: bmbmatrix.h:365
null_support
NULL-able value support.
Definition: bmconst.h:214
blocks_manager_type::block_idx_type block_idx_type
Definition: bm.h:113
unsigned effective_plains() const
Number of effective bit-plains in the value type.
Definition: bmbmatrix.h:360
allocator_pool_type * pool_
Definition: bmbmatrix.h:231
unsigned int word_t
Definition: bmconst.h:38
int compare_octet(size_type pos, size_type octet_idx, char octet) const
Definition: bmbmatrix.h:976
size_type bv_size_
Definition: bmbmatrix.h:228
static void throw_bad_alloc()
Definition: bmbmatrix.h:225
support "non-assigned" or "NULL" logic
Definition: bmconst.h:216
Basic dense bit-matrix class.
Definition: bmbmatrix.h:53
BV::allocator_type allocator_type
Definition: bmbmatrix.h:264
void allocate_rows(size_type rsize)
Definition: bmbmatrix.h:609
unsigned gap_test_unr(const T *buf, const unsigned pos)
Tests if bit = pos is true. Analog of bm::gap_test with SIMD unrolling.
Definition: bmfunc.h:1256
const unsigned set_array_mask
Definition: bmconst.h:93
const value_type & const_reference
Definition: bmbmatrix.h:263
void copy_from(const basic_bmatrix< BV > &bbm)
Definition: bmbmatrix.h:576
void init()
Explicit post-construction initialization.
Definition: bm.h:2427
void insert_octet(size_type pos, size_type octet_idx, unsigned char octet)
Definition: bmbmatrix.h:828
blocks_manager< Alloc > blocks_manager_type
Definition: bm.h:112
bvector_type * construct_bvector(const bvector_type *bv) const
Definition: bmbmatrix.h:731
size_type rows() const
Definition: bmbmatrix.h:131
const bvector_type * bvector_type_const_ptr
Definition: bmbmatrix.h:58
void reset()
Reset statisctics.
Definition: bmfunc.h:93
allocation_policy_type ap_
Definition: bmbmatrix.h:230
Definitions(internal)
bvector_type_const_ptr get_plain(unsigned i) const
get read-only access to bit-plain
Definition: bmbmatrix.h:348
bvector_type * bvector_type_ptr
Definition: bmbmatrix.h:261
bvector_type_ptr construct_row(size_type row)
Definition: bmbmatrix.h:681
void set_allocator_pool(allocator_pool_type *pool_ptr)
Definition: bmbmatrix.h:101
#define BM_IS_GAP(ptr)
Definition: bmdef.h:168
Utilities for bit transposition (internal) (experimental!)
size_type rsize_
Definition: bmbmatrix.h:234
const unsigned set_block_mask
Definition: bmconst.h:56
bvector_type_const_ptr get_row(size_type i) const
Definition: bmbmatrix.h:537
Constant iterator designed to enumerate "ON" bits.
Definition: bm.h:590
optmode
Optimization mode Every next level means additional checks (better compression vs time) ...
Definition: bm.h:129
#define BMGAP_PTR(ptr)
Definition: bmdef.h:166
const unsigned set_word_mask
Definition: bmconst.h:71
static unsigned null_plain()
plain index for the "NOT NULL" flag1s plain
Definition: bmbmatrix.h:460
base_sparse_vector(base_sparse_vector< Val, BV, MAX_SIZE > &&bsv) BMNOEXEPT
Definition: bmbmatrix.h:282
allocator_type alloc_
Definition: bmbmatrix.h:229
#define BM_ASSERT
Definition: bmdef.h:117
void destruct_bvector(bvector_type *bv) const
Definition: bmbmatrix.h:756
void set_octet(size_type pos, size_type octet_idx, unsigned char octet)
Definition: bmbmatrix.h:785
bm::bvector bvector_type
unsigned char octet_type
Definition: bmbmatrix.h:64
bmatrix_type bmatr_
bit-transposed matrix
Definition: bmbmatrix.h:462
const unsigned set_block_shift
Definition: bmconst.h:55
void add(const bv_statistics &st)
Sum data from another sttructure.
Definition: bmfunc.h:102
bool empty() const
Definition: bmbmatrix.h:303
bvector_type_ptr * bv_rows_
Definition: bmbmatrix.h:233
static unsigned stored_plains()
Number of stored bit-plains (value plains + extra.
Definition: bmbmatrix.h:356
allocator_type::allocator_pool_type allocator_pool_type
Definition: bmbmatrix.h:61
BV::size_type size_type
Definition: bmbmatrix.h:260
void destruct_row(size_type row)
Definition: bmbmatrix.h:715
bvector_type::allocation_policy allocation_policy_type
Definition: bmbmatrix.h:265
void set_bit_no_check(size_type n)
Set bit without checking preconditions (size, etc)
Definition: bm.h:3425
size_type size_
array size
Definition: bmbmatrix.h:463
#define FULL_BLOCK_FAKE_ADDR
Definition: bmdef.h:136
bool insert(size_type n, bool value)
Insert bit into specified position All the vector content after insert position is shifted right...
Definition: bm.h:4311