X-Git-Url: http://git.nguyen.vg/gitweb/?a=blobdiff_plain;f=XMLTree.cpp;h=61f6a4d30b0223a246f2656838f40cc1240c7546;hb=fdf29cca5a2df608373ffbeb3a4155876a55df2c;hp=bd728af5d665e695733364fc0783436b4f072ea2;hpb=5db16dd3e0bf609bc0fa84ee7d067f6bbc58013e;p=SXSI%2FXMLTree.git diff --git a/XMLTree.cpp b/XMLTree.cpp index bd728af..61f6a4d 100644 --- a/XMLTree.cpp +++ b/XMLTree.cpp @@ -1,5 +1,7 @@ -#include "XMLTree.h" + +#include "basics.h" #include +#include "XMLTree.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,317 +10,261 @@ // 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; -} +inline treeNode tagpos2node(int t) + { + return (treeNode) t; + } // tree node -> tag position -inline int node2tagpos(treeNode x) { - return (int)x; +inline int node2tagpos(treeNode x) +{ + return (int)x; } +// returns NULLT if the test is true +#define NULLT_IF(x) do { if (x) return NULLT; } while (0) -//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"; +XMLTree::XMLTree( pb * const par, uint npar, vector * const TN, TagIdMap * const tim, uint *empty_texts_bmp, TagType *tags, + TextCollection * const TC, vector * const CT, bool dis_tc) - return; -} + { + // creates the data structure for the tree topology + Par = (bp *)umalloc(sizeof(bp)); + bp_construct(Par, npar, (pb*) par, OPT_DEGREE|0); + + // creates structure for tags -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; -} + 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; -// 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){ + 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[i]); - void * dest = realloc(ptr,size); - //don't fail if we requested size 0 - if (dest == NULL && size > 0 ) - throw std::bad_alloc(); - return dest; + delete bmb; + free(tags); + tags = NULL; + + Text = (TextCollection*) TC; -} + CachedText = (vector*) CT; + EBVector = new static_bitsequence_rrr02(empty_texts_bmp,npar,32); + free(empty_texts_bmp); + empty_texts_bmp = NULL; -inline void * ucalloc(size_t nmemb, size_t size){ + + disable_tc = dis_tc; + } - 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; -} +// ~XMLTree: frees memory of XML tree. +XMLTree::~XMLTree() + { + int i; -inline void * umalloc(size_t size){ - void * dest = malloc(size); - if (dest == NULL && size > 0) - throw std::bad_alloc(); - return dest; -} + destroyTree(Par); + free(Par); // frees the memory of struct Par + + delete tIdMap; + tIdMap = NULL; + + delete TagName; + TagName = NULL; + + delete Tags; + Tags = NULL; -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; -} + delete Text; + Text = NULL; -// Save: saves XML tree data structure to file. -void XMLTree::Save(unsigned char *filename) + delete EBVector; + EBVector = NULL; + + + } + + +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; - - 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); - } - + + 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(); + int st = CachedText->size(); + ufwrite(&st, sizeof(int),1,fp); - for (int i = 0; i< CachedText.size(); i++){ - st = CachedText.at(i).size(); + 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); + + ufwrite(CachedText->at(i).c_str(),sizeof(char),1+CachedText->at(i).size(),fp); + }; + + Text->Save(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) { - 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); - } + + + + fp = fdopen(fd, "r"); XML_Tree = new XMLTree(); + // Load the tree structure XML_Tree->Par = (bp *)umalloc(sizeof(bp)); loadTree(XML_Tree->Par, fp); - 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)); + + }; - // 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); + 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; - 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); + XML_Tree->EBVector = static_bitsequence_rrr02::load(fp); + + // Not used + int sample_rate_text = 64; // loads the texts if (!XML_Tree->disable_tc){ - XML_Tree->Text = TextCollection::Load(fp,sample_rate_text); + XML_Tree->CachedText = new vector; int sst; int st; ufread(&sst, sizeof(int),1,fp); + for (int i=0;iCachedText.push_back(cppstr); + XML_Tree->CachedText->push_back(cppstr); free(str); - }; + }; + XML_Tree->Text = TextCollection::Load(fp,sample_rate_text); } - else { - XML_Tree->Text = NULL; - } - s_text = ftell(fp) - s_text; - + else XML_Tree->Text = NULL; - - - 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 TextBuilder; - TextBuilder = NULL; - delete Text; - Text = NULL; - - initialized = false; - finished = false; - } - // root(): returns the tree root. -treeNode XMLTree::Root() +inline treeNode XMLTree::Root() { - if (!finished) { - fprintf(stderr, "Root() : Error: data structure has not been constructed properly\n"); - exit(1); - } - return root_node(Par); + return 0; //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); @@ -338,59 +284,39 @@ bool XMLTree::IsLeaf(treeNode 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); } // 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; return depth(Par, x) == (depth(Par, y) + 1); } -bool XMLTree::IsFirstChild(treeNode x){ - return ((x != NULLT)&&(x==Root() || prev_sibling(Par,x) == NULLT)); -} + +// 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); } @@ -398,11 +324,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); } @@ -410,68 +331,44 @@ 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 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 (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; + + 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 { // 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; - } + 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 @@ -481,263 +378,153 @@ treeNode XMLTree::Parent(treeNode 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 first_child(Par, x); + } + +treeNode XMLTree::FirstElement(treeNode x) + { + NULLT_IF(x==NULLT); + treeNode fc = first_child(Par, x); + //<$> is 2 + return ((fc == NULLT || Tag(fc) != PCDATA_TAG_ID) ? fc : next_sibling(Par,fc)); - return first_child(Par, x); } -treeNode XMLTree::LastChild(treeNode x) +treeNode XMLTree::NextElement(treeNode x) { - if (x == Root() || isleaf(Par,x) || x == NULLT) - return x; - else - return find_open(Par,find_close(Par,parent(Par,x))-1); + NULLT_IF(x==NULLT); + treeNode ns = next_sibling(Par, x); + return ((ns == NULLT || Tag(ns) != PCDATA_TAG_ID) ? ns : next_sibling(Par,ns)); } +// LastChild(x): returns the last child of node x. +treeNode XMLTree::LastChild(treeNode x) + { + NULLT_IF(x==NULLT || x == Root() || isleaf(Par,x)); + return find_open(Par, 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() ); + 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); + NULLT_IF(x==NULLT || x == Root()); + 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 || isleaf(Par,x)); -// 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; - - int s = (int) Tags->select_next(tag,node2tagpos(x)); - /*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 child; + child = first_child(Par, x); // starts at first child of node x + if (get_field(tags_fix,tags_blen,node2tagpos(child)) == tag) + return child; + else + return TaggedFollSibling(child,tag); } -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::TaggedFollSibling(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 = next_sibling(Par, x); + while (sibling != NULLT) { + if (get_field(tags_fix,tags_blen,node2tagpos(sibling)) == tag) // current sibling is labeled with tag of interest + return sibling; + sibling = next_sibling(Par, sibling); // 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, std::unordered_set *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 || isleaf(Par,x)); + int i; + treeNode child = first_child(Par, x); + TagType t = get_field(tags_fix, tags_blen, node2tagpos(child)); + std::unordered_set::const_iterator tagit = tags->find(t); + if (tagit != tags->end()) return child; + return SelectFollSibling(child,tags); } -treeNode 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::SelectFollSibling(treeNode x, std::unordered_set *tags) { - treeNode res,y,lim; - //int r,s; - lim = find_close(Par,root); - res=NULLT; - for (unsigned int i = 0; i < ftlen; i ++ ) - { - - int s = (int) Tags->select_next(folltags[i],node2tagpos(x)); - /*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 = next_sibling(Par, x); + std::unordered_set::const_iterator tagit; + while (sibling != NULLT) { + t = get_field(tags_fix, tags_blen, node2tagpos(sibling)); + tagit = tags->find(t); + if (tagit != tags->end()) return sibling; + sibling = next_sibling(Par, sibling); + } + 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) +// 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) { - treeNode y,old_y,lim,res; - TagType tag; - if (x == NULLT || x == Root()) - return NULLT; + NULLT_IF(x==NULLT || 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 (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::SelectDesc(treeNode x, std::unordered_set *tags) + { + NULLT_IF (x ==NULLT || isleaf(Par,x)); + int i; + treeNode min = NULLT; + treeNode fc = first_child(Par,x); + treeNode aux; + std::unordered_set::const_iterator tagit; + for (tagit = tags->begin(); tagit != tags->end(); tagit++) { + aux = TaggedDesc(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); - } - + { int r, s; treeNode node_s, root; r = (int)Tags->rank(tag, node2tagpos(x)-1); @@ -759,71 +546,68 @@ treeNode XMLTree::TaggedPrec(treeNode x, TagType tag) // the subtree of x. Returns NULLT if there is none. treeNode XMLTree::TaggedFoll(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,find_close(Par, x))); - //int r, s; - if (x ==NULLT || x == Root()) - return NULLT; - - int s = (int) Tags->select_next(tag,find_close(Par,x)); - /*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. +// TaggedFollBelow(x,tag,root): returns the first node tagged tag with larger preorder than x +// and not in the subtree of x. Returns NULLT if there is none. treeNode XMLTree::TaggedFollBelow(treeNode x, TagType tag, treeNode root) - { - - if (x == NULLT || x == Root()) return NULLT; - treeNode s = (treeNode) Tags->select_next(tag,find_close(Par,x)); - /*int r = (int) Tags->rank(tag, find_close(Par, x)); - int s = (int) Tags->select(tag, r+1); */ - if (root == Root()) - return s; - - if (s == NULLT || s >= find_close(Par,root)) return NULLT; - return s; - } +{ + NULLT_IF (x == NULLT || x == Root()); + + treeNode s = tagpos2node(Tags->select_next(tag, find_close(Par, x))); + + if (root == Root()) return s; + NULLT_IF (s == NULLT || s >= find_close(Par, root)); + + return s; +} -// 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) +/* Here we inline TaggedFoll to find the min globally, and only at the end + we check if the min is below the context node */ +treeNode XMLTree::SelectFollBelow(treeNode x, std::unordered_set *tags, treeNode root) { - 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 = next_sibling(Par, x); + treeNode aux; + std::unordered_set::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, find_close(Par, x))); + + // 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. - int s = (int) Tags->select_next(tag,node2tagpos(ns)-1); - /*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); + if (root == Root()) return min; + // else check whether if is in below the ctx node + + NULLT_IF (min == NULLT || min >= find_close(Par, root)); + + 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; @@ -836,84 +620,29 @@ treeNode XMLTree::TaggedAncestor(treeNode x, TagType tag) } -// 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); - } +{ + TagType tag = Tag(x); + // seems faster than testing EBVector->access(x); - 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 - } - } + if (tag == PCDATA_TAG_ID || tag == ATTRIBUTE_DATA_TAG_ID) + return (DocID) (EBVector->rank1(x)-1); //-1 because document ids start from 0 + else + return (DocID) NULLT; + +} // 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 - } + 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 @@ -921,361 +650,26 @@ 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); - } + 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)); - - if (disable_tc) - TextBuilder = 0; - else - TextBuilder = new TextCollectionBuilder((unsigned)sample_rate_text); - Text = 0; - - 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() - { - 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) - { - assert(Text == 0); - assert(TextBuilder != 0); - Text = TextBuilder->InitTextCollection(); - delete TextBuilder; - TextBuilder = 0; - } - - // 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) - { - 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; - - } - - -// 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) - { - 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; iInsertText(s); - string cpps = (char*) s; - CachedText.push_back(cpps); - - return 1; // success - } - -// 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 TextBuilder->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); + } @@ -1284,38 +678,37 @@ TagType XMLTree::GetTagId(unsigned char *tagname) unsigned char *XMLTree::GetTagName(TagType tagid) { unsigned char *s; - if(tagid==(uint)-1) return NULL; - 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; + if ( tagid < 0 || tagid >= TagName->size()) + return (unsigned char *) ""; + strcpy((char *)s, TagName->at(tagid).c_str()); + + return (s == NULL ? (unsigned char*) "" : s); } -//KIM : OJO need the two following methods - 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]); + + unsigned char *s; + if ( tagid < 0 || tagid >= TagName->size()) + return (unsigned char *) ""; + + return (const unsigned char *) TagName->at(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); - }; - - return id; -} + { + TagType id = XMLTree::GetTagId(tagname); + if (id == NULLT) { + string s = (char *) tagname; + REGISTER_TAG(TagName,tIdMap,s); + + }; + + return id; + } + +