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