bp-darray.h

   1 #ifndef BP_DARRAY_H_
   2 #define BP_DARRAY_H_
   3
   4 #ifdef __cplusplus
   5 extern "C" {
   6 #endif
   7 #include "bp-utils.h"
   8
   9 typedef unsigned char byte;
  10 typedef unsigned short word;
  11 typedef unsigned int dword;
  12
  13 #define OPT_NO_RANK (1<<30)
  14
  15
  16 typedef dword pb;
  17
  18
  19 typedef struct {
  20   int n,m;
  21   int size;
  22   pb *buf;
  23   dword *lp;
  24   dword *sl;
  25   word *ss;
  26   dword *p;
  27
  28   dword *rl;
  29   word *rm;
  30   byte *rs;
  31
  32   int idx_size;
  33 } darray;
  34
  35
  36 darray * bp_darray_construct(int n, pb *buf,int opt);
  37 void bp_darray_free(darray *da);
  38
  39 int bp_darray_select(darray *da, int i,int f);
  40
  41 static inline int bp_darray_rank(darray *da, int i)
  42 {
  43   int r,j,i_rr, i_rrr;
  44   int offset;
  45   pb *p;
  46   byte *buff;
  47   i_rr = i >> logRR;
  48   i_rrr = i >> logRRR;
  49   r = da->rl[i>>logR] + da->rm[i_rr];
  50
  51   j = (i_rrr) & (RR/RRR-1);
  52   offset = i_rr << (logRR-logRRR);
  53   buff = &(da->rs[offset-1]);
  54   while (j > 0) {
  55     r += buff[j];
  56     j--;
  57   }
  58
  59   p = da->buf + ((i_rrr)<<(logRRR-logD));
  60   j = i & (RRR-1);
  61   while (j >= D) {
  62     r += popcount(*p++);
  63     j -= D;
  64   }
  65   r += popcount(*p >> (D-1-j));
  66
  67   return r;
  68 }
  69
  70 darray * bp_darray_pat_construct(int n, pb *buf, int k, pb pat, int opt);
  71 int bp_darray_pat_select(darray *da, int i, pb (*getpat)(pb *));
  72 int bp_darray_pat_rank(darray *da, int i, pb (*getpat)(pb *));
  73
  74 int bp_darray_select_bsearch(darray *da, int i, pb (*getpat)(pb *));
  75
  76
  77
  78 #ifdef __cplusplus
  79 }
  80 #endif
  81
  82
  83 #endif