X-Git-Url: http://git.nguyen.vg/gitweb/?a=blobdiff_plain;ds=sidebyside;f=XMLTree.cpp;h=40d80555a6838486be8b3b9ac3cfa59a8e9c2867;hb=8b92ac7e539c796ee3160078b5ca30537f26ea51;hp=dfda61afa9467dd8049037bfef8866eec4ee82d1;hpb=fadbf5f42541aa09769cbe406f5756fa042fe2d9;p=SXSI%2FXMLTree.git diff --git a/XMLTree.cpp b/XMLTree.cpp index dfda61a..40d8055 100644 --- a/XMLTree.cpp +++ b/XMLTree.cpp @@ -1,94 +1,84 @@ #include "basics.h" -#include -#include #include "XMLTree.h" -#include -#include -#include -#include - -static double tLoading = 0; - -static unsigned int cLoading = 0; -static struct timeval tmpv1; -static struct timeval tmpv2; -static string mem1; -static string mem2; - -void read_procmem(string& memstr) { - std::string buf; - pid_t pid = getpid(); - std::stringstream path; - path << "/proc/" << pid << "/status"; - std::ifstream infile; - infile.open (path.str().c_str(), std::ifstream::in); - while (infile.good()){ - getline(infile,buf); - if (infile.eof()) { - memstr = "Could not read memory"; - return; - }; - int idx = buf.find("VmRSS"); - if (idx == 0){ - memstr = buf; - return; - }; - }; - memstr = "Could not read memory"; - return; +#include "timings.h" +#include +using std::cout; +using std::endl; +using std::min; +using std::string; +// functions to convert tag positions to the corresponding tree node and viceversa. +// These are implemented in order to be able to change the tree and Tags representations, +// without affecting the code so much. +// Current implementation corresponds to balanced-parentheses representation for +// the tree, and storing 2 tags per tree node (opening and closing tags). + + +static int bits8 (int t ) { + int r = bits(t); + if (r <= 8) + return 8; + else if (r <= 16) + return 16; + else + return r; } -#define STARTTIMER() do { \ - gettimeofday(&tmpv1,NULL); \ - read_procmem(mem1); \ - } while (0) \ -#define STOPTIMER(x) do { \ - read_procmem(mem2); \ - gettimeofday(&tmpv2,NULL); \ - (t##x) = ((tmpv2.tv_sec - tmpv1.tv_sec) * 1000000.0 + \ - (tmpv2.tv_usec - tmpv1.tv_usec))/1000.0; \ - (c##x)= (c##x)+1; \ - } while (0) -#define PRINTTIME(s,x) do { \ - std::cerr << (s) << " : " << (t##x) << "ms" << std::endl; \ - std::cerr << "Mem use before: " << mem1 << std::endl; \ - std::cerr << "Mem use after: " << mem2 << std::endl; \ - std::cerr.flush(); \ - } while (0) \ +static treeNode fast_sibling(bp* Par,treeNode x,TagType tag){ + if (tag == PCDATA_TAG_ID){ + x = x+2; + return fast_inspect(Par,x)==OP ? x : NULLT; + } else return fast_next_sibling(Par,x); + +} -// functions to convert tag positions to the corresponding tree node and viceversa. -// These are implemented in order to be able to change the tree and Tags representations, -// without affecting the code so much. -// Current implementation corresponds to balanced-parentheses representation for -// the tree, and storing 2 tags per tree node (opening and closing tags). -// tag position -> tree node -inline treeNode tagpos2node(int t) - { - return (treeNode) t; - } -// tree node -> tag position -inline int node2tagpos(treeNode x) + +inline uint get_field_no_power(uint *A, uint len, uint index) { + + register uint i=index*len/W, j=index*len-W*i; + return (j+len <= W) ? (A[i] << (W-j-len)) >> (W-len) : (A[i] >> j) | (A[i+1] << (WW-j-len)) >> (W-len); + +} + +static uint fast_get_field(uint* A,int len, int idx) { - return (int)x; + uint f1, f2; + switch (len) { + case 8: + return (uint) (((uchar*)A)[idx]); + case 16: + f2 = ((unsigned short*)A)[idx]; + f1 = ((unsigned short*)A)[idx+1]; + return (f1 << 16) + f2; + default: + return get_field_no_power (A,len,idx); + }; + } -// returns NULLT if the test is true -#define NULLT_IF(x) do { if (x) return NULLT; } while (0) -XMLTree::XMLTree( pb * const par, uint npar, vector * const TN, TagIdMap * const tim, uint *empty_texts_bmp, TagType *tags, - TextCollection * const TC, bool dis_tc) +XMLTree::XMLTree( pb * const par, uint npar, vector * const TN, TagIdMap * const tim, + uint *empty_texts_bmp, TagType *tags, + TextCollection * const TC, bool dis_tc, + TextCollectionBuilder::index_type_t _index_type ) { + buffer = 0; + print_stack = 0; // creates the data structure for the tree topology Par = (bp *)umalloc(sizeof(bp)); - bp_construct(Par, npar, (pb*) par, OPT_DEGREE|0); + STARTTIMER(); + bp_construct(Par, npar, (pb*) par, OPT_DEGREE|0); + STOPTIMER(Building); + PRINTTIME("Building parenthesis struct", Building); + STARTTIMER(); + // creates structure for tags @@ -96,32 +86,42 @@ XMLTree::XMLTree( pb * const par, uint npar, vector * const TN, TagIdM tIdMap = (TagIdMap *) tim; uint max_tag = TN->size() - 1; + static_bitsequence_builder *bmb = new static_bitsequence_builder_sdarray(); alphabet_mapper *am = new alphabet_mapper_none(); Tags = new static_sequence_bs((uint*)tags,npar,am,bmb); - cout << "Tags test: " << Tags->test((uint*)tags,npar) << endl; + //cout << "Tags test: " << Tags->test((uint*)tags,npar) << endl; - tags_blen = bits(max_tag); + //Ensures that for small tag numbers, we are on an 8bit boundary. + //Makes tag access way faster with negligeable waste of space. + tags_blen = bits8(max_tag); + std::cerr << "Tags blen is " << tags_blen << "\n"; tags_len = (uint)npar; tags_fix = new uint[uint_len(tags_blen,tags_len)]; for(uint i=0;i<(uint)npar;i++) set_field(tags_fix,tags_blen,i,tags[i]); - delete bmb; free(tags); tags = NULL; + + STOPTIMER(Building); + PRINTTIME("Building Tag Structure", Building); Text = (TextCollection*) TC; EBVector = new static_bitsequence_rrr02(empty_texts_bmp,npar,32); + //EBVector = new static_bitsequence_sdarray(empty_texts_bmp,npar); free(empty_texts_bmp); empty_texts_bmp = NULL; disable_tc = dis_tc; + text_index_type = _index_type; + std::cerr << "Number of distinct tags " << TagName->size() << "\n"; + //std::cerr.flush(); } @@ -148,7 +148,6 @@ XMLTree::~XMLTree() delete EBVector; EBVector = NULL; - } @@ -196,23 +195,39 @@ void XMLTree::Save(int fd) // stores the texts if (!disable_tc) { - Text->Save(fp); - }; + ufwrite(&text_index_type, sizeof(TextCollectionBuilder::index_type_t), 1, fp); + + const char * pref; + switch (text_index_type){ + case TextCollectionBuilder::index_type_default: + pref = "default_"; + break; + case TextCollectionBuilder::index_type_swcsa: + pref = "swcsa_"; + break; + case TextCollectionBuilder::index_type_rlcsa: + pref = "rlcsa_"; + break; + }; + + Text->Save(fp, pref); + + } } - // Load: loads XML tree data structure from file. Returns // a pointer to the loaded data structure -XMLTree *XMLTree::Load(int fd) +XMLTree *XMLTree::Load(int fd, bool load_tc,int sample_factor) { + FILE *fp; char buffer[1024]; XMLTree *XML_Tree; int i; - + buffer[1023] = '\0'; fp = fdopen(fd, "r"); @@ -226,23 +241,21 @@ XMLTree *XMLTree::Load(int fd) PRINTTIME("Loading parenthesis struct", Loading); STARTTIMER(); - XML_Tree->TagName = new vector(); - XML_Tree->tIdMap = new std::unordered_map(); - - string s; + XML_Tree->TagName = new std::vector(); + XML_Tree->tIdMap = new std::unordered_map(); + std::string s; int ntags; // Load the tag names ufread(&ntags, sizeof(int), 1, fp); for (i=0; iTagName->push_back(s); + XML_Tree->TagName->push_back(s); XML_Tree->tIdMap->insert(std::make_pair(s,i)); }; @@ -253,100 +266,140 @@ XMLTree *XMLTree::Load(int fd) // loads the tag structure XML_Tree->Tags = static_sequence::load(fp); ufread(&XML_Tree->tags_blen,sizeof(uint),1,fp); + std::cerr << "tags_blen is "<< XML_Tree->tags_blen <<"\n"; ufread(&XML_Tree->tags_len,sizeof(uint),1,fp); XML_Tree->tags_fix = new uint[uint_len(XML_Tree->tags_blen,XML_Tree->tags_len)]; ufread(XML_Tree->tags_fix,sizeof(uint),uint_len(XML_Tree->tags_blen,XML_Tree->tags_len),fp); // TODO ask francisco about this /// FIXME:UGLY tests! - uint * seq = new uint[XML_Tree->tags_len]; - for(uint i=0;itags_len;i++) - seq[i] = get_field(XML_Tree->tags_fix,XML_Tree->tags_blen,i); + //uint * seq = new uint[XML_Tree->tags_len]; + //for(uint i=0;itags_len;i++) + // seq[i] = get_field(XML_Tree->tags_fix,XML_Tree->tags_blen,i); //cout << "Tags test: " << XML_Tree->Tags->test(seq,XML_Tree->tags_len) << endl; - XML_Tree->Tags->test(seq,XML_Tree->tags_len); - delete [] seq; + //XML_Tree->Tags->test(seq,XML_Tree->tags_len); + //delete [] seq; /// End ugly tests STOPTIMER(Loading); + std::cerr << (uint_len(XML_Tree->tags_blen,XML_Tree->tags_len)*sizeof(uint))/(1024*1024) << " MB for tag sequence" << std::endl; PRINTTIME("Loading tag struct", Loading); STARTTIMER(); // loads the flags ufread(&(XML_Tree->disable_tc), sizeof(bool), 1, fp); + if (load_tc) { + XML_Tree->EBVector = static_bitsequence_rrr02::load(fp); - XML_Tree->EBVector = static_bitsequence_rrr02::load(fp); - - - STOPTIMER(Loading); - PRINTTIME("Loading text bitvector struct", Loading); - STARTTIMER(); - - // Not used - int sample_rate_text = 64; - // loads the texts - if (!XML_Tree->disable_tc){ - XML_Tree->Text = TextCollection::Load(fp,sample_rate_text); + STOPTIMER(Loading); + PRINTTIME("Loading text bitvector struct", Loading); + STARTTIMER(); + + // Not used + // loads the texts + if (!XML_Tree->disable_tc){ + ufread(&(XML_Tree->text_index_type), + sizeof(TextCollectionBuilder::index_type_t), 1, fp); + const char * pref; + switch (!XML_Tree->text_index_type){ + case TextCollectionBuilder::index_type_default: + pref = "default_"; + break; + case TextCollectionBuilder::index_type_swcsa: + pref = "swcsa_"; + break; + case TextCollectionBuilder::index_type_rlcsa: + pref = "rlcsa_"; + break; + }; + XML_Tree->Text = TextCollection::Load(fp, pref, TextCollection::index_mode_default, sample_factor); + + } + else XML_Tree->Text = NULL; + STOPTIMER(Loading); + PRINTTIME("Loading TextCollection", Loading); + STARTTIMER(); } - else XML_Tree->Text = NULL; - STOPTIMER(Loading); - PRINTTIME("Loading TextCollection", Loading); - STARTTIMER(); + else { + XML_Tree->EBVector = NULL; + XML_Tree->Text = NULL; + XML_Tree->disable_tc = true; + }; + return XML_Tree; } -// root(): returns the tree root. -inline treeNode XMLTree::Root() - { - return 0; //root_node(Par); - } // SubtreeSize(x): the number of nodes (and attributes) in the subtree of node x. -int XMLTree::SubtreeSize(treeNode x) +/*int XMLTree::SubtreeSize(treeNode x) { return subtree_size(Par, x); } - +*/ // SubtreeTags(x,tag): the number of occurrences of tag within the subtree of node x. +/* int XMLTree::SubtreeTags(treeNode x, TagType tag) { if (x == Root()) - x = first_child(Par,x); + x = fast_first_child(Par,x); int s = x + 2*subtree_size(Par, x) - 1; - return Tags->rank(tag, s) - Tags->rank(tag, node2tagpos(x)-1); + return (Tags->rank(tag, s) - Tags->rank(tag, node2tagpos(x)-1))+1; + } +*/ +int XMLTree::SubtreeElements(treeNode x) + { + + int size = subtree_size(Par,x); + if (x == Root()){ + x = fast_first_child(Par,x); + size = size - 1; + }; + + int s = x + 2*size - 1; + int ntext = Tags->rank(PCDATA_TAG_ID, s) - Tags->rank(PCDATA_TAG_ID, node2tagpos(x)-1); + size = size - ntext; + treeNode fin = fast_find_close(Par,x); + treeNode y = Tags->select_next(ATTRIBUTE_TAG_ID,node2tagpos(x)); + while (y != NULLT && y < fin){ + size -= SubtreeSize(y); + y = Tags->select_next(ATTRIBUTE_TAG_ID,node2tagpos(y)); + }; + return size; } // IsLeaf(x): returns whether node x is leaf or not. In the succinct representation // this is just a bit inspection. bool XMLTree::IsLeaf(treeNode x) { - return isleaf(Par, x); + NULLT_IF(x==NULLT); + return fast_isleaf(Par, x); } // IsAncestor(x,y): returns whether node x is ancestor of node y. bool XMLTree::IsAncestor(treeNode x, treeNode y) { - return is_ancestor(Par, x, y); + return fast_is_ancestor(Par, x, y); } // IsChild(x,y): returns whether node x is parent of node y. bool XMLTree::IsChild(treeNode x, treeNode y) { - if (!is_ancestor(Par, x, y)) return false; + if (!fast_is_ancestor(Par, x, y)) return false; return depth(Par, x) == (depth(Par, y) + 1); } // IsFirstChild(x): returns whether node x is the first child of its parent. -bool XMLTree::IsFirstChild(treeNode x) +/*bool XMLTree::IsFirstChild(treeNode x) { return ((x != NULLT)&&(x==Root() || prev_sibling(Par,x) == (treeNode)-1)); } - +*/ // NumChildren(x): number of children of node x. Constant time with the data structure // of Sadakane. @@ -380,47 +433,45 @@ int XMLTree::Postorder(treeNode x) { return postorder_rank(Par, x); } - +/* // Tag(x): returns the tag identifier of node x. TagType XMLTree::Tag(treeNode x) { - return get_field(tags_fix,tags_blen,node2tagpos(x)); + return fast_get_field(tags_fix,tags_blen,node2tagpos(x)); } - +*/ // DocIds(x): returns the range of text identifiers that descend from node x. // returns {NULLT, NULLT} when there are no texts descending from x. range XMLTree::DocIds(treeNode x) { - range r; - if (x == NULLT) { - r.min = NULLT; - r.max = NULLT; - return r; - }; - - - int min = EBVector->rank1(x-1); - int max = EBVector->rank1(x+2*subtree_size(Par, x)-2); - if (min==max) { // range is empty, no texts within the subtree of x - r.min = NULLT; - r.max = NULLT; - } - else { // the range is non-empty, there are texts within the subtree of x - r.min = min+1; - r.max = max; - } - return r; - + range r; + if (x == NULLT) { + r.min = NULLT; + r.max = NULLT; + return r; + }; + int min = EBVector->rank1(x-1); + int max = EBVector->rank1(x+2*subtree_size(Par, x)-2); + if (min==max) { // range is empty, no texts within the subtree of x + r.min = NULLT; + r.max = NULLT; + } + else { // the range is non-empty, there are texts within the subtree of x + r.min = min+1; + r.max = max; + } + return r; } // Parent(x): returns the parent node of node x. +/* treeNode XMLTree::Parent(treeNode x) { if (x == Root()) return NULLT; else - return parent(Par, x); - } + return parent(Par, x);; + }*/ // Child(x,i): returns the i-th child of node x, assuming it exists. treeNode XMLTree::Child(treeNode x, int i) @@ -430,135 +481,161 @@ treeNode XMLTree::Child(treeNode x, int i) } // FirstChild(x): returns the first child of node x, assuming it exists. Very fast in BP. +/* treeNode XMLTree::FirstChild(treeNode x) { NULLT_IF(x==NULLT); - return first_child(Par, x); + return fast_first_child(Par, x); } - +*/ +/* treeNode XMLTree::FirstElement(treeNode x) { NULLT_IF(x==NULLT); - treeNode fc = first_child(Par, x); - //<$> is 2 - return ((fc == NULLT || Tag(fc) != PCDATA_TAG_ID) ? fc : next_sibling(Par,fc)); - + x = fast_first_child(Par, x); + NULLT_IF(x == NULLT); + switch (Tag(x)){ + + case PCDATA_TAG_ID: + x = x+2; + return (fast_inspect(Par,x)==OP)? x : NULLT; + + case ATTRIBUTE_TAG_ID: + x = fast_next_sibling(Par,x); + if (x != NULLT && Tag(x) == PCDATA_TAG_ID){ + x = x+2; + return (fast_inspect(Par,x)==OP)? x : NULLT; + } + else return x; + default: + return x; + } } - +*//* treeNode XMLTree::NextElement(treeNode x) { - NULLT_IF(x==NULLT); - treeNode ns = next_sibling(Par, x); - return ((ns == NULLT || Tag(ns) != PCDATA_TAG_ID) ? ns : next_sibling(Par,ns)); -} + NULLT_IF(x==NULLT); + x = fast_next_sibling(Par, x); + NULLT_IF(x == NULLT); + if (Tag(x) == PCDATA_TAG_ID){ + x = x+2; + return (fast_inspect(Par,x)==OP)? x : NULLT; + } + else return x; + }*/ // LastChild(x): returns the last child of node x. -treeNode XMLTree::LastChild(treeNode x) + /*treeNode XMLTree::LastChild(treeNode x) { - NULLT_IF(x==NULLT || x == Root() || isleaf(Par,x)); - return find_open(Par, find_close(Par, x)-1); + NULLT_IF(x == NULLT || fast_isleaf(Par,x)); + return find_open(Par, fast_find_close(Par, x)-1); } - - + */ // NextSibling(x): returns the next sibling of node x, assuming it exists. -treeNode XMLTree::NextSibling(treeNode x) +/*treeNode XMLTree::NextSibling(treeNode x) { NULLT_IF(x==NULLT || x == Root() ); - return next_sibling(Par, x); + x = fast_find_close(Par,x)+1; + return (fast_inspect(Par,x) == CP ? NULLT : x); } +*/ // PrevSibling(x): returns the previous sibling of node x, assuming it exists. -treeNode XMLTree::PrevSibling(treeNode x) +/*treeNode XMLTree::PrevSibling(treeNode x) { - NULLT_IF(x==NULLT || x == Root()); + NULLT_IF(x==NULLT); return prev_sibling(Par, x); } - +*/ // TaggedChild(x,tag): returns the first child of node x tagged tag, or NULLT if there is none. // Because of the balanced-parentheses representation of the tree, this operation is not supported // efficiently, just iterating among the children of node x until finding the desired child. +/* treeNode XMLTree::TaggedChild(treeNode x, TagType tag) { - NULLT_IF(x==NULLT || isleaf(Par,x)); - + NULLT_IF(x==NULLT || fast_isleaf(Par,x)); treeNode child; - child = first_child(Par, x); // starts at first child of node x - if (get_field(tags_fix,tags_blen,node2tagpos(child)) == tag) + child = fast_first_child(Par, x); // starts at first child of node x + if (Tag(child) == tag) return child; else - return TaggedFollSibling(child,tag); + return TaggedFollowingSibling(child,tag); } // TaggedSibling(x,tag): returns the first sibling of node x tagged tag, or NULLT if there is none. -treeNode XMLTree::TaggedFollSibling(treeNode x, TagType tag) +treeNode XMLTree::TaggedFollowingSibling(treeNode x, TagType tag) { NULLT_IF(x==NULLT); - treeNode sibling = next_sibling(Par, x); + treeNode sibling = fast_next_sibling(Par, x); + TagType ctag; while (sibling != NULLT) { - if (get_field(tags_fix,tags_blen,node2tagpos(sibling)) == tag) // current sibling is labeled with tag of interest + ctag = Tag(sibling); + if (ctag == tag) // current sibling is labeled with tag of interest return sibling; - sibling = next_sibling(Par, sibling); // OK, let's try with the next sibling + sibling = fast_sibling(Par, sibling, ctag); // OK, let's try with the next sibling } return NULLT; // no such sibling was found } - -treeNode XMLTree::SelectChild(treeNode x, std::unordered_set *tags) +*/ +treeNode XMLTree::SelectChild(treeNode x, TagIdSet *tags) { - NULLT_IF(x==NULLT || isleaf(Par,x)); + NULLT_IF(x==NULLT || fast_isleaf(Par,x)); int i; - treeNode child = first_child(Par, x); - TagType t = get_field(tags_fix, tags_blen, node2tagpos(child)); - std::unordered_set::const_iterator tagit = tags->find(t); - if (tagit != tags->end()) return child; - return SelectFollSibling(child,tags); + treeNode child = fast_first_child(Par, x); + TagType t; + while (child != NULLT) { + t = Tag(child); + if (tags->find(t) != tags->end()) return child; + child = fast_sibling(Par, child,t); + } + return NULLT; } -treeNode XMLTree::SelectFollSibling(treeNode x, std::unordered_set *tags) +treeNode XMLTree::SelectFollowingSibling(treeNode x, TagIdSet *tags) { NULLT_IF(x==NULLT); int i; TagType t; - treeNode sibling = next_sibling(Par, x); - std::unordered_set::const_iterator tagit; + treeNode sibling = fast_next_sibling(Par, x); while (sibling != NULLT) { - t = get_field(tags_fix, tags_blen, node2tagpos(sibling)); - tagit = tags->find(t); - if (tagit != tags->end()) return sibling; - sibling = next_sibling(Par, sibling); + t = Tag(sibling); + if (tags->find(t) != tags->end()) return sibling; + sibling = fast_sibling(Par, sibling,t); } return NULLT; } -// TaggedDesc(x,tag): returns the first node tagged tag with larger preorder than x and within +// TaggedDescendant(x,tag): returns the first node tagged tag with larger preorder than x and within // the subtree of x. Returns NULLT if there is none. -treeNode XMLTree::TaggedDesc(treeNode x, TagType tag) +/* +treeNode XMLTree::TaggedDescendant(treeNode x, TagType tag) { - NULLT_IF(x==NULLT || isleaf(Par,x)); + //NULLT_IF(x==NULLT || fast_isleaf(Par,x)); int s = (int) Tags->select_next(tag,node2tagpos(x)); NULLT_IF (s == -1); treeNode y = tagpos2node(s); // transforms the tag position into a node position - return (is_ancestor(Par,x,y) ? y : NULLT); + return (fast_is_ancestor(Par,x,y) ? y : NULLT); } - - -treeNode XMLTree::SelectDesc(treeNode x, std::unordered_set *tags) +*/ +/* +treeNode XMLTree::SelectDescendant(treeNode x, TagIdSet *tags) { - NULLT_IF (x ==NULLT || isleaf(Par,x)); + NULLT_IF (x ==NULLT || fast_isleaf(Par,x)); int i; treeNode min = NULLT; - treeNode fc = first_child(Par,x); + treeNode fc = fast_first_child(Par,x); treeNode aux; - std::unordered_set::const_iterator tagit; + TagIdSet::const_iterator tagit; for (tagit = tags->begin(); tagit != tags->end(); tagit++) { - aux = TaggedDesc(x, (TagType) *tagit); + aux = TaggedDescendant(x, (TagType) *tagit); if (aux == fc) return fc; if (aux == NULLT) continue; if ((min == NULLT) || (aux < min)) min = aux; @@ -566,11 +643,11 @@ treeNode XMLTree::SelectDesc(treeNode x, std::unordered_set *tags) return min; } - +*/ // TaggedPrec(x,tag): returns the first node tagged tag with smaller preorder than x and not an // ancestor of x. Returns NULLT if there is none. -treeNode XMLTree::TaggedPrec(treeNode x, TagType tag) +treeNode XMLTree::TaggedPreceding(treeNode x, TagType tag) { int r, s; treeNode node_s, root; @@ -579,7 +656,7 @@ treeNode XMLTree::TaggedPrec(treeNode x, TagType tag) s = (int)Tags->select(tag, r); root = root_node(Par); node_s = tagpos2node(s); - while (is_ancestor(Par, node_s, x) && (node_s!=root)) { // the one that we found is an ancestor of x + while (fast_is_ancestor(Par, node_s, x) && (node_s!=root)) { // the one that we found is an ancestor of x r--; if (r==0) return NULLT; // there is no such node s = (int)Tags->select(tag, r); // we should use select_prev instead when provided @@ -591,43 +668,118 @@ treeNode XMLTree::TaggedPrec(treeNode x, TagType tag) // TaggedFoll(x,tag): returns the first node tagged tag with larger preorder than x and not in // the subtree of x. Returns NULLT if there is none. -treeNode XMLTree::TaggedFoll(treeNode x, TagType tag) +treeNode XMLTree::TaggedFollowing(treeNode x, TagType tag) { - NULLT_IF (x ==NULLT || x == Root()); - - return tagpos2node(Tags->select_next(tag,find_close(Par, x))); + NULLT_IF (x ==NULLT || x == Root()); + return tagpos2node(Tags->select_next(tag,fast_find_close(Par, x))); } // TaggedFollBelow(x,tag,root): returns the first node tagged tag with larger preorder than x // and not in the subtree of x. Returns NULLT if there is none. -treeNode XMLTree::TaggedFollBelow(treeNode x, TagType tag, treeNode root) +/* +treeNode XMLTree::TaggedFollowingBelow(treeNode x, TagType tag, treeNode ancestor) { + // NULLT_IF (x == NULLT || x == Root() || x == ancestor); - NULLT_IF (x == NULLT || x == Root()); + //Special optimisation, test for the following sibling first + treeNode close = fast_find_close(Par, x); + treeNode s = tagpos2node(Tags->select_next(tag, close)); - treeNode s = tagpos2node(Tags->select_next(tag, find_close(Par, x))); + if (ancestor == Root() || s==NULLT || s < fast_find_close(Par,ancestor)) return s; + else return NULLT; +} +*/ + /* +treeNode XMLTree::TaggedFollowingBefore(treeNode x, TagType tag, treeNode closing) +{ + + NULLT_IF (x == NULLT || x == Root()); - if (root == Root()) return s; - NULLT_IF (s == NULLT || s >= find_close(Par, root)); + treeNode s = tagpos2node(Tags->select_next(tag, fast_find_close(Par, x))); + NULLT_IF (s == NULLT || s >= closing); return s; } - + */ /* Here we inline TaggedFoll to find the min globally, and only at the end we check if the min is below the context node */ -treeNode XMLTree::SelectFollBelow(treeNode x, std::unordered_set *tags, treeNode root) +treeNode XMLTree::SelectFollowingBelow(treeNode x, TagIdSet *tags, treeNode ancestor) + { + + NULLT_IF(x==NULLT || x==Root()); + + treeNode close = fast_find_close(Par,x); + treeNode ns = close+1; + if ( (fast_inspect(Par,ns) == OP) && (tags->find(Tag(ns)) != tags->end())) + return ns; + + int i; + treeNode min = NULLT; + treeNode aux; + + + TagIdSet::const_iterator tagit; + for (tagit = tags->begin(); tagit != tags->end(); ++tagit) { + + aux = tagpos2node(Tags->select_next(*tagit, close)); + if (aux == NULLT) continue; + if ((min == NULLT) || (aux < min)) min = aux; + }; + + // found the smallest node in preorder which is after x. + // if ctx is the root node, just return what we found. + + if (ancestor == Root() || min == NULLT || min < fast_find_close(Par, ancestor)) return min; + else return NULLT; + + } +/* +treeNode XMLTree::SelectFollowingBefore(treeNode x, TagIdSet *tags, treeNode ancestor_closing) + { + + NULLT_IF(x==NULLT || x==Root()); + + treeNode close = fast_find_close(Par,x); + treeNode ns = close+1; + if ( (fast_inspect(Par,ns) == OP) && (tags->find(Tag(ns)) != tags->end())) + return ns; + + int i; + treeNode min = NULLT; + treeNode aux; + + + TagIdSet::const_iterator tagit; + for (tagit = tags->begin(); tagit != tags->end(); ++tagit) { + + aux = tagpos2node(Tags->select_next(*tagit, close)); + if (aux == NULLT) continue; + if ((min == NULLT) || (aux < min)) min = aux; + }; + + // found the smallest node in preorder which is after x. + // if ctx is the root node, just return what we found. + + if (ancestor_closing == Root() || min == NULLT || min < ancestor_closing) return min; + else return NULLT; + + } +*/ +/* +treeNode XMLTree::SelectFollowingBefore(treeNode x, TagIdSet *tags, treeNode closing) { NULLT_IF(x==NULLT || x==Root()); int i; treeNode min = NULLT; - treeNode ns = next_sibling(Par, x); + treeNode ns = fast_next_sibling(Par, x); + treeNode close = ns - 1; treeNode aux; - std::unordered_set::const_iterator tagit; + TagIdSet::const_iterator tagit; for (tagit = tags->begin(); tagit != tags->end(); tagit++) { - aux = tagpos2node(Tags->select_next(*tagit, find_close(Par, x))); + aux = tagpos2node(Tags->select_next(*tagit, close)); // The next sibling of x is guaranteed to be below ctx // and is the node with lowest preorder which is after ctx. @@ -641,15 +793,12 @@ treeNode XMLTree::SelectFollBelow(treeNode x, std::unordered_set *tags, tre // found the smallest node in preorder which is after x. // if ctx is the root node, just return what we found. - if (root == Root()) return min; - // else check whether if is in below the ctx node - - NULLT_IF (min == NULLT || min >= find_close(Par, root)); + NULLT_IF (min == NULLT || min >= closing); return min; } - +*/ // TaggedAncestor(x, tag): returns the closest ancestor of x tagged tag. Return // NULLT is there is none. @@ -660,7 +809,7 @@ treeNode XMLTree::TaggedAncestor(treeNode x, TagType tag) treeNode s = parent(Par, x), r = Root(); while (s != r) { - if (get_field(tags_fix,tags_blen,node2tagpos(s)) /*Tags->access(node2tagpos(s))*/ == tag) return s; + if (Tag(s) == tag) return s; s = parent(Par, s); } return NULLT; @@ -677,12 +826,19 @@ DocID XMLTree::MyText(treeNode x) // seems faster than testing EBVector->access(x); if (tag == PCDATA_TAG_ID || tag == ATTRIBUTE_DATA_TAG_ID) - return (DocID) (EBVector->rank1(x)-1); //-1 because document ids start from 0 - else + return (DocID) (EBVector->rank1(x)-1); + else return (DocID) NULLT; + +} +// MyText(x): returns the document identifier of the text below node x, +// or NULLT if x is not a leaf node or the text is empty. Assumes Doc +// ids start from 0. +DocID XMLTree::MyTextUnsafe(treeNode x) +{ + return (DocID) (EBVector->rank1(x)-1); //-1 because document ids start from 0 } - // TextXMLId(d): returns the preorder of document with identifier d in the tree consisting of // all tree nodes and all text nodes. Assumes that the tree root has preorder 1. int XMLTree::TextXMLId(DocID d) @@ -729,7 +885,7 @@ unsigned char *XMLTree::GetTagName(TagType tagid) unsigned char *s; if ( tagid < 0 || tagid >= TagName->size()) return (unsigned char *) ""; - strcpy((char *)s, TagName->at(tagid).c_str()); + strcpy((char *)s, (*TagName)[tagid].c_str()); return (s == NULL ? (unsigned char*) "" : s); } @@ -742,7 +898,7 @@ const unsigned char *XMLTree::GetTagNameByRef(TagType tagid) if ( tagid < 0 || tagid >= TagName->size()) return (unsigned char *) ""; - return (const unsigned char *) TagName->at(tagid).c_str(); + return (const unsigned char *) (*TagName)[tagid].c_str(); } @@ -753,11 +909,118 @@ TagType XMLTree::RegisterTag(unsigned char *tagname) TagType id = XMLTree::GetTagId(tagname); if (id == NULLT) { string s = (char *) tagname; - REGISTER_TAG(TagName,tIdMap,s); - + REGISTER_TAG(TagName,tIdMap,s); }; return id; } +treeNode XMLTree::Closing(treeNode x) { + return fast_find_close(Par,x); +} +bool XMLTree::IsOpen(treeNode x) { return fast_inspect(Par,x); } + +//WARNING this uses directly the underlying implementation for plain text + + +void XMLTree::Print(int fd,treeNode x, bool no_text){ + + if (buffer == 0) { + buffer = new string(BUFFER_ALLOC, 0); + print_stack = new std::vector(); + print_stack->reserve(256); + }; + treeNode fin = fast_find_close(Par,x); + treeNode n = x; + TagType tag = Tag(n); + + range r = DocIds(x); + treeNode first_idx; + treeNode first_text = (tag == PCDATA_TAG_ID ? x : ParentNode(r.min-1)); + treeNode first_att = NULLT; + + if (first_att == NULLT) + first_idx = first_text; + else if (first_text == NULLT) + first_idx = first_att; + else + first_idx = min(first_att,first_text); + + uchar * current_text=NULL; + + if (first_idx != NULLT) + current_text = GetText(MyTextUnsafe(first_idx)); + + size_t read = 0; + while (n <= fin){ + if (fast_inspect(Par,n)){ + if (tag == PCDATA_TAG_ID) { + + if (no_text) + _dputs("<$/>", fd); + else { + read = _dprintf((const char*) current_text, fd); + current_text += (read + 1); + }; + n+=2; // skip closing $ + tag = Tag(n); + + } else { + + _dputc('<',fd); + _dput_str((*TagName)[tag], fd); + n++; + if (fast_inspect(Par,n)) { + print_stack->push_back(&((*TagName)[tag])); + tag = Tag(n); + if (tag == ATTRIBUTE_TAG_ID){ + n++; + if (no_text) _dputs("><@@>",fd); + + while (fast_inspect(Par,n)){ + if (no_text) { + _dputc('<', fd); + _dputs((const char*) &(GetTagNameByRef(Tag(n))[3]), fd); + _dputc('>', fd); + _dputs("<$@/>', fd); + n+= 4; + } else { + _dputc(' ', fd); + _dputs((const char*) &(GetTagNameByRef(Tag(n))[3]), fd); + n++; + _dputs("=\"", fd); + read = _dprintf((const char*) current_text, fd); + current_text += (read + 1); + _dputc('"', fd); + n+=3; + } + }; + if (no_text) _dputs("", fd); + else _dputc('>', fd); + n++; + tag=Tag(n); + + } else + _dputc('>', fd); + + } else {// tag + _dputs("/>", fd); + n++; + tag=Tag(n); + }; + }; + } else do { + _dputs("back()), fd); + _dputc('>', fd); + print_stack->pop_back(); + n++; + } while (!(fast_inspect(Par,n) || print_stack->empty())); + tag = Tag(n); + }; + _dputc('\n', fd); + //_flush(fd); +}