XMLTree.h

   1 \r
   2 /******************************************************************************\r
   3  *   Copyright (C) 2008 by Diego Arroyuelo                                    *\r
   4  *   Interface for the in-memory XQuery/XPath engine                          *\r
   5  *                                                                            *\r
   6  *   This program is free software; you can redistribute it and/or modify     *\r
   7  *   it under the terms of the GNU Lesser General Public License as published *\r
   8  *   by the Free Software Foundation; either version 2 of the License, or     *\r
   9  *   (at your option) any later version.                                      *\r
  10  *                                                                            *\r
  11  *   This program is distributed in the hope that it will be useful,          *\r
  12  *   but WITHOUT ANY WARRANTY; without even the implied warranty of           *\r
  13  *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the            *\r
  14  *   GNU Lesser General Public License for more details.                      *\r
  15  *                                                                            *\r
  16  *   You should have received a copy of the GNU Lesser General Public License *\r
  17  *   along with this program; if not, write to the                            *\r
  18  *   Free Software Foundation, Inc.,                                          *\r
  19  *   59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.                *\r
  20  ******************************************************************************/\r
  21 \r
  22 #ifndef XMLTREE_H_\r
  23 #define XMLTREE_H_\r
  24 #include <unordered_set>\r
  25 #include <unordered_map>\r
  26 #include "TextCollection/TextCollectionBuilder.h"\r
  27 #include <stdio.h>\r
  28 #include <stdlib.h>\r
  29 #include <cstring>\r
  30 \r
  31 \r
  32 #undef W\r
  33 #undef WW\r
  34 #undef Wminusone\r
  35 \r
  36 #include "bp.h"\r
  37 \r
  38 #include <static_bitsequence.h>\r
  39 #include <alphabet_mapper.h>\r
  40 #include <static_sequence.h>\r
  41 using SXSI::TextCollection;\r
  42 using SXSI::TextCollectionBuilder;\r
  43 \r
  44 \r
  45 // this constant is used to efficiently compute the child operation in the tree\r
  46 #define OPTD 10\r
  47 \r
  48 #define NULLT -1\r
  49 \r
  50 #define PERM_SAMPLE 10\r
  51 \r
  52 \r
  53 typedef int treeNode;\r
  54 typedef int TagType; \r
  55 typedef int DocID;  \r
  56 \r
  57 typedef struct {\r
  58    int min;\r
  59    int max;\r
  60 } range;\r
  61 \r
  62 // Encoding of the XML Document :\r
  63 // The following TAGs and IDs are fixed, "" is the tag of the root.\r
  64 // a TextNode is represented by a leaf <<$>></<$>> The DocId in the TextCollection\r
  65 // of that leaf is kept in a bit sequence.\r
  66 // a TextNode below an attribute is likewise represented by a leaf <<@$>><</@$>>\r
  67 // An element <e a1="v1" a2="v2" ... an="vn" > ...</e> the representation is:\r
  68 // <e><<@>> <<@>a1> <<$@>>DocID(v1)</<$@>></<@>a1> ... </<@>> .... </e>\r
  69 // Hence the attributes (if any) are always below the first child of their element,\r
  70 // as the children of a fake node <@>.\r
  71 \r
  72 \r
  73 #define DOCUMENT_OPEN_TAG ""\r
  74 #define DOCUMENT_TAG_ID 0\r
  75 #define ATTRIBUTE_OPEN_TAG "<@>"\r
  76 #define ATTRIBUTE_TAG_ID 1\r
  77 #define PCDATA_OPEN_TAG "<$>"\r
  78 #define PCDATA_TAG_ID 2\r
  79 #define ATTRIBUTE_DATA_OPEN_TAG "<@$>"\r
  80 #define ATTRIBUTE_DATA_TAG_ID 3\r
  81 #define DOCUMENT_CLOSE_TAG "/"\r
  82 #define ATTRIBUTE_CLOSE_TAG "/<@>"\r
  83 #define PCDATA_CLOSE_TAG "/<$>"\r
  84 #define ATTRIBUTE_DATA_CLOSE_TAG "/<@$>"\r
  85 \r
  86 \r
  87 \r
  88 typedef std::unordered_map<string,int> TagIdMap;\r
  89 typedef TagIdMap::const_iterator TagIdMapIT;\r
  90 \r
  91 #define REGISTER_TAG(v,h,t) do { (h)->insert(std::make_pair((t),(v)->size()));\\r
  92     (v)->push_back(t); } while (false)\r
  93 \r
  94 \r
  95 class XMLTreeBuilder;\r
  96 \r
  97 class XMLTree {\r
  98 \r
  99   // Only the builder can access the constructor\r
 100   friend class XMLTreeBuilder;\r
 101 \r
 102  private:\r
 103    /** Balanced parentheses representation of the tree */\r
 104    bp *Par;\r
 105  \r
 106    /** Mapping from tag identifer to tag name */  \r
 107    vector<string> *TagName;\r
 108    TagIdMap * tIdMap;\r
 109   \r
 110    /** Bit vector indicating with a 1 the positions of the non-empty texts. */\r
 111    static_bitsequence *EBVector;  \r
 112                       \r
 113    /** Tag sequence represented with a data structure for rank and select */\r
 114    static_sequence *Tags;\r
 115    uint * tags_fix;\r
 116    uint tags_blen, tags_len;\r
 117 \r
 118    /** The texts in the XML document */\r
 119    TextCollection *Text;\r
 120 \r
 121    // Allows to disable the TextCollection for benchmarkin purposes\r
 122    bool disable_tc;\r
 123    \r
 124 \r
 125    /** Data structure constructors */\r
 126    XMLTree(){;};\r
 127 \r
 128    // non const pointer are freed by this method.\r
 129   XMLTree( pb * const par, uint npar,  vector<string> * const TN,  TagIdMap * const tim, uint *empty_texts_bmp, TagType *tags,\r
 130            TextCollection * const TC, bool dis_tc);\r
 131 \r
 132 public: \r
 133    /** Data structure destructor */\r
 134    ~XMLTree();\r
 135    \r
 136    /** root(): returns the tree root. */\r
 137    treeNode Root();\r
 138    \r
 139    /** SubtreeSize(x): the number of nodes (and attributes) in the subtree of \r
 140     * node x. */\r
 141    int SubtreeSize(treeNode x);\r
 142    \r
 143    /** SubtreeTags(x,tag): the number of occurrences of tag within the subtree \r
 144     * of node x. */\r
 145    int SubtreeTags(treeNode x, TagType tag);\r
 146    \r
 147    /** IsLeaf(x): returns whether node x is leaf or not. In the succinct \r
 148     * representation this is just a bit inspection. */\r
 149    bool IsLeaf(treeNode x);\r
 150     \r
 151    /** IsAncestor(x,y): returns whether node x is ancestor of node y. */\r
 152    bool IsAncestor(treeNode x, treeNode y);\r
 153   \r
 154    /** IsChild(x,y): returns whether node x is parent of node y. */\r
 155    bool IsChild(treeNode x, treeNode y);\r
 156 \r
 157    /** IsFirstChild(x): returns whether node x is the first child of its parent. */\r
 158    bool IsFirstChild(treeNode x);\r
 159 \r
 160    /** NumChildren(x): number of children of node x. Constant time with the \r
 161     * data structure of Sadakane. */\r
 162    int NumChildren(treeNode x);\r
 163    \r
 164    /** ChildNumber(x): returns i if node x is the i-th children of its \r
 165     * parent. */\r
 166    inline int ChildNumber(treeNode x);\r
 167 \r
 168    /** Depth(x): depth of node x, a simple binary rank on the parentheses \r
 169     * sequence. */\r
 170    int Depth(treeNode x);\r
 171    \r
 172    /** Preorder(x): returns the preorder number of node x, just regarding tree \r
 173     * nodes (and not texts). */ \r
 174    int Preorder(treeNode x);\r
 175    \r
 176    /** Postorder(x): returns the postorder number of node x, just regarding \r
 177     * tree nodes (and not texts). */\r
 178    int Postorder(treeNode x);\r
 179    \r
 180    /** Tag(x): returns the tag identifier of node x. */\r
 181    TagType Tag(treeNode x);\r
 182    \r
 183    /** DocIds(x): returns the range (i.e., a pair of integers) of document \r
 184     * identifiers that descend from node x. */\r
 185    range DocIds(treeNode x);\r
 186    \r
 187    /** Parent(x): returns the parent node of node x. */\r
 188    treeNode Parent(treeNode x);\r
 189    \r
 190    /** Child(x,i): returns the i-th child of node x, assuming it exists. */   \r
 191    treeNode Child(treeNode x, int i);\r
 192    \r
 193    /** FirstChild(x): returns the first child of node x, assuming it exists. \r
 194     * Very fast in BP. */\r
 195    treeNode FirstChild(treeNode x);\r
 196    treeNode FirstElement(treeNode x);\r
 197 \r
 198    /** LastChild(x): returns the last child of node x.  */\r
 199    treeNode LastChild(treeNode x);\r
 200    \r
 201    /** NextSibling(x): returns the next sibling of node x, assuming it \r
 202     * exists. */\r
 203    treeNode NextSibling(treeNode x);\r
 204    treeNode NextElement(treeNode x);\r
 205    \r
 206    /** PrevSibling(x): returns the previous sibling of node x, assuming it \r
 207     * exists. */\r
 208    treeNode PrevSibling(treeNode x);\r
 209    \r
 210    /** TaggedChild(x,tag): returns the first child of node x tagged tag, or \r
 211     * NULLT if there is none. Because of the balanced-parentheses representation \r
 212     * of the tree, this operation is not supported efficiently, just iterating \r
 213     * among the children of node x until finding the desired child. */\r
 214    treeNode TaggedChild(treeNode x, TagType tag);\r
 215    \r
 216    treeNode SelectChild(treeNode x, std::unordered_set<int> * tags);\r
 217 \r
 218    /** TaggedFollSibling(x,tag): returns the first sibling of node x tagged tag, or \r
 219     *  NULLT if there is none. */\r
 220    treeNode TaggedFollSibling(treeNode x, TagType tag);\r
 221    \r
 222    treeNode SelectFollSibling(treeNode x, std::unordered_set<int> * tags);\r
 223 \r
 224    /** TaggedDesc(x,tag): returns the first node tagged tag with larger \r
 225     * preorder than x and within the subtree of x. Returns NULT if there \r
 226     * is none. */\r
 227    treeNode TaggedDesc(treeNode x, TagType tag);\r
 228 \r
 229    treeNode SelectDesc(treeNode x, std::unordered_set<int> * tags);\r
 230 \r
 231 \r
 232    /** TaggedPrec(x,tag): returns the first node tagged tag with smaller \r
 233     * preorder than x and not an ancestor of x. Returns NULLT if there \r
 234     * is none. */\r
 235    treeNode TaggedPrec(treeNode x, TagType tag);\r
 236   \r
 237    /** TaggedFoll(x,tag): returns the first node tagged tag with larger \r
 238     * preorder than x and not in the subtree of x. Returns NULLT if there \r
 239     * is none. */\r
 240    treeNode TaggedFoll(treeNode x, TagType tag);\r
 241 \r
 242    treeNode TaggedFollBelow(treeNode x, TagType tag,treeNode root);     \r
 243    \r
 244    treeNode SelectFollBelow(treeNode x, std::unordered_set<int> * tags, treeNode root);\r
 245 \r
 246    /** TaggedFollowingSibling(x,tag) */\r
 247    treeNode TaggedFollowingSibling(treeNode x, TagType tag);\r
 248 \r
 249    /** TaggedAncestor(x, tag): returns the closest ancestor of x tagged \r
 250      * tag. Return NULLT is there is none. */\r
 251    treeNode TaggedAncestor(treeNode x, TagType tag);\r
 252  \r
 253    /** PrevText(x): returns the document identifier of the text to the left of \r
 254     * node x, or NULLT if x is the root node. */\r
 255    DocID PrevText(treeNode x);\r
 256    \r
 257    /** NextText(x): returns the document identifier of the text to the right of \r
 258     * node x, or NULLT if x is the root node. */\r
 259    DocID NextText(treeNode x);\r
 260    \r
 261    /** MyText(x): returns the document identifier of the text below node x, or \r
 262     * NULLT if x is not a leaf node. */\r
 263    DocID MyText(treeNode x);\r
 264    \r
 265    /** TextXMLId(d): returns the preorder of document with identifier d in the \r
 266     * tree consisting of all tree nodes and all text nodes. */\r
 267    int TextXMLId(DocID d);\r
 268    \r
 269    /** NodeXMLId(x): returns the preorder of node x in the tree consisting of \r
 270     * all tree nodes and all text nodes. */\r
 271    int NodeXMLId(treeNode x);\r
 272    \r
 273    /** ParentNode(d): returns the parent node of document identifier d. */\r
 274    treeNode ParentNode(DocID d);\r
 275    \r
 276    treeNode PrevNode(DocID d);\r
 277 \r
 278    /** GetTagId(tagname): returns the tag identifier corresponding to a given \r
 279     * tag name. Returns NULLT in case that the tag name does not exists. */\r
 280    TagType GetTagId(unsigned char *tagname);\r
 281 \r
 282    /** GetTagName(tagid): returns the tag name of a given tag identifier. \r
 283     * Returns NULL in case that the tag identifier is not valid.*/\r
 284    unsigned char *GetTagName(TagType tagid);\r
 285 \r
 286    /** GetTagName(tagid): returns the tag name of a given tag identifier.     \r
 287     *  The result is just a reference and should not be freed by the caller.\r
 288     */\r
 289    const unsigned char *GetTagNameByRef(TagType tagid);\r
 290 \r
 291    /** RegisterTag adds a new tag to the tag collection this is needed\r
 292     * if the query contains a tag which is not in the document, we need\r
 293     * to give this new tag a fresh id and store it somewhere. A logical\r
 294     * choice is here.\r
 295     * We might want to use a hashtable instead of an array though.\r
 296     */\r
 297    TagType RegisterTag(unsigned char *tagname);\r
 298 \r
 299    bool EmptyText(DocID i) {\r
 300        return Text->EmptyText(i);\r
 301    }\r
 302 \r
 303    /** Prefix(s): search for texts prefixed by string s. */\r
 304    TextCollection::document_result Prefix(uchar const *s) {\r
 305       return Text->Prefix(s);\r
 306    }\r
 307 \r
 308    /** Suffix(s): search for texts having string s as a suffix. */\r
 309    TextCollection::document_result Suffix(uchar const *s) {\r
 310       return Text->Suffix(s);\r
 311    }\r
 312 \r
 313    /** Equal(s): search for texts equal to string s. */\r
 314    TextCollection::document_result Equal(uchar const *s) {\r
 315       return Text->Equal(s);\r
 316    }\r
 317 \r
 318    /** Contains(s): search for texts containing string s.  */\r
 319    TextCollection::document_result Contains(uchar const *s) {\r
 320       return Text->Contains(s);\r
 321    }\r
 322 \r
 323    /** LessThan(s): returns document identifiers for the texts that\r
 324     * are lexicographically smaller than string s. */\r
 325    TextCollection::document_result LessThan(uchar const *s) {\r
 326       return Text->LessThan(s);\r
 327    }\r
 328    \r
 329    /** IsPrefix(x): returns true if there is a text prefixed by string s. */\r
 330    bool IsPrefix(uchar const *s) {\r
 331       return Text->IsPrefix(s);\r
 332    }          \r
 333    \r
 334    /** IsSuffix(s): returns true if there is a text having string s as a \r
 335     * suffix.*/\r
 336    bool IsSuffix(uchar const *s) {\r
 337       return Text->IsSuffix(s);\r
 338    }\r
 339    \r
 340    /** IsEqual(s): returns true if there is a text that equals given \r
 341     * string s. */\r
 342    bool IsEqual(uchar const *s) {\r
 343       return Text->IsEqual(s);\r
 344    }\r
 345    \r
 346    /** IsContains(s): returns true if there is a text containing string s. */\r
 347    bool IsContains(uchar const *s) {\r
 348       return Text->IsContains(s);\r
 349    }\r
 350    \r
 351    /** IsLessThan(s): returns true if there is at least a text that is \r
 352     * lexicographically smaller than string s. */\r
 353    bool IsLessThan(uchar const *s) {\r
 354       return Text->IsLessThan(s);\r
 355    }\r
 356    \r
 357    /** Count(s): Global counting  */\r
 358    unsigned Count(uchar const *s) {\r
 359       return Text->Count(s);\r
 360    }\r
 361 \r
 362    /** CountPrefix(s): counting version of Prefix(s). */\r
 363    unsigned CountPrefix(uchar const *s) {\r
 364       return Text->CountPrefix(s);\r
 365    }\r
 366    \r
 367    /** CountSuffix(s): counting version of Suffix(s). */\r
 368    unsigned CountSuffix(uchar const *s) {\r
 369       return Text->CountSuffix(s);\r
 370    }\r
 371    \r
 372    /** CountEqual(s): counting version of Equal(s). */\r
 373    unsigned CountEqual(uchar const *s) {\r
 374       return Text->CountEqual(s);\r
 375    }\r
 376    \r
 377    /** CountContains(s): counting version of Contains(s). */\r
 378    unsigned CountContains(uchar const *s) {\r
 379       return Text->CountContains(s);\r
 380    }\r
 381    \r
 382    /** CountLessThan(s): counting version of LessThan(s). */\r
 383    unsigned CountLessThan(uchar const *s) {\r
 384       return Text->CountLessThan(s);\r
 385    }\r
 386    \r
 387    /** GetText(d): returns the text corresponding to document with\r
 388     * id d. */\r
 389    uchar* GetText(DocID d) {\r
 390      uchar * s = Text->GetText(d);\r
 391      return (s[0] == 1 ? (uchar*)"" : s);\r
 392    }\r
 393 \r
 394    /** GetText(i, j): returns the texts corresponding to documents with\r
 395     * ids i, i+1, ..., j. Texts are separated by '\0' character.  */\r
 396    //   uchar* GetText(DocID i, DocID j) {\r
 397    //  uchar * s = Text->GetText(i, j);\r
 398    // return (s[0] == 1 ? (uchar*)"" : s);\r
 399    //}\r
 400 \r
 401    TextCollection *getTextCollection() {\r
 402       return Text;\r
 403    }\r
 404    \r
 405    /** Save: saves XML tree data structure to file. */\r
 406    void Save(int fd);\r
 407       \r
 408    /** Load: loads XML tree data structure from file. sample_rate_text \r
 409     * indicates the sample rate for the text search data structure. */\r
 410    static XMLTree *Load(int fd);   \r
 411 \r
 412    void insertTag(TagType tag, uint position);\r
 413    \r
 414    void print_stats();\r
 415 };\r
 416 #endif\r
 417 \r