From e2c476850d5598f78c8584530563491a7effd632 Mon Sep 17 00:00:00 2001 From: kim Date: Thu, 8 Sep 2011 02:44:06 +0000 Subject: [PATCH] - Implement popcount in ASM if available - Pass around extra file name to load/save for tc extra-index files. git-svn-id: svn+ssh://idea.nguyen.vg/svn/sxsi/trunk/XMLTree@1102 3cdefd35-fc62-479d-8e8d-bae585ffb9ca --- Makefile | 2 +- XMLTree.cpp | 346 ++++++++++++++++++++++++++-------------------------- XMLTree.h | 300 +++++++++++++++++++++++++-------------------- bpcore.c | 10 +- darray.c | 80 +++--------- darray.h | 2 +- 6 files changed, 361 insertions(+), 379 deletions(-) diff --git a/Makefile b/Makefile index fd24873..035d0d9 100644 --- a/Makefile +++ b/Makefile @@ -1,4 +1,4 @@ -OPT_FLAGS=-O6 -DPOPCOUNT_TABLE -DHAS_NATIVE_POPCOUNT -fno-PIC -static +OPT_FLAGS=-O4 -DPOPCOUNT_TABLE -DHAS_NATIVE_POPCOUNT -fno-PIC -static INC_FLAGS=-I./libcds/includes/ -I. CFLAGS= $(INC_FLAGS) $(OPT_FLAGS) CXXFLAGS= -std=c++0x $(INC_FLAGS) $(OPT_FLAGS) diff --git a/XMLTree.cpp b/XMLTree.cpp index 119048d..a1eb13c 100644 --- a/XMLTree.cpp +++ b/XMLTree.cpp @@ -7,8 +7,8 @@ using std::endl; using std::min; using std::string; -// functions to convert tag positions to the corresponding tree node and viceversa. -// These are implemented in order to be able to change the tree and Tags representations, +// functions to convert tag positions to the corresponding tree node and viceversa. +// These are implemented in order to be able to change the tree and Tags representations, // without affecting the code so much. // Current implementation corresponds to balanced-parentheses representation for // the tree, and storing 2 tags per tree node (opening and closing tags). @@ -20,7 +20,7 @@ static int bits8 (int t ) { return 8; else if (r <= 16) return 16; - else + else return r; } @@ -39,7 +39,7 @@ static treeNode fast_sibling(bp* Par,treeNode x,TagType tag){ inline uint get_field_no_power(uint *A, uint len, uint index) { - + register uint i=index*len/W, j=index*len-W*i; return (j+len <= W) ? (A[i] << (W-j-len)) >> (W-len) : (A[i] >> j) | (A[i+1] << (WW-j-len)) >> (W-len); @@ -64,7 +64,7 @@ static uint fast_get_field(uint* A,int len, int idx) -XMLTree::XMLTree( pb * const par, uint npar, vector * const TN, TagIdMap * const tim, +XMLTree::XMLTree( pb * const par, uint npar, vector * const TN, TagIdMap * const tim, uint *empty_texts_bmp, TagType *tags, TextCollection * const TC, bool dis_tc, TextCollectionBuilder::index_type_t _index_type ) @@ -79,19 +79,19 @@ XMLTree::XMLTree( pb * const par, uint npar, vector * const TN, TagIdM PRINTTIME("Building parenthesis struct", Building); STARTTIMER(); - + // creates structure for tags TagName = (vector*)TN; tIdMap = (TagIdMap *) tim; - + uint max_tag = TN->size() - 1; - - + + static_bitsequence_builder *bmb = new static_bitsequence_builder_sdarray(); alphabet_mapper *am = new alphabet_mapper_none(); Tags = new static_sequence_bs((uint*)tags,npar,am,bmb); - + //cout << "Tags test: " << Tags->test((uint*)tags,npar) << endl; //Ensures that for small tag numbers, we are on an 8bit boundary. @@ -102,13 +102,13 @@ XMLTree::XMLTree( pb * const par, uint npar, vector * const TN, TagIdM tags_fix = new uint[uint_len(tags_blen,tags_len)]; for(uint i=0;i<(uint)npar;i++) set_field(tags_fix,tags_blen,i,tags[i]); - delete bmb; + delete bmb; free(tags); tags = NULL; STOPTIMER(Building); PRINTTIME("Building Tag Structure", Building); - + Text = (TextCollection*) TC; @@ -117,32 +117,32 @@ XMLTree::XMLTree( pb * const par, uint npar, vector * const TN, TagIdM free(empty_texts_bmp); empty_texts_bmp = NULL; - + disable_tc = dis_tc; - text_index_type = _index_type; + text_index_type = _index_type; std::cerr << "Number of distinct tags " << TagName->size() << "\n"; //std::cerr.flush(); } // ~XMLTree: frees memory of XML tree. -XMLTree::~XMLTree() - { +XMLTree::~XMLTree() + { int i; destroyTree(Par); free(Par); // frees the memory of struct Par - + delete tIdMap; tIdMap = NULL; - + delete TagName; TagName = NULL; - + delete Tags; Tags = NULL; - delete Text; + delete Text; Text = NULL; delete EBVector; @@ -151,7 +151,7 @@ XMLTree::~XMLTree() } -void XMLTree::print_stats() +void XMLTree::print_stats() { uint total_space = Tags->size()+sizeof(static_sequence*); total_space += sizeof(uint*)+sizeof(uint)*(2+uint_len(tags_blen,tags_len)); @@ -162,11 +162,10 @@ void XMLTree::print_stats() << " *total* " << total_space << endl; } -// Save: saves XML tree data structure to file. -void XMLTree::Save(int fd) +// Save: saves XML tree data structure to file. +void XMLTree::Save(int fd, char * name) { FILE *fp; - char filenameaux[1024]; int i; fp = fdopen(fd, "wa"); @@ -179,7 +178,7 @@ void XMLTree::Save(int fd) ufwrite(&ntags, sizeof(int), 1, fp); for (i = 0; iat(i).c_str()); - + // stores the tags Tags->save(fp); @@ -187,39 +186,40 @@ void XMLTree::Save(int fd) ufwrite(&tags_len,sizeof(uint),1,fp); ufwrite(tags_fix,sizeof(uint),uint_len(tags_blen,tags_len),fp); - // flags + // flags ufwrite(&disable_tc, sizeof(bool),1,fp); - + //text positions EBVector->save(fp); - - // stores the texts + + // stores the texts if (!disable_tc) { ufwrite(&text_index_type, sizeof(TextCollectionBuilder::index_type_t), 1, fp); - - const char * pref; + + + string file(name); switch (text_index_type){ case TextCollectionBuilder::index_type_default: - pref = "default_"; + file.append(".default"); break; case TextCollectionBuilder::index_type_swcsa: - pref = "swcsa_"; + file.append(".swcsa"); break; case TextCollectionBuilder::index_type_rlcsa: - pref = "rlcsa_"; + file.append(".rlcsa"); break; }; - - Text->Save(fp, pref); - + + Text->Save(fp, file.c_str()); + } } // Load: loads XML tree data structure from file. Returns // a pointer to the loaded data structure -XMLTree *XMLTree::Load(int fd, bool load_tc,int sample_factor) +XMLTree *XMLTree::Load(int fd, bool load_tc,int sample_factor, char * name) { FILE *fp; @@ -236,7 +236,7 @@ XMLTree *XMLTree::Load(int fd, bool load_tc,int sample_factor) // Load the tree structure XML_Tree->Par = (bp *)umalloc(sizeof(bp)); - loadTree(XML_Tree->Par, fp); + loadTree(XML_Tree->Par, fp); STOPTIMER(Loading); PRINTTIME("Loading parenthesis struct", Loading); STARTTIMER(); @@ -245,7 +245,7 @@ XMLTree *XMLTree::Load(int fd, bool load_tc,int sample_factor) XML_Tree->tIdMap = new std::unordered_map(); std::string s; int ntags; - + // Load the tag names ufread(&ntags, sizeof(int), 1, fp); @@ -254,10 +254,10 @@ XMLTree *XMLTree::Load(int fd, bool load_tc,int sample_factor) throw "Cannot read tag list"; s = buffer; // remove the trailing \n - s.erase(s.size()-1); - XML_Tree->TagName->push_back(s); + s.erase(s.size()-1); + XML_Tree->TagName->push_back(s); XML_Tree->tIdMap->insert(std::make_pair(s,i)); - + }; STOPTIMER(Loading); PRINTTIME("Loading tag names struct", Loading); @@ -266,7 +266,7 @@ XMLTree *XMLTree::Load(int fd, bool load_tc,int sample_factor) // loads the tag structure XML_Tree->Tags = static_sequence::load(fp); ufread(&XML_Tree->tags_blen,sizeof(uint),1,fp); - std::cerr << "tags_blen is "<< XML_Tree->tags_blen <<"\n"; + std::cerr << "tags_blen is "<< XML_Tree->tags_blen <<"\n"; ufread(&XML_Tree->tags_len,sizeof(uint),1,fp); XML_Tree->tags_fix = new uint[uint_len(XML_Tree->tags_blen,XML_Tree->tags_len)]; ufread(XML_Tree->tags_fix,sizeof(uint),uint_len(XML_Tree->tags_blen,XML_Tree->tags_len),fp); @@ -280,14 +280,14 @@ XMLTree *XMLTree::Load(int fd, bool load_tc,int sample_factor) //XML_Tree->Tags->test(seq,XML_Tree->tags_len); //delete [] seq; /// End ugly tests - + STOPTIMER(Loading); std::cerr << (uint_len(XML_Tree->tags_blen,XML_Tree->tags_len)*sizeof(uint))/(1024*1024) << " MB for tag sequence" << std::endl; PRINTTIME("Loading tag struct", Loading); STARTTIMER(); // loads the flags - + ufread(&(XML_Tree->disable_tc), sizeof(bool), 1, fp); if (load_tc) { XML_Tree->EBVector = static_bitsequence_rrr02::load(fp); @@ -295,38 +295,38 @@ XMLTree *XMLTree::Load(int fd, bool load_tc,int sample_factor) STOPTIMER(Loading); PRINTTIME("Loading text bitvector struct", Loading); STARTTIMER(); - - // Not used + + // Not used // loads the texts if (!XML_Tree->disable_tc){ ufread(&(XML_Tree->text_index_type), sizeof(TextCollectionBuilder::index_type_t), 1, fp); - const char * pref; - switch (!XML_Tree->text_index_type){ + string file(name); + switch (XML_Tree->text_index_type){ case TextCollectionBuilder::index_type_default: - pref = "default_"; + file.append(".default"); break; case TextCollectionBuilder::index_type_swcsa: - pref = "swcsa_"; + file.append(".swcsa"); break; case TextCollectionBuilder::index_type_rlcsa: - pref = "rlcsa_"; + file.append(".rlcsa"); break; - }; - XML_Tree->Text = TextCollection::Load(fp, pref, TextCollection::index_mode_default, sample_factor); + }; + 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(); + STARTTIMER(); } else { XML_Tree->EBVector = NULL; XML_Tree->Text = NULL; XML_Tree->disable_tc = true; }; - + return XML_Tree; } @@ -334,27 +334,27 @@ XMLTree *XMLTree::Load(int fd, bool load_tc,int sample_factor) // SubtreeSize(x): the number of nodes (and attributes) in the subtree of node x. -/*int XMLTree::SubtreeSize(treeNode x) +/*int XMLTree::SubtreeSize(treeNode x) { return subtree_size(Par, x); } */ // SubtreeTags(x,tag): the number of occurrences of tag within the subtree of node x. /* -int XMLTree::SubtreeTags(treeNode x, TagType tag) +int XMLTree::SubtreeTags(treeNode x, TagType tag) { if (x == Root()) x = fast_first_child(Par,x); - + int s = x + 2*subtree_size(Par, x) - 1; - + return (Tags->rank(tag, s) - Tags->rank(tag, node2tagpos(x)-1))+1; } */ -int XMLTree::SubtreeElements(treeNode x) +int XMLTree::SubtreeElements(treeNode x) { - + int size = subtree_size(Par,x); if (x == Root()){ x = fast_first_child(Par,x); @@ -370,25 +370,25 @@ int XMLTree::SubtreeElements(treeNode x) size -= SubtreeSize(y); y = Tags->select_next(ATTRIBUTE_TAG_ID,node2tagpos(y)); }; - return size; + return size; } // IsLeaf(x): returns whether node x is leaf or not. In the succinct representation // this is just a bit inspection. -bool XMLTree::IsLeaf(treeNode x) +bool XMLTree::IsLeaf(treeNode x) { NULLT_IF(x==NULLT); return fast_isleaf(Par, x); - } + } // IsAncestor(x,y): returns whether node x is ancestor of node y. -bool XMLTree::IsAncestor(treeNode x, treeNode y) +bool XMLTree::IsAncestor(treeNode x, treeNode y) { return fast_is_ancestor(Par, x, y); } // 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 (!fast_is_ancestor(Par, x, y)) return false; return depth(Par, x) == (depth(Par, y) + 1); @@ -403,46 +403,46 @@ bool XMLTree::IsChild(treeNode x, treeNode y) // NumChildren(x): number of children of node x. Constant time with the data structure // of Sadakane. -int XMLTree::NumChildren(treeNode x) +int XMLTree::NumChildren(treeNode x) { return degree(Par, x); } // ChildNumber(x): returns i if node x is the i-th children of its parent. -int XMLTree::ChildNumber(treeNode x) +int XMLTree::ChildNumber(treeNode x) { return child_rank(Par, x); } // Depth(x): depth of node x, a simple binary rank on the parentheses sequence. -int XMLTree::Depth(treeNode x) +int XMLTree::Depth(treeNode x) { return depth(Par, x); } // Preorder(x): returns the preorder number of node x, just counting the tree // nodes (i.e., tags, it disregards the texts in the tree). -int XMLTree::Preorder(treeNode x) +int XMLTree::Preorder(treeNode x) { return preorder_rank(Par, x); } // 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) +int XMLTree::Postorder(treeNode x) { return postorder_rank(Par, x); } /* // Tag(x): returns the tag identifier of node x. -TagType XMLTree::Tag(treeNode x) +TagType XMLTree::Tag(treeNode x) { return fast_get_field(tags_fix,tags_blen,node2tagpos(x)); } */ // DocIds(x): returns the range of text identifiers that descend from node x. // returns {NULLT, NULLT} when there are no texts descending from x. -range XMLTree::DocIds(treeNode x) +range XMLTree::DocIds(treeNode x) { range r; if (x == NULLT) { @@ -450,8 +450,8 @@ range XMLTree::DocIds(treeNode x) r.max = NULLT; return r; }; - int min = EBVector->rank1(x-1); - int max = EBVector->rank1(x+2*subtree_size(Par, x)-2); + int min = EBVector->rank1(x-1); + int max = EBVector->rank1(x+2*subtree_size(Par, x)-2); if (min==max) { // range is empty, no texts within the subtree of x r.min = NULLT; r.max = NULLT; @@ -465,7 +465,7 @@ range XMLTree::DocIds(treeNode x) // Parent(x): returns the parent node of node x. /* -treeNode XMLTree::Parent(treeNode x) +treeNode XMLTree::Parent(treeNode x) { if (x == Root()) return NULLT; @@ -474,7 +474,7 @@ 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) +treeNode XMLTree::Child(treeNode x, int i) { if (i <= OPTD) return naive_child(Par, x, i); else return child(Par, x, i); @@ -482,46 +482,46 @@ treeNode XMLTree::Child(treeNode x, int i) // FirstChild(x): returns the first child of node x, assuming it exists. Very fast in BP. /* -treeNode XMLTree::FirstChild(treeNode x) +treeNode XMLTree::FirstChild(treeNode x) { NULLT_IF(x==NULLT); return fast_first_child(Par, x); } */ /* -treeNode XMLTree::FirstElement(treeNode x) +treeNode XMLTree::FirstElement(treeNode x) { NULLT_IF(x==NULLT); x = fast_first_child(Par, x); NULLT_IF(x == NULLT); switch (Tag(x)){ - + case PCDATA_TAG_ID: x = x+2; return (fast_inspect(Par,x)==OP)? x : NULLT; - - case ATTRIBUTE_TAG_ID: + + case ATTRIBUTE_TAG_ID: x = fast_next_sibling(Par,x); if (x != NULLT && Tag(x) == PCDATA_TAG_ID){ x = x+2; return (fast_inspect(Par,x)==OP)? x : NULLT; - } - else return x; + } + else return x; default: return x; } } *//* -treeNode XMLTree::NextElement(treeNode x) +treeNode XMLTree::NextElement(treeNode x) { NULLT_IF(x==NULLT); x = fast_next_sibling(Par, x); - NULLT_IF(x == NULLT); + NULLT_IF(x == NULLT); if (Tag(x) == PCDATA_TAG_ID){ x = x+2; return (fast_inspect(Par,x)==OP)? x : NULLT; } - else return x; + else return x; }*/ // LastChild(x): returns the last child of node x. @@ -532,7 +532,7 @@ treeNode XMLTree::NextElement(treeNode x) } */ // NextSibling(x): returns the next sibling of node x, assuming it exists. -/*treeNode XMLTree::NextSibling(treeNode x) +/*treeNode XMLTree::NextSibling(treeNode x) { NULLT_IF(x==NULLT || x == Root() ); x = fast_find_close(Par,x)+1; @@ -541,7 +541,7 @@ treeNode XMLTree::NextElement(treeNode x) */ // PrevSibling(x): returns the previous sibling of node x, assuming it exists. -/*treeNode XMLTree::PrevSibling(treeNode x) +/*treeNode XMLTree::PrevSibling(treeNode x) { NULLT_IF(x==NULLT); return prev_sibling(Par, x); @@ -551,11 +551,11 @@ treeNode XMLTree::NextElement(treeNode x) // Because of the balanced-parentheses representation of the tree, this operation is not supported // efficiently, just iterating among the children of node x until finding the desired child. /* -treeNode XMLTree::TaggedChild(treeNode x, TagType tag) +treeNode XMLTree::TaggedChild(treeNode x, TagType tag) { - + NULLT_IF(x==NULLT || fast_isleaf(Par,x)); - treeNode child; + treeNode child; child = fast_first_child(Par, x); // starts at first child of node x if (Tag(child) == tag) return child; @@ -572,25 +572,25 @@ treeNode XMLTree::TaggedFollowingSibling(treeNode x, TagType tag) while (sibling != NULLT) { ctag = Tag(sibling); if (ctag == tag) // current sibling is labeled with tag of interest - return sibling; + return sibling; sibling = fast_sibling(Par, sibling, ctag); // OK, let's try with the next sibling } - return NULLT; // no such sibling was found + return NULLT; // no such sibling was found } */ treeNode XMLTree::SelectChild(treeNode x, TagIdSet *tags) { - + NULLT_IF(x==NULLT || fast_isleaf(Par,x)); int i; - treeNode child = fast_first_child(Par, x); + treeNode child = fast_first_child(Par, x); TagType t; while (child != NULLT) { t = Tag(child); if (tags->find(t) != tags->end()) return child; child = fast_sibling(Par, child,t); } - return NULLT; + return NULLT; } @@ -606,14 +606,14 @@ treeNode XMLTree::SelectFollowingSibling(treeNode x, TagIdSet *tags) if (tags->find(t) != tags->end()) return sibling; sibling = fast_sibling(Par, sibling,t); } - return NULLT; + return NULLT; } // TaggedDescendant(x,tag): returns the first node tagged tag with larger preorder than x and within // the subtree of x. Returns NULLT if there is none. /* -treeNode XMLTree::TaggedDescendant(treeNode x, TagType tag) +treeNode XMLTree::TaggedDescendant(treeNode x, TagType tag) { //NULLT_IF(x==NULLT || fast_isleaf(Par,x)); @@ -621,7 +621,7 @@ treeNode XMLTree::TaggedDescendant(treeNode x, TagType tag) NULLT_IF (s == -1); treeNode y = tagpos2node(s); // transforms the tag position into a node position - + return (fast_is_ancestor(Par,x,y) ? y : NULLT); } */ @@ -647,8 +647,8 @@ treeNode XMLTree::SelectDescendant(treeNode x, TagIdSet *tags) // TaggedPrec(x,tag): returns the first node tagged tag with smaller preorder than x and not an // ancestor of x. Returns NULLT if there is none. -treeNode XMLTree::TaggedPreceding(treeNode x, TagType tag) - { +treeNode XMLTree::TaggedPreceding(treeNode x, TagType tag) + { int r, s; treeNode node_s, root; r = (int)Tags->rank(tag, node2tagpos(x)-1); @@ -662,7 +662,7 @@ treeNode XMLTree::TaggedPreceding(treeNode x, TagType tag) 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 } @@ -670,37 +670,37 @@ treeNode XMLTree::TaggedPreceding(treeNode x, TagType tag) // the subtree of x. Returns NULLT if there is none. treeNode XMLTree::TaggedFollowing(treeNode x, TagType tag) { - NULLT_IF (x ==NULLT || x == Root()); + NULLT_IF (x ==NULLT || x == Root()); return tagpos2node(Tags->select_next(tag,fast_find_close(Par, x))); - } + } -// TaggedFollBelow(x,tag,root): returns the first node tagged tag with larger preorder than x +// TaggedFollBelow(x,tag,root): returns the first node tagged tag with larger preorder than x // and not in the subtree of x. Returns NULLT if there is none. /* treeNode XMLTree::TaggedFollowingBelow(treeNode x, TagType tag, treeNode ancestor) { - // NULLT_IF (x == NULLT || x == Root() || x == ancestor); + // NULLT_IF (x == NULLT || x == Root() || x == ancestor); //Special optimisation, test for the following sibling first treeNode close = fast_find_close(Par, x); treeNode s = tagpos2node(Tags->select_next(tag, close)); - + if (ancestor == Root() || s==NULLT || s < fast_find_close(Par,ancestor)) return s; else return NULLT; -} +} */ /* treeNode XMLTree::TaggedFollowingBefore(treeNode x, TagType tag, treeNode closing) { NULLT_IF (x == NULLT || x == Root()); - - treeNode s = tagpos2node(Tags->select_next(tag, fast_find_close(Par, x))); + + treeNode s = tagpos2node(Tags->select_next(tag, fast_find_close(Par, x))); NULLT_IF (s == NULLT || s >= closing); - + return s; -} +} */ /* Here we inline TaggedFoll to find the min globally, and only at the end we check if the min is below the context node */ @@ -717,7 +717,7 @@ treeNode XMLTree::SelectFollowingBelow(treeNode x, TagIdSet *tags, treeNode ance int i; treeNode min = NULLT; treeNode aux; - + TagIdSet::const_iterator tagit; for (tagit = tags->begin(); tagit != tags->end(); ++tagit) { @@ -726,13 +726,13 @@ treeNode XMLTree::SelectFollowingBelow(treeNode x, TagIdSet *tags, treeNode ance if (aux == NULLT) continue; if ((min == NULLT) || (aux < min)) min = aux; }; - + // found the smallest node in preorder which is after x. // if ctx is the root node, just return what we found. if (ancestor == Root() || min == NULLT || min < fast_find_close(Par, ancestor)) return min; else return NULLT; - + } /* treeNode XMLTree::SelectFollowingBefore(treeNode x, TagIdSet *tags, treeNode ancestor_closing) @@ -748,7 +748,7 @@ treeNode XMLTree::SelectFollowingBefore(treeNode x, TagIdSet *tags, treeNode anc int i; treeNode min = NULLT; treeNode aux; - + TagIdSet::const_iterator tagit; for (tagit = tags->begin(); tagit != tags->end(); ++tagit) { @@ -757,13 +757,13 @@ treeNode XMLTree::SelectFollowingBefore(treeNode x, TagIdSet *tags, treeNode anc if (aux == NULLT) continue; if ((min == NULLT) || (aux < min)) min = aux; }; - + // found the smallest node in preorder which is after x. // if ctx is the root node, just return what we found. if (ancestor_closing == Root() || min == NULLT || min < ancestor_closing) return min; else return NULLT; - + } */ /* @@ -780,33 +780,33 @@ treeNode XMLTree::SelectFollowingBefore(treeNode x, TagIdSet *tags, treeNode clo for (tagit = tags->begin(); tagit != tags->end(); tagit++) { aux = tagpos2node(Tags->select_next(*tagit, close)); - + // The next sibling of x is guaranteed to be below ctx // and is the node with lowest preorder which is after ctx. // if we find it, we return early; - + if (aux == ns ) return ns; if (aux == NULLT) continue; if ((min == NULLT) || (aux < min)) min = aux; }; - + // found the smallest node in preorder which is after x. // if ctx is the root node, just return what we found. NULLT_IF (min == NULLT || min >= closing); - + return min; - + } */ // TaggedAncestor(x, tag): returns the closest ancestor of x tagged tag. Return // NULLT is there is none. treeNode XMLTree::TaggedAncestor(treeNode x, TagType tag) - { + { if (x == NULLT || x == Root()) return NULLT; - + treeNode s = parent(Par, x), r = Root(); while (s != r) { if (Tag(s) == tag) return s; @@ -817,42 +817,42 @@ treeNode XMLTree::TaggedAncestor(treeNode x, TagType tag) -// MyText(x): returns the document identifier of the text below node x, -// or NULLT if x is not a leaf node or the text is empty. Assumes Doc +// MyText(x): returns the document identifier of the text below node x, +// or NULLT if x is not a leaf node or the text is empty. Assumes Doc // ids start from 0. -DocID XMLTree::MyText(treeNode x) +DocID XMLTree::MyText(treeNode x) { TagType tag = Tag(x); // seems faster than testing EBVector->access(x); if (tag == PCDATA_TAG_ID || tag == ATTRIBUTE_DATA_TAG_ID) - return (DocID) (EBVector->rank1(x)-1); - else + return (DocID) (EBVector->rank1(x)-1); + else return (DocID) NULLT; - + } -// MyText(x): returns the document identifier of the text below node x, -// or NULLT if x is not a leaf node or the text is empty. Assumes Doc +// MyText(x): returns the document identifier of the text below node x, +// or NULLT if x is not a leaf node or the text is empty. Assumes Doc // ids start from 0. -DocID XMLTree::MyTextUnsafe(treeNode x) +DocID XMLTree::MyTextUnsafe(treeNode x) { return (DocID) (EBVector->rank1(x)-1); //-1 because document ids start from 0 - + } // TextXMLId(d): returns the preorder of document with identifier d in the tree consisting of // all tree nodes and all text nodes. Assumes that the tree root has preorder 1. -int XMLTree::TextXMLId(DocID d) +int XMLTree::TextXMLId(DocID d) { NULLT_IF(d == NULLT); int s = EBVector->select1(d+1); return rank_open(Par, s) + d + 1; // +1 because root has preorder 1 - + } -// NodeXMLId(x): returns the preorder of node x in the tree consisting +// NodeXMLId(x): returns the preorder of node x in the tree consisting // of all tree nodes and all text nodes. Assumes that the tree root has // preorder 0; -int XMLTree::NodeXMLId(treeNode x) +int XMLTree::NodeXMLId(treeNode x) { NULLT_IF(x == NULLT); if (x == Root()) return 1; // root node has preorder 1 @@ -860,21 +860,21 @@ int XMLTree::NodeXMLId(treeNode x) } // ParentNode(d): returns the parent node of document identifier d. -treeNode XMLTree::ParentNode(DocID d) - { - NULLT_IF (d == NULLT); - return (treeNode) EBVector->select1(d+1); +treeNode XMLTree::ParentNode(DocID d) + { + NULLT_IF (d == NULLT); + return (treeNode) EBVector->select1(d+1); } // GetTagId: returns the tag identifier corresponding to a given tag name. // Returns NULLT in case that the tag name does not exists. TagType XMLTree::GetTagId(unsigned char *tagname) { - + string s = (char *) tagname; - TagIdMapIT it = tIdMap->find(s); + TagIdMapIT it = tIdMap->find(s); return (TagType) ((it != tIdMap->end()) ? it->second : -1); - + } @@ -886,7 +886,7 @@ unsigned char *XMLTree::GetTagName(TagType tagid) if ( tagid < 0 || tagid >= TagName->size()) return (unsigned char *) ""; strcpy((char *)s, (*TagName)[tagid].c_str()); - + return (s == NULL ? (unsigned char*) "" : s); } @@ -897,27 +897,27 @@ const unsigned char *XMLTree::GetTagNameByRef(TagType tagid) unsigned char *s; if ( tagid < 0 || tagid >= TagName->size()) return (unsigned char *) ""; - + return (const unsigned char *) (*TagName)[tagid].c_str(); - + } TagType XMLTree::RegisterTag(unsigned char *tagname) - { + { TagType id = XMLTree::GetTagId(tagname); if (id == NULLT) { - string s = (char *) tagname; - REGISTER_TAG(TagName,tIdMap,s); + string s = (char *) tagname; + REGISTER_TAG(TagName,tIdMap,s); }; - + return id; } treeNode XMLTree::Closing(treeNode x) { - return fast_find_close(Par,x); + return fast_find_close(Par,x); } bool XMLTree::IsOpen(treeNode x) { return fast_inspect(Par,x); } @@ -925,8 +925,8 @@ bool XMLTree::IsOpen(treeNode x) { return fast_inspect(Par,x); } void XMLTree::Print(int fd,treeNode x, bool no_text){ - - if (buffer == 0) { + + if (buffer == 0) { buffer = new string(BUFFER_ALLOC, 0); buffer->clear(); print_stack = new std::vector(); @@ -936,30 +936,30 @@ void XMLTree::Print(int fd,treeNode x, bool no_text){ treeNode fin = fast_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) + + 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 (fast_inspect(Par,n)){ - if (tag == PCDATA_TAG_ID) { - + if (tag == PCDATA_TAG_ID) { + if (no_text) _dputs("<$/>", fd); else { @@ -968,10 +968,10 @@ void XMLTree::Print(int fd,treeNode x, bool no_text){ }; n+=2; // skip closing $ tag = Tag(n); - + } else { - _dputc('<',fd); + _dputc('<',fd); _dput_str((*TagName)[tag], fd); n++; if (fast_inspect(Par,n)) { @@ -1005,15 +1005,15 @@ void XMLTree::Print(int fd,treeNode x, bool no_text){ else _dputc('>', fd); n++; tag=Tag(n); - - } else + + } else _dputc('>', fd); - + } else {// tag _dputs("/>", fd); n++; - tag=Tag(n); - }; + tag=Tag(n); + }; }; } else do { _dputs("= -1) return r+1; + return -1; +} + static inline int fast_find_close(bp *b,int s) { return fwd_excess(b,s,-1); } +static inline int fast_find_parent_close(bp *b,int s) +{ + return fwd_excess(b,s,-2); +} + + static inline int fast_inspect(bp* Par,treeNode i) { int j,l; @@ -132,12 +146,12 @@ inline static bool fast_is_ancestor(bp * Par,treeNode x,treeNode y){ } // tag position -> tree node -static treeNode tagpos2node(int t) +static treeNode tagpos2node(int t) { return (treeNode) t; } // tree node -> tag position -static int node2tagpos(treeNode x) +static int node2tagpos(treeNode x) { return (int)x; } @@ -153,13 +167,13 @@ class XMLTree { private: /** Balanced parentheses representation of the tree */ bp *Par; - - /** Mapping from tag identifer to tag name */ + + /** Mapping from tag identifer to tag name */ std::vector *TagName; TagIdMap * tIdMap; - + /** Bit vector indicating with a 1 the positions of the non-empty texts. */ - static_bitsequence *EBVector; + static_bitsequence *EBVector; /** Tag sequence represented with a data structure for rank and select */ static_sequence *Tags; @@ -172,21 +186,28 @@ class XMLTree { // Allows to disable the TextCollection for benchmarkin purposes bool disable_tc; SXSI::TextCollectionBuilder::index_type_t text_index_type; - + std::string *buffer; std::vector *print_stack; + + void _real_flush(int fd, size_t size) { + if (size == 0) return; + size_t written; + while (1) { + written = write(fd, buffer->data(), size); + if ((written < 0) && (errno == EAGAIN || errno == EINTR)) + continue; + break; + }; + buffer->clear(); + + } + void _flush(int fd){ size_t size = buffer->size(); if (size < BUFFER_SIZE) return; - size_t written; - while (1) { - written = write(fd, buffer->data(), size); - if ((written < 0) && (errno == EAGAIN || errno == EINTR)) - continue; - break; - }; - buffer->clear(); + _real_flush(fd, size); } void _dput_str(std::string s, int fd){ @@ -196,7 +217,7 @@ class XMLTree { void _dputs(const char* s, int fd){ buffer->append(s); - _flush(fd); + _flush(fd); } void _dputc(const char c, int fd){ @@ -245,10 +266,10 @@ class XMLTree { TextCollection * const TC, bool dis_tc, TextCollectionBuilder::index_type_t _index_type ); -public: +public: /** Data structure destructor */ ~XMLTree(); - + /** root(): returns the tree root. */ treeNode Root() { return 0; } @@ -268,16 +289,16 @@ public: unsigned int * TagStruct() { return tags_fix; }; - /** SubtreeSize(x): the number of nodes (and attributes) in the subtree of + /** SubtreeSize(x): the number of nodes (and attributes) in the subtree of * node x. */ int SubtreeSize(treeNode x) { return subtree_size(Par, x); } - - /** SubtreeTags(x,tag): the number of occurrences of tag within the subtree + + /** SubtreeTags(x,tag): the number of occurrences of tag within the subtree * of node x. */ int SubtreeTags(treeNode x, TagType tag){ //int s = x + 2*subtree_size(Par, x) - 1; treeNode y = fast_find_close(Par, x); - + if (y - x < 10) { int count = 0; for(int i = x; i < y; i++) @@ -287,12 +308,12 @@ public: else return (Tags->rank(tag, y) - Tags->rank(tag, x)); }; - + /** SubtreeElements(x) of element nodes in the subtree of x */ int SubtreeElements(treeNode x); - /** IsLeaf(x): returns whether node x is leaf or not. In the succinct + /** IsLeaf(x): returns whether node x is leaf or not. In the succinct * representation this is just a bit inspection. */ bool IsLeaf(treeNode x); @@ -300,43 +321,54 @@ public: /** IsAncestor(x,y): returns whether node x is ancestor of node y. */ bool IsAncestor(treeNode x, treeNode y); - + + + /** IsRigthDescendant returns true if y is a descendant of x and y is + not a descendant of the first child of x */ + bool IsRightDescendant(treeNode x, treeNode y) { + if (x <= Root()) return false; + treeNode z = fast_find_parent_close(Par, x); + treeNode c = fast_find_close(Par, x); + return (y > c && y < z ); + } + + /** IsChild(x,y): returns whether node x is parent of node y. */ bool IsChild(treeNode x, treeNode y); /** IsFirstChild(x): returns whether node x is the first child of its parent. */ /* OCAML */ - bool IsFirstChild(treeNode x) { + bool 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 + + /** NumChildren(x): number of children of node x. Constant time with the * data structure of Sadakane. */ int NumChildren(treeNode x); - /** ChildNumber(x): returns i if node x is the i-th children of its + /** ChildNumber(x): returns i if node x is the i-th children of its * parent. */ int ChildNumber(treeNode x); - /** Depth(x): depth of node x, a simple binary rank on the parentheses + /** Depth(x): depth of node x, a simple binary rank on the parentheses * sequence. */ int Depth(treeNode x); - - /** Preorder(x): returns the preorder number of node x, just regarding tree - * nodes (and not texts). */ + + /** Preorder(x): returns the preorder number of node x, just regarding tree + * nodes (and not texts). */ int Preorder(treeNode x); - - /** Postorder(x): returns the postorder number of node x, just regarding + + /** Postorder(x): returns the postorder number of node x, just regarding * tree nodes (and not texts). */ int Postorder(treeNode x); - - /** DocIds(x): returns the range (i.e., a pair of integers) of document + + /** DocIds(x): returns the range (i.e., a pair of integers) of document * identifiers that descend from node x. */ range DocIds(treeNode x); /** Parent(x): returns the parent node of node x. */ - treeNode Parent(treeNode x) { + treeNode Parent(treeNode x) { if (x == Root()) return NULLT; else @@ -344,17 +376,17 @@ public: }; treeNode BinaryParent(treeNode x){ - if (x <= Root()) - return NULLT; - else { - treeNode prev = x - 1; - return (fast_inspect(Par, prev) == OP) ? prev : find_open(Par, prev); - }; + if (x <= Root()) + return NULLT; + else { + treeNode prev = x - 1; + return (fast_inspect(Par, prev) == OP) ? prev : fast_find_open(Par, prev); + }; }; /* Assumes x is neither 0 nor -1 */ - - /** Child(x,i): returns the i-th child of node x, assuming it exists. */ + + /** Child(x,i): returns the i-th child of node x, assuming it exists. */ treeNode Child(treeNode x, int i); @@ -362,10 +394,10 @@ public: /** LastChild(x): returns the last child of node x. */ treeNode LastChild(treeNode x) { NULLT_IF(x == NULLT || fast_isleaf(Par,x)); - return find_open(Par, fast_find_close(Par, x)-1); + return fast_find_open(Par, fast_find_close(Par, x)-1); } - - /** PrevSibling(x): returns the previous sibling of node x, assuming it + + /** PrevSibling(x): returns the previous sibling of node x, assuming it * exists. */ treeNode PrevSibling(treeNode x) @@ -374,18 +406,18 @@ public: return prev_sibling(Par, x); } - - /** TaggedChild(x,tag): returns the first child of node x tagged tag, or - * NULLT if there is none. Because of the balanced-parentheses representation - * of the tree, this operation is not supported efficiently, just iterating + + /** 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 SelectChild(treeNode x, TagIdSet * tags); - /** TaggedFollowingSibling(x,tag): returns the first sibling of node x tagged tag, or + /** TaggedFollowingSibling(x,tag): returns the first sibling of node x tagged tag, or * NULLT if there is none. */ - + treeNode SelectFollowingSibling(treeNode x, TagIdSet * tags); @@ -400,19 +432,19 @@ public: TagIdSet::const_iterator tagit; for (tagit = tags->begin(); tagit != tags->end(); ++tagit) { - aux = TaggedDescendant(x, (TagType) *tagit); + aux = TaggedDescendant(x, (TagType) *tagit); if (((unsigned int) aux) < ((unsigned int) min)) min = aux; }; 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 + /** 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 TaggedPreceding(treeNode x, TagType tag); - - /** TaggedFoll(x,tag): returns the first node tagged tag with larger - * preorder than x and not in the subtree of x. Returns NULLT if there + + /** 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 TaggedFollowing(treeNode x, TagType tag); @@ -429,63 +461,63 @@ public: treeNode close = fast_find_close(Par,x); - + treeNode min = NULLT; treeNode aux; - + TagIdSet::const_iterator tagit; for (tagit = tags->begin(); tagit != tags->end(); ++tagit) { - aux = tagpos2node(Tags->select_next(*tagit, close)); + aux = tagpos2node(Tags->select_next(*tagit, close)); if (((unsigned int) aux) < ((unsigned int) min)) min = aux; }; - + return (min < ancestor_closing) ? min : NULLT; - + } - /** TaggedAncestor(x, tag): returns the closest ancestor of x tagged + /** TaggedAncestor(x, tag): returns the closest ancestor of x tagged * tag. Return NULLT is there is none. */ treeNode TaggedAncestor(treeNode x, TagType tag); - - /** PrevText(x): returns the document identifier of the text to the left of + + /** PrevText(x): returns the document identifier of the text to the left of * node x, or NULLT if x is the root node. */ DocID PrevText(treeNode x); - - /** NextText(x): returns the document identifier of the text to the right of + + /** NextText(x): returns the document identifier of the text to the right of * node x, or NULLT if x is the root node. */ DocID NextText(treeNode x); - - /** MyText(x): returns the document identifier of the text below node x, or + + /** MyText(x): returns the document identifier of the text below node x, or * NULLT if x is not a leaf node. */ DocID MyText(treeNode x); DocID MyTextUnsafe(treeNode x); - /** TextXMLId(d): returns the preorder of document with identifier d in the + /** TextXMLId(d): returns the preorder of document with identifier d in the * tree consisting of all tree nodes and all text nodes. */ int TextXMLId(DocID d); - - /** NodeXMLId(x): returns the preorder of node x in the tree consisting of + + /** NodeXMLId(x): returns the preorder of node x in the tree consisting of * all tree nodes and all text nodes. */ int NodeXMLId(treeNode x); - + /** ParentNode(d): returns the parent node of document identifier d. */ treeNode ParentNode(DocID d); - + treeNode PrevNode(DocID d); - /** GetTagId(tagname): returns the tag identifier corresponding to a given + /** GetTagId(tagname): returns the tag identifier corresponding to a given * tag name. Returns NULLT in case that the tag name does not exists. */ TagType GetTagId(unsigned char *tagname); - /** GetTagName(tagid): returns the tag name of a given tag identifier. + /** GetTagName(tagid): returns the tag name of a given tag identifier. * Returns NULL in case that the tag identifier is not valid.*/ unsigned char *GetTagName(TagType tagid); - /** GetTagName(tagid): returns the tag name of a given tag identifier. + /** 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); @@ -527,35 +559,35 @@ public: TextCollection::document_result LessThan(uchar const *s) { return Text->LessThan(s); } - + /** IsPrefix(x): returns true if there is a text prefixed by string s. */ bool IsPrefix(uchar const *s) { return Text->IsPrefix(s); - } - - /** IsSuffix(s): returns true if there is a text having string s as a + } + + /** IsSuffix(s): returns true if there is a text having string s as a * suffix.*/ bool IsSuffix(uchar const *s) { return Text->IsSuffix(s); } - - /** IsEqual(s): returns true if there is a text that equals given + + /** IsEqual(s): returns true if there is a text that equals given * string s. */ bool IsEqual(uchar const *s) { return Text->IsEqual(s); } - + /** IsContains(s): returns true if there is a text containing string s. */ bool IsContains(uchar const *s) { return Text->IsContains(s); } - - /** IsLessThan(s): returns true if there is at least a text that is + + /** IsLessThan(s): returns true if there is at least a text that is * lexicographically smaller than string s. */ bool IsLessThan(uchar const *s) { return Text->IsLessThan(s); } - + /** Count(s): Global counting */ unsigned Count(uchar const *s) { return Text->Count(s); @@ -565,31 +597,31 @@ public: unsigned CountPrefix(uchar const *s) { return Text->CountPrefix(s); } - + /** CountSuffix(s): counting version of Suffix(s). */ unsigned CountSuffix(uchar const *s) { return Text->CountSuffix(s); } - + /** CountEqual(s): counting version of Equal(s). */ unsigned CountEqual(uchar const *s) { return Text->CountEqual(s); } - + /** CountContains(s): counting version of Contains(s). */ unsigned CountContains(uchar const *s) { return Text->CountContains(s); } - + /** CountLessThan(s): counting version of LessThan(s). */ unsigned CountLessThan(uchar const *s) { return Text->CountLessThan(s); } - + /** GetText(d): returns the text corresponding to document with * id d. */ uchar* GetText(DocID d) { - + uchar * s = Text->GetText(d); return (s[0] == 1 ? (s+1) : s); } @@ -604,19 +636,19 @@ public: TextCollection *getTextCollection() { return Text; } - + /** Save: saves XML tree data structure to file. */ - void Save(int fd ); - - /** Load: loads XML tree data structure from file. sample_rate_text + void Save(int fd, char* name ); + + /** Load: loads XML tree data structure from file. sample_rate_text * indicates the sample rate for the text search data structure. */ - static XMLTree *Load(int fd, bool load_tc, int sample_factor); + static XMLTree *Load(int fd, bool load_tc, int sample_factor, char * name); void insertTag(TagType tag, uint position); - + void print_stats(); - + /** Parenthesis functions */ treeNode Closing(treeNode x); @@ -626,7 +658,7 @@ public: /** Print procedure */ void Print(int fd,treeNode x, bool no_text); void Print(int fd,treeNode x) { Print(fd,x,false); } - void Flush(int fd){ _flush(fd); } + void Flush(int fd){ if (buffer) _real_flush(fd, buffer->size()); } // The following are inlined here for speed /** Tag(x): returns the tag identifier of node x. */ @@ -634,13 +666,13 @@ public: inline TagType Tag(treeNode x) const throw () { if (tags_blen == 8) return (TagType) (((uchar*)tags_fix)[(int) x]); - else + else return get_field(tags_fix, tags_blen, x); /* - { + { size_t idxlen = x * tags_blen; size_t j = idxlen % W; - size_t i = idxlen / W; + size_t i = idxlen / W; size_t offset = W - tags_blen; size_t offset2 = offset - j; size_t w = tags_fix[i]; @@ -669,28 +701,28 @@ public: NULLT_IF(x == NULLT); switch (Tag(x)){ - case ATTRIBUTE_TAG_ID: + case ATTRIBUTE_TAG_ID: x = fast_next_sibling(Par,x); if (x == NULLT || Tag(x) != PCDATA_TAG_ID) return x; - + case PCDATA_TAG_ID: x = x+2; return (fast_inspect(Par,x)==OP)? x : NULLT; - + default: return x; } } }; - /** NextSibling(x): returns the next sibling of node x, or NULLT if none + /** NextSibling(x): returns the next sibling of node x, or NULLT if none * exists. */ - + treeNode NextSibling(treeNode x) { NULLT_IF (x <= 0); return fast_next_sibling(Par, x); }; - + /** NextElement(x): returns the first non text, non attribute sibling of node x, or NULLT * if none. */ @@ -698,32 +730,32 @@ public: { NULLT_IF(x <= 0); x = fast_next_sibling(Par, x); - NULLT_IF(x == NULLT); + NULLT_IF(x == NULLT); if (Tag(x) == PCDATA_TAG_ID){ int y = x+2; return (fast_inspect(Par, y) == OP) ? y : NULLT; } - else return x; + else return x; }; - /** TaggedDesc(x,tag): returns the first node tagged tag with larger - * preorder than x and within the subtree of x. Returns NULT if there + /** TaggedDesc(x,tag): returns the first node tagged tag with larger + * preorder than x and within the subtree of x. Returns NULT if there * is none. */ inline treeNode TaggedDescendant(treeNode x, TagType tag) { - + int s = (int) Tags->select_next(tag,node2tagpos(x)); NULLT_IF (s == -1); - + treeNode y = tagpos2node(s); // transforms the tag position into a node position - + return (fast_is_ancestor(Par,x,y) ? y : NULLT); }; - + inline treeNode TaggedFollowingBelow(treeNode x, TagType tag, treeNode ancestor) { treeNode close = fast_find_close(Par, x); treeNode s = tagpos2node(Tags->select_next(tag, close)); - + if (ancestor == Root() || s == NULLT || s < fast_find_close(Par,ancestor)) return s; else return NULLT; }; @@ -732,11 +764,11 @@ public: { treeNode close = fast_find_close(Par, x); treeNode s = tagpos2node(Tags->select_next(tag, close)); - + if (ancestor_closing == Root() || s == NULLT || s < ancestor_closing) return s; else return NULLT; }; - + // TaggedSibling(x,tag): returns the first sibling of node x tagged tag, or NULLT if there is none. treeNode TaggedFollowingSibling(treeNode x, TagType tag) { @@ -745,18 +777,18 @@ treeNode TaggedFollowingSibling(treeNode x, TagType tag) TagType ctag; while ((sibling = fast_next_sibling(Par, sibling)) != NULLT) { ctag = Tag(sibling); - if (ctag == tag) return sibling; + if (ctag == tag) return sibling; } - return NULLT; + return NULLT; }; -treeNode TaggedChild(treeNode x, TagType tag) +treeNode TaggedChild(treeNode x, TagType tag) { - + NULLT_IF(x==NULLT || fast_isleaf(Par,x)); - treeNode child; + treeNode child; child = fast_first_child(Par, x); - + if (Tag(child) == tag) return child; else diff --git a/bpcore.c b/bpcore.c index df39e2c..5c8ec4a 100644 --- a/bpcore.c +++ b/bpcore.c @@ -1,6 +1,8 @@ #include #include #include "bp.h" +#include "utils.h" + #ifndef min #define min(x,y) ((x)<(y)?(x):(y)) @@ -130,7 +132,7 @@ int search_SB_r(bp *b, int i, int rel) } } r = min(j,ETW); - rel -= 2*popCount[w]-r; + rel -= 2*popcount(w)-r; x <<= r; i += r; j -= r; @@ -329,7 +331,7 @@ int degree_SB(bp *b, int i, int t, int rel, int *ans, int ith) } r = min(j,ETW); - d += 2*popCount[w]-r; + d += 2*popcount(w)-r; x <<= r; i += r; j -= r; @@ -615,7 +617,7 @@ int search_SB_l(bp *b, int i, int rel) } } r = min(j,ETW); - rel += 2*popCount[w]-r; + rel += 2*popcount(w)-r; x >>= r; i -= r; j -= r; @@ -764,7 +766,7 @@ int rmq_SB(bp *b, int s, int t, int opt, int *dm) } r = min(j,ETW); - d += 2*popCount[w]-r; + d += 2*popcount(w)-r; x <<= r; i += r; j -= r; diff --git a/darray.c b/darray.c index 780b967..890de45 100644 --- a/darray.c +++ b/darray.c @@ -1,6 +1,7 @@ #include #include #include "darray.h" +#include "utils.h" //typedef unsigned char byte; //typedef unsigned short word; @@ -134,61 +135,6 @@ static const unsigned int popCount[] = { static int selecttbl[8*256]; -unsigned int popcount_old(pb x) -{ - pb r; -#if 0 - r = x; - r = r - ((r>>1) & 0x77777777) - ((r>>2) & 0x33333333) - ((r>>3) & 0x11111111); - r = ((r + (r>>4)) & 0x0f0f0f0f) % 0xff; -#elif 1 - r = x; - r = ((r & 0xaaaaaaaa)>>1) + (r & 0x55555555); - r = ((r & 0xcccccccc)>>2) + (r & 0x33333333); - //r = ((r & 0xf0f0f0f0)>>4) + (r & 0x0f0f0f0f); - r = ((r>>4) + r) & 0x0f0f0f0f; - //r = ((r & 0xff00ff00)>>8) + (r & 0x00ff00ff); - r = (r>>8) + r; - //r = ((r & 0xffff0000)>>16) + (r & 0x0000ffff); - r = ((r>>16) + r) & 63; -#else - r = popCount[x & 0xff]; - x >>= 8; - r += popCount[x & 0xff]; - x >>= 8; - r += popCount[x & 0xff]; - x >>= 8; - r += popCount[x & 0xff]; -#endif - return r; -} - -inline unsigned int -popcount(pb x) -{ - uint m1 = 0x55555555; - uint m2 = 0xc30c30c3; - x -= (x >> 1) & m1; - x = (x & m2) + ((x >> 2) & m2) + ((x >> 4) & m2); - x += x >> 6; - return (x + (x >> 12) + (x >> 24)) & 0x3f; -} - - -unsigned int popcount8(pb x) -{ - dword r; -#if 1 - r = x; - r = ((r & 0xaa)>>1) + (r & 0x55); - r = ((r & 0xcc)>>2) + (r & 0x33); - r = ((r>>4) + r) & 0x0f; -#else - r = popCount[x & 0xff]; -#endif - return r; -} - void make_selecttbl(void) { int i,x,r; @@ -416,17 +362,19 @@ int darray_rank0(darray *da, int i) int darray_rank(darray *da, int i) { - int r,j; + int r,j,i_rr, i_rrr; pb *p; + i_rr = i >> logRR; + i_rrr = i >> logRRR; + r = da->rl[i>>logR] + da->rm[i_rr]; - r = da->rl[i>>logR] + da->rm[i>>logRR]; - j = (i>>logRRR) & (RR/RRR-1); + j = (i_rrr) & (RR/RRR-1); while (j > 0) { - r += da->rs[((i>>logRR)<<(logRR-logRRR))+j-1]; + r += da->rs[((i_rr)<<(logRR-logRRR))+j-1]; j--; } - p = da->buf + ((i>>logRRR)<<(logRRR-logD)); + p = da->buf + ((i_rrr)<<(logRRR-logD)); j = i & (RRR-1); while (j >= D) { r += popcount(*p++); @@ -618,8 +566,8 @@ int darray_select(darray *da, int i,int f) x = *q; while (1) { //rr = popcount(x >> (D-8)); - rr = popCount[x >> (D-8)]; - //rr = popcount8(x >> (D-8)); + //rr = popcount(x >> (D-8)); + rr = popcount8(x >> (D-8)); if (r + rr >= i) break; r += rr; p += 8; @@ -643,8 +591,8 @@ int darray_select(darray *da, int i,int f) while (1) { //rr = popcount(x >> (D-8)); - rr = popCount[x >> (D-8)]; - //rr = popcount8(x >> (D-8)); + //rr = popCount[x >> (D-8)]; + rr = popcount8(x >> (D-8)); if (r + rr >= i) break; r += rr; p += 8; @@ -700,8 +648,8 @@ int darray_pat_select(darray *da, int i, pb (*getpat)(pb *)) x = getpat(q); while (1) { //rr = popcount(x >> (D-8)); - rr = popCount[x >> (D-8)]; - //rr = popcount8(x >> (D-8)); + //rr = popCount[x >> (D-8)]; + rr = popcount8(x >> (D-8)); if (r + rr >= i) break; r += rr; p += 8; diff --git a/darray.h b/darray.h index f5603c6..a88150b 100644 --- a/darray.h +++ b/darray.h @@ -41,7 +41,7 @@ int setbit(pb *B, int i,int x); int setbits(pb *B, int i, int d, int x); int getbit(pb *B, int i); dword getbits(pb *B, int i, int d); -unsigned int popcount(pb x); +//unsigned int popcount(pb x); int darray_construct(darray *da, int n, pb *buf,int opt); int darray_select(darray *da, int i,int f); -- 2.17.1