5 * Created by Victor Grishchenko on 4/1/09.
6 * Copyright 2009 Delft University of Technology. All rights reserved.
22 // make it work piece by piece
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;
31 void binmap_t::extend () {
32 const size_t nblocks = (blocks_allocated != 0) ? (2 * blocks_allocated) : (1);
34 if( 16 * nblocks > 1 + std::numeric_limits<uint16_t>::max() )
35 return /* The limit of cells number reached */;
37 uint32_t * const ncells = (uint32_t *) realloc(cells, nblocks * 16 * sizeof(uint32_t));
39 return /* Memory allocation error */;
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);
46 blk_ptr[28] = free_top;
48 for(uint16_t i = 13; i != (uint16_t)-1; --i)
49 blk_ptr[2 * i] = blk_off + i + 1;
54 blocks_allocated = nblocks;
58 binmap_t::binmap_t() : height(4), blocks_allocated(0), cells(NULL),
59 free_top(0), cells_allocated(0), twist_mask(0) {
61 assert( free_top == 1 );
64 binmap_t::~binmap_t () {
69 void binmap_t::twist (uint64_t mask) {
70 while ( (1<<height) <= mask )
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);
82 void binmap_t::dump (const char* note) {
84 for(int i=0; i<(blocks_allocated<<5); i++) {
86 printf("|%x ",halves[i]);
88 printf(">%i ",halves[i]);
90 printf("%x ",halves[i]);
97 uint32_t binmap_t::split16to32(uint16_t halfval) {
99 for(int i=0; i<4; i++) {
101 nval |= (SPLIT[halfval&0xf])<<24;
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 )
113 uvar.i = (uvar.i&0x05050505) | ((uvar.i&0x50505050U)>>3);
115 for(int i=3; i>=0; i--) {
117 res |= JOIN[uvar.a[i]];
123 void binmap_t::split (uint32_t half) {
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;
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))
141 int res = join32to16(cells[cellno]);
144 halves[half] = (uint16_t)res;
147 //cells[(half>>1)|0xf] &= ~(1<<(half&0x1f));
148 //(*childdeepcell) &= 0xffff>>1; // clean the full bit
152 void binmap_t::free_cell (uint16_t cell) {
155 halves[2 * cell] = free_top;
159 /** Get a free cell. */
160 uint16_t binmap_t::alloc_cell () {
161 if( cells_allocated == 15 * blocks_allocated )
164 if( cells_allocated == 15 * blocks_allocated ) {
165 assert( free_top != 0 );
171 const uint16_t ref = free_top;
172 free_top = halves[2 * ref];
182 bin64_t iterator::next (bool need_solid) {
184 while (pos.is_right())
187 //if (need_solid ? !solid() : deep())
190 while (need_solid ? !solid() : deep())
196 iterator::iterator(binmap_t* host_, bin64_t start, bool split) {
199 for(int i=0; i<64; i++)
201 pos = bin64_t(host->height,0);
202 layer_ = host->height;
203 while (!start.within(pos))
205 while (pos!=start && (deep() || split))
210 iterator::~iterator () {
211 while (half>1 && !deep())
213 // PROBLEM: may hang in the air if two iters
214 // exist simultaneously
215 // FIX: iterators are not exposed (protected)
219 void iterator::to (bool right) {
222 history[layer()] = half; // FIXME
225 if ( (host->twist_mask >> layer()) & 1 )
226 right = !right; // twist it!
227 half = (host->halves[half]<<1) + right;
231 void binmap_t::extend_range () {
234 uint16_t newroot = alloc_cell();
235 int left = newroot<<1, right = left+1;
236 cells[newroot] = cells[0];
249 void iterator::parent () {
251 host->extend_range();
252 history[layer()+1] = 0;
256 half = history[layer()];
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;
266 while ( i.deep() || (*i!=stop && *i!=seek) )
268 if (!i.deep() && *i==seek)
270 while (i.bin().is_right() && i.bin()!=range)
277 return bin64_t::NONE;
281 uint16_t binmap_t::get (bin64_t bin) {
282 if (bin==bin64_t::NONE)
284 iterator i(this,bin,true);
285 //while ( i.pos!=bin &&
286 // (i.deep() || (*i!=BIN_FULL && *i!=BIN_EMPTY)) )
288 //printf("at %i ",i.half);
290 return *i; // deep cell is never 0xffff or 0x0000; FIXME: API caveat
294 void binmap_t::clear () {
295 set(bin64_t(height,0),EMPTY);
299 uint64_t binmap_t::mass () {
300 iterator i(this,bin64_t(0,0),false);
305 if (*i==binmap_t::FILLED)
306 ret += i.pos.width();
313 void binmap_t::set (bin64_t bin, fill_t val) {
314 if (bin==bin64_t::NONE)
316 assert(val==FILLED || val==EMPTY);
317 iterator i(this,bin,false);
318 while (i.bin()!=bin && (i.deep() || *i!=val))
320 if (!i.deep() && *i==val)
327 } while (i.bin().within(bin));
332 uint64_t* binmap_t::get_stripes (int& count) {
334 uint64_t *stripes = (uint64_t*) malloc(32*8);
336 uint16_t cur = binmap_t::EMPTY;
337 stripes[count++] = 0;
338 iterator i(this,bin64_t(0,0),false);
344 if (cur!=*i) { // new stripe
346 stripes[count++] = i.bin().base_offset();
349 stripes = (uint64_t*) realloc(stripes,size*8);
358 stripes[count++] = i.bin().base_offset();
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);
369 while (zis.deep() || zat.deep()) {
370 zis.left(); zat.left();
375 while (zis.pos.is_right()) {
376 zis.parent(); zat.parent();
378 zis.sibling(); zat.sibling();
383 bin64_t binmap_t::cover(bin64_t val) {
384 if (val==bin64_t::NONE)
386 iterator i(this,val,false);
387 while (i.pos!=val && !i.solid())
390 return bin64_t::NONE;
395 bin64_t binmap_t::find_filtered
396 (binmap_t& filter, bin64_t range, fill_t seek)
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;
405 (ti.deep() || *ti!=stop) :
406 (ti.deep() ? *fi!=FILLED : ( ((*ti^stop)&~*fi) && (*ti!=seek || *fi!=EMPTY) ) )
409 ti.left(); fi.left();
411 if (!ti.deep() && *ti==seek && !fi.deep() && *fi==EMPTY)
413 while (ti.bin().is_right() && ti.bin()!=range)
414 ti.parent(), fi.parent();
417 ti.sibling(), fi.sibling();
419 return bin64_t::NONE;
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();
434 while (zis.pos.is_right()) {
435 zis.parent(); zat.parent();
437 zis.sibling(); zat.sibling();
441 uint64_t binmap_t::seq_length () {
442 iterator i(this,bin64_t(height,0));
443 if (!i.deep() && *i==FILLED)
444 return i.pos.width();
445 while (!i.pos.is_base()) {
446 if (i.deep() || *i!=FILLED)
451 return i.pos.base_offset() + (*i==FILLED ? 1 : 0);
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()) )
461 return i.solid() && (is_mixed(val) || *i==val);
467 heap_ = (bin64_t*) malloc(size_*sizeof(bin64_t));
471 bool bincomp (const bin64_t& a, const bin64_t& b) {
472 register uint64_t ab = a.base_offset(), bb = b.base_offset();
474 return a.tail_bit() < b.tail_bit();
479 bool bincomp_rev (const bin64_t& a, const bin64_t& b) {
480 register uint64_t ab = a.base_offset(), bb = b.base_offset();
482 return a.tail_bit() > b.tail_bit();
487 bin64_t binheap::pop() {
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);
497 void binheap::extend() {
498 std::sort(heap_,heap_+filled_,bincomp_rev);
500 for(int i=1; i<filled_; i++)
501 if (!heap_[i].within(heap_[solid]))
502 heap_[++solid] = heap_[i];
504 if (2*filled_>size_) {
506 heap_ = (bin64_t*) realloc(heap_,size_*sizeof(bin64_t));
510 void binheap::push(bin64_t val) {
513 heap_[filled_++] = val;
514 std::push_heap(heap_, heap_+filled_,bincomp);
517 binheap::~binheap() {