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     void        to_coarse_bitmap (void* bits, bin64_t range, uint8_t height);
 117
 118 private:
 119
 120     /** Every 16th uint32 is a flag field denoting whether
 121      previous 30 halves (in 15 cells) are deep or not.
 122      The last bit is used as a fill-flag.
 123      Free cells have a value of 0; neither deep nor flat
 124      cell could have a value of 0 except for the root
 125      cell in case the binmap is all-0. */
 126     union {
 127         uint32_t    *cells;
 128         uint16_t    *halves;
 129     };
 130     uint32_t    blocks_allocated;
 131     uint32_t    cells_allocated;
 132     int         height;
 133     uint64_t    twist_mask;
 134     uint16_t    free_top;
 135
 136     void extend();
 137
 138     static const uint8_t    SPLIT[16];
 139     static const uint8_t    JOIN[16];
 140
 141     bool        deep(uint32_t half) const {
 142         return cells[(half>>1)|0xf] & (1<<(half&0x1f));
 143     }
 144     void        mark(uint32_t half) {
 145         cells[(half>>1)|0xf] |= (1<<(half&0x1f));
 146     }
 147     void        unmark(uint32_t half) {
 148         cells[(half>>1)|0xf] &= ~(1<<(half&0x1f));
 149     }
 150
 151     void        extend_range();
 152
 153     uint16_t    alloc_cell ();
 154     void        free_cell (uint16_t cell);
 155
 156     /** Join the cell this half is pointing to
 157      (in other words, flatten the half). */
 158     bool        join(uint32_t half) ;
 159
 160     /** Make the half deep. */
 161     void        split(uint32_t half) ;
 162
 163     static uint32_t split16to32(uint16_t half);
 164     static int join32to16(uint32_t cell);
 165
 166     void        map16 (uint16_t* target, bin64_t range);
 167
 168     friend class iterator;
 169 #ifdef FRIEND_TEST
 170     FRIEND_TEST(BinsTest,Routines);
 171 #endif
 172 };
 173
 174
 175 /** Iterates over bins; for deep halves, bin==half.
 176  For flat halves, bin is a range of bits in a half.
 177  Iterator may split cells if needed.
 178  Value is either undefined (deep cell, mixed cell)
 179  or FILLED/EMPTY. */
 180 class iterator {
 181 public: // rm this
 182     binmap_t        *host;
 183     uint32_t    history[64];
 184     uint32_t    half;
 185     uint8_t     layer_;
 186     bin64_t     pos;  // TODO: half[] layer bin
 187 public:
 188     iterator(binmap_t* host, bin64_t start=bin64_t(0,0), bool split=false);
 189     ~iterator();
 190     bool deep () { return host->deep(half); }
 191     bool solid () {
 192         return !deep() && binmap_t::is_solid(host->halves[half]);
 193     }
 194     void sibling () { half^=1; pos=pos.sibling(); }
 195     bool end () { return half==1; }
 196     void to (bool right);
 197     void left() {to(0);}
 198     void right() {to(1);}
 199     /** Move to the next defined (non-deep, flat) cell.
 200         If solid==true, move to a solid (0xffff/0x0) cell. */
 201     bin64_t next (bool stop_undeep=true, bool stop_solid=false, uint8_t stop_layer=0);
 202     bin64_t next_solid () { return next(false, true,0); }
 203     bin64_t bin() { return pos; }
 204     void towards(bin64_t bin) {
 205         bin64_t next = pos.towards(bin);
 206         assert(next!=bin64_t::NONE);
 207         to(next.is_right());
 208     }
 209     void parent() ;
 210     bool defined() { return !host->deep(half); }
 211     uint16_t& operator* () { return host->halves[half]; }
 212     uint8_t layer() const { return layer_; }
 213 };
 214
 215
 216 class binheap {
 217     bin64_t     *heap_;
 218     uint32_t    filled_;
 219     uint32_t    size_;
 220 public:
 221     binheap();
 222     bin64_t pop();
 223     void    push(bin64_t);
 224     bool    empty() const { return !filled_; }
 225     void    extend();
 226     ~binheap();
 227 };
 228
 229
 230 #endif