timeXMLTree.cpp

   1 #include "XMLDocShredder.h"
   2 #include "XMLTree.h"
   3 #include "Utils.h"
   4 #include <sys/time.h>
   5 #include <time.h>
   6
   7 using std::cout;
   8 using std::string;
   9 using std::left;
  10 using std::right;
  11
  12 static double tFirstChild = 0;
  13 static double tNextSibling = 0;
  14 static double tParent = 0;
  15 static double tTaggedAncestor = 0;
  16 static double tTaggedChild = 0;
  17 static double tTaggedDesc = 0;
  18 static double tTaggedFoll = 0;
  19 static double tParentNode = 0;
  20 static double tPrevNode = 0;
  21 static double tTag = 0;
  22 static double tMyText = 0;
  23 static double tPrevText = 0;
  24 static double tNextText = 0;
  25 static double tDocIds = 0;
  26
  27 static double tFullTraversal = 0;
  28 static double tJumpTraversal = 0;
  29
  30 static unsigned int cFirstChild = 0;
  31 static unsigned int cNextSibling = 0;
  32 static unsigned int cParent = 0;
  33 static unsigned int cTaggedAncestor = 0;
  34 static unsigned int cTaggedChild = 0;
  35 static unsigned int cTaggedDesc = 0;
  36 static unsigned int cTaggedFoll = 0;
  37 static unsigned int cParentNode = 0;
  38 static unsigned int cPrevNode = 0;
  39 static unsigned int cTag = 0;
  40 static unsigned int cMyText = 0;
  41 static unsigned int cPrevText = 0;
  42 static unsigned int cNextText = 0;
  43 static unsigned int cDocIds = 0;
  44
  45 static unsigned int cFullTraversal = 0;
  46 static unsigned int cJumpTraversal = 0;
  47
  48
  49 static struct timeval tmpv1;
  50 static struct timeval tmpv2;
  51
  52 static TagType target_tag = -1;
  53
  54 #define STARTTIMER()   (gettimeofday(&tmpv1,NULL))
  55 #define STOPTIMER(x)   do {                                             \
  56     gettimeofday(&tmpv2,NULL);                                          \
  57     (t##x) = (t##x) + ((tmpv2.tv_sec  - tmpv1.tv_sec) * 1000000.0 +     \
  58                        (tmpv2.tv_usec  - tmpv1.tv_usec))/1000.0;        \
  59     (c##x)= (c##x)+1;                                                   \
  60   } while (0)
  61
  62 #define PRINTSTATS(x)  do {                                             \
  63     std::cout.width(15);                                                \
  64     std::cout << std::left << #x;                                       \
  65     std::cout << " : ";                                                 \
  66     std::cout.width(8);                                                 \
  67     std::cout << std::right << c##x << " calls, ";                      \
  68     std::cout.width(8);                                                 \
  69     std::cout << std::right << (t##x)                                   \
  70               << " ms, mean: ";                                         \
  71     std::cout.width(8);                                                 \
  72     std::cout << std::right                                             \
  73               << (t##x)  *1.00 / c##x                                   \
  74               << "\n";                                                  \
  75   } while (0)
  76
  77 void traversal(XMLTree * tree, treeNode node,unsigned char* targettagname){
  78   treeNode res1,res2;
  79   TagType tag;
  80   DocID id1,id2,id3;
  81   range rg;
  82   const unsigned char * tagname;
  83   if (node != NULLT){
  84
  85     STARTTIMER();
  86     tag = tree->Tag(node);
  87     STOPTIMER(Tag);
  88     if (target_tag == -1){
  89       tagname = tree->GetTagNameByRef(tag);
  90       if (strcmp( (char*) tagname, (char*) targettagname) == 0)
  91         target_tag = tag;
  92     };
  93     STARTTIMER();
  94     res1 = tree->Parent(node);
  95     STOPTIMER(Parent);
  96     /*
  97     STARTTIMER();
  98     res1 = tree->TaggedChild(node,0,tag);
  99     STOPTIMER(TaggedChild);
 100
 101     STARTTIMER();
 102     res1 = tree->TaggedAncestor(node,tag);
 103     STOPTIMER(TaggedAncestor);
 104     */
 105     STARTTIMER();
 106     res1 = tree->TaggedDesc(node,tag);
 107     STOPTIMER(TaggedDesc);
 108
 109     STARTTIMER();
 110     res1 = tree->TaggedFoll(node,tag);
 111     STOPTIMER(TaggedFoll);
 112
 113     STARTTIMER();
 114     rg = tree->DocIds(node);
 115     STOPTIMER(DocIds);
 116
 117     STARTTIMER();
 118     id1 = tree->MyText(node);
 119     STOPTIMER(MyText);
 120
 121     STARTTIMER();
 122     id2 = tree->PrevText(node);
 123     STOPTIMER(PrevText);
 124
 125     STARTTIMER();
 126     id3 = tree->NextText(node);
 127     STOPTIMER(NextText);
 128
 129     id1 = max(id1, max(id2,id3));
 130
 131     STARTTIMER();
 132     res1 = tree->ParentNode(id1);
 133     STOPTIMER(ParentNode);
 134
 135     STARTTIMER();
 136     res1 = tree->PrevNode(id1);
 137     STOPTIMER(PrevNode);
 138
 139     STARTTIMER();
 140     res1 = tree->FirstChild(node);
 141     STOPTIMER(FirstChild);
 142
 143     STARTTIMER();
 144     res2 = tree->NextSibling(node);
 145     STOPTIMER(NextSibling);
 146
 147     traversal(tree,res1,targettagname);
 148     traversal(tree,res2,targettagname);
 149
 150   };
 151
 152 }
 153
 154 /* This simulates the run function of the automata */
 155
 156 unsigned int time_traversal(XMLTree *tree,treeNode node){
 157   TagType tag;
 158   if (node != NULLT) {
 159     cFullTraversal++;
 160     tag = tree->Tag(node);
 161     if (tag == target_tag)
 162       return 1 +
 163         time_traversal(tree,tree->FirstChild(node)) +
 164         time_traversal(tree,tree->NextSibling(node));
 165     else
 166       return time_traversal(tree,tree->FirstChild(node)) +
 167         time_traversal(tree,tree->NextSibling(node));
 168
 169   }
 170   else
 171     return 0;
 172 }
 173
 174 /* This simulates the run function of the jumping automata*/
 175 unsigned int time_jump(XMLTree* tree, treeNode node,treeNode root){
 176   TagType tag;
 177   if (node != NULLT) {
 178     cJumpTraversal++;
 179     tag = tree->Tag(node);
 180     if (tag == target_tag)
 181       return 1 +
 182         time_jump(tree, tree->TaggedDesc(node,target_tag),node) +
 183         time_jump(tree, tree->TaggedFollBelow(node,target_tag,root),  root);
 184
 185     else
 186       return time_jump(tree, tree->TaggedDesc(node,target_tag),node) +
 187         time_jump(tree, tree->TaggedFollBelow(node,target_tag,root),  root);
 188   }
 189   else
 190     return 0;
 191 }
 192
 193
 194
 195
 196
 197 int main(int argc, char ** argv){
 198   unsigned int count1,count2;
 199   unsigned char * tagname = (unsigned char *) "keyword";
 200
 201   if (argc != 2){
 202     std::cout << "Usage : " << argv[0] << " filename (without .srx)\n";
 203     return 1;
 204   };
 205
 206   // The samplerate is not taken into account for loading anymore
 207   XMLTree * tree = XMLTree::Load((unsigned char*) argv[1],64);
 208
 209   traversal(tree,tree->Root(),tagname);
 210
 211   STARTTIMER();
 212   count1 = time_traversal(tree,tree->Root());
 213   STOPTIMER(FullTraversal);
 214
 215   count2 = time_jump(tree,tree->Root(),tree->Root());
 216   STOPTIMER(JumpTraversal);
 217
 218   PRINTSTATS(Tag);
 219   PRINTSTATS(FirstChild);
 220   PRINTSTATS(NextSibling);
 221   PRINTSTATS(Parent);
 222   PRINTSTATS(TaggedAncestor);
 223   PRINTSTATS(TaggedChild);
 224   PRINTSTATS(DocIds);
 225   PRINTSTATS(TaggedDesc);
 226   PRINTSTATS(TaggedFoll);
 227   PRINTSTATS(PrevText);
 228   PRINTSTATS(MyText);
 229   PRINTSTATS(NextText);
 230   PRINTSTATS(ParentNode);
 231   PRINTSTATS(PrevNode);
 232   std::cout << "\n";
 233   std::cout << "Full traversal found " << count1 << " " << tagname << "  nodes\n";
 234   PRINTSTATS(FullTraversal);
 235   std::cout << "\n";
 236   std::cout << "Jump traversal found " << count2 << " " << tagname << "  nodes\n";
 237   PRINTSTATS(JumpTraversal);
 238
 239
 240   return 0;
 241 }