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