-/******************************************************************************\r
- * Copyright (C) 2008 by Diego Arroyuelo *\r
- * Interface for the in-memory XQuery/XPath engine *\r
- * *\r
- * This program is free software; you can redistribute it and/or modify *\r
- * it under the terms of the GNU Lesser General Public License as published *\r
- * by the Free Software Foundation; either version 2 of the License, or *\r
- * (at your option) any later version. *\r
- * *\r
- * This program is distributed in the hope that it will be useful, *\r
- * but WITHOUT ANY WARRANTY; without even the implied warranty of *\r
- * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the *\r
- * GNU Lesser General Public License for more details. *\r
- * *\r
- * You should have received a copy of the GNU Lesser General Public License *\r
- * along with this program; if not, write to the *\r
- * Free Software Foundation, Inc., *\r
- * 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. *\r
- ******************************************************************************/\r
-\r
-#ifndef XMLTREE_H_\r
-#define XMLTREE_H_\r
-\r
-\r
-#include <unordered_set>\r
-#include <unordered_map>\r
-#include <sstream>\r
-#include "TextCollection/TextCollectionBuilder.h"\r
-\r
-#undef W\r
-#undef WW\r
-#undef Wminusone\r
-\r
-#include "bp.h"\r
-#include <libcds/includes/basics.h>\r
-#include <static_bitsequence.h>\r
-#include <alphabet_mapper.h>\r
-#include <static_sequence.h>\r
-using SXSI::TextCollection;\r
-using SXSI::TextCollectionBuilder;\r
-\r
-\r
-// this constant is used to efficiently compute the child operation in the tree\r
-#define OPTD 10\r
-\r
-#define NULLT -1\r
-\r
-#define PERM_SAMPLE 10\r
-\r
-\r
-typedef int treeNode;\r
-typedef int TagType; \r
-typedef int DocID; \r
-\r
-typedef struct {\r
- int min;\r
- int max;\r
-} range;\r
-\r
-// Encoding of the XML Document :\r
-// The following TAGs and IDs are fixed, "" is the tag of the root.\r
-// a TextNode is represented by a leaf <<$>></<$>> The DocId in the TextCollection\r
-// of that leaf is kept in a bit sequence.\r
-// a TextNode below an attribute is likewise represented by a leaf <<@$>><</@$>>\r
-// An element <e a1="v1" a2="v2" ... an="vn" > ...</e> the representation is:\r
-// <e><<@>> <<@>a1> <<$@>>DocID(v1)</<$@>></<@>a1> ... </<@>> .... </e>\r
-// Hence the attributes (if any) are always below the first child of their element,\r
-// as the children of a fake node <@>.\r
-\r
-\r
-#define DOCUMENT_OPEN_TAG ""\r
-#define DOCUMENT_TAG_ID 0\r
-#define ATTRIBUTE_OPEN_TAG "<@>"\r
-#define ATTRIBUTE_TAG_ID 1\r
-#define PCDATA_OPEN_TAG "<$>"\r
-#define PCDATA_TAG_ID 2\r
-#define ATTRIBUTE_DATA_OPEN_TAG "<@$>"\r
-#define ATTRIBUTE_DATA_TAG_ID 3\r
-#define CLOSING_TAG "</>"\r
-#define CLOSING_TAG_ID 4\r
-#define DOCUMENT_CLOSE_TAG "/"\r
-#define ATTRIBUTE_CLOSE_TAG "/<@>"\r
-#define PCDATA_CLOSE_TAG "/<$>"\r
-#define ATTRIBUTE_DATA_CLOSE_TAG "/<@$>"\r
-\r
-\r
-typedef std::unordered_set<int> TagIdSet;\r
-typedef std::unordered_map<std::string,int> TagIdMap;\r
-typedef TagIdMap::const_iterator TagIdMapIT;\r
-\r
-#define REGISTER_TAG(v,h,t) do { (h)->insert(std::make_pair((t),(v)->size()));\\r
- (v)->push_back(t); } while (false)\r
-\r
-// returns NULLT if the test is true\r
-#define NULLT_IF(x) do { if (x) return NULLT; } while (0)\r
-\r
-// Direct calls to sarray library\r
-\r
-static inline int fast_find_close(bp *b,int s)\r
-{\r
- return fwd_excess(b,s,-1);\r
-}\r
-\r
-static inline int fast_inspect(bp* Par,treeNode i)\r
-{\r
- int j,l;\r
- j = i >> logD;\r
- l = i & (D-1);\r
- return (Par->B[j] >> (D-1-l)) & 1;\r
-}\r
-\r
-static bool fast_isleaf(bp* Par,treeNode x){\r
- return (fast_inspect(Par, x+1) == CP);\r
-}\r
-\r
-static treeNode fast_first_child(bp *Par, treeNode x)\r
-{\r
- x = x+1;\r
- return (fast_inspect(Par,x) == OP) ? x : NULLT;\r
-}\r
-\r
-inline static treeNode fast_next_sibling(bp* Par,treeNode x)\r
-{\r
- treeNode y = fast_find_close(Par,x)+1;\r
- return (fast_inspect(Par, y) == OP) ? y : NULLT;\r
-}\r
-\r
-inline static bool fast_is_ancestor(bp * Par,treeNode x,treeNode y){\r
- return (x <= y) && ((x==0) || (y <= fast_find_close(Par,x)));\r
-}\r
-\r
-// tag position -> tree node\r
-static treeNode tagpos2node(int t) \r
- {\r
- return (treeNode) t;\r
- }\r
-// tree node -> tag position\r
-static int node2tagpos(treeNode x) \r
-{\r
- return (int)x;\r
-}\r
-\r
-\r
-class XMLTreeBuilder;\r
-\r
-class XMLTree {\r
-\r
- // Only the builder can access the constructor\r
- friend class XMLTreeBuilder;\r
-\r
- private:\r
- /** Balanced parentheses representation of the tree */\r
- bp *Par;\r
- \r
- /** Mapping from tag identifer to tag name */ \r
- std::vector<std::string> *TagName;\r
- TagIdMap * tIdMap;\r
- \r
- /** Bit vector indicating with a 1 the positions of the non-empty texts. */\r
- static_bitsequence *EBVector; \r
- \r
- /** Tag sequence represented with a data structure for rank and select */\r
- static_sequence *Tags;\r
- uint * tags_fix;\r
- uint tags_blen, tags_len;\r
-\r
- /** The texts in the XML document */\r
- TextCollection *Text;\r
-\r
- // Allows to disable the TextCollection for benchmarkin purposes\r
- bool disable_tc;\r
- \r
- FILE* stream;\r
- int stream_fd; \r
- std::string * buffer;\r
- void myfputs(const char* s, FILE * fp){\r
- buffer->append(s);\r
- if (buffer->size() >= 100000){\r
- fputs(buffer->c_str(),fp);\r
- buffer->clear();\r
- };\r
-\r
- }\r
- void myfputc(const char c, FILE*fp){\r
- buffer->append(1,c);\r
- if (buffer->size() >= 100000){\r
- fputs(buffer->c_str(),fp);\r
- buffer->clear();\r
- };\r
- }\r
- void mybufferflush(FILE* fp){\r
- fputs(buffer->c_str(), fp);\r
- buffer->clear();\r
- }\r
-\r
- size_t myfprintf(const char* s, FILE * fp){\r
- if (s == NULL)\r
- return 0;\r
- size_t i = buffer->size();\r
- buffer->append(s);\r
- size_t j = buffer->size();\r
- if (buffer->size() >= 100000){\r
- fputs(buffer->c_str(),fp);\r
- buffer->clear();\r
- };\r
- return (j-i);\r
- }\r
-\r
- void PrintNode(treeNode n, int fd);\r
- /** Data structure constructors */\r
- XMLTree(){ buffer = 0;};\r
-\r
- // non const pointer are freed by this method.\r
- XMLTree( pb * const par, uint npar, std::vector<std::string> * const TN, TagIdMap * const tim, uint *empty_texts_bmp, TagType *tags,\r
- TextCollection * const TC, bool dis_tc);\r
-\r
-public: \r
- /** Data structure destructor */\r
- ~XMLTree();\r
- \r
- /** root(): returns the tree root. */\r
- treeNode Root() { return 0; }\r
-\r
- /** Size() : Number of parenthesis */\r
- unsigned int Size(){\r
- return tags_len/2;\r
- }\r
-\r
-\r
- /** NumTags() : Number of distinct tags */\r
- unsigned int NumTags() {\r
- return TagName->size();\r
- }\r
-\r
- int TagsBinaryLength(){ return tags_blen; };\r
- unsigned int TagStructLength(){ return uint_len(tags_blen,tags_len); };\r
- unsigned int * TagStruct() { return tags_fix; };\r
-\r
-\r
- /** SubtreeSize(x): the number of nodes (and attributes) in the subtree of \r
- * node x. */\r
- int SubtreeSize(treeNode x);\r
- \r
- /** SubtreeTags(x,tag): the number of occurrences of tag within the subtree \r
- * of node x. */\r
- int SubtreeTags(treeNode x, TagType tag);\r
- \r
- /** SubtreeElements(x) of element nodes in the subtree of x\r
- */\r
- int SubtreeElements(treeNode x);\r
-\r
- /** IsLeaf(x): returns whether node x is leaf or not. In the succinct \r
- * representation this is just a bit inspection. */\r
-\r
- bool IsLeaf(treeNode x);\r
-\r
- /** IsAncestor(x,y): returns whether node x is ancestor of node y. */\r
-\r
- bool IsAncestor(treeNode x, treeNode y);\r
- \r
- /** IsChild(x,y): returns whether node x is parent of node y. */\r
- bool IsChild(treeNode x, treeNode y);\r
-\r
- /** IsFirstChild(x): returns whether node x is the first child of its parent. */\r
- /* OCAML */\r
- bool IsFirstChild(treeNode x) { \r
- return ((x != NULLT)&&(x==Root() || prev_sibling(Par,x) == (treeNode)-1));\r
- };\r
- \r
- /** NumChildren(x): number of children of node x. Constant time with the \r
- * data structure of Sadakane. */\r
- int NumChildren(treeNode x);\r
-\r
- /** ChildNumber(x): returns i if node x is the i-th children of its \r
- * parent. */\r
- int ChildNumber(treeNode x);\r
-\r
- /** Depth(x): depth of node x, a simple binary rank on the parentheses \r
- * sequence. */\r
- int Depth(treeNode x);\r
- \r
- /** Preorder(x): returns the preorder number of node x, just regarding tree \r
- * nodes (and not texts). */ \r
- int Preorder(treeNode x);\r
- \r
- /** Postorder(x): returns the postorder number of node x, just regarding \r
- * tree nodes (and not texts). */\r
- int Postorder(treeNode x);\r
- \r
-\r
- /** DocIds(x): returns the range (i.e., a pair of integers) of document \r
- * identifiers that descend from node x. */\r
- range DocIds(treeNode x);\r
-\r
- /** Parent(x): returns the parent node of node x. */\r
- treeNode Parent(treeNode x) { \r
- if (x == Root())\r
- return NULLT;\r
- else\r
- return parent(Par, x);\r
- };\r
- /* Assumes x is neither 0 nor -1 */\r
- \r
- /** Child(x,i): returns the i-th child of node x, assuming it exists. */ \r
- treeNode Child(treeNode x, int i);\r
-\r
-\r
-\r
- /** LastChild(x): returns the last child of node x. */\r
- treeNode LastChild(treeNode x);\r
- \r
-\r
-\r
- /** PrevSibling(x): returns the previous sibling of node x, assuming it \r
- * exists. */\r
-\r
- treeNode PrevSibling(treeNode x);\r
- \r
- /** TaggedChild(x,tag): returns the first child of node x tagged tag, or \r
- * NULLT if there is none. Because of the balanced-parentheses representation \r
- * of the tree, this operation is not supported efficiently, just iterating \r
- * among the children of node x until finding the desired child. */\r
-\r
- \r
- treeNode SelectChild(treeNode x, TagIdSet * tags);\r
-\r
- /** TaggedFollowingSibling(x,tag): returns the first sibling of node x tagged tag, or \r
- * NULLT if there is none. */\r
- \r
- treeNode SelectFollowingSibling(treeNode x, TagIdSet * tags);\r
-\r
-\r
-\r
-\r
- treeNode SelectDescendant(treeNode x, TagIdSet * tags);\r
-\r
- /** TaggedPrec(x,tag): returns the first node tagged tag with smaller \r
- * preorder than x and not an ancestor of x. Returns NULLT if there \r
- * is none. */\r
- treeNode TaggedPreceding(treeNode x, TagType tag);\r
- \r
- /** TaggedFoll(x,tag): returns the first node tagged tag with larger \r
- * preorder than x and not in the subtree of x. Returns NULLT if there \r
- * is none. */\r
- treeNode TaggedFollowing(treeNode x, TagType tag);\r
-\r
-\r
-\r
- treeNode SelectFollowingBelow(treeNode x, TagIdSet * tags, treeNode ancestor);\r
-\r
- // treeNode TaggedFollowingBefore(treeNode x, TagType tag,treeNode closing);\r
-\r
- treeNode SelectFollowingBefore(treeNode x, TagIdSet * tags, treeNode closing);\r
-\r
- /** TaggedAncestor(x, tag): returns the closest ancestor of x tagged \r
- * tag. Return NULLT is there is none. */\r
- treeNode TaggedAncestor(treeNode x, TagType tag);\r
- \r
- /** PrevText(x): returns the document identifier of the text to the left of \r
- * node x, or NULLT if x is the root node. */\r
- DocID PrevText(treeNode x);\r
- \r
- /** NextText(x): returns the document identifier of the text to the right of \r
- * node x, or NULLT if x is the root node. */\r
- DocID NextText(treeNode x);\r
- \r
- /** MyText(x): returns the document identifier of the text below node x, or \r
- * NULLT if x is not a leaf node. */\r
- DocID MyText(treeNode x);\r
- DocID MyTextUnsafe(treeNode x);\r
-\r
- /** TextXMLId(d): returns the preorder of document with identifier d in the \r
- * tree consisting of all tree nodes and all text nodes. */\r
- int TextXMLId(DocID d);\r
- \r
- /** NodeXMLId(x): returns the preorder of node x in the tree consisting of \r
- * all tree nodes and all text nodes. */\r
- int NodeXMLId(treeNode x);\r
- \r
- /** ParentNode(d): returns the parent node of document identifier d. */\r
- treeNode ParentNode(DocID d);\r
- \r
- treeNode PrevNode(DocID d);\r
-\r
- /** GetTagId(tagname): returns the tag identifier corresponding to a given \r
- * tag name. Returns NULLT in case that the tag name does not exists. */\r
- TagType GetTagId(unsigned char *tagname);\r
-\r
- /** GetTagName(tagid): returns the tag name of a given tag identifier. \r
- * Returns NULL in case that the tag identifier is not valid.*/\r
- unsigned char *GetTagName(TagType tagid);\r
-\r
- /** GetTagName(tagid): returns the tag name of a given tag identifier. \r
- * The result is just a reference and should not be freed by the caller.\r
- */\r
- const unsigned char *GetTagNameByRef(TagType tagid);\r
-\r
- /** RegisterTag adds a new tag to the tag collection this is needed\r
- * if the query contains a tag which is not in the document, we need\r
- * to give this new tag a fresh id and store it somewhere. A logical\r
- * choice is here.\r
- * We might want to use a hashtable instead of an array though.\r
- */\r
- TagType RegisterTag(unsigned char *tagname);\r
-\r
- bool EmptyText(DocID i) {\r
- return Text->EmptyText(i);\r
- }\r
-\r
- /** Prefix(s): search for texts prefixed by string s. */\r
- TextCollection::document_result Prefix(uchar const *s) {\r
- return Text->Prefix(s);\r
- }\r
-\r
- /** Suffix(s): search for texts having string s as a suffix. */\r
- TextCollection::document_result Suffix(uchar const *s) {\r
- return Text->Suffix(s);\r
- }\r
-\r
- /** Equal(s): search for texts equal to string s. */\r
- TextCollection::document_result Equals(uchar const *s) {\r
- return Text->Equal(s);\r
- }\r
-\r
- /** Contains(s): search for texts containing string s. */\r
- TextCollection::document_result Contains(uchar const *s) {\r
- return Text->Contains(s);\r
- }\r
-\r
- /** LessThan(s): returns document identifiers for the texts that\r
- * are lexicographically smaller than string s. */\r
- TextCollection::document_result LessThan(uchar const *s) {\r
- return Text->LessThan(s);\r
- }\r
- \r
- /** IsPrefix(x): returns true if there is a text prefixed by string s. */\r
- bool IsPrefix(uchar const *s) {\r
- return Text->IsPrefix(s);\r
- } \r
- \r
- /** IsSuffix(s): returns true if there is a text having string s as a \r
- * suffix.*/\r
- bool IsSuffix(uchar const *s) {\r
- return Text->IsSuffix(s);\r
- }\r
- \r
- /** IsEqual(s): returns true if there is a text that equals given \r
- * string s. */\r
- bool IsEqual(uchar const *s) {\r
- return Text->IsEqual(s);\r
- }\r
- \r
- /** IsContains(s): returns true if there is a text containing string s. */\r
- bool IsContains(uchar const *s) {\r
- return Text->IsContains(s);\r
- }\r
- \r
- /** IsLessThan(s): returns true if there is at least a text that is \r
- * lexicographically smaller than string s. */\r
- bool IsLessThan(uchar const *s) {\r
- return Text->IsLessThan(s);\r
- }\r
- \r
- /** Count(s): Global counting */\r
- unsigned Count(uchar const *s) {\r
- return Text->Count(s);\r
- }\r
-\r
- /** CountPrefix(s): counting version of Prefix(s). */\r
- unsigned CountPrefix(uchar const *s) {\r
- return Text->CountPrefix(s);\r
- }\r
- \r
- /** CountSuffix(s): counting version of Suffix(s). */\r
- unsigned CountSuffix(uchar const *s) {\r
- return Text->CountSuffix(s);\r
- }\r
- \r
- /** CountEqual(s): counting version of Equal(s). */\r
- unsigned CountEqual(uchar const *s) {\r
- return Text->CountEqual(s);\r
- }\r
- \r
- /** CountContains(s): counting version of Contains(s). */\r
- unsigned CountContains(uchar const *s) {\r
- return Text->CountContains(s);\r
- }\r
- \r
- /** CountLessThan(s): counting version of LessThan(s). */\r
- unsigned CountLessThan(uchar const *s) {\r
- return Text->CountLessThan(s);\r
- }\r
- \r
- /** GetText(d): returns the text corresponding to document with\r
- * id d. */\r
- uchar* GetText(DocID d) {\r
- \r
- uchar * s = Text->GetText(d);\r
- return (s[0] == 1 ? (s+1) : s);\r
- }\r
-\r
- /** GetText(i, j): returns the texts corresponding to documents with\r
- * ids i, i+1, ..., j. Texts are separated by '\0' character. */\r
- // uchar* GetText(DocID i, DocID j) {\r
- // uchar * s = Text->GetText(i, j);\r
- // return (s[0] == 1 ? (uchar*)"" : s);\r
- //}\r
-\r
- TextCollection *getTextCollection() {\r
- return Text;\r
- }\r
- \r
- /** Save: saves XML tree data structure to file. */\r
- void Save(int fd, char *filename);\r
- \r
- /** Load: loads XML tree data structure from file. sample_rate_text \r
- * indicates the sample rate for the text search data structure. */\r
- static XMLTree *Load(int fd, char *filename, bool load_tc, int sample_factor); \r
-\r
- void insertTag(TagType tag, uint position);\r
- \r
- void print_stats();\r
-\r
- \r
- /** Parenthesis functions */\r
- treeNode Closing(treeNode x);\r
-\r
- bool IsOpen(treeNode x);\r
-\r
-\r
- /** Print procedure */\r
- void Print(int fd,treeNode x, bool no_text);\r
- void Print(int fd,treeNode x) { Print(fd,x,false); }\r
-\r
- // The following are inlined here for speed\r
- /** Tag(x): returns the tag identifier of node x. */\r
-\r
- inline TagType Tag(treeNode x) const throw () {\r
- if (tags_blen == 8)\r
- return (TagType) (((uchar*)tags_fix)[(int) x]);\r
- else \r
- return get_field(tags_fix, tags_blen, x);\r
- /*\r
- { \r
- size_t idxlen = x * tags_blen;\r
- size_t j = idxlen % W;\r
- size_t i = idxlen / W; \r
- size_t offset = W - tags_blen;\r
- size_t offset2 = offset - j;\r
- size_t w = tags_fix[i];\r
- return (offset2 >= 0)\r
- ? ( w << offset2 ) >> offset\r
- : ( w >> j) | (tags_fix[i+1] << (W+offset2)) >> offset;\r
- }; */\r
-\r
- }\r
-\r
- /** FirstChild(x): returns the first child of node x, or NULLT if the node is a leaf\r
- */\r
- treeNode FirstChild(treeNode x) {\r
- NULLT_IF(x==NULLT);\r
- return fast_first_child(Par, x);\r
- };\r
-\r
-\r
- /** FirstElement(x): returns the first non text, non attribute child of node x, or NULLT\r
- * if none.\r
- */\r
- treeNode FirstElement(treeNode x){\r
- {\r
- NULLT_IF(x==NULLT);\r
- x = fast_first_child(Par, x);\r
- NULLT_IF(x == NULLT);\r
- switch (Tag(x)){\r
- \r
- case PCDATA_TAG_ID:\r
- x = x+2;\r
- return (fast_inspect(Par,x)==OP)? x : NULLT;\r
- \r
- case ATTRIBUTE_TAG_ID: \r
- x = fast_next_sibling(Par,x);\r
- if (x != NULLT && Tag(x) == PCDATA_TAG_ID){\r
- x = x+2;\r
- return (fast_inspect(Par,x)==OP)? x : NULLT;\r
- } \r
- else return x; \r
- default:\r
- return x;\r
- }\r
- }\r
- };\r
-\r
- /** NextSibling(x): returns the next sibling of node x, or NULLT if none \r
- * exists. */\r
- \r
- treeNode NextSibling(treeNode x) {\r
- NULLT_IF (x <= 0);\r
- return fast_next_sibling(Par, x);\r
- };\r
- \r
- /** NextElement(x): returns the first non text, non attribute sibling of node x, or NULLT\r
- * if none.\r
- */\r
- treeNode NextElement(treeNode x)\r
- {\r
- NULLT_IF(x <= 0);\r
- x = fast_next_sibling(Par, x);\r
- NULLT_IF(x == NULLT); \r
- if (Tag(x) == PCDATA_TAG_ID){\r
- x = x+2;\r
- return (fast_inspect(Par,x)==OP)? x : NULLT;\r
- }\r
- else return x; \r
- };\r
- /** TaggedDesc(x,tag): returns the first node tagged tag with larger \r
- * preorder than x and within the subtree of x. Returns NULT if there \r
- * is none. */\r
- inline treeNode TaggedDescendant(treeNode x, TagType tag)\r
- {\r
- \r
- int s = (int) Tags->select_next(tag,node2tagpos(x));\r
- NULLT_IF (s == -1);\r
- \r
- treeNode y = tagpos2node(s); // transforms the tag position into a node position\r
- \r
- return (fast_is_ancestor(Par,x,y) ? y : NULLT);\r
- };\r
- \r
- inline treeNode TaggedFollowingBelow(treeNode x, TagType tag, treeNode ancestor)\r
- {\r
- treeNode close = fast_find_close(Par, x);\r
- treeNode s = tagpos2node(Tags->select_next(tag, close));\r
- \r
- if (ancestor == Root() || s == NULLT || s < fast_find_close(Par,ancestor)) return s;\r
- else return NULLT;\r
- };\r
-\r
- inline treeNode TaggedFollowingBefore(treeNode x, TagType tag, treeNode ancestor_closing)\r
- {\r
- treeNode close = fast_find_close(Par, x);\r
- treeNode s = tagpos2node(Tags->select_next(tag, close));\r
- \r
- if (ancestor_closing == Root() || s == NULLT || s < ancestor_closing) return s;\r
- else return NULLT;\r
- };\r
- \r
-// TaggedSibling(x,tag): returns the first sibling of node x tagged tag, or NULLT if there is none.\r
-treeNode TaggedFollowingSibling(treeNode x, TagType tag)\r
-{\r
- NULLT_IF(x==NULLT);\r
- treeNode sibling = x;\r
- TagType ctag;\r
- while ((sibling = fast_next_sibling(Par, sibling)) != NULLT) {\r
- ctag = Tag(sibling);\r
- if (ctag == tag) return sibling; \r
- }\r
- return NULLT; \r
-};\r
-\r
-treeNode TaggedChild(treeNode x, TagType tag) \r
-{\r
- \r
- NULLT_IF(x==NULLT || fast_isleaf(Par,x));\r
- treeNode child; \r
- child = fast_first_child(Par, x);\r
-\r
- if (Tag(child) == tag)\r
- return child;\r
- else\r
- return TaggedFollowingSibling(child, tag);\r
-};\r
-\r
-\r
-};\r
-\r
-\r
-#endif\r
-\r
+/******************************************************************************
+ * Copyright (C) 2008 by Diego Arroyuelo *
+ * Interface for the in-memory XQuery/XPath engine *
+ * *
+ * This program is free software; you can redistribute it and/or modify *
+ * it under the terms of the GNU Lesser General Public License as published *
+ * by the Free Software Foundation; either version 2 of the License, or *
+ * (at your option) any later version. *
+ * *
+ * This program is distributed in the hope that it will be useful, *
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of *
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the *
+ * GNU Lesser General Public License for more details. *
+ * *
+ * You should have received a copy of the GNU Lesser General Public License *
+ * along with this program; if not, write to the *
+ * Free Software Foundation, Inc., *
+ * 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. *
+ ******************************************************************************/
+
+#ifndef XMLTREE_H_
+#define XMLTREE_H_
+
+
+#include <unordered_set>
+#include <unordered_map>
+#include <sstream>
+#include "TextCollection/TextCollectionBuilder.h"
+
+#undef W
+#undef WW
+#undef Wminusone
+
+#include "bp.h"
+#include <libcds/includes/basics.h>
+#include <static_bitsequence.h>
+#include <alphabet_mapper.h>
+#include <static_sequence.h>
+using SXSI::TextCollection;
+using SXSI::TextCollectionBuilder;
+
+
+// this constant is used to efficiently compute the child operation in the tree
+#define OPTD 10
+
+#define NULLT -1
+
+#define PERM_SAMPLE 10
+
+
+typedef int treeNode;
+typedef int TagType;
+typedef int DocID;
+
+typedef struct {
+ int min;
+ int max;
+} range;
+
+// Encoding of the XML Document :
+// The following TAGs and IDs are fixed, "" is the tag of the root.
+// a TextNode is represented by a leaf <<$>></<$>> The DocId in the TextCollection
+// of that leaf is kept in a bit sequence.
+// a TextNode below an attribute is likewise represented by a leaf <<@$>><</@$>>
+// An element <e a1="v1" a2="v2" ... an="vn" > ...</e> the representation is:
+// <e><<@>> <<@>a1> <<$@>>DocID(v1)</<$@>></<@>a1> ... </<@>> .... </e>
+// Hence the attributes (if any) are always below the first child of their element,
+// as the children of a fake node <@>.
+
+
+#define DOCUMENT_OPEN_TAG ""
+#define DOCUMENT_TAG_ID 0
+#define ATTRIBUTE_OPEN_TAG "<@>"
+#define ATTRIBUTE_TAG_ID 1
+#define PCDATA_OPEN_TAG "<$>"
+#define PCDATA_TAG_ID 2
+#define ATTRIBUTE_DATA_OPEN_TAG "<@$>"
+#define ATTRIBUTE_DATA_TAG_ID 3
+#define CLOSING_TAG "</>"
+#define CLOSING_TAG_ID 4
+#define DOCUMENT_CLOSE_TAG "/"
+#define ATTRIBUTE_CLOSE_TAG "/<@>"
+#define PCDATA_CLOSE_TAG "/<$>"
+#define ATTRIBUTE_DATA_CLOSE_TAG "/<@$>"
+
+
+typedef std::unordered_set<int> TagIdSet;
+typedef std::unordered_map<std::string,int> TagIdMap;
+typedef TagIdMap::const_iterator TagIdMapIT;
+
+#define REGISTER_TAG(v,h,t) do { (h)->insert(std::make_pair((t),(v)->size()));\
+ (v)->push_back(t); } while (false)
+
+// returns NULLT if the test is true
+#define NULLT_IF(x) do { if (x) return NULLT; } while (0)
+
+// Direct calls to sarray library
+
+static inline int fast_find_close(bp *b,int s)
+{
+ return fwd_excess(b,s,-1);
+}
+
+static inline int fast_inspect(bp* Par,treeNode i)
+{
+ int j,l;
+ j = i >> logD;
+ l = i & (D-1);
+ return (Par->B[j] >> (D-1-l)) & 1;
+}
+
+static bool fast_isleaf(bp* Par,treeNode x){
+ return (fast_inspect(Par, x+1) == CP);
+}
+
+static treeNode fast_first_child(bp *Par, treeNode x)
+{
+ x = x+1;
+ return (fast_inspect(Par,x) == OP) ? x : NULLT;
+}
+
+inline static treeNode fast_next_sibling(bp* Par,treeNode x)
+{
+ treeNode y = fast_find_close(Par,x)+1;
+ return (fast_inspect(Par, y) == OP) ? y : NULLT;
+}
+
+inline static bool fast_is_ancestor(bp * Par,treeNode x,treeNode y){
+ return (x <= y) && ((x==0) || (y <= fast_find_close(Par,x)));
+}
+
+// tag position -> tree node
+static treeNode tagpos2node(int t)
+ {
+ return (treeNode) t;
+ }
+// tree node -> tag position
+static int node2tagpos(treeNode x)
+{
+ return (int)x;
+}
+
+
+class XMLTreeBuilder;
+
+class XMLTree {
+
+ // Only the builder can access the constructor
+ friend class XMLTreeBuilder;
+
+ private:
+ /** Balanced parentheses representation of the tree */
+ bp *Par;
+
+ /** Mapping from tag identifer to tag name */
+ std::vector<std::string> *TagName;
+ TagIdMap * tIdMap;
+
+ /** Bit vector indicating with a 1 the positions of the non-empty texts. */
+ static_bitsequence *EBVector;
+
+ /** Tag sequence represented with a data structure for rank and select */
+ static_sequence *Tags;
+ uint * tags_fix;
+ uint tags_blen, tags_len;
+
+ /** The texts in the XML document */
+ TextCollection *Text;
+
+ // Allows to disable the TextCollection for benchmarkin purposes
+ bool disable_tc;
+
+ FILE* stream;
+ int stream_fd;
+ std::string * buffer;
+
+ void _flush(int fd){
+ size_t size = buffer->size();
+ size_t written = write(fd, buffer->data(), size);
+ if (written != size)
+ throw "Cannot flush buffer";
+ buffer->clear();
+ }
+
+ void _dputs(const char* s, int fd){
+ buffer->append(s);
+ if (buffer->size() >= 131072) _flush(fd);
+
+ }
+
+ void _dputc(const char c, int fd){
+ buffer->append(1,c);
+ if (buffer->size() >= 131072) _flush(fd);
+ }
+
+ size_t _dprintf(const char* s, int fd){
+ if (s == NULL) return 0;
+ size_t i = 0;
+ while (1) {
+ switch (s[i]) {
+ case '&':
+ buffer->append("&");
+ break;
+ case '\'':
+ buffer->append("'");
+ break;
+ case '"':
+ buffer->append(""");
+ break;
+ case '<':
+ buffer->append("<");
+ break;
+ case '>':
+ buffer->append(">");
+ break;
+ case 0:
+ return i;
+ default:
+ buffer->append(1, s[i]);
+
+ };
+ if (buffer->size() >= 131072) _flush(fd);
+ ++i;
+ };
+ }
+
+ void PrintNode(treeNode n, int fd);
+ /** Data structure constructors */
+ XMLTree(){ buffer = 0;};
+
+ // non const pointer are freed by this method.
+ XMLTree( pb * const par, uint npar, std::vector<std::string> * const TN, TagIdMap * const tim, uint *empty_texts_bmp, TagType *tags,
+ TextCollection * const TC, bool dis_tc);
+
+public:
+ /** Data structure destructor */
+ ~XMLTree();
+
+ /** root(): returns the tree root. */
+ treeNode Root() { return 0; }
+
+ /** Size() : Number of parenthesis */
+ unsigned int Size(){
+ return tags_len/2;
+ }
+
+
+ /** NumTags() : Number of distinct tags */
+ unsigned int NumTags() {
+ return TagName->size();
+ }
+
+ int TagsBinaryLength(){ return tags_blen; };
+ unsigned int TagStructLength(){ return uint_len(tags_blen,tags_len); };
+ unsigned int * TagStruct() { return tags_fix; };
+
+
+ /** 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
+ * 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++)
+ count += (Tag(i) == tag);
+ return count;
+ }
+ 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
+ * representation this is just a bit inspection. */
+
+ bool IsLeaf(treeNode x);
+
+ /** IsAncestor(x,y): returns whether node x is ancestor of node y. */
+
+ bool IsAncestor(treeNode x, treeNode y);
+
+ /** 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) {
+ 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 NumChildren(treeNode x);
+
+ /** 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
+ * sequence. */
+ int Depth(treeNode x);
+
+ /** 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
+ * tree nodes (and not texts). */
+ int Postorder(treeNode x);
+
+
+ /** 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) {
+ if (x == Root())
+ return NULLT;
+ else
+ return parent(Par, x);
+ };
+ /* Assumes x is neither 0 nor -1 */
+
+ /** Child(x,i): returns the i-th child of node x, assuming it exists. */
+ treeNode Child(treeNode x, int i);
+
+
+
+ /** LastChild(x): returns the last child of node x. */
+ treeNode LastChild(treeNode x);
+
+
+
+ /** PrevSibling(x): returns the previous sibling of node x, assuming it
+ * exists. */
+
+ treeNode PrevSibling(treeNode 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
+ * 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
+ * NULLT if there is none. */
+
+ treeNode SelectFollowingSibling(treeNode x, TagIdSet * tags);
+
+
+
+
+ treeNode SelectDescendant(treeNode x, TagIdSet * tags) {
+ NULLT_IF (x == NULLT);
+ treeNode fc = x+1;
+ if (fast_inspect(Par, fc) == CP) return NULLT;
+ treeNode min = NULLT;
+ treeNode aux;
+
+ TagIdSet::const_iterator tagit;
+ for (tagit = tags->begin(); tagit != tags->end(); ++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
+ * 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
+ * is none. */
+ treeNode TaggedFollowing(treeNode x, TagType tag);
+
+
+
+ treeNode SelectFollowingBelow(treeNode x, TagIdSet * tags, treeNode ancestor);
+
+ // treeNode TaggedFollowingBefore(treeNode x, TagType tag,treeNode closing);
+
+ treeNode SelectFollowingBefore(treeNode x, TagIdSet * tags, treeNode ancestor_closing)
+ {
+
+ NULLT_IF(x <= 0);
+
+ 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));
+
+ 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
+ * 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
+ * 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
+ * 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
+ * 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
+ * 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
+ * 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
+ * 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.
+ * 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.
+ * The result is just a reference and should not be freed by the caller.
+ */
+ const unsigned char *GetTagNameByRef(TagType tagid);
+
+ /** 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) {
+ return Text->EmptyText(i);
+ }
+
+ /** Prefix(s): search for texts prefixed by string s. */
+ TextCollection::document_result Prefix(uchar const *s) {
+ return Text->Prefix(s);
+ }
+
+ /** Suffix(s): search for texts having string s as a suffix. */
+ TextCollection::document_result Suffix(uchar const *s) {
+ return Text->Suffix(s);
+ }
+
+ /** Equal(s): search for texts equal to string s. */
+ TextCollection::document_result Equals(uchar const *s) {
+ return Text->Equal(s);
+ }
+
+ /** Contains(s): search for texts containing string s. */
+ TextCollection::document_result Contains(uchar const *s) {
+ return Text->Contains(s);
+ }
+
+ /** LessThan(s): returns document identifiers for the texts that
+ * are lexicographically smaller than string s. */
+ 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
+ * suffix.*/
+ bool IsSuffix(uchar const *s) {
+ return Text->IsSuffix(s);
+ }
+
+ /** 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
+ * 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);
+ }
+
+ /** CountPrefix(s): counting version of Prefix(s). */
+ 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);
+ }
+
+ /** GetText(i, j): returns the texts corresponding to documents with
+ * ids i, i+1, ..., j. Texts are separated by '\0' character. */
+ // uchar* GetText(DocID i, DocID j) {
+ // uchar * s = Text->GetText(i, j);
+ // return (s[0] == 1 ? (uchar*)"" : s);
+ //}
+
+ TextCollection *getTextCollection() {
+ return Text;
+ }
+
+ /** Save: saves XML tree data structure to file. */
+ void Save(int fd, char *filename);
+
+ /** 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, char *filename, bool load_tc, int sample_factor);
+
+ void insertTag(TagType tag, uint position);
+
+ void print_stats();
+
+
+ /** Parenthesis functions */
+ treeNode Closing(treeNode x);
+
+ bool IsOpen(treeNode x);
+
+
+ /** Print procedure */
+ void Print(int fd,treeNode x, bool no_text);
+ void Print(int fd,treeNode x) { Print(fd,x,false); }
+
+ // The following are inlined here for speed
+ /** Tag(x): returns the tag identifier of node x. */
+
+ inline TagType Tag(treeNode x) const throw () {
+ if (tags_blen == 8)
+ return (TagType) (((uchar*)tags_fix)[(int) x]);
+ 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 offset = W - tags_blen;
+ size_t offset2 = offset - j;
+ size_t w = tags_fix[i];
+ return (offset2 >= 0)
+ ? ( w << offset2 ) >> offset
+ : ( w >> j) | (tags_fix[i+1] << (W+offset2)) >> offset;
+ }; */
+
+ }
+
+ /** FirstChild(x): returns the first child of node x, or NULLT if the node is a leaf
+ */
+ treeNode FirstChild(treeNode x) {
+ NULLT_IF(x==NULLT);
+ return fast_first_child(Par, x);
+ };
+
+
+ /** FirstElement(x): returns the first non text, non attribute child of node x, or NULLT
+ * if none.
+ */
+ treeNode FirstElement(treeNode node){
+ {
+ NULLT_IF(node == NULLT);
+ treeNode x = fast_first_child(Par, node);
+ NULLT_IF(x == NULLT);
+ switch (Tag(x)){
+
+ 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
+ * 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.
+ */
+ treeNode NextElement(treeNode x)
+ {
+ NULLT_IF(x <= 0);
+ x = fast_next_sibling(Par, x);
+ 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;
+ };
+ /** 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;
+ };
+
+ inline treeNode TaggedFollowingBefore(treeNode x, TagType tag, treeNode ancestor_closing)
+ {
+ 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)
+{
+ NULLT_IF(x==NULLT);
+ treeNode sibling = x;
+ TagType ctag;
+ while ((sibling = fast_next_sibling(Par, sibling)) != NULLT) {
+ ctag = Tag(sibling);
+ if (ctag == tag) return sibling;
+ }
+ return NULLT;
+};
+
+treeNode TaggedChild(treeNode x, TagType tag)
+{
+
+ NULLT_IF(x==NULLT || fast_isleaf(Par,x));
+ treeNode child;
+ child = fast_first_child(Par, x);
+
+if (Tag(child) == tag)
+ return child;
+ else
+ return TaggedFollowingSibling(child, tag);
+};
+
+
+};
+
+
+#endif
+
projects / SXSI / XMLTree.git / commitdiff