From a0808cd570d8645798ae80287d2b4845ceea36a2 Mon Sep 17 00:00:00 2001 From: kim Date: Thu, 29 Jan 2009 08:12:33 +0000 Subject: [PATCH] Some more debugging and comments. git-svn-id: svn+ssh://idea.nguyen.vg/svn/sxsi/trunk/XMLTree@91 3cdefd35-fc62-479d-8e8d-bae585ffb9ca --- XMLTree.cpp | 205 +++++++++++++++++++++++++--------------------------- XMLTree.h | 32 ++++++++ 2 files changed, 130 insertions(+), 107 deletions(-) diff --git a/XMLTree.cpp b/XMLTree.cpp index a696d7f..b93e75a 100644 --- a/XMLTree.cpp +++ b/XMLTree.cpp @@ -1,7 +1,7 @@ #include "XMLTree.h" #include - // functions to convert tag positions to the corresponding tree node and viceversa. +// 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 @@ -17,7 +17,8 @@ inline int node2tagpos(treeNode x) { return (int)x; } -// to prevent suprious "unused result" warnings + +//KIM OJO to prevent suprious "unused result" warnings inline void ufread(void *ptr, size_t size, size_t nmemb, FILE *stream){ size_t res; @@ -27,6 +28,7 @@ inline void ufread(void *ptr, size_t size, size_t nmemb, FILE *stream){ return; } + inline void ufwrite(const void *ptr, size_t size, size_t nmemb, FILE *stream){ size_t res; res = fwrite(ptr,size,nmemb,stream); @@ -35,6 +37,36 @@ inline void ufwrite(const void *ptr, size_t size, size_t nmemb, FILE *stream){ 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){ + + 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 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) { @@ -85,52 +117,53 @@ XMLTree *XMLTree::Load(unsigned char *filename, int sample_rate_text) { FILE *fp; - char filenameaux[1024]; + char buffer[1024]; XMLTree *XML_Tree; int i; // first load the tree topology - sprintf(filenameaux, "%s.srx", filename); - fp = fopen(filenameaux, "r"); + 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", filenameaux); + 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 *)malloc(sizeof(bp)); + XML_Tree->Par = (bp *)umalloc(sizeof(bp)); loadTree(XML_Tree->Par, fp); // stores the table with tag names ufread(&XML_Tree->ntagnames, sizeof(int), 1, fp); - XML_Tree->TagName = (unsigned char **)malloc(XML_Tree->ntagnames*sizeof(unsigned char *)); + XML_Tree->TagName = (unsigned char **)umalloc(XML_Tree->ntagnames*sizeof(unsigned char *)); for (i=0; intagnames;i++) { - // Kim is it needed ? + // OJO Kim is it needed ? int k = feof(fp); - // fscanf chokes ont "\n" which is the case for the root element - char * r = fgets(filenameaux,1023,fp); - // int r = fscanf(fp, "<%s>\n",filenameaux); + + + // 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"; - - int len = strlen((const char*)filenameaux); - XML_Tree->TagName[i] = (unsigned char *)calloc(len,sizeof(char)); - - //XML_Tree->TagName[i] = (unsigned char *)malloc(sizeof(unsigned char)*(strlen((const char *)filenameaux)+1)); - //the - 1 removes the trailing \n - strncpy((char *)XML_Tree->TagName[i], (const char *)filenameaux,len - 1); + // 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); } // 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); + if (!(XML_Tree->indexing_empty_texts)) XML_Tree->EBVector = static_bitsequence_rrr02::load(fp); // loads the tags @@ -297,7 +330,6 @@ int XMLTree::Postorder(treeNode x) fprintf(stderr, "Error: data structure has not been constructed properly\n"); exit(1); } - return postorder_rank(Par, x); } @@ -591,10 +623,15 @@ treeNode XMLTree::ParentNode(DocID d) fprintf(stderr, "Error: data structure has not been constructed properly\n"); exit(1); } - - int s; + + if (d == NULLT) + return NULLT; + + int s = d; + // Kim : I added the d+1. before that, else was select1(d) + // and gave wrong results but I'm really poking a dead bear with a stick here. if (indexing_empty_texts) s = d; - else s = EBVector->select1(d); + else s = EBVector->select1(d+1); if (inspect(Par,s) == CP) // is a closing parenthesis return parent(Par, find_open(Par, s)); @@ -619,48 +656,25 @@ int XMLTree::OpenDocument(bool empty_texts, int sample_rate_text,bool dtc) indexing_empty_texts = empty_texts; - par_aux = (pb *)malloc(sizeof(pb)*parArraySize); - if (!par_aux) { - fprintf(stderr, "Error: not enough memory\n"); - return NULLT; - } + par_aux = (pb *)umalloc(sizeof(pb)*parArraySize); - tags_aux = (TagType *) malloc(sizeof(TagType)); - if (!tags_aux) { - fprintf(stderr, "Error: not enough memory\n"); - return NULLT; - } + tags_aux = (TagType *) umalloc(sizeof(TagType)); - TagName = (unsigned char **) malloc(2*sizeof(unsigned char*)); - if (!TagName){ - fprintf(stderr, "Error: not enough memory\n"); - return NULLT; - } + TagName = (unsigned char **) umalloc(2*sizeof(unsigned char*)); - TagName[0] = (unsigned char *) malloc(4*sizeof(unsigned char)); - strcpy((char *) TagName[0], "<@>"); + TagName[0] = (unsigned char *) umalloc(4*sizeof(unsigned char)); - if (!TagName[0]){ - fprintf(stderr, "Error: not enough memory\n"); - return NULLT; - } + strcpy((char *) TagName[0], "<@>"); - TagName[1] = (unsigned char *) malloc(4*sizeof(unsigned char)); - if (!TagName[1]){ - fprintf(stderr, "Error: not enough memory\n"); - return NULLT; - } + TagName[1] = (unsigned char *) umalloc(4*sizeof(unsigned char)); strcpy((char *) TagName[1], "<$>"); - if (!indexing_empty_texts) { - empty_texts_aux = (unsigned int *)malloc(sizeof(unsigned int)); - if (!empty_texts_aux) { - fprintf(stderr, "Error: not enough memory\n"); - return NULLT; - } - } + if (!indexing_empty_texts) + empty_texts_aux = (unsigned int *)umalloc(sizeof(unsigned int)); + + Text = TextCollection::InitTextCollection((unsigned)sample_rate_text); @@ -679,14 +693,10 @@ int XMLTree::CloseDocument() } // closing parenthesis for the tree root - par_aux = (pb *)realloc(par_aux, sizeof(pb)*(1+npar/(8*sizeof(pb)))); - if (!par_aux) { - fprintf(stderr, "Error: not enough memory\n"); - return NULLT; - } + par_aux = (pb *)urealloc(par_aux, sizeof(pb)*(1+npar/(8*sizeof(pb)))); // creates the data structure for the tree topology - Par = (bp *)malloc(sizeof(bp)); + 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); @@ -714,7 +724,9 @@ int XMLTree::CloseDocument() empty_texts_aux = NULL; } + // OJO was leaked before, found by valgrind free(tags_aux); + tags_aux = NULL; finished = true; @@ -737,15 +749,10 @@ int XMLTree::NewOpenTag(unsigned char *tagname) // 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 *)realloc(par_aux, sizeof(pb)*2*parArraySize); + par_aux = (pb *)urealloc(par_aux, sizeof(pb)*2*parArraySize); parArraySize *= 2; } - if (!par_aux) { - fprintf(stderr, "Error: not enough memory\n"); - return NULLT; - } - setbit(par_aux,npar,OP); // marks a new opening parenthesis // transforms the tagname into a tag identifier. If the tag is new, we insert @@ -759,7 +766,7 @@ int XMLTree::NewOpenTag(unsigned char *tagname) found_attributes=true; if (i==ntagnames) { // the tag is a new one, then we insert it - TagName = (unsigned char **)realloc(TagName, sizeof(char *)*(ntagnames+1)); + TagName = (unsigned char **)urealloc(TagName, sizeof(char *)*(ntagnames+1)); if (!TagName) { fprintf(stderr, "Error: not enough memory\n"); @@ -767,14 +774,10 @@ int XMLTree::NewOpenTag(unsigned char *tagname) } ntagnames++; - TagName[i] = (unsigned char *)malloc(sizeof(unsigned char)*(strlen((const char *)tagname)+1)); + TagName[i] = (unsigned char *)umalloc(sizeof(unsigned char)*(strlen((const char *)tagname)+1)); strcpy((char *)TagName[i], (const char *)tagname); } - tags_aux = (TagType *) realloc(tags_aux, sizeof(TagType)*(npar + 1)); - if (!tags_aux) { - fprintf(stderr, "Error: not enough memory\n"); - return NULLT; - } + 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 @@ -799,14 +802,10 @@ int XMLTree::NewClosingTag(unsigned char *tagname) // 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 *)realloc(par_aux, sizeof(pb)*2*parArraySize); + par_aux = (pb *)urealloc(par_aux, sizeof(pb)*2*parArraySize); parArraySize *= 2; } - if (!par_aux) { - fprintf(stderr, "Error: not enough memory\n"); - return NULLT; - } 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 @@ -815,25 +814,16 @@ int XMLTree::NewClosingTag(unsigned char *tagname) if (strcmp((const char *)tagname,(const char *)TagName[i])==0) break; if (i==ntagnames) { // the tag is a new one, then we insert it - TagName = (unsigned char **)realloc(TagName, sizeof(char *)*(ntagnames+1)); + 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 *)malloc(sizeof(char)*(strlen((const char *)tagname)+2)); + TagName[i] = (unsigned char *)umalloc(sizeof(char)*(strlen((const char *)tagname)+2)); TagName[i][0] = '/'; strcpy((char *)&(TagName[i][1]), (const char *)tagname); } - tags_aux = (TagType *)realloc(tags_aux, sizeof(TagType)*(npar + 1)); - - if (!tags_aux) { - fprintf(stderr, "Error: not enough memory\n"); - return NULLT; - } + 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 @@ -860,13 +850,8 @@ int XMLTree::NewText(unsigned char *s) }; if (!indexing_empty_texts) { - empty_texts_aux = (unsigned int *)realloc(empty_texts_aux, sizeof(pb)*(1+(npar-1)/(8*sizeof(pb)))); - if (!empty_texts_aux) { - fprintf(stderr, "Error: not enough memory\n"); - return NULLT; - } - - bitset(empty_texts_aux, npar-1); // marks the non-empty text with a 1 in the bit vector + 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); @@ -888,11 +873,7 @@ int XMLTree::NewEmptyText() } if (!indexing_empty_texts) { - empty_texts_aux = (unsigned int *)realloc(empty_texts_aux, sizeof(pb)*(1+(npar-1)/(8*sizeof(pb)))); - if (!empty_texts_aux) { - fprintf(stderr, "Error: not enough memory\n"); - return NULLT; - } + 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 } @@ -922,23 +903,33 @@ unsigned char *XMLTree::GetTagName(TagType tagid) unsigned char *s; if (tagid >= ntagnames) return NULL; // invalid tag identifier - s = (unsigned char *)malloc((strlen((const char *)TagName[tagid])+1)*sizeof(unsigned char)); + 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 + +const unsigned char *XMLTree::GetTagNameByRef(TagType tagid) + { + if (tagid >= ntagnames) return NULL; // invalid tag identifier + return ((const unsigned char*) TagName[tagid]); + } + + + 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 **) realloc(TagName,ntagnames*(sizeof(unsigned char*))); + 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); }; diff --git a/XMLTree.h b/XMLTree.h index 759aff8..7c08fcc 100644 --- a/XMLTree.h +++ b/XMLTree.h @@ -26,6 +26,7 @@ #include #include +//KIM : OJO //clash between TextCollection/Tools.h and libcds/includes/basics.h #undef W #undef WW @@ -61,6 +62,13 @@ typedef struct { } range; +//KIM : OJO +// I know this class implements the working draft that we have but the logics seem flawed here... +// We should have two classes. One XMLTreeBuilder and one XMLTree. +// XMLTreeBuilder would have OpenDocument, NewOpenTag,... and CloseDocument would return an XMLTree +// XMLTree would have only an initialized structure. If find it really ugly to check (!finished) or (!initialized) +// in every function (FirstChild....). + class XMLTree { /** Balanced parentheses representation of the tree */ bp *Par; @@ -96,7 +104,17 @@ class XMLTree { int parArraySize; int ntagnames; unsigned int *empty_texts_aux; + + // KIM : OJO + // I added those two. The TagName array should always contains two special tags + // <@> for attributes and <$> for PCDATA. + // <$> can never be in a document (since we handle the text differently) + // but <@> can be returned by the parser. This boolean is needed for the construction + // of the Tag bitmap to know if <@> must be taken into account or not bool found_attributes; + + // KIM : OJO + // Allows to disable the TextCollection for benchmarkin purposes bool disable_tc; public: @@ -226,6 +244,7 @@ public: * (i.e. everything is considered an empty text *) * Returns a non-zero value upon success, NULLT in case of * error. */ + int OpenDocument(bool empty_texts, int sample_rate_text, bool dtc); /** CloseDocument(): finishes the construction of the data structure for @@ -265,6 +284,19 @@ public: unsigned char *GetTagName(TagType tagid); + // OJO + /** GetTagName(tagid): returns the tag name of a given tag identifier. + * The result is just a reference and should not be freed by the caller. + */ + const unsigned char *GetTagNameByRef(TagType tagid); + + //OJO + /** RegisterTag adds a new tag to the tag collection this is needed + * if the query contains a tag which is not in the document, we need + * to give this new tag a fresh id and store it somewhere. A logical + * choice is here. + * We might want to use a hashtable instead of an array though. + */ TagType RegisterTag(unsigned char *tagname); bool EmptyText(DocID i) { -- 2.17.1