Adds utils.h

[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 "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
@@ -15,19 +25,6 @@
 #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;
@@ -135,7 +132,7 @@ int search_SB_r(bp *b, int i, int rel)
        }
       }
       r = min(j,ETW);
-      rel -= 2*popCount[w]-r;
+      rel -= 2*popcount(w)-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;
-#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;
 }
 
 
@@ -351,7 +331,7 @@ int degree_SB(bp *b, int i, int t, int rel, int *ans, int ith)
       }
 
       r = min(j,ETW);
-      d += 2*popCount[w]-r;
+      d += 2*popcount(w)-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);
-      rel += 2*popCount[w]-r;
+      rel += 2*popcount(w)-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);
-      d += 2*popCount[w]-r;
+      d += 2*popcount(w)-r;
       x <<= r;
       i += r;
       j -= r;