\r
#ifndef XMLTREE_H_\r
#define XMLTREE_H_\r
-extern "C" {\r
-#define CAML_NAME_SPACE\r
-#include <caml/mlvalues.h>\r
-#include <caml/custom.h>\r
-#define XMLTREE(x) ((XMLTree *)(* (XMLTree**) Data_custom_val(x)))\r
- //#define XMLTREE(x) ((XMLTree*) (x))\r
-}\r
+\r
+\r
#include <unordered_set>\r
#include <unordered_map>\r
#include <sstream>\r
#include "TextCollection/TextCollectionBuilder.h"\r
\r
-#include <cstdio>\r
-#include <cstdlib>\r
-#include <cstring>\r
-\r
-\r
#undef W\r
#undef WW\r
#undef Wminusone\r
using SXSI::TextCollectionBuilder;\r
\r
\r
-\r
// this constant is used to efficiently compute the child operation in the tree\r
#define OPTD 10\r
\r
\r
\r
typedef std::unordered_set<int> TagIdSet;\r
-typedef std::unordered_map<string,int> TagIdMap;\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
-\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 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
bp *Par;\r
\r
/** Mapping from tag identifer to tag name */ \r
- vector<string> *TagName;\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
bool disable_tc;\r
\r
FILE* stream;\r
- int stream_fd;\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(){;};\r
+ XMLTree(){ buffer = 0;};\r
\r
// non const pointer are freed by this method.\r
- XMLTree( pb * const par, uint npar, vector<string> * const TN, TagIdMap * const tim, uint *empty_texts_bmp, TagType *tags,\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
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
/** IsFirstChild(x): returns whether node x is the first child of its parent. */\r
/* OCAML */\r
- bool IsFirstChild(treeNode x);\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
* tree nodes (and not texts). */\r
int Postorder(treeNode x);\r
\r
- /** Tag(x): returns the tag identifier of node x. */\r
- TagType Tag(treeNode x) {\r
- if (tags_blen == 8)\r
- return (TagType) (((uchar*)tags_fix)[(int) x]);\r
- else\r
- return (TagType) get_field(tags_fix,tags_blen, (int) 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
+ 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
- /** FirstChild(x): returns the first child of node x, or NULLT if the node is a leaf\r
- */\r
- treeNode FirstChild(treeNode x);\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
- value CamlFirstElement(value x);\r
+\r
/** LastChild(x): returns the last child of node x. */\r
treeNode LastChild(treeNode x);\r
\r
- /** NextSibling(x): returns the next sibling of node x, or NULLT if none \r
- * exists. */\r
\r
- treeNode NextSibling(treeNode x);\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
- value CamlNextElement(value x);\r
/** PrevSibling(x): returns the previous sibling of node x, assuming it \r
* exists. */\r
\r
\r
treeNode SelectFollowingSibling(treeNode x, TagIdSet * tags);\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
- treeNode TaggedDescendant(treeNode x, TagType tag);\r
\r
- treeNode SelectDescendant(treeNode x, TagIdSet * tags);\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 TaggedFollowing(treeNode x, TagType tag);\r
\r
- treeNode TaggedFollowingBelow(treeNode x, TagType tag,treeNode ancestor); \r
+\r
\r
treeNode SelectFollowingBelow(treeNode x, TagIdSet * tags, treeNode ancestor);\r
\r
- treeNode TaggedFollowingBefore(treeNode x, TagType tag,treeNode closing);\r
+ // treeNode TaggedFollowingBefore(treeNode x, TagType tag,treeNode closing);\r
\r
treeNode SelectFollowingBefore(treeNode x, TagIdSet * tags, treeNode closing);\r
\r
uchar* GetText(DocID d) {\r
\r
uchar * s = Text->GetText(d);\r
- return (s[0] == 1 ? (uchar*)"" : s);\r
+ return (s[0] == 1 ? (s+1) : s);\r
}\r
\r
/** GetText(i, j): returns the texts corresponding to documents with\r
}\r
\r
/** Save: saves XML tree data structure to file. */\r
- void Save(int fd);\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,bool load_tc, int sample_factor); \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(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
};\r
\r
-extern "C" value caml_cpp_fast_first_element(value xmltree, value node);\r
-extern "C" value caml_cpp_fast_next_element(value xmltree, value node);\r
\r
\r
\r
projects / SXSI / XMLTree.git / blobdiff