swcsa/utils/bitmap.h

   1
   2 // Implements operations over a bitmap
   3
   4 #ifndef BITMAPINCLUDED
   5 #define BITMAPINCLUDED
   6
   7 #include "basics.h"
   8
   9 typedef struct sbitmap
  10    { uint *data;
  11      uint n;        // # of bits
  12      uint pop;      // # bits set
  13      uint *sdata;   // superblock counters
  14      uint sSize;        //              size of sdata vector
  15      byte *bdata;   // block counters
  16      uint bSize;        //     size of bdata vector
  17      uint mem_usage;
  18    } *bitmap;
  19
  20
  21         // creates a bitmap structure from a bitstring, which gets owned
  22 bitmap createBitmap (uint *string, uint n);
  23         // rank(i): how many 1's are there before position i, not included
  24 uint rank (bitmap B, uint i);
  25         // select(i): position of i-th 1
  26 uint bselect (bitmap B, uint i);
  27         // destroys the bitmap, freeing the original bitstream
  28 void destroyBitmap (bitmap B);
  29         // popcounts 1's in x
  30 uint popcount (register uint x);
  31
  32 void saveBitmap (char *filename, bitmap b);
  33 bitmap loadBitmap (char *filename, uint *string, uint n);
  34
  35
  36
  37 ////EDU'S functions included here.
  38 //bitmap createBitmapEdu (uint *string, uint n);
  39 //uint popcountEdu (register uint x);     //which is identical to popcount.
  40 //uint rank1Edu(bitmap B, unsigned int position);
  41 //unsigned int isActiveBit(uint *V, uint position);
  42 void showBitVector(uint * V, int vectorSize);
  43
  44 #endif
  45
  46