#define logL (logLL-1-5)
#define L (1<<logL)
-int blog(int x) {
+int __blog(int x) {
int l;
l = 0;
while (x>0) {
}
-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;
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;
}
-int getbit2(uchar *B, int i) {
+int __getbit2(uchar *B, int i) {
int j,l;
//j = i / D;
#if 1
-uint getbits(uint *B, int i, int d) {
+uint __getbits(uint *B, int i, int d) {
qword x,z;
B += (i >> logD);
#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,
4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8
};
-static unsigned int selecttbl[8*256];
+static unsigned int __selecttbl[8*256];
-void make_selecttbl(void) {
+void make___selecttbl(void) {
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;
//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;
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;
int r;
uint *s;
- make_selecttbl();
+ make___selecttbl();
if (L/LLL == 0) {
printf("ERROR: L=%d LLL=%d\n",L,LLL);
}
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);
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 = (n+7)/8;
+ 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++) {
}
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;
}
if (f == 1) {
rr = p & (8-1);
- r -= popCount[*q >> (8-1-rr)];
+ r -= _popCount[*q >> (8-1-rr)];
//p = p - rr;
while (1) {
- rr = popCount[*q];
+ rr = _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)];
//p = p - rr;
while (1) {
- rr = popCount[*q ^ 0xff];
+ rr = _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;
if (f == 1) {
rr = p & (8-1);
- r -= popCount[*q >> (8-1-rr)];
+ r -= _popCount[*q >> (8-1-rr)];
//p = p - rr;
while (1) {
- rr = popCount[*q];
+ rr = _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];
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);
}
else {
rr = p & (8-1);
- r -= popCount[(*q ^ 0xff) >> (8-1-rr)];
+ r -= _popCount[(*q ^ 0xff) >> (8-1-rr)];
//p = p - rr;
while (1) {
- rr = popCount[*q ^ 0xff];
+ rr = _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];
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);
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;
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;
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++;
}
}
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);
if (i == 0) return -1;
d = select->d;
-
- x = selectd2_select(select->sd1,i,1) - (i-1);
- x <<= d;
- x += getbits(select->low,(i-1)*d,d);
+ if(select->lasti==(uint)i-1) {
+ while(!__getbit2(select->sd1->buf,++select->lasti));
+ }
+ else {
+ select->lasts = selectd2_select(select->sd1,i,1);
+ }
+ select->lasti = i;
+ //lasts3 = select;
+ x = (select->lasts-(i-1)) << 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) {
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;
}
}
- return x;
+ return x;
}
+
projects / SXSI / XMLTree.git / blobdiff