myTimeXMLTree.cpp

   1 #include "XMLDocShredder.h"
   2 #include "XMLTree.h"
   3 #include "Utils.h"
   4 #include <sys/time.h>
   5 #include <time.h>
   6 #include <sys/stat.h>
   7 #include <vector>
   8 #include <queue>
   9
  10 using namespace std;
  11
  12 /* Time meassuring */
  13 double ticks= (double)sysconf(_SC_CLK_TCK);
  14 struct tms t1,t2;
  15
  16 void start_clock() {
  17   times (&t1);
  18 }
  19
  20
  21 double stop_clock() {
  22   times (&t2);
  23   return (t2.tms_utime-t1.tms_utime)/ticks;
  24 }
  25
  26
  27 /* end Time meassuring */
  28
  29 void printStats(double time, string fname, uint queries) {
  30   cout.width(15);
  31   cout << std::left << fname;
  32   cout << " : ";
  33   cout.width(8);
  34   cout << std::right << queries << " calls, ";
  35   cout.width(8);
  36   cout << std::right << time << "ms, mean: ";
  37   cout.width(8);
  38   cout << std::right << time/queries << endl;
  39 }
  40
  41
  42 #define STATS1(fname,vect) {\
  43     start_clock(); \
  44     uint q = 0; \
  45     while(q<treenodeQueries.size()) \
  46     { \
  47       acc += tree->fname((vect)[q]); \
  48       q++; \
  49     } \
  50     double t = 1000.0*stop_clock(); \
  51     printStats(t,#fname,(vect).size()); \
  52   }
  53
  54 #define STATS1p(fname,vect) {\
  55     start_clock(); \
  56     uint q = 0; \
  57     while(q<treenodeQueries.size()) \
  58     { \
  59       acc += tree->fname((vect)[q]).min; \
  60       q++; \
  61     } \
  62     double t = 1000.0*stop_clock(); \
  63     printStats(t,#fname,(vect).size()); \
  64   }
  65
  66 #define STATS2(fname,vect) {\
  67     start_clock(); \
  68     uint q = 0; \
  69     while(q<treenodeQueries.size()) \
  70     { \
  71       acc += tree->fname((vect)[q].first,(vect)[q].second); \
  72       q++; \
  73     } \
  74     double t = 1000.0*stop_clock(); \
  75     printStats(t,#fname,(vect).size()); \
  76   }
  77
  78       TagType target_tag = -1;
  79 vector<treeNode> treenodeQueries;
  80 vector<pair<treeNode,TagType> > treenodetagQueries;
  81 vector<DocID> docidQueries;
  82
  83 uint acc = 0;
  84
  85 void runQueries(XMLTree * tree) {
  86   STATS1(Tag,treenodeQueries);
  87   STATS1(Parent,treenodeQueries);
  88   STATS1p(DocIds,treenodeQueries);
  89   STATS1(MyText,treenodeQueries);
  90   STATS1(PrevText,treenodeQueries);
  91   STATS1(NextText,treenodeQueries);
  92   STATS1(FirstChild,treenodeQueries);
  93   STATS1(NextSibling,treenodeQueries);
  94   STATS1(ParentNode,docidQueries);
  95   STATS1(PrevNode,treenodeQueries);
  96   STATS2(TaggedDesc,treenodetagQueries);
  97   STATS2(TaggedFoll,treenodetagQueries);
  98 }
  99
 100
 101 void fill_queries(XMLTree * tree, treeNode node,unsigned char* targettagname) {
 102   treeNode res1,res2;
 103   TagType tag;
 104   DocID id1,id2,id3;
 105   queue<treeNode> q;
 106   q.push(node);
 107   while(!q.empty()) {
 108     node = q.front();
 109     q.pop();
 110     if (node != NULLT) {
 111       tag = tree->Tag(node);
 112       if (target_tag == -1) {
 113         const unsigned char * tagname;
 114         tagname = tree->GetTagNameByRef(tag);
 115         if (strcmp( (char*) tagname, (char*) targettagname) == 0)
 116           target_tag = tag;
 117       }
 118       treenodeQueries.push_back(node);
 119       treenodetagQueries.push_back(pair<treeNode,TagType>(node,tag));
 120       id1 = tree->MyText(node);
 121       id2 = tree->PrevText(node);
 122       id3 = tree->NextText(node);
 123       id1 = max(id1, max(id2,id3));
 124       docidQueries.push_back(id1);
 125       res1 = tree->FirstChild(node);
 126       res2 = tree->NextSibling(node);
 127       q.push(res1);
 128       q.push(res2);
 129     }
 130   }
 131 }
 132
 133
 134 vector<treeNode> traversalQueries;
 135 uint cFullTraversal = 0;
 136
 137 void traversal_time(XMLTree * tree) {
 138   start_clock();
 139   uint q = 0;
 140   while(q<traversalQueries.size()) {
 141     treeNode node = traversalQueries[q];
 142     acc += tree->FirstChild(node);
 143     acc += tree->NextSibling(node);
 144     q++;
 145   }
 146   double t = 1000.0*stop_clock();
 147   printStats(t,"FullTraversal",traversalQueries.size());
 148 }
 149
 150
 151 unsigned int traversal(XMLTree *tree,treeNode node) {
 152   uint ret = 0;
 153   TagType tag;
 154   queue<treeNode> q;
 155   q.push(node);
 156   while(!q.empty()) {
 157     node = q.front();
 158     q.pop();
 159     if (node != NULLT) {
 160       cFullTraversal++;
 161       tag = tree->Tag(node);
 162       if (tag == target_tag)
 163         ret++;
 164                         treeNode t1 = tree->FirstChild(node);
 165       q.push(tree->FirstChild(node));
 166                         treeNode t2 = tree->NextSibling(node);
 167       q.push(tree->NextSibling(node));
 168                         if(t1!=NULLT)
 169       traversalQueries.push_back(t1);
 170                         if(t2!=NULLT)
 171       traversalQueries.push_back(t2);
 172     }
 173   }
 174   return ret;
 175 }
 176
 177
 178 vector<pair<treeNode,treeNode> > jumpQueries;
 179 uint cJumpTraversal = 0;
 180
 181 void jump_time(XMLTree * tree) {
 182   start_clock();
 183   uint q = 0;
 184   while(q<jumpQueries.size()) {
 185     treeNode node = jumpQueries[q].first;
 186     treeNode root = jumpQueries[q].second;
 187     acc += tree->TaggedDesc(node,target_tag);
 188     acc += tree->TaggedFollBelow(node,target_tag,root);
 189     q++;
 190   }
 191   double t = 1000.0*stop_clock();
 192   printStats(t,"JumpTraversal",jumpQueries.size());
 193 }
 194
 195
 196 /* This simulates the run function of the jumping automata*/
 197 unsigned int jump_traversal(XMLTree* tree, treeNode node,treeNode root) {
 198   uint ret = 0;
 199   TagType tag;
 200   queue<pair<treeNode,treeNode> > q;
 201   q.push(pair<treeNode,treeNode>(node,root));
 202   while(!q.empty()) {
 203     pair<treeNode,treeNode> p = q.front();
 204     q.pop();
 205     node = p.first;
 206     root = p.second;
 207     if (node != NULLT) {
 208       cJumpTraversal++;
 209       tag = tree->Tag(node);
 210       if (tag == target_tag)
 211         ret++;
 212       pair<treeNode,treeNode> p1(tree->TaggedDesc(node,target_tag),node);
 213       pair<treeNode,treeNode> p2(tree->TaggedFollBelow(node,target_tag,root),root);
 214                         if(p1.first!=NULLT)
 215               jumpQueries.push_back(p1);
 216                         if(p2.first!=NULLT)
 217               jumpQueries.push_back(p2);
 218       q.push(p1);
 219       q.push(p2);
 220     }
 221   }
 222   return ret;
 223 }
 224
 225
 226 int usage(char ** argv) {
 227   std::cout << "usage : " << argv[0] << " [-d] [-s] file.{xml,.srx} tagname\n";
 228   return 1;
 229 }
 230
 231
 232 int main(int argc, char ** argv) {
 233   unsigned int count1,count2;
 234   unsigned char * tagname;
 235   string arg,filename,ext;
 236   bool disable_tc = false;
 237   bool save = false;
 238   bool srx;
 239   XMLTree * tree;
 240
 241   int i = 1;
 242   if ( i >= argc)
 243     return usage(argv);
 244
 245   arg = argv[i];
 246   if (arg.compare("-d") == 0) {
 247     disable_tc = true;
 248     i++;
 249     if ( i >= argc)
 250       return usage(argv);
 251     arg = argv[i];
 252   }
 253
 254   if (arg.compare("-s") == 0) {
 255     save = true;
 256     i++;
 257     if ( i >= argc)
 258       return usage(argv);
 259     arg = argv[i];
 260   }
 261
 262   // The filename
 263   if (arg.size() < 4)
 264     return usage(argv);
 265
 266   ext=(arg.substr(arg.size()-4,4));
 267   if (ext.compare(".srx") == 0) {
 268     // must truncate
 269     filename = arg.substr(0,arg.size()-4);
 270     srx = true;
 271   }
 272   else if (ext.compare(".xml")==0) {
 273     filename = arg;
 274     srx = false;
 275   }
 276   else
 277     return usage(argv);
 278   i++;
 279
 280   if (i >= argc)
 281     return usage(argv);
 282
 283   tagname = (unsigned char*) argv[i];
 284
 285   if (srx)
 286     // The samplerate is not taken into account for loading anymore
 287     tree = XMLTree::Load((unsigned char*) filename.c_str(),64);
 288   else {
 289     try
 290     {
 291       //filename, sampling factor, index empty texts, disable tc
 292       XMLDocShredder shredder(filename.c_str(),64,false,disable_tc);
 293       shredder.processStartDocument("");
 294       shredder.parse();
 295       shredder.processEndDocument();
 296       tree = (XMLTree *) shredder.storageIfc_->returnDocument();
 297       if (save) {
 298         filename = filename.substr(0,filename.size()-4).append(".srx");
 299         struct stat stats;
 300         int exists = stat(filename.c_str(),&stats);
 301         if(exists == 0) {
 302           std::cout << "Warning : indexed file " << filename << " exists, not overwriting\n";
 303         }
 304         else {
 305           tree->Save((unsigned char*) filename.substr(0,filename.size()-4).c_str());
 306         }
 307
 308       }
 309     }
 310     catch (const std::exception& e) {
 311       cout << "Error during parsing : " << e.what() << "\n";
 312       return 2;
 313     }
 314   }
 315
 316   fill_queries(tree,tree->Root(),tagname);
 317   runQueries(tree);
 318
 319   if (target_tag == -1) {
 320     cout << "Warning:  tag " << tagname << " was not found in the document!\n"
 321       << "Warning:  not timing traversal and jumping functions\n";
 322     return 0;
 323   }
 324
 325   count1 = traversal(tree,tree->Root());
 326   count2 = jump_traversal(tree,tree->Root(),tree->Root());
 327
 328   cout << "Full traversal found " << count1 << " '" << tagname << "' nodes, "
 329     << cFullTraversal << " function calls." << endl;
 330   traversal_time(tree);
 331   cout << "Jump traversal found " << count2 << " '" << tagname << "' nodes, "
 332     << cJumpTraversal << " function calls." << endl;
 333   jump_time(tree);
 334
 335   return 0;
 336 }