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