X-Git-Url: http://git.nguyen.vg/gitweb/?a=blobdiff_plain;f=XMLTree.cpp;h=06aaba0517bf1128628a685fcaa49dc2e9ff6c31;hb=9bb139eb78d143264e4d4dc6b3f9f1be3874ec6e;hp=ae80fc2a489680d270c6fba2d59939a8c9bddc00;hpb=b53633fb64f387edb5cebefbb3308b6347b2389c;p=SXSI%2FXMLTree.git diff --git a/XMLTree.cpp b/XMLTree.cpp index ae80fc2..06aaba0 100644 --- a/XMLTree.cpp +++ b/XMLTree.cpp @@ -1,5 +1,8 @@ +#include "basics.h" +//#include +#include #include "XMLTree.h" -#include +#include "timings.h" // 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, @@ -8,386 +11,426 @@ // 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; +static treeNode tagpos2node(int t) + { + return (treeNode) t; + } + +static int bits8 (int t ) { + int r = bits(t); + if (r <= 8) + return 8; + else if (r <= 16) + return 16; + else + return r; } // tree node -> tag position -inline int node2tagpos(treeNode x) { - return (int)x; +static int node2tagpos(treeNode x) +{ + return (int)x; } +static int fast_find_close(bp *b,int s) +{ + return fwd_excess(b,s,-1); +} -//KIM OJO to prevent suprious "unused result" warnings - -inline void ufread(void *ptr, size_t size, size_t nmemb, FILE *stream){ - size_t res; - res = fread(ptr,size,nmemb,stream); - if (res < nmemb) - throw "ufread I/O error"; +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; +} - return; +static treeNode fast_first_child(bp *Par, treeNode x) +{ + x = x+1; + return (fast_inspect(Par,x) == OP) ? x : NULLT; } -inline void ufwrite(const void *ptr, size_t size, size_t nmemb, FILE *stream){ - size_t res; - res = fwrite(ptr,size,nmemb,stream); - if (res < nmemb) - throw "ufwrite I/O error"; - return; +static treeNode fast_next_sibling(bp* Par,treeNode x) +{ + x = fwd_excess(Par,x,0); + return (fast_inspect(Par,x) == OP) ? x : NULLT; } -// OJO to fail cleanly while doing a realloc -// if we can't realloc we are pretty much screwed anyway but -// it makes the code clearer to not have a bunch of if (!ptr) { printf("..."); exit(1); }; -inline void * urealloc(void *ptr, size_t size){ - void * dest = realloc(ptr,size); - //don't fail if we requested size 0 - if (dest == NULL && size > 0 ) - throw std::bad_alloc(); - return dest; +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); + +} +static bool fast_isleaf(bp* Par,treeNode x){ + return (fast_inspect(Par,x+1) == CP ? true : false); } -inline void * ucalloc(size_t nmemb, size_t size){ - void * dest = calloc(nmemb,size); - //don't fail if we requested size 0 - if (dest == NULL && nmemb > 0 && size > 0 ) - throw std::bad_alloc(); - return dest; +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); } -inline void * umalloc(size_t size){ - void * dest = malloc(size); - if (dest == NULL && size > 0) - throw std::bad_alloc(); - return dest; +static uint fast_get_field(uint* A,int len, int idx) +{ + 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); + }; + } -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)); - cout << "Space usage for XMLTree:" << endl - << " - tags static_sequence: " << Tags->size()+sizeof(static_sequence*) << endl - << " - tags access array: " << sizeof(uint*)+sizeof(uint)*(2+uint_len(tags_blen,tags_len)) << endl - << " ... add Diego structures ... " << endl - << " *total* " << total_space << endl; +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)); } -// Save: saves XML tree data structure to file. -void XMLTree::Save(unsigned char *filename) + +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) { + // 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(); - FILE *fp; - char filenameaux[1024]; + + // 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. + //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; + stream = NULL; + stream_fd = 0; + std::cerr << "Number of distinct tags " << TagName->size() << "\n"; + //std::cerr.flush(); + } + + +// ~XMLTree: frees memory of XML tree. +XMLTree::~XMLTree() + { int i; + + destroyTree(Par); + free(Par); // frees the memory of struct Par - sprintf(filenameaux, "%s.srx", filename); - fp = fopen(filenameaux, "w"); - if (fp == NULL) { - printf("Error: cannot create file %s to store the tree structure of XML collection\n", filenameaux); - exit(1); - } + delete tIdMap; + tIdMap = NULL; + + delete TagName; + TagName = NULL; + delete Tags; + Tags = NULL; + + delete Text; + Text = NULL; + + delete EBVector; + EBVector = NULL; + if (stream != NULL){ + fclose(stream); + stream = NULL; + stream_fd = 0; + }; + + } + + +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)); + cout << "Space usage for XMLTree:" << endl + << " - tags static_sequence: " << Tags->size()+sizeof(static_sequence*) << endl + << " - tags access array: " << sizeof(uint*)+sizeof(uint)*(2+uint_len(tags_blen,tags_len)) << endl + << " ... add Diego structures ... " << endl + << " *total* " << total_space << endl; + } + +// Save: saves XML tree data structure to file. +void XMLTree::Save(int fd) + { + FILE *fp; + char filenameaux[1024]; + int i; + + fp = fdopen(fd, "wa"); // first stores the tree topology saveTree(Par, fp); - + // stores the table with tag names - ufwrite(&ntagnames, sizeof(int), 1, fp); - for (i=0; isave(fp); + int ntags = TagName->size(); + + ufwrite(&ntags, sizeof(int), 1, fp); + for (i = 0; iat(i).c_str()); + // stores the tags Tags->save(fp); - ufwrite(&tags_blen,sizeof(uint),1,fp); - ufwrite(&tags_len,sizeof(uint),1,fp); - ufwrite(tags_fix,sizeof(uint),uint_len(tags_blen,tags_len),fp); + ufwrite(&tags_blen,sizeof(uint),1,fp); + ufwrite(&tags_len,sizeof(uint),1,fp); + ufwrite(tags_fix,sizeof(uint),uint_len(tags_blen,tags_len),fp); + // flags + ufwrite(&disable_tc, sizeof(bool),1,fp); + + //text positions + EBVector->save(fp); + // stores the texts if (!disable_tc) { Text->Save(fp); - int st = CachedText.size(); - ufwrite(&st, sizeof(int),1,fp); - for (int i = 0; i< CachedText.size(); i++){ - st = CachedText.at(i).size(); - ufwrite(&st, sizeof(int),1,fp); - ufwrite(CachedText.at(i).c_str(),sizeof(char),1+CachedText.at(i).size(),fp); - }; }; - fclose(fp); + } // Load: loads XML tree data structure from file. Returns // a pointer to the loaded data structure -XMLTree *XMLTree::Load(unsigned char *filename, int sample_rate_text) +XMLTree *XMLTree::Load(int fd, bool load_tc,int sample_factor) { - FILE *fp; char buffer[1024]; XMLTree *XML_Tree; int i; - size_t s_tree = 0; - long s_text = 0; - size_t s_tags = 0; - - // first load the tree topology - sprintf(buffer, "%s.srx", filename); - fp = fopen(buffer, "r"); - if (fp == NULL) { - printf("Error: cannot open file %s to load the tree structure of XML collection\n", buffer); - exit(1); - } - XML_Tree = new XMLTree(); + + fp = fdopen(fd, "r"); + + XML_Tree = new XMLTree(); + STARTTIMER(); + // Load the tree structure XML_Tree->Par = (bp *)umalloc(sizeof(bp)); loadTree(XML_Tree->Par, fp); + STOPTIMER(Loading); + PRINTTIME("Loading parenthesis struct", Loading); + STARTTIMER(); - s_tree += sizeof(bp); - - // stores the table with tag names - ufread(&XML_Tree->ntagnames, sizeof(int), 1, fp); + XML_Tree->TagName = new vector(); + XML_Tree->tIdMap = new std::unordered_map(); - s_tree += sizeof(int); - - XML_Tree->TagName = (unsigned char **)umalloc(XML_Tree->ntagnames*sizeof(unsigned char *)); + string s; + int ntags; - s_tags += sizeof(unsigned char*)*XML_Tree->ntagnames; - + // Load the tag names + ufread(&ntags, sizeof(int), 1, fp); - for (i=0; intagnames;i++) { - - // OJO Kim is it needed ? - int k = feof(fp); - - - // fscanf chokes on "\n" which is the case for the root element - char * r = fgets(buffer,1023,fp); - // int r = fscanf(fp, "%s\n",buffer); + for (i=0; iTagName->push_back(s); + XML_Tree->tIdMap->insert(std::make_pair(s,i)); + + }; + STOPTIMER(Loading); + PRINTTIME("Loading tag names struct", Loading); + STARTTIMER(); - // strlen is actually the right size, since there is a trailing '\n' - int len = strlen((const char*)buffer); - XML_Tree->TagName[i] = (unsigned char *)ucalloc(len,sizeof(char)); - strncpy((char *)XML_Tree->TagName[i], (const char *)buffer,len - 1); - s_tags+= len*sizeof(char); - } - - // loads the flags - - ufread(&(XML_Tree->indexing_empty_texts), sizeof(bool), 1, fp); - ufread(&(XML_Tree->initialized), sizeof(bool), 1, fp); - ufread(&(XML_Tree->finished), sizeof(bool), 1, fp); - ufread(&(XML_Tree->disable_tc), sizeof(bool), 1, fp); + // 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); + //cout << "Tags test: " << XML_Tree->Tags->test(seq,XML_Tree->tags_len) << endl; + //XML_Tree->Tags->test(seq,XML_Tree->tags_len); + //delete [] seq; + /// End ugly tests - s_tree+=sizeof(bool)*4; + 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(); - if (!(XML_Tree->indexing_empty_texts)) XML_Tree->EBVector = static_bitsequence_rrr02::load(fp); - - s_tree+= XML_Tree->EBVector->size(); + // loads the flags - // loads the tags - XML_Tree->Tags = static_sequence::load(fp); - ufread(&XML_Tree->tags_blen,sizeof(uint),1,fp); - 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); - s_tree+=2*sizeof(uint)+sizeof(uint)*uint_len(XML_Tree->tags_blen,XML_Tree->tags_len); - s_tree+= XML_Tree->Tags->size(); - - /// 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); - cout << "Tags test: " << XML_Tree->Tags->test(seq,XML_Tree->tags_len) << endl; - delete [] seq;*/ - /// End ugly tests - - s_text = ftell(fp); + 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::InitTextCollection(sample_rate_text); - XML_Tree->Text->Load(fp,sample_rate_text); - int sst; - int st; - ufread(&sst, sizeof(int),1,fp); - for (int i=0;iCachedText.push_back(cppstr); - free(str); - }; - + XML_Tree->Text = TextCollection::Load(fp,sample_factor); + } + else XML_Tree->Text = NULL; + STOPTIMER(Loading); + PRINTTIME("Loading TextCollection", Loading); + STARTTIMER(); } else { + XML_Tree->EBVector = NULL; XML_Tree->Text = NULL; - } - s_text = ftell(fp) - s_text; + XML_Tree->disable_tc = true; + }; + XML_Tree->stream = NULL; + XML_Tree->stream_fd = 0; - - - fclose(fp); - - /*std::cerr << "Tree part is " << s_tree/1024 << " Kbytes,\n" - << "with node->tagid part " << XML_Tree->Tags->size()/1024+(uint_len(XML_Tree->tags_blen,XML_Tree->tags_len)*sizeof(uint))/1024 << "Kbytes \n" - << "size of Tag part : " << XML_Tree->Tags->length () << " elements\n" - << "sizof(unsigned int)* " << XML_Tree->Tags->length () << " = " << - sizeof(unsigned int) * XML_Tree->Tags->length () / 1024 << " Kbytes\n" - << "Tag part is " << s_tags/1024 << " Kbytes,\n" - << "Text collection is " << s_text/1024 << " Kbytes \n";*/ - XML_Tree->print_stats(); return XML_Tree; } -// ~XMLTree: frees memory of XML tree. -XMLTree::~XMLTree() - { - int i; - - destroyTree(Par); - free(Par); // frees the memory of struct Par - - for (i=0; i~static_bitsequence_rrr02(); - delete EBVector; - EBVector = NULL; - } - - //Tags->~static_sequence_wvtree(); - delete Tags; - Tags = NULL; - - //Text->~TextCollection(); - delete Text; - Text = NULL; - - initialized = false; - finished = false; - } - -// root(): returns the tree root. -treeNode XMLTree::Root() - { - if (!finished) { - fprintf(stderr, "Root() : Error: data structure has not been constructed properly\n"); - exit(1); - } - return root_node(Par); - } // SubtreeSize(x): the number of nodes (and attributes) in the subtree of node x. int XMLTree::SubtreeSize(treeNode x) { - if (!finished) { - fprintf(stderr, "Error: data structure has not been constructed properly\n"); - exit(1); - } 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 (!finished) { - fprintf(stderr, "Error: data structure has not been constructed properly\n"); - exit(1); - } 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); } +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) { - if (!finished) { - fprintf(stderr, "Error: data structure has not been constructed properly\n"); - exit(1); - } - - 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 (!finished) { - fprintf(stderr, "Error: data structure has not been constructed properly\n"); - exit(1); - } - - 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) + { + 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. int XMLTree::NumChildren(treeNode x) { - if (!finished) { - fprintf(stderr, "Error: data structure has not been constructed properly\n"); - exit(1); - } - return degree(Par, x); } // ChildNumber(x): returns i if node x is the i-th children of its parent. int XMLTree::ChildNumber(treeNode x) { - if (!finished) { - fprintf(stderr, "Error: data structure has not been constructed properly\n"); - exit(1); - } - return child_rank(Par, x); } // Depth(x): depth of node x, a simple binary rank on the parentheses sequence. int XMLTree::Depth(treeNode x) { - if (!finished) { - fprintf(stderr, "Error: data structure has not been constructed properly\n"); - exit(1); - } - return depth(Par, x); } @@ -395,11 +438,6 @@ int XMLTree::Depth(treeNode x) // nodes (i.e., tags, it disregards the texts in the tree). int XMLTree::Preorder(treeNode x) { - if (!finished) { - fprintf(stderr, "Error: data structure has not been constructed properly\n"); - exit(1); - } - return preorder_rank(Par, x); } @@ -407,324 +445,237 @@ int XMLTree::Preorder(treeNode x) // nodes (i.e., tags, it disregards the texts in the tree). int XMLTree::Postorder(treeNode x) { - if (!finished) { - fprintf(stderr, "Error: data structure has not been constructed properly\n"); - exit(1); - } return postorder_rank(Par, x); } - +/* // Tag(x): returns the tag identifier of node x. TagType XMLTree::Tag(treeNode x) { - if (!finished) { - fprintf(stderr, "Error: data structure has not been constructed properly\n"); - exit(1); - } - - return get_field(tags_fix,tags_blen,node2tagpos(x)); //Tags->access(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) { - if (!finished) { - fprintf(stderr, "Error: data structure has not been constructed properly\n"); - exit(1); - } - - range r; - if (x == NULLT) - { - r.min = NULLT; - r.max = NULLT; - return r; - }; - - - if (indexing_empty_texts) { // faster, no rank needed - r.min = x; - r.max = x+2*subtree_size(Par, x)-2; - } - else { // we are not indexing empty texts, we need rank - 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 (!finished) { - fprintf(stderr, "Error: data structure has not been constructed properly\n"); - exit(1); - } 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) { - if (!finished) { - fprintf(stderr, "Error: data structure has not been constructed properly\n"); - exit(1); - } - if (i <= OPTD) return naive_child(Par, x, i); else return 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) { - if (!finished) { - fprintf(stderr, "Error: data structure has not been constructed properly\n"); - exit(1); - } + NULLT_IF(x==NULLT); + return fast_first_child(Par, x); + } - return 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; +} +value XMLTree::CamlFirstElement(value x) +{ + return Val_int(FirstElement(Int_val(x))); +} +value XMLTree::CamlNextElement(value x) +{ + return Val_int(NextElement(Int_val(x))); +} + +extern "C" value caml_cpp_fast_first_element(value xmltree, value node){ + return XMLTREE(xmltree)->CamlFirstElement(node); +} + +extern "C" value caml_cpp_fast_next_element(value xmltree, value node){ + return XMLTREE(xmltree)->CamlNextElement(node); +} + +// 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) { - if (!finished) { - fprintf(stderr, "Error: data structure has not been constructed properly\n"); - exit(1); - } - if (x == Root() || x==NULLT) - return NULLT; - - return next_sibling(Par, 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) { - if (!finished) { - fprintf(stderr, "Error: data structure has not been constructed properly\n"); - exit(1); - } - - return prev_sibling(Par, x); + NULLT_IF(x==NULLT); + return prev_sibling(Par, x); } -// TaggedChild(x,i,tag): returns the i-th child of node x tagged tag, or NULLT if there is none. +// 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, int i, TagType tag) +treeNode XMLTree::TaggedChild(treeNode x, TagType tag) { - if (!finished) { - fprintf(stderr, "Error: data structure has not been constructed properly\n"); - exit(1); - } - - treeNode child; - child = first_child(Par, x); // starts at first child of node x - if (child==(treeNode)-1) return NULLT; // node x is a leaf, there is no such child - while (child!=(treeNode)-1) { - if (get_field(tags_fix,tags_blen,node2tagpos(child)) /*Tags->access(node2tagpos(child))*/ == tag) { // current child is labeled with tag of interest - i--; - if (i==0) return child; // we have seen i children of x tagged tag, this is the one we are looking for - } - child = next_sibling(Par, x); // OK, let's try with the next child - } - return NULLT; // no such child was found + 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); } -// TaggedDesc(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) - { - if (!finished) { - fprintf(stderr, "Error: data structure has not been constructed properly\n"); - exit(1); - } - - int r, s; - treeNode y; - if (isleaf(Par,x)) - return NULLT; - - r = (int) Tags->rank(tag, node2tagpos(x)); - s = (int) Tags->select(tag, r+1); - if (s == -1) return NULLT; // there is no such node - y = tagpos2node(s); // transforms the tag position into a node position - if (!is_ancestor(Par, x, y)) return NULLT; // the next node tagged tag (in preorder) is not within the subtree of x. - else return y; - } - -treeNode XMLTree::TaggedDescOnly(treeNode x,TagType *desctags, unsigned int dtlen) +// 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) { - - treeNode res,y; - if (isleaf(Par,x)) - return NULLT; - - res=NULLT; - for (unsigned int i = 0; i < dtlen; i ++ ) - { - y = TaggedDesc(x,desctags[i]); - res = (res == NULLT) || (( res != NULLT) && (y =! NULLT) && y < res) ? y : res; - - }; - - return res; - + 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::TaggedBelow(treeNode x, TagType *childtags, unsigned int ctlen, - TagType *desctags, unsigned int dtlen) +treeNode XMLTree::SelectChild(treeNode x, TagIdSet *tags) { - treeNode fs,y,res; - TagType tag; - - if (isleaf(Par,x)) - return NULLT; - res = NULLT; - fs = first_child(Par,x); - while (fs != NULLT) { - tag = get_field(tags_fix,tags_blen,node2tagpos(fs)); - - /* Check for first_child */ - for (unsigned int i = 0; i < ctlen; i++) { - if (childtags[i] == tag) - return fs; - }; - - for (unsigned int i = 0; i < dtlen; i++) - if (desctags[i] == tag) - return fs; - - /* check in the descendants */ - res = NULLT; - for (unsigned int i = 0; i < dtlen; i ++ ){ - /* maybe inline by hand */ - y = TaggedDesc(fs,desctags[i]); - res = (res==NULLT || (y != NULLT) &&(y < res)) ? y : res; - }; - if (res != NULLT) - return res; - - fs = next_sibling(Par,fs); - }; - return res; - + NULLT_IF(x==NULLT || fast_isleaf(Par,x)); + int i; + 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::TaggedFollOnly(treeNode x,TagType *folltags, unsigned int ftlen,treeNode root) -{ - treeNode res,y,lim; - lim = find_close(Par,root); - res=NULLT; - for (unsigned int i = 0; i < ftlen; i ++ ) - { - y = TaggedFoll(x,folltags[i]); - res = (res == NULLT) || (( res != NULLT) && (y =! NULLT) && y < res) ? y : res; - - }; - - return res < lim ? res : NULLT; - -} -treeNode XMLTree::TaggedDescOrFollOnly(treeNode x,TagType *folltags, unsigned int ftlen,treeNode root) +treeNode XMLTree::SelectFollowingSibling(treeNode x, TagIdSet *tags) { - treeNode res,y,lim; - int r,s; - lim = find_close(Par,root); - res=NULLT; - for (unsigned int i = 0; i < ftlen; i ++ ) - { - - r = (int) Tags->rank(folltags[i], node2tagpos(x)); - s = (int) Tags->select(folltags[i], r+1); - if (s == -1) - y = NULLT; // there is no such node - else { - y = tagpos2node(s); - if (y >= lim) - y = NULLT; - }; - res = (res == NULLT) || (( res != NULLT) && (y =! NULLT) && y < res) ? y : res; - - }; - - return res < lim ? res : NULLT; - -} + NULLT_IF(x==NULLT); + int i; + TagType t; + treeNode sibling = fast_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; + } -// TaggedNext(x,tag): returns the first node tagged tag with larger preorder than x -// Returns NULLT if there is none. -treeNode XMLTree::TaggedNext(treeNode x, TagType *childtags, unsigned int ctlen, - TagType *folltags, unsigned int flen,treeNode root) +// 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) { - treeNode y,old_y,lim,res; - TagType tag; - if (x == NULLT || x == Root()) - return NULLT; + //NULLT_IF(x==NULLT || fast_isleaf(Par,x)); + int s = (int) Tags->select_next(tag,node2tagpos(x)); + NULLT_IF (s == -1); - lim = find_close(Par,root); + treeNode y = tagpos2node(s); // transforms the tag position into a node position + + return (fast_is_ancestor(Par,x,y) ? y : NULLT); + } - res = NULLT; - - y = next_sibling(Par,x); - while (y != NULLT) { - tag = get_field(tags_fix,tags_blen,node2tagpos(y)); - for(unsigned int i = 0; i < ctlen;i++) - if (childtags[i] == tag) - return y; - - for(unsigned int i = 0; i < flen;i++) - if (folltags[i] == tag) - return y; - res = TaggedBelow(y,NULL,0,folltags,flen); - if (res != NULLT) - return res; - - y = next_sibling(Par,y); - }; - //Found nothing in the following sibling of x. - res = NULLT; - for(unsigned int i = 0; i < flen;i++){ - y = TaggedFoll(x,folltags[i]); - res = (y!= x && (res == NULLT || (y != NULLT && y < res)))? y : res; +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 res < lim ? res : NULLT; - + 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) - { - if (!finished) { - fprintf(stderr, "Error: data structure has not been constructed properly\n"); - exit(1); - } - +treeNode XMLTree::TaggedPreceding(treeNode x, TagType tag) + { int r, s; treeNode node_s, root; r = (int)Tags->rank(tag, node2tagpos(x)-1); @@ -732,7 +683,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 @@ -744,163 +695,176 @@ 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) { - if (!finished) { - fprintf(stderr, "Error: data structure has not been constructed properly\n"); - exit(1); - } + NULLT_IF (x ==NULLT || x == Root()); + return tagpos2node(Tags->select_next(tag,fast_find_close(Par, x))); - int r, s; - if (x ==NULLT || x == Root()) - return NULLT; - - r = (int) Tags->rank(tag, find_close(Par, x)); - s = (int) Tags->select(tag, r+1); // select returns -1 in case that there is no r+1-th tag. - if (s==-1) return NULLT; - else return tagpos2node(s); } -// 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::TaggedFollBelow(treeNode x, TagType tag, treeNode root) +// 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); + + //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 */ +treeNode XMLTree::SelectFollowingBelow(treeNode x, TagIdSet *tags, treeNode ancestor) { - int r, s; - int lim = node2tagpos(find_close(Par,root)); - if (x ==NULLT || x == Root()) - return NULLT; - - r = (int) Tags->rank(tag,find_close(Par,x)); - s = (int) Tags->select(tag, r+1); // select returns -1 in case that there is no r+1-th tag. - if (s==-1 || s >= lim) - return NULLT; - else - return tagpos2node(s); - } + 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; -// TaggedFollowingSibling(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::TaggedFollowingSibling(treeNode x, TagType tag) + 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) { - if (!finished) { - fprintf(stderr, "Error: data structure has not been constructed properly\n"); - exit(1); - } - int r, s; - treeNode ns = next_sibling(Par,x); + 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++) { - if (x == NULLT || x == Root() || ns == -1) - return NULLT; + 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. - r = (int) Tags->rank(tag, node2tagpos(ns)-1); - s = (int) Tags->select(tag, r+1); // select returns -1 in case that there is no r+1-th tag. - if (s==-1) return NULLT; - else return tagpos2node(s); + 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. treeNode XMLTree::TaggedAncestor(treeNode x, TagType tag) - { - if (!finished) { - fprintf(stderr, "Error: data structure has not been constructed properly\n"); - exit(1); - } - + { if (x == NULLT || x == Root()) return NULLT; 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; } -// PrevText(x): returns the document identifier of the text to the left -// of node x, or NULLT if x is the root node or the text is empty. -// Assumes Doc ids start from 0. -DocID XMLTree::PrevText(treeNode x) - { - if (!finished) { - fprintf(stderr, "Error: data structure has not been constructed properly\n"); - exit(1); - } - - if (x == Root()) return NULLT; - if (indexing_empty_texts) // faster, no rank needed - return (DocID)x-1; - else { // we are not indexing empty texts, rank is needed - if (EBVector->access(x-1) == 0) - return (DocID)NULLT; // there is no text to the left of node (text is empty) - else - return (DocID)EBVector->rank1(x-1)-1; //-1 because document ids start from 0 - } - } - -// NextText(x): returns the document identifier of the text to the right -// of node x, or NULLT if x is the root node. Assumes Doc ids start from 0. -DocID XMLTree::NextText(treeNode x) - { - if (!finished) { - fprintf(stderr, "Error: data structure has not been constructed properly\n"); - exit(1); - } - - if (x == Root()) return NULLT; - if (indexing_empty_texts) // faster, no rank needed - return (DocID)x+2*subtree_size(Par, x)-1; - else { // we are not indexing empty texts, rank is needed - int p = x+2*subtree_size(Par, x)-1; - if (EBVector->access(p) == 0) // there is no text to the right of node - return (DocID)NULLT; - else - return (DocID)EBVector->rank1(p)-1; //-1 because document ids start from 0 - } - } // 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) - { - if (!finished) { - fprintf(stderr, "Error: data structure has not been constructed properly\n"); - exit(1); - } - - if (!IsLeaf(x)) return NULLT; - if (indexing_empty_texts) // faster, no rank needed - return (DocID)x; - else { // we are not indexing empty texts, rank is needed - if (EBVector->access(x) == 0) // there is no text below node x - return (DocID)NULLT; - else - return (DocID)EBVector->rank1(x)-1; //-1 because document ids start from 0 - } - } - +{ + 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) 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) { - if (!finished) { - fprintf(stderr, "Error: data structure has not been constructed properly\n"); - exit(1); - } - - if (indexing_empty_texts) - return d + rank_open(Par, d)+1; // +1 because root has preorder 1 - else { // slower, needs rank and select - int s = EBVector->select1(d+1); - return rank_open(Par, s) + d + 1; // +1 because root has preorder 1 - } + NULLT_IF(d == NULLT); + int s = EBVector->select1(d+1); + return rank_open(Par, s) + d + 1; // +1 because root has preorder 1 + } // NodeXMLId(x): returns the preorder of node x in the tree consisting @@ -908,393 +872,183 @@ int XMLTree::TextXMLId(DocID d) // preorder 0; int XMLTree::NodeXMLId(treeNode x) { - if (!finished) { - fprintf(stderr, "Error: data structure has not been constructed properly\n"); - exit(1); - } - - if (indexing_empty_texts) - return x - 1 + rank_open(Par, x); - else { - if (x == Root()) return 1; // root node has preorder 1 - else - return rank_open(Par, x) + EBVector->rank1(x-1); - } + NULLT_IF(x == NULLT); + if (x == Root()) return 1; // root node has preorder 1 + return rank_open(Par, x) + EBVector->rank1(x-1); } // ParentNode(d): returns the parent node of document identifier d. treeNode XMLTree::ParentNode(DocID d) - { - if (!finished) { - fprintf(stderr, "Error: data structure has not been constructed properly\n"); - exit(1); - } - - if (d == NULLT) - return NULLT; - - int s; - // OJO : Kim : I added the d+1. before that, else branch was - // EBVector->select1(d) - // and gave wrong results (I'm really poking a bear with a stick here). - if (indexing_empty_texts) s = d; - else s = EBVector->select1(d+1); - - if (inspect(Par,s) == CP) // is a closing parenthesis - return parent(Par, find_open(Par, s)); - else // is an opening parenthesis - return (treeNode)s; - - } -treeNode XMLTree::PrevNode(DocID d) - { - if (!finished) { - fprintf(stderr, "Error: data structure has not been constructed properly\n"); - exit(1); - } - - if (d == NULLT) - return NULLT; - - int s; - - if (indexing_empty_texts) s = d; - else s = EBVector->select1(d+1); - if (s == -1) - return NULLT; - - if (inspect(Par,s) == CP) // is a closing parenthesis - return find_open(Par, s); - else // is an opening parenthesis - return NULLT; - - } - - -// OpenDocument(empty_texts): it starts the construction of the data structure for -// the XML document. Parameter empty_texts indicates whether we index empty texts -// in document or not. Returns a non-zero value upon success, NULLT in case of error. -int XMLTree::OpenDocument(bool empty_texts, int sample_rate_text,bool dtc) - { - initialized = true; - finished = false; - found_attributes = false; - npar = 0; - parArraySize = 1; - ntagnames = 4; - disable_tc = dtc; - - indexing_empty_texts = empty_texts; - - par_aux = (pb *)umalloc(sizeof(pb)*parArraySize); - - tags_aux = (TagType *) umalloc(sizeof(TagType)); - - TagName = (unsigned char **) umalloc(4*sizeof(unsigned char*)); - - TagName[0] = (unsigned char *) umalloc(4*sizeof(unsigned char)); - - strcpy((char *) TagName[0], "<@>"); - - TagName[1] = (unsigned char *) umalloc(4*sizeof(unsigned char)); - - strcpy((char *) TagName[1], "<$>"); - - //OJO need to put these in the table too. - TagName[2] = (unsigned char *) umalloc(5*sizeof(unsigned char)); - - strcpy((char *) TagName[2], "/<@>"); - - TagName[3] = (unsigned char *) umalloc(5*sizeof(unsigned char)); - - strcpy((char *) TagName[3], "/<$>"); - - - if (!indexing_empty_texts) - empty_texts_aux = (unsigned int *)umalloc(sizeof(unsigned int)); - - - - Text = TextCollection::InitTextCollection((unsigned)sample_rate_text); - - return 1; // indicates success in the initialization of the data structure + { + NULLT_IF (d == NULLT); + return (treeNode) EBVector->select1(d+1); } -// CloseDocument(): it finishes the construction of the data structure for the XML -// document. Tree and tags are represented in the final form, dynamic data -// structures are made static, and the flag "finished" is set to true. After that, -// the data structure can be queried. -int XMLTree::CloseDocument() +// 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) { - if (!initialized) { // data structure has not been initialized properly - fprintf(stderr, "Error: data structure has not been initialized properly (by calling method OpenDocument)\n"); - return NULLT; - } - - // closing parenthesis for the tree root - par_aux = (pb *)urealloc(par_aux, sizeof(pb)*(1+npar/(8*sizeof(pb)))); - - // creates the data structure for the tree topology - Par = (bp *)umalloc(sizeof(bp)); - bp_construct(Par, npar, par_aux, OPT_DEGREE|0); - // creates structure for tags - - // If we found an attribute then "<@>" is present in the tree - // if we didn't then it is not. "<$>" is never present in the tree - //uint max_tag = 0; - //for(uint i=0;i<(uint)npar-1;i++) - // max_tag = max(max_tag,tags_aux[i]); - //max_tag++; - //tags_aux = (TagType *) urealloc(tags_aux, sizeof(TagType)*(npar + 1)); - //tags_aux[npar++] = max_tag; - //int ntagsize = found_attributes ? 2*ntagnames-1 : 2*ntagnames - 2; - int ntagsize = 2*ntagnames + 2; - - //static_bitsequence_builder * bmb = new static_bitsequence_builder_brw32(20); - //static_permutation_builder * pmb = new static_permutation_builder_mrrr(PERM_SAMPLE, bmb); - //static_sequence_builder * ssb = new static_sequence_builder_gmr_chunk(bmb, pmb); - static_bitsequence_builder * bmb = new static_bitsequence_builder_sdarray(); - alphabet_mapper *am = new alphabet_mapper_none(); - //wt_coder * wc = new wt_coder_huff((uint*)tags_aux,npar,am); - //Tags = new static_sequence_wvtree((uint*)tags_aux,npar,wc ,bmb, am); - //Tags = new static_sequence_gmr((uint *) tags_aux, (uint) npar,ntagsize, bmb, ssb); - Tags = new static_sequence_bs((uint*)tags_aux,npar,am,bmb); - - cout << "Tags test: " << Tags->test((uint*)tags_aux,npar) << endl; - - tags_blen = bits(max_tag); - 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_aux[i]); - - delete bmb; - //delete pmb; - //delete ssb; - - - // makes the text collection static - if (!disable_tc) - Text->MakeStatic(); + + string s = (char *) tagname; + TagIdMapIT it = tIdMap->find(s); + return (TagType) ((it != tIdMap->end()) ? it->second : -1); - // creates the data structure marking the non-empty texts (just in the case it is necessary) - if (!indexing_empty_texts) { - EBVector = new static_bitsequence_rrr02((uint *)empty_texts_aux,(ulong)npar,(uint)32); - free (empty_texts_aux); - empty_texts_aux = NULL; - } - - // OJO was leaked before, found by valgrind - free(tags_aux); - - tags_aux = NULL; - - finished = true; - print_stats(); - - return 1; // indicates success in the inicialization } -// NewOpenTag(tagname): indicates the event of finding a new opening tag in the document. -// Tag name is given. Returns a non-zero value upon success, and returns NULLT -// in case of failing when trying to insert the new tag. -int XMLTree::NewOpenTag(unsigned char *tagname) +// GetTagName(tagid): returns the tag name of a given tag identifier. +// Returns NULL in case that the tag identifier is not valid. +unsigned char *XMLTree::GetTagName(TagType tagid) { - int i; - - if (!initialized) { // data structure has not been initialized properly - fprintf(stderr, "Error: you cannot insert a new opening tag without first calling method OpenDocument first\n"); - return NULLT; - } - - // inserts a new opening parentheses in the bit sequence - if (sizeof(pb)*8*parArraySize == npar) { // no space left for the new parenthesis - par_aux = (pb *)urealloc(par_aux, sizeof(pb)*2*parArraySize); - parArraySize *= 2; - } - - setbit(par_aux,npar,OP); // marks a new opening parenthesis - - // transforms the tagname into a tag identifier. If the tag is new, we insert - // it in the table. - for (i=0; i") was called - if (i==0) - found_attributes=true; - - if (i==ntagnames) { // the tag is a new one, then we insert it - TagName = (unsigned char **)urealloc(TagName, sizeof(char *)*(ntagnames+1)); - - if (!TagName) { - fprintf(stderr, "Error: not enough memory\n"); - return NULLT; - } - - ntagnames++; - TagName[i] = (unsigned char *)umalloc(sizeof(unsigned char)*(strlen((const char *)tagname)+1)); - strcpy((char *)TagName[i], (const char *)tagname); - } - tags_aux = (TagType *) urealloc(tags_aux, sizeof(TagType)*(npar + 1)); - - tags_aux[npar] = i; // inserts the new tag id within the preorder sequence of tags - - npar++; - - return 1; + unsigned char *s; + if ( tagid < 0 || tagid >= TagName->size()) + return (unsigned char *) ""; + strcpy((char *)s, (*TagName)[tagid].c_str()); + return (s == NULL ? (unsigned char*) "" : s); } -// NewClosingTag(tagname): indicates the event of finding a new closing tag in the document. -// Tag name is given. Returns a non-zero value upon success, and returns NULLT -// in case of failing when trying to insert the new tag. -int XMLTree::NewClosingTag(unsigned char *tagname) +const unsigned char *XMLTree::GetTagNameByRef(TagType tagid) { - int i; - if (!initialized) { // data structure has not been initialized properly - fprintf(stderr, "Error: you cannot insert a new closing tag without first calling method OpenDocument first\n"); - return NULLT; - } - - // inserts a new closing parentheses in the bit sequence - if (sizeof(pb)*8*parArraySize == npar) { // no space left for the new parenthesis - par_aux = (pb *)urealloc(par_aux, sizeof(pb)*2*parArraySize); - parArraySize *= 2; - } - - setbit(par_aux,npar,CP); // marks a new closing parenthesis - - // transforms the tagname into a tag identifier. If the tag is new, we insert - // it in the table. - for (i=0; i= TagName->size()) + return (unsigned char *) ""; + + return (const unsigned char *) (*TagName)[tagid].c_str(); + } -// NewText(s): indicates the event of finding a new (non-empty) text s in the document. -// The new text is inserted within the text collection. Returns a non-zero value upon -// success, NULLT in case of error. -int XMLTree::NewText(unsigned char *s) - { - if (!initialized) { // data structure has not been initialized properly - fprintf(stderr, "Error: you cannot insert a new text without first calling method OpenDocument first\n"); - return NULLT; - } - if (disable_tc) { - XMLTree::NewEmptyText(); - return 1; +TagType XMLTree::RegisterTag(unsigned char *tagname) + { + TagType id = XMLTree::GetTagId(tagname); + if (id == NULLT) { + string s = (char *) tagname; + REGISTER_TAG(TagName,tIdMap,s); }; - - if (!indexing_empty_texts) { - empty_texts_aux = (unsigned int *)urealloc(empty_texts_aux, sizeof(pb)*(1+(npar-1)/(8*sizeof(pb)))); - bitset(empty_texts_aux, npar-1); // marks the non-empty text with a 1 in the bit vector - } - Text->InsertText(s); - string cpps = (char*) s; - CachedText.push_back(cpps); - - return 1; // success + return id; } -// NewEmptyText(): indicates the event of finding a new empty text in the document. -// In case of indexing empty and non-empty texts, we insert the empty texts into the -// text collection. In case of indexing only non-empty texts, it just indicates an -// empty text in the bit vector of empty texts. Returns a non-zero value upon -// success, NULLT in case of error. -int XMLTree::NewEmptyText() - { - unsigned char c = 0; - if (!initialized) { // data structure has not been initialized properly - fprintf(stderr, "Error: you cannot insert a new empty text without first calling method OpenDocument first\n"); - return NULLT; - } - if (!indexing_empty_texts) { - empty_texts_aux = (unsigned int *)urealloc(empty_texts_aux, sizeof(pb)*(1+(npar-1)/(8*sizeof(pb)))); - - bitclean(empty_texts_aux, npar-1); // marks the empty text with a 0 in the bit vector - } - else Text->InsertText(&c); // we insert the empty text just in case we index all the texts - - return 1; // success - } - - -// 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) - { - int i; - // this should be changed for more efficient processing - for (i=0; i= ntagnames) return NULL; // invalid tag identifier - s = (unsigned char *)umalloc((strlen((const char *)TagName[tagid])+1)*sizeof(unsigned char)); - strcpy((char *)s, (const char *)TagName[tagid]); - return s; - } - - -//KIM : OJO need the two following methods +treeNode XMLTree::Closing(treeNode x) { + return fast_find_close(Par,x); +} +bool XMLTree::IsOpen(treeNode x) { return fast_inspect(Par,x); } -const unsigned char *XMLTree::GetTagNameByRef(TagType tagid) - { - if(tagid==(uint)-1) return NULL; - if (tagid >= ntagnames) return NULL; // invalid tag identifier - return ((const unsigned char*) TagName[tagid]); - } +//WARNING this uses directly the underlying implementation for plain text -TagType XMLTree::RegisterTag(unsigned char *tagname) -{ - if (!finished) - return NULLT; +void XMLTree::Print(int fd,treeNode x, bool no_text){ - TagType id = XMLTree::GetTagId(tagname); - if (id == NULLT){ - id = ntagnames; - ntagnames = ntagnames + 1; - TagName = (unsigned char **) urealloc(TagName,ntagnames*(sizeof(unsigned char*))); - TagName[id] = (unsigned char *) umalloc(sizeof(unsigned char)*strlen( (const char*) tagname)+1); - strcpy((char*)TagName[id], (const char *)tagname); - }; - - return id; + int newfd = dup(fd); + stream = fdopen(newfd,"wa"); + + + FILE* fp = stream; + treeNode fin = fast_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 : TaggedDescendant(x,PCDATA_TAG_ID)); + treeNode first_att = NULLT;//TaggedDesc(x,ATTRIBUTE_DATA_TAG_ID); + + 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(MyText(first_idx)); + int read = 0; + + std::stack st; + while (n <= fin){ + if (fast_inspect(Par,n)){ + if (tag == PCDATA_TAG_ID ) { + // myfputs((const char*) (GetText(MyTextUnsafe(n))),fp); + if (no_text) + myfputs("<$/>",fp); + else{ + read = fprintf(fp,"%s",(const char*) current_text); + 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(tagstr); + 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 = fprintf(fp,"%s",(const char*) current_text); + current_text += (read + 1); + //myfputs((const char*) GetText(MyTextUnsafe(n)),fp); + myfputc('"',fp); + n+=3; + } + }; + if (no_text) + myfputs("",fp); + else myfputc('>',fp); + n++; + tag=Tag(n); + } + else { + myfputc('>',fp); + }; + } + else {// tag + myfputs("/>",fp); + n++; + tag=Tag(n); + }; + }; + } + else + do { + myfputs("', fp); + st.pop(); + n++; + }while (!fast_inspect(Par,n) && !st.empty()); + tag=Tag(n); + }; + myfputc('\n',fp); + mybufferflush(fp); + fflush(fp); + fclose(fp); }