Various fixes and cosmetic changes.

diff --git a/Makefile b/Makefile
index 3effd67..59e83a1 100644 (file)
--- a/Makefile
+++ b/Makefile
@@ -1,7 +1,7 @@
 POPCOUNT=$(shell grep -q popcnt /proc/cpuinfo && echo 1)
 
 ifeq ($(POPCOUNT), 1)
-       POPCOUNT_FLAG=-DHAS_NATIVE_POPCOUNT
+       POPCOUNT_FLAG=-DHAS_NATIVE_POPCOUNT -mpopcnt -mtune=corei7 -march=corei7
 else
        #POPCOUNT_FLAG=-DHAS_POPCOUNT_TABLE
        POPCOUNT_FLAG=
@@ -16,14 +16,20 @@ endif
 ifeq ($(DEBUG), true)
        OPT_FLAGS=-O0 -g $(POPCOUNT_FLAG) -static
 else
-       OPT_FLAGS=-O4 $(POPCOUNT_FLAG) -static -flto
+       OPT_FLAGS=-O3 $(POPCOUNT_FLAG) -static -flto
 endif
 
 
+ifeq ($(PROFILE), true)
+       PROF_FLAGS=-pg -g
+else
+       PROF_FLAGS=
+endif
+
 
 INC_FLAGS=-I.
-CFLAGS= $(INC_FLAGS) $(OPT_FLAGS)
-CXXFLAGS= $(INC_FLAGS) $(OPT_FLAGS)
+CFLAGS= $(INC_FLAGS) $(OPT_FLAGS) $(PROF_FLAGS)
+CXXFLAGS= $(INC_FLAGS) $(OPT_FLAGS) $(PROF_FLAGS)
 CC=g++
 
 

diff --git a/bp-core.c b/bp-core.c
index 70a0959..67cc780 100644 (file)
--- a/bp-core.c
+++ b/bp-core.c
@@ -119,11 +119,11 @@ 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;
@@ -274,55 +274,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);
@@ -360,18 +360,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)];
     }
@@ -386,8 +386,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;
@@ -407,8 +407,8 @@ static void 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;
@@ -474,7 +474,7 @@ int bp_fast_degree(bp *b,int s, int t, int ith)
     } else {
       deg += degtmp;
       if (d == END) {
-       return deg;
+        return deg;
       }
     }
   }
@@ -493,8 +493,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];
     }
@@ -515,23 +515,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;
@@ -543,25 +543,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;
@@ -605,11 +605,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;
@@ -742,22 +742,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);
@@ -772,16 +772,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++;
@@ -809,12 +809,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;
       }
     }
   }
@@ -896,11 +896,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;
       }
     }
   }
@@ -915,63 +915,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;
       }
     }
   }

diff --git a/bp-darray.c b/bp-darray.c
index 800ebb1..866ce6f 100644 (file)
--- a/bp-darray.c
+++ b/bp-darray.c
@@ -58,11 +58,30 @@ static int getpattern(pb *B, int i, int k, pb pat)
 \r
 static int selecttbl[8*256];\r
 static int selecttbl_init = 0;\r
+static void prbin(unsigned int x)\r
+{\r
+  int i;\r
+  //  for(i = 31; i >= 0; i--){\r
+  for (i = 0 ; i < 32; i ++) {\r
+    fprintf(stderr,"%.1u", (x >> i)&1);\r
+    if (i % 4 == 3)\r
+      fprintf(stderr, " ");\r
+  }\r
+\r
+}\r
+int clz(unsigned int x)\r
+{\r
+  if (x == 0)\r
+    return -1;\r
+  else\r
+    __builtin_clz(x);\r
+}\r
 \r
 static void make_selecttbl(void)\r
 {\r
   int i,x,r;\r
   pb buf[1];\r
+  unsigned int mask;\r
   if (selecttbl_init) return;\r
 \r
   selecttbl_init = 1;\r
@@ -73,11 +92,21 @@ static void make_selecttbl(void)
     r = 0;\r
     for (i=0; i<8; i++) {\r
       if (bp_getbit(buf,i)) {\r
+       //      fprintf(stderr, "Init: setting %i to %i (r= %i, x = %i)\n", (r<<8)+x, i, r, x);\r
        selecttbl[(r<<8)+x] = i;\r
        r++;\r
       }\r
     }\r
   }\r
+  /*\r
+  fprintf(stderr, "Select table:\n");\r
+  for (i = 0; i < 8 * 256; i++){\r
+    mask = i / 256 + 1;\r
+    x = __builtin_clz((i + (i << 8)));\r
+    prbin(i);\r
+    fprintf(stderr, " (%.4i): %08i, %08i\n", i, selecttbl[i], x);\r
+  };\r
+  */\r
 }\r
 \r
 \r

diff --git a/bp-darray.h b/bp-darray.h
index 4224dba..75808f1 100644 (file)
--- a/bp-darray.h
+++ b/bp-darray.h
@@ -37,6 +37,7 @@ darray * bp_darray_construct(int n, pb *buf,int opt);
 void bp_darray_free(darray *da);
 
 int bp_darray_select(darray *da, int i,int f);
+
 static int bp_darray_rank(darray *da, int i)
 {
   int r,j,i_rr, i_rrr;

diff --git a/bp-utils.h b/bp-utils.h
index 21aa7d3..56f2d73 100644 (file)
--- a/bp-utils.h
+++ b/bp-utils.h
@@ -18,20 +18,21 @@ extern "C" {
 #define RRR (1<<logRRR)
 
 
-
-
-
 #include <stdlib.h>
 
-
+#ifdef __GNUC__
+#define UNUSED __attribute__((unused))
+#else
+#define UNUSED
+#endif
 
 #ifdef HAS_NATIVE_POPCOUNT
-static inline unsigned int popcount(unsigned int n){
+static inline UNUSED unsigned int popcount(unsigned int n){
   asm ("popcnt %1, %0" : "=r" (n) : "0" (n));
   return n;
 }
 
-static inline unsigned int popcount8(unsigned int n) {
+static inline UNUSED unsigned int popcount8(unsigned int n) {
   return popcount(n & 0xff);
 }
 
@@ -40,12 +41,12 @@ static inline unsigned int popcount8(unsigned int n) {
 
 extern unsigned char popCount[256];
 
-static unsigned int popcount8(unsigned int x)
+static UNUSED unsigned int popcount8(unsigned int x)
 {
   return (unsigned int) popCount[x & 0xff];
 }
 
-static unsigned int popcount(unsigned int x)
+static UNUSED unsigned int popcount(unsigned int x)
 {
   return popcount8(x) +
     popcount8((x >> 8)) +
@@ -55,7 +56,7 @@ static unsigned int popcount(unsigned int x)
 
 
 #else
-static unsigned int popcount8(unsigned int x)
+static UNUSED unsigned int popcount8(unsigned int x)
 {
   unsigned int r;
   r = x;
@@ -65,7 +66,7 @@ static unsigned int popcount8(unsigned int x)
   return r;
 }
 
-static inline unsigned int popcount(unsigned int x)
+static inline UNUSED unsigned int popcount(unsigned int x)
 {
   unsigned int m1 = 0x55555555;
   unsigned int m2 = 0xc30c30c3;

diff --git a/bp.c b/bp.c
index f1aef19..62f4613 100644 (file)
--- a/bp.c
+++ b/bp.c
@@ -1,4 +1,5 @@
 #include "bp.h"
+#include <unistd.h>
 
 //#define CHECK
 #define RANDOM
@@ -159,7 +160,7 @@ static void make_matchtbl(void)
       if (bp_getbit(buf,i)==OP) {
        r++;
        if (r > M) {
-         M = r;  
+         M = r;
          //maxtbl_li[x] = i;  maxtbl_lv[x] = r;
          minmaxtbl_i[OPT_MAX | OPT_LEFT][x] = i;
          minmaxtbl_v[OPT_MAX | OPT_LEFT][x] = r;
@@ -192,7 +193,7 @@ static void make_matchtbl(void)
       if (bp_getbit(buf,i)==OP) {
        r++;
        if (r >= M) {
-         M = r;  
+         M = r;
          //maxtbl_ri[x] = i;  maxtbl_rv[x] = r;
          minmaxtbl_i[OPT_MAX | OPT_RIGHT][x] = i;
          minmaxtbl_v[OPT_MAX | OPT_RIGHT][x] = r;
@@ -457,6 +458,63 @@ void saveTree(bp *b, FILE *fp) {
    }
 }
 
+static ssize_t uwrite(int fd, const void* buff, size_t count)
+{
+  ssize_t written;
+  char *p = (char *) buff;
+  do {
+    written = write(fd, p, count);
+    p += written;
+    count -= written;
+  } while (written > 0);
+
+  return (written == -1);
+}
+
+static ssize_t uread(int fd, const void* buff, size_t count)
+{
+  ssize_t loaded;
+  char *p = (char *) buff;
+  do {
+    loaded = read(fd, p, count);
+    p += loaded;
+    count -= loaded;
+  } while (loaded > 0);
+
+  return (loaded == -1);
+}
+
+int bp_save(bp *b, int fd)
+{
+  if (uwrite(fd, &b->n, sizeof(int))) return 1;
+  if (uwrite(fd, b->B, sizeof(pb) * (b->n+D-1)/D)) return 1;
+  if (uwrite(fd, &b->opt, sizeof(int))) return 1;
+  return 0;
+}
+
+bp* bp_load(int fd)
+{
+  pb *B;
+  int n, opt;
+  if (uread(fd, &n, sizeof(int))) return NULL;
+  bp_xmalloc(B, (n+D-1)/D);
+
+  if (B == NULL) return NULL;
+
+  if (uread(fd, B, sizeof(pb) * (n+D-1)/D)) {
+    free(B);
+    return NULL;
+  };
+
+  if (uread(fd, &opt, sizeof(int))){
+    free(B);
+    return NULL;
+  };
+
+  return bp_construct(n, B, opt);
+}
+
+
 // loadTree: load parentheses data structure from file
 // By Diego Arroyuelo
 bp * loadTree(FILE *fp) {
@@ -481,7 +539,7 @@ bp * loadTree(FILE *fp) {
       exit(1);
    }
 
-   return bp_construct(n, B, opt); 
+   return bp_construct(n, B, opt);
 
 }
 
@@ -859,7 +917,7 @@ int bp_child(bp *b, int s, int d)
   } else {
     return bp_naive_child(b,s,d);
   }
-    
+
 }
 
 

diff --git a/bp.h b/bp.h
index b982430..6177b83 100644 (file)
--- a/bp.h
+++ b/bp.h
@@ -114,7 +114,9 @@ static inline int bp_find_open(bp *b,int s)
 ///////////////////////////////////////////
 static inline int bp_parent(bp *b, int s)
 {
-  int r = bp_bwd_excess(b,s,-2);
+  int r;
+  if (bp_getbit(b->B, s - 1) == OP) return s - 1;
+  r = bp_bwd_excess(b,s,-2);
   return (r >= -1) ? r+1 : -1;
 }
 
@@ -228,7 +230,7 @@ static inline int bp_first_child(bp *b, int s)
 static inline int bp_next_sibling(bp *b, int s)
 {
   int t;
-  t = bp_find_close(b,s) + 1;
+  t = bp_find_close(b, s) + 1;
   return (bp_inspect(b, t) == CP) ? -1 : t;
 
 }
@@ -288,6 +290,13 @@ int bp_child(bp *b, int s, int d);
 // new functions for persistence purposes, added by Diego Arroyuelo
 void saveTree(bp *b, FILE *fp);
 bp * loadTree(FILE *fp);
+
+//0: success 1: failure (errno)
+int bp_save(bp *b, int fd);
+
+//non-null: sucess, null: failure (errno)
+
+bp * bp_load(int fd);
 void bp_delete(bp *b);