3 * binmap, a hybrid of bitmap and binary tree
5 * Created by Victor Grishchenko on 3/28/09.
6 * Copyright 2009 Delft University of Technology. All rights reserved.
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. */
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).
25 typedef enum { FILLED=0xffff, EMPTY=0x0000, MIXED=0x5555 } fill_t;
26 static const int NOJOIN;
30 /** Copying constructor. */
31 binmap_t(const binmap_t& b);
34 ~binmap_t() { delete [] cells; }
36 /** Get value for the bin. */
37 uint16_t get (bin64_t bin);
39 /** Set value for the bin. */
40 void set (bin64_t bin, fill_t val=FILLED);
42 /** Copy a range from another binmap. */
43 void copy_range (binmap_t& origin, bin64_t range);
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) ;
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. */
53 (binmap_t& filter, bin64_t range, fill_t seek=EMPTY) ;
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);
59 void dump(const char* note);
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);
67 /** Return the number of cells allocated in the binmap. */
68 uint32_t size() { return cells_allocated; }
70 uint64_t seq_length ();
72 /** Return the topmost solid bin which covers the specified bin. */
73 bin64_t cover(bin64_t val);
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); }
86 /** Clear everything, empty all bins. */
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; }
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);
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. */
111 uint32_t blocks_allocated;
112 uint32_t cells_allocated;
119 static const uint8_t SPLIT[16];
120 static const uint8_t JOIN[16];
122 bool deep(uint32_t half) const {
123 return cells[(half>>1)|0xf] & (1<<(half&0x1f));
125 void mark(uint32_t half) {
126 cells[(half>>1)|0xf] |= (1<<(half&0x1f));
128 void unmark(uint32_t half) {
129 cells[(half>>1)|0xf] &= ~(1<<(half&0x1f));
134 uint16_t alloc_cell ();
135 void free_cell (uint16_t cell);
137 /** Join the cell this half is pointing to
138 (in other words, flatten the half). */
139 bool join(uint32_t half) ;
141 /** Make the half deep. */
142 void split(uint32_t half) ;
144 static uint32_t split16to32(uint16_t half);
145 static int join32to16(uint32_t cell);
147 friend class iterator;
149 FRIEND_TEST(BinsTest,Routines);
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)
162 uint32_t history[64];
165 bin64_t pos; // TODO: half[] layer bin
167 iterator(binmap_t* host, bin64_t start=bin64_t(0,0), bool split=false);
169 bool deep () { return host->deep(half); }
171 return !deep() && binmap_t::is_solid(host->halves[half]);
173 void sibling () { half^=1; pos=pos.sibling(); }
174 bool end () { return half==1; }
175 void to (bool right);
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);
188 bool defined() { return !host->deep(half); }
189 uint16_t& operator* () { return host->halves[half]; }
190 uint8_t layer() const { return layer_; }
202 bool empty() const { return !filled_; }