add .gitignore

[swift-upb.git] / bins.cpp

diff --git a/bins.cpp b/bins.cpp
index 80c531d..6376bad 100644 (file)
--- a/bins.cpp
+++ b/bins.cpp
@@ -10,11 +10,12 @@
 #include <algorithm>
 #include <cstdio>
 #include <cstring>
+#include <cstdlib>
 #include <limits>
 #include <numeric>
 #include <utility>
 
-#include "binmap.h"
+#include "bins.h"
 
 #undef max
 
@@ -60,6 +61,11 @@ binmap_t::binmap_t() :  height(4), blocks_allocated(0), cells(NULL),
     assert( free_top == 1 );
 }
 
+binmap_t::~binmap_t () {
+    if (cells)
+        free(cells);
+}
+
 void binmap_t::twist (uint64_t mask) {
     while ( (1<<height) <= mask )
         extend_range();
@@ -173,15 +179,13 @@ uint16_t    binmap_t::alloc_cell () {
 }
 
 
-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;
 }
@@ -298,7 +302,7 @@ uint64_t binmap_t::mass () {
     while (!i.end()) {
         if (*i==binmap_t::FILLED)
             ret += i.pos.width();
-        i.next(true);
+        i.next_solid();
     }
     return ret;
 }
@@ -344,7 +348,7 @@ uint64_t*   binmap_t::get_stripes (int& count) {
             }
         }
 
-        i.next(true);
+        i.next_solid();
 
     }
 
@@ -397,7 +401,8 @@ bin64_t     binmap_t::find_filtered
         while ( 
                 fi.deep() ?
                 (ti.deep() || *ti!=stop)  :
-                (ti.deep() ? *fi!=FILLED : ( ((*ti^stop)&~*fi) && (*ti!=seek || *fi!=EMPTY) ) ) 
+                (ti.deep() ? *fi!=FILLED : 
+                    ( ((*ti^stop)&~*fi) && (*ti!=seek || *fi!=EMPTY) ) ) 
               ) 
         {
             ti.left(); fi.left();                
@@ -413,17 +418,28 @@ bin64_t     binmap_t::find_filtered
     return bin64_t::NONE;    
 }
 
-// FIXME unite with remove(); do bitwise()
-void        binmap_t::copy_range (binmap_t& origin, bin64_t range) { 
+void        binmap_t::range_op (binmap_t& mask, bin64_t range, bin_op_t op) {
     if (range==bin64_t::ALL)
-        range = bin64_t ( height>origin.height ? height : origin.height, 0 );
-    iterator zis(this,range,true), zat(&origin,range,true);
+        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();
         }
-        
-        *zis = *zat;
+
+        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();
@@ -433,7 +449,7 @@ void        binmap_t::copy_range (binmap_t& origin, bin64_t range) {
 }
 
 uint64_t    binmap_t::seq_length () {
-    iterator i(this);
+    iterator i(this,bin64_t(height,0));
     if (!i.deep() && *i==FILLED)
         return i.pos.width();
     while (!i.pos.is_base()) {
@@ -456,6 +472,37 @@ bool        binmap_t::is_solid (bin64_t range, fill_t 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));
@@ -511,3 +558,4 @@ void    binheap::push(bin64_t val) {
 binheap::~binheap() {
     free(heap_);
 }
+