X-Git-Url: http://git.nguyen.vg/gitweb/?a=blobdiff_plain;f=XMLTree.cpp;h=20e680165fd6e9e99d60f8aa36cee74336e08857;hb=d79d6498e2d585560d915592ef59f3ad6a57b3c7;hp=cdfe95296d6e4310ac04356d18e374af0688600d;hpb=39ee9d4c866fd5e4ba478ef65dc7e714e80c0b91;p=SXSI%2FXMLTree.git diff --git a/XMLTree.cpp b/XMLTree.cpp index cdfe952..20e6801 100644 --- a/XMLTree.cpp +++ b/XMLTree.cpp @@ -1,984 +1,627 @@ +#include "common.h" #include "XMLTree.h" -#include - -// 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, +#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). -// tag position -> tree node -inline treeNode tagpos2node(int t) { - return (treeNode)t; -} -// tree node -> tag position -inline int node2tagpos(treeNode x) { - return (int)x; +static int bits8 (int t ) { + int r = bits(t); + if (r <= 8) + return 8; + else if (r <= 16) + return 16; + else + return r; } -//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 treeNode fast_sibling(bp* Par,treeNode x,TagType tag){ - return; -} + if (tag == PCDATA_TAG_ID){ + x = x+2; + return bp_inspect(Par,x)==OP ? x : NULLT; + } else return bp_next_sibling(Par,x); -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; } -// 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; -} -inline void * ucalloc(size_t nmemb, size_t size){ +inline uint get_field_no_power(uint *A, uint len, uint index) { - 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; + 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; -} - -// Save: saves XML tree data structure to file. -void XMLTree::Save(unsigned char *filename) - { +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); + }; - FILE *fp; - char filenameaux[1024]; - int i; - - 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); - } - - // 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); - - // stores the tags - Tags->save(fp); +} - // stores the texts - if (!disable_tc) - Text->Save(fp); - if (!disable_tc){ - 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+strlen(CachedText.at(i).c_str())),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( pb * const par, uint npar, vector * const TN, TagIdMap * const tim, + uint *empty_texts_bmp, TagType *tags, + TextCollectionBuilder * const TCB, bool dis_tc, + TextCollectionBuilder::index_type_t _index_type ) { + buffer = 0; + print_stack = 0; + // creates the data structure for the tree topology + STARTTIMER(); + Par = bp_construct(npar, (pb*) par, OPT_DEGREE|0); + STOPTIMER(Building); + PRINTTIME("Building parenthesis struct", Building); + STARTTIMER(); - 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(); - XML_Tree->Par = (bp *)umalloc(sizeof(bp)); + // creates structure for tags - loadTree(XML_Tree->Par, fp); + TagName = (vector*)TN; + tIdMap = (TagIdMap *) tim; - s_tree += sizeof(bp); + uint max_tag = TN->size() - 1; - // stores the table with tag names - ufread(&XML_Tree->ntagnames, sizeof(int), 1, fp); - - s_tree += sizeof(int); + 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); - XML_Tree->TagName = (unsigned char **)umalloc(XML_Tree->ntagnames*sizeof(unsigned char *)); - - s_tags += sizeof(unsigned char*)*XML_Tree->ntagnames; + //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; - for (i=0; intagnames;i++) { - - // OJO Kim is it needed ? - int k = feof(fp); + STOPTIMER(Building); + PRINTTIME("Building Tag Structure", Building); - - // 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); - if (r==NULL) - throw "Cannot read tag list"; + EBVector = new static_bitsequence_rrr02(empty_texts_bmp,npar,32); + free(empty_texts_bmp); + empty_texts_bmp = NULL; - // 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); - - s_tree+=sizeof(bool)*4; - - if (!(XML_Tree->indexing_empty_texts)) XML_Tree->EBVector = static_bitsequence_rrr02::load(fp); - - s_tree+= XML_Tree->EBVector->size(); - - // loads the tags - XML_Tree->Tags = static_sequence::load(fp); - s_tree+= XML_Tree->Tags->size(); - - s_text = ftell(fp); - - // 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); - }; + disable_tc = dis_tc; + text_index_type = _index_type; + if (!disable_tc) { + assert(TCB != 0); + STARTTIMER(); + Text = TCB->InitTextCollection(); + delete TCB; + STOPTIMER(Building); + PRINTTIME("Building TextCollection", Building); + } else { + Text = NULL; } - else - XML_Tree->Text = NULL; - - s_text = ftell(fp) - s_text; - - - - fclose(fp); - - std::cerr << "Tree part is " << s_tree/1024 << " Kbytes,\n" - << "with node->tagid part " << XML_Tree->Tags->size()/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"; - return XML_Tree; + 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 - - for (i=0; i~static_bitsequence_rrr02(); - delete EBVector; - EBVector = NULL; - } + bp_delete(Par); + Par = NULL; + + delete tIdMap; + tIdMap = NULL; + + delete TagName; + TagName = NULL; - //Tags->~static_sequence_wvtree(); delete Tags; Tags = NULL; - //Text->~TextCollection(); delete Text; Text = NULL; - initialized = false; - finished = false; + delete EBVector; + EBVector = NULL; + } -// root(): returns the tree root. -treeNode XMLTree::Root() + +void XMLTree::print_stats() { - if (!finished) { - fprintf(stderr, "Root() : Error: data structure has not been constructed properly\n"); - exit(1); - } - return root_node(Par); + 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; } -// SubtreeSize(x): the number of nodes (and attributes) in the subtree of node x. -int XMLTree::SubtreeSize(treeNode x) +// Save: saves XML tree data structure to file. +void XMLTree::Save(int fd, char * name) { - if (!finished) { - fprintf(stderr, "Error: data structure has not been constructed properly\n"); - exit(1); + FILE *fp; + int i; + off_t pos = lseek(fd, 0, SEEK_CUR); + int fd2 = dup(fd); + fp = fdopen(fd2, "w"); + fseek(fp, pos, SEEK_SET); + // first stores the tree topology + saveTree(Par, fp); + + // stores the table with tag names + 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); + + // flags + ufwrite(&disable_tc, sizeof(bool),1,fp); + + //text positions + EBVector->save(fp); + std::cerr << "TC Index position: " << ftell(fp) << std::endl; + // stores the texts + if (!disable_tc) { + std::cerr << "Writing " << sizeof(TextCollectionBuilder::index_type_t) << " bytes\n" << std::endl; + 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()); + + } - return subtree_size(Par, x); + fflush(fp); + fclose(fp); } -// SubtreeTags(x,tag): the number of occurrences of tag within the subtree of node x. -int XMLTree::SubtreeTags(treeNode x, TagType tag) +// 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, char * name) { - if (!finished) { - fprintf(stderr, "Error: data structure has not been constructed properly\n"); - exit(1); + + FILE *fp; + char buffer[1024]; + XMLTree *XML_Tree; + int i; + + buffer[1023] = '\0'; + + fp = fdopen(fd, "r"); + + XML_Tree = new XMLTree(); + STARTTIMER(); + // Load the tree structure + XML_Tree->Par = loadTree(fp); + STOPTIMER(Loading); + PRINTTIME("Loading parenthesis struct", Loading); + STARTTIMER(); + + 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->tIdMap->insert(std::make_pair(s,i)); + + }; + STOPTIMER(Loading); + PRINTTIME("Loading tag names struct", Loading); + STARTTIMER(); + + // 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 + + 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); + + STOPTIMER(Loading); + PRINTTIME("Loading text bitvector struct", Loading); + STARTTIMER(); + std::cerr << "TC Load Index position: " << ftell(fp) << std::endl; + // 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(); } - if (x == Root()) - x = first_child(Par,x); - + else { + XML_Tree->EBVector = NULL; + XML_Tree->Text = NULL; + XML_Tree->disable_tc = true; + }; - int s = x + 2*subtree_size(Par, x) - 1; - - return Tags->rank(tag, s) - Tags->rank(tag, node2tagpos(x)-1); + + return XML_Tree; + } + + + + +int XMLTree::SubtreeElements(treeNode x) + { + + int size = bp_subtree_size(Par, x); + if (x == Root()){ + 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 = 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)); + }; + 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) { - return isleaf(Par, x); - } + NULLT_IF(x==NULLT); + 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) { - if (!finished) { - fprintf(stderr, "Error: data structure has not been constructed properly\n"); - exit(1); - } - - return 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) +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; - return depth(Par, x) == (depth(Par, y) + 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) { - if (!finished) { - fprintf(stderr, "Error: data structure has not been constructed properly\n"); - exit(1); - } - - 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) { - if (!finished) { - fprintf(stderr, "Error: data structure has not been constructed properly\n"); - exit(1); - } - - 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) { - if (!finished) { - fprintf(stderr, "Error: data structure has not been constructed properly\n"); - exit(1); - } - - 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) { - if (!finished) { - fprintf(stderr, "Error: data structure has not been constructed properly\n"); - exit(1); - } - - 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) - { - 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) +int XMLTree::Postorder(treeNode x) { - if (!finished) { - fprintf(stderr, "Error: data structure has not been constructed properly\n"); - exit(1); - } - - return Tags->access(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) - { - if (!finished) { - fprintf(stderr, "Error: data structure has not been constructed properly\n"); - exit(1); - } - - range 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 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*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; + } + 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); - } // 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 (!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); - } - - return first_child(Par, x); - } - -// 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()) - return NULLT; - - return next_sibling(Par, 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); - } + if (i <= OPTD) return bp_naive_child(Par, x, i); + else return bp_child(Par, x, i); +} -// TaggedChild(x,i,tag): returns the i-th 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) - { - 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 (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 - } +treeNode XMLTree::SelectChild(treeNode x, TagIdSet *tags) +{ -// 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); - } + NULLT_IF(x==NULLT || bp_isleaf(Par,x)); + int i; + 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; +} - 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; - } -// 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 tag) - { - if (!finished) { - fprintf(stderr, "Error: data structure has not been constructed properly\n"); - exit(1); - } +treeNode XMLTree::SelectFollowingSibling(treeNode x, TagIdSet *tags) +{ - int r, s; - treeNode y; - if (x==NULLT) - 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 - return (y<=x ? NULLT : y); + NULLT_IF(x==NULLT); + int i; + TagType t; + 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; } // 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) { - if (!finished) { - fprintf(stderr, "Error: data structure has not been constructed properly\n"); - exit(1); - } - 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 (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 } + // 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); - } - - int r, s; - if (x ==NULLT || x == Root()|| (next_sibling(Par,x) == -1 )) - return NULLT; + NULLT_IF (x ==NULLT || x == Root()); + return tagpos2node(Tags->select_next(tag, bp_find_close(Par, x))); - r = (int) Tags->rank(tag, node2tagpos(next_sibling(Par, x))-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); } -// 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) +/* 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) { - 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 - } - } + NULLT_IF(x==NULLT || x==Root()); -// 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); - } + treeNode close = bp_find_close(Par,x); + treeNode ns = close+1; + if ( (bp_inspect(Par,ns) == OP) && (tags->find(Tag(ns)) != tags->end())) + return ns; - 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 - } - } + int i; + treeNode min = NULLT; + treeNode aux; -// 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 - } - } - -// 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) - { - if (!finished) { - fprintf(stderr, "Error: data structure has not been constructed properly\n"); - exit(1); - } + TagIdSet::const_iterator tagit; + for (tagit = tags->begin(); tagit != tags->end(); ++tagit) { - 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); - } - } + aux = tagpos2node(Tags->select_next(*tagit, close)); + if (aux == NULLT) continue; + if ((min == NULLT) || (aux < min)) min = aux; + }; -// 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; - - } + // 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 < bp_find_close(Par, ancestor)) return min; + else 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 = 2; - 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(2*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], "<$>"); - - - 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 } - -// 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() +// 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 (!initialized) { // data structure has not been initialized properly - fprintf(stderr, "Error: data structure has not been initialized properly (by calling method OpenDocument)\n"); + if (x == NULLT || x == Root()) 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 - 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); - - // 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 - int ntagsize = found_attributes ? 2*ntagnames-1 : 2*ntagnames - 2; - - Tags = new static_sequence_gmr((uint *) tags_aux, (uint) npar-1,ntagsize, bmb, ssb); - - delete bmb; - delete pmb; - delete ssb; - // makes the text collection static - if (!disable_tc) - Text->MakeStatic(); - - // 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; + treeNode s = bp_parent(Par, x), r = Root(); + while (s != r) { + if (Tag(s) == tag) return s; + s = bp_parent(Par, s); } - - // OJO was leaked before, found by valgrind - free(tags_aux); - - tags_aux = NULL; - - finished = true; - - return 1; // indicates success in the inicialization + return NULLT; } -// 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) - { - 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; - - } +// 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) +{ + TagType tag = Tag(x); + // seems faster than testing EBVector->access(x); + if (tag == PCDATA_TAG_ID || tag == ATTRIBUTE_DATA_TAG_ID) + return (DocID) (EBVector->rank1(x)-1); + else + return (DocID) NULLT; -// 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) +} +// 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) { - int i; + NULLT_IF(d == NULLT); + int s = EBVector->select1(d+1); + return bp_rank_open(Par, s) + d + 1; // +1 because root has preorder 1 - 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 opening parenthesis - - // transforms the tagname into a tag identifier. If the tag is new, we insert - // it in the table. - for (i=0; iInsertText(s); - string cpps = (char*) s; - CachedText.push_back(cpps); - - return 1; // success + NULLT_IF(x == NULLT); + if (x == Root()) return 1; // root node has preorder 1 + return bp_rank_open(Par, x) + EBVector->rank1(x-1); } -// 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() +// ParentNode(d): returns the parent node of document identifier d. +treeNode XMLTree::ParentNode(DocID d) { - 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 + 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) { - int i; - // this should be changed for more efficient processing - for (i=0; ifind(s); + return (TagType) ((it != tIdMap->end()) ? it->second : -1); + } @@ -987,37 +630,147 @@ TagType XMLTree::GetTagId(unsigned char *tagname) unsigned char *XMLTree::GetTagName(TagType tagid) { unsigned char *s; + if ( tagid < 0 || tagid >= TagName->size()) + return (unsigned char *) ""; + strcpy((char *)s, (*TagName)[tagid].c_str()); - if (tagid >= 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; + return (s == NULL ? (unsigned char*) "" : s); } -//KIM : OJO need the two following methods - const unsigned char *XMLTree::GetTagNameByRef(TagType tagid) { - if (tagid >= ntagnames) return NULL; // invalid tag identifier - return ((const unsigned char*) TagName[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) -{ - if (!finished) - return NULLT; - - 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); + { + TagType id = XMLTree::GetTagId(tagname); + if (id == NULLT) { + string s = (char *) tagname; + REGISTER_TAG(TagName,tIdMap,s); + }; + + return id; + } + + +treeNode XMLTree::Closing(treeNode x) { + return bp_find_close(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){ + + if (buffer == 0) { + buffer = new string(BUFFER_ALLOC, 0); + buffer->clear(); + print_stack = new std::vector(); + print_stack->reserve(256); }; - return id; + treeNode fin = bp_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 (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); + + } 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 do { + _dputs("back()), fd); + _dputc('>', fd); + print_stack->pop_back(); + n++; + } while (!(bp_inspect(Par,n) || print_stack->empty())); + tag = Tag(n); + }; + _dputc('\n', fd); + //_flush(fd); }