From: kim <kim@3cdefd35-fc62-479d-8e8d-bae585ffb9ca>
Date: Mon, 7 Feb 2011 13:24:36 +0000 (+0000)
Subject: Add some inlining by hand
X-Git-Url: http://git.nguyen.vg/gitweb/?p=SXSI%2FXMLTree.git;a=commitdiff_plain;h=45de465016fdd58a01d69012691772ef1b8d335c

Add some inlining by hand

git-svn-id: svn+ssh://idea.nguyen.vg/svn/sxsi/trunk/XMLTree@952 3cdefd35-fc62-479d-8e8d-bae585ffb9ca
---

diff --git a/XMLTree.cpp b/XMLTree.cpp
index 764e910..a0815b8 100644
--- a/XMLTree.cpp
+++ b/XMLTree.cpp
@@ -13,11 +13,6 @@ using std::string;
 // Current implementation corresponds to balanced-parentheses representation for
 // the tree, and storing 2 tags per tree node (opening and closing tags).
 
-// tag position -> tree node
-static treeNode tagpos2node(int t) 
- {
-    return (treeNode) t;
- }
 
 static int bits8 (int t ) {
   int r = bits(t);
@@ -29,36 +24,7 @@ static int bits8 (int t ) {
     return r;
 }
 
-// tree node -> tag position
-static int node2tagpos(treeNode x) 
-{
-  return (int)x;
-}
-
-static int fast_find_close(bp *b,int s)
-{
-  return fwd_excess(b,s,-1);
-}
-
-static int fast_inspect(bp* Par,treeNode i)
-{
-  int j,l;
-  j = i >> logD;
-  l = i & (D-1);
-  return (Par->B[j] >> (D-1-l)) & 1;
-}
-
-static treeNode fast_first_child(bp *Par, treeNode x)
-{
-  x = x+1;
-  return (fast_inspect(Par,x) == OP) ? x : NULLT;
-}
 
-static treeNode fast_next_sibling(bp* Par,treeNode x)
-{
-  x = fast_find_close(Par,x)+1;
-  return (fast_inspect(Par,x) == OP) ? x : NULLT;
-}
 
 
 static treeNode fast_sibling(bp* Par,treeNode x,TagType tag){
@@ -98,12 +64,7 @@ static uint fast_get_field(uint* A,int len, int idx)
 
 }
 
-inline bool fast_is_ancestor(bp * Par,treeNode x,treeNode y){
-  if (x > y) 
-    return false;
-  else
-    return (x==0) || (y <= fast_find_close(Par,x));
-}
+
 
 
 XMLTree::XMLTree( pb * const par, uint npar,  vector<string> * const TN,  TagIdMap * const tim, 
@@ -410,11 +371,11 @@ bool XMLTree::IsChild(treeNode x, treeNode y)
  }
 
 // IsFirstChild(x): returns whether node x is the first child of its parent.
-bool XMLTree::IsFirstChild(treeNode x)
+/*bool XMLTree::IsFirstChild(treeNode x)
  {
     return ((x != NULLT)&&(x==Root() || prev_sibling(Par,x) == (treeNode)-1));
  }
-
+*/
 
 // NumChildren(x): number of children of node x. Constant time with the data structure
 // of Sadakane.
@@ -479,14 +440,14 @@ range XMLTree::DocIds(treeNode x)
  }
 
 // Parent(x): returns the parent node of node x.
-
+/*
 treeNode XMLTree::Parent(treeNode x) 
  {
     if (x == Root())
       return NULLT;
     else
       return  parent(Par, x);;
- }
+ }*/
 
 // Child(x,i): returns the i-th child of node x, assuming it exists.
 treeNode XMLTree::Child(treeNode x, int i) 
@@ -496,13 +457,14 @@ treeNode XMLTree::Child(treeNode x, int i)
 }
 
 // FirstChild(x): returns the first child of node x, assuming it exists. Very fast in BP.
-
+/*
 treeNode XMLTree::FirstChild(treeNode x) 
  {
    NULLT_IF(x==NULLT);
    return fast_first_child(Par, x);
  }
-
+*/
+/*
 treeNode XMLTree::FirstElement(treeNode x) 
  {
    NULLT_IF(x==NULLT);
@@ -525,7 +487,7 @@ treeNode XMLTree::FirstElement(treeNode x)
      return x;
    }
  }
-
+*//*
 treeNode XMLTree::NextElement(treeNode x) 
 {
   NULLT_IF(x==NULLT);
@@ -536,7 +498,7 @@ treeNode XMLTree::NextElement(treeNode x)
      return (fast_inspect(Par,x)==OP)? x : NULLT;
   }
   else return x;  
-}
+  }*/
 
 // LastChild(x): returns the last child of node x.
 treeNode XMLTree::LastChild(treeNode x)
@@ -546,13 +508,13 @@ treeNode XMLTree::LastChild(treeNode x)
  }
 
 // NextSibling(x): returns the next sibling of node x, assuming it exists.
-treeNode XMLTree::NextSibling(treeNode x) 
+/*treeNode XMLTree::NextSibling(treeNode x) 
  {
    NULLT_IF(x==NULLT || x == Root() );
    x = fast_find_close(Par,x)+1;
    return (fast_inspect(Par,x) == CP ? NULLT : x);
  }
-
+*/
 
 // PrevSibling(x): returns the previous sibling of node x, assuming it exists.
 treeNode XMLTree::PrevSibling(treeNode x) 
@@ -625,6 +587,7 @@ treeNode XMLTree::SelectFollowingSibling(treeNode x, TagIdSet *tags)
 
 // TaggedDescendant(x,tag): returns the first node tagged tag with larger preorder than x and within
 // the subtree of x. Returns NULLT if there is none.
+/*
 treeNode XMLTree::TaggedDescendant(treeNode x, TagType tag) 
  {
    //NULLT_IF(x==NULLT || fast_isleaf(Par,x));
@@ -636,7 +599,7 @@ treeNode XMLTree::TaggedDescendant(treeNode x, TagType tag)
    
    return (fast_is_ancestor(Par,x,y) ? y : NULLT);
  }
-
+*/
 
 treeNode XMLTree::SelectDescendant(treeNode x, TagIdSet *tags)
  {
@@ -689,35 +652,19 @@ treeNode XMLTree::TaggedFollowing(treeNode x, TagType tag)
 
 // TaggedFollBelow(x,tag,root): returns the first node tagged tag with larger preorder than x 
 // and not in the subtree of x. Returns NULLT if there is none.
+/*
 treeNode XMLTree::TaggedFollowingBelow(treeNode x, TagType tag, treeNode ancestor)
 {
   // NULLT_IF (x == NULLT || x == Root() || x == ancestor); 
 
   //Special optimisation, test for the following sibling first
   treeNode close = fast_find_close(Par, x);
-  /*
-   treeNode ns = close+1;
-  if (fast_inspect(Par,ns) == OP) {
-    TagType tagns = Tag(ns);
-    //    cout << GetTagNameByRef(tagns) << endl;
-    //cout.flush();
-    if (tagns == PCDATA_TAG_ID){
-      close = ns+1;
-      ns = ns+2;
-      if (fast_inspect(Par,ns) != OP)
-	goto after;
-      tagns = Tag(ns);      
-    };
-    if (tagns == tag)
-      return ns;
-  };
- after:
-  */
   treeNode s = tagpos2node(Tags->select_next(tag, close));
   
   if (ancestor == Root() || s==NULLT || s < fast_find_close(Par,ancestor)) return s;
   else return NULLT;
 } 
+*/
 
 treeNode XMLTree::TaggedFollowingBefore(treeNode x, TagType tag, treeNode closing)
 {
diff --git a/XMLTree.h b/XMLTree.h
index 1eddbb0..8671bae 100644
--- a/XMLTree.h
+++ b/XMLTree.h
@@ -95,9 +95,47 @@ typedef TagIdMap::const_iterator TagIdMapIT;
 // returns NULLT if the test is true
 #define NULLT_IF(x)  do { if (x) return NULLT; } while (0)
 
-
-
-
+// Direct calls to sarray library
+
+static inline int fast_find_close(bp *b,int s)
+{
+  return fwd_excess(b,s,-1);
+}
+
+static int fast_inspect(bp* Par,treeNode i)
+{
+  int j,l;
+  j = i >> logD;
+  l = i & (D-1);
+  return (Par->B[j] >> (D-1-l)) & 1;
+}
+
+static treeNode fast_first_child(bp *Par, treeNode x)
+{
+  x = x+1;
+  return (fast_inspect(Par,x) == OP) ? x : NULLT;
+}
+
+static treeNode fast_next_sibling(bp* Par,treeNode x)
+{
+  x = fast_find_close(Par,x)+1;
+  return (fast_inspect(Par,x) == OP) ? x : NULLT;
+}
+
+static bool fast_is_ancestor(bp * Par,treeNode x,treeNode y){
+  return (x <= y) && ((x==0) || (y <= fast_find_close(Par,x)));
+}
+
+// tag position -> tree node
+static treeNode tagpos2node(int t) 
+ {
+    return (treeNode) t;
+ }
+// tree node -> tag position
+static int node2tagpos(treeNode x) 
+{
+  return (int)x;
+}
 
 
 class XMLTreeBuilder;
@@ -211,7 +249,9 @@ public:
 
    /** IsFirstChild(x): returns whether node x is the first child of its parent. */
    /* OCAML */
-   bool IsFirstChild(treeNode x);
+   bool IsFirstChild(treeNode x) { 
+	   return ((x != NULLT)&&(x==Root() || prev_sibling(Par,x) == (treeNode)-1));
+   };
      
    /** NumChildren(x): number of children of node x. Constant time with the 
     * data structure of Sadakane. */
@@ -233,46 +273,29 @@ public:
     * tree nodes (and not texts). */
    int Postorder(treeNode x);
       
-   /** Tag(x): returns the tag identifier of node x. */
-   TagType Tag(treeNode x) {
-     if (tags_blen == 8)
-       return  (TagType) (((uchar*)tags_fix)[(int) x]);
-     else
-       return (TagType) get_field(tags_fix,tags_blen, (int) x);
-   }
 
    /** DocIds(x): returns the range (i.e., a pair of integers) of document 
     * identifiers that descend from node x. */
    range DocIds(treeNode x);
 
    /** Parent(x): returns the parent node of node x. */
-   treeNode Parent(treeNode x);
+   treeNode Parent(treeNode x) {	   
+    if (x == Root())
+      return NULLT;
+    else
+      return parent(Par, x);
+   };
    /* Assumes x is neither 0 nor -1 */
    
    /** Child(x,i): returns the i-th child of node x, assuming it exists. */   
    treeNode Child(treeNode x, int i);
 
-   /** FirstChild(x): returns the first child of node x, or NULLT if the node is a leaf
-    */
-   treeNode FirstChild(treeNode x);
 
-   /** FirstElement(x): returns the first non text, non attribute child of node x, or NULLT
-    *    if none.
-    */
-   treeNode FirstElement(treeNode x);
 
    /** LastChild(x): returns the last child of node x.  */
    treeNode LastChild(treeNode x);
    
-   /** NextSibling(x): returns the next sibling of node x, or NULLT if none 
-    * exists. */
 
-   treeNode NextSibling(treeNode x);
-
-   /** NextElement(x): returns the first non text, non attribute sibling of node x, or NULLT
-    *    if none.
-    */
-   treeNode NextElement(treeNode x);
 
    /** PrevSibling(x): returns the previous sibling of node x, assuming it 
     * exists. */
@@ -293,12 +316,10 @@ public:
    
    treeNode SelectFollowingSibling(treeNode x, TagIdSet * tags);
 
-   /** TaggedDesc(x,tag): returns the first node tagged tag with larger 
-    * preorder than x and within the subtree of x. Returns NULT if there 
-    * is none. */
-   treeNode TaggedDescendant(treeNode x, TagType tag);
 
-   treeNode SelectDescendant(treeNode x, TagIdSet * tags);
+
+
+  treeNode SelectDescendant(treeNode x, TagIdSet * tags);
 
    /** TaggedPrec(x,tag): returns the first node tagged tag with smaller 
     * preorder than x and not an ancestor of x. Returns NULLT if there 
@@ -310,7 +331,7 @@ public:
     * is none. */
    treeNode TaggedFollowing(treeNode x, TagType tag);
 
-   treeNode TaggedFollowingBelow(treeNode x, TagType tag,treeNode ancestor);     
+
 
    treeNode SelectFollowingBelow(treeNode x, TagIdSet * tags, treeNode ancestor);
 
@@ -498,6 +519,96 @@ public:
    void Print(int fd,treeNode x, bool no_text);
    void Print(int fd,treeNode x) { Print(fd,x,false); }
 
+  // The following are inlined here for speed
+  /** Tag(x): returns the tag identifier of node x. */
+
+  TagType Tag(treeNode x) {
+    if (tags_blen == 8)
+      return  (TagType) (((uchar*)tags_fix)[(int) x]);
+    else
+      return (TagType) get_field(tags_fix,tags_blen, (int) x);
+  }
+
+     /** FirstChild(x): returns the first child of node x, or NULLT if the node is a leaf
+    */
+   treeNode FirstChild(treeNode x) {
+	   NULLT_IF(x==NULLT);
+	   return fast_first_child(Par, x);
+   };
+
+
+   /** FirstElement(x): returns the first non text, non attribute child of node x, or NULLT
+    *    if none.
+    */
+   treeNode FirstElement(treeNode x){
+     {
+       NULLT_IF(x==NULLT);
+       x = fast_first_child(Par, x);
+       NULLT_IF(x == NULLT);
+       switch (Tag(x)){
+	 
+       case PCDATA_TAG_ID:
+	 x = x+2;
+	 return (fast_inspect(Par,x)==OP)? x : NULLT;
+	 
+       case ATTRIBUTE_TAG_ID:  
+	 x = fast_next_sibling(Par,x);
+	 if (x != NULLT && Tag(x) == PCDATA_TAG_ID){
+	   x = x+2;
+	   return (fast_inspect(Par,x)==OP)? x : NULLT;
+	 } 
+	 else return x;     
+       default:
+	 return x;
+       }
+     }
+   };
+
+  /** NextSibling(x): returns the next sibling of node x, or NULLT if none 
+   * exists. */
+  
+  treeNode NextSibling(treeNode x) {
+    NULLT_IF (x <= 0);
+    return fast_next_sibling(Par, x);
+  };
+  
+   /** NextElement(x): returns the first non text, non attribute sibling of node x, or NULLT
+    *    if none.
+    */
+  treeNode NextElement(treeNode x)
+  {
+    NULLT_IF(x <= 0);
+    x = fast_next_sibling(Par, x);
+    NULLT_IF(x == NULLT);   
+    if (Tag(x) == PCDATA_TAG_ID){
+      x = x+2;
+      return (fast_inspect(Par,x)==OP)? x : NULLT;
+    }
+    else return x;  
+  };
+     /** TaggedDesc(x,tag): returns the first node tagged tag with larger 
+    * preorder than x and within the subtree of x. Returns NULT if there 
+    * is none. */
+  treeNode TaggedDescendant(treeNode x, TagType tag)
+  {
+    
+	  int s = (int) Tags->select_next(tag,node2tagpos(x));
+	  NULLT_IF (s == -1);
+	  
+	  treeNode y = tagpos2node(s); // transforms the tag position into a node position
+	  
+	  return (fast_is_ancestor(Par,x,y) ? y : NULLT);
+  };
+  
+  treeNode TaggedFollowingBelow(treeNode x, TagType tag,treeNode ancestor)
+  {
+	  treeNode close = fast_find_close(Par, x);
+	  treeNode s = tagpos2node(Tags->select_next(tag, close));
+	  
+	  if (ancestor == Root() || s == NULLT || s < fast_find_close(Par,ancestor)) return s;
+	  else return NULLT;
+  };
+    
 };
 
 
diff --git a/libcds/src/static_bitsequence/static_bitsequence_sdarray.h b/libcds/src/static_bitsequence/static_bitsequence_sdarray.h
index 54ab29a..f8944d4 100644
--- a/libcds/src/static_bitsequence/static_bitsequence_sdarray.h
+++ b/libcds/src/static_bitsequence/static_bitsequence_sdarray.h
@@ -17,6 +17,9 @@ class static_bitsequence_sdarray: public static_bitsequence {
 		virtual int save(FILE * fp);
 		static static_bitsequence_sdarray * load(FILE * fp);
 
+		uint select_next1_unsafe(uint i){
+			return selects3_selectnext(&sd,i);	
+		};
 	protected:
 		selects3 sd;
 		static_bitsequence_sdarray();
diff --git a/libcds/src/static_sequence/static_sequence_bs.h b/libcds/src/static_sequence/static_sequence_bs.h
index 76de5ae..fe023d0 100644
--- a/libcds/src/static_sequence/static_sequence_bs.h
+++ b/libcds/src/static_sequence/static_sequence_bs.h
@@ -40,7 +40,7 @@ public:
   virtual uint rank(uint c, uint i);
   
   virtual uint select(uint c, uint i);
-	virtual uint select_next(uint c, uint i);
+  uint select_next(uint c, uint i);
 
   virtual uint access(uint i);
 
@@ -50,7 +50,13 @@ public:
 
   /** Reads a bitmap determining the type */
   static static_sequence_bs * load(FILE * fp);
-  
+
+  uint select_next_unsafe(uint c, uint i){
+	  static_bitsequence * bs = bitmaps[c];
+	  static_bitsequence_sdarray * sd = reinterpret_cast<static_bitsequence_sdarray *>(bs);
+	  return sd->select_next1_unsafe(i);
+  };
+ 
 protected:
   uint sigma;
 	static_bitsequence ** bitmaps;
diff --git a/makefile b/makefile
index 65ca372..5caf9dd 100644
--- a/makefile
+++ b/makefile
@@ -1,6 +1,7 @@
-CFLAGS= -g -O0 -I./libcds/includes/ -I.
+CFLAGS= -O6 -I./libcds/includes/ -fno-PIC -I.
 FLAGS= -std=c++0x $(CFLAGS)
 
+
 LIBCDS_A=libcds/lib/libcds.a 
 OBJECTS_TCO= TextCollection/TextCollection.o TextCollection/TextCollectionBuilder.o TextCollection/RLCSABuilder.o \
              TextCollection/FMIndex.o TextCollection/FMIndexBuilder.o TextCollection/Tools.o \