#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 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;
}
}
r = min(j,ETW);
- rel -= 2*popCount[w]-r;
+ rel -= 2*popcount(w)-r;
x <<= r;
i += r;
j -= r;
n = b->n; B = b->B;
i = s+1;
-#if 1
+
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;
-#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;
+
i = MBid(s) + m_ofs;
+
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;
}
}
r = min(j,ETW);
- d += 2*popCount[w]-r;
+ d += 2*popcount(w)-r;
x <<= r;
i += r;
j -= r;
}
}
r = min(j,ETW);
- rel += 2*popCount[w]-r;
+ rel += 2*popcount(w)-r;
x >>= r;
i -= r;
j -= r;
}
r = min(j,ETW);
- d += 2*popCount[w]-r;
+ d += 2*popcount(w)-r;
x <<= r;
i += r;
j -= r;