src/libswift_udp/binmap.h

   1 #ifndef __binmap_h__
   2 #define __binmap_h__
   3
   4 #include <cstddef>
   5 #include "bin.h"
   6 #include "compat.h"
   7 #include "serialize.h"
   8
   9 namespace swift {
  10
  11 /**
  12  * Binmap class
  13  */
  14 class binmap_t : Serializable {
  15 public:
  16     /** Type of bitmap */
  17     typedef int32_t bitmap_t;
  18     /** Type of reference */
  19     typedef uint32_t ref_t;
  20
  21
  22     /**
  23      * Constructor
  24      */
  25     binmap_t();
  26
  27
  28     /**
  29      * Destructor
  30      */
  31     ~binmap_t();
  32
  33
  34     /**
  35      * Set the bin
  36      */
  37     void set(const bin_t& bin);
  38
  39
  40     /**
  41      * Reset the bin
  42      */
  43     void reset(const bin_t& bin);
  44
  45
  46     /**
  47      * Empty all bins
  48      */
  49     void clear();
  50
  51
  52     /**
  53      * Ric: Fill all bins, size is given by the source's root
  54      */
  55     void fill(const binmap_t& source);
  56
  57
  58     /**
  59      * Whether binmap is empty
  60      */
  61     bool is_empty() const;
  62
  63
  64     /**
  65      * Whether binmap is filled
  66      */
  67     bool is_filled() const;
  68
  69
  70     /**
  71      * Whether range/bin is empty
  72      */
  73     bool is_empty(const bin_t& bin) const;
  74
  75
  76     /**
  77      * Whether range/bin is filled
  78      */
  79     bool is_filled(const bin_t& bin) const;
  80
  81
  82     /**
  83      * Return the topmost solid bin which covers the specified bin
  84      */
  85     bin_t cover(const bin_t& bin) const;
  86
  87
  88     /**
  89      * Find first empty bin
  90      */
  91     bin_t find_empty() const;
  92
  93
  94     /**
  95      * Find first filled bin
  96      */
  97     bin_t find_filled() const;
  98
  99
 100     /**
 101      * Get number of allocated cells
 102      */
 103     size_t cells_number() const;
 104
 105
 106     /**
 107      * Get total size of the binmap (Arno: =number of bytes it occupies in memory)
 108      */
 109     size_t total_size() const;
 110
 111
 112     /**
 113      * Echo the binmap status to stdout
 114      */
 115     void status() const;
 116
 117
 118     /**
 119      * Find first additional bin in source
 120      */
 121     static bin_t find_complement(const binmap_t& destination, const binmap_t& source, const bin_t::uint_t twist);
 122
 123
 124     /**
 125      * Find first additional bin of the source inside specified range
 126      */
 127     static bin_t find_complement(const binmap_t& destination, const binmap_t& source, bin_t range, const bin_t::uint_t twist);
 128
 129
 130     /**
 131      * Copy one binmap to another
 132      */
 133     static void copy(binmap_t& destination, const binmap_t& source);
 134
 135
 136     /**
 137      * Copy a range from one binmap to another binmap
 138      */
 139     static void copy(binmap_t& destination, const binmap_t& source, const bin_t& range);
 140
 141
 142     // Arno, 2011-10-20: Persistent storage
 143     int serialize(FILE *fp);
 144     int deserialize(FILE *fp);
 145 private:
 146     #pragma pack(push, 1)
 147
 148     /**
 149      * Structure of cell halves
 150      */
 151     typedef struct {
 152         union {
 153             bitmap_t bitmap_;
 154             ref_t ref_;
 155         };
 156     } half_t;
 157
 158     /**
 159      * Structure of cells
 160      */
 161     typedef union {
 162         struct {
 163             half_t left_;
 164             half_t right_;
 165             bool is_left_ref_ : 1;
 166             bool is_right_ref_ : 1;
 167             bool is_free_ : 1;
 168         };
 169         ref_t free_next_;
 170     } cell_t;
 171
 172     #pragma pack(pop)
 173
 174 private:
 175
 176     /** Allocates one cell (dirty allocation) */
 177     ref_t _alloc_cell();
 178
 179     /** Allocates one cell */
 180     ref_t alloc_cell();
 181
 182     /** Reserve cells allocation capacity */
 183     bool reserve_cells(size_t count);
 184
 185     /** Releases the cell */
 186     void free_cell(ref_t cell);
 187
 188     /** Extend root */
 189     bool extend_root();
 190
 191     /** Pack a trace of cells */
 192     void pack_cells(ref_t* cells);
 193
 194
 195     /** Pointer to the list of blocks */
 196     cell_t* cell_;
 197
 198     /** Number of available cells */
 199     size_t cells_number_;
 200
 201     /** Number of allocated cells */
 202     size_t allocated_cells_number_;
 203
 204     /** Front of the free cell list */
 205     ref_t free_top_;
 206
 207     /** The root bin */
 208     bin_t root_bin_;
 209
 210
 211     /** Trace the bin */
 212     void trace(ref_t* ref, bin_t* bin, const bin_t& target) const;
 213
 214     /** Trace the bin */
 215     void trace(ref_t* ref, bin_t* bin, ref_t** history, const bin_t& target) const;
 216
 217
 218     /** Sets low layer bitmap */
 219     void _set__low_layer_bitmap(const bin_t& bin, const bitmap_t bitmap);
 220
 221     /** Sets high layer bitmap */
 222     void _set__high_layer_bitmap(const bin_t& bin, const bitmap_t bitmap);
 223
 224
 225     /** Clone binmap cells to another binmap */
 226     static void copy(binmap_t& destination, const ref_t dref, const binmap_t& source, const ref_t sref);
 227
 228     static void _copy__range(binmap_t& destination, const binmap_t& source, const ref_t sref, const bin_t sbin);
 229
 230
 231     /** Find first additional bin in source */
 232     static bin_t _find_complement(const bin_t& bin, const ref_t dref, const binmap_t& destination, const ref_t sref, const binmap_t& source, const bin_t::uint_t twist);
 233     static bin_t _find_complement(const bin_t& bin, const bitmap_t dbitmap, const ref_t sref, const binmap_t& source, const bin_t::uint_t twist);
 234     static bin_t _find_complement(const bin_t& bin, const ref_t dref, const binmap_t& destination, const bitmap_t sbitmap, const bin_t::uint_t twist);
 235     static bin_t _find_complement(const bin_t& bin, const bitmap_t dbitmap, const bitmap_t sbitmap, const bin_t::uint_t twist);
 236
 237
 238     /* Disabled */
 239     binmap_t& operator = (const binmap_t&);
 240
 241     /* Disabled */
 242     binmap_t(const binmap_t&);
 243
 244     // Arno, 2011-10-20: Persistent storage
 245     int write_cell(FILE *fp,cell_t c);
 246     int read_cell(FILE *fp,cell_t *c);
 247 };
 248
 249 } // namespace end
 250
 251 #endif /*_binmap_h__*/