BitMagic-C++
bmsparsevec_compr.h
Go to the documentation of this file.
1#ifndef BMSPARSEVEC_COMPR_H__INCLUDED__
2#define BMSPARSEVEC_COMPR_H__INCLUDED__
3/*
4Copyright(c) 2002-2017 Anatoliy Kuznetsov(anatoliy_kuznetsov at yahoo.com)
5
6Licensed under the Apache License, Version 2.0 (the "License");
7you may not use this file except in compliance with the License.
8You may obtain a copy of the License at
9
10 http://www.apache.org/licenses/LICENSE-2.0
11
12Unless required by applicable law or agreed to in writing, software
13distributed under the License is distributed on an "AS IS" BASIS,
14WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
15See the License for the specific language governing permissions and
16limitations under the License.
17
18For more information please visit: http://bitmagic.io
19*/
20
21/*! \file bmsparsevec_compr.h
22 \brief Compressed sparse container rsc_sparse_vector<> for integer types
23*/
24
25#include <memory.h>
26
27#ifndef BM_NO_STL
28#include <stdexcept>
29#endif
30
31#ifndef BM__H__INCLUDED__
32// BitMagic utility headers do not include main "bm.h" declaration
33// #include "bm.h" or "bm64.h" explicitly
34# error missing include (bm.h or bm64.h)
35#endif
36
37
38#include "bmsparsevec.h"
39#include "bmdef.h"
40
41namespace bm
42{
43
44
45/*!
46 \brief Rank-Select compressed sparse vector
47
48 Container uses Rank-Select method of compression, where
49 all NULL columns gets dropped, effective address of columns is computed
50 using address bit-vector.
51
52 Use for cases, where memory efficiency is preferable over
53 single element access latency.
54
55 \ingroup sv
56*/
57template<class Val, class SV>
59{
60public:
62 {
63 sv_plains = (sizeof(Val) * 8 + 1),
64 sv_value_plains = (sizeof(Val) * 8)
65 };
66
67 typedef Val value_type;
69 typedef typename SV::size_type size_type;
71 typedef typename SV::const_iterator sparse_vector_const_iterator;
72 typedef typename SV::bvector_type bvector_type;
79 typedef typename SV::bmatrix_type bmatrix_type;
80
85
86 struct is_remap_support { enum trait { value = false }; };
87 struct is_rsc_support { enum trait { value = true }; };
88
89public:
90 /*! Statistical information about memory allocation details. */
91 struct statistics : public bv_statistics
92 {};
93
94public:
95 /**
96 Reference class to access elements via common [] operator
97 */
99 {
100 public:
102 : csv_(csv), idx_(idx)
103 {}
104 operator value_type() const BMNOEXCEPT { return csv_.get(idx_); }
105 bool operator==(const reference& ref) const BMNOEXCEPT
106 { return bool(*this) == bool(ref); }
107 bool is_null() const BMNOEXCEPT { return csv_.is_null(idx_); }
108 private:
110 size_type idx_;
111 };
112
113 /**
114 Const iterator to traverse the rsc sparse vector.
115
116 Implementation uses buffer for decoding so, competing changes
117 to the original vector may not match the iterator returned values.
118
119 This iterator keeps an operational buffer, memory footprint is not
120 negligable
121
122 @ingroup sv
123 */
125 {
126 public:
127 friend class rsc_sparse_vector;
128
129#ifndef BM_NO_STL
130 typedef std::input_iterator_tag iterator_category;
131#endif
138 typedef typename
140 typedef bm::byte_buffer<allocator_type> buffer_type;
141
142 typedef unsigned difference_type;
143 typedef unsigned* pointer;
145
146 public:
151
152 bool operator==(const const_iterator& it) const BMNOEXCEPT
153 { return (pos_ == it.pos_) && (csv_ == it.csv_); }
155 { return ! operator==(it); }
157 { return pos_ < it.pos_; }
159 { return pos_ <= it.pos_; }
161 { return pos_ > it.pos_; }
163 { return pos_ >= it.pos_; }
164
165 /// \brief Get current position (value)
166 value_type operator*() const { return this->value(); }
167
168
169 /// \brief Advance to the next available value
170 const_iterator& operator++() BMNOEXCEPT { this->advance(); return *this; }
171
172 /// \brief Advance to the next available value
174 { const_iterator tmp(*this);this->advance(); return tmp; }
175
176
177 /// \brief Get current position (value)
178 value_type value() const;
179
180 /// \brief Get NULL status
181 bool is_null() const BMNOEXCEPT;
182
183 /// Returns true if iterator is at a valid position
184 bool valid() const BMNOEXCEPT { return pos_ != bm::id_max; }
185
186 /// Invalidate current iterator
188
189 /// Current position (index) in the vector
190 size_type pos() const BMNOEXCEPT{ return pos_; }
191
192 /// re-position to a specified position
194
195 /// advance iterator forward by one
196 /// @return true if it is still valid
197 bool advance() BMNOEXCEPT;
198
200 private:
201 enum buf_size_e
202 {
203 n_buf_size = 1024 * 8
204 };
205
206 private:
207 const rsc_sparse_vector_type* csv_; ///!< ptr to parent
208 size_type pos_; ///!< Position
209 mutable buffer_type vbuffer_; ///!< value buffer
210 mutable buffer_type tbuffer_; ///!< temp buffer
211 mutable value_type* buf_ptr_; ///!< position in the buffer
212 };
213
214
215
216 /**
217 Back insert iterator implements buffered insert, faster than generic
218 access assignment.
219
220 Limitations for buffered inserter:
221 1. Do not use more than one inserter per vector at a time
222 2. Use method flush() at the end to send the rest of accumulated buffer
223 flush is happening automatically on destruction, but if flush produces an
224 exception (for whatever reason) it will be an exception in destructor.
225 As such, explicit flush() is safer way to finilize the sparse vector load.
226
227 @ingroup sv
228 */
230 {
231 public:
232#ifndef BM_NO_STL
233 typedef std::output_iterator_tag iterator_category;
234#endif
240
241 typedef void difference_type;
242 typedef void pointer;
243 typedef void reference;
244
245 public:
248
250 {
251 BM_ASSERT(bi.empty());
252 this->flush(); sv_bi_ = bi.sv_bi_;
253 return *this;
254 }
255
257
258 /** push value to the vector */
260 { this->add(v); return *this; }
261 /** noop */
262 back_insert_iterator& operator*() { return *this; }
263 /** noop */
264 back_insert_iterator& operator++() { return *this; }
265 /** noop */
266 back_insert_iterator& operator++( int ) { return *this; }
267
268 /** add value to the container*/
269 void add(value_type v);
270
271 /** add NULL (no-value) to the container */
272 void add_null() BMNOEXCEPT;
273
274 /** add a series of consequitve NULLs (no-value) to the container */
276
277 /** flush the accumulated buffer */
278 void flush();
279 protected:
280
281 /** add value to the buffer without changing the NULL vector
282 @param v - value to push back
283 @return index of added value in the internal buffer
284 @internal
285 */
286 ///size_type add_value(value_type v);
287
289 typedef
291 private:
292 rsc_sparse_vector_type* csv_; ///!< pointer on the parent vector
293 sparse_vector_bi sv_bi_;
294 };
295
296public:
297 // ------------------------------------------------------------
298 /*! @name Construction and assignment */
299 //@{
300
303 size_type bv_max_size = bm::id_max,
304 const allocator_type& alloc = allocator_type());
306
307 /*! copy-ctor */
308 rsc_sparse_vector(const rsc_sparse_vector<Val, SV>& csv);
309
310
311 /*! copy assignmment operator */
312 rsc_sparse_vector<Val,SV>& operator=(const rsc_sparse_vector<Val, SV>& csv)
313 {
314 if (this != &csv)
315 {
316 sv_ = csv.sv_;
317 size_ = csv.size_; max_id_ = csv.max_id_;
318 in_sync_ = csv.in_sync_;
319 if (in_sync_)
320 {
321 bv_blocks_ptr_->copy_from(*(csv.bv_blocks_ptr_));
322 }
323 }
324 return *this;
325 }
326
327#ifndef BM_NO_CXX11
328 /*! move-ctor */
330
331 /*! move assignmment operator */
333 {
334 if (this != &csv)
335 {
336 clear();
337 sv_.swap(csv.sv_);
338 size_ = csv.size_; max_id_ = csv.max_id_; in_sync_ = csv.in_sync_;
339 if (in_sync_)
340 {
341 bv_blocks_ptr_->copy_from(*(csv.bv_blocks_ptr_));
342 }
343 }
344 return *this;
345 }
346#endif
347
348 //@}
349 // ------------------------------------------------------------
350 /*! @name Size, etc */
351 ///@{
352
353 /*! \brief return size of the vector
354 \return size of sparse vector
355 */
356 size_type size() const BMNOEXCEPT;
357
358 /*! \brief return true if vector is empty
359 \return true if empty
360 */
361 bool empty() const { return sv_.empty(); }
362
363 ///@}
364
365 // ------------------------------------------------------------
366 /*! @name Element access */
367 //@{
368
369 /*!
370 \brief get specified element without bounds checking
371 \param idx - element index
372 \return value of the element
373 */
374 value_type operator[](size_type idx) const { return this->get(idx); }
375
376 /*!
377 \brief access specified element with bounds checking
378 \param idx - element index
379 \return value of the element
380 */
381 value_type at(size_type idx) const;
382
383 /*!
384 \brief get specified element without bounds checking
385 \param idx - element index
386 \return value of the element
387 */
389
390 /*!
391 \brief set specified element with bounds checking and automatic resize
392
393 Method cannot insert elements, so every new idx has to be greater or equal
394 than what it used before. Elements must be loaded in a sorted order.
395
396 \param idx - element index
397 \param v - element value
398 */
399 void push_back(size_type idx, value_type v);
400
401 /*!
402 \brief set specified element with bounds checking and automatic resize
403 \param idx - element index
404 \param v - element value
405 */
406 void set(size_type idx, value_type v);
407
408 /*!
409 \brief set specified element to NULL
410 RSC vector actually erases element when it is set to NULL (expensive).
411 \param idx - element index
412 */
413 void set_null(size_type idx);
414
415
416
417 /** \brief test if specified element is NULL
418 \param idx - element index
419 \return true if it is NULL false if it was assigned or container
420 is not configured to support assignment flags
421 */
422 bool is_null(size_type idx) const BMNOEXCEPT;
423
424 /**
425 \brief Get bit-vector of assigned values (or NULL)
426 */
428
429 /**
430 \brief find position of compressed element by its rank
431 \param rank - rank (virtual index in sparse vector)
432 \param idx - index (true position)
433 */
434 bool find_rank(size_type rank, size_type& idx) const BMNOEXCEPT;
435
436 //@}
437
438 // ------------------------------------------------------------
439 /*! @name Export content to C-stype array */
440 ///@{
441
442 /**
443 \brief C-style decode
444 \param arr - decode target array (must be properly sized)
445 \param idx_from - start address to decode
446 \param size - number of elements to decode
447 \param zero_mem - flag if array needs to beset to zeros first
448
449 @return actual decoded size
450 @sa decode_buf
451 */
453 size_type idx_from,
455 bool zero_mem = true) const;
456
457
458 /**
459 \brief C-style decode (variant with external memory)
460 Analog of decode, but requires two arrays.
461 Faster than decode in many cases.
462
463 \param arr - decode target array (must be properly sized)
464 \param arr_buf_tmp - decode temp bufer (must be same size of arr)
465 \param idx_from - start address to decode
466 \param size - number of elements to decode
467 \param zero_mem - flag if array needs to beset to zeros first
468
469 @return actual decoded size
470 @sa decode
471 */
473 value_type* arr_buf_tmp,
474 size_type idx_from,
476 bool zero_mem = true) const BMNOEXCEPT;
477
478 ///@}
479
480
481 // ------------------------------------------------------------
482 /*! @name Various traits */
483 //@{
484 /**
485 \brief if container supports NULL(unassigned) values (true)
486 */
487 bool is_nullable() const { return true; }
488
489 /** \brief trait if sparse vector is "compressed" (true)
490 */
491 static
492 bool is_compressed() { return true; }
493
494 ///@}
495
496
497 // ------------------------------------------------------------
498 /*! @name Comparison */
499 //@{
500
501 /*!
502 \brief check if another vector has the same content
503 \return true, if it is the same
504 */
505 bool equal(const rsc_sparse_vector<Val, SV>& csv) const BMNOEXCEPT;
506 //@}
507
508
509 // ------------------------------------------------------------
510 /*! @name Load-Export compressed vector with data */
511
512 //@{
513
514
515 /*!
516 \brief Load compressed vector from a sparse vector (with NULLs)
517 \param sv_src - source sparse vector
518 */
519 void load_from(const sparse_vector_type& sv_src);
520
521 /*!
522 \brief Exort compressed vector to a sparse vector (with NULLs)
523 \param sv - target sparse vector
524 */
525 void load_to(sparse_vector_type& sv) const;
526
527 //@}
528
529 // ------------------------------------------------------------
530 /*! @name Iterator access */
531 //@{
532
533 /** Provide const iterator access to container content */
535 { return const_iterator(this); }
536
537 /** Provide const iterator access to the end */
539 { return const_iterator(this, bm::id_max); }
540
541 /** Get const_itertor re-positioned to specific element
542 @param idx - position in the sparse vector
543 */
546
548 ///@}
549
550 // ------------------------------------------------------------
551 /*! @name Memory optimization */
552 ///@{
553
554 /*!
555 \brief run memory optimization for all vector plains
556 \param temp_block - pre-allocated memory block to avoid unnecessary re-allocs
557 \param opt_mode - requested compression depth
558 \param stat - memory allocation statistics after optimization
559 */
560 void optimize(
561 bm::word_t* temp_block = 0,
563 statistics* stat = 0);
564
565 /*! \brief resize to zero, free memory
566 */
567 void clear() BMNOEXCEPT;
568
569 /*!
570 @brief Calculates memory statistics.
571
572 Function fills statistics structure containing information about how
573 this vector uses memory and estimation of max. amount of memory
574 bvector needs to serialize itself.
575
576 @param st - pointer on statistics structure to be filled in.
577
578 @sa statistics
579 */
580 void calc_stat(
581 struct rsc_sparse_vector<Val, SV>::statistics* st) const BMNOEXCEPT;
582
583 ///@}
584
585 // ------------------------------------------------------------
586 /*! @name Merge, split, partition data */
587 ///@{
588
589 /**
590 @brief copy range of values from another sparse vector
591
592 Copy [left..right] values from the source vector,
593 clear everything outside the range.
594
595 \param csv - source vector
596 \param left - index from in losed diapason of [left..right]
597 \param right - index to in losed diapason of [left..right]
598 */
599 void copy_range(const rsc_sparse_vector<Val, SV>& csv,
600 size_type left, size_type right);
601
602 ///@}
603
604 // ------------------------------------------------------------
605 /*! @name Fast access structues sync */
606 //@{
607 /*!
608 \brief Re-calculate prefix sum table used for rank search
609 \param force - force recalculation even if it is already recalculated
610 */
611 void sync(bool force);
612
613 /*!
614 \brief Re-calculate prefix sum table used for rank search (if necessary)
615 */
616 void sync() { sync(false); }
617
618 /*!
619 \brief returns true if prefix sum table is in sync with the vector
620 */
621 bool in_sync() const BMNOEXCEPT { return in_sync_; }
622
623 /*!
624 \brief Unsync the prefix sum table
625 */
626 void unsync() BMNOEXCEPT { in_sync_ = false; }
627 ///@}
628
629 // ------------------------------------------------------------
630 /*! @name Access to internals */
631 ///@{
632
633 /*!
634 \brief get access to bit-plain, function checks and creates a plain
635 \return bit-vector for the bit plain
636 */
638 { return sv_.get_plain(i); }
639
641 { return sv_.get_plain(i); }
642
643 /*!
644 Number of effective bit-plains in the value type
645 */
647 { return sv_.effective_plains(); }
648
649 /*!
650 \brief get total number of bit-plains in the vector
651 */
652 static unsigned plains() BMNOEXCEPT
653 { return sparse_vector_type::plains(); }
654
655 /** Number of stored bit-plains (value plains + extra */
656 static unsigned stored_plains()
657 { return sparse_vector_type::stored_plains(); }
658
659 /*!
660 \brief access dense vector
661 */
662 const sparse_vector_type& get_sv() const BMNOEXCEPT { return sv_; }
663
664 /*!
665 \brief size of internal dense vector
666 */
667 size_type effective_size() const BMNOEXCEPT { return sv_.size(); }
668
669 /**
670 \brief Always 1 (non-matrix type)
671 */
673
674 /*!
675 get read-only access to inetrnal bit-matrix
676 */
678 { return sv_.get_bmatrix(); }
679
680 ///@}
681
682protected:
684 {
686 };
687
688 /*!
689 \brief Resolve logical address to access via rank compressed address
690
691 \param idx - input id to resolve
692 \param idx_to - output id
693
694 \return true if id is known and resolved successfully
695 */
696 bool resolve(size_type idx, size_type* idx_to) const BMNOEXCEPT;
697
698 bool resolve_range(size_type from, size_type to,
699 size_type* idx_from, size_type* idx_to) const BMNOEXCEPT;
700
701 void resize_internal(size_type sz) { sv_.resize_internal(sz); }
702 size_type size_internal() const BMNOEXCEPT { return sv_.size(); }
703
704 bool is_remap() const BMNOEXCEPT { return false; }
705 size_t remap_size() const BMNOEXCEPT { return 0; }
706 const unsigned char* get_remap_buffer() const BMNOEXCEPT { return 0; }
707 unsigned char* init_remap_buffer() BMNOEXCEPT { return 0; }
709
711
712
713private:
714 void construct_bv_blocks();
715 void free_bv_blocks();
716
717protected:
718 template<class SVect> friend class sparse_vector_scanner;
719 template<class SVect> friend class sparse_vector_serializer;
720 template<class SVect> friend class sparse_vector_deserializer;
721
722private:
723 sparse_vector_type sv_; ///< transpose-sparse vector for "dense" packing
724 size_type size_; ///< vector size (logical)
725 size_type max_id_; ///< control variable for sorted load
726 bool in_sync_; ///< flag if prefix sum is in-sync with vector
727 rs_index_type* bv_blocks_ptr_ = 0; ///< prefix sum for rank translation
728};
729
730//---------------------------------------------------------------------
731//
732//---------------------------------------------------------------------
733
734template<class Val, class SV>
737 size_type bv_max_size,
738 const allocator_type& alloc)
739: sv_(null_able, ap, bv_max_size, alloc), in_sync_(false)
740{
741 BM_ASSERT(null_able == bm::use_null);
742 BM_ASSERT(int(sv_value_plains) == int(SV::sv_value_plains));
743 size_ = max_id_ = 0;
744 construct_bv_blocks();
745}
746
747//---------------------------------------------------------------------
748
749template<class Val, class SV>
751{
752 free_bv_blocks();
753}
754
755//---------------------------------------------------------------------
756
757template<class Val, class SV>
760: sv_(csv.sv_), size_(csv.size_), max_id_(csv.max_id_), in_sync_(csv.in_sync_)
761{
762 BM_ASSERT(int(sv_value_plains) == int(SV::sv_value_plains));
763
764 construct_bv_blocks();
765 if (in_sync_)
766 bv_blocks_ptr_->copy_from(*(csv.bv_blocks_ptr_));
767}
768
769//---------------------------------------------------------------------
770
771template<class Val, class SV>
774: sv_(bm::use_null),
775 size_(0),
776 max_id_(0), in_sync_(false)
777{
778 if (this != &csv)
779 {
780 sv_.swap(csv.sv_);
781 size_ = csv.size_; max_id_ = csv.max_id_; in_sync_ = csv.in_sync_;
782 bv_blocks_ptr_ = csv.bv_blocks_ptr_; csv.bv_blocks_ptr_ = 0;
783 }
784}
785
786//---------------------------------------------------------------------
787
788template<class Val, class SV>
791{
792 return size_;
793}
794
795//---------------------------------------------------------------------
796
797template<class Val, class SV>
799{
800 if (sv_.empty())
801 {}
802 else
803 if (idx <= max_id_ && size_)
804 {
805 sv_.throw_range_error("compressed sparse vector push_back() range error");
806 }
807 push_back_no_check(idx, v);
808}
809
810//---------------------------------------------------------------------
811
812template<class Val, class SV>
814{
815 bvector_type* bv_null = sv_.get_null_bvect();
816 BM_ASSERT(bv_null);
817
818 bv_null->set_bit_no_check(idx);
819 sv_.push_back_no_null(v);
820
821 max_id_ = idx;
822 size_ = idx + 1;
823 in_sync_ = false;
824}
825
826//---------------------------------------------------------------------
827
828template<class Val, class SV>
830{
831 bvector_type* bv_null = sv_.get_null_bvect();
832 BM_ASSERT(bv_null);
833
834 bool found = bv_null->test(idx);
835 if (found)
836 {
837 size_type sv_idx = bv_null->count_range(0, idx);
838 bv_null->clear_bit_no_check(idx);
839 sv_.erase(--sv_idx);
840 in_sync_ = false;
841 }
842}
843
844//---------------------------------------------------------------------
845
846template<class Val, class SV>
848{
849 bvector_type* bv_null = sv_.get_null_bvect();
850 BM_ASSERT(bv_null);
851
852 bool found = bv_null->test(idx);
853 size_type sv_idx = bv_null->count_range(0, idx); // TODO: make test'n'count
854 if (found)
855 {
856 sv_.set_value_no_null(--sv_idx, v);
857 }
858 else
859 {
860 sv_.insert_value_no_null(sv_idx, v);
861 bv_null->set_bit_no_check(idx);
862
863 if (idx > max_id_)
864 {
865 max_id_ = idx;
866 size_ = max_id_ + 1;
867 }
868 in_sync_ = false;
869 }
870}
871
872//---------------------------------------------------------------------
873
874template<class Val, class SV>
876 const rsc_sparse_vector<Val, SV>& csv) const BMNOEXCEPT
877{
878 if (this == &csv)
879 return true;
880 if (max_id_ != csv.max_id_ || size_ != csv.size_)
881 return false;
882 bool same_sv = sv_.equal(csv.sv_);
883 return same_sv;
884}
885
886//---------------------------------------------------------------------
887
888template<class Val, class SV>
890 const sparse_vector_type& sv_src)
891{
892 max_id_ = size_ = 0;
893
894 bvector_type* bv_null = sv_.get_null_bvect();
895 BM_ASSERT(bv_null);
896
897 const bvector_type* bv_null_src = sv_src.get_null_bvector();
898 if (!bv_null_src) // dense vector (no NULL columns)
899 {
900 sv_ = sv_src;
901 BM_ASSERT(sv_.get_null_bvect());
902 }
903 else
904 {
905 sv_.clear();
906 *bv_null = *bv_null_src;
907
908 bm::rank_compressor<bvector_type> rank_compr; // re-used for plains
909
910 unsigned src_plains = sv_src.plains();
911 for (unsigned i = 0; i < src_plains; ++i)
912 {
913 const bvector_type* bv_src_plain = sv_src.get_plain(i);
914 if (bv_src_plain)
915 {
916 bvector_type* bv_plain = sv_.get_plain(i);
917 rank_compr.compress(*bv_plain, *bv_null, *bv_src_plain);
918 }
919 } // for
920 size_type count = bv_null->count(); // set correct sizes
921 sv_.resize(count);
922 }
923
924 sync(true);
925}
926
927//---------------------------------------------------------------------
928
929template<class Val, class SV>
931{
932 sv.clear();
933
934 const bvector_type* bv_null_src = this->get_null_bvector();
935 if (!bv_null_src)
936 {
937 BM_ASSERT(bv_null_src);
938 return;
939 }
940
941 bvector_type* bv_null = sv.get_null_bvect();
942 BM_ASSERT(bv_null);
943 *bv_null = *bv_null_src;
944
945 bm::rank_compressor<bvector_type> rank_compr; // re-used for plains
946
947 unsigned src_plains = sv_.plains();
948 for (unsigned i = 0; i < src_plains; ++i)
949 {
950 const bvector_type* bv_src_plain = sv_.get_plain(i);
951 if (bv_src_plain)
952 {
953 bvector_type* bv_plain = sv.get_plain(i);
954 rank_compr.decompress(*bv_plain, *bv_null, *bv_src_plain);
955 }
956 } // for
957 sv.resize(this->size());
958}
959
960//---------------------------------------------------------------------
961
962template<class Val, class SV>
964{
965 if (in_sync_ && force == false)
966 return; // nothing to do
967 const bvector_type* bv_null = sv_.get_null_bvector();
968 BM_ASSERT(bv_null);
969 bv_null->build_rs_index(bv_blocks_ptr_); // compute popcount prefix list
970
971 // sync the max-id
972 bool found = bv_null->find_reverse(max_id_);
973 if (!found)
974 {
975 BM_ASSERT(!bv_null->any());
976 max_id_ = size_ = 0;
977 }
978 else
979 {
980 size_ = max_id_ + 1;
981 }
982 in_sync_ = true;
983}
984
985//---------------------------------------------------------------------
986
987template<class Val, class SV>
989 size_type* idx_to) const BMNOEXCEPT
990{
991 BM_ASSERT(idx_to);
992 const bvector_type* bv_null = sv_.get_null_bvector();
993 if (in_sync_)
994 {
995 *idx_to = bv_null->count_to_test(idx, *bv_blocks_ptr_);
996 }
997 else // slow access
998 {
999 bool found = bv_null->test(idx);
1000 *idx_to = found ? bv_null->count_range(0, idx) : 0;
1001 }
1002 return bool(*idx_to);
1003}
1004
1005//---------------------------------------------------------------------
1006
1007template<class Val, class SV>
1009 size_type from, size_type to,
1010 size_type* idx_from, size_type* idx_to) const BMNOEXCEPT
1011{
1012 BM_ASSERT(idx_to && idx_from);
1013 const bvector_type* bv_null = sv_.get_null_bvector();
1014 size_type copy_sz, sv_left;
1015 if (in_sync_)
1016 copy_sz = bv_null->count_range(from, to, *bv_blocks_ptr_);
1017 else // slow access
1018 copy_sz = bv_null->count_range(from, to);
1019 if (!copy_sz)
1020 return false;
1021
1022 if (in_sync_)
1023 sv_left = bv_null->rank_corrected(from, *bv_blocks_ptr_);
1024 else
1025 {
1026 sv_left = bv_null->count_range(0, from);
1027 bool tl = bv_null->test(from); // TODO: add count and test
1028 sv_left -= tl; // rank correction
1029 }
1030
1031 *idx_from = sv_left; *idx_to = sv_left + copy_sz - 1;
1032 return true;
1033}
1034
1035
1036//---------------------------------------------------------------------
1037
1038template<class Val, class SV>
1041{
1042 size_type sv_idx;
1043 if (idx >= size())
1044 sv_.throw_range_error("compressed collection access error");
1045
1046 bool found = resolve(idx, &sv_idx);
1047 if (!found)
1048 {
1049 sv_.throw_range_error("compressed collection item not found");
1050 }
1051 return sv_.at(--sv_idx);
1052}
1053
1054//---------------------------------------------------------------------
1055
1056template<class Val, class SV>
1059{
1060 size_type sv_idx;
1061 bool found = resolve(idx, &sv_idx);
1062 if (!found)
1063 return value_type(0);
1064
1065 return sv_.get(--sv_idx);
1066}
1067
1068//---------------------------------------------------------------------
1069
1070template<class Val, class SV>
1072{
1073 const bvector_type* bv_null = sv_.get_null_bvector();
1074 BM_ASSERT(bv_null);
1075 return !(bv_null->test(idx));
1076}
1077
1078//---------------------------------------------------------------------
1079
1080template<class Val, class SV>
1082 typename bvector_type::optmode opt_mode,
1083 statistics* st)
1084{
1085 sv_.optimize(temp_block, opt_mode, (typename sparse_vector_type::statistics*)st);
1086 if (st)
1087 {
1088 st->memory_used += sizeof(rs_index_type);
1089 st->memory_used += bv_blocks_ptr_->get_total() *
1090 (sizeof(typename rs_index_type::size_type)
1091 + sizeof(typename rs_index_type::sb_pair_type));
1092 }
1093}
1094
1095//---------------------------------------------------------------------
1096
1097template<class Val, class SV>
1099{
1100 sv_.clear();
1101 in_sync_ = false; max_id_ = size_ = 0;
1102}
1103
1104//---------------------------------------------------------------------
1105
1106template<class Val, class SV>
1109{
1110 BM_ASSERT(st);
1111 sv_.calc_stat((typename sparse_vector_type::statistics*)st);
1112 if (st)
1113 {
1114 st->memory_used += sizeof(rs_index_type);
1115 st->memory_used += bv_blocks_ptr_->get_total() *
1116 (sizeof(typename rs_index_type::size_type)
1117 + sizeof(typename rs_index_type::sb_pair_type));
1118 }
1119}
1120
1121//---------------------------------------------------------------------
1122
1123template<class Val, class SV>
1126{
1127 return sv_.get_null_bvector();
1128}
1129
1130//---------------------------------------------------------------------
1131
1132template<class Val, class SV>
1133bool
1135 size_type& idx) const BMNOEXCEPT
1136{
1137 BM_ASSERT(rank);
1138 bool b;
1139 const bvector_type* bv_null = get_null_bvector();
1140 if (in_sync())
1141 b = bv_null->select(rank, idx, *bv_blocks_ptr_);
1142 else
1143 b = bv_null->find_rank(rank, 0, idx);
1144 return b;
1145}
1146
1147//---------------------------------------------------------------------
1148
1149
1150template<class Val, class SV>
1153 size_type idx_from,
1154 size_type size,
1155 bool zero_mem) const
1156{
1157 if (size == 0)
1158 return 0;
1159
1160 BM_ASSERT(arr);
1161 BM_ASSERT(in_sync_); // call sync() before decoding
1162 BM_ASSERT(bv_blocks_ptr_);
1163
1164 if (idx_from >= this->size())
1165 return 0;
1166
1167 if ((bm::id_max - size) <= idx_from)
1168 size = bm::id_max - idx_from;
1169 if ((idx_from + size) > this->size())
1170 size = this->size() - idx_from;
1171
1172 const bvector_type* bv_null = sv_.get_null_bvector();
1173 size_type rank = bv_null->rank_corrected(idx_from, *bv_blocks_ptr_);
1174
1175 BM_ASSERT(rank == bv_null->count_range(0, idx_from) - bv_null->test(idx_from));
1176
1177 bvector_enumerator_type en_i = bv_null->get_enumerator(idx_from);
1178 BM_ASSERT(en_i.valid());
1179
1180 if (zero_mem)
1181 ::memset(arr, 0, sizeof(value_type)*size);
1182
1183 sparse_vector_const_iterator it = sv_.get_const_iterator(rank);
1184 size_type i = 0;
1185 if (it.valid())
1186 {
1187 do
1188 {
1189 size_type en_idx = *en_i;
1190 size_type delta = en_idx - idx_from;
1191 idx_from += delta;
1192 i += delta;
1193 if (i >= size)
1194 return size;
1195 arr[i++] = it.value();
1196 if (!en_i.advance())
1197 break;
1198 if (!it.advance())
1199 break;
1200 ++idx_from;
1201 } while (i < size);
1202 }
1203 return i;
1204}
1205
1206
1207template<class Val, class SV>
1210 value_type* arr_buf_tmp,
1211 size_type idx_from,
1212 size_type size,
1213 bool zero_mem) const BMNOEXCEPT
1214{
1215 if (!size || (idx_from >= this->size()))
1216 return 0;
1217
1218 BM_ASSERT(arr && arr_buf_tmp);
1219 BM_ASSERT(arr != arr_buf_tmp);
1220 BM_ASSERT(in_sync_); // call sync() before decoding
1221 BM_ASSERT(bv_blocks_ptr_);
1222
1223 if ((bm::id_max - size) <= idx_from)
1224 size = bm::id_max - idx_from;
1225 if ((idx_from + size) > this->size())
1226 size = this->size() - idx_from;
1227
1228 if (zero_mem)
1229 ::memset(arr, 0, sizeof(value_type)*size);
1230
1231 const bvector_type* bv_null = sv_.get_null_bvector();
1232 size_type rank = bv_null->rank_corrected(idx_from, *bv_blocks_ptr_);
1233
1234 BM_ASSERT(rank == bv_null->count_range(0, idx_from) - bv_null->test(idx_from));
1235
1236 bvector_enumerator_type en_i = bv_null->get_enumerator(idx_from);
1237 if (!en_i.valid())
1238 return size;
1239
1240 size_type i = en_i.value();
1241 if (idx_from + size <= i) // empty space (all zeros)
1242 return size;
1243
1244 size_type extract_cnt =
1245 bv_null->count_range(idx_from, idx_from + size - 1, *bv_blocks_ptr_);
1246
1247 BM_ASSERT(extract_cnt <= this->size());
1248 auto ex_sz = sv_.decode(arr_buf_tmp, rank, extract_cnt, true);
1249 BM_ASSERT(ex_sz == extract_cnt); (void) ex_sz;
1250
1251 for (i = 0; i < extract_cnt; ++i)
1252 {
1253 BM_ASSERT(en_i.valid());
1254 size_type en_idx = *en_i;
1255 arr[en_idx-idx_from] = arr_buf_tmp[i];
1256 en_i.advance();
1257 } // for i
1258
1259 return size;
1260}
1261
1262
1263//---------------------------------------------------------------------
1264
1265template<class Val, class SV>
1267{
1268 if (bv_blocks_ptr_)
1269 return;
1270 bv_blocks_ptr_ =
1271 (rs_index_type*) bm::aligned_new_malloc(sizeof(rs_index_type));
1272 bv_blocks_ptr_ = new(bv_blocks_ptr_) rs_index_type(); // placement new
1273}
1274
1275//---------------------------------------------------------------------
1276
1277template<class Val, class SV>
1278void rsc_sparse_vector<Val, SV>::free_bv_blocks()
1279{
1280 if (bv_blocks_ptr_)
1281 {
1282 bv_blocks_ptr_->~rs_index_type();
1283 bm::aligned_free(bv_blocks_ptr_);
1284 }
1285}
1286
1287//---------------------------------------------------------------------
1288
1289template<class Val, class SV>
1291 const rsc_sparse_vector<Val, SV>& csv,
1292 size_type left, size_type right)
1293{
1294 if (left > right)
1295 bm::xor_swap(left, right);
1296
1297 if (left >= csv.size())
1298 return;
1299
1300 size_ = csv.size_; max_id_ = csv.max_id_;
1301 in_sync_ = false;
1302
1303 const bvector_type* arg_bv_null = csv.sv_.get_null_bvector();
1304 size_type sv_left, sv_right;
1305 bool range_valid = csv.resolve_range(left, right, &sv_left, &sv_right);
1306 if (!range_valid)
1307 {
1308 sv_.clear(); sv_.resize(size_);
1309 bvector_type* bv_null = sv_.get_null_bvect();
1310 bv_null->copy_range(*arg_bv_null, 0, right);
1311 return;
1312 }
1313 bvector_type* bv_null = sv_.get_null_bvect();
1314 bv_null->copy_range(*arg_bv_null, 0, right); // not NULL vector gets a full copy
1315 sv_.copy_range(csv.sv_, sv_left, sv_right, bm::no_null); // don't copy NULL
1316}
1317
1318
1319
1320
1321//---------------------------------------------------------------------
1322//
1323//---------------------------------------------------------------------
1324
1325
1326template<class Val, class SV>
1330
1331
1332//---------------------------------------------------------------------
1333
1334template<class Val, class SV>
1337{
1338 csv_ = csv;
1339 sv_bi_ = csv->sv_.get_back_inserter();
1340 sv_bi_.disable_set_null(); // NULL is handled outside
1341}
1342
1343//---------------------------------------------------------------------
1344
1345template<class Val, class SV>
1350
1351//---------------------------------------------------------------------
1352
1353template<class Val, class SV>
1356{
1357 BM_ASSERT(csv_);
1358 sv_bi_.add_value_no_null(v);
1359 bvector_type* bv_null = sv_bi_.get_null_bvect();
1360 BM_ASSERT(bv_null);
1361 bv_null->set_bit_no_check(csv_->size_);
1362
1363 csv_->max_id_++;
1364 csv_->size_++;
1365}
1366
1367//---------------------------------------------------------------------
1368
1369template<class Val, class SV>
1371{
1372 BM_ASSERT(csv_);
1373 csv_->max_id_++;
1374 csv_->size_++;
1375}
1376
1377//---------------------------------------------------------------------
1378
1379template<class Val, class SV>
1382{
1383 BM_ASSERT(csv_);
1384 csv_->max_id_+=count;
1385 csv_->size_+=count;
1386}
1387
1388//---------------------------------------------------------------------
1389
1390template<class Val, class SV>
1392{
1393 sv_bi_.flush();
1394 csv_->in_sync_ = false;
1395}
1396
1397//---------------------------------------------------------------------
1398//
1399//---------------------------------------------------------------------
1400
1401template<class Val, class BV>
1405
1406//---------------------------------------------------------------------
1407
1408template<class Val, class SV>
1411: csv_(it.csv_), pos_(it.pos_), buf_ptr_(0)
1412{}
1413
1414//---------------------------------------------------------------------
1415
1416template<class Val, class SV>
1419 ) BMNOEXCEPT
1420: csv_(csv), buf_ptr_(0)
1421{
1422 BM_ASSERT(csv_);
1423 pos_ = csv_->empty() ? bm::id_max : 0u;
1424}
1425
1426//---------------------------------------------------------------------
1427
1428template<class Val, class SV>
1432: csv_(csv), buf_ptr_(0)
1433{
1434 BM_ASSERT(csv_);
1435 this->go_to(pos);
1436}
1437
1438//---------------------------------------------------------------------
1439
1440template<class Val, class SV>
1442{
1443 pos_ = (!csv_ || pos >= csv_->size()) ? bm::id_max : pos;
1444 buf_ptr_ = 0;
1445}
1446
1447//---------------------------------------------------------------------
1448
1449template<class Val, class SV>
1451{
1452 if (pos_ == bm::id_max) // nothing to do, we are at the end
1453 return false;
1454 ++pos_;
1455 if (pos_ >= csv_->size())
1456 {
1457 this->invalidate();
1458 return false;
1459 }
1460 if (buf_ptr_)
1461 {
1462 ++buf_ptr_;
1463 if (buf_ptr_ - ((value_type*)vbuffer_.data()) >= n_buf_size)
1464 buf_ptr_ = 0;
1465 }
1466 return true;
1467}
1468
1469//---------------------------------------------------------------------
1470
1471template<class Val, class SV>
1474{
1475 BM_ASSERT(this->valid());
1476 value_type v;
1477
1478 if (!buf_ptr_)
1479 {
1480 vbuffer_.reserve(n_buf_size * sizeof(value_type));
1481 tbuffer_.reserve(n_buf_size * sizeof(value_type));
1482 buf_ptr_ = (value_type*)(vbuffer_.data());
1483 value_type* tmp_buf_ptr = (value_type*) (tbuffer_.data());
1484
1485 csv_->decode_buf(buf_ptr_, tmp_buf_ptr, pos_, n_buf_size, true);
1486 }
1487 v = *buf_ptr_;
1488 return v;
1489}
1490
1491//---------------------------------------------------------------------
1492
1493template<class Val, class SV>
1495{
1496 value_type v = value();
1497 if (buf_ptr_)
1498 {
1499 v = *buf_ptr_;
1500 value_type* buf_end = ((value_type*)vbuffer_.data()) + n_buf_size;
1501 while(!v)
1502 {
1503 ++pos_;
1504 if (++buf_ptr_ < buf_end)
1505 v = *buf_ptr_;
1506 else
1507 break;
1508 }
1509 if (pos_ >= csv_->size())
1510 {
1511 pos_ = bm::id_max;
1512 return;
1513 }
1514 if (buf_ptr_ >= buf_end)
1515 buf_ptr_ = 0;
1516 }
1517}
1518
1519//---------------------------------------------------------------------
1520
1521template<class Val, class SV>
1523{
1524 return csv_->is_null(pos_);
1525}
1526
1527
1528//---------------------------------------------------------------------
1529
1530
1531
1532} // namespace bm
1533
1534#include "bmundef.h"
1535
1536
1537#endif
Definitions(internal)
#define BMNOEXCEPT
Definition bmdef.h:79
#define BM_ASSERT
Definition bmdef.h:130
Sparse constainer sparse_vector<> for integer types using bit-transposition transform.
pre-processor un-defines to avoid global space pollution (internal)
Constant iterator designed to enumerate "ON" bits.
Definition bm.h:600
size_type value() const BMNOEXCEPT
Get current position (value)
Definition bm.h:641
bool advance() BMNOEXCEPT
Definition bm.h:662
bool valid() const BMNOEXCEPT
Checks if iterator is still valid.
Definition bm.h:280
Bitvector Bit-vector container with runtime compression of bits.
Definition bm.h:108
optmode
Optimization mode Every next level means additional checks (better compression vs time)
Definition bm.h:130
@ opt_compress
compress blocks when possible (GAP/prefix sum)
Definition bm.h:134
allocator_type::allocator_pool_type allocator_pool_type
Definition bm.h:111
rs_index< allocator_type > rs_index_type
Definition bm.h:831
Alloc allocator_type
Definition bm.h:110
Algorithms for rank compression of bit-vector.
Definition bmalgo.h:408
void decompress(BV &bv_target, const BV &bv_idx, const BV &bv_src)
Rank decompression.
Definition bmalgo.h:525
void compress(BV &bv_target, const BV &bv_idx, const BV &bv_src)
Rank compression algorithm based on two palallel iterators/enumerators set of source vector gets re-m...
Definition bmalgo.h:452
Back insert iterator implements buffered insert, faster than generic access assignment.
void flush()
flush the accumulated buffer
rsc_sparse_vector_type::sparse_vector_type sparse_vector_type
add value to the buffer without changing the NULL vector
void add(value_type v)
add value to the container
rsc_sparse_vector_type::bvector_type bvector_type
back_insert_iterator & operator=(value_type v)
push value to the vector
rsc_sparse_vector< Val, SV > rsc_sparse_vector_type
rsc_sparse_vector_type::size_type size_type
rsc_sparse_vector_type::value_type value_type
back_insert_iterator & operator++(int)
noop
void add_null() BMNOEXCEPT
add NULL (no-value) to the container
sparse_vector_type::back_insert_iterator sparse_vector_bi
Const iterator to traverse the rsc sparse vector.
const_iterator & operator++() BMNOEXCEPT
Advance to the next available value.
bool advance() BMNOEXCEPT
advance iterator forward by one
rsc_sparse_vector< Val, SV > rsc_sparse_vector_type
size_type pos() const BMNOEXCEPT
Current position (index) in the vector.
rsc_sparse_vector_type::value_type value_type
bool operator!=(const const_iterator &it) const BMNOEXCEPT
bool operator<=(const const_iterator &it) const BMNOEXCEPT
bool operator>(const const_iterator &it) const BMNOEXCEPT
bm::byte_buffer< allocator_type > buffer_type
void go_to(size_type pos) BMNOEXCEPT
re-position to a specified position
bool operator<(const const_iterator &it) const BMNOEXCEPT
bool operator==(const const_iterator &it) const BMNOEXCEPT
bool is_null() const BMNOEXCEPT
Get NULL status.
rsc_sparse_vector_type::bvector_type bvector_type
rsc_sparse_vector_type * rsc_sparse_vector_type_ptr
const_iterator & operator++(int)
Advance to the next available value.
bool valid() const BMNOEXCEPT
Returns true if iterator is at a valid position.
void invalidate() BMNOEXCEPT
Invalidate current iterator.
bool operator>=(const const_iterator &it) const BMNOEXCEPT
rsc_sparse_vector_type::size_type size_type
bvector_type::allocator_type::allocator_pool_type allocator_pool_type
value_type operator*() const
Get current position (value)
value_type value() const
Get current position (value)
bvector_type::allocator_type allocator_type
Reference class to access elements via common [] operator.
bool operator==(const reference &ref) const BMNOEXCEPT
reference(rsc_sparse_vector< Val, SV > &csv, size_type idx) BMNOEXCEPT
Rank-Select compressed sparse vector.
bvector_type * bvector_type_ptr
bool resolve(size_type idx, size_type *idx_to) const BMNOEXCEPT
Resolve logical address to access via rank compressed address.
void load_from(const sparse_vector_type &sv_src)
Load compressed vector from a sparse vector (with NULLs)
rsc_sparse_vector< Val, SV > & operator=(rsc_sparse_vector< Val, SV > &&csv) BMNOEXCEPT
value_type operator[](size_type idx) const
get specified element without bounds checking
static unsigned plains() BMNOEXCEPT
get total number of bit-plains in the vector
const sparse_vector_type & get_sv() const BMNOEXCEPT
access dense vector
bool is_nullable() const
if container supports NULL(unassigned) values (true)
const bmatrix_type & get_bmatrix() const BMNOEXCEPT
size_type decode(value_type *arr, size_type idx_from, size_type size, bool zero_mem=true) const
C-style decode.
void push_back(size_type idx, value_type v)
set specified element with bounds checking and automatic resize
static unsigned stored_plains()
Number of stored bit-plains (value plains + extra.
back_insert_iterator get_back_inserter()
void load_to(sparse_vector_type &sv) const
Exort compressed vector to a sparse vector (with NULLs)
SV::bmatrix_type bmatrix_type
void set(size_type idx, value_type v)
set specified element with bounds checking and automatic resize
const_iterator end() const BMNOEXCEPT
Provide const iterator access to the end
value_type at(size_type idx) const
access specified element with bounds checking
void optimize(bm::word_t *temp_block=0, typename bvector_type::optmode opt_mode=bvector_type::opt_compress, statistics *stat=0)
run memory optimization for all vector plains
size_type effective_vector_max() const BMNOEXCEPT
Always 1 (non-matrix type)
bvector_type_const_ptr get_plain(unsigned i) const BMNOEXCEPT
get access to bit-plain, function checks and creates a plain
rsc_sparse_vector(bm::null_support null_able=bm::use_null, allocation_policy_type ap=allocation_policy_type(), size_type bv_max_size=bm::id_max, const allocator_type &alloc=allocator_type())
void unsync() BMNOEXCEPT
Unsync the prefix sum table.
bool resolve_range(size_type from, size_type to, size_type *idx_from, size_type *idx_to) const BMNOEXCEPT
size_type effective_size() const BMNOEXCEPT
size of internal dense vector
void set_remap() BMNOEXCEPT
void set_null(size_type idx)
set specified element to NULL RSC vector actually erases element when it is set to NULL (expensive).
bool empty() const
return true if vector is empty
void resize_internal(size_type sz)
size_type decode_buf(value_type *arr, value_type *arr_buf_tmp, size_type idx_from, size_type size, bool zero_mem=true) const BMNOEXCEPT
C-style decode (variant with external memory) Analog of decode, but requires two arrays.
size_type size_internal() const BMNOEXCEPT
SV::const_iterator sparse_vector_const_iterator
bool equal(const rsc_sparse_vector< Val, SV > &csv) const BMNOEXCEPT
check if another vector has the same content
bvector_type_ptr get_plain(unsigned i) BMNOEXCEPT
value_type get(size_type idx) const BMNOEXCEPT
get specified element without bounds checking
static bool is_compressed()
trait if sparse vector is "compressed" (true)
const value_type & const_reference
const_iterator get_const_iterator(size_type idx) const BMNOEXCEPT
Get const_itertor re-positioned to specific element.
const bvector_type * bvector_type_const_ptr
size_t remap_size() const BMNOEXCEPT
void sync()
Re-calculate prefix sum table used for rank search (if necessary)
const unsigned char * get_remap_buffer() const BMNOEXCEPT
unsigned char * init_remap_buffer() BMNOEXCEPT
bool is_null(size_type idx) const BMNOEXCEPT
test if specified element is NULL
unsigned effective_plains() const BMNOEXCEPT
void calc_stat(struct rsc_sparse_vector< Val, SV >::statistics *st) const BMNOEXCEPT
Calculates memory statistics.
bvector_type::allocator_type allocator_type
const bvector_type * get_null_bvector() const BMNOEXCEPT
Get bit-vector of assigned values (or NULL)
void clear() BMNOEXCEPT
resize to zero, free memory
bvector_type::rs_index_type rs_index_type
bool find_rank(size_type rank, size_type &idx) const BMNOEXCEPT
find position of compressed element by its rank
size_type size() const BMNOEXCEPT
return size of the vector
bvector_type::enumerator bvector_enumerator_type
bool in_sync() const BMNOEXCEPT
returns true if prefix sum table is in sync with the vector
void copy_range(const rsc_sparse_vector< Val, SV > &csv, size_type left, size_type right)
copy range of values from another sparse vector
void push_back_no_check(size_type idx, value_type v)
bool is_remap() const BMNOEXCEPT
bvector_type::allocation_policy allocation_policy_type
SV::bvector_type bvector_type
const_iterator begin() const BMNOEXCEPT
Provide const iterator access to container content
sparse vector de-serializer
algorithms for sparse_vector scan/search
null_support
NULL-able value support.
Definition bmconst.h:214
@ use_null
support "non-assigned" or "NULL" logic
Definition bmconst.h:215
@ no_null
do not support NULL values
Definition bmconst.h:216
Definition bm.h:77
void xor_swap(W &x, W &y) BMNOEXCEPT
XOR swap two scalar variables.
Definition bmfunc.h:909
const unsigned id_max
Definition bmconst.h:108
unsigned int word_t
Definition bmconst.h:38
void aligned_free(void *ptr) BMNOEXCEPT
Aligned free.
Definition bmalloc.h:424
void * aligned_new_malloc(size_t size)
Aligned malloc (unlike classic malloc it throws bad_alloc exception)
Definition bmalloc.h:396
Structure with statistical information about memory allocation footprint, serialization projection,...
Definition bmfunc.h:55
size_t memory_used
memory usage for all blocks and service tables
Definition bmfunc.h:61
memory allocation policy
Definition bm.h:820