lzindex/bitmap.h

   1
   2
   3 // Implements operations over a bitmap
   4
   5 #ifndef BITMAPINCLUDED
   6 #define BITMAPINCLUDED
   7
   8 #include "basics.h"
   9
  10 typedef struct sbitmap
  11  {
  12     uint *data;
  13     uint n;        // # of bits
  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
  18  } *bitmap;
  19
  20
  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);
  33         // popcounts 1's in x
  34 uint popcount (register uint x);
  35
  36 uint sizeofBitmap(bitmap B);
  37 #endif
  38