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