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