bins.cpp

   1 /*
   2  *  sbit.cpp
   3  *  serp++
   4  *
   5  *  Created by Victor Grishchenko on 4/1/09.
   6  *  Copyright 2009 Delft University of Technology. All rights reserved.
   7  *
   8  */
   9
  10 #include <algorithm>
  11 #include <cstdio>
  12 #include <cstring>
  13 #include <cstdlib>
  14 #include <limits>
  15 #include <numeric>
  16 #include <utility>
  17
  18 #include "bins.h"
  19
  20 #undef max
  21
  22 // make it work piece by piece
  23
  24 const uint8_t    binmap_t::SPLIT[16] =
  25 {0, 3, 12, 15, 48, 51, 60, 63, 192, 195, 204, 207, 240, 243, 252, 255};
  26 const uint8_t    binmap_t::JOIN[16] =
  27 {0, 1, 4, 5, 2, 3, 6, 7, 8, 9, 12, 13, 10, 11, 14, 15};
  28 const int binmap_t::NOJOIN = 0x10000;
  29
  30
  31 void binmap_t::extend () {
  32     const size_t nblocks = (blocks_allocated != 0) ? (2 * blocks_allocated) : (1);
  33
  34     if( 16 * nblocks > 1 + std::numeric_limits<uint16_t>::max() )
  35         return /* The limit of cells number reached */;
  36
  37     uint32_t * const ncells = (uint32_t *) realloc(cells, nblocks * 16 * sizeof(uint32_t));
  38     if( ncells == NULL )
  39         return /* Memory allocation error */;
  40
  41     size_t blk = nblocks;
  42     while( blk-- != blocks_allocated ) {
  43         uint16_t const blk_off =  16 * blk;
  44         uint16_t * const blk_ptr = reinterpret_cast<uint16_t *>(ncells + blk_off);
  45
  46         blk_ptr[28] = free_top;
  47
  48         for(uint16_t i = 13; i != (uint16_t)-1; --i)
  49             blk_ptr[2 * i] = blk_off + i + 1;
  50
  51         free_top = blk_off;
  52     }
  53
  54     blocks_allocated = nblocks;
  55     cells = ncells;
  56 }
  57
  58 binmap_t::binmap_t() :  height(4), blocks_allocated(0), cells(NULL),
  59                 free_top(0), cells_allocated(0), twist_mask(0) {
  60     alloc_cell();
  61     assert( free_top == 1 );
  62 }
  63
  64 binmap_t::~binmap_t () {
  65     if (cells)
  66         free(cells);
  67 }
  68
  69 void binmap_t::twist (uint64_t mask) {
  70     while ( (1<<height) <= mask )
  71         extend_range();
  72     twist_mask = mask;
  73 }
  74
  75 binmap_t::binmap_t (const binmap_t& b) : height(b.height), free_top(b.free_top),
  76 blocks_allocated(b.blocks_allocated), cells_allocated(b.cells_allocated) {
  77     size_t memsz = blocks_allocated*16*32;
  78     cells = (uint32_t*) malloc(memsz);
  79     memcpy(cells,b.cells,memsz);
  80 }
  81
  82 void binmap_t::dump (const char* note) {
  83     printf("%s\t",note);
  84     for(int i=0; i<(blocks_allocated<<5); i++) {
  85         if ( (i&0x1f)>29 )
  86             printf("|%x ",halves[i]);
  87         else if (deep(i))
  88             printf(">%i ",halves[i]);
  89         else
  90             printf("%x ",halves[i]);
  91         if (i&1)
  92             printf(" ");
  93     }
  94     printf("\n");
  95 }
  96
  97 uint32_t binmap_t::split16to32(uint16_t halfval) {
  98     uint32_t nval = 0;
  99     for(int i=0; i<4; i++) {
 100         nval >>= 8;
 101         nval |= (SPLIT[halfval&0xf])<<24;
 102         halfval >>= 4;
 103     }
 104     return nval;
 105 }
 106
 107
 108 int binmap_t::join32to16(uint32_t cval) {
 109     union { uint32_t i; uint8_t a[4]; } uvar;
 110     uvar.i = cval & (cval>>1) & 0x55555555;
 111     if ( (uvar.i|(uvar.i<<1)) != cval )
 112         return NOJOIN;
 113     uvar.i = (uvar.i&0x05050505) | ((uvar.i&0x50505050U)>>3);
 114     uint16_t res = 0;
 115     for(int i=3; i>=0; i--) {
 116         res <<= 4;
 117         res |= JOIN[uvar.a[i]];
 118     }
 119     return res;
 120 }
 121
 122
 123 void        binmap_t::split (uint32_t half) {
 124     if (deep(half))
 125         return;
 126     uint32_t cell = alloc_cell(), left=cell<<1, right=left+1;
 127     mark(half); //cells[(half>>1)|0xf] |= 1<<(half&0x1f);
 128     uint16_t halfval = halves[half];
 129     uint32_t nval = split16to32(halfval);
 130     halves[left] = nval&0xffff;
 131     halves[right] = nval>>16;
 132     halves[half] = cell;
 133 }
 134
 135
 136 bool        binmap_t::join (uint32_t half) {
 137     uint32_t cellno = halves[half];
 138     int left = cellno<<1, right=left+1;
 139     if (deep(left) || deep(right))
 140         return false;
 141     int res = join32to16(cells[cellno]);
 142     if (res>0xffff)
 143         return false;
 144     halves[half] = (uint16_t)res;
 145     unmark(half);
 146     free_cell(cellno);
 147     //cells[(half>>1)|0xf] &= ~(1<<(half&0x1f));
 148     //(*childdeepcell) &= 0xffff>>1; // clean the full bit
 149     return true;
 150 }
 151
 152 void    binmap_t::free_cell (uint16_t cell) {
 153     --cells_allocated;
 154
 155     halves[2 * cell] = free_top;
 156     free_top = cell;
 157 }
 158
 159 /** Get a free cell. */
 160 uint16_t    binmap_t::alloc_cell () {
 161     if( cells_allocated == 15 * blocks_allocated )
 162         extend();
 163
 164     if( cells_allocated == 15 * blocks_allocated ) {
 165         assert( free_top != 0 );
 166         return 0;
 167     }
 168
 169     ++cells_allocated;
 170
 171     const uint16_t ref = free_top;
 172     free_top = halves[2 * ref];
 173
 174     cells[ref] = 0;
 175     unmark(2 * ref);
 176     unmark(2 * ref + 1);
 177
 178     return ref;
 179 }
 180
 181
 182 bin64_t iterator::next (bool stop_undeep, bool stop_solid, uint8_t stop_layer) {
 183     while (pos.is_right())
 184         parent();
 185     sibling();
 186     while (     (!stop_undeep || deep()) &&
 187                 (!stop_solid || (deep() || !solid()) ) &&
 188                 (layer()>stop_layer)      )
 189         left();
 190     return pos;
 191 }
 192
 193
 194 iterator::iterator(binmap_t* host_, bin64_t start, bool split) {
 195     host = host_;
 196     half = 0;
 197     for(int i=0; i<64; i++)
 198         history[i] = 1;
 199     pos = bin64_t(host->height,0);
 200     layer_ = host->height;
 201     while (!start.within(pos))
 202         parent();
 203     while (pos!=start && (deep() || split))
 204         towards(start);
 205 }
 206
 207
 208 iterator::~iterator () {
 209     while (half>1 && !deep())
 210         parent();
 211     // PROBLEM: may hang in the air if two iters
 212     // exist simultaneously
 213     // FIX: iterators are not exposed (protected)
 214 }
 215
 216
 217 void iterator::to (bool right) {
 218     if (!deep())
 219         host->split(half);
 220     history[layer()] = half; // FIXME
 221     pos = pos.to(right);
 222     layer_--;
 223     if ( (host->twist_mask >> layer()) & 1 )
 224         right = !right; // twist it!
 225     half = (host->halves[half]<<1) + right;
 226 }
 227
 228
 229 void binmap_t::extend_range () {
 230     assert(height<62);
 231     height++;
 232     uint16_t newroot = alloc_cell();
 233     int left = newroot<<1, right = left+1;
 234     cells[newroot] = cells[0];
 235     halves[0] = newroot;
 236     halves[1] = 0;
 237     if (deep(0))
 238         mark(left);
 239     else
 240         mark(0);
 241     if (deep(1)) {
 242         mark(right);
 243         unmark(1);
 244     }
 245 }
 246
 247 void iterator::parent () {
 248     if (!half) {
 249         host->extend_range();
 250         history[layer()+1] = 0;
 251     }
 252     pos = pos.parent();
 253     layer_++;
 254     half = history[layer()];
 255     host->join(half);
 256     //host->dump("| ");
 257 }
 258
 259
 260 bin64_t binmap_t::find (const bin64_t range, fill_t seek) {
 261     iterator i(this,range,true);
 262     fill_t stop = seek==EMPTY ? FILLED : EMPTY;
 263     while (true) {
 264         while ( i.deep() || (*i!=stop && *i!=seek) )
 265             i.left();
 266         if (!i.deep() && *i==seek)
 267             return i.bin();
 268         while (i.bin().is_right() && i.bin()!=range)
 269             i.parent();
 270         if (i.bin()==range)
 271             break;
 272         i.parent();
 273         i.right();
 274     }
 275     return bin64_t::NONE;
 276 }
 277
 278
 279 uint16_t binmap_t::get (bin64_t bin) {
 280     if (bin==bin64_t::NONE)
 281         return EMPTY;
 282     iterator i(this,bin,true);
 283     //while ( i.pos!=bin &&
 284     //        (i.deep() || (*i!=BIN_FULL && *i!=BIN_EMPTY)) )
 285     //    i.towards(bin);
 286     //printf("at %i ",i.half);
 287     //dump("get made");
 288     return *i; // deep cell is never 0xffff or 0x0000; FIXME: API caveat
 289 }
 290
 291
 292 void binmap_t::clear () {
 293     set(bin64_t(height,0),EMPTY);
 294 }
 295
 296
 297 uint64_t binmap_t::mass () {
 298     iterator i(this,bin64_t(0,0),false);
 299     uint64_t ret = 0;
 300     while (!i.solid())
 301         i.left();
 302     while (!i.end()) {
 303         if (*i==binmap_t::FILLED)
 304             ret += i.pos.width();
 305         i.next_solid();
 306     }
 307     return ret;
 308 }
 309
 310
 311 void binmap_t::set (bin64_t bin, fill_t val) {
 312     if (bin==bin64_t::NONE)
 313         return;
 314     assert(val==FILLED || val==EMPTY);
 315     iterator i(this,bin,false);
 316     while (i.bin()!=bin && (i.deep() || *i!=val))
 317         i.towards(bin);
 318     if (!i.deep() && *i==val)
 319         return;
 320     while (i.deep())
 321         i.left();
 322     do {
 323         *i = val;
 324         i.next();
 325     } while (i.bin().within(bin));
 326     // dump("just set");
 327 }
 328
 329
 330 uint64_t*   binmap_t::get_stripes (int& count) {
 331     int size = 32;
 332     uint64_t *stripes = (uint64_t*) malloc(32*8);
 333     count = 0;
 334     uint16_t cur = binmap_t::EMPTY;
 335     stripes[count++] = 0;
 336     iterator i(this,bin64_t(0,0),false);
 337     while (!i.solid())
 338         i.left();
 339
 340     while (!i.end()) {
 341
 342         if (cur!=*i) { // new stripe
 343             cur = *i;
 344             stripes[count++] = i.bin().base_offset();
 345             if (count==size) {
 346                 size <<= 1;
 347                 stripes = (uint64_t*) realloc(stripes,size*8);
 348             }
 349         }
 350
 351         i.next_solid();
 352
 353     }
 354
 355     if ( !(count&1) )
 356         stripes[count++] = i.bin().base_offset();
 357
 358     return stripes;
 359 }
 360
 361
 362 void    binmap_t::remove (binmap_t& b) {
 363     uint8_t start_lr = b.height>height ? b.height : height;
 364     bin64_t top(start_lr,0);
 365     iterator zis(this,top), zat(&b,top);
 366     while (!zis.end()) {
 367         while (zis.deep() || zat.deep()) {
 368             zis.left(); zat.left();
 369         }
 370
 371         *zis &= ~*zat;
 372
 373         while (zis.pos.is_right()) {
 374             zis.parent(); zat.parent();
 375         }
 376         zis.sibling(); zat.sibling();
 377     }
 378 }
 379
 380
 381 bin64_t     binmap_t::cover(bin64_t val) {
 382     if (val==bin64_t::NONE)
 383         return val;
 384     iterator i(this,val,false);
 385     while (i.pos!=val && !i.solid())
 386         i.towards(val);
 387     if (!i.solid())
 388         return bin64_t::NONE;
 389     return i.pos;
 390 }
 391
 392
 393 bin64_t     binmap_t::find_filtered
 394     (binmap_t& filter, bin64_t range, fill_t seek)
 395 {
 396     if (range==bin64_t::ALL)
 397         range = bin64_t ( height>filter.height ? height : filter.height, 0 );
 398     iterator ti(this,range,true), fi(&filter,range,true);
 399     fill_t stop = seek==EMPTY ? FILLED : EMPTY;
 400     while (true) {
 401         while (
 402                 fi.deep() ?
 403                 (ti.deep() || *ti!=stop)  :
 404                 (ti.deep() ? *fi!=FILLED :
 405                     ( ((*ti^stop)&~*fi) && (*ti!=seek || *fi!=EMPTY) ) )
 406               )
 407         {
 408             ti.left(); fi.left();
 409         }
 410         if (!ti.deep() && *ti==seek && !fi.deep() && *fi==EMPTY)
 411             return ti.bin();
 412         while (ti.bin().is_right() && ti.bin()!=range)
 413             ti.parent(), fi.parent();
 414         if (ti.bin()==range)
 415             break;
 416         ti.sibling(), fi.sibling();
 417     }
 418     return bin64_t::NONE;
 419 }
 420
 421 void        binmap_t::range_op (binmap_t& mask, bin64_t range, bin_op_t op) {
 422     if (range==bin64_t::ALL)
 423         range = bin64_t ( height>mask.height ? height : mask.height, 0 );
 424     iterator zis(this,range,true), zat(&mask,range,true);
 425     while (zis.pos.within(range)) {
 426         while (zis.deep() || zat.deep()) {
 427             zis.left(); zat.left();
 428         }
 429
 430         switch (op) {
 431             case REMOVE_OP:
 432                 *zis &= ~*zat;
 433                 break;
 434             case AND_OP:
 435                 *zis &= *zat;
 436                 break;
 437             case COPY_OP:
 438                 *zis = *zat;
 439                 break;
 440             case OR_OP:
 441                 *zis |= *zat;
 442         }
 443
 444         while (zis.pos.is_right()) {
 445             zis.parent(); zat.parent();
 446         }
 447         zis.sibling(); zat.sibling();
 448     }
 449 }
 450
 451 uint64_t    binmap_t::seq_length () {
 452     iterator i(this,bin64_t(height,0));
 453     if (!i.deep() && *i==FILLED)
 454         return i.pos.width();
 455     while (!i.pos.is_base()) {
 456         if (i.deep() || *i!=FILLED)
 457             i.left();
 458         else
 459             i.sibling();
 460     }
 461     return i.pos.base_offset() + (*i==FILLED ? 1 : 0);
 462 }
 463
 464
 465 bool        binmap_t::is_solid (bin64_t range, fill_t val)  {
 466     if (range==bin64_t::ALL)
 467         return !deep(0) && (is_mixed(val) || halves[0]==val);
 468     iterator i(this,range,false);
 469     while ( i.pos!=range && (i.deep() || !i.solid()) )
 470         i.towards(range);
 471     return i.solid() && (is_mixed(val) || *i==val);
 472 }
 473
 474
 475 void    binmap_t::map16 (uint16_t* target, bin64_t range) {
 476     iterator lead(this,range,true);
 477     if (!lead.deep()) {
 478         *target = *lead;
 479         return;
 480     }
 481     lead.left();
 482     lead.left();
 483     lead.left();
 484     lead.left();
 485     uint16_t shift = 1;
 486     for(int i=0; i<16; i++) {
 487         if (!lead.deep() && *lead==FILLED)
 488             *target |= shift;
 489         shift<<=1;
 490         lead.next(false,false,range.layer()-4);
 491     }
 492 }
 493
 494
 495 void    binmap_t::to_coarse_bitmap (uint16_t* bits, bin64_t range, uint8_t height) {
 496     //assert(range.layer()-height>=4);
 497     int height16 = range.layer()-height-4;
 498     int wordwidth = height16 > 0 ? (1 << height16) : 1;
 499     int offset = height16 > 0 ? (range.offset() << height16) :
 500                                 (range.offset() >> -height16);
 501     for(int i=0; i<wordwidth; i++)
 502         map16(bits+i,bin64_t(height+4,offset+i));
 503 }
 504
 505
 506 binheap::binheap() {
 507     size_ = 32;
 508     heap_ = (bin64_t*) malloc(size_*sizeof(bin64_t));
 509     filled_ = 0;
 510 }
 511
 512 bool bincomp (const bin64_t& a, const bin64_t& b) {
 513     register uint64_t ab = a.base_offset(), bb = b.base_offset();
 514     if (ab==bb)
 515         return a.tail_bit() < b.tail_bit();
 516     else
 517         return ab > bb;
 518 }
 519
 520 bool bincomp_rev (const bin64_t& a, const bin64_t& b) {
 521     register uint64_t ab = a.base_offset(), bb = b.base_offset();
 522     if (ab==bb)
 523         return a.tail_bit() > b.tail_bit();
 524     else
 525         return ab < bb;
 526 }
 527
 528 bin64_t binheap::pop() {
 529     if (!filled_)
 530         return bin64_t::NONE;
 531     bin64_t ret = heap_[0];
 532     std::pop_heap(heap_, heap_+filled_--,bincomp);
 533     while (filled_ && heap_[0].within(ret))
 534         std::pop_heap(heap_, heap_+filled_--,bincomp);
 535     return ret;
 536 }
 537
 538 void    binheap::extend() {
 539     std::sort(heap_,heap_+filled_,bincomp_rev);
 540     int solid = 0;
 541     for(int i=1; i<filled_; i++)
 542         if (!heap_[i].within(heap_[solid]))
 543             heap_[++solid] = heap_[i];
 544     filled_ = solid+1;
 545     if (2*filled_>size_) {
 546         size_ <<= 1;
 547         heap_ = (bin64_t*) realloc(heap_,size_*sizeof(bin64_t));
 548     }
 549 }
 550
 551 void    binheap::push(bin64_t val) {
 552     if (filled_==size_)
 553         extend();
 554     heap_[filled_++] = val;
 555     std::push_heap(heap_, heap_+filled_,bincomp);
 556 }
 557
 558 binheap::~binheap() {
 559     free(heap_);
 560 }
 561