X-Git-Url: http://git.nguyen.vg/gitweb/?p=SXSI%2Flibbp.git;a=blobdiff_plain;f=bp.h;h=e0eb4c9ad241c1a90055ea2a4af7674fefd19078;hp=00aecf73f07dbe2c47cfca64e96cc148e0cde819;hb=HEAD;hpb=45ff7a2260f890f6ef6a7b56f654ffa1a057a7e7

diff --git a/bp.h b/bp.h
index 00aecf7..e0eb4c9 100644
--- a/bp.h
+++ b/bp.h
@@ -6,13 +6,11 @@
 extern "C" {
 #endif
 
-
 #include <stdio.h>
 #include <stdlib.h>
 #include "bp-darray.h"
 #include "bp-utils.h"
 
-
 #define OP 1
 #define CP 0
 
@@ -21,15 +19,15 @@ extern "C" {
 #define OPT_LEFT 0
 #define OPT_RIGHT 2
 
-#define OPT_LEAF (1<<0)
-#define OPT_INORDER (1<<1)
-#define OPT_DEGREE (1<<2)
-#define OPT_FAST_PREORDER_SELECT (1<<3)
-#define OPT_FAST_LEAF_SELECT (1<<4)
-#define OPT_FAST_INORDER_SELECT (1<<5)
-#define OPT_FAST_POSTORDER_SELECT (1<<6)
-#define OPT_DFUDS_LEAF (1<<7)
-#define OPT_FAST_DFUDS_LEAF_SELECT (1<<8)
+#define OPT_LEAF (1 << 0)
+#define OPT_INORDER (1 << 1)
+#define OPT_DEGREE (1 << 2)
+#define OPT_FAST_PREORDER_SELECT (1 << 3)
+#define OPT_FAST_LEAF_SELECT (1 << 4)
+#define OPT_FAST_INORDER_SELECT (1 << 5)
+#define OPT_FAST_POSTORDER_SELECT (1 << 6)
+#define OPT_DFUDS_LEAF (1 << 7)
+#define OPT_FAST_DFUDS_LEAF_SELECT (1 << 8)
 
 //#define logSB 9
 #define logSB 7
@@ -88,6 +86,14 @@ static inline int bp_root_node(bp *b)
   return 0;
 }
 
+///////////////////////////////////////////
+//  inspect(bp *b, int s)
+//    returns OP (==1) or CP (==0) at s-th bit (0 <= s < n)
+///////////////////////////////////////////
+static inline int bp_inspect(bp *b, int s)
+{
+  return bp_getbit(b->B, s);
+}
 
 ///////////////////////////////////////////
 //  find_close(bp *b,int s)
@@ -95,7 +101,11 @@ static inline int bp_root_node(bp *b)
 ///////////////////////////////////////////
 static inline int bp_find_close(bp *b,int s)
 {
-  return bp_fwd_excess(b, s, -1);
+  int s1 = s + 1;
+  if (bp_inspect(b, s1) == CP)
+    return s1;
+  else
+    return bp_fwd_excess(b, s, -1);
 }
 
 ///////////////////////////////////////////
@@ -116,7 +126,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;
 }
 
@@ -187,15 +199,6 @@ static inline int bp_preorder_select(bp *b,int s)
 
 int bp_postorder_rank(bp *b,int s);
 
-///////////////////////////////////////////
-//  inspect(bp *b, int s)
-//    returns OP (==1) or CP (==0) at s-th bit (0 <= s < n)
-///////////////////////////////////////////
-static inline int bp_inspect(bp *b, int s)
-{
-  return bp_getbit(b->B,s);
-}
-
 static inline int bp_isleaf(bp *b, int s)
 {
   return (bp_inspect(b, s+1) == CP);
@@ -218,7 +221,8 @@ static inline int bp_subtree_size(bp *b, int s)
 
 static inline int bp_first_child(bp *b, int s)
 {
-  return (bp_inspect(b, s+1) == CP) ? -1 : s+1;
+  int s1 = s + 1;
+  return bp_inspect(b, s1) ? s1 : -1;
 }
 
 
@@ -230,8 +234,8 @@ 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;
-  return (bp_inspect(b, t) == CP) ? -1 : t;
+  t = bp_find_close(b, s) + 1;
+  return bp_inspect(b, t) ? t : -1;
 
 }
 
@@ -290,6 +294,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);
 
 
@@ -308,8 +319,6 @@ static inline int blog(int x)
 
 
 extern int *matchtbl,*parenttbl;
-void make_naivetbl(pb *B,int n);
-
 
 extern int fwdtbl[(2*ETW+1)*(1<<ETW)];
 extern int bwdtbl[(2*ETW+1)*(1<<ETW)];