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