Rewrite printing function to make it faster. Now also handles

[SXSI/XMLTree.git] / bp.c

diff --git a/bp.c b/bp.c
index 9058ec8..1745621 100644 (file)
--- a/bp.c
+++ b/bp.c
@@ -1,10 +1,18 @@
 #include "bp.h"\r
+#include <algorithm>\r
+using std::min;\r
+using std::max;\r
 \r
 //#define CHECK\r
 #define RANDOM\r
 \r
 int msize=0;\r
-#define mymalloc(p,n,f) {p =(__typeof__(p)) malloc((n)*sizeof(*p)); msize += (f)*(n)*sizeof(*p); /* if (f) printf("malloc %d bytes at line %d total %d\n",(n)*sizeof(*p),__LINE__,msize);  */ if ((p)==NULL) {printf("not enough memory (%d bytes) in line %d\n",msize,__LINE__); exit(1);};}\r
+#define mymalloc(p,n,f) {                              \\r
+  p = (__typeof__(p)) malloc((n)*sizeof(*p));          \\r
+if ((p)==NULL) {printf("not enough memory (%d bytes) in line %d\n",msize,__LINE__); \\r
+  exit(1);};                                                           \\r
+msize += (f)*(n)*sizeof(*p);                                           \\r
+;}\r
 \r
 int postorder_select_bsearch(bp *b,int s);\r
 \r
@@ -88,14 +96,16 @@ int degtbl2[(2*ETW+1)*(1<<ETW)];
 int childtbl[(ETW)*(1<<ETW)];\r
 int childtbl2[2*ETW+1][ETW][(1<<ETW)];\r
 int depthtbl[(2*ETW+1)*(1<<ETW)];\r
-\r
+int inited = 0;\r
 void make_matchtbl(void)\r
 {\r
   int i,j,x,r;\r
   int m,M;\r
   pb buf[1];\r
   int deg;\r
-\r
+  if (inited)\r
+    return;\r
+  inited = 1;\r
   for (x = 0; x < (1<<ETW); x++) {\r
     setbits(buf,0,ETW,x);\r
     for (r=-ETW; r<=ETW; r++) fwdtbl[((r+ETW)<<ETW)+x] = ETW;\r
@@ -266,7 +276,8 @@ int bp_construct(bp *b,int n, pb *B, int opt)
   mymalloc(b->da,1,0);\r
   darray_construct(b->da,n,B, opt & OPT_FAST_PREORDER_SELECT);\r
   b->idx_size += b->da->idx_size;\r
-  printf("preorder rank/select table: %d bytes (%1.2f bpc)\n",b->da->idx_size,(double)b->da->idx_size*8/n);\r
+  //Kim: comment this and the following, they polute the printing of the xpath library\r
+  //printf("preorder rank/select table: %d bytes (%1.2f bpc)\n",b->da->idx_size,(double)b->da->idx_size*8/n);\r
 \r
   make_matchtbl();\r
 \r
@@ -278,9 +289,9 @@ int bp_construct(bp *b,int n, pb *B, int opt)
   if (opt & OPT_DEGREE) {\r
     mymalloc(sd, ns, 0);  b->idx_size += ns * sizeof(*sd);\r
     b->sd = sd;\r
-    printf("SB degree table: %d bytes (%1.2f bpc)\n",ns * sizeof(*sd), (double)ns * sizeof(*sd) * 8/n);\r
+    //printf("SB degree table: %d bytes (%1.2f bpc)\n",ns * sizeof(*sd), (double)ns * sizeof(*sd) * 8/n);\r
   }\r
-  printf("SB table: %d bytes (%1.2f bpc)\n",ns * sizeof(*sm) * 2, (double)ns * sizeof(*sm)*2 * 8/n);\r
+  //printf("SB table: %d bytes (%1.2f bpc)\n",ns * sizeof(*sm) * 2, (double)ns * sizeof(*sm)*2 * 8/n);\r
 \r
   for (i=0; i<n; i++) {\r
     if (i % SB == 0) {\r
@@ -328,9 +339,9 @@ int bp_construct(bp *b,int n, pb *B, int opt)
   if (opt & OPT_DEGREE) {\r
     mymalloc(md, nm + m_ofs, 0);  b->idx_size += (nm+m_ofs) * sizeof(*md);\r
     b->md = md;\r
-    printf("MB degree table: %d bytes (%1.2f bpc)\n",(nm+m_ofs) * sizeof(*md), (double)(nm+m_ofs) * sizeof(*md) * 8/n);\r
+    //printf("MB degree table: %d bytes (%1.2f bpc)\n",(nm+m_ofs) * sizeof(*md), (double)(nm+m_ofs) * sizeof(*md) * 8/n);\r
   }\r
-  printf("MB table: %d bytes (%1.2f bpc)\n",(nm+m_ofs) * sizeof(*mm) * 2, (double)(nm+m_ofs) * sizeof(*mm)*2 * 8/n);\r
+  //printf("MB table: %d bytes (%1.2f bpc)\n",(nm+m_ofs) * sizeof(*mm) * 2, (double)(nm+m_ofs) * sizeof(*mm)*2 * 8/n);\r
 \r
   for (i=0; i<n; i++) {\r
     d = depth(b,i);\r
@@ -386,7 +397,7 @@ int bp_construct(bp *b,int n, pb *B, int opt)
   if (opt & OPT_LEAF) {\r
     mymalloc(b->da_leaf,1,0);\r
     darray_pat_construct(b->da_leaf, n, B, 2, 0x2, opt & OPT_FAST_LEAF_SELECT);\r
-    printf("leaf rank/select table: %d bytes (%1.2f bpc)\n",b->da_leaf->idx_size,(double)b->da_leaf->idx_size*8/n);\r
+    //printf("leaf rank/select table: %d bytes (%1.2f bpc)\n",b->da_leaf->idx_size,(double)b->da_leaf->idx_size*8/n);\r
     b->idx_size += b->da_leaf->idx_size;  \r
   } else {\r
     b->da_leaf = NULL;\r
@@ -395,7 +406,7 @@ int bp_construct(bp *b,int n, pb *B, int opt)
   if (opt & OPT_INORDER) {\r
     mymalloc(b->da_inorder,1,0);\r
     darray_pat_construct(b->da_inorder, n, B, 2, 0x1, opt & OPT_FAST_INORDER_SELECT);\r
-    printf("inorder rank/select table: %d bytes (%1.2f bpc)\n",b->da_inorder->idx_size,(double)b->da_inorder->idx_size*8/n);\r
+    //printf("inorder rank/select table: %d bytes (%1.2f bpc)\n",b->da_inorder->idx_size,(double)b->da_inorder->idx_size*8/n);\r
     b->idx_size += b->da_inorder->idx_size;\r
   } else {\r
     b->da_inorder = NULL;\r
@@ -404,7 +415,7 @@ int bp_construct(bp *b,int n, pb *B, int opt)
   if (opt & OPT_FAST_POSTORDER_SELECT) {\r
     mymalloc(b->da_postorder,1,0);\r
     darray_pat_construct(b->da_postorder, n, B, 1, 0x0, (opt & OPT_FAST_POSTORDER_SELECT) | OPT_NO_RANK);\r
-    printf("postorder rank/select table: %d bytes (%1.2f bpc)\n",b->da_postorder->idx_size,(double)b->da_postorder->idx_size*8/n);\r
+    //printf("postorder rank/select table: %d bytes (%1.2f bpc)\n",b->da_postorder->idx_size,(double)b->da_postorder->idx_size*8/n);\r
     b->idx_size += b->da_postorder->idx_size;\r
   } else {\r
     b->da_postorder = NULL;\r
@@ -413,7 +424,7 @@ int bp_construct(bp *b,int n, pb *B, int opt)
   if (opt & OPT_DFUDS_LEAF) {\r
     mymalloc(b->da_dfuds_leaf,1,0);\r
     darray_pat_construct(b->da_dfuds_leaf, n, B, 2, 0x0, opt & OPT_FAST_DFUDS_LEAF_SELECT);\r
-    printf("dfuds leaf rank/select table: %d bytes (%1.2f bpc)\n",b->da_dfuds_leaf->idx_size,(double)b->da_dfuds_leaf->idx_size*8/n);\r
+    //printf("dfuds leaf rank/select table: %d bytes (%1.2f bpc)\n",b->da_dfuds_leaf->idx_size,(double)b->da_dfuds_leaf->idx_size*8/n);\r
     b->idx_size += b->da_dfuds_leaf->idx_size;\r
   } else {\r
     b->da_dfuds_leaf = NULL;\r