X-Git-Url: http://git.nguyen.vg/gitweb/?a=blobdiff_plain;f=libcds%2Fsrc%2Fstatic_bitsequence%2Fsdarray.cpp;h=258162acc744911067d19870b51dcb0ee91cb76a;hb=1c40b498ddd6d66b09aff3a22b9f7ddd845250dc;hp=3b772cc6f31e7e2892e601423874f2f43333456c;hpb=d96b0847640fede84d3f9b09babe8c2e5d48d480;p=SXSI%2FXMLTree.git

diff --git a/libcds/src/static_bitsequence/sdarray.cpp b/libcds/src/static_bitsequence/sdarray.cpp
index 3b772cc..258162a 100644
--- a/libcds/src/static_bitsequence/sdarray.cpp
+++ b/libcds/src/static_bitsequence/sdarray.cpp
@@ -26,7 +26,7 @@ typedef unsigned long long qword;
 #define logL (logLL-1-5)
 #define L (1<<logL)
 
-int blog(int x) {
+int __blog(int x) {
   int l;
   l = 0;
   while (x>0) {
@@ -37,22 +37,22 @@ int blog(int x) {
 }
 
 
-int setbit(uint *B, int i,int x) {
+int __setbit(uint *B, int i,int x) {
   int j,l;
-//printf("%u\n",D);
+  //printf("%u\n",D);
   j = i / D;
   l = i % D;
   if (x==0) B[j] &= (~(1<<(D-1-l)));
   else if (x==1) B[j] |= (1<<(D-1-l));
   else {
-    printf("error setbit x=%d\n",x);
+    printf("error __setbit x=%d\n",x);
     exit(1);
   }
   return x;
 }
 
 
-int setbit2(uchar *B, int i,int x) {
+int __setbit2(uchar *B, int i,int x) {
   int j,l;
 
   j = i / 8;
@@ -60,24 +60,24 @@ int setbit2(uchar *B, int i,int x) {
   if (x==0) B[j] &= (~(1<<(8-1-l)));
   else if (x==1) B[j] |= (1<<(8-1-l));
   else {
-    printf("error setbit2 x=%d\n",x);
+    printf("error __setbit2 x=%d\n",x);
     exit(1);
   }
   return x;
 }
 
 
-int setbits(uint *B, int i, int d, int x) {
+int __setbits(uint *B, int i, int d, int x) {
   int j;
 
   for (j=0; j<d; j++) {
-    setbit(B,i+j,(x>>(d-j-1))&1);
+    __setbit(B,i+j,(x>>(d-j-1))&1);
   }
   return x;
 }
 
 
-int getbit(uint *B, int i) {
+int __getbit(uint *B, int i) {
   int j,l;
 
   //j = i / D;
@@ -88,7 +88,7 @@ int getbit(uint *B, int i) {
 }
 
 
-int getbit2(uchar *B, int i) {
+int __getbit2(uchar *B, int i) {
   int j,l;
 
   //j = i / D;
@@ -100,7 +100,7 @@ int getbit2(uchar *B, int i) {
 
 
 #if 1
-uint getbits(uint *B, int i, int d) {
+uint __getbits(uint *B, int i, int d) {
   qword x,z;
 
   B += (i >> logD);
@@ -127,19 +127,19 @@ uint getbits(uint *B, int i, int d) {
 #endif
 
 #if 0
-uint getbits(uint *B, int i, int d) {
+uint __getbits(uint *B, int i, int d) {
   uint j,x;
 
   x = 0;
   for (j=0; j<d; j++) {
     x <<= 1;
-    x += getbit(B,i+j);
+    x += __getbit(B,i+j);
   }
   return x;
 }
 #endif
 
-static const unsigned int popCount[] = {
+static const unsigned int _popCount[] = {
   0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4,
   1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,
   1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,
@@ -157,27 +157,59 @@ static const unsigned int popCount[] = {
   3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
   4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8
 };
+static inline unsigned int
+_fast_popcount2(int x)
+{
+    uint m1 = 0x55555555;
+    uint m2 = 0x33333333;
+    uint m4 = 0x0f0f0f0f;
+    x -= (x >> 1) & m1;
+    x = (x & m2) + ((x >> 2) & m2);
+    x = (x + (x >> 4)) & m4;
+    x += x >>  8;
+    return (x + (x >> 16)) & 0x3f;
+}
+
+static inline unsigned int
+_fast_popcount3(int x) 
+{
+  uint m1 = 0x55555555;
+  uint m2 = 0xc30c30c3;
+  x -= (x >> 1) & m1;
+  x = (x & m2) + ((x >> 2) & m2) + ((x >> 4) & m2);
+  x += x >> 6;
+  return  (x + (x >> 12) + (x >> 24)) & 0x3f;
+}
 
-static unsigned int selecttbl[8*256];
+static inline unsigned int
+_fast_popcount(int x) {
+  return _popCount[x];
+}
+
+static unsigned int __selecttbl[8*256];
+static int built = 0;
 
-void make_selecttbl(void) {
+void make___selecttbl(void) {
+  if(built) return;
+  built = 1;
   int i,x,r;
   uint buf[1];
 
   for (x = 0; x < 256; x++) {
-    setbits(buf,0,8,x);
-    for (r=0; r<8; r++) selecttbl[(r<<8)+x] = -1;
+    __setbits(buf,0,8,x);
+    for (r=0; r<8; r++) __selecttbl[(r<<8)+x] = -1;
     r = 0;
     for (i=0; i<8; i++) {
-      if (getbit(buf,i)) {
-        selecttbl[(r<<8)+x] = i;
+      if (__getbit(buf,i)) {
+        __selecttbl[(r<<8)+x] = i;
         r++;
       }
     }
   }
 }
 
-unsigned int popcount(uint x) {
+
+unsigned int __popCount(uint x) {
   uint r;
   #if 0
   r = x;
@@ -194,19 +226,19 @@ unsigned int popcount(uint x) {
   //r = ((r & 0xffff0000)>>16) + (r & 0x0000ffff);
   r = ((r>>16) + r) & 63;
   #else
-  r = popCount[x & 0xff];
+  r = _popCount[x & 0xff];
   x >>= 8;
-  r += popCount[x & 0xff];
+  r += _popCount[x & 0xff];
   x >>= 8;
-  r += popCount[x & 0xff];
+  r += _popCount[x & 0xff];
   x >>= 8;
-  r += popCount[x & 0xff];
+  r += _popCount[x & 0xff];
   #endif
   return r;
 }
 
 
-unsigned int popcount8(uint x) {
+unsigned int __popCount8(uint x) {
   uint r;
   #if 1
   r = x;
@@ -214,60 +246,64 @@ unsigned int popcount8(uint x) {
   r = ((r & 0xcc)>>2) + (r & 0x33);
   r = ((r>>4) + r) & 0x0f;
   #else
-  r = popCount[x & 0xff];
+  r = _popCount[x & 0xff];
   #endif
   return r;
 }
 
+
 int selectd2_save(selectd2 * s, FILE * fp) {
-	uint wr = 0;
-	wr += fwrite(&s->n,sizeof(uint),1,fp);
-	wr += fwrite(&s->m,sizeof(uint),1,fp);
-	wr += fwrite(&s->size,sizeof(uint),1,fp);
-	wr += fwrite(&s->ss_len,sizeof(uint),1,fp);
-	wr += fwrite(&s->sl_len,sizeof(uint),1,fp);
-	wr += fwrite(s->buf,sizeof(uchar),(s->n+7)/8+1,fp);
-	uint nl = (s->m-1) / L + 1;
-	wr += fwrite(s->lp,sizeof(uint),nl+1,fp);
-	wr += fwrite(s->p,sizeof(uint),nl+1,fp);
-	wr += fwrite(s->ss,sizeof(ushort),s->ss_len,fp);
-	wr += fwrite(s->sl,sizeof(uint),s->sl_len,fp);
-	if(wr!=s->sl_len+s->ss_len+2*(nl+1)+(s->n+7)/8+1+5) 
-		return 1;
-	return 0;
+  uint wr = 0;
+  wr += fwrite(&s->n,sizeof(uint),1,fp);
+  wr += fwrite(&s->m,sizeof(uint),1,fp);
+  wr += fwrite(&s->size,sizeof(uint),1,fp);
+  wr += fwrite(&s->ss_len,sizeof(uint),1,fp);
+  wr += fwrite(&s->sl_len,sizeof(uint),1,fp);
+  wr += fwrite(s->buf,sizeof(uchar),(s->n+7)/8+1,fp);
+  uint nl = (s->m-1) / L + 1;
+  wr += fwrite(s->lp,sizeof(uint),nl+1,fp);
+  wr += fwrite(s->p,sizeof(uint),nl+1,fp);
+  wr += fwrite(s->ss,sizeof(ushort),s->ss_len,fp);
+  wr += fwrite(s->sl,sizeof(uint),s->sl_len,fp);
+  if(wr!=s->sl_len+s->ss_len+2*(nl+1)+(s->n+7)/8+1+5)
+    return 1;
+  return 0;
 }
 
+
 int selectd2_load(selectd2 * s, FILE * fp) {
-	uint rd = 0;
-	rd += fread(&s->n,sizeof(uint),1,fp);
-	rd += fread(&s->m,sizeof(uint),1,fp);
-	rd += fread(&s->size,sizeof(uint),1,fp);
-	rd += fread(&s->ss_len,sizeof(uint),1,fp);
-	rd += fread(&s->sl_len,sizeof(uint),1,fp);
-	s->buf = new uchar[(s->n+7)/8+1];
-	rd += fread(s->buf,sizeof(uchar),(s->n+7)/8+1,fp);
-	uint nl = (s->m-1) / L + 1;
-	s->lp = new uint[nl+1];
-	rd += fread(s->lp,sizeof(uint),nl+1,fp);
-	s->p = new uint[nl+1];
-	rd += fread(s->p,sizeof(uint),nl+1,fp);
-	s->ss = new ushort[s->ss_len];
-	rd += fread(s->ss,sizeof(ushort),s->ss_len,fp);
-	s->sl = new uint[s->sl_len];
-	rd += fread(s->sl,sizeof(uint),s->sl_len,fp);
-	if(rd!=s->sl_len+s->ss_len+2*(nl+1)+(s->n+7)/8+1+5) 
-		return 1;
-	return 0;
+  uint rd = 0;
+  rd += fread(&s->n,sizeof(uint),1,fp);
+  rd += fread(&s->m,sizeof(uint),1,fp);
+  rd += fread(&s->size,sizeof(uint),1,fp);
+  rd += fread(&s->ss_len,sizeof(uint),1,fp);
+  rd += fread(&s->sl_len,sizeof(uint),1,fp);
+  s->buf = new uchar[(s->n+7)/8+1];
+  rd += fread(s->buf,sizeof(uchar),(s->n+7)/8+1,fp);
+  uint nl = (s->m-1) / L + 1;
+  s->lp = new uint[nl+1];
+  rd += fread(s->lp,sizeof(uint),nl+1,fp);
+  s->p = new uint[nl+1];
+  rd += fread(s->p,sizeof(uint),nl+1,fp);
+  s->ss = new ushort[s->ss_len];
+  rd += fread(s->ss,sizeof(ushort),s->ss_len,fp);
+  s->sl = new uint[s->sl_len];
+  rd += fread(s->sl,sizeof(uint),s->sl_len,fp);
+  if(rd!=s->sl_len+s->ss_len+2*(nl+1)+(s->n+7)/8+1+5)
+    return 1;
+  return 0;
 }
 
+
 void selectd2_free(selectd2 * s) {
-	//delete [] s->buf;
-	delete [] s->lp;
-	delete [] s->p;
-	delete [] s->ss;
-	delete [] s->sl;
+  //delete [] s->buf;
+  delete [] s->lp;
+  delete [] s->p;
+  delete [] s->ss;
+  delete [] s->sl;
 }
 
+
 int selectd2_construct(selectd2 *select, int n, uchar *buf) {
   int i,m;
   int nl;
@@ -276,7 +312,7 @@ int selectd2_construct(selectd2 *select, int n, uchar *buf) {
   int r;
   uint *s;
 
-  make_selecttbl();
+  make___selecttbl();
 
   if (L/LLL == 0) {
     printf("ERROR: L=%d LLL=%d\n",L,LLL);
@@ -284,7 +320,7 @@ int selectd2_construct(selectd2 *select, int n, uchar *buf) {
   }
 
   m = 0;
-  for (i=0; i<n; i++) m += getbit2(buf,i);
+  for (i=0; i<n; i++) m += __getbit2(buf,i);
   select->n = n;
   select->m = m;
   //printf("n=%d m=%d\n",n,m);
@@ -294,19 +330,19 @@ int selectd2_construct(selectd2 *select, int n, uchar *buf) {
   s = new uint[m];
   m = 0;
   for (i=0; i<n; i++) {
-    if (getbit2(buf,i)) {
+    if (__getbit2(buf,i)) {
       m++;
       s[m-1] = i;
     }
   }
 
   nl = (m-1) / L + 1;
-  select->size = 0; //ignoring buf, shared with selects3
+  select->size = 0;              //ignoring buf, shared with selects3
   select->lp = new uint[nl+1];
-	for(int k=0;k<nl+1;k++) select->lp[k]=0;
+  for(int k=0;k<nl+1;k++) select->lp[k]=0;
   select->size += (nl+1)*sizeof(uint);
   select->p = new uint[nl+1];
-	for(int k=0;k<nl+1;k++) select->p[k]=0;
+  for(int k=0;k<nl+1;k++) select->p[k]=0;
   select->size += (nl+1)*sizeof(uint);
 
   for (r = 0; r < 2; r++) {
@@ -340,17 +376,17 @@ int selectd2_construct(selectd2 *select, int n, uchar *buf) {
     }
     if (r == 0) {
       select->sl = new uint[ml*L+1];
-			for(int k=0;k<ml*L+1;k++) select->sl[k]=0;
+      for(int k=0;k<ml*L+1;k++) select->sl[k]=0;
       select->size += sizeof(uint)*(ml*L+1);
-			select->sl_len = ml*L+1;
+      select->sl_len = ml*L+1;
       select->ss = new ushort[ms*(L/LLL)+1];
-			for(int k=0;k<ms*(L/LLL)+1;k++) select->ss[k]=0;
-			select->ss_len = ms*(L/LLL)+1;
+      for(int k=0;k<ms*(L/LLL)+1;k++) select->ss[k]=0;
+      select->ss_len = ms*(L/LLL)+1;
       select->size += sizeof(ushort)*(ms*(L/LLL)+1);
     }
   }
   delete [] s;
-	return 0;
+  return 0;
 }
 
 
@@ -387,33 +423,37 @@ int selectd2_select(selectd2 *select, int i,int f) {
 
     if (f == 1) {
       rr = p & (8-1);
-      r -= popCount[*q >> (8-1-rr)];
+      //r -= _popCount[*q >> (8-1-rr)];
+      r -= _fast_popcount(*q >> (8-1-rr));
       //p = p - rr;
 
       while (1) {
-        rr = popCount[*q];
+        //rr = _popCount[*q];
+	rr = _fast_popcount(*q);
         if (r + rr >= i) break;
         r += rr;
         //p += 8;
         q++;
       }
       p = (q - select->buf) << 3;
-      p += selecttbl[((i-r-1)<<8)+(*q)];
+      p += __selecttbl[((i-r-1)<<8)+(*q)];
     }
     else {
       rr = p & (8-1);
-      r -= popCount[(*q ^ 0xff) >> (8-1-rr)];
+      //r -= _popCount[(*q ^ 0xff) >> (8-1-rr)];
+      r -= _fast_popcount((*q ^ 0xff) >> (8-1-rr));
       //p = p - rr;
 
       while (1) {
-        rr = popCount[*q ^ 0xff];
+        //rr = _popCount[*q ^ 0xff];
+	rr = _fast_popcount(*q ^ 0xff);
         if (r + rr >= i) break;
         r += rr;
         //p += 8;
         q++;
       }
       p = (q - select->buf) << 3;
-      p += selecttbl[((i-r-1)<<8)+(*q ^ 0xff)];
+      p += __selecttbl[((i-r-1)<<8)+(*q ^ 0xff)];
     }
   }
   return p;
@@ -463,29 +503,32 @@ int selectd2_select2(selectd2 *select, int i,int f, int *st, int *en) {
 
     if (f == 1) {
       rr = p & (8-1);
-      r -= popCount[*q >> (8-1-rr)];
+      //r -= _popCount[*q >> (8-1-rr)];
+      r -= _fast_popcount(*q >> (8-1-rr));
       //p = p - rr;
 
       while (1) {
-        rr = popCount[*q];
+        //rr = _popCount[*q];
+	rr = _fast_popcount(*q);
         if (r + rr >= i) break;
         r += rr;
         //p += 8;
         q++;
       }
       p = (q - select->buf) << 3;
-      p += selecttbl[((i-r-1)<<8)+(*q)];
+      p += __selecttbl[((i-r-1)<<8)+(*q)];
 
       if ((i>>logL) == ((i+1)>>logL)) {
         i++;
         while (1) {
-          rr = popCount[*q];
+          //rr = _popCount[*q];
+	  r = _fast_popcount(*q);
           if (r + rr >= i) break;
           r += rr;
           q++;
         }
         p2 = (q - select->buf) << 3;
-        p2 += selecttbl[((i-r-1)<<8)+(*q)];
+        p2 += __selecttbl[((i-r-1)<<8)+(*q)];
       }
       else {
         p2 = selectd2_select(select,i+2,f);
@@ -494,29 +537,32 @@ int selectd2_select2(selectd2 *select, int i,int f, int *st, int *en) {
     }
     else {
       rr = p & (8-1);
-      r -= popCount[(*q ^ 0xff) >> (8-1-rr)];
+      //r -= _popCount[(*q ^ 0xff) >> (8-1-rr)];
+      r -= _fast_popcount((*q ^ 0xff) >> (8-1-rr));
       //p = p - rr;
 
       while (1) {
-        rr = popCount[*q ^ 0xff];
+        //rr = _popCount[*q ^ 0xff];
+	rr = _fast_popcount(*q ^ 0xff);
         if (r + rr >= i) break;
         r += rr;
         //p += 8;
         q++;
       }
       p = (q - select->buf) << 3;
-      p += selecttbl[((i-r-1)<<8)+(*q ^ 0xff)];
+      p += __selecttbl[((i-r-1)<<8)+(*q ^ 0xff)];
 
       if ((i>>logL) == ((i+1)>>logL)) {
         i++;
         while (1) {
-          rr = popCount[*q ^ 0xff];
+          //rr = _popCount[*q ^ 0xff];
+	  rr = _fast_popcount(*q ^ 0xff);
           if (r + rr >= i) break;
           r += rr;
           q++;
         }
         p2 = (q - select->buf) << 3;
-        p2 += selecttbl[((i-r-1)<<8)+(*q ^ 0xff)];
+        p2 += __selecttbl[((i-r-1)<<8)+(*q ^ 0xff)];
       }
       else {
         p2 = selectd2_select(select,i+2,f);
@@ -530,57 +576,60 @@ int selectd2_select2(selectd2 *select, int i,int f, int *st, int *en) {
 
 
 int selects3_save(selects3 * s, FILE * fp) {
-	uint wr = 0;
-	wr += fwrite(&s->n,sizeof(uint),1,fp);
-	wr += fwrite(&s->m,sizeof(uint),1,fp);
-	wr += fwrite(&s->size,sizeof(uint),1,fp);
-        wr += fwrite(&s->d,sizeof(uint),1,fp);
-	wr += fwrite(&s->hi_len,sizeof(uint),1,fp);
-        wr += fwrite(&s->low_len,sizeof(uint),1,fp);
-	wr += fwrite(s->hi,sizeof(uchar),s->hi_len,fp);
-	wr += fwrite(s->low,sizeof(uint),s->low_len,fp);
-	if(wr!=(6+s->hi_len+s->low_len))
-		return 1;
-	if(selectd2_save(s->sd0,fp)) return 2;
-	if(selectd2_save(s->sd1,fp)) return 3;
-	return 0;
+  uint wr = 0;
+  wr += fwrite(&s->n,sizeof(uint),1,fp);
+  wr += fwrite(&s->m,sizeof(uint),1,fp);
+  wr += fwrite(&s->size,sizeof(uint),1,fp);
+  wr += fwrite(&s->d,sizeof(uint),1,fp);
+  wr += fwrite(&s->hi_len,sizeof(uint),1,fp);
+  wr += fwrite(&s->low_len,sizeof(uint),1,fp);
+  wr += fwrite(s->hi,sizeof(uchar),s->hi_len,fp);
+  wr += fwrite(s->low,sizeof(uint),s->low_len,fp);
+  if(wr!=(6+s->hi_len+s->low_len))
+    return 1;
+  if(selectd2_save(s->sd0,fp)) return 2;
+  if(selectd2_save(s->sd1,fp)) return 3;
+  return 0;
 }
 
+
 int selects3_load(selects3 * s, FILE * fp) {
-	uint rd = 0;
-	rd += fread(&s->n,sizeof(uint),1,fp);
-	rd += fread(&s->m,sizeof(uint),1,fp);
-	rd += fread(&s->size,sizeof(uint),1,fp);
-	rd += fread(&s->d,sizeof(uint),1,fp);
-	rd += fread(&s->hi_len,sizeof(uint),1,fp);
-	rd += fread(&s->low_len,sizeof(uint),1,fp);
-	s->hi = new uchar[s->hi_len];
-	rd += fread(s->hi,sizeof(uchar),s->hi_len,fp);
-	s->low = new uint[s->low_len];
-	rd += fread(s->low,sizeof(uint),s->low_len,fp);
-	if(rd!=(6+s->hi_len+s->low_len))
-		return 1;
-	s->sd0 = new selectd2;
-	if(selectd2_load(s->sd0,fp)) return 2;
-	s->sd1 = new selectd2;
-	if(selectd2_load(s->sd1,fp)) return 3;
-	delete [] s->sd0->buf;
-	delete [] s->sd1->buf;
-	s->sd0->buf = s->hi;
-	s->sd1->buf = s->hi;
-	return 0;
+  uint rd = 0;
+  rd += fread(&s->n,sizeof(uint),1,fp);
+  rd += fread(&s->m,sizeof(uint),1,fp);
+  rd += fread(&s->size,sizeof(uint),1,fp);
+  rd += fread(&s->d,sizeof(uint),1,fp);
+  rd += fread(&s->hi_len,sizeof(uint),1,fp);
+  rd += fread(&s->low_len,sizeof(uint),1,fp);
+  s->hi = new uchar[s->hi_len];
+  rd += fread(s->hi,sizeof(uchar),s->hi_len,fp);
+  s->low = new uint[s->low_len];
+  rd += fread(s->low,sizeof(uint),s->low_len,fp);
+  if(rd!=(6+s->hi_len+s->low_len))
+    return 1;
+  s->sd0 = new selectd2;
+  if(selectd2_load(s->sd0,fp)) return 2;
+  s->sd1 = new selectd2;
+  if(selectd2_load(s->sd1,fp)) return 3;
+  delete [] s->sd0->buf;
+  delete [] s->sd1->buf;
+  s->sd0->buf = s->hi;
+  s->sd1->buf = s->hi;
+  return 0;
 }
 
+
 void selects3_free(selects3 * s) {
-	delete [] s->hi;
-	delete [] s->low;
-	//delete [] s->sd0->buf;
-	selectd2_free(s->sd0);
-	delete s->sd0;
-	selectd2_free(s->sd1);
-	delete s->sd1;
+  delete [] s->hi;
+  delete [] s->low;
+  //delete [] s->sd0->buf;
+  selectd2_free(s->sd0);
+  delete s->sd0;
+  selectd2_free(s->sd1);
+  delete s->sd1;
 }
 
+
 int selects3_construct(selects3 *select, int n, uint *buf) {
   int i,m;
   int d,mm;
@@ -589,7 +638,7 @@ int selects3_construct(selects3 *select, int n, uint *buf) {
   selectd2 *sd0,*sd1;
 
   m = 0;
-  for (i=0; i<n; i++) m += getbit(buf,i);
+  for (i=0; i<n; i++) m += __getbit(buf,i);
   select->n = n;
   select->m = m;
 
@@ -605,23 +654,23 @@ int selects3_construct(selects3 *select, int n, uint *buf) {
   select->d = d;
 
   buf2 = new uchar[(2*m+8-1)/8+1];
-	for(int k=0;k<(2*m+8-1)/8+1;k++) buf2[k]=0;
-	select->hi_len = (2*m+8-1)/8+1;
+  for(int k=0;k<(2*m+8-1)/8+1;k++) buf2[k]=0;
+  select->hi_len = (2*m+8-1)/8+1;
   low = new uint[(d*m+PBS-1)/PBS+1];
-	for(uint k=0;k<(d*m+PBS-1)/PBS+1;k++) low[k]=0;
-	select->low_len = (d*m+PBS-1)/PBS+1;
+  for(uint k=0;k<(d*m+PBS-1)/PBS+1;k++) low[k]=0;
+  select->low_len = (d*m+PBS-1)/PBS+1;
 
   select->hi = buf2;
   select->low = low;
   select->size = sizeof(uchar)*((2*m+8-1)/8+1) + sizeof(uint)*((d*m+PBS-1)/PBS+1);
 
-  for (i=0; i<m*2; i++) setbit2(buf2,i,0);
+  for (i=0; i<m*2; i++) __setbit2(buf2,i,0);
 
   m = 0;
   for (i=0; i<n; i++) {
-    if (getbit(buf,i)) {
-      setbit2(buf2,(i>>d)+m,1);
-      setbits(low,m*d,d,i & ((1<<d)-1));
+    if (__getbit(buf,i)) {
+      __setbit2(buf2,(i>>d)+m,1);
+      __setbits(low,m*d,d,i & ((1<<d)-1));
       m++;
     }
   }
@@ -633,19 +682,22 @@ int selects3_construct(selects3 *select, int n, uint *buf) {
   selectd2_construct(sd1,m*2,buf2);
   select->sd1 = sd1;
 
-  for (i=0; i<m*2; i++) setbit2(buf2,i,1-getbit2(buf2,i));
+  for (i=0; i<m*2; i++) __setbit2(buf2,i,1-__getbit2(buf2,i));
   selectd2_construct(sd0,m*2,buf2);
   select->sd0 = sd0;
 
-  for (i=0; i<m*2; i++) setbit2(buf2,i,1-getbit2(buf2,i));
-	return 0;
+  for (i=0; i<m*2; i++) __setbit2(buf2,i,1-__getbit2(buf2,i));
+  return 0;
 }
 
+//selects3 * lasts3=NULL;
+//int lasti=0;
+//int lasts=0;
 
 int selects3_select(selects3 *select, int i) {
   int d,x;
 
-  #if 1
+  #if 0
   if (i > select->m) {
     printf("ERROR: m=%d i=%d\n",select->m,i);
     exit(1);
@@ -655,12 +707,83 @@ int selects3_select(selects3 *select, int i) {
   if (i == 0) return -1;
 
   d = select->d;
-
-  x = selectd2_select(select->sd1,i,1) - (i-1);
+	/*if(select->lasti==(uint)i-1) {
+		while(!__getbit2(select->sd1->buf,++select->lasts));
+	} 
+	else {
+	  select->lasts = selectd2_select(select->sd1,i,1);
+	}
+	select->lasti = i;
+	//lasts3 = select; */
+	x = selectd2_select(select->sd1,i,1) - (i-1);
+  //x = (select->lasts-(i-1)) << d;
   x <<= d;
-  x += getbits(select->low,(i-1)*d,d);
+  x += __getbits(select->low,(i-1)*d,d);
   return x;
+}
+
 
+int selects3_selectnext(selects3 *select, int i) {
+	//return selects3_select(select,selects3_rank(select,i)+1);
+  int d,x,w,y;
+  int r,j;
+  int z,ii;
+  uint *q;
+  d = select->d;
+  q = select->low;
+  ii = i>>d;
+  y = selectd2_select(select->sd0,ii,0)+1;
+	int k2=y-ii;
+  x = y - ii;
+	int x_orig = x;
+  j = i - (ii<<d);
+  r = y & 7;
+  y >>= 3;
+  z = select->hi[y];
+  while (1) {
+    if (((z << r) & 0x80) == 0) {
+			if(x!=x_orig) k2++;
+			break;
+		}
+    w = __getbits(q,x*d,d);
+    if (w >= j) {
+      if (w == j) {
+				if(__getbit2(select->hi,(8*y+r))) k2++;
+				x++;
+				r++;
+			}
+      break;
+    }
+    x++;
+    r++;
+		if(__getbit2(select->hi,(8*y+r))) k2++;
+    if (r == 8) {
+      r = 0;
+      y++;
+      z = select->hi[y];
+    }
+  }
+	if(x==select->m)
+		return (uint)-1;
+	int c=8*y+r;
+	int fin=0;
+	for(int kk=0;kk<8-r;kk++) {
+		if(__getbit2(select->hi,c)) {
+			fin=1;
+			break;
+		}
+		c++;
+	}
+	if(!fin) {
+		int pp = c/8;
+		while(select->hi[pp]==0) {
+			pp++;
+			c+=8;
+		}
+		while(!__getbit2(select->hi,c)) c++;
+	}
+	c -= (k2);
+  return __getbits(q,x*d,d)+((c)<<d);
 }
 
 int selects3_rank(selects3 *select, int i) {
@@ -673,6 +796,7 @@ int selects3_rank(selects3 *select, int i) {
   q = select->low;
 
   ii = i>>d;
+
   y = selectd2_select(select->sd0,ii,0)+1;
   //  selectd2_select2(select->sd0,ii,0,&y1,&y2);
   //y1++;  y2++;
@@ -687,7 +811,7 @@ int selects3_rank(selects3 *select, int i) {
   z = select->hi[y];
   while (1) {
     if (((z << r) & 0x80) == 0) break;
-    w = getbits(q,x*d,d);
+    w = __getbits(q,x*d,d);
     if (w >= j) {
       if (w == j) x++;
       break;
@@ -701,5 +825,6 @@ int selects3_rank(selects3 *select, int i) {
     }
   }
 
-  return x;
+	return x;
 }
+