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