projects
/
SXSI
/
XMLTree.git
/ blobdiff
commit
grep
author
committer
pickaxe
?
search:
re
summary
|
shortlog
|
log
|
commit
|
commitdiff
|
tree
raw
|
inline
| side by side
Create branch library-split
[SXSI/XMLTree.git]
/
bpcore.c
diff --git
a/bpcore.c
b/bpcore.c
index
6bc12bd
..
5c8ec4a
100644
(file)
--- a/
bpcore.c
+++ b/
bpcore.c
@@
-1,6
+1,16
@@
#include <stdio.h>
#include <stdlib.h>
#include "bp.h"
#include <stdio.h>
#include <stdlib.h>
#include "bp.h"
+#include "utils.h"
+
+
+#ifndef min
+#define min(x,y) ((x)<(y)?(x):(y))
+#endif
+
+#ifndef max
+#define max(x,y) ((x)>(y)?(x):(y))
+#endif
#define NOTFOUND -2
#define CONTINUE -3
#define NOTFOUND -2
#define CONTINUE -3
@@
-15,19
+25,6
@@
#define MBfirst(i) ((i) & (~(MB-1)))
#define MBlast(i) ((i) | (MB-1))
#define MBfirst(i) ((i) & (~(MB-1)))
#define MBlast(i) ((i) | (MB-1))
-
-int blog(int x)
-{
-int l;
- l = 0;
- while (x>0) {
- x>>=1;
- l++;
- }
- return l;
-}
-
-
pb getpat_preorder(pb *b)
{
return *b;
pb getpat_preorder(pb *b)
{
return *b;
@@
-135,7
+132,7
@@
int search_SB_r(bp *b, int i, int rel)
}
}
r = min(j,ETW);
}
}
r = min(j,ETW);
- rel -= 2*pop
Count[w]
-r;
+ rel -= 2*pop
count(w)
-r;
x <<= r;
i += r;
j -= r;
x <<= r;
i += r;
j -= r;
@@
-184,59
+181,42
@@
int fwd_excess(bp *b,int s, int rel)
n = b->n; B = b->B;
i = s+1;
n = b->n; B = b->B;
i = s+1;
-#if 1
+
d = search_SB_r(b,i,rel);
if (d >= NOTFOUND) return d;
d = search_SB_r(b,i,rel);
if (d >= NOTFOUND) return d;
- i = min((SBid(i) + 1) << logSB,n);
+ i = min((SBid(i) + 1) << logSB,
n);
td = depth(b,s) + rel;
d = search_MB_r(b,i,td);
if (d >= NOTFOUND) return d;
td = depth(b,s) + rel;
d = search_MB_r(b,i,td);
if (d >= NOTFOUND) return d;
-#else
- if (i != SBfirst(i)) {
- d = search_SB_r(b,i,rel);
- if (d >= NOTFOUND) return d;
- }
-
- td = depth(b,s) + rel;
-
- i = SBid(i+SB-1) << logSB;
-
- if (i != MBfirst(i)) {
- d = search_MB_r(b,i,td);
- if (d >= NOTFOUND) return d;
- }
-#endif
m_ofs = b->m_ofs;
m_ofs = b->m_ofs;
+
i = MBid(s) + m_ofs;
i = MBid(s) + m_ofs;
+
while (i > 0) {
if ((i&1) == 0) {
i++;
m = b->mm[i];
M = b->mM[i];
while (i > 0) {
if ((i&1) == 0) {
i++;
m = b->mm[i];
M = b->mM[i];
- if (m <= td && td <= M) break;
- }
- i >>= 1;
- }
- if (i == 0) return NOTFOUND;
- while (i < m_ofs) {
- i <<= 1;
- m = b->mm[i];
- M = b->mM[i];
- if (!(m <= td && td <= M)) i++;
- }
- i -= m_ofs;
- i <<= logMB;
+ if (m <= td && td <= M) {
+ while (i < m_ofs) {
+ i <<= 1;
+ m = b->mm[i];
+ M = b->mM[i];
+ if (!(m <= td && td <= M)) i++;
+ }
+ i -= m_ofs;
+ i <<= logMB;
- d = search_MB_r(b,i,td);
- if (d >= NOTFOUND) return d;
-
- // unexpected (bug)
- printf("fwd_excess: ???\n");
- return -99;
+ return search_MB_r(b,i,td);
+ };
+ }
+ i >>= 1;
+ }
+ return NOTFOUND;
}
}
@@
-351,7
+331,7
@@
int degree_SB(bp *b, int i, int t, int rel, int *ans, int ith)
}
r = min(j,ETW);
}
r = min(j,ETW);
- d += 2*pop
Count[w]
-r;
+ d += 2*pop
count(w)
-r;
x <<= r;
i += r;
j -= r;
x <<= r;
i += r;
j -= r;
@@
-637,7
+617,7
@@
int search_SB_l(bp *b, int i, int rel)
}
}
r = min(j,ETW);
}
}
r = min(j,ETW);
- rel += 2*pop
Count[w]
-r;
+ rel += 2*pop
count(w)
-r;
x >>= r;
i -= r;
j -= r;
x >>= r;
i -= r;
j -= r;
@@
-786,7
+766,7
@@
int rmq_SB(bp *b, int s, int t, int opt, int *dm)
}
r = min(j,ETW);
}
r = min(j,ETW);
- d += 2*pop
Count[w]
-r;
+ d += 2*pop
count(w)
-r;
x <<= r;
i += r;
j -= r;
x <<= r;
i += r;
j -= r;