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