X-Git-Url: http://git.nguyen.vg/gitweb/?a=blobdiff_plain;f=XMLTree.cpp;h=65a577bbc66eb643ab1b4bc71ddb72f140c811d7;hb=refs%2Fheads%2Ftrunk;hp=248185d70d431e2d99db5219ee858a29aba6a04b;hpb=691d12dccc6710752553f92d300ac4f82f7e67cc;p=SXSI%2FXMLTree.git diff --git a/XMLTree.cpp b/XMLTree.cpp index 248185d..65a577b 100644 --- a/XMLTree.cpp +++ b/XMLTree.cpp @@ -1,4 +1,4 @@ -#include "basics.h" +#include "common.h" #include "XMLTree.h" #include "timings.h" #include @@ -7,17 +7,12 @@ 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, +// 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 -static treeNode tagpos2node(int t) - { - return (treeNode) t; - } static int bits8 (int t ) { int r = bits(t); @@ -25,58 +20,26 @@ static int bits8 (int t ) { return 8; else if (r <= 16) return 16; - else + else return r; } -// tree node -> tag position -static int node2tagpos(treeNode x) -{ - return (int)x; -} - -static int fast_find_close(bp *b,int s) -{ - return fwd_excess(b,s,-1); -} - -static int fast_inspect(bp* Par,treeNode i) -{ - int j,l; - j = i >> logD; - l = i & (D-1); - return (Par->B[j] >> (D-1-l)) & 1; -} - -static treeNode fast_first_child(bp *Par, treeNode x) -{ - x = x+1; - return (fast_inspect(Par,x) == OP) ? x : NULLT; -} - -static treeNode fast_next_sibling(bp* Par,treeNode x) -{ - x = fast_find_close(Par,x)+1; - return (fast_inspect(Par,x) == OP) ? x : NULLT; -} 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); + return bp_inspect(Par,x)==OP ? x : NULLT; + } else return bp_next_sibling(Par,x); } -static bool fast_isleaf(bp* Par,treeNode x){ - return (fast_inspect(Par,x+1) == CP ? true : false); -} + 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); @@ -98,40 +61,36 @@ static uint fast_get_field(uint* A,int len, int idx) } -inline bool fast_is_ancestor(bp * Par,treeNode x,treeNode y){ - if (x > y) - return false; - else - return (x==0) || (y <= fast_find_close(Par,x)); -} -XMLTree::XMLTree( pb * const par, uint npar, vector * const TN, TagIdMap * const tim, + +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) + TextCollection * const TC, bool dis_tc, + TextCollectionBuilder::index_type_t _index_type ) { buffer = 0; - // creates the data structure for the tree topology - Par = (bp *)umalloc(sizeof(bp)); - STARTTIMER(); - bp_construct(Par, npar, (pb*) par, OPT_DEGREE|0); - STOPTIMER(Building); - PRINTTIME("Building parenthesis struct", Building); - STARTTIMER(); + print_stack = 0; + // creates the data structure for the tree topology + STARTTIMER(); + Par = bp_construct(npar, (pb*) par, OPT_FAST_PREORDER_SELECT | OPT_DEGREE|0); + STOPTIMER(Building); + PRINTTIME("Building parenthesis struct", Building); + STARTTIMER(); + - // creates structure for tags TagName = (vector*)TN; 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; //Ensures that for small tag numbers, we are on an 8bit boundary. @@ -142,13 +101,13 @@ XMLTree::XMLTree( pb * const par, uint npar, vector * const TN, TagIdM 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; + delete bmb; free(tags); tags = NULL; STOPTIMER(Building); PRINTTIME("Building Tag Structure", Building); - + Text = (TextCollection*) TC; @@ -157,47 +116,41 @@ XMLTree::XMLTree( pb * const par, uint npar, vector * const TN, TagIdM free(empty_texts_bmp); empty_texts_bmp = NULL; - + disable_tc = dis_tc; - stream = NULL; - stream_fd = 0; + text_index_type = _index_type; std::cerr << "Number of distinct tags " << TagName->size() << "\n"; //std::cerr.flush(); } // ~XMLTree: frees memory of XML tree. -XMLTree::~XMLTree() - { +XMLTree::~XMLTree() + { int i; - destroyTree(Par); - free(Par); // frees the memory of struct Par - + bp_delete(Par); + Par = NULL; + delete tIdMap; tIdMap = NULL; - + delete TagName; TagName = NULL; - + delete Tags; Tags = NULL; - delete Text; + delete Text; Text = NULL; delete EBVector; EBVector = NULL; - if (stream != NULL){ - fclose(stream); - stream = NULL; - stream_fd = 0; - }; } -void XMLTree::print_stats() +void XMLTree::print_stats() { uint total_space = Tags->size()+sizeof(static_sequence*); total_space += sizeof(uint*)+sizeof(uint)*(2+uint_len(tags_blen,tags_len)); @@ -208,11 +161,10 @@ void XMLTree::print_stats() << " *total* " << total_space << endl; } -// Save: saves XML tree data structure to file. -void XMLTree::Save(int fd) +// Save: saves XML tree data structure to file. +void XMLTree::Save(int fd, char * name) { FILE *fp; - char filenameaux[1024]; int i; fp = fdopen(fd, "wa"); @@ -225,7 +177,7 @@ void XMLTree::Save(int fd) ufwrite(&ntags, sizeof(int), 1, fp); for (i = 0; iat(i).c_str()); - + // stores the tags Tags->save(fp); @@ -233,24 +185,40 @@ void XMLTree::Save(int fd) ufwrite(&tags_len,sizeof(uint),1,fp); ufwrite(tags_fix,sizeof(uint),uint_len(tags_blen,tags_len),fp); - // flags + // flags ufwrite(&disable_tc, sizeof(bool),1,fp); - + //text positions EBVector->save(fp); - - // stores the texts + + // stores the texts if (!disable_tc) { - Text->Save(fp); - }; + ufwrite(&text_index_type, sizeof(TextCollectionBuilder::index_type_t), 1, fp); - } + string file(name); + switch (text_index_type){ + case TextCollectionBuilder::index_type_default: + file.append(".default"); + break; + case TextCollectionBuilder::index_type_swcsa: + file.append(".swcsa"); + break; + case TextCollectionBuilder::index_type_rlcsa: + file.append(".rlcsa"); + break; + }; + + Text->Save(fp, file.c_str()); + + + } + } // Load: loads XML tree data structure from file. Returns // a pointer to the loaded data structure -XMLTree *XMLTree::Load(int fd, bool load_tc,int sample_factor) +XMLTree *XMLTree::Load(int fd, bool load_tc,int sample_factor, char * name) { FILE *fp; @@ -265,9 +233,7 @@ XMLTree *XMLTree::Load(int fd, bool load_tc,int sample_factor) XML_Tree = new XMLTree(); STARTTIMER(); // Load the tree structure - XML_Tree->Par = (bp *)umalloc(sizeof(bp)); - - loadTree(XML_Tree->Par, fp); + XML_Tree->Par = loadTree(fp); STOPTIMER(Loading); PRINTTIME("Loading parenthesis struct", Loading); STARTTIMER(); @@ -276,7 +242,7 @@ XMLTree *XMLTree::Load(int fd, bool load_tc,int sample_factor) XML_Tree->tIdMap = new std::unordered_map(); std::string s; int ntags; - + // Load the tag names ufread(&ntags, sizeof(int), 1, fp); @@ -285,10 +251,10 @@ XMLTree *XMLTree::Load(int fd, bool load_tc,int sample_factor) throw "Cannot read tag list"; s = buffer; // remove the trailing \n - s.erase(s.size()-1); - XML_Tree->TagName->push_back(s); + s.erase(s.size()-1); + XML_Tree->TagName->push_back(s); XML_Tree->tIdMap->insert(std::make_pair(s,i)); - + }; STOPTIMER(Loading); PRINTTIME("Loading tag names struct", Loading); @@ -297,7 +263,7 @@ XMLTree *XMLTree::Load(int fd, bool load_tc,int sample_factor) // 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"; + 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); @@ -311,32 +277,46 @@ XMLTree *XMLTree::Load(int fd, bool load_tc,int sample_factor) //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_sdarray::load(fp); - - STOPTIMER(Loading); - PRINTTIME("Loading text bitvector struct", Loading); - STARTTIMER(); - - // Not used - // loads the texts - if (!XML_Tree->disable_tc){ - XML_Tree->Text = TextCollection::Load(fp, TextCollection::index_mode_default, sample_factor); - } - else XML_Tree->Text = NULL; - STOPTIMER(Loading); - PRINTTIME("Loading TextCollection", Loading); - STARTTIMER(); + XML_Tree->EBVector = static_bitsequence_rrr02::load(fp); + + 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); + string file(name); + switch (XML_Tree->text_index_type){ + case TextCollectionBuilder::index_type_default: + file.append(".default"); + break; + case TextCollectionBuilder::index_type_swcsa: + file.append(".swcsa"); + break; + case TextCollectionBuilder::index_type_rlcsa: + file.append(".rlcsa"); + break; + }; + XML_Tree->Text = TextCollection::Load(fp, file.c_str(), TextCollection::index_mode_default, sample_factor); + + } + else XML_Tree->Text = NULL; + STOPTIMER(Loading); + PRINTTIME("Loading TextCollection", Loading); + STARTTIMER(); } else { XML_Tree->EBVector = NULL; @@ -344,122 +324,92 @@ XMLTree *XMLTree::Load(int fd, bool load_tc,int sample_factor) XML_Tree->disable_tc = true; }; - XML_Tree->stream = NULL; - XML_Tree->stream_fd = 0; - + return XML_Tree; } -// SubtreeSize(x): the number of nodes (and attributes) in the subtree of node 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) +int XMLTree::SubtreeElements(treeNode x) { - if (x == Root()) - 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))+1; - } -int XMLTree::SubtreeElements(treeNode x) - { - - int size = subtree_size(Par,x); + int size = bp_subtree_size(Par, x); if (x == Root()){ - x = fast_first_child(Par,x); + x = bp_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 fin = bp_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)); + y = Tags->select_next(ATTRIBUTE_TAG_ID, node2tagpos(y)); }; - return size; + 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) +bool XMLTree::IsLeaf(treeNode x) { NULLT_IF(x==NULLT); - return fast_isleaf(Par, x); - } + return bp_isleaf(Par, x); + } // IsAncestor(x,y): returns whether node x is ancestor of node y. -bool XMLTree::IsAncestor(treeNode x, treeNode y) +bool XMLTree::IsAncestor(treeNode x, treeNode y) { - return fast_is_ancestor(Par, x, y); + return bp_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 (!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::IsChild(treeNode x, treeNode y) { - return ((x != NULLT)&&(x==Root() || prev_sibling(Par,x) == (treeNode)-1)); + if (!bp_is_ancestor(Par, x, y)) return false; + return bp_depth(Par, x) == (bp_depth(Par, y) + 1); } // NumChildren(x): number of children of node x. Constant time with the data structure // of Sadakane. -int XMLTree::NumChildren(treeNode x) +int XMLTree::NumChildren(treeNode x) { - return degree(Par, x); + return bp_degree(Par, x); } // ChildNumber(x): returns i if node x is the i-th children of its parent. -int XMLTree::ChildNumber(treeNode x) +int XMLTree::ChildNumber(treeNode x) { - return child_rank(Par, x); + return bp_child_rank(Par, x); } // Depth(x): depth of node x, a simple binary rank on the parentheses sequence. -int XMLTree::Depth(treeNode x) +int XMLTree::Depth(treeNode x) { - return depth(Par, x); + return bp_depth(Par, x); } // Preorder(x): returns the preorder number of node x, just counting the tree // nodes (i.e., tags, it disregards the texts in the tree). -int XMLTree::Preorder(treeNode x) +int XMLTree::Preorder(treeNode x) { - return preorder_rank(Par, x); + return bp_preorder_rank(Par, x); } // Postorder(x): returns the postorder number of node x, just counting the tree // nodes (i.e., tags, it disregards the texts in the tree). -int XMLTree::Postorder(treeNode x) - { - return postorder_rank(Par, x); - } -/* -// Tag(x): returns the tag identifier of node x. -TagType XMLTree::Tag(treeNode x) +int XMLTree::Postorder(treeNode x) { - return fast_get_field(tags_fix,tags_blen,node2tagpos(x)); + return bp_postorder_rank(Par, 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 XMLTree::DocIds(treeNode x) { range r; if (x == NULLT) { @@ -467,8 +417,8 @@ range XMLTree::DocIds(treeNode x) r.max = NULLT; return r; }; - int min = EBVector->rank1(x-1); - int max = EBVector->rank1(x+2*subtree_size(Par, x)-2); + int min = EBVector->rank1(x-1); + int max = EBVector->rank1(x+2*bp_subtree_size(Par, x)-2); if (min==max) { // range is empty, no texts within the subtree of x r.min = NULLT; r.max = NULLT; @@ -480,132 +430,28 @@ range XMLTree::DocIds(treeNode x) 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);; - } // Child(x,i): returns the i-th child of node x, assuming it exists. -treeNode XMLTree::Child(treeNode x, int i) +treeNode XMLTree::Child(treeNode x, int i) { - if (i <= OPTD) return naive_child(Par, x, i); - else return child(Par, x, i); + if (i <= OPTD) return bp_naive_child(Par, x, i); + else return bp_child(Par, x, 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 fast_first_child(Par, x); - } - -treeNode XMLTree::FirstElement(treeNode x) - { - NULLT_IF(x==NULLT); - 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); - 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) - { - 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) - { - NULLT_IF(x==NULLT || x == Root() ); - 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) - { - 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 || fast_isleaf(Par,x)); - treeNode child; - child = fast_first_child(Par, x); // starts at first child of node x - if (Tag(child) == tag) - return child; - else - return TaggedFollowingSibling(child,tag); - } - -// TaggedSibling(x,tag): returns the first sibling of node x tagged tag, or NULLT if there is none. -treeNode XMLTree::TaggedFollowingSibling(treeNode x, TagType tag) -{ - NULLT_IF(x==NULLT); - treeNode sibling = fast_next_sibling(Par, x); - TagType ctag; - while (sibling != NULLT) { - ctag = Tag(sibling); - if (ctag == tag) // current sibling is labeled with tag of interest - return 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, TagIdSet *tags) { - - NULLT_IF(x==NULLT || fast_isleaf(Par,x)); + + NULLT_IF(x==NULLT || bp_isleaf(Par,x)); int i; - treeNode child = fast_first_child(Par, x); + treeNode child = bp_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; + return NULLT; } @@ -615,68 +461,34 @@ treeNode XMLTree::SelectFollowingSibling(treeNode x, TagIdSet *tags) NULLT_IF(x==NULLT); int i; TagType t; - treeNode sibling = fast_next_sibling(Par, x); + treeNode sibling = bp_next_sibling(Par, x); while (sibling != NULLT) { t = Tag(sibling); if (tags->find(t) != tags->end()) return sibling; sibling = fast_sibling(Par, sibling,t); } - return NULLT; - } - - -// 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::TaggedDescendant(treeNode x, TagType tag) - { - //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 (fast_is_ancestor(Par,x,y) ? y : NULLT); - } - - -treeNode XMLTree::SelectDescendant(treeNode x, TagIdSet *tags) - { - NULLT_IF (x ==NULLT || fast_isleaf(Par,x)); - int i; - treeNode min = NULLT; - treeNode fc = fast_first_child(Par,x); - treeNode aux; - TagIdSet::const_iterator tagit; - for (tagit = tags->begin(); tagit != tags->end(); tagit++) { - aux = TaggedDescendant(x, (TagType) *tagit); - if (aux == fc) return fc; - if (aux == NULLT) continue; - if ((min == NULLT) || (aux < min)) min = aux; - }; - return min; + return NULLT; } - // 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::TaggedPreceding(treeNode x, TagType tag) - { +treeNode XMLTree::TaggedPreceding(treeNode x, TagType tag) + { int r, s; treeNode node_s, root; r = (int)Tags->rank(tag, node2tagpos(x)-1); if (r==0) return NULLT; // there is no such node. s = (int)Tags->select(tag, r); - root = root_node(Par); + root = bp_root_node(Par); node_s = tagpos2node(s); - while (fast_is_ancestor(Par, node_s, x) && (node_s!=root)) { // the one that we found is an ancestor of x + while (bp_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 node_s = tagpos2node(s); } - return NULLT; // there is no such node + return NULLT; // there is no such node } @@ -684,53 +496,11 @@ treeNode XMLTree::TaggedPreceding(treeNode x, TagType tag) // the subtree of x. Returns NULLT if there is none. treeNode XMLTree::TaggedFollowing(treeNode x, TagType tag) { - 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::TaggedFollowingBelow(treeNode x, TagType tag, treeNode ancestor) -{ - // NULLT_IF (x == NULLT || x == Root() || x == ancestor); + NULLT_IF (x ==NULLT || x == Root()); + return tagpos2node(Tags->select_next(tag, bp_find_close(Par, x))); - //Special optimisation, test for the following sibling first - treeNode close = fast_find_close(Par, x); - /* - treeNode ns = close+1; - if (fast_inspect(Par,ns) == OP) { - TagType tagns = Tag(ns); - // cout << GetTagNameByRef(tagns) << endl; - //cout.flush(); - if (tagns == PCDATA_TAG_ID){ - close = ns+1; - ns = ns+2; - if (fast_inspect(Par,ns) != OP) - goto after; - tagns = Tag(ns); - }; - if (tagns == tag) - return ns; - }; - after: - */ - treeNode s = tagpos2node(Tags->select_next(tag, close)); - - 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()); - - 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 */ @@ -739,147 +509,106 @@ treeNode XMLTree::SelectFollowingBelow(treeNode x, TagIdSet *tags, treeNode ance NULLT_IF(x==NULLT || x==Root()); - treeNode close = fast_find_close(Par,x); + treeNode close = bp_find_close(Par,x); treeNode ns = close+1; - if ( (fast_inspect(Par,ns) == OP) && (tags->find(Tag(ns)) != tags->end())) + if ( (bp_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)); - - // The next sibling of x is guaranteed to be below ctx - // and is the node with lowest preorder which is after ctx. - // if we find it, we return early; - 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()) return min; - // else check whether if is in below the ctx node - - NULLT_IF (min == NULLT || min >= fast_find_close(Par, ancestor)); - - return min; - - } -treeNode XMLTree::SelectFollowingBefore(treeNode x, TagIdSet *tags, treeNode closing) - { - - NULLT_IF(x==NULLT || x==Root()); - int i; - treeNode min = NULLT; - treeNode ns = fast_next_sibling(Par, x); - treeNode close = ns - 1; - treeNode aux; TagIdSet::const_iterator tagit; - for (tagit = tags->begin(); tagit != tags->end(); tagit++) { + for (tagit = tags->begin(); tagit != tags->end(); ++tagit) { 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. - // if we find it, we return early; - - if (aux == ns ) return ns; 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. - NULLT_IF (min == NULLT || min >= closing); - - return min; - - } - + if (ancestor == Root() || min == NULLT || min < bp_find_close(Par, ancestor)) return min; + else return NULLT; + } // TaggedAncestor(x, tag): returns the closest ancestor of x tagged tag. Return // NULLT is there is none. treeNode XMLTree::TaggedAncestor(treeNode x, TagType tag) - { + { if (x == NULLT || x == Root()) return NULLT; - - treeNode s = parent(Par, x), r = Root(); + + treeNode s = bp_parent(Par, x), r = Root(); while (s != r) { if (Tag(s) == tag) return s; - s = parent(Par, s); + s = bp_parent(Par, s); } return 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 +// 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::MyText(treeNode x) +DocID XMLTree::MyText(treeNode x) { TagType tag = Tag(x); // seems faster than testing EBVector->access(x); if (tag == PCDATA_TAG_ID || tag == ATTRIBUTE_DATA_TAG_ID) - //if (EBVector->access(x)) - 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 +// 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) +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) +int XMLTree::TextXMLId(DocID d) { NULLT_IF(d == NULLT); int s = EBVector->select1(d+1); - return rank_open(Par, s) + d + 1; // +1 because root has preorder 1 - + return bp_rank_open(Par, s) + d + 1; // +1 because root has preorder 1 + } -// NodeXMLId(x): returns the preorder of node x in the tree consisting +// NodeXMLId(x): returns the preorder of node x in the tree consisting // of all tree nodes and all text nodes. Assumes that the tree root has // preorder 0; -int XMLTree::NodeXMLId(treeNode x) +int XMLTree::NodeXMLId(treeNode x) { NULLT_IF(x == NULLT); if (x == Root()) return 1; // root node has preorder 1 - return rank_open(Par, x) + EBVector->rank1(x-1); + return bp_rank_open(Par, x) + EBVector->rank1(x-1); } // ParentNode(d): returns the parent node of document identifier d. -treeNode XMLTree::ParentNode(DocID d) - { - NULLT_IF (d == NULLT); - return (treeNode) EBVector->select1(d+1); +treeNode XMLTree::ParentNode(DocID d) + { + NULLT_IF (d == NULLT); + return (treeNode) EBVector->select1(d+1); } // GetTagId: returns the tag identifier corresponding to a given tag name. // Returns NULLT in case that the tag name does not exists. TagType XMLTree::GetTagId(unsigned char *tagname) { - + string s = (char *) tagname; - TagIdMapIT it = tIdMap->find(s); + TagIdMapIT it = tIdMap->find(s); return (TagType) ((it != tIdMap->end()) ? it->second : -1); - + } @@ -891,7 +620,7 @@ unsigned char *XMLTree::GetTagName(TagType tagid) if ( tagid < 0 || tagid >= TagName->size()) return (unsigned char *) ""; strcpy((char *)s, (*TagName)[tagid].c_str()); - + return (s == NULL ? (unsigned char*) "" : s); } @@ -902,142 +631,133 @@ const unsigned char *XMLTree::GetTagNameByRef(TagType tagid) unsigned char *s; if ( tagid < 0 || tagid >= TagName->size()) return (unsigned char *) ""; - + return (const unsigned char *) (*TagName)[tagid].c_str(); - + } TagType XMLTree::RegisterTag(unsigned char *tagname) - { + { TagType id = XMLTree::GetTagId(tagname); if (id == NULLT) { - string s = (char *) tagname; - REGISTER_TAG(TagName,tIdMap,s); + string s = (char *) tagname; + REGISTER_TAG(TagName,tIdMap,s); }; - + return id; } treeNode XMLTree::Closing(treeNode x) { - return fast_find_close(Par,x); + return bp_find_close(Par,x); } -bool XMLTree::IsOpen(treeNode x) { return fast_inspect(Par,x); } +bool XMLTree::IsOpen(treeNode x) { return bp_inspect(Par,x); } //WARNING this uses directly the underlying implementation for plain text void XMLTree::Print(int fd,treeNode x, bool no_text){ - - int newfd = dup(fd); - stream = fdopen(newfd,"wa"); - if (stream == 0){ - perror(NULL); - return; - }; - if (buffer == 0) - buffer = new string(); + if (buffer == 0) { + buffer = new string(BUFFER_ALLOC, 0); + buffer->clear(); + print_stack = new std::vector(); + print_stack->reserve(256); + }; - FILE* fp = stream; - treeNode fin = fast_find_close(Par,x); + treeNode fin = bp_find_close(Par,x); treeNode n = x; TagType tag = Tag(n); - uchar * tagstr; + 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; + first_idx = first_text; else if (first_text == NULLT) - first_idx = first_att; + first_idx = first_att; else - first_idx = min(first_att,first_text); - + first_idx = min(first_att,first_text); + uchar * current_text=NULL; + if (first_idx != NULLT) - current_text = GetText(MyText(first_idx)); + current_text = GetText(MyTextUnsafe(first_idx)); + size_t read = 0; - std::vector st; - while (n <= fin){ - if (fast_inspect(Par,n)){ - if (tag == PCDATA_TAG_ID ) { - - if (no_text) - myfputs("<$/>",fp); - else{ - read = myfprintf((const char*) current_text, fp); - current_text += (read + 1); - }; - n+=2; // skip closing $ - tag = Tag(n); - - } - else { - myfputc('<',fp); - tagstr = (uchar*) GetTagNameByRef(tag); - myfputs((const char*) tagstr ,fp); - n++; - if (fast_inspect(Par,n)) { - st.push_back(tagstr); + + while (n <= fin){ + if (bp_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); - if (tag == ATTRIBUTE_TAG_ID){ - n++; - if (no_text) myfputs("><@@>",fp); - while (fast_inspect(Par,n)){ - if (no_text) { - myfputc('<',fp); - myfputs((const char*) &(GetTagNameByRef(Tag(n))[3]),fp); - myfputc('>',fp); - myfputs("<$@/>',fp); - n+= 4; - } - else { - myfputc(' ',fp); - myfputs((const char*) &(GetTagNameByRef(Tag(n))[3]),fp); - n++; - myfputs("=\"",fp); - read = myfprintf((const char*) current_text,fp); - current_text += (read + 1); - myfputc('"',fp); - n+=3; - } - }; - if (no_text) - myfputs("",fp); - else myfputc('>',fp); + + } else { + + _dputc('<',fd); + _dput_str((*TagName)[tag], fd); + n++; + if (bp_inspect(Par,n)) { + print_stack->push_back(&((*TagName)[tag])); + tag = Tag(n); + if (tag == ATTRIBUTE_TAG_ID){ + n++; + if (no_text) _dputs("><@@>",fd); + + while (bp_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 { - myfputc('>',fp); }; - } - else {// tag - myfputs("/>",fp); + }; + } else do { + _dputs("back()), fd); + _dputc('>', fd); + print_stack->pop_back(); n++; - tag=Tag(n); - }; - }; - } - else - do { - myfputs("', fp); - st.pop_back(); - n++; - }while (!fast_inspect(Par,n) && !st.empty()); - tag=Tag(n); - }; - myfputc('\n',fp); - mybufferflush(fp); - //fflush(fp); - fclose(fp); + } while (!(bp_inspect(Par,n) || print_stack->empty())); + tag = Tag(n); + }; + _dputc('\n', fd); + //_flush(fd); }