projects
/
SXSI
/
libbp.git
/ blobdiff
commit
grep
author
committer
pickaxe
?
search:
re
summary
|
shortlog
|
log
|
commit
|
commitdiff
|
tree
raw
|
inline
| side by side
Silence a printf warning for %lu on 32bits archs.
[SXSI/libbp.git]
/
bp-core.c
diff --git
a/bp-core.c
b/bp-core.c
index
b01c1d2
..
700e3e5
100644
(file)
--- a/
bp-core.c
+++ b/
bp-core.c
@@
-14,17
+14,16
@@
#define MBid(i) ((i)>>logMB)
#define MBfirst(i) ((i) & (~(MB-1)))
#define MBlast(i) ((i) | (MB-1))
#define MBid(i) ((i)>>logMB)
#define MBfirst(i) ((i) & (~(MB-1)))
#define MBlast(i) ((i) | (MB-1))
-#define max(a,b) \
- ({ __typeof__ (a) _a = (a); \
- __typeof__ (b) _b = (b); \
- _a > _b ? _a : _b; })
+static int min(int a, int b)
+{
+ return (a <= b) ? a : b;
+}
-#define min(a,b) \
- ({ __typeof__ (a) _a = (a); \
- __typeof__ (b) _b = (b); \
- _a <= _b ? _a : _b; })
-
+static int max(int a, int b)
+{
+ return (a >= b) ? a : b;
+}
pb getpat_preorder(pb *b)
{
pb getpat_preorder(pb *b)
{
@@
-109,7
+108,7
@@
int search_SB_r(bp *b, int i, int rel)
pb *p,x,w;
n = b->n;
pb *p,x,w;
n = b->n;
- il = min((SBid(i) + 1) << logSB,n);
+ il = min((SBid(i) + 1) << logSB,
n);
p = &b->B[i>>logD];
while (i<il) {
x = *p++;
p = &b->B[i>>logD];
while (i<il) {
x = *p++;
@@
-119,14
+118,14
@@
int search_SB_r(bp *b, int i, int rel)
while (j>0) {
w = (x >> (D-ETW)) & ((1<<ETW)-1);
if (rel >= -ETW && rel <= ETW) {
while (j>0) {
w = (x >> (D-ETW)) & ((1<<ETW)-1);
if (rel >= -ETW && rel <= ETW) {
- r = fwdtbl[((rel+ETW)<<ETW)+w];
- if (r<ETW && r<j) {
- if (i+r >= n) return NOTFOUND;
- return i+r;
- }
+
r = fwdtbl[((rel+ETW)<<ETW)+w];
+
if (r<ETW && r<j) {
+
if (i+r >= n) return NOTFOUND;
+
return i+r;
+
}
}
r = min(j,ETW);
}
r = min(j,ETW);
- rel -=
2*popcount(w
)-r;
+ rel -=
(popcount(w) << 1
)-r;
x <<= r;
i += r;
j -= r;
x <<= r;
i += r;
j -= r;
@@
-274,55
+273,55
@@
int degree_SB(bp *b, int i, int t, int rel, int *ans, int ith)
w = (x >> (D-ETW)) & ((1<<ETW)-1);
w2 = 0;
if (j < ETW || il-i < ETW) {
w = (x >> (D-ETW)) & ((1<<ETW)-1);
w2 = 0;
if (j < ETW || il-i < ETW) {
- r = max(ETW-j,ETW-(il-i));
- w2 = (1<<r)-1;
+
r = max(ETW-j,ETW-(il-i));
+
w2 = (1<<r)-1;
}
v = minmaxtbl_v[0][w | w2];
if (d + v < rel) {
}
v = minmaxtbl_v[0][w | w2];
if (d + v < rel) {
- if (ith > 0) {
+
if (ith > 0) {
#if 0
#if 0
- for (r = 0; r < ETW; r++) {
- if (w & 0x80) {
- d++;
- } else {
- d--;
- if (d < rel) break;
- if (d == rel) {
- ith--;
- if (ith == 0) {
- *ans = i + r;
- return FOUND;
- }
- }
- }
- w <<= 1;
- }
- return NOTFOUND;
+
for (r = 0; r < ETW; r++) {
+
if (w & 0x80) {
+
d++;
+
} else {
+
d--;
+
if (d < rel) break;
+
if (d == rel) {
+
ith--;
+
if (ith == 0) {
+
*ans = i + r;
+
return FOUND;
+
}
+
}
+
}
+
w <<= 1;
+
}
+
return NOTFOUND;
#else
#else
- r = childtbl2[rel-d+ETW][ith-1][w];
- if (r >= 0) {
- *ans = i + r;
- return FOUND;
- }
- return NOTFOUND;
+
r = childtbl2[rel-d+ETW][ith-1][w];
+
if (r >= 0) {
+
*ans = i + r;
+
return FOUND;
+
}
+
return NOTFOUND;
#endif
#endif
- }
- r = ETW-1-minmaxtbl_i[0][w | w2];
- w2 = (1<<r)-1;
- deg += degtbl2[((rel-d+ETW)<<ETW) + (w & (~w2))];
- *ans = deg;
- return END;
+
}
+
r = ETW-1-minmaxtbl_i[0][w | w2];
+
w2 = (1<<r)-1;
+
deg += degtbl2[((rel-d+ETW)<<ETW) + (w & (~w2))];
+
*ans = deg;
+
return END;
}
if (d + v == rel) {
}
if (d + v == rel) {
- r = degtbl[w | w2];
- deg += r;
- if (ith > 0) {
- if (ith <= r) {
- *ans = i + childtbl[((ith-1)<<ETW) + (w | w2)];
- return FOUND;
- }
- ith -= r;
- }
+
r = degtbl[w | w2];
+
deg += r;
+
if (ith > 0) {
+
if (ith <= r) {
+
*ans = i + childtbl[((ith-1)<<ETW) + (w | w2)];
+
return FOUND;
+
}
+
ith -= r;
+
}
}
r = min(j,ETW);
}
r = min(j,ETW);
@@
-360,18
+359,18
@@
int degree_MB(bp *b, int i, int t, int td, int *ans,int ith)
if (m < td) {
r = degree_SB(b,i,n,td-d,°tmp,ith);
if (ith > 0) {
if (m < td) {
r = degree_SB(b,i,n,td-d,°tmp,ith);
if (ith > 0) {
- if (r == NOTFOUND) return NOTFOUND;
- *ans = degtmp;
- return FOUND;
+
if (r == NOTFOUND) return NOTFOUND;
+
*ans = degtmp;
+
return FOUND;
} else {
} else {
- *ans = deg + degtmp;
- return END;
+
*ans = deg + degtmp;
+
return END;
}
}
if (m == td) {
if (ith > 0) {
}
}
if (m == td) {
if (ith > 0) {
- if (ith <= b->sd[SBid(i)]) break;
- ith -= b->sd[SBid(i)];
+
if (ith <= b->sd[SBid(i)]) break;
+
ith -= b->sd[SBid(i)];
}
deg += b->sd[SBid(i)];
}
}
deg += b->sd[SBid(i)];
}
@@
-386,8
+385,8
@@
int degree_MB(bp *b, int i, int t, int td, int *ans,int ith)
if (ith > 0) {
if (r == NOTFOUND) return NOTFOUND;
if (r == FOUND) {
if (ith > 0) {
if (r == NOTFOUND) return NOTFOUND;
if (r == FOUND) {
- *ans = degtmp;
- return FOUND;
+
*ans = degtmp;
+
return FOUND;
}
} else {
deg += degtmp;
}
} else {
deg += degtmp;
@@
-398,7
+397,7
@@
int degree_MB(bp *b, int i, int t, int td, int *ans,int ith)
return CONTINUE;
}
return CONTINUE;
}
-static
int
partition_range(int s,int t)
+static
void
partition_range(int s,int t)
{
int i,j,h;
{
int i,j,h;
@@
-407,8
+406,8
@@
static int partition_range(int s,int t)
while (s <= t) {
if (s & h) {
if (s+h-1 <= t) {
while (s <= t) {
if (s & h) {
if (s+h-1 <= t) {
- printf("[%d,%d] ",s,s+h-1);
- s += h;
+
printf("[%d,%d] ",s,s+h-1);
+
s += h;
}
} else {
if (s+h > t) break;
}
} else {
if (s+h > t) break;
@@
-474,7
+473,7
@@
int bp_fast_degree(bp *b,int s, int t, int ith)
} else {
deg += degtmp;
if (d == END) {
} else {
deg += degtmp;
if (d == END) {
- return deg;
+
return deg;
}
}
}
}
}
}
@@
-493,8
+492,8
@@
int bp_fast_degree(bp *b,int s, int t, int ith)
}
if (b->mm[i] == td) {
if (ith > 0) {
}
if (b->mm[i] == td) {
if (ith > 0) {
- if (ith <= b->md[i]) break;
- ith -= b->md[i];
+
if (ith <= b->md[i]) break;
+
ith -= b->md[i];
}
deg += b->md[i];
}
}
deg += b->md[i];
}
@@
-515,23
+514,23
@@
int bp_fast_degree(bp *b,int s, int t, int ith)
while (sm <= tm) {
if (sm & h) {
if (sm+h-1 <= tm) {
while (sm <= tm) {
if (sm & h) {
if (sm+h-1 <= tm) {
- //printf("[%d,%d] ",sm,sm+h-1);
- j = sm / h;
- if (b->mm[j] < td) {
- h >>= 1;
- break;
- }
- if (b->mm[j] == td) {
- if (ith > 0) {
- if (ith <= b->md[j]) {
- h >>= 1;
- break;
- }
- ith -= b->md[j];
- }
- deg += b->md[j];
- }
- sm += h;
+
//printf("[%d,%d] ",sm,sm+h-1);
+
j = sm / h;
+
if (b->mm[j] < td) {
+
h >>= 1;
+
break;
+
}
+
if (b->mm[j] == td) {
+
if (ith > 0) {
+
if (ith <= b->md[j]) {
+
h >>= 1;
+
break;
+
}
+
ith -= b->md[j];
+
}
+
deg += b->md[j];
+
}
+
sm += h;
}
} else {
if (sm+h > tm) break;
}
} else {
if (sm+h > tm) break;
@@
-543,25
+542,25
@@
int bp_fast_degree(bp *b,int s, int t, int ith)
//printf("[%d,%d] ",sm,sm+h-1);
j = sm / h;
if (ith > 0) {
//printf("[%d,%d] ",sm,sm+h-1);
j = sm / h;
if (ith > 0) {
- if (b->mm[j] >= td) {
- if (b->mm[j] == td) {
- if (ith > b->md[j]) {
- ith -= b->md[j];
- sm += h;
- } else {
- deg += b->md[j];
- }
- } else {
- sm += h;
- }
- }
+
if (b->mm[j] >= td) {
+
if (b->mm[j] == td) {
+
if (ith > b->md[j]) {
+
ith -= b->md[j];
+
sm += h;
+
} else {
+
deg += b->md[j];
+
}
+
} else {
+
sm += h;
+
}
+
}
} else {
} else {
- if (b->mm[j] >= td) {
- if (b->mm[j] == td) {
- deg += b->md[j];
- }
- sm += h;
- }
+
if (b->mm[j] >= td) {
+
if (b->mm[j] == td) {
+
deg += b->md[j];
+
}
+
sm += h;
+
}
}
}
h >>= 1;
}
}
h >>= 1;
@@
-605,11
+604,11
@@
int search_SB_l(bp *b, int i, int rel)
while (j>0) {
w = x & ((1<<ETW)-1);
if (rel >= -ETW && rel <= ETW) {
while (j>0) {
w = x & ((1<<ETW)-1);
if (rel >= -ETW && rel <= ETW) {
- r = bwdtbl[((rel+ETW)<<ETW)+w];
- if (r<ETW && r<j) {
- if (i-r < 0) return NOTFOUND;
- return i-r-1;
- }
+
r = bwdtbl[((rel+ETW)<<ETW)+w];
+
if (r<ETW && r<j) {
+
if (i-r < 0) return NOTFOUND;
+
return i-r-1;
+
}
}
r = min(j,ETW);
rel += 2*popcount(w)-r;
}
r = min(j,ETW);
rel += 2*popcount(w)-r;
@@
-742,22
+741,22
@@
int rmq_SB(bp *b, int s, int t, int opt, int *dm)
w = (x >> (D-ETW)) & ((1<<ETW)-1);
w2 = 0;
if (j < ETW || t-i < ETW-1) {
w = (x >> (D-ETW)) & ((1<<ETW)-1);
w2 = 0;
if (j < ETW || t-i < ETW-1) {
- r = max(ETW-j,ETW-1-(t-i));
- w2 = (1<<r)-1;
+
r = max(ETW-j,ETW-1-(t-i));
+
w2 = (1<<r)-1;
}
if (op & OPT_MAX) {
}
if (op & OPT_MAX) {
- v = minmaxtbl_v[op][w & (~w2)];
- if (d + v + lr > ds) {
- ds = d + v;
- is = i + minmaxtbl_i[op][w & (~w2)];
- }
+
v = minmaxtbl_v[op][w & (~w2)];
+
if (d + v + lr > ds) {
+
ds = d + v;
+
is = i + minmaxtbl_i[op][w & (~w2)];
+
}
} else {
} else {
- v = minmaxtbl_v[op][w | w2];
- if (d + v < ds +lr) {
- ds = d + v;
- is = i + minmaxtbl_i[op][w | w2];
- }
+
v = minmaxtbl_v[op][w | w2];
+
if (d + v < ds +lr) {
+
ds = d + v;
+
is = i + minmaxtbl_i[op][w | w2];
+
}
}
r = min(j,ETW);
}
r = min(j,ETW);
@@
-772,16
+771,16
@@
int rmq_SB(bp *b, int s, int t, int opt, int *dm)
if (bp_getbit(b->B,i)==OP) {
d++;
if (op & OPT_MAX) {
if (bp_getbit(b->B,i)==OP) {
d++;
if (op & OPT_MAX) {
- if (d + lr > ds) {
- ds = d; is = i;
- }
+
if (d + lr > ds) {
+
ds = d; is = i;
+
}
}
} else {
d--;
if (!(op & OPT_MAX)) {
}
} else {
d--;
if (!(op & OPT_MAX)) {
- if (d < ds + lr) {
- ds = d; is = i;
- }
+
if (d < ds + lr) {
+
ds = d; is = i;
+
}
}
}
i++;
}
}
i++;
@@
-809,12
+808,12
@@
int rmq_MB(bp *b, int s, int t, int opt, int *dm)
if (opt & OPT_MAX) {
m = d + b->sM[i] - 1;
if (m + lr > md) {
if (opt & OPT_MAX) {
m = d + b->sM[i] - 1;
if (m + lr > md) {
- md = m; mi = i;
+
md = m; mi = i;
}
} else {
m = d + b->sm[i] - SB;
if (m < md + lr) {
}
} else {
m = d + b->sm[i] - SB;
if (m < md + lr) {
- md = m; mi = i;
+
md = m; mi = i;
}
}
}
}
}
}
@@
-896,11
+895,11
@@
int bp_rmq(bp *b, int s, int t, int opt)
for (i=sm; i<=tm; i++) {
if (opt & OPT_MAX) {
if (b->mM[i] + lr > ds) {
for (i=sm; i<=tm; i++) {
if (opt & OPT_MAX) {
if (b->mM[i] + lr > ds) {
- ds = b->mM[i]; is = i - m_ofs; ys = 2;
+
ds = b->mM[i]; is = i - m_ofs; ys = 2;
}
} else {
if (b->mm[i] < ds + lr) {
}
} else {
if (b->mm[i] < ds + lr) {
- ds = b->mm[i]; is = i - m_ofs; ys = 2;
+
ds = b->mm[i]; is = i - m_ofs; ys = 2;
}
}
}
}
}
}
@@
-915,63
+914,63
@@
int bp_rmq(bp *b, int s, int t, int opt)
if (opt & OPT_MAX) {
if (b->mM[sm] + lr > ds) {
if (opt & OPT_MAX) {
if (b->mM[sm] + lr > ds) {
- ds = b->mM[sm]; is = sm; ys = 2;
+
ds = b->mM[sm]; is = sm; ys = 2;
}
for (i=0; i<=h-2; i++) {
}
for (i=0; i<=h-2; i++) {
- j = sm>>i;
- if ((j&1) == 0) {
- if (b->mM[j+1] + lr > ds) {
- ds = b->mM[j+1]; is = j+1; ys = 2;
- }
- }
+
j = sm>>i;
+
if ((j&1) == 0) {
+
if (b->mM[j+1] + lr > ds) {
+
ds = b->mM[j+1]; is = j+1; ys = 2;
+
}
+
}
}
for (i=h-2; i>=0; i--) {
}
for (i=h-2; i>=0; i--) {
- j = tm>>i;
- if ((j&1)==1) {
- if (b->mM[j-1] + lr > ds) {
- ds = b->mM[j-1]; is = j-1; ys = 2;
- }
- }
+
j = tm>>i;
+
if ((j&1)==1) {
+
if (b->mM[j-1] + lr > ds) {
+
ds = b->mM[j-1]; is = j-1; ys = 2;
+
}
+
}
}
if (b->mM[tm] + lr > ds) {
}
if (b->mM[tm] + lr > ds) {
- ds = b->mM[tm]; is = tm; ys = 2;
+
ds = b->mM[tm]; is = tm; ys = 2;
}
if (ys == 2) {
}
if (ys == 2) {
- while (is < m_ofs) {
- is <<= 1;
- if (b->mM[is+1] + lr > b->mM[is]) is++;
- }
- is -= m_ofs;
+
while (is < m_ofs) {
+
is <<= 1;
+
if (b->mM[is+1] + lr > b->mM[is]) is++;
+
}
+
is -= m_ofs;
}
} else { // MIN
if (b->mm[sm] < ds + lr) {
}
} else { // MIN
if (b->mm[sm] < ds + lr) {
- ds = b->mm[sm]; is = sm; ys = 2;
+
ds = b->mm[sm]; is = sm; ys = 2;
}
for (i=0; i<=h-2; i++) {
}
for (i=0; i<=h-2; i++) {
- j = sm>>i;
- if ((j&1) == 0) {
- if (b->mm[j+1] < ds + lr) {
- ds = b->mm[j+1]; is = j+1; ys = 2;
- }
- }
+
j = sm>>i;
+
if ((j&1) == 0) {
+
if (b->mm[j+1] < ds + lr) {
+
ds = b->mm[j+1]; is = j+1; ys = 2;
+
}
+
}
}
for (i=h-2; i>=0; i--) {
}
for (i=h-2; i>=0; i--) {
- j = tm>>i;
- if ((j&1)==1) {
- if (b->mm[j-1] < ds + lr) {
- ds = b->mm[j-1]; is = j-1; ys = 2;
- }
- }
+
j = tm>>i;
+
if ((j&1)==1) {
+
if (b->mm[j-1] < ds + lr) {
+
ds = b->mm[j-1]; is = j-1; ys = 2;
+
}
+
}
}
if (b->mm[tm] < ds + lr) {
}
if (b->mm[tm] < ds + lr) {
- ds = b->mm[tm]; is = tm; ys = 2;
+
ds = b->mm[tm]; is = tm; ys = 2;
}
if (ys == 2) {
}
if (ys == 2) {
- while (is < m_ofs) {
- is <<= 1;
- if (b->mm[is+1] < b->mm[is] + lr) is++;
- }
- is -= m_ofs;
+
while (is < m_ofs) {
+
is <<= 1;
+
if (b->mm[is+1] < b->mm[is] + lr) is++;
+
}
+
is -= m_ofs;
}
}
}
}
}
}