12 using namespace swift;
16 inline size_t _max_(const size_t x, const size_t y)
21 typedef binmap_t::ref_t ref_t;
22 typedef binmap_t::bitmap_t bitmap_t;
24 /* Bitmap constants */
25 const bitmap_t BITMAP_EMPTY = static_cast<bitmap_t>(0);
26 const bitmap_t BITMAP_FILLED = static_cast<bitmap_t>(-1);
28 const bin_t::uint_t BITMAP_LAYER_BITS = 2 * 8 * sizeof(bitmap_t) - 1;
30 const ref_t ROOT_REF = 0;
33 # pragma warning (push)
34 # pragma warning ( disable:4309 )
37 const bitmap_t BITMAP[] = {
38 static_cast<bitmap_t>(0x00000001), static_cast<bitmap_t>(0x00000003),
39 static_cast<bitmap_t>(0x00000002), static_cast<bitmap_t>(0x0000000f),
40 static_cast<bitmap_t>(0x00000004), static_cast<bitmap_t>(0x0000000c),
41 static_cast<bitmap_t>(0x00000008), static_cast<bitmap_t>(0x000000ff),
42 static_cast<bitmap_t>(0x00000010), static_cast<bitmap_t>(0x00000030),
43 static_cast<bitmap_t>(0x00000020), static_cast<bitmap_t>(0x000000f0),
44 static_cast<bitmap_t>(0x00000040), static_cast<bitmap_t>(0x000000c0),
45 static_cast<bitmap_t>(0x00000080), static_cast<bitmap_t>(0x0000ffff),
46 static_cast<bitmap_t>(0x00000100), static_cast<bitmap_t>(0x00000300),
47 static_cast<bitmap_t>(0x00000200), static_cast<bitmap_t>(0x00000f00),
48 static_cast<bitmap_t>(0x00000400), static_cast<bitmap_t>(0x00000c00),
49 static_cast<bitmap_t>(0x00000800), static_cast<bitmap_t>(0x0000ff00),
50 static_cast<bitmap_t>(0x00001000), static_cast<bitmap_t>(0x00003000),
51 static_cast<bitmap_t>(0x00002000), static_cast<bitmap_t>(0x0000f000),
52 static_cast<bitmap_t>(0x00004000), static_cast<bitmap_t>(0x0000c000),
53 static_cast<bitmap_t>(0x00008000), static_cast<bitmap_t>(0xffffffff),
54 static_cast<bitmap_t>(0x00010000), static_cast<bitmap_t>(0x00030000),
55 static_cast<bitmap_t>(0x00020000), static_cast<bitmap_t>(0x000f0000),
56 static_cast<bitmap_t>(0x00040000), static_cast<bitmap_t>(0x000c0000),
57 static_cast<bitmap_t>(0x00080000), static_cast<bitmap_t>(0x00ff0000),
58 static_cast<bitmap_t>(0x00100000), static_cast<bitmap_t>(0x00300000),
59 static_cast<bitmap_t>(0x00200000), static_cast<bitmap_t>(0x00f00000),
60 static_cast<bitmap_t>(0x00400000), static_cast<bitmap_t>(0x00c00000),
61 static_cast<bitmap_t>(0x00800000), static_cast<bitmap_t>(0xffff0000),
62 static_cast<bitmap_t>(0x01000000), static_cast<bitmap_t>(0x03000000),
63 static_cast<bitmap_t>(0x02000000), static_cast<bitmap_t>(0x0f000000),
64 static_cast<bitmap_t>(0x04000000), static_cast<bitmap_t>(0x0c000000),
65 static_cast<bitmap_t>(0x08000000), static_cast<bitmap_t>(0xff000000),
66 static_cast<bitmap_t>(0x10000000), static_cast<bitmap_t>(0x30000000),
67 static_cast<bitmap_t>(0x20000000), static_cast<bitmap_t>(0xf0000000),
68 static_cast<bitmap_t>(0x40000000), static_cast<bitmap_t>(0xc0000000),
69 static_cast<bitmap_t>(0x80000000), /* special */ static_cast<bitmap_t>(0xffffffff) /* special */
78 * Get the leftmost bin that corresponded to bitmap (the bin is filled in bitmap)
80 bin_t::uint_t bitmap_to_bin(register bitmap_t b)
82 static const unsigned char BITMAP_TO_BIN[] = {
83 0xff, 0, 2, 1, 4, 0, 2, 1, 6, 0, 2, 1, 5, 0, 2, 3,
84 8, 0, 2, 1, 4, 0, 2, 1, 6, 0, 2, 1, 5, 0, 2, 3,
85 10, 0, 2, 1, 4, 0, 2, 1, 6, 0, 2, 1, 5, 0, 2, 3,
86 9, 0, 2, 1, 4, 0, 2, 1, 6, 0, 2, 1, 5, 0, 2, 3,
87 12, 0, 2, 1, 4, 0, 2, 1, 6, 0, 2, 1, 5, 0, 2, 3,
88 8, 0, 2, 1, 4, 0, 2, 1, 6, 0, 2, 1, 5, 0, 2, 3,
89 10, 0, 2, 1, 4, 0, 2, 1, 6, 0, 2, 1, 5, 0, 2, 3,
90 9, 0, 2, 1, 4, 0, 2, 1, 6, 0, 2, 1, 5, 0, 2, 3,
91 14, 0, 2, 1, 4, 0, 2, 1, 6, 0, 2, 1, 5, 0, 2, 3,
92 8, 0, 2, 1, 4, 0, 2, 1, 6, 0, 2, 1, 5, 0, 2, 3,
93 10, 0, 2, 1, 4, 0, 2, 1, 6, 0, 2, 1, 5, 0, 2, 3,
94 9, 0, 2, 1, 4, 0, 2, 1, 6, 0, 2, 1, 5, 0, 2, 3,
95 13, 0, 2, 1, 4, 0, 2, 1, 6, 0, 2, 1, 5, 0, 2, 3,
96 8, 0, 2, 1, 4, 0, 2, 1, 6, 0, 2, 1, 5, 0, 2, 3,
97 10, 0, 2, 1, 4, 0, 2, 1, 6, 0, 2, 1, 5, 0, 2, 3,
98 11, 0, 2, 1, 4, 0, 2, 1, 6, 0, 2, 1, 5, 0, 2, 7
101 assert (sizeof(bitmap_t) <= 4);
102 assert (b != BITMAP_EMPTY);
106 t = BITMAP_TO_BIN[ b & 0xff ];
109 return static_cast<bin_t::uint_t>(t);
115 return BITMAP_LAYER_BITS / 2;
117 if (0 == (b & 0xffff)) {
124 t = BITMAP_TO_BIN[ b & 0xff ];
130 // return 32 + bitmap_to_bin( b >> 8 );
132 assert (sizeof(bitmap_t) == 4);
135 t = BITMAP_TO_BIN[ b & 0xff ];
138 return 32 + static_cast<bin_t::uint_t>(t);
143 if (0 == (b & 0xffff)) {
150 return 48 + BITMAP_TO_BIN[ b & 0xff ];
155 * Get the leftmost bin that corresponded to bitmap (the bin is filled in bitmap)
157 bin_t bitmap_to_bin(const bin_t& bin, const bitmap_t bitmap)
159 assert (bitmap != BITMAP_EMPTY);
161 if (bitmap == BITMAP_FILLED) {
165 return bin_t(bin.base_left().toUInt() + bitmap_to_bin(bitmap));
180 assert (sizeof(bitmap_t) <= 4);
184 allocated_cells_number_ = 0;
185 free_top_ = ROOT_REF;
187 const ref_t root_ref = alloc_cell();
189 assert (root_ref == ROOT_REF && cells_number_ > 0);
196 binmap_t::~binmap_t()
205 * Allocates one cell (dirty allocation)
207 ref_t binmap_t::_alloc_cell()
209 assert (allocated_cells_number_ < cells_number_);
211 /* Pop an element from the free cell list */
212 const ref_t ref = free_top_;
213 assert (cell_[ref].is_free_);
215 free_top_ = cell_[ ref ].free_next_;
217 assert (!(cell_[ ref ].is_free_ = false)); /* Reset flag in DEBUG */
219 ++allocated_cells_number_;
228 ref_t binmap_t::alloc_cell()
230 if (!reserve_cells(1)) {
231 return ROOT_REF /* MEMORY ERROR or OVERFLOW ERROR */;
234 const ref_t ref = _alloc_cell();
237 memset(&cell_[ref], 0, sizeof(cell_[0]));
244 * Reserve cells allocation capacity
246 bool binmap_t::reserve_cells(size_t count)
248 if (cells_number_ - allocated_cells_number_ < count) {
249 /* Finding new sizeof of the buffer */
250 const size_t old_cells_number = cells_number_;
251 const size_t new_cells_number = _max_(16U, _max_(2 * old_cells_number, allocated_cells_number_ + count));
253 /* Check for reference capacity */
254 if (static_cast<ref_t>(new_cells_number) < old_cells_number) {
255 fprintf(stderr, "Warning: binmap_t::reserve_cells: REFERENCE LIMIT ERROR\n");
256 return false /* REFERENCE LIMIT ERROR */;
259 /* Check for integer overflow */
260 static const size_t MAX_NUMBER = (static_cast<size_t>(-1) / sizeof(cell_[0]));
261 if (MAX_NUMBER < new_cells_number) {
262 fprintf(stderr, "Warning: binmap_t::reserve_cells: INTEGER OVERFLOW\n");
263 return false /* INTEGER OVERFLOW */;
266 /* Reallocate memory */
267 cell_t* const cell = static_cast<cell_t*>(realloc(cell_, new_cells_number * sizeof(cell_[0])));
269 fprintf(stderr, "Warning: binmap_t::reserve_cells: MEMORY ERROR\n");
270 return false /* MEMORY ERROR */;
274 cells_number_ = new_cells_number;
276 /* Insert new cells to the free cell list */
277 const size_t stop_idx = old_cells_number - 1;
278 size_t idx = new_cells_number - 1;
280 cell_[ idx ].is_free_ = true;
281 cell_[ idx ].free_next_ = free_top_;
283 for (--idx; idx != stop_idx; --idx) {
284 cell_[ idx ].is_free_ = true;
285 cell_[ idx ].free_next_ = static_cast<ref_t>(idx + 1);
288 free_top_ = static_cast<ref_t>(old_cells_number);
298 void binmap_t::free_cell(ref_t ref)
301 assert (!cell_[ref].is_free_);
303 if (cell_[ref].is_left_ref_) {
304 free_cell(cell_[ref].left_.ref_);
306 if (cell_[ref].is_right_ref_) {
307 free_cell(cell_[ref].right_.ref_);
309 assert ((cell_[ref].is_free_ = true)); /* Set flag in DEBUG */
310 cell_[ref].free_next_ = free_top_;
314 --allocated_cells_number_;
321 bool binmap_t::extend_root()
323 assert (!root_bin_.is_all());
325 if (!cell_[ROOT_REF].is_left_ref_ && !cell_[ROOT_REF].is_right_ref_ && cell_[ROOT_REF].left_.bitmap_ == cell_[ROOT_REF].right_.bitmap_) {
326 /* Setup the root cell */
327 cell_[ROOT_REF].right_.bitmap_ = BITMAP_EMPTY;
330 /* Allocate new cell */
331 const ref_t ref = alloc_cell();
332 if (ref == ROOT_REF) {
333 return false /* ALLOC ERROR */;
336 /* Move old root to the cell */
337 cell_[ref] = cell_[ROOT_REF];
340 cell_[ROOT_REF].is_left_ref_ = true;
341 cell_[ROOT_REF].is_right_ref_ = false;
343 cell_[ROOT_REF].left_.ref_ = ref;
344 cell_[ROOT_REF].right_.bitmap_ = BITMAP_EMPTY;
348 root_bin_.to_parent();
354 * Pack a trace of cells
356 void binmap_t::pack_cells(ref_t* href)
359 if (ref == ROOT_REF) {
363 if (cell_[ref].is_left_ref_ || cell_[ref].is_right_ref_ ||
364 cell_[ref].left_.bitmap_ != cell_[ref].right_.bitmap_) {
368 const bitmap_t bitmap = cell_[ref].left_.bitmap_;
373 if (!cell_[ref].is_left_ref_) {
374 if (cell_[ref].left_.bitmap_ != bitmap) {
378 } else if (!cell_[ref].is_right_ref_) {
379 if (cell_[ref].right_.bitmap_ != bitmap) {
387 } while (ref != ROOT_REF);
389 const ref_t par_ref = href[2];
391 if (cell_[ref].is_left_ref_ && cell_[ref].left_.ref_ == par_ref) {
392 cell_[ref].is_left_ref_ = false;
393 cell_[ref].left_.bitmap_ = bitmap;
395 cell_[ref].is_right_ref_ = false;
396 cell_[ref].right_.bitmap_ = bitmap;
404 * Whether binmap is empty
406 bool binmap_t::is_empty() const
408 const cell_t& cell = cell_[ROOT_REF];
410 return !cell.is_left_ref_ && !cell.is_right_ref_ &&
411 cell.left_.bitmap_ == BITMAP_EMPTY && cell.right_.bitmap_ == BITMAP_EMPTY;
416 * Whether binmap is filled
418 bool binmap_t::is_filled() const
420 const cell_t& cell = cell_[ROOT_REF];
422 return root_bin_.is_all() && !cell.is_left_ref_ && !cell.is_right_ref_ &&
423 cell.left_.bitmap_ == BITMAP_FILLED && cell.right_.bitmap_ == BITMAP_FILLED;
428 * Whether range/bin is empty
430 bool binmap_t::is_empty(const bin_t& bin) const
432 /* Process hi-layers case */
433 if (!root_bin_.contains(bin)) {
434 return !bin.contains(root_bin_) || is_empty();
441 trace(&cur_ref, &cur_bin, bin);
443 assert (cur_bin.layer_bits() > BITMAP_LAYER_BITS);
445 /* Process common case */
446 const cell_t& cell = cell_[cur_ref];
448 if (bin.layer_bits() > BITMAP_LAYER_BITS) {
450 return cell.left_.bitmap_ == BITMAP_EMPTY;
453 return cell.right_.bitmap_ == BITMAP_EMPTY;
455 return !cell.is_left_ref_ && !cell.is_right_ref_ &&
456 cell.left_.bitmap_ == BITMAP_EMPTY && cell.right_.bitmap_ == BITMAP_EMPTY;
459 /* Process low-layers case */
460 assert (bin != cur_bin);
462 const bitmap_t bm1 = (bin < cur_bin) ? cell.left_.bitmap_ : cell.right_.bitmap_;
463 const bitmap_t bm2 = BITMAP[ BITMAP_LAYER_BITS & bin.toUInt() ];
465 return (bm1 & bm2) == BITMAP_EMPTY;
470 * Whether range/bin is filled
472 bool binmap_t::is_filled(const bin_t& bin) const
474 /* Process hi-layers case */
475 if (!root_bin_.contains(bin)) {
483 trace(&cur_ref, &cur_bin, bin);
485 assert (cur_bin.layer_bits() > BITMAP_LAYER_BITS);
487 /* Process common case */
488 const cell_t& cell = cell_[cur_ref];
490 if (bin.layer_bits() > BITMAP_LAYER_BITS) {
492 return cell.left_.bitmap_ == BITMAP_FILLED;
495 return cell.right_.bitmap_ == BITMAP_FILLED;
497 return !cell.is_left_ref_ && !cell.is_right_ref_ &&
498 cell.left_.bitmap_ == BITMAP_FILLED && cell.right_.bitmap_ == BITMAP_FILLED;
501 /* Process low-layers case */
502 assert (bin != cur_bin);
504 const bitmap_t bm1 = (bin < cur_bin) ? cell.left_.bitmap_ : cell.right_.bitmap_;
505 const bitmap_t bm2 = BITMAP[ BITMAP_LAYER_BITS & bin.toUInt() ];
507 return (bm1 & bm2) == bm2;
512 * Return the topmost solid bin which covers the specified bin
514 bin_t binmap_t::cover(const bin_t& bin) const
516 /* Process hi-layers case */
517 if (!root_bin_.contains(bin)) {
518 if (!bin.contains(root_bin_)) {
519 return root_bin_.sibling();
531 trace(&cur_ref, &cur_bin, bin);
533 assert (cur_bin.layer_bits() > BITMAP_LAYER_BITS);
535 /* Process common case */
536 const cell_t& cell = cell_[cur_ref];
538 if (bin.layer_bits() > BITMAP_LAYER_BITS) {
540 if (cell.left_.bitmap_ == BITMAP_EMPTY || cell.left_.bitmap_ == BITMAP_FILLED) {
541 return cur_bin.left();
546 if (cell.right_.bitmap_ == BITMAP_EMPTY || cell.right_.bitmap_ == BITMAP_FILLED) {
547 return cur_bin.right();
551 if (cell.is_left_ref_ || cell.is_right_ref_) {
554 if (cell.left_.bitmap_ != cell.right_.bitmap_) {
557 assert (cur_bin == root_bin_);
558 if (cell.left_.bitmap_ == BITMAP_EMPTY) {
561 if (cell.left_.bitmap_ == BITMAP_FILLED) {
567 /* Process low-layers case */
568 assert (bin != cur_bin);
572 bm1 = cell.left_.bitmap_;
575 bm1 = cell.right_.bitmap_;
579 if (bm1 == BITMAP_EMPTY) {
585 if (bm1 == BITMAP_FILLED) {
592 /* Trace the bitmap */
594 bitmap_t bm2 = BITMAP[ BITMAP_LAYER_BITS & b.toUInt() ];
596 if ((bm1 & bm2) == BITMAP_EMPTY) {
600 bm2 = BITMAP[ BITMAP_LAYER_BITS & b.toUInt() ];
601 } while ((bm1 & bm2) == BITMAP_EMPTY);
605 } else if ((bm1 & bm2) == bm2) {
609 bm2 = BITMAP[ BITMAP_LAYER_BITS & b.toUInt() ];
610 } while ((bm1 & bm2) == bm2);
620 * Find first empty bin
622 bin_t binmap_t::find_empty() const
625 bitmap_t bitmap = BITMAP_FILLED;
631 /* Processing the root */
632 if (cell_[ROOT_REF].is_left_ref_) {
633 cur_ref = cell_[ROOT_REF].left_.ref_;
634 cur_bin = root_bin_.left();
635 } else if (cell_[ROOT_REF].left_.bitmap_ != BITMAP_FILLED) {
636 if (cell_[ ROOT_REF].left_.bitmap_ == BITMAP_EMPTY) {
637 if (!cell_[ ROOT_REF].is_right_ref_ && cell_[ ROOT_REF ].right_.bitmap_ == BITMAP_EMPTY) {
640 return root_bin_.left();
642 bitmap = cell_[ROOT_REF].left_.bitmap_;
643 cur_bin = root_bin_.left();
645 } else if (cell_[ROOT_REF].is_right_ref_) {
646 cur_ref = cell_[ROOT_REF].right_.ref_;
647 cur_bin = root_bin_.right();
649 if (cell_[ROOT_REF].right_.bitmap_ == BITMAP_FILLED) {
650 if (root_bin_.is_all()) {
653 return root_bin_.sibling();
655 bitmap = cell_[ROOT_REF].right_.bitmap_;
656 cur_bin = root_bin_.right();
660 /* Processing middle layers */
662 if (cell_[cur_ref].is_left_ref_) {
663 cur_ref = cell_[cur_ref].left_.ref_;
665 } else if (cell_[cur_ref].left_.bitmap_ != BITMAP_FILLED) {
666 bitmap = cell_[cur_ref].left_.bitmap_;
669 } else if (cell_[cur_ref].is_right_ref_) {
670 cur_ref = cell_[cur_ref].right_.ref_;
673 assert (cell_[cur_ref].right_.bitmap_ != BITMAP_FILLED);
674 bitmap = cell_[cur_ref].right_.bitmap_;
683 assert (bitmap != BITMAP_FILLED);
685 return bitmap_to_bin(cur_bin, ~bitmap);
690 * Find first filled bin
692 bin_t binmap_t::find_filled() const
695 bitmap_t bitmap = BITMAP_EMPTY;
701 /* Processing the root */
702 if (cell_[ROOT_REF].is_left_ref_) {
703 cur_ref = cell_[ROOT_REF].left_.ref_;
704 cur_bin = root_bin_.left();
705 } else if (cell_[ROOT_REF].left_.bitmap_ != BITMAP_EMPTY) {
706 if (cell_[ ROOT_REF].left_.bitmap_ == BITMAP_FILLED) {
707 if (!cell_[ ROOT_REF].is_right_ref_ && cell_[ ROOT_REF ].right_.bitmap_ == BITMAP_FILLED) {
710 return root_bin_.left();
712 bitmap = cell_[ROOT_REF].left_.bitmap_;
713 cur_bin = root_bin_.left();
715 } else if (cell_[ROOT_REF].is_right_ref_) {
716 cur_ref = cell_[ROOT_REF].right_.ref_;
717 cur_bin = root_bin_.right();
719 if (cell_[ROOT_REF].right_.bitmap_ == BITMAP_EMPTY) {
722 bitmap = cell_[ROOT_REF].right_.bitmap_;
723 cur_bin = root_bin_.right();
727 /* Processing middle layers */
729 if (cell_[cur_ref].is_left_ref_) {
730 cur_ref = cell_[cur_ref].left_.ref_;
732 } else if (cell_[cur_ref].left_.bitmap_ != BITMAP_EMPTY) {
733 bitmap = cell_[cur_ref].left_.bitmap_;
736 } else if (cell_[cur_ref].is_right_ref_) {
737 cur_ref = cell_[cur_ref].right_.ref_;
740 assert (cell_[cur_ref].right_.bitmap_ != BITMAP_EMPTY);
741 bitmap = cell_[cur_ref].right_.bitmap_;
750 assert (bitmap != BITMAP_EMPTY);
752 return bitmap_to_bin(cur_bin, bitmap);
756 #define LR_LEFT (0x00)
757 #define RL_RIGHT (0x01)
758 #define RL_LEFT (0x02)
759 #define LR_RIGHT (0x03)
782 #define SPUSH(b, sr, twist) \
785 _sref_[_top_] = sr; \
786 _dir_[_top_] = (0 != (twist & (b.base_length() >> 1))); \
790 #define DPUSH(b, dr, twist) \
793 _dref_[_top_] = dr; \
794 _dir_[_top_] = (0 != (twist & (b.base_length() >> 1))); \
798 #define SDPUSH(b, sr, dr, twist) \
801 _sref_[_top_] = sr; \
802 _dref_[_top_] = dr; \
803 _dir_[_top_] = (0 != (twist & (b.base_length() >> 1))); \
809 assert (_top_ < 65); \
811 const bin_t b = _bin_[_top_]; \
812 const cell_t& sc = source.cell_[_sref_[_top_]]; \
813 const bool is_left = !(_dir_[_top_] & 0x01); \
814 if (0 == (_dir_[_top_] & 0x02)) { \
815 _dir_[_top_++] ^= 0x03; \
819 assert (_top_ < 65); \
821 const bin_t b = _bin_[_top_]; \
822 const cell_t& dc = destination.cell_[_dref_[_top_]]; \
823 const bool is_left = !(_dir_[_top_] & 0x01); \
824 if (0 == (_dir_[_top_] & 0x02)) { \
825 _dir_[_top_++] ^= 0x03; \
829 assert (_top_ < 65); \
831 const bin_t b = _bin_[_top_]; \
832 const cell_t& sc = source.cell_[_sref_[_top_]]; \
833 const cell_t& dc = destination.cell_[_dref_[_top_]]; \
834 const bool is_left = !(_dir_[_top_] & 0x01); \
835 if (0 == (_dir_[_top_] & 0x02)) { \
836 _dir_[_top_++] ^= 0x03; \
841 * Find first additional bin in source
844 * the destination binmap
848 bin_t binmap_t::find_complement(const binmap_t& destination, const binmap_t& source, const bin_t::uint_t twist)
850 return find_complement(destination, source, bin_t::ALL, twist);
852 if (destination.is_empty()) {
853 const cell_t& cell = source.cell_[ROOT_REF];
854 if (!cell.is_left_ref_ && !cell.is_right_ref_ && cell.left_.bitmap_ == BITMAP_FILLED && cell.right_.bitmap_ == BITMAP_FILLED) {
855 return source.root_bin_;
857 return _find_complement(source.root_bin_, BITMAP_EMPTY, ROOT_REF, source, twist);
860 if (destination.root_bin_.contains(source.root_bin_)) {
864 destination.trace(&dref, &dbin, source.root_bin_);
866 if (dbin == source.root_bin_) {
867 return binmap_t::_find_complement(dbin, dref, destination, ROOT_REF, source, twist);
870 assert (source.root_bin_ < dbin);
872 if (destination.cell_[dref].left_.bitmap_ != BITMAP_FILLED) {
873 if (destination.cell_[dref].left_.bitmap_ == BITMAP_EMPTY) {
874 const cell_t& cell = source.cell_[ROOT_REF];
875 if (!cell.is_left_ref_ && !cell.is_right_ref_ && cell.left_.bitmap_ == BITMAP_FILLED && cell.right_.bitmap_ == BITMAP_FILLED) {
876 return source.root_bin_;
879 return binmap_t::_find_complement(source.root_bin_, destination.cell_[dref].left_.bitmap_, ROOT_REF, source, twist);
888 SPUSH(source.root_bin_, ROOT_REF, twist);
895 if (b.left() == destination.root_bin_) {
896 if (sc.is_left_ref_) {
897 const bin_t res = binmap_t::_find_complement(destination.root_bin_, ROOT_REF, destination, sc.left_.ref_, source, twist);
898 if (!res.is_none()) {
901 } else if (sc.left_.bitmap_ != BITMAP_EMPTY) {
902 const bin_t res = binmap_t::_find_complement(destination.root_bin_, ROOT_REF, destination, sc.left_.bitmap_, twist);
903 if (!res.is_none()) {
910 if (sc.is_left_ref_) {
911 SPUSH(b.left(), sc.left_.ref_, twist);
914 } else if (sc.left_.bitmap_ != BITMAP_EMPTY) {
915 if (0 == (twist & (b.left().base_length() - 1) & ~(destination.root_bin_.base_length() - 1))) {
916 const bin_t res = binmap_t::_find_complement(destination.root_bin_, ROOT_REF, destination, sc.left_.bitmap_, twist);
917 if (!res.is_none()) {
920 return binmap_t::_find_complement(destination.root_bin_.sibling(), BITMAP_EMPTY, sc.left_.bitmap_, twist);
922 } else if (sc.left_.bitmap_ != BITMAP_FILLED) {
923 return binmap_t::_find_complement(b.left(), BITMAP_EMPTY, sc.left_.bitmap_, twist);
926 bin_t::uint_t s = twist & (b.left().base_length() - 1);
927 /* Sorry for the following hardcode hack: Flow the highest bit of s */
928 s |= s >> 1; s |= s >> 2;
929 s |= s >> 4; s |= s >> 8;
931 s |= (s >> 16) >> 16; // FIXME: hide warning
932 return bin_t(s + 1 + (s >> 1)); /* bin_t(s >> 1).sibling(); */
937 if (sc.is_right_ref_) {
938 return binmap_t::_find_complement(b.right(), BITMAP_EMPTY, sc.right_.ref_, source, twist);
939 } else if (sc.right_.bitmap_ != BITMAP_EMPTY) {
940 return binmap_t::_find_complement(b.right(), BITMAP_EMPTY, sc.right_.bitmap_, twist);
951 bin_t binmap_t::find_complement(const binmap_t& destination, const binmap_t& source, bin_t range, const bin_t::uint_t twist)
953 ref_t sref = ROOT_REF;
954 bitmap_t sbitmap = BITMAP_EMPTY;
957 if (range.contains(source.root_bin_)) {
958 range = source.root_bin_;
962 } else if (source.root_bin_.contains(range)) {
964 source.trace(&sref, &sbin, range);
972 sbitmap = source.cell_[sref].left_.bitmap_;
974 sbitmap = source.cell_[sref].right_.bitmap_;
977 sbitmap &= BITMAP[ BITMAP_LAYER_BITS & range.toUInt() ];
979 if (sbitmap == BITMAP_EMPTY) {
988 assert (is_sref || sbitmap != BITMAP_EMPTY);
990 if (destination.is_empty()) {
992 const cell_t& cell = source.cell_[sref];
993 if (!cell.is_left_ref_ && !cell.is_right_ref_ && cell.left_.bitmap_ == BITMAP_FILLED && cell.right_.bitmap_ == BITMAP_FILLED) {
996 return _find_complement(range, BITMAP_EMPTY, sref, source, twist);
999 return _find_complement(range, BITMAP_EMPTY, sbitmap, twist);
1003 if (destination.root_bin_.contains(range)) {
1006 destination.trace(&dref, &dbin, range);
1008 if (range == dbin) {
1010 return _find_complement(range, dref, destination, sref, source, twist);
1012 return _find_complement(range, dref, destination, sbitmap, twist);
1019 dbitmap = destination.cell_[dref].left_.bitmap_;
1021 dbitmap = destination.cell_[dref].right_.bitmap_;
1024 if (dbitmap == BITMAP_FILLED) {
1027 } else if (is_sref) {
1028 if (dbitmap == BITMAP_EMPTY) {
1029 const cell_t& cell = source.cell_[sref];
1030 if (!cell.is_left_ref_ && !cell.is_right_ref_ && cell.left_.bitmap_ == BITMAP_FILLED && cell.right_.bitmap_ == BITMAP_FILLED) {
1035 return _find_complement(range, dbitmap, sref, source, twist);
1038 if ((sbitmap & ~dbitmap) != BITMAP_EMPTY) {
1039 return _find_complement(range, dbitmap, sbitmap, twist);
1046 } else if (!range.contains(destination.root_bin_)) {
1048 return _find_complement(range, BITMAP_EMPTY, sref, source, twist);
1050 return _find_complement(range, BITMAP_EMPTY, sbitmap, twist);
1053 } else { // range.contains(destination.m_root_bin)
1057 SPUSH(range, sref, twist);
1063 if (b.left() == destination.root_bin_) {
1064 if (sc.is_left_ref_) {
1065 const bin_t res = binmap_t::_find_complement(destination.root_bin_, ROOT_REF, destination, sc.left_.ref_, source, twist);
1066 if (!res.is_none()) {
1069 } else if (sc.left_.bitmap_ != BITMAP_EMPTY) {
1070 const bin_t res = binmap_t::_find_complement(destination.root_bin_, ROOT_REF, destination, sc.left_.bitmap_, twist);
1071 if (!res.is_none()) {
1078 if (sc.is_left_ref_) {
1079 SPUSH(b.left(), sc.left_.ref_, twist);
1082 } else if (sc.left_.bitmap_ != BITMAP_EMPTY) {
1083 if (0 == (twist & (b.left().base_length() - 1) & ~(destination.root_bin_.base_length() - 1))) {
1084 const bin_t res = binmap_t::_find_complement(destination.root_bin_, ROOT_REF, destination, sc.left_.bitmap_, twist);
1085 if (!res.is_none()) {
1088 return binmap_t::_find_complement(destination.root_bin_.sibling(), BITMAP_EMPTY, sc.left_.bitmap_, twist);
1090 } else if (sc.left_.bitmap_ != BITMAP_FILLED) {
1091 return binmap_t::_find_complement(b.left(), BITMAP_EMPTY, sc.left_.bitmap_, twist);
1094 bin_t::uint_t s = twist & (b.left().base_length() - 1);
1095 /* Sorry for the following hardcode hack: Flow the highest bit of s */
1096 s |= s >> 1; s |= s >> 2;
1097 s |= s >> 4; s |= s >> 8;
1099 s |= (s >> 16) >> 16; // FIXME: hide warning
1100 return bin_t(s + 1 + (s >> 1)); /* bin_t(s >> 1).sibling(); */
1105 if (sc.is_right_ref_) {
1106 return binmap_t::_find_complement(b.right(), BITMAP_EMPTY, sc.right_.ref_, source, twist);
1107 } else if (sc.right_.bitmap_ != BITMAP_EMPTY) {
1108 return binmap_t::_find_complement(b.right(), BITMAP_EMPTY, sc.right_.bitmap_, twist);
1112 } while (_top_ > 0);
1117 if (0 == (twist & (range.base_length() - 1) & ~(destination.root_bin_.base_length() - 1))) {
1118 const bin_t res = binmap_t::_find_complement(destination.root_bin_, ROOT_REF, destination, sbitmap, twist);
1119 if (!res.is_none()) {
1122 return binmap_t::_find_complement(destination.root_bin_.sibling(), BITMAP_EMPTY, sbitmap, twist);
1124 } else if (sbitmap != BITMAP_FILLED) {
1125 return binmap_t::_find_complement(range, BITMAP_EMPTY, sbitmap, twist);
1128 bin_t::uint_t s = twist & (range.base_length() - 1);
1129 /* Sorry for the following hardcode hack: Flow the highest bit of s */
1130 s |= s >> 1; s |= s >> 2;
1131 s |= s >> 4; s |= s >> 8;
1133 s |= (s >> 16) >> 16; // FIXME: hide warning
1134 return bin_t(s + 1 + (s >> 1)); /* bin_t(s >> 1).sibling(); */
1141 bin_t binmap_t::_find_complement(const bin_t& bin, const ref_t dref, const binmap_t& destination, const ref_t sref, const binmap_t& source, const bin_t::uint_t twist)
1143 /* Initialization */
1145 SDPUSH(bin, sref, dref, twist);
1152 if (sc.is_left_ref_) {
1153 if (dc.is_left_ref_) {
1154 SDPUSH(b.left(), sc.left_.ref_, dc.left_.ref_, twist);
1157 } else if (dc.left_.bitmap_ != BITMAP_FILLED) {
1158 const bin_t res = binmap_t::_find_complement(b.left(), dc.left_.bitmap_, sc.left_.ref_, source, twist);
1159 if (!res.is_none()) {
1165 } else if (sc.left_.bitmap_ != BITMAP_EMPTY) {
1166 if (dc.is_left_ref_) {
1167 const bin_t res = binmap_t::_find_complement(b.left(), dc.left_.ref_, destination, sc.left_.bitmap_, twist);
1168 if (!res.is_none()) {
1173 } else if ((sc.left_.bitmap_ & ~dc.left_.bitmap_) != BITMAP_EMPTY) {
1174 return binmap_t::_find_complement(b.left(), dc.left_.bitmap_, sc.left_.bitmap_, twist);
1179 if (sc.is_right_ref_) {
1180 if (dc.is_right_ref_) {
1181 SDPUSH(b.right(), sc.right_.ref_, dc.right_.ref_, twist);
1184 } else if (dc.right_.bitmap_ != BITMAP_FILLED) {
1185 const bin_t res = binmap_t::_find_complement(b.right(), dc.right_.bitmap_, sc.right_.ref_, source, twist);
1186 if (!res.is_none()) {
1192 } else if (sc.right_.bitmap_ != BITMAP_EMPTY) {
1193 if (dc.is_right_ref_) {
1194 const bin_t res = binmap_t::_find_complement(b.right(), dc.right_.ref_, destination, sc.right_.bitmap_, twist);
1195 if (!res.is_none()) {
1200 } else if ((sc.right_.bitmap_ & ~dc.right_.bitmap_) != BITMAP_EMPTY) {
1201 return binmap_t::_find_complement(b.right(), dc.right_.bitmap_, sc.right_.bitmap_, twist);
1205 } while (_top_ > 0);
1211 bin_t binmap_t::_find_complement(const bin_t& bin, const bitmap_t dbitmap, const ref_t sref, const binmap_t& source, const bin_t::uint_t twist)
1213 assert (dbitmap != BITMAP_EMPTY || sref != ROOT_REF ||
1214 source.cell_[ROOT_REF].is_left_ref_ ||
1215 source.cell_[ROOT_REF].is_right_ref_ ||
1216 source.cell_[ROOT_REF].left_.bitmap_ != BITMAP_FILLED ||
1217 source.cell_[ROOT_REF].right_.bitmap_ != BITMAP_FILLED);
1219 /* Initialization */
1221 SPUSH(bin, sref, twist);
1228 if (sc.is_left_ref_) {
1229 SPUSH(b.left(), sc.left_.ref_, twist);
1231 } else if ((sc.left_.bitmap_ & ~dbitmap) != BITMAP_EMPTY) {
1232 return binmap_t::_find_complement(b.left(), dbitmap, sc.left_.bitmap_, twist);
1236 if (sc.is_right_ref_) {
1237 SPUSH(b.right(), sc.right_.ref_, twist);
1239 } else if ((sc.right_.bitmap_ & ~dbitmap) != BITMAP_EMPTY) {
1240 return binmap_t::_find_complement(b.right(), dbitmap, sc.right_.bitmap_, twist);
1243 } while (_top_ > 0);
1249 bin_t binmap_t::_find_complement(const bin_t& bin, const ref_t dref, const binmap_t& destination, const bitmap_t sbitmap, const bin_t::uint_t twist)
1251 /* Initialization */
1253 DPUSH(bin, dref, twist);
1260 if (dc.is_left_ref_) {
1261 DPUSH(b.left(), dc.left_.ref_, twist);
1264 } else if ((sbitmap & ~dc.left_.bitmap_) != BITMAP_EMPTY) {
1265 return binmap_t::_find_complement(b.left(), dc.left_.bitmap_, sbitmap, twist);
1269 if (dc.is_right_ref_) {
1270 DPUSH(b.right(), dc.right_.ref_, twist);
1273 } else if ((sbitmap & ~dc.right_.bitmap_) != BITMAP_EMPTY) {
1274 return binmap_t::_find_complement(b.right(), dc.right_.bitmap_, sbitmap, twist);
1277 } while (_top_ > 0);
1283 bin_t binmap_t::_find_complement(const bin_t& bin, const bitmap_t dbitmap, const bitmap_t sbitmap, bin_t::uint_t twist)
1285 bitmap_t bitmap = sbitmap & ~dbitmap;
1287 assert (bitmap != BITMAP_EMPTY);
1289 if (bitmap == BITMAP_FILLED) {
1293 twist &= bin.base_length() - 1;
1295 if (sizeof(bitmap_t) == 2) {
1297 bitmap = ((bitmap & 0x5555) << 1) | ((bitmap & 0xAAAA) >> 1);
1300 bitmap = ((bitmap & 0x3333) << 2) | ((bitmap & 0xCCCC) >> 2);
1303 bitmap = ((bitmap & 0x0f0f) << 4) | ((bitmap & 0xf0f0) >> 4);
1306 bitmap = ((bitmap & 0x00ff) << 8) | ((bitmap & 0xff00) >> 8);
1309 // Arno, 2012-03-21: Do workaround (see below) here as well?
1311 return bin_t(bin.base_left().twisted(twist & ~0x0f).toUInt() + bitmap_to_bin(bitmap)).to_twisted(twist & 0x0f);
1315 bitmap = ((bitmap & 0x55555555) << 1) | ((bitmap & 0xAAAAAAAA) >> 1);
1318 bitmap = ((bitmap & 0x33333333) << 2) | ((bitmap & 0xCCCCCCCC) >> 2);
1321 bitmap = ((bitmap & 0x0f0f0f0f) << 4) | ((bitmap & 0xf0f0f0f0) >> 4);
1324 bitmap = ((bitmap & 0x00ff00ff) << 8) | ((bitmap & 0xff00ff00) >> 8);
1327 bitmap = ((bitmap & 0x0000ffff) << 16) | ((bitmap & 0xffff0000) >> 16);
1330 bin_t diff = bin_t(bin.base_left().twisted(twist & ~0x1f).toUInt() + bitmap_to_bin(bitmap)).to_twisted(twist & 0x1f);
1332 // Arno, 2012-03-21: Sanity check, if it fails, attempt workaround
1333 if (!bin.contains(diff))
1335 // Bug: Proposed bin is outside of specified range. The bug appears
1336 // to be that the code assumes that the range parameter (called bin
1337 // here) is aligned on a 32-bit boundary. I.e. the width of a
1338 // half_t. Hence when the code does range + bitmap_to_bin(x)
1339 // to find the base-layer offset of the bit on which the source
1340 // and dest bitmaps differ, the result may be too high.
1342 // What I do here is to round the rangestart to 32 bits, and
1343 // then add bitmap_to_bin(bitmap), divided by two as that function
1344 // returns the bit in a "bin number" format (=bit * 2).
1346 // In other words, the "bin" parameter should tell us at what
1347 // base offset of the 32-bit dbitmap and sbitmap is. At the moment
1348 // it doesn't always, because "bin" is not rounded to 32-bit.
1350 // see tests/binstest3.cpp
1352 bin_t::uint_t rangestart = bin.base_left().twisted(twist & ~0x1f).layer_offset();
1353 bin_t::uint_t b2b = bitmap_to_bin(bitmap);
1354 bin_t::uint_t absoff = ((int)(rangestart/32))*32 + b2b/2;
1356 diff = bin_t(0,absoff);
1357 diff = diff.to_twisted(twist & 0x1f);
1360 //fprintf(stderr,"__fc solution %s\n", diff.str(binstr) );
1373 void binmap_t::set(const bin_t& bin)
1375 if (bin.is_none()) {
1379 if (bin.layer_bits() > BITMAP_LAYER_BITS) {
1380 _set__high_layer_bitmap(bin, BITMAP_FILLED);
1382 _set__low_layer_bitmap(bin, BITMAP_FILLED);
1393 void binmap_t::reset(const bin_t& bin)
1395 if (bin.is_none()) {
1399 if (bin.layer_bits() > BITMAP_LAYER_BITS) {
1400 _set__high_layer_bitmap(bin, BITMAP_EMPTY);
1402 _set__low_layer_bitmap(bin, BITMAP_EMPTY);
1410 void binmap_t::clear()
1412 cell_t& cell = cell_[ROOT_REF];
1414 if (cell.is_left_ref_) {
1415 free_cell(cell.left_.ref_);
1417 if (cell.is_right_ref_) {
1418 free_cell(cell.right_.ref_);
1421 cell.is_left_ref_ = false;
1422 cell.is_right_ref_ = false;
1423 cell.left_.bitmap_ = BITMAP_EMPTY;
1424 cell.right_.bitmap_ = BITMAP_EMPTY;
1429 * Fill the binmap. Creates a new filled binmap. Size is given by the source root
1431 void binmap_t::fill(const binmap_t& source)
1433 root_bin_ = source.root_bin_;
1434 /* Extends root if needed */
1435 while (!root_bin_.contains(source.root_bin_)) {
1436 if (!extend_root()) {
1437 return /* ALLOC ERROR */;
1440 set(source.root_bin_);
1442 cell_t& cell = cell_[ROOT_REF];
1444 cell.is_left_ref_ = false;
1445 cell.is_right_ref_ = false;
1446 cell.left_.bitmap_ = BITMAP_FILLED;
1447 cell.right_.bitmap_ = BITMAP_FILLED;
1453 * Get number of allocated cells
1455 size_t binmap_t::cells_number() const
1457 return allocated_cells_number_;
1462 * Get total size of the binmap
1464 size_t binmap_t::total_size() const
1466 return sizeof(*this) + sizeof(cell_[0]) * cells_number_;
1472 * Echo the binmap status to stdout
1474 void binmap_t::status() const
1476 printf("bitmap:\n");
1477 for (int i = 0; i < 16; ++i) {
1478 for (int j = 0; j < 64; ++j) {
1479 printf("%d", is_filled(bin_t(i * 64 + j)));
1484 printf("size: %u bytes\n", static_cast<unsigned int>(total_size()));
1485 printf("cells number: %u (of %u)\n", static_cast<unsigned int>(allocated_cells_number_), static_cast<unsigned int>(cells_number_));
1486 printf("root bin: %llu\n", static_cast<unsigned long long>(root_bin_.toUInt()));
1490 /** Trace the bin */
1491 inline void binmap_t::trace(ref_t* ref, bin_t* bin, const bin_t& target) const
1493 assert (root_bin_.contains(target));
1495 ref_t cur_ref = ROOT_REF;
1496 bin_t cur_bin = root_bin_;
1498 while (target != cur_bin) {
1499 if (target < cur_bin) {
1500 if (cell_[cur_ref].is_left_ref_) {
1501 cur_ref = cell_[cur_ref].left_.ref_;
1507 if (cell_[cur_ref].is_right_ref_) {
1508 cur_ref = cell_[cur_ref].right_.ref_;
1516 assert (cur_bin.layer_bits() > BITMAP_LAYER_BITS);
1527 /** Trace the bin */
1528 inline void binmap_t::trace(ref_t* ref, bin_t* bin, ref_t** history, const bin_t& target) const
1531 assert (root_bin_.contains(target));
1533 ref_t* href = *history;
1534 ref_t cur_ref = ROOT_REF;
1535 bin_t cur_bin = root_bin_;
1538 while (target != cur_bin) {
1539 if (target < cur_bin) {
1540 if (cell_[cur_ref].is_left_ref_) {
1541 cur_ref = cell_[cur_ref].left_.ref_;
1547 if (cell_[cur_ref].is_right_ref_) {
1548 cur_ref = cell_[cur_ref].right_.ref_;
1558 assert (cur_bin.layer_bits() > BITMAP_LAYER_BITS);
1572 * Copy a binmap to another
1574 void binmap_t::copy(binmap_t& destination, const binmap_t& source)
1576 destination.root_bin_ = source.root_bin_;
1577 binmap_t::copy(destination, ROOT_REF, source, ROOT_REF);
1582 * Copy a range from one binmap to another binmap
1584 void binmap_t::copy(binmap_t& destination, const binmap_t& source, const bin_t& range)
1589 if (range.contains(destination.root_bin_)) {
1590 if (source.root_bin_.contains(range)) {
1591 source.trace(&int_ref, &int_bin, range);
1592 destination.root_bin_ = range;
1593 binmap_t::copy(destination, ROOT_REF, source, int_ref);
1594 } else if (range.contains(source.root_bin_)) {
1595 destination.root_bin_ = source.root_bin_;
1596 binmap_t::copy(destination, ROOT_REF, source, ROOT_REF);
1598 destination.reset(range);
1602 if (source.root_bin_.contains(range)) {
1603 source.trace(&int_ref, &int_bin, range);
1605 const cell_t& cell = source.cell_[int_ref];
1607 if (range.layer_bits() <= BITMAP_LAYER_BITS) {
1608 if (range < int_bin) {
1609 destination._set__low_layer_bitmap(range, cell.left_.bitmap_);
1611 destination._set__low_layer_bitmap(range, cell.right_.bitmap_);
1615 if (range == int_bin) {
1616 if (cell.is_left_ref_ || cell.is_right_ref_ || cell.left_.bitmap_ != cell.right_.bitmap_) {
1617 binmap_t::_copy__range(destination, source, int_ref, range);
1619 destination._set__high_layer_bitmap(range, cell.left_.bitmap_);
1621 } else if (range < int_bin) {
1622 destination._set__high_layer_bitmap(range, cell.left_.bitmap_);
1624 destination._set__high_layer_bitmap(range, cell.right_.bitmap_);
1628 } else if (range.contains(source.root_bin_)) {
1629 destination.reset(range); // Probably it could be optimized
1631 const cell_t& cell = source.cell_[ ROOT_REF ];
1633 if (cell.is_left_ref_ || cell.is_right_ref_ || cell.left_.bitmap_ != cell.right_.bitmap_) {
1634 binmap_t::_copy__range(destination, source, ROOT_REF, source.root_bin_);
1636 destination._set__high_layer_bitmap(source.root_bin_, cell.left_.bitmap_);
1640 destination.reset(range);
1646 inline void binmap_t::_set__low_layer_bitmap(const bin_t& bin, const bitmap_t _bitmap)
1648 assert (bin.layer_bits() <= BITMAP_LAYER_BITS);
1650 const bitmap_t bin_bitmap = BITMAP[ bin.toUInt() & BITMAP_LAYER_BITS ];
1651 const bitmap_t bitmap = _bitmap & bin_bitmap;
1653 /* Extends root if needed */
1654 if (!root_bin_.contains(bin)) {
1656 if (bitmap == BITMAP_EMPTY) {
1660 if (!extend_root()) {
1661 return /* ALLOC ERROR */;
1663 } while (!root_bin_.contains(bin));
1666 /* Get the pre-range */
1667 const bin_t pre_bin( (bin.toUInt() & (~(BITMAP_LAYER_BITS + 1))) | BITMAP_LAYER_BITS );
1669 /* The trace the bin with history */
1671 ref_t* href = _href;
1675 /* Process first stage -- do not touch existed tree */
1676 trace(&cur_ref, &cur_bin, &href, pre_bin);
1678 assert (cur_bin.layer_bits() > BITMAP_LAYER_BITS);
1680 /* Checking that we need to do anything */
1681 bitmap_t bm = BITMAP_EMPTY;
1683 cell_t& cell = cell_[cur_ref];
1685 if (bin < cur_bin) {
1686 assert (!cell.is_left_ref_);
1687 bm = cell.left_.bitmap_;
1688 if ((bm & bin_bitmap) == bitmap) {
1691 if (cur_bin == pre_bin) {
1692 cell.left_.bitmap_ = (cell.left_.bitmap_ & ~bin_bitmap) | bitmap;
1693 pack_cells(href - 1);
1697 assert (!cell.is_right_ref_);
1698 bm = cell.right_.bitmap_;
1699 if ((bm & bin_bitmap) == bitmap) {
1702 if (cur_bin == pre_bin) {
1703 cell.right_.bitmap_ = (cell.right_.bitmap_ & ~bin_bitmap) | bitmap;
1704 pack_cells(href - 1);
1710 /* Reserving proper number of cells */
1711 if (!reserve_cells( cur_bin.layer() - pre_bin.layer() )) {
1712 return /* MEMORY ERROR or OVERFLOW ERROR */;
1715 /* Continue to trace */
1717 const ref_t ref = _alloc_cell();
1719 cell_[ref].is_left_ref_ = false;
1720 cell_[ref].is_right_ref_ = false;
1721 cell_[ref].left_.bitmap_ = bm;
1722 cell_[ref].right_.bitmap_ = bm;
1724 if (pre_bin < cur_bin) {
1725 cell_[cur_ref].is_left_ref_ = true;
1726 cell_[cur_ref].left_.ref_ = ref;
1729 cell_[cur_ref].is_right_ref_ = true;
1730 cell_[cur_ref].right_.ref_ = ref;
1735 } while (cur_bin != pre_bin);
1737 assert (cur_bin == pre_bin);
1738 assert (cur_bin.layer_bits() > BITMAP_LAYER_BITS);
1740 /* Complete setting */
1741 if (bin < cur_bin) {
1742 cell_[cur_ref].left_.bitmap_ = (cell_[cur_ref].left_.bitmap_ & ~bin_bitmap) | bitmap;
1744 cell_[cur_ref].right_.bitmap_ = (cell_[cur_ref].right_.bitmap_ & ~bin_bitmap) | bitmap;
1749 inline void binmap_t::_set__high_layer_bitmap(const bin_t& bin, const bitmap_t bitmap)
1751 assert (bin.layer_bits() > BITMAP_LAYER_BITS);
1753 /* First trivial case */
1754 if (bin.contains(root_bin_)) {
1755 cell_t& cell = cell_[ROOT_REF];
1756 if (cell.is_left_ref_) {
1757 free_cell(cell.left_.ref_);
1759 if (cell.is_right_ref_) {
1760 free_cell(cell.right_.ref_);
1764 cell.is_left_ref_ = false;
1765 cell.is_right_ref_ = false;
1766 cell.left_.bitmap_ = bitmap;
1767 cell.right_.bitmap_ = bitmap;
1772 /* Get the pre-range */
1773 bin_t pre_bin = bin.parent();
1775 /* Extends root if needed */
1776 if (!root_bin_.contains(pre_bin)) {
1777 /* Second trivial case */
1778 if (bitmap == BITMAP_EMPTY) {
1783 if (!extend_root()) {
1784 return /* ALLOC ERROR */;
1786 } while (!root_bin_.contains(pre_bin));
1789 /* The trace the bin with history */
1791 ref_t* href = _href;
1795 /* Process first stage -- do not touch existed tree */
1796 trace(&cur_ref, &cur_bin, &href, pre_bin);
1798 /* Checking that we need to do anything */
1799 bitmap_t bm = BITMAP_EMPTY;
1801 cell_t& cell = cell_[cur_ref];
1802 if (bin < cur_bin) {
1803 if (cell.is_left_ref_) {
1804 /* assert (cur_bin == pre_bin); */
1805 cell.is_left_ref_ = false;
1806 free_cell(cell.left_.ref_);
1808 bm = cell.left_.bitmap_;
1813 if (cur_bin == pre_bin) {
1814 cell.left_.bitmap_ = bitmap;
1815 pack_cells(href - 1);
1819 if (cell.is_right_ref_) {
1820 /* assert (cur_bin == pre_bin); */
1821 cell.is_right_ref_ = false;
1822 free_cell(cell.right_.ref_);
1824 bm = cell.right_.bitmap_;
1829 if (cur_bin == pre_bin) {
1830 cell.right_.bitmap_ = bitmap;
1831 pack_cells(href - 1);
1837 /* Reserving proper number of cells */
1838 if (!reserve_cells( cur_bin.layer() - pre_bin.layer() )) {
1839 return /* MEMORY ERROR or OVERFLOW ERROR */;
1842 /* Continue to trace */
1844 const ref_t ref = _alloc_cell();
1846 cell_[ref].is_left_ref_ = false;
1847 cell_[ref].is_right_ref_ = false;
1848 cell_[ref].left_.bitmap_ = bm;
1849 cell_[ref].right_.bitmap_ = bm;
1851 if (pre_bin < cur_bin) {
1852 cell_[cur_ref].is_left_ref_ = true;
1853 cell_[cur_ref].left_.ref_ = ref;
1856 cell_[cur_ref].is_right_ref_ = true;
1857 cell_[cur_ref].right_.ref_ = ref;
1862 } while (cur_bin != pre_bin);
1864 assert (cur_bin == pre_bin);
1865 assert (cur_bin.layer_bits() > BITMAP_LAYER_BITS);
1867 /* Complete setting */
1868 if (bin < cur_bin) {
1869 cell_[cur_ref].left_.bitmap_ = bitmap;
1871 cell_[cur_ref].right_.bitmap_ = bitmap;
1876 void binmap_t::_copy__range(binmap_t& destination, const binmap_t& source, const ref_t sref, const bin_t sbin)
1878 assert (sbin.layer_bits() > BITMAP_LAYER_BITS);
1880 assert (sref == ROOT_REF ||
1881 source.cell_[ sref ].is_left_ref_ || source.cell_[ sref ].is_right_ref_ ||
1882 source.cell_[ sref ].left_.bitmap_ != source.cell_[ sref ].right_.bitmap_
1885 /* Extends root if needed */
1886 while (!destination.root_bin_.contains(sbin)) {
1887 if (!destination.extend_root()) {
1888 return /* ALLOC ERROR */;
1892 /* The trace the bin */
1896 /* Process first stage -- do not touch existed tree */
1897 destination.trace(&cur_ref, &cur_bin, sbin);
1899 /* Continue unpacking if needed */
1900 if (cur_bin != sbin) {
1901 bitmap_t bm = BITMAP_EMPTY;
1903 if (sbin < cur_bin) {
1904 bm = destination.cell_[cur_ref].left_.bitmap_;
1906 bm = destination.cell_[cur_ref].right_.bitmap_;
1909 /* Reserving proper number of cells */
1910 if (!destination.reserve_cells( cur_bin.layer() - sbin.layer() )) {
1911 return /* MEMORY ERROR or OVERFLOW ERROR */;
1914 /* Continue to trace */
1916 const ref_t ref = destination._alloc_cell();
1918 destination.cell_[ref].is_left_ref_ = false;
1919 destination.cell_[ref].is_right_ref_ = false;
1920 destination.cell_[ref].left_.bitmap_ = bm;
1921 destination.cell_[ref].right_.bitmap_ = bm;
1923 if (sbin < cur_bin) {
1924 destination.cell_[cur_ref].is_left_ref_ = true;
1925 destination.cell_[cur_ref].left_.ref_ = ref;
1928 destination.cell_[cur_ref].is_right_ref_ = true;
1929 destination.cell_[cur_ref].right_.ref_ = ref;
1934 } while (cur_bin != sbin);
1938 copy(destination, cur_ref, source, sref);
1943 * Clone binmap cells to another binmap
1945 void binmap_t::copy(binmap_t& destination, const ref_t dref, const binmap_t& source, const ref_t sref)
1947 assert (dref == ROOT_REF ||
1948 source.cell_[ sref ].is_left_ref_ || source.cell_[ sref ].is_right_ref_ ||
1949 source.cell_[ sref ].left_.bitmap_ != source.cell_[ sref ].right_.bitmap_
1952 size_t sref_size = 0;
1953 size_t dref_size = 0;
1959 /* Get size of the source subtree */
1960 sstack[top++] = sref;
1962 assert (top < sizeof(sstack) / sizeof(sstack[0]));
1966 const cell_t& scell = source.cell_[ sstack[--top] ];
1967 if (scell.is_left_ref_) {
1968 sstack[top++] = scell.left_.ref_;
1970 if (scell.is_right_ref_) {
1971 sstack[top++] = scell.right_.ref_;
1976 /* Get size of the destination subtree */
1977 dstack[top++] = dref;
1979 assert (top < sizeof(dstack) / sizeof(dstack[0]));
1983 const cell_t& dcell = destination.cell_[ dstack[--top] ];
1984 if (dcell.is_left_ref_) {
1985 dstack[top++] = dcell.left_.ref_;
1987 if (dcell.is_right_ref_) {
1988 dstack[top++] = dcell.right_.ref_;
1993 /* Reserving proper number of cells */
1994 if (dref_size < sref_size) {
1995 if (!destination.reserve_cells( sref_size - dref_size)) {
1996 return /* MEMORY ERROR or OVERFLOW ERROR */;
2000 /* Release the destination subtree */
2001 if (destination.cell_[dref].is_left_ref_) {
2002 destination.free_cell(destination.cell_[dref].left_.ref_);
2004 if (destination.cell_[dref].is_right_ref_) {
2005 destination.free_cell(destination.cell_[dref].right_.ref_);
2015 const cell_t& scell = source.cell_[ sstack[top] ];
2016 cell_t& dcell = destination.cell_[ dstack[top] ];
2018 /* Processing left ref */
2019 if (scell.is_left_ref_) {
2020 dcell.is_left_ref_ = true;
2021 dcell.left_.ref_ = destination._alloc_cell();
2023 sstack[top] = scell.left_.ref_;
2024 dstack[top] = dcell.left_.ref_;
2027 dcell.is_left_ref_ = false;
2028 dcell.left_.bitmap_ = scell.left_.bitmap_;
2031 /* Processing right ref */
2032 if (scell.is_right_ref_) {
2033 dcell.is_right_ref_ = true;
2034 dcell.right_.ref_ = destination._alloc_cell();
2036 sstack[top] = scell.right_.ref_;
2037 dstack[top] = dcell.right_.ref_;
2040 dcell.is_right_ref_ = false;
2041 dcell.right_.bitmap_ = scell.right_.bitmap_;
2046 int binmap_t::write_cell(FILE *fp,cell_t c)
2048 fprintf_retiffail(fp,"leftb %d\n", c.left_.bitmap_);
2049 fprintf_retiffail(fp,"rightb %d\n", c.right_.bitmap_);
2050 fprintf_retiffail(fp,"is_left %d\n", c.is_left_ref_ ? 1 : 0 );
2051 fprintf_retiffail(fp,"is_right %d\n", c.is_right_ref_ ? 1 : 0 );
2052 fprintf_retiffail(fp,"is_free %d\n", c.is_free_ ? 1 : 0 );
2057 int binmap_t::read_cell(FILE *fp,cell_t *c)
2059 bitmap_t left,right;
2060 int is_left,is_right,is_free;
2061 fscanf_retiffail(fp,"leftb %d\n", &left);
2062 fscanf_retiffail(fp,"rightb %d\n", &right);
2063 fscanf_retiffail(fp,"is_left %d\n", &is_left );
2064 fscanf_retiffail(fp,"is_right %d\n", &is_right );
2065 fscanf_retiffail(fp,"is_free %d\n", &is_free );
2067 //fprintf(stderr,"binmapread_cell: l%ld r%ld %d %d %d\n", left, right, is_left, is_right, is_free );
2069 c->left_.bitmap_ = left;
2070 c->right_.bitmap_ = right;
2071 c->is_left_ref_ = (bool)is_left;
2072 c->is_right_ref_ = (bool)is_right;
2073 c->is_free_ = (bool)is_free;
2078 // Arno, 2011-10-20: Persistent storage
2079 int binmap_t::serialize(FILE *fp)
2081 fprintf_retiffail(fp,"root bin %lli\n",root_bin_.toUInt() );
2082 fprintf_retiffail(fp,"free top %i\n",free_top_ );
2083 fprintf_retiffail(fp,"alloc cells " PRISIZET"\n", allocated_cells_number_);
2084 fprintf_retiffail(fp,"cells num " PRISIZET"\n", cells_number_);
2085 for (size_t i=0; i<cells_number_; i++)
2087 if (write_cell(fp,cell_[i]) < 0)
2096 int binmap_t::deserialize(FILE *fp)
2098 bin_t::uint_t rootbinval;
2100 size_t alloccells,cells;
2101 fscanf_retiffail(fp,"root bin %lli\n", &rootbinval );
2102 fscanf_retiffail(fp,"free top %i\n", &freetop );
2103 fscanf_retiffail(fp,"alloc cells " PRISIZET"\n", &alloccells);
2104 fscanf_retiffail(fp,"cells num " PRISIZET"\n", &cells);
2106 //fprintf(stderr,"Filling BINMAP %p\n", this );
2107 //fprintf(stderr,"Rootbin %lli freetop %li alloc %li num %li\n", rootbinval, freetop, alloccells, cells );
2109 root_bin_ = bin_t(rootbinval);
2110 free_top_ = freetop;
2111 allocated_cells_number_ = alloccells;
2112 cells_number_ = cells;
2113 if (cell_ != NULL) {
2116 cell_ = (cell_t *)new cell_t[cells];
2118 for (i=0; i<cells; i++)
2121 memset(&cell_[i], 0, sizeof(cell_[0]));
2122 if (read_cell(fp,&cell_[i]) < 0)