--- /dev/null
+#include "XMLTree.h"
+#include "Utils.h"
+#include <stdlib.h>
+#include <stdio.h>
+#include <sys/time.h>
+#include <time.h>
+#include <sys/types.h>
+#include <sys/stat.h>
+#include <errno.h>
+#include <strings.h>
+#include <fcntl.h>
+#include <malloc.h>
+#include "timings.h"
+
+
+using std::cout;
+using std::string;
+using std::left;
+using std::right;
+using std::cerr;
+
+
+#define NUM_PATHS 10000
+#define RANDOM(m) ((unsigned long int) (random() % (m)))
+
+#define OUTPUT_LINE() (std::cerr << "------------------------------------\n\n")
+#define SRX_MAGIC_STRING "SXSI_INDEX\n"
+#define SRX_VERSION "2\n"
+#define READ_UCHAR(pchar,file) do { \
+ if (fread((pchar),sizeof(char),1,(file)) == 0) { \
+ std::cerr << "Error: Invalid .srx file\n"; \
+ return NULL; \
+ }; \
+ } while(0) \
+
+
+extern "C" {
+ typedef void ** tree_node;
+
+#define SIZE(v) (((unsigned long) ((v)[0])) >> 1)
+#define ISBINARY(v) (((unsigned long) ((v)[0])) & 1)
+#define CHILDR(v,i) (((tree_node)(v))[(i)+1])
+#define CHILD(v,i) ((tree_node) (((tree_node)(v))[(i)+1]))
+
+ static tree_node create_node(long size,int binary){
+ tree_node node = (tree_node) malloc(sizeof(void*) * (size+1));
+ if (node) {
+ binary = binary & 1;
+ node[0] = (void *) (size << 1 | binary);
+ node[1] = NULL;
+ node[2] = NULL;
+ };
+ return node;
+ }
+
+ tree_node create_naive(XMLTree *tree, treeNode node, int prealloc){
+ if (node == NULLT)
+ return NULL;
+ else {
+ tree_node self;
+ if (prealloc)
+ self = create_node(2,1);
+
+ tree_node first = create_naive(tree,tree->FirstChild(node),prealloc);
+ tree_node next = create_naive(tree,tree->NextSibling(node),prealloc);
+ if (!prealloc)
+ self = create_node(2,1);
+ self[0] = (void *) (tree->NumChildren(node) << 1 | 1);
+ self[1] = first;
+ self[2] = next;
+
+ return self;
+ };
+ }
+
+ tree_node create_with_child_array(XMLTree *tree, treeNode node){
+ if (tree==NULL)
+ return NULL;
+ else {
+ long size = (long) tree->NumChildren(node);
+ tree_node self = create_node(size,0);
+ treeNode child = tree->FirstChild(node);
+ for(int i = 0; i < size; i++){
+ CHILDR(self,i) = create_with_child_array(tree,child);
+ child = tree->NextSibling(child);
+ };
+ return self;
+ };
+
+ }
+
+ static unsigned long my_malloc_idx;
+
+ tree_node my_malloc_create_node(tree_node pool) {
+ tree_node ret;
+ ret = &pool[my_malloc_idx * 3];
+ my_malloc_idx++;
+ return ret;
+ }
+
+ tree_node create_perfect_rec(XMLTree *tree, treeNode node, tree_node pool ,int prealloc ) {
+ if (node == NULLT)
+ return NULL;
+ else {
+ tree_node self;
+ if (prealloc)
+ self = my_malloc_create_node(pool);
+
+ tree_node first = create_naive(tree,tree->FirstChild(node),prealloc);
+ tree_node next = create_naive(tree,tree->NextSibling(node),prealloc);
+ if (!prealloc)
+ self = my_malloc_create_node(pool);
+ self[0] = (void *) (tree->NumChildren(node) << 1 | 1);
+ self[1] = first;
+ self[2] = next;
+
+ return self;
+ };
+
+ }
+
+ tree_node create_perfect(XMLTree *tree, int prealloc){
+ tree_node v = (tree_node) malloc(sizeof(void*)*3 * tree->Size());
+ my_malloc_idx = 0;
+ if (v)
+ create_perfect_rec(tree,0,v,prealloc);
+
+ return v;
+
+ }
+
+ void unranked_preorder(tree_node node){
+ if (node == NULL)
+ return;
+ for(unsigned long i = 0; i < SIZE(node); i++)
+ unranked_preorder(CHILD(node,i));
+ };
+
+ void binary_preorder(tree_node node){
+ if (node == NULL)
+ return;
+
+ binary_preorder( (tree_node) (node[1]));
+ binary_preorder( (tree_node) (node[2]));
+ };
+
+ void nsfs_order(tree_node node){
+ if (node == NULL)
+ return;
+
+ binary_preorder( (tree_node) (node[2]));
+ binary_preorder( (tree_node) (node[1]));
+ };
+
+
+
+ void pre_order(tree_node node){
+ if (node == NULL)
+ return;
+ if (ISBINARY(node))
+ binary_preorder(node);
+ else
+ unranked_preorder(node);
+ return;
+ }
+
+
+ tree_node binary_nth_child (tree_node node, unsigned long n){
+ if (n >= SIZE(node))
+ return NULL;
+
+ tree_node child = CHILD(node,0);
+ for(unsigned long i = 0; i < n; i ++)
+ child=CHILD(child,1);
+ return child;
+
+ }
+
+
+ void binary_random_path(tree_node node){
+ if (node == NULL || SIZE(node) == 0)
+ return;
+ binary_random_path(binary_nth_child(node,RANDOM(SIZE(node))));
+ }
+
+ unsigned long crc = 0;
+
+ void unranked_random_path(tree_node node){
+ if (node == NULL || SIZE(node) == 0)
+ return;
+ unsigned long n = RANDOM(SIZE(node));
+ crc+=n;
+ unranked_random_path(CHILD(node,n));
+ }
+
+ void random_path(tree_node node){
+ if (ISBINARY(node))
+ binary_random_path(node);
+ else
+ unranked_random_path(node);
+
+ }
+
+ void delete_tree_node(tree_node node){
+ if (node) {
+ if (ISBINARY(node)) {
+ delete_tree_node((tree_node) (node[1]));
+ delete_tree_node((tree_node) (node[2]));
+ }
+ else
+ for(unsigned long i = 0; i < SIZE(node); i++)
+ delete_tree_node(CHILD(node,i));
+
+ free(node);
+ };
+ }
+
+}
+
+void xml_tree_preorder(XMLTree* tree, treeNode node){
+ if (node == NULLT)
+ return;
+
+ xml_tree_preorder(tree,tree->FirstChild(node));
+ xml_tree_preorder(tree,tree->NextSibling(node));
+
+}
+void xml_tree_unranked_preorder(XMLTree* tree,treeNode node){
+ if (node == NULLT|| tree->IsLeaf(node))
+ return;
+
+ for(int i = 1; i <= tree->NumChildren(node); i++)
+ xml_tree_unranked_preorder(tree,tree->Child(node,i));
+
+}
+
+void xml_tree_nsfc(XMLTree* tree, treeNode node){
+ if (node == NULLT)
+ return;
+
+ xml_tree_preorder(tree,tree->NextSibling(node));
+ xml_tree_preorder(tree,tree->FirstChild(node));
+
+
+}
+
+
+void xml_tree_time_siblings(XMLTree* tree){
+ treeNode first = tree->FirstChild(0);
+ unsigned long children = tree->NumChildren(first);
+ unsigned long print = children / 100;
+ treeNode child;
+ double max_time = 0;
+ double max_i = 0;
+ double time = 0;
+ std::cerr << children << " children\n";
+ std::cerr << "Timings:\n";
+ for(unsigned long i = 1; i<= children;i++){
+ STARTTIMER();
+ for(int j = 0; j < 5; j++)
+ child = tree->Child(first,i);
+ STOPTIMER(Parsing);
+ time = tParsing / 5.0;
+ if (time >= max_time){
+ max_time = time;
+ max_i = i;
+ };
+ };
+ std::cerr << "Peak for node " << max_i << " : " << time << "\n";
+ return;
+
+}
+
+
+void xml_tree_lcps(XMLTree * tree, treeNode node){
+ if (node == NULLT)
+ return;
+
+ xml_tree_lcps(tree,tree->LastChild(node));
+ xml_tree_lcps(tree,tree->PrevSibling(node));
+}
+
+void xml_tree_random_path(XMLTree *tree, treeNode node){
+ if (node == NULLT|| tree->IsLeaf(node))
+ return;
+ unsigned long n = (unsigned long) RANDOM(tree->NumChildren(node));
+ crc+=n;
+ xml_tree_random_path(tree,tree->Child(node,1+n));
+}
+
+
+XMLTree* load_srx(const char* file){
+
+ char buffer[1024];
+ char * read_;
+ int fd = open(file,O_RDONLY);
+ FILE* fp = fdopen(fd, "r");
+ unsigned int u32 = 0;
+ unsigned char cbuff;
+ XMLTree* tree;
+
+ if (fp == NULL) {
+ std::cerr << "Error: " << strerror(errno) << "\n";
+ return NULL;
+ };
+
+ read_ = fgets(buffer,1023, fp);
+
+ if (read_ == NULL || (strncmp(buffer,SRX_MAGIC_STRING,1023) != 0)){
+ std::cerr << "Error: Invalid .srx file\n";
+ return NULL;
+ };
+
+ read_ = fgets(buffer,1023,fp);
+
+ if (read_ == NULL || (strncmp(buffer,SRX_VERSION,1023) != 0)){
+ std::cerr << "Error: Invalid .srx file\n";
+ return NULL;
+ };
+
+ //OCaml marshaled data structure
+ //Skip the first 4 bytes = unsigned int 32
+ READ_UCHAR(&cbuff,fp);
+ READ_UCHAR(&cbuff,fp);
+ READ_UCHAR(&cbuff,fp);
+ READ_UCHAR(&cbuff,fp);
+
+ READ_UCHAR(&cbuff,fp);
+ u32 = cbuff << 24;
+ READ_UCHAR(&cbuff,fp);
+ u32 += cbuff << 16;
+ READ_UCHAR(&cbuff,fp);
+ u32 += cbuff << 8;
+ READ_UCHAR(&cbuff,fp);
+ u32 += cbuff;
+ // u32 is the data size, we need now to skip (data_size + 20) - (4 * 2) bytes
+ // 20 is the header_size defined in marshal.ml
+ if (fseek(fp,u32+20-8, SEEK_CUR) == -1){
+ std::cerr << "Error: " << strerror(errno) << "\n";
+ return NULL;
+ };
+
+ // Now we point to the correct area in the file
+ // We make sure that the fd is at the correct position and call XMLTree::Load
+ if (lseek(fd,ftell(fp),SEEK_SET) == -1){
+ std::cerr << "Error: " << strerror(errno) << "\n";
+ return NULL;
+ };
+ //Sampling factor is ignored
+ tree = XMLTree::Load(fd,true,64);
+ fclose(fp); //also closes fd!
+ return tree;
+
+}
+
+int main(int argc,char ** argv ){
+ XMLTree *tree;
+ tree_node naive;
+ if (argc != 2) {
+ std::cerr << "Usage: " << argv[0] << " file.srx\n";
+ exit (1);
+ };
+
+ STARTTIMER();
+ tree = load_srx(argv[1]);
+ STOPTIMER(Loading);
+ PRINTTIME("Loading SRX file from disk",Loading);
+
+ OUTPUT_LINE();
+ /*
+ // Naive pointer structure, allocated in post order
+ STARTTIMER();
+ naive = create_naive(tree,0,1);
+ STOPTIMER(Building);
+ PRINTTIME("Building pre-order allocated binary structure",Building);
+
+ STARTTIMER();
+ pre_order(naive);
+ STOPTIMER(Parsing);
+ PRINTTIME("Preoder traversal",Parsing);
+
+ STARTTIMER();
+ nsfs_order(naive);
+ STOPTIMER(Parsing);
+ PRINTTIME("NextSibling/FirstChild",Parsing);
+
+ srandom(1);
+ STARTTIMER();
+ for(int i = 0; i < NUM_PATHS; i++)
+ random_path(naive);
+
+ STOPTIMER(Parsing);
+ PRINTTIME("10000 random paths",Parsing);
+
+ STARTTIMER();
+ delete_tree_node(naive);
+ STOPTIMER(Parsing);
+ PRINTTIME("Freeing structure",Parsing);
+
+ OUTPUT_LINE();
+
+ // Naive pointer structure, allocated in pre-order
+ STARTTIMER();
+ naive = create_naive(tree,0,0);
+ STOPTIMER(Building);
+ PRINTTIME("Building post-order allocated binary pointer structure",Building);
+ STARTTIMER();
+ pre_order(naive);
+ STOPTIMER(Parsing);
+ PRINTTIME("Preoder traversal",Parsing);
+
+ STARTTIMER();
+ nsfs_order(naive);
+ STOPTIMER(Parsing);
+ PRINTTIME("NextSibling/FirstChild",Parsing);
+
+ srandom(1);
+ STARTTIMER();
+ for(int i = 0; i < NUM_PATHS; i++)
+ random_path(naive);
+
+ STOPTIMER(Parsing);
+ PRINTTIME("10000 random paths",Parsing);
+
+
+ STARTTIMER();
+ delete_tree_node(naive);
+ STOPTIMER(Parsing);
+ PRINTTIME("Freeing structure",Parsing);
+
+ OUTPUT_LINE();
+
+
+
+ STARTTIMER();
+ naive = create_with_child_array(tree,0);
+ STOPTIMER(Building);
+ PRINTTIME("Building child array structure",Building);
+ STARTTIMER();
+ pre_order(naive);
+ STOPTIMER(Parsing);
+ PRINTTIME("Preoder traversal",Parsing);
+
+ srandom(1);
+ STARTTIMER();
+ for(int i = 0; i < NUM_PATHS; i++)
+ random_path(naive);
+
+ STOPTIMER(Parsing);
+ PRINTTIME("10000 random paths",Parsing);
+
+ std::cerr << "crc = " << crc << "\n";
+ STARTTIMER();
+ delete_tree_node(naive);
+ STOPTIMER(Parsing);
+ PRINTTIME("Freeing structure",Parsing);
+
+ OUTPUT_LINE();
+
+
+ // Naive pointer structure, allocated in pre-order
+ STARTTIMER();
+ naive = create_perfect(tree,1);
+ STOPTIMER(Building);
+ PRINTTIME("Building pre-order pre-allocated contiguous binary structure",Building);
+ STARTTIMER();
+ pre_order(naive);
+ STOPTIMER(Parsing);
+ PRINTTIME("Preoder traversal",Parsing);
+
+ STARTTIMER();
+ nsfs_order(naive);
+ STOPTIMER(Parsing);
+ PRINTTIME("NextSibling/FirstChild",Parsing);
+
+ srandom(1);
+ STARTTIMER();
+ for(int i = 0; i < NUM_PATHS; i++)
+ random_path(naive);
+
+ STOPTIMER(Parsing);
+ PRINTTIME("10000 random paths",Parsing);
+
+ STARTTIMER();
+ free(naive);
+ STOPTIMER(Parsing);
+ PRINTTIME("Freeing structure",Parsing);
+
+ OUTPUT_LINE();
+
+ // Naive pointer structure, allocated in pre-order
+ STARTTIMER();
+ naive = create_perfect(tree,0);
+ STOPTIMER(Building);
+ PRINTTIME("Building post-order pre-allocated contiguous binary structure",Building);
+ STARTTIMER();
+ pre_order(naive);
+ STOPTIMER(Parsing);
+ PRINTTIME("Preoder traversal",Parsing);
+
+ STARTTIMER();
+ nsfs_order(naive);
+ STOPTIMER(Parsing);
+ PRINTTIME("NextSibling/FirstChild",Parsing);
+
+ srandom(1);
+ STARTTIMER();
+ for(int i = 0; i < NUM_PATHS; i++)
+ random_path(naive);
+
+ STOPTIMER(Parsing);
+ PRINTTIME("10000 random paths",Parsing);
+ std::cerr << "crc = " << crc << "\n";
+ STARTTIMER();
+ free(naive);
+ STOPTIMER(Parsing);
+ PRINTTIME("Freeing structure",Parsing);
+
+ OUTPUT_LINE();
+
+ // XMLTree structure
+ std::cerr << "Timing XMLTree structure\n";
+ STARTTIMER();
+
+ xml_tree_preorder(tree,0);
+ STOPTIMER(Parsing);
+ PRINTTIME("Preoder traversal",Parsing);
+
+ STARTTIMER();
+ xml_tree_nsfc(tree,0);
+ STOPTIMER(Parsing);
+ PRINTTIME("NextSibling/FirstChild",Parsing);
+
+ STARTTIMER();
+ xml_tree_unranked_preorder(tree,0);
+ STOPTIMER(Parsing);
+ PRINTTIME("Unranked pre-order",Parsing);
+
+ srandom(1);
+ STARTTIMER();
+ crc = 0;
+ for(int i = 0; i < NUM_PATHS; i++)
+ xml_tree_random_path(tree,0);
+
+ STOPTIMER(Parsing);
+ PRINTTIME("10000 random paths",Parsing);
+ std::cerr << "crc = " << crc << "\n";
+ OUTPUT_LINE();
+ */
+ xml_tree_time_siblings(tree);
+
+
+ exit(0);
+};
+
projects / SXSI / xpathcomp.git / blobdiff