parseHTML.cilk - pbrowser - Project Hosting on Google Code

‹r597

r625

Source path: svn/ trunk/ layout/ match/ parseHTML.cilk

//verbose
// #define DEBUGY

#ifdef DEBUGY
#define DEBUG 1
#else
#define DEBUG 0
#endif

//enable cilk
// #define CILKY

//enable problem statistics
// #define STATY

//enable PAPI
// #define PAPIFY

//enable TBB
#define TBBY

int MAX_WEIGHT = 0;


#ifdef CILKY
  # include <cilk.h>
  # include <reducer_opadd.h>
  # include <reducer_list.h>
#endif

#include "tbb/tick_count.h"  
using namespace tbb;


#ifdef TBBY
  # include "tbb/task_scheduler_init.h"
  # include "tbb/task.h"
  #include "tbb/blocked_range.h"
  #include "tbb/parallel_for.h"  
  #include "tbb/tick_count.h"
#endif

#ifdef PAPIFY
  #include <papi.h>
#endif

// MYSTERY INCLUDES FROM testHTML.c for libxml
#include "libxml.h"
#include <string.h>
#include <stdarg.h>
#ifdef HAVE_SYS_TYPES_H
#include <sys/types.h>
#endif
#ifdef HAVE_SYS_STAT_H
#include <sys/stat.h>
#endif
#ifdef HAVE_FCNTL_H
#include <fcntl.h>
#endif
#ifdef HAVE_UNISTD_H
#include <unistd.h>
#endif
#ifdef HAVE_STDLIB_H
#include <stdlib.h>
#endif
#include <libxml/xmlmemory.h>
#include <libxml/HTMLparser.h>
#include <libxml/HTMLtree.h>
#include <libxml/debugXML.h>
#include <libxml/xmlerror.h>
#include <libxml/globals.h>
#ifdef LIBXML_DEBUG_ENABLED
//static int debug = 0;
#endif
//static int copy = 0;
//static int noout = 0;
#ifdef LIBXML_PUSH_ENABLED
//static int push = 0;
#endif /* LIBXML_PUSH_ENABLED */
//static char *encoding = NULL;
static int options = 0;
//static int sax = 0;
//static int repeat = 0;

#include "parseHTML.h"

//CSS yacc parser
#include "selectors.h"
#include "css2.h"

#include <tr1/unordered_map>
#include <map>
#include <set>
#include <list>
#include <algorithm>

#include <stdio.h>
#include <iostream>

//timing
#include <sys/time.h>

//output
#include <sstream>

using namespace std;
#ifdef TBBY
  using namespace tbb;
#endif


#define RANDOMIZE

#define GRAIN_SIZE 1
int GRAIN_SIZETBB = 700;
//max rules per hashtable
int NUM_THREADS; 


typedef xmlChar xmlChar2;

//for mapping
class XMLComp {  
  public: bool operator()(const xmlChar2* s1, const xmlChar2* s2) const { return xmlStrcmp(s1, s2) < 0; }
};

class RuleSComp {
  public: bool operator()(const RuleSelector* s1, const RuleSelector* s2) const { return s1 < s2; }
};

class RuleSTokComp {
  public: bool operator()(const RuleSelectorTok* s1, const RuleSelectorTok* s2) const { return s1 < s2; }
};


class SelectorComp {
  public: bool operator()(const Selector* s1, const Selector* s2) const { return s1 < s2; }
};

class SelectorTokComp {
  public: bool operator()(const SelectorTok* s1, const SelectorTok* s2) const { return s1 < s2; }
};


class SelectorTokCompStrEq {
  //s1 < s2?
  public: bool operator()(const SelectorTok* s1, const SelectorTok* s2) const {    
    if (s2->selector.size() > s1->selector.size()) return true;
    if (s2->selector.size() < s1->selector.size()) return false;
    for (uint i = 0; i < s1->selector.size(); i++) {
      pair<COMBINATOR, SelectorPredicateTok> a = s1->selector[i];
      pair<COMBINATOR, SelectorPredicateTok> b = s2->selector[i];
      
      if (a.first != b.first) { return a.first < b.first; }
      if (a.second.tag != b.second.tag) { return a.second.tag < b.second.tag; }
      if (a.second.id != b.second.id) { return a.second.id < b.second.id; }
      if (a.second.classNames.size() != b.second.classNames.size()) {
        return a.second.classNames.size() < b.second.classNames.size();
      }
      for (uint n = 0; n < a.second.classNames.size(); n++) {
        if (a.second.classNames[n] != b.second.classNames[n]) {
          return a.second.classNames[n] < b.second.classNames[n];
        }
      }      
    }
    return false;
  }
};





template<class C>
class hyperwrapper {
  private:
    C *data;
  public:    
    hyperwrapper<C>() { 
      data = new C();
    }
    C &operator() () {
      return *data;
    }
};


  //make replacement wrapper for a list
  typedef hyperwrapper<list<RuleSelectorTok*> > MatchingRules;

//create a cilk and non-cilk hyperobject interface

typedef set<SelectorTok *, SelectorTokComp> CheckRange;

typedef pair<RuleSelectorTok*, CheckRange* > RTableRange;

  typedef hyperwrapper<multimap< int, RTableRange*> > RTableMap;

  typedef map<SelectorTok*, 
              set<RuleSelectorTok*, RuleSTokComp>*, 
              SelectorTokCompStrEq> SelRange;
  typedef map< int, SelRange*> RSelMap;


typedef vector<RTableMap*> RTableMapList;

typedef multimap<int, RTableRange*>::iterator RTableMapIterator;
typedef pair<int, RTableRange* > RTablePair;
typedef map<RuleSelectorTok *, vector<CheckRange *>*> CheckSet;



template<int n>
class SelectorTokPrefix {
  //s1 < s2?
  public: bool operator()(const SelectorTok* s1, const SelectorTok* s2) const {    
    if (s1->selector.size() < n && s2->selector.size() < n) {
      return false;
    } else if (s1->selector.size() < n) {
      return true;
    } else if (s2->selector.size() < n) {
      return false;
    } else {
      for (int i = 0; i < n; i++) {
        pair<COMBINATOR, SelectorPredicateTok> a = s1->selector[s1->selector.size() - 1 - i];
        pair<COMBINATOR, SelectorPredicateTok> b = s2->selector[s2->selector.size() - 1 - i];
        
        if (a.first != b.first) { return a.first < b.first; }
        if (a.second.tag != b.second.tag) { return a.second.tag < b.second.tag; }
        if (a.second.id != b.second.id) { return a.second.id < b.second.id; }
        if (a.second.classNames.size() != b.second.classNames.size()) {
          return a.second.classNames.size() < b.second.classNames.size();
        }
        for (uint j = 0; j < a.second.classNames.size(); j++) {
          if (a.second.classNames[j] != b.second.classNames[j]) {
            return a.second.classNames[j] < b.second.classNames[j];
          }
        }      
      }
      return false;
    }
  }
  
  //how many w/prefix size n
  public: static int nCount(set<SelectorTok*, SelectorTokPrefix<n> > *s) {
    int ret = 0;
    for (typename set<SelectorTok*, SelectorTokPrefix<n> >::iterator it  = s->begin();
         it != s->end(); ++it) {
      if ((*it)->selector.size() >= n) {
        ret++;   
      }
    }
    return ret;
  }

  
  //order by unique n-prefix + exact prefix for < n
  public: static set<SelectorTok*, SelectorTokPrefix<n> >* genNEquiv(SelRange* sr) {
    set<SelectorTok*, SelectorTokPrefix<n> >* equiv = new set<SelectorTok*, SelectorTokPrefix<n> >*();
    for (SelRange::iterator it = sr->begin(); it != sr->end(); ++it) {
      equiv->insert((*it).first);
    }
    return equiv;
  }
  
  public: static int nCountFilter(set<SelectorTok*, SelectorTokPrefix<n> > *sraw) {
    set<SelectorTok*, SelectorTokPrefix<n> > *s = genNEquiv(sraw);
    int ret = 0;
    for (typename set<SelectorTok*, SelectorTokPrefix<n> >::iterator it  = s->begin();
         it != s->end(); ++it) {
      if ((*it).first->selector.size() >= n) {
        ret++;   
      }
    }
    return ret;
  }
  
  public: static int sizeFilter (set<SelectorTok*, SelectorTokCompStrEq> *s) {
    int ret = 0;
    for (typename set<SelectorTok*, SelectorTokCompStrEq>::iterator it = s->begin(); it != s->end(); ++it) {
      if ((*it)->selector.size() >= n) ret++;
    }
    return ret;
  }
  
  
};


int countNodes (xmlNode *n) {
  int i = 0;
  if (n) {
      if (n->type == XML_ELEMENT_NODE) i++;
      
      xmlNode *cur_node = NULL;
      for (cur_node = n; cur_node; cur_node = cur_node->next) {       
        i += countNodes(cur_node->children);    
      }
  }
  return i;
}

int i = 0;
static void
print_element_names(xmlNode * a_node)
{
    xmlNode *cur_node = NULL;

    for (cur_node = a_node; cur_node; cur_node = cur_node->next) {       
            i++;
        if (cur_node->type == XML_ELEMENT_NODE) {
            cout << i << ". " << cur_node->name << endl;
            
            xmlAttr *attr_node = xmlHasProp(cur_node, xmlCharStrdup("class"));
            if (attr_node) {                 
                cout << "  classes: ";
                for (_xmlNode *c = attr_node->children; c; c = c->next) {
                  cout << " attr c n:[" << c->name << "], content:[" << c->content << "], type: " << (c->type == XML_TEXT_NODE) << endl;                
                }              
            }
        } else if (cur_node->name) {
//            cout << "[" << i << ", skip: " << cur_node->name << "]\n";
        } else {
//            cout << "[" << i << ", no name]\n";
        }

        print_element_names(cur_node->children);
    }
}


Doc::Doc (char *filename) {
    doc = htmlReadFile(filename, NULL, options);    
    if (doc == NULL) {
        cout << "Failed!" << endl;
        xmlGenericError(xmlGenericErrorContext, "Could not parse %s\n", filename);
    }      
}

Doc::~Doc () {
  if (doc) { 
    xmlFreeDoc(doc);
  }
}


//auxillary info predicates: convert strings etc. so that XMLLib can use them
class XMLLibSelectorPredicate {
  public:
    const xmlChar2 *xmlTag;
    const xmlChar2 *xmlID;
    vector<const xmlChar2*> xmlClassNames; //sorted
    SelectorPredicate *orig;
    XMLLibSelectorPredicate(SelectorPredicate *p) {
      xmlTag = p->tag != "" ? xmlCharStrdup(p->tag.c_str()) : NULL;
      xmlID = p->id != "" ? xmlCharStrdup(p->id.c_str()) : NULL; 
      
//      if (xmlTag) cout << "old tag: " << p->tag << ", wrapped tag: " << xmlTag << endl;
//      if (xmlID) cout << "old id: " << p->id << ", wrapped id: " << xmlID << endl;

      sort(p->classNames.begin(), p->classNames.end());
      for (vector<string>::iterator s = p->classNames.begin(); 
           s != p->classNames.end(); 
           ++s)  {
        xmlClassNames.push_back(xmlCharStrdup((*s).c_str()));
//        if (xmlCharStrdup((*s).c_str())) cout << "old class: " << *s << ", new class: " << xmlCharStrdup((*s).c_str()) << endl; 
      }
    }
    
    static void wrapPredicate (SelectorPredicate *p) {
      p->xmlData = (void*) new XMLLibSelectorPredicate(p);
    }
    
    static void wrapSelector (Selector *s) {
      for (vector<pair<COMBINATOR, SelectorPredicate*>*>::iterator p = s->selector.begin(); 
           p != s->selector.end(); 
           ++p)
           wrapPredicate((*p)->second);
    }
    
    static void wrapRules (vector<RuleSelector*> *rs) {
      for (vector<RuleSelector*>::iterator r = rs->begin(); r != rs->end(); ++r)
        for (vector<Selector*>::iterator s = (*r)->selectors.begin(); s != (*r)->selectors.end(); ++s)
          wrapSelector(*s);      
    }
    XMLLibSelectorPredicate *clone() {
      return new XMLLibSelectorPredicate(orig);
    }
    
};

//TODO check how it handles multiple spaces, e.g. "a     b"
void splitStr(string str, vector<string> *results) {

    string::size_type lastPos = str.find_first_not_of(" ", 0);
    string::size_type pos = str.find_first_of(" ", lastPos);

    while (string::npos != pos || string::npos != lastPos) {
        results->push_back(str.substr(lastPos, pos - lastPos));
        lastPos = str.find_first_not_of(" ", pos);
        pos = str.find_first_of(" ", lastPos);
    }

}



class WrappedXMLNode {
  public:
    vector<int> classNames;    
    int id;
    int tag;
    
    xmlNode *xml;
    vector<set<RuleSelectorTok*, RuleSTokComp>*> ruleSetsOverflow;
    set<RuleSelectorTok*, RuleSTokComp>* ruleSets[10];
    int nRules;
    set<RuleSelector*> rules;
    set<RuleSelectorTok*> rulesTok; //TODO remove
    vector<RuleSelectorTok*> rulesTokV; //TODO remove
    //MatchingRules unreducedRules;    
    //list<set<RuleSelectorTok*, RuleSTokComp>*> unreducedRules;

    static void inserter(WrappedXMLNode *xn, set<RuleSelectorTok*, RuleSTokComp>* s) {
      if (xn->nRules < 10) {
        xn->ruleSets[xn->nRules] = s;
        xn->nRules++;
      } else {
        xn->ruleSetsOverflow.push_back(s);
      }
    }

    int numChildren;
    vector <WrappedXMLNode*> children;
    WrappedXMLNode* parent;

    WrappedXMLNode (xmlNode *n, WrappedXMLNode *p, map<string, int> *lookup) {
      nRules = 0;
      xml = n;
      parent = p;
      xmlAttr *attr_node;

      //id      
      id = 0;
      attr_node = xmlHasProp(n, xmlCharStrdup("id"));
      if (attr_node) {
          for (_xmlNode *c = attr_node->children; c; c = c->next) {
              if (c->content) id = lookup->insert(pair<string, int>
                                                     ((const char*)xmlStrdup(c->content), 
                                                      lookup->size())).first->second;
          }                    
      }
      
      //split up class names 
      attr_node = xmlHasProp(n, xmlCharStrdup("class"));
      if (attr_node) {
          for (_xmlNode *c = attr_node->children; c; c = c->next) {          
              vector<string> cs; 
              string orig;
              const char * ee = (const char*) xmlStrdup(c->content);
              orig.assign(ee);
              splitStr(orig, &cs); 
              for (vector<string>::iterator s = cs.begin(); s != cs.end(); ++s) {
                  classNames.push_back(lookup->insert(pair<string, int>
                                                     (*s, lookup->size())).first->second);
              }
          }              
      } 
      sort(classNames.begin(), classNames.end());
      
      tag = !xml->name? 0 : lookup->insert(pair<string, int>
                              ((const char*) xmlStrdup(xml->name), 
                               lookup->size())).first->second;
                               
      numChildren = 0;      
      //recur and count children
      for (xmlNode *c = n->children; c; c = c->next) {         
          WrappedXMLNode *child = new WrappedXMLNode(c, this, lookup);
          children.push_back(child);
          numChildren += 1 + child->numChildren;
      }
      
    }
};

int flattenPage(WrappedXMLNode *r, WrappedXMLNode **pageFlat, int i) {
  int next = i;
  if (r->xml->type == XML_ELEMENT_NODE) {

    pageFlat[i] = r;
    next++;
  }  
  for (vector<WrappedXMLNode*>::iterator it = r->children.begin(); it != r->children.end(); ++it) {
    next = flattenPage(*it, pageFlat, next);    
  }
  return next;  
}




static bool matchNodePredicate(WrappedXMLNode *n, SelectorPredicateTok* p) {
  if (p->tag > 0) {
    if (n->tag != p->tag) { return false; }    
  }
  
  if (p->id > 0) {
    if (n->id != p->id) { return false; }
  }
  
  for (vector<int>::iterator pc = p->classNames.begin();  pc != p->classNames.end();  ++pc) {
    bool found = false;
    int pci = *pc;
    for (vector<int>::iterator nc = n->classNames.begin();
         !found && nc != n->classNames.end(); 
         ++nc) {
      if (pci == *nc) {
        found = true;
      }
    }

    if (!found) {
      return false;
    }
  }
    
  return true;
}

int potential = 0;
int potential1len = 0;
int potential2len = 0;
int potential3len = 0;
int potentialmorelen = 0;

int instant = 0;
int instant2 = 0;
int instant3 = 0;
int restNum = 0;
int restLen = 0;

static bool matchNodeSelector (WrappedXMLNode *xn, SelectorTok *s) {

  #ifdef STATY
  potential++;
  if (s->selector.size() == 1) potential1len++;
  else if (s->selector.size() == 2) potential2len++;
  else if (s->selector.size() == 3) potential3len++;
  else if (s->selector.size() == 0) { cout << "empty selector!!" << endl; }
  else potentialmorelen++;
  int advanced = 0;
  #endif


  bool first = true; 
  WrappedXMLNode *cur = xn;
  vector<pair<COMBINATOR, SelectorPredicateTok> >::iterator p = s->selector.begin();
  do {
//    cout << "Try a predicate." << endl;     
    if (cur) {
      bool p_hit;
      if (first) {
          first = false;
          #ifdef STATY
          advanced++;
          #endif
          p_hit = matchNodePredicate(cur, &((*p).second));
          if (!p_hit) { 
            break; 
          }
          return (s->selector.size() == 2);

      } else if ((*p).first == DESCENDANT) {
          /* walk up until a hit or end */
          for (p_hit = false; (!p_hit) && cur; cur = cur->parent) {
            p_hit = matchNodePredicate(cur, &((*p).second));
            #ifdef STATY
            advanced++;
            #endif
          }
          if (!p_hit) { 
            break; 
          }
      } else {
        #ifdef STATY
        advanced++;
        #endif
        //cout << "UNHANDLED css command: " << (*p)->first << endl;
        break;
       //exit(1);
      }
    }

    ++p;
    if (cur) {
      if(cur->parent) cur = cur->parent;
    } else break;
  } while ( (p != s->selector.end()) );
  
  #ifdef STATY
  if (advanced == 1) instant++; 
  else if (advanced == 2) instant2++; 
  else if (advanced == 3) instant3++; 
  else {
    restNum++;
    restLen+=advanced;
  }
  #endif
  
  return p == s->selector.end();
}


// a b > c d > e f
#ifdef CILKY
  cilk::hyperobject<cilk::reducer_opadd<int> > nhits;
  cilk::hyperobject<cilk::reducer_opadd<int> > nihits;
#else
  int nhits = 0;
  int nihits = 0;
#endif

static void matchNodesNaive(WrappedXMLNode * xn, vector<RuleSelectorTok*> *rs)
{
    //match
    if (xn->xml->type == XML_ELEMENT_NODE) {
    
        for (vector<RuleSelectorTok*>::iterator r = rs->begin(); r != rs->end(); ++r) {
          bool hit = false;
          for (vector<SelectorTok>::iterator s = (*r)->selectors.begin(); 
               !hit && s != (*r)->selectors.end(); 
               ++s) {
              
            hit = matchNodeSelector(xn, &*s);
          }
          if (hit) {
            xn->rules.insert((*r)->rs);
          }
        }
    }
    
    //recur
    for (vector<WrappedXMLNode*>::iterator c = xn->children.begin(); 
         c != xn->children.end(); 
         ++c) {
      if ((*c)->xml->type == XML_ELEMENT_NODE) matchNodesNaive(*c, rs);
    }

}


// a b > c d > e f
static void matchNodesNaiveCilk(WrappedXMLNode * xn, vector<RuleSelectorTok*> *rs)
{

  //recur
  if (xn->numChildren > MAX_WEIGHT) {
      int s = xn->children.size();
      #ifdef CILKY
        #pragma cilk_grainsize = GRAIN_SIZE
        cilk_for (int i = 0; i < s; i++) {
      #else
        for (int i = 0; i < s; i++) {
      #endif
          if (xn->children.at(i)->xml->type == XML_ELEMENT_NODE) matchNodesNaiveCilk(xn->children.at(i), rs);
        }  
  } else {
      for (vector<WrappedXMLNode*>::iterator c = xn->children.begin(); 
         c != xn->children.end(); 
         ++c) {
         if ((*c)->xml->type == XML_ELEMENT_NODE) matchNodesNaive( *c, rs);
      }  
  }



    //match
    if (xn->xml->type == XML_ELEMENT_NODE) {
        for (vector<RuleSelectorTok*>::iterator r = rs->begin(); r != rs->end(); ++r) {
    
          bool hit = false;
          for (vector<SelectorTok>::iterator s = (*r)->selectors.begin(); 
               !hit && s != (*r)->selectors.end(); 
               ++s) {
     
              hit = matchNodeSelector(xn, &*s);       
          }
          if (hit) {
            xn->rules.insert((*r)->rs);
          }
          
    
        }
    }

}

static void selHashAdd(RSelMap* hash, RuleSelectorTok *r, SelectorTok* s, int idx) {
            RSelMap::iterator rowIt = hash->find(idx);
            SelRange *row;
            if (rowIt == hash->end()) {
              row =  new SelRange();
              hash->insert(pair<int, SelRange*>(idx, row));
            } else {
              row = (*rowIt).second;
            }
            SelRange::iterator equivIt = row->find(s);
            set<RuleSelectorTok*, RuleSTokComp> *equiv;
            if (equivIt == row->end()) {
              equiv = new set<RuleSelectorTok*, RuleSTokComp>();
              row->insert(pair<SelectorTok*, set<RuleSelectorTok*, RuleSTokComp>*>(s, equiv));
            } else { 
              equiv = (*equivIt).second; 
            }
            equiv->insert(r); 
}

static vector<RSelMap*>* genSelHash(vector<RuleSelectorTok*> *rules) {
  vector<RSelMap*>* results = new vector<RSelMap*>();
  RSelMap *tagMap = new RSelMap();  
  RSelMap *idMap = new RSelMap();  
  RSelMap *classMap = new RSelMap();  
  
  results->push_back(tagMap);
  results->push_back(idMap);
  results->push_back(classMap);  

    for (size_t sz = 0; sz < rules->size(); sz++) {
      RuleSelectorTok *r = rules->at(sz);
      for (vector<SelectorTok>::iterator s = r->selectors.begin(); 
           s != r->selectors.end(); 
           ++s) {
          
          //aliases
          pair<COMBINATOR, SelectorPredicateTok> p = (*s).selector[0];
          int idx;

          bool added = false;

          //by id
          idx = p.second.id;
          if (idx > 0) {
            selHashAdd(idMap, r, &*s, idx);
            added = true;
          } 

          //by first class
          if (!added) {
            if (  p.second.classNames.size() > 0) {
              idx = p.second.classNames[0];
              selHashAdd(classMap, r, &*s, idx);
              added = true;
            }
          }

          //by tag
          if (!added) {
            idx = p.second.tag;
            if (idx == 0) { //TODO 
              #ifdef DEBUGY
                cout << " Malformed selector!\n"; 
              #endif
              continue; 
            }
            selHashAdd(tagMap, r, &*s, idx);
          }
      }
  }
  return results;
}


//three hash entries: tag, lowest class, id
static vector<RTableMap*>* genHash(vector<RuleSelectorTok*> *rules) {

  vector<RTableMap*>* results = new vector<RTableMap*>();
  RTableMap *tagMap = new RTableMap();  
  RTableMap *idMap = new RTableMap();  
  RTableMap *classMap = new RTableMap();  
  
  results->push_back(tagMap);
  results->push_back(idMap);
  results->push_back(classMap);  

  //TODO is this a useful distinction?
    for (vector<RuleSelectorTok*>::iterator rr = rules->begin(); rr != rules->end(); ++rr) {
      RuleSelectorTok* r = *rr;
      for (vector<SelectorTok>::iterator s = r->selectors.begin(); 
           s != r->selectors.end(); 
           ++s) {
          
          //TODO cleanup, made these bags for an earlier, incorrect optimization
          RTableRange *tagRow = NULL;
          RTableRange *idRow = NULL; 
          RTableRange *classRow = NULL; 


          pair<COMBINATOR, SelectorPredicateTok> p = (*s).selector[0];

          //aliases
          int idx;

          bool added = false;

          //by id
          idx = p.second.id;
          if (idx > 0) {
            if (!idRow) {
              idRow = new RTableRange(r, new CheckRange());
              (*idMap)().insert(RTablePair(idx, idRow));
            }
            idRow->second->insert(&*s);
            added = true;
            
          }


          if (!added) {
            //by first class
            if (  p.second.classNames.size() > 0) {
              idx = p.second.classNames[0];
              if (!classRow) {
                classRow = new RTableRange(r, new CheckRange());
                (*classMap)().insert(RTablePair(idx, classRow));
              }
              classRow->second->insert(&*s);
              added = true;
            }
          }

          if (!added) {
            //by tag
            idx = p.second.tag;
              
            if (idx == 0) { 
              #ifdef DEBUGY
                cout << " Malformed selector!\n"; 
              #endif
              continue; 
            }

            if (!tagRow) {
              tagRow = new RTableRange(r, new CheckRange());
              (*tagMap)().insert(RTablePair(idx, tagRow));

            }             
            
            tagRow->second->insert(&*s);
          }
          
//          cout << "Added: " << idx << endl;
          
      }
  }
  
  return results;
}




static bool matchNodeSelectors (WrappedXMLNode *xn, pair<RuleSelectorTok *,  CheckRange *> *pr) {
  CheckRange *ss = pr->second;
  for (CheckRange::iterator s = ss->begin(); 
       s != ss->end(); 
       ++s) {
      if ( matchNodeSelector(xn, *s) ) { return true; }      
  }
  return false;
}




int matchedRules = 0;


int dupeSelCount = 0;
int nSel2 = 0;
int nSel3 = 0;
int nSel4 = 0;
int nSel5 = 0;

int unSel2 = 0;
int unSel3 = 0;
int unSel4 = 0;
int unSel5 = 0;

//single node
static void matchNodeHashed(WrappedXMLNode * xn, 
                             RTableMap *tagMap,
                             RTableMap *idMap,
                             RTableMap *classMap) {

    //TODO debug repeat hits
    //option: allow multiply hitting rules; use set datastructure to cull out repeats

    pair<RTableMapIterator,RTableMapIterator> sub;
    RTableMapIterator subIt;
        
    CheckSet possibilities;

    //if (xn->xml && xn->xml->type == XML_ELEMENT_NODE) {
    
        //by tag
        if (xn->tag > 0) {
          sub = (*tagMap)().equal_range(xn->tag);
          for (RTableMapIterator pr = sub.first; pr != sub.second; ++pr) {
            RuleSelectorTok *idx = (*pr).second->first;
            vector<CheckRange*> *dest = new vector<CheckRange*>();
            possibilities.insert(pair<RuleSelectorTok *, vector<CheckRange *>*>(idx, dest));
            dest->push_back( (*pr).second->second );
          } 
        } else {
          exit(1); //shouldn't be checking here...
        }

        //by id
        if (xn->id > 0) {
          sub = (*idMap)().equal_range(xn->id);
          for (RTableMapIterator pr = sub.first; pr != sub.second; ++pr) {
            RuleSelectorTok *idx = (*pr).second->first;
            vector<CheckRange*> *dest;
            CheckSet::iterator row = possibilities.find(idx);
            if (row == possibilities.end()) {
              dest = new vector<CheckRange*>();
              possibilities.insert(pair<RuleSelectorTok *, vector<CheckRange *>*>(idx, dest));
            } else {
              dest = row->second;              
            }           
            dest->push_back( (*pr).second->second );             
          } 
        } 

        //by class
        for (vector<int>::iterator c = xn->classNames.begin(); 
             c != xn->classNames.end(); 
             ++c) {
          sub = (*classMap)().equal_range(*c);          
          for (RTableMapIterator pr = sub.first; pr != sub.second; ++pr) {
            RuleSelectorTok *idx = (*pr).second->first;
            vector<CheckRange*> *dest;
            CheckSet::iterator row = possibilities.find(idx);
            if (row == possibilities.end()) {
              dest = new vector<CheckRange*>();
              possibilities.insert(pair<RuleSelectorTok *, vector<CheckRange *>*>(idx, dest));
            } else {
              dest = row->second;              
            }           
            dest->push_back( (*pr).second->second );                        
          }
        }
        
        
        multimap<SelectorTok*,  RuleSelectorTok*, SelectorTokCompStrEq> hits;
        #ifdef STATY        
        set<SelectorTok*, SelectorTokCompStrEq> hitKeys;
        set<SelectorTok*, SelectorPrefix<2> > * checkN2 = new set<SelectorTok*, SelectorPrefix<2> >();
        set<SelectorTok*, SelectorPrefix<3> > * checkN3 = new set<SelectorTok*, SelectorPrefix<3> >();
        set<SelectorTok*, SelectorPrefix<4> > * checkN4 = new set<SelectorTok*, SelectorPrefix<4> >();
        set<SelectorTok*, SelectorPrefix<5> > * checkN5 = new set<SelectorTok*, SelectorPrefix<5> >();        
        #endif

        //try all of them
        for (CheckSet::iterator prs = possibilities.begin(); prs != possibilities.end(); ++prs) {
            bool ruleHit = false;
            for (vector<CheckRange *>::iterator pr = (*prs).second->begin();
                 !ruleHit && pr != (*prs).second->end();
                 ++pr) {
              ruleHit = matchNodeSelectors(xn, new pair<RuleSelectorTok*,CheckRange*>((*prs).first,*pr));

              for (CheckRange::iterator hit = (*pr)->begin();
                hit != (*pr)->end(); ++hit) {
                  hits.insert(pair<SelectorTok*, RuleSelectorTok*>(*hit,(*prs).first));
                  #ifdef STATY
                  hitKeys.insert(*hit);
                  checkN2->insert(*hit);
                  checkN3->insert(*hit);
                  checkN4->insert(*hit);
                  checkN5->insert(*hit);
                  #endif
              }

              if (ruleHit) {
                xn->rules.insert( (*prs).first->rs);
                matchedRules++;
                break;
              }
            }
        }
        
        #ifdef STATY
        //count n prefices
        unSel2 += SelectorPrefix<2>::nCount(checkN2);
        unSel3 += SelectorPrefix<3>::nCount(checkN3);
        unSel4 += SelectorPrefix<4>::nCount(checkN4);
        unSel5 += SelectorPrefix<5>::nCount(checkN5);
        #endif
        
        #ifdef STATY
        nSel2 += SelectorPrefix<2>::sizeFilter(&hitKeys);
        nSel3 += SelectorPrefix<3>::sizeFilter(&hitKeys);
        nSel4 += SelectorPrefix<4>::sizeFilter(&hitKeys);
        nSel5 += SelectorPrefix<5>::sizeFilter(&hitKeys);
        #endif
        
        //count dupe selectors
        #ifdef STATY
        for (set<SelectorTok*, SelectorTokCompStrEq>::iterator k = hitKeys.begin();
           k != hitKeys.end(); ++k) {
             pair<multimap<SelectorTok*,  RuleSelectorTok*>::iterator,multimap<SelectorTok*,  RuleSelectorTok*>::iterator> ret;
             ret = hits.equal_range(*k);
             multimap<SelectorTok*,  RuleSelectorTok*>::iterator it;
             
             for (it = ret.first; it != ret.second; ++it) {
               dupeSelCount++;
             }
             dupeSelCount--;
        }
        #endif


    //}      
}                             

int nodes = 0;
static void matchNodesHashed(WrappedXMLNode * xn, 
                             RTableMap *tagMap,
                             RTableMap *idMap,
                             RTableMap *classMap) {

    //work
    matchNodeHashed(xn, tagMap, idMap, classMap);
    nodes++;
    
    //recur
    for (vector<WrappedXMLNode*>::iterator c = xn->children.begin(); 
         c != xn->children.end(); 
         ++c) {
      if ((*c)->xml->type == XML_ELEMENT_NODE) matchNodesHashed(*c, tagMap, idMap, classMap);
    }

}


static void matchNodesHashedCilk(WrappedXMLNode * xn, 
                             RTableMap *tagMap,
                             RTableMap *idMap,
                             RTableMap *classMap) {

    //recur
    if (xn->numChildren > MAX_WEIGHT) {
      int sz = xn->children.size();
      #ifdef CILKY
        #pragma cilk_grainsize = GRAIN_SIZE
        cilk_for (int i = 0; i < sz; i++) {
      #else
        for (int i = 0; i < sz; i++) {
      #endif
          if (xn->children.at(i)->xml->type == XML_ELEMENT_NODE) matchNodesHashedCilk(xn->children.at(i), tagMap, idMap, classMap);
        }      
    } else {
      for (vector<WrappedXMLNode*>::iterator c = xn->children.begin(); 
         c != xn->children.end(); 
         ++c) {
        if ((*c)->xml->type == XML_ELEMENT_NODE) matchNodesHashed(*c, tagMap, idMap, classMap);
      }
    }

    //work
    matchNodeHashed(xn, tagMap, idMap, classMap);

} 

/*  typedef map<Selector*, 
              set < RuleSelector*, RuleSComp >*, 
              SelectorTokCompStrEq> SelRange;
  typedef map< const xmlChar2*, SelRange*, XMLComp> RSelMap;
*/
static void splitSelAttempt (WrappedXMLNode *xn, int idx, RSelMap *hash) {
  RSelMap::iterator it = hash->find(idx);
  if (it != hash->end()) {
    for (SelRange::iterator possibility = (*it).second->begin(); 
         possibility != (*it).second->end(); 
         ++possibility ) {
      if (matchNodeSelector(xn, (*possibility).first)) {
        WrappedXMLNode::inserter(xn, (*possibility).second);
        /*for (set<RuleSelectorTok*, RuleSTokComp>::iterator en = (*possibility).second->begin();
             en != (*possibility).second->end(); ++en) {
          xn->rules.insert((*en)->rs);
        }*/
      }
    }
  }  
}






static void splitAttempt (WrappedXMLNode *xn, int idx, RTableMap *hash) {
  pair<RTableMapIterator,RTableMapIterator> possibilities = (*hash)().equal_range( idx );

  for (RTableMapIterator rulePossibility = possibilities.first;
       rulePossibility != possibilities.second;
       ++rulePossibility) {

    //only follow selector for a rule if previous hashtable didn't have a selector to match it
    //faster to let 'set' data structure worry about it, as well as local hash reasoning
//    if (xn->rules.end() == xn->rules.find( (*rulePossibility).second->first)) {
      bool hit = false;
      
      for (set<SelectorTok*>::iterator s = (*rulePossibility).second->second->begin(); 
         s != (*rulePossibility).second->second->end(); 
         ++s) {           
          if (matchNodeSelector(xn, *s)) {
            hit = true;
            break;
          }
      }
      if (hit) {
        xn->rules.insert( (*rulePossibility).second->first->rs );
//        cout << "Matched. " << endl; 
      }
      //(update hit counts later all together)
  //  }
  }
}


//three passes: compute based on Tag, then ID, then Class
static void matchNodesSplitIDCilk(WrappedXMLNode *xn, RTableMap *hash) {

  //recur
  int sz = xn->children.size();
  #ifdef CILKY
    #pragma cilk_grainsize = GRAIN_SIZE
    cilk_for (int i = 0; i < sz; i++) {
  #else
    for (int i = 0; i < sz; i++) {
  #endif
      if (xn->children[i]->xml->type == XML_ELEMENT_NODE) matchNodesSplitIDCilk(xn->children[i], hash);
    }      

  //work
  if (xn->id) {  splitAttempt(xn, xn->id, hash); }
}



//three passes: compute based on Tag, then ID, then Class
 void matchNodesSplitSelID(WrappedXMLNode *xn, RSelMap *hash) {

  //recur
  int sz = xn->children.size();
    for (int i = 0; i < sz; i++) {
      if (xn->children[i]->xml->type == XML_ELEMENT_NODE) matchNodesSplitSelID(xn->children[i], hash);
    }      

  //work
  if (xn->id) {  splitSelAttempt(xn, xn->id, hash); }
}


//three passes: compute based on Tag, then ID, then Class
 void matchNodesSplitSelIDCilk(WrappedXMLNode *xn, RSelMap *hash) {
 
 
   #ifdef CILKY
  if (xn->numChildren < MAX_WEIGHT) { 
    matchNodesSplitSelID(xn, hash);
    return;
  }
  #endif


  //recur
  int sz = xn->children.size();
    for (int i = 0; i < sz; i++) {
      if (xn->children[i]->xml->type == XML_ELEMENT_NODE) 
        #ifdef CILKY
        cilk_spawn
        #endif
        matchNodesSplitSelIDCilk(xn->children[i], hash);
    }      

  //work
  if (xn->id) {  splitSelAttempt(xn, xn->id, hash); }
}


//three passes: compute based on Tag, then ID, then Class
static void matchNodesSplitTagCilk(WrappedXMLNode *xn, RTableMap *hash) {

  //recur
  int sz = xn->children.size();
  #ifdef CILKY
    #pragma cilk_grainsize = GRAIN_SIZE
    cilk_for (int i = 0; i < sz; i++) {
  #else
    for (int i = 0; i < sz; i++) {
  #endif
      if (xn->children[i]->xml->type == XML_ELEMENT_NODE) matchNodesSplitTagCilk(xn->children[i], hash);
    }      

  //work
  if (xn->tag > 0) { splitAttempt(xn, xn->tag, hash); }
}

//three passes: compute based on Tag, then ID, then Class
 void matchNodesSplitSelTag( WrappedXMLNode *xn, RSelMap *hash) {

  //recur
  int sz = xn->children.size();
    for (int i = 0; i < sz; i++) {
      if (xn->children[i]->xml->type == XML_ELEMENT_NODE) matchNodesSplitSelTag(xn->children[i], hash);
    }      

  //work
  if (xn->tag > 0) { splitSelAttempt(xn, xn->tag, hash); }
}



//three passes: compute based on Tag, then ID, then Class
 void matchNodesSplitSelTagCilk( WrappedXMLNode *xn, RSelMap *hash) {

  #ifdef CILKY
  if (xn->numChildren < MAX_WEIGHT) { 
    matchNodesSplitSelTag(xn, hash);
    return;
  }
  #endif


  //recur
  int sz = xn->children.size();
    for (int i = 0; i < sz; i++) {
      if (xn->children[i]->xml->type == XML_ELEMENT_NODE) 
        #ifdef CILKY
        cilk_spawn
        #endif
        matchNodesSplitSelTagCilk(xn->children[i], hash);
    }      

  //work
  if (xn->tag > 0) { splitSelAttempt(xn, xn->tag, hash); }
}



//three passes: compute based on Tag, then ID, then Class
static void matchNodesSplitClassCilk(WrappedXMLNode *xn, RTableMap *hash) {

  //recur
  int sz = xn->children.size();
  #ifdef CILKY
    #pragma cilk_grainsize = GRAIN_SIZE
    cilk_for (int i = 0; i < sz; i++) {
  #else
    for (int i = 0; i < sz; i++) {
  #endif
      if (xn->children[i]->xml->type == XML_ELEMENT_NODE) matchNodesSplitClassCilk(xn->children[i], hash);
    }      

  //work
  //do sequentially to avoid any locking considerations if there is a hit on this node
  for (vector<int>::iterator c = xn->classNames.begin(); 
       c != xn->classNames.end(); 
       ++c) {             
    splitAttempt(xn, *c, hash);
  }
}


//three passes: compute based on Tag, then ID, then Class
 void matchNodesSplitSelClass(WrappedXMLNode *xn, RSelMap *hash) {

  //recur
  int sz = xn->children.size();
    for (int i = 0; i < sz; i++) {
      if (xn->children[i]->xml->type == XML_ELEMENT_NODE) matchNodesSplitSelClass(xn->children[i], hash);
    }      

  //work
  //do sequentially to avoid any locking considerations if there is a hit on this node
  for (vector<int>::iterator c = xn->classNames.begin(); 
       c != xn->classNames.end(); 
       ++c) {             
    splitSelAttempt(xn, *c, hash);
  }
}



//three passes: compute based on Tag, then ID, then Class
 void matchNodesSplitSelClassCilk(WrappedXMLNode *xn, RSelMap *hash) {

  #ifdef CILKY
  if (xn->numChildren < MAX_WEIGHT) { 
    matchNodesSplitSelClass(xn, hash);
    return;
  }
  #endif

  //recur
  int sz = xn->children.size();
    for (int i = 0; i < sz; i++) {
      if (xn->children[i]->xml->type == XML_ELEMENT_NODE) 
        #ifdef CILKY
        cilk_spawn
        #endif
        matchNodesSplitSelClassCilk(xn->children[i], hash);
    }      

  //work
  //do sequentially to avoid any locking considerations if there is a hit on this node
  for (vector<int>::iterator c = xn->classNames.begin(); 
       c != xn->classNames.end(); 
       ++c) {             
    splitSelAttempt(xn, *c, hash);
  }
}


//================================= TBB ===================================
//TODO need to bottom out on nodes that are not XML ones (not doing so, at a minimum, might skew benchmarks due to caches)

//three passes: compute based on Tag, then ID, then Class
#ifdef TBBY


void workClass (WrappedXMLNode *xn, RSelMap *hash) {
	for (vector<int>::iterator c = xn->classNames.begin(); 
		 c != xn->classNames.end(); 
		 ++c) {             
	  splitSelAttempt(xn, *c, hash);
	}
}        
void workTag (WrappedXMLNode *xn, RSelMap *hash) {
    if (xn->tag > 0) { splitSelAttempt(xn, xn->tag, hash); }
}        
void workID (WrappedXMLNode *xn, RSelMap *hash) {
    if (xn->id) {  splitSelAttempt(xn, xn->id, hash); }
}

template<void (*work)(WrappedXMLNode *xn, RSelMap *hash)>
class MatchRange {
  public:
    RSelMap *hash;
    WrappedXMLNode **flatPage;
    
    MatchRange(WrappedXMLNode **flatPage_, RSelMap *hash_) : hash(hash_), flatPage(flatPage_)  { }
    
    void operator()( const tbb::blocked_range<size_t>& range) const {
            
      size_t d = range.end();
      for (size_t j = range.begin(); j < d; j++) {
          work(flatPage[d], hash);
      }
    }
};    




template<void (*work)(WrappedXMLNode *xn, RSelMap *hash),
         void (*bottom)(WrappedXMLNode *xn, RSelMap *hash)>
class IndTree : public task {

  public:
    WrappedXMLNode *xn;
    RSelMap *hash;
    
    IndTree<work, bottom>(WrappedXMLNode *xn_, RSelMap *hash_) : 
      xn(xn_), hash(hash_) { }


    task* execute() {  // Overrides virtual function 
      task *ret = NULL;
   
      if (xn->numChildren < MAX_WEIGHT) { 
          bottom(xn, hash);
      } else { 
      
        empty_task& cont = *new( this->allocate_continuation() ) empty_task;        
      
        int sz = xn->children.size();
        cont.set_ref_count(1 + sz - 1); //this + children - continuation

        //note: recycle first task
        if (sz > 0) { 
          ret = this; 
        
          //MatchNodesSplitSelClassTbbTask& tasks[sz];
          //non-recycled        
          for (int i = 1; i < sz; i++) {
            //tasks[i] = 
            cont.spawn(
              *new( cont.allocate_child() ) IndTree<work, bottom>(xn->children[i], hash)//;
            );
          }
          //for (int i = 1; i < sz; i++) { spawn(tasks[i]);  }          
        }
  
        //work on this node
        work(xn, hash);

        recycle_as_child_of(cont);
        xn = xn->children[0];
      }
     
      return ret; 
    } 

};


//sequentially run small children
template<void (*work)(WrappedXMLNode *xn, RSelMap *hash),
         void (*bottom)(WrappedXMLNode *xn, RSelMap *hash)>
class IndTreeSparse : public task {


  public:
    WrappedXMLNode *xn;
    RSelMap *hash;
    
    IndTreeSparse<work, bottom>(WrappedXMLNode *xn_, RSelMap *hash_) : 
      xn(xn_), hash(hash_) { }


    task* execute() {  // Overrides virtual function 
      task *ret = NULL;
   
      if (xn->numChildren <= MAX_WEIGHT) { 
          bottom(xn, hash);
      } else { 
        int sz = xn->children.size();
        int numToSpawn = 0;
        int hd = -1;
        for (int i = sz - 1; i >= 0; i--) {
          if (xn->children[i]->numChildren > MAX_WEIGHT) {
            numToSpawn++;
            hd = i;
          }
        }
        if (numToSpawn == 0) {
          bottom(xn, hash);
        } else  {
          
          empty_task& cont = *new( this->allocate_continuation() ) empty_task;        
      
          cont.set_ref_count(1 + numToSpawn - 1); //this + children - continuation

          //note: recycle first task
          ret = this; 
        
          //non-recycled
          //if only 1 child, hopefully cost of directly reusing task is cheap
          int hits = 0;
          for (int i = hd + 1; i < sz; i++) {
             WrappedXMLNode *c = xn->children[i];
             if (c->numChildren > MAX_WEIGHT) {
               cont.spawn(*new( cont.allocate_child() ) IndTreeSparse<work, bottom>(xn->children[i], hash));
               hits++;
               if (hits == numToSpawn) { break; }
             }
          }
  
          //work on this node
          work(xn, hash);
          
          //work on small children
          if (numToSpawn != sz) {
			//work on small children
			for (int i = 0; i < sz; i++) {
			  WrappedXMLNode *c = xn->children[i];
			  if (c->numChildren <= MAX_WEIGHT) {
			    bottom(c, hash);
			  }
			}
          }
          
          ret = this;
          recycle_as_child_of(cont);
          xn = xn->children[hd];
        }
      } 
      return ret; 
    } 

};





//basic forking task structure
template<void (*work)(WrappedXMLNode *xn, RSelMap *hash),
         void (*bottom)(WrappedXMLNode *xn, RSelMap *hash)>
class IndTreeNaive : public task {

  public:
    WrappedXMLNode *xn;
    RSelMap *hash;
    
    IndTreeNaive<work, bottom>(WrappedXMLNode *xn_, RSelMap *hash_) : 
      xn(xn_), hash(hash_) { }


    task* execute() {  // Overrides virtual function 
      task *ret = NULL;
   
      if (xn->numChildren <= MAX_WEIGHT) { 
          bottom(xn, hash);
      } else { 
 
        int sz = xn->children.size();
        set_ref_count(1 + sz); //this + children

        for (int i = 1; i < sz; i++) {
          //tasks[i] = 
          spawn(
            *new( allocate_child() ) IndTreeNaive<work, bottom>(xn->children[i], hash)//;
          );
        }
        
        if (sz >= 1) {
            IndTreeNaive &first = *new( allocate_child() ) IndTreeNaive<work, bottom>(xn->children[0], hash);
            spawn_and_wait_for_all(first);
        }
        
        //work on this node
        work(xn, hash);
      }
     
      return ret;
    }
           
};
#endif



//add to nihits
//clear out matched rules after counted
static void calcHits(WrappedXMLNode *xn) {
     
    
     int sz = xn->children.size();
     #ifdef CILKY
     #pragma cilk_grainsize = GRAIN_SIZE
     cilk_for (int i = 0; i < sz; i++) {
     #else
     for (int i = 0; i < sz; i++) {
     #endif
       calcHits(xn->children[i]);
     }          

     int s = xn->rules.size();
     if (s > 0) {     
       #ifdef CILKY
        nhits() ++;
        nihits() += s;
      #else
        nhits ++;
        nihits += s;
      #endif
     }
     
     xn->rules.clear();
     //xn->unreducedRules.clear();

}

static void matchNodesSplitHashedCilk(WrappedXMLNode *xn, vector<RTableMap *> *hashes) {
                             
//    if (xn->xml && xn->xml->type == XML_ELEMENT_NODE) {
      //id 1
      //cout << "id" << endl;
      matchNodesSplitIDCilk(xn, (*hashes)[1]);

      //class 2
      //cout << "class" << endl;
      //shouldn't be first as have to do checks anyways
      matchNodesSplitClassCilk(xn, (*hashes)[2]);
      
      
      //tag 0
      //cout << "tag" << endl;
      matchNodesSplitTagCilk(xn, (*hashes)[0]);
  //  }
}    




static void matchNodesSplitSelHashedCilk(WrappedXMLNode *xn, vector<RSelMap*> *hashes) {
                             
//    if (xn->xml && xn->xml->type == XML_ELEMENT_NODE) {
      //id 1
      //cout << "id" << endl;
      matchNodesSplitSelIDCilk(xn, (*hashes)[1]);

      //class 2
      //cout << "class" << endl;
      //shouldn't be first as have to do checks anyways
      matchNodesSplitSelClassCilk(xn, (*hashes)[2]);
      
      
      //tag 0
      //cout << "tag" << endl;
      matchNodesSplitSelTagCilk(xn, (*hashes)[0]);
  //  }
}    


static void matchNodesSplitSelHashedCilkFlat(WrappedXMLNode **flatPage, int pages, vector<RSelMap*> *hashes) {
                            
      //id 1
      //cout << "id" << endl;
      //matchNodesSplitSelIDCilk(xn, (*hashes)[1]);      
      #ifdef CILKY
        //#pragma cilk_grainsize = GRAIN_SIZE
        cilk_for (int i = 0; i < pages; i++) {
      #else
        for (int i = 0; i < pages; i++) {
      #endif
        WrappedXMLNode *xn = flatPage[i];
        if (xn->id) { splitSelAttempt(xn, xn->id, (*hashes)[1]); }
      }


      //class 2
      //cout << "class" << endl;
      //shouldn't be first as have to do checks anyways
      //matchNodesSplitSelClassCilk(xn, (*hashes)[2]);
      #ifdef CILKY
        //#pragma cilk_grainsize = GRAIN_SIZE
        cilk_for (int i = 0; i < pages; i++) {
      #else
        for (int i = 0; i < pages; i++) {
      #endif
        WrappedXMLNode *xn = flatPage[i];
        for (vector<int>::iterator c = xn->classNames.begin(); 
          c != xn->classNames.end(); 
           ++c) {             
            splitSelAttempt(xn, *c, (*hashes)[2]);
        }
      }    
      
      //tag 0
      //cout << "tag" << endl;
      //matchNodesSplitSelTagCilk(xn, (*hashes)[0]);
      #ifdef CILKY
        //#pragma cilk_grainsize = GRAIN_SIZE
        cilk_for (int i = 0; i < pages; i++) {
      #else
        for (int i = 0; i < pages; i++) {
      #endif
        WrappedXMLNode *xn = flatPage[i];
        if (xn->tag > 0) { splitSelAttempt(xn, xn->tag, (*hashes)[0]); }
      }

}    





static void matchNodesSplitSelHashedTbb(WrappedXMLNode *xn, vector<RSelMap*> *hashes) {
#ifdef TBBY      
      //id 1
      //cout << "id" << endl;
      IndTree<workID, matchNodesSplitSelIDCilk> &firstWave = 
        *new(task::allocate_root()) IndTree<workID, matchNodesSplitSelIDCilk>(xn, (*hashes)[1]);
      task::spawn_root_and_wait(firstWave);

      
      //class 2
      //cout << "class" << endl;
      //shouldn't be first as have to do checks anyways
      IndTree<workClass, matchNodesSplitSelClassCilk> &secondWave =
        *new(task::allocate_root()) IndTree<workClass, matchNodesSplitSelClassCilk>(xn, (*hashes)[2]);
      task::spawn_root_and_wait(secondWave);
      
      
      //tag 0
      //cout << "tag" << endl;
      IndTree<workTag, matchNodesSplitSelTagCilk> &thirdWave =
        *new(task::allocate_root()) IndTree<workTag, matchNodesSplitSelTagCilk>(xn, (*hashes)[0]);
      task::spawn_root_and_wait(thirdWave);
#endif
}    

static void matchNodesSplitSelHashedTbbSparse(WrappedXMLNode *xn, vector<RSelMap*> *hashes) {
#ifdef TBBY      
      
      //id 1
      //cout << "id" << endl;
      IndTreeSparse<workID, matchNodesSplitSelIDCilk> &firstWave = 
        *new(task::allocate_root()) IndTreeSparse<workID, matchNodesSplitSelIDCilk>(xn, (*hashes)[1]);
      task::spawn_root_and_wait(firstWave);

      
      //class 2
      //cout << "class" << endl;
      //shouldn't be first as have to do checks anyways
      IndTreeSparse<workClass, matchNodesSplitSelClassCilk> &secondWave =
        *new(task::allocate_root()) IndTreeSparse<workClass, matchNodesSplitSelClassCilk>(xn, (*hashes)[2]);
      task::spawn_root_and_wait(secondWave);
      
      
      //tag 0
      //cout << "tag" << endl;
      IndTreeSparse<workTag, matchNodesSplitSelTagCilk> &thirdWave =
        *new(task::allocate_root()) IndTreeSparse<workTag, matchNodesSplitSelTagCilk>(xn, (*hashes)[0]);
      task::spawn_root_and_wait(thirdWave);
#endif
}    

static void matchNodesSplitSelHashedTbbNaive(WrappedXMLNode *xn, vector<RSelMap*> *hashes) {
#ifdef TBBY      
      
      //id 1
      //cout << "id" << endl;
      IndTreeNaive<workID, matchNodesSplitSelIDCilk> &firstWave = 
        *new(task::allocate_root()) IndTreeNaive<workID, matchNodesSplitSelIDCilk>(xn, (*hashes)[1]);
      task::spawn_root_and_wait(firstWave);

      
      //class 2
      //cout << "class" << endl;
      //shouldn't be first as have to do checks anyways
      IndTreeNaive<workClass, matchNodesSplitSelClassCilk> &secondWave =
        *new(task::allocate_root()) IndTreeNaive<workClass, matchNodesSplitSelClassCilk>(xn, (*hashes)[2]);
      task::spawn_root_and_wait(secondWave);
     
      
      //tag 0
      //cout << "tag" << endl;
      IndTreeNaive<workTag, matchNodesSplitSelTagCilk> &thirdWave =
        *new(task::allocate_root()) IndTreeNaive<workTag, matchNodesSplitSelTagCilk>(xn, (*hashes)[0]);
      task::spawn_root_and_wait(thirdWave);

#endif
}    

static void matchNodesSplitSelHashedTbbFlat(WrappedXMLNode **flatPage, int pages, vector<RSelMap*> *hashes) {
#ifdef TBBY      
      
//      cout << "grain..." << endl;
      int grain = GRAIN_SIZETBB; //GRAIN_SIZETBB; //NUM_THREADS > 1 ? GRAIN_SIZETBB : 1000000;
      tbb::parallel_for(tbb::blocked_range<size_t>(0,pages - 1), // Index space for loop
                        MatchRange<workID>(flatPage, (*hashes)[1]));

      tbb::parallel_for(tbb::blocked_range<size_t>(0,pages - 1), // Index space for loop
                        MatchRange<workClass>(flatPage, (*hashes)[2]));



      tbb::parallel_for(tbb::blocked_range<size_t>(0,pages - 1), // Index space for loop
                        MatchRange<workTag>(flatPage, (*hashes)[0]));

#endif
}    



static void reduceResultsWorker(WrappedXMLNode **flatPage, int i) {
    WrappedXMLNode *xn = flatPage[i];
     
    xn->rulesTokV.reserve(xn->nRules + xn->ruleSetsOverflow.size());
     for (int i = 0; i < xn->nRules; i++) {
      for (set<RuleSelectorTok*, RuleSTokComp>::iterator rit = xn->ruleSets[i]->begin();
        rit != xn->ruleSets[i]->end(); ++rit) {
        bool found = false;
        int e = xn->rulesTokV.size();
        for (int j = 0; j < e; j++) {
          if (xn->rulesTokV[j] == *rit) {
            found = true; 
            break;
          }
        }
        if (!found) { xn->rulesTokV[e] = *rit; }
      }  
    }
    for (vector<set<RuleSelectorTok*, RuleSTokComp>*>::iterator it=xn->ruleSetsOverflow.begin();
        it != xn-> ruleSetsOverflow.end(); 
        ++it) {
       for (set<RuleSelectorTok*, RuleSTokComp>::iterator rit = (*it)->begin();
        rit != (*it)->end(); ++rit) {
         bool found = false;
        int e = xn->rulesTokV.size();
        for (int j = 0; j < e; j++) {
          if (xn->rulesTokV[j] == *rit) {
            found = true; 
            break;
          }
        }
        if (!found) { xn->rulesTokV[e] = *rit; }
      }  
    }
  /*
    for (int i = 0; i < xn->nRules; i++) {
      for (set<RuleSelectorTok*, RuleSTokComp>::iterator rit = xn->ruleSets[i]->begin();
        rit != xn->ruleSets[i]->end(); ++rit) {
        xn->rulesTok.insert(*rit);
      }  
    }
    for (vector<set<RuleSelectorTok*, RuleSTokComp>*>::iterator it=xn->ruleSetsOverflow.begin();
        it != xn-> ruleSetsOverflow.end(); 
        ++it) {
       for (set<RuleSelectorTok*, RuleSTokComp>::iterator rit = (*it)->begin();
        rit != (*it)->end(); ++rit) {
        xn->rulesTok.insert(*rit);
      }  
    }
   */

}

#ifdef TBBY
class ReduceResultsRange {
  public:
    WrappedXMLNode **flatPage;
    
    ReduceResultsRange(WrappedXMLNode **flatPage_) : flatPage(flatPage_)  { }
    
    void operator()( const tbb::blocked_range<size_t>& range) const {
      size_t d = range.end();
      for (size_t j = range.begin(); j < d; j++) {
          reduceResultsWorker(flatPage, j);
      }
    }
};


#endif


static void reduceResultsTbb (WrappedXMLNode **flatPage, int pages) {
#ifdef TBBY
      int grain = GRAIN_SIZETBB; //NUM_THREADS > 1 ? GRAIN_SIZETBB : 1000000;
      tbb::parallel_for(tbb::blocked_range<size_t>(0, pages - 1), // Index space for loop
                        ReduceResultsRange(flatPage));  


#endif
}


static void reduceResults (WrappedXMLNode **flatPage, int pages) {
      #ifdef CILKY
        //#pragma cilk_grainsize = GRAIN_SIZE
        cilk_for (int i = 0; i < pages; i++) {
      #else
        for (int i = 0; i < pages; i++) {
      #endif      
        reduceResultsWorker(flatPage, i);
   }

}

extern int yydebug;
extern FILE *yyin;
extern vector<RuleSelector*> ruleSelectors;
extern int yyparse();
extern "C" int yywrap ();
int yywrap () {return 1;}
void parseCSS(int debug, FILE *in) {

    yydebug = debug;
    yyin = in;    
    yyparse();
    yywrap();
//    cout << "done" << endl;
}

#ifdef PAPIFY
  const int nEvents = 1;
  int evts[nEvents] = { PAPI_L1_DCM};//,PAPI_TLB_DM, PAPI_L1_DCM, PAPI_L2_DCM};
  long_long values[nEvents] = { 0 };
  long_long dummyValues[nEvents] = { 0 };
#endif


void papiInit() {
#ifdef PAPIFY
     if (PAPI_library_init(PAPI_VER_CURRENT) != PAPI_VER_CURRENT) {
        cout << "PAPI lib init error" << endl;
        exit(1);
      }
      
      if (PAPI_query_event (PAPI_L1_DCM) != PAPI_OK) {
        cout << "No L1 data cache miss counter" << endl;
        exit(1);
      }
      if (PAPI_query_event (PAPI_L2_DCM) != PAPI_OK) {
        cout << "No L1 data cache miss counter" << endl;
        exit(1);
      }
      
      PAPI_num_counters();
      if ( PAPI_start_counters(evts, nEvents) != PAPI_OK) {
       cout << "could not start" << endl;
      }    
      if ( PAPI_read_counters(dummyValues, nEvents) != PAPI_OK) {
       cout << "could not initial read" << endl;
      }    
#endif
}

void papiStart() {
  #ifdef PAPIFY
      if ( PAPI_read_counters(dummyValues, nEvents) != PAPI_OK) {
       cout << "could not reset" << endl;
      }    
  #endif 
}

void papiStop() {
  #ifdef PAPIFY
      if ( PAPI_accum_counters(values, nEvents) != PAPI_OK) {
       cout << "could not accum" << endl;
      }    
  #endif
}




int nNodes = 0;
int class0 = 0;
int class1 = 0;
int class2 = 0;
int class3 = 0;
int classmany= 0;
int id = 0;
int justTag = 0;
int justClass = 0;
int justID = 0;

void characterizeTree (WrappedXMLNode *n) {
  if (n->xml->type == XML_ELEMENT_NODE) {
    nNodes++;
    bool hasID = (n->id);
    if (hasID) id++;
    bool hasClass = n->classNames.size() > 0;
    switch (n->classNames.size()) {
      case 0: class0++; break;
      case 1: class1++; break;
      case 2: class2++; break;
      case 3: class3++; break;
      default: classmany++;
    }
    justTag += (hasID || hasClass) ? 0 : 1;
    justClass += (!hasID && hasClass) ? 1 : 0;
    justID += (hasID && !hasClass)? 1 : 0;
    
    //recur
    for (vector<WrappedXMLNode*>::iterator c = n->children.begin(); 
         c != n->children.end(); 
         ++c) {
      characterizeTree(*c);
    }

  } 
  
}



void outputGlobals(char* file) {
          int oLen = 30;
          string heading[30] = 
                              {"potential", 
                              "nodes", 
                              "1selAttempt", 
                              "2selAttempt", 
                              "3selAttempt",
                              "+selAttempt",
                              "1deep",
                              "2deep",
                              "3deep",
                              "+deep",
                              "matched",
                              "0classNodes",
                              "1classNodes",
                              "2classNodes",
                              "3classNodes",
                              "+classNodes",
                              "idNodes",
                              "justTagNodes",
                              "justClassNodes",
                              "justIDNodes",
                              "dupeSels",
                              "avgDupeSels",
                              "nSel2",
                              "nSel3",
                              "nSel4",
                              "nSel5",
                              "unSel2",
                              "unSel3",
                              "unSel4",
                              "unSel5"};
          int vals[30] = 
                       {potential, nNodes, potential1len, potential2len, potential3len, 
                        potentialmorelen, instant, instant2, instant3, restNum, matchedRules,
                        class0, class1, class2, class3, classmany, id, justTag, justClass, justID,
                        dupeSelCount,
                        dupeSelCount/(nNodes + 0.0),
                        nSel2,
                        nSel3,
                        nSel4,
                        nSel5,
                        unSel2,
                        unSel3,
                        unSel4,
                        unSel5};
          potential = 0;
          nNodes = 0;
          potential1len = 0;
          potential2len = 0;
          potential3len = 0;
          potentialmorelen = 0;
          instant = 0;
          instant2 = 0;
          instant3 = 0;
          restNum = 0;
          matchedRules = 0;
          class0 = 0; 
          class1 = 0;
          class2 = 0;
          class3 = 0;
          classmany = 0;
          id = 0;
          justTag = 0;
          justClass = 0;
          justID = 0;
          dupeSelCount = 0;
          nSel2 = 0;
          nSel3 = 0;
          nSel4 = 0;
          nSel5 = 0;
          unSel2 = 0;
          unSel3 = 0;
          unSel4 = 0;
          unSel5 = 0;
          
          
         
          string hd = "file";
          string vl = "" + string(file);
          for (int i = 0; i < oLen; i++) {
            hd += ", ";
            vl += ", ";              
            hd += heading[i];
            
            //awkward squad
            stringstream s;
            s << vals[i];
            vl += s.str();
          }
          
//          cout << hd << endl;
          cout << vl << endl;


          /*
          cout << "Potential: " << potential << ", Nodes: " << nodes << ", avg: " << ((0.0 + potential)/nodes) << endl;
          cout << "1len: " << potential1len << ", average: " << ((0.0 + potential1len)/potential) << endl;
          cout << "2len: " << potential2len << ", average: " << ((0.0 + potential2len)/potential) << endl;
          cout << "3len: " << potential3len << ", average: " << ((0.0 + potential3len)/potential) << endl;
          cout << "morelen: " << potentialmorelen << ", average: " << ((0.0 + potentialmorelen)/potential) << endl;          
          cout << "Instantly hit: " << instant << ", average: " << ((0.0 + instant)/potential) << endl;
          cout << "2nd hit: " << instant2 << ", average: " << ((0.0 + instant2)/potential) << endl;
          cout << "third hit: " << instant3 << ", average: " << ((0.0 + instant3)/potential) << endl;
          cout << "Rest hit: " << ((0.0 + restNum)/potential) << ", average len of rest: " << (0.0 + restLen)/restNum << endl;          
          cout << "Average matched rules per node: " << ((0.0 + matchedRules)/nodes) << endl;          
          */
          
          
          
          
 
}


#ifdef CILKY
int cilk_main (int argc, char **argv) {
#else
int main (int argc, char **argv) {
#endif


    timeval startTime, endTime;
    timeval startTime2, endTime2;

    int dir;
    int rounds;
    int doci;
    
    if (argc < 3) { 
        cout << "Need mode, max weight, num threads, rounds, one HTML file, and at least one ";
        cout << "CSS file, only received: " << argc << endl;
        
        cout << "0: naive seq, 1: hashed seq, 2: naive cilk, 3: hashed cilk, 4: mult seq, ";
        cout << "5: hashed and split cilk, 6: parse, 7: parse & hash, 8: parse & cilk hash" << endl;
        return -1;
    } else {
        dir = atoi(argv[1]);
        MAX_WEIGHT = atoi(argv[2]);
        NUM_THREADS = atoi(argv[3]);
        rounds = atoi(argv[4]);
        GRAIN_SIZETBB = atoi(argv[5]);
        doci = 6;
    }
    
    #ifdef TBBY
        task_scheduler_init init(task_scheduler_init::deferred); 
        init.initialize(NUM_THREADS);
        //task_scheduler_init init();
    #endif

    
    
    if (dir == -1) {
      #ifdef DEBUGY
        cout << "Skip all processing." << endl;
      #endif
      gettimeofday(&endTime, NULL);   
      double t1=startTime.tv_sec+(startTime.tv_usec/1000000.0);
      double t2=endTime.tv_sec+(endTime.tv_usec/1000000.0);
      cout << t2 - t1;

      exit(1);
    }

    
    Doc *d = new Doc(argv[doci]);
    #ifdef DEBUGY
      cout << "HTML (" << argv[doci] << ") Nodes: " << countNodes(xmlDocGetRootElement(d->doc)) << endl;
    #endif

    //cout << "Parsing css " << endl;
    for (int i = doci + 1; i < argc; i++)  {
      FILE *f = fopen(argv[i], "r");
      parseCSS(DEBUG, f);
      fclose(f);
      #ifdef DEBUGY
        cout << "file " << argv[i] << ": rules so far: " << ruleSelectors.size() << endl;
      #endif
    }
    
    //string coercions to enable comparisons with xmlLib's HTML parse tree
    XMLLibSelectorPredicate::wrapRules(&ruleSelectors);
    
    if (!d || !d->doc) {
        cout << "no doc" << endl;
        exit(1);
    }
    
    
    map<string, int> lookup;
    lookup.insert(pair<string, int>("", 0));
    
    //compact rule selectors to use tokens
    
    
    vector<RuleSelectorTok*> ruleSelectorsTok;
    for (vector<RuleSelector*>::iterator it = ruleSelectors.begin();
         it != ruleSelectors.end(); ++it) {
         
         ruleSelectorsTok.push_back(RuleSelectorTok::clone(*it, &lookup));
    }

    
        
    //wrap xml tree to add auxillary data, like split class names
    WrappedXMLNode *r = new WrappedXMLNode(xmlDocGetRootElement(d->doc), NULL, &lookup);
    
    WrappedXMLNode **pageFlat = new WrappedXMLNode*[r->numChildren + 1]; //actually less, only puts in XML nodes    
    bzero(pageFlat, sizeof(WrappedXMLNode*) * (r->numChildren + 1));
    int pageFlatSize = flattenPage(r, pageFlat, 0);
    #ifdef RANDOMIZE
    for (int i = 0; i < pageFlatSize; i++) {
        int target = rand() % pageFlatSize;
        WrappedXMLNode *old = pageFlat[target];
        pageFlat[target] = pageFlat[i];
        pageFlat[i] = old;
    }
    #endif
    
    

    #ifdef DEBUGY
        if (dir == 0) {            
          cout << "Naive seq: ";
        } else if (dir == 1) {
          cout << "Hashed seq: ";
        } else if (dir == 2) {
          cout << "Naive cilk (weight " << MAX_WEIGHT << "): ";
        } else if (dir == 3) {
          cout << "Hashed cilk (weight " << MAX_WEIGHT << "): ";
        } else if (dir == 4) {
          cout << "Mult seq (repeat 4)";
        } else if (dir == 5) {
          cout << "Hashed and split cilk (weight " << MAX_WEIGHT << "): ";      
        } else if (dir == 6) {
          cout << "nothing: ";
        } else if (dir == 7) {
          cout << "genhash: ";
        } else if (dir == 8) {
          cout << "genhash cilk: ";
          cout << "\n\nERROR! Not implemented!" << endl;
          exit(1);
        } else if (dir == 9) {
          cout << "Cache-hashed and cached cilk (weight " << MAX_WEIGHT << "): ";
        } else if (dir == 10) {
          cout << "Cache-hashing";
        } else if (dir == 1) {
          cout << "Traversing tree"; 
        }
        cout << rounds << " rounds" << endl;
    #endif
    
    papiInit();  
    #ifdef PAPIFY
    
    #endif
    

   vector<RSelMap*> *hash;
   if (dir == 12 || dir == 14 || dir == 15 || dir == 16 || dir == 17 || dir == 18) {
     hash = genSelHash(&ruleSelectorsTok);
   }
   
   vector<RTableMap*> *hashOld;
   if (dir == 3 || dir == 4 || dir == 5) {
     hashOld = genHash(&ruleSelectorsTok);
   }

//   gettimeofday(&startTime, NULL);
        tbb::tick_count::interval_t interval;  
        tbb::tick_count t0 = tbb::tick_count::now();  

    for (int i = 0; i < rounds; i++) {                
        if (dir == 0) {            
          cout << "Matching naive." << endl;
          matchNodesNaive(r, &ruleSelectorsTok);
          calcHits(r);   
        } else if (dir == 1) {

/*  typedef map<Selector*, 
              set < RuleSelector*, RuleSComp >*, 
              SelectorTokCompStrEq> SelRange;
  typedef map< int, SelRange*, XMLComp> RSelMap;
*/

          //vector<RTableMap*> *hash = genHash(&ruleSelectorsTok);
          //matchNodesHashed(r, (*hash)[0], (*hash)[1], (*hash)[2]);
          //calcHits(r); 
          //characterizeTree(r);
          //outputGlobals(argv[doci]);          

          vector<RSelMap*> *selHash = genSelHash(&ruleSelectorsTok);
          matchNodesSplitSelHashedCilk(r, selHash);
          outputGlobals(argv[doci]);


        } else if (dir == 2) {
          matchNodesNaiveCilk(r, &ruleSelectorsTok);    
        } else if (dir == 3) {
          vector<RTableMap*> *hash = hashOld;
          papiStart(); 
          matchNodesHashedCilk(r, (*hash)[0], (*hash)[1], (*hash)[2]);
          papiStop();
        } else if (dir == 4) {
          vector<RTableMap*> *hash = hashOld;
          #ifdef CILKY
          #pragma cilk_grainsize = 1
          cilk_for (int j = 0; j < 4; j++) {
          #else
          for (int j = 0; j < 4; j++) {
          #endif
            papiStart(); 
            matchNodesHashed(r, (*hash)[0], (*hash)[1], (*hash)[2]);
            papiStop();
          }
        } else if (dir == 5) {
          papiStart();    
          vector<RTableMap*> *hash = hashOld;
          matchNodesSplitHashedCilk(r, hash);
          papiStop();
        } else if (dir == 6) {
          //nothing
        } else if (dir == 7) {
          papiStart(); 
          /*vector<RTableMap*> *hash = */ genHash(&ruleSelectorsTok);
          papiStop();
        } else if (dir == 8) {
          //vector<RTableMap*> *hash = genHashCilk(&ruleSelectorsTok);          
        } else if (dir == 9) {
        } else if (dir == 10) {
        } else if (dir == 11) {
          papiStart();
          cout << "nodes: " << countNodes(r->xml) << endl;
          papiStop();
        } else if (dir == 12) {
          papiStart(); 
          matchNodesSplitSelHashedCilk(r, hash);
	  gettimeofday(&startTime2, NULL);
          papiStop();
          reduceResults(pageFlat, pageFlatSize);
        } else if (dir == 13) {
          vector<RSelMap*> *hash = genSelHash(&ruleSelectorsTok);
        } else if (dir == 14) {
          papiStart(); 
          matchNodesSplitSelHashedTbb(r, hash);
	  gettimeofday(&startTime2, NULL);
          reduceResultsTbb(pageFlat, pageFlatSize);
          papiStop();          
        } else if (dir == 15) {
          papiStart(); 
          matchNodesSplitSelHashedTbbSparse(r, hash);
	  gettimeofday(&startTime2, NULL);
  	  reduceResultsTbb(pageFlat, pageFlatSize);
          papiStop();          
        } else if (dir == 16) {
          papiStart(); 
          matchNodesSplitSelHashedTbbNaive(r, hash);
	  gettimeofday(&startTime2, NULL);
          reduceResultsTbb(pageFlat, pageFlatSize);
          papiStop();          
        } else if (dir == 17) {
          papiStart(); 
          matchNodesSplitSelHashedCilkFlat(pageFlat, pageFlatSize, hash);
	  gettimeofday(&startTime2, NULL);
          reduceResults(pageFlat, pageFlatSize);
          papiStop();
        } else if (dir == 18) {
          papiStart();
          matchNodesSplitSelHashedTbbFlat(pageFlat, pageFlatSize, hash);
          reduceResultsTbb(pageFlat, pageFlatSize);
	  gettimeofday(&startTime2, NULL);
          papiStop();
        }
   }


  #ifdef PAPIFY
    if (PAPI_stop_counters(dummyValues, nEvents) != PAPI_OK) {
      cout << "could not stop" << endl;
    }   
    for (int i = 0; i < nEvents; i++) {
      cout << values[i] << " ";
    }
    cout << endl;
  #endif

        tbb::tick_count t1 = tbb::tick_count::now();  
        interval = t1-t0;  
        printf("%g\n",interval.seconds());     //asdf TODO reenable
    
//   gettimeofday(&endTime, NULL);   
//   double t1=startTime.tv_sec+(startTime.tv_usec/1000000.0);
//   double t2=endTime.tv_sec+(endTime.tv_usec/1000000.0);
//   cout << t2 - t1 << endl;

   calcHits(r); 
  
  #ifdef DEBUGY
    #ifdef CILKY
      cout << nhits().get_value() << " nodes with rules, and total of " << nihits().get_value() << " rules matched\n";
      cout << "\nnihits: " << nihits().get_value() << endl;
    #else
      cout << nhits << " nodes with rules, and total of " << nihits << " rules matched\n";  
      cout << "\nnihits: " << nihits << endl;
    #endif
  #endif
    
  #ifdef TBBY
    init.terminate();
  #endif
}

Show details Hide details

Change log

r612 by lmeyerov on Oct 29, 2009 Diff

fixed tbb craziness

Go to:

Older revisions

r597 by lmeyerov on Sep 27, 2009 Diff

bad tbb settings in prev

r596 by lmeyerov on Sep 27, 2009 Diff

updated timer etc

r576 by lmeyerov on Jul 20, 2009 Diff

benchmark between phases

All revisions of this file

File info

Size: 69393 bytes, 2379 lines

View raw file