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     //assert( (!deep()) || (layer()==min_layer));
 184     while (pos.is_right())
 185         parent();
 186     //parent();
 187     //if (need_solid ? !solid() : deep())
 188     //    right();
 189     sibling();
 190     while (     (!stop_undeep || deep()) &&
 191                 (!stop_solid || (deep() || !solid()) ) &&
 192                 (layer()>stop_layer)      )
 193         left();
 194     return pos;
 195 }
 196
 197
 198 iterator::iterator(binmap_t* host_, bin64_t start, bool split) {
 199     host = host_;
 200     half = 0;
 201     for(int i=0; i<64; i++)
 202         history[i] = 1;
 203     pos = bin64_t(host->height,0);
 204     layer_ = host->height;
 205     while (!start.within(pos))
 206         parent();
 207     while (pos!=start && (deep() || split))
 208         towards(start);
 209 }
 210
 211
 212 iterator::~iterator () {
 213     while (half>1 && !deep())
 214         parent();
 215     // PROBLEM: may hang in the air if two iters
 216     // exist simultaneously
 217     // FIX: iterators are not exposed (protected)
 218 }
 219
 220
 221 void iterator::to (bool right) {
 222     if (!deep())
 223         host->split(half);
 224     history[layer()] = half; // FIXME
 225     pos = pos.to(right);
 226     layer_--;
 227     if ( (host->twist_mask >> layer()) & 1 )
 228         right = !right; // twist it!
 229     half = (host->halves[half]<<1) + right;
 230 }
 231
 232
 233 void binmap_t::extend_range () {
 234     assert(height<62);
 235     height++;
 236     uint16_t newroot = alloc_cell();
 237     int left = newroot<<1, right = left+1;
 238     cells[newroot] = cells[0];
 239     halves[0] = newroot;
 240     halves[1] = 0;
 241     if (deep(0))
 242         mark(left);
 243     else
 244         mark(0);
 245     if (deep(1)) {
 246         mark(right);
 247         unmark(1);
 248     }
 249 }
 250
 251 void iterator::parent () {
 252     if (!half) {
 253         host->extend_range();
 254         history[layer()+1] = 0;
 255     }
 256     pos = pos.parent();
 257     layer_++;
 258     half = history[layer()];
 259     host->join(half);
 260     //host->dump("| ");
 261 }
 262
 263
 264 bin64_t binmap_t::find (const bin64_t range, fill_t seek) {
 265     iterator i(this,range,true);
 266     fill_t stop = seek==EMPTY ? FILLED : EMPTY;
 267     while (true) {
 268         while ( i.deep() || (*i!=stop && *i!=seek) )
 269             i.left();
 270         if (!i.deep() && *i==seek)
 271             return i.bin();
 272         while (i.bin().is_right() && i.bin()!=range)
 273             i.parent();
 274         if (i.bin()==range)
 275             break;
 276         i.parent();
 277         i.right();
 278     }
 279     return bin64_t::NONE;
 280 }
 281
 282
 283 uint16_t binmap_t::get (bin64_t bin) {
 284     if (bin==bin64_t::NONE)
 285         return EMPTY;
 286     iterator i(this,bin,true);
 287     //while ( i.pos!=bin &&
 288     //        (i.deep() || (*i!=BIN_FULL && *i!=BIN_EMPTY)) )
 289     //    i.towards(bin);
 290     //printf("at %i ",i.half);
 291     //dump("get made");
 292     return *i; // deep cell is never 0xffff or 0x0000; FIXME: API caveat
 293 }
 294
 295
 296 void binmap_t::clear () {
 297     set(bin64_t(height,0),EMPTY);
 298 }
 299
 300
 301 uint64_t binmap_t::mass () {
 302     iterator i(this,bin64_t(0,0),false);
 303     uint64_t ret = 0;
 304     while (!i.solid())
 305         i.left();
 306     while (!i.end()) {
 307         if (*i==binmap_t::FILLED)
 308             ret += i.pos.width();
 309         i.next_solid();
 310     }
 311     return ret;
 312 }
 313
 314
 315 void binmap_t::set (bin64_t bin, fill_t val) {
 316     if (bin==bin64_t::NONE)
 317         return;
 318     assert(val==FILLED || val==EMPTY);
 319     iterator i(this,bin,false);
 320     while (i.bin()!=bin && (i.deep() || *i!=val))
 321         i.towards(bin);
 322     if (!i.deep() && *i==val)
 323         return;
 324     while (i.deep())
 325         i.left();
 326     do {
 327         *i = val;
 328         i.next();
 329     } while (i.bin().within(bin));
 330     // dump("just set");
 331 }
 332
 333
 334 uint64_t*   binmap_t::get_stripes (int& count) {
 335     int size = 32;
 336     uint64_t *stripes = (uint64_t*) malloc(32*8);
 337     count = 0;
 338     uint16_t cur = binmap_t::EMPTY;
 339     stripes[count++] = 0;
 340     iterator i(this,bin64_t(0,0),false);
 341     while (!i.solid())
 342         i.left();
 343
 344     while (!i.end()) {
 345
 346         if (cur!=*i) { // new stripe
 347             cur = *i;
 348             stripes[count++] = i.bin().base_offset();
 349             if (count==size) {
 350                 size <<= 1;
 351                 stripes = (uint64_t*) realloc(stripes,size*8);
 352             }
 353         }
 354
 355         i.next_solid();
 356
 357     }
 358
 359     if ( !(count&1) )
 360         stripes[count++] = i.bin().base_offset();
 361
 362     return stripes;
 363 }
 364
 365
 366 void    binmap_t::remove (binmap_t& b) {
 367     uint8_t start_lr = b.height>height ? b.height : height;
 368     bin64_t top(start_lr,0);
 369     iterator zis(this,top), zat(&b,top);
 370     while (!zis.end()) {
 371         while (zis.deep() || zat.deep()) {
 372             zis.left(); zat.left();
 373         }
 374
 375         *zis &= ~*zat;
 376
 377         while (zis.pos.is_right()) {
 378             zis.parent(); zat.parent();
 379         }
 380         zis.sibling(); zat.sibling();
 381     }
 382 }
 383
 384
 385 bin64_t     binmap_t::cover(bin64_t val) {
 386     if (val==bin64_t::NONE)
 387         return val;
 388     iterator i(this,val,false);
 389     while (i.pos!=val && !i.solid())
 390         i.towards(val);
 391     if (!i.solid())
 392         return bin64_t::NONE;
 393     return i.pos;
 394 }
 395
 396
 397 bin64_t     binmap_t::find_filtered
 398     (binmap_t& filter, bin64_t range, fill_t seek)
 399 {
 400     if (range==bin64_t::ALL)
 401         range = bin64_t ( height>filter.height ? height : filter.height, 0 );
 402     iterator ti(this,range,true), fi(&filter,range,true);
 403     fill_t stop = seek==EMPTY ? FILLED : EMPTY;
 404     while (true) {
 405         while (
 406                 fi.deep() ?
 407                 (ti.deep() || *ti!=stop)  :
 408                 (ti.deep() ? *fi!=FILLED :
 409                     ( ((*ti^stop)&~*fi) && (*ti!=seek || *fi!=EMPTY) ) )
 410               )
 411         {
 412             ti.left(); fi.left();
 413         }
 414         if (!ti.deep() && *ti==seek && !fi.deep() && *fi==EMPTY)
 415             return ti.bin();
 416         while (ti.bin().is_right() && ti.bin()!=range)
 417             ti.parent(), fi.parent();
 418         if (ti.bin()==range)
 419             break;
 420         ti.sibling(), fi.sibling();
 421     }
 422     return bin64_t::NONE;
 423 }
 424
 425 void        binmap_t::range_op (binmap_t& mask, bin64_t range, bin_op_t op) {
 426     if (range==bin64_t::ALL)
 427         range = bin64_t ( height>mask.height ? height : mask.height, 0 );
 428     iterator zis(this,range,true), zat(&mask,range,true);
 429     while (zis.pos.within(range)) {
 430         while (zis.deep() || zat.deep()) {
 431             zis.left(); zat.left();
 432         }
 433
 434         switch (op) {
 435             case REMOVE_OP:
 436                 *zis &= ~*zat;
 437                 break;
 438             case AND_OP:
 439                 *zis &= *zat;
 440                 break;
 441             case COPY_OP:
 442                 *zis = *zat;
 443                 break;
 444             case OR_OP:
 445                 *zis |= *zat;
 446         }
 447
 448         while (zis.pos.is_right()) {
 449             zis.parent(); zat.parent();
 450         }
 451         zis.sibling(); zat.sibling();
 452     }
 453 }
 454
 455 uint64_t    binmap_t::seq_length () {
 456     iterator i(this,bin64_t(height,0));
 457     if (!i.deep() && *i==FILLED)
 458         return i.pos.width();
 459     while (!i.pos.is_base()) {
 460         if (i.deep() || *i!=FILLED)
 461             i.left();
 462         else
 463             i.sibling();
 464     }
 465     return i.pos.base_offset() + (*i==FILLED ? 1 : 0);
 466 }
 467
 468
 469 bool        binmap_t::is_solid (bin64_t range, fill_t val)  {
 470     if (range==bin64_t::ALL)
 471         return !deep(0) && (is_mixed(val) || halves[0]==val);
 472     iterator i(this,range,false);
 473     while ( i.pos!=range && (i.deep() || !i.solid()) )
 474         i.towards(range);
 475     return i.solid() && (is_mixed(val) || *i==val);
 476 }
 477
 478
 479 void    binmap_t::map16 (uint16_t* target, bin64_t range) {
 480     iterator lead(this,range,true);
 481     if (!lead.deep()) {
 482         *target = *lead;
 483         return;
 484     }
 485     lead.left();
 486     lead.left();
 487     lead.left();
 488     lead.left();
 489     uint16_t shift = 1;
 490     for(int i=0; i<16; i++) {
 491         if (!lead.deep() && *lead==FILLED)
 492             *target |= shift;
 493         shift<<=1;
 494         lead.next(false,false,range.layer()-4);
 495     }
 496 }
 497
 498
 499 void    binmap_t::to_coarse_bitmap (void* bits, bin64_t range, uint8_t height) {
 500     uint16_t* bits16 = (uint16_t*) bits;
 501     int height16 = range.layer()-height-4;
 502     int wordwidth = 1 << height16;
 503     int offset = range.offset() << height16;
 504     for(int i=0; i<wordwidth; i++)
 505         map16(bits16+i,bin64_t(height+4,offset+i));
 506 }
 507
 508
 509 binheap::binheap() {
 510     size_ = 32;
 511     heap_ = (bin64_t*) malloc(size_*sizeof(bin64_t));
 512     filled_ = 0;
 513 }
 514
 515 bool bincomp (const bin64_t& a, const bin64_t& b) {
 516     register uint64_t ab = a.base_offset(), bb = b.base_offset();
 517     if (ab==bb)
 518         return a.tail_bit() < b.tail_bit();
 519     else
 520         return ab > bb;
 521 }
 522
 523 bool bincomp_rev (const bin64_t& a, const bin64_t& b) {
 524     register uint64_t ab = a.base_offset(), bb = b.base_offset();
 525     if (ab==bb)
 526         return a.tail_bit() > b.tail_bit();
 527     else
 528         return ab < bb;
 529 }
 530
 531 bin64_t binheap::pop() {
 532     if (!filled_)
 533         return bin64_t::NONE;
 534     bin64_t ret = heap_[0];
 535     std::pop_heap(heap_, heap_+filled_--,bincomp);
 536     while (filled_ && heap_[0].within(ret))
 537         std::pop_heap(heap_, heap_+filled_--,bincomp);
 538     return ret;
 539 }
 540
 541 void    binheap::extend() {
 542     std::sort(heap_,heap_+filled_,bincomp_rev);
 543     int solid = 0;
 544     for(int i=1; i<filled_; i++)
 545         if (!heap_[i].within(heap_[solid]))
 546             heap_[++solid] = heap_[i];
 547     filled_ = solid+1;
 548     if (2*filled_>size_) {
 549         size_ <<= 1;
 550         heap_ = (bin64_t*) realloc(heap_,size_*sizeof(bin64_t));
 551     }
 552 }
 553
 554 void    binheap::push(bin64_t val) {
 555     if (filled_==size_)
 556         extend();
 557     heap_[filled_++] = val;
 558     std::push_heap(heap_, heap_+filled_,bincomp);
 559 }
 560
 561 binheap::~binheap() {
 562     free(heap_);
 563 }
 564