3 // Implements operations over a bitmap
10 typedef struct sbitmap
14 uint *sdata; // superblock counters
15 byte *bdata; // block counters
16 uint *sdata_0; // superblock counters for select_0() queries
17 byte *bdata_0; // block counters for select_0() queries
21 // creates a bitmap structure from a bitstring, which gets owned
22 bitmap createBitmap (uint *string, uint n, bool isfullbmap);
23 // rank(i): how many 1's are there before position i, not included
24 uint rank (bitmap B, uint i);
25 // select_1(x): returns the position i of the bitmap B such that
26 // the number of ones up to position i is x.
27 uint select_1(bitmap B, uint x);
28 // select_0(x): returns the position i of the bitmap B such that
29 // the number of zeros up to position i is x.
30 uint select_0(bitmap B, uint x);
31 // destroys the bitmap, freeing the original bitstream
32 void destroyBitmap (bitmap B);
34 uint popcount (register uint x);
36 uint sizeofBitmap(bitmap B);