bins.h

   1 /*
   2  *  sbit.cpp
   3  *  binmap, a hybrid of bitmap and binary tree
   4  *
   5  *  Created by Victor Grishchenko on 3/28/09.
   6  *  Copyright 2009 Delft University of Technology. All rights reserved.
   7  *
   8  */
   9 #ifndef BINS_H
  10 #define BINS_H
  11 #include "bin64.h"
  12
  13 class iterator; // FIXME shame
  14
  15 /** A binmap covering 2^64 range. Binmap is a hybrid of a bitmap (aka
  16     bit vector) and a binary tree. The key ability of a binmap is
  17     the aggregation of solid (all-0 or all-1) ranges. */
  18 class binmap_t {
  19
  20 public:
  21     /** Need a 3-valued logic as a range might be either all-0 or all-1
  22         or some mix. In fact, any value different from 0x0 or 0xffff
  23         must be interpreted as MIXED.
  24         All read/write operations on a binmap are made in terms of
  25         aligned binary intervals (bins).
  26      */
  27     typedef enum { FILLED=0xffff, EMPTY=0x0000, MIXED=0x5555 } fill_t;
  28     static const int NOJOIN;
  29
  30     binmap_t();
  31
  32     /** Copying constructor. */
  33     binmap_t(const binmap_t& b);
  34
  35     /** Destructor. */
  36     ~binmap_t();
  37
  38     /** Get value for the bin. */
  39     uint16_t    get (bin64_t bin);
  40
  41     /** Set value for the bin. */
  42     void        set (bin64_t bin, fill_t val=FILLED);
  43
  44     typedef enum {
  45         OR_OP,
  46         AND_OP,
  47         REMOVE_OP,
  48         COPY_OP
  49     } bin_op_t;
  50
  51     /** Copy a range from another binmap. */
  52     void        range_op (binmap_t& mask, bin64_t range, bin_op_t op);
  53     void        range_copy (binmap_t& mask, bin64_t range)
  54         {   range_op(mask, range, COPY_OP);   }
  55     void        range_remove (binmap_t& mask, bin64_t range)
  56         {   range_op(mask, range, REMOVE_OP);   }
  57     void        range_or (binmap_t& mask, bin64_t range)
  58         {   range_op(mask, range, OR_OP);   }
  59     void        range_and (binmap_t& mask, bin64_t range)
  60         {   range_op(mask, range, AND_OP);   }
  61
  62     /** Find the leftmost bin within the specified range which is
  63         either filled or empty. */
  64     bin64_t     find (const bin64_t range, fill_t seek=EMPTY) ;
  65
  66     /** Find the leftmost bin within the specified range which is
  67         either filled or empty. Bins set to 1 in the filter binmap cannot
  68         be returned. In fact, this is an incremental bitwise op. */
  69     bin64_t     find_filtered
  70         (binmap_t& filter, bin64_t range, fill_t seek=EMPTY) ;
  71
  72     /** Bitwise SUB; any bins set to one in the filter binmap should
  73         be set to 0 in this binmap. */
  74     void        remove (binmap_t& filter);
  75
  76     void        dump(const char* note);
  77
  78     /** Represent the binmap as a sequence of 0 and 1 stripes; for each
  79         new stripe only the starting offset is given. The first stripe
  80         is supposed to be empty (if the (0,0) bin is actually filled,
  81         the next stripe will also start at 0). */
  82     uint64_t*   get_stripes (int& count);
  83
  84     /** Return the number of cells allocated in the binmap. */
  85     uint32_t    size() { return cells_allocated; }
  86
  87     uint64_t    seq_length ();
  88
  89     /** Return the topmost solid bin which covers the specified bin. */
  90     bin64_t     cover(bin64_t val);
  91
  92     uint64_t    mass ();
  93
  94     /** Return true if the range is solid (either all-0 or 1). If val is
  95         specified, the interval must be both solid and filled/empty,
  96         depending on the value. */
  97     bool        is_solid (bin64_t range=bin64_t::ALL, fill_t val=MIXED) ;
  98     /** Whether range/bin is empty. */
  99     bool        is_empty (bin64_t range=bin64_t::ALL) { return is_solid(range,EMPTY); }
 100     /** Whether range/bin is filled. */
 101     bool        is_filled (bin64_t range=bin64_t::ALL) { return is_solid(range,FILLED); }
 102
 103     /** Clear everything, empty all bins. */
 104     void        clear ();
 105
 106     /** Returns whether the int is mixed (not all-1 or all-0). */
 107     static bool is_mixed (uint16_t val) { return val!=EMPTY && val!=FILLED; }
 108     /** Returns whether the int is solid (0x0 or 0xffff). */
 109     static bool is_solid (uint16_t val) { return val==EMPTY || val==FILLED; }
 110
 111     /** Twisting is some generalization of XOR. For every 1-bit in the mask,
 112         the respective layer of the binary tree is flipped, i.e. left and
 113         right change places. Twisting is mostly needed for randomization.  */
 114     void        twist (uint64_t mask);
 115
 116     /** Convert binmap to a conventional flat bitmap; only bits corresponding
 117         to solid filled bins are set to 1.
 118         @param range  the bin (the range) to cover
 119         @param height aggregation level; use 2**height bins (2**height base
 120                 layer bits per one bitmap bit).
 121         @param bits   uint16_t array to put bitmap into; must have enough
 122                       of space, i.e. 2**(range.layer()-height-4) cells.  */
 123     void        to_coarse_bitmap (uint16_t* bits, bin64_t range, uint8_t height);
 124
 125 private:
 126
 127     /** Every 16th uint32 is a flag field denoting whether
 128      previous 30 halves (in 15 cells) are deep or not.
 129      The last bit is used as a fill-flag.
 130      Free cells have a value of 0; neither deep nor flat
 131      cell could have a value of 0 except for the root
 132      cell in case the binmap is all-0. */
 133     union {
 134         uint32_t    *cells;
 135         uint16_t    *halves;
 136     };
 137     uint32_t    blocks_allocated;
 138     uint32_t    cells_allocated;
 139     int         height;
 140     uint64_t    twist_mask;
 141     uint16_t    free_top;
 142
 143     void extend();
 144
 145     static const uint8_t    SPLIT[16];
 146     static const uint8_t    JOIN[16];
 147
 148     bool        deep(uint32_t half) const {
 149         return cells[(half>>1)|0xf] & (1<<(half&0x1f));
 150     }
 151     void        mark(uint32_t half) {
 152         cells[(half>>1)|0xf] |= (1<<(half&0x1f));
 153     }
 154     void        unmark(uint32_t half) {
 155         cells[(half>>1)|0xf] &= ~(1<<(half&0x1f));
 156     }
 157
 158     void        extend_range();
 159
 160     uint16_t    alloc_cell ();
 161     void        free_cell (uint16_t cell);
 162
 163     /** Join the cell this half is pointing to
 164      (in other words, flatten the half). */
 165     bool        join(uint32_t half) ;
 166
 167     /** Make the half deep. */
 168     void        split(uint32_t half) ;
 169
 170     static uint32_t split16to32(uint16_t half);
 171     static int join32to16(uint32_t cell);
 172
 173     void        map16 (uint16_t* target, bin64_t range);
 174
 175     friend class iterator;
 176 #ifdef FRIEND_TEST
 177     FRIEND_TEST(BinsTest,Routines);
 178 #endif
 179 };
 180
 181
 182 /** Iterates over bins; for deep halves, bin==half.
 183  For flat halves, bin is a range of bits in a half.
 184  Iterator may split cells if needed.
 185  Value is either undefined (deep cell, mixed cell)
 186  or FILLED/EMPTY. */
 187 class iterator {
 188 public: // rm this
 189     binmap_t        *host;
 190     uint32_t    history[64];
 191     uint32_t    half;
 192     uint8_t     layer_;
 193     bin64_t     pos;  // TODO: half[] layer bin
 194 public:
 195     iterator(binmap_t* host, bin64_t start=bin64_t(0,0), bool split=false);
 196     ~iterator();
 197     bool deep () { return host->deep(half); }
 198     bool solid () {
 199         return !deep() && binmap_t::is_solid(host->halves[half]);
 200     }
 201     void sibling () { half^=1; pos=pos.sibling(); }
 202     bool end () { return half==1; }
 203     void to (bool right);
 204     void left() {to(0);}
 205     void right() {to(1);}
 206     /** Move to the next defined (non-deep, flat) cell.
 207         If solid==true, move to a solid (0xffff/0x0) cell. */
 208     bin64_t next (bool stop_undeep=true, bool stop_solid=false, uint8_t stop_layer=0);
 209     bin64_t next_solid () { return next(false, true,0); }
 210     bin64_t bin() { return pos; }
 211     void towards(bin64_t bin) {
 212         bin64_t next = pos.towards(bin);
 213         assert(next!=bin64_t::NONE);
 214         to(next.is_right());
 215     }
 216     void parent() ;
 217     bool defined() { return !host->deep(half); }
 218     uint16_t& operator* () { return host->halves[half]; }
 219     uint8_t layer() const { return layer_; }
 220 };
 221
 222
 223 class binheap {
 224     bin64_t     *heap_;
 225     uint32_t    filled_;
 226     uint32_t    size_;
 227 public:
 228     binheap();
 229     bin64_t pop();
 230     void    push(bin64_t);
 231     bool    empty() const { return !filled_; }
 232     void    extend();
 233     ~binheap();
 234 };
 235
 236
 237 #endif