projects / SXSI / XMLTree.git / blobdiff
? search:
summary | shortlog | log | commit | commitdiff | tree
raw | inline | side by side
.
[SXSI/XMLTree.git] / libcds / src / static_bitsequence / sdarray.cpp
diff --git a/libcds/src/static_bitsequence/sdarray.cpp b/libcds/src/static_bitsequence/sdarray.cpp
index 9e0a8a5..258162a 100644 (file)
--- a/libcds/src/static_bitsequence/sdarray.cpp
+++ b/libcds/src/static_bitsequence/sdarray.cpp
@@ -157,10 +157,41 @@ 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 inline unsigned int
+_fast_popcount(int x) {
+  return _popCount[x];
+}
 
 static unsigned int __selecttbl[8*256];
+static int built = 0;
 
 void make___selecttbl(void) {
+  if(built) return;
+  built = 1;
   int i,x,r;
   uint buf[1];
 
@@ -392,11 +423,13 @@ 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;
@@ -407,11 +440,13 @@ int selectd2_select(selectd2 *select, int i,int f) {
     }
     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;
@@ -468,11 +503,13 @@ 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;
@@ -484,7 +521,8 @@ int selectd2_select2(selectd2 *select, int i,int f, int *st, int *en) {
       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++;
@@ -499,11 +537,13 @@ 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;
@@ -515,7 +555,8 @@ int selectd2_select2(selectd2 *select, int i,int f, int *st, int *en) {
       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++;
@@ -649,6 +690,9 @@ int selects3_construct(selects3 *select, int n, uint *buf) {
   return 0;
 }
 
+//selects3 * lasts3=NULL;
+//int lasti=0;
+//int lasts=0;
 
 int selects3_select(selects3 *select, int i) {
   int d,x;
@@ -663,44 +707,42 @@ 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);
   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;
-  //  selectd2_select2(select->sd0,ii,0,&y1,&y2);
-  //y1++;  y2++;
-  //printf("y %d y1 %d  %d\n",y,y1,y2-y1);
-
   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(!__getbit2(select->hi,(8*y+r))) k2++;
                        if(x!=x_orig) k2++;
-                       //cout << "??? i=" << i << " bit=" << __getbit2(select->hi,(8*y+r)) << " minirank=" << minirank << endl;
                        break;
                }
     w = __getbits(q,x*d,d);
@@ -721,29 +763,26 @@ int selects3_selectnext(selects3 *select, int i) {
       z = select->hi[y];
     }
   }
-
        if(x==select->m)
                return (uint)-1;
-
-       /*if(i==0) {
-               for(int kk=0;kk<40;kk++)
-                       cout << ((__getbit2(select->hi,kk))?1:0);
-               cout << endl;
-       }*/
-       int c=8*y+r;//-k2;//+x-r;//x-r;//+r;//-x;
-       while(!__getbit2(select->hi,c)) c++;
+       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);
-       //cout << "i=" << i << " y=" << y << " r=" << r << " x=" << x << " k2=" << k2 << " ii=" << ii << " s2=" <<  selectd2_select(select->sd0,ii,0)+1 
-       //      << " j=" << j << " c=" << c << endl;
-       //while(__getbit2(select->hi,c)==0) c++;
-       //c+=ii-r+x;
-       //if(i==601) c=2;
-       //cout << "c=" << c << " (c<<d)=" << (c<<d) << endl;
-       /*while(select->hi[y]==0) y++;
-       int c = 8*y;
-       z = select->hi[y];
-       while(__getbit((uint*)&z,i++)==0) c++;*/
-
   return __getbits(q,x*d,d)+((c)<<d);
 }
 
@@ -757,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++;
Succinct representation of XML documents. Requires libbp, libcds and libTextCollection.