X-Git-Url: http://git.nguyen.vg/gitweb/?a=blobdiff_plain;f=libcds%2Fsrc%2Fstatic_bitsequence%2Fsdarray.cpp;h=258162acc744911067d19870b51dcb0ee91cb76a;hb=1c40b498ddd6d66b09aff3a22b9f7ddd845250dc;hp=9e0a8a59226f6c55ae85865e7c87f7d3f6292505;hpb=935f20b93a3db7cd2f9f39573d4ab434fcc4356a;p=SXSI%2FXMLTree.git diff --git a/libcds/src/static_bitsequence/sdarray.cpp b/libcds/src/static_bitsequence/sdarray.cpp index 9e0a8a5..258162a 100644 --- 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<>= 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<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)<low; ii = i>>d; + y = selectd2_select(select->sd0,ii,0)+1; // selectd2_select2(select->sd0,ii,0,&y1,&y2); //y1++; y2++;