bins.h

   1 /*
   2  *  sbit.cpp
   3  *  serp++
   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. Complexity limit: 100+200LoC  */
  14 class bins {
  15
  16 public:
  17     typedef enum { FILLED=0xffff, EMPTY=0x0000, MIXED=0x5555 } fill_t;
  18     static const int NOJOIN;
  19
  20     bins();
  21
  22     bins(const bins& b);
  23
  24     uint16_t    get (bin64_t bin);
  25
  26     void        set (bin64_t bin, fill_t val=FILLED);
  27
  28     void        copy_range (bins& origin, bin64_t range);
  29
  30     bin64_t     find (const bin64_t range, fill_t seek=EMPTY) ;
  31
  32     bin64_t     find_filtered
  33         (bins& filter, bin64_t range, fill_t seek=EMPTY) ;
  34
  35     void        remove (bins& b);
  36
  37     void        dump(const char* note);
  38
  39     uint64_t*   get_stripes (int& count);
  40
  41     uint32_t    size() { return cells_allocated; }
  42
  43     uint64_t    seq_length ();
  44
  45     bin64_t     cover(bin64_t val);
  46
  47     uint64_t    mass ();
  48
  49     bool        is_solid (bin64_t range=bin64_t::ALL, fill_t val=MIXED) ;
  50     bool        is_empty (bin64_t range=bin64_t::ALL) { return is_solid(range,EMPTY); }
  51     bool        is_filled (bin64_t range=bin64_t::ALL) { return is_solid(range,FILLED); }
  52
  53     void        clear ();
  54
  55     static bool is_mixed (uint16_t val) { return val!=EMPTY && val!=FILLED; }
  56     static bool is_solid (uint16_t val) { return val==EMPTY || val==FILLED; }
  57
  58     void        twist (uint64_t mask);
  59
  60 private:
  61
  62     /** Every 16th uint32 is a flag field denoting whether
  63      previous 30 halves (in 15 cells) are deep or not.
  64      The last bit is used as a fill-flag.
  65      Free cells have a value of 0; neither deep nor flat
  66      cell could have a value of 0 except for the root
  67      cell in case the binmap is all-0. */
  68     union {
  69         uint32_t    *cells;
  70         uint16_t    *halves;
  71     };
  72     uint32_t    blocks_allocated;
  73     uint32_t    cells_allocated;
  74     int         height;
  75     uint32_t    ap;
  76     uint64_t    twist_mask;
  77
  78     void extend();
  79
  80     static const uint8_t    SPLIT[16];
  81     static const uint8_t    JOIN[16];
  82
  83     bool        deep(uint32_t half) const {
  84         return cells[(half>>1)|0xf] & (1<<(half&0x1f));
  85     }
  86     void        mark(uint32_t half) {
  87         cells[(half>>1)|0xf] |= (1<<(half&0x1f));
  88     }
  89     void        unmark(uint32_t half) {
  90         cells[(half>>1)|0xf] &= ~(1<<(half&0x1f));
  91     }
  92
  93     void        extend_range();
  94
  95     uint16_t    alloc_cell ();
  96     void        free_cell (uint16_t cell);
  97
  98     /** Join the cell this half is pointing to
  99      (in other words, flatten the half). */
 100     bool        join(uint32_t half) ;
 101
 102     /** Make the half deep. */
 103     void        split(uint32_t half) ;
 104
 105     static uint32_t split16to32(uint16_t half);
 106     static int join32to16(uint32_t cell);
 107
 108     friend class iterator;
 109 #ifdef FRIEND_TEST
 110     FRIEND_TEST(BinsTest,Routines);
 111 #endif
 112 };
 113
 114
 115 /** Iterates over bins; for deep halves, bin==half.
 116  For flat halves, bin is a range of bits in a half.
 117  Iterator may split cells if needed.
 118  Value is either undefined (deep cell, mixed cell)
 119  or FILLED/EMPTY. */
 120 class iterator {
 121 public: // rm this
 122     bins        *host;
 123     uint32_t    history[64];
 124     uint32_t    half;
 125     uint8_t     layer_;
 126     bin64_t     pos;  // TODO: half[] layer bin
 127 public:
 128     iterator(bins* host, bin64_t start=bin64_t(0,0), bool split=false);
 129     ~iterator();
 130     bool deep () { return host->deep(half); }
 131     bool solid () {
 132         return !deep() && bins::is_solid(host->halves[half]);
 133     }
 134     void sibling () { half^=1; pos=pos.sibling(); }
 135     bool end () { return half==1; }
 136     void to (bool right);
 137     void left() {to(0);}
 138     void right() {to(1);}
 139     /** Move to the next defined (non-deep, flat) cell.
 140         If solid==true, move to a solid (0xffff/0x0) cell. */
 141     bin64_t next (bool solid=false);
 142     bin64_t bin() { return pos; }
 143     void towards(bin64_t bin) {
 144         bin64_t next = pos.towards(bin);
 145         assert(next!=bin64_t::NONE);
 146         to(next.is_right());
 147     }
 148     void parent() ;
 149     bool defined() { return !host->deep(half); }
 150     uint16_t& operator* () { return host->halves[half]; }
 151     uint8_t layer() const { return layer_; }
 152 };
 153
 154
 155 class binheap {
 156     bin64_t     *heap_;
 157     uint32_t    filled_;
 158     uint32_t    size_;
 159 public:
 160     binheap();
 161     bin64_t pop();
 162     void    push(bin64_t);
 163     bool    empty() const { return !filled_; }
 164     void    extend();
 165     ~binheap();
 166 };
 167
 168
 169 #endif