add .gitignore

[swift-upb.git] / bins.h

diff --git a/bins.h b/bins.h
index c6a69f1..df48c48 100644 (file)
--- a/bins.h
+++ b/bins.h
@@ -10,6 +10,8 @@
 #define BINS_H
 #include "bin64.h"
 
+class iterator; // FIXME shame
+
 /** A binmap covering 2^64 range. Binmap is a hybrid of a bitmap (aka
     bit vector) and a binary tree. The key ability of a binmap is
     the aggregation of solid (all-0 or all-1) ranges. */
@@ -30,14 +32,32 @@ public:
     /** Copying constructor. */
     binmap_t(const binmap_t& b);
     
+    /** Destructor. */
+    ~binmap_t(); 
+
     /** Get value for the bin. */
     uint16_t    get (bin64_t bin); 
     
     /** Set value for the bin. */
     void        set (bin64_t bin, fill_t val=FILLED); 
     
+    typedef enum {
+        OR_OP,
+        AND_OP,
+        REMOVE_OP,
+        COPY_OP
+    } bin_op_t;
+    
     /** Copy a range from another binmap. */
-    void        copy_range (binmap_t& origin, bin64_t range);
+    void        range_op (binmap_t& mask, bin64_t range, bin_op_t op);
+    void        range_copy (binmap_t& mask, bin64_t range)
+        {   range_op(mask, range, COPY_OP);   }
+    void        range_remove (binmap_t& mask, bin64_t range)
+        {   range_op(mask, range, REMOVE_OP);   }
+    void        range_or (binmap_t& mask, bin64_t range)
+        {   range_op(mask, range, OR_OP);   }
+    void        range_and (binmap_t& mask, bin64_t range)
+        {   range_op(mask, range, AND_OP);   }
     
     /** Find the leftmost bin within the specified range which is
         either filled or empty. */
@@ -93,6 +113,15 @@ public:
         right change places. Twisting is mostly needed for randomization.  */
     void        twist (uint64_t mask);
     
+    /** Convert binmap to a conventional flat bitmap; only bits corresponding
+        to solid filled bins are set to 1.
+        @param range  the bin (the range) to cover
+        @param height aggregation level; use 2**height bins (2**height base
+                layer bits per one bitmap bit). 
+        @param bits   uint16_t array to put bitmap into; must have enough
+                      of space, i.e. 2**(range.layer()-height-4) cells.  */
+    void        to_coarse_bitmap (uint16_t* bits, bin64_t range, uint8_t height);
+    
 private:
     
     /** Every 16th uint32 is a flag field denoting whether
@@ -108,8 +137,8 @@ private:
     uint32_t    blocks_allocated;
     uint32_t    cells_allocated;
     int         height;
-    uint32_t    ap;
     uint64_t    twist_mask;
+    uint16_t    free_top;
     
     void extend();
     
@@ -140,6 +169,8 @@ private:
     
     static uint32_t split16to32(uint16_t half);
     static int join32to16(uint32_t cell);
+
+    void        map16 (uint16_t* target, bin64_t range);
     
     friend class iterator;
 #ifdef FRIEND_TEST
@@ -174,7 +205,8 @@ public:
     void right() {to(1);}
     /** Move to the next defined (non-deep, flat) cell.
         If solid==true, move to a solid (0xffff/0x0) cell. */
-    bin64_t next (bool solid=false);
+    bin64_t next (bool stop_undeep=true, bool stop_solid=false, uint8_t stop_layer=0);
+    bin64_t next_solid () { return next(false, true,0); }
     bin64_t bin() { return pos; }
     void towards(bin64_t bin) {
         bin64_t next = pos.towards(bin);