xbuild.c

xtree程序实现

/*
  CSC 5120 Project
  Group 2
  Members : Cheung Ka Leong (99586612) (klcheung@cse)
            Wong Chi Wing   (99681242) (cwwong@cse)
*/

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#include <math.h>

#include <string.h>

#ifndef WIN32
#include <sys/times.h>
#include <unistd.h>
#endif

#include "xtree.h"

#define DEBUG 1

FILE *filePtrID;

void overflow(node_type *, int, int, node_type *, node_type *);

/*
  function : int hasLeafElement(node_type *node, int reqID)
  purpose  : to check whether there is a leaf node with leaf node id reqID 
  parameter: node_type *node - leaf node to be examined
             int reqID       - the node id to be examined
  return   : int - the boolean to represent whether there is a node
                   with node id reqID 
*/
int hasLeafElement(node_type *node, int reqID)
{

	if (node->id == reqID)
	{
		return TRUE;
	}
	else
	{
		return FALSE;
	}
}

/*
  function : int hasInterElement(node_type *node, int reqID)
  purpose  : to check whether there is a leaf node with leaf node id reqID for all
             children at this internal node
  parameter: node_type *node - the internode with all children to be examined
             int reqID       - the node id to be examined
  return   : int - the boolean to represent whether there is a node with node
                   node id reqID for all children at this internal node
*/
int hasInterElement(node_type *node, int reqID)
{
	int i, count;
	int returnValue;

	returnValue = FALSE;

	count = M*node->snodeSize - node->vacancy;
	for (i = 0; i < count; i ++)
	{
		if (node->ptr[i]->attribute != LEAF)
		{
			if (hasInterElement(node->ptr[i], reqID) == TRUE)
			{
				returnValue = TRUE;
			}
		}
		else
		{
			if (hasLeafElement(node->ptr[i], reqID) == TRUE)
			{
				returnValue = TRUE;
			}
		}
	}

	return returnValue;
}


/****************************/
/* Start Utility procedures */
/****************************/
/*
  function : void initialize(config_type *config)
  purpose  : to initialize the configuration file of X-tree
  parameter: config_type *config - the configuration structure
  return   : none
*/
void initialize(config_type *config)
{ 
  FILE *fp;
  int string_len;

  fp = fopen(CONFIG_FILE, "r");

  fscanf(fp, "m=%d\n", &m);
  fscanf(fp, "M=%d\n", &M);
  fscanf(fp, "dim=%d\n", &dim);
  fscanf(fp, "reinsert_p=%d\n", &reinsert_p);
  fscanf(fp, "no_histogram=%d\n",&no_histogram);

  fgets(config->nodefile, FILENAME_MAX, fp);
  string_len = strlen(config->nodefile);
  config->nodefile[string_len-1] = '\0';

  fgets(config->rootfile, FILENAME_MAX, fp);
  string_len = strlen(config->rootfile);
  config->rootfile[string_len-1] = '\0';

  fgets(config->positionfile, FILENAME_MAX, fp);
  string_len = strlen(config->positionfile);
  config->positionfile[string_len-1] = '\0';

  fgets(config->queryfile, FILENAME_MAX, fp);
  string_len = strlen(config->queryfile);
  config->queryfile[string_len-1] = '\0';


} 
/* initialize */

/*
  function : void tree_node_allocate(node_type **node)
  purpose  : to allocate a tree node node
  parameter: node_type **node - a tree node
  return   : none
*/
void tree_node_allocate(node_type **node)
{

  (*node) = (node_type *)malloc(sizeof(node_type));
  (*node)->a = (float *)malloc(sizeof(float) * dim);
  (*node)->b = (float *)malloc(sizeof(float) * dim);
  //(*node)->ptr = (node_type **)malloc(sizeof(node_type *) * MAX_X_SNODE *M);
  (*node)->ptr = (node_type **)malloc(sizeof(node_type *) * M);

  // *** Ray added
  (*node)->snodeSize = 1;
}

void tree_temp_node_allocate(node_type **node, int snodeSize)
{
  (*node) = (node_type *)malloc(sizeof(node_type));
  (*node)->a = (float *)malloc(sizeof(float) * dim);
  (*node)->b = (float *)malloc(sizeof(float) * dim);
  (*node)->ptr = (node_type **)malloc(sizeof(node_type *) * snodeSize *M);

  // *** Ray added
  (*node)->snodeSize = 1;
}

/*
  function : void tree_node_deallocate(node_type *free_node)
  purpose  : to free the node
  parameter: node_type *free_node - the node to be freed
  return   : none
*/
void tree_node_deallocate(node_type *free_node)
{

  free(free_node->a);
  free(free_node->b);
  free(free_node->ptr);

  free(free_node);

}


/*
  function : void cal_MBR_node_node(float *new_a, float *new_b, node_type *node1, node_type *node2)
  purpose  : to calculate the MBR among two nodes
  parameter: float *new_a     - the returned array of the lower bound for each dimension
             float *new_b     - the returned array of the upper bound for each dimension
	     node_type *node1 - the first to be calculated
	     node_type *node2 - the second to be calculated
  return   : none
*/
void cal_MBR_node_node(float *new_a, float *new_b, node_type *node1, node_type *node2)
{
  int i;

  for (i=0; i<dim; i++) {

	if (node1->a[i] < node2->a[i])
		new_a[i] = node1->a[i];
	else
		new_a[i] = node2->a[i];
  }

  for (i=0; i<dim; i++) {

        if (node1->b[i] > node2->b[i])
                new_b[i] = node1->b[i];
        else
                new_b[i] = node2->b[i];
  }

  return;

}

/*
  function : double cal_vol(float *a, float *b)
  purpose  : to calculate the volume of the given bound
  parameter: float *a - the array of the lower bounds for each dimension
             float *b - the array of the upper bounds for each dimension
  return   : double - the volume of the give bounds
*/
double cal_vol(float *a, float *b)
{
  int i;
  double volume = 1.0;

  for (i=0; i<dim; i++)
	volume = volume * (double)(b[i] - a[i]);


  return(volume);

}

/*
  function : double cal_overlap(node_type *node1, node_type *node2)
  purpose  : to calculate the overlap of these given two nodes
  parameter: node_type *node1 - the 1st node
             node_type *node2 - the 2nd node
  return   : double - the overlap of these give two nodes
*/
double cal_overlap(node_type *node1, node_type *node2)
{
  double overlap;

  int i;

  overlap = 1.0;
  for (i=0; i<dim; i++) {

	/* 6 possible cases */

	if (node2->a[i] > node1->b[i] || node1->a[i] > node2->b[i]) {

		overlap = 0.0;
		break;

	}
	else if (node2->a[i] <= node1->a[i]) {

		if (node2->b[i] <= node1->b[i]) {

			// a2, a1, b2, b1

			overlap = overlap * (node2->b[i] - node1->a[i]);

		}
		else {

			// a2, a1, b1, b2

			overlap = overlap * (node1->b[i] - node1->a[i]);

		}
	}
	else if (node1->a[i] < node2->a[i]) {

		if (node2->b[i] <= node1->b[i]) {

			// a1, a2, b2, b1

			overlap = overlap * (node2->b[i] - node2->a[i]);

		}
		else {

			// a1, a2, b1, b2

			overlap = overlap * (node1->b[i] - node2->a[i]);

		}

	}


	// *** Ray added
	overlap *= 100;

  }


  return(overlap);

}

/*
  function : double cal_overlap_sum(node_type *node, int index_skip,  node_type *parent_node)
  purpose  : to calculate the sum of the overlap between the node and all children nodes
             (except the index specified) of the parent node parent_node
  parameter: node_type *node        - the node to be calculated with the overlap
             int index_skip         - the index of the children to be skipped to calculate the overlap
             node_type *parent_node - the parent node with all children to be calculated with the overlap
  return   : double - the sum of the overlap between the node and all children nodes (except the
                      index specified) of the parent node parent_node
*/
double cal_overlap_sum(node_type *node, int index_skip,  node_type *parent_node)
{
  double overlap;

  int i, stop;


  overlap = 0.0;
  // **** Ray changed
  //stop = M - parent_node->vacancy;
  stop = parent_node->snodeSize*M - parent_node->vacancy;
  for (i=0; i<stop; i++) {

	if (i == index_skip) continue;
// ***** To be Changed
if (i == 13) 
{
	//parent_node->ptr[i] = parent_node->ptr[i-1];
	//printf("Hello!\n");
}
	overlap = overlap + cal_overlap(parent_node->ptr[i], node);

  }


  return(overlap);

}

/*
  function : double Dist2(node_type *node1, node_type *node2)
  purpose  : to calculate the distance between the centers of two nodes
  parameter: node_type *node1 - the first node to be calculated with the distance
             node_type *node2 - the second node to be calculated with the distance
  return   : double - the distance between the centers of two nodes
*/
double Dist2(node_type *node1, node_type *node2)
{
  double distance;
  float *point1, *point2;

  int i;

  point1 = (float *)malloc(sizeof(float) * dim);
  point2 = (float *)malloc(sizeof(float) * dim);

  for (i=0; i<dim; i++) {
	// *** Ray has type casting the following with float type
	point1[i] = (float)((node1->b[i] - node1->a[i])/2.0);
	point2[i] = (float)((node2->b[i] - node2->a[i])/2.0);
  }

  distance = 0.0;
  for (i=0; i<dim; i++) {
	distance = distance + pow((double)(point1[i] - point2[i]), 2.0);
  }

  return(pow(distance, 0.5));

}


/**************************/
/* End Utility procedures */
/**************************/

/*
  function : int least_overlap_enlarge(node_type *parent_node, node_type  *data_node)
  purpose  : to return the index of the children such that the overlap enlargement
             is minimum when the data_node is inserted to parent_node
  parameter: node_type *parent_node - the parent node in which the data node is inserted
             node_type *data_node   - the data node to be inserted to the parent node
  return   : int - the index of the best children of the parent node to be inserted
*/
int least_overlap_enlarge(node_type *parent_node, node_type  *data_node)
{
  double new_overlap_diff, old_overlap, new_overlap; 
  double vol_at_index, new_vol, min_overlap_diff;
  int index;
  node_type *temp_node;

  int i, stop;
 

  tree_node_allocate(&temp_node);

  // **** Ray changed
  //stop = M - parent_node->vacancy;
  stop = parent_node->snodeSize*M - parent_node->vacancy;
  for(i=0; i<stop; i++) {

        /* original overlap */
   
        old_overlap = cal_overlap_sum(parent_node->ptr[i], i, parent_node);
 
        /* overlap after enlargement */
 
        cal_MBR_node_node(temp_node->a, temp_node->b, parent_node->ptr[i], data_node);
  
        new_overlap = cal_overlap_sum(temp_node, i, parent_node);

        /* check if index is needed to updated */
        new_overlap_diff = new_overlap - old_overlap;

	if (i == 0) {

                index = i;
                min_overlap_diff = new_overlap_diff;   

	}
	else {
        	if (new_overlap_diff < min_overlap_diff) {
                	index = i;
	                min_overlap_diff = new_overlap_diff;
        	}
        	else if (new_overlap_diff == min_overlap_diff) {

			vol_at_index = cal_vol(parent_node->ptr[index]->a, parent_node->ptr[index]->b);
			new_vol = cal_vol(temp_node->a, temp_node->b);
	                if(new_vol < vol_at_index) {

        	                index=i;

	                }
		}
       	}
        
  }  /* end i */

  tree_node_deallocate(temp_node);
        
                
  return (index);
                
}



/********************************************************/
/* least_area_enlarge():                                */
/* Select the node which will cause least bounding      */
/* box enlargement when insert an entry to it           */
/********************************************************/
/*
  function : int least_area_enlarge(node_type *parent_node, node_type *data_node)
  purpose  : to return the index of the children such that the area enlargement
             is minimum when the data_node is inserted to parent_node
  parameter: node_type *parent_node - the parent node in which the data node is inserted
             node_type *data_node   - the data node to be inserted to the parent node
  return   : int - the index of the best children of the parent node to be inserted
*/
int least_area_enlarge(node_type *parent_node, node_type *data_node)
{ 
  double new_vol_diff, old_vol, new_vol;
  double vol_at_index, min_vol_diff;
  int index;
  float *temp_a, *temp_b;
  int i, stop;

  temp_a = (float *)malloc(sizeof(float) * dim);
  temp_b = (float *)malloc(sizeof(float) * dim);

  // *** Ray changed
  //stop = M - parent_node->vacancy;
  stop = parent_node->snodeSize*M - parent_node->vacancy;
if (parent_node->snodeSize > 1)
{
	printf("snode Size : %d\n", parent_node->snodeSize);
}
if (stop > 13)
{
	printf("  stop : %d\n", stop);
}
  for(i=0; i<stop; i++) { 

	/* original volume */

	old_vol = cal_vol(parent_node->ptr[i]->a, parent_node->ptr[i]->b);            	

	/* volume after enlargement */

	cal_MBR_node_node(temp_a, temp_b, parent_node->ptr[i], data_node);

	new_vol = cal_vol(temp_a, temp_b);

	/* check if index is needed to updated */
        new_vol_diff = new_vol - old_vol;

	if (i == 0) {

                index = i;
                min_vol_diff = new_vol_diff;
                vol_at_index = new_vol;

	}
	else {
		if (new_vol_diff < min_vol_diff) { 
			index = i;
           		min_vol_diff = new_vol_diff;
	           	vol_at_index = new_vol;
		}
		else if (new_vol_diff == min_vol_diff) { 
			if(new_vol < vol_at_index) {
              			index=i;
              			vol_at_index = new_vol;
			}
	        }
	}
      
  }  /* end i */

  free(temp_a);
  free(temp_b);
            
  return (index);

} 
/* least_enlarge */




/**********************************************************/
/* choose_leaf():                                         */
/* Select a leaf node in which to place a new index entry */
/* current_level is the level of the current_node	  */
/**********************************************************/
/*
  function : int choose_leaf(node_type **node_found, node_type *current_node, int 
             current_level, node_type *data_node) 
  purpose  : Select a leaf node in which to place a new index entry
             current_level is the level of the current_node
  parameter: node_type **node_found  - the node found
             node_type *current_node - the current node
	     int current_level       - current level
	     node_type *data_node    - the data node to be inserted
  return   : int - the index of the children for the best leaf node to place a new
                   index entry
*/
int choose_leaf(node_type **node_found, node_type *current_node, int 
current_level, node_type *data_node) 
{

  int child_chosen, level_found;

  /*******/
  /* CL1 */
  /*******/
  
  /**********************************************************/
  /* Initialise: 			     		    */  
  /* Set N to be the root node(already done in insert_node) */
  /**********************************************************/

  /*  It has been already done in insert()  */

  /*******/
  /* CL2 */
  /*******/

  /**************/
  /* Leaf check */
  /**************/
  
  if(current_node->attribute == ROOT && (current_node->ptr[0]==NULL || current_node->ptr[0]->attribute==LEAF)) { 

	/************************************************************
	*node_found is the root of the tree because the root is 
	the only internal node of the tree at that time.
	*************************************************************/

   	return(current_level);		// root is at level 0				

  }
/*
printf("currentLevel:%d\n", current_level);
if (current_node == NULL) printf("current_node is NULL!\n");
if (current_node->ptr[0] == NULL) 
{printf(" ptr[0] is NULL!\n");

 //printf(" NOde type : %d\n", 
}
printf("   node size: %d\n", current_node->snodeSize);
*/
  if (current_node->ptr[0]->attribute == LEAF) {
        *node_found = current_node;
        return(current_level);
  }

  /*******/
  /* CL3 */
  /*******/

  /******************/