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 (file)
--- a/XMLTree.cpp
+++ b/XMLTree.cpp
@@ -13,11 +13,6 @@ using std::string;
 // Current implementation corresponds to balanced-parentheses representation for\r
 // the tree, and storing 2 tags per tree node (opening and closing tags).\r
 \r
-// tag position -> tree node\r
-static treeNode tagpos2node(int t) \r
- {\r
-    return (treeNode) t;\r
- }\r
 \r
 static int bits8 (int t ) {\r
   int r = bits(t);\r
@@ -29,36 +24,7 @@ static int bits8 (int t ) {
     return r;\r
 }\r
 \r
-// tree node -> tag position\r
-static int node2tagpos(treeNode x) \r
-{\r
-  return (int)x;\r
-}\r
-\r
-static int fast_find_close(bp *b,int s)\r
-{\r
-  return fwd_excess(b,s,-1);\r
-}\r
-\r
-static int fast_inspect(bp* Par,treeNode i)\r
-{\r
-  int j,l;\r
-  j = i >> logD;\r
-  l = i & (D-1);\r
-  return (Par->B[j] >> (D-1-l)) & 1;\r
-}\r
-\r
-static treeNode fast_first_child(bp *Par, treeNode x)\r
-{\r
-  x = x+1;\r
-  return (fast_inspect(Par,x) == OP) ? x : NULLT;\r
-}\r
 \r
-static treeNode fast_next_sibling(bp* Par,treeNode x)\r
-{\r
-  x = fast_find_close(Par,x)+1;\r
-  return (fast_inspect(Par,x) == OP) ? x : NULLT;\r
-}\r
 \r
 \r
 static treeNode fast_sibling(bp* Par,treeNode x,TagType tag){\r
@@ -98,12 +64,7 @@ static uint fast_get_field(uint* A,int len, int idx)
 \r
 }\r
 \r
-inline bool fast_is_ancestor(bp * Par,treeNode x,treeNode y){\r
-  if (x > y) \r
-    return false;\r
-  else\r
-    return (x==0) || (y <= fast_find_close(Par,x));\r
-}\r
+\r
 \r
 \r
 XMLTree::XMLTree( pb * const par, uint npar,  vector<string> * const TN,  TagIdMap * const tim, \r
@@ -410,11 +371,11 @@ bool XMLTree::IsChild(treeNode x, treeNode y)
  }\r
 \r
 // IsFirstChild(x): returns whether node x is the first child of its parent.\r
-bool XMLTree::IsFirstChild(treeNode x)\r
+/*bool XMLTree::IsFirstChild(treeNode x)\r
  {\r
     return ((x != NULLT)&&(x==Root() || prev_sibling(Par,x) == (treeNode)-1));\r
  }\r
-\r
+*/\r
 \r
 // NumChildren(x): number of children of node x. Constant time with the data structure\r
 // of Sadakane.\r
@@ -479,14 +440,14 @@ range XMLTree::DocIds(treeNode x)
  }\r
 \r
 // Parent(x): returns the parent node of node x.\r
-\r
+/*\r
 treeNode XMLTree::Parent(treeNode x) \r
  {\r
     if (x == Root())\r
       return NULLT;\r
     else\r
       return  parent(Par, x);;\r
- }\r
+ }*/\r
 \r
 // Child(x,i): returns the i-th child of node x, assuming it exists.\r
 treeNode XMLTree::Child(treeNode x, int i) \r
@@ -496,13 +457,14 @@ treeNode XMLTree::Child(treeNode x, int i)
 }\r
 \r
 // FirstChild(x): returns the first child of node x, assuming it exists. Very fast in BP.\r
-\r
+/*\r
 treeNode XMLTree::FirstChild(treeNode x) \r
  {\r
    NULLT_IF(x==NULLT);\r
    return fast_first_child(Par, x);\r
  }\r
-\r
+*/\r
+/*\r
 treeNode XMLTree::FirstElement(treeNode x) \r
  {\r
    NULLT_IF(x==NULLT);\r
@@ -525,7 +487,7 @@ treeNode XMLTree::FirstElement(treeNode x)
      return x;\r
    }\r
  }\r
-\r
+*//*\r
 treeNode XMLTree::NextElement(treeNode x) \r
 {\r
   NULLT_IF(x==NULLT);\r
@@ -536,7 +498,7 @@ treeNode XMLTree::NextElement(treeNode x)
      return (fast_inspect(Par,x)==OP)? x : NULLT;\r
   }\r
   else return x;  \r
-}\r
+  }*/\r
 \r
 // LastChild(x): returns the last child of node x.\r
 treeNode XMLTree::LastChild(treeNode x)\r
@@ -546,13 +508,13 @@ treeNode XMLTree::LastChild(treeNode x)
  }\r
 \r
 // NextSibling(x): returns the next sibling of node x, assuming it exists.\r
-treeNode XMLTree::NextSibling(treeNode x) \r
+/*treeNode XMLTree::NextSibling(treeNode x) \r
  {\r
    NULLT_IF(x==NULLT || x == Root() );\r
    x = fast_find_close(Par,x)+1;\r
    return (fast_inspect(Par,x) == CP ? NULLT : x);\r
  }\r
-\r
+*/\r
 \r
 // PrevSibling(x): returns the previous sibling of node x, assuming it exists.\r
 treeNode XMLTree::PrevSibling(treeNode x) \r
@@ -625,6 +587,7 @@ treeNode XMLTree::SelectFollowingSibling(treeNode x, TagIdSet *tags)
 \r
 // TaggedDescendant(x,tag): returns the first node tagged tag with larger preorder than x and within\r
 // the subtree of x. Returns NULLT if there is none.\r
+/*\r
 treeNode XMLTree::TaggedDescendant(treeNode x, TagType tag) \r
  {\r
    //NULLT_IF(x==NULLT || fast_isleaf(Par,x));\r
@@ -636,7 +599,7 @@ treeNode XMLTree::TaggedDescendant(treeNode x, TagType tag)
    \r
    return (fast_is_ancestor(Par,x,y) ? y : NULLT);\r
  }\r
-\r
+*/\r
 \r
 treeNode XMLTree::SelectDescendant(treeNode x, TagIdSet *tags)\r
  {\r
@@ -689,35 +652,19 @@ treeNode XMLTree::TaggedFollowing(treeNode x, TagType tag)
 \r
 // TaggedFollBelow(x,tag,root): returns the first node tagged tag with larger preorder than x \r
 // and not in the subtree of x. Returns NULLT if there is none.\r
+/*\r
 treeNode XMLTree::TaggedFollowingBelow(treeNode x, TagType tag, treeNode ancestor)\r
 {\r
   // NULLT_IF (x == NULLT || x == Root() || x == ancestor); \r
 \r
   //Special optimisation, test for the following sibling first\r
   treeNode close = fast_find_close(Par, x);\r
-  /*\r
-   treeNode ns = close+1;\r
-  if (fast_inspect(Par,ns) == OP) {\r
-    TagType tagns = Tag(ns);\r
-    //    cout << GetTagNameByRef(tagns) << endl;\r
-    //cout.flush();\r
-    if (tagns == PCDATA_TAG_ID){\r
-      close = ns+1;\r
-      ns = ns+2;\r
-      if (fast_inspect(Par,ns) != OP)\r
-       goto after;\r
-      tagns = Tag(ns);      \r
-    };\r
-    if (tagns == tag)\r
-      return ns;\r
-  };\r
- after:\r
-  */\r
   treeNode s = tagpos2node(Tags->select_next(tag, close));\r
   \r
   if (ancestor == Root() || s==NULLT || s < fast_find_close(Par,ancestor)) return s;\r
   else return NULLT;\r
 } \r
+*/\r
 \r
 treeNode XMLTree::TaggedFollowingBefore(treeNode x, TagType tag, treeNode closing)\r
 {\r

diff --git a/XMLTree.h b/XMLTree.h
index 1eddbb0..8671bae 100644 (file)
--- a/XMLTree.h
+++ b/XMLTree.h
@@ -95,9 +95,47 @@ typedef TagIdMap::const_iterator TagIdMapIT;
 // returns NULLT if the test is true\r
 #define NULLT_IF(x)  do { if (x) return NULLT; } while (0)\r
 \r
-\r
-\r
-\r
+// Direct calls to sarray library\r
+\r
+static inline int fast_find_close(bp *b,int s)\r
+{\r
+  return fwd_excess(b,s,-1);\r
+}\r
+\r
+static int fast_inspect(bp* Par,treeNode i)\r
+{\r
+  int j,l;\r
+  j = i >> logD;\r
+  l = i & (D-1);\r
+  return (Par->B[j] >> (D-1-l)) & 1;\r
+}\r
+\r
+static treeNode fast_first_child(bp *Par, treeNode x)\r
+{\r
+  x = x+1;\r
+  return (fast_inspect(Par,x) == OP) ? x : NULLT;\r
+}\r
+\r
+static treeNode fast_next_sibling(bp* Par,treeNode x)\r
+{\r
+  x = fast_find_close(Par,x)+1;\r
+  return (fast_inspect(Par,x) == OP) ? x : NULLT;\r
+}\r
+\r
+static bool fast_is_ancestor(bp * Par,treeNode x,treeNode y){\r
+  return (x <= y) && ((x==0) || (y <= fast_find_close(Par,x)));\r
+}\r
+\r
+// tag position -> tree node\r
+static treeNode tagpos2node(int t) \r
+ {\r
+    return (treeNode) t;\r
+ }\r
+// tree node -> tag position\r
+static int node2tagpos(treeNode x) \r
+{\r
+  return (int)x;\r
+}\r
 \r
 \r
 class XMLTreeBuilder;\r
@@ -211,7 +249,9 @@ public:
 \r
    /** IsFirstChild(x): returns whether node x is the first child of its parent. */\r
    /* OCAML */\r
-   bool IsFirstChild(treeNode x);\r
+   bool IsFirstChild(treeNode x) { \r
+          return ((x != NULLT)&&(x==Root() || prev_sibling(Par,x) == (treeNode)-1));\r
+   };\r
      \r
    /** NumChildren(x): number of children of node x. Constant time with the \r
     * data structure of Sadakane. */\r
@@ -233,46 +273,29 @@ public:
     * tree nodes (and not texts). */\r
    int Postorder(treeNode x);\r
       \r
-   /** Tag(x): returns the tag identifier of node x. */\r
-   TagType Tag(treeNode x) {\r
-     if (tags_blen == 8)\r
-       return  (TagType) (((uchar*)tags_fix)[(int) x]);\r
-     else\r
-       return (TagType) get_field(tags_fix,tags_blen, (int) x);\r
-   }\r
 \r
    /** DocIds(x): returns the range (i.e., a pair of integers) of document \r
     * identifiers that descend from node x. */\r
    range DocIds(treeNode x);\r
 \r
    /** Parent(x): returns the parent node of node x. */\r
-   treeNode Parent(treeNode x);\r
+   treeNode Parent(treeNode x) {          \r
+    if (x == Root())\r
+      return NULLT;\r
+    else\r
+      return parent(Par, x);\r
+   };\r
    /* Assumes x is neither 0 nor -1 */\r
    \r
    /** Child(x,i): returns the i-th child of node x, assuming it exists. */   \r
    treeNode Child(treeNode x, int i);\r
 \r
-   /** FirstChild(x): returns the first child of node x, or NULLT if the node is a leaf\r
-    */\r
-   treeNode FirstChild(treeNode x);\r
 \r
-   /** FirstElement(x): returns the first non text, non attribute child of node x, or NULLT\r
-    *    if none.\r
-    */\r
-   treeNode FirstElement(treeNode x);\r
 \r
    /** LastChild(x): returns the last child of node x.  */\r
    treeNode LastChild(treeNode x);\r
    \r
-   /** NextSibling(x): returns the next sibling of node x, or NULLT if none \r
-    * exists. */\r
 \r
-   treeNode NextSibling(treeNode x);\r
-\r
-   /** NextElement(x): returns the first non text, non attribute sibling of node x, or NULLT\r
-    *    if none.\r
-    */\r
-   treeNode NextElement(treeNode x);\r
 \r
    /** PrevSibling(x): returns the previous sibling of node x, assuming it \r
     * exists. */\r
@@ -293,12 +316,10 @@ public:
    \r
    treeNode SelectFollowingSibling(treeNode x, TagIdSet * tags);\r
 \r
-   /** TaggedDesc(x,tag): returns the first node tagged tag with larger \r
-    * preorder than x and within the subtree of x. Returns NULT if there \r
-    * is none. */\r
-   treeNode TaggedDescendant(treeNode x, TagType tag);\r
 \r
-   treeNode SelectDescendant(treeNode x, TagIdSet * tags);\r
+\r
+\r
+  treeNode SelectDescendant(treeNode x, TagIdSet * tags);\r
 \r
    /** TaggedPrec(x,tag): returns the first node tagged tag with smaller \r
     * preorder than x and not an ancestor of x. Returns NULLT if there \r
@@ -310,7 +331,7 @@ public:
     * is none. */\r
    treeNode TaggedFollowing(treeNode x, TagType tag);\r
 \r
-   treeNode TaggedFollowingBelow(treeNode x, TagType tag,treeNode ancestor);     \r
+\r
 \r
    treeNode SelectFollowingBelow(treeNode x, TagIdSet * tags, treeNode ancestor);\r
 \r
@@ -498,6 +519,96 @@ public:
    void Print(int fd,treeNode x, bool no_text);\r
    void Print(int fd,treeNode x) { Print(fd,x,false); }\r
 \r
+  // The following are inlined here for speed\r
+  /** Tag(x): returns the tag identifier of node x. */\r
+\r
+  TagType Tag(treeNode x) {\r
+    if (tags_blen == 8)\r
+      return  (TagType) (((uchar*)tags_fix)[(int) x]);\r
+    else\r
+      return (TagType) get_field(tags_fix,tags_blen, (int) x);\r
+  }\r
+\r
+     /** FirstChild(x): returns the first child of node x, or NULLT if the node is a leaf\r
+    */\r
+   treeNode FirstChild(treeNode x) {\r
+          NULLT_IF(x==NULLT);\r
+          return fast_first_child(Par, x);\r
+   };\r
+\r
+\r
+   /** FirstElement(x): returns the first non text, non attribute child of node x, or NULLT\r
+    *    if none.\r
+    */\r
+   treeNode FirstElement(treeNode x){\r
+     {\r
+       NULLT_IF(x==NULLT);\r
+       x = fast_first_child(Par, x);\r
+       NULLT_IF(x == NULLT);\r
+       switch (Tag(x)){\r
+        \r
+       case PCDATA_TAG_ID:\r
+        x = x+2;\r
+        return (fast_inspect(Par,x)==OP)? x : NULLT;\r
+        \r
+       case ATTRIBUTE_TAG_ID:  \r
+        x = fast_next_sibling(Par,x);\r
+        if (x != NULLT && Tag(x) == PCDATA_TAG_ID){\r
+          x = x+2;\r
+          return (fast_inspect(Par,x)==OP)? x : NULLT;\r
+        } \r
+        else return x;     \r
+       default:\r
+        return x;\r
+       }\r
+     }\r
+   };\r
+\r
+  /** NextSibling(x): returns the next sibling of node x, or NULLT if none \r
+   * exists. */\r
+  \r
+  treeNode NextSibling(treeNode x) {\r
+    NULLT_IF (x <= 0);\r
+    return fast_next_sibling(Par, x);\r
+  };\r
+  \r
+   /** NextElement(x): returns the first non text, non attribute sibling of node x, or NULLT\r
+    *    if none.\r
+    */\r
+  treeNode NextElement(treeNode x)\r
+  {\r
+    NULLT_IF(x <= 0);\r
+    x = fast_next_sibling(Par, x);\r
+    NULLT_IF(x == NULLT);   \r
+    if (Tag(x) == PCDATA_TAG_ID){\r
+      x = x+2;\r
+      return (fast_inspect(Par,x)==OP)? x : NULLT;\r
+    }\r
+    else return x;  \r
+  };\r
+     /** TaggedDesc(x,tag): returns the first node tagged tag with larger \r
+    * preorder than x and within the subtree of x. Returns NULT if there \r
+    * is none. */\r
+  treeNode TaggedDescendant(treeNode x, TagType tag)\r
+  {\r
+    \r
+         int s = (int) Tags->select_next(tag,node2tagpos(x));\r
+         NULLT_IF (s == -1);\r
+         \r
+         treeNode y = tagpos2node(s); // transforms the tag position into a node position\r
+         \r
+         return (fast_is_ancestor(Par,x,y) ? y : NULLT);\r
+  };\r
+  \r
+  treeNode TaggedFollowingBelow(treeNode x, TagType tag,treeNode ancestor)\r
+  {\r
+         treeNode close = fast_find_close(Par, x);\r
+         treeNode s = tagpos2node(Tags->select_next(tag, close));\r
+         \r
+         if (ancestor == Root() || s == NULLT || s < fast_find_close(Par,ancestor)) return s;\r
+         else return NULLT;\r
+  };\r
+    \r
 };\r
 \r
 \r

diff --git a/libcds/src/static_bitsequence/static_bitsequence_sdarray.h b/libcds/src/static_bitsequence/static_bitsequence_sdarray.h
index 54ab29a..f8944d4 100644 (file)
--- 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 (file)
--- 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 (file)
--- a/makefile
+++ b/makefile
@@ -1,6 +1,7 @@
-CFLAGS= -g -O0 -I./libcds/includes/ -I.\r
+CFLAGS= -O6 -I./libcds/includes/ -fno-PIC -I.\r
 FLAGS= -std=c++0x $(CFLAGS)\r
 \r
+\r
 LIBCDS_A=libcds/lib/libcds.a \r
 OBJECTS_TCO= TextCollection/TextCollection.o TextCollection/TextCollectionBuilder.o TextCollection/RLCSABuilder.o \\r
              TextCollection/FMIndex.o TextCollection/FMIndexBuilder.o TextCollection/Tools.o \\r