projects / SXSI / libbp.git / blobdiff
? search:
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 7b35966..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 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)
 {
@@ -109,7 +108,7 @@ int search_SB_r(bp *b, int i, int rel)
   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++;
@@ -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) {
-       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);
-      rel -= 2*popcount(w)-r;
+      rel -= (popcount(w) << 1)-r;
       x <<= r;
       i += r;
       j -= r;
@@ -144,7 +143,7 @@ int search_MB_r(bp *b, int i, int td)
   B = b->B;
   n = b->n;
 
-  il = min((MBid(i) + 1) << logMB,n);
+  il = min((MBid(i) + 1) << logMB, n);
   for (  ;  i < il;  i+=SB) {
 #if (SB % RRR != 0)
     d = bp_depth(b,i-1);
@@ -172,6 +171,7 @@ int bp_fwd_excess(bp *b,int s, int rel)
   int m,M;
   int m_ofs;
   pb *B;
+
   n = b->n;  B = b->B;
 
   i = s+1;
@@ -273,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) {
-       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) {
-       if (ith > 0) {
+        if (ith > 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
-         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
-       }
-       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) {
-       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);
@@ -359,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,&degtmp,ith);
       if (ith > 0) {
-       if (r == NOTFOUND) return NOTFOUND;
-       *ans = degtmp;
-       return FOUND;
+        if (r == NOTFOUND) return NOTFOUND;
+        *ans = degtmp;
+        return FOUND;
       } else {
-       *ans = deg + degtmp;
-       return END;
+        *ans = deg + degtmp;
+        return END;
       }
     }
     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)];
     }
@@ -385,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) {
-       *ans = degtmp;
-       return FOUND;
+        *ans = degtmp;
+        return FOUND;
       }
     } else {
       deg += degtmp;
@@ -397,7 +397,7 @@ int degree_MB(bp *b, int i, int t, int td, int *ans,int ith)
   return CONTINUE;
 }
 
-static int partition_range(int s,int t)
+static void partition_range(int s,int t)
 {
   int i,j,h;
 
@@ -406,8 +406,8 @@ static int partition_range(int s,int 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;
@@ -442,7 +442,7 @@ int bp_fast_degree(bp *b,int s, int t, int ith)
   int deg,degtmp;
   int sm,tm,ss,h;
 
-  n = t;  
+  n = t;
   B = b->B;
 
   deg = 0;
@@ -473,7 +473,7 @@ int bp_fast_degree(bp *b,int s, int t, int ith)
     } else {
       deg += degtmp;
       if (d == END) {
-       return deg;
+        return deg;
       }
     }
   }
@@ -492,8 +492,8 @@ int bp_fast_degree(bp *b,int s, int t, int ith)
     }
     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];
     }
@@ -514,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) {
-       //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;
@@ -542,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) {
-       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 {
-       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;
@@ -582,7 +582,7 @@ int bp_fast_degree(bp *b,int s, int t, int ith)
   deg += degtmp;
   if (d == END) return deg;
   return deg;
-  
+
   // unexpected (bug)
   printf("degree: ???\n");
   return -99;
@@ -604,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) {
-       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;
@@ -741,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) {
-       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) {
-       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 {
-       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);
@@ -771,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 (d + lr > ds) {
-         ds = d;  is = i;
-       }
+        if (d + lr > ds) {
+          ds = d;  is = i;
+        }
       }
     } else {
       d--;
       if (!(op & OPT_MAX)) {
-       if (d < ds + lr) {
-         ds = d;  is = i;
-       }
+        if (d < ds + lr) {
+          ds = d;  is = i;
+        }
       }
     }
     i++;
@@ -808,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) {
-       md = m;  mi = i;
+        md = m;  mi = i;
       }
     } else {
       m = d + b->sm[i] - SB;
       if (m < md + lr) {
-       md = m;  mi = i;
+        md = m;  mi = i;
       }
     }
   }
@@ -895,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) {
-       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) {
-       ds = b->mm[i];  is = i - m_ofs;  ys = 2;
+        ds = b->mm[i];  is = i - m_ofs;  ys = 2;
       }
     }
   }
@@ -914,63 +914,63 @@ int bp_rmq(bp *b, int s, int t, int opt)
 
     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++) {
-       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--) {
-       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) {
-       ds = b->mM[tm];  is = tm;  ys = 2;
+        ds = b->mM[tm];  is = tm;  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) {
-       ds = b->mm[sm];  is = sm;  ys = 2;
+        ds = b->mm[sm];  is = sm;  ys = 2;
       }
       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--) {
-       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) {
-       ds = b->mm[tm];  is = tm;  ys = 2;
+        ds = b->mm[tm];  is = tm;  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;
       }
     }
   }
Succinct balanced parenthesis representation of trees