XMLTree.h

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