* Copyright 2009 Delft University of Technology. All rights reserved.
*
*/
+
+#include <algorithm>
+#include <cstdio>
+#include <cstring>
+#include <cstdlib>
+#include <limits>
+#include <numeric>
+#include <utility>
+
#include "bins.h"
-#include <string.h>
+
+#undef max
// make it work piece by piece
-const uint8_t bins::SPLIT[16] =
+const uint8_t binmap_t::SPLIT[16] =
{0, 3, 12, 15, 48, 51, 60, 63, 192, 195, 204, 207, 240, 243, 252, 255};
-const uint8_t bins::JOIN[16] =
+const uint8_t binmap_t::JOIN[16] =
{0, 1, 4, 5, 2, 3, 6, 7, 8, 9, 12, 13, 10, 11, 14, 15};
-const int bins::NOJOIN = 0x10000;
+const int binmap_t::NOJOIN = 0x10000;
+
+
+void binmap_t::extend () {
+ const size_t nblocks = (blocks_allocated != 0) ? (2 * blocks_allocated) : (1);
+
+ if( 16 * nblocks > 1 + std::numeric_limits<uint16_t>::max() )
+ return /* The limit of cells number reached */;
+
+ uint32_t * const ncells = (uint32_t *) realloc(cells, nblocks * 16 * sizeof(uint32_t));
+ if( ncells == NULL )
+ return /* Memory allocation error */;
+
+ size_t blk = nblocks;
+ while( blk-- != blocks_allocated ) {
+ uint16_t const blk_off = 16 * blk;
+ uint16_t * const blk_ptr = reinterpret_cast<uint16_t *>(ncells + blk_off);
+
+ blk_ptr[28] = free_top;
+
+ for(uint16_t i = 13; i != (uint16_t)-1; --i)
+ blk_ptr[2 * i] = blk_off + i + 1;
+ free_top = blk_off;
+ }
-void bins::extend () {
- uint16_t nblocks = blocks_allocated ? (blocks_allocated<<1) : 1;
- size_t had_bytes = blocks_allocated<<6;
- size_t need_bytes = nblocks<<6;
- cells = (uint32_t*) realloc(cells,need_bytes);
- memset(((char*)cells)+had_bytes,0,need_bytes-had_bytes);
- for(int b=blocks_allocated; b<nblocks; b++)
- cells[(b<<4)|0xf] = 0x55555555; // cells are free
blocks_allocated = nblocks;
+ cells = ncells;
+}
+
+binmap_t::binmap_t() : height(4), blocks_allocated(0), cells(NULL),
+ free_top(0), cells_allocated(0), twist_mask(0) {
+ alloc_cell();
+ assert( free_top == 1 );
+}
+
+binmap_t::~binmap_t () {
+ if (cells)
+ free(cells);
}
-bins::bins() : height(4), blocks_allocated(0), cells(NULL),
- ap(0), cells_allocated(0) {
- extend();
- assert(!alloc_cell());
+void binmap_t::twist (uint64_t mask) {
+ while ( (1<<height) <= mask )
+ extend_range();
+ twist_mask = mask;
}
-bins::bins (const bins& b) : height(b.height), ap(b.ap),
+binmap_t::binmap_t (const binmap_t& b) : height(b.height), free_top(b.free_top),
blocks_allocated(b.blocks_allocated), cells_allocated(b.cells_allocated) {
size_t memsz = blocks_allocated*16*32;
cells = (uint32_t*) malloc(memsz);
memcpy(cells,b.cells,memsz);
}
-void bins::dump (const char* note) {
+void binmap_t::dump (const char* note) {
printf("%s\t",note);
for(int i=0; i<(blocks_allocated<<5); i++) {
if ( (i&0x1f)>29 )
printf("\n");
}
-uint32_t bins::split16to32(uint16_t halfval) {
+uint32_t binmap_t::split16to32(uint16_t halfval) {
uint32_t nval = 0;
for(int i=0; i<4; i++) {
nval >>= 8;
}
-int bins::join32to16(uint32_t cval) {
+int binmap_t::join32to16(uint32_t cval) {
union { uint32_t i; uint8_t a[4]; } uvar;
uvar.i = cval & (cval>>1) & 0x55555555;
if ( (uvar.i|(uvar.i<<1)) != cval )
}
-void bins::split (uint32_t half) {
+void binmap_t::split (uint32_t half) {
if (deep(half))
return;
uint32_t cell = alloc_cell(), left=cell<<1, right=left+1;
}
-bool bins::join (uint32_t half) {
+bool binmap_t::join (uint32_t half) {
uint32_t cellno = halves[half];
int left = cellno<<1, right=left+1;
if (deep(left) || deep(right))
return true;
}
-void bins::free_cell (uint16_t cell) {
- cells[cell] = 0;
- int left = cell<<1, right=left+1;
- mark(left);
- unmark(right);
- if (ap==cell+1)
- ap--;
- cells_allocated--;
+void binmap_t::free_cell (uint16_t cell) {
+ --cells_allocated;
+
+ halves[2 * cell] = free_top;
+ free_top = cell;
}
/** Get a free cell. */
-uint16_t bins::alloc_cell () {
- uint16_t ap1 = ap;
- cells_allocated++;
- for(; ap<(blocks_allocated<<4); ap++) {
- if ((ap&0xf)==0xf)
- continue;
- if (!cells[ap] && deep(ap<<1)) {
- unmark(ap<<1);
- return ap++;
- }
- }
- if (ap1)
- ap = 0;
- else
+uint16_t binmap_t::alloc_cell () {
+ if( cells_allocated == 15 * blocks_allocated )
extend();
- cells_allocated--;
- return alloc_cell();
+
+ if( cells_allocated == 15 * blocks_allocated ) {
+ assert( free_top != 0 );
+ return 0;
+ }
+
+ ++cells_allocated;
+
+ const uint16_t ref = free_top;
+ free_top = halves[2 * ref];
+
+ cells[ref] = 0;
+ unmark(2 * ref);
+ unmark(2 * ref + 1);
+
+ return ref;
}
-bin64_t iterator::next (bool need_solid) {
- assert(!deep());
+bin64_t iterator::next (bool stop_undeep, bool stop_solid, uint8_t stop_layer) {
while (pos.is_right())
parent();
- //parent();
- //if (need_solid ? !solid() : deep())
- // right();
sibling();
- while (need_solid ? !solid() : deep())
+ while ( (!stop_undeep || deep()) &&
+ (!stop_solid || (deep() || !solid()) ) &&
+ (layer()>stop_layer) )
left();
return pos;
}
-iterator::iterator(bins* host_, bin64_t start, bool split) {
+iterator::iterator(binmap_t* host_, bin64_t start, bool split) {
host = host_;
half = 0;
for(int i=0; i<64; i++)
history[i] = 1;
pos = bin64_t(host->height,0);
+ layer_ = host->height;
while (!start.within(pos))
parent();
while (pos!=start && (deep() || split))
void iterator::to (bool right) {
if (!deep())
host->split(half);
- history[pos.layer()] = half; // FIXME
+ history[layer()] = half; // FIXME
pos = pos.to(right);
+ layer_--;
+ if ( (host->twist_mask >> layer()) & 1 )
+ right = !right; // twist it!
half = (host->halves[half]<<1) + right;
- //host->dump("/\\ ");
}
-void bins::extend_range () {
+void binmap_t::extend_range () {
assert(height<62);
height++;
uint16_t newroot = alloc_cell();
void iterator::parent () {
if (!half) {
host->extend_range();
- history[pos.layer()+1] = 0;
+ history[layer()+1] = 0;
}
pos = pos.parent();
- half = history[pos.layer()];
+ layer_++;
+ half = history[layer()];
host->join(half);
//host->dump("| ");
}
-bin64_t bins::find (const bin64_t range, const uint8_t layer, fill_t seek) {
+bin64_t binmap_t::find (const bin64_t range, fill_t seek) {
iterator i(this,range,true);
fill_t stop = seek==EMPTY ? FILLED : EMPTY;
while (true) {
- while ( i.bin().layer()>layer && (i.deep() || *i!=stop) )
+ while ( i.deep() || (*i!=stop && *i!=seek) )
i.left();
- if (i.bin().layer()==layer && !i.deep() && *i==seek)
+ if (!i.deep() && *i==seek)
return i.bin();
while (i.bin().is_right() && i.bin()!=range)
i.parent();
}
-uint16_t bins::get (bin64_t bin) {
+uint16_t binmap_t::get (bin64_t bin) {
+ if (bin==bin64_t::NONE)
+ return EMPTY;
iterator i(this,bin,true);
//while ( i.pos!=bin &&
// (i.deep() || (*i!=BIN_FULL && *i!=BIN_EMPTY)) )
// i.towards(bin);
//printf("at %i ",i.half);
//dump("get made");
- return *i; // deep cell is never 0xffff or 0x0000
+ return *i; // deep cell is never 0xffff or 0x0000; FIXME: API caveat
+}
+
+
+void binmap_t::clear () {
+ set(bin64_t(height,0),EMPTY);
+}
+
+
+uint64_t binmap_t::mass () {
+ iterator i(this,bin64_t(0,0),false);
+ uint64_t ret = 0;
+ while (!i.solid())
+ i.left();
+ while (!i.end()) {
+ if (*i==binmap_t::FILLED)
+ ret += i.pos.width();
+ i.next_solid();
+ }
+ return ret;
}
-void bins::set (bin64_t bin, fill_t val) {
+void binmap_t::set (bin64_t bin, fill_t val) {
+ if (bin==bin64_t::NONE)
+ return;
assert(val==FILLED || val==EMPTY);
iterator i(this,bin,false);
while (i.bin()!=bin && (i.deep() || *i!=val))
}
-uint64_t* bins::get_stripes (int& count) {
+uint64_t* binmap_t::get_stripes (int& count) {
int size = 32;
uint64_t *stripes = (uint64_t*) malloc(32*8);
count = 0;
- uint16_t cur = bins::EMPTY;
+ uint16_t cur = binmap_t::EMPTY;
stripes[count++] = 0;
- iterator i(this,0,false);
+ iterator i(this,bin64_t(0,0),false);
while (!i.solid())
i.left();
}
}
- i.next(true);
+ i.next_solid();
}
}
-void bins::remove (bins& b) {
+void binmap_t::remove (binmap_t& b) {
uint8_t start_lr = b.height>height ? b.height : height;
bin64_t top(start_lr,0);
iterator zis(this,top), zat(&b,top);
}
+bin64_t binmap_t::cover(bin64_t val) {
+ if (val==bin64_t::NONE)
+ return val;
+ iterator i(this,val,false);
+ while (i.pos!=val && !i.solid())
+ i.towards(val);
+ if (!i.solid())
+ return bin64_t::NONE;
+ return i.pos;
+}
+
+
+bin64_t binmap_t::find_filtered
+ (binmap_t& filter, bin64_t range, fill_t seek)
+{
+ if (range==bin64_t::ALL)
+ range = bin64_t ( height>filter.height ? height : filter.height, 0 );
+ iterator ti(this,range,true), fi(&filter,range,true);
+ fill_t stop = seek==EMPTY ? FILLED : EMPTY;
+ while (true) {
+ while (
+ fi.deep() ?
+ (ti.deep() || *ti!=stop) :
+ (ti.deep() ? *fi!=FILLED :
+ ( ((*ti^stop)&~*fi) && (*ti!=seek || *fi!=EMPTY) ) )
+ )
+ {
+ ti.left(); fi.left();
+ }
+ if (!ti.deep() && *ti==seek && !fi.deep() && *fi==EMPTY)
+ return ti.bin();
+ while (ti.bin().is_right() && ti.bin()!=range)
+ ti.parent(), fi.parent();
+ if (ti.bin()==range)
+ break;
+ ti.sibling(), fi.sibling();
+ }
+ return bin64_t::NONE;
+}
+
+void binmap_t::range_op (binmap_t& mask, bin64_t range, bin_op_t op) {
+ if (range==bin64_t::ALL)
+ range = bin64_t ( height>mask.height ? height : mask.height, 0 );
+ iterator zis(this,range,true), zat(&mask,range,true);
+ while (zis.pos.within(range)) {
+ while (zis.deep() || zat.deep()) {
+ zis.left(); zat.left();
+ }
+
+ switch (op) {
+ case REMOVE_OP:
+ *zis &= ~*zat;
+ break;
+ case AND_OP:
+ *zis &= *zat;
+ break;
+ case COPY_OP:
+ *zis = *zat;
+ break;
+ case OR_OP:
+ *zis |= *zat;
+ }
+
+ while (zis.pos.is_right()) {
+ zis.parent(); zat.parent();
+ }
+ zis.sibling(); zat.sibling();
+ }
+}
+
+uint64_t binmap_t::seq_length () {
+ iterator i(this,bin64_t(height,0));
+ if (!i.deep() && *i==FILLED)
+ return i.pos.width();
+ while (!i.pos.is_base()) {
+ if (i.deep() || *i!=FILLED)
+ i.left();
+ else
+ i.sibling();
+ }
+ return i.pos.base_offset() + (*i==FILLED ? 1 : 0);
+}
+
+
+bool binmap_t::is_solid (bin64_t range, fill_t val) {
+ if (range==bin64_t::ALL)
+ return !deep(0) && (is_mixed(val) || halves[0]==val);
+ iterator i(this,range,false);
+ while ( i.pos!=range && (i.deep() || !i.solid()) )
+ i.towards(range);
+ return i.solid() && (is_mixed(val) || *i==val);
+}
+
+
+void binmap_t::map16 (uint16_t* target, bin64_t range) {
+ iterator lead(this,range,true);
+ if (!lead.deep()) {
+ *target = *lead;
+ return;
+ }
+ lead.left();
+ lead.left();
+ lead.left();
+ lead.left();
+ uint16_t shift = 1;
+ for(int i=0; i<16; i++) {
+ if (!lead.deep() && *lead==FILLED)
+ *target |= shift;
+ shift<<=1;
+ lead.next(false,false,range.layer()-4);
+ }
+}
+
+
+void binmap_t::to_coarse_bitmap (uint16_t* bits, bin64_t range, uint8_t height) {
+ //assert(range.layer()-height>=4);
+ int height16 = range.layer()-height-4;
+ int wordwidth = height16 > 0 ? (1 << height16) : 1;
+ int offset = height16 > 0 ? (range.offset() << height16) :
+ (range.offset() >> -height16);
+ for(int i=0; i<wordwidth; i++)
+ map16(bits+i,bin64_t(height+4,offset+i));
+}
+
+
binheap::binheap() {
size_ = 32;
heap_ = (bin64_t*) malloc(size_*sizeof(bin64_t));
binheap::~binheap() {
free(heap_);
}
+
projects / swift-upb.git / blobdiff