X-Git-Url: http://git.nguyen.vg/gitweb/?a=blobdiff_plain;f=libcds%2Fsrc%2Fstatic_bitsequence%2Fsdarray.cpp;h=4fe52b24b2e1b9f6129b8e9ac3f2f4f3c210f40c;hb=f32808a35be7a1e62830a5972473178014fa44e5;hp=949726a9c8bcfef9ce30125ee3e5b433808bd07b;hpb=dc02a833a150dbef202bc14aca74c51360d4a631;p=SXSI%2FXMLTree.git

diff --git a/libcds/src/static_bitsequence/sdarray.cpp b/libcds/src/static_bitsequence/sdarray.cpp
index 949726a..4fe52b2 100644
--- a/libcds/src/static_bitsequence/sdarray.cpp
+++ b/libcds/src/static_bitsequence/sdarray.cpp
@@ -1,6 +1,7 @@
 
 #include <sdarray.h>
-
+using std::min;
+using std::max;
 #if 0
 typedef unsigned int qword;
 #define logD 4
@@ -157,10 +158,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 +424,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 +441,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 +504,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 +522,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 +538,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 +556,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++;
@@ -672,8 +714,8 @@ int selects3_select(selects3 *select, int i) {
 	else {
 	  select->lasts = selectd2_select(select->sd1,i,1);
 	}
-	select->lasti = i;*/
-	//lasts3 = select;
+	select->lasti = i;
+	//lasts3 = select; */
 	x = selectd2_select(select->sd1,i,1) - (i-1);
   //x = (select->lasts-(i-1)) << d;
   x <<= d;
@@ -755,6 +797,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++;