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