src/libswift_udp/binmap.cpp

   1 #include <cassert>
   2 #include <cstddef>
   3 #include <cstdlib>
   4 #include <cstring>
   5 #include <cstdio>
   6
   7 #include <iostream>
   8
   9
  10 #include "binmap.h"
  11
  12 using namespace swift;
  13
  14 namespace swift {
  15
  16 inline size_t _max_(const size_t x, const size_t y)
  17 {
  18     return x < y ? y : x;
  19 }
  20
  21 typedef binmap_t::ref_t ref_t;
  22 typedef binmap_t::bitmap_t bitmap_t;
  23
  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);
  27
  28 const bin_t::uint_t BITMAP_LAYER_BITS = 2 * 8 * sizeof(bitmap_t) - 1;
  29
  30 const ref_t ROOT_REF = 0;
  31
  32 #ifdef _MSC_VER
  33 #  pragma warning (push)
  34 #  pragma warning ( disable:4309 )
  35 #endif
  36
  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 */
  70 };
  71
  72 #ifdef _MSC_VER
  73 #pragma warning (pop)
  74 #endif
  75
  76
  77 /**
  78  * Get the leftmost bin that corresponded to bitmap (the bin is filled in bitmap)
  79  */
  80 bin_t::uint_t bitmap_to_bin(register bitmap_t b)
  81 {
  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
  99     };
 100
 101     assert (sizeof(bitmap_t) <= 4);
 102     assert (b != BITMAP_EMPTY);
 103
 104     unsigned char t;
 105
 106     t = BITMAP_TO_BIN[ b & 0xff ];
 107     if (t < 16) {
 108         if (t != 7) {
 109             return static_cast<bin_t::uint_t>(t);
 110         }
 111
 112         b += 1;
 113         b &= -b;
 114         if (0 == b) {
 115             return BITMAP_LAYER_BITS / 2;
 116         }
 117         if (0 == (b & 0xffff)) {
 118             return 15;
 119         }
 120         return 7;
 121     }
 122
 123     b >>= 8;
 124     t = BITMAP_TO_BIN[ b & 0xff ];
 125     if (t <= 15) {
 126         return 16 + t;
 127     }
 128
 129     /* Recursion */
 130     // return 32 + bitmap_to_bin( b >> 8 );
 131
 132     assert (sizeof(bitmap_t) == 4);
 133
 134     b >>= 8;
 135     t = BITMAP_TO_BIN[ b & 0xff ];
 136     if (t < 16) {
 137         if (t != 7) {
 138             return 32 + static_cast<bin_t::uint_t>(t);
 139         }
 140
 141         b += 1;
 142         b &= -b;
 143         if (0 == (b & 0xffff)) {
 144             return 47;
 145         }
 146         return 39;
 147     }
 148
 149     b >>= 8;
 150     return 48 + BITMAP_TO_BIN[ b & 0xff ];
 151 }
 152
 153
 154 /**
 155  * Get the leftmost bin that corresponded to bitmap (the bin is filled in bitmap)
 156  */
 157 bin_t bitmap_to_bin(const bin_t& bin, const bitmap_t bitmap)
 158 {
 159     assert (bitmap != BITMAP_EMPTY);
 160
 161     if (bitmap == BITMAP_FILLED) {
 162         return bin;
 163     }
 164
 165     return bin_t(bin.base_left().toUInt() + bitmap_to_bin(bitmap));
 166 }
 167
 168 } /* namespace */
 169
 170
 171 /* Methods */
 172
 173
 174 /**
 175  * Constructor
 176  */
 177 binmap_t::binmap_t()
 178     : root_bin_(63)
 179 {
 180     assert (sizeof(bitmap_t) <= 4);
 181
 182     cell_ = NULL;
 183     cells_number_ = 0;
 184     allocated_cells_number_ = 0;
 185     free_top_ = ROOT_REF;
 186
 187     const ref_t root_ref = alloc_cell();
 188
 189     assert (root_ref == ROOT_REF && cells_number_ > 0);
 190 }
 191
 192
 193 /**
 194  * Destructor
 195  */
 196 binmap_t::~binmap_t()
 197 {
 198     if (cell_) {
 199         free(cell_);
 200     }
 201 }
 202
 203
 204 /**
 205  * Allocates one cell (dirty allocation)
 206  */
 207 ref_t binmap_t::_alloc_cell()
 208 {
 209     assert (allocated_cells_number_ < cells_number_);
 210
 211     /* Pop an element from the free cell list */
 212     const ref_t ref = free_top_;
 213     assert (cell_[ref].is_free_);
 214
 215     free_top_ = cell_[ ref ].free_next_;
 216
 217     assert (!(cell_[ ref ].is_free_ = false));   /* Reset flag in DEBUG */
 218
 219     ++allocated_cells_number_;
 220
 221     return ref;
 222 }
 223
 224
 225 /**
 226  * Allocates one cell
 227  */
 228 ref_t binmap_t::alloc_cell()
 229 {
 230     if (!reserve_cells(1)) {
 231         return ROOT_REF /* MEMORY ERROR or OVERFLOW ERROR */;
 232     }
 233
 234     const ref_t ref = _alloc_cell();
 235
 236     /* Cleans cell */
 237     memset(&cell_[ref], 0, sizeof(cell_[0]));
 238
 239     return ref;
 240 }
 241
 242
 243 /**
 244  * Reserve cells allocation capacity
 245  */
 246 bool binmap_t::reserve_cells(size_t count)
 247 {
 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));
 252
 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 */;
 257         }
 258
 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 */;
 264         }
 265
 266         /* Reallocate memory */
 267         cell_t* const cell = static_cast<cell_t*>(realloc(cell_, new_cells_number * sizeof(cell_[0])));
 268         if (cell == NULL) {
 269             fprintf(stderr, "Warning: binmap_t::reserve_cells: MEMORY ERROR\n");
 270             return false /* MEMORY ERROR */;
 271         }
 272
 273         cell_ = cell;
 274         cells_number_ = new_cells_number;
 275
 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;
 279
 280         cell_[ idx ].is_free_ = true;
 281         cell_[ idx ].free_next_ = free_top_;
 282
 283         for (--idx; idx != stop_idx; --idx) {
 284             cell_[ idx ].is_free_ = true;
 285             cell_[ idx ].free_next_ = static_cast<ref_t>(idx + 1);
 286         }
 287
 288         free_top_ = static_cast<ref_t>(old_cells_number);
 289     }
 290
 291     return true;
 292 }
 293
 294
 295 /**
 296  * Releases the cell
 297  */
 298 void binmap_t::free_cell(ref_t ref)
 299 {
 300     assert (ref > 0);
 301     assert (!cell_[ref].is_free_);
 302
 303     if (cell_[ref].is_left_ref_) {
 304         free_cell(cell_[ref].left_.ref_);
 305     }
 306     if (cell_[ref].is_right_ref_) {
 307         free_cell(cell_[ref].right_.ref_);
 308     }
 309     assert ((cell_[ref].is_free_ = true)); /* Set flag in DEBUG */
 310     cell_[ref].free_next_ = free_top_;
 311
 312     free_top_ = ref;
 313
 314     --allocated_cells_number_;
 315 }
 316
 317
 318 /**
 319  * Extend root
 320  */
 321 bool binmap_t::extend_root()
 322 {
 323     assert (!root_bin_.is_all());
 324
 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;
 328
 329     } else {
 330         /* Allocate new cell */
 331         const ref_t ref = alloc_cell();
 332         if (ref == ROOT_REF) {
 333             return false /* ALLOC ERROR */;
 334         }
 335
 336         /* Move old root to the cell */
 337         cell_[ref] = cell_[ROOT_REF];
 338
 339         /* Setup new root */
 340         cell_[ROOT_REF].is_left_ref_ = true;
 341         cell_[ROOT_REF].is_right_ref_ = false;
 342
 343         cell_[ROOT_REF].left_.ref_ = ref;
 344         cell_[ROOT_REF].right_.bitmap_ = BITMAP_EMPTY;
 345     }
 346
 347     /* Reset bin */
 348     root_bin_.to_parent();
 349     return true;
 350 }
 351
 352
 353 /**
 354  * Pack a trace of cells
 355  */
 356 void binmap_t::pack_cells(ref_t* href)
 357 {
 358     ref_t ref = *href--;
 359     if (ref == ROOT_REF) {
 360         return;
 361     }
 362
 363     if (cell_[ref].is_left_ref_ || cell_[ref].is_right_ref_ ||
 364         cell_[ref].left_.bitmap_ != cell_[ref].right_.bitmap_) {
 365         return;
 366     }
 367
 368     const bitmap_t bitmap = cell_[ref].left_.bitmap_;
 369
 370     do {
 371         ref = *href--;
 372
 373         if (!cell_[ref].is_left_ref_) {
 374             if (cell_[ref].left_.bitmap_ != bitmap) {
 375                 break;
 376             }
 377
 378         } else if (!cell_[ref].is_right_ref_) {
 379             if (cell_[ref].right_.bitmap_ != bitmap) {
 380                 break;
 381             }
 382
 383         } else {
 384             break;
 385         }
 386
 387     } while (ref != ROOT_REF);
 388
 389     const ref_t par_ref = href[2];
 390
 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;
 394     } else {
 395         cell_[ref].is_right_ref_ = false;
 396         cell_[ref].right_.bitmap_ = bitmap;
 397     }
 398
 399     free_cell(par_ref);
 400 }
 401
 402
 403 /**
 404  * Whether binmap is empty
 405  */
 406 bool binmap_t::is_empty() const
 407 {
 408     const cell_t& cell = cell_[ROOT_REF];
 409
 410     return !cell.is_left_ref_ && !cell.is_right_ref_ &&
 411            cell.left_.bitmap_ == BITMAP_EMPTY && cell.right_.bitmap_ == BITMAP_EMPTY;
 412 }
 413
 414
 415 /**
 416  * Whether binmap is filled
 417  */
 418 bool binmap_t::is_filled() const
 419 {
 420     const cell_t& cell = cell_[ROOT_REF];
 421
 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;
 424 }
 425
 426
 427 /**
 428  * Whether range/bin is empty
 429  */
 430 bool binmap_t::is_empty(const bin_t& bin) const
 431 {
 432     /* Process hi-layers case */
 433     if (!root_bin_.contains(bin)) {
 434         return !bin.contains(root_bin_) || is_empty();
 435     }
 436
 437     /* Trace the bin */
 438     ref_t cur_ref;
 439     bin_t cur_bin;
 440
 441     trace(&cur_ref, &cur_bin, bin);
 442
 443     assert (cur_bin.layer_bits() > BITMAP_LAYER_BITS);
 444
 445     /* Process common case */
 446     const cell_t& cell = cell_[cur_ref];
 447
 448     if (bin.layer_bits() > BITMAP_LAYER_BITS) {
 449         if (bin < cur_bin) {
 450             return cell.left_.bitmap_ == BITMAP_EMPTY;
 451         }
 452         if (cur_bin < bin) {
 453             return cell.right_.bitmap_ == BITMAP_EMPTY;
 454         }
 455         return !cell.is_left_ref_ && !cell.is_right_ref_ &&
 456                 cell.left_.bitmap_ == BITMAP_EMPTY && cell.right_.bitmap_ == BITMAP_EMPTY;
 457     }
 458
 459     /* Process low-layers case */
 460     assert (bin != cur_bin);
 461
 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() ];
 464
 465     return (bm1 & bm2) == BITMAP_EMPTY;
 466 }
 467
 468
 469 /**
 470  * Whether range/bin is filled
 471  */
 472 bool binmap_t::is_filled(const bin_t& bin) const
 473 {
 474     /* Process hi-layers case */
 475     if (!root_bin_.contains(bin)) {
 476         return false;
 477     }
 478
 479     /* Trace the bin */
 480     ref_t cur_ref;
 481     bin_t cur_bin;
 482
 483     trace(&cur_ref, &cur_bin, bin);
 484
 485     assert (cur_bin.layer_bits() > BITMAP_LAYER_BITS);
 486
 487     /* Process common case */
 488     const cell_t& cell = cell_[cur_ref];
 489
 490     if (bin.layer_bits() > BITMAP_LAYER_BITS) {
 491         if (bin < cur_bin) {
 492             return cell.left_.bitmap_ == BITMAP_FILLED;
 493         }
 494         if (cur_bin < bin) {
 495             return cell.right_.bitmap_ == BITMAP_FILLED;
 496         }
 497         return !cell.is_left_ref_ && !cell.is_right_ref_ &&
 498                cell.left_.bitmap_ == BITMAP_FILLED && cell.right_.bitmap_ == BITMAP_FILLED;
 499     }
 500
 501     /* Process low-layers case */
 502     assert (bin != cur_bin);
 503
 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() ];
 506
 507     return (bm1 & bm2) == bm2;
 508 }
 509
 510
 511 /**
 512  * Return the topmost solid bin which covers the specified bin
 513  */
 514 bin_t binmap_t::cover(const bin_t& bin) const
 515 {
 516     /* Process hi-layers case */
 517     if (!root_bin_.contains(bin)) {
 518         if (!bin.contains(root_bin_)) {
 519             return root_bin_.sibling();
 520         }
 521         if (is_empty()) {
 522             return bin_t::ALL;
 523         }
 524         return bin_t::NONE;
 525     }
 526
 527     /* Trace the bin */
 528     ref_t cur_ref;
 529     bin_t cur_bin;
 530
 531     trace(&cur_ref, &cur_bin, bin);
 532
 533     assert (cur_bin.layer_bits() > BITMAP_LAYER_BITS);
 534
 535     /* Process common case */
 536     const cell_t& cell = cell_[cur_ref];
 537
 538     if (bin.layer_bits() > BITMAP_LAYER_BITS) {
 539         if (bin < cur_bin) {
 540             if (cell.left_.bitmap_ == BITMAP_EMPTY || cell.left_.bitmap_ == BITMAP_FILLED) {
 541                 return cur_bin.left();
 542             }
 543             return bin_t::NONE;
 544         }
 545         if (cur_bin < bin) {
 546             if (cell.right_.bitmap_ == BITMAP_EMPTY || cell.right_.bitmap_ == BITMAP_FILLED) {
 547                 return cur_bin.right();
 548             }
 549             return bin_t::NONE;
 550         }
 551         if (cell.is_left_ref_ || cell.is_right_ref_) {
 552             return bin_t::NONE;
 553         }
 554         if (cell.left_.bitmap_ != cell.right_.bitmap_) {
 555             return bin_t::NONE;
 556         }
 557         assert (cur_bin == root_bin_);
 558         if (cell.left_.bitmap_ == BITMAP_EMPTY) {
 559             return bin_t::ALL;
 560         }
 561         if (cell.left_.bitmap_ == BITMAP_FILLED) {
 562             return cur_bin;
 563         }
 564         return bin_t::NONE;
 565     }
 566
 567     /* Process low-layers case */
 568     assert (bin != cur_bin);
 569
 570     bitmap_t bm1;
 571     if (bin < cur_bin) {
 572         bm1 = cell.left_.bitmap_;
 573         cur_bin.to_left();
 574     } else {
 575         bm1 = cell.right_.bitmap_;
 576         cur_bin.to_right();
 577     }
 578
 579     if (bm1 == BITMAP_EMPTY) {
 580         if (is_empty()) {
 581             return bin_t::ALL;
 582         }
 583         return cur_bin;
 584     }
 585     if (bm1 == BITMAP_FILLED) {
 586         if (is_filled()) {
 587             return bin_t::ALL;
 588         }
 589         return cur_bin;
 590     }
 591
 592     /* Trace the bitmap */
 593     bin_t b = bin;
 594     bitmap_t bm2 = BITMAP[ BITMAP_LAYER_BITS & b.toUInt() ];
 595
 596     if ((bm1 & bm2) == BITMAP_EMPTY) {
 597         do {
 598             cur_bin = b;
 599             b.to_parent();
 600             bm2 = BITMAP[ BITMAP_LAYER_BITS & b.toUInt() ];
 601         } while ((bm1 & bm2) == BITMAP_EMPTY);
 602
 603         return cur_bin;
 604
 605     } else if ((bm1 & bm2) == bm2) {
 606         do {
 607             cur_bin = b;
 608             b.to_parent();
 609             bm2 = BITMAP[ BITMAP_LAYER_BITS & b.toUInt() ];
 610         } while ((bm1 & bm2) == bm2);
 611
 612         return cur_bin;
 613     }
 614
 615     return bin_t::NONE;
 616 }
 617
 618
 619 /**
 620  * Find first empty bin
 621  */
 622 bin_t binmap_t::find_empty() const
 623 {
 624     /* Trace the bin */
 625     bitmap_t bitmap = BITMAP_FILLED;
 626
 627     ref_t cur_ref;
 628     bin_t cur_bin;
 629
 630     do {
 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) {
 638                     return bin_t::ALL;
 639                 }
 640                 return root_bin_.left();
 641             }
 642             bitmap = cell_[ROOT_REF].left_.bitmap_;
 643             cur_bin = root_bin_.left();
 644             break;
 645         } else if (cell_[ROOT_REF].is_right_ref_) {
 646             cur_ref = cell_[ROOT_REF].right_.ref_;
 647             cur_bin = root_bin_.right();
 648         } else {
 649             if (cell_[ROOT_REF].right_.bitmap_ == BITMAP_FILLED) {
 650                 if (root_bin_.is_all()) {
 651                     return bin_t::NONE;
 652                 }
 653                 return root_bin_.sibling();
 654             }
 655             bitmap = cell_[ROOT_REF].right_.bitmap_;
 656             cur_bin = root_bin_.right();
 657             break;
 658         }
 659
 660         /* Processing middle layers */
 661         for ( ;;) {
 662             if (cell_[cur_ref].is_left_ref_) {
 663                 cur_ref = cell_[cur_ref].left_.ref_;
 664                 cur_bin.to_left();
 665             } else if (cell_[cur_ref].left_.bitmap_ != BITMAP_FILLED) {
 666                 bitmap = cell_[cur_ref].left_.bitmap_;
 667                 cur_bin.to_left();
 668                 break;
 669             } else if (cell_[cur_ref].is_right_ref_) {
 670                 cur_ref = cell_[cur_ref].right_.ref_;
 671                 cur_bin.to_right();
 672             } else {
 673                 assert (cell_[cur_ref].right_.bitmap_ != BITMAP_FILLED);
 674                 bitmap = cell_[cur_ref].right_.bitmap_;
 675                 cur_bin.to_right();
 676                 break;
 677             }
 678         }
 679
 680     } while (false);
 681
 682     /* Getting result */
 683     assert (bitmap != BITMAP_FILLED);
 684
 685     return bitmap_to_bin(cur_bin, ~bitmap);
 686 }
 687
 688
 689 /**
 690  * Find first filled bin
 691  */
 692 bin_t binmap_t::find_filled() const
 693 {
 694     /* Trace the bin */
 695     bitmap_t bitmap = BITMAP_EMPTY;
 696
 697     ref_t cur_ref;
 698     bin_t cur_bin;
 699
 700     do {
 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) {
 708                     return root_bin_;
 709                 }
 710                 return root_bin_.left();
 711             }
 712             bitmap = cell_[ROOT_REF].left_.bitmap_;
 713             cur_bin = root_bin_.left();
 714             break;
 715         } else if (cell_[ROOT_REF].is_right_ref_) {
 716             cur_ref = cell_[ROOT_REF].right_.ref_;
 717             cur_bin = root_bin_.right();
 718         } else {
 719             if (cell_[ROOT_REF].right_.bitmap_ == BITMAP_EMPTY) {
 720                 return bin_t::NONE;
 721             }
 722             bitmap = cell_[ROOT_REF].right_.bitmap_;
 723             cur_bin = root_bin_.right();
 724             break;
 725         }
 726
 727         /* Processing middle layers */
 728         for ( ;;) {
 729             if (cell_[cur_ref].is_left_ref_) {
 730                 cur_ref = cell_[cur_ref].left_.ref_;
 731                 cur_bin.to_left();
 732             } else if (cell_[cur_ref].left_.bitmap_ != BITMAP_EMPTY) {
 733                 bitmap = cell_[cur_ref].left_.bitmap_;
 734                 cur_bin.to_left();
 735                 break;
 736             } else if (cell_[cur_ref].is_right_ref_) {
 737                 cur_ref = cell_[cur_ref].right_.ref_;
 738                 cur_bin.to_right();
 739             } else {
 740                 assert (cell_[cur_ref].right_.bitmap_ != BITMAP_EMPTY);
 741                 bitmap = cell_[cur_ref].right_.bitmap_;
 742                 cur_bin.to_right();
 743                 break;
 744             }
 745         }
 746
 747     } while (false);
 748
 749     /* Getting result */
 750     assert (bitmap != BITMAP_EMPTY);
 751
 752     return bitmap_to_bin(cur_bin, bitmap);
 753 }
 754
 755
 756 #define LR_LEFT   (0x00)
 757 #define RL_RIGHT  (0x01)
 758 #define RL_LEFT   (0x02)
 759 #define LR_RIGHT  (0x03)
 760
 761
 762 #define SSTACK()                                    \
 763     int _top_ = 0;                                  \
 764     bin_t _bin_[64];                                \
 765     ref_t _sref_[64];                               \
 766     char _dir_[64];
 767
 768 #define DSTACK()                                    \
 769     int _top_ = 0;                                  \
 770     bin_t _bin_[64];                                \
 771     ref_t _dref_[64];                               \
 772     char _dir_[64];
 773
 774 #define SDSTACK()                                   \
 775     int _top_ = 0;                                  \
 776     bin_t _bin_[64];                                \
 777     ref_t _sref_[64];                               \
 778     ref_t _dref_[64];                               \
 779     char _dir_[64];
 780
 781
 782 #define SPUSH(b, sr, twist)                         \
 783     do {                                            \
 784         _bin_[_top_] = b;                           \
 785         _sref_[_top_] = sr;                         \
 786         _dir_[_top_] = (0 != (twist & (b.base_length() >> 1))); \
 787         ++_top_;                                    \
 788     } while (false)
 789
 790 #define DPUSH(b, dr, twist)                         \
 791     do {                                            \
 792         _bin_[_top_] = b;                           \
 793         _dref_[_top_] = dr;                         \
 794         _dir_[_top_] = (0 != (twist & (b.base_length() >> 1))); \
 795         ++_top_;                                    \
 796     } while (false)
 797
 798 #define SDPUSH(b, sr, dr, twist)                    \
 799     do {                                            \
 800         _bin_[_top_] = b;                           \
 801         _sref_[_top_] = sr;                         \
 802         _dref_[_top_] = dr;                         \
 803         _dir_[_top_] = (0 != (twist & (b.base_length() >> 1))); \
 804         ++_top_;                                    \
 805     } while (false)
 806
 807
 808 #define SPOP()                                      \
 809     assert (_top_ < 65);                            \
 810     --_top_;                                        \
 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;                     \
 816     }
 817
 818 #define DPOP()                                      \
 819     assert (_top_ < 65);                            \
 820     --_top_;                                        \
 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;                     \
 826     }
 827
 828 #define SDPOP()                                     \
 829     assert (_top_ < 65);                            \
 830     --_top_;                                        \
 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;                     \
 837     }
 838
 839
 840 /**
 841  * Find first additional bin in source
 842  *
 843  * @param destination
 844  *             the destination binmap
 845  * @param source
 846  *             the source binmap
 847  */
 848 bin_t binmap_t::find_complement(const binmap_t& destination, const binmap_t& source, const bin_t::uint_t twist)
 849 {
 850     return find_complement(destination, source, bin_t::ALL, twist);
 851
 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_;
 856         }
 857         return _find_complement(source.root_bin_, BITMAP_EMPTY, ROOT_REF, source, twist);
 858     }
 859
 860     if (destination.root_bin_.contains(source.root_bin_)) {
 861         ref_t dref;
 862         bin_t dbin;
 863
 864         destination.trace(&dref, &dbin, source.root_bin_);
 865
 866         if (dbin == source.root_bin_) {
 867             return binmap_t::_find_complement(dbin, dref, destination, ROOT_REF, source, twist);
 868         }
 869
 870         assert (source.root_bin_ < dbin);
 871
 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_;
 877                 }
 878             }
 879             return binmap_t::_find_complement(source.root_bin_, destination.cell_[dref].left_.bitmap_, ROOT_REF, source, twist);
 880         }
 881
 882         return bin_t::NONE;
 883
 884     } else {
 885         SSTACK();
 886
 887         /* Initialization */
 888         SPUSH(source.root_bin_, ROOT_REF, twist);
 889
 890         /* Main loop */
 891         do {
 892             SPOP();
 893
 894             if (is_left) {
 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()) {
 899                             return res;
 900                         }
 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()) {
 904                             return res;
 905                         }
 906                     }
 907                     continue;
 908                 }
 909
 910                 if (sc.is_left_ref_) {
 911                     SPUSH(b.left(), sc.left_.ref_, twist);
 912                     continue;
 913
 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()) {
 918                             return res;
 919                         }
 920                         return binmap_t::_find_complement(destination.root_bin_.sibling(), BITMAP_EMPTY, sc.left_.bitmap_, twist);
 921
 922                     } else if (sc.left_.bitmap_ != BITMAP_FILLED) {
 923                         return binmap_t::_find_complement(b.left(), BITMAP_EMPTY, sc.left_.bitmap_, twist);
 924
 925                     } else {
 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;
 930                         s |= s >> 16;
 931                         s |= (s >> 16) >> 16;   // FIXME: hide warning
 932                         return bin_t(s + 1 + (s >> 1)); /* bin_t(s >> 1).sibling(); */
 933                     }
 934                 }
 935
 936             } else {
 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);
 941                 }
 942                 continue;
 943             }
 944         } while (_top_ > 0);
 945
 946         return bin_t::NONE;
 947     }
 948 }
 949
 950
 951 bin_t binmap_t::find_complement(const binmap_t& destination, const binmap_t& source, bin_t range, const bin_t::uint_t twist)
 952 {
 953     ref_t sref = ROOT_REF;
 954     bitmap_t sbitmap = BITMAP_EMPTY;
 955     bool is_sref = true;
 956
 957     if (range.contains(source.root_bin_)) {
 958         range = source.root_bin_;
 959         is_sref = true;
 960         sref = ROOT_REF;
 961
 962     } else if (source.root_bin_.contains(range)) {
 963         bin_t sbin;
 964         source.trace(&sref, &sbin, range);
 965
 966         if (range == sbin) {
 967             is_sref = true;
 968         } else {
 969             is_sref = false;
 970
 971             if (range < sbin) {
 972                 sbitmap = source.cell_[sref].left_.bitmap_;
 973             } else {
 974                 sbitmap = source.cell_[sref].right_.bitmap_;
 975             }
 976
 977             sbitmap &= BITMAP[ BITMAP_LAYER_BITS & range.toUInt() ];
 978
 979             if (sbitmap == BITMAP_EMPTY) {
 980                 return bin_t::NONE;
 981             }
 982         }
 983
 984     } else {
 985         return bin_t::NONE;
 986     }
 987
 988     assert (is_sref || sbitmap != BITMAP_EMPTY);
 989
 990     if (destination.is_empty()) {
 991         if (is_sref) {
 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) {
 994                 return range;
 995             } else {
 996                 return _find_complement(range, BITMAP_EMPTY, sref, source, twist);
 997             }
 998         } else {
 999             return _find_complement(range, BITMAP_EMPTY, sbitmap, twist);
1000         }
1001     }
1002
1003     if (destination.root_bin_.contains(range)) {
1004         ref_t dref;
1005         bin_t dbin;
1006         destination.trace(&dref, &dbin, range);
1007
1008         if (range == dbin) {
1009             if (is_sref) {
1010                 return _find_complement(range, dref, destination, sref, source, twist);
1011             } else {
1012                 return _find_complement(range, dref, destination, sbitmap, twist);
1013             }
1014
1015         } else {
1016             bitmap_t dbitmap;
1017
1018             if (range < dbin) {
1019                 dbitmap = destination.cell_[dref].left_.bitmap_;
1020             } else {
1021                 dbitmap = destination.cell_[dref].right_.bitmap_;
1022             }
1023
1024             if (dbitmap == BITMAP_FILLED) {
1025                 return bin_t::NONE;
1026
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) {
1031                         return range;
1032                     }
1033                 }
1034
1035                 return _find_complement(range, dbitmap, sref, source, twist);
1036
1037             } else {
1038                 if ((sbitmap & ~dbitmap) != BITMAP_EMPTY) {
1039                     return _find_complement(range, dbitmap, sbitmap, twist);
1040                 } else {
1041                     return bin_t::NONE;
1042                 }
1043             }
1044         }
1045
1046     } else if (!range.contains(destination.root_bin_)) {
1047         if (is_sref) {
1048             return _find_complement(range, BITMAP_EMPTY, sref, source, twist);
1049         } else {
1050             return _find_complement(range, BITMAP_EMPTY, sbitmap, twist);
1051         }
1052
1053     } else { // range.contains(destination.m_root_bin)
1054         if (is_sref) {
1055             SSTACK();
1056
1057             SPUSH(range, sref, twist);
1058
1059             do {
1060                 SPOP();
1061
1062                 if (is_left) {
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()) {
1067                                 return res;
1068                             }
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()) {
1072                                 return res;
1073                             }
1074                         }
1075                         continue;
1076                     }
1077
1078                     if (sc.is_left_ref_) {
1079                         SPUSH(b.left(), sc.left_.ref_, twist);
1080                         continue;
1081
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()) {
1086                                 return res;
1087                             }
1088                             return binmap_t::_find_complement(destination.root_bin_.sibling(), BITMAP_EMPTY, sc.left_.bitmap_, twist);
1089
1090                         } else if (sc.left_.bitmap_ != BITMAP_FILLED) {
1091                             return binmap_t::_find_complement(b.left(), BITMAP_EMPTY, sc.left_.bitmap_, twist);
1092
1093                         } else {
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;
1098                             s |= s >> 16;
1099                             s |= (s >> 16) >> 16;   // FIXME: hide warning
1100                             return bin_t(s + 1 + (s >> 1)); /* bin_t(s >> 1).sibling(); */
1101                         }
1102                     }
1103
1104                 } else {
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);
1109                     }
1110                     continue;
1111                 }
1112             } while (_top_ > 0);
1113
1114             return bin_t::NONE;
1115
1116         } else {
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()) {
1120                     return res;
1121                 }
1122                 return binmap_t::_find_complement(destination.root_bin_.sibling(), BITMAP_EMPTY, sbitmap, twist);
1123
1124             } else if (sbitmap != BITMAP_FILLED) {
1125                 return binmap_t::_find_complement(range, BITMAP_EMPTY, sbitmap, twist);
1126
1127             } else {
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;
1132                 s |= s >> 16;
1133                 s |= (s >> 16) >> 16;   // FIXME: hide warning
1134                 return bin_t(s + 1 + (s >> 1)); /* bin_t(s >> 1).sibling(); */
1135             }
1136         }
1137     }
1138 }
1139
1140
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)
1142 {
1143     /* Initialization */
1144     SDSTACK();
1145     SDPUSH(bin, sref, dref, twist);
1146
1147     /* Main loop */
1148     do {
1149         SDPOP();
1150
1151         if (is_left) {
1152             if (sc.is_left_ref_) {
1153                 if (dc.is_left_ref_) {
1154                     SDPUSH(b.left(), sc.left_.ref_, dc.left_.ref_, twist);
1155                     continue;
1156
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()) {
1160                         return res;
1161                     }
1162                     continue;
1163                 }
1164
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()) {
1169                         return res;
1170                     }
1171                     continue;
1172
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);
1175                 }
1176             }
1177
1178         } else {
1179             if (sc.is_right_ref_) {
1180                 if (dc.is_right_ref_) {
1181                     SDPUSH(b.right(), sc.right_.ref_, dc.right_.ref_, twist);
1182                     continue;
1183
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()) {
1187                         return res;
1188                     }
1189                     continue;
1190                 }
1191
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()) {
1196                         return res;
1197                     }
1198                     continue;
1199
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);
1202                 }
1203             }
1204         }
1205     } while (_top_ > 0);
1206
1207     return bin_t::NONE;
1208 }
1209
1210
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)
1212 {
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);
1218
1219     /* Initialization */
1220     SSTACK();
1221     SPUSH(bin, sref, twist);
1222
1223     /* Main loop */
1224     do {
1225         SPOP();
1226
1227         if (is_left) {
1228             if (sc.is_left_ref_) {
1229                 SPUSH(b.left(), sc.left_.ref_, twist);
1230                 continue;
1231             } else if ((sc.left_.bitmap_ & ~dbitmap) != BITMAP_EMPTY) {
1232                 return binmap_t::_find_complement(b.left(), dbitmap, sc.left_.bitmap_, twist);
1233             }
1234
1235         } else {
1236             if (sc.is_right_ref_) {
1237                 SPUSH(b.right(), sc.right_.ref_, twist);
1238                 continue;
1239             } else if ((sc.right_.bitmap_ & ~dbitmap) != BITMAP_EMPTY) {
1240                 return binmap_t::_find_complement(b.right(), dbitmap, sc.right_.bitmap_, twist);
1241             }
1242         }
1243     } while (_top_ > 0);
1244
1245     return bin_t::NONE;
1246 }
1247
1248
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)
1250 {
1251     /* Initialization */
1252     DSTACK();
1253     DPUSH(bin, dref, twist);
1254
1255     /* Main loop */
1256     do {
1257         DPOP();
1258
1259         if (is_left) {
1260             if (dc.is_left_ref_) {
1261                 DPUSH(b.left(), dc.left_.ref_, twist);
1262                 continue;
1263
1264             } else if ((sbitmap & ~dc.left_.bitmap_) != BITMAP_EMPTY) {
1265                 return binmap_t::_find_complement(b.left(), dc.left_.bitmap_, sbitmap, twist);
1266             }
1267
1268         } else {
1269             if (dc.is_right_ref_) {
1270                 DPUSH(b.right(), dc.right_.ref_, twist);
1271                 continue;
1272
1273             } else if ((sbitmap & ~dc.right_.bitmap_) != BITMAP_EMPTY) {
1274                 return binmap_t::_find_complement(b.right(), dc.right_.bitmap_, sbitmap, twist);
1275             }
1276         }
1277     } while (_top_ > 0);
1278
1279     return bin_t::NONE;
1280 }
1281
1282
1283 bin_t binmap_t::_find_complement(const bin_t& bin, const bitmap_t dbitmap, const bitmap_t sbitmap, bin_t::uint_t twist)
1284 {
1285     bitmap_t bitmap = sbitmap & ~dbitmap;
1286
1287     assert (bitmap != BITMAP_EMPTY);
1288
1289     if (bitmap == BITMAP_FILLED) {
1290         return bin;
1291     }
1292
1293     twist &= bin.base_length() - 1;
1294
1295     if (sizeof(bitmap_t) == 2) {
1296         if (twist & 1) {
1297             bitmap = ((bitmap & 0x5555) << 1)  | ((bitmap & 0xAAAA) >> 1);
1298         }
1299         if (twist & 2) {
1300             bitmap = ((bitmap & 0x3333) << 2)  | ((bitmap & 0xCCCC) >> 2);
1301         }
1302         if (twist & 4) {
1303             bitmap = ((bitmap & 0x0f0f) << 4)  | ((bitmap & 0xf0f0) >> 4);
1304         }
1305         if (twist & 8) {
1306             bitmap = ((bitmap & 0x00ff) << 8)  | ((bitmap & 0xff00) >> 8);
1307         }
1308
1309         // Arno, 2012-03-21: Do workaround (see below) here as well?
1310
1311         return bin_t(bin.base_left().twisted(twist & ~0x0f).toUInt() + bitmap_to_bin(bitmap)).to_twisted(twist & 0x0f);
1312
1313     } else {
1314         if (twist & 1) {
1315             bitmap = ((bitmap & 0x55555555) << 1)  | ((bitmap & 0xAAAAAAAA) >> 1);
1316         }
1317         if (twist & 2) {
1318             bitmap = ((bitmap & 0x33333333) << 2)  | ((bitmap & 0xCCCCCCCC) >> 2);
1319         }
1320         if (twist & 4) {
1321             bitmap = ((bitmap & 0x0f0f0f0f) << 4)  | ((bitmap & 0xf0f0f0f0) >> 4);
1322         }
1323         if (twist & 8) {
1324             bitmap = ((bitmap & 0x00ff00ff) << 8)  | ((bitmap & 0xff00ff00) >> 8);
1325         }
1326         if (twist & 16) {
1327             bitmap = ((bitmap & 0x0000ffff) << 16)  | ((bitmap & 0xffff0000) >> 16);
1328         }
1329
1330         bin_t diff = bin_t(bin.base_left().twisted(twist & ~0x1f).toUInt() + bitmap_to_bin(bitmap)).to_twisted(twist & 0x1f);
1331
1332         // Arno, 2012-03-21: Sanity check, if it fails, attempt workaround
1333         if (!bin.contains(diff))
1334         {
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.
1341                 //
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).
1345                 //
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.
1349                 //
1350                 // see tests/binstest3.cpp
1351
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;
1355
1356                 diff = bin_t(0,absoff);
1357                 diff = diff.to_twisted(twist & 0x1f);
1358
1359                 //char binstr[32];
1360                 //fprintf(stderr,"__fc solution %s\n", diff.str(binstr) );
1361         }
1362         return diff;
1363     }
1364 }
1365
1366
1367 /**
1368  * Sets bins
1369  *
1370  * @param bin
1371  *             the bin
1372  */
1373 void binmap_t::set(const bin_t& bin)
1374 {
1375     if (bin.is_none()) {
1376         return;
1377     }
1378
1379     if (bin.layer_bits() > BITMAP_LAYER_BITS) {
1380         _set__high_layer_bitmap(bin, BITMAP_FILLED);
1381     } else {
1382         _set__low_layer_bitmap(bin, BITMAP_FILLED);
1383     }
1384 }
1385
1386
1387 /**
1388  * Resets bins
1389  *
1390  * @param bin
1391  *             the bin
1392  */
1393 void binmap_t::reset(const bin_t& bin)
1394 {
1395     if (bin.is_none()) {
1396         return;
1397     }
1398
1399     if (bin.layer_bits() > BITMAP_LAYER_BITS) {
1400         _set__high_layer_bitmap(bin, BITMAP_EMPTY);
1401     } else {
1402         _set__low_layer_bitmap(bin, BITMAP_EMPTY);
1403     }
1404 }
1405
1406
1407 /**
1408  * Empty all bins
1409  */
1410 void binmap_t::clear()
1411 {
1412     cell_t& cell = cell_[ROOT_REF];
1413
1414     if (cell.is_left_ref_) {
1415         free_cell(cell.left_.ref_);
1416     }
1417     if (cell.is_right_ref_) {
1418         free_cell(cell.right_.ref_);
1419     }
1420
1421     cell.is_left_ref_ = false;
1422     cell.is_right_ref_ = false;
1423     cell.left_.bitmap_ = BITMAP_EMPTY;
1424     cell.right_.bitmap_ = BITMAP_EMPTY;
1425 }
1426
1427
1428 /**
1429  * Fill the binmap. Creates a new filled binmap. Size is given by the source root
1430  */
1431 void binmap_t::fill(const binmap_t& source)
1432 {
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 */;
1438         }
1439     }
1440     set(source.root_bin_);
1441
1442     cell_t& cell = cell_[ROOT_REF];
1443
1444     cell.is_left_ref_ = false;
1445     cell.is_right_ref_ = false;
1446     cell.left_.bitmap_ = BITMAP_FILLED;
1447     cell.right_.bitmap_ = BITMAP_FILLED;
1448 }
1449
1450
1451
1452 /**
1453  * Get number of allocated cells
1454  */
1455 size_t binmap_t::cells_number() const
1456 {
1457     return allocated_cells_number_;
1458 }
1459
1460
1461 /**
1462  * Get total size of the binmap
1463  */
1464 size_t binmap_t::total_size() const
1465 {
1466     return sizeof(*this) + sizeof(cell_[0]) * cells_number_;
1467 }
1468
1469
1470
1471 /**
1472  * Echo the binmap status to stdout
1473  */
1474 void binmap_t::status() const
1475 {
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)));
1480         }
1481         printf("\n");
1482     }
1483
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()));
1487 }
1488
1489
1490 /** Trace the bin */
1491 inline void binmap_t::trace(ref_t* ref, bin_t* bin, const bin_t& target) const
1492 {
1493     assert (root_bin_.contains(target));
1494
1495     ref_t cur_ref = ROOT_REF;
1496     bin_t cur_bin = root_bin_;
1497
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_;
1502                 cur_bin.to_left();
1503             } else {
1504                 break;
1505             }
1506         } else {
1507             if (cell_[cur_ref].is_right_ref_) {
1508                 cur_ref = cell_[cur_ref].right_.ref_;
1509                 cur_bin.to_right();
1510             } else {
1511                 break;
1512             }
1513         }
1514     }
1515
1516     assert (cur_bin.layer_bits() > BITMAP_LAYER_BITS);
1517
1518     if (ref) {
1519         *ref = cur_ref;
1520     }
1521     if (bin) {
1522         *bin = cur_bin;
1523     }
1524 }
1525
1526
1527 /** Trace the bin */
1528 inline void binmap_t::trace(ref_t* ref, bin_t* bin, ref_t** history, const bin_t& target) const
1529 {
1530     assert (history);
1531     assert (root_bin_.contains(target));
1532
1533     ref_t* href = *history;
1534     ref_t cur_ref = ROOT_REF;
1535     bin_t cur_bin = root_bin_;
1536
1537     *href++ = ROOT_REF;
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_;
1542                 cur_bin.to_left();
1543             } else {
1544                 break;
1545             }
1546         } else {
1547             if (cell_[cur_ref].is_right_ref_) {
1548                 cur_ref = cell_[cur_ref].right_.ref_;
1549                 cur_bin.to_right();
1550             } else {
1551                 break;
1552             }
1553         }
1554
1555         *href++ = cur_ref;
1556     }
1557
1558     assert (cur_bin.layer_bits() > BITMAP_LAYER_BITS);
1559
1560     if (ref) {
1561         *ref = cur_ref;
1562     }
1563     if (bin) {
1564         *bin = cur_bin;
1565     }
1566
1567     *history = href;
1568 }
1569
1570
1571 /**
1572  * Copy a binmap to another
1573  */
1574 void binmap_t::copy(binmap_t& destination, const binmap_t& source)
1575 {
1576     destination.root_bin_ = source.root_bin_;
1577     binmap_t::copy(destination, ROOT_REF, source, ROOT_REF);
1578 }
1579
1580
1581 /**
1582  * Copy a range from one binmap to another binmap
1583  */
1584 void binmap_t::copy(binmap_t& destination, const binmap_t& source, const bin_t& range)
1585 {
1586     ref_t int_ref;
1587     bin_t int_bin;
1588
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);
1597         } else {
1598             destination.reset(range);
1599         }
1600
1601     } else {
1602         if (source.root_bin_.contains(range)) {
1603             source.trace(&int_ref, &int_bin, range);
1604
1605             const cell_t& cell = source.cell_[int_ref];
1606
1607             if (range.layer_bits() <= BITMAP_LAYER_BITS) {
1608                 if (range < int_bin) {
1609                     destination._set__low_layer_bitmap(range, cell.left_.bitmap_);
1610                 } else {
1611                     destination._set__low_layer_bitmap(range, cell.right_.bitmap_);
1612                 }
1613
1614             } else {
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);
1618                     } else {
1619                         destination._set__high_layer_bitmap(range, cell.left_.bitmap_);
1620                     }
1621                 } else if (range < int_bin) {
1622                     destination._set__high_layer_bitmap(range, cell.left_.bitmap_);
1623                 } else {
1624                     destination._set__high_layer_bitmap(range, cell.right_.bitmap_);
1625                 }
1626             }
1627
1628         } else if (range.contains(source.root_bin_)) {
1629             destination.reset(range);   // Probably it could be optimized
1630
1631             const cell_t& cell = source.cell_[ ROOT_REF ];
1632
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_);
1635             } else {
1636                 destination._set__high_layer_bitmap(source.root_bin_, cell.left_.bitmap_);
1637             }
1638
1639         } else {
1640             destination.reset(range);
1641         }
1642     }
1643 }
1644
1645
1646 inline void binmap_t::_set__low_layer_bitmap(const bin_t& bin, const bitmap_t _bitmap)
1647 {
1648     assert (bin.layer_bits() <= BITMAP_LAYER_BITS);
1649
1650     const bitmap_t bin_bitmap = BITMAP[ bin.toUInt() & BITMAP_LAYER_BITS ];
1651     const bitmap_t bitmap = _bitmap & bin_bitmap;
1652
1653     /* Extends root if needed */
1654     if (!root_bin_.contains(bin)) {
1655         /* Trivial case */
1656         if (bitmap == BITMAP_EMPTY) {
1657             return;
1658         }
1659         do {
1660             if (!extend_root()) {
1661                 return /* ALLOC ERROR */;
1662             }
1663         } while (!root_bin_.contains(bin));
1664     }
1665
1666     /* Get the pre-range */
1667     const bin_t pre_bin( (bin.toUInt() & (~(BITMAP_LAYER_BITS + 1))) | BITMAP_LAYER_BITS );
1668
1669     /* The trace the bin with history */
1670     ref_t _href[64];
1671     ref_t* href = _href;
1672     ref_t cur_ref;
1673     bin_t cur_bin;
1674
1675     /* Process first stage -- do not touch existed tree */
1676     trace(&cur_ref, &cur_bin, &href, pre_bin);
1677
1678     assert (cur_bin.layer_bits() > BITMAP_LAYER_BITS);
1679
1680     /* Checking that we need to do anything */
1681     bitmap_t bm = BITMAP_EMPTY;
1682     {
1683         cell_t& cell = cell_[cur_ref];
1684
1685         if (bin < cur_bin) {
1686             assert (!cell.is_left_ref_);
1687             bm = cell.left_.bitmap_;
1688             if ((bm & bin_bitmap) == bitmap) {
1689                 return;
1690             }
1691             if (cur_bin == pre_bin) {
1692                 cell.left_.bitmap_ = (cell.left_.bitmap_ & ~bin_bitmap) | bitmap;
1693                 pack_cells(href - 1);
1694                 return;
1695             }
1696         } else {
1697             assert (!cell.is_right_ref_);
1698             bm = cell.right_.bitmap_;
1699             if ((bm & bin_bitmap) == bitmap) {
1700                 return;
1701             }
1702             if (cur_bin == pre_bin) {
1703                 cell.right_.bitmap_ = (cell.right_.bitmap_ & ~bin_bitmap) | bitmap;
1704                 pack_cells(href - 1);
1705                 return;
1706             }
1707         }
1708     }
1709
1710     /* Reserving proper number of cells */
1711     if (!reserve_cells( cur_bin.layer() - pre_bin.layer() )) {
1712         return /* MEMORY ERROR or OVERFLOW ERROR */;
1713     }
1714
1715     /* Continue to trace */
1716     do {
1717         const ref_t ref = _alloc_cell();
1718
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;
1723
1724         if (pre_bin < cur_bin) {
1725             cell_[cur_ref].is_left_ref_ = true;
1726             cell_[cur_ref].left_.ref_ = ref;
1727             cur_bin.to_left();
1728         } else {
1729             cell_[cur_ref].is_right_ref_ = true;
1730             cell_[cur_ref].right_.ref_ = ref;
1731             cur_bin.to_right();
1732         }
1733
1734         cur_ref = ref;
1735     } while (cur_bin != pre_bin);
1736
1737     assert (cur_bin == pre_bin);
1738     assert (cur_bin.layer_bits() > BITMAP_LAYER_BITS);
1739
1740     /* Complete setting */
1741     if (bin < cur_bin) {
1742         cell_[cur_ref].left_.bitmap_ = (cell_[cur_ref].left_.bitmap_ & ~bin_bitmap) | bitmap;
1743     } else {
1744         cell_[cur_ref].right_.bitmap_ = (cell_[cur_ref].right_.bitmap_ & ~bin_bitmap) | bitmap;
1745     }
1746 }
1747
1748
1749 inline void binmap_t::_set__high_layer_bitmap(const bin_t& bin, const bitmap_t bitmap)
1750 {
1751     assert (bin.layer_bits() > BITMAP_LAYER_BITS);
1752
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_);
1758         }
1759         if (cell.is_right_ref_) {
1760             free_cell(cell.right_.ref_);
1761         }
1762
1763         root_bin_ = bin;
1764         cell.is_left_ref_ = false;
1765         cell.is_right_ref_ = false;
1766         cell.left_.bitmap_ = bitmap;
1767         cell.right_.bitmap_ = bitmap;
1768
1769         return;
1770     }
1771
1772     /* Get the pre-range */
1773     bin_t pre_bin = bin.parent();
1774
1775     /* Extends root if needed */
1776     if (!root_bin_.contains(pre_bin)) {
1777         /* Second trivial case */
1778         if (bitmap == BITMAP_EMPTY) {
1779             return;
1780         }
1781
1782         do {
1783             if (!extend_root()) {
1784                 return /* ALLOC ERROR */;
1785             }
1786         } while (!root_bin_.contains(pre_bin));
1787     }
1788
1789     /* The trace the bin with history */
1790     ref_t _href[64];
1791     ref_t* href = _href;
1792     ref_t cur_ref;
1793     bin_t cur_bin;
1794
1795     /* Process first stage -- do not touch existed tree */
1796     trace(&cur_ref, &cur_bin, &href, pre_bin);
1797
1798     /* Checking that we need to do anything */
1799     bitmap_t bm = BITMAP_EMPTY;
1800     {
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_);
1807             } else {
1808                 bm = cell.left_.bitmap_;
1809                 if (bm == bitmap) {
1810                     return;
1811                 }
1812             }
1813             if (cur_bin == pre_bin) {
1814                 cell.left_.bitmap_ = bitmap;
1815                 pack_cells(href - 1);
1816                 return;
1817             }
1818         } else {
1819             if (cell.is_right_ref_) {
1820                 /* assert (cur_bin == pre_bin); */
1821                 cell.is_right_ref_ = false;
1822                 free_cell(cell.right_.ref_);
1823             } else {
1824                 bm = cell.right_.bitmap_;
1825                 if (bm == bitmap) {
1826                     return;
1827                 }
1828             }
1829             if (cur_bin == pre_bin) {
1830                 cell.right_.bitmap_ = bitmap;
1831                 pack_cells(href - 1);
1832                 return;
1833             }
1834         }
1835     }
1836
1837     /* Reserving proper number of cells */
1838     if (!reserve_cells( cur_bin.layer() - pre_bin.layer() )) {
1839         return /* MEMORY ERROR or OVERFLOW ERROR */;
1840     }
1841
1842     /* Continue to trace */
1843     do {
1844         const ref_t ref = _alloc_cell();
1845
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;
1850
1851         if (pre_bin < cur_bin) {
1852             cell_[cur_ref].is_left_ref_ = true;
1853             cell_[cur_ref].left_.ref_ = ref;
1854             cur_bin.to_left();
1855         } else {
1856             cell_[cur_ref].is_right_ref_ = true;
1857             cell_[cur_ref].right_.ref_ = ref;
1858             cur_bin.to_right();
1859         }
1860
1861         cur_ref = ref;
1862     } while (cur_bin != pre_bin);
1863
1864     assert (cur_bin == pre_bin);
1865     assert (cur_bin.layer_bits() > BITMAP_LAYER_BITS);
1866
1867     /* Complete setting */
1868     if (bin < cur_bin) {
1869         cell_[cur_ref].left_.bitmap_ = bitmap;
1870     } else {
1871         cell_[cur_ref].right_.bitmap_ = bitmap;
1872     }
1873 }
1874
1875
1876 void binmap_t::_copy__range(binmap_t& destination, const binmap_t& source, const ref_t sref, const bin_t sbin)
1877 {
1878     assert (sbin.layer_bits() > BITMAP_LAYER_BITS);
1879
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_
1883     );
1884
1885     /* Extends root if needed */
1886     while (!destination.root_bin_.contains(sbin)) {
1887         if (!destination.extend_root()) {
1888             return /* ALLOC ERROR */;
1889         }
1890     }
1891
1892     /* The trace the bin */
1893     ref_t cur_ref;
1894     bin_t cur_bin;
1895
1896     /* Process first stage -- do not touch existed tree */
1897     destination.trace(&cur_ref, &cur_bin, sbin);
1898
1899     /* Continue unpacking if needed */
1900     if (cur_bin != sbin) {
1901         bitmap_t bm = BITMAP_EMPTY;
1902
1903         if (sbin < cur_bin) {
1904             bm = destination.cell_[cur_ref].left_.bitmap_;
1905         } else {
1906             bm = destination.cell_[cur_ref].right_.bitmap_;
1907         }
1908
1909         /* Reserving proper number of cells */
1910         if (!destination.reserve_cells( cur_bin.layer() - sbin.layer() )) {
1911             return /* MEMORY ERROR or OVERFLOW ERROR */;
1912         }
1913
1914         /* Continue to trace */
1915         do {
1916             const ref_t ref = destination._alloc_cell();
1917
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;
1922
1923             if (sbin < cur_bin) {
1924                 destination.cell_[cur_ref].is_left_ref_ = true;
1925                 destination.cell_[cur_ref].left_.ref_ = ref;
1926                 cur_bin.to_left();
1927             } else {
1928                 destination.cell_[cur_ref].is_right_ref_ = true;
1929                 destination.cell_[cur_ref].right_.ref_ = ref;
1930                 cur_bin.to_right();
1931             }
1932
1933             cur_ref = ref;
1934         } while (cur_bin != sbin);
1935     }
1936
1937     /* Make copying */
1938     copy(destination, cur_ref, source, sref);
1939 }
1940
1941
1942 /**
1943  * Clone binmap cells to another binmap
1944  */
1945 void binmap_t::copy(binmap_t& destination, const ref_t dref, const binmap_t& source, const ref_t sref)
1946 {
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_
1950     );
1951
1952     size_t sref_size = 0;
1953     size_t dref_size = 0;
1954
1955     ref_t sstack[128];
1956     ref_t dstack[128];
1957     size_t top = 0;
1958
1959     /* Get size of the source subtree */
1960     sstack[top++] = sref;
1961     do {
1962         assert (top < sizeof(sstack) / sizeof(sstack[0]));
1963
1964         ++sref_size;
1965
1966         const cell_t& scell = source.cell_[ sstack[--top] ];
1967         if (scell.is_left_ref_) {
1968             sstack[top++] = scell.left_.ref_;
1969         }
1970         if (scell.is_right_ref_) {
1971             sstack[top++] = scell.right_.ref_;
1972         }
1973
1974     } while (top > 0);
1975
1976     /* Get size of the destination subtree */
1977     dstack[top++] = dref;
1978     do {
1979         assert (top < sizeof(dstack) / sizeof(dstack[0]));
1980
1981         ++dref_size;
1982
1983         const cell_t& dcell = destination.cell_[ dstack[--top] ];
1984         if (dcell.is_left_ref_) {
1985             dstack[top++] = dcell.left_.ref_;
1986         }
1987         if (dcell.is_right_ref_) {
1988             dstack[top++] = dcell.right_.ref_;
1989         }
1990
1991     } while (top > 0);
1992
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 */;
1997         }
1998     }
1999
2000     /* Release the destination subtree */
2001     if (destination.cell_[dref].is_left_ref_) {
2002         destination.free_cell(destination.cell_[dref].left_.ref_);
2003     }
2004     if (destination.cell_[dref].is_right_ref_) {
2005         destination.free_cell(destination.cell_[dref].right_.ref_);
2006     }
2007
2008     /* Make cloning */
2009     sstack[top] = sref;
2010     dstack[top] = dref;
2011     ++top;
2012
2013     do {
2014         --top;
2015         const cell_t& scell = source.cell_[ sstack[top] ];
2016         cell_t& dcell = destination.cell_[ dstack[top] ];
2017
2018         /* Processing left ref */
2019         if (scell.is_left_ref_) {
2020             dcell.is_left_ref_ = true;
2021             dcell.left_.ref_ = destination._alloc_cell();
2022
2023             sstack[top] = scell.left_.ref_;
2024             dstack[top] = dcell.left_.ref_;
2025             ++top;
2026         } else {
2027             dcell.is_left_ref_ = false;
2028             dcell.left_.bitmap_ = scell.left_.bitmap_;
2029         }
2030
2031         /* Processing right ref */
2032         if (scell.is_right_ref_) {
2033             dcell.is_right_ref_ = true;
2034             dcell.right_.ref_ = destination._alloc_cell();
2035
2036             sstack[top] = scell.right_.ref_;
2037             dstack[top] = dcell.right_.ref_;
2038             ++top;
2039         } else {
2040             dcell.is_right_ref_ = false;
2041             dcell.right_.bitmap_ = scell.right_.bitmap_;
2042         }
2043     } while (top > 0);
2044 }
2045
2046 int binmap_t::write_cell(FILE *fp,cell_t c)
2047 {
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 );
2053         return 0;
2054 }
2055
2056
2057 int binmap_t::read_cell(FILE *fp,cell_t *c)
2058 {
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 );
2066
2067         //fprintf(stderr,"binmapread_cell: l%ld r%ld %d %d %d\n", left, right, is_left, is_right, is_free );
2068
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;
2074
2075         return 0;
2076 }
2077
2078 // Arno, 2011-10-20: Persistent storage
2079 int binmap_t::serialize(FILE *fp)
2080 {
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++)
2086          {
2087                 if (write_cell(fp,cell_[i]) < 0)
2088                         return -1;
2089          }
2090          return 0;
2091 }
2092
2093
2094
2095
2096 int binmap_t::deserialize(FILE *fp)
2097 {
2098          bin_t::uint_t rootbinval;
2099          ref_t freetop;
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);
2105
2106          //fprintf(stderr,"Filling BINMAP %p\n", this );
2107          //fprintf(stderr,"Rootbin %lli freetop %li alloc %li num %li\n", rootbinval, freetop, alloccells, cells );
2108
2109          root_bin_ = bin_t(rootbinval);
2110          free_top_ = freetop;
2111          allocated_cells_number_ = alloccells;
2112          cells_number_ = cells;
2113          if (cell_ != NULL) {
2114                  free(cell_);
2115          }
2116          cell_ = (cell_t *)new cell_t[cells];
2117          size_t i=0;
2118          for (i=0; i<cells; i++)
2119          {
2120                 /* Cleans cell */
2121                 memset(&cell_[i], 0, sizeof(cell_[0]));
2122                 if (read_cell(fp,&cell_[i]) < 0)
2123                         return -1;
2124          }
2125          return 0;
2126 }