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