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