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