projects
/
SXSI
/
XMLTree.git
/ blobdiff
commit
grep
author
committer
pickaxe
?
search:
re
summary
|
shortlog
|
log
|
commit
|
commitdiff
|
tree
raw
|
inline
| side by side
fixes
[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
3b772cc
..
f904aa3
100644
(file)
--- 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)
#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 l;
l = 0;
while (x>0) {
@@
-37,7
+37,7
@@
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);
j = i / D;
int j,l;
//printf("%u\n",D);
j = i / D;
@@
-45,14
+45,14
@@
int setbit(uint *B, int i,int x) {
if (x==0) B[j] &= (~(1<<(D-1-l)));
else if (x==1) B[j] |= (1<<(D-1-l));
else {
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;
}
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;
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 {
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;
}
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++) {
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;
}
}
return x;
}
-int getbit(uint *B, int i) {
+int
__
getbit(uint *B, int i) {
int j,l;
//j = i / D;
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;
int j,l;
//j = i / D;
@@
-100,7
+100,7
@@
int getbit2(uchar *B, int i) {
#if 1
#if 1
-uint getbits(uint *B, int i, int d) {
+uint
__
getbits(uint *B, int i, int d) {
qword x,z;
B += (i >> logD);
qword x,z;
B += (i >> logD);
@@
-127,19
+127,19
@@
uint getbits(uint *B, int i, int d) {
#endif
#if 0
#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;
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
}
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,
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,
@@
-158,26
+158,26
@@
static const unsigned int popCount[] = {
4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8
};
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++) {
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++) {
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++;
}
}
}
}
r++;
}
}
}
}
-unsigned int
popc
ount(uint x) {
+unsigned int
__popC
ount(uint x) {
uint r;
#if 0
r = x;
uint r;
#if 0
r = x;
@@
-194,19
+194,19
@@
unsigned int popcount(uint x) {
//r = ((r & 0xffff0000)>>16) + (r & 0x0000ffff);
r = ((r>>16) + r) & 63;
#else
//r = ((r & 0xffff0000)>>16) + (r & 0x0000ffff);
r = ((r>>16) + r) & 63;
#else
- r = popCount[x & 0xff];
+ r =
_
popCount[x & 0xff];
x >>= 8;
x >>= 8;
- r += popCount[x & 0xff];
+ r +=
_
popCount[x & 0xff];
x >>= 8;
x >>= 8;
- r += popCount[x & 0xff];
+ r +=
_
popCount[x & 0xff];
x >>= 8;
x >>= 8;
- r += popCount[x & 0xff];
+ r +=
_
popCount[x & 0xff];
#endif
return r;
}
#endif
return r;
}
-unsigned int
popc
ount8(uint x) {
+unsigned int
__popC
ount8(uint x) {
uint r;
#if 1
r = x;
uint r;
#if 1
r = x;
@@
-214,7
+214,7
@@
unsigned int popcount8(uint x) {
r = ((r & 0xcc)>>2) + (r & 0x33);
r = ((r>>4) + r) & 0x0f;
#else
r = ((r & 0xcc)>>2) + (r & 0x33);
r = ((r>>4) + r) & 0x0f;
#else
- r = popCount[x & 0xff];
+ r =
_
popCount[x & 0xff];
#endif
return r;
}
#endif
return r;
}
@@
-276,7
+276,7
@@
int selectd2_construct(selectd2 *select, int n, uchar *buf) {
int r;
uint *s;
int r;
uint *s;
- make_selecttbl();
+ make_
__
selecttbl();
if (L/LLL == 0) {
printf("ERROR: L=%d LLL=%d\n",L,LLL);
if (L/LLL == 0) {
printf("ERROR: L=%d LLL=%d\n",L,LLL);
@@
-284,7
+284,7
@@
int selectd2_construct(selectd2 *select, int n, uchar *buf) {
}
m = 0;
}
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);
select->n = n;
select->m = m;
//printf("n=%d m=%d\n",n,m);
@@
-294,7
+294,7
@@
int selectd2_construct(selectd2 *select, int n, uchar *buf) {
s = new uint[m];
m = 0;
for (i=0; i<n; i++) {
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;
}
m++;
s[m-1] = i;
}
@@
-387,33
+387,33
@@
int selectd2_select(selectd2 *select, int i,int f) {
if (f == 1) {
rr = p & (8-1);
if (f == 1) {
rr = p & (8-1);
- r -= popCount[*q >> (8-1-rr)];
+ r -=
_
popCount[*q >> (8-1-rr)];
//p = p - rr;
while (1) {
//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;
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);
}
else {
rr = p & (8-1);
- r -= popCount[(*q ^ 0xff) >> (8-1-rr)];
+ r -=
_
popCount[(*q ^ 0xff) >> (8-1-rr)];
//p = p - rr;
while (1) {
//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;
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;
}
}
return p;
@@
-463,29
+463,29
@@
int selectd2_select2(selectd2 *select, int i,int f, int *st, int *en) {
if (f == 1) {
rr = p & (8-1);
if (f == 1) {
rr = p & (8-1);
- r -= popCount[*q >> (8-1-rr)];
+ r -=
_
popCount[*q >> (8-1-rr)];
//p = p - rr;
while (1) {
//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;
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) {
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;
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 {
p2 = selectd2_select(select,i+2,f);
@@
-494,29
+494,29
@@
int selectd2_select2(selectd2 *select, int i,int f, int *st, int *en) {
}
else {
rr = p & (8-1);
}
else {
rr = p & (8-1);
- r -= popCount[(*q ^ 0xff) >> (8-1-rr)];
+ r -=
_
popCount[(*q ^ 0xff) >> (8-1-rr)];
//p = p - rr;
while (1) {
//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;
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) {
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;
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);
}
else {
p2 = selectd2_select(select,i+2,f);
@@
-589,7
+589,7
@@
int selects3_construct(selects3 *select, int n, uint *buf) {
selectd2 *sd0,*sd1;
m = 0;
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->n = n;
select->m = m;
@@
-615,13
+615,13
@@
int selects3_construct(selects3 *select, int n, uint *buf) {
select->low = low;
select->size = sizeof(uchar)*((2*m+8-1)/8+1) + sizeof(uint)*((d*m+PBS-1)/PBS+1);
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++) {
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++;
}
}
m++;
}
}
@@
-633,11
+633,11
@@
int selects3_construct(selects3 *select, int n, uint *buf) {
selectd2_construct(sd1,m*2,buf2);
select->sd1 = sd1;
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;
selectd2_construct(sd0,m*2,buf2);
select->sd0 = sd0;
- 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));
return 0;
}
return 0;
}
@@
-658,7
+658,7
@@
int selects3_select(selects3 *select, int i) {
x = selectd2_select(select->sd1,i,1) - (i-1);
x <<= d;
x = selectd2_select(select->sd1,i,1) - (i-1);
x <<= d;
- x += getbits(select->low,(i-1)*d,d);
+ x +=
__
getbits(select->low,(i-1)*d,d);
return x;
}
return x;
}
@@
-687,7
+687,7
@@
int selects3_rank(selects3 *select, int i) {
z = select->hi[y];
while (1) {
if (((z << r) & 0x80) == 0) break;
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;
if (w >= j) {
if (w == j) x++;
break;